voom 0.14.1

Fast, safe, parallel build-artifact pruning across every major language ecosystem
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
//! Measuring and removing whole trees through directory descriptors.
//!
//! Sizing and removal are the stages that touch every entry of every artifact, and on a machine
//! with an endpoint-security agent every `open` is a round trip through it. Measured over Bazel
//! output bases of one to three and a half million entries each, under two such agents: `std`'s
//! path-based `read_dir` plus an `fstatat` per entry on eighteen threads ran at 38,000 entries a
//! second cold; descriptor-relative opens with `getattrlistbulk(2)` on sixty-four ran at 119,000.
//!
//! Three things carry that, and each is a system primitive rather than a cleverness:
//!
//! - every directory is opened with `openat` against its parent's descriptor, so the kernel
//!   resolves one component rather than the whole path again;
//! - on Apple platforms a directory's names, types, sizes, link counts and inodes come back in
//!   bulk, one call per buffer rather than one `fstatat` per entry ([`sys`]);
//! - the walk fans out across `rayon` *inside* one tree, because a sweep's trees are wildly
//!   uneven and the largest would otherwise run on one thread.
//!
//! Removal is the same walk with `unlinkat` in it, post-order, and it counts what it frees as it
//! goes — so a real run never has to measure a tree before taking it.
//!
//! Neither walk follows a symlink or crosses onto another filesystem: a directory is opened
//! `O_NOFOLLOW`, a symlink is unlinked as the link it is, and a directory with something mounted
//! on it is left in place and reported.

mod sys;

use std::ffi::{CStr, CString};
use std::os::fd::{AsRawFd, OwnedFd, RawFd};
use std::path::Path;
use std::sync::Mutex;
use std::sync::atomic::{AtomicU64, Ordering};
use std::time::Duration;

use rayon::prelude::*;

use crate::size::{Links, Measured};
use sys::Kind;
#[cfg(target_vendor = "apple")]
use sys::USER_IMMUTABLE;

/// How many recursive levels are divided across `rayon` before the walk goes serial.
///
/// Removal stores narrow chains on an explicit stack, spending this budget only on branches;
/// a cache's wide subtree can sit below a long prefix. Sizing still counts directory levels.
/// Below the bound both walks hold one descriptor per level.
const FANOUT_DEPTH: u32 = 10;

/// The owner bits a directory needs to be listed and emptied.
const DIRECTORY_BITS: u32 = 0o700;

/// Amortizes rayon scheduling while allowing a flat cache to use the removal pool.
const UNLINK_BATCH: usize = 64;

/// Small directories leave the parallel file batches to larger flat caches.
const PARALLEL_FILES: usize = 256;

/// Waits before emptying a directory again after something wrote into it during its removal.
const RESWEEP_BACKOFF: [Duration; 3] = [
    Duration::from_millis(10),
    Duration::from_millis(50),
    Duration::from_millis(250),
];

/// Waits between attempts to open a directory while the process is out of descriptors.
const EXHAUSTED_BACKOFF: [Duration; 4] = [
    Duration::from_millis(1),
    Duration::from_millis(5),
    Duration::from_millis(25),
    Duration::from_millis(100),
];

/// Opens `name` under `parent`, waiting briefly if the process has run out of descriptors.
///
/// Every worker holds one descriptor per level it is inside, so a wide fan-out over a deep tree
/// can briefly meet the limit; whichever sibling finishes first hands some back.
fn open(parent: RawFd, name: &CStr) -> std::io::Result<OwnedFd> {
    let mut waits = EXHAUSTED_BACKOFF.iter();
    loop {
        match sys::open_dir_at(parent, name) {
            Err(error) if matches!(error.raw_os_error(), Some(libc::EMFILE | libc::ENFILE)) => {
                let Some(wait) = waits.next() else { return Err(error) };
                std::thread::sleep(*wait);
            }
            result => return result,
        }
    }
}

