use File::Compare;
use File::Temp;
-# Copyright (C) 2003-2006 Zygo Blaxell <zblaxell@feedme.hungrycats.org>
+# Copyright (C) 2002-2010 Zygo Blaxell <faster-dupemerge@mailtoo.hungrycats.org>
# 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
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;
if ($skip_hashes) {
return "SKIPPING HASHES";
} else {
+ print STDERR 'H' if $progress;
my $digest = &really_digest($filename);
$hash_bytes += -s $filename;
$hash_files++;
--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)
} 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') {
}
}
-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: $!";
my $printf_string = '%s ' .
($collapse_access ? '0 0 0 ' : '%U %G %m ') .
($collapse_timestamp ? '0 ' : '%T@ ') .
- '%D:%i %p\0';
+ '%D %i %p\0';
push(@find_command, '!', '-empty') unless $collapse_zero;
push(@find_command, '-printf', $printf_string);
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;
$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++;
}
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 ($@) {
if ($ok) {
print STDERR "\t\tDigest is $digest\n" if $debug;
- my $incumbent = $hash_to_inode{$digest};
- if (defined($incumbent)) {
+ my $incumbent_list = ($hash_to_inode{$digest} ||= []);
+ my $incumbent_matched = 0;
+ for my $incumbent (sort @$incumbent_list) {
print STDERR "\t\tInodes $incumbent and $candidate have same hash\n" if $debug;
my $finished = 0;
link_start:
until ($finished) {
- my @incumbent_names = keys(%{$inode_to_file_name{$incumbent}});
- my @candidate_names = keys(%{$inode_to_file_name{$candidate}});
- print STDERR "\t\tLinks to $incumbent:", join("\n\t\t\t", '', @incumbent_names), "\n" if $debug;
+ 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;
}
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;
}
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;
print STDERR "$quoted_incumbent_file and $quoted_candidate_file have same hash but do not compare equal!\n" unless $skip_hashes;
} else {
$identical = 1;
+ $incumbent_matched = 1;
}
$compare_count++;
$compare_bytes += $incumbent_size;
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;
# My random number generator chooses the incumbent's size.
if ($link_done) {
- # Since we're in a dry run, the filesystem doesn't change.
- # Our notion of what the filesystem should look like should not change either.
delete $inode_to_file_name{$to_inode}->{$to_file};
- unless ($dry_run) {
- $inode_to_file_name{$from_inode}->{$to_file} = undef;
- $hash_to_inode{$digest} = $from_inode;
- }
+ $inode_to_file_name{$from_inode}->{$to_file} = undef unless ($dry_run);
+ $hash_to_inode{$digest} = [ $from_inode ];
$hard_links++;
if ($to_nlink == 1) {
}
$finished = 1;
}
- } else {
+ }
+ unless ($incumbent_matched) {
print STDERR "\t\tNew hash entered\n" if $debug;
- $hash_to_inode{$digest} = $candidate;
+ push(@$incumbent_list, $candidate);
}
} else {
warn "No digests found for inode $candidate\n";
delete $inode_to_file_name{$candidate};
}
}
+ print STDERR '.' if $progress;
end_merge:
undef %inode_to_file_name;
}
+my $last_time = 0;
+my $last_size = 0;
+
while (<FIND>) {
- my ($weak_key, $inode, $name) = m/^(\d+ \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++;
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;
}
$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);
projects / dupemerge / blobdiff