Page MenuHomeFreeBSD
Files F133031015

D19826.id.diff
No OneTemporary
Actions

D19826.id.diff
View Options

Index: head/sys/vm/vm_map.c
===================================================================
--- head/sys/vm/vm_map.c
+++ head/sys/vm/vm_map.c
@@ -962,55 +962,92 @@
}
/*
- * 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 @@
* 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 @@
*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 @@
* 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 @@
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 @@
/* 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 @@
* 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 @@
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 @@
};
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 @@
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 @@
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_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 @@
* 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 @@
* 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 @@
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 @@
/*
* 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);
}

File Metadata

Mime Type
text/plain
Expires
Thu, Oct 23, 6:14 AM (9 h, 21 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24062463
Default Alt Text
D19826.id.diff (14 KB)

Event Timeline