Daniel Marino
ABSTRACT
Data races are one of the most common and subtle causes of pernicious concurrency bugs. Static techniques for preventing data races are overly conservative and do not scale well to large programs. Past research has produced several dynamic data race detectors that can be applied to large programs. They are precise in the sense that they only report actual data races. However, dynamic data race detectors incur a high performance overhead, slowing down a program's execution by an order of magnitude.
In this paper we present LiteRace, a very lightweight data race detector that samples and analyzes only selected portions of a program's execution. We show that it is possible to sample a multithreaded program at a low frequency, and yet, find infrequently occurring data races. We implemented LiteRace using Microsoft's Phoenix compiler. Our experiments with several Microsoft programs, Apache, and Firefox show that LiteRace is able to find more than 70% of data races by sampling less than 2% of memory accesses in a given program execution.
- S. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. Computer, 29(12):66--76, 1996. Google Scholar
Digital Library
- S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In ISCA '91: Proceedings of the 18th Annual International Symposium on Computer architecture, 1991. Google ScholarDigital Library
- M. Arnold, M. Vechev, and E. Yahav. QVM: An efficient runtime for detecting defects in deployed systems. In OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, 2008. Google ScholarDigital Library
- Matthew Arnold and Barbara G. Ryder. A framework for reducing the cost of instrumented code. In PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 168--179, 2001. Google ScholarDigital Library
- C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, 2008. Google ScholarDigital Library
- Hans-Juergen Boehm and Sarita V. Adve. Foundations of the C++ concurrency memory model. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pages 68--78, 2008. Google ScholarDigital Library
- C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In OOPSLA'02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 211---230, 2002. Google ScholarDigital Library
- J. D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 258--269, 2002. Google ScholarDigital Library
- J. D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Transactions on Programming Languages and Systems, 13(4):491--530, 1991. Google ScholarDigital Library
- M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in java programs. In JVM '01: Proceedings of the Java Virtual Machine Research and Technology Symposium, 2001. Google ScholarDigital Library
- J. M. Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 24--33, 1991. Google ScholarDigital Library
- A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, pages 1--10, 1990. Google ScholarDigital Library
- A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, 1991. Google ScholarDigital Library
- Joe Duffy. A query language for data parallel programming: invited talk. In DAMP, page 50, 2007. Google ScholarDigital Library
- T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A race and transaction-aware java runtime. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 245--255, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 237--252, 2003. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Type-based race detection for Java. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 219--232, 2000. Google ScholarDigital Library
- M. Hauswirth and T. M. Chilimbi. Low-overhead memory leak detection using adaptive statistical profiling. In ASPLOS-XI: Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, pages 156--164, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- T. A. Henzinger, R. Jhala, and R. Majumdar. Race checking by context inference. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 1--13, 2004. Google ScholarDigital Library
- M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: Distributed data-parallel programs from sequential building blocks. In Proceedings of the EuroSys Conference, pages 59--72, 2007. Google ScholarDigital Library
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- Generic concurrent lock-free linked list -- http://www.cs.rpi.edu/ bushl2/project web/page5.html.Google Scholar
- J. Manson, W. Pugh, and S. Adve. The Java memory model. In Principles of Programming Languages (POPL), 2005. Google ScholarDigital Library
- Microsoft. Phoenix compiler. http://research.microsoft.com/Phoenix/.Google Scholar
- Microsoft. Thread execution blocks. http://msdn.microsoft.com/en-us/library/ms686708.aspx.Google Scholar
- S. L. Min and J.-D. Choi. An efficient cache-based access anomaly detection scheme. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS), pages 235--244, 1991. Google ScholarDigital Library
- M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 308--319, 2006. Google ScholarDigital Library
- R. H. B. Netzer. Optimal tracing and replay for debugging shared-memory parallel programs. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, pages 1--11, 1993. Google ScholarDigital Library
- H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. Third Virtual Machine Research & Technology Symposium, pages 127--138, May 2004. Google ScholarDigital Library
- R. O'Callahan and J. D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178, 2003. Google ScholarDigital Library
- D. Perkovic and P. J. Keleher. Online data-race detection via coherency guarantees. In OSDI '96: Operating System Design and Implementation, pages 47--57, 1996. Google ScholarDigital Library
- E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 179--190, 2003. Google ScholarDigital Library
- P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: Context-sensitive correlation analysis for race detection. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 320--331, 2006. Google ScholarDigital Library
- S. Qadeer and D. Wu. KISS: Keep it simple and sequential. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pages 14--24, 2004. Google ScholarDigital Library
- M. Ronsse and K. de Bosschere. Non-intrusive on-the-fly data race detection using execution replay. In Proceedings of Automated and Algorithmic Debugging, Nov 2000.Google Scholar
- P. Sack, B. E. Bliss, Z. Ma, P. Petersen, and J. Torrellas. Accurate and efficient filtering for the Intel Thread Checker race detector. In ASID'06: Proceedings of the 1st workshop on Architectural and system support for improving software dependability, pages 34--41, 2006. Google ScholarDigital Library
- A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 83--94, 2005. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997. Google ScholarDigital Library
- E. Schonberg. On-the-fly detection of access anomalies. In Proceedings of the ACM SIGPLAN'89 Conference on Programming Language Design and Implementation (PLDI), 1989. Google ScholarDigital Library
- N. Sterling. WARLOCK -- a static data race analysis tool. In Proceedings of the USENIX Winter Technical Conference, pages 97--106, 1993.Google Scholar
- C. von Praun and T. R. Gross. Object race detection. In OOPSLA'01: Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 70---82, 2001. Google ScholarDigital Library
- J.W. Voung, R. Jhala, and S. Lerner. RELAY: Static race detection on millions of lines of code. In ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, pages 205--214, 2007. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221--234, 2005. Google ScholarDigital Library
Index Terms
- LiteRace: effective sampling for lightweight data-race detection
Recommendations
ThreadSanitizer: data race detection in practice
WBIA '09: Proceedings of the Workshop on Binary Instrumentation and ApplicationsData races are a particularly unpleasant kind of threading bugs. They are hard to find and reproduce -- you may not observe a bug during the entire testing cycle and will only see it in production as rare unexplainable failures. This paper presents ...
LiteRace: effective sampling for lightweight data-race detection
PLDI '09Data races are one of the most common and subtle causes of pernicious concurrency bugs. Static techniques for preventing data races are overly conservative and do not scale well to large programs. Past research has produced several dynamic data race ...
A deployable sampling strategy for data race detection
FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software EngineeringDynamic data race detection incurs heavy runtime overheads. Recently, many sampling techniques have been proposed to detect data races. However, some sampling techniques (e.g., Pacer) are based on traditional happens-before relation and incur a large ...
Comments