Memory Model

Memory Model

Purpose

Guide agents through C++ and Rust memory models: memory orderings, the happens-before relation, atomic operations, fences, and practical patterns for lock-free data structures.

Triggers

• "What is the C++ memory model?"
• "What memory order should I use for my atomic operation?"
• "What is the difference between acquire-release and seq_cst?"
• "How do I use std::atomic in C++?"
• "What is acquire/release in Rust atomics?"
• "How do I implement a lock-free queue?"

Workflow

1. Memory ordering overview

Modern CPUs and compilers reorder operations for performance. The memory model specifies what reorderings are allowed and how synchronisation is achieved.

Ordering strength (weakest to strongest):
Relaxed < Release/Acquire < AcqRel < SeqCst

Stronger ordering = more synchronization = more correct, but slower
Weaker ordering  = fewer barriers = faster, but needs careful analysis

2. Memory orderings

3. C++ std::atomic

#include <atomic>
#include <thread>

std::atomic<int> counter{0};
std::atomic<bool> ready{false};

// Producer thread
void producer() {
    data = 42;                              // (1) write data
    ready.store(true, std::memory_order_release);  // (2) signal
}

// Consumer thread
void consumer() {
    while (!ready.load(std::memory_order_acquire));  // (3) wait
    assert(data == 42);                              // (4) guaranteed to see (1)
}

Acquire-release guarantees: if thread A does a release store to X, and thread B does an acquire load that sees A's value, then all writes by A before the release are visible to B after the acquire.

4. Choosing the right ordering

Use case?
├── Counter (just needs atomicity, order irrelevant)    → Relaxed
├── Reference counting (decrement + final check)        → AcqRel (dec), Acquire (load 0 check)
├── Publish data from one thread to another             → Release (store), Acquire (load)
├── Mutual exclusion / mutex implementation             → AcqRel / SeqCst
├── Lock-free queue multiple producers/consumers        → SeqCst (safest to start)
└── Sequence number check (simple flag)                 → Release + Acquire

5. Common patterns

