KVM: optimize memslots searching

PATCH In review Xiao Guangrong 4 participants 23 messages Nov 18, 2011 – Nov 21, 2011

Subsystems (5)

x86 KVM PowerPC KVM x86 +1 more subsystems

lore

Share & tools

lore

Xiao Guangrong

author

2011-11-18 09:16 UTC #0 lore raw

v2 cover KVM: optimize memslots searching

This is the more work base on my v1 patchset which is posted some months ago, it can be found at:
https://lkml.org/lkml/2011/2/22/68

Change log:
- sort memslots base on its size and do the line search instead of binary search base on gfn, it is from Avi's idea.
- in order to reduce cache footprint, memslots are sorted in the array of kvm->memslots->memslots[] and introduce a table to map slot id to index in the array

There is the performance result:

autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8

kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66

Xiao Guangrong

author

2011-11-18 09:17 UTC #1 lore raw

PATCH v2 1/6 KVM: introduce KVM_MEM_SLOTS_NUM macro

Introduce KVM_MEM_SLOTS_NUM macro to instead of
KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS

Signed-off-by Xiao Guangrong <[email protected]>

---
 arch/x86/include/asm/kvm_host.h |    4 +++-
 arch/x86/kvm/mmu.c              |    2 +-
 include/linux/kvm_host.h        |    7 +++++--
 virt/kvm/kvm_main.c             |    2 +-
 4 files changed, 10 insertions(+), 5 deletions(-)

arch/x86/include/asm/kvm_host.h +3 -1

index 6d83264..b80a310 100644
@@ -31,6 +31,8 @@
 #define KVM_MEMORY_SLOTS 32
 /* memory slots that does not exposed to userspace */
 #define KVM_PRIVATE_MEM_SLOTS 4
+#define KVM_MEM_SLOTS_NUM (KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
+
 #define KVM_MMIO_SIZE 16
 
 #define KVM_PIO_PAGE_OFFSET 1

@@ -228,7 +230,7 @@ struct kvm_mmu_page {
 	 * One bit set per slot which has memory
 	 * in this shadow page.
 	 */
-	DECLARE_BITMAP(slot_bitmap, KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS);
+	DECLARE_BITMAP(slot_bitmap, KVM_MEM_SLOTS_NUM);
 	bool unsync;
 	int root_count;          /* Currently serving as active root */
 	unsigned int unsync_children;

arch/x86/kvm/mmu.c +1 -1

index a9b3a32..e6c2755 100644
@@ -1337,7 +1337,7 @@ static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
 						  PAGE_SIZE);
 	set_page_private(virt_to_page(sp->spt), (unsigned long)sp);
 	list_add(&sp->link, &vcpu->kvm->arch.active_mmu_pages);
-	bitmap_zero(sp->slot_bitmap, KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS);
+	bitmap_zero(sp->slot_bitmap, KVM_MEM_SLOTS_NUM);
 	sp->parent_ptes = 0;
 	mmu_page_add_parent_pte(vcpu, sp, parent_pte);
 	kvm_mod_used_mmu_pages(vcpu->kvm, +1);

include/linux/kvm_host.h +5 -2

index c6a2ec9..a42d50b 100644
@@ -226,11 +226,14 @@ struct kvm_irq_routing_table {};
 
 #endif
 
+#ifndef KVM_MEM_SLOTS_NUM
+#define KVM_MEM_SLOTS_NUM (KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
+#endif
+
 struct kvm_memslots {
 	int nmemslots;
 	u64 generation;
-	struct kvm_memory_slot memslots[KVM_MEMORY_SLOTS +
-					KVM_PRIVATE_MEM_SLOTS];
+	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
 };
 
 struct kvm {

virt/kvm/kvm_main.c +1 -1

index d9cfb78..eb55a11 100644
@@ -662,7 +662,7 @@ int __kvm_set_memory_region(struct kvm *kvm,
 			(void __user *)(unsigned long)mem->userspace_addr,
 			mem->memory_size)))
 		goto out;
-	if (mem->slot >= KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
+	if (mem->slot >= KVM_MEM_SLOTS_NUM)
 		goto out;
 	if (mem->guest_phys_addr + mem->memory_size < mem->guest_phys_addr)
 		goto out;

Signature · 1 line

1.7.7.1

Xiao Guangrong

author

2011-11-18 09:17 UTC #2 lore raw

PATCH v2 2/6 KVM: introduce update_memslots function

In reply to Xiao Guangrong

Introduce update_memslots to update slot which will be update to kvm->memslots

Signed-off-by Xiao Guangrong <[email protected]>

---
 arch/x86/kvm/x86.c       |    2 +-
 include/linux/kvm_host.h |    1 +
 virt/kvm/kvm_main.c      |   22 +++++++++++++++-------
 3 files changed, 17 insertions(+), 8 deletions(-)

arch/x86/kvm/x86.c +1 -1

index 9eff4af..56d1a39 100644
@@ -3504,7 +3504,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 			goto out;
 		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
 		slots->memslots[log->slot].dirty_bitmap = dirty_bitmap;
-		slots->generation++;
+		update_memslots(slots, NULL);
 
 		old_slots = kvm->memslots;
 		rcu_assign_pointer(kvm->memslots, slots);

include/linux/kvm_host.h +1 -0

index a42d50b..bb8728e 100644
@@ -319,6 +319,7 @@ void kvm_exit(void);
 
 void kvm_get_kvm(struct kvm *kvm);
 void kvm_put_kvm(struct kvm *kvm);
+void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *new);
 
 static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 {

virt/kvm/kvm_main.c +15 -7

index eb55a11..0fb3aeb 100644
@@ -629,6 +629,19 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
 }
 #endif /* !CONFIG_S390 */
 
