From: Sean Christopherson <sean.j.christopherson@intel.com>
To: "James Hogan" <jhogan@kernel.org>,
"Paul Mackerras" <paulus@ozlabs.org>,
"Christian Borntraeger" <borntraeger@de.ibm.com>,
"Janosch Frank" <frankja@linux.ibm.com>,
"Paolo Bonzini" <pbonzini@redhat.com>,
"Radim Krčmář" <rkrcmar@redhat.com>,
"Marc Zyngier" <maz@kernel.org>
Cc: David Hildenbrand <david@redhat.com>,
Cornelia Huck <cohuck@redhat.com>,
Sean Christopherson <sean.j.christopherson@intel.com>,
Vitaly Kuznetsov <vkuznets@redhat.com>,
Wanpeng Li <wanpengli@tencent.com>,
Jim Mattson <jmattson@google.com>, Joerg Roedel <joro@8bytes.org>,
James Morse <james.morse@arm.com>,
Julien Thierry <julien.thierry.kdev@gmail.com>,
Suzuki K Poulose <suzuki.poulose@arm.com>,
linux-mips@vger.kernel.org, kvm-ppc@vger.kernel.org,
kvm@vger.kernel.org, linux-arm-kernel@lists.infradead.org,
kvmarm@lists.cs.columbia.edu, linux-kernel@vger.kernel.org
Subject: [PATCH v2 14/15] KVM: Terminate memslot walks via used_slots
Date: Mon, 21 Oct 2019 17:35:36 -0700 [thread overview]
Message-ID: <20191022003537.13013-15-sean.j.christopherson@intel.com> (raw)
In-Reply-To: <20191022003537.13013-1-sean.j.christopherson@intel.com>
Refactor memslot handling to treat the number of used slots as the de
facto size of the memslot array, e.g. return NULL from id_to_memslot()
when an invalid index is provided instead of relying on npages==0 to
detect an invalid memslot. Rework the sorting and walking of memslots
in advance of dynamically sizing memslots to aid bisection and debug,
e.g. with luck, a bug in the refactoring will bisect here and/or hit a
WARN instead of randomly corrupting memory.
Alternatively, a global null/invalid memslot could be returned, i.e. so
callers of id_to_memslot() don't have to explicitly check for a NULL
memslot, but that approach runs the risk of introducing difficult-to-
debug issues, e.g. if the global null slot is modified. Constifying
the return from id_to_memslot() to combat such issues is possible, but
would require a massive refactoring of arch specific code and would
still be susceptible to casting shenanigans.
Add function comments to update_memslots() and search_memslots() to
explicitly (and loudly) state how memslots are sorted.
No functional change intended.
Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
---
arch/powerpc/kvm/book3s_hv.c | 2 +-
arch/x86/kvm/x86.c | 14 ++--
include/linux/kvm_host.h | 18 +++--
virt/kvm/arm/mmu.c | 9 ++-
virt/kvm/kvm_main.c | 145 ++++++++++++++++++++++-------------
5 files changed, 117 insertions(+), 71 deletions(-)
diff --git a/arch/powerpc/kvm/book3s_hv.c b/arch/powerpc/kvm/book3s_hv.c
index 14906f7c12c5..444c76091f17 100644
--- a/arch/powerpc/kvm/book3s_hv.c
+++ b/arch/powerpc/kvm/book3s_hv.c
@@ -4405,7 +4405,7 @@ static int kvm_vm_ioctl_get_dirty_log_hv(struct kvm *kvm,
slots = kvm_memslots(kvm);
memslot = id_to_memslot(slots, log->slot);
r = -ENOENT;
- if (!memslot->dirty_bitmap)
+ if (!memslot || !memslot->dirty_bitmap)
goto out;
/*
diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index 3d3d70aac031..ccaca74b2a0f 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -9437,9 +9437,9 @@ void kvm_arch_sync_events(struct kvm *kvm)
int __x86_set_memory_region(struct kvm *kvm, int id, gpa_t gpa, u32 size)
{
int i, r;
- unsigned long hva;
+ unsigned long hva, uninitialized_var(old_npages);
struct kvm_memslots *slots = kvm_memslots(kvm);
- struct kvm_memory_slot *slot, old;
+ struct kvm_memory_slot *slot;
/* Called with kvm->slots_lock held. */
if (WARN_ON(id >= KVM_MEM_SLOTS_NUM))
@@ -9447,7 +9447,7 @@ int __x86_set_memory_region(struct kvm *kvm, int id, gpa_t gpa, u32 size)
slot = id_to_memslot(slots, id);
if (size) {
- if (slot->npages)
+ if (slot && slot->npages)
return -EEXIST;
/*
@@ -9459,13 +9459,13 @@ int __x86_set_memory_region(struct kvm *kvm, int id, gpa_t gpa, u32 size)
if (IS_ERR((void *)hva))
return PTR_ERR((void *)hva);
} else {
- if (!slot->npages)
+ if (!slot || !slot->npages)
return 0;
- hva = 0;
+ hva = slot->userspace_addr;
+ old_npages = slot->npages;
}
- old = *slot;
for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) {
struct kvm_userspace_memory_region m;
@@ -9480,7 +9480,7 @@ int __x86_set_memory_region(struct kvm *kvm, int id, gpa_t gpa, u32 size)
}
if (!size)
- vm_munmap(old.userspace_addr, old.npages * PAGE_SIZE);
+ vm_munmap(hva, old_npages * PAGE_SIZE);
return 0;
}
diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 4eb14a8cd9cb..3f8a7760bb79 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -580,10 +580,11 @@ static inline int kvm_vcpu_get_idx(struct kvm_vcpu *vcpu)
BUG();
}
-#define kvm_for_each_memslot(memslot, slots) \
- for (memslot = &slots->memslots[0]; \
- memslot < slots->memslots + KVM_MEM_SLOTS_NUM && memslot->npages;\
- memslot++)
+#define kvm_for_each_memslot(memslot, slots) \
+ for (memslot = &slots->memslots[0]; \
+ memslot < slots->memslots + slots->used_slots; memslot++) \
+ if (WARN_ON_ONCE(!memslot->npages)) { \
+ } else
int kvm_vcpu_init(struct kvm_vcpu *vcpu, struct kvm *kvm, unsigned id);
void kvm_vcpu_uninit(struct kvm_vcpu *vcpu);
@@ -643,12 +644,15 @@ static inline struct kvm_memslots *kvm_vcpu_memslots(struct kvm_vcpu *vcpu)
return __kvm_memslots(vcpu->kvm, as_id);
}
-static inline struct kvm_memory_slot *
-id_to_memslot(struct kvm_memslots *slots, int id)
+static inline
+struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id)
{
int index = slots->id_to_index[id];
struct kvm_memory_slot *slot;
+ if (index < 0)
+ return NULL;
+
slot = &slots->memslots[index];
WARN_ON(slot->id != id);
@@ -993,6 +997,8 @@ bool kvm_arch_irqfd_allowed(struct kvm *kvm, struct kvm_irqfd *args);
* used in non-modular code in arch/powerpc/kvm/book3s_hv_rm_mmu.c.
* gfn_to_memslot() itself isn't here as an inline because that would
* bloat other code too much.
+ *
+ * IMPORTANT: Slots are sorted from highest GFN to lowest GFN!
*/
static inline struct kvm_memory_slot *
search_memslots(struct kvm_memslots *slots, gfn_t gfn)
diff --git a/virt/kvm/arm/mmu.c b/virt/kvm/arm/mmu.c
index f3241b268d49..7ea3321cabb8 100644
--- a/virt/kvm/arm/mmu.c
+++ b/virt/kvm/arm/mmu.c
@@ -1536,8 +1536,13 @@ void kvm_mmu_wp_memory_region(struct kvm *kvm, int slot)
{
struct kvm_memslots *slots = kvm_memslots(kvm);
struct kvm_memory_slot *memslot = id_to_memslot(slots, slot);
- phys_addr_t start = memslot->base_gfn << PAGE_SHIFT;
- phys_addr_t end = (memslot->base_gfn + memslot->npages) << PAGE_SHIFT;
+ phys_addr_t start, end;
+
+ if (WARN_ON_ONCE(!memslot))
+ return;
+
+ start = memslot->base_gfn << PAGE_SHIFT;
+ end = (memslot->base_gfn + memslot->npages) << PAGE_SHIFT;
spin_lock(&kvm->mmu_lock);
stage2_wp_range(kvm, start, end);
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
index 7e5a88ab57b6..177caac395de 100644
--- a/virt/kvm/kvm_main.c
+++ b/virt/kvm/kvm_main.c
@@ -535,7 +535,7 @@ static struct kvm_memslots *kvm_alloc_memslots(void)
return NULL;
for (i = 0; i < KVM_MEM_SLOTS_NUM; i++)
- slots->id_to_index[i] = slots->memslots[i].id = i;
+ slots->id_to_index[i] = slots->memslots[i].id = -1;
return slots;
}
@@ -794,64 +794,94 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot)
return 0;
}
+static inline void kvm_shift_memslots_deleted(struct kvm_memslots *slots,
+ struct kvm_memory_slot *new)
+{
+ struct kvm_memory_slot *mslots = slots->memslots;
+ int i;
+
+ if (WARN_ON(slots->id_to_index[new->id] == -1))
+ return;
+
+ slots->used_slots--;
+
+ for (i = slots->id_to_index[new->id]; i < slots->used_slots; i++) {
+ mslots[i] = mslots[i + 1];
+ slots->id_to_index[mslots[i].id] = i;
+ }
+ mslots[i] = *new;
+ slots->id_to_index[new->id] = -1;
+}
+
+static inline int kvm_shift_memslots_forward(struct kvm_memslots *slots,
+ struct kvm_memory_slot *new)
+{
+ struct kvm_memory_slot *mslots = slots->memslots;
+ int i;
+
+ if (WARN_ON_ONCE(slots->id_to_index[new->id] == -1) ||
+ WARN_ON_ONCE(!slots->used_slots))
+ return -1;
+
+ for (i = slots->id_to_index[new->id]; i < slots->used_slots - 1; i++) {
+ if (new->base_gfn > mslots[i + 1].base_gfn)
+ break;
+
+ WARN_ON_ONCE(new->base_gfn == mslots[i + 1].base_gfn);
+
+ /* Shift the next memslot forward one and update its index. */
+ mslots[i] = mslots[i + 1];
+ slots->id_to_index[mslots[i].id] = i;
+ }
+ return i;
+}
+
+static inline int kvm_shift_memslots_back(struct kvm_memslots *slots,
+ struct kvm_memory_slot *new,
+ int start)
+{
+ struct kvm_memory_slot *mslots = slots->memslots;
+ int i;
+
+ for (i = start; i > 0; i--) {
+ if (new->base_gfn < mslots[i - 1].base_gfn)
+ break;
+
+ WARN_ON_ONCE(new->base_gfn == mslots[i - 1].base_gfn);
+
+ /* Shift the next memslot back one and update its index. */
+ mslots[i] = mslots[i - 1];
+ slots->id_to_index[mslots[i].id] = i;
+ }
+ return i;
+}
+
/*
* Insert memslot and re-sort memslots based on their GFN,
* so binary search could be used to lookup GFN.
* Sorting algorithm takes advantage of having initially
* sorted array and known changed memslot position.
+ *
+ * IMPORTANT: Slots are sorted from highest GFN to lowest GFN!
*/
static void update_memslots(struct kvm_memslots *slots,
struct kvm_memory_slot *new,
enum kvm_mr_change change)
{
- int id = new->id;
- int i = slots->id_to_index[id];
- struct kvm_memory_slot *mslots = slots->memslots;
-
- WARN_ON(mslots[i].id != id);
- switch (change) {
- case KVM_MR_CREATE:
- slots->used_slots++;
- WARN_ON(mslots[i].npages || !new->npages);
- break;
- case KVM_MR_DELETE:
- slots->used_slots--;
- WARN_ON(new->npages || !mslots[i].npages);
- break;
- default:
- break;
- }
-
- while (i < KVM_MEM_SLOTS_NUM - 1 &&
- new->base_gfn <= mslots[i + 1].base_gfn) {
- if (!mslots[i + 1].npages)
- break;
- mslots[i] = mslots[i + 1];
- slots->id_to_index[mslots[i].id] = i;
- i++;
+ int i;
+
+ if (change == KVM_MR_DELETE) {
+ kvm_shift_memslots_deleted(slots, new);
+ } else {
+ if (change == KVM_MR_CREATE)
+ i = slots->used_slots++;
+ else
+ i = kvm_shift_memslots_forward(slots, new);
+ i = kvm_shift_memslots_back(slots, new, i);
+
+ slots->memslots[i] = *new;
+ slots->id_to_index[new->id] = i;
}
-
- /*
- * The ">=" is needed when creating a slot with base_gfn == 0,
- * so that it moves before all those with base_gfn == npages == 0.
- *
- * On the other hand, if new->npages is zero, the above loop has
- * already left i pointing to the beginning of the empty part of
- * mslots, and the ">=" would move the hole backwards in this
- * case---which is wrong. So skip the loop when deleting a slot.
- */
- if (new->npages) {
- while (i > 0 &&
- new->base_gfn >= mslots[i - 1].base_gfn) {
- mslots[i] = mslots[i - 1];
- slots->id_to_index[mslots[i].id] = i;
- i--;
- }
- } else
- WARN_ON_ONCE(i != slots->used_slots);
-
- mslots[i] = *new;
- slots->id_to_index[mslots[i].id] = i;
}
static int check_memory_region_flags(const struct kvm_userspace_memory_region *mem)
@@ -1030,8 +1060,13 @@ int __kvm_set_memory_region(struct kvm *kvm,
* when the memslots are re-sorted by update_memslots().
*/
tmp = id_to_memslot(__kvm_memslots(kvm, as_id), id);
- old = *tmp;
- tmp = NULL;
+ if (tmp) {
+ old = *tmp;
+ tmp = NULL;
+ } else {
+ memset(&old, 0, sizeof(old));
+ old.id = id;
+ }
if (!mem->memory_size)
return kvm_delete_memslot(kvm, mem, &old, as_id);
@@ -1149,7 +1184,7 @@ int kvm_get_dirty_log(struct kvm *kvm, struct kvm_dirty_log *log,
slots = __kvm_memslots(kvm, as_id);
*memslot = id_to_memslot(slots, id);
- if (!(*memslot)->dirty_bitmap)
+ if (!(*memslot) || !(*memslot)->dirty_bitmap)
return -ENOENT;
kvm_arch_sync_dirty_log(kvm, *memslot);
@@ -1207,10 +1242,10 @@ static int kvm_get_dirty_log_protect(struct kvm *kvm, struct kvm_dirty_log *log)
slots = __kvm_memslots(kvm, as_id);
memslot = id_to_memslot(slots, id);
+ if (!memslot || !memslot->dirty_bitmap)
+ return -ENOENT;
dirty_bitmap = memslot->dirty_bitmap;
- if (!dirty_bitmap)
- return -ENOENT;
kvm_arch_sync_dirty_log(kvm, memslot);
@@ -1318,10 +1353,10 @@ static int kvm_clear_dirty_log_protect(struct kvm *kvm,
slots = __kvm_memslots(kvm, as_id);
memslot = id_to_memslot(slots, id);
+ if (!memslot || !memslot->dirty_bitmap)
+ return -ENOENT;
dirty_bitmap = memslot->dirty_bitmap;
- if (!dirty_bitmap)
- return -ENOENT;
n = ALIGN(log->num_pages, BITS_PER_LONG) / 8;
--
2.22.0
next prev parent reply other threads:[~2019-10-22 0:36 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-22 0:35 [PATCH v2 00/15] KVM: Dynamically size memslot arrays Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 01/15] KVM: Reinstall old memslots if arch preparation fails Sean Christopherson
2019-10-23 9:29 ` Christoffer Dall
2019-10-22 0:35 ` [PATCH v2 02/15] KVM: Don't free new memslot if allocation of said memslot fails Sean Christopherson
2019-10-23 9:29 ` Christoffer Dall
2019-10-22 0:35 ` [PATCH v2 03/15] KVM: PPC: Move memslot memory allocation into prepare_memory_region() Sean Christopherson
2019-10-24 11:55 ` kbuild test robot
2019-10-22 0:35 ` [PATCH v2 04/15] KVM: x86: Allocate memslot resources during prepare_memory_region() Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 05/15] KVM: Drop kvm_arch_create_memslot() Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 06/15] KVM: Explicitly free allocated-but-unused dirty bitmap Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 07/15] KVM: Refactor error handling for setting memory region Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 08/15] KVM: Move setting of memslot into helper routine Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 09/15] KVM: Move memslot deletion to helper function Sean Christopherson
2019-10-23 9:29 ` Christoffer Dall
2019-10-22 0:35 ` [PATCH v2 10/15] KVM: Simplify kvm_free_memslot() and all its descendents Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 11/15] KVM: Clean up local variable usage in __kvm_set_memory_region() Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 12/15] KVM: Provide common implementation for generic dirty log functions Sean Christopherson
2019-10-23 9:29 ` Christoffer Dall
2019-10-24 10:28 ` kbuild test robot
2019-10-22 0:35 ` [PATCH v2 13/15] KVM: Ensure validity of memslot with respect to kvm_get_dirty_log() Sean Christopherson
2019-10-22 0:35 ` Sean Christopherson [this message]
2019-10-22 14:04 ` [PATCH v2 14/15] KVM: Terminate memslot walks via used_slots Paolo Bonzini
2019-10-22 15:28 ` Sean Christopherson
2019-10-22 15:30 ` Paolo Bonzini
2019-10-22 15:52 ` Sean Christopherson
2019-10-22 15:53 ` Paolo Bonzini
2019-10-24 19:38 ` Sean Christopherson
2019-10-24 19:42 ` Sean Christopherson
2019-10-24 20:24 ` Paolo Bonzini
2019-10-24 20:48 ` Sean Christopherson
2019-10-22 0:35 ` [PATCH v2 15/15] KVM: Dynamically size memslot array based on number of used slots Sean Christopherson
2019-10-22 14:04 ` Paolo Bonzini
2019-10-22 15:22 ` Sean Christopherson
2019-10-22 13:59 ` [PATCH v2 00/15] KVM: Dynamically size memslot arrays Paolo Bonzini
2019-10-23 18:56 ` Christian Borntraeger
2019-10-22 14:04 ` Paolo Bonzini
2019-10-23 9:39 ` Christoffer Dall
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=20191022003537.13013-15-sean.j.christopherson@intel.com \
--to=sean.j.christopherson@intel.com \
--cc=borntraeger@de.ibm.com \
--cc=cohuck@redhat.com \
--cc=david@redhat.com \
--cc=frankja@linux.ibm.com \
--cc=james.morse@arm.com \
--cc=jhogan@kernel.org \
--cc=jmattson@google.com \
--cc=joro@8bytes.org \
--cc=julien.thierry.kdev@gmail.com \
--cc=kvm-ppc@vger.kernel.org \
--cc=kvm@vger.kernel.org \
--cc=kvmarm@lists.cs.columbia.edu \
--cc=linux-arm-kernel@lists.infradead.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mips@vger.kernel.org \
--cc=maz@kernel.org \
--cc=paulus@ozlabs.org \
--cc=pbonzini@redhat.com \
--cc=rkrcmar@redhat.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).