/// The recursive size of a directory's contents, below the directory itself.
///
/// The directory's own bytes are the caller's to count, from whatever `stat` it already holds.
pub(crate) fn measure_below(path: &Path) -> Measured {
    let Ok(fd) = sys::open_dir(path) else {
        return Measured {
            bytes: 0,
            unreadable: 1,
        };
    };
    let Ok(own) = sys::stat_fd(fd.as_raw_fd()) else {
        return Measured {
            bytes: 0,
            unreadable: 1,
        };
    };
    measure_open(&fd, own.dev, FANOUT_DEPTH, &Links::default())
}

/// One directory's entries counted, and the subdirectories still to visit.
fn tally(fd: &OwnedFd, dev: u64, seen: &Links) -> (Measured, Vec<CString>) {
    let Ok(listing) = sys::list(fd) else {
        return (
            Measured {
                bytes: 0,
                unreadable: 1,
            },
            Vec::new(),
        );
    };
    let mut total = Measured {
        bytes: 0,
        unreadable: listing.unreadable,
    };
    let mut subdirectories = Vec::new();
    for entry in listing.entries {
        if !seen.counted_inode(entry.dev, entry.ino, entry.nlink) {
            total.bytes += entry.bytes;
        }
        // Another filesystem's contents are not this tree's, and its mount point is what
        // `--one-file-system` exists to stop at.
        if entry.kind == Kind::Dir && !entry.mount_point && entry.dev == dev {
            subdirectories.push(entry.name);
        }
    }
    (total, subdirectories)
}

fn measure_open(fd: &OwnedFd, dev: u64, fanout: u32, seen: &Links) -> Measured {
    let (total, subdirectories) = tally(fd, dev, seen);
    if fanout == 0 {
        return total + measure_serially(fd, subdirectories, dev, seen);
    }
    total
        + subdirectories
            .par_iter()
            .map(|name| match open(fd.as_raw_fd(), name) {
                Ok(child) => measure_open(&child, dev, fanout - 1, seen),
                Err(error) if error.kind() == std::io::ErrorKind::NotFound => Measured::default(),
                Err(_) => Measured {
                    bytes: 0,
                    unreadable: 1,
                },
            })
            .reduce(Measured::default, |left, right| left + right)
}

/// Everything below `names`, on one thread, with an explicit stack of open descriptors.
fn measure_serially(fd: &OwnedFd, names: Vec<CString>, dev: u64, seen: &Links) -> Measured {
    let mut total = Measured::default();
    let mut stack: Vec<(OwnedFd, Vec<CString>)> = Vec::new();
    let mut first = names;
    loop {
        let (parent, next) = if let Some((dir, pending)) = stack.last_mut() {
            let Some(next) = pending.pop() else {
                stack.pop();
                continue;
            };
            (dir.as_raw_fd(), next)
        } else {
            let Some(next) = first.pop() else { return total };
            (fd.as_raw_fd(), next)
        };
        match open(parent, &next) {
            Ok(child) => {
                let (measured, subdirectories) = tally(&child, dev, seen);
                total += measured;
                stack.push((child, subdirectories));
            }
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
            Err(_) => total.unreadable += 1,
        }
    }
}

/// What a removal took, and the first thing that stopped it taking the rest.
#[derive(Debug, Default)]
pub(crate) struct Removed {
    /// Bytes unlinked, counted the way [`measure_below`] counts them.
    pub(crate) freed: u64,
    /// The first failure. The walk does not stop at it: everything else that can go, goes.
    pub(crate) error: Option<std::io::Error>,
}

/// Removes the directory at `path` and everything below it.
///
/// `repair` is `--force`: an entry that cannot be unlinked because its directory is read-only,
/// or carries a user-immutable flag, has the owner's bits restored and is retried. Only ever
/// below `path` and on `path` itself — never its parent, so an artifact held by a read-only
/// parent is reported rather than taken — and never on a file another hard link also names.
pub(crate) fn remove_dir(path: &Path, repair: bool) -> Removed {
    let (Some(parent), Some(name)) = (path.parent(), path.file_name()) else {
        return Removed {
            freed: 0,
            error: Some(std::io::Error::from(std::io::ErrorKind::InvalidInput)),
        };
    };
    let result = (|| {
        use std::os::unix::ffi::OsStrExt;
        let parent = sys::open_dir(parent)?;
        let name = CString::new(name.as_bytes())?;
        let own = sys::stat_at(parent.as_raw_fd(), &name)?;
        if own.kind != Kind::Dir {
            return Err(std::io::Error::from(std::io::ErrorKind::NotADirectory));
        }
        let remover = Remover {
            repair,
            dev: own.dev,
            seen: Links::default(),
            freed: AtomicU64::new(0),
            error: Mutex::new(None),
        };
        let root = Sub {
            name,
            bytes: own.bytes,
            flags: own.flags,
        };
        remover.remove(parent.as_raw_fd(), root, false, FANOUT_DEPTH);
        Ok(remover.finish())
    })();
    result.unwrap_or_else(|error| Removed {
        freed: 0,
        error: Some(error),
    })
}

