Accurate and efficient on-the-fly data race detection for multithreaded programs

Abstract

Benefiting from the recent hardware improvement, multithreaded programs may still introduce concurrency defects which are notoriously difficult to detect, due to the non-deterministic program behavior. One of such defects is known as data race. Programs which have data races often results in inconsistent data and unpredictable behavior. Conventional hybrid approaches of detecting data races suffer from either excessive analysis overhead or precision loss. In this thesis, we introduce three hybrid algorithms for detecting data races in multithreaded programs. By leveraging recent advances on more efficiently tracking the happens-before relation and by developing new lockset algorithms, our detectors can find more potential data races with less false warnings at some slight performance degradation. We first propose Acculock, which is the first hybrid detector that combines lockset and epoch-based happens-before for data race detection. Acculock analyzes a program execution by reasoning about the subset of the happens-before relation, thereby making it less sensitive to thread interleaving than pure happens-before detectors. When this relaxed happens-before relation is violated, Acculock applies a new lockset algorithm to verify the locking discipline, hence making it report less false warnings than the pure lockset detectors. We also propose MPL, which records sets of locksets instead of locksets to detect data races caused by the use of the multiple-protecting-lock idiom, which cannot be detected by Acculock. We finally present an improved version of MPL, MultiLock-HB, which also leverages the epoch-based happens-before technique by combining with a new lockset algorithm to reduce excessive false warnings and to find more races than MPL. All the properties of Acculock have been validated and confirmed by comparing it six other detectors, which are implemented in Jikes RVM using a collection of large benchmarks. Porting Acculock and repeating experiments in a different platform, RoadRunner, yields similar observations and conclusions in terms of their effectiveness in race detection and instrumentation overhead. Replacing the lockset algorithm used in Acculock with MultiLock-HB only suppresses three false warnings in eclipse at the expense of 3X performance slowdown (on average). Therefore, we can selectively apply MultiLock-HB to certain complicated applications where Acculock fails to reason about the multiple-protecting-lock idiom.