Skip to main content

Module shared_region

subetha_cxc

Module shared_region 

Source
Expand description

SharedRegion<T> - cross-process typed arena with position- independent OffsetPtr<T> references.

The foundational building block for cross-process pointer-bearing data structures (BTree nodes, trie nodes, linked lists, any pointer-graph). Pointers are OffsetPtr<T> { index: u32 } which resolve via mmap_base + index * size_of::<T>() in any process.

§Layout

+----------------------------+
| RegionHeader (64B aligned) |
|   magic, capacity          |
|   bump_next: AtomicU64     |
|   free_head: AtomicU64     |  (counter << 32 | index)
+----------------------------+
| next[capacity]             |  (free-list links, when slot free)
+----------------------------+
| slots[capacity]            |  (T payloads, size_of<T> each)
+----------------------------+

Free-list links live in a separate next[capacity] array (not union’d into T storage) because T need not be 4-byte aligned. The cost is 4 * capacity extra bytes; the gain is layout simplicity and zero overhead on the T storage.

§Concurrent allocation protocol

Allocate:

  1. Try to pop from free_head (lock-free Treiber stack):
    • Load packed (counter, index).
    • If index == NIL_INDEX, free list is empty; fall through.
    • Read next[index]; CAS free_head to (counter+1, next).
    • On success, return OffsetPtr { index }.
  2. Bump alloc: bump_next.fetch_add(1, AcqRel).
    • If the returned index >= capacity, rollback and return Full.
    • Write value into slots[index]; return OffsetPtr { index }.

Free:

  1. Read current (counter, head) from free_head.
  2. Write head into next[ptr.index].
  3. CAS free_head to (counter+1, ptr.index).
  4. On CAS lose, retry from step 1.

§ABA safety

The 32-bit counter prevents ABA: every push bumps the counter, so the packed word is different even when an index repeats. 32 bits of counter span 4B operations, which is far beyond any realistic concrete race window.

§No drop semantics

T: Copy + Sized. Allocated T values are NOT dropped on free (Copy types don’t need drop, and we can’t run drop glue on bytes living in shared memory anyway). free returns the value as a by-copy.

Structs§

OffsetPtr
Position-independent pointer to a slot in a SharedRegion. Stable across processes because the underlying MMF is byte-identical; adding mmap_base + ptr.index * size_of::<T>() resolves in any process.
RegionHeader
SharedRegion

Enums§

RegionError

Constants§

NIL_INDEX
REGION_MAGIC

Functions§

region_file_size