Skip to content
zit Artifact [f37607feb9]
Login

Artifact [f37607feb9]

Artifact f37607feb90ac8e7c8c3df91df26514122df5ddfd7fe815fcc9dc59682a2e4c2:


//! `zit frames`: stream the artifacts appended after a cursor, for
//! incremental consumers.

const std = @import("std");
const zit = @import("zit");
const cli = @import("zit").cli;
const logstore = @import("zit").logstore;
const Repository = @import("zit").Repository;
const artifact = zit.artifact;
const diagnostics = @import("../cli/diagnostics.zig");
const help_pages = @import("../cli/help.zig");
const stateOom = diagnostics.stateOom;
const repoOpenFail = diagnostics.repoOpenFail;
const openRepo = diagnostics.openRepo;
const frames_help = help_pages.frames_help;

// ---------------------------------------------------------------------------
// frames: the incremental-consumer read seam. Emits every artifact
// appended after a cursor as whole raw bytes, self-framed, with a trailer
// carrying the new cursor and a prefix-validation token. The token is the
// store's own LogKey — the O(1) freshness proof the derived-cache tier
// already trusts — so appends keep a cursor alive and a pack/shun rewrite
// (a new generation, new layout) kills it detectably.
// ---------------------------------------------------------------------------

/// Decode a `--since` cursor: the decimal rid count a previous trailer
/// emitted. Null on any malformation — the caller folds it into the
/// cursor-invalid refusal (a forged cursor is indistinguishable from a dead
/// one, and both have the same remedy: re-read from zero).
fn framesParseCursor(text: []const u8) ?u64 {
    return std.fmt.parseInt(u64, text, 10) catch null;
}

/// Decode a `--verify` token: the four LogKey fields a previous trailer
/// emitted, dash-joined decimal. Null on any malformation.
fn framesParseToken(text: []const u8) ?logstore.LogStore.LogKey {
    var it = std.mem.splitScalar(u8, text, '-');
    const end = std.fmt.parseInt(u64, it.next() orelse return null, 10) catch return null;
    const frame_count = std.fmt.parseInt(u64, it.next() orelse return null, 10) catch return null;
    const last_frame_offset = std.fmt.parseInt(u64, it.next() orelse return null, 10) catch return null;
    const last_header_crc = std.fmt.parseInt(u32, it.next() orelse return null, 10) catch return null;
    if (it.next() != null) return null; // no residue
    return .{
        .end = end,
        .frame_count = frame_count,
        .last_frame_offset = last_frame_offset,
        .last_header_crc = last_header_crc,
    };
}

// --- frames: verifying a batch across workers ------------------------------
//
// Reconstruction stays on ONE thread and keeps the plaintext memo, because the
// memo is what made the sequential stream fast: consecutive artifacts chain
// through the same base, so fanning reconstruction out would either share a
// locked cache or redo base work. Verification has neither property — an
// artifact's hash depends on its own bytes and nothing else — and it is the
// larger half of the remaining cost (profile: 59% verify, 38% reconstruct;
// deleting the verify call took a libfossil stream from 2.25s to 0.88s user).
//
// So the split is: the main thread reconstructs a bounded batch, workers hash
// it, the main thread emits it in order. Workers touch no store, no cache, and
// no allocator — only `verify(name, bytes)` over a slot they alone own. There
// is no queue, no lock, and no atomic: each worker walks a fixed STRIDE of the
// batch, so the writes land in disjoint slots and `join` supplies the ordering.

/// One artifact waiting to be verified and then emitted. `bytes` is owned and
/// freed by the emitter; the name is stored inline because the fill loop keeps
/// no per-slot buffer of its own.
const FrameJob = struct {
    hex_buf: [2 * logstore.max_hash_len]u8 = undefined,
    hex_len: usize = 0,
    bytes: []u8 = &.{},
    ok: bool = false,

    fn hex(self: *const FrameJob) []const u8 {
        return self.hex_buf[0..self.hex_len];
    }
};

/// Batch bounds (TigerStyle: both fixed; the byte budget is the one that binds
/// on a corpus with large artifacts). The count keeps per-batch thread spawns
/// amortised — 17,449 artifacts is ~69 batches, well under a percent of the run.
const frames_batch_max: usize = 256;

const frames_batch_bytes: usize = 16 << 20;

/// Upper bound on verify workers. Past the measured Amdahl ceiling (61% parallel, so
/// 2.6x however many cores exist) more threads buy nothing, and a fixed bound
/// keeps the thread array a comptime-sized stack value.
const frames_max_workers: usize = 8;

