KVM: optimize memslots searching and cache GPN to GFN

Sort memslots then search the slot with binary search to speed up the slot searching

Quoted 3 lines · Xiao Guangrong

Sort memslots then search the slot with binary search to speed up the slot searching

I'm not sure if a binary search is the right algorithm here. It introduces a lot of branches which may be mispredicted.

Options we've discussed are:

- Sort slots by size, use linear search (so the largest slots are found quickly)
- Weighted balanced tree
http://en.wikipedia.org/wiki/Weight-balanced_tree, use weight == slot size

Both options still make the miss case (mmio) slow. We could cache the result of a miss in an spte by using a reserved bit, and checking the page fault error code (or seeing if we get an ept violation or ept misconfiguration), so if we get repeated mmio on a page, we don't need to search the slot list/tree.

Signed-off-by Alex Williamson<[email protected]>

---

  include/linux/wbtree.h |   55 ++++++++++++++++
  lib/Makefile           |    3 +
  lib/wbtree.c           |  170 ++++++++++++++++++++++++++++++++++++++++++++++++
  3 files changed, 227 insertions(+), 1 deletions(-)

create mode 100644 include/linux/wbtree.h
create mode 100644 lib/wbtree.c

include/linux/wbtree.h new file +55 -0

new file mode 100644
index 0000000..ef70f6f
@@ -0,0 +1,55 @@
+/*
+ * Weight-balanced binary tree
+ *
+ * The balance of this tree is based on search probability.  The
+ * heaviest weighted nodes (the ones we're most likely to hit), are
+ * at the top of each subtree.
+ *
+ * Copywrite (C) 2011 Red Hat, Inc.
+ *
+ * Authors:
+ *   Alex Williamson<[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+#ifndef _LINUX_WBTREE_H
+#define _LINUX_WBTREE_H
+
+#include<linux/kernel.h>
+#include<linux/stddef.h>
+
+struct wb_node {
+	struct wb_node *wb_parent;
+	struct wb_node *wb_left;
+	struct wb_node *wb_right;
+	unsigned long wb_weight;
+};
+
+struct wb_root {
+	struct wb_node *wb_node;
+};
+
+#define WB_ROOT (struct wb_root) { NULL, }
+#define wb_entry(ptr, type, member) container_of(ptr, type, member)
+
+extern void wb_rebalance(struct wb_node *node, struct wb_root *root);
+extern void wb_erase(struct wb_node *node, struct wb_root *root);
+extern struct wb_node *wb_first(struct wb_root *root);
+extern struct wb_node *wb_last(struct wb_root *root);
+extern struct wb_node *wb_next(struct wb_node *node);
+extern struct wb_node *wb_prev(struct wb_node *node);
+
+static inline void wb_set_weight(struct wb_node *node, unsigned long weight)
+{
+	node->wb_weight = weight;
+}
+
+static inline void wb_link_node(struct wb_node *node, struct wb_node *parent,
+				struct wb_node **wb_link)
+{
+	node->wb_left = node->wb_right = NULL;
+	node->wb_parent = parent;
+	*wb_link = node;
+}
+#endif /* _LINUX_WBTREE_H */

lib/Makefile +0 -0

index cbb774f..5c42e63 100644

lib/Makefile +0 -0

  ifeq ($(CONFIG_DEBUG_KOBJECT),y)
  CFLAGS_kobject.o += -DDEBUG

lib/wbtree.c new file +170 -0