/// A subdirectory still to remove, with what its parent's listing said about it.
#[derive(Debug)]
struct Sub {
    name: CString,
    bytes: u64,
    flags: u32,
}

/// A directory open for removal: its descriptor, its name in its parent, and what is left.
struct Frame {
    fd: OwnedFd,
    sub: Sub,
    pending: Vec<Sub>,
    /// Whether a child could not be removed at all — a mount point or a directory on another
    /// filesystem. The directory can never be emptied, so the re-sweep cannot help it.
    blocked: bool,
}

struct Remover {
    repair: bool,
    dev: u64,
    seen: Links,
    freed: AtomicU64,
    error: Mutex<Option<std::io::Error>>,
}

/// Whether an error is the kind a repair can answer.
fn denied(error: &std::io::Error) -> bool {
    matches!(error.raw_os_error(), Some(libc::EACCES | libc::EPERM))
}

impl Remover {
    fn finish(self) -> Removed {
        Removed {
            freed: self.freed.into_inner(),
            error: self
                .error
                .into_inner()
                .unwrap_or_else(std::sync::PoisonError::into_inner),
        }
    }

    /// Keeps the first failure; later ones are usually its consequences (a parent that is not
    /// empty because a child could not go).
    fn fail(&self, error: std::io::Error) {
        if let Ok(mut slot) = self.error.lock()
            && slot.is_none()
        {
            *slot = Some(error);
        }
    }

    /// The bytes for an inode this removal has not counted yet, or zero for a repeat.
    ///
    /// [`Links::counted_inode`] answers `true` for a hard link whose inode is already counted, so
    /// only an uncounted one contributes.
    fn counted(&self, dev: u64, ino: u64, nlink: u64, bytes: u64) -> u64 {
        if self.seen.counted_inode(dev, ino, nlink) {
            0
        } else {
            bytes
        }
    }

    /// Adds bytes a directory freed to the local and process-wide totals in one update each.
    ///
    /// Batched per directory rather than per unlinking entry: the process-wide counter is a single
    /// atomic, and one contended read-modify-write per file does not scale across removal workers.
    fn add_freed(&self, bytes: u64) {
        if bytes > 0 {
            self.freed.fetch_add(bytes, Ordering::Relaxed);
            crate::delete::note_freed(bytes);
        }
    }

    /// Restores the owner's bits on an open directory and clears its user-immutable flags.
    fn repair_dir(fd: RawFd) {
        if let Ok(own) = sys::stat_fd(fd) {
            sys::add_mode_fd(fd, own.mode, DIRECTORY_BITS);
            sys::clear_immutable_fd(fd, own.flags);
        }
    }

    /// Removes one directory below `parent`, fanning out over its subdirectories.
    ///
    /// `parent_repairable` is false only for the artifact itself, whose parent is outside it.
    fn remove(&self, parent: RawFd, sub: Sub, parent_repairable: bool, fanout: u32) {
        let mut prefix: Vec<Frame> = Vec::new();
        let mut next = Some(sub);
        while let Some(sub) = next.take() {
            let current_parent = prefix.last().map_or(parent, |frame| frame.fd.as_raw_fd());
            let Some(mut frame) = self.open_and_empty(current_parent, sub) else {
                break;
            };
            if fanout > 0 && frame.pending.len() == 1 {
                next = frame.pending.pop();
                prefix.push(frame);
                continue;
            }
            self.remove_branch(current_parent, frame, !prefix.is_empty() || parent_repairable, fanout);
            break;
        }
        while let Some(Frame { fd, sub, blocked, .. }) = prefix.pop() {
            drop(fd);
            let current_parent = prefix.last().map_or(parent, |frame| frame.fd.as_raw_fd());
            self.remove_empty(current_parent, &sub, !prefix.is_empty() || parent_repairable, blocked);
        }
    }

