[PATCH v2 0/6] KVM: optimize memslots searching

[PATCH v2 0/6] KVM: optimize memslots searching

[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

[PATCH v2 1/6] KVM: introduce KVM_MEM_SLOTS_NUM macro

[Xiao Guangrong]

Introduce KVM_MEM_SLOTS_NUM macro to instead of
KVM_MEMORY_SLOTS + KVM_PRIVATE_MEM_SLOTS

Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
---
 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(-)

diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index 6d83264..b80a310 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -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;
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index a9b3a32..e6c2755 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -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);
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index c6a2ec9..a42d50b 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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 {
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index d9cfb78..eb55a11 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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;
-- 
1.7.7.1

[PATCH v2 2/6] KVM: introduce update_memslots function

[Xiao Guangrong]

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

Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
---
 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(-)

diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 9eff4af..56d1a39 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -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);
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index a42d50b..bb8728e 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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)
 {
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index eb55a11..0fb3aeb 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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);
-- 
1.7.7.1

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

[Xiao Guangrong]

Introduce kvm_for_each_memslot to walk all valid memslot

Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
---
 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(-)

diff --git a/arch/ia64/kvm/kvm-ia64.c b/arch/ia64/kvm/kvm-ia64.c
index 43f4c92..7d5bc81 100644
--- a/arch/ia64/kvm/kvm-ia64.c
+++ b/arch/ia64/kvm/kvm-ia64.c
@@ -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]);
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index e6c2755..53dbae0 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -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,
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index bb8728e..10524c0 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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);

diff --git a/virt/kvm/iommu.c b/virt/kvm/iommu.c
index d5f3b8d..02df243 100644
--- a/virt/kvm/iommu.c
+++ b/virt/kvm/iommu.c
@@ -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;
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 0fb3aeb..ec3b03b 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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);
 }
-- 
1.7.7.1

[PATCH v2 4/6] KVM: introduce id_to_memslot function

[Xiao Guangrong]

Introduce id_to_memslot to get memslot by slot id

Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
---
 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(-)

diff --git a/arch/ia64/kvm/kvm-ia64.c b/arch/ia64/kvm/kvm-ia64.c
index 7d5bc81..773a984 100644
--- a/arch/ia64/kvm/kvm-ia64.c
+++ b/arch/ia64/kvm/kvm-ia64.c
@@ -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;
diff --git a/arch/powerpc/kvm/book3s.c b/arch/powerpc/kvm/book3s.c
index f68a34d..c1128d8 100644
--- a/arch/powerpc/kvm/book3s.c
+++ b/arch/powerpc/kvm/book3s.c
@@ -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);
diff --git a/arch/x86/kvm/vmx.c b/arch/x86/kvm/vmx.c
index 6e28d58..4a92073 100644
--- a/arch/x86/kvm/vmx.c
+++ b/arch/x86/kvm/vmx.c
@@ -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;
diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 56d1a39..315c2ca 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -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);
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 10524c0..a0e4d63 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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; }
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index ec3b03b..09bb794 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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;
-- 
1.7.7.1

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

[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 <xiaoguangrong@linux.vnet.ibm.com>
---
 include/linux/kvm_host.h |   22 +++++++++---
 virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
 2 files changed, 75 insertions(+), 29 deletions(-)

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index a0e4d63..83b396a 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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)
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 09bb794..9425e3a 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -440,6 +440,15 @@ static int kvm_init_mmu_notifier(struct kvm *kvm)

 #endif /* CONFIG_MMU_NOTIFIER && KVM_ARCH_WANT_MMU_NOTIFIER */

