Changeset View
Changeset View
Standalone View
Standalone View
sys/dev/iommu/iommu_gas.c
Show First 20 Lines • Show All 199 Lines • ▼ Show 20 Lines | iommu_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); | |||||
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 17 Lines | iommu_gas_init_domain(struct iommu_domain *domain) | ||||
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); | ||||
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); | iommu_gas_rb_insert(domain, end); | ||||
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 Lines | iommu_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) | ||||
Not Done Inline ActionsThis 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)); | ||||
Not Done Inline ActionsMight 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. */ | |||||
first = a->domain->start_gap; | |||||
while (first != NULL && first->free_down == 0) | |||||
first = RB_PARENT(first, rb_entry); | |||||
for (curr = first; curr != NULL; | |||||
curr = iommu_gas_next(curr, 1)) { | |||||
Done Inline ActionsShould a->size somehow participate in the expression for min_free? kib: Should a->size somehow participate in the expression for min_free? | |||||
Done Inline ActionsThe 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… | |||||
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 |
This expression is in style, but IMO it is too confusing for a reader. Could you please add braces for the inner '?:' expression?