SATB Garbage Collection and Tri-Color Marking in Java

One line of Java, and 331M that stayed put

if (marking && oldValue != null) satbBuffer.add(oldValue);   // runs BEFORE the store, on every reference write

That's the whole idea of SATB garbage collection, in one line. The rest of this article is why that line is enough to let G1 and Shenandoah mark a heap while your threads keep rewriting it, and what it costs you.

The cost shows up in a GC log. I dropped the only reference to a 330 MB object graph while G1 was in the middle of a concurrent marking cycle, then asked for another cycle right after. This is what it printed (OpenJDK 21.0.12.1, G1, -Xms1g -Xmx1g, 2 vCPUs, lab numbers):

[3.061s] GC(9)  Pause Young (Concurrent Start) (System.gc()) 329M->330M(1024M) 30.146ms
=== dropped root, 150 ms after System.gc() call ===
[3.379s] GC(10) Concurrent Mark From Roots 315.602ms
[3.383s] GC(10) Pause Remark 331M->331M(1024M) 3.200ms
[3.587s] GC(10) Pause Cleanup 331M->331M(1024M) 0.411ms
=== cycle 1 done ===
[3.892s] GC(11) Pause Young (Concurrent Start) (System.gc()) 331M->329M(1024M) 1.539ms
[3.901s] GC(12) Pause Remark 329M->4M(1024M) 2.942ms

The graph was garbage from about 150 ms into the first cycle. That cycle freed nothing: 331M in, 331M out. The next one freed everything: 329M down to 4M. Run the same program but null the reference before the first cycle starts and that cycle does the job itself (Pause Remark 321M->5M).

Nothing is broken. G1 did what it promised. The promise just isn't the one most people assume, and "SATB garbage collection" is the name of the promise.

The short version: a snapshot, and a promise to honour it

A concurrent collector has a problem a stop-the-world one doesn't. It walks the object graph to decide what's alive, and while it walks, your code is changing the graph. If your code hides a live object from the walker, the collector frees something you still use. That's the worst bug a GC can have.

Snapshot-at-the-beginning (SATB) solves it by cheating on purpose. The collector decides what's live as of the moment marking started. Anything reachable in that snapshot gets marked, even if it stops being reachable a millisecond later. Anything allocated after the snapshot is treated as live. To make the snapshot hold while the graph changes, every reference write records the value it's about to overwrite.

So the mechanism and the cost are the same thing. Objects that die after the snapshot are kept until the next cycle. That's floating garbage, and the log above is it. I'll come back to it, because it's the thing you'll actually see in production.

I went in assuming the barrier was the interesting part. It isn't, really. The barrier is simple. What's interesting is what the invariant forces everywhere else: the pause structure, the memory overhead, the way Pause Remark behaves.

A toy marker, then the real thing

There are two labs. The first is a 40-line model that shows the lost-object bug and the barrier fixing it. It's a model, not HotSpot. The second runs real collectors and shows the floating garbage above.

What you need. A JDK 21 with G1 and (for the optional step) Shenandoah. I used the Ubuntu openjdk-21 package, 21.0.12.1+1-1-24.04.4, on x86-64 Linux, 2 vCPUs, 8 GB. Check yours with java -XX:+UseShenandoahGC -version; some vendor builds don't ship Shenandoah. No Docker, no dependencies. Everything runs with the source launcher.

Part 1: the model. Toy.java:

import java.util.*;

public class Toy {
    static class Obj { String name; Obj[] f = new Obj[2]; int color; /* 0 white, 1 grey, 2 black */
        Obj(String n){ name = n; } }

    static ArrayDeque<Obj> grey = new ArrayDeque<>(), satbBuf = new ArrayDeque<>();
    static boolean marking;

    static void shade(Obj o){ if (o != null && o.color == 0) { o.color = 1; grey.add(o); } }
    static void scan(Obj o){ for (Obj c : o.f) shade(c); o.color = 2; }

