Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -335,8 +335,12 @@
 	RB_COLOR(red, field) = RB_RED;					\
 } 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.
+ */
 #ifndef RB_AUGMENT
-#define RB_AUGMENT(x)	do {} while (0)
+#define RB_AUGMENT(x)	break
 #endif
 
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
@@ -344,7 +348,6 @@
 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
 	}								\
-	RB_AUGMENT(elm);						\
 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
@@ -354,9 +357,7 @@
 		(head)->rbh_root = (tmp);				\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
-	RB_AUGMENT(tmp);						\
-	if ((RB_PARENT(tmp, field)))					\
-		RB_AUGMENT(RB_PARENT(tmp, field));			\
+	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
@@ -364,7 +365,6 @@
 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
 	}								\
-	RB_AUGMENT(elm);						\
 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
@@ -374,9 +374,7 @@
 		(head)->rbh_root = (tmp);				\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
-	RB_AUGMENT(tmp);						\
-	if ((RB_PARENT(tmp, field)))					\
-		RB_AUGMENT(RB_PARENT(tmp, field));			\
+	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 /* Generates prototypes and inline functions */
@@ -571,62 +569,49 @@
 	else if (RB_RIGHT(elm, field) == NULL)				\
 		child = RB_LEFT(elm, field);				\
 	else {								\
-		struct type *left;					\
-		elm = RB_RIGHT(elm, field);				\
-		while ((left = RB_LEFT(elm, field)) != NULL)		\
-			elm = left;					\
-		child = RB_RIGHT(elm, field);				\
-		parent = RB_PARENT(elm, field);				\
-		color = RB_COLOR(elm, field);				\
-		if (child)						\
-			RB_PARENT(child, field) = parent;		\
-		if (parent) {						\
-			if (RB_LEFT(parent, field) == elm)		\
-				RB_LEFT(parent, field) = child;		\
+		elm = RB_RIGHT(old, field);				\
+		if ((child = RB_LEFT(elm, field)) == NULL) {		\
+			child = RB_RIGHT(elm, field);			\
+			RB_RIGHT(old, field) = child;			\
+			RB_PARENT(elm, field) = elm;			\
+		} else {						\
+			do						\
+				elm = child;				\
+			while ((child = RB_LEFT(elm, field)) != NULL);	\
+			child = RB_RIGHT(elm, field);			\
+			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
+		}							\
+		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
+		parent = RB_PARENT(old, field);				\
+		if (parent != NULL) {					\
+			if (RB_LEFT(parent, field) == old)		\
+				RB_LEFT(parent, field) = elm;		\
 			else						\
-				RB_RIGHT(parent, field) = child;	\
-			RB_AUGMENT(parent);				\
+				RB_RIGHT(parent, field) = elm;		\
 		} else							\
-			RB_ROOT(head) = child;				\
-		if (RB_PARENT(elm, field) == old)			\
-			parent = elm;					\
-		(elm)->field = (old)->field;				\
-		if (RB_PARENT(old, field)) {				\
-			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
-				RB_LEFT(RB_PARENT(old, field), field) = elm;\
-			else						\
-				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
-			RB_AUGMENT(RB_PARENT(old, field));		\
-		} else							\
 			RB_ROOT(head) = elm;				\
-		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
-		if (RB_RIGHT(old, field))				\
-			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
-		if (parent) {						\
-			left = parent;					\
-			do {						\
-				RB_AUGMENT(left);			\
-			} while ((left = RB_PARENT(left, field)) != NULL); \
-		}							\
-		goto color;						\
 	}								\
 	parent = RB_PARENT(elm, field);					\
 	color = RB_COLOR(elm, field);					\
-	if (child)							\
+	if (child != NULL)						\
 		RB_PARENT(child, field) = parent;			\
-	if (parent) {							\
+	if (parent != NULL) {						\
 		if (RB_LEFT(parent, field) == elm)			\
 			RB_LEFT(parent, field) = child;			\
 		else							\
 			RB_RIGHT(parent, field) = child;		\
-		RB_AUGMENT(parent);					\
 	} else								\
 		RB_ROOT(head) = child;					\
-color:									\
+	if (elm != old)							\
+		(elm)->field = (old)->field;				\
 	if (color == RB_BLACK)						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
+	while (parent != NULL) {					\
+		RB_AUGMENT(parent);					\
+		parent = RB_PARENT(parent, field);			\
+	}								\
 	return (old);							\
-}									\
+}
 
 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 /* Inserts a node into the RB tree */					\
