summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/File.zig5
-rw-r--r--src/memory.zig5
-rw-r--r--src/replica.zig73
-rw-r--r--src/walk.zig172
-rw-r--r--src/wire.zig5
5 files changed, 45 insertions, 215 deletions
diff --git a/src/File.zig b/src/File.zig
index 8e5c0101..05d02673 100644
--- a/src/File.zig
+++ b/src/File.zig
@@ -961,7 +961,7 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who
undo_gone = f.history.journal.swap(p.gpa, old, old_len, new_len);
} else {
// Raw: `free` overwrites a safe build's freed memory, a whole
- // file's worth; and its digest word goes (src/walk.zig).
+ // file's worth.
pardes.memory.freeRaw(p.gpa, old);
}
} else {
@@ -972,8 +972,6 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who
@memcpy(buffer[off..][0..bytes.len], bytes);
f.content = buffer[0..new_len];
f.cap = buffer.len;
- // Written in place: a word a digest kept for it is no longer its.
- pardes.walk.forget(@intFromPtr(buffer.ptr));
}
f.revision +%= 1;
f.splice = .{ .revision = f.revision, .head = span.head, .tail = span.tail, .old_len = old_len };
@@ -1034,7 +1032,6 @@ fn grow(gpa: std.mem.Allocator, f: *State, n: usize) !void {
if (n <= room.len) return;
const want = n + @max(n / 8, 4096);
if (room.len > 0) if (gpa.remap(room, want)) |grown| {
- pardes.walk.forget(@intFromPtr(room.ptr));
f.content = grown[0..f.content.len];
f.cap = grown.len;
return;
diff --git a/src/memory.zig b/src/memory.zig
index 676793c2..e3fa4ac9 100644
--- a/src/memory.zig
+++ b/src/memory.zig
@@ -1,6 +1,5 @@
const std = @import("std");
const builtin = @import("builtin");
-const walk = @import("walk.zig");
const config = @import("pardes_config");
const KiB = 1024;
@@ -351,8 +350,6 @@ pub fn freeRaw(allocator: Allocator, items: anytype) void {
const E = @typeInfo(@TypeOf(items)).pointer.child;
const bytes = std.mem.sliceAsBytes(items);
if (bytes.len == 0) return;
- // A blob's digest word goes with it (walk.zig).
- walk.forget(@intFromPtr(bytes.ptr));
if (pinned(allocator, bytes, .of(E))) return;
allocator.rawFree(@constCast(bytes), .of(E), @returnAddress());
}
@@ -403,8 +400,6 @@ pub fn unpin(bytes: []const u8) void {
}
pins_lock.store(false, .release);
if (due) |f| {
- // A word made for it while it was pinned (walk.makeWords) goes too.
- walk.forget(addr);
f.allocator.rawFree(@constCast(f.bytes), f.alignment, @returnAddress());
}
}
diff --git a/src/replica.zig b/src/replica.zig
index f58a4b27..71528fc4 100644
--- a/src/replica.zig
+++ b/src/replica.zig
@@ -947,9 +947,6 @@ pub const Replica = struct {
c.update(in.event);
c.step();
p.terminal = r.t.screen_state and (keyboard or r.t.touched);
- // No digest is taken here: a blob born under the copy and digested
- // keeps its word past the epoch's free of it (src/walk.zig), and a
- // later blob at that address read as it.
const clean = tape.endSpeculation(&r.t);
const dt = nowNs() - t0;
// Where a blob was written, should one be: the input that did.
@@ -1455,7 +1452,7 @@ pub const Peer = struct {
/// state, then the blobs it says it lacks; what follows the join goes
/// in a cheaper frame. The hashing is this thread's, never the step's.
/// ponytail: a blob is hashed again at every far join, 3.6 GB/s; a
- /// session's join after its first would keep them, beside its words.
+ /// session's join after its first could keep them.
fn farJoin(peer: *Peer) bool {
const gpa = peer.peers.gpa;
peer.z = zstd.compressor(6, 23) orelse return false;
@@ -1736,14 +1733,8 @@ pub const Peers = struct {
/// it records: what each was sent.
screens: Screens = undefined,
msgs: std.ArrayListUnmanaged([]u8) = .empty,
- /// Clients waiting to join while the session's texts are hashed
- /// (`joins`), the texts and the thread hashing them.
- held: std.ArrayListUnmanaged(Joining) = .empty,
- texts: std.ArrayListUnmanaged([]const u8) = .empty,
- hasher: ?std.Thread = null,
- rounds: u8 = 0,
- pub const Note = union(enum) { join: Joining, input: Msg, screen: Msg, gone: *Peer, check: *Peer, joined: *Peer, hashed };
+ pub const Note = union(enum) { join: Joining, input: Msg, screen: Msg, gone: *Peer, check: *Peer, joined: *Peer };
/// A connection to join, and the view it joins again for, if it does.
pub const Joining = daemon.Joining;
pub const Msg = struct { peer: *Peer, msg: []u8 };
@@ -1761,7 +1752,7 @@ pub const Peers = struct {
switch (note) {
.join => |j| _ = libc.close(j.fd),
.input, .screen => |in| ps.gpa.free(in.msg),
- .gone, .check, .joined, .hashed => {},
+ .gone, .check, .joined => {},
}
return;
};
@@ -1812,17 +1803,7 @@ pub const Peers = struct {
ps.mail.store(false, .release);
ps.lock.unlock(ps.io);
for (ps.taken.items) |note| switch (note) {
- .join => |j| {
- ps.held.append(ps.gpa, j) catch {
- daemon.refuseReplica(j.fd, "out of memory");
- continue;
- };
- ps.joins(core);
- },
- .hashed => {
- ps.unhashedDone();
- ps.joins(core);
- },
+ .join => |j| ps.join(core, j),
.input => |in| {
ps.input(core, in.peer, in.msg);
ps.gpa.free(in.msg);
@@ -1885,42 +1866,6 @@ pub const Peers = struct {
}
}
- /// The clients waiting to join, joined, once the texts the session
- /// never digested have their words (`walk.unhashed`): those are hashed
- /// on a thread of their own, pinned meanwhile, and the joins wait a
- /// boundary or two for them, the session's step never. A second round
- /// joins whatever is left.
- fn joins(ps: *Peers, core: *Pardes) void {
- if (ps.hasher != null or ps.held.items.len == 0) return;
- if (ps.rounds < 2) {
- walk.unhashed(Pardes, core, &ps.texts);
- if (ps.texts.items.len > 0) {
- for (ps.texts.items) |b| pardes.memory.pin(b);
- if (std.Thread.spawn(.{}, hashTexts, .{ps})) |t| {
- ps.hasher = t;
- ps.rounds += 1;
- return;
- } else |_| ps.unhashedDone();
- }
- }
- ps.rounds = 0;
- for (ps.held.items) |j| ps.join(core, j);
- ps.held.clearRetainingCapacity();
- }
-
- fn hashTexts(ps: *Peers) void {
- walk.makeWords(ps.texts.items);
- ps.post(.hashed);
- }
-
- /// The hashing thread joined, its texts unpinned.
- fn unhashedDone(ps: *Peers) void {
- if (ps.hasher) |t| t.join();
- ps.hasher = null;
- for (ps.texts.items) |b| pardes.memory.unpin(b);
- ps.texts.clearRetainingCapacity();
- }
-
fn join(ps: *Peers, core: *Pardes, joining: Joining) void {
const fd = joining.fd;
const t0 = nowNs();
@@ -2064,7 +2009,7 @@ pub const Peers = struct {
const mine = switch (ps.inbox.items[i]) {
.input, .screen => |in| in.peer == peer,
.gone, .check, .joined => |p| p == peer,
- .join, .hashed => false,
+ .join => false,
};
if (!mine) {
i += 1;
@@ -2145,10 +2090,6 @@ pub const Peers = struct {
/// ...each view kept for its client if `again` (an Upgrade's).
fn drop(ps: *Peers, core: *Pardes, again: bool) void {
- ps.unhashedDone();
- for (ps.held.items) |j| _ = libc.close(j.fd);
- ps.held.clearRetainingCapacity();
- ps.rounds = 0;
for (&ps.list) |*slot| if (slot.*) |peer| {
slot.* = null;
core.undrawn &= ~(@as(u8, 1) << @intCast(peer.view));
@@ -2161,7 +2102,7 @@ pub const Peers = struct {
for (ps.inbox.items) |note| switch (note) {
.join => |j| _ = libc.close(j.fd),
.input, .screen => |in| ps.gpa.free(in.msg),
- .gone, .check, .joined, .hashed => {},
+ .gone, .check, .joined => {},
};
ps.inbox.clearRetainingCapacity();
ps.lock.unlock(ps.io);
@@ -2175,8 +2116,6 @@ pub const Peers = struct {
ps.input_ns.deinit(ps.gpa);
ps.boundary_ns.deinit(ps.gpa);
ps.msgs.deinit(ps.gpa);
- ps.held.deinit(ps.gpa);
- ps.texts.deinit(std.heap.c_allocator);
ps.each_join.deinit(ps.gpa);
}
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);
}
diff --git a/src/wire.zig b/src/wire.zig
index 3406321b..735fc37f 100644
--- a/src/wire.zig
+++ b/src/wire.zig
@@ -9,6 +9,9 @@ const builtin = @import("builtin");
const pardes = @import("pardes.zig");
const config = @import("pardes_config");
+/// 20: a digest takes a blob of 4 KiB and up (a file's text, a register's,
+/// an undo entry's bytes) by its length, not its bytes (src/walk.zig): a
+/// text's revision says what it holds;
/// 19: a client joining again names the view it had in its hello, and a
/// bye says whether it joins again for it (views.away);
/// 18: a replica's input is stamped with its guess of the session's
@@ -24,7 +27,7 @@ const config = @import("pardes_config");
/// part B); 14: the hello names a session and
/// carries the semantics hash, and a ping is answered (phase 5's
/// groundwork); 13: the frames went (phase 3).
-pub const version: u16 = 19;
+pub const version: u16 = 20;
/// The terminal's build and the window's step alike (`semantics`).
const family = switch (config.platform) {