LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: "Maciej S. Szmigiero" <mail@maciej.szmigiero.name>
To: Paolo Bonzini <pbonzini@redhat.com>
Cc: Sean Christopherson <seanjc@google.com>,
	Vitaly Kuznetsov <vkuznets@redhat.com>,
	Wanpeng Li <wanpengli@tencent.com>,
	Jim Mattson <jmattson@google.com>, Joerg Roedel <joro@8bytes.org>,
	Igor Mammedov <imammedo@redhat.com>,
	kvm@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH 3/3] KVM: Make kvm_for_each_memslot_in_gfn_range() strict and use iterators
Date: Fri, 26 Nov 2021 01:31:09 +0100	[thread overview]
Message-ID: <4e6962905b2fc003acabf8bbee3a0ec1d634966c.1637884349.git.maciej.szmigiero@oracle.com> (raw)
In-Reply-To: <cover.1637884349.git.maciej.szmigiero@oracle.com>

From: "Maciej S. Szmigiero" <maciej.szmigiero@oracle.com>

Make kvm_for_each_memslot_in_gfn_range() return only memslots at least
partially intersecting the requested range.
At the same time modify its implementation to use iterators.

This simplifies kvm_check_memslot_overlap() a bit.

Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@oracle.com>
---
 arch/x86/kvm/mmu/mmu.c   |  11 ++---
 include/linux/kvm_host.h | 104 +++++++++++++++++++++++++--------------
 virt/kvm/kvm_main.c      |  17 ++-----
 3 files changed, 75 insertions(+), 57 deletions(-)

