prune.rs 89.8%

212 of 236 lines run, 61 of 70 functions · run #222 on main · run missed

//! Pruning a build cache before it is kept (oxygenflow#72, spec §5.4).
//!
//! A kept disk starts the next run, so without pruning it carries every
//! build's files: each crate's artifacts under every hash a lockfile or a
//! feature set ever gave it. Before a passing job's cache disk goes back
//! into the pool, the files this run did not use are removed, oldest
//! first, until what is on the disk is at most a share of its size (the
//! cap). The microVM's guest init prunes its disks before it powers off,
//! since only it can see inside them; the runner prunes the syscall
//! tier's directories itself. Both use this module.
//!
//! What the run used is told by the files' times against when the job
//! started: written (mtime), changed (ctime) or read (atime). Reads are
//! seen only where the file system records them: the guest mounts a cache
//! disk `strictatime`; on the runner, where a directory sits on whatever
//! file system the runner has, each file's atime is set to the epoch
//! before the job ([`forget_reads`]), so even `relatime` records its
//! first read. A file system mounted `noatime` records none, and then
//! nothing is pruned.
//!
//! A build tool does not read everything it relies on. Cargo, finding a
//! crate fresh, reads its fingerprint and only looks at its rlib and
//! binaries, so their times say nothing. Every name cargo gives a unit's
//! files carries the unit's hash (`.fingerprint/foo-<hash>/`,
//! `deps/libfoo-<hash>.rlib`, `build/foo-<hash>/`), so a file stays when
//! a file this run used carries one of the hashes in its path: a fresh
//! crate's fingerprint keeps its artifacts. A file with another link
//! that stays, or under a path the job's outputs name, stays too. What
//! goes is what this run's build did not touch, which a later build needs
//! only if an older lockfile comes back, and then cargo rebuilds it.

use serde::{Deserialize, Serialize};
#[cfg(unix)]
use std::collections::{HashMap, HashSet};
#[cfg(unix)]
use std::os::unix::fs::MetadataExt;
use std::path::Path;
#[cfg(unix)]
use std::path::PathBuf;
use std::time::{Duration, SystemTime};

/// The share of a cache disk a kept cache may fill when no runner says
/// otherwise: room for this run's build and as much again.
pub const DEFAULT_PERCENT: u8 = 60;

/// What pruning a cache found and did, in bytes of blocks on its disk.
#[derive(Serialize, Deserialize, Debug, Clone, Default, PartialEq, Eq)]
pub struct Pruned {
    /// The disk's size, and the share of it the cache may fill.
    pub size: u64,
    pub percent: u8,
    /// What was on the disk before pruning, and after.
    pub before: u64,
    pub after: u64,
    /// What went: bytes and files.
    pub freed: u64,
    pub files: u64,
    /// Why nothing could be pruned, when so (no access times, or an
    /// error): only the size then decides.
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub unpruned: Option<String>,
}

impl Pruned {
    /// The most the cache may keep: `percent` of `size`.
    pub fn cap(&self) -> u64 {
        cap(self.size, self.percent)
    }

    /// Whether what is left may be kept.
    pub fn fits(&self) -> bool {
        self.after <= self.cap()
    }
}

fn cap(size: u64, percent: u8) -> u64 {
    (size as u128 * percent.min(100) as u128 / 100) as u64
}

/// Now, as a job's start to compare file times against. File systems
/// stamp times from a clock that may lag this one by a tick, so the
/// moments either side of it are left to pass: nothing done before the
/// call (such as [`forget_reads`]) can look as though it came after.
pub fn start_clock() -> SystemTime {
    std::thread::sleep(Duration::from_millis(20));
    let t = SystemTime::now();
    std::thread::sleep(Duration::from_millis(20));
    t
}

#[cfg(unix)]
/// Whether the file system holding `path` records reads (not `noatime`).
pub fn records_reads(path: &Path) -> bool {
    let Ok(c) = std::ffi::CString::new(path.as_os_str().as_encoded_bytes()) else { return false };
    let mut st: libc::statvfs = unsafe { std::mem::zeroed() };
    if unsafe { libc::statvfs(c.as_ptr(), &mut st) } != 0 {
        return false;
    }
    // Only Linux's statvfs has a `noatime` flag: elsewhere (Haiku, FreeBSD)
    // reads are taken as recorded, and the access-time check decides.
    #[cfg(any(target_os = "linux", target_os = "android"))]
    return st.f_flag & libc::ST_NOATIME == 0;
    #[cfg(not(any(target_os = "linux", target_os = "android")))]
    true
}

#[cfg(unix)]
/// The blocks in use on the file system mounted at `path`, and its size
/// (as `df` counts them).
pub fn usage(path: &Path) -> std::io::Result<(u64, u64)> {
    let c = std::ffi::CString::new(path.as_os_str().as_encoded_bytes())?;
    let mut st: libc::statvfs = unsafe { std::mem::zeroed() };
    if unsafe { libc::statvfs(c.as_ptr(), &mut st) } != 0 {
        return Err(std::io::Error::last_os_error());
    }
    let unit = st.f_frsize as u64;
    Ok(((st.f_blocks as u64).saturating_sub(st.f_bfree as u64) * unit, st.f_blocks as u64 * unit))
}

