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

[Ankit Soni]

On Thu, Sep 24, 2026 at 02:52:45PM +0200, Jörg Rödel wrote:
> 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

Hi Rik and Joerg,

I tested this series on two AMD EPYC systems with real NVMe devices
through the AMD IOMMU driver. Base is v7.2-rc7-104 (ad8d485e6658),
patched is base plus your three patches. I booted base twice on each
system to get a noise floor. The first table pools both boots; the later
two show the first boot, and I only call a difference real where the
second boot agreed.

  system 1: EPYC 9996, 2 sockets, 1024 CPUs, 4 NUMA nodes,  1 NVMe
  system 2: EPYC 9965, 2 sockets,  512 CPUs, 2 NUMA nodes, 12 NVMe

Tests

  1. dma_map_benchmark, the upstream selftest, varying thread count
  2. a depth sweep, varying tree depth on its own at 16 threads
  3. memory at scale, 12 NVMes holding 12.58M live IOVAs
  4. fio across the 12 NVMes
  
1. dma_map_benchmark

It reaches alloc_iova() as long as the granule is above the 128 KiB that
the per-CPU IOVA cache serves. At granule 64 pages the live set is one
mapping per thread, so the thread count is also the tree depth. Strict
mode, min-max over all runs, EPYC 9996:

  threads    base             patched
  1          0.2 us           0.4-0.5 us
  16         0.8-2.0 us       1.4-3.4 us
  128        1.8-226 us       1.7-18.6 us
  512        1,772-2,926 us   4-1,387 us
  1,024      5,532-7,431 us   2,480-2,954 us

At one thread the maple tree costs about 2x, and the ranges do not
overlap, so that cost is real. At 512 and 1,024 threads they do not
overlap the other way and the series is 2-3x faster. In between they
overlap and I would not call either kernel ahead.

2. Depth sweep

dma_map_benchmark unmaps immediately, so the only way it grows the tree
is by adding threads, which also adds lock contention. To vary depth on
its own I used a small driver: real dma_map_single() on an NVMe, N live
mappings per thread, replacing one at random each iteration so the tree
stays N deep and fragmented. Fixed at 16 threads, strict mode:

  live IOVAs      EPYC 9996            EPYC 9965
  in the tree     base     patched     base      patched
  16              1.39 us  1.13 us       930 ns   777 ns
  1,024           94.5 us  19.1 us      58.6 us   14.8 us
  8,192            206 us  31.1 us       132 us   20.7 us
  65,536          1.95 ms  34.8 us      1.25 ms   26.5 us
  524,288         17.6 ms  42.0 us      15.6 ms   28.7 us
  1,048,576       66.9 ms  47.7 us      99.8 ms   33.7 us

The live set grows 65,536x down that table; base grows 48,000x with it,
the series 40x. Tearing the full set back down takes the same time on
both kernels, 3.42 s against 3.42 s on system 2 and 5.4 s against 5.2 s
on system 1. That phase is hardware invalidation, so the gap above is
tree time and not device time.

In lazy mode the series is slower to build a tree from empty, on both
systems: at 16 live IOVAs 26 us against 54 us on system 1, and 15 us
against 27 us on system 2. It is still slower at 1,024 live on both, and
at 8,192 live on system 1. Base itself varies a lot in lazy mode, so I
cannot give a clean size where the cost ends.

3. Memory at scale

One device cannot hold enough live IOVAs to clear the noise, so this is
the 12-NVMe system: twelve independent trees of 1,048,576 entries,
12,582,912 live in total, no allocation failures. Peak slab, three runs:

  live IOVAs    base          patched
  98,304        1007-1011 MB   982-1082 MB
  786,432       1053-1055 MB  1045-1070 MB
  12,582,912    1861-1864 MB  1610-1622 MB

On the first two rows the run-to-run spread is as large as any gap
between the kernels, so I draw no conclusion there, which matches what
your cover letter says. The last is clear of it: patched is 239-254 MB
lower, 72 bytes per live IOVA against 48. The gain is capped by the
maple nodes, 1.47M of 256 bytes at 12.58M live.

4. fio

No change in IOPS, bandwidth or any latency percentile, in either mode.
Block I/O cannot reach this allocator: NVMe clamps its transfer size to
dma_opt_mapping_size(), 128 KiB here, which is exactly the largest size
the per-CPU IOVA cache serves. A kprobe counted 805 of 12,367,841 maps
getting as far as alloc_iova().

Summary:

alloc_iova() is O(log n) in practice, on two CPUs and by two independent
tools. The series costs about 2x on a near-empty tree and wins by orders
of magnitude on a deep one, which is the trade you describe. Memory is
the same within noise below 786k live IOVAs and a third less at 12.58M. 
The costs are confined to microbenchmarks on near-empty trees, No regression
in any real workload.

Tested-by: Ankit Soni <Ankit.Soni@xxxxxxx>

Thanks,
Ankit