[PATCH] KVM: MMU: Shadow page table caching

Define a hashtable for caching shadow page tables. Look up the cache on
context switch (cr3 change) or during page faults.

The key to the cache is a combination of
- the guest page table frame number
- the number of paging levels in the guest
   * we can cache real mode, 32-bit mode, pae, and long mode page
     tables simultaneously.  this is useful for smp bootup.
- the guest page table table
   * some kernels use a page as both a page table and a page directory.  this
     allows multiple shadow pages to exist for that page, one per level
- the "quadrant"
   * 32-bit mode page tables span 4MB, whereas a shadow page table spans
     2MB.  similarly, a 32-bit page directory spans 4GB, while a shadow
     page directory spans 1GB.  the quadrant allows caching up to 4 shadow page
     tables for one guest page in one level.
- a "metaphysical" bit
   * for real mode, and for pse pages, there is no guest page table, so set
     the bit to avoid write protecting the page.

Signed-off-by: Avi Kivity <avi@qumranet.com>
Acked-by: Ingo Molnar <mingo@elte.hu>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

1 files changed, 44 insertions, 1 deletions

diff --git a/drivers/kvm/kvm.h b/drivers/kvm/kvm.h
index abe40dd34eea..58b9deb0bc0e 100644
--- a/drivers/kvm/kvm.h
+++ b/drivers/kvm/kvm.h
@@ -89,14 +89,53 @@ typedef unsigned long  hva_t;
 typedef u64            hpa_t;
 typedef unsigned long  hfn_t;
 
+#define NR_PTE_CHAIN_ENTRIES 5
+
+struct kvm_pte_chain {
+        u64 *parent_ptes[NR_PTE_CHAIN_ENTRIES];
+        struct hlist_node link;
+};
+
+/*
+ * kvm_mmu_page_role, below, is defined as:
+ *
+ *   bits 0:3 - total guest paging levels (2-4, or zero for real mode)
+ *   bits 4:7 - page table level for this shadow (1-4)
+ *   bits 8:9 - page table quadrant for 2-level guests
+ *   bit   16 - "metaphysical" - gfn is not a real page (huge page/real mode)
+ */
+union kvm_mmu_page_role {
+        unsigned word;
+        struct {
+                unsigned glevels : 4;
+                unsigned level : 4;
+                unsigned quadrant : 2;
+                unsigned pad_for_nice_hex_output : 6;
+                unsigned metaphysical : 1;
+        };
+};
+
 struct kvm_mmu_page {
         struct list_head link;
+        struct hlist_node hash_link;
+
+        /*
+         * The following two entries are used to key the shadow page in the
+         * hash table.
+         */
+        gfn_t gfn;
+        union kvm_mmu_page_role role;
+
         hpa_t page_hpa;
         unsigned long slot_bitmap; /* One bit set per slot which has memory
                                     * in this shadow page.
                                     */
         int global;              /* Set if all ptes in this page are global */
-        u64 *parent_pte;
+        int multimapped;         /* More than one parent_pte? */
+        union {
+                u64 *parent_pte;               /* !multimapped */
+                struct hlist_head parent_ptes; /* multimapped, kvm_pte_chain */
+        };
 };
 
 struct vmcs {
@@ -235,7 +274,11 @@ struct kvm {
         spinlock_t lock; /* protects everything except vcpus */
         int nmemslots;
         struct kvm_memory_slot memslots[KVM_MEMORY_SLOTS];
+        /*
+         * Hash table of struct kvm_mmu_page.
+         */
         struct list_head active_mmu_pages;
+        struct hlist_head mmu_page_hash[KVM_NUM_MMU_PAGES];
         struct kvm_vcpu vcpus[KVM_MAX_VCPUS];
         int memory_config_version;
         int busy;