Lab 15: Mark and Sweep (Milestone 11)

Background

You will build the collector: the slot-table heap, generation-checked handles, root enumeration, worklist marking, sweeping, allocation accounting, thresholds, --trace-gc, --gc-stress, and collectgarbage().

Then you will deliberately break it, twice — once by forgetting a root and once by forgetting an edge — observe both, and fix them with the invariants that prevent recurrence.

Why This Lab Matters

A cycle being collected is the test that justifies the entire subsystem. Everything else about the collector is scheduling.
The two bug classes here are timing-dependent, which means they survive normal test suites and appear in production. --gc-stress plus generation checks convert them into deterministic, diagnosable failures. Building both tools is most of the lab.
This is where Rust's ownership model is least helpful, and where the handle design pays for itself.

Prerequisites

Labs 13–14 complete; closures and tables exist and there is a cycle test in the corpus.
Garbage Collection read.
The Rust problem statement in the section index re-read.

Predict First

How many root sets are there? Name them before looking.
local a,b = {},{} a.o=b b.o=a a,b=nil,nil collectgarbage() — how many objects freed?
You forget to trace table keys. What is the first program that breaks, and after how long?
--gc-stress collects on every allocation. Roughly how much slower, and what does that buy?
What does bumping a slot's generation counter on free give you that a plain free-list does not?
An object is allocated and not yet stored anywhere when the next allocation triggers a collection. What happens, and what are the three fixes?

Step 1: The Heap

#![allow(unused)]
fn main() {
pub struct Heap {
    slots:       Vec<Option<HeapObject>>,
    generations: Vec<u32>,
    marks:       Vec<bool>,          // a separate Vec, not a bit in the object
    free:        Vec<u32>,
    next_id:     u64,                // stable object ids for table keys (Lab 13)
    bytes_allocated: usize,
    next_gc:     usize,
    limit:       usize,              // §5's memory budget — a DIFFERENT number
    grey:        Vec<Handle>,        // reused across collections; marking must not allocate
    stress:      bool,
}
}

#![allow(unused)]
fn main() {
pub fn table(&self, r: GcRef<Table>) -> Result<&Table> {
    let i = r.index as usize;
    if self.generations.get(i) != Some(&r.gen) {
        // This message is doing real work: it names the bug CLASS and the tool
        // that finds it. Error messages that teach are worth writing.
        return Err(internal("stale handle: a GC root or edge was missed \
                             — re-run with --gc-stress to make it deterministic"));
    }
    match &self.slots[i] { Some(HeapObject::Table(t)) => Ok(t), _ => Err(internal("type mismatch")) }
}
}

Checkpoint question. Why are marks a separate Vec<bool> rather than a field on each object? (Two reasons: sweeping clears them in one pass over contiguous memory, and objects stay immutable during marking, which matters if you ever make the collector concurrent.)

Step 2: Root Enumeration — One Function, Seven Sets

Write enumerate_roots from the concept chapter. All seven sets.

Then add the rule that keeps it correct:

#![allow(unused)]
fn main() {
// tests/gc.rs
#[test]
fn every_vm_field_that_can_hold_a_value_is_rooted() {
    // A structural reminder, not a proof: this list must be updated in the SAME
    // COMMIT as any new Vm field that can hold a Value or a GcRef. Reviewers
    // check it. It is cheap, it is not airtight, and it has caught real bugs.
    const ROOTED_FIELDS: &[&str] = &[
        "stack", "frames", "globals", "open_upvalues",
        "live_protos (constant pools)", "strings (intern table)", "host_handles",
    ];
    assert_eq!(ROOTED_FIELDS.len(), 7);
    assert_eq!(ROOTED_FIELDS.len(), Vm::ROOT_SET_COUNT);   // bumped by hand, deliberately
}
}

Note: That test cannot prove completeness — nothing short of a proc macro can. What it does is make adding an unrooted field require editing a test that says "seven", which turns a silent omission into a visible decision. Cheap structural friction in the right place beats an elaborate mechanism in the wrong one.

Step 3: Mark and Sweep

Write collect() and trace_children from the concept chapter.

Four edges. Check each against your code:

Table array values
Table entry keys and values — the keys are the forgotten one
Table metatable
Closure upvalues and its proto's constant pool; and a Closed upvalue's value (an Open one's lives on the stack, already a root)

Step 4: Break It On Purpose

This is the step people skip and it is the most valuable one in the lab. Do both.

Bug 1: a missing root

#![allow(unused)]
fn main() {
fn enumerate_roots(&self, grey: &mut Vec<Handle>) {
    for v in &self.stack { push_value(grey, *v) }
    // for &u in &self.open_upvalues { push_upvalue(grey, u) }   ← COMMENT THIS OUT
    // ...
}
}

$ ember run tests/golden/closures/counter.ember            # passes. Heap is too small to collect.
$ ember run --gc-stress tests/golden/closures/counter.ember
error: stale handle: a GC root or edge was missed — re-run with --gc-stress to make it deterministic

Write down what you just observed: the bug was invisible under normal execution and instant under stress. That is the entire argument for the stress mode, and it is why it is not optional.

Now imagine the same bug without generation checks: the slot has been reused by an unrelated object, table() returns that object, and the program computes a plausible wrong answer. Two tools, two conversions: stress mode makes it deterministic; generations make it diagnosable.

Bug 2: a missing edge

#![allow(unused)]
fn main() {
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);    ← COMMENT OUT: the KEY
        push_value(grey, e.1);
    }
}
}

$ ember run --gc-stress -e 'local k = {} local t = {} t[k] = "v"
                            collectgarbage() return tostring(t[k])'
error: stale handle: ...

Note that this one needs a table used as a key to show up — the most common missing edge is invisible for string and integer keys, which is why it survives casual testing.

Record both in docs/learning/11-gc.md in the shape the curriculum asks for:

SYMPTOM        stale-handle error under --gc-stress; silent wrong values without it
ROOT CAUSE     open_upvalues omitted from enumerate_roots
WRONG MODEL    "roots are the things the program can name" — but a freshly
               allocated upvalue is named only by the VM's own bookkeeping
FIX            one function, seven sets, and a test that asserts the count
INVARIANT      any Vm field that can hold a Value is added to enumerate_roots
               in the same commit

Step 5: The Allocation Hazard

#![allow(unused)]
fn main() {
// WRONG. If alloc_table collects, `key` is reachable from nothing.
let key = self.heap.intern(b"name")?;
let tbl = self.heap.alloc_table()?;
self.heap.table_set(tbl, Value::Str(key), v)?;
}

Fix it, and then make the class of bug hard to write:

#![allow(unused)]
fn main() {
/// A temporary root. Anything reachable only from a Rust local across an
/// allocation point must be held by one of these.
pub struct Rooted<'h> { heap: &'h mut Heap, slot: usize }
impl Drop for Rooted<'_> { fn drop(&mut self) { self.heap.temp_roots.pop(); } }
}

Inside the VM this is rarely needed — intermediates are already on the value stack, which is a root set — and that is not an accident. Lua's C API is stack-based for exactly this reason: every lua_pushX roots the value, so a host physically cannot hold an unrooted object across an allocation. Section 5 adopts the same posture.

Step 6: Accounting, Thresholds, and `--trace-gc`

#![allow(unused)]
fn main() {
const GROWTH_FACTOR: usize = 2;
const MIN_HEAP: usize = 256 * 1024;
}

#![allow(unused)]
fn main() {
#[test]
fn allocation_accounting_is_exact() {
    // Walk the heap and sum object sizes; compare with bytes_allocated.
    // This finds the accounting bug you WILL have, in one run.
    let audited: usize = heap.iter_live().map(|o| o.size_of()).sum();
    assert_eq!(audited, heap.bytes_allocated);
}
}

And expose it to scripts and to the CLI:

collectgarbage()          -- full collection
collectgarbage("count")   -- KB in use, like Lua

Warning: The GC threshold and the memory limit are different numbers with different meanings. Crossing the threshold triggers a collection; crossing the limit returns ErrorKind::Limit. Wire them to the same value and a script that legitimately allocates a lot gets "memory budget exhausted" when it should have got a collection.

The Trace

$ cat > /tmp/cycle.ember <<'EOF'
local function make_pair()
  local a, b = {}, {}
  a.other, b.other = b, a          -- a CYCLE: refcounting could never free this
  return nil
