[PATCH v2] iommu: revisit iommu_insert_resv_region() implementation

[PATCH v2] iommu: revisit iommu_insert_resv_region() implementation

[Eric Auger]

Current implementation is recursive and in case of allocation
failure the existing @regions list is altered. A non recursive
version looks better for maintainability and simplifies the
error handling. We use a separate stack for overlapping segment
merging. The elements are sorted by start address and then by
type, if their start address match.

Note this new implementation may change the region order of
appearance in /sys/kernel/iommu_groups/<n>/reserved_regions
files but this order has never been documented, see
commit bc7d12b91bd3 ("iommu: Implement reserved_regions
iommu-group sysfs file").

Signed-off-by: Eric Auger <eric.auger@redhat.com>

---

v1 -> v2:
- adapt the algo so that we don't need to move elements of
  other types to different list and sort by address and then by
  type
---
 drivers/iommu/iommu.c | 107 +++++++++++++++++++++++-------------------
 1 file changed, 59 insertions(+), 48 deletions(-)

diff --git a/drivers/iommu/iommu.c b/drivers/iommu/iommu.c
index 0c674d80c37f..4257b179fa54 100644
--- a/drivers/iommu/iommu.c
+++ b/drivers/iommu/iommu.c
@@ -229,60 +229,71 @@ static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf)
  * @new: new region to insert
  * @regions: list of regions
  *
- * The new element is sorted by address with respect to the other
- * regions of the same type. In case it overlaps with another
- * region of the same type, regions are merged. In case it
- * overlaps with another region of different type, regions are
- * not merged.
+ * Elements are sorted by start address and overlapping segments
+ * of the same type are merged.
  */
-static int iommu_insert_resv_region(struct iommu_resv_region *new,
-				    struct list_head *regions)
+int iommu_insert_resv_region(struct iommu_resv_region *new,
+			     struct list_head *regions)
 {
-	struct iommu_resv_region *region;
-	phys_addr_t start = new->start;
-	phys_addr_t end = new->start + new->length - 1;
-	struct list_head *pos = regions->next;
+	struct iommu_resv_region *iter, *tmp, *nr, *top;
+	struct list_head stack;
+	bool added = false;
 
-	while (pos != regions) {
-		struct iommu_resv_region *entry =
-			list_entry(pos, struct iommu_resv_region, list);
-		phys_addr_t a = entry->start;
-		phys_addr_t b = entry->start + entry->length - 1;
-		int type = entry->type;
+	INIT_LIST_HEAD(&stack);
 
-		if (end < a) {
-			goto insert;
-		} else if (start > b) {
-			pos = pos->next;
-		} else if ((start >= a) && (end <= b)) {
-			if (new->type == type)
-				return 0;
-			else
-				pos = pos->next;
-		} else {
-			if (new->type == type) {
-				phys_addr_t new_start = min(a, start);
-				phys_addr_t new_end = max(b, end);
-				int ret;
-
-				list_del(&entry->list);
-				entry->start = new_start;
-				entry->length = new_end - new_start + 1;
-				ret = iommu_insert_resv_region(entry, regions);
-				kfree(entry);
-				return ret;
-			} else {
-				pos = pos->next;
-			}
-		}
-	}
-insert:
-	region = iommu_alloc_resv_region(new->start, new->length,
-					 new->prot, new->type);
-	if (!region)
+	nr = iommu_alloc_resv_region(new->start, new->length,
+				     new->prot, new->type);
+	if (!nr)
 		return -ENOMEM;
 
-	list_add_tail(&region->list, pos);
+	/* First add the new elt based on start address sorting */
+	list_for_each_entry(iter, regions, list) {
+		if (nr->start < iter->start) {
+			list_add_tail(&nr->list, &iter->list);
+			added = true;
+			break;
+		} else if (nr->start == iter->start && nr->type <= iter->type) {
+			list_add_tail(&nr->list, &iter->list);
+			added = true;
+			break;
+		}
+	}
+	if (!added)
+		list_add_tail(&nr->list, regions);
+
+	/* Merge overlapping segments of type nr->type, if any */
+	list_for_each_entry_safe(iter, tmp, regions, list) {
+		phys_addr_t top_end, iter_end = iter->start + iter->length - 1;
+		bool found = false;
+
+		/* no merge needed on elements of different types than @nr */
+		if (iter->type != nr->type) {
+			list_move_tail(&iter->list, &stack);
+			continue;
+		}
+
+		/* look for the last stack element of same type as @iter */
+		list_for_each_entry_reverse(top, &stack, list)
+			if (top->type == iter->type) {
+				found = true;
+				break;
+			}
+		if (!found) {
+			list_move_tail(&iter->list, &stack);
+			continue;
+		}
+
+		top_end = top->start + top->length - 1;
+
+		if (iter->start > top_end + 1) {
+			list_move_tail(&iter->list, &stack);
+		} else {
+			top->length = max(top_end, iter_end) - top->start + 1;
+			list_del(&iter->list);
+			kfree(iter);
+		}
+	}
+	list_splice(&stack, regions);
 	return 0;
 }
 
