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

Changeset View

Standalone View

View Options

sys/dev/iommu/iommu_gas.c

Show First 20 Lines • Show All 213 Lines • ▼ Show 20 Linesiommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry)
found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry); found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry);
return (found == NULL); 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 27 Linesiommu_gas_init_domain(struct iommu_domain *domain)
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); iommu_gas_rb_insert(domain, 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); iommu_gas_rb_insert(domain, 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 20 Lines • Show All 66 Lines • ▼ Show 20 Linesiommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg,
} }
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); found = iommu_gas_rb_insert(a->domain, entry);
KASSERT(found, ("found dup %p start %jx size %jx", KASSERT(found, ("found dup %p start %jx size %jx",
a->domain, (uintmax_t)start, (uintmax_t)size)); a->domain, (uintmax_t)start, (uintmax_t)size));
/* The new entry may be a new, greater lower bound on free gaps. */
if (start == a->domain->start_gap->end)
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.
/* Make start_gap the greatest lower bound on free gaps. */
min_free = 3 * IOMMU_PAGE_SIZE;
first = a->domain->start_gap;
while (first != NULL && first->free_down < min_free)
first = RB_PARENT(first, rb_entry);
for (curr = first; curr != NULL;
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…
curr = iommu_gas_next(curr, min_free)) {
if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
first->last < curr->start) {
a->domain->start_gap =
iommu_gas_entries_tree_RB_PREV(first);
break;
}
if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
curr->end < first->first) {
a->domain->start_gap = curr;
break;
}
}
/* /*
* 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);
/* /*
* 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.
*/ */
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)) {
▲ Show 20 Lines • Show All 566 Lines • Show Last 20 Lines