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
@@ -99,7 +99,8 @@
 .Nm RB_INSERT ,
 .Nm RB_REMOVE ,
 .Nm RB_REINSERT ,
-.Nm RB_AUGMENT
+.Nm RB_AUGMENT ,
+.Nm RB_AUGMENT_CHECK
 .Nd "implementations of splay and rank-balanced (wavl) trees"
 .Sh SYNOPSIS
 .In sys/tree.h
@@ -196,6 +197,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"
 .Sh DESCRIPTION
 These macros define data structures for different types of trees:
 splay trees and rank-balanced (wavl) trees.
@@ -598,6 +601,21 @@
 bottom of the tree up to the top.
 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, 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.
 .Sh EXAMPLES
 The following example demonstrates how to declare a rank-balanced tree
 holding integers.
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,43 @@
 	return (0);
 }
 
-static void
+static bool
 iommu_gas_augment_entry(struct iommu_map_entry *entry)
 {
-	struct iommu_map_entry *child;
+	struct iommu_map_entry *left, *right;
 	iommu_gaddr_t free_down;
+	bool changed;
 
-	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
+	left = RB_LEFT(entry, rb_entry);
+	right = RB_RIGHT(entry, rb_entry);
+	if (left == NULL && right == NULL) {
 		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 = 0;
+		return (true);
+	}
+	if (left == NULL) {
+		entry->first = entry->start;
+		entry->last = right->last;
+		entry->free_down = right->first - entry->end;
+		return (true);
+	}
+	if (right == NULL) {
+		entry->first = left->start;
+		entry->last = entry->end;
+		entry->free_down = entry->start - left->last;
+		return (true);
+	}
+	free_down = MAX(
+	    MAX(left->free_down, entry->start - left->last),
+	    MAX(right->free_down, right->first - entry->end));
+	changed = free_down != entry->free_down ||
+		left->first != entry->first ||
+		right->last != entry->last;
 	entry->free_down = free_down;
+	entry->first = left->first;
+	entry->last = right->last;
+	return (changed);
 }
 
 RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -362,12 +362,20 @@
 				RB_RED_LEFT(RB_PARENT(elm, field), field) : \
 				RB_RED_RIGHT(RB_PARENT(elm, field), field))
 
