Skip to contentSkip to conversation

iommu/iova: convert from rbtree to maple tree

PATCH In review Rik van Riel 5 participants 13 messages Aug 18 – Oct 12

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

v5 cover iommu/iova: convert from rbtree to maple tree

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/[email protected]

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

#1 lore raw

RFC PATCH v5 1/3 iommu/iova: convert from rbtree to maple tree

alloc_iova() looks for free space by walking the rbtree linearly. On production workloads at Meta, enough CPUs have ended up in that walk at the same time to trigger soft lockups.

Index the iova ranges in a maple tree instead. Its gap search makes alloc_iova() O(log n).

__alloc_and_insert_iova_range() asks mas_empty_area_rev() for the highest free range below limit_pfn. Alignment is handled by rounding up the allocation size, prioritizing speed over address space waste, with the thought that many iova requests on a system will be similar in size, and reuse the same holes.

remove_iova() stores NULL over the entry's range with mas_store_gfp(&mas, NULL, GFP_ATOMIC). mas_erase() is not usable here:
it retries a failed allocation with GFP_KERNEL, which the irq-safe iova_lock does not allow.

That store can fail when the tree needs a node to rebalance, and the entry then stays in the tree. The next patch marks such a range and retries the erase from iova_drain_deferred().

reserve_iova() widens the requested range to cover every overlapping entry in iova_merge_overlaps(), stores one merged entry, and frees the entries that entry supersedes. A request already covered by an existing entry gets that entry back.

struct iova loses its rb_node and shrinks from 40 to 16 bytes. Remove SLAB_HWCACHE_ALIGN to pack 4 iova structs in a cache line.

The tree tracks gaps itself, so the IOVA_ANCHOR sentinel and the cached_node and cached32_node fields are gone.

iova_rbtree_lock is renamed to iova_lock and handed to the tree with MT_FLAGS_LOCK_EXTERN, because the iova code can be called from interrupt context, and an irq safe lock is needed. The same lock also protects related iova data.

The rcache layer is unchanged. It deals in raw pfn values and does not care what the ranges are kept in.

Assisted-by Claude:claude-opus-4-8
---
 drivers/iommu/iova.c | 379 ++++++++++++++++---------------------------
 include/linux/iova.h |  10 +-
 2 files changed, 140 insertions(+), 249 deletions(-)
drivers/iommu/iova.c +137 -242
index 021daf6528de..69f80b14cb3d 100644
@@ -13,9 +13,7 @@
 #include <linux/bitops.h>
 #include <linux/cpu.h>
 #include <linux/workqueue.h>
-
-/* The anchor node sits above the top of the usable address space */
-#define IOVA_ANCHOR	~0UL
+#include <linux/maple_tree.h>
 
 #define IOVA_RANGE_CACHE_MAX_SIZE 6	/* log of max cached IOVA range size (in pages) */
 
@@ -29,11 +27,6 @@ static void free_iova_rcaches(struct iova_domain *iovad);
 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
 static void free_global_cached_iovas(struct iova_domain *iovad);
 
-static struct iova *to_iova(struct rb_node *node)
-{
-	return rb_entry(node, struct iova, node);
-}
-
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	unsigned long start_pfn)
@@ -45,180 +38,68 @@ init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	 */
 	BUG_ON((granule > PAGE_SIZE) || !is_power_of_2(granule));
 
-	spin_lock_init(&iovad->iova_rbtree_lock);
-	iovad->rbroot = RB_ROOT;
-	iovad->cached_node = &iovad->anchor.node;
-	iovad->cached32_node = &iovad->anchor.node;
+	spin_lock_init(&iovad->iova_lock);
+	/*
+	 * IOVAs are freed from hardirq context; use the irq-safe iova_lock,
+	 * instead of the mtree lock. It also protects related iova data.
+	 */
+	mt_init_flags(&iovad->mtree,
+		      MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
+	mt_set_external_lock(&iovad->mtree, &iovad->iova_lock);
 	iovad->granule = granule;
 	iovad->start_pfn = start_pfn;
 	iovad->dma_32bit_pfn = 1UL << (32 - iova_shift(iovad));
 	iovad->max32_alloc_size = iovad->dma_32bit_pfn;
-	iovad->anchor.pfn_lo = iovad->anchor.pfn_hi = IOVA_ANCHOR;
-	rb_link_node(&iovad->anchor.node, NULL, &iovad->rbroot.rb_node);
-	rb_insert_color(&iovad->anchor.node, &iovad->rbroot);
 }
 EXPORT_SYMBOL_GPL(init_iova_domain);
 