    /// Spends a recursion level only where siblings can share the workers.
    fn remove_branch(&self, parent: RawFd, frame: Frame, parent_repairable: bool, fanout: u32) {
        let Frame {
            fd,
            sub,
            pending,
            blocked,
        } = frame;
        if fanout == 0 {
            self.remove_serially(&fd, pending);
        } else {
            pending
                .into_par_iter()
                .for_each(|child| self.remove(fd.as_raw_fd(), child, true, fanout - 1));
        }
        drop(fd);
        self.remove_empty(parent, &sub, parent_repairable, blocked);
    }

    /// Post-order removal on one thread, holding one descriptor per level.
    fn remove_serially(&self, fd: &OwnedFd, subdirectories: Vec<Sub>) {
        let mut first = subdirectories;
        let mut stack: Vec<Frame> = Vec::new();
        loop {
            let next = match stack.last_mut() {
                Some(frame) => frame.pending.pop().map(|next| (frame.fd.as_raw_fd(), next)),
                None => match first.pop() {
                    Some(next) => Some((fd.as_raw_fd(), next)),
                    None => return,
                },
            };
            if let Some((parent, sub)) = next {
                if let Some(frame) = self.open_and_empty(parent, sub) {
                    stack.push(frame);
                }
                continue;
            }
            let Some(Frame {
                fd: done, sub, blocked, ..
            }) = stack.pop()
            else {
                return;
            };
            drop(done);
            let parent = stack.last().map_or(fd.as_raw_fd(), |frame| frame.fd.as_raw_fd());
            self.remove_empty(parent, &sub, true, blocked);
        }
    }

    /// Opens a directory and unlinks every non-directory in it, returning what is left to do.
    fn open_and_empty(&self, parent: RawFd, sub: Sub) -> Option<Frame> {
        let fd = match open(parent, &sub.name) {
            Ok(fd) => fd,
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => return None,
            Err(error) if self.repair && denied(&error) => {
                // A directory missing its owner's read or search bit cannot be opened to be
                // emptied. Its mode belongs to it, inside the artifact, so it is restored.
                if let Ok(own) = sys::stat_at(parent, &sub.name)
                    && own.kind == Kind::Dir
                {
                    sys::add_mode_at(parent, &sub.name, own.mode, DIRECTORY_BITS);
                }
                match open(parent, &sub.name) {
                    Ok(fd) => fd,
                    Err(error) => {
                        self.fail(error);
                        return None;
                    }
                }
            }
            Err(error) => {
                self.fail(error);
                return None;
            }
        };

        let listing = match sys::list(&fd) {
            Ok(listing) => listing,
            Err(error) => {
                self.fail(error);
                return None;
            }
        };
        if listing.unreadable > 0 {
            self.fail(std::io::Error::other(format!(
                "{} entries could not be read",
                listing.unreadable
            )));
        }

        let mut pending = Vec::new();
        let mut files = Vec::new();
        let mut blocked = false;
        for entry in listing.entries {
            if entry.kind == Kind::Dir {
                if entry.mount_point || entry.dev != self.dev {
                    self.fail(std::io::Error::other(format!(
                        "{} is a mount point; voom does not remove across filesystems",
                        entry.name.to_string_lossy()
                    )));
                    blocked = true;
                    continue;
                }
                pending.push(Sub {
                    name: entry.name,
                    bytes: entry.bytes,
                    flags: entry.flags,
                });
                continue;
            }
            files.push(entry);
        }
        self.unlink_files(&fd, &files);
        Some(Frame {
            fd,
            sub,
            pending,
            blocked,
        })
    }

