From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([140.186.70.92]:43640) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RW8Ox-0000pI-Bx for qemu-devel@nongnu.org; Thu, 01 Dec 2011 10:18:25 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RW8Or-00041o-In for qemu-devel@nongnu.org; Thu, 01 Dec 2011 10:18:19 -0500 Received: from mx1.redhat.com ([209.132.183.28]:39969) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RW8Or-00041b-9n for qemu-devel@nongnu.org; Thu, 01 Dec 2011 10:18:13 -0500 Message-ID: <4ED79AAE.8000201@redhat.com> Date: Thu, 01 Dec 2011 17:18:06 +0200 From: Avi Kivity MIME-Version: 1.0 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> In-Reply-To: <4ED5BC03.5000901@oss.ntt.co.jp> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH 0/4] KVM: Dirty logging optimization using rmap List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Takuya Yoshikawa Cc: KVM , quintela@redhat.com, Marcelo Tosatti , qemu-devel@nongnu.org, Xiao Guangrong , Takuya Yoshikawa 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