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: Sat, 30 Oct 2021 00:32:02 +0000 [thread overview]
Message-ID: <YXySglMHYhHHVxm/@google.com> (raw)
In-Reply-To: <4156d889-5320-ff78-9898-e065d8554c7d@maciej.szmigiero.name>
On Fri, Oct 29, 2021, Maciej S. Szmigiero wrote:
> On 28.10.2021 19:53, Sean Christopherson wrote:
> > 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
>
> As you say, that's rather unpleasant, since we know that the first
> returned memslot is the only one that's possibly *not* overlapping
> (and then it only happens sometimes).
> Yet with the above change we'll pay the price of this check for every
> loop iteration (for every returned memslot).
I'm definitely not saying that it's the best/right/only way to handle this,
merely pointing out that it's not _that_ complex, modulo off-by-one bugs :-)
> That's definitely not optimizing for the most common case.
Meh, it's a nop for kvm_check_memslot_overlap() and completely in the noise for
kvm_zap_gfn_range(). Not saying I disagree that's a flawed way to handle this
just saying that even the quick-and-dirty solution is extremely unlikely to be
relevant to performance.
> Also, the above code has a bug - using a [start, end) notation compatible
> with what kvm_for_each_memslot_in_gfn_range() expects, where [1, 4)
> means a range consisting of { 1, 2, 3 }, consider a tree consisting of the
> following two memslots: [1, 2), [3, 5)
>
> When kvm_for_each_memslot_in_gfn_range() is then called to "return"
> memslots overlapping range [2, 4) it will "return" the [1, 2) memslot, too -
> even though it does *not* actually overlap the requested range.
>
> While this bug is easy to fix (just use "<=" instead of "<") it serves to
> underline that one has to be very careful with working with this type of
> code as it is very easy to introduce subtle mistakes here.
Yes, and that's exactly why I want to write this _once_.
> > 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.
>
> What kind of future users of this API do you envision?
>
> I've pointed out above that adding this extra check means essentially
> optimizing for an uncommon case.
Usage similar to kvm_zap_gfn_range() where KVM wants to take action on a specific
gfn range. I'm actually somewhat surprised that none of the other architectures
have a use case in their MMUs, though I don't know the story for things like
shadow paging that "necessitate" x86's behavior.
> One of the callers of this function already has the necessary code to
> reject non-overlapping memslots and have to keep it to calculate the
> effective overlapping range for each memslot.
> For the second caller (which, by the way, is called much less often than
> kvm_zap_gfn_range()) it's a matter of one extra condition.
>
> > > 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. :-)
> >
>
> If you absolutely insist then obviously I can change the code to return
> only memslots strictly overlapping the requested range in the next
> patchset version.
I feel pretty strongly that the risk vs. reward is heavily in favor of returning
only strictly overlapping memslots. The risk being that a few years down the road
someone runs afoul of this and we end up with a bug in production. The reward is
avoiding writing moderately complex code and at best shave a few uops in an x86
slooow path. It's entirely possible there's never a third user, but IMO there
isn't enough reward to justify even the smallest amount of risk.
Paolo, any opinion?
next prev parent reply other threads:[~2021-10-30 0:32 UTC|newest]
Thread overview: 53+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-20 21:38 [PATCH v5 00/13] KVM: Scalable memslots implementation Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 01/13] KVM: x86: Cache total page count to avoid traversing the memslot array Maciej S. Szmigiero
2021-10-19 22:24 ` Sean Christopherson
2021-10-19 22:31 ` Sean Christopherson
2021-10-20 18:40 ` Maciej S. Szmigiero
2021-10-20 18:41 ` Maciej S. Szmigiero
2021-10-20 19:01 ` Sean Christopherson
2021-11-01 22:29 ` Sean Christopherson
2021-11-03 11:59 ` Maciej S. Szmigiero
2021-11-03 14:47 ` Sean Christopherson
2021-11-03 15:38 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 02/13] KVM: x86: Don't call kvm_mmu_change_mmu_pages() if the count hasn't changed Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 03/13] KVM: Add "old" memslot parameter to kvm_arch_prepare_memory_region() Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 04/13] KVM: x86: Move n_memslots_pages recalc " Maciej S. Szmigiero
2021-10-19 22:38 ` Sean Christopherson
2021-10-20 18:41 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 05/13] KVM: Integrate gfn_to_memslot_approx() into search_memslots() Maciej S. Szmigiero
2021-10-19 23:38 ` Sean Christopherson
2021-10-20 18:41 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 06/13] KVM: Move WARN on invalid memslot index to update_memslots() Maciej S. Szmigiero
2021-10-19 23:42 ` Sean Christopherson
2021-09-20 21:38 ` [PATCH v5 07/13] KVM: Just resync arch fields when slots_arch_lock gets reacquired Maciej S. Szmigiero
2021-10-19 23:55 ` Sean Christopherson
2021-10-20 18:41 ` Maciej S. Szmigiero
2021-10-20 18:57 ` Sean Christopherson
2021-10-20 18:58 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 08/13] KVM: Resolve memslot ID via a hash table instead of via a static array Maciej S. Szmigiero
2021-10-20 0:43 ` Sean Christopherson
2021-10-20 18:42 ` Maciej S. Szmigiero
2021-10-20 22:39 ` Sean Christopherson
2021-10-21 14:15 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 09/13] KVM: Use interval tree to do fast hva lookup in memslots Maciej S. Szmigiero
2021-10-26 18:19 ` Sean Christopherson
2021-10-26 18:46 ` Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 10/13] KVM: s390: Introduce kvm_s390_get_gfn_end() Maciej S. Szmigiero
2021-09-20 21:38 ` [PATCH v5 11/13] KVM: Keep memslots in tree-based structures instead of array-based ones Maciej S. Szmigiero
2021-10-27 0:36 ` Sean Christopherson
2021-10-27 23:54 ` Sean Christopherson
2021-10-28 22:22 ` Sean Christopherson
2021-09-20 21:39 ` [PATCH v5 12/13] KVM: Optimize gfn lookup in kvm_zap_gfn_range() Maciej S. Szmigiero
2021-10-20 23:47 ` Sean Christopherson
2021-10-21 14:16 ` Maciej S. Szmigiero
2021-10-21 16:30 ` Sean Christopherson
2021-10-21 21:44 ` Maciej S. Szmigiero
2021-09-20 21:39 ` [PATCH v5 13/13] KVM: Optimize overlapping memslots check Maciej S. Szmigiero
2021-10-26 18:59 ` Sean Christopherson
2021-10-27 13:48 ` Maciej S. Szmigiero
2021-10-28 17:53 ` Sean Christopherson
2021-10-29 16:23 ` Maciej S. Szmigiero
2021-10-30 0:32 ` Sean Christopherson [this message]
2021-10-19 22:07 ` [PATCH v5 00/13] KVM: Scalable memslots implementation Sean Christopherson
2021-10-20 18:40 ` Maciej S. Szmigiero
2021-10-20 19:58 ` Sean Christopherson
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=YXySglMHYhHHVxm/@google.com \
--to=seanjc@google.com \
--cc=aleksandar.qemu.devel@gmail.com \
--cc=borntraeger@de.ibm.com \
--cc=chenhuacai@kernel.org \
--cc=cohuck@redhat.com \
--cc=david@redhat.com \
--cc=frankja@linux.ibm.com \
--cc=imammedo@redhat.com \
--cc=imbrenda@linux.ibm.com \
--cc=james.morse@arm.com \
--cc=jmattson@google.com \
--cc=joro@8bytes.org \
--cc=julien.thierry.kdev@gmail.com \
--cc=kvm@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mail@maciej.szmigiero.name \
--cc=maz@kernel.org \
--cc=paulus@ozlabs.org \
--cc=pbonzini@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).