# Memory

This document owns the memory model of Gizlang: what each part of memory management does, the
one owner of each part, and the rules between them. [RUNTIME](runtime.md) owns the C files and
their ABI. [COMPILER](compiler.md) owns code generation.

## The model in one paragraph

Values are owned and counted. A string, bytes, Vec or function value is one buffer with a count.
The compiler emits the counting (dup, drop, write-in-place when the count is 1). A buffer that a
second owner gets is copied only when one of the owners writes (copy on write). There is no
collector for values. The only collected memory is the heap of `Ref<T>` objects: a program makes
one with `Memory.create`, and only then. Each World has one heap, on one thread. It is precise
and does not move objects. Its roots are the compiler's root frames, the parked frames of
suspended tasks, and holds. Every byte, an object's own block and every buffer, counts against
one budget: the World's `GIZLANG_MEMORY_LIMIT`. The same limit bounds all Worlds together:
the allocator measures the process's resident memory, and a request that would pass the limit
fails with fault 11 on the thread that asks (the table below).

## Concerns and owners

| Concern | Owner | Rule |
| --- | --- | --- |
| Allocation of blocks | `runtime/memory.c` (`gizlang_block_alloc`); `wasm.c` on Wasm | Size classes in thread-local pages. Blocks past the largest class go to malloc. Heap objects and buffers both come from here. A thread keeps at most 4 MiB of empty pages resident (`KEPT`), each for 1 s; a page that empties past that is given back at once. `string(b)` shares the buffer of `b` unless its capacity passes 2 × the length + 64 (append room); then it copies the bytes into an exact buffer (`gizlang_rc_fit`). |
| The process bound | `runtime/memory.c` (`charge`, `gizlang_memory_resident`) | The anonymous resident memory of the process, measured from the kernel each time the allocator takes a step of fresh memory, never passes `GIZLANG_MEMORY_LIMIT` for all threads together. Past it the allocator gives back what it keeps (kept large blocks, empty pages, `malloc_trim`), asks the `Task.parallel` threads and the event loops that wait to give back the empty pages they keep (`io.c` `reclaim_waiting_loops`, at most 50 ms), and measures again; a request still past it fails as a budget does (fault 11). A thread that is not essential (`Memory.essential`) leaves 1 / `ESSENTIAL_SHARE` of the limit to those that are (a server's engine loop). Shared buffers settle into a budget with no check of their own: this bound is the check. The host's room bounds it too (`host_room`): the room left in the process's cgroups and on the machine, so a request fails with fault 11 before the kernel OOM-kills the process; a request takes at most 1 / `ROOM_SHARE` of the room. |
| The budget | `Gizlang_Context.memory_remaining` (word 4), refilled by `gizlang_memory_more` | One budget for each World call. A buffer, a heap object and the buffers it holds are charged when made and credited when freed. No other quota exists. Refusal is fault 11 (`R011`). |
| Counting of owned values | `compiler/ownership.giz` (generated dup, drop, mark, unique) | The count is at data-16 and the capacity at data-8. `n > 0` is owned by one thread, `-1 - n` is shared between threads, `-1` is immortal. `runtime/value_layout.c` (`gizlang_value_retain`, `gizlang_value_drop`) does the same by layout, for the runtime. |
| Lifetime of expression temporaries and their root slots | `compiler/managed.giz` `rootedExpression`, `compiler/emit.giz` `dropTemporaries` | A root slot holds only a value its frame owns (a temporary), never a borrow of a parameter, a local or a place of one: their binding roots them. A temporary's buffers and its root slot end together, where the temporary ends. |
| Roots | `runtime/heap.c` | Root frames (compiler, LIFO), parked frames of suspended tasks, holds (values outside every frame) and shared borrows. Nothing else is a root: no stack scan, no pins. |
| Heap objects and their handles | `runtime/heap.c` | The heap owns each object's slot, generation, block and value. A `Ref` is `(generation << 32) \| (slot + 1)`. Objects are not resources. |
| Collection | `runtime/heap.c` `collect` | Two generations. A minor collection marks from the roots and the remembered set and sweeps the young objects; a major one marks and sweeps all. An edge to no live object fails the collection with `-40207` and sweeps nothing. |
| Lifetimes | `Memory.region` (`runtime/heap.c` regions) | A region's end frees what it made and did not keep. Web, DB and JS wrap their units (a request, a statement, a COPY batch, an exec) in it. |
| A type's walks | `Gizlang_HeapType` `retain`, `drop`, `trace` (compiler, may be null) | The heap calls the type's own walk when it is set, else it walks the layout. |
| Ownership across tasks | `runtime/task.c` | Tasks of one World share its heap. A suspended task's frames are parked, and still roots. |
| Ownership across threads | `gizlang_value_transfer`, crossing channels, `Task.cell`, `Task.thread` | A value crosses only with no Ref in it. Its buffers are marked shared. Each thread has its own World and heap. |
| Live swap | `runtime/state.c` | A named state binding is a hold. A new type migrates field by field, matched by key. |
| External resources | `runtime/resources.c` | One handle table of files, sockets and processes. A handle has a generation and an owner World. Release is explicit. A World with open resources refuses teardown. Heap objects have no finalizers. |
| Objects of a guest language (JS, Python) | The VM's own generational collector (`vm/heap.giz`) | [VM](vm.md). |

### Rules between the owners

- A buffer has one count. A heap object holds its value's buffers as one more owner. A load gives
  the caller one more owner (`gizlang_services_ref_load`: one copy of the fixed bytes, no
  buffer copy). A store gives the object the new value and drops the old one. A write to a
  loaded value copies only what it changes.
- A Ref lives only in the heap that made it. No boundary admits a Ref: thread closures and
  results, crossing channels and cells refuse one (`gizlang_value_transfer`). A Ref from another
  heap names nothing, because each heap starts its generations at its own seed.
- Collection happens only at a Ref allocation or store, or at `Memory.collect`. At these
  points the compiler roots every Ref it still holds. A buffer allocation never collects,
  because generated code holds Refs in registers between root slots.
- A Ref allocation collects when the heap has twice the objects or object bytes that the last
  collection left (at least 4,096 objects or 4 MiB), or when the budget is below a quarter of the
  limit and has fallen by a sixteenth of the limit since the last collection. The budget shows
  dead buffers that a heap object held: the heap does not count them itself.
- When a call ends, the World's heap is collected into the call's budget before the leak check
  (`runtime/process.c`, `wasm.c`). A byte that is still taken is a leak (exit 70).
- A task that faults, also with fault 11 (over the budget), fails alone: its joiner gets the
  fault as a value, and the join collects, so the Refs the task held go back to the budget. A
  server that runs each request or statement in a task turns that value into its own limit error
  (a DB statement gets a DbError); a fault outside every task ends the World.
  `tests/sdk/memory/task-limit`.
- A heap object whose layout can reach no Ref (bytes, strings, vectors of scalars, records of
  them) is a leaf: a collection marks it and never walks its value.
- A stored value's edges are checked by a walk only under GC stress. In production every Ref in a
  value that generated code holds is rooted, so it is valid by construction; the walk cost a whole
  value per store (7 µs per Resources reserve in a COPY).
- **Generations.** An object is young until it survives a collection, then old. The barrier is
  in the two stores (`gizlang_heap_replace` and `gizlang_heap_swap`, the put-back of
  `Memory.update` included): a store into an old object that can hold a Ref puts it in the
  remembered set, once. A new object names only older ones, so a store is the one way an old
  object can come to name a young one. A minor collection traces the roots and the remembered
  objects, never an old object's edges, and sweeps the young list. A minor collection runs when
  the young objects reach 4,096 (or twice the young survivors) or 4 MiB; a major one when all
  objects double, or on budget pressure, and `Memory.collect` is major. Under GC stress three
  minor collections run to each major one.
- **`Memory.region(f)`** runs `f` as one lifetime. While a region runs, a collection keeps its
  young survivors young (they are not promoted), so the minor collection at the region's end
  frees all that `f` made and did not keep: in its result, a root or an older object (the
  barrier finds the stores). The survivors become old after the outermost region. It is not
  O(1): each freed object's buffers are dropped. A region that faults ends without the
  collection. Regions nest, and tasks may interleave them: the rule above is correct for any
  order, only less exact. The runtime entry is `gizlang_memory_budgeted` with bytes -1 (no grant
  of its own); `Memory.budgeted` treats a negative grant as 0.
- **Validation of stored values.** `gizlang_heap_allocate`, `_put`, `_replace` and `_swap` check
  a value's edges only under GC stress. Every Ref in a value from generated code was valid when
  loaded, and is rooted since, so it names a live object of this heap: a Ref of another World
  never reaches a store (a value crosses Worlds only with no Ref in it, `gizlang_value_transfer`),
  and a stale one would mean a missing root, which stress finds. A wrong edge found at a
  collection fails it with `-40207` before any sweep, in every build.
- **A type's own walks.** `Gizlang_HeapType` (64 bytes) ends with `retain(value)`,
  `drop(context, value)` and `trace(value, visit, state)`, each emitted by the compiler or null.
  `trace` visits each Ref, and a boxed word's short form `(1 << 63) | payload` for each tag in
  its mask. `gizlang_services_ref_put`, `_copy` and `_swap` are create, load and store for a
  compiler that dups and drops by type: put takes a dup'd value as is (the caller drops it on an
  error), copy gives the bits, swap stores a dup'd value and gives the old bits to drop.
