RaceTrack: efficient detection of data race conditions via adaptive tracking

Abstract

Bugs due to data races in multithreaded programs often exhibit non-deterministic symptoms and are notoriously difficult to find. This paper describes RaceTrack, a dynamic race detection tool that tracks the actions of a program and reports a warning whenever a suspicious pattern of activity has been observed. RaceTrack uses a novel hybrid detection algorithm and employs an adaptive approach that automatically directs more effort to areas that are more suspicious, thus providing more accurate warnings for much less over-head. A post-processing step correlates warnings and ranks code segments based on how strongly they are implicated in potential data races. We implemented RaceTrack inside the virtual machine of Microsoft's Common Language Runtime (product version v1.1.4322) and monitored several major, real-world applications directly out-of-the-box,without any modification. Adaptive tracking resulted in a slowdown ratio of about 3x on memory-intensive programs and typically much less than 2x on other programs,and a memory ratio of typically less than 1.2x. Several serious data race bugs were revealed, some previously unknown.

References

1. S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In Proceedings of the 18th Annual International Symposium on Computer Architecture (ISCA), pages 234--243, May 1991.
2. C. Boyapati and M. Rinard. A parameterized type system for race-free Java programs. In Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications (OOPSLA), Oct. 2001.
3. A. Broder, S. Glassman, M. Manasse, and G. Zweig. Syntactic clustering of the web. In Proceedings of the 6th International World Wide Web Conference, 1997.
4. J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise data race detection for object oriented programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, 2002.
5. 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, October 1991.
6. M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in Java programs. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM), Apr. 2001.
7. A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 1--10, 1990.
8. 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, New York, NY, USA, 1991. ACM Press.
9. Ecma International. Standard ECMA-335: Common language infrastructure (CLI), 2002. http://www.ecma-international.org/publications/standards/Ecma335.htm.
10. D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP), pages 237--252, October 2003.
11. C. Flanagan and S. N. Freund. Type-based race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 219--232, 2000.
12. J. Gough and K. Gough. Compiling for the .NET Common Language Runtime. Prentice Hall PTR, 2001.
13. J. J. Harrow. Runtime checking of multithreaded applications with visual threads. In Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, pages 331--342, London, UK, 2000. Springer-Verlag.
14. T. Henzinger, R. Jhala, and R. Majumder. Race checking by context inference. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2004.
15. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, July 1978.
16. J. MacCormick, N. Murphy, M. Najork, C. A. Thekkath, and L. Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI), pages 105--120, Dec. 2004.
17. F. Mattern. Virtual time and global states of distributed systems. In C. M. et al., editor, Proc. Workshop on Parallel and Distributed Algorithms, pages 215--226, North-Holland / Elsevier, 1989.
18. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of Supercomputing, November 1991.
19. Microsoft Corporation. Basic class library communities. http://msdn.microsoft.com/netframework/programming/classlibraries/.
20. Microsoft Corporation. Shared source common language infrastructure 1.0 release, Nov. 2002. http://msdn.microsoft.com/net/sscli.
21. H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (VM), May 2004.
22. R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 167--178, 2003.
23. D. Perković and P. J. Keleher. Online data-race detection via coherency guarantees. In The Second Symposium on Operating Systems Design and Implementation (OSDI), pages 47--57, Oct. 1996.
24. E. Pozniansky and A. Schuster. Efficient on-the-fly race detection in multithreaded C++ programs. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2003.
25. C. Praun and T. Gross. Object race detection. In Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications (OOPSLA), pages 70--82, 2001.
26. M. O. Rabin. Fingerprinting by random polynomials. Report TR--15--81, Department of Computer Science, Harvard University, 1981.
27. M. Ronsse and K. De Bosschere. RecPlay: A fully integrated practical record/replay system. ACM Transactions on Computer Systems, 17(2):133--152, May 1999.
28. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997.
29. D. C. Schmidt and T. Harrison. Double-checked locking: An optimization pattern for efficiently initializing and accessing thread-safe objects. In M. Buschmann and D. Riehle, editors, Pattern Languages of Program Design 3. Addison-Wesley, Reading, MA, 1997.
30. E. Schonberg. On-the-fly detection of access anomalies. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, 1989.
31. Standard Performance Evaluation Corporation. SPEC JBB2000. http://www.spec.org/jbb2000/.
32. N. Sterling. Warlock: A static data race analysis tool. In Proceedings of USENIX Winter Technical Conference, January 1993.
33. Valgrind project. Helgrind: a data-race detector, 2005. http://valgrind.org/docs/manual/hg-manual.html.

Index Terms

• Information systems

  • Data management systems

    • Middleware for databases

      • Distributed transaction monitors

• Software and its engineering

  • Software creation and management

    • Software verification and validation

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Monitors