convert iova to maple tree
Subsystems (2)
cover convert iova to maple tree
Occasionally production workloads at Meta run into the linear search in alloc_iova() in ways that cause real issues. For example, when enough CPUs at a time fall into the linear search trap, systems have been known to get stuck for so long that it causes soft lockups.
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
v4:
- reduce the size of struct iova to 16 bytes
- simplify the (hopefully rare) remove_iova GFP_ATOMIC failure path
- test case for the deferred free code
v3:
- switch to maple tree (suggested by Robin Murphy)
v2:
- clean up selftests (thanks Jason Gunthorpe)
- address Sashiko concerns
- drop the search-with-alignment, since most iova requests should be of similar sizes, so the worst case behavior is unlikely to hit once ranges are excluded by the augmented rbtree
PATCH 1/3 iova: convert from rbtree to maple tree
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.
--- drivers/iommu/iova.c | 375 +++++++++++++++---------------------------- include/linux/iova.h | 10 +- 2 files changed, 133 insertions(+), 252 deletions(-)
drivers/iommu/iova.c +130 -245
@@ -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,87 @@ 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); +/* +* Drive the maple tree with iova_lock rather than its internal lock: +* the same lock already serialises the rest of the domain's mutable +* state (e.g. max32_alloc_size), and IOVA frees can run in hardirq +* context, so the tree lock must be irq-safe. +*/ +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); +/* +* Fast-fail a 32-bit request once one of the same-or-larger size has +* already failed, without searching. The hint is read under the lock +* that guards it: a lockless read could race an update and spuriously +* return -ENOMEM, and the cost is hidden by the tree walk that follows. +*/ if (limit_pfn <= iovad->dma_32bit_pfn && size >= iovad->max32_alloc_size) - goto iova32_full; - - curr =__get_cached_rbnode (iovad, limit_pfn); - curr_iova =to_iova (curr); - retry_pfn = curr_iova->pfn_hi; - -retry: -do { - high_pfn =min (high_pfn, curr_iova->pfn_lo); - new_pfn = (high_pfn - size) & align_mask; - prev = curr; - curr =rb_prev (curr); - curr_iova =to_iova (curr); - }while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn); - -if (high_pfn < size || new_pfn < low_pfn) { -if (low_pfn == iovad->start_pfn && retry_pfn < limit_pfn) { - high_pfn = limit_pfn; - low_pfn = retry_pfn +1 ; - curr =iova_find_limit (iovad, limit_pfn); - curr_iova =to_iova (curr); - goto retry; - } - iovad->max32_alloc_size = size; - goto iova32_full; + goto alloc_fail; + +if (mas_empty_area_rev (&mas, iovad->start_pfn, + limit_pfn -1 , search_size)) { +/* +* No gap of the requested size exists below limit_pfn. For a +* 32-bit allocation record the failing size, so later same-or- +* larger 32-bit allocations fail fast without searching until a +* free in the 32-bit range clears the hint. Only genuine space +* exhaustion updates the hint: the transient store failure +* below must not, or it would spuriously fail-fast valid +* allocations under memory pressure. +*/ +if (limit_pfn <= iovad->dma_32bit_pfn) + iovad->max32_alloc_size = size; + goto alloc_fail; } -/* pfn_lo will point to size aligned address if size_aligned is set */ +/* +* mas_empty_area_rev() guarantees a gap of at least search_size +* within [start_pfn, limit_pfn - 1], so the size-aligned PFN carved +* from the top of that gap is always >= mas.index >= start_pfn. +*/ + new_pfn = (mas.last - size +1 ) & align_mask; + new->pfn_lo = new_pfn; - new->pfn_hi = new->pfn_lo + size -1 ; + new->pfn_hi = new_pfn + size -1 ; -/* If we have 'prev', it's a valid place to start the insertion. */ -iova_insert_rbtree (&iovad->rbroot, new, prev); -__cached_rbnode_insert_update (iovad, new); + mas.index = new->pfn_lo; + mas.last = new->pfn_hi; +if (mas_store_gfp (&mas, new,GFP_ATOMIC )) + goto alloc_fail; -spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +spin_unlock_irqrestore (&iovad->iova_lock, flags);return 0 ; -iova32_full: -spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +alloc_fail: +spin_unlock_irqrestore (&iovad->iova_lock, flags);return -ENOMEM ; }
@@ -233,8 +133,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 +174,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; - -assert_spin_locked (&iovad->iova_rbtree_lock); +MA_STATE (mas, &iovad->mtree, pfn, pfn); -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 +204,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 +222,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 +242,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 +336,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 +362,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 +369,67 @@ __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; +struct iova *iova =NULL , *overlap; +unsigned long merged_lo = pfn_lo, merged_hi = pfn_hi;unsigned long flags; -struct iova *iova; -unsigned int overlap =0 ; + +MA_STATE (mas, &iovad->mtree, pfn_lo, pfn_hi); +MA_STATE (fmas, &iovad->mtree,0 ,0 );/* Don't allow nonsensical pfns */ if (WARN_ON ((pfn_hi | pfn_lo) > (ULLONG_MAX >>iova_shift (iovad))))return NULL ; -spin_lock_irqsave (&iovad->iova_rbtree_lock, flags); -for (node =rb_first (&iovad->rbroot); node; node =rb_next (node)) { -if (__is_range_overlap (node, pfn_lo, pfn_hi)) { - iova =to_iova (node); -__adjust_overlap_range (iova, &pfn_lo, &pfn_hi); -if ((pfn_lo >= iova->pfn_lo) && - (pfn_hi <= iova->pfn_hi)) - goto finish; - overlap =1 ; - - }else if (overlap) -break ; +spin_lock_irqsave (&iovad->iova_lock, flags); + +/* +* Compute the range covering all overlaps, but do not free the +* overlapping iovas yet: the merged store below can fail, and freeing +* before a failed store would leave dangling pointers in the tree. +*/ +mas_for_each (&mas, overlap, pfn_hi) { +/* Fully covered by an existing reservation: hand it back. */ +if (pfn_lo >= overlap->pfn_lo && pfn_hi <= overlap->pfn_hi) { + iova = overlap; + goto out; + } +if (overlap->pfn_lo < merged_lo) + merged_lo = overlap->pfn_lo; +if (overlap->pfn_hi > merged_hi) + merged_hi = overlap->pfn_hi; } -/* We are here either because this is the first reserver node -* or need to insert remaining non overlap addr range + iova =alloc_and_init_iova (merged_lo, merged_hi); +if (!iova) + goto out; + +/* +* Preallocate the nodes for the merged store so it cannot fail; only +* then free the now-superseded overlaps and store the merged range. */ - iova =__insert_new_range (iovad, pfn_lo, pfn_hi); -finish: +mas_set_range (&mas, merged_lo, merged_hi); +if (mas_preallocate (&mas, iova,GFP_ATOMIC )) { +free_iova_mem (iova); + iova =NULL ; + goto out; + } + +mas_set_range (&fmas, merged_lo, merged_hi); +mas_for_each (&fmas, overlap, merged_hi) +free_iova_mem (overlap); -spin_unlock_irqrestore (&iovad->iova_rbtree_lock, flags); +mas_store_prealloc (&mas, iova); +out: +spin_unlock_irqrestore (&iovad->iova_lock, flags);return iova; }EXPORT_SYMBOL_GPL (reserve_iova);
@@ -621,7 +506,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 +518,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 +841,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
@@ -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.53.0-Meta
PATCH 2/3 iova: add KUnit test suite
In reply to Rik van RielAdd 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
--- drivers/iommu/.kunitconfig | 6 + drivers/iommu/Kconfig | 16 ++ drivers/iommu/Makefile | 1 + drivers/iommu/iova-kunit.c | 439 +++++++++++++++++++++++++++++++++++++ drivers/iommu/iova.c | 34 +++ include/linux/iova.h | 3 + 6 files changed, 499 insertions(+) create mode 100644 drivers/iommu/.kunitconfig create mode 100644 drivers/iommu/iova-kunit.c
drivers/iommu/.kunitconfig new file +6 -0
@@ -0,0 +1,6 @@ +CONFIG_KUNIT=y +CONFIG_IOMMU_SUPPORT=y +CONFIG_IOMMU_IOVA=y +CONFIG_IOMMU_IOVA_KUNIT_TEST=y +CONFIG_KASAN=y +CONFIG_KASAN_GENERIC=y
drivers/iommu/Kconfig +16 -0
@@ -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
@@ -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 +439 -0
439 lines not on this page · raw message
drivers/iommu/iova.c +34 -0
@@ -890,6 +890,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
@@ -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.53.0-Meta
PATCH 3/3 iova: defer maple tree erase on GFP_ATOMIC failure
In reply to Rik van RielUnlike the old rbtree, where rb_erase() never allocates, removing an entry from the maple tree can require a node for rebalancing, and mas_store_gfp(NULL, GFP_ATOMIC) can fail under memory pressure. The IOVA allocator frees in atomic context (DMA map/unmap may run from hardirq, softirq, or with spinlocks held), where the erase must not fail and GFP_KERNEL is not available.
When the GFP_ATOMIC erase fails, overwrite the slot in place with a marker (IOVA_DEFERRED) and free the struct iova immediately. Unlike erasing, an in-place store over the entry's existing range changes no range boundaries, so it needs no node for rebalancing and cannot fail:
storing NULL first runs mas_wr_extend_null(), which can widen the range and escape the allocation-free wr_exact_fit store type, whereas storing a non-NULL value over the same range stays wr_exact_fit. The marker is a non-NULL, non-internal pointer, so the allocator's gap search keeps the range reserved, while lookups, teardown and the invariant checker recognise and skip it.
The slots that need a later erase are tracked by a [deferred_lo, deferred_hi] bounding range in the domain. The deferred erase is retried, returning the address space for reuse, by the next allocation in the domain (before it searches for free space) or by the next successful free, via iova_drain_deferred(), which walks only that bounding range.
This keeps struct iova at 16 bytes: the rare-path state lives in the maple tree (the marker) and two unsigned longs in the domain, rather than a per-iova list node paid by every live mapping. No timer or workqueue is needed; the erase that can fail is moved off the free path and onto the allocation path, where running out of memory can simply be reported to the caller.
In practice GFP_ATOMIC erase failures are rare: the slab allocator keeps emergency reserves, the common erase case needs no node allocation at all, and the first allocation attempt is backed by per-CPU caches. This mechanism is a safety net for the exceptional case.
--- drivers/iommu/iova-kunit.c | 70 ++++++++++++++++ drivers/iommu/iova.c | 168 +++++++++++++++++++++++++++++++++---- include/linux/iova.h | 9 ++ 3 files changed, 233 insertions(+), 14 deletions(-)
drivers/iommu/iova-kunit.c +70 -0
@@ -413,6 +413,74 @@ static void test_fragmented_32bit_search(struct kunit *test)__free_iova (&ctx->iovad, iova); } +/* +* Exercise the deferred-erase path: remove_iova() failing to erase under +* GFP_ATOMIC leaves an IOVA_DEFERRED marker in the tree and frees the struct +* iova immediately. iova_kunit_defer_erase makes that failure deterministic. +* Verify that while marked the range looks free to lookups yet stays reserved, +* that invariants hold, and that the next allocation drains the marker and +* reuses the space. +*/ +static void test_deferred_erase (struct kunit *test) +{ +struct iova_test_ctx *ctx = test->priv; +struct iova *a, *b; +unsigned long pfn; + + a =alloc_iova (&ctx->iovad,1 ,TEST_LIMIT_32BIT , false); +KUNIT_ASSERT_NOT_NULL (test, a); + pfn = a->pfn_lo; + +/* Free 'a', forcing the erase to be deferred (marker left behind). */ + iova_kunit_defer_erase = true; +__free_iova (&ctx->iovad, a); + iova_kunit_defer_erase = false; + +/* +* The erase was deferred, not performed: a marker now occupies the slot, +* so the backlog records the deferral and the pfn looks absent to lookups, +* while the tree stays consistent with the marker present. +*/ +KUNIT_EXPECT_TRUE (test,iova_domain_has_deferred (&ctx->iovad)); +KUNIT_EXPECT_NULL (test,find_iova (&ctx->iovad, pfn)); +KUNIT_EXPECT_TRUE (test,iova_domain_verify_invariants (&ctx->iovad)); + +/* +* The next allocation drains deferred markers before searching, so the +* backlog clears and the marked range is reclaimed; a top-down size-1 +* alloc reuses exactly the pfn that was freed. +*/ + b =alloc_iova (&ctx->iovad,1 ,TEST_LIMIT_32BIT , false); +KUNIT_ASSERT_NOT_NULL (test, b); +KUNIT_EXPECT_FALSE (test,iova_domain_has_deferred (&ctx->iovad)); +KUNIT_EXPECT_EQ (test, b->pfn_lo, pfn); +KUNIT_EXPECT_TRUE (test,iova_domain_verify_invariants (&ctx->iovad)); + +__free_iova (&ctx->iovad, b); +KUNIT_EXPECT_TRUE (test,iova_domain_verify_invariants (&ctx->iovad)); +} + +/* +* Tearing down a domain that still holds an undrained IOVA_DEFERRED marker must +* skip the marker (it is static storage, not a heap iova) and not crash or +* double-free. Leave a marker live for iova_test_exit()'s put_iova_domain(). +*/ +static void test_deferred_erase_teardown (struct kunit *test) +{ +struct iova_test_ctx *ctx = test->priv; +struct iova *a; + + a =alloc_iova (&ctx->iovad,4 ,TEST_LIMIT_32BIT , false); +KUNIT_ASSERT_NOT_NULL (test, a); + + iova_kunit_defer_erase = true; +__free_iova (&ctx->iovad, a); + iova_kunit_defer_erase = false; + +/* Marker left live; the suite's exit -> put_iova_domain must cope. */ +KUNIT_EXPECT_TRUE (test,iova_domain_verify_invariants (&ctx->iovad)); +} +static struct kunit_case iova_test_cases[] = {KUNIT_CASE (test_size_aligned),KUNIT_CASE (test_top_down_preference),
@@ -424,6 +492,8 @@ static struct kunit_case iova_test_cases[] = {KUNIT_CASE (test_stress_random),KUNIT_CASE (test_full_space_search_time),KUNIT_CASE (test_fragmented_32bit_search), +KUNIT_CASE (test_deferred_erase), + KUNIT_CASE(test_deferred_erase_teardown), {} };
drivers/iommu/iova.c +154 -14
259 lines not on this page · raw message
include/linux/iova.h +9 -0
@@ -31,6 +31,13 @@ struct iova_domain {unsigned long start_pfn;/* Lower limit for this domain */ unsigned long dma_32bit_pfn;unsigned long max32_alloc_size;/* Size of last failed allocation */ +/* +* Bounding range of slots whose erase was deferred because a node +* allocation failed under GFP_ATOMIC; deferred_lo > deferred_hi when +* there are none. See remove_iova()/iova_drain_deferred(). +*/ +unsigned long deferred_lo; +unsigned long deferred_hi;struct iova_rcache *rcaches;struct hlist_node cpuhp_dead;
@@ -100,6 +107,8 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn);void put_iova_domain (struct iova_domain *iovad);#if IS_ENABLED (CONFIG_IOMMU_IOVA_KUNIT_TEST )bool iova_domain_verify_invariants (struct iova_domain *iovad); +bool iova_domain_has_deferred (struct iova_domain *iovad); +extern bool iova_kunit_defer_erase;#endif #else static inline int iova_cache_get (void )
Signature · 1 line
2.53.0-Meta
Re: [PATCH 3/3] iova: defer maple tree erase on GFP_ATOMIC failure
On Tue, Jun 23, 2026 at 11:07:36PM -0400, Rik van Riel wrote:
Hi Rik,
Thanks for the v4 redesign — the in-place marker approach is much cleaner than the delayed_work/llist scheme from v3, and it directly addresses the retry-forever concern I raised earlier.
[snip]
Quoted 21 lines
drivers/iommu/iova.c +15
-1+/* +* Remove an IOVA entry from the maple tree and free it. +* +* This runs in atomic context (DMA map/unmap can be called from hardirq, +* softirq, or with spinlocks held) and must not fail. Erasing an entry can +* require a maple tree node for rebalancing, and mas_store_gfp(NULL, +* GFP_ATOMIC) can fail under memory pressure. When it does, overwrite the slot +* in place with IOVA_DEFERRED -- an in-place store needs no node allocation and +* so cannot fail -- which keeps the address range reserved (the allocator's gap +* search treats the non-NULL slot as occupied) and lets the struct iova be +* freed now. The marker is erased later by iova_drain_deferred(). +*/ static void remove_iova (struct iova_domain *iovad,struct iova *iova) { -MA_STATE (mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi); +unsigned long pfn_lo = iova->pfn_lo, pfn_hi = iova->pfn_hi; + +MA_STATE (mas, &iovad->mtree, pfn_lo, pfn_hi);assert_spin_locked (&iovad->iova_lock);
drivers/iommu/iova.c static struct iova * · line 298
Quoted 10 lines
drivers/iommu/iova.c +6
-2-if (iova->pfn_lo < iovad->dma_32bit_pfn) +if (pfn_lo < iovad->dma_32bit_pfn) iovad->max32_alloc_size = iovad->dma_32bit_pfn; -mas_store_gfp (&mas,NULL ,GFP_ATOMIC ); +if (iova_kunit_defer_erase ||mas_store_gfp (&mas,NULL ,GFP_ATOMIC )) { +/* Erase failed: mark the slot in place and defer removal. */ +mas_set_range (&mas, pfn_lo, pfn_hi); +if (WARN_ON_ONCE (mas_store_gfp (&mas,IOVA_DEFERRED ,GFP_ATOMIC ))) +return ;/* in-place store cannot fail; entry stays put */
/* * <-- deferred_lo/hi not updated and range stays * occupied for ever? */
drivers/iommu/iova.c static struct iova * · line 303
Quoted 5 lines
drivers/iommu/iova.c +5
-0+if (pfn_lo < iovad->deferred_lo) + iovad->deferred_lo = pfn_lo; +if (pfn_hi > iovad->deferred_hi) + iovad->deferred_hi = pfn_hi; +free_iova_mem (iova);
<--- only reached if second store succeeds?
drivers/iommu/iova.c static struct iova * · line 312
Quoted 10 lines
drivers/iommu/iova.c +8
-0+return ; + } + +free_iova_mem (iova); + +/* A successful erase means memory is available; clear any backlog. */ +if (unlikely (iova_has_deferred (iovad))) +iova_drain_deferred (iovad); }
If the in-place marker store fails and WARN_ON_ONCE fires:
- free_iova_mem(iova) is never reached — the struct iova leaks.
- deferred_lo/hi is not updated — the address range stays permanently occupied with no way to reclaim it.
- After the first occurrence, WARN_ON_ONCE suppresses the warning on all subsequent hits, so further failures on this path are completely silent.
I understand the comment says this cannot happen, and if that guarantee holds then it's fine. But if it can, a BUG_ON might be a cleaner way to express that invariant — it makes the intent unambiguous rather than leaving the impression the failure is being gracefully handled when it isn't.
Happy to be wrong if I'm missing something about the maple tree's in-place store guarantees.
Cheers,
Ashok
Quoted 6 lines · Rik van Riel
Based on
5d6919055decLinux 7.1-rc3v4:
- reduce the size of struct iova to 16 bytes
- simplify the (hopefully rare)remove_iovaGFP_ATOMICfailure path
- test case for the deferred free code
Somehow the v4 in the subject got dropped out.
Quoted 11 lines
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
Signature · 3 lines
/ashok.raj [email protected] Qualcomm Inc
Re: [PATCH 3/3] iova: defer maple tree erase on GFP_ATOMIC failure
In reply to Ashok RajQuoted 52 lines · Ashok Raj
On Tue, Jun 23, 2026 at 11:07:36PM -0400, Rik van Riel wrote:
Hi Rik,
Thanks for the v4 redesign — the in-place marker approach is much cleaner than
the delayed_work/llist scheme from v3, and it directly addresses the
retry-forever concern I raised earlier.[snip]
Quoted 40 lines
+/*
+ * Remove an IOVA entry from the maple tree and free it.
+ *
+ * This runs in atomic context (DMA map/unmap can be called from hardirq,
+ * softirq, or with spinlocks held) and must not fail. Erasing an entry can
+ * require a maple tree node for rebalancing, and mas_store_gfp(NULL,
+ *GFP_ATOMIC) can fail under memory pressure. When it does, overwrite the slot
+ * in place withIOVA_DEFERRED-- an in-place store needs no node allocation and
+ * so cannot fail -- which keeps the address range reserved (the allocator's gap
+ * search treats the non-NULL slot as occupied) and lets the struct iova be
+ * freed now. The marker is erased later byiova_drain_deferred().
+ */
static voidremove_iova(struct iova_domain *iovad, struct iova *iova)
{(quoted diff) +1
-1- MA_STATE(mas, &iovad->mtree, iova->pfn_lo, iova->pfn_hi); + unsigned long pfn_lo = iova->pfn_lo, pfn_hi = iova-Quoted 1 line
pfn_hi;(quoted diff) +2
-0+ + MA_STATE(mas, &iovad->mtree, pfn_lo, pfn_hi);
assert_spin_locked(&iovad->iova_lock);drivers/iommu/iova.c +1
-1-if (iova->pfn_lo < iovad->dma_32bit_pfn) +if (pfn_lo < iovad->dma_32bit_pfn)
iovad->max32_alloc_size=iovad->dma_32bit_pfn;(quoted diff) +1
-1- mas_store_gfp(&mas, NULL, GFP_ATOMIC); + if (iova_kunit_defer_erase || mas_store_gfp(&mas, NULL,
GFP_ATOMIC)) {(quoted diff) +1
-0+ /* Erase failed: mark the slot in place and deferremoval. */
drivers/iommu/iova.c +1
-0+mas_set_range (&mas, pfn_lo, pfn_hi);
Quoted 8 lines
Quoted 4 lines
(quoted diff) +1
-0+ if (WARN_ON_ONCE(mas_store_gfp(&mas,
IOVA_DEFERRED,GFP_ATOMIC)))(quoted diff) +1
-0+ return; /* in-place store cannotfail; entry stays put */
/* * <-- deferred_lo/hi not updated and range stays * occupied for ever? */
If the in-place store fails, then updating deferred_lo / hi won't help, since the sweep later on will be unable to identify this area.
Freeing the iova at that point would leave the maple tree with a pointer into memory that could be re-used for something else.
We need to either return early and warn, or panic.
I'm fine with either.
Robin, do you have a preference here?
Quoted 9 lines
drivers/iommu/iova.c static struct iova * · line 303
Quoted 5 lines
drivers/iommu/iova.c +5
-0+if (pfn_lo < iovad->deferred_lo) + iovad->deferred_lo = pfn_lo; +if (pfn_hi > iovad->deferred_hi) + iovad->deferred_hi = pfn_hi; + free_iova_mem(iova);<--- only reached if second store succeeds?
Quoted 3 lines
(quoted diff) +2
-0+ return; + }
Signature · 1 line
All Rights Reversed.