+void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *new)
+{
+	if (new) {
+		int id = new->id;
+
+		slots->memslots[id] = *new;
+		if (id >= slots->nmemslots)
+			slots->nmemslots = id + 1;
+	}
+
+	slots->generation++;
+}
+
 /*
  * Allocate some memory and give it an address in the guest physical address
  * space.

@@ -779,10 +792,8 @@ skip_lpage:
 		if (!slots)
 			goto out_free;
 		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-		if (mem->slot >= slots->nmemslots)
-			slots->nmemslots = mem->slot + 1;
-		slots->generation++;
 		slots->memslots[mem->slot].flags |= KVM_MEMSLOT_INVALID;
+		update_memslots(slots, NULL);
 
 		old_memslots = kvm->memslots;
 		rcu_assign_pointer(kvm->memslots, slots);

@@ -814,9 +825,6 @@ skip_lpage:
 	if (!slots)
 		goto out_free;
 	memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-	if (mem->slot >= slots->nmemslots)
-		slots->nmemslots = mem->slot + 1;
-	slots->generation++;
 
 	/* actual memory is freed via old in kvm_free_physmem_slot below */
 	if (!npages) {

@@ -826,7 +834,7 @@ skip_lpage:
 			new.lpage_info[i] = NULL;
 	}
 
-	slots->memslots[mem->slot] = new;
+	update_memslots(slots, &new);
 	old_memslots = kvm->memslots;
 	rcu_assign_pointer(kvm->memslots, slots);
 	synchronize_srcu_expedited(&kvm->srcu);

Signature · 1 line

1.7.7.1

Xiao Guangrong

author

2011-11-18 09:18 UTC #3 lore raw

PATCH v2 3/6 KVM: introduce kvm_for_each_memslot macro

In reply to Xiao Guangrong

Introduce kvm_for_each_memslot to walk all valid memslot

Signed-off-by Xiao Guangrong <[email protected]>

---
 arch/ia64/kvm/kvm-ia64.c |    4 +---
 arch/x86/kvm/mmu.c       |    9 +++++----
 include/linux/kvm_host.h |    4 ++++
 virt/kvm/iommu.c         |   13 +++++++------
 virt/kvm/kvm_main.c      |    5 +++--
 5 files changed, 20 insertions(+), 15 deletions(-)

arch/ia64/kvm/kvm-ia64.c +1 -3

index 43f4c92..7d5bc81 100644
@@ -1370,10 +1370,8 @@ static void kvm_release_vm_pages(struct kvm *kvm)
 	unsigned long base_gfn;
 
 	slots = kvm_memslots(kvm);
