Rename a note.

1 files changed, 0 insertions, 410 deletions

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