Lock-Free Programming Fundamentals

A concurrent algorithm is lock-free if, whenever multiple threads operate on a shared data structure concurrently, at least one thread is guaranteed to make progress in a finite number of steps—even if the OS scheduler pauses or preempts any other arbitrary thread mid-operation.

Progress Guarantee Hierarchy

Treiber Lock-Free Stack (`AtomicPtr<Node<T>>` Head CAS Loop):

  head: AtomicPtr ---> [ Node B ] ---> [ Node A ] ---> null
                          ^
                          |
  New `Node C` sets `C.next = head` (`Node B`), then runs:
  `head.compare_exchange_weak(Node B, Node C, Release, Relaxed)`
    - If `head` is still `Node B`: `head` becomes `Node C` in 1 instruction!
    - If another thread pushed `Node D` first: update `C.next = Node D` and retry!

Implementing a Lock-Free Append-Only Stack (AtomicPtr)

An append-only (or batch-drained) lock-free stack avoids the ABA problem and concurrent memory reclamation hazards (where a popped node is freed while another thread is still reading its next pointer) because individual nodes are only freed when the entire stack is drained via swap(null_mut()) or dropped via &mut self:

use std::ptr;
use std::sync::atomic::{AtomicPtr, Ordering};
use std::thread;

struct Node<T> {
    value: T,
    next: *mut Node<T>,
}

pub struct LockFreeBag<T> {
    head: AtomicPtr<Node<T>>,
}

impl<T> LockFreeBag<T> {
    pub const fn new() -> Self {
        Self {
            head: AtomicPtr::new(ptr::null_mut()),
        }
    }

    pub fn push(&self, value: T) {
        let new_node = Box::into_raw(Box::new(Node {
            value,
            next: ptr::null_mut(),
        }));

        let mut current_head = self.head.load(Ordering::Relaxed);
        loop {
            // SAFETY: `new_node` is uniquely owned by this thread until CAS succeeds.
            unsafe {
                (*new_node).next = current_head;
            }

            match self.head.compare_exchange_weak(
                current_head,
                new_node,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual_head) => current_head = actual_head,
            }
        }
    }

    /// Atomically takes all elements out of the bag in LIFO order.
    pub fn drain_all(&self) -> Vec<T> {
        let mut head = self.head.swap(ptr::null_mut(), Ordering::Acquire);
        let mut items = Vec::new();
        while !head.is_null() {
            // SAFETY: `swap` with `Acquire` gave this caller exclusive ownership of
            // the entire linked list starting at `head`.
            unsafe {
                let boxed = Box::from_raw(head);
                head = boxed.next;
                items.push(boxed.value);
            }
        }
        items
    }
}

impl<T> Drop for LockFreeBag<T> {
    fn drop(&mut self) {
        let _ = self.drain_all();
    }
}

fn main() {
    let bag = LockFreeBag::new();

    thread::scope(|s| {
        for id in 1..=4 {
            s.spawn(move || {
                bag.push(id * 10);
            });
        }
    });

    let mut items = bag.drain_all();
    items.sort();
    println!("drained lock-free items: {:?}", items);
}

drained lock-free items: [10, 20, 30, 40]

The Two Major Pitfalls in General Lock-Free Data Structures

1. The ABA Problem: In a stack that supports concurrent single-element pop(), Thread 1 reads head = A (with A.next = B) and is preempted. Thread 2 pops A, pops B, frees B, allocates a new node that reuses address A, and pushes A back onto the stack. When Thread 1 resumes, its compare_exchange(A, B) succeeds even though B is now a dangling freed pointer!
2. Safe Memory Reclamation: Freeing a popped node immediately (Box::from_raw) while another thread is concurrently reading (*head).next inside its pop() CAS loop causes a use-after-free. Production lock-free queues (crossbeam-epoch) solve both problems using epoch-based memory reclamation or hazard pointers.