| Message ID | 1375189330-24066-8-git-send-email-xiaoguangrong@linux.vnet.ibm.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Tue, Jul 30, 2013 at 09:02:05PM +0800, Xiao Guangrong wrote: > 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 first desc to the the position we want > to remove when remove a spte in the parent_ptes/rmap ?backward-move). > It is good for us to implement lockless rmap walk since in the current > code, when a spte is deleted from the "desc", another spte in the last > "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 forward > move the entry: when a spte is deleted, we move the entry in the first > desc to that position > > Both of these also can reduce cache miss > > Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com> > --- > arch/x86/kvm/mmu.c | 182 ++++++++++++++++++++++++++++++++++++----------------- > 1 file changed, 125 insertions(+), 57 deletions(-) > > diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c > index 5a40564..3013bb1 100644 > --- a/arch/x86/kvm/mmu.c > +++ b/arch/x86/kvm/mmu.c > @@ -918,6 +918,50 @@ static int mapping_level(struct kvm_vcpu *vcpu, gfn_t large_gfn) > return level - 1; > } > > +static int __find_first_free(struct pte_list_desc *desc) > +{ > + int i; > + > + for (i = 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 = __find_first_free(desc); > + > + WARN_ON(free >= PTE_LIST_EXT); > + return free; > +} > + > +static int find_last_used(struct pte_list_desc *desc) > +{ > + int used = __find_first_free(desc) - 1; > + > + WARN_ON(used < 0 || used >= 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 = __find_first_free(desc); > + > + for (desc_num = 0; desc->more; desc = desc->more) > + desc_num++; > + > + return first_free + desc_num * PTE_LIST_EXT; > +} > + > /* > * Pte mapping structures: > * > @@ -934,92 +978,116 @@ static int pte_list_add(struct kvm_vcpu *vcpu, u64 *spte, > unsigned long *pte_list) > { > struct pte_list_desc *desc; > - int i, count = 0; > + int free_pos; > > if (!*pte_list) { > rmap_printk("pte_list_add: %p %llx 0->1\n", spte, *spte); > *pte_list = (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 = mmu_alloc_pte_list_desc(vcpu); > desc->sptes[0] = (u64 *)*pte_list; > desc->sptes[1] = spte; > *pte_list = (unsigned long)desc | 1; > - ++count; > - } else { > - rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); > - desc = (struct pte_list_desc *)(*pte_list & ~1ul); > - while (desc->sptes[PTE_LIST_EXT-1] && desc->more) { > - desc = desc->more; > - count += PTE_LIST_EXT; > - } > - if (desc->sptes[PTE_LIST_EXT-1]) { > - desc->more = mmu_alloc_pte_list_desc(vcpu); > - desc = desc->more; > - } > - for (i = 0; desc->sptes[i]; ++i) > - ++count; > - desc->sptes[i] = spte; > + return 1; > + } > + > + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); > + desc = (struct pte_list_desc *)(*pte_list & ~1ul); > + > + /* No empty position in the desc. */ > + if (desc->sptes[PTE_LIST_EXT - 1]) { > + struct pte_list_desc *new_desc; > + new_desc = mmu_alloc_pte_list_desc(vcpu); > + new_desc->more = desc; > + desc = new_desc; > + *pte_list = (unsigned long)desc | 1; > } > - return count; > + > + free_pos = find_first_free(desc); > + desc->sptes[free_pos] = spte; > + return count_spte_number(desc); Should it be count_spte_number(desc) - 1? The function should returns the number of pte entries before the spte was added. > } > > static void > -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *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; > + > + first_desc = (struct pte_list_desc *)(*pte_list & ~1ul); > + last_used = find_last_used(first_desc); > > - for (j = PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) > - ; > - desc->sptes[i] = desc->sptes[j]; > - desc->sptes[j] = NULL; > - if (j != 0) > + /* > + * Move the entry from the first desc to this position we want > + * to remove. > + */ > + desc->sptes[i] = first_desc->sptes[last_used]; > + first_desc->sptes[last_used] = NULL; > + What if desc == first_desc and i < last_used. You still move spte backwards so lockless walk may have already examined entry at i and will miss spte that was moved there from last_used position, no? > + /* No valid entry in this desc, we can free this desc now. */ > + if (!first_desc->sptes[0]) { > + struct pte_list_desc *next_desc = 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); > + first_desc = next_desc; > + *pte_list = (unsigned long)first_desc | 1ul; > return; > - if (!prev_desc && !desc->more) > - *pte_list = (unsigned long)desc->sptes[0]; > - else > - if (prev_desc) > - prev_desc->more = desc->more; > - else > - *pte_list = (unsigned long)desc->more | 1; > - mmu_free_pte_list_desc(desc); > + } > + > + WARN_ON(!first_desc->sptes[0]); > + > + /* > + * 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 = (unsigned long)first_desc->sptes[0]; > + mmu_free_pte_list_desc(first_desc); > + } > } > > static void pte_list_remove(u64 *spte, unsigned long *pte_list) > { > struct pte_list_desc *desc; > - struct pte_list_desc *prev_desc; > int i; > > if (!*pte_list) { > - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); > - BUG(); > - } else if (!(*pte_list & 1)) { > + WARN(1, KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); Why change BUG() to WARN() here and below? > + return; > + } > + > + if (!(*pte_list & 1)) { > rmap_printk("pte_list_remove: %p 1->0\n", spte); > if ((u64 *)*pte_list != spte) { > - printk(KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); > - BUG(); > + WARN(1, KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); > } Remove {} since only one statement left in the if(). Or better yet why not: WARN ((u64 *)*pte_list != spte, ....)? But again why not BUG()? > *pte_list = 0; > - } else { > - rmap_printk("pte_list_remove: %p many->many\n", spte); > - desc = (struct pte_list_desc *)(*pte_list & ~1ul); > - prev_desc = NULL; > - while (desc) { > - for (i = 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) > - if (desc->sptes[i] == spte) { > - pte_list_desc_remove_entry(pte_list, > - desc, i, > - prev_desc); > - return; > - } > - prev_desc = desc; > - desc = 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 = (struct pte_list_desc *)(*pte_list & ~1ul); > + while (desc) { > + for (i = 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) > + if (desc->sptes[i] == spte) { > + pte_list_desc_remove_entry(pte_list, > + desc, i); > + return; > + } > + desc = desc->more; > + } > + > + WARN(1, "pte_list_remove: %p many->many\n", spte); > } > > typedef void (*pte_list_walk_fn) (u64 *spte); > -- > 1.8.1.4 -- Gleb. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 08/28/2013 04:12 PM, Gleb Natapov wrote: >> + >> + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); >> + desc = (struct pte_list_desc *)(*pte_list & ~1ul); >> + >> + /* No empty position in the desc. */ >> + if (desc->sptes[PTE_LIST_EXT - 1]) { >> + struct pte_list_desc *new_desc; >> + new_desc = mmu_alloc_pte_list_desc(vcpu); >> + new_desc->more = desc; >> + desc = new_desc; >> + *pte_list = (unsigned long)desc | 1; >> } >> - return count; >> + >> + free_pos = find_first_free(desc); >> + desc->sptes[free_pos] = spte; >> + return count_spte_number(desc); > Should it be count_spte_number(desc) - 1? The function should returns > the number of pte entries before the spte was added. Yes. We have handled it count_spte_number(), we count the number like this: return first_free + desc_num * PTE_LIST_EXT; The first_free is indexed from 0. Maybe it is clearer to let count_spte_number() return the real number. > >> } >> >> static void >> -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *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; >> + >> + first_desc = (struct pte_list_desc *)(*pte_list & ~1ul); >> + last_used = find_last_used(first_desc); >> >> - for (j = PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) >> - ; >> - desc->sptes[i] = desc->sptes[j]; >> - desc->sptes[j] = NULL; >> - if (j != 0) >> + /* >> + * Move the entry from the first desc to this position we want >> + * to remove. >> + */ >> + desc->sptes[i] = first_desc->sptes[last_used]; >> + first_desc->sptes[last_used] = NULL; >> + > What if desc == first_desc and i < last_used. You still move spte > backwards so lockless walk may have already examined entry at i and > will miss spte that was moved there from last_used position, no? Right. I noticed it too and fixed in the v2 which is being tested. I fixed it by bottom-up walk desc, like this: pte_list_walk_lockless(): desc = (struct pte_list_desc *)(pte_list_value & ~1ul); while (!desc_is_a_nulls(desc)) { /* * We should do bottom-up walk since we always use the * bottom entry to replace the deleted entry if only * one desc is used in the rmap when a spte is removed. * Otherwise the moved entry will be missed. */ for (i = PTE_LIST_EXT - 1; i >= 0; i--) fn(desc->sptes[i]); desc = ACCESS_ONCE(desc->more); /* It is being initialized. */ if (unlikely(!desc)) goto restart; } How about this? > >> + /* No valid entry in this desc, we can free this desc now. */ >> + if (!first_desc->sptes[0]) { >> + struct pte_list_desc *next_desc = 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); >> + first_desc = next_desc; >> + *pte_list = (unsigned long)first_desc | 1ul; >> return; >> - if (!prev_desc && !desc->more) >> - *pte_list = (unsigned long)desc->sptes[0]; >> - else >> - if (prev_desc) >> - prev_desc->more = desc->more; >> - else >> - *pte_list = (unsigned long)desc->more | 1; >> - mmu_free_pte_list_desc(desc); >> + } >> + >> + WARN_ON(!first_desc->sptes[0]); >> + >> + /* >> + * 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 = (unsigned long)first_desc->sptes[0]; >> + mmu_free_pte_list_desc(first_desc); >> + } >> } >> >> static void pte_list_remove(u64 *spte, unsigned long *pte_list) >> { >> struct pte_list_desc *desc; >> - struct pte_list_desc *prev_desc; >> int i; >> >> if (!*pte_list) { >> - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); >> - BUG(); >> - } else if (!(*pte_list & 1)) { >> + WARN(1, KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); > Why change BUG() to WARN() here and below? WARN(1, "xxx") can replace two lines in the origin code. And personally, i prefer WARN() to BUG() since sometimes BUG() can stop my box and i need to get the full log by using kdump. If you object it, i will change it back in the next version. :) > >> + return; >> + } >> + >> + if (!(*pte_list & 1)) { >> rmap_printk("pte_list_remove: %p 1->0\n", spte); >> if ((u64 *)*pte_list != spte) { >> - printk(KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); >> - BUG(); >> + WARN(1, KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); >> } > Remove {} since only one statement left in the if(). Or better yet why > not: > WARN ((u64 *)*pte_list != spte, ....)? Yes, it is better. > But again why not BUG()? The explanation is above. :) -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Aug 28, 2013 at 04:37:32PM +0800, Xiao Guangrong wrote: > On 08/28/2013 04:12 PM, Gleb Natapov wrote: > > >> + > >> + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); > >> + desc = (struct pte_list_desc *)(*pte_list & ~1ul); > >> + > >> + /* No empty position in the desc. */ > >> + if (desc->sptes[PTE_LIST_EXT - 1]) { > >> + struct pte_list_desc *new_desc; > >> + new_desc = mmu_alloc_pte_list_desc(vcpu); > >> + new_desc->more = desc; > >> + desc = new_desc; > >> + *pte_list = (unsigned long)desc | 1; > >> } > >> - return count; > >> + > >> + free_pos = find_first_free(desc); > >> + desc->sptes[free_pos] = spte; > >> + return count_spte_number(desc); > > Should it be count_spte_number(desc) - 1? The function should returns > > the number of pte entries before the spte was added. > > Yes. We have handled it count_spte_number(), we count the number like this: > > return first_free + desc_num * PTE_LIST_EXT; > > The first_free is indexed from 0. > Suppose when pte_list_add() is called there is one full desc, so the number that should be returned is PTE_LIST_EXT, correct? But since before calling count_spte_number() one more desc will be added and desc->sptes[0] will be set in it the first_free in count_spte_number will be 1 and PTE_LIST_EXT + 1 will be returned. > Maybe it is clearer to let count_spte_number() return the real number. > > > > >> } > >> > >> static void > >> -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *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; > >> + > >> + first_desc = (struct pte_list_desc *)(*pte_list & ~1ul); > >> + last_used = find_last_used(first_desc); > >> > >> - for (j = PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) > >> - ; > >> - desc->sptes[i] = desc->sptes[j]; > >> - desc->sptes[j] = NULL; > >> - if (j != 0) > >> + /* > >> + * Move the entry from the first desc to this position we want > >> + * to remove. > >> + */ > >> + desc->sptes[i] = first_desc->sptes[last_used]; > >> + first_desc->sptes[last_used] = NULL; > >> + > > What if desc == first_desc and i < last_used. You still move spte > > backwards so lockless walk may have already examined entry at i and > > will miss spte that was moved there from last_used position, no? > > Right. I noticed it too and fixed in the v2 which is being tested. > I fixed it by bottom-up walk desc, like this: > > pte_list_walk_lockless(): > > desc = (struct pte_list_desc *)(pte_list_value & ~1ul); > while (!desc_is_a_nulls(desc)) { > /* > * We should do bottom-up walk since we always use the > * bottom entry to replace the deleted entry if only > * one desc is used in the rmap when a spte is removed. > * Otherwise the moved entry will be missed. > */ I would call it top-down walk since we are walking from big indices to smaller once. > for (i = PTE_LIST_EXT - 1; i >= 0; i--) > fn(desc->sptes[i]); > > desc = ACCESS_ONCE(desc->more); > > /* It is being initialized. */ > if (unlikely(!desc)) > goto restart; > } > > How about this? > Tricky, very very tricky :) > > > >> + /* No valid entry in this desc, we can free this desc now. */ > >> + if (!first_desc->sptes[0]) { > >> + struct pte_list_desc *next_desc = 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); > >> + first_desc = next_desc; > >> + *pte_list = (unsigned long)first_desc | 1ul; > >> return; > >> - if (!prev_desc && !desc->more) > >> - *pte_list = (unsigned long)desc->sptes[0]; > >> - else > >> - if (prev_desc) > >> - prev_desc->more = desc->more; > >> - else > >> - *pte_list = (unsigned long)desc->more | 1; > >> - mmu_free_pte_list_desc(desc); > >> + } > >> + > >> + WARN_ON(!first_desc->sptes[0]); > >> + > >> + /* > >> + * 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 = (unsigned long)first_desc->sptes[0]; > >> + mmu_free_pte_list_desc(first_desc); > >> + } > >> } > >> > >> static void pte_list_remove(u64 *spte, unsigned long *pte_list) > >> { > >> struct pte_list_desc *desc; > >> - struct pte_list_desc *prev_desc; > >> int i; > >> > >> if (!*pte_list) { > >> - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); > >> - BUG(); > >> - } else if (!(*pte_list & 1)) { > >> + WARN(1, KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); > > Why change BUG() to WARN() here and below? > > WARN(1, "xxx") can replace two lines in the origin code. And personally, > i prefer WARN() to BUG() since sometimes BUG() can stop my box and i need to > get the full log by using kdump. > > If you object it, i will change it back in the next version. :) > For debugging WARN() is doubtlessly better, but outside of development you do not want to allow kernel to run after serious MMU corruption is detected. It may be exploitable further, we do not know, so the safe choice is to stop the kernel. -- Gleb. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 08/28/2013 04:58 PM, Gleb Natapov wrote: > On Wed, Aug 28, 2013 at 04:37:32PM +0800, Xiao Guangrong wrote: >> On 08/28/2013 04:12 PM, Gleb Natapov wrote: >> >>>> + >>>> + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); >>>> + desc = (struct pte_list_desc *)(*pte_list & ~1ul); >>>> + >>>> + /* No empty position in the desc. */ >>>> + if (desc->sptes[PTE_LIST_EXT - 1]) { >>>> + struct pte_list_desc *new_desc; >>>> + new_desc = mmu_alloc_pte_list_desc(vcpu); >>>> + new_desc->more = desc; >>>> + desc = new_desc; >>>> + *pte_list = (unsigned long)desc | 1; >>>> } >>>> - return count; >>>> + >>>> + free_pos = find_first_free(desc); >>>> + desc->sptes[free_pos] = spte; >>>> + return count_spte_number(desc); >>> Should it be count_spte_number(desc) - 1? The function should returns >>> the number of pte entries before the spte was added. >> >> Yes. We have handled it count_spte_number(), we count the number like this: >> >> return first_free + desc_num * PTE_LIST_EXT; >> >> The first_free is indexed from 0. >> > Suppose when pte_list_add() is called there is one full desc, so the > number that should be returned is PTE_LIST_EXT, correct? But since > before calling count_spte_number() one more desc will be added and > desc->sptes[0] will be set in it the first_free in count_spte_number > will be 1 and PTE_LIST_EXT + 1 will be returned. Oh, yes, you are right. Will fix it in the next version, thanks for you pointing it out. > >> Maybe it is clearer to let count_spte_number() return the real number. >> >>> >>>> } >>>> >>>> static void >>>> -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *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; >>>> + >>>> + first_desc = (struct pte_list_desc *)(*pte_list & ~1ul); >>>> + last_used = find_last_used(first_desc); >>>> >>>> - for (j = PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) >>>> - ; >>>> - desc->sptes[i] = desc->sptes[j]; >>>> - desc->sptes[j] = NULL; >>>> - if (j != 0) >>>> + /* >>>> + * Move the entry from the first desc to this position we want >>>> + * to remove. >>>> + */ >>>> + desc->sptes[i] = first_desc->sptes[last_used]; >>>> + first_desc->sptes[last_used] = NULL; >>>> + >>> What if desc == first_desc and i < last_used. You still move spte >>> backwards so lockless walk may have already examined entry at i and >>> will miss spte that was moved there from last_used position, no? >> >> Right. I noticed it too and fixed in the v2 which is being tested. >> I fixed it by bottom-up walk desc, like this: >> >> pte_list_walk_lockless(): >> >> desc = (struct pte_list_desc *)(pte_list_value & ~1ul); >> while (!desc_is_a_nulls(desc)) { >> /* >> * We should do bottom-up walk since we always use the >> * bottom entry to replace the deleted entry if only >> * one desc is used in the rmap when a spte is removed. >> * Otherwise the moved entry will be missed. >> */ > I would call it top-down walk since we are walking from big indices to > smaller once. Okay, will fix the comments. > >> for (i = PTE_LIST_EXT - 1; i >= 0; i--) >> fn(desc->sptes[i]); >> >> desc = ACCESS_ONCE(desc->more); >> >> /* It is being initialized. */ >> if (unlikely(!desc)) >> goto restart; >> } >> >> How about this? >> > Tricky, very very tricky :) > >>> >>>> + /* No valid entry in this desc, we can free this desc now. */ >>>> + if (!first_desc->sptes[0]) { >>>> + struct pte_list_desc *next_desc = 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); >>>> + first_desc = next_desc; >>>> + *pte_list = (unsigned long)first_desc | 1ul; >>>> return; >>>> - if (!prev_desc && !desc->more) >>>> - *pte_list = (unsigned long)desc->sptes[0]; >>>> - else >>>> - if (prev_desc) >>>> - prev_desc->more = desc->more; >>>> - else >>>> - *pte_list = (unsigned long)desc->more | 1; >>>> - mmu_free_pte_list_desc(desc); >>>> + } >>>> + >>>> + WARN_ON(!first_desc->sptes[0]); >>>> + >>>> + /* >>>> + * 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 = (unsigned long)first_desc->sptes[0]; >>>> + mmu_free_pte_list_desc(first_desc); >>>> + } >>>> } >>>> >>>> static void pte_list_remove(u64 *spte, unsigned long *pte_list) >>>> { >>>> struct pte_list_desc *desc; >>>> - struct pte_list_desc *prev_desc; >>>> int i; >>>> >>>> if (!*pte_list) { >>>> - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); >>>> - BUG(); >>>> - } else if (!(*pte_list & 1)) { >>>> + WARN(1, KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); >>> Why change BUG() to WARN() here and below? >> >> WARN(1, "xxx") can replace two lines in the origin code. And personally, >> i prefer WARN() to BUG() since sometimes BUG() can stop my box and i need to >> get the full log by using kdump. >> >> If you object it, i will change it back in the next version. :) >> > For debugging WARN() is doubtlessly better, but outside of development > you do not want to allow kernel to run after serious MMU corruption is > detected. It may be exploitable further, we do not know, so the safe > choice is to stop the kernel. Okay, will keep BUG() in the next version. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c index 5a40564..3013bb1 100644 --- a/arch/x86/kvm/mmu.c +++ b/arch/x86/kvm/mmu.c @@ -918,6 +918,50 @@ static int mapping_level(struct kvm_vcpu *vcpu, gfn_t large_gfn) return level - 1; } +static int __find_first_free(struct pte_list_desc *desc) +{ + int i; + + for (i = 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 = __find_first_free(desc); + + WARN_ON(free >= PTE_LIST_EXT); + return free; +} + +static int find_last_used(struct pte_list_desc *desc) +{ + int used = __find_first_free(desc) - 1; + + WARN_ON(used < 0 || used >= 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 = __find_first_free(desc); + + for (desc_num = 0; desc->more; desc = desc->more) + desc_num++; + + return first_free + desc_num * PTE_LIST_EXT; +} + /* * Pte mapping structures: * @@ -934,92 +978,116 @@ static int pte_list_add(struct kvm_vcpu *vcpu, u64 *spte, unsigned long *pte_list) { struct pte_list_desc *desc; - int i, count = 0; + int free_pos; if (!*pte_list) { rmap_printk("pte_list_add: %p %llx 0->1\n", spte, *spte); *pte_list = (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 = mmu_alloc_pte_list_desc(vcpu); desc->sptes[0] = (u64 *)*pte_list; desc->sptes[1] = spte; *pte_list = (unsigned long)desc | 1; - ++count; - } else { - rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); - desc = (struct pte_list_desc *)(*pte_list & ~1ul); - while (desc->sptes[PTE_LIST_EXT-1] && desc->more) { - desc = desc->more; - count += PTE_LIST_EXT; - } - if (desc->sptes[PTE_LIST_EXT-1]) { - desc->more = mmu_alloc_pte_list_desc(vcpu); - desc = desc->more; - } - for (i = 0; desc->sptes[i]; ++i) - ++count; - desc->sptes[i] = spte; + return 1; + } + + rmap_printk("pte_list_add: %p %llx many->many\n", spte, *spte); + desc = (struct pte_list_desc *)(*pte_list & ~1ul); + + /* No empty position in the desc. */ + if (desc->sptes[PTE_LIST_EXT - 1]) { + struct pte_list_desc *new_desc; + new_desc = mmu_alloc_pte_list_desc(vcpu); + new_desc->more = desc; + desc = new_desc; + *pte_list = (unsigned long)desc | 1; } - return count; + + free_pos = find_first_free(desc); + desc->sptes[free_pos] = spte; + return count_spte_number(desc); } static void -pte_list_desc_remove_entry(unsigned long *pte_list, struct pte_list_desc *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; + + first_desc = (struct pte_list_desc *)(*pte_list & ~1ul); + last_used = find_last_used(first_desc); - for (j = PTE_LIST_EXT - 1; !desc->sptes[j] && j > i; --j) - ; - desc->sptes[i] = desc->sptes[j]; - desc->sptes[j] = NULL; - if (j != 0) + /* + * Move the entry from the first desc to this position we want + * to remove. + */ + desc->sptes[i] = first_desc->sptes[last_used]; + first_desc->sptes[last_used] = NULL; + + /* No valid entry in this desc, we can free this desc now. */ + if (!first_desc->sptes[0]) { + struct pte_list_desc *next_desc = 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); + first_desc = next_desc; + *pte_list = (unsigned long)first_desc | 1ul; return; - if (!prev_desc && !desc->more) - *pte_list = (unsigned long)desc->sptes[0]; - else - if (prev_desc) - prev_desc->more = desc->more; - else - *pte_list = (unsigned long)desc->more | 1; - mmu_free_pte_list_desc(desc); + } + + WARN_ON(!first_desc->sptes[0]); + + /* + * 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 = (unsigned long)first_desc->sptes[0]; + mmu_free_pte_list_desc(first_desc); + } } static void pte_list_remove(u64 *spte, unsigned long *pte_list) { struct pte_list_desc *desc; - struct pte_list_desc *prev_desc; int i; if (!*pte_list) { - printk(KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); - BUG(); - } else if (!(*pte_list & 1)) { + WARN(1, KERN_ERR "pte_list_remove: %p 0->BUG\n", spte); + return; + } + + if (!(*pte_list & 1)) { rmap_printk("pte_list_remove: %p 1->0\n", spte); if ((u64 *)*pte_list != spte) { - printk(KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); - BUG(); + WARN(1, KERN_ERR "pte_list_remove: %p 1->BUG\n", spte); } *pte_list = 0; - } else { - rmap_printk("pte_list_remove: %p many->many\n", spte); - desc = (struct pte_list_desc *)(*pte_list & ~1ul); - prev_desc = NULL; - while (desc) { - for (i = 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) - if (desc->sptes[i] == spte) { - pte_list_desc_remove_entry(pte_list, - desc, i, - prev_desc); - return; - } - prev_desc = desc; - desc = 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 = (struct pte_list_desc *)(*pte_list & ~1ul); + while (desc) { + for (i = 0; i < PTE_LIST_EXT && desc->sptes[i]; ++i) + if (desc->sptes[i] == spte) { + pte_list_desc_remove_entry(pte_list, + desc, i); + return; + } + desc = desc->more; + } + + WARN(1, "pte_list_remove: %p many->many\n", spte); } typedef void (*pte_list_walk_fn) (u64 *spte);
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 first desc to the the position we want to remove when remove a spte in the parent_ptes/rmap ?backward-move). It is good for us to implement lockless rmap walk since in the current code, when a spte is deleted from the "desc", another spte in the last "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 forward move the entry: when a spte is deleted, we move the entry in the first desc to that position Both of these also can reduce cache miss Signed-off-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com> --- arch/x86/kvm/mmu.c | 182 ++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 125 insertions(+), 57 deletions(-)