[PATCH 0/3] Misc IOVA tweaks

[PATCH 0/3] Misc IOVA tweaks

[Robin Murphy]

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

-- 
2.13.4.dirty

[PATCH 1/3] iommu/iova: Simplify domain destruction

[Robin Murphy]

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 <robin.murphy-5wv7dgnIgG8@public.gmane.org>
---
 drivers/iommu/iova.c | 50 ++++++++++----------------------------------------
 1 file changed, 10 insertions(+), 40 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index a6cf775f75e0..35dde0fc7793 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -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]);
 	}
 }
 
-- 
2.13.4.dirty

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

[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 <robin.murphy@arm.com>
---
 drivers/iommu/iova.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 35dde0fc7793..8f8b436afd81 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -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);
 }
 
 /*
-- 
2.13.4.dirty

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

[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 <robin.murphy@arm.com>
---
 drivers/iommu/iova.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 8f8b436afd81..a7af8273fa98 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -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)
-- 
2.13.4.dirty

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

[Joerg Roedel]

On Tue, Sep 19, 2017 at 02:48:41PM +0100, Robin Murphy wrote:
> 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 <robin.murphy-5wv7dgnIgG8@public.gmane.org>
> ---
>  drivers/iommu/iova.c | 19 ++++++++++++++++---
>  1 file changed, 16 insertions(+), 3 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index 8f8b436afd81..a7af8273fa98 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -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];

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

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

[Robin Murphy]

On Wed, 27 Sep 2017 16:00:51 +0200
Joerg Roedel <joro-zLv9SwRftAIdnm+yROfE0A@public.gmane.org> wrote:

> On Tue, Sep 19, 2017 at 02:48:41PM +0100, Robin Murphy wrote:
> > 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 <robin.murphy-5wv7dgnIgG8@public.gmane.org>
> > ---
> >  drivers/iommu/iova.c | 19 ++++++++++++++++---
> >  1 file changed, 16 insertions(+), 3 deletions(-)
> > 
> > diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> > index 8f8b436afd81..a7af8273fa98 100644
> > --- a/drivers/iommu/iova.c
> > +++ b/drivers/iommu/iova.c
> > @@ -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];  
> 
> 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.

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

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

Signed-off-by: Robin Murphy <robin.murphy@arm.com>
---

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

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

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 506780084425..bb392fdc7a1b 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -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)
-- 
2.13.4.dirty

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

[Joerg Roedel]

On Thu, Sep 28, 2017 at 11:31:23AM +0100, Robin Murphy wrote:
> 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.
> 
> Signed-off-by: Robin Murphy <robin.murphy@arm.com>
> ---
> 
> 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.