From 6b89fed454fd56a3af4b576646538b45d3315146 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 12:32:23 -0300 Subject: FreeBSD: the tty pardes builds for it and runs there, terminals, 9P and the daemon included Cross-compiled with -Dtarget=x86_64-freebsd.15.0 (15 ships libutil.so.10; Zig's default 14.0 links .so.9) and run on the FreeBSD 15.1 box: - 9p_io serves there: fstatat, not Linux's statx. madvise is Linux's. - WINCH reaches the sigwait thread through a handler that does nothing: FreeBSD drops a signal ignored by default as it is sent. - A dead terminal answers a write with ENXIO, which std does not expect: a Debug build traced it to stderr, that same terminal, and recursed until the stack ran out (a session whose ssh dropped hung). No tracing there. - waitid's FreeBSD numbers and 64-bit id: a command pane's exit is seen. - No /proc: a shell's directory and program by sysctl, ttyTaken by the foreground group, the foreground job's name by its program. - File watching by FreeBSD 15's inotify. - ghostty's kitty loader: off Linux a stat comes before a t=f open (a FIFO hung it); FreeBSD's shm_open refuses O_NONBLOCK. - vaxis's test terminal has no read off Linux: no input thread for it. - test-install: the test-build programs installed into /test, to run where the build cannot. Co-Authored-By: Claude Opus 5.5 --- src/memory.zig | 1 + 1 file changed, 1 insertion(+) (limited to 'src/memory.zig') diff --git a/src/memory.zig b/src/memory.zig index cb75ee0e..47bd755d 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -442,6 +442,7 @@ pub fn trim() void { /// 71 MiB that way. Only the region given, never the whole process (a prctl /// would reach every shell and server pardes starts). pub fn sparse(region: []u8) void { + if (comptime builtin.os.tag != .linux) return; advise(region, std.posix.MADV.NOHUGEPAGE); } -- cgit v1.3 From 3b57a72becd6dd6700d996c9c5c000e1cb53e076 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 18:19:13 -0300 Subject: phase 5 part A: the speculation and rollback engine, in one process: a walker copy put back where it was, replicas that apply their own input at once and take the authority's tape as the truth, and a harness of typists over delayed links src/rollback.zig: the replica core's allocator (`Epoch`) knows every allocation, and while a copy is held puts off frees of what was there before and refuses to grow it in place, so what the core held stays where it was. The copy (`Copy`) is the digest's walk saving the bytes of every allocation it reaches, field by field (the derived caches and this process's own too: a safe build's free writes over what it frees, and the frame arena points at what the epoch then frees), but the queues a step drains and the frame statistics; a file's text, its line index and its undo snapshots are pinned instead (made anew at each edit, never written; now freed raw everywhere), checked unchanged in a safe build. Put back, each allocation's bytes go back over it, the epoch's allocations are freed and its put-off frees forgotten; let go, they are made. Tree-sitter's trees, the C heap's, are held the same way (syntax.held_trees). src/replica.zig: an `Authority` records its core's every input to a tape in memory and hands each client's input back as a unit (origin, sequence number, its tape); a `Replica` applies its own input at once, as the authority will (update, then pump), recorded by its own tape (tape.zig's speculation mode), and for each unit in order drops its pending head when the authority recorded the same (inputs, host calls and answers: the fast path), else puts the copy back, replays the units since and this one (every digest checked) and applies its pending inputs again. A host call or a syscall stops a speculation: it is answered harmlessly, undone when it returns, and the input waits for the authority's answer; a clock or environment read is a guess the comparison checks; an emulator is the authority's (terminal.zig's writers stop a speculation; a safe build asserts none changed). The view's events (a resize, the pointer) wait. Messages are bytes: no transport yet. Each client has a view of its own (src/views.zig): the authority goes into it before the client's input (`toView`, taped), the replica's speculation the same, and the copy walks the views not live too (`parked`, each pane's `pv`). test/replicas.zig (`zig build replicas`): one authority and N replicas, a view each (`--shared` puts them in one), each client typing monkey.zig's mix at 50-200 ms over its own link (half the RTT plus 10% jitter, in order), the authority's pty echoing 2 ms later; gates: no replica diverges, every replica's digest is the authority's at quiescence; reported per RTT: inputs applied at once, stopped, waiting, fast paths, rollbacks (mispredicted, foreign), and what a speculative apply, a copy and a rollback cost. 3 clients x 100 inputs at 30, 80 and 207 ms: no divergence over 12 Debug seeds and 20 ReleaseFast ones with a filled heap; ReleaseFast p99 a speculative apply under 0.2 ms, a rollback under 1.6 ms. `zig build rollback-bench` times the real copy now (take, release, an edit, restore). What the replicas found, fixed: a release build reads what the heap had where Debug's fill made two cores agree: `col_panes` and `restore_buf` digested undefined (zeroed now), `terminal.State.reply_dropped` never set at create, `Text.sels` and `PendingPipe.ranges` digested past their length (a walker `len` cuts a slice too). PARDES_REPLICA_FILL fills a replica's allocations to show what is left. Co-Authored-By: Claude Opus 5.5 --- build.zig | 10 + src/File.zig | 14 +- src/Pipe.zig | 2 + src/Text.zig | 6 +- src/memory.zig | 9 + src/pardes.zig | 11 +- src/replica.zig | 578 ++++++++++++++++++++++++++++++++++++++++++++++++ src/rollback.zig | 496 +++++++++++++++++++++++++++++++++++++++++ src/syntax.zig | 24 ++ src/tape.zig | 236 ++++++++++++++++++-- src/terminal.zig | 17 ++ src/walk.zig | 24 +- test/replicas.zig | 327 +++++++++++++++++++++++++++ test/rollback_bench.zig | 120 ++++------ 14 files changed, 1763 insertions(+), 111 deletions(-) create mode 100644 src/replica.zig create mode 100644 src/rollback.zig create mode 100644 test/replicas.zig (limited to 'src/memory.zig') diff --git a/build.zig b/build.zig index 13cb8ebc..1a5dd200 100644 --- a/build.zig +++ b/build.zig @@ -1504,6 +1504,16 @@ pub fn build(b: *std.Build) void { run_rollback_bench.has_side_effects = true; b.step("rollback-bench", "a replica's rollback copy (walked state, pinned blobs, walk time) for a typical and a big session, and a fork of the big one (-Doptimize=ReleaseFast)").dependOn(&run_rollback_bench.step); + const replicas = b.addExecutable(.{ + .name = "pardes-replicas", + .root_module = b.createModule(.{ .target = target, .optimize = optimize, .root_source_file = b.path("test/replicas.zig"), .link_libc = true }), + }); + replicas.root_module.addImport("pardes", core_module); + const run_replicas = b.addRunArtifact(replicas); + run_replicas.addPassthruArgs(); + run_replicas.has_side_effects = true; + b.step("replicas", "one authority and several replicas in process, each client typing over a delayed link: digests at quiescence, rollback rate and costs per RTT (-- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207])").dependOn(&run_replicas.step); + const locations_bench_step = b.step("locations-bench", "measure cold/warm result formatting (-Doptimize=ReleaseFast; CSV on stderr)"); if (optimize != .fast) { locations_bench_step.dependOn(&b.addFail("locations-bench requires -Doptimize=ReleaseFast").step); diff --git a/src/File.zig b/src/File.zig index dd6b2d34..84222191 100644 --- a/src/File.zig +++ b/src/File.zig @@ -1159,10 +1159,12 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { if (p.panes[id].?.file.?.line_starts.ptr == file.line_starts.ptr) break true; } else false; p.gpa.free(file.path); - if (ntwins == 0) p.gpa.free(file.content); + // Raw, as every text is freed (a replica's rollback copy pins them, + // src/rollback.zig, and a safe build's free writes over what it frees). + if (ntwins == 0) pardes.memory.freeUnfilled(p.gpa, file.content); if (file.listing) |listing| p.gpa.free(listing.names); if (file.mini) |*mini| mini.deinit(p.gpa); - if (file.line_starts.len > 0 and !index_shared) p.gpa.free(file.line_starts); + if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, file.line_starts); if (file.highlights.len > 0) p.tree_sitter_gpa.free(file.highlights); p.gpa.free(file.pager_spans); locations.freeRows(p.gpa, file.location_rows); @@ -1264,7 +1266,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { }; // The clock the session that recorded read (src/tape.zig). f.mtime = pardes.tape.value(.mtime, pardes.ctlfs.events.now, .{}); - if (f.line_starts.len > 0) p.gpa.free(f.line_starts); + if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); f.line_starts = starts; if (f.highlights.len > 0) p.tree_sitter_gpa.free(f.highlights); f.highlights = &.{}; @@ -1276,7 +1278,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { const tf = &t.file.?; // Its own index, built while the shared one was empty, goes; the // shared one, freed above, is replaced. - if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) p.gpa.free(tf.line_starts); + if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, tf.line_starts); tf.content = f.content; tf.line_starts = f.line_starts; tf.revision = f.revision; @@ -1498,8 +1500,8 @@ pub fn relink(p: *Pardes, of: usize, id: usize, dot: ?[2]u32) void { sf.twin = p.next_twin; p.next_twin +%= 1; } - p.gpa.free(f.content); - if (f.line_starts.len > 0) p.gpa.free(f.line_starts); + pardes.memory.freeUnfilled(p.gpa, f.content); + if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); f.history.destroy(p.gpa); f.content = sf.content; f.line_starts = sf.line_starts; diff --git a/src/Pipe.zig b/src/Pipe.zig index 850f9c64..239a94e4 100644 --- a/src/Pipe.zig +++ b/src/Pipe.zig @@ -52,6 +52,8 @@ pub fn pipeMarker(how: modal.Normal.PipeBehavior) []const u8 { } pub const PendingPipe = struct { + /// The digest's walk (src/walk.zig) of the ranges, as far as they go. + pub const replica = .{ .len = .{.{ "ranges", "nranges" }} }; id: u32, pane: usize, serial: u32, diff --git a/src/Text.zig b/src/Text.zig index 3f107542..da4be590 100644 --- a/src/Text.zig +++ b/src/Text.zig @@ -49,9 +49,9 @@ pub const SelRange = struct { sticky: i32 = -1, }; -/// The replay digest's walk (src/walk.zig) of the histories: as far as -/// they go. -pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" } } }; +/// The replay digest's walk (src/walk.zig) of the histories and the ranges: +/// as far as they go (the ranges' room is made whole and used `nsel` deep). +pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" }, .{ "sels", "nsel" } } }; what: What = .body, /// The characters of a text that holds its own (gpa-owned): everything but diff --git a/src/memory.zig b/src/memory.zig index 47bd755d..1d082964 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -421,6 +421,15 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); } +/// `freeUnfilled` for a slice of any element: a text's line index, made +/// anew at every edit too (and pinned by a replica's rollback copy, +/// src/rollback.zig, which a safe build's overwrite would spoil). +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) allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); +} + /// Gives free memory back to the system, the arenas' and libc's, inside its /// heap too: after a big result is formatted or a big pane torn down, the /// tree-sitter arena kept 73 MiB of emptied buckets resident and glibc what diff --git a/src/pardes.zig b/src/pardes.zig index 75e91ee9..5d889c86 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -65,6 +65,8 @@ pub const tape = @import("tape.zig"); pub const walk = @import("walk.zig"); pub const screen_state = if (terminal_panes) @import("screen_state.zig") else struct {}; pub const views = @import("views.zig"); +pub const rollback = @import("rollback.zig"); +pub const replica = @import("replica.zig"); pub const image = @import("image.zig"); pub const dump = @import("dump.zig"); pub const lsp = @import("lsp/lsp.zig"); @@ -474,6 +476,8 @@ pub const Loc = struct { }; test { + _ = @import("rollback.zig"); + _ = @import("replica.zig"); _ = @import("modal.zig"); _ = @import("tagline.zig"); _ = @import("hunks.zig"); @@ -4412,7 +4416,10 @@ pub const Pardes = struct { // layout: columns own x by weight; panes own y by vweight within a column. ncol: usize = 0, col_weight: [MAX_COLS]u64 = @splat(column_weight_unit), - col_panes: [MAX_COLS][MAX_PANES]usize = undefined, + // Zeroed, not undefined: a digest takes the whole of it, a release + // build's heap leaves its unused slots whatever was there before, and + // two replicas must agree on them (src/replica.zig). + col_panes: [MAX_COLS][MAX_PANES]usize = @splat(@splat(0)), col_n: [MAX_COLS]usize = @splat(0), /// Each column's tag and the workspace's: Texts like a pane's tag, with /// no prefix, showing a default until someone edits them. @@ -4698,7 +4705,7 @@ pub const Pardes = struct { /// a Restore builtin wants this dump loaded into the live session; the /// shell consumes it via takeRestore each frame (restore contents stay host-fed) restore_req: ?[]const u8 = null, - restore_buf: [1024]u8 = undefined, + restore_buf: [1024]u8 = @splat(0), surface: Surface = .{}, /// The view the fields above are of: whose layout, focus, pointer and diff --git a/src/replica.zig b/src/replica.zig new file mode 100644 index 00000000..42d94503 --- /dev/null +++ b/src/replica.zig @@ -0,0 +1,578 @@ +//! A session's replicas (docs/next-daemon.md, phase 5 part A): the authority +//! orders every input and records what its core consumed (src/tape.zig); +//! each replica runs a core of its own, applies its own inputs at once, and +//! takes the authority's stream as the truth. +//! +//! A replica's state is the confirmed position plus its own pending inputs, +//! applied on top (a speculation, recorded as the authority would record +//! it). For each unit of the authority's stream, in order: +//! - its own pending head, recorded the same (inputs, host calls and +//! answers): the head goes, nothing is redone (the fast path); +//! - else the rollback copy is put back (src/rollback.zig), the confirmed +//! units since it are replayed, then this one, and the pending inputs +//! are applied again. +//! A speculation that reaches a host call or a syscall (a Host function, +//! a `tape.site`) or an emulator (the authority's) stops: the copy is put +//! back and the input waits for the authority's answer, one RTT late but +//! never wrong. Clock and environment reads (`tape.value`) are made here, +//! and the comparison catches a guess the authority did not share. +//! +//! No transport: messages are bytes in and out. A client's input is its +//! id, a sequence number and the event as detached/wire.zig frames it; a +//! unit is the input's origin (0 for the authority's own: a pty's output, a +//! tick), its sequence number and the authority's tape of it. +const std = @import("std"); +const builtin = @import("builtin"); +const pardes = @import("pardes.zig"); +const tape = @import("tape.zig"); +const rollback = @import("rollback.zig"); +const walk = @import("walk.zig"); +const wire = @import("detached/wire.zig"); +const Allocator = std.mem.Allocator; +const Pardes = pardes.Pardes; + +const checked = builtin.mode == .debug or builtin.mode == .safe; +const head_len = 6; // origin or client: u16le, seq: u32le +/// Confirmed units fast-pathed under one copy before it is taken afresh: +/// a rollback replays them all. +const rebase_after = 32; + +fn header(buf: []u8, who: u16, seq: u32) void { + std.mem.writeInt(u16, buf[0..2], who, .little); + std.mem.writeInt(u32, buf[2..6], seq, .little); +} + +pub const Unit = struct { origin: u16, seq: u32, tape: []const u8 }; + +pub fn parseUnit(msg: []const u8) ?Unit { + if (msg.len < head_len) return null; + return .{ .origin = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .tape = msg[head_len..] }; +} + +pub const Input = struct { client: u16, seq: u32, event: pardes.Event }; + +/// A client's input message; its event borrows `msg`. +pub fn parseInput(msg: []const u8) ?Input { + if (msg.len < head_len) return null; + const f = (wire.framed(msg[head_len..]) catch return null) orelse return null; + const ev = switch (wire.decodeClient(f.tag, f.payload) catch return null) { + .event => |ev| ev, + else => return null, + }; + return .{ .client = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .event = ev }; +} + +/// The core whose tape is `t`, stepped: tape.on is process-wide, and so +/// are syntax.zig's held trees, so one process can step several. +const Stepping = struct { + tape: ?*tape.Tape, + trees: ?*pardes.syntax.HeldTrees, + + fn begin(t: *tape.Tape, epoch: ?*rollback.Epoch) Stepping { + const was: Stepping = .{ .tape = tape.on, .trees = pardes.syntax.held_trees }; + tape.on = t; + rollback.Epoch.select(epoch); + return was; + } + + fn end(was: Stepping) void { + tape.on = was.tape; + pardes.syntax.held_trees = was.trees; + } +}; + +fn nowNs() u64 { + return pardes.FrameStats.nowNs(); +} + +// ---- the authority ---- + +pub const Authority = struct { + gpa: Allocator, + t: tape.Tape, + core: *Pardes, + host: pardes.Host, + out: std.ArrayListUnmanaged(u8) = .empty, + seq: u32 = 0, + /// Each client's view (src/views.zig): its own layout, focus and + /// cursors over the session's text. The first client has the session's. + view_of: [64]u8 = @splat(0), + + /// A session booted with `opts`; `unit` is its first, which a replica + /// is made from. + pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host) !*Authority { + // A replay gives its core every allocator (tape.zig), and a digest + // tells an allocator from none. + var opts = options; + opts.image_allocator = opts.image_allocator orelse gpa; + opts.pdf_allocator = opts.pdf_allocator orelse gpa; + opts.tree_sitter_allocator = opts.tree_sitter_allocator orelse gpa; + opts.frame_allocator = opts.frame_allocator orelse gpa; + const a = try gpa.create(Authority); + errdefer gpa.destroy(a); + a.* = .{ .gpa = gpa, .t = tape.memory(gpa), .core = undefined, .host = host }; + const was = Stepping.begin(&a.t, null); + defer was.end(); + a.core = try Pardes.init(gpa, opts); + a.core.host = host; + a.core.pump(host) catch {}; + return a; + } + + pub fn deinit(a: *Authority) void { + const was = Stepping.begin(&a.t, null); + a.core.deinit(); + was.end(); + tape.release(&a.t); + a.out.deinit(a.gpa); + a.gpa.destroy(a); + } + + /// What was recorded since the last unit, as one (the boot's, a setup's + /// done straight on the core). + pub fn unit(a: *Authority, origin: u16, seq: u32) ![]const u8 { + a.out.clearRetainingCapacity(); + try a.out.appendNTimes(a.gpa, 0, head_len); + header(a.out.items, origin, seq); + try a.out.appendSlice(a.gpa, tape.taken(&a.t)); + tape.clearTaken(&a.t); + return a.out.items; + } + + /// An input of the authority's own (a pty's output, a tick, a setup's + /// command), recorded into the unit being made. + pub fn apply(a: *Authority, ev: pardes.Event) void { + const was = Stepping.begin(&a.t, null); + a.core.update(ev); + a.core.pump(a.host) catch {}; + was.end(); + } + + /// One of the authority's own inputs, as its unit. + pub fn local(a: *Authority, ev: pardes.Event) ![]const u8 { + a.apply(ev); + a.seq += 1; + return a.unit(0, a.seq); + } + + /// A view of its own for `client`, as its unit; which it is. + pub fn openView(a: *Authority, client: u16) !struct { view: u8, unit: []const u8 } { + const was = Stepping.begin(&a.t, null); + const k = a.core.openView() orelse { + was.end(); + return error.TooManyViews; + }; + a.core.pump(a.host) catch {}; + was.end(); + a.view_of[client] = k; + a.seq += 1; + return .{ .view = k, .unit = try a.unit(0, a.seq) }; + } + + /// One client's input, applied in the order it came, in its view: the + /// unit every replica takes. + pub fn take(a: *Authority, msg: []const u8) ![]const u8 { + const in = parseInput(msg) orelse return error.BadInput; + const was = Stepping.begin(&a.t, null); + a.core.toView(a.view_of[in.client]); + a.core.update(in.event); + a.core.pump(a.host) catch {}; + was.end(); + return a.unit(in.client, in.seq); + } +}; + +// ---- a replica ---- + +pub const Stats = struct { + inputs: u32 = 0, + /// Applied at once and clean. + speculated: u32 = 0, + /// Stopped at a host call, a syscall or an emulator: waits one RTT. + stopped: u32 = 0, + /// Not tried: an event of the view's (a resize, the pointer), phase 4's. + unspeculated: u32 = 0, + /// The authority's unit was the pending head, recorded the same. + fast: u32 = 0, + /// The copy put back: the head recorded otherwise (a guess of the clock + /// the authority did not share), or another's unit first. + mispredicted: u32 = 0, + foreign: u32 = 0, + rebases: u32 = 0, + units: u32 = 0, + /// Nanoseconds: one speculative apply, a copy taken, a rollback (the + /// copy put back, the confirmed units replayed, the pending reapplied). + spec_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_ns: std.ArrayListUnmanaged(u64) = .empty, + rollback_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_bytes: u64 = 0, + copies: u32 = 0, + + pub fn deinit(s: *Stats, gpa: Allocator) void { + s.spec_ns.deinit(gpa); + s.copy_ns.deinit(gpa); + s.rollback_ns.deinit(gpa); + } +}; + +const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null }; + +pub const Replica = struct { + gpa: Allocator, + id: u16, + /// Its own view of the session (Authority.openView's). + view: u8 = 0, + /// The core's allocator; its tapes and the engine's own lists are not. + epoch: rollback.Epoch = .{}, + t: tape.Tape, + copy: rollback.Copy = .{}, + pending: std.ArrayListUnmanaged(Pending) = .empty, + /// pending[0..applied] are applied on top of the confirmed position. + applied: usize = 0, + /// The pending input that waits for the authority (it stopped at a host + /// call, or is the view's), and those after it with it. + blocked: ?u32 = null, + /// Confirmed units fast-pathed since the copy was taken. + since: std.ArrayListUnmanaged([]u8) = .empty, + /// Pending inputs to apply again (after a rollback). + dirty: bool = false, + next_seq: u32 = 1, + stats: Stats = .{}, + diverged: ?[]const u8 = null, + out: std.ArrayListUnmanaged(u8) = .empty, + /// Nanoseconds of the rollback being made, until its reapply. + recovering: ?u64 = null, + + /// A replica of the session whose first unit is `first`. + pub fn init(gpa: Allocator, id: u16, first: []const u8) !*Replica { + const r = try gpa.create(Replica); + r.* = .{ .gpa = gpa, .id = id, .t = tape.memory(gpa) }; + r.t.core_gpa = r.epoch.allocator(); + r.confirm(first); + if (r.t.core == null) { + r.deinit(); + return error.NoCore; + } + return r; + } + + pub fn deinit(r: *Replica) void { + if (r.t.core) |c| { + const was = Stepping.begin(&r.t, &r.epoch); + if (r.copy.held) r.copy.restore(); + c.deinit(); + was.end(); + } + r.copy.deinit(); + for (r.pending.items) |p| r.freePending(p); + r.pending.deinit(r.gpa); + for (r.since.items) |u| r.gpa.free(u); + r.since.deinit(r.gpa); + r.out.deinit(r.gpa); + r.stats.deinit(r.gpa); + tape.release(&r.t); + if (r.diverged) |why| r.gpa.free(why); + r.epoch.deinit(); + r.gpa.destroy(r); + } + + pub fn core(r: *const Replica) *Pardes { + return r.t.core.?; + } + + fn freePending(r: *Replica, p: Pending) void { + r.gpa.free(p.msg); + if (p.spec) |s| r.gpa.free(s); + } + + /// The replica's own input: applied at once when it can be, and the + /// message for the authority returned (valid until the next call). + pub fn input(r: *Replica, ev: pardes.Event) ![]const u8 { + r.stats.inputs += 1; + const seq = r.next_seq; + r.next_seq += 1; + const room = try r.gpa.alloc(u8, head_len + wire.clientBound(.{ .event = ev })); + defer r.gpa.free(room); + const n = (try wire.encodeClient(room[head_len..], .{ .event = ev })).len; + header(room, r.id, seq); + const msg = try r.gpa.dupe(u8, room[0 .. head_len + n]); + try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg }); + r.dirty = true; + r.settle(); + r.out.clearRetainingCapacity(); + try r.out.appendSlice(r.gpa, msg); + return r.out.items; + } + + /// One unit of the authority's stream, in its order. + pub fn confirm(r: *Replica, msg: []const u8) void { + if (r.diverged != null) return; + const u = parseUnit(msg) orelse return r.fail("a unit too short to read"); + r.stats.units += 1; + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and + tape.sameRecords(r.pending.items[0].spec.?, u.tape)) + { + r.stats.fast += 1; + r.freePending(r.pending.orderedRemove(0)); + r.applied -= 1; + if (r.applied == 0) { + // Nothing speculative on top any more: the state is the + // confirmed one. + r.copy.release(); + rollback.Epoch.select(null); + r.clearSince(); + return; + } + const kept = r.gpa.dupe(u8, u.tape) catch return r.fail("out of memory"); + r.since.append(r.gpa, kept) catch return r.fail("out of memory"); + if (r.since.items.len >= rebase_after) { + r.stats.rebases += 1; + r.toConfirmed(); + r.dirty = true; + } + return; + } + if (r.applied > 0) { + if (u.origin == r.id) r.stats.mispredicted += 1 else r.stats.foreign += 1; + if (u.origin == r.id and std.c.getenv("PARDES_REPLICA_TRACE") != null) { + var w: std.Io.Writer.Allocating = .init(r.gpa); + defer w.deinit(); + w.writer.print("replica {d}: its input {d} was recorded otherwise; it guessed:\n", .{ r.id, u.seq }) catch {}; + tape.describe(r.pending.items[0].spec.?, &w.writer); + w.writer.print("and the authority recorded:\n", .{}) catch {}; + tape.describe(u.tape, &w.writer); + std.debug.print("{s}", .{w.written()}); + } + r.recovering = nowNs(); + r.toConfirmed(); + } + if (tape.replayUnit(&r.t, u.tape)) |why| { + if (std.c.getenv("PARDES_REPLICA_TRACE") != null) { + var w: std.Io.Writer.Allocating = .init(r.gpa); + defer w.deinit(); + w.writer.print("replica {d}: the unit of {d}/{d} diverged: {s}\n", .{ r.id, u.origin, u.seq, why }) catch {}; + tape.describe(u.tape, &w.writer); + std.debug.print("{s}", .{w.written()}); + } + return r.fail(why); + } + if (u.origin == r.id) { + if (r.pending.items.len == 0 or r.pending.items[0].seq != u.seq) return r.fail("the authority confirmed an input this replica did not send next"); + if (r.blocked == u.seq) r.blocked = null; + r.freePending(r.pending.orderedRemove(0)); + } + r.dirty = true; + } + + fn fail(r: *Replica, why: []const u8) void { + if (r.diverged == null) r.diverged = r.gpa.dupe(u8, why) catch return; + } + + fn clearSince(r: *Replica) void { + for (r.since.items) |u| r.gpa.free(u); + r.since.clearRetainingCapacity(); + } + + /// Back to the confirmed position: the copy put back, the units fast- + /// pathed since replayed. + fn toConfirmed(r: *Replica) void { + if (r.copy.held) { + r.copy.restore(); + rollback.Epoch.select(null); + } + r.applied = 0; + for (r.since.items) |u| if (tape.replayUnit(&r.t, u)) |why| return r.fail(why); + r.clearSince(); + for (r.pending.items) |*p| if (p.spec) |s| { + r.gpa.free(s); + p.spec = null; + }; + } + + /// The pending inputs applied again, as far as they go. + pub fn settle(r: *Replica) void { + if (!r.dirty or r.diverged != null) return; + r.dirty = false; + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + while (r.applied < r.pending.items.len and r.blocked != r.pending.items[r.applied].seq) if (!r.speculate()) break; + if (r.recovering) |t0| { + r.stats.rollback_ns.append(r.gpa, nowNs() - t0) catch {}; + r.recovering = null; + } + } + + /// pending[applied] applied on top: whether it was. + fn speculate(r: *Replica) bool { + const p = &r.pending.items[r.applied]; + const in = parseInput(p.msg) orelse return false; + switch (in.event) { + .key, .paste, .command => {}, + else => { + // The view's (a resize, the pointer): the authority's for + // now, phase 4's views to come. + r.stats.unspeculated += 1; + r.blocked = p.seq; + return false; + }, + } + const c = r.core(); + if (!r.copy.held) { + const t0 = nowNs(); + r.copy.take(&r.epoch, c) catch return false; + rollback.Epoch.select(&r.epoch); + r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {}; + r.stats.copy_bytes += r.copy.savedBytes(); + r.stats.copies += 1; + } + var terminals: [pardes.MAX_PANES]u64 = undefined; + if (checked) terminalDigests(c, &terminals); + const t0 = nowNs(); + tape.beginSpeculation(&r.t); + c.toView(r.view); + c.update(in.event); + c.pump(c.host) catch {}; + const clean = tape.endSpeculation(&r.t); + const dt = nowNs() - t0; + // Where a blob was written, should one be: the input that did. + if (checked and std.c.getenv("PARDES_REPLICA_TRACE") != null) r.copy.check(); + if (!clean) { + // Undone, and the earlier ones applied again on the confirmed + // position: this one waits for the authority. + r.stats.stopped += 1; + r.blocked = p.seq; + const upto = r.applied; + r.toConfirmed(); + while (r.applied < upto) if (!r.speculate()) break; + if (r.applied == 0 and r.copy.held) { + r.copy.release(); + rollback.Epoch.select(null); + } + return false; + } + if (checked) { + var after: [pardes.MAX_PANES]u64 = undefined; + terminalDigests(c, &after); + if (!std.mem.eql(u64, &terminals, &after)) @panic("replica: a speculation wrote a terminal's emulator"); + } + r.stats.speculated += 1; + r.stats.spec_ns.append(r.gpa, dt) catch {}; + p.spec = r.gpa.dupe(u8, tape.taken(&r.t)) catch return false; + tape.clearTaken(&r.t); + r.applied += 1; + return true; + } + + /// Nothing pending and nothing applied: the replica is the authority's + /// confirmed state, which `digest` says. + pub fn quiet(r: *const Replica) bool { + return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held; + } + + pub fn digest(r: *Replica) u64 { + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + return tape.digestOf(r.core()); + } +}; + +fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void { + for (p.panes, out) |slot, *d| { + d.* = 0; + const pane = slot orelse continue; + const state = pane.terminal orelse continue; + var h = walk.Hasher.init(0); + state.digest(&h); + d.* = h.final(); + } +} + +pub fn digestOf(a: *Authority) u64 { + const was = Stepping.begin(&a.t, null); + defer was.end(); + return tape.digestOf(a.core); +} + +const TestHost = struct { + fn watched(_: ?*anyopaque) bool { + return false; + } + const vtable: pardes.Host.VTable = .{ .watched = watched }; + fn host() pardes.Host { + return .{ .vtable = &vtable }; + } +}; + +fn key(r: *Replica, cp: u21, sent: *std.ArrayListUnmanaged([]u8)) !void { + const text = [_]u8{@intCast(cp & 0x7f)}; + const msg = try r.input(.{ .key = .{ .cp = cp, .text = if (cp < 0x80 and cp >= 0x20) &text else "" } }); + try sent.append(std.testing.allocator, try std.testing.allocator.dupe(u8, msg)); +} + +test "a replica's own keys apply at once, confirm on the fast path, and end at the authority's digest" { + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host()); + defer a.deinit(); + const r = try Replica.init(gpa, 1, try a.unit(0, 0)); + defer r.deinit(); + try std.testing.expectEqual(digestOf(a), r.digest()); + var sent: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (sent.items) |m| gpa.free(m); + sent.deinit(gpa); + } + for ("oabc") |k| try key(r, k, &sent); + try key(r, pardes.Key.escape, &sent); + try std.testing.expectEqual(@as(usize, 5), r.applied); + for (sent.items) |m| { + r.confirm(try a.take(m)); + r.settle(); + } + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null); + try std.testing.expectEqual(@as(u32, 5), r.stats.fast); + try std.testing.expect(r.quiet()); + try std.testing.expectEqual(digestOf(a), r.digest()); +} + +test "another client's input first: a replica rolls back, replays it and applies its own again" { + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host()); + defer a.deinit(); + const first = try gpa.dupe(u8, try a.unit(0, 0)); + defer gpa.free(first); + const r1 = try Replica.init(gpa, 1, first); + defer r1.deinit(); + const r2 = try Replica.init(gpa, 2, first); + defer r2.deinit(); + var s1: std.ArrayListUnmanaged([]u8) = .empty; + var s2: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (s1.items) |m| gpa.free(m); + for (s2.items) |m| gpa.free(m); + s1.deinit(gpa); + s2.deinit(gpa); + } + for ("oone") |k| try key(r1, k, &s1); + for ("Otwo") |k| try key(r2, k, &s2); + // The authority hears r2 first, then r1; both hear the units in that + // order. + for ([_]*std.ArrayListUnmanaged([]u8){ &s2, &s1 }) |list| for (list.items) |m| { + const u = try gpa.dupe(u8, try a.take(m)); + defer gpa.free(u); + r1.confirm(u); + r1.settle(); + r2.confirm(u); + r2.settle(); + }; + for ([_]*Replica{ r1, r2 }) |r| { + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null); + try std.testing.expect(r.quiet()); + try std.testing.expectEqual(digestOf(a), r.digest()); + } + try std.testing.expect(r1.stats.foreign >= 1); + try std.testing.expectEqual(@as(u32, 4), r2.stats.fast); +} diff --git a/src/rollback.zig b/src/rollback.zig new file mode 100644 index 00000000..9137b6f6 --- /dev/null +++ b/src/rollback.zig @@ -0,0 +1,496 @@ +//! A replica's rollback copy (docs/next-daemon.md, phase 5): the state a +//! speculation can write, saved before it writes, and put back where it was +//! when the authority's order differs. +//! +//! Two halves: +//! - `Epoch`, the replica core's allocator. It knows every allocation, and +//! while a copy is held it frees nothing that was there before (a free +//! is put off) and grows nothing of then in place. What is allocated +//! meanwhile is the epoch's. So whatever the core held when the copy was +//! taken is still where it was when the copy is put back. +//! - `Copy`, the walker's walk of the core's state (src/walk.zig: what a +//! digest covers, so views, buffers, registers, counters and terminal +//! metadata), saving the bytes of every allocation it reaches, the core +//! struct's own included. A file's text, its line index and its undo +//! snapshots are pinned instead: an edit puts a new buffer in their +//! place (File.setContentSpan) and never writes one, so the copy keeps +//! a reference and the put-off free keeps it alive. +//! +//! Putting the copy back writes each saved allocation's bytes over it, so +//! every pointer in them points where it did, at what was there; then the +//! epoch's allocations are freed and its put-off frees forgotten. Letting +//! the copy go (the speculation was right) makes the put-off frees. +//! +//! ponytail: an allocation reached only through a field the walk leaves +//! out (a derived cache's own heap, say) is not saved; that cache is the +//! epoch's as it was written, which is right for one remade from the text +//! it was made of and wrong for one changed in place. The replica harness +//! (test/replicas.zig) checks a digest at every confirmed step. +const std = @import("std"); +const builtin = @import("builtin"); +const pardes = @import("pardes.zig"); +const walk = @import("walk.zig"); +const Allocator = std.mem.Allocator; +const Alignment = std.mem.Alignment; +const Pardes = pardes.Pardes; + +/// Blobs this long or longer (`pinned`) are pinned, not copied. Checked +/// unchanged in a safe build when the copy goes. +const blob_min = 4096; +const checked = builtin.mode == .debug or builtin.mode == .safe; + +pub const Epoch = struct { + child: Allocator = std.heap.c_allocator, + /// Its own bookkeeping, never the epoch's. + meta: Allocator = std.heap.c_allocator, + live: std.AutoHashMapUnmanaged(usize, Entry) = .empty, + on: bool = false, + id: u32 = 0, + born: std.ArrayListUnmanaged(usize) = .empty, + deferred: std.ArrayListUnmanaged(usize) = .empty, + trees: pardes.syntax.HeldTrees = .{ .meta = std.heap.c_allocator }, + + const Entry = struct { len: usize, alignment: Alignment, epoch: u32, freed: bool = false }; + + pub fn allocator(e: *Epoch) Allocator { + return .{ .ptr = e, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } }; + } + + pub fn deinit(e: *Epoch) void { + var it = e.live.iterator(); + while (it.next()) |kv| e.child.rawFree(@as([*]u8, @ptrFromInt(kv.key_ptr.*))[0..kv.value_ptr.len], kv.value_ptr.alignment, @returnAddress()); + e.live.deinit(e.meta); + e.born.deinit(e.meta); + e.deferred.deinit(e.meta); + e.trees.born.deinit(e.meta); + e.trees.freed.deinit(e.meta); + } + + fn mine(e: *const Epoch, entry: Entry) bool { + return e.on and entry.epoch == e.id; + } + + /// The live allocation that starts at `addr`. + pub fn owns(e: *const Epoch, addr: usize) ?Entry { + const entry = e.live.get(addr) orelse return null; + return if (entry.freed) null else entry; + } + + fn note(e: *Epoch, addr: usize, len: usize, alignment: Alignment) bool { + e.live.put(e.meta, addr, .{ .len = len, .alignment = alignment, .epoch = if (e.on) e.id else 0 }) catch return false; + if (e.on) e.born.append(e.meta, addr) catch {}; + return true; + } + + /// Every new allocation filled with this: a core reading memory it never + /// wrote shows as a replica's divergence (test/replicas.zig, a release + /// build's heap is otherwise whatever it was). + pub var fill: ?u8 = null; + + fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const ptr = e.child.rawAlloc(len, alignment, ra) orelse return null; + if (fill) |b| @memset(ptr[0..len], b); + if (!e.note(@intFromPtr(ptr), len, alignment)) { + e.child.rawFree(ptr[0..len], alignment, ra); + return null; + } + return ptr; + } + + fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const entry = e.live.getPtr(@intFromPtr(memory.ptr)) orelse return false; + // What the copy saved stays its size: the core moves instead. + if (e.on and !e.mine(entry.*)) return false; + if (!e.child.rawResize(memory, alignment, new_len, ra)) return false; + entry.len = new_len; + return true; + } + + fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const old = @intFromPtr(memory.ptr); + const entry = e.live.get(old) orelse return null; + if (e.on and !e.mine(entry)) return null; + const ptr = e.child.rawRemap(memory, alignment, new_len, ra) orelse return null; + _ = e.live.remove(old); + e.live.put(e.meta, @intFromPtr(ptr), .{ .len = new_len, .alignment = alignment, .epoch = entry.epoch }) catch {}; + if (e.mine(entry) and @intFromPtr(ptr) != old) e.born.append(e.meta, @intFromPtr(ptr)) catch {}; + return ptr; + } + + fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const addr = @intFromPtr(memory.ptr); + const entry = e.live.getPtr(addr) orelse return e.child.rawFree(memory, alignment, ra); + if (e.on and !e.mine(entry.*)) { + // Held by the copy until it is put back or let go. + if (!entry.freed) e.deferred.append(e.meta, addr) catch {}; + entry.freed = true; + return; + } + e.child.rawFree(memory.ptr[0..entry.len], entry.alignment, ra); + _ = e.live.remove(addr); + } + + fn reallyFree(e: *Epoch, addr: usize) void { + const entry = e.live.get(addr) orelse return; + e.child.rawFree(@as([*]u8, @ptrFromInt(addr))[0..entry.len], entry.alignment, @returnAddress()); + _ = e.live.remove(addr); + } + + fn begin(e: *Epoch) void { + std.debug.assert(!e.on); + e.id +%= 1; + if (e.id == 0) e.id = 1; + e.on = true; + e.born.clearRetainingCapacity(); + e.deferred.clearRetainingCapacity(); + e.trees.born.clearRetainingCapacity(); + e.trees.freed.clearRetainingCapacity(); + pardes.syntax.held_trees = &e.trees; + } + + /// The copy put back: what the epoch made goes, what it freed stays. + fn discard(e: *Epoch) void { + for (e.born.items) |addr| if (e.live.get(addr)) |entry| if (e.mine(entry)) e.reallyFree(addr); + for (e.deferred.items) |addr| if (e.live.getPtr(addr)) |entry| { + entry.freed = false; + }; + for (e.trees.born.items) |t| pardes.syntax.destroyTree(t); + e.end(); + } + + /// The copy let go: what the epoch freed goes now. + fn keep(e: *Epoch) void { + for (e.deferred.items) |addr| e.reallyFree(addr); + for (e.trees.freed.items) |t| pardes.syntax.destroyTree(t); + e.end(); + } + + fn end(e: *Epoch) void { + e.on = false; + e.born.clearRetainingCapacity(); + e.deferred.clearRetainingCapacity(); + e.trees.born.clearRetainingCapacity(); + e.trees.freed.clearRetainingCapacity(); + if (pardes.syntax.held_trees == &e.trees) pardes.syntax.held_trees = null; + } + + /// The trees of whichever core is stepped next: one in-process harness + /// steps several (syntax.held_trees is process-wide). + pub fn select(e: ?*Epoch) void { + pardes.syntax.held_trees = if (e) |x| (if (x.on) &x.trees else null) else null; + } +}; + +pub const Copy = struct { + meta: Allocator = std.heap.c_allocator, + regions: std.ArrayListUnmanaged(Region) = .empty, + bytes: std.ArrayListUnmanaged(u8) = .empty, + seen: std.AutoHashMapUnmanaged(Seen, void) = .empty, + pins: std.ArrayListUnmanaged(Pin) = .empty, + held: bool = false, + epoch: ?*Epoch = null, + /// The field being walked, for a pin's report, and whether it is one + /// of the blobs: a file's text or an undo snapshot's. + where: []const u8 = "", + pinnable: bool = false, + + const Region = struct { addr: usize, off: usize, len: usize }; + const Pin = struct { addr: usize, len: usize, hash: u64, where: []const u8 }; + const Seen = struct { addr: usize, ty: usize }; + pub const Error = Allocator.Error; + + pub fn deinit(c: *Copy) void { + c.regions.deinit(c.meta); + c.bytes.deinit(c.meta); + c.seen.deinit(c.meta); + c.pins.deinit(c.meta); + } + + pub fn savedBytes(c: *const Copy) usize { + return c.bytes.items.len; + } + + pub fn pinnedBytes(c: *const Copy) usize { + var n: usize = 0; + for (c.pins.items) |pin| n += pin.len; + return n; + } + + /// The copy of `p`, whose allocator is `e`'s, taken: from now on what + /// it held stays where it is until the copy is put back or let go. + pub fn take(c: *Copy, e: *Epoch, p: *const Pardes) Error!void { + std.debug.assert(!c.held); + c.regions.clearRetainingCapacity(); + c.bytes.clearRetainingCapacity(); + c.seen.clearRetainingCapacity(); + c.pins.clearRetainingCapacity(); + c.epoch = e; + // A step drains these before it ends: between steps they hold + // nothing, and a copy is taken between steps. + std.debug.assert(p.effects_len == 0 and p.in_len == 0); + if (c.epoch.?.owns(@intFromPtr(p)) == null) @panic("rollback: the core is not its epoch's"); + try c.object(Pardes, p); + e.begin(); + c.held = true; + } + + /// The core as it was when the copy was taken. + pub fn restore(c: *Copy) void { + std.debug.assert(c.held); + c.check(); + for (c.regions.items) |r| @memcpy(@as([*]u8, @ptrFromInt(r.addr))[0..r.len], c.bytes.items[r.off..][0..r.len]); + c.epoch.?.discard(); + c.held = false; + } + + /// The speculation was right: the copy is not wanted. + pub fn release(c: *Copy) void { + std.debug.assert(c.held); + c.check(); + c.epoch.?.keep(); + c.held = false; + } + + pub fn check(c: *const Copy) void { + if (comptime !checked) return; + for (c.pins.items) |pin| if (std.hash.Wyhash.hash(0, @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]) != pin.hash) { + const now = @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]; + const entry = c.epoch.?.live.get(pin.addr); + std.debug.print("rollback: {s}, {d} bytes at {x}, pinned, was written in place: now {any}; entry {any}, epoch {d}\n", .{ pin.where, pin.len, pin.addr, now[0..32], entry, c.epoch.?.id }); + @panic("rollback: a pinned blob was written in place"); + }; + } + + fn save(c: *Copy, addr: usize, len: usize) Error!void { + if (len == 0) return; + const off = c.bytes.items.len; + try c.bytes.appendSlice(c.meta, @as([*]const u8, @ptrFromInt(addr))[0..len]); + try c.regions.append(c.meta, .{ .addr = addr, .off = off, .len = len }); + } + + /// Whether the value at `addr` of type `T` was reached before. + fn reached(c: *Copy, comptime T: type, addr: usize) Error!bool { + const key: Seen = .{ .addr = addr, .ty = @intFromPtr(@typeName(T).ptr) }; + const got = try c.seen.getOrPut(c.meta, key); + return got.found_existing; + } + + /// The allocation at `addr`, saved once, whatever reaches it. + fn allocation(c: *Copy, addr: usize) Error!?usize { + const entry = c.epoch.?.owns(addr) orelse return null; + if (try c.reached(void, addr)) return entry.len; + try c.save(addr, entry.len); + return entry.len; + } + + fn visit(c: *Copy, comptime T: type, v: *const T) Error!void { + if (comptime !heapIn(T, 0)) return; + switch (@typeInfo(T)) { + .optional => |o| if (v.*) |*payload| try c.visit(o.child, payload), + .array => |a| if (comptime heapIn(a.child, 0)) for (v) |*e| try c.visit(a.child, e), + .pointer => |p| switch (p.size) { + .one => try c.object(p.child, v.*), + .slice => try c.slice(p.child, v.*), + // No length to walk by: its keeper's (a C handle's buffer). + else => {}, + }, + .@"struct" => |s| { + if (comptime walk.machinery(T)) return; + // A terminal: the authority's (its emulator is never written + // by a speculation: terminal.zig's guards). + if (comptime @hasDecl(T, "digest") and @TypeOf(T.digest) == fn (*const T, *walk.Hasher) void) return; + if (s.layout == .@"packed") return; + if (comptime @hasField(T, "items") and @hasField(T, "capacity") and s.field_names.len == 2) { + if (v.capacity == 0) return; + _ = try c.allocation(@intFromPtr(v.items.ptr)); + const E = @typeInfo(@FieldType(T, "items")).pointer.child; + if (comptime heapIn(E, 0)) for (v.items) |*e| try c.visit(E, e); + return; + } + if (comptime @hasDecl(T, "KV") and @hasDecl(T, "Hash") and @hasField(T, "metadata")) { + const m = v.metadata orelse return; + // std's header sits before the metadata, at the start + // of the one allocation. + const header = std.mem.alignForward(usize, 2 * @sizeOf(usize) + @sizeOf(u32), @alignOf(usize)); + _ = try c.allocation(@intFromPtr(m) - header); + var it = v.iterator(); + while (it.next()) |entry| { + try c.visit(@TypeOf(entry.key_ptr.*), entry.key_ptr); + try c.visit(@TypeOf(entry.value_ptr.*), entry.value_ptr); + } + return; + } + if (comptime @hasField(T, "raw") and s.field_names.len == 1 and @hasDecl(T, "load")) return; + if (comptime @hasField(T, "any_future")) return; + if (comptime @hasField(T, "bit_length") and @hasField(T, "masks") and s.field_names.len == 2) { + if (v.bit_length == 0) return; + _ = try c.allocation(@intFromPtr(v.masks) - @sizeOf(@typeInfo(@FieldType(T, "masks")).pointer.child)); + return; + } + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + // What a digest covers, the caches made from it and this + // process's own (the views not live are among it): a + // safe build's free writes over what it frees, so what + // the speculation freed would come back as that. Not the + // queues a step drains (undefined between steps), nor the + // authority's. + if (attr.@"comptime" or comptime (annotated(T, "authority", name) or (annotated(T, "local", name) and unsaved(name)))) continue; + if (comptime opaqueTo(F)) continue; + c.where = @typeName(T) ++ "." ++ name; + c.pinnable = comptime pinned(T, name); + if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { + const len = comptime walk.lengthOf(T, name).?; + if (comptime heapIn(@typeInfo(F).array.child, 0)) for (@field(v, name)[0..walk.lengthIn(v, len)]) |*e| try c.visit(@typeInfo(F).array.child, e); + } else try c.visit(F, &@field(v, name)); + } + }, + .@"union" => switch (v.*) { + inline else => |*payload| try c.visit(@TypeOf(payload.*), payload), + }, + .error_union => |e| if (v.*) |*payload| try c.visit(e.payload, payload) else |_| {}, + else => {}, + } + } + + fn object(c: *Copy, comptime P: type, ptr: *const P) Error!void { + if (comptime walk.machinery(P)) return; + const addr = @intFromPtr(ptr); + if (try c.reached(P, addr)) return; + if (comptime @hasDecl(P, "digest") and @TypeOf(P.digest) == fn (*const P, *walk.Hasher) void) return; + if (c.epoch.?.owns(addr) != null) { + _ = try c.reached(void, addr); + try c.fields(P, ptr); + } + try c.visit(P, ptr); + } + + /// A struct's bytes, field by field where it says what its fields are: + /// all of them (this process's own too, which the epoch's frees would + /// leave pointing at nothing), but the queues a step drains and the + /// frame statistics (numbers, megabytes of them), and an array only as + /// far as its length says. + fn fields(c: *Copy, comptime T: type, v: *const T) Error!void { + if (comptime @typeInfo(T) != .@"struct" or !@hasDecl(T, "replica")) return c.save(@intFromPtr(v), @sizeOf(T)); + const s = @typeInfo(T).@"struct"; + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime") continue; + if (comptime annotated(T, "local", name) and unsaved(name)) continue; + const at = @intFromPtr(&@field(v, name)); + if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { + try c.save(at, walk.lengthIn(v, comptime walk.lengthOf(T, name).?) * @sizeOf(@typeInfo(F).array.child)); + } else if (comptime annotatedStruct(F)) { + try c.fields(F, &@field(v, name)); + } else if (comptime @typeInfo(F) == .array and annotatedStruct(@typeInfo(F).array.child)) { + for (&@field(v, name)) |*e| try c.fields(@typeInfo(F).array.child, e); + } else try c.save(at, @sizeOf(F)); + } + } + + fn slice(c: *Copy, comptime E: type, s: []const E) Error!void { + if (s.len == 0) return; + const addr = @intFromPtr(s.ptr); + if (try c.reached([]const E, addr)) return; + if (comptime !heapIn(E, 0)) if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { + const bytes = std.mem.sliceAsBytes(s); + try c.pins.append(c.meta, .{ .addr = addr, .len = bytes.len, .hash = if (checked) std.hash.Wyhash.hash(0, bytes) else 0, .where = c.where }); + return; + }; + _ = try c.allocation(addr); + if (comptime heapIn(E, 0)) for (s) |*e| try c.visit(E, e); + } +}; + +/// The blobs: what an edit puts in place of its predecessor, never writes +/// (File.setContentSpan), and frees raw (memory.freeUnfilled, freeRaw). +fn pinned(comptime T: type, comptime name: []const u8) bool { + const File = pardes.panes.File; + return (T == File.State and (std.mem.eql(u8, name, "content") or std.mem.eql(u8, name, "line_starts"))) or + (T == File.Snapshot and std.mem.eql(u8, name, "content")); +} + +fn annotatedStruct(comptime T: type) bool { + return @typeInfo(T) == .@"struct" and @hasDecl(T, "replica"); +} + +/// The queues every step drains (empty between steps, asserted when a copy +/// is taken: what is in their slots is nothing), and the frame statistics +/// (numbers, and a static name). +fn unsaved(comptime name: []const u8) bool { + return std.mem.eql(u8, name, "effects") or std.mem.eql(u8, name, "in_q") or std.mem.eql(u8, name, "frames"); +} + +fn annotated(comptime T: type, comptime kind: []const u8, comptime name: []const u8) bool { + @setEvalBranchQuota(100_000); + if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), kind)) return false; + inline for (@field(T.replica, kind)) |n| if (comptime std.mem.eql(u8, n, name)) return true; + return false; +} + +/// A field no walk sees into (a C handle, a function): its own keeper's. +fn opaqueTo(comptime F: type) bool { + return switch (@typeInfo(F)) { + .optional => |o| opaqueTo(o.child), + .pointer => |p| p.size == .many or p.size == .c or switch (@typeInfo(p.child)) { + .@"opaque", .@"fn" => true, + else => false, + }, + else => false, + }; +} + +/// Whether a `T` can hold a pointer to the heap at all (else a walk of it +/// finds nothing to save). Deep types count as yes. +fn heapIn(comptime T: type, comptime depth: u32) bool { + if (depth > 12) return true; + return switch (@typeInfo(T)) { + .void, .null, .undefined, .bool, .int, .float, .@"enum", .error_set, .comptime_int, .comptime_float, .enum_literal, .type => false, + .optional => |o| heapIn(o.child, depth + 1), + .array => |a| a.len > 0 and heapIn(a.child, depth + 1), + .pointer => true, + .error_union => |e| heapIn(e.payload, depth + 1), + .@"struct" => |s| blk: { + if (s.layout == .@"packed") break :blk false; + for (s.field_types, s.field_attrs) |F, attr| if (!attr.@"comptime" and heapIn(F, depth + 1)) break :blk true; + break :blk false; + }, + .@"union" => |u| blk: { + for (u.field_types) |F| if (heapIn(F, depth + 1)) break :blk true; + break :blk false; + }, + else => true, + }; +} + +test "a copy put back is the core as it was; one let go keeps what was done" { + var e: Epoch = .{ .child = std.testing.allocator }; + defer e.deinit(); + const gpa = e.allocator(); + const p = try Pardes.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa }); + p.pump(.{}) catch {}; + const before = walk.digest(Pardes, p); + var c: Copy = .{}; + defer c.deinit(); + const typed = "ox y z"; + try c.take(&e, p); + for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } }); + p.update(.{ .key = .{ .cp = pardes.Key.escape } }); + p.pump(.{}) catch {}; + const edited = walk.digest(Pardes, p); + try std.testing.expect(edited != before); + c.restore(); + try std.testing.expectEqual(before, walk.digest(Pardes, p)); + // The same again, let go this time: what was typed stays. + try c.take(&e, p); + for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } }); + p.update(.{ .key = .{ .cp = pardes.Key.escape } }); + p.pump(.{}) catch {}; + try std.testing.expectEqual(edited, walk.digest(Pardes, p)); + c.release(); + try std.testing.expectEqual(edited, walk.digest(Pardes, p)); + p.deinit(); + try std.testing.expectEqual(@as(usize, 0), e.live.count()); +} diff --git a/src/syntax.zig b/src/syntax.zig index 985a9888..858ef6a2 100644 --- a/src/syntax.zig +++ b/src/syntax.zig @@ -381,10 +381,34 @@ pub fn parseTree(path: []const u8, content: []const u8) ?*anyopaque { if (!enabled) return null; const selected = (forExt(std.fs.path.extension(path)) catch return null) orelse return null; const tree = selected.parser.parseString(content, null) orelse return null; + if (held_trees) |h| h.born.append(h.meta, @ptrCast(tree)) catch {}; return @ptrCast(tree); } +/// While a replica's rollback copy is held (src/rollback.zig) a tree parsed +/// is the speculation's, and one freed is put off: trees live on the C +/// heap, which the core's allocator cannot see. Null otherwise. +pub var held_trees: ?*HeldTrees = null; +pub const HeldTrees = struct { + meta: std.mem.Allocator, + born: std.ArrayListUnmanaged(*anyopaque) = .empty, + freed: std.ArrayListUnmanaged(*anyopaque) = .empty, +}; + pub fn freeTree(tree: *anyopaque) void { + if (!enabled) return; + if (held_trees) |h| { + for (h.born.items, 0..) |t, i| if (t == tree) { + _ = h.born.swapRemove(i); + return destroyTree(tree); + }; + h.freed.append(h.meta, tree) catch destroyTree(tree); + return; + } + destroyTree(tree); +} + +pub fn destroyTree(tree: *anyopaque) void { if (!enabled) return; const t: *ts.Tree = @ptrCast(@alignCast(tree)); t.destroy(); diff --git a/src/tape.zig b/src/tape.zig index ec38deac..70609858 100644 --- a/src/tape.zig +++ b/src/tape.zig @@ -127,19 +127,40 @@ pub const Tape = struct { /// PARDES_RECORD_EVERY: a digest after every input, a nested one's too /// (to find the step a divergence starts at), not only the host's last. every: bool = false, + /// A replica applying its own input before the authority has ordered it + /// (src/replica.zig): recorded as the authority would record it, so the + /// two can be compared, but nothing is performed. A host call or a + /// syscall stops it (`poisoned`): what the call returns is the + /// authority's to say, and the input waits for it. A read of the clock + /// or the environment (`value`) is made here, a guess the comparison + /// checks. + speculating: bool = false, + poisoned: bool = false, + /// The allocator of the core a replay makes (a replica's rollback epoch, + /// src/rollback.zig), when it is not the tape's own. + core_gpa: ?std.mem.Allocator = null, + /// Where a replay keeps what a core keeps of an input (its options), + /// for a tape that is let go; else the tape's allocator, for good. + kept_arena: ?std.heap.ArenaAllocator = null, + /// No digests recorded (a speculation's: a replica compares what it + /// was given and what it asked, from a state the authority shares). + no_digest: bool = false, fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void { t.scratch.clearRetainingCapacity(); walk.encode(T, v, &t.scratch.writer) catch @panic("tape: out of memory"); const payload = t.scratch.written(); const len: u32 = @intCast(payload.len); - t.buf.append(t.gpa, @intFromEnum(kind)) catch @panic("tape: out of memory"); + t.buf.append(t.gpa, @backingInt(kind)) catch @panic("tape: out of memory"); t.buf.appendSlice(t.gpa, std.mem.asBytes(&len)) catch @panic("tape: out of memory"); t.buf.appendSlice(t.gpa, payload) catch @panic("tape: out of memory"); if (t.buf.items.len > 1 << 20) t.flush(); } fn flush(t: *Tape) void { + // A tape in memory (a replica's, an authority's stream) is taken + // by whoever holds it. + if (t.fd < 0) return; var at: usize = 0; while (at < t.buf.items.len) { const n = libc.write(t.fd, t.buf.items[at..].ptr, t.buf.items.len - at); @@ -222,7 +243,7 @@ pub const Tape = struct { t.wrap(core); }; t.record(.done, void, &{}); - if (t.depth == 0 or t.every) if (t.core) |core| { + if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| { var parts: Parts = undefined; const d = digestParts(core, &parts); t.record(.digest, []const u64, &d); @@ -239,12 +260,12 @@ pub const Tape = struct { const head = t.in.take(5) catch return null; const len = std.mem.bytesToValue(u32, head[1..5]); const payload = t.in.take(len) catch return null; - return .{ .kind = @enumFromInt(head[0]), .payload = .{ .bytes = payload } }; + return .{ .kind = @fromBackingInt(@intCast(head[0])), .payload = .{ .bytes = payload } }; } fn peek(t: *const Tape) ?Kind { if (t.in.bytes.len - t.in.at < 5) return null; - return @enumFromInt(t.in.bytes[t.in.at]); + return @fromBackingInt(@intCast(t.in.bytes[t.in.at])); } fn diverge(t: *Tape, comptime why: []const u8, args: anytype) void { @@ -374,7 +395,8 @@ pub const Tape = struct { const tag = std.mem.bytesToValue(Tag, (r.take(@sizeOf(Tag)) catch return t.diverge("a short input", .{}))); r.at -= @sizeOf(Tag); const kept = tag == .init or tag == .init_from_dump or tag == .restore; - const input = walk.decode(Input, r, if (kept) t.gpa else t.arena.allocator()) catch return t.diverge("a short input", .{}); + const keep = if (t.kept_arena) |*k| k.allocator() else t.gpa; + const input = walk.decode(Input, r, if (kept) keep else t.arena.allocator()) catch return t.diverge("a short input", .{}); const outer = t.applying; t.applying = switch (input) { .update => |ev| @tagName(ev), @@ -390,13 +412,14 @@ pub const Tape = struct { .init_from_dump => |d| d.opts, else => unreachable, }; - opts.image_allocator = t.gpa; - opts.pdf_allocator = t.gpa; - opts.tree_sitter_allocator = t.gpa; - opts.frame_allocator = t.gpa; + const gpa = t.core_gpa orelse t.gpa; + opts.image_allocator = gpa; + opts.pdf_allocator = gpa; + opts.tree_sitter_allocator = gpa; + opts.frame_allocator = gpa; t.core = switch (input) { - .init => Pardes.init(t.gpa, opts), - .init_from_dump => |d| pardes.dump.initFromDump(t.gpa, opts, d.bytes), + .init => Pardes.init(gpa, opts), + .init_from_dump => |d| pardes.dump.initFromDump(gpa, opts, d.bytes), else => unreachable, } catch |err| return t.diverge("init failed: {t}", .{err}); t.core.?.host = t.hostOf(t.mask); @@ -608,8 +631,21 @@ fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype } return walk.decode(R, &ret, t.arena.allocator()) catch std.mem.zeroes(R); } - const real = @field(t.real.vtable.*, name).?; const id: u16 = i; + if (t.speculating) { + // Nobody watches a replica's step: its frames are its own, drawn + // outside it (and the authority's host says so too, or the + // comparison fails). + if (comptime std.mem.eql(u8, name, "watched")) { + const r = false; + t.record(.host, u16, &id); + t.record(.ret, R, &r); + return r; + } + t.poisoned = true; + return poisonOf(R); + } + const real = @field(t.real.vtable.*, name).?; t.record(.host, u16, &id); t.seeFields(); const outer = !t.host_side; @@ -639,7 +675,7 @@ pub fn value(comptime s: Site, comptime f: anytype, args: anytype) @typeInfo(@Ty fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anytype, comptime yields: bool) @typeInfo(@TypeOf(f)).@"fn".return_type.? { const R = @typeInfo(@TypeOf(f)).@"fn".return_type.?; const t = on orelse return if (yields) out(f, args) else @call(.auto, f, args); - const id: u16 = @as(u16, host_fns.len) + @intFromEnum(s); + const id: u16 = @as(u16, host_fns.len) + @backingInt(s); if (t.replay) { if (!t.expectHost(id, @tagName(s))) { std.debug.print("replay: {s}\n", .{t.diverged orelse "?"}); @@ -651,6 +687,12 @@ fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anyt // The host's own (a shell's spawn asking the shell), or one inside a // site's syscall: the outer call is the record. if (t.host_side) return if (yields) out(f, args) else @call(.auto, f, args); + // A syscall a speculating replica must not make: its input waits for + // the authority's answer. + if (yields and t.speculating) { + t.poisoned = true; + return poisonOf(R); + } t.record(.host, u16, &id); t.seeFields(); t.host_side = true; @@ -679,7 +721,173 @@ fn out(comptime f: anytype, args: anytype) @typeInfo(@TypeOf(f)).@"fn".return_ty /// Asked by `turn.yield`: a syscall a replica must never make. pub fn replaying() bool { - return if (on) |t| t.replay else false; + return if (on) |t| t.replay or t.speculating else false; +} + +/// A replica speculating (src/replica.zig): state only the authority +/// changes (a terminal's emulator) is left alone, and the input waits. +pub fn speculating() bool { + return if (on) |t| t.speculating else false; +} + +/// What a speculation reached is the authority's: the input is undone and +/// waits for the authority's order. +pub fn poison() void { + if (on) |t| if (t.speculating) { + t.poisoned = true; + }; +} + +/// A harmless stand-in for what a host call or a syscall would have +/// returned to a speculation that is thrown away once it returns: an +/// error where one can be said, else zeroes. +fn poisonOf(comptime R: type) R { + return switch (@typeInfo(R)) { + .error_union => |e| if (@typeInfo(e.error_set).error_set.error_names) |errors| + (if (errors.len > 0) @field(e.error_set, errors[0]) else std.mem.zeroes(R)) + else + error.Unexpected, + .optional => null, + .void => {}, + .@"union" => |u| inline for (u.field_names, u.field_types) |name, F| { + if (comptime zeroable(F)) break @unionInit(R, name, std.mem.zeroes(F)); + } else @compileError("tape: no harmless value of " ++ @typeName(R)), + else => std.mem.zeroes(R), + }; +} + +fn zeroable(comptime T: type) bool { + return switch (@typeInfo(T)) { + .int, .float, .bool, .optional, .void => true, + .pointer => |p| p.size == .slice, + .array => |a| zeroable(a.child), + .@"struct" => |s| blk: { + for (s.field_types) |F| if (!zeroable(F)) break :blk false; + break :blk true; + }, + else => false, + }; +} + +// ---- a replica's tapes in memory (src/replica.zig) ---- + +/// A tape recorded in memory: an authority's stream, taken unit by unit. +pub fn memory(gpa: std.mem.Allocator) Tape { + return .{ .gpa = gpa, .replay = false, .scratch = .init(gpa), .arena = .init(gpa), .kept_arena = .init(gpa) }; +} + +/// What a tape in memory holds, given back (its core is gone already). +pub fn release(t: *Tape) void { + t.buf.deinit(t.gpa); + t.scratch.deinit(); + t.arena.deinit(); + if (t.kept_arena) |*k| k.deinit(); +} + +/// What was recorded since the last take; the tape's to reuse after. +pub fn taken(t: *Tape) []const u8 { + return t.buf.items; +} + +pub fn clearTaken(t: *Tape) void { + t.buf.clearRetainingCapacity(); +} + +/// The records of `bytes`, top-level inputs and all, applied to the +/// tape's core as the authority applied them, each digest checked; why +/// they diverged, or null. +pub fn replayUnit(t: *Tape, bytes: []const u8) ?[]const u8 { + t.replay = true; + t.speculating = false; + defer t.replay = false; + t.in = .{ .bytes = bytes }; + while (t.diverged == null) { + const kind = t.peek() orelse break; + var rec = t.next().?; + switch (kind) { + .input => { + t.apply(&rec.payload); + _ = t.arena.reset(.retain_capacity); + }, + .set => t.applySet(&rec.payload), + .digest => t.check(&rec.payload), + .host, .ret, .done => t.diverge("a {t} record at the top", .{kind}), + } + } + return t.diverged; +} + +/// Starts recording `t`'s core as a speculation: the host's watched +/// fields as they are now, nothing recorded yet. +pub fn beginSpeculation(t: *Tape) void { + t.replay = false; + t.speculating = true; + t.poisoned = false; + t.no_digest = true; + t.buf.clearRetainingCapacity(); + t.seeFields(); +} + +/// Whether it stayed clean (no host call, no syscall, no authority state). +pub fn endSpeculation(t: *Tape) bool { + t.speculating = false; + t.no_digest = false; + return !t.poisoned; +} + +/// Whether two tapes record the same inputs, host calls and answers, +/// their digests aside. +pub fn sameRecords(a: []const u8, b: []const u8) bool { + var x: walk.Reader = .{ .bytes = a }; + var y: walk.Reader = .{ .bytes = b }; + while (true) { + const ra = nextRecord(&x); + const rb = nextRecord(&y); + if (ra == null or rb == null) return ra == null and rb == null; + if (ra.?.kind != rb.?.kind or !std.mem.eql(u8, ra.?.payload, rb.?.payload)) return false; + } +} + +fn nextRecord(r: *walk.Reader) ?struct { kind: Kind, payload: []const u8 } { + while (true) { + const head = r.take(5) catch return null; + const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return null; + const kind: Kind = @fromBackingInt(@intCast(head[0])); + if (kind != .digest) return .{ .kind = kind, .payload = payload }; + } +} + +/// A tape's records, one a line (kind; an input's or a host call's name), +/// for a divergence's report. +pub fn describe(bytes: []const u8, w: *std.Io.Writer) void { + var r: walk.Reader = .{ .bytes = bytes }; + var depth: usize = 0; + while (true) { + const head = r.take(5) catch return; + const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return; + const kind: Kind = @fromBackingInt(@intCast(head[0])); + if (kind == .done or kind == .ret) depth -|= 1; + w.splatByteAll(' ', depth * 2) catch {}; + switch (kind) { + .input => { + const tag = std.mem.bytesToValue(std.meta.Tag(Input), payload[0..@sizeOf(std.meta.Tag(Input))]); + w.print("input {t}", .{tag}) catch {}; + if (tag == .update) w.print(" {t}", .{std.mem.bytesToValue(std.meta.Tag(pardes.Event), payload[@sizeOf(std.meta.Tag(Input))..][0..@sizeOf(std.meta.Tag(pardes.Event))])}) catch {}; + }, + .host => { + const id = std.mem.bytesToValue(u16, payload[0..2]); + w.print("host {s}", .{if (id < host_fns.len) host_fns[id] else @tagName(@as(Site, @fromBackingInt(@intCast(id - host_fns.len))))}) catch {}; + }, + else => w.print("{t} ({d} bytes)", .{ kind, payload.len }) catch {}, + } + w.writeByte('\n') catch {}; + if (kind == .input or kind == .host) depth += 1; + } +} + +/// The digest a replica and its authority must agree on. +pub fn digestOf(p: *const Pardes) u64 { + return walk.digest(Pardes, p); } /// PARDES_RECORD set: the tape is written from the session's first call. diff --git a/src/terminal.zig b/src/terminal.zig index e737a831..81fae5db 100644 --- a/src/terminal.zig +++ b/src/terminal.zig @@ -417,9 +417,18 @@ pub fn panFor(p: *const Pardes, pane: *const Pane, r: pardes.Rect) u16 { return @intCast(@min(pane.rows - shown, (at + 1) -| shown)); } +/// A replica's speculation leaves an emulator be: it is the authority's +/// (docs/next-daemon.md, phase 5), so the input waits for its order. +fn authorityOnly() bool { + if (!pardes.tape.speculating()) return false; + pardes.tape.poison(); + return true; +} + /// Move the emulator's viewport by `delta` shell rows (negative scrolls back). pub fn scrollGrid(pane: *Pane, delta: i32) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; state.vt.screens.active.scroll(.{ .delta_row = delta }); } @@ -434,6 +443,7 @@ pub fn atBottom(pane: *const Pane) bool { /// Snap the viewport back onto live output. pub fn followOutput(pane: *Pane) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; state.vt.screens.active.scroll(.active); } @@ -442,6 +452,7 @@ pub fn followOutput(pane: *Pane) void { /// a scrollback; the next resize retries with the same numbers. pub fn resizeGrid(pane: *Pane, gpa: std.mem.Allocator, cols: u16, rows: u16) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; if (cols != pane.cols) for (0..pane.sel.len) |button| { pane.clearPointerSelection(button); @@ -643,6 +654,7 @@ pub fn screenTextLen(pane: *Pane) usize { /// Release the emulator's heap. The Pane allocation itself is the core's. pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; if (comptime images_enabled) state.images.deinit(gpa); state.stream.deinit(); @@ -654,6 +666,7 @@ pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void { /// Allocate the live emulator half of a terminal pane. Slot ownership, serial /// assignment, and spawn effects remain core lifecycle invariants. pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { + if (authorityOnly()) return error.OutOfMemory; const pane = try createDoc(gpa, cols, rows); errdefer gpa.destroy(pane); if (comptime !enabled) return pane; @@ -674,6 +687,9 @@ pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { }); state.stream = .init(.{ .handler = .{ .inner = state.vt.vtHandler() }, .allocator = gpa }); state.reply_len = 0; + // Every field its default (create leaves them what the heap had, which + // a digest then reads: two replicas must agree, src/replica.zig). + state.reply_dropped = 0; state.mouse_cell = null; state.images = if (images_enabled) .{} else {}; if (comptime images_enabled) TerminalImages.installPngDecoder(); @@ -900,6 +916,7 @@ pub fn feedOutput(p: *Pardes, pane: *Pane, bytes: []const u8) void { // There are no pty reads at all without an emulator to parse them into. if (comptime !enabled) return; if (pane.terminal == null) return; + if (authorityOnly()) return; const has_positions = pane.ovl != null or pane.body.cur_pinned or pane.body.vsel.active or pane.body.msel.active or pane.body.nsel > 0 or pane.body.last_edit != null or pane.look_at != null or pane.body.ed_undo_len > 0 or pane.body.ed_redo_len > 0 or pointerRowCount(pane) > 0; diff --git a/src/walk.zig b/src/walk.zig index dc1664cb..3e482e9a 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -42,7 +42,7 @@ pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 { if (attr.@"comptime" or comptime excluded(T, name)) continue; var h = Hasher.init(0); if (comptime lengthOf(T, name)) |len| { - hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], &h); + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h); } else hash(F, &@field(v, name), &h); out[n] = h.final(); n += 1; @@ -63,7 +63,7 @@ pub fn fieldNames(comptime T: type) []const []const u8 { } /// Types that are machinery, never state: an allocator, the Io, a lock. -fn machinery(comptime T: type) bool { +pub fn machinery(comptime T: type) bool { inline for (.{ std.mem.Allocator, std.Io, std.Io.Mutex, std.Io.Condition, std.Thread, std.heap.ArenaAllocator }) |M| if (T == M) return true; return false; } @@ -92,7 +92,7 @@ fn opaqueTo(comptime F: type) bool { }; } -fn excluded(comptime T: type, comptime name: []const u8) bool { +pub fn excluded(comptime T: type, comptime name: []const u8) bool { @setEvalBranchQuota(100_000); if (!@hasDecl(T, "replica")) return false; inline for (.{ "local", "derived", "authority" }) |kind| { @@ -104,12 +104,22 @@ fn excluded(comptime T: type, comptime name: []const u8) bool { } /// How far the field `len` names says its array is written (null: none). -fn lengthIn(v: anytype, comptime len: []const u8) usize { +/// What a `len`-cut field holds: a fixed array's, or a slice's room (a +/// selection's ranges, made once and used `nsel` deep). +fn Element(comptime F: type) type { + return switch (@typeInfo(F)) { + .array => |a| a.child, + .pointer => |p| p.child, + else => @compileError("walk: a `len` cuts an array or a slice, not " ++ @typeName(F)), + }; +} + +pub fn lengthIn(v: anytype, comptime len: []const u8) usize { const n = @field(v, len); return if (@typeInfo(@TypeOf(n)) == .optional) (if (n) |k| k else 0) else n; } -fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 { +pub fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 { @setEvalBranchQuota(100_000); if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "len")) return null; inline for (T.replica.len) |pair| if (comptime std.mem.eql(u8, pair[0], name)) return pair[1]; @@ -134,7 +144,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { .bool => h.update(&.{@intFromBool(v.*)}), .int => hashInt(T, v.*, h), .float => h.update(std.mem.asBytes(v)), - .@"enum" => |e| hashInt(e.tag_type, @intFromEnum(v.*), h), + .@"enum" => |e| hashInt(e.tag_type, @backingInt(v.*), h), .optional => |o| if (v.*) |*payload| { h.update(&.{1}); hash(o.child, payload, h); @@ -167,7 +177,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { 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`)"); if (comptime lengthOf(T, name)) |len| { - hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], h); + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h); } else hash(F, &@field(v, name), h); } }, diff --git a/test/replicas.zig b/test/replicas.zig new file mode 100644 index 00000000..cdb161e8 --- /dev/null +++ b/test/replicas.zig @@ -0,0 +1,327 @@ +//! pardes-replicas: one authority and several replicas of a session in one +//! process (src/replica.zig), each client typing at once over its own +//! delayed, jittered link, as monkey.zig's scripts type at a tty, each in a +//! view of its own (src/views.zig) over the text they share; `--shared` +//! puts them all in one, where they clash at every key: a stress of +//! correctness, not a picture of a session. +//! +//! zig build replicas -Dplatform=tty -- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207] [--first K] [--shared] +//! +//! Gates, per seed and RTT: no replica diverges (every confirmed unit's +//! digests agree as it is replayed), and at quiescence every replica's +//! digest is the authority's. Reported per RTT: how inputs went (applied at +//! once, stopped at a host call, left to the authority), how units were +//! taken (fast path, rollback for a misprediction or another's input), and +//! what a speculative apply, a copy and a rollback cost against a frame. +const std = @import("std"); +const libc = std.c; +const pardes = @import("pardes"); +const replica = pardes.replica; +const Key = pardes.Key; + +const gpa = std.heap.c_allocator; +var trace = false; +const frame_us = 16_667; + +/// The authority's host: no frames drawn (a replica draws its own), and a +/// pty that echoes what it is written, 2 ms later, as a shell's. +const Host = struct { + echo: std.ArrayListUnmanaged(struct { pane: u8, bytes: []u8 }) = .empty, + + fn watched(_: ?*anyopaque) bool { + return false; + } + + fn ptyWrite(ctx: ?*anyopaque, pane: u8, bytes: []const u8) void { + const h: *Host = @ptrCast(@alignCast(ctx.?)); + h.echo.append(gpa, .{ .pane = pane, .bytes = gpa.dupe(u8, bytes) catch return }) catch {}; + } + + fn ignore(_: ?*anyopaque, _: []const u8) void {} + + const vtable: pardes.Host.VTable = .{ .watched = watched, .pty_write = ptyWrite, .set_clipboard = ignore }; + + fn host(h: *Host) pardes.Host { + return .{ .ctx = h, .vtable = &vtable }; + } +}; + +const Kind = enum { input, to_authority, to_replica, echo }; + +const Msg = struct { + at: u64, + n: u64, + kind: Kind, + who: u16, + bytes: []u8, + + fn order(_: void, a: Msg, b: Msg) std.math.Order { + if (a.at != b.at) return std.math.order(a.at, b.at); + return std.math.order(a.n, b.n); + } +}; + +const Link = struct { + last: u64 = 0, + /// When a message sent at `now` arrives: half the RTT, jitter on top, + /// and never before the one sent ahead of it (a stream keeps order). + fn arrive(l: *Link, random: std.Random, now: u64, one_way: u64, jitter: u64) u64 { + const at = @max(l.last + 1, now + one_way + random.uintLessThan(u64, jitter + 1)); + l.last = at; + return at; + } +}; + +const Totals = struct { + inputs: u64 = 0, + speculated: u64 = 0, + stopped: u64 = 0, + unspeculated: u64 = 0, + units: u64 = 0, + fast: u64 = 0, + mispredicted: u64 = 0, + foreign: u64 = 0, + rebases: u64 = 0, + copies: u64 = 0, + copy_bytes: u64 = 0, + divergences: u64 = 0, + unequal: u64 = 0, + spec_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_ns: std.ArrayListUnmanaged(u64) = .empty, + rollback_ns: std.ArrayListUnmanaged(u64) = .empty, + + fn add(t: *Totals, s: *const replica.Stats) !void { + t.inputs += s.inputs; + t.speculated += s.speculated; + t.stopped += s.stopped; + t.unspeculated += s.unspeculated; + t.units += s.units; + t.fast += s.fast; + t.mispredicted += s.mispredicted; + t.foreign += s.foreign; + t.rebases += s.rebases; + t.copies += s.copies; + t.copy_bytes += s.copy_bytes; + try t.spec_ns.appendSlice(gpa, s.spec_ns.items); + try t.copy_ns.appendSlice(gpa, s.copy_ns.items); + try t.rollback_ns.appendSlice(gpa, s.rollback_ns.items); + } +}; + +/// One client's next input: monkey.zig's mix, as events. +fn nextEvent(random: std.Random, buf: *[64]u8) pardes.Event { + const typed = "abcdefghijklmnopqrstuvwxyz0123456789 -_=+,:;()"; + const normal = "hjklwbe0$xpuyoOiaAIdcv.nN%sC"; + switch (random.uintLessThan(u8, 40)) { + 0...15 => { + buf[0] = typed[random.uintLessThan(usize, typed.len)]; + return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; + }, + 16...27 => { + buf[0] = normal[random.uintLessThan(usize, normal.len)]; + return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; + }, + 28...31 => return .{ .key = .{ .cp = Key.escape } }, + 32 => return .{ .key = .{ .cp = Key.enter } }, + 33 => return .{ .key = .{ .cp = Key.backspace } }, + 34 => return .{ .key = .{ .cp = switch (random.uintLessThan(u8, 4)) { + 0 => Key.up, + 1 => Key.down, + 2 => Key.left, + else => Key.right, + } } }, + 35 => { + const n = random.intRangeAtMost(usize, 1, 24); + for (buf[0..n]) |*c| c.* = typed[random.uintLessThan(usize, typed.len)]; + return .{ .paste = buf[0..n] }; + }, + 36 => return .{ .command = switch (random.uintLessThan(u8, 4)) { + 0 => "Newcol", + 1 => "Zerox", + 2 => "Undo", + else => "Redo", + } }, + 37 => return .{ .resize = .{ .cols = @intCast(random.intRangeAtMost(u16, 60, 120)), .rows = @intCast(random.intRangeAtMost(u16, 16, 40)) } }, + 38 => return .{ .mouse = .{ .button = .left, .kind = .press, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, + else => return .{ .mouse = .{ .button = .left, .kind = .release, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, + } +} + +fn writeFile(path: [:0]const u8, lines: usize) !void { + const fd = libc.open(path, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = libc.close(fd); + var line: [80]u8 = undefined; + for (0..lines) |n| { + const text = try std.fmt.bufPrint(&line, "const value_{d:0>4} = {d}; // a line to edit\n", .{ n, n *% 7919 }); + if (libc.write(fd, text.ptr, text.len) != @as(isize, @intCast(text.len))) return error.WriteFailed; + } +} + +const Run = struct { seed: u64, rtt_ms: u64, steps: usize, clients: u16, shared: bool }; + +fn run(r: Run, dir: []const u8, totals: *Totals) !void { + if (trace) std.debug.print("seed {d} rtt {d} ms\n", .{ r.seed, r.rtt_ms }); + var prng = std.Random.DefaultPrng.init(r.seed *% 0x9e3779b97f4a7c15 +% r.rtt_ms); + const random = prng.random(); + var host: Host = .{}; + defer { + for (host.echo.items) |e| gpa.free(e.bytes); + host.echo.deinit(gpa); + } + var paths: [3][256:0]u8 = undefined; + for (&paths, 0..) |*p, i| { + const path = try std.fmt.bufPrintSentinel(p, "{s}/f{d}.zig", .{ dir, i }, 0); + try writeFile(path, 60 + 40 * i); + } + // The tty's own boot (a raw shell, a text pane under it), then three + // files looked at: keys go to the last, a pane's shell echoes. + const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty }, host.host()); + defer a.deinit(); + const first = try gpa.dupe(u8, try a.unit(0, 0)); + defer gpa.free(first); + var reps: [8]*replica.Replica = undefined; + for (reps[0..r.clients], 1..) |*rp, id| rp.* = try replica.Replica.init(gpa, @intCast(id), first); + defer for (reps[0..r.clients]) |rp| rp.deinit(); + for (&paths) |*path| { + var line: [300]u8 = undefined; + const unit = try a.local(.{ .command = try std.fmt.bufPrint(&line, "Look {s}", .{std.mem.sliceTo(path, 0)}) }); + for (reps[0..r.clients]) |rp| rp.confirm(unit); + } + // Each client a view of its own (src/views.zig), the first the + // session's; or, --shared, every client in the one. + if (!r.shared) for (reps[1..r.clients], 2..) |rp, id| { + const opened = try a.openView(@intCast(id)); + rp.view = opened.view; + for (reps[0..r.clients]) |each| each.confirm(opened.unit); + }; + var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; + defer queue.deinit(gpa); + var n: u64 = 0; + const one_way = r.rtt_ms * 1000 / 2; + const jitter = one_way / 10; + var up: [8]Link = @splat(.{}); + var down: [8]Link = @splat(.{}); + var left: [8]usize = @splat(r.steps); + // Each client's first input, soon. + for (0..r.clients) |c| { + try queue.push(gpa, .{ .at = random.uintLessThan(u64, 200_000), .n = n, .kind = .input, .who = @intCast(c + 1), .bytes = &.{} }); + n += 1; + } + while (queue.pop()) |m| { + defer if (m.bytes.len > 0) gpa.free(m.bytes); + switch (m.kind) { + .input => { + const c = m.who - 1; + var buf: [64]u8 = undefined; + const ev = nextEvent(random, &buf); + const before = reps[c].stats; + const msg = try gpa.dupe(u8, try reps[c].input(ev)); + if (trace) std.debug.print("{d} ms client {d}: {t} {s} -> {s}\n", .{ m.at / 1000, m.who, ev, switch (ev) { + .key => |k| k.text, + .paste => |t| t, + .command => |t| t, + else => "", + }, if (reps[c].stats.speculated > before.speculated) "applied" else if (reps[c].stats.stopped > before.stopped) "STOPPED" else if (reps[c].stats.unspeculated > before.unspeculated) "view" else "waits" }); + try queue.push(gpa, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_authority, .who = m.who, .bytes = msg }); + n += 1; + left[c] -= 1; + if (left[c] > 0) { + // A typist: keys 50-200 ms apart, a pause now and then. + const gap: u64 = if (random.uintLessThan(u8, 12) == 0) random.intRangeAtMost(u64, 300_000, 1_500_000) else random.intRangeAtMost(u64, 50_000, 200_000); + try queue.push(gpa, .{ .at = m.at + gap, .n = n, .kind = .input, .who = m.who, .bytes = &.{} }); + n += 1; + } + }, + .to_authority, .echo => { + const unit = if (m.kind == .echo) + try a.local(.{ .output = .{ .pane = @intCast(m.who), .bytes = m.bytes } }) + else + try a.take(m.bytes); + for (0..r.clients) |c| { + const copy = try gpa.dupe(u8, unit); + try queue.push(gpa, .{ .at = down[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_replica, .who = @intCast(c + 1), .bytes = copy }); + n += 1; + } + for (host.echo.items) |e| { + try queue.push(gpa, .{ .at = m.at + 2_000, .n = n, .kind = .echo, .who = e.pane, .bytes = e.bytes }); + n += 1; + } + host.echo.clearRetainingCapacity(); + }, + .to_replica => { + const rp = reps[m.who - 1]; + rp.confirm(m.bytes); + rp.settle(); + }, + } + } + const want = replica.digestOf(a); + for (reps[0..r.clients], 1..) |rp, id| { + try totals.add(&rp.stats); + if (rp.diverged) |why| { + totals.divergences += 1; + std.debug.print("seed {d} rtt {d} ms: replica {d} diverged: {s}\n", .{ r.seed, r.rtt_ms, id, why }); + } else if (!rp.quiet() or rp.digest() != want) { + totals.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: replica {d} at quiescence: {s}\n", .{ r.seed, r.rtt_ms, id, if (rp.quiet()) "another digest" else "inputs still pending" }); + } + } +} + +fn pct(samples: []u64, p: usize) u64 { + if (samples.len == 0) return 0; + std.mem.sort(u64, samples, {}, std.sort.asc(u64)); + return samples[@min(samples.len - 1, samples.len * p / 100)]; +} + +pub fn main(init: std.process.Init) !void { + const args = try init.minimal.args.toSlice(init.arena.allocator()); + var seeds: u64 = 4; + var first: u64 = 0; + var steps: usize = 120; + var clients: u16 = 3; + var rtts: []const u64 = &.{ 30, 80, 207 }; + var shared = false; + var rtt_buf: [8]u64 = undefined; + var i: usize = 1; + while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; + while (i + 1 < args.len) : (i += 2) { + while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; + if (i + 1 >= args.len) break; + const name = args[i]; + const value = args[i + 1]; + if (std.mem.eql(u8, name, "--seeds")) seeds = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--first")) first = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--steps")) steps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, name, "--clients")) clients = @min(8, try std.fmt.parseInt(u16, value, 10)) else if (std.mem.eql(u8, name, "--rtt")) { + var it = std.mem.tokenizeScalar(u8, value, ','); + var k: usize = 0; + while (it.next()) |v| : (k += 1) rtt_buf[k] = try std.fmt.parseInt(u64, v, 10); + rtts = rtt_buf[0..k]; + } else return error.UnknownOption; + } + trace = libc.getenv("PARDES_REPLICA_TRACE") != null; + if (libc.getenv("PARDES_REPLICA_FILL")) |b| pardes.rollback.Epoch.fill = std.fmt.parseInt(u8, std.mem.span(b), 0) catch 0xff; + var dir_buf: [256]u8 = undefined; + const tmp = std.mem.span(libc.getenv("TMPDIR") orelse "/tmp"); + const dir = try std.fmt.bufPrint(&dir_buf, "{s}/replicas-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) }); + try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); + defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; + var failed = false; + std.debug.print("{d} seeds x {d} inputs from each of {d} clients, {s}; costs in us (frame {d})\n", .{ seeds, steps, clients, if (shared) "sharing one view" else "a view each", frame_us }); + std.debug.print(" rtt inputs at-once stopped view units fast rollback(mis+foreign) rate rebase spec p50/p99 copy p50/p99 (KB) rollback p50/p99 diverged unequal\n", .{}); + for (rtts) |rtt| { + var t: Totals = .{}; + for (first..first + seeds) |seed| try run(.{ .seed = seed, .rtt_ms = rtt, .steps = steps, .clients = clients, .shared = shared }, dir, &t); + const rollbacks = t.mispredicted + t.foreign; + std.debug.print("{d:>4} {d:>6} {d:>7} {d:>7} {d:>4} {d:>6} {d:>6} {d:>6} ({d}+{d}) {d:>5.1}% {d:>6} {d:>5}/{d:<6} {d:>5}/{d:<5} ({d}) {d:>7}/{d:<7} {d:>8} {d:>7}\n", .{ + rtt, t.inputs, t.speculated, + t.stopped, t.unspeculated, t.units, + t.fast, rollbacks, t.mispredicted, + t.foreign, @as(f64, @floatFromInt(rollbacks)) * 100 / @as(f64, @floatFromInt(@max(t.inputs, 1))), t.rebases, + pct(t.spec_ns.items, 50) / 1000, pct(t.spec_ns.items, 99) / 1000, pct(t.copy_ns.items, 50) / 1000, + pct(t.copy_ns.items, 99) / 1000, t.copy_bytes / @max(t.copies, 1) / 1024, pct(t.rollback_ns.items, 50) / 1000, + pct(t.rollback_ns.items, 99) / 1000, t.divergences, t.unequal, + }); + if (t.divergences > 0 or t.unequal > 0) failed = true; + } + if (failed) std.process.exit(1); +} diff --git a/test/rollback_bench.zig b/test/rollback_bench.zig index 721c6f13..38fe011d 100644 --- a/test/rollback_bench.zig +++ b/test/rollback_bench.zig @@ -1,14 +1,11 @@ -//! What a replica's rollback copy would cost (docs/next-daemon.md, open -//! point 3), and what a fork of the authority stalls it for (open point 5). -//! A typical session and a big one are built in process; for each: -//! - the state the walker visits (src/walk.zig's digest walk, which is -//! what speculation can write: views, buffers, registers, counters, -//! terminal metadata), in bytes; -//! - the part of it that is pinned blobs: a file's text and its undo -//! snapshots, which an edit replaces rather than changes -//! (File.setContentSpan), so a copy keeps a reference; -//! - the walk's time, the blobs' share of it, and a memcpy of the rest: -//! a walker copy costs about the walk plus that write. +//! What a replica's rollback copy costs (docs/next-daemon.md, open point +//! 3, src/rollback.zig), and what a fork of the authority stalls it for +//! (open point 5). A typical session and a big one are built in process, on +//! a rollback epoch's allocator as a replica's core is; for each: +//! - the copy taken and let go: its time, the bytes it saves, the bytes +//! it pins (a file's text, its undo snapshots); +//! - a key that edits a file (`x`) applied on top, as a speculation, and +//! the copy put back: the apply's time and the restore's. //! Then a fork of the big one, child gone at once, and the authority's //! copy-on-write after it. //! @@ -69,8 +66,8 @@ fn writeFile(path: []const u8, lines: usize) !void { } } -fn build(s: Session, dir: []const u8) !*pardes.Pardes { - const core = try pardes.Pardes.init(gpa, .{ .tty_only = true }); +fn build(s: Session, dir: []const u8, a: std.mem.Allocator) !*pardes.Pardes { + const core = try pardes.Pardes.init(a, .{ .tty_only = true, .image_allocator = a, .pdf_allocator = a, .tree_sitter_allocator = a, .frame_allocator = a }); core.update(.{ .resize = .{ .cols = 200, .rows = 60 } }); pump(core); // The shell: pane 0 of a tty boot, its output fed as a pty's. @@ -112,36 +109,6 @@ fn build(s: Session, dir: []const u8) !*pardes.Pardes { return core; } -/// Where a file's text and its undo snapshots are held: what a copy pins. -fn blobs(core: *pardes.Pardes, out: *std.ArrayList(*[]u8)) !usize { - var total: usize = 0; - for (core.panes) |slot| if (slot) |pane| if (pane.file) |*f| { - try out.append(gpa, &f.content); - for (f.history.undo[0..f.history.undo_len]) |*snap| try out.append(gpa, &snap.content); - for (f.history.redo[0..f.history.redo_len]) |*snap| try out.append(gpa, &snap.content); - }; - for (out.items) |b| total += b.len; - return total; -} - -fn walkNs(core: *const pardes.Pardes) u64 { - var t: [reps]u64 = undefined; - var sink: u64 = 0; - for (&t) |*x| { - const t0 = nowNs(); - sink +%= walk.digest(pardes.Pardes, core); - x.* = nowNs() - t0; - } - std.mem.doNotOptimizeAway(sink); - return median(&t); -} - -fn walked(core: *const pardes.Pardes) usize { - var h = walk.Hasher.init(0); - walk.hash(pardes.Pardes, core, &h); - return h.total_len; -} - fn median(samples: []u64) u64 { std.mem.sort(u64, samples, {}, std.sort.asc(u64)); return samples[samples.len / 2]; @@ -161,49 +128,44 @@ pub fn main(init: std.process.Init) !void { const dir = try std.fmt.bufPrint(&dir_buf, "{s}/rollback-bench-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) }); try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; - std.debug.print("session panes walked MB blobs MB copy KB walk ms walk ms, blobs out memcpy ms copy ms (est.)\n", .{}); + std.debug.print("session panes copy KB pinned MB take ms release ms edit ms restore ms\n", .{}); var big: ?*pardes.Pardes = null; - for (sessions) |s| { - const core = try build(s, dir); - var list: std.ArrayList(*[]u8) = .empty; - defer list.deinit(gpa); - const blob_bytes = try blobs(core, &list); - const all = walked(core); - const walk_ns = walkNs(core); - // The blobs taken out, as a copy pins them: the walk of what a copy - // writes, then put back. - const kept = try gpa.alloc([]u8, list.items.len); - defer gpa.free(kept); - for (list.items, kept) |b, *k| { - k.* = b.*; - b.* = &.{}; + var epochs: [sessions.len]*pardes.rollback.Epoch = undefined; + for (sessions, &epochs) |s, *e| { + e.* = try gpa.create(pardes.rollback.Epoch); + e.*.* = .{}; + const core = try build(s, dir, e.*.allocator()); + var c: pardes.rollback.Copy = .{}; + defer c.deinit(); + var take: [reps]u64 = undefined; + var release: [reps]u64 = undefined; + for (&take, &release) |*x, *y| { + const t0 = nowNs(); + try c.take(e.*, core); + const t1 = nowNs(); + c.release(); + x.* = t1 - t0; + y.* = nowNs() - t1; } - const copy_bytes = walked(core); - const copy_walk_ns = walkNs(core); - for (list.items, kept) |b, k| b.* = k; - const src = try gpa.alloc(u8, @max(copy_bytes, 1)); - defer gpa.free(src); - const dst = try gpa.alloc(u8, @max(copy_bytes, 1)); - defer gpa.free(dst); - @memset(src, 1); - @memset(dst, 0); - var t: [reps]u64 = undefined; - for (&t) |*x| { + var edit: [reps]u64 = undefined; + var restore: [reps]u64 = undefined; + for (&edit, &restore) |*x, *y| { + try c.take(e.*, core); const t0 = nowNs(); - @memcpy(dst, src); - std.mem.doNotOptimizeAway(dst.ptr); - x.* = nowNs() - t0; + key(core, 'x', "x"); + const t1 = nowNs(); + c.restore(); + x.* = t1 - t0; + y.* = nowNs() - t1; } - const memcpy_ns = median(&t); var panes: usize = 0; for (core.panes) |slot| panes += @intFromBool(slot != null); const ms = 1e-6; - std.debug.print("{s:<8} {d:>5} {d:>9.1} {d:>8.1} {d:>7.1} {d:>7.3} {d:>18.3} {d:>9.3} {d:>14.3}\n", .{ - s.name, panes, - @as(f64, @floatFromInt(all)) / 1e6, @as(f64, @floatFromInt(blob_bytes)) / 1e6, - @as(f64, @floatFromInt(copy_bytes)) / 1e3, @as(f64, @floatFromInt(walk_ns)) * ms, - @as(f64, @floatFromInt(copy_walk_ns)) * ms, @as(f64, @floatFromInt(memcpy_ns)) * ms, - @as(f64, @floatFromInt(copy_walk_ns + memcpy_ns)) * ms, + std.debug.print("{s:<8} {d:>5} {d:>7.1} {d:>9.1} {d:>7.3} {d:>10.3} {d:>7.3} {d:>10.3}\n", .{ + s.name, panes, + @as(f64, @floatFromInt(c.savedBytes())) / 1e3, @as(f64, @floatFromInt(c.pinnedBytes())) / 1e6, + @as(f64, @floatFromInt(median(&take))) * ms, @as(f64, @floatFromInt(median(&release))) * ms, + @as(f64, @floatFromInt(median(&edit))) * ms, @as(f64, @floatFromInt(median(&restore))) * ms, }); if (big) |b| b.deinit(); big = core; -- cgit v1.3 From f264dbc4a646da695331fe7401fa013cbb720b6a Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Fri, 30 Oct 2026 00:25:19 -0300 Subject: 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 --- docs/next-daemon.md | 44 +++++++++++++++++ src/File.zig | 12 +++-- src/Query.zig | 1 + src/Registers.zig | 38 +++++++------- src/memory.zig | 10 +++- src/replica.zig | 51 +++++++++++++++++++ src/rollback.zig | 36 ++------------ src/walk.zig | 139 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 277 insertions(+), 54 deletions(-) (limited to 'src/memory.zig') diff --git a/docs/next-daemon.md b/docs/next-daemon.md index 55921027..681a2ed4 100644 --- a/docs/next-daemon.md +++ b/docs/next-daemon.md @@ -1825,6 +1825,50 @@ Follow-ups (2026-10-29): one leaves none. The gate's baselines are recorded again from base (main and the new perf.zig), and .scratch/daemon/base/pardes-perf-live rebuilt from it. +- **A blob's digest is a word, made once.** The walker's digest, taken at + every unit a replica is sent and every unit it replays, hashed every blob + whole each time: a 100 MB file was 5 ms a digest, two digests a unit, on + the user's own session. A blob (a field annotated `.blob`: a file's text + and line index, an undo snapshot, a register's values and joined text, a + file's location rows, the ones an edit dropped, a query's saved) is now + hashed once, its word kept by its address (walk.zig), and the digest + folds that word in. The rollback copy pins what the same annotation + names (`pinned` and `pinnedDeep` are gone). + - **Exact while every free drops the word:** every such blob is freed + raw, through `memory.freeRaw` or `freeUnfilled` (the pins needed raw + frees), and those drop its word, so an address used again is hashed + again. The first ReleaseFast harness run found one that did not: an + edit freed the old text with `rawFree` itself, the next text of the + same length came back at the same address, and the old word was folded + in (162 of 180 replica runs diverged, in `file.content`, named with + PARDES_REPLICA_TRACE); it goes through `freeUnfilled` now. A replica's + blobs born under a copy are never digested (a speculation records + none), so the epoch's own frees leave no word behind. A register's + values array was the one written in place; `put` now makes a new one. + ponytail: the word is kept by address, so a new free path that skips + those two misses it; a word carried in the struct beside its blob if + that bites again. + - **Written in place, or freed past its word:** a Debug build hashes a + blob's bytes at every digest and folds those in, and panics where the + word kept at that address and length is not their hash: a blob written + in place (which the pins forbid too) or freed without dropping its + word. The tests, the replicas harness and replay run Debug and go + through it (and pass); walk.zig's test writes a blob in place and sees + its kept word is no longer its hash. A release build (ReleaseSafe, the + user's own, and ReleaseFast) takes the word and never panics on a stale + one: at worst it shows as a digest divergence. Not recovered yet: a + replica that diverges records why (`Replica.diverged`) and takes no + more units; nothing resets it or joins it again. That is the remote + client's to add (a fresh join from the authority's dump), not a crash. + - Measured (ReleaseFast, alone on the perf cores; PARDES_DIGEST_BENCH=100 + zig build core-test -Dtest-filter="big file open"): with a 100 MB file + open, a unit of a key into it (two digests) went from p50 10.45 ms, + p99 41.6 ms to p50 24 us, p99 6.1 ms (the first, which makes the + file's word), and a digest from 5.18 ms to 10 us. The harness (20 seeds + x 120 inputs x 3 clients, ReleaseFast): rollback p99 at 30 ms went from + 9.5 to 2.6 ms (1.5 and 1.4 ms at 80 and 207 ms, about as before), copy + p99 0.27 ms (0.22 before, within the run's noise); none diverged, none + unequal, no delta wrong. ## Phase 6: upgrade notes diff --git a/src/File.zig b/src/File.zig index 48a996a4..7acf8dd6 100644 --- a/src/File.zig +++ b/src/File.zig @@ -30,6 +30,7 @@ const long_paint: usize = 16 << 10; /// Content and primary selection at one file edit boundary. Keeping only the /// primary avoids putting Text.max_selections ranges in every history entry. pub const Snapshot = struct { + pub const replica = .{ .blob = .{"content"} }; content: []u8, cur_row: i32, cur_col: i32, @@ -139,7 +140,11 @@ pub const History = struct { pub const State = struct { /// What the replay digest leaves out (src/walk.zig): what is made again /// from the text whenever it is wanted. - pub const replica = .{ .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" } }; + pub const replica = .{ + .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, + // Replaced whole at every edit (setContentSpan), never written. + .blob = .{ "content", "line_starts", "location_rows" }, + }; path: []u8, content: []u8, @@ -840,6 +845,7 @@ fn reportEdit(p: *Pardes, f: *State, new: []const u8) void { } pub const DroppedMarks = struct { + pub const replica = .{ .blob = .{"rows"} }; len: usize, hash: u64, rows: []locations.Row, @@ -908,8 +914,8 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { f.saved_len = f.content.len; } // Raw: `free` overwrites a safe build's freed memory, a whole file's - // worth per keystroke. - if (f.content.len > 0) p.gpa.rawFree(f.content, .of(u8), @returnAddress()); + // worth per keystroke; and its digest word goes (src/walk.zig). + pardes.memory.freeUnfilled(p.gpa, f.content); f.content = new; f.revision +%= 1; f.splice = .{ .revision = f.revision, .head = known.head, .tail = known.tail, .old_len = old_len }; diff --git a/src/Query.zig b/src/Query.zig index 8296aa80..49f58a0e 100644 --- a/src/Query.zig +++ b/src/Query.zig @@ -173,6 +173,7 @@ capped: bool = false, saved: ?Saved = null, pub const Saved = struct { + pub const replica = .{ .blob = .{"rows"} }; content: []u8, rows: []locations.Row, asked: []u8, diff --git a/src/Registers.zig b/src/Registers.zig index 760aff9a..6df7401d 100644 --- a/src/Registers.zig +++ b/src/Registers.zig @@ -12,11 +12,12 @@ const Registers = @This(); list: std.ArrayList(Reg) = .empty, last_search: u21 = '/', -/// A value and the joined text are replaced whole, never written in place, -/// so a replica's rollback copy pins them as it does a file's text -/// (src/rollback.zig `pinned`), and they are freed raw: a safe build's -/// free would write over one the copy still holds. +/// The values (their array too) and the joined text are replaced whole, +/// never written in place (`put` makes a new array), freed raw: blobs +/// (src/walk.zig), which a digest hashes once and a replica's rollback copy +/// pins as it does a file's text. pub const Reg = struct { + pub const replica = .{ .blob = .{ "values", "joined" } }; name: u21, /// gpa-owned, one per range, in document order values: [][]u8, @@ -36,7 +37,7 @@ pub fn deinit(r: *Registers, gpa: std.mem.Allocator) void { fn freeReg(gpa: std.mem.Allocator, reg: *Reg) void { for (reg.values) |v| freeRaw(gpa, v); - gpa.free(reg.values); + freeRaw(gpa, reg.values); if (reg.joined) |j| freeRaw(gpa, j); } @@ -65,19 +66,20 @@ pub fn put(r: *Registers, gpa: std.mem.Allocator, name: u21, bytes: []const u8, }; break :blk &r.list.items[r.list.items.len - 1]; }; - if (fresh or reg.values.len != n) { - const values = gpa.alloc([]u8, n) catch { - gpa.free(copy); - return; - }; - for (values) |*v| v.* = &.{}; - freeReg(gpa, reg); - reg.* = .{ .name = name, .values = values }; - } - freeRaw(gpa, reg.values[i]); - reg.values[i] = copy; - if (reg.joined) |j| freeRaw(gpa, j); - reg.joined = null; + // A new array, the old one's values moved into it but value `i`. + const values = gpa.alloc([]u8, n) catch { + gpa.free(copy); + return; + }; + const keep = !fresh and reg.values.len == n; + for (values, 0..) |*v, j| v.* = if (keep and j != i) reg.values[j] else &.{}; + values[i] = copy; + if (keep) { + freeRaw(gpa, reg.values[i]); + freeRaw(gpa, reg.values); + if (reg.joined) |j| freeRaw(gpa, j); + } else freeReg(gpa, reg); + reg.* = .{ .name = name, .values = values }; } /// The whole register as one text: its values joined by newlines, no diff --git a/src/memory.zig b/src/memory.zig index 1d082964..7adcf914 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -1,5 +1,6 @@ const std = @import("std"); const builtin = @import("builtin"); +const walk = @import("walk.zig"); const config = @import("pardes_config"); const board = config.platform == .esp32p4; @@ -418,7 +419,10 @@ pub fn dupeUnfilled(allocator: Allocator, bytes: []const u8) Allocator.Error![]u /// Frees without the safe-build overwrite `free` does, for text-sized buffers /// freed on every edit. pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { - if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); + if (bytes.len == 0) return; + // A blob's digest word goes with it (walk.zig). + walk.forget(@intFromPtr(bytes.ptr)); + allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); } /// `freeUnfilled` for a slice of any element: a text's line index, made @@ -427,7 +431,9 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { 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) allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); + if (bytes.len == 0) return; + walk.forget(@intFromPtr(bytes.ptr)); + allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); } /// Gives free memory back to the system, the arenas' and libc's, inside its diff --git a/src/replica.zig b/src/replica.zig index a96a056a..0b55a5bf 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -1011,3 +1011,54 @@ test "a delta applied under a speculation outlives its rollback: the terminal st const shown = a.core.panes[shell].?.rows; for (rows_a[rows_a.len - shown ..], rows_r[rows_r.len - shown ..]) |x, y| try std.testing.expectEqualStrings(x, y); } + +/// p50 and p99 of `samples`, sorted in place. +fn spread(samples: []u64) [2]u64 { + std.mem.sort(u64, samples, {}, std.sort.asc(u64)); + return .{ samples[samples.len / 2], samples[@min(samples.len - 1, samples.len * 99 / 100)] }; +} + +test "the authority's units with a big file open: its blobs hashed once (PARDES_DIGEST_BENCH=)" { + const arg = std.c.getenv("PARDES_DIGEST_BENCH") orelse return error.SkipZigTest; + const mb = std.fmt.parseInt(usize, std.mem.span(arg), 10) catch 100; + const gpa = std.heap.c_allocator; + const tmp = std.mem.span(std.c.getenv("TMPDIR") orelse "/tmp"); + var path_buf: [256]u8 = undefined; + const path = try std.fmt.bufPrintSentinel(&path_buf, "{s}/pardes-digest-bench.txt", .{tmp}, 0); + { + const fd = std.c.open(path, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(std.c.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = std.c.close(fd); + var line: [80]u8 = undefined; + var n: usize = 0; + var i: usize = 0; + while (n < mb << 20) : (i += 1) { + const text = try std.fmt.bufPrint(&line, "line {d:0>9} of a big file, as a log or a dump is\n", .{i}); + if (std.c.write(fd, text.ptr, text.len) != @as(isize, @intCast(text.len))) return error.WriteFailed; + n += text.len; + } + } + defer _ = std.c.unlink(path); + const a = try Authority.init(gpa, .{ .cols = 120, .rows = 40, .file = path }, TestHost.host(), true); + defer a.deinit(); + _ = try a.unit(0, 0); + var unit_ns: [40]u64 = undefined; + var digest_ns: [40]u64 = undefined; + for ([_]bool{ false, true }) |on| { + walk.blob_words_on = on; + defer walk.blob_words_on = true; + walk.forgetAll(); + for (&unit_ns, &digest_ns, 0..) |*u, *d, k| { + // A key into the file: a unit as a replica is sent it. + const t0 = nowNs(); + _ = try a.local(.{ .key = .{ .cp = if (k % 2 == 0) 'j' else 'k', .text = if (k % 2 == 0) "j" else "k" } }); + u.* = nowNs() - t0; + const t1 = nowNs(); + _ = digestOf(a); + d.* = nowNs() - t1; + } + const us = spread(&unit_ns); + const ds = spread(&digest_ns); + std.debug.print("{d} MB file, blobs {s}: a unit p50 {d} us p99 {d} us; a digest p50 {d} us p99 {d} us\n", .{ mb, if (on) "hashed once" else "hashed whole", us[0] / 1000, us[1] / 1000, ds[0] / 1000, ds[1] / 1000 }); + } +} diff --git a/src/rollback.zig b/src/rollback.zig index a7027da6..37fc481d 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -35,8 +35,8 @@ const Allocator = std.mem.Allocator; const Alignment = std.mem.Alignment; const Pardes = pardes.Pardes; -/// Blobs this long or longer (`pinned`) are pinned, not copied. Checked -/// unchanged in a safe build when the copy goes. +/// Blobs (walk.blob: fields annotated `.blob`) this long or longer are +/// pinned, not copied. Checked unchanged in a safe build when the copy goes. const blob_min = 4096; const checked = builtin.mode == .debug or builtin.mode == .safe; @@ -198,8 +198,6 @@ pub const Copy = struct { /// of the blobs: a file's text or an undo snapshot's. where: []const u8 = "", pinnable: bool = false, - /// Whether it is a blob of rows that own allocations of their own. - deep: bool = false, const Region = struct { addr: usize, off: usize, len: usize }; const Pin = struct { addr: usize, len: usize, hash: u64, where: []const u8 }; @@ -344,8 +342,7 @@ pub const Copy = struct { if (attr.@"comptime" or comptime (annotated(T, "authority", name) or ((annotated(T, "local", name) or annotated(T, "derived", name)) and unsaved(name)))) continue; if (comptime opaqueTo(F)) continue; c.where = @typeName(T) ++ "." ++ name; - c.pinnable = comptime pinned(T, name); - c.deep = comptime pinnedDeep(T, name); + c.pinnable = comptime walk.blob(T, name); if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { const len = comptime walk.lengthOf(T, name).?; if (comptime heapIn(@typeInfo(F).array.child, 0)) for (@field(v, name)[0..walk.lengthIn(v, len)]) |*e| try c.visit(@typeInfo(F).array.child, e); @@ -398,9 +395,8 @@ pub const Copy = struct { if (s.len == 0) return; const addr = @intFromPtr(s.ptr); if (try c.reached([]const E, addr)) return; - const flat = comptime !heapIn(E, 0); - if ((if (flat) c.pinnable else c.deep) and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { - // A blob of rows with allocations of their own pinned whole: + if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { + // A blob of rows with allocations of their own is pinned whole: // they are as immutable as it, and kept alive with it. const bytes = std.mem.sliceAsBytes(s); try c.pins.append(c.meta, .{ .addr = addr, .len = bytes.len, .hash = if (checked) std.hash.Wyhash.hash(0, bytes) else 0, .where = c.where }); @@ -411,28 +407,6 @@ pub const Copy = struct { } }; -/// The blobs: what an edit puts in place of its predecessor, never writes -/// (File.setContentSpan), and frees raw (memory.freeUnfilled, freeRaw). -fn pinned(comptime T: type, comptime name: []const u8) bool { - const File = pardes.panes.File; - return (T == File.State and (std.mem.eql(u8, name, "content") or std.mem.eql(u8, name, "line_starts"))) or - (T == File.Snapshot and std.mem.eql(u8, name, "content")) or - // A register's values and joined text: a yank of a terminal's whole - // grid is megabytes, which every speculation would otherwise copy. - (T == pardes.Registers.Reg and (std.mem.eql(u8, name, "values") or std.mem.eql(u8, name, "joined"))); -} - -/// Blobs of rows that own allocations of their own (a location's path, its -/// colours), the array and they replaced whole and never written, freed raw -/// (locations.freeRows): a file's location rows (5 MB after a flood of -/// search results), the ones an edit dropped, a query's saved. -fn pinnedDeep(comptime T: type, comptime name: []const u8) bool { - const File = pardes.panes.File; - return (T == File.State and std.mem.eql(u8, name, "location_rows")) or - (T == File.DroppedMarks and std.mem.eql(u8, name, "rows")) or - (T == pardes.panes.Query.Saved and std.mem.eql(u8, name, "rows")); -} - fn annotatedStruct(comptime T: type) bool { return @typeInfo(T) == .@"struct" and @hasDecl(T, "replica"); } 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); +} -- cgit v1.3 From c892cf0c3246b6c41f8f67810d360c5ea0ff66ef Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Fri, 30 Oct 2026 02:34:25 -0300 Subject: a replica client's join costs the session's step its mutable state alone: the dump leaves the blobs out (walk.zig `Dump.deferred`: a `.blob`'s texts of 4 KiB and up, noted where they go) and its terminals' emulators (a size: the first delta brings each), the client's writer thread writes the welcome and the dump with the blobs put back in place, and each blob is pinned until written (memory.zig `pin`: its free put off); the texts the session never digested are hashed first on a thread of their own (walk.zig `unhashed`, `makeWords`), the join waiting a boundary for them The client is unchanged: what it reads is the dump `dumpBytes` makes, byte for byte (a test splices one and compares). ReleaseFast, the session's worst boundary while three clients join one after another (`t2/join2.py`), before and after: typical (4.1 MB of files, 1 MB of scrollback, an 8.1 MB dump) 12.4 to 1.6 ms; big (38.6 MB, 8 MB, 76 MB) 51.3 to 1.5 ms; a 100 MB file open beside typical's (254 MB) 172.5 to 1.6 ms. Of the dump the step makes 113 to 122 KB. PARDES_REPLICA_STATS says each join's time and the state's size. Co-Authored-By: Claude Opus 5.5 --- src/dump.zig | 19 +++++ src/memory.zig | 79 +++++++++++++++++++++ src/replica.zig | 207 ++++++++++++++++++++++++++++++++++++++++++++++++------- src/terminal.zig | 49 ++++++++----- src/walk.zig | 55 +++++++++++++++ 5 files changed, 365 insertions(+), 44 deletions(-) (limited to 'src/memory.zig') diff --git a/src/dump.zig b/src/dump.zig index 152495e2..c64f83c4 100644 --- a/src/dump.zig +++ b/src/dump.zig @@ -174,8 +174,27 @@ pub fn dumpState(p: *Pardes) !void { /// The session as a dump, gpa-owned. pub fn dumpBytes(p: *Pardes) ![]u8 { + return dumpWith(p, null); +} + +/// A dump for a screen-state replica's join (src/replica.zig): its blobs' +/// bytes left out and noted in `deferred` (they are the session's, alive +/// while pinned: memory.zig `pin`), its terminals' emulators left out (the +/// first delta brings each afresh). What is left is the session's mutable +/// state, made in its step. +pub fn dumpJoin(p: *Pardes, deferred: *std.ArrayListUnmanaged(walk.Deferred)) ![]u8 { + slim_terminals = true; + defer slim_terminals = false; + return dumpWith(p, deferred); +} + +/// `dumpJoin`'s: a terminal dumps its size, not its emulator. +pub var slim_terminals = false; + +fn dumpWith(p: *Pardes, deferred: ?*std.ArrayListUnmanaged(walk.Deferred)) ![]u8 { var d = try Session.init(p.gpa); errdefer d.deinit(); + d.deferred = deferred; try d.put(Pardes, p); const mounts: []const filesystem.Mount = p.fs.mounts.items; try d.put([]const filesystem.Mount, &mounts); diff --git a/src/memory.zig b/src/memory.zig index 7adcf914..cd29308f 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -422,6 +422,7 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { 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(u8))) return; allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); } @@ -433,9 +434,72 @@ pub fn freeRaw(allocator: Allocator, items: anytype) void { const bytes = std.mem.sliceAsBytes(items); if (bytes.len == 0) return; walk.forget(@intFromPtr(bytes.ptr)); + if (pinned(allocator, bytes, .of(E))) return; allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); } +// ---- a join's pins (src/replica.zig) ---- +// +// A replica client's join dumps the session's mutable state in its step and +// leaves its blobs out (walk.Deferred); its writer thread streams them after. +// A blob is never written in place and is freed raw (above), so until the +// writer has sent it, its free is put off: `pin` it, `unpin` it after. +var pins_lock: std.atomic.Value(bool) = .init(false); +var pins: std.AutoHashMapUnmanaged(usize, u32) = .empty; +var pin_count: std.atomic.Value(usize) = .init(0); +const PutOff = struct { allocator: Allocator, bytes: []const u8, alignment: std.mem.Alignment }; +var put_off: std.ArrayListUnmanaged(PutOff) = .empty; + +fn lockPins() void { + while (pins_lock.cmpxchgWeak(false, true, .acquire, .monotonic) != null) std.atomic.spinLoopHint(); +} + +/// The blob at `bytes.ptr` kept alive until it is unpinned as many times. +pub fn pin(bytes: []const u8) void { + lockPins(); + defer pins_lock.store(false, .release); + const got = pins.getOrPut(std.heap.page_allocator, @intFromPtr(bytes.ptr)) catch return; + got.value_ptr.* = if (got.found_existing) got.value_ptr.* + 1 else 1; + pin_count.store(pins.count(), .release); +} + +/// One pin of the blob at `bytes.ptr` let go: its free, put off, made now +/// the last one goes. +pub fn unpin(bytes: []const u8) void { + const addr = @intFromPtr(bytes.ptr); + lockPins(); + const n = pins.getPtr(addr) orelse { + pins_lock.store(false, .release); + return; + }; + n.* -= 1; + var due: ?PutOff = null; + if (n.* == 0) { + _ = pins.remove(addr); + pin_count.store(pins.count(), .release); + for (put_off.items, 0..) |f, i| if (@intFromPtr(f.bytes.ptr) == addr) { + due = put_off.swapRemove(i); + break; + }; + } + 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()); + } +} + +/// Whether the free of `bytes` is put off (it is pinned). +fn pinned(allocator: Allocator, bytes: []const u8, alignment: std.mem.Alignment) bool { + if (pin_count.load(.acquire) == 0) return false; + lockPins(); + defer pins_lock.store(false, .release); + if (!pins.contains(@intFromPtr(bytes.ptr))) return false; + put_off.append(std.heap.page_allocator, .{ .allocator = allocator, .bytes = bytes, .alignment = alignment }) catch return false; + return true; +} + /// Gives free memory back to the system, the arenas' and libc's, inside its /// heap too: after a big result is formatted or a big pane torn down, the /// tree-sitter arena kept 73 MiB of emptied buckets resident and glibc what @@ -568,3 +632,18 @@ test "memory limits preserve desktop capacities" { try std.testing.expectEqual(256 * MiB, limits.arena.image); try std.testing.expectEqual(if (config.mupdf) 512 * MiB else 64 * KiB, limits.arena.pdf); } + +test "a pinned blob's free is put off until its last pin goes" { + const gpa = std.testing.allocator; + const b = try gpa.alloc(u8, 8192); + @memset(b, 7); + pin(b); + pin(b); + freeUnfilled(gpa, b); + // Still the blob's: a join's writer reads it. + try std.testing.expectEqual(@as(u8, 7), b[100]); + unpin(b); + try std.testing.expectEqual(@as(u8, 7), b[8000]); + // The last pin: freed now (the testing allocator says if not). + unpin(b); +} diff --git a/src/replica.zig b/src/replica.zig index 8d8d47c5..2e14cb6f 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -1071,6 +1071,17 @@ fn writeAll(fd: c_int, bytes: []const u8) bool { return true; } +/// `bytes` as dump pieces (1 MiB at most each). +fn writePieces(fd: c_int, bytes: []const u8) bool { + var at: usize = 0; + while (at < bytes.len) : (at += dump_piece) { + const piece = bytes[at..@min(bytes.len, at + dump_piece)]; + const head = wire.header(@backingInt(wire.ServerTag.dump), piece.len); + if (!writeAll(fd, &head) or !writeAll(fd, piece)) return false; + } + return true; +} + fn readSome(fd: c_int, buf: []u8) usize { while (true) { const n = libc.read(fd, buf.ptr, buf.len); @@ -1144,6 +1155,24 @@ pub const Peer = struct { cut: bool = false, /// Its writer has ended (what it was sent, written). done: std.atomic.Value(bool) = .init(false), + /// Its join, which its writer writes before what it is sent: the + /// welcome, then the dump with the session's blobs put back where they + /// go, pinned until written (memory.zig `pin`). The core's allocator's. + welcome: [wire.hello_max + 64]u8 = undefined, + welcome_len: usize = 0, + dump: []u8 = &.{}, + blobs: std.ArrayListUnmanaged(walk.Deferred) = .empty, + dump_gpa: Allocator = undefined, + + fn writeJoin(peer: *Peer) bool { + if (!writeAll(peer.fd, peer.welcome[0..peer.welcome_len])) return false; + var pos: usize = 0; + for (peer.blobs.items) |b| { + if (!writePieces(peer.fd, peer.dump[pos..b.at]) or !writePieces(peer.fd, b.bytes)) return false; + pos = b.at; + } + return writePieces(peer.fd, peer.dump[pos..]); + } /// `parts` queued for it, in order; never waits. A client whose queue /// passes its limit is cut off: its link is shut down, and its reader @@ -1174,6 +1203,12 @@ pub const Peer = struct { fn writeLoop(peer: *Peer) void { const io = peer.peers.io; defer peer.done.store(true, .release); + if (!peer.writeJoin()) { + _ = libc.shutdown(peer.fd, 2); + return; + } + // Its pins let go at the next boundary. + peer.peers.post(.{ .joined = peer }); while (true) { peer.lock.lockUncancelable(io); while (peer.out.items.len == 0 and !peer.closing and !peer.cut) peer.cond.waitUncancelable(io, &peer.lock); @@ -1261,7 +1296,10 @@ pub const Peers = struct { alone_unattended: bool = false, /// The worst a join cost the session's step, and the last one's dump. join_ns: u64 = 0, + each_join: std.ArrayListUnmanaged(u64) = .empty, dump_bytes: usize = 0, + /// ...of it the state the step dumped (the rest, blobs, the writer's). + state_bytes: usize = 0, /// What each client input cost the session (its step, its unit sent), /// and each boundary (its pump's unit sent, what came taken in), ns: /// PARDES_REPLICA_STATS writes them at the session's end. @@ -1273,8 +1311,14 @@ pub const Peers = struct { /// it records: what each was sent. screens: Screens = undefined, msgs: std.ArrayListUnmanaged([]u8) = .empty, - - pub const Note = union(enum) { join: c_int, input: Msg, screen: Msg, gone: *Peer, check: *Peer }; + /// Clients waiting to join while the session's texts are hashed + /// (`joins`), the texts and the thread hashing them. + held: std.ArrayListUnmanaged(c_int) = .empty, + texts: std.ArrayListUnmanaged([]const u8) = .empty, + hasher: ?std.Thread = null, + rounds: u8 = 0, + + pub const Note = union(enum) { join: c_int, input: Msg, screen: Msg, gone: *Peer, check: *Peer, joined: *Peer, hashed }; pub const Msg = struct { peer: *Peer, msg: []u8 }; pub fn count(ps: *const Peers) usize { @@ -1290,7 +1334,7 @@ pub const Peers = struct { switch (note) { .join => |fd| _ = libc.close(fd), .input, .screen => |in| ps.gpa.free(in.msg), - .gone, .check => {}, + .gone, .check, .joined, .hashed => {}, } return; }; @@ -1344,7 +1388,17 @@ pub const Peers = struct { ps.mail.store(false, .release); ps.lock.unlock(ps.io); for (ps.taken.items) |note| switch (note) { - .join => |fd| ps.join(core, fd), + .join => |fd| { + ps.held.append(ps.gpa, fd) catch { + refuse(fd, "out of memory"); + continue; + }; + ps.joins(core); + }, + .hashed => { + ps.unhashedDone(); + ps.joins(core); + }, .input => |in| { ps.input(core, in.peer, in.msg); ps.gpa.free(in.msg); @@ -1357,6 +1411,7 @@ pub const Peers = struct { in.peer.send(&.{ &head, reply }); }, .gone => |peer| ps.leave(core, peer), + .joined => |peer| released(peer), .check => |peer| { var out: [16]u8 = undefined; peer.send(&.{wire.encodeServer(&out, .{ .check = tape.digestOf(core) }) catch unreachable}); @@ -1410,9 +1465,48 @@ pub const Peers = struct { _ = libc.close(fd); } + /// 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) |fd| ps.join(core, fd); + 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, fd: c_int) void { const t0 = nowNs(); - defer ps.join_ns = @max(ps.join_ns, nowNs() - t0); + defer { + ps.join_ns = @max(ps.join_ns, nowNs() - t0); + ps.each_join.append(ps.gpa, nowNs() - t0) catch {}; + } const slot = for (&ps.list) |*s| { if (s.* == null) break s; } else return refuse(fd, "that session has as many clients as it takes"); @@ -1440,7 +1534,12 @@ pub const Peers = struct { core.undrawn |= @as(u8, 1) << @intCast(k); ps.seq += 1; ps.unit(0, ps.seq); - const bytes = pardes.dump.dumpBytes(core) catch |err| { + // The session's mutable state, dumped now; its blobs (file texts, + // undo, registers) left out, pinned, and streamed by the client's + // writer thread: the step pays for the state, not for the text. + var blobs: std.ArrayListUnmanaged(walk.Deferred) = .empty; + const bytes = pardes.dump.dumpJoin(core, &blobs) catch |err| { + blobs.deinit(core.gpa); core.undrawn &= ~(@as(u8, 1) << @intCast(k)); core.closeView(k); ps.unit(0, ps.seq); @@ -1448,28 +1547,29 @@ pub const Peers = struct { var why: [96]u8 = undefined; return refuse(fd, std.fmt.bufPrint(&why, "that session could not be dumped: {t}", .{err}) catch "that session could not be dumped"); }; - // The core's, as a Dump's is. - defer core.gpa.free(bytes); - ps.dump_bytes = bytes.len; + var whole = bytes.len; + for (blobs.items) |b| { + pardes.memory.pin(b.bytes); + whole += b.bytes.len; + } + ps.dump_bytes = whole; + ps.state_bytes = bytes.len; // The joiner's core is the dump's: the host this tape wraps, and // what the host wrote in the core, are said again at the next input. tape.resync(&ps.t); - const peer = ps.gpa.create(Peer) catch return refuse(fd, "out of memory"); + const peer = ps.gpa.create(Peer) catch { + for (blobs.items) |b| pardes.memory.unpin(b.bytes); + blobs.deinit(core.gpa); + core.gpa.free(bytes); + return refuse(fd, "out of memory"); + }; if (std.c.getenv("PARDES_REPLICA_LAG_KB")) |kb| lag_max = (std.fmt.parseInt(usize, std.mem.span(kb), 10) catch 64 << 10) << 10; - peer.* = .{ .peers = ps, .fd = fd, .id = ps.next_id, .view = k, .limit = bytes.len + lag_max }; + peer.* = .{ .peers = ps, .fd = fd, .id = ps.next_id, .view = k, .limit = lag_max, .dump = bytes, .blobs = blobs, .dump_gpa = core.gpa }; ps.next_id +%= 1; if (ps.next_id == 0) ps.next_id = 1; - var out: [wire.hello_max + 64]u8 = undefined; // The session's digest as dumped, for the joiner to check its load by. const digest = tape.digestOf(core); - const welcome = wire.encodeServer(&out, .{ .welcome = .{ .pid = @intCast(libc.getpid()), .session = ps.name[0..@min(ps.name.len, wire.max_name)], .client = peer.id, .view = k, .dump_len = bytes.len, .gmtoff = gmtoff(), .digest = digest, .semantics = wire.semantics } }) catch unreachable; - peer.send(&.{welcome}); - var at: usize = 0; - while (at < bytes.len) : (at += dump_piece) { - const piece = bytes[at..@min(bytes.len, at + dump_piece)]; - const head = wire.header(@backingInt(wire.ServerTag.dump), piece.len); - peer.send(&.{ &head, piece }); - } + peer.welcome_len = (wire.encodeServer(&peer.welcome, .{ .welcome = .{ .pid = @intCast(libc.getpid()), .session = ps.name[0..@min(ps.name.len, wire.max_name)], .client = peer.id, .view = k, .dump_len = whole, .gmtoff = gmtoff(), .digest = digest, .semantics = wire.semantics } }) catch unreachable).len; peer.writer = std.Thread.spawn(.{}, Peer.writeLoop, .{peer}) catch null; peer.reader = std.Thread.spawn(.{}, Peer.readLoop, .{peer}) catch null; if (peer.writer == null or peer.reader == null) { @@ -1485,7 +1585,7 @@ pub const Peers = struct { peer.sid = sid; ps.screensTo(core, peer, .flush); } else |_| _ = libc.shutdown(fd, 2); - log.info("client {d} joined '{s}' as view {d}: a {d} KB dump in {d} us", .{ peer.id, ps.name, k, bytes.len >> 10, (nowNs() - t0) / 1000 }); + log.info("client {d} joined '{s}' as view {d}: a {d} KB dump ({d} KB of state) in {d} us", .{ peer.id, ps.name, k, whole >> 10, bytes.len >> 10, (nowNs() - t0) / 1000 }); if (std.c.getenv("PARDES_REPLICA_TRACE") != null) std.debug.print("session: client {d} joined after unit {d}\n", .{ peer.id, ps.seq }); } @@ -1514,6 +1614,7 @@ pub const Peers = struct { _ = libc.shutdown(peer.fd, 2); if (peer.writer) |w| w.join(); if (peer.reader) |r| r.join(); + released(peer); _ = libc.close(peer.fd); peer.out.deinit(ps.gpa); peer.sending.deinit(ps.gpa); @@ -1523,8 +1624,8 @@ pub const Peers = struct { while (i < ps.inbox.items.len) { const mine = switch (ps.inbox.items[i]) { .input, .screen => |in| in.peer == peer, - .gone, .check => |p| p == peer, - .join => false, + .gone, .check, .joined => |p| p == peer, + .join, .hashed => false, }; if (!mine) { i += 1; @@ -1567,6 +1668,15 @@ pub const Peers = struct { ps.dropAll(core); } + /// A join's dump and pins let go: written, or its client gone. + fn released(peer: *Peer) void { + for (peer.blobs.items) |b| pardes.memory.unpin(b.bytes); + peer.blobs.deinit(peer.dump_gpa); + peer.blobs = .empty; + if (peer.dump.len > 0) peer.dump_gpa.free(peer.dump); + peer.dump = &.{}; + } + /// Detach typed in client view `k`'s: its link ends (its reader says /// it is gone, and the next boundary lets it go). pub fn detach(ps: *Peers, k: u8) bool { @@ -1589,6 +1699,10 @@ pub const Peers = struct { /// Every client let go (the session's end, a Restore): each sees its /// link end. pub fn dropAll(ps: *Peers, core: *Pardes) void { + ps.unhashedDone(); + for (ps.held.items) |fd| _ = libc.close(fd); + ps.held.clearRetainingCapacity(); + ps.rounds = 0; for (&ps.list) |*slot| if (slot.*) |peer| { slot.* = null; core.undrawn &= ~(@as(u8, 1) << @intCast(peer.view)); @@ -1601,7 +1715,7 @@ pub const Peers = struct { for (ps.inbox.items) |note| switch (note) { .join => |fd| _ = libc.close(fd), .input, .screen => |in| ps.gpa.free(in.msg), - .gone, .check => {}, + .gone, .check, .joined, .hashed => {}, }; ps.inbox.clearRetainingCapacity(); ps.lock.unlock(ps.io); @@ -1615,20 +1729,29 @@ 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); } fn writeStats(ps: *Peers, path: []const u8) void { var buf: [400]u8 = undefined; - const line = std.fmt.bufPrint(&buf, "session inputs {d} input_us {d}/{d}/{d} boundaries {d} boundary_us {d}/{d}/{d} join_us {d} dump_kb {d} cut {d}\n", .{ + const line = std.fmt.bufPrint(&buf, "session inputs {d} input_us {d}/{d}/{d} boundaries {d} boundary_us {d}/{d}/{d} join_us {d} dump_kb {d} state_kb {d} cut {d}\n", .{ ps.input_ns.items.len, pctOf(ps.input_ns.items, 50) / 1000, pctOf(ps.input_ns.items, 99) / 1000, pctOf(ps.input_ns.items, 100) / 1000, ps.boundary_ns.items.len, pctOf(ps.boundary_ns.items, 50) / 1000, pctOf(ps.boundary_ns.items, 99) / 1000, pctOf(ps.boundary_ns.items, 100) / 1000, - ps.join_ns / 1000, ps.dump_bytes >> 10, ps.cut, + ps.join_ns / 1000, ps.dump_bytes >> 10, ps.state_bytes >> 10, ps.cut, }) catch return; var z: [4096]u8 = undefined; const pz = std.fmt.bufPrintSentinel(&z, "{s}", .{path}, 0) catch return; const fd = libc.open(pz, .{ .ACCMODE = .WRONLY, .CREAT = true, .APPEND = true, .CLOEXEC = true }, @as(libc.mode_t, 0o644)); if (fd < 0) return; _ = libc.write(fd, line.ptr, line.len); + var each: [400]u8 = undefined; + var w: std.Io.Writer = .fixed(&each); + w.writeAll("session joins_us") catch {}; + for (ps.each_join.items) |ns| w.print(" {d}", .{ns / 1000}) catch {}; + w.writeAll("\n") catch {}; + _ = libc.write(fd, w.buffered().ptr, w.buffered().len); _ = libc.close(fd); } }; @@ -2052,3 +2175,35 @@ test "a replica joined from the session's dump replays the units after it" { try std.testing.expect(r.quiet()); try std.testing.expectEqual(digestOf(a), r.digest()); } + +test "a join's dump, its blobs put back where they go, is the session's dump" { + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false); + defer a.deinit(); + const text = try gpa.alloc(u8, 20000); + defer gpa.free(text); + @memset(text, 'x'); + _ = try a.local(.{ .key = .{ .cp = 'i', .text = "i" } }); + _ = try a.local(.{ .paste = text }); + _ = try a.local(.{ .key = .{ .cp = pardes.Key.escape, .text = "" } }); + const was = Stepping.begin(&a.t, null); + defer was.end(); + const whole = try pardes.dump.dumpBytes(a.core); + defer a.core.gpa.free(whole); + var blobs: std.ArrayListUnmanaged(walk.Deferred) = .empty; + defer blobs.deinit(a.core.gpa); + const state = try pardes.dump.dumpJoin(a.core, &blobs); + defer a.core.gpa.free(state); + try std.testing.expect(blobs.items.len > 0); + try std.testing.expect(state.len + 20000 <= whole.len); + var joined: std.ArrayListUnmanaged(u8) = .empty; + defer joined.deinit(gpa); + var pos: usize = 0; + for (blobs.items) |b| { + try joined.appendSlice(gpa, state[pos..b.at]); + try joined.appendSlice(gpa, b.bytes); + pos = b.at; + } + try joined.appendSlice(gpa, state[pos..]); + try std.testing.expectEqualSlices(u8, whole, joined.items); +} diff --git a/src/terminal.zig b/src/terminal.zig index 2bc96a6e..42268f0a 100644 --- a/src/terminal.zig +++ b/src/terminal.zig @@ -259,6 +259,9 @@ pub const State = struct { defer gpa.free(bytes); try w.writeAll(std.mem.asBytes(&@as(u64, bytes.len))); try w.writeAll(bytes); + // A join's (dump.zig `dumpJoin`): its size alone, an emulator made + // afresh there, which its first delta replaces. + if (pardes.dump.slim_terminals) return w.writeAll(std.mem.asBytes(&[2]u16{ s.vt.cols, s.vt.rows })); try ghostty_vt.snapshot.encode(gpa, w, &s.vt, .{ .continuation = .ground }); } @@ -283,12 +286,17 @@ pub const State = struct { defer arena.deinit(); const parts = try pardes.walk.load(Parts, arena.allocator(), bytes[8..][0..n], null); var reader: std.Io.Reader = .fixed(bytes[8 + n ..]); - var decoded = try ghostty_vt.snapshot.decodeExact(gpa, terminalIo(), &reader, .{ - .max_continuation_bytes = 0, - .kitty_image_storage_limit = if (images_enabled) TerminalImages.storage_limit else 0, - }); - defer decoded.deinit(gpa); - out.* = .{ .gpa = gpa, .vt = decoded.toOwned(), .stream = undefined }; + if (reader.buffer.len == 4) { + const size = std.mem.bytesToValue([2]u16, bytes[8 + n ..][0..4]); + out.* = .{ .gpa = gpa, .vt = try emulator(gpa, @max(1, size[0]), @max(1, size[1])), .stream = undefined }; + } else { + var decoded = try ghostty_vt.snapshot.decodeExact(gpa, terminalIo(), &reader, .{ + .max_continuation_bytes = 0, + .kitty_image_storage_limit = if (images_enabled) TerminalImages.storage_limit else 0, + }); + defer decoded.deinit(gpa); + out.* = .{ .gpa = gpa, .vt = decoded.toOwned(), .stream = undefined }; + } if (comptime images_enabled) inline for (.{ .primary, .alternate }) |key| { if (out.vt.screens.get(key)) |screen| screen.kitty_images.image_limits = .allWithTempDir(tempDir()); }; @@ -846,18 +854,9 @@ pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void { pane.terminal = null; } -/// Allocate the live emulator half of a terminal pane. Slot ownership, serial -/// assignment, and spawn effects remain core lifecycle invariants. -pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { - if (authorityOnly()) return error.OutOfMemory; - const pane = try createDoc(gpa, cols, rows); - errdefer gpa.destroy(pane); - if (comptime !enabled) return pane; - const own = if (pardes.tape.screenReplica()) emulator_gpa else gpa; - const state = try own.create(State); - errdefer own.destroy(state); - state.gpa = own; - state.vt = try ghostty_vt.Terminal.init(terminalIo(), own, .{ +/// A terminal pane's emulator, `cols` by `rows`, as `create` makes one. +fn emulator(gpa: std.mem.Allocator, cols: u16, rows: u16) !ghostty_vt.Terminal { + return ghostty_vt.Terminal.init(terminalIo(), gpa, .{ .cols = cols, .rows = rows, .max_scrollback_bytes = 16 * 1024 * 1024, @@ -870,6 +869,20 @@ pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { // it could send itself: it runs as the user, under pardes. .kitty_image_loading_limits = if (images_enabled) .allWithTempDir(tempDir()) else if (@FieldType(ghostty_vt.Terminal.Options, "kitty_image_loading_limits") == void) {} else .direct, }); +} + +/// Allocate the live emulator half of a terminal pane. Slot ownership, serial +/// assignment, and spawn effects remain core lifecycle invariants. +pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { + if (authorityOnly()) return error.OutOfMemory; + const pane = try createDoc(gpa, cols, rows); + errdefer gpa.destroy(pane); + if (comptime !enabled) return pane; + const own = if (pardes.tape.screenReplica()) emulator_gpa else gpa; + const state = try own.create(State); + errdefer own.destroy(state); + state.gpa = own; + state.vt = try emulator(own, cols, rows); state.stream = .init(.{ .handler = .{ .inner = state.vt.vtHandler() }, .allocator = own }); state.reply_len = 0; state.changes = 0; diff --git a/src/walk.zig b/src/walk.zig index 2dc0a721..d0d20e8a 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -112,6 +112,10 @@ fn hashBlob(comptime E: type, items: []const E, h: *Hasher) void { break :kept if (b.len == items.len) b.word else null; } else null; if (!rehash) if (kept) |w| break :word w; + 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); @@ -130,6 +134,37 @@ fn hashBlob(comptime E: type, items: []const E, h: *Hasher) void { 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; + +/// 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 unlockBlobs(); + 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); @@ -801,6 +836,9 @@ fn tableOf(comptime types: []const type) []const u8 { return Once.bytes; } +/// A blob's bytes a dump left out (`Dump.deferred`): they go at `at`. +pub const Deferred = struct { at: usize, bytes: []const u8 }; + /// Writes a dump of `roots`' values, one `put` each in order. pub fn Dump(comptime roots: []const type) type { return struct { @@ -811,6 +849,13 @@ pub fn Dump(comptime roots: []const type) type { out: std.Io.Writer.Allocating, memo: std.AutoHashMapUnmanaged(Key, u32) = .empty, shared: u32 = 0, + /// Set: a `.blob`'s bytes (of `blob_min` and up) are not written but + /// noted, where they go and what they are; the dump with them put + /// back in place is the dump. A replica's join streams them from + /// its writer thread (src/replica.zig), the session's step paying + /// for the rest alone. + deferred: ?*std.ArrayListUnmanaged(Deferred) = null, + in_blob: bool = false, const Key = struct { addr: usize, len: usize, ty: u32 }; @@ -893,6 +938,13 @@ pub fn Dump(comptime roots: []const type) type { .slice => { const E = @typeInfo(T).pointer.child; if (try d.seen(T, @intFromPtr(v.ptr), v.len)) return; + if (comptime flat(E)) if (d.in_blob) if (d.deferred) |later| { + const bytes = std.mem.sliceAsBytes(v.*); + if (bytes.len >= blob_min) { + try w.writeAll(std.mem.asBytes(&@as(u64, v.len))); + return later.append(d.gpa, .{ .at = d.out.writer.end, .bytes = bytes }); + } + }; try d.items(E, v.*); }, .array => { @@ -905,6 +957,9 @@ pub fn Dump(comptime roots: []const type) type { const packed_struct = comptime @typeInfo(T).@"struct".layout == .@"packed"; inline for (comptime dumpFields(T)) |name| { const F = @FieldType(T, name); + const was = d.in_blob; + d.in_blob = was or comptime blob(T, name); + defer d.in_blob = was; if (comptime cutArray(T, name)) { const all = &@field(v, name); try d.items(@typeInfo(F).array.child, all[0..@min(all.len, lengthIn(v, comptime lengthOf(T, name).?))]); -- cgit v1.3