-	for (i = 0; i < slots->nmemslots; i++) {
-		memslot = &slots->memslots[i];
+	kvm_for_each_memslot(slots, memslot, i) {
 		base_gfn = memslot->base_gfn;
-
 		for (j = 0; j < memslot->npages; j++) {
 			if (memslot->rmap[j])
 				put_page((struct page *)memslot->rmap[j]);

arch/x86/kvm/mmu.c +5 -4

index e6c2755..53dbae0 100644
@@ -1120,11 +1120,11 @@ static int kvm_handle_hva(struct kvm *kvm, unsigned long hva,
 	int ret;
 	int retval = 0;
 	struct kvm_memslots *slots;
+	struct kvm_memory_slot *memslot;
 
 	slots = kvm_memslots(kvm);
 
-	for (i = 0; i < slots->nmemslots; i++) {
-		struct kvm_memory_slot *memslot = &slots->memslots[i];
+	kvm_for_each_memslot(slots, memslot, i) {
 		unsigned long start = memslot->userspace_addr;
 		unsigned long end;

@@ -3977,11 +3977,12 @@ unsigned int kvm_mmu_calculate_mmu_pages(struct kvm *kvm)
 	unsigned int nr_mmu_pages;
 	unsigned int  nr_pages = 0;
 	struct kvm_memslots *slots;
+	struct kvm_memory_slot *memslot;
 
 	slots = kvm_memslots(kvm);
 
-	for (i = 0; i < slots->nmemslots; i++)
-		nr_pages += slots->memslots[i].npages;
+	kvm_for_each_memslot(slots, memslot, i)
+		nr_pages += memslot->npages;
 
 	nr_mmu_pages = nr_pages * KVM_PERMILLE_MMU_PAGES / 1000;
 	nr_mmu_pages = max(nr_mmu_pages,

include/linux/kvm_host.h +4 -0

index bb8728e..10524c0 100644
@@ -307,6 +307,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)
 
+#define kvm_for_each_memslot(slots, memslot, i)	\
+	for (i = 0; i < (slots)->nmemslots &&	\
+	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+
 int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id);
 void kvm_vcpu_uninit(struct kvm_vcpu *vcpu);

virt/kvm/iommu.c +7 -6

index d5f3b8d..02df243 100644
@@ -134,12 +134,13 @@ static int kvm_iommu_map_memslots(struct kvm *kvm)
 {
 	int i, idx, r = 0;
 	struct kvm_memslots *slots;
+	struct kvm_memory_slot *memslot;
 
 	idx = srcu_read_lock(&kvm->srcu);
 	slots = kvm_memslots(kvm);
 
-	for (i = 0; i < slots->nmemslots; i++) {
-		r = kvm_iommu_map_pages(kvm, &slots->memslots[i]);
+	kvm_for_each_memslot(slots, memslot, i) {
+		r = kvm_iommu_map_pages(kvm, memslot);
 		if (r)
 			break;
 	}

@@ -311,14 +312,14 @@ static int kvm_iommu_unmap_memslots(struct kvm *kvm)
 {
 	int i, idx;
 	struct kvm_memslots *slots;
+	struct kvm_memory_slot *memslot;
 
 	idx = srcu_read_lock(&kvm->srcu);
 	slots = kvm_memslots(kvm);
 
-	for (i = 0; i < slots->nmemslots; i++) {
-		kvm_iommu_put_pages(kvm, slots->memslots[i].base_gfn,
-				    slots->memslots[i].npages);
-	}
+	kvm_for_each_memslot(slots, memslot, i)
+		kvm_iommu_put_pages(kvm, memslot->base_gfn, memslot->npages);
+
 	srcu_read_unlock(&kvm->srcu, idx);
 
 	return 0;

virt/kvm/kvm_main.c +3 -2

index 0fb3aeb..ec3b03b 100644
@@ -549,9 +549,10 @@ void kvm_free_physmem(struct kvm *kvm)
 {
 	int i;
 	struct kvm_memslots *slots = kvm->memslots;
+	struct kvm_memory_slot *memslot;
 
-	for (i = 0; i < slots->nmemslots; ++i)
-		kvm_free_physmem_slot(&slots->memslots[i], NULL);
+	kvm_for_each_memslot(slots, memslot, i)
+		kvm_free_physmem_slot(memslot, NULL);
 
 	kfree(kvm->memslots);
 }

Signature · 1 line

1.7.7.1

Avi Kivity

2011-11-20 11:22 UTC #4 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

include/linux/kvm_host.h static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i) · line 314

Quoted 12 lines · Xiao Guangrong

index bb8728e..10524c0 100644

include/linux/kvm_host.h +4 -0

@@ -307,6 +307,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)
 
+#define kvm_for_each_memslot(slots, memslot, i)	\
+	for (i = 0; i < (slots)->nmemslots &&	\
+	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+

Statement expression not needed, you can use the comma operator:

  i < (slots)->nmemslots && (memslot = @(slots)->memslots[i], true)

or even

memslot = &(slots)->memslots[i], i < (slots)->nmemslots

or just kill i and make memslot the loop variable.

Signature · 1 line

error compiling committee.c: too many arguments to function

Takuya Yoshikawa

2011-11-21 00:53 UTC #5 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

Quoted 16 lines · Avi Kivity

include/linux/kvm_host.h static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i) · line 314
Quoted 12 lines · Xiao Guangrong
index bb8728e..10524c0 100644
include/linux/kvm_host.h +4 -0
@@ -307,6 +307,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
  	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
  	     idx++)
 
+#define kvm_for_each_memslot(slots, memslot, i)	\
+	for (i = 0; i<  (slots)->nmemslots&&	\
+	      ({ memslot =&(slots)->memslots[i]; 1; }); i++)
+
 
Statement expression not needed, you can use the comma operator:

Quoted 8 lines

   i<  (slots)->nmemslots&&  (memslot = @(slots)->memslots[i], true)

or even

   memslot =&(slots)->memslots[i], i<  (slots)->nmemslots

or just kill i and make memslot the loop variable.

Do you have any preference for the arguments ordering?

I think placing the target one, memslot in this case, first is conventional in the kernel code, except when we want to place "kvm" or something like that.

But in kvm code, there seems to be some difference.

Takuya

Avi Kivity

2011-11-21 08:34 UTC #6 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

Quoted 27 lines · Takuya Yoshikawa

Quoted 17 lines · Avi Kivity
include/linux/kvm_host.h static inline struct kvm_vcpu · line 315
Quoted 13 lines · Xiao Guangrong
index bb8728e..10524c0 100644
include/linux/kvm_host.h +4 -0
@@ -307,6 +307,10 @@ static inline struct kvm_vcpu
 *kvm_get_vcpu(struct kvm *kvm, int i)
           (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
           idx++)
 
+#define kvm_for_each_memslot(slots, memslot, i)    \
+    for (i = 0; i<  (slots)->nmemslots&&    \
+          ({ memslot =&(slots)->memslots[i]; 1; }); i++)
+
 
Statement expression not needed, you can use the comma operator:
Quoted 8 lines
   i<  (slots)->nmemslots&&  (memslot = @(slots)->memslots[i], true)
or even
   memslot =&(slots)->memslots[i], i<  (slots)->nmemslots
or just kill i and make memslot the loop variable.

Quoted 8 lines

Do you have any preference for the arguments ordering?
I think placing the target one, memslot in this case, first is conventional in
the kernel code, except when we want to place "kvm" or something like that.
But in kvm code, there seems to be some difference.

You mean for the macro? Yes, making memslot the first argument is a good idea. Any difference in kvm code is not intentional.

Signature · 1 line

error compiling committee.c: too many arguments to function

Takuya Yoshikawa

2011-11-21 08:39 UTC #7 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

Quoted 7 lines · Avi Kivity

Quoted 7 lines
Do you have any preference for the arguments ordering?
I think placing the target one, memslot in this case, first is conventional in
the kernel code, except when we want to place "kvm" or something like that.

Quoted 5 lines

Quoted 1 line
But in kvm code, there seems to be some difference.
You mean for the macro? Yes, making memslot the first argument is a good idea. Any difference in kvm code is not intentional.

Yes.

Xiao, please change the order if you have no problem.

Thanks,
Takuya

Xiao Guangrong

author

2011-11-21 08:43 UTC #8 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

Quoted 10 lines · Takuya Yoshikawa

Quoted 9 lines · Avi Kivity
Quoted 8 lines
Do you have any preference for the arguments ordering?
I think placing the target one, memslot in this case, first is conventional in
the kernel code, except when we want to place "kvm" or something like that.
But in kvm code, there seems to be some difference.

Quoted 8 lines

Quoted 3 lines
You mean for the macro? Yes, making memslot the first argument is a good idea. Any difference in kvm code is not intentional.
Yes.
Xiao, please change the order if you have no problem.

OK, will change it in the next version, thanks!

Xiao Guangrong

author

2011-11-21 03:33 UTC #9 lore raw

Re: [PATCH v2 3/6] KVM: introduce kvm_for_each_memslot macro

In reply to Avi Kivity

Quoted 16 lines · Avi Kivity

include/linux/kvm_host.h static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i) · line 314
Quoted 12 lines · Xiao Guangrong
index bb8728e..10524c0 100644
include/linux/kvm_host.h +4 -0
@@ -307,6 +307,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)
 
+#define kvm_for_each_memslot(slots, memslot, i)	\
+	for (i = 0; i < (slots)->nmemslots &&	\
+	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+
 
Statement expression not needed, you can use the comma operator:

Quoted 8 lines

  i < (slots)->nmemslots && (memslot = @(slots)->memslots[i], true)
or even
memslot = &(slots)->memslots[i], i < (slots)->nmemslots
or just kill i and make memslot the loop variable.

Good, will fix it in the next version, thanks!

Xiao Guangrong

author

2011-11-18 09:19 UTC #10 lore raw

PATCH v2 4/6 KVM: introduce id_to_memslot function

In reply to Xiao Guangrong

Introduce id_to_memslot to get memslot by slot id

Signed-off-by Xiao Guangrong <[email protected]>

---
 arch/ia64/kvm/kvm-ia64.c  |    2 +-
 arch/powerpc/kvm/book3s.c |    2 +-
 arch/x86/kvm/vmx.c        |    6 ++++--
 arch/x86/kvm/x86.c        |    8 +++++---
 include/linux/kvm_host.h  |    6 ++++++
 virt/kvm/kvm_main.c       |   12 ++++++++----
 6 files changed, 25 insertions(+), 11 deletions(-)

arch/ia64/kvm/kvm-ia64.c +1 -1

index 7d5bc81..773a984 100644
@@ -1818,7 +1818,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 	if (log->slot >= KVM_MEMORY_SLOTS)
 		goto out;
 
-	memslot = &kvm->memslots->memslots[log->slot];
+	memslot = id_to_memslot(kvm->memslots, log->slot);
 	r = -ENOENT;
 	if (!memslot->dirty_bitmap)
 		goto out;

arch/powerpc/kvm/book3s.c +1 -1

index f68a34d..c1128d8 100644
@@ -497,7 +497,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 
 	/* If nothing is dirty, don't bother messing with page tables. */
 	if (is_dirty) {
-		memslot = &kvm->memslots->memslots[log->slot];
+		memslot = id_to_memslot(kvm->memslots, log->slot)
 
 		ga = memslot->base_gfn << PAGE_SHIFT;
 		ga_end = ga + (memslot->npages << PAGE_SHIFT);

arch/x86/kvm/vmx.c +4 -2

index 6e28d58..4a92073 100644
@@ -2716,11 +2716,13 @@ static gva_t rmode_tss_base(struct kvm *kvm)
 {
 	if (!kvm->arch.tss_addr) {
 		struct kvm_memslots *slots;
+		struct kvm_memory_slot *slot;
 		gfn_t base_gfn;
 
 		slots = kvm_memslots(kvm);
-		base_gfn = slots->memslots[0].base_gfn +
-				 kvm->memslots->memslots[0].npages - 3;
+		slot = id_to_memslot(slots, 0);
+		base_gfn = slot->base_gfn + slot->npages - 3;
+
 		return base_gfn << PAGE_SHIFT;
 	}
 	return kvm->arch.tss_addr;

arch/x86/kvm/x86.c +5 -3

index 56d1a39..315c2ca 100644
@@ -3478,7 +3478,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 	if (log->slot >= KVM_MEMORY_SLOTS)
 		goto out;
 
-	memslot = &kvm->memslots->memslots[log->slot];
+	memslot = id_to_memslot(kvm->memslots, log->slot);
 	r = -ENOENT;
 	if (!memslot->dirty_bitmap)
 		goto out;

@@ -3491,6 +3491,7 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 	/* If nothing is dirty, don't bother messing with page tables. */
 	if (is_dirty) {
 		struct kvm_memslots *slots, *old_slots;
+		struct kvm_memory_slot *slot;
 		unsigned long *dirty_bitmap;
 
 		dirty_bitmap = memslot->dirty_bitmap_head;

@@ -3503,13 +3504,14 @@ int kvm_vm_ioctl_get_dirty_log(struct kvm *kvm,
 		if (!slots)
 			goto out;
 		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-		slots->memslots[log->slot].dirty_bitmap = dirty_bitmap;
+		slot = id_to_memslot(slots, log->slot);
+		slot->dirty_bitmap = dirty_bitmap;
 		update_memslots(slots, NULL);
 
 		old_slots = kvm->memslots;
 		rcu_assign_pointer(kvm->memslots, slots);
 		synchronize_srcu_expedited(&kvm->srcu);
-		dirty_bitmap = old_slots->memslots[log->slot].dirty_bitmap;
+		dirty_bitmap = memslot->dirty_bitmap;
 		kfree(old_slots);
 
 		spin_lock(&kvm->mmu_lock);

include/linux/kvm_host.h +6 -0

index 10524c0..a0e4d63 100644
@@ -332,6 +332,12 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 			|| lockdep_is_held(&kvm->slots_lock));
 }
 
+static inline struct kvm_memory_slot *
+id_to_memslot(struct kvm_memslots *slots, int id)
+{
+	return &slots->memslots[id];
+}
+
 #define HPA_MSB ((sizeof(hpa_t) * 8) - 1)
 #define HPA_ERR_MASK ((hpa_t)1 << HPA_MSB)
 static inline int is_error_hpa(hpa_t hpa) { return hpa >> HPA_MSB; }

virt/kvm/kvm_main.c +8 -4

index ec3b03b..09bb794 100644
@@ -634,8 +634,9 @@ void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *new)
 {
 	if (new) {
 		int id = new->id;
+		struct kvm_memory_slot *old = id_to_memslot(slots, id);
 
-		slots->memslots[id] = *new;
+		*old = *new;
 		if (id >= slots->nmemslots)
 			slots->nmemslots = id + 1;
 	}

@@ -681,7 +682,7 @@ int __kvm_set_memory_region(struct kvm *kvm,
 	if (mem->guest_phys_addr + mem->memory_size < mem->guest_phys_addr)
 		goto out;
 
-	memslot = &kvm->memslots->memslots[mem->slot];
+	memslot = id_to_memslot(kvm->memslots, mem->slot);
 	base_gfn = mem->guest_phys_addr >> PAGE_SHIFT;
 	npages = mem->memory_size >> PAGE_SHIFT;

@@ -788,12 +789,15 @@ skip_lpage:
 #endif /* not defined CONFIG_S390 */
 
 	if (!npages) {
+		struct kvm_memory_slot *slot;
+
 		r = -ENOMEM;
 		slots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
 		if (!slots)
 			goto out_free;
 		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-		slots->memslots[mem->slot].flags |= KVM_MEMSLOT_INVALID;
+		slot = id_to_memslot(slots, mem->slot);
+		slot->flags |= KVM_MEMSLOT_INVALID;
 		update_memslots(slots, NULL);
 
 		old_memslots = kvm->memslots;

@@ -897,7 +901,7 @@ int kvm_get_dirty_log(struct kvm *kvm,
 	if (log->slot >= KVM_MEMORY_SLOTS)
 		goto out;
 
-	memslot = &kvm->memslots->memslots[log->slot];
+	memslot = id_to_memslot(kvm->memslots, log->slot);
 	r = -ENOENT;
 	if (!memslot->dirty_bitmap)
 		goto out;

Signature · 1 line

1.7.7.1

Xiao Guangrong

author

2011-11-18 09:19 UTC #11 lore raw

PATCH v2 5/6 KVM: sort memslots by its size and use line search

In reply to Xiao Guangrong

Sort memslots base on its size and use line search to find it, so the larger memslots have better fit

The idea is from Avi

Signed-off-by Xiao Guangrong <[email protected]>

---
 include/linux/kvm_host.h |   22 +++++++++---
 virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
 2 files changed, 75 insertions(+), 29 deletions(-)

include/linux/kvm_host.h +17 -5

index a0e4d63..83b396a 100644
@@ -230,8 +230,12 @@ struct kvm_irq_routing_table {};
 #define KVM_MEM_SLOTS_NUM (KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
 #endif
 
+/*
+ * Note:
+ * memslots are not sorted by id anymore, please use id_to_memslot()
+ * to get the memslot by its id.
+ */
 struct kvm_memslots {
-	int nmemslots;
 	u64 generation;
 	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
 };

@@ -307,9 +311,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)
 
-#define kvm_for_each_memslot(slots, memslot, i)	\
-	for (i = 0; i < (slots)->nmemslots &&	\
-	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+#define kvm_for_each_memslot(slots, memslot, i)			\
+	for (i = 0; i < KVM_MEM_SLOTS_NUM &&			\
+	      ({ memslot = &(slots)->memslots[i]; 1; }) &&	\
+	      memslot->npages != 0; i++)
 
 int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id);
 void kvm_vcpu_uninit(struct kvm_vcpu *vcpu);

@@ -335,7 +340,14 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	return &slots->memslots[id];
+	int i;
+
+	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
+		if (slots->memslots[i].id == id)
+			return &slots->memslots[i];
+
+	WARN_ON(1);
+	return NULL;
 }
 
 #define HPA_MSB ((sizeof(hpa_t) * 8) - 1)

virt/kvm/kvm_main.c +58 ~~-24~~

121 lines not on this page · raw message

Signature · 1 line

1.7.7.1

Avi Kivity

2011-11-20 11:26 UTC #12 lore raw

Re: [PATCH v2 5/6] KVM: sort memslots by its size and use line search

Quoted 30 lines · Xiao Guangrong

Sort memslots base on its size and use line search to find it, so the larger memslots have better fit

The idea is from Avi

Signed-off-by Xiao Guangrong <[email protected]>

---
 include/linux/kvm_host.h |   22 +++++++++---
 virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
 2 files changed, 75 insertions(+), 29 deletions(-)

include/linux/kvm_host.h +5 -1

index a0e4d63..83b396a 100644
@@ -230,8 +230,12 @@ struct kvm_irq_routing_table {};
 #define KVM_MEM_SLOTS_NUM (KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
 #endif
 
+/*
+ * Note:
+ * memslots are not sorted by id anymore, please use id_to_memslot()
+ * to get the memslot by its id.
+ */
 struct kvm_memslots {
-	int nmemslots;
 	u64 generation;
 	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
 };

include/linux/kvm_host.h static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i) · line 317

Quoted 10 lines

include/linux/kvm_host.h +4 -3

@@ -307,9 +311,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)
 
-#define kvm_for_each_memslot(slots, memslot, i)	\
-	for (i = 0; i < (slots)->nmemslots &&	\
-	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+#define kvm_for_each_memslot(slots, memslot, i)			\
+	for (i = 0; i < KVM_MEM_SLOTS_NUM &&			\
+	      ({ memslot = &(slots)->memslots[i]; 1; }) &&	\
+	      memslot->npages != 0; i++)

You might allocate an always-empty memslot at the end and simplify the termination condition.

Quoted 4 lines

include/linux/kvm_host.h +0 -0

 int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id);
 void kvm_vcpu_uninit(struct kvm_vcpu *vcpu);

include/linux/kvm_host.h static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm) · line 348

Quoted 10 lines

include/linux/kvm_host.h +6 -1

@@ -335,7 +340,14 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	return &slots->memslots[id];
+	int i;
+
+	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
+		if (slots->memslots[i].id == id)
+			return &slots->memslots[i];
+

Is that in any hot path? we could make an array for doing this translation.

Alex wants to increase the memslot count, so this could be a long loop.

Signature · 1 line

error compiling committee.c: too many arguments to function

Avi Kivity

2011-11-20 11:27 UTC #13 lore raw

Re: [PATCH v2 5/6] KVM: sort memslots by its size and use line search

Quoted 16 lines · Avi Kivity

Quoted 4 lines
int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id); void kvm_vcpu_uninit(struct kvm_vcpu *vcpu);
include/linux/kvm_host.h static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm) · line 348
Quoted 10 lines
include/linux/kvm_host.h +6 -1
@@ -335,7 +340,14 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	return &slots->memslots[id];
+	int i;
+
+	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
+		if (slots->memslots[i].id == id)
+			return &slots->memslots[i];
+
Is that in any hot path? we could make an array for doing this translation.

Never mind, I see patch 6. I should have known you wouldn't leave it like that.

Signature · 1 line

error compiling committee.c: too many arguments to function

Xiao Guangrong

author

2011-11-21 03:48 UTC #14 lore raw

Re: [PATCH v2 5/6] KVM: sort memslots by its size and use line search

In reply to Avi Kivity

Quoted 34 lines · Avi Kivity

Quoted 33 lines · Xiao Guangrong

Sort memslots base on its size and use line search to find it, so the larger memslots have better fit

The idea is from Avi

Signed-off-by Xiao Guangrong <[email protected]>

---
 include/linux/kvm_host.h |   22 +++++++++---
 virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
 2 files changed, 75 insertions(+), 29 deletions(-)

include/linux/kvm_host.h +5 -1

index a0e4d63..83b396a 100644
@@ -230,8 +230,12 @@ struct kvm_irq_routing_table {};
 #define KVM_MEM_SLOTS_NUM (KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS)
 #endif
 
+/*
+ * Note:
+ * memslots are not sorted by id anymore, please use id_to_memslot()
+ * to get the memslot by its id.
+ */
 struct kvm_memslots {
-	int nmemslots;
 	u64 generation;
 	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
 };

@@ -307,9 +311,10 @@ static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i)
 	     (vcpup = kvm_get_vcpu(kvm, idx)) != NULL; \
 	     idx++)

Quoted 11 lines

include/linux/kvm_host.h static inline struct kvm_vcpu *kvm_get_vcpu(struct kvm *kvm, int i) · line 317
Quoted 7 lines
include/linux/kvm_host.h +4 -3
-#define kvm_for_each_memslot(slots, memslot, i)	\
-	for (i = 0; i < (slots)->nmemslots &&	\
-	      ({ memslot = &(slots)->memslots[i]; 1; }); i++)
+#define kvm_for_each_memslot(slots, memslot, i)			\
+	for (i = 0; i < KVM_MEM_SLOTS_NUM &&			\
+	      ({ memslot = &(slots)->memslots[i]; 1; }) &&	\
+	      memslot->npages != 0; i++)
You might allocate an always-empty memslot at the end and simplify the termination condition.

The slots are sorted by its size, all empty slots are at the end of the array, so we can simplify break the loop if meet a empty slot.

Xiao Guangrong

author

2011-11-18 09:20 UTC #15 lore raw

PATCH v2 6/6 KVM: introduce a table to map slot id to index in memslots arry

In reply to Xiao Guangrong

The operation of getting dirty log is frequency When framebuffer-based displays are used(for example, Xwindow), so, we introduce a mapping table to speed up id_to_memslot()

Signed-off-by Xiao Guangrong <[email protected]>

---
 include/linux/kvm_host.h |   13 +++++++------
 virt/kvm/kvm_main.c      |    7 ++++++-
 2 files changed, 13 insertions(+), 7 deletions(-)

include/linux/kvm_host.h +7 -6

index 83b396a..fbf66eb 100644
@@ -238,6 +238,8 @@ struct kvm_irq_routing_table {};
 struct kvm_memslots {
 	u64 generation;
 	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
+	/* The mapping table from slot id to the index in memslots[]. */
+	int id_to_index[KVM_MEM_SLOTS_NUM];
 };
 
 struct kvm {

@@ -340,14 +342,13 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	int i;
+	int index = slots->id_to_index[id];
+	struct kvm_memory_slot *slot;
 
-	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
-		if (slots->memslots[i].id == id)
-			return &slots->memslots[i];
+	slot = &slots->memslots[index];
 
-	WARN_ON(1);
-	return NULL;
+	WARN_ON(slot->id != id);
+	return slot;
 }
 
 #define HPA_MSB ((sizeof(hpa_t) * 8) - 1)

virt/kvm/kvm_main.c +6 -1

index 9425e3a..0dad825 100644
@@ -446,7 +446,7 @@ static void kvm_init_memslots_id(struct kvm *kvm)
 	struct kvm_memslots *slots = kvm->memslots;
 
 	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
-		slots->memslots[i].id = i;
+		slots->id_to_index[i] = slots->memslots[i].id = i;
 }
 
 static struct kvm *kvm_create_vm(void)

