From mboxrd@z Thu Jan 1 00:00:00 1970 From: Xiao Guangrong Subject: [PATCH v3 06/15] KVM: MMU: redesign the algorithm of pte_list Date: Wed, 23 Oct 2013 21:29:24 +0800 Message-ID: <1382534973-13197-7-git-send-email-xiaoguangrong@linux.vnet.ibm.com> References: <1382534973-13197-1-git-send-email-xiaoguangrong@linux.vnet.ibm.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: avi.kivity@gmail.com, mtosatti@redhat.com, pbonzini@redhat.com, linux-kernel@vger.kernel.org, kvm@vger.kernel.org, Xiao Guangrong To: gleb@redhat.com Return-path: In-Reply-To: <1382534973-13197-1-git-send-email-xiaoguangrong@linux.vnet.ibm.com> Sender: linux-kernel-owner@vger.kernel.org List-Id: kvm.vger.kernel.org Change the algorithm to: 1) always add new desc to the first desc (pointed by parent_ptes/rmap) that is good to implement rcu-nulls-list-like lockless rmap walking 2) always move the entry in the first desc to the the position we want to remove when delete a spte in the parent_ptes/rmap =EF=BC=88backwa= rd-move). It is good for us to implement lockless rmap walk since in the curre= nt code, when a spte is deleted from the "desc", another spte in the la= st "desc" will be moved to this position to replace the deleted one. If= the deleted one has been accessed and we do not access the replaced one,= the replaced one is missed when we do lockless walk. To fix this case, we do not backward move the spte, instead, we forw= ard move the entry: when a spte is deleted, we move the entry in the fir= st desc to that position Both of these also can reduce cache miss Signed-off-by: Xiao Guangrong --- arch/x86/kvm/mmu.c | 179 ++++++++++++++++++++++++++++++++++++---------= -------- 1 file changed, 123 insertions(+), 56 deletions(-) diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c index e85eed6..5cce039 100644 --- a/arch/x86/kvm/mmu.c +++ b/arch/x86/kvm/mmu.c @@ -913,6 +913,50 @@ static int mapping_level(struct kvm_vcpu *vcpu, gf= n_t large_gfn) return level - 1; } =20 +static int __find_first_free(struct pte_list_desc *desc) +{ + int i; + + for (i =3D 0; i < PTE_LIST_EXT; i++) + if (!desc->sptes[i]) + break; + return i; +} + +static int find_first_free(struct pte_list_desc *desc) +{ + int free =3D __find_first_free(desc); + + WARN_ON(free >=3D PTE_LIST_EXT); + return free; +} + +static int find_last_used(struct pte_list_desc *desc) +{ + int used =3D __find_first_free(desc) - 1; + + WARN_ON(used < 0 || used >=3D PTE_LIST_EXT); + return used; +} + +/* + * TODO: we can encode the desc number into the rmap/parent_ptes + * since at least 10 physical/virtual address bits are reserved + * on x86. It is worthwhile if it shows that the desc walking is + * a performance issue. + */ +static int count_spte_number(struct pte_list_desc *desc) +{ + int first_free, desc_num; + + first_free =3D __find_first_free(desc); + + for (desc_num =3D 0; desc->more; desc =3D desc->more) + desc_num++; + + return first_free + desc_num * PTE_LIST_EXT; +} + /* * Pte mapping structures: * @@ -923,98 +967,121 @@ static int mapping_level(struct kvm_vcpu *vcpu, = gfn_t large_gfn) * * Returns the number of pte entries before the spte was added or zero= if * the spte was not added. - * */ static int pte_list_add(struct kvm_vcpu *vcpu, u64 *spte, unsigned long *pte_list) { struct pte_list_desc *desc; - int i, count =3D 0; + int free_pos; =20 if (!*pte_list) { rmap_printk("pte_list_add: %p %llx 0->1\n", spte, *spte); *pte_list =3D (unsigned long)spte; - } else if (!(*pte_list & 1)) { + return 0; + } + + if (!(*pte_list & 1)) { rmap_printk("pte_list_add: %p %llx 1->many\n", spte, *spte); desc =3D mmu_alloc_pte_list_desc(vcpu); desc->sptes[0] =3D (u64 *)*pte_list; desc->sptes[1] =3D spte; *pte_list =3D (unsigned long)desc | 1; - ++count; - } else { - rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); - desc =3D (struct pte_list_desc *)(*pte_list & ~1ul); - while (desc->sptes[PTE_LIST_EXT-1] && desc->more) { - desc =3D desc->more; - count +=3D PTE_LIST_EXT; - } - if (desc->sptes[PTE_LIST_EXT-1]) { - desc->more =3D mmu_alloc_pte_list_desc(vcpu); - desc =3D desc->more; - } - for (i =3D 0; desc->sptes[i]; ++i) - ++count; - desc->sptes[i] =3D spte; + return 1; } - return count; + + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); + desc =3D (struct pte_list_desc *)(*pte_list & ~1ul); + + /* No empty entry in the desc. */ + if (desc->sptes[PTE_LIST_EXT - 1]) { + struct pte_list_desc *new_desc; + new_desc =3D mmu_alloc_pte_list_desc(vcpu); + new_desc->more =3D desc; + desc =3D new_desc; + *pte_list =3D (unsigned long)desc | 1; + } + + free_pos =3D find_first_free(desc); + desc->sptes[free_pos] =3D spte; + return count_spte_number(desc) - 1; } =20 static void -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_de= sc *desc, - int i, struct pte_list_desc *prev_desc) +pte_list_desc_remove_entry(unsigned long *pte_list, + struct pte_list_desc *desc, int i) { - int j; + struct pte_list_desc *first_desc; + int last_used; =20 - for (j =3D PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) - ; - desc->sptes[i] =3D desc->sptes[j]; - desc->sptes[j] =3D NULL; - if (j !=3D 0) + first_desc =3D (struct pte_list_desc *)(*pte_list & ~1ul); + last_used =3D find_last_used(first_desc); + + /* + * Move the entry from the first desc to this position we want + * to remove. + */ + desc->sptes[i] =3D first_desc->sptes[last_used]; + first_desc->sptes[last_used] =3D NULL; + + /* No valid entry in this desc, we can free this desc now. */ + if (!first_desc->sptes[0]) { + struct pte_list_desc *next_desc =3D first_desc->more; + + /* + * Only one entry existing but still use a desc to store it? + */ + WARN_ON(!next_desc); + + mmu_free_pte_list_desc(first_desc); + *pte_list =3D (unsigned long)next_desc | 1ul; return; - if (!prev_desc && !desc->more) - *pte_list =3D (unsigned long)desc->sptes[0]; - else - if (prev_desc) - prev_desc->more =3D desc->more; - else - *pte_list =3D (unsigned long)desc->more | 1; - mmu_free_pte_list_desc(desc); + } + + /* + * Only one entry in this desc, move the entry to the head + * then the desc can be freed. + */ + if (!first_desc->sptes[1] && !first_desc->more) { + *pte_list =3D (unsigned long)first_desc->sptes[0]; + mmu_free_pte_list_desc(first_desc); + } } =20 static void pte_list_remove(u64 *spte, unsigned long *pte_list) { struct pte_list_desc *desc; - struct pte_list_desc *prev_desc; int i; =20 if (!*pte_list) { - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); + pr_err("pte_list_remove: %p 0->BUG\n", spte); BUG(); - } else if (!(*pte_list & 1)) { + return; + } + + if (!(*pte_list & 1)) { rmap_printk("pte_list_remove: %p 1->0\n", spte); if ((u64 *)*pte_list !=3D spte) { - printk(KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); + pr_err("pte_list_remove: %p 1->BUG\n", spte); BUG(); } *pte_list =3D 0; - } else { - rmap_printk("pte_list_remove: %p many->many\n", spte); - desc =3D (struct pte_list_desc *)(*pte_list & ~1ul); - prev_desc =3D NULL; - while (desc) { - for (i =3D 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) - if (desc->sptes[i] =3D=3D spte) { - pte_list_desc_remove_entry(pte_list, - desc, i, - prev_desc); - return; - } - prev_desc =3D desc; - desc =3D desc->more; - } - pr_err("pte_list_remove: %p many->many\n", spte); - BUG(); + return; } + + rmap_printk("pte_list_remove: %p many->many\n", spte); + desc =3D (struct pte_list_desc *)(*pte_list & ~1ul); + while (desc) { + for (i =3D 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) + if (desc->sptes[i] =3D=3D spte) { + pte_list_desc_remove_entry(pte_list, + desc, i); + return; + } + desc =3D desc->more; + } + + pr_err("pte_list_remove: %p many->many\n", spte); + BUG(); } =20 typedef void (*pte_list_walk_fn) (u64 *spte); --=20 1.8.1.4