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: Sarita V. Adve , Mark D. Hill , Barton P. Miller , Robert H. B. Netzer, Detecting data races on weak memory systems, Proceedings of the 18th annual international symposium on Computer architecture, p.234-243, May 27-30, 1991, Toronto, Ontario, Canada
• 2: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 3: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 4: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 5: Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
• 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 , E. Schonberg, An empirical comparison of monitoring algorithms for access anomaly detection, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.1-10, March 14-16, 1990, Seattle, Washington, United States
• 8: Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.85-96, May 20-21, 1991, Santa Cruz, California, United States
• 9: Ecma International. Standard ECMA-335: Common language infrastructure (CLI), 2002. http://www.ecma-international.org/publications/standards/Ecma335.htm.
• 10: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 11: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.219-232, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: John John Gough , K. John Gough, Compiling for the .Net Common Language Runtime, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 13: Jerry J. Harrow, Runtime Checking of Multithreaded Applications with Visual Threads, Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, p.331-342, August 30-September 01, 2000
• 14: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar, Race checking by context inference, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 15: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 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: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 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: Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 23: Dejan Perkovic , Peter J. Keleher, Online data-race detection via coherency guarantees, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.47-57, October 29-November 01, 1996, Seattle, Washington, United States
• 24: Eli Pozniansky , Assaf Schuster, Efficient on-the-fly data race detection in multithreaded C++ programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 25: Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
• 26: M. O. Rabin. Fingerprinting by random polynomials. Report TR--15--81, Department of Computer Science, Harvard University, 1981.
• 27: Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999 [doi>10.1145/312203.312214]
• 28: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 29: Douglas C. Schmidt , Tim Harrison, Double-checked locking, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 30: D. Schonberg, On-the-fly detection of access anomalies, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.285-297, June 19-23, 1989, Portland, Oregon, United States
• 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

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

General Terms:
Performance, Reliability

Keywords:
race detection, virtual machine instrumentation