SimpleLock(+): Fast and Accurate Hybrid Data Race Detection

Abstract

Multithreading is a widely used programming technique that efficiently uses multicore processors. However, correctly executing a multithreaded program is challenging mainly because of intractable concurrency bugs caused by nondeterministic thread scheduling. Data races are one of the main causes of those concurrency bugs, and data race detectors are essential tools to assist long-suffering programmers in locating data races in problematic multithreaded programs. In this paper, we propose a new hybrid detector called SimpleLock(+), which accurately detects data races in a scheduling-insensitive manner with a low runtime overhead by combining happens-before and simplified Lockset algorithms. We significantly reduce the runtime slowdowns of previous hybrid detectors by assuming that most data races are caused by accesses to a shared memory location without the protection of locks and that the distance between accesses that cause a data race is not long in an execution trace. In addition, we improve the speed of the detection algorithm by using a simpler data structure and by eliminating redundant operations. The results of the experiments that are conducted on the RoadRunner framework confirm that those assumptions are valid and that the SimpleLock(+) detector can efficiently and accurately detect real and potential data races that are caused by inconsistent locking in one execution trace. The results also show that the average runtime slowdown of SimpleLock(+) is only 1.09 times that of FastTrack, which is the fastest happens-before race detector, and SimpleLock+ reports the same race warnings with one missing data race as the current accurate hybrid detector.