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,36 @@
 	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 first, free_down, free_left, free_right, last;
 
-	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
-		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 (entry->first == first &&
+	    entry->last == last &&
+	    entry->free_down == free_down)
+		return (true);
+	entry->first = first;
+	entry->last = last;
 	entry->free_down = free_down;
+	return (false);
 }
 
 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 */
@@ -621,6 +623,7 @@
 		}							\
 		RB_SET_PARENT(RB_LEFT(old, field), elm, field);		\
 		elm->field = old->field;				\
+		do {RB_AUGMENT(elm);} while(0);				\
 	}								\
 	RB_SWAP_CHILD(head, old, elm, field);				\
 	if (child != NULL)						\