[PATCH v5.5 24/30] KVM: Use interval tree to do fast hva lookup in memslots

[Maciej S. Szmigiero]

On 04.11.2021 01:25, Sean Christopherson wrote:
> From: Maciej S. Szmigiero <maciej.szmigiero at oracle.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 at oracle.com>
> [sean: handle interval tree updates in kvm_replace_memslot()]
> Signed-off-by: Sean Christopherson <seanjc at google.com>
> ---
>   arch/arm64/kvm/Kconfig   |  1 +
>   arch/mips/kvm/Kconfig    |  1 +
>   arch/powerpc/kvm/Kconfig |  1 +
>   arch/s390/kvm/Kconfig    |  1 +
>   arch/x86/kvm/Kconfig     |  1 +
>   include/linux/kvm_host.h |  3 ++
>   virt/kvm/kvm_main.c      | 60 +++++++++++++++++++++++++++++-----------
>   7 files changed, 52 insertions(+), 16 deletions(-)
> 
(..)
> @@ -1262,22 +1274,32 @@ static void kvm_replace_memslot(struct kvm_memslots *slots,
>   				struct kvm_memory_slot *new)
>   {
>   	/*
> -	 * Remove the old memslot from the hash list, copying the node data
> -	 * would corrupt the list.
> +	 * Remove the old memslot from the hash list and interval tree, copying
> +	 * the node data would corrupt the structures.
>   	 */
>   	if (old) {
>   		hash_del(&old->id_node);
> +		interval_tree_remove(&old->hva_node, &slots->hva_tree);
>   
>   		if (!new)
>   			return;
>   	}
>   
> -	/* Copy the source *data*, not the pointer, to the destination. */
> -	if (old)
> +	/*
> +	 * Copy the source *data*, not the pointer, to the destination.  If
> +	 * @old is NULL, initialize @new's hva range.
> +	 */
> +	if (old) {
>   		*new = *old;
> +	} else if (new) {

Unnecessary check - if "new" is NULL then the code will crash anyway
accessing this pointer unconditionally...

> +		new->hva_node.start = new->userspace_addr;
> +		new->hva_node.last = new->userspace_addr +
> +				     (new->npages << PAGE_SHIFT) - 1;
> +	}
>   
>   	/* (Re)Add the new memslot. */
>   	hash_add(slots->id_hash, &new->id_node, new->id);
> +	interval_tree_insert(&new->hva_node, &slots->hva_tree);

...in these two lines above.

Thanks,
Maciej