-static struct rb_node *
-__get_cached_rbnode(struct iova_domain *iovad, unsigned long limit_pfn)
-{
-	if (limit_pfn <= iovad->dma_32bit_pfn)
-		return iovad->cached32_node;
-
-	return iovad->cached_node;
-}
-
-static void
-__cached_rbnode_insert_update(struct iova_domain *iovad, struct iova *new)
-{
-	if (new->pfn_hi < iovad->dma_32bit_pfn)
-		iovad->cached32_node = &new->node;
-	else
-		iovad->cached_node = &new->node;
-}
-
-static void
-__cached_rbnode_delete_update(struct iova_domain *iovad, struct iova *free)
-{
-	struct iova *cached_iova;
-
-	cached_iova = to_iova(iovad->cached32_node);
-	if (free == cached_iova ||
-	    (free->pfn_hi < iovad->dma_32bit_pfn &&
-	     free->pfn_lo >= cached_iova->pfn_lo))
-		iovad->cached32_node = rb_next(&free->node);
-
-	if (free->pfn_lo < iovad->dma_32bit_pfn)
-		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
-
-	cached_iova = to_iova(iovad->cached_node);
-	if (free->pfn_lo >= cached_iova->pfn_lo)
-		iovad->cached_node = rb_next(&free->node);
-}
-
-static struct rb_node *iova_find_limit(struct iova_domain *iovad, unsigned long limit_pfn)
-{
-	struct rb_node *node, *next;
-	/*
-	 * Ideally what we'd like to judge here is whether limit_pfn is close
-	 * enough to the highest-allocated IOVA that starting the allocation
-	 * walk from the anchor node will be quicker than this initial work to
-	 * find an exact starting point (especially if that ends up being the
-	 * anchor node anyway). This is an incredibly crude approximation which
-	 * only really helps the most likely case, but is at least trivially easy.
-	 */
-	if (limit_pfn > iovad->dma_32bit_pfn)
-		return &iovad->anchor.node;
-
-	node = iovad->rbroot.rb_node;
-	while (to_iova(node)->pfn_hi < limit_pfn)
-		node = node->rb_right;
-
-search_left:
-	while (node->rb_left && to_iova(node->rb_left)->pfn_lo >= limit_pfn)
-		node = node->rb_left;
-
-	if (!node->rb_left)
-		return node;
-
-	next = node->rb_left;
-	while (next->rb_right) {
-		next = next->rb_right;
-		if (to_iova(next)->pfn_lo >= limit_pfn) {
-			node = next;
-			goto search_left;
-		}
-	}
-
-	return node;
-}
-
-/* Insert the iova into domain rbtree by holding writer lock */
-static void
-iova_insert_rbtree(struct rb_root *root, struct iova *iova,
-		   struct rb_node *start)
-{
-	struct rb_node **new, *parent = NULL;
-
-	new = (start) ? &start : &(root->rb_node);
-	/* Figure out where to put new node */
-	while (*new) {
-		struct iova *this = to_iova(*new);
-
-		parent = *new;
-
-		if (iova->pfn_lo < this->pfn_lo)
-			new = &((*new)->rb_left);
-		else if (iova->pfn_lo > this->pfn_lo)
-			new = &((*new)->rb_right);
-		else {
-			WARN_ON(1); /* this should not happen */
-			return;
-		}
-	}
-	/* Add new node and rebalance tree. */
-	rb_link_node(&iova->node, parent, new);
-	rb_insert_color(&iova->node, root);
-}
-
 static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 		unsigned long size, unsigned long limit_pfn,
 			struct iova *new, bool size_aligned)
 {
-	struct rb_node *curr, *prev;
-	struct iova *curr_iova;
 	unsigned long flags;
-	unsigned long new_pfn, retry_pfn;
+	unsigned long new_pfn;
 	unsigned long align_mask = ~0UL;
-	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
+	unsigned long search_size = size;
+	MA_STATE(mas, &iovad->mtree, 0, 0);
+
+	if (size_aligned) {
+		unsigned long align = 1UL << fls_long(size - 1);
 
-	if (size_aligned)
 		align_mask <<= fls_long(size - 1);
+		search_size = size + align - 1;
+	}
 
-	/* Walk the tree backwards */
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	spin_lock_irqsave(&iovad->iova_lock, flags);
+	/* No 32-bit request this large can fit until the hint is cleared. */
 	if (limit_pfn <= iovad->dma_32bit_pfn &&
 			size >= iovad->max32_alloc_size)
-		goto iova32_full;
-
-	curr = __get_cached_rbnode(iovad, limit_pfn);
-	curr_iova = to_iova(curr);
-	retry_pfn = curr_iova->pfn_hi;
-
-retry:
-	do {
-		high_pfn = min(high_pfn, curr_iova->pfn_lo);
-		new_pfn = (high_pfn - size) & align_mask;
-		prev = curr;
-		curr = rb_prev(curr);
-		curr_iova = to_iova(curr);
-	} while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
-
-	if (high_pfn < size || new_pfn < low_pfn) {
-		if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
-			high_pfn = limit_pfn;
-			low_pfn = retry_pfn + 1;
-			curr = iova_find_limit(iovad, limit_pfn);
-			curr_iova = to_iova(curr);
-			goto retry;
-		}
-		iovad->max32_alloc_size = size;
-		goto iova32_full;
+		goto alloc_fail;
+
+	if (mas_empty_area_rev(&mas, iovad->start_pfn,
+				 limit_pfn - 1, search_size)) {
+		/* Only real exhaustion sets the hint, not a failed store. */
+		if (limit_pfn <= iovad->dma_32bit_pfn)
+			iovad->max32_alloc_size = size;
+		goto alloc_fail;
 	}
 
-	/* pfn_lo will point to size aligned address if size_aligned is set */
+	/* The gap is search_size wide, so alignment cannot pass start_pfn. */
+	new_pfn = (mas.last - size + 1) & align_mask;
+
 	new->pfn_lo = new_pfn;
-	new->pfn_hi = new->pfn_lo + size - 1;
+	new->pfn_hi = new_pfn + size - 1;
 
-	/* If we have 'prev', it's a valid place to start the insertion. */
-	iova_insert_rbtree(&iovad->rbroot, new, prev);
-	__cached_rbnode_insert_update(iovad, new);
+	mas.index = new->pfn_lo;
+	mas.last = new->pfn_hi;
+	if (mas_store_gfp(&mas, new, GFP_ATOMIC))
+		goto alloc_fail;
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return 0;
 
-iova32_full:
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+alloc_fail:
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return -ENOMEM;
 }
 
@@ -233,8 +114,7 @@ static struct iova *alloc_iova_mem(void)
 
 static void free_iova_mem(struct iova *iova)
 {
-	if (iova->pfn_lo != IOVA_ANCHOR)
-		kmem_cache_free(iova_cache, iova);
+	kmem_cache_free(iova_cache, iova);
 }
 
 /**
@@ -275,29 +155,29 @@ EXPORT_SYMBOL_GPL(alloc_iova);
 static struct iova *
 private_find_iova(struct iova_domain *iovad, unsigned long pfn)
 {
-	struct rb_node *node = iovad->rbroot.rb_node;
-
-	assert_spin_locked(&iovad->iova_rbtree_lock);
-
-	while (node) {
-		struct iova *iova = to_iova(node);
-
-		if (pfn < iova->pfn_lo)
-			node = node->rb_left;
-		else if (pfn > iova->pfn_hi)
-			node = node->rb_right;
-		else
-			return iova;	/* pfn falls within iova's range */
-	}
+	MA_STATE(mas, &iovad->mtree, pfn, pfn);
 
