The native runtime

Compiled Larva code does not stand alone. It calls a small runtime for everything that needs the operating system or the collector: allocating objects, collecting them, throwing, printing, files, sockets, threads, and the arithmetic of number types the processor lacks. This page describes that runtime. The collectors themselves have their own page, Garbage collection, and the way several of them share one program is in GC domains.

Four runtimes, one interface

Every back end calls the same larva_* functions with the same C signatures. Four implementations answer them:

The C runtime is the reference: the other three copy its object layout (the same 16-byte header, the same type descriptors) so that the same compiled code runs on all of them. The rest of this page is about larva_rt.c unless it says otherwise.

How the runtime gets into a program

The C source is embedded in larva's Larva.Native library as a resource. It is never shipped as a separate file and never precompiled: the first link that needs it compiles it with the system's C compiler and keeps the object in the per-user toolchain cache (%LOCALAPPDATA%\Larva\toolchain on Windows), named by a hash of the source, the compiler flags and the compiler's environment (Toolchain.CachedRuntime). Later links only run the linker. Changing the runtime, or a flag such as LARVA_DIAGNOSTICS, makes a new hash and a new compile.

The same file builds three ways:

LARVA_WITH_CRT=1 at build time compiles the Windows runtime with the C library again and links the UCRT, to compare against the default. LARVA_DIAGNOSTICS=1 at build time compiles in the diagnostic switches (see Environment variables).

A hello world shows what the default build links. Its import table, read from the PE file, names two libraries:

$ larva build -o hello.exe hello.ant
hello.exe (llvm back end, O3, entry hello::Hello.$Module.Main)
$ ./hello.exe
Hello from Larva!

The file is 68,096 bytes, and its sections are .text, .rdata, .data, .pdata, .CRT and .reloc.

Start-up and exit

A Windows executable's entry point is larva_crt_start, in the runtime. It splits the command line with the C library's rules (quotes, 2n and 2n+1 backslashes before a quote, "" inside quotes), converts each word to UTF-8 and calls main, which calls program_main. With the shared runtime, a tiny generated start file calls larva_run_main in larva_rt.dll instead; on POSIX the C library's own main does it.

program_main does the same everywhere:

1. runtime_settings() reads the environment (once, before any Larva code runs) and installs report_crash as the unhandled-exception filter on Windows.
2. It calls larva_entry_info(), a function the linker generates (ExecutableEntry.AddWrappers), and decodes it.
3. It parses up to four command-line integers (or true/false) when the entry takes arguments.
4. It calls larva_entry (or larva_entry_f64 for a float result) inside the exception guard.
5. It prints the result by its kind, runs a final collection and prints statistics when LARVA_STATS is on, and returns the exit code.

The entry's info word:

Exit codes the runtime itself produces:

The object header

Every gc object has a 16-byte header just before its payload. A handle (the value a Larva variable holds) is the address of the payload, never of the header, so field offsets in compiled code start at 0 and the header is at negative offsets.

 handle - 16                                   handle - 1   handle (payload)
     |                                                 |       |
     v                                                 v       v
     +--------------------------+------------+----+-----+------+-----+--------------
     | type: const LarvaType *  | refcount   |mark|flags|domain| age | payload ...
     | (8 bytes)                | (i32)      | i8 | u8  | i8   | u8  |
     +--------------------------+------------+----+-----+------+-----+--------------
     offset 0                   8            12   13    14     15    16

The flags byte:

  bit:   7     6        5          4        3        2           1        0
       +---+--------+-----------+--------+--------+-----------+--------+-------+
       | - | CUSTOM | FORWARDED | PINNED | REGION | FINALIZER | CARDED | LARGE |
       +---+--------+-----------+--------+--------+-----------+--------+-------+

The domain byte:

  bit:    7 6          5   4   3   2   1   0
       +------+-----------+-----------------------+
       |  0   | UNCOUNTED |  domain number (0-63)  |
       +------+-----------+-----------------------+
  0xFF (all bits set) = SLOT_FREE

