Skip to content
zit Artifact [bcfd037acc]
Login

Artifact [bcfd037acc]

Check-ins Using Download Hex

Artifact bcfd037acc26f75ab7da5c628c08ac67051311b7bdf7e492d5d429f807fa5416:

//! Store byte accounting — the one physical frame walk over a `.zit`, and the
//! per-`FrameKind` totals it produces.
//!
//! This exists so the store can be interrogated about its own contents without
//! anyone guessing. Two numbers about a store are routinely confused, and the
//! confusion is the reason this module is separate and shared:
//!
//!   * the STORE size is the `.zit` file — header, frame headers, padding,
//!     content, everything;
//!   * the CONTENT bytes are the sum of the artifact frames' payload lengths,
//!     which is a strictly smaller number and the only one that answers "how
//!     many bytes of artifact does this repository hold".
//!
//! Deriving the second from the first would fold in the header and the padding
//! slack and produce something that looks like a measurement and is not one.
//! So content is MEASURED, frame by frame, here — and callers get both numbers
//! as separate fields so neither can stand in for the other.
//!
//! The one testable property is exact accounting: every byte of the file is the
//! 64-byte header or part of exactly one frame span, so
//! `header + raw + zlib + delta + config + shun == file size`. The walk proves
//! it by tiling the file exactly; falling short or overshooting is
//! `error.Corrupt`.
//!
//! This walker classifies from raw prefix bytes, so it restates `FrameKind`'s
//! universe independently of `LogStore`. That second statement is derived from
//! the enum (`kind_count`), never hand-written: a kind added to `logstore.zig`
//! but missed here turns every repository holding one into `error.Corrupt` for
//! every consumer of this module.
//!
//! Read-only by construction: positional reads of each frame's 10-byte prefix,
//! no payload decode, no write path. The caller is expected to have opened the
//! store through `LogStore.openReadOnly` first, which whole-frame-CRC-verifies
//! every frame — so the prefix bytes this walk trusts have been checked.

const std = @import("std");
const storage = @import("storage.zig");
const logstore = @import("logstore.zig");

/// A failed read of the backing file (`Storage`) or a frame layout that does
/// not tile the file (`Corrupt`). Never `anyerror`.
pub const Error = error{ Storage, Corrupt };

/// Frame kinds, in `logstore.FrameKind` order, used to index the arrays below.
const raw_k: usize = @intFromEnum(logstore.FrameKind.raw);
const zlib_k: usize = @intFromEnum(logstore.FrameKind.zlib);
const delta_k: usize = @intFromEnum(logstore.FrameKind.delta);
const config_k: usize = @intFromEnum(logstore.FrameKind.config);
const shun_k: usize = @intFromEnum(logstore.FrameKind.shun);

/// How many frame kinds the arrays below account for, and the bound the flag
/// byte is checked against. NOT hand-written and not restated from a named kind
/// either: it is `logstore.frame_kind_count`, folded from `FrameKind`'s own
/// fields. This file holds a second, parallel statement of the frame-kind
/// universe (it classifies from raw prefix bytes rather than through
/// `LogStore`), and a width tied to a named kind — `shun_k + 1` — reads as
/// derived while being exactly as stale-able as a literal `5`: adding a kind to
/// `logstore.zig` would not change it, and every repository holding one would
/// become `error.Corrupt` for `zit stat` and the storage bench. Only the fold
/// actually widens. Public so a per-kind table elsewhere (the benchmark's
/// report) sizes itself from the same number and fails to compile if it drifts.
pub const kind_count: usize = logstore.frame_kind_count;

