lib/BackupPC/PoolWrite.pm

   1 #============================================================= -*-perl-*-
   2 #
   3 # BackupPC::PoolWrite package
   4 #
   5 # DESCRIPTION
   6 #
   7 #   This library defines a BackupPC::PoolWrite class for writing
   8 #   files to disk that are candidates for pooling.  One instance
   9 #   of this class is used to write each file.  The following steps
  10 #   are executed:
  11 #
  12 #     - As the incoming data arrives, the first 1MB is buffered
  13 #       in memory so the MD5 digest can be computed.
  14 #
  15 #     - A running comparison against all the candidate pool files
  16 #       (ie: those with the same MD5 digest, usually at most a single
  17 #       file) is done as new incoming data arrives.  Up to $MaxFiles
  18 #       simultaneous files can be compared in parallel.  This
  19 #       involves reading and uncompressing one or more pool files.
  20 #
  21 #     - When a pool file no longer matches it is discarded from
  22 #       the search.  If there are more than $MaxFiles candidates, one of
  23 #       the new candidates is added to the search, first checking
  24 #       that it matches up to the current point (this requires
  25 #       re-reading one of the other pool files).
  26 #
  27 #     - When or if no pool files match then the new file is written
  28 #       to disk.  This could occur many MB into the file.  We don't
  29 #       need to buffer all this data in memory since we can copy it
  30 #       from the last matching pool file, up to the point where it
  31 #       fully matched.
  32 #
  33 #     - When all the new data is complete, if a pool file exactly
  34 #       matches then the file is simply created as a hardlink to
  35 #       the pool file.
  36 #
  37 # AUTHOR
  38 #   Craig Barratt  <cbarratt@users.sourceforge.net>
  39 #
  40 # COPYRIGHT
  41 #   Copyright (C) 2001  Craig Barratt
  42 #
  43 #   This program is free software; you can redistribute it and/or modify
  44 #   it under the terms of the GNU General Public License as published by
  45 #   the Free Software Foundation; either version 2 of the License, or
  46 #   (at your option) any later version.
  47 #
  48 #   This program is distributed in the hope that it will be useful,
  49 #   but WITHOUT ANY WARRANTY; without even the implied warranty of
  50 #   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  51 #   GNU General Public License for more details.
  52 #
  53 #   You should have received a copy of the GNU General Public License
  54 #   along with this program; if not, write to the Free Software
  55 #   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  56 #
  57 #========================================================================
  58 #
  59 # Version 2.0.0_CVS, released 3 Feb 2003.
  60 #
  61 # See http://backuppc.sourceforge.net.
  62 #
  63 #========================================================================
  64
  65 package BackupPC::PoolWrite;
  66
  67 use strict;
  68
  69 use File::Path;
  70 use Digest::MD5;
  71 use BackupPC::FileZIO;
  72
  73 sub new
  74 {
  75     my($class, $bpc, $fileName, $fileSize, $compress) = @_;
  76
  77     my $self = bless {
  78         fileName => $fileName,
  79         fileSize => $fileSize,
  80         bpc      => $bpc,
  81         compress => $compress,
  82         nWrite   => 0,
  83         digest   => undef,
  84         files    => [],
  85         fileCnt  => -1,
  86         fhOut    => undef,
  87         errors   => [],
  88         data     => "",
  89         eof      => undef,
  90     }, $class;
  91
  92     $self->{hardLinkMax} = $bpc->ConfValue("HardLinkMax");
  93
  94     #
  95     # Always unlink any current file in case it is already linked
  96     #
  97     unlink($fileName) if ( -f $fileName );
  98     return $self;
  99 }
 100
 101 my $BufSize  = 1048576;     # 1MB or 2^20
 102 my $MaxFiles = 20;
 103
 104 sub write
 105 {
 106     my($a, $dataRef) = @_;
 107
 108     return if ( $a->{eof} );
 109     $a->{data} .= $$dataRef if ( defined($dataRef) );
 110     return if ( length($a->{data}) < $BufSize && defined($dataRef) );
 111     if ( !defined($a->{digest}) && $a->{fileSize} > 0 ) {
 112         #
 113         # build a list of all the candidate matching files
 114         #
 115         my $md5 = Digest::MD5->new;
 116         $a->{digest} = $a->{bpc}->Buffer2MD5($md5, $a->{fileSize}, \$a->{data});
 117         if ( !defined($a->{base} = $a->{bpc}->MD52Path($a->{digest},
 118                                                        $a->{compress})) ) {
 119             push(@{$a->{errors}}, "Unable to get path from '$a->{digest}'"
 120                                 . " for $a->{fileName}\n");
 121         } else {
 122             while ( @{$a->{files}} < $MaxFiles ) {
 123                 my $fh;
 124                 my $fileName = $a->{fileCnt} < 0 ? $a->{base}
 125                                         : "$a->{base}_$a->{fileCnt}";
 126                 last if ( !-f $fileName );
 127                 if ( (stat(_))[3] >= $a->{hardLinkMax}
 128                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
 129                                                      $a->{compress})) ) {
 130                     $a->{fileCnt}++;
 131                     next;
 132                 }
 133                 push(@{$a->{files}}, {
 134                         name => $fileName,
 135                         fh   => $fh,
 136                      });
 137                 $a->{fileCnt}++;
 138             }
 139         }
 140         #
 141         # if there are no candidate files then we must write
 142         # the new file to disk
 143         #
 144         if ( !@{$a->{files}} ) {
 145             $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
 146                                               1, $a->{compress});
 147             if ( !defined($a->{fhOut}) ) {
 148                 push(@{$a->{errors}}, "Unable to open $a->{fileName}"
 149                                     . " for writing\n");
 150             }
 151         }
 152     }
 153     my $dataLen = length($a->{data});
 154     if ( !defined($a->{fhOut}) && $a->{fileSize} > 0 ) {
 155         #
 156         # See if the new chunk of data continues to match the
 157         # candidate files.
 158         #
 159         for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
 160             my($d, $match);
 161             my $fileName = $a->{fileCnt} < 0 ? $a->{base}
 162                                              : "$a->{base}_$a->{fileCnt}";
 163             if ( $dataLen > 0 ) {
 164                 # verify next $dataLen bytes from candidate file
 165                 my $n = $a->{files}[$i]->{fh}->read(\$d, $dataLen);
 166                 next if ( $n == $dataLen && $d eq $a->{data} );
 167             } else {
 168                 # verify candidate file is at EOF
 169                 my $n = $a->{files}[$i]->{fh}->read(\$d, 100);
 170                 next if ( $n == 0 );
 171             }
 172             #print("   File $a->{files}[$i]->{name} doesn't match\n");
 173             #
 174             # this candidate file didn't match.  Replace it
 175             # with a new candidate file.  We have to qualify
 176             # any new candidate file by making sure that its
 177             # first $a->{nWrite} bytes match, plus the next $dataLen
 178             # bytes match $a->{data}.
 179             #
 180             while ( -f $fileName ) {
 181                 my $fh;
 182                 if ( (stat(_))[3] >= $a->{hardLinkMax}
 183                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
 184                                                      $a->{compress})) ) {
 185                     $a->{fileCnt}++;
 186                     #print("   Discarding $fileName (open failed)\n");
 187                     $fileName = "$a->{base}_$a->{fileCnt}";
 188                     next;
 189                 }
 190                 if ( !$a->{files}[$i]->{fh}->rewind() ) {
 191                     push(@{$a->{errors}},
 192                             "Unable to rewind $a->{files}[$i]->{name}"
 193                           . " for compare\n");
 194                 }
 195                 $match = $a->filePartialCompare($a->{files}[$i]->{fh}, $fh,
 196                                           $a->{nWrite}, $dataLen, \$a->{data});
 197                 if ( $match ) {
 198                     $a->{files}[$i]->{fh}->close();
 199                     $a->{files}[$i]->{fh} = $fh,
 200                     $a->{files}[$i]->{name} = $fileName;
 201                     #print("   Found new candidate $fileName\n");
 202                     $a->{fileCnt}++;
 203                     last;
 204                 } else {
 205                     #print("   Discarding $fileName (no match)\n");
 206                 }
 207                 $fh->close();
 208                 $a->{fileCnt}++;
 209                 $fileName = "$a->{base}_$a->{fileCnt}";
 210             }
 211             if ( !$match ) {
 212                 #
 213                 # We couldn't find another candidate file
 214                 #
 215                 if ( @{$a->{files}} == 1 ) {
 216                     #print("   Exhausted matches, now writing\n");
 217                     $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
 218                                                     1, $a->{compress});
 219                     if ( !defined($a->{fhOut}) ) {
 220                         push(@{$a->{errors}},
 221                                 "Unable to open $a->{fileName}"
 222                               . " for writing\n");
 223                     } else {
 224                         if ( !$a->{files}[$i]->{fh}->rewind() ) {
 225                             push(@{$a->{errors}},
 226                                      "Unable to rewind"
 227                                    . " $a->{files}[$i]->{name} for copy\n");
 228                         }
 229                         $a->filePartialCopy($a->{files}[$i]->{fh}, $a->{fhOut},
 230                                         $a->{nWrite});
 231                     }
 232                 }
 233                 $a->{files}[$i]->{fh}->close();
 234                 splice(@{$a->{files}}, $i, 1);
 235                 $i--;
 236             }
 237         }
 238     }
 239     if ( defined($a->{fhOut}) && $dataLen > 0 ) {
 240         #
 241         # if we are in writing mode then just write the data
 242         #
 243         my $n = $a->{fhOut}->write(\$a->{data});
 244         if ( $n != $dataLen ) {
 245             push(@{$a->{errors}}, "Unable to write $dataLen bytes to"
 246                                 . " $a->{fileName} (got $n)\n");
 247         }
 248     }
 249     $a->{nWrite} += $dataLen;
 250     $a->{data} = "";
 251     return if ( defined($dataRef) );
 252
 253     #
 254     # We are at EOF, so finish up
 255     #
 256     $a->{eof} = 1;
 257     foreach my $f ( @{$a->{files}} ) {
 258         $f->{fh}->close();
 259     }
 260     if ( $a->{fileSize} == 0 ) {
 261         #
 262         # Simply create an empty file
 263         #
 264         local(*OUT);
 265         if ( !open(OUT, ">", $a->{fileName}) ) {
 266             push(@{$a->{errors}}, "Can't open $a->{fileName} for empty"
 267                                 . " output\n");
 268         } else {
 269             close(OUT);
 270         }
 271         return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
 272     } elsif ( defined($a->{fhOut}) ) {
 273         $a->{fhOut}->close();
 274         return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
 275     } else {
 276         if ( @{$a->{files}} == 0 ) {
 277             push(@{$a->{errors}}, "Botch, no matches on $a->{fileName}"
 278                                 . " ($a->{digest})\n");
 279         } elsif ( @{$a->{files}} > 1 ) {
 280             #
 281             # This is no longer a real error because $Conf{HardLinkMax}
 282             # could be hit, thereby creating identical pool files
 283             #
 284             #my $str = "Unexpected multiple matches on"
 285             #       . " $a->{fileName} ($a->{digest})\n";
 286             #for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
 287             #    $str .= "     -> $a->{files}[$i]->{name}\n";
 288             #}
 289             #push(@{$a->{errors}}, $str);
 290         }
 291         #print("   Linking $a->{fileName} to $a->{files}[0]->{name}\n");
 292         if ( @{$a->{files}} && !link($a->{files}[0]->{name}, $a->{fileName}) ) {
 293             push(@{$a->{errors}}, "Can't link $a->{fileName} to"
 294                                 . " $a->{files}[0]->{name}\n");
 295         }
 296         return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
 297     }
 298 }
 299
 300 #
 301 # Finish writing: pass undef dataRef to write so it can do all
 302 # the work.  Returns a 4 element array:
 303 #
 304 #   (existingFlag, digestString, outputFileLength, errorList)
 305 #
 306 sub close
 307 {
 308     my($a) = @_;
 309
 310     return $a->write(undef);
 311 }
 312
 313 #
 314 # Copy $nBytes from files $fhIn to $fhOut.
 315 #
 316 sub filePartialCopy
 317 {
 318     my($a, $fhIn, $fhOut, $nBytes) = @_;
 319     my($nRead);
 320
 321     while ( $nRead < $nBytes ) {
 322         my $thisRead = $nBytes - $nRead < $BufSize
 323                             ? $nBytes - $nRead : $BufSize;
 324         my $data;
 325         my $n = $fhIn->read(\$data, $thisRead);
 326         if ( $n != $thisRead ) {
 327             push(@{$a->{errors}},
 328                         "Unable to read $thisRead bytes from "
 329                        . $fhIn->name . " (got $n)\n");
 330             return;
 331         }
 332         $n = $fhOut->write(\$data, $thisRead);
 333         if ( $n != $thisRead ) {
 334             push(@{$a->{errors}},
 335                         "Unable to write $thisRead bytes to "
 336                        . $fhOut->name . " (got $n)\n");
 337             return;
 338         }
 339         $nRead += $thisRead;
 340     }
 341 }
 342
 343 #
 344 # Compare $nBytes from files $fh0 and $fh1, and also compare additional
 345 # $extra bytes from $fh1 to $$extraData.
 346 #
 347 sub filePartialCompare
 348 {
 349     my($a, $fh0, $fh1, $nBytes, $extra, $extraData) = @_;
 350     my($nRead, $n);
 351     my($data0, $data1);
 352
 353     while ( $nRead < $nBytes ) {
 354         my $thisRead = $nBytes - $nRead < $BufSize
 355                             ? $nBytes - $nRead : $BufSize;
 356         $n = $fh0->read(\$data0, $thisRead);
 357         if ( $n != $thisRead ) {
 358             push(@{$a->{errors}}, "Unable to read $thisRead bytes from "
 359                                  . $fh0->name . " (got $n)\n");
 360             return;
 361         }
 362         $n = $fh1->read(\$data1, $thisRead);
 363         return 0 if ( $n < $thisRead || $data0 ne $data1 );
 364         $nRead += $thisRead;
 365     }
 366     if ( $extra > 0 ) {
 367         # verify additional bytes
 368         $n = $fh1->read(\$data1, $extra);
 369         return 0 if ( $n != $extra || $data1 ne $$extraData );
 370     } else {
 371         # verify EOF
 372         $n = $fh1->read(\$data1, 100);
 373         return 0 if ( $n != 0 );
 374     }
 375     return 1;
 376 }
 377
 378 1;