Rust 101 🦀 Lock-Free Data Structures and Atomic Operations (std::sync::atomic) - KandZ

⏱️ Estimated read: 16 min | |

A lock-free data structure is one where at least one thread can always make progress, even when other threads are stalled, preempted, or killed mid-operation. This guarantee is stronger than a mutex-based structure, where a thread holding the lock can block every other thread indefinitely. The tool that makes lock-free programming possible in Rust is the std::sync::atomic module: a set of types whose operations complete in a single, indivisible step, with no internal mutex and no risk of tearing .

This chapter covers the atomic primitives and the lock-free patterns built on them. It begins with the Ordering enum, which determines how atomic operations synchronize memory across threads, and explains why SeqCst is the safe default rather than the fastest choice. It then examines the compare-and-swap loop that underlies most lock-free algorithms, the ABA problem that makes naive CAS loops unsound for pointer-based structures, and the memory reclamation strategies that solve it. The final sections address the practical reality: when lock-free is worth the complexity, and why the crossbeam ecosystem exists for the cases where it is.

Key point: Lock-free does not mean wait-free. A lock-free algorithm guarantees that the system as a whole makes progress, but an individual thread can retry its CAS loop indefinitely under contention. The guarantee is about the system, not the thread.

Why atomics exist

The data race problem. An ordinary read-modify-write operation like counter += 1 is not atomic. It compiles to a load, an add, and a store, and another thread can interleave between any of those steps. The result is a lost update: two threads read the same value, both add one, both write the same result, and the counter advances by one instead of two. Atomics provide operations that the hardware guarantees cannot be split .

The compiler reordering problem. The compiler and the CPU reorder instructions for performance. A write that appears before a read in the source code may execute after it on the actual hardware. Atomics with the appropriate Ordering act as barriers that prevent this reordering, ensuring that memory writes are visible to other threads in the order the programmer intended .

The blocking cost. A Mutex is correct, but it serializes access. Under high contention, threads spend more time waiting for the lock than doing work, and the operating system may put them to sleep and wake them, adding context-switch overhead. A lock-free data structure replaces the lock with a compare-and-swap loop: threads that fail retry immediately, and the system as a whole makes progress without the OS scheduler’s intervention .

The reclamation hazard. In a lock-free linked list or stack, a thread may read a pointer to a node, and another thread may remove and free that node before the first thread dereferences it. The result is a use-after-free. Solving this requires a memory reclamation strategy—hazard pointers, epoch-based reclamation, or tagged pointers—that is often more complex than the lock-free algorithm itself .

a. Atomic types and memory ordering

The std::sync::atomic module provides atomic versions of the primitive integer types (AtomicUsize, AtomicU64, AtomicBool, etc.) and a pointer type, AtomicPtr<T> . Each type supports a set of methods—load, store, swap, compare_exchange, and arithmetic operations like fetch_add—and each method takes an Ordering argument.

Ordering is an enum with five variants, borrowed from C++20’s memory model . Relaxed provides atomicity but no synchronization: the operation itself is indivisible, but the compiler and CPU can reorder other memory operations around it. Acquire on a load ensures that subsequent reads and writes cannot be moved before the load. Release on a store ensures that previous reads and writes cannot be moved after the store. AcqRel combines both for read-modify-write operations. SeqCst adds a total global order across all threads, which is the strongest guarantee and the easiest to reason about .

use std::sync::atomic::{AtomicUsize, Ordering};

// A counter shared between threads.
static COUNTER: AtomicUsize = AtomicUsize::new(0);

// Relaxed: atomic, but no ordering guarantees for other data.
// Suitable for a standalone counter with no correlated state.
COUNTER.fetch_add(1, Ordering::Relaxed);

// Acquire on a load: subsequent reads see writes that happened
// before the matching Release store.
let value = COUNTER.load(Ordering::Acquire);

// Release on a store: previous writes are visible to any thread
// that performs an Acquire load of this value.
COUNTER.store(value + 1, Ordering::Release);

The pairing of Release and Acquire is the core synchronization pattern. A thread that writes data and then stores a flag with Release guarantees that the data is visible to any thread that loads the flag with Acquire and sees the expected value. This is how atomics are used to publish data between threads without a mutex .

SeqCst is the default recommendation for code that does not have a measured reason to use something weaker. The performance difference between SeqCst and Acquire/Release is negligible on x86-64, and the reasoning burden is significantly lower. Weaker orderings are for hot paths where the synchronization pattern has been proven correct and benchmarked .