/// Per-kind byte accounting. Indexed by `@intFromEnum(FrameKind)` (raw=0,
/// zlib=1, delta=2, config=3, shun=4). `on_disk` is the aligned frame span;
/// `payload` is the on-disk (raw/container) payload length; `overhead` is
/// header+padding (`on_disk - payload`).
pub const Breakdown = struct {
    count: [kind_count]u64 = .{0} ** kind_count,
    on_disk: [kind_count]u64 = .{0} ** kind_count,
    payload: [kind_count]u64 = .{0} ** kind_count,
    overhead: [kind_count]u64 = .{0} ** kind_count,

    /// Summed over every kind — the exact-accounting identity `header_len +
    /// totalOnDisk() == file_size` depends on omitting none, so these fold the
    /// whole array rather than listing indices.
    pub fn totalOnDisk(self: Breakdown) u64 {
        var n: u64 = 0;
        for (self.on_disk) |v| n += v;
        return n;
    }

    pub fn totalOverhead(self: Breakdown) u64 {
        var n: u64 = 0;
        for (self.overhead) |v| n += v;
        return n;
    }

    /// Every frame in the file, of every kind — the count that belongs beside
    /// `totalOnDisk()` in a report, folded for the same reason: a total spelled
    /// out as a sum of named indices silently stops counting a kind the moment
    /// one is added, and then disagrees with the byte total printed next to it.
    pub fn totalFrames(self: Breakdown) u64 {
        var n: u64 = 0;
        for (self.count) |v| n += v;
        return n;
    }

    /// Content artifacts: every frame that is neither the repository's config
    /// record nor a shun-table row (neither is content-addressed, and neither
    /// is ever interned). This is the artifact census `--artifacts` enumerates.
    pub fn artifacts(self: Breakdown) u64 {
        return self.count[raw_k] + self.count[zlib_k] + self.count[delta_k];
    }

    /// Artifacts stored whole rather than against a base (raw or zlib).
    pub fn fullForm(self: Breakdown) u64 {
        return self.count[raw_k] + self.count[zlib_k];
    }

    pub fn deltas(self: Breakdown) u64 {
        return self.count[delta_k];
    }

    /// `contentBytes` split the same way `fullForm`/`deltas` split the census,
    /// so a store's payload can be attributed to the two storage forms rather
    /// than inferred from counts. The counts alone mislead badly: a store can
    /// be a minority full-form by artifact and a large majority full-form by
    /// byte, because an artifact is stored whole precisely when delta did not
    /// pay -- the large, poorly-compressible ones. Decompression cost tracks
    /// these bytes, not the census, so a reader comparing pack efficiency or
    /// sizing a decode budget needs the split measured rather than assumed.
    pub fn fullFormBytes(self: Breakdown) u64 {
        return self.payload[raw_k] + self.payload[zlib_k];
    }

    pub fn deltaBytes(self: Breakdown) u64 {
        return self.payload[delta_k];
    }

    /// The measured artifact payload bytes — NOT the file size, and never to
    /// be substituted for it. Excludes the config frame, every frame header,
    /// and every padding byte.
    pub fn contentBytes(self: Breakdown) u64 {
        return self.payload[raw_k] + self.payload[zlib_k] + self.payload[delta_k];
    }

    /// Frame header + padding bytes spent on the content artifacts.
    pub fn contentOverhead(self: Breakdown) u64 {
        return self.overhead[raw_k] + self.overhead[zlib_k] + self.overhead[delta_k];
    }

    /// The config record's whole frame span (§9.1 project code and defaults) —
    /// repository metadata, not content.
    pub fn configBytes(self: Breakdown) u64 {
        return self.on_disk[config_k];
    }

    /// The repository shun table's whole frame span — repository metadata like
    /// the config record, not content, and counted separately from both.
    pub fn shunBytes(self: Breakdown) u64 {
        return self.on_disk[shun_k];
    }

    pub fn shunRows(self: Breakdown) u64 {
        return self.count[shun_k];
    }
};

/// A frame's on-disk span (logstore.zig frame layout): the fixed header
/// (`len|flags|hash_len|prefix_crc|hash|delta_of|header_crc` = 22 + hash_len),
/// the payload, and the 4-byte whole-frame CRC, padded up to an 8-byte
/// boundary — i.e. `align8(26 + hash_len + payload_len)`.
pub fn frameSpan(hash_len_b: u8, payload_len: u64) u64 {
    return alignUp8(26 + @as(u64, hash_len_b) + payload_len);
}

fn alignUp8(n: u64) u64 {
    return (n + 7) / 8 * 8;
}

/// Walk every frame from its physical bytes, classifying by the prefix flag
/// byte and summing spans by kind. Reads only the 10-byte fixed prefix
/// (`payload_len|flags|hash_len|prefix_crc`) of each frame — no payload, no
/// decode — so it is a cheap structural scan, one pass, independent of the
/// artifact count. Reaching `file_size` exactly is the exact-accounting
/// invariant.
/// A read-ahead window over the store file, sized so the walk below reads the
/// file in few large sequential preads instead of one 10-byte pread per frame.
/// `FileStorage.pread` is unbuffered — a real kernel transition per call — and
/// a census walk visits EVERY frame, so per-frame preads put an O(frames)
/// syscall floor under `zit stat` (~150k calls, ~0.2s, on a 148k-artifact
/// store; #121). A frame whose span exceeds the window costs one refill at its
/// successor's offset — the window never re-reads a skipped payload it has
/// already passed. Purely an I/O strategy: the bytes classified are the same.
const PrefixWindow = struct {
    sfile: storage.StorageFile,
    file_size: u64,
    buf: [window_len]u8 = undefined,
    start: u64 = 0,
    len: usize = 0,

    const window_len: usize = 64 * 1024;

    /// The 10-byte fixed prefix at `offset`, served from the window, refilling
    /// it from the file when `offset` falls outside. A refill that cannot
    /// produce 10 bytes is the same truncation the unbuffered read called
    /// `Corrupt`.
    fn prefix(self: *PrefixWindow, offset: u64) Error![10]u8 {
        if (offset < self.start or offset + 10 > self.start + self.len) {
            const want: usize = @intCast(@min(@as(u64, window_len), self.file_size -| offset));
            if (want < 10) return error.Corrupt;
            const n = self.sfile.pread(offset, self.buf[0..want]) catch return error.Storage;
            if (n < 10) return error.Corrupt;
            self.start = offset;
            self.len = n;
        }
        const at: usize = @intCast(offset - self.start);
        return self.buf[at..][0..10].*;
    }
};

