path: root/notes/260925-satb.md

# No-STW SATB

<!--TOC-->

_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.