Index: share/man/man3/tree.3 =================================================================== --- share/man/man3/tree.3 +++ share/man/man3/tree.3 @@ -97,6 +97,8 @@ .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , +.Nm RB_INSERT_NEXT , +.Nm RB_INSERT_PREV , .Nm RB_REMOVE , .Nm RB_REINSERT , .Nm RB_AUGMENT @@ -193,6 +195,10 @@ .Ft "struct TYPE *" .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" +.Fn RB_INSERT_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *next" +.Ft "struct TYPE *" +.Fn RB_INSERT_PREV NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *prev" +.Ft "struct TYPE *" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" @@ -515,6 +521,18 @@ into the tree. .Pp The +.Fn RB_INSERT_NEXT +macro inserts the new element +.Fa elm +into the tree immediately after a given element. +.Pp +The +.Fn RB_INSERT_PREV +macro inserts the new element +.Fa elm +into the tree immediately before a given element. +.Pp +The .Fn RB_REMOVE macro removes the element .Fa elm Index: sys/dev/iommu/iommu.h =================================================================== --- sys/dev/iommu/iommu.h +++ sys/dev/iommu/iommu.h @@ -109,6 +109,7 @@ struct iommu_map_entries_tailq unload_entries; /* (d) Entries to unload */ struct iommu_gas_entries_tree rb_root; /* (d) */ + struct iommu_map_entry *start_gap; /* (d) */ iommu_gaddr_t end; /* (c) Highest address + 1 in the guest AS */ struct iommu_map_entry *first_place, *last_place; /* (d) */ Index: sys/dev/iommu/iommu_gas.c =================================================================== --- sys/dev/iommu/iommu_gas.c +++ sys/dev/iommu/iommu_gas.c @@ -206,19 +206,16 @@ } #endif -static bool -iommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry) -{ - struct iommu_map_entry *found; - - found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry); - return (found == NULL); -} - static void iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry) { + /* + * The predecessor to the removed entry may become the new greatest + * lower bound on free gaps. + */ + if (entry->end <= domain->start_gap->end) + domain->start_gap = iommu_gas_entries_tree_RB_PREV(entry); RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); } @@ -255,13 +252,15 @@ end->start = domain->end; end->end = domain->end; end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; - iommu_gas_rb_insert(domain, end); + RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end); begin->start = 0; begin->end = IOMMU_PAGE_SIZE; begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; - iommu_gas_rb_insert(domain, begin); + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, end, begin); + domain->start_gap = begin; domain->first_place = begin; domain->last_place = end; domain->flags |= IOMMU_DOMAIN_GAS_INITED; @@ -283,7 +282,7 @@ KASSERT(entry->flags == (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), ("start entry flags %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root); @@ -292,15 +291,14 @@ KASSERT(entry->flags == (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), ("end entry flags %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root, entry1) { KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0, ("non-RMRR entry left %p", domain)); - RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, - entry); + iommu_gas_rb_remove(domain, entry); iommu_gas_free_entry(entry); } } @@ -326,7 +324,6 @@ { struct iommu_map_entry *entry; iommu_gaddr_t first, size, start; - bool found __diagused; int offset; /* @@ -380,9 +377,9 @@ entry->start = start; entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE); entry->flags = IOMMU_MAP_ENTRY_MAP; - found = iommu_gas_rb_insert(a->domain, entry); - KASSERT(found, ("found dup %p start %jx size %jx", - a->domain, (uintmax_t)start, (uintmax_t)size)); + /* The new entry may be a new, greater lower bound on free gaps. */ + if (start <= a->domain->start_gap->end + 3 * IOMMU_PAGE_SIZE) + a->domain->start_gap = entry; return (true); } @@ -431,32 +428,36 @@ * Find the first entry in the lower region that could abut a big-enough * range. */ - curr = RB_ROOT(&a->domain->rb_root); - first = NULL; - while (curr != NULL && curr->free_down >= min_free) { - first = curr; - curr = RB_LEFT(curr, rb_entry); - } + first = a->domain->start_gap; + while (first != NULL && first->free_down < min_free) + first = RB_PARENT(first, rb_entry); /* * Walk the big-enough ranges until one satisfies alignment * requirements, or violates lowaddr address requirement. */ + domain = a->domain; addr = a->common->lowaddr + 1; for (curr = first; curr != NULL; curr = iommu_gas_next(curr, min_free)) { if ((first = RB_LEFT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, first->last, curr->start, - 0, addr)) + 0, addr)) { + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } if (curr->end >= addr) { /* All remaining ranges >= addr */ break; } if ((first = RB_RIGHT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, curr->end, first->first, - 0, addr)) + 0, addr)) { + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } } /* @@ -481,17 +482,22 @@ * Walk the remaining big-enough ranges until one satisfies alignment * requirements. */ - domain = a->domain; for (curr = first; curr != NULL; curr = iommu_gas_next(curr, min_free)) { if ((first = RB_LEFT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, first->last, curr->start, - addr + 1, domain->end)) + addr + 1, domain->end)) { + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } if ((first = RB_RIGHT(curr, rb_entry)) != NULL && iommu_gas_match_one(a, curr->end, first->first, - addr + 1, domain->end)) + addr + 1, domain->end)) { + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, curr, a->entry); return (0); + } } return (ENOMEM); @@ -502,7 +508,6 @@ u_int flags) { struct iommu_map_entry *next, *prev; - bool found __diagused; IOMMU_DOMAIN_ASSERT_LOCKED(domain); @@ -550,14 +555,13 @@ iommu_gas_rb_remove(domain, prev); prev = NULL; } + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, next, entry); if (next->start < entry->end) { iommu_gas_rb_remove(domain, next); next = NULL; } - found = iommu_gas_rb_insert(domain, entry); - KASSERT(found, ("found RMRR dup %p start %jx end %jx", - domain, (uintmax_t)entry->start, (uintmax_t)entry->end)); if ((flags & IOMMU_MF_RMRR) != 0) entry->flags = IOMMU_MAP_ENTRY_RMRR; @@ -647,7 +651,8 @@ *res = *entry; res->start = entry->end = start; RB_UPDATE_AUGMENT(entry, rb_entry); - iommu_gas_rb_insert(domain, res); + RB_INSERT_NEXT(iommu_gas_entries_tree, + &domain->rb_root, entry, res); return (res); } @@ -662,7 +667,8 @@ *r = *entry; r->end = entry->start = end; RB_UPDATE_AUGMENT(entry, rb_entry); - iommu_gas_rb_insert(domain, r); + RB_INSERT_PREV(iommu_gas_entries_tree, + &domain->rb_root, entry, r); return (true); } Index: sys/sys/tree.h =================================================================== --- sys/sys/tree.h +++ sys/sys/tree.h @@ -414,12 +414,15 @@ RB_PROTOTYPE_RANK(name, type, attr) \ RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ + RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \ RB_PROTOTYPE_INSERT(name, type, attr); \ RB_PROTOTYPE_REMOVE(name, type, attr); \ RB_PROTOTYPE_FIND(name, type, attr); \ RB_PROTOTYPE_NFIND(name, type, attr); \ RB_PROTOTYPE_NEXT(name, type, attr); \ + RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \ RB_PROTOTYPE_PREV(name, type, attr); \ + RB_PROTOTYPE_INSERT_PREV(name, type, attr); \ RB_PROTOTYPE_MINMAX(name, type, attr); \ RB_PROTOTYPE_REINSERT(name, type, attr); #ifdef _RB_DIAGNOSTIC @@ -436,6 +439,9 @@ struct type *, struct type *) #define RB_PROTOTYPE_REMOVE(name, type, attr) \ attr struct type *name##_RB_REMOVE(struct name *, struct type *) +#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \ + attr struct type *name##_RB_INSERT_FINISH(struct name *, \ + struct type *, struct type **, struct type *) #define RB_PROTOTYPE_INSERT(name, type, attr) \ attr struct type *name##_RB_INSERT(struct name *, struct type *) #define RB_PROTOTYPE_FIND(name, type, attr) \ @@ -444,8 +450,14 @@ attr struct type *name##_RB_NFIND(struct name *, struct type *) #define RB_PROTOTYPE_NEXT(name, type, attr) \ attr struct type *name##_RB_NEXT(struct type *) +#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \ + attr struct type *name##_RB_INSERT_NEXT(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_PREV(name, type, attr) \ attr struct type *name##_RB_PREV(struct type *) +#define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \ + attr struct type *name##_RB_INSERT_PREV(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_MINMAX(name, type, attr) \ attr struct type *name##_RB_MINMAX(struct name *, int) #define RB_PROTOTYPE_REINSERT(name, type, attr) \ @@ -462,12 +474,15 @@ RB_GENERATE_RANK(name, type, field, attr) \ RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ + RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ RB_GENERATE_INSERT(name, type, field, cmp, attr) \ RB_GENERATE_REMOVE(name, type, field, attr) \ RB_GENERATE_FIND(name, type, field, cmp, attr) \ RB_GENERATE_NFIND(name, type, field, cmp, attr) \ RB_GENERATE_NEXT(name, type, field, attr) \ + RB_GENERATE_INSERT_NEXT(name, type, field, attr) \ RB_GENERATE_PREV(name, type, field, attr) \ + RB_GENERATE_INSERT_PREV(name, type, field, attr) \ RB_GENERATE_MINMAX(name, type, field, attr) \ RB_GENERATE_REINSERT(name, type, field, cmp, attr) @@ -786,6 +801,24 @@ return (out); \ } +#define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ +/* Inserts a node into the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \ + struct type **pptr, struct type *elm) \ +{ \ + struct type *tmp = NULL; \ + \ + RB_SET(elm, parent, field); \ + *pptr = elm; \ + if (parent != NULL) \ + tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ + _RB_AUGMENT_WALK(elm, tmp, field); \ + if (tmp != NULL) \ + RB_AUGMENT_CHECK(tmp); \ + return (NULL); \ +} + #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ /* Inserts a node into the RB tree */ \ attr struct type * \ @@ -805,14 +838,7 @@ else \ return (parent); \ } \ - RB_SET(elm, parent, field); \ - *tmpp = elm; \ - if (parent != NULL) \ - tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ - _RB_AUGMENT_WALK(elm, tmp, field); \ - if (tmp != NULL) \ - RB_AUGMENT_CHECK(tmp); \ - return (NULL); \ + return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \ } #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ @@ -874,6 +900,22 @@ return (elm); \ } +#define RB_GENERATE_INSERT_NEXT(name, type, field, attr) \ +/* Inserts a node into the next position in the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_NEXT(struct name *head, \ + struct type *elm, struct type *next) \ +{ \ + struct type *tmp; \ + struct type **tmpp = &RB_RIGHT(elm, field); \ + \ + while ((tmp = *tmpp) != NULL) { \ + elm = tmp; \ + tmpp = &RB_LEFT(elm, field); \ + } \ + return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \ +} + #define RB_GENERATE_PREV(name, type, field, attr) \ /* ARGSUSED */ \ attr struct type * \ @@ -892,6 +934,22 @@ return (elm); \ } +#define RB_GENERATE_INSERT_PREV(name, type, field, attr) \ +/* Inserts a node into the prev position in the RB tree */ \ +attr struct type * \ +name##_RB_INSERT_PREV(struct name *head, \ + struct type *elm, struct type *prev) \ +{ \ + struct type *tmp; \ + struct type **tmpp = &RB_LEFT(elm, field); \ + \ + while ((tmp = *tmpp) != NULL) { \ + elm = tmp; \ + tmpp = &RB_RIGHT(elm, field); \ + } \ + return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \ +} + #define RB_GENERATE_MINMAX(name, type, field, attr) \ attr struct type * \ name##_RB_MINMAX(struct name *head, int val) \ @@ -928,6 +986,8 @@ #define RB_INF 1 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) +#define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z) +#define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z) #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) #define RB_FIND(name, x, y) name##_RB_FIND(x, y) #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)