Understand Concurrent Garbage Collection

Topic Overview

Collect While Mutator Runs

Stop-the-world pauses hurt latency. Concurrent mark-sweep runs marker alongside mutator with write barriers to catch new references. G1, ZGC, and Go's concurrent sweeper reduce pause times to milliseconds or sub-ms.

Tri-Color Invariant

White: unvisited. Gray: visited, children pending. Black: fully scanned. Barrier ensures black objects do not point to white without gray intervention.

cCopy
Loading…

• Floating garbage: whites reachable later but collected
• Remark phase fixes drift from concurrent stores
• Sweep can be lazy per-page
• Correctness harder than stop-the-world

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will understand concurrent garbage collection algorithms. This exercise asks you to model tri-color marking, write barriers, and how the collector maintains correctness while the mutator allocates.

Your Task

Simulate concurrent marking with the tri-color abstraction and see why concurrent collectors need write barriers: interleave collector steps with mutator writes, run the same schedule with no barrier, a Dijkstra insertion barrier and a Yuasa deletion (snapshot-at-the-beginning) barrier, and detect when a live object gets freed.

Input

cCopy
Loading…

Marking

• start: every object is white; each root, in root order, is shaded grey (appended to a FIFO grey queue).
• step: repeatedly take the object at the front of the grey queue, make it black, and shade each white object it points to grey (in link order): up to N objects.
• Barriers (only while marking is active):
  • dijkstra: on link A B, if B is white, shade B grey.
  • satb: on unlink A B, if B is white, shade B grey (the old value is preserved).
  • none: nothing.
• finish: step until no grey objects remain, then free every white object (allocation order). Afterwards, compute which objects are actually reachable from the roots at that moment; each freed object that is reachable is a bug.

Output

cCopy
Loading…

Example

The classic lost object: the mutator moves the only pointer to c from a grey object into a black one.

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A color per object and a FIFO grey queue; barriers hook into link/unlink.
2. The final reachability check must be independent of the colors.

Hidden tests run the lost-object schedule under both barriers, a schedule where satb retains floating garbage (an object unlinked during marking survives even though it is dead), and objects created unreachable.