Re: [PATCH v5 0/3] iommu/iova: convert from rbtree to maple tree

["Jörg Rödel" <joro@8bytes.org>]

Hi Rik,

On Tue, Aug 18, 2026 at 11:25:00AM -0400, Rik van Riel wrote:
> Occasionally production workloads at Meta run into the linear search in
> alloc_iova() in ways that cause real issues. For example, when enough
> CPUs at a time fall into the linear search trap, systems have been known
> to get stuck for so long that it causes soft lockups.
> 
> This series indexes the iova ranges in a maple tree instead. Its gap
> search makes alloc_iova() O(log n).

Thanks for working on this, I really love the idea and more efficient
allocation complexity. For long-term maintainability a few things need to be
sorted out, though.

First, I will ask AMDs IOMMU driver team to do some performance and regression
tests with this series.

> struct iova loses its rb_node and shrinks from 40 to 16 bytes.
> The maple tree keeps its nodes outside the entries, so total memory
> use ends up about the same as before.
> 
> Patch 2 handles the one thing the maple tree does that an rbtree does
> not: erasing an entry can result in the need to rebalance a tree, and
> allocation of maple tree nodes.
> 
> iovas are freed from atomic context, and GFP_ATOMIC allocations mean
> the erase can fail. When it does, the entry is marked IOVA_DEFERRED
> in place and the struct iova is freed. The marker keeps the range
> reserved until iova_drain_deferred() retries the erase.
> 
> Ashok Raj asked on v4 whether the marker store can fail in turn, since
> the WARN_ON_ONCE there reads like error handling for a case the comment
> claims cannot happen.
> 
> Code examination shows that, with the current maple tree code, the
> IOVA_DEFERRED maple tree store will never result in an allocation,
> and cannot fail. This series adds a test case which allows us to verify
> that maple tree property continues to be true.
> 
> Only a corrupted tree, one no longer holding the iova at its own range,
> can reach a store type that allocates. The WARN_ON_ONCE is more of an
> assertion than a recovery path.

This is a lot for the interface contract between the IOVA code and the Maple
tree. We need a way to test and enforce that the maple tree implementation
adheres to the requirements of the IOMMU code going forward. You mention that
there is a test included, not sure if it covers all expectations this code has
(especially when the expectations are different from the ones in core MM code).

The last thing we want is regressions in one of the IOMMU-layers core
componentents because of changes to core MM code.


-Joerg