b. The compare-and-swap loop

The compare_exchange method is the cornerstone of lock-free programming . It atomically checks whether the current value equals an expected value, and if so, replaces it with a new value. If not, it returns the actual current value and the operation fails. The loop that retries on failure is the fundamental lock-free algorithm.

use std::sync::atomic::{AtomicUsize, Ordering};

// A lock-free increment: read, try to CAS, retry on failure.
fn increment(counter: &AtomicUsize) {
    let mut current = counter.load(Ordering::Relaxed);
    loop {
        match counter.compare_exchange_weak(
            current,
            current + 1,
            Ordering::SeqCst,
            Ordering::Relaxed,
        ) {
            Ok(_) => return,          // success
            Err(actual) => current = actual, // retry with fresh value
        }
    }
}

The compare_exchange_weak variant may fail spuriously even when the value matches, which allows it to be implemented more efficiently on some architectures. compare_exchange (without _weak) does not fail spuriously and is appropriate when a spurious failure would be incorrect or wasteful. For retry loops, _weak is the conventional choice .

The loop’s correctness depends on the assumption that the expected value remains comparable. For a counter, this is true: the value is a number, and a failed CAS means another thread incremented it, which is exactly the situation the loop handles. For a pointer-based data structure, the assumption is fragile. A pointer can be freed and a new node allocated at the same address, making the CAS succeed when it should fail. This is the ABA problem .

c. The ABA problem and memory reclamation

The ABA problem occurs when a value changes from A to B and back to A between a thread’s read and its compare-and-swap. The CAS succeeds because the value matches, but the data structure has changed in a way the thread did not observe . In a lock-free stack, this could mean a node was popped, freed, and a new node allocated at the same address, and the thread’s CAS links the new node into a list where the old node’s successor is no longer valid.

Tagged pointers are the classical solution: attach a version counter to the pointer, so that the CAS compares both the pointer and the counter. If the pointer is reused, the counter has advanced, and the CAS fails. On platforms with spare bits in the pointer, the tag can be stored inline; otherwise, a AtomicU128 or a separate counter is used .

Epoch-based reclamation is the modern solution used by the crossbeam-epoch crate. It defers freeing a node until all threads that might have a reference to it have finished their operations. Each thread announces an epoch, and a node removed in epoch N is freed only after all threads have advanced past epoch N .

use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::sync::atomic::Ordering;

// A lock-free stack node.
struct Node<T> {
    data: T,
    next: Atomic<Node<T>>,
}

// Push with crossbeam-epoch: the guard protects the lifetime
// of nodes that other threads may still be reading.
fn push<T>(head: &Atomic<Node<T>>, value: T) {
    let guard = epoch::pin();
    let node = Owned::new(Node {
        data: value,
        next: Atomic::null(),
    });
    let mut node = node.into_shared(&guard);
    loop {
        let current = head.load(Ordering::Relaxed, &guard);
        unsafe { node.deref_mut().next.store(current, Ordering::Relaxed); }
        match head.compare_exchange_weak(
            current,
            node,
            Ordering::Release,
            Ordering::Relaxed,
            &guard,
        ) {
            Ok(_) => return,
            Err(_) => continue,
        }
    }
}

The crossbeam ecosystem exists because getting these details right is difficult. The crossbeam-epoch crate provides the reclamation mechanism, and the crossbeam-skiplist crate provides a lock-free ordered map built on it . For most applications, using these libraries is the correct choice rather than implementing the reclamation logic from scratch.

Complete Example Session

// ============================================
// PART 1: THE ATOMIC COUNTER
// ============================================
// The simplest lock-free primitive: a shared counter.

use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;
use std::thread;

let counter = Arc::new(AtomicUsize::new(0));
let mut handles = vec![];

for _ in 0..10 {
    let counter = Arc::clone(&counter);
    handles.push(thread::spawn(move || {
        for _ in 0..1000 {
            counter.fetch_add(1, Ordering::Relaxed);
        }
    }));
}

for h in handles { h.join().unwrap(); }
assert_eq!(counter.load(Ordering::SeqCst), 10_000);

// ============================================
// PART 2: THE CAS LOOP
// ============================================
// A manual increment using compare_exchange.

fn increment(counter: &AtomicUsize) {
    let mut current = counter.load(Ordering::Relaxed);
    loop {
        match counter.compare_exchange_weak(
            current,
            current + 1,
            Ordering::SeqCst,
            Ordering::Relaxed,
        ) {
            Ok(_) => return,
            Err(actual) => current = actual,
        }
    }
}

