Memory ordering

Deep dive

Decision table

Code

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

// 1. Message passing (one-shot). Release/Acquire make the plain write to `data` visible.
pub struct Mailbox { ready: AtomicBool, data: UnsafeCell<u64> }
unsafe impl Sync for Mailbox {}
impl Mailbox {
    pub fn send(&self, v: u64) { // call at most once
        unsafe { *self.data.get() = v; }
        self.ready.store(true, Release);
    }
    pub fn recv(&self) -> Option<u64> {
        if self.ready.load(Acquire) { Some(unsafe { *self.data.get() }) } else { None }
    }
}

// 2. Reference count, as in std::sync::Arc.
pub fn rc_inc(rc: &AtomicUsize) { rc.fetch_add(1, Relaxed); }
pub fn rc_dec(rc: &AtomicUsize) -> bool { // true => caller frees
    if rc.fetch_sub(1, Release) != 1 { return false; }
    fence(Acquire); // synchronize with every other owner's Release decrement
    true
}

// 3. Store buffering: "a == 0 && b == 0" is impossible only with SeqCst.
pub static X: AtomicBool = AtomicBool::new(false);
pub static Y: AtomicBool = AtomicBool::new(false);
pub fn thread_a() -> bool { X.store(true, SeqCst); Y.load(SeqCst) }
pub fn thread_b() -> bool { Y.store(true, SeqCst); X.load(SeqCst) }
// With Release/Acquire both can return false: each store sits in its core's store buffer.

// 4. Spin on a relaxed load, then one acquire fence (cheaper loop body on ARM).
pub fn wait_ready(flag: &AtomicBool) {
    while !flag.load(Relaxed) { std::hint::spin_loop(); }
    fence(Acquire);
}

Efficiency

• Cost: on x86-64 acquire loads and release stores are plain mov; a SeqCst store is an xchg, order of 20 cycles. On AArch64 they are ldar/stlr, relaxed is ldr/str. Contention costs far more than ordering: order of 50-100+ ns per line transfer. Bound: coherence traffic, not the fence.
• Levers:
  • Relaxed for counters that publish nothing — plain lock xadd or ldadd, no fences — statistics, refcount increments
  • Release/Acquire instead of SeqCst — plain mov on x86, no xchg or mfence (table above) — message passing, locks
  • relaxed spin loop plus one fence(Acquire) — cheaper loop body on ARM — flag waits
  • build for ARMv8.1 LSE (-march=armv8.1-a, Rust +lse) — single-instruction atomics instead of LL/SC retry loops (see Pitfalls) — Graviton, Apple Silicon
  • remove the shared write instead of weakening its order (sharded counters) — contention dominates — hot counters
• Naive → standard → state of the art:
  • SeqCst on every access · an xchg per store, order of 20 cycles
  • Release/Acquire per pattern (decision table) · plain mov on x86
  • relaxed accesses with a single fence, LSE atomics, no shared writes on the hot path · order of 1 ns per operation

Rules that matter

• Happens-before comes from a release operation and an acquire operation on the same atomic, where the acquire reads the value written by the release (or a later RMW in its release sequence).
• Acquire/release on different variables gives no ordering between them.
• RMWs (fetch_add, swap, CAS) always read the latest value in that location's modification order, even when Relaxed; plain Relaxed loads may read stale values.
• Every atomic location has a single total modification order that all threads agree on (coherence), even with Relaxed.
• Fences: a fence(Release) before a relaxed store acts like a release store; a fence(Acquire) after a relaxed load acts like an acquire load.
• SeqCst operations form one total order consistent with happens-before; mixing SeqCst with weaker accesses on the same locations is subtle (C++20 repaired the rules after Lahav et al. 2017).

Pitfalls

• "It works on x86": TSO hides missing acquire/release at the hardware level, but the compiler can still reorder. Test on ARM (Apple Silicon, Graviton) and with model checkers.
• load then store instead of an RMW: lost updates.
• volatile (C/C++) or read_volatile (Rust) is not atomic and orders nothing across threads.
• Using Acquire on a store or Release on a load: Rust panics at runtime for load(Release); C++ makes it undefined.
• Flag-based sleep/wake (set "sleeping", check queue; producer pushes, checks "sleeping") with only acquire/release: both sides can miss each other. Needs SeqCst fences or a lock.
• Pre-LSE ARM (ARMv8.0) atomics are LL/SC loops that livelock-ish under contention; build with LSE (-march=armv8.1-a, Rust +lse, or GCC outline atomics).
• Benchmarks of "SeqCst is slow" usually measure contention, not the fence.

Tooling

• Rust: loom (exhaustive interleavings under the C11 model), Miri (detects data races and some weak-memory behaviours), ThreadSanitizer (-Zsanitizer=thread).
• C/C++: ThreadSanitizer, GenMC, CDSChecker, herd7 litmus tests for hardware models.

Implementations

Sources

• Hans-J. Boehm, Sarita V. Adve, Foundations of the C++ Concurrency Memory Model, PLDI 2008. paper
• Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, Magnus O. Myreen, x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors, Communications of the ACM 53(7), 2010. paper
• Ori Lahav, Viktor Vafeiadis, Jeehoon Kang, Chung-Kil Hur, Derek Dreyer, Repairing Sequential Consistency in C/C++11, PLDI 2017. paper
• Mara Bos, Rust Atomics and Locks, O'Reilly, 2023. book
• Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, kernel.org (continuously updated). book