Page MenuHomeFreeBSD
Files F107372697

D36509.diff
No OneTemporary
Actions

D36509.diff
View Options

diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -320,6 +320,7 @@
timeradd.3 timespecisset.3 \
timeradd.3 timespeccmp.3
MLINKS+= tree.3 RB_AUGMENT.3 \
+ tree.3 RB_AUGMENT_CHECK.3 \
tree.3 RB_EMPTY.3 \
tree.3 RB_ENTRY.3 \
tree.3 RB_FIND.3 \
diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -100,6 +100,7 @@
.Nm RB_REMOVE ,
.Nm RB_REINSERT ,
.Nm RB_AUGMENT
+.Nm RB_AUGMENT_CHECK,
.Nm RB_UPDATE_AUGMENT
.Nd "implementations of splay and rank-balanced (wavl) trees"
.Sh SYNOPSIS
@@ -197,6 +198,8 @@
.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm"
.Ft "void"
.Fn RB_AUGMENT NAME "struct TYPE *elm"
+.Ft "bool"
+.Fn RB_AUGMENT_CHECK NAME "struct TYPE *elm"
.Ft "void"
.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm"
.Sh DESCRIPTION
@@ -620,6 +623,22 @@
elements, such as sums, minima, maxima, and the like.
.Pp
The
+.Fn RB_AUGMENT_CHECK
+macro updates augmentation data of the element
+.Fa elm
+in the tree.
+By default, it does nothing and returns false.
+If
+.Fn RB_AUGMENT_CHECK
+is defined, then when an element is inserted or removed from the tree,
+it is invoked for every element in the tree that is the root of an
+altered subtree, working from the bottom of the tree up toward the
+top, until it returns false to indicate that it did not change the
+element and so working further up the tree would change nothing.
+It is typically used to maintain some associative accumulation of tree
+elements, such as sums, minima, maxima, and the like.
+.Pp
+The
.Fn RB_UPDATE_AUGMENT
macro updates augmentation data of the element
.Fa elm
diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -31,7 +31,7 @@
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
-#define RB_AUGMENT(entry) iommu_gas_augment_entry(entry)
+#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry)
#include <sys/param.h>
#include <sys/systm.h>
@@ -139,27 +139,41 @@
return (0);
}
-static void
+/*
+ * Update augmentation data based on data from children.
+ * Return true if and only if the update changes the augmentation data.
+ */
+static bool
iommu_gas_augment_entry(struct iommu_map_entry *entry)
{
struct iommu_map_entry *child;
- iommu_gaddr_t free_down;
+ iommu_gaddr_t bound, delta, free_down;
free_down = 0;
+ bound = entry->start;
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;
-
+ free_down = MAX(child->free_down, bound - child->last);
+ bound = child->first;
+ }
+ delta = bound - entry->first;
+ entry->first = bound;
+ bound = entry->end;
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;
+ free_down = MAX(free_down, child->first - bound);
+ bound = child->last;
+ }
+ delta += entry->last - bound;
+ if (delta == 0)
+ delta = entry->free_down - free_down;
+ entry->last = bound;
entry->free_down = free_down;
+
+ /*
+ * Return true either if the value of last-first changed,
+ * or if free_down changed.
+ */
+ return (delta != 0);
}
RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
@@ -228,16 +242,26 @@
KASSERT(RB_EMPTY(&domain->rb_root),
("non-empty entries %p", domain));
- begin->start = 0;
- begin->end = IOMMU_PAGE_SIZE;
- begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
- iommu_gas_rb_insert(domain, begin);
-
+ /*
+ * The end entry must be inserted first because it has a zero-length gap
+ * between start and end. Initially, all augmentation data for a new
+ * entry is zero. Function iommu_gas_augment_entry will compute no
+ * change in the value of (start-end) and no change in the value of
+ * free_down, so it will return false to suggest that nothing changed in
+ * the entry. Thus, inserting the end entry second prevents
+ * augmentation information to be propogated to the begin entry at the
+ * tree root. So it is inserted first.
+ */
end->start = domain->end;
end->end = domain->end;
end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
iommu_gas_rb_insert(domain, 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);
+
domain->first_place = begin;
domain->last_place = end;
domain->flags |= IOMMU_DOMAIN_GAS_INITED;
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -357,18 +357,25 @@
} 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.
+ * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of
+ * every modified subtree, from the bottom up to the root, to update augmented
+ * node data. RB_AUGMENT_CHECK returns true only when the update changes the
+ * node data, so that updating can be stopped short of the root when it returns
+ * false.
*/
+#ifndef RB_AUGMENT_CHECK
#ifndef RB_AUGMENT
-#define RB_AUGMENT(x) break
+#define RB_AUGMENT_CHECK(x) false
+#else
+#define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), true)
+#endif
#endif
#define RB_UPDATE_AUGMENT(elm, field) do { \
__typeof(elm) rb_update_tmp = (elm); \
- do { \
- RB_AUGMENT(rb_update_tmp); \
- } while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \
+ while (RB_AUGMENT_CHECK(rb_update_tmp) && \
+ (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL) \
+ ; \
} while (0)
#define RB_SWAP_CHILD(head, par, out, in, field) do { \
@@ -422,10 +429,10 @@
#define RB_PROTOTYPE_RANK(name, type, attr)
#endif
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
- attr void name##_RB_INSERT_COLOR(struct name *, \
+ attr struct type *name##_RB_INSERT_COLOR(struct name *, \
struct type *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
- attr void name##_RB_REMOVE_COLOR(struct name *, \
+ attr struct type *name##_RB_REMOVE_COLOR(struct name *, \
struct type *, struct type *)
#define RB_PROTOTYPE_REMOVE(name, type, attr) \
attr struct type *name##_RB_REMOVE(struct name *, struct type *)
@@ -465,7 +472,16 @@
RB_GENERATE_REINSERT(name, type, field, cmp, attr)
#ifdef _RB_DIAGNOSTIC
+#ifndef RB_AUGMENT
+#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)
+#else
+#define _RB_AUGMENT_VERIFY(x) false
+#endif
#define RB_GENERATE_RANK(name, type, field, attr) \
+/* \
+ * Return the rank of the subtree rooted at elm, or -1 if the subtree \
+ * is not rank-balanced, or has inconsistent augmentation data.
+ */ \
attr int \
name##_RB_RANK(struct type *elm) \
{ \
@@ -482,7 +498,8 @@
right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) + \
name##_RB_RANK(right); \
if (left_rank != right_rank || \
- (left_rank == 2 && left == NULL && right == NULL)) \
+ (left_rank == 2 && left == NULL && right == NULL) || \
+ _RB_AUGMENT_VERIFY(elm)) \
return (-1); \
return (left_rank); \
}
@@ -491,7 +508,7 @@
#endif
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
-attr void \
+attr struct type * \
name##_RB_INSERT_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
@@ -516,7 +533,7 @@
if (_RB_BITS(gpar) & elmdir) { \
/* shorten the parent-elm edge to rebalance */ \
_RB_BITSUP(parent, field) ^= elmdir; \
- return; \
+ return (NULL); \
} \
sibdir = elmdir ^ _RB_LR; \
/* the other edge must change length */ \
@@ -582,10 +599,11 @@
_RB_UP(child, field) = gpar; \
RB_SWAP_CHILD(head, gpar, parent, child, field); \
if (elm != child) \
- RB_AUGMENT(elm); \
- RB_AUGMENT(parent); \
- break; \
+ RB_AUGMENT_CHECK(elm); \
+ RB_AUGMENT_CHECK(parent); \
+ return (child); \
} while ((parent = gpar) != NULL); \
+ return (NULL); \
}
#ifndef RB_STRICT_HST
@@ -600,7 +618,7 @@
#endif
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
-attr void \
+attr struct type * \
name##_RB_REMOVE_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
@@ -614,7 +632,7 @@
_RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \
elm = parent; \
if ((parent = _RB_UP(elm, field)) == NULL) \
- return; \
+ return (NULL); \
} \
do { \
/* the rank of the tree rooted at elm shrank */ \
@@ -624,7 +642,7 @@
if (_RB_BITS(gpar) & elmdir) { \
/* lengthen the parent-elm edge to rebalance */ \
_RB_UP(parent, field) = gpar; \
- return; \
+ return (NULL); \
} \
if (_RB_BITS(gpar) & _RB_LR) { \
/* shorten other edge, retry from parent */ \
@@ -707,11 +725,19 @@
RB_SET_PARENT(elm, gpar, field); \
RB_SWAP_CHILD(head, gpar, parent, elm, field); \
if (sib != elm) \
- RB_AUGMENT(sib); \
- break; \
+ RB_AUGMENT_CHECK(sib); \
+ return (parent); \
} while (elm = parent, (parent = gpar) != NULL); \
+ return (NULL); \
}
+#define _RB_AUGMENT_WALK(elm, match, field) \
+do { \
+ if (match == elm) \
+ match = NULL; \
+} while (RB_AUGMENT_CHECK(elm) && \
+ (elm = RB_PARENT(elm, field)) != NULL)
+
#define RB_GENERATE_REMOVE(name, type, field, attr) \
attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *out) \
@@ -744,12 +770,18 @@
if (child != NULL) \
_RB_UP(child, field) = parent; \
if (parent != NULL) { \
- name##_RB_REMOVE_COLOR(head, parent, child); \
+ opar = name##_RB_REMOVE_COLOR(head, parent, child); \
/* if rotation has made 'parent' the root of the same \
* subtree as before, don't re-augment it. */ \
- if (parent == in && RB_LEFT(parent, field) == NULL) \
+ if (parent == in && RB_LEFT(parent, field) == NULL) { \
+ opar = NULL; \
parent = RB_PARENT(parent, field); \
- RB_UPDATE_AUGMENT(parent, field); \
+ } \
+ _RB_AUGMENT_WALK(parent, opar, field); \
+ if (opar != NULL) { \
+ RB_AUGMENT_CHECK(opar); \
+ RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \
+ } \
} \
return (out); \
}
@@ -776,8 +808,10 @@
RB_SET(elm, parent, field); \
*tmpp = elm; \
if (parent != NULL) \
- name##_RB_INSERT_COLOR(head, parent, elm); \
- RB_UPDATE_AUGMENT(elm, field); \
+ tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
+ _RB_AUGMENT_WALK(elm, tmp, field); \
+ if (tmp != NULL) \
+ RB_AUGMENT_CHECK(tmp); \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Tue, Jan 14, 5:27 AM (21 h, 33 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
15791410
Default Alt Text
D36509.diff (10 KB)

Event Timeline