Received: from eggs.gnu.org ([2001:4830:134:3::10]:43041) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Vgsmc-0001hq-1H for qemu-devel@nongnu.org; Thu, 14 Nov 2013 04:00:21 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VgsmU-0000TE-OO for qemu-devel@nongnu.org; Thu, 14 Nov 2013 04:00:13 -0500 Received: from plane.gmane.org ([80.91.229.3]:52193) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VgsmU-0000QU-Hn for qemu-devel@nongnu.org; Thu, 14 Nov 2013 04:00:06 -0500 Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1VgsmS-0002qJ-B7 for qemu-devel@nongnu.org; Thu, 14 Nov 2013 10:00:04 +0100 Received: from IGLD-84-229-225-122.inter.net.il ([84.229.225.122]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 14 Nov 2013 10:00:04 +0100 Received: from avi by IGLD-84-229-225-122.inter.net.il with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 14 Nov 2013 10:00:04 +0100 From: Avi Kivity Date: Thu, 14 Nov 2013 08:54:11 +0000 (UTC) Message-ID: References: <1384370613-6433-1-git-send-email-mst@redhat.com> <1384370613-6433-6-git-send-email-mst@redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] =?utf-8?q?=5BPATCH_v2_5/7=5D_exec=3A_memory_radix_tr?= =?utf-8?q?ee_page_level=09compression?= List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Michael S. Tsirkin redhat.com> writes: > > At the moment, memory radix tree is already variable width, but it can > only skip the low bits of address. > > This is efficient if we have huge memory regions but inefficient if we > are only using a tiny portion of the address space. > > After we have built up the map, detect > configurations where a single L2 entry is valid. > > We then speed up the lookup by skipping one or more levels. > In case any levels were skipped, we might end up in a valid section > instead of erroring out. We handle this by checking that > the address is in range of the resulting section. > I think this is overkill. It can be done in a simpler way as follows: phys_page_find(RadixTree* tr, hwaddr index, ...) { if (index & rt->invalid_index_mask) { // not found } lp = rt->root; for (i = rt->nb_levels - 1; i >= 0 && !lp.is_leaf; --i) { ... This exploits the fact the lower portion of the address space is always filled, at least in the cases that matter to us.