[PATCH v3 0/3] iova: use maple tree for O(log n) allocation

[PATCH v3 0/3] iova: use maple tree for O(log n) allocation

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

With the old code, free_iova, find_iova, reserve_iova, iova_insert_rbtree,
and remove_iova were all O(log n) already. They stay that way with these
patches.

This patch series uses a maple tree to index the iova ranges.
This allows alloc_iova() to have O(log n) complexity, while
memory use stays about the same as before.

It also adds some self tests for the iova code.

The code was written by Claude, and nitpicked by myself.
Don't be shy if there are more nitpicks remaining.

It was tested both in a VM (running the selftests), and on an
AMD Bergamo system with IOMMU enabled.

Unfortunately I do not know of any way to reproduce the linear
search soft lockups at will, so I have not been able to verify
that scenary in practice.

Based on 5d6919055dec Linux 7.1-rc3

v3:
 - switch to maple tree (suggested by Robin Murphy)
v2:
 - clean up selftests (thanks Jason Gunthorpe)
 - address Sashiko concerns
 - 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

[PATCH v3 1/3] iova: convert from rbtree to maple tree

[Rik van Riel]

From: Rik van Riel <riel@meta.com>

Replace the hand-rolled rbtree in the IOVA allocator with a maple tree.
The maple tree is a B-tree variant designed for range tracking with
built-in gap searching, making it a natural fit for IOVA address space
management -- the same data structure is used by the kernel VMA
subsystem for the analogous problem.

Key changes:

  - struct iova shrinks from 40 bytes (rb_node 24 + pfn_hi 8 + pfn_lo 8)
    to just pfn_hi + pfn_lo (16 bytes). SLAB_HWCACHE_ALIGN is dropped
    from the iova slab cache since struct iova no longer contains an
    embedded rb_node touched during tree rebalancing -- tree traversal
    now touches maple nodes exclusively. This lets the slab allocator
    pack 16-byte objects tightly instead of rounding to 64 bytes.

    The maple tree replaces the embedded rb_node with external B-tree
    nodes: each maple_arange_64 node is 256 bytes and holds up to 10
    entries, plus internal nodes add ~11% overhead. At typical
    utilization (~70-90% full), this works out to ~28-41 bytes of maple
    tree node memory per IOVA entry. The net per-entry cost is ~44-57
    bytes (16 bytes slab + ~28-41 bytes maple), compared to ~64 bytes
    with the old rbtree (64 bytes HWCACHE_ALIGN slab + 0 bytes
    embedded rbtree). Combined with the maple tree's O(log_10 n)
    search depth and better cache locality from B-tree fan-out,
    this improves both memory efficiency and search performance.

  - struct iova_domain replaces rb_root + cached_node + cached32_node
    + anchor with a single struct maple_tree. The iova_rbtree_lock
    spinlock is renamed to iova_lock. The maple tree is initialized
    with MT_FLAGS_ALLOC_RANGE (enables gap tracking for
    mas_empty_area_rev) and MT_FLAGS_LOCK_EXTERN (uses the existing
    iova_lock spinlock instead of the maple tree internal lock).

  - Allocation via __alloc_and_insert_iova_range() uses
    mas_empty_area_rev() to find the highest-addressed gap of
    sufficient size below limit_pfn in O(log n) with B-tree fan-out.
    Alignment is handled by over-requesting (size + alignment - 1)
    to guarantee room after rounding, eliminating the need for a
    retry loop. The result is stored with mas_store_gfp().

  - Lookup via private_find_iova() uses mas_walk() for O(log n)
    point-in-range lookup.

  - Deletion via remove_iova() uses mas_erase(). No successor gap
    fixup needed -- the maple tree handles it internally.

  - reserve_iova() walks the requested range for existing entries,
    computes the merged range, collects old entries for freeing, then
    stores a single merged entry. If the request is fully covered by
    an existing entry, it returns that entry without allocating.

  - The IOVA_ANCHOR sentinel node is eliminated. The maple tree
    tracks gaps implicitly, including the space above the highest
    allocation.

  - The cached_node / cached32_node fields and all their helpers
    are eliminated. The maple tree B-tree structure provides
    equivalent or better cache behaviour.

The rcache (magazine cache) layer is unchanged -- it operates on raw
pfn values and is orthogonal to the tree backing store.

Assisted-by: Claude:claude-opus-4-6
Signed-off-by: Rik van Riel <riel@surriel.com>
Suggested-by: Robin Murphy <robin.murphy@arm.com>
---
 drivers/iommu/iova.c | 338 ++++++++++++-------------------------------
 include/linux/iova.h |  10 +-
 2 files changed, 98 insertions(+), 250 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 021daf6528de..523d1e8315f9 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -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,63 @@ 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);
+	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);
 	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;
+	if (mas_empty_area_rev(&mas, iovad->start_pfn,
+				 limit_pfn - 1, search_size))
+		goto alloc_fail;
 
-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;
-	}
+	new_pfn = (mas.last - size + 1) & align_mask;
+	if (new_pfn < mas.index || new_pfn < iovad->start_pfn)
+		goto alloc_fail;
 
-	/* pfn_lo will point to size aligned address if size_aligned is set */
 	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;
 
+alloc_fail:
+	if (limit_pfn <= iovad->dma_32bit_pfn)
+		iovad->max32_alloc_size = size;
 iova32_full:
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return -ENOMEM;
 }
 
@@ -233,8 +109,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 +150,22 @@ 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;
+	MA_STATE(mas, &iovad->mtree, pfn, pfn);
 
-	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 */
-	}
-
-	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;
+
+	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
 }
 
 /**
@@ -312,10 +180,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,9 +198,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);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	free_iova_mem(iova);
 }
 EXPORT_SYMBOL_GPL(__free_iova);
@@ -351,14 +218,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);
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	free_iova_mem(iova);
 }
 EXPORT_SYMBOL_GPL(free_iova);
@@ -445,27 +312,18 @@ static void iova_domain_free_rcaches(struct iova_domain *iovad)
  */
 void put_iova_domain(struct iova_domain *iovad)
 {
-	struct iova *iova, *tmp;
+	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)
+	mas_for_each(&mas, iova, ULONG_MAX)
 		free_iova_mem(iova);
+	__mt_destroy(&iovad->mtree);
 }
 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,29 +338,6 @@ 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)
-{
-	struct iova *iova;
-
-	iova = alloc_and_init_iova(pfn_lo, pfn_hi);
-	if (iova)
-		iova_insert_rbtree(&iovad->rbroot, iova, NULL);
-
-	return iova;
-}
-
-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;
-}
-
 /**
  * reserve_iova - reserves an iova in the given range
  * @iovad: - iova domain pointer
@@ -510,41 +345,58 @@ __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 flags;
-	struct iova *iova;
-	unsigned int overlap = 0;
+	struct iova *iova, *overlap;
+	unsigned long merged_lo = pfn_lo, merged_hi = pfn_hi;
 
 	/* 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);
+	{
+		MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
+
+		mas_for_each(&mas, overlap, pfn_hi) {
+			if (pfn_lo >= overlap->pfn_lo &&
+			    pfn_hi <= overlap->pfn_hi) {
+				spin_unlock_irqrestore(&iovad->iova_lock,
+						       flags);
+				return overlap;
+			}
+			if (overlap->pfn_lo < merged_lo)
+				merged_lo = overlap->pfn_lo;
+			if (overlap->pfn_hi > merged_hi)
+				merged_hi = overlap->pfn_hi;
+			free_iova_mem(overlap);
+		}
 	}
 
-	/* We are here either because this is the first reserver node
-	 * or need to insert remaining non overlap addr range
-	 */
-	iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
-finish:
+	iova = alloc_and_init_iova(merged_lo, merged_hi);
+	if (!iova) {
+		spin_unlock_irqrestore(&iovad->iova_lock, flags);
+		return NULL;
+	}
+
+	{
+		MA_STATE(mas, &iovad->mtree, merged_lo, merged_hi);
 
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+		if (mas_store_gfp(&mas, iova, GFP_ATOMIC)) {
+			spin_unlock_irqrestore(&iovad->iova_lock, flags);
+			free_iova_mem(iova);
+			return NULL;
+		}
+	}
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 	return iova;
 }
 EXPORT_SYMBOL_GPL(reserve_iova);
@@ -621,7 +473,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 +485,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 +808,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;
 
