Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -31,10 +31,11 @@
 #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>
+#include <sys/counter.h>
 #include <sys/malloc.h>
 #include <sys/bus.h>
 #include <sys/interrupt.h>
@@ -139,27 +140,42 @@
 	return (0);
 }
 
-static void
+static COUNTER_U64_DEFINE_EARLY(gas_augments);
+SYSCTL_COUNTER_U64(_hw_iommu, OID_AUTO, gas_augments, CTLFLAG_RD,
+    &gas_augments,
+    "Number of gas tree augmentations");
+
+static bool
 iommu_gas_augment_entry(struct iommu_map_entry *entry)
 {
 	struct iommu_map_entry *child;
-	iommu_gaddr_t free_down;
+	iommu_gaddr_t free_left, free_right;
+	iommu_gaddr_t first, last, free_down;
 
-	free_down = 0;
+	counter_u64_add(gas_augments, 1);
 	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_left = MAX(child->free_down, entry->start - child->last);
+		first = child->first;
+	} else {
+		free_left = 0;
+		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;
+		free_right = MAX(child->free_down, child->first - entry->end);
+		last = child->last;
+	} else {
+		free_right = 0;
+		last = entry->end;
+	}
+	free_down = MAX(free_left, free_right);
+	if (free_down == entry->free_down &&
+	    first == entry->first &&
+	    last == entry->last)
+		return (false);
+	entry->first = first;
+	entry->last = last;
 	entry->free_down = free_down;
+	return (true);
 }
 
 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 {			\
@@ -388,7 +396,7 @@
 	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 {			\
@@ -400,7 +408,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,17 +473,18 @@
 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);		\
 				RB_ROTATE_LEFT(head, elm, child, field);\
@@ -489,13 +498,11 @@
 		} 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);		\
 				RB_ROTATE_RIGHT(head, elm, child, 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;							\
 	}								\
+	while (changed && elm != NULL) {				\
+		changed = RB_AUGMENT_CHECK(elm);			\
+		elm = RB_PARENT(elm, field);				\
+	};								\
 }
 
 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
@@ -518,9 +531,11 @@
     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;			\
+		changed = RB_AUGMENT_CHECK(parent);			\
 		elm = parent;						\
 		parent = RB_PARENT(elm, field);				\
 		if (parent == NULL)					\
@@ -530,17 +545,15 @@
 		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);			\
@@ -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);			\
@@ -588,8 +599,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);			\
+	while (changed && parent != NULL) {				\
+		changed = RB_AUGMENT_CHECK(parent);			\
+		parent = RB_PARENT(parent, field);			\
+	};								\
 }
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\
@@ -627,10 +646,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 +676,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);							\
 }