RecPlay: a fully integrated practical record/replay system

ABSTRACT

This article presents a practical solution for the cyclic debugging of nondeterministic parallel programs. The solution consists of a combination of record/replay with automatic on-the-fly data race detection. This combination enables us to limit the record phase to the more efficient recording of the synchronization operations, while deferring the time-consuming data race detection to the replay phase. As the record phase is highly efficient, there is no need to switch it off, hereby eliminating the possibility of Heisenbugs because tracing can be left on all the time. This article describes an implementation of the tools needed to support RecPlay.

REFERENCES

• 1: Sarita V. Adve , Mark D. Hill , Barton P. Miller , Robert H. B. Netzer, Detecting data races on weak memory systems, ACM SIGARCH Computer Architecture News, v.19 n.3, p.234-243, May 1991
• 2: AUDENAERT, K. AND LEVROUW, L. 1994. Interrupt replay: A debugging method for parallel programs with interrupts. Microprocess. Microsyst. 18, 10, 601-612.
• 3: K. Audenaert , L. Levrouw, Space efficient data race detection for parallel programs with series-parallel task graphs, Proceedings of the 3rd Euromicro Workshop on Parallel and Distributed Processing, p.508, January 25-27, 1995
• 4: Anton Beranek, Data Race Detection Based on Replay for Parallel Applications, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.109-114, September 01-04, 1992
• 5: CAVALHEIRO, G. AND DOREILLE, M. 1996. Athapascan: A C++ library for parallel programming. In Stratagem '96 (Sophia Antipolis, France, June). INRIA, Rennes, France.
• 6: Jong-Deok Choi , Sang Lyul Min, Race Frontier: reproducing data races in parallel-program debugging, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.145-154, April 21-24, 1991, Williamsburg, Virginia, United States
• 7: Jong-Deok Choi , Harini Srinivasan, Deterministic replay of Java multithreaded applications, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.48-59, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281041]
• 8: Koen de Bosschere , Michiel Ronsse, Clock Snooping and its Application in on-the-fly Data Race Detection, Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), p.324, December 18-20, 1997
• 9: Colin Fidge, Logical Time in Distributed Computing Systems, Computer, v.24 n.8, p.28-33, August 1991 [doi>10.1109/2.84874]
• 10: HOLLOMAN, E. D. 1989. Design and implementation of a replay debugger for parallel programs on unix-based systems. Master's Thesis. Computer Science Department, NC State, Raleigh, NC.
• 11: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• 12: Eric Leu , André Schiper , Abdelwahab Zramdini, Efficient execution replay technique for distributed memory architectures, Proceedings of the 2nd European conference on Distributed memory computing, p.315-324, April 1991, Munich, Germany
• 13: Luk Levrouw , Koenraad Audenaert , J. M. Van Campenhout, Execution Replay with Compact Logs for Shared-Memory Programs, Proceedings of the IFIP WG10.3 Working Conference on Applications in Parallel and Distributed Computing, p.125-134, April 18-22, 1994
• 14: LEVROUW, L. J., AUDENAERT, K. M., AND VAN CAMPENHOUT, J. M. 1994b. A new trace and replay system for shared memory programs based on Lamport Clocks. In Proceedings of the 2nd Euromicro Workshop on Parallel and Distributed Processing (Jan.). IEEE Computer Society Press, Los Alamitos, CA, 471-478.
• 15: Hsueh Lu , Philip N. Klein , Robert H.B. Netzer, Detecting Race Conditions in Parallel Programs That Use One Semaphore, Brown University, Providence, RI, 1996
• 16: MATTERN, F. 1989. Virtual time and global states of distributed systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms (Gers, France, Oct. 3-6), M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, Eds. North-Holland Publishing Co., Amsterdam, The Netherlands, 215-226.
• 17: 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]
• 18: Robert H. B. Netzer, Optimal tracing and replay for debugging shared-memory parallel programs, ACM SIGPLAN Notices, v.28 n.12, p.1-11, Dec. 1993
• 19: NETZER, R. H. B. AND MILLER, B. P. 1990. On the complexity of event ordering for shared-memory parallel program executions. In Proceedings of the International Conference on Parallel Processing (Aug.). 93-97.
• 20: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States
• 21: Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.74-88, March 1992 [doi>10.1145/130616.130623]
• 22: Dejan Perkovic , Peter J. Keleher, Online data-race detection via coherency guarantees, ACM SIGOPS Operating Systems Review, v.30 n.SI, p.47-57, Oct. 1996
• 23: Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996 [doi>10.1109/2.485846]
• 24: RONSSE, M. AND ZWAENEPOEL, W. 1997. Execution replay for TreadMarks. In Proceedings of the 5th Euromicro Workshop on Parallel and Distributed Processing. 343-350.
• 25: RONSSE, M., LEVROUW, L., AND BASTIAENS, K. 1995. Efficient coding of execution-traces of parallel programs. In Proceedings of the ProRISC/IEEE Benelux Workshop on Circuits, Systems and Signal Processing (Mar.), J. P. Veen, Ed. 251-258.
• 26: Mark Russinovich , Bryce Cogswell, Replay for concurrent non-deterministic shared-memory applications, ACM SIGPLAN Notices, v.31 n.5, p.258-266, May 1996
• 27: Sunil K. Sarin , Nancy A. Lynch, Discarding obsolete information in a replicated database system, IEEE Transactions on Software Engineering, v.13 n.1, p.39-47, Jan. 1987 [doi>10.1109/TSE.1987.232564]
• 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: D. Schonberg, On-the-fly detection of access anomalies, ACM SIGPLAN Notices, v.24 n.7, p.285-297, July 1989
• 30: Ariel Tamches , Barton P. Miller, Fine-grained dynamic instrumentation of commodity operating system kernels, Proceedings of the third symposium on Operating systems design and implementation, p.117-130, February 1999, New Orleans, Louisiana, United States
• 31: 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
• 32: Gene T.J. Wuu , Arthur J. Bernstein, Efficient solutions to the replicated log and dictionary problems, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.233-242, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806750]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

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

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
binary code modification, multithreaded programming, race detection