New note.

3 files changed, 132 insertions, 0 deletions

diff --git a/MetaAlloc.ods b/MetaAlloc.ods
index 943d14f..a3d88ea 100644
--- a/MetaAlloc.ods
+++ b/MetaAlloc.ods
diff --git a/notes/260922-use-alloc-3.md b/notes/260922-use-alloc-3.md
new file mode 100644
index 0000000..9ca98f7
--- /dev/null
+++ b/notes/260922-use-alloc-3.md
@@ -0,0 +1,131 @@
+# Using Meta Alloc, Attempt 3
+
+_2026 September_
+
+Here's a fairly concrete design proposal.
+
+## Block Alloc
+
+This is a simple manual alloc/free allocator, based on the Meta Alloc
+slabs/blocks, simply adding support for the more granular size classes
+we discussed earlier.
+
+It uses the coarse power-of-two Meta Alloc blocks for efficiently
+managing the backing memory.  (Not needing to use mmap all the time.)
+It simply uses thread-local free caches, occasionally flushed to or
+refreshed from shared free-lists.  (Meta Alloc does the same thing,
+just for larger blocks.)
+
+In short, Meta Alloc + Block Alloc simply offer a fairly simple,
+highly efficient, thread-safe, always O(1), multi-layered (slab ->
+block -> slot), completely general-purpose manual allocator with 56
+size classes.
+
+It still has the caveats that it requires a size argument to `free()`
+so it knows which size class the freed slot belongs to, and inherits
+the Meta Alloc limitation of 256 GiB total heap / 16 GiB per slab.
+(Every four size classes, roughly; first few classes being exceptions
+e.g. 8-byte size class gets an entire slab for itself.)
+
+## GC Alloc
+
+A fully concurrent (virtually "zero pause") mark-sweep tracing GC
+built on top of Meta Alloc, supporting the same 56 size classes as
+Block Alloc, with the following collection strategy:
+
+* For each Meta Alloc slab a "GC occupancy bitmap array" is allocated
+  in virtual memory via `mmap()`.  Each element (bitmap) of the array
+  corresponds to a Meta Alloc block, whose index is easily calculated
+  in few CPU instructions.
+
+* Using `gc_alloc()` sets bits in the GC occupancy bitmap for the
+  current block, acquiring a new block if needed.
+
+* If there are interleaved uses of the manual Block Alloc `alloc()`,
+  and `gc_alloc()`, then some bitmaps in the array remain zero, since
+  Block Alloc takes a Meta Alloc block and dedicates it to itself.
+  This isn't ideal, as it creates holes in the GC bitmap array, but
+  should be acceptable, and doesn't break the design.
+
+* When the concurrent mark phase begins, a fresh, seconary, all-zero
+  bitmap array is allocated.  (Or the previous one explicitly zeroed
+  out; may be faster than having fresh memory paged in.  We can swap
+  back and forth between two bitmap arrays.)
+
+* The new bitmap array is swapped in eagerly, so new allocations will
+  set bits directly in the new one.  Object graph tracing now begins,
+  locating live objects, setting bits in the new bitmap array.  Store
+  barriers are used to safely handle concurrent object graph mutation,
+  making sure the new bitmap array remains accurate.
+
+* When the mark phase has ended and concurrent sweeping begins, we
+  walk through the original (old, stored away) bitmap array and the
+  new (already swapped into place) bitmap array in parallel, using
+  "AND NOT" to identify memory slots that were live before the mark
+  phase (bit was set in original) but have been found not to be live
+  anymore (bit not set in new).
+
+* If an entire block comes out empty, we can release it directly back
+  to Meta Alloc.  Otherwise, we perform a `free()` on individual "now
+  dead" memory slots which does something similar to Block Alloc, but
+  freeing directly to the shared free-list of the appropriate size
+  class, instead of thread-local caches.  The mutator threads have
+  thread-local caches anyway, filled from the global free-list in
+  chunks, as an optimization.
+
+* We need a way to identify what size class a block is for.  Remember
+  that the blocks supporting multiple size classes use a `u32` but
+  don't need all bits in it; at most 25 bits are used for occupancy
+  data.  We can dedicate 2 bits at the "other end" of the integer to
+  identify which of the (up to 4 possible) size classes the block is
+  currently used for.
+
+* It may be good to double the size of each Meta Alloc block (i.e.,
+  smallest Meta Alloc size class becomes 256) so we can use `u64`
+  bitmaps instead of `u32` which should boost throughput.
+
+* The old bitmap array that was used to identify "previously live"
+  memory slots can be zeroed out and used as the new bitmap array in
+  the next GC cycle.
+
+It's possible to add a compaction phase to this design, using load
+barriers with colored pointers and whatnot, like ZGC.  It's unclear
+whether the CPU overhead would be justified; all it gives you is
+potentially improved spatial locality of objects in memory.
+
+Oh, and with regards to object pinning, Gemini gave me a really cool
+idea on how to do it efficiently:
+
+* A third bitmap array is used to represent pinned memory slots.
+
+* When the mark phase begins, it's used to "seed" the new bitmaps
+  (immediately marking those slots as live) and also as GC roots.
+
+* To prevent the need to scan the entire pinned objects bitmap array
+  which would typically be *very* sparsely populated, a "summary"
+  bitmap array is used, where one bit represents a span of N slots.
+  When pinning, the bit representing the relevant span is marked in
+  the summary bitmap, so during scanning we can look at the summary
+  and only scan the spans that have any bits in them at all.
+
+The span size N is probably best decided such that a bit represents a
+cache line i.e. 64 bytes i.e. 512 bits of the actual pinned objects
+bitmap array.  Assuming that one uses a u32 for the first two block
+sizes, and u64 beyond that, our bitmap memory needs are:
+
+| Slab | Regular Bitmap | Summary Bitmap |
+|------|----------------|----------------|
+| 1    | 256 MiB        | 0.5 MiB        |
+| 2    | 128 MiB        | 0.25 MiB       |
+| 3    | 128 MiB        | 0.25 MiB       |
+| 4    | 64 MiB         | 0.0125 MiB     |
+| 5    | (halve it...)  | (halve it...)  |
+| ...  | ...            | ...            |
+| SUM  | ~640 MiB       | ~1.25 MiB      |
+
+That's a very lean summary bitmap.  The regular bitmaps are bigger,
+and unfortunately there's three of them, but that still gives us:
+
+    (3 * 640 MiB) / 256 GiB ~= 0.73% metadata overhead
+
+That's quite good I think.
diff --git a/notes/index.md b/notes/index.md
index 10bbd93..a9faf3d 100644
--- a/notes/index.md
+++ b/notes/index.md
@@ -43,3 +43,4 @@
 * [Memory management of code](260825-code-gc.html)
 * [Using Meta Alloc](260826-use-alloc.html)
 * [Using Meta Alloc, Attempt 2](260920-use-alloc-2.html)
+* [Using Meta Alloc, Attempt 3](260922-use-alloc-3.html)