Skip to contentSkip to conversation

iova: use maple tree for O(log n) allocation

PATCH Superseded Rik van Riel 4 participants 29 messages Jun 3 – Jun 30

Subsystems (2)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v3 cover iova: use maple tree for O(log n) allocation

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

#1 lore raw

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

From: Rik van Riel <[email protected]>

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
---
 drivers/iommu/iova.c | 338 ++++++++++++-------------------------------
 include/linux/iova.h |  10 +-
 2 files changed, 98 insertions(+), 250 deletions(-)
drivers/iommu/iova.c +95 -243
index 021daf6528de..523d1e8315f9 100644
@@ -13,9 +13,7 @@
 #include <linux/bitops.h>
 #include <linux/cpu.h>
 #include <linux/workqueue.h>
-
-/* The anchor node sits above the top of the usable address space */
-#define IOVA_ANCHOR	~0UL
+#include <linux/maple_tree.h>
 
 #define IOVA_RANGE_CACHE_MAX_SIZE 6	/* log of max cached IOVA range size (in pages) */
 
@@ -29,11 +27,6 @@ static void free_iova_rcaches(struct iova_domain *iovad);
 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
 static void free_global_cached_iovas(struct iova_domain *iovad);
 
-static struct iova *to_iova(struct rb_node *node)
-{
-	return rb_entry(node, struct iova, node);
-}
-
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	unsigned long start_pfn)
@@ -45,180 +38,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;
 
include/linux/iova.h +3 -7
index d2c4fd923efa..eb4f9ead5451 100644
@@ -11,12 +11,11 @@
 
 #include <linux/types.h>
 #include <linux/kernel.h>
-#include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/dma-mapping.h>
 
 /* iova structure */
 struct iova {
-	struct rb_node	node;
 	unsigned long	pfn_hi; /* Highest allocated pfn */
 	unsigned long	pfn_lo; /* Lowest allocated pfn */
 };
@@ -26,15 +25,12 @@ struct iova_rcache;
 
 /* holds all the iova translations for a domain */
 struct iova_domain {
-	spinlock_t	iova_rbtree_lock; /* Lock to protect update of rbtree */
-	struct rb_root	rbroot;		/* iova domain rbtree root */
-	struct rb_node	*cached_node;	/* Save last alloced node */
-	struct rb_node	*cached32_node; /* Save last 32-bit alloced node */
+	spinlock_t	iova_lock;	/* 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;
Signature · 1 line
2.54.0
#2 lore raw

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

Quoted 28 lines · Rik van Riel

From: Rik van Riel <[email protected]>

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.

Quoted 6 lines

- 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?

Quoted 207 lines

- 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
---
 drivers/iommu/iova.c | 338 ++++++++++++-------------------------------
 include/linux/iova.h |  10 +-
 2 files changed, 98 insertions(+), 250 deletions(-)
drivers/iommu/iova.c +11 -122
index 021daf6528de..523d1e8315f9 100644
@@ -13,9 +13,7 @@
 #include <linux/bitops.h>
 #include <linux/cpu.h>
 #include <linux/workqueue.h>
-
-/* The anchor node sits above the top of the usable address space */
-#define IOVA_ANCHOR	~0UL
+#include <linux/maple_tree.h>
 
 #define IOVA_RANGE_CACHE_MAX_SIZE 6	/* log of max cached IOVA range size (in pages) */
 
@@ -29,11 +27,6 @@ static void free_iova_rcaches(struct iova_domain *iovad);
 static void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
 static void free_global_cached_iovas(struct iova_domain *iovad);
 
-static struct iova *to_iova(struct rb_node *node)
-{
-	return rb_entry(node, struct iova, node);
-}
-
 void
 init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 	unsigned long start_pfn)
@@ -45,180 +38,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)

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

Quoted 10 lines
drivers/iommu/iova.c +3 -2
 		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.

Quoted 21 lines
drivers/iommu/iova.c +3 -16
-	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;

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

Quoted 10 lines
drivers/iommu/iova.c +3 -7
-			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.

