f85c69e34b8cdbce9d4704c2bf86a5d4ada890cd
[BackupPC.git] / lib / BackupPC / Xfer / RsyncDigest.pm
1 #============================================================= -*-perl-*-
2 #
3 # BackupPC::Xfer::RsyncDigest package
4 #
5 # DESCRIPTION
6 #
7 #   This library defines a BackupPC::Xfer::RsyncDigest class for computing
8 #   and caching rsync checksums.
9 #
10 # AUTHOR
11 #   Craig Barratt  <cbarratt@users.sourceforge.net>
12 #
13 # COPYRIGHT
14 #   Copyright (C) 2001-2007  Craig Barratt
15 #
16 #   This program is free software; you can redistribute it and/or modify
17 #   it under the terms of the GNU General Public License as published by
18 #   the Free Software Foundation; either version 2 of the License, or
19 #   (at your option) any later version.
20 #
21 #   This program is distributed in the hope that it will be useful,
22 #   but WITHOUT ANY WARRANTY; without even the implied warranty of
23 #   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
24 #   GNU General Public License for more details.
25 #
26 #   You should have received a copy of the GNU General Public License
27 #   along with this program; if not, write to the Free Software
28 #   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
29 #
30 #========================================================================
31 #
32 # Version 3.1.0beta0, released 3 Sep 2007.
33 #
34 # See http://backuppc.sourceforge.net.
35 #
36 #========================================================================
37
38 package BackupPC::Xfer::RsyncDigest;
39
40 use strict;
41 use BackupPC::FileZIO;
42
43 use vars qw( $RsyncLibOK );
44 use Carp;
45 use Fcntl;
46 require Exporter;
47 use vars qw( @ISA @EXPORT @EXPORT_OK %EXPORT_TAGS );
48
49 my $Log = \&logHandler;
50
51 #
52 # Magic value for checksum seed.  We only cache block and file digests
53 # when the checksum seed matches this value.
54 #
55 use constant RSYNC_CSUMSEED_CACHE     => 32761;
56
57 @ISA = qw(Exporter);
58
59 @EXPORT    = qw( );
60
61 @EXPORT_OK = qw(
62                   RSYNC_CSUMSEED_CACHE
63              );
64
65 %EXPORT_TAGS = (
66     'all'    => [ @EXPORT_OK ],
67 );
68
69 BEGIN {
70     eval "use File::RsyncP;";
71     if ( $@ ) {
72         #
73         # File::RsyncP doesn't exist.  Define some dummy constant
74         # subs so that the code below doesn't barf.
75         #
76         $RsyncLibOK = 0;
77     } else {
78         $RsyncLibOK = 1;
79     }
80 };
81
82 #
83 # Return the rsync block size based on the file size.
84 # We also make sure the block size plus 4 (ie: cheeksumSeed)
85 # is not a multiple of 64 - otherwise the cached checksums
86 # will not be the same for protocol versions <= 26 and > 26.
87 #
88 sub blockSize
89 {
90     my($class, $fileSize, $defaultBlkSize) = @_;
91
92     my $blkSize = int($fileSize / 10000);
93     $blkSize = $defaultBlkSize if ( $blkSize < $defaultBlkSize );
94     $blkSize = 16384 if ( $blkSize > 16384 );
95     $blkSize += 4 if ( (($blkSize + 4) % 64) == 0 );
96     return $blkSize;
97 }
98
99 sub fileDigestIsCached
100 {
101     my($class, $file) = @_;
102     my $data;
103
104     sysopen(my $fh, $file, O_RDONLY) || return -1;
105     binmode($fh);
106     return -2 if ( sysread($fh, $data, 1) != 1 );
107     close($fh);
108     return $data eq chr(0xd7) ? 1 : 0;
109 }
110
111 #
112 # Compute and add rsync block and file digests to the given file.
113 #
114 # Empty files don't get cached checksums.
115 #
116 # If verify is set then existing cached checksums are checked.
117 # If verify == 2 then only a verify is done; no fixes are applied.
118
119 # Returns 0 on success.  Returns 1 on good verify and 2 on bad verify.
120 # Returns a variety of negative values on error.
121 #
122 sub digestAdd
123 {
124     my($class, $file, $blockSize, $checksumSeed, $verify,
125                 $protocol_version) = @_;
126     my $retValue = 0;
127
128     #
129     # Don't cache checksums if the checksumSeed is not RSYNC_CSUMSEED_CACHE
130     # or if the file is empty.
131     #
132     return -100 if ( $checksumSeed != RSYNC_CSUMSEED_CACHE || !-s $file );
133
134     if ( $blockSize == 0 ) {
135         &$Log("digestAdd: bad blockSize ($file, $blockSize, $checksumSeed)");
136         $blockSize = 2048;
137     }
138     my $nBlks = int(65536 * 16 / $blockSize) + 1;
139     my($data, $blockDigest, $fileDigest);
140
141     return -101 if ( !$RsyncLibOK );
142
143     my $digest = File::RsyncP::Digest->new;
144     $digest->protocol($protocol_version)
145                         if ( defined($protocol_version) );
146     $digest->add(pack("V", $checksumSeed)) if ( $checksumSeed );
147
148     return -102 if ( !defined(my $fh = BackupPC::FileZIO->open($file, 0, 1)) );
149
150     my $fileSize;
151     while ( 1 ) {
152         $fh->read(\$data, $nBlks * $blockSize);
153         $fileSize += length($data);
154         last if ( $data eq "" );
155         $blockDigest .= $digest->blockDigest($data, $blockSize, 16,
156                                              $checksumSeed);
157         $digest->add($data);
158     }
159     $fileDigest = $digest->digest2;
160     my $eofPosn = sysseek($fh->{fh}, 0, 1);
161     $fh->close;
162     my $rsyncData = $blockDigest . $fileDigest;
163     my $metaData  = pack("VVVV", $blockSize,
164                                  $checksumSeed,
165                                  length($blockDigest) / 20,
166                                  0x5fe3c289,                # magic number
167                         );
168     my $data2 = chr(0xb3) . $rsyncData . $metaData;
169 #    printf("appending %d+%d bytes to %s at offset %d\n",
170 #                                            length($rsyncData),
171 #                                            length($metaData),
172 #                                            $file,
173 #                                            $eofPosn);
174     sysopen(my $fh2, $file, O_RDWR) || return -103;
175     binmode($fh2);
176     return -104 if ( sysread($fh2, $data, 1) != 1 );
177     if ( $data ne chr(0x78) && $data ne chr(0xd6) && $data ne chr(0xd7) ) {
178         &$Log(sprintf("digestAdd: $file has unexpected first char 0x%x",
179                              ord($data)));
180         return -105;
181     }
182     return -106 if ( sysseek($fh2, $eofPosn, 0) != $eofPosn );
183     if ( $verify ) {
184         my $data3;
185
186         #
187         # Verify the cached checksums
188         #
189         return -107 if ( $data ne chr(0xd7) );
190         return -108 if ( sysread($fh2, $data3, length($data2) + 1) < 0 );
191         if ( $data2 eq $data3 ) {
192             return 1;
193         }
194         #
195         # Checksums don't agree - fall through so we rewrite the data
196         #
197         &$Log(sprintf("digestAdd: %s verify failed; redoing checksums; len = %d,%d; eofPosn = %d, fileSize = %d",
198                 $file, length($data2), length($data3), $eofPosn, $fileSize));
199         #&$Log(sprintf("dataNew  = %s", unpack("H*", $data2)));
200         #&$Log(sprintf("dataFile = %s", unpack("H*", $data3)));
201         return -109 if ( sysseek($fh2, $eofPosn, 0) != $eofPosn );
202         $retValue = 2;
203         return $retValue if ( $verify == 2 );
204     }
205     return -110 if ( syswrite($fh2, $data2) != length($data2) );
206     if ( $verify ) {
207         #
208         # Make sure there is no extraneous data on the end of
209         # the file.  Seek to the end and truncate if it doesn't
210         # match our expected length.
211         #
212         return -111 if ( !defined(sysseek($fh2, 0, 2)) );
213         if ( sysseek($fh2, 0, 1) != $eofPosn + length($data2) ) {
214             if ( !truncate($fh2, $eofPosn + length($data2)) ) {
215                 &$Log(sprintf("digestAdd: $file truncate from %d to %d failed",
216                                 sysseek($fh2, 0, 1), $eofPosn + length($data2)));
217                 return -112;
218             } else {
219                 &$Log(sprintf("digestAdd: %s truncated from %d to %d",
220                                 $file,
221                                 sysseek($fh2, 0, 1), $eofPosn + length($data2)));
222             }
223         }
224     }
225     return -113 if ( !defined(sysseek($fh2, 0, 0)) );
226     return -114 if ( syswrite($fh2, chr(0xd7)) != 1 );
227     close($fh2);
228     return $retValue;
229 }
230
231 #
232 # Return rsync checksums for the given file.  We read the cached checksums
233 # if they exist and the block size and checksum seed match.  Otherwise
234 # we compute the checksums from the file contents.
235 #
236 # The doCache flag can take three ranges:
237 #
238 #  - doCache <  0: don't generate/use cached checksums
239 #  - doCache == 0: don't generate, but do use cached checksums if available
240 #  - doCache >  0: generate (if necessary) and use cached checksums
241 #
242 # Note: caching is only enabled when compression is on and the
243 # checksum seed is RSYNC_CSUMSEED_CACHE (32761).
244 #
245 # Returns 0 on success.  Returns a variety of negative values on error.
246 #
247 sub digestStart
248 {
249     my($class, $fileName, $fileSize, $blockSize, $defBlkSize,
250        $checksumSeed, $needMD4, $compress, $doCache, $protocol_version) = @_;
251
252     return -1 if ( !$RsyncLibOK );
253
254     my $data;
255
256     my $dg = bless {
257         name     => $fileName,
258         needMD4  => $needMD4,
259         digest   => File::RsyncP::Digest->new,
260         protocol_version => $protocol_version,
261     }, $class;
262
263     $dg->{digest}->protocol($dg->{protocol_version})
264                         if ( defined($dg->{protocol_version}) );
265
266     if ( $fileSize > 0 && $compress && $doCache >= 0 ) {
267         open(my $fh, "<", $fileName) || return -2;
268         binmode($fh);
269         return -3 if ( sysread($fh, $data, 4096) < 1 );
270         my $ret;
271
272         if ( (vec($data, 0, 8) == 0x78 || vec($data, 0, 8) == 0xd6) && $doCache > 0
273                      && $checksumSeed == RSYNC_CSUMSEED_CACHE ) {
274             #
275             # RSYNC_CSUMSEED_CACHE (32761) is the magic number that
276             # rsync uses for checksumSeed with the --fixed-csum option.
277             #
278             # We now add the cached checksum data to the file.  There
279             # is a possible race condition here since two BackupPC_dump
280             # processes might call this function at the same time
281             # on the same file.  But this should be ok since both
282             # processes will write the same data, and the order
283             # in which they write it doesn't matter.
284             #
285             close($fh);
286             $ret = $dg->digestAdd($fileName,
287                             $blockSize
288                                 || BackupPC::Xfer::RsyncDigest->blockSize(
289                                                     $fileSize, $defBlkSize),
290                                 $checksumSeed, 0, $dg->{protocol_version});
291             if ( $ret < 0 ) {
292                 &$Log("digestAdd($fileName) failed ($ret)");
293             }
294             #
295             # now re-open the file and re-read the first byte
296             #
297             open($fh, "<", $fileName) || return -4;
298             binmode($fh);
299             return -5 if ( read($fh, $data, 1) != 1 );
300         }
301         if ( $ret >= 0 && vec($data, 0, 8) == 0xd7 ) {
302             #
303             # Looks like this file has cached checksums
304             # Read the last 48 bytes: that's 2 file MD4s (32 bytes)
305             # plus 4 words of meta data
306             #
307             my $cacheInfo;
308             if ( length($data) >= 4096 ) {
309                 return -6 if ( !defined(sysseek($fh, -4096, 2)) ); 
310                 return -7 if ( sysread($fh, $data, 4096) != 4096 );
311             }
312             $cacheInfo = substr($data, -48);
313             ($dg->{md4DigestOld},
314              $dg->{md4Digest},
315              $dg->{blockSize},
316              $dg->{checksumSeed},
317              $dg->{nBlocks},
318              $dg->{magic}) = unpack("a16 a16 V V V V", $cacheInfo);
319             if ( $dg->{magic} == 0x5fe3c289
320                     && $dg->{checksumSeed} == $checksumSeed
321                     && ($blockSize == 0 || $dg->{blockSize} == $blockSize) ) {
322                 $dg->{fh}     = $fh;
323                 $dg->{cached} = 1;
324                 if ( length($data) >= $dg->{nBlocks} * 20 + 48 ) {
325                     #
326                     # We have all the data already - just remember it
327                     #
328                     $dg->{digestData} = substr($data,
329                                                length($data) - $dg->{nBlocks} * 20 - 48,
330                                                $dg->{nBlocks} * 20);
331                 } else {
332                     #
333                     # position the file at the start of the rsync block checksums
334                     # (4 (adler) + 16 (md4) bytes each)
335                     #
336                     return -8
337                         if ( !defined(sysseek($fh, -$dg->{nBlocks} * 20 - 48, 2)) );
338                 }
339             } else {
340                 #
341                 # cached checksums are not valid, so we close the
342                 # file and treat it as uncached.
343                 #
344                 $dg->{cachedInvalid} = 1;
345                 close($fh);
346             }
347         }
348     }
349     if ( !$dg->{cached} ) {
350         #
351         # This file doesn't have cached checksums, or the checksumSeed
352         # or blocksize doesn't match.  Open the file and prepare to
353         # compute the checksums.
354         #
355         $blockSize
356             = BackupPC::Xfer::RsyncDigest->blockSize($fileSize, $defBlkSize)
357                                     if ( $blockSize == 0 );
358         $dg->{checksumSeed} = $checksumSeed;
359         $dg->{blockSize}    = $blockSize;
360         $dg->{fh} = BackupPC::FileZIO->open($fileName, 0, $compress);
361         return -9 if ( !defined($dg->{fh}) );
362         if ( $needMD4) {
363             $dg->{csumDigest} = File::RsyncP::Digest->new;
364             $dg->{csumDigest}->protocol($dg->{protocol_version})
365                                 if ( defined($dg->{protocol_version}) );
366             $dg->{csumDigest}->add(pack("V", $dg->{checksumSeed}));
367         }
368     }
369     return (undef, $dg, $dg->{blockSize});
370 }
371
372 sub digestGet
373 {
374     my($dg, $num, $csumLen, $noPad) = @_;
375     my($fileData);
376     my $blockSize = $dg->{blockSize};
377
378     if ( $dg->{cached} ) {
379         my $thisNum = $num;
380         $thisNum = $dg->{nBlocks} if ( $thisNum > $dg->{nBlocks} );
381         if ( defined($dg->{digestData}) ) {
382             $fileData = substr($dg->{digestData}, 0, 20 * $thisNum);
383             $dg->{digestData} = substr($dg->{digestData}, 20 * $thisNum);
384         } else {
385             sysread($dg->{fh}, $fileData, 20 * $thisNum);
386         }
387         $dg->{nBlocks} -= $thisNum;
388         if ( $thisNum < $num && !$noPad) {
389             #
390             # unexpected shortfall of data; pad with zero digest
391             #
392             $fileData .= pack("c", 0) x (20 * ($num - $thisNum));
393         }
394         return $dg->{digest}->blockDigestExtract($fileData, $csumLen);
395     } else {
396         if ( $dg->{fh}->read(\$fileData, $blockSize * $num) <= 0 ) {
397             #
398             # unexpected shortfall of data; pad with zeros
399             #
400             $fileData = pack("c", 0) x ($blockSize * $num) if ( !$noPad );
401         }
402         $dg->{csumDigest}->add($fileData) if ( $dg->{needMD4} );
403         return $dg->{digest}->blockDigest($fileData, $blockSize,
404                                            $csumLen, $dg->{checksumSeed});
405     }
406 }
407
408 sub digestEnd
409 {
410     my($dg, $skipMD4) = @_;
411     my($fileData);
412
413     if ( $dg->{cached} ) {
414         close($dg->{fh});
415         if ( $dg->{needMD4} ) {
416             if ( $dg->{protocol_version} <= 26 ) {
417                 return $dg->{md4DigestOld};
418             } else {
419                 return $dg->{md4Digest};
420             }
421         }
422     } else {
423         #
424         # make sure we read the entire file for the file MD4 digest
425         #
426         if ( $dg->{needMD4} && !$skipMD4 ) {
427             my $fileData;
428             while ( $dg->{fh}->read(\$fileData, 65536) > 0 ) {
429                 $dg->{csumDigest}->add($fileData);
430             }
431         }
432         $dg->{fh}->close();
433         return $dg->{csumDigest}->digest if ( $dg->{needMD4} );
434     }
435 }
436
437 sub isCached
438 {
439     my($dg) = @_;
440  
441     return wantarray ? ($dg->{cached}, $dg->{cachedInvalid}) : $dg->{cached};
442 }
443
444 sub blockSizeCurr
445 {
446     my($dg) = @_;
447  
448     return $dg->{blockSize};
449 }
450
451 #
452 # Default log handler
453 #
454 sub logHandler
455 {
456     my($str) = @_;
457
458     print(STDERR $str, "\n");
459 }
460
461 #
462 # Set log handler to a new subroutine.
463 #
464 sub logHandlerSet
465 {
466     my($dg, $sub) = @_;
467
468     $Log = $sub;
469 }
470
471 1;