git: d0fb642b6457 - stable/13 - rb_tree: let insert search start from next node
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Mon, 24 Oct 2022 00:44:03 UTC
The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=d0fb642b64571de87ae444c960b3d21c3d0ed79d commit d0fb642b64571de87ae444c960b3d21c3d0ed79d Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-10-03 03:27:21 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-10-24 00:43:22 +0000 rb_tree: let insert search start from next node When the node to insert in the rb_tree is known to precede or follow a particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT, defined here, allow the search for where to insert the new node begin with that particular node, rather than at the root, to save a bit of time. Using those methods, instead of RB_INSERT, in managing a tree in iommu_gas.c, saves a little time. Reviewed by: kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D35516 (cherry picked from commit 368ee2f86a0f4f60338472be4bfd3c09ab401f87) --- share/man/man3/tree.3 | 18 ++++++++ sys/dev/iommu/iommu_gas.c | 60 +++++++++++++------------- sys/sys/tree.h | 104 +++++++++++++++++++++++++++++++++++++++------- 3 files changed, 136 insertions(+), 46 deletions(-) diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index eaddc9f811c4..cc4c836e8889 100644 --- a/share/man/man3/tree.3 +++ b/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 @@ macro inserts the new element 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 diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c index c04edb8451b4..8c8d0e49c378 100644 --- a/sys/dev/iommu/iommu_gas.c +++ b/sys/dev/iommu/iommu_gas.c @@ -206,15 +206,6 @@ iommu_gas_check_free(struct iommu_domain *domain) } #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) { @@ -255,12 +246,12 @@ iommu_gas_init_domain(struct iommu_domain *domain) 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->first_place = begin; domain->last_place = end; @@ -283,7 +274,7 @@ iommu_gas_fini_domain(struct iommu_domain *domain) 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 +283,14 @@ iommu_gas_fini_domain(struct iommu_domain *domain) 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 +316,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, { struct iommu_map_entry *entry; iommu_gaddr_t first, size, start; - bool found __diagused; int offset; /* @@ -380,9 +369,6 @@ iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, 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)); return (true); } @@ -431,7 +417,8 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) * Find the first entry in the lower region that could abut a big-enough * range. */ - curr = RB_ROOT(&a->domain->rb_root); + domain = a->domain; + curr = RB_ROOT(&domain->rb_root); first = NULL; while (curr != NULL && curr->free_down >= min_free) { first = curr; @@ -447,16 +434,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) 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 +474,22 @@ iommu_gas_find_space(struct iommu_gas_match_args *a) * 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 +500,6 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr u_int flags) { struct iommu_map_entry *next, *prev; - bool found __diagused; IOMMU_DOMAIN_ASSERT_LOCKED(domain); @@ -550,14 +547,13 @@ iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entr 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 +643,8 @@ iommu_gas_remove_clip_left(struct iommu_domain *domain, iommu_gaddr_t start, *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 +659,8 @@ iommu_gas_remove_clip_right(struct iommu_domain *domain, *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); } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 47cd14d6691b..7aa00bd53fd7 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -414,12 +414,15 @@ struct { \ 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 { \ 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 @@ struct { \ 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 @@ struct { \ 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, cmp, attr) \ RB_GENERATE_PREV(name, type, field, attr) \ + RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ RB_GENERATE_MINMAX(name, type, field, attr) \ RB_GENERATE_REINSERT(name, type, field, cmp, attr) @@ -556,7 +571,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ * other edge lengths based on the downward \ * edges from 'child'. \ * \ - * par par \ + * par par \ * / \ / \ \ * elm z / z \ * / \ child \ @@ -587,7 +602,7 @@ name##_RB_INSERT_COLOR(struct name *head, \ * 'parent' a child of 'child', then make both edges \ * of 'child' short to rebalance. \ * \ - * par child \ + * par child \ * / \ / \ \ * / z x par \ * child / \ \ @@ -800,6 +815,29 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ 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) \ + /* \ + * An element rotated into the search path has a \ + * changed subtree, so update augmentation for it if \ + * AUGMENT_WALK didn't. \ + */ \ + (void)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 * \ @@ -819,19 +857,7 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ 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) \ - /* \ - * An element rotated into the search path has a \ - * changed subtree, so update augmentation for it if \ - * AUGMENT_WALK didn't. \ - */ \ - (void)RB_AUGMENT_CHECK(tmp); \ - return (NULL); \ + return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \ } #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ @@ -893,6 +919,33 @@ name##_RB_NEXT(struct type *elm) \ return (elm); \ } +#if defined(_KERNEL) && defined(DIAGNOSTIC) +#define _RB_ORDER_CHECK(lo, hi) do { \ + KASSERT(cmp(lo, hi) < 0, "out of order insertion"); \ +} while (0) +#else +#define _RB_ORDER_CHECK(elm, next) do {} while (0) +#endif + +#define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, 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); \ + \ + _RB_ORDER_CHECK(elm, next); \ + if (name##_RB_NEXT(elm) != NULL) \ + _RB_ORDER_CHECK(next, name##_RB_NEXT(elm)); \ + 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 * \ @@ -911,6 +964,25 @@ name##_RB_PREV(struct type *elm) \ return (elm); \ } +#define RB_GENERATE_INSERT_PREV(name, type, field, cmp, 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); \ + \ + _RB_ORDER_CHECK(prev, elm); \ + if (name##_RB_PREV(elm) != NULL) \ + _RB_ORDER_CHECK(name##_RB_PREV(elm), prev); \ + 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) \ @@ -947,6 +1019,8 @@ name##_RB_REINSERT(struct name *head, struct type *elm) \ #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)