# M11: GC + tail calls, GPU rendering from Lux, and the raw-device unlock

## Context

Yggdrasil M0–M10 + SMP are green. Three linked gaps remain before Lux programs can be *long-running device drivers* (the project's whole thesis, proven once already by the TCP stack):

1. **No GC and no tail calls.** Heaps are fixed bump arenas (quota-death), and every `CALL_EXT` grows the native stack — so a Lux server/render loop can survive neither its own garbage nor its own iterations. These two must land together: proper tail calls create exactly the safe point where a moving GC is trivially sound.
2. **Lux can't touch ports.** The bytecode has `PORT_OPEN`/`PORT_SUBMIT` (the assembler uses them) but the Lux language exposes no builtins — that's why the TCP demo's NIC adapter is native Rust.
3. **No display device**, and no generic way for a Lux program to drive a virtio device's queues directly — which is what "independent virgl-class driver in Lux" requires.

The design principle throughout: **the kernel moves buffers; Lux implements protocols.** Verified: `virtio_drivers::queue::VirtQueue<H, SIZE>` is public (`new<T: Transport>`, `add_notify_wait_pop`) — a raw transport port needs no fork. The virtio-gpu 2D command structs (GET_DISPLAY_INFO 0x100, RESOURCE_CREATE_2D 0x101, SET_SCANOUT, TRANSFER_TO_HOST_2D, RESOURCE_FLUSH, ATTACH_BACKING) are plain little-endian structs a Lux program encodes with `list_to_binary` — the kernel never learns the GPU protocol.

---

## Part A — Tail calls + segmented heaps + trampoline GC

### Tail calls: `TAIL_CALL_EXT` via engine trampoline

Key insight: Lux compiles one function per content-addressed module, so **every Lux-level call is already `CALL_EXT`** — a tail variant of `CALL_EXT` alone gives Lux full tail-call coverage (no local/`return_call` work needed).

- New opcode `TAIL_CALL_EXT = 47` (same operands as `CALL_EXT`, no destination reg; terminal like `RET`).
- **Trampoline in `modload::invoke`**: `run_function`/JIT return a reserved sentinel (tag `0b111`, unused by any term — e.g. `Term(7)`); the target `(module_atom, fname_atom, args)` is stashed per-process. `invoke` becomes a loop: run → sentinel? → pop stash → resolve current version (this *is* the hot-load migration point, unchanged semantics) → run again. Constant native stack.
- Interpreter: `TAIL_CALL_EXT` stashes via a new `SystemApi::tail_call(matom, fatom, args)` and returns the sentinel. JIT: helper `TailCallExt` (spill args like `CallExt`), then `return_(sentinel)` — codegen is a call + ret.
- Stash storage: per-process `tail_target: Option<(u32, u32, Vec<Term>)>` in `Process` (terms point into the process heap — same lifetime rules as registers). Kernel + `ygg-run` host harness (both engines) implement it.
- **Lux backend** (`../lux/src/codegen/yggdrasil.rs`): thread `tail: bool` through `compile_expr` — true for the function body root, `Let` body, `Seq` second, `Case`/`Receive` clause bodies; on a tail-position cross-module call emit `TAIL_CALL_EXT`. (`boolean_from_int` and friends are non-tail by construction.)

### Segmented heap growth (non-moving, works under JIT)

`ygg_term::Heap` stays a single-span bump arena; the kernel wraps it:

- `Process.heap` becomes `ProcHeap { spans: Vec<(phys, pages)>, cur: Heap, max_pages, used_pages }`. Allocation failure → `grow()`: allocate a new span (double, capped by `max_pages`), `cur = Heap::new(new_span)`; old spans stay alive (terms in them remain valid — nothing moves, so JIT-held pointers stay sound).
- Spawn takes `(initial_pages, max_pages)`; default initial 16 pages / max 64 → the existing `heap_quota` test behavior (death at cap) is preserved verbatim. `spawn_with_heap` callers set bigger maxes.
- Wiring: JIT helpers' `HeapFull` paths call `proc::grow_current_heap()` and retry, dying only at cap; interpreter gets `SystemApi::heap_grow() -> bool` and a retry wrapper around its alloc sites (one helper fn, not per-op edits). `cpu().current_heap` now points at `ProcHeap.cur` — updated by `grow()` (only the owning core grows, so the lock-free contract holds).

### Moving GC: Cheney compaction at the trampoline

At a trampoline hop, the process's *entire* live term set is: the stashed tail-call args + nothing else (no interpreter frames, no JIT frames — that's what a tail call means). Mailbox fragments and port buffers are separate allocations. So:

- `ygg-term`: `pub unsafe fn evacuate(roots: &mut [Term], to: &mut Heap) -> Result<(), HeapFull>` — proper Cheney with **forwarding pointers** (header word replaced by forwarded pointer, box-kind 7 = forwarded) so *sharing is preserved* (naive `copy_term` would duplicate diamonds). All boxed kinds incl. maps/binaries. Host tests: sharing preserved (copy a diamond, assert one copy), cycles impossible (terms are immutable/acyclic), immediates untouched.
- Trampoline GC policy: at each hop, if `used > ~half of allocated spans` or `spans > 1`: allocate a fresh span sized to live-estimate (`term_size_words` over args), evacuate args, free all old spans. A tail-recursive Lux loop thus runs forever in bounded memory with per-iteration collection of exactly its garbage — BEAM-hibernate-style compaction without stack maps.
- Also compact at `bytecode_entry` return (process about to die — moot) and optionally at `Recv` inside the trampoline loop later; not needed for this milestone.

### Part A acceptance

- Host: segmented-heap tests, Cheney sharing/forwarding tests, interpreter tail-call test in `ygg-interp` mock, `ygg-run` runs a tail-recursive luxpack 100k iterations.
- Kernel marker `[ok] lux loop: 100k tail-recursive iterations in bounded memory` — a Lux module looping 100 000 times, allocating a list + map per iteration, with `max_pages` small enough that the old fixed-heap design would die within ~200 iterations, and iteration count large enough to prove the native stack isn't growing.
- Entire existing suite green (quota, hot-loading, TCP echo unchanged).

---

## Part B — Lux port builtins + `PORT_SUBMIT2`

- New opcode `PORT_SUBMIT2 = 48`: all-register form `(rport, rop, rarg0, rarg1, rtag)` — exposes `Sqe.arg1` (needed for cmd+aux buffer pairs) and makes the op dynamic. Verifier/interp/JIT (helper `PortSubmit2`, 5 args)/kernel/`ygg-run` stubs.
- Lux builtins in the yggdrasil backend (BEAM backend maps them to `erlang:error` stubs so `cargo test` in lux stays green):
  - `port_open(kind) -> Port` → `PORT_OPEN`
  - `port_submit(port, op, arg0, arg1, tag) -> Int` → `PORT_SUBMIT2`
  - `buf_to_bin(id) -> String`, `bin_to_buf(bin) -> Int` → existing ops (already in bytecode, not yet in Lux).
- Completions already arrive as `{port_reply, Port, Tag, Result}` messages — Lux `receive` handles them today.
- Acceptance: a Lux module opens the **serial** port and writes `LUX-PORT-OK` byte-by-byte (op WRITE, `SKIP_CQE` tag); xtask asserts the string in the transcript. Proves the whole Lux→port path with zero new kernel driver code.

---

## Part C — virtio-gpu raw transport port + a Lux GPU driver that renders

### Kernel: `KIND_GPU = 3`, a *transport*, not a driver

`kernel/src/virtio.rs` gains gpu discovery (`DeviceType::GPU`): negotiate baseline features, build the control `VirtQueue` (queue 0) directly via the public `VirtQueue<KernelHal, 64>` API + `PciTransport` (cursor queue ignored). `kernel/src/ports.rs` gains:

- `OP_CTRL (1)`: `arg0` = command-buffer id, `arg1` = response-capacity hint; kernel does `add_notify_wait_pop(cmd_bytes, resp_bytes)`, creates a response buffer, completion result = response buffer id. The command bytes are **opaque** — virtio-gpu 2D today, virgl `SUBMIT_3D` command streams tomorrow, no kernel change.
- `OP_CTRL_ATTACH (2)`: `arg0` = command-prefix buffer id (the Lux-built `RESOURCE_ATTACH_BACKING` header with `nr_entries=1`), `arg1` = backing buffer id; the kernel appends the one `{phys_addr, length}` mem-entry for the backing buffer (talc-heap buffers are physically contiguous; `mm::virt_to_phys` exists). This is the *only* protocol-shaped assist — it exists because guest physical addresses must never be visible to bytecode. Attached buffers are pinned: marked non-takeable in the buffer table until the port closes.
- Buffer table addition: `buf_write(id, offset, bytes)`? Not needed — the demo rebuilds the pixel binary per frame (`bin_to_buf`), and `OP_CTRL_ATTACH` re-attach or `TRANSFER_TO_HOST_2D` from a fresh buffer covers updates. Keep the surface minimal.

### Lux: the driver + renderer (`../lux/examples/gpu_demo.lux`)