Quoted 212 lines
drivers/iommu/iova.c +39 -79
-	/* 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);

drivers/iommu/iova.c __adjust_overlap_range(struct iova *iova, · line 367

Quoted 10 lines
drivers/iommu/iova.c +3 -7
-			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.

Quoted 15 lines
drivers/iommu/iova.c +14 -0
+
+		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);
+		}
 	}

drivers/iommu/iova.c __adjust_overlap_range(struct iova *iova, · line 387

Quoted 10 lines
drivers/iommu/iova.c +4 -5
 
-	/* 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?

drivers/iommu/iova.c __adjust_overlap_range(struct iova *iova, · line 547

Quoted 6 lines
drivers/iommu/iova.c +4 -1
+	}
+
+	{
+		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.

Quoted 29 lines
drivers/iommu/iova.c +9 -2
+		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;
 }

drivers/iommu/iova.c int iova_cache_get(void) · line 812

Quoted 7 lines
drivers/iommu/iova.c +2 -2
@@ -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?

Quoted 43 lines
drivers/iommu/iova.c +0 -0
 		if (!iova_cache)
 			goto out_err;
 
include/linux/iova.h +3 -7
index d2c4fd923efa..eb4f9ead5451 100644
@@ -11,12 +11,11 @@
 
 #include <linux/types.h>
 #include <linux/kernel.h>
-#include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/dma-mapping.h>
 
 /* iova structure */
 struct iova {
-	struct rb_node	node;
 	unsigned long	pfn_hi; /* Highest allocated pfn */
 	unsigned long	pfn_lo; /* Lowest allocated pfn */
 };
