Skip to contentSkip to conversation

iommu/iova: Retry from last rb tree node if iova search fails

PATCH In review [email protected] 3 participants 7 messages Jul 3, 2020 – Sep 14, 2020

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/2 iommu/iova: Retry from last rb tree node if iova search fails

From: Vijayanand Jitta <[email protected]>

When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.

Consider the following sequence of iova alloc and frees on 1GB of iova space

1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MB

After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.

To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available.

---
 drivers/iommu/iova.c | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)
drivers/iommu/iova.c +17 -6
index 49fc01f..4e77116 100644
@@ -184,8 +184,9 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 	struct rb_node *curr, *prev;
 	struct iova *curr_iova;
 	unsigned long flags;
-	unsigned long new_pfn;
+	unsigned long new_pfn, low_pfn_new;
 	unsigned long align_mask = ~0UL;
+	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
 
 	if (size_aligned)
 		align_mask <<= fls_long(size - 1);
@@ -198,15 +199,25 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 
 	curr = __get_cached_rbnode(iovad, limit_pfn);
 	curr_iova = rb_entry(curr, struct iova, node);
+	low_pfn_new = curr_iova->pfn_hi + 1;
+
+retry:
 	do {
-		limit_pfn = min(limit_pfn, curr_iova->pfn_lo);
-		new_pfn = (limit_pfn - size) & align_mask;
+		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);
-
-	if (limit_pfn < size || new_pfn < iovad->start_pfn) {
+	} 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 && low_pfn_new < limit_pfn) {
+			high_pfn = limit_pfn;
+			low_pfn = low_pfn_new;
+			curr = &iovad->anchor.node;
+			curr_iova = rb_entry(curr, struct iova, node);
+			goto retry;
+		}
 		iovad->max32_alloc_size = size;
 		goto iova32_full;
 	}
Signature · 7 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
1.9.1

_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
#1 lore raw

PATCH 2/2 iommu/iova: Free global iova rcache on iova alloc failure

From: Vijayanand Jitta <[email protected]>

When ever an iova alloc request fails we free the iova ranges present in the percpu iova rcaches and then retry but the global iova rcache is not freed as a result we could still see iova alloc failure even after retry as global rcache is holding the iova's which can cause fragmentation. So, free the global iova rcache as well and then go for the retry.

Change-Id Ib8236dc88ba5516b73d4fbf6bf8e68bbf09bbad2
---
 drivers/iommu/iova.c | 23 +++++++++++++++++++++++
 include/linux/iova.h |  6 ++++++
 2 files changed, 29 insertions(+)
drivers/iommu/iova.c +23 -0
index 4e77116..5836c87 100644
@@ -442,6 +442,7 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 		flush_rcache = false;
 		for_each_online_cpu(cpu)
 			free_cpu_cached_iovas(cpu, iovad);
+		free_global_cached_iovas(iovad);
 		goto retry;
 	}
 
@@ -1055,5 +1056,27 @@ void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
 	}
 }
 
+/*
+ * free all the IOVA ranges of global cache
+ */
+void free_global_cached_iovas(struct iova_domain *iovad)
+{
+	struct iova_rcache *rcache;
+	unsigned long flags;
+	int i, j;
+
+	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
+		rcache = &iovad->rcaches[i];
+		spin_lock_irqsave(&rcache->lock, flags);
+		for (j = 0; j < rcache->depot_size; ++j) {
+			iova_magazine_free_pfns(rcache->depot[j], iovad);
+			iova_magazine_free(rcache->depot[j]);
+			rcache->depot[j] = NULL;
+		}
+		rcache->depot_size = 0;
+		spin_unlock_irqrestore(&rcache->lock, flags);
+	}
+}
+
 MODULE_AUTHOR("Anil S Keshavamurthy <[email protected]>");
 MODULE_LICENSE("GPL");
include/linux/iova.h +6 -0
index a0637ab..a905726 100644
@@ -163,6 +163,7 @@ int init_iova_flush_queue(struct iova_domain *iovad,
 struct iova *split_and_remove_iova(struct iova_domain *iovad,
 	struct iova *iova, unsigned long pfn_lo, unsigned long pfn_hi);
 void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
+void free_global_cached_iovas(struct iova_domain *iovad);
 #else
 static inline int iova_cache_get(void)
 {
@@ -270,6 +271,11 @@ static inline void free_cpu_cached_iovas(unsigned int cpu,
 					 struct iova_domain *iovad)
 {
 }
+
+static inline void free_global_cached_iovas(struct iova_domain *iovad)
+{
+}
+
 #endif
 
 #endif
Signature · 7 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
1.9.1

_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
#2 lore raw

Re: [PATCH 2/2] iommu/iova: Free global iova rcache on iova alloc failure

Quoted 72 lines · On 7/3/2020 7:47 PM, [email protected] wrote:

From: Vijayanand Jitta <[email protected]>

When ever an iova alloc request fails we free the iova ranges present in the percpu iova rcaches and then retry but the global iova rcache is not freed as a result we could still see iova alloc failure even after retry as global rcache is holding the iova's which can cause fragmentation. So, free the global iova rcache as well and then go for the retry.

Change-Id Ib8236dc88ba5516b73d4fbf6bf8e68bbf09bbad2
---
 drivers/iommu/iova.c | 23 +++++++++++++++++++++++
 include/linux/iova.h |  6 ++++++
 2 files changed, 29 insertions(+)
drivers/iommu/iova.c +23 -0
index 4e77116..5836c87 100644
@@ -442,6 +442,7 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
 		flush_rcache = false;
 		for_each_online_cpu(cpu)
 			free_cpu_cached_iovas(cpu, iovad);
+		free_global_cached_iovas(iovad);
 		goto retry;
 	}
 
@@ -1055,5 +1056,27 @@ void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
 	}
 }
 
