Misc IOVA tweaks

PATCH In review Robin Murphy 2 participants 8 messages Sep 19, 2017 – Sep 28, 2017

Subsystems (2)

IOMMU IOMMU DMA-API layer

lore

Share & tools

lore

Robin Murphy

author maintainer

2017-09-19 13:48 UTC #0 lore raw

cover Misc IOVA tweaks

While I was elbow-deep in the IOVA code, a few other things came to light which don't really fit into the rbtree optimisation series. Patches #1 and #2 are more or less just cleanup, while patch #3 complements Tomasz' recent PCI allocation patch as it aims to potentially improve the same situation.

Last time I checked, these should all apply independently and without major conflicts against any other in-flight IOVA patches.

Robin.

Robin Murphy (3):
iommu/iova: Simplify domain destruction iommu/iova: Make rcache limit_pfn handling more robust iommu/iova: Try harder to allocate from rcache magazine

 drivers/iommu/iova.c | 73 ++++++++++++++++++++--------------------------------
 1 file changed, 28 insertions(+), 45 deletions(-)

Signature · 1 line

2.13.4.dirty

Robin Murphy

author maintainer

2017-09-19 13:48 UTC #1 lore raw

PATCH 1/3 iommu/iova: Simplify domain destruction

All put_iova_domain() should have to worry about is freeing memory - by that point the domain must no longer be live, so the act of cleaning up doesn't need to be concurrency-safe or maintain the rbtree in a self-consistent state. There's no need to waste time with locking or emptying the rcache magazines, and we can just use the postorder traversal helper to clear out the remaining rbtree entries in-place.

Signed-off-by Robin Murphy <[email protected]>

---
 drivers/iommu/iova.c | 50 ++++++++++----------------------------------------
 1 file changed, 10 insertions(+), 40 deletions(-)

drivers/iommu/iova.c +10 ~~-40~~

index a6cf775f75e0..35dde0fc7793 100644
@@ -588,21 +588,12 @@ EXPORT_SYMBOL_GPL(queue_iova);
  */
 void put_iova_domain(struct iova_domain *iovad)
 {
-	struct rb_node *node;
-	unsigned long flags;
+	struct iova *iova, *tmp;
 
 	free_iova_flush_queue(iovad);
 	free_iova_rcaches(iovad);
-	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
-	node = rb_first(&iovad->rbroot);
-	while (node) {
-		struct iova *iova = rb_entry(node, struct iova, node);
-
-		rb_erase(node, &iovad->rbroot);
+	rbtree_postorder_for_each_entry_safe(iova, tmp, &iovad->rbroot, node)
 		free_iova_mem(iova);
-		node = rb_first(&iovad->rbroot);
-	}
-	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 }
 EXPORT_SYMBOL_GPL(put_iova_domain);

@@ -995,46 +986,25 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad,
 }
 
 /*
- * Free a cpu's rcache.
- */
-static void free_cpu_iova_rcache(unsigned int cpu, struct iova_domain *iovad,
-				 struct iova_rcache *rcache)
-{
-	struct iova_cpu_rcache *cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
-	unsigned long flags;
-
-	spin_lock_irqsave(&cpu_rcache->lock, flags);
-
-	iova_magazine_free_pfns(cpu_rcache->loaded, iovad);
-	iova_magazine_free(cpu_rcache->loaded);
-
-	iova_magazine_free_pfns(cpu_rcache->prev, iovad);
-	iova_magazine_free(cpu_rcache->prev);
-
-	spin_unlock_irqrestore(&cpu_rcache->lock, flags);
-}
-
-/*
  * free rcache data structures.
  */
 static void free_iova_rcaches(struct iova_domain *iovad)
 {
 	struct iova_rcache *rcache;
-	unsigned long flags;
+	struct iova_cpu_rcache *cpu_rcache;
 	unsigned int cpu;
 	int i, j;
 
 	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 		rcache = &iovad->rcaches[i];
-		for_each_possible_cpu(cpu)
-			free_cpu_iova_rcache(cpu, iovad, rcache);
-		spin_lock_irqsave(&rcache->lock, flags);
-		free_percpu(rcache->cpu_rcaches);
-		for (j = 0; j < rcache->depot_size; ++j) {
-			iova_magazine_free_pfns(rcache->depot[j], iovad);
-			iova_magazine_free(rcache->depot[j]);
+		for_each_possible_cpu(cpu) {
+			cpu_rcache = per_cpu_ptr(rcache->cpu_rcaches, cpu);
+			iova_magazine_free(cpu_rcache->loaded);
+			iova_magazine_free(cpu_rcache->prev);
 		}
-		spin_unlock_irqrestore(&rcache->lock, flags);
+		free_percpu(rcache->cpu_rcaches);
+		for (j = 0; j < rcache->depot_size; ++j)
+			iova_magazine_free(rcache->depot[j]);
 	}
 }

