D19826.id58256.diff
No OneTemporary
Actions

Size

13 KB

Referenced Files

None

Subscribers

None

D19826.id58256.diff
View Options

	Index: vm_map.c
	===================================================================
	--- vm_map.c
	+++ vm_map.c
	@@ -954,55 +954,84 @@
	}

	/*
	- * vm_map_entry_set_max_free:
	+ * vm_map_entry_max_free_{left,right}:
	*
	- * Set the max_free field in a vm_map_entry.
	+ * Compute the size of the largest free gap between two entries,
	+ * one the root of a tree and the other the ancestor of that root
	+ * that is the least or greatest ancestor found on the search path.
	*/
	-static inline void
	-vm_map_entry_set_max_free(vm_map_entry_t entry)
	+static inline vm_size_t
	+vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
	{
	- vm_map_entry_t child;
	- vm_size_t max_left, max_right;

	- child = entry->left;
	- max_left = (child != NULL) ? child->max_free :
	- entry->start - entry->prev->end;
	- child = entry->right;
	- max_right = (child != NULL) ? child->max_free :
	- entry->next->start - entry->end;
	- entry->max_free = MAX(max_left, max_right);
	+ return (root->left != NULL ?
	+ root->left->max_free : root->start - left_ancestor->end);
	}

	-#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
	- y = root->left; \
	- if (y != NULL && (test)) { \
	- /* Rotate right and make y root. */ \
	- root->left = y->right; \
	- y->right = root; \
	- vm_map_entry_set_max_free(root); \
	- root = y; \
	- y = root->left; \
	- } \
	- /* Put root on rlist. */ \
	- root->left = rlist; \
	- rlist = root; \
	- root = y; \
	+static inline vm_size_t
	+vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
	+{
	+
	+ return (root->right != NULL ?
	+ root->right->max_free : right_ancestor->start - root->end);
	+}
	+
	+#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
	+ vm_size_t max_free; \
	+ \
	+ /* \
	+ * Infer root->right->max_free == root->max_free when \
	+ * y->max_free < root->max_free \|\| root->max_free == 0. \
	+ * Otherwise, look right to find it. \
	+ */ \
	+ y = root->left; \
	+ max_free = root->max_free; \
	+ if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
	+ max_free = vm_map_entry_max_free_right(root, rlist); \
	+ if (y != NULL && (test)) { \
	+ /* Rotate right and make y root. */ \
	+ root->left = y->right; \
	+ y->right = root; \
	+ if (max_free < y->max_free) \
	+ root->max_free = max_free = MAX(max_free, \
	+ vm_map_entry_max_free_left(root, y)); \
	+ root = y; \
	+ y = root->left; \
	+ } \
	+ /* Copy right->max_free. Put root on rlist. */ \
	+ root->max_free = max_free; \
	+ root->left = rlist; \
	+ rlist = root; \
	+ root = y; \
	} while (0)

	-#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
	- y = root->right; \
	- if (y != NULL && (test)) { \
	- /* Rotate left and make y root. */ \
	- root->right = y->left; \
	- y->left = root; \
	- vm_map_entry_set_max_free(root); \
	- root = y; \
	- y = root->right; \
	- } \
	- /* Put root on llist. */ \
	- root->right = llist; \
	- llist = root; \
	- root = y; \
	+#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
	+ vm_size_t max_free; \
	+ \
	+ /* \
	+ * Infer root->left->max_free == root->max_free when \
	+ * y->max_free < root->max_free \|\| root->max_free == 0. \
	+ * Otherwise, look left to find it. \
	+ */ \
	+ y = root->right; \
	+ max_free = root->max_free; \
	+ if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
	+ max_free = vm_map_entry_max_free_left(root, llist); \
	+ if (y != NULL && (test)) { \
	+ /* Rotate left and make y root. */ \
	+ root->right = y->left; \
	+ y->left = root; \
	+ if (max_free < y->max_free) \
	+ root->max_free = max_free = MAX(max_free, \
	+ vm_map_entry_max_free_right(root, y)); \
	+ root = y; \
	+ y = root->right; \
	+ } \
	+ /* Copy left->max_free. Put root on llist. */ \
	+ root->max_free = max_free; \
	+ root->right = llist; \
	+ llist = root; \
	+ root = y; \
	} while (0)

	/*
	@@ -1015,13 +1044,13 @@
	*/
	static vm_map_entry_t
	vm_map_splay_split(vm_offset_t addr, vm_size_t length,
	- vm_map_entry_t root, vm_map_entry_t out_llist, vm_map_entry_t out_rlist)
	+ vm_map_entry_t root, vm_map_entry_t io_llist, vm_map_entry_t io_rlist)
	{
	vm_map_entry_t llist, rlist;
	vm_map_entry_t y;

	- llist = NULL;
	- rlist = NULL;
	+ llist = *io_llist;
	+ rlist = *io_rlist;
	while (root != NULL && root->max_free >= length) {
	if (addr < root->start) {
	SPLAY_LEFT_STEP(root, y, rlist,
	@@ -1032,8 +1061,8 @@
	} else
	break;
	}
	- *out_llist = llist;
	- *out_rlist = rlist;
	+ *io_llist = llist;
	+ *io_rlist = rlist;
	return (root);
	}

	@@ -1061,44 +1090,56 @@
	*iolist = llist;
	}

	+static inline void
	+vm_map_entry_swap(vm_map_entry_t a, vm_map_entry_t b)
	+{
	+ vm_map_entry_t tmp;
	+
	+ tmp = *b;
	+ b = a;
	+ *a = tmp;
	+}
	+
	/*
	* 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 vm_map_entry_t
	-vm_map_splay_merge(vm_map_entry_t root,
	- vm_map_entry_t llist, vm_map_entry_t rlist,
	- vm_map_entry_t ltree, vm_map_entry_t rtree)
	+static void
	+vm_map_splay_merge(vm_map_entry_t root, vm_map_entry_t header,
	+ vm_map_entry_t llist, vm_map_entry_t rlist)
	{
	- vm_map_entry_t y;
	+ vm_map_entry_t prev;
	+ vm_size_t max_free_left, max_free_right;

	- while (llist != NULL) {
	- y = llist->right;
	- llist->right = ltree;
	- vm_map_entry_set_max_free(llist);
	- ltree = llist;
	- llist = y;
	+ max_free_left = vm_map_entry_max_free_left(root, llist);
	+ if (llist != header) {
	+ prev = root->left;
	+ do {
	+ 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 != header);
	+ root->left = prev;
	}
	- while (rlist != NULL) {
	- y = rlist->left;
	- rlist->left = rtree;
	- vm_map_entry_set_max_free(rlist);
	- rtree = rlist;
	- rlist = y;
	- }

	- /*
	- * Final assembly: add ltree and rtree as subtrees of root.
	- */
	- root->left = ltree;
	- root->right = rtree;
	- vm_map_entry_set_max_free(root);
	+ max_free_right = vm_map_entry_max_free_right(root, rlist);
	+ if (rlist != header) {
	+ prev = root->right;
	+ do {
	+ 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 != header);
	+ root->right = prev;
	+ }

	- return (root);
	+ root->max_free = MAX(max_free_left, max_free_right);
	}

	/*
	- * vm_map_entry_splay:
	+ * vm_map_splay:
	*
	* The Sleator and Tarjan top-down splay algorithm with the
	* following variation. Max_free must be computed bottom-up, so
	@@ -1115,14 +1156,15 @@
	* Returns: the new root.
	*/
	static vm_map_entry_t
	-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
	+vm_map_splay(vm_offset_t addr, vm_map_t map)
	{
	- vm_map_entry_t llist, rlist;
	+ vm_map_entry_t llist, rlist, root;

	- root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
	+ llist = rlist = &map->header;
	+ root = vm_map_splay_split(addr, 0, map->root, &llist, &rlist);
	if (root != NULL) {
	/* do nothing */
	- } else if (llist != NULL) {
	+ } else if (llist != &map->header) {
	/*
	* Recover the greatest node in the left
	* subtree and make it the root.
	@@ -1130,7 +1172,7 @@
	root = llist;
	llist = root->right;
	root->right = NULL;
	- } else if (rlist != NULL) {
	+ } else if (rlist != &map->header) {
	/*
	* Recover the least node in the right
	* subtree and make it the root.
	@@ -1142,8 +1184,10 @@
	/* There is no root. */
	return (NULL);
	}
	- return (vm_map_splay_merge(root, llist, rlist,
	- root->left, root->right));
	+ vm_map_splay_merge(root, &map->header, llist, rlist);
	+ map->root = root;
	+ VM_MAP_ASSERT_CONSISTENT(map);
	+ return (root);
	}

	/*
	@@ -1162,14 +1206,15 @@
	map->nentries, entry);
	VM_MAP_ASSERT_LOCKED(map);
	map->nentries++;
	- root = map->root;
	- root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
	+ llist = rlist = &map->header;
	+ root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
	KASSERT(root == NULL,
	("vm_map_entry_link: link object already mapped"));
	- entry->prev = (llist == NULL) ? &map->header : llist;
	- entry->next = (rlist == NULL) ? &map->header : rlist;
	- entry->prev->next = entry->next->prev = entry;
	- root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL);
	+ entry->prev = llist;
	+ entry->next = rlist;
	+ llist->next = rlist->prev = entry;
	+ entry->left = entry->right = NULL;
	+ vm_map_splay_merge(entry, &map->header, llist, rlist);
	map->root = entry;
	VM_MAP_ASSERT_CONSISTENT(map);
	}
	@@ -1188,12 +1233,8 @@
	vm_map_entry_t llist, rlist, root, y;

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

	@@ -1218,11 +1259,11 @@
	case UNLINK_MERGE_NONE:
	vm_map_splay_findprev(root, &llist);
	vm_map_splay_findnext(root, &rlist);
	- if (llist != NULL) {
	+ if (llist != &map->header) {
	root = llist;
	llist = root->right;
	root->right = NULL;
	- } else if (rlist != NULL) {
	+ } else if (rlist != &map->header) {
	root = rlist;
	rlist = root->left;
	root->left = NULL;
	@@ -1230,9 +1271,11 @@
	root = NULL;
	break;
	}
	+ y = entry->next;
	+ y->prev = entry->prev;
	+ y->prev->next = y;
	if (root != NULL)
	- root = vm_map_splay_merge(root, llist, rlist,
	- root->left, root->right);
	+ vm_map_splay_merge(root, &map->header, llist, rlist);
	map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	map->nentries--;
	@@ -1254,15 +1297,15 @@
	vm_map_entry_t llist, rlist, root;

	VM_MAP_ASSERT_LOCKED(map);
	- root = map->root;
	- root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
	+ llist = rlist = &map->header;
	+ root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
	KASSERT(root != NULL,
	("%s: resize object not mapped", __func__));
	vm_map_splay_findnext(root, &rlist);
	root->right = NULL;
	entry->end += grow_amount;
	- map->root = vm_map_splay_merge(root, llist, rlist,
	- root->left, root->right);
	+ vm_map_splay_merge(root, &map->header, llist, rlist);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
	__func__, map, map->nentries, entry);
	@@ -1308,8 +1351,7 @@
	* change the map. Thus, the map's timestamp need not change
	* on a temporary upgrade.
	*/
	- map->root = cur = vm_map_entry_splay(address, cur);
	- VM_MAP_ASSERT_CONSISTENT(map);
	+ cur = vm_map_splay(address, map);
	if (!locked)
	sx_downgrade(&map->lock);

	@@ -1596,11 +1638,11 @@
	* After splay, if start comes before root node, then there
	* must be a gap from start to the root.
	*/
	- root = vm_map_splay_split(start, length, map->root,
	- &llist, &rlist);
	+ llist = rlist = &map->header;
	+ root = vm_map_splay_split(start, length, map->root, &llist, &rlist);
	if (root != NULL)
	start = root->end;
	- else if (rlist != NULL) {
	+ else if (rlist != &map->header) {
	root = rlist;
	rlist = root->left;
	root->left = NULL;
	@@ -1609,8 +1651,8 @@
	llist = root->right;
	root->right = NULL;
	}
	- map->root = vm_map_splay_merge(root, llist, rlist,
	- root->left, root->right);
	+ vm_map_splay_merge(root, &map->header, llist, rlist);
	+ map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	if (start + length <= root->start)
	return (start);
	@@ -1631,39 +1673,33 @@
	/*
	* Splay for the least large-enough gap in the right subtree.
	*/
	- llist = NULL;
	- rlist = NULL;
	+ llist = rlist = &map->header;
	for (left_length = 0; ;
	- left_length = root->left != NULL ?
	- root->left->max_free : root->start - llist->end) {
	+ left_length = vm_map_entry_max_free_left(root, llist)) {
	if (length <= left_length)
	SPLAY_LEFT_STEP(root, y, rlist,
	- length <= (y->left != NULL ?
	- y->left->max_free : y->start - llist->end));
	+ length <= vm_map_entry_max_free_left(y, llist));
	else
	SPLAY_RIGHT_STEP(root, y, llist,
	- length > (y->left != NULL ?
	- y->left->max_free : y->start - root->end));
	+ length > vm_map_entry_max_free_left(y, root));
	if (root == NULL)
	break;
	}
	root = llist;
	llist = root->right;
	- if ((y = rlist) == NULL)
	+ if (rlist == &map->header)
	root->right = NULL;
	else {
	+ y = rlist;
	rlist = y->left;
	+ vm_map_splay_merge(y, &map->header, &map->header, rlist);
	y->left = NULL;
	- root->right = y->right;
	- }
	- root = vm_map_splay_merge(root, llist, rlist,
	- root->left, root->right);
	- if (y != NULL) {
	- y->right = root->right;
	- vm_map_entry_set_max_free(y);
	+ y->max_free = MAX(
	+ vm_map_entry_max_free_left(y, root),
	+ vm_map_entry_max_free_right(y, &map->header));
	root->right = y;
	- vm_map_entry_set_max_free(root);
	}
	+ vm_map_splay_merge(root, &map->header, llist, &map->header);
	map->root = root;
	VM_MAP_ASSERT_CONSISTENT(map);
	return (root->end);

File Metadata

Mime Type: text/plain
Expires: Tue, Nov 18, 9:03 AM (4 h, 42 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 25495156
Default Alt Text: D19826.id58256.diff (13 KB)

D19826.id58256.diffNo OneTemporaryActions

D19826.id58256.diffView Options

File Metadata

Event Timeline

D19826.id58256.diff
No OneTemporary
Actions

D19826.id58256.diff
View Options