Garbage Collection

Three concepts: reachability, mark-and-sweep, and scheduling.

This chapter produces ADR-006 and it is the reason the whole heap design looks the way it does. It is also the place where Rust's ownership model is least helpful and where the workaround — handles instead of pointers — turns out to buy more than it costs.

Concept 1: Reachability

1. Concept

An object is live if it is reachable from a root by following references. Everything else is garbage, whatever its reference count says.

2. Problem

local a, b = {}, {}
a.other = b
b.other = a
a, b = nil, nil        -- unreachable. Both refcounts are still 1.

Two objects, each referenced once, neither reachable from anything. Reference counting cannot free them, because the property "nothing points at me" is local and the property "nothing reachable points at me" is global.

And this is not an exotic case. It takes one line with tables, and with closures it happens by accident:

local function loop(n)                 -- the closure captures an upvalue...
  if n == 0 then return end
  return loop(n - 1)                   -- ...that holds the closure. A cycle.
end

Every recursive local function in every Ember program is a cycle. That is why Rc was never an option, and it is worth stating that plainly rather than as a general preference.

3. Mental model

The heap is a directed graph. The roots are the entry points. Collection is: mark everything reachable, free the rest. Reference counting asks each object "who points at you?"; tracing asks the program "what can you still get to?" — and only the second question has a correct answer.

   ROOTS  (seven sets — miss one and you free a live object)
   ┌────────────┬────────────┬─────────┬───────────────┬───────────────┬────────────┬────────────┐
   │ value      │ call       │ globals │ open          │ chunk         │ the intern │ host       │
   │ stack      │ frames     │ table   │ upvalues      │ constant pools│ table      │ handles    │
   └─────┬──────┴─────┬──────┴────┬────┴───────┬───────┴───────┬───────┴──────┬─────┴──────┬─────┘
         ▼            ▼           ▼            ▼               ▼              ▼            ▼
     ┌────────┐  ┌─────────┐  ┌────────┐  ┌──────────┐   ┌──────────┐
     │Table A │─▶│ Closure │─▶│Upvalue │  │ Table B  │   │ EmberStr │
     └───┬────┘  └─────────┘  └────────┘  └────┬─────┘   └──────────┘
         ▼                                     ▼
     ┌────────┐◀──────────────────────────┌──────────┐
     │Table C │──────────────────────────▶│ Table D  │   ← C and D are a CYCLE, but
     └────────┘                            └──────────┘     they are REACHABLE, so live

     ┌────────┐
     │Table E │ ← reachable from nothing. GARBAGE, despite a nonzero "refcount"
     │  ↕     │   from the object beside it.
     │Table F │
     └────────┘

4. Implementation

Root enumeration lives in exactly one function. This is not tidiness; it is the only defense against the bug class.

#![allow(unused)]
fn main() {
impl Vm {
    /// THE root set. Every GC edge into the heap from outside the heap is here.
    /// If you add a field to `Vm` that can hold a `Value` or a `GcRef`, it goes
    /// in this function in the same commit — no exceptions.
    fn enumerate_roots(&self, grey: &mut Vec<GcRef<AnyObject>>) {
        for v in &self.stack                { push_value(grey, *v) }          // 1
        for f in &self.frames               { push_closure(grey, f.closure) } // 2
        push_table(grey, self.globals);                                       // 3
        for &u in &self.open_upvalues       { push_upvalue(grey, u) }         // 4
        for p in self.live_protos()         { p.chunk.trace_constants(grey) } // 5
        self.strings.trace_intern_table(grey);                                // 6
        for &h in self.host_handles.iter()  { push_any(grey, h) }             // 7
    }
}
}

Sets 5, 6, and 7 are the ones people miss. A chunk's constant pool holds interned string handles; the intern table itself holds every live interned string; and Section 5's Engine hands handles to Rust code that the VM cannot see. All three are edges from outside the object graph, and all three are invisible if you think of "roots" as "the stack".

