git: e0e8d0c8d694 - main - iommu_gas: consolidate find_space helpers
Date: Sun, 10 Jul 2022 19:39:40 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=e0e8d0c8d69459c7128e6fd4fb537892445ce710
commit e0e8d0c8d69459c7128e6fd4fb537892445ce710
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-07-10 19:24:23 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-07-10 19:24:23 +0000
iommu_gas: consolidate find_space helpers
Merge lowermatch and uppermatch into find_space. Eliminate uppermatch
recursion. Merge match_insert into match_one and eliminate some
redundant calculation. Move some initialization out of find_space and
into map (and out from under a lock).
Reviewed by: kib (previous version), alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35440
---
sys/dev/iommu/iommu_gas.c | 300 +++++++++++++++++++++-------------------------
1 file changed, 139 insertions(+), 161 deletions(-)
diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
index bb6cde2721a6..86dc919e4572 100644
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -292,90 +292,109 @@ struct iommu_gas_match_args {
/*
* The interval [beg, end) is a free interval between two iommu_map_entries.
- * maxaddr is an upper bound on addresses that can be allocated. Try to
- * allocate space in the free interval, subject to the conditions expressed
- * by a, and return 'true' if and only if the allocation attempt succeeds.
+ * Addresses can be allocated only in the range [lbound, ubound). Try to
+ * allocate space in the free interval, subject to the conditions expressed by
+ * a, and return 'true' if and only if the allocation attempt succeeds.
*/
static bool
iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
- iommu_gaddr_t end, iommu_gaddr_t maxaddr)
+ iommu_gaddr_t end, iommu_gaddr_t lbound, iommu_gaddr_t ubound)
{
- iommu_gaddr_t bs, start;
+ struct iommu_map_entry *entry;
+ iommu_gaddr_t first, size, start;
+ bool found __diagused;
+ int offset;
/*
* The prev->end is always aligned on the page size, which
* causes page alignment for the entry->start too.
*
- * A page sized gap is created between consecutive
- * allocations to ensure that out-of-bounds accesses fault.
+ * Create IOMMU_PAGE_SIZE gaps before, after new entry
+ * to ensure that out-of-bounds accesses fault.
*/
- a->entry->start = roundup2(beg + IOMMU_PAGE_SIZE,
- a->common->alignment);
- if (a->entry->start + a->offset + a->size > maxaddr)
+ beg = MAX(beg + IOMMU_PAGE_SIZE, lbound);
+ start = roundup2(beg, a->common->alignment);
+ if (start < beg)
return (false);
-
- /* IOMMU_PAGE_SIZE to create gap after new entry. */
- if (a->entry->start < beg + IOMMU_PAGE_SIZE ||
- a->entry->start + a->size + a->offset + IOMMU_PAGE_SIZE > end)
+ end = MIN(end - IOMMU_PAGE_SIZE, ubound);
+ offset = a->offset;
+ size = a->size;
+ if (start + offset + size > end)
return (false);
- /* No boundary crossing. */
- if (vm_addr_bound_ok(a->entry->start + a->offset, a->size,
- a->common->boundary))
- return (true);
-
- /*
- * The start + offset to start + offset + size region crosses
- * the boundary. Check if there is enough space after the
- * next boundary after the beg.
- */
- bs = rounddown2(a->entry->start + a->offset + a->common->boundary,
- a->common->boundary);
- start = roundup2(bs, a->common->alignment);
- /* IOMMU_PAGE_SIZE to create gap after new entry. */
- if (start + a->offset + a->size + IOMMU_PAGE_SIZE <= end &&
- start + a->offset + a->size <= maxaddr &&
- vm_addr_bound_ok(start + a->offset, a->size,
- a->common->boundary)) {
- a->entry->start = start;
- return (true);
- }
-
- /*
- * Not enough space to align at the requested boundary, or
- * boundary is smaller than the size, but allowed to split.
- * We already checked that start + size does not overlap maxaddr.
- *
- * XXXKIB. It is possible that bs is exactly at the start of
- * the next entry, then we do not have gap. Ignore for now.
- */
- if ((a->gas_flags & IOMMU_MF_CANSPLIT) != 0) {
- a->size = bs - a->entry->start - a->offset;
- return (true);
+ /* Check for and try to skip past boundary crossing. */
+ if (!vm_addr_bound_ok(start + offset, size, a->common->boundary)) {
+ /*
+ * The start + offset to start + offset + size region crosses
+ * the boundary. Check if there is enough space after the next
+ * boundary after the beg.
+ */
+ first = start;
+ beg = roundup2(start + offset + 1, a->common->boundary);
+ start = roundup2(beg, a->common->alignment);
+
+ if (start + offset + size > end ||
+ !vm_addr_bound_ok(start + offset, size,
+ a->common->boundary)) {
+ /*
+ * Not enough space to align at the requested boundary,
+ * or boundary is smaller than the size, but allowed to
+ * split. We already checked that start + size does not
+ * overlap ubound.
+ *
+ * XXXKIB. It is possible that beg is exactly at the
+ * start of the next entry, then we do not have gap.
+ * Ignore for now.
+ */
+ if ((a->gas_flags & IOMMU_MF_CANSPLIT) == 0)
+ return (false);
+ size = beg - first - offset;
+ start = first;
+ }
}
-
- return (false);
+ entry = a->entry;
+ entry->start = start;
+ entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
+ entry->flags = IOMMU_MAP_ENTRY_MAP;
+ found = iommu_gas_rb_insert(a->domain, entry);
+ KASSERT(found, ("found dup %p start %jx size %jx",
+ a->domain, (uintmax_t)start, (uintmax_t)size));
+ return (true);
}
-static void
-iommu_gas_match_insert(struct iommu_gas_match_args *a)
+/* Find the next entry that might abut a big-enough range. */
+static struct iommu_map_entry *
+iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free)
{
- bool found __diagused;
-
- a->entry->end = a->entry->start +
- roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
-
- found = iommu_gas_rb_insert(a->domain, a->entry);
- KASSERT(found, ("found dup %p start %jx size %jx",
- a->domain, (uintmax_t)a->entry->start, (uintmax_t)a->size));
- a->entry->flags = IOMMU_MAP_ENTRY_MAP;
+ struct iommu_map_entry *next;
+
+ if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
+ next->free_down >= min_free) {
+ /* Find next entry in right subtree. */
+ do
+ curr = next;
+ while ((next = RB_LEFT(curr, rb_entry)) != NULL &&
+ next->free_down >= min_free);
+ } else {
+ /* Find next entry in a left-parent ancestor. */
+ while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
+ curr == RB_RIGHT(next, rb_entry))
+ curr = next;
+ curr = next;
+ }
+ return (curr);
}
static int
-iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry)
+iommu_gas_find_space(struct iommu_gas_match_args *a)
{
- struct iommu_map_entry *first;
- iommu_gaddr_t min_free;
+ struct iommu_domain *domain;
+ struct iommu_map_entry *curr, *first;
+ iommu_gaddr_t addr, min_free;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(a->domain);
+ KASSERT(a->entry->flags == 0,
+ ("dirty entry %p %p", a->domain, a->entry));
/*
* If the subtree doesn't have free space for the requested allocation
@@ -384,121 +403,74 @@ iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *ent
min_free = 2 * IOMMU_PAGE_SIZE +
roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
- /* Find the first entry that could abut a big-enough range. */
+ /*
+ * Find the first entry in the lower region that could abut a big-enough
+ * range.
+ */
+ curr = RB_ROOT(&a->domain->rb_root);
first = NULL;
- while (entry != NULL && entry->free_down >= min_free) {
- first = entry;
- entry = RB_LEFT(entry, rb_entry);
+ while (curr != NULL && curr->free_down >= min_free) {
+ first = curr;
+ curr = RB_LEFT(curr, rb_entry);
}
/*
* Walk the big-enough ranges until one satisfies alignment
* requirements, or violates lowaddr address requirement.
*/
- entry = first;
- while (entry != NULL) {
- if ((first = RB_LEFT(entry, rb_entry)) != NULL &&
- iommu_gas_match_one(a, first->last, entry->start,
- a->common->lowaddr)) {
- iommu_gas_match_insert(a);
+ addr = a->common->lowaddr + 1;
+ for (curr = first; curr != NULL;
+ curr = iommu_gas_next(curr, min_free)) {
+ if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
+ iommu_gas_match_one(a, first->last, curr->start,
+ 0, addr))
return (0);
- }
- if (entry->end >= a->common->lowaddr) {
- /* All remaining ranges >= lowaddr */
+ if (curr->end >= addr) {
+ /* All remaining ranges >= addr */
break;
}
- if ((first = RB_RIGHT(entry, rb_entry)) != NULL &&
- iommu_gas_match_one(a, entry->end, first->first,
- a->common->lowaddr)) {
- iommu_gas_match_insert(a);
+ if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+ iommu_gas_match_one(a, curr->end, first->first,
+ 0, addr))
return (0);
- }
- /* Find the next entry that might abut a big-enough range. */
- if (first != NULL && first->free_down >= min_free) {
- /* Find next entry in right subtree. */
- do
- entry = first;
- while ((first = RB_LEFT(entry, rb_entry)) != NULL &&
- first->free_down >= min_free);
- } else {
- /* Find next entry in a left-parent ancestor. */
- while ((first = RB_PARENT(entry, rb_entry)) != NULL &&
- entry == RB_RIGHT(first, rb_entry))
- entry = first;
- entry = first;
- }
}
- return (ENOMEM);
-}
-
-static int
-iommu_gas_uppermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry)
-{
- struct iommu_map_entry *child;
/*
- * If the subtree doesn't have free space for the requested allocation
- * plus two guard pages, give up.
+ * To resume the search at the start of the upper region, first climb to
+ * the nearest ancestor that spans highaddr. Then find the last entry
+ * before highaddr that could abut a big-enough range.
*/
- if (entry->free_down < 2 * IOMMU_PAGE_SIZE +
- roundup2(a->size + a->offset, IOMMU_PAGE_SIZE))
- return (ENOMEM);
- if (entry->last < a->common->highaddr)
- return (ENOMEM);
- child = RB_LEFT(entry, rb_entry);
- if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
- return (0);
- if (child != NULL && child->last >= a->common->highaddr &&
- iommu_gas_match_one(a, child->last, entry->start,
- a->domain->end)) {
- iommu_gas_match_insert(a);
- return (0);
- }
- child = RB_RIGHT(entry, rb_entry);
- if (child != NULL && entry->end >= a->common->highaddr &&
- iommu_gas_match_one(a, entry->end, child->first,
- a->domain->end)) {
- iommu_gas_match_insert(a);
- return (0);
+ addr = a->common->highaddr;
+ while (curr != NULL && curr->last < addr)
+ curr = RB_PARENT(curr, rb_entry);
+ first = NULL;
+ while (curr != NULL && curr->free_down >= min_free) {
+ if (addr < curr->end)
+ curr = RB_LEFT(curr, rb_entry);
+ else {
+ first = curr;
+ curr = RB_RIGHT(curr, rb_entry);
+ }
}
- if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
- return (0);
- return (ENOMEM);
-}
-
-static int
-iommu_gas_find_space(struct iommu_domain *domain,
- const struct bus_dma_tag_common *common, iommu_gaddr_t size,
- int offset, u_int flags, struct iommu_map_entry *entry)
-{
- struct iommu_gas_match_args a;
- int error;
-
- IOMMU_DOMAIN_ASSERT_LOCKED(domain);
- KASSERT(entry->flags == 0, ("dirty entry %p %p", domain, entry));
- a.domain = domain;
- a.size = size;
- a.offset = offset;
- a.common = common;
- a.gas_flags = flags;
- a.entry = entry;
-
- /* Handle lower region. */
- if (common->lowaddr > 0) {
- error = iommu_gas_lowermatch(&a, RB_ROOT(&domain->rb_root));
- if (error == 0)
+ /*
+ * Walk the remaining big-enough ranges until one satisfies alignment
+ * requirements.
+ */
+ domain = a->domain;
+ for (curr = first; curr != NULL;
+ curr = iommu_gas_next(curr, min_free)) {
+ if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
+ iommu_gas_match_one(a, first->last, curr->start,
+ addr + 1, domain->end))
+ return (0);
+ if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+ iommu_gas_match_one(a, curr->end, first->first,
+ addr + 1, domain->end))
return (0);
- KASSERT(error == ENOMEM,
- ("error %d from iommu_gas_lowermatch", error));
}
- /* Handle upper region. */
- if (common->highaddr >= domain->end)
- return (ENOMEM);
- error = iommu_gas_uppermatch(&a, RB_ROOT(&domain->rb_root));
- KASSERT(error == 0 || error == ENOMEM,
- ("error %d from iommu_gas_uppermatch", error));
- return (error);
+
+ return (ENOMEM);
}
static int
@@ -627,19 +599,25 @@ iommu_gas_map(struct iommu_domain *domain,
const struct bus_dma_tag_common *common, iommu_gaddr_t size, int offset,
u_int eflags, u_int flags, vm_page_t *ma, struct iommu_map_entry **res)
{
+ struct iommu_gas_match_args a;
struct iommu_map_entry *entry;
int error;
KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0,
("invalid flags 0x%x", flags));
+ a.domain = domain;
+ a.size = size;
+ a.offset = offset;
+ a.common = common;
+ a.gas_flags = flags;
entry = iommu_gas_alloc_entry(domain,
(flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);
if (entry == NULL)
return (ENOMEM);
+ a.entry = entry;
IOMMU_DOMAIN_LOCK(domain);
- error = iommu_gas_find_space(domain, common, size, offset, flags,
- entry);
+ error = iommu_gas_find_space(&a);
if (error == ENOMEM) {
IOMMU_DOMAIN_UNLOCK(domain);
iommu_gas_free_entry(domain, entry);