new file mode 100644
index 0000000..54c3817
@@ -0,0 +1,170 @@
+/*
+ * Weight-balanced binary tree
+ *
+ * The balance of this tree is based on search probability.  The
+ * heaviest weighted nodes (the ones we're most likely to hit), are
+ * at the top of each subtree.
+ *
+ * Copywrite (C) 2011 Red Hat, Inc.
+ *
+ * Authors:
+ *   Alex Williamson<[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+#include<linux/wbtree.h>
+#include<linux/module.h>
+
+static void __wb_rotate_left(struct wb_node *node, struct wb_root *root)
+{
+	struct wb_node *right = node->wb_right;
+	struct wb_node *parent = node->wb_parent;
+
+	if ((node->wb_right = right->wb_left))
+		right->wb_left->wb_parent = node;
+	right->wb_left = node;
+
+	right->wb_parent = parent;
+
+	if (parent) {
+		if (node == parent->wb_left)
+			parent->wb_left = right;
+		else
+			parent->wb_right = right;
+	} else
+		root->wb_node = right;
+
+	node->wb_parent = right;
+}
+
+static void __wb_rotate_right(struct wb_node *node, struct wb_root *root)
+{
+	struct wb_node *left = node->wb_left;
+	struct wb_node *parent = node->wb_parent;
+
+	if ((node->wb_left = left->wb_right))
+		left->wb_right->wb_parent = node;
+	left->wb_right = node;
+
+	left->wb_parent = parent;
+
+	if (parent) {
+		if (node == parent->wb_right)
+			parent->wb_right = left;
+		else
+			parent->wb_left = left;
+	} else
+		root->wb_node = left;
+
+	node->wb_parent = left;
+}
+
+void wb_rebalance(struct wb_node *node, struct wb_root *root)
+{
+	while (node->wb_parent&&  node->wb_parent->wb_weight<  node->wb_weight) {
+		if (node == node->wb_parent->wb_left)
+			__wb_rotate_right(node->wb_parent, root);
+		else
+			__wb_rotate_left(node->wb_parent, root);
+	}
+}
+EXPORT_SYMBOL(wb_rebalance);
+
+void wb_erase(struct wb_node *node, struct wb_root *root)
+{
+	while (node->wb_left || node->wb_right) {
+		if (!node->wb_left)
+			__wb_rotate_left(node, root);
+		else if (!node->wb_right)
+			__wb_rotate_right(node, root);
+		else {
+			if (node->wb_left->wb_weight>
+			    node->wb_right->wb_weight)
+				__wb_rotate_right(node, root);
+			else
+				__wb_rotate_left(node, root);
+		}
+	}
+
+	if (node->wb_parent) {
+		if (node->wb_parent->wb_left == node)
+			node->wb_parent->wb_left = NULL;
+		else
+			node->wb_parent->wb_right = NULL;
+	} else
+		root->wb_node = NULL;
+}
+EXPORT_SYMBOL(wb_erase);
+
+struct wb_node *wb_first(struct wb_root *root)
+{
+	struct wb_node *node;
+
+	node = root->wb_node;
+	if (!node)
+		return NULL;
+
+	while (node->wb_left)
+		node = node->wb_left;
+
+	return node;
+}
+EXPORT_SYMBOL(wb_first);
+
+struct wb_node *wb_last(struct wb_root *root)
+{
+	struct wb_node *node;
+
+	node = root->wb_node;
+	if (!node)
+		return NULL;
+
+	while (node->wb_right)
+		node = node->wb_right;
+
+	return node;
+}
+EXPORT_SYMBOL(wb_last);
+
+struct wb_node *wb_next(struct wb_node *node)
+{
+	struct wb_node *parent;
+
+	if (node->wb_parent == node)
+		return NULL;
+
+	if (node->wb_right) {
+		node = node->wb_right;
+		while (node->wb_left)
+			node = node->wb_left;
+		return node;
+	}
+
+	while ((parent = node->wb_parent)&&  node == parent->wb_right)
+		node = parent;
+
+	return parent;
+}
+EXPORT_SYMBOL(wb_next);
+
+struct wb_node *wb_prev(struct wb_node *node)
+{
+	struct wb_node *parent;
+
+	if (node->wb_parent == node)
+		return NULL;
+
+	if (node->wb_left) {
+		node = node->wb_left;
+		while (node->wb_right)
+			node = node->wb_right;
+		return node;
+	}
+
+	while ((parent = node->wb_parent)&&  node == parent->wb_left)
+		node = parent;
+
+	return parent;
+}
+EXPORT_SYMBOL(wb_prev);

Quoted 10 lines · Alex Williamson

Signed-off-by Alex Williamson<[email protected]>

---

  include/linux/wbtree.h |   55 ++++++++++++++++
  lib/Makefile           |    3 +
  lib/wbtree.c           |  170 ++++++++++++++++++++++++++++++++++++++++++++++++
  3 files changed, 227 insertions(+), 1 deletions(-)

create mode 100644 include/linux/wbtree.h
create mode 100644 lib/wbtree.c

Andrew, can we add something like this to the tree? Can it go through the kvm tree?

Quoted 66 lines

include/linux/wbtree.h new file +55 -0

new file mode 100644
index 0000000..ef70f6f
@@ -0,0 +1,55 @@
+/*
+ * Weight-balanced binary tree
+ *
+ * The balance of this tree is based on search probability.  The
+ * heaviest weighted nodes (the ones we're most likely to hit), are
+ * at the top of each subtree.
+ *
+ * Copywrite (C) 2011 Red Hat, Inc.
+ *
+ * Authors:
+ *   Alex Williamson<[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+#ifndef _LINUX_WBTREE_H
+#define _LINUX_WBTREE_H
+
+#include<linux/kernel.h>
+#include<linux/stddef.h>
+
+struct wb_node {
+	struct wb_node *wb_parent;
+	struct wb_node *wb_left;
+	struct wb_node *wb_right;
+	unsigned long wb_weight;
+};
+
+struct wb_root {
+	struct wb_node *wb_node;
+};
+
+#define WB_ROOT (struct wb_root) { NULL, }
+#define wb_entry(ptr, type, member) container_of(ptr, type, member)
+
+extern void wb_rebalance(struct wb_node *node, struct wb_root *root);
+extern void wb_erase(struct wb_node *node, struct wb_root *root);
+extern struct wb_node *wb_first(struct wb_root *root);
+extern struct wb_node *wb_last(struct wb_root *root);
+extern struct wb_node *wb_next(struct wb_node *node);
+extern struct wb_node *wb_prev(struct wb_node *node);
+
+static inline void wb_set_weight(struct wb_node *node, unsigned long weight)
+{
+	node->wb_weight = weight;
+}
+
+static inline void wb_link_node(struct wb_node *node, struct wb_node *parent,
+				struct wb_node **wb_link)
+{
+	node->wb_left = node->wb_right = NULL;
+	node->wb_parent = parent;
+	*wb_link = node;
+}
+#endif /* _LINUX_WBTREE_H */

lib/Makefile +0 -0

index cbb774f..5c42e63 100644

lib/Makefile lib-y += kobject.o kref.o klist.o · line 26

Quoted 7 lines

lib/Makefile +2 -1

@@ -21,7 +21,8 @@ lib-y	+= kobject.o kref.o klist.o
 
  obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
  	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
+	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
+	 wbtree.o
 

obj-$(CONFIG_WEIGHT_BALANCED_TREE) += wbtree.o

then kvm can select it, and the impact on non-kvm kernels is removed.

Quoted 4 lines

obj-$(CONFIG_WEIGHT_BALANCED_TREE) += wbtree.o

then kvm can select it, and the impact on non-kvm kernels is removed.

Then we'd have issues trying to build an external kvm module for a pre-existing non-kvm kernel. Do we care?

If we were to take such a
path, I think the default should be on, kvm would depend on it, but we could add an option to disable it for EMBEDDED/EXPERT. Thanks,

Quoted 7 lines · Alex Williamson

Quoted 4 lines

