The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=80ad47c9325071083d1579aecd50188e0209c5a2
commit 80ad47c9325071083d1579aecd50188e0209c5a2 Author: Doug Moore <[email protected]> AuthorDate: 2022-06-09 04:14:28 +0000 Commit: Doug Moore <[email protected]> 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: [email protected] 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);