diff --git a/include/linux/iova.h b/include/linux/iova.h
index d2c4fd923efa..eb4f9ead5451 100644
--- a/include/linux/iova.h
+++ b/include/linux/iova.h
@@ -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;	/* Lock to protect update of 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;
-- 
2.54.0

Re: [PATCH v3 1/3] iova: convert from rbtree to maple tree

[Liam R. Howlett]

On 26/06/02 11:35PM, Rik van Riel wrote:
> From: Rik van Riel <riel@meta.com>
> 
> Replace the hand-rolled rbtree in the IOVA allocator with a maple tree.
> The maple tree is a B-tree variant designed for range tracking with
> built-in gap searching, making it a natural fit for IOVA address space
> management -- the same data structure is used by the kernel VMA
> subsystem for the analogous problem.
> 
> Key changes:
> 
>   - struct iova shrinks from 40 bytes (rb_node 24 + pfn_hi 8 + pfn_lo 8)
>     to just pfn_hi + pfn_lo (16 bytes). SLAB_HWCACHE_ALIGN is dropped
>     from the iova slab cache since struct iova no longer contains an
>     embedded rb_node touched during tree rebalancing -- tree traversal
>     now touches maple nodes exclusively. This lets the slab allocator
>     pack 16-byte objects tightly instead of rounding to 64 bytes.
> 
>     The maple tree replaces the embedded rb_node with external B-tree
>     nodes: each maple_arange_64 node is 256 bytes and holds up to 10
>     entries, plus internal nodes add ~11% overhead. At typical
>     utilization (~70-90% full), this works out to ~28-41 bytes of maple
>     tree node memory per IOVA entry. The net per-entry cost is ~44-57
>     bytes (16 bytes slab + ~28-41 bytes maple), compared to ~64 bytes
>     with the old rbtree (64 bytes HWCACHE_ALIGN slab + 0 bytes
>     embedded rbtree). Combined with the maple tree's O(log_10 n)
>     search depth and better cache locality from B-tree fan-out,
>     this improves both memory efficiency and search performance.
> 
>   - struct iova_domain replaces rb_root + cached_node + cached32_node
>     + anchor with a single struct maple_tree. The iova_rbtree_lock
>     spinlock is renamed to iova_lock. The maple tree is initialized
>     with MT_FLAGS_ALLOC_RANGE (enables gap tracking for
>     mas_empty_area_rev) and MT_FLAGS_LOCK_EXTERN (uses the existing
>     iova_lock spinlock instead of the maple tree internal lock)there .

If the spinlock is only used to protect the tree, why are you using an
external lock?

> 
>   - Allocation via __alloc_and_insert_iova_range() uses
>     mas_empty_area_rev() to find the highest-addressed gap of
>     sufficient size below limit_pfn in O(log n) with B-tree fan-out.
>     Alignment is handled by over-requesting (size + alignment - 1)
>     to guarantee room after rounding, eliminating the need for a
>     retry loop. The result is stored with mas_store_gfp().
> 
>   - Lookup via private_find_iova() uses mas_walk() for O(log n)
>     point-in-range lookup.
> 
>   - Deletion via remove_iova() uses mas_erase(). No successor gap
>     fixup needed -- the maple tree handles it internally.
> 
>   - reserve_iova() walks the requested range for existing entries,
>     computes the merged range, collects old entries for freeing, then
>     stores a single merged entry. If the request is fully covered by
>     an existing entry, it returns that entry without allocating.
> 
>   - The IOVA_ANCHOR sentinel node is eliminated. The maple tree
>     tracks gaps implicitly, including the space above the highest
>     allocation.
> 
>   - The cached_node / cached32_node fields and all their helpers
>     are eliminated. The maple tree B-tree structure provides
>     equivalent or better cache behaviour.
> 
> The rcache (magazine cache) layer is unchanged -- it operates on raw
> pfn values and is orthogonal to the tree backing store.
> 
> Assisted-by: Claude:claude-opus-4-6
> Signed-off-by: Rik van Riel <riel@surriel.com>
> Suggested-by: Robin Murphy <robin.murphy@arm.com>
> ---
>  drivers/iommu/iova.c | 338 ++++++++++++-------------------------------
>  include/linux/iova.h |  10 +-
>  2 files changed, 98 insertions(+), 250 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index 021daf6528de..523d1e8315f9 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -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,63 @@ 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);
> +	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);
>  	if (limit_pfn <= iovad->dma_32bit_pfn &&
>  			size >= iovad->max32_alloc_size)
>  		goto iova32_full;

This check seems to ensure the request is either both 32bit safe or it's
fine to pass.  If a 64bit allocation uses a larger size and we fail
later, aren't we overwriting the 32bit size safety in your alloc_fail
label?  It seems wrong to be changing the max32_alloc_size in the error
recovery.

This also could happen outside the spinlock?  I'm not sure why it was
inside to begin with.

>  
> -	curr = __get_cached_rbnode(iovad, limit_pfn);
> -	curr_iova = to_iova(curr);
> -	retry_pfn = curr_iova->pfn_hi;
> +	if (mas_empty_area_rev(&mas, iovad->start_pfn,
> +				 limit_pfn - 1, search_size))
> +		goto alloc_fail;
>  
> -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;
> -	}
> +	new_pfn = (mas.last - size + 1) & align_mask;
> +	if (new_pfn < mas.index || new_pfn < iovad->start_pfn)
> +		goto alloc_fail;

Neither of these can ever happen..?  You've searched for a gap that's
the worst case alignment and now you're ensuring the offset off the end
aligned isn't smaller than the start of the gap or the end of your
search.  I'm no LLM, I don't think this is possible.

>  
> -	/* pfn_lo will point to size aligned address if size_aligned is set */
>  	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;
>  
> +alloc_fail:
> +	if (limit_pfn <= iovad->dma_32bit_pfn)
> +		iovad->max32_alloc_size = size;
>  iova32_full:
> -	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>  	return -ENOMEM;
>  }
>  
> @@ -233,8 +109,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 +150,22 @@ 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;
> +	MA_STATE(mas, &iovad->mtree, pfn, pfn);
>  
> -	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 */
> -	}
> -
> -	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;
> +
> +	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
>  }
>  
>  /**
> @@ -312,10 +180,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,9 +198,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);
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>  	free_iova_mem(iova);
>  }
>  EXPORT_SYMBOL_GPL(__free_iova);
> @@ -351,14 +218,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);
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>  	free_iova_mem(iova);
>  }
>  EXPORT_SYMBOL_GPL(free_iova);
> @@ -445,27 +312,18 @@ static void iova_domain_free_rcaches(struct iova_domain *iovad)
>   */
>  void put_iova_domain(struct iova_domain *iovad)
>  {
> -	struct iova *iova, *tmp;
> +	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)
> +	mas_for_each(&mas, iova, ULONG_MAX)
>  		free_iova_mem(iova);
> +	__mt_destroy(&iovad->mtree);
>  }
>  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,29 +338,6 @@ 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)
> -{
> -	struct iova *iova;
> -
> -	iova = alloc_and_init_iova(pfn_lo, pfn_hi);
> -	if (iova)
> -		iova_insert_rbtree(&iovad->rbroot, iova, NULL);
> -
> -	return iova;
> -}
> -
> -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;
> -}
> -
>  /**
>   * reserve_iova - reserves an iova in the given range
>   * @iovad: - iova domain pointer
> @@ -510,41 +345,58 @@ __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 flags;
> -	struct iova *iova;
> -	unsigned int overlap = 0;
> +	struct iova *iova, *overlap;
> +	unsigned long merged_lo = pfn_lo, merged_hi = pfn_hi;
>  
>  	/* 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);
> +	{
> +		MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);

You might want to look at mas_init() instead of the extra tab block.

> +
> +		mas_for_each(&mas, overlap, pfn_hi) {
> +			if (pfn_lo >= overlap->pfn_lo &&
> +			    pfn_hi <= overlap->pfn_hi) {
> +				spin_unlock_irqrestore(&iovad->iova_lock,
> +						       flags);
> +				return overlap;
> +			}
> +			if (overlap->pfn_lo < merged_lo)
> +				merged_lo = overlap->pfn_lo;
> +			if (overlap->pfn_hi > merged_hi)
> +				merged_hi = overlap->pfn_hi;
> +			free_iova_mem(overlap);
> +		}
>  	}
>  
> -	/* We are here either because this is the first reserver node
> -	 * or need to insert remaining non overlap addr range
> -	 */
> -	iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
> -finish:
> +	iova = alloc_and_init_iova(merged_lo, merged_hi);
> +	if (!iova) {
> +		spin_unlock_irqrestore(&iovad->iova_lock, flags);
> +		return NULL;

                A goto the same repeated block below might be in order?

> +	}
> +
> +	{
> +		MA_STATE(mas, &iovad->mtree, merged_lo, merged_hi);
>  
> -	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);

The maple state keeps track of where things are, so if you have a maple
state pointing at the correct slot, then you can avoid rewalking the
tree.  This is rather complicated, but it will save you a hand full of
dereferences if you need them.

> +		if (mas_store_gfp(&mas, iova, GFP_ATOMIC)) {
> +			spin_unlock_irqrestore(&iovad->iova_lock, flags);
> +			free_iova_mem(iova);
> +			return NULL;
> +		}
> +	}
> +	spin_unlock_irqrestore(&iovad->iova_lock, flags);
>  	return iova;
>  }
>  EXPORT_SYMBOL_GPL(reserve_iova);
> @@ -621,7 +473,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 +485,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 +808,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);

Was this in the patch notes or expected to change?

>  		if (!iova_cache)
>  			goto out_err;
>  
> diff --git a/include/linux/iova.h b/include/linux/iova.h
> index d2c4fd923efa..eb4f9ead5451 100644
> --- a/include/linux/iova.h
> +++ b/include/linux/iova.h
> @@ -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;	/* Lock to protect update of 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;
> -- 
> 2.54.0
> 
> 

Re: [PATCH v3 1/3] iova: convert from rbtree to maple tree

[Rik van Riel]

On Wed, 2026-06-17 at 15:55 -0400, Liam R. Howlett wrote:
> On 26/06/02 11:35PM, Rik van Riel wrote:
> > From: Rik van Riel <riel@meta.com>
> > 
> >   - struct iova_domain replaces rb_root + cached_node +
> > cached32_node
> >     + anchor with a single struct maple_tree. The iova_rbtree_lock
> >     spinlock is renamed to iova_lock. The maple tree is initialized
> >     with MT_FLAGS_ALLOC_RANGE (enables gap tracking for
> >     mas_empty_area_rev) and MT_FLAGS_LOCK_EXTERN (uses the existing
> >     iova_lock spinlock instead of the maple tree internal
> > lock)there .
> 
> If the spinlock is only used to protect the tree, why are you using
> an
> external lock?

The IOVA code needs an irqsafe lock, but the lock also
protects some other things like iovad->max32_alloc_size,
and the failed-to-rebalance-deferred free list from patch 3.

Implementing something behind the MT_FLAGS_LOCK_IRQ
would address the first thing, but not the second.

> 
> >  
> > -	/* Walk the tree backwards */
> > -	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
> > +	spin_lock_irqsave(&iovad->iova_lock, flags);
> >  	if (limit_pfn <= iovad->dma_32bit_pfn &&
> >  			size >= iovad->max32_alloc_size)
> >  		goto iova32_full;
> 
> This check seems to ensure the request is either both 32bit safe or
> it's
> fine to pass.  If a 64bit allocation uses a larger size and we fail
> later, aren't we overwriting the 32bit size safety in your alloc_fail
> label?  It seems wrong to be changing the max32_alloc_size in the
> error
> recovery.
> 
> This also could happen outside the spinlock?  I'm not sure why it was
> inside to begin with.

Good eyes. There's a bug here. While the iova32_full
code already has a limit_pfn check, we could also end
up there because the GFP_ATOMIC allocation failed,
turning a temporary failure into a permanent one.

This will be fixed for v4.

> 
> > +	new_pfn = (mas.last - size + 1) & align_mask;
> > +	if (new_pfn < mas.index || new_pfn < iovad->start_pfn)
> > +		goto alloc_fail;
> 
> Neither of these can ever happen..?  You've searched for a gap that's
> the worst case alignment and now you're ensuring the offset off the
> end
> aligned isn't smaller than the start of the gap or the end of your
> search.  I'm no LLM, I don't think this is possible.

I'll drop these for v4.