/// Verify every `stride`-th job from `start`. Pure and allocation-free: the
/// only writes are to `jobs[i].ok`, and the strides partition the batch, so no
/// two threads ever touch one slot.
fn framesVerifyStride(jobs: []FrameJob, start: usize, stride: usize) void {
    std.debug.assert(stride >= 1);
    std.debug.assert(start < stride);
    var i = start;
    while (i < jobs.len) : (i += stride) {
        jobs[i].ok = zit.artifact.verify(jobs[i].hex(), jobs[i].bytes);
    }
}

/// Hash a whole batch, using `workers` threads when that is worth it. Falls
/// back in-thread for a small batch, a single-core host, or a spawn that
/// fails — a stride whose thread never started is walked by the caller's own
/// thread, so a partial spawn can never leave a slot unverified, which would
/// read as a false corruption report.
fn framesVerifyBatch(jobs: []FrameJob, workers: usize) void {
    std.debug.assert(workers >= 1 and workers <= frames_max_workers);
    if (workers == 1 or jobs.len < 2) {
        framesVerifyStride(jobs, 0, 1);
        return;
    }
    const stride = @min(workers, jobs.len);
    var threads: [frames_max_workers - 1]std.Thread = undefined;
    var spawned: usize = 0;
    while (spawned + 1 < stride) : (spawned += 1) {
        threads[spawned] = std.Thread.spawn(.{}, framesVerifyStride, .{ jobs, spawned + 1, stride }) catch break;
    }
    // Stride 0 is always ours, and so is any stride whose spawn did not happen.
    var s: usize = 0;
    while (s < stride) : (s += 1) {
        if (s == 0 or s > spawned) framesVerifyStride(jobs, s, stride);
    }
    for (threads[0..spawned]) |t| t.join();
}

/// Verify a filled batch, then write it out in index order. Returns false once
/// an artifact fails to hash to its name, having already named it on stderr —
/// the caller frees the batch and exits. Emission order is the batch's own
/// order, which is persisted order, so the worker count never reaches the
/// stream.
fn framesFlushBatch(streams: cli.Streams, jobs: []FrameJob, workers: usize) bool {
    framesVerifyBatch(jobs, workers);
    for (jobs) |*job| {
        if (!job.ok) {
            streams.err.print("zit frames: stored artifact {s} does not hash to its name\n", .{job.hex()}) catch {};
            return false;
        }
        streams.out.print("artifact {s} {d}\n", .{ job.hex(), job.bytes.len }) catch {};
        streams.out.writeAll(job.bytes) catch {};
        streams.out.writeAll("\n") catch {};
    }
    return true;
}

/// How many verify workers this host should use: one per core, bounded, and
/// exactly 1 when the count cannot be determined — an unknown machine takes
/// the sequential path rather than a guess.
fn framesWorkerCount() usize {
    const cpus = std.Thread.getCpuCount() catch return 1;
    return @max(1, @min(cpus, frames_max_workers));
}

