Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Lock-Free Programming

  • Locks can block threads. When a thread tries to acquire a lock that’s held, it stops and waits. A stalled or slow thread cannot prevent others from making progress.
  1. Lock-free operations never block
    Example: In an audio processing thread, blocking even briefly can cause audible glitches.
  • Locks guarantee nothing under contention—threads can starve.
  1. Lock-free structures guarantee system-wide progress:
    Lock-free: at least one thread always makes progress.
    Wait-free: every thread makes progress within a bounded time.
  • Locks come with hazards: Deadlocks
    Priority inversion (low-priority thread holds lock; high-priority thread waits)
    Convoys (one slow thread causes others to queue)
  1. Lock-free code avoids all of these because it never “holds” exclusive access.
  • With many CPUs hammering the same lock, performance collapses: Threads constantly block, sleep, wake up (expensive operations)
    Cache lines bounce between cores like crazy
  1. Lock-free operations often scale much better because:
    They use atomic instructions (CAS, fetch_add) that avoid kernel involvement
    They allow optimistic concurrency—many threads proceed in parallel
  • Under load, locks often collapse into long queues, causing: Latency spikes
    Tail latency problems (p99, p999)
  1. Lock-free structures often offer:
    Predictable latency
    Fewer outlier delays

❌ Why NOT Use Lock-Free Everywhere?

Lock-free is hard:

  • Complex to design
  • Easy to introduce subtle memory-ordering bugs
  • ABA problem must be handled (with hazard pointers or epoch GC)
  • Debugging is more difficult
  • Unsafe code is often required

Locks are:

  • Simple
  • Correct by default
  • Good enough for most workloads

Rule of thumb:

Use locks unless you have a measurable reason not to.

FeatureLocksLock-Free
BlockingYesNo
DeadlocksPossibleImpossible
Priority inversionPossibleImpossible
Contention behaviorPoorOften good
LatencyCan spikeMore stable
ComplexityLowHigh
SafetyEasyHard

Pattern 1: Memory Ordering Semantics

Problem: CPU reordering and compiler optimizations can break lock-free algorithms—writes may be visible in different order than written. Relaxed ordering is fast but provides no guarantees, causing race conditions.

Solution: Use Acquire for reads that need to see all previous writes. Use Release for writes that make previous operations visible.

Why It Matters: Ordering determines correctness and performance. Wrong ordering: lock-free queue corrupts data, appears to work in tests, fails randomly in production.

Use Cases: Lock-free data structures (queues, stacks, maps), reference counting (Arc), flags and signals, atomic counters, synchronization primitives, wait-free algorithms.

Example: Relaxed - No ordering guarantees (fastest)

Relaxed provides only atomicity—no guarantees about when other threads see updates or operation ordering. Use for counters where you only care about the final result; never use when the atomic signals that other data is ready.

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;

// Counters where exact ordering doesn't matter
fn relaxed_ordering_example() {
    let counter = Arc::new(AtomicUsize::new(0));
    let mut handles = vec![];

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

    for handle in handles {
        handle.join().unwrap();
    }

    // Final value guaranteed correct
    // Intermediate values may appear in any order
    let val = counter.load(Ordering::Relaxed);
    println!("Counter (Relaxed): {}", val);
}

relaxed_ordering_example(); // Output: 10000
}

Example: Acquire/Release - Synchronization without sequential consistency

Release on store publishes all prior writes; Acquire on load sees those writes. The workhorse of lock-free synchronization: producer sets flag with Release after preparing data, consumer uses Acquire to see all the data. Weaker than SeqCst but sufficient for most synchronization.

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, AtomicBool, Ordering};
use std::thread;

// Producer-consumer, message passing
fn acquire_release_ordering() {
    let data = Arc::new(AtomicUsize::new(0));
    let ready = Arc::new(AtomicBool::new(false));

    let data_c = Arc::clone(&data);
    let ready_c = Arc::clone(&ready);

    // Producer
    let producer = thread::spawn(move || {
        data_c.store(42, Ordering::Relaxed);
        // Release: writes visible to Acquire
        ready_c.store(true, Ordering::Release);
    });

    // Consumer
    let consumer = thread::spawn(move || {
        // Acquire: see all writes before Release
        while !ready.load(Ordering::Acquire) {
            thread::yield_now();
        }
        // Guaranteed to see data == 42
        let value = data.load(Ordering::Relaxed);
        println!("Consumer sees: {}", value);
        assert_eq!(value, 42);
    });

    producer.join().unwrap();
    consumer.join().unwrap();
}

}

Example: SeqCst - Sequential consistency (slowest)

SeqCst creates a single global total order—all threads see operations in the exact same order. Use when multiple atomics must appear coordinated or when correctness matters more than performance; can be 10-100x slower than Relaxed on ARM/POWER.

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;

// When correctness > performance
fn seq_cst_ordering() {
    let x = Arc::new(AtomicBool::new(false));
    let y = Arc::new(AtomicBool::new(false));
    let z1 = Arc::new(AtomicBool::new(false));
    let z2 = Arc::new(AtomicBool::new(false));

    let (x1, y1, z1c) = (
        Arc::clone(&x), Arc::clone(&y), Arc::clone(&z1)
    );

    let t1 = thread::spawn(move || {
        x1.store(true, Ordering::SeqCst);
        if !y1.load(Ordering::SeqCst) {
            z1c.store(true, Ordering::SeqCst);
        }
    });

    let (x2, y2, z2c) = (
        Arc::clone(&x), Arc::clone(&y), Arc::clone(&z2)
    );

    let t2 = thread::spawn(move || {
        y2.store(true, Ordering::SeqCst);
        if !x2.load(Ordering::SeqCst) {
            z2c.store(true, Ordering::SeqCst);
        }
    });

    t1.join().unwrap();
    t2.join().unwrap();

    // With SeqCst: cannot have both z1 and z2 true
    // Without: theoretically possible (hw reorder)
    let z1v = z1.load(Ordering::SeqCst);
    let z2v = z2.load(Ordering::SeqCst);
    println!("Both flags set: {} (expect false)", z1v && z2v);
}

}

Example: AcqRel - Combine Acquire and Release

AcqRel combines Acquire (read) and Release (write) for read-modify-write operations like fetch_add and compare_exchange. Use for spinlocks and counters used for synchronization; pure loads use Acquire, pure stores use Release.

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, AtomicBool, Ordering};
use std::thread;

// Read-modify-write operations
fn acq_rel_ordering() {
    let counter = Arc::new(AtomicUsize::new(0));

    let mut handles = vec![];
    for _ in 0..5 {
        let ctr = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..100 {
                // AcqRel: Acquire on load, Release on store
                ctr.fetch_add(1, Ordering::AcqRel);
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let val = counter.load(Ordering::Acquire);
    println!("Counter (AcqRel): {}", val);
}

// Spinlock with proper ordering
struct Spinlock {
    locked: AtomicBool,
}

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

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

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

let lock = Spinlock::new();
lock.lock();
/* critical section */
lock.unlock();
}

Example: Double-checked locking for lazy initialization

DCL avoids locking on every access: fast path checks initialized.load(Acquire), slow path uses CAS to compete for initialization. Tricky to get right—prefer std::sync::OnceLock or once_cell::OnceCell which handle ordering correctly.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, AtomicBool, Ordering};

struct LazyInit<T> {
    data: AtomicUsize, // Actually *mut T
    initialized: AtomicBool,
    _marker: std::marker::PhantomData<T>,
}

impl<T> LazyInit<T> {
    fn new() -> Self {
        Self {
            data: AtomicUsize::new(0),
            initialized: AtomicBool::new(false),
            _marker: std::marker::PhantomData,
        }
    }

