Method for back tracing program execution
First Claim
1. A method of back-tracing execution of a computer program, said computer program comprising a plurality of blocks, said method comprising:
- identifying the blocks of the computer program;
instrumenting an original version of the program by adding instrumentation code to identified blocks to form an instrumented program, the instrumentation code recording execution sequence information upon execution of the corresponding instrumented block, such that cumulative sequence information recorded during execution of the program forms a sequence record;
recording a sequence record of the program by executing the instrumented program; and
upon occurrence of a triggering event, processing the recorded sequence record to form a trace record, wherein sequence information in the recorded sequence record is translated into at least one program counter value of an instruction within an instrumented block whose execution caused the sequence information to be recorded.
7 Assignments
0 Petitions
Accused Products
Abstract
A method of back-tracing execution of a computer program, where the computer program comprises a plurality of blocks, comprises instrumenting an original version of the program by adding instrumentation code to some or all of the blocks to form an instrumented program. Instrumentation can be added at the binary or source level, or at link time. The instrumentation code records execution sequence information upon execution of the corresponding instrumented block to create a trace record of the executed program. The execution sequence information for each block comprises a block identifier which identifies the corresponding block. A detailed back-trace is generated, after the program has executed, by replacing each recorded block identifier with program counters associated with each instruction in the corresponding block. The application may comprise several programs or subprograms, in which case separate regions of memory can be maintained. Each region is associated with a program or subprogram or a set of programs or subprograms and stores therein part of the trace record corresponding to the associated set of programs or subprograms. The trace records themselves may be of different types. After execution, the trace record is presented to a user, in the form of assembly code, or more preferably, in the form of source level code. In an alternative embodiment, a summary of the trace record recorded during execution of an instrumented program is presented to a user. Various types of traces can be produced, including a last instruction trace and a first instruction trace.
191 Citations
73 Claims
-
1. A method of back-tracing execution of a computer program, said computer program comprising a plurality of blocks, said method comprising:
-
identifying the blocks of the computer program;
instrumenting an original version of the program by adding instrumentation code to identified blocks to form an instrumented program, the instrumentation code recording execution sequence information upon execution of the corresponding instrumented block, such that cumulative sequence information recorded during execution of the program forms a sequence record;
recording a sequence record of the program by executing the instrumented program; and
upon occurrence of a triggering event, processing the recorded sequence record to form a trace record, wherein sequence information in the recorded sequence record is translated into at least one program counter value of an instruction within an instrumented block whose execution caused the sequence information to be recorded. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46)
replacing each recorded block identifier with program counters associated with each instruction in the corresponding block.
-
-
6. The method of claim 2 further comprising:
using Huffman coding to allocate block identifiers.
-
7. The method of claim 2, further comprising:
recording a block identifier in a condensed representation, wherein the condensed representation holds a plurality of block identifiers.
-
8. The method of claim 7, wherein the condensed representation is stored in a register.
-
9. The method of claim 7, wherein the condensed representation is stored in a memory location.
-
10. The method of claim 7, wherein the condensed representation uses logn2 bits to encode a path for each n-way branch in the program.
-
11. The method of claim 7, wherein the size of the condensed representation for any path makes use of an expected frequency with which that path is taken.
-
12. The method of claim 7, wherein the condensed representation uses path encoding.
-
13. The method of claim 7, further comprising:
expanding the condensed representation by storing the individual block identifiers contained therein into the sequence record.
-
14. The method of claim 1, wherein recording the sequence information into the sequence record comprises storing the sequence information in memory.
-
15. The method of claim 14, wherein the sequence record is stored in a region of memory separate from where the program is stored.
-
16. The method of claim 14, wherein the sequence record is stored in a circular buffer.
-
17. The method of claim 16, wherein the buffer size is dynamically set.
-
18. The method of claim 14, wherein the program comprises plural programs/subprograms, and wherein separate regions of memory are maintained, each region being associated with a program/subprogram for storing therein part of the sequence record corresponding to the associated program/subprogram.
-
19. The method of claim 1, wherein recording the sequence information into the sequence record comprises storing the sequence information to a file.
-
20. The method of claim 1 wherein the program'"'"'s source code is instrumented.
-
21. The method of claim 1 wherein instrumenting the program occurs at a link level.
-
22. The method of claim 1 wherein the program'"'"'s binary code is instrumented.
-
23. The method of claim 1, further comprising:
presenting the trace record to a user.
-
24. The method of claim 23, wherein the trace record is presented in the form of assembly code.
-
25. The method of claim 23, wherein the trace record is presented in the form of source level code.
-
26. The method of claim 25 further comprising:
maintaining, for each binary-level instruction, a pointer to a line of source code from which the binary-level instruction was generated.
-
27. The method of claim 26, wherein the pointer is determined from a compiler listing file.
-
28. The method of claim 26, further comprising:
filtering out repeat source level instructions.
-
29. The method of claim 1, further comprising:
presenting a summary of the trace record to a user.
-
30. The method of claim 29, wherein presenting a summary further comprises:
presenting basic block lines identified in the trace record.
-
31. The method of claim 29, wherein presenting a summary further comprises:
presenting procedure calls identified in the trace record.
-
32. The method of claim 29, wherein presenting a summary further comprises:
presenting inter-module or inter-program calls identified in the trace record.
-
33. The method of claim 1, further comprising:
maintaining a table, the table comprising a plurality of entries, each entry corresponding to a program block.
-
34. The method of claim 33, wherein each entry is addressed by a hash of its corresponding block'"'"'s program counter.
-
35. The method of claim 33, wherein the instrumentation code produces a last instruction trace by recording a sequence indicator when recording the block identifier.
-
36. The method of claim 35, wherein the sequence indicator is a time-stamp.
-
37. The method of claim 36, wherein the time-stamp is recorded upon entry into the corresponding block.
-
38. The method of claim 36, wherein the time-stamp is recorded upon exit from the corresponding block.
-
39. The method of claim 35, wherein the sequence indicator is a counter value, further comprising:
incrementing the counter value after recording its value.
-
40. The method of claim 39, further comprising:
maintaining a separate counter for each module, subprogram or procedure.
-
41. The method of claim 39, wherein when the counter value reaches a preset limit, a time-stamp is recorded in place of the counter value.
-
42. The method of claim 33, wherein the instrumentation code produces a first instruction trace by recording a sequence indicator for a corresponding block only the first time the block is executed.
-
43. The method of claim 1, wherein sequence information is stored only when a specified event is detected by the instrumentation code.
-
44. The method of claim 43, wherein the specified event is selected by a user.
-
45. The method of claim 1, wherein an application comprises multiple programs, wherein presenting the instruction trace to a user further comprises:
displaying, in the trace record, a program name corresponding to an instruction trace entry.
-
46. The method of claim 1, further comprising:
storing any or all of a crash instruction trace, a first instruction trace, and a last instruction trace.
-
47. A computer memory configured for back-tracing execution of a computer program, said computer program comprising a plurality of identified blocks, comprising:
-
a trace record instrumenter for instrumenting an original version of the program by adding instrumentation code to identified blocks to form an instrumented program, the instrumentation code recording execution sequence information upon execution of the corresponding instrumented block, such that cumulative sequence information recorded during execution of the program forms a sequence record;
a post-processor for transforming, upon occurrence of a triggering event, the sequence record recorded during an execution of the program into a trace record, wherein sequence information in the sequence record is transformed into at least one program counter value of an instruction within an instrumented block whose execution caused the sequence information to be recorded; and
a trace record presenter for presenting the trace record. - View Dependent Claims (48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73)
recording a block identifier in a condensed representation, wherein the condensed representation holds a plurality of block identifiers.
-
-
52. The computer memory of claim 48, wherein the program may comprise several programs or subprograms, and wherein separate regions of memory are maintained, each region being associated with a program or subprogram for storing therein sequence information corresponding to the associated program or subprogram.
-
53. The computer memory of claim 48, wherein the trace record instrumenter instruments the program'"'"'s source code.
-
54. The computer memory of claim 48, wherein the trace record instrumenter instruments the program'"'"'s binary code.
-
55. The computer memory of claim 47, wherein the trace record presenter presents the trace record in the form of assembly code.
-
56. The computer memory of claim 47, wherein the trace record presenter presents the trace record in the form of source level code.
-
57. The computer memory of claim 56, further comprising:
for each binary-level instruction, a pointer to a line of source code from which the binary-level instruction was generated.
-
58. The computer memory of claim 57, wherein each pointer is determined from a compiler listing file.
-
59. The computer memory of claim 47, wherein the trace record presenter presents a summary of the sequence information.
-
60. The computer memory of claim 59, wherein the summary comprises procedure calls identified in the sequence information.
-
61. The computer memory of claim 59, wherein the summary comprises inter-module or inter-program calls identified in the sequence information.
-
62. The computer memory of claim 47, further comprising:
a table comprising a plurality of entries, each entry corresponding to a program block.
-
63. The computer memory of claim 62, wherein the instrumented code produces a last instruction trace by recording a sequence indicator when recording the block identifier.
-
64. The computer memory of claim 63, wherein the sequence indicator is a time-stamp.
-
65. The computer memory of claim 64, wherein the time-stamp is recorded upon entry into the corresponding block.
-
66. The computer memory of claim 63, further comprising:
a counter whose current value is taken as the sequence indicator, wherein the counter is incremented after its value is recorded.
-
67. The computer memory of claim 66, further comprising:
a separate counter for each module, subprogram or procedure.
-
68. The computer memory of claim 66, wherein when the counter value reaches a preset limit, a time-stamp is recorded in place of the counter'"'"'s value.
-
69. The computer memory of claim 62, wherein the instrumented code produces a first instruction trace by recording a sequence indicator for a corresponding block only the first time the block is executed.
-
70. The computer memory of claim 47, wherein sequence indicators are stored only when a specified event is detected by the instrumented code.
-
71. The computer memory of claim 47, wherein an application comprises multiple programs, such that, for each line displayed, the trace record presenter presents, in the trace record, a program name corresponding to an instruction trace entry.
-
72. The computer memory of claim 47, wherein the post-processor is triggered by a specified event.
-
73. The computer memory of claim 72, wherein the specified event occurs when the instrumented code detects a designated condition.
Specification