- `Memory.update(r, f)` is the one in-place write of a Ref's value. The value moves out (no
  count), `f` gets it as `mut` and is its one owner, so it writes without a copy; the value
  moves back when `f` returns. Meanwhile the object is busy: a load, store or update of it
  faults, and a collection marks it without tracing it (the caller's frame roots the value). If
  `f` faults, the object stays busy: valid to trace and to sweep, never readable again.
- `Memory.budgeted(bytes, f)` runs `f` on the calling task with at most `bytes` of the running
  budget. The scope takes its grant out of the running budget (a nested scope out of its
  parent's) and stops refills, so scopes never add up. Over it, `f` ends with fault 11 and
  unwinds (its frames drop what they own), and `budgeted` returns `MemoryLimit`; any other
  fault goes on. A scope bounds its own task only: a task switch parks it (runtime/task.c).
  The caller's state is as `f` left it; a DB rolls back through its transaction.
- `Memory.weak(r)` does not keep its object alive; `Memory.upgrade(w)` gives the Ref while the
  object lives. A Weak is always the full 64-bit Ref (31-bit generation), never a boxed word's
  short form, so a dead Weak never names a later object in its slot: a slot whose generation
  would come back to its first is retired. `Memory.collections()` counts collections, so a
  table of Weak values (an intern table) drops its dead entries when it changed.
- `Memory.census(top)` says where the memory is, as text: the World's Ref objects by type (count and
  bytes, a type by the names in its key), the allocator's blocks of every thread by size class with
  the pages that hold them, the empty pages kept and given back, and the blocks past 64 KiB. It walks
  every object and page, so it is for finding where memory went, not for a hot path.
- `Memory.pin(r)` gives a u64 word that keeps its object alive until `Memory.unpin(word)`, for a
  table outside the program's values (a VM's cache of compiled code per JS object, a native's
  handle). The word is the Ref's own bits; `Memory.pinned<T>(word)` gives the Ref back, or
  undefined for another type. A pinned object is a collection root, as an open borrow is. Each
  pin needs its own unpin; an unpin of a word with no pin faults. A pin still held when the entry returns
  ends there, as the program's module state does, so it is no leak (`runtime/heap.c`
  `gizlang_heap_unpin_all`).