+/*
+ * free all the IOVA ranges of global cache
+ */
+void free_global_cached_iovas(struct iova_domain *iovad)
+{
+	struct iova_rcache *rcache;
+	unsigned long flags;
+	int i, j;
+
+	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
+		rcache = &iovad->rcaches[i];
+		spin_lock_irqsave(&rcache->lock, flags);
+		for (j = 0; j < rcache->depot_size; ++j) {
+			iova_magazine_free_pfns(rcache->depot[j], iovad);
+			iova_magazine_free(rcache->depot[j]);
+			rcache->depot[j] = NULL;
+		}
+		rcache->depot_size = 0;
+		spin_unlock_irqrestore(&rcache->lock, flags);
+	}
+}
+
 MODULE_AUTHOR("Anil S Keshavamurthy <[email protected]>");
 MODULE_LICENSE("GPL");
include/linux/iova.h +1 -0
index a0637ab..a905726 100644
@@ -163,6 +163,7 @@ int init_iova_flush_queue(struct iova_domain *iovad,
 struct iova *split_and_remove_iova(struct iova_domain *iovad,
 	struct iova *iova, unsigned long pfn_lo, unsigned long pfn_hi);
 void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
+void free_global_cached_iovas(struct iova_domain *iovad);
 #else
 static inline int iova_cache_get(void)
 {
@@ -270,6 +271,11 @@ static inline void free_cpu_cached_iovas(unsigned int cpu,
 					 struct iova_domain *iovad)

include/linux/iova.h static inline void free_cpu_cached_iovas(unsigned int cpu, · line 281

Quoted 10 lines
include/linux/iova.h +5 -0
 {
 }
+
+static inline void free_global_cached_iovas(struct iova_domain *iovad)
+{
+}
+
 #endif
 
 #endif

ping?

Signature · 6 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of Code Aurora Forum, hosted by The Linux Foundation
_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
maintainer
#3 lore raw

Re: [PATCH 2/2] iommu/iova: Free global iova rcache on iova alloc failure

Quoted 1 line · Vijayanand Jitta

ping?

Please repost when v5.9-rc1 is released and add

Robin Murphy <[email protected]>

on your Cc list.

Thanks,

Joerg

#4 lore raw

Re: [PATCH 2/2] iommu/iova: Free global iova rcache on iova alloc failure

Quoted 5 lines · Joerg Roedel
Quoted 1 line · Vijayanand Jitta

ping?

Please repost when v5.9-rc1 is released and add

Quoted 8 lines

Robin Murphy <[email protected]>

on your Cc list.

Thanks,

Joerg

Sure, will do.

Thanks,
Vijay

Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of Code Aurora Forum, hosted by The Linux Foundation
#5 lore raw

Re: [PATCH 2/2] iommu/iova: Free global iova rcache on iova alloc failure

Quoted 14 lines · Vijayanand Jitta
Quoted 11 lines · Joerg Roedel
Quoted 1 line · Vijayanand Jitta

ping?

Please repost when v5.9-rc1 is released and add

Robin Murphy <[email protected]>

on your Cc list.

Thanks,

Quoted 8 lines
Quoted 2 lines

Joerg

Sure, will do.

Thanks,
Vijay

And a cover letter would be useful also, to at least us know what changes have been made per version.

drivers/iommu/iova.c struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn) · line 445

Quoted 10 lines
drivers/iommu/iova.c +1 -0
index 4e77116..5836c87 100644
@@ -442,6 +442,7 @@ struct iova *find_iova(struct iova_domain *iovad, unsigned long pfn)
  		flush_rcache = false;
  		for_each_online_cpu(cpu)
  			free_cpu_cached_iovas(cpu, iovad);
+		free_global_cached_iovas(iovad);

Have you seen an issue where this is needed?

If we have filled the IOVA space, then as a measure we flush all the CPU rcaches, and then there should be free IOVA space and we can make progress. And it may be useful to still have the global depots to use straightaway then to swap into empty CPU rcaches.

include/linux/iova.h

Quoted 35 lines
drivers/iommu/iova.c +22 -0
  		goto retry;
  	}
 
@@ -1055,5 +1056,27 @@ void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad)
  	}
  }
 