> > +	spin_lock_irqsave(&iovad->iova_lock, flags);
> > +	{
> > +		MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
> 
> You might want to look at mas_init() instead of the extra tab block.
> 

That is nicer. Thank you.

> > -	/* We are here either because this is the first reserver
> > node
> > -	 * or need to insert remaining non overlap addr range
> > -	 */
> > -	iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
> > -finish:
> > +	iova = alloc_and_init_iova(merged_lo, merged_hi);
> > +	if (!iova) {
> > +		spin_unlock_irqrestore(&iovad->iova_lock, flags);
> > +		return NULL;
> 
>                 A goto the same repeated block below might be in
> order?
> 
Fixed for v4.

> > +	}
> > +
> > +	{
> > +		MA_STATE(mas, &iovad->mtree, merged_lo,
> > merged_hi);
> >  
> > -	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
> 
> The maple state keeps track of where things are, so if you have a
> maple
> state pointing at the correct slot, then you can avoid rewalking the
> tree.  This is rather complicated, but it will save you a hand full
> of
> dereferences if you need them.

This code is for the overlap case, where a new
iova mapping is explicitly set to overlap already
existing mappings.

This makes the maple tree logic even more complex,
and I'm not sure whether this case is common enough
to justify that.

> 
> > @@ -956,8 +808,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);
> 
> Was this in the patch notes or expected to change?

This change is what reduces the allocated size of the
iova struct from 64 bytes to 16 bytes.

That seems desired, and potentially important for
some users.

I believe I also covered it in the changelog.

-- 
All Rights Reversed.

[PATCH v3 2/3] iova: add KUnit test suite

[Rik van Riel]

From: Rik van Riel <riel@meta.com>

Add a kunit suite for the maple-tree-based IOVA allocator, plus an
iova_domain_verify_invariants() helper (compiled only when the test
config is enabled) that walks the maple tree and confirms every entry's
pfn_lo/pfn_hi match the maple tree index range and that no entries
overlap.

Test cases:
  - test_size_aligned: alignment of size_aligned allocs across orders 0..7.
  - test_top_down_preference: sequential allocs decrease in pfn_lo.
  - test_reserve_iova: allocs avoid the reserved range.
  - test_32bit_in_64bit_domain: 1000 64-bit allocs followed by a 32-bit
    alloc must still find a slot below DMA_BIT_MASK(32).
  - test_arbitrary_dma_limits: after filling 64-bit space, verify that
    bounded allocations at 33-bit and 56-bit limits still find slots
    within their respective ranges, confirming that mas_empty_area_rev
    generalizes to arbitrary limit_pfn values.
  - test_aligned_in_fragmented: pack size-2 size_aligned allocs, free
    every other to leave size-2 holes; a fresh size-2 aligned alloc
    must still succeed and return a 2-aligned pfn.
  - test_pci_32bit_workaround_pattern: alternate 32-bit-first allocation
    attempts with 64-bit fallback, mirroring dma-iommu.c.
  - test_stress_random: 2048 random alloc/free operations with mixed
    sizes, alignments, and DMA limits (32/33/56/64-bit), checking
    invariants after every operation. Uses a deterministic PRNG so
    failures reproduce across boots.
  - test_full_space_search_time: fill a 16K-pfn range completely, then
    verify that a failed alloc returns in bounded time (O(log n) via
    mas_empty_area_rev, not O(n)).
  - test_fragmented_32bit_search: pack the 32-bit IOVA space, then
    verify bounded search time for both 32-bit failure and 64-bit
    fallback success paths.

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

Assisted-by: Claude:claude-opus-4-6
Signed-off-by: Rik van Riel <riel@surriel.com>
---
 drivers/iommu/.kunitconfig |   4 +
 drivers/iommu/Kconfig      |  16 ++
 drivers/iommu/Makefile     |   1 +
 drivers/iommu/iova-kunit.c | 432 +++++++++++++++++++++++++++++++++++++
 drivers/iommu/iova.c       |  34 +++
 include/linux/iova.h       |   3 +
 6 files changed, 490 insertions(+)
 create mode 100644 drivers/iommu/.kunitconfig
 create mode 100644 drivers/iommu/iova-kunit.c

diff --git a/drivers/iommu/.kunitconfig b/drivers/iommu/.kunitconfig
new file mode 100644
index 000000000000..56b481ecf993
--- /dev/null
+++ b/drivers/iommu/.kunitconfig
@@ -0,0 +1,4 @@
+CONFIG_KUNIT=y
+CONFIG_IOMMU_SUPPORT=y
+CONFIG_IOMMU_IOVA=y
+CONFIG_IOMMU_IOVA_KUNIT_TEST=y
diff --git a/drivers/iommu/Kconfig b/drivers/iommu/Kconfig
index f86262b11416..f09046e238fd 100644
--- a/drivers/iommu/Kconfig
+++ b/drivers/iommu/Kconfig
@@ -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
diff --git a/drivers/iommu/Makefile b/drivers/iommu/Makefile
index 0275821f4ef9..6bd7da1cbebd 100644
--- a/drivers/iommu/Makefile
+++ b/drivers/iommu/Makefile
@@ -16,6 +16,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
diff --git a/drivers/iommu/iova-kunit.c b/drivers/iommu/iova-kunit.c
new file mode 100644
index 000000000000..fffeab8552cd
--- /dev/null
+++ b/drivers/iommu/iova-kunit.c
@@ -0,0 +1,432 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for the IOVA allocator.
+ *
+ * Exercises the maple-tree-based allocator: basic alloc/free,
+ * size-aligned allocations, top-down ordering, bounded allocations
+ * with various DMA limits (32-bit, 33-bit, 56-bit), aligned
+ * allocations in fragmented domains, and randomly fragmented stress.
+ *
+ * Each test verifies that the maple tree invariants remain consistent
+ * after every batch of operations.
+ */
+#include <kunit/test.h>
+#include <linux/dma-mapping.h>
+#include <linux/iova.h>
+
+#define TEST_GRANULE PAGE_SIZE
+/* Highest pfn that fits in 32 bits — triggers the bounded alloc path. */
+#define TEST_LIMIT_32BIT (DMA_BIT_MASK(32) >> PAGE_SHIFT)
+/* 33-bit limit — exercises non-power-of-two DMA boundaries. */
+#define TEST_LIMIT_33BIT (DMA_BIT_MASK(33) >> PAGE_SHIFT)
+/* 56-bit limit — typical server IOMMU address width. */
+#define TEST_LIMIT_56BIT (DMA_BIT_MASK(56) >> PAGE_SHIFT)
+/* A 64-bit-ish limit well above dma_32bit_pfn. 1ULL avoids UB on ILP32. */
+#define TEST_LIMIT_64BIT ((1ULL << 36) >> PAGE_SHIFT)
+/*
+ * A small <=32-bit limit used by tests that want to actually exhaust the
+ * restricted region within a tractable number of allocations.
+ */
+#define TEST_LIMIT_32BIT_RESTRICTED (TEST_LIMIT_32BIT / 2)
+
+struct iova_test_ctx {
+	struct iova_domain iovad;
+	bool initialized;
+};
+
+static int iova_test_init(struct kunit *test)
+{
+	struct iova_test_ctx *ctx;
+	int ret;
+
+	ctx = kunit_kzalloc(test, sizeof(*ctx), GFP_KERNEL);
+	if (!ctx)
+		return -ENOMEM;
+	test->priv = ctx;
+
+	ret = iova_cache_get();
+	if (ret)
+		return ret;
+
+	init_iova_domain(&ctx->iovad, TEST_GRANULE, 1);
+	ret = iova_domain_init_rcaches(&ctx->iovad);
+	if (ret) {
+		put_iova_domain(&ctx->iovad);
+		iova_cache_put();
+		return ret;
+	}
+	ctx->initialized = true;
+
+	KUNIT_ASSERT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+	return 0;
+}
+
+static void iova_test_exit(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+
+	if (ctx && ctx->initialized) {
+		put_iova_domain(&ctx->iovad);
+		ctx->initialized = false;
+		iova_cache_put();
+	}
+}
+
+static void test_size_aligned(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	int order;
+
+	for (order = 0; order < 8; ++order) {
+		unsigned long size = 1UL << order;
+		struct iova *iova = alloc_iova(&ctx->iovad, size,
+					       TEST_LIMIT_32BIT, true);
+
+		KUNIT_ASSERT_NOT_NULL(test, iova);
+		KUNIT_EXPECT_EQ(test, iova->pfn_lo & (size - 1), 0);
+		KUNIT_EXPECT_EQ(test, iova->pfn_hi - iova->pfn_lo + 1, size);
+		__free_iova(&ctx->iovad, iova);
+		KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+	}
+}
+
+static void test_top_down_preference(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	struct iova *iovas[16];
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(iovas); ++i) {
+		iovas[i] = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_32BIT, false);
+		KUNIT_ASSERT_NOT_NULL(test, iovas[i]);
+		if (i > 0)
+			KUNIT_EXPECT_LT(test, iovas[i]->pfn_lo,
+					iovas[i - 1]->pfn_lo);
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	for (i = 0; i < ARRAY_SIZE(iovas); ++i)
+		__free_iova(&ctx->iovad, iovas[i]);
+}
+
+static void test_reserve_iova(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	const unsigned long reserve_lo = TEST_LIMIT_32BIT / 2;
+	struct iova *r, *iova;
+	int i;
+
+	/* Reserve the entire top half through the limit_pfn, inclusive. */
+	r = reserve_iova(&ctx->iovad, reserve_lo, TEST_LIMIT_32BIT);
+	KUNIT_ASSERT_NOT_NULL(test, r);
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	/* All allocs must land below the reserved range. */
+	for (i = 0; i < 100; ++i) {
+		iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_32BIT, false);
+		KUNIT_ASSERT_NOT_NULL(test, iova);
+		KUNIT_EXPECT_LT(test, iova->pfn_hi, reserve_lo);
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+}
+
+/*
+ * The pci_32bit_workaround scenario: every PCI device's first IOVA
+ * allocation hits the 32-bit-restricted path before falling back to
+ * 64-bit. Fill the 64-bit space, then verify a 32-bit alloc still
+ * finds a slot below DMA_BIT_MASK(32).
+ */
+static void test_32bit_in_64bit_domain(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	struct iova *iova;
+	int i;
+
+	for (i = 0; i < 1000; ++i) {
+		iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_64BIT, true);
+		KUNIT_ASSERT_NOT_NULL(test, iova);
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_32BIT, true);
+	KUNIT_ASSERT_NOT_NULL(test, iova);
+	KUNIT_EXPECT_LE(test, iova->pfn_hi, TEST_LIMIT_32BIT);
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	__free_iova(&ctx->iovad, iova);
+}
+
+/*
+ * Exercise non-power-of-two DMA limits: fill the 64-bit space, then
+ * verify that bounded allocations at 33-bit and 56-bit limits still
+ * find slots within their respective ranges. This confirms the
+ * navigate-to-limit_pfn search generalizes beyond the 32-bit case.
+ */
+static void test_arbitrary_dma_limits(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	struct iova *iova;
+	int i;
+
+	for (i = 0; i < 1000; ++i) {
+		iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_64BIT, true);
+		KUNIT_ASSERT_NOT_NULL(test, iova);
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	/* 33-bit bounded allocation */
+	iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_33BIT, true);
+	KUNIT_ASSERT_NOT_NULL(test, iova);
+	KUNIT_EXPECT_LE(test, iova->pfn_hi, TEST_LIMIT_33BIT);
+	__free_iova(&ctx->iovad, iova);
+
+	/* 56-bit bounded allocation */
+	iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_56BIT, true);
+	KUNIT_ASSERT_NOT_NULL(test, iova);
+	KUNIT_EXPECT_LE(test, iova->pfn_hi, TEST_LIMIT_56BIT);
+	__free_iova(&ctx->iovad, iova);
+
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+}
+
+/*
+ * Aligned allocation in a fragmented domain: pack size-2 size_aligned
+ * allocations at the top, free every other one to leave size-2 holes,
+ * then verify a fresh size-2 aligned alloc still succeeds and returns
+ * a 2-aligned pfn.
+ */
+static void test_aligned_in_fragmented(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	const int N = 64;
+	struct iova **iovas;
+	struct iova *iova;
+	int i;
+
+	iovas = kunit_kcalloc(test, N, sizeof(*iovas), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, iovas);
+
+	for (i = 0; i < N; ++i) {
+		iovas[i] = alloc_iova(&ctx->iovad, 2, TEST_LIMIT_32BIT, true);
+		KUNIT_ASSERT_NOT_NULL(test, iovas[i]);
+		KUNIT_EXPECT_EQ(test, iovas[i]->pfn_lo & 1, 0);
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	for (i = 0; i < N; i += 2) {
+		__free_iova(&ctx->iovad, iovas[i]);
+		iovas[i] = NULL;
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	iova = alloc_iova(&ctx->iovad, 2, TEST_LIMIT_32BIT, true);
+	KUNIT_ASSERT_NOT_NULL(test, iova);
+	KUNIT_EXPECT_EQ(test, iova->pfn_lo & 1, 0);
+	__free_iova(&ctx->iovad, iova);
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+
+	for (i = 0; i < N; ++i)
+		if (iovas[i])
+			__free_iova(&ctx->iovad, iovas[i]);
+}
+
+/*
+ * Mimic dma-iommu's pci_32bit_workaround pattern: every alloc first
+ * tries a small restricted limit; if that fails, retry with the 64-bit
+ * limit. Verifies that the navigate-to-limit search survives rapid
+ * switching between different limit_pfn values.
+ */
+static void test_pci_32bit_workaround_pattern(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	int fallback_count = 0;
+	int i;
+
+	for (i = 0; i < 500; ++i) {
+		unsigned long size = (i % 4) + 1;
+		struct iova *iova = alloc_iova(&ctx->iovad, size,
+					       TEST_LIMIT_32BIT_RESTRICTED,
+					       true);
+
+		if (!iova) {
+			iova = alloc_iova(&ctx->iovad, size,
+					  TEST_LIMIT_64BIT, true);
+			fallback_count++;
+		}
+		if (!iova)
+			break;
+	}
+	KUNIT_EXPECT_TRUE(test, iova_domain_verify_invariants(&ctx->iovad));
+	KUNIT_EXPECT_GT(test, i, 0);
+}
+
+/*
+ * Random alloc/free over many iterations, verifying invariants after
+ * every operation. Uses a deterministic PRNG so failures reproduce
+ * across boots. Exercises mixed DMA limits (32, 33, 56, 64-bit).
+ */
+static void test_stress_random(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	const int N = 512;
+	const int iters = 4 * N;
+	const unsigned long limits[] = {
+		TEST_LIMIT_32BIT, TEST_LIMIT_33BIT,
+		TEST_LIMIT_56BIT, TEST_LIMIT_64BIT,
+	};
+	struct iova **iovas;
+	u32 rng = 0xDEADBEEF;
+	int i;
+
+	iovas = kunit_kcalloc(test, N, sizeof(*iovas), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, iovas);
+
+	for (i = 0; i < iters; ++i) {
+		int slot;
+		unsigned long limit;
+		const char *op;
+
+		rng = rng * 1103515245 + 12345;
+		slot = (rng >> 8) % N;
+		rng = rng * 1103515245 + 12345;
+		limit = limits[(rng >> 8) % ARRAY_SIZE(limits)];
+
+		if (iovas[slot]) {
+			op = "free";
+			__free_iova(&ctx->iovad, iovas[slot]);
+			iovas[slot] = NULL;
+		} else {
+			unsigned long size;
+			bool aligned;
+
+			rng = rng * 1103515245 + 12345;
+			size = 1UL << ((rng >> 8) % 4);
+			rng = rng * 1103515245 + 12345;
+			aligned = (rng >> 8) & 1;
+
+			op = "alloc";
+			iovas[slot] = alloc_iova(&ctx->iovad, size, limit,
+						 aligned);
+		}
+		if (!iova_domain_verify_invariants(&ctx->iovad)) {
+			kunit_info(test, "iter %d slot %d: invariant broken after %s\n",
+				   i, slot, op);
+			KUNIT_FAIL(test, "verify failed");
+			break;
+		}
+	}
+
+	for (i = 0; i < N; ++i)
+		if (iovas[i])
+			__free_iova(&ctx->iovad, iovas[i]);
+}
+
+/*
+ * Verify that alloc_iova fails in bounded time when the IOVA space is
+ * fully packed. Fill a 16K-pfn range with size-1 allocations (leaving
+ * no gaps), then attempt a size-2 aligned alloc. The maple tree's
+ * mas_empty_area_rev must determine there is no suitable gap in
+ * O(log n) time rather than walking every entry. The 10ms threshold
+ * is generous — real hardware watchdogs fire at ~10s.
+ */
+static void test_full_space_search_time(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	const unsigned long fill_limit = 16384;
+	const int fill_count = fill_limit;
+	struct iova *iova;
+	ktime_t start, elapsed;
+	int i, allocated = 0;
+
+	for (i = 0; i < fill_count; ++i) {
+		iova = alloc_iova(&ctx->iovad, 1, fill_limit, false);
+		if (!iova)
+			break;
+		allocated++;
+	}
+	kunit_info(test, "allocated %d iovas in [1, %lu]\n",
+		   allocated, fill_limit);
+	KUNIT_ASSERT_GT(test, allocated, 1000);
+
+	start = ktime_get();
+	iova = alloc_iova(&ctx->iovad, 2, fill_limit, true);
+	elapsed = ktime_sub(ktime_get(), start);
+
+	KUNIT_EXPECT_NULL(test, iova);
+	kunit_info(test, "failed alloc took %lld ns\n",
+		   ktime_to_ns(elapsed));
+	KUNIT_EXPECT_LT(test, ktime_to_ns(elapsed), 10000000LL);
+
+	if (iova)
+		__free_iova(&ctx->iovad, iova);
+}
+
+/*
+ * Verify bounded search time with a fragmented 32-bit IOVA space.
+ * Pack the 32-bit range with size-1 allocs, then attempt a large
+ * aligned alloc that must either succeed from a remaining gap or
+ * fail fast. The 64-bit fallback must always succeed promptly.
+ */
+static void test_fragmented_32bit_search(struct kunit *test)
+{
+	struct iova_test_ctx *ctx = test->priv;
+	struct iova *iova;
+	ktime_t start, elapsed;
+	int i, allocated = 0;
+
+	for (i = 0; i < 8000; ++i) {
+		iova = alloc_iova(&ctx->iovad, 1, TEST_LIMIT_32BIT, false);
+		if (!iova)
+			break;
+		allocated++;
+	}
+	kunit_info(test, "filled 32-bit space with %d allocs\n", allocated);
+	KUNIT_ASSERT_GT(test, allocated, 1000);
+
+	start = ktime_get();
+	iova = alloc_iova(&ctx->iovad, 32, TEST_LIMIT_32BIT, true);
+	elapsed = ktime_sub(ktime_get(), start);
+
+	kunit_info(test, "32-bit alloc (size 32) took %lld ns, result=%px\n",
+		   ktime_to_ns(elapsed), iova);
+	KUNIT_EXPECT_LT(test, ktime_to_ns(elapsed), 10000000LL);
+
+	if (iova)
+		__free_iova(&ctx->iovad, iova);
+
+	start = ktime_get();
+	iova = alloc_iova(&ctx->iovad, 32, TEST_LIMIT_64BIT, true);
+	elapsed = ktime_sub(ktime_get(), start);
+
+	kunit_info(test, "64-bit fallback (size 32) took %lld ns\n",
+		   ktime_to_ns(elapsed));
+	KUNIT_EXPECT_LT(test, ktime_to_ns(elapsed), 10000000LL);
+
+	if (iova)
+		__free_iova(&ctx->iovad, iova);
+}
+
+static struct kunit_case iova_test_cases[] = {
+	KUNIT_CASE(test_size_aligned),
+	KUNIT_CASE(test_top_down_preference),
+	KUNIT_CASE(test_reserve_iova),
+	KUNIT_CASE(test_32bit_in_64bit_domain),
+	KUNIT_CASE(test_arbitrary_dma_limits),
+	KUNIT_CASE(test_aligned_in_fragmented),
+	KUNIT_CASE(test_pci_32bit_workaround_pattern),
+	KUNIT_CASE(test_stress_random),
+	KUNIT_CASE(test_full_space_search_time),
+	KUNIT_CASE(test_fragmented_32bit_search),
+	{}
+};
+
+static struct kunit_suite iova_test_suite = {
+	.name = "iova",
+	.init = iova_test_init,
+	.exit = iova_test_exit,
+	.test_cases = iova_test_cases,
+};
+kunit_test_suite(iova_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for the IOVA allocator");
+MODULE_LICENSE("GPL");
diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 523d1e8315f9..1ceab6cbefc2 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -857,6 +857,40 @@ void iova_cache_put(void)
 }
 EXPORT_SYMBOL_GPL(iova_cache_put);
 
+#if IS_ENABLED(CONFIG_IOMMU_IOVA_KUNIT_TEST)
+bool iova_domain_verify_invariants(struct iova_domain *iovad)
+{
+	struct iova *iova, *prev = NULL;
+	unsigned long flags;
+	bool ok = true;
+	MA_STATE(mas, &iovad->mtree, 0, 0);
+
+	spin_lock_irqsave(&iovad->iova_lock, flags);
+	mas_for_each(&mas, iova, ULONG_MAX) {
+		if (mas.index != iova->pfn_lo || mas.last != iova->pfn_hi) {
+			pr_err("iova_verify: maple index [%lu,%lu] != iova [%lu,%lu]\n",
+			       mas.index, mas.last, iova->pfn_lo, iova->pfn_hi);
+			ok = false;
+		}
+		if (iova->pfn_lo > iova->pfn_hi) {
+			pr_err("iova_verify: pfn_lo=%lu > pfn_hi=%lu\n",
+			       iova->pfn_lo, iova->pfn_hi);
+			ok = false;
+		}
+		if (prev && prev->pfn_hi >= iova->pfn_lo) {
+			pr_err("iova_verify: overlap prev=[%lu,%lu] curr=[%lu,%lu]\n",
+			       prev->pfn_lo, prev->pfn_hi,
+			       iova->pfn_lo, iova->pfn_hi);
+			ok = false;
+		}
+		prev = iova;
+	}
+	spin_unlock_irqrestore(&iovad->iova_lock, flags);
+	return ok;
+}
+EXPORT_SYMBOL_GPL(iova_domain_verify_invariants);
+#endif /* CONFIG_IOMMU_IOVA_KUNIT_TEST */
+
 MODULE_AUTHOR("Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>");
 MODULE_DESCRIPTION("IOMMU I/O Virtual Address management");
 MODULE_LICENSE("GPL");
diff --git a/include/linux/iova.h b/include/linux/iova.h
index eb4f9ead5451..6fc070a4f58e 100644
--- a/include/linux/iova.h
+++ b/include/linux/iova.h
@@ -98,6 +98,9 @@ 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);
+#endif
 #else
 static inline int iova_cache_get(void)
 {
-- 
2.54.0

[PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

From: Rik van Riel <riel@meta.com>

The maple tree may need to allocate nodes during erase operations
for tree rebalancing. Unlike the old rbtree where rb_erase() never
allocated, mas_store_gfp(NULL, GFP_ATOMIC) can fail under memory
pressure. Since the IOVA allocator runs in atomic context (DMA
map/unmap can be called from hardirq, softirq, or with spinlocks
held), GFP_KERNEL allocation is not possible.

Add a deferred free mechanism: when mas_store_gfp(NULL, GFP_ATOMIC)
fails, the iova entry remains in the maple tree (preventing address
reuse and keeping the pointer valid) and is added to a lockless
per-domain deferred free list. A delayed workqueue retries the erase
with GFP_ATOMIC after a 10ms delay -- by the time the workqueue runs,
transient memory pressure has typically subsided and the allocation
succeeds.

The deferred free path temporarily reduces available IOVA address
space until the workqueue processes the backlog, but causes no
corruption -- the entry stays in the tree and the struct iova is not
freed until the erase succeeds.

put_iova_domain() cancels the delayed work and discards the deferred
list before destroying the tree. Since deferred entries remain in
the maple tree, the mas_for_each teardown loop frees them along with
all other entries, avoiding a double-free.

In practice, GFP_ATOMIC erase failures are quite rare: the slab
allocator maintains emergency reserves for GFP_ATOMIC, and the common
erase case (exact_fit, slot_store) needs zero node allocations. This
mechanism is a safety net for the exceptional case.

Assisted-by: Claude:claude-opus-4-6
Signed-off-by: Rik van Riel <riel@surriel.com>
---
 drivers/iommu/iova.c | 84 +++++++++++++++++++++++++++++++++++++++-----
 include/linux/iova.h |  3 ++
 2 files changed, 79 insertions(+), 8 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 1ceab6cbefc2..ae89d780fce5 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -7,6 +7,7 @@
 
 #include <linux/iova.h>
 #include <linux/kmemleak.h>
+#include <linux/llist.h>
 #include <linux/module.h>
 #include <linux/slab.h>
 #include <linux/smp.h>
@@ -26,6 +27,7 @@ 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_deferred_free_work(struct work_struct *work);
 
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
@@ -46,6 +48,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;
+	init_llist_head(&iovad->deferred_frees);
+	INIT_DELAYED_WORK(&iovad->deferred_free_work, iova_deferred_free_work);
 }
 EXPORT_SYMBOL_GPL(init_iova_domain);
 
@@ -156,7 +160,13 @@ private_find_iova(struct iova_domain *iovad, unsigned long pfn)
 	return mas_walk(&mas);
 }
 
-static void remove_iova(struct iova_domain *iovad, struct iova *iova)
+/*
+ * Remove an IOVA entry from the maple tree. Returns true on success.
+ * On failure (maple tree node allocation under GFP_ATOMIC failed),
+ * returns false — the entry remains in the tree and the caller must
+ * not free the struct iova.
+ */
+static bool remove_iova(struct iova_domain *iovad, struct iova *iova)
 {
 	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
 
@@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain *iovad, struct iova *iova)
 	if (iova->pfn_lo < iovad->dma_32bit_pfn)
 		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
 
-	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
+	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
+		return false;
+	return true;
+}
+
+static void iova_deferred_free_work(struct work_struct *work)
+{
+	struct delayed_work *dwork = to_delayed_work(work);
+	struct iova_domain *iovad = container_of(dwork, struct iova_domain,
+						 deferred_free_work);
+	struct llist_node *list = llist_del_all(&iovad->deferred_frees);
+	struct llist_node *node, *next;
+
+	llist_for_each_safe(node, next, list) {
+		struct iova *iova = container_of(node, struct iova,
+						 deferred_free);
+		unsigned long flags;
+
+		spin_lock_irqsave(&iovad->iova_lock, flags);
+		if (remove_iova(iovad, iova))
+			free_iova_mem(iova);
+		else
+			llist_add(&iova->deferred_free,
+				  &iovad->deferred_frees);
+		spin_unlock_irqrestore(&iovad->iova_lock, flags);
+	}
+
+	if (!llist_empty(&iovad->deferred_frees))
+		schedule_delayed_work(&iovad->deferred_free_work,
+				      msecs_to_jiffies(10));
 }
 
 /**
@@ -199,9 +238,15 @@ __free_iova(struct iova_domain *iovad, struct iova *iova)
 	unsigned long flags;
 
 	spin_lock_irqsave(&iovad->iova_lock, flags);
-	remove_iova(iovad, iova);
+	if (remove_iova(iovad, iova)) {
+		spin_unlock_irqrestore(&iovad->iova_lock, flags);
+		free_iova_mem(iova);
+		return;
+	}
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
-	free_iova_mem(iova);
+	llist_add(&iova->deferred_free, &iovad->deferred_frees);
+	schedule_delayed_work(&iovad->deferred_free_work,
+			      msecs_to_jiffies(10));
 }
 EXPORT_SYMBOL_GPL(__free_iova);
 
@@ -224,9 +269,15 @@ free_iova(struct iova_domain *iovad, unsigned long pfn)
 		spin_unlock_irqrestore(&iovad->iova_lock, flags);
 		return;
 	}
-	remove_iova(iovad, iova);
+	if (remove_iova(iovad, iova)) {
+		spin_unlock_irqrestore(&iovad->iova_lock, flags);
+		free_iova_mem(iova);
+		return;
+	}
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
-	free_iova_mem(iova);
+	llist_add(&iova->deferred_free, &iovad->deferred_frees);
+	schedule_delayed_work(&iovad->deferred_free_work,
+			      msecs_to_jiffies(10));
 }
 EXPORT_SYMBOL_GPL(free_iova);
 
@@ -318,6 +369,15 @@ void put_iova_domain(struct iova_domain *iovad)
 	if (iovad->rcaches)
 		iova_domain_free_rcaches(iovad);
 
+	cancel_delayed_work_sync(&iovad->deferred_free_work);
+
+	/*
+	 * Deferred entries are still in the maple tree, so the
+	 * mas_for_each loop below frees them along with everything else.
+	 * Just discard the deferred list without double-freeing.
+	 */
+	llist_del_all(&iovad->deferred_frees);
+
 	mas_for_each(&mas, iova, ULONG_MAX)
 		free_iova_mem(iova);
 	__mt_destroy(&iovad->mtree);