@@ -653,10 +638,13 @@
 			RB_LEFT(parent, field) = elm;			\
 		else							\
 			RB_RIGHT(parent, field) = elm;			\
-		RB_AUGMENT(parent);					\
 	} else								\
 		RB_ROOT(head) = elm;					\
 	name##_RB_INSERT_COLOR(head, elm);				\
+	while (elm != NULL) {						\
+		RB_AUGMENT(elm);					\
+		elm = RB_PARENT(elm, field);				\
+	}								\
 	return (NULL);							\
 }
 
Index: sys/x86/iommu/intel_gas.c
===================================================================
--- sys/x86/iommu/intel_gas.c
+++ sys/x86/iommu/intel_gas.c
@@ -139,38 +139,20 @@
 static void
 dmar_gas_augment_entry(struct dmar_map_entry *entry)
 {
-	struct dmar_map_entry *l, *r;
+	struct dmar_map_entry *child;
+	dmar_gaddr_t free_down;
 
-	for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) {
-		l = RB_LEFT(entry, rb_entry);
-		r = RB_RIGHT(entry, rb_entry);
-		if (l == NULL && r == NULL) {
-			entry->free_down = entry->free_after;
-		} else if (l == NULL && r != NULL) {
-			entry->free_down = MAX(entry->free_after, r->free_down);
-		} else if (/*l != NULL && */ r == NULL) {
-			entry->free_down = MAX(entry->free_after, l->free_down);
-		} else /* if (l != NULL && r != NULL) */ {
-			entry->free_down = MAX(entry->free_after, l->free_down);
-			entry->free_down = MAX(entry->free_down, r->free_down);
-		}
-	}
+	free_down = entry->free_after;
+	if ((child = RB_LEFT(entry, rb_entry)) != NULL)
+		free_down = MAX(free_down, child->free_down);
+	if ((child = RB_RIGHT(entry, rb_entry)) != NULL)
+		free_down = MAX(free_down, child->free_down);
+	entry->free_down = free_down;
 }
 
 RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry,
     dmar_gas_cmp_entries);
 
-static void
-dmar_gas_fix_free(struct dmar_domain *domain, struct dmar_map_entry *entry)
-{
-	struct dmar_map_entry *next;
-
-	next = RB_NEXT(dmar_gas_entries_tree, &domain->rb_root, entry);
-	entry->free_after = (next != NULL ? next->start : domain->end) -
-	    entry->end;
-	dmar_gas_augment_entry(entry);
-}
-
 #ifdef INVARIANTS
 static void
 dmar_gas_check_free(struct dmar_domain *domain)
@@ -211,13 +193,9 @@
 static bool
 dmar_gas_rb_insert(struct dmar_domain *domain, struct dmar_map_entry *entry)
 {
-	struct dmar_map_entry *prev, *found;
+	struct dmar_map_entry *found;
 
 	found = RB_INSERT(dmar_gas_entries_tree, &domain->rb_root, entry);
-	dmar_gas_fix_free(domain, entry);
-	prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry);
-	if (prev != NULL)
-		dmar_gas_fix_free(domain, prev);
 	return (found == NULL);
 }
 
@@ -228,8 +206,6 @@
 
 	prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry);
 	RB_REMOVE(dmar_gas_entries_tree, &domain->rb_root, entry);
-	if (prev != NULL)
-		dmar_gas_fix_free(domain, prev);
 }
 
 void