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-2003  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.0.0beta3, released 3 Dec 2006.
  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 ( read($fh, $data, 1) != 1 );
 270         my $ret;
 271
 272         if ( ($data eq chr(0x78) || $data eq chr(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 && $data eq chr(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             return -6 if ( !defined(seek($fh, -48, 2)) );
 308             return -7 if ( read($fh, $data, 48) != 48 );
 309             ($dg->{md4DigestOld},
 310              $dg->{md4Digest},
 311              $dg->{blockSize},
 312              $dg->{checksumSeed},
 313              $dg->{nBlocks},
 314              $dg->{magic}) = unpack("a16 a16 V V V V", $data);
 315             if ( $dg->{magic} == 0x5fe3c289
 316                     && $dg->{checksumSeed} == $checksumSeed
 317                     && ($blockSize == 0 || $dg->{blockSize} == $blockSize) ) {
 318                 $dg->{fh}     = $fh;
 319                 $dg->{cached} = 1;
 320                 #
 321                 # position the file at the start of the rsync block checksums
 322                 # (4 (adler) + 16 (md4) bytes each)
 323                 #
 324                 return -8
 325                     if ( !defined(seek($fh, -$dg->{nBlocks}*20 - 48, 2)) );
 326             } else {
 327                 #
 328                 # cached checksums are not valid, so we close the
 329                 # file and treat it as uncached.
 330                 #
 331                 $dg->{cachedInvalid} = 1;
 332                 close($fh);
 333             }
 334         }
 335     }
 336     if ( !$dg->{cached} ) {
 337         #
 338         # This file doesn't have cached checksums, or the checksumSeed
 339         # or blocksize doesn't match.  Open the file and prepare to
 340         # compute the checksums.
 341         #
 342         $blockSize
 343             = BackupPC::Xfer::RsyncDigest->blockSize($fileSize, $defBlkSize)
 344                                     if ( $blockSize == 0 );
 345         $dg->{checksumSeed} = $checksumSeed;
 346         $dg->{blockSize}    = $blockSize;
 347         $dg->{fh} = BackupPC::FileZIO->open($fileName, 0, $compress);
 348         return -9 if ( !defined($dg->{fh}) );
 349         if ( $needMD4) {
 350             $dg->{csumDigest} = File::RsyncP::Digest->new;
 351             $dg->{csumDigest}->protocol($dg->{protocol_version})
 352                                 if ( defined($dg->{protocol_version}) );
 353             $dg->{csumDigest}->add(pack("V", $dg->{checksumSeed}));
 354         }
 355     }
 356     return (undef, $dg, $dg->{blockSize});
 357 }
 358
 359 sub digestGet
 360 {
 361     my($dg, $num, $csumLen, $noPad) = @_;
 362     my($fileData);
 363     my $blockSize = $dg->{blockSize};
 364
 365     if ( $dg->{cached} ) {
 366         my $thisNum = $num;
 367         $thisNum = $dg->{nBlocks} if ( $thisNum > $dg->{nBlocks} );
 368         read($dg->{fh}, $fileData, 20 * $thisNum);
 369         $dg->{nBlocks} -= $thisNum;
 370         if ( $thisNum < $num && !$noPad) {
 371             #
 372             # unexpected shortfall of data; pad with zero digest
 373             #
 374             $fileData .= pack("c", 0) x (20 * ($num - $thisNum));
 375         }
 376         return $dg->{digest}->blockDigestExtract($fileData, $csumLen);
 377     } else {
 378         if ( $dg->{fh}->read(\$fileData, $blockSize * $num) <= 0 ) {
 379             #
 380             # unexpected shortfall of data; pad with zeros
 381             #
 382             $fileData = pack("c", 0) x ($blockSize * $num) if ( !$noPad );
 383         }
 384         $dg->{csumDigest}->add($fileData) if ( $dg->{needMD4} );
 385         return $dg->{digest}->blockDigest($fileData, $blockSize,
 386                                            $csumLen, $dg->{checksumSeed});
 387     }
 388 }
 389
 390 sub digestEnd
 391 {
 392     my($dg, $skipMD4) = @_;
 393     my($fileData);
 394
 395     if ( $dg->{cached} ) {
 396         close($dg->{fh});
 397         if ( $dg->{needMD4} ) {
 398             if ( $dg->{protocol_version} <= 26 ) {
 399                 return $dg->{md4DigestOld};
 400             } else {
 401                 return $dg->{md4Digest};
 402             }
 403         }
 404     } else {
 405         #
 406         # make sure we read the entire file for the file MD4 digest
 407         #
 408         if ( $dg->{needMD4} && !$skipMD4 ) {
 409             my $fileData;
 410             while ( $dg->{fh}->read(\$fileData, 65536) > 0 ) {
 411                 $dg->{csumDigest}->add($fileData);
 412             }
 413         }
 414         $dg->{fh}->close();
 415         return $dg->{csumDigest}->digest if ( $dg->{needMD4} );
 416     }
 417 }
 418
 419 sub isCached
 420 {
 421     my($dg) = @_;
 422
 423     return wantarray ? ($dg->{cached}, $dg->{cachedInvalid}) : $dg->{cached};
 424 }
 425
 426 sub blockSizeCurr
 427 {
 428     my($dg) = @_;
 429
 430     return $dg->{blockSize};
 431 }
 432
 433 #
 434 # Default log handler
 435 #
 436 sub logHandler
 437 {
 438     my($str) = @_;
 439
 440     print(STDERR $str, "\n");
 441 }
 442
 443 #
 444 # Set log handler to a new subroutine.
 445 #
 446 sub logHandlerSet
 447 {
 448     my($dg, $sub) = @_;
 449
 450     $Log = $sub;
 451 }
 452
 453 1;