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

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

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

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@oss.qualcomm.com
Qualcomm Inc

On Fri, 2026-09-11 at 10:10 -0700, Ashok Raj wrote:
> 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? 

Ugh, indeed.

The content of the patches matches what I wanted
to send, though.

Do you want an identical v6-marked series, or
should I wait for feedback on the code?

kind regards,

Rik
-- 
All Rights Reversed.

On Fri, Sep 11, 2026 at 01:27:29PM -0400, Rik van Riel wrote:
> On Fri, 2026-09-11 at 10:10 -0700, Ashok Raj wrote:
> > 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? 
> 
> Ugh, indeed.
> 
> The content of the patches matches what I wanted
> to send, though.
> 
> Do you want an identical v6-marked series, or
> should I wait for feedback on the code?

naa, just wanted to tell you since it happed the last one too. 

Unless you hear from others and you want to roll in new changes, this
can stay. 

> 
> kind regards,
> 
> Rik
> -- 
> All Rights Reversed.

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