diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -292,90 +292,109 @@
 
 /*
  * The interval [beg, end) is a free interval between two iommu_map_entries.
- * maxaddr is an upper bound on addresses that can be allocated. Try to
- * allocate space in the free interval, subject to the conditions expressed
- * by a, and return 'true' if and only if the allocation attempt succeeds.
+ * Addresses can be allocated only in the range [lbound, ubound). Try to
+ * allocate space in the free interval, subject to the conditions expressed by
+ * a, and return 'true' if and only if the allocation attempt succeeds.
  */
 static bool
 iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
-    iommu_gaddr_t end, iommu_gaddr_t maxaddr)
+    iommu_gaddr_t end, iommu_gaddr_t lbound, iommu_gaddr_t ubound)
 {
-	iommu_gaddr_t bs, start;
+	struct iommu_map_entry *entry;
+	iommu_gaddr_t first, size, start;
+	bool found __diagused;
+	int offset;
 
 	/*
 	 * The prev->end is always aligned on the page size, which
 	 * causes page alignment for the entry->start too.
 	 *
-	 * A page sized gap is created between consecutive
-	 * allocations to ensure that out-of-bounds accesses fault.
+	 * Create IOMMU_PAGE_SIZE gaps before, after new entry
+	 * to ensure that out-of-bounds accesses fault.
 	 */
-	a->entry->start = roundup2(beg + IOMMU_PAGE_SIZE,
-	    a->common->alignment);
-	if (a->entry->start + a->offset + a->size > maxaddr)
+	beg = MAX(beg + IOMMU_PAGE_SIZE, lbound);
+	start = roundup2(beg, a->common->alignment);
+	if (start < beg)
 		return (false);
-
-	/* IOMMU_PAGE_SIZE to create gap after new entry. */
-	if (a->entry->start < beg + IOMMU_PAGE_SIZE ||
-	    a->entry->start + a->size + a->offset + IOMMU_PAGE_SIZE > end)
+	end = MIN(end - IOMMU_PAGE_SIZE, ubound);
+	offset = a->offset;
+	size = a->size;
+	if (start + offset + size > end)
 		return (false);
 
-	/* No boundary crossing. */
-	if (vm_addr_bound_ok(a->entry->start + a->offset, a->size,
-	    a->common->boundary))
-		return (true);
-
-	/*
-	 * The start + offset to start + offset + size region crosses
-	 * the boundary.  Check if there is enough space after the
-	 * next boundary after the beg.
-	 */
-	bs = rounddown2(a->entry->start + a->offset + a->common->boundary,
-	    a->common->boundary);
-	start = roundup2(bs, a->common->alignment);
-	/* IOMMU_PAGE_SIZE to create gap after new entry. */
-	if (start + a->offset + a->size + IOMMU_PAGE_SIZE <= end &&
-	    start + a->offset + a->size <= maxaddr &&
-	    vm_addr_bound_ok(start + a->offset, a->size,
-	    a->common->boundary)) {
-		a->entry->start = start;
-		return (true);
-	}
-
-	/*
-	 * Not enough space to align at the requested boundary, or
-	 * boundary is smaller than the size, but allowed to split.
-	 * We already checked that start + size does not overlap maxaddr.
-	 *
-	 * XXXKIB. It is possible that bs is exactly at the start of
-	 * the next entry, then we do not have gap.  Ignore for now.
-	 */
-	if ((a->gas_flags & IOMMU_MF_CANSPLIT) != 0) {
-		a->size = bs - a->entry->start - a->offset;
-		return (true);
+	/* Check for and try to skip past boundary crossing. */
+	if (!vm_addr_bound_ok(start + offset, size, a->common->boundary)) {
+		/*
+		 * The start + offset to start + offset + size region crosses
+		 * the boundary.  Check if there is enough space after the next
+		 * boundary after the beg.
+		 */
+		first = start;
+		beg = roundup2(start + offset + 1, a->common->boundary);
+		start = roundup2(beg, a->common->alignment);
+
+		if (start + offset + size > end ||
+		    !vm_addr_bound_ok(start + offset, size,
+		    a->common->boundary)) {
+			/*
+			 * Not enough space to align at the requested boundary,
+			 * or boundary is smaller than the size, but allowed to
+			 * split.  We already checked that start + size does not
+			 * overlap ubound.
+			 *
+			 * XXXKIB. It is possible that beg is exactly at the
+			 * start of the next entry, then we do not have gap.
+			 * Ignore for now.
+			 */
+			if ((a->gas_flags & IOMMU_MF_CANSPLIT) == 0)
+				return (false);
+			size = beg - first - offset;
+			start = first;
+		}
 	}
-
-	return (false);
+	entry = a->entry;
+	entry->start = start;
+	entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
+	entry->flags = IOMMU_MAP_ENTRY_MAP;
+	found = iommu_gas_rb_insert(a->domain, entry);
+	KASSERT(found, ("found dup %p start %jx size %jx",
+	    a->domain, (uintmax_t)start, (uintmax_t)size));
+	return (true);
 }
 
-static void
-iommu_gas_match_insert(struct iommu_gas_match_args *a)
+/* Find the next entry that might abut a big-enough range. */
+static struct iommu_map_entry *
+iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free)
 {
-	bool found __diagused;
-
-	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));
-	a->entry->flags = IOMMU_MAP_ENTRY_MAP;
+	struct iommu_map_entry *next;
+
+	if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
+	    next->free_down >= min_free) {
+		/* Find next entry in right subtree. */
+		do
+			curr = next;
+		while ((next = RB_LEFT(curr, rb_entry)) != NULL &&
+		    next->free_down >= min_free);
+	} else {
+		/* Find next entry in a left-parent ancestor. */
+		while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
+		    curr == RB_RIGHT(next, rb_entry))
+			curr = next;
+		curr = next;
+	}
+	return (curr);
 }
 
 static int
-iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry)
+iommu_gas_find_space(struct iommu_gas_match_args *a)
 {
-	struct iommu_map_entry *first;
-	iommu_gaddr_t min_free;
+	struct iommu_domain *domain;
+	struct iommu_map_entry *curr, *first;
+	iommu_gaddr_t addr, min_free;
+
+	IOMMU_DOMAIN_ASSERT_LOCKED(a->domain);
+	KASSERT(a->entry->flags == 0,
+	    ("dirty entry %p %p", a->domain, a->entry));
 
 	/*
 	 * If the subtree doesn't have free space for the requested allocation
@@ -384,121 +403,74 @@
 	min_free = 2 * IOMMU_PAGE_SIZE +
 	    roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
 
-	/* Find the first entry that could abut a big-enough range. */
+	/*
+	 * Find the first entry in the lower region that could abut a big-enough
+	 * range.
+	 */
+	curr = RB_ROOT(&a->domain->rb_root);
 	first = NULL;
-	while (entry != NULL && entry->free_down >= min_free) {
-		first = entry;
-		entry = RB_LEFT(entry, rb_entry);
+	while (curr != NULL && curr->free_down >= min_free) {
+		first = curr;
+		curr = RB_LEFT(curr, rb_entry);
 	}
 
 	/*
 	 * Walk the big-enough ranges until one satisfies alignment
 	 * requirements, or violates lowaddr address requirement.
 	 */
-	entry = first;
-	while (entry != NULL) {
-		if ((first = RB_LEFT(entry, rb_entry)) != NULL &&
-		    iommu_gas_match_one(a, first->last, entry->start,
-		    a->common->lowaddr)) {
-			iommu_gas_match_insert(a);
+	addr = a->common->lowaddr + 1;
+	for (curr = first; curr != NULL;
+	    curr = iommu_gas_next(curr, min_free)) {
+		if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
+		    iommu_gas_match_one(a, first->last, curr->start,
+		    0, addr))
 			return (0);
-		}
-		if (entry->end >= a->common->lowaddr) {
-			/* All remaining ranges >= lowaddr */
+		if (curr->end >= addr) {
+			/* All remaining ranges >= addr */
 			break;
 		}
-		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);
+		if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+		    iommu_gas_match_one(a, curr->end, first->first,
+		    0, addr))
 			return (0);
-		}
-		/* Find the next entry that might abut a big-enough range. */
-		if (first != NULL && first->free_down >= min_free) {
-			/* Find next entry in right subtree. */
-			do
-				entry = first;
-			while ((first = RB_LEFT(entry, rb_entry)) != NULL &&
-			    first->free_down >= min_free);
-		} else {
-			/* Find next entry in a left-parent ancestor. */
-			while ((first = RB_PARENT(entry, rb_entry)) != NULL &&
-			    entry == RB_RIGHT(first, rb_entry))
-				entry = first;
-			entry = first;
-		}
 	}
