lib/BackupPC/RsyncDigest.pm

   1 #============================================================= -*-perl-*-
   2 #
   3 # BackupPC::RsyncDigest package
   4 #
   5 # DESCRIPTION
   6 #
   7 #   This library defines a BackupPC::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 2.1.0_CVS, released 3 Jul 2003.
  33 #
  34 # See http://backuppc.sourceforge.net.
  35 #
  36 #========================================================================
  37
  38 package BackupPC::RsyncDigest;
  39
  40 use strict;
  41
  42 use vars qw( $RsyncLibOK );
  43 use Carp;
  44
  45 BEGIN {
  46     eval "use File::RsyncP;";
  47     if ( $@ ) {
  48         #
  49         # File::RsyncP doesn't exist.  Define some dummy constant
  50         # subs so that the code below doesn't barf.
  51         #
  52         $RsyncLibOK = 0;
  53     } else {
  54         $RsyncLibOK = 1;
  55     }
  56 };
  57
  58 #
  59 # Return the rsync block size based on the file size.
  60 # We also make sure the block size plus 4 (ie: cheeksumSeed)
  61 # is not a multiple of 64 - otherwise the cached checksums
  62 # will not be the same for protocol versions <= 26 and > 26.
  63 #
  64 sub blockSize
  65 {
  66     my($class, $fileSize, $defaultBlkSize) = @_;
  67
  68     my $blkSize = int($fileSize / 10000);
  69     $blkSize = $defaultBlkSize if ( $blkSize < $defaultBlkSize );
  70     $blkSize = 16384 if ( $blkSize > 16384 );
  71     $blkSize += 4 if ( (($blkSize + 4) % 64) == 0 );
  72     return $blkSize;
  73 }
  74
  75 #
  76 # Compute and add rsync block and file digests to the given file.
  77 #
  78 sub digestAdd
  79 {
  80     my($class, $file, $blockSize, $checksumSeed) = @_;
  81     if ( $blockSize == 0 ) {
  82         print("bogus digestAdd($file, $blockSize, $checksumSeed)\n");
  83         $blockSize = 2048;
  84     }
  85     my $nBlks = int(65536 * 16 / $blockSize) + 1;
  86     my($data, $blockDigest, $fileDigest);
  87
  88     return if ( !$RsyncLibOK );
  89
  90     my $digest = File::RsyncP::Digest->new;
  91     $digest->add(pack("V", $checksumSeed)) if ( $checksumSeed );
  92
  93     return -1 if ( !defined(my $fh = BackupPC::FileZIO->open($file, 0, 1)) );
  94     while ( 1 ) {
  95         $fh->read(\$data, $nBlks * $blockSize);
  96         last if ( $data eq "" );
  97         $blockDigest .= $digest->blockDigest($data, $blockSize, 16,
  98                                              $checksumSeed);
  99         $digest->add($data);
 100     }
 101     $fileDigest = $digest->digest2;
 102     my $eofPosn = tell($fh->{fh});
 103     $fh->close;
 104     my $rsyncData = $blockDigest . $fileDigest;
 105     my $metaData  = pack("VVVV", $blockSize,
 106                                  $checksumSeed,
 107                                  length($blockDigest) / 20,
 108                                  0x5fe3c289,                # magic number
 109                         );
 110     my $data2 = chr(0xb3) . $rsyncData . $metaData;
 111 #    printf("appending %d+%d bytes to %s at offset %d\n",
 112 #                                            length($rsyncData),
 113 #                                            length($metaData),
 114 #                                            $file,
 115 #                                            $eofPosn);
 116     open(my $fh2, "+<", $file) || return -2;
 117     binmode($fh2);
 118     return -3 if ( sysread($fh2, $data, 1) != 1 );
 119     if ( $data ne chr(0x78) && $data ne chr(0xd6) ) {
 120         printf("Unexpected first char 0x%x\n", ord($data));
 121         return -4;
 122     }
 123     return -5 if ( sysseek($fh2, $eofPosn, 0) != $eofPosn );
 124     return -6 if ( syswrite($fh2, $data2) != length($data2) );
 125     return -7 if ( !defined(sysseek($fh2, 0, 0)) );
 126     return -8 if ( syswrite($fh2, chr(0xd6)) != 1 );
 127     close($fh2);
 128 }
 129
 130 #
 131 # Return rsync checksums for the given file.  We read the cached checksums
 132 # if they exist and the block size and checksum seed match.  Otherwise
 133 # we compute the checksums from the file contents.
 134 #
 135 sub digestStart
 136 {
 137     my($class, $fileName, $fileSize, $blockSize, $defBlkSize,
 138        $checksumSeed, $needMD4, $compress, $doCache) = @_;
 139
 140     return -1 if ( !$RsyncLibOK );
 141
 142     my $data;
 143
 144     my $fio = bless {
 145         name     => $fileName,
 146         needMD4  => $needMD4,
 147         digest   => File::RsyncP::Digest->new,
 148     }, $class;
 149
 150     if ( $fileSize > 0 && $compress ) {
 151         open(my $fh, "<", $fileName) || return -2;
 152         binmode($fh);
 153         return -3 if ( read($fh, $data, 1) != 1 );
 154         if ( $data eq chr(0x78) && $doCache && $checksumSeed == 32761 ) {
 155             #
 156             # 32761 is the magic number that rsync uses for checksumSeed
 157             # with the --fixed-csum option.
 158             #
 159             # We now add the cached checksum data to the file.  There
 160             # is a possible race condition here since two BackupPC_dump
 161             # processes might call this function at the same time
 162             # on the same file.  But this should be ok since both
 163             # processes will write the same data, and the order
 164             # in which they write it doesn't matter.
 165             #
 166             close($fh);
 167             $fio->digestAdd($fileName,
 168                     $blockSize || $fio->blockSize($fileSize, $defBlkSize),
 169                     $checksumSeed);
 170             #
 171             # now re-open the file and re-read the first byte
 172             #
 173             open($fh, "<", $fileName) || return -2;
 174             binmode($fh);
 175             return -3 if ( read($fh, $data, 1) != 1 );
 176         }
 177         if ( $data eq chr(0xd6) ) {
 178             #
 179             # Looks like this file has cached checksums
 180             # Read the last 48 bytes: that's 2 file MD4s (32 bytes)
 181             # plus 4 words of meta data
 182             #
 183             return -4 if ( !defined(seek($fh, -48, 2)) );
 184             return -5 if ( read($fh, $data, 48) != 48 );
 185             ($fio->{md4DigestOld},
 186              $fio->{md4Digest},
 187              $fio->{blockSize},
 188              $fio->{checksumSeed},
 189              $fio->{nBlocks},
 190              $fio->{magic}) = unpack("a16 a16 V V V V", $data);
 191             if ( $fio->{magic} == 0x5fe3c289
 192                     && $fio->{checksumSeed} == $checksumSeed
 193                     && ($blockSize == 0 || $fio->{blockSize} == $blockSize) ) {
 194                 $fio->{fh}     = $fh;
 195                 $fio->{cached} = 1;
 196             } else {
 197                 close($fh);
 198             }
 199             #
 200             # position the file at the start of the rsync block checksums
 201             # (4 (adler) + 16 (md4) bytes each)
 202             #
 203             return -6 if ( !defined(seek($fh, -$fio->{nBlocks}*20 - 48, 2)) );
 204         }
 205     }
 206     if ( !$fio->{cached} ) {
 207         #
 208         # This file doesn't have cached checksums, or the checksumSeed
 209         # or blocksize doesn't match.  Open the file and prepare to
 210         # compute the checksums.
 211         #
 212         $blockSize = BackupPC::RsyncDigest->blockSize($fileSize, $defBlkSize)
 213                                         if ( $blockSize == 0 );
 214         $fio->{checksumSeed} = $checksumSeed;
 215         $fio->{blockSize}    = $blockSize;
 216         $fio->{fh} = BackupPC::FileZIO->open($fileName, 0, $compress);
 217         return -7 if ( !defined($fio->{fh}) );
 218         if ( $needMD4) {
 219             $fio->{csumDigest} = File::RsyncP::Digest->new;
 220             $fio->{csumDigest}->add(pack("V", $fio->{checksumSeed}));
 221         }
 222     }
 223     return (undef, $fio, $fio->{blockSize});
 224 }
 225
 226 sub digestGet
 227 {
 228     my($fio, $num, $csumLen) = @_;
 229     my($fileData);
 230     my $blockSize = $fio->{blockSize};
 231
 232     if ( $fio->{cached} ) {
 233         my $thisNum = $num;
 234         $thisNum = $fio->{nBlocks} if ( $thisNum > $fio->{nBlocks} );
 235         read($fio->{fh}, $fileData, 20 * $thisNum);
 236         $fio->{nBlocks} -= $thisNum;
 237         if ( $thisNum < $num ) {
 238             #
 239             # unexpected shortfall of data; pad with zero digest
 240             #
 241             $fileData .= pack("c", 0) x (20 * ($num - $thisNum));
 242         }
 243         return $fio->{digest}->blockDigestExtract($fileData, $csumLen);
 244     } else {
 245         if ( $fio->{fh}->read(\$fileData, $blockSize * $num) <= 0 ) {
 246             #
 247             # unexpected shortfall of data; pad with zeros
 248             #
 249             $fileData = pack("c", 0) x ($blockSize * $num);
 250         }
 251         $fio->{csumDigest}->add($fileData) if ( $fio->{needMD4} );
 252         return $fio->{digest}->blockDigest($fileData, $blockSize,
 253                                            $csumLen, $fio->{checksumSeed});
 254     }
 255 }
 256
 257 sub digestEnd
 258 {
 259     my($fio) = @_;
 260     my($fileData);
 261
 262     if ( $fio->{cached} ) {
 263         close($fio->{fh});
 264         return $fio->{md4DigestOld} if ( $fio->{needMD4} );
 265     } else {
 266         #
 267         # make sure we read the entire file for the file MD4 digest
 268         #
 269         if ( $fio->{needMD4} ) {
 270             my $fileData;
 271             while ( $fio->{fh}->read(\$fileData, 65536) > 0 ) {
 272                 $fio->{csumDigest}->add($fileData);
 273             }
 274         }
 275         $fio->{fh}->close();
 276         return $fio->{csumDigest}->digest if ( $fio->{needMD4} );
 277     }
 278 }
 279
 280 1;