Shared Memory Consistency From Scratch Part 1: Causality

Hardware and programming language memory models are rightly seen as difficult subjects, yet the confusion that surrounds them is a side effect of poor understanding, even amongst experts, and not part of the intrinsic difficulty. While I can't invent the universe to explain shared memory consistency from scratch, I can design a novel computer architecture, together with a set of atomic instruction, to highlight the core problems and how to overcome them. The architecture will be weaker than anything that exists today, and serve as a proving ground for various abstract memory models, including the now ubiquitous C++ memory model. Along the way, I'll introduce new semantics to facilitate efficient synchronization and reasoning about correctness, as well as discuss how to fix problems with the C++ model.

1. Outline

This article will cover the basic building blocks of the hardware, and the problems they cause when attempting to synchronize access to memory. I will also introduce the specialized memory operations we'll need to tame the chaos. Part 2 will introduce a novel framework for synchronizing data, then cover read-modify-write operations, local dependencies, fences, compiler mappings, and a summarized description of the machine, alongside its associated informal memory model. The remaining articles in the series will be dedicated to reasoning about correctness and exploring how formal models are synthesized, and where things tend to go wrong, particularly in the context of the C++11 and 20 memory models.

2. Memory Models

A shared memory consistency model defines the rules specifying how updates to shared data may be observed by different participants. In hardware, these rules govern both access to the same physical memory location, as well as management of cached copies (replicas) of different locations. From here on, hardware and software consistency models will be referred to simply as memory models.

Replication improves data locality, reduces read latency, and increases read throughput, but unlike distributed systems, hardware architectures do not, generally, use replication for fault tolerance, so availability is not a concern for memory models.

We could, in principle, provide exclusive access (serialization) to every memory location (a byte for byte-addressable memory) to only one participant - a processor - at a time, but that would ruin the throughput of the system. A simple fix is to split RAM into multiple granules, and provide a mechanism for per-granule exclusive access. We could also improve read throughput by allowing multiple processors to read from the same granule at the same time. If you're familiar with parallel programming terminology, what I'm describing is, conceptually, striped reader-writer locking for RAM. I will challenge this assumption in Part 2, but, for now, it's a useful and practical abstraction.

Once we bring caching into the picture, the reader-writer lock analogy becomes more complicated, because a read operation involves copying the granule into the reader's cache, and servicing future reads from the local copy. Therefore, in addition to acquiring exclusive access to the granule, a write operation needs to also make sure the cached copies are eventually updated. The choice of what "eventually" means will turn out to be the most important part of the hardware's design, and I'll discuss it at length later.

The size of the granule is also critical. If we make it too small, say, a byte, we'll introduce a lot of overhead in both tracking metadata and transaction frequency. If we make it too big, we'll increase latency due to large data transfers, and reduce concurrency by locking regions of memory the processor might not actually need, resulting in an overall loss of throughput. A conventional choice, nowadays, is to make the size of the cache line 64 bytes.

For the remainder of this article, you can assume that a granule spans multiple memory locations. The observable per-location behaviour is called coherence, while the mechanism that coordinates access and update propagation is a cache-coherence protocol. Because of the caching involved, a granule is typically called a coherence unit, or a cache line.

While coherence, often called per-location consistency, governs behaviour with respect to a single location, consistency, as a whole, also includes the observable ordering of memory operations across different locations, which involves a complex interplay between the processors, and the coherence protocol. Throughout this article, you may assume that variables used in examples reside in different cache lines, because that's when things get interesting. Unless stated otherwise, all variables used in the various examples will also be initialized to zero.

It may be tempting to assume that per-location behaviour is the same as the observed behaviour for individual cache lines. That's typically true in modern hardware, but I'd caution against making this assumption by default. I'll cover both deliberate and accidental violations at the end of this article.

For a detailed overview of cache coherence, the second edition of A Primer on Memory Consistency and Cache Coherence (APMCCC) is both open access and highly regarded. If you're interested in how processors communicate at the physical level, I'd recommend Principles and Practices of Interconnection Networks as a starting point. The remainder of this article will address topics that, in my opinion, are covered poorly or are completely ignored by existing resources.

3. Write Atomicity

Suppose you've implemented some arbitration mechanism that grants access to individual cache lines. At what point is a write operation considered complete, and should you service reads before the write reaches that point (read-others'-writes-early, or simply early reads)? Although these two questions are related to coherence, as you'll soon find out, they also have an enormous impact on consistency as a whole. In fact, when it comes to shared memory synchronization, the very first thing I want to know about a new hardware architecture is how it answers these questions. The answer to the first question, at least in Part 1, will be that a write is considered complete when all processors confirm that they can observe the new data. This matches the reader-write lock abstraction, and will serve as a stepping stone for understanding the framework I'll introduce in Part 2 - it's also the reality in most modern CPUs.

Taking a conservative approach, let's say you choose to wait for all copies to be marked stale, or invalidated, before the write is considered complete, and read or write access can be granted again. Other write propagation mechanisms, such as immediate replication (update), temporal leasing (time-based self-invalidation), and various hybrids come with their own trade-offs, and will not be considered here. This property of a coherence protocol is called write atomicity (WA), store atomicity, or multi-copy atomicity (MCA). For performance reasons, it's often assumed that the processor which performed the write can service its same-location reads early, which is called read-own-write-early multiple-copy atomicity (rMCA) or other-multicopy-atomicity (oMCA). The rMCA term is popular in the academic memory models literature, while oMCA was popularised by ARM's architecture manuals:

In an Other-multi-copy atomic system, a write from an Observer, if observed by a different Observer, must be observed by all other Observers that access the location coherently. However, an Observer can observe its own writes before making them visible to other observers in the system.

Lack of multi-copy atomicity is usually called non-multi-copy atomicity (nMCA), and is becoming increasingly rare on modern architectures. Here's a classification of popular architectures:

oMCA or MCA: x86, x86-64, ARMv8-A (2017 revision), RISC-V, SPARC v9 (all models), IBM z/Architecture (since System/370, though 370 was strict MCA), DEC Alpha (with caveats) nMCA: Itanium, ARMv7, IBM Power, NVIDIA PTX (GPU)

As you can see, the only modern nMCA architectures are Power and PTX. Memory model tests have identified nMCA behaviour in Intel's Iris Pro 650 GPU, and Intel's oneAPI GPU documentation uses language that, while not conclusive, indicates nMCA:

If the program author/compiler does not make appropriate use of fences, it is not guaranteed that all threads see the result of any given memory operation at the same time, or in any particular order with respect to updates to other memory addresses.

I couldn't find concrete information on AMD's GPUs, though it might be possible to infer the behaviour from a detailed examination of examples used in their manuals. This is a common, and concerning, trend because write atomicity is essential in selecting both correct and efficient synchronization primitives. Experienced developers are often forced to infer what's happening from non-standard (quasi-axiomatic) definitions, vague statements, an incomplete set of examples, or claims from people involved in the design. This has, historically, caused problems even for compiler developers who need to rely on expert interpretation of architecture manuals, even though the experts also struggle to get this right. The highly influential C/C++11 mappings to processors required multiple revisions (as seen in the changelog link at the top) to get things right, and, Itanium, which took an unusual approach to write atomicity, was completely broken for years after the initial mapping was proposed.

More recently, researchers have begun to compile systematic tests to determine what the hardware is actually doing, and while that's helped clarify the vagaries of manuals significantly, it still requires access to new or exotic hardware to run those tests. I'll cover those tests extensively throughout this article, particularly the Power ones, because that's the closest existing architecture to what I'm building.

3.1 Local Reasoning and Synchronization Asymmetry

So why do I claim that write atomicity is the most important property of memory models? Because all externally observable reordering of operations becomes a processor-local phenomenon, and an entire class of synchronization problems is eliminated. One of my primary motivations for working on this series was explaining the intrinsic difficulty of nMCA consistency from the ground up, without getting bogged down in the extrinsic complexity of various formal descriptions and their errors.

When writes aren't atomic, the burden of restoring atomicity, when necessary, falls on the reader, and the mechanisms for achieving that are either inefficient, or non-trivial. This asymmetry also causes a lot of problems for programming language memory models that target both oMCA and nMCA hardware. The C++11 memory model, which doesn't mandate write atomicity for the sake of compatibility and efficient implementation, has seen a wide, though sometimes unofficial, adoption, across a variety of low level programming languages including C, Rust, Odin, and any language that depends on LLVM, like Zig. Go was also inspired by C++11, though, like Java's volatile, it only provides operations that implicitly require write atomicity.

It took 6 years after the release of C++11 for researchers to find issues with its specification, and while C++20 made an attempt to repair the holes, it accidentally made instruction selection on some architectures, notably x86, horrendously inefficient, prompting Hans-J. Boehm, one of the chief architects of the model, to exclaim:

The fact that nobody noticed this for a very long time, and implementers were not bothered by it, suggests that the audience for this part of the standard is nearly empty. We conjecture that implementers actually rely on atomics mappings generated by memory model experts, who are more interested in formal models than standardese. A more formal description is likely to increase the size of the audience, and would definitely ease verification and reduce the probability of mistakes like this.

If you skim through the links I've provided, you'll find only a single paragraph related to Itanium in the "Repairing Sequential Consistency in C/C++11" paper by Lahav et al., and an insightful comment by Boehm:

This lack of "multi-copy atomicity" is also the core distinguishing property of the Power and ARM[v7] memory models.

All 3 links discuss "sequential consistency" (SC), and I suspect most people familiar with the term won't be able to see the connection with write atomicity, because prohibiting early reads should have nothing to do with the concept of a "total order of operations." I'll explain what those terms mean and correct the misconception later in the article, but before I do that, I need to introduce the virtual machine that will serve as the foundation for both understanding and deriving formal rules.

4. Hardware Wish List

Given all the, claimed but yet to be established, benefits of write atomicity, it might surprise you that the purpose of this section, and the rest of the article, is to relax that requirement. The primary reason why is because I want to develop a virtual machine architecture capable of exhibiting almost all subtleties of the C++11 memory model. However, the choice is not entirely arbitrary from an efficiency perspective either.

One of the main benefits of hierarchical caches is locality, and locality is only really relevant if you can exploit it. I'll cover how cache hierarchies interact with the memory model in Part 2.

Prohibiting early reads also means two processors which share a local cache can't exchange data until all readers, potentially very far away, have acknowledged an invalidation. The processor may also leverage SMT (Simultaneous Multithreading) or SIMT (Single Instruction, Multiple Threads) execution, and allow forwarding of yet-to-complete writes from its store buffer to reads performed by local hardware threads (store-to-load forwarding). We want to permit efficient sharing of data between hardware threads on processors that support SMT or SIMT execution, which means the store buffer will not be statically or dynamically partitioned to isolate hardware threads.

Applying the invalidation could also take a long time if the cache is busy servicing other invalidations or processor requests, so it would be convenient if processors only acknowledged that they've received an invalidation, and have placed it in an invalidation buffer (IB). The reason why I don't call it an invalidation queue is because parallel application of invalidations may be desirable for large caches, which would mean that a first-in-first-out (FIFO) processing order could be inefficient to maintain by default.