@@ -675,8 +675,13 @@ static int cmp_memslot(const void *slot1, const void *slot2)
  */
 static void sort_memslots(struct kvm_memslots *slots)
 {
+	int i;
+
 	sort(slots->memslots, KVM_MEM_SLOTS_NUM,
 	      sizeof(struct kvm_memory_slot), cmp_memslot, NULL);
+
+	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
+		slots->id_to_index[slots->memslots[i].id] = i;
 }
 
 void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *new)

Signature · 1 line

1.7.7.1

Sasha Levin

2011-11-18 09:45 UTC #16 lore raw

Re: [PATCH v2 6/6] KVM: introduce a table to map slot id to index in memslots arry

Quoted 31 lines · Xiao Guangrong

The operation of getting dirty log is frequency When framebuffer-based displays are used(for example, Xwindow), so, we introduce a mapping table to speed up id_to_memslot()

Signed-off-by Xiao Guangrong <[email protected]>

---
 include/linux/kvm_host.h |   13 +++++++------
 virt/kvm/kvm_main.c      |    7 ++++++-
 2 files changed, 13 insertions(+), 7 deletions(-)

include/linux/kvm_host.h +4 -1

index 83b396a..fbf66eb 100644
@@ -238,6 +238,8 @@ struct kvm_irq_routing_table {};
 struct kvm_memslots {
 	u64 generation;
 	struct kvm_memory_slot memslots[KVM_MEM_SLOTS_NUM];
+	/* The mapping table from slot id to the index in memslots[]. */
+	int id_to_index[KVM_MEM_SLOTS_NUM];
 };
 
 struct kvm {

@@ -340,14 +342,13 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	int i;
+	int index = slots->id_to_index[id];
+	struct kvm_memory_slot *slot;

include/linux/kvm_host.h static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm) · line 352

