Repository: pkolaczk/fclones (language: rust)

Issue:
Already hardlinked files are read more than once
Hello,

files which are already hardlinked do not need to read twice ore more. Expected in this test is, that 20 GB are read, not 40 GB.
Patterns like this are caused by [backups using cp and rsync](http://www.mikerubel.org/computers/rsync_snapshots/), where hundreds of hardlinks are not uncommon.

```
me@pc:~/tmp$ mkdir a ; mkdir b ; dd if=/dev/urandom of=a/1 bs=1M count=10k ; cp a/1 a/2 ; ln a/1 b/1 ; ln a/2 b/2 
10240+0 Datensätze ein
10240+0 Datensätze aus
10737418240 Bytes (11 GB, 10 GiB) kopiert, 33,2262 s, 323 MB/s
me@pc:~/tmp$ fclones group a b
[2022-06-11 16:31:02.355] fclones:  info: Started grouping
[2022-06-11 16:31:02.360] fclones:  info: Scanned 6 file entries
[2022-06-11 16:31:02.360] fclones:  info: Found 4 (42.9 GB) files matching selection criteria
[2022-06-11 16:31:02.361] fclones:  info: Found 3 (32.2 GB) candidates after grouping by size
[2022-06-11 16:31:02.361] fclones:  info: Found 3 (32.2 GB) candidates after grouping by paths and file identifiers
[2022-06-11 16:31:02.363] fclones:  info: Found 3 (32.2 GB) candidates after grouping by prefix
[2022-06-11 16:31:02.364] fclones:  info: Found 3 (32.2 GB) candidates after grouping by suffix
Grouping by contents        [==========================================>       ]    34.28GB/40.00GB
^C
me@pc:~/tmp$ ls -li a/? b/?
8126615 -rw-r--r-- 2 me me 10737418240 11. Jun 16:29 a/1
8126616 -rw-r--r-- 2 me me 10737418240 11. Jun 16:30 a/2
8126615 -rw-r--r-- 2 me me 10737418240 11. Jun 16:29 b/1
8126616 -rw-r--r-- 2 me me 10737418240 11. Jun 16:30 b/2
me@pc:~/tmp$ 
```




Discussion / hints:
I think you can use `--cache` to avoid it.
 

Anyway, this is a known issue. This started happening after I removed the code that prunes the hardlinks early in the process, so that all hardlinks can be reported in the output. However, I need to add some in-memory caching layer to avoid hashing the files we already hashed once. 
> I think you can use `--cache` to avoid it.
Well, not on the first run:
```
me@pc:~/tmp$ rm -rf ~/.cache/fclones/
me@pc:~/tmp$ time fclones group  a b
[2022-06-13 17:32:42.201] fclones:  info: Started grouping
[2022-06-13 17:32:42.205] fclones:  info: Scanned 6 file entries
[2022-06-13 17:32:42.205] fclones:  info: Found 4 (42.9 GB) files matching selection criteria
[2022-06-13 17:32:42.205] fclones:  info: Found 3 (32.2 GB) candidates after grouping by size
[2022-06-13 17:32:42.205] fclones:  info: Found 3 (32.2 GB) candidates after grouping by paths and file identifiers
[2022-06-13 17:32:42.209] fclones:  info: Found 3 (32.2 GB) candidates after grouping by prefix
[2022-06-13 17:32:42.216] fclones:  info: Found 3 (32.2 GB) candidates after grouping by suffix
[2022-06-13 17:32:54.937] fclones:  info: Found 3 (32.2 GB) redundant files
# Report by fclones 0.25.0
# Timestamp: 2022-06-13 17:32:54.939 +0200
# Command: fclones group a b
# Base dir: /home/me/tmp
# Total: 42949672960 B (42.9 GB) in 4 files in 1 groups
# Redundant: 32212254720 B (32.2 GB) in 3 files
# Missing: 0 B (0 B) in 0 files
32d0c7c0740d7b71703c5df2f89dce3d, 10737418240 B (10.7 GB) * 4:
    /home/me/tmp/a/1
    /home/me/tmp/a/2
    /home/me/tmp/b/1
    /home/me/tmp/b/2

real	0m12,759s
user	0m3,318s
sys	0m12,767s
me@pc:~/tmp$ time fclones group --cache a b
[2022-06-13 17:33:03.823] fclones:  info: Started grouping
[2022-06-13 17:33:03.846] fclones:  info: Scanned 6 file entries
[2022-06-13 17:33:03.846] fclones:  info: Found 4 (42.9 GB) files matching selection criteria
[2022-06-13 17:33:03.846] fclones:  info: Found 3 (32.2 GB) candidates after grouping by size
[2022-06-13 17:33:03.847] fclones:  info: Found 3 (32.2 GB) candidates after grouping by paths and file identifiers
[2022-06-13 17:33:03.850] fclones:  info: Found 3 (32.2 GB) candidates after grouping by prefix
[2022-06-13 17:33:03.850] fclones:  info: Found 3 (32.2 GB) candidates after grouping by suffix
[2022-06-13 17:33:18.567] fclones:  info: Found 3 (32.2 GB) redundant files
# Report by fclones 0.25.0
# Timestamp: 2022-06-13 17:33:18.575 +0200
# Command: fclones group --cache a b
# Base dir: /home/me/tmp
# Total: 42949672960 B (42.9 GB) in 4 files in 1 groups
# Redundant: 32212254720 B (32.2 GB) in 3 files
# Missing: 0 B (0 B) in 0 files
32d0c7c0740d7b71703c5df2f89dce3d, 10737418240 B (10.7 GB) * 4:
    /home/me/tmp/a/1
    /home/me/tmp/a/2
    /home/me/tmp/b/1
    /home/me/tmp/b/2

real	0m14,768s
user	0m3,632s
sys	0m14,287s
me@pc:~/tmp$ time fclones group --cache a b
[2022-06-13 17:33:26.262] fclones:  info: Started grouping
[2022-06-13 17:33:26.285] fclones:  info: Scanned 6 file entries
[2022-06-13 17:33:26.285] fclones:  info: Found 4 (42.9 GB) files matching selection criteria
[2022-06-13 17:33:26.286] fclones:  info: Found 3 (32.2 GB) candidates after grouping by size
[2022-06-13 17:33:26.286] fclones:  info: Found 3 (32.2 GB) candidates after grouping by paths and file identifiers
[2022-06-13 17:33:26.289] fclones:  info: Found 3 (32.2 GB) candidates after grouping by prefix
[2022-06-13 17:33:26.290] fclones:  info: Found 3 (32.2 GB) candidates after grouping by suffix
[2022-06-13 17:33:26.292] fclones:  info: Found 3 (32.2 GB) redundant files
# Report by fclones 0.25.0
# Timestamp: 2022-06-13 17:33:26.295 +0200
# Command: fclones group --cache a b
# Base dir: /home/me/tmp
# Total: 42949672960 B (42.9 GB) in 4 files in 1 groups
# Redundant: 32212254720 B (32.2 GB) in 3 files
# Missing: 0 B (0 B) in 0 files
32d0c7c0740d7b71703c5df2f89dce3d, 10737418240 B (10.7 GB) * 4:
    /home/me/tmp/a/1
    /home/me/tmp/a/2
    /home/me/tmp/b/1
    /home/me/tmp/b/2

real	0m0,047s
user	0m0,006s
sys	0m0,063s
me@pc:~/tmp$ 

```

Fix patch:
diff --git a/src/file.rs b/src/file.rs
index ab86a7e..69405b2 100644
--- a/src/file.rs
+++ b/src/file.rs
@@ -260,6 +260,10 @@ impl FileId {
             device: metadata.dev(),
         }
     }