Another benefit of deferred invalidation is the possibility of caches acting as coherence proxies when bridging two potentially unsynchronized coherence domains, as is the case for GPUs and some ARM devices. The cache itself may appear as a processor on the local network, while actually managing traffic on behalf of an unknown processor elsewhere on the network. In this model, a shared cache, or an I/O controller can be modelled as local processors. While the C++11 model doesn't concern itself with different coherence domains, the need for understanding how algorithms could work in such environments exists for a non-trivial percentage of developers.

In summary, the virtual machine will support early reads, invalidation buffering, and out-of-order invalidation processing. The processor is allowed to execute instructions out of order whenever data dependencies permit that, but you should always consider the difference between out-of-order execution, which is a processor-local optimization, and the reordering effects of the hardware components and network that connect different processors. I'll also make no assumptions about the topology of the fabric (interconnect) used for inter-processor communication until Part 2, not even deterministic point-to-point routing (messages sent in order can arrive out of order). This means that perfectly in-order local execution may result in visibly out-of-order behaviour. Here's a simplified diagram of a single processor:

Given all these theoretical hardware benefits, you might wonder why so many popular architectures remain oMCA, or have pivoted to it like ARM. One of the reasons why, besides developer comfort, is their use of speculation. They may be just as permissive under the hood, but they'll aggressively cancel speculative computations when they detect that violations of write atomicity can become externally observable. Even though speculation can work around ordering constraints, it's not a silver bullet. Excessive coherence traffic spikes and pipeline flushing can be triggered by mis-speculation, which could result in either overall performance decline (average latency and throughput), or increased tail latency.

It's also possible to create a special set of store instructions that retain their write atomicity, while gaining additional functionality that allows them to assist in coordinating regular access to memory regions. Typically, only a small subset of memory is used for synchronization, so we'd still gain the theoretical advantages of our nMCA architecture. This is the approach Itanium took with its st.rel and read-modify-write (semaphore) instructions, and, to my knowledge, it was the first to do so. Nowadays, a lot of the decisions Itanium engineers made are seen in a negative light, but I think this particular feature of the architecture is actually quite good given the design tradeoffs. I won't be as practical as Itanium in this regard, because I want to limit test the permissiveness of the architecture.

On a side note, if we follow Adve and Gharachorloo's definition, the DEC Alpha is classified as MCA, because a write-atomic protocol "prohibits a read from returning a newly written value until all cached copies have acknowledged receipt of the invalidates or updates generated by the write (that is, until the write becomes visible to all processors)." As I'll demonstrate, a mere receipt of invalidates is not sufficient to preserve the appearance of MCA, unless additional synchronization functionality is provided by the hardware or instruction set architecture (ISA). I'm sure the authors understand this nuance, but I want to make it clear for people who're not familiar with this space of ideas.

5. Message Passing

Removing the write atomicity requirement is only acceptable if we're able to deal with the consequences. One of the backbones of any synchronization protocol is message passing, so we need to provide the tools necessary to accomplish this task.

Plain load and store instructions will be called ld and st respectively, and in pseudo-assembly syntax inspired by the Intel x86 style, the first message passing example will be:

// Processor 0 (P0) (this is a comment)
st [message], 42 // store 42 in the message variable
st [flag], 1

// Processor 1 (P1)
ld r1, [flag] // load the value of the flag variable in the r1 register
ld r2, [message]

Consider whether it's possible for P1 to see r1 = 1 and r2 = 0. Walking back from an undesirable state to a chain of events that caused it is an acquired skill, so let me go over it in detail.

If the receiver (P1) doesn't observe the new message value, then it must've had a stale copy of the cache line containing the variable (remember, all variables are in separate cache lines for these examples), and didn't apply or receive the invalidation.

However, the receiver did read the updated flag value, so it either didn't have it cached, or it processed that particular invalidation before the one for the message.

Both scenarios are interesting, but let's start with the latter. Our invalidation buffer allows out of order processing, so it's entirely possible that both messages were sitting in it, and the flag got processed first. As long as the sender side can guarantee that the message invalidation will arrive before the flag, we can simply snapshot the invalidations in the IB (mark the current head of, say, a ring buffer, and wait for the tail to catch up, or a similar mechanism) at the time of performing the flag load and wait for them to be processed before executing any subsequent loads.

Waiting for invalidations on every load is wasteful, so let's introduce a new operation, ld.rcv (rcv stands for "receive"), that will perform a load, snapshot the IB, and stall subsequent reads until the snapshotted invalidations are processed.

On the sender's side (P0), it's easy to guarantee that the invalidation for the message arrives before the invalidation for the flag if the processor waits for the message acknowledgement before issuing the flag write. However, that's also wasteful, because we might have to process many writes that are part of the message payload, and waiting for each of them to be acknowledged introduces unnecessary round-trip latency, and prevents bulk processing such as combining multiple invalidations into one packet sent across the interconnect (the receiver can implement similar optimizations). We can use the same approach as the receiver and implement a st.snd (snd for "send") operation that waits for all preceding stores to be acknowledged before making its write visible. The correct implementations is therefore:

// P0
st     [message], 42
st.snd [flag], 1

// P1
ld.rcv r1, [flag]
ld     r2, [message]

If the cache line containing the flag was already evicted for capacity or conflict reasons, the same logic still applies. We might fetch a new value directly, but we still need to snapshot the IB and stall until completion.

A robust cache coherence protocol must also deal with race conditions between data requests and invalidation messages. If an invalidation arrives after fresh data is supplied, it will result in a spurious invalidation, but the real correctness problem is installing stale data after an invalidation was processed.

We can take a pessimistic approach to solving the lost invalidation problem: announce that we've evicted the cache line and wait for acknowledgement before requesting new data. Such an explicit eviction scheme will guarantee that no invalidations arrive in the first place, but it introduces some unnecessary traffic if the same line is immediately requested soon after.

The optimistic approach is to perform a silent eviction (no announcement), but keep track of any invalidation messages that arrive while waiting for the response. If an invalidation address matches the address of the an outstanding read request, we can mark the register responsible for tracking the request with an "ignore data" flag, and immediately discard and re-issue the data when it arrives. This incurs significantly more unnecessary interconnect traffic compared to explicit eviction, but it only happens when a race is detected. I won't consider versioning the cache lines as a method of detecting staleness, because every bit in the cache is precious, and the metadata overhead relative to the size of each cache line would be too large.

From a protocol standpoint, explicit eviction usually results in simpler implementations, but, for our purposes, it really doesn't matter which approach is taken.

An alternative approach to consider, and I suspect this is what every major modern architecture does under the hood, is to snapshot the IB and stall data requests for every line fill. This will effectively reduce the ld.rcv into a simple read barrier (if processor-local reordering is allowed), hiding almost all reordering issues caused by invalidation buffering and out-of-order processing - speculative racy reads followed by a verification read of a synchronization variable, as is the case with sequence locks (seqlock), could still expose the presence of an invalidation buffer. Needless to say, I won't be taking this approach because my goal is to be as permissive as possible, and explore how complicated things can get on the software side.

On the subject of reordering, once we allow that, there's really no reason why ld.rcv should block subsequent writes, or wait for prior reads and writes to complete. The term used for this kind of instruction is a one-way read barrier. Similarly, st.snd can become a one-way write barrier.

The ld.rcv and st.snd instructions allow us to implement single-producer, single-consumer data structures like ring buffers, which can be used for efficient point-to-point communication between two processors. Such a ring buffer is already sufficient, though potentially inefficient, for design patterns like the Actor model, but, ideally, we should allow more than two processors to access the same data structure.

6. Mutual Exclusion

The second backbone of shared memory synchronization is mutual exclusion, or locking, as it's commonly called. A simple implementation of a lock can be done by synchronizing all accesses against a single variable. In pseudo-code, it looks like this:

lock.acquire()
// Critical section. Shared data accesses are only performed here.
lock.release()

The release operation can be as simple as storing the "unlocked" value in the lock variable:

st.snd [lock], 0 // 0 = unlocked, 1 = locked

I'm using the st.snd instruction because a write might've been performed inside the critical section, and we want the next processor which acquires the lock to be able to see it.

The acquire operation is more complicated and requires a read-modify-write (RMW) operation, which I'll cover in Part 2, but the basic idea is that we can perform a ld.rcv (a special variant of it) and check if the value is 0 (no one's holding the lock). If that's true, we can try to conditionally set the value to 1, which will only succeed if no other processor managed to sneak in and acquire the lock in between our load and the conditional store. If the lock is being held or someone else managed to get in before us, we simply retry, possibly after a small delay. The important part of this operation is the load, which makes sure we receive the latest update for the data from whoever held the lock before.

Here's the entire locking and update procedure in pseudo-assembly:

RETRY:
ld.rcv r1, [lock] // acquire the lock
// Check if r1 is 0 and try to conditionally store 1 if true.
// Go to RETRY if either fails, after a delay.

// Lock acquired. Access the shared data.
st.snd [lock], 0 // release the lock

There are more efficient lock designs and operations for acquiring the lock, but this setup is good enough for now. Can you spot any issues that could arise from this implementation? The problem now is processors executing the instructions out of order.

First, while the release operation already prevents prior stores from completing after the lock value is set, it doesn't constrain loads in the same way. Performing reads outside the critical section will provide no synchronization guarantees whatsoever.

Second, in the current example, we can't allow any store instructions to be executed before the conditional store, because that instruction can fail, and we'd end up modifying shared data without actually holding the lock. The conditional branch typically prevents such reordering from being externally observable, but reading is a bit more tricky. If we perform a read before the conditional store succeeds, we could end up reading data without any synchronization, and then succeeding anyway. Some processors, like Power, respect control (branch) dependencies when it comes to stores, but require additional ordering instructions to prevent speculative reads from completing when the branch is actually taken. In my quest to create the least programmer friendly architecture, I'll also allow speculative loads to ignore branch dependencies. More on this subject in Part 2.

Lastly, it might be tempting to leave the receive load as it is, but there are lock implementations that don't require any conditional store operations between the load and the store. One example is a simple ticket lock, where one variable is used for reservation, and a next variable is used to indicate who can enter the critical section next. Such an implementation would use an RMW operation to reserve a "ticket", and then busy wait with a receive load on the next variable. This means we need to add writes to the list of operations that can't be executed before the receiving load.

I think now is an appropriate time to introduce new load and store instructions to capture these rules. An acquire load will be performed by executing ld.acq and will behave like ld.rcv, except it will also stop subsequent writes from completing before it. In effect, all subsequent instruction processing will halt until the acquire load completes, though we don't need to wait for prior instructions to complete.

Similarly, a release store, st.rel, will behave like st.snd, but it won't allow prior loads to complete after it. Instructions that come after the release store need not wait for anything else to complete, as they're outside the critical section.

This behaviour of acquire and release is sometimes called "Roach Motel optimization", which is a reference to the slogan of a roach trap with that name: "Roaches check in, but they don't check out." The idea is that unrelated operations can move inside the critical section, but nothing inside can get out. Using our "barrier" terminology from before, both ld.acq and st.rel are now one-way read-write barriers, but in opposite directions.