@@ -481,12 +541,20 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 		if (WARN_ON(!iova))
 			continue;
 
-		remove_iova(iovad, iova);
-		free_iova_mem(iova);
+		if (remove_iova(iovad, iova)) {
+			free_iova_mem(iova);
+		} else {
+			llist_add(&iova->deferred_free,
+				  &iovad->deferred_frees);
+		}
 	}
 
 	spin_unlock_irqrestore(&iovad->iova_lock, flags);
 
+	if (!llist_empty(&iovad->deferred_frees))
+		schedule_delayed_work(&iovad->deferred_free_work,
+				      msecs_to_jiffies(10));
+
 	mag->size = 0;
 }
 
diff --git a/include/linux/iova.h b/include/linux/iova.h
index 6fc070a4f58e..cc1b5441a058 100644
--- a/include/linux/iova.h
+++ b/include/linux/iova.h
@@ -16,6 +16,7 @@
 
 /* iova structure */
 struct iova {
+	struct llist_node	deferred_free;
 	unsigned long	pfn_hi; /* Highest allocated pfn */
 	unsigned long	pfn_lo; /* Lowest allocated pfn */
 };
@@ -31,6 +32,8 @@ 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 */
+	struct llist_head deferred_frees;
+	struct delayed_work deferred_free_work;
 
 	struct iova_rcache	*rcaches;
 	struct hlist_node	cpuhp_dead;
