Amend last note.

1 files changed, 82 insertions, 14 deletions

diff --git a/notes/260925-satb.md b/notes/260925-satb.md
index 2d72eb8..f951135 100644
--- a/notes/260925-satb.md
+++ b/notes/260925-satb.md
@@ -223,8 +223,8 @@ the order of events:
    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 count
-   as box objects on the heap, so to speak; write barrier applies.)
+   (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
@@ -266,11 +266,11 @@ the order of events:
 
    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
+   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.)
+   then dropped.
 
    The solution is a *Dijkstra-style insertion barrier* AKA *Dijkstra
    barrier* which is another kind of write barrier: It intercepts the
@@ -300,8 +300,6 @@ the order of events:
    The Dijkstra barrier is disabled again for a Mutator thread once
    it's scanned its roots and entered the MARK state.
 
-   Wow, this was a lot of text for a list point...
-
    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.
@@ -315,14 +313,12 @@ the order of events:
    into the Work Set.  So, the GC enters the FREE state and begins
    waiting.
 
-   There's one important nuance to keep in mind here: Mutators may
-   continue to put the same Black objects into the Work Set over and
-   over again due to barrier behavior (explained below), so tracing
-   could get stuck in a loop if we're not careful.  The trace loop
-   must be able to deal with this edge case, noticing that all new
-   additions to the Work Set that it found during an iteration were
-   Black, *and* all Mutators were in the MARK state already at the
-   start of that iteration.  This condition must terminate the loop.
+   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
@@ -340,3 +336,75 @@ 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.