Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
1999-12-29
2004-10-12
Dam, Tuan (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S128000, C717S130000
Reexamination Certificate
active
06804814
ABSTRACT:
BACKGROUND OF THE INVENTION
With the proliferation of the internet and electronic commerce (“eCommerce”), businesses have begun to rely on the continuous operation of their computer systems. Even small disruptions of computer systems can have disastrous financial consequences as customers opt to go to other web sites or take their business elsewhere.
One reason that computer systems become unavailable is failure in the application or operating system code that runs on them. Failures in programs can occur for many reasons, including but not limited to, illegal operations such as dividing by zero, accessing invalid memory locations, going into an infinite loop, running out of memory, writing into memory that belongs to another user, accessing an invalid device, and so on. These problems are often due to program bugs.
Ayers, Agarwal and Schooler (hereafter “Ayers”), “A Method for Back Tracking Program Execution,” U.S. application Ser. No. 09/246,619, filed on Feb. 8, 1999, now U.S. Pat. No. 6,353,924, and incorporated by reference herein in its entirety, focuses on aiding rapid recovery in the face of a computer crash. When a computer runs an important aspect of a business, it is critical that the system be able to recover from the crash as quickly as possible, and that the cause of the crash be identified and fixed to prevent further crash occurrences, and even more important, to prevent the problem that caused the crash from causing other damage such as data corruption. Ayers discloses a method for recording a sequence of instructions executed during a production run of the program and outputting this sequence upon a crash.
Traceback technology is also important for purposes other then crash recovery, such as performance tuning and debugging, in which case some system event or program event or termination condition can trigger the writing out of an instruction trace.
The preferred method for traceback disclosed by Ayers is binary instrumentation in which code instrumentation is introduced in an executable. The instrumentation code writes out the trace.
SUMMARY OF THE INVENTION
In an improvement to the traceback technology of Ayer, an embodiment of the present invention records data values loaded or stored by the program as well as the instructions in one or more circular buffers. These buffers are dumped upon a crash, providing a user with a data and instruction trace. The data values are often very useful in reconstructing the cause of the crash.
Recording the data values often can significantly slow a program down. The present invention mitigates this problem by using a traceback instruction sequence to guide a backward simulation of the execution, recording in a file the sequence of all computable data values starting with the final values contained in a final value set. Of course, after some point, it is possible that data values cannot be computed. Thus, this technique is approximate, and the previous data history it yields is limited.
As an example, assume a procedure receives an argument value A, which is incremented by 1 three times in the procedure. Given a value of A from a recorded value set, previous values of A can be reconstructed by subtracting 1 from the current value of A whenever an instruction incrementing the value of A is encountered. These intermediate values are recorded in a data trace. Thus, the initial value of the argument A upon entering the procedure is obtained.
In an alternate embodiment, forward simulation, using the trace and an intermediate value set, is used
In addition, the same set of values is recorded at intermittent intervals of time. These are intermediate-value-sets.
The final values of all the registers, the stack, and memory are recorded. This is called the final-value-set.
Upon a crash, system level parameters and values are stored. These include the names and identifiers of other processes running on the same machine at the point of the crash, the names and identifiers of other processes running on other machines in a distributed networked environment at the point of the crash, the set of files in use by the failed process, and system level parameters at the point of the crash such as CPU utilization, active pages, size of swapped data, etc.
Therefore, in accordance with an embodiment of the present invention, a method for creating a program execution data trace, comprises recording a first value set associated with the execution of a first instruction referenced in an instruction trace. For a second instruction referenced in the instruction trace, and responsive to the first value set, a second value set is determined by simulating instructions from the first instruction to the second instruction according to the instruction trace.
Preferably, the program is instrumented to record the value sets. Either the program source or the program binary can be instrumented. The instrumentor itself can be part of a compiler.
The instrumented instruction and the second instruction are different execution instances but can be the same statement or different statements within the program.
In a further embodiment, determining the second value set is responsive to a control flow graph or representation of the program.
In one embodiment, the second instruction executes before the first instruction, possibly immediately prior to the first instruction, such that instructions are simulated backward from the first instruction to the second instruction.
In one embodiment, a table is maintained which associates program instructions encountered in the instruction trace with simulation instructions which reverse the operation of the of the associated program instructions. Thus the associated instruction is “back-simulated.”
The instruction trace can be examined for a previous computation of an unknown value. For example, the previous computation can be an immediate previous dominator of the “current” instruction found by searching backwards through the instruction trace. Alternatively, the previous computation can be determined by using a static analysis of the program to find the immediate dominator of an instruction, where there are no intervening instructions impacting the value of the variable.
The first value set can be a final value set, which can be recorded responsive to a program crash. A final value set can comprise system level parameters and values, such as but not limited to the names and identifiers of other processes running on the same machine at the time of recording, the names and identifiers of other processes running on other machines in a distributed networked environment at the time of recording, the set of files in use by the program at the time of recording, CPU utilization information at the time of recording, active pages at the time of recording and/or a size of swapped data at the time of recording.
The first value set can also be an intermediate value set, such as is recorded by instrumented code at regular or other intervals, upon a predetermined or user-specified event. An event can be, for example, the loading or storing of a value.
In an alternate embodiment, the second instruction executes after the first instruction, for example, immediately after the first instruction, such that instructions are simulated forward from the first instruction to the second instruction. The first value set can be an intermediate value set as with backward simulation, or an initial value set, recorded, for example, upon entering a routine.
In a further embodiment, a probe is inserted into the program to save a value of a particular variable at a particular instruction in the program. Examples of values a probe might record include, but are not limited to, values returned from calls such as system calls, values returned from I/O calls, for example, those from a user input to a web form and values obtained from database records.
Probes are used to determine values where the value is not determinable by the usual backward or forward simulation. In one embodiment, simulating a simulate-backward or -forward process is itself simulated, for exampl
Agarwal Anant
Ayers Andrew E.
Schooler Richard
Dam Tuan
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
VERITAS Operating Corporation
Vo Ted T.
LandOfFree
Method for simulating back program execution from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for simulating back program execution from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for simulating back program execution from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3317643