    fn get_or_init<F>(&self, init: F) -> &T
    where
        F: FnOnce() -> T,
    {
        // Fast path: Acquire ensures we see data
        if self.initialized.load(Ordering::Acquire) {
            let ptr = self.data.load(Ordering::Relaxed);
            unsafe { &*(ptr as *const T) }
        } else {
            self.init_slow(init)
        }
    }

    fn init_slow<F>(&self, init: F) -> &T
    where
        F: FnOnce() -> T,
    {
        let ptr = Box::into_raw(Box::new(init()));

        // Try to publish (SeqCst for correctness)
        match self.initialized.compare_exchange(
            false, true,
            Ordering::SeqCst, Ordering::SeqCst,
        ) {
            Ok(_) => {
                // We won the race
                self.data.store(ptr as usize, Ordering::Release);
                unsafe { &*ptr }
            }
            Err(_) => {
                // Someone else won, clean up
                unsafe { drop(Box::from_raw(ptr)) };
                let p = self.data.load(Ordering::Acquire);
                unsafe { &*(p as *const T) }
            }
        }
    }
}
}

Memory Ordering Guide:

OrderingGuaranteesUse CasePerformance
RelaxedAtomicity onlyCounters, flags (order doesn’t matter)Fastest
AcquireSee writes before ReleaseConsumer in producer-consumerFast
ReleasePublish writes to AcquireProducer in producer-consumerFast
AcqRelBoth Acquire and ReleaseRMW operationsMedium
SeqCstTotal order across all threadsWhen correctness is criticalSlowest

Example: Fence for non-atomic data

A fence establishes ordering even for non-atomic data. Pattern: write data → Release fence → Relaxed store (producer); Relaxed load → Acquire fence → read data (consumer). Use for FFI, MMIO, DMA, or batching ordering guarantees for multiple operations.

#![allow(unused)]
fn main() {
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering, fence};
use std::thread;

fn fence_with_non_atomic() {
    let mut data = 0u64;
    let ready = Arc::new(AtomicBool::new(false));
    let ready_c = Arc::clone(&ready);

    // Producer
    let producer = thread::spawn(move || {
        unsafe {
            let data_ptr = &mut data as *mut u64;
            *data_ptr = 42;

            // Fence ensures writes visible
            fence(Ordering::Release);
            ready_c.store(true, Ordering::Relaxed);
        }
    });

    // Consumer
    thread::sleep(std::time::Duration::from_millis(10));

    if ready.load(Ordering::Relaxed) {
        // Fence: see writes before Release fence
        fence(Ordering::Acquire);
        println!("Data: {}", data);
    }

    producer.join().unwrap();
}

}

Example: Compiler fence (prevents compiler reordering only)

compiler_fence prevents compiler reordering but emits no CPU instruction—CPU can still reorder. Use for signal handlers or x86 where CPU ordering suffices. On ARM/POWER, NOT sufficient for inter-thread synchronization.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering, compiler_fence};

fn compiler_fence_example() {
    let x = AtomicUsize::new(0);
    let y = AtomicUsize::new(0);

    x.store(1, Ordering::Relaxed);

    // Prevent compiler reorder (hw can still)
    compiler_fence(Ordering::SeqCst);

    y.store(2, Ordering::Relaxed);
    // Compiler sees x=1 before y=2
}
}

Example: Memory barrier for DMA/MMIO

For DMA/MMIO, barriers ensure CPU writes are visible to devices and vice versa. Pattern: write data → Release fence → signal (producer); check flag → Acquire fence → read (consumer). Used in network drivers, GPU programming, embedded systems.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicBool, Ordering, fence};

#[repr(C)]
struct DmaBuffer {
    data: [u8; 4096],
    ready: AtomicBool,
}

impl DmaBuffer {
    fn write_for_dma(&mut self, data: &[u8]) {
        self.data[..data.len()].copy_from_slice(data);

        // Ensure writes complete before signal
        fence(Ordering::Release);
        self.ready.store(true, Ordering::Relaxed);
    }

    fn read_from_dma(&mut self) -> Option<&[u8]> {
        if !self.ready.load(Ordering::Relaxed) {
            return None;
        }

        // Ensure we see all device writes
        fence(Ordering::Acquire);

        Some(&self.data)
    }
}
}

Fence Types:

  • fence(Ordering): Hardware and compiler barrier
  • compiler_fence(Ordering): Compiler-only barrier (no CPU fence)
  • Use for: MMIO, DMA, FFI boundaries

Pattern 2: Compare-and-Swap Patterns

Problem: Implementing lock-free operations requires atomic read-modify-write. Naive approaches have race conditions when multiple threads update simultaneously.

Solution: Use compare-and-swap (CAS) as fundamental building block. Load current value, compute new value, CAS to update only if unchanged.

Why It Matters: CAS is foundation of all lock-free algorithms. Without proper CAS loops, concurrent updates are lost.

Use Cases: Lock-free stacks and queues, atomic max/min tracking, conditional increments (rate limiting), version tracking, optimistic updates, retry logic.

Example: Basic CAS loop

CAS atomically compares and swaps if value matches expected. Loop pattern: load current, compute new, CAS to update (retry if failed). Foundation of all lock-free algorithms—optimistic concurrency that’s faster than locking under low contention.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

fn cas_increment(counter: &AtomicUsize) {
    loop {
        let cur = counter.load(Ordering::Relaxed);
        let new_val = cur + 1;

        // Try update: succeeds if value unchanged
        if counter
            .compare_exchange_weak(
                cur, new_val,
                Ordering::Relaxed, Ordering::Relaxed,
            )
            .is_ok()
        {
            break;
        }
        // Spurious failure or contention - retry
    }
}

// Increment counter with CAS loop
let counter = AtomicUsize::new(0);
cas_increment(&counter);
}

Example: compare_exchange vs compare_exchange_weak

compare_exchange always succeeds if value matches; compare_exchange_weak may spuriously fail (on ARM/POWER). Use weak in retry loops (2-3x faster on ARM), use strong for single attempts where you need the true result.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

fn compare_exchange_variants() {
    let value = AtomicUsize::new(0);

    // compare_exchange: no spurious failure
    let result = value.compare_exchange(
        0, 1, Ordering::SeqCst, Ordering::SeqCst,
    );
    assert!(result.is_ok());

    // compare_exchange_weak: may spuriously fail
    loop {
        let res = value.compare_exchange_weak(
            1, 2, Ordering::SeqCst, Ordering::SeqCst
        );
        if res.is_ok() { break; }
    }

    println!("Final: {}", value.load(Ordering::SeqCst));
}

}

Example: CAS with data transformation

Generic CAS loop applying any transformation: load, apply function, CAS, retry on failure. Key optimization: use the current value returned by failed CAS instead of reloading. Use for custom operations not covered by built-in fetch_* operations.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

fn cas_update<F>(counter: &AtomicUsize, f: F)
where
    F: Fn(usize) -> usize,
{
    let mut cur = counter.load(Ordering::Relaxed);

    loop {
        let new_val = f(cur);

        match counter.compare_exchange_weak(
            cur, new_val,
            Ordering::Relaxed, Ordering::Relaxed,
        ) {
            Ok(_) => break,
            Err(actual) => cur = actual, // Retry
        }
    }
}
}

Example: Lock-free max tracking

No fetch_max instruction exists—implement with CAS: load current, compare, CAS if larger. Early exit when value <= current avoids contention. Use for metrics collection, finding extremes in parallel algorithms.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

struct MaxTracker {
    max: AtomicUsize,
}

impl MaxTracker {
    fn new() -> Self {
        Self {
            max: AtomicUsize::new(0),
        }
    }