    /// Files in one directory share the bounded removal pool, including a flat cache.
    fn unlink_files(&self, fd: &OwnedFd, files: &[sys::Entry]) {
        // Caches often have thousands of files directly inside one directory. Fanning out only
        // over subdirectories leaves that whole directory on one worker regardless of `-j`.
        let unlink_batch = |batch: &[sys::Entry]| {
            let mut repaired = false;
            let mut freed = 0;
            for entry in batch {
                match self.unlink(fd, entry, &mut repaired) {
                    Ok(()) => freed += self.counted(entry.dev, entry.ino, entry.nlink, entry.bytes),
                    Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
                    Err(error) => self.fail(error),
                }
            }
            self.add_freed(freed);
        };
        if cfg!(target_vendor = "apple") && files.len() < PARALLEL_FILES {
            unlink_batch(files);
        } else {
            files.par_chunks(UNLINK_BATCH).for_each(unlink_batch);
        }
    }

    /// Unlinks one non-directory, repairing its directory once if `--force` allows it.
    fn unlink(&self, dir: &OwnedFd, entry: &sys::Entry, repaired: &mut bool) -> std::io::Result<()> {
        let error = match sys::unlink_at(dir.as_raw_fd(), &entry.name, false) {
            Err(error) if self.repair && denied(&error) => error,
            result => return result,
        };
        if !*repaired {
            *repaired = true;
            Self::repair_dir(dir.as_raw_fd());
            match sys::unlink_at(dir.as_raw_fd(), &entry.name, false) {
                Err(error) if denied(&error) => {}
                result => return result,
            }
        }
        // A flag belongs to the inode, which a second hard link names from somewhere voom was
        // never given; clearing it there would widen a file outside the artifact.
        #[cfg(target_vendor = "apple")]
        if entry.flags & USER_IMMUTABLE != 0 && entry.nlink <= 1 {
            sys::clear_immutable_at(dir.as_raw_fd(), &entry.name, entry.flags);
            return sys::unlink_at(dir.as_raw_fd(), &entry.name, false);
        }
        Err(error)
    }

    /// Removes a directory that has just been emptied.
    ///
    /// A directory something wrote into between being emptied and being unlinked is emptied
    /// again, a few times, before it is reported. A real sweep met this on `go-build`, `uv` and
    /// Homebrew caches that other work was using while they went; each left a residue that the
    /// next run had to take.
    fn remove_empty(&self, parent: RawFd, sub: &Sub, parent_repairable: bool, mut blocked: bool) {
        let mut result = self.unlink_empty(parent, sub, parent_repairable);
        for wait in RESWEEP_BACKOFF {
            // A child that cannot go at all — a mount point, a directory on another filesystem —
            // means this directory can never be emptied, so re-emptying it only spends the
            // backoff before reporting the same failure.
            if blocked || !matches!(&result, Err(error) if error.kind() == std::io::ErrorKind::DirectoryNotEmpty) {
                break;
            }
            std::thread::sleep(wait);
            let again = Sub {
                name: sub.name.clone(),
                bytes: sub.bytes,
                flags: sub.flags,
            };
            if let Some(Frame {
                fd,
                pending,
                blocked: still,
                ..
            }) = self.open_and_empty(parent, again)
            {
                blocked = still;
                self.remove_serially(&fd, pending);
            }
            result = self.unlink_empty(parent, sub, parent_repairable);
        }
        match result {
            Ok(()) => self.add_freed(sub.bytes),
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
            Err(error) => self.fail(error),
        }
    }

    /// One attempt at unlinking an emptied directory, repairing what `--force` allows.
    fn unlink_empty(&self, parent: RawFd, sub: &Sub, parent_repairable: bool) -> std::io::Result<()> {
        match sys::unlink_at(parent, &sub.name, true) {
            Err(error) if self.repair && denied(&error) => {
                // The directory's own immutable flag stops its removal as surely as its
                // parent's mode does; the first is inside the artifact whatever the parent is.
                #[cfg(target_vendor = "apple")]
                if sub.flags & USER_IMMUTABLE != 0
                    && let Ok(fd) = open(parent, &sub.name)
                {
                    sys::clear_immutable_fd(fd.as_raw_fd(), sub.flags);
                }
                if parent_repairable {
                    Self::repair_dir(parent);
                }
                sys::unlink_at(parent, &sub.name, true)
            }
            result => result,
        }
    }
}