#[cfg(unix)]
/// Set every regular file's atime under `root` to the epoch, its mtime
/// kept, so the job's first read of each is recorded even on `relatime`
/// (which records a read only of a file read no later than it changed).
/// Links are not followed. The count of files.
pub fn forget_reads(root: &Path) -> std::io::Result<u64> {
    let mut n = 0;
    let mut err = None;
    walk(root, &mut |p, md| {
        if !md.file_type().is_file() {
            return;
        }
        let Ok(c) = std::ffi::CString::new(p.as_os_str().as_encoded_bytes()) else { return };
        let times = [libc::timespec { tv_sec: 0, tv_nsec: 0 }, libc::timespec { tv_sec: 0, tv_nsec: libc::UTIME_OMIT }];
        if unsafe { libc::utimensat(libc::AT_FDCWD, c.as_ptr(), times.as_ptr(), libc::AT_SYMLINK_NOFOLLOW) } == 0 {
            n += 1;
        } else if err.is_none() {
            err = Some(std::io::Error::last_os_error());
        }
    })?;
    match err {
        Some(e) => Err(e),
        None => Ok(n),
    }
}

#[cfg(unix)]
/// Each entry under `root` (not `root` itself) with its metadata, parents
/// before children; links are not followed, nor other file systems
/// entered.
fn walk(root: &Path, f: &mut dyn FnMut(&Path, &std::fs::Metadata)) -> std::io::Result<()> {
    let dev = std::fs::symlink_metadata(root)?.dev();
    let mut dirs = vec![root.to_path_buf()];
    while let Some(d) = dirs.pop() {
        let Ok(entries) = std::fs::read_dir(&d) else { continue };
        for e in entries.flatten() {
            let p = e.path();
            let Ok(md) = std::fs::symlink_metadata(&p) else { continue };
            if md.dev() != dev {
                continue;
            }
            f(&p, &md);
            if md.is_dir() {
                dirs.push(p);
            }
        }
    }
    Ok(())
}

#[cfg(unix)]
/// The unit hashes in `rel`: a 16-digit lowercase hex word after a `-`
/// in any of its names, as cargo names a unit's files.
fn hashes(rel: &Path) -> impl Iterator<Item = String> + '_ {
    rel.components().filter_map(|c| c.as_os_str().to_str()).flat_map(|name| {
        name.split('-').skip(1).filter_map(|w| {
            let w = w.split('.').next().unwrap_or("");
            (w.len() == 16 && w.bytes().all(|b| b.is_ascii_digit() || (b'a'..=b'f').contains(&b))).then(|| w.to_string())
        })
    })
}

#[cfg(unix)]
fn nanos(s: i64, ns: i64) -> i128 {
    s as i128 * 1_000_000_000 + ns as i128
}

#[cfg(unix)]
/// One file, however many names it has.
struct File {
    paths: Vec<PathBuf>,
    links: u64,
    bytes: u64,
    /// When it was last used as far as can be told: the later of its
    /// atime and mtime.
    last: i128,
    used: bool,
}

#[cfg(unix)]
/// Prune the cache at `root`, a disk of `size` bytes with `before` in
/// use, down to `percent` of its size, removing only regular files this
/// run did not use (see the module's notes), those used longest ago
/// first. `started` is when the job started ([`start_clock`]); `keep` are
/// paths relative to `root` (the job's outputs) that stay whatever their
/// times. Under the cap nothing is touched. `after` is `before` less what
/// was freed.
pub fn prune(root: &Path, started: SystemTime, keep: &[String], size: u64, before: u64, percent: u8) -> std::io::Result<Pruned> {
    let mut out = Pruned { size, percent, before, after: before, ..Pruned::default() };
    if before <= out.cap() {
        return Ok(out);
    }
    let since = started.duration_since(SystemTime::UNIX_EPOCH).map(|d| d.as_nanos() as i128).unwrap_or(0);
    let keep: Vec<PathBuf> = keep.iter().map(|k| PathBuf::from(k.trim_start_matches('/'))).filter(|k| !k.as_os_str().is_empty()).collect();
    let mut files: HashMap<(u64, u64), File> = HashMap::new();
    walk(root, &mut |p, md| {
        if !md.file_type().is_file() {
            return;
        }
        let rel = p.strip_prefix(root).unwrap_or(p);
        let used = [nanos(md.atime(), md.atime_nsec()), nanos(md.mtime(), md.mtime_nsec()), nanos(md.ctime(), md.ctime_nsec())]
            .into_iter()
            .any(|t| t >= since)
            || keep.iter().any(|k| rel.starts_with(k));
        let f = files.entry((md.dev(), md.ino())).or_insert_with(|| File {
            paths: Vec::new(),
            links: md.nlink(),
            bytes: md.blocks() * 512,
            last: nanos(md.atime(), md.atime_nsec()).max(nanos(md.mtime(), md.mtime_nsec())),
            used: false,
        });
        f.paths.push(p.to_path_buf());
        f.used |= used;
    })?;
    // A hash any used file carries keeps every file carrying it.
    let live: HashSet<String> =
        files.values().filter(|f| f.used).flat_map(|f| f.paths.iter().flat_map(|p| hashes(p.strip_prefix(root).unwrap_or(p)))).collect();
    let mut gone: Vec<File> = files
        .into_values()
        .filter(|f| {
            !f.used
                // A link from outside the cache: removing it frees nothing.
                && f.links == f.paths.len() as u64
                && !f.paths.iter().any(|p| hashes(p.strip_prefix(root).unwrap_or(p)).any(|h| live.contains(&h)))
        })
        .collect();
    gone.sort_by_key(|f| f.last);
    let mut emptied: HashSet<PathBuf> = HashSet::new();
    for f in gone {
        if out.after <= out.cap() {
            break;
        }
        let mut removed = true;
        for p in &f.paths {
            if std::fs::remove_file(p).is_err() {
                removed = false;
            } else if let Some(parent) = p.parent() {
                emptied.insert(parent.to_path_buf());
            }
        }
        if removed {
            out.after = out.after.saturating_sub(f.bytes);
            out.freed += f.bytes;
            out.files += 1;
        }
    }
    // Directories pruning emptied go too, deepest first; never `root`.
    let mut dirs: Vec<PathBuf> = emptied.into_iter().collect();
    dirs.sort_by_key(|d| std::cmp::Reverse(d.components().count()));
    for d in dirs {
        let mut d = d.as_path();
        while d != root && d.starts_with(root) && std::fs::remove_dir(d).is_ok() {
            match d.parent() {
                Some(p) => d = p,
                None => break,
            }
        }
    }
    Ok(out)
}