pub fn walk(sfile: storage.StorageFile, file_size: u64) Error!Breakdown {
    std.debug.assert(file_size >= logstore.header_len);
    var bd = Breakdown{};
    var offset: u64 = logstore.header_len;
    // Each frame spans >= 8 bytes; the count can never exceed file_size/8.
    const max_frames: u64 = file_size / logstore.frame_align + 1;
    var seen: u64 = 0;
    var window = PrefixWindow{ .sfile = sfile, .file_size = file_size };
    while (offset < file_size) {
        seen += 1;
        if (seen > max_frames) return error.Corrupt;
        const prefix = try window.prefix(offset);
        const payload_len = std.mem.readInt(u32, prefix[0..4], .little);
        const flags = prefix[4];
        const hlen = prefix[5];
        // Every kind `FrameKind` names, and nothing beyond it. Bounded by
        // `kind_count` so the array indexing below cannot run off the end: this
        // guard and the array width are the same fact, stated once.
        if (flags >= kind_count) return error.Corrupt;
        if (hlen < logstore.min_hash_len or hlen > logstore.max_hash_len) return error.Corrupt;
        const span = frameSpan(hlen, payload_len);
        const k: usize = flags;
        bd.count[k] += 1;
        bd.on_disk[k] += span;
        bd.payload[k] += payload_len;
        bd.overhead[k] += span - payload_len;
        offset += span;
    }
    if (offset != file_size) return error.Corrupt; // frame boundaries must tile the file exactly
    std.debug.assert(logstore.header_len + bd.totalOnDisk() == file_size); // exact accounting
    return bd;
}

// ---------------------------------------------------------------------------
// Tests — the exact-accounting invariant that makes every consumer's number
// trustworthy, over a store built through the public LogStore write path.
// ---------------------------------------------------------------------------

const testing = std.testing;

/// Builds a store in a temp `.zit` holding `n` artifacts whose bodies are near
/// enough to each other that the store's own base selection produces delta
/// frames alongside full-form ones. Returns the file and its size.
const Fixture = struct {
    file: std.Io.File,
    size: u64,

    fn build(io: std.Io, dir: std.Io.Dir, n: usize) !Fixture {
        const file = try dir.createFile(io, ".zit", .{ .read = true });
        var fs = storage.FileStorage.init(io, file, 0);
        var log = try logstore.LogStore.open(testing.allocator, fs.storageFile(), 0);
        defer log.deinit(testing.allocator);

        var body: [512]u8 = undefined;
        var base: ?logstore.Rid = null;
        for (0..n) |i| {
            @memset(&body, 'a');
            // A short, varying prefix on an otherwise identical body: the
            // shared tail is what the delta encoder can reference, so the
            // corpus carries full-form and delta frames both.
            _ = try std.fmt.bufPrint(body[0..16], "artifact {d:0>6} ", .{i});
            var h: [32]u8 = undefined;
            std.crypto.hash.sha2.Sha256.hash(&body, &h, .{});
            // Every 4th artifact is stored raw, which also gives later deltas
            // a raw base — so all three content kinds appear.
            base = if (i % 4 == 0)
                try log.put(&h, &body)
            else
                try log.putArtifact(&h, &body, base);
        }
        try log.putConfig(.{
            .hash_policy = 0,
            .default_branch = "trunk",
            .project_id = "zit-storestat-test",
            .project_code = "0000000000000000",
        });
        try log.commit();
        const size = try fs.storageFile().size();
        return .{ .file = file, .size = size };
    }
};

