From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([2001:4830:134:3::10]:56083)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <mst@redhat.com>) id 1Vgy3F-0000SZ-Qj
	for qemu-devel@nongnu.org; Thu, 14 Nov 2013 09:37:51 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <mst@redhat.com>) id 1Vgy39-0002N4-R6
	for qemu-devel@nongnu.org; Thu, 14 Nov 2013 09:37:45 -0500
Received: from mx1.redhat.com ([209.132.183.28]:38363)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <mst@redhat.com>) id 1Vgy39-0002My-It
	for qemu-devel@nongnu.org; Thu, 14 Nov 2013 09:37:39 -0500
Date: Thu, 14 Nov 2013 16:40:37 +0200
From: "Michael S. Tsirkin" <mst@redhat.com>
Message-ID: <20131114144037.GA6635@redhat.com>
References: <1384370613-6433-1-git-send-email-mst@redhat.com>
	<1384370613-6433-6-git-send-email-mst@redhat.com>
	<loom.20131114T094304-721@post.gmane.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <loom.20131114T094304-721@post.gmane.org>
Subject: Re: [Qemu-devel] [PATCH v2 5/7] exec: memory radix tree page
 level?compression
List-Id: <qemu-devel.nongnu.org>
List-Unsubscribe: <https://lists.nongnu.org/mailman/options/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <https://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: Avi Kivity <avi@cloudius-systems.com>
Cc: qemu-devel@nongnu.org

On Thu, Nov 14, 2013 at 08:54:11AM +0000, Avi Kivity wrote:
> Michael S. Tsirkin <mst <at> 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.
> 
> 
> 
> 
> 

Basically skip unused high bits?
Sure.
In fact I think both optimizations can be combined.

-- 
MST