wsb 0.275.7622

//! A directory kept under a size, by removing the oldest things in it.
//!
//! Two directories in this worktree are unbounded by nature and bounded by
//! policy: the logs, which grow by one file per operation, and the build root,
//! which grows by one tree per project per toolchain. Both hold only things
//! that can be produced again, both are read long after they were written, and
//! both fill a disk if nothing says otherwise.
//!
//! What differs between them is what an ENTRY is — one operation's log, one
//! test session, one project's target directory — and that is the only thing
//! their own modules have to answer. Everything else is here: how big a thing
//! is, when it was last written, which of them go, and what a sweep may never
//! touch.
//!
//! # What a sweep removes
//!
//! Whole entries, oldest first, until the total is under the limit. Never half
//! of one: half a test session is a directory that still reads as a session,
//! and half a target directory is a build that fails in a way that looks like
//! a code problem. Anything protected is skipped whatever the total, and a
//! sweep that cannot get under the limit says so rather than pretending.

use crate::prelude::*;
use std::collections::BTreeMap;
use std::path::{Path, PathBuf};

/// Whether a stream's entries are files or directories.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EntryKind {
    File,
    Directory,
}

/// One removable thing: an operation's log, a test session, a daemon log.
#[derive(Debug, Clone)]
pub struct Entry {
    pub path: PathBuf,
    /// Which part of the directory it belongs to — a log stream, a toolchain.
    /// Free text, because the two callers name their parts differently and
    /// neither name means anything here beyond grouping a report.
    pub group: String,
    pub bytes: u64,
    /// Newest modification anywhere inside it. What "oldest" is ordered by.
    pub modified: std::time::SystemTime,
    /// Whether the directory it is in stays when this was the last thing in
    /// it. A log's date directory goes with its last entry; a build root's
    /// folders do not — a shared cache's folder is what every snapshot links
    /// to, and taken empty it left them all dangling.
    pub keeps_parent: bool,
}

/// What the logs directory currently holds.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct Usage {
    /// Everything under the root, managed or not — the number `du` gives.
    pub total_bytes: u64,
    /// The part of it a sweep can act on.
    pub managed_bytes: u64,
    /// Anything else under the root: a file somebody parked there, a
    /// directory from a tool that does not know about the streams.
    ///
    /// Counted, because the limit is on a directory and a page that reported
    /// only what it manages would show 400 MB for a directory holding 2 GB.
    /// Never swept, because it was not written here and nothing here knows
    /// what it is.
    pub unmanaged_bytes: u64,
    pub entries: usize,
    /// Bytes per group, by name.
    pub by_group: BTreeMap<String, u64>,
}

fn read_dir_sorted(dir: &Path) -> Vec<PathBuf> {
    let Ok(entries) = std::fs::read_dir(dir) else {
        return Vec::new();
    };
    let mut paths: Vec<PathBuf> = entries.flatten().map(|e| e.path()).collect();
    paths.sort();
    paths
}

/// Size, and when content was last written, for a file or a whole directory.
///
/// Only FILES contribute the timestamp. A directory's own mtime moves when
/// anything is added to or removed from it — including by the sweep itself, and
/// including at the moment it is created — so a session whose logs were all
/// written yesterday would look like it was written a moment ago. What orders a
/// sweep is when somebody last wrote something worth reading.
///
/// A directory holding no files therefore dates from the epoch, and is the
/// first thing a sweep takes. That is the right answer: an empty session
/// directory is what a killed run leaves behind.
fn measure(path: &Path) -> (u64, std::time::SystemTime) {
    let mut bytes = 0u64;
    let mut newest = std::time::UNIX_EPOCH;
    let mut stack = vec![path.to_path_buf()];
    while let Some(current) = stack.pop() {
        let Ok(meta) = std::fs::symlink_metadata(&current) else {
            continue;
        };
        if meta.is_dir() {
            if let Ok(children) = std::fs::read_dir(&current) {
                stack.extend(children.flatten().map(|c| c.path()));
            }
            continue;
        }
        if let Ok(modified) = meta.modified() {
            if modified > newest {
                newest = modified;
            }
        }
        bytes += meta.len();
    }
    (bytes, newest)
}

