diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/next-daemon.md | 176 |
1 files changed, 174 insertions, 2 deletions
diff --git a/docs/next-daemon.md b/docs/next-daemon.md index efe5214a..d4f9130e 100644 --- a/docs/next-daemon.md +++ b/docs/next-daemon.md @@ -1136,5 +1136,177 @@ What proved wrong in the design: hashes every dependency, and leaves the OS out on purpose. - Pre-existing on the phase 1 tip, and not this line's: test/fs.py's `mounted-startup` session hangs at startup (its main thread waits on a - futex), the same with the base binary. A ReleaseFast `exit_answers` - run loses its Rclunk race about 1 time in 7 on base, and 1 in 40 here. + futex), the same with the base binary, and still on main after phase 4 + (Phase 5 part A notes). A ReleaseFast `exit_answers` run loses its + Rclunk race about 1 time in 7 on base, and 1 in 40 here. + +## Phase 5 part A notes + +Built 2026-10-29, in one process and with no transport: the rollback copy +(`src/rollback.zig`), the replica engine (`src/replica.zig`), the tape's +speculation mode (`src/tape.zig`), and an in-process harness +(`test/replicas.zig`, `zig build replicas`). `zig build rollback-bench` +now times the real copy. Decisions taken at the forks, with the ponytail +lens: + +- **The copy saves bytes and puts them back where they were.** Its walk + is the digest's (src/walk.zig): views, buffers, registers, counters and + terminal metadata. It saves the bytes of every allocation the walk + reaches, and puts each back over its allocation. That works because the + replica core's allocator (`rollback.Epoch`) changes three things while + a copy is held: + - a free of anything older than the copy is put off; + - growing such an allocation in place is refused, so the core moves it; + - anything allocated meanwhile belongs to the epoch. + + So every pointer in the saved bytes still points at what it pointed at + when the copy was taken. Putting the copy back frees the epoch's + allocations and forgets the put-off frees. Letting the copy go makes + them. Nothing has to know who owns what. +- **Three blobs are pinned instead of copied** (4 KiB and up): a file's + text, its line index and its undo snapshots. An edit puts a new one in + place of the old (File.setContentSpan) and never writes one, so the + copy keeps a reference and the put-off free keeps it alive. A safe + build checks every pin is unchanged when the copy goes. +- **More than the digest's fields are saved.** Within a struct the copy + saves every field: the derived caches, and this process's own state too. + It skips the queues a step drains (asserted empty) and the frame + statistics, and cuts an array at its `len`. Both were measured wrong + first: + - a safe build's `free` writes 0xAA over what it frees, so a cache the + speculation freed came back as that (a line index full of 0xAA, then a + crash); + - this process's own fields (the frame arena, the surface) point at what + the epoch then frees. + + For the same reason, file texts and line indexes are now freed raw + everywhere (`memory.freeRaw`), as setContentSpan already did. +- **A speculation is checked against the authority's tape of the same + input.** The replica applies its own input as the authority will (an + update, then a pump) and records it with its own tape. If the + authority's unit for that input has the same records (inputs, host calls + and their answers, digests aside), the head goes: that is the fast path. + The digests are left out of the comparison because the starting states + are equal by induction. A digest checks every unit a replica replays. +- **Each client has its own view** (src/views.zig). The authority goes + into the client's view before its input (`toView`, which is taped), and + the replica's speculation does the same. So a unit records the switch + only when another view was live, alike on both sides. The views not + live (`parked`, each pane's `pv`) are this process's own fields, and + the copy saves them with the rest. +- **A host call or a syscall stops a speculation, but cannot stop it + midway.** Zig has no unwinding. The call is answered with a harmless + value (an error of its set, null, zeroes, or a union's first zeroable + case), the input runs to its end, and then it is undone: the copy is + put back and the earlier pending inputs applied again. That input, and + those after it, wait for the authority's answer. A read of the clock or + the environment (`tape.value`) is a guess made locally, which the + comparison checks. `watched` is answered false, as the authority's host + says too: a replica draws outside the step. +- **An emulator is the authority's.** Its writers in terminal.zig (feed, + resize, scroll, follow, create, deinit) stop a speculation before they + write. A safe build asserts that a clean speculation left every + terminal's digest as it was. Tree-sitter's trees live on the C heap, + which the epoch cannot see. While a copy is held, `syntax.held_trees` + puts off their frees and frees the epoch's own. +- **The view's events wait** (a resize, the pointer): phase 4. +- **Messages are bytes.** A client's input is a u16 client id, a u32 + 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 setup), + its sequence number, and the authority's tape of it. +- **The harness** is a discrete-event simulation. One authority and three + replicas share one view, each client typing monkey.zig's mix (keys, + typing, pastes, a few commands, resizes and clicks) at 50-200 ms with + pauses. Each link takes half the RTT plus up to 10% of it in jitter, in + order. The session is the tty's own boot (a raw shell over a text pane) + with three files looked at. The authority's pty echoes what it is + written 2 ms later, which makes units of its own. + +Found on the way: phase 1's replay ran Debug, whose 0xAA fill made every +read of unwritten memory alike in two cores. In a release build they read +what the heap had, and replicas diverged at once, from: +- `col_panes`, digested whole and undefined past each column's panes (now + zeroed); +- `restore_buf`, the same (now zeroed); +- `terminal.State.reply_dropped`, never set, since `create` leaves fields + as the heap had them; +- `Text.sels` and `PendingPipe.ranges`, digested past their length (a + `len` now cuts a slice too). + +`PARDES_REPLICA_FILL=0xff` fills a replica's allocations, so that what is +left shows at once. Any replica is a release build, so these mattered. + +Measured on main with views (lyntonns). The ReleaseFast runs were alone +through the perf lock; the correctness sweeps ran beside builds. + +- **Correctness.** Three clients each typed 100 inputs per seed, at RTTs + of 30, 80 and 207 ms. No replica diverged, and every replica ended on + the authority's digest, in all three runs: + - Debug: 12 seeds, a view each; + - ReleaseFast with `PARDES_REPLICA_FILL=0xff`: 20 seeds, a view each; + - ReleaseFast, timed: 20 seeds, a view each and in one shared view. +- **What happened to the inputs, and what it cost** (ReleaseFast, a view + each; times in µs, p50 / p99): + + | RTT | rollbacks per input (mispredicted + another's) | speculative apply | copy (1.3 MB) | rollback | + |---|---|---|---|---| + | 30 ms | 31% (106 + 1745) | 35 / 183 | 75 / 198 | 342 / 818 | + | 80 ms | 76% (257 + 4285) | 54 / 168 | 94 / 447 | 455 / 1318 | + | 207 ms | 129% (423 + 7335) | 50 / 174 | 91 / 373 | 569 / 1561 | + + - Of 6000 inputs a run, 259 to 348 stopped at a host call and waited, + and 434 to 449 were the view's own (resizes and clicks). + - In one shared view, the copy is half the size (0.66 MB), the costs + are half (copy 37 / 152, rollback 184 to 259 at p50), and the + rollbacks are the same: 30%, 70% and 121%. + - The worst rollback, 1.6 ms, is a tenth of a 16.7 ms frame. A + speculative apply is 0.2 ms at worst. +- **The copy alone** (`rollback-bench`, ReleaseFast, single view): + + | session | saved | pinned | take | put back after an edit | + |---|---|---|---|---| + | typical (5 panes) | 980 KB | 36.6 MB | 0.044 ms | 0.036 ms | + | big (14 panes) | 1.49 MB | 286.5 MB | 0.071 ms | 0.051 ms | + + Letting a copy go costs nothing measurable. + +What proved wrong: +- "Views cut the conflicts": they cut what a rollback shows, not how + often one happens. Any unit of another client's, in any view, comes + before this replica's pending inputs in the authority's order, so the + copy goes back and the pending inputs are applied again. Each costs a + third of a millisecond, a tenth of a frame at worst. Telling which + units commute with which pending inputs is the next lever, not a + needed one. +- "A copy of about 100 KB": it is 1 to 1.5 MB. The core struct itself is + most of it (the presentation, the surface, the settings and the column + tags), plus the views' parked state, now that the copy saves all of a + struct and not only what a digest takes. It is still under 0.1 ms. +- "A misprediction is rare": every key that leaves a message stamps it + with the time of day (`HH:MM:SS`). So a key confirmed in another second + than it was applied is recorded differently: 2 to 7% of inputs here. In + the harness both cores share one clock, so this is the floor. Across + machines an offset between the clocks raises it. Part B should guess + the authority's clock (its last confirmed reading, plus the time since + locally), not read its own. +- views.zig left a pane's slot for the live view unwritten, and a slot + holding the live body's selections. A pane closed before that view + parked again freed whatever its slot held. This is fixed in its own + change, before this one. Every replica switches views on every input, + and found it at once. + +Not done, and why: +- No transport: part B. +- The view's events (a resize, a click) still wait for the authority. + With views they could be applied at once. +- A pty write stops a speculation, so a shell's echo is shown late. + Phase 6 predicts the echo. +- The authority's own units (a shell's echo) roll back a replica that has + pending inputs. +- The epoch allocator is single-threaded. A replica core's workers + (images, search) must allocate elsewhere, or hold a lock, in part B. +- A replica keeps a timing sample for every input it applies (the + harness reads them). A long-lived one keeps only counters. +- test/fs.py's `mounted-startup` still hangs on main (lyntonns). The same + hang shows with main's own binary in a workspace of its own, so it is + not this line's. |
