Page MenuHomeFreeBSD
Differential D36624 Diff 110932 sys/dev/iommu/iommu_gas.c

Changeset View

Standalone View

View Options

sys/dev/iommu/iommu_gas.c

Show First 20 Lines • Show All 200 Lines • ▼ Show 20 Lines if (r != NULL) {
v = MAX(v, r->free_down); v = MAX(v, r->free_down);
v = MAX(v, r->first - entry->end); v = MAX(v, r->first - entry->end);
} }
MPASS(entry->free_down == v); MPASS(entry->free_down == v);
} }
} }
#endif #endif
static bool
iommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry)
{
struct iommu_map_entry *found;
found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry);
return (found == NULL);
}
static void static void
iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry) iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry)
{ {
/*
* The predecessor to the removed entry may become the new greatest
* lower bound on free gaps.
*/
if (entry->end <= domain->start_gap->end)
domain->start_gap = iommu_gas_entries_tree_RB_PREV(entry);
kibUnsubmitted
Done
Inline Actions

This expression is in style, but IMO it is too confusing for a reader. Could you please add braces for the inner '?:' expression?

kib: This expression is in style, but IMO it is too confusing for a reader. Could you please add…
RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
} }
struct iommu_domain * struct iommu_domain *
iommu_get_ctx_domain(struct iommu_ctx *ctx) iommu_get_ctx_domain(struct iommu_ctx *ctx)
{ {
return (ctx->domain); return (ctx->domain);
Show All 20 Linesiommu_gas_init_domain(struct iommu_domain *domain)
* free_down, so it will return false to suggest that nothing changed in * free_down, so it will return false to suggest that nothing changed in
* the entry. Thus, inserting the end entry second prevents * the entry. Thus, inserting the end entry second prevents
* augmentation information to be propogated to the begin entry at the * augmentation information to be propogated to the begin entry at the
* tree root. So it is inserted first. * tree root. So it is inserted first.
*/ */
end->start = domain->end; end->start = domain->end;
end->end = domain->end; end->end = domain->end;
end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
iommu_gas_rb_insert(domain, end); RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end);
begin->start = 0; begin->start = 0;
begin->end = IOMMU_PAGE_SIZE; begin->end = IOMMU_PAGE_SIZE;
begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
iommu_gas_rb_insert(domain, begin); RB_INSERT_PREV(iommu_gas_entries_tree,
&domain->rb_root, end, begin);
domain->start_gap = begin;
domain->first_place = begin; domain->first_place = begin;
domain->last_place = end; domain->last_place = end;
domain->flags |= IOMMU_DOMAIN_GAS_INITED; domain->flags |= IOMMU_DOMAIN_GAS_INITED;
IOMMU_DOMAIN_UNLOCK(domain); IOMMU_DOMAIN_UNLOCK(domain);
} }
void void
iommu_gas_fini_domain(struct iommu_domain *domain) iommu_gas_fini_domain(struct iommu_domain *domain)
{ {
struct iommu_map_entry *entry, *entry1; struct iommu_map_entry *entry, *entry1;
IOMMU_DOMAIN_ASSERT_LOCKED(domain); IOMMU_DOMAIN_ASSERT_LOCKED(domain);
KASSERT(domain->entries_cnt == 2, KASSERT(domain->entries_cnt == 2,
("domain still in use %p", domain)); ("domain still in use %p", domain));
entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root); entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root);
KASSERT(entry->start == 0, ("start entry start %p", domain)); KASSERT(entry->start == 0, ("start entry start %p", domain));
KASSERT(entry->end == IOMMU_PAGE_SIZE, ("start entry end %p", domain)); KASSERT(entry->end == IOMMU_PAGE_SIZE, ("start entry end %p", domain));
KASSERT(entry->flags == KASSERT(entry->flags ==
(IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
("start entry flags %p", domain)); ("start entry flags %p", domain));
RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); iommu_gas_rb_remove(domain, entry);
iommu_gas_free_entry(entry); iommu_gas_free_entry(entry);
entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root); entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
KASSERT(entry->start == domain->end, ("end entry start %p", domain)); KASSERT(entry->start == domain->end, ("end entry start %p", domain));
KASSERT(entry->end == domain->end, ("end entry end %p", domain)); KASSERT(entry->end == domain->end, ("end entry end %p", domain));
KASSERT(entry->flags == KASSERT(entry->flags ==
(IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
("end entry flags %p", domain)); ("end entry flags %p", domain));
RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); iommu_gas_rb_remove(domain, entry);
iommu_gas_free_entry(entry); iommu_gas_free_entry(entry);
RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root, RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
entry1) { entry1) {
KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0, KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
("non-RMRR entry left %p", domain)); ("non-RMRR entry left %p", domain));
RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, iommu_gas_rb_remove(domain, entry);
entry);
iommu_gas_free_entry(entry); iommu_gas_free_entry(entry);
} }
} }
struct iommu_gas_match_args { struct iommu_gas_match_args {
struct iommu_domain *domain; struct iommu_domain *domain;
iommu_gaddr_t size; iommu_gaddr_t size;
int offset; int offset;
Show All 9 Lines
* a, and return 'true' if and only if the allocation attempt succeeds. * a, and return 'true' if and only if the allocation attempt succeeds.
*/ */
static bool static bool
iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
iommu_gaddr_t end, iommu_gaddr_t lbound, iommu_gaddr_t ubound) iommu_gaddr_t end, iommu_gaddr_t lbound, iommu_gaddr_t ubound)
{ {
struct iommu_map_entry *entry; struct iommu_map_entry *entry;
iommu_gaddr_t first, size, start; iommu_gaddr_t first, size, start;
bool found __diagused;
int offset; int offset;
/* /*
* The prev->end is always aligned on the page size, which * The prev->end is always aligned on the page size, which
* causes page alignment for the entry->start too. * causes page alignment for the entry->start too.
* *
* Create IOMMU_PAGE_SIZE gaps before, after new entry * Create IOMMU_PAGE_SIZE gaps before, after new entry
* to ensure that out-of-bounds accesses fault. * to ensure that out-of-bounds accesses fault.
Show All 37 Lines if (start + offset + size > end ||
size = beg - first - offset; size = beg - first - offset;
start = first; start = first;
} }
} }
entry = a->entry; entry = a->entry;
entry->start = start; entry->start = start;
entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE); entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
entry->flags = IOMMU_MAP_ENTRY_MAP; entry->flags = IOMMU_MAP_ENTRY_MAP;
found = iommu_gas_rb_insert(a->domain, entry); /* The new entry may be a new, greater lower bound on free gaps. */
KASSERT(found, ("found dup %p start %jx size %jx", if (start <= a->domain->start_gap->end + 3 * IOMMU_PAGE_SIZE)
a->domain, (uintmax_t)start, (uintmax_t)size)); a->domain->start_gap = entry;
return (true); return (true);
} }
/* Find the next entry that might abut a big-enough range. */ /* Find the next entry that might abut a big-enough range. */
static struct iommu_map_entry * static struct iommu_map_entry *
iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free) iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free)
{ {
struct iommu_map_entry *next; struct iommu_map_entry *next;
Show All 10 Lines if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
while ((next = RB_PARENT(curr, rb_entry)) != NULL && while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
curr == RB_RIGHT(next, rb_entry)) curr == RB_RIGHT(next, rb_entry))
curr = next; curr = next;
curr = next; curr = next;
} }
return (curr); return (curr);
} }
static int static int
iommu_gas_find_space(struct iommu_gas_match_args *a) iommu_gas_find_space(struct iommu_gas_match_args *a)
alcUnsubmitted
Not Done
Inline Actions