+
+    pub fn of(f: impl AsRef<FileId>) -> FileId {
+        *f.as_ref()
+    }
 }
 
 /// Convenience wrapper for accessing OS-dependent metadata like inode and device-id
diff --git a/src/group.rs b/src/group.rs
index 7342062..80345c5 100644
--- a/src/group.rs
+++ b/src/group.rs
@@ -249,6 +249,28 @@ impl<F: AsRef<Path>> FileGroup<F> {
     }
 }
 
+impl<F: AsRef<FileId>> FileGroup<F> {
+    /// Returns the number of files with distinct identifiers.
+    /// Files must be sorted by id.
+    pub fn unique_count(&self) -> usize {
+        self.files
+            .iter()
+            .dedup_by(|f1, f2| FileId::of(f1) == FileId::of(f2))
+            .count()
+    }
+
+    /// Returns the total size of data in files with distinct identifiers.
+    /// Files must be sorted by id.
+    pub fn unique_size(&self) -> FileLen {
+        self.file_len * self.unique_count() as u64
+    }
+
+    /// Sorts the files in this group by their identifiers.
+    pub fn sort_by_id(&mut self) {
+        self.files.sort_by_key(|f| FileId::of(f));
+    }
+}
+
 impl<F: AsRef<Path> + AsRef<FileId>> FileGroup<F> {
     /// Returns true if the file group should be forwarded to the next grouping stage,
     /// because the number of duplicate files is higher than the maximum allowed number of replicas.
@@ -339,7 +361,7 @@ impl<F: AsRef<Path> + AsRef<FileId>> FileGroup<F> {
 
     /// Sorts the files by their path names.
     /// If filter requires grouping by roots, then groups are kept together.
-    pub fn sort(&mut self, root_paths: &[Path]) {
+    pub fn sort_by_path(&mut self, root_paths: &[Path]) {
         self.files.sort_by(|f1, f2| {
             let p1: &Path = f1.as_ref();
             let p2: &Path = f2.as_ref();
@@ -511,10 +533,10 @@ where
             // Launch a separate thread for each device, so we can process
             // files on each device independently
             s.spawn(move |_| {
-                // Sort files by their physical location, to reduce disk seek latency
-                if device.disk_type != DiskType::SSD {
-                    files.par_sort_unstable_by_key(|f| f.file_info.location);
-                }
+                // Sort files by their physical location, to reduce disk seek latency on HDD.
+                // Additionally, files with the same id end up directly
+                // next to each other so we can avoid rehashing the same files.
+                files.par_sort_unstable_by_key(|f| f.file_info.location);
 
                 // Some devices like HDDs may benefit from different amount of parallelism
                 // depending on the access type. Therefore we chose a thread pool appropriate
@@ -533,8 +555,10 @@ where
                 // when processing 1M of files.
                 let semaphore = Arc::new(Semaphore::new(8 * thread_count));
 
-                // Run hashing on the thread-pool dedicated to the device
-                for mut f in files {
+                // Run hashing on the thread-pool dedicated to the device.
+                // Group files by their identifiers so we hash only one file per unique id.
+                for (_, fg) in &files.into_iter().group_by(|f| f.file_info.id) {
+                    let mut fg = fg.collect_vec();
                     let tx = tx.clone();
                     let guard = semaphore.clone().access_owned();
 
@@ -549,9 +573,12 @@ where
                     // when the pool has only one thread.
                     let hash_fn: &HashFn<'static> = unsafe { std::mem::transmute(hash_fn) };
                     thread_pool.spawn_fifo(move || {
-                        if let Some(hash) = hash_fn((&mut f.file_info, f.file_hash)) {
-                            f.file_hash = hash;
-                            tx.send(f).unwrap();
+                        let old_hash = fg[0].file_hash;
+                        if let Some(hash) = hash_fn((&mut fg[0].file_info, old_hash)) {
+                            for mut f in fg {
+                                f.file_hash = hash;
+                                tx.send(f).unwrap();
+                            }
                         }
                         // This forces moving the guard into this task and be released when
                         // the task is done
@@ -642,6 +669,32 @@ fn total_size<'a, T: 'a>(groups: impl IntoIterator<Item = &'a FileGroup<T>>) ->
     groups.into_iter().map(|g| g.total_size()).sum()
 }
 
+/// Returns the sum of number of files in all groups
+fn unique_file_count<'a, T>(groups: impl IntoIterator<Item = &'a FileGroup<T>>) -> usize
+where
+    T: AsRef<FileId> + 'a,
+{
+    groups.into_iter().map(|g| g.unique_count()).sum()
+}
+
+/// Returns the sum of sizes of files in all groups, including duplicates
+fn unique_file_size<'a, T: 'a>(groups: impl IntoIterator<Item = &'a FileGroup<T>>) -> FileLen
+where
+    T: AsRef<FileId> + 'a,
+{
+    groups.into_iter().map(|g| g.unique_size()).sum()
+}
+
+/// Sorts each file group by file identifiers
+fn sort_files_by_id<'a, T: 'a>(groups: impl IntoIterator<Item = &'a mut FileGroup<T>>)
+where
+    T: AsRef<FileId> + 'a,
+{
+    for g in groups.into_iter() {
+        g.sort_by_id()
+    }
+}
+
 /// Returns an estimation of the number of files matching the search criteria
 fn stage_stats(groups: &[FileGroup<FileInfo>], filter: &FileGroupFilter) -> (usize, FileLen) {
     let mut total_count = 0;
@@ -806,16 +859,20 @@ fn handle_fetch_physical_location_err(
 
 /// Transforms files by piping them to an external program and groups them by their hashes
 fn group_transformed(ctx: &GroupCtx<'_>, files: Vec<FileInfo>) -> Vec<FileGroup<FileInfo>> {
+    let mut files = files;
+    files.par_sort_unstable_by_key(|f| FileId::of(f)); // need to sort so we know unique_file_count
+
+    let groups = vec![FileGroup {
+        file_len: FileLen(0),   // doesn't matter, will be computed
+        file_hash: FileHash(0), // doesn't matter, will be computed
+        files,
+    }];
     let progress = ctx.log.progress_bar(
         &ctx.phases.format(Phase::TransformAndGroup),
-        files.len() as u64,
+        unique_file_count(&groups) as u64,
     );
     let groups = rehash(
-        vec![FileGroup {
-            file_len: FileLen(0),   // doesn't matter, will be computed
-            file_hash: FileHash(0), // doesn't matter, will be computed
-            files,
-        }],
+        groups,
         |_| true,
         |g| g.matches(&ctx.group_filter),
         &ctx.devices,
@@ -874,8 +931,11 @@ fn group_by_prefix(
     prefix_len: FileLen,
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
-    let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1;
-    let file_count = file_count(groups.iter().filter(|&g| pre_filter(g)));
+    let mut groups = groups;
+    sort_files_by_id(&mut groups);
+
+    let pre_filter = |g: &FileGroup<FileInfo>| g.unique_count() > 1;
+    let file_count = unique_file_count(groups.iter().filter(|g| pre_filter(g)));
     let progress = ctx
         .log
         .progress_bar(&ctx.phases.format(Phase::GroupByPrefix), file_count as u64);
@@ -927,10 +987,14 @@ fn group_by_suffix(
     ctx: &GroupCtx<'_>,
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
+    let mut groups = groups;
+    sort_files_by_id(&mut groups);
+
     let suffix_len = suffix_len(&ctx.devices, flat_iter(&groups));
     let suffix_threshold = suffix_threshold(&ctx.devices, flat_iter(&groups));
-    let pre_filter = |g: &FileGroup<FileInfo>| g.file_len >= suffix_threshold && g.files.len() > 1;
-    let file_count = file_count(groups.iter().filter(|&g| pre_filter(g)));
+    let pre_filter =
+        |g: &FileGroup<FileInfo>| g.file_len >= suffix_threshold && g.unique_count() > 1;
+    let file_count = unique_file_count(groups.iter().filter(|g| pre_filter(g)));
     let progress = ctx
         .log
         .progress_bar(&ctx.phases.format(Phase::GroupBySuffix), file_count as u64);
@@ -963,8 +1027,11 @@ fn group_by_contents(
     min_file_len: FileLen,
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
-    let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1 && g.file_len >= min_file_len;
-    let bytes_to_scan = total_size(groups.iter().filter(|&g| pre_filter(g)));
+    let mut groups = groups;
+    sort_files_by_id(&mut groups);
+
+    let pre_filter = |g: &FileGroup<FileInfo>| g.unique_count() > 1 && g.file_len >= min_file_len;
+    let bytes_to_scan = unique_file_size(groups.iter().filter(|g| pre_filter(g)));
     let progress = &ctx
         .log
         .bytes_progress_bar(&ctx.phases.format(Phase::GroupByContents), bytes_to_scan.0);
@@ -1084,7 +1151,7 @@ pub fn group_files(config: &GroupConfig, log: &Log) -> Result<Vec<FileGroup<File
     groups.par_sort_by_key(|g| Reverse((g.file_len, g.file_hash)));
     groups
         .par_iter_mut()
-        .for_each(|g| g.sort(&ctx.group_filter.root_paths));
+        .for_each(|g| g.sort_by_path(&ctx.group_filter.root_paths));
     Ok(groups)
 }
 
@@ -1156,7 +1223,7 @@ mod test {
     use std::fs::{create_dir, hard_link, File, OpenOptions};
     use std::io::{Read, Write};
     use std::path::PathBuf;
-    use std::sync::atomic::{AtomicBool, Ordering};
+    use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
     use std::sync::Mutex;
 
     use rand::seq::SliceRandom;
@@ -1231,6 +1298,53 @@ mod test {
         assert_ne!(result[0].files[0].path, result[1].files[0].path);
     }
 
+    #[test]
+    fn test_rehash_doesnt_hash_files_with_same_id_more_than_once() {
+        let devices = DiskDevices::default();
+        let input = vec![FileGroup {
+            file_len: FileLen(200),
+            file_hash: FileHash(0),
+            files: vec![
+                FileInfo {
+                    id: FileId {
+                        device: 1,
+                        inode: 1,
+                    },
+                    len: FileLen(200),
+                    location: 0,
+                    path: Path::from("file1"),
+                },
+                FileInfo {
+                    id: FileId {
+                        device: 1,
+                        inode: 1,
+                    },
+                    len: FileLen(200),
+                    location: 0,
+                    path: Path::from("file2"),
+                },
+            ],
+        }];
+
+        let hash_call_count = AtomicUsize::new(0);
+        let result = rehash(
+            input,
+            |_| true,
+            |_| true,
+            &devices,
+            FileAccess::Random,
+            |(fi, _)| {
+                hash_call_count.fetch_add(1, Ordering::Relaxed);
+                Some(FileHash(fi.location as u128))
+            },
+        );
+
+        assert_eq!(result.len(), 1);
+        assert_eq!(result[0].files.len(), 2);
+        assert_ne!(result[0].files[0].path, result[0].files[1].path);
+        assert_eq!(hash_call_count.load(Ordering::Relaxed), 1);
+    }
+
     /// Files hashing to same values should be placed into the same groups
     #[test]
     fn test_rehash_puts_files_with_same_hashes_to_same_groups() {


Test patch: