Page MenuHomeFreeBSD
Files F106086744

D19826.id56126.diff
No OneTemporary
Actions

D19826.id56126.diff
View Options

Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -898,23 +898,24 @@
}
/*
- * vm_map_entry_set_max_free:
+ * maxfree_{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 entry that lies on
+ * the other side of the tree.
*/
-static inline void
-vm_map_entry_set_max_free(vm_map_entry_t entry)
-{
- 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);
+static inline size_t
+maxfree_left(vm_map_entry_t root, vm_map_entry_t y)
+{
+ return (root->left != NULL ?
+ root->left->max_free : root->start - y->end);
+}
+static inline size_t
+maxfree_right(vm_map_entry_t root, vm_map_entry_t y)
+{
+ return (root->right != NULL ?
+ root->right->max_free : y->start - root->end);
}
#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
@@ -923,10 +924,15 @@
/* Rotate right and make y root. */ \
root->left = y->right; \
y->right = root; \
- vm_map_entry_set_max_free(root); \
+ if (root->max_free == y->max_free) \
+ root->max_free = MAX( \
+ maxfree_left(root, y), \
+ maxfree_right(root, rlist));\
+ y->max_free = root->max_free; \
root = y; \
y = root->left; \
- } \
+ } else \
+ root->max_free = maxfree_right(root, rlist); \
/* Put root on rlist. */ \
root->left = rlist; \
rlist = root; \
@@ -939,11 +945,17 @@
/* Rotate left and make y root. */ \
root->right = y->left; \
y->left = root; \
- vm_map_entry_set_max_free(root); \
+ if (root->max_free == y->max_free) \
+ root->max_free = MAX( \
+ maxfree_left(root, llist), \
+ maxfree_right(root, y)); \
+ y->max_free = root->max_free; \
root = y; \
y = root->right; \
- } \
+ } else \
+ root->max_free = maxfree_left(root, llist); \
/* Put root on llist. */ \
+ root->max_free = maxfree_left(root, llist); \
root->right = llist; \
llist = root; \
root = y; \
@@ -959,13 +971,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,
@@ -976,8 +988,8 @@
} else
break;
}
- *out_llist = llist;
- *out_rlist = rlist;
+ *io_llist = llist;
+ *io_rlist = rlist;
return (root);
}
@@ -1009,36 +1021,43 @@
* 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
+static void
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)
+ vm_map_entry_t llist, vm_map_entry_t rlist)
{
- vm_map_entry_t y;
+ vm_map_entry_t tree, y;
+ vm_size_t max_free;
- while (llist != NULL) {
+ tree = root->left;
+ if ((llist->eflags & MAP_ENTRY_HEADER) == 0)
+ max_free = maxfree_left(root, llist);
+ while ((llist->eflags & MAP_ENTRY_HEADER) == 0) {
y = llist->right;
- llist->right = ltree;
- vm_map_entry_set_max_free(llist);
- ltree = llist;
+ llist->right = tree;
+ if (llist->max_free < max_free)
+ llist->max_free = max_free;
+ else
+ max_free = llist->max_free;
+ tree = llist;
llist = y;
}
- while (rlist != NULL) {
+ root->left = tree;
+ tree = root->right;
+ if ((rlist->eflags & MAP_ENTRY_HEADER) == 0)
+ max_free = maxfree_right(root, rlist);
+ while ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
y = rlist->left;
- rlist->left = rtree;
- vm_map_entry_set_max_free(rlist);
- rtree = rlist;
+ rlist->left = tree;
+ if (rlist->max_free < max_free)
+ rlist->max_free = max_free;
+ else
+ max_free = rlist->max_free;
+ tree = 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);
+ root->right = tree;
+ root->max_free =
+ MAX(maxfree_left(root, llist), maxfree_right(root, rlist));
}
/*
@@ -1059,14 +1078,16 @@
* Returns: the new root.
*/
static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+vm_map_entry_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);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ 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->eflags & MAP_ENTRY_HEADER) == 0) {
/*
* Recover the greatest node in the left
* subtree and make it the root.
@@ -1074,7 +1095,7 @@
root = llist;
llist = root->right;
root->right = NULL;
- } else if (rlist != NULL) {
+ } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
/*
* Recover the least node in the right
* subtree and make it the root.
@@ -1084,10 +1105,13 @@
root->left = NULL;
} else {
/* There is no root. */
+ map->root = NULL;
return (NULL);
}
- return (vm_map_splay_merge(root, llist, rlist,
- root->left, root->right));
+ vm_map_splay_merge(root, llist, rlist);
+ map->root = root;
+ VM_MAP_ASSERT_CONSISTENT(map);
+ return (root);
}
/*
@@ -1099,21 +1123,38 @@
vm_map_entry_link(vm_map_t map,
vm_map_entry_t entry)
{
- vm_map_entry_t llist, rlist, root;
+ vm_map_entry_t llist, rlist, root, y;
CTR3(KTR_VM,
"vm_map_entry_link: map %p, nentries %d, entry %p", map,
map->nentries, entry);
VM_MAP_ASSERT_LOCKED(map);
+ VM_MAP_ASSERT_CONSISTENT(map);
map->nentries++;
- root = map->root;
- root = vm_map_splay_split(entry->start, 0, 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);
+ llist = rlist = &map->header;
+ root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
+ entry->left = entry->right = NULL;
+ if (root != NULL &&
+ entry->start <= root->start && entry->end < root->end) {
+ vm_map_splay_findprev(root, &llist);
+ SPLAY_LEFT_STEP(root, y, rlist, false);
+ rlist->offset += (entry->end - rlist->start);
+ rlist->start = entry->end;
+ } else if (root != NULL &&
+ entry->start > root->start && root->end >= entry->end) {
+ vm_map_splay_findnext(root, &rlist);
+ SPLAY_RIGHT_STEP(root, y, llist, false);
+ llist->end = entry->start;
+ } else
+ KASSERT(root == NULL,
+ ("vm_map_entry_link: inserting range [%jx, %jx) improperly"
+ " overlaps mapped range [%jx, %jx)",
+ (uintmax_t)entry->start, (uintmax_t)entry->end,
+ (uintmax_t)root->start, (uintmax_t)root->end));
+ entry->prev = llist;
+ entry->next = rlist;
+ llist->next = rlist->prev = entry;
+ vm_map_splay_merge(entry, llist, rlist);
map->root = entry;
VM_MAP_ASSERT_CONSISTENT(map);
}
@@ -1132,12 +1173,9 @@
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);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ 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"));
@@ -1162,11 +1200,11 @@
case UNLINK_MERGE_NONE:
vm_map_splay_findprev(root, &llist);
vm_map_splay_findnext(root, &rlist);
- if (llist != NULL) {
+ if ((llist->eflags & MAP_ENTRY_HEADER) == 0) {
root = llist;
llist = root->right;
root->right = NULL;
- } else if (rlist != NULL) {
+ } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
root = rlist;
rlist = root->left;
root->left = NULL;
@@ -1174,9 +1212,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, llist, rlist);
map->root = root;
VM_MAP_ASSERT_CONSISTENT(map);
map->nentries--;
@@ -1195,22 +1235,24 @@
* The map must be locked, and leaves it so.
*/
static void
-vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry)
+vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry, size_t grow_amount)
{
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);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ llist = rlist = &map->header;
+ root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
KASSERT(root != NULL,
("vm_map_entry_resize_free: resize_free object not mapped"));
vm_map_splay_findnext(root, &rlist);
root->right = NULL;
- map->root = vm_map_splay_merge(root, llist, rlist,
- root->left, root->right);
+ entry->end += grow_amount;
+ vm_map_splay_merge(root, llist, rlist);
+ map->root = root;
VM_MAP_ASSERT_CONSISTENT(map);
- CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map,
- map->nentries, entry);
+ CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p",
+ map, map->nentries, entry);
}
/*
@@ -1253,8 +1295,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_entry_splay(address, map);
if (!locked)
sx_downgrade(&map->lock);
@@ -1427,8 +1468,8 @@
prev_entry));
if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0)
map->size += end - prev_entry->end;
- prev_entry->end = end;
- vm_map_entry_resize_free(map, prev_entry);
+ vm_map_entry_resize_free(map, prev_entry,
+ end - prev_entry->end);
vm_map_simplify_entry(map, prev_entry);
return (KERN_SUCCESS);
}
@@ -1538,11 +1579,12 @@
* 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);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ 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->eflags & MAP_ENTRY_HEADER) == 0) {
root = rlist;
rlist = root->left;
root->left = NULL;
@@ -1551,8 +1593,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, llist, rlist);
+ map->root = root;
VM_MAP_ASSERT_CONSISTENT(map);
if (start + length <= root->start)
return (start);
@@ -1573,39 +1615,32 @@
/*
* 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 = maxfree_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 <= maxfree_left(y, llist));
else
SPLAY_RIGHT_STEP(root, y, llist,
- length > (y->left != NULL ?
- y->left->max_free : y->start - root->end));
+ length > maxfree_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, 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(maxfree_left(y, root),
+ maxfree_right(y, &map->header));
root->right = y;
- vm_map_entry_set_max_free(root);
}
+ vm_map_splay_merge(root, llist, &map->header);
map->root = root;
VM_MAP_ASSERT_CONSISTENT(map);
return (root->end);
@@ -2068,8 +2103,6 @@
*new_entry = *entry;
new_entry->end = start;
- entry->offset += (start - entry->start);
- entry->start = start;
if (new_entry->cred != NULL)
crhold(entry->cred);
@@ -2150,7 +2183,7 @@
new_entry = vm_map_entry_create(map);
*new_entry = *entry;
- new_entry->start = entry->end = end;
+ new_entry->start = end;
new_entry->offset += (end - entry->start);
if (new_entry->cred != NULL)
crhold(entry->cred);
@@ -4181,25 +4214,20 @@
gap_deleted = true;
} else {
MPASS(gap_entry->start < gap_entry->end - grow_amount);
- gap_entry->end -= grow_amount;
- vm_map_entry_resize_free(map, gap_entry);
+ vm_map_entry_resize_free(map, gap_entry, -grow_amount);
gap_deleted = false;
}
rv = vm_map_insert(map, NULL, 0, grow_start,
grow_start + grow_amount,
stack_entry->protection, stack_entry->max_protection,
MAP_STACK_GROWS_DOWN);
- if (rv != KERN_SUCCESS) {
- if (gap_deleted) {
- rv1 = vm_map_insert(map, NULL, 0, gap_start,
- gap_end, VM_PROT_NONE, VM_PROT_NONE,
- MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN);
- MPASS(rv1 == KERN_SUCCESS);
- } else {
- gap_entry->end += grow_amount;
- vm_map_entry_resize_free(map, gap_entry);
- }
- }
+ if (rv != KERN_SUCCESS && gap_deleted) {
+ rv1 = vm_map_insert(map, NULL, 0, gap_start,
+ gap_end, VM_PROT_NONE, VM_PROT_NONE,
+ MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN);
+ MPASS(rv1 == KERN_SUCCESS);
+ } else if (rv != KERN_SUCCESS)
+ vm_map_entry_resize_free(map, gap_entry, grow_amount);
} else {
grow_start = stack_entry->end;
cred = stack_entry->cred;
@@ -4213,13 +4241,15 @@
stack_entry->offset,
(vm_size_t)(stack_entry->end - stack_entry->start),
(vm_size_t)grow_amount, cred != NULL)) {
- if (gap_entry->start + grow_amount == gap_entry->end)
+ if (gap_entry->start + grow_amount == gap_entry->end) {
vm_map_entry_delete(map, gap_entry);
- else
+ vm_map_entry_resize_free(map, stack_entry,
+ grow_amount);
+ } else {
gap_entry->start += grow_amount;
- stack_entry->end += grow_amount;
+ stack_entry += grow_amount;
+ }
map->size += grow_amount;
- vm_map_entry_resize_free(map, stack_entry);
rv = KERN_SUCCESS;
} else
rv = KERN_FAILURE;

File Metadata

Mime Type
text/plain
Expires
Thu, Dec 26, 4:26 AM (6 h, 8 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
15601366
Default Alt Text
D19826.id56126.diff (15 KB)

Event Timeline