memory ordering is not what you think

I spent a week finding out why lock-free code that worked on x86 lost messages on a Graviton instance. I kept looking at the processor before checking whether the language allowed what I had written.

A ready flag is where that mistake is easiest to see. The reader checks one address, then uses data at another. How does the first load make the second safe?

the store that makes a payload readable

Here only ready is atomic; payload is a plain int. Start both threads after initialization and call each function once:

#include <atomic>
#include <cassert>

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

void producer() {
  payload = 1;
  ready.store(true, std::memory_order_release);
}

void consumer() {
  if (ready.load(std::memory_order_acquire)) {
    assert(payload == 1);
  }
}

There is only one true value for the consumer to find: the one the producer stored. If the load returns true, we can join that release store to this acquire load. C++ calls the edge synchronizes-with. Now trace the whole path from the payload write, through the flag, to the assertion. The write happens before the read, so a plain int works here.

A false flag sends the consumer straight back out. It never touches the payload and never retries. The producer also gets no second turn with this payload. Another write would need separate coordination with the reader.

Change both flag operations to relaxed and that path breaks. We still read and write the flag atomically; we have lost the ordering for the payload. I would ask the same question about an atomic pointer: what publishes the object at that address? Rust has the corresponding Ordering::Release and Ordering::Acquire operations, though publishing an object also requires obeying Rust's aliasing rules for the non-atomic storage.

how a store can still be waiting

A core may have to wait to write a cache line. If another core owns the line, for example, the coherence protocol has work to do before this core can change it. Keeping the store in a buffer lets later instructions make progress during that wait. The buffer entry can drain once the core has the line and permission to write it. Until then, another core may still read the old value.

That forwarding matters. A thread can read its own recent write even while everyone else still sees the old value. For a different address, there may be nothing in the buffer to wait for, so a later load can finish ahead of the earlier store. There goes the assumption that all accesses fit into one global order that respects every thread's source order.

Out-of-order execution inside a core is a separate part of this story. Independent instructions can execute before earlier ones finish, provided the processor preserves the architectural behavior promised to its running thread. That promise does not tell us the order in which another core can observe memory accesses. A memory model supplies those constraints. Coherence alone covers one location: cores can agree about writes to x without any rule connecting them to writes at the ready flag's address.

both readers get zero

The x86-TSO model by Owens, Sarkar, and Sewell describes ordinary aligned accesses to cacheable memory with a FIFO store buffer for each core. Stores leave that buffer in program order. Loads keep their order relative to other loads, and a load sees the appropriate earlier store from its own core, including one still buffered. But a load may pass a pending store to a different address.

Start both locations at zero and give each core one store followed by a load of the other location:

// Hardware litmus pseudocode; x and y initially 0.
// Thread 0            // Thread 1
x = 1;                 y = 1;
r0 = y;                r1 = x;

Zero in both registers is allowed on x86. Both stores can remain buffered while each core reads the other location and gets zero. Neither core needs to observe its own store late.

Either zero fits into an SC schedule on its own. Asking for both causes trouble. For r0 = 0, read y has to come before write y. For r1 = 0, read x has to come before write x. Add the two threads' program order and the arrows return to their starting point: write x → read y → write y → read x → write x. Those four events cannot fit along one forward timeline.

The enumerator made that easy to check. Only six SC schedules respect the two thread orders. Between them they return (0, 1), (1, 0), and (1, 1). With independent store-buffer flushes, it finds one extra pair: (0, 0). The entire buffered search has 34 states, small enough to inspect. I ran it with python3 scripts/blog-models.py; the output is from that model, with no CPU litmus run involved.

So far the accesses have all been ordinary aligned accesses to cacheable memory. I would consult the other architectural rules for streaming stores or device memory. There is also a check to make before looking at assembly: does the source contain a C++ or Rust data race? If so, favorable x86 instructions cannot make that program valid.

the flag arrives, the payload does not

Message passing has a different pair of dependencies. Here the writer stores x and then y; the reader loads y and then x. Again both locations start at zero. This is hardware litmus pseudocode, because running the same sketch with plain shared C variables would introduce a data race:

// Hardware litmus pseudocode, not unsynchronized C.
// x and y initially 0

