summaryrefslogtreecommitdiff
path: root/src/tape.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 /src/tape.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 'src/tape.zig')
-rw-r--r--src/tape.zig236
1 files changed, 222 insertions, 14 deletions
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.