Method and system for performing virtual to physical address translations in a virtual machine monitor

• US 7,069,413 B1
• Filed: 01/29/2003
• Issued: 06/27/2006
• Est. Priority Date: 01/29/2003
• Status: Expired due to Term

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Agesen, Ole, Subrahmanyam, Pratap
• Primary Examiner(s): Peikari, B. James
• Assistant Examiner(s): Choi, Woo H.
• Application Number:
  US10/354,556
• Time in Patent Office: 1,245 Days
• Field of Search: 711/6, 711/207
• US Class Current: 711/207
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 2212/682 Multiprocessor TLB consistency

Abstract

The invention is used in a virtual machine monitor for a multiprocessing system that includes a virtual memory system. During a software-based processing of a guest instruction, including translating or interpreting a guest instruction, mappings between virtual addresses and physical addresses are retained in memory until processing of the guest instruction is completed. The retained mappings may be cleared after each guest instruction has been processed, or after multiple guest instructions have been processed. Information may also be stored to indicate that an attempt to map a virtual address to a physical address was not successful. The invention may be extended beyond virtual machine monitors to other systems involving the software-based processing of instructions, and beyond multiprocessing systems to other systems involving concurrent access to virtual memory management data.

Claims

1. A method for attempting to determine memory mappings between virtual addresses and physical addresses in a Virtual Machine Monitor (VMM), the VMM running on a physical computer having a plurality of physical processors and implementing a virtual memory system that is used by the physical processors, the method being used during a software-based processing of one or more guest instructions, the processing of the one or more guest instructions requiring one or more guest memory mappings, the method comprising:

(A) establishing a data store for memory mappings between virtual addresses and physical addresses that is separate from the virtual memory system used by the physical processors;

(B) for one or more of the required memory mappings, performing the following steps;

(1) searching the data store for a virtual address for the required memory mapping, and performing the following step;

(2) if a matching virtual address is not found, performing the following steps;

(a) attempting to establish the required memory mapping according to the virtual memory system used by the physical processors;

(b) if the required memory mapping is established according to the virtual memory system, using the established memory mapping, and adding an entry to the data store indicating the established memory mapping for the virtual address and retaining the established memory mapping at least until the software-based processing of a current guest instruction is completed; and

(c) if the required memory mapping is not established according to the virtual memory system, using no memory mapping, and adding an entry to the data store indicating that a memory mapping was not found for the virtual address; and

(3) if a matching virtual address is found, performing the following steps;

(a) if an entry containing the matching virtual address indicates that a memory mapping was not found for the virtual address, using no memory mapping; and

(b) if an entry containing the matching virtual address indicates that a memory mapping was found for the virtual address, using the memory mapping indicated in the entry; and

(C) upon completing the processing of one or more guest instructions, invalidating all entries in the data store.

2. The method of claim 1, wherein the software-based processing of guest instructions comprises interpreting the guest instructions.

3. The method of claim 2, wherein the memory mappings are cleared from the data store after each guest instruction is interpreted.

4. The method of claim 1, wherein the software-based processing of guest instructions comprises translating the guest instructions.

5. The method of claim 4, wherein the memory mappings are cleared from the data store after a group of one or more guest instructions is translated.

6. The method of claim 1, wherein the step of attempting to establish the required memory mapping according to the virtual memory system used by the physical processors comprises attempting to find the required memory mapping in one or more page tables.

7. The method of claim 1, wherein the step of invalidating all entries in the data store involves resetting a counter that counts the number of valid entries in the data store, and wherein the counter is incremented each time a valid entry is added to the data store.

8. The method of claim 1, wherein the step of searching the data store for a virtual address for the required memory mapping comprises sequentially checking each valid entry in the data store for the virtual address.

9. The method of claim 1, wherein the steps (1), (2) and (3) are performed for every guest memory mapping during the software-based processing of guest instructions.

10. The method of claim 1, wherein the step of adding an entry to the data store indicating the established memory mapping comprises adding physical address information to the entry, and wherein the step of adding an entry to the data store indicating that a memory mapping was not found for the virtual address comprises adding a negative value to the entry instead of adding physical address information.

11. A method for determining memory mappings between virtual addresses and physical addresses during a software-based processing of an instruction in a computer system having a virtual memory system, in which multiple devices have concurrent access to virtual memory management data, the method comprising:

for a first attempt at establishing a memory mapping, attempting to establish a memory mapping for a first virtual address according to the virtual memory system;

if a first memory mapping is established for the first virtual address according to the virtual memory system during the processing of the instruction, retaining the first memory mapping until processing of the instruction has completed;