end
for i = 1, 50000 do make_pair() end
collectgarbage()
EOF
$ ember run --trace-gc /tmp/cycle.ember

gc: trigger    heap=524288 B  threshold=524288 B
gc: mark       roots=7 sets, 41 objects greyed
gc: mark done  reachable=39   grey-pushes=612   in 0.31 ms
gc: sweep      scanned=8192 slots  freed=8153  bytes=-4162048
gc: done       heap=32104 B  next_gc=256000 B  pause=1.24 ms
...
gc: trigger    heap=…
gc: done       heap=…  freed=100000 objects

Three things to read off that:

freed=8153 on a heap whose only garbage is cyclic pairs. Reference counting would have freed zero of them. That number is the justification for the whole subsystem, in one line of output.
sweep scanned=8192 versus reachable=39. Marking is proportional to the live set; sweeping is proportional to the whole heap. They respond to different fixes, which is why --trace-gc reports them separately — and it is the measurement that motivates capstone project 3.
pause=1.24 ms. Write yours down. It is the number that decides whether an incremental collector is worth building for your workload, and guessing at it is how people build collectors nobody needed.

And the census, which is how a host finds a leak that is not a bug:

$ ember run --stats -e 'local t = {} for i=1,1000 do t[i] = {id=i, name="n"..i} end return #t'
--- heap census ---
  Table     1001    ~120 KB
  EmberStr  1002    ~ 28 KB
  Closure      0
  Upvalue      0
  total     2003    ~148 KB   (peak 152 KB, 2 collections, 3.1 ms total pause)

Expected Output

$ ember run -e 'local a,b={},{} a.o=b b.o=a a,b=nil,nil
                local before=collectgarbage("count") collectgarbage()
                return tostring(collectgarbage("count") < before)'
true

$ ember run --gc-stress tests/golden/**/*.ember     # the WHOLE corpus, all green
$ cargo test --features gc-stress                    # and in CI

Debugging Steps

`--gc-stress` fails and normal runs pass

Working as designed. A missing root or edge. Read the error, then bisect by commenting out root sets one at a time until the failure changes.

Stale-handle errors only in programs with nested tables

A missing edge, not a missing root. Check keys, metatables, and proto constants.

Objects are freed that are clearly reachable from a local Rust variable

The allocation hazard. Find the alloc between the creation and the store.

`bytes_allocated` drifts

Your alloc and your sweep use different size functions, or a path frees without subtracting. The audit test names it.

The collector runs constantly on a tiny heap

MIN_HEAP is missing, so next_gc is being set to twice a very small number.

A collection during `close_upvalues` corrupts things

close_upvalues must not allocate, and collect() must only be reachable from alloc. If both are true this cannot happen; verify both rather than adding a flag.

`--gc-stress` is so slow the corpus takes an hour

Expected — it is ~1000× slower. Run the full corpus under it in CI nightly, and a fast subset on every commit.

Experiment

CLAIM. Reference counting cannot free cyclic garbage, and the difference is measurable, not theoretical.

METHOD. Add --refcount-only: a mode that frees an object when nothing points at it (maintain a count on every Value copy in the table/closure paths) and never traces. Run /tmp/cycle.ember under both modes with --stats.

PREDICTION. How much memory does the refcount mode reclaim? What is the per-operation cost it adds to the tracing mode's zero?

RESULT. Record both numbers. Then delete the refcount mode — you have made the point, and maintaining two collectors is not the assignment. Put the numbers in docs/adr/ADR-006-tracing-gc-with-handles.md as the evidence for the decision, which is what turns an ADR from an opinion into a record.

Test