Quoted 10 lines

include/linux/kvm_host.h +3 -5

-	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
-		if (slots->memslots[i].id == id)
-			return &slots->memslots[i];
+	slot = &slots->memslots[index];
 
-	WARN_ON(1);
-	return NULL;
+	WARN_ON(slot->id != id);
+	return slot;
 }

If we didn't find the right memslot we shouldn't be returning a wrong one, we should be failing.

Signature · 1 line

Sasha.

Xiao Guangrong

author

2011-11-18 10:03 UTC #17 lore raw

Re: [PATCH v2 6/6] KVM: introduce a table to map slot id to index in memslots arry

Quoted 14 lines · Sasha Levin

Quoted 14 lines

struct kvm {

include/linux/kvm_host.h +3 -4

@@ -340,14 +342,13 @@ static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm)
 static inline struct kvm_memory_slot *
 id_to_memslot(struct kvm_memslots *slots, int id)
 {
-	int i;
+	int index = slots->id_to_index[id];
+	struct kvm_memory_slot *slot;
 
-	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
-		if (slots->memslots[i].id == id)
-			return &slots->memslots[i];
+	slot = &slots->memslots[index];

Quoted 9 lines

include/linux/kvm_host.h static inline struct kvm_memslots *kvm_memslots(struct kvm *kvm) · line 352
Quoted 5 lines
include/linux/kvm_host.h +2 -2
-	WARN_ON(1);
-	return NULL;
+	WARN_ON(slot->id != id);
+	return slot;
 }