diff --git a/arch/x86/kvm/mmu/mmu.c b/arch/x86/kvm/mmu/mmu.c
index 8f0035517450..009eb27d34d3 100644
--- a/arch/x86/kvm/mmu/mmu.c
+++ b/arch/x86/kvm/mmu/mmu.c
@@ -5715,23 +5715,22 @@ static bool __kvm_zap_rmaps(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end)
 {
 	const struct kvm_memory_slot *memslot;
 	struct kvm_memslots *slots;
-	struct rb_node *node;
+	struct kvm_memslot_iter iter;
 	bool flush = false;
 	gfn_t start, end;
-	int i, idx;
+	int i;
 
 	if (!kvm_memslots_have_rmaps(kvm))
 		return flush;
 
 	for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) {
 		slots = __kvm_memslots(kvm, i);
-		idx = slots->node_idx;
 
-		kvm_for_each_memslot_in_gfn_range(node, slots, gfn_start, gfn_end) {
-			memslot = container_of(node, struct kvm_memory_slot, gfn_node[idx]);
+		kvm_for_each_memslot_in_gfn_range(&iter, slots, gfn_start, gfn_end) {
+			memslot = kvm_memslot_iter_slot(&iter);
 			start = max(gfn_start, memslot->base_gfn);
 			end = min(gfn_end, memslot->base_gfn + memslot->npages);
-			if (start >= end)
+			if (WARN_ON_ONCE(start >= end))
 				continue;
 
 			flush = slot_handle_level_range(kvm, memslot, kvm_zap_rmapp,
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 3932bb091099..580d9abd97c1 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -841,74 +841,104 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id)
 	return NULL;
 }
 
-static inline
-struct rb_node *kvm_memslots_gfn_upper_bound(struct kvm_memslots *slots, gfn_t gfn)
+/* Iterator used for walking memslots that overlap a gfn range. */
+struct kvm_memslot_iter {
+	struct kvm_memslots *slots;
+	gfn_t end;
+	struct rb_node *node;
+};
+
+static inline void kvm_memslot_iter_start(struct kvm_memslot_iter *iter,
+					  struct kvm_memslots *slots,
+					  gfn_t start, gfn_t end)
 {
 	int idx = slots->node_idx;
-	struct rb_node *node, *result = NULL;
+	struct rb_node *tmp;
+	struct kvm_memory_slot *slot;
 
-	for (node = slots->gfn_tree.rb_node; node; ) {
-		struct kvm_memory_slot *slot;
+	iter->slots = slots;
+	iter->end = end;
 
-		slot = container_of(node, struct kvm_memory_slot, gfn_node[idx]);
-		if (gfn < slot->base_gfn) {
-			result = node;
-			node = node->rb_left;
-		} else
-			node = node->rb_right;
+	/*
+	 * Find the so called "upper bound" of a key - the first node that has
+	 * its key strictly greater than the searched one (the start gfn in our case).
+	 */
+	iter->node = NULL;
+	for (tmp = slots->gfn_tree.rb_node; tmp; ) {
+		slot = container_of(tmp, struct kvm_memory_slot, gfn_node[idx]);
+		if (start < slot->base_gfn) {
+			iter->node = tmp;
+			tmp = tmp->rb_left;
+		} else {
+			tmp = tmp->rb_right;
+		}
 	}
 
-	return result;
-}
-
-static inline
-struct rb_node *kvm_for_each_in_gfn_first(struct kvm_memslots *slots, gfn_t start)
-{
-	struct rb_node *node;
-
 	/*
 	 * Find the slot with the lowest gfn that can possibly intersect with
 	 * the range, so we'll ideally have slot start <= range start
 	 */
-	node = kvm_memslots_gfn_upper_bound(slots, start);
-	if (node) {
-		struct rb_node *pnode;
-
+	if (iter->node) {
 		/*
 		 * A NULL previous node means that the very first slot
 		 * already has a higher start gfn.
 		 * In this case slot start > range start.
 		 */
-		pnode = rb_prev(node);
-		if (pnode)
-			node = pnode;
+		tmp = rb_prev(iter->node);
+		if (tmp)
+			iter->node = tmp;
 	} else {
 		/* a NULL node below means no slots */
-		node = rb_last(&slots->gfn_tree);
+		iter->node = rb_last(&slots->gfn_tree);
 	}
 
-	return node;
+	if (iter->node) {
+		/*
+		 * It is possible in the slot start < range start case that the
+		 * found slot ends before or at range start (slot end <= range start)
+		 * and so it does not overlap the requested range.
+		 *
+		 * In such non-overlapping case the next slot (if it exists) will
+		 * already have slot start > range start, otherwise the logic above
+		 * would have found it instead of the current slot.
+		 */
+		slot = container_of(iter->node, struct kvm_memory_slot, gfn_node[idx]);
+		if (slot->base_gfn + slot->npages <= start)
+			iter->node = rb_next(iter->node);
+	}
 }
 
-static inline
-bool kvm_for_each_in_gfn_no_more(struct kvm_memslots *slots, struct rb_node *node, gfn_t end)
+static inline struct kvm_memory_slot *kvm_memslot_iter_slot(struct kvm_memslot_iter *iter)
+{
+	return container_of(iter->node, struct kvm_memory_slot, gfn_node[iter->slots->node_idx]);
+}
+
+static inline bool kvm_memslot_iter_is_valid(struct kvm_memslot_iter *iter)
 {
 	struct kvm_memory_slot *memslot;
 
-	memslot = container_of(node, struct kvm_memory_slot, gfn_node[slots->node_idx]);
+	if (!iter->node)
+		return false;
+
+	memslot = kvm_memslot_iter_slot(iter);
 
 	/*
 	 * If this slot starts beyond or at the end of the range so does
 	 * every next one
 	 */
-	return memslot->base_gfn >= end;
+	return memslot->base_gfn < iter->end;
+}
+
+static inline void kvm_memslot_iter_next(struct kvm_memslot_iter *iter)
+{
+	iter->node = rb_next(iter->node);
 }
 
-/* Iterate over each memslot *possibly* intersecting [start, end) range */
-#define kvm_for_each_memslot_in_gfn_range(node, slots, start, end)	\
-	for (node = kvm_for_each_in_gfn_first(slots, start);		\
-	     node && !kvm_for_each_in_gfn_no_more(slots, node, end);	\
-	     node = rb_next(node))					\
+/* Iterate over each memslot at least partially intersecting [start, end) range */
+#define kvm_for_each_memslot_in_gfn_range(iter, slots, start, end)	 \
+	for (kvm_memslot_iter_start(iter, slots, start, end);		 \
+	     kvm_memslot_iter_is_valid(iter);				 \
+	     kvm_memslot_iter_next(iter))
 
 /*
  * KVM_SET_USER_MEMORY_REGION ioctl allows the following operations:
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 367c1cba26d2..d6503b92b3cf 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -1797,22 +1797,11 @@ static int kvm_set_memslot(struct kvm *kvm,
 static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id,
 				      gfn_t start, gfn_t end)
 {
-	int idx = slots->node_idx;
-	struct rb_node *node;
-
-	kvm_for_each_memslot_in_gfn_range(node, slots, start, end) {
-		struct kvm_memory_slot *cslot;
-		gfn_t cend;
+	struct kvm_memslot_iter iter;
 
-		cslot = container_of(node, struct kvm_memory_slot, gfn_node[idx]);
-		cend = cslot->base_gfn + cslot->npages;
-		if (cslot->id == id)
-			continue;
-
-		/* kvm_for_each_in_gfn_no_more() guarantees that cslot->base_gfn < nend */
-		if (cend > start)
+	kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end)
+		if (kvm_memslot_iter_slot(&iter)->id != id)
 			return true;
-	}
 
 	return false;
 }

  parent reply	other threads:[~2021-11-26  0:33 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-11-26  0:31 [PATCH 0/3] KVM: Scalable memslots implementation additional patches Maciej S. Szmigiero
2021-11-26  0:31 ` [PATCH 1/3] KVM: x86: Avoid overflowing nr_mmu_pages in kvm_arch_commit_memory_region() Maciej S. Szmigiero
2021-11-29 21:03   ` Sean Christopherson
2021-11-26  0:31 ` [PATCH 2/3] KVM: Use atomic_long_cmpxchg() instead of an open-coded variant Maciej S. Szmigiero
2021-11-26 10:34   ` Paolo Bonzini
2021-11-26  0:31 ` Maciej S. Szmigiero [this message]
2021-11-26 10:35 ` [PATCH 0/3] KVM: Scalable memslots implementation additional patches Paolo Bonzini
2021-11-26 13:18   ` Maciej S. Szmigiero
2021-11-26 13:19     ` Paolo Bonzini

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=4e6962905b2fc003acabf8bbee3a0ec1d634966c.1637884349.git.maciej.szmigiero@oracle.com \
    --to=mail@maciej.szmigiero.name \
    --cc=imammedo@redhat.com \
    --cc=jmattson@google.com \
    --cc=joro@8bytes.org \
    --cc=kvm@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=pbonzini@redhat.com \
    --cc=seanjc@google.com \
    --cc=vkuznets@redhat.com \
    --cc=wanpengli@tencent.com \
    --subject='Re: [PATCH 3/3] KVM: Make kvm_for_each_memslot_in_gfn_range() strict and use iterators' \
    /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

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