// Pattern 1: Spinlock
class Spinlock {
    std::atomic_flag flag = ATOMIC_FLAG_INIT;
public:
    void lock() {
        while (flag.test_and_set(std::memory_order_acquire))
            ; // spin
    }
    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

// Pattern 2: Reference counting
class RefCounted {
    std::atomic<int> refcount{1};
public:
    void addref() {
        refcount.fetch_add(1, std::memory_order_relaxed);  // only need atomicity
    }
    void release() {
        if (refcount.fetch_sub(1, std::memory_order_acq_rel) == 1) {
            // AcqRel ensures we see all writes from other releasers
            delete this;
        }
    }
};

// Pattern 3: One-time initialisation
class LazyInit {
    std::atomic<void*> ptr{nullptr};
    std::mutex mtx;
public:
    void* get() {
        void* p = ptr.load(std::memory_order_acquire);
        if (p == nullptr) {
            std::lock_guard lock(mtx);
            p = ptr.load(std::memory_order_relaxed);
            if (p == nullptr) {
                p = create();
                ptr.store(p, std::memory_order_release);
            }
        }
        return p;
    }
};

6. Rust atomics

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

// Simple counter
let counter = Arc::new(AtomicUsize::new(0));

// Increment
counter.fetch_add(1, Ordering::Relaxed);

// Read
let val = counter.load(Ordering::Relaxed);

// Publish/subscribe pattern
static READY: AtomicBool = AtomicBool::new(false);

// Publisher thread
unsafe { DATA = 42; }  // Write data
READY.store(true, Ordering::Release);  // Signal

// Subscriber thread
while !READY.load(Ordering::Acquire) {}
let d = unsafe { DATA };  // Safe: guaranteed to see publisher's write

7. Fences

Fences provide ordering without an atomic operation on a specific variable:

// C++ fence — equivalent to a global memory barrier
std::atomic_thread_fence(std::memory_order_acquire);  // Acquire fence
std::atomic_thread_fence(std::memory_order_release);  // Release fence

// Typical use: multiple atomic writes then one fence
relaxed_atomic_a.store(1, std::memory_order_relaxed);
relaxed_atomic_b.store(2, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_release);  // barrier for all above
sentinel.store(true, std::memory_order_relaxed);

8. Common mistakes

For memory ordering rules and happens-before reference, see references/cpp-memory-ordering.md.

Related skills

• Use skills/runtimes/sanitizers — TSan detects data races involving non-atomic accesses
• Use skills/rust/rust-sanitizers-miri for detecting Rust memory ordering violations with Miri
• Use skills/low-level-programming/assembly-x86 to understand generated fence instructions
• Use skills/debuggers/gdb for debugging concurrent programs with thread inspection

C++ Memory Ordering Reference

Happens-Before Relation

A happens-before (HB) relationship between operation A and B means: the effects of A are guaranteed to be visible when B executes.

Establishing HB:

1. Sequenced-before: program order within a single thread 2. Synchronizes-with: a release operation synchronizes-with an acquire operation that reads its value 3. Transitivity: if A HB B and B HB C, then A HB C

Thread 1:                    Thread 2:
x = 42;        ←─────────────────────────────────────
flag.store(true,             while(!flag.load(
  release);     ─ sync-with ─  acquire));
                             assert(x == 42);  // HB guarantees this

Memory Order Rules Table

SeqCst Total Order

memory_order_seq_cst establishes a single total order across all seq_cst operations in all threads. Every thread observes these operations in the same order.

std::atomic<bool> x{false}, y{false};
std::atomic<int> z{0};

void write_x() { x.store(true, std::memory_order_seq_cst); }
void write_y() { y.store(true, std::memory_order_seq_cst); }

void read_x_then_y() {
    while (!x.load(seq_cst));
    if (y.load(seq_cst)) z.fetch_add(1, seq_cst);
}
void read_y_then_x() {
    while (!y.load(seq_cst));
    if (x.load(seq_cst)) z.fetch_add(1, seq_cst);
}

// SeqCst guarantees: z will never be 0 after both readers complete
// With weaker orderings, z could be 0 (both readers miss each other's store)

CAS (Compare-And-Swap) Patterns

// Strong CAS (never spuriously fails)
std::atomic<int> val{0};

int expected = 0;
bool success = val.compare_exchange_strong(
    expected,              // Updated to actual val if fail
    42,                    // New value to write
    std::memory_order_acq_rel,   // success ordering
    std::memory_order_relaxed    // failure ordering (load only)
);

// Weak CAS (may spuriously fail, use in retry loops)
int expected = 0;
while (!val.compare_exchange_weak(expected, 42,
    std::memory_order_acq_rel,
    std::memory_order_relaxed)) {
    expected = 0;  // Reset if failed
}

CAS ordering rule: failure ordering must not be stronger than success ordering; failure ordering cannot be Release or AcqRel (it's a load).

Lock-Free Stack

template<typename T>
class LockFreeStack {
    struct Node {
        T data;
        Node* next;
    };
    std::atomic<Node*> head{nullptr};

public:
    void push(T val) {
        Node* node = new Node{val, nullptr};
        node->next = head.load(std::memory_order_relaxed);
        while (!head.compare_exchange_weak(
                node->next, node,
                std::memory_order_release,
                std::memory_order_relaxed)) {}
    }

    std::optional<T> pop() {
        Node* node = head.load(std::memory_order_acquire);
        while (node != nullptr &&
               !head.compare_exchange_weak(
                node, node->next,
                std::memory_order_acquire,
                std::memory_order_acquire)) {}
        if (node == nullptr) return std::nullopt;
        T val = std::move(node->data);
        // Note: ABA problem and safe memory reclamation omitted
        delete node;
        return val;
    }
};

Platform Memory Models

x86 TSO means: on x86, Acquire/Release operations are essentially "free" (no explicit barrier). SeqCst still requires an mfence or locked operation. On ARM, every Acquire needs a dmb ish barrier.

std::atomic_flag (Simplest Atomic)

// Only guaranteed lock-free atomic type
std::atomic_flag flag = ATOMIC_FLAG_INIT;  // starts false

// Test-and-set (returns old value, sets to true)
bool was_set = flag.test_and_set(std::memory_order_acquire);

// Clear (set to false)
flag.clear(std::memory_order_release);

// C++20: test without setting
bool val = flag.test(std::memory_order_acquire);

Rust Ordering Equivalents

Quick Selection Guide

Counter only (e.g., statistics):
    → Relaxed for all operations

Reference count:
    → Relaxed for addref
    → AcqRel for release (detect zero)
    → Acquire for optional final load

One writer, one reader flag:
    → Release on store
    → Acquire on load

Multiple writers, single reader:
    → AcqRel on all modifications
    → Acquire on read

Need global ordering across multiple atomics:
    → SeqCst on everything (but benchmark!)