git: 30031172534c - main - iommu_gas: Change find_space lower search order
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Thu, 09 Jun 2022 04:20:15 UTC
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=30031172534c22695ab7b26a9420bda7b20b0824 commit 30031172534c22695ab7b26a9420bda7b20b0824 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-06-09 04:14:28 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-06-09 04:14:28 +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 --- 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 78dd86c1f255..5b589e999926 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);