# Shared memory consistency from scratch, part 1: causality

The first part of a series on allthoughts.me by an author signing as Alloth. The claim behind it is that memory models are confusing because they are poorly understood, even by experts, and not because they are intrinsically hard. The method is to design a virtual multiprocessor that guarantees less ordering than any real architecture, add atomic instructions one at a time until each classic anomaly is ruled out, and use the result to read the C++ memory model critically. Part 1 covers causality; read-modify-write operations, fences and compiler mappings are promised for Part 2.

The post is long, dense, and opinionated. Several of its sharper claims about C++20 are the author's own and, by their account, not yet raised anywhere else. They are marked as such below.

## The machine

A memory model defines how updates to shared data may be observed. In hardware that means coherence for a single location (a cache line, the unit a cache-coherence protocol arbitrates) and consistency across locations. The author treats coherence as a striped reader-writer lock over RAM, then asks the question they consider most important about any architecture: when is a write complete, and may other processors read it before then?

The answer defines [[write-atomicity]]. x86, RISC-V, ARMv8-A and SPARC are write-atomic (MCA) or write-atomic except for a processor's own writes (oMCA); IBM Power, ARMv7, Itanium and NVIDIA's PTX GPU are not (nMCA). Write atomicity turns every externally visible reordering into a processor-local one. Without it, the reader carries the burden of restoring order.

The virtual machine drops it on purpose. Processors may serve reads of a write before every copy is invalidated (early reads). Invalidations are acknowledged into an invalidation buffer and may be applied out of order. Hardware threads share one store buffer and forward from it. The interconnect gives no delivery-order guarantee, and speculative loads may ignore branch dependencies. The stated goal is to build "the least programmer friendly architecture" so every subtlety of the C++11 model has room to appear.

## The instructions

Each new instruction suffix exists to rule out one anomaly:

| Suffix | Name | What it guarantees |
|---|---|---|
| `.rcv` / `.snd` | receive / send | one-way read and write barriers; enough for a single-producer single-consumer ring buffer |
| `.acq` / `.rel` | acquire / release | lock semantics; nothing moves out of the critical section ("Roach Motel") |
| `.rlx` | relaxed | atomic access with no ordering guarantees |
| `.cmt` | commit | wait until causally prior writes are globally visible |
| `.rec` | reconcile | a load that also waits for the observed write to be globally visible |
| `.sqc` | sequentially consistent | the C++ `memory_order_seq_cst` equivalent |
| `.cns` / `.vfy` / `.prp` | consume / verify / prepare | pointer-publish (RCU-style), seqlock read validation, seqlock single-writer start |

Mutual exclusion on this machine can only protect one cache line of atomic state, which is why real architectures limit atomic types to a few bytes. An aside on x86 explains that a `LOCK`-prefixed instruction spanning two cache lines triggers a bus-wide lock (the Linux "split lock" detector exists because userspace can abuse this), and that without the prefix such an access simply tears.

## The litmus tests

The core of the article is a walk through the anomalies from the memory-model literature, renamed by the author to make the structure visible.

Write-to-read causality (WRC, from Adve and Boehm's *Foundations of the C++ Concurrency Memory Model*): one processor reads data early, then releases a flag; another acquires the flag and reads stale data. Ruling it out needs external cumulativity (A-cumulativity in the Power and ARM manuals). The author calls this D-WRC, and the indirect variant I-WRC, which needs internal (B-) cumulativity.

Read-to-write causality (RWC) is the one the author says trips up experienced developers, and C++11 deliberately allows it. Mapped onto a Chase-Lev work-stealing deque it is a duplicated pop: the single producer and a consumer both see one item left and both take it. Fixing it needs a commit load on the producer and a reconcile load on the consumer. The W+RWC variant appears in delegated hazard-pointer reclamation (the neighbour of [[epoch-based-reclamation]]), where a collector frees memory a reader is still using.

Further variants add coherence ordering (WRW+WR, Z6.3), independent reads from independent writes (IRIW), and store-to-load forwarding (2+2W and SB+rfis, renamed SLF2 and SLF1). Each is cross-referenced to the Power litmus results from Cambridge's herdtools work, including which outcomes were actually observed on Power 6, 7 and 8.

## Sequential consistency as an acyclic graph

The author's formal core: an execution is sequentially consistent when the graph of modification-order (mo), reads-from (rf), reads-before (rb, their name for the literature's "from-reads") and program-order (sb) edges is acyclic. A partial order is enough, since any DAG topologically sorts into a total one. Write atomicity plus program order is sufficient, and the proof reduces any execution cycle to a cycle between writes using the pattern