-- 
2.54.0

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Tue, Jun 02, 2026 at 11:35:48PM -0400, Rik van Riel wrote:
> +/*
> + * Remove an IOVA entry from the maple tree. Returns true on success.
> + * On failure (maple tree node allocation under GFP_ATOMIC failed),
> + * returns false — the entry remains in the tree and the caller must
> + * not free the struct iova.
> + */
> +static bool remove_iova(struct iova_domain *iovad, struct iova *iova)
>  {
>  	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
>  
> @@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain *iovad, struct iova *iova)
>  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
>  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
>  
> -	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
> +	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
> +		return false;

But why does it use mas_store(NULL) instead of mas_erase()? I thought
the iova alloc/free has to be pair wise, we don't split allocations?

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Tue, 2026-06-09 at 10:04 -0300, Jason Gunthorpe wrote:
> On Tue, Jun 02, 2026 at 11:35:48PM -0400, Rik van Riel wrote:
> > +/*
> > + * Remove an IOVA entry from the maple tree. Returns true on
> > success.
> > + * On failure (maple tree node allocation under GFP_ATOMIC
> > failed),
> > + * returns false — the entry remains in the tree and the caller
> > must
> > + * not free the struct iova.
> > + */
> > +static bool remove_iova(struct iova_domain *iovad, struct iova
> > *iova)
> >  {
> >  	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
> >  
> > @@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
> > *iovad, struct iova *iova)
> >  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
> >  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
> >  
> > -	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
> > +	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
> > +		return false;
> 
> But why does it use mas_store(NULL) instead of mas_erase()? I thought
> the iova alloc/free has to be pair wise, we don't split allocations?
> 
Mas_erase() would look cleaner, indeed, and it
looks like the mas_wr_preallocate() call is
safe from atomic context, as well!

Let me give that a try tomorrow.

I'll send a v4 if that cleanup works right.

-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Tue, 2026-06-09 at 10:04 -0300, Jason Gunthorpe wrote:
> On Tue, Jun 02, 2026 at 11:35:48PM -0400, Rik van Riel wrote:
> > +/*
> > + * Remove an IOVA entry from the maple tree. Returns true on
> > success.
> > + * On failure (maple tree node allocation under GFP_ATOMIC
> > failed),
> > + * returns false — the entry remains in the tree and the caller
> > must
> > + * not free the struct iova.
> > + */
> > +static bool remove_iova(struct iova_domain *iovad, struct iova
> > *iova)
> >  {
> >  	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
> >  
> > @@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
> > *iovad, struct iova *iova)
> >  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
> >  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
> >  
> > -	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
> > +	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
> > +		return false;
> 
> But why does it use mas_store(NULL) instead of mas_erase()? I thought
> the iova alloc/free has to be pair wise, we don't split allocations?
> 
I just looked into this some more, and I was
confused earlier this week.

The mas_erase() function calls mas_nomem(mas, GFP_KERNEL),
which is not safe to call while holding a spinlock.

The remove_iova() function holds a spinlock, with
interrupts blocked, and needs to run like that because
it could be called from places like IO completion
handlers.

That leaves the option of either having slightly
uglier maple tree code, or going back to the
augmented rbtree (but cleaning that up a little).

Just let me know what you prefer, I'm happy to do
either.

-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Fri, Jun 12, 2026 at 12:02:55PM -0400, Rik van Riel wrote:
> On Tue, 2026-06-09 at 10:04 -0300, Jason Gunthorpe wrote:
> > On Tue, Jun 02, 2026 at 11:35:48PM -0400, Rik van Riel wrote:
> > > +/*
> > > + * Remove an IOVA entry from the maple tree. Returns true on
> > > success.
> > > + * On failure (maple tree node allocation under GFP_ATOMIC
> > > failed),
> > > + * returns false — the entry remains in the tree and the caller
> > > must
> > > + * not free the struct iova.
> > > + */
> > > +static bool remove_iova(struct iova_domain *iovad, struct iova
> > > *iova)
> > >  {
> > >  	MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi);
> > >  
> > > @@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
> > > *iovad, struct iova *iova)
> > >  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
> > >  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
> > >  
> > > -	mas_store_gfp(&mas, NULL, GFP_ATOMIC);
> > > +	if (mas_store_gfp(&mas, NULL, GFP_ATOMIC))
> > > +		return false;
> > 
> > But why does it use mas_store(NULL) instead of mas_erase()? I thought
> > the iova alloc/free has to be pair wise, we don't split allocations?
> > 
> I just looked into this some more, and I was
> confused earlier this week.
> 
> The mas_erase() function calls mas_nomem(mas, GFP_KERNEL),
> which is not safe to call while holding a spinlock.

Oh, the kdoc doesn't say that, it doesn't return any error code if it
can't allocate memory, and not a single caller checks for erase
failures.

I assumed internally it "somehow worked out" even though there are
allocations in the callchains..

This is probably a better question for Liam? Can mtree_erase actually
fail ENOMEM? Is it safe to call it in an atomic context?

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Fri, 2026-06-12 at 13:48 -0300, Jason Gunthorpe wrote:
> On Fri, Jun 12, 2026 at 12:02:55PM -0400, Rik van Riel wrote:
> > 
> > The mas_erase() function calls mas_nomem(mas, GFP_KERNEL),
> > which is not safe to call while holding a spinlock.
> 
> Oh, the kdoc doesn't say that, it doesn't return any error code if it
> can't allocate memory, and not a single caller checks for erase
> failures.
> 
> I assumed internally it "somehow worked out" even though there are
> allocations in the callchains..
> 
> This is probably a better question for Liam? Can mtree_erase actually
> fail ENOMEM? Is it safe to call it in an atomic context?

Yes, it can fail.

When it does, __free_iova and friends fall back to
asynchronously freeing the iova from a worker.

If we are ok with always asynchronously freeing
iovas, we might be able to simplify the code by
always going through that helper.

If there are cases where asynchronously freeing
the iova breaks the system, we cannot use the
maple tree, but need the augmented rbtree, instead.

I do still have a cleaned up version of the augmented
rbtree, if asynchronous freeing is a real concern.

-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Fri, Jun 12, 2026 at 01:23:58PM -0400, Rik van Riel wrote:
> On Fri, 2026-06-12 at 13:48 -0300, Jason Gunthorpe wrote:
> > On Fri, Jun 12, 2026 at 12:02:55PM -0400, Rik van Riel wrote:
> > > 
> > > The mas_erase() function calls mas_nomem(mas, GFP_KERNEL),
> > > which is not safe to call while holding a spinlock.
> > 
> > Oh, the kdoc doesn't say that, it doesn't return any error code if it
> > can't allocate memory, and not a single caller checks for erase
> > failures.
> > 
> > I assumed internally it "somehow worked out" even though there are
> > allocations in the callchains..
> > 
> > This is probably a better question for Liam? Can mtree_erase actually
> > fail ENOMEM? Is it safe to call it in an atomic context?
> 
> Yes, it can fail.

