Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-12-01
2004-03-09
Courtenay, III, St. John (Department: 2126)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C709S241000, C703S026000
Reexamination Certificate
active
06704925
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a dynamic binary translator, which may be used in a virtual machine monitor to virtualize a computer system or an emulator that simulates a computer system.
2. Description of the Related Art
Binary translation is a technique that allows the execution of binary codes for a first architecture (the simulated architecture) on a second architecture (the host architecture). Binary translators between different architectures are known as cross-architectural. The two architectures may, however, be identical. In this latter case, the binary translation is often used to instrument an executable instruction so that the execution of the program provides additional information about its execution.
Binary translators provide a performance advantage over software interpreters. Software interpreters simulate in software the fetch-decode-execute cycle of the simulated architecture by reading each instruction one at a time and simulating its execution. Binary translators offer superior performance by taking groups of instructions (or even the entire program) and generating a corresponding sequence that executes directly on the host processor. Binary translators fall into two main categories—static and dynamic.
Static binary translators perform the translation of the original instruction sequence before the execution of the program. In their seminal paper “Binary translation” (Communication of the ACM Volume 36, 1993), Sites, et al., give a good introduction to the topic of static binary translators. Certain translators, known as closed translation systems, require that all of the instructions that the program eventually executes must be known at translation time; one example of such a translator is the binary editing ATOM system described by Alan Eustace and Amitabh Srivastava in “ATOM: A Flexible Interface for Building High Performance Program Analysis Tools,” Digital WRL Technical Note 44.
Other binary translators, known as open translation systems, attempt to translate as much of the code as possible and revert to a slower software emulator for the portions that have not been translated. This is the case in the VAX-to-Alpha translator described by Sites, et al., and also in the FX!32 system from Compaq/DEC that translates x86 binaries to Alpha.
Dynamic binary translators perform the translation from an original instruction sequence to a host instruction sequence during the execution of the program. The translated code sequences are then stored in a buffer called the translation cache. The binary translation function is interleaved with the execution of the output of the binary translator. Dynamic binary translators have been used in architectural simulators such as Shade (See Cmelik and Keppel, “Shade: A Fast Instruction-Set Simulator for Execution Profiling,” SIGMetrics '94) and machine simulators such as SimOS (see Witchel and Rosenblum, “Embra: Fast and Flexible Machine Simulation,” ACM SIGMetrics '96). Dynamic binary translators have also been used to build virtual machine monitors (see Ebcioglu and Altman, “DAISY: Dynamic Compilation for 100% Architectural Compatibility,” IBM Research Report #20538). Dynamic binary translators are also used to build fast Java Virtual Machines; in that context, they are sometimes referred to as “just-in-time compilers.”
A dynamic binary translator is also used to provide cross-architectural compatibility as described in U.S. Pat. No. 5,832,205 (“Memory Controller for a Microprocessor for Detecting a Failure of Speculation on the Physical Nature of a Component Being Addressed,” Kelly, et al.). In the discussion below, this system is referred to as the “Transmeta” system.
Binary translators share one common problem not found in simpler software interpreters: the execution of the translated code sequence can lead to a correct execution of the program only if the original sequence that it emulates has not been modified since its translation. Certain systems, including most static translators and some dynamic translators assume that such modifications don't occur; these systems ignore the problem rather than solve it. More recent dynamic binary translators such as SimOS, DAISY, and the Transmeta processor, however, guarantee the coherency of the translations that have been generated and are stored in the translation cache. In effect, they solve the translation cache coherency problem, but they do so using a technique referred to below as “conflict detection.” This technique has the disadvantage that it leads to poor performance in a wide range of cases. The technique of conflict detection is discussed in greater detail below.
Rather than simulating CPUs by interpreting an instruction sequence one instruction at a time, dynamic binary translators thus translate blocks of instructions into code that, when executed, emulate the execution of the original block. The translated blocks are then stored into a memory buffer for further reuse. The use of binary translation eliminates most of the overheads of software interpretation.
A basic binary translation system according to the prior art is illustrated in FIG.
1
. As
FIG. 1
illustrates, a conventional binary translation system typically consists of a translator
100
, a chaining subsystem
110
, an access module
120
, and various callout routines. By way of example, two callout routines—for privilege emulation
130
and I/O
132
—are illustrated.
The translator converts blocks
140
of instructions received as input from a virtual machine (VM)
142
or other emulated system into a sequence of instructions that run on the host architecture. The generated code (or emitted code) is then stored into a memory buffer known as a translation cache (TC)
150
. In
FIG. 1
, three translated and stored code sequences are illustrated as blocks labeled A, B and C.
Callout routines are functions of the simulation system or virtual machine monitor that can be called by the code emitted by the translator. The translator inserts direct or indirect calls to these functions into the emitted code. Callout routines are used, for example, to emulate certain instructions with complicated semantics. In
FIG. 1
, code block A is shown as having a callout to both routines
130
and
132
.
The chaining subsystem is a mechanism that allows an emitted instruction sequence to directly branch to another emitted sequence, without relying on more than one callout (the callout to the chaining subsystem itself). In
FIG. 1
, the chaining module
110
is shown as having inserted a branch or “patch” (symbolized by an asterisk *) between code blocks B and C within the TC
150
. This is an optimization over a naive implementation in which all emitted code blocks always end with a callout to a routine that looks up the translation of the next basic block.
The idea behind binary translation is the reuse of previously generated translations. The access module
120
determines the location in the TC
150
, if one is to be found, of the translation that corresponds to the start of a given instruction sequence. If no translation is found, then the access module transfers control to the translator to generate a translation.
This basic design of a binary translation system relies on the invariance of the code, that is, the instruction sequences, that served as the input to the binary translator. If the content of the program stored in the memory of the simulated system or virtual machine changes during the execution, then the cached translations that emulate the behavior of the modified instructions are typically discarded, effectively forcing the translator to re-translate the instruction sequence a second time.
Early binary translators such as Shade effectively ignored the problem of possible code variance, since it did not occur in the cases for which Shade was designed. More recent systems such as SimOS and DAISY, however, address and solve the problem by detecting inconsistencies and taking appropriate actions in the case of a violation of translat
Courtenay III St. John
Pearce Jeffrey
VMware, Inc.
LandOfFree
Dynamic binary translator with a system and method for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic binary translator with a system and method for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic binary translator with a system and method for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266551