danos/docs/threading.md

# Threading: `runtime.Thread`, a std-shaped API over a private thread ABI

A note on danos **threads** — several tasks sharing one address space — provided by a
`runtime.Thread` type that mirrors the shape of Zig's `std.Thread` while keeping every
kernel entry behind the [runtime](../library/runtime). **Built** (M1–M11, see
[threading-plan.md](threading-plan.md)): `spawn`/`join`/`detach`, cross-core parallelism,
a futex, `Mutex`/`Condition`/`Semaphore`/`RwLock`/`WaitGroup`, `getCurrentId`/`currentCore`,
per-thread thread-pointer TLS, thread-safe allocation, and a task reaper that reclaims dead
tasks' kernel stacks. Deferred by design (no consumer yet): the Zig `threadlocal`
*compiler* layer (the per-thread thread pointer is in place, so it's runtime+linker work on top) and
detached-thread user-stack reclaim — see the plan's M9/M10 notes. The analysis is against
**Zig 0.16** (the pinned toolchain); `std.Thread`'s internals move between releases, so
treat upstream shapes as "0.16.x."

## The win condition

A danos service can write

```zig
const t = try runtime.Thread.spawn(.{}, worker, .{ctx});
// ... do other work concurrently ...
t.join();
```

and get real parallelism across cores — with `runtime.Thread.Mutex`,
`runtime.Thread.Condition`, and `runtime.Thread.Semaphore` available for
coordination — **without any code path reaching the kernel except through the
runtime**. The call sites read exactly like `std.Thread`, so the day danos becomes a
real Zig target (see [self-hosting](#the-self-hosting-endgame)) we swap the
implementation underneath, not the API above.

## Locked decisions (do not relitigate)

- **We build `runtime.Thread`, not literal `std.Thread`.** It mirrors std's *API and
  features*; the implementation underneath is danos-native. See
  [Why not literal std.Thread](#why-not-literal-stdthread).
- **Threads are a narrow, opt-in capability — not the default concurrency tool.** The
  default for resilience stays **process + IPC** ([resilience.md](resilience.md),
  [ipc.md](ipc.md)). See [Where threads fit](#where-threads-fit-the-resilience-tension).
- **Blocking synchronization is futex-backed, never spin-backed.** Waiters sleep in
  the kernel so an idle core still halts ([halting.md](halting.md)).
- **Per-binary opt-in to multi-threaded codegen.** Only a service that asks for
  threads is built `single_threaded = false`; the rest stay lean and single-threaded.
- **The thread ABI is private.** New syscalls extend [abi.zig](../system/abi.zig)
  `SystemCall` and are reached only through `library/runtime` wrappers, exactly like
  every other danos syscall ([syscall.md](syscall.md)) — numbers stay renumberable.

## Why not literal `std.Thread`

danos's ABI invariant is that the **runtime is the sole holder of the syscall ABI**,
and that ABI is private and renumberable ([syscall.md](syscall.md) — "unstable
private ABI"). That is a security and evolvability asset: no compiled binary can
hardcode a syscall number, and the kernel can renumber freely because only the
runtime — rebuilt in lockstep — knows the mapping.

`std.Thread` is incompatible with that invariant on two counts:

1. **It selects its backend from `builtin.os.tag`, and issues syscalls directly.**
   danos targets `.os_tag = .freestanding` ([build.zig](../build.zig)), for which
   `std.Thread` resolves to an unsupported stub that `@compileError`s. Adding a real
   backend would either bake danos syscall numbers into std (breaking ABI privacy and
   renumbering) or fork std to route back through the runtime — a permanent rebase
   cost that buys nothing the native type doesn't.
2. **Our user binaries are built `single_threaded = true`** ([build.zig](../build.zig)
   `addUserBinary`), which compiles threading out entirely and makes atomics and TLS
   single-threaded. Threads need this flipped per binary regardless.

So we take the *shape* of `std.Thread`, not the *type*. The cost of replicating the
surface (spawn/join/Mutex/Condition) is small; the cost of the std type is the ABI
invariant.

## Where threads fit: the resilience tension

Threads are in genuine tension with a resilience-first microkernel, and it is worth
being explicit so we do not reach for them by reflex.

The reason danos pays for a microkernel is **fault isolation**
([resilience.md](resilience.md)): a component corrupts its own address space, faults,
and is **restarted** without touching anyone else — because the boundary *is* the
address space. Threads deliberately remove that boundary *within* a process:

- Threads share one address space, so one thread's stray write corrupts them all —
  there is no isolation **between** threads.
- Threads share fate: a fault in any thread, or a "kill the process" decision, takes
  down **all** of them. Restartability lives at the process level, not the thread
  level.
- Shared mutable state reintroduces data races — the failure class the
  isolate-and-message model was chosen to avoid.

**Therefore:** the default answer to "make X concurrent" stays *another process over
IPC* (isolated, independently restartable) or a single event loop with several
message sources. Reach for a thread only inside **one** service that needs genuine
**shared-memory, low-latency parallelism** and can accept intra-service fate-sharing —
e.g. a compositor splitting tile compositing across cores, where per-tile IPC would be
too chatty. "Input on one thread, display on another" is *not* that case; it wants two
processes. The isolation boundary stays at process granularity.

## The API surface (mirrors `std.Thread`)

Lives in `library/runtime/thread.zig`, re-exported as `runtime.Thread`.

```zig
pub const Thread = struct {
    pub const Id = u32;                       // the kernel task id
    pub const SpawnConfig = struct {
        stack_size: usize = default_stack_size,
        allocator: ?std.mem.Allocator = null, // for the closure + stack bookkeeping
    };
    pub const SpawnError = error{ OutOfMemory, ThreadQuotaExceeded, SystemResources };

    pub fn spawn(config: SpawnConfig, comptime function: anytype, args: anytype) SpawnError!Thread;
    pub fn join(self: Thread) void;           // block until the thread ends, reclaim its stack
    pub fn detach(self: Thread) void;         // give up the right to join; kernel reclaims on exit
    pub fn getCurrentId() Id;
    pub fn yield() void;                       // -> existing `yield` syscall

    pub const Mutex     = struct { pub fn lock(*Mutex) void; pub fn tryLock(*Mutex) bool; pub fn unlock(*Mutex) void; };
    pub const Condition = struct { pub fn wait(*Condition, *Mutex) void; pub fn timedWait(*Condition, *Mutex, u64) error{Timeout}!void; pub fn signal(*Condition) void; pub fn broadcast(*Condition) void; };
    pub const Semaphore = struct { pub fn wait(*Semaphore) void; pub fn post(*Semaphore) void; };
    pub const Futex     = struct { pub fn wait(*const atomic.Value(u32), u32) void; pub fn timedWait(...) error{Timeout}!void; pub fn wake(*const atomic.Value(u32), u32) void; };
    // RwLock / ResetEvent / WaitGroup follow the same pattern, added as needed.
};
```

Deviations from `std.Thread`, called out honestly:

- **The thread function's return value is discarded** (as `std.Thread.join` returns
  `void`). Return data through shared state or a `Semaphore`/`Condition`, not the
  return.
- `getCpuCount()` maps to the existing SMP core count ([smp.md](smp.md)); a service
  rarely needs it.

## Kernel primitives (new private syscalls)

Four new entries extend [abi.zig](../system/abi.zig) `SystemCall` after
`shm_physical = 36`, each with a `library/runtime` wrapper:

| Syscall | Signature | Purpose |
|---|---|---|
| `thread_spawn` | `(entry, stack_top, arg) -> tid` | create a task sharing the **caller's** address space |
| `thread_exit`  | `(stack_base, stack_len)` | end the calling thread; hand back its stack range for reclaim |
| `futex_wait`   | `(addr, expected, timeout_ns) -> status` | block if `*addr == expected`, until woken or timeout |
| `futex_wake`   | `(addr, count) -> woken` | wake up to `count` waiters on `addr` |

Plus one invariant change with no new syscall: **address-space reference counting**.

## Mechanics

### Address-space reference counting

Today an address space is 1:1 with a task: `spawnUserLocked` records `address_space` on the
Task, and teardown does `destroyAddressSpace(t.address_space)` when **any** user task exits
([scheduler.zig](../system/kernel/scheduler.zig)). With threads, several tasks share
one `address_space`, so the first to exit would rip the address space out from under its
siblings.

Fix: a small refcount keyed by the address-space root (`createAddressSpace` in
[process.zig](../system/kernel/process.zig) sets it to 1). `thread_spawn` increments
it; task teardown decrements and only calls `destroyAddressSpace` at **zero**. All of
this is already under the big kernel lock, so no new locking. This is the one piece
that must land and be proven before anything shares an address space.

### `thread_spawn` and the trampoline

The scheduler already accepts an arbitrary `address_space` and does **not** smuggle values
through registers — `startUserTask` reads the entry/stack from the Task and
`jumpToUser`s ([scheduler.zig](../system/kernel/scheduler.zig)). That makes the thread
path clean:

1. The runtime's `spawn` `mmap`s a stack (syscall `4`), heap-allocates a closure —
   `{ fn_ptr, args_tuple, completion }`, the std "Instance" pattern — and writes the
   closure pointer to the **top word of the new stack**.
2. It calls `thread_spawn(entry = &threadTrampoline, stack_top, arg = closure_ptr)`.
   The kernel calls the same `spawnUserLocked` path with the **caller's address space**
   (refcount++), `entry`, and `user_sp = stack_top`.
3. `threadTrampoline` (a small runtime shim) reads the closure off its stack, calls
   the user function, then calls `thread_exit`. No new register ABI — the closure
   pointer rides the stack the runtime set up, mirroring how `startUserTask` avoids
   register smuggling.

Unlike a process start, there is **no** System V argc/argv/auxv block
([sysv.md](sysv.md)) — a thread stack carries only the closure pointer.

### Lifetime: exit, join, detach, stack reclaim

- **`thread_exit`** marks the task dead and hands the kernel the thread's user-stack
  range. The kernel reaps the task on the scheduler (already running on a *kernel*
  stack, so it can safely unmap the user stack), decrements the address-space refcount, and
  frees the task slot.
- **`join` — Stage 1** reuses the existing exit-notification machinery
  ([process-lifecycle.md](process-lifecycle.md)): `spawn` passes a per-thread
  `exit_endpoint`, and `join` blocks in `ipc_reply_wait` until the child-exit
  notification for that `tid` arrives, then `munmap`s the stack. No futex needed to
  land spawn/join.
- **`join` — Stage 2 refinement** migrates to the std shape: a `completion` word in
  the closure that `thread_exit`'s trampoline `futex_wake`s and `join` `futex_wait`s
  on — dropping the per-thread endpoint. Kept as a refinement so Stage 1 ships first.
- **`detach`** relinquishes the join right; the kernel reclaims the stack and slot on
  `thread_exit` (a detached thread's stack range is unmapped by the reaper, since no
  joiner will).

### Futex, and the sync primitives on top

`futex_wait`/`futex_wake` are the one blocking primitive; `Mutex`, `Condition`, and
`Semaphore` are ordinary user-space state machines over an `atomic.Value(u32)` that
call the futex wrappers on the slow path — the same construction `std.Thread` uses,
so the algorithms port directly.

Keying: threads share an address space, so a **virtual address within that address space**
identifies a futex uniquely; the kernel keys its wait queue by `(address_space_root, virtual_address)`.
Keying by the **physical** address instead (translate `virtual_address -> physical_address` on entry) is a
deliberate forward door: it lets two *processes* share a futex through an
[shm](display-v2.md) region later, without changing the API. We start with the
private-per-address-space key and note the physical-key upgrade.

No spinning: a contended lock parks the task in the kernel and the core is free to run
other work or `hlt` ([halting.md](halting.md)). This is why futex is a locked
decision, not a "maybe later."

### TLS and `getCurrentId`

danos sets up no thread-pointer TLS today (fine under `single_threaded`). Two scoped needs:

- **`getCurrentId`** returns the kernel task id — either a trivial syscall or, better,
  a value the runtime stashes in a per-thread control block.
- **`threadlocal` variables** need a real per-thread TLS block and the thread pointer set per
  thread. `thread_spawn` sets the thread pointer to a runtime-allocated per-thread block; full
  `threadlocal` support is Stage 3, only if a consumer needs it. Nothing in the core
  spawn/join/mutex path requires `threadlocal`.

### Build: multi-threaded codegen, opt-in

`addUserBinary` gains a `threaded: bool = false` parameter; when set it builds that
binary `single_threaded = false` so atomics and (later) TLS are real. Threads and
atomics are unsound in a `single_threaded` image, so a binary must opt in **before**
it may call `runtime.Thread.spawn`. Everyone else stays single-threaded and lean.

## Interaction with the rest of the kernel

- **Scheduler / SMP** ([scheduling.md](scheduling.md), [smp.md](smp.md)): a thread is
  just another `Task` with an `address_space` shared with its siblings; the existing
  per-core ready queues, priorities, and affinity apply unchanged. Threads of one
  process can run on different cores simultaneously — that is the point.
- **Halting** ([halting.md](halting.md)): futex-parked waiters keep the "idle core
  halts" property intact under lock contention — no busy-wait.
- **Lifecycle** ([process-lifecycle.md](process-lifecycle.md)): killing a process
  must kill *all* its threads and only then drop the last address-space ref. The kill path
  already targets a process; it fans out to every task on that address space.
- **Resilience** ([resilience.md](resilience.md)): a faulting thread kills its whole
  process (shared fate). The supervisor restarts the **process**, which respawns its
  threads from a known-good state — restart granularity stays the process.
- **IPC — two consequences threads forced ([ipc.md](ipc.md)):**
  - *Handles do not cross threads.* The handle table lives on the `Task`
    ([scheduler.zig](../system/kernel/scheduler.zig)), so a handle number is meaningful
    only to the thread that created it — thread A's endpoint handle `3` is not thread B's.
    A thread that needs to reach an endpoint another thread owns looks it up
    (`ipc.lookup(service)`) to install its **own** handle to the same underlying endpoint.
    This is how the display's mouse-listener thread reaches the compositor loop's endpoint
    to poke it awake (docs/display.md).
  - *IPC syscalls that touch shared kernel state now serialize under the big kernel lock.*
    `create_ipc_endpoint`/`ipc_register`/`ipc_lookup` allocate from the kernel heap and
    mutate the global service registry, endpoint refcounts, and handle tables. Those paths
    were unlocked because a single-threaded process could not race itself; a multi-threaded
    one can, from two cores at once. They now take `sync.enter()` like `call`/`reply_wait`/
    `send` already did — the kernel heap has no lock of its own yet (heap.zig: "a lock comes
    with threads/SMP"), so the big lock is what keeps its callers serialized.

## Build-out plan (staged, each gate serial-checkable)

The ordered, `/loop`-runnable milestones live in
**[threading-plan.md](threading-plan.md)** (shaped like
[display-v2-plan.md](display-v2-plan.md)): every milestone lands on its own and ends in
a verifiable gate (`python3 test/qemu_test.py <case>`, asserting serial markers;
`zig build test` for host unit tests). The stages below are the shape it expands.

- **Stage 0 — address-space refcount.** Refcount on the address-space root; teardown destroys
  at zero. No API yet; nothing shares an address space, so refcount is 1 everywhere.
  *Gate:* the full QEMU suite stays green (no regression) — proves the reframing is
  invisible until used.
- **Stage 1 — spawn / join / detach.** `thread_spawn` + `thread_exit`, the trampoline,
  stacks via `mmap`, join over the exit-endpoint, the `threaded` build flag.
  *Gate:* `-Dtest-case=thread-spawn` — a threaded test service spawns N threads that
  each `@atomicRmw`-increment a shared counter, the parent joins all N, and asserts
  the total is exactly N × iterations. Runs `smp` (multi-core) to prove real
  parallelism.
- **Stage 2 — blocking synchronization.** `futex_wait`/`futex_wake` + `Futex`,
  `Mutex`, `Condition`, `Semaphore`; optionally migrate join to a futex completion
  word. *Gate:* `-Dtest-case=thread-mutex` — a bounded producer/consumer over a
  `Mutex` + `Condition` moves K items with no lost wakeups and no busy-wait (assert
  the consumer blocked, e.g. via a low idle tick count).
- **Stage 3 — polish.** Per-thread TLS / thread pointer and `threadlocal` (only if a
  consumer needs it), `RwLock`/`WaitGroup` as demanded, and this doc's cases wired
  into [test/qemu_test.py](../test/qemu_test.py).

## Conventions

Follow [coding-standards.md](coding-standards.md): spell out non-acronym
abbreviations, kebab-case file names, no `Co-Authored-By` trailers. New syscalls
extend [abi.zig](../system/abi.zig) `SystemCall` + a `library/runtime` wrapper
([syscall.md](syscall.md)). `runtime.Thread` is a first-class runtime module, the same
way `runtime.process` ([process-lifecycle.md](process-lifecycle.md)) and `runtime.ipc`
are — user code never names a syscall.

## Non-goals

- **No preemptive user-space signals delivered to a specific thread.** Signals stay
  process-scoped ([process-lifecycle.md](process-lifecycle.md)).
- **No thread priorities distinct from the process.** Threads inherit the process
  priority; per-thread priority is a later question if it ever earns its keep.
- **No cross-process shared-memory futex yet** — the physical-address key leaves the
  door open, but the first cut is private-per-address-space.
- **No `pthread`/POSIX surface.** The API is `std.Thread`-shaped Zig, nothing more.

## The self-hosting endgame

When danos becomes a real Zig target and we (eventually) add a danos backend to std
([zig-self-hosting.md](zig-self-hosting.md)), `std.Thread` can sit *on top of* these
same kernel primitives — the danos `std.Thread.Impl` would call the very
`thread_spawn`/`futex_*` wrappers `runtime.Thread` already uses. Because
`runtime.Thread` was built API-compatible from day one, that transition swaps the
implementation, not a single call site. Designing to the std shape now is what makes
the later self-hosting lift cheap.

## Further reading

- [scheduling.md](scheduling.md), [smp.md](smp.md) — the task model these threads join.
- [resilience.md](resilience.md), [vision.md](vision.md) — why isolation is the default
  and threads are the exception.
- [syscall.md](syscall.md), [ipc.md](ipc.md) — the private ABI and the messaging model
  threads sit beside.
- [halting.md](halting.md) — the idle/halt property futex-backed blocking preserves.
- [zig-self-hosting.md](zig-self-hosting.md) — the target this bends toward.