Changeset View
Changeset View
Standalone View
Standalone View
sys/vm/vm_map.c
Context not available. | |||||
{ | { | ||||
map->header.next = map->header.prev = &map->header; | map->header.next = map->header.prev = &map->header; | ||||
map->header.left = map->header.right = NULL; | |||||
map->header.adj_free = max - min; | |||||
map->header.max_free = map->header.adj_free; | |||||
map->needs_wakeup = FALSE; | map->needs_wakeup = FALSE; | ||||
map->system_map = 0; | map->system_map = 0; | ||||
map->pmap = pmap; | map->pmap = pmap; | ||||
map->min_offset = min; | map->min_offset = min; | ||||
map->max_offset = max; | map->max_offset = max; | ||||
map->flags = 0; | map->flags = 0; | ||||
map->root = NULL; | map->root = &map->header; | ||||
map->timestamp = 0; | map->timestamp = 0; | ||||
map->busy = 0; | map->busy = 0; | ||||
} | } | ||||
Context not available. | |||||
} | } | ||||
/* | /* | ||||
* 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 | ||||
Context not available. | |||||
* 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 | ||||
* adjacent entry (lower or higher) if addr is not in the tree. | * the next lower entry 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. | |||||
*/ | */ | ||||
static vm_map_entry_t | static void | ||||
vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root) | vm_map_splay(vm_offset_t addr, vm_map_t map, vm_map_entry_t *io) | ||||
{ | { | ||||
vm_map_entry_t llist, rlist; | vm_map_entry_t llist, rlist; | ||||
vm_map_entry_t ltree, rtree; | vm_map_entry_t ltree, rtree; | ||||
vm_map_entry_t y; | vm_map_entry_t root, x, y; | ||||
/* Special case of empty tree. */ | KASSERT(addr >= map->min_offset && addr < map->max_offset, | ||||
if (root == NULL) | ("vm_map_splay: addr %jx, offsets start %jx, end %jx", | ||||
return (root); | (uintmax_t)addr, | ||||
(uintmax_t)map->min_offset, (uintmax_t)map->max_offset)); | |||||
/* | /* | ||||
* Pass One: Splay down the tree until we find addr or a NULL | * Pass One: Splay down the tree until we find addr or a NULL | ||||
Context not available. | |||||
*/ | */ | ||||
llist = NULL; | llist = NULL; | ||||
rlist = NULL; | rlist = NULL; | ||||
for (;;) { | root = map->root; | ||||
/* root is never NULL in here. */ | do { | ||||
if (addr < root->start) { | x = root; | ||||
y = root->left; | /* x is never NULL in here. */ | ||||
if (y == NULL) | if (addr >= x->end) { | ||||
break; | y = x->right; | ||||
if (addr < y->start && y->left != NULL) { | if (y != NULL && addr >= y->end) { | ||||
/* Rotate right and put y on rlist. */ | root = y->right; | ||||
root->left = y->right; | /* Rotate left. */ | ||||
y->right = root; | x->right = y->left; | ||||
vm_map_entry_set_max_free(root); | y->left = x; | ||||
vm_map_entry_set_max_free(x); | |||||
/* Put y on llist. */ | |||||
y->right = llist; | |||||
llist = y; | |||||
} else if (y != NULL && addr < y->start) { | |||||
root = y->left; | root = y->left; | ||||
/* Put x on llist. */ | |||||
x->right = llist; | |||||
llist = x; | |||||
/* Put y on rlist */ | |||||
y->left = rlist; | y->left = rlist; | ||||
rlist = y; | rlist = y; | ||||
} else { | } else { | ||||
/* Put root on rlist. */ | |||||
root->left = rlist; | |||||
rlist = root; | |||||
root = y; | root = y; | ||||
} | /* Put x on llist. */ | ||||
} else if (addr >= root->end) { | x->right = llist; | ||||
y = root->right; | llist = x; | ||||
if (y == NULL) | |||||
break; | break; | ||||
if (addr >= y->end && y->right != NULL) { | } | ||||
/* Rotate left and put y on llist. */ | } else if (addr < x->start) { | ||||
root->right = y->left; | y = x->left; | ||||
y->left = root; | if (y != NULL && addr >= y->end) { | ||||
vm_map_entry_set_max_free(root); | |||||
root = y->right; | root = y->right; | ||||
/* Put x on rlist. */ | |||||
x->left = rlist; | |||||
rlist = x; | |||||
/* Put y on llist. */ | |||||
y->right = llist; | y->right = llist; | ||||
llist = y; | llist = y; | ||||
} else if (y != NULL && addr < y->start) { | |||||
root = y->left; | |||||
/* Rotate right. */ | |||||
x->left = y->right; | |||||
y->right = x; | |||||
vm_map_entry_set_max_free(x); | |||||
/* Put y on rlist. */ | |||||
y->left = rlist; | |||||
rlist = y; | |||||
} else { | } else { | ||||
/* Put root on llist. */ | |||||
root->right = llist; | |||||
llist = root; | |||||
root = y; | root = y; | ||||
/* Put x on rlist. */ | |||||
x->left = rlist; | |||||
rlist = x; | |||||
break; | |||||
} | } | ||||
} else | } else | ||||
break; | break; | ||||
} while (root != NULL); | |||||
if (io == NULL) { /* Lookup only. */ | |||||
if (root == NULL) { | |||||
/* | |||||
* With no matching node found, recover the | |||||
* greatest node in the left subtree and make | |||||
* it the root. There is such a node, since | |||||
* map->header is in the tree and left of all | |||||
* addresses. | |||||
*/ | |||||
root = llist; | |||||
llist = root->right; | |||||
root->right = NULL; | |||||
} | |||||
} else if (*io == NULL && root != NULL) { | |||||
/* | |||||
* To delete the found item from the tree, walk the | |||||
* left spine of the found subtree, extending the left | |||||
* spine of the new subtree, so that the predecessor | |||||
* of the found node can be the new root. | |||||
*/ | |||||
rtree = root->right; | |||||
root->right = NULL; | |||||
ltree = root->left; | |||||
root->left = NULL; | |||||
*io = root; | |||||
if (ltree == NULL) { | |||||
root = llist; | |||||
llist = root->right; | |||||
} else { | |||||
root = ltree; | |||||
for(;;) { | |||||
y = root->right; | |||||
if (y == NULL) | |||||
break; | |||||
x = root; | |||||
root = y->right; | |||||
/* Rotate left. */ | |||||
x->right = y->left; | |||||
y->left = x; | |||||
vm_map_entry_set_max_free(x); | |||||
if (root == NULL) { | |||||
root = y; | |||||
break; | |||||
} | |||||
/* Put y on llist. */ | |||||
y->right = llist; | |||||
llist = y; | |||||
} | |||||
} | |||||
root->right = rtree; | |||||
} else if (*io != NULL && root == NULL) { | |||||
/* Install the new item as tree root */ | |||||
root = *io; | |||||
*io = NULL; | |||||
root->left = root->right = NULL; | |||||
} | } | ||||
/* | /* | ||||
Context not available. | |||||
root->right = rtree; | root->right = rtree; | ||||
vm_map_entry_set_max_free(root); | vm_map_entry_set_max_free(root); | ||||
return (root); | map->root = root; | ||||
} | } | ||||
/* | /* | ||||
Context not available. | |||||
entry->next = after_where->next; | entry->next = after_where->next; | ||||
entry->next->prev = entry; | entry->next->prev = entry; | ||||
after_where->next = entry; | after_where->next = entry; | ||||
after_where->adj_free = entry->start - after_where->end; | |||||
if (after_where != &map->header) { | |||||
if (after_where != map->root) | |||||
vm_map_entry_splay(after_where->start, map->root); | |||||
entry->right = after_where->right; | |||||
entry->left = after_where; | |||||
after_where->right = NULL; | |||||
after_where->adj_free = entry->start - after_where->end; | |||||
vm_map_entry_set_max_free(after_where); | |||||
} else { | |||||
entry->right = map->root; | |||||
entry->left = NULL; | |||||
} | |||||
entry->adj_free = entry->next->start - entry->end; | entry->adj_free = entry->next->start - entry->end; | ||||
vm_map_entry_set_max_free(entry); | vm_map_splay(entry->start, map, &entry); | ||||
map->root = entry; | |||||
} | } | ||||
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) | ||||
{ | { | ||||
vm_map_entry_t next, prev, root; | vm_map_entry_t next, prev; | ||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
if (entry != map->root) | |||||
vm_map_entry_splay(entry->start, map->root); | |||||
if (entry->left == NULL) | |||||
root = entry->right; | |||||
else { | |||||
root = vm_map_entry_splay(entry->start, entry->left); | |||||
root->right = entry->right; | |||||
root->adj_free = entry->next->start - root->end; | |||||
vm_map_entry_set_max_free(root); | |||||
} | |||||
map->root = root; | |||||
prev = entry->prev; | prev = entry->prev; | ||||
next = entry->next; | next = entry->next; | ||||
next->prev = prev; | next->prev = prev; | ||||
prev->next = next; | prev->next = next; | ||||
prev->adj_free = next->start - prev->end; | |||||
prev = NULL; | |||||
vm_map_splay(entry->start, map, &prev); | |||||
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); | ||||
Context not available. | |||||
* root and making the change there. | * root and making the change there. | ||||
*/ | */ | ||||
if (entry != map->root) | if (entry != map->root) | ||||
map->root = vm_map_entry_splay(entry->start, map->root); | vm_map_splay(entry->start, map, NULL); | ||||
entry->adj_free = entry->next->start - entry->end; | entry->adj_free = entry->next->start - entry->end; | ||||
vm_map_entry_set_max_free(entry); | vm_map_entry_set_max_free(entry); | ||||
Context not available. | |||||
boolean_t locked; | boolean_t locked; | ||||
/* | /* | ||||
* If the address is out of range, fail immediately. | |||||
*/ | |||||
if (address < map->min_offset || address >= map->max_offset) { | |||||
*entry = &map->header; | |||||
return (FALSE); | |||||
} | |||||
/* | |||||
* If the map is empty, then the map entry immediately preceding | * If the map is empty, then the map entry immediately preceding | ||||
* "address" is the map's header. | * "address" is the map's header. | ||||
*/ | */ | ||||
cur = map->root; | cur = map->root; | ||||
if (cur == NULL) | if (address >= cur->start && cur->end > address) { | ||||
*entry = &map->header; | |||||
else if (address >= cur->start && cur->end > address) { | |||||
*entry = cur; | *entry = cur; | ||||
return (TRUE); | return (TRUE); | ||||
} else if ((locked = vm_map_locked(map)) || | } | ||||
sx_try_upgrade(&map->lock)) { | if ((locked = vm_map_locked(map)) || 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_splay(address, map, NULL); | ||||
cur = map->root; | |||||
if (!locked) | if (!locked) | ||||
sx_downgrade(&map->lock); | sx_downgrade(&map->lock); | ||||
/* | *entry = cur; | ||||
* If "address" is contained within a map entry, the new root | if (cur->end > address) | ||||
* is that map entry. Otherwise, the new root is a map entry | return (TRUE); | ||||
* immediately before or after "address". | |||||
*/ | |||||
if (address >= cur->start) { | |||||
*entry = cur; | |||||
if (cur->end > address) | |||||
return (TRUE); | |||||
} else | |||||
*entry = cur->prev; | |||||
} else | } else | ||||
/* | /* | ||||
* Since the map is only locked for read access, perform a | * Since the map is only locked for read access, perform a | ||||
* standard binary search tree lookup for "address". | * standard binary search tree lookup for "address". | ||||
*/ | */ | ||||
for (;;) { | do { | ||||
if (address < cur->start) { | if (cur->end <= address) { | ||||
if (cur->left == NULL) { | *entry = cur; | ||||
*entry = cur->prev; | cur = cur->right; | ||||
break; | } else if (address < cur->start) { | ||||
} | |||||
cur = cur->left; | cur = cur->left; | ||||
} else if (cur->end > address) { | } else { | ||||
*entry = cur; | *entry = cur; | ||||
return (TRUE); | return (TRUE); | ||||
} else { | |||||
if (cur->right == NULL) { | |||||
*entry = cur; | |||||
break; | |||||
} | |||||
cur = cur->right; | |||||
} | } | ||||
} | } while (cur != NULL); | ||||
return (FALSE); | return (FALSE); | ||||
} | } | ||||
Context not available. | |||||
if (start + length > map->max_offset || start + length < start) | if (start + length > map->max_offset || start + length < start) | ||||
return (1); | return (1); | ||||
/* Empty tree means wide open address space. */ | |||||
if (map->root == NULL) { | |||||
*addr = start; | |||||
return (0); | |||||
} | |||||
/* | |||||
* After splay, if start comes before root node, then there | |||||
* must be a gap from start to the root. | |||||
*/ | |||||
map->root = vm_map_entry_splay(start, map->root); | |||||
if (start + length <= map->root->start) { | |||||
*addr = start; | |||||
return (0); | |||||
} | |||||
/* | /* | ||||
* 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. | ||||
*/ | */ | ||||
vm_map_splay(start, map, NULL); | |||||
st = (start > map->root->end) ? start : map->root->end; | st = (start > map->root->end) ? start : map->root->end; | ||||
if (length <= map->root->end + map->root->adj_free - st) { | if (length <= map->root->end + map->root->adj_free - st) { | ||||
*addr = st; | *addr = st; | ||||
Context not available. | |||||
kib: Change the return type to bool ? | |||||
Done Inline Actions!= NULL kib: != NULL | |||||
Done Inline ActionsBlank line is needed before start of multi-line comment. kib: Blank line is needed before start of multi-line comment. | |||||
Done Inline ActionsAlmost all () there and below are excessive, and no need in space before the excessive '(' at this line. kib: Almost all () there and below are excessive, and no need in space before the excessive '(' at… | |||||
Done Inline ActionsNo need in additional space for indent. kib: No need in additional space for indent. |
Change the return type to bool ?