If we didn't find the right memslot we shouldn't be returning a wrong one, we should be failing.

Um, in the current code, the "id" has already been checked by the caller, that means "id" should be < KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS, so, if we can not find the memslot for this slot, it must be a bug.

Sasha Levin

2011-11-18 09:41 UTC #18 lore raw

In reply to Xiao Guangrong

Quoted 13 lines · Xiao Guangrong

This is the more work base on my v1 patchset which is posted some months ago, it can be found at:
https://lkml.org/lkml/2011/2/22/68
Change log:
- sort memslots base on its size and do the line search instead of binary search base on gfn, it is from Avi's idea.
- in order to reduce cache footprint, memslots are sorted in the array of kvm->memslots->memslots[] and introduce a table to map slot id to index in the array
There is the performance result:

Quoted 7 lines

autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8
kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66

Hi,

Do these patches depend on any other patches? Looks like they don't apply on kvm-next.

Signature · 1 line

Sasha.

Xiao Guangrong

author

2011-11-18 09:56 UTC #19 lore raw

Quoted 4 lines · Sasha Levin

Quoted 4 lines
autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8

Quoted 9 lines

Quoted 3 lines
kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66
Hi,
Do these patches depend on any other patches? Looks like they don't apply on kvm-next.

Ah, i forgot that i was using Avi's kvm tree, this patchset is just base on that, to avoid noise, i'll rebase it after it is reviewed.

