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

[Ashok Raj]

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

Something odd, except your cover letter rest of the patches are missing
v5 prefix in your patch? 

> This series indexes the iova ranges in a maple tree instead. Its gap
> search makes alloc_iova() O(log n).
> 
> 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.
> 
> Liam Howlett's "maple_tree: lock checking and clean ups" series adds a
> WARN_ON_ONCE to mas_nomem() for a GFP_ATOMIC store under an external
> lock. This series is external-lock and GFP_ATOMIC by construction, so
> both stores would splat if that lands as posted.
> 
> Liam, is the intent to disallow that combination, or to flag callers that
> cannot tolerate a failed store? The iova code handles failure on both
> paths.
> 
> The code was written with Claude, and nitpicked by myself. Don't be shy
> if there are more nitpicks remaining.
> 
> Tested with the KUnit suite in a VM, including with PROVE_LOCKING,
> DEBUG_MAPLE_TREE and KASAN enabled, and on an AMD Bergamo system with the
> IOMMU enabled. I know of no way to reproduce the linear search soft
> lockups at will, so that scenario stays unverified in practice.
> 
>  drivers/iommu/.kunitconfig |   6 +
>  drivers/iommu/Kconfig      |  16 +
>  drivers/iommu/Makefile     |   1 +
>  drivers/iommu/iova-kunit.c | 544 +++++++++++++++++++++++++++++++++
>  drivers/iommu/iova.c       | 561 ++++++++++++++++++++---------------
>  include/linux/iova.h       |  21 +-
>  6 files changed, 901 insertions(+), 248 deletions(-)
> 
> ---
> 
> v4: https://lore.kernel.org/r/20260624030853.2340880-1-riel@surriel.com
> 
> v5:
>  - subject prefix iommu/iova:, matching the file's history
>  - put_iova_domain() takes iova_lock across the tree walk and
>    __mt_destroy(); without it lockdep reports suspicious RCU usage,
>    since a MT_FLAGS_LOCK_EXTERN tree checks the external lock
>  - explain why the IOVA_DEFERRED store cannot fail, and check it in
>    test_marker_store_needs_no_node()
>  - deferred erase is now patch 2, the test suite patch 3
>  - rebased onto v7.2-rc8
> v4:
>  - reduce the size of struct iova to 16 bytes
>  - simplify the (hopefully rare) remove_iova GFP_ATOMIC failure path
>  - test case for the deferred free code
> v3:
>  - switch to maple tree (suggested by Robin Murphy)
> v2:
>  - clean up selftests (thanks Jason Gunthorpe)
>  - drop the search-with-alignment, since most iova requests should be
>    of similar sizes, so the worst case behavior is unlikely to hit
>    once ranges are excluded by the augmented rbtree
> 
> base-commit: ad8d485e665829ecbf3c97b22ce251f8ff5f8037

-- 
/ashok.raj
ashok.raj at oss.qualcomm.com
Qualcomm Inc