D36624.id111004.diff
No OneTemporary
Actions

Size

13 KB

Referenced Files

None

Subscribers

None

D36624.id111004.diff
View Options

	Index: share/man/man3/tree.3
	===================================================================
	--- share/man/man3/tree.3
	+++ share/man/man3/tree.3
	@@ -97,6 +97,8 @@
	.Nm RB_FOREACH_REVERSE_SAFE ,
	.Nm RB_INIT ,
	.Nm RB_INSERT ,
	+.Nm RB_INSERT_NEXT ,
	+.Nm RB_INSERT_PREV ,
	.Nm RB_REMOVE ,
	.Nm RB_REINSERT ,
	.Nm RB_AUGMENT
	@@ -193,6 +195,10 @@
	.Ft "struct TYPE *"
	.Fn RB_INSERT NAME "RB_HEAD head" "struct TYPE elm"
	.Ft "struct TYPE *"
	+.Fn RB_INSERT_NEXT NAME "RB_HEAD head" "struct TYPE elm" "struct TYPE *next"
	+.Ft "struct TYPE *"
	+.Fn RB_INSERT_PREV NAME "RB_HEAD head" "struct TYPE elm" "struct TYPE *prev"
	+.Ft "struct TYPE *"
	.Fn RB_REMOVE NAME "RB_HEAD head" "struct TYPE elm"
	.Ft "struct TYPE *"
	.Fn RB_REINSERT NAME "RB_HEAD head" "struct TYPE elm"
	@@ -515,6 +521,18 @@
	into the tree.
	.Pp
	The
	+.Fn RB_INSERT_NEXT
	+macro inserts the new element
	+.Fa elm
	+into the tree immediately after a given element.
	+.Pp
	+The
	+.Fn RB_INSERT_PREV
	+macro inserts the new element
	+.Fa elm
	+into the tree immediately before a given element.
	+.Pp
	+The
	.Fn RB_REMOVE
	macro removes the element
	.Fa elm
	Index: sys/dev/iommu/iommu.h
	===================================================================
	--- sys/dev/iommu/iommu.h
	+++ sys/dev/iommu/iommu.h
	@@ -109,6 +109,7 @@
	struct iommu_map_entries_tailq unload_entries; /* (d) Entries to
	unload */
	struct iommu_gas_entries_tree rb_root; /* (d) */
	+ struct iommu_map_entry start_gap; / (d) */
	iommu_gaddr_t end; /* (c) Highest address + 1 in
	the guest AS */
	struct iommu_map_entry first_place, last_place; /* (d) */
	Index: sys/dev/iommu/iommu_gas.c
	===================================================================
	--- sys/dev/iommu/iommu_gas.c
	+++ sys/dev/iommu/iommu_gas.c
	@@ -206,19 +206,16 @@
	}
	#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
	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);
	RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
	}

	@@ -255,13 +252,15 @@
	end->start = domain->end;
	end->end = domain->end;
	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->end = IOMMU_PAGE_SIZE;
	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->last_place = end;
	domain->flags \|= IOMMU_DOMAIN_GAS_INITED;
	@@ -283,7 +282,7 @@
	KASSERT(entry->flags ==
	(IOMMU_MAP_ENTRY_PLACE \| IOMMU_MAP_ENTRY_UNMAPPED),
	("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);

	entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
	@@ -292,15 +291,14 @@
	KASSERT(entry->flags ==
	(IOMMU_MAP_ENTRY_PLACE \| IOMMU_MAP_ENTRY_UNMAPPED),
	("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);

	RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
	entry1) {
	KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
	("non-RMRR entry left %p", domain));
	- RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root,
	- entry);
	+ iommu_gas_rb_remove(domain, entry);
	iommu_gas_free_entry(entry);
	}
	}
	@@ -326,7 +324,6 @@
	{
	struct iommu_map_entry *entry;
	iommu_gaddr_t first, size, start;
	- bool found __diagused;
	int offset;

	/*
	@@ -380,9 +377,9 @@
	entry->start = start;
	entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
	entry->flags = IOMMU_MAP_ENTRY_MAP;
	- found = iommu_gas_rb_insert(a->domain, entry);
	- KASSERT(found, ("found dup %p start %jx size %jx",
	- 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 + 3 * IOMMU_PAGE_SIZE)
	+ a->domain->start_gap = entry;
	return (true);
	}

	@@ -431,32 +428,36 @@
	* Find the first entry in the lower region that could abut a big-enough
	* range.
	*/
	- curr = RB_ROOT(&a->domain->rb_root);
	- first = NULL;
	- while (curr != NULL && curr->free_down >= min_free) {
	- first = curr;
	- curr = RB_LEFT(curr, rb_entry);
	- }
	+ first = a->domain->start_gap;
	+ while (first != NULL && first->free_down < min_free)
	+ first = RB_PARENT(first, rb_entry);

	/*
	* Walk the big-enough ranges until one satisfies alignment
	* requirements, or violates lowaddr address requirement.
	*/
	+ domain = a->domain;
	addr = a->common->lowaddr + 1;
	for (curr = first; curr != NULL;
	curr = iommu_gas_next(curr, min_free)) {
	if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
	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);
	+ }
	if (curr->end >= addr) {
	/* All remaining ranges >= addr */
	break;
	}
	if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
	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);
	+ }
	}

	/*
	@@ -481,17 +482,22 @@
	* Walk the remaining big-enough ranges until one satisfies alignment
	* requirements.
	*/
	- domain = a->domain;
	for (curr = first; curr != NULL;
	curr = iommu_gas_next(curr, min_free)) {
	if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
	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);
	+ }
	if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
	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 (ENOMEM);
	@@ -502,7 +508,6 @@
	u_int flags)
	{
	struct iommu_map_entry next, prev;
	- bool found __diagused;

	IOMMU_DOMAIN_ASSERT_LOCKED(domain);

	@@ -550,14 +555,13 @@
	iommu_gas_rb_remove(domain, prev);
	prev = NULL;
	}
	+ RB_INSERT_PREV(iommu_gas_entries_tree,
	+ &domain->rb_root, next, entry);
	if (next->start < entry->end) {
	iommu_gas_rb_remove(domain, next);
	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)
	entry->flags = IOMMU_MAP_ENTRY_RMRR;

	@@ -647,7 +651,8 @@
	res = entry;
	res->start = entry->end = start;
	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);
	}

	@@ -662,7 +667,8 @@
	r = entry;
	r->end = entry->start = end;
	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);
	}

	Index: sys/sys/tree.h
	===================================================================
	--- sys/sys/tree.h
	+++ sys/sys/tree.h
	@@ -414,12 +414,15 @@
	RB_PROTOTYPE_RANK(name, type, attr) \
	RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
	+ RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \
	RB_PROTOTYPE_INSERT(name, type, attr); \
	RB_PROTOTYPE_REMOVE(name, type, attr); \
	RB_PROTOTYPE_FIND(name, type, attr); \
	RB_PROTOTYPE_NFIND(name, type, attr); \
	RB_PROTOTYPE_NEXT(name, type, attr); \
	+ RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \
	RB_PROTOTYPE_PREV(name, type, attr); \
	+ RB_PROTOTYPE_INSERT_PREV(name, type, attr); \
	RB_PROTOTYPE_MINMAX(name, type, attr); \
	RB_PROTOTYPE_REINSERT(name, type, attr);
	#ifdef _RB_DIAGNOSTIC
	@@ -436,6 +439,9 @@
	struct type , struct type )
	#define RB_PROTOTYPE_REMOVE(name, type, attr) \
	attr struct type name##_RB_REMOVE(struct name , struct type *)
	+#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \
	+ attr struct type name##_RB_INSERT_FINISH(struct name , \
	+ struct type , struct type , struct type )
	#define RB_PROTOTYPE_INSERT(name, type, attr) \
	attr struct type name##_RB_INSERT(struct name , struct type *)
	#define RB_PROTOTYPE_FIND(name, type, attr) \
	@@ -444,8 +450,14 @@
	attr struct type name##_RB_NFIND(struct name , struct type *)
	#define RB_PROTOTYPE_NEXT(name, type, attr) \
	attr struct type name##_RB_NEXT(struct type )
	+#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \
	+ attr struct type name##_RB_INSERT_NEXT(struct name , \
	+ struct type , struct type )
	#define RB_PROTOTYPE_PREV(name, type, attr) \
	attr struct type name##_RB_PREV(struct type )
	+#define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \
	+ attr struct type name##_RB_INSERT_PREV(struct name , \
	+ struct type , struct type )
	#define RB_PROTOTYPE_MINMAX(name, type, attr) \
	attr struct type name##_RB_MINMAX(struct name , int)
	#define RB_PROTOTYPE_REINSERT(name, type, attr) \
	@@ -462,12 +474,15 @@
	RB_GENERATE_RANK(name, type, field, attr) \
	RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
	RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
	+ RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
	RB_GENERATE_INSERT(name, type, field, cmp, attr) \
	RB_GENERATE_REMOVE(name, type, field, attr) \
	RB_GENERATE_FIND(name, type, field, cmp, attr) \
	RB_GENERATE_NFIND(name, type, field, cmp, attr) \
	RB_GENERATE_NEXT(name, type, field, attr) \
	+ RB_GENERATE_INSERT_NEXT(name, type, field, attr) \
	RB_GENERATE_PREV(name, type, field, attr) \
	+ RB_GENERATE_INSERT_PREV(name, type, field, attr) \
	RB_GENERATE_MINMAX(name, type, field, attr) \
	RB_GENERATE_REINSERT(name, type, field, cmp, attr)

	@@ -800,6 +815,29 @@
	return (out); \
	}

	+#define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
	+/* Inserts a node into the RB tree */ \
	+attr struct type * \
	+name##_RB_INSERT_FINISH(struct name head, struct type parent, \
	+ struct type *pptr, struct type elm) \
	+{ \
	+ struct type *tmp = NULL; \
	+ \
	+ RB_SET(elm, parent, field); \
	+ *pptr = elm; \
	+ if (parent != NULL) \
	+ tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
	+ _RB_AUGMENT_WALK(elm, tmp, field); \
	+ if (tmp != NULL) \
	+ /* \
	+ * An element rotated into the search path has a \
	+ * changed subtree, so update augmentation for it if \
	+ * AUGMENT_WALK didn't. \
	+ */ \
	+ RB_AUGMENT_CHECK(tmp); \
	+ return (NULL); \
	+}
	+
	#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
	/* Inserts a node into the RB tree */ \
	attr struct type * \
	@@ -819,19 +857,7 @@
	else \
	return (parent); \
	} \
	- RB_SET(elm, parent, field); \
	- *tmpp = elm; \
	- if (parent != NULL) \
	- tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
	- _RB_AUGMENT_WALK(elm, tmp, field); \
	- if (tmp != NULL) \
	- /* \
	- * An element rotated into the search path has a \
	- * changed subtree, so update augmentation for it if \
	- * AUGMENT_WALK didn't. \
	- */ \
	- RB_AUGMENT_CHECK(tmp); \
	- return (NULL); \
	+ return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \
	}

	#define RB_GENERATE_FIND(name, type, field, cmp, attr) \
	@@ -893,6 +919,22 @@
	return (elm); \
	}

	+#define RB_GENERATE_INSERT_NEXT(name, type, field, attr) \
	+/* Inserts a node into the next position in the RB tree */ \
	+attr struct type * \
	+name##_RB_INSERT_NEXT(struct name *head, \
	+ struct type elm, struct type next) \
	+{ \
	+ struct type *tmp; \
	+ struct type **tmpp = &RB_RIGHT(elm, field); \
	+ \
	+ while ((tmp = *tmpp) != NULL) { \
	+ elm = tmp; \
	+ tmpp = &RB_LEFT(elm, field); \
	+ } \
	+ return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \
	+}
	+
	#define RB_GENERATE_PREV(name, type, field, attr) \
	/* ARGSUSED */ \
	attr struct type * \
	@@ -911,6 +953,22 @@
	return (elm); \
	}

	+#define RB_GENERATE_INSERT_PREV(name, type, field, attr) \
	+/* Inserts a node into the prev position in the RB tree */ \
	+attr struct type * \
	+name##_RB_INSERT_PREV(struct name *head, \
	+ struct type elm, struct type prev) \
	+{ \
	+ struct type *tmp; \
	+ struct type **tmpp = &RB_LEFT(elm, field); \
	+ \
	+ while ((tmp = *tmpp) != NULL) { \
	+ elm = tmp; \
	+ tmpp = &RB_RIGHT(elm, field); \
	+ } \
	+ return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \
	+}
	+
	#define RB_GENERATE_MINMAX(name, type, field, attr) \
	attr struct type * \
	name##_RB_MINMAX(struct name *head, int val) \
	@@ -947,6 +1005,8 @@
	#define RB_INF 1

	#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
	+#define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z)
	+#define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z)
	#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
	#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
	#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)

File Metadata

Mime Type: text/plain
Expires: Sat, Oct 19, 2:09 AM (17 h, 34 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 14241444
Default Alt Text: D36624.id111004.diff (13 KB)

D36624.id111004.diffNo OneTemporaryActions

D36624.id111004.diffView Options

File Metadata

Event Timeline

D36624.id111004.diff
No OneTemporary
Actions

D36624.id111004.diff
View Options