git: 9b12e43d1f80 - stable/13 - iommu_gas: use to first-fit search for lowermatch

The branch stable/13 has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=9b12e43d1f80923fd5f6e9b6a137938830a6165a

commit 9b12e43d1f80923fd5f6e9b6a137938830a6165a
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-06-14 05:47:22 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-07-06 16:42:48 +0000

    iommu_gas: use to first-fit search for lowermatch
    
    Reverse the order of the search for a free space in lowermatch, to
    make it a first-fit search. Iommu_gas_match_one always allocates from
    the beginning of the free gap discovered from searching the tree, so
    the current code isn't really allocating in a reverse first-fit
    anyway, and making the search first-fit reduces the number of iommu
    page table pages that are used.
    
    Reported by:    alc
    Reviewed by:    alc, kib
    MFC after:      3 weeks
    Differential Revision:  https://reviews.freebsd.org/D35458
    
    (cherry picked from commit 975715b78819c6de68df15a6dd78157c6dba0fcb)
---
 sys/dev/iommu/iommu_gas.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
index f7c38e8d65e8..11a3e9ab695e 100644
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -387,18 +387,18 @@ 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_RIGHT(entry, rb_entry);
+	child = RB_LEFT(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,
+	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_LEFT(entry, rb_entry);
-	if (child != NULL && child->last < a->common->lowaddr &&
-	    iommu_gas_match_one(a, child->last, entry->start,
+	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);