Thank you, Sasha!

Avi Kivity

2011-11-20 11:29 UTC #20 lore raw

In reply to Xiao Guangrong

Quoted 13 lines · Xiao Guangrong

This is the more work base on my v1 patchset which is posted some months ago, it can be found at:
https://lkml.org/lkml/2011/2/22/68
Change log:
- sort memslots base on its size and do the line search instead of binary search base on gfn, it is from Avi's idea.
- in order to reduce cache footprint, memslots are sorted in the array of kvm->memslots->memslots[] and introduce a table to map slot id to index in the array
There is the performance result:

Quoted 7 lines

autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8
kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66

Looks good, had a couple of comments but they're really minor.

Signature · 1 line

error compiling committee.c: too many arguments to function

Avi Kivity

2011-11-20 12:12 UTC #21 lore raw

Quoted 18 lines · Avi Kivity

Quoted 17 lines · Xiao Guangrong
This is the more work base on my v1 patchset which is posted some months ago, it can be found at:
https://lkml.org/lkml/2011/2/22/68
Change log:
- sort memslots base on its size and do the line search instead of binary search base on gfn, it is from Avi's idea.
- in order to reduce cache footprint, memslots are sorted in the array of kvm->memslots->memslots[] and introduce a table to map slot id to index in the array
There is the performance result:
autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8

