termux-janitor

//! Bounded scan generation owned by `spec/PRODUCT.md` sections 4, 7, and 8
//! and `spec/FILESYSTEM_CAPABILITIES.md`.
//!
//! Traversal uses `lstat` semantics without following symlinks, crosses
//! mount boundaries, keeps one attempt outcome per enumerated entry, and
//! never recurses: the directory stack is a fixed array bounded by the
//! registered traversal depth. Every capacity is a registered limit;
//! exhaustion marks the affected root incomplete and increments the matching
//! omission counter instead of dropping data silently.
const std = @import("std");
const linux = std.os.linux;
const spec_data = @import("spec_data");
const config_mod = @import("config.zig");

pub const raw_path_bytes_max: u32 = @intCast(spec_data.limit_value.raw_path_bytes);
pub const raw_component_bytes_max: u32 = @intCast(spec_data.limit_value.raw_component_bytes);
pub const symlink_target_bytes_max: u32 = @intCast(spec_data.limit_value.symlink_target_bytes);
pub const traversal_depth_max: u32 = @intCast(spec_data.limit_value.traversal_depth);
pub const retained_findings_max: u32 = @intCast(spec_data.limit_value.retained_findings);
pub const retained_warnings_max: u32 = @intCast(spec_data.limit_value.retained_warnings);
pub const identity_domains_max: u32 = @intCast(spec_data.limit_value.filesystem_identity_domains);

/// Per-finding name bytes: one component per finding, so the retained-name
/// pool is the registered per-component bound times the retained count.
pub const name_pool_bytes: u64 = @as(u64, retained_findings_max) * raw_component_bytes_max;
/// Per-finding symlink target bytes for symlink findings only.
pub const target_pool_bytes: u64 = @as(u64, retained_findings_max) * symlink_target_bytes_max;

pub const no_parent: u32 = std.math.maxInt(u32);
pub const unknown_size: u64 = std.math.maxInt(u64);

pub const Kind = enum { file, directory, symlink, other };

pub const TargetStatus = enum { none, resolved, broken, loop, depth_exhausted, untrusted, unknown };

pub const AttemptOutcome = enum {
    retained,
    excluded,
    deduplicated,
    disappeared,
    metadata_failed,
    crossed_mount,
    capacity_exhausted,
    depth_exhausted,
    cancelled,
};

pub const Warning = struct {
    /// Bounded human-readable text; never operator path bytes.
    text: []const u8,
    finding: u32 = no_parent,
};

/// One retained filesystem object. Raw authority bytes are reconstructable
/// from the parent chain plus `name`; no display text is stored here.
pub const Finding = struct {
    parent: u32 = no_parent,
    name: []const u8 = &.{},
    depth: u32 = 0,
    kind: Kind = .file,
    dev_major: u32 = 0,
    dev_minor: u32 = 0,
    ino: u64 = 0,
    mnt_id: u64 = 0,
    nlink: u64 = 0,
    apparent_size: u64 = 0,
    blocks_known: bool = false,
    allocated_bytes: u64 = 0,
    mtime_sec: i64 = 0,
    mtime_nsec: u32 = 0,
    mtime_known: bool = false,
    /// Symlink target bytes inside the target pool, empty otherwise.
    target: []const u8 = &.{},
    target_status: TargetStatus = .none,
    target_dev_known: bool = false,
    target_ino: u64 = 0,
    /// Recursive apparent-size aggregate for directories; `unknown_size`
    /// when any descendant contribution is unknown.
    aggregate_apparent: u64 = 0,
    aggregate_known: bool = false,
    /// Set when the finding shares a trusted inode with another displayed
    /// row in the same aggregate scope (`TJ-SIZE-05`).
    non_additive: bool = false,
    root_index: u32 = 0,
    category: u16 = 0,
    manual_only: bool = true,
    selected: bool = false,
};

pub const Domain = struct {
    dev_major: u32,
    dev_minor: u32,
    mnt_id: u64,
};

pub const Ledger = struct {
    retained: u64 = 0,
    excluded: u64 = 0,
    deduplicated: u64 = 0,
    disappeared: u64 = 0,
    metadata_failed: u64 = 0,
    crossed_mount: u64 = 0,
    capacity_exhausted: u64 = 0,
    depth_exhausted: u64 = 0,
};

