//! Storage measurement harness (storage-efficiency survey, step 1: bytes at
//! rest per frame class + serve CPU).
//!
//! `zig build bench -- storage [<.zit path>]`. Reads a `.zit` (a real store
//! passed by path, or a seeded synthetic corpus built in a temp file) and
//! reports, over the physical file, WITHOUT modifying it:
//!
//! 1. bytes at rest by `FrameKind` (raw/zlib/delta/config): frame count,
//! on-disk bytes, % of store, avg bytes/frame, and the header+padding
//! overhead per kind (so "frame overhead is ~1%" is a measured fact);
//! 2. bytes by artifact TYPE — each content artifact is classified as a
//! check-in/manifest (its bytes parse as a §4/§5 structural artifact) or
//! a file blob (they do not), so "how much of the byte budget is
//! manifests" is a number, not a guess;
//! 3. a compression-headroom probe over a sample of full-form (`.zlib`)
//! frames — uncompressed vs the current zlib-compressed size — quantifying
//! the delta-miss population a global codec/dictionary could target;
//! 4. serve CPU — time to produce the §4.1/§7.2 wire form for each artifact
//! (verbatim `wire()` for a stored container, on-the-fly `container.encode`
//! for a raw frame, mirroring the serve loop), in us/artifact and MB/s.
//!
//! `storage --probe-manifest [<path>]` runs a SEPARATE read-only projection
//! (survey §2.5): it PROJECTS — without implementing — the win from a
//! Courgette-style transform of check-in manifests. (Courgette is Chromium's
//! differential updater, which rewrites absolute references into a canonical,
//! more-compressible form before diffing:
//! chromium.org/developers/design-documents/software-updates-courgette.) Each
//! manifest's 40/64-hex artifact-name tokens that resolve in the store index
//! become a varint of the artifact's rid ordinal; structural residue is kept
//! byte-for-byte; a token that does not resolve is left verbatim (fallback).
//! The projected bytes are zlib-compressed and compared against the current
//! manifest compressed size, so the reported win is a REAL compressed delta
//! (hex already compresses ~2x under zlib), never an uncompressed count. Like
//! the storage report it writes nothing and asserts no performance claim.
//!
//! There is no RFC oracle behind a benchmark, so this file implements no
//! normative clause and asserts no comparative claim: it is measurement
//! INFRASTRUCTURE — it makes no performance claim itself, it lets the survey
//! ideas be weighed honestly. The one testable property is exact accounting:
//! `header + raw + zlib + delta + config == file size`, checked by the frame
//! walk reaching the file end exactly.
//!
//! Everything effectful goes through the injected `std.Io`: the monotonic clock
//! (`Io.Timestamp.now(io, .awake)`) and the backing file. The store is read
//! ONLY through `LogStore.openReadOnly` (which never creates, rewrites, or
//! truncates) plus positional reads for the frame walk; a diagnostic must not
//! mutate the store it measures. Synthetic corpus bytes derive solely from the
//! `--seed`, so a run replays exactly.
const std = @import("std");
const Io = std.Io;
const zit = @import("zit");
const artifact = zit.artifact;
const codec = zit.container;
const storage = @import("zit_storage");
const logstore = @import("zit_logstore");
/// Closed harness error set. `Storage`/`Corrupt` propagate from LogStore, `Io`
/// is a failed file syscall (open/stat/read), `BadArgs` is a rejected flag.
/// Printing adds the writer's own error set; never `anyerror`.
pub const Error = error{ OutOfMemory, Storage, Corrupt, Io, BadArgs };
pub const RunError = Error || Io.Writer.Error;
// ---------------------------------------------------------------------------
// Explicit fixed caps (TigerStyle bounds); each overflow -> BadArgs.
// ---------------------------------------------------------------------------
const max_count: u64 = 1_000_000;
const min_blob: u64 = 32; // room for the 8-byte index prefix + mutations.
const max_blob: u64 = 16 << 20;
const max_frac: u64 = 100;
/// Full-form frames sampled for the compression-headroom probe.
const headroom_sample_cap: usize = 1024;
/// SHA-256 content-address width the corpus synthesizes for every artifact.
const hash_len: usize = 32;
/// One synthetic-corpus shape (all inputs arrive from argv only). Defaults give
/// a mixed store: many small check-in manifests plus larger, chained file
/// blobs, so every frame kind and both artifact types are exercised.
const Config = struct {
seed: u64 = 1234,
count: u64 = 500,
blob: u64 = 2048,
/// Percent of artifacts emitted as check-in manifests (the rest are blobs).
manifest_frac: u64 = 45,
};
/// Where the measured `.zit` comes from.
const Source = union(enum) { path: []const u8, synthetic: Config };
/// Which report the harness produces: `measure` is the storage survey (frame
/// kinds, artifact types, headroom, serve CPU); `probe_manifest` is the §2.5
/// manifest-transform projection. Both are read-only over the same source.
const Mode = enum { measure, probe_manifest };
/// A parsed invocation: the report to run and the store to run it over.
const Command = struct { mode: Mode, source: Source };
// ---------------------------------------------------------------------------
// Entry point + argument parsing.
// ---------------------------------------------------------------------------
/// Dispatched from logstore_benchmark's `run` when argv[1] == "storage". `args`
/// is the whole process argv; a bare `[<path>]` and the synthetic flags begin
/// at index 2.
pub fn run(gpa: std.mem.Allocator, io: Io, args: []const []const u8, out: *Io.Writer) RunError!void {
const cmd = try parseArgs(args);
switch (cmd.source) {
.path => |p| try runPath(gpa, io, cmd.mode, p, out),
.synthetic => |cfg| try runSynthetic(gpa, io, cmd.mode, cfg, out),
}
try out.flush();
}
/// An optional leading `--probe-manifest` selects the projection report; the
/// remaining tokens name the source (a `.zit` path, or `--flag value` pairs
/// configuring the synthetic corpus).
fn parseArgs(args: []const []const u8) Error!Command {
std.debug.assert(args.len >= 2);
var i: usize = 2;
var mode: Mode = .measure;
if (i < args.len and std.mem.eql(u8, args[i], "--probe-manifest")) {
mode = .probe_manifest;
i += 1;
}
return .{ .mode = mode, .source = try parseSource(args, i) };
}
/// A leading non-`--` token is a `.zit` path (a real store); otherwise every
/// argument is a `--flag value` pair configuring the synthetic corpus.
fn parseSource(args: []const []const u8, start: usize) Error!Source {
var i: usize = start;
if (i < args.len and !std.mem.startsWith(u8, args[i], "--")) {
// A real store: the path is the sole positional; no flags follow it.
if (i + 1 != args.len) return error.BadArgs;
return .{ .path = args[i] };
}
var cfg = Config{};
while (i < args.len) : (i += 1) {
const flag = args[i];
i += 1;
if (i >= args.len) return error.BadArgs; // flag with no value
const val = std.fmt.parseInt(u64, args[i], 0) catch return error.BadArgs;
if (std.mem.eql(u8, flag, "--seed")) {
cfg.seed = val;
} else if (std.mem.eql(u8, flag, "--count")) {
cfg.count = val;
} else if (std.mem.eql(u8, flag, "--blob")) {
cfg.blob = val;
} else if (std.mem.eql(u8, flag, "--manifest-frac")) {
cfg.manifest_frac = val;
} else return error.BadArgs;
}
if (cfg.count < 1 or cfg.count > max_count) return error.BadArgs;
if (cfg.blob < min_blob or cfg.blob > max_blob) return error.BadArgs;
if (cfg.manifest_frac > max_frac) return error.BadArgs;
return .{ .synthetic = cfg };
}
// ---------------------------------------------------------------------------
// Source acquisition
// ---------------------------------------------------------------------------
/// Open a real `.zit` read-only and run `mode` over it. Filesystem access is
/// confined here; the store is never written.
fn runPath(gpa: std.mem.Allocator, io: Io, mode: Mode, path: []const u8, out: *Io.Writer) RunError!void {
var file = Io.Dir.openFileAbsolute(io, path, .{}) catch return error.Io;
defer file.close(io);
const st = file.stat(io) catch return error.Io;
var fs = storage.FileStorage.init(io, file, st.size);
try dispatch(gpa, io, mode, fs.storageFile(), st.size, path, out);
}
/// Build a seeded synthetic corpus in a throwaway temp file, run `mode` over
/// it, and unlink it. Same seed -> byte-identical file -> identical numbers.
fn runSynthetic(gpa: std.mem.Allocator, io: Io, mode: Mode, cfg: Config, out: *Io.Writer) RunError!void {
var temp = try Temp.create(io);
defer temp.cleanup(io);
var fs = storage.FileStorage.init(io, temp.file, 0);
try buildCorpus(gpa, fs.storageFile(), cfg);
const file_size = fs.storageFile().size() catch return error.Storage;
var name_buf: [96]u8 = undefined;
const label = std.fmt.bufPrint(&name_buf, "synthetic corpus seed={d} count={d} blob={d} manifest_frac={d}%", .{
cfg.seed, cfg.count, cfg.blob, cfg.manifest_frac,
}) catch return error.BadArgs;
// Re-open over the SAME file at its post-build size; the report reads only.
var fs2 = storage.FileStorage.init(io, temp.file, file_size);
try dispatch(gpa, io, mode, fs2.storageFile(), file_size, label, out);
}
/// Run the selected report over an opened source. Both branches read only.
fn dispatch(gpa: std.mem.Allocator, io: Io, mode: Mode, sfile: storage.StorageFile, file_size: u64, label: []const u8, out: *Io.Writer) RunError!void {
switch (mode) {
.measure => try measure(gpa, io, sfile, file_size, label, out),
.probe_manifest => try probeManifests(gpa, io, sfile, file_size, label, out),
}
}
// ---------------------------------------------------------------------------
// The measurement (read-only over the store)
// ---------------------------------------------------------------------------
fn measure(
gpa: std.mem.Allocator,
io: Io,
sfile: storage.StorageFile,
file_size: u64,
label: []const u8,
out: *Io.Writer,
) RunError!void {
// openReadOnly walks and whole-frame-CRC-verifies every frame, so the
// subsequent lightweight prefix-only frame walk reads trustworthy bytes.
var store = logstore.LogStore.openReadOnly(gpa, sfile) catch |e| return mapOpen(e);
defer store.deinit(gpa);
const bd = try walkFrames(sfile, file_size);
try reportFrameKinds(out, label, bd, file_size);
const rids = try store.ridsInPersistedOrder(gpa);
defer gpa.free(rids);
try reportArtifactTypes(gpa, &store, rids, file_size, out);
try reportHeadroom(gpa, &store, rids, out);
try reportServeCpu(gpa, io, &store, rids, out);
try out.writeAll("# zit-vs-fossil ratio: skipped (needs a cloneable fossil repo; network-dependent)\n");
}
// ---------------------------------------------------------------------------
// 1. Bytes at rest, by FrameKind — an independent physical frame walk.
// ---------------------------------------------------------------------------
/// Per-kind byte accounting. Indexed by `@intFromEnum(FrameKind)` (raw=0,
/// zlib=1, delta=2, config=3). `on_disk` is the aligned frame span; `payload`
/// is the on-disk (raw/container) payload length; `overhead` is header+padding
/// (`on_disk - payload`).
const Breakdown = struct {
count: [4]u64 = .{ 0, 0, 0, 0 },
on_disk: [4]u64 = .{ 0, 0, 0, 0 },
payload: [4]u64 = .{ 0, 0, 0, 0 },
overhead: [4]u64 = .{ 0, 0, 0, 0 },
fn total_on_disk(self: Breakdown) u64 {
return self.on_disk[0] + self.on_disk[1] + self.on_disk[2] + self.on_disk[3];
}
fn total_overhead(self: Breakdown) u64 {
return self.overhead[0] + self.overhead[1] + self.overhead[2] + self.overhead[3];
}
};
/// A frame's on-disk span (logstore.zig frame layout): the fixed header
/// (`len|flags|hash_len|prefix_crc|hash|delta_of|header_crc` = 22 + hash_len),
/// the payload, and the 4-byte whole-frame CRC, padded up to an 8-byte
/// boundary — i.e. `align8(26 + hash_len + payload_len)`.
fn frameSpan(hash_len_b: u8, payload_len: u64) u64 {
return alignUp8(26 + @as(u64, hash_len_b) + payload_len);
}
fn alignUp8(n: u64) u64 {
return (n + 7) / 8 * 8;
}
/// Walk every frame from its physical bytes, classifying by the prefix flag
/// byte and summing spans by kind. Reads only the 10-byte fixed prefix
/// (`payload_len|flags|hash_len|prefix_crc`) of each frame — no payload, no
/// decode — so it is a cheap structural scan. The store was CRC-verified by
/// `openReadOnly` before this runs, so the prefix bytes are trustworthy.
/// Reaching `file_size` exactly is the exact-accounting invariant.
fn walkFrames(sfile: storage.StorageFile, file_size: u64) Error!Breakdown {
std.debug.assert(file_size >= logstore.header_len);
var bd = Breakdown{};
var offset: u64 = logstore.header_len;
// Each frame spans >= 8 bytes; the count can never exceed file_size/8.
const max_frames: u64 = file_size / logstore.frame_align + 1;
var seen: u64 = 0;
while (offset < file_size) {
seen += 1;
if (seen > max_frames) return error.Corrupt;
var prefix: [10]u8 = undefined;
const n = sfile.pread(offset, &prefix) catch return error.Storage;
if (n < prefix.len) return error.Corrupt; // a known frame is never short
const payload_len = std.mem.readInt(u32, prefix[0..4], .little);
const flags = prefix[4];
const hlen = prefix[5];
if (flags > @intFromEnum(logstore.FrameKind.config)) return error.Corrupt;
if (hlen < logstore.min_hash_len or hlen > logstore.max_hash_len) return error.Corrupt;
const span = frameSpan(hlen, payload_len);
const k: usize = flags;
bd.count[k] += 1;
bd.on_disk[k] += span;
bd.payload[k] += payload_len;
bd.overhead[k] += span - payload_len;
offset += span;
}
if (offset != file_size) return error.Corrupt; // frame boundaries must tile the file exactly
std.debug.assert(logstore.header_len + bd.total_on_disk() == file_size); // exact accounting
return bd;
}
const kind_names = [4][]const u8{ "raw", "zlib", "delta", "config" };
fn reportFrameKinds(out: *Io.Writer, label: []const u8, bd: Breakdown, file_size: u64) RunError!void {
try out.print("# storage bench: bytes at rest [{s}]\n\n", .{label});
try out.writeAll("frame-kind breakdown\n");
try out.writeAll("kind frames on-disk %store avg/frame overhead ovhd%\n");
for (0..4) |k| {
if (bd.count[k] == 0 and bd.on_disk[k] == 0) continue;
const avg = if (bd.count[k] == 0) 0 else bd.on_disk[k] / bd.count[k];
try out.print("{s:<8} {d:>6} {d:>10} {d:>5.1}% {d:>9} {d:>8} {d:>4.1}%\n", .{
kind_names[k], bd.count[k],
bd.on_disk[k], pct(bd.on_disk[k], file_size),
avg, bd.overhead[k],
pct(bd.overhead[k], bd.on_disk[k]),
});
}
try out.print("{s:<8} {d:>6} {d:>10}\n", .{ "header", @as(u64, 0), logstore.header_len });
try out.print("{s:<8} {d:>6} {d:>10} {d:>5.1}% {s:>9} {d:>8} {d:>4.1}%\n", .{
"total", bd.count[0] + bd.count[1] + bd.count[2] + bd.count[3],
file_size, @as(f64, 100.0),
"", bd.total_overhead(),
pct(bd.total_overhead() + logstore.header_len, file_size),
});
const accounted = logstore.header_len + bd.total_on_disk();
try out.print("# accounting: header(64) + raw + zlib + delta + config = {d} = file size ({s})\n\n", .{
accounted, if (accounted == file_size) "exact" else "MISMATCH",
});
}
// ---------------------------------------------------------------------------
// 2. Bytes by artifact TYPE — parse each content artifact's card grammar.
// ---------------------------------------------------------------------------
/// A content artifact is a check-in/manifest when its uncompressed bytes parse
/// as a §4/§5 structural artifact of type `manifest`; another structural type
/// (tag, cluster, wiki, ...) is `other`; anything that fails to parse is a file
/// blob (source content). Bytes are the on-disk frame span, so the totals here
/// reconcile with the raw+zlib+delta on-disk totals from the frame walk.
const TypeClass = enum(usize) { manifest = 0, other = 1, blob = 2 };
fn reportArtifactTypes(
gpa: std.mem.Allocator,
store: *logstore.LogStore,
rids: []const logstore.Rid,
file_size: u64,
out: *Io.Writer,
) RunError!void {
var count = [_]u64{ 0, 0, 0 };
var on_disk = [_]u64{ 0, 0, 0 };
for (rids) |rid| {
const span = frameSpan(@intCast(store.hashOf(rid).len), store.payloadLenOf(rid));
const content = (store.content(gpa, rid) catch |e| return mapContent(e)) orelse continue;
defer gpa.free(content);
const cls = classify(gpa, content) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
};
const i = @intFromEnum(cls);
count[i] += 1;
on_disk[i] += span;
}
try out.writeAll("artifact-type breakdown (content frames, on-disk bytes)\n");
try out.writeAll("type count on-disk %store\n");
const type_names = [_][]const u8{ "checkin/manifest", "other-artifact", "file-blob" };
for (0..3) |i| {
if (count[i] == 0) continue;
try out.print("{s:<16} {d:>6} {d:>10} {d:>5.1}%\n", .{
type_names[i], count[i], on_disk[i], pct(on_disk[i], file_size),
});
}
try out.print("# manifests are {d:.1}% of the store by bytes at rest (survey §2.5: the manifest-transform budget)\n\n", .{
pct(on_disk[@intFromEnum(TypeClass.manifest)], file_size),
});
}
/// Classify uncompressed artifact bytes. `artifact.parse` is the card-grammar
/// oracle: success means a structural artifact (its `kind` splits manifest from
/// other), a parse failure means a file blob. Only OOM escapes.
fn classify(gpa: std.mem.Allocator, content: []const u8) error{OutOfMemory}!TypeClass {
var m = artifact.parse(gpa, content) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return .blob, // not a structural artifact -> a file blob
};
defer m.deinit();
return if (m.kind == .manifest) .manifest else .other;
}
// ---------------------------------------------------------------------------
// 3. Compression-headroom probe over full-form (.zlib) frames.
// ---------------------------------------------------------------------------
fn reportHeadroom(
gpa: std.mem.Allocator,
store: *logstore.LogStore,
rids: []const logstore.Rid,
out: *Io.Writer,
) RunError!void {
var sampled: u64 = 0;
var uncompressed: u64 = 0;
var compressed: u64 = 0;
for (rids) |rid| {
if (sampled >= headroom_sample_cap) break;
if (store.kindOf(rid) != .zlib) continue; // full-form only; deltas are already differential
const content = (store.content(gpa, rid) catch |e| return mapContent(e)) orelse continue;
defer gpa.free(content);
uncompressed += content.len;
compressed += store.payloadLenOf(rid); // the stored §4.1 container length
sampled += 1;
}
try out.writeAll("full-form (.zlib) compression headroom\n");
if (sampled == 0) {
try out.writeAll("# no full-form frames sampled (store holds only raw/delta content)\n\n");
return;
}
try out.print("sampled {d} frames: uncompressed={d} compressed={d} ratio={d:.1}% (compressed/uncompressed)\n", .{
sampled, uncompressed, compressed, pct(compressed, uncompressed),
});
try out.writeAll("# informational (no claim): the delta-miss population a global codec / preset dictionary (survey §2.2) could target\n\n");
}
// ---------------------------------------------------------------------------
// 4. Serve CPU — time to produce the §4.1/§7.2 wire form per artifact.
// ---------------------------------------------------------------------------
fn reportServeCpu(
gpa: std.mem.Allocator,
io: Io,
store: *logstore.LogStore,
rids: []const logstore.Rid,
out: *Io.Writer,
) RunError!void {
var served: u64 = 0;
var wire_bytes: u64 = 0;
const t0 = now(io);
for (rids) |rid| {
wire_bytes += try produceWire(gpa, store, rid);
served += 1;
}
const elapsed_ns = elapsed(t0, now(io));
try out.writeAll("serve CPU (produce §4.1/§7.2 wire form)\n");
const us_each = if (served == 0) 0 else nsToUs(elapsed_ns) / @as(f64, @floatFromInt(served));
try out.print("artifacts={d} total={d:.2}ms {d:.3}us/artifact {d:.1} MB/s (wire bytes out)\n\n", .{
served, nsToMs(elapsed_ns), us_each, mbPerSec(wire_bytes, elapsed_ns),
});
}
/// Produce and free `rid`'s served wire bytes, returning their length. A stored
/// container is served verbatim via `wire()` (§4.1/§7.2 — the stored bytes ARE
/// the wire payload); a raw frame has no stored container, so the serve loop
/// compresses its content on the fly (`container.encode`, matching serve.zig).
fn produceWire(gpa: std.mem.Allocator, store: *logstore.LogStore, rid: logstore.Rid) Error!u64 {
if (store.wire(gpa, rid) catch |e| return mapContent(e)) |w| {
var wm = w;
const len = wm.container().len;
wm.deinit(gpa);
return len;
}
// Raw (or phantom): compress the reconstructed content the way serve does.
const content = (store.content(gpa, rid) catch |e| return mapContent(e)) orelse return 0;
defer gpa.free(content);
const container = codec.encode(gpa, content, .default) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.InputTooLarge => error.Corrupt,
};
defer gpa.free(container);
return container.len;
}
// ---------------------------------------------------------------------------
// Manifest-transform projection (survey §2.5) — READ-ONLY, projects only.
//
// PROJECTS the Courgette-style win without implementing the transform: replace
// every 40/64-hex artifact-name token in a check-in manifest that RESOLVES in
// the store index with a varint of its rid ordinal, keep the structural
// residue verbatim, then zlib-compress and compare against the current
// compressed manifest. Manifest cards carry hashes as lowercase hex (§4.7.1);
// the store keys frames by the raw digest, so a token is hex-decoded before
// `lookup`. A non-resolving token (or a decode miss) is left verbatim.
// ---------------------------------------------------------------------------
/// Introduces a varint ordinal in the projected stream: a resolving token
/// becomes `0x00 || uleb128(rid)`. A canonical manifest card token never
/// contains NUL (control bytes in names are escaped, §4.5), so the sentinel
/// keeps the stream unambiguously invertible against the verbatim residue.
const ordinal_sentinel: u8 = 0x00;
/// Projection measurements, summed across every manifest so the whole-store
/// figures are honest totals, not per-manifest best cases.
const ProbeStats = struct {
manifests: u64 = 0,
manifests_improved: u64 = 0, // projected zlib strictly smaller than current
hash_tokens: u64 = 0, // 40/64-hex tokens seen (resolving + non-resolving)
resolving: u64 = 0,
nonresolving: u64 = 0,
hash_bytes_unc: u64 = 0, // source bytes of resolving hex tokens (40/64 each)
ordinal_bytes_unc: u64 = 0, // their replacement bytes (sentinel + varint)
cur_unc: u64 = 0,
proj_unc: u64 = 0,
cur_zlib: u64 = 0, // full-form zlib of the current manifest bytes
proj_zlib: u64 = 0, // full-form zlib of the projected bytes
cur_ondisk: u64 = 0, // manifest frames' actual stored payload (may be delta)
};
/// Walk every artifact, project each check-in manifest, and report the summed
/// win. Read-only: `openReadOnly`, `content`, `lookup`, and zlib encode only.
fn probeManifests(
gpa: std.mem.Allocator,
io: Io,
sfile: storage.StorageFile,
file_size: u64,
label: []const u8,
out: *Io.Writer,
) RunError!void {
var store = logstore.LogStore.openReadOnly(gpa, sfile) catch |e| return mapOpen(e);
defer store.deinit(gpa);
const rids = try store.ridsInPersistedOrder(gpa);
defer gpa.free(rids);
var s = ProbeStats{};
const t0 = now(io);
for (rids) |rid| {
const content = (store.content(gpa, rid) catch |e| return mapContent(e)) orelse continue;
defer gpa.free(content);
const cls = classify(gpa, content) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
};
if (cls != .manifest) continue;
s.cur_ondisk += store.payloadLenOf(rid);
try projectManifest(gpa, &store, content, &s);
}
const elapsed_ns = elapsed(t0, now(io));
try reportProbe(out, label, s, file_size, elapsed_ns);
}
/// Build one manifest's projected bytes, compress both forms, and fold the
/// result into `s`. The projected bytes are never longer than the source (a
/// 40/64-byte token shrinks to at most 1 + 10 varint bytes), so `content.len`
/// is a valid capacity bound.
fn projectManifest(gpa: std.mem.Allocator, store: *logstore.LogStore, content: []const u8, s: *ProbeStats) Error!void {
var buf: std.ArrayList(u8) = .empty;
defer buf.deinit(gpa);
try buf.ensureTotalCapacity(gpa, content.len);
var i: usize = 0;
while (i < content.len) {
const c = content[i];
if (c == ' ' or c == '\n') {
buf.appendAssumeCapacity(c);
i += 1;
continue;
}
const start = i;
while (i < content.len and content[i] != ' ' and content[i] != '\n') i += 1;
try appendToken(gpa, store, content[start..i], &buf, s);
}
const transformed = buf.items;
const cur = codec.encode(gpa, content, .default) catch |e| return mapEncode(e);
defer gpa.free(cur);
const proj = codec.encode(gpa, transformed, .default) catch |e| return mapEncode(e);
defer gpa.free(proj);
s.manifests += 1;
s.cur_unc += content.len;
s.proj_unc += transformed.len;
s.cur_zlib += cur.len;
s.proj_zlib += proj.len;
if (proj.len < cur.len) s.manifests_improved += 1;
}
/// Append `token`'s projected form. A canonical 40/64-hex artifact name whose
/// raw digest resolves in the index becomes `sentinel || uleb128(rid)`;
/// everything else (non-hash residue, a hex name that does not resolve, a
/// decode miss) is copied verbatim.
fn appendToken(gpa: std.mem.Allocator, store: *logstore.LogStore, token: []const u8, buf: *std.ArrayList(u8), s: *ProbeStats) Error!void {
if (!artifact.validateName(token)) {
try buf.appendSlice(gpa, token);
return;
}
s.hash_tokens += 1;
var raw: [32]u8 = undefined;
const n = token.len / 2; // 20 bytes for SHA-1, 32 for SHA3-256; both <= 32
std.debug.assert(n <= raw.len);
const decoded = std.fmt.hexToBytes(raw[0..n], token) catch {
s.nonresolving += 1;
try buf.appendSlice(gpa, token);
return;
};
const rid = store.lookup(decoded) orelse {
s.nonresolving += 1;
try buf.appendSlice(gpa, token);
return;
};
s.resolving += 1;
s.hash_bytes_unc += token.len;
try buf.append(gpa, ordinal_sentinel);
s.ordinal_bytes_unc += 1 + try appendUleb128(gpa, buf, rid);
}
/// Append `value` as unsigned LEB128, returning the byte count. Bounded: a u64
/// is at most 10 groups of 7 bits.
fn appendUleb128(gpa: std.mem.Allocator, buf: *std.ArrayList(u8), value: u64) Error!usize {
var v = value;
var n: usize = 0;
while (true) {
var byte: u8 = @truncate(v & 0x7f);
v >>= 7;
if (v != 0) byte |= 0x80;
try buf.append(gpa, byte);
n += 1;
std.debug.assert(n <= 10);
if (v == 0) return n;
}
}
fn reportProbe(out: *Io.Writer, label: []const u8, s: ProbeStats, file_size: u64, elapsed_ns: u64) RunError!void {
try out.print("# storage bench: manifest-transform projection [{s}]\n\n", .{label});
if (s.manifests == 0) {
try out.writeAll("# no check-in manifests found in this store (nothing to project)\n\n");
return;
}
const cur_zlib_f: f64 = @floatFromInt(s.cur_zlib);
const saving: f64 = cur_zlib_f - @as(f64, @floatFromInt(s.proj_zlib));
const man_pct: f64 = if (s.cur_zlib == 0) 0 else saving * 100.0 / cur_zlib_f;
const store_pct: f64 = if (file_size == 0) 0 else saving * 100.0 / @as(f64, @floatFromInt(file_size));
const us_each: f64 = nsToUs(elapsed_ns) / @as(f64, @floatFromInt(s.manifests));
try out.print("manifests={d} improved={d} hash-tokens={d} (resolving={d} non-resolving={d})\n", .{
s.manifests, s.manifests_improved, s.hash_tokens, s.resolving, s.nonresolving,
});
try out.print("uncompressed: current={d} projected={d}; resolving hash bytes={d} ({d:.1}% of manifest bytes) -> ordinal bytes={d}\n", .{
s.cur_unc, s.proj_unc, s.hash_bytes_unc, pct(s.hash_bytes_unc, s.cur_unc), s.ordinal_bytes_unc,
});
try out.print("compressed (zlib full-form): current={d} projected={d} saving={d:.0} ({d:.1}% of manifest zlib)\n", .{
s.cur_zlib, s.proj_zlib, saving, man_pct,
});
try out.print("current manifest on-disk payload (as actually stored)={d}; whole store={d}\n", .{
s.cur_ondisk, file_size,
});
try out.print("whole-store reduction from the manifest transform: {d:.2}% ({d:.0} bytes / {d} store bytes)\n", .{
store_pct, saving, file_size,
});
try out.print("cost: {d:.3} us/manifest\n", .{us_each});
try out.print("# {s}: whole-store projection {d:.2}% ({s} ~10% bar)\n", .{
if (store_pct >= 10.0) "PROCEED" else "DEFER", store_pct, if (store_pct >= 10.0) ">=" else "<",
});
try out.writeAll("# read-only, full-form-baselined: the current manifest is re-zlibbed as the baseline, so if manifests are stored on-disk as deltas (on-disk payload << full-form zlib above) the realizable whole-store win is smaller than this figure. Ordinal->hash inversion reuses the store's global rid index (no per-manifest table); only the 1-byte sentinel per replaced token is charged. Assumes canonical single-space/LF card spacing preserved byte-exact.\n\n");
}
fn mapEncode(e: codec.EncodeError) Error {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.InputTooLarge => error.Corrupt,
};
}
// ---------------------------------------------------------------------------
// Synthetic corpus (pure — bytes derive from the seed alone).
// ---------------------------------------------------------------------------
/// Build a mixed store: check-in manifests (chained so many delta-encode) and
/// file blobs (some stored raw, the rest a chained delta lineage), plus one
/// config frame. Every frame kind and both artifact types appear. All
/// randomness is one seeded PRNG with a fixed draw order, so the file is
/// byte-identical for a given `(seed, count, blob, manifest_frac)`.
fn buildCorpus(gpa: std.mem.Allocator, sfile: storage.StorageFile, cfg: Config) Error!void {
var store = logstore.LogStore.open(gpa, sfile, 0) catch |e| return mapOpen(e);
defer store.deinit(gpa);
var prng = std.Random.DefaultPrng.init(cfg.seed);
const rand = prng.random();
const blob = gpa.alloc(u8, @intCast(cfg.blob)) catch return error.OutOfMemory;
defer gpa.free(blob);
const prev = gpa.alloc(u8, @intCast(cfg.blob)) catch return error.OutOfMemory;
defer gpa.free(prev);
var man_buf: [256]u8 = undefined;
var last_manifest: ?logstore.Rid = null;
var last_blob: ?logstore.Rid = null;
var have_prev_blob = false;
const n: usize = @intCast(cfg.count);
for (0..n) |i| {
const draw = rand.int(u64);
if (draw % 100 < cfg.manifest_frac) {
const bytes = try buildManifest(&man_buf, i);
const h = hashBlob(bytes);
last_manifest = store.putArtifact(&h, bytes, last_manifest) catch |e| return mapPut(e);
} else {
fillBlob(rand, blob, prev, have_prev_blob, i);
@memcpy(prev, blob);
have_prev_blob = true;
const h = hashBlob(blob);
// Every 4th blob is stored raw (populates the raw bucket, and gives
// later deltas a raw base — legal); the rest chain as zlib/delta.
if ((draw / 100) % 4 == 0) {
last_blob = store.put(&h, blob) catch |e| return mapPut(e);
} else {
last_blob = store.putArtifact(&h, blob, last_blob) catch |e| return mapPut(e);
}
}
if ((i + 1) % 64 == 0) store.commit() catch return error.Storage;
}
store.putConfig(.{
.hash_policy = 0,
.default_branch = "trunk",
.project_id = "zit-storage-bench",
.project_code = "0000000000000000",
}) catch |e| return mapPut(e);
store.commit() catch return error.Storage;
}
/// A minimal, valid §4/§5 check-in manifest (card set C,D,P,R,U,Z, matching the
/// RFC A.1.1 worked example), distinct per `index` via its comment. `R` is the
/// §6.3 aggregate of zero tracked files (md5 of the empty string); `Z` is the
/// §6.2 self-checksum, so the bytes parse and classify as `manifest`. Successive
/// indices differ only in the comment + Z line, so consecutive manifests are
/// similar enough for a profitable delta.
fn buildManifest(buf: []u8, index: u64) Error![]const u8 {
const body = std.fmt.bufPrint(buf, "C checkin-{d}\nD 2007-07-21T14:09:59\nP\nR d41d8cd98f00b204e9800998ecf8427e\nU bench\n", .{index}) catch return error.BadArgs;
var digest: [32]u8 = undefined;
_ = artifact.selfChecksum(body, &digest);
// Append "Z <32-hex>\n" after the body.
const zoff = body.len;
std.debug.assert(zoff + 35 <= buf.len);
buf[zoff] = 'Z';
buf[zoff + 1] = ' ';
@memcpy(buf[zoff + 2 ..][0..32], &digest);
buf[zoff + 34] = '\n';
return buf[0 .. zoff + 35];
}
/// A tiny word vocabulary so synthetic file blobs read like compressible
/// source text (real file blobs compress ~3-4x), making the full-form
/// compression-headroom probe representative rather than measuring random
/// noise. Fixed at comptime; no ambient data.
const vocab = [_][]const u8{
"fn ", "return ", "const ", "value ", "buffer ", "index ", "store ", "frame ",
"hash =", "payload", "= self.", "len);\n", "if (x) ", "loop {\n", "assert(", "offset ",
};
/// Fill `blob` for artifact `index`: pseudo-source text (compressible) for the
/// first blob, else a ~2% mutation of the previous blob (a delta-able chain).
/// The first 8 bytes always carry `index`, so every blob's content — and hash —
/// is distinct.
fn fillBlob(rand: std.Random, blob: []u8, prev: []const u8, have_prev: bool, index: u64) void {
std.debug.assert(blob.len >= 8);
if (!have_prev) {
var w: usize = 0;
while (w < blob.len) {
const tok = vocab[rand.uintLessThan(usize, vocab.len)];
const n = @min(tok.len, blob.len - w);
@memcpy(blob[w..][0..n], tok[0..n]);
w += n;
}
} else {
@memcpy(blob, prev);
const mutations = blob.len / 50 + 1; // ~2% of tokens rewritten
for (0..mutations) |_| {
const at = rand.uintLessThan(usize, blob.len);
const tok = vocab[rand.uintLessThan(usize, vocab.len)];
const n = @min(tok.len, blob.len - at);
@memcpy(blob[at..][0..n], tok[0..n]);
}
}
std.mem.writeInt(u64, blob[0..8], index, .little);
}
fn hashBlob(bytes: []const u8) [hash_len]u8 {
var h: [hash_len]u8 = undefined;
std.crypto.hash.sha2.Sha256.hash(bytes, &h, .{});
return h;
}
// ---------------------------------------------------------------------------
// Temp backing file (real file, reached only through injected Io).
// ---------------------------------------------------------------------------
/// A throwaway `/tmp` file, named from the monotonic clock so concurrent runs
/// never collide, unlinked on cleanup.
const Temp = struct {
file: Io.File,
path_buf: [64]u8,
path_len: usize,
fn create(io: Io) Error!Temp {
var t: Temp = undefined;
const nonce = Io.Clock.Timestamp.now(io, .awake).raw.nanoseconds;
const p = std.fmt.bufPrint(&t.path_buf, "/tmp/zit-sbench-{d}.zit", .{nonce}) catch return error.BadArgs;
t.path_len = p.len;
t.file = Io.Dir.createFileAbsolute(io, t.path_buf[0..t.path_len], .{ .read = true }) catch return error.Io;
return t;
}
fn cleanup(self: *Temp, io: Io) void {
self.file.close(io);
Io.Dir.deleteFileAbsolute(io, self.path_buf[0..self.path_len]) catch {};
}
};
// ---------------------------------------------------------------------------
// Timing, formatting, error mapping.
// ---------------------------------------------------------------------------
fn now(io: Io) Io.Timestamp {
return Io.Timestamp.now(io, .awake);
}
fn elapsed(t0: Io.Timestamp, t1: Io.Timestamp) u64 {
const ns = t0.durationTo(t1).nanoseconds; // i96, monotonic so >= 0
return if (ns < 0) 0 else @intCast(ns);
}
fn pct(part: u64, whole: u64) f64 {
if (whole == 0) return 0;
return @as(f64, @floatFromInt(part)) * 100.0 / @as(f64, @floatFromInt(whole));
}
fn mbPerSec(bytes: u64, ns: u64) f64 {
if (ns == 0 or bytes == 0) return 0;
const secs = @as(f64, @floatFromInt(ns)) / 1_000_000_000.0;
const mib = @as(f64, @floatFromInt(bytes)) / (1024.0 * 1024.0);
return mib / secs;
}
fn nsToUs(ns: u64) f64 {
return @as(f64, @floatFromInt(ns)) / 1000.0;
}
fn nsToMs(ns: u64) f64 {
return @as(f64, @floatFromInt(ns)) / 1_000_000.0;
}
fn mapOpen(e: logstore.OpenError) Error {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Storage => error.Storage,
error.Corrupt => error.Corrupt,
};
}
fn mapContent(e: logstore.ContentError) Error {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Storage => error.Storage,
error.Corrupt => error.Corrupt,
};
}
fn mapPut(e: logstore.PutError) Error {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Storage => error.Storage,
};
}
// ---------------------------------------------------------------------------
// Tests (Debug, wired into `zig build test`): a benchmark has no RFC oracle, so
// the only testable properties are the harness's own invariants — exact
// accounting, deterministic classification, and read-only measurement. No
// timing loop runs under `test`.
// ---------------------------------------------------------------------------
const testing = std.testing;
/// Build a small corpus into a tmp file and return the opened read-only handle
/// plus its size. Caller closes the file and deinits the store.
const Fixture = struct {
file: Io.File,
size: u64,
fn build(io: Io, dir: Io.Dir, cfg: Config) !Fixture {
const file = try dir.createFile(io, ".zit", .{ .read = true });
var fs = storage.FileStorage.init(io, file, 0);
try buildCorpus(testing.allocator, fs.storageFile(), cfg);
const size = try fs.storageFile().size();
return .{ .file = file, .size = size };
}
};
test "storage bench: frame-kind breakdown sums to the total store size (exact accounting)" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const fx = try Fixture.build(io, tmp.dir, .{ .count = 120, .blob = 512 });
var file = fx.file;
defer file.close(io);
var fs = storage.FileStorage.init(io, file, fx.size);
const bd = try walkFrames(fs.storageFile(), fx.size);
// The whole file is the header plus every frame span, nothing unaccounted.
try testing.expectEqual(fx.size, logstore.header_len + bd.total_on_disk());
// The corpus exercises every kind we depend on: raw, zlib/delta content,
// and exactly one config frame.
try testing.expect(bd.count[@intFromEnum(logstore.FrameKind.raw)] > 0);
try testing.expect(bd.count[@intFromEnum(logstore.FrameKind.zlib)] +
bd.count[@intFromEnum(logstore.FrameKind.delta)] > 0);
try testing.expectEqual(@as(u64, 1), bd.count[@intFromEnum(logstore.FrameKind.config)]);
// Per-kind overhead is header+padding only: on_disk == payload + overhead.
for (0..4) |k| {
try testing.expectEqual(bd.on_disk[k], bd.payload[k] + bd.overhead[k]);
}
}
test "storage bench: artifact-frame spans reconcile with the store's own per-rid view" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const fx = try Fixture.build(io, tmp.dir, .{ .count = 120, .blob = 512 });
var file = fx.file;
defer file.close(io);
var fs = storage.FileStorage.init(io, file, fx.size);
const bd = try walkFrames(fs.storageFile(), fx.size);
var fs2 = storage.FileStorage.init(io, file, fx.size);
var store = try logstore.LogStore.openReadOnly(testing.allocator, fs2.storageFile());
defer store.deinit(testing.allocator);
const rids = try store.ridsInPersistedOrder(testing.allocator);
defer testing.allocator.free(rids);
// The frame walk's non-config on-disk total must equal the sum of every
// artifact rid's span computed from the public API — the two independent
// views of the same frames agree.
var api_total: u64 = 0;
for (rids) |rid| api_total += frameSpan(@intCast(store.hashOf(rid).len), store.payloadLenOf(rid));
const walk_content = bd.on_disk[@intFromEnum(logstore.FrameKind.raw)] +
bd.on_disk[@intFromEnum(logstore.FrameKind.zlib)] +
bd.on_disk[@intFromEnum(logstore.FrameKind.delta)];
try testing.expectEqual(walk_content, api_total);
try testing.expectEqual(@as(usize, bd.count[0] + bd.count[1] + bd.count[2]), rids.len);
}
test "storage bench: classification is deterministic and splits manifests from blobs" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const fx = try Fixture.build(io, tmp.dir, .{ .count = 120, .blob = 512 });
var file = fx.file;
defer file.close(io);
var fs = storage.FileStorage.init(io, file, fx.size);
var store = try logstore.LogStore.openReadOnly(testing.allocator, fs.storageFile());
defer store.deinit(testing.allocator);
const rids = try store.ridsInPersistedOrder(testing.allocator);
defer testing.allocator.free(rids);
var manifests: u64 = 0;
var blobs: u64 = 0;
for (rids) |rid| {
const content = (try store.content(testing.allocator, rid)) orelse continue;
defer testing.allocator.free(content);
const cls = try classify(testing.allocator, content);
// Determinism: the same bytes classify identically on a repeat call.
try testing.expectEqual(cls, try classify(testing.allocator, content));
switch (cls) {
.manifest => manifests += 1,
.blob => blobs += 1,
.other => {},
}
}
// The corpus mixes both, so both buckets are non-empty.
try testing.expect(manifests > 0);
try testing.expect(blobs > 0);
}
test "storage bench: a synthetic manifest parses and classifies as a check-in" {
var buf: [256]u8 = undefined;
const bytes = try buildManifest(&buf, 7);
var m = try artifact.parse(testing.allocator, bytes);
defer m.deinit();
try testing.expectEqual(artifact.ArtifactType.manifest, m.kind);
try testing.expectEqual(TypeClass.manifest, try classify(testing.allocator, bytes));
}
test "storage bench: measuring is read-only — the store is byte-identical afterward" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const fx = try Fixture.build(io, tmp.dir, .{ .count = 120, .blob = 512 });
var file = fx.file;
defer file.close(io);
const before = try testing.allocator.alloc(u8, @intCast(fx.size));
defer testing.allocator.free(before);
try testing.expectEqual(@as(usize, @intCast(fx.size)), try file.readPositionalAll(io, before, 0));
// Run the full measurement into a discarding writer.
var sink: [512]u8 = undefined;
var dw: Io.Writer.Discarding = .init(&sink);
var fs = storage.FileStorage.init(io, file, fx.size);
try measure(testing.allocator, io, fs.storageFile(), fx.size, "test", &dw.writer);
const after = try testing.allocator.alloc(u8, @intCast(fx.size));
defer testing.allocator.free(after);
try testing.expectEqual(@as(usize, @intCast(fx.size)), try file.readPositionalAll(io, after, 0));
try testing.expectEqualSlices(u8, before, after);
}
test "storage bench: same seed reproduces a byte-identical corpus" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const cfg = Config{ .seed = 99, .count = 80, .blob = 256 };
const a = try Fixture.build(io, tmp.dir, cfg);
var fa = a.file;
defer fa.close(io);
var fb = try tmp.dir.createFile(io, ".zit-b", .{ .read = true });
defer fb.close(io);
var fs = storage.FileStorage.init(io, fb, 0);
try buildCorpus(testing.allocator, fs.storageFile(), cfg);
const b_size = try fs.storageFile().size();
try testing.expectEqual(a.size, b_size);
const ba = try testing.allocator.alloc(u8, @intCast(a.size));
defer testing.allocator.free(ba);
const bb = try testing.allocator.alloc(u8, @intCast(b_size));
defer testing.allocator.free(bb);
_ = try fa.readPositionalAll(io, ba, 0);
_ = try fb.readPositionalAll(io, bb, 0);
try testing.expectEqualSlices(u8, ba, bb);
}
test "storage bench: probing a manifest is read-only — the store is byte-identical afterward" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
const fx = try Fixture.build(io, tmp.dir, .{ .count = 120, .blob = 512 });
var file = fx.file;
defer file.close(io);
const before = try testing.allocator.alloc(u8, @intCast(fx.size));
defer testing.allocator.free(before);
try testing.expectEqual(@as(usize, @intCast(fx.size)), try file.readPositionalAll(io, before, 0));
var sink: [512]u8 = undefined;
var dw: Io.Writer.Discarding = .init(&sink);
var fs = storage.FileStorage.init(io, file, fx.size);
try probeManifests(testing.allocator, io, fs.storageFile(), fx.size, "probe", &dw.writer);
const after = try testing.allocator.alloc(u8, @intCast(fx.size));
defer testing.allocator.free(after);
try testing.expectEqual(@as(usize, @intCast(fx.size)), try file.readPositionalAll(io, after, 0));
try testing.expectEqualSlices(u8, before, after);
}
test "storage bench: a resolving hash token projects to a rid ordinal that inverts, a non-resolving one stays verbatim" {
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const io = testing.io;
var file = try tmp.dir.createFile(io, ".zit", .{ .read = true });
defer file.close(io);
var fs = storage.FileStorage.init(io, file, 0);
var store = try logstore.LogStore.open(testing.allocator, fs.storageFile(), 0);
defer store.deinit(testing.allocator);
// Store a blob; the manifest below cites it by its canonical 64-hex name.
const blob = "hello fossil\n";
var name_buf: [64]u8 = undefined;
const name = artifact.artifactName(.sha3_256, blob, &name_buf); // 64 lowercase hex
var raw: [32]u8 = undefined;
_ = try std.fmt.hexToBytes(&raw, name);
const rid = try store.put(&raw, blob);
try store.commit();
// A resolving token projects to sentinel + uleb128(rid); the raw digest
// decoded from that rid's stored hash re-hexes back to the original name.
var s = ProbeStats{};
var buf: std.ArrayList(u8) = .empty;
defer buf.deinit(testing.allocator);
try appendToken(testing.allocator, &store, name, &buf, &s);
try testing.expectEqual(@as(u64, 1), s.resolving);
try testing.expectEqual(ordinal_sentinel, buf.items[0]);
var v: u64 = 0;
var shift: u6 = 0;
var j: usize = 1;
while (true) {
const byte = buf.items[j];
v |= @as(u64, byte & 0x7f) << shift;
j += 1;
if (byte & 0x80 == 0) break;
shift += 7;
}
try testing.expectEqual(rid, v);
const stored = store.hashOf(v);
try testing.expectEqual(@as(usize, 32), stored.len);
var digest: [32]u8 = undefined;
@memcpy(&digest, stored);
const rehex = std.fmt.bytesToHex(digest, .lower);
try testing.expectEqualSlices(u8, name, rehex[0..]);
// A well-formed but unknown 64-hex name never resolves — verbatim fallback.
const bogus = [_]u8{'a'} ** 64;
var s2 = ProbeStats{};
var buf2: std.ArrayList(u8) = .empty;
defer buf2.deinit(testing.allocator);
try appendToken(testing.allocator, &store, &bogus, &buf2, &s2);
try testing.expectEqual(@as(u64, 0), s2.resolving);
try testing.expectEqual(@as(u64, 1), s2.nonresolving);
try testing.expectEqualSlices(u8, &bogus, buf2.items);
}