obj-$(CONFIG_WEIGHT_BALANCED_TREE) += wbtree.o

then kvm can select it, and the impact on non-kvm kernels is removed.

Then we'd have issues trying to build an external kvm module for a pre-existing non-kvm kernel. Do we care?

Officially, no.

What we typically do in these cases is copy the code into the kvm-kmod compatibility layer and compile it if the kernel doesn't supply it (like all older kernels regardless of config).

Quoted 3 lines

If we were to take such a
path, I think the default should be on, kvm would depend on it, but we could add an option to disable it for EMBEDDED/EXPERT. Thanks,

That would work as well.

Signed-off-by Alex Williamson <[email protected]>

---

 include/linux/wbtree.h |   55 ++++++++++++++++
 lib/Makefile           |    3 +
 lib/wbtree.c           |  170 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 227 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/wbtree.h
 create mode 100644 lib/wbtree.c

include/linux/wbtree.h new file +24 -0

new file mode 100644
index 0000000..ef70f6f
@@ -0,0 +1,55 @@
+/*
+ * Weight-balanced binary tree
+ *
+ * The balance of this tree is based on search probability.  The
+ * heaviest weighted nodes (the ones we're most likely to hit), are
+ * at the top of each subtree.
+ *
+ * Copywrite (C) 2011 Red Hat, Inc.
+ *
+ * Authors:
+ *   Alex Williamson <[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+#ifndef _LINUX_WBTREE_H
+#define _LINUX_WBTREE_H
+
+#include <linux/kernel.h>
+#include <linux/stddef.h>
+
+struct wb_node {
+	struct wb_node *wb_parent;
+	struct wb_node *wb_left;

Remove fixed KVM_MEMORY_SLOTS limit, allowing the slot array to grow on demand. Private slots are now allocated at the front instead of the end. Only x86 seems to use private slots, so this is now zero for all other archs. The memslots pointer is already updated using rcu, so changing the size off the array when it's replaces is straight forward. x86 also keeps a bitmap of slots used by a kvm_mmu_page, which requires a shadow tlb flush whenever we increase the number of slots. This forces the pages to be rebuilt with the new bitmap size.

  #define KVM_PIO_PAGE_OFFSET 1
  #define KVM_COALESCED_MMIO_PAGE_OFFSET 2

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

  static void kvm_mmu_free_page(struct kvm *kvm, struct kvm_mmu_page *sp)
  {
+	struct kvm_memslots *slots = kvm_memslots(kvm);
+
  	ASSERT(is_empty_shadow_page(sp->spt));
  	hlist_del(&sp->hash_link);
  	list_del(&sp->link);
+	if (unlikely(slots->nmemslots>  sizeof(sp->slot_bitmap) * 8))
+		kfree(sp->slot_bitmap);
  	__free_page(virt_to_page(sp->spt));
  	if (!sp->role.direct)
  		__free_page(virt_to_page(sp->gfns));

@@ -1048,6 +1052,7 @@ static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
  					       u64 *parent_pte, int direct)
  {
  	struct kvm_mmu_page *sp;
+	struct kvm_memslots *slots = kvm_memslots(vcpu->kvm);
 
  	sp = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_header_cache, sizeof *sp);
  	sp->spt = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_cache, PAGE_SIZE);

@@ -1056,7 +1061,16 @@ static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
  						  PAGE_SIZE);

arch/x86/kvm/mmu.c +3 -0

+	} else
+		bitmap_zero((void *)&sp->slot_bitmap, slots->nmemslots);
+
 
 
 

static void mmu_convert_notrap(struct kvm_mmu_page *sp)

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

@@ -3530,13 +3548,19 @@ int kvm_mmu_setup(struct kvm_vcpu *vcpu)
  void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot)
  {
  	struct kvm_mmu_page *sp;
+	struct kvm_memslots *slots = kvm_memslots(kvm);
 
  	list_for_each_entry(sp,&kvm->arch.active_mmu_pages, link) {
  		int i;
  		u64 *pt;

  	if (!npages) {
  		r = -ENOMEM;

virt/kvm/kvm_main.c +11 -4

-		slots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
+
+		nmemslots = (mem->slot>= kvm->memslots->nmemslots) ?
+			    mem->slot + 1 : kvm->memslots->nmemslots;
+
+		slots = kzalloc(sizeof(struct kvm_memslots) +
+				nmemslots * sizeof(struct kvm_memory_slot),
+				GFP_KERNEL);
  		if (!slots)
  			goto out_free;
-		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-		if (mem->slot>= slots->nmemslots)
-			slots->nmemslots = mem->slot + 1;
+		memcpy(slots, kvm->memslots,
+		       sizeof(struct kvm_memslots) + kvm->memslots->nmemslots *
+		       sizeof(struct kvm_memory_slot));
+		slots->nmemslots = nmemslots;
  		slots->generation++;
  		slots->memslots[mem->slot].flags |= KVM_MEMSLOT_INVALID;

virt/kvm/kvm_main.c +3 -3

  	if (!slots)
  		goto out_free;
-	memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-	if (mem->slot>= slots->nmemslots)
-		slots->nmemslots = mem->slot + 1;
+	memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots) +
+	       kvm->memslots->nmemslots * sizeof(struct kvm_memory_slot));
+	slots->nmemslots = nmemslots;
  	slots->generation++;
 
  	/* actual memory is freed via old in kvm_free_physmem_slot below */

Quoted 15 lines · Alex Williamson

