diff options
| -rw-r--r-- | drivers/iommu/iommu.c | 96 |
1 files changed, 47 insertions, 49 deletions
diff --git a/drivers/iommu/iommu.c b/drivers/iommu/iommu.c index 0f585b614657..b6980938882e 100644 --- a/drivers/iommu/iommu.c +++ b/drivers/iommu/iommu.c @@ -286,60 +286,58 @@ 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; - - 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; - - 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; + struct iommu_resv_region *iter, *tmp, *nr, *top; + LIST_HEAD(stack); + + nr = iommu_alloc_resv_region(new->start, new->length, + new->prot, new->type); + if (!nr) + return -ENOMEM; + + /* First add the new element based on start address sorting */ + list_for_each_entry(iter, regions, list) { + if (nr->start < iter->start || + (nr->start == iter->start && nr->type <= iter->type)) + break; + } + list_add_tail(&nr->list, &iter->list); + + /* Merge overlapping segments of type nr->type in @regions, if any */ + list_for_each_entry_safe(iter, tmp, regions, list) { + phys_addr_t top_end, iter_end = iter->start + iter->length - 1; + + /* 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) + goto check_overlap; + + list_move_tail(&iter->list, &stack); + continue; + +check_overlap: + top_end = top->start + top->length - 1; + + if (iter->start > top_end + 1) { + list_move_tail(&iter->list, &stack); } 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; - } + top->length = max(top_end, iter_end) - top->start + 1; + list_del(&iter->list); + kfree(iter); } } -insert: - region = iommu_alloc_resv_region(new->start, new->length, - new->prot, new->type); - if (!region) - return -ENOMEM; - - list_add_tail(®ion->list, pos); + list_splice(&stack, regions); return 0; } |