pub fn runFrames(
    gpa: std.mem.Allocator,
    io: std.Io,
    arena: std.mem.Allocator,
    verb_args: []const []const u8,
    streams: cli.Streams,
    amb: cli.Ambient,
) cli.Exit {
    const parsed = switch (cli.parseFramesArgs(verb_args)) {
        .ok => |p| p,
        .unknown_option => |tok| return cli.usageError(streams, "frames", .unknown_option, tok),
        .extra_argument => |tok| return cli.usageError(streams, "frames", .extra_argument, tok),
        .empty_value => |tok| return cli.usageError(streams, "frames", .unknown_option, tok),
    };
    if (parsed.help) {
        streams.out.writeAll(frames_help) catch {};
        return .ok;
    }

    var repo: Repository = undefined;
    var root_dir: std.Io.Dir = undefined;
    const rc = openRepo(gpa, io, arena, streams, "frames", amb.repo_override, false, true, &repo, &root_dir);
    if (rc != .ok) return rc;
    defer root_dir.close(io);
    defer repo.deinit(gpa);

    const log = repo.logStore(gpa) catch |e| return repoOpenFail(streams, "frames", e);
    // PERSISTED (frame) order, not dense rid order: `intern` mints a rid for
    // a phantom before the frame that fills it lands, so a rid-ordered cursor
    // would pass a hole and never revisit it. Frame order is append order --
    // the same clock the LogKey prefix token describes.
    const persisted = log.ridsInPersistedOrder(gpa) catch return stateOom(streams, "frames");
    defer gpa.free(persisted);
    const count: u64 = persisted.len;

    // The consumed prefix: 0 (bootstrap) or the previous trailer's cursor.
    var since: u64 = 0;
    if (parsed.since) |text| {
        since = framesParseCursor(text) orelse return framesCursorInvalid(streams, "the cursor is not one this store issued");
        // A cursor past the store's end can only come from a rewritten
        // (shrunk) store or a foreign one -- dead either way.
        if (since > count) return framesCursorInvalid(streams, "the cursor names artifacts this store does not hold");
    }
    // Prefix validation: the token is the LogKey of the consumed prefix. A
    // rewrite (pack / shun reclaim) relocates or re-CRCs frames and fails
    // this check; plain appends never touch it.
    if (parsed.verify) |text| {
        const key = framesParseToken(text) orelse return framesCursorInvalid(streams, "the token is not one this store issued");
        if (!logstore.LogStore.validatePrefix(log.file, key)) {
            return framesCursorInvalid(streams, "the store was rewritten since the cursor was issued");
        }
    }

    // Emit rids since+1..count: whole reconstructed artifacts (the delta
    // chain and container layout stay private), each verified against its
    // name before a byte leaves — byte-identical to `artifact HASH --raw`.
    // Phantoms hold no bytes and shun-masked names read as absent; both are
    // skipped, and the cursor still advances over them (rid order is the
    // cursor's clock, presence is per-artifact).
    // A full-history stream is the read `contentCached` exists for. Nine
    // artifacts in ten are deltas in an imported fossil corpus (measured
    // 89% on libfossil, 91% on sqlite), and consecutive artifacts in persisted
    // order routinely chain through the same base — so the uncached reader
    // reconstructed each base once per referencing delta, which is what made a
    // linear stream cost superlinear work. `memoize_undeltaed` stays OFF: this
    // sweep reads each artifact exactly once, so memoizing top-level raw/zlib
    // plaintext would duplicate bytes nothing asks for again. Bases are
    // memoized regardless of their own frame kind, which is the whole win.
    var plaintext: logstore.PlaintextCache = .{};
    defer plaintext.deinit(gpa);

    // Reconstruct into a bounded batch, hash the batch across workers, then
    // emit it in persisted order. Order is the batch's own index order, so the
    // stream is byte-identical to the single-threaded read whatever the worker
    // count — a property the e2e pins by hashing the whole stream.
    const jobs = gpa.alloc(FrameJob, frames_batch_max) catch return stateOom(streams, "frames");
    defer gpa.free(jobs);
    const workers = framesWorkerCount();

    var emitted: u64 = 0;
    var filled: usize = 0;
    var batch_bytes: usize = 0;
    // Whatever exits this scope — a read fault, a verification failure, or the
    // clean end — the batch still holds owned plaintext that has not been
    // emitted. One place frees it.
    defer for (jobs[0..filled]) |job| gpa.free(job.bytes);

    for (persisted[@intCast(since)..]) |r| {
        const bytes = (log.contentCached(gpa, r, &plaintext) catch |e| return framesReadFail(streams, e)) orelse continue;
        // --structural: emit only what the crosslink itself would link.
        // The gate is the SAME parse (`artifact.parseForImport`), applied to
        // the reconstructed bytes -- never a cache lookup, so the filtered
        // stream cannot disagree with the log. Skipped frames are neither
        // hashed nor emitted; the cursor advances over them regardless, so a
        // later poll -- with or without the flag -- resumes identically.
        if (parsed.structural) {
            // Reject-fast pre-screen. A structural artifact's first bytes are
            // either a card line, `<LETTER><SP>` (artifact-format section
            // 4.2), or a signature wrapper, `-----BEGIN ...` (section 4.1.1)
            // -- the sqlite corpus holds 1,087 clearsigned manifests, which is
            // how the first draft of this screen (card shape only) was caught
            // by the stream-equality check. The screen only ever REJECTS;
            // every accept still takes the full parse below, so nothing the
            // crosslink would refuse can be admitted. What it saves is the
            // whole-bytes Z-checksum a parse attempt pays before rejecting a
            // content blob.
            const card_shaped = bytes.len >= 2 and bytes[0] >= 'A' and bytes[0] <= 'Z' and bytes[1] == ' ';
            const wrapper_shaped = std.mem.startsWith(u8, bytes, "-----BEGIN ");
            if (!card_shaped and !wrapper_shaped) {
                gpa.free(bytes);
                continue;
            }
            if (artifact.parseForImport(gpa, bytes)) |im_const| {
                var im = im_const;
                im.deinit(gpa);
            } else |e| switch (e) {
                error.OutOfMemory => {
                    gpa.free(bytes);
                    return stateOom(streams, "frames");
                },
                else => { // not a structural artifact: a content blob
                    gpa.free(bytes);
                    continue;
                },
            }
        }
        jobs[filled] = .{ .bytes = bytes };
        const hex = std.fmt.bufPrint(&jobs[filled].hex_buf, "{x}", .{log.hashOf(r)}) catch unreachable;
        jobs[filled].hex_len = hex.len;
        filled += 1;
        batch_bytes += bytes.len;

        if (filled == frames_batch_max or batch_bytes >= frames_batch_bytes) {
            if (!framesFlushBatch(streams, jobs[0..filled], workers)) return .failure;
            emitted += filled;
            for (jobs[0..filled]) |job| gpa.free(job.bytes);
            filled = 0;
            batch_bytes = 0;
        }
    }
    if (filled != 0) {
        if (!framesFlushBatch(streams, jobs[0..filled], workers)) return .failure;
        emitted += filled;
        for (jobs[0..filled]) |job| gpa.free(job.bytes);
        filled = 0;
    }

    // The trailer: the new cursor and its token, emitted even when nothing
    // new exists so a bootstrap poll always learns its position.
    const key = if (count == 0)
        (log.logKey() catch |e| return framesKeyFail(streams, e))
    else
        (log.logKeyAt(persisted[persisted.len - 1]) catch |e| return framesKeyFail(streams, e));
    streams.out.print("cursor {d} {d}-{d}-{d}-{d}\n", .{
        count, key.end, key.frame_count, key.last_frame_offset, key.last_header_crc,
    }) catch {};

    if (emitted == 0) return .no_new;
    return .ok;
}