Signature · 1 line

2.13.4.dirty

Robin Murphy

author maintainer

2017-09-19 13:48 UTC #2 lore raw

PATCH 2/3 iommu/iova: Make rcache limit_pfn handling more robust

In reply to Robin Murphy

When popping a pfn from an rcache, we are currently checking it directly against limit_pfn for viability. Since this represents iova->pfn_lo, it is technically possible for the corresponding iova->pfn_hi to be greater than limit_pfn. Although we generally get away with it in practice since limit_pfn is typically a power-of-two boundary and the IOVAs are size-aligned, it's pretty trivial to make the iova_rcache_get() path take the allocation size into account for complete safety.

Signed-off-by Robin Murphy <[email protected]>

---
 drivers/iommu/iova.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

drivers/iommu/iova.c +3 -3

index 35dde0fc7793..8f8b436afd81 100644
@@ -411,7 +411,7 @@ alloc_iova_fast(struct iova_domain *iovad, unsigned long size,
 	unsigned long iova_pfn;
 	struct iova *new_iova;
 
-	iova_pfn = iova_rcache_get(iovad, size, limit_pfn);
+	iova_pfn = iova_rcache_get(iovad, size, limit_pfn + 1);
 	if (iova_pfn)
 		return iova_pfn;

@@ -828,7 +828,7 @@ static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 {
 	BUG_ON(iova_magazine_empty(mag));
 
-	if (mag->pfns[mag->size - 1] >= limit_pfn)
+	if (mag->pfns[mag->size - 1] > limit_pfn)
 		return 0;
 
 	return mag->pfns[--mag->size];

@@ -982,7 +982,7 @@ static unsigned long iova_rcache_get(struct iova_domain *iovad,
 	if (log_size >= IOVA_RANGE_CACHE_MAX_SIZE)
 		return 0;
 
-	return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn);
+	return __iova_rcache_get(&iovad->rcaches[log_size], limit_pfn - size);
 }
 
 /*

Signature · 1 line

2.13.4.dirty

Robin Murphy

author maintainer

2017-09-19 13:48 UTC #3 lore raw

PATCH 3/3 iommu/iova: Try harder to allocate from rcache magazine

In reply to Robin Murphy

When devices with different DMA masks are using the same domain, or for PCI devices where we usually try a speculative 32-bit allocation first, there is a fair possibility that the top PFN of the rcache stack at any given time may be unsuitable for the lower limit, prompting a fallback to allocating anew from the rbtree. Consequently, we may end up artifically increasing pressure on the 32-bit IOVA space as unused IOVAs accumulate lower down in the rcache stacks, while callers with 32-bit masks also impose unnecessary rbtree overhead.

In such cases, let's try a bit harder to satisfy the allocation locally first - scanning the whole stack should still be relatively inexpensive, and even rotating an entry up from the very bottom probably has less overall impact than going to the rbtree.

Signed-off-by Robin Murphy <[email protected]>

---
 drivers/iommu/iova.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

drivers/iommu/iova.c +16 -3

index 8f8b436afd81..a7af8273fa98 100644
@@ -826,12 +826,25 @@ static bool iova_magazine_empty(struct iova_magazine *mag)
 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 				       unsigned long limit_pfn)
 {
+	int i;
+	unsigned long pfn;
+
 	BUG_ON(iova_magazine_empty(mag));
 
-	if (mag->pfns[mag->size - 1] > limit_pfn)
-		return 0;
+	/*
+	 * If we can pull a suitable pfn from anywhere in the stack, that's
+	 * still probably preferable to falling back to the rbtree.
+	 */
+	for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
+		if (i == 0)
+			return 0;
 
-	return mag->pfns[--mag->size];
+	pfn = mag->pfns[i];
+	mag->size--;
+	for (; i < mag->size; i++)
+		mag->pfns[i] = mag->pfns[i + 1];
+
+	return pfn;
 }
 
 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)

