* BackupPC_trashClean now logs an error if it can't remove all the
[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  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.0beta2, released 13 Apr 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
112     #
113     # Correct the fileSize if it is wrong (rsync might transfer
114     # a file whose length is different to the length sent with the
115     # file list if the file changes between the file list sending
116     # and the file sending).  Here we only catch the case where
117     # we haven't computed the digest (ie: we have written no more
118     # than $BufSize.  We catch the big file case below.
119     #
120     if ( !defined($dataRef) && !defined($a->{digest})
121                 && $a->{fileSize} != length($a->{data}) ) {
122         $a->{fileSize} = length($a->{data});
123     }
124
125     if ( !defined($a->{digest}) && length($a->{data}) > 0 ) {
126         #
127         # build a list of all the candidate matching files
128         #
129         my $md5 = Digest::MD5->new;
130         $a->{fileSize} = length($a->{data})
131                             if ( $a->{fileSize} < length($a->{data}) );
132         $a->{digest} = $a->{bpc}->Buffer2MD5($md5, $a->{fileSize}, \$a->{data});
133         if ( !defined($a->{base} = $a->{bpc}->MD52Path($a->{digest},
134                                                        $a->{compress})) ) {
135             push(@{$a->{errors}}, "Unable to get path from '$a->{digest}'"
136                                 . " for $a->{fileName}\n");
137         } else {
138             while ( @{$a->{files}} < $MaxFiles ) {
139                 my $fh;
140                 my $fileName = $a->{fileCnt} < 0 ? $a->{base}
141                                         : "$a->{base}_$a->{fileCnt}";
142                 last if ( !-f $fileName );
143                 if ( (stat(_))[3] >= $a->{hardLinkMax}
144                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
145                                                      $a->{compress})) ) {
146                     $a->{fileCnt}++;
147                     next;
148                 }
149                 push(@{$a->{files}}, {
150                         name => $fileName,
151                         fh   => $fh,
152                      });
153                 $a->{fileCnt}++;
154             }
155         }
156         #
157         # if there are no candidate files then we must write
158         # the new file to disk
159         #
160         if ( !@{$a->{files}} ) {
161             $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
162                                               1, $a->{compress});
163             if ( !defined($a->{fhOut}) ) {
164                 push(@{$a->{errors}}, "Unable to open $a->{fileName}"
165                                     . " for writing\n");
166             }
167         }
168     }
169     my $dataLen = length($a->{data});
170     if ( !defined($a->{fhOut}) && length($a->{data}) > 0 ) {
171         #
172         # See if the new chunk of data continues to match the
173         # candidate files.
174         #
175         for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
176             my($d, $match);
177             my $fileName = $a->{fileCnt} < 0 ? $a->{base}
178                                              : "$a->{base}_$a->{fileCnt}";
179             if ( $dataLen > 0 ) {
180                 # verify next $dataLen bytes from candidate file
181                 my $n = $a->{files}[$i]->{fh}->read(\$d, $dataLen);
182                 next if ( $n == $dataLen && $d eq $a->{data} );
183             } else {
184                 # verify candidate file is at EOF
185                 my $n = $a->{files}[$i]->{fh}->read(\$d, 100);
186                 next if ( $n == 0 );
187             }
188             #print("   File $a->{files}[$i]->{name} doesn't match\n");
189             #
190             # this candidate file didn't match.  Replace it
191             # with a new candidate file.  We have to qualify
192             # any new candidate file by making sure that its
193             # first $a->{nWrite} bytes match, plus the next $dataLen
194             # bytes match $a->{data}.
195             #
196             while ( -f $fileName ) {
197                 my $fh;
198                 if ( (stat(_))[3] >= $a->{hardLinkMax}
199                     || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
200                                                      $a->{compress})) ) {
201                     $a->{fileCnt}++;
202                     #print("   Discarding $fileName (open failed)\n");
203                     $fileName = "$a->{base}_$a->{fileCnt}";
204                     next;
205                 }
206                 if ( !$a->{files}[$i]->{fh}->rewind() ) {
207                     push(@{$a->{errors}},
208                             "Unable to rewind $a->{files}[$i]->{name}"
209                           . " for compare\n");
210                 }
211                 $match = $a->filePartialCompare($a->{files}[$i]->{fh}, $fh,
212                                           $a->{nWrite}, $dataLen, \$a->{data});
213                 if ( $match ) {
214                     $a->{files}[$i]->{fh}->close();
215                     $a->{files}[$i]->{fh} = $fh,
216                     $a->{files}[$i]->{name} = $fileName;
217                     #print("   Found new candidate $fileName\n");
218                     $a->{fileCnt}++;
219                     last;
220                 } else {
221                     #print("   Discarding $fileName (no match)\n");
222                 }
223                 $fh->close();
224                 $a->{fileCnt}++;
225                 $fileName = "$a->{base}_$a->{fileCnt}";
226             }
227             if ( !$match ) {
228                 #
229                 # We couldn't find another candidate file
230                 #
231                 if ( @{$a->{files}} == 1 ) {
232                     #print("   Exhausted matches, now writing\n");
233                     $a->{fhOut} = BackupPC::FileZIO->open($a->{fileName},
234                                                     1, $a->{compress});
235                     if ( !defined($a->{fhOut}) ) {
236                         push(@{$a->{errors}},
237                                 "Unable to open $a->{fileName}"
238                               . " for writing\n");
239                     } else {
240                         if ( !$a->{files}[$i]->{fh}->rewind() ) {
241                             push(@{$a->{errors}}, 
242                                      "Unable to rewind"
243                                    . " $a->{files}[$i]->{name} for copy\n");
244                         }
245                         $a->filePartialCopy($a->{files}[$i]->{fh}, $a->{fhOut},
246                                         $a->{nWrite});
247                     }
248                 }
249                 $a->{files}[$i]->{fh}->close();
250                 splice(@{$a->{files}}, $i, 1);
251                 $i--;
252             }
253         }
254     }
255     if ( defined($a->{fhOut}) && $dataLen > 0 ) {
256         #
257         # if we are in writing mode then just write the data
258         #
259         my $n = $a->{fhOut}->write(\$a->{data});
260         if ( $n != $dataLen ) {
261             push(@{$a->{errors}}, "Unable to write $dataLen bytes to"
262                                 . " $a->{fileName} (got $n)\n");
263         }
264     }
265     $a->{nWrite} += $dataLen;
266     $a->{data} = "";
267     return if ( defined($dataRef) );
268
269     #
270     # We are at EOF, so finish up
271     #
272     $a->{eof} = 1;
273     foreach my $f ( @{$a->{files}} ) {
274         $f->{fh}->close();
275     }
276
277     #
278     # Make sure the fileSize was correct.  See above for comments about
279     # rsync.
280     #
281     if ( $a->{nWrite} != $a->{fileSize} ) {
282         #
283         # Oops, fileSize was wrong, so our MD5 digest was wrong and our
284         # effort to match files likely failed.  This is ugly, but our
285         # only choice at this point is to re-write the entire file with
286         # the correct length.  We need to rename the file, open it for
287         # reading, and then re-write the file with the correct length.
288         #
289
290         #print("Doing big file fixup ($a->{fileSize} != $a->{nWrite})\n");
291
292         my($fh, $fileName);
293         $a->{fileSize} = $a->{nWrite};
294         if ( $a->{fileName} =~ /(.*)\// ) {
295             $fileName = $1;
296         } else {
297             $fileName = ".";
298         }
299
300         #
301         # Find a unique target temporary file name
302         #
303         my $i = 0;
304         while ( -f "$fileName/t$$.$i" ) {
305             $i++;
306         }
307         $fileName = "$fileName/t$$.$i";
308         $a->{fhOut}->close();
309         if ( !rename($a->{fileName}, $fileName)
310           || !defined($fh = BackupPC::FileZIO->open($fileName, 0,
311                                              $a->{compress})) ) {
312             push(@{$a->{errors}}, "Can't rename $a->{fileName} -> $fileName"
313                                 . " or open during size fixup\n");
314         } else {
315             my $poolWrite = BackupPC::PoolWrite->new($a->{bpc}, $a->{fileName},
316                                         $a->{fileSize}, $a->{compress});
317             my $nRead = 0;
318
319             while ( $nRead < $a->{fileSize} ) {
320                 my $thisRead = $a->{fileSize} - $nRead < $BufSize
321                              ? $a->{fileSize} - $nRead : $BufSize;
322                 my $data;
323                 my $n = $fh->read(\$data, $thisRead);
324                 if ( $n != $thisRead ) {
325                     push(@{$a->{errors}},
326                                 "Unable to read $thisRead bytes during resize"
327                                . " from temp $fileName (got $n)\n");
328                     last;
329                 }
330                 $poolWrite->write(\$data);
331                 $nRead += $thisRead;
332             }
333             $fh->close;
334             unlink($fileName);
335             if ( @{$a->{errors}} ) {
336                 $poolWrite->close;
337                 return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
338             } else {
339                 return $poolWrite->close;
340             }
341         }
342     }
343
344     if ( $a->{fileSize} == 0 ) {
345         #
346         # Simply create an empty file
347         #
348         local(*OUT);
349         if ( !open(OUT, ">", $a->{fileName}) ) {
350             push(@{$a->{errors}}, "Can't open $a->{fileName} for empty"
351                                 . " output\n");
352         } else {
353             close(OUT);
354         }
355         return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
356     } elsif ( defined($a->{fhOut}) ) {
357         $a->{fhOut}->close();
358         return (0, $a->{digest}, -s $a->{fileName}, $a->{errors});
359     } else {
360         if ( @{$a->{files}} == 0 ) {
361             push(@{$a->{errors}}, "Botch, no matches on $a->{fileName}"
362                                 . " ($a->{digest})\n");
363         } elsif ( @{$a->{files}} > 1 ) {
364             #
365             # This is no longer a real error because $Conf{HardLinkMax}
366             # could be hit, thereby creating identical pool files
367             #
368             #my $str = "Unexpected multiple matches on"
369             #       . " $a->{fileName} ($a->{digest})\n";
370             #for ( my $i = 0 ; $i < @{$a->{files}} ; $i++ ) {
371             #    $str .= "     -> $a->{files}[$i]->{name}\n";
372             #}
373             #push(@{$a->{errors}}, $str);
374         }
375         #print("   Linking $a->{fileName} to $a->{files}[0]->{name}\n");
376         if ( @{$a->{files}} && !link($a->{files}[0]->{name}, $a->{fileName}) ) {
377             push(@{$a->{errors}}, "Can't link $a->{fileName} to"
378                                 . " $a->{files}[0]->{name}\n");
379         }
380         return (1, $a->{digest}, -s $a->{fileName}, $a->{errors});
381     }
382 }
383
384 #
385 # Finish writing: pass undef dataRef to write so it can do all
386 # the work.  Returns a 4 element array:
387 #
388 #   (existingFlag, digestString, outputFileLength, errorList)
389 #
390 sub close
391 {
392     my($a) = @_;
393
394     return $a->write(undef);
395 }
396
397 #
398 # Copy $nBytes from files $fhIn to $fhOut.
399 #
400 sub filePartialCopy
401 {
402     my($a, $fhIn, $fhOut, $nBytes) = @_;
403     my($nRead);
404
405     while ( $nRead < $nBytes ) {
406         my $thisRead = $nBytes - $nRead < $BufSize
407                             ? $nBytes - $nRead : $BufSize;
408         my $data;
409         my $n = $fhIn->read(\$data, $thisRead);
410         if ( $n != $thisRead ) {
411             push(@{$a->{errors}},
412                         "Unable to read $thisRead bytes from "
413                        . $fhIn->name . " (got $n)\n");
414             return;
415         }
416         $n = $fhOut->write(\$data, $thisRead);
417         if ( $n != $thisRead ) {
418             push(@{$a->{errors}},
419                         "Unable to write $thisRead bytes to "
420                        . $fhOut->name . " (got $n)\n");
421             return;
422         }
423         $nRead += $thisRead;
424     }
425 }
426
427 #
428 # Compare $nBytes from files $fh0 and $fh1, and also compare additional
429 # $extra bytes from $fh1 to $$extraData.
430 #
431 sub filePartialCompare
432 {
433     my($a, $fh0, $fh1, $nBytes, $extra, $extraData) = @_;
434     my($nRead, $n);
435     my($data0, $data1);
436
437     while ( $nRead < $nBytes ) {
438         my $thisRead = $nBytes - $nRead < $BufSize
439                             ? $nBytes - $nRead : $BufSize;
440         $n = $fh0->read(\$data0, $thisRead);
441         if ( $n != $thisRead ) {
442             push(@{$a->{errors}}, "Unable to read $thisRead bytes from "
443                                  . $fh0->name . " (got $n)\n");
444             return;
445         }
446         $n = $fh1->read(\$data1, $thisRead);
447         return 0 if ( $n < $thisRead || $data0 ne $data1 );
448         $nRead += $thisRead;
449     }
450     if ( $extra > 0 ) {
451         # verify additional bytes
452         $n = $fh1->read(\$data1, $extra);
453         return 0 if ( $n != $extra || $data1 ne $$extraData );
454     } else {
455         # verify EOF
456         $n = $fh1->read(\$data1, 100);
457         return 0 if ( $n != 0 );
458     }
459     return 1;
460 }
461
462 1;