Dynamic Race Detection

Dynamic race detection is the practice of finding data races — two concurrent accesses to the same memory location where at least one is a write and the two are not ordered by synchronization — by observing a program as it actually runs, rather than by proving properties of its source. Two algorithm families dominate. Happens-before detectors (Lamport’s partial order, tracked with vector clocks) are precise: they report a race only when the observed execution truly contains one, but they see only the interleaving that happened. Lockset detectors — the technique introduced by Eraser (Savage, Burrows, Nelson, Sobalvarro & Anderson, SOSP 1997, Sosp97.pdf) — instead check that a consistent locking discipline is obeyed, catching races that a given schedule did not expose, at the cost of false alarms. Modern tools such as Google’s ThreadSanitizer and Go’s -race build a fast happens-before engine on shadow memory. The one property no dynamic detector can escape: it can only judge the code paths and interleavings it actually executes.

This is the general theory of runtime race detection. For the concrete Go-specific instrument — the -race flag, the exact ThreadSanitizer shadow-cell bit layout, the GORACE knobs — see Data Races and the Race Detector, which this note is the upstream reference for. The definitions of race vs. race condition live in Race Conditions and Data Races; the partial order every happens-before detector rests on is Happens-Before Relation; its clock representation is Vector Clocks.

Mental Model

Every dynamic detector answers the same question on each memory access — “could this access be racing with a prior one?” — but the two families answer it from opposite directions. A happens-before detector asks a question about this run: “is there a synchronization chain ordering my access after every prior conflicting access?” If yes, safe; if no, race. A lockset detector asks a question about discipline: “is there some lock that has been held by every thread on every access to this location so far?” If the set of such candidate locks ever empties, the location is unprotected and a warning fires — regardless of whether this schedule happened to collide.

flowchart TD
    ACC["memory access<br/>(thread t, addr a, read/write)"]
    ACC --> HB["Happens-before family<br/>compare vector clocks"]
    ACC --> LS["Lockset family (Eraser)<br/>intersect candidate locks"]

    HB --> HBQ{"prior conflicting access<br/>NOT ordered before me?"}
    HBQ -->|yes| RACE1["RACE (real, on this run)"]
    HBQ -->|no| OK1["ordered → safe"]

    LS --> LSQ{"candidate lock set C(a)<br/>became empty?"}
    LSQ -->|yes| RACE2["WARNING (discipline violated;<br/>may be false positive)"]
    LSQ -->|no| OK2["some lock still covers a"]

    HB -. "precise, schedule-dependent" .-> J["Hybrid: run both,<br/>fewer misses, some noise"]
    LS -. "coverage, false positives" .-> J

Diagram: the two families and their fusion. The insight to carry away — happens-before trades coverage for precision (never lies, but only about the schedule it saw); lockset trades precision for coverage (generalizes across schedules, but cries wolf on lock-free and read-shared code). Hybrid detectors run both and take the intersection of their strengths.

What Counts as a Race — and Which “Race” Each Family Finds

A data race is defined relative to the happens-before partial order: two accesses to one location conflict if they come from different threads and at least one writes; they race if they conflict and neither happens-before the other (Race Conditions and Data Races). This is the definition a happens-before detector checks directly. Crucially, a data race is not the same as a race condition — a race condition is any order-dependent bug, which may involve no data race at all (two atomics interleaving badly), and a data race may be benign. Dynamic detectors target the data race, because the language memory models make it undefined behavior: in C, C++, and Go a data race gives the compiler and hardware license to produce torn reads, lost updates, and “impossible” values (the DRF-SC bargain — see Data-Race-Free Programs and the DRF-SC Theorem).

The lockset family checks a sufficient condition for race-freedom rather than the definition itself: if every shared location is consistently protected by some lock, the program has no data races. The converse fails — a program can be race-free without consistent locking (it might use happens-before ordering via thread creation, channels, or atomics) — which is exactly the source of lockset false positives.

Happens-Before Detection — Precise but Schedule-Bound

The happens-before approach instruments every synchronizing operation (lock/unlock, thread fork/join, channel send/receive, atomic load/store) to maintain, per thread, a vector clock: a vector of logical timestamps, one entry per thread, recording “the latest event in thread j that this thread knows happens-before its current point” (Vector Clocks). On a release-style operation (unlock, send) the thread publishes its vector clock into the synchronization object; on the matching acquire (lock, receive) the receiver takes the component-wise maximum, absorbing everything ordered before the release. For each memory location the detector remembers the vector clock at the last read and last write. A new access at clock C_t conflicts with a stored access at clock C_prev iff C_prev is not ≤ C_t component-wise — i.e. the prior access is not in this access’s causal past. That comparison is precisely “not ordered by happens-before,” so a positive is a true race in the executed schedule.

