Re: [Qemu-devel] [PATCH v2 5/7] exec: memory radix tr ee page level compression

[Avi Kivity]

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.