Crust of Rust: Atomics and Memory Ordering

This chapter explores the low-level mechanics of concurrent programming in Rust, focusing on atomic types and the memory ordering guarantees that govern multi-threaded execution. We will demystify how the compiler and CPU optimize memory accesses, why naive synchronization fails, and how to construct sound, lock-free primitives using Rust's atomic API.

1. Why Do We Need Atomics? (The Problem of Shared State)

In a single-threaded program, the compiler and CPU cooperate to ensure that your code executes in a way that preserves sequential consistency. However, when multiple threads access the same memory location concurrently, this illusion breaks down.

If you attempt to share a primitive type (such as a bool or usize) across thread boundaries without synchronization, you run into two fundamental issues:

1. Data Races & Undefined Behavior: If two threads access the same memory location concurrently, and at least one of the accesses is a write, you have a data race. In Rust, data races are classified as Undefined Behavior (UB). Once UB occurs, the compiler is free to optimize away entire blocks of code, leading to unpredictable crashes or silent data corruption.
2. Lack of Visibility Guarantees: Even if data racing were somehow "sound," there is no guarantee that a write operation performed by Thread A will ever become visible to Thread B. The CPU might cache the value in a local register or L1 cache, or the compiler might optimize away a read loop entirely, assuming the value cannot change.

Atomics solve these problems by:

• Generating specialized CPU instructions that guarantee indivisible (atomic) reads and writes.
• Placing strict constraints on how both the compiler and the CPU are allowed to reorder memory operations.

2. The Core Mental Model & Interior Mutability

An atomic type (such as AtomicUsize or AtomicBool) has the exact same in-memory representation and size as its primitive counterpart (usize or bool). The key difference lies in how they are accessed.

Interior Mutability via UnsafeCell

To modify a standard primitive value, Rust requires an exclusive reference (&mut T). However, atomic types allow modification through a shared reference (&self). Under the hood, atomic types wrap their inner primitive in an UnsafeCell:

// Conceptual representation of an atomic type in the standard library
pub struct AtomicUsize {
    v: std::cell::UnsafeCell<usize>,
}

Because UnsafeCell disables the compiler's alias analysis optimizations, it serves as the primitive building block for interior mutability. The atomic methods then use raw assembly instructions to ensure these shared accesses are safe across threads.

Sharing Atomics Across Threads

Because threads spawned via std::thread::spawn require closures with a 'static lifetime, you cannot easily share stack-allocated atomics using raw references. Instead, atomics are typically shared using one of two patterns:

3. Naive vs. Atomic Mutex (The Spinlock Evolution)

To understand why atomic operations must be indivisible, let us attempt to implement a simple Spinlock Mutex from scratch.

The Naive (Broken) Approach

A naive implementation might attempt to use a simple load-and-store loop to acquire a lock:

use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicBool, Ordering};

pub struct NaiveMutex<T> {
    locked: AtomicBool,
    value: UnsafeCell<T>,
}

const LOCKED: bool = true;
const UNLOCKED: bool = false;

impl<T> NaiveMutex<T> {
    pub fn new(value: T) -> Self {
        Self {
            locked: AtomicBool::new(UNLOCKED),
            value: UnsafeCell::new(value),
        }
    }

    // WARNING: This implementation contains a critical race condition!
    pub fn with_lock<F, R>(&self, f: F) -> R
    where
        F: FnOnce(&mut T) -> R,
    {
        // 1. Spin-wait until the lock is unlocked
        while self.locked.load(Ordering::Relaxed) != UNLOCKED {
            std::thread::yield_now();
        }

        // 2. Set the lock to locked
        self.locked.store(LOCKED, Ordering::Relaxed);

        // 3. Access the protected value
        let result = f(unsafe { &mut *self.value.get() });

        // 4. Unlock
        self.locked.store(UNLOCKED, Ordering::Relaxed);

        result
    }
}

Why the Naive Approach Fails

The critical flaw in NaiveMutex is that the load (checking if unlocked) and the store (marking as locked) are two separate, non-atomic steps.

If Thread A and Thread B call with_lock concurrently, both can read UNLOCKED before either has a chance to execute the store instruction. Both threads will exit the loop, acquire a mutable reference to the same underlying data, and cause a data race.

4. Optimizing the Spinlock (The MESI Protocol & Cache Coherence)

To fix the race condition, we must combine the load and store into a single, indivisible CPU instruction. This is achieved using compare_exchange.

The Corrected Spinlock

