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

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

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