Changeset View
Changeset View
Standalone View
Standalone View
head/sys/vm/vm_map.c
Show First 20 Lines • Show All 956 Lines • ▼ Show 20 Lines | |||||
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: | * 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 | static inline vm_size_t | ||||
vm_map_entry_set_max_free(vm_map_entry_t entry) | 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; | return (root->left != NULL ? | ||||
max_left = (child != NULL) ? child->max_free : | root->left->max_free : root->start - left_ancestor->end); | ||||
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 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 { \ | #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; \ | 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)) { \ | 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; \ | ||||
vm_map_entry_set_max_free(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; \ | root = y; \ | ||||
y = root->left; \ | y = root->left; \ | ||||
} \ | } \ | ||||
/* Put root on rlist. */ \ | /* 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; \ | 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 { \ | ||||
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; \ | 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)) { \ | 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 (max_free < y->max_free) \ | ||||
root->max_free = max_free = MAX(max_free, \ | |||||
vm_map_entry_max_free_right(root, y)); \ | |||||
root = y; \ | root = y; \ | ||||
y = root->right; \ | y = root->right; \ | ||||
} \ | } \ | ||||
/* Put root on llist. */ \ | /* 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; \ | 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, 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 | static vm_map_entry_t | ||||
vm_map_splay_split(vm_offset_t addr, vm_size_t length, | vm_map_splay_split(vm_map_t map, 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 *out_llist, vm_map_entry_t *out_rlist) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist; | vm_map_entry_t llist, rlist, root, y; | ||||
vm_map_entry_t y; | |||||
llist = NULL; | llist = rlist = &map->header; | ||||
rlist = NULL; | root = map->root; | ||||
while (root != NULL && root->max_free >= length) { | 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) { | 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; | ||||
Show All 22 Lines | vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist) | ||||
root = root->left; | root = root->left; | ||||
llist = *iolist; | llist = *iolist; | ||||
while (root != NULL) | while (root != NULL) | ||||
SPLAY_RIGHT_STEP(root, y, llist, true); | SPLAY_RIGHT_STEP(root, y, llist, true); | ||||
*iolist = llist; | *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 | * 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_t map, 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 prev; | ||||
vm_size_t max_free_left, max_free_right; | |||||
while (llist != NULL) { | max_free_left = vm_map_entry_max_free_left(root, llist); | ||||
y = llist->right; | if (llist != &map->header) { | ||||
llist->right = ltree; | prev = root->left; | ||||
vm_map_entry_set_max_free(llist); | do { | ||||
ltree = llist; | /* | ||||
llist = y; | * 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) { | max_free_right = vm_map_entry_max_free_right(root, rlist); | ||||
y = rlist->left; | if (rlist != &map->header) { | ||||
rlist->left = rtree; | prev = root->right; | ||||
vm_map_entry_set_max_free(rlist); | do { | ||||
rtree = rlist; | |||||
rlist = y; | |||||
} | |||||
/* | /* | ||||
* Final assembly: add ltree and rtree as subtrees of root. | * The max_free values of the children of rlist are in | ||||
* rlist->max_free and max_free_right. Update with the | |||||
* max value. | |||||
*/ | */ | ||||
root->left = ltree; | rlist->max_free = max_free_right = | ||||
root->right = rtree; | MAX(rlist->max_free, max_free_right); | ||||
vm_map_entry_set_max_free(root); | vm_map_entry_swap(&rlist->left, &prev); | ||||
vm_map_entry_swap(&prev, &rlist); | |||||
return (root); | } 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 | * 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_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) { | if (root != NULL) { | ||||
/* do nothing */ | /* do nothing */ | ||||
} else if (llist != NULL) { | } else if (llist != &map->header) { | ||||
/* | /* | ||||
* 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 != &map->header) { | ||||
/* | /* | ||||
* 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(map, root, llist, rlist); | ||||
root->left, root->right)); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
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; | ||||
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); | ||||
map->nentries++; | map->nentries++; | ||||
root = map->root; | root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | ||||
root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); | |||||
KASSERT(root == NULL, | KASSERT(root == NULL, | ||||
("vm_map_entry_link: link object already mapped")); | ("vm_map_entry_link: link object already mapped")); | ||||
entry->prev = (llist == NULL) ? &map->header : llist; | entry->prev = llist; | ||||
entry->next = (rlist == NULL) ? &map->header : rlist; | entry->next = rlist; | ||||
entry->prev->next = entry->next->prev = entry; | llist->next = rlist->prev = entry; | ||||
root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL); | entry->left = entry->right = NULL; | ||||
map->root = entry; | vm_map_splay_merge(map, entry, llist, rlist); | ||||
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, | ||||
UNLINK_MERGE_NEXT | UNLINK_MERGE_NEXT | ||||
}; | }; | ||||
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; | root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | ||||
rlist = entry->next; | |||||
llist->next = 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 != &map->header) { | ||||
root = llist; | root = llist; | ||||
llist = root->right; | llist = root->right; | ||||
root->right = NULL; | root->right = NULL; | ||||
} else if (rlist != NULL) { | } else if (rlist != &map->header) { | ||||
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(map, root, llist, rlist); | ||||
root->left, root->right); | else | ||||
map->root = root; | map->root = NULL; | ||||
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: | * vm_map_entry_resize: | ||||
* | * | ||||
* Resize a vm_map_entry, recompute the amount of free space that | * Resize a vm_map_entry, recompute the amount of free space that | ||||
* follows it and propagate that value up the tree. | * follows it and propagate that value up the tree. | ||||
* | * | ||||
* 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(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount) | vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_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; | root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); | ||||
root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); | |||||
KASSERT(root != NULL, | KASSERT(root != NULL, | ||||
("%s: resize object not mapped", __func__)); | ("%s: resize object not mapped", __func__)); | ||||
vm_map_splay_findnext(root, &rlist); | vm_map_splay_findnext(root, &rlist); | ||||
root->right = NULL; | root->right = NULL; | ||||
entry->end += grow_amount; | entry->end += grow_amount; | ||||
map->root = vm_map_splay_merge(root, llist, rlist, | vm_map_splay_merge(map, root, llist, rlist); | ||||
root->left, root->right); | |||||
VM_MAP_ASSERT_CONSISTENT(map); | VM_MAP_ASSERT_CONSISTENT(map); | ||||
CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p", | CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p", | ||||
__func__, map, map->nentries, entry); | __func__, map, map->nentries, entry); | ||||
} | } | ||||
/* | /* | ||||
* vm_map_lookup_entry: [ internal use only ] | * vm_map_lookup_entry: [ internal use only ] | ||||
* | * | ||||
Show All 29 Lines | vm_map_lookup_entry( | ||||
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); | cur = vm_map_splay(map, address); | ||||
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 20 Lines • Show All 270 Lines • ▼ Show 20 Lines | vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length) | ||||
/* 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, | root = vm_map_splay_split(map, start, length, &llist, &rlist); | ||||
&llist, &rlist); | |||||
if (root != NULL) | if (root != NULL) | ||||
start = root->end; | start = root->end; | ||||
else if (rlist != NULL) { | else if (rlist != &map->header) { | ||||
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(map, root, llist, rlist); | ||||
root->left, root->right); | |||||
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 = vm_map_entry_max_free_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 <= vm_map_entry_max_free_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 > vm_map_entry_max_free_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) | |||||
root->right = NULL; | root->right = NULL; | ||||
else { | if (rlist != &map->header) { | ||||
y = rlist; | |||||
rlist = y->left; | rlist = y->left; | ||||
y->left = NULL; | y->left = NULL; | ||||
root->right = y->right; | vm_map_splay_merge(map, y, &map->header, rlist); | ||||
} | y->max_free = MAX( | ||||
root = vm_map_splay_merge(root, llist, rlist, | vm_map_entry_max_free_left(y, root), | ||||
root->left, root->right); | vm_map_entry_max_free_right(y, &map->header)); | ||||
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); | |||||
} | } | ||||
map->root = root; | vm_map_splay_merge(map, root, llist, &map->header); | ||||
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, | ||||
vm_prot_t max, int cow) | vm_prot_t max, int cow) | ||||
▲ Show 20 Lines • Show All 3,193 Lines • Show Last 20 Lines |