[PATCH 2/2] iommu/iova: Use bottom-up allocation for DMA32

Chris Wilson chris at chris-wilson.co.uk
Sat Jan 16 21:46:04 UTC 2021


Since DMA32 allocations are currently allocated top-down from the 4G
boundary, this causes fragmentation and reduces the maximise allocation
size. On some systems, the dma address space may be extremely
constrained by PCIe windows, requiring a stronger anti-fragmentation
strategy.

Closes: https://gitlab.freedesktop.org/drm/intel/-/issues/2929
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
 drivers/iommu/dma-iommu.c |   4 +-
 drivers/iommu/iova.c      | 210 +++++++++++++++++++++++---------------
 include/linux/iova.h      |  14 ++-
 3 files changed, 138 insertions(+), 90 deletions(-)

diff --git a/drivers/iommu/dma-iommu.c b/drivers/iommu/dma-iommu.c
index 34353d8a785d..9f7553d23adf 100644
--- a/drivers/iommu/dma-iommu.c
+++ b/drivers/iommu/dma-iommu.c
@@ -351,9 +351,9 @@ static int iommu_dma_init_domain(struct iommu_domain *domain, dma_addr_t base,
 	}
 
 	/* start_pfn is always nonzero for an already-initialised domain */
-	if (iovad->start_pfn) {
+	if (iovad_start_pfn(iovad)) {
 		if (1UL << order != iovad->granule ||
-		    base_pfn != iovad->start_pfn) {
+		    base_pfn != iovad_start_pfn(iovad)) {
 			pr_warn("Incompatible range for DMA domain\n");
 			return -EFAULT;
 		}
diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 0c43c2b5f040..4b6175c88ac1 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -40,17 +40,26 @@ init_iova_domain(struct iova_domain *iovad, unsigned long granule,
 
 	spin_lock_init(&iovad->iova_rbtree_lock);
 	iovad->rbroot = RB_ROOT;
-	iovad->cached_node = &iovad->anchor.node;
-	iovad->cached32_node = &iovad->anchor.node;
 	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->flush_cb = NULL;
 	iovad->fq = NULL;
-	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);
+
+	INIT_LIST_HEAD(&iovad->holes);
+
+	iovad->head.pfn_lo = 0;
+	iovad->head.pfn_hi = start_pfn;
+	rb_link_node(&iovad->head.node, NULL, &iovad->rbroot.rb_node);
+	rb_insert_color(&iovad->head.node, &iovad->rbroot);
+	list_add(&iovad->head.hole, &iovad->holes);
+
+	iovad->tail.pfn_lo = IOVA_ANCHOR;
+	iovad->tail.pfn_hi = IOVA_ANCHOR;
+	rb_link_node(&iovad->tail.node,
+		     &iovad->head.node,
+		     &iovad->head.node.rb_right);
+	rb_insert_color(&iovad->tail.node, &iovad->rbroot);
+
 	init_iova_rcaches(iovad);
 }
 EXPORT_SYMBOL_GPL(init_iova_domain);
@@ -114,42 +123,6 @@ int init_iova_flush_queue(struct iova_domain *iovad,
 }
 EXPORT_SYMBOL_GPL(init_iova_flush_queue);
 
-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 = rb_entry(iovad->cached32_node, struct iova, 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);
-		iovad->max32_alloc_size = iovad->dma_32bit_pfn;
-	}
-
-	cached_iova = rb_entry(iovad->cached_node, struct iova, node);
-	if (free->pfn_lo >= cached_iova->pfn_lo)
-		iovad->cached_node = rb_next(&free->node);
-}
-
 /* Insert the iova into domain rbtree by holding writer lock */
 static void
 iova_insert_rbtree(struct rb_root *root, struct iova *iova,
@@ -178,65 +151,87 @@ iova_insert_rbtree(struct rb_root *root, struct iova *iova,
 	rb_insert_color(&iova->node, root);
 }
 
+static struct iova *iova_next(const struct iova *iova)
+{
+	return rb_entry(rb_next(&iova->node), struct iova, node);
+}
+
+static struct iova *iova_prev(const struct iova *iova)
+{
+	return rb_entry(rb_prev(&iova->node), struct iova, node);
+}
+
+static bool iova_hole_follows(const struct iova *iova, const struct iova *next)
+{
+	return iova->pfn_hi < next->pfn_lo - 1;
+}
+
 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 align_mask = ~0UL;
-	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
+	struct iova *prev, *next;
+	unsigned long new_pfn;
+	unsigned long flags;
+	struct iova *it;
 
 	if (size_aligned)
 		align_mask <<= fls_long(size - 1);
 
-	/* Walk the tree backwards */
+	if (size > ((limit_pfn - iovad_start_pfn(iovad)) & align_mask))
+		return -ENOMEM;
+
 	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
-	if (limit_pfn <= iovad->dma_32bit_pfn &&
-			size >= iovad->max32_alloc_size)
-		goto iova32_full;
+	if (limit_pfn <= iovad->dma_32bit_pfn) {
+		list_for_each_entry(it, &iovad->holes, hole) {
+			new_pfn = it->pfn_hi + 1;
+			if (new_pfn >= limit_pfn)
+				break;
 
-	curr = __get_cached_rbnode(iovad, limit_pfn);
-	curr_iova = rb_entry(curr, struct iova, node);
-	retry_pfn = curr_iova->pfn_hi + 1;
+			new_pfn = (new_pfn + ~align_mask) & align_mask;
+			if (new_pfn > limit_pfn - size)
+				break;
 
-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 = rb_entry(curr, struct iova, node);
-	} 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;
-			curr = &iovad->anchor.node;
-			curr_iova = rb_entry(curr, struct iova, node);
-			goto retry;
+			prev = it;
+			next = iova_next(it);
+			if (new_pfn + size - 1 < next->pfn_lo)
+				goto done;
 		}
-		iovad->max32_alloc_size = size;
-		goto iova32_full;
-	}
+	} else {
+		list_for_each_entry_reverse(it, &iovad->holes, hole) {
+			next = iova_next(it);
+			prev = it;
 
+			new_pfn = min(next->pfn_lo, limit_pfn);
+			if (new_pfn < size)
+				break;
+
+			new_pfn = (new_pfn - size) & align_mask;
+			if (new_pfn < iovad_start_pfn(iovad))
+				break;
+
+			if (new_pfn > prev->pfn_hi)
+				goto done;
+		}
+	}
+	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
+	return -ENOMEM;
+
+done:
 	/* 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;
 
 	/* 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);
+	iova_insert_rbtree(&iovad->rbroot, new, &prev->node);
+	if (iova_hole_follows(new, next))
+		list_add(&new->hole, &prev->hole);
+	if (!iova_hole_follows(prev, new))
+		list_del(&prev->hole);
 
 	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 	return 0;
-
-iova32_full:
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
-	return -ENOMEM;
 }
 
 static struct kmem_cache *iova_cache;
@@ -345,10 +340,38 @@ private_find_iova(struct iova_domain *iovad, unsigned long pfn)
 	return NULL;
 }
 
+static void remove_hole(struct iova_domain *iovad, struct iova *iova)
+{
+	struct iova *prev, *next;
+
+	prev = iova_prev(iova);
+	if (!iova_hole_follows(prev, iova)) {
+		struct iova *it = iova;
+
+		do {
+			next = iova_next(it);
+			if (!next) {
+				list_add_tail(&prev->hole, &iovad->holes);
+				break;
+			}
+			if (iova_hole_follows(it, next)) {
+				list_add_tail(&prev->hole, &it->hole);
+				break;
+			}
+
+			it = next;
+		} while (1);
+	}
+
+	next = iova_next(iova);
+	if (iova_hole_follows(iova, next))
+		list_del(&iova->hole);
+}
+
 static void private_free_iova(struct iova_domain *iovad, struct iova *iova)
 {
 	assert_spin_locked(&iovad->iova_rbtree_lock);
-	__cached_rbnode_delete_update(iovad, iova);
+	remove_hole(iovad, iova);
 	rb_erase(&iova->node, &iovad->rbroot);
 	free_iova_mem(iova);
 }
@@ -656,6 +679,24 @@ alloc_and_init_iova(unsigned long pfn_lo, unsigned long pfn_hi)
 	return iova;
 }
 
+static void insert_hole(struct iova_domain *iovad, struct iova *iova)
+{
+	if (iova_hole_follows(iova, iova_next(iova))) {
+		struct iova *prev, *it = iova;
+
+		do {
+			prev = iova_prev(it);
+			if (!prev || iova_hole_follows(prev, it))
+				break;
+			if (!iova_hole_follows(prev, iova))
+				list_del(&prev->hole);
+			it = prev;
+		} while (1);
+
+		list_add(&iova->hole, prev ? &prev->hole : &iovad->holes);
+	}
+}
+
 static struct iova *
 __insert_new_range(struct iova_domain *iovad,
 	unsigned long pfn_lo, unsigned long pfn_hi)
@@ -663,8 +704,11 @@ __insert_new_range(struct iova_domain *iovad,
 	struct iova *iova;
 
 	iova = alloc_and_init_iova(pfn_lo, pfn_hi);
-	if (iova)
-		iova_insert_rbtree(&iovad->rbroot, iova, NULL);
+	if (!iova)
+		return NULL;
+
+	iova_insert_rbtree(&iovad->rbroot, iova, NULL);
+	insert_hole(iovad, iova);
 
 	return iova;
 }
diff --git a/include/linux/iova.h b/include/linux/iova.h
index 76e16ae20729..076eb6cfc613 100644
--- a/include/linux/iova.h
+++ b/include/linux/iova.h
@@ -11,6 +11,7 @@
 
 #include <linux/types.h>
 #include <linux/kernel.h>
+#include <linux/list.h>
 #include <linux/rbtree.h>
 #include <linux/atomic.h>
 #include <linux/dma-mapping.h>
@@ -18,6 +19,7 @@
 /* iova structure */
 struct iova {
 	struct rb_node	node;
+	struct list_head hole;
 	unsigned long	pfn_hi; /* Highest allocated pfn */
 	unsigned long	pfn_lo; /* Lowest allocated pfn */
 };
@@ -68,12 +70,8 @@ struct iova_fq {
 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 */
 	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_fq __percpu *fq;	/* Flush Queue */
 
 	atomic64_t	fq_flush_start_cnt;	/* Number of TLB flushes that
@@ -82,7 +80,8 @@ struct iova_domain {
 	atomic64_t	fq_flush_finish_cnt;	/* Number of TLB flushes that
 						   have been finished */
 
-	struct iova	anchor;		/* rbtree lookup anchor */
+	struct list_head holes;
+	struct iova	head, tail;		/* rbtree lookup anchors */
 	struct iova_rcache rcaches[IOVA_RANGE_CACHE_MAX_SIZE];	/* IOVA range caches */
 
 	iova_flush_cb	flush_cb;	/* Call-Back function to flush IOMMU
@@ -251,4 +250,9 @@ static inline void free_cpu_cached_iovas(unsigned int cpu,
 }
 #endif
 
+static inline unsigned long iovad_start_pfn(struct iova_domain *iovad)
+{
+	return iovad->head.pfn_hi;
+}
+
 #endif
-- 
2.20.1



More information about the Intel-gfx-trybot mailing list