diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-30 01:34:23 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-30 02:10:05 -0300 |
| commit | 3703c2526fb59708b00e12816bd88ffd8a15fc69 (patch) | |
| tree | bfec0f20e970edf6d41a9943446dd6a52296e0db /test | |
| parent | 965a78eafacbffb7cd25104181c81fe5871102c1 (diff) | |
| download | pardes-3703c2526fb59708b00e12816bd88ffd8a15fc69.tar.gz pardes-3703c2526fb59708b00e12816bd88ffd8a15fc69.zip | |
echo: a replica draws a key typed into a terminal at once, mosh's way (a printable character at the cursor, Backspace, Left and Right, in tty mode on the primary screen), from an overlay of its own that no digest, dump or rollback copy sees, painted over the terminal's body at the end of renderBody (the tty's and the GUI's); judged at each delta once the authority has the key and 50 ms have passed, every prediction taken back on a mismatch; drawn at once at a prompt pardes's marks vouch for, elsewhere only once an echo was confirmed, never after a drawn misprediction until one is, so a password prompt or a program that ignores input shows nothing typed; the keys typed behind one not predicted (Tab, Enter) predicted over the screen that shows its doing; zig build replicas -- --echo types a corpus into a played shell at 30/80/207 ms: a key to its character p50 239 -> 8.9 ms and p90 248 -> 15.8 ms at 207, no wrong character drawn; docs/next-daemon.md: the decisions, the hook for the remote client, the numbers, the gates and what is not done
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Diffstat (limited to 'test')
| -rw-r--r-- | test/replicas.zig | 766 |
1 files changed, 737 insertions, 29 deletions
diff --git a/test/replicas.zig b/test/replicas.zig index 9b5c3c3b..baaa669d 100644 --- a/test/replicas.zig +++ b/test/replicas.zig @@ -13,6 +13,11 @@ //! 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] +//! zig build replicas -Dplatform=tty -- --echo [--seeds N] [--rtt 30,80,207] [--first K] +//! +//! `--echo` types a corpus into a shell instead, with and without the +//! predicted echo (src/echo.zig), and gates what it draws: below, at +//! "predicted echo". //! //! Gates, per seed and RTT: no replica diverges (every confirmed unit's //! digests agree as it is replayed), and at quiescence every replica's @@ -29,6 +34,7 @@ const libc = std.c; const pardes = @import("pardes"); const replica = pardes.replica; const screen_state = pardes.screen_state; +const echo = pardes.echo; const Key = pardes.Key; const gpa = std.heap.c_allocator; @@ -58,7 +64,7 @@ const Host = struct { } }; -const Kind = enum { input, to_authority, to_replica, echo, frame, output, screen_down, screen_up }; +const Kind = enum { input, to_authority, to_replica, echo, frame, output, screen_down, screen_up, client_frame }; const Msg = struct { at: u64, @@ -66,6 +72,8 @@ const Msg = struct { kind: Kind, who: u16, bytes: []u8, + /// An echo's: the client's input that made it (--echo). + seq: u32 = 0, fn order(_: void, a: Msg, b: Msg) std.math.Order { if (a.at != b.at) return std.math.order(a.at, b.at); @@ -288,14 +296,6 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { var down: [8]Link = @splat(.{}); var left: [8]usize = @splat(r.steps); 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 = &.{} }); @@ -309,26 +309,6 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { // 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); @@ -432,6 +412,7 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { } 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) }); }, + .client_frame => {}, .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); @@ -467,6 +448,35 @@ fn run(r: Run, dir: []const u8, totals: *Totals) !void { } } +fn push(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); +} + +/// What each peer is owed of the terminals, onto its link (before the +/// authority steps an input, and once a frame); each version as the +/// authority's screen showed it. +fn flushAll(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)); + }; +} + /// A unit of the authority's to every replica, down its link: first the /// rows of its terminals its step read that a replica holds as holes. 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, screens: *replica.Screens, core: *pardes.Pardes, peers: []const u16) !void { @@ -490,6 +500,695 @@ fn sendUnit(q: *std.PriorityQueue(Msg, void, Msg.order), n: *u64, unit: []const } } +// ---- predicted echo (--echo): one client typing a corpus into a shell ---- +// +// The authority's pty is a shell played here (`FakeShell`): a line editor at +// a prompt with pardes's OSC 133 marks and Tab completion, and the programs +// the corpus runs in it: a password prompt (no echo), vim (the alternate +// screen), a program that ignores what is typed, and `cat` (the kernel's +// plain echo, no marks). Each key's echo comes back 2 ms after the authority +// writes it, as a shell's. The client types at a typist's pace and in bursts; +// each of its frames (60 Hz, a phase of its own) is what its screen shows: +// the predicted echo where it is drawn (src/echo.zig), the screen state +// under it. Per key the shell echoed at a prompt or in cat: the time from +// the key to its character on that screen, with prediction and without. Per +// key predicted: whether the authority's screen, right after its echo, +// shows what was predicted where it was. Per key drawn wrong: its frames. + +const ascii: [128][1]u8 = blk: { + var t: [128][1]u8 = undefined; + for (&t, 0..) |*c, i| c.* = .{@intCast(i)}; + break :blk t; +}; + +const Step = struct { gap: u64, key: Key, section: u8 }; + +/// The corpus's parts, each a case of the gates. +const sections = [_][]const u8{ "typing", "a burst", "backspace", "left, right", "tab", "password", "vim", "ignores input", "cat", "typed ahead" }; + +const Corpus = struct { + steps: std.ArrayListUnmanaged(Step) = .empty, + random: std.Random, + extra: u64 = 0, + section: u8 = 0, + + fn add(c: *Corpus, gap: u64, key: Key) !void { + try c.steps.append(gpa, .{ .gap = gap + c.extra, .key = key, .section = c.section }); + c.extra = 0; + } + + fn typing(c: *Corpus, text: []const u8, fast: bool) !void { + for (text) |ch| try c.add(if (fast) c.random.intRangeAtMost(u64, 12_000, 60_000) else c.random.intRangeAtMost(u64, 60_000, 180_000), .{ .cp = ch, .text = &ascii[ch] }); + } + + fn press(c: *Corpus, key: Key) !void { + try c.add(c.random.intRangeAtMost(u64, 80_000, 250_000), key); + } + + fn pause(c: *Corpus) void { + c.extra += c.random.intRangeAtMost(u64, 500_000, 1_200_000); + } + + fn build(c: *Corpus) !void { + const enter: Key = .{ .cp = Key.enter }; + const bs: Key = .{ .cp = Key.backspace }; + c.pause(); + // At a prompt, at a typist's pace, then in a burst. + c.section = 0; + try c.typing("echo hello world", false); + try c.press(enter); + c.pause(); + c.section = 1; + try c.typing("echo the quick brown fox jumps over", true); + try c.press(enter); + c.pause(); + // Backspace. + c.section = 2; + try c.typing("ecoh", false); + try c.press(bs); + try c.press(bs); + try c.typing("ho fixed tpyo", false); + for (0..3) |_| try c.press(bs); + try c.typing("ypo", false); + try c.press(enter); + c.pause(); + // Left and right over what was typed. + c.section = 3; + try c.typing("echo abc", false); + for ([_]u21{ Key.left, Key.left, Key.right, Key.right }) |k| try c.press(.{ .cp = k }); + try c.typing("def", false); + try c.press(enter); + c.pause(); + // Tab completion, typed straight on. + c.section = 4; + try c.typing("ec", false); + try c.press(.{ .cp = Key.tab }); + try c.typing("tab completed", false); + try c.press(enter); + c.pause(); + // A password prompt: nothing typed there may show. + c.section = 5; + try c.typing("sudo ls", false); + try c.press(enter); + c.pause(); + try c.typing("hunter2", false); + try c.press(enter); + c.pause(); + // vim: the alternate screen, never predicted. + c.section = 6; + try c.typing("vim", false); + try c.press(enter); + c.pause(); + try c.typing("ihello from vim", false); + try c.press(.{ .cp = Key.escape, .shift = true }); + try c.typing(":q", false); + try c.press(enter); + c.pause(); + // A program that ignores what is typed. + c.section = 7; + try c.typing("sink", false); + try c.press(enter); + c.pause(); + try c.typing("this goes nowhere", false); + try c.press(.{ .cp = 'c', .ctrl = true }); + c.pause(); + // cat: the kernel's plain echo. + c.section = 8; + try c.typing("cat", false); + try c.press(enter); + c.pause(); + try c.typing("plain echo", false); + try c.press(enter); + try c.typing("a second line", false); + try c.press(enter); + try c.press(.{ .cp = 'd', .ctrl = true }); + c.pause(); + // Typed on before the next prompt. + c.section = 9; + try c.typing("echo one", false); + try c.press(enter); + try c.typing("echo two", false); + try c.press(enter); + c.pause(); + } +}; + +const prompt_bytes = "\x1b]133;A;cl=line;aid=pardes\x07$ \x1b]133;B;aid=pardes\x07"; + +/// The shell on the authority's pty, a key a write (as forwardKey writes). +const FakeShell = struct { + mode: Mode = .prompt, + line: [256]u8 = undefined, + len: usize = 0, + cur: usize = 0, + vim_cmd: [8]u8 = undefined, + vim_n: usize = 0, + out: std.ArrayListUnmanaged(u8) = .empty, + + const Mode = enum { prompt, password, vim, vim_insert, sink, cat }; + + fn put(sh: *FakeShell, bytes: []const u8) void { + sh.out.appendSlice(gpa, bytes) catch {}; + } + + fn print(sh: *FakeShell, comptime fmt: []const u8, args: anytype) void { + sh.out.print(gpa, fmt, args) catch {}; + } + + fn done(sh: *FakeShell, status: u8) void { + sh.print("\x1b]133;D;{d};aid=pardes\x07" ++ prompt_bytes, .{status}); + sh.mode = .prompt; + sh.len = 0; + sh.cur = 0; + } + + fn insert(sh: *FakeShell, c: u8) void { + if (sh.len + 1 >= sh.line.len) return; + sh.put(&.{c}); + if (sh.cur < sh.len) { + sh.put(sh.line[sh.cur..sh.len]); + sh.print("\x1b[{d}D", .{sh.len - sh.cur}); + } + std.mem.copyBackwards(u8, sh.line[sh.cur + 1 .. sh.len + 1], sh.line[sh.cur..sh.len]); + sh.line[sh.cur] = c; + sh.len += 1; + sh.cur += 1; + } + + fn key(sh: *FakeShell, b: []const u8) void { + const printable = b.len == 1 and b[0] >= 0x20 and b[0] < 0x7f; + const eql = std.mem.eql; + switch (sh.mode) { + .prompt => if (printable) sh.insert(b[0]) else if (eql(u8, b, "\x7f")) { + if (sh.cur == 0) return; + if (sh.cur == sh.len) sh.put("\x08\x1b[K") else { + sh.put("\x08"); + sh.put(sh.line[sh.cur..sh.len]); + sh.print(" \x1b[{d}D", .{sh.len - sh.cur + 1}); + } + std.mem.copyForwards(u8, sh.line[sh.cur - 1 .. sh.len - 1], sh.line[sh.cur..sh.len]); + sh.len -= 1; + sh.cur -= 1; + } else if (eql(u8, b, "\x1b[D")) { + if (sh.cur == 0) return; + sh.put(b); + sh.cur -= 1; + } else if (eql(u8, b, "\x1b[C")) { + if (sh.cur == sh.len) return; + sh.put(b); + sh.cur += 1; + } else if (eql(u8, b, "\t")) { + if (sh.cur != sh.len or std.mem.indexOfScalar(u8, sh.line[0..sh.len], ' ') != null) return; + for ([_][]const u8{ "echo", "sudo", "sink", "cat", "vim" }) |cmd| { + if (sh.len == 0 or sh.len >= cmd.len or !std.mem.startsWith(u8, cmd, sh.line[0..sh.len])) continue; + for (cmd[sh.len..]) |ch| sh.insert(ch); + sh.insert(' '); + return; + } + } else if (eql(u8, b, "\r")) { + var cmd_buf: [256]u8 = undefined; + const cmd = cmd_buf[0..sh.len]; + @memcpy(cmd, sh.line[0..sh.len]); + sh.len = 0; + sh.cur = 0; + sh.put("\r\n\x1b]133;C;aid=pardes\x07"); + if (cmd.len == 0) return sh.done(0); + if (std.mem.startsWith(u8, cmd, "echo")) { + sh.print("{s}\r\n", .{std.mem.trimStart(u8, cmd[4..], " ")}); + sh.done(0); + } else if (std.mem.startsWith(u8, cmd, "sudo")) { + sh.put("[sudo] password for you: "); + sh.mode = .password; + } else if (eql(u8, cmd, "vim")) { + sh.put("\x1b[?1049h\x1b[2J\x1b[H~\r\n~\r\n~\x1b[H"); + sh.mode = .vim; + } else if (eql(u8, cmd, "sink")) { + sh.mode = .sink; + } else if (eql(u8, cmd, "cat")) { + sh.mode = .cat; + } else { + sh.print("fake: unknown command: {s}\r\n", .{cmd}); + sh.done(127); + } + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .password => if (eql(u8, b, "\r")) { + sh.put("\r\nsudo: 1 incorrect password attempt\r\n"); + sh.done(1); + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .vim => if (sh.vim_n > 0) { + if (eql(u8, b, "\r")) { + const quit = eql(u8, sh.vim_cmd[0..sh.vim_n], ":q"); + sh.vim_n = 0; + if (quit) { + sh.put("\x1b[?1049l"); + sh.done(0); + } + } else if (printable and sh.vim_n < sh.vim_cmd.len) { + sh.vim_cmd[sh.vim_n] = b[0]; + sh.vim_n += 1; + } + } else if (eql(u8, b, "i")) { + sh.mode = .vim_insert; + } else if (eql(u8, b, ":")) { + sh.vim_cmd[0] = ':'; + sh.vim_n = 1; + }, + .vim_insert => if (eql(u8, b, "\x1b")) { + sh.mode = .vim; + } else if (printable) sh.put(b), + .sink => if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + .cat => if (printable) { + sh.put(b); + if (sh.len < sh.line.len) { + sh.line[sh.len] = b[0]; + sh.len += 1; + } + } else if (eql(u8, b, "\x7f")) { + if (sh.len == 0) return; + sh.put("\x08 \x08"); + sh.len -= 1; + } else if (eql(u8, b, "\r")) { + sh.print("\r\n{s}\r\n", .{sh.line[0..sh.len]}); + sh.len = 0; + } else if (eql(u8, b, "\x04") and sh.len == 0) { + sh.done(0); + } else if (eql(u8, b, "\x03")) { + sh.put("^C\r\n"); + sh.done(130); + }, + } + } +}; + +/// The authority's host: each pty write tagged with the client input that +/// made it. +const EchoHost = struct { + writes: std.ArrayListUnmanaged(struct { seq: u32, bytes: []u8 }) = .empty, + current: u32 = 0, + + fn watched(_: ?*anyopaque) bool { + return false; + } + + fn ptyWrite(ctx: ?*anyopaque, _: u8, bytes: []const u8) void { + const h: *EchoHost = @ptrCast(@alignCast(ctx.?)); + h.writes.append(gpa, .{ .seq = h.current, .bytes = gpa.dupe(u8, bytes) catch return }) catch {}; + } + + fn ignore(_: ?*anyopaque, _: []const u8) void {} + + const vtable: pardes.Host.VTable = .{ .watched = watched, .pty_write = ptyWrite, .set_clipboard = ignore }; + + fn host(h: *EchoHost) pardes.Host { + return .{ .ctx = h, .vtable = &vtable }; + } +}; + +const Typed = struct { + seq: u32, + section: u8, + at: u64, + printable: bool, + /// What was predicted: the cell (its row in the active area) and the + /// cursor after it. + pred: ?struct { x: u16, y: u16, cp: u21 } = null, + pcur: ?struct { x: u16, y: u16 } = null, + /// The shell's mode as it took the key; whether it printed anything for + /// it; the authority's version of the screen before that. + mode: ?FakeShell.Mode = null, + echoed: bool = false, + version_before: u32 = 0, + /// The authority's screen right after its echo: its cursor and the + /// cursor's row; whether that is what was predicted. + after: ?struct { x: u16, y: u16, row: [128]u21 } = null, + truth: ?bool = null, + /// Its prediction drawn: first, and in how many frames. + first_visible: ?u64 = null, + visible_frames: u32 = 0, + /// The screen state showing its echo, first. + seen: ?u64 = null, +}; + +const EchoTotals = struct { + keys: u64 = 0, + echo_keys: u64 = 0, + latency: std.ArrayListUnmanaged(u64) = .empty, + predicted: u64 = 0, + unpredicted: u64 = 0, + confirmed: u64 = 0, + mispredicted: u64 = 0, + cursor_missed: u64 = 0, + right: u64 = 0, + wrong: u64 = 0, + wrong_shown: u64 = 0, + wrong_frames: u64 = 0, + wrong_max: u64 = 0, + secret_frames: u64 = 0, + alt_predicted: u64 = 0, + divergences: u64 = 0, + unequal: u64 = 0, + screens_wrong: u64 = 0, + /// The replica's frame drawn while it shows a prediction (its core's + /// render, the tty's and the GUI's), and the overlay's part of it (ns); + /// cells drawn otherwise than predicted. + render_ns: std.ArrayListUnmanaged(u64) = .empty, + paint_ns: std.ArrayListUnmanaged(u64) = .empty, + drawn_frames: u64 = 0, + paint_wrong: u64 = 0, + sec: [sections.len]Section = @splat(.{}), + + const Section = struct { keys: u64 = 0, predicted: u64 = 0, wrong_frames: u64 = 0, latency: std.ArrayListUnmanaged(u64) = .empty }; + + fn deinit(et: *EchoTotals) void { + for (&et.sec) |*x| x.latency.deinit(gpa); + et.latency.deinit(gpa); + et.render_ns.deinit(gpa); + et.paint_ns.deinit(gpa); + } +}; + +fn cellCp(state: *pardes.panes.terminal.State, x: u16, y: u16) u21 { + const ci = state.vt.screens.active.pages.getCell(.{ .active = .{ .x = x, .y = y } }) orelse return 0x10ffff; + const cp = ci.cell.codepoint(); + return if (cp == 0) ' ' else cp; +} + +/// A key's prediction against the authority's screen right after its echo, +/// once both are known (a key typed behind one not predicted is predicted +/// after the authority has it). +fn judgeTruth(k: *Typed) void { + if (k.truth != null) return; + const pc = k.pcur orelse return; + const after = k.after orelse return; + var ok = after.x == pc.x and after.y == pc.y; + if (k.pred) |cell| ok = ok and cell.y == after.y and cell.x < after.row.len and after.row[cell.x] == cell.cp; + k.truth = ok; + if (trace and !ok) std.debug.print("key {d} in {t} predicted cursor {d},{d} cell {any}; the authority's cursor {d},{d}\n", .{ k.seq, k.mode.?, pc.x, pc.y, k.pred, after.x, after.y }); +} + +fn runEcho(seed: u64, rtt_ms: u64, on: bool, et: *EchoTotals) !void { + var prng = std.Random.DefaultPrng.init(seed *% 0x9e3779b97f4a7c15 +% rtt_ms); + const random = prng.random(); + var host: EchoHost = .{}; + defer { + for (host.writes.items) |w| gpa.free(w.bytes); + host.writes.deinit(gpa); + } + var sh: FakeShell = .{}; + defer sh.out.deinit(gpa); + const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty_shell }, host.host(), true); + defer a.deinit(); + var screens: replica.Screens = .init(gpa); + defer screens.deinit(a.core); + const peer = try screens.addPeer(); + const peers = [_]u16{peer}; + const rp = try replica.Replica.init(gpa, 1, try a.unit(0, 0), true); + defer rp.deinit(); + rp.echo.on = on; + const shell: u8 = for (a.core.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.isTerminal()) break @intCast(id); + } else return error.NoShell; + var corpus: Corpus = .{ .random = random }; + defer corpus.steps.deinit(gpa); + try corpus.build(); + var typed: std.ArrayListUnmanaged(Typed) = .empty; + defer typed.deinit(gpa); + var t: Totals = .{}; + defer { + t.spec_ns.deinit(gpa); + t.copy_ns.deinit(gpa); + t.rollback_ns.deinit(gpa); + t.apply_ns.deinit(gpa); + t.frame_ns.deinit(gpa); + } + var versions: std.AutoHashMapUnmanaged(u64, u64) = .empty; + defer versions.deinit(gpa); + var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; + defer { + while (queue.pop()) |m| if (m.bytes.len > 0) gpa.free(m.bytes); + queue.deinit(gpa); + } + var n: u64 = 0; + const one_way = rtt_ms * 1000 / 2; + const jitter = one_way / 10; + var up: [1]Link = @splat(.{}); + var down: [1]Link = @splat(.{}); + var owed: std.ArrayListUnmanaged([]u8) = .empty; + defer owed.deinit(gpa); + + // The shell's first prompt. + sh.put(prompt_bytes); + a.output(.{ .output = .{ .pane = shell, .bytes = sh.out.items } }); + sh.out.clearRetainingCapacity(); + var next_step: usize = 0; + try push(&queue, &n, .{ .at = corpus.steps.items[0].gap, .n = 0, .kind = .input, .who = 1, .bytes = &.{} }); + try push(&queue, &n, .{ .at = frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }); + try push(&queue, &n, .{ .at = random.uintLessThan(u64, frame_us), .n = 0, .kind = .client_frame, .who = 1, .bytes = &.{} }); + // Two clocks tick while anything else moves, and a second after. + var periodic: usize = 2; + var left: [2]u32 = .{ 60, 60 }; + + var frame_arena: std.heap.ArenaAllocator = .init(gpa); + defer frame_arena.deinit(); + var made: std.ArrayListUnmanaged(echo.Echo.Predicted) = .empty; + defer made.deinit(gpa); + rp.echo.log = &made; + while (queue.pop()) |m| { + defer if (m.bytes.len > 0) gpa.free(m.bytes); + rp.echo.now = m.at * 1000; + // What it predicted in the last event's calls (a key typed, or the + // keys behind one it did not, at a unit, a delta or a frame). + defer { + const top = rp.echo.tops[shell]; + for (made.items) |pr| { + const k = &typed.items[pr.seq - 1]; + if (trace) { + const sc = rp.core().panes[shell].?.terminal.?.vt.screens.active.cursor; + std.debug.print("{d} ms ({t}): key {d} predicted {any} cursor {d}; acked {d} wait {d} nd {d}; the screen's cursor {d},{d}\n", .{ m.at / 1000, m.kind, pr.seq, pr.cell, pr.cursor.x, rp.echo.acked, rp.echo.wait, rp.echo.nd, sc.x, sc.y }); + } + if (pr.cell) |cell| k.pred = .{ .x = cell.x, .y = @intCast(cell.row - top), .cp = cell.cp }; + k.pcur = .{ .x = pr.cursor.x, .y = @intCast(pr.cursor.row - top) }; + judgeTruth(k); + } + made.clearRetainingCapacity(); + } + switch (m.kind) { + .input => { + const step = corpus.steps.items[next_step]; + next_step += 1; + const msg = try gpa.dupe(u8, try rp.input(.{ .key = step.key })); + const seq = rp.next_seq - 1; + try typed.append(gpa, .{ .seq = seq, .section = step.section, .at = m.at, .printable = step.key.text.len == 1 }); + if (trace) std.debug.print("{d} ms: key {d} typed: '{s}' cp {x}\n", .{ m.at / 1000, seq, step.key.text, step.key.cp }); + try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .to_authority, .who = 1, .bytes = msg }); + if (next_step < corpus.steps.items.len) try push(&queue, &n, .{ .at = m.at + corpus.steps.items[next_step].gap, .n = 0, .kind = .input, .who = 1, .bytes = &.{} }); + }, + .to_authority => { + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + try flushAll(&screens, a.core, &peers, &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, &t); + host.current = (replica.parseInput(m.bytes) orelse return error.BadInput).seq; + const unit = try a.take(m.bytes); + host.current = 0; + try sendUnit(&queue, &n, unit, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + for (host.writes.items) |w| try push(&queue, &n, .{ .at = m.at + 2_000, .n = 0, .kind = .echo, .who = shell, .bytes = w.bytes, .seq = w.seq }); + host.writes.clearRetainingCapacity(); + }, + .echo => { + const ty: ?*Typed = if (m.seq > 0) &typed.items[m.seq - 1] else null; + const state = a.core.panes[shell].?.terminal.?; + if (ty) |k| { + k.mode = sh.mode; + k.version_before = if (screens.tracks[shell]) |*tr| tr.track.version else 0; + } + sh.key(m.bytes); + if (sh.out.items.len > 0) { + a.output(.{ .output = .{ .pane = shell, .bytes = sh.out.items } }); + sh.out.clearRetainingCapacity(); + if (ty) |k| k.echoed = true; + } + if (ty) |k| { + const cur = state.vt.screens.active.cursor; + k.after = .{ .x = @intCast(cur.x), .y = @intCast(cur.y), .row = undefined }; + for (&k.after.?.row, 0..) |*cp, x| cp.* = cellCp(state, @intCast(x), @intCast(cur.y)); + judgeTruth(k); + } + }, + .frame => { + if (try a.pending()) |batch| try sendUnit(&queue, &n, batch, m.at, &down, random, one_way, jitter, &t, false, &screens, a.core, &peers); + try flushAll(&screens, a.core, &peers, &owed, &queue, &n, m.at, &down, random, one_way, jitter, &versions, &t); + const busy = next_step < corpus.steps.items.len or queue.count() + 1 > periodic; + left[0] = if (busy) 60 else left[0] -| 1; + if (left[0] > 0) try push(&queue, &n, .{ .at = m.at + frame_us, .n = 0, .kind = .frame, .who = 0, .bytes = &.{} }) else periodic -= 1; + }, + .client_frame => { + _ = rp.echoFrame(); + const core = rp.core(); + const drawn = rp.echo.visible(core) and core.panes[shell].?.body.mode == .tty; + if (drawn and rp.echo.n > 0) { + // Drawn as the client draws it: each cell where it was + // predicted. + _ = frame_arena.reset(.retain_capacity); + core.needs_frame = true; + const t0 = pardes.FrameStats.nowNs(); + const surf = try core.render(frame_arena.allocator()); + try et.render_ns.append(gpa, pardes.FrameStats.nowNs() - t0); + const body = surf.region(.body, shell).?.rect; + const top = rp.echo.tops[shell]; + for (rp.echo.cells[0..rp.echo.n]) |cell| { + if (cell.row < top or surf.at(body.x + cell.x, body.y + @as(u16, @intCast(cell.row - top))).text[0] != cell.cp) et.paint_wrong += 1; + } + const t1 = pardes.FrameStats.nowNs(); + rp.echo.paint(core, surf, core.panes[shell].?, shell, body.x, body.w, body.y, body.h, true); + try et.paint_ns.append(gpa, pardes.FrameStats.nowNs() - t1); + et.drawn_frames += 1; + } + if (drawn) for (rp.echo.cells[0..rp.echo.n]) |cell| { + const k = &typed.items[cell.seq - 1]; + k.visible_frames += 1; + if (k.first_visible == null) { + k.first_visible = m.at; + if (trace) { + const st = core.panes[shell].?.terminal.?; + std.debug.print("{d} ms: key {d} ('{u}') drawn: trusted {} doubt {} phase {t} sem {t}\n", .{ m.at / 1000, cell.seq, cell.cp, rp.echo.trusted, rp.echo.doubt, st.stream.handler.phase, st.vt.screens.active.cursor.semantic_content }); + } + } + }; + const applied = if (rp.screens[shell]) |sc| sc.rep.seq else 0; + for (typed.items) |*k| if (k.echoed and k.seen == null and applied > k.version_before) { + k.seen = m.at; + }; + const busy = next_step < corpus.steps.items.len or queue.count() + 1 > periodic; + left[1] = if (busy) 60 else left[1] -| 1; + if (left[1] > 0) try push(&queue, &n, .{ .at = m.at + frame_us, .n = 0, .kind = .client_frame, .who = 1, .bytes = &.{} }) else periodic -= 1; + }, + .to_replica => { + rp.confirm(m.bytes); + rp.settle(); + }, + .screen_down => { + if (rp.screen(m.bytes)) |reply| { + const pane = m.bytes[0]; + if (reply[5] == 1) { + const sc = rp.screens[pane].?; + if (versions.get(@as(u64, sc.serial) << 32 | sc.rep.seq)) |want| { + if (want != screenHash(&rp.core().panes[pane].?.terminal.?.vt)) t.screens_wrong += 1; + } else t.screens_wrong += 1; + } + try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = 1, .bytes = try gpa.dupe(u8, reply) }); + } + if (rp.screenRequest()) |req| try push(&queue, &n, .{ .at = up[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_up, .who = 1, .bytes = try gpa.dupe(u8, req) }); + }, + .screen_up => { + if (try screens.take(a.core, peer, m.bytes)) |answer| try push(&queue, &n, .{ .at = down[0].arrive(random, m.at, one_way, jitter), .n = 0, .kind = .screen_down, .who = 1, .bytes = answer }); + }, + .output => {}, + } + } + const s = rp.echo.stats; + et.predicted += s.predicted; + et.unpredicted += s.unpredicted; + et.confirmed += s.confirmed; + et.mispredicted += s.mispredicted; + et.cursor_missed += s.cursor_missed; + et.screens_wrong += t.screens_wrong; + for (typed.items) |k| { + et.keys += 1; + const sec = &et.sec[k.section]; + sec.keys += 1; + if (k.pcur != null) sec.predicted += 1; + if (k.visible_frames > 0 and k.truth != true) sec.wrong_frames += k.visible_frames; + if (k.truth) |ok| { + if (ok) et.right += 1 else et.wrong += 1; + } + const md = k.mode orelse .prompt; + if (md == .password or md == .sink) et.secret_frames += k.visible_frames; + if ((md == .vim or md == .vim_insert) and k.pcur != null) et.alt_predicted += 1; + if (k.visible_frames > 0 and k.truth != true) { + if (trace) std.debug.print("seed {d}: key {d} at {d} ms in {t} drawn {d} frames, truth {?}, predicted {any} cursor {any}, the authority after it {any}\n", .{ seed, k.seq, k.at / 1000, md, k.visible_frames, k.truth, k.pred, k.pcur, if (k.after) |af| .{ af.x, af.y } else null }); + et.wrong_shown += 1; + et.wrong_frames += k.visible_frames; + et.wrong_max = @max(et.wrong_max, k.visible_frames); + } + if (k.printable and k.echoed and (md == .prompt or md == .cat)) { + const seen = k.seen orelse std.math.maxInt(u64); + const drawn = if (k.first_visible != null and k.truth == true) @min(k.first_visible.?, seen) else seen; + if (drawn == std.math.maxInt(u64)) { + std.debug.print("seed {d} rtt {d} ms: a key's echo was never drawn\n", .{ seed, rtt_ms }); + et.unequal += 1; + continue; + } + et.echo_keys += 1; + try et.latency.append(gpa, drawn - k.at); + try sec.latency.append(gpa, drawn - k.at); + if (trace and drawn - k.at > 2 * frame_us) std.debug.print("key {d} at {d} ms in {t}: drawn after {d} ms, {s}\n", .{ k.seq, k.at / 1000, md, (drawn - k.at) / 1000, if (k.pcur == null) "not predicted" else if (k.first_visible == null) "predicted, not drawn" else if (k.truth != true) "predicted wrong" else "predicted, drawn late" }); + } + } + if (rp.diverged) |why| { + et.divergences += 1; + std.debug.print("seed {d} rtt {d} ms: the replica diverged: {s}\n", .{ seed, rtt_ms, why }); + } else if (!rp.quiet() or rp.digest() != replica.digestOf(a)) { + et.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: the replica at quiescence: {s}\n", .{ seed, rtt_ms, if (rp.quiet()) "another digest" else "inputs still pending" }); + } + if (screenHash(&a.core.panes[shell].?.terminal.?.vt) != screenHash(&rp.core().panes[shell].?.terminal.?.vt)) { + et.unequal += 1; + std.debug.print("seed {d} rtt {d} ms: the shell at quiescence is not the authority's\n", .{ seed, rtt_ms }); + } +} + +fn echoMain(seeds: u64, first: u64, rtts: []const u64) !bool { + var failed = false; + var draw_lines: std.ArrayList(u8) = .empty; + defer draw_lines.deinit(gpa); + std.debug.print("predicted echo: one client typing the corpus into a shell, {d} seeds a cell; from a key to its character on the client's screen (ms, frames at 60 Hz)\n", .{seeds}); + std.debug.print(" rtt echo keys echoed p50 p90 max predicted unpredicted right/wrong confirmed mispredicted cursor-missed drawn-wrong keys/frames/max secret-frames vim-predicted diverged unequal screens-wrong\n", .{}); + var by_section: std.ArrayList(u8) = .empty; + defer by_section.deinit(gpa); + var off: [sections.len][2]u64 = undefined; + for (rtts) |rtt| for ([_]bool{ false, true }) |on| { + var et: EchoTotals = .{}; + defer et.deinit(); + for (first..first + seeds) |seed| try runEcho(seed, rtt, on, &et); + const ms = struct { + fn f(us: u64) f64 { + return @as(f64, @floatFromInt(us)) / 1000; + } + }.f; + std.debug.print("{d:>4} {s:>4} {d:>4} {d:>6} {d:>5.1} {d:>5.1} {d:>5.1} {d:>9} {d:>11} {d:>5}/{d:<5} {d:>9} {d:>12} {d:>13} {d:>5}/{d:>5}/{d:<5} {d:>13} {d:>13} {d:>8} {d:>7} {d:>13}\n", .{ + rtt, if (on) "on" else "off", et.keys, et.echo_keys, + ms(pct(et.latency.items, 50)), ms(pct(et.latency.items, 90)), ms(pct(et.latency.items, 100)), et.predicted, + et.unpredicted, et.right, et.wrong, et.confirmed, + et.mispredicted, et.cursor_missed, et.wrong_shown, et.wrong_frames, + et.wrong_max, et.secret_frames, et.alt_predicted, et.divergences, + et.unequal, et.screens_wrong, + }); + for (&et.sec, &off, sections) |*x, *o, name| { + const p50 = pct(x.latency.items, 50) / 1000; + const p90 = pct(x.latency.items, 90) / 1000; + if (!on) { + o.* = .{ p50, p90 }; + continue; + } + try by_section.print(gpa, "{d:>4} {s:<14} {d:>5} {d:>9} {d:>7} {d:>4} -> {d:<4} {d:>4} -> {d:<4} {d:>12}\n", .{ rtt, name, x.keys, x.predicted, x.latency.items.len, o[0], p50, o[1], p90, x.wrong_frames }); + } + if (on) try draw_lines.print(gpa, "{d:>4} {d:>12} {d:>6}/{d:<6} {d:>5}/{d:<5} {d:>10}\n", .{ rtt, et.drawn_frames, pct(et.render_ns.items, 50) / 1000, pct(et.render_ns.items, 99) / 1000, pct(et.paint_ns.items, 50), pct(et.paint_ns.items, 99), et.paint_wrong }); + if (et.divergences > 0 or et.unequal > 0 or et.screens_wrong > 0 or et.secret_frames > 0 or et.alt_predicted > 0 or et.paint_wrong > 0) failed = true; + }; + std.debug.print("by part of the corpus (all seeds): keys typed, predicted, echoed (the latency sample); key to its character on the screen, ms, without -> with; frames a wrong prediction was drawn\n rtt part keys predicted echoed p50 off/on p90 off/on drawn-wrong\n{s}", .{by_section.items}); + std.debug.print("the client's frames drawn with a prediction shown: its render (us) and the overlay's part (ns); cells drawn otherwise than predicted\n rtt frames-drawn render p50/p99 paint p50/p99 drawn-wrong\n{s}", .{draw_lines.items}); + return !failed; +} + + fn pct(samples: []u64, p: usize) u64 { if (samples.len == 0) return 0; std.mem.sort(u64, samples, {}, std.sort.asc(u64)); @@ -504,6 +1203,7 @@ pub fn main(init: std.process.Init) !void { var clients: u16 = 3; var rtts: []const u64 = &.{ 30, 80, 207 }; var shared = false; + var echo_mode = false; var flood_mb: u64 = 8; var rtt_buf: [8]u64 = undefined; var i: usize = 1; @@ -513,6 +1213,10 @@ pub fn main(init: std.process.Init) !void { shared = true; continue; } + if (std.mem.eql(u8, name, "--echo")) { + echo_mode = true; + continue; + } if (i + 1 >= args.len) return error.MissingValue; i += 1; const value = args[i]; @@ -530,6 +1234,10 @@ pub fn main(init: std.process.Init) !void { const dir = try std.fmt.bufPrint(&dir_buf, "{s}/replicas-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) }); try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; + if (echo_mode) { + if (!try echoMain(seeds, first, rtts)) std.process.exit(1); + return; + } var failed = false; 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", .{}); |
