Re: [PATCH 2/3] KVM: MMU: Improve iteration over sptes linked by rmap

[Avi Kivity <avi@redhat.com>]

On 03/15/2012 11:20 AM, Takuya Yoshikawa wrote:
> Iteration using rmap_next(), the actual body is pte_list_next(), is
> inefficient: every time we call it we start from checking whether rmap
> holds a single spte or points to a descriptor which links more sptes.
>
> In the case of shadow paging, this quadratic total iteration cost is a
> problem.  Even for two dimensional paging, with EPT/NPT on, in which we
> almost always have a single spte, the extra checks at the end of the
> iteration should be eliminated.
>
> This patch fixes this by introducing rmap_iterator which keeps the
> iteration context for the next search.  Furthermore the implementation
> of rmap_next() is splitted into two functions - rmap_get_first() and
> rmap_get_next() - to avoid repeatedly checking whether the rmap being
> iterated on has only one spte.
>
> Note: we just remove pte_list_next() because we can think of parent_ptes
> as a reverse mapping.
>
> Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
> ---
>  arch/x86/kvm/mmu.c       |  198 ++++++++++++++++++++++++++++------------------
>  arch/x86/kvm/mmu_audit.c |    8 +-
>  2 files changed, 124 insertions(+), 82 deletions(-)
>
> diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
> index 384d3c0..d042087 100644
> --- a/arch/x86/kvm/mmu.c
> +++ b/arch/x86/kvm/mmu.c
> @@ -842,32 +842,6 @@ static int pte_list_add(struct kvm_vcpu *vcpu, u64 *spte,
>  	return count;
>  }
>  
> -static u64 *pte_list_next(unsigned long *pte_list, u64 *spte)
> -{
> -	struct pte_list_desc *desc;
> -	u64 *prev_spte;
> -	int i;
> -
> -	if (!*pte_list)
> -		return NULL;
> -	else if (!(*pte_list & 1)) {
> -		if (!spte)
> -			return (u64 *)*pte_list;
> -		return NULL;
> -	}
> -	desc = (struct pte_list_desc *)(*pte_list & ~1ul);
> -	prev_spte = NULL;
> -	while (desc) {
> -		for (i = 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) {
> -			if (prev_spte == spte)
> -				return desc->sptes[i];
> -			prev_spte = desc->sptes[i];
> -		}
> -		desc = desc->more;
> -	}
> -	return NULL;
> -}
> -
>  static void
>  pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *desc,
>  			   int i, struct pte_list_desc *prev_desc)
> @@ -988,11 +962,6 @@ static int rmap_add(struct kvm_vcpu *vcpu, u64 *spte, gfn_t gfn)
>  	return pte_list_add(vcpu, spte, rmapp);
>  }
>  
> -static u64 *rmap_next(unsigned long *rmapp, u64 *spte)
> -{
> -	return pte_list_next(rmapp, spte);
> -}
> -
>  static void rmap_remove(struct kvm *kvm, u64 *spte)
>  {
>  	struct kvm_mmu_page *sp;
> @@ -1005,6 +974,72 @@ static void rmap_remove(struct kvm *kvm, u64 *spte)
>  	pte_list_remove(spte, rmapp);
>  }
>  
> +/*
> + * Used by the following functions to iterate over the sptes linked by a rmap.
> + * Only sptep can be used outside of these functions.
> + */
> +struct rmap_iterator {
> +	u64 *sptep;			/* points to the current spte */
> +	/* private fields */
> +	struct pte_list_desc *desc;	/* holds the sptep if not NULL */
> +	int pos;			/* index of the sptep */
> +};
> +
> +/*
> + * Iteration must be started by this function.  This should also be used after
> + * removing/dropping sptes from rmap because in such cases the information in
> + * the itererator may not be valid.

Note: this suggests rmap_remove(struct rmap_iterator *ri) to remove an
rmap from the iterator while keeping it valid.  Converts a potentially
quadratic kvm_mmu_rmap_write_protect() to linear.

> + *
> + * Returns true if spte is found, false otherwise.
> + */
> +static bool rmap_get_first(unsigned long rmap, struct rmap_iterator *iter)
> +{
> +	if (!rmap) {
> +		iter->sptep = NULL;
> +		return false;
> +	}
> +
> +	if (!(rmap & 1)) {
> +		iter->sptep = (u64 *)rmap;
> +		iter->desc = NULL;
> +	} else {
> +		iter->desc = (struct pte_list_desc *)(rmap & ~1ul);
> +		iter->pos = 0;
> +		iter->sptep = iter->desc->sptes[iter->pos];
> +	}
> +
> +	return true;
> +}

Might be simplified to return the sptep or NULL; so you don't have to
copy it to the iterator.


-- 
error compiling committee.c: too many arguments to function