D21964.id64840.diff
No OneTemporary
Actions

Size

25 KB

Referenced Files

None

Subscribers

None

D21964.id64840.diff
View Options

	Index: sys/vm/vm_map.h
	===================================================================
	--- sys/vm/vm_map.h
	+++ sys/vm/vm_map.h
	@@ -99,10 +99,8 @@
	* Also included is control information for virtual copy operations.
	*/
	struct vm_map_entry {
	- struct vm_map_entry prev; / previous entry */
	- struct vm_map_entry next; / next entry */
	- struct vm_map_entry left; / left child in binary search tree */
	- struct vm_map_entry right; / right child in binary search tree */
	+ struct vm_map_entry left; / left child or previous entry */
	+ struct vm_map_entry right; / right child or next entry */
	vm_offset_t start; /* start address */
	vm_offset_t end; /* end address */
	vm_offset_t next_read; /* vaddr of the next sequential read */
	@@ -424,14 +422,21 @@
	vm_map_entry_first(vm_map_t map)
	{

	- return (map->header.next);
	+ return (map->header.right);
	}

	static inline vm_map_entry_t
	vm_map_entry_succ(vm_map_entry_t entry)
	{
	+ vm_map_entry_t after;

	- return (entry->next);
	+ after = entry->right;
	+ if (after->left->start > entry->start) {
	+ do
	+ after = after->left;
	+ while (after->left != entry);
	+ }
	+ return (after);
	}

	#define VM_MAP_ENTRY_FOREACH(it, map) \
	Index: sys/vm/vm_map.c
	===================================================================
	--- sys/vm/vm_map.c
	+++ sys/vm/vm_map.c
	@@ -885,7 +885,6 @@
	_vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
	{

	- map->header.next = map->header.prev = &map->header;
	map->header.eflags = MAP_ENTRY_HEADER;
	map->needs_wakeup = FALSE;
	map->system_map = 0;
	@@ -893,6 +892,7 @@
	map->header.end = min;
	map->header.start = max;
	map->flags = 0;
	+ map->header.left = map->header.right = &map->header;
	map->root = NULL;
	map->timestamp = 0;
	map->busy = 0;
	@@ -955,6 +955,12 @@
	(behavior & MAP_ENTRY_BEHAV_MASK);
	}

	+static inline vm_size_t
	+vm_size_max(vm_size_t a, vm_size_t b)
	+{
	+ return (a > b) ? a : b;
	+}
	+
	/*
	* vm_map_entry_max_free_{left,right}:
	*
	@@ -966,7 +972,7 @@
	vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
	{

	- return (root->left != NULL ?
	+ return (root->left != left_ancestor ?
	root->left->max_free : root->start - left_ancestor->end);
	}

	@@ -974,7 +980,7 @@
	vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
	{

	- return (root->right != NULL ?
	+ return (root->right != right_ancestor ?
	root->right->max_free : right_ancestor->start - root->end);
	}

	@@ -987,13 +993,20 @@
	static inline vm_map_entry_t
	vm_map_entry_pred(vm_map_entry_t entry)
	{
	+ vm_map_entry_t prior;

	- return (entry->prev);
	+ prior = entry->left;
	+ if (prior->right->start < entry->start) {
	+ do
	+ prior = prior->right;
	+ while (prior->right != entry);
	+ }
	+ return (prior);
	}

	/* vm_map_entry_succ is defined in vm_map.h. */

	-#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
	+#define SPLAY_LEFT_STEP(root, y, llist, rlist, found, test) do { \
	vm_size_t max_free; \
	\
	/* \
	@@ -1005,14 +1018,17 @@
	max_free = root->max_free; \
	KASSERT(max_free >= vm_map_entry_max_free_right(root, rlist), \
	("%s: max_free invariant fails", __func__)); \
	- if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
	+ if (y == llist ? max_free > 0 : max_free - 1 < y->max_free) \
	max_free = vm_map_entry_max_free_right(root, rlist); \
	- if (y != NULL && (test)) { \
	+ if (y != llist && (test)) { \
	/* Rotate right and make y root. */ \
	- root->left = y->right; \
	- y->right = root; \
	+ if (y->right != root) { \
	+ root->left = y->right; \
	+ y->right = root; \
	+ } \
	if (max_free < y->max_free) \
	- root->max_free = max_free = MAX(max_free, \
	+ root->max_free = max_free = \
	+ vm_size_max(max_free, \
	vm_map_entry_max_free_left(root, y)); \
	root = y; \
	y = root->left; \
	@@ -1024,9 +1040,10 @@
	root->left = rlist; \
	rlist = root; \
	root = y; \
	+ found = root != llist; \
	} while (0)

	-#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
	+#define SPLAY_RIGHT_STEP(root, y, llist, rlist, found, test) do { \
	vm_size_t max_free; \
	\
	/* \
	@@ -1038,14 +1055,17 @@
	max_free = root->max_free; \
	KASSERT(max_free >= vm_map_entry_max_free_left(root, llist), \
	("%s: max_free invariant fails", __func__)); \
	- if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
	+ if (y == rlist ? max_free > 0 : max_free - 1 < y->max_free) \
	max_free = vm_map_entry_max_free_left(root, llist); \
	- if (y != NULL && (test)) { \
	+ if (y != rlist && (test)) { \
	/* Rotate left and make y root. */ \
	- root->right = y->left; \
	- y->left = root; \
	+ if (y->left != root) { \
	+ root->right = y->left; \
	+ y->left = root; \
	+ } \
	if (max_free < y->max_free) \
	- root->max_free = max_free = MAX(max_free, \
	+ root->max_free = max_free = \
	+ vm_size_max(max_free, \
	vm_map_entry_max_free_right(root, y)); \
	root = y; \
	y = root->right; \
	@@ -1057,67 +1077,65 @@
	root->right = llist; \
	llist = root; \
	root = y; \
	+ found = root != rlist; \
	} while (0)

	/*
	- * Walk down the tree until we find addr or a NULL pointer where addr would go,
	- * breaking off left and right subtrees of nodes less than, or greater than
	- * addr. Treat pointers to nodes with max_free < length as NULL pointers.
	- * llist and rlist are the two sides in reverse order (bottom-up), with llist
	- * linked by the right pointer and rlist linked by the left pointer in the
	- * vm_map_entry, and both lists terminated by &map->header. This function, and
	- * the subsequent call to vm_map_splay_merge, rely on the start and end address
	- * values in &map->header.
	+ * Walk down the tree until we find addr or a gap where addr would go, breaking
	+ * off left and right subtrees of nodes less than, or greater than addr. Treat
	+ * subtrees with root->max_free < length as empty trees. llist and rlist are
	+ * the two sides in reverse order (bottom-up), with llist linked by the right
	+ * pointer and rlist linked by the left pointer in the vm_map_entry, and both
	+ * lists terminated by &map->header. This function, and the subsequent call to
	+ * vm_map_splay_merge_{left,right}, rely on the start and end address values in
	+ * &map->header.
	*/
	-static vm_map_entry_t
	-vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length,
	- vm_map_entry_t out_llist, vm_map_entry_t out_rlist)
	-{
	- vm_map_entry_t llist, rlist, root, y;
	+#define VM_MAP_SPLAY_SPLIT(map, addr, length, root, llist, rlist, found)\
	+do { \
	+ vm_map_entry_t y; \
	+ \
	+ llist = rlist = &map->header; \
	+ root = map->root; \
	+ found = root != NULL; \
	+ while (found && root->max_free >= length) { \
	+ KASSERT(llist->end <= root->start && \
	+ root->end <= rlist->start, \
	+ ("%s: root not within tree bounds", __func__)); \
	+ if (addr < root->start) { \
	+ SPLAY_LEFT_STEP(root, y, llist, rlist, found, \
	+ y->max_free >= length && addr < y->start); \
	+ } else if (addr >= root->end) { \
	+ SPLAY_RIGHT_STEP(root, y, llist, rlist, found, \
	+ y->max_free >= length && addr >= y->end); \
	+ } else \
	+ break; \
	+ } \
	+} while (0)

	- llist = rlist = &map->header;
	- root = map->root;
	- while (root != NULL && root->max_free >= length) {
	- KASSERT(llist->end <= root->start && root->end <= rlist->start,
	- ("%s: root not within tree bounds", __func__));
	- if (addr < root->start) {
	- SPLAY_LEFT_STEP(root, y, rlist,
	- y->max_free >= length && addr < y->start);
	- } else if (addr >= root->end) {
	- SPLAY_RIGHT_STEP(root, y, llist,
	- y->max_free >= length && addr >= y->end);
	- } else
	- break;
	- }
	- *out_llist = llist;
	- *out_rlist = rlist;
	- return (root);
	-}
	+#define VM_MAP_SPLAY_FINDNEXT(root, rlist) do { \
	+ vm_map_entry_t hi, y; \
	+ bool found; \
	+ \
	+ hi = root->right; \
	+ if (hi == rlist) \
	+ break; \
	+ do \
	+ SPLAY_LEFT_STEP(hi, y, root, rlist, found, true); \
	+ while (found); \
	+} while (0)

	-static void
	-vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist)
	-{
	- vm_map_entry_t rlist, y;
	+#define VM_MAP_SPLAY_FINDPREV(root, llist) do { \
	+ vm_map_entry_t lo, y; \
	+ bool found; \
	+ \
	+ lo = root->left; \
	+ if (lo == llist) \
	+ break; \
	+ do \
	+ SPLAY_RIGHT_STEP(lo, y, llist, root, found, true); \
	+ while (found); \
	+} while (0)

	- root = root->right;
	- rlist = *iolist;
	- while (root != NULL)
	- SPLAY_LEFT_STEP(root, y, rlist, true);
	- *iolist = rlist;
	-}
	-
	-static void
	-vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist)
	-{
	- vm_map_entry_t llist, y;
	-
	- root = root->left;
	- llist = *iolist;
	- while (root != NULL)
	- SPLAY_RIGHT_STEP(root, y, llist, true);
	- *iolist = llist;
	-}
	-
	static inline void
	vm_map_entry_swap(vm_map_entry_t a, vm_map_entry_t b)
	{
	@@ -1132,50 +1150,120 @@
	* Walk back up the two spines, flip the pointers and set max_free. The
	* subtrees of the root go at the bottom of llist and rlist.
	*/
	-static void
	-vm_map_splay_merge(vm_map_t map, vm_map_entry_t root,
	- vm_map_entry_t llist, vm_map_entry_t rlist)
	+static vm_size_t
	+vm_map_splay_merge_left_walk(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t llist)
	{
	- vm_map_entry_t prev;
	- vm_size_t max_free_left, max_free_right;
	+ do {
	+ /*
	+ * The max_free values of the children of llist are in
	+ * llist->max_free and max_free. Update with the
	+ * max value.
	+ */
	+ llist->max_free = max_free =
	+ vm_size_max(llist->max_free, max_free);
	+ vm_map_entry_swap(&llist->right, &tail);
	+ vm_map_entry_swap(&tail, &llist);
	+ } while (llist != &map->header);
	+ root->left = tail;
	+ return (max_free);
	+}

	- max_free_left = vm_map_entry_max_free_left(root, llist);
	+/*
	+ * When llist is known to be the predecessor of root.
	+ */
	+static inline vm_size_t
	+vm_map_splay_merge_pred(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t llist)
	+{
	+ vm_size_t max_free;
	+
	+ max_free = root->start - llist->end;
	+ if (llist != &map->header)
	+ max_free = vm_map_splay_merge_left_walk(map, root,
	+ root, max_free, llist);
	+ else {
	+ root->left = llist;
	+ llist->right = root;
	+ }
	+ return (max_free);
	+}
	+
	+/*
	+ * When llist may or may not be the predecessor of root.
	+ */
	+static inline vm_size_t
	+vm_map_splay_merge_left(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t llist)
	+{
	+ vm_size_t max_free;
	+
	+ max_free = vm_map_entry_max_free_left(root, llist);
	if (llist != &map->header) {
	- prev = root->left;
	- do {
	- /*
	- * The max_free values of the children of llist are in
	- * llist->max_free and max_free_left. Update with the
	- * max value.
	- */
	- llist->max_free = max_free_left =
	- MAX(llist->max_free, max_free_left);
	- vm_map_entry_swap(&llist->right, &prev);
	- vm_map_entry_swap(&prev, &llist);
	- } while (llist != &map->header);
	- root->left = prev;
	+ max_free = vm_map_splay_merge_left_walk(map, root,
	+ root->left == llist ? root : root->left,
	+ max_free, llist);
	+ } else if (root->left == llist)
	+ llist->right = root;
	+ return (max_free);
	+}
	+
	+static vm_size_t
	+vm_map_splay_merge_right_walk(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t rlist)
	+{
	+ do {
	+ /*
	+ * The max_free values of the children of rlist are in
	+ * rlist->max_free and max_free. Update with the
	+ * max value.
	+ */
	+ rlist->max_free = max_free =
	+ vm_size_max(rlist->max_free, max_free);
	+ vm_map_entry_swap(&rlist->left, &tail);
	+ vm_map_entry_swap(&tail, &rlist);
	+ } while (rlist != &map->header);
	+ root->right = tail;
	+ return (max_free);
	+}
	+
	+/*
	+ * When rlist is known to be the succecessor of root.
	+ */
	+static inline vm_size_t
	+vm_map_splay_merge_succ(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t rlist)
	+{
	+ vm_size_t max_free;
	+
	+ max_free = rlist->start - root->end;
	+ if (rlist != &map->header) {
	+ max_free = vm_map_splay_merge_right_walk(map, root,
	+ root, max_free, rlist);
	+ } else {
	+ root->right = rlist;
	+ rlist->left = root;
	}
	- max_free_right = vm_map_entry_max_free_right(root, rlist);
	+ return (max_free);
	+}
	+
	+/*
	+ * When rlist may or may not be the succecessor of root.
	+ */
	+static inline vm_size_t
	+vm_map_splay_merge_right(vm_map_t map, vm_map_entry_t root,
	+ vm_map_entry_t rlist)
	+{
	+ vm_size_t max_free;
	+
	+ max_free = vm_map_entry_max_free_right(root, rlist);
	if (rlist != &map->header) {
	- prev = root->right;
	- do {
	- /*
	- * The max_free values of the children of rlist are in
	- * rlist->max_free and max_free_right. Update with the
	- * max value.
	- */
	- rlist->max_free = max_free_right =
	- MAX(rlist->max_free, max_free_right);
	- vm_map_entry_swap(&rlist->left, &prev);
	- vm_map_entry_swap(&prev, &rlist);
	- } while (rlist != &map->header);
	- root->right = prev;
	- }
	- root->max_free = MAX(max_free_left, max_free_right);
	- map->root = root;
	-#ifdef DIAGNOSTIC
	- ++map->nupdates;
	-#endif
	+ max_free = vm_map_splay_merge_right_walk(map, root,
	+ root->right == rlist ? root : root->right,
	+ max_free, rlist);
	+ } else if (root->right == rlist)
	+ rlist->left = root;
	+ return (max_free);
	}

	/*
	@@ -1188,6 +1276,14 @@
	* the pointers and compute max_free. The time bound is O(log n)
	* amortized.
	*
	+ * The tree is threaded, which means that there are no null pointers.
	+ * When a node has no left child, its left pointer points to its
	+ * predecessor, which the last ancestor on the search path from the root
	+ * where the search branched right. Likewise, when a node has no right
	+ * child, its right pointer points to its successor. The map header node
	+ * is the predecessor of the first map entry, and the successor of the
	+ * last.
	+ *
	* The new root is the vm_map_entry containing "addr", or else an
	* adjacent entry (lower if possible) if addr is not in the tree.
	*
	@@ -1199,10 +1295,13 @@
	vm_map_splay(vm_map_t map, vm_offset_t addr)
	{
	vm_map_entry_t llist, rlist, root;
	+ vm_size_t max_free_left, max_free_right;
	+ bool found;

	- root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
	- if (root != NULL) {
	- /* do nothing */
	+ VM_MAP_SPLAY_SPLIT(map, addr, 0, root, llist, rlist, found);
	+ if (found) {
	+ max_free_left = vm_map_splay_merge_left(map, root, llist);
	+ max_free_right = vm_map_splay_merge_right(map, root, rlist);
	} else if (llist != &map->header) {
	/*
	* Recover the greatest node in the left
	@@ -1210,7 +1309,8 @@
	*/
	root = llist;
	llist = root->right;
	- root->right = NULL;
	+ max_free_left = vm_map_splay_merge_left(map, root, llist);
	+ max_free_right = vm_map_splay_merge_succ(map, root, rlist);
	} else if (rlist != &map->header) {
	/*
	* Recover the least node in the right
	@@ -1218,12 +1318,14 @@
	*/
	root = rlist;
	rlist = root->left;
	- root->left = NULL;
	+ max_free_left = vm_map_splay_merge_pred(map, root, llist);
	+ max_free_right = vm_map_splay_merge_right(map, root, rlist);
	} else {
	/* There is no root. */
	return (NULL);
	}
	- vm_map_splay_merge(map, root, llist, rlist);
	+ root->max_free = vm_size_max(max_free_left, max_free_right);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	return (root);
	}
	@@ -1237,20 +1339,21 @@
	vm_map_entry_link(vm_map_t map, vm_map_entry_t entry)
	{
	vm_map_entry_t llist, rlist, root;
	+ bool found;

	CTR3(KTR_VM,
	"vm_map_entry_link: map %p, nentries %d, entry %p", map,
	map->nentries, entry);
	VM_MAP_ASSERT_LOCKED(map);
	map->nentries++;
	- root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
	- KASSERT(root == NULL,
	+ VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
	+ KASSERT(!found,
	("vm_map_entry_link: link object already mapped"));
	- entry->prev = llist;
	- entry->next = rlist;
	- llist->next = rlist->prev = entry;
	- entry->left = entry->right = NULL;
	- vm_map_splay_merge(map, entry, llist, rlist);
	+ root = entry;
	+ root->max_free = vm_size_max(
	+ vm_map_splay_merge_pred(map, root, llist),
	+ vm_map_splay_merge_succ(map, root, rlist));
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	}

	@@ -1263,44 +1366,38 @@
	vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry,
	enum unlink_merge_type op)
	{
	- vm_map_entry_t llist, rlist, root, y;
	+ vm_map_entry_t llist, rlist, root;
	+ vm_size_t max_free_left, max_free_right;
	+ bool found;

	VM_MAP_ASSERT_LOCKED(map);
	- root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
	- KASSERT(root != NULL,
	+ VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
	+ KASSERT(found,
	("vm_map_entry_unlink: unlink object not mapped"));

	- vm_map_splay_findnext(root, &rlist);
	- switch (op) {
	- case UNLINK_MERGE_NEXT:
	+ VM_MAP_SPLAY_FINDPREV(root, llist);
	+ VM_MAP_SPLAY_FINDNEXT(root, rlist);
	+ if (op == UNLINK_MERGE_NEXT) {
	rlist->start = root->start;
	rlist->offset = root->offset;
	- y = root->left;
	+ }
	+ if (llist != &map->header) {
	+ root = llist;
	+ llist = root->right;
	+ max_free_left = vm_map_splay_merge_left(map, root, llist);
	+ max_free_right = vm_map_splay_merge_succ(map, root, rlist);
	+ } else if (rlist != &map->header) {
	root = rlist;
	rlist = root->left;
	- root->left = y;
	- break;
	- case UNLINK_MERGE_NONE:
	- vm_map_splay_findprev(root, &llist);
	- if (llist != &map->header) {
	- root = llist;
	- llist = root->right;
	- root->right = NULL;
	- } else if (rlist != &map->header) {
	- root = rlist;
	- rlist = root->left;
	- root->left = NULL;
	- } else
	- root = NULL;
	- break;
	+ max_free_left = vm_map_splay_merge_pred(map, root, llist);
	+ max_free_right = vm_map_splay_merge_right(map, root, rlist);
	+ } else {
	+ map->header.left = map->header.right = &map->header;
	+ root = NULL;
	}
	- y = entry->next;
	- y->prev = entry->prev;
	- y->prev->next = y;
	if (root != NULL)
	- vm_map_splay_merge(map, root, llist, rlist);
	- else
	- map->root = NULL;
	+ root->max_free = vm_size_max(max_free_left, max_free_right);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	map->nentries--;
	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
	@@ -1319,15 +1416,18 @@
	vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount)
	{
	vm_map_entry_t llist, rlist, root;
	+ bool found;

	VM_MAP_ASSERT_LOCKED(map);
	- root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
	- KASSERT(root != NULL,
	+ VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
	+ KASSERT(found,
	("%s: resize object not mapped", __func__));
	- vm_map_splay_findnext(root, &rlist);
	- root->right = NULL;
	+ VM_MAP_SPLAY_FINDNEXT(root, rlist);
	entry->end += grow_amount;
	- vm_map_splay_merge(map, root, llist, rlist);
	+ root->max_free = vm_size_max(
	+ vm_map_splay_merge_left(map, root, llist),
	+ vm_map_splay_merge_succ(map, root, rlist));
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
	__func__, map, map->nentries, entry);
	@@ -1349,7 +1449,7 @@
	vm_offset_t address,
	vm_map_entry_t entry) / OUT */
	{
	- vm_map_entry_t cur, lbound;
	+ vm_map_entry_t cur, lbound, ubound;
	boolean_t locked;

	/*
	@@ -1395,18 +1495,23 @@
	* Since the map is only locked for read access, perform a
	* standard binary search tree lookup for "address".
	*/
	- lbound = &map->header;
	- do {
	+ lbound = ubound = &map->header;
	+ for (;;) {
	if (address < cur->start) {
	+ ubound = cur;
	cur = cur->left;
	+ if (cur == lbound)
	+ break;
	} else if (cur->end <= address) {
	lbound = cur;
	cur = cur->right;
	+ if (cur == ubound)
	+ break;
	} else {
	*entry = cur;
	return (TRUE);
	}
	- } while (cur != NULL);
	+ }
	*entry = lbound;
	return (FALSE);
	}
	@@ -1646,8 +1751,8 @@
	vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length)
	{
	vm_map_entry_t llist, rlist, root, y;
	- vm_size_t left_length;
	- vm_offset_t gap_end;
	+ vm_size_t left_length, max_free_left, max_free_right;
	+ bool found;

	/*
	* Request must fit within min/max VM address and must avoid
	@@ -1664,32 +1769,37 @@
	/*
	* After splay_split, if start is within an entry, push it to the start
	* of the following gap. If rlist is at the end of the gap containing
	- * start, save the end of that gap in gap_end to see if the gap is big
	- * enough; otherwise set gap_end to start skip gap-checking and move
	- * directly to a search of the right subtree.
	+ * start, clear 'found' and see if the gap is big enough.
	*/
	- root = vm_map_splay_split(map, start, length, &llist, &rlist);
	- gap_end = rlist->start;
	- if (root != NULL) {
	- start = root->end;
	- if (root->right != NULL)
	- gap_end = start;
	+ VM_MAP_SPLAY_SPLIT(map, start, length, root, llist, rlist, found);
	+ if (found) {
	+ max_free_left = vm_map_splay_merge_left(map, root, llist);
	+ if (root->right == rlist) {
	+ start = root->end;
	+ found = false;
	+ }
	+ max_free_right = vm_map_splay_merge_right(map, root, rlist);
	} else if (rlist != &map->header) {
	root = rlist;
	rlist = root->left;
	- root->left = NULL;
	+ max_free_left = vm_map_splay_merge_pred(map, root, llist);
	+ max_free_right = vm_map_splay_merge_right(map, root, rlist);
	} else {
	root = llist;
	llist = root->right;
	- root->right = NULL;
	+ root->right = rlist;
	+ rlist->left = root;
	+ max_free_left = vm_map_splay_merge_left(map, root, llist);
	+ max_free_right = rlist->start - root->end;
	}
	- vm_map_splay_merge(map, root, llist, rlist);
	+ root->max_free = vm_size_max(max_free_left, max_free_right);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	- if (length <= gap_end - start)
	+ if (!found && length <= rlist->start - start)
	return (start);

	/* With max_free, can immediately tell if no solution. */
	- if (root->right == NULL \|\| length > root->right->max_free)
	+ if (root->right == &map->header \|\| length > root->right->max_free)
	return (vm_map_max(map) - length + 1);

	/*
	@@ -1699,28 +1809,32 @@
	for (left_length = 0;;
	left_length = vm_map_entry_max_free_left(root, llist)) {
	if (length <= left_length)
	- SPLAY_LEFT_STEP(root, y, rlist,
	+ SPLAY_LEFT_STEP(root, y, llist, rlist, found,
	length <= vm_map_entry_max_free_left(y, llist));
	else
	- SPLAY_RIGHT_STEP(root, y, llist,
	+ SPLAY_RIGHT_STEP(root, y, llist, rlist, found,
	length > vm_map_entry_max_free_left(y, root));
	- if (root == NULL)
	+ if (!found)
	break;
	}
	root = llist;
	llist = root->right;
	- root->right = NULL;
	- if (rlist != &map->header) {
	+ root->max_free = vm_map_splay_merge_left(map, root, llist);
	+ if (rlist == &map->header) {
	+ root->right = rlist;
	+ root->max_free = vm_size_max(root->max_free,
	+ rlist->start - root->end);
	+ } else {
	y = rlist;
	rlist = y->left;
	- y->left = NULL;
	- vm_map_splay_merge(map, y, &map->header, rlist);
	- y->max_free = MAX(
	- vm_map_entry_max_free_left(y, root),
	- vm_map_entry_max_free_right(y, &map->header));
	+ y->left = root;
	+ y->max_free = vm_size_max(
	+ y->start - root->end,
	+ vm_map_splay_merge_right(map, y, rlist));
	root->right = y;
	+ root->max_free = vm_size_max(root->max_free, y->max_free);
	}
	- vm_map_splay_merge(map, root, llist, &map->header);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	return (root->end);
	}
	@@ -4847,8 +4961,12 @@
	_vm_map_assert_consistent(vm_map_t map, int check)
	{
	vm_map_entry_t entry, prev;
	+ vm_map_entry_t cur, lbound, ubound;
	vm_size_t max_left, max_right;

	+#ifdef DIAGNOSTIC
	+ ++map->nupdates;
	+#endif
	if (enable_vmmap_check != check)
	return;

	@@ -4860,23 +4978,39 @@
	KASSERT(entry->start < entry->end,
	("map %p start = %jx, end = %jx", map,
	(uintmax_t)entry->start, (uintmax_t)entry->end));
	- KASSERT(entry->end <= vm_map_entry_succ(entry)->start,
	- ("map %p end = %jx, next->start = %jx", map,
	- (uintmax_t)entry->end,
	- (uintmax_t)vm_map_entry_succ(entry)->start));
	- KASSERT(entry->left == NULL \|\|
	+ KASSERT(entry->left == &map->header \|\|
	entry->left->start < entry->start,
	("map %p left->start = %jx, start = %jx", map,
	(uintmax_t)entry->left->start, (uintmax_t)entry->start));
	- KASSERT(entry->right == NULL \|\|
	+ KASSERT(entry->right == &map->header \|\|
	entry->start < entry->right->start,
	("map %p start = %jx, right->start = %jx", map,
	(uintmax_t)entry->start, (uintmax_t)entry->right->start));
	- max_left = vm_map_entry_max_free_left(entry,
	- vm_map_entry_pred(entry));
	- max_right = vm_map_entry_max_free_right(entry,
	- vm_map_entry_succ(entry));
	- KASSERT(entry->max_free == MAX(max_left, max_right),
	+ cur = map->root;
	+ lbound = ubound = &map->header;
	+ for (;;) {
	+ if (entry->start < cur->start) {
	+ ubound = cur;
	+ cur = cur->left;
	+ KASSERT(cur != lbound,
	+ ("map %p cannot find %jx",
	+ map, entry->start));
	+ } else if (cur->end <= entry->start) {
	+ lbound = cur;
	+ cur = cur->right;
	+ KASSERT(cur != ubound,
	+ ("map %p cannot find %jx",
	+ map, entry->start));
	+ } else {
	+ KASSERT(cur == entry,
	+ ("map %p cannot find %jx",
	+ map, entry->start));
	+ break;
	+ }
	+ }
	+ max_left = vm_map_entry_max_free_left(entry, lbound);
	+ max_right = vm_map_entry_max_free_right(entry, ubound);
	+ KASSERT(entry->max_free == vm_size_max(max_left, max_right),
	("map %p max = %jx, max_left = %jx, max_right = %jx", map,
	(uintmax_t)entry->max_free,
	(uintmax_t)max_left, (uintmax_t)max_right));

File Metadata

Mime Type: text/plain
Expires: Fri, Feb 27, 11:24 AM (14 h, 12 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 29027816
Default Alt Text: D21964.id64840.diff (25 KB)

D21964.id64840.diffNo OneTemporaryActions

D21964.id64840.diffView Options

File Metadata

Event Timeline

D21964.id64840.diff
No OneTemporary
Actions

D21964.id64840.diff
View Options