impl<T> NaiveMutex<T> {
    pub fn with_lock_correct<F, R>(&self, f: F) -> R
    where
        F: FnOnce(&mut T) -> R,
    {
        // Atomically transition from UNLOCKED to LOCKED.
        // If the current value is UNLOCKED, set it to LOCKED and return Ok.
        // If the current value is already LOCKED, return Err and spin.
        while self.locked.compare_exchange_weak(
            UNLOCKED,
            LOCKED,
            Ordering::Acquire,
            Ordering::Relaxed
        ).is_err() {
            std::thread::yield_now();
        }

        let result = f(unsafe { &mut *self.value.get() });
        self.locked.store(UNLOCKED, Ordering::Release);
        result
    }
}

Optimizing for Cache Coherence (The MESI Protocol)

While the code above is correct, spinning on compare_exchange_weak is highly inefficient on multi-core processors due to how CPU caches coordinate.

Modern CPUs use cache coherence protocols like MESI (Modified, Exclusive, Shared, Invalid):

• Shared (S): Multiple cores have a read-only copy of the cache line containing our lock.
• Exclusive (E) / Modified (M): A core must obtain exclusive ownership of the cache line to write to it.

When a core executes compare_exchange, it issues a write intent, forcing all other cores to invalidate their local copies of that cache line. If 16 cores are spinning on compare_exchange, the cache line containing the lock constantly bounces between cores. This phenomenon is known as cacheline thrashing or ownership bouncing.

The Optimized Spin Loop

To mitigate cacheline thrashing, we can spin on a read-only load operation. A read-only load allows the cache line to remain in the Shared (S) state across all cores. Only when the load indicates the lock has been released do we attempt the expensive compare_exchange operation:

pub fn with_lock_optimized<F, R>(&self, f: F) -> R
where
    F: FnOnce(&mut T) -> R,
    {
        // Outer loop: Attempt to acquire exclusive lock
        while self.locked.compare_exchange_weak(
            UNLOCKED,
            LOCKED,
            Ordering::Acquire,
            Ordering::Relaxed
        ).is_err() {
            // Inner loop: Spin-read in Shared (S) state without invalidating other caches
            while self.locked.load(Ordering::Relaxed) == LOCKED {
                std::thread::yield_now();
            }
        }

        let result = f(unsafe { &mut *self.value.get() });
        self.locked.store(UNLOCKED, Ordering::Release);
        result
    }

5. Compare-Exchange: Strong vs. Weak

Rust's atomic types offer two variants of the compare-and-swap operation: compare_exchange and compare_exchange_weak.

The Hardware Reality: ARM vs. x86

On x86 architectures, the CPU provides a dedicated hardware instruction for compare-and-swap. Thus, compare_exchange and compare_exchange_weak compile to the same assembly instruction.

On ARM architectures, there is no single compare-and-swap instruction. Instead, ARM uses a pair of instructions:

1. Load-Linked (ldrex): Loads the value and registers a hardware monitor on the memory address.
2. Store-Conditional (strex): Stores the new value only if no other processor has modified that memory address since the ldrex.

If a context switch or interrupt occurs between ldrex and strex, the hardware monitor is cleared, and strex fails spuriously.

• To implement the guaranteed strong compare_exchange on ARM, the compiler must generate an internal loop around ldrex/strex to retry on spurious failures.
• If you are already calling the method inside a loop in your Rust code, using the strong variant results in a nested loop, which wastes registers and CPU cycles. Using compare_exchange_weak avoids this overhead by letting your outer loop handle the retry.

6. Memory Ordering Demystified: The Relaxed Anarchy

Memory ordering specifies how memory accesses around an atomic operation are allowed to be reordered by the compiler and the CPU.

What is Ordering::Relaxed?

Relaxed is the weakest memory ordering. It guarantees atomicity (you will never read a partially written value), but it provides no synchronization or ordering guarantees across threads.

Under Relaxed ordering, the compiler and CPU are free to reorder reads and writes arbitrarily, provided they do not violate single-threaded program logic.

Real-Life Analogy: Out-of-Order Execution

Imagine a manager writing two independent letters: one to a client and one to a supplier. Because the letters are unrelated, the manager might write them in any order, or even work on them simultaneously.

Similarly, if a thread performs two unrelated memory writes using Relaxed ordering, the CPU may execute them out of order, or write them to main memory out of order, to optimize pipeline efficiency.

The "Time Travel" Paradox

To see how extreme Relaxed reordering can be, consider the following classic concurrent execution:

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

static X: AtomicUsize = AtomicUsize::new(0);
static Y: AtomicUsize = AtomicUsize::new(0);