Signature · 1 line

2.13.4.dirty

Joerg Roedel

maintainer

2017-09-27 14:00 UTC #4 lore raw

Re: [PATCH 3/3] iommu/iova: Try harder to allocate from rcache magazine

Quoted 37 lines · Robin Murphy

When devices with different DMA masks are using the same domain, or for PCI devices where we usually try a speculative 32-bit allocation first, there is a fair possibility that the top PFN of the rcache stack at any given time may be unsuitable for the lower limit, prompting a fallback to allocating anew from the rbtree. Consequently, we may end up artifically increasing pressure on the 32-bit IOVA space as unused IOVAs accumulate lower down in the rcache stacks, while callers with 32-bit masks also impose unnecessary rbtree overhead.
In such cases, let's try a bit harder to satisfy the allocation locally first - scanning the whole stack should still be relatively inexpensive, and even rotating an entry up from the very bottom probably has less overall impact than going to the rbtree.
Signed-off-by Robin Murphy <[email protected]>
---
 drivers/iommu/iova.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)
drivers/iommu/iova.c +6 -2
index 8f8b436afd81..a7af8273fa98 100644
@@ -826,12 +826,25 @@ static bool iova_magazine_empty(struct iova_magazine *mag)
 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 				       unsigned long limit_pfn)
 {
+	int i;
+	unsigned long pfn;
+
 	BUG_ON(iova_magazine_empty(mag));
 
-	if (mag->pfns[mag->size - 1] > limit_pfn)
-		return 0;
+	/*
+	 * If we can pull a suitable pfn from anywhere in the stack, that's
+	 * still probably preferable to falling back to the rbtree.

drivers/iommu/iova.c static bool iova_magazine_empty(struct iova_magazine *mag) · line 845

Quoted 10 lines

drivers/iommu/iova.c +8 -1

+	 */
+	for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
+		if (i == 0)
+			return 0;
 
-	return mag->pfns[--mag->size];
+	pfn = mag->pfns[i];
+	mag->size--;
+	for (; i < mag->size; i++)
+		mag->pfns[i] = mag->pfns[i + 1];

Do we need to preserve the order of the elements on the stack or would it also suffice to just copy the top-element to the position we are removing?

Joerg

Robin Murphy

author maintainer

2017-09-27 16:50 UTC #5 lore raw

Re: [PATCH 3/3] iommu/iova: Try harder to allocate from rcache magazine

Quoted 45 lines · On Wed, 27 Sep 2017 16:00:51 +0200 Joerg Roedel…

Quoted 44 lines · Robin Murphy
When devices with different DMA masks are using the same domain, or for PCI devices where we usually try a speculative 32-bit allocation first, there is a fair possibility that the top PFN of the rcache stack at any given time may be unsuitable for the lower limit, prompting a fallback to allocating anew from the rbtree. Consequently, we may end up artifically increasing pressure on the 32-bit IOVA space as unused IOVAs accumulate lower down in the rcache stacks, while callers with 32-bit masks also impose unnecessary rbtree overhead.
In such cases, let's try a bit harder to satisfy the allocation locally first - scanning the whole stack should still be relatively inexpensive, and even rotating an entry up from the very bottom probably has less overall impact than going to the rbtree.
Signed-off-by Robin Murphy <[email protected]>
---
 drivers/iommu/iova.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)
