//! 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); }