Mutual exclusion, particularly when multiple parallel reads are allowed, is actually much better than people give it credit for, though that will be the subject of another article.

Without implementing some kind of complicated transaction protocol, cache-coherence can only provide unsynchronized access to one cache line worth of data, because our coherence protocol behaves like a reader-writer lock, with some important caveats I'll discuss later. Typically, architectures only provide atomic access - meaning it's safe to access in parallel - up to 4, 8, or maybe 16 bytes at most - enough bytes to pass one or two pointers around. These are the variables we'd be using for send, receiver, acquire, and release instructions.

If atomic instructions span two separate cache lines, processors usually give up and raise an exception, or enforce a heavy interconnect lockdown. x86 is an example of the latter, where instructions with the "LOCK" property (prefix) will actually cause a system-wide lock of the interconnect until the double-line transaction is complete. A userspace program can effectively perform a denial of service attack by abusing this mechanism, which is why the Linux kernel, for example, has options for detecting so-called split locks. The x86 XCHG instruction has an implicit "LOCK" prefix with memory operands, so it's easy for developers to degrade system performance without any malicious intent. Accesses that span two different cache lines without this prefix are silently allowed to tear, meaning you get only parts of what each processor wrote. This is one of many reasons why hardware architectures should have explicit atomic instructions.

If you prefix every atomic operation in x86 with "LOCK", you'll be shooting yourself in the foot in terms of performance, because that prefix will also cause the processor to stall until a snapshot of its store buffer is fully processed - and you rarely want that. For correctness reasons, processors that don't even support locking should just raise an exception when an atomic variable isn't contained in one cache line. This is not possible on x86 - you either get garbage or unnecessary performance degradation.

However, even assuming our atomic synchronization variables are correctly aligned, we're not out of problems to address yet.

7. Repairing Write Causality

We may sometimes want parallel access to data without mutual exclusion or any kind of acquire or release synchronization. This kind of access will be facilitated by relaxed atomic operations, and I'll use the .rlx suffix to denote them in code snippets. In fact, any instruction with that suffix, or a stricter version of it, can be considered atomic. These instructions will not offer any ordering or visibility guarantees for ordinary loads, stores, and even other relaxed operations.

If you've been paying attention so far, you might be wondering why early reads haven't caused any issues yet. Consider the following scenario:

// P0
st.rlx [data], 1

// P1
ld.rlx r1, [data] // reads 1
st.rlx [flag], 1

// P2
ld.rlx r2, [flag] // reads 1
ld.rlx r3, [data] // reads 0

Is it possible to get r1 = r2 = 1, and r3 = 0 at the end? The answer is yes, and I already hinted at the mechanism. Lack of write atomicity means P0's write to data might be observed by P1 before the invalidation even reaches P2. P1's invalidation of the flag could then race P0's to P2's invalidation buffer, and then, assuming P2 already had a cached copy of the data, we get a stale read for data, and a fresh read for flag. We can't even guarantee that the invalidation will be in P2's IB by the time the flag invalidation is processed, so ld.rcv and ld.acq can't prevent this outcome.

Because we didn't give the relaxed loads any ordering guarantees, this outcome is consistent with the operations in either P1 or P2 swapping places, so, while perhaps counter-intuitive, there's no issue with allowing this outcome once we allow local reordering of regular and relaxed operations.

However, the situation becomes more complicated once we introduce synchronization on the flag variable:

// P0
st.rlx [data], 1

// P1
ld.rlx r1, [data] // reads 1
st.rel [flag], 1

// P2
ld.acq r2, [flag] // reads 1
ld.rlx r3, [data] // reads 0

Now we have a problem. Even with local reordering permitted, the rules for acquire and release state that memory operations can't move past the one-way barriers, yet, unless we somehow violated causality, that's the only logical conclusion. We could either prohibit this behaviour, or document it as an exception, and, since the C++11 memory model demands the former, we'll have to figure out how to make sure P0's write is visible to P2 by the time it reads the updated flag.

The simplest, and most efficient, fix in terms of hardware complexity is to make all atomic operations write-atomic. This was Itanium's approach, and chapter 13.2.1.12, "Obeying Causality," of the Intel® IA-64 Architecture Software Developer's Manual Volume 2: IA-64 System Architecture Revision 1.1 uses the same example. However, since the C++ memory model doesn't mandate this, I find it interesting to explore how we can prohibit the undesirable outcome with minimal additional complexity.

7.1 External Cumulativity

A straightforward way to prohibit this outcome is to fix the problem at the source. If P1 is aware that one of its loads has observed an early store, it can stall on the release operation until the observed store is globally visible - it can't know the future, so it needs to be conservative. The processor which produced that store is naturally aware of when the last invalidation acknowledgement arrives, which signifies global visibility, so it can send a message to any processor it serviced early to notify it of the completion.

It would be extremely wasteful to send a notification for every store, because there's no guarantee a release operation will even be executed. Furthermore, accessing regular data like that should be classified as a race condition, so we should only do it for atomic operations. Lastly, we need to decide what to do in cases where the programmer mixes regular memory operations with atomic ones.

One way to let the processor which produced a write (producer) know that an atomic read is being serviced early, is by augmenting the system's communication protocol with an ReadAtomic operation. If it services such an atomic read early, it can use a per-processor bitset, or a similar data structure, to flag that it needs to notify that processor of the global acknowledgement before removing the write from its pending-completion buffer (or wherever that's being tracked). If the write is already globally acknowledged, it can set a "completed" bit in its response.

On the early consumer's side (the processor which issued the atomic read), if the data for the load is supplied, and the "completed" bit isn't set, the load can be placed in a special buffer optimized for lookup and snapshotting, or tagged with a local "epoch" that advances when a release operation is initiated. The release write can then wait until all loads with the previous epoch, or the snapshotted entries, have received a completion notification before issuing the write.

In the literature on memory models, this scenario is called Write-to-Read Causality (WRC), and the term, at least to my knowledge, was first introduced by the seminal Foundations of the C++ Concurrency Memory Model paper by Adve and Boehm. If you're familiar with distributed systems theory, you might recognize WRC as a test of whether the system enforces the "writes follow reads" guarantee of Causal Consistency. The specific feature of the release operation that I developed in this section is also known as A-cumulativity in the IBM Power and later ARM manuals, though I prefer to call it external cumulativity as a direct reference to the fact that we're ordering external writes observed through early loads.

I call this test D-WRC, where the "D" stands for "Direct", because the processor performing the release store observes the value it's propagating directly.

Send operations don't need to provide external cumulativity because they're optimized for point-to-point message passing.

7.2 Internal Cumulativity

Ordering of internal writes, or internal cumulativity (B-cumulativity in IBM and ARM manuals), is a feature the release operation already supports. Consider the following modification of WRC, which is sometimes called ISA2 (a modified version of it appears as the second cumulativity example in the Power ISA manuals):

// P0
st     [data], 1
st.rel [data_ready], 1

// P1
ld.rlx r1, [data_ready] // reads 1
st.rel [flag], 1

// P2
ld.acq r2, [flag] // reads 1
ld     r3, [data] // reads 0

C++11 forbids this outcome, and, given the current implementation of release, it's impossible to manifest it, because, by construction, the release operation doesn't perform the write to data_ready until data is globally visible, so any observation of data_ready = 1 implies the new value for data is obtainable, provided the invalidation buffer is processed. However, notice how P1's release store is completely unnecessary in this test.

In an implementation where P0 didn't have to wait for global acknowledgement of the data modification before issuing the data_ready write, and assuming the architecture guarantees those writes will be observed in the same order by every processor, this outcome would still fail to manifest, because of P1's observation of the modified data_ready flag. External cumulativity would kick in, and P1 will have to make sure its write is issued after the data_ready update is globally visible, which, by extension, guarantees the data write is also globally visible (data has to be processed before data_ready if we want to maintain write ordering).

I'll address the redundant work performed by st.rel in the next chapter, but what's important for now is the fact that external cumulativity is load bearing, and the only difference between ISA2 and D-WRC is that the value we're observing is an indirect causal successor of the write we want to propagate. This is why I call this test I-WRC, which coincides with "I" for both "Indirect" and "Internal [cumulativity]". Global visibility, which is the current solution for external cumulativity, is also an unnecessarily strong condition for external cumulativity too - all we want is for the causal graph of dependent writes to be visible to any processor which observes the most recent write in the graph.

7.3 Error Detection

The additional complexity and storage requirements to support cumulativity might seem excessive given that, seemingly, the only benefit is a faster completion of atomic writes, and only to handle a case that I, quite frankly, haven't seen in real code (would appreciate it if anyone who's encountered this scenario in practical algorithms emails me about the specifics). However, we can use this tracking machinery to detect improper synchronization if writes are tagged with an "atomic" bit. If an incomplete non-atomic write value is requested early, the processor could be dynamically configured to trigger an exception, instead of letting potentially buggy code continue to execute. This is obviously not sufficient to catch all synchronization bugs, but it will increase both reliability and security.

Raising an exception when an early non-atomic read is detected should also raise some concerns about this particular nMCA architecture. We're paying a rather large complexity tax, only to optimize the synchronization operations themselves. Outside of complex coordination protocols or optimistic locking implementations, like a seqlock, early reads will likely be followed by an attempt to write to the same location immediately, which must wait for global acknowledgement anyway. Moreover, seqlock-like scenarios, which are extremely useful in practice, can't be implemented if a racy read triggers an exception. Addressing these concerns will require fundamental changes to the architecture, and will come with non-trivial tradeoffs, so I'll discuss those later.

8. Asynchronous Cumulativity

Analysis of I-WRC revealed that we could potentially optimize the implementation of release stores, because, at least as far as internal cumulativity is concerned, global visibility is not required as long as we can guarantee that the value written by the store is only available after prior local writes become available. This is trivially guaranteed in the case of hardware multithreading, because threads on the same core have access to a shared store buffer, which can easily provide the required ordering.

However, the current behaviour of release stores may still be useful, so I'll split the release implementation into a release store, which only guarantees ordered delivery, and a commit store, st.cmt, which, in addition, waits until prior writes are globally visible, or committed, before issuing its associated store operation.

I'll not cover possible implementations of cross-processor asynchronous cumulativity in this article - that will be the subject of Part 2 - but I'll briefly discuss the inherent challenges such an implementation needs to overcome in a setup where no assumptions can be made about the topology of the interconnect, and the implementation of cache coherence.

8.1 Asynchronous Internal Cumulativity

Suppose you decide to implement internal cumulativity by assigning each invalidation a monotonically increasing, per-processor sequence number. A receiving processor could then stall applying invalidation when it detects there are gaps in the sequences that have been observed. But what if we don't even need to send an invalidation for the release store itself, because the receiver doesn't have a stale copy of its associated cache line. The receiver may have also silently evicted the cache line. We'd need to guard against a cache line fill request overtaking in-flight invalidations, and that's where complexity and overhead start to explode. The receiver can't know who's going to supply the data, so it can't provide a reference "highest observed" sequence number to identify a request we can reject, unless it attaches the observed sequence number vector for all processors, which is expensive. On the producer's side, we need to snapshot the per-processor counter when a release store is issued, so we can attach it to the returned data payload; the receiver can then detect a mismatch and delay installing the new data.

