Re: [PATCH v5 13/13] KVM: Optimize overlapping memslots check

From: Sean Christopherson <seanjc@google.com>
To: "Maciej S. Szmigiero" <mail@maciej.szmigiero.name>
Cc: Paolo Bonzini <pbonzini@redhat.com>,
	Vitaly Kuznetsov <vkuznets@redhat.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: Re: [PATCH v5 13/13] KVM: Optimize overlapping memslots check
Date: Thu, 28 Oct 2021 17:53:33 +0000	[thread overview]
Message-ID: <YXrjnSKBhzG7JVLF@google.com> (raw)
In-Reply-To: <4222ead3-f80f-0992-569f-9e1a7adbabcc@maciej.szmigiero.name>

On Wed, Oct 27, 2021, Maciej S. Szmigiero wrote:
> On 26.10.2021 20:59, Sean Christopherson wrote:
> > > +		/* kvm_for_each_in_gfn_no_more() guarantees that cslot->base_gfn < nend */
> > > +		if (cend > nslot->base_gfn)
> > 
> > Hmm, IMO the need for this check means that kvm_for_each_memslot_in_gfn_range()
> > is flawed.  The user of kvm_for_each...() should not be responsible for skipping
> > memslots that do not actually overlap the requested range.  I.e. this function
> > should be no more than:
> > 
> > static bool kvm_check_memslot_overlap(struct kvm_memslots *slots,
> > 				      struct kvm_memory_slot *slot)
> > {
> > 	gfn_t start = slot->base_gfn;
> > 	gfn_t end = start + slot->npages;
> > 
> > 	kvm_for_each_memslot_in_gfn_range(&iter, slots, start, end) {
> > 		if (iter.slot->id != slot->id)
> > 			return true;
> > 	}
> > 
> > 	return false;
> > }
> > 
> > 
> > and I suspect kvm_zap_gfn_range() could be further simplified as well.
> > 
> > Looking back at the introduction of the helper, its comment's highlighting of
> > "possibily" now makes sense.
> > 
> >    /* Iterate over each memslot *possibly* intersecting [start, end) range */
> >    #define kvm_for_each_memslot_in_gfn_range(node, slots, start, end)	\
> > 
> > That's an unnecessarily bad API.  It's a very solvable problem for the iterator
> > helpers to advance until there's actually overlap, not doing so violates the
> > principle of least surprise, and unless I'm missing something, there's no use
> > case for an "approximate" iteration.
> 
> In principle this can be done, however this will complicate the gfn
> iterator logic - especially the kvm_memslot_iter_start() part, which
> will already get messier from open-coding kvm_memslots_gfn_upper_bound()
> there.

Hmm, no, this is trivial to handle, though admittedly a bit unpleasant.

/*
 * Note, kvm_memslot_iter_start() finds the first memslot that _may_ overlap
 * the range, it does not verify that there is actual overlap.  The check in
 * the loop body filters out the case where the highest memslot with a base_gfn
 * below start doesn't actually overlap.
 */
#define kvm_for_each_memslot_in_gfn_range(iter, node, slots, start, end) \
        for (kvm_memslot_iter_start(iter, node, slots, start, end);      \
             kvm_memslot_iter_is_valid(iter);                            \
             kvm_memslot_iter_next(node))                                \
		if (iter->slot->base_gfn + iter->slot->npages < start) { \
		} else

> At the same kvm_zap_gfn_range() will still need to do the memslot range
> <-> request range merging by itself as it does not want to process the
> whole returned memslot, but rather just the part that's actually
> overlapping its requested range.

That's purely coincidental though.  IMO, kvm_zap_gfn_range() would be well within
its rights to sanity the memslot, e.g.

	if (WARN_ON(memslot->base_gfn + memslot->npages < gfn_start))
		continue;

> In the worst case, the current code can return one memslot too much, so
> I don't think it's worth bringing additional complexity just to detect
> and skip it

I strongly disagree.  This is very much a case of one chunk of code that knows
the internal details of what it's doing taking on all the pain and complexity
so that users of the helper

> it's not that uncommon to design an API that needs extra checking from its
> caller to cover some corner cases.

That doesn't mean it's desirable.

> For example, see pthread_cond_wait() or kernel waitqueues with their
> spurious wakeups or atomic_compare_exchange_weak() from C11.
> And these are higher level APIs than a very limited internal KVM one
> with just two callers.

Two _existing_ callers.  Odds are very, very high that future usage of
kvm_for_each_memslot_in_gfn_range() will overlook the detail about the helper
not actually doing what it says it does.  That could be addressed to some extent
by renaming it kvm_for_each_memslot_in_gfn_range_approx() or whatever, but as
above this isn't difficult to handle, just gross.

> In case of kvm_zap_gfn_range() the necessary checking is already
> there and has to be kept due to the above range merging.
> 
> Also, a code that is simpler is easier to understand, maintain and
> so less prone to subtle bugs.

Heh, and IMO that's an argument for putting all the complexity into a single
location.  :-)