fn main() {
    let t1 = thread::spawn(|| {
        // Thread 1
        let r1 = Y.load(Ordering::Relaxed); // Load Y
        X.store(r1, Ordering::Relaxed);    // Store into X
        r1
    });

    let t2 = thread::spawn(|| {
        // Thread 2
        let r2 = X.load(Ordering::Relaxed); // Load X
        Y.store(42, Ordering::Relaxed);     // Store 42 into Y
        r2
    });

    let r1 = t1.join().unwrap();
    let r2 = t2.join().unwrap();

    println!("r1: {}, r2: {}", r1, r2);
}

The Surprising Result

It is entirely possible for this program to print r1: 42, r2: 42!

How can r1 read 42 from Y before Thread 2 has stored 42 into Y?

1. In Thread 2, the load of X and the store of 42 into Y are completely independent.
2. Because we used Ordering::Relaxed, the compiler or the CPU's out-of-order execution engine is allowed to reorder Thread 2's operations:

If Thread 2's store executes first, Thread 1 can load 42 from Y, store it in X, and then Thread 2 can load 42 from X. This demonstrates that without explicit synchronization, sequential time across threads is an illusion.

7. The Happens-Before Relationship: Acquire and Release

To safely coordinate data across threads, we must establish a happens-before relationship. This is achieved using the complementary pair: Acquire and Release.

Ordering::Release (For Stores)

When you store a value with Release ordering:

• No memory operations (reads or writes) that occurred before this store can be reordered after it.
• All writes performed by the current thread prior to this store are guaranteed to become visible to any thread that loads this value with Acquire ordering.

Ordering::Acquire (For Loads)

When you load a value with Acquire ordering:

• No memory operations (reads or writes) that occur after this load can be reordered before it.
• The current thread is guaranteed to see all memory writes that were synchronized via the corresponding Release store.

Correcting our Mutex with Acquire/Release

In our optimized spinlock, we must use Acquire when locking and Release when unlocking:

// Locking (Acquire)
self.locked.compare_exchange_weak(
    UNLOCKED,
    LOCKED,
    Ordering::Acquire, // Ensures subsequent critical section reads/writes don't escape upwards
    Ordering::Relaxed
)

// Critical Section
// (All reads and writes here are guaranteed to stay within the lock boundaries)

// Unlocking (Release)
self.locked.store(UNLOCKED, Ordering::Release); // Ensures prior critical section writes don't escape downwards

8. Global Consensus: Sequentially Consistent (SeqCst)

While Acquire and Release establish pairwise synchronization between threads, they do not guarantee a single, globally agreed-upon order of all operations across the entire system. For that, we need Ordering::SeqCst (Sequentially Consistent).

What is SeqCst?

SeqCst provides the same guarantees as Acquire (for loads) and Release (for stores), plus a total global ordering. All threads in the system are guaranteed to observe all SeqCst operations in the exact same sequence.

The Cost of SeqCst

To enforce a global order, the CPU must insert memory barriers (fences) and coordinate across all cores to synchronize cache pipelines. On weakly ordered architectures like ARM, this incurs a significant performance penalty.

9. Complete Flow Walkthrough: The Z-Counter Paradox

To understand the difference between Acquire/Release and SeqCst, let us analyze a classic concurrent puzzle.

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

static X: AtomicBool = AtomicBool::new(false);
static Y: AtomicBool = AtomicBool::new(false);
static Z: AtomicUsize = AtomicUsize::new(0);

