GC domains

Every project chooses its memory management with gc: in its .queen file. A GC domain is what lets a program use libraries that chose differently: a tracing program can call a reference-counted library, and each side keeps its own rules. This page explains how. The collectors themselves are described in Garbage collection and the object header in The native runtime.

The goal

The design notes state it plainly: each project picks its GC, projects with the same GC share it, and projects with different GCs still call each other and use each other's code. The per-mode work (tracing, counting, arenas, manual memory, destructors in each) was the precondition; mixing is the point.

Until the domains work, the IR linker enforced one GC per program. Every object file records the GcConfig it was checked for, and a module checked for another mode was rejected with "module … was checked for GC mode …, but the program uses …". That error still exists (Linker.CheckModules), for links that do not ask for mixing (LinkOptions.MixedDomains).

Vocabulary

The central decision: the domain is in the object

There were two ways to know which collector owns an object.

• In the type (gc<D> T): every signature that receives another domain's objects would change, System's generic code would be multiplied per domain, and a List<T> could not hold objects of two domains. Rejected.
• In the object: one byte of the header says which domain the object belongs to. The handle type stays gc T everywhere; what changes is the operation at the boundary, which reads the byte. This is the same scheme as the generational write barrier, which already reads the age byte on every handle store. Chosen.

The byte is the header's byte 14, domain (it used to be custom, which distinguished memory from a custom collector; that moved to FLAG_CUSTOM in the flags byte):

 handle - 16                          handle - 2  handle - 1
 +---------------+----------+------+-------+--------+-----+--------------
 | type          | refcount | mark | flags | domain | age | payload ...
 +---------------+----------+------+-------+--------+-----+--------------

 domain byte:   bit 7    bit 6        bits 5..0
              +-------+-----------+------------------+
              |   0   | UNCOUNTED | domain (0 to 63) |
              +-------+-----------+------------------+
              0xFF: SLOT_FREE (a free chunk slot, not an object)

IrModule.DomainByte(domain, program) computes what code of a domain writes there: the domain number, plus UncountedDomain (0x40) when that domain does not count references. In a program with one GC it is always 0, so every single-GC path is unchanged.

The byte reaches each new object by the route that object takes:

Intrinsic 90, gc.domain(*mut u8) : i64 (larva_gc_domain), returns the low six bits. It reads the header blindly: on a pointer that is not a gc object it reads whatever is there.

How a mixed program is built

larva build of a project makes a mixed program when a project in its DEPS (proj:) says a different gc: than the root. Dependencies with the same GC are compiled into the program as before; the others become external dependencies (SourceBuild, "a dependency built for another GC is not compiled into the program"):

 App.queen (gc: default)  ──proj──>  Counter.queen (gc: refcount)

 Counter (external)                         App (the program, domain 0)
 ─────────────────                          ───────────────────────────
 sources + System.Core                      sources, compiled against
   │ compile (language pack)                  [System.Core, Counter.lva]
   ▼                                          │
 Counter.lva ──────── reference ─────────────>│
   │ HIR link with the core                   │ HIR link [core, Counter, App]
   ▼                                          ▼
 lower with gc RefCount, ExportAll          lower with gc Default,
   │                                          ExternalAssemblies = {Counter}
   ▼                                          │ (crossable calls become imports)
 IR object (its own System) ──┐               ▼
                              └──> Linker.Link([App, Counter], MixedDomains)
                                         │
                                         ▼  one IR program, Domains = [Default, RefCount]
                                   back end + runtime

