KVM: Scalable memslots implementation
v2 cover KVM: Scalable memslots implementation
From: "Maciej S. Szmigiero" <[email protected]>
The current memslot code uses a (reverse) gfn-ordered memslot array for keeping track of them.
This only allows quick binary search by gfn, quick lookup by hva is not possible (the implementation has to do a linear scan of the whole memslot array).
Because the memslot array that is currently in use cannot be modified every memslot management operation (create, delete, move, change flags) has to make a copy of the whole array so it has a scratch copy to work on.
Strictly speaking, however, it is only necessary to make copy of the memslot that is being modified, copying all the memslots currently present is just a limitation of the array-based memslot implementation.
Two memslot sets, however, are still needed so the VM continues to run on the currently active set while the requested operation is being performed on the second, currently inactive one.
In order to have two memslot sets, but only one copy of the actual memslots it is necessary to split out the memslot data from the memslot sets.
The memslots themselves should be also kept independent of each other so they can be individually added or deleted.
These two memslot sets should normally point to the same set of memslots. They can, however, be desynchronized when performing a memslot management operation by replacing the memslot to be modified by its copy. After the operation is complete, both memslot sets once again point to the same, common set of memslot data.
This series implements the aforementioned idea.
The new implementation uses two trees to perform quick lookups:
For tracking of gfn an ordinary rbtree is used since memslots cannot overlap in the guest address space and so this data structure is sufficient for ensuring that lookups are done quickly.
For tracking of hva, however, an interval tree is needed since they can overlap between memslots.
ID to memslot mappings are kept in a hash table instead of using a statically allocated "id_to_index" array.
The "lru slot" mini-cache, that keeps track of the last found-by-gfn memslot, is still present in the new code.
There was also a desire to make the new structure operate on "pay as you go" basis, that is, that the user only pays the price of the memslot count that is actually used, not of the maximum count allowed.
The operation semantics were carefully matched to the original implementation, the outside-visible behavior should not change. Only the timing will be different.
Making lookup and memslot management operations O(log(n)) brings some performance benefits (tested on a Xeon 8167M machine):
509 slots in use:
Test Before After Improvement Map 0.0232s 0.0223s 4% Unmap 0.0724s 0.0315s 56% Unmap 2M 0.00155s 0.000869s 44% Move active 0.000101s 0.0000792s 22% Move inactive 0.000108s 0.0000847s 21% Slot setup 0.0135s 0.00803s 41%
100 slots in use:
Test Before After Improvement Map 0.0195s 0.0191s None Unmap 0.0374s 0.0312s 17% Unmap 2M 0.000470s 0.000447s 5% Move active 0.0000956s 0.0000800s 16% Move inactive 0.000101s 0.0000840s 17% Slot setup 0.00260s 0.00174s 33%
50 slots in use:
Test Before After Improvement Map 0.0192s 0.0190s None Unmap 0.0339s 0.0311s 8% Unmap 2M 0.000399s 0.000395s None Move active 0.0000999s 0.0000854s 15% Move inactive 0.0000992s 0.0000826s 17% Slot setup 0.00141s 0.000990s 30%
30 slots in use:
Test Before After Improvement Map 0.0192s 0.0190s None Unmap 0.0325s 0.0310s 5% Unmap 2M 0.000373s 0.000373s None Move active 0.000100s 0.0000865s 14% Move inactive 0.000106s 0.0000918s 13% Slot setup 0.000989s 0.000775s 22%
10 slots in use:
Test Before After Improvement Map 0.0192s 0.0186s 3% Unmap 0.0313s 0.0310s None Unmap 2M 0.000348s 0.000351s None Move active 0.000110s 0.0000948s 14% Move inactive 0.000111s 0.0000933s 16% Slot setup 0.000342s 0.000283s 17%
32k slots in use:
Test Before After Improvement Map (8194) 0.200s 0.0541s 73% Unmap 3.88s 0.0351s 99% Unmap 2M 3.88s 0.0348s 99% Move active 0.00142s 0.0000786s 94% Move inactive 0.00148s 0.0000880s 94% Slot setup 16.1s 0.59s 96%
Since the map test can be done with up to 8194 slots, the result above for this test was obtained running it with that maximum number of slots.
In both the old and new memslot code case the measurements were done against the new KVM selftest framework, with TDP MMU disabled (that is, with the default setting).
On x86-64 the code was well tested, passed KVM unit tests and KVM selftests with KASAN on.
And, of course, booted various guests successfully (including nested ones with TDP MMU enabled).
On other KVM platforms the code was compile-tested only.
Changes since v1:
* Drop the already merged HVA handler retpoline-friendliness patch,
* Split the scalable memslots patch into 8 smaller ones,
* Rebase onto the current kvm/queue,
* Make sure that ranges at both memslot's hva_nodes are always initialized,
* Remove kvm_mmu_calculate_default_mmu_pages() prototype, too, when removing this function,
* Redo benchmarks, measure 32k memslots on the old implementation, too.
arch/arm64/kvm/Kconfig | 1 + arch/arm64/kvm/mmu.c | 20 +- arch/mips/kvm/Kconfig | 1 + arch/mips/kvm/mmu.c | 12 +- arch/powerpc/kvm/Kconfig | 1 + arch/powerpc/kvm/book3s_64_mmu_hv.c | 16 +- arch/powerpc/kvm/book3s_64_vio.c | 2 +- arch/powerpc/kvm/book3s_64_vio_hv.c | 2 +- arch/powerpc/kvm/book3s_hv.c | 3 +- arch/powerpc/kvm/book3s_hv_nested.c | 4 +- arch/powerpc/kvm/book3s_hv_uvmem.c | 14 +- arch/powerpc/kvm/book3s_pr.c | 12 +- arch/s390/kvm/Kconfig | 1 + arch/s390/kvm/kvm-s390.c | 66 +--- arch/s390/kvm/kvm-s390.h | 15 + arch/s390/kvm/pv.c | 4 +- arch/x86/include/asm/kvm_host.h | 2 +- arch/x86/kvm/Kconfig | 1 + arch/x86/kvm/mmu/mmu.c | 78 ++-- arch/x86/kvm/mmu/tdp_mmu.c | 15 +- arch/x86/kvm/x86.c | 18 +- include/linux/kvm_host.h | 139 ++++--- virt/kvm/kvm_main.c | 592 ++++++++++++++++------------ 23 files changed, 603 insertions(+), 416 deletions(-)
PATCH v2 1/8 KVM: x86: Cache total page count to avoid traversing the memslot array
From: "Maciej S. Szmigiero" <[email protected]>
There is no point in recalculating from scratch the total number of pages in all memslots each time a memslot is created or deleted.
Just cache the value and update it accordingly on each such operation so the code doesn't need to traverse the whole memslot array each time.
--- arch/x86/include/asm/kvm_host.h | 2 +- arch/x86/kvm/mmu/mmu.c | 24 ------------------------ arch/x86/kvm/x86.c | 18 +++++++++++++++--- 3 files changed, 16 insertions(+), 28 deletions(-)
arch/x86/include/asm/kvm_host.h +1 -1
@@ -939,6 +939,7 @@ enum kvm_irqchip_mode {#define APICV_INHIBIT_REASON_X2APIC 5struct kvm_arch { +unsigned long n_memslots_pages;unsigned long n_used_mmu_pages;unsigned long n_requested_mmu_pages;unsigned long n_max_mmu_pages;
@@ -1426,7 +1427,6 @@ void kvm_mmu_slot_largepage_remove_write_access(struct kvm *kvm, struct kvm_memory_slot *memslot);void kvm_mmu_zap_all (struct kvm *kvm);void kvm_mmu_invalidate_mmio_sptes (struct kvm *kvm,u64 gen); -unsigned long kvm_mmu_calculate_default_mmu_pages (struct kvm *kvm);void kvm_mmu_change_mmu_pages (struct kvm *kvm,unsigned long kvm_nr_mmu_pages);int load_pdptrs (struct kvm_vcpu *vcpu,struct kvm_mmu *mmu,unsigned long cr3);
arch/x86/kvm/mmu/mmu.c +0 -24
@@ -5869,30 +5869,6 @@ int kvm_mmu_module_init(void)return ret; } -/* -* Calculate mmu pages needed for kvm. -*/ -unsigned long kvm_mmu_calculate_default_mmu_pages (struct kvm *kvm) -{ -unsigned long nr_mmu_pages; -unsigned long nr_pages =0 ; -struct kvm_memslots *slots; -struct kvm_memory_slot *memslot; -int i; - -for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) { - slots =__kvm_memslots (kvm, i); - -kvm_for_each_memslot (memslot, slots) - nr_pages += memslot->npages; - } - - nr_mmu_pages = nr_pages *KVM_PERMILLE_MMU_PAGES /1000 ; - nr_mmu_pages =max (nr_mmu_pages,KVM_MIN_ALLOC_MMU_PAGES ); - -return nr_mmu_pages; -} -void kvm_mmu_destroy (struct kvm_vcpu *vcpu) {kvm_mmu_unload (vcpu);
arch/x86/kvm/x86.c +15 -3
@@ -10959,9 +10959,21 @@ void kvm_arch_commit_memory_region(struct kvm *kvm,const struct kvm_memory_slot *new, enum kvm_mr_change change) { - if (!kvm->arch.n_requested_mmu_pages) - kvm_mmu_change_mmu_pages(kvm, - kvm_mmu_calculate_default_mmu_pages(kvm)); + if (change == KVM_MR_CREATE) + kvm->arch.n_memslots_pages += new->npages; + else if (change == KVM_MR_DELETE) { + WARN_ON(kvm->arch.n_memslots_pages < old->npages); + kvm->arch.n_memslots_pages -= old->npages; + } + +if (!kvm->arch.n_requested_mmu_pages) { +unsigned long nr_mmu_pages; + + nr_mmu_pages = kvm->arch.n_memslots_pages * +KVM_PERMILLE_MMU_PAGES /1000 ; + nr_mmu_pages =max (nr_mmu_pages,KVM_MIN_ALLOC_MMU_PAGES ); +kvm_mmu_change_mmu_pages (kvm, nr_mmu_pages); + }/* * FIXME: const-ify all uses of struct kvm_memory_slot.
PATCH v2 2/8 KVM: Integrate gfn_to_memslot_approx() into search_memslots()
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
s390 arch has gfn_to_memslot_approx() which is almost identical to search_memslots(), differing only in that in case the gfn falls in a hole one of the memslots bordering the hole is returned.
Add this lookup mode as an option to search_memslots() so we don't have two almost identical functions for looking up a memslot by its gfn.
--- arch/powerpc/kvm/book3s_64_vio.c | 2 +- arch/powerpc/kvm/book3s_64_vio_hv.c | 2 +- arch/s390/kvm/kvm-s390.c | 39 ++--------------------------- include/linux/kvm_host.h | 13 +++++++--- 4 files changed, 14 insertions(+), 42 deletions(-)
arch/powerpc/kvm/book3s_64_vio.c +1 -1
@@ -346,7 +346,7 @@ static long kvmppc_tce_to_ua(struct kvm *kvm, unsigned long tce,unsigned long gfn = tce >>PAGE_SHIFT ;struct kvm_memory_slot *memslot; - memslot =search_memslots (kvm_memslots (kvm), gfn); + memslot =search_memslots (kvm_memslots (kvm), gfn, false);if (!memslot)return -EINVAL ;
arch/powerpc/kvm/book3s_64_vio_hv.c +1 -1
@@ -80,7 +80,7 @@ static long kvmppc_rm_tce_to_ua(struct kvm *kvm,unsigned long gfn = tce >>PAGE_SHIFT ;struct kvm_memory_slot *memslot; - memslot =search_memslots (kvm_memslots_raw (kvm), gfn); + memslot =search_memslots (kvm_memslots_raw (kvm), gfn, false);if (!memslot)return -EINVAL ;
arch/s390/kvm/kvm-s390.c +2 -37
@@ -1912,41 +1912,6 @@ static long kvm_s390_set_skeys(struct kvm *kvm, struct kvm_s390_skeys *args)/* for consistency */ #define KVM_S390_CMMA_SIZE_MAX ((u32)KVM_S390_SKEYS_MAX) -/* -* Similar to gfn_to_memslot, but returns the index of a memslot also when the -* address falls in a hole. In that case the index of one of the memslots -* bordering the hole is returned. -*/ -static int gfn_to_memslot_approx (struct kvm_memslots *slots,gfn_t gfn) -{ -int start =0 , end = slots->used_slots; -int slot =atomic_read (&slots->lru_slot); -struct kvm_memory_slot *memslots = slots->memslots; - -if (gfn >= memslots[slot].base_gfn && - gfn < memslots[slot].base_gfn + memslots[slot].npages) -return slot; - -while (start < end) { - slot = start + (end - start) /2 ; - -if (gfn >= memslots[slot].base_gfn) - end = slot; -else - start = slot +1 ; - } - -if (start >= slots->used_slots) -return slots->used_slots -1 ; - -if (gfn >= memslots[start].base_gfn && - gfn < memslots[start].base_gfn + memslots[start].npages) { -atomic_set (&slots->lru_slot, start); - } - -return start; -} -static int kvm_s390_peek_cmma (struct kvm *kvm,struct kvm_s390_cmma_log *args,u8 *res,unsigned long bufsize) {
@@ -1973,8 +1938,8 @@ static int kvm_s390_peek_cmma(struct kvm *kvm, struct kvm_s390_cmma_log *args,static unsigned long kvm_s390_next_dirty_cmma (struct kvm_memslots *slots,unsigned long cur_gfn) { -int slotidx =gfn_to_memslot_approx (slots, cur_gfn); -struct kvm_memory_slot *ms = slots->memslots + slotidx; +struct kvm_memory_slot *ms =search_memslots (slots, cur_gfn, true); +int slotidx = ms - slots->memslots;unsigned long ofs = cur_gfn - ms->base_gfn;if (ms->base_gfn + ms->npages <= cur_gfn) {
include/linux/kvm_host.h +10 -3
@@ -1084,10 +1084,14 @@ bool kvm_arch_irqfd_allowed(struct kvm *kvm, struct kvm_irqfd *args);* gfn_to_memslot() itself isn't here as an inline because that would * bloat other code too much. * +* With "approx" set returns the memslot also when the address falls +* in a hole. In that case one of the memslots bordering the hole is +* returned. +* * IMPORTANT: Slots are sorted from highest GFN to lowest GFN! */ static inline struct kvm_memory_slot * -search_memslots (struct kvm_memslots *slots,gfn_t gfn) +search_memslots (struct kvm_memslots *slots,gfn_t gfn,bool approx) {int start =0 , end = slots->used_slots;int slot =atomic_read (&slots->lru_slot);
@@ -1109,19 +1113,22 @@ search_memslots(struct kvm_memslots *slots, gfn_t gfn) start = slot +1 ; } +if (approx && start >= slots->used_slots) +return &memslots[slots->used_slots -1 ]; +if (start < slots->used_slots && gfn >= memslots[start].base_gfn && gfn < memslots[start].base_gfn + memslots[start].npages) {atomic_set (&slots->lru_slot, start);return &memslots[start]; } -return NULL ; +return approx ? &memslots[start] :NULL ; }static inline struct kvm_memory_slot *__gfn_to_memslot (struct kvm_memslots *slots,gfn_t gfn) { -return search_memslots (slots, gfn); +return search_memslots (slots, gfn, false); } static inline unsigned long
PATCH v2 3/8 KVM: Resolve memslot ID via a hash table instead of via a static array
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
Memslot ID to the corresponding memslot mappings are currently kept as indices in static id_to_index array.
The size of this array depends on the maximum allowed memslot count (regardless of the number of memslots actually in use).
This has become especially problematic recently, when memslot count cap was removed, so the maximum count is now full 32k memslots - the maximum allowed by the current KVM API.
Keeping these IDs in a hash table (instead of an array) avoids this problem.
Resolving a memslot ID to the actual memslot (instead of its index) will also enable transitioning away from an array-based implementation of the whole memslots structure in a later commit.
--- include/linux/kvm_host.h | 16 +++++------ virt/kvm/kvm_main.c | 58 ++++++++++++++++++++++++++++++---------- 2 files changed, 52 insertions(+), 22 deletions(-)
include/linux/kvm_host.h +8 -8
@@ -27,6 +27,7 @@#include <linux/rcuwait.h> #include <linux/refcount.h> #include <linux/nospec.h> +#include <linux/hashtable.h> #include <asm/signal.h> #include <linux/kvm.h>
@@ -350,6 +351,7 @@ static inline int kvm_vcpu_exiting_guest_mode(struct kvm_vcpu *vcpu)#define KVM_MEM_MAX_NR_PAGES ((1UL << 31) - 1)struct kvm_memory_slot { +struct hlist_node id_node;gfn_t base_gfn;unsigned long npages;unsigned long *dirty_bitmap;
@@ -452,7 +454,7 @@ static inline int kvm_arch_vcpu_memslots_id(struct kvm_vcpu *vcpu)struct kvm_memslots {u64 generation;/* The mapping table from slot id to the index in memslots[]. */ -short id_to_index[KVM_MEM_SLOTS_NUM ]; + DECLARE_HASHTABLE(id_hash, 7);atomic_t lru_slot;int used_slots;struct kvm_memory_slot memslots[];
@@ -674,16 +676,14 @@ static inline struct kvm_memslots *kvm_vcpu_memslots(struct kvm_vcpu *vcpu)static inline struct kvm_memory_slot *id_to_memslot (struct kvm_memslots *slots,int id) { -int index = slots->id_to_index[id];struct kvm_memory_slot *slot; -if (index <0 ) -return NULL ; - - slot = &slots->memslots[index]; +hash_for_each_possible (slots->id_hash, slot, id_node, id) { +if (slot->id == id) +return slot; + } -WARN_ON (slot->id != id); -return slot; +return NULL ; }/*
virt/kvm/kvm_main.c +44 -14
162 lines not on this page · raw message
PATCH v2 4/8 KVM: Introduce memslots hva tree
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
The current memslots implementation only allows quick binary search by gfn, quick lookup by hva is not possible - the implementation has to do a linear scan of the whole memslots array, even though the operation being performed might apply just to a single memslot.
This significantly hurts performance of per-hva operations with higher memslot counts.
Since hva ranges can overlap between memslots an interval tree is needed for tracking them.
--- arch/arm64/kvm/Kconfig | 1 + arch/arm64/kvm/mmu.c | 10 +++++++--- arch/mips/kvm/Kconfig | 1 + arch/mips/kvm/mmu.c | 10 +++++++--- arch/powerpc/kvm/Kconfig | 1 + arch/powerpc/kvm/book3s_64_mmu_hv.c | 10 +++++++--- arch/powerpc/kvm/book3s_pr.c | 10 +++++++--- arch/s390/kvm/Kconfig | 1 + arch/x86/kvm/Kconfig | 1 + arch/x86/kvm/mmu/mmu.c | 11 +++++++--- arch/x86/kvm/mmu/tdp_mmu.c | 13 +++++++++--- include/linux/kvm_host.h | 8 ++++++++ virt/kvm/kvm_main.c | 31 +++++++++++++++++++++++++---- 13 files changed, 86 insertions(+), 22 deletions(-)
arch/arm64/kvm/Kconfig +1 -0
@@ -40,6 +40,7 @@ menuconfig KVM select HAVE_KVM_VCPU_RUN_PID_CHANGE select TASKSTATS select TASK_DELAY_ACCT + select INTERVAL_TREE help Support hosting virtualized guest machines.
arch/arm64/kvm/mmu.c +7 -3
@@ -1073,21 +1073,25 @@ static int handle_hva_to_gpa(struct kvm *kvm, void *data) {struct kvm_memslots *slots; +struct interval_tree_node *node;struct kvm_memory_slot *memslot;int ret =0 ; +if (end == start ||WARN_ON (end < start)) +return 0 ; + slots =kvm_memslots (kvm);/* we only care about the pages that the guest sees */ -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gpa; + memslot = container_of(node, struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ; gpa =hva_to_gfn_memslot (hva_start, memslot) <<PAGE_SHIFT ; ret |=handler (kvm, gpa, (u64)(hva_end - hva_start), data);
arch/mips/kvm/Kconfig +1 -0
@@ -27,6 +27,7 @@ config KVM select KVM_MMIO select MMU_NOTIFIER select SRCU + select INTERVAL_TREE help Support for hosting Guest kernels.
arch/mips/kvm/mmu.c +7 -3
@@ -449,21 +449,25 @@ static int handle_hva_to_gpa(struct kvm *kvm, void *data) {struct kvm_memslots *slots; +struct interval_tree_node *node;struct kvm_memory_slot *memslot;int ret =0 ; +if (end == start ||WARN_ON (end < start)) +return 0 ; + slots =kvm_memslots (kvm);/* we only care about the pages that the guest sees */ -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn, gfn_end; + memslot = container_of(node, struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ;/* * {gfn(page) | page intersects with [hva_start, hva_end)} =
arch/powerpc/kvm/Kconfig +1 -0
@@ -26,6 +26,7 @@ config KVM select KVM_VFIO select IRQ_BYPASS_MANAGER select HAVE_KVM_IRQ_BYPASS + select INTERVAL_TREE config KVM_BOOK3S_HANDLER bool
arch/powerpc/kvm/book3s_64_mmu_hv.c +7 -3
@@ -763,18 +763,22 @@ static int kvm_handle_hva_range(struct kvm *kvm,int ret;int retval =0 ;struct kvm_memslots *slots; +struct interval_tree_node *node;struct kvm_memory_slot *memslot; +if (end == start ||WARN_ON (end < start)) +return 0 ; + slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn, gfn_end; + memslot = container_of(node, struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ;/* * {gfn(page) | page intersects with [hva_start, hva_end)} = * {gfn, gfn+1, ..., gfn_end-1}.
arch/powerpc/kvm/book3s_pr.c +7 -3
@@ -431,18 +431,22 @@ static void do_kvm_unmap_hva(struct kvm *kvm, unsigned long start,long i;struct kvm_vcpu *vcpu;struct kvm_memslots *slots; +struct interval_tree_node *node;struct kvm_memory_slot *memslot; +if (end == start ||WARN_ON (end < start)) +return ; + slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn, gfn_end; + memslot = container_of(node, struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ;/* * {gfn(page) | page intersects with [hva_start, hva_end)} = * {gfn, gfn+1, ..., gfn_end-1}.
arch/s390/kvm/Kconfig +1 -0
@@ -33,6 +33,7 @@ config KVM select HAVE_KVM_NO_POLL select SRCU select KVM_VFIO + select INTERVAL_TREE help Support hosting paravirtualized guest machines using the SIE virtualization capability on the mainframe. This should work
arch/x86/kvm/Kconfig +1 -0
@@ -46,6 +46,7 @@ config KVM select KVM_GENERIC_DIRTYLOG_READ_PROTECT select KVM_VFIO select SRCU + select INTERVAL_TREE help Support hosting fully virtualized guest machines using hardware virtualization extensions. You will need a fairly recent
arch/x86/kvm/mmu/mmu.c +8 -3
@@ -1430,17 +1430,22 @@ static __always_inline int kvm_handle_hva_range(struct kvm *kvm,int ret =0 ;int i; +if (end == start ||WARN_ON (end < start)) +return 0 ; +for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) { +struct interval_tree_node *node; + slots =__kvm_memslots (kvm, i); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn_start, gfn_end; + memslot = container_of(node, struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ;/* * {gfn(page) | page intersects with [hva_start, hva_end)} = * {gfn_start, gfn_start+1, ..., gfn_end-1}.
arch/x86/kvm/mmu/tdp_mmu.c +10 -3
@@ -889,18 +889,25 @@ static __always_inline int kvm_tdp_mmu_handle_hva_range(struct kvm *kvm,int ret =0 ;int as_id; +if (end == start ||WARN_ON (end < start)) +return 0 ; +for (as_id =0 ; as_id <KVM_ADDRESS_SPACE_NUM ; as_id++) {for_each_tdp_mmu_root_yield_safe (kvm, root, as_id) { +struct interval_tree_node *node; + slots =__kvm_memslots (kvm, as_id); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_hva_range_memslot (node, slots, + start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn_start, gfn_end; + memslot =container_of (node, + struct kvm_memory_slot, + hva_node); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT )); -if (hva_start >= hva_end) -continue ;/* * {gfn(page) | page intersects with [hva_start, hva_end)} = * {gfn_start, gfn_start+1, ..., gfn_end-1}.
include/linux/kvm_host.h +8 -0
@@ -27,6 +27,7 @@#include <linux/rcuwait.h> #include <linux/refcount.h> #include <linux/nospec.h> +#include <linux/interval_tree.h> #include <linux/hashtable.h> #include <asm/signal.h>
@@ -352,6 +353,7 @@ static inline int kvm_vcpu_exiting_guest_mode(struct kvm_vcpu *vcpu)struct kvm_memory_slot {struct hlist_node id_node; +struct interval_tree_node hva_node;gfn_t base_gfn;unsigned long npages;unsigned long *dirty_bitmap;
@@ -453,6 +455,7 @@ static inline int kvm_arch_vcpu_memslots_id(struct kvm_vcpu *vcpu)*/ struct kvm_memslots {u64 generation; +struct rb_root_cached hva_tree;/* The mapping table from slot id to the index in memslots[]. */ DECLARE_HASHTABLE(id_hash, 7);atomic_t lru_slot;
@@ -673,6 +676,11 @@ static inline struct kvm_memslots *kvm_vcpu_memslots(struct kvm_vcpu *vcpu)return __kvm_memslots (vcpu->kvm, as_id); } +#define kvm_for_each_hva_range_memslot (node, slots, start, last) \ + for (node = interval_tree_iter_first(&slots->hva_tree, start, last); \ + node; \ + node = interval_tree_iter_next(node, start, last)) \ +static inline struct kvm_memory_slot *id_to_memslot (struct kvm_memslots *slots,int id) {
virt/kvm/kvm_main.c +27 -4
@@ -662,6 +662,7 @@ static struct kvm_memslots *kvm_alloc_memslots(void)if (!slots)return NULL ; + slots->hva_tree =RB_ROOT_CACHED ;hash_init (slots->id_hash);return slots;
@@ -988,10 +989,14 @@ static inline void kvm_memslot_delete(struct kvm_memslots *slots,atomic_set (&slots->lru_slot,0 );for (i = dmemslot - mslots; i < slots->used_slots; i++) { +interval_tree_remove (&mslots[i].hva_node, &slots->hva_tree);hash_del (&mslots[i].id_node); + mslots[i] = mslots[i +1 ]; +interval_tree_insert (&mslots[i].hva_node, &slots->hva_tree);hash_add (slots->id_hash, &mslots[i].id_node, mslots[i].id); } +interval_tree_remove (&mslots[i].hva_node, &slots->hva_tree);hash_del (&mslots[i].id_node); mslots[i] = *memslot; }
@@ -1011,7 +1016,8 @@ static inline int kvm_memslot_insert_back(struct kvm_memslots *slots)* itself is not preserved in the array, i.e. not swapped at this time, only * its new index into the array is tracked. Returns the changed memslot's * current index into the memslots array. -* The memslot at the returned index will not be in @slots->id_hash by then. +* The memslot at the returned index will not be in @slots->hva_tree or +* @slots->id_hash by then. * @memslot is a detached struct with desired final data of the changed slot. */ static inline int kvm_memslot_move_backward(struct kvm_memslots *slots,
@@ -1029,6 +1035,7 @@ static inline int kvm_memslot_move_backward(struct kvm_memslots *slots,* update_memslots() will unconditionally overwrite and re-add the * target memslot so it has to be removed here first */ +interval_tree_remove (&mmemslot->hva_node, &slots->hva_tree);hash_del (&mmemslot->id_node);/*
@@ -1043,8 +1050,11 @@ static inline int kvm_memslot_move_backward(struct kvm_memslots *slots,WARN_ON_ONCE (memslot->base_gfn == mslots[i +1 ].base_gfn);/* Shift the next memslot forward one and update its index. */ +interval_tree_remove (&mslots[i +1 ].hva_node, &slots->hva_tree);hash_del (&mslots[i +1 ].id_node); + mslots[i] = mslots[i +1 ]; +interval_tree_insert (&mslots[i].hva_node, &slots->hva_tree);hash_add (slots->id_hash, &mslots[i].id_node, mslots[i].id); }return i;
@@ -1056,10 +1066,12 @@ static inline int kvm_memslot_move_backward(struct kvm_memslots *slots,* is not preserved in the array, i.e. not swapped at this time, only its new * index into the array is tracked. Returns the changed memslot's final index * into the memslots array. -* The memslot at the returned index will not be in @slots->id_hash by then. +* The memslot at the returned index will not be in @slots->hva_tree or +* @slots->id_hash by then. * @memslot is a detached struct with desired final data of the new or * changed slot. -* Assumes that the memslot at @start index is not in @slots->id_hash. +* Assumes that the memslot at @start index is not in @slots->hva_tree or +* @slots->id_hash. */ static inline int kvm_memslot_move_forward(struct kvm_memslots *slots, struct kvm_memory_slot *memslot,
@@ -1075,8 +1087,11 @@ static inline int kvm_memslot_move_forward(struct kvm_memslots *slots,WARN_ON_ONCE (memslot->base_gfn == mslots[i -1 ].base_gfn);/* Shift the next memslot back one and update its index. */ +interval_tree_remove (&mslots[i -1 ].hva_node, &slots->hva_tree);hash_del (&mslots[i -1 ].id_node); + mslots[i] = mslots[i -1 ]; +interval_tree_insert (&mslots[i].hva_node, &slots->hva_tree);hash_add (slots->id_hash, &mslots[i].id_node, mslots[i].id); }return i;
@@ -1149,6 +1164,11 @@ static void update_memslots(struct kvm_memslots *slots,* its index accordingly. */ slots->memslots[i] = *memslot; + slots->memslots[i].hva_node.start = memslot->userspace_addr; + slots->memslots[i].hva_node.last = memslot->userspace_addr + + (memslot->npages <<PAGE_SHIFT ) -1 ; +interval_tree_insert (&slots->memslots[i].hva_node, + &slots->hva_tree);hash_add (slots->id_hash, &slots->memslots[i].id_node, memslot->id); }
@@ -1230,9 +1250,12 @@ static struct kvm_memslots *kvm_dup_memslots(struct kvm_memslots *old,memcpy (slots, old, old_size); + slots->hva_tree =RB_ROOT_CACHED ;hash_init (slots->id_hash); -kvm_for_each_memslot (memslot, slots) +kvm_for_each_memslot (memslot, slots) { +interval_tree_insert (&memslot->hva_node, &slots->hva_tree);hash_add (slots->id_hash, &memslot->id_node, memslot->id); + }return slots; }
PATCH v2 5/8 KVM: s390: Introduce kvm_s390_get_gfn_end()
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
And use it where s390 code would just access the memslot with the highest gfn directly.
No functional change intended.
--- arch/s390/kvm/kvm-s390.c | 2 +- arch/s390/kvm/kvm-s390.h | 12 ++++++++++++ arch/s390/kvm/pv.c | 4 +--- 3 files changed, 14 insertions(+), 4 deletions(-)
arch/s390/kvm/kvm-s390.c +1 -1
@@ -1977,7 +1977,7 @@ static int kvm_s390_get_cmma(struct kvm *kvm, struct kvm_s390_cmma_log *args,if (!ms)return 0 ; next_gfn =kvm_s390_next_dirty_cmma (slots, cur_gfn +1 ); - mem_end = slots->memslots[0 ].base_gfn + slots->memslots[0 ].npages; + mem_end =kvm_s390_get_gfn_end (slots);while (args->count < bufsize) { hva =gfn_to_hva (kvm, cur_gfn);
arch/s390/kvm/kvm-s390.h +12 -0
@@ -208,6 +208,18 @@ static inline int kvm_s390_user_cpu_state_ctrl(struct kvm *kvm)return kvm->arch.user_cpu_state_ctrl !=0 ; } +/* get the end gfn of the last (highest gfn) memslot */ +static inline unsigned long kvm_s390_get_gfn_end (struct kvm_memslots *slots) +{ +struct kvm_memory_slot *ms; + +if (WARN_ON (!slots->used_slots)) +return 0 ; + + ms = slots->memslots; +return ms->base_gfn + ms->npages; +} +/* implemented in pv.c */ int kvm_s390_pv_destroy_cpu (struct kvm_vcpu *vcpu,u16 *rc,u16 *rrc);int kvm_s390_pv_create_cpu (struct kvm_vcpu *vcpu,u16 *rc,u16 *rrc);
arch/s390/kvm/pv.c +1 -3
@@ -117,7 +117,6 @@ static int kvm_s390_pv_alloc_vm(struct kvm *kvm)unsigned long base = uv_info.guest_base_stor_len;unsigned long virt = uv_info.guest_virt_var_stor_len;unsigned long npages =0 , vlen =0 ; -struct kvm_memory_slot *memslot; kvm->arch.pv.stor_var =NULL ; kvm->arch.pv.stor_base =__get_free_pages (GFP_KERNEL_ACCOUNT ,get_order (base));
@@ -131,8 +130,7 @@ static int kvm_s390_pv_alloc_vm(struct kvm *kvm)* Slots are sorted by GFN */ mutex_lock (&kvm->slots_lock); - memslot =kvm_memslots (kvm)->memslots; - npages = memslot->base_gfn + memslot->npages; + npages =kvm_s390_get_gfn_end (kvm_memslots (kvm));mutex_unlock (&kvm->slots_lock); kvm->arch.pv.guest_len = npages *PAGE_SIZE ;
PATCH v2 6/8 KVM: Keep memslots in tree-based structures instead of array-based ones
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
The current memslot code uses a (reverse gfn-ordered) memslot array for keeping track of them.
Because the memslot array that is currently in use cannot be modified every memslot management operation (create, delete, move, change flags) has to make a copy of the whole array so it has a scratch copy to work on.
Strictly speaking, however, it is only necessary to make copy of the memslot that is being modified, copying all the memslots currently present is just a limitation of the array-based memslot implementation.
Two memslot sets, however, are still needed so the VM continues to run on the currently active set while the requested operation is being performed on the second, currently inactive one.
In order to have two memslot sets, but only one copy of actual memslots it is necessary to split out the memslot data from the memslot sets.
The memslots themselves should be also kept independent of each other so they can be individually added or deleted.
These two memslot sets should normally point to the same set of memslots. They can, however, be desynchronized when performing a memslot management operation by replacing the memslot to be modified by its copy. After the operation is complete, both memslot sets once again point to the same, common set of memslot data.
This commit implements the aforementioned idea.
For tracking of gfns an ordinary rbtree is used since memslots cannot overlap in the guest address space and so this data structure is sufficient for ensuring that lookups are done quickly.
The "lru slot" mini-cache, that keeps track of the last found-by-gfn memslot, is still present in the new code.
--- arch/arm64/kvm/mmu.c | 12 +- arch/mips/kvm/mmu.c | 4 +- arch/powerpc/kvm/book3s_64_mmu_hv.c | 8 +- arch/powerpc/kvm/book3s_hv.c | 3 +- arch/powerpc/kvm/book3s_hv_nested.c | 4 +- arch/powerpc/kvm/book3s_hv_uvmem.c | 14 +- arch/powerpc/kvm/book3s_pr.c | 4 +- arch/s390/kvm/kvm-s390.c | 27 +- arch/s390/kvm/kvm-s390.h | 7 +- arch/x86/kvm/mmu/mmu.c | 8 +- arch/x86/kvm/mmu/tdp_mmu.c | 4 +- include/linux/kvm_host.h | 100 ++--- virt/kvm/kvm_main.c | 576 ++++++++++++++-------------- 13 files changed, 394 insertions(+), 377 deletions(-)
arch/arm64/kvm/mmu.c +7 -5
@@ -161,13 +161,13 @@ static void stage2_flush_vm(struct kvm *kvm) {struct kvm_memslots *slots;struct kvm_memory_slot *memslot; -int idx; +int idx, ctr; idx =srcu_read_lock (&kvm->srcu);spin_lock (&kvm->mmu_lock); slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) +kvm_for_each_memslot (memslot, ctr, slots)stage2_flush_memslot (kvm, memslot);spin_unlock (&kvm->mmu_lock);
@@ -452,14 +452,14 @@ void stage2_unmap_vm(struct kvm *kvm) {struct kvm_memslots *slots;struct kvm_memory_slot *memslot; -int idx; +int idx, ctr; idx =srcu_read_lock (&kvm->srcu);mmap_read_lock (current->mm);spin_lock (&kvm->mmu_lock); slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) +kvm_for_each_memslot (memslot, ctr, slots)stage2_unmap_memslot (kvm, memslot);spin_unlock (&kvm->mmu_lock);
@@ -1073,6 +1073,7 @@ static int handle_hva_to_gpa(struct kvm *kvm, void *data) {struct kvm_memslots *slots; +int idxactive;struct interval_tree_node *node;struct kvm_memory_slot *memslot;int ret =0 ;
@@ -1081,6 +1082,7 @@ static int handle_hva_to_gpa(struct kvm *kvm,return 0 ; slots =kvm_memslots (kvm); + idxactive =kvm_memslots_idx (slots);/* we only care about the pages that the guest sees */ kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {
@@ -1088,7 +1090,7 @@ static int handle_hva_to_gpa(struct kvm *kvm,gfn_t gpa; memslot = container_of(node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
arch/mips/kvm/mmu.c +3 -1
@@ -449,6 +449,7 @@ static int handle_hva_to_gpa(struct kvm *kvm, void *data) {struct kvm_memslots *slots; +int idxactive;struct interval_tree_node *node;struct kvm_memory_slot *memslot;int ret =0 ;
@@ -457,6 +458,7 @@ static int handle_hva_to_gpa(struct kvm *kvm,return 0 ; slots =kvm_memslots (kvm); + idxactive =kvm_memslots_idx (slots);/* we only care about the pages that the guest sees */ kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {
@@ -464,7 +466,7 @@ static int handle_hva_to_gpa(struct kvm *kvm,gfn_t gfn, gfn_end; memslot = container_of(node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
arch/powerpc/kvm/book3s_64_mmu_hv.c +5 -3
@@ -734,11 +734,11 @@ void kvmppc_rmap_reset(struct kvm *kvm) {struct kvm_memslots *slots;struct kvm_memory_slot *memslot; -int srcu_idx; +int srcu_idx, ctr; srcu_idx =srcu_read_lock (&kvm->srcu); slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_memslot (memslot, ctr, slots) {/* Mutual exclusion with kvm_unmap_hva_range etc. */ spin_lock (&kvm->mmu_lock);/*
@@ -763,6 +763,7 @@ static int kvm_handle_hva_range(struct kvm *kvm,int ret;int retval =0 ;struct kvm_memslots *slots; +int idxactive;struct interval_tree_node *node;struct kvm_memory_slot *memslot;
@@ -770,12 +771,13 @@ static int kvm_handle_hva_range(struct kvm *kvm,return 0 ; slots =kvm_memslots (kvm); + idxactive =kvm_memslots_idx (slots);kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn, gfn_end; memslot = container_of(node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
arch/powerpc/kvm/book3s_hv.c +2 -1
@@ -5574,11 +5574,12 @@ static int kvmhv_svm_off(struct kvm *kvm)for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) {struct kvm_memory_slot *memslot;struct kvm_memslots *slots =__kvm_memslots (kvm, i); +int ctr;if (!slots)continue ; -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_memslot (memslot, ctr, slots) {kvmppc_uvmem_drop_pages (memslot, kvm, true);uv_unregister_mem_slot (kvm->arch.lpid, memslot->id); }
arch/powerpc/kvm/book3s_hv_nested.c +2 -2
@@ -698,7 +698,7 @@ void kvmhv_release_all_nested(struct kvm *kvm)struct kvm_nested_guest *gp;struct kvm_nested_guest *freelist =NULL ;struct kvm_memory_slot *memslot; -int srcu_idx; +int srcu_idx, ctr;spin_lock (&kvm->mmu_lock);for (i =0 ; i <= kvm->arch.max_nested_lpid; i++) {
@@ -719,7 +719,7 @@ void kvmhv_release_all_nested(struct kvm *kvm) } srcu_idx =srcu_read_lock (&kvm->srcu); -kvm_for_each_memslot (memslot,kvm_memslots (kvm)) +kvm_for_each_memslot (memslot, ctr,kvm_memslots (kvm))kvmhv_free_memslot_nest_rmap (memslot);srcu_read_unlock (&kvm->srcu, srcu_idx); }
arch/powerpc/kvm/book3s_hv_uvmem.c +7 -7
@@ -458,7 +458,7 @@ unsigned long kvmppc_h_svm_init_start(struct kvm *kvm)struct kvm_memslots *slots;struct kvm_memory_slot *memslot, *m;int ret =H_SUCCESS ; -int srcu_idx; +int srcu_idx, ctr; kvm->arch.secure_guest =KVMPPC_SECURE_INIT_START ;
@@ -477,7 +477,7 @@ unsigned long kvmppc_h_svm_init_start(struct kvm *kvm)/* register the memslot */ slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_memslot (memslot, ctr, slots) { ret =__kvmppc_uvmem_memslot_create (kvm, memslot);if (ret)break ;
@@ -485,7 +485,7 @@ unsigned long kvmppc_h_svm_init_start(struct kvm *kvm)if (ret) { slots =kvm_memslots (kvm); -kvm_for_each_memslot (m, slots) { +kvm_for_each_memslot (m, ctr, slots) {if (m == memslot)break ;__kvmppc_uvmem_memslot_delete (kvm, memslot);
@@ -646,7 +646,7 @@ void kvmppc_uvmem_drop_pages(const struct kvm_memory_slot *slot,unsigned long kvmppc_h_svm_init_abort (struct kvm *kvm) { -int srcu_idx; +int srcu_idx, ctr;struct kvm_memory_slot *memslot;/*
@@ -661,7 +661,7 @@ unsigned long kvmppc_h_svm_init_abort(struct kvm *kvm) srcu_idx =srcu_read_lock (&kvm->srcu); -kvm_for_each_memslot (memslot,kvm_memslots (kvm)) +kvm_for_each_memslot (memslot, ctr,kvm_memslots (kvm))kvmppc_uvmem_drop_pages (memslot, kvm, false);srcu_read_unlock (&kvm->srcu, srcu_idx);
@@ -820,7 +820,7 @@ unsigned long kvmppc_h_svm_init_done(struct kvm *kvm) {struct kvm_memslots *slots;struct kvm_memory_slot *memslot; -int srcu_idx; +int srcu_idx, ctr;long ret =H_SUCCESS ;if (!(kvm->arch.secure_guest &KVMPPC_SECURE_INIT_START ))
@@ -829,7 +829,7 @@ unsigned long kvmppc_h_svm_init_done(struct kvm *kvm)/* migrate any unmoved normal pfn to device pfns*/ srcu_idx =srcu_read_lock (&kvm->srcu); slots =kvm_memslots (kvm); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_memslot (memslot, ctr, slots) { ret =kvmppc_uv_migrate_mem_slot (kvm, memslot);if (ret) {/*
arch/powerpc/kvm/book3s_pr.c +3 -1
@@ -431,6 +431,7 @@ static void do_kvm_unmap_hva(struct kvm *kvm, unsigned long start,long i;struct kvm_vcpu *vcpu;struct kvm_memslots *slots; +int idxactive;struct interval_tree_node *node;struct kvm_memory_slot *memslot;
@@ -438,12 +439,13 @@ static void do_kvm_unmap_hva(struct kvm *kvm, unsigned long start,return ; slots =kvm_memslots (kvm); + idxactive =kvm_memslots_idx (slots);kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn, gfn_end; memslot = container_of(node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
arch/s390/kvm/kvm-s390.c +14 -13
@@ -1006,13 +1006,13 @@ static int kvm_s390_vm_start_migration(struct kvm *kvm)struct kvm_memory_slot *ms;struct kvm_memslots *slots;unsigned long ram_pages =0 ; -int slotnr; +int ctr;/* migration mode already enabled */ if (kvm->arch.migration_mode)return 0 ; slots =kvm_memslots (kvm); -if (!slots || !slots->used_slots) +if (!slots ||kvm_memslots_empty (slots))return -EINVAL ;if (!kvm->arch.use_cmma) {
@@ -1020,8 +1020,7 @@ static int kvm_s390_vm_start_migration(struct kvm *kvm)return 0 ; }/* mark all the pages in active slots as dirty */ -for (slotnr =0 ; slotnr < slots->used_slots; slotnr++) { - ms = slots->memslots + slotnr; +kvm_for_each_memslot (ms, ctr, slots) {if (!ms->dirty_bitmap)return -EINVAL ;/*
@@ -1939,22 +1938,24 @@ static unsigned long kvm_s390_next_dirty_cmma(struct kvm_memslots *slots, unsigned long cur_gfn) {struct kvm_memory_slot *ms =search_memslots (slots, cur_gfn, true); -int slotidx = ms - slots->memslots;unsigned long ofs = cur_gfn - ms->base_gfn; +int idxactive =kvm_memslots_idx (slots); +struct rb_node *mnode = &ms->gfn_node[idxactive];if (ms->base_gfn + ms->npages <= cur_gfn) { - slotidx--; + mnode =rb_next (mnode);/* If we are above the highest slot, wrap around */ -if (slotidx <0 ) - slotidx = slots->used_slots -1 ; +if (!mnode) + mnode =rb_first (&slots->gfn_tree); - ms = slots->memslots + slotidx; + ms = container_of(mnode, struct kvm_memory_slot, + gfn_node[idxactive]); ofs =0 ; } ofs =find_next_bit (kvm_second_dirty_bitmap (ms), ms->npages, ofs); -while ((slotidx >0 ) && (ofs >= ms->npages)) { - slotidx--; - ms = slots->memslots + slotidx; +while (ofs >= ms->npages && (mnode =rb_next (mnode))) { + ms = container_of(mnode, struct kvm_memory_slot, + gfn_node[idxactive]); ofs =find_next_bit (kvm_second_dirty_bitmap (ms), ms->npages,0 ); }return ms->base_gfn + ofs;
@@ -1967,7 +1968,7 @@ static int kvm_s390_get_cmma(struct kvm *kvm, struct kvm_s390_cmma_log *args,struct kvm_memslots *slots =kvm_memslots (kvm);struct kvm_memory_slot *ms; -if (unlikely (!slots->used_slots)) +if (unlikely (kvm_memslots_empty (slots)))return 0 ; cur_gfn =kvm_s390_next_dirty_cmma (slots, args->start_gfn);
arch/s390/kvm/kvm-s390.h +5 -2
@@ -211,12 +211,15 @@ static inline int kvm_s390_user_cpu_state_ctrl(struct kvm *kvm)/* get the end gfn of the last (highest gfn) memslot */ static inline unsigned long kvm_s390_get_gfn_end (struct kvm_memslots *slots) { +struct rb_node *node; +int idxactive =kvm_memslots_idx (slots);struct kvm_memory_slot *ms; -if (WARN_ON (!slots->used_slots)) +if (WARN_ON (kvm_memslots_empty (slots)))return 0 ; - ms = slots->memslots; + node =rb_last (&slots->gfn_tree); + ms = container_of(node, struct kvm_memory_slot, gfn_node[idxactive]);return ms->base_gfn + ms->npages; }
arch/x86/kvm/mmu/mmu.c +6 -2
@@ -1434,15 +1434,17 @@ static __always_inline int kvm_handle_hva_range(struct kvm *kvm,return 0 ;for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) { +int idxactive;struct interval_tree_node *node; slots =__kvm_memslots (kvm, i); + idxactive =kvm_memslots_idx (slots);kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;gfn_t gfn_start, gfn_end; memslot = container_of(node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
@@ -5498,8 +5500,10 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end)write_lock (&kvm->mmu_lock);for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) { +int ctr; + slots =__kvm_memslots (kvm, i); -kvm_for_each_memslot (memslot, slots) { +kvm_for_each_memslot (memslot, ctr, slots) {gfn_t start, end; start =max (gfn_start, memslot->base_gfn);
arch/x86/kvm/mmu/tdp_mmu.c +3 -1
@@ -894,9 +894,11 @@ static __always_inline int kvm_tdp_mmu_handle_hva_range(struct kvm *kvm,for (as_id =0 ; as_id <KVM_ADDRESS_SPACE_NUM ; as_id++) {for_each_tdp_mmu_root_yield_safe (kvm, root, as_id) { +int idxactive;struct interval_tree_node *node; slots =__kvm_memslots (kvm, as_id); + idxactive =kvm_memslots_idx (slots);kvm_for_each_hva_range_memslot (node, slots, start, end -1 ) {unsigned long hva_start, hva_end;
@@ -904,7 +906,7 @@ static __always_inline int kvm_tdp_mmu_handle_hva_range(struct kvm *kvm, memslot =container_of (node, struct kvm_memory_slot, - hva_node); + hva_node[idxactive]); hva_start =max (start, memslot->userspace_addr); hva_end =min (end, memslot->userspace_addr + (memslot->npages <<PAGE_SHIFT ));
include/linux/kvm_host.h +53 -47
161 lines not on this page · raw message
virt/kvm/kvm_main.c +284 -292
719 lines not on this page · raw message
PATCH v2 7/8 KVM: Optimize gfn lookup in kvm_zap_gfn_range()
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
Introduce a memslots gfn upper bound operation and use it to optimize kvm_zap_gfn_range().
This way this handler can do a quick lookup for intersecting gfns and won't have to do a linear scan of the whole memslot set.
--- arch/x86/kvm/mmu/mmu.c | 41 ++++++++++++++++++++++++++++++++++++++-- include/linux/kvm_host.h | 22 +++++++++++++++++++++ 2 files changed, 61 insertions(+), 2 deletions(-)
arch/x86/kvm/mmu/mmu.c +39 -2
@@ -5498,14 +5498,51 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end)int i;bool flush = false; +if (gfn_end == gfn_start ||WARN_ON (gfn_end < gfn_start)) +return ; +write_lock (&kvm->mmu_lock);for (i =0 ; i <KVM_ADDRESS_SPACE_NUM ; i++) { -int ctr; +int idxactive; +struct rb_node *node; slots =__kvm_memslots (kvm, i); -kvm_for_each_memslot (memslot, ctr, slots) { + idxactive =kvm_memslots_idx (slots); + +/* +* Find the slot with the lowest gfn that can possibly intersect with +* the range, so we'll ideally have slot start <= range start +*/ + node =kvm_memslots_gfn_upper_bound (slots, gfn_start); +if (node) { +struct rb_node *pnode; + +/* +* A NULL previous node means that the very first slot +* already has a higher start gfn. +* In this case slot start > range start. +*/ + pnode =rb_prev (node); +if (pnode) + node = pnode; + }else { +/* a NULL node below means no slots */ + node =rb_last (&slots->gfn_tree); + } + +for ( ; node; node =rb_next (node)) {gfn_t start, end; + memslot = container_of(node, struct kvm_memory_slot, + gfn_node[idxactive]); + +/* +* If this slot starts beyond or at the end of the range so does +* every next one +*/ +if (memslot->base_gfn >= gfn_start + gfn_end) +break ; + start =max (gfn_start, memslot->base_gfn); end =min (gfn_end, memslot->base_gfn + memslot->npages);if (start >= end)
include/linux/kvm_host.h +22 -0
@@ -703,6 +703,28 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id)return NULL ; } +static inline +struct rb_node *kvm_memslots_gfn_upper_bound (struct kvm_memslots *slots, +gfn_t gfn) +{ +int idxactive =kvm_memslots_idx (slots); +struct rb_node *node, *result =NULL ; + +for (node = slots->gfn_tree.rb_node; node; ) { +struct kvm_memory_slot *slot; + + slot = container_of(node, struct kvm_memory_slot, + gfn_node[idxactive]); +if (gfn < slot->base_gfn) { + result = node; + node = node->rb_left; + }else + node = node->rb_right; + } + +return result; +} +/* * KVM_SET_USER_MEMORY_REGION ioctl allows the following operations: * - create a new memory slot
PATCH v2 8/8 KVM: Optimize overlapping memslots check
In reply to Maciej S. SzmigieroFrom: "Maciej S. Szmigiero" <[email protected]>
Do a quick lookup for possibly overlapping gfns when creating or moving a memslot instead of performing a linear scan of the whole memslot set.
--- virt/kvm/kvm_main.c | 65 ++++++++++++++++++++++++++++++++++++++------- 1 file changed, 56 insertions(+), 9 deletions(-)
virt/kvm/kvm_main.c +56 -9
@@ -1341,6 +1341,59 @@ static int kvm_delete_memslot(struct kvm *kvm,return kvm_set_memslot (kvm, mem, old, &new, as_id,KVM_MR_DELETE ); } +static bool kvm_check_memslot_overlap (struct kvm_memslots *slots, +struct kvm_memory_slot *nslot) +{ +int idxactive =kvm_memslots_idx (slots); +struct rb_node *node; + +/* +* Find the slot with the lowest gfn that can possibly intersect with +* the new slot, so we'll ideally have slot start <= nslot start +*/ + node =kvm_memslots_gfn_upper_bound (slots, nslot->base_gfn); +if (node) { +struct rb_node *pnode; + +/* +* A NULL previous node means that the very first slot +* already has a higher start gfn. +* In this case slot start > nslot start. +*/ + pnode =rb_prev (node); +if (pnode) + node = pnode; + }else { +/* a NULL node below means no existing slots */ + node =rb_last (&slots->gfn_tree); + } + +for ( ; node; node =rb_next (node)) { +struct kvm_memory_slot *cslot; + + cslot = container_of(node, struct kvm_memory_slot, + gfn_node[idxactive]); + +/* +* if this slot starts beyond or at the end of the new slot +* so does every next one +*/ +if (cslot->base_gfn >= nslot->base_gfn + nslot->npages) +break ; + +if (cslot->id == nslot->id) +continue ; + +if (cslot->base_gfn >= nslot->base_gfn) +return true; + +if (cslot->base_gfn + cslot->npages > nslot->base_gfn) +return true; + } + +return false; +} +/* * Allocate some memory and give it an address in the guest physical address * space.
@@ -1426,16 +1479,10 @@ int __kvm_set_memory_region(struct kvm *kvm, }if ((change ==KVM_MR_CREATE ) || (change ==KVM_MR_MOVE )) { -int ctr; -/* Check for overlaps */ -kvm_for_each_memslot (tmp, ctr,__kvm_memslots (kvm, as_id)) { -if (tmp->id == id) -continue ; -if (!((new.base_gfn + new.npages <= tmp->base_gfn) || - (new.base_gfn >= tmp->base_gfn + tmp->npages))) -return -EEXIST ; - } +if (kvm_check_memslot_overlap (__kvm_memslots (kvm, as_id), + &new)) +return -EEXIST ; }/* Allocate/free page dirty bitmap as needed */
Sean Christopherson
maintainerQuoted 1 line · Maciej S. Szmigiero
From: "Maciej S. Szmigiero" <[email protected]>
Grr, this entire series got autobinned into my spam folder, which I obviously don't check very often. I won't be able to take a look until next week at the earliest, any chance you'd want to rebase to the latest kvm/queue and spin v3? The rebase will probably be a bit painful, but on the plus side the majority of the arch specific changes will disappear now that walking the memslots for the MMU notifiers is done in common code.
Quoted 25 lines
arch/arm64/kvm/Kconfig | 1 + arch/arm64/kvm/mmu.c | 20 +- arch/mips/kvm/Kconfig | 1 + arch/mips/kvm/mmu.c | 12 +- arch/powerpc/kvm/Kconfig | 1 + arch/powerpc/kvm/book3s_64_mmu_hv.c | 16 +- arch/powerpc/kvm/book3s_64_vio.c | 2 +- arch/powerpc/kvm/book3s_64_vio_hv.c | 2 +- arch/powerpc/kvm/book3s_hv.c | 3 +- arch/powerpc/kvm/book3s_hv_nested.c | 4 +- arch/powerpc/kvm/book3s_hv_uvmem.c | 14 +- arch/powerpc/kvm/book3s_pr.c | 12 +- arch/s390/kvm/Kconfig | 1 + arch/s390/kvm/kvm-s390.c | 66 +--- arch/s390/kvm/kvm-s390.h | 15 + arch/s390/kvm/pv.c | 4 +- arch/x86/include/asm/kvm_host.h | 2 +- arch/x86/kvm/Kconfig | 1 + arch/x86/kvm/mmu/mmu.c | 78 ++-- arch/x86/kvm/mmu/tdp_mmu.c | 15 +- arch/x86/kvm/x86.c | 18 +- include/linux/kvm_host.h | 139 ++++--- virt/kvm/kvm_main.c | 592 ++++++++++++++++------------ 23 files changed, 603 insertions(+), 416 deletions(-)
Quoted 9 lines · Sean Christopherson
Quoted 1 line · Maciej S. Szmigiero
From: "Maciej S. Szmigiero" <[email protected]>
Grr, this entire series got autobinned into my spam folder, which I obviously don't check very often. I won't be able to take a look until next week at the earliest, any chance you'd want to rebase to the latest kvm/queue and spin v3? The rebase will probably be a bit painful, but on the plus side the majority of the arch specific changes will disappear now that walking the memslots for the MMU notifiers is done in common code.
A respin (and a re-test) of this series is needed anyway since these patches have conflicts with the now-merged MMU notifiers rewrite (that you mention above).
Will try to post it by the next week.
Thanks,
Maciej