From mboxrd@z Thu Jan 1 00:00:00 1970 From: Marcelo Tosatti Subject: Re: [PATCH v3 06/15] KVM: MMU: redesign the algorithm of pte_list Date: Mon, 18 Nov 2013 22:48:13 -0200 Message-ID: <20131119004812.GA22049@amt.cnet> References: <1382534973-13197-1-git-send-email-xiaoguangrong@linux.vnet.ibm.com> <1382534973-13197-7-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: gleb@redhat.com, avi.kivity@gmail.com, pbonzini@redhat.com, linux-kernel@vger.kernel.org, kvm@vger.kernel.org To: Xiao Guangrong Return-path: Content-Disposition: inline In-Reply-To: <1382534973-13197-7-git-send-email-xiaoguangrong@linux.vnet.ibm.com> Sender: linux-kernel-owner@vger.kernel.org List-Id: kvm.vger.kernel.org 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 >=20 > 2) always move the entry in the first desc to the the position we wan= t > to remove when delete a spte in the parent_ptes/rmap =EF=BC=88back= ward-move). > It is good for us to implement lockless rmap walk since in the cur= rent > 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 on= e, the > replaced one is missed when we do lockless walk. > To fix this case, we do not backward move the spte, instead, we fo= rward > move the entry: when a spte is deleted, we move the entry in the f= irst > desc to that position >=20 > Both of these also can reduce cache miss >=20 > Signed-off-by: Xiao Guangrong Reviewed-by: Marcelo Tosatti