The one reordering x86 permits, made visible, and the one memory order that forbids it. Two threads: Thread 1: x = 1; r1 = y; Thread 2: y = 1; r2 = x; Under sequential consistency, at least one thread must see the other's store: r1 == r2 == 0 is impossible. On real hardware each store sits in its core's STORE BUFFER for a while, and the following load reads the other variable from cache before that store is globally visible. Both loads can return 0. This is the "StoreLoad" reordering that TSO allows, and it is why memory_order_seq_cst exists. One million trials, three memory orders.
$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs
$ cd concurrency && ./build.sh
$ ./bin/05_store_buffer 1000000
relaxed r1==r2==0 in 87632 of 1000000 trials
acquire/release r1==r2==0 in 246171 of 1000000 trials
seq_cst r1==r2==0 in 0 of 1000000 trials$ grep -E '^\s+(xchgl|movl\s+\$1,)' bin/05_store_buffer.s | sort | uniq -c
7 xchgl %ecx, _ZL1x.0(%rip) <- seq_cst stores: xchg = store + full fence
7 xchgl %ecx, _ZL1y.0(%rip)The relaxed and acquire/release versions store with a plain `movl $1` (lab 03: on x86 a release store IS a plain store); only seq_cst uses xchg, which drains the store buffer before the next load can execute.
- relaxed: 8.8% of trials saw both zeros. acquire/release: 24.6%. Both are "impossible" under SC and both happen constantly, because on x86 relaxed and acq/rel compile to the same plain mov: neither prevents a store from being buffered past a later load. (The different rates are timing artifacts of the two runs; the point is both are far from 0.) - seq_cst: 0 in a million. The xchg makes the store globally visible before the load issues, so at least one thread must observe the other's store. This is the Dekker / Peterson pattern: two flags, each thread sets its own then checks the other's. Mutual exclusion built on that pattern REQUIRES seq_cst (or an explicit full fence between the store and the load); acquire/release is not enough, no matter how it reads. - Everything else you write (producer/consumer, publish-then-flag, reference counts, queues) needs only acquire/release, because those patterns order a store BEFORE a load in the OTHER thread through the same variable, which is what acq/rel promises. The store-buffer pattern needs a store in each thread to be ordered before a load of a DIFFERENT variable in the same thread: only a full fence does that. THE RULE OF THUMB YOU CAN DEFEND IN AN INTERVIEW: "Does my correctness depend on two threads agreeing on the order of stores to two DIFFERENT variables?" If yes: seq_cst (or a seq_cst fence between the store and the load). If no: acquire on the load that consumes, release on the store that publishes. And on AArch64 the answer is the same and the instructions are the same (ldar/stlr are RCsc), so this test gives 0 there for acq/rel too; the relaxed row would still show reordering, and more of it.
S1. x86 reorders exactly one thing: a store followed by a load of a different address. Everything you cannot see on x86 you WILL see on Arm; everything you can see on x86 you can see everywhere. S2. seq_cst on x86 costs an xchg per store (~20-40 cycles); use it where S1 matters, acq/rel elsewhere. S3. Write litmus tests for your own lock-free code: a million trials across two pinned cores finds in seconds what code review misses.
1. Pin both threads to SMT siblings (2 and 3): the rate drops (shared store buffer? no: shared L1 and different timing) but does not reach 0. 2. Replace the seq_cst stores with relaxed stores plus atomic_thread_fence(seq_cst) between the store and the load: 0 again (`lock orl` from lab 03). 3. Cross-compile the litmus for aarch64 (tools/a64.sh) and run it under qemu: user-mode qemu executes the threads with a single-core model, so you will NOT see reordering there. That is a lesson about emulators, not about Arm. ============================================================
#include "../tools/bench.h"
#include <atomic>
#include <thread>
/* Thread 1: x = 1; r1 = y; Thread 2: y = 1; r2 = x;
* Sequential consistency forbids r1 == r2 == 0. TSO (x86) allows it: each store sits in the
* core's store buffer while the load reads the other variable from cache (StoreLoad reorder). */
static std::atomic<int> x{0}, y{0};
static std::atomic<long> round_{0}, done1{0}, done2{0}; /* main announces a round; each thread reports its own completion */
static int r1, r2;
template <std::memory_order MO> static void t1(long trials) {
for (long t = 1; t <= trials; t++) { while (round_.load(std::memory_order_acquire) != t) {} x.store(1, MO); r1 = y.load(MO); done1.store(t, std::memory_order_release); }
}
template <std::memory_order MO> static void t2(long trials) {
for (long t = 1; t <= trials; t++) { while (round_.load(std::memory_order_acquire) != t) {} y.store(1, MO); r2 = x.load(MO); done2.store(t, std::memory_order_release); }
}
template <std::memory_order MO> static long run(const char *name, long trials) {
long both_zero = 0; x = 0; y = 0; round_ = 0; done1 = 0; done2 = 0;
std::thread a([&] { bench_pin(2); t1<MO>(trials); }), b([&] { bench_pin(4); t2<MO>(trials); });
for (long t = 1; t <= trials; t++) {
x.store(0); y.store(0);
round_.store(t, std::memory_order_release); /* start trial t */
while (done1.load(std::memory_order_acquire) != t || done2.load(std::memory_order_acquire) != t) {}
if (r1 == 0 && r2 == 0) both_zero++;
}
a.join(); b.join();
printf("%-26s r1==r2==0 in %ld of %ld trials\n", name, both_zero, trials);
return both_zero;
}
int main(int argc, char **argv) {
long trials = argc > 1 ? atol(argv[1]) : 1000000;
run<std::memory_order_relaxed>("relaxed", trials);
run<std::memory_order_acq_rel>("acquire/release", trials); /* store=release, load=acquire */
run<std::memory_order_seq_cst>("seq_cst", trials);
return 0;
}A lab is done when you can say what it showed on your machine — not when you have read it.
It decides which problems come first, which drills open, which labs you see and how the Learn surface is organised. Change it any time from the switch in the top bar, or press Escape to look around first.