Dynamic recognition of synchronization operations for improved data race detection

ABSTRACT

Debugging multithreaded programs, which involves detection and identification of the cause of data races, has proved to be a hard problem. Although there has been significant amount of research on this topic, prior works rely on one important assumption - the debuggers must be aware of all the synchronization operations that take place during a program run. This assumption is a significant limitation as multithreaded programs, including the popular SPLASH-2 benchmark, have barriers and flag synchronizations implemented in the user code. We show that the lack of knowledge of these synchronization operations leads to unnecessary reporting of numerous races. Our experiments with SPLASH-2 benchmark suite show that 12-131 distinct segments in source code, on an average, give rise to well over 4 million dynamic instances of falsely reported races for these programs. We propose a dynamic software technique that identifies the user defined synchronizations exercised during a program run. This information not only helps avoids reporting of unnecessary races, but also helps a record/replay system to speedup the replay.

Our evaluation confirms that our synchronization detector is highly accurate with no false negatives and very few false positives. Thus, reporting of nearly all unnecessary races is avoided. Finally, we show that the knowledge of synchronization operations resulted in about 23% reduction in replay time.

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: E. Artiaga, N. Navarro, X. Martorell, Y. Becerra, M. Gil, and A. Serra. Experiences on the implementation of parmacs macros using different multiprocessor operating system interfaces.
• 3: David F. Bacon , Seth Copen Goldstein, Hardware-assisted replay of multiprocessor programs, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.194-206, May 20-21, 1991, Santa Cruz, California, United States
• 4: Sanjay Bhansali , Wen-Ke Chen , Stuart de Jong , Andrew Edwards , Ron Murray , Milenko Drinić , Darek Mihočka , Joe Chau, Framework for instruction-level tracing and analysis of program executions, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1220164]
• 5: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 6: 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]
• 7: Mark Christiaens , Koen De Bosschere, TRaDe, a topological approach to on-the-fly race detection in java programs, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.15-15, April 23-24, 2001, Monterey, California
• 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: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, ACM SIGPLAN Notices, v.35 n.5, p.219-232, May 2000
• 10: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, ACM SIGPLAN Notices, v.39 n.1, p.256-267, January 2004
• 11: Rajiv Gupta, The fuzzy barrier: a mechanism for high speed synchronization of processors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.54-63, April 03-06, 1989, Boston, Massachusetts, United States
• 12: Bohuslav Krena , Zdenek Letko , Rachel Tzoref , Shmuel Ur , Tomáš Vojnar, Healing data races on-the-fly, Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, July 09-09, 2007, London, United Kingdom [doi>10.1145/1273647.1273658]
• 13: 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]
• 14: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, ACM SIGPLAN Notices, v.40 n.6, June 2005
• 15: Peter S. Magnusson , Anders Landin , Erik Hagersten, Queue Locks on Cache Coherent Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.165-171, April 01, 1994
• 16: 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]
• 17: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 18: Satish Narayanasamy , Cristiano Pereira , Brad Calder, Recording shared memory dependencies using strata, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 19: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 20: Satish Narayanasamy , Zhenghao Wang , Jordan Tigani , Andrew Edwards , Brad Calder, Automatically classifying benign and harmful data racesallusing replay analysis, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 21: Nicholas Nethercote , Julian Seward, How to shadow every byte of memory used by a program, Proceedings of the 3rd international conference on Virtual execution environments, June 13-15, 2007, San Diego, California, USA [doi>10.1145/1254810.1254820]
• 22: Robert H. B. Netzer, Optimal tracing and replay for debugging shared-memory parallel programs, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.1-11, May 17-18, 1993, San Diego, California, United States
• 23: 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
• 24: V. Project. Helgrind, a data race detector. In http://valgrind.org/docs/manual/hg-manual.html, 2003.
• 25: 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]
• 26: Yasushi Saito, Jockey: a user-space library for record-replay debugging, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.69-76, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085139]
• 27: Amit Sasturkar , Rahul Agarwal , Liqiang Wang , Scott D. Stoller, Automated type-based analysis of data races and atomicity, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065956]
• 28: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multi-threaded programs, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.27-37, October 05-08, 1997, Saint Malo, France
• 29: 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
• 30: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 31: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 32: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Measurement, Reliability

Keywords:
data races, record and replay, synchronization and infeasible races