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(entry) if (iommu_gas_augment_entry(entry)) break;
 
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -139,27 +139,33 @@
 	return (0);
 }
 
-static void
+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;
+	first = entry->first;
+	free_left = 0;
+	entry->first = 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);
+		free_left = MAX(child->free_down, entry->start - child->last);
 		entry->first = child->first;
-	} else
-		entry->first = entry->start;
+	}
 	
+	last = entry->last;
+	free_right = 0;
+	entry->last = 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);
+		free_right = MAX(child->free_down, child->first - entry->end);
 		entry->last = child->last;
-	} else
-		entry->last = entry->end;
-	entry->free_down = free_down;
+	}
+	free_down = entry->free_down;
+	entry->free_down = MAX(free_left, free_right);
+	return (first == entry->first &&
+		last == entry->last &&
+		free_down == entry->free_down);
 }
 
 RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -389,6 +389,7 @@
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
 	RB_AUGMENT(elm);						\
+	RB_AUGMENT(tmp);						\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
@@ -401,6 +402,7 @@
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
 	RB_AUGMENT(elm);						\
+	RB_AUGMENT(tmp);						\
 } while (/*CONSTCOND*/ 0)
 
 /* Generates prototypes and inline functions */
@@ -625,12 +627,13 @@
 	RB_SWAP_CHILD(head, old, elm, field);				\
 	if (child != NULL)						\
 		RB_SET_PARENT(child, parent, field);			\
-	if (parent != NULL)						\
-		name##_RB_REMOVE_COLOR(head, parent, child);		\
+	elm = parent;							\
 	while (parent != NULL) {					\
 		RB_AUGMENT(parent);					\
 		parent = RB_PARENT(parent, field);			\
 	}								\
+	if (elm != NULL)						\
+		name##_RB_REMOVE_COLOR(head, elm, child);		\
 	return (old);							\
 }
 
@@ -660,11 +663,12 @@
 		RB_LEFT(parent, field) = elm;				\
 	else								\
 		RB_RIGHT(parent, field) = elm;				\
-	name##_RB_INSERT_COLOR(head, elm);				\
-	while (elm != NULL) {						\
-		RB_AUGMENT(elm);					\
-		elm = RB_PARENT(elm, field);				\
+	tmp = elm;							\
+	while (tmp != NULL) {						\
+		RB_AUGMENT(tmp);					\
+		tmp = RB_PARENT(tmp, field);				\
 	}								\
+	name##_RB_INSERT_COLOR(head, elm);				\
 	return (NULL);							\
 }