Remove fixed KVM_MEMORY_SLOTS limit, allowing the slot array to grow on demand. Private slots are now allocated at the front instead of the end. Only x86 seems to use private slots, so this is now zero for all other archs. The memslots pointer is already updated using rcu, so changing the size off the array when it's replaces is straight forward. x86 also keeps a bitmap of slots used by a kvm_mmu_page, which requires a shadow tlb flush whenever we increase the number of slots. This forces the pages to be rebuilt with the new bitmap size.

  #define KVM_PIO_PAGE_OFFSET 1
  #define KVM_COALESCED_MMIO_PAGE_OFFSET 2

arch/x86/include/asm/kvm_host.h struct kvm_mmu_page { · line 209

Quoted 5 lines

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

@@ -207,7 +206,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);
+	unsigned long *slot_bitmap;

What about

     union {
           DECLARE_BITMAP(direct_slot_bitmap, BITS_PER_LONG);
           unsigned long *indirect_slot_bitmap;
     };

to make the hackery below more explicit?

Quoted 29 lines

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

  static void kvm_mmu_free_page(struct kvm *kvm, struct kvm_mmu_page *sp)
  {
+	struct kvm_memslots *slots = kvm_memslots(kvm);
+
  	ASSERT(is_empty_shadow_page(sp->spt));
  	hlist_del(&sp->hash_link);
  	list_del(&sp->link);
+	if (unlikely(slots->nmemslots>  sizeof(sp->slot_bitmap) * 8))
+		kfree(sp->slot_bitmap);
  	__free_page(virt_to_page(sp->spt));
  	if (!sp->role.direct)
  		__free_page(virt_to_page(sp->gfns));

@@ -1048,6 +1052,7 @@ static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,
  					       u64 *parent_pte, int direct)
  {
  	struct kvm_mmu_page *sp;
+	struct kvm_memslots *slots = kvm_memslots(vcpu->kvm);
 
  	sp = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_header_cache, sizeof *sp);
  	sp->spt = mmu_memory_cache_alloc(&vcpu->arch.mmu_page_cache, PAGE_SIZE);

@@ -1056,7 +1061,16 @@ 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);
+
+	if (unlikely(slots->nmemslots>  sizeof(sp->slot_bitmap) * 8)) {

arch/x86/kvm/mmu.c static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu, · line 1070

Quoted 5 lines

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

+		sp->slot_bitmap = kzalloc(sizeof(long) *
+					  BITS_TO_LONGS(slots->nmemslots),
+					  GFP_KERNEL);
+		if (!sp->slot_bitmap)
+			return NULL;

We don't support failing kvm_mmu_get_page(). See mmu_memory_cache_alloc() and mmu_topup_memory_caches().

Quoted 18 lines

arch/x86/kvm/mmu.c +3 -0

+	} else
+		bitmap_zero((void *)&sp->slot_bitmap, slots->nmemslots);
+
 
 
 

static void mmu_convert_notrap(struct kvm_mmu_page *sp)

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

@@ -3530,13 +3548,19 @@ int kvm_mmu_setup(struct kvm_vcpu *vcpu)
  void kvm_mmu_slot_remove_write_access(struct kvm *kvm, int slot)
  {
  	struct kvm_mmu_page *sp;
+	struct kvm_memslots *slots = kvm_memslots(kvm);
 
  	list_for_each_entry(sp,&kvm->arch.active_mmu_pages, link) {
  		int i;
  		u64 *pt;

arch/x86/kvm/mmu.c int kvm_mmu_setup(struct kvm_vcpu *vcpu) · line 3563

Quoted 10 lines

arch/x86/kvm/mmu.c +7 -2

 
-		if (!test_bit(slot, sp->slot_bitmap))
-			continue;
+		if (likely(slots->nmemslots<= sizeof(sp->slot_bitmap) * 8)) {
+			if (!test_bit(slot, (void *)&sp->slot_bitmap))
+				continue;
+		} else {
+			if (!test_bit(slot, sp->slot_bitmap))
+				continue;
+		}

That likely() would fail 100% for certain guests.

Neater to write

     slot_bitmap = sp_slot_bitmap(sp);
     if (!test_bit(slot, sp_slot_bitmap))
         continue;

Quoted 5 lines

include/linux/kvm_host.h +5 -0

+
+/*
+ * Protect from malicious userspace by putting an upper bound on the number
+ * of memory slots.  This is an arbitrarily large number that still allows
+ * us to make pseudo-guarantees about supporting 64 assigned devices with

include/linux/kvm_host.h line 47

Quoted 5 lines

+ * plenty of slots left over.
+ */

include/linux/kvm_host.h +3 -0

+#ifndef KVM_MAX_MEM_SLOTS
+ #define KVM_MAX_MEM_SLOTS 512
+#endif

The increase should be in a separate patch (after we optimize the search-fail case).

Quoted 26 lines

  	if (!npages) {
  		r = -ENOMEM;

virt/kvm/kvm_main.c +11 -4

-		slots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
+
+		nmemslots = (mem->slot>= kvm->memslots->nmemslots) ?
+			    mem->slot + 1 : kvm->memslots->nmemslots;
+
+		slots = kzalloc(sizeof(struct kvm_memslots) +
+				nmemslots * sizeof(struct kvm_memory_slot),
+				GFP_KERNEL);
  		if (!slots)
  			goto out_free;
-		memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-		if (mem->slot>= slots->nmemslots)
-			slots->nmemslots = mem->slot + 1;
+		memcpy(slots, kvm->memslots,
+		       sizeof(struct kvm_memslots) + kvm->memslots->nmemslots *
+		       sizeof(struct kvm_memory_slot));
+		slots->nmemslots = nmemslots;
  		slots->generation++;
  		slots->memslots[mem->slot].flags |= KVM_MEMSLOT_INVALID;

@@ -787,12 +797,21 @@ skip_lpage:
  	}
 

virt/kvm/kvm_main.c skip_lpage: · line 803

Quoted 6 lines

virt/kvm/kvm_main.c +4 -1

  	r = -ENOMEM;
-	slots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
+
+	if (mem->slot>= kvm->memslots->nmemslots) {
+		nmemslots = mem->slot + 1;
+		flush = true;

Isn't flush here a little too agressive? Shouldn't we flush only if we cross the BITS_PER_LONG threshold?

virt/kvm/kvm_main.c skip_lpage: · line 809

Quoted 6 lines

virt/kvm/kvm_main.c +6 -0

+	} else
+		nmemslots = kvm->memslots->nmemslots;
+
+	slots = kzalloc(sizeof(struct kvm_memslots) +
+			nmemslots * sizeof(struct kvm_memory_slot),
+			GFP_KERNEL);

Code duplication -> helper.

Quoted 12 lines

virt/kvm/kvm_main.c +3 -3

  	if (!slots)
  		goto out_free;
-	memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots));
-	if (mem->slot>= slots->nmemslots)
-		slots->nmemslots = mem->slot + 1;
+	memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots) +
+	       kvm->memslots->nmemslots * sizeof(struct kvm_memory_slot));
+	slots->nmemslots = nmemslots;
  	slots->generation++;
 
  	/* actual memory is freed via old in kvm_free_physmem_slot below */

