FerrousPath

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 — Arc in 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 A after reuse differs from the original A. 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 like take_all above 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: replace std::sync types 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

  1. Add is_empty and a pop to the first stack by guarding the whole structure with a spin lock. Benchmark against Mutex<Vec<T>> with 1, 4 and 16 threads.
  2. Reproduce the ABA scenario on paper for the unsound pop with three nodes, writing each thread’s steps on a timeline.
  3. Implement the Michael–Scott queue with crossbeam-epoch. Where are its linearization points?
  4. Write a loom test for the first stack with two pushing threads and assert that both values are present.
  5. Implement a single-producer single-consumer ring buffer with two AtomicUsize indices. Why does it need no reclamation and suffer no ABA?

Check your understanding

Pick an answer to see the explanation.

  1. 1.What does *lock-free* guarantee?

  2. 2.What is the ABA problem?

  3. 3.Why can a lock-free stack not simply Box::from_raw a node as soon as it is popped?

Key terms in this lesson

Finished the lesson and the exercises?