Project 3: An Incremental Collector

Build the write barrier, which is the thing the GC chapter described and deliberately did not implement.

Effort: a week. Value: after this you can read Go's mgc.go or Lua's lgc.c and know exactly what every barrier call is protecting.

Start With the Number

Do not build this because incremental collectors sound advanced. Build it if your measurement says to:

cargo bench --bench gc 2>&1 | grep -A6 'pause distribution'

  runs: 184   p50: 1.1ms   p95: 6.8ms   max: 31.4ms

The max is what lands in your p99 latency. If your policy-engine workload has a max pause of 1 ms and a request budget of 50 ms, stop here and write that down — a correct decision not to build something is a result.

If the max is tens of milliseconds on a heap you expect to grow, continue.

The Problem

Marking becomes interruptible, so the program runs between mark steps and can break the tri-color invariant:

   1. Collector marks table A BLACK   (scanned; all children grey or black)
   2. PROGRAM runs:  A.x = B          where B is WHITE and reachable from nowhere else
   3. Collector finishes. B was never greyed. B is swept. A.x DANGLES.

The invariant: no black object may reference a white object without a grey object on some path to it. Stop-the-world maintains it for free, because the program cannot run. Incremental does not.

The Barrier

Two classic flavors, and you should implement one and understand the other:

#![allow(unused)]
fn main() {
#[inline]
fn barrier(&mut self, parent: Handle, child: Value) {
    // The cost: this runs on EVERY pointer store into a heap object. Table
    // field writes, array stores, upvalue writes, metatable assignment.
    // Make the common case one predictable branch.
    if self.gc_phase == Phase::Marking
        && self.marks[parent.index as usize]                    // parent is black
    {
        if let Some(h) = child.as_handle() {
            if !self.marks[h.index as usize] { self.grey.push(h); }   // grey the child
        }
    }
}
}

Every mutation site must call it, and there are more than you think:

   Table::set (hash part)        Table::set (array part)      SET_LIST
   SET_UPVAL (closed upvalues)   setmetatable                 userdata field setters
   the module cache insert       Engine::set_global           Engine::stash

Finding all of them is the project. A missed barrier is a use-after-free that appears only under memory pressure, only when the collector happens to be mid-mark — which is precisely why --gc-stress needs an incremental sibling:

#![allow(unused)]
fn main() {
// --gc-incremental-stress: run ONE mark step per allocation, so the collector
// is almost always mid-mark and every missing barrier fires immediately.
}

The Work Budget

Incremental means bounded steps, and choosing the bound is a real decision:

Lua's tuning knobs — pause and stepmul — are worth reading about, because they are the two parameters every incremental collector ends up exposing and neither has an obvious default.

The Measurement

Expect throughput to get worse. Incremental collection trades total time for pause distribution, and the barrier costs a branch on every store. If your total GC time did not increase, either your barrier is missing or your benchmark does not mutate.

That tradeoff — worse mean, better tail — is the finding, and being able to state it from your own numbers is the deliverable.

Deliverables

• The pause-distribution measurement first, and a written decision to proceed (or not).
• Phased collection: Idle → Marking → Sweeping, with bounded steps.
• A write barrier at every mutation site; a checklist of sites in docs/gc.md.
• --gc-incremental-stress running one step per allocation.
• The whole corpus green under it.
• A step-budget policy, with the two tuning knobs exposed and documented.
• The before/after table, including the throughput regression.
• ADR-017, superseding ADR-006's "non-incremental" clause.

Where It Gets Hard

1. Finding every mutation site. Make Table's fields private and route every write through one method that calls the barrier. Structural prevention beats an audit.
2. The sweep phase must not free objects allocated during the sweep. New objects are allocated black (or in a separate "new" colour) so they survive the cycle they were born in.
3. Weak structures, if you have them. Interact badly with incremental marking; Lua has a whole phase for them.
4. Reasoning about correctness. Write the invariant at the top of gc.rs and check every change against it. This is the one place in the curriculum where a written invariant is genuinely the only defense.

Where to Read

rg -n 'luaC_barrier|luaC_barrierback|GCSpropagate|singlestep|luaC_step' lgc.c

• Lua's lgc.c — a production incremental collector in ~1,200 lines, with both barrier flavors (luaC_barrier forward, luaC_barrierback for tables) and the pause/stepmul tuning.
• Go's runtime/mbarrier.go — the best plain-English explanation of hybrid write barriers in existence, in the comment block.
• Dijkstra, Lamport, Martin, Scholten & Steffens (1978) and Yuasa (1990) — the two barriers, from the source.
• Jones, Hosking & Moss, The Garbage Collection Handbook, chapters 15–16.

Validation / Self-check

1. State the tri-color invariant and the three-step sequence that breaks it.
2. Give the two barrier flavors, what each does on a store, and who uses which.
3. List every mutation site in Ember that needs a barrier. How did you make finding them structural?
4. Why must objects allocated during a sweep survive it?
5. What does --gc-incremental-stress do that --gc-stress cannot?
6. Report your before/after table. Which metric got worse, and why is that expected?
7. Was it worth it for your workload? Answer from the max-pause number you started with.

Next: Project 4 — Coroutines.