Cost. Naïvely this is expensive: a vector clock is O(n) words for n threads, and every memory access does an O(n) comparison and possibly an O(n) join. FastTrack (Flanagan & Freund, PLDI 2009, pldi09.pdf) is the key optimization that made precise happens-before detection practical. Its observation: the last write to a location is always by a single thread, so it can be summarized by a single epoch — a pair c@t of one clock value and one thread id — instead of a whole vector. Reads are similar unless a location is genuinely read-shared by concurrent readers, in which case FastTrack keeps a full vector clock but only for that minority of locations. The result is that the common cases (thread-local, lock-protected, write-owned) run in O(1) per access while precision is fully preserved; the full vector is materialized lazily only where the sharing pattern demands it.

The intrinsic limitation. A happens-before detector can only witness the interleaving the scheduler produced. Eraser’s authors illustrate this with a two-thread program that races on a variable y accessed once outside a lock and once inside: in the particular interleaving where thread 1 finishes its locked section before thread 2 begins, an unlock→lock edge orders the two y accesses, and happens-before sees no race — even though a different schedule would collide (per Eraser, §1). To catch such a race a happens-before tool needs a test that exercises the racy interleaving. This is why a green -race run means “no race on the paths and schedules I ran,” never “race-free.”

Lockset Detection — Eraser’s Discipline Check

Eraser attacks the schedule-dependence head-on by not tracking ordering at all. For each shared location v it keeps a candidate lock set C(v), initialized to the set of all locks. On each access to v by thread t, Eraser refines C(v) := C(v) ∩ locks_held(t) — intersecting with the locks the accessing thread currently holds. If a single lock protects every access, that lock survives in C(v); if C(v) ever becomes empty, no lock consistently protects v, and Eraser issues a warning (Eraser §2). The power of this is that the violation is detected whichever interleaving runs, as long as the two conflicting code paths both execute — the tool generalizes a single observed execution into a statement about the locking discipline.

The refinement state machine

The naïve lockset rule is too strict: it flags perfectly correct code that legitimately runs without locks. Eraser’s refinement is a four-state machine per location that suppresses those false positives (Eraser §2.1–2.3, Figure 4):

• Virgin — freshly allocated, never accessed. No thread can hold a reference yet.
• Exclusive — accessed by exactly one thread so far. Reads and writes here do not refine C(v), which is how initialization without a lock is tolerated: a thread may set up a structure lock-free, and only when a second thread touches it does discipline-checking begin.
• Shared — read by a second thread. C(v) is now refined on access, but races are not reported. This tolerates read-shared data: values written once during initialization and only read thereafter need no lock, and multiple concurrent readers never race.
• Shared-Modified — written by a thread after the location became shared. Only here does Eraser both refine C(v) and report an empty candidate set as a race.

stateDiagram-v2
    [*] --> Virgin
    Virgin --> Exclusive: first access
    Exclusive --> Exclusive: rd/wr, same thread
    Exclusive --> Shared: rd, new thread
    Exclusive --> SharedModified: wr, new thread
    Shared --> Shared: rd (any thread)
    Shared --> SharedModified: wr
    SharedModified --> SharedModified: rd/wr;<br/>refine C(v), report if empty

Diagram: Eraser’s per-location state machine (after Eraser Figure 4). The insight — the states exist purely to model when unlocked access is legitimate (single-owner initialization; read-only sharing) so that the lockset check only bites once a location is genuinely written while shared. Races are reported only in Shared-Modified.

Eraser also handles reader-writer locks: a lock held in read mode protects against writer/reader conflicts but not writer/writer, so on a write the refinement intersects only with locks held in write mode, while a read intersects with locks held in any mode. Implementation-wise the original ran on DIGITAL Unix/Alpha via the ATOM binary-rewriting toolkit, adding a 2-bit state and a 30-bit “lockset index” (interned pointer into a table of distinct lock sets, of which real programs exhibit surprisingly few — the paper never saw more than ~10,000) into a shadow word per 32-bit application word.

Where lockset is wrong

Lockset’s coverage is bought with false positives, and Eraser’s own experience report (§3.3, §4) is candid about the categories: memory reuse (a freed-and-recycled block carries a stale shadow lockset unless the allocator is instrumented to reset it to Virgin); private locks (a program’s home-grown mutex the tool doesn’t recognize as a lock); and genuinely benign races (statistics counters, done-flags) that violate the discipline deliberately. Eraser exposed EraserIgnoreOn/Off, EraserReuse, and EraserReadLock/WriteLock annotations to silence these — a handful per large server sufficed to drive reports to zero. The deeper false-positive is structural: any synchronization that establishes ordering without a lock — thread fork/join, message passing, atomics, condition-variable signaling — looks to a pure lockset detector like an unprotected access.

Hybrid Detectors

Because each family misses what the other catches — happens-before misses races the schedule hid; lockset misses that non-lock synchronization is legitimate — practical tools combine them. Helgrind (Valgrind) pioneered a hybrid algorithm, and the first-generation ThreadSanitizer (Serebryany & Iskhodzhanov, “ThreadSanitizer — data race detection in practice,” WBIA 2009) formalized the fusion. TSan’s hybrid state machine tracks, per location, both segment sets (encoding the happens-before partial order via Lamport-style segments) and locksets: two accesses are concurrent only if there is no happens-before arc between them and their locksets are disjoint, and a race is a concurrent pair with at least one write. The hybrid reports more real races than pure happens-before, but it over-reports on lock-free synchronization the tool cannot infer — so TSan introduced dynamic annotations (ANNOTATE_HAPPENS_BEFORE / ANNOTATE_HAPPENS_AFTER) letting the programmer inject the missing happens-before edges around custom synchronization (message queues, reference counting, publish-via-flag), collapsing the false positives (per the WBIA 2009 paper).

