# Deliberation circle — kido-alloc (2026-10-14)

Allocator design choice, run as a circle: positions, challenges, convergence, preserved dissent.
Prior art consulted: kido-mem design (region seed list is the allocator's backing store;
interior-hole reservations fail loud because a single-region bootinfo cannot represent a hole —
"fine carving is the future allocator's job"), kido-sched design (P2 static TCBs, P3 explicit
stack carving "replaced by the allocator, not the interface"; C2 carving duplicates the future
allocator — "temporary and declared"; D2 carve does not know image bounds).

## Positions

- **P1 — First-fit free-list with immediate coalescing, over the kido-mem region list.**
  The honest first-kernel allocator: genuinely general (variable sizes, alignment), genuinely
  correct, genuinely testable on the dev host with synthetic regions. Free-list sorted by
  address; coalesce on free. Fragmentation is real and declared, not hidden.
- **P2 — Explicit region-list parameter, no hidden coupling.** `kido_alloc_init(regions, n, ...)`
  takes the backing store as an argument. Bare metal passes `kido_mem_regions()`; hosted passes
  a static arena; tests pass synthetic regions. The allocator never reaches into kido-mem
  globals, so it is unit-testable in isolation.
- **P3 — Loud exhaustion contract.** `kido_alloc` returns `KIDO_ERR_NO_MEMORY` with `*out = NULL`
  on exhaustion. No silent NULL for callers to ignore; the status code IS the contract, matching
  the codebase convention (scheduler's table-full is already `KIDO_ERR_NO_MEMORY`, loud).
- **P4 — Double-free and invalid-free are defined and loud.** Block header carries a magic;
  free checks it: `FREE_MAGIC` (double free) or anything-else-invalid returns
  `KIDO_ERR_EARLY_ENV`. `free(NULL)` is `KIDO_ERR_EARLY_ENV`, consistent with the codebase's
  NULL-guard convention.
- **P5 — Reservation parameter for image bounds (answers sched D2).** `kido_alloc_init` takes
  `(reserve_base, reserve_size)` and carves it out of the region list before building the free
  list. The scheduler passes 0,0 today with the D2 limitation documented; the mechanism is real
  and tested now, the wiring waits on the linker script exposing image symbols.
- **P6 — Identity-map assumption stated loudly.** The allocator dereferences firmware physical
  addresses as pointers. That is correct only under identity mapping; the MMU module will
  revisit it. Stated in the header, not assumed silently.
- **P7 — Scheduler keeps its interface; carving becomes a client.** `kido_sched_create` keeps
  its signature and semantics; the carve block is replaced by `kido_alloc(STACK_SIZE, 16)`.
  DONE-slot stack reuse is preserved (a DONE stack is provably idle). The 33-check self-test
  is adapted to the new backing, not weakened.

## Challenges

- **C1 against P1:** First-fit fragments; a fixed-block slab for 16 KiB stacks would be
  fragmentation-free for the scheduler's exact need, with O(1) alloc. *Answer:* the allocator
  must serve general clients, not just stacks — the task explicitly asks for a real allocation
  interface replacing carving. Fragmentation is declared; `kido_alloc_stats` exposes
  `largest_free` so callers can observe it. A slab for hot paths is a future optimization,
  not today's correctness story.
- **C2 against P1:** Header-before-payload plus alignment creates internal waste (up to
  align-1 bytes per alloc). *Answer:* bounded and documented; the header stays at the block
  start and only the payload is aligned up, so there is no leading free fragment to manage.
  Simplicity of the invariant beats squeezing those bytes in a first kernel.
- **C3 against P4:** Validating "belongs to the allocator" on free costs a region walk.
  *Answer:* regions are bounded at 8 (`KIDO_MEM_MAX_REGIONS`); the walk is trivial. Correctness
  first.
- **C4 against P2:** Passing regions explicitly means every client must know its backing
  store; a global "the allocator" would be more convenient. *Answer:* convenience is how
  hidden coupling starts. Explicit is testable. The scheduler — the first client — wires it
  in `kido_sched_init`, one place.
- **C5 against P3:** Should exhaustion halt loud instead of returning a status? *Answer:* the
  scheduler must distinguish "table full" from "no memory for a stack", and tests must observe
  the failure path. Status codes are the established codebase contract. A policy layer above
  may choose to halt on `KIDO_ERR_NO_MEMORY`; the allocator does not decide that.

## Convergence

First-fit free-list with address-ordered coalescing (P1), explicit region parameter (P2), loud
status-code exhaustion (P3), magic-checked loud free (P4), reservation carve-out implemented now
(P5), identity-map assumption declared (P6), scheduler rewired as a client with its interface
and test count intact (P7). No virtual memory, no demand paging — loud DEFERRED.

## Preserved dissent

- **D1:** A 16 KiB slab would serve the scheduler's stacks with zero fragmentation and a
  five-line implementation; building the general allocator first is gold-plating for a kernel
  whose only client carves identical stacks. *Overruled:* the Gate-approved roadmap needs a
  general allocation interface (future: strings, tables, message buffers), and the carving
  interface was always declared temporary. The slab remains a legitimate future fast path.
- **D2:** `free(NULL)` as a silent no-op matches C convention and would simplify callers.
  *Overruled:* this codebase treats NULL as a contract violation everywhere (scheduler guards
  prove it); consistency beats C convention here.
