Level 4 · Expert· Lesson 6 of 9 · 40 min
Lock-free data structures
Progress guarantees, the Treiber stack, the ABA problem, memory reclamation with epochs and hazard pointers, and linearizability.
Progress guarantees
| Property | Guarantee |
|---|---|
| Blocking | A thread holding a lock can stall everyone (if it is descheduled, or dies). |
| Obstruction-free | A thread running alone completes in a bounded number of steps. |
| Lock-free | Some thread always completes in a bounded number of steps. Individual threads may starve. |
| Wait-free | Every thread completes in a bounded number of its own steps. |
Lock-free does not mean faster. It means no thread can prevent the system from making progress — valuable in signal handlers, interrupt contexts, real-time code, and under heavy contention. A well-tuned mutex often wins on throughput. Measure.
The Treiber stack
The simplest lock-free structure (Treiber, 1986) is a linked stack whose head is an atomic pointer.
use std::ptr;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::thread;
struct Node<T> {
value: T,
next: *mut Node<T>,
}
pub struct Stack<T> {
head: AtomicPtr<Node<T>>,
}
// SAFETY: values are moved between threads through the stack; nodes are owned by it.
unsafe impl<T: Send> Send for Stack<T> {}
unsafe impl<T: Send> Sync for Stack<T> {}
impl<T> Stack<T> {
pub const fn new() -> Self {
Stack { head: AtomicPtr::new(ptr::null_mut()) }
}
pub fn push(&self, value: T) {
let node = Box::into_raw(Box::new(Node { value, next: ptr::null_mut() }));
let mut head = self.head.load(Ordering::Relaxed);
loop {
// SAFETY: `node` is not yet shared; we are its only owner.
unsafe { (*node).next = head };
// Release: publish the node's contents to whoever loads `head`.
match self.head.compare_exchange_weak(head, node, Ordering::Release, Ordering::Relaxed) {
Ok(_) => return,
Err(actual) => head = actual,
}
}
}
/// Removes every element at once. Safe from ABA and from use-after-free,
/// because after the swap this thread owns the entire detached list.
pub fn take_all(&self) -> Vec<T> {
let mut node = self.head.swap(ptr::null_mut(), Ordering::Acquire);
let mut out = Vec::new();
while !node.is_null() {
// SAFETY: the list was detached atomically; no other thread can reach these nodes.
let boxed = unsafe { Box::from_raw(node) };
node = boxed.next;
out.push(boxed.value);
}
out
}
}
impl<T> Drop for Stack<T> {
fn drop(&mut self) {
self.take_all();
}
}
fn main() {
let stack = Stack::new();
thread::scope(|s| {
for t in 0..4u32 {
let stack = &stack;
s.spawn(move || for i in 0..1000 { stack.push(t * 1000 + i) });
}
});
let mut all = stack.take_all();
all.sort_unstable();
println!("{} items, all distinct: {}", all.len(), all.windows(2).all(|w| w[0] != w[1]));
}
push is the canonical CAS loop: read the head, prepare the node, try to swing the head, retry on failure. It is correct as written.
Notice what is missing: a pop that removes one element. That is where the difficulty lives.
Why pop is hard
The obvious implementation:
// ⚠ UNSOUND — do not use. Shown to explain the bugs.
pub fn pop(&self) -> Option<T> {
loop {
let head = self.head.load(Ordering::Acquire);
if head.is_null() {
return None;
}
let next = unsafe { (*head).next }; // (1) dereference
if self.head.compare_exchange_weak(head, next, // (2) swing head
Ordering::AcqRel, Ordering::Relaxed).is_ok()
{
let node = unsafe { Box::from_raw(head) }; // (3) free
return Some(node.value);
}
}
}
Bug 1 — use-after-free. Thread A loads head and is descheduled before step (1). Thread B pops the same node and frees it at (3). Thread A resumes and dereferences freed memory.
Bug 2 — ABA. The stack is A → B → C. Thread 1 reads head = A, next = B, and pauses. Thread 2 pops A, pops B (freeing it), and pushes a new node that the allocator places at address A. The stack is now A → C. Thread 1 resumes; its CAS sees head == A and succeeds, installing B — a freed node — as the head.
Both stem from one fact: in a lock-free structure, unlinking a node does not mean nobody still holds a pointer to it. Garbage-collected languages never see either bug, because a node cannot be freed or reused while referenced. In Rust you need a safe memory reclamation scheme.
Memory reclamation
Epoch-based reclamation
Threads announce when they are inside a critical region (“pinned”). A global epoch advances only when every pinned thread has observed the current one. A node unlinked in epoch e may be freed once the epoch reaches e + 2, because by then no thread pinned during e can remain.
- Very low overhead on the read path — pin and unpin are a couple of thread-local operations.
- A stalled pinned thread delays all reclamation: memory use is unbounded in the worst case.
crossbeam-epoch implements this. A correct Treiber stack with it:
// crate: crossbeam-epoch
use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::mem::ManuallyDrop;
use std::ptr;
use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
struct Node<T> {
value: ManuallyDrop<T>,
next: Atomic<Node<T>>,
}
pub struct Stack<T> {
head: Atomic<Node<T>>,
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack { head: Atomic::null() }
}
pub fn push(&self, value: T) {
let mut node = Owned::new(Node { value: ManuallyDrop::new(value), next: Atomic::null() });
let guard = epoch::pin();
loop {
let head = self.head.load(Relaxed, &guard);
node.next.store(head, Relaxed);
match self.head.compare_exchange(head, node, Release, Relaxed, &guard) {
Ok(_) => return,
Err(e) => node = e.new, // take the node back and retry
}
}
}
pub fn pop(&self) -> Option<T> {
let guard = epoch::pin(); // while pinned, nodes we can see will not be freed
loop {
let head = self.head.load(Acquire, &guard);
// SAFETY: `head` was read while pinned, so it is either null or still allocated.
let node = unsafe { head.as_ref() }?;
let next = node.next.load(Relaxed, &guard);
if self.head.compare_exchange(head, next, Release, Relaxed, &guard).is_ok() {
// SAFETY: the CAS succeeded, so we unlinked the node and are the only thread
// that will read its value. Freeing is deferred until no pinned thread remains.
unsafe {
guard.defer_destroy(head);
return Some(ptr::read(&*node.value));
}
}
}
}
}
fn main() {
let s = Stack::new();
std::thread::scope(|scope| {
for t in 0..4 {
let s = &s;
scope.spawn(move || for i in 0..1000 { s.push(t * 1000 + i); s.pop(); });
}
});
println!("empty afterwards: {}", s.pop().is_none());
}
Pinning fixes use-after-free directly, and it fixes ABA as well: an address cannot be reused while any thread that might still compare against it is pinned.
Hazard pointers
Each thread publishes, in a shared slot, the pointer it is about to dereference, then re-checks that the pointer is still reachable. A thread wanting to free a node scans all hazard slots; nodes that appear there are kept for later.
- Bounded garbage: at most (threads × hazards per thread) nodes are ever awaiting reclamation.
- Each protected access costs a store and a
SeqCst-style fence, so reads are slower than with epochs.
Crates: haphazard, seize (a hybrid scheme).
Other strategies
- Reference counting —
Arcin an atomic slot (arc-swap), or split/differential counts. Simple; puts writes on the read path. - Tagged pointers / version counters — pack a counter into the pointer’s unused bits (or use a double-width CAS) so that
Aafter reuse differs from the originalA. Solves ABA but not use-after-free; adequate when nodes come from a pool that is never returned to the allocator. - Avoid the problem. Single-consumer queues, bounded array queues (
crossbeam::ArrayQueue), and “take everything” operations liketake_allabove need no reclamation scheme at all.
Correctness: linearizability
How do you even state that a concurrent stack is correct? The standard criterion (Herlihy and Wing, 1990) is linearizability: every operation appears to take effect atomically at some single instant — its linearization point — between its invocation and its response, and the resulting sequential history is legal for the data type.
For the Treiber stack the linearization point of a successful push or pop is its successful CAS; for a pop that returns None, it is the load that read null. Identifying those points is the first step of any correctness argument, and of any formal proof.
Testing
loom: replacestd::synctypes with loom’s, write small tests, and loom explores every interleaving within bounds — including weak-memory outcomes. Indispensable.- Miri with many seeds (
-Zmiri-many-seeds) for data races and use-after-free. - ThreadSanitizer and stress tests on many-core ARM hardware.
- Linearizability checkers that record histories and search for a valid sequential order.
Prefer audited implementations — crossbeam, parking_lot, dashmap, flume — to your own. Write your own to learn, with all of the tools above switched on.
Further reading
- Herlihy and Shavit, The Art of Multiprocessor Programming — the textbook.
- Michael and Scott (1996), “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”.
- Michael (2004), “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”.
- Fraser (2004), Practical Lock-Freedom — the origin of epoch-based reclamation.
- Aaron Turon (2015), “Lock-freedom without garbage collection” — the design behind
crossbeam-epoch.
Exercises
- Add
is_emptyand apopto the first stack by guarding the whole structure with a spin lock. Benchmark againstMutex<Vec<T>>with 1, 4 and 16 threads. - Reproduce the ABA scenario on paper for the unsound
popwith three nodes, writing each thread’s steps on a timeline. - Implement the Michael–Scott queue with
crossbeam-epoch. Where are its linearization points? - Write a
loomtest for the first stack with two pushing threads and assert that both values are present. - Implement a single-producer single-consumer ring buffer with two
AtomicUsizeindices. Why does it need no reclamation and suffer no ABA?
Check your understanding
Pick an answer to see the explanation.
1.What does *lock-free* guarantee?
2.What is the ABA problem?
3.Why can a lock-free stack not simply
Box::from_rawa node as soon as it is popped?