// Elsewhere (a Windows runner, which has no microVM tier and so no cache
// disks to prune) nothing records reads, so nothing is pruned.

#[cfg(not(unix))]
pub fn records_reads(_path: &Path) -> bool {
    false
}

#[cfg(not(unix))]
pub fn usage(_path: &Path) -> std::io::Result<(u64, u64)> {
    Err(std::io::Error::new(std::io::ErrorKind::Unsupported, "cache disks are pruned only on Linux"))
}

#[cfg(not(unix))]
pub fn forget_reads(_root: &Path) -> std::io::Result<u64> {
    Ok(0)
}

#[cfg(not(unix))]
pub fn prune(_root: &Path, _started: SystemTime, _keep: &[String], _size: u64, _before: u64, _percent: u8) -> std::io::Result<Pruned> {
    Err(std::io::Error::new(std::io::ErrorKind::Unsupported, "cache disks are pruned only on Linux"))
}

#[cfg(all(test, unix))]
mod tests {
    use super::*;

    /// Times around a job that started at `T`, ahead of the clock: a file
    /// whose times are set is changed (ctime) now, before it.
    const T: u64 = 4_000_000_000;

    fn at(secs: u64) -> SystemTime {
        SystemTime::UNIX_EPOCH + Duration::from_secs(secs)
    }

    /// A file of `kib` KiB at `rel`, last read and written at `secs`.
    fn file(root: &Path, rel: &str, kib: usize, secs: u64) -> PathBuf {
        let p = root.join(rel);
        std::fs::create_dir_all(p.parent().unwrap()).unwrap();
        let bytes: Vec<u8> = (0..kib << 10).map(|i: usize| (i.wrapping_mul(2_654_435_761) >> 13) as u8).collect();
        std::fs::write(&p, bytes).unwrap();
        let f = std::fs::File::options().write(true).open(&p).unwrap();
        f.set_times(std::fs::FileTimes::new().set_accessed(at(secs)).set_modified(at(secs))).unwrap();
        p
    }

    fn bytes(p: &Path) -> u64 {
        std::fs::metadata(p).unwrap().blocks() * 512
    }

    #[test]
    fn hashes_are_cargos_unit_hashes() {
        let h = |p: &str| hashes(Path::new(p)).collect::<Vec<_>>();
        assert_eq!(h("debug/deps/libdep-8f2b19826c505967.rlib"), ["8f2b19826c505967"]);
        assert_eq!(h("debug/.fingerprint/dep-8f2b19826c505967/lib-dep"), ["8f2b19826c505967"]);
        assert_eq!(h("debug/build/my-crate-0123456789abcdef/out/x.o"), ["0123456789abcdef"]);
        assert!(h("debug/incremental/app-2dadnjnzlrswc/s-hndl5uwdpw-1uaho4m.lock").is_empty());
        assert!(h("debug/app").is_empty() && h("debug/deps/x-0123456789ABCDEF").is_empty() && h("x-0123456789abcde").is_empty());
    }

    #[test]
    fn under_the_cap_nothing_is_touched() {
        let dir = tempfile::tempdir().unwrap();
        let old = file(dir.path(), "debug/deps/libold-1111111111111111.rlib", 64, 1_000);
        let p = prune(dir.path(), at(T), &[], 1 << 30, 64 << 10, 60).unwrap();
        assert!(old.exists() && p.fits() && p.freed == 0 && p.after == p.before, "{p:?}");
    }

