Reduction of operational costs of virtual TLBs

• US 20080134174A1
• Filed: 12/05/2006
• Published: 06/05/2008
• Est. Priority Date: 12/05/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Landy, Sheu, John Te-Jui, Vega, Rene Antonio, Nanavati, Sharvil A., Cohen, Ernest S., Hendel, Matthew D.
• Granted Patent: US 8,694,712 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence

Abstract

Various operations are disclosed for improving the operational efficiency of a virtual translation look-aside buffer (TLB) in a virtual machine environment. For example, operations are disclosed that allow for determination of whether present entries in shadow page tables (SPTs) are stale by comparing shadowed guest page table (GPT) entries against snapshots taken when the entries were cached. Other operations are disclosed that allow a virtual machine monitor (VMM) to access shadow page table trees (SPTTs) by walking trees in software or in hardware. Still other operations are disclosed allowing the VMM to use a hash table to relate GVA ranges to SPTs that map them, thus significantly reducing the cost of having to walk each SPTT in order to invalidate desired GVA(s). And, finally, operations are disclosed allowing the VMM to determine global GVA ranges by checking a bitmap, when invalidating global GVAs.

Claims

1. A method for reducing the operational cost of a virtual machine environment, comprising:

using at least one virtual translation look-aside buffer (TLB) with at least one shadow page table tree (SPTT) and at least one shadow page table (SPT) residing in said SPTT, wherein said at least one SPTT maps guest virtual addresses (GVAs) to system physical addresses (SPAs);

caching translations from at least one guest page table (GPTs), wherein said GPTs map said GVAs to guest physical addresses (GPAs); and

using data from (a) said at least one of SPT or (b) said GPT to perform an operation on said virtual TLB.

2. The method according to claim 1, said operation further comprising taking a snapshot of at least one entry in said GPT and maintaining a list of at least one entry in said SPT, wherein said snapshot is compared to at least one entry in said GPT at a different time, and if a disparity exists between said snapshot and said GPT entry at said different time, updating at least one entry in said SPT that corresponds to said snapshot that exhibits the disparity with the help of said list, wherein said list also contains indices to entries in said at least one SPT.

3. The method according to claim 1, said operation further comprising:

obtaining an SPA for a SPT;

establishing a relation between said SPA and said SPT;

storing said relation in a database;

maintaining said database for said relation;

looking up said SPA to walk to said SPT wherein said SPA is obtained from an entry in a higher-level SPT in said SPTT.

4. The method according to claim 3, wherein said establishing of said relation between said SPA and said SPT is established when said SPT is allocated and before said SPT is used.

5. The method according to claim 3, wherein said relation is cleared from a database before said SPT is freed.

6. The method according to claim 1, said operation further comprising:

pointing a first entry in a top-level virtual machine monitor page table (VPT) at a top-level shadow page table (SPT) in said SPTT;

pointing a second entry in said top-level VPT at the VPT itself.

accessing a target SPT at any level of a shadow page table tree (SPTT), wherein said accessing is made via a hypervisor virtual address (HVA) that walks through said second entry zero or more times and then follows said first entry in said SPT.

7. The method according to claim 6, wherein a memory management unit (MMU) accesses said target SPT on behalf of a virtual machine monitor (VMM) given said HVA for said target SPT.

8. The method according to claim 1, said operation further comprising:

defining a hash table that is configured to relate GVA ranges to SPTs in said SPTT;

taking a snapshot of said at least one SPT that maps at least one GVA in a GVA range, wherein said at least one GVA has been selected for invalidation; and

invalidating said at least one GVA in said at least one SPT per said snapshot.

9. The method according to claim 8, further comprising after said defining, performing at least one of (a) adding at least one selected SPT to said hash table upon allocation of said at least one selected SPT, and (b) removing at least one selected SPT from said hash table upon deallocation of said at least one selected SPT.

10. The method according to claim 8, further comprising locking said at least one SPT before said snapshot and unlocking said at least one SPT after said snapshot.

11. The method according to claim 8, wherein said GVA is local to a shadow address space (SAS).

12. The method according to claim 8, wherein said GVA is global across a plurality of shadow address spaces (SASes).

13. The method according to claim 1, said operation further comprising:

providing a bitmap configured to have a set of bit values corresponding to a set of ranges in guest virtual address (GVA) space;

setting said set of bit values in said bitmap when caching GVA translations, wherein a range in said set of ranges is assigned a first bit value if at least one GVA translation in said range is a global GVA, and wherein said range is assigned a second bit value if no GVA translations in said range is said global GVA;

checking a bit value in said bitmap when an invalidation request is made for at least one GVA in a range corresponding to said bit value; and

invalidating said at least one GVA in all address spaces only if said bit value is said first bit value.

14. A system for reducing the operational cost of a virtual machine environment, comprising:

at least one virtual translation look-aside buffer (TLB) with at least one shadow page table tree (SPTT) and at least one shadow page table (SPT) residing in said SPTT, wherein said at least one SPT maps guest virtual addresses (GVAs) to system physical addresses (SPAs);

a set of (GPTs), wherein said GPTs map said GVAs to guest physical addresses (GPAs); and

data from said at least one of SPT and said GPT to perform an operation on said virtual TLB.

15. The system according to claim 14, wherein said operation comprises of taking a snapshot a GPT of said set of GPTs, wherein said snapshot is compared to said GPT at a different time, and if a disparity exists between said snapshot and said GPT, updating a SPT associated with said GPT.

16. The system according to claim 14, wherein said operation comprises of accessing said SPTT by walking the said SPTT in software.

17. The system according to claim 14, wherein said operation comprises of accessing said SPTT by walking the said SPTT in hardware.

18. The system according to claim 14, wherein said operation comprises using a VMM to service GVA invalidations using a hash table relating said GVAs to said at least one SPT that maps said GVAs.

19. The system according to claim 14, wherein said operation comprises using a VMM to determine whether a GVA of said GVAs is global by checking a bitmap for global GVA ranges.

20. A computer readable medium bearing computer executable instructions for reducing the operational cost of a virtual machine environment, comprising performing at least one of the following operations:

taking a snapshot of a guest page table (GPT) and comparing said snapshot to a later version of said GPT, in order to determine any stale entries in an associated shadow page table (SPT);

accessing a shadow page table tree (SPTT) by walking the said SPTT in software, wherein said walking is accomplished by using system physical addresses (SPAs) associated with said SPTs;

accessing said SPTT by walking the said SPTT in hardware, wherein said walking is accomplished by pointing virtual page table trees (VPTTs) to shadow SPTTs and walking said SPTTs using a hardware component;

using a module to service GVA invalidations using a hash table relating said GVAs to SPTs that maps said GVAs; and

using a module to determine whether GVAs are global by checking a bitmap for global GVA ranges.