summaryrefslogtreecommitdiff
path: root/src/walk.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/walk.zig')
-rw-r--r--src/walk.zig172
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);
}