fn main() {
    // Thread TX: Writes to X
    let tx = thread::spawn(|| {
        X.store(true, Ordering::Release);
    });

    // Thread TY: Writes to Y
    let ty = thread::spawn(|| {
        Y.store(true, Ordering::Release);
    });

    // Thread T1: Reads X, then Y
    let t1 = thread::spawn(|| {
        while !X.load(Ordering::Acquire) {} // Spin until X is true
        if Y.load(Ordering::Acquire) {
            Z.fetch_add(1, Ordering::Relaxed);
        }
    });

    // Thread T2: Reads Y, then X
    let t2 = thread::spawn(|| {
        while !Y.load(Ordering::Acquire) {} // Spin until Y is true
        if X.load(Ordering::Acquire) {
            Z.fetch_add(1, Ordering::Relaxed);
        }
    });

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

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

Can Z be 0 at the end of execution?

Case 1: Using Acquire / Release

If we use Acquire and Release orderings (as written above), Z can indeed be 0!

How is this possible?

1. Threads TX and TY write to independent memory locations (X and Y). There is no synchronization between TX and TY.
2. Thread T1 observes X as true (synchronizing with TX), but is allowed to observe Y as still being false.
3. Thread T2 observes Y as true (synchronizing with TY), but is allowed to observe X as still being false.
4. Because there is no global consensus on whether X or Y was written to first, both T1 and T2 can fail their respective if checks.

Case 2: Using SeqCst

If we change all stores and loads on X and Y to Ordering::SeqCst, Z can never be 0.

SeqCst forces a single global timeline. The system must agree on whether X or Y was set to true first.

• If X was set first, T2 will see X as true and increment Z.
• If Y was set first, T1 will see Y as true and increment Z.

10. Memory Ordering Comparison

11. Testing and Verification: Thread Sanitizer & Loom

Because concurrent bugs are highly non-deterministic and hardware-dependent, standard testing is insufficient. Rust developers rely on specialized tools to verify atomic code.

1. Thread Sanitizer (TSan)

Thread Sanitizer is a tool built into compilers (LLVM/Clang) that instruments memory accesses at runtime.

• How it works: It monitors every read and write operation as your program runs. If it detects two threads accessing the same memory address without a clear happens-before relationship, it flags a data race.
• Limitation: It can only detect bugs that actually occur during the specific execution of your test suite.

2. Loom (Model Checking)

Loom is a state-space exploration tool designed specifically for concurrent Rust.

• How it works: You replace standard library types with Loom's equivalents (e.g., loom::sync::atomic::AtomicUsize). Loom then runs your test case repeatedly, systematically simulating every single legally permitted thread interleaving and memory reordering allowed by the memory model.

#[test]
fn test_concurrent_logic() {
    loom::model(|| {
        let atomic = Arc::new(AtomicUsize::new(0));
        let atomic_clone = atomic.clone();

        let th = thread::spawn(move || {
            atomic_clone.store(1, Ordering::Release);
        });

        let val = atomic.load(Ordering::Acquire);
        th.join().unwrap();
    });
}

• Loom Limitations:
  • State Space Explosion: If your test case has too many threads or operations, the number of possible interleavings becomes too large to compute. Keep Loom tests small and focused.
  • SeqCst Approximation: Loom currently downgrades SeqCst operations to AcqRel during analysis. This means it may report false positives (spurious bugs) for code that strictly relies on SeqCst global ordering, but it will never miss a real bug (no false negatives).

12. Related Concepts: Fences, Volatile, and AtomicPointer

Fences vs. Atomics

An atomic operation associates memory ordering with a specific memory location. A fence (or memory barrier) is a standalone operation that establishes ordering constraints without being tied to a specific atomic variable.

use std::sync::atomic::fence;
// Establishes a release barrier across all preceding writes
fence(Ordering::Release);

Fences are rarely needed in modern Rust; atomic operations with explicit orderings are preferred because they are easier to reason about and allow the compiler to generate more optimized code.

Volatile vs. Atomics

A common point of confusion is the difference between volatile operations and atomic operations.

• Atomics are for multi-threaded synchronization. They prevent data races and coordinate memory visibility between different CPU cores.
• Volatile (e.g., core::ptr::read_volatile) is for Memory-Mapped I/O (MMIO). It tells the compiler that a memory location can be modified by hardware outside the program (e.g., a network card register). The compiler is forbidden from optimizing away, caching, or reordering volatile reads and writes within a thread, but volatile operations do not generate multi-core synchronization instructions or prevent multi-threaded data races.

AtomicPointer

AtomicPointer<T> is simply an AtomicUsize specialized for raw pointers (*mut T). It does not provide any automatic safety guarantees for the data behind the pointer; you must still use unsafe blocks and correct memory ordering to dereference and access the underlying data.

13. Summary and Key Takeaways

• Atomics are the foundation of concurrency: They prevent undefined behavior by ensuring memory operations are indivisible and visible across threads.
• Interior Mutability: Atomics use UnsafeCell under the hood, allowing safe mutation through shared references (&self).
• Avoid Cacheline Thrashing: When implementing spinlocks, spin on a read-only load (Shared state) before attempting an expensive compare_exchange (Exclusive state).
• Use Weak Compare-Exchange in Loops: On ARM architectures, compare_exchange_weak avoids nested loops and generates more efficient assembly.
• Relaxed has no ordering: Only use Relaxed when you do not care about the relative order of other memory operations (e.g., simple counters).
• Acquire / Release is your workhorse: Use this pair to establish a happens-before relationship between producer and consumer threads.
• SeqCst is powerful but expensive: It guarantees a single global timeline across all threads, but incurs a high performance penalty on weakly ordered CPUs like ARM.
• Don't write lock-free code unless you have to: Lock-free programming is incredibly difficult to get right. Prefer standard mutexes (std::sync::Mutex) unless profiling proves that synchronization is a bottleneck. If you must write lock-free code, verify it using Loom and Thread Sanitizer.