From: "Maciej S. Szmigiero" <mail@maciej.szmigiero.name>
To: Paolo Bonzini <pbonzini@redhat.com>,
Vitaly Kuznetsov <vkuznets@redhat.com>
Cc: Sean Christopherson <seanjc@google.com>,
Wanpeng Li <wanpengli@tencent.com>,
Jim Mattson <jmattson@google.com>,
Igor Mammedov <imammedo@redhat.com>,
Marc Zyngier <maz@kernel.org>, James Morse <james.morse@arm.com>,
Julien Thierry <julien.thierry.kdev@gmail.com>,
Suzuki K Poulose <suzuki.poulose@arm.com>,
Huacai Chen <chenhuacai@kernel.org>,
Aleksandar Markovic <aleksandar.qemu.devel@gmail.com>,
Paul Mackerras <paulus@ozlabs.org>,
Christian Borntraeger <borntraeger@de.ibm.com>,
Janosch Frank <frankja@linux.ibm.com>,
David Hildenbrand <david@redhat.com>,
Cornelia Huck <cohuck@redhat.com>,
Claudio Imbrenda <imbrenda@linux.ibm.com>,
Joerg Roedel <joro@8bytes.org>,
kvm@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH v3 8/8] KVM: Optimize overlapping memslots check
Date: Sun, 16 May 2021 23:44:34 +0200 [thread overview]
Message-ID: <61d53c8121b5b906bbed363e493ac75aebbda693.1621191552.git.maciej.szmigiero@oracle.com> (raw)
In-Reply-To: <cover.1621191549.git.maciej.szmigiero@oracle.com>
From: "Maciej S. Szmigiero" <maciej.szmigiero@oracle.com>
Do a quick lookup for possibly overlapping gfns when creating or moving
a memslot instead of performing a linear scan of the whole memslot set.
Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@oracle.com>
---
virt/kvm/kvm_main.c | 65 ++++++++++++++++++++++++++++++++++++++-------
1 file changed, 56 insertions(+), 9 deletions(-)
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 189504b27ca6..11814730cbcb 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -1474,6 +1474,59 @@ static int kvm_delete_memslot(struct kvm *kvm,
return kvm_set_memslot(kvm, mem, old, &new, as_id, KVM_MR_DELETE);
}
+static bool kvm_check_memslot_overlap(struct kvm_memslots *slots,
+ struct kvm_memory_slot *nslot)
+{
+ int idxactive = kvm_memslots_idx(slots);
+ struct rb_node *node;
+
+ /*
+ * Find the slot with the lowest gfn that can possibly intersect with
+ * the new slot, so we'll ideally have slot start <= nslot start
+ */
+ node = kvm_memslots_gfn_upper_bound(slots, nslot->base_gfn);
+ if (node) {
+ struct rb_node *pnode;
+
+ /*
+ * A NULL previous node means that the very first slot
+ * already has a higher start gfn.
+ * In this case slot start > nslot start.
+ */
+ pnode = rb_prev(node);
+ if (pnode)
+ node = pnode;
+ } else {
+ /* a NULL node below means no existing slots */
+ node = rb_last(&slots->gfn_tree);
+ }
+
+ for ( ; node; node = rb_next(node)) {
+ struct kvm_memory_slot *cslot;
+
+ cslot = container_of(node, struct kvm_memory_slot,
+ gfn_node[idxactive]);
+
+ /*
+ * if this slot starts beyond or at the end of the new slot
+ * so does every next one
+ */
+ if (cslot->base_gfn >= nslot->base_gfn + nslot->npages)
+ break;
+
+ if (cslot->id == nslot->id)
+ continue;
+
+ if (cslot->base_gfn >= nslot->base_gfn)
+ return true;
+
+ if (cslot->base_gfn + cslot->npages > nslot->base_gfn)
+ return true;
+ }
+
+ return false;
+}
+
/*
* Allocate some memory and give it an address in the guest physical address
* space.
@@ -1559,16 +1612,10 @@ int __kvm_set_memory_region(struct kvm *kvm,
}
if ((change == KVM_MR_CREATE) || (change == KVM_MR_MOVE)) {
- int ctr;
-
/* Check for overlaps */
- kvm_for_each_memslot(tmp, ctr, __kvm_memslots(kvm, as_id)) {
- if (tmp->id == id)
- continue;
- if (!((new.base_gfn + new.npages <= tmp->base_gfn) ||
- (new.base_gfn >= tmp->base_gfn + tmp->npages)))
- return -EEXIST;
- }
+ if (kvm_check_memslot_overlap(__kvm_memslots(kvm, as_id),
+ &new))
+ return -EEXIST;
}
/* Allocate/free page dirty bitmap as needed */
prev parent reply other threads:[~2021-05-16 21:45 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-16 21:44 [PATCH v3 0/8] KVM: Scalable memslots implementation Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 1/8] KVM: x86: Cache total page count to avoid traversing the memslot array Maciej S. Szmigiero
2021-05-19 21:00 ` Sean Christopherson
2021-05-21 7:03 ` Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 2/8] KVM: Integrate gfn_to_memslot_approx() into search_memslots() Maciej S. Szmigiero
2021-05-19 21:24 ` Sean Christopherson
2021-05-21 7:03 ` Maciej S. Szmigiero
2021-06-10 16:17 ` Paolo Bonzini
2021-05-16 21:44 ` [PATCH v3 3/8] KVM: Resolve memslot ID via a hash table instead of via a static array Maciej S. Szmigiero
2021-05-19 22:31 ` Sean Christopherson
2021-05-21 7:05 ` Maciej S. Szmigiero
2021-05-22 11:11 ` Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 4/8] KVM: Introduce memslots hva tree Maciej S. Szmigiero
2021-05-19 23:07 ` Sean Christopherson
2021-05-21 7:06 ` Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 5/8] KVM: s390: Introduce kvm_s390_get_gfn_end() Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 6/8] KVM: Keep memslots in tree-based structures instead of array-based ones Maciej S. Szmigiero
2021-05-19 23:10 ` Sean Christopherson
2021-05-21 7:06 ` Maciej S. Szmigiero
2021-05-25 23:21 ` Sean Christopherson
2021-06-01 20:24 ` Maciej S. Szmigiero
2021-05-16 21:44 ` [PATCH v3 7/8] KVM: Optimize gfn lookup in kvm_zap_gfn_range() Maciej S. Szmigiero
2021-05-26 17:33 ` Sean Christopherson
2021-06-01 20:25 ` Maciej S. Szmigiero
2021-05-16 21:44 ` Maciej S. Szmigiero [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=61d53c8121b5b906bbed363e493ac75aebbda693.1621191552.git.maciej.szmigiero@oracle.com \
--to=mail@maciej.szmigiero.name \
--cc=aleksandar.qemu.devel@gmail.com \
--cc=borntraeger@de.ibm.com \
--cc=chenhuacai@kernel.org \
--cc=cohuck@redhat.com \
--cc=david@redhat.com \
--cc=frankja@linux.ibm.com \
--cc=imammedo@redhat.com \
--cc=imbrenda@linux.ibm.com \
--cc=james.morse@arm.com \
--cc=jmattson@google.com \
--cc=joro@8bytes.org \
--cc=julien.thierry.kdev@gmail.com \
--cc=kvm@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=maz@kernel.org \
--cc=paulus@ozlabs.org \
--cc=pbonzini@redhat.com \
--cc=seanjc@google.com \
--cc=suzuki.poulose@arm.com \
--cc=vkuznets@redhat.com \
--cc=wanpengli@tencent.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).