Artifact be81f86dc637b6a4bcfd15f8d9cdac32ef0f1259b9b7397a930b9600888d7219:
- File
src/git/git_import_benchmark.zig
— part of check-in
[5c445bb3f3]
at
2026-09-28 02:39:03
on branch trunk
— Take the writer lock inside LogStore.open and test the lock class
LogStore.open now takes the exclusive lock before it reads the file's length and scans for the end, and a read-only handle refuses to append. purge undo opens the store through the shared writer path.
A new DST sweep runs two to four writers interleaved against one log through a file that models the lock. It flags unlocked or misplaced appends as they happen, checks each writer sees everything committed before it locked and reads back its own writes, including deltas. A source check fails on any write-mode open of the store outside openStoreAppend. An e2e test races commits, tags and user-table writes on one store and counts what landed. (user: dmestas, size: 63123) [annotate] [blame] [check-ins using]
const std = @import("std"); const builtin = @import("builtin"); const zit = @import("zit"); const artifact = zit.artifact; const editor = zit.submanifest_editor; const fast_export = zit.git_fast_export; const git_import = zit.git_import; const logstore = zit.logstore; const storage = zit.storage; const import_support = zit.git_import_benchmark_support; const max_f_cards: u64 = 10_000_000; const max_new_store_bytes: u64 = 2 * 1024 * 1024 * 1024; const max_wall_ns: u64 = 15 * 60 * std.time.ns_per_s; const max_width: u64 = 10_000_000; const max_commits: u64 = 190_000; const default_cache_bytes: usize = 1 << 20; const default_max_rss_bytes: u64 = 2 * 1024 * 1024 * 1024; // A corpus is retained as one contiguous stream; cap its preallocation below // the store ceiling so parameter products cannot turn validation into an OOM. const max_stream_bytes: u64 = 64 * 1024 * 1024; const max_blob_bytes: u64 = 80; const max_commit_bytes: u64 = 256; const max_command_bytes: u64 = 64; const stream_fixed_bytes: u64 = "feature done\n".len + "done\n".len; const Error = error{ BadArgs, BoundExceeded, SemanticMismatch, GateFailed, ProvenanceUnavailable, Io, OutOfMemory }; const Config = struct { seed: u64 = 1, width: u64 = 20_000, commits: u64 = 1_000, changed: u64 = 1, branch_every: u64 = 97, merge_every: u64 = 389, revision: []const u8 = "", k: u4 = 5, reps: usize = 3, cache_bytes: usize = default_cache_bytes, full: bool = false, max_rss_bytes: u64 = default_max_rss_bytes, }; const Arm = enum { flat_reference, incremental_tree }; const Bound = enum { none, f_cards, store_bytes, wall_time }; const CorpusBounds = struct { records: u64, bytes: u64, bound: Bound, }; const CommonPrefix = struct { commits: u64, expected_control_bound: ?Bound, }; const PhaseTimes = struct { corpus_ns: u64, import_ns: u64, finalize_ns: u64, semantic_ns: u64, finalize_cpu_ns: u64, wall_ns: u64, cpu_ns: u64, }; const RunRecord = struct { arm: Arm, effective_commits: u64, semantic_prefix_commits: u64 = 0, expected_control_bound: ?Bound = null, phase: PhaseTimes, counters: git_import.WorkCounters, store_bytes: u64, f_cards: u64, bound: Bound, semantic: [32]u8, sampled: [32]u8, equal_sampled_trees: ?bool = null, process_peak_rss_bytes: u64, retained_state_entries: usize, wall_scale_ratio: f64 = 0, cpu_scale_ratio: f64 = 0, }; const RssAccumulator = struct { peak_bytes: u64 = 0, fn observe(self: *RssAccumulator, bytes: u64) void { self.peak_bytes = @max(self.peak_bytes, bytes); } }; const CapturedRun = struct { record: RunRecord, store: Store, root_checkin: []u8, mid_checkin: []u8, side_checkin: ?[]u8, merge_checkin: ?[]u8, sampled_checkin: []u8, final_checkin: []u8, fn deinit(self: *CapturedRun, gpa: std.mem.Allocator) void { gpa.free(self.sampled_checkin); gpa.free(self.final_checkin); gpa.free(self.root_checkin); gpa.free(self.mid_checkin); if (self.side_checkin) |checkin| gpa.free(checkin); if (self.merge_checkin) |checkin| gpa.free(checkin); self.store.deinit(gpa); self.* = undefined; } }; const SampleComparison = struct { flat_digest: [32]u8, tree_digest: [32]u8, equal: bool, }; const MemoryFile = struct { gpa: std.mem.Allocator, bytes: std.ArrayList(u8) = .empty, max_bytes: u64 = max_new_store_bytes, limit_reached: bool = false, fn init(gpa: std.mem.Allocator) MemoryFile { return .{ .gpa = gpa }; } fn deinit(self: *MemoryFile) void { self.bytes.deinit(self.gpa); self.* = undefined; } fn storageFile(self: *MemoryFile) storage.StorageFile { return .{ .context = self, .vtable = &vtable }; } const vtable: storage.StorageFile.VTable = .{ .append = append, .pread = pread, .sync = sync, .size = size, .truncate = truncate, .lock = lock, }; /// One writer by construction, so there is no other writer to exclude and /// no other writer's appends to re-read the length for. fn lock(_: *anyopaque) storage.StorageError!void {} fn append(context: *anyopaque, data: []const u8) storage.StorageError!void { const self: *MemoryFile = @ptrCast(@alignCast(context)); const data_len: u64 = @intCast(data.len); const current_len: u64 = @intCast(self.bytes.items.len); if (data_len > self.max_bytes -| current_len) { self.limit_reached = true; return error.Io; } self.bytes.appendSlice(self.gpa, data) catch return error.Io; } fn pread(context: *anyopaque, offset: u64, out: []u8) storage.StorageError!usize { const self: *MemoryFile = @ptrCast(@alignCast(context)); if (offset >= self.bytes.items.len) return 0; const begin: usize = @intCast(offset); const len = @min(out.len, self.bytes.items.len - begin); @memcpy(out[0..len], self.bytes.items[begin..][0..len]); return len; } fn sync(_: *anyopaque) storage.StorageError!void {} fn size(context: *anyopaque) storage.StorageError!u64 { const self: *MemoryFile = @ptrCast(@alignCast(context)); return self.bytes.items.len; } fn truncate(context: *anyopaque, length: u64) storage.StorageError!void { const self: *MemoryFile = @ptrCast(@alignCast(context)); const end: usize = @intCast(length); if (end > self.bytes.items.len) return error.Io; self.bytes.shrinkRetainingCapacity(end); } }; const Store = struct { gpa: std.mem.Allocator, log: logstore.LogStore, file: *MemoryFile, fn init(gpa: std.mem.Allocator) !Store { const file = try gpa.create(MemoryFile); errdefer gpa.destroy(file); file.* = MemoryFile.init(gpa); errdefer file.deinit(); return .{ .gpa = gpa, .file = file, .log = try logstore.LogStore.open(gpa, file.storageFile(), @intFromEnum(artifact.defaultPolicy(true, false))) }; } fn deinit(self: *Store, gpa: std.mem.Allocator) void { self.log.deinit(gpa); self.file.deinit(); gpa.destroy(self.file); self.* = undefined; } fn treeStore(self: *Store) git_import.TreeStore { return .{ .ctx = self, .load_fn = load, .put_fn = put, .put_batch_fn = putBatch }; } fn load(context: *anyopaque, allocator: std.mem.Allocator, name: []const u8) git_import.TreeStoreError!git_import.LoadedBytes { const self: *Store = @ptrCast(@alignCast(context)); var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.MissingNode; const rid = self.log.lookup(digest) orelse return error.MissingNode; const bytes = self.log.content(allocator, rid) catch return error.StorageFailure; return .{ .bytes = bytes orelse return error.MissingNode, .allocator = allocator }; } fn put(context: *anyopaque, name: []const u8, bytes: []const u8) git_import.TreeStoreError!void { const self: *Store = @ptrCast(@alignCast(context)); // Algorithm-agnostic: `verify` picks the digest from the name width. if (!artifact.verify(name, bytes)) return error.StorageFailure; var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.StorageFailure; _ = self.log.putArtifact(digest, bytes, null) catch return error.StorageFailure; } fn putBatch(context: *anyopaque, nodes: []const editor.StoreBatchNode) git_import.TreeStoreError!void { const self: *Store = @ptrCast(@alignCast(context)); var digests: std.ArrayList([32]u8) = .empty; defer digests.deinit(self.gpa); var items: std.ArrayList(logstore.LogStore.ArtifactBatchItem) = .empty; defer items.deinit(self.gpa); digests.ensureTotalCapacity(self.gpa, nodes.len) catch return error.OutOfMemory; items.ensureTotalCapacity(self.gpa, nodes.len) catch return error.OutOfMemory; for (nodes) |node| { var expected: [64]u8 = undefined; if (!std.mem.eql(u8, node.name, artifact.artifactName(git_import.import_hash_algo, node.bytes, &expected))) { return error.StorageFailure; } var digest: [32]u8 = undefined; const raw = rawHashName(node.name, &digest) orelse return error.StorageFailure; digests.appendAssumeCapacity(digest); items.appendAssumeCapacity(.{ .hash = digests.items[digests.items.len - 1][0..raw.len], .bytes = node.bytes, }); } self.log.putArtifactBatch(items.items) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => return error.StorageFailure, }; } }; /// The benchmark's test-only baseline. It deliberately flattens an inherited /// S-tree before applying each change; production never instantiates it. const FlatReferencePolicy = struct { pub fn apply( _: *editor.TreeEditor, gpa: std.mem.Allocator, tree_store: git_import.TreeStore, parent: git_import.RootView, commands: []const git_import.TreeCommand, result: *git_import.BuildResult, cache_high_water: *usize, ) git_import.TreeError!void { var arena_state = std.heap.ArenaAllocator.init(gpa); errdefer arena_state.deinit(); const arena = arena_state.allocator(); var cards = std.ArrayList(artifact.FCard).empty; const root: SemanticRoot = switch (parent) { .flat => |flat| .{ .flat = flat }, .tree => |tree| .{ .tree = tree }, }; try flattenRoot(&cards, arena, tree_store, root); for (commands) |command| try applyFlatCommand(&cards, arena, command); std.mem.sort(artifact.FCard, cards.items, {}, lessCard); result.* = .{ .root = .{ .flat = try cards.toOwnedSlice(arena) }, .tree_height = 0, .changed_paths = commands.len, .reused_nodes = 0, .emitted_nodes = cards.items.len, .arena_state = arena_state, }; cache_high_water.* = 0; } pub fn inheritedFullTreeMaterialization(parent: git_import.RootView) bool { return switch (parent) { .flat => |cards| cards.len != 0, .tree => |cards| cards.len != 0, }; } }; /// Compile-time production policy used only by the private benchmark seam. const IncrementalTreePolicy = import_support.IncrementalTreePolicy; const BoundsContext = struct { io: std.Io, store: *Store, start_ns: u64, f_cards: u64 = 0, total_commits: u64, replay_start_ns: ?u64 = null, replay_start_cpu_ns: ?u64 = null, replay_ns: u64 = 0, replay_cpu_ns: u64 = 0, fired: ?Bound = null, fn fail(self: *BoundsContext, bound: Bound) error{BoundExceeded} { self.fired = bound; return error.BoundExceeded; } fn beforeCommit(self: *BoundsContext) !void { if (self.store.file.bytes.items.len >= max_new_store_bytes) return self.fail(.store_bytes); if (nowNs(self.io) - self.start_ns >= max_wall_ns) return self.fail(.wall_time); } fn beforeCommitFlush(self: *BoundsContext, observation: anytype) !void { if (observation.serialized_f_cards >= max_f_cards - self.f_cards) return self.fail(.f_cards); if (self.store.file.bytes.items.len >= max_new_store_bytes or observation.staged_artifact_bytes > max_new_store_bytes - self.store.file.bytes.items.len) return self.fail(.store_bytes); if (nowNs(self.io) - self.start_ns >= max_wall_ns) return self.fail(.wall_time); } fn afterCommitFlush(self: *BoundsContext, observation: anytype) void { self.f_cards += observation.serialized_f_cards; } fn finish(self: *BoundsContext) void { if (self.fired == null) return; if (self.replay_start_ns) |replay_start_ns| { self.replay_ns = nowNs(self.io) - replay_start_ns; self.replay_cpu_ns = selfCpuNs() - self.replay_start_cpu_ns.?; } } fn afterCommit(self: *BoundsContext, counters: *const git_import.WorkCounters) void { if (counters.commits == 1) { self.replay_start_ns = nowNs(self.io); self.replay_start_cpu_ns = selfCpuNs(); } else if (counters.commits == self.total_commits) { self.replay_ns = nowNs(self.io) - self.replay_start_ns.?; self.replay_cpu_ns = selfCpuNs() - self.replay_start_cpu_ns.?; } } }; const BoundsObserver = struct { bounds: *BoundsContext, pub fn beforeEvent(self: *BoundsObserver, _: *const git_import.WorkCounters, event: zit.git_fast_export.Event) !void { switch (event) { .blob, .commit => try self.bounds.beforeCommit(), else => {}, } } pub fn beforeCommitFlush(self: *BoundsObserver, _: *const git_import.WorkCounters, observation: anytype) !void { try self.bounds.beforeCommitFlush(observation); } pub fn afterCommitFlush(self: *BoundsObserver, _: *const git_import.WorkCounters, observation: anytype) void { self.bounds.afterCommitFlush(observation); } pub fn stopOnError(self: *BoundsObserver, err: anyerror) bool { if (self.bounds.store.file.limit_reached) { self.bounds.fired = .store_bytes; return true; } return err == error.BoundExceeded and self.bounds.fired != null; } pub fn afterEvent(self: *BoundsObserver, counters: *const git_import.WorkCounters, event: zit.git_fast_export.Event) !void { switch (event) { .commit => self.bounds.afterCommit(counters), else => {}, } } }; const FlatImporter = import_support.Importer(FlatReferencePolicy, BoundsObserver); const IncrementalImporter = import_support.Importer(IncrementalTreePolicy, BoundsObserver); fn lessCard(_: void, a: artifact.FCard, b: artifact.FCard) bool { return std.mem.order(u8, a.filename, b.filename) == .lt; } fn flattenRoot(cards: *std.ArrayList(artifact.FCard), arena: std.mem.Allocator, tree_store: git_import.TreeStore, root: SemanticRoot) !void { switch (root) { .flat => |flat| for (flat) |card| try cards.append(arena, try cloneCard(arena, card)), .tree => |tree| for (tree) |sub| { var loaded = try tree_store.load_fn(tree_store.ctx, arena, sub.hash); defer loaded.deinit(); var manifest = artifact.parse(arena, loaded.bytes) catch |err| { std.debug.print("flat node parse name={s} error={s}\n", .{ sub.hash, @errorName(err) }); return error.MalformedNode; }; defer manifest.deinit(); const child: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try flattenRoot(cards, arena, tree_store, child); }, } } fn cloneCard(allocator: std.mem.Allocator, card: artifact.FCard) !artifact.FCard { return .{ .filename = try allocator.dupe(u8, card.filename), .hash = if (card.hash) |hash| try allocator.dupe(u8, hash) else null, .perm = if (card.perm) |perm| try allocator.dupe(u8, perm) else null, .old_name = if (card.old_name) |name| try allocator.dupe(u8, name) else null, .mode = card.mode, }; } fn applyFlatCommand(cards: *std.ArrayList(artifact.FCard), arena: std.mem.Allocator, command: anytype) !void { switch (command) { .upsert => |card| { const owned = try cloneCard(arena, card); if (findCard(cards.items, card.filename)) |index| cards.items[index] = owned else try cards.append(arena, owned); }, .delete => |path| { const index = findCard(cards.items, path) orelse return error.MissingPath; _ = cards.orderedRemove(index); }, .rename => |rename| { const index = findCard(cards.items, rename.old) orelse return error.MissingPath; var card = cards.orderedRemove(index); card.filename = try arena.dupe(u8, rename.new); if (findCard(cards.items, rename.new)) |existing| cards.items[existing] = card else try cards.append(arena, card); }, .copy => |copy| { const index = findCard(cards.items, copy.old) orelse return error.MissingPath; var card = try cloneCard(arena, cards.items[index]); card.filename = try arena.dupe(u8, copy.new); if (findCard(cards.items, copy.new)) |existing| cards.items[existing] = card else try cards.append(arena, card); }, .delete_all => cards.clearRetainingCapacity(), } } fn findCard(cards: []const artifact.FCard, path: []const u8) ?usize { for (cards, 0..) |card, index| if (std.mem.eql(u8, card.filename, path)) return index; return null; } pub fn main(init: std.process.Init) !void { const args = try init.minimal.args.toSlice(init.arena.allocator()); var output_buffer: [64 * 1024]u8 = undefined; var output = std.Io.File.Writer.init(.stdout(), init.io, &output_buffer); run(init.gpa, init.io, args, &output.interface) catch |err| { std.debug.print("import-git-bench: {s}\n", .{@errorName(err)}); return err; }; try output.interface.flush(); } fn run(gpa: std.mem.Allocator, io: std.Io, args: []const []const u8, out: *std.Io.Writer) !void { var cfg = try parseArgs(args); const revision = try checkoutRevision(gpa, io); cfg.revision = &revision; if (corpusBounds(cfg, cfg.commits).bound != .none) return error.BoundExceeded; const prefix = commonPrefix(cfg); const fingerprint_stream = try buildStream(gpa, cfg, cfg.commits); defer gpa.free(fingerprint_stream); const fingerprint = corpusFingerprint(fingerprint_stream); const executable_hash = try executableHash(io, gpa, args[0]); if (cfg.full) return runProductionCorpus(gpa, io, cfg, out, fingerprint, executable_hash); const small = @max(@as(u64, 1), prefix.commits / 2); // Paired, untimed qualification establishes the intermediate sampled and // final output oracles before the fixed-corpus timing matrix. var rss = RssAccumulator{}; const warm_small = try runPaired(gpa, io, cfg, small, &rss); var warm_big = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&warm_big, prefix); if (!warm_small.equal or !warm_big.equal) return error.GateFailed; const width_ratio = try widthDoublingRatio(gpa, io, cfg, &rss); var flat_records: [7]RunRecord = undefined; var tree_records: [7]RunRecord = undefined; if (cfg.reps > flat_records.len) return error.BadArgs; var equal_sampled_trees = true; var bounds_clear = pairedBoundsAccepted(warm_small.flat.bound, warm_small.tree.bound, null) and pairedBoundsAccepted(warm_big.flat.bound, warm_big.tree.bound, prefix.expected_control_bound); var retained_state_clear = retainedStateConstant(cfg, warm_small.flat) and retainedStateConstant(cfg, warm_small.tree) and retainedStateConstant(cfg, warm_big.flat) and retainedStateConstant(cfg, warm_big.tree); for (0..cfg.reps) |rep| { const small_pair = try runPaired(gpa, io, cfg, small, &rss); var big_pair = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&big_pair, prefix); try expectSameSemantics(small_pair.flat, small_pair.tree); try expectSameSemantics(big_pair.flat, big_pair.tree); equal_sampled_trees = equal_sampled_trees and small_pair.equal and big_pair.equal; bounds_clear = bounds_clear and pairedBoundsAccepted(small_pair.flat.bound, small_pair.tree.bound, null) and pairedBoundsAccepted(big_pair.flat.bound, big_pair.tree.bound, prefix.expected_control_bound); retained_state_clear = retained_state_clear and retainedStateConstant(cfg, small_pair.flat) and retainedStateConstant(cfg, small_pair.tree) and retainedStateConstant(cfg, big_pair.flat) and retainedStateConstant(cfg, big_pair.tree); flat_records[rep] = big_pair.flat; tree_records[rep] = big_pair.tree; flat_records[rep].wall_scale_ratio = ratio(big_pair.flat.phase.wall_ns, small_pair.flat.phase.wall_ns); flat_records[rep].cpu_scale_ratio = ratio(big_pair.flat.phase.cpu_ns, small_pair.flat.phase.cpu_ns); tree_records[rep].wall_scale_ratio = ratio(big_pair.tree.phase.wall_ns, small_pair.tree.phase.wall_ns); tree_records[rep].cpu_scale_ratio = ratio(big_pair.tree.phase.cpu_ns, small_pair.tree.phase.cpu_ns); } const flat_wall = medianRatio(flat_records[0..cfg.reps], true); const tree_wall = medianRatio(tree_records[0..cfg.reps], true); const flat_cpu = medianRatio(flat_records[0..cfg.reps], false); const tree_cpu = medianRatio(tree_records[0..cfg.reps], false); const rss_clear = rss.peak_bytes <= cfg.max_rss_bytes; const failed_gate = gateFailure(flat_wall, tree_wall, flat_cpu, tree_cpu, width_ratio, equal_sampled_trees, bounds_clear, retained_state_clear, rss_clear); for (flat_records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, flat_wall, flat_cpu, width_ratio, rss.peak_bytes, true, failed_gate); for (tree_records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, tree_wall, tree_cpu, width_ratio, rss.peak_bytes, true, failed_gate); try out.flush(); if (!std.mem.eql(u8, failed_gate, "none")) return error.GateFailed; } fn runProductionCorpus(gpa: std.mem.Allocator, io: std.Io, cfg: Config, out: *std.Io.Writer, fingerprint: [32]u8, executable_hash: [32]u8) !void { const prefix = commonPrefix(cfg); const small = cfg.commits / 2; var rss = RssAccumulator{}; // This untimed pair is the independent flat/tree oracle over the explicit // safe prefix; all warm and timed qualification remains at full input size. var semantic_pair = try runPaired(gpa, io, cfg, prefix.commits, &rss); annotateCommonPrefix(&semantic_pair, prefix); const full_semantic_clear = semantic_pair.equal; const warm = try runOne(IncrementalTreePolicy, gpa, io, cfg, cfg.commits, .incremental_tree, &rss); const width_ratio = try widthDoublingRatio(gpa, io, cfg, &rss); var records: [7]RunRecord = undefined; var bounds_clear = pairedBoundsAccepted(semantic_pair.flat.bound, semantic_pair.tree.bound, prefix.expected_control_bound) and warm.bound == .none; var retained_state_clear = retainedStateConstant(cfg, semantic_pair.flat) and retainedStateConstant(cfg, semantic_pair.tree) and retainedStateConstant(cfg, warm); for (0..cfg.reps) |rep| { const before = try runOne(IncrementalTreePolicy, gpa, io, cfg, small, .incremental_tree, &rss); var after = try runOne(IncrementalTreePolicy, gpa, io, cfg, cfg.commits, .incremental_tree, &rss); after.semantic_prefix_commits = prefix.commits; after.expected_control_bound = prefix.expected_control_bound; after.wall_scale_ratio = ratio(after.phase.wall_ns, before.phase.wall_ns); after.cpu_scale_ratio = ratio(after.phase.cpu_ns, before.phase.cpu_ns); records[rep] = after; bounds_clear = bounds_clear and before.bound == .none and after.bound == .none; retained_state_clear = retained_state_clear and retainedStateConstant(cfg, before) and retainedStateConstant(cfg, after); } const wall = medianRatio(records[0..cfg.reps], true); const cpu = medianRatio(records[0..cfg.reps], false); const rss_clear = rss.peak_bytes <= cfg.max_rss_bytes; const failed_gate = productionGateFailure(bounds_clear, full_semantic_clear, retained_state_clear, rss_clear, wall, cpu, width_ratio); for (records[0..cfg.reps]) |record| try writeJsonl(out, cfg, executable_hash, fingerprint, record, wall, cpu, width_ratio, rss.peak_bytes, full_semantic_clear, failed_gate); try out.flush(); if (!std.mem.eql(u8, failed_gate, "none")) return error.GateFailed; } fn parseArgs(args: []const []const u8) !Config { var cfg = Config{}; var index: usize = 1; while (index < args.len) { const flag = args[index]; if (std.mem.eql(u8, flag, "--full")) { cfg.full = true; index += 1; continue; } if (index + 1 >= args.len) return error.BadArgs; const value = args[index + 1]; if (std.mem.eql(u8, flag, "--width")) cfg.width = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--commits")) cfg.commits = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--changed")) cfg.changed = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--seed")) cfg.seed = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--reps")) cfg.reps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, flag, "--branch-every")) cfg.branch_every = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--merge-every")) cfg.merge_every = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, flag, "--k")) cfg.k = try std.fmt.parseInt(u4, value, 10) else if (std.mem.eql(u8, flag, "--cache-bytes")) cfg.cache_bytes = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, flag, "--max-rss-bytes")) cfg.max_rss_bytes = try std.fmt.parseInt(u64, value, 10) else return error.BadArgs; index += 2; } if (cfg.width == 0 or cfg.width > max_width / 2 or cfg.commits == 0 or cfg.commits > max_commits or cfg.changed == 0 or cfg.changed > cfg.width or cfg.reps == 0 or cfg.reps > 7 or cfg.reps % 2 == 0 or cfg.cache_bytes == 0 or cfg.max_rss_bytes == 0) return error.BadArgs; if (cfg.seed > std.math.maxInt(u64) - (cfg.changed - 1)) return error.BadArgs; if (cfg.k < artifact.min_k or cfg.k > artifact.max_k) return error.BadArgs; if (cfg.full and (cfg.width < 100_000 or cfg.commits < 100_000)) return error.BadArgs; return cfg; } fn commonPrefix(cfg: Config) CommonPrefix { const commits = @max(@as(u64, 1), @min(cfg.commits, (max_f_cards - 1) / cfg.width)); return .{ .commits = commits, .expected_control_bound = if (commits < cfg.commits) .f_cards else null, }; } fn pairedBoundsAccepted(flat: Bound, tree: Bound, expected_control_bound: ?Bound) bool { return flat == (expected_control_bound orelse .none) and tree == .none; } fn runOne(comptime policy: type, gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, arm: Arm, rss: *RssAccumulator) !RunRecord { var captured = try runCaptured(policy, gpa, io, cfg, commits, arm, rss); defer captured.deinit(gpa); return captured.record; } const PairedRun = struct { flat: RunRecord, tree: RunRecord, equal: bool, }; fn annotateCommonPrefix(pair: *PairedRun, prefix: CommonPrefix) void { pair.flat.semantic_prefix_commits = prefix.commits; pair.flat.expected_control_bound = prefix.expected_control_bound; pair.tree.semantic_prefix_commits = prefix.commits; pair.tree.expected_control_bound = prefix.expected_control_bound; if (prefix.expected_control_bound) |bound| { if (pair.flat.bound == .none) pair.flat.bound = bound; } } fn runPaired(gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, rss: *RssAccumulator) !PairedRun { var flat = try runCaptured(FlatReferencePolicy, gpa, io, cfg, commits, .flat_reference, rss); defer flat.deinit(gpa); var tree = try runCaptured(IncrementalTreePolicy, gpa, io, cfg, commits, .incremental_tree, rss); defer tree.deinit(gpa); if (flat.record.effective_commits != tree.record.effective_commits) { const safe_commits = @min(flat.record.effective_commits, tree.record.effective_commits); const flat_bound = if (flat.record.effective_commits == safe_commits) flat.record.bound else .none; const tree_bound = if (tree.record.effective_commits == safe_commits) tree.record.bound else .none; return runCommonSafePair(gpa, io, cfg, safe_commits, flat_bound, tree_bound, rss); } return compareCapturedRuns(gpa, &flat, &tree); } fn runCommonSafePair(gpa: std.mem.Allocator, io: std.Io, cfg: Config, safe_commits: u64, flat_bound: Bound, tree_bound: Bound, rss: *RssAccumulator) !PairedRun { var flat = try runCaptured(FlatReferencePolicy, gpa, io, cfg, safe_commits, .flat_reference, rss); defer flat.deinit(gpa); var tree = try runCaptured(IncrementalTreePolicy, gpa, io, cfg, safe_commits, .incremental_tree, rss); defer tree.deinit(gpa); flat.record.bound = flat_bound; tree.record.bound = tree_bound; return compareCapturedRuns(gpa, &flat, &tree); } fn compareCapturedRuns(gpa: std.mem.Allocator, flat: *CapturedRun, tree: *CapturedRun) !PairedRun { const root = try compareSampledTrees(gpa, &flat.store, flat.root_checkin, &tree.store, tree.root_checkin); const mid = try compareSampledTrees(gpa, &flat.store, flat.mid_checkin, &tree.store, tree.mid_checkin); const sampled = try compareSampledTrees(gpa, &flat.store, flat.sampled_checkin, &tree.store, tree.sampled_checkin); const final = try compareSampledTrees(gpa, &flat.store, flat.final_checkin, &tree.store, tree.final_checkin); const side_equal = if (flat.side_checkin) |checkin| blk: { const peer = tree.side_checkin orelse break :blk false; break :blk (try compareSampledTrees(gpa, &flat.store, checkin, &tree.store, peer)).equal; } else tree.side_checkin == null; const merge_equal = if (flat.merge_checkin) |checkin| blk: { const peer = tree.merge_checkin orelse break :blk false; break :blk (try compareSampledTrees(gpa, &flat.store, checkin, &tree.store, peer)).equal; } else tree.merge_checkin == null; const equal = root.equal and mid.equal and sampled.equal and final.equal and side_equal and merge_equal and flat.record.effective_commits == tree.record.effective_commits; flat.record.sampled = sampled.flat_digest; flat.record.equal_sampled_trees = equal; tree.record.sampled = sampled.tree_digest; tree.record.equal_sampled_trees = equal; return .{ .flat = flat.record, .tree = tree.record, .equal = equal }; } fn runCaptured(comptime policy: type, gpa: std.mem.Allocator, io: std.Io, cfg: Config, commits: u64, arm: Arm, rss: *RssAccumulator) !CapturedRun { if (corpusBounds(cfg, commits).bound != .none) return error.BoundExceeded; var store = try Store.init(gpa); errdefer store.deinit(gpa); const corpus_start = nowNs(io); const stream = try buildStream(gpa, cfg, commits); defer gpa.free(stream); const corpus_ns = nowNs(io) - corpus_start; var bounds = BoundsContext{ .io = io, .store = &store, .start_ns = nowNs(io), .total_commits = commits, }; var importer = if (comptime policy == IncrementalTreePolicy) try IncrementalImporter.initObserved(gpa, &store.log, store.treeStore(), .{ .submanifest = .{ .tree = cfg.k }, .tree_cache_bytes = cfg.cache_bytes }, .{ .bounds = &bounds }) else try FlatImporter.initObserved(gpa, &store.log, store.treeStore(), .{ .submanifest = .{ .tree = cfg.k }, .tree_cache_bytes = cfg.cache_bytes }, .{ .bounds = &bounds }); defer importer.deinit(); const cpu_start = selfCpuNs(); const import_start = nowNs(io); // No per-commit command ceiling is pinned here. The parser derives it from // the payload budget, so the root commit's `width` files sit orders of // magnitude below it instead of exactly at it; the assertion states the // headroom rather than trusting it. const export_limits: fast_export.Limits = .{ .max_line = 1024 * 1024, .max_data = 1024 * 1024 * 1024, .max_path = 4096, // The benchmark drives synthetic streams whose event count is the // dimension under test; a ceiling here would cap the measurement. .max_events = std.math.maxInt(u64), }; if (fast_export.fileCommandCeiling(export_limits) <= cfg.width) return error.BoundExceeded; try importer.ingestFastExport(stream, export_limits); bounds.finish(); const counters = importer.workCounters(); const retained_state_entries = importer.retainedStateEntries(); const effective_commits = counters.commits; if (effective_commits == 0) return error.GateFailed; const total_import_ns = nowNs(io) - import_start; const total_cpu_ns = selfCpuNs() - cpu_start; const import_ns = if (effective_commits > 1) bounds.replay_ns else total_import_ns; const cpu_ns = if (effective_commits > 1) bounds.replay_cpu_ns else total_cpu_ns; const finalize_cpu_start = selfCpuNs(); const finalize_start = nowNs(io); var refs = try importer.finalizeRefs(.{}); defer refs.deinit(gpa); const finalize_ns = nowNs(io) - finalize_start; const finalize_cpu_ns = selfCpuNs() - finalize_cpu_start; const semantic_start = nowNs(io); const root_mark = cfg.width + 1; const mid_commit = if (effective_commits == 1) 1 else (effective_commits + 1) / 2; const mid_mark = cfg.width + 1 + (mid_commit - 1) * (cfg.changed + 1); const sampled_commit = if (effective_commits == 1) 1 else 1 + (cfg.seed % (effective_commits - 1)); const sampled_mark = cfg.width + 1 + (sampled_commit - 1) * (cfg.changed + 1); const final_mark = cfg.width + 1 + (effective_commits - 1) * (cfg.changed + 1); const root_checkin = try gpa.dupe(u8, try importer.objectForMark(root_mark)); errdefer gpa.free(root_checkin); const mid_checkin = try gpa.dupe(u8, try importer.objectForMark(mid_mark)); errdefer gpa.free(mid_checkin); const sampled_checkin = try gpa.dupe(u8, try importer.objectForMark(sampled_mark)); errdefer gpa.free(sampled_checkin); const final_checkin = try gpa.dupe(u8, try importer.objectForMark(final_mark)); errdefer gpa.free(final_checkin); const side_checkin = if (cfg.branch_every != 0 and cfg.branch_every < effective_commits) try gpa.dupe(u8, try importer.objectForMark(cfg.width + 1 + cfg.branch_every * (cfg.changed + 1))) else null; errdefer if (side_checkin) |checkin| gpa.free(checkin); var merge_index = cfg.merge_every; while (cfg.merge_every != 0 and merge_index < effective_commits) : (merge_index += cfg.merge_every) { if (cfg.branch_every != 0 and merge_index >= cfg.branch_every and merge_index % cfg.branch_every != 0) break; } const merge_checkin = if (cfg.merge_every != 0 and cfg.branch_every != 0 and merge_index < effective_commits) try gpa.dupe(u8, try importer.objectForMark(cfg.width + 1 + merge_index * (cfg.changed + 1))) else null; errdefer if (merge_checkin) |checkin| gpa.free(checkin); const semantic = try rootSemanticDigest(gpa, &store, final_checkin); const semantic_ns = nowNs(io) - semantic_start; const total_wall = corpus_ns + total_import_ns + finalize_ns + semantic_ns; const timed_wall = combinedPhaseNs(import_ns, finalize_ns); const f_cards = bounds.f_cards; // This is reported by the actual policy result root, not selected by arm. const bound: Bound = bounds.fired orelse if (f_cards >= max_f_cards) .f_cards else if (store.file.bytes.items.len >= max_new_store_bytes) .store_bytes else if (total_wall >= max_wall_ns) .wall_time else .none; if (arm == .incremental_tree and counters.inherited_full_tree_materializations != 0) return error.GateFailed; const process_peak_rss_bytes = peakRssBytes(); rss.observe(process_peak_rss_bytes); return .{ .record = .{ .arm = arm, .effective_commits = effective_commits, .phase = .{ .corpus_ns = corpus_ns, .import_ns = import_ns, .finalize_ns = finalize_ns, .semantic_ns = semantic_ns, .finalize_cpu_ns = finalize_cpu_ns, .wall_ns = timed_wall, .cpu_ns = combinedPhaseNs(cpu_ns, finalize_cpu_ns) }, .counters = counters, .store_bytes = store.file.bytes.items.len, .f_cards = f_cards, .bound = bound, .semantic = semantic, .sampled = semantic, .process_peak_rss_bytes = process_peak_rss_bytes, .retained_state_entries = retained_state_entries, }, .store = store, .root_checkin = root_checkin, .mid_checkin = mid_checkin, .side_checkin = side_checkin, .merge_checkin = merge_checkin, .sampled_checkin = sampled_checkin, .final_checkin = final_checkin, }; } fn widthDoublingRatio(gpa: std.mem.Allocator, io: std.Io, cfg: Config, rss: *RssAccumulator) !f64 { const post_seed_commits: u64 = 128; const measured_commits = 1 + post_seed_commits; var samples: [3]f64 = undefined; for (&samples) |*sample| { const one = try runOne(IncrementalTreePolicy, gpa, io, cfg, measured_commits, .incremental_tree, rss); var doubled = cfg; doubled.width *= 2; const two = try runOne(IncrementalTreePolicy, gpa, io, doubled, measured_commits, .incremental_tree, rss); const one_edits = one.counters.changed_paths -| cfg.width; const two_edits = two.counters.changed_paths -| doubled.width; const expected_edits = post_seed_commits * cfg.changed; if (one_edits != expected_edits or two_edits != expected_edits or one.counters.tree_apply_count != post_seed_commits or two.counters.tree_apply_count != post_seed_commits or one.counters.tree_apply_cpu_ns == 0 or two.counters.tree_apply_cpu_ns == 0) return error.GateFailed; sample.* = @as(f64, @floatFromInt(two.counters.tree_apply_cpu_ns)) / @as(f64, @floatFromInt(one.counters.tree_apply_cpu_ns)); } std.sort.pdq(f64, &samples, {}, std.sort.asc(f64)); return samples[1]; } fn corpusBounds(cfg: Config, commits: u64) CorpusBounds { const post_first_commits = commits -| 1; const changed_blobs = std.math.mul(u64, post_first_commits, cfg.changed) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; const blobs = std.math.add(u64, cfg.width, changed_blobs) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; const records = std.math.add(u64, blobs, commits) catch return .{ .records = max_f_cards, .bytes = max_stream_bytes, .bound = .f_cards, }; if (records >= max_f_cards) return .{ .records = records, .bytes = max_stream_bytes, .bound = .f_cards }; const blob_bytes = std.math.mul(u64, blobs, max_blob_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const commit_bytes = std.math.mul(u64, commits, max_commit_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const command_bytes = std.math.mul(u64, blobs, max_command_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const bytes = std.math.add(u64, stream_fixed_bytes, blob_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const after_commits = std.math.add(u64, bytes, commit_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; const total_bytes = std.math.add(u64, after_commits, command_bytes) catch return .{ .records = records, .bytes = max_stream_bytes, .bound = .store_bytes }; if (total_bytes >= max_stream_bytes) return .{ .records = records, .bytes = total_bytes, .bound = .store_bytes }; return .{ .records = records, .bytes = total_bytes, .bound = .none }; } fn productionGateFailure(bounds_clear: bool, full_semantic_clear: bool, retained_state_clear: bool, rss_clear: bool, wall: f64, cpu: f64, width_ratio: f64) []const u8 { if (!bounds_clear) return "bound_exceeded"; if (!full_semantic_clear) return "full_semantic_mismatch"; if (!retained_state_clear) return "retained_state"; if (!rss_clear) return "peak_rss"; if (!scalePass(wall)) return "scale_wall"; if (!scalePass(cpu)) return "scale_cpu"; if (width_ratio > 1.5) return "width_doubling_cpu"; return "none"; } fn secondCommitOffset(stream: []const u8) ?usize { const first = std.mem.indexOf(u8, stream, "\ncommit ") orelse return null; return std.mem.indexOfPos(u8, stream, first + 1, "\ncommit "); } fn expectSameSemantics(flat: RunRecord, tree: RunRecord) !void { if (!std.mem.eql(u8, &flat.semantic, &tree.semantic)) return error.SemanticMismatch; } fn buildStream(gpa: std.mem.Allocator, cfg: Config, commits: u64) ![]u8 { const bounds = corpusBounds(cfg, commits); if (bounds.bound != .none) return error.BoundExceeded; var out = std.ArrayList(u8).empty; errdefer out.deinit(gpa); try out.ensureTotalCapacity(gpa, @intCast(bounds.bytes)); try out.appendSlice(gpa, "feature done\n"); var mark: u64 = 0; var file: u64 = 0; while (file < cfg.width) : (file += 1) { mark += 1; try appendBlob(&out, gpa, mark, cfg.seed, file, 0); } var main_head: u64 = 0; var side_head: u64 = 0; var commit: u64 = 0; while (commit < commits) : (commit += 1) { var changed: u64 = 0; const command_count = if (commit == 0) cfg.width else cfg.changed; const first_blob = if (commit == 0) @as(u64, 1) else mark + 1; if (commit != 0) while (changed < cfg.changed) : (changed += 1) { mark += 1; try appendBlob(&out, gpa, mark, cfg.seed, try churnIndex(cfg, commit, changed), commit + 1); }; const commit_mark = mark + 1; mark = commit_mark; const on_side = cfg.branch_every != 0 and commit != 0 and commit % cfg.branch_every == 0; const ref = if (on_side) "refs/heads/side" else "refs/heads/main"; const first_parent = if (on_side) if (side_head != 0) side_head else main_head else main_head; try appendFormat(&out, gpa, "commit {s}\nmark :{d}\nauthor Bench <[email protected]> {d} +0000\ncommitter Bench <[email protected]> {d} +0000\ndata 5\nbench\n", .{ ref, mark, 1_700_000_000 + commit, 1_700_000_000 + commit }); if (first_parent != 0) try appendFormat(&out, gpa, "from :{d}\n", .{first_parent}); if (!on_side and side_head != 0 and cfg.merge_every != 0 and commit % cfg.merge_every == 0) try appendFormat(&out, gpa, "merge :{d}\n", .{side_head}); changed = 0; while (changed < command_count) : (changed += 1) try appendFormat(&out, gpa, "M 100644 :{d} file-{d:0>8}\n", .{ first_blob + changed, if (commit == 0) changed else try churnIndex(cfg, commit, changed) }); out.append(gpa, '\n') catch return error.OutOfMemory; if (on_side) side_head = mark else main_head = mark; } try out.appendSlice(gpa, "done\n"); return out.toOwnedSlice(gpa); } fn appendBlob(out: *std.ArrayList(u8), gpa: std.mem.Allocator, mark: u64, seed: u64, file: u64, version: u64) !void { var body: [32]u8 = undefined; std.mem.writeInt(u64, body[0..8], seed, .little); std.mem.writeInt(u64, body[8..16], file, .little); std.mem.writeInt(u64, body[16..24], version, .little); std.mem.writeInt(u64, body[24..32], std.hash.Wyhash.hash(seed, std.mem.asBytes(&file)), .little); try appendFormat(out, gpa, "blob\nmark :{d}\ndata {d}\n", .{ mark, body.len }); try out.appendSlice(gpa, &body); try out.append(gpa, '\n'); } fn appendFormat(out: *std.ArrayList(u8), gpa: std.mem.Allocator, comptime format: []const u8, args: anytype) !void { var buffer: [512]u8 = undefined; const line = std.fmt.bufPrint(&buffer, format, args) catch return error.OutOfMemory; try out.appendSlice(gpa, line); } fn churnIndex(cfg: Config, _: u64, changed: u64) Error!u64 { // Repeatedly mutate the same deterministic sparse working set. This keeps // the workload's inherited-tree cost stable while exercising the canonical // path rewriter rather than accidentally turning a scaling control into a // breadth-first mutation sweep. const index = std.math.add(u64, cfg.seed, changed) catch return error.BadArgs; return index % cfg.width; } fn corpusFingerprint(stream: []const u8) [32]u8 { var digest: [32]u8 = undefined; var hasher = std.crypto.hash.sha2.Sha256.init(.{}); hasher.update(stream); hasher.final(&digest); return digest; } const SemanticRoot = union(enum) { flat: []const artifact.FCard, tree: []const artifact.SCard, }; fn rootSemanticDigest(gpa: std.mem.Allocator, store: *Store, checkin: []const u8) ![32]u8 { var raw: [32]u8 = undefined; const digest = rawHashName(checkin, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; const bytes = (try store.log.content(gpa, rid)) orelse return error.SemanticMismatch; defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); var hasher = std.crypto.hash.sha2.Sha256.init(.{}); const root: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try hashRoot(&hasher, gpa, store, root); var result: [32]u8 = undefined; hasher.final(&result); return result; } fn compareSampledTrees(gpa: std.mem.Allocator, flat_store: *Store, flat_checkin: []const u8, tree_store: *Store, tree_checkin: []const u8) !SampleComparison { var flat_cards = try flattenCheckin(gpa, flat_store, flat_checkin); defer deinitCards(gpa, &flat_cards); var tree_cards = try flattenCheckin(gpa, tree_store, tree_checkin); defer deinitCards(gpa, &tree_cards); std.mem.sort(artifact.FCard, flat_cards.items, {}, lessCard); std.mem.sort(artifact.FCard, tree_cards.items, {}, lessCard); const flat_digest = try digestLeaves(gpa, flat_store, flat_cards.items); const tree_digest = try digestLeaves(gpa, tree_store, tree_cards.items); var equal = flat_cards.items.len == tree_cards.items.len; const common = @min(flat_cards.items.len, tree_cards.items.len); for (flat_cards.items[0..common], tree_cards.items[0..common]) |flat, tree| { if (!std.mem.eql(u8, flat.filename, tree.filename) or flat.mode != tree.mode or !optionalBytesEqual(flat.perm, tree.perm) or !optionalBytesEqual(flat.hash, tree.hash)) equal = false; const flat_blob = try verifiedBlob(gpa, flat_store, flat); defer gpa.free(flat_blob); const tree_blob = try verifiedBlob(gpa, tree_store, tree); defer gpa.free(tree_blob); if (!std.mem.eql(u8, flat_blob, tree_blob)) equal = false; } return .{ .flat_digest = flat_digest, .tree_digest = tree_digest, .equal = equal }; } fn flattenCheckin(gpa: std.mem.Allocator, store: *Store, checkin: []const u8) !std.ArrayList(artifact.FCard) { var cards = std.ArrayList(artifact.FCard).empty; errdefer deinitCards(gpa, &cards); try appendStoredManifest(gpa, store, checkin, &cards); return cards; } fn appendStoredManifest(gpa: std.mem.Allocator, store: *Store, name: []const u8, cards: *std.ArrayList(artifact.FCard)) !void { const bytes = try storedArtifact(gpa, store, name); defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); if (manifest.s.len == 0) { for (manifest.f) |card| try cards.append(gpa, try cloneCard(gpa, card)); return; } for (manifest.s) |sub| try appendStoredManifest(gpa, store, sub.hash, cards); } fn deinitCards(gpa: std.mem.Allocator, cards: *std.ArrayList(artifact.FCard)) void { for (cards.items) |card| { gpa.free(card.filename); if (card.hash) |hash| gpa.free(hash); if (card.perm) |perm| gpa.free(perm); if (card.old_name) |old_name| gpa.free(old_name); } cards.deinit(gpa); } fn digestLeaves(gpa: std.mem.Allocator, store: *Store, cards: []const artifact.FCard) ![32]u8 { var hasher = std.crypto.hash.sha2.Sha256.init(.{}); for (cards) |card| { const blob = try verifiedBlob(gpa, store, card); defer gpa.free(blob); hasher.update(card.filename); hasher.update(@tagName(card.mode)); hasher.update(card.perm orelse ""); hasher.update(card.hash orelse ""); hasher.update(blob); } var digest: [32]u8 = undefined; hasher.final(&digest); return digest; } fn verifiedBlob(gpa: std.mem.Allocator, store: *Store, card: artifact.FCard) ![]u8 { const hash = card.hash orelse return error.SemanticMismatch; const bytes = try storedArtifact(gpa, store, hash); errdefer gpa.free(bytes); var expected: [64]u8 = undefined; if (!std.mem.eql(u8, hash, artifact.artifactName(git_import.import_hash_algo, bytes, &expected))) return error.SemanticMismatch; return bytes; } fn storedArtifact(gpa: std.mem.Allocator, store: *Store, name: []const u8) ![]u8 { var raw: [32]u8 = undefined; const digest = rawHashName(name, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; return (try store.log.content(gpa, rid)) orelse error.SemanticMismatch; } fn optionalBytesEqual(a: anytype, b: anytype) bool { if (a) |a_value| { if (b) |b_value| return std.mem.eql(u8, a_value, b_value); return false; } return b == null; } fn hashRoot(hasher: anytype, gpa: std.mem.Allocator, store: *Store, root: SemanticRoot) !void { switch (root) { .flat => |flat| for (flat) |card| { hasher.update(card.filename); hasher.update(card.hash orelse ""); hasher.update(card.perm orelse ""); hasher.update(@tagName(card.mode)); }, .tree => |tree| for (tree) |sub| { var raw: [32]u8 = undefined; const digest = rawHashName(sub.hash, &raw) orelse return error.SemanticMismatch; const rid = store.log.lookup(digest) orelse return error.SemanticMismatch; const bytes = (try store.log.content(gpa, rid)) orelse return error.SemanticMismatch; defer gpa.free(bytes); var manifest = try artifact.parse(gpa, bytes); defer manifest.deinit(); const child: SemanticRoot = if (manifest.s.len == 0) .{ .flat = manifest.f } else .{ .tree = manifest.s }; try hashRoot(hasher, gpa, store, child); }, } } fn rawHashName(name: []const u8, buffer: *[32]u8) ?[]const u8 { if (name.len != 40) return null; const raw = buffer[0..20]; _ = std.fmt.hexToBytes(raw, name) catch return null; return raw; } fn checkoutRevision(gpa: std.mem.Allocator, io: std.Io) ![40]u8 { const result = std.process.run(gpa, io, .{ .argv = &.{ "fossil", "info" } }) catch return error.ProvenanceUnavailable; defer gpa.free(result.stdout); defer gpa.free(result.stderr); const succeeded = switch (result.term) { .exited => |code| code == 0, else => false, }; if (!succeeded) return error.ProvenanceUnavailable; return revisionFromFossilInfo(result.stdout) orelse error.ProvenanceUnavailable; } fn revisionFromFossilInfo(output: []const u8) ?[40]u8 { var lines = std.mem.splitScalar(u8, output, '\n'); while (lines.next()) |line| { const trimmed = std.mem.trim(u8, line, " \t\r"); if (!std.mem.startsWith(u8, trimmed, "checkout:")) continue; const value = std.mem.trim(u8, trimmed["checkout:".len..], " \t"); var end: usize = 0; while (end < value.len and value[end] != ' ' and value[end] != '\t') : (end += 1) {} if (end != 40) return null; var revision: [40]u8 = undefined; @memcpy(revision[0..], value[0..end]); var raw: [20]u8 = undefined; _ = std.fmt.hexToBytes(raw[0..], revision[0..]) catch return null; return revision; } return null; } fn nowNs(io: std.Io) u64 { const ns = std.Io.Clock.Timestamp.now(io, .awake).raw.nanoseconds; return if (ns < 0) 0 else @intCast(ns); } const RusageSelector = enum(i32) { self = 0, }; const process_cpu_clock = "process_rusage"; fn selfCpuNs() u64 { const usage = std.posix.getrusage(@intFromEnum(RusageSelector.self)); const seconds: u64 = @intCast(usage.utime.sec + usage.stime.sec); const micros: u64 = @intCast(usage.utime.usec + usage.stime.usec); return seconds * std.time.ns_per_s + micros * std.time.ns_per_us; } fn peakRssBytes() u64 { const usage = std.posix.getrusage(@intFromEnum(RusageSelector.self)); const rss: u64 = @intCast(@max(usage.maxrss, 0)); return if (builtin.os.tag == .macos) rss else rss * 1024; } fn combinedPhaseNs(import_ns: u64, finalize_ns: u64) u64 { return std.math.add(u64, import_ns, finalize_ns) catch std.math.maxInt(u64); } fn ratio(big: u64, small: u64) f64 { return @as(f64, @floatFromInt(big)) / @as(f64, @floatFromInt(@max(small, 1))); } fn gateFailure(flat_wall: f64, tree_wall: f64, flat_cpu: f64, tree_cpu: f64, width_ratio: f64, equal_sampled_trees: bool, bounds_clear: bool, retained_state_clear: bool, rss_clear: bool) []const u8 { if (!bounds_clear) return "bound_exceeded"; if (!equal_sampled_trees) return "sampled_tree_mismatch"; if (!retained_state_clear) return "retained_state"; if (!rss_clear) return "peak_rss"; if (!scalePass(flat_wall)) return "flat_wall_scale"; if (!scalePass(tree_wall)) return "tree_wall_scale"; if (!scalePass(flat_cpu)) return "flat_cpu_scale"; if (!scalePass(tree_cpu)) return "tree_cpu_scale"; if (width_ratio > 1.5) return "width_doubling_cpu"; return "none"; } fn medianRatio(records: []const RunRecord, comptime wall: bool) f64 { var values: [7]f64 = undefined; for (records, 0..) |record, index| values[index] = if (wall) record.wall_scale_ratio else record.cpu_scale_ratio; std.mem.sort(f64, values[0..records.len], {}, struct { fn less(_: void, a: f64, b: f64) bool { return a < b; } }.less); return values[records.len / 2]; } fn scalePass(value: f64) bool { return value >= 1.6 and value <= 2.4; } fn retainedStateConstant(cfg: Config, record: RunRecord) bool { const limit: usize = @intCast(6 * (record.counters.blobs + record.counters.commits + record.counters.resets + record.counters.tags + 1)); return record.retained_state_entries <= limit and record.counters.cache_high_water_bytes <= cfg.cache_bytes and (record.arm == .flat_reference or record.counters.inherited_full_tree_materializations == 0); } fn executableHash(io: std.Io, gpa: std.mem.Allocator, executable: []const u8) ![32]u8 { const cwd = try std.process.currentPathAlloc(io, gpa); defer gpa.free(cwd); const path = try std.fs.path.resolve(gpa, &.{ cwd, executable }); defer gpa.free(path); var file = std.Io.Dir.openFileAbsolute(io, path, .{ .mode = .read_only }) catch return error.Io; defer file.close(io); const stat = file.stat(io) catch return error.Io; var hasher = std.crypto.hash.sha2.Sha256.init(.{}); var bytes: [64 * 1024]u8 = undefined; var offset: u64 = 0; while (offset < stat.size) { const len: usize = @intCast(@min(stat.size - offset, @as(u64, bytes.len))); const n = file.readPositionalAll(io, bytes[0..len], offset) catch return error.Io; if (n != len) return error.Io; hasher.update(bytes[0..len]); offset += len; } var result: [32]u8 = undefined; hasher.final(&result); return result; } fn writeJsonl(out: *std.Io.Writer, cfg: Config, executable: [32]u8, fingerprint: [32]u8, record: RunRecord, wall_ratio: f64, cpu_ratio: f64, width_ratio: f64, aggregate_peak_rss_bytes: u64, full_semantic_clear: bool, failed_gate: []const u8) !void { const executable_hex = std.fmt.bytesToHex(executable, .lower); const fingerprint_hex = std.fmt.bytesToHex(fingerprint, .lower); const semantic_hex = std.fmt.bytesToHex(record.semantic, .lower); const sample_hex = std.fmt.bytesToHex(record.sampled, .lower); const equality_json = if (record.equal_sampled_trees) |equal| if (equal) "true" else "false" else "null"; const retained_state_constant = retainedStateConstant(cfg, record); try out.print( "{{\"schema\":\"zit.import-git-benchmark.v1\",\"arm\":\"{s}\",\"binary_sha256\":\"{s}\",\"revision\":\"{s}\",\"platform\":\"{s}-{s}\",\"corpus_fingerprint\":\"{s}\",\"seed\":{d},\"width\":{d},\"requested_commits\":{d},\"effective_commits\":{d},\"semantic_prefix_commits\":{d},\"expected_control_bound\":\"{s}\",\"changed_paths\":{d},\"branch_every\":{d},\"merge_every\":{d},\"k\":{d},\"repetitions\":{d},\"cache_budget_bytes\":{d},\"max_rss_bytes\":{d},", .{ @tagName(record.arm), executable_hex, cfg.revision, @tagName(builtin.os.tag), @tagName(builtin.cpu.arch), fingerprint_hex, cfg.seed, cfg.width, cfg.commits, record.effective_commits, record.semantic_prefix_commits, @tagName(record.expected_control_bound orelse .none), cfg.changed, cfg.branch_every, cfg.merge_every, cfg.k, cfg.reps, cfg.cache_bytes, cfg.max_rss_bytes }, ); try out.print( "\"process_cpu_clock\":\"{s}\",\"phases_ns\":{{\"corpus\":{d},\"import\":{d},\"finalize\":{d},\"finalize_cpu\":{d},\"semantic\":{d},\"wall\":{d},\"cpu\":{d}}},\"counters\":{{\"blobs\":{d},\"commits\":{d},\"resets\":{d},\"tags\":{d},\"changed_paths\":{d},\"max_tree_height\":{d},\"emitted_nodes\":{d},\"reused_nodes\":{d},\"cache_high_water_bytes\":{d},\"inherited_full_tree_materializations\":{d},\"tree_apply_count\":{d},\"tree_apply_cpu_ns\":{d},\"tree_apply_cpu_clock\":\"{s}\"}},", .{ process_cpu_clock, record.phase.corpus_ns, record.phase.import_ns, record.phase.finalize_ns, record.phase.finalize_cpu_ns, record.phase.semantic_ns, record.phase.wall_ns, record.phase.cpu_ns, record.counters.blobs, record.counters.commits, record.counters.resets, record.counters.tags, record.counters.changed_paths, record.counters.max_tree_height, record.counters.emitted_nodes, record.counters.reused_nodes, record.counters.cache_high_water_bytes, record.counters.inherited_full_tree_materializations, record.counters.tree_apply_count, record.counters.tree_apply_cpu_ns, @tagName(record.counters.tree_apply_cpu_clock) }, ); try out.print( "\"store_bytes\":{d},\"emitted_f_cards\":{d},\"bound\":\"{s}\",\"process_peak_rss_bytes\":{d},\"aggregate_peak_rss_bytes\":{d},\"retained_state_entries\":{d},\"semantic_digest\":\"{s}\",\"sampled_tree_digest\":\"{s}\",\"equal_sampled_trees\":{s},\"failed_gate\":\"{s}\",\"gates\":{{\"scale_wall_median\":{d},\"scale_cpu_median\":{d},\"width_doubling_cpu\":{d},\"cache_bound\":{},\"peak_rss_within_limit\":{},\"full_semantic_check\":{},\"retained_state_constant\":{},\"production_no_inherited_full_list\":{}}}}}\n", .{ record.store_bytes, record.f_cards, @tagName(record.bound), record.process_peak_rss_bytes, aggregate_peak_rss_bytes, record.retained_state_entries, semantic_hex, sample_hex, equality_json, failed_gate, wall_ratio, cpu_ratio, width_ratio, record.counters.cache_high_water_bytes <= cfg.cache_bytes, aggregate_peak_rss_bytes <= cfg.max_rss_bytes, full_semantic_clear, retained_state_constant, record.arm == .flat_reference or record.counters.inherited_full_tree_materializations == 0 }, ); } test "git import benchmark corpus bounds reject overflow and oversized streams" { const normal = corpusBounds(.{ .width = 2, .commits = 2, .changed = 1 }, 2); try std.testing.expectEqual(Bound.none, normal.bound); const overflow = corpusBounds(.{ .width = std.math.maxInt(u64), .commits = std.math.maxInt(u64), .changed = std.math.maxInt(u64), }, std.math.maxInt(u64)); try std.testing.expectEqual(Bound.f_cards, overflow.bound); const oversized = corpusBounds(.{ .width = 500_000, .commits = 1, .changed = 1 }, 1); try std.testing.expectEqual(Bound.store_bytes, oversized.bound); const full = corpusBounds(.{ .full = true, .width = 100_000, .commits = 100_000, .changed = 100_000 }, 100_000); try std.testing.expectEqual(Bound.f_cards, full.bound); } test "git import benchmark reports its proactive flat control cap" { const prefix = commonPrefix(.{ .width = 20_000, .commits = 1_000 }); try std.testing.expectEqual(@as(u64, 499), prefix.commits); try std.testing.expectEqual(@as(?Bound, .f_cards), prefix.expected_control_bound); try std.testing.expect(pairedBoundsAccepted(.f_cards, .none, prefix.expected_control_bound)); const full_prefix = commonPrefix(.{ .full = true, .width = 100_000, .commits = 100_000 }); try std.testing.expectEqual(@as(u64, 99), full_prefix.commits); try std.testing.expectEqual(@as(?Bound, .f_cards), full_prefix.expected_control_bound); } test "git import benchmark rejects unexpected control and tree bounds" { try std.testing.expect(!pairedBoundsAccepted(.none, .none, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.store_bytes, .none, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.f_cards, .f_cards, .f_cards)); try std.testing.expect(!pairedBoundsAccepted(.f_cards, .none, null)); } test "git import benchmark churn index accepts the max seed boundary and rejects overflow" { const max = std.math.maxInt(u64); try std.testing.expectEqual(max % 2, try churnIndex(.{ .seed = max - 1, .width = 2 }, 0, 1)); try std.testing.expectError(error.BadArgs, churnIndex(.{ .seed = max, .width = 2 }, 0, 1)); const boundary = try parseArgs(&.{ "import-git-bench", "--seed", "18446744073709551614", "--changed", "2" }); try std.testing.expectEqual(max - 1, boundary.seed); try std.testing.expectError(error.BadArgs, parseArgs(&.{ "import-git-bench", "--seed", "18446744073709551615", "--changed", "2" })); } test "git import benchmark production gate includes retained state" { const failed_gate = productionGateFailure(true, true, false, true, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("retained_state", failed_gate); } test "git import benchmark full semantic gate rejects reference disagreement" { const failed_gate = productionGateFailure(true, false, true, true, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("full_semantic_mismatch", failed_gate); } test "git import benchmark scaling includes finalize refs" { const small = combinedPhaseNs(100, 100); const quadratic_finalize = combinedPhaseNs(200, 1_000); try std.testing.expect(!scalePass(ratio(quadratic_finalize, small))); } test "git import benchmark peak RSS gate rejects one byte over limit" { const limit = default_max_rss_bytes; const failed_gate = productionGateFailure(true, true, true, limit + 1 <= limit, 2.0, 2.0, 1.0); try std.testing.expectEqualStrings("peak_rss", failed_gate); }