Differential D35390 Diff 111957 sys/dev/iommu/iommu_gas.c

Changeset View

Standalone View

sys/dev/iommu/iommu_gas.c

Show All 29 Lines

#include <sys/cdefs.h>		#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");		__FBSDID("$FreeBSD$");

#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry)		#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry)

#include <sys/param.h>		#include <sys/param.h>
#include <sys/systm.h>		#include <sys/systm.h>
		#include <sys/counter.h>
#include <sys/malloc.h>		#include <sys/malloc.h>
#include <sys/bus.h>		#include <sys/bus.h>
#include <sys/interrupt.h>		#include <sys/interrupt.h>
#include <sys/kernel.h>		#include <sys/kernel.h>
#include <sys/ktr.h>		#include <sys/ktr.h>
#include <sys/lock.h>		#include <sys/lock.h>
#include <sys/proc.h>		#include <sys/proc.h>
#include <sys/rwlock.h>		#include <sys/rwlock.h>
▲ Show 20 Lines • Show All 155 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 COUNTER_U64_DEFINE_EARLY(gas_total);
		SYSCTL_COUNTER_U64(_hw_iommu, OID_AUTO, gas_total, CTLFLAG_RD,
		&gas_total,
		"Sum of gas tree sizes");

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)
{		{

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

		static COUNTER_U64_DEFINE_EARLY(gas_lookup);
		SYSCTL_COUNTER_U64(_hw_iommu, OID_AUTO, gas_lookup, CTLFLAG_RD,
		&gas_lookup,
		"Number of gas node accesses");

/*		/*
* The interval [beg, end) is a free interval between two iommu_map_entries.		* The interval [beg, end) is a free interval between two iommu_map_entries.
* Addresses can be allocated only in the range [lbound, ubound). Try to		* Addresses can be allocated only in the range [lbound, ubound). Try to
* allocate space in the free interval, subject to the conditions expressed by		* allocate space in the free interval, subject to the conditions expressed by
* 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,
▲ Show 20 Lines • Show All 49 Lines • ▼ Show 20 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;
		counter_u64_add(gas_total, a->domain->entries_cnt);
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;

if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&		if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
next->free_down >= min_free) {		next->free_down >= min_free) {
/* Find next entry in right subtree. */		/* Find next entry in right subtree. */
do		do {
		counter_u64_add(gas_lookup, 1);
curr = next;		curr = next;
while ((next = RB_LEFT(curr, rb_entry)) != NULL &&		} while ((next = RB_LEFT(curr, rb_entry)) != NULL &&
next->free_down >= min_free);		next->free_down >= min_free);
} else {		} else {
/* Find next entry in a left-parent ancestor. */		/* Find next entry in a left-parent ancestor. */
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)) {
		counter_u64_add(gas_lookup, 1);
curr = next;		curr = next;
		}
		counter_u64_add(gas_lookup, 1);
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)
{		{
Show All 15 Lines	iommu_gas_find_space(struct iommu_gas_match_args *a)
/*		/*
* 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.
*/		*/
domain = a->domain;		domain = a->domain;
curr = RB_ROOT(&domain->rb_root);		curr = RB_ROOT(&domain->rb_root);
first = NULL;		first = NULL;
while (curr != NULL && curr->free_down >= min_free) {		while (curr != NULL && curr->free_down >= min_free) {
		counter_u64_add(gas_lookup, 1);
first = curr;		first = curr;
curr = RB_LEFT(curr, rb_entry);		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.
*/		*/
Show All 21 Lines	iommu_gas_find_space(struct iommu_gas_match_args *a)
}		}

/*		/*
* 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) {
		counter_u64_add(gas_lookup, 1);
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) {
		counter_u64_add(gas_lookup, 1);
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);
}		}
}		}

▲ Show 20 Lines • Show All 539 Lines • Show Last 20 Lines