+static void kvm_init_memslots_id(struct kvm *kvm)
+{
+	int i;
+	struct kvm_memslots *slots = kvm->memslots;
+
+	for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
+		slots->memslots[i].id = i;
+}
+
 static struct kvm *kvm_create_vm(void)
 {
 	int r, i;
@@ -465,6 +474,7 @@ static struct kvm *kvm_create_vm(void)
 	kvm->memslots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
 	if (!kvm->memslots)
 		goto out_err_nosrcu;
+	kvm_init_memslots_id(kvm);
 	if (init_srcu_struct(&kvm->srcu))
 		goto out_err_nosrcu;
 	for (i = 0; i < KVM_NR_BUSES; i++) {
@@ -630,15 +640,55 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
 }
 #endif /* !CONFIG_S390 */

+static struct kvm_memory_slot *
+search_memslots(struct kvm_memslots *slots, gfn_t gfn)
+{
+	int i;
+	struct kvm_memory_slot *memslot;
+
+	kvm_for_each_memslot(slots, memslot, i)
+		if (gfn >= memslot->base_gfn &&
+		      gfn < memslot->base_gfn + memslot->npages)
+			return memslot;
+
+	return NULL;
+}
+
+static int cmp_memslot(const void *slot1, const void *slot2)
+{
+	struct kvm_memory_slot *s1, *s2;
+
+	s1 = (struct kvm_memory_slot *)slot1;
+	s2 = (struct kvm_memory_slot *)slot2;
+
+	if (s1->npages < s2->npages)
+		return 1;
+	if (s1->npages > s2->npages)
+		return -1;
+
+	return 0;
+}
+
+/*
+ * Sort the memslots base on its size, so the larger slots
+ * will get better fit.
+ */
+static void sort_memslots(struct kvm_memslots *slots)
+{
+	sort(slots->memslots, KVM_MEM_SLOTS_NUM,
+	      sizeof(struct kvm_memory_slot), cmp_memslot, NULL);
+}
+
 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);
+		unsigned long npages = old->npages;

 		*old = *new;
-		if (id >= slots->nmemslots)
-			slots->nmemslots = id + 1;
+		if (new->npages != npages)
+			sort_memslots(slots);
 	}

 	slots->generation++;
@@ -979,16 +1029,7 @@ EXPORT_SYMBOL_GPL(kvm_is_error_hva);
 static struct kvm_memory_slot *__gfn_to_memslot(struct kvm_memslots *slots,
 						gfn_t gfn)
 {
-	int i;
-
-	for (i = 0; i < slots->nmemslots; ++i) {
-		struct kvm_memory_slot *memslot = &slots->memslots[i];
-
-		if (gfn >= memslot->base_gfn
-		    && gfn < memslot->base_gfn + memslot->npages)
-			return memslot;
-	}
-	return NULL;
+	return search_memslots(slots, gfn);
 }

 struct kvm_memory_slot *gfn_to_memslot(struct kvm *kvm, gfn_t gfn)
@@ -999,20 +1040,13 @@ EXPORT_SYMBOL_GPL(gfn_to_memslot);

 int kvm_is_visible_gfn(struct kvm *kvm, gfn_t gfn)
 {
-	int i;
-	struct kvm_memslots *slots = kvm_memslots(kvm);
+	struct kvm_memory_slot *memslot = gfn_to_memslot(kvm, gfn);

-	for (i = 0; i < KVM_MEMORY_SLOTS; ++i) {
-		struct kvm_memory_slot *memslot = &slots->memslots[i];
-
-		if (memslot->flags & KVM_MEMSLOT_INVALID)
-			continue;
+	if (!memslot || memslot->id >= KVM_MEMORY_SLOTS ||
+	      memslot->flags & KVM_MEMSLOT_INVALID)
+		return 0;

-		if (gfn >= memslot->base_gfn
-		    && gfn < memslot->base_gfn + memslot->npages)
-			return 1;
-	}
-	return 0;
+	return 1;
 }
 EXPORT_SYMBOL_GPL(kvm_is_visible_gfn);

-- 
1.7.7.1

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

[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 <xiaoguangrong@linux.vnet.ibm.com>
---
 include/linux/kvm_host.h |   13 +++++++------
 virt/kvm/kvm_main.c      |    7 ++++++-
 2 files changed, 13 insertions(+), 7 deletions(-)

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 83b396a..fbf66eb 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -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)
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 9425e3a..0dad825 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -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)
-- 
1.7.7.1

Re: [PATCH v2 0/6] KVM: optimize memslots searching

[Sasha Levin]

On Fri, 2011-11-18 at 17:16 +0800, Xiao Guangrong wrote:
> 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

Hi,

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

-- 

Sasha.

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

[Sasha Levin]

On Fri, 2011-11-18 at 17:20 +0800, Xiao Guangrong wrote:
> 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 <xiaoguangrong@linux.vnet.ibm.com>
> ---
>  include/linux/kvm_host.h |   13 +++++++------
>  virt/kvm/kvm_main.c      |    7 ++++++-
>  2 files changed, 13 insertions(+), 7 deletions(-)
> 
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index 83b396a..fbf66eb 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -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;
>  }

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

-- 

Sasha.

Re: [PATCH v2 0/6] KVM: optimize memslots searching

[Xiao Guangrong]