Now what happens when we need to downgrade the write to a shared state? The new data could now be supplied by multiple processors, so we need to replicate the tracking metadata, and make sure it's actually usable by processors with different sequence numbers. The tracking metadata would also need to be replicated if another processor issues a read-modify-write operation, though I'll cover the reason why later. If we decide to deny those request until outstanding invalidations are confirmed, we'd be stalling reads and writes globally, all for the sake of not blocking a single write. Do the tradeoffs seem worth it to you?

8.2 Asynchronous External Cumulativity

Asynchronous external cumulativity is difficult to achieve even in the hardware multithreading case. If an early read is serviced from a local write that's not yet globally visible, we'd need to make sure subsequent release stores by the reader are serviced after that particular write. However, the write which was observed early could, itself, be a release store from another thread that observed one or more writes early. This applies recursively up the chain, until we've built up an acyclic dependency graph of writes. Tracking this metadata efficiently is difficult, and would require heavy compression to avoid large storage requirements (cache is already precious, and we'd need to justify any additional storage), and that also comes with false dependency tradeoffs. If you think this is difficult to implement efficiently in hardware, now imagine implementing the tracking and ordering mechanism across multiple processors. This is orders of magnitude more difficult compared to cross-processor internal cumulativity, and that was already highly non-trivial.

Fortunately, there's an alternative to implementing a full distributed system, with all its associated downsides, in hardware.

8.3 Partially-Ordered Interconnect

The problem of asynchronous cumulativity becomes a lot more tractable in hardware if we drop the "arbitrary topology and routing" assumption about the interconnect. Instead of tracking and enforcing a directed acyclic graph of dependent writes and reads, and all the associated metadata, we could turn those dependencies into transient state inside an interconnect that's, itself, a directed acyclic graph (partially ordered). Moreover, this transient state is provably bounded, provided a suitable backpressure mechanism is in place.

This insight was polished into the operational "Flowing Model (FM), with a more abstract "Partial Order Propagation" (POP) distillation, during the development of the pre-MCA ARMv8 architecture. The paper is excellent, though I'd recommend reading it alongside "Simplifying ARM Concurrency: Multicopy-atomic Axiomatic and Operational Models for ARMv8", which explains the issues with this model, and why ARM ultimately pivoted away from it by requiring MCA architecturally. If you're unfamiliar with the subject, you'll get a lot more out of the papers if you finish this article first. I'll discuss how we can improve upon the Flowing Model in Part 2.

The idea was also explored in the 2013 "A String of Ponies", which introduced Distributed Pony, an experimental extension of the actor-based Pony language.

A similar approach was taken in the distributed systems world with the 2017 Saturn, a metadata service for causally consistent replication, except the partially-ordered topology is dynamically reconfigured in the event of a fault. The authors appear unaware of prior work in the multiprocessor interconnect space, and their related-work review also indicates this idea isn't present in the distributed systems literature, which, while strange, is not surprising given how the work on Flexible Paxos revealed there's still a lot of low-hanging fruit in that space (sorry, Heidi Howard).

Using network topology to maintain order without excessive metadata isn't a particularly new idea, and appears at least as far back as 1991 in the Race-free Interconnection Networks and Multiprocessor Consistency paper. The 1997 Sun Microsystems Enterprise 10000 (Starfire), as presented in chapter 7.7.1 of APMCCC, also uses a tree topology to serialize coherence traffic across 64 processors:

Regardless of how it's accomplished in hardware, I won't require release stores to ensure cumulativity by blocking until causally-prior writes, whether internal or external, are globally visible - only per-processor visibility is necessary. Commit stores, on the other hand, will continue to maintain this property. IBM takes the same per-processor visibility approach when it comes to its lwsync instruction, which can be used to implement release-acquire synchronization on the Power architecture.

9. Commit-Reconcile Semantics

Adve and Boehm introduced another scenario, called Read-to-Write Causality (RWC), which shows up in practice, and often trips up even experienced developers. Here's a slightly modified version of it that introduces more useful context:

// tail = 0, head = 2 at the start

// P0 (Consumer)
st.rel [tail], 1 // advance the tail

// P1 (Producer)
st.rlx [head], 1  // decrement the head
ld.rlx r1, [tail] // reads 0
// head - tail = 1

// P2 (Consumer)
ld.acq r2, [tail] // reads 1
ld.rlx r3, [head] // reads 2
// head - tail = 1

The C++ memory model architects decided that this outcome shouldn't be prohibited, even if we somehow managed to prevent the P1 store from executing after the load locally, and they had a very good reason for making that choice. We only have 2 variables instead of 3, and, when reading the paper, it seems like a purely theoretical concern.

Now imagine that head and tail are the producer and consumer indices of a ring-buffer-style input-restricted deque. The producer advances the head, the consumer advances the tail, and, at the start, the deque contains two items (head - tail = 2). This particular implementation, called a Chase-Lev deque, allows for multiple consumers, but there's only ever one producer, which is allowed to consume from the front by decrementing the head. Consumers in this design operate speculatively - they copy the entry at the tail first, then attempt to increment the tail index, hoping they were the first to do so.

In this scenario, P0 is a consumer that successfully pops one of the items from the tail. The store would be a RMW operation in actual implementations, but what matters is that a write is performed. The problem arises when there's only one item left in the deque, and both a consumer and a producer attempt to claim it:

If both of them see that there's one item remaining, which happens in this case, they'll both pop it and effectively duplicate the entry. We want one of them to observe head - tail = 0, so the producer can roll back its decrement, or the consumer can give up.

9.1 Store Buffering

The first problem to resolve is ordering the store and the load. The producer needs to make sure its intent to consume an entry from the head is visible to all consumers before it checks the state of the tail. However, we don't have any way of making sure a store is globally visible before executing a load. Conceptually, a commit store executes a commit pseudo-instruction before executing the store, where commit stalls until prior loads and stores are globally committed, meaning local stores and observed external stores (via loads) are globally visible. Similarly, an acquire operation executes an update pseudo-instruction after executing the load, where update performs the usual snapshot of the invalidation buffer and stalling until the snapshotted entries are processed. A commit store followed by an acquire load therefore maps to the following conceptual sequence of instructions:

// st.rel is equivalent to:
commit
st.rlx [head], 1
// ld.acq is equivalent to:
ld.rlx r1, [tail]
update

Notice how the relaxed store and load have no ordering guarantees. In fact, commit and update only stall their associated memory operations, so there are no ordering guarantees for anything that happens before or after them. This is not just a processor-local reordering either - executing the instructions in order provides no guarantees about global visibility because the architecture is nMCA. So what kind of operation do we need to provide to constrain store-load ordering?

Suppose we implemented a commit load (ld.cmt) instruction, which behaves like st.cmt, except it executes a load instead when all prior internal and external stores are globally visible. The store-load ordering case then becomes:

st.rlx [head], 1
commit
ld.rlx r1, [tail]

This might seem sufficient, but consider what would happen if an invalidation arrives before, or while waiting for the store to commit. Without an update, the follow-up load will read a stale value, which would, in effect, reorder the two operations, even if the processor faithfully executed them in program order. The commit load would therefore need to perform an update after the commit:

st.rlx [head], 1
commit
update
ld.rlx r1, [tail]

By the same logic, we can define a reconcile store, st.rec, that performs a store followed by a commit and an update. Notably, the commit part of this operation need only wait for the associated store to become globally visible, and the update part of the commit load should only make sure to apply the invalidation in the IB for the load's cache line, if there is one.

Both options are valid for this litmus test, and which one is a better choice would depend on the context in which they're used in a real algorithm. I'll pick ld.cmt because the instruction will become relevant again in the next section.

The store-load reordering problem is typically called store buffering, because it can be caused by a store buffering unit that allows the processor to continue executing instructions without waiting for cache line arbitration and global acknowledgement. However, as demonstrated, the presence of an invalidation buffer needs to be accounted for as well, both locally and remotely, because a buffered invalidation is the same as non-local store buffering.

The updated snippet now looks like this:

// P0 (Consumer)
st.rel [tail], 1 // advance the tail

// P1 (Producer)
st.rlx [head], 1  // decrement the head
ld.cmt r1, [tail] // reads 0
// head - tail = 1

// P2 (Consumer)
ld.acq r2, [tail] // reads 1
ld.rlx r3, [head] // reads 2
// head - tail = 1

Do you see any problems with it? While we've considered the ordering issues caused by the invalidation buffers, we've yet to account for issues caused by early loads.

9.2 Reconcile Loads

What would happen if P2's load of tail is early, and the invalidation hasn't even reached P1 by the time it performs its load? P2 may also observe the state of the head before P1's store. This would create the exact same problem we're trying to avoid, and, unlike the external cumulativity issue, this time we can't just shift the responsibility onto the commit operation. Fortunately, we already have the external-cumulativity machinery to detect the early load and stall until the observed write is globally visible. In fact, the commit operation does exactly what we need, so P2 can be modified to:

ld.rlx r2, [tail]
commit // wait for the tail write to be globally visible
update // perform the acquire operation
ld.rlx r3, [head]

Notice how this maps exactly to the ld.cmt pattern:

ld.rlx r2, [tail]
ld.cmt r3, [head]

If we only cared about economy of instructions, we could use ld.cmt to enforce the desired behaviour. However, it's worth considering the impact on the ISA as a whole. If a concrete implementation prohibits early reads, the commit in P2 becomes unnecessary. On the other hand, a ld.cmt operation still needs to guard against potential upstream write buffering, so the commit operation can't be dropped.

The other problem with the commit semantics on the second load is that it doesn't communicate the programmer's intent. Are they guarding against an upstream store, or do they want to work around the lack of write atomicity? It's convenient to have a load that can restore write atomicity, and we'll need such an instruction very soon in a different context.

I'll call the new instruction a reconcile load, or ld.rec; the name is inspired by the 1999 paper on "Commit-Reconcile and Fences" (CRF) semantics, though the similarity is superficial. Using pseudo-instructions, a reconcile load corresponds to the ld.rlx; commit; update sequence of operations, where the semi-colon is used to separate different instructions without a new line in between them. Something important to point out is that the commit in this implementation would only wait for its associated load, not all prior loads and stores. The reason why I'm illustrating it this way is to highlight the commit; update shape, because it will become relevant later. The reconcile load is actually similar to a commit store in that it's a more restrictive version of an acquire operation - it performs an update, just like an acquire, but it doesn't complete the operation until the observed value is globally visible.

Here's the final version of the example:

// P0 (Consumer)
st.rel [tail], 1 // advance the tail

// P1 (Producer)
st.rlx [head], 1  // decrement the head
ld.cmt r1, [tail] // reads 0
// head - tail = 1

// P2 (Consumer)
ld.rec r2, [tail] // reads 1
ld.rlx r3, [head] // reads 2
// head - tail = 1

