A lock-free freelist pops a node by reading head, reading the next of that node, then compare-and-swapping head from the old node to that next. Construct the interleaving that corrupts the list, then give two fixes with their costs.

A lock-free freelist pops a node by reading head, reading the next of that node, then compare-and-swapping head from the old node to that next. Construct the interleaving that corrupts the list, then give two fixes with their costs.

Approach: Let one thread stall between reading the next pointer and its compare and swap, and have other threads recycle the same address in that window.

Thread A reads head as node X and reads the next of X as Y, then stalls; thread B pops X, pops Y, and pushes X back, so head is X again with its next now Z; thread A resumes, its compare and swap sees X and succeeds, and head is set to Y, which is no longer in the list. This is the ABA problem: a compare and swap compares a value rather than the history of the location, and the value returned to its original while the meaning changed underneath. The first fix is a tagged pointer, packing a monotonically increasing counter beside the pointer so a reuse changes the compared word, which costs a 128 bit double width atomic and a 16 byte alignment requirement. The second is hazard pointers or epoch based reclamation, which stop a node being reused while any thread may still reference it, at the cost of deferred frees and a retire list that grows under load.

Follow-up: Why does a garbage collected runtime make this particular bug disappear, and which lock-free bug does it leave in place?

Key concepts: aba problem, compare and swap, tagged pointer, hazard pointers.