Differential D36624 Diff 112367 sys/dev/iommu/iommu_gas.c

Changeset View

Standalone View

sys/dev/iommu/iommu_gas.c

Show First 20 Lines • Show All 203 Lines • ▼ Show 20 Lines	RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
MPASS(entry->free_down == v);		MPASS(entry->free_down == v);
}		}
}		}
#endif		#endif

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)
{		{
		struct iommu_map_entry *nbr;

		/* Removing entry may open a new free gap before domain->start_gap. */
		if (entry->end <= domain->start_gap->end) {
		if (RB_RIGHT(entry, rb_entry) != NULL)
		nbr = iommu_gas_entries_tree_RB_NEXT(entry);
		else if (RB_LEFT(entry, rb_entry) != NULL)
		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…
		nbr = RB_LEFT(entry, rb_entry);
		else
		nbr = RB_PARENT(entry, rb_entry);
		domain->start_gap = nbr;
		}
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 Lines	iommu_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;
RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, 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;
RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);		RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);

		domain->start_gap = end;
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)
Show All 27 Lines	RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
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));
iommu_gas_rb_remove(domain, entry);		iommu_gas_rb_remove(domain, 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;
iommu_gaddr_t size;		iommu_gaddr_t size;
int offset;		int offset;
const struct bus_dma_tag_common *common;		const struct bus_dma_tag_common *common;
u_int gas_flags;		u_int gas_flags;
struct iommu_map_entry *entry;		struct iommu_map_entry *entry;
};		};

/*		/*
▲ Show 20 Lines • Show All 82 Lines • ▼ Show 20 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);
}		}

		/*
		* Address-ordered first-fit search of 'domain' for free space satisfying the
		* conditions of 'a'. The space allocated is at least one page big, and is
		* bounded by guard pages to left and right. The allocated space for 'domain'
		* is described by an rb-tree of map entries at domain->rb_root, and
		* domain->start_gap points a map entry less than or adjacent to the first
		* free-space of size at least 3 pages.
		*/
static int		static int
iommu_gas_find_space(struct iommu_gas_match_args *a)		iommu_gas_find_space(struct iommu_domain *domain,
		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_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(domain);
KASSERT(a->entry->flags == 0,		KASSERT(a->entry->flags == 0,
("dirty entry %p %p", a->domain, a->entry));		("dirty entry %p %p", 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.
/*		/*
		* start_gap may point to an entry adjacent to gaps too small for any
		* new allocation. In that case, advance start_gap to the first free
		* space big enough for a minimum allocation plus two guard pages.
		*/
		min_free = 3 * 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…
		first = domain->start_gap;
		while (first != NULL && first->free_down < min_free)
		first = RB_PARENT(first, rb_entry);
		for (curr = first; curr != NULL;
		curr = iommu_gas_next(curr, min_free)) {
		if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
		first->last + min_free <= curr->start)
		break;
		if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
		curr->end + min_free <= first->first)
		break;
		}
		domain->start_gap = curr;

		/*
* 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);

/*		/* Climb to find a node in the subtree of big-enough ranges. */
* Find the first entry in the lower region that could abut a big-enough
* range.
*/
domain = a->domain;
curr = RB_ROOT(&domain->rb_root);
first = NULL;
while (curr != NULL && curr->free_down >= min_free) {
first = curr;		first = curr;
curr = RB_LEFT(curr, rb_entry);		while (first != NULL && first->free_down < min_free)
}		first = RB_PARENT(first, rb_entry);

/*		/*
* Walk the big-enough ranges until one satisfies alignment		* Walk the big-enough ranges tree 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)) {
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)) {
▲ Show 20 Lines • Show All 303 Lines • ▼ Show 20 Lines
{		{
struct iommu_gas_match_args a;		struct iommu_gas_match_args a;
struct iommu_map_entry *entry;		struct iommu_map_entry *entry;
int error;		int error;

KASSERT((flags & ~(IOMMU_MF_CANWAIT \| IOMMU_MF_CANSPLIT)) == 0,		KASSERT((flags & ~(IOMMU_MF_CANWAIT \| IOMMU_MF_CANSPLIT)) == 0,
("invalid flags 0x%x", flags));		("invalid flags 0x%x", flags));

a.domain = domain;
a.size = size;		a.size = size;
a.offset = offset;		a.offset = offset;
a.common = common;		a.common = common;
a.gas_flags = flags;		a.gas_flags = flags;
entry = iommu_gas_alloc_entry(domain,		entry = iommu_gas_alloc_entry(domain,
(flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);		(flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);
if (entry == NULL)		if (entry == NULL)
return (ENOMEM);		return (ENOMEM);
a.entry = entry;		a.entry = entry;
IOMMU_DOMAIN_LOCK(domain);		IOMMU_DOMAIN_LOCK(domain);
error = iommu_gas_find_space(&a);		error = iommu_gas_find_space(domain, &a);
if (error == ENOMEM) {		if (error == ENOMEM) {
IOMMU_DOMAIN_UNLOCK(domain);		IOMMU_DOMAIN_UNLOCK(domain);
iommu_gas_free_entry(entry);		iommu_gas_free_entry(entry);
return (error);		return (error);
}		}
#ifdef INVARIANTS		#ifdef INVARIANTS
if (iommu_check_free)		if (iommu_check_free)
iommu_gas_check_free(domain);		iommu_gas_check_free(domain);
▲ Show 20 Lines • Show All 243 Lines • Show Last 20 Lines