Dependencies, RCsc, and RCpc Acquire on ARMv8

A pointer chase on ARMv8 needs no barrier. If a thread loads a pointer with an ordinary LDR and then dereferences it with another LDR, the two loads cannot be reordered, because the address of the second depends on the value of the first. The hardware must wait for the first load to complete before it can issue the second. This dependency is free ordering, and it is the basis of the read-copy-update idiom that dominates the Linux kernel on weakly ordered machines.

Dependencies are one of three ordering mechanisms the architecture provides, and they are the cheapest. The other two are the load-acquire and store-release instructions, which come in two strengths, and the barrier instructions. Choosing among them is a question about which observers need to see the order, and the answer changed when ARMv8.3 added a weaker acquire.

Three kinds of dependency

The architecture recognises several dependency relations, and each orders a different pair of accesses.

Address dependency. A load’s address is computed from the result of an earlier load. The second load cannot issue before the first returns, so the two are ordered. This is the pointer-chase case and the one RCU relies on.

Data dependency. A load’s value is computed from the result of an earlier load, or a store’s data is. The dependent access cannot compute its value before the first returns, so the order is enforced by dataflow rather than by a barrier.

Control dependency. A conditional branch tests the result of a load, and the instructions on the taken path are ordered after the load. This one is the weakest and the most fragile: it exists in the architecture, it is easy for a compiler to destroy, and the specification’s treatment of it is narrower than most programmers assume.

The formal models define dependency on the instruction sequence, not on the runtime value. A load whose address is computed as the result of a previous load plus zero is still an address dependency in the model, even though the arithmetic is trivial. The converse matters more: a compiler that folds the addition away destroys the dependency, and the ordering with it. Dependency ordering is therefore a compiler property before it is a hardware one. The hardware honours dependencies present in the machine code; the compiler decides whether they are present at all.

What load-acquire and store-release order

STLR is the store-release form and LDAR the load-acquire form. In the base ARMv8 architecture these have RCsc semantics — release consistency with sequentially consistent acquire and release — and the property that makes them strong is cumulativity. A STLR ensures that every memory access before it is observed before the store itself is observed, and that this ordering holds for all observers, not just for the thread that issued the store. An LDAR does the mirror: every access after it is observed after the load, again cumulatively. Neither instruction orders accesses on the far side of itself.

Base ARMv8 is also multi-copy atomic: a store becomes visible to all observers at a single point, rather than at different times for different observers. That property is what allows the simple mental model in which there is a single order of writes, and it is what the Pulte et al. model of the architecture establishes. The weaker, non-multi-copy-atomic machines that earlier ARM and Power implementations resembled are a different case, and conflating them leads to fences that are stronger than necessary on ARMv8 and reasoning that does not transfer.

A message-passing test makes the strength concrete. Thread 0 writes a data field, then release-stores a flag. Thread 1 acquire-loads the flag and then reads the data field.

// P0: data at X2, flag at X1    | P1: flag at X1, data at X2
MOV  W0, #1                     | LDAR W0, [X1]    // load flag
STR  W0, [X2]     // data = 1    | LDR  W1, [X2]    // read data
STLR W0, [X1]     // flag = 1    |

The outcome in which thread 1 reads the flag as set but the data as stale is forbidden. The STLR makes the data store visible before the flag to every observer, and the LDAR prevents the data read from moving above the flag read. Both halves are needed; either alone leaves a hole.

The second acquire, and why it is cheaper

ARMv8.3 introduced LDAPR, a load-acquire with RCpc semantics — the “pc” standing for processor consistency, the weaker of the two release-consistency variants. LDAPR still orders the load against subsequent accesses, but the order is not cumulative in the same way: it constrains the reading thread’s own subsequent accesses and does not establish the same globally visible ordering that LDAR does for a third observer.

The concrete difference appears when an acquire load is followed by a store to a different location and a third thread observes both. With LDAR, the acquire’s ordering is visible system-wide, so the third thread’s observations are constrained. With LDAPR, they are not: the later store can become visible to the third thread before the acquire’s ordering point, so the third thread may see the store without seeing the value the acquire read.

The gain is that LDAPR need not wait for the acquire’s ordering to propagate to other observers, which on a large system means it need not reach a coherence point. It can be satisfied locally at the core. The instruction exists because a class of patterns — reference counting, some RCU uses, sequences where the acquire is not publishing to a third party — do not need the cumulative property, and paying for it is wasted latency.

Choosing between them is not a matter of taste. A pattern in which the acquire load is followed by a store that another thread will read, and in which that other thread’s ordering depends on the acquire, requires LDAR. A pattern in which the acquire only protects accesses by the acquiring thread can use LDAPR. Getting this wrong produces code that is correct on a machine with LDAR-strength acquires and wrong after an optimisation that substitutes the weaker instruction.

Barriers and shareability domains

DMB SY orders all memory accesses before it against all accesses after it, for all observers in the system. DMB ISH does the same within the inner-shareable domain, which covers the cores that share a cache-coherence domain and excludes devices. The choice is about which observers must see the order: a driver sharing memory with a device needs the wider domain, and threads that share only with other threads in the same cluster can use the narrower one.

DSB differs from DMB in that it waits for the ordered accesses to complete rather than merely ordering them. It is used where the code needs the accesses to have actually reached the point of coherence — before a cache maintenance operation, or before a store that turns a page table entry live — rather than merely to be ordered.

Barrier bugs are hard to find by inspection because the failure is usually not a missing instruction but a wrong domain or a wrong barrier type for the direction needed. DMB ISHLD waits only for prior loads to complete, DMB ISHST only for prior stores, and using a full DMB where a directional one suffices costs more than the code needs.

Where dependencies are not enough

Dependencies order a load against an access that uses its result. They do not order a load against a store that does not use the result, and they do not order two independent loads. The RCU pattern works because the reader’s chain of pointer dereferences is genuinely dependent; a reader that loads a pointer and then reads an unrelated global is not protected by the dependency.

Dependencies also do not survive the compiler without help. The Linux kernel’s rcu_dereference and its dependency annotations exist precisely to tell the compiler that a dependency must be preserved, and the READ_ONCE family prevents the compiler from inventing or eliminating loads. A compiler that proves the dependent value is constant, or that re-associates the address arithmetic, is free to emit code in which the dependency no longer exists, and the hardware guarantee evaporates with it.

Control dependencies are the sharpest case. The architecture’s guarantee for them is narrow — it covers the ordering of accesses on the path taken, and the formal models describe exactly which instructions the dependency must pass through. A conditional whose branch was converted to a conditional move has no control dependency at all, and a branch whose condition was hoisted has lost the load-to-branch edge. The litmus test framework is how these cases are checked, because reasoning about them by inspection fails.

What the architecture does not promise

The model is a specification of the permitted observations, not a description of any particular core. A core may implement LDAR with a mechanism quite unlike another core’s, and both are conforming as long as the observations they permit are within the model. The model is also deliberately conservative in places: an implementation that excludes some executions the model permits is conforming, which is why a litmus test that the model allows may never be observed on hardware.

The release-acquire rules in the language model are the same idea with a different vocabulary, and the mapping from memory_order_acquire to LDAR or LDAPR is a compiler decision that must be justified against this model. The Linux kernel’s model is where the two vocabularies meet, and where the choice between the two acquire strengths is made per primitive.