iommu: revisit iommu_insert_resv_region() implementation
PATCH v2 1/1 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").
---
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(-)
drivers/iommu/iommu.c +59 -48
@@ -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 (®ion->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 ; }
Signature · 1 line
2.20.1
Hi Eric,
Quoted 18 lines
-----Original Message-----
From: Eric Auger [mailto:[email protected]]
Sent: 01 August 2019 17:00
To: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Shameerali Kolothum Thodi <[email protected]>; [email protected]; [email protected]; [email protected]
Subject: [PATCH v2] iommu: revisitiommu_insert_resv_region()implementationCurrent 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.
Quoted 5 lines
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: Implementreserved_regionsiommu-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,
Cheers,
Shameer
Quoted 139 lines
Signed-off-by Eric Auger <[email protected]>---
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(-)drivers/iommu/iommu.c +59
-49@@ -229,60 +229,71 @@ static ssize_t iommu_group_show_name(structiommu_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 (®ion->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
A couple nitpicks below:
Quoted 8 lines · Eric Auger
- * 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.
*/
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 242
Quoted 8 lines
drivers/iommu/iommu.c +6
-0+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.
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 249
Quoted 6 lines
drivers/iommu/iommu.c +4
-0+ 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/ ?
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 259
Quoted 10 lines
drivers/iommu/iommu.c +10
-0+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;
}drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 262
Quoted 2 lines
drivers/iommu/iommu.c +2
-0+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.
Quoted 8 lines
drivers/iommu/iommu.c +8
-0+/* 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);
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 281
Quoted 10 lines
drivers/iommu/iommu.c +10
-0+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.
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 294
Quoted 13 lines
drivers/iommu/iommu.c +13
-0+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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu
Hi Christoph,
Quoted 18 lines · Christoph Hellwig
A couple nitpicks below:
Quoted 15 lines · Eric Auger
- * 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.
*/drivers/iommu/iommu.c +5
-0+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;
Quoted 1 line
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 242
Quoted 1 line
drivers/iommu/iommu.c +1
-0+INIT_LIST_HEAD (&stack);
Please forgive me for the delay. I am just back to the office.
Quoted 6 lines
Nit: you could just use
LIST_HEAD(&stack);to declare and initialize the variable in a single line.
done
Quoted 9 lines
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 249
Quoted 7 lines
drivers/iommu/iommu.c +4
-0+ 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
Quoted 15 lines
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 259
Quoted 11 lines
drivers/iommu/iommu.c +10
-0+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:
Quoted 5 lines
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
Quoted 8 lines
}drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 262
Quoted 2 lines
drivers/iommu/iommu.c +2
-0+if (!added) +list_add_tail (&nr->list, regions);Probably down to preference, but I'd just use a goto to jump past the
list_addand save the added variable.
done
Quoted 13 lines
Quoted 13 lines
drivers/iommu/iommu.c +12
-0+/* 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 */
Quoted 8 lines
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 281
Quoted 6 lines
drivers/iommu/iommu.c +6
-0+list_for_each_entry_reverse (top, &stack, list) +if (top->type == iter->type) { + found = true; +break ; + } +if (!found) {Same here.
done
Quoted 10 lines
Quoted 10 lines
drivers/iommu/iommu.c +9
-0+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 {
Quoted 8 lines
drivers/iommu/iommu.c static ssize_t iommu_group_show_name(struct iommu_group *group, char *buf) · line 294
Quoted 4 lines
drivers/iommu/iommu.c +4
-0+ 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_safeloop 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
Quoted 1 line
_______________________________________________
iommu mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/iommu