# No-STW SATB _2026 September_ Snapshot at the Beginning (SATB) seems like an elegant strategy for a concurrent mark-sweep GC. Implementations of it out in the wild seem to generally use a global STW for root scanning. I.e., they need all threads to be paused simultaneously, at which point some work is done, and then the threads can continue. That's sub-optimal because it may take a while for all threads to jointly come to a halt. But the upside is you need no load barriers. Given that reading a pointer from the heap is typically a lot more common than writing a pointer into the heap, a no-load-barriers design like SATB is quite attractive. Here's an attempt at a GC design using SATB without a global STW. I'm still by no means a GC expert, and will be glossing over some details. There's a chance I'll miss something crucial, making some aspect of the design unfeasible. We'll see. By the way, some familiarity with GC terminology is assumed, such as tricolor object sets, and what a barrier is at a basic level. ## Data Structure Recap First, let's recap some of the design choices related to the mark and sweep phases of the GC, which I've already covered in previous notes. ### 'Allocated' Bitmaps A massive block of virtual memory containing bitmaps that cover every slot of memory that our GC can give out. The location of a bit is trivially calculated from the object address in few CPU instructions. The kernel's demand paging ensures that the physical backing memory is proportional to all-time peak heap usage including uncollected garbage, and it's only a tiny fraction of that, since one bit here represents an object of 64 bits at minimum, up to many KiB at the high end. A bit is set atomically whenever any thread allocates an object. The GC will swap out the entire Allocated bitmap array for a zeroed out bitmap when it begins the mark phase; the original one is stored away to be used for the sweep phase, and then recycled. Basically, this becomes the representation of the White object set at the start of marking; AKA the 'condemned' set. ### 'Marked' Bitmaps Same shape and characteristics as the Allocated Bitmaps. Starts out all zero, and replaces the Allocated Bitmaps when marking begins, so new allocations are automatically marked. Basically, the Black object set during marking. After marking, the sweep phase subtracts this set from the White set, to determine the set of objects to be freed. ### Trace Work Set A radix tree-like structure storing an ordered map of object address to type, so the trace loop can scan memory in order, and objects need no in-heap type headers (since we use NaN-packed tagged pointers that obviate the need for that). Basically the Grey set during marking. ## State Terminology Let's establish some common terminology with regards to different states the GC and application threads can be in. ### GC States * `IDLE`: Not doing any GC work (that other threads need to know of). * `SATB`: Waiting for application threads to reach SATB status. * `MARK`: Marking has begun after SATB has been established. * `FREE`: Wants to sweep; will wait for application threads to flush any pending Work Set writes from SATB barrier action. We may need one more state to synchronize across multiple GC threads; that's outside the scope of this article. ### Mutator States *Mutator means application thread.* * `IDLE`: Assumes the GC is idle; barriers disabled. * `SATB`: Acknowledged the GC's SATB request; store barriers enabled. * `MARK`: Acknowledged the GC's start of the mark phase. * `FREE`: Acknowledged the GC's desire to begin sweeping, so has disabled barriers and flushed pending writes into the Work Set. ## GC Strategies Before we get to our actual desired design, let's look at simpler GC strategies as a baseline, and look at problems that arise as we add Concurrent and No-STW capabilities. ### STW Serial M/S This one is extremely simple. Stop all threads, scan their roots, trace the object graph, sweep, continue all threads. The only interesting problem is that stopping the threads arbitrarily could lead to pointers being invisible due to being in the middle of some pointer arithmetic shenanigans. The typical solution is to wait for all threads to hit a safe-point in which they have a well-defined layout with regards to register contents. (Once again, I'm glossing over details, but I believe the design of safe-points with regards to ensuring a well-defined view of thread roots is largely an orthogonal issue to what I'm focusing on here.) We need no barriers of any kind, and it doesn't matter whether the Allocated and Marked bitmaps are swapped at the start or end, since allocations are paused anyway. If language semantics don't permit threads directly writing into the roots of other threads, then I believe threads could scan their own roots as they hit the pause, without waiting for the global pause. However, in the context of STW Serial M/S this would probably be a micro-optimization at best. Anyhow. ### STW Concurrent M/S This isn't too complicated. You perform the same STW to scan roots, but then mark and sweep concurrently. Similar to the serial method, you either wait for all threads to hit the pause, and then scan their roots; or, if cross-thread writes to roots isn't possible by language semantics, you can have them scan their own roots before hitting pause. Either way, what happens next is that the GC enters the mark phase, but then wakes up application threads, allowing them to run concurrently with M/S. Note that this means the Mutators don't need to be set to the MARK state; they can just stay in SATB which tells the GC that they have been, or can be, scanned. Then, they're just woken up and continue execution while the GC marks and sweeps. Here we need barriers for the first time to satisfy SATB invariants. What if, after the GC begins marking, an application thread acquires some pointer from deep within the object graph, that hasn't yet been traced, deletes all occurrences of it within the heap, but stores it locally? It could stay in a register or on the stack for any amount of time and used later. Meanwhile, the GC finds no trace of it, and it gets freed during sweep. This is called "hiding" a White object. Another way of doing it is acquiring a pointer to a White object and writing it into a Black object, then removing any other pointers to it. Since the Black object won't be scanned again, we successfully hid the White one. A solution is to use a write barrier that takes the *old* value of a pointer being overwritten within the heap, and greys it. I.e., it's inserted into the Trace Work Set. Hence "Snapshot at the Beginning": Any object that *was* reachable when marking began will be considered reachable by this GC cycle, just in case. Hiding becomes impossible. This is the traditional *Yuasa barrier* or *Yuasa-style deletion barrier* that's used to implement regular SATB. And what about newly allocated objects? The GC swaps the Allocated and Marked bitmaps while entering the MARK state, which application threads are forced to observe, in terms of memory ordering, by the time they're woken up. As such, new objects become Black; the GC allocator thinks it's setting bits in the Allocated bitmap but the pointer goes to the Marked bitmap which will effectively become the Allocated bitmap by the end of the mark phase. In tricolor terms, this puts new objects into the Black set after the mark phase has begun. This is correct because new objects can't have pointers to existing objects. To summarize, the sequence here would be: 1. GC enters SATB state and begins waiting. 2. Mutators gradually halt (enter SATB state), signaling the GC to continue if all mutators have reached SATB state. They can scan their roots before pausing, or let the GC do it once all are in pause (if cross-thread root access is possible). 3. GC swaps out Allocated & Marked bitmaps, enters MARK state, and wakes up mutators. The Yuasa barrier upholds the SATB invariant during concurrent GC work. ### No-STW Concurrent M/S Now we're finally getting to our actual desired design, where threads don't all need to reach a simultaneous pause. Let me simply explain the order of events: 0. Everything is IDLE. 1. The GC is triggered: It enters the SATB state and begins waiting. 2. Mutator threads gradually all enter SATB: From this point on, no object reachable *from the heap* can get lost, thanks to write barriers intercepting the *deletion* of a pointer *in* the heap. (Threads can drop pointers in locals, but global variables are as if box objects on the heap; write barriers apply.) (I realize now that I may be abusing the term "Snapshot," the S in SATB, because there's no single instant in which we capture a view of *all* live objects.) 3. The GC finds that all Mutators have acknowledged SATB. It enters the MARK state, which will tell Mutators that they can scan their roots now. The GC's trace loop begins, which continues until all Mutators are in MARK, and the Trace Work Set is empty / all Black. (Yes, Black objects can end up in the set; explained later.) This is a good time to scan global roots; the GC can begin their tracing, while Mutator threads are busy scanning their roots. (Global roots are global/static variables; Mutator roots are the stack, registers, and thread-local variables of Mutator threads.) Also, this is when the Allocated and Marked bitmaps are swapped. 4. Mutators gradually acknowledge the scan request, performing it and updating themselves to the MARK state. This forces them, in terms of memory ordering, to observe the swap of the Allocated bitmap. That means new allocations are Black rather than White. Some threads may have "coincidentally" observed the bitmap swap earlier, while still in SATB; this is benign. A Mutator in SATB state (pre root scan) can safely interact with Black objects, and can see some in the heap, since concurrent mark may have already started. Read on for how this is made safe. After the stack scan, new allocations are guaranteed Black, which is typical Concurrent M/S behavior. However, while this works in STW SATB due to any objects written into a Black object being part of the existing snapshot; we have the problem that some Mutator, which didn't scan its roots yet, could have the sole copy of some White object's pointer, which it writes into the new Black object, then drops the local pointer before its root scan. The more general version of this problem is that *any* Black heap object could have a White pointer written into it by a thread that hasn't yet performed its root scan. It wouldn't be a problem if the White object came from the heap, since the Yuasa barrier would make sure it can't be hidden, but pre-scan Mutator roots may still contain White pointers that can be written into Black objects and then dropped. The solution is a *Dijkstra-style insertion barrier* AKA *Dijkstra barrier* which is another kind of write barrier: It intercepts the *new* pointer being written into any heap object (includes global variables, which are seen as box objects on the heap) and greys that pointer (puts it in the Work Set). Though this only needs to happen if the pointer is written into a Black object, it's probably not worth adding this conditional, for multiple reasons: 1. It requires a "remote" memory load from the Marked bitmap. 2. We can't really mark global pointers as Black, since they're not really heap objects. The combination of the Yuasa and Dijkstra barriers is also what Go uses, because although it performs a very brief STW, it then scans thread roots incrementally. Oh, and this is how Black objects can end up in the Work Set: The Dijkstra barrier won't be checking whether the new value of the pointer it's writing is White, just like it won't be checking if the object that's being written into is Black. Similar reason as before: It may end up doing a "remote" memory load for a mark bit that's not in this thread's L1. Greying, on the other hand, is very cheap with local buffers that get flushed to the Work Set in batches. The Dijkstra barrier is disabled again for a Mutator thread once it's scanned its roots and entered the MARK state. One last note: I believe the Dijkstra barrier can allow for safe cross-thread root writing. After all, the object whose pointer you're "sending off" is greyed, so it can't possibly be hidden. Just make sure cross-thread root references are seen as "heap" objects, so the barrier is added to write operations to them. 5. The GC's trace loop eventually terminates as it finds the Work Set empty while all Mutators are in the MARK state, meaning there's no more marking work to be done, except that some Mutators may still be holding on to unmarked objects that haven't yet been flushed into the Work Set. So, the GC enters the FREE state and begins waiting. There's an important edge case here: Mutators may continuously put new Black objects into the Work Set due to the Yuasa barrier, so the trace loop could end up stuck in a loop. We can solve this by detecting that all new entries in the Work Set during an iteration were Black, *and* all Mutators were in the MARK state already at the start of the iteration. This condition terminates the loop. 6. Mutators acknowledge the GC's transition into the FREE state and flush any pending writes into the Work Set, then enter the FREE state themselves. 7. The GC observes that all Mutators have acknowledged the desire to end marking. It restarts the trace loop to finish off stragglers and then performs the sweep. It returns to IDLE. I'm glossing over some details here, and I'm not sure yet how some of them would best be implemented, such as the GC "waiting" for Mutator threads to do something. But that should be easy to figure out when compared to all else we've discussed. I won't be discussing the spawning of new threads during GC, or the synchronization of multiple GC threads. That's for another time, because this is complicated enough already. ## Optimizations Here are some optimization strategies that come to mind. ### Frozen Mutator This isn't really an optimization: It's crucial that the GC doesn't wait for a Mutator thread that's currently blocking on a syscall. For Mutators only, we can add a state called `BUSY` which indicates that it cannot scan its own roots right now. In that case, the GC will simply do this for it. When it wants to exit the busy state, it must ensure that, if the GC is running, it immediately enters the MARK state: Store barriers are enabled, and new allocations become Black. I think the correct way to achieve that in a race-free way would be actually having the GC put the thread into MARK state with an atomic compare and exchange operation. What the Mutator needs to do, upon returning from its busy code section (e.g. post-syscall) is to also perform a compare and exchange. This means either the Mutator or GC will succeed in putting the thread into the MARK state, and the one that succeeds has the responsibility to scan its roots. The other fails, but in doing so, observes that the other has succeeded in changing the Mutator state to MARK. This fits beautifully to an older idea of mine: * [2026-05-24: Static analysis to optimize GC](260524-gc-opt.html) In short, through an explicit code construct or static analysis, some static or dynamic extents of a thread's execution could be devoid of safepoints and barriers, running with maximal throughput. And what if the GC wants to end marking? The same dance as before: Compare and exchange operations ensure that either the GC puts the Mutator back into the BUSY state, or recognizes that the thread has stopped being busy. This actually requires a separate state or flag since we could otherwise not, at this point, differentiate between a thread that we had put into MARK vs. one that entered MARK itself. Perhaps we need a `BUSY_MARK` state. Anyhow, I'll figure it out. ### Greying Buffer The store barriers must be as cheap as possible. Barrier code that's executed by a Mutator could push objects to be greyed into a lockless queue consumed by a GC thread. From there, the GC could just transfer them to the Trace Work Set, or process them directly. This should probably be a statically bounded ring buffer or the like, which raises the question of what the Mutator does if it's full. I think the easiest solution is to ensure that it's drained after a bounded amount of work by the GC. Remember that at the leafs of our layered radix-based Work Set structure, we have small sub-structures that represent groups of objects co-inhabiting at most 1 MiB spans of the Meta Alloc heap. In the most egregious case, that could contain 128 Ki pointers to be greyed. Need to think about whether that's too much, or whether it would be OK to have a Mutator wait until that's done because the trace loop drains Mutator grey buffers after every such leaf node of the Work Set. Could also just do something super simple like increment a counter every time we process one pointer, so we stop to drain the Mutator greying buffers after every N greying operations. Easy.