```text
W(x); mo | (rf?; sb; rb?); W(y)
```

which the author calls causal read projection.

Two implementation shapes can provide it: propagate-then-commit, which this machine uses, and commit-then-propagate with a central arbiter. On chips that only offer a single `serialize` barrier, SC loads and stores can be mapped with the barrier before the access (leading-sync) or after it (trailing-sync). ARMv7's recommended C++11 mapping uses `dmb ish` three times per store; Power's mapping uses the leading form.

The author thinks SC+DRF (sequential consistency in the absence of data races) is a good model for a language that wants a small set of atomics, and says this is plausibly why Java and Golang adopted it. The trouble starts when weaker atomics coexist with SC ones.

## The case against C++

The C++11 model, which C, Rust, Odin, LLVM-based languages and (indirectly) Golang inherit, does not require write atomicity. It took until 2016 (Manerkar et al.) and 2017 (Lahav et al., *Repairing Sequential Consistency in C/C++11*) for researchers to show that trailing-sync mappings for Power and ARMv7 violate it. C++20 patched the specification, and the patch made some instruction selection on x86 badly inefficient (LWG issue 3941), which drew Hans-J. Boehm's comment that the audience for that part of the standard is "nearly empty" and that implementers rely on expert mappings rather than standardese.

The author's diagnosis is that C++ formulates release-acquire through transitive "happens-before" rules instead of saying an acquire only guarantees visibility of writes causally prior to the release it read. As evidence they construct an I-RWC execution that a machine placing serialization points dynamically would allow and C++20 forbids, and state that to their knowledge this has not been raised before. That, and the claim that C++'s missing commit and reconcile operations make SC a blunt tool for advanced algorithms, are arguments to weigh rather than settled results.

## Same-location ordering

The last section answers why relaxed atomics exist at all if coherence is a reader-writer lock. Two loads of the same location through different pointers can complete out of order when the pointer lines fill at different times, and architectures without memory ordering buffers do not prevent it; Itanium's manual lists read-after-write, write-after-read and write-after-write dependencies but not read-after-read. Hardware bugs do the same thing: the 2013 *Herding Cats* paper found load-load hazards on Cortex-A9 systems, which ARM acknowledged as erratum 761319, with a workaround of a `DMB` after every volatile read. GCC's Itanium backend and Intel's icc both treat `volatile` as a relaxed atomic in practice, whatever the standard says.

The article ends with a disclosure that GPT-5.6 Sol was used only to find and summarize references; ideas, writing and diagrams are the author's.

## Related

The cache-line coherence traffic this builds on is what [[false-sharing-alignment-128]] measures from the software side. [[threadsanitizer-limits]] shows the software-detection counterpart: C11's data-race definition borrows the same "happens before" language, and TSan's vector clocks are one way of computing it. [[message-passing-vs-shared-memory]] frames the higher-level debate, and [[art-of-multiprocessor-programming]] is the textbook on the shared-memory algorithms the litmus tests model. [[itanium-too-few-parameters]] is another look at how Itanium enforced correctness in hardware that other architectures left to software. [[cobaltc]]'s specification uses the same ordering vocabulary for its threads, defining happens-before as the transitive closure of sequenced-before and synchronizes-with, the kind of transitive rule this post faults in C++, and leaves each atomic ordering mode to document its own guarantees.