if a memory mapping is not established for the first virtual address according to the virtual memory system during the processing of the instruction, retaining information indicating a failure to establish a memory mapping for the first virtual address until processing of the instruction has completed; and

for a subsequent attempted memory mapping;

if a stored virtual address for a retained memory mapping matches a second virtual address for the subsequent attempted memory mapping, using the retained memory mapping instead of attempting to establish a new memory mapping for the second virtual address according to the virtual memory system; and

if retained information indicates a failure to establish a memory mapping for the second virtual address, using no memory mapping instead of attempting to establish a new memory mapping for the second virtual address according to the virtual memory system.

12. The method of claim 11, further comprising establishing a data store for retained memory mappings, which is retained separately from the virtual memory system, which is used by a physical processor in the computer system.

13. The method of claim 12, further comprising searching the data store for a retained memory mapping that matches the second virtual address for the subsequent attempted memory mapping and, if a matching retained memory mapping is not found, attempting to establish a new memory mapping for the second virtual address for the subsequent attempted memory mapping according to the virtual memory system used by the physical processor or, if a matching retained memory mapping is found, using the retained memory mapping instead of attempting to establish a new memory mapping for the second virtual address for the subsequent attempted memory mapping according to the virtual memory system.

14. The method of claim 11, further comprising a step of invalidating all retained memory mappings upon completion of the software-based processing of the instruction.

15. The method of claim 11, wherein the software-based processing of the instruction comprises interpreting the instruction.

16. The method of claim 11, wherein the multiple devices having concurrent access to virtual memory management data comprise multiple physical processors.

17. The method of claim 11, wherein the multiple devices having concurrent access to virtual memory management data comprise multiple logical processors.

18. A computer program embodied in a tangible computer readable medium, the computer program being executable in a computer system in which multiple devices have concurrent memory access, the computer program comprising:

a software-based instruction processor for enabling the execution of an instruction as if the instruction were executed on a virtualized computer system, the computer system having a virtual memory system, the execution of the instruction requiring multiple memory accesses to access code and data related to the instruction, each of a plurality of the multiple memory accesses requiring a memory mapping from a virtual address to a physical address in accordance with the virtual memory system; and

a plurality of mapping-data storage locations for storing memory mappings between virtual addresses and physical addresses during the software-based processing of the instruction,

wherein, when the instruction processor is processing the instruction, for each of the plurality of memory accesses that require a memory mapping, the instruction processor attempts to establish the required memory mapping by determining whether the mapping-data storage locations contain an entry that matches a virtual address of the required memory mapping and,

if the instruction processor finds a matching entry in the mapping-data storage locations, the instruction processor uses a stored memory mapping from the matching entry, instead of attempting to establish the required memory mapping according to the virtual memory system,

if the instruction processor does not find a matching entry in the mapping-data storage locations, the instruction processor attempts to establish the required memory mapping according to the virtual memory system and, if the required mapping is established, adding an entry to the mapping-data storage locations indicating the established memory mapping and retaining the entry until the software-based processing of the instruction is completed,

if the instruction processor does not find a matching entry in the mapping-data storage locations and the required memory mapping is not established according to the virtual memory system, adding an entry to the mapping-data storage locations indicating that the required memory mapping was not established for the virtual address and retaining the entry until the processing of the instruction is completed, and

if the instruction processor finds a matching entry in the mapping-data storage locations, but the entry indicates that a memory mapping was not established for the virtual address, using no memory mapping instead of attempting to establish the required memory mapping according to the virtual memory system.

19. The computer program of claim 18, wherein the computer program is executable in a multiprocessor computer system.

20. The computer program of claim 18, wherein the software-based instruction processor is an interpreter, which interprets the instruction.

21. The computer program of claim 20, wherein the memory mappings in the mapping-data storage locations are cleared after each of a plurality of instructions is interpreted.

22. The computer program of claim 18, wherein the software-based instruction processor is an instruction translator.

23. The computer program of claim 22, wherein the memory mappings in the mapping-data storage locations are cleared after a group of one or more instructions is translated.

24. The computer program of claim 18, wherein the computer program comprises a virtual machine monitor.

25. The computer program of claim 18, wherein the mapping-data storage locations are contained within a linear data array, with each entry in the array including virtual address information and corresponding physical address information.

26. The computer program of claim 25, wherein the number of entries in the linear data array is eight.

27. The computer program of claim 25 further comprising a counter for counting the number of valid entries within the data array, wherein the counter is incremented each time an entry is added to the data array and the data array is cleared by resetting the counter.