* Changes in preparation for 3.2.0beta1...
[BackupPC.git] / 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-2009  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 3.2.0beta0, released 5 April 2009.
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     if ( $fileName =~ m{(.*)/.+} && !-d $1 ) {
99         my $newDir = $1;
100         eval { mkpath($newDir, 0, 0777) };
101         if ( $@ ) {
102             push(@{$self->{errors}}, "Unable to create directory $newDir for $self->{fileName}");
103         }
104     }
105     return $self;
106 }
107
108 my $BufSize  = 1048576;  # 1MB or 2^20
109 my $MaxFiles = 20;       # max number of compare files open at one time
110
111 sub write
112 {
113     my($a, $dataRef) = @_;
114
115     return if ( $a->{eof} );
116     $a->{data} .= $$dataRef if ( defined($dataRef) );
117     return if ( length($a->{data}) < $BufSize && defined($dataRef) );
118
119     #
120     # Correct the fileSize if it is wrong (rsync might transfer
121     # a file whose length is different to the length sent with the
122     # file list if the file changes between the file list sending
123     # and the file sending).  Here we only catch the case where
124     # we haven't computed the digest (ie: we have written no more
125     # than $BufSize).  We catch the big file case below.
126     #
127     if ( !defined($dataRef) && !defined($a->{digest})
128                 && $a->{fileSize} != length($a->{data}) ) {
129         #my $newSize = length($a->{data});
130         #print("Fixing file size from $a->{fileSize} to $newSize\n");
131         $a->{fileSize} = length($a->{data});
132     }
133
134     if ( !defined($a->{digest}) && length($a->{data}) > 0 ) {
135         #
136         # build a list of all the candidate matching files
137         #
138         my $md5 = Digest::MD5->new;
139         $a->{fileSize} = length($a->{data})
140                             if ( $a->{fileSize} < length($a->{data}) );
141         $a->{digest} = $a->{bpc}->Buffer2MD5($md5, $a->{fileSize}, \$a->{data});
142         if ( !defined($a->{base} = $a->{bpc}->MD52Path($a->{digest},
143                                                        $a->{compress})) ) {
144             push(@{$a->{errors}}, "Unable to get path from '$a->{digest}'"
145                                 . " for $a->{fileName}");
146         } else {
147             while ( @{$a->{files}} < $MaxFiles ) {
148                 my $fh;
149                 my $fileName = $a->{fileCnt} < 0 ? $a->{base}
150                                         : "$a->{base}_$a->{fileCnt}";
151                 last if ( !-f $fileName );
152                 #
153                 # Don't attempt to match pool files that already
154                 # have too many hardlinks.  Also, don't match pool
155                 # files with only one link since starting in
156                 # BackupPC v3.0, BackupPC_nightly could be running
157                 # in parallel (and removing those files).  This doesn't
158                 # eliminate all possible race conditions, but just
159                 # reduces the odds.  Other design steps eliminate
160                 # the remaining race conditions of linking vs
161                 # removing.
162                 #
163                 if ( (stat(_))[3] >= $a->{hardLinkMax}
164                     || (stat(_))[3] <= 1
165                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
166                                                      $a->{compress})) ) {
167                     $a->{fileCnt}++;
168                     next;
169                 }
170                 push(@{$a->{files}}, {
171                         name => $fileName,
172                         fh   => $fh,
173                      });
174                 $a->{fileCnt}++;
175             }
176         }
177         #
178         # if there are no candidate files then we must write
179         # the new file to disk
180         #
181         if ( !@{$a->{files}} ) {
182             $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
183                                               1, $a->{compress});
184             if ( !defined($a->{fhOut}) ) {
185                 push(@{$a->{errors}}, "Unable to open $a->{fileName}"
186                                     . " for writing");
187             }
188         }
189     }
190     my $dataLen = length($a->{data});
191     if ( !defined($a->{fhOut}) && length($a->{data}) > 0 ) {
192         #
193         # See if the new chunk of data continues to match the
194         # candidate files.
195         #
196         for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
197             my($d, $match);
198             my $fileName = $a->{fileCnt} < 0 ? $a->{base}
199                                              : "$a->{base}_$a->{fileCnt}";
200             if ( $dataLen > 0 ) {
201                 # verify next $dataLen bytes from candidate file
202                 my $n = $a->{files}[$i]->{fh}->read(\$d, $dataLen);
203                 next if ( $n == $dataLen && $d eq $a->{data} );
204             } else {
205                 # verify candidate file is at EOF
206                 my $n = $a->{files}[$i]->{fh}->read(\$d, 100);
207                 next if ( $n == 0 );
208             }
209             #print("   File $a->{files}[$i]->{name} doesn't match\n");
210             #
211             # this candidate file didn't match.  Replace it
212             # with a new candidate file.  We have to qualify
213             # any new candidate file by making sure that its
214             # first $a->{nWrite} bytes match, plus the next $dataLen
215             # bytes match $a->{data}.
216             #
217             while ( -f $fileName ) {
218                 my $fh;
219                 if ( (stat(_))[3] >= $a->{hardLinkMax}
220                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
221                                                      $a->{compress})) ) {
222                     $a->{fileCnt}++;
223                     #print("   Discarding $fileName (open failed)\n");
224                     $fileName = "$a->{base}_$a->{fileCnt}";
225                     next;
226                 }
227                 if ( !$a->{files}[$i]->{fh}->rewind() ) {
228                     push(@{$a->{errors}},
229                             "Unable to rewind $a->{files}[$i]->{name}"
230                           . " for compare");
231                 }
232                 $match = $a->filePartialCompare($a->{files}[$i]->{fh}, $fh,
233                                           $a->{nWrite}, $dataLen, \$a->{data});
234                 if ( $match ) {
235                     $a->{files}[$i]->{fh}->close();
236                     $a->{files}[$i]->{fh} = $fh,
237                     $a->{files}[$i]->{name} = $fileName;
238                     #print("   Found new candidate $fileName\n");
239                     $a->{fileCnt}++;
240                     last;
241                 } else {
242                     #print("   Discarding $fileName (no match)\n");
243                 }
244                 $fh->close();
245                 $a->{fileCnt}++;
246                 $fileName = "$a->{base}_$a->{fileCnt}";
247             }
248             if ( !$match ) {
249                 #
250                 # We couldn't find another candidate file
251                 #
252                 if ( @{$a->{files}} == 1 ) {
253                     #print("   Exhausted matches, now writing\n");
254                     $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
255                                                     1, $a->{compress});
256                     if ( !defined($a->{fhOut}) ) {
257                         push(@{$a->{errors}},
258                                 "Unable to open $a->{fileName}"
259                               . " for writing");
260                     } else {
261                         if ( !$a->{files}[$i]->{fh}->rewind() ) {
262                             push(@{$a->{errors}}, 
263                                      "Unable to rewind"
264                                    . " $a->{files}[$i]->{name} for copy");
265                         }
266                         $a->filePartialCopy($a->{files}[$i]->{fh}, $a->{fhOut},
267                                         $a->{nWrite});
268                     }
269                 }
270                 $a->{files}[$i]->{fh}->close();
271                 splice(@{$a->{files}}, $i, 1);
272                 $i--;
273             }
274         }
275     }
276     if ( defined($a->{fhOut}) && $dataLen > 0 ) {
277         #
278         # if we are in writing mode then just write the data
279         #
280         my $n = $a->{fhOut}->write(\$a->{data});
281         if ( $n != $dataLen ) {
282             push(@{$a->{errors}}, "Unable to write $dataLen bytes to"
283                                 . " $a->{fileName} (got $n)");
284         }
285     }
286     $a->{nWrite} += $dataLen;
287     $a->{data} = "";
288     return if ( defined($dataRef) );
289
290     #
291     # We are at EOF, so finish up
292     #
293     $a->{eof} = 1;
294
295     #
296     # Make sure the fileSize was correct.  See above for comments about
297     # rsync.
298     #
299     if ( $a->{nWrite} != $a->{fileSize} ) {
300         #
301         # Oops, fileSize was wrong, so our MD5 digest was wrong and our
302         # effort to match files likely failed.  This is ugly, but our
303         # only choice at this point is to re-write the entire file with
304         # the correct length.  We need to rename the file, open it for
305         # reading, and then re-write the file with the correct length.
306         #
307
308         #print("Doing big file fixup ($a->{fileSize} != $a->{nWrite})\n");
309
310         my($fh, $fileName);
311         $a->{fileSize} = $a->{nWrite};
312
313         if ( defined($a->{fhOut}) ) {
314             if ( $a->{fileName} =~ /(.*)\// ) {
315                 $fileName = $1;
316             } else {
317                 $fileName = ".";
318             }
319             #
320             # Find a unique target temporary file name
321             #
322             my $i = 0;
323             while ( -f "$fileName/t$$.$i" ) {
324                 $i++;
325             }
326             $fileName = "$fileName/t$$.$i";
327             $a->{fhOut}->close();
328             if ( !rename($a->{fileName}, $fileName)
329               || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
330                                                  $a->{compress})) ) {
331                 push(@{$a->{errors}}, "Can't rename $a->{fileName} -> $fileName"
332                                     . " or open during size fixup");
333             }
334             #print("Using temporary name $fileName\n");
335         } elsif ( defined($a->{files}) && defined($a->{files}[0]) ) {
336             #
337             # We haven't written anything yet, so just use the
338             # compare file to copy from.
339             #
340             $fh = $a->{files}[0]->{fh};
341             $fh->rewind;
342             #print("Using compare file $a->{files}[0]->{name}\n");
343         }
344         if ( defined($fh) ) {
345             my $poolWrite = BackupPC::PoolWrite->new($a->{bpc}, $a->{fileName},
346                                         $a->{fileSize}, $a->{compress});
347             my $nRead = 0;
348
349             while ( $nRead < $a->{fileSize} ) {
350                 my $thisRead = $a->{fileSize} - $nRead < $BufSize
351                              ? $a->{fileSize} - $nRead : $BufSize;
352                 my $data;
353                 my $n = $fh->read(\$data, $thisRead);
354                 if ( $n != $thisRead ) {
355                     push(@{$a->{errors}},
356                                 "Unable to read $thisRead bytes during resize"
357                                . " from temp $fileName (got $n)");
358                     last;
359                 }
360                 $poolWrite->write(\$data);
361                 $nRead += $thisRead;
362             }
363             $fh->close;
364             unlink($fileName) if ( defined($fileName) );
365             if ( @{$a->{errors}} ) {
366                 $poolWrite->close;
367                 return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
368             } else {
369                 return $poolWrite->close;
370             }
371         }
372     }
373
374     if ( $a->{fileSize} == 0 ) {
375         #
376         # Simply create an empty file
377         #
378         local(*OUT);
379         if ( !open(OUT, ">", $a->{fileName}) ) {
380             push(@{$a->{errors}}, "Can't open $a->{fileName} for empty"
381                                 . " output");
382         } else {
383             close(OUT);
384         }
385         #
386         # Close the compare files
387         #
388         foreach my $f ( @{$a->{files}} ) {
389             $f->{fh}->close();
390         }
391         return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
392     } elsif ( defined($a->{fhOut}) ) {
393         $a->{fhOut}->close();
394         #
395         # Close the compare files
396         #
397         foreach my $f ( @{$a->{files}} ) {
398             $f->{fh}->close();
399         }
400         return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
401     } else {
402         if ( @{$a->{files}} == 0 ) {
403             push(@{$a->{errors}}, "Botch, no matches on $a->{fileName}"
404                                 . " ($a->{digest})");
405         } elsif ( @{$a->{files}} > 1 ) {
406             #
407             # This is no longer a real error because $Conf{HardLinkMax}
408             # could be hit, thereby creating identical pool files
409             #
410             #my $str = "Unexpected multiple matches on"
411             #       . " $a->{fileName} ($a->{digest})\n";
412             #for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
413             #    $str .= "     -> $a->{files}[$i]->{name}\n";
414             #}
415             #push(@{$a->{errors}}, $str);
416         }
417         for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
418             if ( link($a->{files}[$i]->{name}, $a->{fileName}) ) {
419                 #print("  Linked $a->{fileName} to $a->{files}[$i]->{name}\n");
420                 #
421                 # Close the compare files
422                 #
423                 foreach my $f ( @{$a->{files}} ) {
424                     $f->{fh}->close();
425                 }
426                 return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
427             }
428         }
429         #
430         # We were unable to link to the pool.  Either we're at the
431         # hardlink max, or the pool file got deleted.  Recover by
432         # writing the matching file, since we still have an open
433         # handle.
434         #
435         for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
436             if ( !$a->{files}[$i]->{fh}->rewind() ) {
437                 push(@{$a->{errors}}, 
438                          "Unable to rewind $a->{files}[$i]->{name}"
439                        . " for copy after link fail");
440                 next;
441             }
442             $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
443                                             1, $a->{compress});
444             if ( !defined($a->{fhOut}) ) {
445                 push(@{$a->{errors}},
446                         "Unable to open $a->{fileName}"
447                       . " for writing after link fail");
448             } else {
449                 $a->filePartialCopy($a->{files}[$i]->{fh}, $a->{fhOut},
450                                     $a->{nWrite});
451                 $a->{fhOut}->close;
452             }
453             last;
454         }
455         #
456         # Close the compare files
457         #
458         foreach my $f ( @{$a->{files}} ) {
459             $f->{fh}->close();
460         }
461         return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
462     }
463 }
464
465 #
466 # Finish writing: pass undef dataRef to write so it can do all
467 # the work.  Returns a 4 element array:
468 #
469 #   (existingFlag, digestString, outputFileLength, errorList)
470 #
471 sub close
472 {
473     my($a) = @_;
474
475     return $a->write(undef);
476 }
477
478 #
479 # Abort a pool write
480 #
481 sub abort
482 {
483     my($a) = @_;
484
485     if ( defined($a->{fhOut}) ) {
486         $a->{fhOut}->close();
487         unlink($a->{fileName});
488     }
489     foreach my $f ( @{$a->{files}} ) {
490         $f->{fh}->close();
491     }
492     $a->{files} = [];
493 }
494
495 #
496 # Copy $nBytes from files $fhIn to $fhOut.
497 #
498 sub filePartialCopy
499 {
500     my($a, $fhIn, $fhOut, $nBytes) = @_;
501     my($nRead);
502
503     while ( $nRead < $nBytes ) {
504         my $thisRead = $nBytes - $nRead < $BufSize
505                             ? $nBytes - $nRead : $BufSize;
506         my $data;
507         my $n = $fhIn->read(\$data, $thisRead);
508         if ( $n != $thisRead ) {
509             push(@{$a->{errors}},
510                         "Unable to read $thisRead bytes from "
511                        . $fhIn->name . " (got $n)");
512             return;
513         }
514         $n = $fhOut->write(\$data, $thisRead);
515         if ( $n != $thisRead ) {
516             push(@{$a->{errors}},
517                         "Unable to write $thisRead bytes to "
518                        . $fhOut->name . " (got $n)");
519             return;
520         }
521         $nRead += $thisRead;
522     }
523 }
524
525 #
526 # Compare $nBytes from files $fh0 and $fh1, and also compare additional
527 # $extra bytes from $fh1 to $$extraData.
528 #
529 sub filePartialCompare
530 {
531     my($a, $fh0, $fh1, $nBytes, $extra, $extraData) = @_;
532     my($nRead, $n);
533     my($data0, $data1);
534
535     while ( $nRead < $nBytes ) {
536         my $thisRead = $nBytes - $nRead < $BufSize
537                             ? $nBytes - $nRead : $BufSize;
538         $n = $fh0->read(\$data0, $thisRead);
539         if ( $n != $thisRead ) {
540             push(@{$a->{errors}}, "Unable to read $thisRead bytes from "
541                                  . $fh0->name . " (got $n)");
542             return;
543         }
544         $n = $fh1->read(\$data1, $thisRead);
545         return 0 if ( $n < $thisRead || $data0 ne $data1 );
546         $nRead += $thisRead;
547     }
548     if ( $extra > 0 ) {
549         # verify additional bytes
550         $n = $fh1->read(\$data1, $extra);
551         return 0 if ( $n != $extra || $data1 ne $$extraData );
552     } else {
553         # verify EOF
554         $n = $fh1->read(\$data1, 100);
555         return 0 if ( $n != 0 );
556     }
557     return 1;
558 }
559
560 #
561 # LinkOrCopy() does a hardlink from oldFile to newFile.
562 #
563 # If that fails (because there are too many links on oldFile)
564 # then oldFile is copied to newFile, and the pool stats are
565 # returned to be added to the new file list.  That allows
566 # BackupPC_link to try again, and to create a new pool file
567 # if necessary.
568 #
569 sub LinkOrCopy
570 {
571     my($bpc, $oldFile, $oldFileComp, $newFile, $newFileComp) = @_;
572     my($nRead, $data);
573
574     unlink($newFile)  if ( -f $newFile );
575     #
576     # Try to link if hardlink limit is ok, and compression types
577     # are the same
578     #
579     return (1, undef) if ( (stat($oldFile))[3] < $bpc->{Conf}{HardLinkMax}
580                             && !$oldFileComp == !$newFileComp
581                             && link($oldFile, $newFile) );
582     #
583     # There are too many links on oldFile, or compression
584     # type if different, so now we have to copy it.
585     #
586     # We need to compute the file size, which is expensive
587     # since we need to read the file twice.  That's probably
588     # ok since the hardlink limit is rarely hit.
589     #
590     my $readFd = BackupPC::FileZIO->open($oldFile, 0, $oldFileComp);
591     if ( !defined($readFd) ) {
592         return (0, undef, undef, undef, ["LinkOrCopy: can't open $oldFile"]);
593     }
594     while ( $readFd->read(\$data, $BufSize) > 0 ) {
595         $nRead += length($data);
596     }
597     $readFd->rewind();
598
599     my $poolWrite = BackupPC::PoolWrite->new($bpc, $newFile,
600                                              $nRead, $newFileComp);
601     while ( $readFd->read(\$data, $BufSize) > 0 ) {
602         $poolWrite->write(\$data);
603     }
604     my($exists, $digest, $outSize, $errs) = $poolWrite->close;
605
606     return ($exists, $digest, $nRead, $outSize, $errs);
607 }
608
609 1;