drivers/iommu/iova.c +0 -0
index 8f8b436afd81..a7af8273fa98 100644
@@ -826,12 +826,25 @@ static bool iova_magazine_empty(struct
iova_magazine *mag) static unsigned long iova_magazine_pop(struct iova_magazine *mag, unsigned long limit_pfn)
{
drivers/iommu/iova.c +5 -2
+	int i;
+	unsigned long pfn;
+
 	BUG_ON(iova_magazine_empty(mag));
 
-	if (mag->pfns[mag->size - 1] > limit_pfn)
-		return 0;
+	/*
+	 * If we can pull a suitable pfn from anywhere in the
stack, that's
drivers/iommu/iova.c +5 -0
+	 * still probably preferable to falling back to the rbtree.
+	 */
+	for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
+		if (i == 0)
+			return 0;

Quoted 9 lines

drivers/iommu/iova.c static bool iova_magazine_empty(struct iova_magazine *mag) · line 845
Quoted 5 lines
drivers/iommu/iova.c +4 -1
-	return mag->pfns[--mag->size];
+	pfn = mag->pfns[i];
+	mag->size--;
+	for (; i < mag->size; i++)
+		mag->pfns[i] = mag->pfns[i + 1];  
Do we need to preserve the order of the elements on the stack or would it also suffice to just copy the top-element to the position we are removing?

Ooh, good point - the order is more or less meaningless, and if it *did* matter then that would imply we couldn't do this anyway. Getting rid of the second loop makes it even more compelling.

Robin.

Robin Murphy

author maintainer

2017-09-28 10:31 UTC #6 lore raw

PATCH v2 1/1 iommu/iova: Try harder to allocate from rcache magazine

In reply to Robin Murphy

In such cases, let's try a bit harder to satisfy the allocation locally first - scanning the whole stack should still be relatively inexpensive.

Signed-off-by Robin Murphy <[email protected]>

---

v2: There's no need for a 'proper' stack rotation

 drivers/iommu/iova.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

drivers/iommu/iova.c +12 -3

index 506780084425..bb392fdc7a1b 100644
@@ -822,12 +822,21 @@ static bool iova_magazine_empty(struct iova_magazine *mag)
 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 				       unsigned long limit_pfn)
 {
+	int i;
+	unsigned long pfn;
+
 	BUG_ON(iova_magazine_empty(mag));
 
-	if (mag->pfns[mag->size - 1] > limit_pfn)
-		return 0;
+	/* Only fall back to the rbtree if we have no suitable pfns at all */
+	for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--)
+		if (i == 0)
+			return 0;
 
-	return mag->pfns[--mag->size];
+	/* Swap it to pop it */
+	pfn = mag->pfns[i];
+	mag->pfns[i] = mag->pfns[--mag->size];
+
+	return pfn;
 }
 
 static void iova_magazine_push(struct iova_magazine *mag, unsigned long pfn)

Signature · 1 line

2.13.4.dirty

Joerg Roedel

maintainer Applied

2017-09-28 13:41 UTC #7 lore raw

Re: [PATCH v2] iommu/iova: Try harder to allocate from rcache magazine

Quoted 12 lines · Robin Murphy

When devices with different DMA masks are using the same domain, or for PCI devices where we usually try a speculative 32-bit allocation first, there is a fair possibility that the top PFN of the rcache stack at any given time may be unsuitable for the lower limit, prompting a fallback to allocating anew from the rbtree. Consequently, we may end up artifically increasing pressure on the 32-bit IOVA space as unused IOVAs accumulate lower down in the rcache stacks, while callers with 32-bit masks also impose unnecessary rbtree overhead.
In such cases, let's try a bit harder to satisfy the allocation locally first - scanning the whole stack should still be relatively inexpensive.

Quoted 7 lines

Signed-off-by Robin Murphy <[email protected]>
---
v2: There's no need for a 'proper' stack rotation
 drivers/iommu/iova.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

Thanks, applied the series.