/// What a sweep did, or would do.
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct SweepReport {
    /// Paths removed, oldest first, with what each freed.
    pub removed: Vec<RemovedEntry>,
    pub freed_bytes: u64,
    /// What the directory holds now.
    pub remaining_bytes: u64,
    /// Entries left alone because something is writing them.
    pub protected: usize,
    /// True when the limit is still exceeded after removing everything
    /// removable — which means what is left is being written right now, is
    /// declared kept, or is not something this sweep manages at all.
    pub still_over: bool,
    /// Bytes under the root that NO sweep can reach, whatever the limit.
    ///
    /// Not the same as protected: a protected entry is one this sweep knows
    /// about and is declining to take right now, and the next sweep may take
    /// it. These bytes are ones no entry covers — a directory from an earlier
    /// layout, a file somebody parked there — so no limit an operator can set
    /// will ever reclaim them.
    ///
    /// Carried because the two were reported as one silence. A logs root
    /// accumulated 174 MB in the shape of a layout that predated the streams;
    /// every sweep walked it, matched nothing, and reported itself settled.
    /// Naming these bytes is what turns "lower the limit" into "move or
    /// delete that directory, because the limit is not what is holding it".
    pub unreachable_bytes: u64,
    /// Bytes this sweep had to free to put the VOLUME back above its floor,
    /// over and above whatever the configured cap asked for. Zero when the
    /// disk has room, which is the ordinary case.
    pub must_free_bytes: u64,
    /// Why the volume's free space could not be read, when it could not be.
    ///
    /// Carried rather than swallowed: "the disk is fine" and "nobody looked"
    /// are the same silence, and the second one is how a machine fills up
    /// with a limiter running.
    pub space_error: Option<String>,
    /// The limit this sweep actually enforced, after the minimum floor and the
    /// volume's own demand were applied to whatever cap was asked for.
    ///
    /// Reported because the caller cannot derive it. `wsb test` printed the
    /// number IT computed — "build cache: freed 9.4 GB (1 tree) to stay under
    /// 0 B" — on a machine where the sweep had floored that to 16 GB and swept
    /// against it. The sweep was right and its own account of itself was
    /// false, which is the most expensive kind of log line: it sends whoever
    /// reads it looking for a misconfigured cap that does not exist.
    pub enforced_limit: u64,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RemovedEntry {
    pub path: String,
    /// Which part of the directory it came out of.
    pub group: String,
    pub bytes: u64,
}

/// Whether this entry is, or contains, something the caller is writing.
/// Whether a sweep must leave `entry` alone, given what is protected.
pub fn protects(entry: &Path, protect: &[PathBuf]) -> bool {
    is_protected(entry, protect)
}

fn is_protected(entry: &Path, protect: &[PathBuf]) -> bool {
    // An entry holding something protected, and an entry inside a protected
    // tree — a snapshot in use protects its whole build root.
    protect
        .iter()
        .any(|held| held == entry || held.starts_with(entry) || entry.starts_with(held))
}

/// Remove one entry, and the date directory it leaves empty behind it.
///
/// The empty parent matters: a month of sweeping without it leaves thirty
/// empty dated directories, and a listing that is mostly empty directories is
/// one somebody has to open to find out that it is empty.
fn remove_entry(entry: &Entry) -> bool {
    let removed = if entry.path.is_dir() {
        std::fs::remove_dir_all(&entry.path)
    } else {
        std::fs::remove_file(&entry.path)
    };
    if let Err(error) = removed {
        tracing::warn!(path = %entry.path.display(), %error, "could not remove a log entry");
        return false;
    }
    if let Some(parent) = entry.path.parent().filter(|_| !entry.keeps_parent) {
        if parent.file_name().is_some() {
            // Only when it is empty: remove_dir refuses otherwise, which is
            // exactly the check wanted.
            let _ = std::fs::remove_dir(parent);
        }
    }
    true
}

/// A byte count as a person reads it.
pub fn human_bytes(bytes: u64) -> String {
    const UNITS: [&str; 5] = ["B", "KB", "MB", "GB", "TB"];
    let mut value = bytes as f64;
    let mut unit = 0;
    while value >= 1024.0 && unit + 1 < UNITS.len() {
        value /= 1024.0;
        unit += 1;
    }
    if unit == 0 {
        format!("{bytes} B")
    } else if value >= 100.0 {
        format!("{value:.0} {}", UNITS[unit])
    } else {
        format!("{value:.1} {}", UNITS[unit])
    }
}


/// Free space the volume must keep, whatever any cap is set to.
///
/// One gibibyte. Below this a machine stops being usable in ways that do not
/// look like a full disk: a link step dies with a bus error, a database write
/// fails mid-transaction, an editor cannot save. The cache is the one thing
/// on the volume that is reproducible by building again, so it is the one
/// thing that should go first — and it should go without anyone being asked,
/// because by the time somebody reads a warning the build has already failed.
pub const FREE_SPACE_FLOOR: u64 = 1024 * 1024 * 1024;

/// What the volume holding a path has: what this process may still write,
/// and how big it is.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VolumeSpace {
    pub available: u64,
    pub total: u64,
}

