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