Data Race Detection with Vector Clocks and Happens-Before Order

A data race is two accesses to the same memory location, at least one of them a write, from different threads, with no ordering between them. The definition is precise, and it is the last clause that makes detection hard: establishing that no ordering exists requires reasoning about every synchronisation operation that could have connected the two threads, across all their history. A detector that only compares thread identifiers and access times will report a race between two accesses that were in fact separated by a mutex.

The standard solution is to attach a timestamp to every memory access and every synchronisation event, where the timestamps form a partial order — the happens-before relation — and to report a race only when two accesses are concurrent in that order. The timestamp representation is the interesting part, because it determines both the precision of the answer and the cost of getting it.

Happens-before in a few rules

The relation is defined by a small set of axioms. Events within a single thread are totally ordered by program order. A release operation followed by an acquire of the same synchronisation object creates an order: everything before the release happens before everything after the acquire. Thread creation orders the creating thread’s earlier events before the new thread’s events, and thread join does the reverse.

From those axioms, a detector can maintain for each thread a clock representing the set of events known to precede its current point. When a thread performs a release, it publishes its clock into the synchronisation object. When another thread acquires, it merges the published clock into its own. The merge is a pointwise maximum over the clock’s components.

If the clock is a scalar counter, the representation is cheap and the relation it captures is coarse: it can express “thread A is ahead of thread B” but not “thread A has seen events from B and C”. For race detection, the coarse form produces false positives whenever a thread has synchronised with one thread but not another, because it cannot record which threads contributed to its knowledge.

The vector clock and its shadow word

A vector clock stores one component per thread, so a thread’s knowledge of the system is a vector of counters, and merging is pointwise maximum. The memory cost is the problem: with n threads, every clock is n components, and every synchronisation object must store one.

ThreadSanitizer’s compromise is a hybrid. Each thread has a fixed-size vector clock — four 64-bit components — plus a small hash map of additional slots for threads whose identifiers do not fit. The clock is not indexed by thread identifier directly; each component holds a thread identifier and a counter, so a clock with four components can represent knowledge of four threads precisely and falls back to the map for the rest. With more than four threads, the fallback path is slower and less precise, which is why the tool’s accuracy degrades on programs with many threads.

Memory accesses are not tracked per access in a log. Each memory location gets a shadow word: four 64-bit fields packed into 32 bytes, recording the last write and the last read as a thread identifier plus the clock value that thread had reached. On a 64-bit machine, that is 32 bytes of shadow per 8 bytes of program data, a 4:1 expansion. The shadow is stored in a sparse map keyed by address, allocated per 64-byte block as blocks are first touched, so only memory the program actually uses pays the cost.

#include <stdint.h>

struct vclock;                          /* per-thread vector clock */
uint64_t vclock_get(const struct vclock *vc, uint64_t tid);

/* Reduced shape of a shadow word: the last write and the last read, each
   as a thread identifier plus the clock value that thread had reached. */
struct shadow_word {
    uint64_t w_tid, w_epoch;
    uint64_t r_tid, r_epoch;
};

/* Does a new write by (tid, epoch) conflict with the recorded write?
   Ordered means the new thread's clock has passed the recorded epoch. */
int write_conflicts(const struct shadow_word *s, uint64_t tid, uint64_t epoch,
                    const struct vclock *vc)
{
    if (s->w_tid == tid) return 0;                    /* same thread */
    if (s->w_epoch <= vclock_get(vc, s->w_tid)) return 0;  /* ordered */
    return 1;                                         /* concurrent */
}

The comparison s->w_epoch <= vclock_get(vc, s->w_tid) is the whole detection: if the current thread’s clock has advanced past the epoch of the previous write, then the current thread has synchronised with that write, and the accesses are ordered. If not, they are concurrent, and since at least one is a write, it is a race.

Reads are handled by a coarser rule to keep the fast path short. A read does not update the shadow on every access; it updates a read epoch that summarises the range of timestamps at which the location has been read by the current thread. That approximation can miss a race between two reads and a write in a specific interleaving, and it can report a race that a per-access log would have cleared, but it keeps the instrumented read path to a handful of instructions.