On 11/18/2011 05:41 PM, Sasha Levin wrote:


>> 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.
> 


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!

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

[Xiao Guangrong]

On 11/18/2011 05:45 PM, Sasha Levin wrote:


>>  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;
>>  }
> 
> 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.

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

[Avi Kivity]

On 11/18/2011 11:18 AM, Xiao Guangrong wrote:
> index bb8728e..10524c0 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -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.

-- 
error compiling committee.c: too many arguments to function

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

[Avi Kivity]

On 11/18/2011 11:19 AM, Xiao Guangrong wrote:
> 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 <xiaoguangrong@linux.vnet.ibm.com>
> ---
>  include/linux/kvm_host.h |   22 +++++++++---
>  virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
>  2 files changed, 75 insertions(+), 29 deletions(-)
>
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index a0e4d63..83b396a 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -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++)

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

>
>  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];
> +

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.


-- 
error compiling committee.c: too many arguments to function

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

[Avi Kivity]

On 11/20/2011 01:26 PM, Avi Kivity wrote:
> >
> >  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];
> > +
>
> 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.

-- 
error compiling committee.c: too many arguments to function

Re: [PATCH v2 0/6] KVM: optimize memslots searching

[Avi Kivity]

On 11/18/2011 11:16 AM, Xiao Guangrong wrote:
> 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

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

-- 
error compiling committee.c: too many arguments to function

Re: [PATCH v2 0/6] KVM: optimize memslots searching

[Avi Kivity]

On 11/20/2011 01:29 PM, Avi Kivity wrote:
> On 11/18/2011 11:16 AM, Xiao Guangrong wrote:
> > 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
>
> 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?

-- 
error compiling committee.c: too many arguments to function

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

[Takuya Yoshikawa]

(2011/11/20 20:21), Avi Kivity wrote:
> On 11/18/2011 11:18 AM, Xiao Guangrong wrote:
>> index bb8728e..10524c0 100644
>> --- a/include/linux/kvm_host.h
>> +++ b/include/linux/kvm_host.h
>> @@ -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.
>

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

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

[Xiao Guangrong]

On 11/20/2011 07:21 PM, Avi Kivity wrote:

> On 11/18/2011 11:18 AM, Xiao Guangrong wrote:
>> index bb8728e..10524c0 100644
>> --- a/include/linux/kvm_host.h
>> +++ b/include/linux/kvm_host.h
>> @@ -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.
> 


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

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

[Xiao Guangrong]

On 11/20/2011 07:26 PM, Avi Kivity wrote:

> On 11/18/2011 11:19 AM, Xiao Guangrong wrote:
>> 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 <xiaoguangrong@linux.vnet.ibm.com>
>> ---
>>  include/linux/kvm_host.h |   22 +++++++++---
>>  virt/kvm/kvm_main.c      |   82 ++++++++++++++++++++++++++++++++-------------
>>  2 files changed, 75 insertions(+), 29 deletions(-)
>>
>> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
>> index a0e4d63..83b396a 100644
>> --- a/include/linux/kvm_host.h
>> +++ b/include/linux/kvm_host.h
>> @@ -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++)
> 
> 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.

Re: [PATCH v2 0/6] KVM: optimize memslots searching

[Xiao Guangrong]

On 11/20/2011 08:12 PM, Avi Kivity wrote:

> On 11/20/2011 01:29 PM, Avi Kivity wrote:
>> On 11/18/2011 11:16 AM, Xiao Guangrong wrote:
>>> 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
>>
>> 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!

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

[Avi Kivity]

On 11/21/2011 02:54 AM, Takuya Yoshikawa wrote:
> (2011/11/20 20:21), Avi Kivity wrote:
>> On 11/18/2011 11:18 AM, Xiao Guangrong wrote:
>>> index bb8728e..10524c0 100644
>>> --- a/include/linux/kvm_host.h
>>> +++ b/include/linux/kvm_host.h
>>> @@ -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.
>>
>
> 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.


-- 
error compiling committee.c: too many arguments to function

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

[Takuya Yoshikawa]

(2011/11/21 17:34), Avi Kivity wrote:
>> 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.
>

Yes.

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

Thanks,
	Takuya

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

[Xiao Guangrong]

On 11/21/2011 04:40 PM, Takuya Yoshikawa wrote:

> (2011/11/21 17:34), Avi Kivity wrote:
>>> 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.
>>
> 
> Yes.
> 
> Xiao, please change the order if you have no problem.
> 


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