kvm cleanup: Introduce sibling_pte and do cleanup for reverse map and parent_pte
Subsystems (4)
PATCH 1/1 kvm cleanup: Introduce sibling_pte and do cleanup for reverse map and parent_pte
This patch is just a big cleanup. it reduces 220 lines of code.
It introduces sibling_pte array for tracking identical sptes, so the identical sptes can be linked as a single linked list by their corresponding sibling_pte. A reverse map or a parent_pte points at the head of this single linked list. So we can do cleanup for reverse map and parent_pte VERY LARGELY.
BAD:
If most rmap have only one entry or most sp have only one parent, this patch may use more memory than before.
GOOD:
1) Reduce a lot of code, The functions which are in hot path becomes very very simple and terrifically fast.
2) rmap_next(): O(N) -> O(1). traveling a ramp: O(N*N) -> O(N)
3) Remove the ugly interlayer: struct kvm_rmap_desc, struct kvm_pte_chain
4) We don't need to allocate any thing when we change the mappings. So we can avoid allocation when we have held kvm mmu spin lock. (this feature is very helpful in future).
5) better readability.
Documentation/kvm/mmu.txt | 16 + arch/x86/include/asm/kvm_host.h | 16 - arch/x86/kvm/mmu.c | 343 +++++++--------------------------------- 3 files changed, 78 insertions(+), 297 deletions(-)
Documentation/kvm/mmu.txt +9 -7
@@ -178,8 +178,13 @@ Shadow pages contain the following information: at __pa(sp2->spt). sp2 will point back at sp1 through parent_pte. The spt array forms a DAG structure with the shadow page as a node, and guest pages as leaves. + sibling_pte: + An array of 512 pointers, one for each present pte, every pointer points at + a next spte with identical spte. Several identical sptes are linked as + a single linked list by their corresponding sibling_pte. A reverse map or + a parent_pte points at the head spte of this single linked list. gfns: - An array of 512 guest frame numbers, one for each present pte. Used to + An array of 512 guest frame numbers, one for each last present pte. Used to perform a reverse map from a pte to a gfn. When role.direct is set, any element of this array can be calculated from the gfn field when used, in this case, the array of gfns is not allocated. See role.direct and gfn.
@@ -194,12 +199,9 @@ Shadow pages contain the following information: A counter keeping track of how many hardware registers (guest cr3 or pdptrs) are now pointing at the page. While this counter is nonzero, the page cannot be destroyed. See role.invalid. - multimapped: - Whether there exist multiple sptes pointing at this page. - parent_pte/parent_ptes: - If multimapped is zero, parent_pte points at the single spte that points at - this page's spt. Otherwise, parent_ptes points at a data structure - with a list of parent_ptes. + parent_pte: + parent_pte points at the head spte of sptes that point at this page's spt. + See sibling_pte. unsync: If true, then the translations in this page may not match the guest's translation. This is equivalent to the state of the tlb when a pte is
arch/x86/include/asm/kvm_host.h +2 -14
@@ -153,13 +153,6 @@ struct kvm_mmu_memory_cache {void *objects[KVM_NR_MEM_OBJS ]; }; -#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: *
@@ -197,6 +190,7 @@ struct kvm_mmu_page {union kvm_mmu_page_role role;u64 *spt; +u64 **sibling_pte;/* hold the gfn of each spte inside spt */ gfn_t *gfns;/*
@@ -204,14 +198,10 @@ struct kvm_mmu_page {* in this shadow page. */ DECLARE_BITMAP (slot_bitmap,KVM_MEMORY_SLOTS +KVM_PRIVATE_MEM_SLOTS ); -bool multimapped;/* More than one parent_pte? */ bool unsync;int root_count;/* Currently serving as active root */ unsigned int unsync_children; -union { -u64 *parent_pte;/* !multimapped */ -struct hlist_head parent_ptes;/* multimapped, kvm_pte_chain */ - }; +u64 *parent_pte;DECLARE_BITMAP (unsync_child_bitmap,512 ); };
@@ -287,8 +277,6 @@ struct kvm_vcpu_arch {* put it here to avoid allocation */ struct kvm_pv_mmu_op_buffer mmu_op_buffer; -struct kvm_mmu_memory_cache mmu_pte_chain_cache; -struct kvm_mmu_memory_cache mmu_rmap_desc_cache;struct kvm_mmu_memory_cache mmu_page_cache;struct kvm_mmu_memory_cache mmu_page_header_cache;
arch/x86/kvm/mmu.c +67 -276
487 lines not on this page · raw message
Quoted 11 lines · Lai Jiangshan
This patch is just a big cleanup. it reduces 220 lines of code.
It introduces
sibling_ptearray for tracking identical sptes, so the identical sptes can be linked as a single linked list by their correspondingsibling_pte. A reverse map or aparent_ptepoints at the head of this single linked list. So we can do cleanup for reverse map andparent_pteVERY LARGELY.BAD:
If most rmap have only one entry or most sp have only one parent, this patch may use more memory than before.
That is the case with NPT and EPT. Each page has exactly one spte (except a few vga pages), and each sp has exactly one parent_pte (except the root pages).
Quoted 4 lines
GOOD:
1) Reduce a lot of code, The functions which are in hot path becomes very very simple and terrifically fast.
2)rmap_next(): O(N) -> O(1). traveling a ramp:O(N*N)-> O(N)
The existing rmap_next() is not O(N), it's O(RMAP_EXT), which is 4. The data structure was chosen over a simple linked list to avoid extra cache misses.
Quoted 1 line
3) Remove the ugly interlayer: struct
kvm_rmap_desc, structkvm_pte_chain
kvm_rmap_desc and kvm_pte_chain are indeed ugly, but they do save a lot of memory and cache misses.
Quoted 4 lines
4) We don't need to allocate any thing when we change the mappings. So we can avoid allocation when we have held kvm mmu spin lock. (this feature is very helpful in future).
5) better readability.
I agree the new code is more readable. Unfortunately it uses more memory and is likely to be slower. You add a cache miss for every spte, while kvm_rmap_desc amortizes the cache miss among 4 sptes, and special cases 1 spte to have no cache misses (or extra memory requirements).
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Quoted 37 lines · Avi Kivity
Quoted 11 lines · Lai Jiangshan
This patch is just a big cleanup. it reduces 220 lines of code.
It introduces
sibling_ptearray for tracking identical sptes, so the identical sptes can be linked as a single linked list by their correspondingsibling_pte. A reverse map or aparent_ptepoints at the head of this single linked list. So we can do cleanup for reverse map andparent_pteVERY LARGELY.BAD:
If most rmap have only one entry or most sp have only one parent, this patch may use more memory than before.That is the case with NPT and EPT. Each page has exactly one spte (except a few vga pages), and each sp has exactly one
parent_pte(except the root pages).Quoted 4 lines
GOOD:
1) Reduce a lot of code, The functions which are in hot path becomes very very simple and terrifically fast.
2)rmap_next(): O(N) -> O(1). traveling a ramp:O(N*N)-> O(N)The existing
rmap_next()is not O(N), it'sO(RMAP_EXT), which is 4. The data structure was chosen over a simple linked list to avoid extra cache misses.Quoted 2 lines
3) Remove the ugly interlayer: struct
kvm_rmap_desc, structkvm_pte_chain
kvm_rmap_descandkvm_pte_chainare indeed ugly, but they do save a lot of memory and cache misses.Quoted 4 lines
4) We don't need to allocate any thing when we change the mappings. So we can avoid allocation when we have held kvm mmu spin lock. (this feature is very helpful in future).
5) better readability.
Quoted 5 lines
I agree the new code is more readable. Unfortunately it uses more memory and is likely to be slower. You add a cache miss for every spte, while
kvm_rmap_descamortizes the cache miss among 4 sptes, and special cases 1 spte to have no cache misses (or extra memory requirements).
You are right, please omit this patch
thanks, lai.