svn commit: r348881 - head/sys/vm
Doug Moore
dougm at FreeBSD.org
Mon Jun 10 21:34:08 UTC 2019
Author: dougm
Date: Mon Jun 10 21:34:07 2019
New Revision: 348881
URL: https://svnweb.freebsd.org/changeset/base/348881
Log:
The computations of vm_map_splay_split and vm_map_splay_merge touch both
children of every entry on the search path as part of updating values of
the max_free field. By comparing the max_free values of an entry and its
child on the search path, the code can avoid accessing the child off the
path in cases where the max_free value decreases along the path.
Specifically, this patch changes splay_split so that the max_free field
of every entry on the search path is replaced, temporarily, by the
max_free field from its child not on the search path or, if the child
in that direction is NULL, then a difference between start and end
values of two pointers already available in the split code, without
following any next or prev pointers. However, to find that max_free
value does not require looking toward that other child if either the
child on the search path has a lower max_free value, or the current max_free
value is zero, because in either case we know that the value of max_free for
the other child is the value we already have. So, the changes to
vm_entry_splay_split make sure that we know all the off-search-path entries
we will need to complete the splay, without looking at all of them. There is
an exception at the bottom of the search path where we cannot rely on the
max_free value in the direction of the NULL pointer that ends the search,
because of the behavior of entry-clipping code.
The corresponding change to vm_splay_entry_merge makes it simpler, since it's
just reversing pointers and updating running maxima.
In a test intended to exercise vigorously the vm_map implementation, the
effect of this change was to reduce the data cache miss rate by 10-14% and
the running time by 5-7%.
Tested by: pho
Reviewed by: alc
Approved by: kib (mentor)
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D19826
Modified:
head/sys/vm/vm_map.c
Modified: head/sys/vm/vm_map.c
==============================================================================
--- head/sys/vm/vm_map.c Mon Jun 10 21:27:21 2019 (r348880)
+++ head/sys/vm/vm_map.c Mon Jun 10 21:34:07 2019 (r348881)
@@ -962,55 +962,92 @@ vm_map_entry_set_behavior(vm_map_entry_t entry, u_char
}
/*
- * 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; \
+ 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) \
+ 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; \
+ KASSERT(max_free == vm_map_entry_max_free_right(root, rlist), \
+ ("%s: max_free not copied from right", __func__)); \
+ 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; \
+ 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) \
+ 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; \
+ KASSERT(max_free == vm_map_entry_max_free_left(root, llist), \
+ ("%s: max_free not copied from left", __func__)); \
+ root->right = llist; \
+ llist = root; \
+ root = y; \
} while (0)
/*
@@ -1019,18 +1056,21 @@ vm_map_entry_set_max_free(vm_map_entry_t entry)
* 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.
+ * 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.
*/
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_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;
- vm_map_entry_t y;
+ vm_map_entry_t llist, rlist, root, y;
- llist = NULL;
- rlist = NULL;
+ 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);
@@ -1069,44 +1109,65 @@ vm_map_splay_findprev(vm_map_entry_t root, vm_map_entr
*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_t map, vm_map_entry_t root,
+ 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 != &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;
}
- 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);
-
- return (root);
+ max_free_right = 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;
}
/*
- * 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
@@ -1123,14 +1184,14 @@ vm_map_splay_merge(vm_map_entry_t root,
* 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_map_t map, vm_offset_t addr)
{
- vm_map_entry_t llist, rlist;
+ vm_map_entry_t llist, rlist, root;
- root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
+ root = vm_map_splay_split(map, addr, 0, &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.
@@ -1138,7 +1199,7 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro
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.
@@ -1150,8 +1211,9 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro
/* There is no root. */
return (NULL);
}
- return (vm_map_splay_merge(root, llist, rlist,
- root->left, root->right));
+ vm_map_splay_merge(map, root, llist, rlist);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ return (root);
}
/*
@@ -1160,8 +1222,7 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro
* Insert/remove entries from maps.
*/
static void
-vm_map_entry_link(vm_map_t map,
- vm_map_entry_t entry)
+vm_map_entry_link(vm_map_t map, vm_map_entry_t entry)
{
vm_map_entry_t llist, rlist, root;
@@ -1170,15 +1231,14 @@ vm_map_entry_link(vm_map_t map,
map->nentries, entry);
VM_MAP_ASSERT_LOCKED(map);
map->nentries++;
- root = map->root;
- root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+ 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 == 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);
- map->root = entry;
+ entry->prev = llist;
+ entry->next = rlist;
+ llist->next = rlist->prev = entry;
+ entry->left = entry->right = NULL;
+ vm_map_splay_merge(map, entry, llist, rlist);
VM_MAP_ASSERT_CONSISTENT(map);
}
@@ -1189,19 +1249,13 @@ enum unlink_merge_type {
};
static void
-vm_map_entry_unlink(vm_map_t map,
- vm_map_entry_t entry,
- enum unlink_merge_type op)
+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_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);
+ root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
KASSERT(root != NULL,
("vm_map_entry_unlink: unlink object not mapped"));
@@ -1226,11 +1280,11 @@ vm_map_entry_unlink(vm_map_t map,
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;
@@ -1238,10 +1292,13 @@ vm_map_entry_unlink(vm_map_t map,
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);
- map->root = root;
+ vm_map_splay_merge(map, root, llist, rlist);
+ else
+ map->root = NULL;
VM_MAP_ASSERT_CONSISTENT(map);
map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
@@ -1262,15 +1319,13 @@ vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry
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);
+ root = vm_map_splay_split(map, entry->start, 0, &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(map, root, llist, rlist);
VM_MAP_ASSERT_CONSISTENT(map);
CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
__func__, map, map->nentries, entry);
@@ -1316,8 +1371,7 @@ vm_map_lookup_entry(
* 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(map, address);
if (!locked)
sx_downgrade(&map->lock);
@@ -1604,11 +1658,10 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s
* 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);
+ root = vm_map_splay_split(map, start, length, &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;
@@ -1617,8 +1670,7 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s
llist = root->right;
root->right = NULL;
}
- map->root = vm_map_splay_merge(root, llist, rlist,
- root->left, root->right);
+ vm_map_splay_merge(map, root, llist, rlist);
VM_MAP_ASSERT_CONSISTENT(map);
if (start + length <= root->start)
return (start);
@@ -1639,40 +1691,32 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s
/*
* Splay for the least large-enough gap in the right subtree.
*/
- llist = NULL;
- rlist = NULL;
- for (left_length = 0; ;
- left_length = root->left != NULL ?
- root->left->max_free : root->start - llist->end) {
+ llist = rlist = &map->header;
+ for (left_length = 0;;
+ 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)
- root->right = NULL;
- else {
+ root->right = NULL;
+ if (rlist != &map->header) {
+ y = rlist;
rlist = y->left;
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);
+ 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));
root->right = y;
- vm_map_entry_set_max_free(root);
}
- map->root = root;
+ vm_map_splay_merge(map, root, llist, &map->header);
VM_MAP_ASSERT_CONSISTENT(map);
return (root->end);
}
More information about the svn-src-head
mailing list