summaryrefslogtreecommitdiff
path: root/src/replica.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/replica.zig')
-rw-r--r--src/replica.zig578
1 files changed, 578 insertions, 0 deletions
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);
+}