Artifact 80bb6fef67c88a29a2b6bdc372996c9f2c4ad65db289cddebc7a427b42ee5d39:
- File
src/sim/checkout_sweep.zig
— part of check-in
[0cea021cf9]
at
2026-07-20 04:21:55
on branch h2-checkout-dst
— sim: working-tree crash-recovery DST sweep for update
Add sim/faulty_dir.zig, a decorator std.Io that cuts a run at a seeded mutating-op boundary the way a power loss does: the crashing write persists at most a torn prefix and every later mutation is a frozen no-op, so the checkout layer's own recovery moves no byte. Crash-point enumeration follows TigerBeetle's storage-fault-injection lineage, ported to the directory surface update.zig and checkout.zig write through.
Add sim/checkout_sweep.zig: it materializes a check-in, replays an A-to-B update.applyCheckin under a crash at every reachable cut, reopens, and asserts unmanaged files are preserved, the checkout record names only a complete target, and the tree recovers to the target via the undo journal. Joins the dst gate per seed at bounded cuts; the soak walks every boundary.
Finding: update.writePayload writes working files in place (createFile truncate, write, sync), not through the atomic write-temp+fsync+rename that checkout.write, the managed set, and the undo journal use. A crash mid-write can leave a file matching neither its pre- nor its post-image. The sweep pins this; a working-tree write-journal is the fix. (user: dmestas, size: 23601) [annotate] [blame] [check-ins using] [more...]
//! The working-tree crash-recovery DST sweep (H2, native harness design — no RFC //! clause touches the working tree; contracts/undo.md and update.zig's own //! transactional discipline are the oracle). It drives the real //! `update.applyCheckin` public API over a real directory whose every write goes //! through `sim/faulty_dir.zig`, cuts the run at every reachable mutating-op //! boundary, reopens, and asserts the crash-recovery invariants. //! //! Crash-point enumeration — count the mutating operations one `update` performs, //! then replay it once per cut `k ∈ [1, total]` and assert recovery from each — //! is TigerBeetle's storage-fault-injection lineage (the VOPR walks every //! disk-write boundary); this ports it from block storage to the checkout layer's //! POSIX directory surface. The seed is the whole universe: the same seed picks //! the same content, the same op count, and the same torn-prefix lengths, so any //! failure replays verbatim from `reproduce with seed=N`. //! //! Invariants (the model tracks each managed path's pre-op A-bytes and post-op //! B-bytes, plus the untouched user witness): //! (i) no silent hybrid — a managed file present after a cut is byte-identical //! to its A-image or its B-image, never a splice. **This does not hold //! today** and is checked only by the finding test below, never the gate: //! `update.writePayload` materializes working files in place //! (`createFile(truncate)` + `writePositionalAll` + `sync`), NOT through //! the atomic write-temp+fsync+rename that `checkout.write`/`managed`/the //! undo journal use — so a crash between the truncate and the durable //! write leaves a file matching neither image. See the finding test. //! (ii) user-edit preservation — an unmanaged witness file is byte-identical to //! the user's bytes under every cut (update never touches out-of-set paths). //! (iii) recoverability — after any cut, a healthy `update` to the target either //! completes directly or, once `zit undo` replays the journal, reaches the //! declared target; the two-phase liveness mirrors storage_sweep.zig's //! healed phase. //! (iv) checkout-record consistency — the record names only A, the target B, or //! unborn; and when it already names B, B is fully materialized (the record //! is the atomic commit point, written last). const std = @import("std"); const zit = @import("zit"); const artifact = zit.artifact; const checkout = zit.checkout; const logstore = zit.logstore; const managed = zit.managed; const storage = zit.storage; const update = zit.update; const faulty_dir = @import("faulty_dir.zig"); const Dir = std.Io.Dir; const Io = std.Io; pub const SweepError = error{ OutOfMemory, /// A backend/setup filesystem op failed unexpectedly (never a fault the /// sweep injected — those are handled). Io, /// Invariant (iv): the record named a check-in other than A/B/unborn, or it /// named B while B was not fully on disk. RecordNamesIncompleteTarget, /// Invariant (ii): a crashed update destroyed an unmanaged user file. UnmanagedFileDestroyed, /// Invariant (iii): after a cut, no healthy path (direct or via `zit undo`) /// returns the tree to the declared target. Unrecoverable, /// Invariant (i): a managed file survived a cut matching neither its pre- nor /// its post-image — a torn, spliced write. THE FINDING (checked only by the /// finding test). HybridFile, }; const witness_path = "witness.txt"; const witness_bytes = "the user's own uncommitted scratch\n"; /// One materialized check-in's file set: path -> uncompressed bytes, owned. const Tree = struct { paths: std.ArrayList([]u8) = .empty, blobs: std.ArrayList([]u8) = .empty, fn deinit(self: *Tree, gpa: std.mem.Allocator) void { for (self.paths.items) |p| gpa.free(p); for (self.blobs.items) |b| gpa.free(b); self.paths.deinit(gpa); self.blobs.deinit(gpa); self.* = undefined; } fn add(self: *Tree, gpa: std.mem.Allocator, path: []const u8, blob: []const u8) SweepError!void { const p = gpa.dupe(u8, path) catch return error.OutOfMemory; errdefer gpa.free(p); const b = gpa.dupe(u8, blob) catch return error.OutOfMemory; errdefer gpa.free(b); self.paths.append(gpa, p) catch return error.OutOfMemory; self.blobs.append(gpa, b) catch return error.OutOfMemory; } /// The image bytes for `path`, or null when this tree does not track it. fn get(self: *const Tree, path: []const u8) ?[]const u8 { for (self.paths.items, self.blobs.items) |p, b| { if (std.mem.eql(u8, p, path)) return b; } return null; } }; /// The full managed-path universe across A and B (used by the hybrid and record /// oracles). A is `{f.txt}`, B is `{f.txt, g.txt}`. const managed_paths = [_][]const u8{ "f.txt", "g.txt" }; /// The seeded corpus for one run: the two check-in ids and the A/B expected /// trees. Pure data — the log is (re)built from it per workspace. A's tracked /// file is rewritten and a second file added at B, so an A->B update deletes, /// rewrites, and creates: a spread of mutating ops for the cut enumeration. const Corpus = struct { a_id: [64]u8, a_len: usize, b_id: [64]u8, b_len: usize, a_tree: Tree, b_tree: Tree, fn aId(self: *const Corpus) []const u8 { return self.a_id[0..self.a_len]; } fn bId(self: *const Corpus) []const u8 { return self.b_id[0..self.b_len]; } fn deinit(self: *Corpus, gpa: std.mem.Allocator) void { self.a_tree.deinit(gpa); self.b_tree.deinit(gpa); self.* = undefined; } }; fn completeArtifact(gpa: std.mem.Allocator, body: []const u8) SweepError![]u8 { var checksum_buf: [32]u8 = undefined; const checksum = artifact.selfChecksum(body, &checksum_buf); return std.fmt.allocPrint(gpa, "{s}Z {s}\n", .{ body, checksum }) catch return error.OutOfMemory; } fn putRaw(log: *logstore.LogStore, name: []const u8, bytes: []const u8) SweepError!void { var digest: [logstore.max_hash_len]u8 = undefined; const raw = digest[0 .. name.len / 2]; _ = std.fmt.hexToBytes(raw, name) catch return error.Io; _ = log.put(raw, bytes) catch return error.Io; } fn seedBlob(gpa: std.mem.Allocator, random: std.Random, tag: []const u8) SweepError![]u8 { // A few hundred bytes of tagged, seed-varied content: distinct per blob so // every artifact hashes distinctly, and non-empty so a torn/empty survivor is // unambiguously neither image. const rows = 6 + random.uintLessThan(usize, 10); var buf: std.ArrayList(u8) = .empty; errdefer buf.deinit(gpa); var i: usize = 0; while (i < rows) : (i += 1) { buf.print(gpa, "{s} line {d} salt {x}\n", .{ tag, i, random.int(u32) }) catch return error.OutOfMemory; } return buf.toOwnedSlice(gpa) catch return error.OutOfMemory; } fn manifestA(gpa: std.mem.Allocator, fa: []const u8) SweepError![]u8 { var fname: [64]u8 = undefined; const fa_id = artifact.artifactName(.sha1, fa, &fname); const body = std.fmt.allocPrint(gpa, "D 2020-01-01T00:00:00\nF f.txt {s}\n", .{fa_id}) catch return error.OutOfMemory; defer gpa.free(body); return completeArtifact(gpa, body); } fn manifestB(gpa: std.mem.Allocator, fb: []const u8, gb: []const u8, a_name: []const u8) SweepError![]u8 { var fname: [64]u8 = undefined; var gname: [64]u8 = undefined; const fb_id = artifact.artifactName(.sha1, fb, &fname); const gb_id = artifact.artifactName(.sha1, gb, &gname); // F cards filename-sorted (f before g); card order D, F, F, P is canonical. const body = std.fmt.allocPrint(gpa, "D 2020-01-02T00:00:00\nF f.txt {s}\nF g.txt {s}\nP {s}\n", .{ fb_id, gb_id, a_name }) catch return error.OutOfMemory; defer gpa.free(body); return completeArtifact(gpa, body); } /// Compute the corpus ids and A/B trees from a seeded content stream. Pure: no /// log, no filesystem — the log is seeded from this per workspace. fn buildCorpus(gpa: std.mem.Allocator, random: std.Random) SweepError!Corpus { const fa = try seedBlob(gpa, random, "f-at-a"); defer gpa.free(fa); const fb = try seedBlob(gpa, random, "f-at-b"); defer gpa.free(fb); const gb = try seedBlob(gpa, random, "g-at-b"); defer gpa.free(gb); const a_bytes = try manifestA(gpa, fa); defer gpa.free(a_bytes); var a_id: [64]u8 = undefined; const a_name = artifact.artifactName(.sha1, a_bytes, &a_id); const b_bytes = try manifestB(gpa, fb, gb, a_name); defer gpa.free(b_bytes); var b_id: [64]u8 = undefined; const b_name = artifact.artifactName(.sha1, b_bytes, &b_id); var a_tree = Tree{}; errdefer a_tree.deinit(gpa); try a_tree.add(gpa, "f.txt", fa); var b_tree = Tree{}; errdefer b_tree.deinit(gpa); try b_tree.add(gpa, "f.txt", fb); try b_tree.add(gpa, "g.txt", gb); return .{ .a_id = a_id, .a_len = a_name.len, .b_id = b_id, .b_len = b_name.len, .a_tree = a_tree, .b_tree = b_tree }; } /// Seed `log` with the corpus's blobs and manifests (byte-identical every call, /// since content is a pure function of the corpus). fn seedLog(gpa: std.mem.Allocator, corpus: *const Corpus, log: *logstore.LogStore) SweepError!void { const fa = corpus.a_tree.get("f.txt").?; const fb = corpus.b_tree.get("f.txt").?; const gb = corpus.b_tree.get("g.txt").?; for ([_][]const u8{ fa, fb, gb }) |blob| { var name: [64]u8 = undefined; const id = artifact.artifactName(.sha1, blob, &name); try putRaw(log, id, blob); } const a_bytes = try manifestA(gpa, fa); defer gpa.free(a_bytes); try putRaw(log, corpus.aId(), a_bytes); const b_bytes = try manifestB(gpa, fb, gb, corpus.aId()); defer gpa.free(b_bytes); try putRaw(log, corpus.bId(), b_bytes); log.commit() catch return error.Io; } /// A live workspace: a fresh subdir under `root`, an open repo.zit seeded with /// the corpus, and its LogStore. const Workspace = struct { name: []u8, dir: Dir, repo_file: std.Io.File, /// Heap-allocated so `StorageFile.context = &fs` stays valid after this /// Workspace is returned by value (a moved local would dangle it). fs: *storage.FileStorage, log: logstore.LogStore, root: Dir, io: Io, fn open(gpa: std.mem.Allocator, io: Io, root: Dir, corpus: *const Corpus, nonce: u64) SweepError!Workspace { const name = std.fmt.allocPrint(gpa, "ws-{x}", .{nonce}) catch return error.OutOfMemory; errdefer gpa.free(name); root.deleteTree(io, name) catch {}; // a prior aborted run may have left it root.createDir(io, name, .default_dir) catch return error.Io; var dir = root.openDir(io, name, .{ .access_sub_paths = true, .follow_symlinks = false }) catch return error.Io; errdefer dir.close(io); var repo_file = dir.createFile(io, "repo.zit", .{ .read = true, .truncate = true, .resolve_beneath = true }) catch return error.Io; errdefer repo_file.close(io); const fs = gpa.create(storage.FileStorage) catch return error.OutOfMemory; errdefer gpa.destroy(fs); fs.* = storage.FileStorage.init(io, repo_file, 0); var log = logstore.LogStore.open(gpa, fs.storageFile(), 0) catch return error.Io; errdefer log.deinit(gpa); try seedLog(gpa, corpus, &log); return .{ .name = name, .dir = dir, .repo_file = repo_file, .fs = fs, .log = log, .root = root, .io = io, }; } fn close(self: *Workspace, gpa: std.mem.Allocator) void { self.log.deinit(gpa); gpa.destroy(self.fs); self.repo_file.close(self.io); self.dir.close(self.io); self.root.deleteTree(self.io, self.name) catch {}; gpa.free(self.name); self.* = undefined; } }; /// Seed the working tree to a clean check-out of A, plus the user's witness file. fn seedAtA(gpa: std.mem.Allocator, io: Io, ws: *Workspace, corpus: *const Corpus) SweepError!void { // Unborn record + empty managed set, exactly what `init` leaves. checkout.write(io, ws.dir, .{ .version = "", .branch = "", .merge_parent = "", .special_op = "", .manifest_flags = "" }) catch return error.Io; var empty = managed.ManagedSet.init(gpa); defer empty.deinit(); empty.write(io, ws.dir) catch return error.Io; writeUserFile(io, ws.dir, witness_path, witness_bytes) catch return error.Io; update.applyCheckin(gpa, io, ws.dir, &ws.log, corpus.aId(), .inherit) catch return error.Io; } fn writeUserFile(io: Io, dir: Dir, path: []const u8, bytes: []const u8) !void { var file = try dir.createFile(io, path, .{ .read = false, .truncate = true, .resolve_beneath = true }); defer file.close(io); try file.writePositionalAll(io, bytes, 0); try file.sync(io); } /// Count the mutating ops one healthy A->B update performs on a throwaway /// workspace — the crash-cut range `[1, total]`. fn countOps(gpa: std.mem.Allocator, io: Io, root: Dir, corpus: *const Corpus) SweepError!u64 { var ws = try Workspace.open(gpa, io, root, corpus, 0xC0); defer ws.close(gpa); try seedAtA(gpa, io, &ws, corpus); var fprng = std.Random.DefaultPrng.init(0xC0); var faulty = faulty_dir.FaultyDir.init(io, fprng.random(), .{}); // no crash: count only faulty.install(); defer faulty_dir.FaultyDir.uninstall(); update.applyCheckin(gpa, faulty.io(), ws.dir, &ws.log, corpus.bId(), .inherit) catch return error.Io; return faulty.op_index; } const FileState = union(enum) { missing, bytes: []u8 }; fn readFile(gpa: std.mem.Allocator, io: Io, dir: Dir, path: []const u8) SweepError!FileState { const bytes = dir.readFileAlloc(io, path, gpa, .limited(1 << 20)) catch |e| switch (e) { error.FileNotFound => return .missing, error.OutOfMemory => return error.OutOfMemory, else => return error.Io, }; return .{ .bytes = bytes }; } /// Invariant (ii): the witness is byte-identical to the user's bytes. fn checkWitness(gpa: std.mem.Allocator, io: Io, dir: Dir) SweepError!void { var st = try readFile(gpa, io, dir, witness_path); switch (st) { .missing => return error.UnmanagedFileDestroyed, .bytes => |*b| { defer gpa.free(b.*); if (!std.mem.eql(u8, b.*, witness_bytes)) return error.UnmanagedFileDestroyed; }, } } /// Invariant (i): every managed path present on disk matches its A-image or its /// B-image. Returns error.HybridFile on the first splice. Only the finding test /// calls this — the property does not hold today. fn checkNoHybrid(gpa: std.mem.Allocator, io: Io, dir: Dir, corpus: *const Corpus) SweepError!void { for (managed_paths) |path| { var st = try readFile(gpa, io, dir, path); switch (st) { .missing => {}, // absence is an (iii) concern, not a splice .bytes => |*b| { defer gpa.free(b.*); const a_img = corpus.a_tree.get(path); const b_img = corpus.b_tree.get(path); const matches_a = a_img != null and std.mem.eql(u8, b.*, a_img.?); const matches_b = b_img != null and std.mem.eql(u8, b.*, b_img.?); if (!matches_a and !matches_b) return error.HybridFile; }, } } } /// Invariant (iv): the record names only A/B/unborn, and if it names B then B is /// fully materialized on disk. fn checkRecord(gpa: std.mem.Allocator, io: Io, dir: Dir, corpus: *const Corpus) SweepError!void { var buf: [checkout.max_ck_payload + 1]u8 = undefined; const state = checkout.read(io, dir, &buf) catch return error.Io; const ver = if (state) |s| s.version else ""; if (ver.len == 0) return; // unborn/mid — permitted if (std.mem.eql(u8, ver, corpus.aId())) return; // still A — permitted if (!std.mem.eql(u8, ver, corpus.bId())) return error.RecordNamesIncompleteTarget; // Record already names B: B must be fully on disk (the record is written last). try expectTree(gpa, io, dir, &corpus.b_tree); } /// Assert every path in `tree` is present with its bytes. fn expectTree(gpa: std.mem.Allocator, io: Io, dir: Dir, tree: *const Tree) SweepError!void { for (tree.paths.items, tree.blobs.items) |path, want| { var st = try readFile(gpa, io, dir, path); switch (st) { .missing => return error.RecordNamesIncompleteTarget, .bytes => |*b| { defer gpa.free(b.*); if (!std.mem.eql(u8, b.*, want)) return error.RecordNamesIncompleteTarget; }, } } } /// Invariant (iii): a healthy `update` to B either completes directly, or — once /// `zit undo` replays the journal — reaches B. The final tree must equal B. fn checkRecoverable(gpa: std.mem.Allocator, io: Io, ws: *Workspace, corpus: *const Corpus) SweepError!void { if (update.applyCheckin(gpa, io, ws.dir, &ws.log, corpus.bId(), .inherit)) |_| { // Direct completion. } else |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, // Any clean refusal (dirty tree, collision, invalid current state) is the // documented interrupted-state report. Recovery is the undo journal. else => { update.journal.undo(gpa, io, ws.dir) catch return error.Unrecoverable; update.applyCheckin(gpa, io, ws.dir, &ws.log, corpus.bId(), .inherit) catch return error.Unrecoverable; }, } try expectTree(gpa, io, ws.dir, &corpus.b_tree); } /// Options controlling one enumeration pass. const CutOpts = struct { torn_write: bool = false, corrupt_torn: bool = false, check_hybrid: bool = false, /// Cap on cuts actually replayed. 0 = every cut. When `total` exceeds it, the /// cuts are sampled evenly across `[1, total]` (endpoints always included), so /// the gate stays small while the soak (larger cap) walks every boundary — the /// ci.yml gate-vs-sweep division, applied here (TEST-HARDENING §H2/§6). max_cuts: usize = 0, }; /// Result of an enumeration: whether any cut tripped the hybrid detector (the /// finding), reported so the finding test can assert on it without treating it as /// a run failure. const CutOutcome = struct { hybrid_seen: bool = false }; /// Build the corpus once, then for every cut `k ∈ [1, total]` replay A->B under a /// crash at op k and check the invariants. Deterministic: `seed` fixes content, /// op count, and every torn length. fn sweepSeed(gpa: std.mem.Allocator, io: Io, root: Dir, seed: u64, opts: CutOpts) SweepError!CutOutcome { var prng = std.Random.DefaultPrng.init(seed); const random = prng.random(); var corpus = try buildCorpus(gpa, random); defer corpus.deinit(gpa); const total = try countOps(gpa, io, root, &corpus); if (total == 0) return .{}; var outcome = CutOutcome{}; const budget = if (opts.max_cuts == 0) total else @min(opts.max_cuts, total); var j: u64 = 0; while (j < budget) : (j += 1) { // Evenly spaced across [1, total], endpoints included: cut = 1 + round(j * // (total-1) / (budget-1)); with budget == total this is every k. const k: u64 = if (budget == 1) 1 else 1 + (j * (total - 1)) / (budget - 1); if (try sweepCut(gpa, io, root, &corpus, seed, k, opts)) outcome.hybrid_seen = true; } return outcome; } /// One cut: fresh workspace at A, faulted A->B at op `k`, then the oracle. /// Returns whether the hybrid detector tripped (only meaningful when /// `opts.check_hybrid`). fn sweepCut(gpa: std.mem.Allocator, io: Io, root: Dir, corpus: *const Corpus, seed: u64, k: u64, opts: CutOpts) SweepError!bool { const nonce = std.hash.Wyhash.hash(seed, std.mem.asBytes(&k)); var ws = try Workspace.open(gpa, io, root, corpus, nonce); defer ws.close(gpa); try seedAtA(gpa, io, &ws, corpus); var fprng = std.Random.DefaultPrng.init(seed *% 0x9E37_79B9 +% k); var faulty = faulty_dir.FaultyDir.init(io, fprng.random(), .{ .crash_at_op = k, .torn_write = opts.torn_write, .corrupt_torn = opts.corrupt_torn, }); faulty.install(); // The faulted update is EXPECTED to fail (that is the crash); ignore its // return and inspect the disk with the healthy io. update.applyCheckin(gpa, faulty.io(), ws.dir, &ws.log, corpus.bId(), .inherit) catch {}; faulty_dir.FaultyDir.uninstall(); // (ii) and (iv) hold at every cut and are always checked. try checkWitness(gpa, io, ws.dir); try checkRecord(gpa, io, ws.dir, corpus); var hybrid = false; if (opts.check_hybrid) { checkNoHybrid(gpa, io, ws.dir, corpus) catch |e| switch (e) { error.HybridFile => hybrid = true, // the finding; recoverability still proven below else => return e, }; } // (iii) recoverability — proven even when a hybrid is present: the tree is // torn but never lost. try checkRecoverable(gpa, io, &ws, corpus); return hybrid; } /// The gate entry: the bounded crash-recovery sweep. Checks invariants (ii), /// (iii), (iv) at every reachable cut of an A->B update. Invariant (i) is the /// documented open finding and is NOT gated here (see the module header and the /// finding test). `root` is a caller-owned directory the sweep makes throwaway /// workspaces under. pub fn run(gpa: std.mem.Allocator, io: Io, root: Dir, seed: u64) SweepError!void { // 16 evenly-spaced cuts keep the gate to seconds; H1's soak runs `sweepSeed` // with `max_cuts = 0` (every boundary) across many seeds for the depth. _ = try sweepSeed(gpa, io, root, seed, .{ .torn_write = false, .check_hybrid = false, .max_cuts = 16 }); } // --------------------------------------------------------------------------- // Inline tests (join `zig build test` via dst.zig's aggregation). They use // std.testing.io + a tmpDir; the gate `run` is driven from dst.zig's main over a // process-created workspace. // --------------------------------------------------------------------------- test "checkout_sweep: A->B recovers at every crash cut (invariants ii/iii/iv)" { const t = std.testing; var tmp = t.tmpDir(.{}); defer tmp.cleanup(); // Two seeds so content and op counts vary; both must stay green. try run(t.allocator, t.io, tmp.dir, 1); try run(t.allocator, t.io, tmp.dir, 2); } test "checkout_sweep FINDING (H2): a torn in-place payload write leaves a hybrid file" { const t = std.testing; var tmp = t.tmpDir(.{}); defer tmp.cleanup(); // Enumerate every cut with torn writes and the (i) detector armed. Because // update.writePayload is a non-atomic createFile(truncate)+write+sync, at // least one cut tears a managed file into a splice matching neither image — // WHILE recoverability (iii) and witness preservation (ii) still hold (proven // inside sweepCut). This PINS the current gap: when a write-journal / // staged-materialization fix lands, no cut will produce a hybrid and this // assertion flips — convert it then to `try t.expect(!outcome.hybrid_seen)`. const outcome = try sweepSeed(t.allocator, t.io, tmp.dir, 1, .{ .torn_write = true, .corrupt_torn = true, .check_hybrid = true }); try t.expect(outcome.hybrid_seen); }