summaryrefslogtreecommitdiff
path: root/test/replicas.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-29 18:19:13 -0300
committerGabriel Schneider <[email protected]>2026-10-29 20:19:19 -0300
commit3b57a72becd6dd6700d996c9c5c000e1cb53e076 (patch)
tree58e59aefe6ae067d95ce4ddf94e8155a9edd3b5a /test/replicas.zig
parent8bad8e3701716a5f2d82d8255a39f3743b13fb96 (diff)
downloadpardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.tar.gz
pardes-3b57a72becd6dd6700d996c9c5c000e1cb53e076.zip
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 <[email protected]>
Diffstat (limited to 'test/replicas.zig')
-rw-r--r--test/replicas.zig327
1 files changed, 327 insertions, 0 deletions
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);
+}