X-Git-Url: http://git.hungrycats.org/cgi-bin/gitweb.cgi?p=dupemerge;a=blobdiff_plain;f=faster-dupemerge;h=4cdef9716fd5e5de600b9810a198936ca9d46301;hp=de9cc7940b11645cb8a3af51201bc32ce11026e7;hb=de7efbca76dfc8ca745d8dabc2f9a99d9af0e4b4;hpb=822747d401e3e4b3cdb1c86b7e4e531cbe8b3d5f diff --git a/faster-dupemerge b/faster-dupemerge index de9cc79..4cdef97 100755 --- a/faster-dupemerge +++ b/faster-dupemerge @@ -4,7 +4,7 @@ use Fcntl qw(:DEFAULT :flock); use File::Compare; use File::Temp; -# Copyright (C) 2003-2007 Zygo Blaxell +# Copyright (C) 2002-2010 Zygo Blaxell # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -86,7 +86,10 @@ my $collapse_access = 0; my $collapse_timestamp = 0; my $collapse_zero = 0; my $skip_compares = 0; +my $skip_compare_preference = 0; my $skip_hashes = 0; +my $skip_hashes_threshold = 0; +my $progress = 0; my $verbose = 0; my $debug = 0; my $dry_run = 0; @@ -102,6 +105,7 @@ sub digest { if ($skip_hashes) { return "SKIPPING HASHES"; } else { + print STDERR 'H' if $progress; my $digest = &really_digest($filename); $hash_bytes += -s $filename; $hash_files++; @@ -132,24 +136,37 @@ hard links). --debug show all steps in duplication discovery process (implies --verbose) - --dry-run do not lock files or make changes to filesystem + --dry-run do not lock files or make changes to filesystem --find pass next options (up to --) to find command - --humane human-readable statistics (e.g. 1 048 576) + --humane human-readable statistics (e.g. 1 048 576) --lock FILE exit immediately (status 10) if unable to obtain a flock(LOCK_EX|LOCK_NB) on FILE - --lock-rm remove lock file at exit + --lock-rm remove lock file at exit + + --progress output single-character progress indicators: + C - compare + H - hash + L - link(2) + R - rename(2) + S, s - lstat(2) (see source for details) + U - unlink(2) + . - all inodes with similar attributes done + (123456) - current file size in bytes --sort pass next options (up to --) to sort command --timestamps mtime may be different for identical files - --skip-compare skip byte-by-byte file comparisons + --skip-compare skip byte-by-byte file comparisons - --skip-hash skip calculation of hash function on files + --skip-hash[=N] skip calculation of hash function on files + larger than N bytes (default 1M). + Scalars KMGT specify KiB, MiB, GiB, and TiB. + Scalars kmgt specify KB, MB, GB, and TB. --trust old name for --skip-compare (trust the hash function) @@ -169,9 +186,26 @@ while ($#ARGV >= 0) { } elsif ($arg eq '--zeros') { $collapse_zero = 1; } elsif ($arg eq '--trust' || $arg eq '--skip-compare') { - $skip_compares = 1; - } elsif ($arg eq '--skip-hash') { - $skip_hashes = 1; + $skip_compares = $skip_compare_preference = 1; + } elsif ($arg =~ /^--skip-hash(?:=(\d+)([KkMmGgTt]?))?$/os) { + my ($quantity, $unit) = ($1, $2); + $unit ||= '_'; + $quantity ||= 1048576; + my %scale = ( + _ => 1, + k => 1000, + K => 1024, + m => 1000*1000, + M => 1024*1024, + g => 1000*1000*1000, + G => 1024*1024*1024, + t => 1000*1000*1000*1000, + T => 1024*1024*1024*1024, + ); + $skip_hashes = 0; + $skip_hashes_threshold = $quantity * $scale{$unit}; + } elsif ($arg eq '--progress') { + $progress = 1; } elsif ($arg eq '--verbose') { $verbose = 1; } elsif ($arg eq '--lock-rm') { @@ -208,11 +242,7 @@ while ($#ARGV >= 0) { } } -if ($skip_hashes && $skip_compares) { - die "Cannot skip both hashes and compares.\n"; -} - -@directories or usage; +@directories or usage($0); if (defined($lock_file) && !$dry_run) { sysopen(LOCK_FILE, $lock_file, O_CREAT|O_RDONLY, 0666) or die "open: $lock_file: $!"; @@ -238,7 +268,7 @@ my @find_command = ('find', @directories, @extra_find_opts, '-type', 'f'); my $printf_string = '%s ' . ($collapse_access ? '0 0 0 ' : '%U %G %m ') . ($collapse_timestamp ? '0 ' : '%T@ ') . - '%i %p\0'; + '%D %i %p\0'; push(@find_command, '!', '-empty') unless $collapse_zero; push(@find_command, '-printf', $printf_string); @@ -269,6 +299,7 @@ sub link_files { my $quoted_from = tick_quote($from); my $quoted_to = tick_quote($to); + print STDERR "\n" if $progress; print STDERR "ln -f $quoted_from $quoted_to\n"; return if $dry_run; @@ -279,15 +310,25 @@ sub link_files { $inode_base =~ s:^.*/::os; my $tmp_to = File::Temp::tempnam($inode_dir, ".$inode_base."); print STDERR "\tlink: $from -> $tmp_to\n" if $debug; + print STDERR 'L' if $progress; link($from, $tmp_to) or die "link: $from -> $tmp_to: $!"; print STDERR "\trename: $tmp_to -> $to\n" if $debug; + print STDERR 'R' if $progress; unless (rename($tmp_to, $to)) { my $saved_bang = $!; + print STDERR 'U' if $progress; unlink($tmp_to) or warn "unlink: $tmp_to: $!"; # Try, possibly in vain, to clean up die "rename: $tmp_to -> $from: $saved_bang"; } } +# Convert $dev,$ino into a single string where lexical and numeric orderings are equivalent +sub format_inode ($$) { + my ($dev, $ino) = @_; + # 64 bits ought to be enough for everybody! + return sprintf('%016x:%016x', $dev, $ino); +} + # Process all known files so far. sub merge_files { $merges_attempted++; @@ -305,21 +346,23 @@ sub merge_files { } print STDERR "Merging...\n" if $debug; - foreach my $candidate (@candidate_list) { + foreach my $candidate (sort @candidate_list) { print STDERR "\tDigesting candidate $candidate\n" if $debug; my $ok = 0; my $digest; hash_file: - foreach my $filename (keys(%{$inode_to_file_name{$candidate}})) { + foreach my $filename (sort keys(%{$inode_to_file_name{$candidate}})) { print STDERR "\t\tDigesting file $filename\n" if $debug; if ((-l $filename) || ! -f _) { + print STDERR "\n" if $progress; warn "Bogon file " . tick_quote($filename); - $surprises++; + $input_bogons++; + delete $inode_to_file_name{$candidate}->{$filename}; next; } - eval { + eval { $digest = digest($filename); }; if ($@) { @@ -335,7 +378,7 @@ hash_file: my $incumbent_list = ($hash_to_inode{$digest} ||= []); my $incumbent_matched = 0; - for my $incumbent (@$incumbent_list) { + for my $incumbent (sort @$incumbent_list) { print STDERR "\t\tInodes $incumbent and $candidate have same hash\n" if $debug; my $finished = 0; @@ -343,25 +386,26 @@ hash_file: link_start: until ($finished) { - my @incumbent_names = keys(%{$inode_to_file_name{$incumbent}}); - my @candidate_names = keys(%{$inode_to_file_name{$candidate}}); + my @incumbent_names = sort keys(%{$inode_to_file_name{$incumbent}}); + my @candidate_names = sort keys(%{$inode_to_file_name{$candidate}}); print STDERR "\t\tLinks to $incumbent:", join("\n\t\t\t", '', @incumbent_names), "\n" if $debug; print STDERR "\t\tLinks to $candidate:", join("\n\t\t\t", '', @candidate_names), "\n" if $debug; incumbent_file: foreach my $incumbent_file (@incumbent_names) { + print STDERR 'S' if $progress; my ($incumbent_dev,$incumbent_ino,$incumbent_mode,$incumbent_nlink,$incumbent_uid,$incumbent_gid,$incumbent_rdev,$incumbent_size,$incumbent_atime,$incumbent_mtime,$incumbent_ctime,$incumbent_blksize,$incumbent_blocks) = lstat($incumbent_file); print STDERR "\t\tINCUMBENT dev=$incumbent_dev ino=$incumbent_ino mode=$incumbent_mode nlink=$incumbent_nlink uid=$incumbent_uid gid=$incumbent_gid rdev=$incumbent_rdev size=$incumbent_size atime=$incumbent_atime mtime=$incumbent_mtime ctime=$incumbent_ctime blksize=$incumbent_blksize blocks=$incumbent_blocks _=$incumbent_file\n" if $debug; - if (!defined($incumbent_blocks)) { + if (!defined($incumbent_blocks) || ! (-f _)) { warn "lstat: $incumbent_file: $!"; $surprises++; next incumbent_file; } - if ($incumbent_ino != $incumbent) { - warn "$incumbent_file: expected inode $incumbent, found $incumbent_ino"; + if (format_inode($incumbent_dev, $incumbent_ino) ne $incumbent) { + warn "$incumbent_file: expected inode $incumbent, found ".format_inode($incumbent_dev, $incumbent_ino); $surprises++; next incumbent_file; } @@ -371,17 +415,18 @@ incumbent_file: candidate_file: foreach my $candidate_file (@candidate_names) { + print STDERR 's' if $progress; my ($candidate_dev,$candidate_ino,$candidate_mode,$candidate_nlink,$candidate_uid,$candidate_gid,$candidate_rdev,$candidate_size,$candidate_atime,$candidate_mtime,$candidate_ctime,$candidate_blksize,$candidate_blocks) = lstat($candidate_file); print STDERR "\t\t\tCANDIDATE dev=$candidate_dev ino=$candidate_ino mode=$candidate_mode nlink=$candidate_nlink uid=$candidate_uid gid=$candidate_gid rdev=$candidate_rdev size=$candidate_size atime=$candidate_atime mtime=$candidate_mtime ctime=$candidate_ctime blksize=$candidate_blksize blocks=$candidate_blocks _=$candidate_file\n" if $debug; - if (!defined($candidate_blocks)) { + if (!defined($candidate_blocks) || ! (-f _)) { warn "lstat: $candidate_file: $!"; $surprises++; next candidate_file; } - if ($candidate_ino != $candidate) { - warn "$candidate_file: expected inode $candidate, found $candidate_ino"; + if (format_inode($candidate_dev, $candidate_ino) ne $candidate) { + warn "$candidate_file: expected inode $candidate, found ".format_inode($candidate_dev, $candidate_ino); $surprises++; next candidate_file; } @@ -402,6 +447,7 @@ candidate_file: my $quoted_incumbent_file = tick_quote($incumbent_file); my $quoted_candidate_file = tick_quote($candidate_file); print STDERR "cmp $quoted_incumbent_file $quoted_candidate_file\n" if $debug; + print STDERR 'C' if $progress; if (compare($incumbent_file, $candidate_file)) { $compare_differences++; $identical = 0; @@ -443,6 +489,12 @@ candidate_file: my $link_done = 0; my ($from_file, $to_file, $from_inode, $to_inode, $from_nlink, $to_nlink); + + # If the candidate has more links than incumbent, replace incumbent with candidate. + # If the incumbent has more links than candidate, replace candidate with incumbent. + # If the link counts are equal, we saw incumbent first, so keep the incumbent. + # "We saw incumbent first" is significant because we explicitly sort the inodes. + # Thank Johannes Niess for this idea. if ($candidate_nlink > $incumbent_nlink) { $from_file = $candidate_file; $to_file = $incumbent_file; @@ -490,7 +542,7 @@ candidate_file: if ($link_done) { delete $inode_to_file_name{$to_inode}->{$to_file}; - $inode_to_file_name{$from_inode}->{$to_file} = undef; + $inode_to_file_name{$from_inode}->{$to_file} = undef unless ($dry_run); $hash_to_inode{$digest} = [ $from_inode ]; $hard_links++; @@ -529,6 +581,7 @@ candidate_file: delete $inode_to_file_name{$candidate}; } } + print STDERR '.' if $progress; end_merge: @@ -536,16 +589,32 @@ end_merge: undef %inode_to_file_name; } +my $last_time = 0; +my $last_size = 0; + while () { - my ($weak_key, $inode, $name) = m/^(\d+ \d+ \d+ \d+ -?[\d.]+) (\d+) (.+)\0$/so; + my ($weak_key, $size, $dev, $ino, $name) = m/^((\d+) \d+ \d+ \d+ -?[\d.]+) (\d+) (\d+) (.+)\0$/so; die "read error: $!\nLast input line was '$_'" unless defined($name); + my $inode = format_inode($dev, $ino); + print STDERR "weak_key=$weak_key inode=$inode name=$name\n" if $debug; - unless (! (-l $name) && (-f _)) { - warn "Bogon file " . tick_quote($name); - $input_bogons++; - next; + if ($skip_hashes_threshold && $size >= $skip_hashes_threshold) { + $skip_hashes = 1; + $skip_compares = 0; + } else { + $skip_hashes = 0; + $skip_compares = $skip_compare_preference; + } + + if ($progress) { + my $this_time = time(); + if ($this_time != $last_time && $size != $last_size) { + $last_time = $this_time; + $last_size = $size; + print STDERR "($size)"; + } } $input_links++; @@ -596,7 +665,7 @@ if ($humane) { sub space_numbers { my ($num) = @_; - 1 while $num =~ s/(\d)(\d\d\d)( \d\d\d)*$/$1 $2$3/os; + 1 while $num =~ s/(\d)(\d\d\d)((?: \d\d\d)*)$/$1 $2$3/os; $num = ' ' x ($max_num_len - length($num)) . $num; return $num; } @@ -606,6 +675,7 @@ if ($humane) { $stats_blob =~ s/([^\n]*\n[^\n]*? )(\s+)( [^\n]*\n)/$1 . ('.' x length($2)) . $3/oemg; +print STDERR "\n" if $progress; print STDERR $stats_blob; exit(0);