Store Buffers and the Total Store Order That Replaces Sequential Consistency

A store that misses in the local cache needs the line in an exclusive state before it can be performed, which on a multiprocessor means asking every other cache to invalidate its copy and waiting for the acknowledgements. The wait is a full interconnect round trip. Blocking the pipeline on it would make every write to shared data as slow as a coherence miss, and writes to shared data are the norm in synchronised code. The store buffer exists to decouple issuing a store from completing it.

The buffer is small, holding somewhere between a handful and a few dozen entries in typical designs, each entry carrying an address, data, and a size. A store is written into a free entry and the core continues immediately. The entry drains into the cache hierarchy when the line is available. Nothing in that description orders the store against anything else, and the model that results from keeping the buffer and restoring just enough order is Total Store Order.

The one relaxation TSO permits, and the four it keeps

TSO is easiest to describe as sequential consistency minus one specific reordering: a load may be satisfied before an earlier store to a different address has become visible to other processors. Everything else stays.

Ordering	Preserved under TSO	Why
Store → store	Yes	Stores drain from the buffer in FIFO order
Store → load (same address)	Yes	The load forwards from the buffer
Store → load (different address)	No	The load bypasses the buffer
Load → load	Yes	Loads issue and complete in order
Load → store	Yes	A store cannot drain before an earlier load has its value
Atomic → anything	Yes	Locked operations drain the buffer first

The four preserved orderings are what makes TSO describable as “sequential consistency plus a store buffer”, and it is worth understanding why each holds rather than treating the table as arbitrary.

Store to store. The buffer is a FIFO. Two stores from the same core enter in program order and drain in that order, so no observer can see the second before the first. This is the property that makes a store-only flag-then-data pattern safe on TSO without a fence, provided the flag store is issued after the data store. It is not safe on Arm, which permits store-store reordering.

Store to load, same address. A load checks the buffer first. If a matching entry exists, the load takes the buffered value and never touches the cache. This is store-to-load forwarding, and it is why a single thread writing and reading the same variable sees its own writes. Without it, TSO would not even be sequentially consistent for a single thread.

Load to load. Loads issue in program order and complete in program order, so two loads from one core cannot be observed in reverse. Weaker models relax some of these per-thread orderings, but the four-thread outcome from Cache Coherence Is Per Location, Consistency Is Not is not a per-thread relaxation at all: it needs two observers to disagree about the order of the two stores, which requires a model that is not multi-copy atomic, such as PowerPC.

Load to store. A later store cannot become visible before an earlier load has produced its value. The store cannot even be formed until its data operand exists, and if the data comes from the load, the dependency forces the order. For a store whose data does not depend on the load, the hardware still holds it until the load has completed, because the buffer drains behind the load.

Atomics. A locked read-modify-write drains the store buffer before it executes and does not allow subsequent operations to begin until it has completed. That is why an atomic operation acts as a full fence on x86, and why the historical LOCK prefix on an instruction that already writes memory doubles as a barrier.

Why the load bypass exists

The relaxation is not gratuitous. A load that hits in the local cache completes in a few cycles; a store whose line is shared must wait for invalidation acknowledgements from every sharer. If the load were required to wait for the store to drain, the core would stall on the interconnect for a duration set by the number of sharers and the topology depth.

Consider the common pattern of writing a result and then reading a different variable that is already in the local cache. Under sequential consistency the second operation waits for the first to propagate. Under TSO it does not, and the core keeps issuing. The benefit is largest exactly where it matters, in code that touches many shared lines with low locality, and the cost is confined to programs that actually depend on store-load ordering across addresses.

The bypass is implemented by letting loads issue to the cache in parallel with the buffer’s drain. A load that misses in the buffer and in the cache issues its request to the coherence fabric immediately. The store’s request may still be in flight. Both are in the interconnect at once, and there is no ordering between them at the point of visibility.

There is a further subtlety in the ordering of the buffer relative to speculative execution. A load that bypasses the buffer may be issued speculatively, before the core knows whether an older store to the same address exists. The hardware checks the buffer by address at issue and again at commit; a mismatch detected late causes a replay of the load. This is why a store buffer needs associative lookup rather than a plain queue, and why its size is limited by the cost of that lookup and by the comparators it needs.

The fence that restores sequential consistency

A full fence on TSO has one job: wait until the store buffer is empty. On x86 that is the MFENCE instruction, and its semantics are exactly “all stores before this instruction are globally visible before any operation after it”. No cache flush, no interconnect broadcast. The cost is the depth of the buffer times the drain rate, plus whatever the oldest entry is waiting for, which may be a full coherence transaction.

#include <stdatomic.h>

_Atomic int ready = 0;
int payload = 0;

void publish(void) {
    payload = 42;
    atomic_thread_fence(memory_order_release);   // orders payload before ready
    atomic_store_explicit(&ready, 1, memory_order_relaxed);
}

int consume(void) {
    if (atomic_load_explicit(&ready, memory_order_acquire) == 1)
        return payload;                          // guaranteed to see 42
    return -1;
}

The fence in publish compiles on x86 to nothing at all, because TSO already preserves store-store order. On Arm the same ordering is obtained without a separate barrier by making the release store STLR, which carries the ordering in its encoding; a full DMB would also work and would cost more. That asymmetry is the single most useful fact about portable fence code: the ordering is required by the weakest target a program must run on, and it costs nothing on the strongest one. The full set of cases appears in What a Fence Instruction Actually Does to the Pipeline.

The store buffer also explains why a fence is not a cache flush, a misconception that persists because early RISC designs did have explicit flush-like synchronising instructions. A fence orders; it does not discard. Data written before a fence is still in the buffer and will still be written to memory; the fence simply guarantees that the writing happens before subsequent operations become visible.

Costs and the cases where the model is not enough

TSO’s cost is bounded and predictable. A store to a line the core already owns exclusively costs nothing extra: the store can be performed directly in the cache and the buffer entry retires without an interconnect transaction. A store to a shared line costs an invalidation round trip, hidden by the buffer. The buffer’s capacity determines how much latency can be hidden before the core stalls on a full buffer, and a core that issues stores faster than the fabric can absorb them will stall regardless of the model.

The model’s limitation is that it does not compose with compiler optimisation. TSO describes hardware. A compiler is free to reorder ordinary loads and stores within a thread as long as single-threaded behaviour is unchanged, and a compiler that hoists a load above a store to a different address produces exactly the store-load relaxation TSO already allows, so no additional harm. But a compiler may also reorder two stores to different addresses, or sink a load below a store, which TSO’s hardware does not do. That is why the language-level model is weaker than the hardware model and why synchronisation must be expressed in terms the compiler understands rather than assumed to survive optimisation. The interaction is covered in Compiler Reordering and the Contract It Must Not Break.

A second limitation is that TSO is a per-location-plus-order model, not a model of causality. It says nothing about whether a store observed by one core is guaranteed to be observed by a third core in any particular relation to another store. On a machine with a non-uniform interconnect, two stores from one core can reach two different observers in different orders even though the core issued them in order and drained its buffer in order, because the paths differ. TSO implementations avoid this by serialising stores at a point all cores can see, which is why the model is associated with a total order on stores rather than a partial one. Architectures that do not provide that point have to describe their models with cumulativity rules instead, which is Propagation, Cumulativity, and Why Weak Models Need Transitive Visibility.

For code that must run on more than one architecture, the practical conclusion is that TSO is a performance fact about x86 and a reasoning convenience, not a portable assumption. The portable assumption is the language memory model, which is weaker than TSO and which requires the fences and atomic orderings that the language specifies.