Happens-Before and the Definition of a Data Race

The phrase “the program has a data race” is usually treated as a warning about timing. In the C and C++ standards it is a definitional statement about a relation, and it has a precise answer that does not depend on scheduling at all: a race exists if two accesses to the same object, at least one of them a write, are not ordered by happens-before. The answer is a property of the program and its inputs, not of the machine it runs on.

This is a stronger statement than it sounds. It means a race can be diagnosed by examining the synchronisation structure of the source, and it means the compiler is entitled to assume no race exists when optimising. Everything else about the language’s concurrency rules follows from that entitlement.

Two relations, one order

Happens-before is not primitive. It is the transitive closure of a union of two relations defined on the actions of a program.

Sequenced-before is the intra-thread order. For an ordinary single-threaded expression, every value computation and side effect is sequenced in the order the language defines for evaluation — full expressions, statements, and the sequencing rules for operators. It is a total order within a thread except where the language leaves evaluation order unspecified, as with the arguments of a function call.

Synchronizes-with is the inter-thread edge, and it exists only between specific pairs of operations. The canonical pair is a release store to an atomic object and an acquire load from that same object that reads the value written by the release store, or by an operation in the release sequence headed by it — the read-modify-writes that follow it in the object’s modification order. There are others: a lock/unlock pair on the same mutex, the completion of a thread and a join on it, the start of a thread and everything it does, and a fence-based pair under the rules for atomic thread fences. Each of these is a real edge in the model, not a figure of speech.

Happens-before is the transitive closure of sequenced-before together with synchronizes-with. The closure is what makes the model useful: thread A stores data, release-stores a flag, thread B acquire-loads the flag and reads the data. There is no direct edge from A’s data store to B’s data load, but there is a path — store → release store (sequenced), release store → acquire load (synchronizes-with), acquire load → load (sequenced) — and the closure puts the two data accesses in order.

Why the order is partial and must stay partial

Happens-before is deliberately not a total order. Two threads that never synchronise have no edges between them, and their operations are unordered, even if one of them finished long before the other started in wall-clock terms. Adding a total order would reintroduce a notion of global time that the model is designed to avoid, and it would make the model stronger than the hardware can implement.

The relation is also not a happens-before in the temporal sense of “earlier”. An operation that is ordered before another in the relation is guaranteed to be visible to it, which is a statement about information flow, not about clocks. Two operations on different cores may be simultaneous in real time while being ordered in the relation, and two operations may be separated by microseconds of real time while being unordered. Treating the relation as a timestamp comparison is the most common way to misread it.

The race definition and its consequences

The C11 and C++11 definitions are close to identical. A data race occurs when two actions in different threads access the same memory location, at least one is a write, and neither happens before the other. If a program contains a data race, its behaviour is undefined — not “unpredictable” or “platform-dependent”, but outside the specification, the same status as a buffer overflow.

Undefined behaviour is a licence. The compiler may assume that no execution of the program contains a race, and it uses that assumption to justify transformations that would be invalid in a racy program. The classic demonstration is a loop that spins on a plain boolean flag:

int stop;   /* plain int, not atomic */

void worker(void) { while (!stop) { /* ... */ } }

A compiler may hoist the load of stop out of the loop, because if the program has defined behaviour, no other thread can be writing stop while this loop reads it, so the value cannot change. The loop then never terminates. Making stop an _Atomic int and loading it with acquire semantics both gives the loop a defined meaning and gives the compiler a value it must reload.

The same licence applies in the other direction. A compiler may fuse, split, or eliminate accesses to non-atomic objects, invent speculative loads, and keep values in registers, all on the strength of the no-race assumption. Code that is racy and “works” is code whose behaviour was never specified, and it can change when the optimiser changes.

Two refinements matter in practice. First, the definition says “conflicting”, meaning same location, at least one write. Two concurrent reads never race. Second, accesses to distinct objects never race, but “object” is finer than programmers expect: adjacent bit-fields may share a memory location, and two char elements of an array are distinct objects but a struct copy of a larger type touches many locations at once.

Atomics, and the cost of ordering

Atomic operations are the escape from undefined behaviour, but the standard offers a menu of orderings whose only difference is which edges they create. A relaxed atomic store and a relaxed atomic load to the same object do not create a synchronizes-with edge; they guarantee only that the load returns some value from the object’s modification order and that the object is not torn. A release store paired with an acquire load creates the edge. A sequentially consistent store and load create the edge plus participation in a single total order over all sequentially consistent operations.

The menu exists because the edge is not free. On a machine with a store buffer, a release store needs the prior writes to be visible before the flag becomes visible, which typically requires a barrier or a store-release instruction; an acquire load needs the following reads not to be hoisted above it. Relaxed operations need neither. A counter that only needs to be incremented and read approximately can use relaxed operations; a flag that publishes a data structure needs release and acquire.

The detailed mechanics of those edges are covered in release, acquire, and synchronizes-with. What matters at this level is that the ordering choice changes the set of permitted executions, and that the permitted executions are exactly those consistent with the edges the programmer wrote.

Mixed atomic and non-atomic access

The standard defines an additional relation, coherence, that orders modifications to a single object. An atomic object has a modification order, and every atomic load reads some value from it. A non-atomic access to an object that is concurrently accessed atomically is not simply racy in the usual sense; the standard treats the combination as undefined as well.

The practical consequence is that the transition from racy to correct requires both sides to change. Converting the writer to an atomic store and leaving the reader as a plain load does not remove the race. The C++20 atomic_ref facility exists to apply atomic operations to an object that is otherwise an ordinary variable, and it works only if every concurrent access goes through an atomic reference.

Where the model stops

Happens-before as defined by the language is not the same relation as the hardware’s. The language relation is a constraint on the compiler’s output; the hardware relation is a constraint on the machine’s execution of that output. The compiler is responsible for preserving the language relation when it emits instructions, which it does by mapping each ordering onto instructions or barriers sufficient for the target. A release store in the source may become a plain store followed by a barrier, or a single store-release instruction, or a plain store on a machine whose stores are already ordered — and all three are correct.

This layering is why a program correct in the language can still fail if it uses inline assembly or intrinsics that bypass the compiler’s model. The DRF-SC guarantee explains what the language promises for race-free programs and why that promise is the foundation of the whole design.