From mboxrd@z Thu Jan 1 00:00:00 1970 From: Avi Kivity Subject: Re: [PATCH 2/3] KVM: MMU: Improve iteration over sptes linked by rmap Date: Thu, 15 Mar 2012 11:44:52 +0200 Message-ID: <4F61BA14.4070305@redhat.com> References: <20120315181856.2ced0a28.yoshikawa.takuya@oss.ntt.co.jp> <20120315182038.329d5ad7.yoshikawa.takuya@oss.ntt.co.jp> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Cc: mtosatti@redhat.com, kvm@vger.kernel.org To: Takuya Yoshikawa Return-path: Received: from mx1.redhat.com ([209.132.183.28]:57685 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1760955Ab2COJo4 (ORCPT ); Thu, 15 Mar 2012 05:44:56 -0400 In-Reply-To: <20120315182038.329d5ad7.yoshikawa.takuya@oss.ntt.co.jp> Sender: kvm-owner@vger.kernel.org List-ID: 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 > --- > 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