-- 
2.20.1

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

RE: [PATCH v2] iommu: revisit iommu_insert_resv_region() implementation

[Shameerali Kolothum Thodi]

Hi Eric,

> -----Original Message-----
> From: Eric Auger [mailto:eric.auger@redhat.com]
> Sent: 01 August 2019 17:00
> To: eric.auger.pro@gmail.com; eric.auger@redhat.com; joro@8bytes.org;
> iommu@lists.linux-foundation.org; linux-kernel@vger.kernel.org;
> dwmw2@infradead.org; Shameerali Kolothum Thodi
> <shameerali.kolothum.thodi@huawei.com>; alex.williamson@redhat.com;
> robin.murphy@arm.com; hch@infradead.org
> Subject: [PATCH v2] iommu: revisit iommu_insert_resv_region()
> implementation
> 
> Current implementation is recursive and in case of allocation
> failure the existing @regions list is altered. A non recursive
> version looks better for maintainability and simplifies the
> error handling. We use a separate stack for overlapping segment
> merging. The elements are sorted by start address and then by
> type, if their start address match.
> 
> Note this new implementation may change the region order of
> appearance in /sys/kernel/iommu_groups/<n>/reserved_regions
> files but this order has never been documented, see
> commit bc7d12b91bd3 ("iommu: Implement reserved_regions
> iommu-group sysfs file").

I rerun this on D05 and seems to retain the order for msi type as before.

estuary:/$ cat /sys/kernel/iommu_groups/3/reserved_regions
0x0000000008000000 0x00000000080fffff msi
0x00000000c6010000 0x00000000c601ffff msi

FWIW,

Tested-by: Shameer Kolothum <shameerali.kolothum.thodi@huawei.com>

Cheers,
Shameer

 
> Signed-off-by: Eric Auger <eric.auger@redhat.com>
> 
> ---
> 
> v1 -> v2:
> - adapt the algo so that we don't need to move elements of
>   other types to different list and sort by address and then by
>   type
> ---
>  drivers/iommu/iommu.c | 107 +++++++++++++++++++++++-------------------
>  1 file changed, 59 insertions(+), 48 deletions(-)
> 
> diff --git a/drivers/iommu/iommu.c b/drivers/iommu/iommu.c
> index 0c674d80c37f..4257b179fa54 100644
> --- a/drivers/iommu/iommu.c
> +++ b/drivers/iommu/iommu.c
> @@ -229,60 +229,71 @@ static ssize_t iommu_group_show_name(struct
> iommu_group *group, char *buf)
>   * @new: new region to insert
>   * @regions: list of regions
>   *
> - * The new element is sorted by address with respect to the other
> - * regions of the same type. In case it overlaps with another
> - * region of the same type, regions are merged. In case it
> - * overlaps with another region of different type, regions are
> - * not merged.
> + * Elements are sorted by start address and overlapping segments
> + * of the same type are merged.
>   */
> -static int iommu_insert_resv_region(struct iommu_resv_region *new,
> -				    struct list_head *regions)
> +int iommu_insert_resv_region(struct iommu_resv_region *new,
> +			     struct list_head *regions)
>  {
> -	struct iommu_resv_region *region;
> -	phys_addr_t start = new->start;
> -	phys_addr_t end = new->start + new->length - 1;
> -	struct list_head *pos = regions->next;
> +	struct iommu_resv_region *iter, *tmp, *nr, *top;
> +	struct list_head stack;
> +	bool added = false;
> 
> -	while (pos != regions) {
> -		struct iommu_resv_region *entry =
> -			list_entry(pos, struct iommu_resv_region, list);
> -		phys_addr_t a = entry->start;
> -		phys_addr_t b = entry->start + entry->length - 1;
> -		int type = entry->type;
> +	INIT_LIST_HEAD(&stack);
> 
> -		if (end < a) {
> -			goto insert;
> -		} else if (start > b) {
> -			pos = pos->next;
> -		} else if ((start >= a) && (end <= b)) {
> -			if (new->type == type)
> -				return 0;
> -			else
> -				pos = pos->next;
> -		} else {
> -			if (new->type == type) {
> -				phys_addr_t new_start = min(a, start);
> -				phys_addr_t new_end = max(b, end);
> -				int ret;
> -
> -				list_del(&entry->list);
> -				entry->start = new_start;
> -				entry->length = new_end - new_start + 1;
> -				ret = iommu_insert_resv_region(entry, regions);
> -				kfree(entry);
> -				return ret;
> -			} else {
> -				pos = pos->next;
> -			}
> -		}
> -	}
> -insert:
> -	region = iommu_alloc_resv_region(new->start, new->length,
> -					 new->prot, new->type);
> -	if (!region)
> +	nr = iommu_alloc_resv_region(new->start, new->length,
> +				     new->prot, new->type);
> +	if (!nr)
>  		return -ENOMEM;
> 
> -	list_add_tail(&region->list, pos);
> +	/* First add the new elt based on start address sorting */
> +	list_for_each_entry(iter, regions, list) {
> +		if (nr->start < iter->start) {
> +			list_add_tail(&nr->list, &iter->list);
> +			added = true;
> +			break;
> +		} else if (nr->start == iter->start && nr->type <= iter->type) {
> +			list_add_tail(&nr->list, &iter->list);
> +			added = true;
> +			break;
> +		}
> +	}
> +	if (!added)
> +		list_add_tail(&nr->list, regions);
> +
> +	/* Merge overlapping segments of type nr->type, if any */
> +	list_for_each_entry_safe(iter, tmp, regions, list) {
> +		phys_addr_t top_end, iter_end = iter->start + iter->length - 1;
> +		bool found = false;
> +
> +		/* no merge needed on elements of different types than @nr */
> +		if (iter->type != nr->type) {
> +			list_move_tail(&iter->list, &stack);
> +			continue;
> +		}
> +
> +		/* look for the last stack element of same type as @iter */
> +		list_for_each_entry_reverse(top, &stack, list)
> +			if (top->type == iter->type) {
> +				found = true;
> +				break;
> +			}
> +		if (!found) {
> +			list_move_tail(&iter->list, &stack);
> +			continue;
> +		}
> +
> +		top_end = top->start + top->length - 1;
> +
> +		if (iter->start > top_end + 1) {
> +			list_move_tail(&iter->list, &stack);
> +		} else {
> +			top->length = max(top_end, iter_end) - top->start + 1;
> +			list_del(&iter->list);
> +			kfree(iter);
> +		}
> +	}
> +	list_splice(&stack, regions);
>  	return 0;
>  }
> 
> --
> 2.20.1

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [PATCH v2] iommu: revisit iommu_insert_resv_region() implementation

[Christoph Hellwig]

A couple nitpicks below:

On Thu, Aug 01, 2019 at 05:59:46PM +0200, Eric Auger wrote:
> - * The new element is sorted by address with respect to the other
> - * regions of the same type. In case it overlaps with another
> - * region of the same type, regions are merged. In case it
> - * overlaps with another region of different type, regions are
> - * not merged.
> + * Elements are sorted by start address and overlapping segments
> + * of the same type are merged.
>   */
> +int iommu_insert_resv_region(struct iommu_resv_region *new,
> +			     struct list_head *regions)
>  {
> +	struct iommu_resv_region *iter, *tmp, *nr, *top;
> +	struct list_head stack;
> +	bool added = false;
>  
> +	INIT_LIST_HEAD(&stack);

Nit: you could just use

	LIST_HEAD(&stack);

to declare and initialize the variable in a single line.

> +	nr = iommu_alloc_resv_region(new->start, new->length,
> +				     new->prot, new->type);
> +	if (!nr)
>  		return -ENOMEM;
>  
> +	/* First add the new elt based on start address sorting */

/elt/element/ ?

> +	list_for_each_entry(iter, regions, list) {
> +		if (nr->start < iter->start) {
> +			list_add_tail(&nr->list, &iter->list);
> +			added = true;
> +			break;
> +		} else if (nr->start == iter->start && nr->type <= iter->type) {
> +			list_add_tail(&nr->list, &iter->list);
> +			added = true;
> +			break;
> +		}

Nit:  no need for an else after a a break.  But then again  both
branches look identical, so why don't you just merge them:

		if (nr->start < iter->start ||
		    (nr->start == iter->start && nr->type <= iter->type)) {
			list_add_tail(&nr->list, &iter->list);
			added = true;
			break;

	}

> +	if (!added)
> +		list_add_tail(&nr->list, regions);

Probably down to preference, but I'd just use a goto to jump past the
list_add and save the added variable.

> +	/* Merge overlapping segments of type nr->type, if any */
> +	list_for_each_entry_safe(iter, tmp, regions, list) {
> +		phys_addr_t top_end, iter_end = iter->start + iter->length - 1;
> +		bool found = false;
> +
> +		/* no merge needed on elements of different types than @nr */
> +		if (iter->type != nr->type) {
> +			list_move_tail(&iter->list, &stack);
> +			continue;
> +		}
> +
> +		/* look for the last stack element of same type as @iter */
> +		list_for_each_entry_reverse(top, &stack, list)
> +			if (top->type == iter->type) {
> +				found = true;
> +				break;
> +			}
> +		if (!found) {

Same here.

> +			list_move_tail(&iter->list, &stack);
> +			continue;
> +		}
> +
> +		top_end = top->start + top->length - 1;
> +
> +		if (iter->start > top_end + 1) {
> +			list_move_tail(&iter->list, &stack);
> +		} else {
> +			top->length = max(top_end, iter_end) - top->start + 1;
> +			list_del(&iter->list);
> +			kfree(iter);
> +		}

I wonder if the body of the outer list_for_each_entry_safe loop would
be a bit nicer in a helper, but again that is probably just down to
personal preference.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [PATCH v2] iommu: revisit iommu_insert_resv_region() implementation

[Auger Eric]

Hi Christoph,

On 8/6/19 9:32 AM, Christoph Hellwig wrote:
> A couple nitpicks below:
> 
> On Thu, Aug 01, 2019 at 05:59:46PM +0200, Eric Auger wrote:
>> - * The new element is sorted by address with respect to the other
>> - * regions of the same type. In case it overlaps with another
>> - * region of the same type, regions are merged. In case it
>> - * overlaps with another region of different type, regions are
>> - * not merged.
>> + * Elements are sorted by start address and overlapping segments
>> + * of the same type are merged.
>>   */
>> +int iommu_insert_resv_region(struct iommu_resv_region *new,
>> +			     struct list_head *regions)
>>  {
>> +	struct iommu_resv_region *iter, *tmp, *nr, *top;
>> +	struct list_head stack;
>> +	bool added = false;
>>  
>> +	INIT_LIST_HEAD(&stack);

Please forgive me for the delay. I am just back to the office.
> 
> Nit: you could just use
> 
> 	LIST_HEAD(&stack);
> 
> to declare and initialize the variable in a single line.
done
> 
>> +	nr = iommu_alloc_resv_region(new->start, new->length,
>> +				     new->prot, new->type);
>> +	if (!nr)
>>  		return -ENOMEM;
>>  
>> +	/* First add the new elt based on start address sorting */
> 
> /elt/element/ ?
yes
> 
>> +	list_for_each_entry(iter, regions, list) {
>> +		if (nr->start < iter->start) {
>> +			list_add_tail(&nr->list, &iter->list);
>> +			added = true;
>> +			break;
>> +		} else if (nr->start == iter->start && nr->type <= iter->type) {
>> +			list_add_tail(&nr->list, &iter->list);
>> +			added = true;
>> +			break;
>> +		}
> 
> Nit:  no need for an else after a a break.  But then again  both
> branches look identical, so why don't you just merge them:
> 
> 		if (nr->start < iter->start ||
> 		    (nr->start == iter->start && nr->type <= iter->type)) {
> 			list_add_tail(&nr->list, &iter->list);
> 			added = true;
> 			break;
I merged both
> 
> 	}
> 
>> +	if (!added)
>> +		list_add_tail(&nr->list, regions);
> 
> Probably down to preference, but I'd just use a goto to jump past the
> list_add and save the added variable.
done
> 
>> +	/* Merge overlapping segments of type nr->type, if any */
>> +	list_for_each_entry_safe(iter, tmp, regions, list) {
>> +		phys_addr_t top_end, iter_end = iter->start + iter->length - 1;
>> +		bool found = false;
>> +
>> +		/* no merge needed on elements of different types than @nr */
>> +		if (iter->type != nr->type) {
>> +			list_move_tail(&iter->list, &stack);
>> +			continue;
>> +		}
>> +
>> +		/* look for the last stack element of same type as @iter */
>> +		list_for_each_entry_reverse(top, &stack, list)
>> +			if (top->type == iter->type) {
>> +				found = true;
>> +				break;
>> +			}
>> +		if (!found) {
> 
> Same here.
done
> 
>> +			list_move_tail(&iter->list, &stack);
>> +			continue;
>> +		}
>> +
>> +		top_end = top->start + top->length - 1;
>> +
>> +		if (iter->start > top_end + 1) {
>> +			list_move_tail(&iter->list, &stack);
>> +		} else {
>> +			top->length = max(top_end, iter_end) - top->start + 1;
>> +			list_del(&iter->list);
>> +			kfree(iter);
>> +		}
> 
> I wonder if the body of the outer list_for_each_entry_safe loop would
> be a bit nicer in a helper, but again that is probably just down to
> personal preference.
I skipped that suggestion at the moment.

Hope that looks better in v3.

Thank you for your review!

Best Regards

Eric
> 
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu