summaryrefslogtreecommitdiff
path: root/docs
diff options
context:
space:
mode:
Diffstat (limited to 'docs')
-rw-r--r--docs/next-daemon.md176
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.