#[cfg(test)]
mod traversal_tests;

#[cfg(test)]
mod tests {
    use std::os::unix::fs::PermissionsExt;

    use super::*;
    use crate::testing::tree;

    fn std_measure(path: &Path) -> u64 {
        use std::os::unix::fs::MetadataExt;
        let mut total = 0;
        let mut seen = std::collections::HashSet::new();
        let mut stack = vec![path.to_path_buf()];
        while let Some(dir) = stack.pop() {
            for entry in std::fs::read_dir(&dir).unwrap().flatten() {
                let metadata = entry.metadata().unwrap();
                if metadata.nlink() > 1 && !metadata.is_dir() && !seen.insert(metadata.ino()) {
                    continue;
                }
                total += metadata.blocks() * 512;
                if metadata.is_dir() {
                    stack.push(entry.path());
                }
            }
        }
        total
    }

    fn deep(root: &Path, levels: usize) {
        let mut path = root.to_path_buf();
        for _ in 0..levels {
            path.push("d");
        }
        std::fs::create_dir_all(&path).unwrap();
        std::fs::write(path.join("leaf"), vec![1u8; 9000]).unwrap();
    }

    #[test]
    fn should_measure_exactly_what_a_std_walk_measures() {
        let root = tree(&["a/b/c.txt", "a/d.txt", "e/f/g/h.txt", "i.txt"]);
        std::fs::write(root.path().join("a/big.bin"), vec![3u8; 1_000_000]).unwrap();
        std::fs::hard_link(root.path().join("a/big.bin"), root.path().join("e/again.bin")).unwrap();
        std::os::unix::fs::symlink(root.path().join("a"), root.path().join("e/link")).unwrap();
        deep(root.path(), 40);

        let measured = measure_below(root.path());
        assert_eq!(measured.bytes, std_measure(root.path()));
        assert_eq!(measured.unreadable, 0);
    }

    #[test]
    fn should_count_a_directory_it_cannot_open_as_unreadable() {
        let root = tree(&["locked/inside.txt", "open.txt"]);
        let locked = root.path().join("locked");
        std::fs::set_permissions(&locked, std::fs::Permissions::from_mode(0o000)).unwrap();
        let measured = measure_below(root.path());
        std::fs::set_permissions(&locked, std::fs::Permissions::from_mode(0o755)).unwrap();
        assert_eq!(measured.unreadable, 1);
    }

    #[test]
    fn should_remove_a_tree_and_count_what_it_freed() {
        let root = tree(&["artifact/a/b/c.txt", "artifact/d.txt", "keep.txt"]);
        let artifact = root.path().join("artifact");
        std::fs::write(artifact.join("a/big.bin"), vec![3u8; 500_000]).unwrap();
        deep(&artifact, 30);
        let expected = std_measure(&artifact) + {
            use std::os::unix::fs::MetadataExt;
            std::fs::symlink_metadata(&artifact).unwrap().blocks() * 512
        };

        let removed = remove_dir(&artifact, false);
        assert!(removed.error.is_none(), "{:?}", removed.error);
        assert!(!artifact.exists());
        assert!(root.path().join("keep.txt").exists());
        assert_eq!(removed.freed, expected);
    }

    #[test]
    fn should_remove_flat_batches_and_count_hard_links_once() {
        let root = tree(&["artifact/", "source/precious"]);
        let artifact = root.path().join("artifact");
        for index in 0..(UNLINK_BATCH * 8) {
            std::fs::write(artifact.join(index.to_string()), [3u8; 4096]).unwrap();
        }
        std::fs::hard_link(artifact.join("0"), artifact.join("again")).unwrap();
        std::os::unix::fs::symlink(root.path().join("source"), artifact.join("link")).unwrap();
        let expected = crate::size::measure(&artifact);
        let removed = remove_dir(&artifact, false);
        assert!(removed.error.is_none(), "flat removal failed: {:?}", removed.error);
        assert_eq!(removed.freed, expected, "batches must count a hard-linked inode once");
        assert!(!artifact.exists(), "all flat batches must be removed");
        assert!(root.path().join("source/precious").exists(), "symlink target survives");
    }

