Page MenuHomeFreeBSD
Files F153350687

D23435.id67634.diff
No OneTemporary
Actions

D23435.id67634.diff
View Options

Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -335,12 +335,8 @@
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) break
+#define RB_AUGMENT(x) do {} while (0)
#endif
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
@@ -348,6 +344,7 @@
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); \
@@ -357,7 +354,9 @@
(head)->rbh_root = (tmp); \
RB_LEFT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -365,6 +364,7 @@
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,7 +374,9 @@
(head)->rbh_root = (tmp); \
RB_RIGHT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
} while (/*CONSTCOND*/ 0)
/* Generates prototypes and inline functions */
@@ -569,49 +571,62 @@
else if (RB_RIGHT(elm, field) == NULL) \
child = RB_LEFT(elm, field); \
else { \
- 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; \
+ 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; \
else \
- RB_RIGHT(parent, field) = elm; \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
} 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 != NULL) \
+ if (child) \
RB_PARENT(child, field) = parent; \
- if (parent != NULL) { \
+ if (parent) { \
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; \
- if (elm != old) \
- (elm)->field = (old)->field; \
+color: \
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 */ \
@@ -638,13 +653,10 @@
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,8 +47,7 @@
struct dmar_map_entry {
dmar_gaddr_t start;
dmar_gaddr_t end;
- dmar_gaddr_t first; /* Least start in subtree */
- dmar_gaddr_t last; /* Greatest end in subtree */
+ dmar_gaddr_t free_after; /* Free space after the entry */
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 first %jx last %jx free_down %jx flags %x ",
- entry->start, entry->end, entry->first, entry->last,
- entry->free_down, entry->flags);
+ " start %jx end %jx free_after %jx free_down %jx flags %x ",
+ entry->start, entry->end, entry->free_after, 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,52 +139,71 @@
static void
dmar_gas_augment_entry(struct dmar_map_entry *entry)
{
- struct dmar_map_entry *child;
- dmar_gaddr_t free_down;
+ struct dmar_map_entry *l, *r;
- 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;
+ 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);
+ }
+ }
}
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, *l, *r;
+ struct dmar_map_entry *entry, *next, *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);
- v = 0;
- if (l != NULL) {
- v = MAX(v, l->free_down);
- v = MAX(v, entry->start - l->last);
- }
- if (r != NULL) {
+ 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 = MAX(v, r->free_down);
- v = MAX(v, r->first - entry->end);
+ MPASS(entry->free_down == v);
}
- MPASS(entry->free_down == v);
}
}
#endif
@@ -192,17 +211,25 @@
static bool
dmar_gas_rb_insert(struct dmar_domain *domain, struct dmar_map_entry *entry)
{
- struct dmar_map_entry *found;
+ struct dmar_map_entry *prev, *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
@@ -219,11 +246,13 @@
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);
@@ -252,6 +281,7 @@
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);
@@ -275,26 +305,19 @@
struct dmar_map_entry *entry;
};
-/*
- * The interval [beg, end) is a free interval between two dmar_map_entries.
- * maxaddr is an upper bound on addresses that can be allocated. Try to
- * allocate space in the free interval, subject to the conditions expressed
- * by a, and return 'true' if and only if the allocation attempt succeeds.
- */
static bool
-dmar_gas_match_one(struct dmar_gas_match_args *a, dmar_gaddr_t beg,
- dmar_gaddr_t end, dmar_gaddr_t maxaddr)
+dmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev,
+ dmar_gaddr_t end)
{
dmar_gaddr_t bs, start;
- a->entry->start = roundup2(beg + DMAR_PAGE_SIZE,
- a->common->alignment);
- if (a->entry->start + a->size > maxaddr)
+ if (a->entry->start + a->size > end)
return (false);
/* DMAR_PAGE_SIZE to create gap after new entry. */
- if (a->entry->start < beg + DMAR_PAGE_SIZE ||
- a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE > end)
+ if (a->entry->start < prev->end + DMAR_PAGE_SIZE ||
+ a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE >
+ prev->end + prev->free_after)
return (false);
/* No boundary crossing. */
@@ -305,14 +328,15 @@
/*
* The start + offset to start + offset + size region crosses
* the boundary. Check if there is enough space after the
- * next boundary after the beg.
+ * next boundary after the prev->end.
*/
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 <= end &&
- start + a->offset + a->size <= maxaddr &&
+ if (start + a->offset + a->size + DMAR_PAGE_SIZE <=
+ prev->end + prev->free_after &&
+ start + a->offset + a->size <= end &&
dmar_test_boundary(start + a->offset, a->size,
a->common->boundary)) {
a->entry->start = start;
@@ -322,7 +346,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 maxaddr.
+ * We already checked that start + size does not overlap end.
*
* XXXKIB. It is possible that bs is exactly at the start of
* the next entry, then we do not have gap. Ignore for now.
@@ -336,8 +360,10 @@
}
static void
-dmar_gas_match_insert(struct dmar_gas_match_args *a)
+dmar_gas_match_insert(struct dmar_gas_match_args *a,
+ struct dmar_map_entry *prev)
{
+ struct dmar_map_entry *next;
bool found;
/*
@@ -350,67 +376,102 @@
*/
a->entry->end = a->entry->start + a->size;
+ next = RB_NEXT(dmar_gas_entries_tree, &a->domain->rb_root, prev);
+ KASSERT(next->start >= a->entry->end &&
+ 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,
+ (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));
a->entry->flags = DMAR_MAP_ENTRY_MAP;
+
+ KASSERT(RB_PREV(dmar_gas_entries_tree, &a->domain->rb_root,
+ a->entry) == prev,
+ ("entry %p prev %p inserted prev %p", a->entry, prev,
+ RB_PREV(dmar_gas_entries_tree, &a->domain->rb_root, a->entry)));
+ KASSERT(RB_NEXT(dmar_gas_entries_tree, &a->domain->rb_root,
+ a->entry) == next,
+ ("entry %p next %p inserted next %p", a->entry, next,
+ RB_NEXT(dmar_gas_entries_tree, &a->domain->rb_root, a->entry)));
}
static int
-dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *entry)
+dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev)
{
- struct dmar_map_entry *child;
+ struct dmar_map_entry *l;
+ int ret;
- child = RB_RIGHT(entry, rb_entry);
- if (child != NULL && entry->end < a->common->lowaddr &&
- dmar_gas_match_one(a, entry->end, child->first,
- a->common->lowaddr)) {
- dmar_gas_match_insert(a);
- return (0);
+ if (prev->end < a->common->lowaddr) {
+ a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE,
+ a->common->alignment);
+ if (dmar_gas_match_one(a, prev, a->common->lowaddr)) {
+ dmar_gas_match_insert(a, prev);
+ return (0);
+ }
}
- if (entry->free_down < a->size + a->offset + DMAR_PAGE_SIZE)
+ if (prev->free_down < a->size + a->offset + DMAR_PAGE_SIZE)
return (ENOMEM);
- child = RB_LEFT(entry, rb_entry);
- if (child != NULL && 0 == dmar_gas_lowermatch(a, child))
- return (0);
- if (child != NULL && child->last < a->common->lowaddr &&
- dmar_gas_match_one(a, child->last, entry->start,
- a->common->lowaddr)) {
- dmar_gas_match_insert(a);
- return (0);
+ l = RB_LEFT(prev, rb_entry);
+ if (l != NULL) {
+ ret = dmar_gas_lowermatch(a, l);
+ if (ret == 0)
+ return (0);
}
- child = RB_RIGHT(entry, rb_entry);
- if (child != NULL && 0 == dmar_gas_lowermatch(a, child))
- return (0);
+ l = RB_RIGHT(prev, rb_entry);
+ if (l != NULL)
+ return (dmar_gas_lowermatch(a, l));
return (ENOMEM);
}
static int
-dmar_gas_uppermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *entry)
+dmar_gas_uppermatch(struct dmar_gas_match_args *a)
{
- struct dmar_map_entry *child;
+ struct dmar_map_entry *next, *prev, find_entry;
- if (entry->last < a->common->highaddr)
+ find_entry.start = a->common->highaddr;
+ next = RB_NFIND(dmar_gas_entries_tree, &a->domain->rb_root,
+ &find_entry);
+ if (next == NULL)
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 &&
- dmar_gas_match_one(a, child->last, entry->start,
- a->domain->end)) {
- dmar_gas_match_insert(a);
- return (0);
+ 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,
+ a->common->alignment);
+ if (dmar_gas_match_one(a, prev, a->domain->end)) {
+ dmar_gas_match_insert(a, prev);
+ 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 &&
- dmar_gas_match_one(a, entry->end, child->first,
- a->domain->end)) {
- dmar_gas_match_insert(a);
- return (0);
- }
- if (child != NULL && 0 == dmar_gas_uppermatch(a, child))
- return (0);
- return (ENOMEM);
}
static int
@@ -443,7 +504,7 @@
/* Handle upper region. */
if (common->highaddr >= domain->end)
return (ENOMEM);
- error = dmar_gas_uppermatch(&a, RB_ROOT(&domain->rb_root));
+ error = dmar_gas_uppermatch(&a);
KASSERT(error == ENOMEM,
("error %d from dmar_gas_uppermatch", error));
return (error);

File Metadata

Mime Type
text/plain
Expires
Tue, Apr 21, 3:47 PM (11 h, 40 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31901419
Default Alt Text
D23435.id67634.diff (18 KB)

Event Timeline