Let's work backwards from P1's results to see if the undesired outcome is still possible. If P1 doesn't see P0's update to tail, that means P1's write to head became globally visible before P0's write to tail. This is guaranteed because the update performed by ld.cmt happens strictly after the commit. By the time P2 is able to complete its observation of P0's write, P1's head invalidation must be in P2's invalidation buffer. This is guaranteed because ld.rec stalls until the observed value is globally visible, and we know from P1 that the head update became globally visible before the tail update. Since ld.rec also performs an update, the subsequent ld.rlx can't observe a stale value for head.

I'll cover the full correctness proof together with some optimizations for existing Chase-Lev deque implementations using commit-reconcile semantics, and how both C++11 and C++20 fail to provide efficient cross-platform instruction mappings, in another article.

9.3 Delegated Store Buffering

A variant of RWC that's worth examining is W+RWC, because it also shows up in algorithms such as delegated safe memory reclamation.

Safe memory reclamation (SMR) is the name for a class of techniques that allow memory removed from a concurrent data structure to be safely reclaimed (returned to an allocator or the operating system) and reused (allocated again), despite other threads potentially still holding references to it. Besides reference counting, which requires expensive read-modify-write operations, common approaches differ primarily in how readers announce what they may still access. Implementations based on hazard pointers (HP) explicitly publish addresses which are currently being accessed, while epoch-based reclamation (EBR) requires announcements that a thread is active in a particular "epoch", conservatively protecting memory that might still be reachable by readers from that epoch. Preemptible and software variants of read-copy-update (RCU) use reader-side per-CPU counters or related bookkeeping to determine whether any readers remain active.

Non-preemptible RCU can avoid such explicit reader announcements by preventing a read-side critical section from being preempted; the reclamation machinery instead waits for every relevant CPU to pass through a quiescent state, such as a context switch, transition to user mode, or entering idle state. In general, reclamation algorithms based on quiescent states don't need to announce that they're about to access a shared memory, and are therefore, at least to my knowledge, not relevant for W+RWC.

Here's a distilled example of the problem delegated hazard pointer implementations need to deal with:

// address = OLD_ADDRESS at the start

// P0 (Writer)
st.rel [address], NEW_ADDRESS
st.cmt [clean_up], OLD_ADDRESS

// P1 (Reader)
st.rlx [looking_at], OLD_ADDRESS
ld.cmt r1, [address] // sees OLD_ADDRESS
// Check if the value stored at looking_at matches the value in r1
// Success. Use the address and set looking_at = 0 at the end

// P2 (Garbage Collector)
ld.acq r2, [clean_up]   // sees OLD_ADDRESS
ld.rlx r3, [looking_at] // sees 0
// Concludes P1 can no longer see OLD_ADDRESS and frees the associated memory

The writer updates a shared pointer (address) and stores the old value in the clean_up variable, so a dedicated garbage collector can clean it up when the reader stops using it. The reader stores the old value in its looking_at variable, loads the value from the address variable, concludes that nothing's been updated because the two values match, so it continues to read from the pointer, setting looking_at to 0 when it's done. Meanwhile, the garbage collector sees that there's a new pointer to be cleaned up in the clean_up variable, checks to see if the reader is currently looking at it and concludes it's not because of a stale read. If the reader also read a stale value, the garbage collector may free the memory while the reader is still using it. Can this actually happen with the synchronization already in place?

Following the same strategy as the proof of the final version of RWC, P1's store to looking_at became globally visible before P0's store to address. The store to address became globally visible before the store to clean_up, because of the commit operation. It follows that the looking_at store became globally visible before the clean_up store, and since the corresponding load in P2 has acquire semantics, the follow-up load of looking_at can't be stale.

You might find it suspicious that we needed ld.rec for RWC, but not for W+RWC. The reason why is because the commit store takes care of the global visibility requirement. The correctness proof relies on the ordering between two independent writes, clean_up and looking_at, and the way we obtain the ordering is through the ld.cmt observation establishing a connection between P0 and P1.

A release instead of a commit store is not sufficient to provide any constraints on the ordering between the independent stores. A reconcile load in such an implementation would determine the point at which clean_up becomes globally visible, which implies the address store that precedes it is also globally visible. This is precisely what we need to establish a causal chain of events, because we know from ld.cmt that the store to looking_at became globally visible before the store to address, so the invalidation must be in P2's invalidation buffer by the time the reconcile load completes.

We've just proved that the following snippet is also a valid solution to the W+RWC problem:

// address = OLD_ADDRESS at the start

// P0 (Writer)
st.rel [address], NEW_ADDRESS
st.rel [clean_up], OLD_ADDRESS

// P1 (Reader)
st.rlx [looking_at], OLD_ADDRESS
ld.cmt r1, [address] // sees OLD_ADDRESS
// Check if the value stored at looking_at matches the value in r1
// Success. Use the address and set looking_at = 0 at the end

// P2 (Garbage Collector)
ld.rec r2, [clean_up]   // sees OLD_ADDRESS
ld.rlx r3, [looking_at] // sees 0
// Concludes P1 can no longer see OLD_ADDRESS and frees the associated memory

The second implementation is also more efficient, because the only reason why we're using a dedicated garbage collector is because we want the write to be as fast as possible, and a release store is less constraining compared to a commit store.

I call W+RWC delegated store buffering because an implementation that doesn't use a garbage collecting processor (thread) would need to load the value of looking_at after performing the store to check if it can free the old address, which turns into a Dekker-style store-load problem across two processors.

For comparison, the first implementation corresponds to the Power W+RWC+sync+addr+sync test, and the second implementation corresponds to W+RWC+lwsync+sync+sync; both implementations make the undesired outcome architecturally forbidden.

In the full implementation, P1 needs to read address with an acquire load to obtain the OLD_ADDRESS value before attempting to announce that it will be looking at it, and the acquire is there to ensure the data P0 wrote before publishing the new address with a release store is actually visible to P1. The commit load is only there to verify that the address itself didn't change between the two loads. This check-announce-check-again pattern is quite common in algorithms, so it's important to have efficient operations to support it.

If we turn the P0 commit store in the first solution into a release, and examine the outcome of the equivalent W+RWC+lwsync+addr+sync Power litmus test, we'd find that outcome is observable on Power 6 and 7, but not PowerG5. We can conclude that lwsync doesn't wait for global visibility of prior writes, which matches statements made in their manuals. This is a strong, though not conclusive, indication that Power implements asynchronous internal cumulativity at the very least.

10. Read Causality

If you stare at RWC and W+RWC long enough, you might notice a resemblance with D-WRC and I-WRC.

Suppose a variable x starts out with a value of 0, and processor P0 writes 1 to it. Another processor, P1, which reads 0 can conclude that its read must have happened before P1's write. However, if P1 performed a write of 1 to a variable y (which also equals 0 at the start) before initiating the load, we can't conclude that a third processor, P2, which observes the write of x will also observe the write of y, because those updates can arrive in any order at P2. However, if P2 waits for the write of y to be observable by P1, then the two loads form a causal link, which guarantees that if P1 observes the old value of x, and P2 observes the new value of x, then P2 is guaranteed to observe P1's y write.

In this way, the commit and reconcile loads form a pair similar to the release-acquire pair in WRC, except they establish causality not by reading the same value, but by reading an older and a newer value, respectively, in the modification order of the variable they use for synchronization. Although the mechanism is a little convoluted, the important part is that P1's prior write is guaranteed to become visible to P2's second read as long as P2's synchronizing read observes a store that P1 missed.

The primary difference between RWC and W+RWC is the fact that the synchronization variable is observed directly in the former, and indirectly, via a causal successor, in the latter. This is why I use D-RWC and I-RWC for RWC and W+RWC respectively. D-WRC and I-WRC follow the same pattern, except the direct and indirect observations concern data that's being propagated.

C++11 didn't ship with reconcile loads, commit loads, or reconcile and commit stores; RWC is allotted only a small paragraph in the Adve and Boehm paper, stating it's not clear the RWC outcome should be prohibited by default. This is rather unfortunate, since the RWC family shows up in practical algorithms all the time, and the language makes it impossible to implement efficient synchronization across all platforms, because it requires the programmer to use the blunt hammer of sequential consistency to repair causality. Above all, the missing operations make it difficult to recognize common patterns in parallel algorithms, which also impedes communication of intent, in code and writing, as well as education.

11. Coherence Causality

The external and internal cumulativity tests (D-WRC and I-WRC respectively) have two interesting analogues that involve coherence ordering, and it's worth examining those carefully, because maintaining cumulativity over coherence is necessary to fully recover the appearance of write atomicity when we need it.

11.1 External Coherence Cumulativity

We get DC-WRC ("C" for "Coherence"), when we replace the observation of the new flag value in P2 (via an acquire load) with a write to the flag variable that follows P1's write in modification order (mo), also called coherence order (co). This means that if we read the value of flag after the processors have successfully synchronized with an external observer, we'll see P2's value. We also need a st.rec to ensure proper handling of the invalidation buffer and local ordering:

// P0
st.rlx [data], 1

// P1
ld.rlx r1, [data] // reads 1
st.rel [flag], 1

// P2
st.rec [flag], 2 // succeeds P1 in co
ld.rlx r3, [data] // reads 0

// flag = 2 at the end

This outcome is impossible with the current implementation of external cumulativity, because the release write in P1 is only executed after P0's write is globally visible. This means that when P2's write successfully overtakes P1's, the invalidation should already be in P2's buffer, and the update at the end will ensure a stale value isn't read.

If P1 and P2 are hardware threads executing on the same processor, P2's flag update might overwrite P1's value in their shared write buffer, but, unless the implementation has parallel and completely unsynchronized loads for each thread, the new data should be available to P2, because of the shared cache. I'll cover load ordering in a later chapter, but, for now, you can assume P2's load can read a stale value, even if P1's load got the update.

As stated before, architecturally, we are allowing the flag write to become visible early, and potentially getting overwritten before the data invalidation reaches P2. We can also manifest this outcome by introducing a minor optimization that allows the write to silently complete locally without issuing any invalidations. This would speed up the arbitration part of the write operation, and introduce the problem of a non-silent write invalidating the silent one, and cancelling the visibility obligation. Arbitration communication need not even take place on the data channels used for invalidation, so P2 could easily complete its write before the P0 invalidation reaches it. The commit executed after the store in st.rec can't do anything about the arrival timing of P1's invalidation, and is only there to order the subsequent read - the acknowledgement from P1 might race the invalidation because it took a different route on the interconnect.

To prohibit this outcome, we'd need to replace the release store with a commit store, because the commit implementation is obligated to not make its write visible after all causally dependent writes are globally visible.

On a side note, following the load-load synchronization pairing from the previous section, this time we have a commit store synchronizing with a reconcile store via their coherence ordering to make sure the new data value is propagated to P2.