-	return NULL;
+	assert_spin_locked(&iovad->iova_lock);
+	return mas_walk(&mas);
 }
 
 static void remove_iova(struct iova_domain *iovad, struct iova *iova)
 {
-	assert_spin_locked(&iovad->iova_rbtree_lock);
-	__cached_rbnode_delete_update(iovad, iova);
-	rb_erase(&iova->node, &iovad->rbroot);
+	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
+
+	assert_spin_locked(&iovad->iova_lock);
+
+	if (iova->pfn_lo < iovad->dma_32bit_pfn)
+		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
+
+	/*
+	 * A failed store leaves the iova in the tree, so it cannot be freed
+	 * here. The range stays reserved until the domain is torn down.
+	 */
+	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
+		return;
+
+	free_iova_mem(iova);
 }
 
 /**
@@ -312,10 +192,9 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 	unsigned long flags;
 	struct iova *iova;
 
-	/* Take the lock so that no other thread is manipulating the rbtree */
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	spin_lock_irqsave(&iovad->iova_lock, flags);
 	iova = private_find_iova(iovad, pfn);
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return iova;
 }
 EXPORT_SYMBOL_GPL(find_iova);
@@ -331,10 +210,9 @@ __free_iova(struct iova_domain *iovad, struct iova *iova)
 {
 	unsigned long flags;
 
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	spin_lock_irqsave(&iovad->iova_lock, flags);
 	remove_iova(iovad, iova);
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
-	free_iova_mem(iova);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 }
 EXPORT_SYMBOL_GPL(__free_iova);
 
@@ -351,15 +229,14 @@ free_iova(struct iova_domain *iovad, unsigned long pfn)
 	unsigned long flags;
 	struct iova *iova;
 
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	spin_lock_irqsave(&iovad->iova_lock, flags);
 	iova = private_find_iova(iovad, pfn);
 	if (!iova) {
-		spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+		spin_unlock_irqrestore(&iovad->iova_lock, flags);
 		return;
 	}
 	remove_iova(iovad, iova);
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
-	free_iova_mem(iova);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 }
 EXPORT_SYMBOL_GPL(free_iova);
 
@@ -445,27 +322,26 @@ static void iova_domain_free_rcaches(struct iova_domain *iovad)
  */
 void put_iova_domain(struct iova_domain *iovad)
 {
-	struct iova *iova, *tmp;
+	unsigned long flags;
+	struct iova *iova;
+
+	MA_STATE(mas, &iovad->mtree, 0, 0);
 
 	if (iovad->rcaches)
 		iova_domain_free_rcaches(iovad);
 
-	rbtree_postorder_for_each_entry_safe(iova, tmp, &iovad->rbroot, node)
+	/*
+	 * Nothing else can reach a domain being destroyed, but the maple tree
+	 * walk still has to hold the lock the tree was given.
+	 */
+	spin_lock_irqsave(&iovad->iova_lock, flags);
+	mas_for_each(&mas, iova, ULONG_MAX)
 		free_iova_mem(iova);
+	__mt_destroy(&iovad->mtree);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 }
 EXPORT_SYMBOL_GPL(put_iova_domain);
 
-static int
-__is_range_overlap(struct rb_node *node,
-	unsigned long pfn_lo, unsigned long pfn_hi)
-{
-	struct iova *iova = to_iova(node);
-
-	if ((pfn_lo <= iova->pfn_hi) && (pfn_hi >= iova->pfn_lo))
-		return 1;
-	return 0;
-}
-
 static inline struct iova *
 alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
 {
@@ -480,27 +356,28 @@ alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
 	return iova;
 }
 
-static struct iova *
-__insert_new_range(struct iova_domain *iovad,
-	unsigned long pfn_lo, unsigned long pfn_hi)
+/*
+ * A maple tree cannot hold overlapping ranges, so overlapping reservations
+ * have to be merged into one wider entry.
+ */
+static struct iova *iova_merge_overlaps(struct iova_domain *iovad,
+					unsigned long *lo, unsigned long *hi)
 {
-	struct iova *iova;
+	unsigned long pfn_lo = *lo, pfn_hi = *hi;
+	struct iova *overlap;
 
-	iova = alloc_and_init_iova(pfn_lo, pfn_hi);
-	if (iova)
-		iova_insert_rbtree(&iovad->rbroot, iova, NULL);
+	MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
 
-	return iova;
-}
+	mas_for_each(&mas, overlap, pfn_hi) {
+		if (pfn_lo >= overlap->pfn_lo && pfn_hi <= overlap->pfn_hi)
+			return overlap;
+		if (overlap->pfn_lo < *lo)
+			*lo = overlap->pfn_lo;
+		if (overlap->pfn_hi > *hi)
+			*hi = overlap->pfn_hi;
+	}
 
-static void
-__adjust_overlap_range(struct iova *iova,
-	unsigned long *pfn_lo, unsigned long *pfn_hi)
-{
-	if (*pfn_lo < iova->pfn_lo)
-		iova->pfn_lo = *pfn_lo;
-	if (*pfn_hi > iova->pfn_hi)
-		*pfn_lo = iova->pfn_hi + 1;
+	return NULL;
 }
 
 /**
@@ -510,41 +387,59 @@ __adjust_overlap_range(struct iova *iova,
  * @pfn_hi:- higher pfn address
  * This function allocates reserves the address range from pfn_lo to pfn_hi so
  * that this address is not dished out as part of alloc_iova.
+ *
+ * If the requested range overlaps existing reservations, ranges are merged.
+ * If the requested range is fully covered by an existing reservation, the
+ * existing entry is returned without allocating.
  */
 struct iova *
 reserve_iova(struct iova_domain *iovad,
 	unsigned long pfn_lo, unsigned long pfn_hi)
 {
-	struct rb_node *node;
+	unsigned long merged_lo = pfn_lo, merged_hi = pfn_hi;
+	struct iova *iova, *overlap;
 	unsigned long flags;
-	struct iova *iova;
-	unsigned int overlap = 0;
+
+	MA_STATE(mas, &iovad->mtree, 0, 0);
+	MA_STATE(fmas, &iovad->mtree, 0, 0);
 
 	/* Don't allow nonsensical pfns */
 	if (WARN_ON((pfn_hi | pfn_lo) > (ULLONG_MAX >> iova_shift(iovad))))
 		return NULL;
 
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
-	for (node = rb_first(&iovad->rbroot); node; node = rb_next(node)) {
-		if (__is_range_overlap(node, pfn_lo, pfn_hi)) {
-			iova = to_iova(node);
-			__adjust_overlap_range(iova, &pfn_lo, &pfn_hi);
-			if ((pfn_lo >= iova->pfn_lo) &&
-				(pfn_hi <= iova->pfn_hi))
-				goto finish;
-			overlap = 1;
-
-		} else if (overlap)
-				break;
-	}
+	spin_lock_irqsave(&iovad->iova_lock, flags);
+
+	/*
+	 * The overlapping iovas cannot be freed yet: the merged store below
+	 * can fail, and freeing before a failed store would leave dangling
+	 * pointers in the tree.
+	 */
+	iova = iova_merge_overlaps(iovad, &merged_lo, &merged_hi);
+	if (iova)
+		goto out;
+
+	iova = alloc_and_init_iova(merged_lo, merged_hi);
+	if (!iova)
+		goto out;
 
-	/* We are here either because this is the first reserver node
-	 * or need to insert remaining non overlap addr range
+	/*
+	 * The superseded overlaps are freed before the merged store, so the
+	 * store must not be able to fail after that point.
 	 */
-	iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
-finish:
+	mas_set_range(&mas, merged_lo, merged_hi);
+	if (mas_preallocate(&mas, iova, GFP_ATOMIC)) {
+		free_iova_mem(iova);
+		iova = NULL;
+		goto out;
+	}
+
+	mas_set_range(&fmas, merged_lo, merged_hi);
+	mas_for_each(&fmas, overlap, merged_hi)
+		free_iova_mem(overlap);
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	mas_store_prealloc(&mas, iova);
+out:
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return iova;
 }
 EXPORT_SYMBOL_GPL(reserve_iova);