    fn update(&self, value: usize) {
        let mut current = self.max.load(Ordering::Relaxed);

        loop {
            if value <= current {
                // Already have a larger max
                break;
            }

            match self.max.compare_exchange_weak(
                current,
                value,
                Ordering::Relaxed,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => current = actual,
            }
        }
    }

    fn get(&self) -> usize {
        self.max.load(Ordering::Relaxed)
    }
}

// Track max across concurrent updates
let t = MaxTracker::new();
t.update(50); t.update(30);
println!("{}", t.get()); // 50
}

Example: Lock-free accumulator

Maintains running sum and count for averages with separate atomics. average() may read slightly inconsistent values (acceptable for approximate stats). The reset() pattern atomically swaps to 0 for “collect and reset” metrics.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

struct Accumulator {
    sum: AtomicUsize,
    count: AtomicUsize,
}

impl Accumulator {
    fn new() -> Self {
        Self {
            sum: AtomicUsize::new(0),
            count: AtomicUsize::new(0),
        }
    }

    fn add(&self, value: usize) {
        self.sum.fetch_add(value, Ordering::Relaxed);
        self.count.fetch_add(1, Ordering::Relaxed);
    }

    fn average(&self) -> f64 {
        let sum = self.sum.load(Ordering::Relaxed);
        let count = self.count.load(Ordering::Relaxed);

        if count == 0 {
            0.0
        } else {
            sum as f64 / count as f64
        }
    }

    fn reset(&self) -> (usize, usize) {
        let sum = self.sum.swap(0, Ordering::Relaxed);
        let count = self.count.swap(0, Ordering::Relaxed);
        (sum, count)
    }
}
}

Example: Conditional update

Increments counter only if below threshold—returns success/failure. Implements rate limiting, connection limits, bounded counters without locks. Multiple threads may race; only one wins CAS, others retry and may find threshold reached.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

struct ConditionalCounter {
    value: AtomicUsize,
}

impl ConditionalCounter {
    fn new(initial: usize) -> Self {
        Self {
            value: AtomicUsize::new(initial),
        }
    }

    fn increment_if_below(&self, threshold: usize) -> bool {
        let mut current = self.value.load(Ordering::Relaxed);

        loop {
            if current >= threshold {
                return false; // Can't increment
            }

            match self.value.compare_exchange_weak(
                current,
                current + 1,
                Ordering::Relaxed,
                Ordering::Relaxed,
            ) {
                Ok(_) => return true,
                Err(actual) => current = actual,
            }
        }
    }

    fn get(&self) -> usize {
        self.value.load(Ordering::Relaxed)
    }
}
}

Usage