DC-WRC has the rather cryptic "WRW+WR" name in the literature, and the Power-specific mapping is WRW+WR+lwsync+sync. Interestingly, while the outcome is allowed, it's not actually observable on Power 6 and 7. This is not surprising once you consider the difficulty of making external cumulativity non-blocking. The interconnect might also be sufficiently ordered to prevent the invalidation-acknowledgement race. If you've got access to a modern Power implementation like 8, 9, or 10, and can run this particular test, I'd be curious to see what the results are!

The version of the test with st.cmt instead of st.rel corresponds to the Power WRW+WR+syncs, and, as expected, is also forbidden.

11.2 Internal Coherence Cumulativity

The IC-WRC test follows the same pattern, except this time we replace the P1 load in I-WRC with a store:

// P0
st.rlx [data], 1
st.rel [data_ready], 1

// P1
st.rlx [data_ready], 2 // succeeds P0 in co
st.rel [flag], 1

// P2
ld.acq r2, [flag] // reads 1
ld.rlx r3, [data] // reads 0

With the optimization from the previous subsection in place, this outcome is now possible if P0's early write is invalidated by P1's. It's also possible if P0 and P1 are actually hardware threads executing on the same processor, and thus sharing a write buffer (which won't be split as per our efficient data sharing between hardware threads requirement), though inheriting the causal obligation to propagate data before the flag to P2 is significantly easier in this case.

Replacing the release store in P0 with a commit one may prohibit the outcome, because by the time data_ready is observable, the data invalidation is already sitting in P2's invalidation buffer. However, consider what would happen if P0 and P1 are hardware threads on the same processor and P1's write overwrites P0's value in their shared store buffer. Should the release store inherit the obligation to propagate P0's write now? Such a demand would expand the responsibility for release stores, because now they need to propagate ordering over single-location writes as well, and only for corner cases like this.

One way to prevent this outcome is to halt execution in P0 until causally prior writes are complete, or have a separate buffer for commit stores, making sure they're carefully synchronized with the general write buffer, where P1's first write would be submitted. I don't think this additional complexity is worth it just to prevent coherence ordering issues, so the approach I'll take is to upgrade P1's release store to a commit, and pass the coherence ordering obligation onto it. A simple fix for the SMT scenario is to have the commit store wait for acknowledgement of all stores the core has issued before making it visible, though fine-grained tracking is also possible. Regardless, the following modification should be a solution to the problem:

// P0
st.rlx [data], 1
st.cmt [data_ready], 1

// P1
st.rlx [data_ready], 2 // succeeds P0 in co
st.cmt [flag], 1

// P2
ld.acq r2, [flag] // reads 1
ld.rlx r3, [data] // reads 0

What if we upgrade P2's acquire read to a reconcile? Waiting until the release store is globally complete is the same as waiting for its causal predecessor to be globally complete, and that means that, by the time the reconcile completes, P0 has seen the data_ready update, and for data_ready = 2 to succeed data_ready = 1 in modification order, the data update must already be globally visible, and that would be the case if P0's data_ready update is a commit; remember, commit stores, unlike release ones, are obligated to make their associated writes visible after the causal predecessors are globally visible. This gives us another solution to the problem:

// P0
st.rlx [data], 1
st.cmt [data_ready], 1

// P1
st.rlx [data_ready], 2 // succeeds P0 in co
st.rel [flag], 1

// P2
ld.rec r2, [flag] // reads 1
ld.rlx r3, [data] // has to read 1

Notice how the causal chain between the commit store and reconcile load is propagated by the ordinary release to ensure the data payload is delivered, whereas, in the previous solution, the two commits are sufficient to deliver the data via an ordinary acquire load. As I'll demonstrate throughout this series, this subtle interplay between coherence and write causality is one of the reasons why the informal specification of the C++ memory model struggles so much with how rules are communicated, and why efficient implementation of the rules on real hardware is constantly running into problems.

IC-WRC is usually called Z6.3 in memory models literature, and, as expected, the Power mapping equivalent to the presented snippet is allowed and reproduces the undesirable outcome on Power 6, and 7 (Z6.3+lwsync+lwsync+addr), as well as Power 8 (Z6.3+pooncerelease+pooncerelease+poacquireonce using the Linux Kernel Memory Model naming convention). Once again, I couldn't find out if this outcome is observable on Power with SMT disabled. The double commit and commit plus reconcile scenarios correspond to Z6.3+sync+sync+addr and Z6.3+sync+lwsync+sync respectively, and both of them are architecturally forbidden.

C++11 doesn't require release operations to maintain cumulativity when it comes to coherence ordering, and we managed to take advantage of this laxness to implement additional optimizations. In Part 2 we'll see how the same issues can materialize even when hardware multithreading isn't involved.

12. Sequential Consistency

You may have noticed that, by now, we've implemented functionality to cancel out almost all ordering side effects caused by local execution reordering, early reads, and invalidation buffering. Reconcile loads prohibit early reads, stops later reads and writes from executing, and the update afterwards makes sure the invalidation buffer doesn't contain any pending invalidations, so the subsequent reads are up-to-date. Commit stores prohibit prior reads and writes from being reordered past them, both locally and globally, in addition to closing off coherence side channels that can expose the lack of write atomicity. The only problem that's left is to close off the store-followed-by-a-load case, which is trivial if we insert a commit;update pseudo-instruction in between them. Once we have that, we'll basically achieving both write atomicity, and strict program order execution, which means executing the instructions in the order they were written.

We can create a new set of sequential consistency loads and stores (.sqc), which, at least for now, will behave like reconcile and commit respectively, except, when a st.sqc is issued, it sets a "pending-serialization" flag, which will be cleared by issuing a commit; update the next time a ld.sqc is executed - commit stores and acquire loads could also clear each of the serialization requirements independently. Similarly to reconcile stores and commit loads, the commit part need only wait for the last SC store, and the update should only make sure there's no invalidation for the load's cache line waiting in the invalidation buffer, and apply it if there is one.

If we turned all loads and stores in our programs into SC ones, we'd effectively restore write atomicity and program order. Obviously that's complete overkill, but as soon as you allow other instructions, like regular loads and stores, you create the possibility of a side channel of communication exposing the architectural lack of write atomicity. An important realization is that this side channel is only opened when regular loads and stores are performed without appropriate synchronization (a data race), so you could mandate that the new set of instructions, together with regular loads and stores, achieve sequential consistency in the absence of data races, or SC+DRF, where "DRF" stands for "Data Race Free". In other words, the DRF part ensures the illusion of write atomicity and program order for SC atomic operations is maintained.

This is quite an attractive model, because the acquire and release semantics built into the SC atomics allow you to create all essential synchronization primitives. The model is also simple to reason about, because programmers can visualize the execution of atomic operations across different processors as a simple interleaving of the instructions they wrote in code. Likewise, proofs and automated verification are straightforward, because they can be modelled with state machines, so reachability of undesired states is a decidable problem.

I'd say SC+DRF is a great model for any language that seeks to expose a simple set of atomic primitives to programmers, and it's a particularly good choice for languages with automatic memory management. This is likely why Java and Go adopted this model, and why computer architectures should have an efficient toolkit for supporting sequential consistency.

12.1 Total Order

If you look at the C++ documentation, you'll find the following definition of sequentially-consistent atomic operations:

Atomic operations tagged memory_order_seq_cst not only order memory the same way as release/acquire ordering (everything that happened-before a store in one thread becomes a visible side effect in the thread that did a load), but also establish a single total modification order of all atomic operations that are so tagged.

I won't get into a mathematical presentation of order theory right now, but, for programmers who are familiar with the language of directed graphs, a total order can be visualized as a sequential chain of nodes with directed edges, while a partial order is a more general directed acyclic graph:

You might think that write atomicity and program order can't possibly achieve a total order across multiple locations, because there's no serialization point anywhere in the system. The reason why that assumption is wrong is because requiring a total order is an unnecessarily strict condition. As long as the operations form a directed acyclic graph, you can topologically sort them into a total order. The topological sorting algorithm serves as a constructive proof of the fact that any finite partial order has a linear extension.

To understand why write atomicity is a prerequisite for acyclicity, you can start by turning memory operations for a single location into a graph:

Reads (R) and writes (W) are represented by function-like notation, where the first argument is the processor, the second is the variable name, and the last is the value read or written - I may omit the processor if it can be inferred from context. Edges between same-location writes are called coherence order (co), or modification order (mo) relations in the formal modelling literature. Edges connecting a write to a read that observes it are called reads-from (rf). Program order edges are typically labelled po or sequenced-before (sb). The most interesting type of edge is reads-before (rb), which is typically called from-reads (fr), though I refuse to use such a terrible name; it connects a read of a prior value to a write that follows the value in modification order. It can formally be specified as going backwards from a read node across an rf edge, and then following the write in modification order to establish an edge between the read and the subsequent write. Formal models literature would also distinguish internal and external operations with an "i" and "e" prefix or suffix, such as "eco", or "rfi". I won't be doing that for now.

As you can see, write atomicity gives us a well-defined cutoff, and past that point the old value is no longer observable by any load.

An execution is called sequentially consistent when the graph formed by all mo, rf, rb, and sb edges is acyclic. Throughout this series, I'll explore this graph-based dataflow analysis in the context of proving correctness and formal modelling.

12.2 Causal Transitivity

But why does write atomicity and program order result in sequentially consistent execution? Feel free to skip this section if you don't care, because I'm about to get a bit more formal.

The per-location graph makes the partial order for each memory location obvious, but, unfortunately, it doesn't provide any insight on how to combine two or more locations into a DAG. A crucial insight is that any cycle which respects the coherence rules of individual memory locations must span multiple locations. Such a cycle necessarily involves at least two writes, including initialization writes. This matters because if we can establish a causal dependency between writes, then every impossible execution can be reduced to a cycle in the write dependency graph, which can't happen unless we've violated causality - that is, unless we have a write causally depend on itself. I call the proof technique I'm going to use causal read projection (CRP), because I'll systematically enumerate all the ways in which two operations sequenced by the same processor create causal dependencies when we project reads onto their causally-dependent writes.

First, the 3 obvious causal dependencies that apply per-location are rf (a read which observes a write), rb (a write that happened after a previous observation), and mo (direct modification order) edges.

I'll denote a read or write event for location x with E(x), with W(x) being a write, and R(y) being a read. An event E(x) connected to an event E(y) by one of the aforementioned edges will be denoted E(x); <edge-type>; E(y), and the starting point for the proof is to considering all pairs of operations that are sequenced before each other: E(x); sb; E(y)

We've got 4 possibilities here: A write followed by a write (WW), a read followed by a write (RW), a write followed by a read (WR), and, finally, the most interesting one: a read followed by a read (RR). Let's carefully examine each one, and how it contributes to establishing a partial order between writes. From now on, I'll use global visibility to reason about causal dependencies.

WW, or W(x); sb; W(y), is the most trivial scenario, because we publish the writes in order, so W(x) became visible before W(y), which I'll denote W(x) < W(y).

The R(x); sb; W(y) RW scenario is also straightforward: Observing a value via a read implies that the corresponding write is already globally visible, and since we publish a write after the read, we can establish that the observed write is globally visible before the second, or W(x) < W(y). The full expression is W(x); rf; R(x); sb; W(y), and if we strip away the events to only highlight the edges, we get our first edge pattern: rf; sb. In this case, we've projected a read sequenced before a write onto the write from which it obtained its value.

