From mboxrd@z Thu Jan 1 00:00:00 1970 From: Avi Kivity Subject: Re: [PATCH 0/4] KVM: Dirty logging optimization using rmap Date: Thu, 01 Dec 2011 17:18:06 +0200 Message-ID: <4ED79AAE.8000201@redhat.com> References: <20111114182041.43570cdf.yoshikawa.takuya@oss.ntt.co.jp> <4EC0EC90.1090202@redhat.com> <4EC0F3D3.9090907@oss.ntt.co.jp> <4EC10BFE.7050704@redhat.com> <4EC33C0B.1060807@oss.ntt.co.jp> <4EC37D18.4010609@redhat.com> <4ED4AF43.2040003@linux.vnet.ibm.com> <4ED4B574.8090907@oss.ntt.co.jp> <4ED4BFEB.5010600@redhat.com> <4ED4C85A.5020509@linux.vnet.ibm.com> <4ED4C9A3.50504@redhat.com> <4ED4E626.5010507@redhat.com> <4ED5B8F2.2090804@oss.ntt.co.jp> <4ED5BC03.5000901@oss.ntt.co.jp> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Cc: Xiao Guangrong , Marcelo Tosatti , KVM , quintela@redhat.com, qemu-devel@nongnu.org, Takuya Yoshikawa To: Takuya Yoshikawa Return-path: Received: from mx1.redhat.com ([209.132.183.28]:48985 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754956Ab1LAPSO (ORCPT ); Thu, 1 Dec 2011 10:18:14 -0500 In-Reply-To: <4ED5BC03.5000901@oss.ntt.co.jp> Sender: kvm-owner@vger.kernel.org List-ID: On 11/30/2011 07:15 AM, Takuya Yoshikawa wrote: > (2011/11/30 14:02), Takuya Yoshikawa wrote: > >> IIUC, even though O(1) is O(1) at the timing of GET DIRTY LOG, it >> needs O(N) write >> protections with respect to the total number of dirty pages: >> distributed, but >> actually each page fault, which should be logged, does some write >> protection? > > Sorry, was not precise. It depends on the level, and not completely > distributed. > But I think it is O(N), and the total number of costs will not change > so much, > I guess. That's true. But some applications do require low latency, and the current code can impose a lot of time with the mmu spinlock held. The total amount of work actually increases slightly, from O(N) to O(N log N), but since the tree is so wide, the overhead is small. -- error compiling committee.c: too many arguments to function