/// One scan generation. All storage is fixed at initialization.
pub const Scan = struct {
    findings: [retained_findings_max]Finding = undefined,
    findings_len: u32 = 0,
    warnings: [retained_warnings_max]Warning = undefined,
    warnings_len: u32 = 0,
    domains: [identity_domains_max]Domain = undefined,
    domains_len: u32 = 0,
    name_pool: [name_pool_bytes]u8 = undefined,
    name_pool_used: u64 = 0,
    target_pool: [target_pool_bytes]u8 = undefined,
    target_pool_used: u64 = 0,
    ledger: Ledger = .{},
    /// Realtime reference captured once before the first entry is examined.
    realtime_sec: i64 = 0,
    complete: bool = true,
    cancelled: bool = false,
    /// Finding index of each scanned root, ordered by root index; execution
    /// revalidation compares the reopened root against this identity
    /// (`TJ-EXEC-01`).
    root_findings: [config_mod.roots_max]u32 = undefined,
    root_findings_len: u32 = 0,

    pub fn finding(self: *const Scan, index: u32) *const Finding {
        std.debug.assert(index < self.findings_len);
        return &self.findings[index];
    }

    pub fn warn(self: *Scan, text: []const u8, finding_index: u32) void {
        if (self.warnings_len >= retained_warnings_max) {
            self.complete = false;
            return;
        }
        self.warnings[self.warnings_len] = .{ .text = text, .finding = finding_index };
        self.warnings_len += 1;
    }

    pub fn storeName(self: *Scan, name: []const u8) ?[]const u8 {
        if (name.len == 0 or name.len > raw_component_bytes_max) return null;
        if (self.name_pool_used + name.len > self.name_pool.len) return null;
        const start: usize = @intCast(self.name_pool_used);
        @memcpy(self.name_pool[start..][0..name.len], name);
        self.name_pool_used += name.len;
        return self.name_pool[start..][0..name.len];
    }

    pub fn storeTarget(self: *Scan, target: []const u8) ?[]const u8 {
        if (target.len > symlink_target_bytes_max) return null;
        if (self.target_pool_used + target.len > self.target_pool.len) return null;
        const start: usize = @intCast(self.target_pool_used);
        @memcpy(self.target_pool[start..][0..target.len], target);
        self.target_pool_used += target.len;
        return self.target_pool[start..][0..target.len];
    }

    fn domainIndex(self: *Scan, stat: *const linux.Statx) ?u32 {
        var index: u32 = 0;
        while (index < self.domains_len) : (index += 1) {
            const domain = self.domains[index];
            if (domain.dev_major == stat.dev_major and
                domain.dev_minor == stat.dev_minor and
                domain.mnt_id == stat.mnt_id) return index;
        }
        if (self.domains_len >= identity_domains_max) return null;
        self.domains[self.domains_len] = .{
            .dev_major = stat.dev_major,
            .dev_minor = stat.dev_minor,
            .mnt_id = stat.mnt_id,
        };
        self.domains_len += 1;
        return self.domains_len - 1;
    }

    /// Reconstructs the raw absolute path of `index` into `out` by walking
    /// the parent chain. Bounded by the registered path length.
    pub fn pathOf(self: *const Scan, index: u32, out: *[raw_path_bytes_max]u8) []const u8 {
        var chain: [traversal_depth_max + 2]u32 = undefined;
        var depth: usize = 0;
        var current = index;
        while (current != no_parent and depth < chain.len) {
            chain[depth] = current;
            depth += 1;
            current = self.findings[current].parent;
        }
        std.debug.assert(depth > 0 and depth <= chain.len);
        var written: usize = 0;
        var level = depth;
        while (level > 0) {
            level -= 1;
            const node = self.findings[chain[level]];
            const name = node.name;
            if (written == 0) {
                // The root's stored name is its absolute path.
                std.debug.assert(written + name.len <= out.len);
                @memcpy(out[written..][0..name.len], name);
                written += name.len;
                continue;
            }
            std.debug.assert(written + 1 + name.len <= out.len);
            out[written] = '/';
            written += 1;
            @memcpy(out[written..][0..name.len], name);
            written += name.len;
        }
        return out[0..written];
    }
};

