diff options
Diffstat (limited to 'src/walk.zig')
| -rw-r--r-- | src/walk.zig | 172 |
1 files changed, 34 insertions, 138 deletions
diff --git a/src/walk.zig b/src/walk.zig index 8360a8b6..dc743a4d 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -39,12 +39,9 @@ const xitdb = @import("xitdb"); 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. +/// Whether `T.name` holds blobs (`.blob`): a file's text, an undo entry's +/// bytes, 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; @@ -52,135 +49,39 @@ pub fn blob(comptime T: type, comptime name: []const u8) bool { return false; } -// ---- a blob's hash, made once ---- +// ---- a blob in a digest: its length ---- // // 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: 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. +// unit a replica replays): a 100 MB file was hashed in full each time, then +// once and kept as a word by its address while texts were never written in +// place. A blob of `blob_min` bytes or more is digested as its length now, +// never its bytes: a file's text says what it holds by its revision +// (File.State.revision, in the digest), and the other blobs are replaced +// whole, never written. A smaller one is hashed as any slice is. 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(); -} - -/// 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 blob_lock.store(false, .release); - 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 blob_lock.store(false, .release); - 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 blob_lock.store(false, .release); - blob_words.clearRetainingCapacity(); - blob_count.store(0, .release); -} - -/// A blob as a digest takes it: its length and its word. +/// A blob as a digest takes it: its length. 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 blob_lock.store(false, .release); - const b = blob_words.get(addr) orelse break :kept null; - break :kept if (b.len == items.len) b.word else null; - } else null; - // The lists are the C heap's (a replica client's, a session's join), - // which a build with no libc has neither of. - if (comptime builtin.link_libc) if (blobs_out) |list| { - list.append(std.heap.c_allocator, std.mem.sliceAsBytes(items)) catch {}; - break :word 0; - }; - if (!rehash) if (kept) |w| break :word w; - if (comptime builtin.link_libc) if (E == u8) if (unhashed_out) |list| if (kept == null) { - list.append(std.heap.c_allocator, items) catch {}; - break :word 0; - }; - 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 blob_lock.store(false, .release); - blob_words.put(std.heap.page_allocator, addr, .{ .len = items.len, .word = w }) catch {}; - blob_count.store(blob_words.count(), .release); - } - break :word w; - }; + // The list is the C heap's (a replica client's), which a build with no + // libc has none of. + if (comptime builtin.link_libc) if (blobs_out) |list| list.append(std.heap.c_allocator, std.mem.sliceAsBytes(items)) catch {}; h.update(std.mem.asBytes(&items.len)); - h.update(std.mem.asBytes(&word)); } -/// Where `unhashed` notes the texts a digest would hash for want of a word. -threadlocal var unhashed_out: ?*std.ArrayListUnmanaged([]const u8) = null; -/// Where `blobs` notes every blob, hashing none. +/// Where `blobs` notes every blob. threadlocal var blobs_out: ?*std.ArrayListUnmanaged([]const u8) = null; -/// Every blob of `v` a digest would take as one (`blob_min` bytes and up), -/// as its bytes, onto `out` (the C heap's), hashed by none: a replica -/// client's, which knows its blobs by content (src/replica.zig `Have`). +/// Every blob of `v` a digest takes as one (`blob_min` bytes and up), as +/// its bytes, onto `out` (the C heap's): a replica client's, which knows +/// its blobs by content (src/replica.zig `Have`). pub fn blobs(comptime T: type, v: *const T, out: *std.ArrayListUnmanaged([]const u8)) void { blobs_out = out; defer blobs_out = null; _ = digest(T, v); } -/// The blob texts a digest of `v` would hash now, having no word yet, onto -/// `out` (the C heap's): a walk with no blob hashed, which `makeWords` then -/// makes on another thread. A replica's join (src/replica.zig) does that -/// first: the session's step never hashes a text it never digested before. -pub fn unhashed(comptime T: type, v: *const T, out: *std.ArrayListUnmanaged([]const u8)) void { - unhashed_out = out; - defer unhashed_out = null; - _ = digest(T, v); -} - -/// The words of `texts` (`unhashed`'s), made on any thread: they must stay -/// as they are meanwhile (pinned, memory.zig), and the next digest takes -/// them. -pub fn makeWords(texts: []const []const u8) void { - for (texts) |items| { - // As hashBlob makes it (hashSlice's length, then the bytes). - var one = Hasher.init(0); - one.update(std.mem.asBytes(&items.len)); - one.update(items); - const w = one.final(); - lockBlobs(); - defer blob_lock.store(false, .release); - const got = blob_words.getOrPut(std.heap.page_allocator, @intFromPtr(items.ptr)) catch continue; - if (!got.found_existing) got.value_ptr.* = .{ .len = items.len, .word = w }; - blob_count.store(blob_words.count(), .release); - } -} - pub fn digest(comptime T: type, v: *const T) u64 { var h = Hasher.init(0); hash(T, v, &h); @@ -2636,36 +2537,31 @@ test "a dump that is not one, or is cut short, is refused" { 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; +test "a blob of 4 KiB and up is digested by its length, what it holds told by its keeper's revision; a smaller one by its bytes" { const gpa = std.testing.allocator; const File = struct { pub const replica = .{ .blob = .{"content"} }; content: []u8, - cursor: u32 = 0, + revision: u32 = 0, }; const text = try gpa.alloc(u8, 64 << 10); + defer gpa.free(text); @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. + // Written in place: the same digest, until its revision says so. 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.freeRaw(gpa, text); - try std.testing.expect(wordOf(@intFromPtr(text.ptr)) == null); + try std.testing.expectEqual(before, digest(File, &f)); + f.revision += 1; + try std.testing.expect(digest(File, &f) != before); + // Another length is another digest. + f.revision = 0; + f.content = text[0 .. text.len - 1]; + try std.testing.expect(digest(File, &f) != before); + // A small one by its bytes. + var small = "abc".*; + f.content = &small; + const was = digest(File, &f); + small[1] = 'x'; + try std.testing.expect(digest(File, &f) != was); } |