-	return (ENOMEM);
-}
-
-static int
-iommu_gas_uppermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry)
-{
-	struct iommu_map_entry *child;
 
 	/*
-	 * If the subtree doesn't have free space for the requested allocation
-	 * plus two guard pages, give up.
+	 * To resume the search at the start of the upper region, first climb to
+	 * the nearest ancestor that spans highaddr.  Then find the last entry
+	 * before highaddr that could abut a big-enough range.
 	 */
-	if (entry->free_down < 2 * IOMMU_PAGE_SIZE +
-	    roundup2(a->size + a->offset, IOMMU_PAGE_SIZE))
-		return (ENOMEM);
-	if (entry->last < a->common->highaddr)
-		return (ENOMEM);
-	child = RB_LEFT(entry, rb_entry);
-	if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
-		return (0);
-	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);
-		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);
-		return (0);
+	addr = a->common->highaddr;
+	while (curr != NULL && curr->last < addr)
+		curr = RB_PARENT(curr, rb_entry);
+	first = NULL;
+	while (curr != NULL && curr->free_down >= min_free) {
+		if (addr < curr->end)
+			curr = RB_LEFT(curr, rb_entry);
+		else {
+			first = curr;
+			curr = RB_RIGHT(curr, rb_entry);
+		}
 	}
-	if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
-		return (0);
-	return (ENOMEM);
-}
-
-static int
-iommu_gas_find_space(struct iommu_domain *domain,
-    const struct bus_dma_tag_common *common, iommu_gaddr_t size,
-    int offset, u_int flags, struct iommu_map_entry *entry)
-{
-	struct iommu_gas_match_args a;
-	int error;
-
-	IOMMU_DOMAIN_ASSERT_LOCKED(domain);
-	KASSERT(entry->flags == 0, ("dirty entry %p %p", domain, entry));
 
-	a.domain = domain;
-	a.size = size;
-	a.offset = offset;
-	a.common = common;
-	a.gas_flags = flags;
-	a.entry = entry;
-
-	/* Handle lower region. */
-	if (common->lowaddr > 0) {
-		error = iommu_gas_lowermatch(&a, RB_ROOT(&domain->rb_root));
-		if (error == 0)
+	/*
+	 * Walk the remaining big-enough ranges until one satisfies alignment
+	 * requirements.
+	 */
+	domain = a->domain;
+	for (curr = first; curr != NULL;
+	    curr = iommu_gas_next(curr, min_free)) {
+		if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
+		    iommu_gas_match_one(a, first->last, curr->start,
+		    addr + 1, domain->end))
+			return (0);
+		if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+		    iommu_gas_match_one(a, curr->end, first->first,
+		    addr + 1, domain->end))
 			return (0);
-		KASSERT(error == ENOMEM,
-		    ("error %d from iommu_gas_lowermatch", error));
 	}
-	/* Handle upper region. */
-	if (common->highaddr >= domain->end)
-		return (ENOMEM);
-	error = iommu_gas_uppermatch(&a, RB_ROOT(&domain->rb_root));
-	KASSERT(error == 0 || error == ENOMEM,
-	    ("error %d from iommu_gas_uppermatch", error));
-	return (error);
+
+	return (ENOMEM);
 }
 
 static int
@@ -627,19 +599,25 @@
     const struct bus_dma_tag_common *common, iommu_gaddr_t size, int offset,
     u_int eflags, u_int flags, vm_page_t *ma, struct iommu_map_entry **res)
 {
+	struct iommu_gas_match_args a;
 	struct iommu_map_entry *entry;
 	int error;
 
 	KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0,
 	    ("invalid flags 0x%x", flags));
 
+	a.domain = domain;
+	a.size = size;
+	a.offset = offset;
+	a.common = common;
+	a.gas_flags = flags;
 	entry = iommu_gas_alloc_entry(domain,
 	    (flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);
 	if (entry == NULL)
 		return (ENOMEM);
+	a.entry = entry;
 	IOMMU_DOMAIN_LOCK(domain);
-	error = iommu_gas_find_space(domain, common, size, offset, flags,
-	    entry);
+	error = iommu_gas_find_space(&a);
 	if (error == ENOMEM) {
 		IOMMU_DOMAIN_UNLOCK(domain);
 		iommu_gas_free_entry(domain, entry);