D21964.diff
No OneTemporary
Actions

Size

17 KB

Referenced Files

None

Subscribers

None

D21964.diff
View Options

	Index: head/sys/vm/vm_map.h
	===================================================================
	--- head/sys/vm/vm_map.h
	+++ head/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 */
	@@ -175,9 +173,12 @@

	/*
	* A map is a set of map entries. These map entries are
	- * organized both as a binary search tree and as a doubly-linked
	- * list. Both structures are ordered based upon the start and
	- * end addresses contained within each map entry.
	+ * organized as a threaded binary search tree. Both structures
	+ * are ordered based upon the start and end addresses contained
	+ * within each map entry. The largest gap between an entry in a
	+ * subtree and one of its neighbors is saved in the max_free
	+ * field, and that field is updated when the tree is
	+ * restructured.
	*
	* Sleator and Tarjan's top-down splay algorithm is employed to
	* control height imbalance in the binary search tree.
	@@ -185,10 +186,12 @@
	* The map's min offset value is stored in map->header.end, and
	* its max offset value is stored in map->header.start. These
	* values act as sentinels for any forward or backward address
	- * scan of the list. The map header has a special value for the
	- * eflags field, MAP_ENTRY_HEADER, that is set initially, is
	- * never changed, and prevents an eflags match of the header
	- * with any other map entry.
	+ * scan of the list. The right and left fields of the map
	+ * header point to the first and list map entries. The map
	+ * header has a special value for the eflags field,
	+ * MAP_ENTRY_HEADER, that is set initially, is never changed,
	+ * and prevents an eflags match of the header with any other map
	+ * entry.
	*
	* List of locks
	* (c) const until freed
	@@ -424,14 +427,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: head/sys/vm/vm_map.c
	===================================================================
	--- head/sys/vm/vm_map.c
	+++ head/sys/vm/vm_map.c
	@@ -896,7 +896,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;
	@@ -904,6 +903,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;
	@@ -977,7 +977,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);
	}

	@@ -985,7 +985,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);
	}

	@@ -994,16 +994,22 @@
	*
	* Find the {predecessor, successor} of the entry by taking one step
	* in the appropriate direction and backtracking as much as necessary.
	+ * vm_map_entry_succ is defined in vm_map.h.
	*/
	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. */
	-
	static inline vm_size_t
	vm_size_max(vm_size_t a, vm_size_t b)
	{
	@@ -1011,7 +1017,8 @@
	return (a > b ? a : b);
	}

	-#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
	+#define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \
	+ vm_map_entry_t z; \
	vm_size_t max_free; \
	\
	/* \
	@@ -1023,16 +1030,20 @@
	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 (max_free < y->max_free) \
	+ z = y->right; \
	+ if (z != root) { \
	+ root->left = z; \
	+ y->right = root; \
	+ if (max_free < y->max_free) \
	+ root->max_free = max_free = \
	+ vm_size_max(max_free, z->max_free); \
	+ } else if (max_free < y->max_free) \
	root->max_free = max_free = \
	- vm_size_max(max_free, \
	- vm_map_entry_max_free_left(root, y)); \
	+ vm_size_max(max_free, root->start - y->end);\
	root = y; \
	y = root->left; \
	} \
	@@ -1042,10 +1053,11 @@
	("%s: max_free not copied from right", __func__)); \
	root->left = rlist; \
	rlist = root; \
	- root = y; \
	+ root = y != llist ? y : NULL; \
	} while (0)

	-#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
	+#define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do { \
	+ vm_map_entry_t z; \
	vm_size_t max_free; \
	\
	/* \
	@@ -1057,16 +1069,20 @@
	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 (max_free < y->max_free) \
	+ z = y->left; \
	+ if (z != root) { \
	+ root->right = z; \
	+ y->left = root; \
	+ if (max_free < y->max_free) \
	+ root->max_free = max_free = \
	+ vm_size_max(max_free, z->max_free); \
	+ } else if (max_free < y->max_free) \
	root->max_free = max_free = \
	- vm_size_max(max_free, \
	- vm_map_entry_max_free_right(root, y)); \
	+ vm_size_max(max_free, y->start - root->end);\
	root = y; \
	y = root->right; \
	} \
	@@ -1076,61 +1092,73 @@
	("%s: max_free not copied from left", __func__)); \
	root->right = llist; \
	llist = root; \
	- root = y; \
	+ root = y != rlist ? y : NULL; \
	} 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
	+ * 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,pred,succ}, rely on the start and end address
	* values in &map->header.
	*/
	static __always_inline vm_map_entry_t
	vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length,
	vm_map_entry_t llist, vm_map_entry_t rlist)
	{
	- vm_map_entry_t root, y;
	+ vm_map_entry_t left, right, root, y;

	- llist = rlist = &map->header;
	+ left = right = &map->header;
	root = map->root;
	while (root != NULL && root->max_free >= length) {
	- KASSERT((*llist)->end <= root->start &&
	- root->end <= (*rlist)->start,
	+ KASSERT(left->end <= root->start &&
	+ root->end <= right->start,
	("%s: root not within tree bounds", __func__));
	if (addr < root->start) {
	- SPLAY_LEFT_STEP(root, y, *rlist,
	+ SPLAY_LEFT_STEP(root, y, left, right,
	y->max_free >= length && addr < y->start);
	} else if (addr >= root->end) {
	- SPLAY_RIGHT_STEP(root, y, *llist,
	+ SPLAY_RIGHT_STEP(root, y, left, right,
	y->max_free >= length && addr >= y->end);
	} else
	break;
	}
	+ *llist = left;
	+ *rlist = right;
	return (root);
	}

	static __always_inline void
	vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist)
	{
	- vm_map_entry_t hi, y;
	+ vm_map_entry_t hi, right, y;

	- hi = root->right;
	- while (hi != NULL)
	- SPLAY_LEFT_STEP(hi, y, *rlist, true);
	+ right = *rlist;
	+ hi = root->right == right ? NULL : root->right;
	+ if (hi == NULL)
	+ return;
	+ do
	+ SPLAY_LEFT_STEP(hi, y, root, right, true);
	+ while (hi != NULL);
	+ *rlist = right;
	}

	static __always_inline void
	vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)
	{
	- vm_map_entry_t lo, y;
	+ vm_map_entry_t left, lo, y;

	- lo = root->left;
	- while (lo != NULL)
	- SPLAY_RIGHT_STEP(lo, y, *llist, true);
	+ left = *llist;
	+ lo = root->left == left ? NULL : root->left;
	+ if (lo == NULL)
	+ return;
	+ do
	+ SPLAY_RIGHT_STEP(lo, y, left, root, true);
	+ while (lo != NULL);
	+ *llist = left;
	}

	static inline void
	@@ -1178,9 +1206,10 @@
	max_free = root->start - llist->end;
	if (llist != header) {
	max_free = vm_map_splay_merge_left_walk(header, root,
	- NULL, max_free, llist);
	+ root, max_free, llist);
	} else {
	- root->left = NULL;
	+ root->left = header;
	+ header->right = root;
	}
	return (max_free);
	}
	@@ -1197,7 +1226,8 @@
	max_free = vm_map_entry_max_free_left(root, llist);
	if (llist != header) {
	max_free = vm_map_splay_merge_left_walk(header, root,
	- root->left, max_free, llist);
	+ root->left == llist ? root : root->left,
	+ max_free, llist);
	}
	return (max_free);
	}
	@@ -1233,9 +1263,10 @@
	max_free = rlist->start - root->end;
	if (rlist != header) {
	max_free = vm_map_splay_merge_right_walk(header, root,
	- NULL, max_free, rlist);
	+ root, max_free, rlist);
	} else {
	- root->right = NULL;
	+ root->right = header;
	+ header->left = root;
	}
	return (max_free);
	}
	@@ -1252,7 +1283,8 @@
	max_free = vm_map_entry_max_free_right(root, rlist);
	if (rlist != header) {
	max_free = vm_map_splay_merge_right_walk(header, root,
	- root->right, max_free, rlist);
	+ root->right == rlist ? root : root->right,
	+ max_free, rlist);
	}
	return (max_free);
	}
	@@ -1267,6 +1299,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.
	*
	@@ -1332,9 +1372,6 @@
	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
	KASSERT(root == NULL,
	("vm_map_entry_link: link object already mapped"));
	- entry->prev = llist;
	- entry->next = rlist;
	- llist->next = rlist->prev = entry;
	root = entry;
	root->max_free = vm_size_max(
	vm_map_splay_merge_pred(header, root, llist),
	@@ -1352,7 +1389,7 @@
	vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry,
	enum unlink_merge_type op)
	{
	- vm_map_entry_t header, llist, rlist, root, y;
	+ vm_map_entry_t header, llist, rlist, root;
	vm_size_t max_free_left, max_free_right;

	VM_MAP_ASSERT_LOCKED(map);
	@@ -1377,11 +1414,10 @@
	rlist = root->left;
	max_free_left = vm_map_splay_merge_pred(header, root, llist);
	max_free_right = vm_map_splay_merge_right(header, root, rlist);
	- } else
	+ } else {
	+ header->left = header->right = header;
	root = NULL;
	- y = entry->next;
	- y->prev = entry->prev;
	- y->prev->next = y;
	+ }
	if (root != NULL)
	root->max_free = vm_size_max(max_free_left, max_free_right);
	map->root = root;
	@@ -1435,7 +1471,7 @@
	vm_offset_t address,
	vm_map_entry_t entry) / OUT */
	{
	- vm_map_entry_t cur, header, lbound;
	+ vm_map_entry_t cur, header, lbound, ubound;
	boolean_t locked;

	/*
	@@ -1482,18 +1518,23 @@
	* Since the map is only locked for read access, perform a
	* standard binary search tree lookup for "address".
	*/
	- lbound = header;
	- do {
	+ lbound = ubound = 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);
	}
	@@ -1760,7 +1801,7 @@
	gap_end = rlist->start;
	if (root != NULL) {
	start = root->end;
	- if (root->right != NULL)
	+ if (root->right != rlist)
	gap_end = start;
	max_free_left = vm_map_splay_merge_left(header, root, llist);
	max_free_right = vm_map_splay_merge_right(header, root, rlist);
	@@ -1782,7 +1823,7 @@
	return (start);

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

	/*
	@@ -1792,10 +1833,10 @@
	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,
	length <= vm_map_entry_max_free_left(y, llist));
	else
	- SPLAY_RIGHT_STEP(root, y, llist,
	+ SPLAY_RIGHT_STEP(root, y, llist, rlist,
	length > vm_map_entry_max_free_left(y, root));
	if (root == NULL)
	break;
	@@ -1812,7 +1853,6 @@
	y->max_free = vm_size_max(
	vm_map_splay_merge_pred(root, y, root),
	vm_map_splay_merge_right(header, y, rlist));
	- root->right = y;
	root->max_free = vm_size_max(max_free_left, y->max_free);
	}
	map->root = root;
	@@ -4961,6 +5001,7 @@
	_vm_map_assert_consistent(vm_map_t map, int check)
	{
	vm_map_entry_t entry, prev;
	+ vm_map_entry_t cur, header, lbound, ubound;
	vm_size_t max_left, max_right;

	#ifdef DIAGNOSTIC
	@@ -4969,7 +5010,7 @@
	if (enable_vmmap_check != check)
	return;

	- prev = &map->header;
	+ header = prev = &map->header;
	VM_MAP_ENTRY_FOREACH(entry, map) {
	KASSERT(prev->end <= entry->start,
	("map %p prev->end = %jx, start = %jx", map,
	@@ -4977,23 +5018,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 == 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 == 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 = 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: Wed, Feb 12, 1:35 AM (17 h, 15 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 16604127
Default Alt Text: D21964.diff (17 KB)

D21964.diffNo OneTemporaryActions

D21964.diffView Options

File Metadata

Event Timeline

D21964.diff
No OneTemporary
Actions

D21964.diff
View Options