git: c253ae9fe423 - stable/13 - iommu_gas: restrict tree search to promising paths

The branch stable/13 has been updated by dougm:

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

commit c253ae9fe423daab996724cb58bc1be7e59212b9
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-06-06 21:26:01 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-06-27 05:36:42 +0000

    iommu_gas: restrict tree search to promising paths
    
    In iommu_gas_lowermatch and iommu_gas_uppermatch, a subtree search is
    quickly terminated if the largest available free space in the subtree
    is below a limit, where that limit is related to the size of the
    allocation request. However, that limit is too small; it does not
    account for both of the guard pages that will surround the allocated
    space, but only for one of them. Consequently, it permits the search
    to proceed through nodes that cannot produce a successful allocation
    for all the requested space. Fix that limit to improve search
    performance.
    
    Reviewed by:    alc, kib
    Submitted by:   Weixi Zhu (wxzhu@rice.edu)
    MFC after:      3 weeks
    Differential Revision:  https://reviews.freebsd.org/D35414
    
    (cherry picked from commit b831865fe3b8f66281b39a9cb567c92dc285a1da)
---
 sys/dev/iommu/iommu_gas.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
index c4faebec9d08..b8bbcf0de7fb 100644
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -384,7 +384,12 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent
 		iommu_gas_match_insert(a);
 		return (0);
 	}
-	if (entry->free_down < a->size + a->offset + IOMMU_PAGE_SIZE)
+
+	/*
+	 * If the subtree doesn't have free space for the requested allocation
+	 * plus two guard pages, give up.
+	 */
+	if (entry->free_down < a->size + a->offset + 2 * IOMMU_PAGE_SIZE)
 		return (ENOMEM);
 	if (entry->first >= a->common->lowaddr)
 		return (ENOMEM);
@@ -408,7 +413,11 @@ iommu_gas_uppermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent
 {
 	struct iommu_map_entry *child;
 
-	if (entry->free_down < a->size + a->offset + IOMMU_PAGE_SIZE)
+	/*
+	 * If the subtree doesn't have free space for the requested allocation
+	 * plus two guard pages, give up.
+	 */
+	if (entry->free_down < a->size + a->offset + 2 * IOMMU_PAGE_SIZE)
 		return (ENOMEM);
 	if (entry->last < a->common->highaddr)
 		return (ENOMEM);