+/*
+ * free all the IOVA ranges of global cache
+ */
+void free_global_cached_iovas(struct iova_domain *iovad)
+{
+	struct iova_rcache *rcache;
+	unsigned long flags;
+	int i, j;
+
+	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
+		rcache = &iovad->rcaches[i];
+		spin_lock_irqsave(&rcache->lock, flags);
+		for (j = 0; j < rcache->depot_size; ++j) {
+			iova_magazine_free_pfns(rcache->depot[j], iovad);
+			iova_magazine_free(rcache->depot[j]);
+			rcache->depot[j] = NULL;
+		}
+		rcache->depot_size = 0;
+		spin_unlock_irqrestore(&rcache->lock, flags);
+	}
+}
+
  MODULE_AUTHOR("Anil S Keshavamurthy <[email protected]>");
  MODULE_LICENSE("GPL");
include/linux/iova.h +0 -0
index a0637ab..a905726 100644

why is this in the iova.h, when it is only used internally in iova.c?

Quoted 20 lines
include/linux/iova.h +6 -0
@@ -163,6 +163,7 @@ int init_iova_flush_queue(struct iova_domain *iovad,
  struct iova *split_and_remove_iova(struct iova_domain *iovad,
  	struct iova *iova, unsigned long pfn_lo, unsigned long pfn_hi);
  void free_cpu_cached_iovas(unsigned int cpu, struct iova_domain *iovad);
+void free_global_cached_iovas(struct iova_domain *iovad);
  #else
  static inline int iova_cache_get(void)
  {
@@ -270,6 +271,11 @@ static inline void free_cpu_cached_iovas(unsigned int cpu,
  					 struct iova_domain *iovad)
  {
  }
+
+static inline void free_global_cached_iovas(struct iova_domain *iovad)
+{
+}
+
  #endif
 
  #endif
#6 lore raw
In reply to [email protected]
Quoted 70 lines · On 7/3/2020 7:47 PM, [email protected] wrote:

From: Vijayanand Jitta <[email protected]>

When ever a new iova alloc request comes iova is always searched from the cached node and the nodes which are previous to cached node. So, even if there is free iova space available in the nodes which are next to the cached node iova allocation can still fail because of this approach.

Consider the following sequence of iova alloc and frees on 1GB of iova space

1) alloc - 500MB
2) alloc - 12MB
3) alloc - 499MB
4) free - 12MB which was allocated in step 2
5) alloc - 13MB

After the above sequence we will have 12MB of free iova space and cached node will be pointing to the iova pfn of last alloc of 13MB which will be the lowest iova pfn of that iova space. Now if we get an alloc request of 2MB we just search from cached node and then look for lower iova pfn's for free iova and as they aren't any, iova alloc fails though there is 12MB of free iova space.

To avoid such iova search failures do a retry from the last rb tree node when iova search fails, this will search the entire tree and get an iova if its available.

---
 drivers/iommu/iova.c | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)
drivers/iommu/iova.c +10 -6
index 49fc01f..4e77116 100644
@@ -184,8 +184,9 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 	struct rb_node *curr, *prev;
 	struct iova *curr_iova;
 	unsigned long flags;
-	unsigned long new_pfn;
+	unsigned long new_pfn, low_pfn_new;
 	unsigned long align_mask = ~0UL;
+	unsigned long high_pfn = limit_pfn, low_pfn = iovad->start_pfn;
 
 	if (size_aligned)
 		align_mask <<= fls_long(size - 1);
@@ -198,15 +199,25 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad,
 
 	curr = __get_cached_rbnode(iovad, limit_pfn);
 	curr_iova = rb_entry(curr, struct iova, node);
+	low_pfn_new = curr_iova->pfn_hi + 1;
+
+retry:
 	do {
-		limit_pfn = min(limit_pfn, curr_iova->pfn_lo);
-		new_pfn = (limit_pfn - size) & align_mask;
+		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);
-
-	if (limit_pfn < size || new_pfn < iovad->start_pfn) {
+	} while (curr && new_pfn <= curr_iova->pfn_hi && new_pfn >= low_pfn);
+
+	if (high_pfn < size || new_pfn < low_pfn) {

drivers/iommu/iova.c static int __alloc_and_insert_iova_range(struct iova_domain *iovad, · line 223

Quoted 10 lines
drivers/iommu/iova.c +7 -0
+		if (low_pfn == iovad->start_pfn && low_pfn_new < limit_pfn) {
+			high_pfn = limit_pfn;
+			low_pfn = low_pfn_new;
+			curr = &iovad->anchor.node;
+			curr_iova = rb_entry(curr, struct iova, node);
+			goto retry;
+		}
 		iovad->max32_alloc_size = size;
 		goto iova32_full;
 	}

ping?

Signature · 2 lines
QUALCOMM INDIA, on behalf of Qualcomm Innovation Center, Inc. is a
member of Code Aurora Forum, hosted by The Linux Foundation