Rename a note.

1 files changed, 410 insertions, 0 deletions

diff --git a/notes/260925-gc.md b/notes/260925-gc.md
new file mode 100644
index 0000000..f951135
--- /dev/null
+++ b/notes/260925-gc.md
@@ -0,0 +1,410 @@
+# 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.