Linearizability, concurrent data structures and memory reclamation

Why it matters

"Is this concurrent structure correct?" needs a definition before it has an answer, and linearizability is the one most libraries, databases and key-value stores use. Lock-free code adds a second problem that garbage-collected languages hide: when may a removed node be freed while other threads might still be reading it? Getting this wrong produces use-after-free bugs that surface rarely, and usually only under load.

Core ideas

Linearizability. Every operation appears to take effect atomically at one instant, its linearization point, somewhere between invocation and response, and the resulting order is a legal sequential history. Operations that do not overlap must keep their real-time order. The condition is local: a system built from linearizable objects is linearizable, so you can reason one object at a time. Sequential consistency drops the real-time requirement; serializability concerns multi-object transactions and also ignores real time.

Finding linearization points. In a lock-based structure, any instant inside the critical section works. In a Treiber stack, push and pop take effect at their successful compare-and-swap on top. In the Michael-Scott queue, enqueue takes effect at the CAS that links the new node after the last node, and dequeue at the CAS that swings head, or at the read that finds the queue empty. When other threads may complete your operation for you (helping), the point can depend on later events, which is where proofs get hard.

Progress. Lock-free means some thread always completes within a finite number of steps, so a descheduled thread cannot block the others; wait-free means every thread completes within a bounded number of its own steps. Neither implies higher throughput: CAS retry loops under contention can be slower than a good lock.

ABA. CAS checks that a value is unchanged, not that nothing happened. Thread 1 reads top = A and A.next = B, then stalls. Other threads pop A, pop B and push A again (a reused node). Thread 1's CAS(top, A, B) succeeds and installs B, which is no longer in the stack. Fixes: pair the pointer with a version counter (double-width CAS), use LL/SC, or make sure a node is not reused while anyone can still see it, which is the reclamation problem.

Safe memory reclamation.

• Reference counting is simple, but every traversal writes shared counters, which creates contention.
• Hazard pointers: a reader publishes the pointer it is about to dereference, then re-validates it; a reclaimer frees only retired nodes that no hazard pointer names. Unreclaimed memory stays bounded, but each protected access costs a store and a fence.
• Epoch-based reclamation: threads announce the global epoch when entering a critical region, and a retired node is freed once every active thread has moved past the epoch in which it was retired. Reads are nearly free, but one stalled thread blocks all reclamation.
• RCU: readers take no locks and, in the classic kernel implementation, write no shared memory; writers publish a new version with release semantics, wait for a grace period in which all pre-existing readers finish, then free the old version. It suits read-mostly data such as routing tables and configuration.

C++26 adds standard library support for both hazard pointers and RCU.

Common misconceptions

• "Lock-free means faster." Its benefit is progress despite preemption or failure; throughput depends on contention.
• "Linearizability is serializability." One is about single operations on objects in real time, the other about transactions over many objects.
• "If the CAS succeeded, nothing changed." That is precisely the ABA trap.
• "Garbage collection solves all of this." It removes use-after-free and pointer reuse, not the need for correct linearization points and memory ordering.
• "Hazard pointers and epochs are interchangeable." They trade read-side cost against bounded memory and robustness to stalled threads.

How to approach it

Implement a Treiber stack, mark its linearization points in comments, construct the ABA interleaving with a deliberately reused node, and fix it twice. Check short recorded histories by hand or with a checker; stress tests alone miss rare interleavings. In interviews, define linearizability crisply, place linearization points, and explain one reclamation scheme with its tradeoff.