diff options
| -rw-r--r-- | src/replica.zig | 291 | ||||
| -rw-r--r-- | src/rollback.zig | 12 | ||||
| -rw-r--r-- | src/screen_state.zig | 680 | ||||
| -rw-r--r-- | src/tape.zig | 53 | ||||
| -rw-r--r-- | src/terminal.zig | 57 | ||||
| -rw-r--r-- | test/replicas.zig | 320 |
6 files changed, 1129 insertions, 284 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, +/// 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) }; + } - pub fn deinit(peer: *Peer, gpa: std.mem.Allocator) void { - peer.known.deinit(gpa); - peer.sent.deinit(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 @@ -169,6 +172,15 @@ pub const State = struct { /// 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(); const cur = screen.cursor; @@ -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); } |