/// The space on the volume holding `path`.
///
/// The volume, not the directory: a cap is about a directory but a full disk
/// is about the filesystem it sits on, and the two are only the same when the
/// build root has a mount of its own.
///
/// Reported as an error rather than as a number when it cannot be read, so a
/// caller cannot mistake "unknown" for "plenty".
///
/// Read from the operating system, on every platform. The host panel read the
/// same fact by running `df`, which Windows does not have — so a Windows
/// machine reported no disk at all while this answered it correctly.
#[cfg(unix)]
pub fn volume_space(path: &Path) -> Result<VolumeSpace, String> {
    use std::os::unix::ffi::OsStrExt;

    let c_path = std::ffi::CString::new(path.as_os_str().as_bytes())
        .map_err(|_| format!("{} cannot be asked about: it contains a NUL", path.display()))?;
    // SAFETY: `stat` is written by statvfs on success and read only then.
    let mut stat: libc::statvfs = unsafe { std::mem::zeroed() };
    let code = unsafe { libc::statvfs(c_path.as_ptr(), &mut stat) };
    if code != 0 {
        return Err(format!(
            "cannot read free space on the volume holding {}: {}",
            path.display(),
            std::io::Error::last_os_error()
        ));
    }
    // `f_bavail` — what a non-root process may actually use. `f_bfree` counts
    // the reserved blocks too, which a build cannot write into, so using it
    // would report room that does not exist right when it matters.
    let block = if stat.f_frsize > 0 {
        stat.f_frsize
    } else {
        stat.f_bsize
    } as u64;
    Ok(VolumeSpace {
        available: (stat.f_bavail as u64).saturating_mul(block),
        total: (stat.f_blocks as u64).saturating_mul(block),
    })
}

/// The same answer on Windows, through `GetDiskFreeSpaceExW`.
///
/// This used to return an error saying the platform could not be asked, which
/// made the free-space floor unenforceable on the ONE platform where a guest
/// actually filled its disk: a Windows CUDA target reached 0 bytes free of 95
/// GB, and every sweep that ran on it reported `space_error` and carried on.
/// "Nobody could look" read as "there is nothing to do".
///
/// `lpFreeBytesAvailableToCaller` is the first out-parameter, and is the right
/// one for the same reason `f_bavail` is on Unix: it is what THIS process may
/// write, after quotas. The other two count space a build cannot have.
#[cfg(windows)]
pub fn volume_space(path: &Path) -> Result<VolumeSpace, String> {
    use std::os::windows::ffi::OsStrExt;

    // A directory, and NUL-terminated — the W form takes a wide string and
    // reads to the terminator.
    let mut wide: Vec<u16> = path.as_os_str().encode_wide().collect();
    if wide.contains(&0) {
        return Err(format!(
            "{} cannot be asked about: it contains a NUL",
            path.display()
        ));
    }
    wide.push(0);

    #[link(name = "kernel32")]
    extern "system" {
        fn GetDiskFreeSpaceExW(
            lpDirectoryName: *const u16,
            lpFreeBytesAvailableToCaller: *mut u64,
            lpTotalNumberOfBytes: *mut u64,
            lpTotalNumberOfFreeBytes: *mut u64,
        ) -> i32;
    }

    let mut available: u64 = 0;
    let mut total: u64 = 0;
    let mut free: u64 = 0;
    // SAFETY: `wide` is NUL-terminated and outlives the call; the three
    // out-parameters are owned locals, written only on success.
    let ok = unsafe {
        GetDiskFreeSpaceExW(wide.as_ptr(), &mut available, &mut total, &mut free)
    };
    if ok == 0 {
        return Err(format!(
            "cannot read free space on the volume holding {}: {}",
            path.display(),
            std::io::Error::last_os_error()
        ));
    }
    Ok(VolumeSpace { available, total })
}