// Thread 0            // Thread 1
x = 1;                 r1 = y;
y = 1;                 r2 = x;

Here the result to look for is r1 = 1, r2 = 0, a new flag followed by an old payload. Try putting that on x86's timeline. The write to x must leave before the write to y, and the reader must load y before x. Once y has become 1 for that reader, the earlier x store is already visible. Under the ordinary-access TSO rules, this pair of results has no valid execution.

ARM permits more freedom. Even independent store-store and load-load pairs can be observed out of order, so this result can occur without added ordering. Certain dependencies constrain the possibilities under ARM's architectural rules. An extra source-level branch is no substitute for a general acquire operation. This difference matters when code moves to Graviton or Apple Silicon, even though source-language validity must be settled before reasoning about either machine.

Return to the C++ example. Release keeps the payload write on the producer's side of publication; acquire orders the consumer's later use. Both sides belong in the source so the compiler can select the required instructions. The load must actually read the release, or the applicable release sequence defined by the language model. Calling an unrelated load acquire creates no connection to our producer.

which ordering do we need?

I find "drain the store buffer" too crude a description of a barrier. x86 has mfence, sfence, and lfence, with different guarantees. ARM's dmb orders data-memory accesses; dsb adds completion requirements. Instruction synchronization is the job of isb. Choosing among them requires the instruction rules for the memory being accessed.

I compiled the same C++ example with Apple clang 21.0.0 (clang-2100.3.34.2), C++20, and -O2. For x86_64-apple-macos, the flag store was movb and the load was movzbl, with no added fence. For arm64-apple-macos with -mcpu=generic, they were stlrb and ldarb. Those are byte operations because ready is a bool. The release still orders the producer's earlier work, and acquire the consumer's later work; the x86 listing simply needs no extra fence instruction for this example.

The default arm64 target gave me a detail worth checking: its load was ldaprb, which my first search for ldarb missed. Adding -mcpu=generic changed it to ldarb. Arm's RCpc compiler note explains why a supported target can use the LDAPR family for C++ acquire loads. So I cannot infer the source ordering from one expected mnemonic. The commands save all three listings and the compiler version. This checks the generated code for those settings, without measuring its runtime cost.

I start with an ordering I can defend. Sequentially consistent atomics add a common order for those operations, which can make the first proof easier. I only weaken an operation when I can explain why the proof still holds. Then I inspect the generated code and measure on the target architecture under the relevant contention. An independent counter might need only relaxed ordering. Our ready flag publishes other data, so its job includes more than keeping its own value atomic.

a retry does not erase a race

Sequence counters make this distinction harder to ignore. A writer marks a counter odd, changes the data, then makes it even. Writers must be serialized. Stripped of the ordering and access primitives, the writer looks like this:

// Sketch only: writer serialization and ordering omitted.
seq++;          // odd: write in progress
write(data);
seq++;          // even: write done

A reader brackets its data reads with counter samples and retries if it finds an odd value or a change:

// Sketch only: platform-specific access/barrier rules omitted.
do {
  s1 = seq;
  read(data);
  s2 = seq;
} while (s1 != s2 || s1 & 1);

Equal even values let a valid implementation accept the snapshot, assuming the counter did not wrap during the attempt. But the sketch leaves the hard parts open. What keeps the data reads between the two checks? A final acquire load cannot hold earlier reads in place; acquire constrains later operations. And what makes a data read legal while a writer could be changing that data? Once plain C++ or Rust reads race with a writer, we already have undefined behavior. Discovering a changed counter afterward does not repair those reads.

I would start a kernel implementation with Linux's sequence-counter documentation: use read_seqcount_begin and read_seqcount_retry, and meet the writer serialization and preemption requirements. Copying READ_ONCE and WRITE_ONCE into the sketch would constrain the compiler's treatment of those accesses, but would still leave us to establish their ordering. I can then ask LKMM and herd7 whether the proposed rules allow a reader to accept a bad snapshot.

In the one-shot publication example I can name the store the reader observed and trace a happens-before path to the payload. The sequence-counter sketch still owes us those details. That is what I look for in lock-free code now. I would still stress-test it. A quiet run, though, cannot tell me which execution the next compiler or processor might allow.