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.