#![allow(unused)]
fn main() {
#[test]
fn a_cycle_is_collected() {
    // THE test for this subsystem. Everything else is scheduling.
    let mut vm = Vm::new();
    vm.run_str("local a,b={},{} a.o=b b.o=a").unwrap();
    vm.run_str("a,b=nil,nil").unwrap();
    let before = vm.heap.bytes_allocated;
    vm.collect();
    assert!(vm.heap.bytes_allocated < before, "cyclic garbage was not collected");
}

#[test]
fn closure_cycles_are_collected() {
    // A recursive local function IS a cycle: closure → upvalue → closure.
    // This is the case that makes tracing mandatory rather than nice.
    let mut vm = Vm::new();
    for _ in 0..1000 {
        vm.run_str("do local function f(n) if n>0 then return f(n-1) end return 0 end f(3) end")
          .unwrap();
    }
    vm.collect();
    assert!(vm.heap.live_count() < 100, "closure cycles leaked: {}", vm.heap.live_count());
}

#[test]
fn live_objects_survive_gc_stress_over_the_whole_corpus() {
    for case in corpus() {
        let mut b = VmBackend::with_gc_stress();
        let got = b.run(&case.src, &Limits::test_defaults());
        assert_eq!(normalize(got), normalize(case.expected()),
                   "{} differs under --gc-stress", case.name);
    }
}

#[test]
fn table_keys_are_traced() {
    // The most-forgotten edge. Uses a TABLE as a key so it is a heap object.
    with_gc_stress(|| {
        assert_eq!(run("local k={} local t={} t[k]='v' collectgarbage() return t[k]"), "v");
    });
}

#[test]
fn metatables_are_traced() {
    with_gc_stress(|| {
        assert_eq!(run("local t=setmetatable({}, {__index=function() return 7 end})
                        collectgarbage() return t.anything"), "7");
    });
}

#[test]
fn allocation_accounting_is_exact() { /* Step 6 */ }

#[test]
fn the_memory_limit_is_not_the_gc_threshold() {
    // A script that allocates a lot but stays under the limit must COLLECT,
    // not error.
    let r = run_with_memory_limit("local t={} for i=1,100000 do t[i]={} t[i]=nil end return 1",
                                  4 * 1024 * 1024);
    assert!(r.is_ok(), "collection should have kept this under the limit: {r:?}");
}
}

Challenge Extensions

Incremental marking. Split marking into steps with a bounded grey-set budget, add a Dijkstra write barrier on table/upvalue stores, and measure the pause distribution (not the mean) before and after. This is capstone project 3 started early — and the barrier is the education.
Generational mode. Track object age, collect young objects only, maintain a remembered set via the same barrier. Measure on an allocation-heavy program.
Compaction. Ember's handles make this easy: move objects between slots and update only the slot table. Implement it, measure fragmentation before and after, and confirm that open upvalues are unaffected because they index the stack, not the heap.
A heap dump. ember run --heap-dump=out.json emitting the object graph, and a small script to render it with graphviz. The single best debugging tool you can build for the next three labs.
Weak tables. __mode = "k" / "v". Requires a second marking phase and a decision about ephemerons. Read Lua's lgc.c treatment first; it is genuinely subtle.

Deliverables

Slot-table heap with generation-checked handles; a stale handle is a clean error.
enumerate_roots with all seven sets, in one function, plus the count test.
Worklist marking (not recursion); the grey Vec is reused and marking allocates nothing.
All four edge classes traced, including table keys and metatables.
Both deliberate bugs introduced, observed, fixed, and written up in the five-part shape.
--gc-stress, and the whole corpus green under it (in CI, at least nightly).
The allocation hazard fixed, with a Rooted guard for the cases the value stack does not cover.
Accounting exact, audited by a test; threshold and limit are separate numbers.
--trace-gc reports mark and sweep separately, with pause times.
--stats heap census by object type.
collectgarbage() and collectgarbage("count").
The refcount experiment's numbers recorded in ADR-006.
docs/gc.md and docs/learning/11-gc.md written.

Validation / Self-check

Name the seven root sets and say which three are not the value stack.
Name the four edge classes and which is most often forgotten.
What does --gc-stress convert, and what do generation counters convert? Why do you need both?
Describe the allocation hazard and the three fixes. Why is Lua's C API stack-based?
Why must marking use a worklist? Why must it not allocate?
Why are the GC threshold and the memory limit different numbers?
In your --trace-gc output, which number scales with the live set and which with the whole heap? What does each motivate?
Give your measured pause time, and say whether it justifies an incremental collector for a policy-engine workload.
Why is local function f() return f() end the example that makes tracing mandatory?

Next: Lab 16 — Strings and Interning.

Open-Source Engineer & Contributor