summaryrefslogtreecommitdiff
path: root/src/walk.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-30 00:25:19 -0300
committerGabriel Schneider <[email protected]>2026-10-30 00:53:24 -0300
commitf264dbc4a646da695331fe7401fa013cbb720b6a (patch)
treeb8d960c5034d7ebfeb44fa25fa5697abbf386a9f /src/walk.zig
parentbce88593014a4078dc9259855944f9ddbc19fe54 (diff)
downloadpardes-f264dbc4a646da695331fe7401fa013cbb720b6a.tar.gz
pardes-f264dbc4a646da695331fe7401fa013cbb720b6a.zip
the walker's digest: a blob's hash made once and folded in as a word (a 100 MB file was 5 ms a digest, two a unit, on the authority); blob fields annotated `.blob`, which the rollback copy's pins read too
walk.zig: a field named in a type's `replica.blob` (a file's text, line index and location rows, an undo snapshot's text, a register's values and joined text, the rows an edit dropped, a query's saved rows) holds immutable blobs. A digest hashes one of 4 KiB or more once, keeps the word by its address and length, and folds the length and word in; `forget` drops the word, from memory.freeRaw and freeUnfilled, through which every such blob is freed raw. Only a Debug build (the tests, the harness, replay) hashes the bytes at every digest all the same and panics where the kept word is not their hash: a blob written in place, or freed past its word. A release build, ReleaseSafe the user's own as well as ReleaseFast, takes the word and never panics on a stale one: at worst a divergence, which a replica records and then stops at (nothing resets or rejoins it yet; the notes say so). File.zig: an edit's free of the old text went to `rawFree` itself and so kept its word; the next text of the same length at the same address folded in the old one (the ReleaseFast harness diverged in 162 of 180 replica runs, in `file.content`), and it goes through freeUnfilled now. Registers.zig: `put` makes a new values array rather than writing the old one. rollback.zig: the copy pins what `.blob` names (`pinned` and `pinnedDeep` gone). Measured, ReleaseFast on the perf cores: with a 100 MB file open (PARDES_DIGEST_BENCH=100, replica.zig's bench), a unit of a key into it went from p50 10.45 ms, p99 41.6 ms to p50 24 us, p99 6.1 ms (the first, which makes the word), a digest from 5.18 ms to 10 us. The harness (20 seeds x 120 inputs x 3 clients): rollback p99 9.5 -> 2.6 ms at 30 ms (1.5 and 1.4 ms at 80 and 207), copy p99 0.27 ms; none diverged, none unequal, no delta wrong. Tests: a blob hashed once, its kept word no longer its hash once written in place, its word gone when freed. docs/next-daemon.md: the follow-up. Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'src/walk.zig')
-rw-r--r--src/walk.zig139
1 files changed, 139 insertions, 0 deletions
diff --git a/src/walk.zig b/src/walk.zig
index 5060de3d..33247d42 100644
--- a/src/walk.zig
+++ b/src/walk.zig
@@ -23,6 +23,10 @@
//! .len = .{ .{ "jumps", "njumps" } },
//! // What a field holds is made with another allocator on a load.
//! .alloc = .{ .{ "image", "image" } },
+//! // Immutable blobs: replaced whole, never written, freed raw
+//! // (memory.freeRaw, freeUnfilled). A digest hashes each once and
+//! // folds that word in; a replica's rollback copy pins them.
+//! .blob = .{ "content" },
//! };
//!
//! None of the three kinds is in a digest or a dump. A type with a `pub fn
@@ -31,6 +35,100 @@
const std = @import("std");
pub const Hasher = std.hash.Wyhash;
+const builtin = @import("builtin");
+/// Only a Debug build hashes a blob's bytes at every digest and checks its
+/// kept word; a release one, ReleaseSafe the user's own, takes the word.
+const rehash = builtin.mode == .debug;
+
+/// Whether `T.name` holds immutable blobs (`.blob`): a file's text, an undo
+/// snapshot, a register's text, a file's location rows.
+pub fn blob(comptime T: type, comptime name: []const u8) bool {
+ @setEvalBranchQuota(100_000);
+ if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "blob")) return false;
+ inline for (T.replica.blob) |n| if (comptime std.mem.eql(u8, n, name)) return true;
+ return false;
+}
+
+// ---- a blob's hash, made once ----
+//
+// A digest walks the whole core at every unit a replica is sent (and every
+// unit a replica replays): a 100 MB file was hashed in full each time. A
+// blob of `blob_min` bytes or more is hashed once instead, its word kept by
+// its address, and the digest folds the word in. The word goes when the
+// blob is freed (`forget`, from memory.freeRaw and freeUnfilled: every
+// such blob is freed raw, for the rollback copy's pins), so an address
+// used again is hashed again. A Debug build hashes the bytes all the same,
+// folds those in, and stops where a kept word is not their hash: a blob
+// written in place (which the pins forbid too), or freed past `forget`. A
+// release build never stops there: a stale word shows as a divergence.
+
+const blob_min = 4096;
+var blob_words: std.AutoHashMapUnmanaged(usize, struct { len: usize, word: u64 }) = .empty;
+var blob_lock: std.atomic.Value(bool) = .init(false);
+var blob_count: std.atomic.Value(usize) = .init(0);
+threadlocal var in_blob: bool = false;
+/// Off: every blob hashed whole at every digest, as before (the bench's).
+pub var blob_words_on = true;
+
+fn lockBlobs() void {
+ while (blob_lock.cmpxchgWeak(false, true, .acquire, .monotonic) != null) std.atomic.spinLoopHint();
+}
+
+fn unlockBlobs() void {
+ blob_lock.store(false, .release);
+}
+
+/// The blob at `addr` is freed: its word, if it has one, goes with it.
+pub fn forget(addr: usize) void {
+ if (blob_count.load(.acquire) == 0) return;
+ lockBlobs();
+ defer unlockBlobs();
+ if (blob_words.remove(addr)) blob_count.store(blob_words.count(), .release);
+}
+
+/// The word kept for the blob at `addr` (a test's).
+pub fn wordOf(addr: usize) ?u64 {
+ lockBlobs();
+ defer unlockBlobs();
+ return if (blob_words.get(addr)) |b| b.word else null;
+}
+
+/// Every word forgotten (the bench's cold digests).
+pub fn forgetAll() void {
+ lockBlobs();
+ defer unlockBlobs();
+ blob_words.clearRetainingCapacity();
+ blob_count.store(0, .release);
+}
+
+/// A blob as a digest takes it: its length and its word.
+fn hashBlob(comptime E: type, items: []const E, h: *Hasher) void {
+ const addr = @intFromPtr(items.ptr);
+ const word: u64 = word: {
+ const kept: ?u64 = if (blob_words_on) kept: {
+ lockBlobs();
+ defer unlockBlobs();
+ const b = blob_words.get(addr) orelse break :kept null;
+ break :kept if (b.len == items.len) b.word else null;
+ } else null;
+ if (!rehash) if (kept) |w| break :word w;
+ in_blob = false;
+ defer in_blob = true;
+ var one = Hasher.init(0);
+ hashSlice(E, items, &one);
+ const w = one.final();
+ if (kept) |k| if (k != w) std.debug.panic("walk: the {d}-byte blob at 0x{x} is not what its kept word was: written in place, or freed without memory.freeRaw", .{ items.len, addr });
+ if (blob_words_on and kept == null) {
+ lockBlobs();
+ defer unlockBlobs();
+ blob_words.put(std.heap.page_allocator, addr, .{ .len = items.len, .word = w }) catch {};
+ blob_count.store(blob_words.count(), .release);
+ }
+ break :word w;
+ };
+ h.update(std.mem.asBytes(&items.len));
+ h.update(std.mem.asBytes(&word));
+}
pub fn digest(comptime T: type, v: *const T) u64 {
var h = Hasher.init(0);
@@ -46,6 +144,9 @@ pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 {
inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| {
if (attr.@"comptime" or comptime excluded(T, name)) continue;
var h = Hasher.init(0);
+ const was = in_blob;
+ in_blob = comptime blob(T, name);
+ defer in_blob = was;
if (comptime lengthOf(T, name)) |len| {
hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h);
} else hash(F, &@field(v, name), &h);
@@ -180,6 +281,9 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void {
inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| {
if (attr.@"comptime" or comptime excluded(T, name)) continue;
if (comptime opaqueTo(F)) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is " ++ @typeName(F) ++ ", which no walk sees into: say what it is (`replica`)");
+ const was = in_blob;
+ in_blob = comptime blob(T, name);
+ defer in_blob = was;
if (comptime lengthOf(T, name)) |len| {
hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h);
} else hash(F, &@field(v, name), h);
@@ -214,6 +318,7 @@ fn hashInt(comptime I: type, n: I, h: *Hasher) void {
}
fn hashSlice(comptime E: type, items: []const E, h: *Hasher) void {
+ if (in_blob and items.len * @sizeOf(E) >= blob_min) return hashBlob(E, items, h);
h.update(std.mem.asBytes(&items.len));
if (comptime flat(E)) return h.update(std.mem.sliceAsBytes(items));
for (items) |*e| hash(E, e, h);
@@ -1584,3 +1689,37 @@ test "a dump that is not one, or is cut short, is refused" {
// What it made before the end is freed again.
try std.testing.expectError(error.EndOfDump, load(S, gpa, bytes[0 .. bytes.len - 2], null));
}
+
+test "a blob is hashed once and folded in as a word; one written in place is not its word, which a Debug build checks; a freed one's word goes" {
+ const memory = @import("memory.zig");
+ const digestOfBlob = struct {
+ fn of(items: []const u8) u64 {
+ var h = Hasher.init(0);
+ hashSlice(u8, items, &h);
+ return h.final();
+ }
+ }.of;
+ const gpa = std.testing.allocator;
+ const File = struct {
+ pub const replica = .{ .blob = .{"content"} };
+ content: []u8,
+ cursor: u32 = 0,
+ };
+ const text = try gpa.alloc(u8, 64 << 10);
+ @memset(text, 'a');
+ var f: File = .{ .content = text };
+ const before = digest(File, &f);
+ try std.testing.expect(wordOf(@intFromPtr(text.ptr)) != null);
+ // The same word again: nothing it holds moved.
+ try std.testing.expectEqual(before, digest(File, &f));
+ // Written in place, which a blob never is: its kept word is no longer
+ // its hash, which a Debug build's digest checks (and panics at) where a
+ // release build's would fold the old word in.
+ text[1000] = 'b';
+ try std.testing.expect(wordOf(@intFromPtr(text.ptr)).? != digestOfBlob(text));
+ text[1000] = 'a';
+ try std.testing.expectEqual(digestOfBlob(text), wordOf(@intFromPtr(text.ptr)).?);
+ // Freed, its word goes: an address used again is hashed again.
+ memory.freeUnfilled(gpa, text);
+ try std.testing.expect(wordOf(@intFromPtr(text.ptr)) == null);
+}