From patchwork Tue Feb 22 18:55:32 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alex Williamson X-Patchwork-Id: 580941 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id p1MIuUv3025811 for ; Tue, 22 Feb 2011 18:56:30 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754763Ab1BVSzl (ORCPT ); Tue, 22 Feb 2011 13:55:41 -0500 Received: from mx1.redhat.com ([209.132.183.28]:6030 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754113Ab1BVSzg (ORCPT ); Tue, 22 Feb 2011 13:55:36 -0500 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p1MItYih009366 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 22 Feb 2011 13:55:34 -0500 Received: from s20.home (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p1MItWKW029667; Tue, 22 Feb 2011 13:55:33 -0500 From: Alex Williamson Subject: [RFC PATCH 3/3] kvm: Use weight-balanced tree for memory slot management To: avi@redhat.com Cc: alex.williamson@redhat.com, linux-kernel@vger.kernel.org, kvm@vger.kernel.org, mtosatti@redhat.com, xiaoguangrong@cn.fujitsu.com Date: Tue, 22 Feb 2011 11:55:32 -0700 Message-ID: <20110222185527.22026.85401.stgit@s20.home> In-Reply-To: <20110222183822.22026.62832.stgit@s20.home> References: <20110222183822.22026.62832.stgit@s20.home> User-Agent: StGIT/0.14.3 MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.67 on 10.5.11.11 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter1.kernel.org [140.211.167.41]); Tue, 22 Feb 2011 18:56:30 +0000 (UTC) diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h index 7bbb36f..2a43f9b 100644 --- a/include/linux/kvm_host.h +++ b/include/linux/kvm_host.h @@ -18,6 +18,7 @@ #include #include #include +#include #include #include @@ -171,6 +172,7 @@ struct kvm_lpage_info { }; struct kvm_memory_slot { + struct wb_node wb_node; gfn_t base_gfn; unsigned long npages; unsigned long flags; @@ -225,6 +227,7 @@ struct kvm_irq_routing_table {}; struct kvm_memslots { int nmemslots; u64 generation; + struct wb_root wb_root; struct kvm_memory_slot memslots[]; }; diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c index a3a5bda..0a6ef96 100644 --- a/virt/kvm/kvm_main.c +++ b/virt/kvm/kvm_main.c @@ -447,6 +447,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->memslots->wb_root = WB_ROOT; if (init_srcu_struct(&kvm->srcu)) goto out_err_nosrcu; for (i = 0; i < KVM_NR_BUSES; i++) { @@ -611,6 +612,119 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot) } #endif /* !CONFIG_S390 */ +static struct kvm_memory_slot *kvm_memslot_search(gfn_t gfn, + struct kvm_memslots *slots) +{ + struct wb_node *node = slots->wb_root.wb_node; + struct kvm_memory_slot *slot; + + while (node) { + slot = wb_entry(node, struct kvm_memory_slot, wb_node); + + if (gfn < slot->base_gfn) + node = node->wb_left; + else if (gfn >= slot->base_gfn + slot->npages) + node = node->wb_right; + else + return slot; + } + return NULL; +} + +static void print_tree(struct kvm_memslots *slots) +{ + int i; + + printk("digraph wbtree {\nnode [shape = record];\n"); + + for (i = 0; i < slots->nmemslots; i++) { + struct kvm_memory_slot *s = &slots->memslots[i]; + struct wb_node *n = &s->wb_node; + + if (!s->npages) + continue; + + printk("node%d [label=\" | %lx-%lx\\n(%ld) | \"];\n", + i, (unsigned long)s->base_gfn, + (unsigned long)(s->base_gfn + s->npages), s->npages); + if (n->wb_left) { + struct kvm_memory_slot *sl; + int left; + sl = wb_entry(n->wb_left, struct kvm_memory_slot, + wb_node); + left = sl - slots->memslots; + printk("\"node%d\":l -> \"node%d\":n;\n", i, left); + } + if (n->wb_right) { + struct kvm_memory_slot *sr; + int right; + sr = wb_entry(n->wb_right, struct kvm_memory_slot, + wb_node); + right = sr - slots->memslots; + printk("\"node%d\":r -> \"node%d\":n;\n", i, right); + } + } + printk("}\n"); +} + +static int kvm_memslot_insert(struct kvm_memory_slot *slot, + struct kvm_memslots *slots) +{ + struct wb_node **node = &slots->wb_root.wb_node, *parent = NULL; + struct kvm_memory_slot *memslot; + + wb_set_weight(&slot->wb_node, slot->npages); + + while (*node) { + memslot = wb_entry(*node, struct kvm_memory_slot, wb_node); + parent = *node; + + if (slot->base_gfn + slot->npages <= memslot->base_gfn) + node = &(*node)->wb_left; + else if (slot->base_gfn >= memslot->base_gfn + memslot->npages) + node = &(*node)->wb_right; + else + return -EINVAL; + } + + wb_link_node(&slot->wb_node, parent, node); + wb_rebalance(&slot->wb_node, &slots->wb_root); + print_tree(slots); + return 0; +} + +static void kvm_memslot_remove(struct kvm_memory_slot *slot, + struct kvm_memslots *slots) +{ + wb_erase(&slot->wb_node, &slots->wb_root); + print_tree(slots); +} + +static inline void kvm_memslot_pointer_fix(void *old, void *new, void **ptr) +{ + if (*ptr) { + if (new > old) + *ptr += (new - old); + else + *ptr -= (old - new); + } +} + +static void kvm_memslots_copy_fixup(struct kvm_memslots *old, + struct kvm_memslots *new) +{ + int i; + + for (i = 0; i < old->nmemslots; i++) { + struct wb_node *node = &new->memslots[i].wb_node; + kvm_memslot_pointer_fix(old, new, (void **)&node->wb_left); + kvm_memslot_pointer_fix(old, new, (void **)&node->wb_right); + kvm_memslot_pointer_fix(old, new, (void **)&node->wb_parent); + } + + kvm_memslot_pointer_fix(old, new, (void **)&new->wb_root.wb_node); +} + /* * Allocate some memory and give it an address in the guest physical address * space. @@ -767,6 +881,8 @@ skip_lpage: memcpy(slots, kvm->memslots, sizeof(struct kvm_memslots) + kvm->memslots->nmemslots * sizeof(struct kvm_memory_slot)); + kvm_memslots_copy_fixup(kvm->memslots, slots); + new.wb_node = slots->memslots[mem->slot].wb_node; slots->nmemslots = nmemslots; slots->generation++; slots->memslots[mem->slot].flags |= KVM_MEMSLOT_INVALID; @@ -823,6 +939,13 @@ skip_lpage: } slots->memslots[mem->slot] = new; + kvm_memslots_copy_fixup(kvm->memslots, slots); + + if (npages) + kvm_memslot_insert(&slots->memslots[mem->slot], slots); + else + kvm_memslot_remove(&slots->memslots[mem->slot], slots); + old_memslots = kvm->memslots; rcu_assign_pointer(kvm->memslots, slots); synchronize_srcu_expedited(&kvm->srcu); @@ -946,16 +1069,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 kvm_memslot_search(gfn, slots); } struct kvm_memory_slot *gfn_to_memslot(struct kvm *kvm, gfn_t gfn) @@ -966,20 +1080,16 @@ 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 *slot = kvm_memslot_search(gfn, slots); - for (i = KVM_PRIVATE_MEM_SLOTS; i < slots->nmemslots; ++i) { - struct kvm_memory_slot *memslot = &slots->memslots[i]; + if (!slot || slot->flags & KVM_MEMSLOT_INVALID) + return 0; - if (memslot->flags & KVM_MEMSLOT_INVALID) - continue; + if (slot - slots->memslots < KVM_PRIVATE_MEM_SLOTS) + 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); @@ -1009,19 +1119,10 @@ out: int memslot_id(struct kvm *kvm, gfn_t gfn) { - int i; struct kvm_memslots *slots = kvm_memslots(kvm); - struct kvm_memory_slot *memslot = NULL; - - for (i = 0; i < slots->nmemslots; ++i) { - memslot = &slots->memslots[i]; - - if (gfn >= memslot->base_gfn - && gfn < memslot->base_gfn + memslot->npages) - break; - } + struct kvm_memory_slot *slot = kvm_memslot_search(gfn, slots); - return memslot - slots->memslots; + return slot ? slot - slots->memslots : slots->nmemslots; } static unsigned long gfn_to_hva_many(struct kvm_memory_slot *slot, gfn_t gfn,