| Message ID | 38333ef36e7812e1b9f9d24e726ca632997a8ef1.1621191552.git.maciej.szmigiero@oracle.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | KVM: Scalable memslots implementation | expand |
On Sun, May 16, 2021, Maciej S. Szmigiero wrote: > From: "Maciej S. Szmigiero" <maciej.szmigiero@oracle.com> > > Introduce a memslots gfn upper bound operation and use it to optimize > kvm_zap_gfn_range(). > This way this handler can do a quick lookup for intersecting gfns and won't > have to do a linear scan of the whole memslot set. > > Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@oracle.com> > --- > arch/x86/kvm/mmu/mmu.c | 41 ++++++++++++++++++++++++++++++++++++++-- > include/linux/kvm_host.h | 22 +++++++++++++++++++++ > 2 files changed, 61 insertions(+), 2 deletions(-) > > diff --git a/arch/x86/kvm/mmu/mmu.c b/arch/x86/kvm/mmu/mmu.c > index 7222b552d139..f23398cf0316 100644 > --- a/arch/x86/kvm/mmu/mmu.c > +++ b/arch/x86/kvm/mmu/mmu.c > @@ -5490,14 +5490,51 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end) > int i; > bool flush = false; > > + if (gfn_end == gfn_start || WARN_ON(gfn_end < gfn_start)) > + return; > + > write_lock(&kvm->mmu_lock); > for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) { > - int ctr; > + int idxactive; > + struct rb_node *node; > > slots = __kvm_memslots(kvm, i); > - kvm_for_each_memslot(memslot, ctr, slots) { > + idxactive = kvm_memslots_idx(slots); > + > + /* > + * 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, gfn_start); > + 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 > range start. > + */ > + pnode = rb_prev(node); > + if (pnode) > + node = pnode; > + } else { > + /* a NULL node below means no slots */ > + node = rb_last(&slots->gfn_tree); > + } > + > + for ( ; node; node = rb_next(node)) { > gfn_t start, end; Can this be abstracted into something like: kvm_for_each_memslot_in_gfn_range(...) { } and share that implementation with kvm_check_memslot_overlap() in the next patch? I really don't think arch code should be poking into gfn_tree, and ideally arch code wouldn't even be aware that gfn_tree exists. > + memslot = container_of(node, struct kvm_memory_slot, > + gfn_node[idxactive]); > + > + /* > + * If this slot starts beyond or at the end of the range so does > + * every next one > + */ > + if (memslot->base_gfn >= gfn_start + gfn_end) > + break; > + > start = max(gfn_start, memslot->base_gfn); > end = min(gfn_end, memslot->base_gfn + memslot->npages); > if (start >= end)
On 26.05.2021 19:33, Sean Christopherson wrote: > On Sun, May 16, 2021, Maciej S. Szmigiero wrote: >> From: "Maciej S. Szmigiero" <maciej.szmigiero@oracle.com> >> >> Introduce a memslots gfn upper bound operation and use it to optimize >> kvm_zap_gfn_range(). >> This way this handler can do a quick lookup for intersecting gfns and won't >> have to do a linear scan of the whole memslot set. >> >> Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@oracle.com> >> --- >> arch/x86/kvm/mmu/mmu.c | 41 ++++++++++++++++++++++++++++++++++++++-- >> include/linux/kvm_host.h | 22 +++++++++++++++++++++ >> 2 files changed, 61 insertions(+), 2 deletions(-) >> >> diff --git a/arch/x86/kvm/mmu/mmu.c b/arch/x86/kvm/mmu/mmu.c >> index 7222b552d139..f23398cf0316 100644 >> --- a/arch/x86/kvm/mmu/mmu.c >> +++ b/arch/x86/kvm/mmu/mmu.c >> @@ -5490,14 +5490,51 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end) >> int i; >> bool flush = false; >> >> + if (gfn_end == gfn_start || WARN_ON(gfn_end < gfn_start)) >> + return; >> + >> write_lock(&kvm->mmu_lock); >> for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) { >> - int ctr; >> + int idxactive; >> + struct rb_node *node; >> >> slots = __kvm_memslots(kvm, i); >> - kvm_for_each_memslot(memslot, ctr, slots) { >> + idxactive = kvm_memslots_idx(slots); >> + >> + /* >> + * 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, gfn_start); >> + 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 > range start. >> + */ >> + pnode = rb_prev(node); >> + if (pnode) >> + node = pnode; >> + } else { >> + /* a NULL node below means no slots */ >> + node = rb_last(&slots->gfn_tree); >> + } >> + >> + for ( ; node; node = rb_next(node)) { >> gfn_t start, end; > > Can this be abstracted into something like: > > kvm_for_each_memslot_in_gfn_range(...) { > > } > > and share that implementation with kvm_check_memslot_overlap() in the next patch? > > I really don't think arch code should be poking into gfn_tree, and ideally arch > code wouldn't even be aware that gfn_tree exists. That's a good idea, will do. Thanks, Maciej
diff --git a/arch/x86/kvm/mmu/mmu.c b/arch/x86/kvm/mmu/mmu.c index 7222b552d139..f23398cf0316 100644 --- a/arch/x86/kvm/mmu/mmu.c +++ b/arch/x86/kvm/mmu/mmu.c @@ -5490,14 +5490,51 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end) int i; bool flush = false; + if (gfn_end == gfn_start || WARN_ON(gfn_end < gfn_start)) + return; + write_lock(&kvm->mmu_lock); for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) { - int ctr; + int idxactive; + struct rb_node *node; slots = __kvm_memslots(kvm, i); - kvm_for_each_memslot(memslot, ctr, slots) { + idxactive = kvm_memslots_idx(slots); + + /* + * 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, gfn_start); + 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 > range start. + */ + pnode = rb_prev(node); + if (pnode) + node = pnode; + } else { + /* a NULL node below means no slots */ + node = rb_last(&slots->gfn_tree); + } + + for ( ; node; node = rb_next(node)) { gfn_t start, end; + memslot = container_of(node, struct kvm_memory_slot, + gfn_node[idxactive]); + + /* + * If this slot starts beyond or at the end of the range so does + * every next one + */ + if (memslot->base_gfn >= gfn_start + gfn_end) + break; + start = max(gfn_start, memslot->base_gfn); end = min(gfn_end, memslot->base_gfn + memslot->npages); if (start >= end) diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h index a9c5b0df2311..fd88e971eef2 100644 --- a/include/linux/kvm_host.h +++ b/include/linux/kvm_host.h @@ -709,6 +709,28 @@ 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) +{ + int idxactive = kvm_memslots_idx(slots); + struct rb_node *node, *result = NULL; + + for (node = slots->gfn_tree.rb_node; node; ) { + struct kvm_memory_slot *slot; + + slot = container_of(node, struct kvm_memory_slot, + gfn_node[idxactive]); + if (gfn < slot->base_gfn) { + result = node; + node = node->rb_left; + } else + node = node->rb_right; + } + + return result; +} + /* * KVM_SET_USER_MEMORY_REGION ioctl allows the following operations: * - create a new memory slot