Currently it never returns a failure to the caller. Look at mas_erase():

	entry = mas_state_walk(mas);
	if (!entry)
		return NULL;
[..]
	if (mas_is_err(mas))
		goto out;
[..]
out:
	mas_destroy(mas);
	return entry;

There is no propogation of ENOMEM, it returns success. No caller
checks for any error here either.

So I think the intention is that it cannot fail, yet it does have the
memory allocations and busted failure path. Hence asking Liam what it
should be, and what about an atomic context.

Perhaps this might be relying on the modern kernels "small allocations
never fail", meaning mas_erase never fails, but then you can't
call it from an atomic context..

In any case, it does look like you can't use mas_erase from an atomic
context anyhow so your prior option with the mas_store_gfp() and
failure handling seems reasonable.

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

+Cc maple-tree list.

On 26/06/12 03:03PM, Jason Gunthorpe wrote:
> On Fri, Jun 12, 2026 at 01:23:58PM -0400, Rik van Riel wrote:
> > On Fri, 2026-06-12 at 13:48 -0300, Jason Gunthorpe wrote:
> > > On Fri, Jun 12, 2026 at 12:02:55PM -0400, Rik van Riel wrote:
> > > > 
> > > > The mas_erase() function calls mas_nomem(mas, GFP_KERNEL),
> > > > which is not safe to call while holding a spinlock.
> > > 
> > > Oh, the kdoc doesn't say that, it doesn't return any error code if it
> > > can't allocate memory, and not a single caller checks for erase
> > > failures.

I should fix that.

> > > 
> > > I assumed internally it "somehow worked out" even though there are
> > > allocations in the callchains..
> > > 
> > > This is probably a better question for Liam? Can mtree_erase actually
> > > fail ENOMEM? Is it safe to call it in an atomic context?
> > 
> > Yes, it can fail.
> 
> Currently it never returns a failure to the caller. Look at mas_erase():
> 
> 	entry = mas_state_walk(mas);
> 	if (!entry)
> 		return NULL;
> [..]
> 	if (mas_is_err(mas))
> 		goto out;
> [..]
> out:
> 	mas_destroy(mas);
> 	return entry;
> 
> There is no propogation of ENOMEM, it returns success. No caller
> checks for any error here either.

At one point this was considered to be impossible to fail, and it is
documented to return the entry or null.

> 
> So I think the intention is that it cannot fail, yet it does have the
> memory allocations and busted failure path. Hence asking Liam what it
> should be, and what about an atomic context.
> 
> Perhaps this might be relying on the modern kernels "small allocations
> never fail", meaning mas_erase never fails, but then you can't
> call it from an atomic context..

It _can_ fail, but right now that error will not be propagated to the
caller.  The caller could infer the failure due to the return of NULL...
if that's what would happen, so there's very much an issue on failure
that I need to investigate and fix.

It is possible that it fails with -ENOMEM.  And the spinlock can be
dropped if you are not using an external lock and the gfp flag allows
blocking.  On failure to allocate and the lock is dropped, we retry the
operation from the start in case there was a race with another writer.

