Marking While the Program Runs

How marking actually runs#

The GC keeps a to-do list of objects it has found but not yet looked inside:

put every root's target on the to-do list, and mark it
while the to-do list is not empty:
    take object X off the list
    for each reference field in X:
        if the target is not marked:
            mark it
            put it on the to-do list

At any moment during that walk, every object is in one of three states. GC literature names them with colours:

Everything hangs on that last row. When the program is stopped, nothing can change an object after the GC reads it, so the rule is safe. But when the program keeps running, it can change an object right after the GC has finished with it, and the GC, following its rule, never notices.

The failure, step by step#

Start with A already black, B grey, and C white. B points to C.

That's the exact bug garbage collection exists to prevent, and the collector caused it. But which of the program's two moves is to blame? Replay with one at a time:

• Only step 2 (A.f = C): B still points to C, so when the GC reads B it finds C and marks it. No bug.
• Only step 3 (B.g = null): nothing points to C any more, so C really is garbage, and freeing it is correct. No bug.

Neither move alone does harm; the bug needs both. A reference to a white object is hidden inside an object the GC has finished with, and every path the GC could still use to reach it is cut. Prevent either condition, and the bug can't happen.

The fix: record every reference that gets overwritten#

G1, the default collector on most machines, prevents the second condition. It uses another write barrier, like the card-marking one from Part 3, except this one runs before the store, and only while marking is in progress:

// you wrote:  B.g = null;
// the JIT emits:
if (marking_in_progress) {
    old = B.g                    // the reference about to be lost: C
    if (old != null)
        add old to this thread's queue
}
B.g = null

The GC keeps emptying those queues and marks every object in them grey. Replay the failing timeline: at step 3, the barrier catches C and queues it, the GC marks it, and when marking ends C is black, so it survives. Step 6 finds C exactly where it should be.

Why is that enough? The only way to hide an object from the GC is to cut a path to it, and the only way to cut a path is to overwrite a reference. Every overwrite is now caught, so every object that was reachable when marking started gets marked, however the program rearranges things afterwards. That's why the technique is called snapshot-at-the-beginning, or SATB.

That's the price. SATB keeps everything that was reachable when marking began, plus everything allocated during marking, so garbage that dies during marking survives one extra cycle. Being too careful wastes a little memory for a while; being too eager corrupts data.

There's a second approach, which prevents the first condition instead: record where every reference store happens, and have the GC rescan those places before marking ends. That's called incremental update; the now-removed CMS (Concurrent Mark Sweep) collector worked that way, by dirtying cards.

And objects created during marking? The GC never traced them, but they're obviously in use. G1 remembers, for each part of the heap, where the allocated space ended when marking began, and anything allocated beyond that point is treated as live for this cycle. That boundary is called top-at-mark-start, or TAMS.

Why short pauses remain#

• At the start, the GC must read the roots, and they include local variables on every thread's stack. Locals change constantly and have no barrier, because a barrier on every local-variable write would be far too expensive. So the GC stops the threads briefly to read the roots, then lets them continue.
• At the end, there's another pause, called remark, to process the last entries still sitting in each thread's queue.

In G1, both are usually short, because neither walks the whole heap. The long part, the walk itself, now runs alongside your program. (Part 6 shows a collector that scans thread stacks concurrently too.)

But marking only tells the GC what's live. It frees nothing. Getting most of the space back still means moving objects, and doing that while the program runs is the next problem.

What concurrent marking costs#

If this comes up in an interview#