Method and system for caching address translations from multiple address spaces in virtual machines

1. A method of caching translations of virtual addresses (VA) to system physical addresses (SPA) from multiple address spaces in a virtual machine, the method comprising:

write-protecting a guest page table containing at least one address translation for a first guest address space before caching the at least one address translation in a shadow page table, wherein a subsequent write to the guest page table is intercepted;

intercepting a write to the guest page table;

creating a guest-writable mapping to the guest page table after intercepting at least one write to the guest page table; wherein a subsequent write to the guest page table is not intercepted and wherein the guest-writable mapping is a writable translation in a shadow page table from a virtual address to the system physical address of the guest page table;

marking a cached address translation associated with the guest page table affected by the intercepted guest-writable mapping, wherein the marking indicates a stale cached address translation;

purging the marked address translations upon one of a switch to a second guest address space and a flush of translations, wherein non-stale address translations remain cached and stale address translations are removed;

building a set of tracked guest pages dynamically, wherein the tracked guest pages contain tracked guest page tables and are identified as guest page tables are walked in resolving address translations;

tracking every intercepted guest-writable mapping to a guest page in the set of tracked guest pages;

removing all of the tracked guest-writable mappings to a tracked guest page, wherein a subsequent write to the tracked guest page is intercepted;

counting a number of times that untracked guest page tables are shadowed, wherein the untracked guest page tables have guest-writable mappings that may not be tracked;

deferring write-protecting a guest page containing an untracked guest page table being shadowed until the number of times that untracked guest page tables are shadowed exceeds a threshold, wherein the guest page is assumed to have guest-writable mappings;

adding the guest page containing an untracked guest page table being shadowed to a list of guest pages that are candidates for being tracked; and

purging all cached address translations when the number of times that untracked guest page tables have been shadowed exceeds a threshold, wherein all guest pages are write-protected as a result of removing all guest-writable mappings and wherein the untracked guest pages on the candidate list become tracked guest pages as a result of write-protecting the untracked guest pages.

2. A system for caching translations of virtual addresses (VA) to system physical addresses (SPA) from multiple address spaces in a virtual machine, the system comprising;

at least one guest program running on a host computer, the guest program and host computer comprising the virtual machine;

at least one data storage resource containing:

at least one guest page containing a guest page table with at least one address translation; and

at least one host page containing a shadow page table with at least one address translation; and

a memory; and at least one host processor that accesses the memory, the memory having instructions which when executed, perform a method comprising:

write-protecting a guest page table containing at least one address translation for a first guest address space before caching the at least one address translation in a shadow page table, wherein a subsequent write to the guest page table is intercepted;

intercepting a write to the guest page table;

creating a guest-writable mapping to the guest page table after intercepting at least one write to the guest page table; wherein a subsequent write to the guest page table is not intercepted and wherein the guest-writable mapping is a writable translation in a shadow page table from a virtual address to the system physical address of the guest page table;

marking a cached address translation associated with the guest page table affected by the intercepted guest-writable mapping, wherein the marking indicates a stale cached address translation;

purging the marked address translations upon one of a switch to a second guest address space and a flush of translations, wherein non-stale address translations remain cached and stale address translations are removed;

building a set of tracked guest pages dynamically, wherein the tracked guest pages contain tracked guest page tables and are identified as guest page tables are walked in resolving address translations;

tracking every intercepted guest-writable mapping to a guest page in the set of tracked guest pages; and

removing all of the tracked guest-writable mappings to a tracked guest page, wherein a subsequent write to the tracked guest page is intercepted; and

a software counter which counts a number of times that untracked guest page tables are shadowed, and

wherein the host processor executes software to:

defer write protecting a guest page containing an untracked guest page table being shadowed until the number of times that untracked guest page tables are shadowed exceeds a threshold, wherein the guest page table is assumed to have guest-writable mappings;

add the guest page containing an untracked guest page table being shadowed to a list of guest pages that are candidates for being tracked; and

purge all cached address translations when the number of times that untracked guest page tables have been shadowed exceeds a threshold, wherein all guest pages are write-protected as a result of removing all guest-writable mappings and wherein the untracked guest pages on the candidate list become tracked guest pages as a result of write-protecting the untracked guest pages.

3. A computer-readable storage medium, comprising instructions which execute a method of caching translations of virtual addresses (VA) to system physical addresses (SPA) from multiple address spaces in a virtual machine, the method comprising:

write-protecting a guest page table containing at least one address translation for a first guest address space before caching the at least one address translation in a shadow page table, wherein a subsequent write to the guest page table is intercepted;

intercepting a write to the guest page table;

creating a guest-writable mapping to the guest page table after intercepting at least one write to the guest page table; wherein a subsequent write to the guest page table is not intercepted and wherein the guest-writable mapping is a writable translation in a shadow page table from a virtual address to the system physical address of the guest page table;

marking a cached address translation associated with the guest page table affected by the intercepted guest-writable mapping, wherein the marking indicates a stale cached address translation; and

purging the marked address translations upon one of a switch to a second guest address space and a flush of translations, wherein non-stale address translations remain cached and stale address translations are removed;

building a set of tracked guest pages dynamically, wherein the tracked guest pages contain tracked guest page tables and are identified as guest page tables are walked in resolving address translations;

tracking every intercepted guest-writable mapping to a guest page in the set of tracked guest pages;

removing all of the tracked guest-writable mappings to a tracked guest page, wherein a subsequent write to the tracked guest page is intercepted;

counting a number of times that untracked guest page tables are shadowed, wherein the untracked guest page tables have guest-writable mappings that may not be tracked;

deferring write-protecting a guest page containing an untracked guest page table being shadowed until the number of times that untracked guest page tables are shadowed exceeds a threshold, wherein the guest page is assumed to have guest-writable mappings;

adding the guest page containing an untracked guest page table being shadowed to a list of guest pages that are candidates for being tracked; and

purging all cached address translations when the number of times that untracked guest page tables have been shadowed exceeds a threshold, wherein all guest pages are write-protected as a result of removing all guest-writable mappings and wherein the untracked guest pages on the candidate list become tracked guest pages as a result of write-protecting the untracked guest pages.