/// The cursor-invalid refusal: a distinct exit code (4) so a consumer
/// distinguishes "re-read from zero" from every operational failure. The
/// message states the mechanism, never "corrupt".
fn framesCursorInvalid(s: cli.Streams, reason: []const u8) cli.Exit {
    s.err.print("zit frames: cursor invalid: {s}; re-read from --since=0\n", .{reason}) catch {};
    return .cursor_invalid;
}

fn framesReadFail(s: cli.Streams, e: logstore.ContentError) cli.Exit {
    switch (e) {
        error.OutOfMemory => s.err.writeAll("zit frames: out of memory\n") catch {},
        error.Storage => s.err.writeAll("zit frames: cannot read the repository\n") catch {},
        error.Corrupt => s.err.writeAll("zit frames: the repository is unreadable\n") catch {},
    }
    return .failure;
}

fn framesKeyFail(s: cli.Streams, e: logstore.LogStore.KeyError) cli.Exit {
    switch (e) {
        error.Storage => s.err.writeAll("zit frames: cannot read the repository\n") catch {},
        error.Corrupt => s.err.writeAll("zit frames: the repository is unreadable\n") catch {},
    }
    return .failure;
}

test "frames: strided verification agrees with the sequential answer at every worker count" {
    // The concurrency's whole safety argument is that the strides PARTITION
    // the batch: each slot is written by exactly one thread, and `join`
    // orders those writes before the emitter reads them. This drives the
    // partition at every legal worker count over a batch carrying both good
    // and corrupt names, and demands the identical verdict vector each time —
    // a stride that skipped a slot, double-covered one, or lost a spawn would
    // show up as a `false` where the sequential run says `true`.
    const gpa = std.testing.allocator;
    const count = 37; // deliberately coprime with every worker count below

    var jobs = try gpa.alloc(FrameJob, count);
    defer gpa.free(jobs);
    var bodies = try gpa.alloc([]u8, count);
    defer {
        for (bodies) |b| gpa.free(b);
        gpa.free(bodies);
    }

    // Every third artifact is given a name it does not hash to, so the
    // expected verdict vector is a non-trivial pattern rather than all-true.
    for (0..count) |i| {
        bodies[i] = try std.fmt.allocPrint(gpa, "artifact body number {d}\n", .{i});
        jobs[i] = .{ .bytes = bodies[i] };
        var name_buf: [64]u8 = undefined;
        const name = zit.artifact.artifactName(.sha3_256, bodies[i], &name_buf);
        @memcpy(jobs[i].hex_buf[0..name.len], name);
        jobs[i].hex_len = name.len;
        if (i % 3 == 0) jobs[i].hex_buf[0] = if (name[0] == 'a') 'b' else 'a'; // corrupt the name
    }

    var expected: [count]bool = undefined;
    framesVerifyBatch(jobs, 1);
    for (jobs, 0..) |job, i| expected[i] = job.ok;
    // The pattern must be mixed, or this test would pass on a no-op.
    var trues: usize = 0;
    for (expected) |e| {
        if (e) trues += 1;
    }
    try std.testing.expect(trues > 0 and trues < count);

    var workers: usize = 1;
    while (workers <= frames_max_workers) : (workers += 1) {
        for (jobs) |*job| job.ok = false;
        framesVerifyBatch(jobs, workers);
        for (jobs, 0..) |job, i| try std.testing.expectEqual(expected[i], job.ok);
    }

    // A batch smaller than the worker count takes the same partition path.
    for (jobs[0..1]) |*job| job.ok = false;
    framesVerifyBatch(jobs[0..1], frames_max_workers);
    try std.testing.expectEqual(expected[0], jobs[0].ok);
}