Garbage collection

Larva has one runtime and several ways to give memory back. A project chooses one with gc: in its .queen file (see Memory for the language side). This page explains what each mode makes the compiler emit and what the runtime does with it. The runtime's data structures (the object header, type descriptors, chunks, the live table) are described in The native runtime; mixing modes in one program is GC domains.

Modes and capabilities

A mode is a GcConfig (Larva.IR/GcConfig): a GcMode and a set of GcCapabilities. The back ends never ask "which mode is this?": they ask whether a capability is present, and each capability turns on one kind of generated code.

GcConfig.ManagesObjects (tracing, counting or regions) decides whether gc T handles exist. In manual mode they do not: objects are raw pointers (*mut T), and the IR type checker treats a raw pointer to a struct or array as a handle, so the whole of System.Core compiles in every mode.

A program to watch

The outputs on this page come from this program, built as an executable. It builds one tree that lives to the end and 200 short-lived trees:

import System;

into namespace Trees
{
	class Node
	{
		public Node? Left;
		public Node? Right;
	}

	Make(i32 depth) : Node
	{
		Node node = new Node();
		if (depth > 0)
		{
			node.Left = Make(depth - 1);
			node.Right = Make(depth - 1);
		}
		return node;
	}

	Count(Node? node) : i32
	{
		if (node is Node n)
			return 1 + Count(n.Left) + Count(n.Right);
		return 0;
	}

	Main()
	{
		Node kept = Make(16);
		i64 total = 0;
		loop (i32 i = 0; i < 200; i++)
			total += Count(Make(12));
		Console.WriteLine($"kept {Count(kept)}, made {total}");
	}
}

The statistics need a runtime built with diagnostics (see Environment variables):

$ LARVA_DIAGNOSTICS=1 larva build -o trees.exe trees.ant
trees.exe (llvm back end, O3, entry trees::Trees.$Module.Main)
$ LARVA_STATS=1 ./trees.exe
kept 131071, made 1638200
larva stats: allocations 1769290, frees 1769277, live heap 7, live gc 6, collections 7 (6 minor), collected 1769277, errors 0
larva stats: minor collections 28.3 ms, major 6.1 ms, barrier calls 55, promoted 171961, pinned 70, retained blocks 1
larva stats: minor phases: roots 0.3 ms, copy 15.0 ms, blocks 15.4 ms; live table 1024
larva stats: remembered+cards part of copy 0.2 ms
larva stats: safepoint calls 5
larva stats: cards 0, slots 344164, remembered 55

1.77 million objects were made; six minor collections promoted 172 thousand of them (mostly the kept tree, which is built before the first collection), and the rest died young and cost nothing to free. The final collection at exit, which LARVA_STATS adds, finds everything dead because kept is no longer used.

Tracing: the generational collector

