Doi: 10.1145/1839676.1839699

FastTrack: Efficient and Precise
Dynamic Race Detection

abstract

Multithreaded programs are notoriously prone to race conditions. Prior work developed precise dynamic race detectors that never report false alarms. However, these checkers employ expensive data structures, such as vector clocks (VCs), that result in significant performance overhead.

This paper exploits the insight that the full generality of VCs is not necessary in most cases. That is, we can replace VCs with an adaptive lightweight representation that, for almost all operations of the target program, requires constant space and supports constant-time operations. Experimental results show that the resulting race detection algorithm is over twice as fast as prior precise race detectors, with no loss of precision.

1. intRoDuction

Multithreaded programs are prone to race conditions and other concurrency errors such as deadlocks and violations of expected atomicity or determinism properties. The broad adoption of multicore processors is exacerbating these problems, both by driving the development of multithreaded software and by increasing the interleaving of threads in existing multithreaded systems.

A race condition occurs when two threads concurrently perform memory accesses that conflict. Accesses conflict when they read or write the same memory location and at least one of them is a write. In this situation, the order in which the two conflicting accesses are performed can affect the program’s subsequent state and behavior, likely with unintended and erroneous consequences.

Race conditions are notoriously problematic because they typically cause problems only on rare interleavings, making them difficult to detect, reproduce, and eliminate. Consequently, much prior work has focused on static and dynamic analysis tools for detecting race conditions.

To maximize test coverage, race detectors use a very broad notion of when two conflicting accesses are considered concurrent. The accesses need not be performed at exactly the same time. Instead, the central requirement is that there is no “synchronization dependence” between the two accesses, such as the dependence between a lock release by one thread and a subsequent lock acquire by a different thread. These various kinds of synchronization dependencies form a partial order over the instructions in the execution trace called the happens-before relation. 13 Two memory accesses are then considered to be concurrent if they are not ordered by this happens-before relation.

In this paper, we focus on online dynamic race detectors,
which generally fall into two categories depending on whether
they report false alarms. Precise race detectors never produce
false alarms. Instead, they compute a precise representation
of the happens-before relation for the observed trace and
report an error if and only if the observed trace has a race con-
dition. Note that there are typically many possible traces for a
particular program, depending on test inputs and scheduling
choices. Precise dynamic race detectors do not reason about
all possible traces, however, and may not identify races that
occur only when other code paths are taken. While full cover-
age is desirable, it comes at the cost of potential false alarms
because of the undecidability of the halting problem. To avoid
these false alarms, precise race detectors focus on detecting
only race conditions that occur on the observed trace.