// ============================================
// PART 3: THE SPIN LOCK
// ============================================
// A lock built from a single atomic bool.
// Not lock-free (a thread that holds the lock blocks others),
// but built from the same primitives.

use std::sync::atomic::AtomicBool;
use std::hint;

struct SpinLock {
    locked: AtomicBool,
}

impl SpinLock {
    fn new() -> Self {
        SpinLock { locked: AtomicBool::new(false) }
    }

    fn lock(&self) {
        while self.locked.compare_exchange_weak(
            false, true, Ordering::Acquire, Ordering::Relaxed
        ).is_err() {
            hint::spin_loop();
        }
    }

    fn unlock(&self) {
        self.locked.store(false, Ordering::Release);
    }
}

// ============================================
// PART 4: THE LOCK-FREE STACK (CONCEPTUAL)
// ============================================
// Treiber's stack: push and pop on an atomic head pointer.
// Raw pointers require unsafe, and reclamation requires
// a strategy (epochs, hazard pointers, or tags).

// The core push:
// 1. Allocate a new node.
// 2. Point its next to the current head.
// 3. CAS head from current to new node.

// The core pop:
// 1. Load the current head.
// 2. If null, return None.
// 3. Read head.next.
// 4. CAS head from current to head.next.
// 5. If success, return the node's value.

// ============================================
// PART 5: THE ABA HAZARD
// ============================================
// A thread reads head = A, then A is popped,
// freed, and a new node is allocated at the same
// address. The thread's CAS succeeds, but the
// structure has changed.

// Solution: tagged pointers or epoch-based reclamation.

// ============================================
// PART 6: THE CROSSBEAM APPROACH
// ============================================
// The crossbeam-epoch crate handles reclamation.

use crossbeam_epoch::{self as epoch, Atomic, Owned};

struct Node {
    value: u64,
    next: Atomic<Node>,
}

fn push(head: &Atomic<Node>, value: u64) {
    let guard = epoch::pin();
    let node = Owned::new(Node {
        value,
        next: Atomic::null(),
    });
    let mut node = node.into_shared(&guard);
    loop {
        let current = head.load(Ordering::Relaxed, &guard);
        unsafe { node.deref_mut().next.store(current, Ordering::Relaxed); }
        match head.compare_exchange_weak(
            current, node, Ordering::Release, Ordering::Relaxed, &guard,
        ) {
            Ok(_) => return,
            Err(_) => continue,
        }
    }
}

// ============================================
// PART 7: THE ORDERING DECISION
// ============================================
// Relaxed for standalone counters.
// Acquire/Release for publishing data.
// SeqCst for correctness-critical synchronization
// without a benchmarked reason to weaken.

let flag = AtomicBool::new(false);

// Thread 1: write data, then signal with Release.
// data = 42;
// flag.store(true, Ordering::Release);

// Thread 2: wait for flag with Acquire, then read data.
// while !flag.load(Ordering::Acquire) { spin_loop(); }
// assert_eq!(data, 42);

// ============================================
// PART 8: THE FETCH OPERATIONS
// ============================================
// fetch_add, fetch_sub, fetch_or, fetch_and, fetch_xor.
// Each returns the previous value.

let x = AtomicUsize::new(10);
let old = x.fetch_add(5, Ordering::SeqCst);
assert_eq!(old, 10);
assert_eq!(x.load(Ordering::SeqCst), 15);

// ============================================
// PART 9: THE PORTABILITY CAVEAT
// ============================================
// Not all platforms support all atomics.
// AtomicU64 is missing on 32-bit PowerPC and MIPS.
// ARMv5te without Linux support lacks CAS operations.
// Use #[cfg(target_has_atomic)] for portable code.

// ============================================
// PART 10: THE FULL PICTURE
// ============================================
// Atomics are the building blocks. Lock-free structures
// are the applications. Reclamation is the hard part.

fn main() {
    let lock = SpinLock::new();
    lock.lock();
    // critical section
    lock.unlock();
}

The ten parts build from the simplest atomic counter to the reclamation-aware stack, with the ordering decisions and portability caveats that determine whether the code is correct and portable. The key observation is that the atomic operations themselves are straightforward; the difficulty lies in the memory ordering reasoning and the reclamation strategy.

Quick Reference

Ordering Variants