That same paper is candid about a fundamental hardness result it sidesteps: precise data-race detection is NP-hard, so every practical tool accepts either misses or false alarms; the engineering question is only which, and how few.

Uncertain

Verify: the claim that precise dynamic race detection is NP-hard. Reason: I read it stated in the ThreadSanitizer WBIA 2009 paper’s introduction, which attributes it to prior work (its reference [20]) rather than proving it; the classic result is Netzer & Miller, “What are race conditions?” (1992). To resolve: read Netzer & Miller directly for the exact complexity claim and the class of races it applies to. #uncertain

The Modern Precise Engine — ThreadSanitizer v2 and Go’s -race

The ThreadSanitizer that ships in Clang/GCC (-fsanitize=thread) and is vendored into the Go runtime is a second-generation re-implementation that deliberately runs in pure happens-before mode — it dropped the hybrid lockset to avoid false positives, trading some coverage for the guarantee that every report is a real race. Go’s documentation states this flatly: the detector “will not issue false positives,” so a warning must be taken seriously (The Go Blog: race detector). It works by compiler-instrumenting every memory access and maintaining shadow memory — a small fixed number of shadow cells per application word, each packing a thread id, a scalar logical clock, and read/write metadata — so the happens-before check is an O(1)-ish scan of a few cells with no hash-table lookup on the hot path (see the ThreadSanitizer algorithm wiki). The precise mechanics of that shadow layout, and the Go-specific integration, are documented in Data Races and the Race Detector — this note deliberately does not re-derive them.

The price of “pure happens-before, no false positives” is coverage: because it never generalizes across schedules, TSan v2 finds a race only on runs that actually execute the racy interleaving. The WBIA paper quantifies the practical gap — a hybrid detector may flag a race on every run, while a pure happens-before detector might expose the same race on only 1 of 10–100 runs. Go’s guidance follows directly: run race-enabled binaries under realistic, high-concurrency workloads, and keep them in CI, because coverage of interleavings is the whole game.

Comparison — Choosing an Approach

	Happens-before (precise)	Lockset (Eraser)	Hybrid (TSan v1)
Reports a race when…	observed run truly races	locking discipline violated	concurrent + lockset-disjoint
False positives	none	yes (non-lock sync, reuse, benign)	yes, without annotations
Misses	races not exposed by this schedule	fewer (schedule-independent)	fewest
Sees non-lock synchronization	yes	no	partly
Cost per access	O(1) with FastTrack epochs	O(1) lockset intersection (interned)	both
Canonical tool	TSan v2, Go -race, FastTrack	Eraser (1997)	Helgrind, TSan v1

The industry has largely converged on precise happens-before with FastTrack-style epochs: the value of “zero false positives” for developer trust outweighs the coverage of lockset, and the coverage gap is closed instead by running more interleavings (stress, fuzzing, CI under load — see Stress Testing and Fuzzing Concurrent Code) rather than by tolerating noise. Lockset’s enduring contribution is conceptual — the idea that a discipline can be checked, generalizing beyond one schedule — and it survives inside hybrid engines and static analyzers.

Production Notes

Google’s deployment of ThreadSanitizer across its C++ codebase and Chromium found real races that had gone unexplained for months — the canonical case being a reference-counting class whose increment/decrement raced only rarely, corrupting the allocator and crashing far from the scene; TSan reproduced it in a single instrumented run where stress testing had failed for months (per the WBIA 2009 paper §7). The lesson generalizes: dynamic detectors turn timing-dependent, non-local corruption into a deterministic, pinpointed report at the moment of the racing access — which is why they are worth their 5–10× time and memory overhead in test and CI even though they cannot run continuously in production. The complementary lesson is their blind spot: because they observe only executed interleavings, they pair naturally with schedule-exploration techniques (Model Checking Concurrent Systems exhaustively enumerates interleavings; Stress Testing and Fuzzing Concurrent Code perturbs the scheduler) that attack the coverage problem a single dynamic run cannot.

See Also

• Model Checking Concurrent Systems — the complementary discipline: a dynamic detector observes one schedule; a model checker exhaustively checks all of them
• Data Races and the Race Detector — the concrete Go instance (the -race flag, TSan shadow-cell layout, GORACE); this note is its upstream theory
• Race Conditions and Data Races — the precise definitions (data race ≠ race condition) these detectors target
• Happens-Before Relation — the partial order every happens-before detector checks
• Vector Clocks — the clock representation of happens-before, and what FastTrack epochs compress
• Data-Race-Free Programs and the DRF-SC Theorem — why a data race is undefined behavior worth detecting
• Stress Testing and Fuzzing Concurrent Code — how to increase the interleaving coverage a dynamic detector depends on
• Concurrency and Parallelism MOC — §10 Correctness