    #[test]
    fn should_remove_deeper_than_the_fanout_bound() {
        let root = tree(&["keep.txt"]);
        let artifact = root.path().join("artifact");
        deep(&artifact, 300);
        let removed = remove_dir(&artifact, false);
        assert!(removed.error.is_none(), "{:?}", removed.error);
        assert!(!artifact.exists());
    }

    #[test]
    fn should_unlink_a_symlink_and_leave_its_target() {
        let root = tree(&["target/precious.txt", "artifact/x.txt"]);
        std::os::unix::fs::symlink(root.path().join("target"), root.path().join("artifact/link")).unwrap();
        let removed = remove_dir(&root.path().join("artifact"), false);
        assert!(removed.error.is_none(), "{:?}", removed.error);
        assert!(root.path().join("target/precious.txt").exists());
    }

    #[test]
    fn should_leave_a_read_only_directory_without_repair_and_take_everything_else() {
        let root = tree(&["artifact/held/file.txt", "artifact/free/file.txt"]);
        let held = root.path().join("artifact/held");
        std::fs::set_permissions(&held, std::fs::Permissions::from_mode(0o555)).unwrap();
        let removed = remove_dir(&root.path().join("artifact"), false);
        let survived = held.join("file.txt").exists();
        std::fs::set_permissions(&held, std::fs::Permissions::from_mode(0o755)).unwrap();
        assert!(removed.error.is_some());
        assert!(survived);
        assert!(!root.path().join("artifact/free").exists());
    }

    #[test]
    fn should_repair_a_read_only_directory_when_asked() {
        let root = tree(&["artifact/held/deeper/file.txt", "artifact/locked/file.txt"]);
        let artifact = root.path().join("artifact");
        std::fs::set_permissions(artifact.join("held/deeper"), std::fs::Permissions::from_mode(0o555)).unwrap();
        std::fs::set_permissions(artifact.join("held"), std::fs::Permissions::from_mode(0o555)).unwrap();
        std::fs::set_permissions(artifact.join("locked"), std::fs::Permissions::from_mode(0o000)).unwrap();
        let removed = remove_dir(&artifact, true);
        assert!(removed.error.is_none(), "{:?}", removed.error);
        assert!(!artifact.exists());
    }

    #[test]
    fn should_never_repair_the_artifacts_parent() {
        let root = tree(&["parent/artifact/file.txt"]);
        let parent = root.path().join("parent");
        std::fs::set_permissions(&parent, std::fs::Permissions::from_mode(0o555)).unwrap();
        let removed = remove_dir(&parent.join("artifact"), true);
        let mode = std::fs::metadata(&parent).unwrap().permissions().mode();
        std::fs::set_permissions(&parent, std::fs::Permissions::from_mode(0o755)).unwrap();
        assert!(removed.error.is_some());
        assert_eq!(mode & 0o777, 0o555);
    }

    #[test]
    fn should_refuse_a_path_that_is_not_a_directory() {
        let root = tree(&["file.txt"]);
        let removed = remove_dir(&root.path().join("file.txt"), false);
        assert!(removed.error.is_some());
        assert!(root.path().join("file.txt").exists());
    }

    /// A build still writing into a cache as it goes: files appear in the directories voom has
    /// just emptied. The removal empties them again rather than leaving a residue.
    #[test]
    fn should_take_files_written_into_a_directory_while_it_is_being_removed() {
        let root = tree(&["keep.txt"]);
        let artifact = root.path().join("artifact");
        for index in 0..40 {
            std::fs::create_dir_all(artifact.join(format!("d{index}"))).unwrap();
            std::fs::write(artifact.join(format!("d{index}/f")), b"x").unwrap();
        }
        let writer_dir = artifact.clone();
        let writer = std::thread::spawn(move || {
            for round in 0..300 {
                let _ = std::fs::write(writer_dir.join(format!("d{}/late{round}", round % 40)), b"late");
                std::thread::sleep(Duration::from_micros(300));
            }
        });

        let removed = remove_dir(&artifact, false);
        writer.join().unwrap();

        assert!(removed.error.is_none(), "{:?}", removed.error);
        assert!(!artifact.exists(), "nothing the writer added survived");
    }
}