fn main() {
    println!("=== CAS Increment ===\n");

    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..100 {
                cas_increment(&counter);
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Final count: {}", counter.load(Ordering::Relaxed));

    println!("\n=== Max Tracker ===\n");

    let tracker = Arc::new(MaxTracker::new());
    let mut handles = vec![];

    for i in 0..10 {
        let tracker = Arc::clone(&tracker);
        handles.push(thread::spawn(move || {
            for j in 0..100 {
                tracker.update(i * 100 + j);
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Max value: {}", tracker.get());

    println!("\n=== Accumulator ===\n");

    let acc = Accumulator::new();

    for i in 1..=100 {
        acc.add(i);
    }

    println!("Average: {:.2}", acc.average());
    println!("Reset: {:?}", acc.reset());
    println!("After reset: {:.2}", acc.average());

    println!("\n=== Conditional Counter ===\n");

    let counter = ConditionalCounter::new(0);

    for _ in 0..15 {
        if counter.increment_if_below(10) {
            println!("Incremented to {}", counter.get());
        } else {
            println!("Threshold reached: {}", counter.get());
        }
    }
}

CAS Patterns:

  • Basic loop: Load, compute, CAS, retry on failure
  • compare_exchange_weak: Use in loops (may spuriously fail)
  • compare_exchange: Use outside loops (stronger guarantee)
  • Failure handling: Update current value on failure

Example: ABA Problem and Solutions

ABA: value changes A→B→A, CAS succeeds but state is different (use-after-free in stacks). Solutions: tagged pointers with version counter, epoch-based reclamation, hazard pointers. Use crossbeam-epoch in production—ABA is hard to get right.

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

// Problem: ABA without protection
struct NaiveStack<T> {
    head: AtomicUsize, // *mut Node<T>
    _phantom: std::marker::PhantomData<T>,
}

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

// Unsafe - suffers from ABA problem!
impl<T> NaiveStack<T> {
    unsafe fn pop_unsafe(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            let head_ptr = head as *mut Node<T>;

            if head_ptr.is_null() {
                return None;
            }

            let next = (*head_ptr).next;

            // ABA: Between load and CAS, thread could:
            // 1. Pop node 2. Free it 3. Push new
            // 4. Push same addr back - CAS succeeds!

            if self.head
                .compare_exchange(
                    head, next as usize,
                    Ordering::Release, Ordering::Acquire,
                )
                .is_ok()
            {
                let data = std::ptr::read(&(*head_ptr).data);
                drop(Box::from_raw(head_ptr));
                return Some(data);
            }
        }
    }
}
// Solution 1: Tagged pointers (version counter)
const PTR_MASK: u64 = 0x0000_FFFF_FFFF_FFFF;

struct TaggedPtr {
    value: AtomicU64, // Upper 16: tag, Lower 48: ptr
}

impl TaggedPtr {
    fn new(ptr: *mut u8) -> Self {
        Self { value: AtomicU64::new(ptr as u64) }
    }

    fn load(&self, ord: Ordering) -> (*mut u8, u16) {
        let packed = self.value.load(ord);
        let ptr = (packed & PTR_MASK) as *mut u8;
        let tag = (packed >> 48) as u16;
        (ptr, tag)
    }

    fn store(&self, ptr: *mut u8, tag: u16, ord: Ordering) {
        let packed =
            ((tag as u64) << 48) | ((ptr as u64) & PTR_MASK);
        self.value.store(packed, ord);
    }

    fn compare_exchange(
        &self,
        cur_ptr: *mut u8, cur_tag: u16,
        new_ptr: *mut u8, new_tag: u16,
        success: Ordering, failure: Ordering,
    ) -> Result<(), ()> {
        let cur =
            ((cur_tag as u64) << 48) | (cur_ptr as u64 & PTR_MASK);
        let new =
            ((new_tag as u64) << 48) | (new_ptr as u64 & PTR_MASK);

        self.value
            .compare_exchange(cur, new, success, failure)
            .map(|_| ())
            .map_err(|_| ())
    }
}
// Solution 2: Version counter approach
struct VersionedStack<T> {
    head: AtomicU64, // Upper 32: version, Lower 32: index
    nodes: Vec<Option<VersionedNode<T>>>,
}

struct VersionedNode<T> {
    data: T,
    next: u32,
    version: u32,
}

impl<T> VersionedStack<T> {
    fn pack(index: u32, version: u32) -> u64 {
        ((version as u64) << 32) | (index as u64)
    }

    fn unpack(packed: u64) -> (u32, u32) {
        let index = (packed & 0xFFFF_FFFF) as u32;
        let version = (packed >> 32) as u32;
        (index, version)
    }
}
// Solution 3: Epoch-based reclamation (simplified)
struct EpochGC {
    global_epoch: AtomicUsize,
}

impl EpochGC {
    fn new() -> Self {
        Self {
            global_epoch: AtomicUsize::new(0),
        }
    }

    fn pin(&self) -> usize {
        self.global_epoch.load(Ordering::Acquire)
    }

    fn try_advance(&self) {
        self.global_epoch.fetch_add(1, Ordering::Release);
    }

    fn is_safe_to_free(&self, alloc_epoch: usize) -> bool {
        let cur = self.global_epoch.load(Ordering::Acquire);
        cur > alloc_epoch + 2 // Conservative: 2 epochs
    }
}

// ABA-safe counter
struct ABACounter {
    value: AtomicU64, // Upper 32: version, Lower 32: count
}

impl ABACounter {
    fn new(initial: u32) -> Self {
        Self {
            value: AtomicU64::new(initial as u64),
        }
    }

    fn increment(&self) {
        loop {
            let cur = self.value.load(Ordering::Relaxed);
            let count = (cur & 0xFFFF_FFFF) as u32;
            let ver = (cur >> 32) as u32;

            let new_cnt = count.wrapping_add(1);
            let new_ver = ver.wrapping_add(1);
            let new_val =
                ((new_ver as u64) << 32) | (new_cnt as u64);

            if self.value
                .compare_exchange_weak(
                    cur, new_val,
                    Ordering::Relaxed, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }
    }

    fn get(&self) -> u32 {
        let packed = self.value.load(Ordering::Relaxed);
        (packed & 0xFFFF_FFFF) as u32
    }

    fn get_with_version(&self) -> (u32, u32) {
        let packed = self.value.load(Ordering::Relaxed);
        let count = (packed & 0xFFFF_FFFF) as u32;
        let version = (packed >> 32) as u32;
        (count, version)
    }
}

fn main() {
    println!("=== ABA Counter ===\n");

    let counter = Arc::new(ABACounter::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.increment();
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let (count, version) = counter.get_with_version();
    println!("Count: {}, Version: {}", count, version);

    println!("\n=== Epoch GC ===\n");

    let gc = EpochGC::new();

    let epoch1 = gc.pin();
    println!("Pinned at epoch {}", epoch1);

    gc.try_advance();
    gc.try_advance();
    gc.try_advance();

    println!("Safe to free? {}", gc.is_safe_to_free(epoch1));
}

ABA Solutions:

  1. Tagged pointers: Add version counter to pointer
  2. Double-width CAS: CAS on (pointer, version) pair
  3. Epoch-based reclamation: Defer deletion until safe
  4. Hazard pointers: Track active pointers (next Pattern)

Pattern 3: Lock-Free Queues and Stacks

Problem: Mutex-based data structures serialize all access—threads wait even when operating on different elements. Lock contention causes 80% of multi-threaded time spent waiting.

Solution: Use Treiber stack (lock-free stack with CAS-based push/pop). Implement MPSC queue (multi-producer single-consumer) with atomic operations.

Why It Matters: Lock-free structures enable true parallelism. Multi-threaded counter with Mutex: serialized updates = 1 core performance.

Use Cases: Work-stealing task queues (tokio, rayon), MPMC message passing, real-time audio/video processing, high-frequency trading, concurrent data structure building blocks, actor system mailboxes.

Example: Treiber Stack (Lock-Free Stack)

Simplest lock-free structure: push/pop via CAS on head pointer. Multiple threads race; losers retry, progress guaranteed. Leaks nodes without reclamation—real implementations use hazard pointers or epoch-based reclamation.

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

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

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

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

    // stack.push(42); let val = stack.pop();

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

        loop {
            let head = self.head.load(Ordering::Relaxed);
            unsafe { (*node).next = head; }

            if self.head
                .compare_exchange_weak(
                    head, node,
                    Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            if head.is_null() { return None; }

            unsafe {
                let next = (*head).next;

                if self.head
                    .compare_exchange_weak(
                        head, next,
                        Ordering::Release, Ordering::Acquire)
                    .is_ok()
                {
                    let data = ptr::read(&(*head).data);
                    // Leak node to avoid use-after-free
                    // Real impl: hazard ptrs or epoch GC
                    return Some(data);
                }
            }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.head.load(Ordering::Acquire).is_null()
    }
}

unsafe impl<T: Send> Send for TreiberStack<T> {}
unsafe impl<T: Send> Sync for TreiberStack<T> {}
// Real-world: Work-stealing deque (simplified)
pub struct WorkStealingDeque<T> {
    bottom: AtomicPtr<Node<T>>,
    top: AtomicPtr<Node<T>>,
}

impl<T> WorkStealingDeque<T> {
    pub fn new() -> Self {
        Self {
            bottom: AtomicPtr::new(ptr::null_mut()),
            top: AtomicPtr::new(ptr::null_mut()),
        }
    }

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

        loop {
            let bot = self.bottom.load(Ordering::Relaxed);
            unsafe { (*node).next = bot; }

            if self.bottom
                .compare_exchange_weak(
                    bot, node,
                    Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        // Owner pops from bottom (LIFO)
        loop {
            let bot = self.bottom.load(Ordering::Acquire);
            if bot.is_null() { return None; }

            unsafe {
                let next = (*bot).next;
                if self.bottom
                    .compare_exchange_weak(
                        bot, next,
                        Ordering::Release, Ordering::Acquire)
                    .is_ok()
                {
                    return Some(ptr::read(&(*bot).data));
                }
            }
        }
    }

    pub fn steal(&self) -> Option<T> {
        // Thieves steal from top (FIFO)
        loop {
            let top = self.top.load(Ordering::Acquire);
            if top.is_null() { return None; }

            unsafe {
                let next = (*top).next;
                if self.top
                    .compare_exchange_weak(
                        top, next,
                        Ordering::Release, Ordering::Acquire)
                    .is_ok()
                {
                    return Some(ptr::read(&(*top).data));
                }
            }
        }
    }
}

unsafe impl<T: Send> Send for WorkStealingDeque<T> {}
unsafe impl<T: Send> Sync for WorkStealingDeque<T> {}

fn main() {
    println!("=== Treiber Stack ===\n");

    let stack = Arc::new(TreiberStack::new());
    let mut handles = vec![];

    // Producers
    for i in 0..5 {
        let stack = Arc::clone(&stack);
        handles.push(thread::spawn(move || {
            for j in 0..100 {
                stack.push(i * 100 + j);
            }
        }));
    }

    // Consumers
    for _ in 0..5 {
        let stack = Arc::clone(&stack);
        handles.push(thread::spawn(move || {
            let mut count = 0;
            while let Some(_) = stack.pop() {
                count += 1;
            }
            count
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Stack empty: {}", stack.is_empty());

    println!("\n=== Work Stealing Deque ===\n");

    let deque = Arc::new(WorkStealingDeque::new());

    // Owner thread
    let owner_deque = Arc::clone(&deque);
    let owner = thread::spawn(move || {
        for i in 0..100 {
            owner_deque.push(i);
        }

        let mut popped = 0;
        while owner_deque.pop().is_some() {
            popped += 1;
        }
        println!("Owner popped: {}", popped);
    });

    // Thief threads
    let mut thieves = vec![];
    for id in 0..3 {
        let td = Arc::clone(&deque);
        thieves.push(thread::spawn(move || {
            use std::time::Duration;
            thread::sleep(Duration::from_millis(10));
            let mut stolen = 0;
            while td.steal().is_some() { stolen += 1; }
            println!("Thief {} stole: {}", id, stolen);
        }));
    }

    owner.join().unwrap();
    for thief in thieves {
        thief.join().unwrap();
    }
}

Treiber Stack Properties:

  • Lock-free: At least one thread makes progress
  • Push: O(1) average case
  • Pop: O(1) average case
  • ABA problem: Requires protection (hazard pointers or epoch GC)

Example: Lock-Free Queue (MPSC)

FIFO queue with multiple producers (CAS-based) and single consumer. Uses sentinel node to avoid empty-queue edge cases. Helping mechanism: threads advance stale tail pointers to prevent blocking. SPSC variant needs no CAS—just Acquire/Release.

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

struct QueueNode<T> {
    data: Option<T>,
    next: AtomicPtr<QueueNode<T>>,
}

pub struct MpscQueue<T> {
    head: AtomicPtr<QueueNode<T>>,
    tail: AtomicPtr<QueueNode<T>>,
}

impl<T> MpscQueue<T> {
    pub fn new() -> Self {
        let sentinel = Box::into_raw(Box::new(QueueNode {
            data: None,
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        Self {
            head: AtomicPtr::new(sentinel),
            tail: AtomicPtr::new(sentinel),
        }
    }

    // queue.push(42); let val = queue.pop();

    pub fn push(&self, data: T) {
        let node = Box::into_raw(Box::new(QueueNode {
            data: Some(data),
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        loop {
            let tail = self.tail.load(Ordering::Acquire);

            unsafe {
                let next = (*tail).next.load(Ordering::Acquire);

                if next.is_null() {
                    // Tail is last node
                    if (*tail).next
                        .compare_exchange(
                            ptr::null_mut(), node,
                            Ordering::Release, Ordering::Acquire,
                        )
                        .is_ok()
                    {
                        // Update tail (helps next push)
                        let _ = self.tail.compare_exchange(
                            tail, node,
                            Ordering::Release, Ordering::Acquire,
                        );
                        break;
                    }
                } else {
                    // Help by updating tail
                    let _ = self.tail.compare_exchange(
                        tail, next,
                        Ordering::Release, Ordering::Acquire,
                    );
                }
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        unsafe {
            let head = self.head.load(Ordering::Acquire);
            let next = (*head).next.load(Ordering::Acquire);

            if next.is_null() { return None; }

            self.head.store(next, Ordering::Release);
            let data = (*next).data.take();
            drop(Box::from_raw(head)); // Single consumer
            data
        }
    }
}

unsafe impl<T: Send> Send for MpscQueue<T> {}
unsafe impl<T: Send> Sync for MpscQueue<T> {}
// Bounded SPSC queue (Single Producer Single Consumer)
pub struct BoundedSpscQueue<T> {
    buffer: Vec<Option<T>>,
    head: AtomicUsize,
    tail: AtomicUsize,
    capacity: usize,
}

impl<T> BoundedSpscQueue<T> {
    pub fn new(capacity: usize) -> Self {
        let mut buffer = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            buffer.push(None);
        }

        Self {
            buffer,
            head: AtomicUsize::new(0),
            tail: AtomicUsize::new(0),
            capacity,
        }
    }

    pub fn push(&mut self, data: T) -> Result<(), T> {
        let tail = self.tail.load(Ordering::Relaxed);
        let next_tail = (tail + 1) % self.capacity;
        let head = self.head.load(Ordering::Acquire);

        if next_tail == head {
            return Err(data); // Queue full
        }

        unsafe {
            let slot = self.buffer.get_unchecked_mut(tail);
            *slot = Some(data);
        }

        self.tail.store(next_tail, Ordering::Release);
        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        let head = self.head.load(Ordering::Relaxed);
        let tail = self.tail.load(Ordering::Acquire);

        if head == tail {
            return None; // Queue empty
        }

        unsafe {
            let slot = self.buffer.get_unchecked_mut(head);
            let data = slot.take();

            let next_head = (head + 1) % self.capacity;
            self.head.store(next_head, Ordering::Release);

            data
        }
    }

    pub fn len(&self) -> usize {
        let head = self.head.load(Ordering::Relaxed);
        let tail = self.tail.load(Ordering::Relaxed);

        if tail >= head {
            tail - head
        } else {
            self.capacity - head + tail
        }
    }
}

unsafe impl<T: Send> Send for BoundedSpscQueue<T> {}

fn main() {
    println!("=== MPSC Queue ===\n");

    let queue = Arc::new(MpscQueue::new());

    // Multiple producers
    let mut producers = vec![];
    for i in 0..5 {
        let queue = Arc::clone(&queue);
        producers.push(thread::spawn(move || {
            for j in 0..100 {
                queue.push(i * 100 + j);
            }
        }));
    }

    for p in producers {
        p.join().unwrap();
    }

    // Single consumer
    let mut count = 0;
    while queue.pop().is_some() {
        count += 1;
    }

    println!("Consumed {} items", count);

    println!("\n=== SPSC Queue ===\n");

    let mut producer_queue = BoundedSpscQueue::new(32);
    let mut consumer_queue = unsafe {
        // Safe: only one thread accesses each
        std::ptr::read(&producer_queue as *const _)
    };

    let producer = thread::spawn(move || {
        for i in 0..100 {
            while producer_queue.push(i).is_err() {
                thread::yield_now();
            }
        }
    });

    let consumer = thread::spawn(move || {
        let mut sum = 0;
        let mut received = 0;

        while received < 100 {
            if let Some(value) = consumer_queue.pop() {
                sum += value;
                received += 1;
            } else {
                thread::yield_now();
            }
        }

        sum
    });

    producer.join().unwrap();
    let sum = consumer.join().unwrap();
    println!("Sum of 0..100: {}", sum);
}

Queue Variants:

  • MPSC: Multi-producer, single-consumer
  • SPSC: Single-producer, single-consumer (fastest)
  • MPMC: Multi-producer, multi-consumer (hardest)
  • Bounded: Fixed size, cache-friendly

Pattern 4: Hazard Pointers

Problem: Lock-free structures need memory reclamation—can’t immediately free nodes because other threads might access them. Naive deletion causes use-after-free.

Solution: Use hazard pointers to mark nodes as “in-use”. Each thread announces pointers it’s accessing.

Why It Matters: Prevents crashes in production lock-free code. Without proper reclamation, lock-free queue either leaks memory or crashes with use-after-free.

Use Cases: Production lock-free stacks and queues, concurrent hash maps, lock-free linked lists, RCU-style updates, safe memory management without GC, building blocks for complex concurrent data structures.

Example: Hazard Pointer Implementation

Solves memory reclamation: threads publish pointers they’re accessing, reclaimers scan before freeing. Protect→verify→use→unprotect pattern. Better than epoch-based for real-time (bounded memory), worse for high thread counts. Use haphazard crate.

use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use std::ptr;
use std::collections::HashSet;

const MAX_HAZARDS: usize = 128;

struct HazardPointer {
    pointer: AtomicPtr<u8>,
}

impl HazardPointer {
    fn new() -> Self {
        Self {
            pointer: AtomicPtr::new(ptr::null_mut()),
        }
    }

    fn protect(&self, ptr: *mut u8) {
        self.pointer.store(ptr, Ordering::Release);
    }

    fn clear(&self) {
        self.pointer.store(ptr::null_mut(), Ordering::Release);
    }

    fn get(&self) -> *mut u8 {
        self.pointer.load(Ordering::Acquire)
    }
}

struct HazardPointerDomain {
    hazards: Vec<HazardPointer>,
    retired: AtomicPtr<RetiredNode>,
    retired_count: AtomicUsize,
}

struct RetiredNode {
    ptr: *mut u8,
    next: *mut RetiredNode,
    deleter: unsafe fn(*mut u8),
}

impl HazardPointerDomain {
    fn new() -> Self {
        let mut hazards = Vec::new();
        for _ in 0..MAX_HAZARDS {
            hazards.push(HazardPointer::new());
        }

        Self {
            hazards,
            retired: AtomicPtr::new(ptr::null_mut()),
            retired_count: AtomicUsize::new(0),
        }
    }

    fn acquire(&self) -> Option<usize> {
        for (i, hp) in self.hazards.iter().enumerate() {
            let cur = hp.get();
            if cur.is_null() {
                // Try to claim hazard pointer
                if hp.pointer
                    .compare_exchange(
                        ptr::null_mut(),
                        1 as *mut u8, // Non-null marker
                        Ordering::Acquire, Ordering::Relaxed,
                    )
                    .is_ok()
                {
                    return Some(i);
                }
            }
        }
        None
    }

    fn protect(&self, index: usize, ptr: *mut u8) {
        self.hazards[index].protect(ptr);
    }

    fn release(&self, index: usize) {
        self.hazards[index].clear();
    }

    fn retire(
        &self, ptr: *mut u8, deleter: unsafe fn(*mut u8)
    ) {
        let node = Box::into_raw(Box::new(RetiredNode {
            ptr, next: ptr::null_mut(), deleter,
        }));

        // Add to retired list
        loop {
            let head = self.retired.load(Ordering::Acquire);
            unsafe { (*node).next = head; }

            if self.retired
                .compare_exchange_weak(
                    head, node,
                    Ordering::Release, Ordering::Acquire)
                .is_ok()
            {
                break;
            }
        }

        let cnt =
            self.retired_count.fetch_add(1, Ordering::Relaxed);

        // Trigger reclamation if too many
        if cnt > MAX_HAZARDS * 2 {
            self.scan();
        }
    }

    fn scan(&self) {
        // Collect protected pointers
        let mut protected = HashSet::new();
        for hp in &self.hazards {
            let ptr = hp.get();
            if !ptr.is_null() && ptr != 1 as *mut u8 {
                protected.insert(ptr);
            }
        }

        // Reclaim retired nodes
        let null = ptr::null_mut();
        let mut cur = self.retired.swap(null, Ordering::Acquire);
        let mut kept = Vec::new();

        unsafe {
            while !cur.is_null() {
                let next = (*cur).next;

                if protected.contains(&(*cur).ptr) {
                    kept.push(cur); // Still protected
                } else {
                    ((*cur).deleter)((*cur).ptr);
                    drop(Box::from_raw(cur));
                    self.retired_count
                        .fetch_sub(1, Ordering::Relaxed);
                }
                cur = next;
            }
        }

        // Re-add kept nodes
        for node in kept {
            loop {
                let head = self.retired.load(Ordering::Acquire);
                unsafe { (*node).next = head; }

                if self.retired
                    .compare_exchange_weak(
                        head, node,
                        Ordering::Release, Ordering::Acquire)
                    .is_ok()
                {
                    break;
                }
            }
        }
    }
}
// Example: Stack with hazard pointers
struct SafeNode<T> {
    data: T,
    next: *mut SafeNode<T>,
}

struct SafeStack<T> {
    head: AtomicPtr<SafeNode<T>>,
    hp_domain: HazardPointerDomain,
}

impl<T> SafeStack<T> {
    fn new() -> Self {
        Self {
            head: AtomicPtr::new(ptr::null_mut()),
            hp_domain: HazardPointerDomain::new(),
        }
    }

    fn push(&self, data: T) {
        let node = Box::into_raw(Box::new(SafeNode {
            data, next: ptr::null_mut(),
        }));

        loop {
            let head = self.head.load(Ordering::Relaxed);
            unsafe { (*node).next = head; }

            if self.head
                .compare_exchange_weak(
                    head, node,
                    Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }
    }

    fn pop(&self) -> Option<T> {
        let hp_idx = self.hp_domain.acquire()?;

        loop {
            let head = self.head.load(Ordering::Acquire);

            if head.is_null() {
                self.hp_domain.release(hp_idx);
                return None;
            }

            // Protect head from deletion
            self.hp_domain.protect(hp_idx, head as *mut u8);

            // Verify head unchanged (avoid ABA)
            if self.head.load(Ordering::Acquire) != head {
                continue;
            }

            unsafe {
                let next = (*head).next;

                if self.head
                    .compare_exchange_weak(
                        head, next,
                        Ordering::Release, Ordering::Acquire)
                    .is_ok()
                {
                    let data = ptr::read(&(*head).data);

                    // Retire for later deletion
                    self.hp_domain.retire(head as *mut u8, |p| {
                        drop(Box::from_raw(p as *mut SafeNode<T>));
                    });

                    self.hp_domain.release(hp_idx);
                    return Some(data);
                }
            }
        }
    }
}

unsafe impl<T: Send> Send for SafeStack<T> {}
unsafe impl<T: Send> Sync for SafeStack<T> {}

fn main() {
    println!("=== Safe Stack (Hazard Pointers) ===\n");

    let stack = std::sync::Arc::new(SafeStack::new());
    let mut handles = vec![];

    // Producers
    for i in 0..5 {
        let stack = std::sync::Arc::clone(&stack);
        handles.push(std::thread::spawn(move || {
            for j in 0..1000 {
                stack.push(i * 1000 + j);
            }
        }));
    }

    // Consumers
    for _ in 0..5 {
        let stack = std::sync::Arc::clone(&stack);
        handles.push(std::thread::spawn(move || {
            let mut count = 0;
            while stack.pop().is_some() {
                count += 1;
            }
            count
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Stack operations completed safely");
}

Hazard Pointer Benefits:

  • Safe reclamation: No use-after-free
  • Lock-free: No blocking
  • ABA protection: Version checking via protection
  • Memory efficient: Bounded overhead

Pattern 5: Seqlock Pattern

Problem: Frequent reads of small data with occasional writes. Mutex too expensive (blocks readers).

Solution: Use sequence counter incremented on writes. Writers: increment (odd), write data, increment (even).

Why It Matters: 10-100x faster than locks for read-heavy workloads. Game coordinates updated 60fps, read 10,000x/sec: seqlock enables this.

Use Cases: Game entity positions/state, real-time sensor data, network statistics and metrics, configuration that changes rarely, performance counters, dashboard data, time-series snapshots, read-heavy caches.

Example: Seqlock Implementation

Fast reads with occasional writes via sequence counter: even=stable, odd=writing. Readers retry if sequence changed mid-read. Best when reads >> writes, data is small, T: Copy required. Single writer only.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};
use std::cell::UnsafeCell;

pub struct SeqLock<T> {
    seq: AtomicUsize,
    data: UnsafeCell<T>,
}

impl<T: Copy> SeqLock<T> {
    pub fn new(data: T) -> Self {
        Self {
            seq: AtomicUsize::new(0),
            data: UnsafeCell::new(data),
        }
    }

    // lock.write(42); let val = lock.read();

    pub fn read(&self) -> T {
        loop {
            // Read sequence number (even = not writing)
            let seq1 = self.seq.load(Ordering::Acquire);

            if seq1 % 2 == 1 {
                // Writer is active, spin
                std::hint::spin_loop();
                continue;
            }

            // Read data
            let data = unsafe { *self.data.get() };

            // Verify sequence hasn't changed
            std::sync::atomic::fence(Ordering::Acquire);
            let seq2 = self.seq.load(Ordering::Acquire);

            if seq1 == seq2 {
                return data;
            }

            // Sequence changed during read, retry
        }
    }

    pub fn write(&self, data: T) {
        // Increment sequence (makes it odd = writing)
        let seq = self.seq.fetch_add(1, Ordering::Acquire);
        debug_assert!(seq % 2 == 0, "Concurrent writes!");

        // Write data
        unsafe {
            *self.data.get() = data;
        }

        // Increment again (makes it even = readable)
        self.seq.fetch_add(1, Ordering::Release);
    }

    pub fn try_read(&self) -> Option<T> {
        let seq1 = self.seq.load(Ordering::Acquire);

        if seq1 % 2 == 1 {
            return None; // Writer active
        }

        let data = unsafe { *self.data.get() };

        std::sync::atomic::fence(Ordering::Acquire);
        let seq2 = self.seq.load(Ordering::Acquire);

        if seq1 == seq2 {
            Some(data)
        } else {
            None // Data changed
        }
    }
}

unsafe impl<T: Copy + Send> Send for SeqLock<T> {}
unsafe impl<T: Copy + Send> Sync for SeqLock<T> {}
// Real-world: Coordinates with seqlock
#[derive(Copy, Clone, Debug)]
struct Coordinates {
    x: f64,
    y: f64,
    z: f64,
}

fn seqlock_coordinates_example() {
    use std::sync::Arc;
    use std::thread;
    use std::time::Duration;

    let position = Arc::new(SeqLock::new(Coordinates {
        x: 0.0,
        y: 0.0,
        z: 0.0,
    }));

    // Writer thread (updates position)
    let writer_pos = Arc::clone(&position);
    let writer = thread::spawn(move || {
        for i in 0..100 {
            let coords = Coordinates {
                x: i as f64,
                y: (i * 2) as f64,
                z: (i * 3) as f64,
            };
            writer_pos.write(coords);
            thread::sleep(Duration::from_millis(10));
        }
    });

    // Reader threads (read position frequently)
    let mut readers = vec![];
    for id in 0..5 {
        let reader_pos = Arc::clone(&position);
        readers.push(thread::spawn(move || {
            for _ in 0..1000 {
                let coords = reader_pos.read();
                if id == 0 && coords.x as usize % 10 == 0 {
                    println!("Reader {}: {:?}", id, coords);
                }
            }
        }));
    }

    writer.join().unwrap();
    for reader in readers {
        reader.join().unwrap();
    }
}
// Real-world: Statistics snapshot
#[derive(Copy, Clone, Debug)]
struct Stats {
    count: u64,
    sum: u64,
    min: u64,
    max: u64,
}

impl Stats {
    fn new() -> Self {
        Self {
            count: 0,
            sum: 0,
            min: u64::MAX,
            max: 0,
        }
    }

    fn add(&mut self, value: u64) {
        self.count += 1;
        self.sum += value;
        self.min = self.min.min(value);
        self.max = self.max.max(value);
    }

    fn average(&self) -> f64 {
        if self.count == 0 {
            0.0
        } else {
            self.sum as f64 / self.count as f64
        }
    }
}

fn seqlock_stats_example() {
    use std::sync::Arc;
    use std::thread;

    let stats = Arc::new(SeqLock::new(Stats::new()));

    // Writer thread
    let writer_stats = Arc::clone(&stats);
    let writer = thread::spawn(move || {
        for i in 0..1000 {
            let mut current = writer_stats.read();
            current.add(i);
            writer_stats.write(current);
        }
    });

    // Reader threads (monitor stats)
    let mut readers = vec![];
    for id in 0..3 {
        let rs = Arc::clone(&stats);
        readers.push(thread::spawn(move || {
            use std::time::Duration;
            for _ in 0..100 {
                thread::sleep(Duration::from_millis(10));
                let s = rs.read();
                if id == 0 {
                    println!(
                        "n:{}, avg:{:.2}, min:{}, max:{}",
                        s.count, s.average(), s.min, s.max
                    );
                }
            }
        }));
    }

    writer.join().unwrap();
    for reader in readers {
        reader.join().unwrap();
    }
}

}

Example: Versioned seqlock (track writes)

Extends seqlock to expose version number (seq/2 = write count). Use for cache invalidation (“changed since last read?”), optimistic UI, change detection. Readers can skip processing if version unchanged.

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

pub struct VersionedSeqLock<T> {
    seqlock: SeqLock<T>,
}

impl<T: Copy> VersionedSeqLock<T> {
    pub fn new(data: T) -> Self {
        Self {
            seqlock: SeqLock::new(data),
        }
    }

    pub fn read_with_version(&self) -> (T, usize) {
        let seq1 = self.seqlock.seq.load(Ordering::Acquire);
        let data = self.seqlock.read();
        let version = seq1 / 2;
        (data, version)
    }

    pub fn write(&self, data: T) {
        self.seqlock.write(data);
    }

    pub fn version(&self) -> usize {
        self.seqlock.seq.load(Ordering::Acquire) / 2
    }
}

fn main() {
    println!("=== Seqlock Coordinates ===\n");
    seqlock_coordinates_example();

    println!("\n=== Seqlock Statistics ===\n");
    seqlock_stats_example();

    println!("\n=== Versioned Seqlock ===\n");

    let data = VersionedSeqLock::new(0u64);

    for i in 0..5 {
        data.write(i * 10);
        let (value, version) = data.read_with_version();
        println!("Value: {}, Version: {}", value, version);
    }
}

Seqlock Characteristics:

  • Optimistic reads: No locks for readers
  • Single writer: Only one writer at a time
  • Small data: Works best with Copy types
  • Retry on write: Readers retry if writer was active
  • Use case: Frequently read, rarely written data (coordinates, stats)

Example: Advanced Atomic Patterns

Overview: These patterns address specific performance and correctness challenges in concurrent programming: reducing contention, handling failures gracefully, and building higher-level primitives from atomics.

#![allow(unused)]
fn main() {
use std::sync::atomic::{
    AtomicU64, AtomicUsize, AtomicBool, Ordering
};
use std::sync::Arc;
use std::thread;
use std::time::{Duration, Instant};

}

Example: Striped counter (reduce contention)

Spread updates across multiple stripes by thread ID to reduce cache-line contention (ping-pong is 100+ cycles vs ~1 uncontended). More memory, slower reads (sum all stripes), but much faster writes under contention.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

struct StripedCounter {
    stripes: Vec<AtomicUsize>,
}

impl StripedCounter {
    fn new(num_stripes: usize) -> Self {
        let mut stripes = Vec::new();
        for _ in 0..num_stripes {
            stripes.push(AtomicUsize::new(0));
        }

        Self { stripes }
    }

    fn increment(&self) {
        let tid = std::thread::current().id();
        let idx = format!("{:?}", tid).len() % self.stripes.len();
        self.stripes[idx].fetch_add(1, Ordering::Relaxed);
    }

    fn get(&self) -> usize {
        self.stripes
            .iter()
            .map(|s| s.load(Ordering::Relaxed))
            .sum()
    }
}

// Usage: reduce contention with cache-line striping
let counter = StripedCounter::new(16);
counter.increment();
println!("{}", counter.get());
}

Example: Exponential backoff

On CAS failure, wait progressively longer (doubling delay) instead of tight spinning which wastes cycles and generates cache traffic. Use spin_loop() hint for CPU power savings. Reduces contention in CAS loops, spinlocks, lock-free structures.

#![allow(unused)]
fn main() {
use std::time::Duration;
use std::sync::atomic::{AtomicUsize, Ordering};

struct Backoff {
    current: Duration,
    max: Duration,
}

impl Backoff {
    fn new() -> Self {
        Self {
            current: Duration::from_nanos(1),
            max: Duration::from_micros(1000),
        }
    }

    fn spin(&mut self) {
        for _ in 0..(self.current.as_nanos() / 10) {
            std::hint::spin_loop();
        }

        self.current = (self.current * 2).min(self.max);
    }

    fn reset(&mut self) {
        self.current = Duration::from_nanos(1);
    }
}

fn cas_with_backoff(counter: &AtomicUsize) {
    let mut backoff = Backoff::new();

    loop {
        let current = counter.load(Ordering::Relaxed);

        match counter.compare_exchange_weak(
            current,
            current + 1,
            Ordering::Relaxed,
            Ordering::Relaxed,
        ) {
            Ok(_) => {
                backoff.reset();
                break;
            }
            Err(_) => {
                backoff.spin();
            }
        }
    }
}

}

Example: Atomic min/max

CAS-based min/max tracking: load current, exit if no improvement, CAS to update, retry on failure. Initialize min=MAX, max=0. Rust 1.70+ has fetch_min/fetch_max doing this in one instruction.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicU64, Ordering};

struct AtomicMinMax {
    min: AtomicU64,
    max: AtomicU64,
}

impl AtomicMinMax {
    fn new() -> Self {
        Self {
            min: AtomicU64::new(u64::MAX),
            max: AtomicU64::new(0),
        }
    }

    // mm.update(5); mm.update(10); let (min, max) = mm.get();

    fn update(&self, value: u64) {
        // Update min
        let mut cur_min = self.min.load(Ordering::Relaxed);
        while value < cur_min {
            match self.min.compare_exchange_weak(
                cur_min, value,
                Ordering::Relaxed, Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => cur_min = actual,
            }
        }

        // Update max
        let mut cur_max = self.max.load(Ordering::Relaxed);
        while value > cur_max {
            match self.max.compare_exchange_weak(
                cur_max, value,
                Ordering::Relaxed, Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => cur_max = actual,
            }
        }
    }

    fn get(&self) -> (u64, u64) {
        (
            self.min.load(Ordering::Relaxed),
            self.max.load(Ordering::Relaxed),
        )
    }
}

}

Example: Once flag for initialization

Ensures function runs exactly once: state machine INCOMPLETE→RUNNING→COMPLETE. First thread CAS to RUNNING executes, others spin. For long init, use std::sync::Once which parks threads. Use for singleton init, lazy statics.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

struct OnceFlag {
    state: AtomicUsize,
}

const INCOMPLETE: usize = 0;
const RUNNING: usize = 1;
const COMPLETE: usize = 2;

impl OnceFlag {
    fn new() -> Self {
        Self {
            state: AtomicUsize::new(INCOMPLETE),
        }
    }

    // once.call_once(|| println!("init"));

    fn call_once<F>(&self, f: F)
    where
        F: FnOnce(),
    {
        if self.state.load(Ordering::Acquire) == COMPLETE {
            return;
        }

        match self.state.compare_exchange(
            INCOMPLETE,
            RUNNING,
            Ordering::Acquire,
            Ordering::Acquire,
        ) {
            Ok(_) => {
                // We won the race
                f();
                self.state.store(COMPLETE, Ordering::Release);
            }
            Err(RUNNING) => {
                // Someone else running, wait
                while self.state.load(Ordering::Acquire) == RUNNING
                {
                    std::hint::spin_loop();
                }
            }
            Err(COMPLETE) => {
                // Already done
            }
            _ => unreachable!(),
        }
    }

    fn is_completed(&self) -> bool {
        self.state.load(Ordering::Acquire) == COMPLETE
    }
}

}

Example: Atomic swap chain

Atomically swap heap pointers: allocate new, swap with AcqRel, free old. Zero overhead on load() vs Arc’s refcounting. Use for config hot-reload, double-buffering, RCU-style updates. Production code needs epoch-based reclamation.

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

struct SwapChain<T> {
    value: AtomicUsize, // Actually *mut T
    _phantom: std::marker::PhantomData<T>,
}

impl<T> SwapChain<T> {
    fn new(initial: T) -> Self {
        let ptr = Box::into_raw(Box::new(initial));
        Self {
            value: AtomicUsize::new(ptr as usize),
            _phantom: std::marker::PhantomData,
        }
    }

    fn swap(&self, new_val: T) -> T {
        let new_ptr = Box::into_raw(Box::new(new_val));
        let old =
            self.value.swap(new_ptr as usize, Ordering::AcqRel);
        let old_ptr = old as *mut T;

        unsafe {
            let old_val = std::ptr::read(old_ptr);
            drop(Box::from_raw(old_ptr));
            old_val
        }
    }

    fn load(&self) -> T where T: Clone {
        let ptr = self.value.load(Ordering::Acquire) as *mut T;
        unsafe { (*ptr).clone() }
    }
}

impl<T> Drop for SwapChain<T> {
    fn drop(&mut self) {
        let p = self.value.load(Ordering::Acquire) as *mut T;
        if !p.is_null() {
            unsafe { drop(Box::from_raw(p)); }
        }
    }
}

fn main() {
    println!("=== Striped Counter ===\n");

    let counter = Arc::new(StripedCounter::new(16));
    let mut handles = vec![];

    let start = Instant::now();

    for _ in 0..10 {
        let counter = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..100_000 {
                counter.increment();
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let elapsed = start.elapsed();
    println!("Count: {} in {:?}", counter.get(), elapsed);

    println!("\n=== Backoff ===\n");

    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..10_000 {
                cas_with_backoff(&counter);
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Count: {}", counter.load(Ordering::Relaxed));

    println!("\n=== Atomic Min/Max ===\n");

    let minmax = Arc::new(AtomicMinMax::new());
    let mut handles = vec![];

    for i in 0..10 {
        let minmax = Arc::clone(&minmax);
        handles.push(thread::spawn(move || {
            for j in 0..1000 {
                minmax.update(i * 1000 + j);
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let (min, max) = minmax.get();
    println!("Min: {}, Max: {}", min, max);

    println!("\n=== Once Flag ===\n");

    let once = Arc::new(OnceFlag::new());
    let mut handles = vec![];

    for i in 0..10 {
        let once = Arc::clone(&once);
        handles.push(thread::spawn(move || {
            once.call_once(|| {
                println!("Init by thread {}", i);
            });
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Completed: {}", once.is_completed());
}

Summary

This chapter covered atomic operations and lock-free programming:

  1. Memory Ordering: Relaxed, Acquire/Release, AcqRel, SeqCst with use cases
  2. Compare-and-Swap: CAS loops, weak vs strong, ABA problem and solutions
  3. Lock-Free Structures: Treiber stack, MPSC/SPSC queues, work-stealing deques
  4. Hazard Pointers: Safe memory reclamation without garbage collection
  5. Seqlock: Optimistic reads for small, frequently-read data

Key Takeaways:

  • Memory ordering is critical for correctness
  • Relaxed for counters, Acquire/Release for synchronization, SeqCst for simplicity
  • CAS is the foundation of lock-free algorithms
  • ABA problem requires version counters or hazard pointers
  • Lock-free != faster always (measure performance)
  • Seqlock excels for read-heavy small data

Performance Guidelines:

  • Use Relaxed when order doesn’t matter (fastest)
  • Acquire/Release for most synchronization (good balance)
  • SeqCst when correctness is critical (slowest)
  • Striped counters reduce contention
  • Backoff reduces CPU waste during contention
  • Lock-free shines under high contention

Common Pitfalls:

  • Wrong memory ordering (too weak = race, too strong = slow)
  • ABA problem (use versioning or hazard pointers)
  • Memory leaks (need reclamation strategy)
  • Assuming lock-free = faster (profile!)
  • Over-using atomics (sometimes locks are simpler)

When to Use:

  • Atomics: Counters, flags, simple synchronization
  • Lock-free: High contention, real-time constraints
  • Locks: Complex operations, simplicity, most cases
  • Seqlock: Coordinates, stats, small frequently-read data

Safety:

  • Rust’s type system prevents most data races
  • Atomic operations are safe
  • Raw pointers in lock-free structures require unsafe
  • Use existing libraries (crossbeam) when possible