[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <YXhGo/FpqUAuz7Td@google.com>
Date: Tue, 26 Oct 2021 18:19:15 +0000
From: Sean Christopherson <seanjc@...gle.com>
To: "Maciej S. Szmigiero" <mail@...iej.szmigiero.name>
Cc: Paolo Bonzini <pbonzini@...hat.com>,
Vitaly Kuznetsov <vkuznets@...hat.com>,
Wanpeng Li <wanpengli@...cent.com>,
Jim Mattson <jmattson@...gle.com>,
Igor Mammedov <imammedo@...hat.com>,
Marc Zyngier <maz@...nel.org>,
James Morse <james.morse@....com>,
Julien Thierry <julien.thierry.kdev@...il.com>,
Suzuki K Poulose <suzuki.poulose@....com>,
Huacai Chen <chenhuacai@...nel.org>,
Aleksandar Markovic <aleksandar.qemu.devel@...il.com>,
Paul Mackerras <paulus@...abs.org>,
Christian Borntraeger <borntraeger@...ibm.com>,
Janosch Frank <frankja@...ux.ibm.com>,
David Hildenbrand <david@...hat.com>,
Cornelia Huck <cohuck@...hat.com>,
Claudio Imbrenda <imbrenda@...ux.ibm.com>,
Joerg Roedel <joro@...tes.org>, kvm@...r.kernel.org,
linux-kernel@...r.kernel.org
Subject: Re: [PATCH v5 09/13] KVM: Use interval tree to do fast hva lookup in
memslots
On Mon, Sep 20, 2021, Maciej S. Szmigiero wrote:
> From: "Maciej S. Szmigiero" <maciej.szmigiero@...cle.com>
>
> The current memslots implementation only allows quick binary search by gfn,
> quick lookup by hva is not possible - the implementation has to do a linear
> scan of the whole memslots array, even though the operation being performed
> might apply just to a single memslot.
>
> This significantly hurts performance of per-hva operations with higher
> memslot counts.
>
> Since hva ranges can overlap between memslots an interval tree is needed
> for tracking them.
>
> Signed-off-by: Maciej S. Szmigiero <maciej.szmigiero@...cle.com>
> ---
> diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> index 50597608d085..7ed780996910 100644
> --- a/virt/kvm/kvm_main.c
> +++ b/virt/kvm/kvm_main.c
> @@ -472,6 +472,12 @@ static void kvm_null_fn(void)
> }
> #define IS_KVM_NULL_FN(fn) ((fn) == (void *)kvm_null_fn)
>
> +/* Iterate over each memslot intersecting [start, last] (inclusive) range */
> +#define kvm_for_each_memslot_in_hva_range(node, slots, start, last) \
> + for (node = interval_tree_iter_first(&slots->hva_tree, start, last); \
> + node; \
> + node = interval_tree_iter_next(node, start, last)) \
Similar to kvm_for_each_memslot_in_gfn_range(), this should use an opaque iterator
to hide the implementation details from the caller, e.g. to avoid having to define
a "struct interval_tree_node" and do container_of.
Powered by blists - more mailing lists