Changeset View
Changeset View
Standalone View
Standalone View
sys/vm/vm_map.c
Context not available. | |||||
/* | /* | ||||
* vm_map_entry_set_behavior: | * vm_map_entry_set_behavior: | ||||
* | * | ||||
* Set the expected access behavior, either normal, random, or | * Set the expected access behavior, either normal, random, or | ||||
* sequential. | * sequential. | ||||
*/ | */ | ||||
static inline void | static inline void | ||||
vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior) | vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior) | ||||
{ | { | ||||
entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) | | entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) | | ||||
(behavior & MAP_ENTRY_BEHAV_MASK); | (behavior & MAP_ENTRY_BEHAV_MASK); | ||||
} | } | ||||
/* | /* | ||||
* 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; | static inline size_t | ||||
max_left = (child != NULL) ? child->max_free : | maxfree_left(vm_map_entry_t root, vm_map_entry_t y) | ||||
kib: vm_map_maxfree_left, please honor the symbols namespace. | |||||
entry->start - entry->prev->end; | { | ||||
child = entry->right; | return (root->left != NULL ? | ||||
max_right = (child != NULL) ? child->max_free : | root->left->max_free : root->start - y->end); | ||||
Done Inline ActionsThese functions operate on entries. Why has "entry_" been removed from the function name? alc: These functions operate on entries. Why has "entry_" been removed from the function name? | |||||
Done Inline ActionsBecause 80-character line limits and 8-space tabs make people desperate to avoid long names and nested loops. Neverthless, at the cost of wrapping 2 long lines, this has been changed. dougm: Because 80-character line limits and 8-space tabs make people desperate to avoid long names and… | |||||
entry->next->start - entry->end; | } | ||||
entry->max_free = MAX(max_left, max_right); | static inline size_t | ||||
Done Inline ActionsBlank line between functions definitions. kib: Blank line between functions definitions. | |||||
maxfree_right(vm_map_entry_t root, vm_map_entry_t y) | |||||
Done Inline Actionsnamespace. kib: namespace. | |||||
{ | |||||
return (root->right != NULL ? | |||||
root->right->max_free : y->start - root->end); | |||||
} | } | ||||
Done Inline Actionsvm_size_t, not size_t. alc: vm_size_t, not size_t. | |||||
#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \ | #define SPLAY_LEFT_STEP(root, y, rlist, test) do { \ | ||||
y = root->left; \ | y = root->left; \ | ||||
Done Inline ActionsInsert blank line. alc: Insert blank line. | |||||
if (y != NULL && (test)) { \ | if (y != NULL && (test)) { \ | ||||
/* Rotate right and make y root. */ \ | /* Rotate right and make y root. */ \ | ||||
root->left = y->right; \ | root->left = y->right; \ | ||||
y->right = root; \ | y->right = root; \ | ||||
Done Inline ActionsDitto. alc: Ditto. | |||||
vm_map_entry_set_max_free(root); \ | if (root->max_free == y->max_free) \ | ||||
root->max_free = MAX( \ | |||||
maxfree_left(root, y), \ | |||||
Done Inline ActionsInsert blank line. alc: Insert blank line. | |||||
maxfree_right(root, rlist));\ | |||||
root = y; \ | root = y; \ | ||||
y = root->left; \ | y = root->left; \ | ||||
} \ | } \ | ||||
/* Put root on rlist. */ \ | /* Put root on rlist. */ \ | ||||
root->max_free = maxfree_right(root, rlist); \ | |||||
root->left = rlist; \ | root->left = rlist; \ | ||||
rlist = root; \ | rlist = root; \ | ||||
root = y; \ | root = y; \ | ||||
} while (0) | } while (0) | ||||
#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \ | #define SPLAY_RIGHT_STEP(root, y, llist, test) do { \ | ||||
y = root->right; \ | y = root->right; \ | ||||
if (y != NULL && (test)) { \ | if (y != NULL && (test)) { \ | ||||
/* Rotate left and make y root. */ \ | /* Rotate left and make y root. */ \ | ||||
root->right = y->left; \ | root->right = y->left; \ | ||||
y->left = root; \ | 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)); \ | |||||
root = y; \ | root = y; \ | ||||
y = root->right; \ | y = root->right; \ | ||||
} \ | } \ | ||||
/* Put root on llist. */ \ | /* Put root on llist. */ \ | ||||
root->max_free = maxfree_left(root, llist); \ | |||||
root->right = llist; \ | root->right = llist; \ | ||||
llist = root; \ | llist = root; \ | ||||
root = y; \ | root = y; \ | ||||
} while (0) | } while (0) | ||||
/* | /* | ||||
* Walk down the tree until we find addr or a NULL pointer where addr would go, | * 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 | * 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. | * 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 | * 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 | * linked by the right pointer and rlist linked by the left pointer in the | ||||
* vm_map_entry. | * vm_map_entry. | ||||
*/ | */ | ||||
static vm_map_entry_t | static vm_map_entry_t | ||||
vm_map_splay_split(vm_offset_t addr, vm_size_t length, | 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 llist, rlist; | ||||
vm_map_entry_t y; | vm_map_entry_t y; | ||||
llist = NULL; | llist = *io_llist; | ||||
rlist = NULL; | rlist = *io_rlist; | ||||
while (root != NULL && root->max_free >= length) { | while (root != NULL && root->max_free >= length) { | ||||
if (addr < root->start) { | if (addr < root->start) { | ||||
SPLAY_LEFT_STEP(root, y, rlist, | SPLAY_LEFT_STEP(root, y, rlist, | ||||
y->max_free >= length && addr < y->start); | y->max_free >= length && addr < y->start); | ||||
} else if (addr >= root->end) { | } else if (addr >= root->end) { | ||||
SPLAY_RIGHT_STEP(root, y, llist, | SPLAY_RIGHT_STEP(root, y, llist, | ||||
y->max_free >= length && addr >= y->end); | y->max_free >= length && addr >= y->end); | ||||
} else | } else | ||||
break; | break; | ||||
} | } | ||||
*out_llist = llist; | *io_llist = llist; | ||||
*out_rlist = rlist; | *io_rlist = rlist; | ||||
return (root); | return (root); | ||||
} | } | ||||
static void | static void | ||||
vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist) | vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist) | ||||
{ | { | ||||
vm_map_entry_t rlist, y; | vm_map_entry_t rlist, y; | ||||
Show All 14 Lines | |||||
SPLAY_RIGHT_STEP(root, y, llist, true); | SPLAY_RIGHT_STEP(root, y, llist, true); | ||||
*iolist = llist; | *iolist = llist; | ||||
} | } | ||||
/* | /* | ||||
* Walk back up the two spines, flip the pointers and set max_free. The | * 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. | * 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_splay_merge(vm_map_entry_t root, | ||||
vm_map_entry_t llist, vm_map_entry_t rlist, | vm_map_entry_t llist, vm_map_entry_t rlist) | ||||
vm_map_entry_t ltree, vm_map_entry_t rtree) | |||||
{ | { | ||||
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; | y = llist->right; | ||||
llist->right = ltree; | llist->right = tree; | ||||
vm_map_entry_set_max_free(llist); | if (llist->max_free < max_free) | ||||
ltree = llist; | llist->max_free = max_free; | ||||
else | |||||
max_free = llist->max_free; | |||||
tree = llist; | |||||
llist = y; | 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; | y = rlist->left; | ||||
rlist->left = rtree; | rlist->left = tree; | ||||
vm_map_entry_set_max_free(rlist); | if (rlist->max_free < max_free) | ||||
rtree = rlist; | rlist->max_free = max_free; | ||||
else | |||||
max_free = rlist->max_free; | |||||
tree = rlist; | |||||
rlist = y; | rlist = y; | ||||
} | } | ||||
root->right = tree; | |||||
/* | root->max_free = | ||||
* Final assembly: add ltree and rtree as subtrees of root. | MAX(maxfree_left(root, llist), maxfree_right(root, rlist)); | ||||
*/ | |||||
root->left = ltree; | |||||
root->right = rtree; | |||||
vm_map_entry_set_max_free(root); | |||||
return (root); | |||||
} | } | ||||
/* | /* | ||||
* vm_map_entry_splay: | * vm_map_entry_splay: | ||||
* | * | ||||
* The Sleator and Tarjan top-down splay algorithm with the | * The Sleator and Tarjan top-down splay algorithm with the | ||||
* following variation. Max_free must be computed bottom-up, so | * following variation. Max_free must be computed bottom-up, so | ||||
* on the downward pass, maintain the left and right spines in | * on the downward pass, maintain the left and right spines in | ||||
* reverse order. Then, make a second pass up each side to fix | * reverse order. Then, make a second pass up each side to fix | ||||
* the pointers and compute max_free. The time bound is O(log n) | * the pointers and compute max_free. The time bound is O(log n) | ||||
* amortized. | * amortized. | ||||
* | * | ||||
* The new root is the vm_map_entry containing "addr", or else an | * 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. | * adjacent entry (lower if possible) if addr is not in the tree. | ||||
* | * | ||||
* The map must be locked, and leaves it so. | * The map must be locked, and leaves it so. | ||||
* | * | ||||
* Returns: the new root. | * Returns: the new root. | ||||
*/ | */ | ||||
static vm_map_entry_t | 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); | llist = rlist = &map->header; | ||||
root = vm_map_splay_split(addr, 0, map->root, &llist, &rlist); | |||||
if (root != NULL) { | if (root != NULL) { | ||||
/* do nothing */ | /* do nothing */ | ||||
} else if (llist != NULL) { | } else if ((llist->eflags & MAP_ENTRY_HEADER) == 0) { | ||||
/* | /* | ||||
* Recover the greatest node in the left | * Recover the greatest node in the left | ||||
* subtree and make it the root. | * subtree and make it the root. | ||||
*/ | */ | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = NULL; | root->right = NULL; | ||||
} else if (rlist != NULL) { | } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { | ||||
/* | /* | ||||
Done Inline ActionsWith this change, I would have expected the removal of entry_ from the function's name. In general, there is increasing inconsistency in the use of vm_map_entry_ versus vm_map_. alc: With this change, I would have expected the removal of entry_ from the function's name. In… | |||||
* Recover the least node in the right | * Recover the least node in the right | ||||
* subtree and make it the root. | * subtree and make it the root. | ||||
*/ | */ | ||||
root = rlist; | root = rlist; | ||||
rlist = root->left; | rlist = root->left; | ||||
root->left = NULL; | root->left = NULL; | ||||
} else { | } else { | ||||
/* There is no root. */ | /* There is no root. */ | ||||
return (NULL); | return (NULL); | ||||
} | } | ||||
return (vm_map_splay_merge(root, llist, rlist, | vm_map_splay_merge(root, llist, rlist); | ||||
root->left, root->right)); | return (root); | ||||
} | } | ||||
/* | /* | ||||
* vm_map_entry_{un,}link: | * vm_map_entry_{un,}link: | ||||
* | * | ||||
* Insert/remove entries from maps. | * Insert/remove entries from maps. | ||||
*/ | */ | ||||
static void | static void | ||||
vm_map_entry_link(vm_map_t map, | vm_map_entry_link(vm_map_t map, | ||||
vm_map_entry_t entry) | vm_map_entry_t entry) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist, root; | vm_map_entry_t llist, rlist, root, y; | ||||
CTR3(KTR_VM, | CTR3(KTR_VM, | ||||
"vm_map_entry_link: map %p, nentries %d, entry %p", map, | "vm_map_entry_link: map %p, nentries %d, entry %p", map, | ||||
map->nentries, entry); | map->nentries, entry); | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
VM_MAP_ASSERT_CONSISTENT(map); | |||||
map->nentries++; | map->nentries++; | ||||
root = map->root; | llist = rlist = &map->header; | ||||
root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); | root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist); | ||||
KASSERT(root == NULL, | entry->left = entry->right = NULL; | ||||
("vm_map_entry_link: link object already mapped")); | if (root != NULL && | ||||
entry->prev = (llist == NULL) ? &map->header : llist; | entry->start == root->start && entry->end < root->end) { | ||||
entry->next = (rlist == NULL) ? &map->header : rlist; | vm_map_splay_findprev(root, &llist); | ||||
entry->prev->next = entry->next->prev = entry; | SPLAY_LEFT_STEP(root, y, rlist, false); | ||||
root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL); | 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; | map->root = entry; | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
} | } | ||||
enum unlink_merge_type { | enum unlink_merge_type { | ||||
UNLINK_MERGE_PREV, | UNLINK_MERGE_PREV, | ||||
UNLINK_MERGE_NONE, | UNLINK_MERGE_NONE, | ||||
Done Inline ActionsUnnecessary parentheses. alc: Unnecessary parentheses. | |||||
UNLINK_MERGE_NEXT | UNLINK_MERGE_NEXT | ||||
}; | }; | ||||
Done Inline ActionsIncorrect indentation. alc: Incorrect indentation. | |||||
static void | static void | ||||
vm_map_entry_unlink(vm_map_t map, | vm_map_entry_unlink(vm_map_t map, | ||||
vm_map_entry_t entry, | vm_map_entry_t entry, | ||||
enum unlink_merge_type op) | enum unlink_merge_type op) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist, root, y; | vm_map_entry_t llist, rlist, root, y; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
llist = entry->prev; | VM_MAP_ASSERT_CONSISTENT(map); | ||||
rlist = entry->next; | llist = rlist = &map->header; | ||||
llist->next = rlist; | root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist); | ||||
rlist->prev = llist; | |||||
root = map->root; | |||||
root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); | |||||
KASSERT(root != NULL, | KASSERT(root != NULL, | ||||
("vm_map_entry_unlink: unlink object not mapped")); | ("vm_map_entry_unlink: unlink object not mapped")); | ||||
switch (op) { | switch (op) { | ||||
case UNLINK_MERGE_PREV: | case UNLINK_MERGE_PREV: | ||||
vm_map_splay_findprev(root, &llist); | vm_map_splay_findprev(root, &llist); | ||||
llist->end = root->end; | llist->end = root->end; | ||||
y = root->right; | y = root->right; | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = y; | root->right = y; | ||||
break; | break; | ||||
case UNLINK_MERGE_NEXT: | case UNLINK_MERGE_NEXT: | ||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
rlist->start = root->start; | rlist->start = root->start; | ||||
rlist->offset = root->offset; | rlist->offset = root->offset; | ||||
y = root->left; | y = root->left; | ||||
root = rlist; | root = rlist; | ||||
rlist = root->left; | rlist = root->left; | ||||
root->left = y; | root->left = y; | ||||
break; | break; | ||||
case UNLINK_MERGE_NONE: | case UNLINK_MERGE_NONE: | ||||
vm_map_splay_findprev(root, &llist); | vm_map_splay_findprev(root, &llist); | ||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
if (llist != NULL) { | if ((llist->eflags & MAP_ENTRY_HEADER) == 0) { | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = NULL; | root->right = NULL; | ||||
} else if (rlist != NULL) { | } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { | ||||
root = rlist; | root = rlist; | ||||
rlist = root->left; | rlist = root->left; | ||||
root->left = NULL; | root->left = NULL; | ||||
} else | } else | ||||
root = NULL; | root = NULL; | ||||
break; | break; | ||||
} | } | ||||
y = entry->next; | |||||
y->prev = entry->prev; | |||||
y->prev->next = y; | |||||
if (root != NULL) | if (root != NULL) | ||||
root = vm_map_splay_merge(root, llist, rlist, | vm_map_splay_merge(root, llist, rlist); | ||||
root->left, root->right); | |||||
map->root = root; | map->root = root; | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
map->nentries--; | map->nentries--; | ||||
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map, | CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map, | ||||
map->nentries, entry); | map->nentries, entry); | ||||
} | } | ||||
/* | /* | ||||
* vm_map_entry_resize_free: | * vm_map_entry_resize_free: | ||||
* | * | ||||
* Recompute the amount of free space following a modified vm_map_entry | * Recompute the amount of free space following a modified vm_map_entry | ||||
* and propagate those values up the tree. Call this function after | * and propagate those values up the tree. Call this function after | ||||
* resizing a map entry in-place by changing the end value, without a | * resizing a map entry in-place by changing the end value, without a | ||||
* call to vm_map_entry_link() or _unlink(). | * call to vm_map_entry_link() or _unlink(). | ||||
* | * | ||||
* The map must be locked, and leaves it so. | * The map must be locked, and leaves it so. | ||||
*/ | */ | ||||
static void | 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_entry_t llist, rlist, root; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
root = map->root; | VM_MAP_ASSERT_CONSISTENT(map); | ||||
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, | KASSERT(root != NULL, | ||||
("vm_map_entry_resize_free: resize_free object not mapped")); | ("vm_map_entry_resize_free: resize_free object not mapped")); | ||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
root->right = NULL; | root->right = NULL; | ||||
map->root = vm_map_splay_merge(root, llist, rlist, | entry->end += grow_amount; | ||||
root->left, root->right); | vm_map_splay_merge(root, llist, rlist); | ||||
map->root = root; | |||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map, | CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map, | ||||
map->nentries, entry); | map->nentries, entry); | ||||
} | } | ||||
/* | /* | ||||
* vm_map_lookup_entry: [ internal use only ] | * vm_map_lookup_entry: [ internal use only ] | ||||
* | * | ||||
Show All 14 Lines | |||||
if ((locked = vm_map_locked(map)) || | if ((locked = vm_map_locked(map)) || | ||||
sx_try_upgrade(&map->lock)) { | sx_try_upgrade(&map->lock)) { | ||||
/* | /* | ||||
* Splay requires a write lock on the map. However, it only | * Splay requires a write lock on the map. However, it only | ||||
* restructures the binary search tree; it does not otherwise | * restructures the binary search tree; it does not otherwise | ||||
* change the map. Thus, the map's timestamp need not change | * change the map. Thus, the map's timestamp need not change | ||||
* on a temporary upgrade. | * on a temporary upgrade. | ||||
*/ | */ | ||||
map->root = cur = vm_map_entry_splay(address, cur); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
map->root = cur = vm_map_entry_splay(address, map); | |||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
if (!locked) | if (!locked) | ||||
sx_downgrade(&map->lock); | sx_downgrade(&map->lock); | ||||
/* | /* | ||||
* If "address" is contained within a map entry, the new root | * If "address" is contained within a map entry, the new root | ||||
* is that map entry. Otherwise, the new root is a map entry | * is that map entry. Otherwise, the new root is a map entry | ||||
* immediately before or after "address". | * immediately before or after "address". | ||||
Show All 14 Lines | |||||
prev_entry->protection == prot && | prev_entry->protection == prot && | ||||
prev_entry->max_protection == max && | prev_entry->max_protection == max && | ||||
prev_entry->wired_count == 0) { | prev_entry->wired_count == 0) { | ||||
KASSERT((prev_entry->eflags & MAP_ENTRY_USER_WIRED) == | KASSERT((prev_entry->eflags & MAP_ENTRY_USER_WIRED) == | ||||
0, ("prev_entry %p has incoherent wiring", | 0, ("prev_entry %p has incoherent wiring", | ||||
prev_entry)); | prev_entry)); | ||||
if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0) | if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0) | ||||
map->size += end - prev_entry->end; | 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); | vm_map_simplify_entry(map, prev_entry); | ||||
return (KERN_SUCCESS); | return (KERN_SUCCESS); | ||||
} | } | ||||
/* | /* | ||||
* If we can extend the object but cannot extend the | * If we can extend the object but cannot extend the | ||||
* map entry, we have to create a new map entry. We | * map entry, we have to create a new map entry. We | ||||
* must bump the ref count on the extended object to | * must bump the ref count on the extended object to | ||||
Show All 14 Lines | |||||
/* Empty tree means wide open address space. */ | /* Empty tree means wide open address space. */ | ||||
if (map->root == NULL) | if (map->root == NULL) | ||||
return (start); | return (start); | ||||
/* | /* | ||||
* After splay, if start comes before root node, then there | * After splay, if start comes before root node, then there | ||||
* must be a gap from start to the root. | * must be a gap from start to the root. | ||||
*/ | */ | ||||
root = vm_map_splay_split(start, length, map->root, | VM_MAP_ASSERT_CONSISTENT(map); | ||||
&llist, &rlist); | llist = rlist = &map->header; | ||||
root = vm_map_splay_split(start, length, map->root, &llist, &rlist); | |||||
if (root != NULL) | if (root != NULL) | ||||
start = root->end; | start = root->end; | ||||
else if (rlist != NULL) { | else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { | ||||
root = rlist; | root = rlist; | ||||
rlist = root->left; | rlist = root->left; | ||||
root->left = NULL; | root->left = NULL; | ||||
} else { | } else { | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = NULL; | root->right = NULL; | ||||
} | } | ||||
map->root = vm_map_splay_merge(root, llist, rlist, | vm_map_splay_merge(root, llist, rlist); | ||||
root->left, root->right); | map->root = root; | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
if (start + length <= root->start) | if (start + length <= root->start) | ||||
return (start); | return (start); | ||||
/* | /* | ||||
* Root is the last node that might begin its gap before | * Root is the last node that might begin its gap before | ||||
* start, and this is the last comparison where address | * start, and this is the last comparison where address | ||||
* wrap might be a problem. | * wrap might be a problem. | ||||
*/ | */ | ||||
if (root->right == NULL && | if (root->right == NULL && | ||||
start + length <= vm_map_max(map)) | start + length <= vm_map_max(map)) | ||||
return (start); | return (start); | ||||
/* With max_free, can immediately tell if no solution. */ | /* With max_free, can immediately tell if no solution. */ | ||||
if (root->right == NULL || length > root->right->max_free) | if (root->right == NULL || length > root->right->max_free) | ||||
return (vm_map_max(map) - length + 1); | return (vm_map_max(map) - length + 1); | ||||
/* | /* | ||||
* Splay for the least large-enough gap in the right subtree. | * Splay for the least large-enough gap in the right subtree. | ||||
*/ | */ | ||||
llist = NULL; | llist = rlist = &map->header; | ||||
rlist = NULL; | |||||
for (left_length = 0; ; | for (left_length = 0; ; | ||||
left_length = root->left != NULL ? | left_length = maxfree_left(root, llist)) { | ||||
root->left->max_free : root->start - llist->end) { | |||||
if (length <= left_length) | if (length <= left_length) | ||||
SPLAY_LEFT_STEP(root, y, rlist, | SPLAY_LEFT_STEP(root, y, rlist, | ||||
length <= (y->left != NULL ? | length <= maxfree_left(y, llist)); | ||||
y->left->max_free : y->start - llist->end)); | |||||
else | else | ||||
SPLAY_RIGHT_STEP(root, y, llist, | SPLAY_RIGHT_STEP(root, y, llist, | ||||
length > (y->left != NULL ? | length > maxfree_left(y, root)); | ||||
y->left->max_free : y->start - root->end)); | |||||
if (root == NULL) | if (root == NULL) | ||||
break; | break; | ||||
} | } | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
if ((y = rlist) == NULL) | if (rlist == &map->header) | ||||
root->right = NULL; | root->right = NULL; | ||||
else { | else { | ||||
y = rlist; | |||||
rlist = y->left; | rlist = y->left; | ||||
y->left = NULL; | y->left = NULL; | ||||
root->right = y->right; | vm_map_splay_merge(y, &map->header, rlist); | ||||
} | y->max_free = MAX(y->start - root->end, | ||||
root = vm_map_splay_merge(root, llist, rlist, | maxfree_right(y, &map->header)); | ||||
root->left, root->right); | |||||
if (y != NULL) { | |||||
y->right = root->right; | |||||
vm_map_entry_set_max_free(y); | |||||
root->right = y; | root->right = y; | ||||
vm_map_entry_set_max_free(root); | |||||
} | } | ||||
vm_map_splay_merge(root, llist, &map->header); | |||||
map->root = root; | map->root = root; | ||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
return (root->end); | return (root->end); | ||||
} | } | ||||
int | int | ||||
vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset, | vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset, | ||||
vm_offset_t start, vm_size_t length, vm_prot_t prot, | vm_offset_t start, vm_size_t length, vm_prot_t prot, | ||||
Show All 14 Lines | |||||
VM_OBJECT_WUNLOCK(entry->object.vm_object); | VM_OBJECT_WUNLOCK(entry->object.vm_object); | ||||
entry->cred = NULL; | entry->cred = NULL; | ||||
} | } | ||||
new_entry = vm_map_entry_create(map); | new_entry = vm_map_entry_create(map); | ||||
*new_entry = *entry; | *new_entry = *entry; | ||||
new_entry->end = start; | new_entry->end = start; | ||||
entry->offset += (start - entry->start); | |||||
entry->start = start; | |||||
if (new_entry->cred != NULL) | if (new_entry->cred != NULL) | ||||
crhold(entry->cred); | crhold(entry->cred); | ||||
vm_map_entry_link(map, new_entry); | vm_map_entry_link(map, new_entry); | ||||
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { | if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { | ||||
vm_object_reference(new_entry->object.vm_object); | vm_object_reference(new_entry->object.vm_object); | ||||
/* | /* | ||||
Show All 14 Lines | |||||
} | } | ||||
/* | /* | ||||
* Create a new entry and insert it AFTER the specified entry | * Create a new entry and insert it AFTER the specified entry | ||||
*/ | */ | ||||
new_entry = vm_map_entry_create(map); | new_entry = vm_map_entry_create(map); | ||||
*new_entry = *entry; | *new_entry = *entry; | ||||
new_entry->start = entry->end = end; | new_entry->start = end; | ||||
new_entry->offset += (end - entry->start); | new_entry->offset += (end - entry->start); | ||||
if (new_entry->cred != NULL) | if (new_entry->cred != NULL) | ||||
crhold(entry->cred); | crhold(entry->cred); | ||||
vm_map_entry_link(map, new_entry); | vm_map_entry_link(map, new_entry); | ||||
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { | if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { | ||||
vm_object_reference(new_entry->object.vm_object); | vm_object_reference(new_entry->object.vm_object); | ||||
Show All 14 Lines | |||||
grow_start = gap_entry->end - grow_amount; | grow_start = gap_entry->end - grow_amount; | ||||
if (gap_entry->start + grow_amount == gap_entry->end) { | if (gap_entry->start + grow_amount == gap_entry->end) { | ||||
gap_start = gap_entry->start; | gap_start = gap_entry->start; | ||||
gap_end = gap_entry->end; | gap_end = gap_entry->end; | ||||
vm_map_entry_delete(map, gap_entry); | vm_map_entry_delete(map, gap_entry); | ||||
gap_deleted = true; | gap_deleted = true; | ||||
} else { | } else { | ||||
MPASS(gap_entry->start < gap_entry->end - grow_amount); | MPASS(gap_entry->start < gap_entry->end - grow_amount); | ||||
gap_entry->end -= grow_amount; | vm_map_entry_resize_free(map, gap_entry, -grow_amount); | ||||
vm_map_entry_resize_free(map, gap_entry); | |||||
gap_deleted = false; | gap_deleted = false; | ||||
} | } | ||||
rv = vm_map_insert(map, NULL, 0, grow_start, | rv = vm_map_insert(map, NULL, 0, grow_start, | ||||
grow_start + grow_amount, | grow_start + grow_amount, | ||||
stack_entry->protection, stack_entry->max_protection, | stack_entry->protection, stack_entry->max_protection, | ||||
MAP_STACK_GROWS_DOWN); | MAP_STACK_GROWS_DOWN); | ||||
if (rv != KERN_SUCCESS) { | if (rv != KERN_SUCCESS && gap_deleted) { | ||||
if (gap_deleted) { | rv1 = vm_map_insert(map, NULL, 0, gap_start, | ||||
rv1 = vm_map_insert(map, NULL, 0, gap_start, | gap_end, VM_PROT_NONE, VM_PROT_NONE, | ||||
gap_end, VM_PROT_NONE, VM_PROT_NONE, | MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN); | ||||
MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN); | MPASS(rv1 == KERN_SUCCESS); | ||||
MPASS(rv1 == KERN_SUCCESS); | } else if (rv != KERN_SUCCESS) | ||||
} else { | vm_map_entry_resize_free(map, gap_entry, grow_amount); | ||||
gap_entry->end += grow_amount; | |||||
vm_map_entry_resize_free(map, gap_entry); | |||||
} | |||||
} | |||||
} else { | } else { | ||||
grow_start = stack_entry->end; | grow_start = stack_entry->end; | ||||
cred = stack_entry->cred; | cred = stack_entry->cred; | ||||
if (cred == NULL && stack_entry->object.vm_object != NULL) | if (cred == NULL && stack_entry->object.vm_object != NULL) | ||||
cred = stack_entry->object.vm_object->cred; | cred = stack_entry->object.vm_object->cred; | ||||
if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred)) | if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred)) | ||||
rv = KERN_NO_SPACE; | rv = KERN_NO_SPACE; | ||||
/* Grow the underlying object if applicable. */ | /* Grow the underlying object if applicable. */ | ||||
else if (stack_entry->object.vm_object == NULL || | else if (stack_entry->object.vm_object == NULL || | ||||
vm_object_coalesce(stack_entry->object.vm_object, | vm_object_coalesce(stack_entry->object.vm_object, | ||||
stack_entry->offset, | stack_entry->offset, | ||||
(vm_size_t)(stack_entry->end - stack_entry->start), | (vm_size_t)(stack_entry->end - stack_entry->start), | ||||
(vm_size_t)grow_amount, cred != NULL)) { | (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); | vm_map_entry_delete(map, gap_entry); | ||||
else | vm_map_entry_resize_free(map, stack_entry, grow_amount); | ||||
} else { | |||||
gap_entry->start += grow_amount; | gap_entry->start += grow_amount; | ||||
stack_entry->end += grow_amount; | stack_entry += grow_amount; | ||||
} | |||||
map->size += grow_amount; | map->size += grow_amount; | ||||
vm_map_entry_resize_free(map, stack_entry); | |||||
rv = KERN_SUCCESS; | rv = KERN_SUCCESS; | ||||
} else | } else | ||||
rv = KERN_FAILURE; | rv = KERN_FAILURE; | ||||
} | } | ||||
if (rv == KERN_SUCCESS && is_procstack) | if (rv == KERN_SUCCESS && is_procstack) | ||||
vm->vm_ssize += btoc(grow_amount); | vm->vm_ssize += btoc(grow_amount); | ||||
/* | /* | ||||
* Heed the MAP_WIREFUTURE flag if it was set for this process. | * Heed the MAP_WIREFUTURE flag if it was set for this process. | ||||
*/ | */ | ||||
if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE) != 0) { | if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE) != 0) { | ||||
vm_map_unlock(map); | vm_map_unlock(map); | ||||
vm_map_wire(map, grow_start, grow_start + grow_amount, | vm_map_wire(map, grow_start, grow_start + grow_amount, | ||||
VM_MAP_WIRE_USER | VM_MAP_WIRE_NOHOLES); | VM_MAP_WIRE_USER | VM_MAP_WIRE_NOHOLES); | ||||
vm_map_lock_read(map); | vm_map_lock_read(map); | ||||
Context not available. |
vm_map_maxfree_left, please honor the symbols namespace.