Ordering	Use	Guarantee
`Relaxed`	Standalone counters	Atomicity only
`Acquire`	Load after waiting	Subsequent reads see prior writes
`Release`	Store to signal	Prior writes visible to Acquire
`AcqRel`	Read-modify-write	Both Acquire and Release
`SeqCst`	Default safe choice	Total global order

Atomic Methods

Method	Purpose	Returns
`load`	Read value	Value
`store`	Write value	—
`swap`	Exchange	Old value
`compare_exchange`	CAS	`Result<old, actual>`
`fetch_add`	Add	Previous value

Reclamation Strategies

Strategy	Crate	Complexity
Tagged pointers	Manual	Medium
Hazard pointers	Manual / `haphazard`	High
Epoch-based	`crossbeam-epoch`	Low (library)

Portability

Platform	Limitation
32-bit PowerPC/MIPS	No `AtomicU64`
ARMv5te (non-Linux)	No CAS operations
ARM thumbv6m	No CAS operations

Best Practices

✅ Do This:

// Use SeqCst unless benchmarked otherwise.
counter.fetch_add(1, Ordering::SeqCst);                              // ✅

// Pair Release store with Acquire load.
flag.store(true, Ordering::Release);                                 // ✅
while !flag.load(Ordering::Acquire) { spin_loop(); }                 // ✅

// Use compare_exchange_weak in retry loops.
match counter.compare_exchange_weak(...) { ... }                     // ✅

// Use crossbeam-epoch for pointer-based structures.
let guard = epoch::pin();                                            // ✅

// Document the invariant each ordering relies on.
// Release: data is visible after the flag is set.                   // ✅

❌ Don’t Do This:

// Don't use Relaxed when synchronization is needed.
flag.store(true, Ordering::Relaxed); // data may not be visible      // ❌

// Don't ignore the ABA problem in pointer CAS loops.
head.compare_exchange(old, new, ...); // old may be recycled         // ❌

// Don't assume lock-free means wait-free.
// A thread can retry indefinitely under contention.                // ❌

// Don't use atomics for compound operations.
// Two atomic operations are not atomic together.                   // ❌

// Don't forget portability constraints.
AtomicU64::new(0); // not on 32-bit PowerPC                           // ❌

Common Pitfalls

Pitfall	Why It Happens	Fix
Lost update	Non-atomic read-modify-write	Use `fetch_add` or CAS loop
Data not visible	Missing Acquire/Release pairing	Use `Release` store, `Acquire` load
ABA corruption	Pointer reused after free	Tagged pointers or epoch reclamation
Infinite retry	CAS loop under high contention	Consider a mutex for high contention
Portability failure	Atomic type missing on target	`#[cfg(target_has_atomic)]`
Reordering bug	Relaxed used for synchronization	Use SeqCst or explicit Acquire/Release

Real-World Examples

1. Atomic Counter

static COUNT: AtomicUsize = AtomicUsize::new(0);
COUNT.fetch_add(1, Ordering::Relaxed);

2. Flag Publication

ready.store(true, Ordering::Release);

3. Flag Wait

while !ready.load(Ordering::Acquire) { spin_loop(); }

4. CAS Increment

counter.compare_exchange_weak(n, n + 1, SeqCst, Relaxed)

5. Spin Lock

while lock.compare_exchange_weak(false, true, Acquire, Relaxed).is_err() {}

6. Epoch Pin

let guard = crossbeam_epoch::pin();

7. Atomic Pointer

let ptr: AtomicPtr<Node> = AtomicPtr::new(null_mut());

8. Fetch OR

flags.fetch_or(0b100, Ordering::SeqCst);

9. Swap

let old = value.swap(new, Ordering::SeqCst);

10. AcqRel for RMW

counter.fetch_add(1, Ordering::AcqRel);

Visual

The Ordering Guarantees

┌─────────────────────────────────────────────────────────┐
│  RELAXED                                                │
│  Atomic, no reordering constraints.                     │
│  Other memory can move freely around it.                │
│                                                         │
│  RELEASE (store)                                        │
│  Previous writes cannot move after this store.          │
│  They are visible to an Acquire load of this value.     │
│                                                         │
│  ACQUIRE (load)                                         │
│  Subsequent reads cannot move before this load.         │
│  They see writes that happened before a Release store.  │
│                                                         │
│  SEQ_CST                                                │
│  Total global order across all threads.                 │
│  The safest, most expensive, easiest to reason about.   │
└─────────────────────────────────────────────────────────┘

The CAS Loop

