git: cd6395519895 - stable/13 - rb_tree: augmentation shortcut
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 12 Oct 2022 03:00:24 UTC
The branch stable/13 has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=cd639551989539c94c251c81abaa23ab912374a1
commit cd639551989539c94c251c81abaa23ab912374a1
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-09-21 04:21:14 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-10-12 02:45:23 +0000
rb_tree: augmentation shortcut
RB-tree augmentation maintains data in each node of the tree that
represents the product of some associative operator applied to all the
nodes of the subtree rooted at that node. If a node in the tree
changes, augmentation data for the node is updated for that node and
all nodes on the path from that node to the tree root. However,
sometimes, augmenting a node changes no data in that node,
particularly if the associated operation is something involving 'max'
or 'min'. If augmentation changes nothing in a node, then the work of
walking to the tree root from that point is pointless, because
augmentation will change nothing in those nodes either. This change
makes it possible to avoid that wasted work.
Define RB_AUGMENT_CHECK as a macro much like RB_AUGMENT, but which
returns a value 'true' when augmentation changes the augmentation data
of a node, and false otherwise. Change code that unconditionally walks
and augments to the top of tree to code that stops once an
augmentation has no effect. In the case of rebalancing the tree after
insertion or deletion, where previously a node rotated into the path
was inevitably augmented on the march to the tree root, now check to
see if it needs augmentation because the march to the tree root
stopped before reaching it.
Change the augmentation function in iommu_gas.c so that it returns
true/false to indicate whether the augmentation had any effect.
Reviewed by: alc, kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36509
(cherry picked from commit b16f993ec2cafe48fae96ca0eb27224951b30d7e)
---
share/man/man3/Makefile | 1 +
share/man/man3/tree.3 | 19 +++++++++++
sys/dev/iommu/iommu_gas.c | 60 +++++++++++++++++++++++-----------
sys/sys/tree.h | 82 +++++++++++++++++++++++++++++++++--------------
4 files changed, 120 insertions(+), 42 deletions(-)
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index fa4f751ce553..872aec1e83ab 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -320,6 +320,7 @@ MLINKS+= timeradd.3 timerclear.3 \
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
index 86d6569d1955..eaddc9f811c4 100644
--- 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 @@ It is typically used to maintain some associative accumulation of tree
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
index 68e22f16c69f..c04edb8451b4 100644
--- 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 @@ iommu_gas_cmp_entries(struct iommu_map_entry *a, struct iommu_map_entry *b)
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 @@ iommu_gas_init_domain(struct iommu_domain *domain)
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
index c0cd65f41acb..e10d92bb5ce6 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -357,18 +357,25 @@ struct { \
} 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 @@ struct { \
#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 @@ struct { \
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 @@ name##_RB_RANK(struct type *elm) \
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 @@ name##_RB_RANK(struct type *elm) \
#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 @@ name##_RB_INSERT_COLOR(struct name *head, \
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 @@ name##_RB_INSERT_COLOR(struct name *head, \
_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 @@ name##_RB_INSERT_COLOR(struct name *head, \
#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 @@ name##_RB_REMOVE_COLOR(struct name *head, \
_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 @@ name##_RB_REMOVE_COLOR(struct name *head, \
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 @@ name##_RB_REMOVE_COLOR(struct name *head, \
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 @@ name##_RB_REMOVE(struct name *head, struct type *out) \
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 @@ name##_RB_INSERT(struct name *head, struct type *elm) \
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); \
}