Memory management
How the WebAssembly backend lays values out, inserts Perceus reference counting and reuses memory
This page says how the WebAssembly backend lays values out, counts references and reuses memory. What a user sees is in Reference counting, and what is still to do or open is on Memory management in Work in progress.
Summary
Compiled programs free memory by reference counting in the style of
Perceus
(Reinking, Xie, de Moura and Leijen, PLDI 2021), the scheme Koka uses and close to what Lean 4 does
(Counting Immutable Beans, Ullrich and de Moura, 2019). The compiler inserts
precise dup and drop operations, so an object is freed as soon as nothing refers to it. When a function takes
apart a value it holds the only reference to and builds a new one of the same size, the old memory is reused in
place. Generic code is monomorphised, so every object’s layout is known when it is compiled. The host’s garbage
collector (WasmGC) is not used: it would give up reuse and deterministic freeing, and need hosts with GC support.
An int and a U64 are i64s, a float an f64, an F32 an f32, and every other value an i32 (see Value representation).
On the heap, after each object’s header:
| Value | Layout |
|---|---|
| String | UTF-8 bytes, the byte length in the 4 bytes before the pointer, a 0 byte after |
| List | 0 for the empty list, else a pointer to a cell of (head, tail) |
| Record, tuple | the fields one after another in field-name order, the layout’s number in the 4 bytes before |
| Closure | the function’s table slot, then the captured values; the table slot of its environment’s drop function in the 4 bytes before |
| Tag with a payload | a pointer to a cell of (code, payload) |
String literals live in the data segment, with a header of their own. A tag without a payload is not on the heap: it is its code,
(id << 1) | 1. Codes are odd and allocations are 4-byte aligned, so a tag value is a code exactly when its low
bit is set (#181).
Code generation goes from the typed module through the core IR to WebAssembly text.
Design
Monomorphisation
drop has to recurse into the fields of an object it frees, so it has to know which fields are pointers. The core IR
compiles every generic function once for each set of concrete type arguments it is used at, so every value’s type,
and so every object’s layout, is known at compile time. Each type gets a generated drop function (drop of a
List<string> drops each head as a string and each tail as a list), and nothing at run time has to say what a field
is. Integers keep their full width, nothing is boxed behind the program’s back, and every size Perceus reuses is a
compile-time constant. A function that reads fields of any record that has them is specialised per record layout. The
definitions a module reaches in the modules it imports (the prelude included) are inlined into it before code
generation (Inlined in Library.fs), so every generic function’s body is available to specialise.
Tags keep their odd codes: a value of type #some(string) | #none is still a code or a cell, decided at run time,
and its drop function checks the low bit before reading the cell.
If code size becomes a problem, the fallback is Koka and Lean’s: box values only at the generic boundaries that are not specialised (see Open questions).
Value representation
Every value is held at its own width, in locals, fields and payloads alike, and no number is boxed.
An int is an i64 in locals, parameters and results, and takes 8 bytes in a field, a list cell’s head, a tag’s
payload and a closure’s captures, with the narrower sized integers in their own width and every other value in 4
(CoreIrLayout.fs). A local of an int is named with _i64 after the variable’s name, since variables of the same
kind and name share a local. The runtime helpers that store a value (listCons, tagBox, recordSet and the rest)
have an _i64 variant, and a call through a closure uses a function type of the values it passes
(Wat.indirectTypeName).
A U64 is held as an int is. I8, I16, I32, U8, U16 and U32 are
i32s in locals, sign-extended or zero-extended from their width as they are signed or not. In a field, a list
cell’s head, a tag’s payload and a closure’s captures each takes its own width: an I8 or a U8 1 byte, written
with i32.store8 and read with i32.load8_s or i32.load8_u, an I16 or a U16 2, with i32.store16 and
i32.load16_s or i32.load16_u, and an I32 or a U32 4 (CoreIrLayout.storage). Fields are laid one after
another with no padding, so an int after a U8 is read unaligned, which WebAssembly allows. Each storing helper has
a variant for each width, _i8, _i16 and _i64 after its name (WasmRuntime.Storage).
A float is an f64 in locals, parameters and results, and takes 8 bytes wherever an int does, written with
f64.store and read with f64.load; the storing helpers have an _f64 variant for it. It is not on the heap, so nothing
counts it (CoreIrDrop.isHeapType), and arithmetic on floats allocates nothing. A float constant is an f64.const.
The float intrinsics and the helper that writes a float as text take and give f64s, and an extern passes a float as
the f64 it is.
An F32 is held as a float is, as an f32: in locals, parameters and results, and in 4 bytes in memory, written
with f32.store and read with f32.load, with an _f32 variant of each storing helper. Nothing counts it either, and
arithmetic on F32s allocates nothing. % on F32s is taken as a float’s, which is exact, and narrowed back.
Pointers stay 32-bit: linear memory stays memory32. A 64-bit address space (Wasm memory64) only matters past
4 GB of heap, and would double the size of every pointer field.
Object header
Every heap object has a reference count in the word before its info word, so a pointer p to an object with one has
its count at p - 8 and the info word at p - 4: a string’s length, a record’s layout, and a closure’s environment
drop function (below). An object with no info word (a list cell, a tag’s cell) has its count just
before its fields, at p - 4. Every dup and drop knows the type of what it counts, so it knows which; giving
the commonest objects, list cells, an empty info word would make each 20 bytes rather than 16 (with the
allocator’s size word). The drop function for the object’s type knows the rest, so no other run-time layout
information is needed. __nanyx_new_object and __nanyx_new_cell allocate an object of each kind with a count of
one, and __nanyx_release gives up a reference, telling the caller whether it was the last.
Static data (string literals, and closures that capture nothing) gets a header too, with a count of 0, which marks it
as immortal: release leaves it alone, so it is never freed. A literal in the data segment is laid out as a string
on the heap is (the count, the length, the bytes and a 0 byte), padded to 4 bytes so that the next one is aligned.
A closure that captures nothing is the same block every time it is made: a closure over a top-level function passed
as a value (list.map(xs, double)), over a context member’s function passed at a call (the six that println
takes), or over a lambda that captures nothing. So it is static data (#743):
one block per lifted function in the data segment, after the string literals, laid out as a closure on the heap is
(the count, the info word, the table slot), with an info word of 0, since nothing drops it. In the core IR it is an
atom, AStaticClosure, so reference counting gives it no dup or drop, and making one is an i32.const.
Drop functions
CoreIrDrop.fs generates one for each type on the heap that the module’s functions use
(__nanyx_drop_list_string, named by the type), together with the types of their fields. Each gives up a reference
and, when it was the last, drops the fields that are on the heap and frees the object:
- a list’s walks along the list cell by cell, as long as each cell was held only by the one before it, so dropping a long list takes no stack;
- an array’s drops each of its elements, from the first to the last. An array is a block made by
__nanyx_new_cell, so its count is atp - 4, then its length, ani32, atp, then its elements one after another, each stored as a list cell’s head is (CoreIrLayout.arrayElementOffset). A mutable array (MArray) is laid out the same way, so its drop is an array’s; anMRefis a one-field record, so its drop is a record’s; - a tag union’s returns at once for a code (an odd value); for a cell, it reads the code to tell the payload’s type, unless every tag with a payload has a payload of the same type;
- a function value’s calls the function whose table slot is in the closure’s info word, which drops what the
closure captures. There is one such function per list of captured types (
__nanyx_drop_env__string), and one,__nanyx_drop_env, for closures whose captures are none of them on the heap (a closure that captures nothing at all is static data, and is never dropped). It is called through the function table, so it has the type of a closure of one parameter, and returns 0; - a recursive type’s and a function value’s, called while another drop is under way, leave the object they give up
the last reference to waiting on the type’s list, a global (
__nanyx_drop_pending_…) linked through the objects’ counts, which they no longer need, and return. Called when no drop is under way, they drop the object at once with the type’s other drop function (__nanyx_drop_dead_…, which drops the fields of an object whose last reference is gone and frees it), then run__nanyx_drop_pending, which takes the objects waiting off their lists one at a time and drops each the same way, until every list is empty. Dropping one object may leave more waiting, but never calls itself, so a value nested 100,000 deep, such as a trie with a key that long (#1670) or a chain of closures each capturing the one before (#1706), takes no more stack to drop than a shallow one. Every chain of drop functions that calls itself passes through one of these: a function value’s calls its environment’s, which may drop a function value.
Allocator
__nanyx_alloc and __nanyx_free (WasmAllocator.fs) keep segregated free lists by size class, falling back to
bumping $heap_ptr (and growing memory) when a class’s list has nothing to give. Most objects are a handful of
words, so a few small classes cover them; larger objects (long strings, wide records) take a general free list.
- Sizes.
alloc(n)roundsnup to a multiple of 4 (and at least 4), so blocks stay 4-byte aligned and pointers stay even. - 8-byte aligned blocks. A component’s
cabi_reallocmust hand out blocks 8-byte aligned when the host asks it to (Components).__nanyx_alloc_aligned8(allocAligned8Helper) asksallocfor 12 bytes more than it needs. When the block it gets is not 8-byte aligned, it makes the block’s first 8 bytes a block of their own, which it frees, and gives the rest a size word of its own: that block starts 12 bytes on, at a multiple of 8, andfreetakes it back like any other. Under memory checks it counts the block it keeps as handed out. - Size word. A block’s rounded size is stored in the word just before the block
allocreturns, sofree(b)needs only the pointer. The object header is part of the block: a block holds the count, then the info word (if any), then the fields, so the size word sits just before the count. For a string, say, that puts the count atp - 8, the length atp - 4, and the size atp - 12; for a list cell, the count atp - 4and the size atp - 8. The word keepsfreeindependent of types, and lets the large list hand out a bigger block than asked for and still take all of it back. - Classes. Each size from 4 to 256 bytes (64 words) has its own list, so a freed block goes back to exactly the size Perceus will next ask for, without a search. Larger blocks share one list, searched first-fit. The classes reach 256 bytes so that the strings and records programs make most of never go on that list (#1464).
- Lists. The heads are a table of 65 words at the start of the heap, and
$heap_ptrstarts after it. The string literals and static closures run from address 256, and the table goes at 4096 or, when they end past that, after them, 8-byte aligned (heapBaseAfter); the module starts with enough pages of memory to hold them. A free block keeps the next block of its list in its first word. On a small size’s list,freepushes onto the front andalloctakes from the front, so the most recently freed block is reused first. - Large blocks.
freejoins a large block with the free large blocks just before and after it, and a block that then ends at$heap_ptrgoes back to the heap instead; otherwise it goes on the front of the large list. It finds those neighbours without walking the list, by boundary tags (WasmAllocator.SizeWordBits): a free large block has its size in its last word as well as in its size word, and two bits of a size word, which a size never uses, say whether the block is a free large block and whether the block just before it is one. The block after ends where this one does, so its size word is read directly; the block before is found from the size at its end, when this block’s bit says it is free. The list is doubly linked (a free large block’s second word links back), so a neighbour is taken off it at once.allockeeps the bits: it clears the bit of the block after a large block it hands out whole, and a small block’s size word keeps the bit through being freed and handed out again. A free large block never ends at$heap_ptrand never follows another, sincefreewould have joined them.allocsplits a block it takes from the list when the rest would be a large block too; otherwise the block keeps its own size. This is what a string grown by++needs: each copy is freed after the next is made, the copies before it join into a block the one after fits in, so the heap holds about two copies of the string, not every copy there was. - Out of memory. Past 4 GB, the end of a new block wraps around;
allocchecks for that, and formemory.growfailing, and traps withunreachable. It writes no message itself, so a module that never prints imports nothing for it;nanyx runreports anunreachablein__nanyx_allocasRuntime error: out of memory. A host other than the CLI does the same in its own runtime.
Small free blocks are never joined, with each other or with large ones, and the heap never shrinks: memory once
grown is not given back to the host. alloc still searches the large list first-fit, so many large free blocks too
small for a request are each passed over.
Core IR
Perceus works per variable: it inserts a drop x after the last use of x, and a dup x before every use but the
last. That needs a program where every intermediate value has a name and a definite position, so the core IR sits
between the typed AST and WebAssembly text:
source → AST → typed AST → core IR → WAT
It has few constructs (let, call, match, allocate, read field, and the like), in A-normal form, with a
concrete type on every node: generic functions are specialised as the IR is built (see Monomorphisation). Pipes,
interpolation, if ... is, record updates, workflows and context calls are lowered into it, and code generation
works from it alone.
Shape. The IR is in compiler/Nanyx.Compiler.Wasm/CoreIr.fs. A function has typed parameters, a result type and
a body. Types are concrete (int, bool, unit, string, float, a union of tags, a record, a list, a function),
with no type variables. A tuple is a record whose fields are its positions, and a nominal type is the type of its
shape. A body is an expression with a type on every node:
| Node | Meaning |
|---|---|
| atom | a variable or a constant (an int, a bool, unit, a string literal, a tag without a payload, a closure that captures nothing) |
prim(op, atoms) | an operator on ints or booleans |
call(f, atoms) | a call to a top-level function, by its name in WebAssembly text |
makeTag(tag, atom) | allocates the cell of a tag with a payload |
makeRecord(f1 = atom, ...) | allocates a record, its fields in the order they are stored |
field(atom, slot) | reads the field stored in a slot of a record |
updateRecord(atom, slot = atom, ...) | a record with some fields replaced (record with f = v): the same one, updated in place, when it is held once, and a copy otherwise |
x := atom | gives a local cell a new value, dropping the one it held (see Memory) |
x[slot] := atom | writes a field of a box a lambda shares, dropping the value it held: how a captured cell changes |
makeList(atoms) | builds a list |
callRuntime(helper, atoms) | calls a runtime helper: an intrinsic, or what ++ and == on strings, lists and tags need |
makeClosure(f, atoms) | allocates a closure block: the lifted function’s table slot, then what it captures (one or more) |
callClosure(closure, atoms) | calls through a function value, passing the closure block as the environment, to its borrowing or its owning entry (see Closures have two entries) |
floatConstant(value) | a float constant: an f64, or an f32 for an F32 |
forEach(loop) | a for loop over lists and ranges of ints in step, its body run for each step until one of them ends |
crash(messages) | an error deferred to run time: writes the messages to stderr and ends the program |
interpolate(parts) | builds an interpolated string from its text and its holes, each already stored in its hole local |
dbg(location, text) | prints the string text, the text of a value its type’s printer wrote, after the string location, where the dbg was called ([main.nyx:12] ); a release build has none |
let x = value in body | names a value; the value is never a let itself |
do value; rest | evaluates a value for its effects and drops it |
if atom then e1 else e2 | |
match x1, ..., xn | arms | tests variables against each arm’s patterns (_, a literal, a guard such as > 5, a tag with a payload pattern, a tuple, a list, a nominal type’s shape, a binding) |
Every operand is an atom, so every intermediate value has a name. Each variable says what kind it is: a parameter, a local the program declares, a scrutinee, a name a pattern binds, or a temporary (a value the source does not name).
Lowering. CoreIrLower.fs lowers each definition from the typed module: its expressions as the backend sees
them, with each node’s type from ExprTypes and the type of the function at each call from CalleeTypes. Its
FunctionLowering hands parts of the work to files of their own through records of what they need from it, such as
CoreIrLowerMatch.fs for a match and its patterns, CoreIrLowerLocals.fs for local functions generic in variables of their own, CoreIrLowerLifted.fs for lifted lambdas, wrappers and adapters, CoreIrLowerMembers.fs for the context members a call passes and adapting a value to a type, and CoreIrLowerBoxes.fs for boxed values. A
definition whose type is concrete is lowered as it is. A call to a generic definition binds the definition’s type
variables to the types at the call, and asks for the specialisation at those type arguments (id__int,
id__string), which is lowered in turn with the variables replaced. Each specialisation is lowered once, however
many calls ask for it, and a definition can have at most 32 (polymorphic recursion would otherwise never end).
A type variable that nothing constrains (the element of [], the rest of an open union no use closes) is unit:
nothing can make or inspect a value of such a type.
A definition that reads fields of any record that has them is specialised per record layout, so each specialisation
reads its fields from where they are stored. A generic definition exists only as its specialisations: it is neither
compiled nor exported as it is.
A definition inlined from an imported module (the prelude’s list.map, say) is specialised the same way. Only the root
module’s types by node are resolved for the editor’s sake, so the types of the inlined definitions’ nodes are resolved
apart, each by the module it came from, and only the IR reads them (TypedModule.InlinedExprTypes).
Lambda lifting runs on the syntax tree first (LambdaLifting.fs): a lambda becomes a top-level function that
takes a closure block as its environment, and the lambda is replaced by a closure over it, a call to the markers
ClosureSyntax.fs names. The IR lowers a lifted function where a closure over it is made, since only there are the
types of what it captures known. A lambda written in a generic definition is specialised along with it
(__lambda_0__int), and the wrapper that lets a top-level function be passed as a value is lowered for each type it
is passed at. So a lifted function is always lowered at concrete types, and lifting stays on the syntax tree: moving it
into the IR was considered and set aside in #425. A lifted lambda
captures only the context members it may call (#934; see
Context calls).
How a function value is called follows from its type, not from how its lambda names its parameters or how the call
writes its argument, since int, int -> int and (int, int) -> int are one type. A function value whose input is a
tuple of two or more takes one argument for each element (IrType.tupleElements in CoreIr.fs): a lambda or wrapper of
one parameter ({ t -> ... }, { (a, b) -> ... }) takes the elements and builds the tuple again, and a call that
passes a tuple whole (f(t)) reads the elements from it (#441).
A function that requires contexts takes each of their members as a closure, in a parameter of its own after its
others, typed from the context’s definition. A call finds each member the callee requires where the type checker
found its context (a use, the caller’s own members, an instance built from attached definitions, or the ambient
Console). A member that is a top-level function (one of the ambient Console’s, or of an instance built from
attached definitions) or a top-level value is known where the call is compiled, and is not passed: the call goes to a
specialisation of the callee on it (println__string__known), which calls a known function directly and passes it on
to the functions it calls as known. Only a member that is not known is passed as a closure: a use of a lambda, or a
member a function that is not specialised on it passes on. A specialisation makes a closure over a known member only
where it uses the member as a value, as when it passes it to list.map (CoreIrLowerKnown.fs). Context
calls describes this, and what is still to do. A lambda of no parameters is lifted like any other, so def block = { ... } is a function to call. A workflow block that uses a keyword is not a lambda by then: desugaring leaves its body where it
is written.
The module’s top-level expressions are lowered as one more function, the start function, which evaluates each in
turn and drops its value. A module with type or name errors is compiled all the same in a debug build: what failed to
check is a crash that reports the error when it is reached, and a value of no known type because of it has a type of
its own (still an i32). Matching on or interpolating such a value stops the program there, if the error has not
already. A definition (or top-level expression) that holds such errors and cannot be lowered because of them is
lowered to a trap that reports them as soon as it is called. A definition that is generic only because an error left
its type open, and is not specialised, is lowered with its type variables defaulted, so that it still exists.
Top-level values. A top-level value that is not a lambda is lowered to a function of no parameters, one for each
type it is used at when it is generic (proc once per instance). Each one that computes its value is built once, on
its first read (CoreIrCachedValues.fs, #1257,
#1151): the function is emitted as <name>__build, and its own name
is a getter that calls it the first time, keeps the value in a global, and hands each read one more reference to it.
So a dbg in a value prints once, at the value’s first read rather than where it is written, and a list or record a
value builds is allocated once. The inliner leaves the getters alone (it would put the building back at each read). A
value that is a constant (a literal, a closure that captures nothing) is not cached, and is inlined where it is read. A value
that takes a context’s members as parameters is built at each read, as a function is. The start function ends by
dropping each value that was built and marking it unbuilt, so a program run with memory checks frees everything. A
script’s values that need a context are not top-level values by then: they are local defs of its entry point
(Hosts).
Generating code. CoreIrEmit.fs writes WebAssembly text from the IR, with each value in the WebAssembly type of
its type (see Value representation above). A temporary is not stored: it is used exactly once, by the next instruction that needs
it, so its value is computed where it is used. An operand that stores to a local on its way to its value (a match
or an interpolated string among a call’s arguments, say) is one temporary whose value is the whole sequence, stores
and all, so nothing waits on the stack across a store. Record layouts and function table slots are numbered as
functions are emitted, in definition order, each definition followed by its specialisations. What the module needs
besides its functions comes from the IR of exactly the functions it emits (CoreIrFacts.fs): the tags it numbers
(sorted by name, so every case of a tag type a hole prints has one), the string literals in its data segment, and the
helpers dbg calls. The heap is set up when some function calls $alloc.
What cannot be compiled. Every function is compiled from the IR; there is no other way. What the IR cannot lower
is an error, UnsupportedByBackend, reported where it is written: tryTranspileTypedModuleToWat gives the first
one. == on a record, a tuple, a list or a tag with a payload calls an equality function generated for its type,
which compares the values by their structure (CoreIrEquality.fs,
#424). A broken invariant of the backend is reported apart from these, as
BackendInternalError, which asks for a bug report. Only a type-checked module is compiled.
transpileTypedModuleWithReport also lists the functions it was compiled into, specialisations among them.
Inserting counts
On the IR, following the paper:
- Ownership. A function either owns a parameter (and must consume or drop it) or borrows it (the caller keeps it alive). Parameters are inferred as borrowed when the function only reads them.
dupanddrop. Inserted by liveness: a variable is dropped where it dies, on every branch, and duplicated when it is used again after being passed to an owning call.- Drop specialisation. A
dropright after amatchthat took the value apart becomes a check: if the count is one, free the cell and drop only the fields not used; otherwise decrement. - Reuse. When a dropped cell is the same size as one allocated later on the same path, the drop becomes a reuse token and the allocation writes into it when the count was one.
Steps 1 and 2 are CoreIrCounting.fs, run on every function of the module after it is lowered and calls are inlined
into it (Inlining), which adds three
nodes to the IR: dup x1, ...; e, drop x1, ...; e, and e then drop x1, ... (drop once e is done).
CoreIrDrop.fs generates the dup and drop function of each type.
- Every variable owns its reference, except a parameter its function borrows, a name a pattern binds that the
arm does not use, and, inside a
forloop’s body or a guard, every variable from outside it. Each instruction either takes an operand over (a call that owns the parameter, a field of a new object, a value returned) or borrows it (a field read, an operator, a runtime helper,dbg): a variable is duplicated where it is taken over and still used after, and dropped after the instruction that used it last if that one only borrowed it. An instruction reads what it borrows when it runs, after all its operands are evaluated, so a variable it borrows counts as used until then: an operand after it that takes it over (f(x, x)with the first parameter borrowed) gets a reference of its own, a temporary after it (f(x, x * x)) does not drop it, and the variable is dropped once the instruction is done. - Temporaries are counted where they are used. A temporary’s value is computed where it is used (see Generating
code), so its value is analysed there, in the order the operands are evaluated. A temporary an instruction only
borrows is kept in a local as it is pushed (
local.tee), and dropped after the instruction. - Drops happen before a store. What dies in a
let’s value is dropped as the value is computed, before it is stored, so a local the variable shares with another of the same name (see the IR’sVarKind) still holds it. - Matching. An arm takes a reference to each name its patterns bind that it uses, then drops the scrutinee if it does not use it either; in a scrutinee the function borrows, it does neither (see below). Reading a field takes a reference to the value read.
- Ownership. A function called through a closure (a lifted lambda, or the wrapper of a function passed as a value) borrows its environment and owns its other parameters: a call through a closure passes them on owned, or a new reference to one if it is used again, and keeps its own reference to the closure. Another function borrows a parameter on the heap it never takes over, and owns it otherwise; this is worked out over the whole module at once, until nothing changes. Calling a closure only borrows it, so a function that is given one and only calls it borrows that parameter too.
- What a function only reads in a match is borrowed (#1468),
inferred as Lean 4 does (
borrowedFromandcouldReuseinCoreIrCounting.fs). Matching on a parameter does not take it over: the scrutinee that copies it, and the names its patterns bind, are borrowed with it, and so is the closure read as the record of what it captures, which is how the inliner gives an inlined lambda its environment (isReadingCopy, #1877); the function borrows the parameter when none of them is taken over (a call that borrows them in turn, the function’s own tail call included, does not take them over) and no arm could reuse its block (none allocates a block of that size, seeCoreIrReuseSites.fs). So a sum or an evaluator over a shared list or tree counts nothing. The cost accepted: a fold over a list held once doesn’t free each cell as it passes it, which doesn’t change peak memory, since the list was built whole first. - Closures have two entries (#1298,
CoreIrClosureEntries.fs). Each function a closure is over is in the closure’s table slot, borrowing its environment, and a copy of it that owns its environment, its owning entry (__lambda_9__owning), is in the slot after it. A tail call of a closure that dies there calls the owning entry (CallClosurewithOwning, which reads the slot and adds 1), since the caller could not drop the closure after the call; so does a call by name in tail position that passes such a closure as the environment, as the simplifier makes of a call of a closure it knows. Every other call of a closure calls the borrowing entry, and a closure that dies there is dropped after the call. A function whose closures capture nothing has no copy: they are static data, which a drop leaves alone, so it is its own owning entry. Once the module is counted, an owning entry nothing can call is left out: one no call names, and of a type no call through a closure that calls the owning entry has. A closure called in a loop, aslist.foldcalls the function it is given, is then counted neither up nor down at each call. - Runtime helpers borrow. Every helper, the ones that write to stdout and stderr among them, borrows its
operands and returns a value of its own, except
list.cons(which takes both over) and++on lists (which takes the second over, and copies the first’s cells with a reference to each element). Strings handed to the host are borrowed for the call. - Tail calls. An argument passed in a tail call that the caller owns makes the callee own that parameter, so nothing is left to drop after a tail call (see Tail calls).
- Recursive local closures need nothing more: lambda lifting already makes a
reclocal refer to itself through the environment it is called with, never through what it captures, so it cannot capture itself.
Steps 3 and 4 are CoreIrReuse.fs, run on the counted IR, which adds two more nodes: release x; e and an
allocation reusing a token.
- Drop specialisation. An arm that takes apart one object (a list’s first cell, a tag’s cell, a record) and that
does not use the object itself releases it instead of taking a reference to each name and dropping it. The release
checks the count: when it is one, the names keep the fields’ references, the fields no name the arm uses are
dropped, and the block is freed; otherwise the names take references of their own and the count goes down. Each
field’s pattern binds or ignores it, tests it without binding anything (
[0, ...rest],[a], whose rest must be[]), or takes apart an object in turn ([b, a, ...rest],[#some(n), ...rest]):CoreIrReuseSites.takenApartbinds that object to a name of its own (__inner_1), whose reference the outer release takes over, and the inner object is released after it, as a nestedmatchwould (#1547). - Reuse. Every object an arm releases, in each of its scrutinees and nested ones, outer before inner, goes to
the first allocation the arm then makes of a block of its size that an earlier one has not taken (not in a loop or
a guard): the release keeps the
block in a token instead of freeing it, or sets the token to 0 when the object was shared, and the allocation
writes into the block when the token holds one (
__nanyx_list_cons_at,__nanyx_tag_box_at,__nanyx_reuse_object). Mapping over a list held once rewrites its cells in place. When the first such allocation is in some branches of aniformatchand not others, each branch that has one writes into the block, and each that has none frees it first (FreeToken), so the block is used or freed once on every path, as in Perceus. Filtering a list held once keeps the cells of the elements it keeps. withupdates in place.updateRecordtakes its record over, counted after the new values, which may read its fields. Its code computes the new values into locals, then releases the record: when the count was one, it drops the old value of each field on the heap it replaces and stores the new ones into the same block; otherwise the release has taken the count down, and it copies the record, takes a reference to each field on the heap it keeps, and stores the new values into the copy (UpdateRecordinCoreIrEmit.fs).- Exclusivity checks. Reuse covers what the compiler can see; the standard library does the rest at run time, as
Lean 4’s
Arraydoes (#1671). The intrinsic__nanyx_is_exclusivetakes over a reference to a value that is always on the heap, reads its count, gives the reference up, and says whether the count was 1 (an immortal object’s is 0, so never). Taking the reference over is what makes the answer mean something: a caller that uses the value afterwards keeps a reference of its own, which counting adds before the check, inlined or not, and a function that checks a parameter owns it.MList.toListchecks its box this way, and hands over the cells theMListbuilt when it holds the only reference, or copies them.__nanyx_list_set_tailchanges a cell’s tail in place, giving up the old one and taking the new one over: what builds a list front to back, in cells nothing else sees yet (MList.add).__nanyx_list_set_headchanges a cell’s element the same way, which is howMList.setchanges an element of its own cells without copying them. All three are written out where they are used (CoreIrEmit.fs), with no helper. [a, ...rest]is[a] ++ restto the parser. It is lowered to a cell forain front ofrest, rather than a one-element list whose cell++copies, so that it allocates one cell, and can reuse one.
The tests in Features/Memory check that a loop over lists, records, closures and tags runs in constant memory,
that the examples that compile free every block they allocate, and, counting what the allocator hands out, that
mapping over a list, a tuple or a tag’s cell held once allocates nothing, nor does a nested pattern or an arm over
several lists, and nor does with on a record held once.
Memory checks. nanyx run --check-memory (WasmOptions.CheckMemory) compiles the program with an allocator
and counts that check themselves (checkedRuntimeHelpers in WasmRuntime.fs and MemoryChecks in WasmAllocator.fs):
allocandfreecount the blocks still in use. The program’s start function is exported rather than run on instantiation, so the CLI can read the count once the program has finished. A count above 0 fails the run.freesets the low bit of a block’s size word (sizes are multiples of 4), andallocclears it when it hands the block out again. Freeing a marked block, or aretainorreleaseof an object on the heap whose block is marked, writes what went wrong to stderr and exits with 70. A check uses WASIproc_exit, not a trap. The Wasm test host and the CLI both run Wasmtime off the CET shadow stack (CetCompatin both projects), so a trap raised inside either doesn’t crash it.freefills a block after its free-list link with0xDEADBEEF, so a field read after the block was freed is a pointer far outside memory, and following it traps.
Every Wasm test that runs a program runs it as nanyx run --check-memory does, through the CLI’s own code in the
test process (runScriptWith in TestHelpers.fs), and the tests that read the counters compile with the checks too. So a leak, a double free or a use after free in any test program fails that test.
nanyx run --memory runs a program as --check-memory does and then writes what the counters say to stderr
(MemoryReport.cs in the CLI, #1562). The checked allocator keeps
them beside the block counts: the bytes of every block it hands out (bytes_allocated, an i64), the bytes in use and
the most there have been at once (live_bytes, peak_live_bytes), and the highest $heap_ptr has been
(peak_heap, an address, so it counts the string literals and the free lists’ table below the heap). A block’s bytes
are its size word’s, so without the word itself. reused_in_place counts the objects built in a block given up with a
count of one: __nanyx_list_cons_at, __nanyx_tag_box_at and __nanyx_reuse_object count it when the token holds a
block, and UpdateRecord when it updates the record in place. The runner reads the counters however the program
stopped (WasmRunner.runCounting), so the report follows a trap, a failed check or a leak too.
Things that need care
- Closures and contexts. Capturing a value duplicates it, and freeing a closure drops what it captured. Context members that are not known where a function is called are passed as closures and follow the same rules.
- Host calls. Strings handed to the runtime (
dbg, a deferred error) are borrowed for the call. The console host writes a string with WASI’sfd_write, through an iovec that holds its address, and keeps it alive past the call withkeepAlive. - Addresses of strings. A host takes a string’s address with
nanyx/host.memory’saddressOf, to pass to a foreign function, and nothing else may read the string after that: inlined, its last use can come before the call the address is passed to. So counting treats a value made from an address (by arithmetic, a copy, or a call of a function that returns one made from its arguments,CoreIrCounting.inferAddressResults) as a use of the strings it is an address in (addressFlow): an instruction that reads it reads them last, and they live until it is done. A string made in the argument ofaddressOfis a temporary with no name to follow, and is dropped at once.