I think I should probably change this to return -ENOMEM, fix the docs on
it, and probably audit the callers (most use external locks or are
early-boot-so-don't-worry-about-it).  Any issue here should also be
caught by lockdep pretty quickly.

> 
> In any case, it does look like you can't use mas_erase from an atomic
> context anyhow so your prior option with the mas_store_gfp() and
> failure handling seems reasonable.

mas_store_gfp() works if you know the range of your entry.  You could
also write the XA_ZERO_ENTRY over the entry so that there is no internal
node changes - just a value swap.  If you do this, you have to be
careful when reading things back when using the mas_ interface.

I think, in your case, hitting an XA_ZERO_ENTRY would be necessary to
indicate that we cannot reuse this particular location until it is
correctly dealt with?  Or is the maple tree the only reason it is
considered unusable?

One thing to remember is that each write can cause allocations to occur,
so if you have a list of items being overwritten then you are causing
the tree to do each write and potentially rebalancing (as you shrink the
data beyond the lower limit of the node).

One way around that is to write XA_ZERO_ENTRY over each one as you
deal with your entry.  Then, when you are done you do a single
mas_store_gfp() of NULL over the whole range.  It will be a larger tree
operation, but smaller than the incremental steps.

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Fri, Jun 12, 2026 at 02:44:06PM -0400, Liam R. Howlett wrote:
> > Currently it never returns a failure to the caller. Look at mas_erase():
> > 
> > 	entry = mas_state_walk(mas);
> > 	if (!entry)
> > 		return NULL;
> > [..]
> > 	if (mas_is_err(mas))
> > 		goto out;
> > [..]
> > out:
> > 	mas_destroy(mas);
> > 	return entry;
> > 
> > There is no propogation of ENOMEM, it returns success. No caller
> > checks for any error here either.
> 
> At one point this was considered to be impossible to fail, and it is
> documented to return the entry or null.

I think that is the right API design..

> I think I should probably change this to return -ENOMEM, fix the docs on
> it, and probably audit the callers (most use external locks or are
> early-boot-so-don't-worry-about-it).  Any issue here should also be
> caught by lockdep pretty quickly.

Locking aside, I don't think most of the callers can handle an -ENOMEM
return at all..

> mas_store_gfp() works if you know the range of your entry.  You could
> also write the XA_ZERO_ENTRY over the entry so that there is no internal
> node changes - just a value swap.  If you do this, you have to be
> careful when reading things back when using the mas_ interface.

That's probably a good option. Try to store NULL, if that ENOMEM's
then drop a ZERO_ENTRY and set a bit someplace so that the next
allocation has to sweep the tree and clean the ZERO's. At least that
shifts the ENOMEM to an alloc side operation where it can be handled.

> I think, in your case, hitting an XA_ZERO_ENTRY would be necessary to
> indicate that we cannot reuse this particular location until it is
> correctly dealt with?  Or is the maple tree the only reason it is
> considered unusable?

Yeah, it would be be a maple tree issue only. Defered rebalancing
leave space unavailable.

This is a case where there is no sane way to handle destroy
failure. You can't return an error code from dma_unmap() for
example. So the only reason for this complexity is because maple tree
exposes a failable erase to it's caller..

IDK, could it handle it internally somehow? Or at least document a
reasonable pattern with some helpers?

Eg _iommufd_destroy_mmap() is in trouble too, it cargo culted the
no-check mt_erase.

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/15 08:56AM, Jason Gunthorpe wrote:
> On Fri, Jun 12, 2026 at 02:44:06PM -0400, Liam R. Howlett wrote:
> > > Currently it never returns a failure to the caller. Look at mas_erase():
> > > 
> > > 	entry = mas_state_walk(mas);
> > > 	if (!entry)
> > > 		return NULL;
> > > [..]
> > > 	if (mas_is_err(mas))
> > > 		goto out;
> > > [..]
> > > out:
> > > 	mas_destroy(mas);
> > > 	return entry;
> > > 
> > > There is no propogation of ENOMEM, it returns success. No caller
> > > checks for any error here either.
> > 
> > At one point this was considered to be impossible to fail, and it is
> > documented to return the entry or null.
> 
> I think that is the right API design..

Callers can check mas_is_err() and check for xa_err(mas) == -ENOMEM.
I'm going to add a note about it to the documentation of the erase
function.

> 
> > I think I should probably change this to return -ENOMEM, fix the docs on
> > it, and probably audit the callers (most use external locks or are
> > early-boot-so-don't-worry-about-it).  Any issue here should also be
> > caught by lockdep pretty quickly.
> 
> Locking aside, I don't think most of the callers can handle an -ENOMEM
> return at all..
> 
> > mas_store_gfp() works if you know the range of your entry.  You could
> > also write the XA_ZERO_ENTRY over the entry so that there is no internal
> > node changes - just a value swap.  If you do this, you have to be
> > careful when reading things back when using the mas_ interface.
> 
> That's probably a good option. Try to store NULL, if that ENOMEM's
> then drop a ZERO_ENTRY and set a bit someplace so that the next
> allocation has to sweep the tree and clean the ZERO's. At least that
> shifts the ENOMEM to an alloc side operation where it can be handled.

Why is the retry GFP_ATOMIC on a timer of 10ms?

Also, why is this patch set using an external spinlock only created to
manage the tree?  Why isn't it using an internal lock?  Is it just to
avoid the possibility of the unlock?

> 
> > I think, in your case, hitting an XA_ZERO_ENTRY would be necessary to
> > indicate that we cannot reuse this particular location until it is
> > correctly dealt with?  Or is the maple tree the only reason it is
> > considered unusable?
> 
> Yeah, it would be be a maple tree issue only. Defered rebalancing
> leave space unavailable.
> 
> This is a case where there is no sane way to handle destroy
> failure. You can't return an error code from dma_unmap() for
> example. So the only reason for this complexity is because maple tree
> exposes a failable erase to it's caller..

I think this is even more complicated by the contexts it is called in -
that is, we cannot preallocate prior to going into this state either?

> 
> IDK, could it handle it internally somehow? Or at least document a
> reasonable pattern with some helpers?
> 
> Eg _iommufd_destroy_mmap() is in trouble too, it cargo culted the
> no-check mt_erase.

Are you sure that's not okay?  The mt_mmap tree is allocated with an
internal spinlock.  In this case, the lock will be dropped, the
allocation will be satisfied and the erase operation will retry.

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Wed, Jun 17, 2026 at 01:45:27PM -0400, Liam R. Howlett wrote:
> On 26/06/15 08:56AM, Jason Gunthorpe wrote:
> > On Fri, Jun 12, 2026 at 02:44:06PM -0400, Liam R. Howlett wrote:
> > > > Currently it never returns a failure to the caller. Look at mas_erase():
> > > > 
> > > > 	entry = mas_state_walk(mas);
> > > > 	if (!entry)
> > > > 		return NULL;
> > > > [..]
> > > > 	if (mas_is_err(mas))
> > > > 		goto out;
> > > > [..]
> > > > out:
> > > > 	mas_destroy(mas);
> > > > 	return entry;
> > > > 
> > > > There is no propogation of ENOMEM, it returns success. No caller
> > > > checks for any error here either.
> > > 
> > > At one point this was considered to be impossible to fail, and it is
> > > documented to return the entry or null.
> > 
> > I think that is the right API design..
> 
> Callers can check mas_is_err() and check for xa_err(mas) == -ENOMEM.
> I'm going to add a note about it to the documentation of the erase
> function.

That's something for mas_erase, but doesn't help mtree_erase() ..

> Why is the retry GFP_ATOMIC on a timer of 10ms?
> 
> Also, why is this patch set using an external spinlock only created to
> manage the tree?  Why isn't it using an internal lock?  Is it just to
> avoid the possibility of the unlock?

IDK, seem like good questions

> > 
> > > I think, in your case, hitting an XA_ZERO_ENTRY would be necessary to
> > > indicate that we cannot reuse this particular location until it is
> > > correctly dealt with?  Or is the maple tree the only reason it is
> > > considered unusable?
> > 
> > Yeah, it would be be a maple tree issue only. Defered rebalancing
> > leave space unavailable.
> > 
> > This is a case where there is no sane way to handle destroy
> > failure. You can't return an error code from dma_unmap() for
> > example. So the only reason for this complexity is because maple tree
> > exposes a failable erase to it's caller..
> 
> I think this is even more complicated by the contexts it is called in -
> that is, we cannot preallocate prior to going into this state either?

Yes, in this case at least the context is GFP_ATOMIC and there is no
way to pre-allocate.. But that seems like another issue since the
mas_erase does not support GFP_ATOMIC anyhow..

> > Eg _iommufd_destroy_mmap() is in trouble too, it cargo culted the
> > no-check mt_erase.
> 
> Are you sure that's not okay?  The mt_mmap tree is allocated with an
> internal spinlock.  In this case, the lock will be dropped, the
> allocation will be satisfied and the erase operation will retry.

Is this what I was asking before? Under some conditions the allocation
can not fail because in the modern kernel we don't allow small
GFP_KERNEL allocations to fail?

Otherwise this:

	if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
		mtree_unlock(mas->tree);
		mas_alloc_nodes(mas, gfp);
		mtree_lock(mas->tree);
	} else {
		mas_alloc_nodes(mas, gfp);
	}

Is always called with GFP_KERNEL for erase. It doesn't seem like
external lock has any impact if mas_alloc_nodes can fail or not?

It looks like if you have an external lock then the hard wired
GFP_KERNEL in mtree_erase/mas_erase mean the lock has to be a sleeping
kind to use those functions.

If that's the case it should be documented like this too :)

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/17 03:04PM, Jason Gunthorpe wrote:
> On Wed, Jun 17, 2026 at 01:45:27PM -0400, Liam R. Howlett wrote:
> > On 26/06/15 08:56AM, Jason Gunthorpe wrote:
> > > On Fri, Jun 12, 2026 at 02:44:06PM -0400, Liam R. Howlett wrote:
> > > > > Currently it never returns a failure to the caller. Look at mas_erase():
> > > > > 
> > > > > 	entry = mas_state_walk(mas);
> > > > > 	if (!entry)
> > > > > 		return NULL;
> > > > > [..]
> > > > > 	if (mas_is_err(mas))
> > > > > 		goto out;
> > > > > [..]
> > > > > out:
> > > > > 	mas_destroy(mas);
> > > > > 	return entry;
> > > > > 
> > > > > There is no propogation of ENOMEM, it returns success. No caller
> > > > > checks for any error here either.
> > > > 
> > > > At one point this was considered to be impossible to fail, and it is
> > > > documented to return the entry or null.
> > > 
> > > I think that is the right API design..
> > 
> > Callers can check mas_is_err() and check for xa_err(mas) == -ENOMEM.
> > I'm going to add a note about it to the documentation of the erase
> > function.
> 
> That's something for mas_erase, but doesn't help mtree_erase() ..

Indeed.

I'd rather avoid the leaking of the very much unlikely failure checks.

...

> > > 
> > > > I think, in your case, hitting an XA_ZERO_ENTRY would be necessary to
> > > > indicate that we cannot reuse this particular location until it is
> > > > correctly dealt with?  Or is the maple tree the only reason it is
> > > > considered unusable?
> > > 
> > > Yeah, it would be be a maple tree issue only. Defered rebalancing
> > > leave space unavailable.
> > > 
> > > This is a case where there is no sane way to handle destroy
> > > failure. You can't return an error code from dma_unmap() for
> > > example. So the only reason for this complexity is because maple tree
> > > exposes a failable erase to it's caller..
> > 
> > I think this is even more complicated by the contexts it is called in -
> > that is, we cannot preallocate prior to going into this state either?
> 
> Yes, in this case at least the context is GFP_ATOMIC and there is no
> way to pre-allocate.. But that seems like another issue since the
> mas_erase does not support GFP_ATOMIC anyhow..

Yes.  If you need atomic allocations then you should stick to the API
that allows you to pass in the GFP flags.  It may not be clear to users
that allocations might be required for erase, so I should document that.

> 
> > > Eg _iommufd_destroy_mmap() is in trouble too, it cargo culted the
> > > no-check mt_erase.
> > 
> > Are you sure that's not okay?  The mt_mmap tree is allocated with an
> > internal spinlock.  In this case, the lock will be dropped, the
> > allocation will be satisfied and the erase operation will retry.
> 
> Is this what I was asking before? Under some conditions the allocation
> can not fail because in the modern kernel we don't allow small
> GFP_KERNEL allocations to fail?
> 
> Otherwise this:
> 
> 	if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
> 		mtree_unlock(mas->tree);
> 		mas_alloc_nodes(mas, gfp);
> 		mtree_lock(mas->tree);
> 	} else {
> 		mas_alloc_nodes(mas, gfp);
> 	}
> 
> Is always called with GFP_KERNEL for erase. It doesn't seem like
> external lock has any impact if mas_alloc_nodes can fail or not?
> 
> It looks like if you have an external lock then the hard wired
> GFP_KERNEL in mtree_erase/mas_erase mean the lock has to be a sleeping
> kind to use those functions.
> 

Ah, right.

Yes.  The idea here is Too Small To Fail.

Also, note that we call our first allocation with NOWAIT, so that may
have already started the process of getting memory (I think?).

Also note that this is in sheaves, so we'd have to have nothing left in
the maple tree kmem_cache, the sheave, and no page laying around (1 page
is 16 nodes..), and the NOWAIT to have no effect when arriving here.


> If that's the case it should be documented like this too :)

Yeah, very much should add some notes here... but also maybe stop them
from doing it by adding this to mas_erase():

if (mt_external_lock(mas->tree))
        might_alloc(GFP_KERNEL);

Otherwise, I'll just be telling people they didn't read the docs.

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Thu, Jun 18, 2026 at 10:50:56AM -0400, Liam R. Howlett wrote:

> > If that's the case it should be documented like this too :)
> 
> Yeah, very much should add some notes here... but also maybe stop them
> from doing it by adding this to mas_erase():
> 
> if (mt_external_lock(mas->tree))
>         might_alloc(GFP_KERNEL);

Yeah, and then I'd add a might_alloc() to mtree_erase() as well, it
can always sleep..

> Otherwise, I'll just be telling people they didn't read the docs.

Okay, so to summarize:

- mas_erase, mtree_erase cannot fail with ENOMEM. The check for ENOMEM
  inside should be changed to a WARN_ON to document this.
  Rational: in a GFP_KERNEL context it will sleep forever until it
  gets memory "too small to fail"

- External locks must be sleepable, add a might_alloc() to check for
  that and document. mtree_erase must be sleepable

- I like your idea for Rik to try to store NULL to erase, on failure
  store ZERO_ENTRY, and then set a note on the next alloc to clean the
  ZERO_ENTRYs?

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> On Thu, Jun 18, 2026 at 10:50:56AM -0400, Liam R. Howlett wrote:
> 
> > > If that's the case it should be documented like this too :)
> > 
> > Yeah, very much should add some notes here... but also maybe stop them
> > from doing it by adding this to mas_erase():
> > 
> > if (mt_external_lock(mas->tree))
> >         might_alloc(GFP_KERNEL);
> 
> Yeah, and then I'd add a might_alloc() to mtree_erase() as well, it
> can always sleep..

mtree_erase() calls mas_erase(), so I think the one should be enough.

> 
> > Otherwise, I'll just be telling people they didn't read the docs.
> 
> Okay, so to summarize:
> 
> - mas_erase, mtree_erase cannot fail with ENOMEM. The check for ENOMEM
>   inside should be changed to a WARN_ON to document this.
>   Rational: in a GFP_KERNEL context it will sleep forever until it
>   gets memory "too small to fail"

The ENOMEM check inside mas_nomem() is still possible because we try
NOWAIT first, so it is possible that we hit a retry.

The return from mas_nomem() without allocations should be impossible.
So if (!mas->sheaf && !mas->alloc) should be a WARN_ON_ONCE().

I believe this is what you meant anyways?

> 
> - External locks must be sleepable, add a might_alloc() to check for
>   that and document. mtree_erase must be sleepable
> 
> - I like your idea for Rik to try to store NULL to erase, on failure
>   store ZERO_ENTRY, and then set a note on the next alloc to clean the
>   ZERO_ENTRYs?

The ZERO_ENTRY can be found by mas_* functions and will cause issues
with the gap searching.  You also have to be careful to handle these
entries in mas_for_each() loops - you don't want to treat them as valid
entries.

So cleaning them up should be handled sooner rather than later.  I'm
trying to figure out the best place to do this as I do not like the
retry with the timer idea.

Setting a bit to clear them later makes sense, but I am concerned that
leaving reserved space for a prolonged period may cause other failures?
I guess we could ensure that the tree is 'clean of reserved space' prior
to searching for space to but new entries?

We probably don't really need to worry about speed since this is an
error recovery situation that will happen rarely, so correct is all we
need.

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Thu, 2026-06-18 at 13:27 -0400, Liam R. Howlett wrote:
> On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> > 
> > 
> > - I like your idea for Rik to try to store NULL to erase, on
> > failure
> >   store ZERO_ENTRY, and then set a note on the next alloc to clean
> > the
> >   ZERO_ENTRYs?
> 
> The ZERO_ENTRY can be found by mas_* functions and will cause issues
> with the gap searching.  You also have to be careful to handle these
> entries in mas_for_each() loops - you don't want to treat them as
> valid
> entries.
> 
Could it make sense for the maple tree to have
something similar to ZERO_ENTRY that is treated
like a gap, so the gap search can find it, and
get rid of those entries when the gap gets re-used?

-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/18 01:30PM, Rik van Riel wrote:
> On Thu, 2026-06-18 at 13:27 -0400, Liam R. Howlett wrote:
> > On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> > > 
> > > 
> > > - I like your idea for Rik to try to store NULL to erase, on
> > > failure
> > >   store ZERO_ENTRY, and then set a note on the next alloc to clean
> > > the
> > >   ZERO_ENTRYs?
> > 
> > The ZERO_ENTRY can be found by mas_* functions and will cause issues
> > with the gap searching.  You also have to be careful to handle these
> > entries in mas_for_each() loops - you don't want to treat them as
> > valid
> > entries.
> > 
> Could it make sense for the maple tree to have
> something similar to ZERO_ENTRY that is treated
> like a gap, so the gap search can find it, and
> get rid of those entries when the gap gets re-used?

It might, but it's not as simple as adding a new special entry.  Gaps
are propagated up the tree so that we know which subtree has what size
gap.  If we have a special entry that isn't counted as an entry at all,
then we're in a position where the gap calculation code needs to change.

I'm also not sure how we handle this entry if it's at the edge of a
node.  How do you account for a gap in a subtree if it's not fully in
that subtree?  If one node has a gap of 5 and a value and then the next
node starts with a gap of 5, how do we represent that gap in the parent
node?  What if it's multiple levels up?  How do we find that gap and how
do we return something that makes sense to the caller?  What if the gap
spans an entire node or larger?

It also brings into question how much data is considered within a node -
is one of these entries kept if we rebalance?  Do we have to mark the
tree itself to state that it's in this odd state to avoid other stores
from actually happening before the tree is cleaned?  How do we state
that the tree is in this unusual state?

It might be worth doing, but it's not a simple change.

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Thu, Jun 18, 2026 at 01:27:02PM -0400, Liam R. Howlett wrote:
> On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> > On Thu, Jun 18, 2026 at 10:50:56AM -0400, Liam R. Howlett wrote:
> > 
> > > > If that's the case it should be documented like this too :)
> > > 
> > > Yeah, very much should add some notes here... but also maybe stop them
> > > from doing it by adding this to mas_erase():
> > > 
> > > if (mt_external_lock(mas->tree))
> > >         might_alloc(GFP_KERNEL);
> > 
> > Yeah, and then I'd add a might_alloc() to mtree_erase() as well, it
> > can always sleep..
> 
> mtree_erase() calls mas_erase(), so I think the one should be enough.

I was thinking an unconditional one before locking:

@@ -5919,6 +5919,8 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
        MA_STATE(mas, mt, index, index);
        trace_ma_op(TP_FCT, &mas);
 
+       might_alloc(GFP_KERNEL);
+
        mtree_lock(mt);

Since with internal locking this can still sleep, and it has to be
called in a sleepable context.

The one in mas_erase() is conditional on external locking and is
basically asserting the external lock is non-atomic.

> > Okay, so to summarize:
> > 
> > - mas_erase, mtree_erase cannot fail with ENOMEM. The check for ENOMEM
> >   inside should be changed to a WARN_ON to document this.
> >   Rational: in a GFP_KERNEL context it will sleep forever until it
> >   gets memory "too small to fail"
> 
> The ENOMEM check inside mas_nomem() is still possible because we try
> NOWAIT first, so it is possible that we hit a retry.
> 
> The return from mas_nomem() without allocations should be impossible.
> So if (!mas->sheaf && !mas->alloc) should be a WARN_ON_ONCE().
> 
> I believe this is what you meant anyways?

Yeah, probably, or maybe this:

	if (mas_is_err(mas))
		goto out;

Can it ever be anything but -ENOMEM within mas_erase()?
 
> So cleaning them up should be handled sooner rather than later.  I'm
> trying to figure out the best place to do this as I do not like the
> retry with the timer idea.

I would clean them up when gap searching to allocate a new thing. That
is a safe place to fail and ensures the gaps are correct before
checking them.

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/19 09:08AM, Jason Gunthorpe wrote:
> On Thu, Jun 18, 2026 at 01:27:02PM -0400, Liam R. Howlett wrote:
> > On 26/06/18 12:24PM, Jason Gunthorpe wrote:
> > > On Thu, Jun 18, 2026 at 10:50:56AM -0400, Liam R. Howlett wrote:
> > > 
> > > > > If that's the case it should be documented like this too :)
> > > > 
> > > > Yeah, very much should add some notes here... but also maybe stop them
> > > > from doing it by adding this to mas_erase():
> > > > 
> > > > if (mt_external_lock(mas->tree))
> > > >         might_alloc(GFP_KERNEL);
> > > 
> > > Yeah, and then I'd add a might_alloc() to mtree_erase() as well, it
> > > can always sleep..
> > 
> > mtree_erase() calls mas_erase(), so I think the one should be enough.
> 
> I was thinking an unconditional one before locking:
> 
> @@ -5919,6 +5919,8 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
>         MA_STATE(mas, mt, index, index);
>         trace_ma_op(TP_FCT, &mas);
>  
> +       might_alloc(GFP_KERNEL);
> +

Right, yes.  I'll do that.

>         mtree_lock(mt);
> 
> Since with internal locking this can still sleep, and it has to be
> called in a sleepable context.
> 
> The one in mas_erase() is conditional on external locking and is
> basically asserting the external lock is non-atomic.
> 
> > > Okay, so to summarize:
> > > 
> > > - mas_erase, mtree_erase cannot fail with ENOMEM. The check for ENOMEM
> > >   inside should be changed to a WARN_ON to document this.
> > >   Rational: in a GFP_KERNEL context it will sleep forever until it
> > >   gets memory "too small to fail"
> > 
> > The ENOMEM check inside mas_nomem() is still possible because we try
> > NOWAIT first, so it is possible that we hit a retry.
> > 
> > The return from mas_nomem() without allocations should be impossible.
> > So if (!mas->sheaf && !mas->alloc) should be a WARN_ON_ONCE().
> > 
> > I believe this is what you meant anyways?
> 
> Yeah, probably, or maybe this:
> 
> 	if (mas_is_err(mas))
> 		goto out;
> 
> Can it ever be anything but -ENOMEM within mas_erase()?
>  
> > So cleaning them up should be handled sooner rather than later.  I'm
> > trying to figure out the best place to do this as I do not like the
> > retry with the timer idea.
> 
> I would clean them up when gap searching to allocate a new thing. That
> is a safe place to fail and ensures the gaps are correct before
> checking them.
> 
> Jason
> 
> -- 
> maple-tree mailing list
> maple-tree@lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Thu, 2026-06-18 at 12:24 -0300, Jason Gunthorpe wrote:
> 
> - I like your idea for Rik to try to store NULL to erase, on failure
>   store ZERO_ENTRY, and then set a note on the next alloc to clean
> the
>   ZERO_ENTRYs?
> 
Is there any efficient way to find those XA_ZERO_ENTRYs?

Without a good way to find them, we might still need the
llist to clean them up, though I agree that cleaning them
up from the allocator side looks cleaner than doing it
from an external worker, and I did make that change for v4.


-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Liam R. Howlett]

