Page MenuHomeFreeBSD
Files F107086741

D35440.id107940.diff
No OneTemporary
Actions

D35440.id107940.diff
View Options

Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -292,15 +292,18 @@
/*
* 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.
+ * minaddr is a lower bound on addresses that can be allocated. 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;
+ iommu_gaddr_t first, size, start;
+ bool found __diagused;
+ int offset = a->offset;
/*
* The prev->end is always aligned on the page size, which
@@ -309,196 +312,168 @@
* A page sized gap is created between consecutive
* allocations 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)
- 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)
- return (false);
- /* No boundary crossing. */
- if (vm_addr_bound_ok(a->entry->start + a->offset, a->size,
- a->common->boundary))
- return (true);
+ /* IOMMU_PAGE_SIZE to create gaps before, after new entry. */
+ beg = MAX(beg + IOMMU_PAGE_SIZE, lbound);
+ end = MIN(end - IOMMU_PAGE_SIZE, ubound);
+ first = start = roundup2(beg, a->common->alignment);
- /*
- * 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);
- }
+ size = a->size;
+ if (start < beg || start + size + offset > end)
+ return (false);
- /*
- * 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.
+ */
+ 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);
+ a->entry->start = start;
+ a->entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
+ a->entry->flags = IOMMU_MAP_ENTRY_MAP;
+ found = iommu_gas_rb_insert(a->domain, a->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 *entry, iommu_gaddr_t min_free)
{
- bool found __diagused;
-
- a->entry->end = a->entry->start +
- roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
+ struct iommu_map_entry *first;
- 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;
+ if ((first = RB_RIGHT(entry, rb_entry)) != 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 (entry);
}
static int
-iommu_gas_lowermatch(struct iommu_gas_match_args *a, struct iommu_map_entry *entry)
+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_map_entry *first;
+ struct iommu_gas_match_args a;
+ struct iommu_map_entry *curr, *first;
iommu_gaddr_t min_free;
+ 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;
+
/*
* If the subtree doesn't have free space for the requested allocation
* plus two guard pages, skip it.
*/
min_free = 2 * IOMMU_PAGE_SIZE +
- roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
+ roundup2(size + 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(&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);
+ 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, common->lowaddr + 1))
return (0);
- }
- if (entry->end >= a->common->lowaddr) {
- /* All remaining ranges >= lowaddr */
+ if (curr->end > common->lowaddr) {
+ /* All remaining ranges > lowaddr */
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, common->lowaddr + 1))
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);
+ while (curr != NULL && curr->last < common->highaddr)
+ curr = RB_PARENT(curr, rb_entry);
+ first = NULL;
+ while (curr != NULL && curr->free_down >= min_free) {
+ if (common->highaddr < 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.
+ */
+ 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,
+ common->highaddr + 1, domain->end))
+ return (0);
+ if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+ iommu_gas_match_one(&a, curr->end, first->first,
+ common->highaddr + 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

File Metadata

Mime Type
text/plain
Expires
Fri, Jan 10, 9:54 PM (15 h, 55 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
15747064
Default Alt Text
D35440.id107940.diff (11 KB)

Event Timeline