| Message ID | a39db04edcacfe955c660e2f139f948cf29362f5.1638304316.git.maciej.szmigiero@oracle.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | KVM: Scalable memslots implementation | expand |
On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote: > diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h > index 41efe53cf150..6fce6eb797a7 100644 > --- a/include/linux/kvm_host.h > +++ b/include/linux/kvm_host.h > @@ -848,6 +848,105 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id) > return NULL; > } > > +/* 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 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]); Having to use a helper in callers of kvm_for_each_memslot_in_gfn_range() is a bit ugly, any reason not to grab @slot as well? Then the callers just do iter.slot, which IMO is much more readable. And if we do that, I'd also vote to omit slots and end from the iterator. It would mean passing in slots and end to kvm_memslot_iter_is_valid() and kvm_memslot_iter_next(), but that's more idiomatic in a for-loop if iter is considered to be _just_ the iterator part. "slots" is arguable, but "end" really shouldn't be part of the iterator. > +} > + > +static inline bool kvm_memslot_iter_is_valid(struct kvm_memslot_iter *iter) > +{ > + struct kvm_memory_slot *memslot; > + > + 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 < iter->end; > +} > + > +static inline void kvm_memslot_iter_next(struct kvm_memslot_iter *iter) > +{ > + iter->node = rb_next(iter->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: > * - create a new memory slot
On 01.12.2021 04:41, Sean Christopherson wrote: > On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote: >> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h >> index 41efe53cf150..6fce6eb797a7 100644 >> --- a/include/linux/kvm_host.h >> +++ b/include/linux/kvm_host.h >> @@ -848,6 +848,105 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id) >> return NULL; >> } >> >> +/* 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 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]); > > Having to use a helper in callers of kvm_for_each_memslot_in_gfn_range() is a bit > ugly, any reason not to grab @slot as well? Then the callers just do iter.slot, > which IMO is much more readable. "slot" can be easily calculated from "node" together with either "slots" or "node_idx" (the code above just adjusts a pointer) so storing it in the iterator makes little sense if the later are already stored there. > And if we do that, I'd also vote to omit slots and end from the iterator. It would > mean passing in slots and end to kvm_memslot_iter_is_valid() and kvm_memslot_iter_next(), > but that's more idiomatic in a for-loop if iter is considered to be _just_ the iterator > part. "slots" is arguable, but "end" really shouldn't be part of the iterator. You're right that we can get away with not storing "end", will remove it. Thanks, Maciej
On Wed, Dec 01, 2021, Maciej S. Szmigiero wrote: > On 01.12.2021 04:41, Sean Christopherson wrote: > > On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote: > > > diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h > > > index 41efe53cf150..6fce6eb797a7 100644 > > > --- a/include/linux/kvm_host.h > > > +++ b/include/linux/kvm_host.h > > > @@ -848,6 +848,105 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id) > > > return NULL; > > > } > > > +/* 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 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]); > > > > Having to use a helper in callers of kvm_for_each_memslot_in_gfn_range() is a bit > > ugly, any reason not to grab @slot as well? Then the callers just do iter.slot, > > which IMO is much more readable. > > "slot" can be easily calculated from "node" together with either "slots" or > "node_idx" (the code above just adjusts a pointer) so storing it in the > iterator makes little sense if the later are already stored there. I don't want the callers to have to calculate the slot. It's mostly syntatic sugar, but I really do think it improves readability. And since the first thing every caller will do is retrieve the slot, I see no benefit in forcing the caller to do the work. E.g. in the simple kvm_check_memslot_overlap() usage, iter.slot->id is intuitive and easy to parse, whereas kvm_memslot_iter_slot(&iter)->id is slightly more difficult to parse and raises questions about why a function call is necessary and what the function might be doing. static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id, gfn_t start, gfn_t end) { struct kvm_memslot_iter iter; kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end) { if (iter.slot->id != id) return true; } return false; } vs. static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id, gfn_t start, gfn_t end) { struct kvm_memslot_iter iter; kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end) { if (kvm_memslot_iter_slot(&iter)->id != id) return true; } return false; }
On 01.12.2021 17:36, Sean Christopherson wrote: > On Wed, Dec 01, 2021, Maciej S. Szmigiero wrote: >> On 01.12.2021 04:41, Sean Christopherson wrote: >>> On Tue, Nov 30, 2021, Maciej S. Szmigiero wrote: >>>> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h >>>> index 41efe53cf150..6fce6eb797a7 100644 >>>> --- a/include/linux/kvm_host.h >>>> +++ b/include/linux/kvm_host.h >>>> @@ -848,6 +848,105 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id) >>>> return NULL; >>>> } >>>> +/* 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 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]); >>> >>> Having to use a helper in callers of kvm_for_each_memslot_in_gfn_range() is a bit >>> ugly, any reason not to grab @slot as well? Then the callers just do iter.slot, >>> which IMO is much more readable. >> >> "slot" can be easily calculated from "node" together with either "slots" or >> "node_idx" (the code above just adjusts a pointer) so storing it in the >> iterator makes little sense if the later are already stored there. > > I don't want the callers to have to calculate the slot. It's mostly syntatic > sugar, but I really do think it improves readability. And since the first thing > every caller will do is retrieve the slot, I see no benefit in forcing the caller > to do the work. > > E.g. in the simple kvm_check_memslot_overlap() usage, iter.slot->id is intuitive > and easy to parse, whereas kvm_memslot_iter_slot(&iter)->id is slightly more > difficult to parse and raises questions about why a function call is necessary > and what the function might be doing. Personally, I don't think it's that much less readable, but I will change the code to store "slots" instead (as you wish) since it's the last remaining change - other than Paolo's call whether we should keep or drop the kvm_arch_flush_shadow_memslot()-related patch 25. Thanks, Maciej
diff --git a/arch/x86/kvm/mmu/mmu.c b/arch/x86/kvm/mmu/mmu.c index f5a89942f054..89d34bcfa9c3 100644 --- a/arch/x86/kvm/mmu/mmu.c +++ b/arch/x86/kvm/mmu/mmu.c @@ -5704,19 +5704,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 kvm_memslot_iter iter; bool flush = false; gfn_t start, end; - int i, bkt; + int i; if (!kvm_memslots_have_rmaps(kvm)) return flush; for (i = 0; i < KVM_ADDRESS_SPACE_NUM; i++) { slots = __kvm_memslots(kvm, i); - kvm_for_each_memslot(memslot, bkt, slots) { + + 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, @@ -5737,6 +5740,9 @@ void kvm_zap_gfn_range(struct kvm *kvm, gfn_t gfn_start, gfn_t gfn_end) bool flush; int i; + if (WARN_ON_ONCE(gfn_end <= gfn_start)) + return; + write_lock(&kvm->mmu_lock); kvm_inc_notifier_count(kvm, gfn_start, gfn_end); diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h index 41efe53cf150..6fce6eb797a7 100644 --- a/include/linux/kvm_host.h +++ b/include/linux/kvm_host.h @@ -848,6 +848,105 @@ struct kvm_memory_slot *id_to_memslot(struct kvm_memslots *slots, int id) return NULL; } +/* 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 *tmp; + struct kvm_memory_slot *slot; + + iter->slots = slots; + iter->end = end; + + /* + * 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; + } + } + + /* + * Find the slot with the lowest gfn that can possibly intersect with + * the range, so we'll ideally have slot start <= range start + */ + 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. + */ + tmp = rb_prev(iter->node); + if (tmp) + iter->node = tmp; + } else { + /* a NULL node below means no slots */ + iter->node = rb_last(&slots->gfn_tree); + } + + 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 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; + + 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 < iter->end; +} + +static inline void kvm_memslot_iter_next(struct kvm_memslot_iter *iter) +{ + iter->node = rb_next(iter->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: * - create a new memory slot