Module shared_treiber_stack

Expand description

SharedTreiberStack<T> - cross-process lock-free LIFO stack.

Classic Treiber-stack pattern: a packed (counter, head_index) atomic head, ABA-safe via the counter wrap. Push and pop are CAS loops bounded only by contention rate (not by logical waiting conditions).

§Companion to other queue primitives

SharedRing: MPMC FIFO with fixed slot ordering
SharedBroadcastRing: 1P+NC pub/sub
SharedTreiberStack: MPMC LIFO (this one)

§Safety properties

Bounded capacity at create time; push returns Err(Full) when capacity is exhausted.
ABA-safe via 32-bit counter packed with index in the head atomic; same proven design as SharedRegion’s free list.
CAS loops are contention-bounded, not logical-condition bounded. Each retry happens because another writer won the race; eventually contention resolves.
No RAII guards with Drop semantics that risk being aliased or double-released. Push and pop return owned values.
No underflow: pop returns None on empty rather than wrapping a counter.

§Layout

+---------------------------+
| StackHeader (64B)         |
|   magic, capacity         |
|   head: AtomicU64         |  // (counter << 32) | top_index, NIL when empty
|   free_head: AtomicU64    |  // free-list of returned slots
|   bump_next: AtomicU32    |
+---------------------------+
| next[capacity: AtomicU32] |  // chain pointers (overlap usage as free + occupied)
+---------------------------+
| slots[capacity * size_of<T>] |
+---------------------------+