Index: sys/sys/tree.h =================================================================== --- sys/sys/tree.h +++ sys/sys/tree.h @@ -335,8 +335,12 @@ RB_COLOR(red, field) = RB_RED; \ } while (/*CONSTCOND*/ 0) +/* + * Something to be invoked in a loop at the root of every modified subtree, + * from the bottom up to the root, to update augmented node data. + */ #ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) +#define RB_AUGMENT(x) break #endif #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ @@ -344,7 +348,6 @@ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ } \ - RB_AUGMENT(elm); \ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ @@ -354,9 +357,7 @@ (head)->rbh_root = (tmp); \ RB_LEFT(tmp, field) = (elm); \ RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ + RB_AUGMENT(elm); \ } while (/*CONSTCOND*/ 0) #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ @@ -364,7 +365,6 @@ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ } \ - RB_AUGMENT(elm); \ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ @@ -374,9 +374,7 @@ (head)->rbh_root = (tmp); \ RB_RIGHT(tmp, field) = (elm); \ RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ + RB_AUGMENT(elm); \ } while (/*CONSTCOND*/ 0) /* Generates prototypes and inline functions */ @@ -571,62 +569,49 @@ else if (RB_RIGHT(elm, field) == NULL) \ child = RB_LEFT(elm, field); \ else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field)) != NULL) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ + elm = RB_RIGHT(old, field); \ + if ((child = RB_LEFT(elm, field)) == NULL) { \ + child = RB_RIGHT(elm, field); \ + RB_RIGHT(old, field) = child; \ + RB_PARENT(elm, field) = elm; \ + } else { \ + do \ + elm = child; \ + while ((child = RB_LEFT(elm, field)) != NULL); \ + child = RB_RIGHT(elm, field); \ + RB_PARENT(RB_RIGHT(old, field), field) = elm; \ + } \ + RB_PARENT(RB_LEFT(old, field), field) = elm; \ + parent = RB_PARENT(old, field); \ + if (parent != NULL) { \ + if (RB_LEFT(parent, field) == old) \ + RB_LEFT(parent, field) = elm; \ else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ + RB_RIGHT(parent, field) = elm; \ } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field)) != NULL); \ - } \ - goto color; \ } \ parent = RB_PARENT(elm, field); \ color = RB_COLOR(elm, field); \ - if (child) \ + if (child != NULL) \ RB_PARENT(child, field) = parent; \ - if (parent) { \ + if (parent != NULL) { \ if (RB_LEFT(parent, field) == elm) \ RB_LEFT(parent, field) = child; \ else \ RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ } else \ RB_ROOT(head) = child; \ -color: \ + if (elm != old) \ + (elm)->field = (old)->field; \ if (color == RB_BLACK) \ name##_RB_REMOVE_COLOR(head, parent, child); \ + while (parent != NULL) { \ + RB_AUGMENT(parent); \ + parent = RB_PARENT(parent, field); \ + } \ return (old); \ -} \ +} #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ /* Inserts a node into the RB tree */ \ @@ -653,10 +638,13 @@ RB_LEFT(parent, field) = elm; \ else \ RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ } else \ RB_ROOT(head) = elm; \ name##_RB_INSERT_COLOR(head, elm); \ + while (elm != NULL) { \ + RB_AUGMENT(elm); \ + elm = RB_PARENT(elm, field); \ + } \ return (NULL); \ } Index: sys/x86/iommu/intel_dmar.h =================================================================== --- sys/x86/iommu/intel_dmar.h +++ sys/x86/iommu/intel_dmar.h @@ -47,7 +47,8 @@ struct dmar_map_entry { dmar_gaddr_t start; dmar_gaddr_t end; - dmar_gaddr_t free_after; /* Free space after the entry */ + dmar_gaddr_t first; /* Least start in subtree */ + dmar_gaddr_t last; /* Greatest end in subtree */ dmar_gaddr_t free_down; /* Max free space below the current R/B tree node */ u_int flags; Index: sys/x86/iommu/intel_drv.c =================================================================== --- sys/x86/iommu/intel_drv.c +++ sys/x86/iommu/intel_drv.c @@ -1112,9 +1112,9 @@ struct dmar_map_entry *l, *r; db_printf( - " start %jx end %jx free_after %jx free_down %jx flags %x ", - entry->start, entry->end, entry->free_after, entry->free_down, - entry->flags); + " start %jx end %jx first %jx last %jx free_down %jx flags %x ", + entry->start, entry->end, entry->first, entry->last, + entry->free_down, entry->flags); db_printf("left "); l = RB_LEFT(entry, rb_entry); if (l == NULL) Index: sys/x86/iommu/intel_gas.c =================================================================== --- sys/x86/iommu/intel_gas.c +++ sys/x86/iommu/intel_gas.c @@ -139,71 +139,52 @@ static void dmar_gas_augment_entry(struct dmar_map_entry *entry) { - struct dmar_map_entry *l, *r; + struct dmar_map_entry *child; + dmar_gaddr_t free_down; - for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) { - l = RB_LEFT(entry, rb_entry); - r = RB_RIGHT(entry, rb_entry); - if (l == NULL && r == NULL) { - entry->free_down = entry->free_after; - } else if (l == NULL && r != NULL) { - entry->free_down = MAX(entry->free_after, r->free_down); - } else if (/*l != NULL && */ r == NULL) { - entry->free_down = MAX(entry->free_after, l->free_down); - } else /* if (l != NULL && r != NULL) */ { - entry->free_down = MAX(entry->free_after, l->free_down); - entry->free_down = MAX(entry->free_down, r->free_down); - } - } + free_down = 0; + if ((child = RB_LEFT(entry, rb_entry)) != NULL) { + free_down = MAX(free_down, child->free_down); + free_down = MAX(free_down, entry->start - child->last); + entry->first = child->first; + } else + entry->first = entry->start; + + if ((child = RB_RIGHT(entry, rb_entry)) != NULL) { + free_down = MAX(free_down, child->free_down); + free_down = MAX(free_down, child->first - entry->end); + entry->last = child->last; + } else + entry->last = entry->end; + entry->free_down = free_down; } RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry, dmar_gas_cmp_entries); -static void -dmar_gas_fix_free(struct dmar_domain *domain, struct dmar_map_entry *entry) -{ - struct dmar_map_entry *next; - - next = RB_NEXT(dmar_gas_entries_tree, &domain->rb_root, entry); - entry->free_after = (next != NULL ? next->start : domain->end) - - entry->end; - dmar_gas_augment_entry(entry); -} - #ifdef INVARIANTS static void dmar_gas_check_free(struct dmar_domain *domain) { - struct dmar_map_entry *entry, *next, *l, *r; + struct dmar_map_entry *entry, *l, *r; dmar_gaddr_t v; RB_FOREACH(entry, dmar_gas_entries_tree, &domain->rb_root) { KASSERT(domain == entry->domain, ("mismatched free domain %p entry %p entry->domain %p", domain, entry, entry->domain)); - next = RB_NEXT(dmar_gas_entries_tree, &domain->rb_root, entry); - if (next == NULL) { - MPASS(entry->free_after == domain->end - entry->end); - } else { - MPASS(entry->free_after = next->start - entry->end); - MPASS(entry->end <= next->start); - } l = RB_LEFT(entry, rb_entry); r = RB_RIGHT(entry, rb_entry); - if (l == NULL && r == NULL) { - MPASS(entry->free_down == entry->free_after); - } else if (l == NULL && r != NULL) { - MPASS(entry->free_down = MAX(entry->free_after, - r->free_down)); - } else if (r == NULL) { - MPASS(entry->free_down = MAX(entry->free_after, - l->free_down)); - } else { - v = MAX(entry->free_after, l->free_down); + v = 0; + if (l != NULL) { + v = MAX(v, l->free_down); + v = MAX(v, entry->start - l->last); + } + if (r != NULL) { v = MAX(v, r->free_down); - MPASS(entry->free_down == v); + v = MAX(v, r->first - entry->end); } + MPASS(entry->free_down == v); } } #endif @@ -211,25 +192,17 @@ static bool dmar_gas_rb_insert(struct dmar_domain *domain, struct dmar_map_entry *entry) { - struct dmar_map_entry *prev, *found; + struct dmar_map_entry *found; found = RB_INSERT(dmar_gas_entries_tree, &domain->rb_root, entry); - dmar_gas_fix_free(domain, entry); - prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry); - if (prev != NULL) - dmar_gas_fix_free(domain, prev); return (found == NULL); } static void dmar_gas_rb_remove(struct dmar_domain *domain, struct dmar_map_entry *entry) { - struct dmar_map_entry *prev; - prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry); RB_REMOVE(dmar_gas_entries_tree, &domain->rb_root, entry); - if (prev != NULL) - dmar_gas_fix_free(domain, prev); } void @@ -246,13 +219,11 @@ begin->start = 0; begin->end = DMAR_PAGE_SIZE; - begin->free_after = domain->end - begin->end; begin->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; dmar_gas_rb_insert(domain, begin); end->start = domain->end; end->end = domain->end; - end->free_after = 0; end->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; dmar_gas_rb_insert(domain, end); @@ -281,7 +252,6 @@ entry = RB_MAX(dmar_gas_entries_tree, &domain->rb_root); KASSERT(entry->start == domain->end, ("end entry start %p", domain)); KASSERT(entry->end == domain->end, ("end entry end %p", domain)); - KASSERT(entry->free_after == 0, ("end entry free_after %p", domain)); KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, ("end entry flags %p", domain)); RB_REMOVE(dmar_gas_entries_tree, &domain->rb_root, entry); @@ -306,18 +276,17 @@ }; static bool -dmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev, - dmar_gaddr_t end) +dmar_gas_match_one(struct dmar_gas_match_args *a, dmar_gaddr_t beg, + dmar_gaddr_t end, dmar_gaddr_t maxaddr) { dmar_gaddr_t bs, start; - if (a->entry->start + a->size > end) + if (a->entry->start + a->size > maxaddr) return (false); /* DMAR_PAGE_SIZE to create gap after new entry. */ - if (a->entry->start < prev->end + DMAR_PAGE_SIZE || - a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE > - prev->end + prev->free_after) + if (a->entry->start < beg + DMAR_PAGE_SIZE || + a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE > end) return (false); /* No boundary crossing. */ @@ -328,15 +297,14 @@ /* * The start + offset to start + offset + size region crosses * the boundary. Check if there is enough space after the - * next boundary after the prev->end. + * next boundary after the beg. */ bs = rounddown2(a->entry->start + a->offset + a->common->boundary, a->common->boundary); start = roundup2(bs, a->common->alignment); /* DMAR_PAGE_SIZE to create gap after new entry. */ - if (start + a->offset + a->size + DMAR_PAGE_SIZE <= - prev->end + prev->free_after && - start + a->offset + a->size <= end && + if (start + a->offset + a->size + DMAR_PAGE_SIZE <= end && + start + a->offset + a->size <= maxaddr && dmar_test_boundary(start + a->offset, a->size, a->common->boundary)) { a->entry->start = start; @@ -346,7 +314,7 @@ /* * Not enough space to align at the requested boundary, or * boundary is smaller than the size, but allowed to split. - * We already checked that start + size does not overlap end. + * We already checked that start + size does not overlap maxaddr. * * XXXKIB. It is possible that bs is exactly at the start of * the next entry, then we do not have gap. Ignore for now. @@ -381,15 +349,11 @@ next->start - a->entry->start >= a->size && prev->end <= a->entry->end, ("dmar_gas_match_insert hole failed %p prev (%jx, %jx) " - "free_after %jx next (%jx, %jx) entry (%jx, %jx)", a->domain, + "next (%jx, %jx) entry (%jx, %jx)", a->domain, (uintmax_t)prev->start, (uintmax_t)prev->end, - (uintmax_t)prev->free_after, (uintmax_t)next->start, (uintmax_t)next->end, (uintmax_t)a->entry->start, (uintmax_t)a->entry->end)); - prev->free_after = a->entry->start - prev->end; - a->entry->free_after = next->start - a->entry->end; - found = dmar_gas_rb_insert(a->domain, a->entry); KASSERT(found, ("found dup %p start %jx size %jx", a->domain, (uintmax_t)a->entry->start, (uintmax_t)a->size)); @@ -406,72 +370,75 @@ } static int -dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev) +dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *entry) { - struct dmar_map_entry *l; - int ret; + struct dmar_map_entry *child; - if (prev->end < a->common->lowaddr) { - a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE, + if (entry->free_down < a->size + a->offset + DMAR_PAGE_SIZE) + return (ENOMEM); + if (entry->first >= a->common->lowaddr) + return (ENOMEM); + child = RB_RIGHT(entry, rb_entry); + if (child != NULL && 0 == dmar_gas_lowermatch(a, child)) + return (0); + if (child != NULL && entry->end < a->common->lowaddr) { + a->entry->start = roundup2(entry->end + DMAR_PAGE_SIZE, a->common->alignment); - if (dmar_gas_match_one(a, prev, a->common->lowaddr)) { - dmar_gas_match_insert(a, prev); + if (dmar_gas_match_one(a, entry->end, + child->first, a->common->lowaddr)) { + dmar_gas_match_insert(a, entry); return (0); } } - if (prev->free_down < a->size + a->offset + DMAR_PAGE_SIZE) - return (ENOMEM); - l = RB_LEFT(prev, rb_entry); - if (l != NULL) { - ret = dmar_gas_lowermatch(a, l); - if (ret == 0) + child = RB_LEFT(entry, rb_entry); + if (child != NULL && child->last < a->common->lowaddr) { + a->entry->start = roundup2(child->last + DMAR_PAGE_SIZE, + a->common->alignment); + if (dmar_gas_match_one(a, child->last, + entry->start, a->common->lowaddr)) { + dmar_gas_match_insert(a, entry); return (0); + } } - l = RB_RIGHT(prev, rb_entry); - if (l != NULL) - return (dmar_gas_lowermatch(a, l)); + if (child != NULL && 0 == dmar_gas_lowermatch(a, child)) + return (0); return (ENOMEM); } static int -dmar_gas_uppermatch(struct dmar_gas_match_args *a) +dmar_gas_uppermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *entry) { - struct dmar_map_entry *next, *prev, find_entry; + struct dmar_map_entry *child; - find_entry.start = a->common->highaddr; - next = RB_NFIND(dmar_gas_entries_tree, &a->domain->rb_root, - &find_entry); - if (next == NULL) + if (entry->free_down < a->size + a->offset + DMAR_PAGE_SIZE) return (ENOMEM); - prev = RB_PREV(dmar_gas_entries_tree, &a->domain->rb_root, next); - KASSERT(prev != NULL, ("no prev %p %jx", a->domain, - (uintmax_t)find_entry.start)); - for (;;) { - a->entry->start = prev->start + DMAR_PAGE_SIZE; - if (a->entry->start < a->common->highaddr) - a->entry->start = a->common->highaddr; - a->entry->start = roundup2(a->entry->start, + if (entry->last < a->common->highaddr) + return (ENOMEM); + child = RB_LEFT(entry, rb_entry); + if (child != NULL && 0 == dmar_gas_uppermatch(a, child)) + return (0); + if (child != NULL && child->last >= a->common->highaddr) { + a->entry->start = roundup2(child->last + DMAR_PAGE_SIZE, a->common->alignment); - if (dmar_gas_match_one(a, prev, a->domain->end)) { - dmar_gas_match_insert(a, prev); + if (dmar_gas_match_one(a, child->last, + entry->start, a->common->highaddr)) { + dmar_gas_match_insert(a, entry); return (0); } - - /* - * XXXKIB. This falls back to linear iteration over - * the free space in the high region. But high - * regions are almost unused, the code should be - * enough to cover the case, although in the - * non-optimal way. - */ - prev = next; - next = RB_NEXT(dmar_gas_entries_tree, &a->domain->rb_root, - prev); - KASSERT(next != NULL, ("no next %p %jx", a->domain, - (uintmax_t)find_entry.start)); - if (next->end >= a->domain->end) - return (ENOMEM); } + child = RB_RIGHT(entry, rb_entry); + if (child != NULL && entry->end >= a->common->highaddr) { + a->entry->start = roundup2(entry->end + DMAR_PAGE_SIZE, + a->common->alignment); + if (dmar_gas_match_one(a, entry->end, + child->first, a->common->lowaddr)) { + dmar_gas_match_insert(a, entry); + return (0); + } + } + if (child != NULL && 0 == dmar_gas_uppermatch(a, child)) + return (0); + return (ENOMEM); } static int @@ -504,7 +471,7 @@ /* Handle upper region. */ if (common->highaddr >= domain->end) return (ENOMEM); - error = dmar_gas_uppermatch(&a); + error = dmar_gas_uppermatch(&a, RB_ROOT(&domain->rb_root)); KASSERT(error == ENOMEM, ("error %d from dmar_gas_uppermatch", error)); return (error);