From 6b89fed454fd56a3af4b576646538b45d3315146 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 12:32:23 -0300 Subject: FreeBSD: the tty pardes builds for it and runs there, terminals, 9P and the daemon included Cross-compiled with -Dtarget=x86_64-freebsd.15.0 (15 ships libutil.so.10; Zig's default 14.0 links .so.9) and run on the FreeBSD 15.1 box: - 9p_io serves there: fstatat, not Linux's statx. madvise is Linux's. - WINCH reaches the sigwait thread through a handler that does nothing: FreeBSD drops a signal ignored by default as it is sent. - A dead terminal answers a write with ENXIO, which std does not expect: a Debug build traced it to stderr, that same terminal, and recursed until the stack ran out (a session whose ssh dropped hung). No tracing there. - waitid's FreeBSD numbers and 64-bit id: a command pane's exit is seen. - No /proc: a shell's directory and program by sysctl, ttyTaken by the foreground group, the foreground job's name by its program. - File watching by FreeBSD 15's inotify. - ghostty's kitty loader: off Linux a stat comes before a t=f open (a FIFO hung it); FreeBSD's shm_open refuses O_NONBLOCK. - vaxis's test terminal has no read off Linux: no input thread for it. - test-install: the test-build programs installed into /test, to run where the build cannot. Co-Authored-By: Claude Opus 5.5 --- build.zig | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index 034d7284..b365d265 100644 --- a/build.zig +++ b/build.zig @@ -1929,6 +1929,19 @@ pub fn build(b: *std.Build) void { } } } + + // The test-build programs installed rather than run, for a machine the + // build cannot run them on (`-Dtarget=x86_64-freebsd.15.0`): each into + // /test, named for its root file. + const test_install = b.step("test-install", "install the test-build programs into /test, to run elsewhere"); + for (test_build.dependencies.items) |dep| { + const t = dep.cast(std.Build.Step.Compile) orelse continue; + const name = switch (t.root_module.root_source_file orelse continue) { + .src_path => |p| std.fs.path.stem(p.sub_path), + else => t.name, + }; + test_install.dependOn(&b.addInstallArtifact(t, .{ .dest_dir = .{ .override = .{ .custom = "test" } }, .dest_sub_path = name }).step); + } } fn testMatch(b: *std.Build, profiler: *std.Build.Step.Compile, filters: []const []const u8, step: *std.Build.Step) ?*std.Build.Step.Run { @@ -1964,7 +1977,8 @@ fn installHome(b: *std.Build, artifact: *std.Build.Step.Compile, home_bin: ?[]co /// file: ghostty opens first and checks after, and the open of a FIFO /// waits for a writer (pardes hung) while a device's open may do /// something. On Linux an O_PATH probe looks, which opens nothing, and -/// the same inode is reopened through /proc/self/fd. +/// the same inode is reopened through /proc/self/fd; elsewhere a stat by +/// path looks first. /// - shared memory is opened non-blocking and must be a regular file, so /// a FIFO in /dev/shm (or a symlink there to one) neither hangs nor maps. /// - an image may be no larger than a screen's storage @@ -1990,14 +2004,15 @@ fn patchGhosttyKitty(b: *std.Build, io: std.Io, dep: *std.Build.Dependency, vt: .{ " const fd = std.c.shm_open(pathz, @as(c_int, @bitCast(std.c.O{ .ACCMODE = .RDONLY })), @as(u16, 0));", \\ // pardes (build.zig): a FIFO there must not hang the open, and - \\ // on Linux nothing but a regular file is opened at all. + \\ // on Linux nothing but a regular file is opened at all. FreeBSD's + \\ // names are no files, and its shm_open refuses O_NONBLOCK. \\ if (comptime builtin.target.os.tag == .linux) if (path.len > 0 and path[0] == '/') { \\ var dev: [std.Io.Dir.max_path_bytes]u8 = undefined; \\ const full = std.fmt.bufPrint(&dev, "/dev/shm{s}", .{path}) catch return error.InvalidData; \\ const shm_stat = std.Io.Dir.cwd().statFile(io, full, .{}) catch return error.InvalidData; \\ if (shm_stat.kind != .file) return error.InvalidData; \\ }; - \\ const fd = std.c.shm_open(pathz, @as(c_int, @bitCast(std.c.O{ .ACCMODE = .RDONLY, .NONBLOCK = true })), @as(u16, 0)); + \\ const fd = std.c.shm_open(pathz, @as(c_int, @bitCast(std.c.O{ .ACCMODE = .RDONLY, .NONBLOCK = builtin.target.os.tag != .freebsd })), @as(u16, 0)); }, .{ " if (stat.size <= 0) return error.InvalidData;", @@ -2011,9 +2026,12 @@ fn patchGhosttyKitty(b: *std.Build, io: std.Io, dep: *std.Build.Dependency, vt: const helper = \\ \\/// pardes (build.zig): `path`, opened for reading only once it is known - \\/// to be a regular file. Elsewhere than Linux, ghostty's open as it was. + \\/// to be a regular file. Elsewhere than Linux, a stat by path first. \\fn pardesOpenRegular(io: std.Io, path: []const u8) !std.Io.File { - \\ if (comptime builtin.target.os.tag != .linux) return std.Io.Dir.cwd().openFile(io, path, .{}); + \\ if (comptime builtin.target.os.tag != .linux) { + \\ if ((try std.Io.Dir.cwd().statFile(io, path, .{})).kind != .file) return error.NotRegularFile; + \\ return std.Io.Dir.cwd().openFile(io, path, .{}); + \\ } \\ const probe = try std.Io.Dir.cwd().openFile(io, path, .{ .path_only = true }); \\ defer probe.close(io); \\ const stat = try probe.stat(io); -- cgit v1.3 From 97f83717cf8be3e4eedd3f7b932766c1cf72fd37 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 10:46:16 -0300 Subject: perf --live: keystroke-to-present through the real tty and GUI, `yes | head -c 1G` through a real pty, and a big file's open The baseline the daemon work is measured against (docs/next-daemon.md). `pardes-perf --live ` runs the real tty binary in a pty (test/e2e_harness.zig, as the snapshot harness does): FrameStats.keys's gestures (key-down, key-right, edit-char, page-down, wheel) on the 50k-line fixture, a phase each, each frame's latency from the shell taking the input off its queue to the end of its present, read back from the session's PARDES_FRAMES dump; `yes | head -c 1G` typed into a bash pane in tty mode, wall time to the mark after it and the frames drawn; and a 1,000,000-line file opened on the command line, wall time to its first line on screen. `--live-gui ` runs the same gestures as the GUI's own timedemo (PARDES_FRAMES_DEMO=keys) in a hidden test window. p50 and p99 per phase, pooled over --reps runs; text or --json. Each run has a private home (bash with a `$ ` prompt), XDG_RUNTIME_DIR and fixtures under $TMPDIR, all removed after. The frames dump now says the monotonic time of its first frame (`# t0_ns`), so a driver lines its own phase times up with the frames'. The perf gate's baselines (test/perf-baseline-{tty-debug,tty-fast,gui-debug}.json) are recorded again: the harness id is perf.zig's hash, and the medium cells came out within about 10% of the old ones (edit-char and edit-twin faster). Co-Authored-By: Claude Opus 5.5 --- build.zig | 2 + src/FrameStats.zig | 54 +++++++ test/perf-baseline-gui-debug.json | 2 +- test/perf-baseline-tty-debug.json | 2 +- test/perf-baseline-tty-fast.json | 2 +- test/perf.zig | 302 +++++++++++++++++++++++++++++++++++++- 6 files changed, 360 insertions(+), 4 deletions(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index b365d265..9515e536 100644 --- a/build.zig +++ b/build.zig @@ -1519,6 +1519,8 @@ pub fn build(b: *std.Build) void { }), }); perf.root_module.addImport("pardes", core_module); + // --live drives the real binary through a pty (test/e2e_harness.zig). + if (ghostty_vt_for_snap) |vt| perf.root_module.addImport("ghostty-vt", vt); perf.root_module.addOptions("perf_options", perf_options); const run_perf = b.addRunArtifact(perf); run_perf.has_side_effects = true; diff --git a/src/FrameStats.zig b/src/FrameStats.zig index cabb003b..2287002e 100644 --- a/src/FrameStats.zig +++ b/src/FrameStats.zig @@ -269,6 +269,9 @@ pub fn dump(stats: *const FrameStats, path: [:0]const u8) void { } write.line(fd, &buf, "# start_ms\tupdate_us\trender_us\tpresent_us\tgap_us\tmoving\tskipped\tscroll\n", .{}); const t0 = if (all[0].len != 0) all[0][0].start_ns else 0; + // The monotonic clock is the machine's: a driver lines its own times + // up with the frames' by this. + write.line(fd, &buf, "# t0_ns {d}\n", .{t0}); // The timedemo's phases, on the frames' clock. if (stats.demo_ns != 0) if (named(stats.demo_name)) |steps| for (steps) |step| switch (step.act) { .phase => |name| write.line(fd, &buf, "# phase {s} {d:.1}\n", .{ name, @as(f64, @floatFromInt((stats.demo_ns + @as(u64, step.at_ms) * std.time.ns_per_ms) -| t0)) / std.time.ns_per_ms }), @@ -328,6 +331,7 @@ pub fn named(name: []const u8) ?[]const Step { if (std.mem.eql(u8, name, "pdf-scroll")) return &pdf_scroll; if (std.mem.eql(u8, name, "pdf-sdm")) return &pdf_sdm; if (std.mem.eql(u8, name, "one")) return &one; + if (std.mem.eql(u8, name, "keys")) return &keystrokes; if (std.mem.eql(u8, name, "jumps")) return &jumps; if (std.mem.eql(u8, name, "longlines")) return &longlines; if (std.mem.eql(u8, name, "clip-flick")) return &clip_flick; @@ -592,6 +596,56 @@ pub const pdf_sdm = blk: { break :blk out; }; +/// Keystroke-to-present, a phase a gesture, on the file the session opened: +/// test/perf.zig's --live sends these same steps to the tty through a pty +/// and --live-gui runs them here, so the two frontends are timed alike. +pub const keystrokes = blk: { + @setEvalBranchQuota(50_000); + var steps: [1024]Step = undefined; + var n: usize = 0; + var t: u32 = 1500; + const at = struct { + fn add(s: []Step, k: *usize, ms: u32, act: @FieldType(Step, "act")) void { + s[k.*] = .{ .at_ms = ms, .act = act }; + k.* += 1; + } + }; + at.add(&steps, &n, t, .{ .phase = "key-down" }); + for (0..150) |_| { + at.add(&steps, &n, t, .{ .key = .{ .cp = 'j', .text = "j" } }); + t += 30; + } + at.add(&steps, &n, t, .{ .phase = "key-right" }); + for (0..150) |i| { + at.add(&steps, &n, t, .{ .key = if (i % 2 == 0) .{ .cp = 'l', .text = "l" } else .{ .cp = 'h', .text = "h" } }); + t += 30; + } + at.add(&steps, &n, t, .{ .phase = "edit-char" }); + at.add(&steps, &n, t, .{ .key = .{ .cp = 'i', .text = "i" } }); + t += 30; + for (0..150) |_| { + at.add(&steps, &n, t, .{ .key = .{ .cp = 'x', .text = "x" } }); + t += 30; + } + at.add(&steps, &n, t, .{ .key = .{ .cp = pardes.Key.escape } }); + t += 300; + at.add(&steps, &n, t, .{ .phase = "page-down" }); + for (0..60) |_| { + at.add(&steps, &n, t, .{ .key = .{ .cp = pardes.Key.page_down } }); + t += 50; + } + at.add(&steps, &n, t, .{ .phase = "wheel" }); + for (0..150) |_| { + at.add(&steps, &n, t, .{ .wheel = 1 }); + t += 30; + } + t += 500; + at.add(&steps, &n, t, .{ .phase = "done" }); + at.add(&steps, &n, t, .end); + const out = steps[0..n].*; + break :blk out; +}; + /// `scrollSet` alone, on the file the session opened: one kind, for a /// profiler's run. pub const one = blk: { diff --git a/test/perf-baseline-gui-debug.json b/test/perf-baseline-gui-debug.json index a41c92b2..160e7bec 100644 --- a/test/perf-baseline-gui-debug.json +++ b/test/perf-baseline-gui-debug.json @@ -1 +1 @@ -{"harness":"442f274a5da9136c","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"debug","c_optimize":"fast","terminal_optimize":"safe","platform":"gui","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":2253,"med_us":2626,"p90_us":3065,"max_us":3090},{"op":"render","fixture":"medium","min_us":100,"med_us":103,"p90_us":103,"max_us":110},{"op":"key-down","fixture":"medium","min_us":102,"med_us":103,"p90_us":105,"max_us":113},{"op":"key-right","fixture":"medium","min_us":98,"med_us":104,"p90_us":108,"max_us":113},{"op":"page-down","fixture":"medium","min_us":103,"med_us":104,"p90_us":111,"max_us":114},{"op":"wheel","fixture":"medium","min_us":98,"med_us":100,"p90_us":102,"max_us":108},{"op":"edit-char","fixture":"medium","min_us":1251,"med_us":1940,"p90_us":2652,"max_us":3041},{"op":"edit-twin","fixture":"medium","min_us":2779,"med_us":3177,"p90_us":3366,"max_us":3657},{"op":"body-2m","fixture":"medium","min_us":5812,"med_us":11423,"p90_us":13681,"max_us":13758},{"op":"body-appends","fixture":"medium","min_us":153898,"med_us":241075,"p90_us":284518,"max_us":305761},{"op":"deep-sel","fixture":"medium","min_us":86,"med_us":91,"p90_us":94,"max_us":122}]} +{"harness":"418270d16a91d1f9","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"debug","c_optimize":"fast","terminal_optimize":"safe","platform":"gui","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":1972,"med_us":2504,"p90_us":3483,"max_us":3564},{"op":"render","fixture":"medium","min_us":95,"med_us":98,"p90_us":100,"max_us":106},{"op":"key-down","fixture":"medium","min_us":95,"med_us":103,"p90_us":120,"max_us":124},{"op":"key-right","fixture":"medium","min_us":95,"med_us":101,"p90_us":108,"max_us":117},{"op":"page-down","fixture":"medium","min_us":94,"med_us":99,"p90_us":106,"max_us":113},{"op":"wheel","fixture":"medium","min_us":91,"med_us":95,"p90_us":97,"max_us":102},{"op":"edit-char","fixture":"medium","min_us":824,"med_us":1322,"p90_us":1456,"max_us":1774},{"op":"edit-twin","fixture":"medium","min_us":877,"med_us":1207,"p90_us":1736,"max_us":1737},{"op":"body-2m","fixture":"medium","min_us":6801,"med_us":10994,"p90_us":14230,"max_us":14251},{"op":"body-appends","fixture":"medium","min_us":149251,"med_us":237290,"p90_us":297061,"max_us":308786},{"op":"deep-sel","fixture":"medium","min_us":90,"med_us":92,"p90_us":100,"max_us":100}]} diff --git a/test/perf-baseline-tty-debug.json b/test/perf-baseline-tty-debug.json index dc37e033..eefb6c60 100644 --- a/test/perf-baseline-tty-debug.json +++ b/test/perf-baseline-tty-debug.json @@ -1 +1 @@ -{"harness":"442f274a5da9136c","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"debug","c_optimize":"fast","terminal_optimize":"safe","platform":"tty","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":2181,"med_us":2495,"p90_us":2621,"max_us":2660},{"op":"render","fixture":"medium","min_us":96,"med_us":98,"p90_us":102,"max_us":112},{"op":"key-down","fixture":"medium","min_us":101,"med_us":103,"p90_us":107,"max_us":108},{"op":"key-right","fixture":"medium","min_us":100,"med_us":112,"p90_us":118,"max_us":119},{"op":"page-down","fixture":"medium","min_us":97,"med_us":101,"p90_us":105,"max_us":107},{"op":"wheel","fixture":"medium","min_us":98,"med_us":100,"p90_us":108,"max_us":110},{"op":"edit-char","fixture":"medium","min_us":1377,"med_us":1842,"p90_us":2336,"max_us":2418},{"op":"edit-twin","fixture":"medium","min_us":2655,"med_us":3200,"p90_us":3321,"max_us":3660},{"op":"body-2m","fixture":"medium","min_us":5420,"med_us":10753,"p90_us":12826,"max_us":15385},{"op":"body-appends","fixture":"medium","min_us":153569,"med_us":232519,"p90_us":281625,"max_us":309036},{"op":"deep-sel","fixture":"medium","min_us":91,"med_us":98,"p90_us":111,"max_us":111}]} +{"harness":"418270d16a91d1f9","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"debug","c_optimize":"fast","terminal_optimize":"safe","platform":"tty","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":2250,"med_us":3027,"p90_us":4030,"max_us":4593},{"op":"render","fixture":"medium","min_us":99,"med_us":115,"p90_us":123,"max_us":126},{"op":"key-down","fixture":"medium","min_us":106,"med_us":117,"p90_us":128,"max_us":144},{"op":"key-right","fixture":"medium","min_us":102,"med_us":107,"p90_us":112,"max_us":149},{"op":"page-down","fixture":"medium","min_us":99,"med_us":103,"p90_us":108,"max_us":116},{"op":"wheel","fixture":"medium","min_us":101,"med_us":113,"p90_us":115,"max_us":117},{"op":"edit-char","fixture":"medium","min_us":986,"med_us":1712,"p90_us":2219,"max_us":2364},{"op":"edit-twin","fixture":"medium","min_us":1116,"med_us":1448,"p90_us":1938,"max_us":2052},{"op":"body-2m","fixture":"medium","min_us":7050,"med_us":12139,"p90_us":18239,"max_us":24078},{"op":"body-appends","fixture":"medium","min_us":220990,"med_us":347620,"p90_us":381389,"max_us":450691},{"op":"deep-sel","fixture":"medium","min_us":106,"med_us":113,"p90_us":117,"max_us":122}]} diff --git a/test/perf-baseline-tty-fast.json b/test/perf-baseline-tty-fast.json index bd8f32dc..c8d0ed78 100644 --- a/test/perf-baseline-tty-fast.json +++ b/test/perf-baseline-tty-fast.json @@ -1 +1 @@ -{"harness":"442f274a5da9136c","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"fast","c_optimize":"fast","terminal_optimize":"fast","platform":"tty","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":2283,"med_us":2611,"p90_us":2812,"max_us":2917},{"op":"render","fixture":"medium","min_us":89,"med_us":97,"p90_us":105,"max_us":119},{"op":"key-down","fixture":"medium","min_us":88,"med_us":95,"p90_us":100,"max_us":116},{"op":"key-right","fixture":"medium","min_us":90,"med_us":99,"p90_us":103,"max_us":106},{"op":"page-down","fixture":"medium","min_us":86,"med_us":90,"p90_us":96,"max_us":97},{"op":"wheel","fixture":"medium","min_us":85,"med_us":91,"p90_us":94,"max_us":101},{"op":"edit-char","fixture":"medium","min_us":1229,"med_us":1823,"p90_us":1874,"max_us":2101},{"op":"edit-twin","fixture":"medium","min_us":2196,"med_us":2745,"p90_us":2928,"max_us":2972},{"op":"body-2m","fixture":"medium","min_us":5606,"med_us":10369,"p90_us":14063,"max_us":14406},{"op":"body-appends","fixture":"medium","min_us":155867,"med_us":237195,"p90_us":289128,"max_us":306283},{"op":"deep-sel","fixture":"medium","min_us":82,"med_us":84,"p90_us":86,"max_us":91}]} +{"harness":"418270d16a91d1f9","build":{"compiler":"0.17.0","target":"x86_64-linux.5.10...7.2-gnu.2.38","cpu":"x86_64","driver_optimize":"fast","core_optimize":"fast","c_optimize":"fast","terminal_optimize":"fast","platform":"tty","grammars":"full","mupdf":true,"jpx":true,"tracy":false,"quic":false,"theme_animation":true,"terminal_simd":true,"prebuilt_shaders":false},"cols":120,"rows":40,"reps":10,"only":"medium","fixtures":[{"name":"small","lines":1000,"cols":60,"bytes":62694},{"name":"medium","lines":50000,"cols":60,"bytes":3201944},{"name":"large","lines":300000,"cols":60,"bytes":19464444},{"name":"longline","lines":400,"cols":8000,"bytes":3200400},{"name":"esp32p4","lines":12,"cols":240,"bytes":2892}],"cells":[{"op":"open","fixture":"medium","min_us":2341,"med_us":2633,"p90_us":3392,"max_us":5686},{"op":"render","fixture":"medium","min_us":87,"med_us":100,"p90_us":112,"max_us":114},{"op":"key-down","fixture":"medium","min_us":89,"med_us":93,"p90_us":98,"max_us":99},{"op":"key-right","fixture":"medium","min_us":94,"med_us":101,"p90_us":110,"max_us":113},{"op":"page-down","fixture":"medium","min_us":91,"med_us":98,"p90_us":105,"max_us":106},{"op":"wheel","fixture":"medium","min_us":89,"med_us":97,"p90_us":103,"max_us":109},{"op":"edit-char","fixture":"medium","min_us":1055,"med_us":1950,"p90_us":2385,"max_us":2911},{"op":"edit-twin","fixture":"medium","min_us":1021,"med_us":1470,"p90_us":1966,"max_us":2153},{"op":"body-2m","fixture":"medium","min_us":5050,"med_us":11673,"p90_us":14865,"max_us":18117},{"op":"body-appends","fixture":"medium","min_us":209537,"med_us":316775,"p90_us":360616,"max_us":365634},{"op":"deep-sel","fixture":"medium","min_us":84,"med_us":118,"p90_us":143,"max_us":150}]} diff --git a/test/perf.zig b/test/perf.zig index ab284739..cc43abcf 100644 --- a/test/perf.zig +++ b/test/perf.zig @@ -378,6 +378,10 @@ const Options = struct { startup: bool = false, mini: bool = false, terminal_mib: ?usize = null, + /// The real binary's keystroke-to-present, `yes` stream and big open + /// (a tty pardes), or its keystrokes alone (a pardes-gui). + live: ?[]const u8 = null, + live_gui: ?[]const u8 = null, self_test: bool = false, /// A gate: fail when a cell's fastest sample is more than this many /// times the baseline's fastest (--base's). @@ -389,7 +393,7 @@ const Options = struct { while (i < args.len) : (i += 1) { const arg = args[i]; if (!std.mem.startsWith(u8, arg, "--")) return error.UnknownOption; - const option = std.meta.stringToEnum(enum { json, creation, startup, mini, @"terminal-mib", @"self-test", reps, cols, rows, base, only, @"max-ratio" }, arg[2..]) orelse + const option = std.meta.stringToEnum(enum { json, creation, startup, mini, @"terminal-mib", @"self-test", reps, cols, rows, base, only, @"max-ratio", live, @"live-gui" }, arg[2..]) orelse return error.UnknownOption; switch (option) { .json => opts.json = true, @@ -409,6 +413,8 @@ const Options = struct { .only => opts.only = value, .@"terminal-mib" => opts.terminal_mib = std.fmt.parseInt(usize, value, 10) catch return error.InvalidNumber, .@"max-ratio" => opts.max_ratio = std.fmt.parseFloat(f64, value) catch return error.InvalidNumber, + .live => opts.live = value, + .@"live-gui" => opts.live_gui = value, else => unreachable, } }, @@ -452,6 +458,8 @@ pub fn main(init: std.process.Init) !void { if (opts.creation) return measureCreation(init.io, reps, opts.json); if (opts.terminal_mib) |mib| return measureTerminalSession(init.io, mib, reps, opts.json); if (opts.mini) return measureMini(init.io, init.gpa, reps, opts.json); + if (opts.live) |exe| return measureLive(init.io, exe, false, reps, opts.json); + if (opts.live_gui) |exe| return measureLive(init.io, exe, true, reps, opts.json); var random: [12]u8 = undefined; init.io.random(&random); @@ -1067,6 +1075,298 @@ fn measureTerminalSession(io: std.Io, mib: usize, reps: usize, json: bool) !void try std.Io.File.stdout().writeStreamingAll(io, "\n"); } +// ---- live: the real binary, in a pty (tty) or a hidden test window (gui) ---- +// +// Keystroke-to-present is FrameStats' own latency: from the shell taking an +// input off its queue to the end of the frame's present. Both frontends run +// FrameStats.keys (the tty through the pty, the gui as its timedemo) and the +// frames' dump (PARDES_FRAMES) is split by its phases. `yes | head -c 1G` is +// typed into a shell and timed to the mark after it; the big file is opened +// on the command line and timed to its first line on screen. + +const eh = @import("e2e_harness.zig"); +extern "c" fn setenv(name: [*:0]const u8, value: [*:0]const u8, overwrite: c_int) c_int; + +const live_phases = [_][]const u8{ "key-down", "key-right", "edit-char", "page-down", "wheel" }; +const yes_bytes = 1 << 30; +const big_lines = 1_000_000; + +const Live = struct { + dir: []const u8, + /// Each phase's frame latencies, µs, over every run, and the core's + /// part of those frames (update and render: the rest is the shell's + /// present, a test window's capture of the frame included). + samples: [live_phases.len]std.ArrayList(u32) = @splat(.empty), + core: [live_phases.len]std.ArrayList(u32) = @splat(.empty), + yes_ns: std.ArrayList(u64) = .empty, + yes_frames: std.ArrayList(u64) = .empty, + open_ns: std.ArrayList(u64) = .empty, + + fn path(l: *const Live, comptime name: []const u8) ![:0]const u8 { + return std.fmt.allocPrintSentinel(gpa, "{s}/" ++ name, .{l.dir}, 0); + } +}; + +/// A private home (bash with a `$ ` prompt, as the snapshot harness pins), +/// runtime directory and the two fixtures, under $TMPDIR. +fn liveSetup(io: std.Io) !Live { + var random: [8]u8 = undefined; + io.random(&random); + const tmp = if (std.c.getenv("TMPDIR")) |t| std.mem.span(t) else "/tmp"; + const dir = try std.fmt.allocPrint(gpa, "{s}/pardes-perf-live-{x}", .{ tmp, random }); + try std.Io.Dir.cwd().createDirPath(io, dir); + const l: Live = .{ .dir = dir }; + try std.Io.Dir.cwd().createDirPath(io, try l.path("home/.config/pardes")); + try writeFile(try l.path("home/.bashrc"), "PS1='$ '\nHISTFILE=\n"); + try writeFile(try l.path("home/.config/pardes/init"), "Shell bash\n"); + // A runtime directory of its own: no session of these shows up in the + // user's. Short, for the 9P socket's 108-byte path. + const run = try std.fmt.allocPrintSentinel(gpa, "/tmp/pardes-perf-run-{x}", .{random}, 0); + try std.Io.Dir.cwd().createDirPath(io, run); + _ = setenv("XDG_RUNTIME_DIR", run, 1); + _ = setenv("HOME", try l.path("home"), 1); + _ = setenv("XDG_CONFIG_HOME", try l.path("home/.config"), 1); + _ = setenv("TERM", "xterm-256color", 1); + const medium = try generate(fixtures[1]); + defer gpa.free(medium); + try writeFile(try l.path("medium.zig"), medium); + var big: std.ArrayList(u8) = .empty; + defer big.deinit(gpa); + for (0..big_lines) |n| try big.print(gpa, "line {d:0>7} the quick brown fox jumps over the lazy dog 0123456789\n", .{n + 1}); + try writeFile(try l.path("big.txt"), big.items); + return l; +} + +fn liveCleanup(io: std.Io, l: *Live) void { + std.Io.Dir.cwd().deleteTree(io, l.dir) catch {}; + if (std.c.getenv("XDG_RUNTIME_DIR")) |run| std.Io.Dir.cwd().deleteTree(io, std.mem.span(run)) catch {}; +} + +/// The bytes a terminal sends for a step of FrameStats.keys. +fn stepBytes(buf: *[32]u8, step: pardes.FrameStats.Step) []const u8 { + return switch (step.act) { + .key => |k| switch (k.cp) { + pardes.Key.escape => "\x1b", + pardes.Key.page_down => "\x1b[6~", + else => buf[0 .. std.unicode.utf8Encode(k.cp, buf) catch 0], + }, + // SGR wheel down (65) or up (64), over the file's body. + .wheel => |notches| std.fmt.bufPrint(buf, "\x1b[<{d};60;20M", .{@as(u8, if (notches > 0) 65 else 64)}) catch "", + else => "", + }; +} + +/// Feeds the harness until the app exits (reaped) or `ms` runs out (killed, +/// its screen shown). +fn liveExit(h: *eh.Harness, ms: i64) bool { + const deadline = eh.nowMs() + ms; + while (eh.nowMs() < deadline) { + var status: c_int = 0; + if (libc.waitpid(h.pid, &status, libc.W.NOHANG) == h.pid) { + if (status != 0) h.dump("live: the app failed"); + // Reaped: the harness must not signal a pid that is gone. + _ = libc.close(h.master); + h.stream.deinit(); + gpa.destroy(h.raw); + h.term.deinit(gpa); + gpa.destroy(h.term); + return true; + } + _ = h.pumpOnce(20) catch false; + } + h.dump("live: the app did not exit"); + h.deinit(); + _ = libc.waitpid(h.pid, null, 0); + return false; +} + +/// Exit, and Exit again past the question an edited file asks. +fn liveQuit(h: *eh.Harness) !bool { + try h.send("\x1b"); + try h.pump(60); + try h.send(" q"); + try h.pump(200); + try h.send(" q"); + return liveExit(h, 10_000); +} + +/// How many frames a PARDES_FRAMES dump says were drawn. +fn dumpFrames(dump_path: []const u8) !u64 { + const text = try readFileAlloc(dump_path); + defer gpa.free(text); + if (!std.mem.startsWith(u8, text, "# frames ")) return error.BadFrames; + var it = std.mem.tokenizeScalar(u8, text["# frames ".len..], ' '); + return std.fmt.parseInt(u64, it.next() orelse return error.BadFrames, 10); +} + +/// The frames of a PARDES_FRAMES dump, each latency into the phase it fell +/// in. `starts` are the phases' monotonic starts, or null to take them +/// from the dump's own `# phase` lines (the GUI's timedemo writes them). +fn liveFrames(l: *Live, dump_path: []const u8, starts: ?*const [live_phases.len + 1]u64) !void { + const text = try readFileAlloc(dump_path); + defer gpa.free(text); + var t0: u64 = 0; + // Each phase's start and, last, "done"'s: the quit's keys are no phase's. + var from: [live_phases.len + 1]u64 = if (starts) |s| s.* else @splat(std.math.maxInt(u64)); + var lines = std.mem.splitScalar(u8, text, '\n'); + while (lines.next()) |line| { + if (std.mem.startsWith(u8, line, "# t0_ns ")) { + t0 = try std.fmt.parseInt(u64, line["# t0_ns ".len..], 10); + } else if (std.mem.startsWith(u8, line, "# phase ") and starts == null) { + var it = std.mem.tokenizeScalar(u8, line["# phase ".len..], ' '); + const name = it.next() orelse continue; + const at = t0 + @as(u64, @intFromFloat(try std.fmt.parseFloat(f64, it.next() orelse continue) * std.time.ns_per_ms)); + for (live_phases ++ [_][]const u8{"done"}, 0..) |phase, i| if (std.mem.eql(u8, name, phase)) { + from[i] = at; + }; + } + } + lines = std.mem.splitScalar(u8, text, '\n'); + while (lines.next()) |line| { + if (line.len == 0 or line[0] == '#') continue; + var fields = std.mem.splitScalar(u8, line, '\t'); + const start_ms = try std.fmt.parseFloat(f64, fields.next() orelse continue); + const update = try std.fmt.parseInt(u32, fields.next() orelse continue, 10); + const render = try std.fmt.parseInt(u32, fields.next() orelse continue, 10); + for (0..6) |_| _ = fields.next(); + const latency = try std.fmt.parseInt(u32, fields.next() orelse continue, 10); + if (latency == 0) continue; + const at = t0 + @as(u64, @intFromFloat(start_ms * std.time.ns_per_ms)); + var phase: ?usize = null; + for (from, 0..) |f, i| if (at >= f) { + phase = i; + }; + if (phase) |i| if (i < live_phases.len) { + try l.samples[i].append(gpa, latency); + try l.core[i].append(gpa, update + render); + }; + } +} + +fn liveKeysTty(l: *Live, exe: [:0]const u8) !void { + const dump_path = try l.path("tty-frames.tsv"); + _ = setenv("PARDES_FRAMES", dump_path, 1); + var h = try eh.Harness.initArgv(gpa, exe, screen_rows, screen_cols, &.{(try l.path("medium.zig")).ptr}); + if (!try h.waitFor("helper_1", 20_000)) return error.LiveFileNotShown; + try h.pump(300); + var starts: [live_phases.len + 1]u64 = @splat(std.math.maxInt(u64)); + const t0 = nowNs(); + var buf: [32]u8 = undefined; + for (pardes.FrameStats.named("keys").?) |step| { + const due = t0 + @as(u64, step.at_ms) * std.time.ns_per_ms; + while (nowNs() < due) _ = try h.pumpOnce(@intCast(@max(1, (due -| nowNs()) / std.time.ns_per_ms))); + switch (step.act) { + .phase => |name| for (live_phases ++ [_][]const u8{"done"}, 0..) |phase, i| if (std.mem.eql(u8, name, phase)) { + starts[i] = nowNs(); + }, + .end => break, + else => try h.send(stepBytes(&buf, step)), + } + } + if (!try liveQuit(&h)) return error.LiveDidNotExit; + try liveFrames(l, dump_path, &starts); +} + +fn liveYes(l: *Live, exe: [:0]const u8) !void { + const dump_path = try l.path("yes-frames.tsv"); + _ = setenv("PARDES_FRAMES", dump_path, 1); + var h = try eh.Harness.initArgv(gpa, exe, screen_rows, screen_cols, &.{ "-n", "1" }); + errdefer h.dump("live yes"); + // The prompt shows in tty mode only: the shell's tag, then Ctrl-b in. + if (!try h.waitFor("Tty+bash", 20_000)) return error.LiveNoPrompt; + try h.pump(500); + try h.send("\x02"); + if (!try h.waitFor("$ ", 20_000)) return error.LiveNoPrompt; + try h.send(std.fmt.comptimePrint("yes | head -c {d}; echo DO''NE", .{yes_bytes})); + try h.pump(100); + const t0 = nowNs(); + try h.send("\r"); + if (!try h.waitFor("DONE", 600_000)) return error.LiveYesUnfinished; + try l.yes_ns.append(gpa, nowNs() - t0); + try h.pump(200); + try h.send("exit\r"); + if (!liveExit(&h, 10_000)) return error.LiveDidNotExit; + // Only the frame count: a stream's frames answer no input. + try l.yes_frames.append(gpa, try dumpFrames(dump_path)); +} + +fn liveOpen(l: *Live, exe: [:0]const u8) !void { + _ = setenv("PARDES_FRAMES", "", 1); + const t0 = nowNs(); + var h = try eh.Harness.initArgv(gpa, exe, screen_rows, screen_cols, &.{(try l.path("big.txt")).ptr}); + if (!try h.waitFor("line 0000001", 60_000)) return error.LiveFileNotShown; + try l.open_ns.append(gpa, nowNs() - t0); + if (!try liveQuit(&h)) return error.LiveDidNotExit; +} + +fn liveKeysGui(l: *Live, exe: [:0]const u8) !void { + const dump_path = try l.path("gui-frames.tsv"); + _ = setenv("PARDES_FRAMES", dump_path, 1); + _ = setenv("PARDES_FRAMES_DEMO", "keys", 1); + _ = setenv("PARDES_TEST", "1", 1); + _ = setenv("PARDES_TEST_CAPTURE_DIR", try std.fmt.allocPrintSentinel(gpa, "{s}", .{l.dir}, 0), 1); + _ = setenv("PARDES_TEST_COLS", try std.fmt.allocPrintSentinel(gpa, "{d}", .{screen_cols}, 0), 1); + _ = setenv("PARDES_TEST_ROWS", try std.fmt.allocPrintSentinel(gpa, "{d}", .{screen_rows}, 0), 1); + _ = setenv("SDL_VIDEODRIVER", "wayland", 1); + // The private runtime directory has no display: the user's, by path. + const display = std.mem.span(std.c.getenv("WAYLAND_DISPLAY") orelse "wayland-0"); + if (display.len > 0 and display[0] != '/') + _ = setenv("WAYLAND_DISPLAY", try std.fmt.allocPrintSentinel(gpa, "/run/user/{d}/{s}", .{ std.c.getuid(), display }, 0), 1); + // Under the pty only for a stdin that stays open (test mode reads it). + var h = try eh.Harness.initArgv(gpa, exe, screen_rows, screen_cols, &.{(try l.path("medium.zig")).ptr}); + if (!liveExit(&h, 120_000)) return error.LiveDidNotExit; + try liveFrames(l, dump_path, null); +} + +/// p50 and p99, sorting `s`. +fn spread(s: []u32) [2]u32 { + std.mem.sort(u32, s, {}, std.sort.asc(u32)); + return .{ s[s.len / 2], s[@min(s.len - 1, s.len * 99 / 100)] }; +} + +fn measureLive(io: std.Io, exe: []const u8, gui: bool, reps: usize, json: bool) !void { + var l = try liveSetup(io); + defer liveCleanup(io, &l); + const exe_z = try gpa.dupeSentinel(u8, exe, 0); + for (0..reps) |_| { + if (gui) { + try liveKeysGui(&l, exe_z); + continue; + } + try liveKeysTty(&l, exe_z); + try liveYes(&l, exe_z); + try liveOpen(&l, exe_z); + } + const frontend = if (gui) "gui" else "tty"; + const out = std.Io.File.stdout(); + var buf: [256]u8 = undefined; + for (live_phases, &l.samples, &l.core) |name, *samples, *core| { + if (samples.items.len == 0) return error.LivePhaseUnmeasured; + const all = spread(samples.items); + const own = spread(core.items); + const line = if (json) + try std.fmt.bufPrint(&buf, "{{\"case\":\"live-{s}-{s}\",\"n\":{d},\"p50_us\":{d},\"p99_us\":{d},\"core_p50_us\":{d},\"core_p99_us\":{d}}}\n", .{ frontend, name, samples.items.len, all[0], all[1], own[0], own[1] }) + else + try std.fmt.bufPrint(&buf, "live {s} {s:<10} keystroke-to-present n {d:>4} p50 {d:>6} us p99 {d:>6} us, core p50 {d:>6} us p99 {d:>6} us\n", .{ frontend, name, samples.items.len, all[0], all[1], own[0], own[1] }); + try out.writeStreamingAll(io, line); + } + if (gui) return; + for (l.yes_ns.items, l.yes_frames.items) |ns, frames| { + const line = if (json) + try std.fmt.bufPrint(&buf, "{{\"case\":\"live-tty-yes-1g\",\"wall_ns\":{d},\"frames\":{d}}}\n", .{ ns, frames }) + else + try std.fmt.bufPrint(&buf, "live tty yes|head -c 1G: {d} ms wall, {d} frames\n", .{ ns / std.time.ns_per_ms, frames }); + try out.writeStreamingAll(io, line); + } + for (l.open_ns.items) |ns| { + const line = if (json) + try std.fmt.bufPrint(&buf, "{{\"case\":\"live-tty-open-big\",\"lines\":{d},\"wall_ns\":{d}}}\n", .{ big_lines, ns }) + else + try std.fmt.bufPrint(&buf, "live tty open {d}-line file: {d} ms to its first line\n", .{ big_lines, ns / std.time.ns_per_ms }); + try out.writeStreamingAll(io, line); + } +} + const MiniProbe = enum { generate, highlight_generate, render }; const MiniMeasurement = struct { cold_ns: u64 = 0, -- cgit v1.3 From e91a3788752c63c2ed086c553f9861056172e8c0 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 11:10:32 -0300 Subject: tty: a pane flooded with output (`yes`) is read on to its end, not left blocked for good while keys still work vaxis's event queue woke one blocked writer, and only on the pop from full. The tty's loop has two writers on it: a pane's pty reader, and the input reader posting the wake for a frame's answered status request (FrameAck). Under `yes` both block on the full queue; the loop then takes a whole batch, its first pop wakes one of them, the rest wake no one, and the pty reader waits for good: the program in the pane blocks writing to its pty, the pane stops moving, and every key still works. It happened from about 400 KB of output, every time at 1 MB, through the snapshot harness's pty as through a terminal. build.zig patches vaxis's src/queue.zig at build time, count-checked as its Parser.zig and Vaxis.zig are: a pop that makes room wakes every blocked writer. A test (src/vaxis_input.zig) empties a full queue in one batch with two writers waiting and requires both to land. `yes | head -c N` through a bash pane in tty mode now finishes at 1 MB, 10 MB, 100 MB (16 s) and 1 GB (179 s, test/perf.zig --live). Co-Authored-By: Claude Opus 5.5 --- build.zig | 18 +++++++++++++++--- src/vaxis_input.zig | 31 +++++++++++++++++++++++++++++++ 2 files changed, 46 insertions(+), 3 deletions(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index 9515e536..5e337dfc 100644 --- a/build.zig +++ b/build.zig @@ -888,13 +888,25 @@ pub fn build(b: *std.Build) void { \\} \\ ; + // And its event queue: a pop that makes room woke one blocked + // writer, and only on the pop from full. The tty has two writers + // (a pane's pty reader, and the input reader posting the frame + // ack's wake), so when the loop emptied a full queue in one batch + // the writer not woken waited on for good: under `yes` the pane + // stopped being read, its program blocked on the pty, while keys + // went on working. Every blocked writer is woken now. + var queue_src = configureRead(b, io, vaxis_dep.builder.root, "src/queue.zig", 1 << 20) catch @panic("read vaxis queue.zig"); + const wake_one = "self.not_full.signal(self.io);"; + if (std.mem.count(u8, queue_src, wake_one) != 2) std.debug.panic("vaxis's queue.zig changed at `{s}`: redo its patch in build.zig", .{wake_one}); + queue_src = std.mem.replaceOwned(u8, b.allocator, queue_src, wake_one, "self.not_full.broadcast(self.io); // pardes's patch (its build.zig)") catch @panic("OOM"); const files = b.addWriteFiles(); _ = files.add("Parser.zig", b.fmt("{s}{s}", .{ src, cursor_report })); _ = files.add("Vaxis.zig", b.fmt("{s}{s}", .{ render_src, blank_ink })); + _ = files.add("queue.zig", queue_src); _ = files.addCopyFile(vaxis_dep.path("src/widgets/terminal/Parser.zig"), "widgets/terminal/Parser.zig"); - // Suffixes: this leaves out both Parser.zig files and Vaxis.zig, - // written above. - _ = files.addCopyDirectory(vaxis_dep.path("src"), "", .{ .exclude_extensions = &.{ "Parser.zig", "Vaxis.zig" } }); + // Suffixes: this leaves out both Parser.zig files, Vaxis.zig and + // queue.zig, written above. + _ = files.addCopyDirectory(vaxis_dep.path("src"), "", .{ .exclude_extensions = &.{ "Parser.zig", "Vaxis.zig", "queue.zig" } }); vaxis_mod.root_source_file = files.getDirectory().path(b, "main.zig"); } diff --git a/src/vaxis_input.zig b/src/vaxis_input.zig index 0e25dea1..59846d0f 100644 --- a/src/vaxis_input.zig +++ b/src/vaxis_input.zig @@ -75,3 +75,34 @@ test "F-keys, Insert and the keypad map to the core's keys" { try std.testing.expectEqual(pardes.Key.enter, keyEvent(.{ .codepoint = vaxis.Key.kp_enter }).key.cp); try std.testing.expectEqual(@as(u21, 'a'), mapKey('a')); } + +test "an event queue emptied in one batch lets every writer it held go on (build.zig's patch)" { + const io = std.testing.io; + const Q = vaxis.Queue(u8, 2); + var q: Q = .init(io); + try q.push(1); + try q.push(2); + const Writer = struct { + fn run(queue: *Q, byte: u8) !void { + try queue.push(byte); + } + }; + // Two writers waiting on the full queue, as a pane's pty reader and + // the frame ack's wake do under `yes`. + var a = try io.concurrent(Writer.run, .{ &q, 3 }); + defer a.cancel(io) catch {}; + var b = try io.concurrent(Writer.run, .{ &q, 4 }); + defer b.cancel(io) catch {}; + try io.sleep(.fromMilliseconds(20), .awake); + // The loop takes both at once: one pop from full, then one more. + try q.lock(); + _ = q.drain().?; + _ = q.drain().?; + q.unlock(); + var got: usize = 0; + var waited: usize = 0; + while (got < 2 and waited < 200) : (waited += 1) { + if (try q.tryPop() != null) got += 1 else try io.sleep(.fromMilliseconds(5), .awake); + } + try std.testing.expectEqual(@as(usize, 2), got); +} -- cgit v1.3 From 6a6e1b2cb3e328d5abd4435c1c2659f4e4e31eb8 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 16:55:47 -0300 Subject: the replica socket: the daemon listens on pardes-replica.sock, a stream `ssh -L` can forward, refuses another build's hello in words and hands the connection to its session, which welcomes it and answers pings The daemon binds `pardes-replica.sock` beside its own (SOCK_STREAM, so ssh can forward it; the SEQPACKET socket that carries fds stays local) once it holds its lock. A replica's first message is a hello (detached/wire.zig, now version 14): the protocol version at offset 0, the client's semantics hash and the session's name. The daemon reads exactly that much and no further, so whatever the client sends next is the session's, keeps up to 16 hellos still on their way (ponytail: one that never comes holds its slot until it hangs up), and refuses in words another protocol, a session nobody has, or another build: every session now says its own hash in its registration (daemon protocol 2), so a mismatch never reaches it. An accepted connection goes to the session over its link (SCM_RIGHTS) and the daemon keeps no copy; the session welcomes it with its pid and name on a thread of its own and answers each ping with a pong, until bye or a hangup. ponytail: that stub is all a session does with a replica until phase 5 proper; it is what times a round trip through the handoff and `ssh -L`. The semantics hash (wire.semantics) is phase 1's undone item: the protocol, the release and commit, the platform, the build options, every dependency the manifest pins by its content hash (grammars, ghostty, the Unicode tables: build.zig's new `deps` option) and the walker codec's assumptions (pointer width, byte order). Not the OS: a Linux client of a FreeBSD session is the main case. ponytail: an unstamped build has no commit, so two dev trees of one release with the same options are not told apart. `pardes --version` prints it on a second line. The hello lost its grid (a replica's view takes a resize like any other input). test/daemon.py: a hello of this build welcomed by the session itself (its pid, one fd more in the session and none in the daemon, and back once it hangs up), 50 pings, another build's hello and an unknown session's refused, and `--ping [n]`, which times a hello and n pings on any replica socket (a forwarded one, say). Co-Authored-By: Claude Opus 5.5 --- build.zig | 13 ++++ docs/typ/building.typ | 17 ++++-- src/CHANGELOG.md | 6 ++ src/daemon.zig | 166 ++++++++++++++++++++++++++++++++++++++++++++++++-- src/detached/wire.zig | 157 ++++++++++++++++++++++++++++++++++++----------- src/main.zig | 6 +- test/daemon.py | 110 ++++++++++++++++++++++++++++++++- 7 files changed, 427 insertions(+), 48 deletions(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index 5e337dfc..24476753 100644 --- a/build.zig +++ b/build.zig @@ -13,6 +13,18 @@ const display_version = if (std.mem.endsWith(u8, zon.version, ".0") and std.mem. else zon.version; +/// Every dependency the manifest pins, by its content hash: a grammar, +/// ghostty or the Unicode tables steps a core differently, so they are part +/// of a replica's semantics hash (src/detached/wire.zig `semantics`). +const deps_text = blk: { + var text: []const u8 = ""; + for (@typeInfo(@TypeOf(zon.dependencies)).@"struct".field_names) |name| { + const dep = @field(zon.dependencies, name); + text = text ++ name ++ " " ++ (if (@hasField(@TypeOf(dep), "hash")) dep.hash else "path") ++ "\n"; + } + break :blk text; +}; + pub const Platform = enum { tty, gui, web, macos, esp32p4 }; const PerfBuild = struct { @@ -2120,6 +2132,7 @@ fn shellOptions(b: *std.Build, cfg: ShellConfig, platform: Platform) *std.Build. // ...and the commit it was built from, when there is one and the build // is stamped at all (see `stamp_commit`). Read at configure time. o.addOption(?[]const u8, "commit", cfg.commit); + o.addOption([]const u8, "deps", deps_text); return o; } diff --git a/docs/typ/building.typ b/docs/typ/building.typ index 152be838..00088d7b 100644 --- a/docs/typ/building.typ +++ b/docs/typ/building.typ @@ -31,7 +31,8 @@ leaves that copy out. Zig 0.17 keeps the prefix from the build script, so so always pass `-Dplatform` while developing. Test, benchmark and run steps build what they need without installing. `pardes --version` prints `pardes ` (from `build.zig.zon`), plus the commit for release builds and the `~/.local` -install; `pardes --help` lists every flag. +install, and on a second line the build's semantics hash, which a replica +must share with its session; `pardes --help` lists every flag. The ESP32-P4 firmware is linked in the sibling `../05-zig-p4` toolchain, which needs ESP-IDF register headers: after building the editor object @@ -223,9 +224,17 @@ process; `pardes-gui --attach` opens one again. `PARDES_DAEMON=off` (the snapshot harness) runs a session as before the daemon: in the terminal's own process, ended by its hangup. -`src/detached/wire.zig` is the input half of the protocol a remote client -will speak (version 13): fixed-width little-endian fields, a 5-byte header -(tag, then a u32 length), the hello and its version, the input events. +A replica (a client running its own copy of the core, phase 5 of +`docs/next-daemon.md`) connects to `pardes-replica.sock`, a stream socket +beside it that `ssh -L` can forward. `src/detached/wire.zig` is its +protocol (version 14): fixed-width little-endian fields, a 5-byte header +(tag, then a u32 length), the hello, a ping, the input events. The hello +names a session and carries the client's semantics hash (the protocol, +release, commit, platform, build options and every dependency's hash); the +daemon refuses another build's, or a session nobody has, in words, and +hands an accepted connection to its session (`SCM_RIGHTS`), which welcomes +it and from then on is the one it talks to. Today the session answers +pings and nothing more. = 9P diff --git a/src/CHANGELOG.md b/src/CHANGELOG.md index 10cc451d..27337781 100644 --- a/src/CHANGELOG.md +++ b/src/CHANGELOG.md @@ -2,6 +2,12 @@ ## Unreleased +- The daemon also listens on `pardes-replica.sock`, a stream socket `ssh + -L` can forward, for the replicated clients to come (docs/next-daemon.md, + phase 5): a hello names a session and the client's build, another + build is refused in words, and an accepted connection is handed to its + session, which so far only welcomes it and answers pings. + `pardes --version` prints that build's semantics hash on a second line. - One `pardes --daemon` per user keeps sessions, started by the first session and gone once it keeps nothing. `pardes` in a terminal forks its session off and stays as its stub: `Detach` (`SPC s D`), or a diff --git a/src/daemon.zig b/src/daemon.zig index ac9e6eb4..702d11b1 100644 --- a/src/daemon.zig +++ b/src/daemon.zig @@ -16,14 +16,22 @@ //! //! Messages are SOCK_SEQPACKET datagrams: a line of words, and the fds it //! carries (SCM_RIGHTS). +//! +//! A replica (docs/next-daemon.md, phase 5) comes in on a stream socket of +//! its own, `pardes-replica.sock`, which `ssh -L` can forward: its hello +//! (detached/wire.zig) names a session, and once its build is the session's +//! the connection is handed to that session, which it talks to from then on. const std = @import("std"); const builtin = @import("builtin"); const libc = std.c; const posix = std.posix; const ninep_io = @import("9p_io.zig"); +const wire = @import("detached/wire.zig"); +const log = std.log.scoped(.replica); pub const supported = builtin.os.tag == .linux or builtin.os.tag == .freebsd; -const version = 1; +/// 2: a session's hello carries its semantics hash (wire.semantics). +const version = 2; pub const max_fds = 64; const msg_max = 4096; /// Idle this long, it exits: long enough for the session that started it to @@ -31,6 +39,9 @@ const msg_max = 4096; const linger_ms = 1000; const max_conns = 64; const max_held = 256; +/// Replicas whose hello is still on its way. ponytail: one that never sends +/// it holds its slot until it hangs up; past 16 a new one is closed at once. +const max_replicas = 16; const sun_path_len = ninep_io.sun_path_len; const nosignal: u32 = if (builtin.os.tag == .linux) libc.MSG.NOSIGNAL else 0; @@ -258,7 +269,7 @@ fn spawn(listener: c_int, lock: c_int) bool { /// (`watch`) takes the `ok`, and only then is the session kept (`kept`). fn hello(fd: c_int, k: Kind, pid: libc.pid_t, named: []const u8, detached: bool) bool { var buf: [256]u8 = undefined; - const words = std.fmt.bufPrint(&buf, "hello {d} {t} {d} {s} {s}", .{ version, k, pid, if (detached) "detached" else "attached", named }) catch return false; + const words = std.fmt.bufPrint(&buf, "hello {d} {t} {d} {s} {x} {s}", .{ version, k, pid, if (detached) "detached" else "attached", wire.semantics, named }) catch return false; return send(fd, words, &.{}); } @@ -376,6 +387,11 @@ fn readNotes(fd: c_int, ctx: *anyopaque, deliver: *const fn (ctx: *anyopaque, no .stub = if (got.nfds >= 2) got.fds[1] else -1, } }); for (got.fds[@min(got.nfds, 2)..got.nfds]) |f| _ = libc.close(f); + } else if (std.mem.eql(u8, verb, "replica")) { + if (got.nfds >= 1) { + if (std.Thread.spawn(.{}, serveReplica, .{got.fds[0]})) |t| t.detach() else |_| _ = libc.close(got.fds[0]); + } + for (got.fds[@min(got.nfds, 1)..got.nfds]) |f| _ = libc.close(f); } else if (std.mem.eql(u8, verb, "adopted")) { var note: Note = .{ .adopted = .{ .pids = undefined, .fds = undefined, .n = 0 } }; const a = ¬e.adopted; @@ -395,6 +411,49 @@ fn readNotes(fd: c_int, ctx: *anyopaque, deliver: *const fn (ctx: *anyopaque, no } } +fn writeAll(fd: c_int, bytes: []const u8) bool { + var at: usize = 0; + while (at < bytes.len) { + const n = libc.send(fd, bytes[at..].ptr, bytes.len - at, nosignal); + if (n < 0 and libc.errno(n) == .INTR) continue; + if (n <= 0) return false; + at += @intCast(n); + } + return true; +} + +/// A replica the daemon handed over, its hello accepted: welcomed, its pings +/// answered, until it says bye or hangs up. ponytail: phase 5 proper makes it +/// a replica (the log, the dump, terminal state); this stub is what times a +/// round trip through the daemon's handoff and `ssh -L`. A message larger +/// than its buffer ends it. +fn serveReplica(fd: c_int) void { + defer _ = libc.close(fd); + log.info("a replica connected to '{s}'", .{name()}); + defer log.info("a replica of '{s}' left", .{name()}); + var out: [wire.hello_max]u8 = undefined; + const pid: u32 = @intCast(libc.getpid()); + if (!writeAll(fd, wire.encodeServer(&out, .{ .welcome = .{ .pid = pid, .session = name() } }) catch return)) return; + var buf: [msg_max]u8 = undefined; + var len: usize = 0; + while (true) { + while (wire.framed(buf[0..len]) catch return) |f| { + switch (wire.decodeClient(f.tag, f.payload) catch return) { + .ping => |v| if (!writeAll(fd, wire.encodeServer(&out, .{ .pong = v }) catch return)) return, + .bye, .hello => return, + .event => {}, + } + std.mem.copyForwards(u8, &buf, buf[f.total..len]); + len -= f.total; + } + if (len == buf.len) return; + const n = libc.read(fd, buf[len..].ptr, buf.len - len); + if (n < 0 and libc.errno(n) == .INTR) continue; + if (n <= 0) return; + len += @intCast(n); + } +} + /// A session ended by a signal (TERM, HUP, INT): its shells go with it, as /// at a quit. Async-signal-safe: one send. One killed outright (KILL) or /// crashed says nothing, and its shells live on for an Adopt. @@ -610,6 +669,8 @@ const Conn = struct { kind: ?Kind = null, pid: libc.pid_t = 0, detached: bool = false, + /// Its build's wire.semantics: a replica's must be the same. + semantics: u64 = 0, name: [128]u8 = undefined, name_len: usize = 0, @@ -625,9 +686,18 @@ const Held = struct { owner: ?u8 = null, }; +/// A replica's connection until its hello is whole: read no further than +/// the hello, so what follows it is the session's to read. +const Replica = struct { + fd: c_int = -1, + buf: [wire.hello_max]u8 = undefined, + len: usize = 0, +}; + const Daemon = struct { conns: [max_conns]Conn = @splat(.{}), held: [max_held]Held = @splat(.{}), + replicas: [max_replicas]Replica = @splat(.{}), fn idle(d: *const Daemon) bool { for (d.conns) |c| if (c.fd >= 0) return false; @@ -668,6 +738,7 @@ const Daemon = struct { const k = std.meta.stringToEnum(Kind, words.next() orelse ""); const pid = std.fmt.parseInt(libc.pid_t, words.next() orelse "", 10) catch 0; const state = words.next() orelse ""; + const semantics = std.fmt.parseInt(u64, words.next() orelse "", 16) catch 0; const rest = std.mem.trim(u8, words.rest(), " "); if (v != version or k == null or pid <= 0) { // Another build's: it runs without a daemon. @@ -677,6 +748,7 @@ const Daemon = struct { c.kind = k; c.pid = pid; c.detached = std.mem.eql(u8, state, "detached"); + c.semantics = semantics; c.name_len = @min(rest.len, c.name.len); @memcpy(c.name[0..c.name_len], rest[0..c.name_len]); return d.reply(i, "ok", &.{}); @@ -796,6 +868,58 @@ const Daemon = struct { return error.Said; } + /// More of a replica's hello; once it is whole, the connection refused + /// in words or handed to its session. + fn hear(d: *Daemon, r: *Replica) void { + const want = if (r.len < wire.header_len) wire.header_len else wire.header_len + @as(usize, std.mem.readInt(u32, r.buf[1..5], .little)); + if (want > r.buf.len) return refuse(r, "the first message is not a hello"); + const n = libc.read(r.fd, r.buf[r.len..want].ptr, want - r.len); + if (n < 0 and libc.errno(n) == .INTR) return; + if (n <= 0) { + _ = libc.close(r.fd); + r.* = .{}; + return; + } + r.len += @intCast(n); + if (r.len < wire.header_len or r.len < wire.header_len + std.mem.readInt(u32, r.buf[1..5], .little)) return; + const f = (wire.framed(r.buf[0..r.len]) catch null) orelse return refuse(r, "the first message is not a hello"); + if (f.tag != @backingInt(wire.ClientTag.hello)) return refuse(r, "the first message is not a hello"); + var why: [512]u8 = undefined; + const v = wire.helloVersion(f.payload) catch 0; + if (v != wire.version) return refuse(r, std.fmt.bufPrint(&why, "this client speaks replica protocol {d}, and this daemon {d}: run the same pardes at both ends", .{ v, wire.version }) catch "another protocol"); + const h = (wire.decodeClient(f.tag, f.payload) catch return refuse(r, "a malformed hello")).hello; + const target = for (&d.conns, 0..) |*c, i| { + if (c.fd >= 0 and c.kind != null and std.mem.eql(u8, c.named(), h.session)) break i; + } else return refuse(r, std.fmt.bufPrint(&why, "no session called '{s}'", .{h.session}) catch "no such session"); + const t = &d.conns[target]; + if (t.semantics != h.semantics) return refuse(r, std.fmt.bufPrint(&why, "session '{s}' runs another build of pardes (semantics {x:0>16}, this client's {x:0>16}): a replica needs the same build at both ends, as `pardes --version` shows", .{ h.session, t.semantics, h.semantics }) catch "another build"); + if (!send(t.fd, "replica", &.{r.fd})) { + d.hangUp(@intCast(target)); + return refuse(r, "that session does not answer"); + } + log.info("a replica handed to '{s}'", .{h.session}); + _ = libc.close(r.fd); + r.* = .{}; + } + + fn refuse(r: *Replica, why: []const u8) void { + var out: [600]u8 = undefined; + // A fresh connection's buffer is empty: this never blocks. + if (wire.encodeServer(&out, .{ .refused = why[0..@min(why.len, 512)] })) |bytes| _ = writeAll(r.fd, bytes) else |_| {} + _ = libc.close(r.fd); + r.* = .{}; + } + + fn acceptReplica(d: *Daemon, listener: c_int) void { + const fd = libc.accept4(listener, null, null, libc.SOCK.CLOEXEC); + if (fd < 0) return; + for (&d.replicas) |*r| if (r.fd < 0) { + r.* = .{ .fd = fd }; + return; + }; + _ = libc.close(fd); + } + fn accept(d: *Daemon, listener: c_int) void { const fd = libc.accept4(listener, null, null, libc.SOCK.CLOEXEC); if (fd < 0) return; @@ -807,6 +931,21 @@ const Daemon = struct { } }; +/// The replicas' stream socket, bound and listening; -1 when it cannot be +/// (a runtime directory too long for a socket's path: 104 bytes on FreeBSD). +/// Ours to replace: the daemon's lock is held. +fn listenReplicas() c_int { + var sock_buf: [sun_path_len:0]u8 = undefined; + const sock = place(&sock_buf, "pardes-replica.sock") orelse return -1; + _ = libc.unlink(sock); + const fd = libc.socket(libc.AF.UNIX, libc.SOCK.STREAM | libc.SOCK.CLOEXEC, 0); + if (fd < 0) return -1; + const addr = address(sock); + if (libc.bind(fd, @ptrCast(&addr), @sizeOf(libc.sockaddr.un)) == 0 and libc.chmod(sock, 0o600) == 0 and libc.listen(fd, max_replicas) == 0) return fd; + _ = libc.close(fd); + return -1; +} + /// `pardes --daemon`: what `spawn` started, on the listener (fd 3) and the /// lock (fd 4). Returns only to exit, idle. pub fn serve() noreturn { @@ -815,22 +954,33 @@ pub fn serve() noreturn { ninep_io.setCloexec(4); const ignore: posix.Sigaction = .{ .handler = .{ .handler = posix.SIG.IGN }, .mask = posix.sigemptyset(), .flags = 0 }; for ([_]posix.SIG{ .PIPE, .HUP, .INT }) |sig| posix.sigaction(sig, &ignore, null); + const replicas = listenReplicas(); var d: Daemon = .{}; - const slots = 1 + max_conns + max_held; + const slots = 2 + max_conns + max_replicas + max_held; var fds: [slots]libc.pollfd = undefined; var conn_of: [slots]u8 = undefined; var held_of: [slots]u16 = undefined; + var replica_of: [slots]u8 = undefined; var buf: [msg_max]u8 = undefined; while (true) { var n: usize = 0; fds[n] = .{ .fd = listener, .events = libc.POLL.IN, .revents = 0 }; n += 1; + // -1 when there is none: poll skips a negative fd. + fds[n] = .{ .fd = replicas, .events = libc.POLL.IN, .revents = 0 }; + n += 1; const conns_at = n; for (&d.conns, 0..) |*c, i| if (c.fd >= 0) { fds[n] = .{ .fd = c.fd, .events = libc.POLL.IN, .revents = 0 }; conn_of[n] = @intCast(i); n += 1; }; + const replicas_at = n; + for (&d.replicas, 0..) |*r, i| if (r.fd >= 0) { + fds[n] = .{ .fd = r.fd, .events = libc.POLL.IN, .revents = 0 }; + replica_of[n] = @intCast(i); + n += 1; + }; const held_at = n; // No events asked of a master: its hangup (every slave closed, the // shell and all it ran gone) is reported anyway, and its output is @@ -858,7 +1008,12 @@ pub fn serve() noreturn { break; } if (fds[0].revents & libc.POLL.IN != 0) d.accept(listener); - for (fds[conns_at..held_at], conn_of[conns_at..held_at]) |pfd, i| { + if (fds[1].revents & libc.POLL.IN != 0) d.acceptReplica(replicas); + for (fds[replicas_at..held_at], replica_of[replicas_at..held_at]) |pfd, i| { + if (pfd.revents == 0 or d.replicas[i].fd != pfd.fd) continue; + d.hear(&d.replicas[i]); + } + for (fds[conns_at..replicas_at], conn_of[conns_at..replicas_at]) |pfd, i| { if (pfd.revents == 0 or d.conns[i].fd != pfd.fd) continue; const got = recv(pfd.fd, &buf) orelse { d.hangUp(i); @@ -874,6 +1029,9 @@ pub fn serve() noreturn { var sock_buf: [sun_path_len:0]u8 = undefined; _ = libc.close(listener); if (place(&sock_buf, "pardes-daemon.sock")) |sock| _ = libc.unlink(sock); + if (replicas >= 0) { + if (place(&sock_buf, "pardes-replica.sock")) |sock| _ = libc.unlink(sock); + } libc._exit(0); } diff --git a/src/detached/wire.zig b/src/detached/wire.zig index 20d75274..097cbee7 100644 --- a/src/detached/wire.zig +++ b/src/detached/wire.zig @@ -1,13 +1,41 @@ -//! The framed stream a remote client will speak (docs/next-daemon.md, -//! phase 5): fixed-width little-endian fields and explicit tags, the hello -//! and its version, and the input Events. Native struct layout never reaches -//! the wire. The cell frames that went the other way, and the frontends that -//! drew them, went with phase 3. +//! The framed stream a replica speaks (docs/next-daemon.md, phase 5), on +//! the daemon's `pardes-replica.sock` and then its session's: fixed-width +//! little-endian fields and explicit tags, the hello and its version, a +//! ping, and the input Events. Native struct layout never reaches the wire. +//! The cell frames that went the other way, and the frontends that drew +//! them, went with phase 3. const std = @import("std"); +const builtin = @import("builtin"); const pardes = @import("../pardes.zig"); - -/// 13: the frames, and every message a session sent, are gone (phase 3). -pub const version: u16 = 13; +const config = @import("pardes_config"); + +/// 14: the hello names a session and carries the semantics hash, and a +/// ping is answered (phase 5's groundwork); 13: the frames went (phase 3). +pub const version: u16 = 14; + +/// What makes two cores step differently, hashed: a replica's hello carries +/// its own, and one of another build is refused. The protocol, the release +/// and commit, the platform and build options, every dependency's content +/// hash (grammars, ghostty, Unicode) and the walker codec's assumptions +/// (pointer width, byte order). Not the OS: a Linux client of a FreeBSD +/// session is the main case, and what differs there is the host's, taped. +/// ponytail: an unstamped build (Debug with -Dplatform, every test build) +/// has no commit, so two dev trees of one release are told apart only by +/// their options and dependencies; -Dstamp-commit stamps one. +pub const semantics: u64 = blk: { + @setEvalBranchQuota(1_000_000); + break :blk std.hash.Wyhash.hash(0, std.fmt.comptimePrint( + "wire {d}\npardes {s} {s}\n{t} grammars {} {} {} {} mupdf {} themes {} workspace_tag {} sources {} board {d}x{d}\nusize {d} {t}\n{s}", + .{ + version, config.version, config.commit orelse "unstamped", + config.platform, config.syntax_highlighting, config.syntax_zig_grammar, + config.syntax_minimal_grammars, config.syntax_full_grammars, config.mupdf, + config.theme_animation, config.workspace_tag, config.embed_sources, + config.esp32p4_cols, config.esp32p4_rows, @sizeOf(usize), + builtin.cpu.arch.endian(), config.deps, + }, + )); +}; /// EndOfStream: the message ends early; WriteFailed: no room for it. /// ReadFailed is in only because std.Io.Reader says so: a fixed one never @@ -23,6 +51,7 @@ pub const header_len = 5; // tag:u8, payload length:u32le pub const ClientTag = enum(u8) { hello = 0x01, bye = 0x02, + ping = 0x03, key = 0x10, mouse = 0x11, @@ -59,12 +88,50 @@ const KindTag = enum(u8) { press = 0x00, release = 0x01, motion = 0x02, drag = 0 /// when the rest of the layout is the part that changed. pub const Hello = struct { version: u16 = version, - /// This client's grid. Never zero: a client not sized yet must not - /// collapse a shared session (getCols). - cols: u16, - rows: u16, + /// The client's `semantics`: the daemon refuses it unless the session's + /// is the same. + semantics: u64 = semantics, + /// Which session (its 9P name, as `--attach=` names it). + session: []const u8, +}; + +/// A session's name on the wire, as the daemon keeps it. +pub const max_name = 128; +/// The longest hello there is, header and all. +pub const hello_max = header_len + 2 + 8 + 2 + max_name; + +/// Daemon or session -> client. +pub const ServerTag = enum(u8) { + /// The hello is accepted and the connection is the session's now: its pid + /// and name. + welcome = 0x01, + /// Refused, said in words; the connection ends. + refused = 0x02, + /// A ping's value back. + pong = 0x03, }; +pub const ServerMsg = union(ServerTag) { + welcome: struct { pid: u32, session: []const u8 }, + refused: []const u8, + pong: u64, +}; + +pub fn encodeServer(out: []u8, msg: ServerMsg) Error![]const u8 { + var w: std.Io.Writer = .fixed(out); + const at = try beginMessage(&w, @backingInt(std.meta.activeTag(msg))); + switch (msg) { + .welcome => |h| { + try w.writeInt(u32, h.pid, .little); + try putSlice16(&w, h.session); + }, + .refused => |words| try putSlice16(&w, words), + .pong => |v| try w.writeInt(u64, v, .little), + } + try finishMessage(&w, at); + return w.buffered(); +} + /// `Hello.version` alone, read out of the still-undecoded payload. /// /// Separate from `decodeClient` because of the guarantee the fixed offset above @@ -88,6 +155,8 @@ pub fn helloVersion(payload: []const u8) Error!u16 { pub const ClientMsg = union(enum) { hello: Hello, bye, + /// A round trip's probe, answered `pong` with the same value. + ping: u64, event: pardes.Event, }; @@ -291,10 +360,12 @@ pub fn encodeClient(out: []u8, msg: ClientMsg) Error![]const u8 { switch (msg) { .hello => |h| { try w.writeInt(u16, h.version, .little); - try w.writeInt(u16, h.cols, .little); - try w.writeInt(u16, h.rows, .little); + try w.writeInt(u64, h.semantics, .little); + if (h.session.len > max_name) return error.Overlong; + try putSlice16(&w, h.session); }, .bye => {}, + .ping => |v| try w.writeInt(u64, v, .little), .event => |ev| switch (ev) { .key => |k| { try w.writeInt(u32, k.cp, .little); @@ -352,10 +423,15 @@ pub fn decodeClient(tag: u8, payload: []const u8) Error!ClientMsg { const msg: ClientMsg = switch (std.enums.fromInt(ClientTag, tag) orelse return error.BadTag) { .hello => .{ .hello = .{ .version = try r.takeInt(u16, .little), - .cols = try getCols(&r), - .rows = try getRows(&r), + .semantics = try r.takeInt(u64, .little), + .session = blk: { + const n = try r.takeInt(u16, .little); + if (n > max_name) return error.BadValue; + break :blk try r.take(n); + }, } }, .bye => .bye, + .ping => .{ .ping = try r.takeInt(u64, .little) }, .key => blk: { const cp = try r.takeInt(u32, .little); // `Key.cp` is a u21, and the specials live in the private-use @@ -415,7 +491,8 @@ const msg_slack = header_len + 64; /// once instead of guessing and retrying. pub fn clientBound(msg: ClientMsg) usize { return msg_slack + switch (msg) { - .hello, .bye => 0, + .hello => |h| h.session.len, + .bye, .ping => 0, .event => |ev| switch (ev) { .mouse, .resize, .pdf_scroll, .pinch, .touch_scroll, .pointer_leave, .focus => 0, .key => |k| k.text.len, @@ -458,12 +535,21 @@ test "detached wire: every Event variant round-trips" { try testing.expectEqual(@as(u8, 0x1d), @backingInt(ClientTag.pointer_leave)); { - const got = try roundClient(&buf, .{ .hello = .{ .cols = 80, .rows = 24 } }); + const got = try roundClient(&buf, .{ .hello = .{ .session = "work" } }); try testing.expectEqual(version, got.hello.version); - try testing.expectEqual(@as(u16, 80), got.hello.cols); - try testing.expectEqual(@as(u16, 24), got.hello.rows); + try testing.expectEqual(semantics, got.hello.semantics); + try testing.expectEqualStrings("work", got.hello.session); } try testing.expectEqual(ClientMsg.bye, try roundClient(&buf, .bye)); + try testing.expectEqual(@as(u64, 0xfeed_beef_0000_0001), (try roundClient(&buf, .{ .ping = 0xfeed_beef_0000_0001 })).ping); + { + // The other way: framed the same, its tag the ServerTag's number. + const bytes = try encodeServer(&buf, .{ .welcome = .{ .pid = 42, .session = "work" } }); + const f = (try framed(bytes)).?; + try testing.expectEqual(@as(u8, 0x01), f.tag); + try testing.expectEqualSlices(u8, &.{ 42, 0, 0, 0, 4, 0, 'w', 'o', 'r', 'k' }, f.payload); + try testing.expectEqual(@as(u8, 0x03), (try framed(try encodeServer(&buf, .{ .pong = 7 }))).?.tag); + } { const key: pardes.Key = .{ .cp = pardes.Key.page_down, .text = "ü", .ctrl = true, .alt = false, .shift = true }; @@ -530,20 +616,19 @@ test "detached wire: a session is never told to do a frontend's remembering" { // Adding a name here is meant to be an ARGUMENT, not a formality, and the // bar is one sentence: A HUMAN DID IT. A keystroke, a click, a pinch, a // window resized, a paste, a command line executed, a pointer leaving the - // window, the window's focus — plus the two session words that say who is speaking. A pty's + // window, the window's focus — plus the session words that say who is speaking, time the link and end it. A pty's // output, a worker's answer, a watched file's new bytes and an animation // tick all fail that bar the same way: nobody did them, a machine reported // them, and the machine that reports them is the one already holding the // core. const allowed = [_][]const u8{ - // Who this connection is, and that it is finished. - "hello", "bye", + // Who this connection is, its round trip, and that it is finished. + "hello", "bye", "ping", // ...and everything a person can do to a window. - "key", "mouse", - "resize", "paste", - "command", "pdf_scroll", - "pinch", "touch_scroll", - "pointer_leave", "focus", + "key", "mouse", "resize", + "paste", "command", "pdf_scroll", + "pinch", "touch_scroll", "pointer_leave", + "focus", }; // One: the tag set is exactly that, named rather than counted, so @@ -663,18 +748,16 @@ test "detached wire: values a field cannot mean are refused" { @backingInt(ClientTag.pdf_scroll), &.{pardes.MAX_PANES}, )); - // A zero-column grid would collapse a shared session; an over-wide one is - // past what this protocol carries. - try testing.expectError(error.BadValue, decodeClient( - @backingInt(ClientTag.hello), - &.{ 1, 0, 0, 0, 24, 0 }, - )); + // A session name longer than the daemon keeps one: refused, never cut + // to another session's name. { - var hello: [6]u8 = undefined; + var hello: [12 + max_name + 1]u8 = @splat('x'); std.mem.writeInt(u16, hello[0..2], version, .little); - std.mem.writeInt(u16, hello[2..4], max_cols + 1, .little); - std.mem.writeInt(u16, hello[4..6], 24, .little); + std.mem.writeInt(u16, hello[10..12], max_name + 1, .little); try testing.expectError(error.BadValue, decodeClient(@backingInt(ClientTag.hello), &hello)); + std.mem.writeInt(u16, hello[10..12], max_name, .little); + try testing.expectEqual(@as(usize, max_name), (try decodeClient(@backingInt(ClientTag.hello), hello[0 .. hello.len - 1])).hello.session.len); + try testing.expect(header_len + hello.len - 1 == hello_max); } // A NaN scroll distance. `pinch` multiplies into a zoom the pane keeps. { diff --git a/src/main.zig b/src/main.zig index 378dbea8..f310bf3c 100644 --- a/src/main.zig +++ b/src/main.zig @@ -288,10 +288,12 @@ fn badArgs(io: std.Io, comptime fmt: []const u8, args: anytype) noreturn { std.process.exit(1); } -const version_text = if (pardes.commit) |c| +/// The second line is what a replica's build must share with its session's +/// (detached/wire.zig `semantics`). +const version_text = (if (pardes.commit) |c| "pardes " ++ pardes.version ++ " (" ++ c ++ ")\n" else - "pardes " ++ pardes.version ++ "\n"; + "pardes " ++ pardes.version ++ "\n") ++ std.fmt.comptimePrint("semantics {x:0>16}\n", .{@import("detached/wire.zig").semantics}); const nested_text = \\pardes: this shell is already inside pardes, and a pardes inside a pardes diff --git a/test/daemon.py b/test/daemon.py index 41cfbaf7..2be3f355 100644 --- a/test/daemon.py +++ b/test/daemon.py @@ -6,16 +6,24 @@ private HOME and runtime directory: from another terminal, N times; - a session killed outright: its shells live on, held by the daemon, and another session adopts them as terminal panes; +- a replica's hello on the daemon's stream socket (phase 5): one of this + build handed to its session, which answers it and its pings; another + build's refused, and a session nobody has; - nothing left behind: no session, shell, daemon or socket. python3 -B test/daemon.py [cycles] python3 -B test/daemon.py --gui [cycles] (a hidden window; needs a Wayland display, and a pardes beside it for the refusal) + python3 -B test/daemon.py --ping [n] + a hello of 's build and n pings on a replica socket (one + `ssh -L` forwards, say), timed """ import fcntl import os import shutil import signal +import socket +import statistics import struct import subprocess import sys @@ -153,6 +161,103 @@ def fds(pid): return -1 +def semantics(binary): + """What a replica's build must share with its session's (--version).""" + out = subprocess.run([binary, '--version'], capture_output=True, check=True).stdout.decode() + return int(next(line.split()[1] for line in out.splitlines() if line.startswith('semantics ')), 16) + + +class Replica: + """A replica's connection (src/detached/wire.zig): length-prefixed + messages, a tag byte and a little-endian u32 length.""" + WIRE = 14 + + def __init__(self, path, timeout=10): + self.s = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM) + self.s.settimeout(timeout) + self.s.connect(os.fspath(path)) + + def send(self, tag, payload): + self.s.sendall(struct.pack(' 5 else 50) + elif '--gui' in sys.argv: args = [a for a in sys.argv[1:] if a != '--gui'] gui(args[0], int(args[1]) if len(args) > 1 else 50) else: -- cgit v1.3 From 1c87b21d9255d9b0a7af102afd7defec25ac2c8a Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 16:55:47 -0300 Subject: rollback-bench and fork_stall.py: what a replica's rollback copy is (a walk of ~100 KB once file texts are pinned) and what a fork stalls the authority for, which settle open points 3 and 5 `zig build rollback-bench -Dplatform=tty -Doptimize=ReleaseFast` (test/rollback_bench.zig) builds a typical session (a shell with 1 MB of scrollback, three 60 KB files and a 3 MB one, 40 edits) and a big one (14 panes, 18 MB, 4x3 MB and 8 small files, 8 MB of scrollback, 200 edits) in process, then measures the state the digest walk visits, the part of it that is a file's text and its undo snapshots (immutable once made: an edit puts a new buffer in place, a snapshot is a copy, so a copy pins them), and the walk again with those taken out, plus a memcpy of what is left. Typical: 36.3 MB walked, 80 KB to copy, about 0.02 ms; big: 282.5 MB, 96 KB, about 0.045 ms. Then a fork of the big session (431 MB RSS: 3.4 to 8.3 ms) and 64 MB written by the parent under the child (~28 ms of copy-on-write). test/fork_stall.py does the fork alone, on any system with a Python (the FreeBSD box): N MB written, then fork() timed and 64 MB written under the child, with Linux's THP as set and with 4 KiB pages. 1 GB: 13.3 to 19.6 ms here, 20.4 ms on FreeBSD 15.1; the copy-on-write after it ~1.3 us a page on both. Co-Authored-By: Claude Opus 5.5 --- build.zig | 9 ++ test/fork_stall.py | 76 +++++++++++++++ test/rollback_bench.zig | 246 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 331 insertions(+) create mode 100644 test/fork_stall.py create mode 100644 test/rollback_bench.zig (limited to 'build.zig') diff --git a/build.zig b/build.zig index 24476753..13cb8ebc 100644 --- a/build.zig +++ b/build.zig @@ -1495,6 +1495,15 @@ pub fn build(b: *std.Build) void { const lspbench_check_step = b.step("lspbench-check", "require every configured language probe to complete correctly"); lspbench_check_step.dependOn(&run_lspbench_check.step); + const rollback_bench = b.addExecutable(.{ + .name = "pardes-rollback-bench", + .root_module = b.createModule(.{ .target = target, .optimize = optimize, .root_source_file = b.path("test/rollback_bench.zig"), .link_libc = true }), + }); + rollback_bench.root_module.addImport("pardes", core_module); + const run_rollback_bench = b.addRunArtifact(rollback_bench); + run_rollback_bench.has_side_effects = true; + b.step("rollback-bench", "a replica's rollback copy (walked state, pinned blobs, walk time) for a typical and a big session, and a fork of the big one (-Doptimize=ReleaseFast)").dependOn(&run_rollback_bench.step); + const locations_bench_step = b.step("locations-bench", "measure cold/warm result formatting (-Doptimize=ReleaseFast; CSV on stderr)"); if (optimize != .fast) { locations_bench_step.dependOn(&b.addFail("locations-bench requires -Doptimize=ReleaseFast").step); diff --git a/test/fork_stall.py b/test/fork_stall.py new file mode 100644 index 00000000..c865b6bc --- /dev/null +++ b/test/fork_stall.py @@ -0,0 +1,76 @@ +#!/usr/bin/env python3 +"""What a fork stalls the authority for (docs/next-daemon.md, open point 5: +the join writer as a fork child): a process holding N MB of written +anonymous memory, as a session's heap and arenas are, forks a child that +waits and exits; timed are the fork() itself and the copy-on-write of the +authority's next 64 MB written while the child lives. + + python3 -B test/fork_stall.py [MB ...] (default 100 600 1024 4096) + +On Linux each size runs twice: with transparent huge pages as the system +has them, and with MADV_NOHUGEPAGE (4 KiB pages, as a fragmented heap). +""" +import mmap +import os +import statistics +import sys +import time + +REPS = 9 +COW = 64 << 20 + + +def fill(m, size): + block = b'\1' * (16 << 20) + for at in range(0, size, len(block)): + m[at:at + len(block)] = block[:size - at] + + +def one(size, huge): + m = mmap.mmap(-1, size, flags=mmap.MAP_PRIVATE | mmap.MAP_ANONYMOUS) + if not huge: + m.madvise(mmap.MADV_NOHUGEPAGE) + fill(m, size) + forks, cows = [], [] + for _ in range(REPS): + r, w = os.pipe() + t0 = time.perf_counter_ns() + pid = os.fork() + if pid == 0: + os.read(r, 1) + os._exit(0) + t1 = time.perf_counter_ns() + # What the authority writes next, the child holding its pages. + for at in range(0, min(COW, size), 4096): + m[at] = 2 + t2 = time.perf_counter_ns() + os.write(w, b'x') + os.waitpid(pid, 0) + os.close(r) + os.close(w) + forks.append((t1 - t0) / 1e6) + cows.append((t2 - t1) / 1e6) + # The same writes with no child: the loop's own cost, taken off. + t0 = time.perf_counter_ns() + for at in range(0, min(COW, size), 4096): + m[at] = 3 + loop = (time.perf_counter_ns() - t0) / 1e6 + m.close() + return statistics.median(forks), max(forks), statistics.median(cows) - loop + + +def main(): + sizes = [int(a) for a in sys.argv[1:]] or [100, 600, 1024, 4096] + modes = [True, False] if hasattr(mmap, 'MADV_NOHUGEPAGE') else [True] + print(f'{os.uname().sysname} {os.uname().release}: fork of a process with N MB written, ' + f'median and max of {REPS}; then {COW >> 20} MB written under the child') + for size in sizes: + for huge in modes: + fork_med, fork_max, cow = one(size << 20, huge) + pages = 'system pages' if huge else '4 KiB pages' + print(f'{size:>6} MB {pages:<12} fork {fork_med:8.3f} ms (max {fork_max:8.3f}) ' + f'cow {cow:8.3f} ms', flush=True) + + +if __name__ == '__main__': + main() diff --git a/test/rollback_bench.zig b/test/rollback_bench.zig new file mode 100644 index 00000000..721c6f13 --- /dev/null +++ b/test/rollback_bench.zig @@ -0,0 +1,246 @@ +//! What a replica's rollback copy would cost (docs/next-daemon.md, open +//! point 3), and what a fork of the authority stalls it for (open point 5). +//! A typical session and a big one are built in process; for each: +//! - the state the walker visits (src/walk.zig's digest walk, which is +//! what speculation can write: views, buffers, registers, counters, +//! terminal metadata), in bytes; +//! - the part of it that is pinned blobs: a file's text and its undo +//! snapshots, which an edit replaces rather than changes +//! (File.setContentSpan), so a copy keeps a reference; +//! - the walk's time, the blobs' share of it, and a memcpy of the rest: +//! a walker copy costs about the walk plus that write. +//! Then a fork of the big one, child gone at once, and the authority's +//! copy-on-write after it. +//! +//! zig build rollback-bench -Dplatform=tty -Doptimize=ReleaseFast +const std = @import("std"); +const libc = std.c; +const pardes = @import("pardes"); +const walk = pardes.walk; + +const gpa = std.heap.c_allocator; + +fn nowNs() u64 { + var ts: libc.timespec = undefined; + _ = libc.clock_gettime(.MONOTONIC, &ts); + return @as(u64, @intCast(ts.sec)) *| 1_000_000_000 +| @as(u64, @intCast(ts.nsec)); +} + +const File = struct { lines: usize, copies: usize = 1 }; + +const Session = struct { + name: []const u8, + files: []const File, + /// The shell's scrollback, fed through its terminal. + scrollback_kb: usize, + /// Insert sessions (`i x Esc`), each an undo step, spread over the files. + edits: usize, +}; + +// 60-column lines: 1k lines is 60 KB, 50k is 3 MB, 300k is 18 MB. +const sessions = [_]Session{ + .{ .name = "typical", .files = &.{ .{ .lines = 1_000, .copies = 3 }, .{ .lines = 50_000 } }, .scrollback_kb = 1024, .edits = 40 }, + .{ .name = "big", .files = &.{ .{ .lines = 1_000, .copies = 8 }, .{ .lines = 50_000, .copies = 4 }, .{ .lines = 300_000 } }, .scrollback_kb = 8 * 1024, .edits = 200 }, +}; + +fn pump(core: *pardes.Pardes) void { + while (core.nextEffect()) |_| {} +} + +fn key(core: *pardes.Pardes, cp: u21, text: []const u8) void { + core.update(.{ .key = .{ .cp = cp, .text = text } }); + pump(core); +} + +fn writeFile(path: []const u8, lines: usize) !void { + var out: std.Io.Writer.Allocating = .init(gpa); + defer out.deinit(); + for (0..lines) |n| try out.writer.print("const value_{d:0>7}: u32 = {d:0>10}; // a line of sixty\n", .{ n, n *% 2654435761 }); + var pathbuf: [4096]u8 = undefined; + const fd = libc.open(try std.fmt.bufPrintSentinel(&pathbuf, "{s}", .{path}, 0), .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = libc.close(fd); + const text = out.written(); + var off: usize = 0; + while (off < text.len) { + const n = libc.write(fd, text.ptr + off, text.len - off); + if (n <= 0) return error.WriteFailed; + off += @intCast(n); + } +} + +fn build(s: Session, dir: []const u8) !*pardes.Pardes { + const core = try pardes.Pardes.init(gpa, .{ .tty_only = true }); + core.update(.{ .resize = .{ .cols = 200, .rows = 60 } }); + pump(core); + // The shell: pane 0 of a tty boot, its output fed as a pty's. + var chunk: std.Io.Writer.Allocating = .init(gpa); + defer chunk.deinit(); + var n: usize = 0; + while (chunk.written().len < s.scrollback_kb * 1024) : (n += 1) + try chunk.writer.print("\x1b[90m[{d:0>6}]\x1b[0m compiling module_{d} ... \x1b[32mok\x1b[0m\r\n", .{ n, n }); + var off: usize = 0; + while (off < chunk.written().len) { + const end = @min(off + 8192, chunk.written().len); + core.update(.{ .output = .{ .pane = 0, .bytes = chunk.written()[off..end] } }); + pump(core); + off = end; + } + var opened: [pardes.MAX_PANES]usize = undefined; + var nopened: usize = 0; + for (s.files, 0..) |f, fi| for (0..f.copies) |c| { + var buf: [512]u8 = undefined; + const path = try std.fmt.bufPrint(&buf, "{s}/f{d}-{d}.zig", .{ dir, fi, c }); + try writeFile(path, f.lines); + pardes.look.lookAt(core, 0, path); + pump(core); + for (core.panes, 0..) |slot, id| if (slot) |pane| if (pane.file) |file| if (std.mem.eql(u8, file.path, path)) { + opened[nopened] = id; + nopened += 1; + }; + }; + if (nopened == 0) return error.NothingOpened; + for (0..s.edits) |e| { + core.active = opened[e % nopened]; + key(core, 'i', "i"); + key(core, 'x', "x"); + key(core, pardes.Key.escape, ""); + } + var arena: std.heap.ArenaAllocator = .init(gpa); + defer arena.deinit(); + _ = try core.render(arena.allocator()); + return core; +} + +/// Where a file's text and its undo snapshots are held: what a copy pins. +fn blobs(core: *pardes.Pardes, out: *std.ArrayList(*[]u8)) !usize { + var total: usize = 0; + for (core.panes) |slot| if (slot) |pane| if (pane.file) |*f| { + try out.append(gpa, &f.content); + for (f.history.undo[0..f.history.undo_len]) |*snap| try out.append(gpa, &snap.content); + for (f.history.redo[0..f.history.redo_len]) |*snap| try out.append(gpa, &snap.content); + }; + for (out.items) |b| total += b.len; + return total; +} + +fn walkNs(core: *const pardes.Pardes) u64 { + var t: [reps]u64 = undefined; + var sink: u64 = 0; + for (&t) |*x| { + const t0 = nowNs(); + sink +%= walk.digest(pardes.Pardes, core); + x.* = nowNs() - t0; + } + std.mem.doNotOptimizeAway(sink); + return median(&t); +} + +fn walked(core: *const pardes.Pardes) usize { + var h = walk.Hasher.init(0); + walk.hash(pardes.Pardes, core, &h); + return h.total_len; +} + +fn median(samples: []u64) u64 { + std.mem.sort(u64, samples, {}, std.sort.asc(u64)); + return samples[samples.len / 2]; +} + +fn rssKb() usize { + var ru: libc.rusage = undefined; + _ = libc.getrusage(libc.rusage.SELF, &ru); + return @intCast(ru.maxrss); +} + +const reps = 15; + +pub fn main(init: std.process.Init) !void { + var dir_buf: [256]u8 = undefined; + const tmp = std.mem.span(libc.getenv("TMPDIR") orelse "/tmp"); + const dir = try std.fmt.bufPrint(&dir_buf, "{s}/rollback-bench-{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 {}; + std.debug.print("session panes walked MB blobs MB copy KB walk ms walk ms, blobs out memcpy ms copy ms (est.)\n", .{}); + var big: ?*pardes.Pardes = null; + for (sessions) |s| { + const core = try build(s, dir); + var list: std.ArrayList(*[]u8) = .empty; + defer list.deinit(gpa); + const blob_bytes = try blobs(core, &list); + const all = walked(core); + const walk_ns = walkNs(core); + // The blobs taken out, as a copy pins them: the walk of what a copy + // writes, then put back. + const kept = try gpa.alloc([]u8, list.items.len); + defer gpa.free(kept); + for (list.items, kept) |b, *k| { + k.* = b.*; + b.* = &.{}; + } + const copy_bytes = walked(core); + const copy_walk_ns = walkNs(core); + for (list.items, kept) |b, k| b.* = k; + const src = try gpa.alloc(u8, @max(copy_bytes, 1)); + defer gpa.free(src); + const dst = try gpa.alloc(u8, @max(copy_bytes, 1)); + defer gpa.free(dst); + @memset(src, 1); + @memset(dst, 0); + var t: [reps]u64 = undefined; + for (&t) |*x| { + const t0 = nowNs(); + @memcpy(dst, src); + std.mem.doNotOptimizeAway(dst.ptr); + x.* = nowNs() - t0; + } + const memcpy_ns = median(&t); + var panes: usize = 0; + for (core.panes) |slot| panes += @intFromBool(slot != null); + const ms = 1e-6; + std.debug.print("{s:<8} {d:>5} {d:>9.1} {d:>8.1} {d:>7.1} {d:>7.3} {d:>18.3} {d:>9.3} {d:>14.3}\n", .{ + s.name, panes, + @as(f64, @floatFromInt(all)) / 1e6, @as(f64, @floatFromInt(blob_bytes)) / 1e6, + @as(f64, @floatFromInt(copy_bytes)) / 1e3, @as(f64, @floatFromInt(walk_ns)) * ms, + @as(f64, @floatFromInt(copy_walk_ns)) * ms, @as(f64, @floatFromInt(memcpy_ns)) * ms, + @as(f64, @floatFromInt(copy_walk_ns + memcpy_ns)) * ms, + }); + if (big) |b| b.deinit(); + big = core; + } + // The join writer as a fork child: what fork() holds the authority for, + // and its copy-on-write after, the child alive. The child waits on a + // pipe and exits. + const core = big.?; + defer core.deinit(); + var t: [reps]u64 = undefined; + var cow: [reps]u64 = undefined; + const touch = try gpa.alloc(u8, 64 << 20); + defer gpa.free(touch); + @memset(touch, 1); + for (&t, &cow) |*x, *c| { + var pipe: [2]c_int = undefined; + if (libc.pipe(&pipe) != 0) return error.Pipe; + const t0 = nowNs(); + const pid = libc.fork(); + if (pid == 0) { + var one: [1]u8 = undefined; + _ = libc.read(pipe[0], &one, 1); + libc._exit(0); + } + x.* = nowNs() - t0; + // 64 MB the authority writes while the child holds its pages. + const t1 = nowNs(); + var i: usize = 0; + while (i < touch.len) : (i += 4096) touch[i] +%= 1; + c.* = nowNs() - t1; + _ = libc.close(pipe[0]); + _ = libc.write(pipe[1], "x", 1); + _ = libc.close(pipe[1]); + var status: c_int = 0; + _ = libc.waitpid(pid, &status, 0); + } + std.debug.print("fork of the big session (max RSS {d} MB): {d:.3} ms; then 64 MB written under the child: {d:.3} ms\n", .{ + rssKb() / 1024, @as(f64, @floatFromInt(median(&t))) / 1e6, @as(f64, @floatFromInt(median(&cow))) / 1e6, + }); +} -- cgit v1.3 From 3b57a72becd6dd6700d996c9c5c000e1cb53e076 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 18:19:13 -0300 Subject: phase 5 part A: the speculation and rollback engine, in one process: a walker copy put back where it was, replicas that apply their own input at once and take the authority's tape as the truth, and a harness of typists over delayed links src/rollback.zig: the replica core's allocator (`Epoch`) knows every allocation, and while a copy is held puts off frees of what was there before and refuses to grow it in place, so what the core held stays where it was. The copy (`Copy`) is the digest's walk saving the bytes of every allocation it reaches, field by field (the derived caches and this process's own too: a safe build's free writes over what it frees, and the frame arena points at what the epoch then frees), but the queues a step drains and the frame statistics; a file's text, its line index and its undo snapshots are pinned instead (made anew at each edit, never written; now freed raw everywhere), checked unchanged in a safe build. Put back, each allocation's bytes go back over it, the epoch's allocations are freed and its put-off frees forgotten; let go, they are made. Tree-sitter's trees, the C heap's, are held the same way (syntax.held_trees). src/replica.zig: an `Authority` records its core's every input to a tape in memory and hands each client's input back as a unit (origin, sequence number, its tape); a `Replica` applies its own input at once, as the authority will (update, then pump), recorded by its own tape (tape.zig's speculation mode), and for each unit in order drops its pending head when the authority recorded the same (inputs, host calls and answers: the fast path), else puts the copy back, replays the units since and this one (every digest checked) and applies its pending inputs again. A host call or a syscall stops a speculation: it is answered harmlessly, undone when it returns, and the input waits for the authority's answer; a clock or environment read is a guess the comparison checks; an emulator is the authority's (terminal.zig's writers stop a speculation; a safe build asserts none changed). The view's events (a resize, the pointer) wait. Messages are bytes: no transport yet. Each client has a view of its own (src/views.zig): the authority goes into it before the client's input (`toView`, taped), the replica's speculation the same, and the copy walks the views not live too (`parked`, each pane's `pv`). test/replicas.zig (`zig build replicas`): one authority and N replicas, a view each (`--shared` puts them in one), each client typing monkey.zig's mix at 50-200 ms over its own link (half the RTT plus 10% jitter, in order), the authority's pty echoing 2 ms later; gates: no replica diverges, every replica's digest is the authority's at quiescence; reported per RTT: inputs applied at once, stopped, waiting, fast paths, rollbacks (mispredicted, foreign), and what a speculative apply, a copy and a rollback cost. 3 clients x 100 inputs at 30, 80 and 207 ms: no divergence over 12 Debug seeds and 20 ReleaseFast ones with a filled heap; ReleaseFast p99 a speculative apply under 0.2 ms, a rollback under 1.6 ms. `zig build rollback-bench` times the real copy now (take, release, an edit, restore). What the replicas found, fixed: a release build reads what the heap had where Debug's fill made two cores agree: `col_panes` and `restore_buf` digested undefined (zeroed now), `terminal.State.reply_dropped` never set at create, `Text.sels` and `PendingPipe.ranges` digested past their length (a walker `len` cuts a slice too). PARDES_REPLICA_FILL fills a replica's allocations to show what is left. Co-Authored-By: Claude Opus 5.5 --- build.zig | 10 + src/File.zig | 14 +- src/Pipe.zig | 2 + src/Text.zig | 6 +- src/memory.zig | 9 + src/pardes.zig | 11 +- src/replica.zig | 578 ++++++++++++++++++++++++++++++++++++++++++++++++ src/rollback.zig | 496 +++++++++++++++++++++++++++++++++++++++++ src/syntax.zig | 24 ++ src/tape.zig | 236 ++++++++++++++++++-- src/terminal.zig | 17 ++ src/walk.zig | 24 +- test/replicas.zig | 327 +++++++++++++++++++++++++++ test/rollback_bench.zig | 120 ++++------ 14 files changed, 1763 insertions(+), 111 deletions(-) create mode 100644 src/replica.zig create mode 100644 src/rollback.zig create mode 100644 test/replicas.zig (limited to 'build.zig') diff --git a/build.zig b/build.zig index 13cb8ebc..1a5dd200 100644 --- a/build.zig +++ b/build.zig @@ -1504,6 +1504,16 @@ pub fn build(b: *std.Build) void { run_rollback_bench.has_side_effects = true; b.step("rollback-bench", "a replica's rollback copy (walked state, pinned blobs, walk time) for a typical and a big session, and a fork of the big one (-Doptimize=ReleaseFast)").dependOn(&run_rollback_bench.step); + const replicas = b.addExecutable(.{ + .name = "pardes-replicas", + .root_module = b.createModule(.{ .target = target, .optimize = optimize, .root_source_file = b.path("test/replicas.zig"), .link_libc = true }), + }); + replicas.root_module.addImport("pardes", core_module); + const run_replicas = b.addRunArtifact(replicas); + run_replicas.addPassthruArgs(); + run_replicas.has_side_effects = true; + b.step("replicas", "one authority and several replicas in process, each client typing over a delayed link: digests at quiescence, rollback rate and costs per RTT (-- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207])").dependOn(&run_replicas.step); + const locations_bench_step = b.step("locations-bench", "measure cold/warm result formatting (-Doptimize=ReleaseFast; CSV on stderr)"); if (optimize != .fast) { locations_bench_step.dependOn(&b.addFail("locations-bench requires -Doptimize=ReleaseFast").step); diff --git a/src/File.zig b/src/File.zig index dd6b2d34..84222191 100644 --- a/src/File.zig +++ b/src/File.zig @@ -1159,10 +1159,12 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { if (p.panes[id].?.file.?.line_starts.ptr == file.line_starts.ptr) break true; } else false; p.gpa.free(file.path); - if (ntwins == 0) p.gpa.free(file.content); + // Raw, as every text is freed (a replica's rollback copy pins them, + // src/rollback.zig, and a safe build's free writes over what it frees). + if (ntwins == 0) pardes.memory.freeUnfilled(p.gpa, file.content); if (file.listing) |listing| p.gpa.free(listing.names); if (file.mini) |*mini| mini.deinit(p.gpa); - if (file.line_starts.len > 0 and !index_shared) p.gpa.free(file.line_starts); + if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, file.line_starts); if (file.highlights.len > 0) p.tree_sitter_gpa.free(file.highlights); p.gpa.free(file.pager_spans); locations.freeRows(p.gpa, file.location_rows); @@ -1264,7 +1266,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { }; // The clock the session that recorded read (src/tape.zig). f.mtime = pardes.tape.value(.mtime, pardes.ctlfs.events.now, .{}); - if (f.line_starts.len > 0) p.gpa.free(f.line_starts); + if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); f.line_starts = starts; if (f.highlights.len > 0) p.tree_sitter_gpa.free(f.highlights); f.highlights = &.{}; @@ -1276,7 +1278,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { const tf = &t.file.?; // Its own index, built while the shared one was empty, goes; the // shared one, freed above, is replaced. - if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) p.gpa.free(tf.line_starts); + if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, tf.line_starts); tf.content = f.content; tf.line_starts = f.line_starts; tf.revision = f.revision; @@ -1498,8 +1500,8 @@ pub fn relink(p: *Pardes, of: usize, id: usize, dot: ?[2]u32) void { sf.twin = p.next_twin; p.next_twin +%= 1; } - p.gpa.free(f.content); - if (f.line_starts.len > 0) p.gpa.free(f.line_starts); + pardes.memory.freeUnfilled(p.gpa, f.content); + if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); f.history.destroy(p.gpa); f.content = sf.content; f.line_starts = sf.line_starts; diff --git a/src/Pipe.zig b/src/Pipe.zig index 850f9c64..239a94e4 100644 --- a/src/Pipe.zig +++ b/src/Pipe.zig @@ -52,6 +52,8 @@ pub fn pipeMarker(how: modal.Normal.PipeBehavior) []const u8 { } pub const PendingPipe = struct { + /// The digest's walk (src/walk.zig) of the ranges, as far as they go. + pub const replica = .{ .len = .{.{ "ranges", "nranges" }} }; id: u32, pane: usize, serial: u32, diff --git a/src/Text.zig b/src/Text.zig index 3f107542..da4be590 100644 --- a/src/Text.zig +++ b/src/Text.zig @@ -49,9 +49,9 @@ pub const SelRange = struct { sticky: i32 = -1, }; -/// The replay digest's walk (src/walk.zig) of the histories: as far as -/// they go. -pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" } } }; +/// The replay digest's walk (src/walk.zig) of the histories and the ranges: +/// as far as they go (the ranges' room is made whole and used `nsel` deep). +pub const replica = .{ .len = .{ .{ "ed_undo", "ed_undo_len" }, .{ "ed_redo", "ed_redo_len" }, .{ "sels", "nsel" } } }; what: What = .body, /// The characters of a text that holds its own (gpa-owned): everything but diff --git a/src/memory.zig b/src/memory.zig index 47bd755d..1d082964 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -421,6 +421,15 @@ pub fn freeUnfilled(allocator: Allocator, bytes: []const u8) void { if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(u8), @returnAddress()); } +/// `freeUnfilled` for a slice of any element: a text's line index, made +/// anew at every edit too (and pinned by a replica's rollback copy, +/// src/rollback.zig, which a safe build's overwrite would spoil). +pub fn freeRaw(allocator: Allocator, items: anytype) void { + const E = @typeInfo(@TypeOf(items)).pointer.child; + const bytes = std.mem.sliceAsBytes(items); + if (bytes.len > 0) allocator.rawFree(@constCast(bytes), .of(E), @returnAddress()); +} + /// Gives free memory back to the system, the arenas' and libc's, inside its /// heap too: after a big result is formatted or a big pane torn down, the /// tree-sitter arena kept 73 MiB of emptied buckets resident and glibc what diff --git a/src/pardes.zig b/src/pardes.zig index 75e91ee9..5d889c86 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -65,6 +65,8 @@ pub const tape = @import("tape.zig"); pub const walk = @import("walk.zig"); pub const screen_state = if (terminal_panes) @import("screen_state.zig") else struct {}; pub const views = @import("views.zig"); +pub const rollback = @import("rollback.zig"); +pub const replica = @import("replica.zig"); pub const image = @import("image.zig"); pub const dump = @import("dump.zig"); pub const lsp = @import("lsp/lsp.zig"); @@ -474,6 +476,8 @@ pub const Loc = struct { }; test { + _ = @import("rollback.zig"); + _ = @import("replica.zig"); _ = @import("modal.zig"); _ = @import("tagline.zig"); _ = @import("hunks.zig"); @@ -4412,7 +4416,10 @@ pub const Pardes = struct { // layout: columns own x by weight; panes own y by vweight within a column. ncol: usize = 0, col_weight: [MAX_COLS]u64 = @splat(column_weight_unit), - col_panes: [MAX_COLS][MAX_PANES]usize = undefined, + // Zeroed, not undefined: a digest takes the whole of it, a release + // build's heap leaves its unused slots whatever was there before, and + // two replicas must agree on them (src/replica.zig). + col_panes: [MAX_COLS][MAX_PANES]usize = @splat(@splat(0)), col_n: [MAX_COLS]usize = @splat(0), /// Each column's tag and the workspace's: Texts like a pane's tag, with /// no prefix, showing a default until someone edits them. @@ -4698,7 +4705,7 @@ pub const Pardes = struct { /// a Restore builtin wants this dump loaded into the live session; the /// shell consumes it via takeRestore each frame (restore contents stay host-fed) restore_req: ?[]const u8 = null, - restore_buf: [1024]u8 = undefined, + restore_buf: [1024]u8 = @splat(0), surface: Surface = .{}, /// The view the fields above are of: whose layout, focus, pointer and diff --git a/src/replica.zig b/src/replica.zig new file mode 100644 index 00000000..42d94503 --- /dev/null +++ b/src/replica.zig @@ -0,0 +1,578 @@ +//! A session's replicas (docs/next-daemon.md, phase 5 part A): the authority +//! orders every input and records what its core consumed (src/tape.zig); +//! each replica runs a core of its own, applies its own inputs at once, and +//! takes the authority's stream as the truth. +//! +//! A replica's state is the confirmed position plus its own pending inputs, +//! applied on top (a speculation, recorded as the authority would record +//! it). For each unit of the authority's stream, in order: +//! - its own pending head, recorded the same (inputs, host calls and +//! answers): the head goes, nothing is redone (the fast path); +//! - else the rollback copy is put back (src/rollback.zig), the confirmed +//! units since it are replayed, then this one, and the pending inputs +//! are applied again. +//! A speculation that reaches a host call or a syscall (a Host function, +//! a `tape.site`) or an emulator (the authority's) stops: the copy is put +//! back and the input waits for the authority's answer, one RTT late but +//! never wrong. Clock and environment reads (`tape.value`) are made here, +//! and the comparison catches a guess the authority did not share. +//! +//! No transport: messages are bytes in and out. A client's input is its +//! id, a sequence number and the event as detached/wire.zig frames it; a +//! unit is the input's origin (0 for the authority's own: a pty's output, a +//! tick), its sequence number and the authority's tape of it. +const std = @import("std"); +const builtin = @import("builtin"); +const pardes = @import("pardes.zig"); +const tape = @import("tape.zig"); +const rollback = @import("rollback.zig"); +const walk = @import("walk.zig"); +const wire = @import("detached/wire.zig"); +const Allocator = std.mem.Allocator; +const Pardes = pardes.Pardes; + +const checked = builtin.mode == .debug or builtin.mode == .safe; +const head_len = 6; // origin or client: u16le, seq: u32le +/// Confirmed units fast-pathed under one copy before it is taken afresh: +/// a rollback replays them all. +const rebase_after = 32; + +fn header(buf: []u8, who: u16, seq: u32) void { + std.mem.writeInt(u16, buf[0..2], who, .little); + std.mem.writeInt(u32, buf[2..6], seq, .little); +} + +pub const Unit = struct { origin: u16, seq: u32, tape: []const u8 }; + +pub fn parseUnit(msg: []const u8) ?Unit { + if (msg.len < head_len) return null; + return .{ .origin = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .tape = msg[head_len..] }; +} + +pub const Input = struct { client: u16, seq: u32, event: pardes.Event }; + +/// A client's input message; its event borrows `msg`. +pub fn parseInput(msg: []const u8) ?Input { + if (msg.len < head_len) return null; + const f = (wire.framed(msg[head_len..]) catch return null) orelse return null; + const ev = switch (wire.decodeClient(f.tag, f.payload) catch return null) { + .event => |ev| ev, + else => return null, + }; + return .{ .client = std.mem.readInt(u16, msg[0..2], .little), .seq = std.mem.readInt(u32, msg[2..6], .little), .event = ev }; +} + +/// The core whose tape is `t`, stepped: tape.on is process-wide, and so +/// are syntax.zig's held trees, so one process can step several. +const Stepping = struct { + tape: ?*tape.Tape, + trees: ?*pardes.syntax.HeldTrees, + + fn begin(t: *tape.Tape, epoch: ?*rollback.Epoch) Stepping { + const was: Stepping = .{ .tape = tape.on, .trees = pardes.syntax.held_trees }; + tape.on = t; + rollback.Epoch.select(epoch); + return was; + } + + fn end(was: Stepping) void { + tape.on = was.tape; + pardes.syntax.held_trees = was.trees; + } +}; + +fn nowNs() u64 { + return pardes.FrameStats.nowNs(); +} + +// ---- the authority ---- + +pub const Authority = struct { + gpa: Allocator, + t: tape.Tape, + core: *Pardes, + host: pardes.Host, + out: std.ArrayListUnmanaged(u8) = .empty, + seq: u32 = 0, + /// Each client's view (src/views.zig): its own layout, focus and + /// cursors over the session's text. The first client has the session's. + view_of: [64]u8 = @splat(0), + + /// 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 { + // A replay gives its core every allocator (tape.zig), and a digest + // tells an allocator from none. + var opts = options; + opts.image_allocator = opts.image_allocator orelse gpa; + opts.pdf_allocator = opts.pdf_allocator orelse gpa; + opts.tree_sitter_allocator = opts.tree_sitter_allocator orelse gpa; + opts.frame_allocator = opts.frame_allocator orelse gpa; + const a = try gpa.create(Authority); + errdefer gpa.destroy(a); + a.* = .{ .gpa = gpa, .t = tape.memory(gpa), .core = undefined, .host = host }; + const was = Stepping.begin(&a.t, null); + defer was.end(); + a.core = try Pardes.init(gpa, opts); + a.core.host = host; + a.core.pump(host) catch {}; + return a; + } + + pub fn deinit(a: *Authority) void { + const was = Stepping.begin(&a.t, null); + a.core.deinit(); + was.end(); + tape.release(&a.t); + a.out.deinit(a.gpa); + a.gpa.destroy(a); + } + + /// What was recorded since the last unit, as one (the boot's, a setup's + /// done straight on the core). + pub fn unit(a: *Authority, origin: u16, seq: u32) ![]const u8 { + a.out.clearRetainingCapacity(); + try a.out.appendNTimes(a.gpa, 0, head_len); + header(a.out.items, origin, seq); + try a.out.appendSlice(a.gpa, tape.taken(&a.t)); + tape.clearTaken(&a.t); + return a.out.items; + } + + /// An input of the authority's own (a pty's output, a tick, a setup's + /// command), recorded into the unit being made. + pub fn apply(a: *Authority, ev: pardes.Event) void { + const was = Stepping.begin(&a.t, null); + a.core.update(ev); + a.core.pump(a.host) catch {}; + was.end(); + } + + /// One of the authority's own inputs, as its unit. + pub fn local(a: *Authority, ev: pardes.Event) ![]const u8 { + a.apply(ev); + a.seq += 1; + return 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 } { + const was = Stepping.begin(&a.t, null); + const k = a.core.openView() orelse { + was.end(); + return error.TooManyViews; + }; + a.core.pump(a.host) catch {}; + was.end(); + a.view_of[client] = k; + a.seq += 1; + return .{ .view = k, .unit = try a.unit(0, a.seq) }; + } + + /// One client's input, applied in the order it came, in its view: the + /// unit every replica takes. + pub fn take(a: *Authority, msg: []const u8) ![]const u8 { + const in = parseInput(msg) orelse return error.BadInput; + const was = Stepping.begin(&a.t, null); + a.core.toView(a.view_of[in.client]); + a.core.update(in.event); + a.core.pump(a.host) catch {}; + was.end(); + return a.unit(in.client, in.seq); + } +}; + +// ---- a replica ---- + +pub const Stats = struct { + inputs: u32 = 0, + /// Applied at once and clean. + speculated: u32 = 0, + /// Stopped at a host call, a syscall or an emulator: waits one RTT. + stopped: u32 = 0, + /// Not tried: an event of the view's (a resize, the pointer), phase 4's. + unspeculated: u32 = 0, + /// The authority's unit was the pending head, recorded the same. + fast: u32 = 0, + /// The copy put back: the head recorded otherwise (a guess of the clock + /// the authority did not share), or another's unit first. + mispredicted: u32 = 0, + foreign: u32 = 0, + rebases: u32 = 0, + units: u32 = 0, + /// Nanoseconds: one speculative apply, a copy taken, a rollback (the + /// copy put back, the confirmed units replayed, the pending reapplied). + spec_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_ns: std.ArrayListUnmanaged(u64) = .empty, + rollback_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_bytes: u64 = 0, + copies: u32 = 0, + + pub fn deinit(s: *Stats, gpa: Allocator) void { + s.spec_ns.deinit(gpa); + s.copy_ns.deinit(gpa); + s.rollback_ns.deinit(gpa); + } +}; + +const Pending = struct { seq: u32, msg: []u8, spec: ?[]u8 = null }; + +pub const Replica = struct { + gpa: Allocator, + id: u16, + /// Its own view of the session (Authority.openView's). + view: u8 = 0, + /// The core's allocator; its tapes and the engine's own lists are not. + epoch: rollback.Epoch = .{}, + t: tape.Tape, + copy: rollback.Copy = .{}, + pending: std.ArrayListUnmanaged(Pending) = .empty, + /// pending[0..applied] are applied on top of the confirmed position. + applied: usize = 0, + /// The pending input that waits for the authority (it stopped at a host + /// call, or is the view's), and those after it with it. + blocked: ?u32 = null, + /// Confirmed units fast-pathed since the copy was taken. + since: std.ArrayListUnmanaged([]u8) = .empty, + /// Pending inputs to apply again (after a rollback). + dirty: bool = false, + next_seq: u32 = 1, + stats: Stats = .{}, + diverged: ?[]const u8 = null, + out: std.ArrayListUnmanaged(u8) = .empty, + /// Nanoseconds of the rollback being made, until its reapply. + recovering: ?u64 = null, + + /// A replica of the session whose first unit is `first`. + pub fn init(gpa: Allocator, id: u16, first: []const u8) !*Replica { + const r = try gpa.create(Replica); + r.* = .{ .gpa = gpa, .id = id, .t = tape.memory(gpa) }; + r.t.core_gpa = r.epoch.allocator(); + r.confirm(first); + if (r.t.core == null) { + r.deinit(); + return error.NoCore; + } + return r; + } + + pub fn deinit(r: *Replica) void { + if (r.t.core) |c| { + const was = Stepping.begin(&r.t, &r.epoch); + if (r.copy.held) r.copy.restore(); + c.deinit(); + was.end(); + } + r.copy.deinit(); + for (r.pending.items) |p| r.freePending(p); + r.pending.deinit(r.gpa); + for (r.since.items) |u| r.gpa.free(u); + r.since.deinit(r.gpa); + r.out.deinit(r.gpa); + r.stats.deinit(r.gpa); + tape.release(&r.t); + if (r.diverged) |why| r.gpa.free(why); + r.epoch.deinit(); + r.gpa.destroy(r); + } + + pub fn core(r: *const Replica) *Pardes { + return r.t.core.?; + } + + fn freePending(r: *Replica, p: Pending) void { + r.gpa.free(p.msg); + if (p.spec) |s| r.gpa.free(s); + } + + /// The replica's own input: applied at once when it can be, and the + /// message for the authority returned (valid until the next call). + pub fn input(r: *Replica, ev: pardes.Event) ![]const u8 { + r.stats.inputs += 1; + const seq = r.next_seq; + r.next_seq += 1; + const room = try r.gpa.alloc(u8, head_len + wire.clientBound(.{ .event = ev })); + defer r.gpa.free(room); + const n = (try wire.encodeClient(room[head_len..], .{ .event = ev })).len; + header(room, r.id, seq); + const msg = try r.gpa.dupe(u8, room[0 .. head_len + n]); + try r.pending.append(r.gpa, .{ .seq = seq, .msg = msg }); + r.dirty = true; + r.settle(); + r.out.clearRetainingCapacity(); + try r.out.appendSlice(r.gpa, msg); + return r.out.items; + } + + /// One unit of the authority's stream, in its order. + pub fn confirm(r: *Replica, msg: []const u8) void { + if (r.diverged != null) return; + const u = parseUnit(msg) orelse return r.fail("a unit too short to read"); + r.stats.units += 1; + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + if (u.origin == r.id and r.pending.items.len > 0 and r.pending.items[0].seq == u.seq and r.applied > 0 and + tape.sameRecords(r.pending.items[0].spec.?, u.tape)) + { + r.stats.fast += 1; + r.freePending(r.pending.orderedRemove(0)); + r.applied -= 1; + if (r.applied == 0) { + // Nothing speculative on top any more: the state is the + // confirmed one. + r.copy.release(); + rollback.Epoch.select(null); + r.clearSince(); + return; + } + const kept = r.gpa.dupe(u8, u.tape) catch return r.fail("out of memory"); + r.since.append(r.gpa, kept) catch return r.fail("out of memory"); + if (r.since.items.len >= rebase_after) { + r.stats.rebases += 1; + r.toConfirmed(); + r.dirty = true; + } + return; + } + if (r.applied > 0) { + if (u.origin == r.id) r.stats.mispredicted += 1 else r.stats.foreign += 1; + if (u.origin == r.id and std.c.getenv("PARDES_REPLICA_TRACE") != null) { + var w: std.Io.Writer.Allocating = .init(r.gpa); + defer w.deinit(); + w.writer.print("replica {d}: its input {d} was recorded otherwise; it guessed:\n", .{ r.id, u.seq }) catch {}; + tape.describe(r.pending.items[0].spec.?, &w.writer); + w.writer.print("and the authority recorded:\n", .{}) catch {}; + tape.describe(u.tape, &w.writer); + std.debug.print("{s}", .{w.written()}); + } + r.recovering = nowNs(); + r.toConfirmed(); + } + if (tape.replayUnit(&r.t, u.tape)) |why| { + if (std.c.getenv("PARDES_REPLICA_TRACE") != null) { + var w: std.Io.Writer.Allocating = .init(r.gpa); + defer w.deinit(); + w.writer.print("replica {d}: the unit of {d}/{d} diverged: {s}\n", .{ r.id, u.origin, u.seq, why }) catch {}; + tape.describe(u.tape, &w.writer); + std.debug.print("{s}", .{w.written()}); + } + return r.fail(why); + } + if (u.origin == r.id) { + if (r.pending.items.len == 0 or r.pending.items[0].seq != u.seq) return r.fail("the authority confirmed an input this replica did not send next"); + if (r.blocked == u.seq) r.blocked = null; + r.freePending(r.pending.orderedRemove(0)); + } + r.dirty = true; + } + + fn fail(r: *Replica, why: []const u8) void { + if (r.diverged == null) r.diverged = r.gpa.dupe(u8, why) catch return; + } + + fn clearSince(r: *Replica) void { + for (r.since.items) |u| r.gpa.free(u); + r.since.clearRetainingCapacity(); + } + + /// Back to the confirmed position: the copy put back, the units fast- + /// pathed since replayed. + fn toConfirmed(r: *Replica) void { + if (r.copy.held) { + r.copy.restore(); + rollback.Epoch.select(null); + } + r.applied = 0; + for (r.since.items) |u| if (tape.replayUnit(&r.t, u)) |why| return r.fail(why); + r.clearSince(); + for (r.pending.items) |*p| if (p.spec) |s| { + r.gpa.free(s); + p.spec = null; + }; + } + + /// The pending inputs applied again, as far as they go. + pub fn settle(r: *Replica) void { + if (!r.dirty or r.diverged != null) return; + r.dirty = false; + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + while (r.applied < r.pending.items.len and r.blocked != r.pending.items[r.applied].seq) if (!r.speculate()) break; + if (r.recovering) |t0| { + r.stats.rollback_ns.append(r.gpa, nowNs() - t0) catch {}; + r.recovering = null; + } + } + + /// pending[applied] applied on top: whether it was. + fn speculate(r: *Replica) bool { + const p = &r.pending.items[r.applied]; + const in = parseInput(p.msg) orelse return false; + switch (in.event) { + .key, .paste, .command => {}, + else => { + // The view's (a resize, the pointer): the authority's for + // now, phase 4's views to come. + r.stats.unspeculated += 1; + r.blocked = p.seq; + return false; + }, + } + const c = r.core(); + if (!r.copy.held) { + const t0 = nowNs(); + r.copy.take(&r.epoch, c) catch return false; + rollback.Epoch.select(&r.epoch); + r.stats.copy_ns.append(r.gpa, nowNs() - t0) catch {}; + r.stats.copy_bytes += r.copy.savedBytes(); + r.stats.copies += 1; + } + var terminals: [pardes.MAX_PANES]u64 = undefined; + if (checked) terminalDigests(c, &terminals); + const t0 = nowNs(); + tape.beginSpeculation(&r.t); + c.toView(r.view); + c.update(in.event); + c.pump(c.host) catch {}; + const clean = tape.endSpeculation(&r.t); + const dt = nowNs() - t0; + // Where a blob was written, should one be: the input that did. + if (checked and std.c.getenv("PARDES_REPLICA_TRACE") != null) r.copy.check(); + if (!clean) { + // Undone, and the earlier ones applied again on the confirmed + // position: this one waits for the authority. + r.stats.stopped += 1; + r.blocked = p.seq; + const upto = r.applied; + r.toConfirmed(); + while (r.applied < upto) if (!r.speculate()) break; + if (r.applied == 0 and r.copy.held) { + r.copy.release(); + rollback.Epoch.select(null); + } + return false; + } + if (checked) { + var after: [pardes.MAX_PANES]u64 = undefined; + terminalDigests(c, &after); + if (!std.mem.eql(u64, &terminals, &after)) @panic("replica: a speculation wrote a terminal's emulator"); + } + r.stats.speculated += 1; + r.stats.spec_ns.append(r.gpa, dt) catch {}; + p.spec = r.gpa.dupe(u8, tape.taken(&r.t)) catch return false; + tape.clearTaken(&r.t); + r.applied += 1; + return true; + } + + /// Nothing pending and nothing applied: the replica is the authority's + /// confirmed state, which `digest` says. + pub fn quiet(r: *const Replica) bool { + return r.pending.items.len == 0 and r.applied == 0 and !r.copy.held; + } + + pub fn digest(r: *Replica) u64 { + const was = Stepping.begin(&r.t, &r.epoch); + defer was.end(); + return tape.digestOf(r.core()); + } +}; + +fn terminalDigests(p: *const Pardes, out: *[pardes.MAX_PANES]u64) void { + for (p.panes, out) |slot, *d| { + d.* = 0; + const pane = slot orelse continue; + const state = pane.terminal orelse continue; + var h = walk.Hasher.init(0); + state.digest(&h); + d.* = h.final(); + } +} + +pub fn digestOf(a: *Authority) u64 { + const was = Stepping.begin(&a.t, null); + defer was.end(); + return tape.digestOf(a.core); +} + +const TestHost = struct { + fn watched(_: ?*anyopaque) bool { + return false; + } + const vtable: pardes.Host.VTable = .{ .watched = watched }; + fn host() pardes.Host { + return .{ .vtable = &vtable }; + } +}; + +fn key(r: *Replica, cp: u21, sent: *std.ArrayListUnmanaged([]u8)) !void { + const text = [_]u8{@intCast(cp & 0x7f)}; + const msg = try r.input(.{ .key = .{ .cp = cp, .text = if (cp < 0x80 and cp >= 0x20) &text else "" } }); + try sent.append(std.testing.allocator, try std.testing.allocator.dupe(u8, msg)); +} + +test "a replica's own keys apply at once, confirm on the fast path, and end at the authority's digest" { + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host()); + defer a.deinit(); + const r = try Replica.init(gpa, 1, try a.unit(0, 0)); + defer r.deinit(); + try std.testing.expectEqual(digestOf(a), r.digest()); + var sent: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (sent.items) |m| gpa.free(m); + sent.deinit(gpa); + } + for ("oabc") |k| try key(r, k, &sent); + try key(r, pardes.Key.escape, &sent); + try std.testing.expectEqual(@as(usize, 5), r.applied); + for (sent.items) |m| { + r.confirm(try a.take(m)); + r.settle(); + } + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null); + try std.testing.expectEqual(@as(u32, 5), r.stats.fast); + try std.testing.expect(r.quiet()); + try std.testing.expectEqual(digestOf(a), r.digest()); +} + +test "another client's input first: a replica rolls back, replays it and applies its own again" { + const gpa = std.testing.allocator; + const a = try Authority.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml" }, TestHost.host()); + 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); + defer r1.deinit(); + const r2 = try Replica.init(gpa, 2, first); + defer r2.deinit(); + var s1: std.ArrayListUnmanaged([]u8) = .empty; + var s2: std.ArrayListUnmanaged([]u8) = .empty; + defer { + for (s1.items) |m| gpa.free(m); + for (s2.items) |m| gpa.free(m); + s1.deinit(gpa); + s2.deinit(gpa); + } + for ("oone") |k| try key(r1, k, &s1); + for ("Otwo") |k| try key(r2, k, &s2); + // The authority hears r2 first, then r1; both hear the units in that + // order. + for ([_]*std.ArrayListUnmanaged([]u8){ &s2, &s1 }) |list| for (list.items) |m| { + const u = try gpa.dupe(u8, try a.take(m)); + defer gpa.free(u); + r1.confirm(u); + r1.settle(); + r2.confirm(u); + r2.settle(); + }; + for ([_]*Replica{ r1, r2 }) |r| { + if (r.diverged) |why| std.debug.print("diverged: {s}\n", .{why}); + try std.testing.expect(r.diverged == null); + try std.testing.expect(r.quiet()); + try std.testing.expectEqual(digestOf(a), r.digest()); + } + try std.testing.expect(r1.stats.foreign >= 1); + try std.testing.expectEqual(@as(u32, 4), r2.stats.fast); +} diff --git a/src/rollback.zig b/src/rollback.zig new file mode 100644 index 00000000..9137b6f6 --- /dev/null +++ b/src/rollback.zig @@ -0,0 +1,496 @@ +//! A replica's rollback copy (docs/next-daemon.md, phase 5): the state a +//! speculation can write, saved before it writes, and put back where it was +//! when the authority's order differs. +//! +//! Two halves: +//! - `Epoch`, the replica core's allocator. It knows every allocation, and +//! while a copy is held it frees nothing that was there before (a free +//! is put off) and grows nothing of then in place. What is allocated +//! meanwhile is the epoch's. So whatever the core held when the copy was +//! taken is still where it was when the copy is put back. +//! - `Copy`, the walker's walk of the core's state (src/walk.zig: what a +//! digest covers, so views, buffers, registers, counters and terminal +//! metadata), saving the bytes of every allocation it reaches, the core +//! struct's own included. A file's text, its line index and its undo +//! snapshots are pinned instead: an edit puts a new buffer in their +//! place (File.setContentSpan) and never writes one, so the copy keeps +//! a reference and the put-off free keeps it alive. +//! +//! Putting the copy back writes each saved allocation's bytes over it, so +//! every pointer in them points where it did, at what was there; then the +//! epoch's allocations are freed and its put-off frees forgotten. Letting +//! the copy go (the speculation was right) makes the put-off frees. +//! +//! ponytail: an allocation reached only through a field the walk leaves +//! out (a derived cache's own heap, say) is not saved; that cache is the +//! epoch's as it was written, which is right for one remade from the text +//! it was made of and wrong for one changed in place. The replica harness +//! (test/replicas.zig) checks a digest at every confirmed step. +const std = @import("std"); +const builtin = @import("builtin"); +const pardes = @import("pardes.zig"); +const walk = @import("walk.zig"); +const Allocator = std.mem.Allocator; +const Alignment = std.mem.Alignment; +const Pardes = pardes.Pardes; + +/// Blobs this long or longer (`pinned`) are pinned, not copied. Checked +/// unchanged in a safe build when the copy goes. +const blob_min = 4096; +const checked = builtin.mode == .debug or builtin.mode == .safe; + +pub const Epoch = struct { + child: Allocator = std.heap.c_allocator, + /// Its own bookkeeping, never the epoch's. + meta: Allocator = std.heap.c_allocator, + live: std.AutoHashMapUnmanaged(usize, Entry) = .empty, + on: bool = false, + id: u32 = 0, + born: std.ArrayListUnmanaged(usize) = .empty, + deferred: std.ArrayListUnmanaged(usize) = .empty, + trees: pardes.syntax.HeldTrees = .{ .meta = std.heap.c_allocator }, + + const Entry = struct { len: usize, alignment: Alignment, epoch: u32, freed: bool = false }; + + pub fn allocator(e: *Epoch) Allocator { + return .{ .ptr = e, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } }; + } + + pub fn deinit(e: *Epoch) void { + var it = e.live.iterator(); + while (it.next()) |kv| e.child.rawFree(@as([*]u8, @ptrFromInt(kv.key_ptr.*))[0..kv.value_ptr.len], kv.value_ptr.alignment, @returnAddress()); + e.live.deinit(e.meta); + e.born.deinit(e.meta); + e.deferred.deinit(e.meta); + e.trees.born.deinit(e.meta); + e.trees.freed.deinit(e.meta); + } + + fn mine(e: *const Epoch, entry: Entry) bool { + return e.on and entry.epoch == e.id; + } + + /// The live allocation that starts at `addr`. + pub fn owns(e: *const Epoch, addr: usize) ?Entry { + const entry = e.live.get(addr) orelse return null; + return if (entry.freed) null else entry; + } + + fn note(e: *Epoch, addr: usize, len: usize, alignment: Alignment) bool { + e.live.put(e.meta, addr, .{ .len = len, .alignment = alignment, .epoch = if (e.on) e.id else 0 }) catch return false; + if (e.on) e.born.append(e.meta, addr) catch {}; + return true; + } + + /// Every new allocation filled with this: a core reading memory it never + /// wrote shows as a replica's divergence (test/replicas.zig, a release + /// build's heap is otherwise whatever it was). + pub var fill: ?u8 = null; + + fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const ptr = e.child.rawAlloc(len, alignment, ra) orelse return null; + if (fill) |b| @memset(ptr[0..len], b); + if (!e.note(@intFromPtr(ptr), len, alignment)) { + e.child.rawFree(ptr[0..len], alignment, ra); + return null; + } + return ptr; + } + + fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const entry = e.live.getPtr(@intFromPtr(memory.ptr)) orelse return false; + // What the copy saved stays its size: the core moves instead. + if (e.on and !e.mine(entry.*)) return false; + if (!e.child.rawResize(memory, alignment, new_len, ra)) return false; + entry.len = new_len; + return true; + } + + fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const old = @intFromPtr(memory.ptr); + const entry = e.live.get(old) orelse return null; + if (e.on and !e.mine(entry)) return null; + const ptr = e.child.rawRemap(memory, alignment, new_len, ra) orelse return null; + _ = e.live.remove(old); + e.live.put(e.meta, @intFromPtr(ptr), .{ .len = new_len, .alignment = alignment, .epoch = entry.epoch }) catch {}; + if (e.mine(entry) and @intFromPtr(ptr) != old) e.born.append(e.meta, @intFromPtr(ptr)) catch {}; + return ptr; + } + + fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void { + const e: *Epoch = @ptrCast(@alignCast(ctx)); + const addr = @intFromPtr(memory.ptr); + const entry = e.live.getPtr(addr) orelse return e.child.rawFree(memory, alignment, ra); + if (e.on and !e.mine(entry.*)) { + // Held by the copy until it is put back or let go. + if (!entry.freed) e.deferred.append(e.meta, addr) catch {}; + entry.freed = true; + return; + } + e.child.rawFree(memory.ptr[0..entry.len], entry.alignment, ra); + _ = e.live.remove(addr); + } + + fn reallyFree(e: *Epoch, addr: usize) void { + const entry = e.live.get(addr) orelse return; + e.child.rawFree(@as([*]u8, @ptrFromInt(addr))[0..entry.len], entry.alignment, @returnAddress()); + _ = e.live.remove(addr); + } + + fn begin(e: *Epoch) void { + std.debug.assert(!e.on); + e.id +%= 1; + if (e.id == 0) e.id = 1; + e.on = true; + e.born.clearRetainingCapacity(); + e.deferred.clearRetainingCapacity(); + e.trees.born.clearRetainingCapacity(); + e.trees.freed.clearRetainingCapacity(); + pardes.syntax.held_trees = &e.trees; + } + + /// The copy put back: what the epoch made goes, what it freed stays. + fn discard(e: *Epoch) void { + for (e.born.items) |addr| if (e.live.get(addr)) |entry| if (e.mine(entry)) e.reallyFree(addr); + for (e.deferred.items) |addr| if (e.live.getPtr(addr)) |entry| { + entry.freed = false; + }; + for (e.trees.born.items) |t| pardes.syntax.destroyTree(t); + e.end(); + } + + /// The copy let go: what the epoch freed goes now. + fn keep(e: *Epoch) void { + for (e.deferred.items) |addr| e.reallyFree(addr); + for (e.trees.freed.items) |t| pardes.syntax.destroyTree(t); + e.end(); + } + + fn end(e: *Epoch) void { + e.on = false; + e.born.clearRetainingCapacity(); + e.deferred.clearRetainingCapacity(); + e.trees.born.clearRetainingCapacity(); + e.trees.freed.clearRetainingCapacity(); + if (pardes.syntax.held_trees == &e.trees) pardes.syntax.held_trees = null; + } + + /// The trees of whichever core is stepped next: one in-process harness + /// steps several (syntax.held_trees is process-wide). + pub fn select(e: ?*Epoch) void { + pardes.syntax.held_trees = if (e) |x| (if (x.on) &x.trees else null) else null; + } +}; + +pub const Copy = struct { + meta: Allocator = std.heap.c_allocator, + regions: std.ArrayListUnmanaged(Region) = .empty, + bytes: std.ArrayListUnmanaged(u8) = .empty, + seen: std.AutoHashMapUnmanaged(Seen, void) = .empty, + pins: std.ArrayListUnmanaged(Pin) = .empty, + held: bool = false, + epoch: ?*Epoch = null, + /// The field being walked, for a pin's report, and whether it is one + /// of the blobs: a file's text or an undo snapshot's. + where: []const u8 = "", + pinnable: bool = false, + + const Region = struct { addr: usize, off: usize, len: usize }; + const Pin = struct { addr: usize, len: usize, hash: u64, where: []const u8 }; + const Seen = struct { addr: usize, ty: usize }; + pub const Error = Allocator.Error; + + pub fn deinit(c: *Copy) void { + c.regions.deinit(c.meta); + c.bytes.deinit(c.meta); + c.seen.deinit(c.meta); + c.pins.deinit(c.meta); + } + + pub fn savedBytes(c: *const Copy) usize { + return c.bytes.items.len; + } + + pub fn pinnedBytes(c: *const Copy) usize { + var n: usize = 0; + for (c.pins.items) |pin| n += pin.len; + return n; + } + + /// The copy of `p`, whose allocator is `e`'s, taken: from now on what + /// it held stays where it is until the copy is put back or let go. + pub fn take(c: *Copy, e: *Epoch, p: *const Pardes) Error!void { + std.debug.assert(!c.held); + c.regions.clearRetainingCapacity(); + c.bytes.clearRetainingCapacity(); + c.seen.clearRetainingCapacity(); + c.pins.clearRetainingCapacity(); + c.epoch = e; + // A step drains these before it ends: between steps they hold + // nothing, and a copy is taken between steps. + std.debug.assert(p.effects_len == 0 and p.in_len == 0); + if (c.epoch.?.owns(@intFromPtr(p)) == null) @panic("rollback: the core is not its epoch's"); + try c.object(Pardes, p); + e.begin(); + c.held = true; + } + + /// The core as it was when the copy was taken. + pub fn restore(c: *Copy) void { + std.debug.assert(c.held); + c.check(); + for (c.regions.items) |r| @memcpy(@as([*]u8, @ptrFromInt(r.addr))[0..r.len], c.bytes.items[r.off..][0..r.len]); + c.epoch.?.discard(); + c.held = false; + } + + /// The speculation was right: the copy is not wanted. + pub fn release(c: *Copy) void { + std.debug.assert(c.held); + c.check(); + c.epoch.?.keep(); + c.held = false; + } + + pub fn check(c: *const Copy) void { + if (comptime !checked) return; + for (c.pins.items) |pin| if (std.hash.Wyhash.hash(0, @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]) != pin.hash) { + const now = @as([*]const u8, @ptrFromInt(pin.addr))[0..pin.len]; + const entry = c.epoch.?.live.get(pin.addr); + std.debug.print("rollback: {s}, {d} bytes at {x}, pinned, was written in place: now {any}; entry {any}, epoch {d}\n", .{ pin.where, pin.len, pin.addr, now[0..32], entry, c.epoch.?.id }); + @panic("rollback: a pinned blob was written in place"); + }; + } + + fn save(c: *Copy, addr: usize, len: usize) Error!void { + if (len == 0) return; + const off = c.bytes.items.len; + try c.bytes.appendSlice(c.meta, @as([*]const u8, @ptrFromInt(addr))[0..len]); + try c.regions.append(c.meta, .{ .addr = addr, .off = off, .len = len }); + } + + /// Whether the value at `addr` of type `T` was reached before. + fn reached(c: *Copy, comptime T: type, addr: usize) Error!bool { + const key: Seen = .{ .addr = addr, .ty = @intFromPtr(@typeName(T).ptr) }; + const got = try c.seen.getOrPut(c.meta, key); + return got.found_existing; + } + + /// The allocation at `addr`, saved once, whatever reaches it. + fn allocation(c: *Copy, addr: usize) Error!?usize { + const entry = c.epoch.?.owns(addr) orelse return null; + if (try c.reached(void, addr)) return entry.len; + try c.save(addr, entry.len); + return entry.len; + } + + fn visit(c: *Copy, comptime T: type, v: *const T) Error!void { + if (comptime !heapIn(T, 0)) return; + switch (@typeInfo(T)) { + .optional => |o| if (v.*) |*payload| try c.visit(o.child, payload), + .array => |a| if (comptime heapIn(a.child, 0)) for (v) |*e| try c.visit(a.child, e), + .pointer => |p| switch (p.size) { + .one => try c.object(p.child, v.*), + .slice => try c.slice(p.child, v.*), + // No length to walk by: its keeper's (a C handle's buffer). + else => {}, + }, + .@"struct" => |s| { + if (comptime walk.machinery(T)) return; + // A terminal: the authority's (its emulator is never written + // by a speculation: terminal.zig's guards). + if (comptime @hasDecl(T, "digest") and @TypeOf(T.digest) == fn (*const T, *walk.Hasher) void) return; + if (s.layout == .@"packed") return; + if (comptime @hasField(T, "items") and @hasField(T, "capacity") and s.field_names.len == 2) { + if (v.capacity == 0) return; + _ = try c.allocation(@intFromPtr(v.items.ptr)); + const E = @typeInfo(@FieldType(T, "items")).pointer.child; + if (comptime heapIn(E, 0)) for (v.items) |*e| try c.visit(E, e); + return; + } + if (comptime @hasDecl(T, "KV") and @hasDecl(T, "Hash") and @hasField(T, "metadata")) { + const m = v.metadata orelse return; + // std's header sits before the metadata, at the start + // of the one allocation. + const header = std.mem.alignForward(usize, 2 * @sizeOf(usize) + @sizeOf(u32), @alignOf(usize)); + _ = try c.allocation(@intFromPtr(m) - header); + var it = v.iterator(); + while (it.next()) |entry| { + try c.visit(@TypeOf(entry.key_ptr.*), entry.key_ptr); + try c.visit(@TypeOf(entry.value_ptr.*), entry.value_ptr); + } + return; + } + if (comptime @hasField(T, "raw") and s.field_names.len == 1 and @hasDecl(T, "load")) return; + if (comptime @hasField(T, "any_future")) return; + if (comptime @hasField(T, "bit_length") and @hasField(T, "masks") and s.field_names.len == 2) { + if (v.bit_length == 0) return; + _ = try c.allocation(@intFromPtr(v.masks) - @sizeOf(@typeInfo(@FieldType(T, "masks")).pointer.child)); + return; + } + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + // What a digest covers, the caches made from it and this + // process's own (the views not live are among it): a + // safe build's free writes over what it frees, so what + // the speculation freed would come back as that. Not the + // queues a step drains (undefined between steps), nor the + // authority's. + if (attr.@"comptime" or comptime (annotated(T, "authority", name) or (annotated(T, "local", name) and unsaved(name)))) continue; + if (comptime opaqueTo(F)) continue; + c.where = @typeName(T) ++ "." ++ name; + c.pinnable = comptime pinned(T, name); + if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { + const len = comptime walk.lengthOf(T, name).?; + if (comptime heapIn(@typeInfo(F).array.child, 0)) for (@field(v, name)[0..walk.lengthIn(v, len)]) |*e| try c.visit(@typeInfo(F).array.child, e); + } else try c.visit(F, &@field(v, name)); + } + }, + .@"union" => switch (v.*) { + inline else => |*payload| try c.visit(@TypeOf(payload.*), payload), + }, + .error_union => |e| if (v.*) |*payload| try c.visit(e.payload, payload) else |_| {}, + else => {}, + } + } + + fn object(c: *Copy, comptime P: type, ptr: *const P) Error!void { + if (comptime walk.machinery(P)) return; + const addr = @intFromPtr(ptr); + if (try c.reached(P, addr)) return; + if (comptime @hasDecl(P, "digest") and @TypeOf(P.digest) == fn (*const P, *walk.Hasher) void) return; + if (c.epoch.?.owns(addr) != null) { + _ = try c.reached(void, addr); + try c.fields(P, ptr); + } + try c.visit(P, ptr); + } + + /// A struct's bytes, field by field where it says what its fields are: + /// all of them (this process's own too, which the epoch's frees would + /// leave pointing at nothing), but the queues a step drains and the + /// frame statistics (numbers, megabytes of them), and an array only as + /// far as its length says. + fn fields(c: *Copy, comptime T: type, v: *const T) Error!void { + if (comptime @typeInfo(T) != .@"struct" or !@hasDecl(T, "replica")) return c.save(@intFromPtr(v), @sizeOf(T)); + const s = @typeInfo(T).@"struct"; + inline for (s.field_names, s.field_types, s.field_attrs) |name, F, attr| { + if (attr.@"comptime") continue; + if (comptime annotated(T, "local", name) and unsaved(name)) continue; + const at = @intFromPtr(&@field(v, name)); + if (comptime walk.lengthOf(T, name) != null and @typeInfo(F) == .array) { + try c.save(at, walk.lengthIn(v, comptime walk.lengthOf(T, name).?) * @sizeOf(@typeInfo(F).array.child)); + } else if (comptime annotatedStruct(F)) { + try c.fields(F, &@field(v, name)); + } else if (comptime @typeInfo(F) == .array and annotatedStruct(@typeInfo(F).array.child)) { + for (&@field(v, name)) |*e| try c.fields(@typeInfo(F).array.child, e); + } else try c.save(at, @sizeOf(F)); + } + } + + fn slice(c: *Copy, comptime E: type, s: []const E) Error!void { + if (s.len == 0) return; + const addr = @intFromPtr(s.ptr); + if (try c.reached([]const E, addr)) return; + if (comptime !heapIn(E, 0)) if (c.pinnable and s.len * @sizeOf(E) >= blob_min and c.epoch.?.owns(addr) != null) { + const bytes = std.mem.sliceAsBytes(s); + try c.pins.append(c.meta, .{ .addr = addr, .len = bytes.len, .hash = if (checked) std.hash.Wyhash.hash(0, bytes) else 0, .where = c.where }); + return; + }; + _ = try c.allocation(addr); + if (comptime heapIn(E, 0)) for (s) |*e| try c.visit(E, e); + } +}; + +/// The blobs: what an edit puts in place of its predecessor, never writes +/// (File.setContentSpan), and frees raw (memory.freeUnfilled, freeRaw). +fn pinned(comptime T: type, comptime name: []const u8) bool { + const File = pardes.panes.File; + return (T == File.State and (std.mem.eql(u8, name, "content") or std.mem.eql(u8, name, "line_starts"))) or + (T == File.Snapshot and std.mem.eql(u8, name, "content")); +} + +fn annotatedStruct(comptime T: type) bool { + return @typeInfo(T) == .@"struct" and @hasDecl(T, "replica"); +} + +/// The queues every step drains (empty between steps, asserted when a copy +/// is taken: what is in their slots is nothing), and the frame statistics +/// (numbers, and a static name). +fn unsaved(comptime name: []const u8) bool { + return std.mem.eql(u8, name, "effects") or std.mem.eql(u8, name, "in_q") or std.mem.eql(u8, name, "frames"); +} + +fn annotated(comptime T: type, comptime kind: []const u8, comptime name: []const u8) bool { + @setEvalBranchQuota(100_000); + if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), kind)) return false; + inline for (@field(T.replica, kind)) |n| if (comptime std.mem.eql(u8, n, name)) return true; + return false; +} + +/// A field no walk sees into (a C handle, a function): its own keeper's. +fn opaqueTo(comptime F: type) bool { + return switch (@typeInfo(F)) { + .optional => |o| opaqueTo(o.child), + .pointer => |p| p.size == .many or p.size == .c or switch (@typeInfo(p.child)) { + .@"opaque", .@"fn" => true, + else => false, + }, + else => false, + }; +} + +/// Whether a `T` can hold a pointer to the heap at all (else a walk of it +/// finds nothing to save). Deep types count as yes. +fn heapIn(comptime T: type, comptime depth: u32) bool { + if (depth > 12) return true; + return switch (@typeInfo(T)) { + .void, .null, .undefined, .bool, .int, .float, .@"enum", .error_set, .comptime_int, .comptime_float, .enum_literal, .type => false, + .optional => |o| heapIn(o.child, depth + 1), + .array => |a| a.len > 0 and heapIn(a.child, depth + 1), + .pointer => true, + .error_union => |e| heapIn(e.payload, depth + 1), + .@"struct" => |s| blk: { + if (s.layout == .@"packed") break :blk false; + for (s.field_types, s.field_attrs) |F, attr| if (!attr.@"comptime" and heapIn(F, depth + 1)) break :blk true; + break :blk false; + }, + .@"union" => |u| blk: { + for (u.field_types) |F| if (heapIn(F, depth + 1)) break :blk true; + break :blk false; + }, + else => true, + }; +} + +test "a copy put back is the core as it was; one let go keeps what was done" { + var e: Epoch = .{ .child = std.testing.allocator }; + defer e.deinit(); + const gpa = e.allocator(); + const p = try Pardes.init(gpa, .{ .cols = 80, .rows = 24, .file = "mise.toml", .image_allocator = gpa, .pdf_allocator = gpa, .tree_sitter_allocator = gpa, .frame_allocator = gpa }); + p.pump(.{}) catch {}; + const before = walk.digest(Pardes, p); + var c: Copy = .{}; + defer c.deinit(); + const typed = "ox y z"; + try c.take(&e, p); + for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } }); + p.update(.{ .key = .{ .cp = pardes.Key.escape } }); + p.pump(.{}) catch {}; + const edited = walk.digest(Pardes, p); + try std.testing.expect(edited != before); + c.restore(); + try std.testing.expectEqual(before, walk.digest(Pardes, p)); + // The same again, let go this time: what was typed stays. + try c.take(&e, p); + for (typed) |k| p.update(.{ .key = .{ .cp = k, .text = &.{k} } }); + p.update(.{ .key = .{ .cp = pardes.Key.escape } }); + p.pump(.{}) catch {}; + try std.testing.expectEqual(edited, walk.digest(Pardes, p)); + c.release(); + try std.testing.expectEqual(edited, walk.digest(Pardes, p)); + p.deinit(); + try std.testing.expectEqual(@as(usize, 0), e.live.count()); +} diff --git a/src/syntax.zig b/src/syntax.zig index 985a9888..858ef6a2 100644 --- a/src/syntax.zig +++ b/src/syntax.zig @@ -381,10 +381,34 @@ pub fn parseTree(path: []const u8, content: []const u8) ?*anyopaque { if (!enabled) return null; const selected = (forExt(std.fs.path.extension(path)) catch return null) orelse return null; const tree = selected.parser.parseString(content, null) orelse return null; + if (held_trees) |h| h.born.append(h.meta, @ptrCast(tree)) catch {}; return @ptrCast(tree); } +/// While a replica's rollback copy is held (src/rollback.zig) a tree parsed +/// is the speculation's, and one freed is put off: trees live on the C +/// heap, which the core's allocator cannot see. Null otherwise. +pub var held_trees: ?*HeldTrees = null; +pub const HeldTrees = struct { + meta: std.mem.Allocator, + born: std.ArrayListUnmanaged(*anyopaque) = .empty, + freed: std.ArrayListUnmanaged(*anyopaque) = .empty, +}; + pub fn freeTree(tree: *anyopaque) void { + if (!enabled) return; + if (held_trees) |h| { + for (h.born.items, 0..) |t, i| if (t == tree) { + _ = h.born.swapRemove(i); + return destroyTree(tree); + }; + h.freed.append(h.meta, tree) catch destroyTree(tree); + return; + } + destroyTree(tree); +} + +pub fn destroyTree(tree: *anyopaque) void { if (!enabled) return; const t: *ts.Tree = @ptrCast(@alignCast(tree)); t.destroy(); diff --git a/src/tape.zig b/src/tape.zig index ec38deac..70609858 100644 --- a/src/tape.zig +++ b/src/tape.zig @@ -127,19 +127,40 @@ pub const Tape = struct { /// PARDES_RECORD_EVERY: a digest after every input, a nested one's too /// (to find the step a divergence starts at), not only the host's last. every: bool = false, + /// A replica applying its own input before the authority has ordered it + /// (src/replica.zig): recorded as the authority would record it, so the + /// two can be compared, but nothing is performed. A host call or a + /// syscall stops it (`poisoned`): what the call returns is the + /// authority's to say, and the input waits for it. A read of the clock + /// or the environment (`value`) is made here, a guess the comparison + /// checks. + speculating: bool = false, + poisoned: bool = false, + /// The allocator of the core a replay makes (a replica's rollback epoch, + /// src/rollback.zig), when it is not the tape's own. + core_gpa: ?std.mem.Allocator = null, + /// Where a replay keeps what a core keeps of an input (its options), + /// for a tape that is let go; else the tape's allocator, for good. + kept_arena: ?std.heap.ArenaAllocator = null, + /// No digests recorded (a speculation's: a replica compares what it + /// was given and what it asked, from a state the authority shares). + no_digest: bool = false, fn record(t: *Tape, kind: Kind, comptime T: type, v: *const T) void { t.scratch.clearRetainingCapacity(); walk.encode(T, v, &t.scratch.writer) catch @panic("tape: out of memory"); const payload = t.scratch.written(); const len: u32 = @intCast(payload.len); - t.buf.append(t.gpa, @intFromEnum(kind)) catch @panic("tape: out of memory"); + t.buf.append(t.gpa, @backingInt(kind)) catch @panic("tape: out of memory"); t.buf.appendSlice(t.gpa, std.mem.asBytes(&len)) catch @panic("tape: out of memory"); t.buf.appendSlice(t.gpa, payload) catch @panic("tape: out of memory"); if (t.buf.items.len > 1 << 20) t.flush(); } fn flush(t: *Tape) void { + // A tape in memory (a replica's, an authority's stream) is taken + // by whoever holds it. + if (t.fd < 0) return; var at: usize = 0; while (at < t.buf.items.len) { const n = libc.write(t.fd, t.buf.items[at..].ptr, t.buf.items.len - at); @@ -222,7 +243,7 @@ pub const Tape = struct { t.wrap(core); }; t.record(.done, void, &{}); - if (t.depth == 0 or t.every) if (t.core) |core| { + if ((t.depth == 0 or t.every) and !t.no_digest) if (t.core) |core| { var parts: Parts = undefined; const d = digestParts(core, &parts); t.record(.digest, []const u64, &d); @@ -239,12 +260,12 @@ pub const Tape = struct { const head = t.in.take(5) catch return null; const len = std.mem.bytesToValue(u32, head[1..5]); const payload = t.in.take(len) catch return null; - return .{ .kind = @enumFromInt(head[0]), .payload = .{ .bytes = payload } }; + return .{ .kind = @fromBackingInt(@intCast(head[0])), .payload = .{ .bytes = payload } }; } fn peek(t: *const Tape) ?Kind { if (t.in.bytes.len - t.in.at < 5) return null; - return @enumFromInt(t.in.bytes[t.in.at]); + return @fromBackingInt(@intCast(t.in.bytes[t.in.at])); } fn diverge(t: *Tape, comptime why: []const u8, args: anytype) void { @@ -374,7 +395,8 @@ pub const Tape = struct { const tag = std.mem.bytesToValue(Tag, (r.take(@sizeOf(Tag)) catch return t.diverge("a short input", .{}))); r.at -= @sizeOf(Tag); const kept = tag == .init or tag == .init_from_dump or tag == .restore; - const input = walk.decode(Input, r, if (kept) t.gpa else t.arena.allocator()) catch return t.diverge("a short input", .{}); + const keep = if (t.kept_arena) |*k| k.allocator() else t.gpa; + const input = walk.decode(Input, r, if (kept) keep else t.arena.allocator()) catch return t.diverge("a short input", .{}); const outer = t.applying; t.applying = switch (input) { .update => |ev| @tagName(ev), @@ -390,13 +412,14 @@ pub const Tape = struct { .init_from_dump => |d| d.opts, else => unreachable, }; - opts.image_allocator = t.gpa; - opts.pdf_allocator = t.gpa; - opts.tree_sitter_allocator = t.gpa; - opts.frame_allocator = t.gpa; + const gpa = t.core_gpa orelse t.gpa; + opts.image_allocator = gpa; + opts.pdf_allocator = gpa; + opts.tree_sitter_allocator = gpa; + opts.frame_allocator = gpa; t.core = switch (input) { - .init => Pardes.init(t.gpa, opts), - .init_from_dump => |d| pardes.dump.initFromDump(t.gpa, opts, d.bytes), + .init => Pardes.init(gpa, opts), + .init_from_dump => |d| pardes.dump.initFromDump(gpa, opts, d.bytes), else => unreachable, } catch |err| return t.diverge("init failed: {t}", .{err}); t.core.?.host = t.hostOf(t.mask); @@ -608,8 +631,21 @@ fn hostCall(comptime i: usize, comptime R: type, ctx: ?*anyopaque, args: anytype } return walk.decode(R, &ret, t.arena.allocator()) catch std.mem.zeroes(R); } - const real = @field(t.real.vtable.*, name).?; const id: u16 = i; + if (t.speculating) { + // Nobody watches a replica's step: its frames are its own, drawn + // outside it (and the authority's host says so too, or the + // comparison fails). + if (comptime std.mem.eql(u8, name, "watched")) { + const r = false; + t.record(.host, u16, &id); + t.record(.ret, R, &r); + return r; + } + t.poisoned = true; + return poisonOf(R); + } + const real = @field(t.real.vtable.*, name).?; t.record(.host, u16, &id); t.seeFields(); const outer = !t.host_side; @@ -639,7 +675,7 @@ pub fn value(comptime s: Site, comptime f: anytype, args: anytype) @typeInfo(@Ty fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anytype, comptime yields: bool) @typeInfo(@TypeOf(f)).@"fn".return_type.? { const R = @typeInfo(@TypeOf(f)).@"fn".return_type.?; const t = on orelse return if (yields) out(f, args) else @call(.auto, f, args); - const id: u16 = @as(u16, host_fns.len) + @intFromEnum(s); + const id: u16 = @as(u16, host_fns.len) + @backingInt(s); if (t.replay) { if (!t.expectHost(id, @tagName(s))) { std.debug.print("replay: {s}\n", .{t.diverged orelse "?"}); @@ -651,6 +687,12 @@ fn call(comptime s: Site, a: ?std.mem.Allocator, comptime f: anytype, args: anyt // The host's own (a shell's spawn asking the shell), or one inside a // site's syscall: the outer call is the record. if (t.host_side) return if (yields) out(f, args) else @call(.auto, f, args); + // A syscall a speculating replica must not make: its input waits for + // the authority's answer. + if (yields and t.speculating) { + t.poisoned = true; + return poisonOf(R); + } t.record(.host, u16, &id); t.seeFields(); t.host_side = true; @@ -679,7 +721,173 @@ fn out(comptime f: anytype, args: anytype) @typeInfo(@TypeOf(f)).@"fn".return_ty /// Asked by `turn.yield`: a syscall a replica must never make. pub fn replaying() bool { - return if (on) |t| t.replay else false; + return if (on) |t| t.replay or t.speculating else false; +} + +/// A replica speculating (src/replica.zig): state only the authority +/// changes (a terminal's emulator) is left alone, and the input waits. +pub fn speculating() bool { + return if (on) |t| 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 { + if (on) |t| if (t.speculating) { + t.poisoned = true; + }; +} + +/// A harmless stand-in for what a host call or a syscall would have +/// returned to a speculation that is thrown away once it returns: an +/// error where one can be said, else zeroes. +fn poisonOf(comptime R: type) R { + return switch (@typeInfo(R)) { + .error_union => |e| if (@typeInfo(e.error_set).error_set.error_names) |errors| + (if (errors.len > 0) @field(e.error_set, errors[0]) else std.mem.zeroes(R)) + else + error.Unexpected, + .optional => null, + .void => {}, + .@"union" => |u| inline for (u.field_names, u.field_types) |name, F| { + if (comptime zeroable(F)) break @unionInit(R, name, std.mem.zeroes(F)); + } else @compileError("tape: no harmless value of " ++ @typeName(R)), + else => std.mem.zeroes(R), + }; +} + +fn zeroable(comptime T: type) bool { + return switch (@typeInfo(T)) { + .int, .float, .bool, .optional, .void => true, + .pointer => |p| p.size == .slice, + .array => |a| zeroable(a.child), + .@"struct" => |s| blk: { + for (s.field_types) |F| if (!zeroable(F)) break :blk false; + break :blk true; + }, + else => false, + }; +} + +// ---- a replica's tapes in memory (src/replica.zig) ---- + +/// A tape recorded in memory: an authority's stream, taken unit by unit. +pub fn memory(gpa: std.mem.Allocator) Tape { + return .{ .gpa = gpa, .replay = false, .scratch = .init(gpa), .arena = .init(gpa), .kept_arena = .init(gpa) }; +} + +/// What a tape in memory holds, given back (its core is gone already). +pub fn release(t: *Tape) void { + t.buf.deinit(t.gpa); + t.scratch.deinit(); + t.arena.deinit(); + if (t.kept_arena) |*k| k.deinit(); +} + +/// What was recorded since the last take; the tape's to reuse after. +pub fn taken(t: *Tape) []const u8 { + return t.buf.items; +} + +pub fn clearTaken(t: *Tape) void { + t.buf.clearRetainingCapacity(); +} + +/// The records of `bytes`, top-level inputs and all, applied to the +/// tape's core as the authority applied them, each digest checked; why +/// they diverged, or null. +pub fn replayUnit(t: *Tape, bytes: []const u8) ?[]const u8 { + t.replay = true; + t.speculating = false; + defer t.replay = false; + t.in = .{ .bytes = bytes }; + while (t.diverged == null) { + const kind = t.peek() orelse break; + var rec = t.next().?; + switch (kind) { + .input => { + t.apply(&rec.payload); + _ = t.arena.reset(.retain_capacity); + }, + .set => t.applySet(&rec.payload), + .digest => t.check(&rec.payload), + .host, .ret, .done => t.diverge("a {t} record at the top", .{kind}), + } + } + return t.diverged; +} + +/// Starts recording `t`'s core as a speculation: the host's watched +/// fields as they are now, nothing recorded yet. +pub fn beginSpeculation(t: *Tape) void { + t.replay = false; + t.speculating = true; + t.poisoned = false; + t.no_digest = true; + t.buf.clearRetainingCapacity(); + t.seeFields(); +} + +/// Whether it stayed clean (no host call, no syscall, no authority state). +pub fn endSpeculation(t: *Tape) bool { + t.speculating = false; + t.no_digest = false; + return !t.poisoned; +} + +/// Whether two tapes record the same inputs, host calls and answers, +/// their digests aside. +pub fn sameRecords(a: []const u8, b: []const u8) bool { + var x: walk.Reader = .{ .bytes = a }; + var y: walk.Reader = .{ .bytes = b }; + while (true) { + const ra = nextRecord(&x); + const rb = nextRecord(&y); + if (ra == null or rb == null) return ra == null and rb == null; + if (ra.?.kind != rb.?.kind or !std.mem.eql(u8, ra.?.payload, rb.?.payload)) return false; + } +} + +fn nextRecord(r: *walk.Reader) ?struct { kind: Kind, payload: []const u8 } { + while (true) { + const head = r.take(5) catch return null; + const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return null; + const kind: Kind = @fromBackingInt(@intCast(head[0])); + if (kind != .digest) return .{ .kind = kind, .payload = payload }; + } +} + +/// A tape's records, one a line (kind; an input's or a host call's name), +/// for a divergence's report. +pub fn describe(bytes: []const u8, w: *std.Io.Writer) void { + var r: walk.Reader = .{ .bytes = bytes }; + var depth: usize = 0; + while (true) { + const head = r.take(5) catch return; + const payload = r.take(std.mem.bytesToValue(u32, head[1..5])) catch return; + const kind: Kind = @fromBackingInt(@intCast(head[0])); + if (kind == .done or kind == .ret) depth -|= 1; + w.splatByteAll(' ', depth * 2) catch {}; + switch (kind) { + .input => { + const tag = std.mem.bytesToValue(std.meta.Tag(Input), payload[0..@sizeOf(std.meta.Tag(Input))]); + w.print("input {t}", .{tag}) catch {}; + if (tag == .update) w.print(" {t}", .{std.mem.bytesToValue(std.meta.Tag(pardes.Event), payload[@sizeOf(std.meta.Tag(Input))..][0..@sizeOf(std.meta.Tag(pardes.Event))])}) catch {}; + }, + .host => { + const id = std.mem.bytesToValue(u16, payload[0..2]); + w.print("host {s}", .{if (id < host_fns.len) host_fns[id] else @tagName(@as(Site, @fromBackingInt(@intCast(id - host_fns.len))))}) catch {}; + }, + else => w.print("{t} ({d} bytes)", .{ kind, payload.len }) catch {}, + } + w.writeByte('\n') catch {}; + if (kind == .input or kind == .host) depth += 1; + } +} + +/// The digest a replica and its authority must agree on. +pub fn digestOf(p: *const Pardes) u64 { + return walk.digest(Pardes, p); } /// PARDES_RECORD set: the tape is written from the session's first call. diff --git a/src/terminal.zig b/src/terminal.zig index e737a831..81fae5db 100644 --- a/src/terminal.zig +++ b/src/terminal.zig @@ -417,9 +417,18 @@ pub fn panFor(p: *const Pardes, pane: *const Pane, r: pardes.Rect) u16 { return @intCast(@min(pane.rows - shown, (at + 1) -| shown)); } +/// 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 { + if (!pardes.tape.speculating()) return false; + pardes.tape.poison(); + return true; +} + /// Move the emulator's viewport by `delta` shell rows (negative scrolls back). pub fn scrollGrid(pane: *Pane, delta: i32) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; state.vt.screens.active.scroll(.{ .delta_row = delta }); } @@ -434,6 +443,7 @@ pub fn atBottom(pane: *const Pane) bool { /// Snap the viewport back onto live output. pub fn followOutput(pane: *Pane) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; state.vt.screens.active.scroll(.active); } @@ -442,6 +452,7 @@ pub fn followOutput(pane: *Pane) void { /// a scrollback; the next resize retries with the same numbers. pub fn resizeGrid(pane: *Pane, gpa: std.mem.Allocator, cols: u16, rows: u16) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; if (cols != pane.cols) for (0..pane.sel.len) |button| { pane.clearPointerSelection(button); @@ -643,6 +654,7 @@ pub fn screenTextLen(pane: *Pane) usize { /// Release the emulator's heap. The Pane allocation itself is the core's. pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void { if (comptime !enabled) return; + if (authorityOnly()) return; const state = pane.terminal orelse return; if (comptime images_enabled) state.images.deinit(gpa); state.stream.deinit(); @@ -654,6 +666,7 @@ pub fn deinitEmulator(pane: *Pane, gpa: std.mem.Allocator) void { /// Allocate the live emulator half of a terminal pane. Slot ownership, serial /// assignment, and spawn effects remain core lifecycle invariants. pub fn create(gpa: std.mem.Allocator, cols: u16, rows: u16) !*Pane { + if (authorityOnly()) return error.OutOfMemory; const pane = try createDoc(gpa, cols, rows); errdefer gpa.destroy(pane); if (comptime !enabled) return pane; @@ -674,6 +687,9 @@ 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; + // 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; state.mouse_cell = null; state.images = if (images_enabled) .{} else {}; if (comptime images_enabled) TerminalImages.installPngDecoder(); @@ -900,6 +916,7 @@ pub fn feedOutput(p: *Pardes, pane: *Pane, bytes: []const u8) void { // There are no pty reads at all without an emulator to parse them into. if (comptime !enabled) return; if (pane.terminal == null) return; + if (authorityOnly()) 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/src/walk.zig b/src/walk.zig index dc1664cb..3e482e9a 100644 --- a/src/walk.zig +++ b/src/walk.zig @@ -42,7 +42,7 @@ pub fn fieldDigests(comptime T: type, v: *const T, out: []u64) []u64 { if (attr.@"comptime" or comptime excluded(T, name)) continue; var h = Hasher.init(0); if (comptime lengthOf(T, name)) |len| { - hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], &h); + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], &h); } else hash(F, &@field(v, name), &h); out[n] = h.final(); n += 1; @@ -63,7 +63,7 @@ pub fn fieldNames(comptime T: type) []const []const u8 { } /// Types that are machinery, never state: an allocator, the Io, a lock. -fn machinery(comptime T: type) bool { +pub fn machinery(comptime T: type) bool { inline for (.{ std.mem.Allocator, std.Io, std.Io.Mutex, std.Io.Condition, std.Thread, std.heap.ArenaAllocator }) |M| if (T == M) return true; return false; } @@ -92,7 +92,7 @@ fn opaqueTo(comptime F: type) bool { }; } -fn excluded(comptime T: type, comptime name: []const u8) bool { +pub fn excluded(comptime T: type, comptime name: []const u8) bool { @setEvalBranchQuota(100_000); if (!@hasDecl(T, "replica")) return false; inline for (.{ "local", "derived", "authority" }) |kind| { @@ -104,12 +104,22 @@ fn excluded(comptime T: type, comptime name: []const u8) bool { } /// How far the field `len` names says its array is written (null: none). -fn lengthIn(v: anytype, comptime len: []const u8) usize { +/// What a `len`-cut field holds: a fixed array's, or a slice's room (a +/// selection's ranges, made once and used `nsel` deep). +fn Element(comptime F: type) type { + return switch (@typeInfo(F)) { + .array => |a| a.child, + .pointer => |p| p.child, + else => @compileError("walk: a `len` cuts an array or a slice, not " ++ @typeName(F)), + }; +} + +pub fn lengthIn(v: anytype, comptime len: []const u8) usize { const n = @field(v, len); return if (@typeInfo(@TypeOf(n)) == .optional) (if (n) |k| k else 0) else n; } -fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 { +pub fn lengthOf(comptime T: type, comptime name: []const u8) ?[]const u8 { @setEvalBranchQuota(100_000); if (!@hasDecl(T, "replica") or !@hasField(@TypeOf(T.replica), "len")) return null; inline for (T.replica.len) |pair| if (comptime std.mem.eql(u8, pair[0], name)) return pair[1]; @@ -134,7 +144,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { .bool => h.update(&.{@intFromBool(v.*)}), .int => hashInt(T, v.*, h), .float => h.update(std.mem.asBytes(v)), - .@"enum" => |e| hashInt(e.tag_type, @intFromEnum(v.*), h), + .@"enum" => |e| hashInt(e.tag_type, @backingInt(v.*), h), .optional => |o| if (v.*) |*payload| { h.update(&.{1}); hash(o.child, payload, h); @@ -167,7 +177,7 @@ pub fn hash(comptime T: type, v: *const T, h: *Hasher) void { if (attr.@"comptime" or comptime excluded(T, name)) continue; if (comptime opaqueTo(F)) @compileError("walk: " ++ @typeName(T) ++ "." ++ name ++ " is " ++ @typeName(F) ++ ", which no walk sees into: say what it is (`replica`)"); if (comptime lengthOf(T, name)) |len| { - hashSlice(@typeInfo(F).array.child, @field(v, name)[0..lengthIn(v, len)], h); + hashSlice(Element(F), @field(v, name)[0..lengthIn(v, len)], h); } else hash(F, &@field(v, name), h); } }, diff --git a/test/replicas.zig b/test/replicas.zig new file mode 100644 index 00000000..cdb161e8 --- /dev/null +++ b/test/replicas.zig @@ -0,0 +1,327 @@ +//! pardes-replicas: one authority and several replicas of a session in one +//! process (src/replica.zig), each client typing at once over its own +//! delayed, jittered link, as monkey.zig's scripts type at a tty, each in a +//! view of its own (src/views.zig) over the text they share; `--shared` +//! 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] +//! +//! 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. +const std = @import("std"); +const libc = std.c; +const pardes = @import("pardes"); +const replica = pardes.replica; +const Key = pardes.Key; + +const gpa = std.heap.c_allocator; +var trace = false; +const frame_us = 16_667; + +/// The authority's host: no frames drawn (a replica draws its own), and a +/// pty that echoes what it is written, 2 ms later, as a shell's. +const Host = struct { + echo: std.ArrayListUnmanaged(struct { pane: u8, bytes: []u8 }) = .empty, + + fn watched(_: ?*anyopaque) bool { + return false; + } + + fn ptyWrite(ctx: ?*anyopaque, pane: u8, bytes: []const u8) void { + const h: *Host = @ptrCast(@alignCast(ctx.?)); + h.echo.append(gpa, .{ .pane = pane, .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: *Host) pardes.Host { + return .{ .ctx = h, .vtable = &vtable }; + } +}; + +const Kind = enum { input, to_authority, to_replica, echo }; + +const Msg = struct { + at: u64, + n: u64, + kind: Kind, + who: u16, + bytes: []u8, + + fn order(_: void, a: Msg, b: Msg) std.math.Order { + if (a.at != b.at) return std.math.order(a.at, b.at); + return std.math.order(a.n, b.n); + } +}; + +const Link = struct { + last: u64 = 0, + /// When a message sent at `now` arrives: half the RTT, jitter on top, + /// and never before the one sent ahead of it (a stream keeps order). + fn arrive(l: *Link, random: std.Random, now: u64, one_way: u64, jitter: u64) u64 { + const at = @max(l.last + 1, now + one_way + random.uintLessThan(u64, jitter + 1)); + l.last = at; + return at; + } +}; + +const Totals = struct { + inputs: u64 = 0, + speculated: u64 = 0, + stopped: u64 = 0, + unspeculated: u64 = 0, + units: u64 = 0, + fast: u64 = 0, + mispredicted: u64 = 0, + foreign: u64 = 0, + rebases: u64 = 0, + copies: u64 = 0, + copy_bytes: u64 = 0, + divergences: u64 = 0, + unequal: u64 = 0, + spec_ns: std.ArrayListUnmanaged(u64) = .empty, + copy_ns: std.ArrayListUnmanaged(u64) = .empty, + rollback_ns: std.ArrayListUnmanaged(u64) = .empty, + + fn add(t: *Totals, s: *const replica.Stats) !void { + t.inputs += s.inputs; + t.speculated += s.speculated; + t.stopped += s.stopped; + t.unspeculated += s.unspeculated; + t.units += s.units; + t.fast += s.fast; + t.mispredicted += s.mispredicted; + t.foreign += s.foreign; + t.rebases += s.rebases; + t.copies += s.copies; + t.copy_bytes += s.copy_bytes; + 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); + } +}; + +/// One client's next input: monkey.zig's mix, as events. +fn nextEvent(random: std.Random, buf: *[64]u8) pardes.Event { + const typed = "abcdefghijklmnopqrstuvwxyz0123456789 -_=+,:;()"; + const normal = "hjklwbe0$xpuyoOiaAIdcv.nN%sC"; + switch (random.uintLessThan(u8, 40)) { + 0...15 => { + buf[0] = typed[random.uintLessThan(usize, typed.len)]; + return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; + }, + 16...27 => { + buf[0] = normal[random.uintLessThan(usize, normal.len)]; + return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; + }, + 28...31 => return .{ .key = .{ .cp = Key.escape } }, + 32 => return .{ .key = .{ .cp = Key.enter } }, + 33 => return .{ .key = .{ .cp = Key.backspace } }, + 34 => return .{ .key = .{ .cp = switch (random.uintLessThan(u8, 4)) { + 0 => Key.up, + 1 => Key.down, + 2 => Key.left, + else => Key.right, + } } }, + 35 => { + const n = random.intRangeAtMost(usize, 1, 24); + for (buf[0..n]) |*c| c.* = typed[random.uintLessThan(usize, typed.len)]; + return .{ .paste = buf[0..n] }; + }, + 36 => return .{ .command = switch (random.uintLessThan(u8, 4)) { + 0 => "Newcol", + 1 => "Zerox", + 2 => "Undo", + else => "Redo", + } }, + 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) } }, + } +} + +fn writeFile(path: [:0]const u8, lines: usize) !void { + const fd = libc.open(path, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o644)); + if (fd < 0) return error.OpenFailed; + defer _ = libc.close(fd); + var line: [80]u8 = undefined; + for (0..lines) |n| { + const text = try std.fmt.bufPrint(&line, "const value_{d:0>4} = {d}; // a line to edit\n", .{ n, n *% 7919 }); + if (libc.write(fd, text.ptr, text.len) != @as(isize, @intCast(text.len))) return error.WriteFailed; + } +} + +const Run = struct { seed: u64, rtt_ms: u64, steps: usize, clients: u16, shared: bool }; + +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 }); + var prng = std.Random.DefaultPrng.init(r.seed *% 0x9e3779b97f4a7c15 +% r.rtt_ms); + const random = prng.random(); + var host: Host = .{}; + defer { + for (host.echo.items) |e| gpa.free(e.bytes); + host.echo.deinit(gpa); + } + var paths: [3][256:0]u8 = undefined; + for (&paths, 0..) |*p, i| { + const path = try std.fmt.bufPrintSentinel(p, "{s}/f{d}.zig", .{ dir, i }, 0); + try writeFile(path, 60 + 40 * i); + } + // 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()); + defer a.deinit(); + 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); + defer for (reps[0..r.clients]) |rp| rp.deinit(); + 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)}) }); + for (reps[0..r.clients]) |rp| rp.confirm(unit); + } + // Each client a view of its own (src/views.zig), the first the + // session's; or, --shared, every client in the one. + if (!r.shared) for (reps[1..r.clients], 2..) |rp, id| { + const opened = try a.openView(@intCast(id)); + rp.view = opened.view; + for (reps[0..r.clients]) |each| each.confirm(opened.unit); + }; + var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; + defer 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; + } + 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 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) { + .key => |k| k.text, + .paste => |t| t, + .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; + 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; + } + }, + .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; + } + host.echo.clearRetainingCapacity(); + }, + .to_replica => { + const rp = reps[m.who - 1]; + rp.confirm(m.bytes); + rp.settle(); + }, + } + } + const want = replica.digestOf(a); + for (reps[0..r.clients], 1..) |rp, id| { + try totals.add(&rp.stats); + if (rp.diverged) |why| { + totals.divergences += 1; + std.debug.print("seed {d} rtt {d} ms: replica {d} diverged: {s}\n", .{ r.seed, r.rtt_ms, id, why }); + } else if (!rp.quiet() or rp.digest() != want) { + 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" }); + } + } +} + +fn pct(samples: []u64, p: usize) u64 { + if (samples.len == 0) return 0; + std.mem.sort(u64, samples, {}, std.sort.asc(u64)); + return samples[@min(samples.len - 1, samples.len * p / 100)]; +} + +pub fn main(init: std.process.Init) !void { + const args = try init.minimal.args.toSlice(init.arena.allocator()); + var seeds: u64 = 4; + var first: u64 = 0; + var steps: usize = 120; + var clients: u16 = 3; + var rtts: []const u64 = &.{ 30, 80, 207 }; + var shared = false; + 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; + 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")) { + 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); + rtts = rtt_buf[0..k]; + } else return error.UnknownOption; + } + trace = libc.getenv("PARDES_REPLICA_TRACE") != null; + if (libc.getenv("PARDES_REPLICA_FILL")) |b| pardes.rollback.Epoch.fill = std.fmt.parseInt(u8, std.mem.span(b), 0) catch 0xff; + var dir_buf: [256]u8 = undefined; + const tmp = std.mem.span(libc.getenv("TMPDIR") orelse "/tmp"); + 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 {}; + 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(" 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", .{}); + 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); + 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, + t.stopped, t.unspeculated, t.units, + t.fast, rollbacks, t.mispredicted, + t.foreign, @as(f64, @floatFromInt(rollbacks)) * 100 / @as(f64, @floatFromInt(@max(t.inputs, 1))), t.rebases, + pct(t.spec_ns.items, 50) / 1000, pct(t.spec_ns.items, 99) / 1000, pct(t.copy_ns.items, 50) / 1000, + 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; + } + if (failed) std.process.exit(1); +} diff --git a/test/rollback_bench.zig b/test/rollback_bench.zig index 721c6f13..38fe011d 100644 --- a/test/rollback_bench.zig +++ b/test/rollback_bench.zig @@ -1,14 +1,11 @@ -//! What a replica's rollback copy would cost (docs/next-daemon.md, open -//! point 3), and what a fork of the authority stalls it for (open point 5). -//! A typical session and a big one are built in process; for each: -//! - the state the walker visits (src/walk.zig's digest walk, which is -//! what speculation can write: views, buffers, registers, counters, -//! terminal metadata), in bytes; -//! - the part of it that is pinned blobs: a file's text and its undo -//! snapshots, which an edit replaces rather than changes -//! (File.setContentSpan), so a copy keeps a reference; -//! - the walk's time, the blobs' share of it, and a memcpy of the rest: -//! a walker copy costs about the walk plus that write. +//! What a replica's rollback copy costs (docs/next-daemon.md, open point +//! 3, src/rollback.zig), and what a fork of the authority stalls it for +//! (open point 5). A typical session and a big one are built in process, on +//! a rollback epoch's allocator as a replica's core is; for each: +//! - the copy taken and let go: its time, the bytes it saves, the bytes +//! it pins (a file's text, its undo snapshots); +//! - a key that edits a file (`x`) applied on top, as a speculation, and +//! the copy put back: the apply's time and the restore's. //! Then a fork of the big one, child gone at once, and the authority's //! copy-on-write after it. //! @@ -69,8 +66,8 @@ fn writeFile(path: []const u8, lines: usize) !void { } } -fn build(s: Session, dir: []const u8) !*pardes.Pardes { - const core = try pardes.Pardes.init(gpa, .{ .tty_only = true }); +fn build(s: Session, dir: []const u8, a: std.mem.Allocator) !*pardes.Pardes { + const core = try pardes.Pardes.init(a, .{ .tty_only = true, .image_allocator = a, .pdf_allocator = a, .tree_sitter_allocator = a, .frame_allocator = a }); core.update(.{ .resize = .{ .cols = 200, .rows = 60 } }); pump(core); // The shell: pane 0 of a tty boot, its output fed as a pty's. @@ -112,36 +109,6 @@ fn build(s: Session, dir: []const u8) !*pardes.Pardes { return core; } -/// Where a file's text and its undo snapshots are held: what a copy pins. -fn blobs(core: *pardes.Pardes, out: *std.ArrayList(*[]u8)) !usize { - var total: usize = 0; - for (core.panes) |slot| if (slot) |pane| if (pane.file) |*f| { - try out.append(gpa, &f.content); - for (f.history.undo[0..f.history.undo_len]) |*snap| try out.append(gpa, &snap.content); - for (f.history.redo[0..f.history.redo_len]) |*snap| try out.append(gpa, &snap.content); - }; - for (out.items) |b| total += b.len; - return total; -} - -fn walkNs(core: *const pardes.Pardes) u64 { - var t: [reps]u64 = undefined; - var sink: u64 = 0; - for (&t) |*x| { - const t0 = nowNs(); - sink +%= walk.digest(pardes.Pardes, core); - x.* = nowNs() - t0; - } - std.mem.doNotOptimizeAway(sink); - return median(&t); -} - -fn walked(core: *const pardes.Pardes) usize { - var h = walk.Hasher.init(0); - walk.hash(pardes.Pardes, core, &h); - return h.total_len; -} - fn median(samples: []u64) u64 { std.mem.sort(u64, samples, {}, std.sort.asc(u64)); return samples[samples.len / 2]; @@ -161,49 +128,44 @@ pub fn main(init: std.process.Init) !void { const dir = try std.fmt.bufPrint(&dir_buf, "{s}/rollback-bench-{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 {}; - std.debug.print("session panes walked MB blobs MB copy KB walk ms walk ms, blobs out memcpy ms copy ms (est.)\n", .{}); + std.debug.print("session panes copy KB pinned MB take ms release ms edit ms restore ms\n", .{}); var big: ?*pardes.Pardes = null; - for (sessions) |s| { - const core = try build(s, dir); - var list: std.ArrayList(*[]u8) = .empty; - defer list.deinit(gpa); - const blob_bytes = try blobs(core, &list); - const all = walked(core); - const walk_ns = walkNs(core); - // The blobs taken out, as a copy pins them: the walk of what a copy - // writes, then put back. - const kept = try gpa.alloc([]u8, list.items.len); - defer gpa.free(kept); - for (list.items, kept) |b, *k| { - k.* = b.*; - b.* = &.{}; + var epochs: [sessions.len]*pardes.rollback.Epoch = undefined; + for (sessions, &epochs) |s, *e| { + e.* = try gpa.create(pardes.rollback.Epoch); + e.*.* = .{}; + const core = try build(s, dir, e.*.allocator()); + var c: pardes.rollback.Copy = .{}; + defer c.deinit(); + var take: [reps]u64 = undefined; + var release: [reps]u64 = undefined; + for (&take, &release) |*x, *y| { + const t0 = nowNs(); + try c.take(e.*, core); + const t1 = nowNs(); + c.release(); + x.* = t1 - t0; + y.* = nowNs() - t1; } - const copy_bytes = walked(core); - const copy_walk_ns = walkNs(core); - for (list.items, kept) |b, k| b.* = k; - const src = try gpa.alloc(u8, @max(copy_bytes, 1)); - defer gpa.free(src); - const dst = try gpa.alloc(u8, @max(copy_bytes, 1)); - defer gpa.free(dst); - @memset(src, 1); - @memset(dst, 0); - var t: [reps]u64 = undefined; - for (&t) |*x| { + var edit: [reps]u64 = undefined; + var restore: [reps]u64 = undefined; + for (&edit, &restore) |*x, *y| { + try c.take(e.*, core); const t0 = nowNs(); - @memcpy(dst, src); - std.mem.doNotOptimizeAway(dst.ptr); - x.* = nowNs() - t0; + key(core, 'x', "x"); + const t1 = nowNs(); + c.restore(); + x.* = t1 - t0; + y.* = nowNs() - t1; } - const memcpy_ns = median(&t); var panes: usize = 0; for (core.panes) |slot| panes += @intFromBool(slot != null); const ms = 1e-6; - std.debug.print("{s:<8} {d:>5} {d:>9.1} {d:>8.1} {d:>7.1} {d:>7.3} {d:>18.3} {d:>9.3} {d:>14.3}\n", .{ - s.name, panes, - @as(f64, @floatFromInt(all)) / 1e6, @as(f64, @floatFromInt(blob_bytes)) / 1e6, - @as(f64, @floatFromInt(copy_bytes)) / 1e3, @as(f64, @floatFromInt(walk_ns)) * ms, - @as(f64, @floatFromInt(copy_walk_ns)) * ms, @as(f64, @floatFromInt(memcpy_ns)) * ms, - @as(f64, @floatFromInt(copy_walk_ns + memcpy_ns)) * ms, + std.debug.print("{s:<8} {d:>5} {d:>7.1} {d:>9.1} {d:>7.3} {d:>10.3} {d:>7.3} {d:>10.3}\n", .{ + s.name, panes, + @as(f64, @floatFromInt(c.savedBytes())) / 1e3, @as(f64, @floatFromInt(c.pinnedBytes())) / 1e6, + @as(f64, @floatFromInt(median(&take))) * ms, @as(f64, @floatFromInt(median(&release))) * ms, + @as(f64, @floatFromInt(median(&edit))) * ms, @as(f64, @floatFromInt(median(&restore))) * ms, }); if (big) |b| b.deinit(); big = core; -- cgit v1.3 From 70de5ec5ff3dad01afcc45244ad5e5a481486da6 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 29 Oct 2026 17:01:35 -0300 Subject: dump: one walker dump of the whole session, by name across builds, for Restore, -l, Handover and the store; dump.zig's hand-written schema gone A dump is walk.zig's walk of the core with a table of every type it reaches (fields, enum and union names, number widths), read back by name; terminals are ghostty's snapshot (screens, history, kitty images); a failed load frees what it made. Co-Authored-By: Claude Opus 5.5 --- build.zig | 3 + build/snap.zig | 10 +- docs/typ/building.typ | 4 +- docs/typ/reference.typ | 35 +- src/File.zig | 387 --------------- src/Handover.zig | 112 +++-- src/Output.zig | 34 +- src/Pipe.zig | 4 + src/Query.zig | 9 +- src/Store.zig | 57 +-- src/builtins.zig | 2 +- src/dump.zig | 1176 +++++++++++----------------------------------- src/file_watch.zig | 57 +-- src/image.zig | 63 --- src/ninep/ctl.zig | 64 +-- src/ninep/events.zig | 24 +- src/panes.zig | 4 +- src/pardes.zig | 55 +-- src/pdf.zig | 4 +- src/pdf_view.zig | 14 + src/tagline.zig | 8 - src/tape.zig | 40 +- src/terminal.zig | 316 ++++++------- src/walk.zig | 1120 ++++++++++++++++++++++++++++++++++++++++++- test/fs.py | 5 +- test/fs_namespace.zig | 44 +- test/kitty.zig | 6 +- test/monkey.zig | 9 +- test/output.zig | 17 - test/panes.zig | 61 +-- test/pdf.zig | 39 -- test/snapshot.zig | 9 +- test/snapshots/dump.snap | 9 +- 33 files changed, 1851 insertions(+), 1950 deletions(-) (limited to 'build.zig') diff --git a/build.zig b/build.zig index 1a5dd200..962b6322 100644 --- a/build.zig +++ b/build.zig @@ -1950,6 +1950,9 @@ pub fn build(b: *std.Build) void { run_shell_test.has_side_effects = true; unit_step.dependOn(&run_shell_test.step); if (unit_match) |check| check.addArtifactArg(shell_test); + // The native shell's tests alone, without the perf gate's + // ReleaseFast build: what a -Dtest-filter iteration wants. + b.step("shell-test", "run the native shell's unit tests (src/main.zig's)").dependOn(&run_shell_test.step); const run_profile = b.addRunArtifact(unit_profile); run_profile.addArtifactArg(shell_test); run_profile.addPassthruArgs(); diff --git a/build/snap.zig b/build/snap.zig index d74767d3..c1a26e64 100644 --- a/build/snap.zig +++ b/build/snap.zig @@ -69,19 +69,21 @@ pub fn addTty(b: *std.Build, opts: struct { // The replay-divergence gate (src/tape.zig, docs/next-daemon.md): every // snapshot script and `replay-seeds` monkey seeds with each session's // tape recorded, each replayed into two replicas at different - // addresses and one that never draws, every digest checked. + // addresses and one that never draws, every digest checked; and at each + // session's end its dump loaded, which must be that session, digest for + // digest, and dump again to the same bytes (phase 2). const tapes = ".zig-cache/tapes"; const run_replay = b.addRunArtifact(snap); run_replay.addArtifactArg(opts.exe); run_replay.addPrefixedFileArg("--lspmock=", lspmock.getEmittedBin()); - run_replay.addArg("--tape=" ++ tapes); + run_replay.addArgs(&.{ "--tape=" ++ tapes, "--dump" }); run_replay.setCwd(b.path(".")); run_replay.has_side_effects = true; const seeds = b.option(u32, "replay-seeds", "monkey seeds `zig build replay` records and replays (default 20)") orelse 20; const run_monkey_replay = b.addRunArtifact(monkey); run_monkey_replay.addArtifactArg(snap); run_monkey_replay.addArtifactArg(opts.exe); - run_monkey_replay.addArgs(&.{ b.fmt("{d}", .{seeds}), "70", "--tape=" ++ tapes ++ "/monkey", "--out=" ++ tapes ++ "/monkey" }); + run_monkey_replay.addArgs(&.{ b.fmt("{d}", .{seeds}), "70", "--tape=" ++ tapes ++ "/monkey", "--dump", "--out=" ++ tapes ++ "/monkey" }); run_monkey_replay.setCwd(b.path(".")); run_monkey_replay.has_side_effects = true; // One pardes-snap run at a time (its lock): the scripts, then the seeds. @@ -95,7 +97,7 @@ pub fn addTty(b: *std.Build, opts: struct { run_views_replay.setCwd(b.path(".")); run_views_replay.has_side_effects = true; run_views_replay.step.dependOn(&run_monkey_replay.step); - b.step("replay", "record every snapshot script's and -Dreplay-seeds monkey seeds' tapes (one terminal and three) and require each to replay without diverging").dependOn(&run_views_replay.step); + b.step("replay", "record every snapshot script's and -Dreplay-seeds monkey seeds' tapes (one terminal and three) and require each to replay without diverging, and each session's dump to load to its digest").dependOn(&run_views_replay.step); const monkey_tests = b.addTest(.{ .root_module = monkey.root_module }); b.step("monkey-test", "test the monkey's generator and panic detector").dependOn(&b.addRunArtifact(monkey_tests).step); const run_driver_test = b.addRunArtifact(snap); diff --git a/docs/typ/building.typ b/docs/typ/building.typ index 00088d7b..e42702c6 100644 --- a/docs/typ/building.typ +++ b/docs/typ/building.typ @@ -19,7 +19,7 @@ builds MuPDF and is on by default (`-Dmupdf=false` drops it). 9P over QUIC [`zig build`], [the terminal shell and the SDL window together, *installed into `~/.local/bin`* (`pardes`, `pardes-gui`, and `pardes-v9fs`, the #word("Tty9p") helper)], [`zig build -Dplatform=tty`], [the terminal shell alone], [`zig build -Dplatform=gui`], [the SDL3 window alone], - [`zig build web -Dplatform=web -Dtarget=wasm32-freestanding -Ddump=`], [a freestanding wasm core plus vanilla JavaScript (`docs/web.md`)], + [`zig build web -Dplatform=web -Dtarget=wasm32-freestanding -Ddump=`], [a freestanding wasm core plus vanilla JavaScript (`docs/web.md`)], [`zig build -Dplatform=macos`], [an AppKit and CoreText app over a static `libpardes.a` (`docs/macos.md`)], [`zig build -Dplatform=esp32p4`], [a freestanding riscv32 editor object for the ESP32-P4, with a 384 KiB heap], ) @@ -59,7 +59,7 @@ there; its namespace is in `src/esp32p4_gpio.zig`. [`-Dprebuilt-shaders`], [bool: embed the committed SPIR-V; on for a bare `zig build`, off with `-Dplatform`; `zig build shaders` refreshes it with glslc], [`-Dtracy`], [path to a Tracy checkout; off], [`-Dmacos-identity`], [codesigning identity for `pardes.app`; `-` (ad hoc)], - [`-Ddump`], [a `dump.zon` to embed in the web shell], + [`-Ddump`], [a Dump to embed in the web shell], [`-Dtest-filter`], [run only tests whose name contains it; a filter that matches nothing fails], [`-Dtest-rebuild`], [bool: fresh Zig test compilation], [`-Dhelix-harness`], [reference executable for live differential tests; `HX_HARNESS`, else `hx-harness` on `PATH`], diff --git a/docs/typ/reference.typ b/docs/typ/reference.typ index ce2a45f1..2e395cc6 100644 --- a/docs/typ/reference.typ +++ b/docs/typ/reference.typ @@ -368,22 +368,20 @@ Writes take settings and session builtins (`scope = .session` in #word("Delcol") and a pane's `get` refuse the same way with their own word, except that #word("Delcol") opens no `+Unsaved` pane: it names the panes only in its `unsaved` records and its notice. -- #word("Dump") writes `pardes--