A write followed by a read (WR) W(x); sb; R(y) is a little more tricky, because we have to reason about any modification order successor W'(y) of the W(y) write observed by the read. We can write that as W(x); sb; R(y); rb; W'(y), or just sb; rb. Processing the invalidation buffer after W(x) is critical for this relation to hold, because we want to use the read of y as a negative observation. Completion of the x read is evidence that its corresponding write is globally visible, and an observation of the old value of y after that point is evidence that the subsequent write is not globally visible yet. Global visibility here is used to establish causal dependence, so we can conclude that W(x) < W'(y). This is the P1 store buffering issue I covered in the context of RWC, and its corresponding pattern is sb; rb.

The last remaining scenario to address is RR, or R(x); sb; R(y), and the strategy for it is a combination of RW and WR: W(x); rf; R(x); sb; R(y); rb; W'(y), which implies that W(x) < W'(y). RR corresponds to the rf; sb; rb pattern, and it should be familiar from the P2 early visibility problem in RWC. Processing the invalidation buffer after R(x) is critical for the same reason as the store buffering case.

The edge patterns correspond to a notion of causal transitivity for write events, and can be used to iteratively construct a partial order; we can summarize all of them using the following pattern matching rule: rf?; sb; rb?, where the ? syntax is inspired by regular expression (regex) syntax and means "zero or one occurrences".

If we add mo to the pattern, we get mo | (rf?; sb; rb?), and we can apply this pattern expression repeatedly to establish causal dependencies between writes. The | syntax is also inspired by regex, and it means "the expression on the left side, or the expression on the right side", transitively. Note that rf; rb is subsumed by mo, so it's implicitly contained in the pattern. Taking into account the fact that we're constraining the end points to be writes, we get the final pattern:

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

We have established a projected write-to-write constraint for every program-order bridge that can participate in a cycle. Taking the union of those constraints with modification order gives a global partial order over all writes; causally unrelated writes remain incomparable.

The exhaustive nature of the pattern expression makes it obvious why a cycle in the execution graph, G, would produce a cycle in the write causality graph, K. Suppose G does contain a cycle, and consider every pair of writes in the cycle with no other writes in between. Only the starting edge after the first write can be rf, and only the last edge (before the last write) can be rb. Anything in between could only be sb, and those are transitive, so we can collapse the chain of sb edges into a single edge. Now we're left with either rf; sb; rb or rf; rb, and since the latter collapses to mo, the entire path corresponds to the edge between the writes in K. This means the entire cycle can be mapped onto a cycle in K, which is acyclic by definition, so we get a contradiction. This concludes the proof.

12.3 Global Commit

Reasoning about global visibility is one way to establish causal dependencies, and it's a natural extension of the architecture I've been developing. However, it's an unnecessarily strong condition. Imagine an architecture where all writes are sent to a central arbiter (server), and the arbiter broadcasts the order it has decided on to each processor. Such an implementation achieves an actual total order, but observing a write doesn't mean the list entry has propagated to all other processors, which would imply the write is globally visible.

The two architectures are, in some sense, duals of each other, because the implementation we've been discussing propagates invalidations first, and a global commit point is established after they're acknowledged, so it follows a propagate -> commit (PC) protocol (PCP). The server architecture, on the other hand, can be described as a commit -> propagate (CP) protocol (CPP), because it commits the stores first, and then propagates the established order asynchronously.

Because CPP is sufficient to establish a total order, it's usually seen as the natural way to define sequential consistency. PCP, on the other hand, provides an excellent foundation for synchronizing other atomic operations. Importantly, both can provide an implementation of sequential consistency. I'll demonstrate how to combine the two approaches in Part 2.

Fow now, it's important to recognize that, in PCP, global visibility implies global commit, which is not true in CPP. The following section will cover the details of how a PCP system can implement sequential consistency.

12.4 Read Optimization

Given the usefulness of sequential consistency, it's important to consider various implementation strategies, and how the ISA would be implemented by physical chips that only support simple commit; update instructions, like the serialization fences I'll discuss later - I'll refer to such instructions as serialize from now on. Such an implementation has a very limited choice when it comes to supporting SC atomic operations, assuming it can't provide conditional execution of serialize instructions. SC loads in such an implementation could be implemented as ld.rlx; serialize, and the SC store would then need to be serialize; st.rlx; serialize. The serialize instruction after the relaxed store could also be moved before the load. Regardless of the choice, two consecutive loads or stores will be executing one redundant serialize. The architecture could fuse those instructions, though other operations being executed in between could make this more cumbersome.

It would be nice to get rid of one of those serializations, and we can do this by recognizing that a reconcile operation is actually unnecessarily strict for what we need. The commit part of reconcile is there to order subsequent atomic reads, but an SC load doesn't need to care about ordering any atomics besides other SC loads. A commit store would already ensure the writes corresponding to prior loads, including the SC one, are globally complete anyway. This means we can change the SC load mapping to a commit; update; ld.rlx; update, while the store could stay the same. More importantly, as long as an implementation can provide an efficient equivalent of update, the mapping could remove a serialize by mapping SC loads to serialize; ld.rlx; update and SC stores to serialize; st.rlx.

The recommended C++11 compiler mappings for ARMv7 and Power are an interesting demonstration of this optimization. The ARMv7 mappings follow the triple-serialization idea discussed earlier. A dmb ish is the equivalent of serialize, and the mappings use ldr; dmb ish for SC loads, and dmb ish; str; dmb ish for stores. The authors of the mappings believed ARM's equivalent to an update, which is teq; beq; isb, is not efficient enough to justify removing a serialization. On the other hand, the Power mapping does take advantage of the optimization I discussed, and uses hwsync; ld; cmp; bc; isync for SC loads, and hwsync; st for SC stores, where hwsync is equivalent to serialize and cmp; bc; isync is the equivalent to update (Power doesn't expose the side effects of its invalidation buffering to the programmer).

We can try to take advantage of the same optimization architecturally by removing the commit from ld.sqc, and checking if prior .sqc loads are complete before issuing another SC load; the processor can perform a commit conditionally if the corresponding write is still not globally visible. However, the problem is that we now need to execute, at a minimum, a targeted update (waiting until a pending invalidation for the load itself is processed, if on exists) before each SC load, because we don't know when the prior load completed. Whether this additional complexity is beneficial or not depends entirely on the code that's being executed, but it reveals the relative weakness of ld.sqc compared to ld.rec, so we'll do it to be maximally permissive.

Consider what a correctly synchronized RWC would look like using SC instructions:

// P0 (Consumer)
st.rel [tail], 1 // advance the tail

// P1 (Producer)
st.sqc [head], 1  // decrement the head
ld.sqc r1, [tail] // reads 0
// head - tail = 1

// P2 (Consumer)
ld.sqc r2, [tail] // reads 1
ld.sqc r3, [head] // reads 2
// head - tail = 1

Notice how the once minimal and efficient solution is now riddled with SC instructions, because we don't know where the commit; update sequence would be inserted in a physical implementation. This awkwardness is not even the major issue with sequential consistency in the presence of weaker atomic operations.

12.5 Shattering the Illusion

I mentioned the danger of side channels of communication exposing the true nature of the underlying architecture, and, while we can claim side channels opened by data races are the fault of the programmer, other, less restrictive, atomic operations can open the same channels, and those operations, by definition, allow for unsynchronized access.

Consider I-RWC implemented with the following synchronizations:

// address = OLD_ADDRESS, looking_at = 0 at the start

// P0 (Writer)
st.sqc [address], NEW_ADDRESS
st.rel [clean_up], OLD_ADDRESS

// P1 (Reader)
st.sqc [looking_at], OLD_ADDRESS
ld.sqc r1, [address] // sees OLD_ADDRESS
// Check if the value stored at looking_at matches the value in r1
// Success. Use the address and set looking_at = 0 at the end

// P2 (Garbage Collector)
ld.acq r2, [clean_up]   // sees OLD_ADDRESS
ld.sqc r3, [looking_at] // sees 0
// Concludes P1 can no longer see OLD_ADDRESS and frees the associated memory

P2's synchronization is obviously not going to work, because the ld.sqc only has acquire semantics, and we can't trust that an implementation will issue a commit; update before each SC load. However, all accesses of address and looking_at are marked with .sqc, so, if we follow the C++11 formulation, there should be a total order for those operations. And yet, if you graph all operations (in a simplified form), you'll find a cycle in the execution graph:

Relaxed atomics can also expose the illusion when taking advantage of store-to-load forwarding, the optimization that separates MCA from other-MCA:

// P0
st.sqc [x], 1
st.sqc [y], 2
ld.rlx r0, [y] // reads 1

// P1
st.sqc [y],1
st.sqc [x], 2
ld.rlx r1, [x] // reads 1

The cycle should be obvious if you examine the pseudo-instructions involved:

commit
st.rlx [y], 2
ld.rlx r0, [y]

There's no commit in between the two operations to prevent the load of y from being satisfied directly from the local write buffer. This litmus test is called 2+2W or WW+WW in the literature, though I prefer to call it SLF2, for "Store-to-Load Forwarding with 2 Writes". SLF1 is an alternative with only 1 write:

// P0
st.rel [x], 1
ld.sqc r0, [x] // reads 1
ld.sqc r1, [y] // reads 0

// P1
st.rel [y], 1
ld.sqc r2, [y] // reads 1
ld.sqc r3, [x] // reads 0

Once again, the first load in each processor is immediately satisfied from the local write buffer, and the update from the other processor is missed, creating a cycle in the execution graph, even though all the loads are sequentially consistent. SLF1 is also called SB+rfis in the literature, and stands for store buffering with multiple reads-from-internal edges, which correspond to the store-to-load forwarding I've been discussing. You might be surprised to hear that C++20 forbids this outcome, which is considered a defect in the standard. This is also the context for the Boehm quote at the beginning of the article.

You can go through all prior litmus tests I've discussed, as well as variations on the problems they highlight, to synthesize other examples where the partial order of SC operations participates in an overall cycle when weaker operations are included.

12.6 The Fundamental Problem

As you can see, defining sequential consistency in terms of a total or partial order within a framework that also permits less strict (weaker) atomic operations is a difficult task, especially when you allow those operations to connect otherwise separate SC graph clusters. C++11 attempted to define how release-acquire atomics can establish ordering between SC operations that are causally connected through a chain of weaker operations, which was proven unsound for Power mappings by Lahav et al. in the aforementioned 2017 "Repairing Sequential Consistency in C/C++11" paper. The 2016 paper by Batty et al. correctly recognizes that a partial order is sufficient for achieving sequential consistency, though it has similar issues as C++11, which Lahav et al. pointed out.

C++20 attempted to translate Lahav et al.'s work to the quasi-formal language of the C++ standard, though it kept the idea of a total order. However, the new strong-happens-before semantics are both cryptic and flawed, as they make correct hardware mappings highly inefficient. I won't get into the specifics of the C++11 and 20 models until I discuss formal modelling in a future article. Part 2 will be a stepping stone towards that, because it will cover other issues with the language rules.

