docs/superpowers/specs/2026-09-30-colosseums-design.md

# colosseums: nested arenas with kernel-driven lazy reclaim
 
Date: 2026-09-30
Status: implemented, verified live (boot + real exec/fd exercise)
 
## Motivation
 
`alloc.nsc` today is a single parent `heap_arena` with one named child,
`fs_arena`, carved out of it once at boot. Both are plain bump
allocators - `arena_alloc` hands out the next `size` bytes and never
gives any of it back. This is already a deliberate, documented choice
(`alloc.nsc`'s own header: "nothing ever frees"), and the same
philosophy shows up independently in `kfs`'s own block/inode
allocators (`kfs_next_free_block`/`kfs_next_free_inode`, rescanned on
mount rather than freed) and even in directory chains
(`kfs_rmdir`'s comment: "the same bump-allocator-never-frees
philosophy as every other allocator in this kernel").
 
That's fine for things allocated once and kept forever (the heap
itself, the fs buffer region as a whole). It's a real, growing problem
for `fd.nsc`'s five per-slot file-cache buffers specifically: each one
only ever grows (never shrinks, even across a close+reopen of that
same slot), so a slot that once cached one unusually large file stays
that large forever, wasting `fs_arena` space permanently for every
future use of that slot no matter how small. Enough
`cat`/`cp`/`mv` calls in one boot session already exhausts real,
reclaimable-in-principle memory for good (the exact bug `alloc.nsc`'s
own comment documents finding).
 
Colosseums generalize the existing one-level parent/child arena shape
into arbitrary nesting, plus a real (but still simple, coarse-grained)
reclaim path: mark a sub-arena "done" when its owner is finished with
it, and the next allocation that would otherwise fail against that
same vector sweeps for anything marked done, wipes it, and reuses the
slot - instead of failing, and instead of ever calling a real `free()`
with all the bookkeeping that implies.
 
## Goals
 
- One recursive structure, used at every nesting level - the whole
  heap, a subsystem's own region, an individual per-fd buffer slot -
  no separate "container" vs "leaf" types.
- A real reclaim path for the one concrete, motivating case above (fd
  file-cache buffers), without introducing a real `free()`, a
  moving/compacting allocator, or any background task/scheduler this
  kernel doesn't otherwise have.
- Fully replace `kalloc`/`fs_alloc` and their `_used`/`_total`/
  `heap_arena_limit` accessors - one real way to allocate anywhere in
  the kernel, not two names for the same thing living side by side.
 
## Non-goals
 
- No true `free()` of an arbitrary pointer at an arbitrary offset -
  reclaim always operates on a whole child slot at once.
- No compaction/coalescing/moving of live data. A reclaimed slot is
  reused in place; nothing about a still-live arena's address ever
  changes.
- No growable vectors. A vector's child count is fixed forever at
  creation, matching every other fixed-size structure in this kernel
  (the heap's own size, the inode table, buffer caps raised only by
  hand when something outgrows them).
- No new generic process/fd lifecycle system. Auto-marking hooks into
  the *existing* teardown paths in `exec.nsc`/`fd.nsc` where one
  already exists; it does not invent a new one.
 
## Design
 
### The struct
 
One type, `struct arena`, used for every role - the root of a tree
(called a *colosseum* when used that way, e.g. `heap_colosseum`,
`fs_colosseum` - naming/role convention only, not a distinct type) and
every nested arena beneath it (`arena`, `sub-arena`, however deep):
 
```nsc
struct arena
{
	u64 start;
	u64 current;
	u64 limit;
	u64 issued;       /* 0 never handed out by arena_child, 1 has been */
	u64 done;         /* 0 in use (or not yet issued), 1 marked done -
	                   * available for reuse regardless of `issued` */
	u64 child_size;   /* 0 if this arena has no children (pure leaf) */
	u64 child_count;  /* 0 if no children */
	ptr children;     /* -> child_count structs, 0 if no children */
};
```
 
An arena with `child_count == 0` behaves exactly like today's plain
bump arena. An arena that's been turned into a vector (`child_count >
0`) additionally owns `child_count` further `struct arena`s, each
`child_size` bytes of its own bump-allocatable space - both the child
bookkeeping array and the child data region are carved out of the
*parent* via the same `arena_alloc` everything else uses, so nothing
new is needed to bootstrap a vector's own storage.
 
**`issued`, added mid-implementation, not in the original draft**: a
child slot's own `current == start` alone can't tell "never handed
out" apart from "handed out and genuinely in use" for a child used as
a flat buffer rather than sub-allocated from - which is exactly how
`fd.nsc`'s own file-cache slots work (the caller never calls
`arena_alloc` on what `arena_child` gives it, so `current` never moves
away from `start` the whole time it's legitimately in use). Caught by
tracing `fd.nsc`'s real usage before trusting the simpler-looking
check, which would otherwise have hidden a real bug: handing the same
still-in-use slot to two different open files at once.
 
### Core functions
 
```nsc
void arena_init(ptr a, u64 start, u64 size);
ptr  arena_alloc(ptr a, u64 size);
ptr  arena_vector(ptr parent, u64 child_size, u64 child_count);
ptr  arena_child(ptr vector);
void arena_mark_done(ptr a);
```
 
- `arena_init` - as today (zero `current` to `start`, set `limit`),
  plus zeroing `issued`/`done`/`child_size`/`child_count`/`children`.
- `arena_alloc(a, size)` - unchanged bump-pointer behavior: round up
  to 16 bytes, fail cleanly (return 0) if it would exceed `limit`.
  This is also the one function `arena_vector` uses internally to
  carve out its own child storage - no separate carving path.
- `arena_vector(parent, child_size, child_count)` - carves
  `child_count * sizeof(struct arena)` from `parent` for the child
  bookkeeping array, then `child_count * child_size` for the children's
  own data region, `arena_init`s each child against its own slice of
  that region, and returns a `struct arena` (also carved from
  `parent`) whose own `child_size`/`child_count`/`children` describe
  the new vector. Returns 0 if `parent` doesn't have room for either
  carve - same clean-failure contract as `arena_alloc`.
- `arena_child(vector)` - a single scan for a child that's either
  `issued == 0` (never handed out at all) or `done == 1` (handed out
  once, since marked done) - either counts as available. The first
  one found gets `arena_init`'d back to its own start/limit (a no-op
  for a genuinely fresh slot, a real wipe for a reclaimed one - same
  call either way, no need to tell the two apart), `issued` set to 1,
  and is returned. **This scan is the entire "lazy sweep"** - scoped
  to exactly this one vector's own direct children, nothing global.
  Returns 0 if every slot is currently issued and live (none marked
  done) - a clean, visible failure exactly like today's "heap
  genuinely full" case.
- `arena_mark_done(a)` - sets `a->done = 1`. Callable on any arena,
  leaf or vector. Marking a vector-node done does **not** need to
  recurse into its own children first - the whole slot (and whatever
  tree was under it) is discarded wholesale the moment its *own*
  parent's `arena_child` reclaims it; nothing underneath it is ever
  touched again after that point regardless of its own state.
 
No registry of colosseums, no background sweep task: reclaim only
ever happens synchronously inside `arena_child`'s own scan, scoped to
the one vector being asked for a slot.
 
### Auto-marking
 
`arena_mark_done` stays the one real mechanism; it gets called from
the *existing* teardown point that already runs today, not a new
lifecycle system: `fd.nsc`'s close path, on that fd's own file-cache
arena. `exec_filebuf` needs no mark_done call at all - it isn't a
vector, see below.
 
### Colosseums this introduces
 
- `heap_colosseum` - replaces `heap_arena`. Same 16MiB region at
  0x2000000.
- `fs_colosseum` - replaces `fs_arena`. Same 4MiB carve-out, but now
  holds one real vector (fd-cache) plus one single permanent arena
  (`exec_filebuf`), instead of being one flat bump region:
  - `exec_filebuf`: **not a vector at all** - a single, permanent
    65536-byte arena, carved once at `alloc_init` time and reused
    forever, no `arena_child`/`arena_mark_done` cycle involved. traced
    `exec.nsc`'s real recursion logic first, not assumed: a shebang
    chain re-execs through the *same* global `exec_filebuf`, safely,
    because the outer call has already parsed everything it needs
    (`interp_path`, a stack local) *before* recursing and never
    touches `exec_filebuf`'s own content again once the inner call
    returns - proven correct by the code that already ships today,
    confirmed against `exec_shebang_depth`'s own real 8-level limit
    (line 467) too: a vector would need at least 8 concurrent slots to
    avoid *regressing* that already-tested bound, when the real fix
    for the actual leak (growing a single buffer in place, abandoning
    the old one on every size increase) is simpler and needs none of
    that - fix the size once, up front, so growth essentially never
    happens for any real file. 65536 covers the same "minimum 63488,
    rounded" floor `exec.nsc` already enforces today for every
    realistic coreutils-sized binary (checked against every real
    binary this disk actually ships - the largest, `4c.elf`, is 31391
    bytes).
 
    a file that needs *more* than 65536 bytes (the dynamite bootloader
    blob is the one documented real case) falls through to a direct,
    uncounted `arena_alloc` against `fs_colosseum` itself, exactly
    like today - rare and deliberate enough not to need fixed-vector
    machinery built around it, matching this project's own "extend
    when something actually needs it" precedent (`fs.btft`'s own
    tier-format history says the same thing about raising ceilings).
    this one case keeps today's exact "abandoned forever" behavior,
    undisguised - not every rough edge needs solving in the same
    change.
  - an fd-file-cache vector: **5 slots of 65536 bytes each** -
    `fd.nsc`'s own real, current fd table is exactly 5 hand-declared
    slots (`fd_inuse0..4`/`fd_data0..4`/`fd_cap0..4`, fd 3..7, not an
    array), each independently grown-in-place with the identical
    `fd_buf_need` floor (63488, rounded) `exec_filebuf` uses - so the
    same 65536 decision applies here too, for the same reason. a file
    needing more than that falls through to the same direct,
    uncounted `arena_alloc` escape hatch as `exec_filebuf`'s oversized
    case.
 
    worth being honest about what this migration actually buys: since
    each fd slot already keeps its own `fd_capN`/`fd_dataN` alive
    across a close+reopen of that *same* slot number today, reopening
    the same fd index already doesn't leak - the real win here is
    replacing 5x hand-duplicated near-identical global-variable
    tracking with one real indexed vector, plus finally being able to
    reclaim a slot that grew large once back down to normal size
    (mark it done on close, get a fresh, minimum-size wipe on next
    use) - something today's per-slot globals have no way to do at
    all.
 
## Migration (every real caller today)
 
Found by direct grep, not assumed:
 
| file | call site | becomes |
|---|---|---|
| `alloc.nsc` | `arena_init`/`arena_alloc`/`arena_carve` definitions, `alloc_init`, `kalloc`/`fs_alloc`/`kalloc_used`/`kalloc_total`/`fs_alloc_used`/`fs_alloc_total`/`heap_arena_limit` | rewritten per this design; `kalloc`/`fs_alloc` and all `_used`/`_total` accessors removed entirely, not kept as wrappers |
| `idt.nsc:585` | `kalloc(arg1)` (the `sys_alloc` syscall handler) | `arena_alloc(&heap_colosseum, arg1)` |
| `exec.nsc:409` | `fs_alloc(need)` growing `exec_filebuf`/`exec_filebuf_cap` in place | the common case (`need <= 65536`) uses the single, permanent `exec_filebuf` arena directly, no allocation call at all; the rare oversized case falls through to a direct `arena_alloc(&fs_colosseum, need)`, same as today. `exec_filebuf_cap` is removed entirely - the buffer's size is fixed, not tracked. |
| `fd.nsc:192,210,228,246,264` | `fs_alloc(need)` per fd slot, plus the 5x hand-duplicated `fd_inuseN`/`fd_dataN`/`fd_capN` globals backing them | `arena_child()` against the fd-file-cache vector (index = fd - 3, replacing the duplicated globals with one real indexed lookup); mark done on close |
| `paging.nsc:67` | `heap_arena_limit()` | equivalent accessor over `heap_colosseum.limit` |
| `virtfs.nsc:249,251,253,255` | `kalloc_used`/`kalloc_total`/`fs_alloc_used`/`fs_alloc_total` for `/int/mem` | equivalent accessors computed from `heap_colosseum`/`fs_colosseum`'s own fields |
| `kfs.nsc:55` | `extern ptr fs_alloc(u64 size);` | dead declaration, never actually called anywhere in this file - dropped, not migrated |
 
## Testing/verification approach
 
This is kernel code with no unit-test harness; verification is real
boot + real exercise, matching how every other change to this kernel
has been verified this project:
 
- Boot in qemu, confirm `alloc_init` still produces a working heap
  (nothing regresses for code paths that don't touch vectors at all).
- Exercise `exec` repeatedly (run several different programs back to
  back in one boot session, and a real shebang chain) and confirm the
  single `exec_filebuf` arena is reused correctly every time with no
  new allocation - `fs_colosseum` usage should not grow at all across
  repeated normal execs.
- Exercise fd open/close repeatedly past the fd-cache vector's own
  slot count in one boot session (more opens-then-closes than there
  are slots) and confirm reuse works instead of failing once every
  slot has been touched once.
- Confirm a genuinely-exhausted vector (every slot live, none marked
  done) still fails cleanly (returns 0), not silently corrupting
  something - the same property `alloc.nsc`'s own original comment
  called out ("a clean failure every caller can see, instead of
  silently handing out live memory").
- `/int/mem` (virtfs) continues to report sane, real numbers against
  the new struct's fields.
 
## Open questions for the implementation plan
 
- Whether `heap_colosseum` itself ever needs to become a vector too,
  or stays a plain bump arena with `fs_colosseum` as its one
  child, as it is today - nothing in the one motivating case (fd
  cache) needs the top-level heap itself to be a vector, so the
  default is: no, unless something else needs it.
 
## Implementation finding: a real boot hang, root-caused before shipping
 
Status: resolved. Recorded here because it changed `alloc.nsh`'s own
shape, not just a footnote.
 
The first full build of every file in the Migration table booted into
a genuine, reproducible triple-fault loop (`B` printed once per real
boot repeating forever) the moment `sys_exec("sh")` actually ran the
loaded program - every value involved (the file's real bytes read
into `exec_filebuf`, a real ELF magic number, a plausible `entry`
point, real-looking code at both the load address and `entry`) was
individually correct, which is what made this take real, methodical
bisection rather than a quick read-the-diff fix:
 
1. A from-scratch git worktree checkout of the pre-colosseums commit,
   rebuilt and booted in this exact same environment, confirmed
   cleanly first - ruling out the environment/qemu itself before
   suspecting the migration.
2. Reintroducing the real (not test-only) migrated files one at a
   time - `alloc.nsc` alone, then `+exec.nsc`, each with temporary
   compatibility shims (`kalloc`/`fs_alloc` as thin wrappers) so the
   still-unmigrated callers kept linking - each booted clean on its
   own, narrowing the fault to one of the remaining files.
3. Reverting `fd.nsc` alone (the most-restructured file, the most
   likely suspect) did *not* fix it. Reverting `idt.nsc` alone did -
   despite `idt.nsc`'s own change being the most trivial one-line
   rename in the entire migration (`kalloc(arg1)` ->
   `arena_alloc(&heap_colosseum, arg1)`), and despite `idt.nsc`'s own
   `sys_alloc` handler never even being reached yet (confirmed with a
   raw serial beacon placed directly inside it) at the point of crash.
4. Isolating further: the crash reproduced with the *functional*
   change reverted back to the original `kalloc(arg1)` call, as long
   as `include "alloc.nsh"` itself was still added - the bug was
   triggered by the mere presence of certain declarations pulled in by
   the include, not by anything `idt.nsc`'s own code actually did with
   them.
5. Bisecting `alloc.nsh`'s own contents line by line (struct
   definition alone: fine; struct + every function declaration: fine;
   `+ global struct arena heap_colosseum`: fine) found the exact
   trigger: adding `global struct arena fs_colosseum` - **on its own**,
   with no `heap_colosseum` present at all - reproduced the hang.
   `heap_colosseum` declared the identical way, alone, never did.
 
The generated assembly for the two single-global test cases was
**byte-identical apart from the symbol name** (`heap_colosseum` vs
`fs_colosseum`), which rules out a logic bug in `idt.nsc` itself -
this is a real, narrow toolchain-level quirk around redundant
multi-file `.comm` (common symbol) declarations of this specific
struct, triggered by some property of `fs_colosseum` specifically
(name, or declaration count/position across the object files actually
linked) that didn't reproduce for the other three globals in every
combination tried. It was not fully root-caused to the exact
assembler/linker mechanism - past a certain point that stopped being
the efficient use of time, once a clean, principled fix was in hand.
 
The fix doesn't work around the quirk - it removes the pattern that
exposes it, and is arguably the better design anyway: `alloc.nsh` no
longer blanket-declares all four colosseum globals for every caller
regardless of whether that caller touches them. Each file now declares
only the specific global(s) it actually uses, inline:
 
- `idt.nsc`: `heap_colosseum` only (`sys_alloc`'s own handler).
- `exec.nsc`: `fs_colosseum` + `exec_filebuf`.
- `fd.nsc`: `fs_colosseum` + `fd_cache_vec`.
- `paging.nsc`/`virtfs.nsc`: neither - they only ever call the
  accessor *functions*, which stay in the shared header unchanged.
 
Re-verified after the fix: a full clean rebuild of every file boots
correctly, and the real functional tests above all pass - repeated
different-program execs hold `fs_colosseum` usage at a constant 393600
bytes (65536 `exec_filebuf` + 320 bytes of vector bookkeeping + 327680
bytes of fd-cache data, matching the design exactly), and 6+ sequential
file opens through a 5-slot fd-cache vector in one boot session hold
that same number steady too, confirming real reuse rather than growth.