Tracing is the default, and the most involved mode. Its heap has four parts:

 nursery: 1 GB of reserved address space, 16384 blocks of 64 KB
 +--------+--------+--------+--------+--------+--------+-- - - -
 | ACTIVE | ACTIVE | FREE   |RETAINED| FREE   | UNUSED |
 +--------+--------+--------+--------+--------+--------+-- - - -
     ^ larva_heap.cursor / limit: compiled code bumps through the current block

 old generation (non-moving)
   size-class chunks (256 KB each, 23 classes from 32 to 2048 bytes)
   large objects (> 2048 bytes; LargeInfo + card table before the header)
   RETAINED nursery blocks (they hold pinned survivors)

 heap cells (box, raw memory, globals' cells, exceptions in flight): the `live` table

The design is the one the notes call "Item 10, a nursery that copies": most objects die young, so making them must be as cheap as bumping a pointer and freeing them must cost nothing; the few that survive are copied out once. Copying needs exact knowledge of where handles are, which the type descriptors give for objects. Stacks and registers are not described precisely in executables, so anything they point at is pinned instead of moved.

The nursery

nursery_init reserves 1 GB of address space once (VirtualAlloc with MEM_RESERVE, or mmap with MAP_NORESERVE) and hands it out in 64 KB blocks. On Windows a block is committed the first time it is used. Each block has a NurseryBlock record:

A freed block is zeroed only when it is handed out again (open_block_for clears its dirty bytes). The zeroes then enter the cache right before the program writes the new objects over them, instead of being written cold during the collection.

Objects that never go to the nursery: those over 2048 bytes (NURSERY_OBJECT_MAX), conservative objects (made without a type: they cannot be copied), objects made inside an arena region, and everything in a program where nothing traces.

When a collection is due

The runtime raises larva_poll_pending (see Safepoints) when one of these holds, and the next safepoint collects:

• The blocks handed out since the last minor collection reach the nursery target (times the number of running threads, up to 16).
• 32 MB were allocated outside the nursery (large objects and heap cells).
• A major collection is due: the old generation grew past major_bytes or major_objects.
• GC.Collect() asked for one (gc.request), or stress mode is on.

A collection is minor unless a major one is due, GC.Collect() asked, or generations are off. A major collection always starts with a minor one, so GC.Collect() counts two collections.

After a major collection the next one waits until the old generation doubles (major_bytes = max(2 × survived bytes, 64 MB), major_objects = max(2 × live objects, 2^20)): the marking work per allocated byte stays bounded however large the heap grows.

Roots

Executables do not use precise stack maps. The LLVM back end compiles them with PreciseStackRoots = false, so handles stay in registers across calls instead of being spilled and reloaded around every call (see The LLVM back end). The runtime finds them itself:

All of these are ambiguous: a word is taken as a handle if it points into an object (interior pointers included). The runtime does read the .llvm_st (stack map) sections of every loaded image, but its scan does not use them; the in-process runtime is the one that walks frames precisely.

An ambiguous word may point at a young object. That object cannot be moved (the word might be an integer that happens to look like its address, and rewriting it would change the program), so it is pinned.

A minor collection

collect_minor copies every reachable young object to the old generation, in three steps:

1. Pin. Every ambiguous root (above), plus the words of old conservative objects that were written to (remembered or with dirty cards), is passed to pin_ambiguous. A word that points into an active nursery block finds its object (nursery_object: the block's object starts are found once per collection by walking it, then binary-searched), sets FLAG_PINNED, marks the block, and queues the object for scanning.
2. Copy. The work list starts with the pinned objects, the remembered old objects and the dirty card runs of large objects. Scanning an object visits each handle slot its descriptor lists (each_slot) and calls evacuate: a young, unpinned target is copied to an old slot, the slot is updated to the copy, and the copy goes on the work list (unless its type is a leaf). Young objects with a destructor that nothing reached are evacuated too, and their destructors run after the collection.
3. Blocks. A block with no pinned object goes back to the free list. A block with pinned objects becomes RETAINED: its pinned objects become old in place (age AGE_OLD), the rest of it is dead space until a major collection frees the block.

The copy reads the object's payload size from its type (young_payload), allocates an old slot of the right size class, copies the payload, then replaces the young object's type word with the copy's address. A promotion fills a recycled slot, never a fresh page: the design notes measured promoting into new chunks as twice as slow.

The parallel copy

Since November 2026 a minor collection copies with several threads. The collector starts alone; after it has copied 2048 objects in a collection (WAKE_AFTER) it wakes the helpers, which are parked between collections. There are half as many as processors, at most 4 by default (GC_WORKERS_DEFAULT; the copy waits on memory, so more stop paying) and at most 8 with LARVA_GC_THREADS. A small collection never pays for waking them.

Two threads may reach the same young object through different slots. Both copy it, and a compare-and-exchange on the header's type word decides whose copy wins:

 young object header                        after the winning CAS
 +----------------------+------------+      +----------------------+--------------+
 | type: LarvaType *    | refcount   |  ->  | copy address | 1     | payload size |
 +----------------------+------------+      +----------------------+--------------+
                                              FLAG_FORWARDED set afterwards

 thread A: seen = type; copy = new slot; memcpy; CAS(word, seen, copy|1) == seen  -> wins, *slot = copy
 thread B: seen = type; copy = new slot; memcpy; CAS(word, seen, copy|1) != seen  -> loses:
           its slot goes back to its cache, *slot = (winner's word) & ~1
 later:    seen & 1  ->  *slot = seen & ~1 (already forwarded)

The payload itself is never touched by the forwarding, so a thread that read the type before the exchange still reads the right array length. The count word is free to hold the payload size because a forwarded object's first word may have been an array's length.

Each thread (GcWorker, aligned to 128 bytes: without that, false sharing made 8 threads slower than 1) has:

• its own work stack. When some thread is idle and a stack is 2 deep or more, half of it (the oldest entries, the larger parts of the remaining graph) moves to a shared list; idle threads take up to 16 entries at a time. A large object's dirty cards are split into runs of 64 so threads can share a big array.
• its own cache of old slots per size class. A thread refills it by taking one chunk's whole free list under a lock (O(1)) or by reserving 32 fresh slots and linking them outside the lock. Walking a global free list under the lock had serialized the copy (247 ms of waiting with 8 threads). Unused cached slots stay with the thread for the next collection.

The collection ends when every thread is idle and the shared list is empty. Measured in the design notes on a binary-trees benchmark: 501 to 429 ms, the copy itself 154 to 87 ms with 4 threads. On the small program above the difference is small:

$ LARVA_GC_THREADS=1 LARVA_STATS=1 ./trees.exe
…
larva stats: minor collections 30.3 ms, major 3.9 ms, barrier calls 55, promoted 171962, pinned 69, retained blocks 1
larva stats: minor phases: roots 0.3 ms, copy 18.1 ms, blocks 14.0 ms; live table 1024
$ LARVA_GC_THREADS=4 LARVA_STATS=1 ./trees.exe
…
larva stats: minor collections 26.8 ms, major 5.9 ms, barrier calls 55, promoted 171961, pinned 71, retained blocks 1
larva stats: minor phases: roots 0.3 ms, copy 14.2 ms, blocks 15.1 ms; live table 1024

Write barriers and cards

A minor collection scans only the nursery's reachable objects, so it must also know every old object that points into the nursery. The write barrier records them. After storing a handle into an object, compiled code checks the owner's age byte and calls the runtime only for an old owner:

  %age1 = load volatile i8, ptr %3, align 1
  %old2 = icmp eq i8 %age1, 1
  br i1 %old2, label %barrier3, label %bb3, !prof !1

barrier3:                                         ; preds = %stored
  tail call void @larva_gc_wb(ptr nonnull %alloc, ptr nonnull %alloc.repack23, i64 8)
  br label %bb3

Stores of numbers need no barrier, and young owners (the common case: a constructor filling its new object) take the fast branch. larva_gc_wb then:

• for an ordinary object, sets its age to AGE_REMEMBERED and adds it to remembered; the next minor collection scans it whole and sets it back to AGE_OLD. Since the age is no longer 1, later stores into it do not call the runtime again.
• for a large object, marks the 512-byte card (CARD) that holds the slot in a byte array allocated on first use, and lists the object in carded once (FLAG_CARDED). The minor collection scans only the dirty cards, so storing one element into a million-element array does not make the next collection scan a million slots.

With threads, the age moves from 1 to 2 by an atomic compare-and-exchange, so only the first writer takes the runtime's lock to list the object; card bytes are set by whoever writes them.

The trees program made only 55 barrier calls for 1.77 million objects: nearly every store went into a young node.

Pins

A function that borrows into a gc object (&obj.field, &array[i]) pins the object for the duration of the borrow (larva_pin, then larva_unpin), because a moving collector would otherwise leave the borrow pointing at the old copy. Pins are taken and released by the same thread, most recent first, so each thread keeps them on a stack of its own without a lock; collections treat every pinned handle as an ambiguous root.

A major collection

collect_major runs a minor collection first (marking knows only the old generation), then a non-moving mark-sweep:

1. Mark. Every ambiguous root marks what it points into (consider_ambiguous: a nursery address, a chunk slot, a large object found by binary search in a sorted address index, or a heap cell). The mark stack is drained object by object through the type descriptors; conservative objects and heap cells are scanned word by word. Arrays of numbers (leaf types) are marked without being scanned.
2. Finalizers. Unreachable objects that have a destructor are marked anyway, with everything they reach: they survive this collection, and their destructors run after it. A later collection frees them once they are unreachable again.
3. Sweep. Unmarked heap cells are freed (their owner is gone); unmarked large objects and chunk slots are freed; retained nursery blocks are freed when nothing in them is marked. Survivors get AGE_OLD, every card table is cleared, and the remembered lists start over.

Objects in an open arena region belong to the region, not to the collector: the sweep skips them.

Nursery sizing

The number of blocks between minor collections adapts to what survives. It starts at 128 blocks (8 MB):

The asymmetry is deliberate. An earlier policy shrank the nursery as soon as one collection was quiet. A program building a large tree then collected in the middle of the construction and promoted half-built trees that would have died soon after: 278 minor collections and 3.9 million promotions on binary trees against 42 and 1.3 million with the current policy (680 to 555 ms). LARVA_GC_NURSERY=n sets the starting target:

$ LARVA_GC_NURSERY=1024 LARVA_STATS=1 ./trees.exe
kept 131071, made 1638200
larva stats: allocations 1769290, frees 1769277, live heap 7, live gc 6, collections 3 (2 minor), collected 1769277, errors 0
larva stats: minor collections 22.4 ms, major 11.0 ms, barrier calls 12, promoted 139246, pinned 20, retained blocks 1
…

Ideas the notes measured and dropped (each lost on the whole benchmark sample): ageing survivors in the nursery before promoting them (strings faster, trees and lists slower), adaptive tenuring, promoting with a cursor in fresh chunks (twice as slow), and prefetching free slots or child headers during the copy. Profiles put the remaining cost in memory traffic: loading the young object's header (a cache miss) and zeroing nursery blocks.

Without generations

generational() is false under LARVA_GC_GENERATIONS=0, a fixed LARVA_GC_THRESHOLD, quarantine, a custom collector, or once any arena region was used. Every collection is then a major one, due when as many objects were allocated as were alive after the last one (at least 4096), or when 32 MB and twice the live bytes were allocated outside the nursery. The same program then spends four times as long collecting:

$ LARVA_GC_GENERATIONS=0 LARVA_STATS=1 ./trees.exe
…
larva stats: allocations 1769290, frees 1769277, live heap 7, live gc 6, collections 11 (0 minor), collected 1769277, errors 0
larva stats: minor collections 0.0 ms, major 122.2 ms, barrier calls 884610, promoted 0, pinned 0, retained blocks 0

(With no nursery, objects are old from birth, so every store into them goes through the barrier's runtime call.)

Reference counting

With gc: refcount every object counts its owners in the header's refcount word, and dies the moment the count reaches zero. No collection ever runs: the program has no safepoints and the entry info's bit 17 tells the runtime that nothing traces, so it turns the nursery off and every object is born old, in a chunk slot or a large block.

$ LARVA_STATS=1 ./bin/Trees.exe
kept 131071, made 1638200
larva stats: allocations 1769290, frees 1769279, live heap 7, live gc 4, collections 0 (0 minor), collected 0, errors 0
…

(The tree program as a project with gc: refcount in its BUILD chunk. Pure reference counting skips the final collection LARVA_STATS normally runs, so "live gc 4" is exactly what the counts kept: library statics.)

Counting inline. In executables, the LLVM back end emits retain as a null check and an add on the i32 at handle - 8, and release as a null check, a subtract, and a call to larva_rc_dead only when the count reaches zero. In a program that mixes domains, both also check the domain byte's DOMAIN_UNCOUNTED bit. In the in-process runtime both are calls.

Death releases what the object holds. larva_rc_dead pushes the object on a list and drains it: each dying object's handle slots, from its type descriptor, are released (rc_drop_slot), and children whose count reaches zero join the list. A long chain dies in a loop, not a deep recursion. An object with a destructor gets one temporary reference for the call: the destructor borrows the object, and it dies afterwards unless the destructor stored it somewhere. The x64 back end emits type descriptors in this mode too (it normally does not), so that deaths know what to release.

Handles at +0. Native code does not pay a retain and a release for every argument. The caller lends a gc argument: a plain local is passed as it is (and released right after the call if that was its last use), anything else is retained around the call. The callee's parameters are Borrowed: it takes its own reference only if it stores the handle. The LLVM back end also skips counting for a field read used only within its block, when nothing in between can write memory, release, or call (FieldBorrows). The VM and WebAssembly still pass handles at +1.

These changes took the design notes' benchmark sample under refcount from 87.8 s to about 3.3 s (tracing: about 1.9 s). The 87.8 s came from three faults since fixed: every retain searched the nursery block for the object, deaths released nothing (368 MB at the peak, now 6 MB), and LLVM spilled every live handle and flag before every call in large functions with a cleanup handler (now kept in the frame with llvm.localescape from 24 owning locals).

Cycles are not collected. Two objects that refer to each other keep each other alive forever. There is no cycle detector: break cycles by setting a field to null.

delete does nothing under reference counting: the count decides.

Arenas

With gc: arena, region { … } opens a region. The lowering emits region_enter(rN) at the start and makes the block's exits (return, break, continue, the end) run region_exit(rN), like a finally.

In the runtime, larva_region_enter pushes the region number and turns inline allocation off; every object gc_allocate makes while a region is open gets FLAG_REGION and an entry in region_of (object → region + 1). larva_region_exit pops the region and frees everything in it: first it runs every destructor (all the region's objects still exist while they run), then it frees the objects. An exception leaving a function closes the regions it opened (larva_region_unwind to the depth saved at the function's entry).

What stops an object from escaping its region is static. The IR's RegionChecker tags every value made inside a region and rejects storing it anywhere that outlives the region (a field of an older object, a global, the result, a thrown exception) with a RegionEscape error. Each function of an arena program gets a region parameter 'a for its caller's region (HirLowerer applies ArenaSignature), so objects flow through arguments, fields and results as in the other modes, and only what a region { } itself allocates is checked. Under arenas, string literals are not cached in globals: a literal first reached inside a region would die with it.

Objects made outside any region are never freed: there is no collector in this mode. With the tree loop's body wrapped in region { … }:

$ LARVA_STATS=1 ./bin/Trees.exe
kept 131071, made 1638200
larva stats: allocations 1769288, frees 1638200, live heap 7, live gc 131081, collections 0 (0 minor), collected 0, errors 0
…

Every node made inside a region was freed (1,638,200), and the kept tree's 131,071 nodes, made outside, are still there.

Manual memory

With gc: manual, objects are raw memory. delete obj; (in unsafe code) calls the object's destructor, dispatched to its real class, then free, which becomes larva_free. Nothing else frees anything. larva_free checks that the address is a heap cell or raw block it knows (live) and counts anything else as an error instead of crashing; errors in the statistics shows double frees and frees of unknown pointers.

When the code freeing a block counts references (a manual library in a program with a reference-counted domain), the back ends first release every gc handle the freed struct holds (HandleSlots), so freeing a container lets go of its counted contents.

Custom collectors

gc: custom is meant for a collector the project writes, named by gc.collector in BUILD. Not usable yet: System.Core has no System.IGarbageCollector interface and no GC.Install, and larva build builds a custom project with the default tracing collector. The .queen reader keeps the setting (QueenProject.CustomGc, GcCollector) and reports QN125 when gc.collector is missing, but nothing consumes it.

What exists is the runtime side. Intrinsic 33, gc.custom(allocate, release, poll), calls larva_gc_custom with three function addresses:

While a hook runs (in_custom), objects it allocates take the runtime's own memory and no collection starts. With a custom collector installed the nursery and generations are off. Null functions put the runtime's allocator back; objects keep their memory's owner. The C runtime and the in-process runtime implement the hooks; the VM and WebAssembly ignore them.

Destructors in each mode

A class's destroy() becomes a synthetic $destroy function, and new passes it to the allocation as the object's finalizer (larva_gc_finalizer). When it runs depends on the mode:

This program runs one destructor in a function's local, one in a region, and one before an explicit delete:

import System;

into namespace Destructors
{
	class Res
	{
		i32 id;

		public:
			new(i32 id) { this.id = id; }

			destroy() { Console.WriteLine($"destroy {id}"); }
	}

	Use(i32 id) : i32
	{
		Res r = new Res(id);
		return id;
	}

	Main()
	{
		Use(1);
		Console.WriteLine("after Use(1)");
		region
		{
			Res inside = new Res(2);
			Console.WriteLine("leaving the region");
		}
		Console.WriteLine("after the region");
		GC.Collect();
		Res filler = new Res(3);
		Console.WriteLine($"collections: {GC.CollectionCount()}");
		unsafe { delete filler; }
		Console.WriteLine("end of Main");
	}
}

Built as a project four times, with gc: set to each mode:

What each column shows:

• Tracing. region is an ordinary block (no Regions capability). GC.Collect() makes the next safepoint run a minor and then a major collection (hence "collections: 2"), and its destructors run right after: object 2 was unreachable. Object 1 was not destroyed: a word of the stack still pointed at it, and conservative roots keep such objects. Nothing runs at exit.
• Reference counting. Object 1 dies when Use returns. Locals are released when their function ends, so inside (2) and filler (3) die at the end of Main; delete changes nothing.
• Arena. Object 2 dies with its region. 1 and 3 were made outside regions and are never freed.
• Manual. Only delete frees, so only 3 is destroyed.

Statistics

LARVA_STATS=1 (with a runtime built with LARVA_DIAGNOSTICS=1) prints six lines at exit, after a final collection unless the program only counts references:

For finding collector bugs rather than measuring: LARVA_GC_VERIFY=1 checks after every collection that no old object points at a young or dead one, LARVA_GC_STRESS=1 collects at every safepoint, and LARVA_GC_QUARANTINE=1 poisons collected memory and never reuses it. The full list is in The native runtime.