In Djit+, each thread has its own clock that is incremented at each lock release operation. Each thread t also
keeps a VC Ct such that, for any thread u, the clock entry
Ct(u) records the clock for the last operation of thread u
that happens before the current operation of thread t. In
addition, the algorithm maintains a VC Lm for each lock m.
These VCs are updated on synchronization operations that
impose a happens-before order between operations of different threads. For example, when thread u releases lock m,
the Djit+ algorithm updates Lm to be Cu. If a thread t subsequently acquires m, the algorithm updates Ct to be Ct Lm,
since subsequent operations of thread t now happen after
that release operation.
To identify conflicting accesses, the Djit+ algorithm keeps
two VCs, Rx and Wx, for each variable x. For any thread t, Rx(t)
and Wx(t) record the clock of the last read and write to x by
thread t. A read from x by thread u is race-free provided it
happens after the last write of each thread, that is, Wx Cu.
A write to x by thread u is race-free provided that the write
happens after all previous accesses to that variable, that is,
Wx Cu and Rx Cu.
As an example, consider the execution trace fragment
shown in Figure 1, where we include the relevant portion
of the Djit+ instrumentation state: the VCs C0 and C1 for
threads 0 and 1; and the VCs Lm and Wx for the last release
of lock m and the last write to variable x, respectively. We
show two components for each VC, but the target program
may of course contain additional threads.a
At the write wr(0, x), Djit+ updates Wx with current
clock of thread 0. At the release rel(0, m), Lm is updated
with C0. At the acquire acq( 1, m), C1 is joined with Lm, thus
capturing the dashed release-acquire happens-before
figure 1. execution trace under Djit+.
a For clarity, we present a variant of the Djit+ algorithm where some clocks
are one less than in the original formulation. 16 This revised algorithm has
the same performance as the original but is slightly simpler and more directly comparable to Fast Track.
edge shown above. At the second write, Djit+ compares
Wx = á4, 0, ...ñ á4, 8, ...ñ = C1
Since this check passes, the two writes are not concurrent,
and no race condition is reported.
3. the fasttrack aLGoRithm
A limitation of VC-based race detectors such as Djit+ is their
performance, since each VC requires O(n) space and each VC
operation (copying, comparing, joining, etc.) requires O(n)
Empirical benchmark data indicates that reads and
writes operations account for the vast majority (over
96%) of monitored operations. The key insight behind
FastTrack is that the full generality of VCs is not necessary in over 99% of these read and write operations: a
more lightweight representation of the happens-before
information can be used instead. Only a small fraction of
operations performed by the target program necessitate
expensive VC operations.
We begin by providing an overview of how our analysis
catches each type of race condition on a memory location. A
race condition is either: a write–write race condition (where a
write is concurrent with a later write); a write–read race condition (where a write is concurrent with a later read); or a read–
write race condition (where a read is concurrent with a later
Detecting Write–Write races: We first consider how to
efficiently analyze write operations. At the second write
operation in the trace in Figure 1, Djit+ compares the
VCs Wx C1 to determine whether there is a race. A careful inspection reveals, however, that it is not necessary
to record the entire VC á4, 0, …ñ from the first write to x.
Assuming no races have been detected on x so far, then
all writes to x are totally ordered by the happens-before
relation, and the only critical information that needs to
be recorded is the clock ( 4) and identity (thread 0) of the
thread performing the last write. This information (clock
4 of thread 0) is sufficient to determine if a subsequent
write to x is in a race with any preceding write.
We refer to a pair of a clock c and a thread t as an
epoch, denoted c@t. Although rather simple, epochs provide the crucial lightweight representation for recording
sufficiently-precise aspects of the happens-before relation
efficiently. Unlike VCs, an epoch requires only constant
space and supports constant-time operations.
An epoch c@t happens before a VC V (c@t V) if and only
if the clock of the epoch is less than or equal to the corresponding clock in the vector:
c@t V iff c ≤ V(t)
We use e to denote a minimal epoch 0@0.
Using this optimized representation, Fast Track analyzes
the trace from Figure 1 using a more compact instrumentation state that records only a write epoch Wx for variable x,
rather than the entire VC Wx, reducing space overhead, as