Page MenuHomeFreeBSD
Files F160491213

D35516.id111213.diff
No OneTemporary
Actions

D35516.id111213.diff
View Options

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_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -206,15 +206,6 @@
}
#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 @@
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 @@
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 @@
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 @@
{
struct iommu_map_entry *entry;
iommu_gaddr_t first, size, start;
- bool found __diagused;
int offset;
/*
@@ -380,9 +369,6 @@
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 @@
* 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 @@
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 @@
* 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 @@
u_int flags)
{
struct iommu_map_entry *next, *prev;
- bool found __diagused;
IOMMU_DOMAIN_ASSERT_LOCKED(domain);
@@ -550,14 +547,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 +643,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 +659,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)
@@ -800,6 +815,29 @@
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. \
+ */ \
+ 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 @@
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. \
- */ \
- 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,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 * \
@@ -911,6 +953,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) \
@@ -947,6 +1005,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)

File Metadata

Mime Type
text/plain
Expires
Fri, Jun 26, 1:50 AM (2 h, 26 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
34336032
Default Alt Text
D35516.id111213.diff (12 KB)

Event Timeline