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

[Robin Murphy <robin.murphy@arm.com>]

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. 
Say for simplicity we have a start_pfn of 0 and limit_pfn of 4 - with 
the current code we can successfully allocate a size of 1 (to IOVA 3) 
followed by a size of 3 (to IOVA 0), or even in the opposite order for 
the same result, whereas with this workaround we couldn't ever allocate 
the 3 either way if its search_size has to be 7.

AFAIK there are real-world use-cases where the usable IOVA space is 
relatively small compared to the sizes of some of the buffers being 
mapped, such that packing density matters (i.e. media stuff in mobile 
SoCs), so if at all possible it would be good if maple tree itself could 
be improved to support searching for a free range with a particular 
alignment (either explicit, or implied natural alignemnt of the size) 
rather than having to bodge it this way. Unfortunately we also can't 
just relax the general DMA API guarantee that DMA addresses are 
naturally-aligned to the mapping/allocation size, as who knows how many 
devices that might break.

> -	/* 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.

Thanks,
Robin.

> +	spin_lock_irqsave(&iovad->iova_lock, flags);
> +	/* No 32-bit request this large can fit until the hint is cleared. */
>   	if (limit_pfn <= iovad->dma_32bit_pfn &&
>   			size >= iovad->max32_alloc_size)
> -		goto iova32_full;
> -
> -	curr = __get_cached_rbnode(iovad, limit_pfn);
> -	curr_iova = to_iova(curr);
> -	retry_pfn = curr_iova->pfn_hi;
> -
> -retry:
> -	do {
> -		high_pfn = min(high_pfn, curr_iova->pfn_lo);
> -		new_pfn = (high_pfn - size) & align_mask;
> -		prev = curr;
> -		curr = rb_prev(curr);
> -		curr_iova = to_iova(curr);
> -	} while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
> -
> -	if (high_pfn < size || new_pfn < low_pfn) {
> -		if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
> -			high_pfn = limit_pfn;
> -			low_pfn = retry_pfn + 1;
> -			curr = iova_find_limit(iovad, limit_pfn);
> -			curr_iova = to_iova(curr);
> -			goto retry;
> -		}
> -		iovad->max32_alloc_size = size;
> -		goto iova32_full;
> +		goto alloc_fail;
> +
> +	if (mas_empty_area_rev(&mas, iovad->start_pfn,
> +				 limit_pfn - 1, search_size)) {
> +		/* Only real exhaustion sets the hint, not a failed store. */
> +		if (limit_pfn <= iovad->dma_32bit_pfn)
> +			iovad->max32_alloc_size = size;
> +		goto alloc_fail;
>   	}
>   
> -	/* pfn_lo will point to size aligned address if size_aligned is set */
> +	/* The gap is search_size wide, so alignment cannot pass start_pfn. */
> +	new_pfn = (mas.last - size + 1) & align_mask;
> +
>   	new->pfn_lo = new_pfn;
> -	new->pfn_hi = new->pfn_lo + size - 1;
> +	new->pfn_hi = new_pfn + size - 1;
>   
> -	/* If we have 'prev', it's a valid place to start the insertion. */
> -	iova_insert_rbtree(&iovad->rbroot, new, prev);
> -	__cached_rbnode_insert_update(iovad, new);
> +	mas.index = new->pfn_lo;
> +	mas.last = new->pfn_hi;
> +	if (mas_store_gfp(&mas, new, GFP_ATOMIC))
> +		goto alloc_fail;
>   
> -	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>   	return 0;
>   
> -iova32_full:
> -	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
> +alloc_fail:
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>   	return -ENOMEM;
>   }