git: 80ad47c93250 - stable/13 - iommu_gas: Change find_space lower search order

The branch stable/13 has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=80ad47c9325071083d1579aecd50188e0209c5a2

commit 80ad47c9325071083d1579aecd50188e0209c5a2
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-06-09 04:14:28 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-07-06 16:39:17 +0000

    iommu_gas: Change find_space lower search order
    
    iommu_gas_lowermatch looks right, then left, then right again in its
    search for free space.  Change to a more straightforward last-fit
    search that touches fewer tree nodes and improves performance.
    
    Reported by:    wxzhu@rice.edu
    Reviewed by:    alc, kib
    MFC after:      3 weeks
    Differential Revision:  https://reviews.freebsd.org/D35439
    
    (cherry picked from commit 30031172534c22695ab7b26a9420bda7b20b0824)
---
 sys/dev/iommu/iommu_gas.c | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
index b8bbcf0de7fb..d1a46ab6ee8f 100644
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -377,14 +377,6 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent
 {
 	struct iommu_map_entry *child;
 
-	child = RB_RIGHT(entry, rb_entry);
-	if (child != NULL && entry->end < a->common->lowaddr &&
-	    iommu_gas_match_one(a, entry->end, child->first,
-	    a->common->lowaddr)) {
-		iommu_gas_match_insert(a);
-		return (0);
-	}
-
 	/*
 	 * If the subtree doesn't have free space for the requested allocation
 	 * plus two guard pages, give up.
@@ -393,16 +385,22 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent
 		return (ENOMEM);
 	if (entry->first >= a->common->lowaddr)
 		return (ENOMEM);
-	child = RB_LEFT(entry, rb_entry);
+	child = RB_RIGHT(entry, rb_entry);
 	if (child != NULL && 0 == iommu_gas_lowermatch(a, child))
 		return (0);
+	if (child != NULL && entry->end < a->common->lowaddr &&
+	    iommu_gas_match_one(a, entry->end, child->first,
+	    a->common->lowaddr)) {
+		iommu_gas_match_insert(a);
+		return (0);
+	}
+	child = RB_LEFT(entry, rb_entry);
 	if (child != NULL && child->last < a->common->lowaddr &&
 	    iommu_gas_match_one(a, child->last, entry->start,
 	    a->common->lowaddr)) {
 		iommu_gas_match_insert(a);
 		return (0);
 	}
-	child = RB_RIGHT(entry, rb_entry);
 	if (child != NULL && 0 == iommu_gas_lowermatch(a, child))
 		return (0);
 	return (ENOMEM);