Dynamic binary translator with a system and method for updating and maintaining coherency of a translation cache

• US 6,704,925 B1
• Filed: 12/01/1998
• Issued: 03/09/2004
• Est. Priority Date: 09/10/1998
• Status: Expired due to Term

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Bugnion, Edouard
• Primary Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US09/203,825
• Time in Patent Office: 1,925 Days
• Field of Search: 703/23, 703/26, 703/27, 709/1, 717/127-130, 717/134-139, 717/148
• US Class Current: 717/138
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation
• CPC Class Codes: G06F 9/45554 Instruction set architectures of guest OS and hypervisor or native processor differ, e.g. Bochs or VirtualPC on PowerPC MacOS

Abstract

A dynamic binary translator converts input instruction sequences into output instruction sequences that are stored in a translation cache. In order to maintain coherence of the translation cache with the run-time version of the input instructions, translated code is checked by either a conflict detection mechanism or a code-invariance mechanism. For conflict detection, the system preferably uses memory traces generated by the memory management unit of the underlying hardware processor. In order to check for code-invariance, preludes for comparing cached, output instruction sequences with their supposed run-time input instruction equivalents are appended to the cached instructions themselves. Changes in the input sequences then result only in retranslation of instruction sequences in which at least one instruction has changed; this avoids costly total flushes of the translation cache. An additional prelude is appended to any cached output sequences displaying characteristics of potentially self-constant-modifying code. If the input instructions have since translation changed with respect only to constants, then the constants are updated before execution; this completely eliminates the need for flushing the translation cache or retranslating the instruction if only constants have changed since the original translation. The invention is preferably incorporated in a virtual machine monitor, on which a virtual machine is running.

Claims

1. A method for virtualizing a computer using binary translation comprising the following steps:

converting by binary translation input instruction sequences into output instruction sequences that emulate the corresponding input instruction sequences, the input instruction sequences being stored in predetermined pages of a system memory;

storing the output instruction sequences in a translation cache;

maintaining coherency of the output instruction sequence with the input instruction sequence by selectively executing the following sub-steps;

detecting conflicts in the memory pages in which a first set of the input instruction sequences is stored and executing the corresponding output instruction sequences only in the absence of detected conflicts; and

by explicitly checking for code-invariance by checking for post-translation changes in a second set of input instruction sequences by comparing the copied input instruction sequences with a current version of the corresponding input instruction sequence, before executing the corresponding output instruction sequence.

2. A method as in claim 1, in which the step of detecting conflicts includes the sub-step of setting a hardware memory management unit (MMU) of the computer to detect memory traces on the memory pages in which the first set of the input instruction sequences is stored.

3. A method as in claim 1, in which the step of checking for post-translation changes includes the following sub-steps:

storing a translation-time copy of each input instruction sequence in the second set of instruction sequences;

appending to each output instruction sequence for which there is a translation-time copy an instruction invariance prelude and storing the instruction invariance prelude in the translation cache along with the corresponding output instruction sequence;

for each output instruction sequence for which there is an instruction invariance prelude, executing the instruction invariance prelude before executing the corresponding output instruction sequence;

the sub-step of executing the instruction invariance prelude comprising the further sub-steps of;

comparing the corresponding translation-time copy of the input instruction sequence with a corresponding current state of the input sequence; and

executing the output instruction sequence only when the current state is the same as the translation-time copy.

4. A method as in claim 3, in which the step of storing the translation-time copy of each input instruction sequence comprises encoding the translation-time copy as an immediate operand of compare instructions in corresponding ones of the instruction invariance preludes.

5. A method as in claim 3, further including the step of reconverting by binary translation only the input instruction sequence for which the current state is different from the translation-time copy.

6. A method as in claim 3, further comprising the following steps:

for each output instruction in an output instruction sequence for which the current state is different from the translation-time copy, detecting whether the output instruction sequence is self-constant-modifying.

7. A method as in claim 6, further comprising the step of reconverting by binary translation only the input instruction sequence for which the current state of operation portions of each instruction included in the sequence is different from a corresponding portion in the translation-time copy.

8. A method as in claim 7, further comprising the following steps:

a) checking for run-time invariance of the operational instruction portion by executing a code-invariance prelude that is appended to the output instruction as stored in the translation cache;

b) for each input instruction sequence for which the current state of the operational portions is the same as corresponding portions in the translation-time copy;

i) executing a constant-updating prelude that is appended to the output instruction and thereby updating the modifiable constant portion of the output instruction by replacing it with a corresponding run-time constant portion of the input instruction in the current state; and

ii) executing the output instruction using the updated modifiable constant portion.

9. A method as in claim 1, further comprising the step of switching between conflict detection and code-invariance checking of the input instruction sequences according to a predetermined memory page cost optimization function, which is evaluated for each memory page that contains input instructions.

10. A system for virtualizing a computer comprising:

binary translation means for converting by binary translation input instruction sequences into output instruction sequences that emulate the corresponding input instruction sequences, the input instruction sequences being stored in predetermined pages of a system memory;

a translation cache in which the output instruction sequences are stored;

means for maintaining coherency of the output instruction sequence with the input instruction sequence and, selectively;

for detecting conflicts in the memory pages in which a first set of the input instruction sequences is stored and executing the corresponding output instruction sequences only in the absence of detected conflicts; and

for explicitly checking for code-invariance by checking for post-translation changes in a second set of input instruction sequences by comparing the copied input instruction sequences with a current version of the corresponding input instruction sequence, before executing the corresponding output instruction sequence.

11. A system as in claim 10, in which the computer includes a memory management unit (MMU), further comprising conflict detection means for setting the hardware memory management unit (MMU) of the computer to detect memory traces on the memory pages in which the first set of the input instruction sequences is stored.