#[cfg(not(any(unix, windows)))]
pub fn volume_space(path: &Path) -> Result<VolumeSpace, String> {
    Err(format!(
        "free space on the volume holding {} cannot be read on this platform",
        path.display()
    ))
}

/// How many bytes a sweep must free to put the volume back above the floor.
///
/// Zero when there is room — the ordinary answer, and the one that leaves a
/// sweep governed entirely by its configured cap.
pub fn must_free_for(path: &Path, floor: u64) -> (u64, Option<String>) {
    match volume_space(path).map(|space| space.available) {
        Ok(available) => (floor.saturating_sub(available), None),
        Err(error) => (0, Some(error)),
    }
}

/// Bring a directory under `max_bytes` by removing its oldest entries.
///
/// The entries are the CALLER's: this decides which of them go, not what they
/// are. `protect` names entries that must survive whatever the total is — the
/// log of an operation still running, a build tree something is writing into,
/// a bundle that costs hours to produce. A path inside a protected entry
/// protects the whole entry.
///
/// `dry_run` decides everything and removes nothing, which is what a settings
/// page calls to say "lowering this would delete 34 things" before anybody
/// lowers it.
///
/// `unreachable` is what the root holds that no entry covers. It is NOT swept
/// and never can be — but it counts against the limit, because the limit is on
/// a DIRECTORY. A sweep that compared only what it manages reports itself
/// settled while the directory it is supposed to bound grows without end.
pub fn sweep_entries(
    mut entries: Vec<Entry>,
    max_bytes: u64,
    minimum: u64,
    must_free: u64,
    unreachable: u64,
    protect: &[PathBuf],
    dry_run: bool,
) -> SweepReport {
    let managed: u64 = entries.iter().map(|e| e.bytes).sum();
    // What the DIRECTORY holds, which is what the limit is about.
    let total = managed.saturating_add(unreachable);

    // Two limits, and the sweep obeys the lower.
    //
    // The configured cap is a preference about how much build output to keep,
    // and `minimum` stops a mistyped one from sweeping a tree as fast as it is
    // written. `must_free` is not a preference: the VOLUME is nearly full, and
    // the next write fails whatever anyone configured. So it is applied AFTER
    // the minimum clamp — a floor that the cap cannot raise, because a cap
    // that wins here is a cap that chooses a dead machine over a smaller
    // cache.
    let configured = max_bytes.max(minimum);
    let limit = configured.min(total.saturating_sub(must_free));

    let mut report = SweepReport {
        remaining_bytes: total,
        must_free_bytes: must_free,
        unreachable_bytes: unreachable,
        enforced_limit: limit,
        ..Default::default()
    };
    if total <= limit {
        return report;
    }

    // Oldest first: what a sweep takes is the least likely to be wanted.
    entries.sort_by_key(|e| e.modified);

    let mut remaining = total;
    for entry in entries {
        if remaining <= limit {
            break;
        }
        if is_protected(&entry.path, protect) {
            report.protected += 1;
            continue;
        }
        if !dry_run && !remove_entry(&entry) {
            // A removal that failed frees nothing, and counting it as freed
            // would make the next sweep believe it is under the limit.
            continue;
        }
        remaining = remaining.saturating_sub(entry.bytes);
        report.freed_bytes += entry.bytes;
        report.removed.push(RemovedEntry {
            path: entry.path.display().to_string(),
            group: entry.group,
            bytes: entry.bytes,
        });
    }

    report.remaining_bytes = remaining;
    report.still_over = remaining > limit;
    report
}

