Re: [PATCH v3 06/15] KVM: MMU: redesign the algorithm of pte_list

Marcelo Tosatti
2013-11-19T01:07:42Z

On Wed, Oct 23, 2013 at 09:29:24PM +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 the first desc to the the position we want
> to remove when delete 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>

Reviewed-by: Marcelo Tosatti <mtosatti@redhat.com>