test "storestat: the frame walk tiles the file exactly (header + every kind == file size)" {
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = testing.io;

    const fx = try Fixture.build(io, tmp.dir, 64);
    var file = fx.file;
    defer file.close(io);

    var fs = storage.FileStorage.init(io, file, fx.size);
    const bd = try walk(fs.storageFile(), fx.size);

    // Nothing unaccounted: the whole file is the header plus every frame span.
    try testing.expectEqual(fx.size, logstore.header_len + bd.totalOnDisk());
    // Per kind, overhead is exactly header+padding.
    for (0..kind_count) |k| {
        try testing.expectEqual(bd.on_disk[k], bd.payload[k] + bd.overhead[k]);
    }
    // Exactly one config frame; the rest are content.
    try testing.expectEqual(@as(u64, 1), bd.count[config_k]);
    try testing.expectEqual(@as(u64, 64), bd.artifacts());
    try testing.expectEqual(bd.artifacts(), bd.fullForm() + bd.deltas());
}

test "storestat: a store holding shun rows still tiles exactly and counts them apart" {
    // This walker restates `FrameKind`'s universe from raw prefix bytes, so a
    // kind added to `logstore.zig` and missed here does not degrade gracefully:
    // the flag guard rejects it and EVERY repository holding one becomes
    // `error.Corrupt` to `zit stat` and to the storage benchmark. Pin the
    // newest kind end to end — walked, tiled, and accounted as metadata rather
    // than as content.
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = testing.io;

    const file = try tmp.dir.createFile(io, ".zit", .{ .read = true });
    defer file.close(io);
    var fs = storage.FileStorage.init(io, file, 0);
    var size: u64 = undefined;
    {
        var log = try logstore.LogStore.open(testing.allocator, fs.storageFile(), 0);
        defer log.deinit(testing.allocator);
        _ = try log.put("storestat-shun-held-hash-000001", "held content");
        try log.putShun("s" ** 32, "takedown", 1753000000);
        try log.putShun("t" ** 20, "", 1753000001);
        try log.commit();
        size = log.size();
    }

    var fs2 = storage.FileStorage.init(io, file, size);
    const bd = try walk(fs2.storageFile(), size);

    try testing.expectEqual(@as(u64, 2), bd.shunRows());
    try testing.expect(bd.shunBytes() > 0);
    // A tombstone is not an artifact: it must not inflate the content census.
    try testing.expectEqual(@as(u64, 1), bd.artifacts());
    // Exact accounting still holds with the new kind in the file.
    try testing.expectEqual(size, logstore.header_len + bd.totalOnDisk());
    try testing.expectEqual(
        size,
        logstore.header_len + bd.contentBytes() + bd.contentOverhead() + bd.configBytes() + bd.shunBytes(),
    );
}

test "storestat: content bytes are strictly smaller than the store size" {
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = testing.io;

    const fx = try Fixture.build(io, tmp.dir, 64);
    var file = fx.file;
    defer file.close(io);

    var fs = storage.FileStorage.init(io, file, fx.size);
    const bd = try walk(fs.storageFile(), fx.size);

    // The honesty property in its primitive form: content is measured, so it
    // cannot equal (or exceed) the file, which also carries the header, every
    // frame header, and the padding slack.
    try testing.expect(bd.contentBytes() > 0);
    try testing.expect(bd.contentBytes() < fx.size);
    // ...and the difference is fully explained, byte for byte.
    try testing.expectEqual(
        fx.size,
        logstore.header_len + bd.contentBytes() + bd.contentOverhead() + bd.configBytes(),
    );
}

test "storestat: the walk agrees with the store's own per-rid view" {
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = testing.io;

    const fx = try Fixture.build(io, tmp.dir, 64);
    var file = fx.file;
    defer file.close(io);

    var fs = storage.FileStorage.init(io, file, fx.size);
    const bd = try walk(fs.storageFile(), fx.size);

    var fs2 = storage.FileStorage.init(io, file, fx.size);
    var store = try logstore.LogStore.openReadOnly(testing.allocator, fs2.storageFile());
    defer store.deinit(testing.allocator);
    const rids = try store.ridsInPersistedOrder(testing.allocator);
    defer testing.allocator.free(rids);

    // Two independent views of the same frames: the physical walk and the
    // public rid API. Both the count and the payload total must agree, which
    // is what lets the CLI enumerate through the API and total through the walk.
    var api_payload: u64 = 0;
    for (rids) |rid| api_payload += store.payloadLenOf(rid);
    try testing.expectEqual(@as(usize, bd.artifacts()), rids.len);
    try testing.expectEqual(bd.contentBytes(), api_payload);
}

test "storestat: a truncated store does not tile the file and is rejected" {
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    const io = testing.io;

    const fx = try Fixture.build(io, tmp.dir, 8);
    var file = fx.file;
    defer file.close(io);

    // Claim a size one byte short of a frame boundary: the walk must overshoot
    // and refuse rather than report a plausible-looking partial total.
    var fs = storage.FileStorage.init(io, file, fx.size - 1);
    try testing.expectError(error.Corrupt, walk(fs.storageFile(), fx.size - 1));
}