/// One entry, measured. The unit both callers build their lists from.
pub fn entry(path: PathBuf, group: &str) -> Entry {
    let (bytes, modified) = measure(&path);
    Entry {
        path,
        group: group.to_string(),
        bytes,
        modified,
        keeps_parent: false,
    }
}

/// An entry whose directory stays when it is swept: see [`Entry::keeps_parent`].
pub fn entry_keeping_its_parent(path: PathBuf, group: &str) -> Entry {
    Entry { keeps_parent: true, ..entry(path, group) }
}

/// What a directory holds, by group and in total.
///
/// `unmanaged` is everything under the root that no entry covers — counted,
/// because the limit is on a DIRECTORY and a page reporting only what it
/// manages would show 400 MB for a directory holding 2 GB; never removed,
/// because it was not written here and nothing here knows what it is.
pub fn usage_of(root: &Path, entries: &[Entry], covered: &[PathBuf]) -> Usage {
    let mut by_group: BTreeMap<String, u64> = BTreeMap::new();
    let mut managed = 0u64;
    for entry in entries {
        *by_group.entry(entry.group.clone()).or_default() += entry.bytes;
        managed += entry.bytes;
    }

    let mut unmanaged = 0u64;
    for path in read_dir_sorted(root) {
        if covered.iter().any(|c| c == &path) {
            continue;
        }
        if entries.iter().any(|e| e.path == path || e.path.starts_with(&path)) {
            continue;
        }
        unmanaged += measure(&path).0;
    }

    Usage {
        total_bytes: managed + unmanaged,
        managed_bytes: managed,
        unmanaged_bytes: unmanaged,
        entries: entries.len(),
        by_group,
    }
}

/// Every path under `dir`, sorted — the shared listing both callers walk.
pub fn children(dir: &Path) -> Vec<PathBuf> {
    read_dir_sorted(dir)
}

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

    /// TEST11404: every platform this runs on can read its own free space.
    ///
    /// The free-space read was implemented for Unix and stubbed everywhere else
    /// with an error saying the platform could not be asked. That made
    /// `FREE_SPACE_FLOOR` — the rule that stops a disk filling — unenforceable
    /// on Windows, which is the one platform where a guest actually filled
    /// one: a CUDA target reached 0 bytes free of 95 GB while every sweep on
    /// it reported `space_error` and swept nothing. "Nobody could look" and
    /// "there is nothing to do" are the same silence, and the stub turned the
    /// first into the second.
    ///
    /// Asserted as a PROPERTY of wherever the tests run, so the Windows
    /// implementation is covered by the Windows suite rather than by nothing.
    #[test]
    fn test11404_the_volume_can_be_asked_how_much_room_it_has() {
        let dir = tempfile::tempdir().expect("a temporary directory");

        let available = volume_space(dir.path()).map(|space| space.available).unwrap_or_else(|error| {
            panic!(
                "free space is unreadable on this platform ({error}), so the \
                 free-space floor cannot be enforced here — which is how a \
                 guest reached 0 bytes free with a limiter running"
            )
        });

        // A volume holding a writable temporary directory has room on it. The
        // bound is deliberately loose: this is checking that a real number
        // came back, not how big anyone's disk is.
        assert!(
            available > 0,
            "the volume holding {} reports {available} bytes free while a \
             directory was just created on it",
            dir.path().display()
        );

        // And the floor is computed from it rather than skipped. A machine
        // with room needs nothing freed; the point is that an ANSWER came
        // back, so `space_error` is None and the sweep is governed by its cap.
        let (must_free, error) = must_free_for(dir.path(), FREE_SPACE_FLOOR);
        assert!(error.is_none(), "the floor could not be evaluated: {error:?}");
        if available >= FREE_SPACE_FLOOR {
            assert_eq!(must_free, 0, "a volume above the floor needs nothing freed");
        }
    }
}