Re: [RFC PATCH 1/3] iommu/iova: convert from rbtree to maple tree

[Rik van Riel <riel@surriel.com>]

On Thu, 2026-09-24 at 16:26 +0100, Robin Murphy wrote:
> On 18/08/2026 4:25 pm, Rik van Riel wrote:
> > alloc_iova() looks for free space by walking the rbtree linearly.
> > On production workloads at Meta, enough CPUs have ended up in that
> > walk
> > at the same time to trigger soft lockups.
> > 
> > Index the iova ranges in a maple tree instead. Its gap search makes
> > alloc_iova() O(log n).
> > 
> > __alloc_and_insert_iova_range() asks mas_empty_area_rev() for the
> > highest free range below limit_pfn. Alignment is handled by
> > rounding
> > up the allocation size, prioritizing speed over address space
> > waste,
> > with the thought that many iova requests on a system will be
> > similar
> > in size, and reuse the same holes.
> [...]
> >   static int __alloc_and_insert_iova_range(struct iova_domain
> > *iovad,
> >   		unsigned long size, unsigned long limit_pfn,
> >   			struct iova *new, bool size_aligned)
> >   {
> > -	struct rb_node *curr, *prev;
> > -	struct iova *curr_iova;
> >   	unsigned long flags;
> > -	unsigned long new_pfn, retry_pfn;
> > +	unsigned long new_pfn;
> >   	unsigned long align_mask = ~0UL;
> > -	unsigned long high_pfn = limit_pfn, low_pfn = iovad-
> > >start_pfn;
> > +	unsigned long search_size = size;
> > +	MA_STATE(mas, &iovad->mtree, 0, 0);
> > +
> > +	if (size_aligned) {
> > +		unsigned long align = 1UL << fls_long(size - 1);
> >   
> > -	if (size_aligned)
> >   		align_mask <<= fls_long(size - 1);
> > +		search_size = size + align - 1;
> > +	}
> 
> Perhaps it's a bit too much of a cool trick, but I think technically
> we 
> could just do "search_size = size + ~align_mask" unconditionally.
> 
> However, either way I do worry somewhat about the increase in 
> fragmentation and premature failures once the space starts to fill
> up. 
> 
For that use case, I am guessing what we really
want to propagate up the tree is not the maximum
size of a gap, but the maximum power of two size
gap that is also aligned to its own size.

In other words, if we have something like this,
aligned 8, we propagate up a gap size 4:

used used used used gap gap gap gap

But if the usage looks like this, at the same
alignment to the start, we propagate a gap size 2:

used used used gap gap gap gap used

That would allow us to easily find gaps aligned
to their own size. Once the size 2 gap is filled
in, we propagate up the remaining size 1 gaps.

That makes me wonder if we need to go back to
the augmented rbtree, instead of using the
maple tree?


Just let me know your preference.
> 
> > -	/* Walk the tree backwards */
> > -	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
> 
> FWIW I'm not much of a fan of the implicit scoped-cleanup stuff in 
> general, but this seems like an instance where using guard() to
> simplify 
> all the early returns might be worthwhile.

I'm happy to do that.

Are there any other changes I should be making
to get this code ready for merging?

-- 
All Rights Reversed.