Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -97,6 +97,7 @@
 .Nm RB_FOREACH_REVERSE_SAFE ,
 .Nm RB_INIT ,
 .Nm RB_INSERT ,
+.Nm RB_INSERT_AT ,
 .Nm RB_REMOVE ,
 .Nm RB_REINSERT
 .Nd "implementations of splay and rank-balanced (wavl) trees"
@@ -189,6 +190,8 @@
 .Fn RB_INIT "RB_HEAD *head"
 .Ft "struct TYPE *"
 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
+.Ft "void"
+.Fn RB_INSERT NAME_AT "RB_HEAD *head" "struct TYPE *parent" "int comp" "struct TYPE *elm"
 .Ft "struct TYPE *"
 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
 .Ft "struct TYPE *"
@@ -506,6 +509,12 @@
 into the tree.
 .Pp
 The
+.Fn RB_INSERT_AT
+macro inserts the new element
+.Fa elm
+into the tree as a child of a specified parent.
+.Pp
+The
 .Fn RB_REMOVE
 macro removes the element
 .Fa elm
Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -352,9 +352,9 @@
 }
 
 static void
-iommu_gas_match_insert(struct iommu_gas_match_args *a)
+iommu_gas_match_insert(struct iommu_gas_match_args *a,
+    struct iommu_map_entry *parent, int comp)
 {
-	bool found __diagused;
 
 	/*
 	 * The prev->end is always aligned on the page size, which
@@ -367,9 +367,15 @@
 	a->entry->end = a->entry->start +
 	    roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
 
-	found = iommu_gas_rb_insert(a->domain, a->entry);
-	KASSERT(found, ("found dup %p start %jx size %jx",
-	    a->domain, (uintmax_t)a->entry->start, (uintmax_t)a->size));
+	if (comp < 0) {
+		while (RB_LEFT(parent, rb_entry) != NULL)
+			parent = RB_LEFT(parent, rb_entry);
+	} else {
+		while (RB_RIGHT(parent, rb_entry) != NULL)
+			parent = RB_RIGHT(parent, rb_entry);
+	}
+	RB_INSERT_AT(iommu_gas_entries_tree,
+	    &a->domain->rb_root, parent, comp, a->entry);
 	a->entry->flags = IOMMU_MAP_ENTRY_MAP;
 }
 
@@ -406,7 +412,7 @@
 			}
 			if (iommu_gas_match_one(a, first->last, entry->start,
 			    a->common->lowaddr)) {
-				iommu_gas_match_insert(a);
+				iommu_gas_match_insert(a, first, RB_INF);
 				return (0);
 			}
 		}
@@ -417,7 +423,7 @@
 		if ((first = RB_RIGHT(entry, rb_entry)) != NULL &&
 		    iommu_gas_match_one(a, entry->end, first->first,
 		    a->common->lowaddr)) {
-			iommu_gas_match_insert(a);
+			iommu_gas_match_insert(a, first, RB_NEGINF);
 			return (0);
 		}
 		/* Find the next entry that might abut a big-enough range. */
@@ -458,14 +464,14 @@
 	if (child != NULL && child->last >= a->common->highaddr &&
 	    iommu_gas_match_one(a, child->last, entry->start,
 	    a->domain->end)) {
-		iommu_gas_match_insert(a);
+		iommu_gas_match_insert(a, child, RB_INF);
 		return (0);
 	}
 	child = RB_RIGHT(entry, rb_entry);
 	if (child != NULL && entry->end >= a->common->highaddr &&
 	    iommu_gas_match_one(a, entry->end, child->first,
 	    a->domain->end)) {
-		iommu_gas_match_insert(a);
+		iommu_gas_match_insert(a, child, RB_NEGINF);
 		return (0);
 	}
 	if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -411,6 +411,7 @@
 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_INSERT_AT(name, type, attr);			\
 	RB_PROTOTYPE_INSERT(name, type, attr);				\
 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
 	RB_PROTOTYPE_FIND(name, type, attr);				\
@@ -426,6 +427,9 @@
 	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\
 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT_AT(name, type, attr)			\
+	attr void name##_RB_INSERT_AT(struct name *, struct type *,	\
+	    int, struct type *)
 #define RB_PROTOTYPE_INSERT(name, type, attr)				\
 	attr struct type *name##_RB_INSERT(struct name *, struct type *)
 #define RB_PROTOTYPE_FIND(name, type, attr)				\
@@ -451,6 +455,7 @@
 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+	RB_GENERATE_INSERT_AT(name, type, field, cmp, attr)		\
 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 	RB_GENERATE_REMOVE(name, type, field, attr)			\
 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
@@ -634,6 +639,26 @@
 	return (old);							\
 }
 
+#define RB_GENERATE_INSERT_AT(name, type, field, cmp, attr)		\
+/* Inserts a node into the RB tree */					\
+attr void								\
+name##_RB_INSERT_AT(struct name *head, struct type *parent,		\
+    int comp, struct type *elm)						\
+{									\
+	RB_SET(elm, parent, field);					\
+	if (parent == NULL)						\
+		RB_ROOT(head) = elm;					\
+	else if (comp < 0)						\
+		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);				\
+	}								\
+}
+
 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 /* Inserts a node into the RB tree */					\
 attr struct type *							\
@@ -653,18 +678,7 @@
 		else							\
 			return (tmp);					\
 	}								\
-	RB_SET(elm, parent, field);					\
-	if (parent == NULL)						\
-		RB_ROOT(head) = elm;					\
-	else if (comp < 0)						\
-		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);				\
-	}								\
+	name##_RB_INSERT_AT(head, parent, comp, elm);			\
 	return (NULL);							\
 }
 
@@ -781,6 +795,7 @@
 #define RB_INF	1
 
 #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
+#define RB_INSERT_AT(name, x, y, z, w)name##_RB_INSERT_AT(x, y, z, w)
 #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
 #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
 #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)