+
 /*
- * 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_SWAP_CHILD(head, out, in, field) do {			\
@@ -380,7 +388,6 @@
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
-	(tmp) = RB_RIGHT(elm, field);					\
 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
 		RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);	\
 	}								\
@@ -388,11 +395,10 @@
 	RB_SWAP_CHILD(head, elm, tmp, field);				\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
-	RB_AUGMENT(elm);						\
+	RB_AUGMENT_CHECK(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
-	(tmp) = RB_LEFT(elm, field);					\
 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
 		RB_SET_PARENT(RB_LEFT(elm, field), elm, field);		\
 	}								\
@@ -400,7 +406,7 @@
 	RB_SWAP_CHILD(head, elm, tmp, field);				\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
-	RB_AUGMENT(elm);						\
+	RB_AUGMENT_CHECK(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 /* Generates prototypes and inline functions */
@@ -465,19 +471,21 @@
 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 {									\
 	struct type *child, *parent;					\
-	while ((parent = RB_PARENT(elm, field)) != NULL) {		\
+	bool changed;							\
+	for (changed = true;						\
+	    (parent = RB_PARENT(elm, field)) != NULL;			\
+	    changed = changed && RB_AUGMENT_CHECK(elm), elm = parent) { \
 		if (RB_LEFT(parent, field) == elm) {			\
 			if (RB_RED_LEFT(parent, field)) {		\
 				RB_FLIP_LEFT(parent, field);		\
-				return;					\
+				break;					\
 			}						\
 			RB_FLIP_RIGHT(parent, field);			\
-			if (RB_RED_RIGHT(parent, field)) {		\
-				elm = parent;				\
+			if (RB_RED_RIGHT(parent, field))		\
 				continue;				\
-			}						\
 			if (!RB_RED_RIGHT(elm, field)) {		\
 				RB_FLIP_LEFT(elm, field);		\
+				child = RB_RIGHT(elm, field);		\
 				RB_ROTATE_LEFT(head, elm, child, field);\
 				if (RB_RED_LEFT(child, field))		\
 					RB_FLIP_RIGHT(elm, field);	\
@@ -489,15 +497,14 @@
 		} else {						\
 			if (RB_RED_RIGHT(parent, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
+				break;					\
 			}						\
 			RB_FLIP_LEFT(parent, field);			\
-			if (RB_RED_LEFT(parent, field)) {		\
-				elm = parent;				\
+			if (RB_RED_LEFT(parent, field))			\
 				continue;				\
-			}						\
 			if (!RB_RED_LEFT(elm, field)) {			\
 				RB_FLIP_RIGHT(elm, field);		\
+				child = RB_LEFT(elm, field);		\
 				RB_ROTATE_RIGHT(head, elm, child, field);\
 				if (RB_RED_RIGHT(child, field))		\
 					RB_FLIP_LEFT(elm, field);	\
@@ -508,8 +515,14 @@
 			RB_ROTATE_LEFT(head, parent, elm, field);	\
 		}							\
 		RB_BITS(elm, field) &= ~RB_RED_MASK;			\
+		RB_AUGMENT_CHECK(elm);					\
+		elm = RB_PARENT(elm, field);				\
 		break;							\
 	}								\
+	if (changed) {							\
+		while (elm != NULL && RB_AUGMENT_CHECK(elm))		\
+			elm = RB_PARENT(elm, field);			\
+	}								\
 }
 
 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
@@ -518,29 +531,28 @@
     struct type *parent, struct type *elm)				\
 {									\
 	struct type *sib;						\
+	bool changed = true;						\
 	if (RB_LEFT(parent, field) == elm &&				\
 	    RB_RIGHT(parent, field) == elm) {				\
 		RB_BITS(parent, field) &= ~RB_RED_MASK;			\
 		elm = parent;						\
-		parent = RB_PARENT(elm, field);				\
-		if (parent == NULL)					\
+		changed = changed && RB_AUGMENT_CHECK(elm);		\
+		if ((parent = RB_PARENT(elm, field)) == NULL)		\
 			return;						\
 	}								\
 	do  {								\
 		if (RB_LEFT(parent, field) == elm) {			\
 			if (!RB_RED_LEFT(parent, field)) {		\
 				RB_FLIP_LEFT(parent, field);		\
-				return;					\
+				break;					\
 			}						\
 			if (RB_RED_RIGHT(parent, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
-				elm = parent;				\
 				continue;				\
 			}						\
 			sib = RB_RIGHT(parent, field);			\
 			if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
 				RB_BITS(sib, field) &= ~RB_RED_MASK;	\
-				elm = parent;				\
 				continue;				\
 			}						\
 			RB_FLIP_RIGHT(sib, field);			\
@@ -548,6 +560,7 @@
 				RB_FLIP_LEFT(parent, field);		\
 			else if (!RB_RED_RIGHT(sib, field)) {		\
 				RB_FLIP_LEFT(parent, field);		\
+				elm = RB_LEFT(sib, field);		\
 				RB_ROTATE_RIGHT(head, sib, elm, field);	\
 				if (RB_RED_RIGHT(elm, field))		\
 					RB_FLIP_LEFT(sib, field);	\
@@ -560,17 +573,15 @@
 		} else {						\
 			if (!RB_RED_RIGHT(parent, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
+				break;					\
 			}						\
 			if (RB_RED_LEFT(parent, field)) {		\
 				RB_FLIP_LEFT(parent, field);		\
-				elm = parent;				\
 				continue;				\
 			}						\
 			sib = RB_LEFT(parent, field);			\
 			if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
 				RB_BITS(sib, field) &= ~RB_RED_MASK;	\
-				elm = parent;				\
 				continue;				\
 			}						\
 			RB_FLIP_LEFT(sib, field);			\
@@ -578,6 +589,7 @@
 				RB_FLIP_RIGHT(parent, field);		\
 			else if (!RB_RED_LEFT(sib, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
+				elm = RB_RIGHT(sib, field);		\
 				RB_ROTATE_LEFT(head, sib, elm, field);	\
 				if (RB_RED_LEFT(elm, field))		\
 					RB_FLIP_RIGHT(sib, field);	\
@@ -588,8 +600,16 @@
 			}						\
 			RB_ROTATE_RIGHT(head, parent, sib, field);	\
 		}							\
+		RB_AUGMENT_CHECK(sib);					\
+		parent = RB_PARENT(sib, field);				\
 		break;							\
-	} while ((parent = RB_PARENT(elm, field)) != NULL);		\
+	} while (elm = parent,						\
+	    changed = changed && RB_AUGMENT_CHECK(elm),			\
+	    (parent = RB_PARENT(elm, field)) != NULL);			\
+	if (changed) {							\
+		while (parent != NULL && RB_AUGMENT_CHECK(parent))	\
+			parent = RB_PARENT(parent, field);		\
+	}								\
 }
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\
@@ -627,10 +647,6 @@
 		RB_SET_PARENT(child, parent, field);			\
 	if (parent != NULL)						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
-	while (parent != NULL) {					\
-		RB_AUGMENT(parent);					\
-		parent = RB_PARENT(parent, field);			\
-	}								\
 	return (old);							\
 }
 
@@ -661,10 +677,6 @@
 	else								\
 		RB_RIGHT(parent, field) = elm;				\
 	name##_RB_INSERT_COLOR(head, elm);				\
-	while (elm != NULL) {						\
-		RB_AUGMENT(elm);					\
-		elm = RB_PARENT(elm, field);				\
-	}								\
 	return (NULL);							\
 }