summaryrefslogtreecommitdiff
path: root/test/replicas.zig
diff options
context:
space:
mode:
Diffstat (limited to 'test/replicas.zig')
-rw-r--r--test/replicas.zig766
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", .{});