- `Memory.Boxed<MASK>` is a NaN-boxed word (JS values; Python later): boxed when its top 13
  bits are set, with its tag in bits 48 to 50. The tags in MASK (JS: `0x78`, tags 3 to 6:
  string, symbol, bigint, object) hold a reference: a heap slot in the low 32 bits and the low 16 bits of its generation above. A
  collection traces those (the 16 bits are a guard: a traced object is alive); a double and any other tag (JS's 7, an array hole, payload 0)
  are scalars. `Memory.box<T, MASK>(r, tag)` and `Memory.unbox<T, MASK>(word)` convert;
  unboxing checks the tag, the slot and the type, as a load does.
- A Task.thread whose work faulted ends its OS thread. Only a thread whose work returned is
  reused. The kernel releases what a thread issued (its io_uring commands) only when the thread
  exits.

### The guest heap rule

A guest language (JavaScript, Python) runs on the VM and keeps its values in the VM heap (`vm/heap.giz`): `u64` values,
a non-moving generational collector, and a conservative scan of the native stack. Gizlang heap structures that the VM
holds are invisible to it, so the VM roots them by hand. The VM's memory counts under the one budget.

## Measurements

`bench/memory/main.giz`, best of 3, `GIZLANG_GC_STRESS=0`:

| Load | Time |
| --- | --- |
| graph: 20 rounds of a 20,000-node ring | 35 ms, 12 MiB peak |
| directory: 200,000 sets in a ManagedPageDirectory of 4,096 | 382 ms |
| record: 1,000,000 load and store of one 12-field record | 192 ms |

## Limits

- **Tasks.** A task costs 4.4 KB at 100,000 tasks (`bench/tasks`), against 2.5 KB for a goroutine. Each task has its
  own guarded stack, and a stack costs at least one 4 KiB page.
- **Escape analysis.** The compiler borrows const bindings and reuses unique buffers. A Ref whose object does not escape
  a function is still a heap object.
- **Allocator.** One allocator API (`gizlang_block_alloc`) has every block. A replacement goes behind that API only, and
  is measured with `bench/memory` and the bench suites.
- **Bulk loads.** Leaf objects (a Ref to bytes, a string or a column vector of scalars) are never walked, and old objects
  are not marked again (generations, above). A batch can run in `Memory.region`. In a database COPY, marking is about 3%
  of the CPU; the rest is Ref loads and stores that copy whole values.
- **Weak references and finalizers** do not exist. Cycles of Refs are collected. Cycles of counted buffers cannot form: a
  buffer cannot point to itself without a Ref.
- **Sanitizers.** `giz test` has no ASan, UBSan or TSan build. Stress collection is the default of `giz test`, and a
  bad edge fails with `-40207`.