Systems and hardwareDive 04 of 06
Atomics, from a log queue to a store buffer
Two threads write, then read. Both can read the old value. Follow a log record through a lock-free queue to understand the language contract, compiler instructions, store buffers, and the cache lines moving between cores.
- Levels
- 8
- Reading
- 42 min
- Depth
- Idea to Silicon
- Published
A write has a waiting room
Both wrote 1.
Both can read 0.
Each core writes its own flag, then reads the other flag. Step the instructions: a write can wait in a private buffer while the next load runs.
Core 0
x = 1; r0 = y;Read result —
Core 1
y = 1; r1 = x;Read result —
Start with both flags at 0. Neither core has executed yet.
The log record that arrived too soon
A worker thread produces log records. A writer thread sends them to a file. You want the worker to get on with its job instead of waiting for the disk, so you put a small queue between them. The worker fills a slot and advances head; the writer notices that the queue is non-empty, copies the record out, and advances tail. Only one thread writes each index. The records themselves are ordinary structs.
This is a A fixed array whose logical end wraps back to its beginning; two indices mark the produced and consumed boundaries.. Use eight slots for the first sketch. head names the next position the worker will fill, and tail names the next position the writer will read. Equal indices mean empty. Advancing head onto tail would mean full, so leave one slot unused. Seven records fit in this eight-slot ring.
The following version is broken when its methods run on different threads. It looks plausible because every assignment is short, and each index has only one writer. Those facts do not establish any communication rule between threads.
#include <cstddef>
struct BrokenQueue {
int slots[8]{};
std::size_t head = 0;
std::size_t tail = 0;
bool push(int record) {
auto next = (head + 1) % 8;
if (next == tail) return false;
slots[head] = record;
head = next;
return true;
}
bool pop(int& record) {
if (tail == head) return false;
record = slots[tail];
tail = (tail + 1) % 8;
return true;
}
};The worker's write to head conflicts with the writer's read of head. The reverse conflict exists on tail. In C++, conflicting accesses in different threads, at least one non-atomic, need an ordering relation called happens-before. Without it, the execution has a Conflicting potentially concurrent accesses, at least one non-atomic, with neither happening before the other. and undefined behavior. The compiler is allowed to optimize under the assumption that your program obeys this rule. The fact that an aligned index fits in one machine instruction does not repair the language-level race. See the formal definition in [intro.races].
There is a second problem hiding behind those indices. The worker must finish writing the record before the writer uses it. Later, the writer must finish reading the record before the worker overwrites its slot on the next lap. These are two ownership transfers, in opposite directions. Making the index accesses indivisible only solves part of the job.
It helps to separate three questions. Can an access tear into pieces? In what order may this thread's operations become observable? Which earlier writes does another thread become entitled to rely on? Atomicity addresses the first. Memory ordering and synchronization answer the others. An atomic flag is useful precisely because it can connect an ordinary block of data to a carefully defined handoff.
The intuitive reference point is Executions behave like one total interleaving of all threads' operations that preserves each thread's program order., or SC. Imagine an impartial clerk taking the next operation from one thread at a time and updating a single shared notebook. Each thread's entries stay in order. Every read gets the most recent preceding write in that notebook. The clerk can choose many schedules, but no schedule lets both reads in the hero return zero.
Why both-zero cannot fit into one sequential order
Core 0 order
Write x = 1 before reading yProgram order keeps the first store before the first load.
Read y = 0
Read y before write y = 1In SC, a read of the initial value must precede the only later write.
Core 1 order
Write y = 1 before reading xProgram order keeps the second store before the second load.
Read x = 0
Read x before write x = 1The last edge returns to the start: a cycle, so no total order exists.
Hardware makes a different bargain. A core can finish an instruction locally while the write waits for permission to update a cache line. A later load from another address may complete first. The compiler can also transform your source before the CPU sees it. You therefore need both a language contract and a hardware implementation of that contract. The queue gives us a concrete way to follow those promises down.
You could use a mutex or a channel, and often should. A bounded SPSC queue is useful when one producer and one consumer have stable roles and a small hot path matters. It gives up generality: a second producer cannot simply call the same method. The Go concurrency dive's channel machinery shows what a runtime adds to support more participants, blocking, and wakeups.
A shared variable needs a communication contract. One writer per variable prevents competing writes, but it does not order the other thread's reads.
Two handoffs, two ordering edges
Start by turning head and tail into std::atomic<std::size_t>. Each atomic object has a total The total order of modifications to one atomic object, shared by all observers of that object. containing its stores and read-modify-write operations. Loads observe those modifications subject to the coherence rules. There is still no automatic combined order of head, tail, and every record field.
An atomic operation takes a memory-order argument. The default is memory_order_seq_cst, a useful starting point. To make the queue's proof explicit, use release when publishing an index and acquire when observing the index owned by the other thread. Use relaxed to read an index owned by the current thread. There are no competing writers to that index, and the peer never advances it for us.
An ordering operation that can publish preceding evaluations to an acquiring observer of its value. is the sending side of a handoff. An ordering operation that can make subsequent evaluations follow a release operation whose value it observes. is the receiving side. The crucial condition is that the acquire reads from the release store, or an applicable release sequence. A load that reads the old initial zero has not acquired a later store of one. Placing the two words in your source is insufficient unless the communication actually connects them.
When a matching acquire observes a release, the release synchronizes with the acquire. Combine that edge with each thread's sequenced-before edges and you obtain happens-before. In our queue: writing the slot is sequenced before releasing head; releasing head synchronizes with the writer's acquiring head load; that load is sequenced before reading the slot. The entire path orders the ordinary payload accesses. The payload does not need to become atomic field by field.
head.store(1, release)tail.store(1, release)Worker owns the slot. Writer waits for head.
Release head synchronizes with acquire head.
Writer owns the published record. Worker cannot overwrite it.
Release tail synchronizes with acquire tail. Ownership returns.
- Both indices start at 0. The queue is empty, so the worker can fill slot 0.
- The worker finishes writing the record before it publishes head = 1.
- The writer's acquire load reads that release store. The record is now safe to read.
- The writer copies the record out before it releases tail = 1.
- The worker acquires the returned tail before reusing the slot on a later lap.
The second edge is just as necessary. Reading the record precedes releasing tail. The worker acquires tail before it treats that slot as available again. Now the old read happens before the next overwrite. If you weaken only tail's ordering, publication may remain correct while reuse becomes a race. That bug often survives a short test because the ring has not wrapped, or the writer finishes copying before the worker catches it.
Experiment with the four cross-thread operations below. The lab follows a successful publication and return. An acquire that still sees an older boundary can report empty or full conservatively; it never grants permission to read an unpublished slot. Missing synchronization on an ordinary payload means undefined behavior, so the lab reports a race instead of inventing a list of C++ results.
Plain shared indices race. The C++ program has undefined behavior.
Slot 0 is free. Step to write log record 42.
One producer, one consumer; non-atomic payload. A successful receive observes the published index; reuse observes the returned index.
| Order | Useful guarantee | Queue role |
|---|---|---|
| relaxed | Atomic access and per-object coherence; no publication of unrelated memory | Read your own index |
| acquire | Matching release happens before following operations | Observe the peer's boundary |
| release | Preceding operations can be published to a matching acquire | Publish your boundary |
| acq_rel | Acquire read half and release write half | Read-modify-write operations; unnecessary here |
| seq_cst | Acquire/release semantics plus participation in the SC order | A correct, stronger starting point |
Acquire is not a valid order for a plain store; release is not a valid order for a plain load. acq_rel belongs on read-modify-write operations, such as exchanging a state while observing the old state. Compare-exchange has separate success and failure orders because failure performs a load without a store. Choosing acquire for failure is a common way to inspect the value that defeated your attempted update.
Sequentially consistent operations participate in a single total order with the consistency constraints specified by the language. If every shared access in a litmus is SC atomic, you recover the clerk's model. Mixing SC operations with weaker operations needs a more careful argument; the SC order does not upgrade every relaxed operation around it. For this queue, making all four cross-thread operations SC works, but the ownership proof needs only release and acquire. The rules are in [atomics.order].
C11 provides the same core vocabulary through _Atomic and atomic_load_explicit/atomic_store_explicit. Its original specification is in N1570 §5.1.2.4 and §7.17. C++20 changed release-sequence details from the original C++11 formulation; our queue uses direct release stores observed by acquire loads, so it needs none of those subtleties. A release sequence can matter when a chain of read-modify-write operations carries a publication across several threads.
memory_order_consume attempted a narrower, dependency-based contract, useful when a pointer load feeds later addresses. Compiler practice generally strengthened it to acquire. The C++26 direction deprecates consume and removes its distinct dependency-order semantics; use acquire for new publication code. The design history is documented in P3475R2, Defang and deprecate memory_order::consume. Consume in the language and RCpc acquire instructions in Arm are separate subjects.
Two C++20 repairs that matter when mixing orders
Before C++20, a release sequence could include later plain atomic stores by the releasing thread. C++20 narrowed the continuation to read-modify-write operations. Here an acquire that reads flag = 2 from publish_store no longer acquires the earlier release: reading data = 0 is permitted. The payload is atomic so this remains a defined example. Replacing that last store with fetch_add, as in publish_rmw, preserves the release sequence and guarantees data = 42. A fresh release store of 2 would also publish the data. This change comes from P0982R1; our queue observes release stores directly.
#include <atomic>
#include <cassert>
#include <iostream>
#include <thread>
std::atomic<int> data{0};
std::atomic<int> flag{0};
void publish_store() {
data.store(42, std::memory_order_relaxed);
flag.store(1, std::memory_order_release);
flag.store(2, std::memory_order_relaxed);
}
void publish_rmw() {
data.store(42, std::memory_order_relaxed);
flag.store(1, std::memory_order_release);
flag.fetch_add(1, std::memory_order_relaxed);
}
int receive() {
while (flag.load(std::memory_order_acquire) != 2) {
std::this_thread::yield();
}
return data.load(std::memory_order_relaxed);
}C++20 also repaired mixed-order SC constraints with P0668R5. Its Z6.U example asks whether b = 1, c = 3, a = 0 can occur:
#include <atomic>
#include <cassert>
#include <functional>
#include <iostream>
#include <thread>
std::atomic<int> x{0};
std::atomic<int> y{0};
void first() {
x.store(1, std::memory_order_seq_cst);
y.store(1, std::memory_order_release);
}
void second(int& b, int& c) {
b = y.fetch_add(1, std::memory_order_seq_cst);
c = y.load(std::memory_order_relaxed);
}
void third(int& a) {
y.store(3, std::memory_order_seq_cst);
a = x.load(std::memory_order_seq_cst);
}Name the SC events A = store x, B = fetch-add y, C = store y, D = load x. The old rules required A before B via happens-before, B before C via coherence, C before D within thread 3, and D before A to read x = 0: a cycle. P0668 ties SC order to strongly happens-before. Here the release-to-SC-acquire path gives A happens-before B without A strongly happens-before B. SC order B, C, D, A therefore permits this outcome, accommodating existing weak-architecture mappings.
P0668 also strengthened SC-fence constraints: relaxed atomic accesses separated by SC fences can enforce SC behavior. Happens-before still governs ordinary-data race freedom. The mixed-order and RMW examples here extend beyond the explorer's load/store subset.
The same problem in other languages
Go's memory model, revised June 6, 2022, gives sync/atomic operations a sequentially consistent order. You do not choose relaxed or release on atomic.Int32. The following store-buffer test uses atomic flags and ordinary result variables. Waiting for both goroutines also synchronizes the final reads of those results. The both-zero result is forbidden by the atomic SC contract, not merely unlikely in a thousand trials. See Go's atomic-values rule.
package main
import (
"fmt"
"sync"
"sync/atomic"
)
func main() {
for trial := 0; trial < 1000; trial++ {
var x, y atomic.Int32
var r0, r1 int32
var done sync.WaitGroup
done.Add(2)
go func() {
defer done.Done()
x.Store(1)
r0 = y.Load()
}()
go func() {
defer done.Done()
y.Store(1)
r1 = x.Load()
}()
done.Wait()
if r0 == 0 && r1 == 0 {
panic("forbidden sequentially consistent outcome")
}
}
fmt.Println("1000 SC trials; no forbidden outcome")
}Rust exposes Relaxed, Acquire, Release, AcqRel, and SeqCst; its Ordering documentation relates these to C++20. Shared mutable payload storage in a custom ring also requires a sound interior-mutability and aliasing design. Correct hardware ordering cannot rescue an invalid reference. Java's volatile fields provide synchronization semantics, while VarHandle offers explicit plain, opaque, acquire/release, and volatile access modes. These are language contracts; translating the spelling of volatile between Java and C++ changes the meaning drastically.
The data can stay ordinary when atomic indices transfer exclusive access to it. The proof is a path of happens-before edges, repeated on every lap.
Small programs that expose big promises
A whole queue has loops, branches, wraparound, and many records. To expose one ordering rule, strip almost all of that away. A A small concurrent program together with a final observation that distinguishes memory models. asks whether a tiny observation is permitted. Initially the shared locations hold zero. Threads execute a handful of operations, and we ask which register values can remain at the end. A forbidden result is a specification statement; failing to observe a result on your laptop proves very little.
SB, store buffering, is the hero: each thread stores one flag and reads the other. Both-zero is forbidden by SC, allowed by x86-TSO, and allowed by ordinary Arm loads and stores. MP, message passing, writes data then a flag, and reads the flag then data. Seeing the new flag with old data is forbidden under TSO's ordinary cacheable-memory rules but allowed on Arm without ordering. C++ relaxed atomics permit that MP result too. Returning to ordinary queue records makes missing publication a data race rather than an atomic old-data outcome.
LB, load buffering, reverses SB: each thread reads before making an unconditional store. The outcome where both reads obtain one cannot fit any SC history and is forbidden by TSO. Arm's independent loads and stores allow it. There is no value conjured from nowhere: the two stores write constants regardless of what the reads return. Introducing data or control dependencies changes the test, and the dependency-free explorer below deliberately excludes them.
Rx reads x; Wx1 writes 1; F is MFENCE / DMB ISH. Initially x = y = z = 0. Custom programs: ≤8 operations, ≤4 threads, ≤2 writes per location. Language modes use atomics throughout and exclude F.
SC: 3 allowed outcomes from 4 candidates. Select an outcome to inspect its execution.
Select an outcome. Each candidate assigns a source write to every read and a coherence order to every location.
0: T0 Wx1 · 1: T0 Ry (r0) 2: T1 Wy1 · 3: T1 Rx (r1) 4: initial x=0 · 5: initial y=0
Event IDs follow program order across threads. Initial writes are the last IDs.
Arm subset: aligned, single-copy atomic ordinary loads/stores and DMB ISH, normal inner-shareable memory; no dependencies, RMWs, mixed sizes, devices or RCpc. Model pinned to herdtools7 7.56 aarch64.cat. Counts are possibilities, not probabilities.
What the enumerator actually checks
The explorer gives each event an ID, picks a source write for each load, and tries both possible orders when two threads write the same location. Initial writes always come first. It constructs three relations: reads-from (rf), coherence (co), and from-read (fr). If a read takes its value from write A, and write B follows A in coherence order, that read has a from-read edge to B. That edge records the fact that the read has not yet observed B.
SC rejects cycles in program order plus those communication edges. The TSO check preserves load-load, load-store and store-store order, while allowing a store to be bypassed by a later load of another location. It includes external reads-from and all coherence/from-read edges, plus a separate same-location consistency check. Internal reads can forward from a pending local store. Full fences restore store-to-load order. This is the axiomatic presentation corresponding to the store-buffer machine in Sewell et al., x86-TSO.
The Arm check uses the normal-memory, single-copy-event subset of herdtools7 7.56's aarch64.cat: internal visibility checks per-location order; external visibility requires acyclic observed-before. External communication, local write successors and full barriers contribute edges. Dependency and RMW relations are empty because this input language has neither. Arm mode's R and W are ordinary machine accesses, not implicit LDAR and STLR. F means DMB ISH in a common inner-shareable domain.
The language modes give every load and store the same class of ordering: all relaxed; all stores release and loads acquire; or all SC. They check atomic coherence and happens-before for unconditional constant stores. They exclude fences, RMWs, release sequences, consume, mixed ordering classes, ordinary data and value-dependent computation. This is a bounded language-model slice, not a checker for arbitrary C++. Within it, release/acquire reads-from edges can create synchronization cycles that relaxed permits.
IRIW means independent reads of independent writes. Two writers set different locations. Two readers inspect them in opposite orders. Both readers seeing their first flag set and second flag unset is allowed by unordered Arm loads and forbidden by TSO. This does not show that Arm lets a write become visible to one remote core and remain hidden from another ordered observer: the readers themselves lack order. Put full barriers between the reads and the weak IRIW outcome disappears.
WRC, write-read causality, relays a flag through a middle thread. The middle thread reads x then writes y; a third reads y then x. It exposes whether the relay and final observations carry order. 2+2W has only stores, two in each thread, and asks about the final values. Opposite final winners on the two locations are possible when cross-location store order is relaxed. For that preset the explorer shows final memory rather than empty register tuples. Barriers restore the missing edges.
| Test and observation | SC | TSO | Armv8 |
|---|---|---|---|
| SB: both reads 0 | Forbidden | Allowed | Allowed |
| MP: flag 1, data 0 | Forbidden | Forbidden | Allowed |
| LB: both reads 1 | Forbidden | Forbidden | Allowed |
| IRIW: 1,0 / 1,0 | Forbidden | Forbidden | Allowed |
| 2+2W: x = 1, y = 1 | Forbidden | Forbidden | Allowed |
| WRC: 1 / 1,0 | Forbidden | Forbidden | Allowed |
These expectations are regression tests for the implementation, alongside same-address forwarding and fenced variants. The Arm model and its relation to multicopy atomicity are developed in Pulte et al., POPL 2018, whose supplementary material includes model results. Enumeration here is exhaustive for the entered bounded program, and runs in short browser slices. An allowed candidate counts once as a possible graph; the count says nothing about how frequently a real processor will produce its result.
What the compiler must preserve
The correct queue is short enough to show in full. The worker calls push, the writer calls pop, and each owns the corresponding local progress variable. This version uses 1,024 slots and reserves one, giving a capacity of 1,023 records. A failed method returns immediately. Retrying or sleeping is the caller's policy; the queue itself does not wait for disk I/O or invoke an operating-system lock.
#include <array>
#include <atomic>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <thread>
struct Record {
std::uint64_t sequence = 0;
};
class LogQueue {
static constexpr std::size_t size = 1024;
std::array<Record, size> slots_{};
std::atomic<std::size_t> head_{0};
std::atomic<std::size_t> tail_{0};
public:
bool push(Record record) {
const auto head = head_.load(std::memory_order_relaxed);
const auto next = (head + 1) % size;
if (next == tail_.load(std::memory_order_acquire)) return false;
slots_[head] = record;
head_.store(next, std::memory_order_release);
return true;
}
bool pop(Record& record) {
const auto tail = tail_.load(std::memory_order_relaxed);
if (tail == head_.load(std::memory_order_acquire)) return false;
record = slots_[tail];
tail_.store((tail + 1) % size, std::memory_order_release);
return true;
}
};The object must be constructed before either thread starts using it and destroyed after both finish. The test driver launches two threads, sends 100,000 numbered records through repeated wraparound, checks their order, and joins them. It passed with GCC and Clang in this checkout. That is a useful implementation check; the proof that ordinary slot accesses do not race comes from the two release/acquire paths, not the test's scheduling luck.
Each successful push writes one whole record then releases the new head. The pop's acquire of head authorizes reading the occupied range. Each successful pop finishes copying before releasing tail; the push's acquire of tail authorizes writing the freed range. A temporarily stale boundary can cause a false report of empty or full. It cannot authorize crossing the boundary in the unsafe direction. Per-object coherence constrains successive observations, and one reserved slot prevents the producer from overtaking the consumer.
The compiler is responsible for preserving those language guarantees in every target instruction sequence it emits. It may still keep arithmetic in registers, unroll loops, merge ordinary writes where allowed, and eliminate dead stores. Acquire and release constrain observable movement across the publication points. They are not requests to turn the optimizer off for a function. On a racy plain-variable spin loop, by contrast, the optimizer may find no valid concurrent write it must account for and hoist or remove work you expected to repeat.
Look at the instructions, not the spelling
The assembly browser uses a small C file with GCC-compatible __atomic builtins on aligned int objects. Those builtins expose the same memory-order choices without requiring a target C++ standard library during cross-compilation. The output was generated locally by Ubuntu Clang 21.1.8 at -O2. The complete source and exact command appear with the listing. Choose a target and operation. Function labels and instruction operands come from the compiler output; only directives and comment-only lines were removed.
int load_relaxed(int *p) {
return __atomic_load_n(p, __ATOMIC_RELAXED);
}
int load_acquire(int *p) {
return __atomic_load_n(p, __ATOMIC_ACQUIRE);
}
int load_sc(int *p) {
return __atomic_load_n(p, __ATOMIC_SEQ_CST);
}
void store_relaxed(int *p, int v) {
__atomic_store_n(p, v, __ATOMIC_RELAXED);
}
void store_release(int *p, int v) {
__atomic_store_n(p, v, __ATOMIC_RELEASE);
}
void store_sc(int *p, int v) {
__atomic_store_n(p, v, __ATOMIC_SEQ_CST);
}
int add_acq_rel(int *p, int v) {
return __atomic_fetch_add(p, v, __ATOMIC_ACQ_REL);
}
int cas_acq_rel(int *p, int *expected, int desired) {
return __atomic_compare_exchange_n(
p, expected, desired, 0, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE);
}
void fence_sc(void) {
__atomic_thread_fence(__ATOMIC_SEQ_CST);
}Ubuntu Clang 21.1.8 (6ubuntu1) · run in src/dives/atomics
clang --target=x86_64-pc-linux-gnu -O2 -S -masm=intel codegen.c -o x86-64.sload_relaxed: # @load_relaxed
mov eax, dword ptr [rdi]
retx86-64: load_relaxed. Generated with Ubuntu Clang 21.1.8 at -O2.
Actual compiler output from codegen.c, using GCC-compatible __atomic builtins on aligned int objects. Directives and comment-only lines removed. Arm baseline: Armv8-A; RCpc baseline: Armv8.3-A + RCpc (including LSE). Cross-compiled Arm assembly; not executed on Arm.
On x86-64, relaxed, acquire and SC loads are ordinary mov instructions for this aligned 32-bit case. Relaxed and release stores are also mov. This does not make their C++ orders interchangeable. The compiler gives the operations different movement constraints, and x86's existing load/load, load/store and store/store ordering supplies the hardware edges without extra instructions. A release operation can therefore be cheap while still being indispensable in the source.
The SC store is different: Clang emits xchg with a memory operand, whose locking is implicit. An alternative correct mapping is a store followed by mfence. For the SC fence in this file Clang emits mfence. Fetch-add with a returned old value uses lock xadd. If the old value is unused, a compiler may choose another locked arithmetic instruction. Instruction selection depends on the whole expression, alignment, operand size, target and compiler version.
Baseline AArch64 uses ldr/str for relaxed access, ldar for acquire and SC loads, and stlr for release and SC stores. It uses dmb ish for the SC fence. The baseline fetch-add retries a load-exclusive/store-exclusive sequence: ldaxr acquires, stlxr releases, and the status result tells the loop whether it succeeded. This is an instruction-level retry loop even though the source operation looks like one function call.
With LSE enabled, fetch-add becomes ldaddal, and compare-exchange uses casal. The suffix carries acquire and release semantics. LSE lets the architecture describe a single atomic instruction instead of a visible exclusive loop; the implementation still has to obtain ownership of the line. In the Armv8.3-A RCpc target, Clang emits ldapr for the acquire load but keeps ldar for the SC load. The distinction matters when combining a preceding release store with a later acquire. Our plain-load litmus model does not model RCpc instructions.
The established mapping alternatives are catalogued in the C/C++11 processor mappings. The assembly here is an observed compiler choice, not a promise that a future compiler must use the same mnemonic. The C++ queue's source is portable across those choices because it specifies the required relationships rather than a fixed instruction sequence.
Fences and compiler barriers
atomic_thread_fence can express ordering separately from a particular atomic access. For example, a release fence before a relaxed store can publish preceding data to a suitable acquire observer. An acquire fence after a relaxed load can receive a suitable release publication. Both need the atomic communication connecting the threads. Two unrelated fences do not manufacture a synchronizes-with edge. The exact fence-to-atomic and fence-to-fence rules appear in [atomics.fences]. Keeping the ordering on the queue's index operations makes the proof easier to inspect.
A compiler barrier constrains compiler transformations without necessarily emitting a CPU barrier. GCC-style inline assembly with a memory clobber is one tool in low-level platform code, but it does not turn plain racy C++ accesses into portable synchronization. atomic_signal_fence has a same-thread signal-handler role. A CPU fence constrains machine visibility or execution according to the ISA. Sometimes the compiler needs both effects; sometimes the target already supplies the hardware part.
Two source orderings can compile to the same instruction and still mean different things. The compiler's freedom is part of the contract.
A store can retire before it is visible
The queue's store to head may retire long before a remote core can read the new value. Retirement means that the instruction is committed in this thread's architectural history. Global visibility means that other observers can obtain its value under the machine's memory model. Between those events sits the store buffer and the work required to obtain a writable cache line.
A core executes many operations before earlier ones finish. Stores need addresses and data, and their effects must not escape while the instruction could still be rolled back after a fault or a wrong branch prediction. The processor tracks them in queues. After retirement, a store can remain pending while a cache miss, ownership request or older store prevents it from draining. Execution resources are then free to work on younger instructions.
A store has two different finishing points
Execute
Compute address and dataThe store enters the store queue; loads check older stores for dependencies.
Retire
Commit the instruction locallyOnce safe to retire, the store can remain buffered while younger instructions continue.
Acquire line
Request writable ownershipThe cache controller obtains permission and waits for required invalidation acknowledgements.
Drain
Make the store globally observableThe buffered value joins coherent memory order. A later fence may have waited for this point.
In the x86-TSO abstract machine, each thread has a FIFO store buffer. A store appends an address/value pair. The oldest buffered store may drain into shared memory. A load checks its own buffer for the youngest pending store to the same address; if present it forwards that value, otherwise it reads shared memory. This A load obtains data from an older pending store in the same core instead of waiting for that store to reach the cache. explains how a thread sees its own writes before other threads do.
SB needs no broken cache protocol. Core 0 buffers x = 1; core 1 buffers y = 1. Core 0's load of y has no matching local store, so it reads shared y = 0. Core 1 similarly reads x = 0. Then the stores drain, leaving x = y = 1 while both result registers remain zero. The loads never read each other's private buffers. Reset the hero and enable fences: each store must drain before its thread crosses the fence to its load, removing that execution.
On x86, this permission for a later load to bypass an older store to another location is the important relaxation for ordinary write-back memory. Loads are not allowed arbitrary architectural reordering just because the core executes them out of order internally. The implementation can speculate, but its externally observable result must still satisfy the ISA. Intel documents the permitted and forbidden histories in the SDM, Volume 3A, §11.2 in revision 093 (September 2026; §8.2 or §10.2 in earlier editions).
The physical load/store machinery is more complicated than the abstract FIFO. A load may run before the address of an older store is known. If the machine later discovers an alias, it must repair the speculation, replaying work. A snoop can also reveal that a speculative load's placement would violate required ordering. Implementations can squash and restart instructions; Intel performance counters describe some such recoveries as memory-ordering machine clears. The repair mechanism and its cost vary across microarchitectures. The model describes the accepted final histories, not every intermediate electrical action.
Invalidation queues are another implementation technique: a cache controller can queue coherence work instead of making every incoming request stop the core immediately. A queued request is not a license to violate the architectural model. Required acknowledgements, load replay and ordering rules must keep the final observations legal. Treating “flush the invalidation queue” as the definition of acquire is too specific to one imagined machine. Acquire is a promise about order; the implementation chooses how to meet it.
Arm ordinary loads and stores leave more cross-location edges unconstrained. MP can expose store-store or load-load relaxation; LB can expose load-store relaxation. DMB instructions and acquire/release accesses restore selected edges. There is no need to assume that every allowed behavior occurs on every implementation. A particular Arm core can be stronger than the architecture. Testing on that core does not license weaker source code elsewhere.
Modern Armv8's revised model is other-multicopy-atomic: a writer can observe its own pending write early, but propagation to other observers is constrained coherently. POWER permits behaviors requiring a different propagation argument. Pulte and colleagues explain the Arm revision and its formal models in their 2018 paper and supplementary material. Copying an old ARMv7 or POWER mental model directly onto current Armv8 can lead you to predict results that its ordered observers cannot produce.
Our queue does not need each store to become visible immediately. It needs that, once the writer observes a released head, the corresponding record write precedes its reads. Delayed publication affects progress and latency. Reordered publication without a synchronization contract affects correctness. Those are different problems, and the former often buys the performance that makes the queue attractive.
One line, one writer at a time
A buffered store eventually needs somewhere to go. The core's private cache can hold a copy of the line, but writing requires permission. A A protocol that ensures writes to each cache line are observed consistently across cached copies. tracks that permission and the location of the freshest data. Memory consistency specifies which combinations of operations across locations the program can observe. Coherence provides the per-location foundation; it does not by itself make all operations sequentially consistent.
The familiar MESI states describe one line in one cache. Modified means this cache has the writable dirty copy. Exclusive means it has the sole clean cached copy, so a local write can silently make it Modified. Shared means several caches may hold clean readable copies; writing requires invalidating the others. Invalid means this cache has no usable copy. The state attaches to a cache line, not to the variable named by the instruction.
In the atomic-bus teaching model below, a read miss sends BusRd and obtains data. If no other cache holds the line, the new copy is Exclusive. If another does, the copies become Shared. A read of a Modified peer's line requires the dirty owner to supply the current data and make memory clean in this MESI model. A writer with no copy sends BusRdX; a writer with a Shared copy sends BusUpgr. Other copies invalidate before the write obtains sole ownership.
Line 0 · head + tail
Line 1 · unused
- Accesses
- 0 / 16
- Logical messages
- 0
- Peer invalidations
- 0
Both caches start invalid. Next: core 0 writes head.
- No accesses yet.
Atomic bus MESI, no eviction. One request, data response, invalidation acknowledgement or dirty flush counts as one logical message. A snooped request carries the invalidation. Cached mode isolates index writes within an already authorized burst; slot data is omitted.
The message counter uses explicit logical transactions: a request, a data response, an invalidation acknowledgement, or a dirty flush. A snooped request carries the invalidation, so there is no additional imaginary packet per invalidated copy. Real interconnects combine, split and route these actions differently. The widget implements a serial atomic-bus MESI state machine, with no evictions or transient states. Its counts let you compare the same trace under two layouts; timing needs a real machine.
Now look at the two indices. Head and tail are small enough to share a 64-byte line on common x86 machines. The worker writes head and the writer writes tail. Even if each has cached the peer's boundary and neither needs a fresh peer load, their independent writes steal permission for the same line. That is Independent variables occupy one coherence unit, so writes to either invalidate the cache line containing both.. The program has no data race when the atomics and payload protocol are correct; it simply moves a line more often than the logical communication requires.
Turn on the cached-index burst in the widget. It alternates head writes by core 0 and tail writes by core 1, assuming each side already has permission for a range of slots. Packed, nearly every write invalidates the peer. Padded, each core retains its own Modified index line after the first miss. In the full handoff trace, peer reads remain necessary: padding cannot eliminate true sharing of each index. This is why padding and cached boundaries work together.
Same variables, different coherence granularity
Packed · 64 B
head (8 B) | tail (8 B) | remaining 48 BA write to either index needs permission for the entire line.
Padded · line 0
head (8 B) | padding (56 B)Only the worker writes this line. The writer still reads it.
Padded · line 1
tail (8 B) | padding (56 B)Only the writer writes this line. The worker still reads it.
Payload lines
slots[0] | slots[1] | …Records move from worker to writer. Keep them separate from frequently updated metadata.
MESI is a family resemblance, not the literal protocol in every processor. MOESI adds Owned, allowing dirty data to be shared while one cache remains responsible for supplying or eventually writing it back. MESIF adds a Forward state to designate which clean sharer should answer a request. These refinements reduce redundant data traffic or memory updates. They preserve the central rule that competing writes cannot independently proceed on divergent cached copies of one line.
A snooping system broadcasts or multicasts requests so caches can check their tags. A directory-based system keeps owner/sharer information near a home agent and targets the relevant caches. Hybrid designs use snoop filters to avoid probing cores unlikely to hold the line. Scaling to many cores requires reducing pointless probes as much as accelerating the data path. The writer of our queue does not choose MESIF or a directory API; it chooses a data layout that creates fewer ownership conflicts.
The memory dive's cache-line level explains line alignment and spatial locality, while the microprocessor dive shows cache lookup. Here the additional cost comes from ownership. A line can be present in your L1 and still require a remote round trip before you may modify it. A load hit and a write-permission hit are different events.
Coherence makes one line behave consistently. Padding changes which operations compete for that line; it cannot replace the ordering that makes a handoff safe.
Make ownership changes rare
Once the queue is correct, optimize communication frequency. Changing release to relaxed on head removes the proof. Reading the peer's head less often can preserve the proof while avoiding repeated coherence traffic. The distinction is the permission carried by a boundary: an acquired head authorizes the consumer to read every already-published slot up to that boundary, not just the first one.
Give the writer a private cached head. While its local tail has not reached that head, records remain available and it need not reload the shared head. Only when the cached boundary says empty does it acquire a fresh head. Give the worker a private cached tail in the same way: keep filling the free range it already knows about, and refresh tail with acquire only when it appears full. The cached value can be stale in a conservative direction. It cannot invent free or filled space.
For modulo indices, preserve the reserved-slot invariant and update cached boundaries before deciding whether the queue is full or empty. A boundary cannot be reused as permission for an additional whole lap. Wider monotonic sequence counters are another design, but unsigned wraparound and distance calculations need a separate proof. The compact implementation above keeps the arithmetic local and refreshes on every call; the cached version below changes the frequency of observation, not the meaning of release or acquire.
Next separate the two writer-owned indices. For a known 64-byte line size, place each atomic in a struct whose alignment and size keep consecutive instances apart. Aligning the whole queue alone only aligns its beginning; it does not separate fields within it. Payload slots also deserve their own aligned region so metadata and the first record do not accidentally share a hot line.
#pragma once
#include <array>
#include <atomic>
#include <cstddef>
#include <cstdint>
struct Record {
std::uint64_t sequence = 0;
};
class CachedLogQueue {
static constexpr std::size_t size = 1024;
struct alignas(64) PublishedIndex {
std::atomic<std::size_t> value{0};
};
struct alignas(64) ProducerState {
std::size_t head = 0;
std::size_t cached_tail = 0;
};
struct alignas(64) ConsumerState {
std::size_t tail = 0;
std::size_t cached_head = 0;
};
PublishedIndex published_head_;
PublishedIndex published_tail_;
ProducerState producer_;
ConsumerState consumer_;
alignas(64) std::array<Record, size> slots_{};
public:
bool push(Record record) {
const auto head = producer_.head;
const auto next = (head + 1) % size;
if (next == producer_.cached_tail) {
producer_.cached_tail =
published_tail_.value.load(std::memory_order_acquire);
if (next == producer_.cached_tail) return false;
}
slots_[head] = record;
producer_.head = next;
published_head_.value.store(next, std::memory_order_release);
return true;
}
bool pop(Record& record) {
const auto tail = consumer_.tail;
if (tail == consumer_.cached_head) {
consumer_.cached_head =
published_head_.value.load(std::memory_order_acquire);
if (tail == consumer_.cached_head) return false;
}
record = slots_[tail];
const auto next = (tail + 1) % size;
consumer_.tail = next;
published_tail_.value.store(next, std::memory_order_release);
return true;
}
};The published indices, producer state, consumer state, and payload each start in separate 64-byte-aligned regions. Only the worker touches producer_; only the writer touches consumer_. Keeping private cursor changes off the published lines avoids invalidating the peer just to update a local cache. Every successful operation still releases its new boundary. Only the apparently full or empty case pays for another acquire.
To see the wrap, first push and pop 1,022 records through an empty queue. Head and tail are then both 1022. The executable test performs the following operations, checks every returned record, and emits the logical cursor trace used by this table.
| Operation | Slot | Head after | Tail after |
|---|---|---|---|
| Empty after 1,022 handoffs | — | 1022 | 1022 |
| Push record 42 | 1022 | 1023 | 1022 |
| Push record 43 | 1023 | 0 | 1022 |
| Pop record 42 | 1022 | 0 | 1023 |
| Pop record 43 | 1023 | 0 | 0 |
| Pop reports empty | — | 0 | 0 |
| Push record 44 | 0 | 1 | 0 |
After the writer acquires head = 0, its cached boundary permits reading slots 1022 and 1023. It reaches that boundary only after the second pop, then must refresh before reading again. The worker similarly refreshes its cached tail before its next cursor would collide with it. Indices stay in 0…1023, so this is modulo-ring wrap, not overflow of std::size_t. The test also fills all 1,023 usable slots, rejects one more push, and checks repeated full-to-empty laps.
From v2, run node --test src/dives/atomics/native.test.mjs. It compiles the companion cached-queue.test.cpp with GCC and Clang, compares the trace fixture, and sends five million numbered records through each executable. Setting ATOMICS_SANITIZE=thread runs the same tests under ThreadSanitizer.
struct alignas(64) Index {
std::atomic<std::size_t> value{0};
};
static_assert(sizeof(Index) >= 64);
Index head;
Index tail;C++17 provides std::hardware_destructive_interference_size as an implementation-defined spacing hint; it is not a runtime query of every machine that might execute your binary. Its ABI implications matter when a public struct layout changes with build flags. A fixed alignment can be appropriate for a controlled target, but 64 bytes is not universal: some systems have larger relevant granules. Check the actual target and isolate the choice from persistent or network formats. The standard's hardware interference-size definitions distinguish destructive and constructive sharing.
Batching is the next lever. Fill several consecutive slots, then release head once to publish the entire range. On the consumer side, copy a group and release tail once. This trades fewer publications for delayed visibility of the first record in each batch. A logger may prefer a small time limit as well as a count threshold so a quiet stream does not leave a partial batch invisible forever. The worker should also publish the final partial batch when shutting down.
- Publication / record
- 1.000
- Later records before publish
- 0
Publish every record: 1,024 release stores for 1,024 records.
Linear bar scale: 0–1,024 operations. One final partial batch is published. Publication counts omit retries and tail updates.
The arithmetic is simple: publications equal ⌈1,024 / b⌉ for batch size b. At b = 1, there are 1,024 release stores; at b = 64, there are 16. The graph starts at zero and uses the same 1,024-operation scale for records and publications. It is a count model. Coherence messages need the actual access trace; elapsed time needs measurement with the real producer, consumer, placement and record size.
Do not infer that sixteen publications make the queue sixty-four times faster. The writer still copies 1,024 records and does file I/O. Payload lines still move between cores. Larger batches may improve spatial locality or increase the time a record waits to reach disk. If the file system dominates, optimizing the shared index might barely change end-to-end throughput. Measure latency percentiles as well as sustained records per second.
Atomic cost is especially sensitive to where the line lives. The PACT 2015 study by Schweizer, Besta and Hoefler measured several atomic operations across cache states and processor topologies. On the tested systems, ownership and coherence state strongly shaped latency; assuming that compare-exchange is always much slower than fetch-add missed much of the picture. Its charts are measurements of those machines, not constants for a new CPU. Contention can serialize many otherwise independent cores behind a single ownership path.
A practical benchmark should pin threads deliberately when comparing placements, warm up the code, keep the data set and payload work identical, and report compiler flags and hardware. Compare packed and padded indices, cached and uncached boundaries, and several batch sizes. Keep the disk out of a queue-only benchmark, then put it back for the application's benchmark. Otherwise the result may answer a different question from the one you intended.
The round trip across the die
At the bottom of the queue's handoff is a physical request crossing a chip. The core that wants to modify a line sends a request through its cache hierarchy. A home agent or distributed directory determines who owns the freshest data and which other caches need to relinquish permission. The response travels back over the on-die fabric. An index update is only a few bytes, but the transfer and permission machinery operate at line granularity.
Some processors connect cache slices and cores with a ring; larger designs often use a mesh or another packet fabric. Address hashing distributes home locations. The distance to the home, distance to the owner, fabric frequency, link contention, and queueing all influence the round trip. A nearby core on the same cluster can be a different communication partner from a core on another tile or socket. “Same CPU” is not a sufficient topology description.
Needs the index line to write head.
Tracks which cache owns this address.
Holds the packed head/tail line.
1 Request path
Address and control travel to the directory, then to the dirty owner.
2 Data path
The owner supplies the current bytes. They can bypass the home agent and DRAM.
3 Acknowledgement path
Core 1 moves M to I and confirms relinquishment. The home grants ownership after the required acknowledgements; core 0 can write once both grant and data have arrived.
Illustrative directory protocol for one dirty owner. The three logical paths may share physical ring or mesh links; implementations can combine data and acknowledgements.
Snoop filters store information about likely sharers so requests can avoid probing every private cache. They consume area, capacity and power; their precision and replacement policy affect how much unnecessary traffic escapes. Directory and cache controllers must also handle transient states: a read can arrive while ownership is being transferred, two writers can request a line together, and data and acknowledgements can travel by different paths. The simple MESI widget compresses each such transaction into one completed transition.
A lock-prefixed x86 instruction constrains the surrounding memory operations and makes its read-modify-write indivisible. For a suitably aligned, cacheable line, modern implementations normally obtain cache ownership rather than asserting a system-wide external bus lock for every operation. Split-line or unsuitable memory accesses can take much more disruptive paths. A locked operation is not the same as a fully serializing instruction such as CPUID: independent execution details remain microarchitecture-specific even though architectural memory ordering is strong.
For scale, an L1 hit is around four cycles on several well-known Intel cores, with other cores taking different numbers. Ownership transfers across cores can cost tens of nanoseconds, with larger costs across sockets or under contention. The relevant references are Intel's Optimization Reference Manuals for named cores and the atomic-operation measurements for tested topologies. These are orders of magnitude to motivate a measurement, not a stopwatch hidden inside memory_order_release.
The crucial quantity for a contended line is often the round-trip time before the next owner can proceed. Faster arithmetic does little if each iteration hands the same line back to another core. A lock-free queue with one producer and one consumer works well because ownership is structured: one thread writes each index, slots advance in a predictable ring, and a batch can amortize publication over many records. Put the indices on one line and you erase part of that advantage.
Return to record 42. The worker copies its fields into ordinary slot memory. A release publication binds that copy to head. The compiler chooses the instructions needed by the target. The store can wait in a buffer until the coherence machinery permits it to drain. The writer observes head through an acquire operation, gains the right to read the record, then releases tail to return the slot. Cached boundaries and batching reduce how often this agreement crosses the interconnect. Every layer is solving the same problem: transferring permission to rely on data without making every operation wait for every other core.
Correctness comes from the ordering edges. Speed comes from arranging data and work so those edges require fewer physical ownership transfers.
End of Atomics · 8 levels, Idea to Silicon
Where to next
Next in Systems and hardware · 05 of 06
What a single read() costs
Follow one HTTP request through a privilege boundary, a sleeping thread, epoll’s ready list and io_uring’s shared rings. Three ways to serve 10,000 connections, down to registers and the packet that wakes a core.
Practical notes
Detect false sharing with a runnable C benchmark
Compare adjacent atomic counters with cache-line-separated counters, then use perf c2c to locate contended lines when PMU access is available.