virt/kvm/kvm_main.c skip_lpage: · line 832

Quoted 6 lines

virt/kvm/kvm_main.c +3 -0

@@ -808,6 +827,9 @@ skip_lpage:
  	rcu_assign_pointer(kvm->memslots, slots);
  	synchronize_srcu_expedited(&kvm->srcu);
 
+	if (flush)
+		kvm_arch_flush_shadow(kvm);
+

Need to flush before rcu_assign_pointer() so kvm_mmu_free_page() sees the old slot count.

But even that is insufficient since we'll create direct and indirect slot bitmaps concurrently. Need to store whether the bitmap is direct or not in kvm_mmu_page.

virt/kvm/kvm_main.c static long kvm_vm_ioctl(struct file *filp, · line 1858

Quoted 6 lines

virt/kvm/kvm_main.c +2 -0

@@ -1832,6 +1854,8 @@ static long kvm_vm_ioctl(struct file *filp,
  						sizeof kvm_userspace_mem))
  			goto out;
 
+		kvm_userspace_mem.slot += KVM_PRIVATE_MEM_SLOTS;
+

Slightly uneasy about this, but no real objection.

Quoted 7 lines

Quoted 6 lines

@@ -207,7 +206,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);
+ unsigned long *slot_bitmap;

Quoted 8 lines

What about

      union {
            DECLARE_BITMAP(direct_slot_bitmap, BITS_PER_LONG);
            unsigned long *indirect_slot_bitmap;
      };

to make the hackery below more explicit?

Yeah, it need something to make the hackery go down easier. I was actually thinking about:

	unsigned long *slot_bitmap;
	DECLARE_BITMAP(direct_slot_bitmap, BITS_PER_LONG);

Where we'd then just set:

	slot_bitmap =&direct_slot_bitmap;

It wastes 8 bytes, and pushes the cache a little harder, but still helps the locality and makes the usage more consistent.

Quoted 3 lines

We don't support failing kvm_mmu_get_page(). See mmu_memory_cache_alloc() and mmu_topup_memory_caches().

Hmm, apparently my search stopped at __direct_map() calling kvm_mmu_get_page() and handling an error.

Quoted 8 lines

Quoted 7 lines

   	r = -ENOMEM;

- slots = kzalloc(sizeof(struct kvm_memslots), GFP_KERNEL);
+
+ if (mem->slot>= kvm->memslots->nmemslots) {
+ nmemslots = mem->slot + 1;
+ flush = true;

Quoted 2 lines

Isn't flush here a little too agressive? Shouldn't we flush only if we cross the BITS_PER_LONG threshold?

Perhaps, but is that overly exploiting our knowledge about the bitmap implementation? I figured better to error too aggressively than too lazy since this is a rare event already.

Quoted 8 lines

Quoted 6 lines

@@ -1832,6 +1854,8 @@ static long kvm_vm_ioctl(struct file *filp,
sizeof kvm_userspace_mem))
goto out;

+ kvm_userspace_mem.slot += KVM_PRIVATE_MEM_SLOTS;
+

Slightly uneasy about this, but no real objection.

If you have better ideas, let me know. This reminds me to ask about this chunk:

virt/kvm/kvm_main.c +1 -1