@@ -26,15 +25,12 @@ struct iova_rcache;
 
 /* holds all the iova translations for a domain */
 struct iova_domain {
-	spinlock_t	iova_rbtree_lock; /* Lock to protect update of rbtree */
-	struct rb_root	rbroot;		/* iova domain rbtree root */
-	struct rb_node	*cached_node;	/* Save last alloced node */
-	struct rb_node	*cached32_node; /* Save last 32-bit alloced node */
+	spinlock_t	iova_lock;	/* 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;
Signature · 1 line
2.54.0
#3 lore raw

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

Quoted 12 lines · Liam R. Howlett
Quoted 10 lines · Rik van Riel

From: Rik van Riel <[email protected]>

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

Quoted 3 lines

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.

Quoted 17 lines
Quoted 8 lines

drivers/iommu/iova.c +1 -2
-	/* 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.

Quoted 2 lines

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.

Quoted 10 lines

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

Quoted 4 lines
drivers/iommu/iova.c +3 -0
+	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.

Quoted 6 lines

drivers/iommu/iova.c __adjust_overlap_range(struct iova *iova, · line 367

Quoted 3 lines
drivers/iommu/iova.c +3 -0
+	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.

Quoted 5 lines
Quoted 5 lines
(quoted diff) +0 -1
-	/* We are here either because this is the first reserver

node

drivers/iommu/iova.c +0 -3
-	 * or need to insert remaining non overlap addr range
-	 */
-	iova = __insert_new_range(iovad, pfn_lo, pfn_hi);
Quoted 9 lines

drivers/iommu/iova.c __adjust_overlap_range(struct iova *iova, · line 387

Quoted 5 lines
drivers/iommu/iova.c +4 -1
-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.

Quoted 6 lines
Quoted 6 lines
drivers/iommu/iova.c +4 -0
+	}
+
+	{
+		MA_STATE(mas, &iovad->mtree, merged_lo,

merged_hi);

Quoted 8 lines

Review

Quoted 1 line
(quoted diff) +0 -1
-	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.

Quoted 14 lines

drivers/iommu/iova.c int iova_cache_get(void) · line 812

Quoted 12 lines
(quoted diff) +0 -0
@@ -956,8 +808,8 @@ int iova_cache_get(void)


  mutex_lock(&iova_cache_mutex);
  if (!iova_cache_users) {

(quoted diff) +0 -1
-		iova_cache = kmem_cache_create("iommu_iova",

sizeof(struct iova), 0,

(quoted diff) +0 -1
-					       SLAB_HWCACHE_ALIGN,

NULL);

(quoted diff) +1 -0
+		iova_cache = kmem_cache_create("iommu_iova",

sizeof(struct iova),

drivers/iommu/iova.c +1 -0
+					       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.

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

PATCH v3 2/3 iova: add KUnit test suite

In reply to Rik van Riel

From: Rik van Riel <[email protected]>

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
---
 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
drivers/iommu/.kunitconfig new file +4 -0
new file mode 100644
index 000000000000..56b481ecf993
@@ -0,0 +1,4 @@
+CONFIG_KUNIT=y
+CONFIG_IOMMU_SUPPORT=y
+CONFIG_IOMMU_IOVA=y
+CONFIG_IOMMU_IOVA_KUNIT_TEST=y
drivers/iommu/Kconfig +16 -0
index f86262b11416..f09046e238fd 100644
@@ -3,6 +3,22 @@
 config IOMMU_IOVA
 	tristate
 
+config IOMMU_IOVA_KUNIT_TEST
+	tristate "KUnit tests for the IOVA allocator" if !KUNIT_ALL_TESTS
+	depends on IOMMU_IOVA && KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  Enable kunit tests for the IOVA allocator. The tests exercise
+	  basic allocation and free, size-aligned allocation, top-down
+	  ordering, bounded allocations with various DMA limits (32-bit,
+	  33-bit, 56-bit), aligned allocations in fragmented domains,
+	  and randomly-fragmented stress scenarios.
+
+	  Run with:
+	    tools/testing/kunit/kunit.py run --kunitconfig=drivers/iommu
+
+	  If unsure, say N here.
+
 # IOMMU_API always gets selected by whoever wants it.
 config IOMMU_API
 	bool
drivers/iommu/Makefile +1 -0
index 0275821f4ef9..6bd7da1cbebd 100644
@@ -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
drivers/iommu/iova-kunit.c new file +432 -0

432 lines not on this page · raw message

drivers/iommu/iova.c +34 -0
index 523d1e8315f9..1ceab6cbefc2 100644
@@ -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 <[email protected]>");
 MODULE_DESCRIPTION("IOMMU I/O Virtual Address management");
 MODULE_LICENSE("GPL");
include/linux/iova.h +3 -0
index eb4f9ead5451..6fc070a4f58e 100644
@@ -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)
 {
Signature · 1 line
2.54.0
#5 lore raw

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

In reply to Rik van Riel

From: Rik van Riel <[email protected]>

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
---
 drivers/iommu/iova.c | 84 +++++++++++++++++++++++++++++++++++++++-----
 include/linux/iova.h |  3 ++
 2 files changed, 79 insertions(+), 8 deletions(-)
drivers/iommu/iova.c +76 -8
index 1ceab6cbefc2..ae89d780fce5 100644
@@ -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;
 }
 
include/linux/iova.h +3 -0
index 6fc070a4f58e..cc1b5441a058 100644
@@ -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;
Signature · 1 line
2.54.0
#6 lore raw

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

Quoted 11 lines · Rik van Riel
drivers/iommu/iova.c +7 -0
+/*
+ * 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);

drivers/iommu/iova.c static void remove_iova(struct iova_domain *iovad, struct iova *iova) · line 179

Quoted 6 lines
drivers/iommu/iova.c +2 -1
@@ -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

#7 lore raw

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

Quoted 18 lines · Jason Gunthorpe
Quoted 17 lines · Rik van Riel

+/*
+ * 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);

(quoted diff) +0 -0
@@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
 *iovad, struct iova *iova)
  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
Quoted 9 lines

drivers/iommu/iova.c static void remove_iova(struct iova_domain *iovad, struct iova *iova) · line 179

Quoted 5 lines
(quoted diff) +0 -0
  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;

drivers/iommu/iova.c +2 -1
-	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.

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

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

In reply to Jason Gunthorpe
Quoted 18 lines · Jason Gunthorpe
Quoted 17 lines · Rik van Riel

+/*
+ * 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);

(quoted diff) +0 -0
@@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
 *iovad, struct iova *iova)
  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
Quoted 9 lines

drivers/iommu/iova.c static void remove_iova(struct iova_domain *iovad, struct iova *iova) · line 179

Quoted 5 lines
(quoted diff) +0 -0
  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;

drivers/iommu/iova.c +2 -1
-	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.

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

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

Quoted 28 lines · Rik van Riel
Quoted 18 lines · Jason Gunthorpe
Quoted 17 lines · Rik van Riel

+/*
+ * 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);

(quoted diff) +0 -0
@@ -165,7 +175,36 @@ static void remove_iova(struct iova_domain
 *iovad, struct iova *iova)
  	if (iova->pfn_lo < iovad->dma_32bit_pfn)
Quoted 9 lines

drivers/iommu/iova.c static void remove_iova(struct iova_domain *iovad, struct iova *iova) · line 179

Quoted 5 lines
(quoted diff) +0 -0
  		iovad->max32_alloc_size = iovad->dma_32bit_pfn;

drivers/iommu/iova.c +2 -1
-	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?

Quoted 5 lines

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

#10 lore raw

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

Quoted 9 lines · Jason Gunthorpe
Quoted 3 lines · Rik van Riel

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.

Quoted 5 lines

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.

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

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

Quoted 10 lines · Rik van Riel
Quoted 9 lines · Jason Gunthorpe
Quoted 3 lines · Rik van Riel

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.

Quoted 7 lines
Quoted 5 lines

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

#12 lore raw

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

+Cc maple-tree list.

Quoted 10 lines · Jason Gunthorpe
Quoted 9 lines · Rik van Riel
Quoted 8 lines · Jason Gunthorpe
Quoted 3 lines · Rik van Riel

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.

Quoted 22 lines
Quoted 8 lines
Quoted 6 lines

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;
Quoted 2 lines

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.

Quoted 8 lines

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.

Quoted 4 lines

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

#13 lore raw

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

Quoted 13 lines · Liam R. Howlett
Quoted 13 lines

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;
Quoted 5 lines
Quoted 2 lines

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

Quoted 4 lines

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

Quoted 4 lines

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.

Quoted 4 lines

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

#14 lore raw

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

Quoted 14 lines · Jason Gunthorpe
Quoted 13 lines · Liam R. Howlett
Quoted 13 lines

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;
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

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.

Quoted 14 lines
Quoted 5 lines

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

Quoted 4 lines

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.

Quoted 4 lines

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?

Quoted 6 lines
Quoted 5 lines

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?

Quoted 7 lines

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?

Quoted 6 lines

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

#15 lore raw

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

Quoted 18 lines · Liam R. Howlett
Quoted 17 lines · Jason Gunthorpe
Quoted 16 lines · Liam R. Howlett
Quoted 15 lines

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.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

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

Quoted 5 lines

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

Quoted 9 lines
Quoted 9 lines
Quoted 5 lines

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.

Quoted 7 lines
Quoted 4 lines

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

Quoted 6 lines
Quoted 2 lines

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

#16 lore raw

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

Quoted 22 lines · Jason Gunthorpe
Quoted 21 lines · Liam R. Howlett
Quoted 20 lines · Jason Gunthorpe
Quoted 18 lines · Liam R. Howlett
Quoted 13 lines

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;
Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

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.

...

Quoted 14 lines
Quoted 14 lines
Quoted 13 lines
Quoted 5 lines

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

Quoted 6 lines
Quoted 2 lines

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.

Quoted 22 lines
Quoted 7 lines
Quoted 3 lines

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);
	}
Quoted 7 lines

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.

Quoted 1 line

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

#17 lore raw

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

Quoted 7 lines · Liam R. Howlett
Quoted 1 line

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

Quoted 1 line

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

#18 lore raw

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

Quoted 4 lines · Jason Gunthorpe
Quoted 2 lines · Liam R. Howlett
Quoted 1 line

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

Quoted 8 lines
Quoted 5 lines

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.

Quoted 9 lines
Quoted 2 lines

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?

Quoted 7 lines

- 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

#19 lore raw

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

Quoted 9 lines · Liam R. Howlett
Quoted 7 lines · Jason Gunthorpe

- 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?

Quoted 6 lines

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?

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

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

Quoted 16 lines · Rik van Riel
Quoted 9 lines · Liam R. Howlett
Quoted 7 lines · Jason Gunthorpe

- 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?

Quoted 6 lines

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.

Quoted 4 lines

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

#21 lore raw

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

In reply to Liam R. Howlett
Quoted 8 lines · Liam R. Howlett
Quoted 7 lines · Jason Gunthorpe
Quoted 5 lines · Liam R. Howlett
Quoted 1 line

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():

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 6 lines

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"

Quoted 7 lines

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()?

Quoted 3 lines

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

#22 lore raw

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

Quoted 20 lines · Jason Gunthorpe
Quoted 8 lines · Liam R. Howlett
Quoted 7 lines · Jason Gunthorpe
Quoted 5 lines · Liam R. Howlett
Quoted 1 line

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():

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

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:

Review void *mtree_erase(struct maple_tree *mt, unsigned long index) · line 5923

Quoted 5 lines
(quoted diff) +2 -0
@@ -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.

Quoted 44 lines
(quoted diff) +0 -0
        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.

Quoted 7 lines
Quoted 6 lines

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"

Quoted 7 lines

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()?

Quoted 3 lines

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

Signature · 3 lines
maple-tree mailing list
[email protected]
https://lists.infradead.org/mailman/listinfo/maple-tree
#23 lore raw

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

In reply to Jason Gunthorpe
Quoted 6 lines · Jason Gunthorpe

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

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

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

Quoted 7 lines · Rik van Riel
Quoted 6 lines · Jason Gunthorpe

- 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?

Quoted 6 lines

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

#25 lore raw

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

Quoted 10 lines · Liam R. Howlett
Quoted 9 lines · Rik van Riel
Quoted 6 lines · Jason Gunthorpe

- 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?

Quoted 8 lines
Quoted 4 lines

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

#26 lore raw

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

Quoted 7 lines · Jason Gunthorpe
Quoted 5 lines · Liam R. Howlett

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

Quoted 6 lines

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.

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

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

In reply to Rik van Riel
Quoted 2 lines · Rik van Riel

From: Rik van Riel <[email protected]>

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]

Quoted 15 lines
drivers/iommu/iova.c +15 -0
+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))

drivers/iommu/iova.c static void remove_iova(struct iova_domain *iovad, struct iova *iova) · line 207

Quoted 10 lines
drivers/iommu/iova.c +10 -0
+			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

#28 lore raw

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

Quoted 9 lines · Ashok Raj

  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.

Quoted 6 lines

  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.

Signature · 1 line
All Rights Reversed.