Re: [PATCH 2/2] iommu/iova: Improve restart logic

[Robin Murphy]

On 2021-03-18 11:38, John Garry wrote:
> On 10/03/2021 17:47, John Garry wrote:
> > On 09/03/2021 15:55, John Garry wrote:
> > > On 05/03/2021 16:35, Robin Murphy wrote:
> > >
> > > Hi Robin,
> > >
> > > > When restarting after searching below the cached node fails, resetting
> > > > the start point to the anchor node is often overly pessimistic. If
> > > > allocations are made with mixed limits - particularly in the case of 
> > > > the
> > > > opportunistic 32-bit allocation for PCI devices - this could mean
> > > > significant time wasted walking through the whole populated upper range
> > > > just to reach the initial limit. 
> > >
> > > Right
> > >
> > > > We can improve on that by implementing
> > > > a proper tree traversal to find the first node above the relevant 
> > > > limit,
> > > > and set the exact start point.
> > >
> > > Thanks for this. However, as mentioned in the other thread, this does 
> > > not help our performance regression Re: commit 4e89dce72521.
> > >
> > > And mentioning this "retry" approach again, in case it was missed, 
> > > from my experiment on the affected HW, it also has generally a 
> > > dreadfully low success rate - less than 1% for the 32b range retry. 
> > > Retry rate is about 20%. So I am saying from this 20%, less than 1% 
> > > of those succeed.

Well yeah, in your particular case you're allocating from a heavily 
over-contended address space, so much of the time it is genuinely full. 
Plus you're primarily churning one or two sizes of IOVA, so there's a 
high chance that you will either allocate immediately from the cached 
node (after a previous free), or search the whole space and fail. In 
case it was missed, searching only some arbitrary subset of the space 
before giving up is not a good behaviour for an allocator to have in 
general.

> > So since the retry means that we search through the complete pfn range 
> > most of the time (due to poor success rate), we should be able to do a 
> > better job at maintaining an accurate max alloc size, by calculating 
> > it from the range search, and not relying on max alloc failed or 
> > resetting it frequently. Hopefully that would mean that we're smarter 
> > about not trying the allocation.
>
> So I tried that out and we seem to be able to scrap back an appreciable 
> amount of performance. Maybe 80% of original, with with another change, 
> below.

TBH if you really want to make allocation more efficient I think there 
are more radical changes that would be worth experimenting with, like 
using some form of augmented rbtree to also encode the amount of free 
space under each branch, or representing the free space in its own 
parallel tree, or whether some other structure entirely might be a 
better bet these days.

And if you just want to make your thing acceptably fast, now I'm going 
to say stick a quirk somewhere to force the "forcedac" option on your 
platform ;)

[...]
> > > > @@ -219,7 +256,7 @@ static int __alloc_and_insert_iova_range(struct 
> > > > iova_domain *iovad,
> > > >           if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
> > > >               high_pfn = limit_pfn;
> > > >               low_pfn = retry_pfn;
> > > > -            curr = &iovad->anchor.node;
> > > > +            curr = iova_find_limit(iovad, limit_pfn);
>
>
> I see that it is now applied. However, alternatively could we just add a 
> zero-length 32b boundary marker node for the 32b pfn restart point?

That would need special cases all over the place to prevent the marker 
getting merged into reservations or hit by lookups, and at worst break 
the ordering of the tree if a legitimate node straddles the boundary. I 
did consider having the insert/delete routines keep track of yet another 
cached node for whatever's currently the first thing above the 32-bit 
boundary, but I was worried that might be a bit too invasive.

FWIW I'm currently planning to come back to this again when I have a bit 
more time, since the optimum thing to do (modulo replacing the entire 
algorithm...) is actually to make the second part of the search 
*upwards* from the cached node to the limit. Furthermore, to revive my 
arch/arm conversion I think we're realistically going to need a 
compatibility option for bottom-up allocation to avoid too many nasty 
surprises, so I'd like to generalise things to tackle both concerns at once.

Thanks,
Robin.