The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=e0e8d0c8d69459c7128e6fd4fb537892445ce710
commit e0e8d0c8d69459c7128e6fd4fb537892445ce710 Author: Doug Moore <[email protected]> AuthorDate: 2022-07-10 19:24:23 +0000 Commit: Doug Moore <[email protected]> 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);