This function has gotten so complicated that I'd suggest adding a comment at the top that says that it implements an address ordered first fit.

alc: This function has gotten so complicated that I'd suggest adding a comment at the top that says…
{ {
struct iommu_domain *domain; struct iommu_domain *domain;
struct iommu_map_entry *curr, *first; struct iommu_map_entry *curr, *first;
iommu_gaddr_t addr, min_free; iommu_gaddr_t addr, min_free;
IOMMU_DOMAIN_ASSERT_LOCKED(a->domain); IOMMU_DOMAIN_ASSERT_LOCKED(a->domain);
KASSERT(a->entry->flags == 0, KASSERT(a->entry->flags == 0,
("dirty entry %p %p", a->domain, a->entry)); ("dirty entry %p %p", a->domain, a->entry));
alcUnsubmitted
Not Done
Inline Actions

Might as well move this up so the above asserts can use it.

alc: Might as well move this up so the above asserts can use it.
/* /*
* If the subtree doesn't have free space for the requested allocation * If the subtree doesn't have free space for the requested allocation
* plus two guard pages, skip it. * plus two guard pages, skip it.
*/ */
min_free = 2 * IOMMU_PAGE_SIZE + min_free = 2 * IOMMU_PAGE_SIZE +
roundup2(a->size + a->offset, IOMMU_PAGE_SIZE); roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
kibUnsubmitted
Done
Inline Actions

Should a->size somehow participate in the expression for min_free?

kib: Should a->size somehow participate in the expression for min_free?
dougmAuthorUnsubmitted
Done
Inline Actions

The value of start_gap is adjusted for the smallest possible allocation, not for this particular (possibly larger) allocation.

dougm: The value of start_gap is adjusted for the smallest possible allocation, not for this…
/* /*
* Find the first entry in the lower region that could abut a big-enough * Find the first entry in the lower region that could abut a big-enough
* range. * range.
*/ */
curr = RB_ROOT(&a->domain->rb_root); first = a->domain->start_gap;
first = NULL; while (first != NULL && first->free_down < min_free)
while (curr != NULL && curr->free_down >= min_free) { first = RB_PARENT(first, rb_entry);
first = curr;
curr = RB_LEFT(curr, rb_entry);
}
/* /*
* Walk the big-enough ranges until one satisfies alignment * Walk the big-enough ranges until one satisfies alignment
* requirements, or violates lowaddr address requirement. * requirements, or violates lowaddr address requirement.
*/ */
domain = a->domain;
addr = a->common->lowaddr + 1; addr = a->common->lowaddr + 1;
for (curr = first; curr != NULL; for (curr = first; curr != NULL;
curr = iommu_gas_next(curr, min_free)) { curr = iommu_gas_next(curr, min_free)) {
if ((first = RB_LEFT(curr, rb_entry)) != NULL && if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
iommu_gas_match_one(a, first->last, curr->start, iommu_gas_match_one(a, first->last, curr->start,
0, addr)) 0, addr)) {
RB_INSERT_PREV(iommu_gas_entries_tree,
&domain->rb_root, curr, a->entry);
return (0); return (0);
}
if (curr->end >= addr) { if (curr->end >= addr) {
/* All remaining ranges >= addr */ /* All remaining ranges >= addr */
break; break;
} }
if ((first = RB_RIGHT(curr, rb_entry)) != NULL && if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
iommu_gas_match_one(a, curr->end, first->first, iommu_gas_match_one(a, curr->end, first->first,
0, addr)) 0, addr)) {
RB_INSERT_NEXT(iommu_gas_entries_tree,
&domain->rb_root, curr, a->entry);
return (0); return (0);
} }
}
/* /*
* To resume the search at the start of the upper region, first climb to * 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 * the nearest ancestor that spans highaddr. Then find the last entry
* before highaddr that could abut a big-enough range. * before highaddr that could abut a big-enough range.
*/ */
addr = a->common->highaddr; addr = a->common->highaddr;
while (curr != NULL && curr->last < addr) while (curr != NULL && curr->last < addr)
curr = RB_PARENT(curr, rb_entry); curr = RB_PARENT(curr, rb_entry);
first = NULL; first = NULL;
while (curr != NULL && curr->free_down >= min_free) { while (curr != NULL && curr->free_down >= min_free) {
if (addr < curr->end) if (addr < curr->end)
curr = RB_LEFT(curr, rb_entry); curr = RB_LEFT(curr, rb_entry);
else { else {
first = curr; first = curr;
curr = RB_RIGHT(curr, rb_entry); curr = RB_RIGHT(curr, rb_entry);
} }
} }
/* /*
* Walk the remaining big-enough ranges until one satisfies alignment * Walk the remaining big-enough ranges until one satisfies alignment
* requirements. * requirements.
*/ */
domain = a->domain;
for (curr = first; curr != NULL; for (curr = first; curr != NULL;
curr = iommu_gas_next(curr, min_free)) { curr = iommu_gas_next(curr, min_free)) {
if ((first = RB_LEFT(curr, rb_entry)) != NULL && if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
iommu_gas_match_one(a, first->last, curr->start, iommu_gas_match_one(a, first->last, curr->start,
addr + 1, domain->end)) addr + 1, domain->end)) {
RB_INSERT_PREV(iommu_gas_entries_tree,
&domain->rb_root, curr, a->entry);
return (0); return (0);
}
if ((first = RB_RIGHT(curr, rb_entry)) != NULL && if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
iommu_gas_match_one(a, curr->end, first->first, iommu_gas_match_one(a, curr->end, first->first,
addr + 1, domain->end)) addr + 1, domain->end)) {
RB_INSERT_NEXT(iommu_gas_entries_tree,
&domain->rb_root, curr, a->entry);
return (0); return (0);
} }
}
return (ENOMEM); return (ENOMEM);
} }
static int static int
iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entry, iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entry,
u_int flags) u_int flags)
{ {
struct iommu_map_entry *next, *prev; struct iommu_map_entry *next, *prev;
bool found __diagused;
IOMMU_DOMAIN_ASSERT_LOCKED(domain); IOMMU_DOMAIN_ASSERT_LOCKED(domain);
if ((entry->start & IOMMU_PAGE_MASK) != 0 || if ((entry->start & IOMMU_PAGE_MASK) != 0 ||
(entry->end & IOMMU_PAGE_MASK) != 0) (entry->end & IOMMU_PAGE_MASK) != 0)
return (EINVAL); return (EINVAL);
if (entry->start >= entry->end) if (entry->start >= entry->end)
return (EINVAL); return (EINVAL);
Show All 31 Linesiommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entry,
if (entry->end == entry->start) if (entry->end == entry->start)
return (0); return (0);
if (prev != NULL && prev->end > entry->start) { if (prev != NULL && prev->end > entry->start) {
/* This assumes that prev is the placeholder entry. */ /* This assumes that prev is the placeholder entry. */
iommu_gas_rb_remove(domain, prev); iommu_gas_rb_remove(domain, prev);
prev = NULL; prev = NULL;
} }
RB_INSERT_PREV(iommu_gas_entries_tree,
&domain->rb_root, next, entry);
if (next->start < entry->end) { if (next->start < entry->end) {
iommu_gas_rb_remove(domain, next); iommu_gas_rb_remove(domain, next);
next = NULL; next = NULL;
} }
found = iommu_gas_rb_insert(domain, entry);
KASSERT(found, ("found RMRR dup %p start %jx end %jx",
domain, (uintmax_t)entry->start, (uintmax_t)entry->end));
if ((flags & IOMMU_MF_RMRR) != 0) if ((flags & IOMMU_MF_RMRR) != 0)
entry->flags = IOMMU_MAP_ENTRY_RMRR; entry->flags = IOMMU_MAP_ENTRY_RMRR;
#ifdef INVARIANTS #ifdef INVARIANTS
struct iommu_map_entry *ip, *in; struct iommu_map_entry *ip, *in;
ip = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, entry); ip = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, entry);
in = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root, entry); in = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root, entry);
KASSERT(prev == NULL || ip == prev, KASSERT(prev == NULL || ip == prev,
▲ Show 20 Lines • Show All 73 Lines • ▼ Show 20 Lines if (entry->start >= start ||
(entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0)
return (entry); return (entry);
res = *r; res = *r;
*r = NULL; *r = NULL;
*res = *entry; *res = *entry;
res->start = entry->end = start; res->start = entry->end = start;
RB_UPDATE_AUGMENT(entry, rb_entry); RB_UPDATE_AUGMENT(entry, rb_entry);
iommu_gas_rb_insert(domain, res); RB_INSERT_NEXT(iommu_gas_entries_tree,
&domain->rb_root, entry, res);
return (res); return (res);
} }
static bool static bool
iommu_gas_remove_clip_right(struct iommu_domain *domain, iommu_gas_remove_clip_right(struct iommu_domain *domain,
iommu_gaddr_t end, struct iommu_map_entry *entry, iommu_gaddr_t end, struct iommu_map_entry *entry,
struct iommu_map_entry *r) struct iommu_map_entry *r)
{ {
if (entry->start >= end || (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) if (entry->start >= end || (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0)
return (false); return (false);
*r = *entry; *r = *entry;
r->end = entry->start = end; r->end = entry->start = end;
RB_UPDATE_AUGMENT(entry, rb_entry); RB_UPDATE_AUGMENT(entry, rb_entry);
iommu_gas_rb_insert(domain, r); RB_INSERT_PREV(iommu_gas_entries_tree,
&domain->rb_root, entry, r);
return (true); return (true);
} }
static void static void
iommu_gas_remove_unmap(struct iommu_domain *domain, iommu_gas_remove_unmap(struct iommu_domain *domain,
struct iommu_map_entry *entry, struct iommu_map_entries_tailq *gcp) struct iommu_map_entry *entry, struct iommu_map_entries_tailq *gcp)
{ {
IOMMU_DOMAIN_ASSERT_LOCKED(domain); IOMMU_DOMAIN_ASSERT_LOCKED(domain);
▲ Show 20 Lines • Show All 340 Lines • Show Last 20 Lines