    /// A cargo target as a run leaves it: this lockfile's units used this
    /// run (one rebuilt, one fresh: only its fingerprint read), an older
    /// lockfile's not, and an output the run did not touch.
    #[test]
    fn what_this_run_did_not_use_goes_oldest_first_and_its_units_stay_whole() {
        let dir = tempfile::tempdir().unwrap();
        let root = dir.path();
        let app = file(root, "debug/deps/app-aaaaaaaaaaaaaaaa", 256, T + 100);
        let app_fp = file(root, "debug/.fingerprint/app-aaaaaaaaaaaaaaaa/bin-app", 1, T + 100);
        let dep_rlib = file(root, "debug/deps/libdep-bbbbbbbbbbbbbbbb.rlib", 256, T - 5_000);
        let dep_fp = file(root, "debug/.fingerprint/dep-bbbbbbbbbbbbbbbb/lib-dep", 1, T - 5_000);
        std::fs::File::open(&dep_fp).unwrap().set_times(std::fs::FileTimes::new().set_accessed(at(T + 50))).unwrap();
        let script = file(root, "debug/build/dep-bbbbbbbbbbbbbbbb/out/gen.rs", 64, T - 5_000);
        // Uplifted: another name of the rebuilt binary.
        std::fs::hard_link(&app, root.join("debug/app")).unwrap();
        // An older lockfile's units, untouched, the oldest first to go.
        let oldest = file(root, "debug/deps/libdep-cccccccccccccccc.rlib", 256, T - 9_000);
        let oldest_fp = file(root, "debug/.fingerprint/dep-cccccccccccccccc/lib-dep", 1, T - 8_999);
        let older = file(root, "debug/deps/libdep-dddddddddddddddd.rlib", 256, T - 8_000);
        // A declared output, older still, that the run did not touch.
        let output = file(root, "release/tool", 128, T - 10_000);
        let all = [&app, &app_fp, &dep_rlib, &dep_fp, &script, &oldest, &oldest_fp, &older, &output];
        let before: u64 = all.iter().map(|p| bytes(p)).sum();
        // Room for all but the oldest unit.
        let want = before - bytes(&oldest) - bytes(&oldest_fp);
        let size = (want * 100).div_ceil(60);
        let p = prune(root, at(T), &["/release/tool".into()], size, before, 60).unwrap();
        assert!(p.fits(), "{p:?}");
        assert!(
            !oldest.exists() && !root.join("debug/.fingerprint/dep-cccccccccccccccc").exists(),
            "the oldest unit went, its emptied directory too"
        );
        assert!(older.exists(), "and pruning stopped under the cap: {p:?}");
        for kept in [&app, &app_fp, &dep_rlib, &dep_fp, &script, &output, &root.join("debug/app")] {
            assert!(kept.exists(), "{} stays", kept.display());
        }
        assert_eq!((p.files, p.freed, p.after), (2, p.before - want, want));
        // With no room at all: still only what the run did not use goes.
        let p = prune(root, at(T), &["release/tool".into()], 1, p.after, 60).unwrap();
        assert!(!older.exists() && !p.fits() && p.files == 1, "{p:?}");
        for kept in [&app, &dep_rlib, &dep_fp, &script, &output] {
            assert!(kept.exists(), "{} stays", kept.display());
        }
        assert!(root.join("debug/deps").is_dir(), "a directory still holding files stays");
    }