const DirLevel = struct {
    dir: std.Io.Dir,
    finding_index: u32,
    iterator: std.Io.Dir.Iterator,
};

pub var name_nul: [raw_component_bytes_max + 1:0]u8 = undefined;

/// Reads one statx record for `name` inside `dir_fd` without following
/// symlinks. `name` must include a NUL terminator in its buffer.
/// Stats an open descriptor itself (empty path requires `AT_EMPTY_PATH`).
pub fn statxFd(fd: std.posix.fd_t) !linux.Statx {
    var stat: linux.Statx = std.mem.zeroes(linux.Statx);
    const mask: linux.STATX = .{
        .TYPE = true,
        .NLINK = true,
        .INO = true,
        .SIZE = true,
        .BLOCKS = true,
        .MTIME = true,
        .MNT_ID = true,
    };
    const rc = linux.statx(fd, "", linux.AT.EMPTY_PATH, mask, &stat);
    if (linux.errno(rc) != .SUCCESS) return error.StatFailed;
    if (!stat.mask.TYPE or !stat.mask.INO or !stat.mask.MNT_ID) return error.StatIncomplete;
    return stat;
}

pub fn statxAt(dir_fd: std.posix.fd_t, name: [*:0]const u8) !linux.Statx {
    var stat: linux.Statx = std.mem.zeroes(linux.Statx);
    const mask: linux.STATX = .{
        .TYPE = true,
        .NLINK = true,
        .INO = true,
        .SIZE = true,
        .BLOCKS = true,
        .MTIME = true,
        .MNT_ID = true,
    };
    const rc = linux.statx(dir_fd, name, linux.AT.SYMLINK_NOFOLLOW, mask, &stat);
    if (linux.errno(rc) != .SUCCESS) return error.StatFailed;
    if (!stat.mask.TYPE or !stat.mask.INO or !stat.mask.MNT_ID) return error.StatIncomplete;
    return stat;
}

pub fn kindOf(stat: *const linux.Statx) ?Kind {
    const kind_bits = stat.mode & linux.S.IFMT;
    return switch (kind_bits) {
        linux.S.IFREG => .file,
        linux.S.IFDIR => .directory,
        linux.S.IFLNK => .symlink,
        else => .other,
    };
}

pub const Root = struct {
    /// Absolute raw path of the configured root (already normalized).
    path: []const u8,
    finding: u32 = no_parent,
    open_failed: bool = false,
};

/// Opens one configured root directory and records its finding.
fn openRoot(scan: *Scan, root_path: []const u8) ?std.Io.Dir {
    const fd = std.posix.openat(
        std.posix.AT.FDCWD,
        root_path,
        .{ .ACCMODE = .RDONLY, .DIRECTORY = true, .CLOEXEC = true, .NOFOLLOW = true },
        0,
    ) catch {
        scan.complete = false;
        scan.warn("warning: scan root is inaccessible", no_parent);
        return null;
    };
    return .{ .handle = fd };
}