    static void store(String mode, Obj src, int i, Obj val){
        if (mode.equals("satb") && marking) { Obj old = src.f[i]; if (old != null) satbBuf.add(old); }  // pre-write: keep the OLD value
        src.f[i] = val;
        if (mode.equals("incr") && marking && src.color == 2) { src.color = 1; grey.add(src); }         // post-write: re-grey the SOURCE
    }

    static void run(String mode){
        grey.clear(); satbBuf.clear();
        Obj root = new Obj("root"), a = new Obj("A"), b = new Obj("B"), x = new Obj("X"), d = new Obj("D");
        root.f[0] = a; root.f[1] = b; b.f[0] = x; a.f[0] = d;
        marking = true; shade(root);
        scan(grey.poll());          // root -> black; A, B grey
        scan(grey.poll());          // A -> black; D grey. B is still grey, X still white
        store(mode, a, 1, x);       // black A now points at white X
        store(mode, b, 0, null);    // the only grey-reachable path to X is cut
        store(mode, a, 0, null);    // A drops D, which is already grey
        while (!grey.isEmpty()) scan(grey.poll());
        while (!satbBuf.isEmpty()) { shade(satbBuf.poll()); while (!grey.isEmpty()) scan(grey.poll()); }   // "remark"
        marking = false;
        System.out.printf("%-5s X marked: %-5s | D marked: %-5s%n", mode, x.color == 2, d.color == 2);
    }
    public static void main(String[] args){ run("none"); run("satb"); run("incr"); }
}

Step 1
$ java Toy.java
none  X marked: false | D marked: true
satb  X marked: true  | D marked: true
incr  X marked: true  | D marked: true

X marked: false in the first line is a live object about to be freed. D marked: true in all three is floating garbage: D was already grey when A let go of it, so it stays.

Part 2: real collectors. Floaty.java builds a six-million-node chain behind a single static field, settles it, then runs a concurrent cycle on a second thread while main decides when to drop the reference:

public class Floaty {
    static class Node { Node next; Node[] kids; long pad; }
    static Object root;                                          // the only reference to ~330 MB

    public static void main(String[] args) throws Exception {
        String mode = args[0];                                   // keep | before | during
        int n = Integer.parseInt(args[1]), delayMs = args.length > 2 ? Integer.parseInt(args[2]) : 100;
        Node head = null;
        for (int i = 0; i < n; i++) { Node x = new Node(); x.next = head; x.kids = new Node[2]; head = x; }
        root = head; head = null;
        System.gc(); Thread.sleep(2000);                         // settle, and let a Shenandoah cycle finish (see the dead end below)
        System.out.println("=== MODE " + mode + " ===");
        if (mode.equals("before")) root = null;                  // dead before the snapshot
        Thread t = new Thread(() -> System.gc());                // with ExplicitGCInvokesConcurrent: Concurrent Start + marking
        t.start();
        if (mode.equals("during")) { Thread.sleep(delayMs); root = null;   // dead after the snapshot, mid-mark
            System.out.println("=== dropped root, " + delayMs + " ms after System.gc() call ==="); }
        t.join();
        System.out.println("=== cycle 1 done ===");
        Thread.sleep(300);
        System.gc();                                             // cycle 2
        System.out.println("=== cycle 2 done ===");
    }
}

Step 2 (run each of keep / before / during)
$ java -XX:+UseG1GC -Xms1g -Xmx1g -XX:+ExplicitGCInvokesConcurrent \
       -Xlog:gc,gc+marking:stdout:uptime Floaty.java during 6000000 150
Expected: "Concurrent Mark From Roots" about 300-400 ms; Pause Remark 331M->331M in cycle 1, 329M->4M in cycle 2

Forcing levers. -Xms1g -Xmx1g is tiny on purpose, and System.gc() plus -XX:+ExplicitGCInvokesConcurrent is how I get a marking cycle on demand instead of waiting for the occupancy threshold. Production wouldn't use either. On this machine marking takes about 400 ms, so a 150 ms delay lands mid-mark. On a faster box the cycle may finish first; raise n or lower delayMs.