    #[test]
    fn reads_are_forgotten_so_the_next_is_seen() {
        let dir = tempfile::tempdir().unwrap();
        let p = file(dir.path(), "a/b", 1, 5_000);
        std::os::unix::fs::symlink("/etc/passwd", dir.path().join("link")).unwrap();
        assert_eq!(forget_reads(dir.path()).unwrap(), 1);
        let md = std::fs::metadata(&p).unwrap();
        assert_eq!((md.atime(), md.mtime()), (0, 5_000), "the mtime is kept");
        assert!(std::fs::symlink_metadata(dir.path().join("link")).unwrap().atime() > 0, "a link is not followed");
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1		//! Pruning a build cache before it is kept (oxygenflow#72, spec §5.4).
2		//!
3		//! A kept disk starts the next run, so without pruning it carries every
4		//! build's files: each crate's artifacts under every hash a lockfile or a
5		//! feature set ever gave it. Before a passing job's cache disk goes back
6		//! into the pool, the files this run did not use are removed, oldest
7		//! first, until what is on the disk is at most a share of its size (the
8		//! cap). The microVM's guest init prunes its disks before it powers off,
9		//! since only it can see inside them; the runner prunes the syscall
10		//! tier's directories itself. Both use this module.
11		//!
12		//! What the run used is told by the files' times against when the job
13		//! started: written (mtime), changed (ctime) or read (atime). Reads are
14		//! seen only where the file system records them: the guest mounts a cache
15		//! disk `strictatime`; on the runner, where a directory sits on whatever
16		//! file system the runner has, each file's atime is set to the epoch
17		//! before the job ([`forget_reads`]), so even `relatime` records its
18		//! first read. A file system mounted `noatime` records none, and then
19		//! nothing is pruned.
20		//!
21		//! A build tool does not read everything it relies on. Cargo, finding a
22		//! crate fresh, reads its fingerprint and only looks at its rlib and
23		//! binaries, so their times say nothing. Every name cargo gives a unit's
24		//! files carries the unit's hash (`.fingerprint/foo-<hash>/`,
25		//! `deps/libfoo-<hash>.rlib`, `build/foo-<hash>/`), so a file stays when
26		//! a file this run used carries one of the hashes in its path: a fresh
27		//! crate's fingerprint keeps its artifacts. A file with another link
28		//! that stays, or under a path the job's outputs name, stays too. What
29		//! goes is what this run's build did not touch, which a later build needs
30		//! only if an older lockfile comes back, and then cargo rebuilds it.
31
32		use serde::{Deserialize, Serialize};
33		#[cfg(unix)]
34		use std::collections::{HashMap, HashSet};
35		#[cfg(unix)]
36		use std::os::unix::fs::MetadataExt;
37		use std::path::Path;
38		#[cfg(unix)]
39		use std::path::PathBuf;
40		use std::time::{Duration, SystemTime};
41
42		/// The share of a cache disk a kept cache may fill when no runner says
43		/// otherwise: room for this run's build and as much again.
44		pub const DEFAULT_PERCENT: u8 = 60;
45
46		/// What pruning a cache found and did, in bytes of blocks on its disk.
47		#[derive(Serialize, Deserialize, Debug, Clone, Default, PartialEq, Eq)]
48		pub struct Pruned {
49		/// The disk's size, and the share of it the cache may fill.
50		pub size: u64,
51		pub percent: u8,
52		/// What was on the disk before pruning, and after.
53		pub before: u64,
54		pub after: u64,
55		/// What went: bytes and files.
56		pub freed: u64,
57		pub files: u64,
58		/// Why nothing could be pruned, when so (no access times, or an
59		/// error): only the size then decides.
60		#[serde(default, skip_serializing_if = "Option::is_none")]
61		pub unpruned: Option<String>,
62		}
63
64		impl Pruned {
65		/// The most the cache may keep: `percent` of `size`.
66	54×	pub fn cap(&self) -> u64 {
67	54×	cap(self.size, self.percent)
68	54×	}
69
70		/// Whether what is left may be kept.
71	35×	pub fn fits(&self) -> bool {
72	35×	self.after <= self.cap()
73	35×	}
74		}
75
76	54×	fn cap(size: u64, percent: u8) -> u64 {
77	54×	(size as u128 * percent.min(100) as u128 / 100) as u64
78	54×	}
79
80		/// Now, as a job's start to compare file times against. File systems
81		/// stamp times from a clock that may lag this one by a tick, so the
82		/// moments either side of it are left to pass: nothing done before the
83		/// call (such as [`forget_reads`]) can look as though it came after.
84	0×	pub fn start_clock() -> SystemTime {
85	0×	std::thread::sleep(Duration::from_millis(20));
86	0×	let t = SystemTime::now();
87	0×	std::thread::sleep(Duration::from_millis(20));
88	0×	t
89	0×	}
90
91		#[cfg(unix)]
92		/// Whether the file system holding `path` records reads (not `noatime`).
93	7×	pub fn records_reads(path: &Path) -> bool {
94	7×	let Ok(c) = std::ffi::CString::new(path.as_os_str().as_encoded_bytes()) else { return false };
95	7×	let mut st: libc::statvfs = unsafe { std::mem::zeroed() };
96	7×	if unsafe { libc::statvfs(c.as_ptr(), &mut st) } != 0 {
97	0×	return false;
98	7×	}
99		// Only Linux's statvfs has a `noatime` flag: elsewhere (Haiku, FreeBSD)
100		// reads are taken as recorded, and the access-time check decides.
101		#[cfg(any(target_os = "linux", target_os = "android"))]
102	7×	return st.f_flag & libc::ST_NOATIME == 0;
103		#[cfg(not(any(target_os = "linux", target_os = "android")))]
104		true
105	7×	}
106
107		#[cfg(unix)]
108		/// The blocks in use on the file system mounted at `path`, and its size
109		/// (as `df` counts them).
110	0×	pub fn usage(path: &Path) -> std::io::Result<(u64, u64)> {
111	0×	let c = std::ffi::CString::new(path.as_os_str().as_encoded_bytes())?;
112	0×	let mut st: libc::statvfs = unsafe { std::mem::zeroed() };
113	0×	if unsafe { libc::statvfs(c.as_ptr(), &mut st) } != 0 {
114	0×	return Err(std::io::Error::last_os_error());
115	0×	}
116	0×	let unit = st.f_frsize as u64;
117	0×	Ok(((st.f_blocks as u64).saturating_sub(st.f_bfree as u64) * unit, st.f_blocks as u64 * unit))
118	0×	}
119
120		#[cfg(unix)]
121		/// Set every regular file's atime under `root` to the epoch, its mtime
122		/// kept, so the job's first read of each is recorded even on `relatime`
123		/// (which records a read only of a file read no later than it changed).
124		/// Links are not followed. The count of files.
125	2×	pub fn forget_reads(root: &Path) -> std::io::Result<u64> {
126	2×	let mut n = 0;
127	2×	let mut err = None;
128	6×	walk(root, &mut \|p, md\| {
129	6×	if !md.file_type().is_file() {
130	4×	return;
131	2×	}
132	2×	let Ok(c) = std::ffi::CString::new(p.as_os_str().as_encoded_bytes()) else { return };
133	2×	let times = [libc::timespec { tv_sec: 0, tv_nsec: 0 }, libc::timespec { tv_sec: 0, tv_nsec: libc::UTIME_OMIT }];
134	2×	if unsafe { libc::utimensat(libc::AT_FDCWD, c.as_ptr(), times.as_ptr(), libc::AT_SYMLINK_NOFOLLOW) } == 0 {
135	2×	n += 1;
136	2×	} else if err.is_none() {
137	0×	err = Some(std::io::Error::last_os_error());
138	0×	}
139	6×	})?;
140	2×	match err {
141	0×	Some(e) => Err(e),
142	2×	None => Ok(n),
143		}
144	2×	}
145
146		#[cfg(unix)]
147		/// Each entry under `root` (not `root` itself) with its metadata, parents
148		/// before children; links are not followed, nor other file systems
149		/// entered.
150	6×	fn walk(root: &Path, f: &mut dyn FnMut(&Path, &std::fs::Metadata)) -> std::io::Result<()> {
151	6×	let dev = std::fs::symlink_metadata(root)?.dev();
152	6×	let mut dirs = vec![root.to_path_buf()];
153	38×	while let Some(d) = dirs.pop() {
154	32×	let Ok(entries) = std::fs::read_dir(&d) else { continue };
155	51×	for e in entries.flatten() {
156	51×	let p = e.path();
157	51×	let Ok(md) = std::fs::symlink_metadata(&p) else { continue };
158	51×	if md.dev() != dev {
159	0×	continue;
160	51×	}
161	51×	f(&p, &md);
162	51×	if md.is_dir() {
163	26×	dirs.push(p);
164	26×	}
165		}
166		}
167	6×	Ok(())
168	6×	}
169
170		#[cfg(unix)]
171		/// The unit hashes in `rel`: a 16-digit lowercase hex word after a `-`
172		/// in any of its names, as cargo names a unit's files.
173	29×	fn hashes(rel: &Path) -> impl Iterator<Item = String> + '_ {
174	89×	rel.components().filter_map(\|c\| c.as_os_str().to_str()).flat_map(\|name\| {
175	89×	name.split('-').skip(1).filter_map(\|w\| {
176	33×	let w = w.split('.').next().unwrap_or("");
177	347×	(w.len() == 16 && w.bytes().all(\|b\| b.is_ascii_digit() \|\| (b'a'..=b'f').contains(&b))).then(\|\| w.to_string())
178	33×	})
179	89×	})
180	29×	}
181
182		#[cfg(unix)]
183	106×	fn nanos(s: i64, ns: i64) -> i128 {
184	106×	s as i128 * 1_000_000_000 + ns as i128
185	106×	}
186
187		#[cfg(unix)]
188		/// One file, however many names it has.
189		struct File {
190		paths: Vec<PathBuf>,
191		links: u64,
192		bytes: u64,
193		/// When it was last used as far as can be told: the later of its
194		/// atime and mtime.
195		last: i128,
196		used: bool,
197		}
198
199		#[cfg(unix)]
200		/// Prune the cache at `root`, a disk of `size` bytes with `before` in
201		/// use, down to `percent` of its size, removing only regular files this
202		/// run did not use (see the module's notes), those used longest ago
203		/// first. `started` is when the job started ([`start_clock`]); `keep` are
204		/// paths relative to `root` (the job's outputs) that stay whatever their
205		/// times. Under the cap nothing is touched. `after` is `before` less what
206		/// was freed.
207	10×	pub fn prune(root: &Path, started: SystemTime, keep: &[String], size: u64, before: u64, percent: u8) -> std::io::Result<Pruned> {
208	10×	let mut out = Pruned { size, percent, before, after: before, ..Pruned::default() };
209	10×	if before <= out.cap() {
210	6×	return Ok(out);
211	4×	}
212	4×	let since = started.duration_since(SystemTime::UNIX_EPOCH).map(\|d\| d.as_nanos() as i128).unwrap_or(0);
213	4×	let keep: Vec<PathBuf> = keep.iter().map(\|k\| PathBuf::from(k.trim_start_matches('/'))).filter(\|k\| !k.as_os_str().is_empty()).collect();
214	4×	let mut files: HashMap<(u64, u64), File> = HashMap::new();
215	45×	walk(root, &mut \|p, md\| {
216	45×	if !md.file_type().is_file() {
217	23×	return;
218	22×	}
219	22×	let rel = p.strip_prefix(root).unwrap_or(p);
220	22×	let used = [nanos(md.atime(), md.atime_nsec()), nanos(md.mtime(), md.mtime_nsec()), nanos(md.ctime(), md.ctime_nsec())]
221	22×	.into_iter()
222	45×	.any(\|t\| t >= since)
223	11×	\|\| keep.iter().any(\|k\| rel.starts_with(k));
224	22×	let f = files.entry((md.dev(), md.ino())).or_insert_with(\|\| File {
225	20×	paths: Vec::new(),
226	20×	links: md.nlink(),
227	20×	bytes: md.blocks() * 512,
228	20×	last: nanos(md.atime(), md.atime_nsec()).max(nanos(md.mtime(), md.mtime_nsec())),
229		used: false,
230	20×	});
231	22×	f.paths.push(p.to_path_buf());
232	22×	f.used \|= used;
233	45×	})?;
234		// A hash any used file carries keeps every file carrying it.
235	4×	let live: HashSet<String> =
236	13×	files.values().filter(\|f\| f.used).flat_map(\|f\| f.paths.iter().flat_map(\|p\| hashes(p.strip_prefix(root).unwrap_or(p)))).collect();
237	4×	let mut gone: Vec<File> = files
238	4×	.into_values()
239	20×	.filter(\|f\| {
240	20×	!f.used
241		// A link from outside the cache: removing it frees nothing.
242	9×	&& f.links == f.paths.len() as u64
243	9×	&& !f.paths.iter().any(\|p\| hashes(p.strip_prefix(root).unwrap_or(p)).any(\|h\| live.contains(&h)))
244	20×	})
245	4×	.collect();
246	4×	gone.sort_by_key(\|f\| f.last);
247	4×	let mut emptied: HashSet<PathBuf> = HashSet::new();
248	5×	for f in gone {
249	5×	if out.after <= out.cap() {
250	1×	break;
251	4×	}
252	4×	let mut removed = true;
253	4×	for p in &f.paths {
254	4×	if std::fs::remove_file(p).is_err() {
255	0×	removed = false;
256	4×	} else if let Some(parent) = p.parent() {
257	4×	emptied.insert(parent.to_path_buf());
258	4×	}
259		}
260	4×	if removed {
261	4×	out.after = out.after.saturating_sub(f.bytes);
262	4×	out.freed += f.bytes;
263	4×	out.files += 1;
264	4×	}
265		}
266		// Directories pruning emptied go too, deepest first; never `root`.
267	4×	let mut dirs: Vec<PathBuf> = emptied.into_iter().collect();
268	4×	dirs.sort_by_key(\|d\| std::cmp::Reverse(d.components().count()));
269	4×	for d in dirs {
270	4×	let mut d = d.as_path();
271	5×	while d != root && d.starts_with(root) && std::fs::remove_dir(d).is_ok() {
272	1×	match d.parent() {
273	1×	Some(p) => d = p,
274	0×	None => break,
275		}
276		}
277		}
278	4×	Ok(out)
279	10×	}
280
281		// Elsewhere (a Windows runner, which has no microVM tier and so no cache
282		// disks to prune) nothing records reads, so nothing is pruned.
283
284		#[cfg(not(unix))]
285		pub fn records_reads(_path: &Path) -> bool {
286		false
287		}
288
289		#[cfg(not(unix))]
290		pub fn usage(_path: &Path) -> std::io::Result<(u64, u64)> {
291		Err(std::io::Error::new(std::io::ErrorKind::Unsupported, "cache disks are pruned only on Linux"))
292		}
293
294		#[cfg(not(unix))]
295		pub fn forget_reads(_root: &Path) -> std::io::Result<u64> {
296		Ok(0)
297		}
298
299		#[cfg(not(unix))]
300		pub fn prune(_root: &Path, _started: SystemTime, _keep: &[String], _size: u64, _before: u64, _percent: u8) -> std::io::Result<Pruned> {
301		Err(std::io::Error::new(std::io::ErrorKind::Unsupported, "cache disks are pruned only on Linux"))
302		}
303
304		#[cfg(all(test, unix))]
305		mod tests {
306		use super::*;
307
308		/// Times around a job that started at `T`, ahead of the clock: a file
309		/// whose times are set is changed (ctime) now, before it.
310		const T: u64 = 4_000_000_000;
311
312	26×	fn at(secs: u64) -> SystemTime {
313	26×	SystemTime::UNIX_EPOCH + Duration::from_secs(secs)
314	26×	}
315
316		/// A file of `kib` KiB at `rel`, last read and written at `secs`.
317	11×	fn file(root: &Path, rel: &str, kib: usize, secs: u64) -> PathBuf {
318	11×	let p = root.join(rel);
319	11×	std::fs::create_dir_all(p.parent().unwrap()).unwrap();
320	1314816×	let bytes: Vec<u8> = (0..kib << 10).map(\|i: usize\| (i.wrapping_mul(2_654_435_761) >> 13) as u8).collect();
321	11×	std::fs::write(&p, bytes).unwrap();
322	11×	let f = std::fs::File::options().write(true).open(&p).unwrap();
323	11×	f.set_times(std::fs::FileTimes::new().set_accessed(at(secs)).set_modified(at(secs))).unwrap();
324	11×	p
325	11×	}
326
327	11×	fn bytes(p: &Path) -> u64 {
328	11×	std::fs::metadata(p).unwrap().blocks() * 512
329	11×	}
330
331		#[test]
332	1×	fn hashes_are_cargos_unit_hashes() {
333	7×	let h = \|p: &str\| hashes(Path::new(p)).collect::<Vec<_>>();
334	1×	assert_eq!(h("debug/deps/libdep-8f2b19826c505967.rlib"), ["8f2b19826c505967"]);
335	1×	assert_eq!(h("debug/.fingerprint/dep-8f2b19826c505967/lib-dep"), ["8f2b19826c505967"]);
336	1×	assert_eq!(h("debug/build/my-crate-0123456789abcdef/out/x.o"), ["0123456789abcdef"]);
337	1×	assert!(h("debug/incremental/app-2dadnjnzlrswc/s-hndl5uwdpw-1uaho4m.lock").is_empty());
338	1×	assert!(h("debug/app").is_empty() && h("debug/deps/x-0123456789ABCDEF").is_empty() && h("x-0123456789abcde").is_empty());
339	1×	}
340
341		#[test]
342	1×	fn under_the_cap_nothing_is_touched() {
343	1×	let dir = tempfile::tempdir().unwrap();
344	1×	let old = file(dir.path(), "debug/deps/libold-1111111111111111.rlib", 64, 1_000);
345	1×	let p = prune(dir.path(), at(T), &[], 1 << 30, 64 << 10, 60).unwrap();
346	1×	assert!(old.exists() && p.fits() && p.freed == 0 && p.after == p.before, "{p:?}");
347	1×	}
348
349		/// A cargo target as a run leaves it: this lockfile's units used this
350		/// run (one rebuilt, one fresh: only its fingerprint read), an older
351		/// lockfile's not, and an output the run did not touch.
352		#[test]
353	1×	fn what_this_run_did_not_use_goes_oldest_first_and_its_units_stay_whole() {
354	1×	let dir = tempfile::tempdir().unwrap();
355	1×	let root = dir.path();
356	1×	let app = file(root, "debug/deps/app-aaaaaaaaaaaaaaaa", 256, T + 100);
357	1×	let app_fp = file(root, "debug/.fingerprint/app-aaaaaaaaaaaaaaaa/bin-app", 1, T + 100);
358	1×	let dep_rlib = file(root, "debug/deps/libdep-bbbbbbbbbbbbbbbb.rlib", 256, T - 5_000);
359	1×	let dep_fp = file(root, "debug/.fingerprint/dep-bbbbbbbbbbbbbbbb/lib-dep", 1, T - 5_000);
360	1×	std::fs::File::open(&dep_fp).unwrap().set_times(std::fs::FileTimes::new().set_accessed(at(T + 50))).unwrap();
361	1×	let script = file(root, "debug/build/dep-bbbbbbbbbbbbbbbb/out/gen.rs", 64, T - 5_000);
362		// Uplifted: another name of the rebuilt binary.
363	1×	std::fs::hard_link(&app, root.join("debug/app")).unwrap();
364		// An older lockfile's units, untouched, the oldest first to go.
365	1×	let oldest = file(root, "debug/deps/libdep-cccccccccccccccc.rlib", 256, T - 9_000);
366	1×	let oldest_fp = file(root, "debug/.fingerprint/dep-cccccccccccccccc/lib-dep", 1, T - 8_999);
367	1×	let older = file(root, "debug/deps/libdep-dddddddddddddddd.rlib", 256, T - 8_000);
368		// A declared output, older still, that the run did not touch.
369	1×	let output = file(root, "release/tool", 128, T - 10_000);
370	1×	let all = [&app, &app_fp, &dep_rlib, &dep_fp, &script, &oldest, &oldest_fp, &older, &output];
371	9×	let before: u64 = all.iter().map(\|p\| bytes(p)).sum();
372		// Room for all but the oldest unit.
373	1×	let want = before - bytes(&oldest) - bytes(&oldest_fp);
374	1×	let size = (want * 100).div_ceil(60);
375	1×	let p = prune(root, at(T), &["/release/tool".into()], size, before, 60).unwrap();
376	1×	assert!(p.fits(), "{p:?}");
377	1×	assert!(
378	1×	!oldest.exists() && !root.join("debug/.fingerprint/dep-cccccccccccccccc").exists(),
379		"the oldest unit went, its emptied directory too"
380		);
381	1×	assert!(older.exists(), "and pruning stopped under the cap: {p:?}");
382	7×	for kept in [&app, &app_fp, &dep_rlib, &dep_fp, &script, &output, &root.join("debug/app")] {
383	7×	assert!(kept.exists(), "{} stays", kept.display());
384		}
385	1×	assert_eq!((p.files, p.freed, p.after), (2, p.before - want, want));
386		// With no room at all: still only what the run did not use goes.
387	1×	let p = prune(root, at(T), &["release/tool".into()], 1, p.after, 60).unwrap();
388	1×	assert!(!older.exists() && !p.fits() && p.files == 1, "{p:?}");
389	5×	for kept in [&app, &dep_rlib, &dep_fp, &script, &output] {
390	5×	assert!(kept.exists(), "{} stays", kept.display());
391		}
392	1×	assert!(root.join("debug/deps").is_dir(), "a directory still holding files stays");
393	1×	}
394
395		#[test]
396	1×	fn reads_are_forgotten_so_the_next_is_seen() {
397	1×	let dir = tempfile::tempdir().unwrap();
398	1×	let p = file(dir.path(), "a/b", 1, 5_000);
399	1×	std::os::unix::fs::symlink("/etc/passwd", dir.path().join("link")).unwrap();
400	1×	assert_eq!(forget_reads(dir.path()).unwrap(), 1);
401	1×	let md = std::fs::metadata(&p).unwrap();
402	1×	assert_eq!((md.atime(), md.mtime()), (0, 5_000), "the mtime is kept");
403	1×	assert!(std::fs::symlink_metadata(dir.path().join("link")).unwrap().atime() > 0, "a link is not followed");
404	1×	}
405		}

Coverage / crates/flow-init/src/prune.rs 89.8%

Keyboard