Instrumentation points and what they cost

The compiler inserts checks at memory accesses, but not at every access. ThreadSanitizer’s instrumentation is applied to loads and stores in instrumented code, and the check consults the shadow word. It also inserts calls at every synchronisation operation, because those are what advance clocks: mutex lock and unlock, atomic operations with acquire or release semantics, thread creation and join, and condition variable waits and signals. The atomic operations are the important ones, since a lock-free algorithm has no mutex to hook and its ordering comes entirely from atomics.

The cost is dominated by the shadow lookup, not the comparison. A shadow lookup on the hot path is a hash computation and a memory read that is usually a cache miss, because the shadow is a separate region from the program data and does not share cache lines with it. That is the same structural cost that any shadow-based tool pays, and it is why the tool is used on a reduced workload rather than a full one.

A second cost is that every memory access now has an extra branch and an extra load, which changes the timing of the very interleavings the tool is trying to observe. A race that requires a narrow window may disappear under instrumentation, and a program that is correct but timing-sensitive may produce spurious reports from library code that the tool does not fully understand. Suppressions exist for exactly this: a list of function or file patterns whose reports are ignored, maintained because the alternative is a report stream that no one reads.

What the memory model permits

The detector implements a specific memory model, and its reports are only as meaningful as that model. It treats ordinary non-atomic accesses as unordered unless synchronisation connects them, which matches the C and C++ models’ notion of a data race and their statement that a racy program has undefined behaviour. It treats atomic accesses as synchronisation points, which matches the acquire and release semantics those operations carry.

The mismatch appears with relaxed atomics. A relaxed atomic operation carries no ordering, so it does not create a happens-before edge, and a detector that reports races on the basis of happens-before will report accesses that are ordered only through relaxed operations as racy. Under the language model that is arguably correct, since the program must not rely on ordering that relaxed operations do not provide; but the program may be correct in a weaker sense, with a hand-written argument that the accesses cannot actually conflict. The tool cannot see that argument.

A second mismatch is with code that uses synchronisation the tool does not recognise. A custom futex-based lock, a lock implemented with inline assembly, or a barrier built from atomics that the compiler does not instrument all fail to advance clocks, so accesses protected by them look unordered. The result is a race report pointing at correct code, and the fix is to annotate the custom primitives so the tool treats them as synchronisation, which requires the tool to expose a way to do so.

The third mismatch is the one that matters most for interpretation: a race report is not a proof of a bug in the sense of an observed failure. It is a statement that the two accesses are unordered in the model, and the program may nonetheless behave correctly on every execution the hardware produces, because the hardware’s ordering may be stronger than the model’s. That gap is exactly why the language model forbids the race: correctness that depends on the hardware’s extra ordering is not portable, and the next compiler version or the next architecture is free to break it.

Reading a report as an ordering argument

A report names two accesses, each with a thread, a stack trace, and the memory location. The useful reading is to reconstruct why the tool believes they are unordered: which lock was not held, which atomic operation did not carry release semantics, which thread was created without a join. The tool prints the synchronisation operations it did see, which is often enough to identify the one it did not.

Reports involving three or more threads are usually a sign that a clock has overflowed its four precise components and the tool has fallen back to the hash map, or that a synchronisation edge exists that the tool cannot model. Distinguishing those two cases requires looking at the thread count and the primitives involved, and it changes the response: the first is a precision limitation to work around, the second is a missing annotation.

The trace quality is again a function of the other machinery. Stack traces in a race report are produced by the unwinder, which needs call frame information as described in stack unwinding with call frame information, and the line numbers come from the tables described in DWARF line tables. A sanitized build without debug information produces reports that name addresses and functions, which is enough to know a race exists and rarely enough to know which lock should have covered it.

The complement to this tool is the address-based checker. A program can be free of data races and still corrupt memory, and the shadow-memory scheme described in AddressSanitizer shadow memory catches that class independently, at lower cost, on the same build if the two are combined where the runtimes permit it.