The confirmation signal. In during mode, Pause Remark in cycle 1 shows the same number on both sides of the arrow. If you see it drop, your delay landed before the Concurrent Start pause, which is the before case. If cycle 1 was already finished, you dropped too late.

Environment differences. Core count changes how long marking takes. Vendor builds differ on Shenandoah. And if you add -XX:-ExplicitGCInvokesConcurrent, System.gc() becomes a full stop-the-world collection and you'll see no concurrent cycle at all.

Cleanup. Nothing is written to disk. Kill any stray java processes.

Why a marker needs a barrier at all

Start with colors. During marking, every object is in one of three states. White means the collector hasn't reached it yet. Grey means it's been reached and marked live, but its outgoing references haven't been looked at. Black means it's marked and every reference it holds has been followed. When no grey objects are left, whatever's still white is garbage.

 white ──(collector reaches it)──▶ grey ──(collector scans its fields)──▶ black
 
 invariant to protect:   no black object points at a white object
                         unless a grey object can still reach that white one

The danger is a specific two-step trick that a running program does without meaning to. The program (the mutator, in GC vocabulary, since from the collector's side its only job is to mutate the graph) does two things between two collector steps. It stores a reference to a white object X into an object that's already black. Then it removes the last reference to X from anything grey. Now X is reachable only through a black object, the collector will never scan that black object again, and X stays white. At the end of marking, X gets freed while the program holds it. That's the lost-object problem, and Toy reproduces it in the none row.

Break either of the two steps and you're safe. There are two families of barrier, one per step.

Incremental update guards the first step. When the program stores a reference into a black object, the barrier turns that object grey again (or shades the new target). The collector then re-scans it. This was the CMS approach. It keeps the invariant strictly, but the collector has to revisit objects, and at the end it needs a pause to re-scan roots and everything dirtied since (that's my reading of the literature, not something I measured).

Snapshot-at-the-beginning guards the second step. When the program overwrites a reference, the barrier saves the old value first, so it can never vanish from the collector's sight. The graph might change shape but the collector still traces everything that was reachable when it started. Objects allocated since then aren't in the snapshot; the collector doesn't need to trace them and just treats them as live.

SATB trades precision for a bounded job. Marking work is fixed at what the snapshot held, so the cycle is guaranteed to end. Thomas Schatzl, who has worked on G1 for years, says in his 2022 post on G1 concurrent marking that these "simple guaranteed termination properties" matter more to him than reclaiming objects that die during marking. I agree. I'd take a predictable cycle with floating garbage over one that might keep chasing a mutator that never stops allocating.

SATB garbage collection in HotSpot: buffers, TAMS, and JDK 9 to 27

Three pieces make SATB real in G1.

TAMS. At the Concurrent Start pause, every old region records its current top as TAMS, top-at-mark-start. Everything below TAMS is the snapshot. Everything at or above it is "allocated after", implicitly live, never traced. Young regions get TAMS set to their bottom, so they're all above it. That's why the snapshot isn't a copy of anything. It's a pointer per region and a convention.

The pre-write barrier. In g1BarrierSet.cpp (I read the jdk-21+35 tag through a fetch summariser, so treat details as second-hand), the logic is short. If the global SATB queue set isn't active, return. Otherwise load the existing value from the field, skip it if null, and enqueue it on the thread's local SATB queue. Threads that start mid-marking copy the active flag. Threads that exit flush their queue. Inactive barrier: one flag check per reference store. Active barrier: a load and a buffer append.

The queue and its filter. G1SATBMarkQueueSet takes full per-thread buffers (-XX:G1SATBBufferSize, default 1024 entries on 21.0.12.1, product flag) and filters them before the marker sees anything. Per the source summary, it drops null entries, anything at or above the region's TAMS, and anything already marked. That filtering is the reason the barrier is affordable. Most overwritten values are young objects or already-marked ones, and they never reach the marker. A related knob, -XX:G1SATBBufferEnqueueingThresholdPercent (60 by default), lets the mutator filter a buffer itself and skip handing it over when it's mostly filtered out.

Remark ties it off. Pause Remark is a stop-the-world pause that drains the SATB buffers that are still sitting in threads, finishes marking, processes weak references, and unloads classes.

I wanted to know how much of remark is SATB draining, so I ran a program that did 1.3 million reference overwrites while a cycle was marking (Writer.java, same G1 flags plus -Xlog:gc+phases=debug). I'd guessed the pause would be dominated by buffer draining.

[2.937s] GC(9) Finalize Marking 0.066ms
[2.938s] GC(9) Weak Processing 0.234ms
[2.939s] GC(9) Class Unloading 1.671ms
[2.940s] GC(9) Pause Remark 291M->291M(1024M) 2.339ms

Finalize Marking, which I'm assuming is where the leftover buffers get drained (I didn't read that code), was 0.066 ms. Class unloading took 1.67 ms of a 2.34 ms pause. I could be wrong about what else the buffers cost during the concurrent phase, since I can't count entries from the log. But at remark, in this lab, the SATB queue was not the long pole.

Shenandoah uses the same idea. On 21.0.12.1, -XX:ShenandoahGCMode defaults to satb, and the SATB barrier is a diagnostic flag defaulting to true:

$ java -XX:+UnlockDiagnosticVMOptions -XX:+PrintFlagsFinal -version | grep -i -E "satb"
    ccstr ShenandoahGCMode             = satb       {product} {default}
     bool ShenandoahSATBBarrier        = true       {diagnostic} {default}

I ran Floaty on Shenandoah (-XX:+UseShenandoahGC) with the same shape: drop mid-mark, and the first cycle logged Concurrent cleanup 324M->324M, the next one 324M->4M. Same behaviour, same reason. Different collector.

ZGC takes a different route, load barriers instead of an old-value barrier. It gets its own article (see ZGC explained); I didn't run it for this one.

JDK 9    G1 is the default collector (JEP 248); CMS deprecated (JEP 291)
JDK 12   Shenandoah arrives as experimental (JEP 189)
JDK 14   CMS removed (JEP 363); its incremental-update barrier goes with it
JDK 15   Shenandoah is a product feature (JEP 379)
JDK 20   G1 moves to a single mark bitmap (JDK-8210708, per Schatzl's post), about 1/64 of heap
JDK 21   what I ran; G1SATBBufferSize 1024, Shenandoah mode = satb

The bitmap change is worth a sentence. With one bit per 8-byte object slot, the mark bitmap is roughly 1.5% of the heap. The old design had two bitmaps and cost about double. Schatzl notes the price: after class unloading there's extra scrubbing and a rebuild of remembered sets. If you've read the remembered sets article, that "Rebuild Remembered Sets" phase after marking is the same machinery.

What actually cracked this. My first Shenandoah run lied. It showed the reference dropping and memory returning immediately, and I wrote down "Shenandoah doesn't float". Wrong. With ExplicitGCInvokesConcurrent, System.gc() on Shenandoah doesn't wait for the cycle to finish the way G1's does. A leftover cycle from my setup call was still running, my explicit cycle queued behind it, and by the time it started my root = null had already happened. Cycle "1" was effectively a before run. The fix was a two-second sleep after settling (it's in the code above). Getting to that took longer than building the model did. The whole thing, with the source reading, was more than a day, and the notes are here so you don't repeat it.

One more thing the lab does not show. In during mode the chain gets traced even without a barrier, because its head was already marked when the Concurrent Start pause scanned roots. The barrier isn't what keeps the graph alive there. The snapshot semantics produce floating garbage in that experiment, and Toy is the experiment that needs the barrier.

What the snapshot costs you, and the claims that don't hold

Floating garbage is expected. Anything that dies during a cycle survives it. With a G1 cycle that takes seconds on a big heap, that can be a lot. In a log it shows up as a cycle that finishes with no reclaimed space, then a later one that does. If you graph heap after each Pause Cleanup and see staircases, this is probably why. Check the GC log guide for reading those lines.

"Concurrent marking means no pauses." There are two short stop-the-world moments: the Concurrent Start (it piggybacks on a young pause) and Remark. Both need a safepoint, which can take longer than the pause itself.

"The barrier is why my app is slow." Plausibly sometimes, but the barrier is only active while marking runs. Between cycles it's a flag check. The post-write barrier (cards, remembered sets) is the one that costs you all the time. I measured that one in the card tables article; I did not measure the pre-barrier's active cost here.

"G1 is full of floating garbage because the heap is too small." Not necessarily. A heap that's too small gives you to-space exhaustion and Full GCs. Floating garbage is present at any heap size. What matters is how much dies in the window.

Cargo-cult flags. -XX:+UseConcMarkSweepGC on JDK 21 fails at startup with Unrecognized VM option 'UseConcMarkSweepGC'. People still paste it from old answers because the incremental-update barrier belongs to that collector, not G1. Setting -XX:ConcGCThreads higher to "finish marking faster" does shorten the window, but costs CPU on the cores your app needs; on this 2-vCPU box the default was 1.

I'll admit one gap: I haven't tested what happens when SATB buffers fill faster than the marker drains them. The code has a path for it (full buffers get handled on the mutator's thread), but I didn't provoke it.

The few knobs, and the things not worth touching

The useful lever is the first one, and it works by shortening the window, not by changing the barrier. If a cycle starts earlier, it ends with less allocation behind it, so less floating garbage. G1 does this for you with adaptive IHOP, which I covered in G1 GC explained. Before touching anything, try the fix that always works: allocate less during the cycle.

The SATB buffer flags are for people reading g1SATBMarkQueueSet.cpp. I haven't found a production case where changing them was the answer, and I'd want a profile before I believed one.

Reading a marking cycle in production, and upgrade notes

Leave -Xlog:gc,gc+marking on. It's cheap at info. The lines to watch for G1: Concurrent Mark From Roots (how long the window is), Pause Remark (how long you're stopped; single-digit milliseconds in my lab), and the before/after on Pause Cleanup and the next Pause Remark. A big gap between cycle N's reclaimed space and cycle N+1's is floating garbage.

For a continuous record, JFR has G1 concurrent-cycle events; I believe the default profile includes them but I didn't verify that here.

Alert on trends. A concurrent cycle that's getting longer over days means a growing live set or too few concurrent threads. Remark that suddenly runs tens of milliseconds usually means class unloading or reference processing, not SATB.

Version safety: I ran only JDK 21.0.12.1. JDK 17 doesn't have the single-bitmap change, so native memory overhead is higher there and I haven't diffed the flag sets. JDK 25 I haven't run. When you move LTS to LTS, diff -XX:+PrintFlagsFinal output for SATB and Conc, and re-read your marking-cycle lines. CMS is gone from JDK 14 on; on 21 a leftover -XX:+UseConcMarkSweepGC in a launch script stops the JVM with Unrecognized VM option.

The version I'd text a teammate

• A concurrent GC has to stop the program from hiding live objects from the marker. SATB does it by saving every overwritten reference while marking is on.
• G1 and Shenandoah (in its default satb mode) keep whatever was alive at cycle start. Garbage that appears after the snapshot lives through the cycle.
• Floating garbage is the design, not a leak. Look for a cycle that reclaims nothing followed by one that reclaims a lot.
• To get less of it, shorten the cycle or allocate less during it. Don't touch the barrier flags.

Questions about SATB and concurrent marking

What is SATB in garbage collection?
Snapshot-at-the-beginning. The collector treats the heap as it was when marking began, and a write barrier records overwritten references so nothing from that snapshot goes unseen. G1 and Shenandoah both use it, verified on JDK 21 above.

Why didn't G1 free memory that died during marking?
Because the snapshot already counted it as live. It gets reclaimed in the next cycle. Lowering the cycle length or the IHOP threshold shrinks the effect.

What's the difference between SATB and incremental update?
SATB records the old value on overwrite and keeps the original graph. Incremental update catches new stores into black objects and re-scans them. CMS used incremental update; it was removed in JDK 14. See the upcoming CMS article.

Do Serial and Parallel GC use SATB?
No. They stop the world to mark, so nothing mutates the graph while they walk it. See Serial and Parallel GC.