@@ -621,7 +516,7 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 	unsigned long flags;
 	int i;
 
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	spin_lock_irqsave(&iovad->iova_lock, flags);
 
 	for (i = 0 ; i < mag->size; ++i) {
 		struct iova *iova = private_find_iova(iovad, mag->pfns[i]);
@@ -633,7 +528,7 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 		free_iova_mem(iova);
 	}
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 
 	mag->size = 0;
 }
@@ -956,8 +851,8 @@ int iova_cache_get(void)
 
 	mutex_lock(&iova_cache_mutex);
 	if (!iova_cache_users) {
-		iova_cache = kmem_cache_create("iommu_iova", sizeof(struct iova), 0,
-					       SLAB_HWCACHE_ALIGN, NULL);
+		iova_cache = kmem_cache_create("iommu_iova", sizeof(struct iova),
+					       0, 0, NULL);
 		if (!iova_cache)
 			goto out_err;
 
include/linux/iova.h +3 -7
index d2c4fd923efa..a3dab6c5fd62 100644
@@ -11,12 +11,11 @@
 
 #include <linux/types.h>
 #include <linux/kernel.h>
-#include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/dma-mapping.h>
 
 /* iova structure */
 struct iova {
-	struct rb_node	node;
 	unsigned long	pfn_hi; /* Highest allocated pfn */
 	unsigned long	pfn_lo; /* Lowest allocated pfn */
 };
@@ -26,15 +25,12 @@ struct iova_rcache;
 
 /* holds all the iova translations for a domain */
 struct iova_domain {
-	spinlock_t	iova_rbtree_lock; /* Lock to protect update of rbtree */
-	struct rb_root	rbroot;		/* iova domain rbtree root */
-	struct rb_node	*cached_node;	/* Save last alloced node */
-	struct rb_node	*cached32_node; /* Save last 32-bit alloced node */
+	spinlock_t	iova_lock;	/* Protects the maple tree */
+	struct maple_tree	mtree;
 	unsigned long	granule;	/* pfn granularity for this domain */
 	unsigned long	start_pfn;	/* Lower limit for this domain */
 	unsigned long	dma_32bit_pfn;
 	unsigned long	max32_alloc_size; /* Size of last failed allocation */
-	struct iova	anchor;		/* rbtree lookup anchor */
 
 	struct iova_rcache	*rcaches;
 	struct hlist_node	cpuhp_dead;
Signature · 1 line
2.53.0-Meta
maintainer
#2 lore raw
Quoted 12 lines · Rik van Riel

alloc_iova() looks for free space by walking the rbtree linearly. On production workloads at Meta, enough CPUs have ended up in that walk at the same time to trigger soft lockups.

Index the iova ranges in a maple tree instead. Its gap search makes alloc_iova() O(log n).

__alloc_and_insert_iova_range() asks mas_empty_area_rev() for the highest free range below limit_pfn. Alignment is handled by rounding up the allocation size, prioritizing speed over address space waste, with the thought that many iova requests on a system will be similar in size, and reuse the same holes.

[...]

Quoted 11 lines

static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
unsigned long size, unsigned long limit_pfn,
struct iova *new, bool size_aligned)
{

drivers/iommu/iova.c +1 -4
-	struct rb_node *curr, *prev;
-	struct iova *curr_iova;
  	unsigned long flags;
-	unsigned long new_pfn, retry_pfn;
+	unsigned long new_pfn;
  	unsigned long align_mask = ~0UL;
-	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;

drivers/iommu/iova.c init_iova_domain(struct iova_domain *iovad, unsigned long granule, · line 71

Quoted 10 lines
drivers/iommu/iova.c +7 -1
+	unsigned long search_size = size;
+	MA_STATE(mas, &iovad->mtree, 0, 0);
+
+	if (size_aligned) {
+		unsigned long align = 1UL << fls_long(size - 1);
 
-	if (size_aligned)
  		align_mask <<= fls_long(size - 1);
+		search_size = size + align - 1;
+	}

Perhaps it's a bit too much of a cool trick, but I think technically we could just do "search_size = size + ~align_mask" unconditionally.

However, either way I do worry somewhat about the increase in fragmentation and premature failures once the space starts to fill up. Say for simplicity we have a start_pfn of 0 and limit_pfn of 4 - with the current code we can successfully allocate a size of 1 (to IOVA 3) followed by a size of 3 (to IOVA 0), or even in the opposite order for the same result, whereas with this workaround we couldn't ever allocate the 3 either way if its search_size has to be 7.

AFAIK there are real-world use-cases where the usable IOVA space is relatively small compared to the sizes of some of the buffers being mapped, such that packing density matters (i.e. media stuff in mobile SoCs), so if at all possible it would be good if maple tree itself could be improved to support searching for a free range with a particular alignment (either explicit, or implied natural alignemnt of the size) rather than having to bodge it this way. Unfortunately we also can't just relax the general DMA API guarantee that DMA addresses are naturally-aligned to the mapping/allocation size, as who knows how many devices that might break.

drivers/iommu/iova.c init_iova_domain(struct iova_domain *iovad, unsigned long granule, · line 179

Quoted 2 lines
drivers/iommu/iova.c +0 -2
-	/* Walk the tree backwards */
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

FWIW I'm not much of a fan of the implicit scoped-cleanup stuff in general, but this seems like an instance where using guard() to simplify all the early returns might be worthwhile.

Thanks,
Robin.

Quoted 65 lines
drivers/iommu/iova.c +21 -33
+	spin_lock_irqsave(&iovad->iova_lock, flags);
+	/* No 32-bit request this large can fit until the hint is cleared. */
  	if (limit_pfn <= iovad->dma_32bit_pfn &&
  			size >= iovad->max32_alloc_size)
-		goto iova32_full;
-
-	curr = __get_cached_rbnode(iovad, limit_pfn);
-	curr_iova = to_iova(curr);
-	retry_pfn = curr_iova->pfn_hi;
-
-retry:
-	do {
-		high_pfn = min(high_pfn, curr_iova->pfn_lo);
-		new_pfn = (high_pfn - size) & align_mask;
-		prev = curr;
-		curr = rb_prev(curr);
-		curr_iova = to_iova(curr);
-	} while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
-
-	if (high_pfn < size || new_pfn < low_pfn) {
-		if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) {
-			high_pfn = limit_pfn;
-			low_pfn = retry_pfn + 1;
-			curr = iova_find_limit(iovad, limit_pfn);
-			curr_iova = to_iova(curr);
-			goto retry;
-		}
-		iovad->max32_alloc_size = size;
-		goto iova32_full;
+		goto alloc_fail;
+
+	if (mas_empty_area_rev(&mas, iovad->start_pfn,
+				 limit_pfn - 1, search_size)) {
+		/* Only real exhaustion sets the hint, not a failed store. */
+		if (limit_pfn <= iovad->dma_32bit_pfn)
+			iovad->max32_alloc_size = size;
+		goto alloc_fail;
  	}
 
-	/* pfn_lo will point to size aligned address if size_aligned is set */
+	/* The gap is search_size wide, so alignment cannot pass start_pfn. */
+	new_pfn = (mas.last - size + 1) & align_mask;
+
  	new->pfn_lo = new_pfn;
-	new->pfn_hi = new->pfn_lo + size - 1;
+	new->pfn_hi = new_pfn + size - 1;
 
-	/* If we have 'prev', it's a valid place to start the insertion. */
-	iova_insert_rbtree(&iovad->rbroot, new, prev);
-	__cached_rbnode_insert_update(iovad, new);
+	mas.index = new->pfn_lo;
+	mas.last = new->pfn_hi;
+	if (mas_store_gfp(&mas, new, GFP_ATOMIC))
+		goto alloc_fail;
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
  	return 0;
 
-iova32_full:
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+alloc_fail:
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
  	return -ENOMEM;
  }
#3 lore raw
Quoted 46 lines · Robin Murphy
Quoted 16 lines · Rik van Riel

alloc_iova() looks for free space by walking the rbtree linearly. On production workloads at Meta, enough CPUs have ended up in that walk
at the same time to trigger soft lockups.

Index the iova ranges in a maple tree instead. Its gap search makes alloc_iova() O(log n).

__alloc_and_insert_iova_range() asks mas_empty_area_rev() for the highest free range below limit_pfn. Alignment is handled by rounding
up the allocation size, prioritizing speed over address space waste,
with the thought that many iova requests on a system will be similar
in size, and reuse the same holes.

[...]

Quoted 21 lines

  static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
   unsigned long size, unsigned long limit_pfn, struct iova *new, bool size_aligned) {

drivers/iommu/iova.c +0 -2
-	struct rb_node *curr, *prev;
-	struct iova *curr_iova;

   unsigned long flags;

drivers/iommu/iova.c +1 -1
-	unsigned long new_pfn, retry_pfn;
+	unsigned long new_pfn;

   unsigned long align_mask = ~0UL;

(quoted diff) +0 -1
-	unsigned long high_pfn = limit_pfn, low_pfn = iovad-
Quoted 1 line

start_pfn;

drivers/iommu/iova.c +5 -0
+	unsigned long search_size = size;
+	MA_STATE(mas, &iovad->mtree, 0, 0);
+
+	if (size_aligned) {
+		unsigned long align = 1UL << fls_long(size - 1);

drivers/iommu/iova.c +0 -1
-	if (size_aligned)

   align_mask <<= fls_long(size - 1);

drivers/iommu/iova.c init_iova_domain(struct iova_domain *iovad, unsigned long granule, · line 71

Quoted 2 lines
drivers/iommu/iova.c +2 -0
+		search_size = size + align - 1;
+	}

Perhaps it's a bit too much of a cool trick, but I think technically we
could just do "search_size = size + ~align_mask" unconditionally.

Quoted 4 lines

However, either way I do worry somewhat about the increase in fragmentation and premature failures once the space starts to fill up.

For that use case, I am guessing what we really want to propagate up the tree is not the maximum size of a gap, but the maximum power of two size gap that is also aligned to its own size.

In other words, if we have something like this, aligned 8, we propagate up a gap size 4:

used used used used gap gap gap gap

But if the usage looks like this, at the same alignment to the start, we propagate a gap size 2:

used used used gap gap gap gap used

That would allow us to easily find gaps aligned to their own size. Once the size 2 gap is filled in, we propagate up the remaining size 1 gaps.

That makes me wonder if we need to go back to the augmented rbtree, instead of using the maple tree?

Just let me know your preference.

Quoted 8 lines

drivers/iommu/iova.c init_iova_domain(struct iova_domain *iovad, unsigned long granule, · line 179

Quoted 3 lines
drivers/iommu/iova.c +0 -2
-	/* Walk the tree backwards */
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);

FWIW I'm not much of a fan of the implicit scoped-cleanup stuff in general, but this seems like an instance where using guard() to simplify
all the early returns might be worthwhile.

I'm happy to do that.

Are there any other changes I should be making to get this code ready for merging?

Signature · 1 line
All Rights Reversed.
#4 lore raw
In reply to Robin Murphy
Quoted 4 lines · Robin Murphy

However, either way I do worry somewhat about the increase in fragmentation and premature failures once the space starts to fill up.

Now that we have AMD's test results, how do you prefer we move forward with making the iova allocation O(log n) ?

Do you want to pursue the maple tree approach, and live with the fragmentation worry?

In that case, I'll apply your suggested cleanups.

Do you want me to code up an augmented rbtree that propagates up (power of 2) aligned gap size, so we can do an exact hole fit without having to walk through the tree?

Do you have some other preference?

Signature · 1 line
All Rights Reversed.
#5 lore raw

RFC PATCH v5 2/3 iommu/iova: defer maple tree erase on GFP_ATOMIC failure

In reply to Rik van Riel

rb_erase() never allocates. Removing an entry from a maple tree can, so the mas_store_gfp(&mas, NULL, GFP_ATOMIC) in remove_iova() can fail, and iovas are freed from atomic context, where GFP_KERNEL is not available.

Failing takes a specific shape. Storing NULL runs mas_wr_extend_null() first, which pulls adjacent free ranges into the store. With a live iova on either side there is nothing to pull in, and the store is wr_exact_fit, which needs no node. Only a free neighbour, dropping the leaf below mt_min_slots, makes the tree rebalance and allocate.

When the erase does fail, store IOVA_DEFERRED over the entry's own range instead, and free the struct iova. A non-NULL value does not extend the range, so that store is wr_exact_fit whatever the neighbours look like, and cannot fail.

XA_ZERO_ENTRY would reserve the range too, but mtree_load() and mt_find() turn it back into NULL, so any later use of the normal API on this tree would see a marked range as free.

The domain keeps a [deferred_lo, deferred_hi] range covering the markers. iova_drain_deferred() walks only that range, and retries the erases from the next allocation or the next successful free.

struct iova stays at 16 bytes: the state is the marker plus two unsigned longs per domain. The store that can fail now runs where failure can be returned to the caller, so no timer or workqueue is needed.

Should the marker store fail anyway, WARN_ON_ONCE() reports it and the entry stays in the tree as a live iova. Its range is then reserved until put_iova_domain() frees it with the rest of the domain. BUG_ON() would trade that stranded range for a dead machine.

Assisted-by Claude:claude-opus-4-8
---
 drivers/iommu/iova.c | 131 +++++++++++++++++++++++++++++++++++++------
 include/linux/iova.h |   3 +
 2 files changed, 118 insertions(+), 16 deletions(-)
drivers/iommu/iova.c +115 -16
index 69f80b14cb3d..255a1cefe8c5 100644
@@ -26,6 +26,23 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad,
 static void free_iova_rcaches(struct iova_domain *iovad);
 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
 static void free_global_cached_iovas(struct iova_domain *iovad);
+static void iova_drain_deferred(struct iova_domain *iovad);
+
+/*
+ * Stored over an entry whose erase failed: an in-place store of a
+ * non-NULL value needs no node allocation, so it works where the
+ * erase did not. The gap search treats the slot as occupied, keeping
+ * the range reserved; lookups, teardown and the invariant checker
+ * skip it. Pointing at a static keeps it 8-byte aligned, out of the
+ * range the maple tree uses for internal entries.
+ */
+static const unsigned long iova_deferred_marker;
+#define IOVA_DEFERRED		((struct iova *)&iova_deferred_marker)
+
+static inline bool iova_has_deferred(const struct iova_domain *iovad)
+{
+	return iovad->deferred_lo <= iovad->deferred_hi;
+}
 
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
@@ -50,6 +67,8 @@ init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	iovad->start_pfn = start_pfn;
 	iovad->dma_32bit_pfn = 1UL << (32 - iova_shift(iovad));
 	iovad->max32_alloc_size = iovad->dma_32bit_pfn;
+	iovad->deferred_lo = ULONG_MAX;
+	iovad->deferred_hi = 0;
 }
 EXPORT_SYMBOL_GPL(init_iova_domain);
 
@@ -71,6 +90,9 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 	}
 
 	spin_lock_irqsave(&iovad->iova_lock, flags);
+	/* Reclaim deferred frees to get their address space back. */
+	if (unlikely(iova_has_deferred(iovad)))
+		iova_drain_deferred(iovad);
 	/* No 32-bit request this large can fit until the hint is cleared. */
 	if (limit_pfn <= iovad->dma_32bit_pfn &&
 			size >= iovad->max32_alloc_size)
@@ -156,28 +178,96 @@ static struct iova *
 private_find_iova(struct iova_domain *iovad, unsigned long pfn)
 {
 	MA_STATE(mas, &iovad->mtree, pfn, pfn);
+	struct iova *iova;
+
+	assert_spin_locked(&iovad->iova_lock);
+	iova = mas_walk(&mas);
+	/* A deferred-erase marker is not a live iova; treat it as absent. */
+	if (iova == IOVA_DEFERRED)
+		return NULL;
+	return iova;
+}
+
+/* Every marker lies within [deferred_lo, deferred_hi]. Needs iova_lock. */
+static void iova_drain_deferred(struct iova_domain *iovad)
+{
+	unsigned long hi = iovad->deferred_hi;
+	void *entry;
+
+	MA_STATE(mas, &iovad->mtree, iovad->deferred_lo, hi);
 
 	assert_spin_locked(&iovad->iova_lock);
-	return mas_walk(&mas);
+
+	while ((entry = mas_find(&mas, hi)) != NULL) {
+		unsigned long lo = mas.index, last = mas.last;
+
+		if (entry == IOVA_DEFERRED) {
+			mas_set_range(&mas, lo, last);
+			if (mas_store_gfp(&mas, NULL, GFP_ATOMIC)) {
+				/*
+				 * No reclaim can happen under the lock, so
+				 * the remaining erases would fail too.
+				 */
+				iovad->deferred_lo = lo;
+				iovad->deferred_hi = hi;
+				return;
+			}
+			/* The store moves the iterator; re-anchor. */
+			mas_set(&mas, last + 1);
+		}
+
+		if (last >= hi)
+			break;
+	}
+
+	iovad->deferred_lo = ULONG_MAX;
+	iovad->deferred_hi = 0;
 }
 
+/*
+ * Must not fail: DMA unmap runs in atomic context, so there is no caller to
+ * return an error to.
+ */
 static void remove_iova(struct iova_domain *iovad, struct iova *iova)
 {
-	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
+	unsigned long pfn_lo = iova->pfn_lo, pfn_hi = iova->pfn_hi;
+
+	MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
 
 	assert_spin_locked(&iovad->iova_lock);
 
-	if (iova->pfn_lo < iovad->dma_32bit_pfn)
+	if (pfn_lo < iovad->dma_32bit_pfn)
 		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
 
-	/*
-	 * A failed store leaves the iova in the tree, so it cannot be freed
-	 * here. The range stays reserved until the domain is torn down.
-	 */
-	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
+	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC)) {
+		/*
+		 * A NULL store gets widened over the neighbouring free ranges,
+		 * and the wider store may cause a maple tree rebalance, which
+		 * can fail if tree nodes failed to allocate. The IOVA_DEFERRED
+		 * store is never widened and needs no allocation, as
+		 * test_marker_store_needs_no_node() checks. Check anyway,
+		 * because surviving e.g. a maple tree corruption here is cheap.
+		 */
+		mas_set_range(&mas, pfn_lo, pfn_hi);
+		if (WARN_ON_ONCE(mas_store_gfp(&mas, IOVA_DEFERRED, GFP_ATOMIC)))
+			/*
+			 * The tree still holds the live iova: nothing for the
+			 * sweep to find, and teardown frees it.
+			 */
+			return;
+		if (pfn_lo < iovad->deferred_lo)
+			iovad->deferred_lo = pfn_lo;
+		if (pfn_hi > iovad->deferred_hi)
+			iovad->deferred_hi = pfn_hi;
+		free_iova_mem(iova);
 		return;
+	}
 
 	free_iova_mem(iova);
+
+	/* A successful erase means memory is available; clear any backlog. */
+	if (unlikely(iova_has_deferred(iovad)))
+		iova_drain_deferred(iovad);
 }
 
 /**
@@ -231,11 +321,8 @@ free_iova(struct iova_domain *iovad, unsigned long pfn)
 
 	spin_lock_irqsave(&iovad->iova_lock, flags);
 	iova = private_find_iova(iovad, pfn);
-	if (!iova) {
-		spin_unlock_irqrestore(&iovad->iova_lock, flags);
-		return;
-	}
-	remove_iova(iovad, iova);
+	if (iova)
+		remove_iova(iovad, iova);
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 }
 EXPORT_SYMBOL_GPL(free_iova);
@@ -335,8 +422,10 @@ void put_iova_domain(struct iova_domain *iovad)
 	 * walk still has to hold the lock the tree was given.
 	 */
 	spin_lock_irqsave(&iovad->iova_lock, flags);
