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@xxxxxxxxxxxxx>
> ---
> 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
--
To unsubscribe from this list: send the line "unsubscribe kvm" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
