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