From e89ee60270267cb268ce642d79fb3fb277e84463 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 21:03:38 -0300 Subject: phase 5 part B, terminals: a replica's terminal fed by screen-state deltas, several in flight against the version last sent, its history the authority's to the row, and the authority's own steps batched into a unit a frame screen_state.zig: each state the authority sends is a version of its terminal (Track), made once for every peer; a peer's delta is against the version it was last sent (the stream is ordered and loses nothing), up to 32 in flight, a peer at the bound waiting for an acknowledgement and then getting the newest; peers at one base are sent the same bytes. A replica refuses a delta against another base and is started afresh. It keeps the authority's history extent to the row (no byte limit of its own, trimmed to the authority's count), takes its viewport and its cursor's semantic content, and grows a flood's rows in bulk. The soak now keeps several in flight, lands them late in order, loses one now and then, and checks the history extent and the viewport too. replica.zig: Screens (the authority's tracks and peers) and Replica.screen/screenRequest, messages of u8 pane, u32 serial, u8 kind (a delta, rows; an ack, a row request, a reset). Deltas are applied with the replica's epoch paused, so an emulator outlives a rollback. Authority.output/pending: its own steps (a pty's output) go into one unit, sent before any other input it steps and at a frame, with one digest; under screen state a digest is one word. tape.zig, terminal.zig: under screen state an output is recorded without its bytes, pty writes are off the tape on both sides, no digest covers an emulator, and a replica's core never ingests or resizes one (a resize's own core work, the pointer selections cleared, still runs). A terminal counts its writes (State.changes); its MarkedHandler cycle rides in each delta. test/replicas.zig: the session's shell runs a TUI, then 8 MB of yes read 4 KB at a time, while three clients type; deltas go out before each input the authority steps and once a frame, acknowledgements and row requests come back over the links, every applied delta is checked against the authority's screen at that version and every terminal at quiescence. Co-Authored-By: Claude Opus 5.5 --- src/replica.zig | 291 +++++++++++++++++++++- src/rollback.zig | 12 + src/screen_state.zig | 682 ++++++++++++++++++++++++++++++++++----------------- src/tape.zig | 53 +++- src/terminal.zig | 57 +++++ test/replicas.zig | 320 ++++++++++++++++++++---- 6 files changed, 1130 insertions(+), 285 deletions(-) diff --git a/src/replica.zig b/src/replica.zig index 42d94503..e229bad5 100644 --- a/src/replica.zig +++ b/src/replica.zig @@ -28,6 +28,8 @@ 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; @@ -97,10 +99,15 @@ pub const Authority = struct { /// 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. - pub fn init(gpa: Allocator, options: pardes.Options, host: pardes.Host) !*Authority { + /// `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; @@ -111,6 +118,9 @@ pub const Authority = struct { 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); @@ -150,13 +160,38 @@ pub const Authority = struct { /// 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(); @@ -172,6 +207,7 @@ pub const Authority = struct { /// 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]); @@ -182,6 +218,140 @@ pub const Authority = struct { } }; +// ---- 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 it asked for (encodeRows); +// 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. +// The authority sends a peer what it is owed (`Screens.flush`) before it +// steps any input but a pty's output, and once a frame; a replica takes +// them in that order between units (`Replica.screen`). So a step a replica +// replays reads the terminal its authority's 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, + 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| s.gpa.destroy(p); + s.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 { + 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); + } + + /// 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.* = .{ .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())); + } + } + + 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 { @@ -207,11 +377,14 @@ pub const Stats = struct { 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); } }; @@ -242,11 +415,26 @@ pub const Replica = struct { out: std.ArrayListUnmanaged(u8) = .empty, /// Nanoseconds of the rollback being made, until its reapply. recovering: ?u64 = null, + /// Its terminals' screen state, as the authority's deltas made it. + screens: [pardes.MAX_PANES]?ScreenOf = @splat(null), + screen_out: std.ArrayListUnmanaged(u8) = .empty, + + 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`. - pub fn init(gpa: Allocator, id: u16, first: []const u8) !*Replica { + /// 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) { @@ -257,6 +445,7 @@ pub const Replica = struct { } pub fn deinit(r: *Replica) void { + for (&r.screens) |*slot| if (slot.*) |*sc| sc.rep.deinit(r.coreGpa()); if (r.t.core) |c| { const was = Stepping.begin(&r.t, &r.epoch); if (r.copy.held) r.copy.restore(); @@ -269,6 +458,7 @@ pub const Replica = struct { 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.stats.deinit(r.gpa); tape.release(&r.t); if (r.diverged) |why| r.gpa.free(why); @@ -471,6 +661,89 @@ pub const Replica = struct { return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held; } + fn coreGpa(r: *Replica) Allocator { + return r.epoch.allocator(); + } + + /// 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(r.coreGpa()); + slot.* = .{ .serial = m.serial }; + } + const sc = &slot.*.?; + // The emulator is the authority's, outside every rollback copy: + // what it allocates now must outlive one. + const was = r.epoch.pause(); + defer r.epoch.unpause(was); + switch (m.kind) { + kind_delta => { + const t0 = nowNs(); + const applied = sc.rep.apply(r.coreGpa(), 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); + 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(r.coreGpa(), &state.vt, m.payload) catch r.fail("a terminal's rows did not apply"); + 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.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(); @@ -484,7 +757,7 @@ fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void { const pane = slot orelse continue; const state = pane.terminal orelse continue; var h = walk.Hasher.init(0); - state.digest(&h); + state.digestScreen(&h); d.* = h.final(); } } @@ -513,9 +786,9 @@ fn key(r: *Replica, cp: u21, sent: *std.ArrayListUnmanaged([]u8)) !void { 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()); + 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)); + 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; @@ -539,13 +812,13 @@ test "a replica's own keys apply at once, confirm on the fast path, and end at t 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()); + 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); + const r1 = try Replica.init(gpa, 1, first, false); defer r1.deinit(); - const r2 = try Replica.init(gpa, 2, first); + const r2 = try Replica.init(gpa, 2, first, false); defer r2.deinit(); var s1: std.ArrayListUnmanaged([]u8) = .empty; var s2: std.ArrayListUnmanaged([]u8) = .empty; diff --git a/src/rollback.zig b/src/rollback.zig index 9137b6f6..b5f4e966 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -140,6 +140,18 @@ pub const Epoch = struct { _ = e.live.remove(addr); } + /// What is allocated and freed until `unpause` is no copy's: a delta + /// written into a replica's terminal while a copy is held (an emulator + /// is the authority's, outside every copy, and must outlive a rollback). + pub fn pause(e: *Epoch) bool { + defer e.on = false; + return e.on; + } + + pub fn unpause(e: *Epoch, was: bool) void { + e.on = was; + } + fn begin(e: *Epoch) void { std.debug.assert(!e.on); e.id +%= 1; diff --git a/src/screen_state.zig b/src/screen_state.zig index 51c2ec30..20ed7ad7 100644 --- a/src/screen_state.zig +++ b/src/screen_state.zig @@ -13,10 +13,15 @@ //! marks). A row's address is a hash of what the row shows, not of its blob, //! whose style ids are its source page's. An unchanged row costs 8 bytes. //! -//! One delta per peer is in flight, as FrameAck keeps one frame in flight -//! for the tty. The next delta is encoded against the state the peer -//! acknowledged, once it has, so a slow peer skips the states in between. -//! The peer holds the blobs of the state it acknowledged and no others. +//! Each state the authority sends is a version of its terminal (`Track`), +//! made once whatever the number of peers. A peer's next delta is against +//! the version it was last sent: the stream is ordered and loses nothing, +//! so the peer has that one by the time it applies the next. Several are +//! in flight (`bound`); acknowledgements free their room, and a peer at the +//! bound gets nothing until one comes, then the newest version, the ones +//! between skipped. Peers at the same base are sent the same bytes. A +//! replica holds the blobs of the state it applied last and no others; a +//! delta against another (one lost) is refused, and the peer started afresh. //! //! The replica writes each delta into a ghostty Terminal, which a replica's //! terminal pane draws as a local one (src/terminal.zig reads only that). @@ -120,23 +125,26 @@ fn pinOf(pages: anytype, top: u64, abs: u64) ?Pin { pub const Encoder = struct { gpa: std.mem.Allocator, scratch: ?Page = null, - meta: std.Io.Writer.Allocating, - pins: std.ArrayList(Pin) = .empty, + blob: std.Io.Writer.Allocating, + /// The rows a delta sends a blob for, and the addresses it lists once. needed: std.ArrayList(struct { pin: Pin, hash: Hash }) = .empty, + listed: std.AutoHashMapUnmanaged(Hash, void) = .empty, + tail: std.ArrayList(Pin) = .empty, pub fn init(gpa: std.mem.Allocator) Encoder { - return .{ .gpa = gpa, .meta = .init(gpa) }; + return .{ .gpa = gpa, .blob = .init(gpa) }; } pub fn deinit(e: *Encoder) void { if (e.scratch) |*s| s.deinit(); - e.meta.deinit(); - e.pins.deinit(e.gpa); + e.blob.deinit(); e.needed.deinit(e.gpa); + e.listed.deinit(e.gpa); + e.tail.deinit(e.gpa); } /// The PAGE record of `row` alone, its first `cols` cells. - fn blob(e: *Encoder, page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void { + fn rowBlob(e: *Encoder, page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void { var cap: vt.page.Capacity = if (e.scratch) |s| s.capacity else .{ .cols = cols, .rows = 1, .styles = 64 }; if (cap.cols != cols) cap = .{ .cols = cols, .rows = 1, .styles = 64 }; for (0..16) |_| { @@ -164,148 +172,245 @@ pub const Encoder = struct { } }; -/// What the authority knows of one peer. -pub const Peer = struct { - seq: u32 = 0, - in_flight: bool = false, - /// Never sent anything, or sent before a renumbering: the next delta - /// starts the replica afresh. - fresh: bool = true, - epoch: u32 = 0, - /// The active area's first row in the state it acknowledged. - top: u64 = 0, - /// The blobs the peer holds: those of the state it acknowledged. - known: std.AutoHashMapUnmanaged(Hash, void) = .empty, - /// Those of the delta in flight, which become `known` on its ack. - sent: std.AutoHashMapUnmanaged(Hash, void) = .empty, - - pub fn deinit(peer: *Peer, gpa: std.mem.Allocator) void { - peer.known.deinit(gpa); - peer.sent.deinit(gpa); +/// Deltas a peer may have in flight. At 207 ms and 60 frames a second about +/// 13 are; past the bound a peer gets nothing until an acknowledgement, and +/// then the newest state, the ones between skipped. +pub const bound = 32; + +/// What a peer holds once it has a version: the addresses of its active +/// rows and its meta. A delta against it sends no blob for these. +const Known = struct { + version: u32, + epoch: u32, + top: u64, + addrs: std.AutoHashMapUnmanaged(Hash, void) = .empty, +}; + +/// One terminal as the authority numbers it, for all of its peers: each +/// state it sends is a version, made once whatever the number of peers. +pub const Track = struct { + rows: Rows = .{}, + version: u32 = 0, + /// The emulator's change count the newest version was made at. + changes: u32 = 0, + /// The newest version: its active rows (pins, good while the emulator + /// is unchanged) and their addresses, and its meta. + pins: std.ArrayList(Pin) = .empty, + hashes: std.ArrayList(Hash) = .empty, + meta: std.Io.Writer.Allocating, + meta_hash: Hash = 0, + /// The newest versions, oldest first: the bases a peer's next delta may + /// have. A peer whose base has gone starts afresh. + known: std.ArrayList(Known) = .empty, + /// The last delta encoded, for the next peer at the same base. + cache: std.Io.Writer.Allocating, + cache_base: u32 = 0, + cache_version: u32 = 0, + + const kept = bound + 8; + + pub fn init(gpa: std.mem.Allocator) Track { + return .{ .meta = .init(gpa), .cache = .init(gpa) }; + } + + /// `t` is the terminal, or null when it is gone already (with its pins). + pub fn deinit(tr: *Track, gpa: std.mem.Allocator, t: ?*Terminal) void { + if (t) |term| tr.rows.deinit(term); + tr.pins.deinit(gpa); + tr.hashes.deinit(gpa); + tr.meta.deinit(); + for (tr.known.items) |*k| k.addrs.deinit(gpa); + tr.known.deinit(gpa); + tr.cache.deinit(); + } + + fn find(tr: *const Track, version: u32) ?*const Known { + if (version == 0) return null; + for (tr.known.items) |*k| if (k.version == version) return if (k.epoch == tr.rows.epoch) k else null; + return null; + } + + /// A version of `t` as it is now. + fn advance(tr: *Track, gpa: std.mem.Allocator, t: *Terminal, changes: u32) !void { + try tr.rows.update(t); + tr.version +%= 1; + if (tr.version == 0) tr.version = 1; + tr.changes = changes; + tr.meta.clearRetainingCapacity(); + { + var rw: snapshot.record.Writer = .init(gpa, &tr.meta.writer); + defer rw.deinit(); + try snapshot.terminal.encode(t, &rw); + } + tr.meta_hash = std.hash.Wyhash.hash(0, tr.meta.written()); + tr.pins.clearRetainingCapacity(); + tr.hashes.clearRetainingCapacity(); + var it = t.screens.active.pages.rowIterator(.right_down, .{ .active = .{} }, null); + while (it.next()) |p| { + try tr.pins.append(gpa, p); + try tr.hashes.append(gpa, rowHash(p.node.page(), p.rowAndCell().row, t.cols)); + } + if (tr.known.items.len == kept) { + tr.known.items[0].addrs.deinit(gpa); + _ = tr.known.orderedRemove(0); + } + var k: Known = .{ .version = tr.version, .epoch = tr.rows.epoch, .top = tr.rows.top }; + errdefer k.addrs.deinit(gpa); + try k.addrs.ensureTotalCapacity(gpa, @intCast(tr.hashes.items.len + 1)); + for (tr.hashes.items) |h| k.addrs.putAssumeCapacity(h, {}); + k.addrs.putAssumeCapacity(tr.meta_hash, {}); + try tr.known.append(gpa, k); } +}; + +/// What the authority knows of one peer of one terminal. +pub const Peer = struct { + /// The version last sent, which the next delta is against; 0: none, so + /// the next starts the replica afresh. + sent: u32 = 0, + /// The versions in flight, oldest first. + flight: [bound]u32 = undefined, + n: u8 = 0, + /// Every version up to `seq` has landed. pub fn ack(peer: *Peer, seq: u32) void { - if (!peer.in_flight or seq != peer.seq) return; - std.mem.swap(std.AutoHashMapUnmanaged(Hash, void), &peer.known, &peer.sent); - peer.in_flight = false; + var i: u8 = 0; + while (i < peer.n and peer.flight[i] <= seq) i += 1; + std.mem.copyForwards(u32, peer.flight[0 .. peer.n - i], peer.flight[i..peer.n]); + peer.n -= i; } - /// Start the peer afresh (it joined again, or lost its state). + /// Start the peer afresh: it lost its state, or never had one. pub fn reset(peer: *Peer) void { - peer.fresh = true; - peer.in_flight = false; - peer.known.clearRetainingCapacity(); + peer.* = .{}; } }; -/// The delta's fixed header: u32 seq, u8 flags, u32 epoch, u64 meta, u16 -/// cursor x and y, u8 cursor style, u8 pending wrap, the kitty keyboard -/// flags, u64 top, u64 history rows; then u16 rows and a u64 per active -/// row, u16 and a u64 per row of the tail (those that scrolled off the -/// active area since the acknowledged state, up to a screen of them, oldest -/// first), and a u16 blob count and each blob as u64 hash, u32 length, bytes. +/// The delta's fixed header: u32 seq, u32 base (0: none, the replica +/// starts afresh), u8 flags, u32 epoch, u64 meta, u16 cursor x and y, u8 +/// cursor style, u8 pending wrap, u8 the cursor's semantic content, the +/// kitty keyboard flags, u64 top, u64 history rows, u64 the viewport's top +/// as an absolute row (all ones: following the active area), u16 and the +/// caller's extra bytes; then u16 rows and a u64 per active row, u16 and a +/// u64 per row of the tail (those that scrolled off the active area since +/// the base, up to a screen of them, oldest first), and a u16 blob count +/// and each blob as u64 hash, u32 length, bytes. const flag_reset: u8 = 1; const KittyFlags = @FieldType(Screen, "kitty_keyboard"); +const following = std.math.maxInt(u64); -/// The delta for `peer` against what it acknowledged, onto `out`, or false -/// (nothing written) while its last delta is in flight. -pub fn encode(e: *Encoder, peer: *Peer, n: *Rows, t: *Terminal, out: *std.Io.Writer) !bool { - if (peer.in_flight) return false; - const gpa = e.gpa; - try n.update(t); - if (peer.epoch != n.epoch) peer.reset(); - const reset = peer.fresh; - peer.sent.clearRetainingCapacity(); - - e.meta.clearRetainingCapacity(); - { - var rw: snapshot.record.Writer = .init(gpa, &e.meta.writer); - defer rw.deinit(); - try snapshot.terminal.encode(t, &rw); +/// The delta that takes `peer` from what it was last sent to `t` as it is, +/// onto `out`; false (nothing written) when it has that already, or has +/// `bound` in flight. `changes` counts the emulator's writes (a new count +/// is a new version); `extra` rides along (the caller's own state of the +/// terminal), the same for every peer of one version. A peer at the same +/// base as the last one encoded is sent the same bytes. +pub fn encode(e: *Encoder, tr: *Track, peer: *Peer, t: *Terminal, changes: u32, extra: []const u8, out: *std.Io.Writer) !bool { + if (tr.version == 0 or changes != tr.changes) try tr.advance(e.gpa, t, changes); + if (peer.sent == tr.version or peer.n == bound) return false; + const base = tr.find(peer.sent); + const base_version = if (base) |b| b.version else 0; + if (tr.cache_version != tr.version or tr.cache_base != base_version) { + tr.cache.clearRetainingCapacity(); + try write(e, tr, base, t, extra, &tr.cache.writer); + tr.cache_version = tr.version; + tr.cache_base = base_version; } - const meta = std.hash.Wyhash.hash(0, e.meta.written()); - try peer.sent.put(gpa, meta, {}); + try out.writeAll(tr.cache.written()); + peer.sent = tr.version; + peer.flight[peer.n] = tr.version; + peer.n += 1; + return true; +} +fn write(e: *Encoder, tr: *Track, base: ?*const Known, t: *Terminal, extra: []const u8, out: *std.Io.Writer) !void { + const gpa = e.gpa; + const reset = base == null; const screen = t.screens.active; const pages = &t.screens.get(.primary).?.pages; - try out.writeInt(u32, peer.seq +% 1, .little); + const history = pages.total_rows - pages.rows; + const top = tr.rows.top; + try out.writeInt(u32, tr.version, .little); + try out.writeInt(u32, if (base) |b| b.version else 0, .little); try out.writeByte(if (reset) flag_reset else 0); - try out.writeInt(u32, n.epoch, .little); - try out.writeInt(u64, meta, .little); + try out.writeInt(u32, tr.rows.epoch, .little); + try out.writeInt(u64, tr.meta_hash, .little); try out.writeInt(u16, screen.cursor.x, .little); try out.writeInt(u16, screen.cursor.y, .little); try out.writeByte(@intFromEnum(screen.cursor.cursor_style)); try out.writeByte(@intFromBool(screen.cursor.pending_wrap)); + try out.writeByte(@intFromEnum(screen.cursor.semantic_content)); // ponytail: raw bytes, as the hello refuses a peer of another build. try out.writeAll(std.mem.asBytes(&screen.kitty_keyboard)); - try out.writeInt(u64, n.top, .little); - const history = pages.total_rows - pages.rows; + try out.writeInt(u64, top, .little); try out.writeInt(u64, history, .little); - try out.writeInt(u16, t.rows, .little); + try out.writeInt(u64, if (pages.viewport == .active) following else top - history + pages.scrollbar().offset, .little); + try out.writeInt(u16, @intCast(extra.len), .little); + try out.writeAll(extra); - // The active rows, then the tail: what scrolled off since the state - // acknowledged, which may have changed after it was sent. - const tail: u16 = if (reset) 0 else @intCast(@min(n.top -| peer.top, t.rows, history)); - e.pins.clearRetainingCapacity(); - var it = screen.pages.rowIterator(.right_down, .{ .active = .{} }, null); - while (it.next()) |p| try e.pins.append(gpa, p); - for (0..tail) |j| try e.pins.append(gpa, pages.getTopLeft(.active).up(tail - j).?); + // The active rows, then the tail: what scrolled off since the base, + // which may have changed after it was sent. + e.listed.clearRetainingCapacity(); e.needed.clearRetainingCapacity(); - for (e.pins.items, 0..) |p, i| { - if (i == t.rows) try out.writeInt(u16, tail, .little); + const tail: u16 = if (base) |b| @intCast(@min(top -| b.top, t.rows, history)) else 0; + e.tail.clearRetainingCapacity(); + for (0..tail) |j| try e.tail.append(gpa, pages.getTopLeft(.active).up(tail - j).?); + try out.writeInt(u16, @intCast(tr.pins.items.len), .little); + for (tr.pins.items, tr.hashes.items) |p, h| { + try out.writeInt(u64, h, .little); + try needBlob(e, base, p, h); + } + try out.writeInt(u16, tail, .little); + for (e.tail.items) |p| { const h = rowHash(p.node.page(), p.rowAndCell().row, t.cols); try out.writeInt(u64, h, .little); - // Every address listed is held once this is acknowledged; a blob - // goes only for one not held already, once. - if ((try peer.sent.getOrPut(gpa, h)).found_existing or peer.known.contains(h)) continue; - try e.needed.append(gpa, .{ .pin = p, .hash = h }); + try needBlob(e, base, p, h); } - if (tail == 0) try out.writeInt(u16, 0, .little); - const meta_new = !peer.known.contains(meta); + const meta_new = if (base) |b| !b.addrs.contains(tr.meta_hash) else true; try out.writeInt(u16, @intCast(e.needed.items.len + @intFromBool(meta_new)), .little); if (meta_new) { - try out.writeInt(u64, meta, .little); - try out.writeInt(u32, @intCast(e.meta.written().len), .little); - try out.writeAll(e.meta.written()); + try out.writeInt(u64, tr.meta_hash, .little); + try out.writeInt(u32, @intCast(tr.meta.written().len), .little); + try out.writeAll(tr.meta.written()); } - var blob: std.Io.Writer.Allocating = .init(gpa); - defer blob.deinit(); for (e.needed.items) |need| { - blob.clearRetainingCapacity(); - try e.blob(need.pin.node.page(), need.pin.rowAndCell().row, t.cols, &blob.writer); + e.blob.clearRetainingCapacity(); + try e.rowBlob(need.pin.node.page(), need.pin.rowAndCell().row, t.cols, &e.blob.writer); try out.writeInt(u64, need.hash, .little); - try out.writeInt(u32, @intCast(blob.written().len), .little); - try out.writeAll(blob.written()); + try out.writeInt(u32, @intCast(e.blob.written().len), .little); + try out.writeAll(e.blob.written()); } - peer.top = n.top; - peer.seq +%= 1; - peer.in_flight = true; - peer.fresh = false; - peer.epoch = n.epoch; - return true; +} + +/// A blob goes for an address the base does not hold, once. +fn needBlob(e: *Encoder, base: ?*const Known, p: Pin, h: Hash) !void { + if ((try e.listed.getOrPut(e.gpa, h)).found_existing) return; + if (base) |b| if (b.addrs.contains(h)) return; + try e.needed.append(e.gpa, .{ .pin = p, .hash = h }); } /// The primary screen's rows `[lo, hi)` the authority still has, as u32 /// epoch, u32 count, then each as u64 row, u32 length, blob: a replica's /// fetch of history it holds as holes. // ponytail: every row its blob, none by address: phase 6's content cache. -pub fn encodeRows(e: *Encoder, n: *Rows, t: *Terminal, lo: u64, hi: u64, out: *std.Io.Writer) !void { - try n.update(t); +pub fn encodeRows(e: *Encoder, tr: *Track, t: *Terminal, lo: u64, hi: u64, out: *std.Io.Writer) !void { + try tr.rows.update(t); var blobs: std.Io.Writer.Allocating = .init(e.gpa); defer blobs.deinit(); var count: u32 = 0; var abs = lo; - while (abs < hi) : (abs += 1) { - const p = n.pinAt(t, abs) orelse continue; + // The active area is the deltas'. + while (abs < @min(hi, tr.rows.top)) : (abs += 1) { + const p = tr.rows.pinAt(t, abs) orelse continue; const start = blobs.written().len; try blobs.writer.writeInt(u64, abs, .little); try blobs.writer.writeInt(u32, 0, .little); - try e.blob(p.node.page(), p.rowAndCell().row, t.cols, &blobs.writer); + try e.rowBlob(p.node.page(), p.rowAndCell().row, t.cols, &blobs.writer); const len: u32 = @intCast(blobs.written().len - start - 12); std.mem.writeInt(u32, blobs.written()[start + 8 ..][0..4], len, .little); count += 1; } - try out.writeInt(u32, n.epoch, .little); + try out.writeInt(u32, tr.rows.epoch, .little); try out.writeInt(u32, count, .little); try out.writeAll(blobs.written()); } @@ -337,21 +442,32 @@ pub const Replica = struct { if (r.scratch) |*s| s.deinit(); } - /// Write one delta into `t`; the seq to acknowledge. - pub fn apply(r: *Replica, gpa: std.mem.Allocator, io: std.Io, t: *Terminal, bytes: []const u8) !u32 { + pub const Applied = struct { seq: u32, extra: []const u8 }; + + /// Write one delta into `t`: the seq to acknowledge, and the caller's + /// extra bytes (borrowed from `bytes`). error.BaseMismatch: the delta + /// is against a state this replica does not have (one was lost, or it + /// started afresh), so `t` is as it was and it must be sent a reset. + pub fn apply(r: *Replica, gpa: std.mem.Allocator, io: std.Io, t: *Terminal, bytes: []const u8) !Applied { var in: std.Io.Reader = .fixed(bytes); const seq = try in.takeInt(u32, .little); + const base = try in.takeInt(u32, .little); const flags = try in.takeByte(); + const reset = flags & flag_reset != 0; + if (!reset and base != r.seq) return error.BaseMismatch; const epoch = try in.takeInt(u32, .little); const meta = try in.takeInt(u64, .little); const cx = try in.takeInt(u16, .little); const cy = try in.takeInt(u16, .little); const style = try in.takeByte(); const wrap = try in.takeByte(); + const semantic = try in.takeByte(); var kitty: KittyFlags = undefined; @memcpy(std.mem.asBytes(&kitty), try in.take(@sizeOf(KittyFlags))); const top = try in.takeInt(u64, .little); const history = try in.takeInt(u64, .little); + const viewport = try in.takeInt(u64, .little); + const extra = try in.take(try in.takeInt(u16, .little)); const nrows = try in.takeInt(u16, .little); const hashes = try in.take(@as(usize, nrows) * 8); const tail = try in.takeInt(u16, .little); @@ -371,18 +487,21 @@ pub const Replica = struct { } }.of; - if (flags & flag_reset != 0 or meta != r.meta) { + if (reset or meta != r.meta) { var reader: std.Io.Reader = .fixed(try blobOf(r, &fresh, meta)); var next = try snapshot.terminal.decode(&reader, try snapshot.record.nextHeader(&reader), io, gpa); - if (flags & flag_reset != 0) { + if (reset) { std.mem.swap(Terminal, t, &next); next.deinit(gpa); for (&r.held) |*h| h.clearRetainingCapacity(); r.holes.clearRetainingCapacity(); r.top = top; r.epoch = epoch; - // The authority's history, blank, to be fetched. + // The authority's history, blank, to be fetched. Its own + // limit is the authority's row count (below), not bytes: + // its pages may pack rows otherwise. const primary = t.screens.get(.primary).?; + primary.pages.setMaxBytes(null); try scrollUp(primary, history); if (history > 0) try r.holes.append(gpa, .{ top -| history, top }); } else { @@ -394,16 +513,12 @@ pub const Replica = struct { if (epoch != r.epoch) return error.Renumbered; // The primary screen scrolled `top - r.top` rows since the last - // delta: as many go up into the history here (no more than it and - // the screen hold). - // ponytail: the history's extent then follows this terminal's own - // pruning, under the authority's limit: a page more or less than the - // authority's, and the oldest rows may be some it has dropped. The tail is what they are now; any older than - // the tail are holes, never seen or seen before they last changed. + // delta: as many go up into the history here (no more than its + // history holds and the screen), each beyond the tail a hole. const primary = t.screens.get(.primary).?; if (top > r.top) { const k = top - r.top; - try scrollUp(primary, @min(k, @as(u64, t.rows) + history + 1)); + try scrollUp(primary, @min(k, @as(u64, t.rows) + history)); const held = &r.held[0]; if (k >= held.items.len) held.clearRetainingCapacity() else { std.mem.copyForwards(Hash, held.items, held.items[@intCast(k)..]); @@ -412,17 +527,18 @@ pub const Replica = struct { if (top - tail > r.top) try r.holes.append(gpa, .{ r.top, top - tail }); r.top = top; } + // The history as long as the authority's (it prunes a page at a + // time, and an ED 3 takes it all): row numbers and the scrollbar + // say the same on both. ponytail: one pruned shorter than that + // (its pages packed otherwise) stays shorter. + const have = primary.pages.total_rows - primary.pages.rows; + if (have > history) primary.pages.eraseHistory(.{ .history = .{ .y = @intCast(have - history - 1) } }); + r.trimHoles(primary); for (0..tail) |j| { const p = pinOf(&primary.pages, top, top - tail + j) orelse continue; const h = std.mem.readInt(u64, tails[j * 8 ..][0..8], .little); if (rowHash(p.node.page(), p.rowAndCell().row, t.cols) != h) try r.writeRow(gpa, primary, p, try blobOf(r, &fresh, h)); } - // The authority's history went (an ED3): so does this one's. - if (history == 0 and primary.pages.total_rows > primary.pages.rows) { - primary.pages.eraseHistory(null); - r.holes.clearRetainingCapacity(); - } - r.trimHoles(primary); const screen = t.screens.active; const held = &r.held[@intFromEnum(t.screens.active_key)]; @@ -439,7 +555,10 @@ pub const Replica = struct { screen.cursorAbsolute(@min(cx, t.cols - 1), @min(cy, t.rows - 1)); screen.cursor.cursor_style = @enumFromInt(style); screen.cursor.pending_wrap = wrap != 0; + screen.cursor.semantic_content = @enumFromInt(semantic); screen.kitty_keyboard = kitty; + const oldest = r.top -| (primary.pages.total_rows - primary.pages.rows); + primary.pages.scroll(if (viewport == following) .active else .{ .row = @intCast(viewport -| oldest) }); // Hold the blobs of this state, and no others. var keep: std.AutoHashMapUnmanaged(Hash, []u8) = .empty; @@ -459,7 +578,7 @@ pub const Replica = struct { r.blobs.deinit(gpa); r.blobs = keep; r.seq = seq; - return seq; + return .{ .seq = seq, .extra = extra }; } /// The holes in `[lo, hi)`: the rows to fetch before showing them. @@ -471,6 +590,15 @@ pub const Replica = struct { } } + /// The absolute row the viewport of `t`'s primary screen starts at, and + /// how many it shows. + pub fn shown(r: *const Replica, t: *Terminal) [2]u64 { + const pages = &t.screens.get(.primary).?.pages; + const sb = pages.scrollbar(); + const oldest = r.top -| (pages.total_rows - pages.rows); + return .{ oldest + sb.offset, oldest + sb.offset + sb.len }; + } + /// Write fetched history rows (`encodeRows`) into `t`. pub fn applyRows(r: *Replica, gpa: std.mem.Allocator, t: *Terminal, bytes: []const u8) !void { var in: std.Io.Reader = .fixed(bytes); @@ -479,7 +607,9 @@ pub const Replica = struct { for (0..try in.takeInt(u32, .little)) |_| { const abs = try in.takeInt(u64, .little); const blob = try in.take(try in.takeInt(u32, .little)); - if (abs >= r.top) continue; + // Only a hole is written: a row the replica holds is the + // authority's already, and newer than what this fetch saw. + if (abs >= r.top or !r.inHole(abs)) continue; const p = pinOf(&primary.pages, r.top, abs) orelse continue; try r.writeRow(gpa, primary, p, blob); try r.fill(gpa, abs); @@ -535,13 +665,18 @@ pub const Replica = struct { }; /// `k` blank rows onto the bottom of a screen's active area, its top `k` -/// going up into the history, as `k` linefeeds at the bottom would. -// ponytail: a row at a time, so a flood costs the replica up to its whole -// history's rows a delta (measured in `bench`); a bulk scroll if that shows. +/// going up into the history, as `k` linefeeds at the bottom would. A +/// flood's thousands are grown a row at a time without the cursor (the +/// page list's fast path, a counter), which is put back after. fn scrollUp(screen: *Screen, k: u64) !void { if (k == 0) return; screen.cursorAbsolute(0, screen.pages.rows - 1); - for (0..@intCast(k)) |_| try screen.cursorDownScroll(); + if (k <= screen.pages.rows or screen.no_scrollback or screen.cursor.style_id != 0) { + for (0..@intCast(k)) |_| try screen.cursorDownScroll(); + return; + } + for (0..@intCast(k)) |_| _ = try screen.pages.grow(); + screen.cursorReload(); } /// `rowHash` of a row never written. @@ -601,13 +736,16 @@ fn dumpRow(page: *Page, row: *Row, cols: u16, w: *std.Io.Writer) !void { } /// The state a replica must match: the terminal-wide state, the cursor, -/// the active screen's rows. -fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void { +/// the history's extent and the viewport, the active screen's rows. +pub fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void { const screen = t.screens.active; - try w.print("{d}x{d} {s} cursor {d},{d} {s} {} title {s} pwd {s}\n", .{ - t.cols, t.rows, @tagName(t.screens.active_key), - screen.cursor.x, screen.cursor.y, @tagName(screen.cursor.cursor_style), - screen.cursor.pending_wrap, t.getTitle() orelse "", t.getPwd() orelse "", + const sb = t.screens.get(.primary).?.pages.scrollbar(); + try w.print("{d}x{d} {s} cursor {d},{d} {s} {} {s} title {s} pwd {s} scrollbar {d} {d} {d}\n", .{ + t.cols, t.rows, @tagName(t.screens.active_key), + screen.cursor.x, screen.cursor.y, @tagName(screen.cursor.cursor_style), + screen.cursor.pending_wrap, @tagName(screen.cursor.semantic_content), t.getTitle() orelse "", + t.getPwd() orelse "", sb.total, sb.offset, + sb.len, }); try w.writeAll(std.mem.asBytes(&t.modes.values)); try w.writeAll(std.mem.asBytes(&screen.kitty_keyboard)); @@ -619,31 +757,38 @@ fn dumpScreen(t: *Terminal, w: *std.Io.Writer) !void { } /// An authority and its replica, fed one stream of pty bytes, the deltas -/// and fetches between them at random: a delta encoded at a random step and -/// applied a random number of steps later (so the states between are -/// skipped), random resizes of the authority, random fetches of holes. -/// After each delta, the replica's screen is the authority's as it was -/// encoded, and every history row it holds outside its holes is what the -/// authority holds at that absolute row. +/// and fetches between them at random: a delta encoded at a random step +/// (so the states between are skipped), several in flight and each landing +/// a random number of steps later, in order, one lost now and then (the +/// replica refuses the next and is started afresh), random resizes of the +/// authority, random fetches of holes. After each delta, the replica's +/// screen is the authority's as it was encoded, and every history row it +/// holds outside its holes is what the authority holds at that absolute +/// row. pub const Soak = struct { gpa: std.mem.Allocator, io: std.Io, a: *Terminal, stream: vt.TerminalStream, - rows: Rows = .{}, + track: Track, enc: Encoder, peer: Peer = .{}, + /// The authority's writes, as terminal.State counts them. + changes: u32 = 0, b: *Terminal, rep: Replica = .{}, prng: std.Random.DefaultPrng, - /// The delta in flight, the authority's dump when it was encoded, and - /// how many steps it waits before it lands. - delta: std.Io.Writer.Allocating, - expect: std.Io.Writer.Allocating, + /// The deltas in flight, oldest first, each with the authority's dump + /// when it was encoded and the step it lands at. + flight: std.ArrayList(struct { delta: []u8, expect: []u8, at: u64 }) = .empty, got: std.Io.Writer.Allocating, - wait: u32 = 0, + now: u64 = 0, resizes: bool = true, - stats: struct { deltas: u64 = 0, bytes: u64 = 0, fetched: u64 = 0, history_checked: u64 = 0 } = .{}, + drops: bool = true, + /// The replica refused a delta and the authority started it afresh: + /// what was in flight before is refused too. + refused: bool = false, + stats: struct { deltas: u64 = 0, bytes: u64 = 0, fetched: u64 = 0, history_checked: u64 = 0, lost: u64 = 0, refused: u64 = 0, most_in_flight: u64 = 0 } = .{}, pub fn init(gpa: std.mem.Allocator, io: std.Io, cols: u16, rows: u16, scrollback: usize, seed: u64) !*Soak { const s = try gpa.create(Soak); @@ -651,17 +796,18 @@ pub const Soak = struct { const a = try gpa.create(Terminal); a.* = try Terminal.init(io, gpa, .{ .cols = cols, .rows = rows, .max_scrollback_bytes = scrollback }); const b = try gpa.create(Terminal); - b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = scrollback }); + // Room to spare: its pages may pack rows otherwise, and it keeps the + // authority's history to the row. + b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = 2 * scrollback }); s.* = .{ .gpa = gpa, .io = io, .a = a, .stream = a.vtStream(), + .track = .init(gpa), .enc = .init(gpa), .b = b, .prng = .init(seed), - .delta = .init(gpa), - .expect = .init(gpa), .got = .init(gpa), }; return s; @@ -670,16 +816,18 @@ pub const Soak = struct { pub fn deinit(s: *Soak) void { const gpa = s.gpa; s.stream.deinit(); - s.rows.deinit(s.a); + s.track.deinit(gpa, s.a); s.a.deinit(gpa); gpa.destroy(s.a); s.b.deinit(gpa); gpa.destroy(s.b); s.enc.deinit(); - s.peer.deinit(gpa); s.rep.deinit(gpa); - s.delta.deinit(); - s.expect.deinit(); + for (s.flight.items) |f| { + gpa.free(f.delta); + gpa.free(f.expect); + } + s.flight.deinit(gpa); s.got.deinit(); gpa.destroy(s); } @@ -691,6 +839,7 @@ pub const Soak = struct { while (at < bytes.len) { const n = @min(bytes.len - at, 1 + random.uintLessThan(usize, 512)); s.stream.nextSlice(bytes[at..][0..n]); + s.changes +%= 1; at += n; try s.step(); } @@ -698,48 +847,82 @@ pub const Soak = struct { pub fn step(s: *Soak) !void { const random = s.prng.random(); + s.now += 1; if (s.resizes and random.uintLessThan(u32, 200) == 0) { try s.a.resize(s.gpa, .{ .cols = 10 + random.uintLessThan(u16, 200), .rows = 3 + random.uintLessThan(u16, 60) }); + s.changes +%= 1; } - if (!s.peer.in_flight) { - if (random.boolean()) return; // a state skipped - s.delta.clearRetainingCapacity(); - if (!try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer)) unreachable; - s.expect.clearRetainingCapacity(); - try dumpScreen(s.a, &s.expect.writer); - s.wait = random.uintLessThan(u32, 4); - s.stats.deltas += 1; - s.stats.bytes += s.delta.written().len; - return; - } - if (s.wait > 0) { - s.wait -= 1; - return; - } - try s.land(); + // A frame now and then; the states between are skipped. + if (random.boolean()) try s.send(s.now + random.uintLessThan(u64, 12)); + while (s.flight.items.len > 0 and s.flight.items[0].at <= s.now) try s.land(); if (random.uintLessThan(u32, 8) == 0) try s.fetch(); } - /// The delta in flight applied and acknowledged, and checked. - pub fn land(s: *Soak) !void { - if (!s.peer.in_flight) return; - s.peer.ack(try s.rep.apply(s.gpa, s.io, s.b, s.delta.written())); + /// A delta, if the peer is owed one, sent to land at step `at`. + fn send(s: *Soak, at: u64) !void { + var d: std.Io.Writer.Allocating = .init(s.gpa); + defer d.deinit(); + if (!try encode(&s.enc, &s.track, &s.peer, s.a, s.changes, "extra", &d.writer)) return; + var expect: std.Io.Writer.Allocating = .init(s.gpa); + defer expect.deinit(); + try dumpScreen(s.a, &expect.writer); + const last = if (s.flight.items.len > 0) s.flight.items[s.flight.items.len - 1].at else 0; + try s.flight.append(s.gpa, .{ .delta = try d.toOwnedSlice(), .expect = try expect.toOwnedSlice(), .at = @max(at, last) }); + s.stats.deltas += 1; + s.stats.bytes += s.flight.items[s.flight.items.len - 1].delta.len; + s.stats.most_in_flight = @max(s.stats.most_in_flight, s.flight.items.len); + } + + /// The oldest delta in flight applied (or lost), acknowledged, checked. + fn land(s: *Soak) !void { + const f = s.flight.orderedRemove(0); + defer s.gpa.free(f.delta); + defer s.gpa.free(f.expect); + if (s.drops and s.prng.random().uintLessThan(u32, 50) == 0) { + s.stats.lost += 1; + return; + } + const applied = s.rep.apply(s.gpa, s.io, s.b, f.delta) catch |err| switch (err) { + error.BaseMismatch => { + // Asked once: the authority starts it afresh. + if (!s.refused) s.peer.reset(); + s.refused = true; + s.stats.refused += 1; + return; + }, + else => return err, + }; + s.refused = false; + if (!std.mem.eql(u8, applied.extra, "extra")) return error.ExtraLost; + s.peer.ack(applied.seq); s.got.clearRetainingCapacity(); try dumpScreen(s.b, &s.got.writer); - if (!std.mem.eql(u8, s.expect.written(), s.got.written())) { - reportDiff(s.expect.written(), s.got.written()); + if (!std.mem.eql(u8, f.expect, s.got.written())) { + reportDiff(f.expect, s.got.written()); return error.ReplicaDiffers; } try s.checkHistory(); } + /// Everything in flight landed, then a last delta of the end, until the + /// replica holds it: what the replica shows at quiescence. + fn settle(s: *Soak) !void { + s.drops = false; + for (0..4) |_| { + while (s.flight.items.len > 0) try s.land(); + try s.send(0); + if (s.flight.items.len == 0) return; + } + return error.NeverSettled; + } + /// Every history row the replica holds, outside its holes and inside /// what the authority still has, is the authority's (rows in history /// never change; a resize renumbers and starts the replica afresh). fn checkHistory(s: *Soak) !void { // Numbered as of now: the authority may have scrolled on since. - try s.rows.update(s.a); - if (s.rep.epoch != s.rows.epoch) return; + try s.track.rows.update(s.a); + if (s.rep.epoch != s.track.rows.epoch) return; const pages = &s.b.screens.get(.primary).?.pages; const have = pages.total_rows - pages.rows; var ra: std.Io.Writer.Allocating = .init(s.gpa); @@ -751,7 +934,7 @@ pub const Soak = struct { const abs = s.rep.top - d; if (s.rep.inHole(abs)) continue; const pb = pinOf(pages, s.rep.top, abs) orelse continue; - const pa = s.rows.pinAt(s.a, abs) orelse continue; + const pa = s.track.rows.pinAt(s.a, abs) orelse continue; ra.clearRetainingCapacity(); rb.clearRetainingCapacity(); try dumpRow(pa.node.page(), pa.rowAndCell().row, s.a.cols, &ra.writer); @@ -774,7 +957,7 @@ pub const Soak = struct { const hi = @min(hole[1], lo + 1 + random.uintLessThan(u64, 80)); var out: std.Io.Writer.Allocating = .init(s.gpa); defer out.deinit(); - try encodeRows(&s.enc, &s.rows, s.a, lo, hi, &out.writer); + try encodeRows(&s.enc, &s.track, s.a, lo, hi, &out.writer); try s.rep.applyRows(s.gpa, s.b, out.written()); s.stats.fetched += hi - lo; try s.checkHistory(); @@ -795,18 +978,14 @@ fn reportDiff(want: []const u8, got: []const u8) void { } } -/// Drive one stream through a soak and land a last delta of its end. +/// Drive one stream through a soak, then settle: the replica's screen at +/// quiescence is the authority's. pub fn soak(gpa: std.mem.Allocator, io: std.Io, bytes: []const u8, cols: u16, rows: u16, scrollback: usize, seed: u64, resizes: bool) !@FieldType(Soak, "stats") { const s = try Soak.init(gpa, io, cols, rows, scrollback, seed); defer s.deinit(); s.resizes = resizes; try s.feed(bytes); - try s.land(); - s.delta.clearRetainingCapacity(); - _ = try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer); - s.expect.clearRetainingCapacity(); - try dumpScreen(s.a, &s.expect.writer); - try s.land(); + try s.settle(); return s.stats; } @@ -841,7 +1020,7 @@ fn perf(gpa: std.mem.Allocator, io: std.Io, dir_path: []const u8, w: *std.Io.Wri failed += 1; continue; }; - if (seed == 0) try w.print("screen-state {s} {d}x{d}: {d} bytes, {d} deltas, {d} wire bytes, {d} history rows checked, {d} fetched\n", .{ entry.name, cols, rows, bytes.len, st.deltas, st.bytes, st.history_checked, st.fetched }); + if (seed == 0) try w.print("screen-state {s} {d}x{d}: {d} bytes, {d} deltas ({d} lost, {d} refused, {d} in flight at most), {d} wire bytes, {d} history rows checked, {d} fetched\n", .{ entry.name, cols, rows, bytes.len, st.deltas, st.lost, st.refused, st.most_in_flight, st.bytes, st.history_checked, st.fetched }); } } try w.print("screen-state corpus: {d} streams x 3 seeds, {d} failed\n", .{ files, failed }); @@ -858,8 +1037,6 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void { defer stream.deinit(); var enc: Encoder = .init(gpa); defer enc.deinit(); - var n: Rows = .{}; - defer n.deinit(t); var out: std.Io.Writer.Allocating = .init(gpa); defer out.deinit(); var line: [1024]u8 = undefined; @@ -868,6 +1045,7 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void { var same: [200]u64 = undefined; var full_bytes: usize = 0; var same_bytes: usize = 0; + var changes: u32 = 0; for (&full, &same, 0..) |*f, *u, rep| { for (0..60) |y| { var lw: std.Io.Writer = .fixed(&line); @@ -875,17 +1053,19 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void { while (lw.end < 190) try lw.writeAll("\x1b[1mbold\x1b[22m text "); stream.nextSlice(lw.buffered()); } + changes += 1; + var tr: Track = .init(gpa); + defer tr.deinit(gpa, t); var peer: Peer = .{}; - defer peer.deinit(gpa); out.clearRetainingCapacity(); var t0 = std.Io.Clock.awake.now(io).nanoseconds; - _ = try encode(&enc, &peer, &n, t, &out.writer); + _ = try encode(&enc, &tr, &peer, t, changes, "", &out.writer); f.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0); full_bytes = out.written().len; - peer.ack(peer.seq); + // The same screen again as a new version: every row held. out.clearRetainingCapacity(); t0 = std.Io.Clock.awake.now(io).nanoseconds; - _ = try encode(&enc, &peer, &n, t, &out.writer); + _ = try encode(&enc, &tr, &peer, t, changes + 1, "", &out.writer); u.* = @intCast(std.Io.Clock.awake.now(io).nanoseconds - t0); same_bytes = out.written().len; } @@ -893,39 +1073,77 @@ fn bench(gpa: std.mem.Allocator, io: std.Io, w: *std.Io.Writer) !void { std.mem.sort(u64, &same, {}, std.sort.asc(u64)); try w.print("screen-state encode 200x60, every row new: p50 {d} us p99 {d} us, {d} bytes\n", .{ full[100] / 1000, full[198] / 1000, full_bytes }); try w.print("screen-state encode 200x60, nothing new: p50 {d} us p99 {d} us, {d} bytes\n", .{ same[100] / 1000, same[198] / 1000, same_bytes }); + try w.flush(); - // Floods: a second of output as fast as ghostty takes it, a delta every - // 16 ms when the last is acknowledged (by a replica applying it at once). + // Floods: a second of output as fast as ghostty takes it, a frame every + // 16 ms: one version, a delta for each peer (the same bytes for peers + // at the same base), each replica applying its own at once. const yes = try yesStream(gpa, 1 << 16); defer gpa.free(yes); const shell = try shellStream(gpa); defer gpa.free(shell); - for ([_]struct { name: []const u8, bytes: []const u8 }{ .{ .name = "yes", .bytes = yes }, .{ .name = "varied text", .bytes = shell } }) |flood| { - const s = try Soak.init(gpa, io, 200, 60, 16 << 20, 0); - defer s.deinit(); + for ([_]struct { name: []const u8, bytes: []const u8 }{ .{ .name = "yes", .bytes = yes }, .{ .name = "varied text", .bytes = shell } }) |flood| for ([_]usize{ 1, 3 }) |npeers| { + const a = try gpa.create(Terminal); + defer gpa.destroy(a); + a.* = try Terminal.init(io, gpa, .{ .cols = 200, .rows = 60, .max_scrollback_bytes = 16 << 20 }); + defer a.deinit(gpa); + var as = a.vtStream(); + defer as.deinit(); + var tr: Track = .init(gpa); + defer tr.deinit(gpa, a); + var peers: [3]Peer = @splat(.{}); + var reps: [3]Replica = @splat(.{}); + var bs: [3]Terminal = undefined; + for (bs[0..npeers]) |*b| b.* = try Terminal.init(io, gpa, .{ .cols = 2, .rows = 2, .max_scrollback_bytes = 32 << 20 }); + defer for (bs[0..npeers], reps[0..npeers]) |*b, *r| { + b.deinit(gpa); + r.deinit(gpa); + }; + var applies: std.ArrayList(u64) = .empty; + defer applies.deinit(gpa); + var frames: std.ArrayList(u64) = .empty; + defer frames.deinit(gpa); const start = std.Io.Clock.awake.now(io).nanoseconds; var next = start; var fed: u64 = 0; var deltas: u64 = 0; var wire: u64 = 0; - var apply_ns: u64 = 0; + var version: u32 = 0; while (true) { const now = std.Io.Clock.awake.now(io).nanoseconds; if (now - start >= std.time.ns_per_s) break; - s.stream.nextSlice(flood.bytes); + as.nextSlice(flood.bytes); + version += 1; fed += flood.bytes.len; if (now < next) continue; next += 16 * std.time.ns_per_ms; - s.delta.clearRetainingCapacity(); - _ = try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer); - const a0 = std.Io.Clock.awake.now(io).nanoseconds; - s.peer.ack(try s.rep.apply(gpa, io, s.b, s.delta.written())); - apply_ns += @intCast(std.Io.Clock.awake.now(io).nanoseconds - a0); - deltas += 1; - wire += s.delta.written().len; + var frame_ns: u64 = 0; + for (peers[0..npeers], reps[0..npeers], bs[0..npeers]) |*peer, *rep, *b| { + out.clearRetainingCapacity(); + const e0 = std.Io.Clock.awake.now(io).nanoseconds; + if (!try encode(&enc, &tr, peer, a, version, "", &out.writer)) continue; + frame_ns += @intCast(std.Io.Clock.awake.now(io).nanoseconds - e0); + const a0 = std.Io.Clock.awake.now(io).nanoseconds; + peer.ack((try rep.apply(gpa, io, b, out.written())).seq); + try applies.append(gpa, @intCast(std.Io.Clock.awake.now(io).nanoseconds - a0)); + deltas += 1; + wire += out.written().len; + } + try frames.append(gpa, frame_ns); } - try w.print("screen-state flood of {s}: {d} MB/s of output, {d} deltas/s, {d} wire bytes/s ({d} a delta), replica apply {d} us a delta\n", .{ flood.name, fed / 1_000_000, deltas, wire, wire / @max(1, deltas), apply_ns / @max(1, deltas) / 1000 }); - } + std.mem.sort(u64, applies.items, {}, std.sort.asc(u64)); + std.mem.sort(u64, frames.items, {}, std.sort.asc(u64)); + const p = struct { + fn at(s: []const u64, q: usize) u64 { + return if (s.len == 0) 0 else s[@min(s.len - 1, s.len * q / 100)] / 1000; + } + }.at; + try w.print("screen-state flood of {s}, {d} peer(s): {d} MB/s of output, {d} deltas/s a peer, {d} wire bytes/s a peer ({d} a delta); encode a frame, all peers: p50 {d} us p99 {d} us; apply a delta p50 {d} us p99 {d} us\n", .{ + flood.name, npeers, fed / 1_000_000, deltas / npeers, wire / npeers, + wire / @max(1, deltas), p(frames.items, 50), p(frames.items, 99), p(applies.items, 50), + p(applies.items, 99), + }); + }; try w.flush(); } @@ -942,7 +1160,7 @@ test "recorded streams through replicas, and the encode's cost (PARDES_SCREEN_ST /// A shell's: prompts marked (OSC 133), colours of the three kinds, wide /// and combined graphemes, hyperlinks, tabs, a title and a directory, long /// lines that wrap, and a clear (ED2, ED3) now and then. -fn shellStream(gpa: std.mem.Allocator) ![]u8 { +pub fn shellStream(gpa: std.mem.Allocator) ![]u8 { var out: std.Io.Writer.Allocating = .init(gpa); errdefer out.deinit(); const w = &out.writer; @@ -965,7 +1183,7 @@ fn shellStream(gpa: std.mem.Allocator) ![]u8 { /// A full-screen program's: the alternate screen and its modes, a status /// line, a scrolling region scrolled both ways, lines inserted and /// deleted, cursor shapes, the kitty keyboard pushed and popped. -fn tuiStream(gpa: std.mem.Allocator) ![]u8 { +pub fn tuiStream(gpa: std.mem.Allocator) ![]u8 { var out: std.Io.Writer.Allocating = .init(gpa); errdefer out.deinit(); const w = &out.writer; @@ -983,7 +1201,7 @@ fn tuiStream(gpa: std.mem.Allocator) ![]u8 { return out.toOwnedSlice(); } -fn yesStream(gpa: std.mem.Allocator, lines: usize) ![]u8 { +pub fn yesStream(gpa: std.mem.Allocator, lines: usize) ![]u8 { const out = try gpa.alloc(u8, lines * 3); for (0..lines) |i| @memcpy(out[i * 3 ..][0..3], "y\r\n"); return out; @@ -1021,20 +1239,24 @@ test "under a flood a delta is a screen of hashes: an unchanged row costs its ad const s = try Soak.init(gpa, testing.io, 200, 60, 1 << 20, 1); defer s.deinit(); s.resizes = false; + s.drops = false; const yes = try yesStream(gpa, 10_000); defer gpa.free(yes); + var last: []u8 = &.{}; + defer gpa.free(last); for (0..3) |_| { s.stream.nextSlice(yes); - s.delta.clearRetainingCapacity(); - try testing.expect(try encode(&s.enc, &s.peer, &s.rows, s.a, &s.delta.writer)); - s.expect.clearRetainingCapacity(); - try dumpScreen(s.a, &s.expect.writer); + s.changes += 1; + try s.send(0); + try testing.expectEqual(@as(usize, 1), s.flight.items.len); + gpa.free(last); + last = try gpa.dupe(u8, s.flight.items[0].delta); try s.land(); } // The last: 60 rows and the tail's 60, of hashes the replica holds, no // blob; the header and counts around them. - const d = s.delta.written(); - const at = 4 + 1 + 4 + 8 + 2 + 2 + 1 + 1 + @sizeOf(KittyFlags) + 8 + 8; + const d = last; + const at = 4 + 4 + 1 + 4 + 8 + 2 + 2 + 1 + 1 + 1 + @sizeOf(KittyFlags) + 8 + 8 + 8 + 2 + "extra".len; const nrows = std.mem.readInt(u16, d[at..][0..2], .little); const tail = std.mem.readInt(u16, d[at + 2 + nrows * 8 ..][0..2], .little); const blobs = std.mem.readInt(u16, d[at + 4 + (nrows + tail) * 8 ..][0..2], .little); @@ -1044,6 +1266,27 @@ test "under a flood a delta is a screen of hashes: an unchanged row costs its ad try testing.expect(s.rep.holes.items.len > 0); } +test "several deltas in flight land in order, and a peer at the bound waits for an acknowledgement" { + const gpa = testing.allocator; + const s = try Soak.init(gpa, testing.io, 80, 24, 1 << 20, 2); + defer s.deinit(); + s.resizes = false; + s.drops = false; + var line: [64]u8 = undefined; + for (0..bound + 5) |i| { + s.stream.nextSlice(try std.fmt.bufPrint(&line, "line {d}\r\n", .{i})); + s.changes += 1; + try s.send(1000); + } + // The bound's worth went; the rest wait, and are skipped. + try testing.expectEqual(@as(usize, bound), s.flight.items.len); + try s.land(); + try s.send(1000); + try testing.expectEqual(@as(usize, bound), s.flight.items.len); + try s.settle(); + try testing.expectEqual(@as(u64, 0), s.stats.refused); +} + test "a replica's terminal pane draws as its authority's does" { const pardes = @import("pardes.zig"); const gpa = testing.allocator; @@ -1065,9 +1308,8 @@ test "a replica's terminal pane draws as its authority's does" { var enc: Encoder = .init(gpa); defer enc.deinit(); var peer: Peer = .{}; - defer peer.deinit(gpa); - var rows: Rows = .{}; - defer rows.deinit(ta); + var tr: Track = .init(gpa); + defer tr.deinit(gpa, ta); var rep: Replica = .{}; defer rep.deinit(gpa); var delta: std.Io.Writer.Allocating = .init(gpa); @@ -1077,8 +1319,8 @@ test "a replica's terminal pane draws as its authority's does" { const bytes = try std.fmt.bufPrint(&line, "\x1b[1;3{d}m{d}\x1b[0m 漢字 e\u{301} \x1b[48;2;{d};40;60mbg\x1b[0m and then some text that wraps past the width of the pane\r\n", .{ i % 8, i, i * 4 % 256 }); a.update(.{ .output = .{ .pane = 0, .bytes = bytes } }); delta.clearRetainingCapacity(); - try testing.expect(try encode(&enc, &peer, &rows, ta, &delta.writer)); - peer.ack(try rep.apply(gpa, terminalIoForTest(), tb, delta.written())); + try testing.expect(try encode(&enc, &tr, &peer, ta, @intCast(i + 1), "", &delta.writer)); + peer.ack((try rep.apply(gpa, terminalIoForTest(), tb, delta.written())).seq); b.needs_frame = true; _ = fa.reset(.retain_capacity); _ = fb.reset(.retain_capacity); diff --git a/src/tape.zig b/src/tape.zig index 84bdce29..0609ce0b 100644 --- a/src/tape.zig +++ b/src/tape.zig @@ -150,6 +150,17 @@ pub const Tape = struct { dump_check: bool = false, dumps: usize = 0, dump_bytes: usize = 0, + /// Screen-state terminals (src/screen_state.zig, docs/next-daemon.md + /// phase 5): an authority recording for replicas, or a replica. A + /// terminal's emulator is the authority's alone: its output is recorded + /// without its bytes (they cross as screen state), its pty writes are + /// not recorded, and no digest covers it. A replica's core never writes + /// one but by `apply`. + screen_state: bool = false, + /// A digest as one word (screen-state replicas: every unit of a pty's + /// output carries one, at the pty's read rate), not one a field; what + /// differs is then not named. + whole_digest: bool = false, fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void { t.scratch.clearRetainingCapacity(); @@ -236,7 +247,12 @@ pub const Tape = struct { t.noteWrites(); t.wrap(core); } - t.record(.input, Input, input); + // A terminal's output crosses as screen state, not as its bytes. + if (t.screen_state and input.* == .update and input.update == .output) { + var bare = input.*; + bare.update.output.bytes = &.{}; + t.record(.input, Input, &bare); + } else t.record(.input, Input, input); return .{ .outer = true }; } @@ -251,7 +267,8 @@ pub const Tape = struct { t.record(.done, void, &{}); if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| { var parts: Parts = undefined; - const d = digestParts(core, &parts); + const whole = [1]u64{digestOf(core)}; + const d: []const u64 = if (t.whole_digest) &whole else digestParts(core, &parts); t.record(.digest, []const u64, &d); }; if (t.depth == 0) t.flush(); @@ -376,8 +393,9 @@ pub const Tape = struct { const want = walk.decode([]const u64, r, t.arena.allocator()) catch return; const p = t.core orelse return; var parts: Parts = undefined; - const got = digestParts(p, &parts); - if (!std.mem.eql(u64, got, want)) t.diverge("digest {d} differs in {s}", .{ t.digests, partsDiffer(got, want, t.arena.allocator()) }); + const whole = [1]u64{digestOf(p)}; + const got: []const u64 = if (want.len == 1) &whole else digestParts(p, &parts); + if (!std.mem.eql(u64, got, want)) t.diverge("digest {d} differs in {s}", .{ t.digests, if (want.len == 1) "the session (a digest of one word: run the authority with whole_digest off to name the field)" else partsDiffer(got, want, t.arena.allocator()) }); t.digests += 1; } @@ -653,6 +671,12 @@ fn Wrap(comptime i: usize) type { fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype) R { const t: *Tape = @ptrCast(@alignCast(ctx.?)); const name = host_fns[i]; + // A terminal's answers and what is typed at it from its output are the + // authority's to write, never a replica's: off the tape on both sides. + if (comptime std.mem.eql(u8, name, "pty_write")) if (t.screen_state and !t.speculating) { + if (!t.replay) @call(.auto, @field(t.real.vtable.*, name).?, .{t.real.ctx} ++ args); + return; + }; if (t.replay) { // A replica that never draws is never watched: it asks no one. if (comptime std.mem.eql(u8, name, "watched")) if (t.headless) return false; @@ -769,6 +793,17 @@ pub fn speculating() bool { return if (on) |t| t.speculating else false; } +/// Screen-state terminals, on either side (`Tape.screen_state`). +pub fn screenState() bool { + return if (on) |t| t.screen_state else false; +} + +/// A replica's core under screen-state terminals: its emulators are +/// written by `apply` alone, never by its own steps. +pub fn screenReplica() bool { + return if (on) |t| t.screen_state and (t.replay or t.speculating) else false; +} + /// What a speculation reached is the authority's: the input is undone and /// waits for the authority's order. pub fn poison() void { @@ -823,6 +858,16 @@ pub fn release(t: *Tape) void { if (t.kept_arena) |*k| k.deinit(); } +/// The session's digest recorded now: a batch of steps recorded without +/// one each (`no_digest`) checked once, at its end. +pub fn digestHere(t: *Tape) void { + const core = t.core orelse return; + var parts: Parts = undefined; + const whole = [1]u64{digestOf(core)}; + const d: []const u64 = if (t.whole_digest) &whole else digestParts(core, &parts); + t.record(.digest, []const u64, &d); +} + /// What was recorded since the last take; the tape's to reuse after. pub fn taken(t: *Tape) []const u8 { return t.buf.items; diff --git a/src/terminal.zig b/src/terminal.zig index bcb70110..6c3eeda7 100644 --- a/src/terminal.zig +++ b/src/terminal.zig @@ -158,6 +158,9 @@ pub const State = struct { mouse_cell: if (enabled) ?ghostty_vt.Coordinate else void = if (enabled) null else {}, /// The kitty graphics its program placed, as drawn (TerminalImages.zig). images: TerminalImages = if (images_enabled) .{} else {}, + /// Counts the emulator's writes (output, a resize, its view scrolled): + /// a new count is a new state for its replicas (screen_state.Track). + changes: u32 = 0, /// The emulator as its program has made it, for the replay digest /// (src/walk.zig): the active screen's text, how much history is above @@ -168,6 +171,15 @@ pub const State = struct { /// a replica's terminal is the authority's screen state from phase 5 /// on (docs/next-daemon.md). pub fn digest(s: *const State, h: *pardes.walk.Hasher) void { + if (comptime !enabled) return; + // Under screen-state terminals the emulator is the authority's, and + // a replica's is what the last delta made it: compared as screens + // (test/replicas.zig), not step by step. + if (pardes.tape.screenState()) return; + s.digestScreen(h); + } + + pub fn digestScreen(s: *const State, h: *pardes.walk.Hasher) void { if (comptime !enabled) return; const screen = s.vt.screens.active; const sb = screen.pages.scrollbar(); @@ -531,6 +543,41 @@ pub fn panFor(p: *const Pardes, pane: *const Pane, r: pardes.Rect) u16 { return @intCast(@min(pane.rows - shown, (at + 1) -| shown)); } +/// What pardes made of a terminal's stream that its emulator does not hold +/// (the OSC 133 cycle, MarkedHandler), for a replica's delta: phase u8, +/// started, prompts, declined u32, continuation and lost u8, a finished +/// command's seq u32 and status i32 (all ones: none; i32 min: no status). +// ponytail: the output pins stay the authority's (its 9P pty/run reads them). +pub const marks_len = 1 + 4 * 3 + 2 + 4 + 4; + +pub fn marksOf(state: *const State, buf: *[marks_len]u8) []const u8 { + if (comptime !enabled) return &.{}; + const m = &state.stream.handler; + var w: std.Io.Writer = .fixed(buf); + w.writeByte(@intFromEnum(m.phase)) catch unreachable; + inline for (.{ m.started, m.prompts, m.declined }) |n| w.writeInt(u32, n, .little) catch unreachable; + w.writeAll(&.{ @intFromBool(m.continuation), @intFromBool(m.lost) }) catch unreachable; + w.writeInt(u32, if (m.finished) |f| f.seq else std.math.maxInt(u32), .little) catch unreachable; + w.writeInt(i32, if (m.finished) |f| f.status orelse std.math.minInt(i32) else 0, .little) catch unreachable; + return w.buffered(); +} + +/// A replica's terminal takes its authority's marks (`marksOf`). +pub fn takeMarks(state: *State, bytes: []const u8) void { + if (comptime !enabled) return; + if (bytes.len != marks_len) return; + const m = &state.stream.handler; + m.phase = @enumFromInt(bytes[0]); + m.started = std.mem.readInt(u32, bytes[1..5], .little); + m.prompts = std.mem.readInt(u32, bytes[5..9], .little); + m.declined = std.mem.readInt(u32, bytes[9..13], .little); + m.continuation = bytes[13] != 0; + m.lost = bytes[14] != 0; + const seq = std.mem.readInt(u32, bytes[15..19], .little); + const status = std.mem.readInt(i32, bytes[19..23], .little); + m.finished = if (seq == std.math.maxInt(u32)) null else .{ .seq = seq, .status = if (status == std.math.minInt(i32)) null else status }; +} + /// A replica's speculation leaves an emulator be: it is the authority's /// (docs/next-daemon.md, phase 5), so the input waits for its order. fn authorityOnly() bool { @@ -545,6 +592,7 @@ pub fn scrollGrid(pane: *Pane, delta: i32) void { if (authorityOnly()) return; const state = pane.terminal orelse return; state.vt.screens.active.scroll(.{ .delta_row = delta }); + state.changes +%= 1; } /// Is the viewport already showing the last row of output? @@ -559,7 +607,9 @@ pub fn followOutput(pane: *Pane) void { if (comptime !enabled) return; if (authorityOnly()) return; const state = pane.terminal orelse return; + const moved = state.vt.screens.active.pages.viewport != .active; state.vt.screens.active.scroll(.active); + state.changes +%= @intFromBool(moved); } /// Reflow the grid. A failed reflow keeps the grid it had rather than dropping @@ -572,6 +622,9 @@ pub fn resizeGrid(pane: *Pane, gpa: std.mem.Allocator, cols: u16, rows: u16) voi pane.clearPointerSelection(button); pane.sel[button].state = .none; }; + // A replica's emulator is sized by its authority: the next delta says. + if (pardes.tape.screenReplica()) return; + state.changes +%= 1; state.vt.resize(gpa, .{ .cols = cols, .rows = rows }) catch {}; } @@ -801,6 +854,7 @@ pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { }); state.stream = .init(.{ .handler = .{ .inner = state.vt.vtHandler() }, .allocator = gpa }); state.reply_len = 0; + state.changes = 0; // Every field its default (create leaves them what the heap had, which // a digest then reads: two replicas must agree, src/replica.zig). state.reply_dropped = 0; @@ -856,6 +910,7 @@ pub fn reviveShell(pane: *Pane) void { /// then apply different views. fn ingest(pane: *Pane, bytes: []const u8) void { pane.terminal.?.stream.nextSlice(bytes); + pane.terminal.?.changes +%= 1; } test "replay ownership is terminal-only and construction rolls back on allocation failure" { @@ -1017,6 +1072,8 @@ pub fn feedOutput(p: *Pardes, pane: *Pane, bytes: []const u8) void { if (comptime !enabled) return; if (pane.terminal == null) return; if (authorityOnly()) return; + // A replica's emulator is what the authority's deltas make it. + if (pardes.tape.screenReplica()) return; const has_positions = pane.ovl != null or pane.body.cur_pinned or pane.body.vsel.active or pane.body.msel.active or pane.body.nsel > 0 or pane.body.last_edit != null or pane.look_at != null or pane.body.ed_undo_len > 0 or pane.body.ed_redo_len > 0 or pointerRowCount(pane) > 0; diff --git a/test/replicas.zig b/test/replicas.zig index cdb161e8..f3618cf1 100644 --- a/test/replicas.zig +++ b/test/replicas.zig @@ -5,18 +5,30 @@ //! puts them all in one, where they clash at every key: a stress of //! correctness, not a picture of a session. //! -//! zig build replicas -Dplatform=tty -- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207] [--first K] [--shared] +//! Terminals cross as screen state (src/screen_state.zig): the session's +//! shell pane runs a full-screen program and then a `yes` flood (`--flood` +//! MB of it) while the clients type, its output stepped by the authority +//! and sent to each replica as deltas, once a frame and before any input +//! the authority steps, each replica acknowledging them over its link and +//! asking for the rows it scrolls back into and does not hold. +//! +//! zig build replicas -Dplatform=tty -- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207] [--first K] [--flood MB] [--shared] //! //! Gates, per seed and RTT: no replica diverges (every confirmed unit's //! digests agree as it is replayed), and at quiescence every replica's -//! digest is the authority's. Reported per RTT: how inputs went (applied at -//! once, stopped at a host call, left to the authority), how units were -//! taken (fast path, rollback for a misprediction or another's input), and -//! what a speculative apply, a copy and a rollback cost against a frame. +//! digest is the authority's; every delta a replica applies leaves its +//! terminal what the authority's was at that version, and at quiescence it +//! is the authority's, cell for cell. Reported per RTT: how inputs went +//! (applied at once, stopped at a host call, left to the authority), how +//! units were taken (fast path, rollback for a misprediction or another's +//! input), what a speculative apply, a copy and a rollback cost against a +//! frame, and the terminals': deltas a second, wire bytes a second under +//! the flood, encode a frame (every peer), apply a delta. const std = @import("std"); const libc = std.c; const pardes = @import("pardes"); const replica = pardes.replica; +const screen_state = pardes.screen_state; const Key = pardes.Key; const gpa = std.heap.c_allocator; @@ -46,7 +58,7 @@ const Host = struct { } }; -const Kind = enum { input, to_authority, to_replica, echo }; +const Kind = enum { input, to_authority, to_replica, echo, frame, output, screen_down, screen_up }; const Msg = struct { at: u64, @@ -89,6 +101,21 @@ const Totals = struct { spec_ns: std.ArrayListUnmanaged(u64) = .empty, copy_ns: std.ArrayListUnmanaged(u64) = .empty, rollback_ns: std.ArrayListUnmanaged(u64) = .empty, + // Terminals. + apply_ns: std.ArrayListUnmanaged(u64) = .empty, + frame_ns: std.ArrayListUnmanaged(u64) = .empty, + deltas: u64 = 0, + delta_bytes: u64 = 0, + unit_bytes: u64 = 0, + /// Deltas the replicas applied while the flood ran. + flood_deltas: u64 = 0, + flood_us: u64 = 0, + flood_delta_bytes: u64 = 0, + flood_unit_bytes: u64 = 0, + fetched: u64 = 0, + resets: u64 = 0, + screens_wrong: u64 = 0, + screens_checked: u64 = 0, fn add(t: *Totals, s: *const replica.Stats) !void { t.inputs += s.inputs; @@ -105,14 +132,16 @@ const Totals = struct { try t.spec_ns.appendSlice(gpa, s.spec_ns.items); try t.copy_ns.appendSlice(gpa, s.copy_ns.items); try t.rollback_ns.appendSlice(gpa, s.rollback_ns.items); + try t.apply_ns.appendSlice(gpa, s.apply_ns.items); } }; -/// One client's next input: monkey.zig's mix, as events. -fn nextEvent(random: std.Random, buf: *[64]u8) pardes.Event { +/// One client's next input: monkey.zig's mix, as events, and now and then +/// a wheel over the shell pane, which scrolls its history into view. +fn nextEvent(random: std.Random, buf: *[64]u8, wheel_at: ?[2]u16) pardes.Event { const typed = "abcdefghijklmnopqrstuvwxyz0123456789 -_=+,:;()"; const normal = "hjklwbe0$xpuyoOiaAIdcv.nN%sC"; - switch (random.uintLessThan(u8, 40)) { + switch (random.uintLessThan(u8, 42)) { 0...15 => { buf[0] = typed[random.uintLessThan(usize, typed.len)]; return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; @@ -143,7 +172,11 @@ fn nextEvent(random: std.Random, buf: *[64]u8) pardes.Event { } }, 37 => return .{ .resize = .{ .cols = @intCast(random.intRangeAtMost(u16, 60, 120)), .rows = @intCast(random.intRangeAtMost(u16, 16, 40)) } }, 38 => return .{ .mouse = .{ .button = .left, .kind = .press, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, - else => return .{ .mouse = .{ .button = .left, .kind = .release, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, + 39 => return .{ .mouse = .{ .button = .left, .kind = .release, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, + else => { + const at = wheel_at orelse return .{ .key = .{ .cp = Key.escape } }; + return .{ .mouse = .{ .button = if (random.uintLessThan(u8, 3) == 0) .wheel_down else .wheel_up, .kind = .press, .col = at[0], .row = at[1] } }; + }, } } @@ -158,7 +191,16 @@ fn writeFile(path: [:0]const u8, lines: usize) !void { } } -const Run = struct { seed: u64, rtt_ms: u64, steps: usize, clients: u16, shared: bool }; +const Run = struct { seed: u64, rtt_ms: u64, steps: usize, clients: u16, shared: bool, flood_mb: u64 }; + +/// The terminal pane's screen as a hash of screen_state's dump of it. +fn screenHash(t: *pardes.panes.terminal.VtSlot) u64 { + var buf: [8192]u8 = undefined; + var h: std.Io.Writer.Hashing(std.hash.Wyhash) = .initHasher(.init(0), &buf); + screen_state.dumpScreen(t, &h.writer) catch {}; + h.writer.flush() catch {}; + return h.hasher.final(); +} fn run(r: Run, dir: []const u8, totals: *Totals) !void { if (trace) std.debug.print("seed {d} rtt {d} ms\n", .{ r.seed, r.rtt_ms }); @@ -176,13 +218,22 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { } // The tty's own boot (a raw shell, a text pane under it), then three // files looked at: keys go to the last, a pane's shell echoes. - const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty }, host.host()); + const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty }, host.host(), true); defer a.deinit(); + var screens: replica.Screens = .init(gpa); + defer screens.deinit(a.core); const first = try gpa.dupe(u8, try a.unit(0, 0)); defer gpa.free(first); var reps: [8]*replica.Replica = undefined; - for (reps[0..r.clients], 1..) |*rp, id| rp.* = try replica.Replica.init(gpa, @intCast(id), first); + var peers: [8]u16 = undefined; + for (reps[0..r.clients], peers[0..r.clients], 1..) |*rp, *peer, id| { + rp.* = try replica.Replica.init(gpa, @intCast(id), first, true); + peer.* = try screens.addPeer(); + } defer for (reps[0..r.clients]) |rp| rp.deinit(); + const shell: u8 = for (a.core.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.isTerminal()) break @intCast(id); + } else return error.NoShell; for (&paths) |*path| { var line: [300]u8 = undefined; const unit = try a.local(.{ .command = try std.fmt.bufPrint(&line, "Look {s}", .{std.mem.sliceTo(path, 0)}) }); @@ -195,26 +246,87 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { rp.view = opened.view; for (reps[0..r.clients]) |each| each.confirm(opened.unit); }; + // Where a wheel over the shell lands in the session's view (the first + // client's); the others' views put it elsewhere, and their wheels hit + // whatever is there. + const sr = a.core.rects[shell]; + const wheel_at: ?[2]u16 = if (sr.h > 2) .{ sr.x + sr.w / 2, sr.y + sr.h / 2 } else null; + + // What the shell's program prints: a full-screen program, then a flood + // of `yes`, read 4 KB at a time as a pty gives it. + const tui = try screen_state.tuiStream(gpa); + defer gpa.free(tui); + const yes = try screen_state.yesStream(gpa, @intCast(r.flood_mb * (1 << 20) / 3)); + defer gpa.free(yes); + const tui_at: u64 = 400_000; + const flood_at: u64 = 1_500_000; + var flood_end: u64 = 0; + var program: struct { bytes: []const u8 = &.{}, at: usize = 0 } = .{}; + // The authority's version of each terminal, as its screen showed then. + var versions: std.AutoHashMapUnmanaged(u64, u64) = .empty; + defer versions.deinit(gpa); + var flood_deltas: [8]u64 = @splat(0); + var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; - defer queue.deinit(gpa); + defer { + while (queue.pop()) |m| if (m.bytes.len > 0) gpa.free(m.bytes); + queue.deinit(gpa); + } var n: u64 = 0; const one_way = r.rtt_ms * 1000 / 2; const jitter = one_way / 10; var up: [8]Link = @splat(.{}); var down: [8]Link = @splat(.{}); var left: [8]usize = @splat(r.steps); - // Each client's first input, soon. - for (0..r.clients) |c| { - try queue.push(gpa, .{ .at = random.uintLessThan(u64, 200_000), .n = n, .kind = .input, .who = @intCast(c + 1), .bytes = &.{} }); - n += 1; - } + var typing: usize = r.clients; + const push = struct { + fn f(q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, m: Msg) !void { + var mm = m; + mm.n = nn.*; + nn.* += 1; + try q.push(gpa, mm); + } + }.f; + // Each client's first input, soon; the programs; the first frame. + for (0..r.clients) |c| try push(&queue, &n, .{ .at = random.uintLessThan(u64, 200_000), .n = 0, .kind = .input, .who = @intCast(c + 1), .bytes = &.{} }); + try push(&queue, &n, .{ .at = tui_at, .n = 0, .kind = .output, .who = 0, .bytes = &.{} }); + try push(&queue, &n, .{ .at = flood_at, .n = 0, .kind = .output, .who = 1, .bytes = &.{} }); + try push(&queue, &n, .{ .at = frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }); + var frames_left: u32 = 0; + var flood_units: u64 = 0; + + // What each peer is owed of the terminals, onto its link: before the + // authority steps an input, and once a frame. + var owed: std.ArrayListUnmanaged([]u8) = .empty; + defer owed.deinit(gpa); + const flushAll = struct { + fn f(sc: *replica.Screens, core: *pardes.Pardes, ps: []const u16, list: *std.ArrayListUnmanaged([]u8), q: *std.PriorityQueue(Msg, void, Msg.order), nn: *u64, now: u64, dl: []Link, rnd: std.Random, ow: u64, jt: u64, vs: *std.AutoHashMapUnmanaged(u64, u64), tot: *Totals) !void { + for (ps, 0..) |peer, c| { + list.clearRetainingCapacity(); + try sc.flush(core, peer, list); + for (list.items) |bytes| { + tot.deltas += 1; + tot.delta_bytes += bytes.len; + try push(q, nn, .{ .at = dl[c].arrive(rnd, now, ow, jt), .n = 0, .kind = .screen_down, .who = @intCast(c + 1), .bytes = bytes }); + } + } + // Each version as the authority's screen showed it. + for (&sc.tracks, 0..) |*slot, id| if (slot.*) |*tr| { + const key = @as(u64, tr.serial) << 32 | tr.track.version; + if (tr.track.version == 0 or vs.contains(key)) continue; + _ = core.panes[id] orelse continue; + try vs.put(gpa, key, screenHash(&tr.state.vt)); + }; + } + }.f; + while (queue.pop()) |m| { defer if (m.bytes.len > 0) gpa.free(m.bytes); switch (m.kind) { .input => { const c = m.who - 1; var buf: [64]u8 = undefined; - const ev = nextEvent(random, &buf); + const ev = nextEvent(random, &buf, if (c == 0) wheel_at else null); const before = reps[c].stats; const msg = try gpa.dupe(u8, try reps[c].input(ev)); if (trace) std.debug.print("{d} ms client {d}: {t} {s} -> {s}\n", .{ m.at / 1000, m.who, ev, switch (ev) { @@ -223,39 +335,96 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { .command => |t| t, else => "", }, if (reps[c].stats.speculated > before.speculated) "applied" else if (reps[c].stats.stopped > before.stopped) "STOPPED" else if (reps[c].stats.unspeculated > before.unspeculated) "view" else "waits" }); - try queue.push(gpa, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_authority, .who = m.who, .bytes = msg }); - n += 1; + try push(&queue, &n, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .to_authority, .who = m.who, .bytes = msg }); left[c] -= 1; if (left[c] > 0) { // A typist: keys 50-200 ms apart, a pause now and then. const gap: u64 = if (random.uintLessThan(u8, 12) == 0) random.intRangeAtMost(u64, 300_000, 1_500_000) else random.intRangeAtMost(u64, 50_000, 200_000); - try queue.push(gpa, .{ .at = m.at + gap, .n = n, .kind = .input, .who = m.who, .bytes = &.{} }); - n += 1; - } + try push(&queue, &n, .{ .at = m.at + gap, .n = 0, .kind = .input, .who = m.who, .bytes = &.{} }); + } else typing -= 1; }, - .to_authority, .echo => { - const unit = if (m.kind == .echo) - try a.local(.{ .output = .{ .pane = @intCast(m.who), .bytes = m.bytes } }) - else - try a.take(m.bytes); - for (0..r.clients) |c| { - const copy = try gpa.dupe(u8, unit); - try queue.push(gpa, .{ .at = down[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_replica, .who = @intCast(c + 1), .bytes = copy }); - n += 1; - } - for (host.echo.items) |e| { - try queue.push(gpa, .{ .at = m.at + 2_000, .n = n, .kind = .echo, .who = e.pane, .bytes = e.bytes }); - n += 1; - } + .to_authority, .echo, .output => { + const unit = switch (m.kind) { + .echo => echo: { + a.output(.{ .output = .{ .pane = @intCast(m.who), .bytes = m.bytes } }); + break :echo null; + }, + .output => out: { + // The program's next read, 4 KB, then the next a + // fraction of a millisecond on (ghostty's pace). + if (program.at == program.bytes.len) { + program = .{ .bytes = if (m.who == 0) tui else yes }; + } + const k = @min(program.bytes.len - program.at, if (m.who == 0) @as(usize, 700) else 4096); + const chunk = program.bytes[program.at..][0..k]; + program.at += k; + if (program.at < program.bytes.len) + try push(&queue, &n, .{ .at = m.at + if (m.who == 0) @as(u64, 3_000) else 450, .n = 0, .kind = .output, .who = m.who, .bytes = &.{} }) + else if (m.who == 1) flood_end = m.at; + if (m.who == 1) flood_units += 1; + a.output(.{ .output = .{ .pane = shell, .bytes = chunk } }); + break :out null; + }, + else => in: { + // The authority's own steps since the last unit, and + // the terminals as they are: what the input's step + // reads, before it is stepped. + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, down[0..r.clients], random, one_way, jitter, totals, m.at >= flood_at and flood_end == 0); + try flushAll(&screens, a.core, peers[0..r.clients], &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, totals); + break :in try a.take(m.bytes); + }, + }; + if (unit) |u| try sendUnit(&queue, &n, u, m.at, down[0..r.clients], random, one_way, jitter, totals, false); + for (host.echo.items) |e| try push(&queue, &n, .{ .at = m.at + 2_000, .n = 0, .kind = .echo, .who = e.pane, .bytes = e.bytes }); host.echo.clearRetainingCapacity(); }, - .to_replica => { - const rp = reps[m.who - 1]; - rp.confirm(m.bytes); - rp.settle(); + .frame => { + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, down[0..r.clients], random, one_way, jitter, totals, m.at >= flood_at and flood_end == 0); + const t0 = screens.encode_ns; + const before = totals.delta_bytes; + try flushAll(&screens, a.core, peers[0..r.clients], &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, totals); + if (screens.encode_ns > t0) try totals.frame_ns.append(gpa, screens.encode_ns - t0); + if (m.at >= flood_at and (flood_end == 0 or m.at <= flood_end)) totals.flood_delta_bytes += totals.delta_bytes - before; + // Frames go on while anything moves, and a second after. + const busy = typing > 0 or flood_end == 0 or queue.count() > 0; + frames_left = if (busy) 60 else frames_left -| 1; + if (frames_left > 0) try push(&queue, &n, .{ .at = m.at + frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }); + }, + .to_replica, .screen_down => { + const c = m.who - 1; + const rp = reps[c]; + if (m.kind == .to_replica) { + rp.confirm(m.bytes); + rp.settle(); + } else if (rp.screen(m.bytes)) |reply| { + const pane = m.bytes[0]; + if (reply[5] == 1) { + // Applied: the screen is the authority's at that version. + const sc = rp.screens[pane].?; + const vt = &rp.core().panes[pane].?.terminal.?.vt; + totals.screens_checked += 1; + if (versions.get(@as(u64, sc.serial) << 32 | sc.rep.seq)) |want| { + if (want != screenHash(vt)) { + totals.screens_wrong += 1; + std.debug.print("seed {d} rtt {d} ms: replica {d}'s terminal {d} at version {d} is not the authority's\n", .{ r.seed, r.rtt_ms, m.who, pane, sc.rep.seq }); + } + } else totals.screens_wrong += 1; + // Deltas while the flood runs (an RTT/2 behind it). + if (m.at >= flood_at + one_way and (flood_end == 0 or m.at <= flood_end + one_way)) flood_deltas[c] += 1; + } else totals.resets += 1; + try push(&queue, &n, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = m.who, .bytes = try gpa.dupe(u8, reply) }); + } + if (rp.screenRequest()) |req| try push(&queue, &n, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = m.who, .bytes = try gpa.dupe(u8, req) }); + }, + .screen_up => { + const c = m.who - 1; + if (m.bytes[5] == 2) totals.fetched += std.mem.readInt(u64, m.bytes[14..22], .little) - std.mem.readInt(u64, m.bytes[6..14], .little); + if (try screens.take(a.core, peers[c], m.bytes)) |answer| try push(&queue, &n, .{ .at = down[c].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_down, .who = m.who, .bytes = answer }); }, } } + totals.flood_us += flood_end -| flood_at; + for (flood_deltas[0..r.clients]) |d| totals.flood_deltas += d; const want = replica.digestOf(a); for (reps[0..r.clients], 1..) |rp, id| { try totals.add(&rp.stats); @@ -266,6 +435,29 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { totals.unequal += 1; std.debug.print("seed {d} rtt {d} ms: replica {d} at quiescence: {s}\n", .{ r.seed, r.rtt_ms, id, if (rp.quiet()) "another digest" else "inputs still pending" }); } + // At quiescence, every terminal the authority's, cell for cell. + for (a.core.panes, 0..) |slot, pid| { + const pane = slot orelse continue; + const state = pane.terminal orelse continue; + const mine = (rp.core().panes[pid] orelse { + totals.unequal += 1; + continue; + }).terminal orelse continue; + if (screenHash(&state.vt) != screenHash(&mine.vt)) { + totals.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: replica {d}'s terminal {d} at quiescence is not the authority's\n", .{ r.seed, r.rtt_ms, id, pid }); + } + } + } +} + +/// A unit of the authority's to every replica, down its link. +fn sendUnit(q: *std.PriorityQueue(Msg, void, Msg.order), n: *u64, unit: []const u8, now: u64, down: []Link, random: std.Random, one_way: u64, jitter: u64, totals: *Totals, flooding: bool) !void { + totals.unit_bytes += unit.len * down.len; + if (flooding) totals.flood_unit_bytes += unit.len * down.len; + for (down, 1..) |*l, who| { + try q.push(gpa, .{ .at = l.arrive(random, now, one_way, jitter), .n = n.*, .kind = .to_replica, .who = @intCast(who), .bytes = try gpa.dupe(u8, unit) }); + n.* += 1; } } @@ -283,15 +475,19 @@ pub fn main(init: std.process.Init) !void { var clients: u16 = 3; var rtts: []const u64 = &.{ 30, 80, 207 }; var shared = false; + var flood_mb: u64 = 8; var rtt_buf: [8]u64 = undefined; var i: usize = 1; - while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; - while (i + 1 < args.len) : (i += 2) { - while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; - if (i + 1 >= args.len) break; + while (i < args.len) : (i += 1) { const name = args[i]; - const value = args[i + 1]; - if (std.mem.eql(u8, name, "--seeds")) seeds = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--first")) first = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--steps")) steps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, name, "--clients")) clients = @min(8, try std.fmt.parseInt(u16, value, 10)) else if (std.mem.eql(u8, name, "--rtt")) { + if (std.mem.eql(u8, name, "--shared")) { + shared = true; + continue; + } + if (i + 1 >= args.len) return error.MissingValue; + i += 1; + const value = args[i]; + if (std.mem.eql(u8, name, "--seeds")) seeds = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--first")) first = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--steps")) steps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, name, "--clients")) clients = @min(8, try std.fmt.parseInt(u16, value, 10)) else if (std.mem.eql(u8, name, "--flood")) flood_mb = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--rtt")) { var it = std.mem.tokenizeScalar(u8, value, ','); var k: usize = 0; while (it.next()) |v| : (k += 1) rtt_buf[k] = try std.fmt.parseInt(u64, v, 10); @@ -306,11 +502,13 @@ pub fn main(init: std.process.Init) !void { try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; var failed = false; - std.debug.print("{d} seeds x {d} inputs from each of {d} clients, {s}; costs in us (frame {d})\n", .{ seeds, steps, clients, if (shared) "sharing one view" else "a view each", frame_us }); + std.debug.print("{d} seeds x {d} inputs from each of {d} clients, {s}, a TUI then {d} MB of yes in the shell; costs in us (frame {d})\n", .{ seeds, steps, clients, if (shared) "sharing one view" else "a view each", flood_mb, frame_us }); std.debug.print(" rtt inputs at-once stopped view units fast rollback(mis+foreign) rate rebase spec p50/p99 copy p50/p99 (KB) rollback p50/p99 diverged unequal\n", .{}); + var term_lines: std.ArrayList(u8) = .empty; + defer term_lines.deinit(gpa); for (rtts) |rtt| { var t: Totals = .{}; - for (first..first + seeds) |seed| try run(.{ .seed = seed, .rtt_ms = rtt, .steps = steps, .clients = clients, .shared = shared }, dir, &t); + for (first..first + seeds) |seed| try run(.{ .seed = seed, .rtt_ms = rtt, .steps = steps, .clients = clients, .shared = shared, .flood_mb = flood_mb }, dir, &t); const rollbacks = t.mispredicted + t.foreign; std.debug.print("{d:>4} {d:>6} {d:>7} {d:>7} {d:>4} {d:>6} {d:>6} {d:>6} ({d}+{d}) {d:>5.1}% {d:>6} {d:>5}/{d:<6} {d:>5}/{d:<5} ({d}) {d:>7}/{d:<7} {d:>8} {d:>7}\n", .{ rtt, t.inputs, t.speculated, @@ -321,7 +519,25 @@ pub fn main(init: std.process.Init) !void { pct(t.copy_ns.items, 99) / 1000, t.copy_bytes / @max(t.copies, 1) / 1024, pct(t.rollback_ns.items, 50) / 1000, pct(t.rollback_ns.items, 99) / 1000, t.divergences, t.unequal, }); - if (t.divergences > 0 or t.unequal > 0) failed = true; + const flood_s = @as(f64, @floatFromInt(@max(1, t.flood_us))) / 1e6; + + try term_lines.print(gpa, "{d:>4} {d:>7.1} {d:>9.0} {d:>9.0} {d:>5}/{d:<5} {d:>5}/{d:<5} {d:>7} {d:>6} {d:>6}/{d:<6}\n", .{ + rtt, + @as(f64, @floatFromInt(t.flood_deltas)) / flood_s / @as(f64, @floatFromInt(clients)), + @as(f64, @floatFromInt(t.flood_delta_bytes)) / flood_s / @as(f64, @floatFromInt(clients)), + @as(f64, @floatFromInt(t.flood_unit_bytes)) / flood_s / @as(f64, @floatFromInt(clients)), + pct(t.frame_ns.items, 50) / 1000, + pct(t.frame_ns.items, 99) / 1000, + pct(t.apply_ns.items, 50) / 1000, + pct(t.apply_ns.items, 99) / 1000, + t.fetched, + t.resets, + t.screens_checked, + t.screens_wrong, + }); + if (t.divergences > 0 or t.unequal > 0 or t.screens_wrong > 0) failed = true; } + std.debug.print("terminals: deltas a replica applied a second under the flood; a peer's bytes a second under the flood (deltas, units); encode a frame for every peer, apply a delta (us); rows fetched; resets; deltas checked/wrong\n", .{}); + std.debug.print(" rtt deltas/s delta B/s unit B/s encode p50/p99 apply p50/p99 fetched resets checked/wrong\n{s}", .{term_lines.items}); if (failed) std.process.exit(1); } -- cgit v1.3