figure 2. execution trace under fasttrack.
C0
á4,0,…ñ
C1
á0, 8,…ñ
Lm
á0,0,…ñ
Wx
⊥e
wr(0,x)
á4,0,…ñ
á0, 8,…ñ
á0,0,…ñ
4@0
rel(0,m)
á5,0,…ñ
á5,0,…ñ
á5,0,…ñ
á0, 8,…ñ
acq( 1,m)
á4, 8,…ñ
wr( 1,x)
á4, 8,…ñ
á4,0,…ñ
á4,0,…ñ
á4,0,…ñ
4@0
4@0
8@ 1
shown in Figure 2. (C and L record the same information as
C and L in Djit+.)
At the first write to x, FastTrack performs an O( 1)-time
epoch write Wx := 4@0. Fast Track subsequently ensures
that the second write is not concurrent with the preceding
write via the O( 1)-time comparison:
Wx = 4@0 á4, 8, ...ñ = C1
To summarize, epochs reduce the space overhead for
detecting write–write conflicts from O(n) to O( 1) per allocated memory location, and replaces the O(n)-time VC comparison “” with the O( 1)-time comparison “”.
Detecting Write–read races: Detecting write–read races
under the new representation is also straightforward. On
each read from x with current VC Ct, we check that the read
happens after the last write via the same O( 1)-time comparison Wx Ct.
Detecting read– Write races: Detecting read–write race conditions is somewhat more difficult. Unlike write operations,
which are totally ordered in race-free programs, reads are
not necessarily totally ordered. Thus, a write to a variable x
could potentially conflict with the last read of x performed
by any other thread, not just the last read in the entire trace
seen so far. Thus, we may need to record an entire VC Rx,
in which Rx(t) records the clock of the last read from x by
thread t.
We can avoid keeping a complete VC in many cases,
however. Our examination of data access patterns across a
variety of multithreaded Java programs indicates that read
operations are often totally ordered in practice, particularly
in the following common situations:
• Thread-local data, where only one thread accesses a
variable, and hence these accesses are totally ordered
by program-order
• Lock-protected data, where a protecting lock is held on
each access to a variable, and hence all access are totally
ordered, either by program order (for accesses by the
same thread) or by synchronization order (for accesses
by different threads)
Reads are typically unordered only when data is
read-shared, that is, when the data is first initialized by one
thread and then shared between multiple threads in a read-only manner.
Fast Track uses an adaptive representation for the read
history of each variable that is optimized for the common
case of totally-ordered reads, while still retaining the full
precision of VCs when necessary.
In particular, if the last read to a variable happens after all
preceding reads, then Fast Track records only the epoch of
this last read, which is sufficient to precisely detect whether
a subsequent write to that variable conflicts with any preceding read in the entire program history. Thus, for thread-local
and lock-protected data (which do exhibit totally-ordered
reads), FastTrack requires only O( 1) space for each allocated memory location and only O( 1) time per memory
access.
In the less common case where reads are not totally
ordered, Fast Track stores the entire VC, but still handles
read operations in O( 1) time. Since such data is typically
read-shared, writes to such variables are rare, and their analysis overhead is negligible.
3. 1. analysis details
Based on the above intuition, we now describe the
FastTrack algorithm in detail. Our analysis is an online
algorithm whose analysis state consists of four components:
• Ct is the current VC of thread t.
The analysis starts with Ct = inct(^V), since the first operations of all threads are not ordered by happens-before. In
addition, initially Lm = V and Rx = Wx = e.
Figure 3 presents the key details of how Fast Track (left
column) and Djit+ (right column) handle read and write
operations of the target program. For each read or write operation, the relevant rules are applied in the order presented
until one matches the current instrumentation state. If an
assertion fails, a race condition exists. The figure shows the
instruction frequencies observed in the programs described
in Section 4, as well as how frequently each rule was applied.
For example, 82.3% of all memory and synchronization operations performed by our benchmarks were reads, and rule [FT
read same epoch] was used to check 63.4% of those reads.
Expensive O(n)-time operations are highlighted in grey.
read operations: The first four rules provide various alternatives for analyzing a read operation rd(t, x). The first rule