Repository: pkolaczk/fclones (language: rust)

Issue:
Improve initialization speed - avoid traversing sysfs
Running fclones on a relatively small directory, I noticed its performance is surprisingly bad:

```
$ time fclones group ~/Downloads/ 
[2021-06-06 18:57:22.658] fclones:  info: Started grouping
[2021-06-06 18:57:23.091] fclones:  info: Scanned 967 file entries
[2021-06-06 18:57:23.091] fclones:  info: Found 873 (2.7 GB) files matching selection criteria
[2021-06-06 18:57:23.091] fclones:  info: Found 47 (9.0 MB) candidates after grouping by size
[2021-06-06 18:57:23.092] fclones:  info: Found 47 (9.0 MB) candidates after grouping by paths and file identifiers
[2021-06-06 18:57:23.097] fclones:  info: Found 45 (8.5 MB) candidates after grouping by prefix
[2021-06-06 18:57:23.105] fclones:  info: Found 45 (8.5 MB) candidates after grouping by suffix
[2021-06-06 18:57:23.125] fclones:  info: Found 45 (8.5 MB) redundant files
<...>
real	0m0.481s
user	0m0.271s
sys	0m0.195s
```
So it takes about 0.5 sec to process a directory with less than 1000 files. I noticed that most of the time is spent in "Initializing" phase. So I ran strace:

```
$ strace -c fclones group ~/Downloads/
<...>
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ------------------
 34.07    0.349066           5     61719      1563 openat
 25.31    0.259249           4     60156           close
 23.58    0.241530           4     53660           newfstatat
  6.21    0.063639           6     10372           read
  4.34    0.044439           6      6691           readlinkat
  3.39    0.034740           7      4502         5 access
  1.92    0.019707         221        89        17 futex
  0.60    0.006150           5      1096           getdents64
<...>
```
So, it appears fclones makes 60k `openat`, 60k `close`, and 54k `newfstat`. This is very surprising.

Inspecting `openat` syscalls it seems that most of them are traversing `/sys/` filesystem. Here is a fragment of strace output (filtered by `openat` syscall):

```
openat(AT_FDCWD, "/sys/devices/pci0000:00/0000:00:14.0/usb2/2-4/2-4:1.0/uevent", O_RDONLY|O_CLOEXEC) = 5
openat(AT_FDCWD, "/run/udev/data/+usb:2-4:1.0", O_RDONLY|O_CLOEXEC) = 5
openat(AT_FDCWD, "/", O_RDONLY|O_CLOEXEC|O_PATH|O_DIRECTORY) = 5
openat(5, "sys", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "bus", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "usb", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "devices", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "1-4.4:1.0", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(5, "..", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "..", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "..", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "devices", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "pci0000:00", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "0000:00:14.0", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "usb1", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "1-4", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
openat(5, "1-4.4", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 6
openat(6, "1-4.4:1.0", O_RDONLY|O_NOFOLLOW|O_CLOEXEC|O_PATH) = 5
```



Discussion / hints:
Suspect is `get_parent_devpath_from_path` function from block-utils crate. 

https://github.com/cholcombe973/block-utils/blob/3906e66694df2e7330f3cabc3cf4ee218f4790b8/src/lib.rs#L1620


This is example stacktrace:

```
 > /usr/lib/x86_64-linux-gnu/libc-2.33.so(close+0x3b) [0x10832b]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0(udev_monitor_receive_device+0x17d8) [0x138a8]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0(udev_monitor_receive_device+0x9de2) [0x1beb2]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0() [0x71e7]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0() [0x770b]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0(udev_device_get_properties_list_entry+0x6de) [0xfb6e]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0(udev_device_get_properties_list_entry+0xb73) [0x10003]
 > /usr/lib/x86_64-linux-gnu/libudev.so.1.7.0(udev_enumerate_scan_devices+0x289) [0x114b9]
 > /home/xxx/.cargo/bin/fclones(block_utils::get_parent_devpath_from_path+0x47) [0xf14d7]
 > /home/xxx/.cargo/bin/fclones(fclones::device::DiskDevices::new+0x1dd) [0xf068d]
 > /home/xxx/.cargo/bin/fclones(fclones::group_files+0x65) [0xffbf5]
 > /home/xxx/.cargo/bin/fclones(fclones::main+0x927) [0x1769d7]
 > /home/xxx/.cargo/bin/fclones(std::sys_common::backtrace::__rust_begin_short_backtrace+0x3) [0x17b2e3]
 > /home/xxx/.cargo/bin/fclones(_ZN3std2rt10lang_start28_$u7b$$u7b$closure$u7d$$u7d$17hf452a67b20fd31b4E.llvm.9150410927396584600+0x9) [0x1770b9]
 > /home/xxx/.cargo/bin/fclones(std::rt::lang_start_internal+0x305) [0x248425]
 > /home/xxx/.cargo/bin/fclones(main+0x22) [0x176c52]
 > /usr/lib/x86_64-linux-gnu/libc-2.33.so(__libc_start_main+0xd5) [0x28565]
 > /home/xxx/.cargo/bin/fclones(_start+0x2e) [0x4b0ee]
```
Yup, I know of this problem and it happens also on my machine. Not sure why block utils has to traverse so much. Looks weird. 

