Framework for instruction-level tracing and analysis of program executions

ABSTRACT

Program execution traces provide the most intimate details of a program's dynamic behavior. They can be used for program optimization, failure diagnosis, collecting software metrics like coverage, test prioritization, etc. Two major obstacles to exploiting the full potential of information they provide are: (i) performance overhead while collecting traces, and (ii) significant size of traces even for short execution scenarios. Reducing information output in an execution trace can reduce both performance overhead and the size of traces. However, the applicability of such traces is limited to a particular task. We present a runtime framework with a goal of collecting a complete, machine- and task-independent, user-mode trace of a program's execution that can be re-simulated deterministically with full fidelity down to the instruction level. The framework has reasonable runtime overhead and by using a novel compression scheme, we significantly reduce the size of traces. Our framework enables building a wide variety of tools for understanding program behavior. As examples of the applicability of our framework, we present a program analysis and a data locality profiling tool. Our program analysis tool is a time travel debugger that enables a developer to debug in both forward and backward direction over an execution trace with nearly all information available as in a regular debugging session. Our profiling tool has been used to improve data locality and reduce the dynamic working sets of real world applications.

REFERENCES

• 1: Andrew Ayers , Richard Schooler , Chris Metcalf , Anant Agarwal , Junghwan Rhee , Emmett Witchel, TraceBack: first fault diagnosis by reconstruction of distributed control flow, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 2: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 3: T. C. Bressoud , F. B. Schneider, Hypervisor-based fault tolerance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.1-11, December 03-06, 1995, Copper Mountain, Colorado, United States
• 4: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 5: Martin Burtscher , Ilya Ganusov , Sandra J. Jackson , Jian Ke , Paruj Ratanaworabhan , Nana B. Sam, The VPC Trace-Compression Algorithms, IEEE Transactions on Computers, v.54 n.11, p.1329-1344, November 2005 [doi>10.1109/TC.2005.186]
• 6: Wen-Ke Chen, Sorin Lerner, Ronnie Chaiken, and David Gillies, Mojo: a dynamic optimization system, ACM Workshop on Feedback-Directed and Dynamic Optimization (2000), 81--90.
• 7: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Bob Cmelik , David Keppel, Shade: a fast instruction-set simulator for execution profiling, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.128-137, May 16-20, 1994, Nashville, Tennessee, United States
• 9: Manuel Costa , Jon Crowcroft , Miguel Castro , Antony Rowstron , Lidong Zhou , Lintao Zhang , Paul Barham, Vigilante: end-to-end containment of internet worms, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 10: Giuseppe Desoli , Nikolay Mateev , Evelyn Duesterwald , Paolo Faraboschi , Joseph A. Fisher, DELI: a new run-time control point, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 11: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060309]
• 12: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 13: Kim Hazelwood , James E. Smith, Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.89, March 20-24, 2004, Palo Alto, California
• 14: Samuel T. King, George W. Dunlap, and Peter M. Chen, Debugging operating systems with time-traveling virtual machines, USENIX Annual Technical Conference (2005), 1--15.
• 15: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 16: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 17: 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, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 18: 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
• 19: Nicholas Nethercote and Julian Seward, Valgrind: a program supervision framework, Electronic Notes in Theoretical Computer Science 89 (2003), no. 2.
• 20: James E. Smith and Ravi Nair, Virtual machines, first ed., Morgan Kaufman, San Francisco, Ca., 2005.
• 21: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 22: Amitabh Srivastava, Hoi Vo, and Andrew Edwards, Vulcan: binary transformation in distributed environment, Tech. Report MSR-TR-2001-50, Micorosft Research, April 2001.
• 23: 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
• 24: Xiangyu Zhang , Rajiv Gupta, Whole execution traces and their applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.3, p.301-334, September 2005 [doi>10.1145/1089008.1089012]

INDEX TERMS

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

General Terms:
Algorithms, Design, Verification

Keywords:
callback, code emulation, code replay, time-travel debugging, tracing