┌─────────────────────────────────────────────────────────┐
│  loop {                                                 │
│      current = load()                                   │
│      new = compute(current)                             │
│      if compare_exchange(current, new) succeeds {       │
│          return                                         │
│      }                                                  │
│      // another thread changed the value, retry         │
│  }                                                      │
│                                                         │
│  Progress: every failure means another thread succeeded.│
│  The system makes progress even if this thread retries. │
│  Individual threads can starve.                         │
└─────────────────────────────────────────────────────────┘

The ABA Problem

┌─────────────────────────────────────────────────────────┐
│  Thread 1: reads head = A (address 0x1000)              │
│                                                         │
│  Thread 2: pops A, frees it                             │
│            allocates new node at 0x1000 (address reused)│
│            pushes the new node                          │
│                                                         │
│  Thread 1: CAS(head, A, new_node) succeeds              │
│            because the address matches                  │
│                                                         │
│  But the node at 0x1000 is not the A that Thread 1 read.│
│  Its next pointer is different.                         │
│  The list is corrupted.                                 │
│                                                         │
│  Fix: tag the pointer with a version counter.           │
│  CAS compares both pointer and version.                 │
└─────────────────────────────────────────────────────────┘

Epoch Reclamation

┌─────────────────────────────────────────────────────────┐
│  Thread A: pins epoch 1, reads node X                   │
│  Thread B: removes X, schedules free at epoch 1         │
│                                                         │
│  The node is NOT freed yet.                             │
│  It is freed only after all threads have advanced       │
│  past epoch 1 (no thread can still reference X).        │
│                                                         │
│  Thread A: unpins (drops guard)                         │
│  Epoch advances. X is freed.                            │
│                                                         │
│  crossbeam-epoch manages this automatically.            │
└─────────────────────────────────────────────────────────┘

Summary

Item	Value
Module	`std::sync::atomic`
Types	`AtomicUsize`, `AtomicBool`, `AtomicPtr<T>`
Ordering	`Relaxed`, `Acquire`, `Release`, `AcqRel`, `SeqCst`
Core operation	`compare_exchange` (CAS)
Default ordering	`SeqCst`
ABA problem	Pointer reuse after free
Reclamation	`crossbeam-epoch`
Portability	`#[cfg(target_has_atomic)]`
Lock-free vs wait-free	System progress vs thread progress

Key takeaways:

Atomics provide indivisible operations. A read-modify-write like fetch_add cannot be interleaved by another thread. This is the foundation of all lock-free programming .
Ordering determines synchronization. Relaxed is atomic but not synchronized. Acquire and Release pair to publish data. SeqCst adds a total order and is the safe default .
The CAS loop is the core pattern. Read, compute, compare-and-swap, retry on failure. The system makes progress even when individual threads retry .
The ABA problem makes naive pointer CAS unsound. A freed node can be reallocated at the same address, making the CAS succeed when it should fail. Tagged pointers or epoch reclamation solve it .
Memory reclamation is the hard part. The crossbeam ecosystem exists because getting it right is difficult. Use it rather than implementing from scratch .
Lock-free is not wait-free. A thread can retry indefinitely. The guarantee is that the system as a whole progresses, not that every thread completes in a bounded number of steps.
Portability is not universal. AtomicU64 is missing on some 32-bit platforms, and CAS operations are missing on some ARM targets. Use #[cfg(target_has_atomic)] for portable code .
A mutex is often the right choice. Under low contention or for complex invariants, a Mutex is simpler, correct, and fast enough. Lock-free is for the cases where the contention is measured and the mutex is the bottleneck .
Weaker orderings are for proven hot paths. Relaxed and Acquire/Release are for code that has been benchmarked and reasoned about. In the absence of evidence, SeqCst is correct.
The Rust type system helps but does not eliminate unsafe. Lock-free pointer manipulation requires unsafe. The unsafe block is a signal that the programmer is responsible for the invariants that the compiler cannot verify .

Remember: Lock-free data structures are a specialized tool for a specific problem: contention that a mutex cannot handle efficiently. The atomics themselves are simple—a handful of types and methods—but the reasoning around memory ordering, ABA, and reclamation is where the complexity lives. Start with SeqCst, start with crossbeam for pointer-based structures, and start by measuring whether the mutex is actually the bottleneck. The lock-free version of a data structure is not automatically faster; it is faster only when the lock is the thing being contended, and the rest of the time it is more complex for no benefit.

Was this helpful?

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!