Quoted 6 lines

Quoted 3 lines
kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66
Looks good, had a couple of comments but they're really minor.

btw, this patchset touches a lot of common code. Did you crossbuild for other kvm archs?

Signature · 1 line

error compiling committee.c: too many arguments to function

Xiao Guangrong

author

2011-11-21 03:54 UTC #22 lore raw

Quoted 23 lines · Avi Kivity

Quoted 22 lines · Avi Kivity
Quoted 20 lines · Xiao Guangrong
This is the more work base on my v1 patchset which is posted some months ago, it can be found at:
https://lkml.org/lkml/2011/2/22/68
Change log:
- sort memslots base on its size and do the line search instead of binary search base on gfn, it is from Avi's idea.
- in order to reduce cache footprint, memslots are sorted in the array of kvm->memslots->memslots[] and introduce a table to map slot id to index in the array
There is the performance result:
autotest for RHEL.6.1 setup/boot/reboot/shutdown(average):
ept=1: before: 449.5 after: 447.8
ept=0: before: 532.7 after: 529.8
kernbench(average):
ept=1: before: 127.94 after: 126.98
ept=0: before: 196.85 after: 189.66

Quoted 6 lines

Quoted 2 lines
Looks good, had a couple of comments but they're really minor.
btw, this patchset touches a lot of common code. Did you crossbuild for other kvm archs?

No :-), but i will build cross compilation environment and test it next time, thanks!