/// Runs one scan generation over the configured roots. Single pass, no
/// recursion, bounded pools. Every enumeration checkpoint observes the
/// cancellation flag and stops admission promptly when set.
pub fn run(scan: *Scan, config: *const config_mod.Config, roots: []const Root) void {
    const reference = std.Io.Timestamp.now(std.Io.Threaded.global_single_threaded.io(), .real);
    scan.realtime_sec = @intCast(@divTrunc(reference.nanoseconds, std.time.ns_per_s));
    var stack: [traversal_depth_max]DirLevel = undefined;
    var root_index: u32 = 0;
    while (root_index < roots.len) : (root_index += 1) {
        if (scan.cancelled) {
            scan.complete = false;
            return;
        }
        const root_path = roots[root_index].path;
        var dir = openRoot(scan, root_path) orelse continue;
        defer dir.close(std.Io.Threaded.global_single_threaded.io());
        const stat = statxFd(dir.handle) catch {
            scan.complete = false;
            scan.warn("warning: scan root metadata is unavailable", no_parent);
            continue;
        };
        if (scan.findings_len >= retained_findings_max) {
            scan.ledger.capacity_exhausted += 1;
            scan.complete = false;
            continue;
        }
        const stored_name = scan.storeName(root_path) orelse {
            scan.ledger.capacity_exhausted += 1;
            scan.complete = false;
            continue;
        };
        const index = scan.findings_len;
        scan.findings[index] = .{
            .parent = no_parent,
            .name = stored_name,
            .depth = 0,
            .kind = .directory,
            .dev_major = stat.dev_major,
            .dev_minor = stat.dev_minor,
            .ino = stat.ino,
            .mnt_id = stat.mnt_id,
            .nlink = stat.nlink,
            .apparent_size = if (stat.mask.SIZE) stat.size else unknown_size,
            .blocks_known = stat.mask.BLOCKS,
            .allocated_bytes = if (stat.mask.BLOCKS)
                std.math.mul(u64, stat.blocks, 512) catch unknown_size
            else
                unknown_size,
            .mtime_sec = if (stat.mask.MTIME) stat.mtime.sec else 0,
            .mtime_nsec = if (stat.mask.MTIME) stat.mtime.nsec else 0,
            .mtime_known = stat.mask.MTIME,
            .root_index = root_index,
        };
        scan.findings_len += 1;
        scan.root_findings[scan.root_findings_len] = index;
        scan.root_findings_len += 1;
        scan.ledger.retained += 1;
        roots_scan: {
            const io = std.Io.Threaded.global_single_threaded.io();
            var level: usize = 1;
            stack[0] = .{
                .dir = dir,
                .finding_index = index,
                .iterator = std.Io.Dir.iterate(dir),
            };
            while (level > 0) {
                if (scan.cancelled) {
                    scan.complete = false;
                    scan.complete = false;
                    break :roots_scan;
                }
                const top = &stack[level - 1];
                const entry = top.iterator.next(io) catch {
                    scan.complete = false;
                    scan.warn("warning: directory enumeration failed", top.finding_index);
                    level -= 1;
                    continue;
                };
                const found = entry orelse {
                    level -= 1;
                    continue;
                };
                const admitted = admit(
                    scan,
                    config,
                    top.dir.handle,
                    top.finding_index,
                    level,
                    found.name,
                    &stack,
                );
                switch (admitted) {
                    .stop => break :roots_scan,
                    .keep => {},
                    .descend => level += 1,
                }
            }
        }
    }
}

/// One admission outcome: `stop` aborts the scan, `keep` continues the
/// current level, and `descend` announces a child level pushed onto the
/// traversal stack so the caller advances (`TJ-SCAN-01`).
const Admit = enum { stop, keep, descend };

