| Message ID | 1384370613-6433-6-git-send-email-mst@redhat.com |
|---|---|
| State | New |
| Headers | show |
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.
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.
On 11/14/2013 04:40 PM, Michael S. Tsirkin wrote: > 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. Not much value in combining them -- the variable level tree check will be dominated by the level skip logic. IMO however skipping intermediate levels will be too rare to justify the complexity and the doubling of the page table size -- it can only happen in iommu setups that place memory in very high addresses. These ought to be rare.
On Thu, Nov 14, 2013 at 04:56:43PM +0200, Avi Kivity wrote: > On 11/14/2013 04:40 PM, Michael S. Tsirkin wrote: > >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. > > Not much value in combining them -- the variable level tree check > will be dominated by the level skip logic. > > IMO however skipping intermediate levels will be too rare to justify > the complexity and the doubling of the page table size -- it can > only happen in iommu setups that place memory in very high > addresses. These ought to be rare. > Well maybe not very high address, but you can have a device with a 64 bit bar and this will add back levels (though it would not be slower than it is currently). I agree the simplicity is attractive. However I really would like some logic that can handle > 1 leaf somehow. Specifically both tricks break if we add a full 64 bit io region in order to return -1 for reads on master abort.
On 11/14/2013 05:37 PM, Michael S. Tsirkin wrote: > On Thu, Nov 14, 2013 at 04:56:43PM +0200, Avi Kivity wrote: >> On 11/14/2013 04:40 PM, Michael S. Tsirkin wrote: >>> 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. >> Not much value in combining them -- the variable level tree check >> will be dominated by the level skip logic. >> >> IMO however skipping intermediate levels will be too rare to justify >> the complexity and the doubling of the page table size -- it can >> only happen in iommu setups that place memory in very high >> addresses. These ought to be rare. >> > Well maybe not very high address, but you can have a device with > a 64 bit bar and this will add back levels (though it would not > be slower than it is currently). > > I agree the simplicity is attractive. > > However I really would like some logic that can handle > 1 leaf > somehow. > > Specifically both tricks break if we add a full 64 bit io region > in order to return -1 for reads on master abort. That can be achieved by directing a missed lookup to a catch-all region. It would be best to do this completely internally to the memory code, without API changes.
On Thu, Nov 14, 2013 at 05:42:26PM +0200, Avi Kivity wrote: > On 11/14/2013 05:37 PM, Michael S. Tsirkin wrote: > >On Thu, Nov 14, 2013 at 04:56:43PM +0200, Avi Kivity wrote: > >>On 11/14/2013 04:40 PM, Michael S. Tsirkin wrote: > >>>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. > >>Not much value in combining them -- the variable level tree check > >>will be dominated by the level skip logic. > >> > >>IMO however skipping intermediate levels will be too rare to justify > >>the complexity and the doubling of the page table size -- it can > >>only happen in iommu setups that place memory in very high > >>addresses. These ought to be rare. > >> > >Well maybe not very high address, but you can have a device with > >a 64 bit bar and this will add back levels (though it would not > >be slower than it is currently). > > > >I agree the simplicity is attractive. > > > >However I really would like some logic that can handle > 1 leaf > >somehow. > > > >Specifically both tricks break if we add a full 64 bit io region > >in order to return -1 for reads on master abort. > > That can be achieved by directing a missed lookup to a catch-all region. > > It would be best to do this completely internally to the memory > code, without API changes. You mean e.g. add a catch-all region to the address space?
On 11/17/2013 05:37 PM, Michael S. Tsirkin wrote: > On Thu, Nov 14, 2013 at 05:42:26PM +0200, Avi Kivity wrote: >> On 11/14/2013 05:37 PM, Michael S. Tsirkin wrote: >>> On Thu, Nov 14, 2013 at 04:56:43PM +0200, Avi Kivity wrote: >>>> On 11/14/2013 04:40 PM, Michael S. Tsirkin wrote: >>>>> 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. >>>> Not much value in combining them -- the variable level tree check >>>> will be dominated by the level skip logic. >>>> >>>> IMO however skipping intermediate levels will be too rare to justify >>>> the complexity and the doubling of the page table size -- it can >>>> only happen in iommu setups that place memory in very high >>>> addresses. These ought to be rare. >>>> >>> Well maybe not very high address, but you can have a device with >>> a 64 bit bar and this will add back levels (though it would not >>> be slower than it is currently). >>> >>> I agree the simplicity is attractive. >>> >>> However I really would like some logic that can handle > 1 leaf >>> somehow. >>> >>> Specifically both tricks break if we add a full 64 bit io region >>> in order to return -1 for reads on master abort. >> That can be achieved by directing a missed lookup to a catch-all region. >> >> It would be best to do this completely internally to the memory >> code, without API changes. > You mean e.g. add a catch-all region to the address space? > The API already specifies a catch-all region - the container region catches everything if an access doesn't hit a sub-region (though I wanted to discourage the practice of using the same region for both I/O and a container), or you can have an I/O region as a subregion with the lowest priority, that spans the entire space, so that any access which misses the other sub-regions will hit the default subregion. So we don't need API changes, just to change the internals. I think this can be done by looking at the address space, and finding out what region is mapped to the very last byte in the address space, if any, and using that as the default if an access misses the tree. That is, this region will be the target of null pointers in the tree, or if (addr & addr_invalid_mask) is true. This will ensure the tree is of the smallest possible size. Another option is to simply give up on the tree and use std::binary_search() on the FlatView. It will be more cpu intensive, but on the other hand more cache-friendly. tcg already caches stuff in the iotlb, and maybe it makes sense to add a cache for kvm lookups too (the advantage of the cache is that it only needs to contain addresses that are actually touched, so it can be very small and fast, compared to the radix tree which needs to cover all addresses).
diff --git a/exec.c b/exec.c index edb577f..474d80d 100644 --- a/exec.c +++ b/exec.c @@ -51,6 +51,8 @@ #include "exec/memory-internal.h" +#include "qemu/range.h" + //#define DEBUG_SUBPAGE #if !defined(CONFIG_USER_ONLY) @@ -216,6 +218,68 @@ static void phys_page_set(AddressSpaceDispatch *d, phys_page_set_level(&d->phys_map, &index, &nb, leaf, P_L2_LEVELS - 1); } +/* Compact a non leaf page entry. Simply detect that the entry has a single child, + * and update our entry so we can skip it and go directly to the destination. + */ +static void phys_page_compact(PhysPageEntry *lp, Node *nodes, unsigned long *compacted) +{ + unsigned valid_ptr = P_L2_SIZE; + int valid = 0; + PhysPageEntry *p; + int i; + + if (lp->ptr == PHYS_MAP_NODE_NIL) { + return; + } + + p = nodes[lp->ptr]; + for (i = 0; i < P_L2_SIZE; i++) { + if (p[i].ptr == PHYS_MAP_NODE_NIL) { + continue; + } + + valid_ptr = i; + valid++; + if (p[i].skip) { + phys_page_compact(&p[i], nodes, compacted); + } + } + + /* We can only compress if there's only one child. */ + if (valid != 1) { + return; + } + + assert(valid_ptr < P_L2_SIZE); + + /* Don't compress if it won't fit in the # of bits we have. */ + if (lp->skip + p[valid_ptr].skip >= (1 << 3)) { + return; + } + + lp->ptr = p[valid_ptr].ptr; + if (!p[valid_ptr].skip) { + /* If our only child is a leaf, make this a leaf. */ + /* By design, we should have made this node a leaf to begin with so we + * should never reach here. + * But since it's so simple to handle this, let's do it just in case we + * change this rule. + */ + lp->skip = 0; + } else { + lp->skip += p[valid_ptr].skip; + } +} + +static void phys_page_compact_all(AddressSpaceDispatch *d, int nodes_nb) +{ + DECLARE_BITMAP(compacted, nodes_nb); + + if (d->phys_map.skip) { + phys_page_compact(&d->phys_map, d->nodes, compacted); + } +} + static MemoryRegionSection *phys_page_find(PhysPageEntry lp, hwaddr addr, Node *nodes, MemoryRegionSection *sections) { @@ -230,7 +294,14 @@ static MemoryRegionSection *phys_page_find(PhysPageEntry lp, hwaddr addr, p = nodes[lp.ptr]; lp = p[(index >> (i * P_L2_BITS)) & (P_L2_SIZE - 1)]; } - return §ions[lp.ptr]; + + if (sections[lp.ptr].size.hi || + range_covers_byte(sections[lp.ptr].offset_within_address_space, + sections[lp.ptr].size.lo, addr)) { + return §ions[lp.ptr]; + } else { + return §ions[PHYS_SECTION_UNASSIGNED]; + } } bool memory_region_is_unassigned(MemoryRegion *mr) @@ -1659,6 +1730,8 @@ static void mem_commit(MemoryListener *listener) next->nodes = next_map.nodes; next->sections = next_map.sections; + phys_page_compact_all(next, next_map.nodes_nb); + as->dispatch = next; g_free(cur); }
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. Signed-off-by: Michael S. Tsirkin <mst@redhat.com> --- exec.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 74 insertions(+), 1 deletion(-)