pub unsafe fn splice_foreign(
seg: &Segment,
head: *mut u8,
tail: *mut u8,
live_sum: usize,
bytes_sum: usize,
)Expand description
Push a slot onto a segment’s foreign-free stack.
§Why this is push-only, and why that matters
A Treiber stack’s ABA hazard lives in pop: a consumer reads
head.next, and between that read and its compare-and-swap another
thread can pop, push other nodes, and push the same address back —
so the CAS succeeds against a stale next. torajs-mmalloc documents
the hazard and accepts it, reasoning that its runtime is
single-threaded. kevy is not: values are shared across shards on the
read lane, so a foreign free is ordinary, and inheriting that note
would be inheriting a bug.
The fix is structural rather than defensive. Only the owning shard
ever removes anything, and it removes the entire list with one
swap. There is no compare-and-swap on the consumer side, so
there is no window for ABA to open. Producers only ever push. This
is mimalloc’s thread-free design, and it is strictly simpler than
tagged pointers or hazard pointers would have been.
Splice a pre-linked chain of freed slots onto a segment’s foreign
list, and post the batch’s byte sums. One CAS and two fetch_adds
for the whole chain — this is the amortisation M1 forced: the per-op
version of this function was three atomic RMWs on this same line for
every single foreign free, and cross-shard KV paid 18–39 % for it.
The chain format is unchanged from the per-op era: each slot’s first
word links to the next, with the requested size at
FOREIGN_SIZE_OFFSET — the owner’s drain cannot tell a spliced
batch from a thousand individual pushes.
§Safety
head..tail must be a chain of live slot addresses belonging to
seg, linked through their first words, referenced by nobody else;
live_sum/bytes_sum must be the chain’s requested/slot-byte sums.