Warning: Root set 6 is subtle in the other direction too. If the intern table is a strong root, no interned string is ever collected — a real leak for a long-lived engine that builds many distinct strings. If it is weak, entries must be removed during sweep. Ember's Lab 16 makes it weak and sweeps it, and the decision is recorded, because "strings are never collected" is a defensible choice too and the two must not be confused.

5. Alternatives

6. Decision

ADR-006: a non-moving, non-incremental, stop-the-world mark-and-sweep collector over a slot table, with generation-checked handles and zero unsafe.

The reasoning, in the curriculum's priority order:

Why not B (CPython's model), which is the other reasonable answer? Because reference counting costs an increment and a decrement on every value copy, which means Value can no longer be Copy, which means the VM's stack operations stop being memcpy and start being bookkeeping. That is the tax discussed in the value representation chapter, and avoiding it is worth a pause we have not yet measured.

7. Tradeoffs

8. Production concerns

The two bug classes, and both are worth causing on purpose in Lab 15:

Both are timing-dependent: they need a collection to happen at the wrong moment. That means they survive your test suite and appear in production. Two defenses, and use both:

# 1. STRESS MODE: collect on EVERY allocation. ~1000x slower, and it turns a
#    timing-dependent bug into a deterministic one. Run the whole corpus under it.
ember run --gc-stress tests/golden/**/*.ember

#![allow(unused)]
fn main() {
// 2. Generation-checked handles turn the failure into a diagnosable error.
pub fn table(&self, r: GcRef<Table>) -> Result<&Table> {
    if self.generations[r.index as usize] != r.gen {
        return Err(internal(
            "stale handle: a GC root or edge was missed — run with --gc-stress"));
    }
    // ...
}
}

That error message is doing real work: it names the class of bug and the tool that finds it. An error message that teaches is worth writing.

The allocation hazard. An object that has been allocated but is not yet reachable from any root can be collected by a GC triggered by the next allocation during its own construction:

#![allow(unused)]
fn main() {
// WRONG: if alloc_table triggers a collection, `key` is unreachable and dies.
let key = self.heap.alloc_string("name")?;
let tbl = self.heap.alloc_table()?;              // ← may collect. `key` is garbage.
self.heap.table_set(tbl, Value::Str(key), v)?;
}

Three fixes, in order of preference:

1. Allocate in an order where each new object is immediately stored in something rooted.
2. Push intermediates onto the VM stack, which is a root set. This is what Lua's C API forces on you — every lua_pushX roots the value — and it is why that API is stack-based.
3. A temporary-root scope guard: let _r = heap.root(key);, released on Drop.

Ember uses 2 inside the VM (the values are already on the stack) and 3 in Engine (Section 5). State the rule in docs/gc.md: "any object reachable only from a Rust local across an allocation point must be rooted." That sentence is the whole hazard.

Safe points. The collector may only run where the VM's state is consistent — in practice, at allocation. Never mid-close_upvalues, never between the two halves of a table rehash. Ember enforces it structurally: collect() is called only from Heap::alloc*, and functions that must not collect simply do not allocate. Write that down too; it is invisible otherwise.

Finalizers and weak tables. Lua has __gc and weak tables. Ember has neither, deliberately:

• A finalizer runs at collection time, which is a nondeterministic moment — and Ember has promised determinism. Worse, a finalizer can resurrect its object by storing it somewhere reachable, which turns a two-phase collector into a three-phase one.
• Weak tables require a second marking phase and a decision about key-vs-value weakness. They are genuinely useful (caches, object-to-metadata maps) and they are a large increment in collector complexity.

Both go in appendix/lua-differences.md and docs/limitations.md. "We did not implement it" and "we decided against it" are different claims, and the second one needs the reason written down.

9. References

rg -n 'propagatemark|reallymarkobject|sweeplist|singlestep|luaC_step' lgc.c
rg -n 'GCObject|CommonHeader|isgray|iswhite' lobject.h lgc.h

• Jones, Hosking & Moss, The Garbage Collection Handbook (2nd ed.) — the reference. Chapters 1–3 cover everything in this chapter properly.
• Wilson, Uniprocessor Garbage Collection Techniques (1992) — the classic survey, free online, and still the best single overview.
• Lua's lgc.c — a production incremental collector in ~1,200 lines, with the tri-color states visible in the macros.
• Go's runtime/mgc.go — unusually well-commented for a concurrent collector, and the place to read about write barriers in anger.
• CPython's Modules/gcmodule.c — option B, and the comments explain the "subtract internal references" trick that finds cycles among candidates.

Concept 2: Mark and Sweep

1. Concept

Two passes. Mark: from every root, walk every edge, set a bit on each object reached. Sweep: walk the whole slot table; free anything unmarked; clear the marks.

2. Problem

You need to compute reachability over a graph that may be large, cyclic, and deep — without recursing (which would blow the Rust stack on a deep list) and without allocating (which would recurse into the collector).

3. Mental model

The tri-color abstraction (Dijkstra et al., 1978) names the three states an object can be in during a mark:

   WHITE  — not yet reached.        At the end of marking: garbage.
   GREY   — reached, but its CHILDREN have not been scanned yet. On the worklist.
   BLACK  — reached, and its children are all at least grey. Done.

   THE INVARIANT:  no BLACK object may point to a WHITE object
                   without a GREY object somewhere on a path to it.

   roots ──▶ grey ──scan──▶ black
                │
                └── pushes its children to grey
   marking ends when the grey set is empty. Everything still WHITE is garbage.

For a stop-the-world collector the invariant is trivially maintained, because the program cannot run during marking and therefore cannot create a black→white edge. The moment you make marking interruptible, the mutator can create one — and that is exactly what a write barrier prevents. See Concept 3.

4. Implementation

#![allow(unused)]
fn main() {
impl Heap {
    pub fn collect(&mut self, roots: impl FnOnce(&mut Vec<Handle>)) -> GcStats {
        let before = self.bytes_allocated;
        let t0 = self.clock.now();          // injected, not std::time — determinism

        // ── MARK ───────────────────────────────────────────────────────────
        // A worklist, NOT recursion. A 100,000-element linked list would
        // recurse 100,000 deep and abort the process — the same hazard as
        // the parser's, in a place where no depth limit can help.
        let mut grey: Vec<Handle> = Vec::new();
        roots(&mut grey);
        while let Some(h) = grey.pop() {
            if self.marks[h.index as usize] { continue; }    // already black
            self.marks[h.index as usize] = true;
            self.trace_children(h, &mut grey);               // push its edges
        }

        // ── SWEEP ──────────────────────────────────────────────────────────
        let mut freed = 0;
        for i in 0..self.slots.len() {
            if self.marks[i] { self.marks[i] = false; continue; }   // clear for next time
            if let Some(obj) = self.slots[i].take() {
                self.bytes_allocated -= obj.size_of();
                // Bump the generation: every EXISTING handle to this slot is
                // now detectably stale. This is what turns a missed root from
                // silent corruption into an error with a message.
                self.generations[i] = self.generations[i].wrapping_add(1);
                self.free.push(i as u32);
                freed += 1;
            }
        }

        self.next_gc = (self.bytes_allocated * GROWTH_FACTOR).max(MIN_HEAP);
        GcStats { before, after: self.bytes_allocated, freed, pause: self.clock.since(t0) }
    }
}
}

And the edges — one match, and it must be exhaustive:

#![allow(unused)]
fn main() {
fn trace_children(&self, h: Handle, grey: &mut Vec<Handle>) {
    match self.slots[h.index as usize].as_ref() {
        Some(HeapObject::Table(t)) => {
            for v in &t.array { push_value(grey, *v) }
            for e in t.entries.iter().flatten() {
                push_value(grey, e.0);       // ← THE KEY. The most-forgotten edge.
                push_value(grey, e.1);
            }
            if let Some(m) = t.meta { grey.push(m.erase()) }   // ← the metatable
        }
        Some(HeapObject::Closure(c)) => {
            for &u in &c.upvals { grey.push(u.erase()) }
            c.proto.chunk.trace_constants(grey);               // ← nested protos too
        }
        Some(HeapObject::Upvalue(u)) => match u {
            // An OPEN upvalue's value lives on the stack, which is already a
            // root. A CLOSED one owns its value and must be traced. Two states,
            // two behaviors.
            Upvalue::Open(_)  => {}
            Upvalue::Closed(v) => push_value(grey, *v),
        },
        Some(HeapObject::Str(_))      => {}                    // no outgoing edges
        Some(HeapObject::UserData(d)) => d.trace(grey),        // §5: the host's job
        None => {}
    }
}
}

Four edges to get right, and each is a real bug someone has shipped: table keys, table metatables, closure protos' constant pools, and the open/closed distinction on upvalues.

5–7. Alternatives, decision, tradeoffs

Decision: worklist marking, whole-table sweeping. The sweep is the part that scales with the whole heap rather than the live set, which is the first thing to fix if measurement says pauses matter — and it is the natural first step toward the incremental collector in capstone project 3.

8. Production concerns

• Marking must not allocate. The grey worklist is a Vec kept on the Heap and reused, so a collection does not itself trigger a collection.
• bytes_allocated must be accurate, or scheduling is nonsense. Every alloc adds and every sweep subtracts the same size function. Add a debug-mode audit that walks the heap and compares the total; it will find your accounting bug in one run.
• Generation counters wrap. A u32 wrapping after 4 billion reuses of one slot would make a very old stale handle look valid. That is astronomically unlikely and it is still worth a comment saying you thought about it.
• The pause is proportional to the live set (mark) plus the heap size (sweep). Measure both separately in --trace-gc; they respond to different fixes.

Concept 3: Scheduling, and What Comes Next

1. Concept

When to collect. Too often and you burn CPU; too rarely and the heap grows unboundedly and the pause gets worse.

2–3. Problem and mental model

Collect when the heap has grown by some factor since the last collection. That makes GC cost proportional to allocation, which is what you want: a program that allocates nothing pays nothing.

#![allow(unused)]
fn main() {
const GROWTH_FACTOR: usize = 2;      // collect when the heap doubles
const MIN_HEAP: usize = 256 * 1024;  // do not collect a tiny heap repeatedly

fn alloc(&mut self, obj: HeapObject) -> Result<Handle> {
    self.bytes_allocated += obj.size_of();
    if self.bytes_allocated > self.limit {
        return Err(limit_error("memory budget exhausted"));   // §5's memory limit
    }
    if self.bytes_allocated > self.next_gc || self.stress { self.request_collection(); }
    // ...
}
}

Note that the memory limit and the GC threshold are different numbers. The threshold is a performance tuning knob; the limit is a sandbox control that returns ErrorKind::Limit. Confusing them means a script that allocates a lot gets a "budget exhausted" error when it should have got a collection.

4–7. Alternatives, decision, tradeoffs

Decision: A, with D available. Section 5 exposes engine.collect() and lets a host set the factor — a request-scoped engine may prefer "never collect, then drop the whole heap", which is a legitimate and very fast strategy.

And here is the honest statement about pauses. Ember stops the world. For a policy script evaluating a few hundred candidates with a heap of a few megabytes, a mark-and-sweep pause is sub-millisecond and nobody notices. For a long-lived engine holding a large object graph, it is visible. --trace-gc reports the pause distribution so that you find out which one you have before deciding whether to build capstone project 3.

8. Production concerns — what an incremental collector would change

This is the part worth understanding even though Ember does not implement it, because it explains why real collectors are so much more complicated.

If marking can be interrupted — the program runs between mark steps — then the program can break the tri-color invariant:

   1. The collector marks table A BLACK (scanned; all its children are grey/black).
   2. The PROGRAM runs:   A.x = B      where B is still WHITE and reachable
                                        from nowhere else.
   3. The collector finishes. B was never greyed. B is swept. A.x dangles.

The fix is a write barrier: code that runs on every pointer store into a heap object, keeping the invariant. Two classic flavors:

The cost is real: every table field write, every upvalue write, every array store now runs a check. Go accepts it because concurrent collection is worth more; Lua accepts it for incrementality; Ember does not pay it because it does not need it.

This is the sentence to remember: a write barrier is the price of an interruptible collector. Stop-the-world is not "the simple version" — it is the version that does not need to observe mutation.

Generational collection adds a second requirement in the same family: if you collect only the young generation, you must know which old objects point into it, which needs a remembered set, which needs — again — a write barrier.

Moving collection would be unusually cheap for Ember, and it is worth knowing why: because values hold handles, not pointers, moving an object between slots requires updating only the slot table, not every reference to it. A pointer-based collector must find and fix every reference; Ember would not. That is a genuine, non-obvious advantage of the handle design and it belongs in ADR-006's consequences — the design chosen for safety turns out to make a future optimization easier, which is the kind of thing worth noticing when it happens.

The one thing that would block moving is open upvalues holding raw stack indices — but those index the stack, not the heap, so they are unaffected. Check that reasoning yourself; it is a good test of whether the two chapters have landed.

9. References

• Dijkstra, Lamport, Martin, Scholten & Steffens, On-the-fly Garbage Collection: An Exercise in Cooperation (1978) — tri-color marking and the invariant.
• Yuasa, Real-time Garbage Collection on General-Purpose Machines (1990) — the snapshot barrier.
• Ungar, Generation Scavenging (1984) — generational collection and the weak generational hypothesis.
• Cheney, A Nonrecursive List Compacting Algorithm (1970) — copying collection in a page.
• Lua's lgc.c: luaC_barrier, luaC_barrierback, and the GCSpropagate/GCSsweep states.
• Go's runtime/mbarrier.go, whose comment block is the best plain-English explanation of hybrid write barriers in existence.

Things to Notice

• Every recursive local function is a cycle. That single fact decides the collector, and it is about closures, not tables.
• Seven root sets, and three of them (constant pools, the intern table, host handles) are not the stack.
• Table keys are edges. So are metatables. So are a proto's constants.
• Mark with a worklist, not recursion, or a long linked list aborts your process.
• The generation counter converts a missed root from corruption into a diagnosable error, and --gc-stress converts it from timing-dependent to deterministic. Those two together are why this design is teachable.
• A write barrier is the price of an interruptible collector. Stop-the-world is not the naive version; it is the version that need not observe mutation.
• Handles make moving collection easy later. A safety decision that turned into a performance option — note it when it happens.
• Finalizers and weak tables are omitted deliberately, and the reasons (determinism, resurrection, complexity) are stronger than "we ran out of time".

Validation / Self-check

1. Draw the two-object cycle and explain precisely why reference counting cannot free it.
2. Name all seven root sets. Which three are not the value stack, and where did each come from?
3. Give the four edges that trace_children must not forget.
4. Define white, grey, and black, and state the tri-color invariant.
5. Why must marking use a worklist rather than recursion? What is the failure mode?
6. What does bumping the generation counter on sweep buy you? What does --gc-stress add to that?
7. Describe the allocation hazard and give the three fixes in order of preference.
8. What is a write barrier, when is it required, and what are the two classic flavors?
9. Why would moving collection be unusually easy for Ember, and what would not block it?
10. Why does Ember have no finalizers? Give two independent reasons.

Next: Strings and Interning.