//! 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 screen_state = @import("screen_state.zig"); const terminal = pardes.panes.terminal; 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); } /// A unit's head: its origin and seq, then the authority's clocks when it /// was made (realtime and monotonic, ns), which a replica's guesses of the /// session's clock start from. const unit_head = head_len + 16; pub const Unit = struct { origin: u16, seq: u32, real_ns: i64 = 0, mono_ns: i64 = 0, tape: []const u8 }; pub fn parseUnit(msg: []const u8) ?Unit { if (msg.len < unit_head) return null; return .{ .origin = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .real_ns = std.mem.readInt(i64, msg[6..14], .little), .mono_ns = std.mem.readInt(i64, msg[14..22], .little), .tape = msg[unit_head..], }; } fn clockNs(id: std.c.clockid_t) i64 { var ts: std.c.timespec = undefined; if (std.c.clock_gettime(id, &ts) != 0) return 0; return @as(i64, ts.sec) * std.time.ns_per_s + ts.nsec; } fn unitHeader(buf: []u8, origin: u16, seq: u32) void { header(buf, origin, seq); std.mem.writeInt(i64, buf[6..14], clockNs(.REALTIME), .little); std.mem.writeInt(i64, buf[14..22], clockNs(.MONOTONIC), .little); } 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 `p`th percentile of `samples` (sorted here); 100 is the worst. fn pctOf(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)]; } // ---- 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), /// Steps of its own taken since the last unit (`output`): one unit, /// `pending`, sent before the next input it steps and at a frame. batched: u32 = 0, /// A session booted with `opts`; `unit` is its first, which a replica /// is made from. /// `screens`: its terminals cross as screen state (`Screens`), not as /// their pty's bytes. pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host, screens: bool) !*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 }; a.t.screen_state = screens; // One word a digest: every pty read is a unit. a.t.whole_digest = screens and std.c.getenv("PARDES_REPLICA_TRACE") == null; 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, unit_head); unitHeader(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 { std.debug.assert(a.batched == 0); // `pending` first: units keep the order steps took a.apply(ev); a.seq += 1; return a.unit(0, a.seq); } /// A step of its own (a pty's output) into the open batch: under a /// flood a replica gets a unit a frame, not one a read (each unit of the /// authority's rolls back a replica's pending inputs), and its digest /// once a unit. pub fn output(a: *Authority, ev: pardes.Event) void { a.t.no_digest = true; defer a.t.no_digest = false; a.apply(ev); a.batched += 1; } /// The open batch as a unit, or null: what the host sends before it /// steps any other input, and once a frame. pub fn pending(a: *Authority) !?[]const u8 { if (a.batched == 0) return null; a.batched = 0; const was = Stepping.begin(&a.t, null); tape.digestHere(&a.t); was.end(); a.seq += 1; return try 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 } { std.debug.assert(a.batched == 0); 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 { std.debug.assert(a.batched == 0); 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.step(); was.end(); return a.unit(in.client, in.seq); } }; // ---- terminals as screen state (src/screen_state.zig) ---- // // A message of either side is u8 pane, u32 the pane's serial (a slot's // next pane is another), u8 kind, and the kind's bytes: // to a replica: kind 1, a delta; kind 2, rows (encodeRows): asked for, // or a step read them; // to the authority: kind 1, an acknowledgement (u32 seq); kind 2, a // request for rows (u64 lo, u64 hi, absolute); kind 3, a // delta refused: start this terminal afresh. // In the authority's stream to a peer, before it steps any input but a // pty's output, and once a frame: its own steps since the last unit, as one // (`Authority.pending`), then what the peer is owed of the terminals // (`Screens.flush`). After a step, before its unit: the rows it read that // the peer holds as holes (`Screens.fill`, then `filled`). A replica takes // them in that order between units (`Replica.screen`), so a step it replays // reads the terminal its authority's step read. const kind_delta = 1; const kind_rows = 2; const kind_ack = 1; const kind_reset = 3; const ScreenMsg = struct { pane: u8, serial: u32, kind: u8, payload: []const u8 }; fn parseScreen(msg: []const u8) ?ScreenMsg { if (msg.len < 6) return null; return .{ .pane = msg[0], .serial = std.mem.readInt(u32, msg[1..5], .little), .kind = msg[5], .payload = msg[6..] }; } fn writeScreenHead(out: *std.ArrayListUnmanaged(u8), gpa: Allocator, pane: u8, serial: u32, kind: u8) !void { var head: [6]u8 = undefined; head[0] = pane; std.mem.writeInt(u32, head[1..5], serial, .little); head[5] = kind; try out.appendSlice(gpa, &head); } /// The authority's side of its replicas' terminals: a track each terminal /// pane, and what each peer was sent of it. pub const Screens = struct { gpa: Allocator, enc: screen_state.Encoder, tracks: [pardes.MAX_PANES]?Tracked = @splat(null), peers: std.ArrayListUnmanaged(*[pardes.MAX_PANES]PeerOf) = .empty, free_peers: std.ArrayListUnmanaged(u16) = .empty, out: std.ArrayListUnmanaged(u8) = .empty, /// Nanoseconds: what each flush spent encoding, for every peer. encode_ns: u64 = 0, const Tracked = struct { serial: u32, state: *terminal.State, track: screen_state.Track }; const PeerOf = struct { serial: u32 = 0, peer: screen_state.Peer = .{} }; pub fn init(gpa: Allocator) Screens { return .{ .gpa = gpa, .enc = .init(gpa) }; } /// `core` is the session's, its terminals still there. pub fn deinit(s: *Screens, core: *Pardes) void { for (&s.tracks, 0..) |*slot, id| if (slot.*) |*tr| tr.track.deinit(s.gpa, if (s.live(core, id, tr)) &tr.state.vt else null); for (s.peers.items) |p| { for (p) |*pp| pp.peer.deinit(s.gpa); s.gpa.destroy(p); } s.peers.deinit(s.gpa); s.free_peers.deinit(s.gpa); s.out.deinit(s.gpa); s.enc.deinit(); } fn live(_: *const Screens, core: *Pardes, id: usize, tr: *const Tracked) bool { const pane = core.panes[id] orelse return false; return pane.serial == tr.serial and pane.terminal == tr.state; } /// A new peer, with nothing yet: its first delta of each terminal /// starts it afresh. pub fn addPeer(s: *Screens) !u16 { if (s.free_peers.pop()) |again| return again; const p = try s.gpa.create([pardes.MAX_PANES]PeerOf); p.* = @splat(.{}); try s.peers.append(s.gpa, p); return @intCast(s.peers.items.len - 1); } /// Peer `peer` gone: what it was sent forgotten, its number free for /// the next `addPeer` (a socket's clients come and go). pub fn dropPeer(s: *Screens, peer: u16) void { for (s.peers.items[peer]) |*pp| pp.peer.deinit(s.gpa); s.peers.items[peer].* = @splat(.{}); s.free_peers.append(s.gpa, peer) catch {}; } /// What `peer` is owed of every terminal, each a message onto `out` /// (owned): nothing for one it has as it is, or with `bound` in flight. pub fn flush(s: *Screens, core: *Pardes, peer: u16, out: *std.ArrayListUnmanaged([]u8)) !void { const t0 = nowNs(); defer s.encode_ns += nowNs() - t0; for (core.panes, 0..) |slot, id| { const pane = slot orelse continue; const state = pane.terminal orelse continue; const tr = try s.track(core, id); const pp = &s.peers.items[peer][id]; if (pp.serial != pane.serial) { pp.peer.reset(); pp.serial = pane.serial; } var marks: [terminal.marks_len]u8 = undefined; s.out.clearRetainingCapacity(); try writeScreenHead(&s.out, s.gpa, @intCast(id), pane.serial, kind_delta); var w: std.Io.Writer.Allocating = .fromArrayList(s.gpa, &s.out); defer s.out = w.toArrayList(); if (!try screen_state.encode(&s.enc, &tr.track, &pp.peer, &state.vt, state.changes, terminal.marksOf(state, &marks), &w.writer)) continue; try out.append(s.gpa, try s.gpa.dupe(u8, w.written())); } } /// Rows a peer holds as holes of every terminal a step read (its rows, /// history and all: text mode over a shell), each a rows message onto /// `out` (owned): sent after the step and before its unit, so the /// replica's replay reads what the authority's step read. A history row /// never changes, so each goes once. Then `filled`. // ponytail: a step that reads a terminal's rows reads all of them (its // motion surface), so the first after a flood sends its whole history. pub fn fill(s: *Screens, core: *Pardes, peer: u16, out: *std.ArrayListUnmanaged([]u8)) !void { for (core.panes, 0..) |slot, id| { const pane = slot orelse continue; const state = pane.terminal orelse continue; if (!state.read) continue; const pp = &s.peers.items[peer][id]; if (pp.serial != pane.serial or pp.peer.holes.items.len == 0) continue; const tr = try s.track(core, id); for (pp.peer.holes.items) |hole| { var lo = hole[0]; while (lo < hole[1]) { const hi = @min(hole[1], lo + 512); s.out.clearRetainingCapacity(); try writeScreenHead(&s.out, s.gpa, @intCast(id), pane.serial, kind_rows); var w: std.Io.Writer.Allocating = .fromArrayList(s.gpa, &s.out); defer s.out = w.toArrayList(); try screen_state.encodeRows(&s.enc, &tr.track, &state.vt, lo, hi, &w.writer); try out.append(s.gpa, try s.gpa.dupe(u8, w.written())); lo = hi; } } pp.peer.holes.clearRetainingCapacity(); } } /// Every peer is filled: the steps' reads are forgotten. pub fn filled(_: *Screens, core: *Pardes) void { for (core.panes) |slot| if (slot) |pane| if (pane.terminal) |state| { state.read = false; }; } fn track(s: *Screens, core: *Pardes, id: usize) !*Tracked { const pane = core.panes[id].?; if (s.tracks[id]) |*tr| { if (s.live(core, id, tr)) return tr; // Its pane closed (its emulator, the pin with it, gone). tr.track.deinit(s.gpa, null); } s.tracks[id] = .{ .serial = pane.serial, .state = pane.terminal.?, .track = .init(s.gpa) }; return &s.tracks[id].?; } /// A peer's message (`Replica.screen`'s, `Replica.screenRequest`'s): /// an answer for it (owned), or null. pub fn take(s: *Screens, core: *Pardes, peer: u16, msg: []const u8) !?[]u8 { const m = parseScreen(msg) orelse return null; const pane = core.panes[m.pane] orelse return null; if (pane.serial != m.serial) return null; const state = pane.terminal orelse return null; const pp = &s.peers.items[peer][m.pane]; if (pp.serial != m.serial) return null; switch (m.kind) { kind_ack => if (m.payload.len == 4) pp.peer.ack(std.mem.readInt(u32, m.payload[0..4], .little)), kind_reset => pp.peer.reset(), kind_rows => { if (m.payload.len != 16) return null; const tr = try s.track(core, m.pane); s.out.clearRetainingCapacity(); try writeScreenHead(&s.out, s.gpa, m.pane, m.serial, kind_rows); var w: std.Io.Writer.Allocating = .fromArrayList(s.gpa, &s.out); defer s.out = w.toArrayList(); try screen_state.encodeRows(&s.enc, &tr.track, &state.vt, std.mem.readInt(u64, m.payload[0..8], .little), std.mem.readInt(u64, m.payload[8..16], .little), &w.writer); return try s.gpa.dupe(u8, w.written()); }, else => {}, } return null; } }; // ---- 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, /// Nanoseconds: a terminal's delta applied. apply_ns: std.ArrayListUnmanaged(u64) = .empty, pub fn deinit(s: *Stats, gpa: Allocator) void { s.spec_ns.deinit(gpa); s.copy_ns.deinit(gpa); s.rollback_ns.deinit(gpa); s.apply_ns.deinit(gpa); } }; const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null, sent_ns: u64 = 0 }; 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, /// The digest the last confirmed unit ended on (its last record's /// bytes): a unit of another's that ends on it again (the session's /// pump that took this replica's input in, and moved nothing) leaves /// the speculation on top as it was. last_digest: std.ArrayListUnmanaged(u8) = .empty, /// Units of another's taken so, no rollback made. neutral: u32 = 0, /// What it shows changed since the host last drew it: a unit replayed /// on it, a rollback (a unit that confirmed what it applied, or moved /// nothing, changes nothing to draw). moved: bool = false, /// A client of a session elsewhere (`initDump`): the session's clock is /// guessed, never read here -- its last unit's reading, plus the time /// since it came, plus a round trip (the input reaches the session that /// much later). In process, both read one clock. guess: bool = false, stamp: struct { real_ns: i64 = 0, mono_ns: i64 = 0, at_ns: u64 = 0 } = .{}, rtt_ns: u64 = 0, gmtoff: i32 = 0, /// Its terminals' screen state, as the authority's deltas made it. screens: [pardes.MAX_PANES]?ScreenOf = @splat(null), screen_out: std.ArrayListUnmanaged(u8) = .empty, /// Its predicted echo (src/echo.zig), drawn over its core's terminals: /// fed by its keys, its units and its deltas here, and by `echoFrame`. echo: pardes.echo.Echo = .{}, const ScreenOf = struct { serial: u32, rep: screen_state.Replica = .{}, /// A delta was refused, and a reset asked for: those in flight /// before it are refused unasked. refused: bool = false, /// The rows asked for and not yet answered. asked: ?[2]u64 = null, }; /// A replica of the session whose first unit is `first`; `screens` /// as the authority's (its terminals fed by `screen`). pub fn init(gpa: Allocator, id: u16, first: []const u8, screens: bool) !*Replica { const r = try gpa.create(Replica); r.* = .{ .gpa = gpa, .id = id, .t = tape.memory(gpa) }; r.t.screen_state = screens; r.t.core_gpa = r.epoch.allocator(); r.confirm(first); if (r.t.core == null) { r.deinit(); return error.NoCore; } if (screens) r.core().echo = &r.echo; return r; } /// A replica of a session elsewhere, as its walker dump (src/dump.zig) /// is: what a client of a socket joins with. `opts` are this process's /// (a replica's own allocators and names); its core's allocator is the /// rollback epoch's, but for images and PDFs, whose workers allocate on /// threads of their own. ponytail: a picture's pixels freed while a copy /// is held are not put off; a rollback over one shows an image a frame /// late at worst... or reads freed pixels, which no test session has. pub fn initDump(gpa: Allocator, id: u16, view: u8, bytes: []const u8, opts: pardes.Options) !*Replica { const r = try gpa.create(Replica); r.* = .{ .gpa = gpa, .id = id, .view = view, .t = tape.memory(gpa), .guess = true }; r.t.headless = true; // Its terminals are the session's deltas (Peers sends them). r.t.screen_state = true; errdefer { tape.release(&r.t); r.epoch.deinit(); gpa.destroy(r); } const epoch = r.epoch.allocator(); r.t.core_gpa = epoch; var o = opts; o.frame_allocator = epoch; o.tree_sitter_allocator = epoch; o.image_allocator = o.image_allocator orelse std.heap.c_allocator; o.pdf_allocator = o.pdf_allocator orelse std.heap.c_allocator; // The session's store and Recent are the authority's. o.store_path = null; // Its emulators off the epoch, as `terminal.create` makes a screen // replica's: deltas write them while a copy is held. pardes.dump.terminal_gpa = terminal.emulator_gpa; defer pardes.dump.terminal_gpa = null; const c = try pardes.dump.load(epoch, o, bytes, null); // What loading queued (a watch, a theme asked for) is the // authority's errand, done there already: the session was dumped // between steps, with nothing queued. c.effects_len = 0; c.effects_head = 0; c.in_len = 0; c.in_head = 0; tape.adoptCore(&r.t, c); // Its keys into a terminal drawn at once (src/echo.zig). c.echo = &r.echo; return r; } pub fn deinit(r: *Replica) void { for (&r.screens) |*slot| if (slot.*) |*sc| sc.rep.deinit(terminal.emulator_gpa); 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.screen_out.deinit(r.gpa); r.last_digest.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, .sent_ns = nowNs() }); r.dirty = true; r.settle(); if (r.t.screen_state and r.diverged == null) r.echo.typed(r.core(), r.view, ev, seq, r.applied == r.pending.items.len); 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; if (u.origin == r.id) if (r.t.core) |c| r.echo.confirmed(c, u.seq); // A copy taken ahead (`ready`), nothing on top: the unit moves the // state it was of. if (r.applied == 0 and r.copy.held) { r.copy.release(); rollback.Epoch.select(null); r.clearSince(); } if (r.guess) { r.stamp = .{ .real_ns = u.real_ns, .mono_ns = u.mono_ns, .at_ns = nowNs() }; if (u.origin == r.id) for (r.pending.items) |p| if (p.seq == u.seq) { // Sent to confirmed: what reaching the session takes, and back. if (p.sent_ns != 0) r.rtt_ns = nowNs() -| p.sent_ns; break; }; } 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; } const ends = lastDigest(u.tape); defer if (ends) |d| { r.last_digest.clearRetainingCapacity(); r.last_digest.appendSlice(r.gpa, d) catch {}; }; if (r.applied > 0 and u.origin != r.id and ends != null and std.mem.eql(u8, ends.?, r.last_digest.items)) { // Nothing a digest covers moved: what was applied on top is // what the session will apply on top of it. Replayed when the // copy is next put back. r.neutral += 1; 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(); } r.moved = true; 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); // The rows a terminal was read as are no copy's: what the // speculation built was the epoch's, freed with it, and what // was there before is of a grid the deltas since moved on // from (a rollback never brings a terminal's past back). r.core().shell_rows = .{}; } 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]; // Every kind, a view's own (a resize, the pointer) too: each client // has its own view, and what reaches the authority's (a pty's size, // the pointer over a sliding pane) stops it as any host call does. const in = parseInput(p.msg) orelse return false; const c = r.core(); if (!r.copy.held) { const t0 = nowNs(); // A grid's worth of text the copy would save, and put back stale. c.shell_rows.reset(c.gpa); 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); r.t.guess = if (r.guess) guess: { const since: i64 = @intCast(nowNs() -| r.stamp.at_ns + r.rtt_ns); break :guess .{ .real_ns = r.stamp.real_ns + since, .mono_ns = r.stamp.mono_ns + since, .gmtoff = r.gmtoff }; } else null; c.toView(r.view); // Input into a terminal is the authority's: its step reads the // emulator (rows, cursor, modes), which here is the last delta's and // there what the pty has said since. It waits; phase 6 predicts the // echo. if (r.t.screen_state) if (c.panes[c.active]) |pane| if (pane.isTerminal()) tape.poison(); c.update(in.event); c.step(); 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; if (std.c.getenv("PARDES_REPLICA_TRACE") != null) std.debug.print("replica {d}: its input {d} ({t}) stopped at a host call: it waits\n", .{ r.id, p.seq, in.event }); 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; } /// Its client's, once a frame before it draws: a predicted echo the /// screen has not shown in time goes, and keys deferred behind one not /// predicted are predicted once its doing is on the screen. Whether what /// the overlay draws changed since the last call (by a key, a unit, a /// delta or this: `echo.changed`). pub fn echoFrame(r: *Replica) bool { return r.echo.frame(r.core()); } /// Nothing pending and nothing applied: the replica is the authority's /// confirmed state, which `digest` says (a copy taken ahead, `ready`, /// has nothing on top of it). pub fn quiet(r: *const Replica) bool { return r.pending.items.len == 0 and r.applied == 0; } /// The copy taken now, while nothing is pending (the host is idle, its /// frame drawn), so that the next input of its own is applied at once /// without taking it: a copy is a megabyte saved. Let go when a unit /// comes first. pub fn ready(r: *Replica) void { if (r.copy.held or r.pending.items.len > 0 or r.diverged != null) return; const c = r.core(); const t0 = nowNs(); rollback.Epoch.select(&r.epoch); defer rollback.Epoch.select(null); r.copy.take(&r.epoch, c) catch return; r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {}; r.stats.copy_bytes += r.copy.savedBytes(); r.stats.copies += 1; } /// Whether its core loaded from the dump is the session as it was /// dumped, by the welcome's `digest`. pub fn loaded(r: *Replica, want: u64) bool { return r.digest() == want; } /// Its own view drawn and presented through `present`, between steps /// (views.drawOne): nothing the digest covers moves. The epoch's trees /// held while a copy is (a render can make or drop a syntax tree). pub fn draw(r: *Replica, present: pardes.views.Present) void { rollback.Epoch.select(&r.epoch); defer rollback.Epoch.select(null); pardes.views.drawOne(r.core(), r.view, present) catch {}; } /// One of the authority's terminal messages (`Screens.flush`, or an /// answer to `screenRequests`), taken between units in stream order: a /// delta written into its pane's emulator, or fetched rows. The /// message for the authority (an acknowledgement, or a request to start /// afresh), valid until the next call, or null. pub fn screen(r: *Replica, msg: []const u8) ?[]const u8 { const m = parseScreen(msg) orelse return null; const c = r.t.core orelse return null; const pane = c.panes[m.pane] orelse return null; if (pane.serial != m.serial) return null; // a pane gone: its slot's next is another const state = pane.terminal orelse return null; const slot = &r.screens[m.pane]; if (slot.* == null or slot.*.?.serial != m.serial) { if (slot.*) |*old| old.rep.deinit(terminal.emulator_gpa); slot.* = .{ .serial = m.serial }; } const sc = &slot.*.?; // The emulator is the authority's: on the C heap, outside the // rollback epoch, so a copy held now never saves or puts back any // of what this writes (State.gpa). switch (m.kind) { kind_delta => { const t0 = nowNs(); const applied = sc.rep.apply(state.gpa, terminal.terminalIo(), &state.vt, m.payload) catch |err| { if (err != error.BaseMismatch) r.fail("a terminal's delta did not apply"); if (sc.refused) return null; sc.refused = true; return r.screenMessage(m.pane, m.serial, kind_reset, &.{}); }; r.stats.apply_ns.append(r.gpa, nowNs() - t0) catch {}; sc.refused = false; terminal.takeMarks(state, applied.extra); r.echo.delta(c, m.pane, sc.rep.top); // Its rows as the core keeps them read are another grid's. c.shell_rows.markStale(pane); var seq: [4]u8 = undefined; std.mem.writeInt(u32, &seq, applied.seq, .little); return r.screenMessage(m.pane, m.serial, kind_ack, &seq); }, kind_rows => { sc.asked = null; sc.rep.applyRows(state.gpa, &state.vt, m.payload) catch r.fail("a terminal's rows did not apply"); c.shell_rows.markStale(pane); return null; }, else => return null, } } /// A request for the rows a terminal shows here and does not hold (its /// holes in view, after a scroll back), one a terminal at a time; null /// when none is owed. Until the answer, a hole shows blank. pub fn screenRequest(r: *Replica) ?[]const u8 { const c = r.t.core orelse return null; for (&r.screens, 0..) |*slot, id| { const sc: *ScreenOf = if (slot.*) |*x| x else continue; if (sc.asked != null) continue; const pane = c.panes[id] orelse continue; if (pane.serial != sc.serial) continue; const state = pane.terminal orelse continue; const shown = sc.rep.shown(&state.vt); var holes: std.ArrayList([2]u64) = .empty; defer holes.deinit(r.gpa); sc.rep.missing(shown[0], shown[1], &holes, r.gpa) catch return null; if (holes.items.len == 0) continue; const want: [2]u64 = .{ holes.items[0][0], holes.items[holes.items.len - 1][1] }; sc.rep.blank(&state.vt, want[0], want[1]); sc.asked = want; var range: [16]u8 = undefined; std.mem.writeInt(u64, range[0..8], want[0], .little); std.mem.writeInt(u64, range[8..16], want[1], .little); return r.screenMessage(@intCast(id), sc.serial, kind_rows, &range); } return null; } fn screenMessage(r: *Replica, pane: u8, serial: u32, kind: u8, payload: []const u8) ?[]const u8 { r.screen_out.clearRetainingCapacity(); writeScreenHead(&r.screen_out, r.gpa, pane, serial, kind) catch return null; r.screen_out.appendSlice(r.gpa, payload) catch return null; return r.screen_out.items; } pub fn digest(r: *Replica) u64 { const was = Stepping.begin(&r.t, &r.epoch); defer was.end(); return tape.digestOf(r.core()); } }; /// The bytes of a unit's last digest record: the state it ended on; null /// for one that says what the host wrote or which host it is (a replica's /// core takes those only by replaying the unit). fn lastDigest(bytes: []const u8) ?[]const u8 { var r: walk.Reader = .{ .bytes = bytes }; var last: ?[]const u8 = null; while (true) { const head = r.take(5) catch return last; const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return last; if (head[0] == tape.digest_kind) last = payload; if (head[0] == tape.set_kind) return null; } } 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.digestScreen(&h); d.* = h.final(); } } // ---- over a socket (docs/next-daemon.md, "Phase 5 part B notes") ---- // // The session's half: each client handed over by the daemon (daemon.zig) is // a Peer, with a view of its own, a thread reading its inputs and one // writing what it is sent. The recorder is on while any is. At each step // boundary of the session's loop (`Peers.boundary`, after a pump): // - the pump's unit goes to every client; // - a client that came is joined: its view opened, the session dumped // (src/dump.zig) and sent ahead of every unit after; // - each input that came is a unit of its own: its view, the input, a // `step` (what the client's own core applied at once); // - a client gone takes its view with it. // A client's link only ever holds bytes queued for it: the session's step // never waits on one. One that lets `lag_max` pile up is cut off. const libc = std.c; const log = std.log.scoped(.replica); const nosignal: u32 = if (builtin.os.tag == .linux) libc.MSG.NOSIGNAL else 0; /// What a client may leave unread, past its join's dump, before it is cut /// off: minutes of typing, a screenful of a flood's deltas many times over. /// PARDES_REPLICA_LAG_KB says another (a test's). var lag_max: usize = 64 << 20; const dump_piece = 1 << 20; const Tm = extern struct { sec: c_int, min: c_int, hour: c_int, mday: c_int, mon: c_int, year: c_int, wday: c_int, yday: c_int, isdst: c_int, gmtoff: c_long, zone: ?[*:0]const u8 }; extern "c" fn localtime_r(t: *const libc.time_t, tm: *Tm) ?*Tm; /// This zone's offset from UTC now, seconds. fn gmtoff() i32 { var ts: libc.timespec = undefined; _ = libc.clock_gettime(.REALTIME, &ts); const secs: libc.time_t = ts.sec; var tm: Tm = undefined; return if (localtime_r(&secs, &tm) != null) @intCast(tm.gmtoff) else 0; } fn writeAll(fd: c_int, bytes: []const u8) bool { var at: usize = 0; while (at < bytes.len) { const n = libc.send(fd, bytes[at..].ptr, bytes.len - at, nosignal); if (n < 0 and libc.errno(n) == .INTR) continue; if (n <= 0) return false; at += @intCast(n); } 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); if (n < 0 and libc.errno(n) == .INTR) continue; return if (n <= 0) 0 else @intCast(n); } } /// What a stream's reader holds of it, read and not yet taken: a dump's /// reader leaves the units read with its last piece to the stream's. pub const Framer = struct { buf: std.ArrayListUnmanaged(u8) = .empty, len: usize = 0, pub fn deinit(f: *Framer, gpa: Allocator) void { f.buf.deinit(gpa); } /// Framed messages off `fd` (detached/wire.zig) handed to `take` until /// the stream ends, `take` says stop, or a message is malformed. fn run(fr: *Framer, gpa: Allocator, fd: c_int, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void { while (true) { var at: usize = 0; var stop = false; while (!stop) { const f = (wire.framed(fr.buf.items[at..fr.len]) catch break) orelse break; at += f.total; stop = !take(ctx, f.tag, f.payload); } if (at > 0) { std.mem.copyForwards(u8, fr.buf.items[0 .. fr.len - at], fr.buf.items[at..fr.len]); fr.len -= at; } if (stop) return; if (wire.framed(fr.buf.items[0..fr.len])) |_| {} else |_| return; // Room for what the head says is coming, or 64 KiB more. const want = if (fr.len >= wire.header_len) wire.header_len + @as(usize, std.mem.readInt(u32, fr.buf.items[1..5], .little)) else 0; const room = @max(want, fr.len + (64 << 10)); if (fr.buf.items.len < room) fr.buf.resize(gpa, room) catch return; const n = readSome(fd, fr.buf.items[fr.len..]); if (n == 0) return; fr.len += n; } } }; fn readFramed(gpa: Allocator, fd: c_int, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void { var fr: Framer = .{}; defer fr.deinit(gpa); fr.run(gpa, fd, ctx, take); } pub const Peer = struct { peers: *Peers, fd: c_int, id: u16, view: u8, /// Its number in the session's `Screens`. sid: u16 = 0, /// Inputs read (each one's seq, as the client numbered them). seq: u32 = 0, reader: ?std.Thread = null, writer: ?std.Thread = null, lock: std.Io.Mutex = .init, cond: std.Io.Condition = .init, /// What it is sent, not written yet, and what the writer writes now. out: std.ArrayListUnmanaged(u8) = .empty, sending: std.ArrayListUnmanaged(u8) = .empty, limit: usize = 64 << 20, closing: bool = false, 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 /// says it is gone. fn send(peer: *Peer, parts: []const []const u8) void { const io = peer.peers.io; peer.lock.lockUncancelable(io); defer peer.lock.unlock(io); if (peer.cut or peer.closing) return; var n: usize = peer.out.items.len; for (parts) |p| n += p.len; if (n > peer.limit) { log.info("client {d} is {d} MB behind: cut off", .{ peer.id, n >> 20 }); peer.peers.cut += 1; peer.cut = true; _ = libc.shutdown(peer.fd, 2); peer.cond.signal(io); return; } for (parts) |p| peer.out.appendSlice(peer.peers.gpa, p) catch { peer.cut = true; _ = libc.shutdown(peer.fd, 2); break; }; peer.cond.signal(io); } 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); if (peer.out.items.len == 0 or peer.cut) { peer.lock.unlock(io); return; } std.mem.swap(std.ArrayListUnmanaged(u8), &peer.out, &peer.sending); // The limit was for the dump and what is queued behind it. peer.limit = lag_max; peer.lock.unlock(io); const ok = writeAll(peer.fd, peer.sending.items); peer.sending.clearRetainingCapacity(); if (!ok) { _ = libc.shutdown(peer.fd, 2); return; } } } fn take(peer: *Peer, tag: u8, payload: []const u8) bool { const t = std.enums.fromInt(wire.ClientTag, tag) orelse return false; switch (t) { .hello, .bye => return false, .ping => { var out: [16]u8 = undefined; const v = (wire.decodeClient(tag, payload) catch return false).ping; const pong = wire.encodeServer(&out, .{ .pong = v }) catch return false; peer.send(&.{pong}); return true; }, // Its word about a terminal (an ack, rows asked, a reset), to // the session's Screens at the next boundary. .screen_ack => { const msg = peer.peers.gpa.dupe(u8, payload) catch return false; peer.peers.post(.{ .screen = .{ .peer = peer, .msg = msg } }); return true; }, .check => { peer.peers.post(.{ .check = peer }); return true; }, else => {}, } peer.seq += 1; const msg = peer.peers.gpa.alloc(u8, head_len + wire.header_len + payload.len) catch return false; header(msg, peer.id, peer.seq); msg[head_len] = tag; std.mem.writeInt(u32, msg[head_len + 1 ..][0..4], @intCast(payload.len), .little); @memcpy(msg[head_len + wire.header_len ..], payload); if (parseInput(msg) == null) { peer.peers.gpa.free(msg); return false; } peer.peers.post(.{ .input = .{ .peer = peer, .msg = msg } }); return true; } fn readLoop(peer: *Peer) void { readFramed(peer.peers.gpa, peer.fd, peer, take); peer.peers.post(.{ .gone = peer }); } }; pub const Peers = struct { gpa: Allocator = std.heap.c_allocator, io: std.Io = undefined, /// This session's name and pid, for a welcome. name: []const u8 = "", t: tape.Tape = undefined, recording: bool = false, list: [pardes.views.max]?*Peer = @splat(null), next_id: u16 = 1, seq: u32 = 0, lock: std.Io.Mutex = .init, inbox: std.ArrayListUnmanaged(Note) = .empty, taken: std.ArrayListUnmanaged(Note) = .empty, /// A reader posted: the loop's one test a step while nothing is attached. mail: std.atomic.Value(bool) = .init(false), /// Wakes the session's loop (its wait for input) from a reader. wake_ctx: ?*anyopaque = null, wake: ?*const fn (?*anyopaque) void = null, /// What the session would be with no client: unattended without a /// terminal of its own (the host says). 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. input_ns: std.ArrayListUnmanaged(u64) = .empty, boundary_ns: std.ArrayListUnmanaged(u64) = .empty, cut: u32 = 0, head: [unit_head]u8 = undefined, /// Its clients' terminals as screen state (src/screen_state.zig), while /// it records: what each was sent. screens: Screens = undefined, msgs: std.ArrayListUnmanaged([]u8) = .empty, /// 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 { var n: usize = 0; for (ps.list) |slot| n += @intFromBool(slot != null); return n; } fn post(ps: *Peers, note: Note) void { ps.lock.lockUncancelable(ps.io); ps.inbox.append(ps.gpa, note) catch { ps.lock.unlock(ps.io); switch (note) { .join => |fd| _ = libc.close(fd), .input, .screen => |in| ps.gpa.free(in.msg), .gone, .check, .joined, .hashed => {}, } return; }; ps.mail.store(true, .release); ps.lock.unlock(ps.io); if (ps.wake) |w| w(ps.wake_ctx); } /// A replica's connection the daemon handed over (its hello taken /// there): joined at the next step boundary. Any thread. pub fn handed(ps: *Peers, fd: c_int) void { ps.post(.{ .join = fd }); } /// What was recorded since the last unit, to every client as one, its /// digest at its end. fn unit(ps: *Peers, origin: u16, seq: u32) void { if (tape.taken(&ps.t).len == 0) return; tape.recordDigest(&ps.t); const bytes = tape.taken(&ps.t); unitHeader(&ps.head, origin, seq); if (std.c.getenv("PARDES_REPLICA_TRACE") != null) { var w: std.Io.Writer.Allocating = .init(ps.gpa); defer w.deinit(); w.writer.print("session: unit {d}/{d}, {d} bytes, to {d} clients:\n", .{ origin, seq, bytes.len, ps.count() }) catch {}; tape.describe(bytes, &w.writer); std.debug.print("{s}", .{w.written()}); } const head = wire.header(@backingInt(wire.ServerTag.unit), unit_head + bytes.len); for (ps.list) |slot| if (slot) |peer| peer.send(&.{ &head, &ps.head, bytes }); tape.clearTaken(&ps.t); } /// After each of the session's pumps: its unit sent, the clients that /// came joined, their inputs taken in, the ones gone let go. pub fn boundary(ps: *Peers, core: *Pardes) void { if (!ps.recording and !ps.mail.load(.acquire)) return; const t0 = nowNs(); defer if (ps.recording) ps.boundary_ns.append(ps.gpa, nowNs() - t0) catch {}; if (ps.recording) { // The rows the pump's steps read, then its unit, then what the // terminals came to (the next steps read that). ps.screensOut(core, .fill); ps.seq += 1; ps.unit(0, ps.seq); ps.screensOut(core, .flush); } if (!ps.mail.load(.acquire)) return; ps.lock.lockUncancelable(ps.io); std.mem.swap(std.ArrayListUnmanaged(Note), &ps.inbox, &ps.taken); ps.mail.store(false, .release); ps.lock.unlock(ps.io); for (ps.taken.items) |note| switch (note) { .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); }, .screen => |in| { defer ps.gpa.free(in.msg); const reply = (ps.screens.take(core, in.peer.sid, in.msg) catch null) orelse continue; defer ps.gpa.free(reply); const head = wire.header(@backingInt(wire.ServerTag.screen), reply.len); 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}); }, }; ps.taken.clearRetainingCapacity(); } fn input(ps: *Peers, core: *Pardes, peer: *Peer, msg: []const u8) void { const in = parseInput(msg) orelse return; const t0 = nowNs(); defer ps.input_ns.append(ps.gpa, nowNs() - t0) catch {}; // The terminals as this step reads them, then the step, the rows // it read, its unit (part B terminal notes' order). ps.screensOut(core, .flush); core.toView(peer.view); core.update(in.event); core.step(); ps.screensOut(core, .fill); ps.unit(peer.id, in.seq); } const ScreensOut = enum { flush, fill }; /// What each client is owed of the terminals (`Screens.flush`), or the /// rows a step read that it lacks (`Screens.fill`, then `filled`), each /// a screen message queued for it. fn screensOut(ps: *Peers, core: *Pardes, comptime what: ScreensOut) void { for (ps.list) |slot| if (slot) |peer| ps.screensTo(core, peer, what); if (what == .fill) ps.screens.filled(core); } fn screensTo(ps: *Peers, core: *Pardes, peer: *Peer, comptime what: ScreensOut) void { defer { for (ps.msgs.items) |m| ps.gpa.free(m); ps.msgs.clearRetainingCapacity(); } (switch (what) { .flush => ps.screens.flush(core, peer.sid, &ps.msgs), .fill => ps.screens.fill(core, peer.sid, &ps.msgs), }) catch return; for (ps.msgs.items) |m| { const head = wire.header(@backingInt(wire.ServerTag.screen), m.len); peer.send(&.{ &head, m }); } } fn refuse(fd: c_int, why: []const u8) void { var out: [600]u8 = undefined; if (wire.encodeServer(&out, .{ .refused = why })) |bytes| _ = writeAll(fd, bytes) else |_| {} _ = 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); 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"); if (!ps.recording) { // A session recording to a file (PARDES_RECORD) has its tape. if (tape.on != null) return refuse(fd, "that session records a tape of its own (PARDES_RECORD)"); ps.t = tape.memory(ps.gpa); ps.t.unit_digests = true; // Terminals cross as screen state: a unit carries no pty bytes, // and its digest is a word (PARDES_REPLICA_TRACE: one a field). ps.t.screen_state = true; ps.t.whole_digest = std.c.getenv("PARDES_REPLICA_TRACE") == null; ps.screens = .init(ps.gpa); tape.on = &ps.t; ps.recording = true; } // Someone looks at it now: its messages go by keys, not the clock. core.unattended = false; const k = core.openView() orelse { core.unattended = ps.count() == 0 and ps.alone_unattended; if (ps.count() == 0) ps.stop(core); return refuse(fd, "that session has as many views as it takes"); }; // Its own process draws it. core.undrawn |= @as(u8, 1) << @intCast(k); ps.seq += 1; ps.unit(0, ps.seq); // 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); if (ps.count() == 0) ps.stop(core); 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"); }; 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 { 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 = lag_max, .dump = bytes, .blobs = blobs, .dump_gpa = core.gpa }; ps.next_id +%= 1; if (ps.next_id == 0) ps.next_id = 1; // The session's digest as dumped, for the joiner to check its load by. const digest = tape.digestOf(core); 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) { ps.letGo(peer); core.undrawn &= ~(@as(u8, 1) << @intCast(k)); core.closeView(k); ps.unit(0, ps.seq); return; } slot.* = peer; // Its terminals afresh, after its dump and before any unit. if (ps.screens.addPeer()) |sid| { 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 ({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 }); } fn leave(ps: *Peers, core: *Pardes, peer: *Peer) void { for (&ps.list) |*slot| if (slot.* == peer) { slot.* = null; }; log.info("client {d} left '{s}'", .{ peer.id, ps.name }); ps.screens.dropPeer(peer.sid); core.undrawn &= ~(@as(u8, 1) << @intCast(peer.view)); core.closeView(peer.view); if (ps.count() == 0) core.unattended = ps.alone_unattended; ps.seq += 1; ps.unit(0, ps.seq); ps.letGo(peer); if (ps.count() == 0) ps.stop(core); } /// Its threads ended and joined, its link closed. fn letGo(ps: *Peers, peer: *Peer) void { const io = ps.io; peer.lock.lockUncancelable(io); peer.closing = true; peer.cond.signal(io); peer.lock.unlock(io); _ = 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); // What its reader posted after it was let go (its end) is nobody's. ps.lock.lockUncancelable(io); var i: usize = 0; while (i < ps.inbox.items.len) { const mine = switch (ps.inbox.items[i]) { .input, .screen => |in| in.peer == peer, .gone, .check, .joined => |p| p == peer, .join, .hashed => false, }; if (!mine) { i += 1; continue; } switch (ps.inbox.items[i]) { .input, .screen => |in| ps.gpa.free(in.msg), else => {}, } _ = ps.inbox.orderedRemove(i); } ps.lock.unlock(io); ps.gpa.destroy(peer); } /// Every client told `why` and let go, its view with it: an Upgrade's /// exec is next (tty.zig `upgradeNow`). What each was sent goes first, /// for up to 200 ms; a client then dials the session again. pub fn refuseAll(ps: *Peers, core: *Pardes, why: []const u8) void { if (ps.count() == 0) return; var out: [600]u8 = undefined; const words = wire.encodeServer(&out, .{ .refused = why }) catch return; const io = ps.io; for (ps.list) |slot| if (slot) |peer| { peer.send(&.{words}); peer.lock.lockUncancelable(io); peer.closing = true; peer.cond.signal(io); peer.lock.unlock(io); }; const until = nowNs() + 200 * std.time.ns_per_ms; while (nowNs() < until) { const busy = for (ps.list) |slot| { if (slot) |peer| if (!peer.done.load(.acquire)) break true; } else false; if (!busy) break; const ts: libc.timespec = .{ .sec = 0, .nsec = 2 * std.time.ns_per_ms }; _ = libc.nanosleep(&ts, null); } 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 { for (ps.list) |slot| if (slot) |peer| if (peer.view == k) { _ = libc.shutdown(peer.fd, 2); return true; }; return false; } fn stop(ps: *Peers, core: *Pardes) void { if (!ps.recording) return; ps.screens.deinit(core); if (core.host.vtable == &ps.t.vtable) core.host = ps.t.real; tape.on = null; tape.release(&ps.t); ps.recording = false; } /// 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)); core.closeView(peer.view); ps.screens.dropPeer(peer.sid); ps.letGo(peer); }; ps.stop(core); ps.lock.lockUncancelable(ps.io); for (ps.inbox.items) |note| switch (note) { .join => |fd| _ = libc.close(fd), .input, .screen => |in| ps.gpa.free(in.msg), .gone, .check, .joined, .hashed => {}, }; ps.inbox.clearRetainingCapacity(); ps.lock.unlock(ps.io); core.unattended = ps.alone_unattended; } pub fn deinit(ps: *Peers) void { if (std.c.getenv("PARDES_REPLICA_STATS")) |path| if (ps.input_ns.items.len > 0) ps.writeStats(std.mem.span(path)); ps.inbox.deinit(ps.gpa); ps.taken.deinit(ps.gpa); 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} 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.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); } }; // ---- the client's half ---- pub const Joined = struct { fd: c_int, pid: u32, client: u16, view: u8, gmtoff: i32, dump: []u8, /// The session's digest as dumped (`Replica.loaded`). digest: u64 = 0, /// Its build's (wire.semantics): the daemon judged the hello by what it /// last heard, which an upgrade under way may not have said yet. semantics: u64 = 0, /// What was read past the dump: the stream's (`readStream`). rest: Framer = .{}, }; /// Connected to the replica socket at `path`, its hello said for /// `session`, welcomed, and the dump read whole: what a client joins with. /// Errors are said in `why`. pub fn dial(gpa: Allocator, path: []const u8, session: []const u8, why: []u8) ?Joined { const fd = libc.socket(libc.AF.UNIX, libc.SOCK.STREAM | libc.SOCK.CLOEXEC, 0); if (fd < 0) return said(why, "no socket", .{}); var addr: libc.sockaddr.un = .{ .path = @splat(0) }; if (path.len >= addr.path.len) { _ = libc.close(fd); return said(why, "the socket's path is too long: {s}", .{path}); } @memcpy(addr.path[0..path.len], path); if (libc.connect(fd, @ptrCast(&addr), @sizeOf(libc.sockaddr.un)) != 0) { _ = libc.close(fd); return said(why, "nothing answers at {s}", .{path}); } var out: [wire.hello_max]u8 = undefined; const hello = wire.encodeClient(&out, .{ .hello = .{ .session = session } }) catch { _ = libc.close(fd); return said(why, "that session's name is too long", .{}); }; var j: Joined = .{ .fd = fd, .pid = 0, .client = 0, .view = 0, .gmtoff = 0, .dump = &.{} }; const Read = struct { j: *Joined, gpa: Allocator, why: []u8, got: usize = 0, failed: ?[]const u8 = null, welcomed: bool = false, fn take(r: *@This(), tag: u8, payload: []const u8) bool { const msg = wire.decodeServer(tag, payload) catch { r.failed = "the session's answer was not understood"; return false; }; switch (msg) { .welcome => |w| { r.j.pid = w.pid; r.j.client = w.client; r.j.view = w.view; r.j.gmtoff = w.gmtoff; r.j.digest = w.digest; r.j.semantics = w.semantics; r.j.dump = r.gpa.alloc(u8, @intCast(w.dump_len)) catch { r.failed = "out of memory for the session's dump"; return false; }; r.welcomed = true; return w.dump_len > 0; }, .refused => |words| { r.failed = std.fmt.bufPrint(r.why, "{s}\x00", .{words}) catch "refused"; return false; }, .dump => |piece| { if (!r.welcomed or r.got + piece.len > r.j.dump.len) { r.failed = "the session sent more dump than it said"; return false; } @memcpy(r.j.dump[r.got..][0..piece.len], piece); r.got += piece.len; return r.got < r.j.dump.len; }, else => { r.failed = "the session sent a unit before its dump"; return false; }, } } }; if (!writeAll(fd, hello)) { _ = libc.close(fd); return said(why, "the session hung up", .{}); } var r: Read = .{ .j = &j, .gpa = gpa, .why = why }; j.rest.run(gpa, fd, &r, Read.take); if (r.failed != null or !r.welcomed or r.got < j.dump.len) { j.rest.deinit(gpa); if (j.dump.len > 0) gpa.free(j.dump); _ = libc.close(fd); const text = r.failed orelse "the session hung up before the dump was whole"; if (text.ptr == why.ptr) return null; return said(why, "{s}", .{text}); } return j; } fn said(why: []u8, comptime fmt: []const u8, args: anytype) ?Joined { _ = std.fmt.bufPrint(why, fmt ++ "\x00", args) catch {}; return null; } /// A message `Replica.input` made, to the session: the event's frame (its /// client and seq are the connection's). pub fn sendInput(fd: c_int, msg: []const u8) bool { return writeAll(fd, msg[head_len..]); } /// A message `Replica.screen` or `screenRequest` made, to the session. pub fn sendScreen(fd: c_int, msg: []const u8) bool { var buf: [64]u8 = undefined; if (wire.header_len + msg.len > buf.len) { const head = wire.header(@backingInt(wire.ClientTag.screen_ack), msg.len); return writeAll(fd, &head) and writeAll(fd, msg); } buf[0..wire.header_len].* = wire.header(@backingInt(wire.ClientTag.screen_ack), msg.len); @memcpy(buf[wire.header_len..][0..msg.len], msg); return writeAll(fd, buf[0 .. wire.header_len + msg.len]); } /// Asks the session's digest, answered in stream order. pub fn askCheck(fd: c_int) bool { var out: [16]u8 = undefined; return writeAll(fd, wire.encodeClient(&out, .check) catch unreachable); } /// The client's last word. pub fn bye(fd: c_int) void { var out: [16]u8 = undefined; if (wire.encodeClient(&out, .bye)) |b| _ = writeAll(fd, b) else |_| {} } /// What follows the dump on the client's connection, each message handed /// to `take` (a unit, a terminal's delta) until the link ends; `rest` is /// what the dump's reader read past it. pub fn readStream(gpa: Allocator, fd: c_int, rest: *Framer, ctx: anytype, comptime take: fn (@TypeOf(ctx), u8, []const u8) bool) void { rest.run(gpa, fd, ctx, take); } 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(), false); defer a.deinit(); const r = try Replica.init(gpa, 1, try a.unit(0, 0), false); 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(), false); 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, false); defer r1.deinit(); const r2 = try Replica.init(gpa, 2, first, false); 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); } fn screensTo(a: *Authority, screens: *Screens, peer: u16, r: *Replica) !void { const gpa = std.testing.allocator; var msgs: std.ArrayListUnmanaged([]u8) = .empty; defer { for (msgs.items) |m| gpa.free(m); msgs.deinit(gpa); } try screens.flush(a.core, peer, &msgs); for (msgs.items) |m| if (r.screen(m)) |reply| { _ = try screens.take(a.core, peer, reply); }; } test "a delta applied under a speculation outlives its rollback: the terminal stays the authority's newest" { if (comptime !terminal.enabled) return error.SkipZigTest; const gpa = std.testing.allocator; const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .boot = .tty }, TestHost.host(), true); defer a.deinit(); var screens: Screens = .init(gpa); defer screens.deinit(a.core); const peer = try screens.addPeer(); const r = try Replica.init(gpa, 1, try a.unit(0, 0), true); defer r.deinit(); const shell: u8 = for (a.core.panes, 0..) |slot, id| { if (slot) |pane| if (pane.isTerminal()) break @intCast(id); } else return error.NoShell; // Typing goes to the text pane under the shell (the host's write of // `active`, taped). a.core.active = for (a.core.panes, 0..) |slot, id| { if (slot) |pane| if (pane.file != null) break id; } else return error.NoTextPane; r.confirm(try a.local(.{ .focus = true })); try screensTo(a, &screens, peer, r); var sent: std.ArrayListUnmanaged([]u8) = .empty; defer { for (sent.items) |m| gpa.free(m); sent.deinit(gpa); } // Typed into the file, at once: a copy is held. try key(r, 'o', &sent); try std.testing.expect(r.copy.held); var line: [64]u8 = undefined; for (0..3) |round| { // The shell prints: its unit rolls the replica back and applies the // key again; then its delta lands, under the new copy. for (0..40) |i| a.output(.{ .output = .{ .pane = shell, .bytes = try std.fmt.bufPrint(&line, "round {d} line {d}\r\n", .{ round, i }) } }); r.confirm((try a.pending()).?); r.settle(); try std.testing.expect(r.copy.held); try screensTo(a, &screens, peer, r); // The rows the core keeps, read once under the copy. _ = try terminal.shellRows(r.core(), r.core().panes[shell].?); } for (sent.items) |m| { r.confirm(try a.take(m)); r.settle(); gpa.free(m); } sent.clearRetainingCapacity(); try screensTo(a, &screens, peer, r); // Drawn (its rows read, between steps), then typed into: the copy keeps // those rows. The shell prints, its delta lands under the copy, and then // another's unit puts the copy back: the rows it kept are of an older // grid and must not be read. r.confirm(try a.local(.{ .focus = false })); _ = try terminal.shellRows(r.core(), r.core().panes[shell].?); try key(r, 'x', &sent); for (0..40) |i| a.output(.{ .output = .{ .pane = shell, .bytes = try std.fmt.bufPrint(&line, "last line {d}\r\n", .{i}) } }); r.confirm((try a.pending()).?); r.settle(); try screensTo(a, &screens, peer, r); r.confirm(try a.local(.{ .focus = true })); r.settle(); const n = a.core.panes[shell].?.rows; const back = try terminal.shellRows(r.core(), r.core().panes[shell].?); const now = try terminal.shellRows(a.core, a.core.panes[shell].?); for (now[now.len - n ..], back[back.len - n ..]) |x, y| try std.testing.expectEqualStrings(x, y); for (sent.items) |m| { r.confirm(try a.take(m)); r.settle(); } try screensTo(a, &screens, peer, r); if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); try std.testing.expect(r.diverged == null and r.quiet()); try std.testing.expectEqual(digestOf(a), r.digest()); var dump_a: std.Io.Writer.Allocating = .init(gpa); defer dump_a.deinit(); var dump_r: std.Io.Writer.Allocating = .init(gpa); defer dump_r.deinit(); try screen_state.dumpScreen(&a.core.panes[shell].?.terminal.?.vt, &dump_a.writer); try screen_state.dumpScreen(&r.core().panes[shell].?.terminal.?.vt, &dump_r.writer); try std.testing.expectEqualStrings(dump_a.written(), dump_r.written()); const rows_a = try terminal.shellRows(a.core, a.core.panes[shell].?); const rows_r = try terminal.shellRows(r.core(), r.core().panes[shell].?); // As many rows (the history is the authority's to the row), the screen's // the same; above it, rows scrolled past more than a screen at once are // holes until fetched. try std.testing.expectEqual(rows_a.len, rows_r.len); 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 }); } } test "a replica joined from the session's dump replays the units after it" { const gpa = std.testing.allocator; const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host(), false); defer a.deinit(); _ = try a.local(.{ .key = .{ .cp = 'j', .text = "j" } }); const was = Stepping.begin(&a.t, null); const bytes = try pardes.dump.dumpBytes(a.core); tape.resync(&a.t); was.end(); defer a.core.gpa.free(bytes); const r = try Replica.initDump(gpa, 1, 0, bytes, .{ .cols = 80, .rows = 24 }); defer r.deinit(); try std.testing.expectEqual(digestOf(a), r.digest()); r.confirm(try a.local(.{ .key = .{ .cp = 'j', .text = "j" } })); if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); try std.testing.expect(r.diverged == null); var sent: std.ArrayListUnmanaged([]u8) = .empty; defer { for (sent.items) |m| gpa.free(m); sent.deinit(gpa); } for ("oab") |k| try key(r, k, &sent); try key(r, pardes.Key.escape, &sent); 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.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); }