# 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 a block was completely full, but is now completely empty, we can
  free it back to Meta Alloc.  (If only some slots were occupied and
  now the whole block is empty, we can't free it, since some of its
  unoccupied slots may be in a free-list.)

* Otherwise, we `free()` individual "now dead" memory slots in it,
  which works similarly to the `free()` of Block Alloc, but putting
  the slots directly into the shared free-list of the size class, in
  chunks to decrease contention.  (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.