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->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_t ltree, rtree; | vm_map_entry_t ltree, rtree; | ||||
vm_map_entry_t y; | vm_map_entry_t y; | ||||
/* Special case of empty tree. */ | |||||
if (root == NULL) | |||||
return (root); | |||||
/* | /* | ||||
* 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 | ||||
* pointer where addr would go. llist and rlist are the two | * pointer where addr would go. llist and rlist are the two | ||||
Context not available. | |||||
*/ | */ | ||||
llist = NULL; | llist = NULL; | ||||
rlist = NULL; | rlist = NULL; | ||||
for (;;) { | do { | ||||
/* root is never NULL in here. */ | /* root is never NULL in here. */ | ||||
if (addr < root->start) { | if (addr >= root->end) { | ||||
y = root->left; | |||||
if (y == NULL) | |||||
break; | |||||
if (addr < y->start && y->left != NULL) { | |||||
/* Rotate right and put y on rlist. */ | |||||
root->left = y->right; | |||||
y->right = root; | |||||
vm_map_entry_set_max_free(root); | |||||
root = y->left; | |||||
y->left = rlist; | |||||
rlist = y; | |||||
} else { | |||||
/* Put root on rlist. */ | |||||
root->left = rlist; | |||||
rlist = root; | |||||
root = y; | |||||
} | |||||
} else if (addr >= root->end) { | |||||
y = root->right; | y = root->right; | ||||
if (y == NULL) | if (y != NULL && addr >= y->end) { | ||||
break; | |||||
if (addr >= y->end && y->right != NULL) { | |||||
/* Rotate left and put y on llist. */ | /* Rotate left and put y on llist. */ | ||||
root->right = y->left; | root->right = y->left; | ||||
y->left = root; | y->left = root; | ||||
Context not available. | |||||
llist = root; | llist = root; | ||||
root = y; | root = y; | ||||
} | } | ||||
} else if (addr < root->start) { | |||||
y = root->left; | |||||
if (y != NULL && addr < y->start) { | |||||
/* Rotate right and put y on rlist. */ | |||||
root->left = y->right; | |||||
y->right = root; | |||||
vm_map_entry_set_max_free(root); | |||||
root = y->left; | |||||
y->left = rlist; | |||||
rlist = y; | |||||
} else { | |||||
/* Put root on rlist. */ | |||||
root->left = rlist; | |||||
rlist = root; | |||||
root = y; | |||||
} | |||||
} else | } else | ||||
break; | break; | ||||
} while (root != NULL); | |||||
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. | |||||
*/ | |||||
if (llist != NULL) { | |||||
root = llist; | |||||
llist = root->right; | |||||
root->right = NULL; | |||||
} else { | |||||
/* addr must lie below the range defined by | |||||
* map->header, so recover the map->header | |||||
* from the right tree instead. | |||||
*/ | |||||
root = rlist; | |||||
rlist = root->left; | |||||
root->left = NULL; | |||||
} | |||||
} | } | ||||
/* | /* | ||||
Context not available. | |||||
entry->next->prev = entry; | entry->next->prev = entry; | ||||
after_where->next = entry; | after_where->next = entry; | ||||
if (after_where != &map->header) { | if (after_where != map->root) | ||||
if (after_where != map->root) | vm_map_entry_splay(after_where->start, map->root); | ||||
vm_map_entry_splay(after_where->start, map->root); | entry->right = after_where->right; | ||||
entry->right = after_where->right; | entry->left = after_where; | ||||
entry->left = after_where; | after_where->right = NULL; | ||||
after_where->right = NULL; | after_where->adj_free = entry->start - after_where->end; | ||||
after_where->adj_free = entry->start - after_where->end; | vm_map_entry_set_max_free(after_where); | ||||
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_entry_set_max_free(entry); | ||||
map->root = entry; | map->root = entry; | ||||
Context not available. | |||||
VM_MAP_ASSERT_LOCKED(map); | VM_MAP_ASSERT_LOCKED(map); | ||||
if (entry != map->root) | if (entry != map->root) | ||||
vm_map_entry_splay(entry->start, map->root); | vm_map_entry_splay(entry->start, map->root); | ||||
if (entry->left == NULL) | root = vm_map_entry_splay(entry->start, entry->left); | ||||
root = entry->right; | root->right = entry->right; | ||||
else { | root->adj_free = entry->next->start - root->end; | ||||
root = vm_map_entry_splay(entry->start, entry->left); | vm_map_entry_set_max_free(root); | ||||
root->right = entry->right; | |||||
root->adj_free = entry->next->start - root->end; | |||||
vm_map_entry_set_max_free(root); | |||||
} | |||||
map->root = root; | map->root = root; | ||||
prev = entry->prev; | prev = entry->prev; | ||||
Context not available. | |||||
* "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 | ||||
Context not available. | |||||
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. | |||||
} | } | ||||
/* | /* | ||||
* 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. | ||||
*/ | */ | ||||
map->root = vm_map_entry_splay(start, map->root); | |||||
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 ?