What I will say is that I believe the weakness of SC loads, at least compared to reconcile ones, as well as the lack of commit loads and reconcile stores, make sequential consistency a highly cumbersome and inefficient tool for more advanced algorithms, where ordering of non-SC atomic operations is required - yet it's all languages based on the C++ memory models currently provide.

It may be tempting to assume that the implementation of SC atomics would be very similar to the implementation of commit-reconcile atomics, and I certainly wouldn't blame if you that's your takeaway from reading this section, because it's possible to implement sequential consistency with commit-reconcile operations, and it may even be desirable on a lot of platforms (for example, ARMv7 SC loads work like reconcile loads). However, Part 2 will introduce a synchronization framework which makes it clear that the two could have very different underlying behaviour, and SC atomics shouldn't be tied to "global visibility" definitions.

The C++ memory model architects have a genuinely difficult task on their hands, especially when programming language semantics are mixed in. Moreover, it's hard to create useful abstractions without a solid understanding of the underlying machine, which is why I consider that the main contribution of this series.

13. Special Loads

There are several common patterns in parallel algorithms that come up often enough to justify additional hardware support. I'll explore two of them, and discuss how the current instruction set is unable to provide an efficient implementation.

13.1 Consume Semantics

The first pattern is publishing an update via a pointer swap, which is common in algorithms that don't rely on mutual exclusion to achieve synchronization. The entire purpose of the Linux kernel RCU implementation is to provide an efficient and safe way of doing these kinds of updates, but the architecture we've designed requires acquire semantics to ensure the data changes are propagated to whoever sees the pointer update. Issuing an acquire load will trigger a stall until all snapshotted invalidation are processed, but we may only care about a handful of those, especially in a system with a lot of hardware threads that are accessing shared memory. Ideally, we'd want an operation, which is typically called consume (abbreviated .cns) that tracks all loads whose address is computed based on the pointer address we're synchronizing on, and wait only for those invalidations instead of the entire snapshot. If this is too difficult to track architecturally, the processor could enter a mode where the addresses of subsequent loads are checked against the snapshot and stalling if an entry matches. This mode can be exited automatically when all entries in the snapshot are processed.

Consume semantics could also be seen as anti-pessimization technique, which means the implementation can treat it as an acquire operation if address dependencies aren't respected by the platform. This is the case in the LKMM, with its smp_read_barrier_depends(), because, historically, it had to support the infamous DEC Alpha, which didn't hide its unordered invalidation buffers from the user:

Although it is legal C11 to say “atomic_thread_fence(memory_order_consume)”, all known C11 implementations promote this to an acquire fence. Within the Linux kernel, this would have the undesirable effect of promoting rcu_dereference() to acquire as well. Linux therefore needs to continue defining smp_read_barrier_depends() as smp_mb() on DEC Alpha and nothingness elsewhere.

This promotion of consume operations to acquire ones by compilers is a language problem that I'll discuss later in the series, but, suffice it to say that aggressive compiler optimizations cause all kinds of headaches when it comes to establishing an efficient memory model. We won't be worrying about that yet.

Consume semantics are the brain child of Paul E. McKenney, and that's not surprising given the fact he also introduced the RCU mechanism Linux relies on, and is one of the chief architect of both the Linux Kernel Memory Model (LKMM), and the C++ memory model.

13.2 Verify Semantics

Speaking of Linux, and operating systems in general, a common way to publish updates, without potentially stalling the writer, is to issue speculative, racy, reads, and have a mechanism to detect when those reads raced with a writer, so they can be discarded.

This is the idea behind sequence locks, which I mentioned before. The writer in the typical sequence lock implementation increments the seqlock synchronization variable to an odd value to indicate it's performing an update, and then increments it again with a release store, making the value even, to signal a completed update. A reader can issue an acquire read on seqlock to get the potentially incomplete data updates, and if it observes an even value, it may assume there's no ongoing write and speculatively read the data. The core problem with this algorithm is that a write may begin at the same time, and the invalidation for the synchronization variable could get stuck in the reader's invalidation queue. If the reader completes its speculative reads and issues a load of seqlockt hat hits a stale cache copy, it may assume the variable didn't change, so it didn't race with a writer.

With the current instruction set, a commit load can provide the necessary behaviour, because it will ensure prior writes aren't completed after the lock read, and it will also make sure the load itself checks the invalidation buffer for its address before completing. However, the commit part of operation is entirely unnecessary.

It's therefore useful to define a verify load, ld.vfy, which waits for prior loads to obtain their values, then searches for the corresponding address in the IB, and, if it finds it, it stall until that entry is processed before completing.

14. Same-Location Causality

When I first learned about cache coherence protocols, I was very puzzled why you'd need relaxed atomics in the first place. Isn't the reader-writer lock supposed to guarantee that there will be no funny business with same-location ordering of operations?

The answer has to do with the difficulty of enforcing ordering of two consecutive loads on the same processor, especially in the context of pointer aliasing. You may have realized this already, but two consecutive loads are a staple in litmus tests because they act as external observers of write events.

Imagine a scenario where the same address (pointer) is stored in two different variables (ptr0 and ptr1), and one processor dereferences the two pointers in order, while another updates the location the pointers alias:

// P0
ld r0, [ptr0]
ld r1, [r0] // reads 1

ld r2, [ptr1]
ld r3, [r2] // reads 0

// P1
ld r4, [ptr0]
st [r4], 1

What sequence of events could lead to this outcome? Since parallel access is involved, the first problem you should suspect is the pointers residing in two different cache lines. Since, as far as the processor is concerned, there's no ordering that needs to be enforced between two independent locations, the line for ptr0 might not be present in the cache, or got evicted due to a conflict, so the pointer load and the load that depends on it get stalled. Meanwhile, the line for ptr1 is in the cache line, so it immediately completes. The last load is then free to observe the old value of the variable. Meanwhile, P1's invalidation reaches P0 and gets processed immediately. By the time the cache line for ptr0 is retrieved, the variable it points to has changed, so it returns new value.

CPUs have sophisticated memory ordering buffers (MOB) that resolve these types of conflicts, but an architecture might want to dispense with the complexity and not enforce the needed synchronization because it wants to, for example, serve loads in parallel. This was probably the case for Itanium (unconfirmed), which featured out of order execution of VLIW instruction bundles. The Itanium Processor Microarchitecture states:

"Reservation stations, reorder buffers, and memory ordering buffers are all replaced by simpler hardware for speculation."

The IA-64 developer's manual, which I referenced before, is also very explicit about this lack of ordering enforcement:

The dependency rules define the relationship between memory operations that access the same address. Specifically, the IA-64 architecture resolves read-after-write (RAW), write-after-read (WAR), and write-after-write (WAW) dependencies through memory in program order on the local processor.

Note the missing read-after-read (RAR) dependency, which C++11 requires for relaxed atomics. Itanium likely submitted its atomic requests to a separate unit, which did have the more complicated dependency enforcement. Although it took a long time for the Itanium mappings to be corrected, acquire loads were used instead of plain loads from the very beginning, and, as far as I know, Itanium was the only architecture at the time which exhibited this behaviour. This is why a separate relaxed atomic type was needed.

However, missing hardware features aren't the only reason to have an atomic type. Sometimes there are hardware bugs which need to be corrected after a lot of software is already written.

The seminal 2013 Herding Cats - Modelling, simulation, testing, and data-mining for weak memory paper, which is a highly recommended read for anyone interested in memory models, uncovered a lot of same-location load-load (load-load coherence) bugs:

Amongst the tests we have ran on ARM hardware, some unveiled a load-load hazard bug in the coherence mechanism of all machines. This bug is a violation of the coRR pattern shown in Sec. 4, and was later acknowledged as such by ARM, in the context of Cortex-A9 cores, in the note [arm 2011].10 Amongst the machines that we have tested, this note applies directly to Tegra 2 and 3, A5X, Exynos 4412. Additionally Qualcomm’s APQ8060 is supposed to have many architectural similarities with the ARM Cortex-A9, thus we believe that the note might apply to APQ8060 as well. Morever we have observed load-load hazards anomalies on cortex-A15 based systems (Exynos 5250 and 5410), on the cortex-A15 compatible Apple “Swift” (A6X) and on the Krait-based APQ8064, although much less often than on cortex-A9 based systems.

In the Cortex-A9 MPCore(TM) Programmer Advice Notice Read-after-Read Hazards, ARM recommended the following fix:

The workaround is to intercept all volatile memory reads in the compiler and issue a DMB instruction immediately afterwards. This ensures that all such accesses are ordered correctly.

The associated 761319: Ordering of Read Accesses to the Same Memory Location Might Be Uncertain errata states that the issue was caused by "some internal replay path mechanisms".

What we can infer from this statement is that if, for some microarchitectural reason, a load fails to complete, it may be sent around a "replay" path and tried again later. This, in effect, could produce the same aliasing race, but without even involving pointers.

Though not directly related, the Arm Cortex-A510 Core errata contain a number of race conditions involving operations by the same processors failing to enforce ordering because of a concurrent write, such as "2218950 Aliased loads and stores might cause an ordering violation", "1976290 A Tag Checked load might forward incorrect data", and "2230537 Load following SVE predicated load/store might cause ordering violation". As you can see, even if the cache coherence protocol functions as a reader-writer lock, it's still possible to have ordering violations.

On a side note, ARM's recommendation to change volatile mappings to preserve load-load coherence isn't unique. Compilers which support Itanium do the same. For example, gcc treats volatile accesses as relaxed atomics and issues ld.acq and st.rel respectively for them (Itanium doesn't have a dedicated relaxed atomic operation):

/* Unless the memory model is relaxed, we want to emit ld.acq, which
    will happen automatically for volatile memories.  */

/* Unless the memory model is relaxed, we want to emit st.rel, which
    will happen automatically for volatile memories.  */

Testing done by PostgreSQL developers revealed the Intel icc compiler does the same, even though the manual states the serialize-volatile option is turned off by default.

All of this is to say that, despite what language lawyers may argue, volatile very much is treated as a relaxed atomic operation by compiler developers, because they have a lot of legacy code to support, which had to be written before atomics were introduced. Linux kernel code, for example, wraps its volatile accesses with READ_ONCE and WRITE_ONCE macros.

15. AI Disclosure

GPT-5.6 Sol was used as a research assistant for this article. It dug up and summarized relevant references for me, so I could evaluate whether it's worth my time to read them. I didn't let it do any of the idea and visualization generation, writing, or proof reading, because its writing style doesn't suit me, and I can't be asked to go through mountains of feedback that I'm going to mostly ignore, so you'll have to bear with any grammar and punctuation mistakes. Above all, letting it do all the work decreases my sense of ownership, and thus motivation to work on articles.

16. Conclusion

I've now introduced all major ideas, and will continue to build upon them in follow-up articles. Read-modify-write operations require dedicated treatment in the context of the synchronization framework I'll introduce in Part 2, so they didn't make the cut for this introduction; same for fences and local dependencies.