@@ -671,7 +674,7 @@ int __kvm_set_memory_region(struct kvm *kvm,
 
         /* Check for overlaps */
         r = -EEXIST;
-       for (i = 0; i<  KVM_MEMORY_SLOTS; ++i) {
+       for (i = KVM_PRIVATE_MEM_SLOTS; i<  kvm->memslots->nmemslots; ++i) {
                 struct kvm_memory_slot *s =&kvm->memslots->memslots[i];
 
                 if (s == memslot || !s->npages)

I kept the same behavior as previous, but it highlights that we're not checking for overlaps between private slots and anything else. Existing bug? Thanks,

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Patches 2 & 3 go on to convert the KVM memory slots to a growable array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

Note that part of why this series is RFC is that the print_tree function in the last patch is debug code that generates output for dot. You can copy the output to a file and run:

dot -Tpdf foo.dot > foo.pdf

to generate a nice diagram of the tree currently in use. I'll follow-up with a few examples. Thanks,

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Patches 2 & 3 go on to convert the KVM memory slots to a growable array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Patches 2& 3 go on to convert the KVM memory slots to a growable array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

Note that part of why this series is RFC is that the print_tree function in the last patch is debug code that generates output for dot. You can copy the output to a file and run:

dot -Tpdf foo.dot> foo.pdf

to generate a nice diagram of the tree currently in use. I'll follow-up with a few examples. Thanks,

Alex

Quoted 7 lines · Alex Williamson

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Quoted 8 lines

Patches 2& 3 go on to convert the KVM memory slots to a growable array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

In this case, I think most of the faults (at least after the guest was warmed up) missed the tree completely.

In this case a weight balanced
tree is hardly optimal (it is optimized for hits), so I think you'll see a bigger gain from the mmio fault optimization. You'll probably see most of the gain running mmu intensive tests with ept=0.

Quoted 17 lines · Avi Kivity

Quoted 7 lines · Alex Williamson

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Quoted 8 lines

Patches 2& 3 go on to convert the KVM memory slots to a growable array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

Quoted 2 lines

In this case, I think most of the faults (at least after the guest was warmed up) missed the tree completely.

Except for the mmio faults for the NIC, which will traverse the entire depth of that branch of the tree for every access.

Quoted 4 lines

In this case a weight balanced
tree is hardly optimal (it is optimized for hits), so I think you'll see a bigger gain from the mmio fault optimization. You'll probably see most of the gain running mmu intensive tests with ept=0.

Right, the gain expected by this test is that we're only traversing 6-7 tree nodes until we don't find a match, versus the full 32 entries of the original memslot array. So it's effectively comparing worst case scenarios for both data structures.

Hopefully the followup with kernbench run with ept=0 show that there's also still a benefit in the data match scenario. The existing array ends up being nearly optimal for memory hits since it registers memory from 1M - 3.5G in slot0 and 4G - 10.5G in slot1. For the tree, we jump straight to the bigger slot. I'll run one more set of kernbench tests with the original code, just reversing slots 0&1 to see if we take much of a hit from the tree overhead. Thanks,

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
%cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Quoted 18 lines · Alex Williamson

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
%cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

Quoted 3 lines

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Doesn't this indicate we should use reordering, instead of a new data structure?

Quoted 19 lines · Avi Kivity

Quoted 18 lines · Alex Williamson

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

 Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
 User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
 System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
 %cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
 context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
 sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

Quoted 6 lines

Quoted 3 lines

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Doesn't this indicate we should use reordering, instead of a new data structure?

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

Quoted 27 lines · Alex Williamson

Quoted 19 lines · Avi Kivity

Quoted 18 lines · Alex Williamson

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

 Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
 User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
 System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
 %cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
 context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
 sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

Quoted 6 lines

Quoted 3 lines

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Doesn't this indicate we should use reordering, instead of a new data structure?

Quoted 7 lines

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

Scaling doesn't matter, only actual performance. Even a guest with 512 slots would still hammer only on the first few slots, since these will contain the bulk of memory.

Quoted 4 lines

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

We have three types of memory:

- RAM - a few large slots
- mapped mmio (for device assignment) - possible many small slots
- non-mapped mmio (for emulated devices) - no slots

The first two are handled in exactly the same way - they're just memory slots. We expect a lot more hits into the RAM slots, since they're much bigger. But by far the majority of faults will be for the third category - mapped memory will be hit once per page, then handled by hardware until Linux memory management does something about the page, which should hopefully be rare (with device assignment, rare == never, since those pages are pinned).

Therefore our optimization priorities should be
- complete miss into the slot list

- hit into the RAM slots

- hit into the other slots (trailing far behind)

Of course worst-case performance matters. For example, we might (not sure) be searching the list with the mmu spinlock held.

I think we still have a bit to go before we can justify the new data structure.

Quoted 9 lines

Quoted 8 lines

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

Quoted 3 lines

Scaling doesn't matter, only actual performance. Even a guest with 512 slots would still hammer only on the first few slots, since these will contain the bulk of memory.

It seems like we need a good mixed workload benchmark. So far we've only tested worst case, with a pure emulated I/O test, and best case, with a pure memory test. Ordering an array only helps the latter, and only barely beats the tree, so I suspect overall performance would be better with a tree.

Quoted 19 lines

Quoted 4 lines

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

We have three types of memory:

- RAM - a few large slots
- mapped mmio (for device assignment) - possible many small slots
- non-mapped mmio (for emulated devices) - no slots

The first two are handled in exactly the same way - they're just memory slots. We expect a lot more hits into the RAM slots, since they're much bigger. But by far the majority of faults will be for the third category - mapped memory will be hit once per page, then handled by hardware until Linux memory management does something about the page, which should hopefully be rare (with device assignment, rare == never, since those pages are pinned).

Quoted 2 lines

Therefore our optimization priorities should be
- complete miss into the slot list

The tree is obviously the most time and space efficient for this and the netperf results show a pretty clear win here. I think it's really only a question of whether we'd be ok with slow, cache thrashing, searches here if we could effectively cache the result for next time as you've suggested.

Even then, it seems like steady state performance would be prone to unusual slowdowns (ex. have to flush sptes on every add, what's the regeneration time to replace all those slow lookups?).

Quoted 1 line

- hit into the RAM slots

It's really just the indirection of the tree and slightly larger element size that gives the sorted array an edge here.

Quoted 1 line

- hit into the other slots (trailing far behind)

Obviously an array sucks at this.

Quoted 5 lines

Of course worst-case performance matters. For example, we might (not sure) be searching the list with the mmu spinlock held.

I think we still have a bit to go before we can justify the new data structure.

Suggestions for a mixed workload benchmark? What else would you like to see? Thanks,

Quoted 13 lines · Alex Williamson

Quoted 12 lines

Quoted 8 lines

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

Scaling doesn't matter, only actual performance. Even a guest with 512 slots would still hammer only on the first few slots, since these will contain the bulk of memory.

Quoted 5 lines

It seems like we need a good mixed workload benchmark. So far we've only tested worst case, with a pure emulated I/O test, and best case, with a pure memory test. Ordering an array only helps the latter, and only barely beats the tree, so I suspect overall performance would be better with a tree.

But if we cache the missed-all-memslots result in the spte, we eliminate the worst case, and are left with just the best case.

Quoted 19 lines

Quoted 19 lines

Quoted 4 lines

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

We have three types of memory:

- RAM - a few large slots
- mapped mmio (for device assignment) - possible many small slots
- non-mapped mmio (for emulated devices) - no slots

The first two are handled in exactly the same way - they're just memory slots. We expect a lot more hits into the RAM slots, since they're much bigger. But by far the majority of faults will be for the third category - mapped memory will be hit once per page, then handled by hardware until Linux memory management does something about the page, which should hopefully be rare (with device assignment, rare == never, since those pages are pinned).

Quoted 8 lines

Quoted 2 lines

Therefore our optimization priorities should be
- complete miss into the slot list

The tree is obviously the most time and space efficient for this and the netperf results show a pretty clear win here. I think it's really only a question of whether we'd be ok with slow, cache thrashing, searches here if we could effectively cache the result for next time as you've suggested.

Yes.

Quoted 3 lines

Even then, it seems like steady state performance would be prone to unusual slowdowns (ex. have to flush sptes on every add, what's the regeneration time to replace all those slow lookups?).

Those sptes would be flushed very rarely (never in normal operation). When we add a slot, yes we drop those sptes, but also a few million other sptes, so it's lost in the noise (regeneration time is just the slot lookup itself).

Quoted 15 lines

Quoted 1 line

- hit into the RAM slots

It's really just the indirection of the tree and slightly larger element size that gives the sorted array an edge here.

Quoted 1 line

- hit into the other slots (trailing far behind)

Obviously an array sucks at this.

Quoted 5 lines

Of course worst-case performance matters. For example, we might (not sure) be searching the list with the mmu spinlock held.

I think we still have a bit to go before we can justify the new data structure.

Quoted 2 lines

Suggestions for a mixed workload benchmark? What else would you like to see? Thanks,

The problem here is that all workloads will cache all memslots very quickly into sptes and all lookups will be misses. There are two cases where we have lookups that hit the memslots structure: ept=0, and host swap. Neither are things we want to optimize too heavily.

Quoted 8 lines

Quoted 5 lines

It seems like we need a good mixed workload benchmark. So far we've only tested worst case, with a pure emulated I/O test, and best case, with a pure memory test. Ordering an array only helps the latter, and only barely beats the tree, so I suspect overall performance would be better with a tree.

But if we cache the missed-all-memslots result in the spte, we eliminate the worst case, and are left with just the best case.

There's potentially a lot of entries between best case and worst case.

Quoted 5 lines

The problem here is that all workloads will cache all memslots very quickly into sptes and all lookups will be misses. There are two cases where we have lookups that hit the memslots structure: ept=0, and host swap. Neither are things we want to optimize too heavily.

Which seems to suggest that:

A. making those misses fast = win
B. making those misses fast + caching misses = win++ C. we don't care if the sorted array is subtly faster for ept=0

Sound right? So is the question whether cached misses alone gets us 99% of the improvement since hits are already getting cached in sptes for cases we care about?

Quoted 27 lines · Alex Williamson

Quoted 19 lines · Avi Kivity

Quoted 18 lines · Alex Williamson

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

 Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
 User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
 System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
 %cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
 context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
 sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

Quoted 6 lines

Quoted 3 lines

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Doesn't this indicate we should use reordering, instead of a new data structure?

Quoted 7 lines

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

Scaling doesn't matter, only actual performance. Even a guest with 512 slots would still hammer only on the first few slots, since these will contain the bulk of memory.

Quoted 4 lines

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

We have three types of memory:

- RAM - a few large slots
- mapped mmio (for device assignment) - possible many small slots
- non-mapped mmio (for emulated devices) - no slots

The first two are handled in exactly the same way - they're just memory slots. We expect a lot more hits into the RAM slots, since they're much bigger. But by far the majority of faults will be for the third category - mapped memory will be hit once per page, then handled by hardware until Linux memory management does something about the page, which should hopefully be rare (with device assignment, rare == never, since those pages are pinned).

Therefore our optimization priorities should be
- complete miss into the slot list
- hit into the RAM slots
- hit into the other slots (trailing far behind)

Of course worst-case performance matters. For example, we might (not sure) be searching the list with the mmu spinlock held.

I think we still have a bit to go before we can justify the new data structure.

Quoted 59 lines · Avi Kivity

Quoted 27 lines · Alex Williamson

Quoted 19 lines · Avi Kivity

Quoted 18 lines · Alex Williamson

I had forgotten about<1M mem, so actually the slot configuration was:

0:<1M
1: 1M - 3.5G
2: 4G+

I stacked the deck in favor of the static array (0: 4G+, 1: 1M-3.5G, 2:
<1M), and got these kernbench results:

base (stdev) reorder (stdev) wbtree (stdev)
--------+-----------------+----------------+----------------+

  Elapsed |  42.809 (0.19)  |  42.160 (0.22) |  42.305 (0.23) |
  User    | 115.709 (0.22)  | 114.358 (0.40) | 114.720 (0.31) |
  System  |  41.605 (0.14)  |  40.741 (0.22) |  40.924 (0.20) |
  %cpu    |   366.9 (1.45)  |   367.4 (1.17) |   367.6 (1.51) |
  context |  7272.3 (68.6)  |  7248.1 (89.7) |  7249.5 (97.8) |
  sleeps  | 14826.2 (110.6) | 14780.7 (86.9) | 14798.5 (63.0) |

Quoted 6 lines

Quoted 3 lines

So, wbtree is only slightly behind reordering, and the standard deviation suggests the runs are mostly within the noise of each other. Thanks,

Doesn't this indicate we should use reordering, instead of a new data structure?

Quoted 7 lines

The original problem that brought this on was scaling. The re-ordered array still has O(N) scaling while the tree should have ~O(logN) (note that it currently doesn't because it needs a compaction algorithm added after insert and remove). So yes, it's hard to beat the results of a test that hammers on the first couple entries of a sorted array, but I think the tree has better than current performance and more predictable when scaled performance.

Scaling doesn't matter, only actual performance. Even a guest with 512 slots would still hammer only on the first few slots, since these will contain the bulk of memory.

Quoted 4 lines

If we knew when we were searching for which type of data, it would perhaps be nice if we could use a sorted array for guest memory (since it's nicely bounded into a small number of large chunks), and a tree for mmio (where we expect the scaling to be a factor). Thanks,

We have three types of memory:

- RAM - a few large slots
- mapped mmio (for device assignment) - possible many small slots
- non-mapped mmio (for emulated devices) - no slots

The first two are handled in exactly the same way - they're just memory slots. We expect a lot more hits into the RAM slots, since they're much bigger. But by far the majority of faults will be for the third category - mapped memory will be hit once per page, then handled by hardware until Linux memory management does something about the page, which should hopefully be rare (with device assignment, rare == never, since those pages are pinned).

Quoted 4 lines

Therefore our optimization priorities should be
- complete miss into the slot list
- hit into the RAM slots
- hit into the other slots (trailing far behind)

Whatever ordering considered optimal in one workload can be suboptimal in another. The binary search reduces the number of slots inspected in the average case. Using slot size as weight favours probability.

Quoted 5 lines

Of course worst-case performance matters. For example, we might (not sure) be searching the list with the mmu spinlock held.

I think we still have a bit to go before we can justify the new data structure.

Intensive IDE disk IO on guest with lots of assigned network devices, 3% improvement on netperf with rtl8139, 1% improvement on kernbench?

Fail to see justification for not using it.

Quoted 17 lines · Avi Kivity

Quoted 15 lines · Alex Williamson

This series introduces a new weight-balanced binary tree (wbtree) for general use. It's largely leveraged from the rbtree, copying it's rotate functions, while introducing different rebalance and erase functions. This tree is particularly useful for managing memory ranges, where it's desirable to have the most likely targets (the largest ranges) at the top of each subtree.

Patches 2& 3 go on to convert the KVM memory slots to a growable
array and make use of wbtree for efficient managment. Trying to exercise the worst case for this data structure, I ran netperf TCP_RR on an emulated rtl8139 NIC connected directly to the host via a tap. Both qemu-kvm and the netserver on the host were pinned to optimal CPUs with taskset. This series resulted in a 3% improvement for this test.

Quoted 2 lines

In this case, I think most of the faults (at least after the guest was warmed up) missed the tree completely.

Except for the mmio faults for the NIC, which will traverse the entire depth of that branch of the tree for every access.

Quoted 4 lines

In this case a weight balanced
tree is hardly optimal (it is optimized for hits), so I think you'll see a bigger gain from the mmio fault optimization. You'll probably see most of the gain running mmu intensive tests with ept=0.

Right, the gain expected by this test is that we're only traversing 6-7 tree nodes until we don't find a match, versus the full 32 entries of the original memslot array. So it's effectively comparing worst case scenarios for both data structures.

Quoted 3 lines · Xiao Guangrong

Sort memslots then search the slot with binary search to speed up the slot searching

I'm not sure if a binary search is the right algorithm here. It introduces a lot of branches which may be mispredicted.

Options we've discussed are:

- Sort slots by size, use linear search (so the largest slots are found quickly)
- Weighted balanced tree http://en.wikipedia.org/wiki/Weight-balanced_tree, use weight == slot size

Both options still make the miss case (mmio) slow. We could cache the result of a miss in an spte by using a reserved bit, and checking the page fault error code (or seeing if we get an ept violation or ept misconfiguration), so if we get repeated mmio on a page, we don't need to search the slot list/tree.

Cache the last used slot, the hit ratio is more than 35% during my test

Cache guest page number to guest frame number to avoid walk guest page table frequently, the 'vtlb' idea is from Xen.

Note:
we can't use vtlb in ept guests since the guest tlb invalid operation is not intercept(reload CR3, invlpg), also can't used in L2 nnpt guest for the same reason, but we can used it to cache L1's npt page table.

Quoted 3 lines · Xiao Guangrong

Cache guest page number to guest frame number to avoid walk guest page table frequently, the 'vtlb' idea is from Xen.

Quoted 5 lines

Note:
we can't use vtlb in ept guests since the guest tlb invalid operation is not intercept(reload CR3, invlpg), also can't used in L2 nnpt guest for the same reason, but we can used it to cache L1's npt page table.

I'm not so hot about introducing a new mechanism strictly for older hosts... EPT exists in three generations of Intel processors now (Sandy Bridge, Westmere, and Nehalem), and NPT is significantly older.

Quoted 10 lines · Avi Kivity

Quoted 8 lines · Xiao Guangrong

Cache guest page number to guest frame number to avoid walk guest page table frequently, the 'vtlb' idea is from Xen.

Note:
we can't use vtlb in ept guests since the guest tlb invalid operation is not intercept(reload CR3, invlpg), also can't used in L2 nnpt guest for the same reason, but we can used it to cache L1's npt page table.

Quoted 2 lines

I'm not so hot about introducing a new mechanism strictly for older hosts... EPT exists in three generations of Intel processors now (Sandy Bridge, Westmere, and Nehalem), and NPT is significantly older.

Um...so, do we should stop the new features for softmmu, only bug fix is welcome? :-)