Index: share/man/man3/Makefile
===================================================================
--- share/man/man3/Makefile
+++ 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 \
Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ 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,21 @@
 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, does nothing and returns false.
+If 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
Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ 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,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -356,19 +356,26 @@
 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
 } 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 {			\
@@ -426,9 +433,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 *, struct type *)
+	attr struct type *name##_RB_INSERT_COLOR(struct name *,		\
+	    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 *)
@@ -468,7 +476,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)					\
 {									\
@@ -485,7 +502,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);						\
 }
@@ -494,7 +512,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 *elm)		\
 {									\
 	/*								\
@@ -507,7 +525,7 @@
 	 * uninitialized 'child', and a later iteration can only happen \
 	 * when a value has been assigned to 'child' in the previous    \
 	 * one.								\
-	 */							\
+	 */								\
 	struct type *child, *child_up, *gpar, *parent;			\
 	__uintptr_t elmdir, sibdir;					\
 									\
@@ -519,7 +537,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 */			\
@@ -585,10 +603,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);						\
 	}								\
+	return (NULL);							\
 }
 
 #ifndef RB_STRICT_HST
@@ -603,7 +622,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)				\
 {									\
@@ -617,7 +636,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 */		\
@@ -627,7 +646,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 */	\
@@ -710,11 +729,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)			\
@@ -747,12 +774,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);							\
 }
@@ -778,8 +811,10 @@
 	}								\
 	RB_SET(elm, parent, field);					\
 	*tmpp = elm;							\
-	name##_RB_INSERT_COLOR(head, elm);				\
-	RB_UPDATE_AUGMENT(elm, field);					\
+	tmp = name##_RB_INSERT_COLOR(head, elm);			\
+	_RB_AUGMENT_WALK(elm, tmp, field);				\
+	if (tmp != NULL)						\
+		RB_AUGMENT_CHECK(tmp);					\
 	return (NULL);							\
 }