DOMAIN_UNCOUNTED (0x40) tells larva_gc_retain and larva_gc_release to leave the object alone: it belongs to a domain that does not count references, in a program that mixes domains. In a program with one GC the byte is always 0. larva_gc_domain (the gc.domain intrinsic) returns the low six bits.

New objects get their header in one of two ways. The runtime writes it in gc_allocate and old_allocate. Compiled code allocating inline in the nursery writes it itself: the type word, then the 8-byte word at offset 8 as the constant 1 (count 1, every other byte 0), or 1 | domain << 48 in a program that mixes domains. The domain byte comes from bits 8–15 of the type descriptor's flags, which the back end set.

Type descriptors

The collector knows where each object keeps its handles because the back end emits a constant descriptor per concrete type (LlvmCodegen.Descriptor, from Layouts.PointerMap):

typedef struct LarvaType {
    uint32_t size;      /* payload size; for an array: the array header (length and padding) */
    uint32_t stride;    /* an array's element size */
    uint32_t flags;     /* TYPE_* below; bits 8..15: the GC domain */
    uint16_t handles;   /* how many handle offsets, first in `offsets` */
    uint16_t cells;     /* how many owned heap-cell (`box`) offsets, after them */
    uint32_t offsets[];
} LarvaType;

Here is what the LLVM back end emitted for a small program with a Node class holding two Node? fields, together with its strings and arrays (from LARVA_DUMP, which writes the whole program's optimized LLVM IR):

@larva.type.0 = private constant { i32, i32, i32, i16, i16, [0 x i32] } { i32 32, i32 1, i32 12, i16 0, i16 0, [0 x i32] zeroinitializer }, align 8
@larva.type.1 = private constant { i32, i32, i32, i16, i16, [2 x i32] } { i32 32, i32 0, i32 0, i16 2, i16 0, [2 x i32] [i32 16, i32 24] }, align 8
@larva.type.2 = private constant { i32, i32, i32, i16, i16, [0 x i32] } { i32 8, i32 1, i32 5, i16 0, i16 0, [0 x i32] zeroinitializer }, align 8
@larva.type.3 = private constant { i32, i32, i32, i16, i16, [0 x i32] } { i32 8, i32 4, i32 5, i16 0, i16 0, [0 x i32] zeroinitializer }, align 8

• type.1 is Node: 32 bytes of payload, two handles at offsets 16 and 24.
• type.0 is String<u8> (the type str names): flags 12 = TRAILING | LEAF, the units start at 32, one byte each.
• type.2 is u8[] and type.3 is i32[]: flags 5 = ARRAY | LEAF, an 8-byte header (the length), elements of 1 and 4 bytes.

Code that gives no type (larva_gc_new, larva_gc_new_in, larva_array_new) gets a descriptor the runtime makes and caches (untyped): conservative for objects, leaf or conservative for arrays.

Objects, arrays and strings in memory

Every class instance starts with the fields of Larva.Object, which the lowering declares link-once (HirLowerer): $class, an i32 class id, and $vt, the pointer to the class's vtable. The class's own fields follow:

 Node payload (32 bytes)
 +---------+---------+-----------------+-----------------+-----------------+
 | $class  | (pad)   | $vt             | Left: Node?     | Right: Node?    |
 | i32     |         | ptr             | handle          | handle          |
 +---------+---------+-----------------+-----------------+-----------------+
 0         4         8                 16                24                32

An array is one object: its length (i64) in the first word, the elements after the array header.

 i32[] of 3 elements (payload 8 + 3 x 4 bytes)
 +--------------------+--------+--------+--------+
 | length = 3 (i64)   | [0]    | [1]    | [2]    |
 +--------------------+--------+--------+--------+
 0                    8        12       16

A string is also one object. String<T> in System.Core is a final class whose last field is fixed T[] units, an array kept inside the object: one allocation per string, no separate buffer.

 String<u8> "kept" (payload 32 + 4 bytes)
 +---------+-------+---------+------------------+------------------+---+---+---+---+
 | $class  | (pad) | $vt     | hash (u64,       | length = 4       | k | e | p | t |
 |         |       |         |  0 until needed) | (i64)            |   |   |   |   |
 +---------+-------+---------+------------------+------------------+---+---+---+---+
 0         4       8         16                 24                 32

str is String<u8>, UTF-8. String literals are not objects until used: the compiler emits their bytes as constant data with the same "length, then bytes" shape (c"\05\00\00\00\00\00\00\00kept " above), and the lowering caches the object it makes from them in a global.

Some memory is not a gc object at all:

live is an open-addressing hash table from address to size and kind (Table, keys 0 and 1 reserved for empty and removed). Large gc objects and memory from a custom collector are listed there too, as KIND_GC; small old objects and nursery objects are not (they are found from their address, see below).

Allocation paths

 new Node()                                         compiled code
     |
     |  larva_heap.fast && cursor + total <= limit ?
     |---- yes --> bump the cursor, write the header        (no call)
     |
     v  no
 larva_gc_alloc(type, size) / larva_gc_array(type, length)          runtime
     |
     |-- nursery usable, typed, total <= 2048 ---> next 64 KB nursery block
     |
     v
 old_allocate
     |-- total <= 2048 ----------> small_allocate: a slot of a size-class chunk
     |-- custom collector -------> its allocate() function   (FLAG_CUSTOM)
     |-- otherwise --------------> a large block: LargeInfo + header + payload

The inline path. larva_heap is a struct the runtime exports with a fixed layout that compiled code knows: { i32 fast, i32 unused, char *cursor, char *limit }. When fast is set and the object (header included, rounded to 16 bytes) fits before limit, the code takes it from the cursor. The nursery's memory is already zero, so nothing is cleared. This is the LLVM back end's code for new Node():

  %heap = load ptr, ptr @__imp_larva_heap, align 8
  %heap.fast = load volatile i32, ptr %heap, align 4
  %10 = getelementptr i8, ptr %heap, i64 8
  %nursery.cursor = load volatile ptr, ptr %10, align 8
  %11 = getelementptr i8, ptr %heap, i64 16
  %nursery.limit = load volatile ptr, ptr %11, align 8
  %nursery.next = getelementptr i8, ptr %nursery.cursor, i64 48
  %12 = icmp ule ptr %nursery.next, %nursery.limit
  %13 = icmp ne i32 %heap.fast, 0
  %14 = icmp ne ptr %nursery.cursor, null
  %15 = and i1 %13, %14
  %alloc.fast = and i1 %15, %12
  br i1 %alloc.fast, label %alloc.inline, label %alloc.call, !prof !0

alloc.inline:                                     ; preds = %"larva.trees2::Trees.Node.$vtable.exit"
  store volatile ptr %nursery.next, ptr %10, align 8
  store volatile ptr @larva.type.1, ptr %nursery.cursor, align 8
  %16 = getelementptr i8, ptr %nursery.cursor, i64 8
  store volatile i64 1, ptr %16, align 8
  %17 = getelementptr i8, ptr %nursery.cursor, i64 16
  br label %alloc.done

alloc.call:                                       ; preds = %"larva.trees2::Trees.Node.$vtable.exit"
  %18 = tail call ptr @larva_gc_alloc(ptr nonnull @larva.type.1, i64 32)
  br label %alloc.done

48 bytes is the 16-byte header and the 32-byte payload. The runtime clears fast whenever inline allocation must stop: inside an arena region, with a custom collector, under the diagnostic switches, without generations, and while several threads run (each thread then has its own block, see Threads).

Small old objects live in chunks of 256 KB (CHUNK), aligned to their size, reserved 64 at a time (16 MB). Each chunk serves one of 23 size classes (header included):

32 48 64 80 96 112 128 160 192 224 256 320 384 448 512 640 768 896 1024 1280 1536 1792 2048

A slot comes from the class's free list, else from the bump pointer of its newest chunk. Free slots are linked through their first word and kept per chunk: a class lists its chunks that have some (partial_chunks), and whoever needs slots takes one chunk's whole list in O(1). Because chunks are aligned, the collector finds the chunk of any address by masking it, and the slot by dividing the offset (small_object); a one-byte-per-chunk map (chunk_map) says which aligned addresses really are chunks.

Large objects (over 2048 bytes) get a block of their own from the aligned allocator, with a LargeInfo (card table, payload size) before the header and an entry in live. Large arrays are where card marking pays (see Garbage collection).

Objects born old. Objects larger than 2048 bytes, objects without a type (conservative), objects made inside an arena region and objects of a program where nothing traces skip the nursery.

Exceptions

On Windows, Larva exceptions are structured exceptions with code LARVA_EXCEPTION, 0xE04C5641 (E0 and the letters LVA). The thrown value travels in a cell from larva_exception_cell; the exception record carries it and the thrown type's id as parameters, and catch filters compare type ids. Compiled code uses the system's __C_specific_handler (from ntdll.dll) and .pdata unwind tables like any C code.

RaiseException enters the kernel before the dispatcher even looks for a handler, and that was most of the cost of a throw (about 1.2 µs). So the LLVM back end throws through larva_raise, which has RaiseException's signature but does the first pass itself, in user mode:

1. It captures the context and walks the frames with RtlLookupFunctionEntry and RtlVirtualUnwind. A frame with no function entry is a leaf: its return address is at the top of the stack.
2. For a frame whose handler is __C_specific_handler (Larva code, or the runtime's own __try), it reads the scope table and asks each filter whose range covers the frame's address, as that handler would.
3. The first filter that accepts gets the exception through RtlUnwindEx, which runs the cleanups of the frames in between and lands in the handler, exactly as after RaiseException.
4. A frame with another handler, a filter that asks to continue, or no handler at all: it calls RaiseException and lets the system do everything.

The design notes measured a throw-heavy section going from about 240 to 145 ms. The x64 back end and the in-process runtime still call RaiseException directly (in NativeRuntime, the symbol larva_raise is bound to kernel32's RaiseException).

On POSIX and WebAssembly there is no unwinder: a throw stores the payload in larva_exception and its type id in larva_exception_type, and the code checks the flag after every call (see The LLVM back end). An exception that leaves a frame closes the arena regions it opened: larva_region_depth is saved on entry and larva_region_unwind(depth) runs on the way out.

What reaches the entry uncaught is reported by the runtime:

import System;

into namespace Fail
{
	Main()
	{
		throw new InvalidOperationError("nobody catches this");
	}
}

$ larva build -o throw.exe throw.ant
throw.exe (llvm back end, O3, entry throw::Fail.$Module.Main)
$ ./throw.exe
larva: unhandled exception (type id 461533486)

Errors that cannot be caught are panics. larva_panic(code, a, b) flushes standard output, prints one line and exits with 101:

This program catches an exception, then indexes past the end of an array:

import System;

into namespace Fail
{
	Main()
	{
		i32[] numbers = new i32[3];
		try
		{
			throw new InvalidOperationError("caught here");
		}
		catch (InvalidOperationError e)
		{
			Console.WriteLine($"caught: {e.Message}");
		}
		i32 i = numbers.Length;
		Console.WriteLine(numbers[i]);
	}
}

$ larva build -o fail.exe fail.ant
fail.exe (llvm back end, O3, entry fail::Fail.$Module.Main)
$ ./fail.exe
caught: caught here
larva panic: index 3 out of bounds for length 3

A hardware fault (an access violation, say) goes to report_crash, which prints the exception code, the registers and up to 24 frames as image+offset. With LARVA_MAP=1 at build time the linker also writes a .map file that turns those offsets into function names.

Threads

System.Threading threads are real operating-system threads running in parallel. Each has a LarvaThread record, aligned to a cache line of its own:

While only one thread exists, the runtime takes no locks and compiled code allocates inline from larva_heap. The first larva_thread_start turns threading on (threads_init): the runtime's shared state is guarded from then on by rt_lock (re-entrant), each thread allocates young objects from a block of its own through the runtime (leave_shared_heap clears larva_heap.fast), and when the program is back to one thread the main thread adopts the shared heap again.

A collection stops the world. The thread whose safepoint finds a collection due sets stop_world, raises larva_poll_pending, and waits on world_stopped until running_count reaches 0. Every other thread stops either at a safepoint (STOP_HERE, which saves its registers and stack pointer in its record and waits on world_resumed) or because it already waits in the runtime: sleeping, joining, taking a lock, waiting on a condition, reading input, a socket call. Those waits are wrapped in BLOCKING_ENTER()/blocking_leave(), which save the registers and count the thread as stopped, so a collection never waits for a thread that is waiting for something else. Locks are always taken in one order, rt_lock before world_lock.

For every thread to reach a safepoint, a program that starts threads polls in every loop, not only in loops that allocate (Safepoints.Threaded). A thread that throws past its function stops the whole program (larva: unhandled exception in thread N, exit code 1).

The in-process runtime (NativeRuntime.Threads) is different on purpose: its tables are plain managed collections, not safe to share, so its threads take turns. A ticket lock gives the turn in arrival order; a thread gives it up at a safepoint when another waits, and while it waits in the runtime. No collection runs while more than one thread is alive there.

Safepoints and polls

A collection can only start at a safepoint. Compiled code polls at the header of every loop that allocates and at the entry of functions that allocate or may recurse (Larva.IR.Analysis.Safepoints). A poll is a load and a branch on larva_poll_pending; the call to larva_poll is on the cold path:

  %poll.flag.address = load ptr, ptr @__imp_larva_poll_pending, align 8
  %poll.flag = load volatile i32, ptr %poll.flag.address, align 4
  %poll.due.not = icmp eq i32 %poll.flag, 0
  br i1 %poll.due.not, label %polled, label %poll, !prof !0

The runtime keeps the flag equal to "something may be due" (update_poll_pending): the world is stopping, a collection was requested, stress mode, a custom collector to ask, or enough allocated. The allocator raises it the moment the nursery target is reached, so the poll costs nothing until then. The in-process runtime keeps its flag permanently set: every safepoint asks.

Numbers the processor does not have

Several number types need code from the runtime:

The software floats work on 13 64-bit words of precision (FL_WORDS, 832 bits: an f256 division needs 3·236 + 5), round to nearest with ties to even, and return the canonical quiet NaN. larva_float_conv names a type by its width (12 bits), plus 0x1000 for signed and 0x2000 for float. The in-process runtime has the same routines (NativeRuntime.SoftFloat, NativeRuntime.WideFloat), computed by the same SoftFloat code the VM uses, so every back end gives the same bits.

Intrinsics

Library code reaches the runtime through intrinsics: extern("gc.request") Request(); in System.Core's GC class, for example. Each intrinsic has a number, a name, an IR signature and a C symbol, declared once in Larva.IR/Intrinsics and implemented by every runtime:

Allocation, counting, barriers, pins, regions, polls, throws and panics are not intrinsics: the back ends call those entry points directly (larva_gc_alloc, larva_gc_retain, larva_gc_wb, larva_pin, larva_region_enter, larva_poll, larva_raise, larva_panic and the rest).

One rule shapes the text intrinsics: the runtime never allocates the program's objects. read.line reads a line into a runtime buffer and returns its length; the library then makes a string of that length and fetches the units one by one with read.unit. Command-line arguments, folder listings, environment values and formatted floats work the same way. The runtime therefore needs to know nothing about String<T>, and every GC mode (and every domain) gets its strings allocated by its own code.

Streams and sockets share one numbering of handles: a socket handle has bit 40 set (SOCKET_TAG), a child process bit 41 (PROC_TAG), so stream.read, stream.write and stream.close work on connections as they are.

The runtime without a C library

Since the design notes' "Item 11", Windows executables and Larva DLLs link no C library at all: they are linked with /NODEFAULTLIB, an entry point of their own (/ENTRY:larva_crt_start), and only kernel32.lib, ws2_32.lib and an import library for a handful of ntdll.dll functions that larva makes once from a .def file (the SDK's ntdll.lib leaves them out). What the runtime used to take from the C library is now in larva_rt.c, under the same names (macros), on top of Windows:

Cold code (start-up, the command line, files and folders, numbers as text, stack maps, interop, starting threads, crash reports) is compiled for size between #pragma optimize("s", on) and ("", on). The collector, allocation, polls, barriers, copies and writes stay compiled for speed: compiled for size, %.15g was 50% slower.

The design notes recorded the effect. The C library itself weighed little (about 3 KB), so a hello world stayed near 66 KB; the runtime's own code is about 40 KB (a generational copying collector, threads, verification, statistics, crash reports). Leaving the diagnostics out by default and compiling cold code for size brought a hello world to 57.9 KB at the time. Start-up went from 22.1 ms with the C library to 19.7 ms (no ucrtbase.dll to load and initialize), and the 19 executable benchmarks took the same time either way.

Environment variables

The runtime reads its settings once, at start (runtime_settings, or DllMain for a Larva DLL). Except for the program's own env.get, everything it reads exists only in a runtime built with diagnostics: Windows programs built with LARVA_DIAGNOSTICS=1, the shared runtime, and every POSIX program. In a normal Windows build these switches are compile-time constants and their code is gone, so setting them changes nothing.

Variables read when building, not when running:

Elsewhere: the VM prints its own counters when larva run of a module sees LARVA_STATS=1, and the WebAssembly loader reads LARVA_GC_STRESS and LARVA_GC_THRESHOLD from Node's environment.

The switches need a rebuild to take effect, and larva build of a project is incremental: after building once without diagnostics, delete the project's bin folder (or use larva run --rebuild) before building with LARVA_DIAGNOSTICS=1.

With the tree program of Garbage collection, built without diagnostics:

$ larva build -o plain.exe trees.ant
plain.exe (llvm back end, O3, entry plain::Trees.$Module.Main)
$ LARVA_STATS=1 ./plain.exe
kept 131071, made 1638200

The same program built with LARVA_DIAGNOSTICS=1 prints its counters (and is 78,336 bytes instead of 72,704):

$ 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 24.0 ms, major 5.4 ms, barrier calls 55, promoted 171967, pinned 72, retained blocks 1
larva stats: minor phases: roots 0.4 ms, copy 11.6 ms, blocks 14.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 344180, remembered 55

The in-process runtime

Larva.Native.NativeRuntime implements the same C ABI inside larva's own process, for machine code compiled into memory. NativeRuntime.Symbols maps each larva_* name to an unmanaged entry point, and the in-memory back ends bind their external declarations through it. It follows the C runtime's layouts (the 16-byte header with the count at +8, the domain byte at -2 from the payload, type descriptors, trailing arrays) but is simpler where speed matters less:

Its state is per process and static, so a host that runs one program after another must clear it in between. NativeRuntime.Reset() frees every block still in live (except memory that came from a custom collector), clears the tables, pins, regions and finalizers, forgets any custom collector's function pointers, closes open streams, zeroes the counters, turns stress off and resets the threads. larva bind --profile, which runs a binding profile as machine code in larva's own process, calls it before and after the run. Forgetting it after a program that installed a custom collector is fatal: the next program would call function pointers into code that no longer exists.