Entirely in Lux: encode `GET_DISPLAY_INFO` → parse the response rect; `RESOURCE_CREATE_2D` (format XRGB8888) → `ATTACH_BACKING` (via `OP_CTRL_ATTACH`) → `SET_SCANOUT` → render a deterministic pattern (three solid color bands + a centered rectangle — trivially assertable pixels) into a pixel binary → `bin_to_buf` → attach/transfer → `RESOURCE_FLUSH`. Use a modest resource (e.g. 320×200×4 = 250 KiB binary; well within a grown heap, and Part A's GC makes iterating it viable). Report `gpu_done` to the parent.

### Harness verification (headless screenshot)

- xtask QEMU args: add `-device virtio-gpu-pci` and a monitor socket (`-monitor unix:build/mon.sock,server,nowait` — same mechanism already used by hand during SMP debugging).
- After the kernel prints `[ok] lux gpu: scene rendered via virtio-gpu`, xtask issues `screendump build/gpu.ppm` over the monitor socket, parses the PPM (raw P6, trivial), and asserts the expected colors at 3–4 probe coordinates.
- Risk hedge: if `screendump` proves unreliable with `-display none` in this QEMU build, fallback assertion = Lux reads back nothing but the kernel verifies the `RESOURCE_FLUSH` response is `OK_NODATA` *and* the display-info round-trip matched — still proves the full queue path; note it and keep the ppm assertion behind a flag. (Test this first, in step C1.)

### The virgl unlock (documentation deliverable, no test)

With Part B+C landed, an independent Lux program can: own the gpu port, allocate/attach backing, and push arbitrary control-queue command streams — which is precisely the surface a virgl driver needs (`CTX_CREATE`, `SUBMIT_3D`, capsets are all `OP_CTRL` commands). Document in README: what's unlocked, and the two known ceilings (QEMU must run with `-device virtio-gpu-gl` + GL display for actual 3D; fence/event-driven completion is currently poll-based via the pump).

---

## Execution order (each step lands with the full suite green)

| step | contents |
|---|---|
| A1 | `ygg-term`: `evacuate` (Cheney + forwarding) + host tests; segmented `ProcHeap` in kernel + grow-retry paths (JIT helpers + interp `heap_grow`); spawn `(initial, max)` |
| A2 | `TAIL_CALL_EXT`: bytecode/verifier/interp/JIT/`ygg-run`; trampoline in `modload::invoke` + stash; trampoline GC; Lux backend tail-position threading; bounded-memory loop marker |
| B1 | `PORT_SUBMIT2` op everywhere + Lux builtins (`port_open`/`port_submit`/`buf_to_bin`/`bin_to_buf`); Lux serial `LUX-PORT-OK` marker |
| C1 | QEMU `-device virtio-gpu-pci` + monitor socket in xtask; spike: confirm headless `screendump` works (throwaway native fill via the transport) |
| C2 | gpu transport port (`OP_CTRL`/`OP_CTRL_ATTACH`, buffer pinning); `gpu_demo.lux`; screendump PPM assertion + `[ok] lux gpu` marker; README/virgl notes |

## Files touched

Yggdrasil: `crates/ygg-term/src/lib.rs` (evacuate, forwarding kind), `crates/ygg-bytecode/src/lib.rs`+`verify.rs` (ops 47–48), `crates/ygg-interp/src/lib.rs` (tail_call + heap_grow in `SystemApi`, retry wrapper, new ops, mock), `crates/ygg-jit/src/lib.rs` (2 helpers, sentinel return, decode arms), `kernel/src/proc.rs` (ProcHeap, grow, stash field), `kernel/src/modload.rs` (trampoline + GC), `kernel/src/jit.rs` (grow-retry, new helpers), `kernel/src/ports.rs` (gpu port, pinning), `kernel/src/virtio.rs` (gpu transport), `kernel/src/selftest.rs`, `tools/ygg-run/src/main.rs` (both engines), `tools/xtask/src/main.rs` (gpu device, monitor, ppm assert, markers).
Lux: `src/codegen/yggdrasil.rs` (tail threading, port/buf builtins), `src/codegen/*` BEAM stubs if needed, `examples/lux_loop.lux`, `examples/port_hello.lux`, `examples/gpu_demo.lux`, `tests` harness `SystemApi` additions.

## Risks

- **Cheney under sharing/forwarding bugs** — pure-crate host tests first (diamond sharing, deep lists, maps); the trampoline root set is tiny and exact, which keeps the blast radius small.
- **Tail-position detection in the Lux backend** — start conservative (body/Let/Seq/Case tails only); a missed tail position degrades to today's behavior (stack growth), never to wrong results.
- **Sentinel discipline** — tag-7 words must never escape as terms: assert in `invoke` and in the verifier-adjacent debug paths.
- **Headless screendump** — spiked in C1 before building on it; explicit fallback assertion defined above.
- **`VirtQueue` API friction** (buffer lifetime/`Transport` ownership when the gpu device isn't wrapped in a driver struct) — if it fights us, hand-roll a minimal split virtqueue (~200 lines; we own the Hal and know the layout) — that also removes the last crate dependency from the "independent driver" story.

## Verification

- `cargo xtask test` (the `-smp 4` two-boot suite + TCP echo + pcap) stays the regression net at every step; new markers: bounded-memory loop, `LUX-PORT-OK`, gpu render.
- Host: `cargo test` across pure crates (new Cheney/segment/tail tests), `ygg-run` (both engines) on the loop and gpu-demo luxpacks (gpu ops stubbed on host).
- Manual once: run with `-display gtk` and eyeball the rendered scene.