Any ideas how to reliably get the physical device name knowing the partition device name on Linux?




Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 78ab947..5ac9c9c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -64,25 +64,6 @@ version = "1.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2da1976d75adbe5fbc88130ecd119529cf1cc6a93ae1546d8696ee66f0d21af1"
 
-[[package]]
-name = "block-utils"
-version = "0.10.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "399a91a5e6dfb70a74c168faeccf4f84e79b47dfaaecee275fc38bba771b8c32"
-dependencies = [
- "fstab",
- "log 0.4.14",
- "nom",
- "regex",
- "serde_json",
- "shellscript",
- "strum",
- "strum_macros",
- "thiserror",
- "udev",
- "uuid",
-]
-
 [[package]]
 name = "bstr"
 version = "0.2.16"
@@ -358,10 +339,9 @@ checksum = "4443176a9f2c162692bd3d352d745ef9413eec5782a80d8fd6f8a1ac692a07f7"
 
 [[package]]
 name = "fclones"
-version = "0.13.0"
+version = "0.14.0"
 dependencies = [
  "atomic-counter",
- "block-utils",
  "byte-unit",
  "bytesize",
  "chrono",
@@ -423,15 +403,6 @@ dependencies = [
  "winapi",
 ]
 
-[[package]]
-name = "fstab"
-version = "0.3.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "f3e033bb8a160dab4557780f3537dee55547cbc27e82687baed5b6d305a3d653"
-dependencies = [
- "log 0.3.9",
-]
-
 [[package]]
 name = "getrandom"
 version = "0.2.3"
@@ -543,34 +514,6 @@ version = "0.2.99"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "a7f823d141fe0a24df1e23b4af4e3c7ba9e5966ec514ea068c93024aa7deb765"
 
-[[package]]
-name = "libudev-sys"
-version = "0.1.4"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3c8469b4a23b962c1396b9b451dda50ef5b283e8dd309d69033475fa9b334324"
-dependencies = [
- "libc",
- "pkg-config",
-]
-
-[[package]]
-name = "log"
-version = "0.3.9"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "e19e8d5c34a3e0e2223db8e060f9e8264aeeb5c5fc64a4ee9965c062211c024b"
-dependencies = [
- "log 0.4.14",
-]
-
-[[package]]
-name = "log"
-version = "0.4.14"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "51b9bbe6c47d51fc3e1a9b945965946b4c44142ab8792c50835a980d362c2710"
-dependencies = [
- "cfg-if 1.0.0",
-]
-
 [[package]]
 name = "maplit"
 version = "1.0.2"
@@ -739,12 +682,6 @@ dependencies = [
  "regex",
 ]
 
-[[package]]
-name = "pkg-config"
-version = "0.3.19"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3831453b3449ceb48b6d9c7ad7c96d5ea673e9b470a1dc578c2ce6521230884c"
-
 [[package]]
 name = "ppv-lite86"
 version = "0.2.10"
@@ -966,12 +903,6 @@ version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b6fa3938c99da4914afedd13bf3d79bcb6c277d1b2c398d23257a304d9e1b074"
 
-[[package]]
-name = "shellscript"
-version = "0.3.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "15c0d07fa97f8d209609a1a1549bd886bd907f520f75e1c785783167a66d20c4"
-
 [[package]]
 name = "smallvec"
 version = "1.6.1"
@@ -1014,24 +945,6 @@ dependencies = [
  "syn",
 ]
 
-[[package]]
-name = "strum"
-version = "0.20.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7318c509b5ba57f18533982607f24070a55d353e90d4cae30c467cdb2ad5ac5c"
-
-[[package]]
-name = "strum_macros"
-version = "0.20.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ee8bc6b87a5112aeeab1f4a9f7ab634fe6cbefc4850006df31267f4cfb9e3149"
-dependencies = [
- "heck",
- "proc-macro2",
- "quote",
- "syn",
-]
-
 [[package]]
 name = "syn"
 version = "1.0.74"
@@ -1102,26 +1015,6 @@ dependencies = [
  "unicode-width",
 ]
 
-[[package]]
-name = "thiserror"
-version = "1.0.26"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "93119e4feac1cbe6c798c34d3a53ea0026b0b1de6a120deef895137c0529bfe2"
-dependencies = [
- "thiserror-impl",
-]
-
-[[package]]
-name = "thiserror-impl"
-version = "1.0.26"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "060d69a0afe7796bf42e9e2ff91f5ee691fb15c53d38b4b62a9a53eb23164745"
-dependencies = [
- "proc-macro2",
- "quote",
- "syn",
-]
-
 [[package]]
 name = "thread_local"
 version = "1.1.3"
@@ -1151,16 +1044,6 @@ dependencies = [
  "crunchy",
 ]
 
-[[package]]
-name = "udev"
-version = "0.5.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "048df778e99eea028c08cca7853b9b521df6948b59bb29ab8bb737c057f58e6d"
-dependencies = [
- "libc",
- "libudev-sys",
-]
-
 [[package]]
 name = "unicode-segmentation"
 version = "1.8.0"
diff --git a/Cargo.toml b/Cargo.toml
index ebddb07..fbaff5e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "fclones"
-version = "0.13.0"
+version = "0.14.0"
 description = "Finds duplicate, unique, under- or over-replicated files"
 authors = ["Piotr Kołaczkowski <pkolaczk@gmail.com>"]
 repository = "https://github.com/pkolaczk/fclones"
@@ -52,7 +52,6 @@ uuid = { version = "0.8.1", features = ["v4"] }
 num_cpus = "1.13.0"
 
 [target.'cfg(target_os = "linux")'.dependencies]
-block-utils = "0.10.1"
 fiemap = "0.1.1"
 
 [target.'cfg(unix)'.dependencies]
diff --git a/src/device.rs b/src/device.rs
index 468ac4b..c49188a 100644
--- a/src/device.rs
+++ b/src/device.rs
@@ -6,6 +6,7 @@ use std::ops::Index;
 use itertools::Itertools;
 use lazy_init::Lazy;
 use rayon::{ThreadPool, ThreadPoolBuilder};
+use regex::Regex;
 use sysinfo::{DiskExt, DiskType, System, SystemExt};
 
 use crate::config::Parallelism;
@@ -209,11 +210,16 @@ impl DiskDevices {
     /// If `name` is a disk partition, it attempts to return the disk device name the partition
     /// resides on. Otherwise, and on failures, it just returns the same `name`.
     #[cfg(target_os = "linux")]
-    fn parent_device_name(name: &OsStr) -> OsString {
-        block_utils::get_parent_devpath_from_path(&std::path::Path::new(name))
-            .unwrap_or(None)
-            .map(|p| p.into_os_string())
-            .unwrap_or_else(|| name.to_os_string())
+    fn physical_device_name(name: &OsStr) -> OsString {
+        let regex = Regex::new(r"^/dev/([fhs]d[a-z]|nvme[0-9]+).*").unwrap();
+        let name_str = name.to_string_lossy();
+        match regex.captures(name_str.as_ref()) {
+            Some(captures) => {
+                let parent = "/dev/".to_owned() + captures.get(1).unwrap().as_str();
+                OsString::from(parent)
+            }
+            None => name.to_os_string(),
+        }
     }
 
     #[cfg(not(target_os = "linux"))]
@@ -235,7 +241,7 @@ impl DiskDevices {
         result.add_device(OsString::from("default"), DiskType::Unknown(-1), pool_sizes);
 
         for d in sys.get_disks() {
-            let device_name = Self::parent_device_name(d.get_name());
+            let device_name = Self::physical_device_name(d.get_name());
             let index = result.add_device(device_name, d.get_type(), pool_sizes);
             result
                 .mount_points
@@ -297,3 +303,32 @@ impl Index<usize> for DiskDevices {
         &self.devices[index]
     }
 }
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_physical_device_name() {
+        assert_eq!(
+            DiskDevices::physical_device_name(OsStr::new("/dev/sda")),
+            OsString::from("/dev/sda")
+        );
+        assert_eq!(
+            DiskDevices::physical_device_name(OsStr::new("/dev/sda1")),
+            OsString::from("/dev/sda")
+        );
+        assert_eq!(
+            DiskDevices::physical_device_name(OsStr::new("/dev/hdc20")),
+            OsString::from("/dev/hdc")
+        );
+        assert_eq!(
+            DiskDevices::physical_device_name(OsStr::new("/dev/nvme0n1p3")),
+            OsString::from("/dev/nvme0")
+        );
+        assert_eq!(
+            DiskDevices::physical_device_name(OsStr::new("/dev/unknown")),
+            OsString::from("/dev/unknown")
+        );
+    }
+}


Test patch: