file manager
git clone https://git.lucas.co/cce-files.git
src/services/scan.rs (16.3K)
1 //! Recursive directory scan feeding the Space (treemap) view.
2 //!
3 //! Unlike `read_directory_internal`, which reads one level and reports each
4 //! entry's own size, this walks the whole subtree and gives every directory
5 //! the sum of what it contains — the number a treemap's area encodes. It runs
6 //! on the `FsService` thread like every other request; the app sees it only as
7 //! progress messages followed by a completed tree.
8
9 use std::collections::{HashMap, HashSet};
10 use std::path::{Path, PathBuf};
11 use std::os::unix::fs::MetadataExt;
12 use std::sync::atomic::{AtomicBool, Ordering};
13 use std::time::{Duration, Instant};
14
15 /// Deepest nesting the walk will descend. Ordinary trees are nowhere near
16 /// this; the cap exists so a pathological one cannot overflow the recursion
17 /// stack.
18 const MAX_DEPTH: u32 = 64;
19
20 /// How often a scan in flight reports what it has counted so far. Short
21 /// enough that the progress line moves, long enough that a fast tree is not
22 /// mostly channel traffic.
23 const PROGRESS_INTERVAL: Duration = Duration::from_millis(150);
24
25 /// One node of a scanned tree. `size` is the recursive total for a directory
26 /// and the apparent size for a file.
27 ///
28 /// Nodes deliberately carry no `PathBuf` — a large tree is millions of nodes,
29 /// and only the few thousand tiles that survive layout culling ever need a
30 /// path. The Space page rebuilds those from the names along the way down.
31 #[derive(Debug, Clone, Default)]
32 pub struct TreeNode {
33 pub name: String,
34 pub size: u64,
35 pub is_dir: bool,
36 /// Sorted descending by `size` — the order the squarified layout wants,
37 /// established once here rather than per frame.
38 pub children: Vec<TreeNode>,
39 }
40
41 #[derive(Debug, Clone, Default)]
42 pub struct ScanResult {
43 pub tree: TreeNode,
44 pub files: u64,
45 pub dirs: u64,
46 /// True when the scan stopped early because its cancel flag was raised —
47 /// the tree is a partial one and should be discarded, not drawn.
48 pub cancelled: bool,
49 }
50
51 struct Walker<'a> {
52 /// Mount points the walk may descend into although they sit on another
53 /// device than their parent — see [`crossable`]. Any other change of
54 /// device is skipped, so scanning `/` does not wander into `/proc`, `/sys`,
55 /// a tmpfs, or a backup drive.
56 crossable: HashSet<PathBuf>,
57 /// Every directory entered, by (device, inode). Directories have no hard
58 /// links, so a second sighting is a bind mount: skipped, it is counted once
59 /// and cannot loop the walk back into itself.
60 seen: HashSet<(u64, u64)>,
61 cancel: &'a AtomicBool,
62 files: u64,
63 dirs: u64,
64 bytes: u64,
65 on_progress: &'a mut dyn FnMut(u64, u64),
66 last_report: Instant,
67 }
68
69 impl Walker<'_> {
70 /// `dev` is the device `dir` lies on; a child on any other is a mount.
71 fn walk(&mut self, dir: &Path, name: String, depth: u32, dev: u64) -> TreeNode {
72 let mut node = TreeNode { name, size: 0, is_dir: true, children: Vec::new() };
73 if depth >= MAX_DEPTH || self.cancel.load(Ordering::Relaxed) {
74 return node;
75 }
76 let Ok(rd) = std::fs::read_dir(dir) else {
77 // Unreadable directory (permissions, races) contributes nothing
78 // rather than aborting the scan around it.
79 return node;
80 };
81
82 for entry in rd.filter_map(|e| e.ok()) {
83 if self.cancel.load(Ordering::Relaxed) {
84 break;
85 }
86 // `DirEntry::metadata` does not traverse symlinks, which is what we
87 // want twice over: a link cannot pull its target's bytes into this
88 // subtree's total, and cannot loop the walk back into itself.
89 let Ok(meta) = entry.metadata() else { continue };
90 let ft = meta.file_type();
91 if ft.is_symlink() {
92 continue;
93 }
94
95 let child_name = entry.file_name().to_string_lossy().into_owned();
96 if ft.is_dir() {
97 let path = entry.path();
98 if meta.dev() != dev && !self.crossable.contains(&path) {
99 continue;
100 }
101 if !self.seen.insert((meta.dev(), meta.ino())) {
102 continue;
103 }
104 self.dirs += 1;
105 let child = self.walk(&path, child_name, depth + 1, meta.dev());
106 node.size += child.size;
107 node.children.push(child);
108 } else if ft.is_file() && meta.dev() == dev {
109 let size = meta.len();
110 self.files += 1;
111 self.bytes += size;
112 node.size += size;
113 node.children.push(TreeNode {
114 name: child_name,
115 size,
116 is_dir: false,
117 children: Vec::new(),
118 });
119 }
120 // Sockets, fifos, and device nodes occupy no meaningful space and
121 // are dropped entirely, as is a file bind-mounted from elsewhere.
122 self.maybe_report();
123 }
124
125 node.children.sort_unstable_by(|a, b| b.size.cmp(&a.size));
126 node
127 }
128
129 fn maybe_report(&mut self) {
130 if self.last_report.elapsed() >= PROGRESS_INTERVAL {
131 self.last_report = Instant::now();
132 (self.on_progress)(self.files, self.bytes);
133 }
134 }
135 }
136
137 /// One line of `/proc/self/mountinfo`, as much as the walk needs.
138 #[derive(Debug, Clone, PartialEq)]
139 struct Mount {
140 point: PathBuf,
141 /// What is mounted: a device path for a disk filesystem, a bare word
142 /// (`tmpfs`, `proc`) or `host:/path` for anything else.
143 source: String,
144 }
145
146 /// Parse mountinfo: `id parent maj:min root POINT opts [optional...] - fstype SOURCE superopts`.
147 /// The optional fields vary in number, so the source is found after the ` - `.
148 fn parse_mountinfo(text: &str) -> Vec<Mount> {
149 text.lines()
150 .filter_map(|line| {
151 let (left, right) = line.split_once(" - ")?;
152 let point = left.split(' ').nth(4)?;
153 let source = right.split(' ').nth(1)?;
154 Some(Mount { point: unescape_mount(point), source: unescape_mount(source).to_string_lossy().into_owned() })
155 })
156 .collect()
157 }
158
159 /// mountinfo writes a space, tab, newline or backslash in a path as a
160 /// three-digit octal escape (`\040`).
161 fn unescape_mount(s: &str) -> PathBuf {
162 use std::os::unix::ffi::OsStringExt;
163 let b = s.as_bytes();
164 let mut out = Vec::with_capacity(b.len());
165 let mut i = 0;
166 while i < b.len() {
167 if b[i] == b'\\' && i + 3 < b.len() && b[i + 1..i + 4].iter().all(|c| (b'0'..=b'7').contains(c)) {
168 out.push((b[i + 1] - b'0') * 64 + (b[i + 2] - b'0') * 8 + (b[i + 3] - b'0'));
169 i += 4;
170 } else {
171 out.push(b[i]);
172 i += 1;
173 }
174 }
175 PathBuf::from(std::ffi::OsString::from_vec(out))
176 }
177
178 /// The disk a mount source lives on: the device itself, a partition's
179 /// parent, and through device-mapper (LUKS, LVM) the disk underneath.
180 /// `None` for anything that is not a block device — tmpfs, proc, a share.
181 fn disk_of(source: &str) -> Option<String> {
182 if !source.starts_with("/dev/") {
183 return None;
184 }
185 let dev = std::fs::canonicalize(source).ok()?;
186 disk_of_block(dev.file_name()?.to_str()?, 0)
187 }
188
189 fn disk_of_block(name: &str, depth: u32) -> Option<String> {
190 let sys = Path::new("/sys/class/block").join(name);
191 if !sys.exists() {
192 return None;
193 }
194 // A mapped device (dm-N) names what it is built on under `slaves/`.
195 if depth < 8 {
196 let slave = std::fs::read_dir(sys.join("slaves")).ok().and_then(|mut rd| rd.next()).and_then(|e| e.ok());
197 if let Some(slave) = slave {
198 return disk_of_block(&slave.file_name().to_string_lossy(), depth + 1);
199 }
200 }
201 // A partition's sysfs node sits inside its disk's.
202 if sys.join("partition").exists() {
203 let real = std::fs::canonicalize(&sys).ok()?;
204 return Some(real.parent()?.file_name()?.to_string_lossy().into_owned());
205 }
206 Some(name.to_string())
207 }
208
209 /// The mount points a scan of `root` may enter: every one whose topmost
210 /// mount is on the same disk as the mount `root` lies in.
211 ///
212 /// Comparing devices alone stopped at every mount, and on a btrfs layout
213 /// (`@` at `/`, `@home` at `/home`) each subvolume is its own device: a scan
214 /// of `/` left out `/home`, most of the disk, and a separate `/home`
215 /// partition went the same way. Comparing disks keeps those and still keeps
216 /// out what the device check was for — `/proc`, `/sys`, tmpfs, network
217 /// shares, a backup drive. Nested btrfs subvolumes that are not mounted
218 /// (snapshots, container layers) have a device of their own and no entry
219 /// here, so they stay out, and a snapshot is not counted as a second copy.
220 fn crossable(mounts: &[Mount], root: &Path, disk_of: impl Fn(&str) -> Option<String>) -> HashSet<PathBuf> {
221 // The last mount at a point is the one on top, the one the walk sees.
222 let mut top: HashMap<&Path, &str> = HashMap::new();
223 for m in mounts {
224 top.insert(&m.point, &m.source);
225 }
226 let Some((home, home_src)) = top
227 .iter()
228 .filter(|(p, _)| root.starts_with(p))
229 .max_by_key(|(p, _)| p.components().count())
230 else {
231 return HashSet::new();
232 };
233 let Some(disk) = disk_of(home_src) else {
234 return HashSet::new();
235 };
236 let mut disks: HashMap<&str, Option<String>> = HashMap::new();
237 top.iter()
238 .filter(|(p, _)| p != &home)
239 .filter(|(_, src)| disks.entry(src).or_insert_with(|| disk_of(src)).as_deref() == Some(disk.as_str()))
240 .map(|(p, _)| p.to_path_buf())
241 .collect()
242 }
243
244 /// Walk `root`, returning its tree with directory sizes summed.
245 ///
246 /// Returns `None` when `root` is not a readable directory. `cancel` is polled
247 /// per entry, so a superseded scan stops within a directory rather than
248 /// running to completion unwatched.
249 pub fn scan(
250 root: &Path,
251 cancel: &AtomicBool,
252 on_progress: &mut dyn FnMut(u64, u64),
253 ) -> Option<ScanResult> {
254 // The root is stat'd through symlinks — the user may well have navigated
255 // to one — while everything beneath it is not.
256 let meta = std::fs::metadata(root).ok()?;
257 if !meta.is_dir() {
258 return None;
259 }
260 // Mount points are canonical, so the walk's paths must be too.
261 let real = std::fs::canonicalize(root).ok()?;
262 let mountinfo = std::fs::read_to_string("/proc/self/mountinfo").unwrap_or_default();
263
264 let name = root
265 .file_name()
266 .map(|n| n.to_string_lossy().into_owned())
267 .unwrap_or_else(|| root.to_string_lossy().into_owned());
268
269 let mut walker = Walker {
270 crossable: crossable(&parse_mountinfo(&mountinfo), &real, disk_of),
271 seen: HashSet::from([(meta.dev(), meta.ino())]),
272 cancel,
273 files: 0,
274 dirs: 0,
275 bytes: 0,
276 on_progress,
277 last_report: Instant::now(),
278 };
279 let tree = walker.walk(&real, name, 0, meta.dev());
280
281 Some(ScanResult {
282 tree,
283 files: walker.files,
284 dirs: walker.dirs,
285 cancelled: cancel.load(Ordering::Relaxed),
286 })
287 }
288
289 #[cfg(test)]
290 mod tests {
291 use super::*;
292 use std::fs;
293
294 /// A scratch tree: `<tmp>/cce_scan_test_<nanos>/`.
295 fn scratch(tag: &str) -> std::path::PathBuf {
296 let nanos = std::time::SystemTime::now()
297 .duration_since(std::time::UNIX_EPOCH)
298 .unwrap()
299 .as_nanos();
300 let dir = std::env::temp_dir().join(format!("cce_scan_test_{tag}_{nanos}"));
301 fs::create_dir_all(&dir).unwrap();
302 dir
303 }
304
305 #[test]
306 fn sums_sizes_recursively_and_sorts_descending() {
307 let root = scratch("sum");
308 fs::write(root.join("small.txt"), vec![b'a'; 10]).unwrap();
309 let sub = root.join("sub");
310 fs::create_dir(&sub).unwrap();
311 fs::write(sub.join("big.bin"), vec![b'b'; 5000]).unwrap();
312 fs::write(sub.join("mid.bin"), vec![b'c'; 500]).unwrap();
313
314 let cancel = AtomicBool::new(false);
315 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
316
317 assert_eq!(res.files, 3);
318 assert_eq!(res.dirs, 1);
319 assert!(!res.cancelled);
320 // The directory carries what it contains, not its own inode size.
321 assert_eq!(res.tree.size, 5510);
322
323 // Children sorted descending: sub (5500) before small.txt (10).
324 assert_eq!(res.tree.children.len(), 2);
325 assert_eq!(res.tree.children[0].name, "sub");
326 assert_eq!(res.tree.children[0].size, 5500);
327 assert!(res.tree.children[0].is_dir);
328 assert_eq!(res.tree.children[1].name, "small.txt");
329
330 // ...and so are the grandchildren.
331 let sub_node = &res.tree.children[0];
332 assert_eq!(sub_node.children[0].name, "big.bin");
333 assert_eq!(sub_node.children[1].name, "mid.bin");
334
335 fs::remove_dir_all(&root).unwrap();
336 }
337
338 #[test]
339 fn symlinks_are_skipped_not_followed() {
340 let root = scratch("link");
341 let real = root.join("real");
342 fs::create_dir(&real).unwrap();
343 fs::write(real.join("data.bin"), vec![b'x'; 1000]).unwrap();
344 // A link back to the root would loop the walk if it were followed, and
345 // a link to the sibling directory would double-count its bytes.
346 std::os::unix::fs::symlink(&root, root.join("loop")).unwrap();
347 std::os::unix::fs::symlink(&real, root.join("alias")).unwrap();
348
349 let cancel = AtomicBool::new(false);
350 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
351
352 assert_eq!(res.files, 1);
353 assert_eq!(res.tree.size, 1000);
354 assert_eq!(res.tree.children.len(), 1, "only `real` — both links dropped");
355
356 fs::remove_dir_all(&root).unwrap();
357 }
358
359 #[test]
360 fn cancel_flag_stops_the_walk() {
361 let root = scratch("cancel");
362 for i in 0..50 {
363 fs::write(root.join(format!("f{i}")), vec![b'z'; 100]).unwrap();
364 }
365
366 // Already-raised flag: the walk bails before reading any entry.
367 let cancel = AtomicBool::new(true);
368 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
369
370 assert!(res.cancelled);
371 assert_eq!(res.files, 0);
372 assert!(res.tree.children.is_empty());
373
374 fs::remove_dir_all(&root).unwrap();
375 }
376
377 #[test]
378 fn mountinfo_parses_past_optional_fields_and_escapes() {
379 let text = "\
380 29 1 0:31 /@ / rw,relatime shared:1 - btrfs /dev/nvme0n1p2 rw,ssd
381 40 29 0:50 /@home /home rw,relatime shared:2 master:7 - btrfs /dev/nvme0n1p2 rw
382 41 29 259:1 / /mnt/my\\040drive rw - ext4 /dev/sdb1 rw
383 ";
384 let m = parse_mountinfo(text);
385 assert_eq!(m.len(), 3);
386 assert_eq!(m[1], Mount { point: "/home".into(), source: "/dev/nvme0n1p2".into() });
387 assert_eq!(m[2].point, PathBuf::from("/mnt/my drive"));
388 }
389
390 #[test]
391 fn mounts_on_the_scanned_disk_are_crossed_and_nothing_else() {
392 let mount = |p: &str, s: &str| Mount { point: p.into(), source: s.into() };
393 let mounts = vec![
394 mount("/", "/dev/nvme0n1p2"),
395 mount("/home", "/dev/nvme0n1p2"), // btrfs subvolume
396 mount("/boot", "/dev/nvme0n1p1"), // another partition, same disk
397 mount("/mnt/backup", "/dev/sdb1"), // another disk
398 mount("/tmp", "tmpfs"),
399 mount("/proc", "proc"),
400 mount("/srv/share", "nas:/export"),
401 mount("/home/me/cache", "/dev/nvme0n1p2"),
402 mount("/home/me/cache", "tmpfs"), // stacked on top: the walk sees this
403 ];
404 let disk = |src: &str| match src {
405 "/dev/nvme0n1p1" | "/dev/nvme0n1p2" => Some("nvme0n1".to_string()),
406 "/dev/sdb1" => Some("sdb".to_string()),
407 _ => None,
408 };
409
410 let got = crossable(&mounts, Path::new("/"), disk);
411 let want: HashSet<PathBuf> = ["/home", "/boot"].iter().map(PathBuf::from).collect();
412 assert_eq!(got, want);
413
414 // Scanning inside the backup drive crosses nothing on the system disk.
415 assert!(crossable(&mounts, Path::new("/mnt/backup/x"), disk).is_empty());
416 // Nor does a scan rooted on a tmpfs.
417 assert!(crossable(&mounts, Path::new("/tmp/x"), disk).is_empty());
418 }
419
420 #[test]
421 fn non_directory_root_is_rejected() {
422 let root = scratch("file");
423 let file = root.join("plain.txt");
424 fs::write(&file, b"hello").unwrap();
425
426 let cancel = AtomicBool::new(false);
427 assert!(scan(&file, &cancel, &mut |_, _| {}).is_none());
428
429 fs::remove_dir_all(&root).unwrap();
430 }
431 }