On 26/06/18 11:51PM, Rik van Riel wrote:
> On Thu, 2026-06-18 at 12:24 -0300, Jason Gunthorpe wrote:
> > 
> > - I like your idea for Rik to try to store NULL to erase, on failure
> >   store ZERO_ENTRY, and then set a note on the next alloc to clean
> > the
> >   ZERO_ENTRYs?
> > 
> Is there any efficient way to find those XA_ZERO_ENTRYs?
> 
> Without a good way to find them, we might still need the
> llist to clean them up, though I agree that cleaning them
> up from the allocator side looks cleaner than doing it
> from an external worker, and I did make that change for v4.

no, but how often is there a failure?  Would walking the list and
writing NULLs be out of the question (I really don't know, sorry if it's
a dumb one)?

Something like this totally untested code:

unsigned long pfn_lo, pfn_hi;

pfn_hi = 0;
pfn_lo = 0;
mas_lock(&mas);
mas_set(&mas, 0);
mas_for_each(&mas, entry, ULONG_MAX) {
        if (entry == XA_ZERO_ENTRY) {
                if (mas.index < pfn_lo)
                        pfn_lo = mas.index;
                pfn_hi = mas.last;
        }
}
                
if (pfn_hi) {
        mas_set_range(&mas, pfn_lo, pfn_hi);
        mas_store_gfp(&mas, NULL, GFP_KERNEL);
}

mas_unlock(&mas);

If you want to optimise it, you can just keep the first failure in the
contiguous area there are failures and reuse the pfn_hi to set the
range. (are the areas contiguous usually?) It's probably better to free
any memory you can since you just ran out of memory anyways.  Although
it's 16B.. how many are usually processed in a group?

Would a normal workqueue be okay to do the freeing?

Thanks,
Liam

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Jason Gunthorpe]

On Fri, Jun 19, 2026 at 12:54:13AM -0400, Liam R. Howlett wrote:
> On 26/06/18 11:51PM, Rik van Riel wrote:
> > On Thu, 2026-06-18 at 12:24 -0300, Jason Gunthorpe wrote:
> > > 
> > > - I like your idea for Rik to try to store NULL to erase, on failure
> > >   store ZERO_ENTRY, and then set a note on the next alloc to clean
> > > the
> > >   ZERO_ENTRYs?
> > > 
> > Is there any efficient way to find those XA_ZERO_ENTRYs?
> > 
> > Without a good way to find them, we might still need the
> > llist to clean them up, though I agree that cleaning them
> > up from the allocator side looks cleaner than doing it
> > from an external worker, and I did make that change for v4.
> 
> no, but how often is there a failure?  Would walking the list and
> writing NULLs be out of the question (I really don't know, sorry if it's
> a dumb one)?

Yeah, this is what I was thinking. Should never happen? I wouldn't
burn memory in each node to make an emergency recovery run faster.

The idea of keeping track of the high/low along with the flag makes
sense, it will narrow the IOVA range to search.

Jason

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Fri, 2026-06-19 at 09:13 -0300, Jason Gunthorpe wrote:
> On Fri, Jun 19, 2026 at 12:54:13AM -0400, Liam R. Howlett wrote:
> > 
> > no, but how often is there a failure?  Would walking the list and
> > writing NULLs be out of the question (I really don't know, sorry if
> > it's
> > a dumb one)?
> 
> Yeah, this is what I was thinking. Should never happen? I wouldn't
> burn memory in each node to make an emergency recovery run faster.
> 
> The idea of keeping track of the high/low along with the flag makes
> sense, it will narrow the IOVA range to search.
> 
I've got this in v4 of the tree now.

One open question is whether cleanup should happen
from the next allocation, or whether we should
move that into a work item that runs in a sleepable
context.

-- 
All Rights Reversed.

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Ashok Raj]

On Tue, Jun 02, 2026 at 11:35:48PM -0400, Rik van Riel wrote:
> From: Rik van Riel <riel@meta.com>
> 

Hi Rik,

I'm a bit rust on these, looking a them after a very long time. So take
my question with a grain of salt :-)


[snip]

> +static void iova_deferred_free_work(struct work_struct *work)
> +{
> +	struct delayed_work *dwork = to_delayed_work(work);
> +	struct iova_domain *iovad = container_of(dwork, struct iova_domain,
> +						 deferred_free_work);
> +	struct llist_node *list = llist_del_all(&iovad->deferred_frees);
> +	struct llist_node *node, *next;
> +
> +	llist_for_each_safe(node, next, list) {
> +		struct iova *iova = container_of(node, struct iova,
> +						 deferred_free);
> +		unsigned long flags;
> +
> +		spin_lock_irqsave(&iovad->iova_lock, flags);
> +		if (remove_iova(iovad, iova))
> +			free_iova_mem(iova);
> +		else
> +			llist_add(&iova->deferred_free,
> +				  &iovad->deferred_frees);
> +		spin_unlock_irqrestore(&iovad->iova_lock, flags);
> +	}
> +
> +	if (!llist_empty(&iovad->deferred_frees))
> +		schedule_delayed_work(&iovad->deferred_free_work,
> +				      msecs_to_jiffies(10));

  If remove_iova() keeps failing (mas_store_gfp(NULL, GFP_ATOMIC) still
  can't get a maple tree node), the iova is pushed back onto deferred_frees
  and the work reschedules itself at a flat 10ms — forever.  There is no
  retry counter or no backoff.

  Under sustained memory pressure a device doing frequent unmap could
  accumulate a growing deferred list, exhaust its IOVA space, and start
  failing DMA map calls — with nothing in dmesg pointing at the real cause.

  Should we:

  1. A simple retry counter per iova (or a domain-level counter) with a
     WARN_ONCE after, say, 10 consecutive failures would at least make the
     condition visible.

  2. Exponential backoff (10ms → 50ms → 200ms, capped at e.g. 1s) reduces
     wasted wakeups under sustained pressure without delaying recovery when
     memory frees up quickly.

Cheers,
Ashok

Re: [PATCH v3 3/3] iova: defer maple tree erase on GFP_ATOMIC failure

[Rik van Riel]

On Sat, 2026-06-20 at 17:08 -0700, Ashok Raj wrote:
> 
>   If remove_iova() keeps failing (mas_store_gfp(NULL, GFP_ATOMIC)
> still
>   can't get a maple tree node), the iova is pushed back onto
> deferred_frees
>   and the work reschedules itself at a flat 10ms — forever.  There is
> no
>   retry counter or no backoff.
> 
>   Under sustained memory pressure a device doing frequent unmap could
>   accumulate a growing deferred list, exhaust its IOVA space, and
> start
>   failing DMA map calls — with nothing in dmesg pointing at the real
> cause.
> 
To some extent, yes.

However, if we have GFP_ATOMIC allocations continue
to fail for several seconds, the system will be in
much larger trouble.

Making the condition visible seems like a good idea,
since I don't know if the other GFP_ATOMIC paths that
could cause system hangs output any warnings.

-- 
All Rights Reversed.