+	/* Skip IOVA_DEFERRED entries: their iovas were already freed. */
 	mas_for_each(&mas, iova, ULONG_MAX)
-		free_iova_mem(iova);
+		if (iova != IOVA_DEFERRED)
+			free_iova_mem(iova);
 	__mt_destroy(&iovad->mtree);
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 }
@@ -369,6 +458,12 @@ static struct iova *iova_merge_overlaps(struct iova_domain *iovad,
 	MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
 
 	mas_for_each(&mas, overlap, pfn_hi) {
+		/*
+		 * A deferred-erase marker isn't a real iova; the merged-range
+		 * store in the caller spans and overwrites it.
+		 */
+		if (overlap == IOVA_DEFERRED)
+			continue;
 		if (pfn_lo >= overlap->pfn_lo && pfn_hi <= overlap->pfn_hi)
 			return overlap;
 		if (overlap->pfn_lo < *lo)
@@ -409,6 +504,10 @@ reserve_iova(struct iova_domain *iovad,
 
 	spin_lock_irqsave(&iovad->iova_lock, flags);
 
+	/* Leave the walk below with only live iovas to look at. */
+	if (unlikely(iova_has_deferred(iovad)))
+		iova_drain_deferred(iovad);
+
 	/*
 	 * The overlapping iovas cannot be freed yet: the merged store below
 	 * can fail, and freeing before a failed store would leave dangling
@@ -435,7 +534,8 @@ reserve_iova(struct iova_domain *iovad,
 
 	mas_set_range(&fmas, merged_lo, merged_hi);
 	mas_for_each(&fmas, overlap, merged_hi)
-		free_iova_mem(overlap);
+		if (overlap != IOVA_DEFERRED)
+			free_iova_mem(overlap);
 
 	mas_store_prealloc(&mas, iova);
 out:
@@ -525,7 +625,6 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 			continue;
 
 		remove_iova(iovad, iova);
-		free_iova_mem(iova);
 	}
 
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
include/linux/iova.h +3 -0
index a3dab6c5fd62..e17bb1e85838 100644
@@ -31,6 +31,9 @@ struct iova_domain {
 	unsigned long	start_pfn;	/* Lower limit for this domain */
 	unsigned long	dma_32bit_pfn;
 	unsigned long	max32_alloc_size; /* Size of last failed allocation */
+	/* Bounding range of deferred erases; lo > hi when there are none. */
+	unsigned long	deferred_lo;
+	unsigned long	deferred_hi;
 
 	struct iova_rcache	*rcaches;
 	struct hlist_node	cpuhp_dead;
Signature · 1 line
2.53.0-Meta
#6 lore raw

RFC PATCH v5 3/3 iommu/iova: add KUnit test suite

In reply to Rik van Riel

Add a KUnit suite for the maple tree based allocator, plus an iova_domain_verify_invariants() helper, built only with the test config, that walks the tree and checks that every entry's pfn_lo and pfn_hi match its index range and that no two entries overlap.

The cases cover size-aligned allocation across orders 0 to 7, top-down placement, reserved ranges, a 32-bit allocation in a filled 64-bit domain, arbitrary limit_pfn values, allocation into a fragmented space, and the 32-bit-first with 64-bit fallback pattern from dma-iommu.c.

test_stress_random runs 2048 random allocations and frees with mixed sizes, alignments and DMA limits, checking the invariants after each operation, from a fixed seed so a failure reproduces across boots.

Two cases fill the space and then time an allocation that has to fail, which with the rbtree meant walking every entry.

A test hook in remove_iova() forces the GFP_ATOMIC erase to fail, so the suite can check that the IOVA_DEFERRED marker keeps the range reserved and that iova_drain_deferred() hands it back.

remove_iova() also relies on that marker store not failing in turn, since it frees the struct iova while the tree still holds the range.

The guarantee comes from the maple tree. mas_wr_extend_null() widens a NULL store over the neighbouring free ranges, and the wider store may need a node. A non-NULL value over the entry's own range is never widened, so it is an exact fit needing none.

iova_kunit_store_types() reports the store type picked for erasing an iova and for marking it deferred. test_marker_store_needs_no_node() drives it over an iova with free neighbours on both sides: erasing is not an exact fit, marking is, and marking asks for no nodes.

A change to the store-type rules then fails a test rather than reaching a WARN whose only recovery is to strand an address range.

Run with:
tools/testing/kunit/kunit.py run --kunitconfig=drivers/iommu

Assisted-by Claude:claude-opus-4-8
---
 drivers/iommu/.kunitconfig |   6 +
 drivers/iommu/Kconfig      |  16 ++
 drivers/iommu/Makefile     |   1 +
 drivers/iommu/iova-kunit.c | 544 +++++++++++++++++++++++++++++++++++++
 drivers/iommu/iova.c       |  87 +++++-
 include/linux/iova.h       |   8 +
 6 files changed, 661 insertions(+), 1 deletion(-)
 create mode 100644 drivers/iommu/.kunitconfig
 create mode 100644 drivers/iommu/iova-kunit.c
drivers/iommu/.kunitconfig new file +6 -0
new file mode 100644
index 000000000000..d2bb924b1883
@@ -0,0 +1,6 @@
+CONFIG_KUNIT=y
+CONFIG_IOMMU_SUPPORT=y
+CONFIG_IOMMU_IOVA=y
+CONFIG_IOMMU_IOVA_KUNIT_TEST=y
+CONFIG_KASAN=y
+CONFIG_KASAN_GENERIC=y
drivers/iommu/Kconfig +16 -0
index 6e07bd69467a..904e04aeae21 100644
@@ -3,6 +3,22 @@
 config IOMMU_IOVA
 	tristate
 
+config IOMMU_IOVA_KUNIT_TEST
+	tristate "KUnit tests for the IOVA allocator" if !KUNIT_ALL_TESTS
+	depends on IOMMU_IOVA && KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  Enable kunit tests for the IOVA allocator. The tests exercise
+	  basic allocation and free, size-aligned allocation, top-down
+	  ordering, bounded allocations with various DMA limits (32-bit,
+	  33-bit, 56-bit), aligned allocations in fragmented domains,
+	  and randomly-fragmented stress scenarios.
+
+	  Run with:
+	    tools/testing/kunit/kunit.py run --kunitconfig=drivers/iommu
+
+	  If unsure, say N here.
+
 # IOMMU_API always gets selected by whoever wants it.
 config IOMMU_API
 	bool
drivers/iommu/Makefile +1 -0
index 2f05725eaab1..0b533911f25f 100644
@@ -17,6 +17,7 @@ obj-$(CONFIG_IOMMU_IO_PGTABLE_LPAE) += io-pgtable-arm.o
 obj-$(CONFIG_IOMMU_IO_PGTABLE_LPAE_KUNIT_TEST) += io-pgtable-arm-selftests.o
 obj-$(CONFIG_IOMMU_IO_PGTABLE_DART) += io-pgtable-dart.o
 obj-$(CONFIG_IOMMU_IOVA) += iova.o
+obj-$(CONFIG_IOMMU_IOVA_KUNIT_TEST) += iova-kunit.o
 obj-$(CONFIG_OF_IOMMU)	+= of_iommu.o
 obj-$(CONFIG_MSM_IOMMU) += msm_iommu.o
 obj-$(CONFIG_IPMMU_VMSA) += ipmmu-vmsa.o
drivers/iommu/iova-kunit.c new file +544 -0

544 lines not on this page · raw message

drivers/iommu/iova.c +86 -1

105 lines not on this page · raw message

include/linux/iova.h +8 -0
index e17bb1e85838..3aef263d0898 100644
@@ -101,6 +101,14 @@ void init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 int iova_domain_init_rcaches(struct iova_domain *iovad);
 struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn);
 void put_iova_domain(struct iova_domain *iovad);
+#if IS_ENABLED(CONFIG_IOMMU_IOVA_KUNIT_TEST)
+bool iova_domain_verify_invariants(struct iova_domain *iovad);
+bool iova_domain_has_deferred(struct iova_domain *iovad);
+extern bool iova_kunit_defer_erase;
+void iova_kunit_store_types(struct iova_domain *iovad, struct iova *iova,
+			    enum store_type *erase, enum store_type *marker,
+			    unsigned char *marker_nodes);
+#endif
 #else
 static inline int iova_cache_get(void)
 {
Signature · 1 line
2.53.0-Meta
#7 lore raw
In reply to Rik van Riel
Quoted 5 lines · Rik van Riel

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?

Quoted 80 lines

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/[email protected]

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

Signature · 3 lines
/ashok.raj
[email protected]
Qualcomm Inc
#8 lore raw
Quoted 10 lines · Ashok Raj
Quoted 8 lines · Rik van Riel

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.

Quoted 3 lines

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

Signature · 1 line
All Rights Reversed.
#9 lore raw
Quoted 15 lines · Rik van Riel
Quoted 10 lines · Ashok Raj
Quoted 8 lines · Rik van Riel

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.

Quoted 3 lines

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

Quoted 7 lines

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.

Quoted 6 lines

kind regards,

Rik

Signature · 1 line
All Rights Reversed.
Signature · 3 lines
/ashok.raj
[email protected]
Qualcomm Inc
maintainer
#10 lore raw
In reply to Rik van Riel

Hi Rik,

Quoted 7 lines · Rik van Riel

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.

Quoted 17 lines

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.

Quoted 8 lines

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

Tested-by
#11 lore raw
Quoted 50 lines · Jörg Rödel

Hi Rik,

Quoted 7 lines · Rik van Riel

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.

Quoted 17 lines

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.

Quoted 8 lines

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

Quoted 5 lines

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.

Thanks,
Ankit

maintainer
#12 lore raw

Hi Ankit,

Quoted 8 lines · Ankit Soni

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.

Thanks for providing these numbers, this is very helpful.

-Joerg