# Atomics and memory ordering

> How C++ defines memory locations, data races, happens-before graphs, acquire-release synchronization, store buffering, and fences.

- **Source:** C++ Atlas (https://cppatlas.com/topics/atomics-and-memory-ordering)
- **Track:** Memory model
- **Estimated reading time:** 11 minutes
- **ISO C++ clauses:** [intro.memory] (https://eel.is/c++draft/intro.memory), [intro.races] (https://eel.is/c++draft/intro.races), [atomics.order] (https://eel.is/c++draft/atomics.order), [atomics.types.generic] (https://eel.is/c++draft/atomics.types.generic), [atomics.fences] (https://eel.is/c++draft/atomics.fences), [atomics.ref.generic] (https://eel.is/c++draft/atomics.ref.generic)
- **cppreference links:** [Memory model](https://en.cppreference.com/w/cpp/language/memory_model), [std::atomic](https://en.cppreference.com/w/cpp/atomic/atomic), [std::memory_order](https://en.cppreference.com/w/cpp/atomic/memory_order), [std::atomic_ref](https://en.cppreference.com/w/cpp/atomic/atomic_ref), [std::atomic_thread_fence](https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence), [std::atomic::compare_exchange_weak](https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange)
- **Prerequisites:** object-lifetime-and-storage, evaluation-order

Locks protect critical sections at the cost of kernel waits or contention. Lock-free programming swaps coarse mutual exclusion for `std::atomic<T>` and explicit **memory ordering constraints**—contracts governing both how the compiler may reorder instructions and which hardware memory barriers must synchronize store buffers across cores.

## Memory locations, bit-fields, and data races

Thread safety in C++ begins at the granularity of a **memory location** (`[intro.memory]`). A memory location is either an object of scalar type (`int`, `double`, pointer) or a maximal sequence of adjacent non-zero-length bit-fields.

Two threads may access distinct memory locations concurrently with zero synchronization. Adjacent scalar struct members (`int a; int b;`) occupy separate memory locations, whereas adjacent non-zero bit-fields share a **single** memory location because CPUs update them via non-atomic read-modify-write instructions on the enclosing machine word:

```cpp
struct Flags {
    unsigned rx_ready : 4;
    unsigned          : 0; // Zero-width bit-field starts a new memory location
    unsigned tx_ready : 4;
};
```

Without the `: 0` separator, one thread writing `f.rx_ready = 1` while another writes `f.tx_ready = 2` triggers a **data race**. Under `[intro.races]`, two conflicting accesses (at least one write, at least one non-atomic) with no happens-before ordering cause **undefined behavior**—not merely a torn read.

When existing non-atomic aligned data needs temporary atomic access during a parallel phase without changing its stored type permanently, C++20 provides `std::atomic_ref<T>` (`[atomics.ref.generic]`), provided no non-atomic access overlaps the lifetime of the `atomic_ref` usage.

> **Standardese.** Per `[intro.races]`, a data race on any non-atomic variable poisons the entire execution with undefined behavior—even on architectures where aligned word reads and writes appear atomic at the assembly level.

## Sequenced-before, synchronizes-with, and happens-before

The C++ memory model guarantees visibility across threads by composing three partial-order relations:

- **Sequenced-before:** evaluation order within a single thread.
- **Synchronizes-with:** an inter-thread edge formed when an atomic release store (or release fence + relaxed store) writes a value read by an atomic acquire load (or relaxed load + acquire fence).
- **Happens-before:** the transitive closure of sequenced-before and synchronizes-with.

```text
Thread 1 (Producer)                        Thread 2 (Consumer)
  payload = 42;
       │  sequenced-before
       ▼
  ready.store(true, release) ──synchronizes-with──▶ while (!ready.load(acquire))
                                                           │  sequenced-before
                                                           ▼
                                                     assert(payload == 42);
```

Because `payload = 42` is sequenced-before `ready.store(true, release)`, and the acquire loop reads that `true` value, `payload = 42` **happens-before** `assert(payload == 42)`. Notice that a release-acquire chain also extends through **release sequences**: if intermediate threads perform atomic read-modify-write operations (`fetch_add`, `exchange`, `compare_exchange`) on `ready` with any ordering (even `relaxed`), an acquire load reading the final value in that modification chain still synchronizes with the initial release store (`[intro.races]`).

> **Mental model.** Release-acquire synchronization does not "flush CPU caches." It erects a one-way happens-before bridge: ordinary writes before a release store cannot sink past it, and ordinary reads after an acquire load cannot hoist ahead of it.

## The memory_order spectrum compared

Every `std::atomic` operation accepts one of the `std::memory_order` modes (`std::memory_order_seq_cst` by default):

| Memory order | Atomicity | Surrounding reordering constraints | Cross-thread total order |
| --- | --- | --- | --- |
| `relaxed` | Indivisible RMW and reads | None for unrelated memory accesses | Single atomic's modification order only |
| `acquire` | Indivisible read or RMW | Prevents later reads/writes hoisting ahead of load | Pairwise with matching `release` |
| `release` | Indivisible store or RMW | Prevents earlier reads/writes sinking past store | Pairwise with matching `acquire` |
| `acq_rel` | Indivisible RMW | Combines `acquire` and `release` on RMWs | Pairwise on read and write sides |
| `seq_cst` | Indivisible load, store, or RMW | Full `acquire`/`release` semantics plus global order | Single total modification order `S` |

Note that `memory_order::consume` (intended for hardware data-dependency ordering) has been discouraged since C++17; compilers treat it identically to `acquire`.

## Store buffering and why acquire-release is not seq_cst

Developers often assume `release` on stores paired with `acquire` on loads forbids all counter-intuitive outcomes. The **Store Buffering** litmus test proves otherwise—even on strongly ordered x86-64 CPUs!

Suppose `std::atomic<int> x{0}, y{0};` start at zero:

- **Thread 1:** `x.store(1, release); int r1 = y.load(acquire);`
- **Thread 2:** `y.store(1, release); int r2 = x.load(acquire);`

Can **both `r1 == 0` and `r2 == 0`** occur? **Yes.** Release forbids prior writes from sinking past the store, and acquire forbids subsequent reads from hoisting ahead of the load—yet **neither** prevents a following acquire load from moving *before* an earlier release store into a core's local store buffer! Each core buffers its own `1` store locally while its read misses the peer's buffer and observes `0`.

Replacing those operations with `std::memory_order::seq_cst` forces a single global order `S` across all `seq_cst` operations, making `r1 == 0 && r2 == 0` impossible.

> **Pitfall.** Sequential consistency holds **only** among `seq_cst` operations. Mixing `relaxed` or `acquire`/`release` operations into a `seq_cst` protocol breaks the global `S` ordering guarantees you relied on to prevent store-buffering anomalies.

## Compare-exchange loops and fences

Read-modify-write algorithms frequently build custom transitions using `compare_exchange_weak` or `compare_exchange_strong`:

```cpp
#include <atomic>

void atomic_update_max(std::atomic<int>& target, int candidate) noexcept {
    int current = target.load(std::memory_order::relaxed);
    while (current < candidate &&
           !target.compare_exchange_weak(
               current, candidate,
               std::memory_order::release,
               std::memory_order::relaxed)) {
        // On failure, `current` is reloaded with target's latest value.
    }
}
```

Use `compare_exchange_weak` inside retry loops because architectures with load-linked/store-conditional (ARM, POWER) may fail spuriously without extra retry loops inside the instruction sequence; use `compare_exchange_strong` for single-shot state flips where looping would cost extra boilerplate. Under C++17+, the failure memory order only needs to avoid `release` and `acq_rel` (`[atomics.types.operations]`).

When a reader loops many times checking a relaxed flag and only consumes shared data once ready, **`std::atomic_thread_fence`** avoids executing acquire barriers on every failed iteration:

```cpp
#include <atomic>

std::atomic<int> state{0};
int shared_data = 0;

void fence_publish() {
    shared_data = 99;
    std::atomic_thread_fence(std::memory_order::release);
    state.store(1, std::memory_order::relaxed);
}

int fence_consume() {
    if (state.load(std::memory_order::relaxed) == 1) {
        std::atomic_thread_fence(std::memory_order::acquire);
        return shared_data;
    }
    return 0;
}
```

> **Pitfall.** `std::atomic<BigStruct>` compiles quietly for arbitrary trivially copyable structs by falling back to an internal mutex shard table. Always verify `std::atomic<T>::is_always_lock_free` with `static_assert` when targeting real-time or lock-free paths.

## What to remember

- Two threads writing adjacent non-zero bit-fields share **one memory location** and create data-race UB unless separated by `: 0` or synchronized.
- **`relaxed`** guarantees atomicity and single-variable modification order (ideal for pure counters) without synchronizing surrounding non-atomic memory.
- Pair **`release`** stores with **`acquire`** loads to form `synchronizes-with` edges that carry non-atomic payload writes via `happens-before`.
- **`acquire`/`release`** still permits Store Buffering (`r1 == 0 && r2 == 0`); reach for **`seq_cst`** when a single global total order across distinct atomics is required.
- Prefer **`compare_exchange_weak`** in retry loops and verify **`is_always_lock_free`** before assuming hardware atomic instructions.

## Concept Map Outline

- **Atomics and Memory Ordering:** Abstract machine synchronization guarantees connecting C++ threads, compilers, and CPU store buffers.
  - **Memory Locations and Races:** Smallest units of storage accessible independently across concurrent threads.
    - **Scalars vs Bit-Fields:** Adjacent scalars are independent locations while adjacent non-zero bit-fields share one.
    - **Zero-Width Bit-Field Split:** Inserting an unnamed : 0 bit-field separates neighboring fields into distinct locations.
    - **Data Race Undefined Behavior:** Unordered conflicting accesses with one non-atomic write invalidate the whole program.
  - **Happens-Before Relations:** Mathematical ordering edges proving when one thread observes another's writes.
    - **Sequenced-Before Order:** Intra-thread evaluation ordering established within a single execution stream.
    - **Synchronizes-With Edge:** Inter-thread link created when an acquire load reads a release store.
    - **Release Sequences:** Chained atomic RMW operations preserve synchronization back to the initial release store.
  - **Memory Order Spectrum:** Six ordering tags balancing barrier cost against cross-thread guarantees.
    - **Relaxed Counters:** Guarantees indivisible operations and modification order without ordering nearby memory.
    - **Acquire-Release Pairwise:** Prevents earlier writes sinking past release and later reads hoisting above acquire.
    - **Seq-Cst Global Total Order:** Enforces one consistent global order S across all seq_cst atomic operations.
  - **Litmus Tests and Hardware:** Why hardware store buffers break naive intuition without fences.
    - **Store Buffering Anomaly:** Acquire-release allows both cores to read zero because store buffers delay writes.
    - **Lock-Free Hardware Checks:** Verify is_always_lock_free so large structs do not silently fall back to hidden mutexes.
  - **CAS Loops and Fences:** Idiomatic lock-free algorithms built from compare-exchange and standalone barriers.
    - **Weak vs Strong CAS:** Prefer compare_exchange_weak inside retry loops to avoid redundant LL/SC checks.
    - **atomic_thread_fence Pairing:** Release and acquire fences synchronize relaxed atomics only on the fast exit path.

## Standardese Quiz Questions

### Question 1 [warmup] ([atomics.order], [intro.races])

If 8 threads solely increment a shared telemetry counter `counter.fetch_add(1, order)` without publishing any non-atomic data alongside it, which memory order suffices for exact totals?

A. std::memory_order::relaxed
B. std::memory_order::acquire
C. std::memory_order::acq_rel
D. std::memory_order::seq_cst

**Answer (A):** std::memory_order::relaxed

**Why:** Every std::atomic read-modify-write operation is indivisible and obeys the single-object modification order regardless of memory_order. Because no surrounding non-atomic writes need ordering, relaxed suffices without losing counts.

### Question 2 [warmup] ([atomics.types.operations])

Why does `compare_exchange_weak` exist alongside `compare_exchange_strong`?

A. compare_exchange_weak uses non-atomic loads for better throughput
B. compare_exchange_weak does not reload the expected parameter upon failure
C. compare_exchange_weak may fail spuriously on LL/SC architectures, avoiding an internal retry loop when you are already inside a while loop
D. compare_exchange_strong cannot use memory_order::seq_cst

**Answer (C):** compare_exchange_weak may fail spuriously on LL/SC architectures, avoiding an internal retry loop when you are already inside a while loop

**Why:** On LL/SC architectures (such as ARM and POWER), compare_exchange_weak maps directly to a single LL/SC attempt that can fail spuriously due to interrupts or cache contention. Inside a CAS loop, letting the outer while loop retry avoids redundant inner branches.

### Question 3 [tricky] ([atomics.order])

Given `std::atomic<int> x{0}, y{0};`, Thread 1 runs `x.store(1, release); r1 = y.load(acquire);` while Thread 2 runs `y.store(1, release); r2 = x.load(acquire);`. Can `r1 == 0 && r2 == 0` occur?

```cpp
std::atomic<int> x{0}, y{0};
// Thread 1: x.store(1, std::memory_order::release); int r1 = y.load(std::memory_order::acquire);
// Thread 2: y.store(1, std::memory_order::release); int r2 = x.load(std::memory_order::acquire);
```

A. No, because release and acquire guarantee sequential consistency
B. Yes—hardware store buffers allow each thread's acquire load to execute before its own buffered release store becomes visible globally
C. No, at least on x86-64 CPUs because TSO forbids reordering
D. Yes, because accessing two separate atomics without a mutex is undefined behavior

**Answer (B):** Yes—hardware store buffers allow each thread's acquire load to execute before its own buffered release store becomes visible globally

**Why:** This is the Store Buffering (SB) litmus test. Neither release nor acquire forbids a subsequent acquire load from completing before an earlier release store drains from the core's store buffer—even on x86-64. Only memory_order::seq_cst enforces a single total order preventing r1 == 0 && r2 == 0.

### Question 4 [tricky] ([intro.memory], [intro.races])

In `struct Packet { unsigned a : 4; unsigned b : 4; } p{};`, Thread 1 writes `p.a = 1;` while Thread 2 concurrently writes `p.b = 2;`. What does the C++ standard say?

```cpp
struct Packet { unsigned a : 4; unsigned b : 4; } p{};
// T1: p.a = 1;
// T2: p.b = 2;
```

A. Well-defined because a and b have distinct member names
B. Well-defined as long as p is aligned to 8 bytes
C. Implementation-defined value, never undefined behavior
D. Undefined behavior due to a data race on a single shared memory location

**Answer (D):** Undefined behavior due to a data race on a single shared memory location

**Why:** Under [intro.memory], a maximal sequence of adjacent non-zero-length bit-fields forms a SINGLE memory location. Updating p.a compiles to a non-atomic read-modify-write of the enclosing word, racing directly with Thread 2 unless separated by an unnamed zero-width bit-field (`unsigned : 0;`).

### Question 5 [standardese] ([atomics.types.operations])

In C++17 and later, which `memory_order` values are forbidden as the `failure` ordering argument to `std::atomic::compare_exchange_weak(expected, desired, success, failure)`?

A. memory_order::relaxed and memory_order::consume
B. memory_order::seq_cst when success is memory_order::relaxed
C. memory_order::release and memory_order::acq_rel
D. Only memory_order::seq_cst

**Answer (C):** memory_order::release and memory_order::acq_rel

**Why:** Failure does not write to the atomic object, so [atomics.types.operations] forbids passing memory_order::release or memory_order::acq_rel as the failure order. Note that C++17 (P0418R2) removed the older restriction banning failure order from being stronger than success order.

### Question 6 [standardese] ([atomics.fences])

How do `std::atomic_thread_fence(release)` and `std::atomic_thread_fence(acquire)` synchronize two threads communicating through a `relaxed` atomic `flag`?

```cpp
// T1: data = 42; atomic_thread_fence(release); flag.store(1, relaxed);
// T2: if (flag.load(relaxed) == 1) { atomic_thread_fence(acquire); use(data); }
```

A. A release fence followed by an atomic store X synchronizes with an atomic load reading X followed by an acquire fence
B. Fences only synchronize when paired with seq_cst stores
C. The release fence must appear AFTER flag.store(1, relaxed) on T1
D. Fences cannot establish happens-before edges across relaxed atomics

**Answer (A):** A release fence followed by an atomic store X synchronizes with an atomic load reading X followed by an acquire fence

**Why:** Under [atomics.fences], a release fence A followed by an atomic store X that is read by an atomic load Y followed by an acquire fence B causes fence A to synchronize-with fence B—establishing happens-before from data = 42 to use(data).