DomainLibrary builds each external: it compiles the dependency's sources (and those of its own dependencies) against System.Core, links them with the core at the HIR level, lowers the result for the dependency's GC with ExportAll (every member is exported, so the program's declarations resolve), checks it for that GC, and returns the IR object and the .lva the program's frontend compiles against. --timings shows the step under the dependency's name and mode:

$ larva build --timings -o app.exe
app.exe (llvm back end, O3, entry app::App.$Module.Main)
timings: System.Core (compiled library) 81 ms, Counter (RefCount) 3683 ms, frontend 66 ms, HIR link 7 ms, lowering 69 ms, IR checks 136 ms, IR link 367 ms, native (llvm) 4511 ms; total 8935 ms

The program is lowered with LoweringOptions.ExternalAssemblies. HirAssembly.Origins, filled by HirLinker while it numbers types, tells the lowering which assembly each type came from. After lowering the bodies, HirLowerer.ApplyLinkage turns the methods of external types that may cross (below) into declarations: Linkage.Import, the symbol Counter::name, no body. The IR linker binds them to the external object's exports. Everything else of an external type that the program's code mentions would be compiled locally, in the program's domain; the frontend makes sure the program cannot use such members (see The crossing diagnostic).

The linker

With MixedDomains, CheckModules starts domain 0 with the program's GC and gives each object the domain whose mode, capabilities and plugin match, opening a new one when none does. DefineSymbols tags every struct and function with its object's domain.

System per domain. Each domain has its own copy of System.Core: a str made by the library is the library's String<u8>, allocated by its collector. The copies do not clash because every symbol carries its module's name. In the example below, the linked program defines both of these:

larva.Counter::System.Exchange.Text
larva.Counter::System.List..new$1<gc Counter::System.String<u8>>

and the program has its own larva.app::System… functions. The design notes weighed a single shared core instead (simpler, but a manual-memory library would then allocate its strings in the root's collector) and chose one per domain; the price is that each domain pays for the parts of System it uses.

Link-once items (the runtime helpers Larva.Object, Larva.Object$vt, Larva.Interface, Larva.Nullable, Larva.FuncN) are shared or duplicated by OnceKey(name, domain, handleFree):

So tracing and reference counting share *::Larva.Object, while a manual library gets *@2::Larva.Object.

Code generation per domain

The back ends (LLVM's FunctionEmitter, x64's FunctionCompiler, the WebAssembly emitter and IlLowering) compile each function with its domain's GC instead of the program's. Three questions on IrModule drive them:

In the example, the tracing App.Main calls larva_rc_dead, its type descriptors carry domain bytes, and its code has no inline nursery allocation (InlineHeapFor is false for code that counts):

@larva.type.0 = private constant { i32, i32, i32, i16, i16, [0 x i32] } { i32 32, i32 1, i32 16396, i16 0, i16 0, [0 x i32] zeroinitializer }, align 8
@larva.type.3 = private constant { i32, i32, i32, i16, i16, [0 x i32] } { i32 32, i32 1, i32 268, i16 0, i16 0, [0 x i32] zeroinitializer }, align 8

Both are String<u8> (TRAILING | LEAF = 12). type.0 has flags 16396 = 0x400C: domain byte 0x40, domain 0, uncounted (the program's strings). type.3 has 268 = 0x10C: domain byte 0x01, domain 1, counted (the library's strings).

The rules at the boundary

Calls

A call between domains is an ordinary direct call: a handle is the payload's address in every domain, so nothing is converted. Stacks belong to the whole program; every collector scans all of them.

What may cross

Between domains cross only static, non-generic functions whose parameters and result are numbers, bools, or pointers to them (HirLowerer.Crosses, NotCrossable):

The reason is in the vocabulary: a library's str is the library's System.String<u8>, a different struct from the program's, with another vtable. Importing the library's structs, vtables and globals was tried first and failed for exactly that reason (imported struct Lib$vt does not match Lib::Lib$vt).

Strings and bytes: System.Exchange

What does not cross by value crosses by copy. System.Exchange (Library/System.Core/Exchange.ant) packs text or bytes into a packet: native memory from mem.alloc, outside every collector, with an 8-byte length and then the bytes.

 packet (u8*)
 +---------------------------+----+----+----+----+-----
 | length (8 bytes, little   | b0 | b1 | b2 | b3 | ...
 |  endian)                  |    |    |    |    |
 +---------------------------+----+----+----+----+-----

Each domain has its own copy of Exchange in its own System; they agree through the packet's primitive format. A packet is taken once, by the side that receives it, and packets are never collected: one that nobody takes leaks.

The crossing diagnostic

The Antril frontend knows which referenced assembly belongs to another domain (TypeSymbol.Domain) and reports AN1079 where a member that cannot cross is used. The lowering has the same check as a second line (CrossingError). Calling a library method that returns a str gives:

…\App.ant(12,27): error AN1079: `Words.Name` belongs to another GC domain (`Counter`, a library built for another gc): its result is a `str`, an object of that domain that cannot cross. Between domains cross only static functions over numbers, bools and `u8*` packets: pack strings and bytes with System.Exchange

The pairs

Each combination of modes needed its own answer. The design first planned a table of cross-domain references (slot → handle, registered by a domain barrier); in the end no pair needed it.

Moves. For counts to be exact the native back ends had to transfer a reference on a move, as IlLowering always did: a local read once and dead afterwards hands its reference to the destination instead of being retained and released later (MoveAnalysis, Transfers). Before that, a counted object handed to a manual struct died only when the function returned.

An example

Two projects in sibling folders. The library counts references:

queen 1.0;

chunk PROJ:
   name: Counter,
   type: library

chunk BUILD:
   gc: refcount

import System;

into namespace Counter
{
	public static class Words
	{
		public:
			/// Counts the words of the text in a packet (the packet is taken and freed).
			static Count(u8* packet) : i32
			{
				str text = Exchange.Text(packet);
				List<str> words = new List<str>();
				loop (str word in text.Split(' '))
					if (word.Length > 0)
						words.Add(word);
				return words.Count;
			}

			/// The text in capitals, as a new packet.
			static Shout(u8* packet) : u8*
			{
				str text = Exchange.Text(packet);
				return Exchange.Pack(text.ToUpper() + "!");
			}

			/// A string: an object of this library's domain.
			static Name() : str => "Counter";
	}
}

The program uses the default tracing collector and depends on the library:

queen 1.0;

chunk PROJ:
   name: App,
   type: exe

chunk DEPS:
   proj: ../Counter

import System;
import Counter;

into namespace App
{
	Main()
	{
		i32 count = Words.Count(Exchange.Pack("the quick brown fox"));
		Console.WriteLine($"words: {count}");
		str loud = Exchange.Text(Words.Shout(Exchange.Pack("hello")));
		Console.WriteLine(loud);
	}
}

The library's List<str>, its strings and its ToUpper result are all allocated and freed by reference counting, in the library's own System; the program's strings live in the tracing heap. Built with either back end:

$ larva build -o app.exe
app.exe (llvm back end, O3, entry app::App.$Module.Main)
$ ./app.exe
words: 4
HELLO!
$ larva build --backend x64 -o app.exe
app.exe (x64 back end, entry app::App.$Module.Main)
$ ./app.exe
words: 4
HELLO!

Adding Console.WriteLine(Words.Name()); to Main stops the build with the AN1079 error shown above: Name returns the library's str.

Limits

• Only static functions over numbers, bools and packets cross. There is no packet format yet for other types (wide numbers, lists): those would be sugar over bytes.
• Packets are not freed for you. A packet nobody takes leaks.
• One level. An external dependency's own dependencies are compiled inside it, in its domain.
• No VM. larva build has no vm back end, so it makes mixed programs only as native code (the VM itself supports domains when a host links IR objects with MixedDomains).
• Not implemented yet: domains in Larva's own WebAssembly back end and in larva_rt.js (the header there has no domain byte, and gc.domain returns 0); a custom collector per domain (gc: custom is not usable at all yet, see Custom collectors).
• Known issue: in a mixed program, tracing code is compiled as counting code (CodeGcOf), and the LLVM and x64 back ends then emit no generational write barrier for it, while the runtime still allocates its objects in the nursery. A young object stored into an old object of the tracing domain can then be missed by a minor collection. A tracing program that fills an old List with new objects across minor collections printed a wrong sum (786 instead of 1000) with LLVM and crashed with the x64 back end once it depended on a reference-counted library; without the dependency it is correct, and LARVA_GC_VERIFY=1 reports the old-to-young pointer.