fn admit(
    scan: *Scan,
    config: *const config_mod.Config,
    parent_dir_fd: std.posix.fd_t,
    parent_finding: u32,
    parent_level: usize,
    name: []const u8,
    stack: *[traversal_depth_max]DirLevel,
) Admit {
    if (name.len > raw_component_bytes_max) {
        scan.ledger.capacity_exhausted += 1;
        scan.complete = false;
        return .keep;
    }
    @memcpy(name_nul[0..name.len], name);
    name_nul[name.len] = 0;
    var stat = statxAt(parent_dir_fd, &name_nul) catch {
        scan.ledger.metadata_failed += 1;
        scan.complete = false;
        return .keep;
    };
    const kind = kindOf(&stat) orelse .other;
    // Exclusion boundary check uses the reconstructed raw path.
    var path_buffer: [raw_path_bytes_max]u8 = undefined;
    const parent_path = scan.pathOf(parent_finding, &path_buffer);
    var joined: [raw_path_bytes_max]u8 = undefined;
    const path = std.fmt.bufPrint(&joined, "{s}/{s}", .{ parent_path, name }) catch {
        scan.ledger.capacity_exhausted += 1;
        scan.complete = false;
        return .keep;
    };
    if (config.excluded(path)) {
        scan.ledger.excluded += 1;
        return .keep;
    }
    if (scan.findings_len >= retained_findings_max) {
        scan.ledger.capacity_exhausted += 1;
        scan.complete = false;
        return .stop;
    }
    const stored_name = scan.storeName(name) orelse {
        scan.ledger.capacity_exhausted += 1;
        scan.complete = false;
        return .stop;
    };
    const index = scan.findings_len;
    scan.findings[index] = .{
        .parent = parent_finding,
        .name = stored_name,
        .depth = @intCast(parent_level),
        .kind = kind,
        .dev_major = stat.dev_major,
        .dev_minor = stat.dev_minor,
        .ino = stat.ino,
        .mnt_id = stat.mnt_id,
        .nlink = stat.nlink,
        .apparent_size = if (stat.mask.SIZE) stat.size else unknown_size,
        .blocks_known = stat.mask.BLOCKS,
        .allocated_bytes = if (stat.mask.BLOCKS)
            std.math.mul(u64, stat.blocks, 512) catch unknown_size
        else
            unknown_size,
        .mtime_sec = if (stat.mask.MTIME) stat.mtime.sec else 0,
        .mtime_nsec = if (stat.mask.MTIME) stat.mtime.nsec else 0,
        .mtime_known = stat.mask.MTIME,
        .root_index = scan.findings[parent_finding].root_index,
    };
    scan.findings_len += 1;
    scan.ledger.retained += 1;
    if (kind == .symlink) tryRecordTarget(scan, parent_dir_fd, &stat, index);
    if (kind == .directory) {
        if (parent_level >= traversal_depth_max) {
            scan.ledger.depth_exhausted += 1;
            scan.complete = false;
            scan.warn("warning: traversal depth bound reached", index);
            return .keep;
        }
        const child_fd = std.posix.openat(
            parent_dir_fd,
            name_nul[0..name.len :0],
            .{ .ACCMODE = .RDONLY, .DIRECTORY = true, .CLOEXEC = true, .NOFOLLOW = true },
            0,
        ) catch {
            scan.ledger.metadata_failed += 1;
            scan.complete = false;
            return .keep;
        };
        const child_dir: std.Io.Dir = .{ .handle = child_fd };
        stack[parent_level] = .{
            .dir = child_dir,
            .finding_index = index,
            .iterator = std.Io.Dir.iterate(child_dir),
        };
        return .descend;
    }
    return .keep;
}

fn tryRecordTarget(scan: *Scan, parent_dir_fd: std.posix.fd_t, stat: *const linux.Statx, index: u32) void {
    var target_buffer: [symlink_target_bytes_max + 1]u8 = undefined;
    const length = linux.readlinkat(
        parent_dir_fd,
        &name_nul,
        &target_buffer,
        symlink_target_bytes_max + 1,
    );
    if (linux.errno(length) != .SUCCESS) {
        scan.findings[index].target_status = .unknown;
        return;
    }
    const bounded: usize = @intCast(length);
    if (bounded > symlink_target_bytes_max) {
        scan.findings[index].target_status = .unknown;
        return;
    }
    const stored = scan.storeTarget(target_buffer[0..bounded]) orelse {
        scan.findings[index].target_status = .unknown;
        return;
    };
    scan.findings[index].target = stored;
    resolveTarget(scan, stat, index, target_buffer[0..bounded], 0);
}

fn resolveTarget(
    scan: *Scan,
    origin: *const linux.Statx,
    index: u32,
    target: []const u8,
    hops: u32,
) void {
    if (hops > symlink_resolution_hops_max) {
        scan.findings[index].target_status = .loop;
        return;
    }
    // Version 1 resolves targets in the host namespace only; proot
    // namespaces require their adapter and stay `untrusted`.
    if (hops > 0 or (target.len > 0 and target[0] == '/')) {
        const fd = std.posix.openat(
            std.posix.AT.FDCWD,
            target,
            .{ .ACCMODE = .RDONLY, .CLOEXEC = true },
            0,
        ) catch {
            scan.findings[index].target_status = .broken;
            return;
        };
        defer _ = std.os.linux.close(fd);
        const stat = statxAt(fd, "") catch {
            scan.findings[index].target_status = .unknown;
            return;
        };
        if (stat.dev_major != origin.dev_major or stat.dev_minor != origin.dev_minor) {
            scan.findings[index].target_status = .untrusted;
            return;
        }
        scan.findings[index].target_status = .resolved;
        scan.findings[index].target_ino = stat.ino;
        scan.findings[index].target_dev_known = true;
        return;
    }
    // Relative host-namespace resolution walks from the symlink parent.
    scan.findings[index].target_status = .unknown;
}

pub const symlink_resolution_hops_max: u32 = 40;