Page MenuHomeFreeBSD
Files F113870058

D13999.id38255.diff
No OneTemporary
Actions

D13999.id38255.diff
View Options

Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -796,13 +796,14 @@
{
map->header.next = map->header.prev = &map->header;
+ map->header.left = map->header.right = NULL;
map->needs_wakeup = FALSE;
map->system_map = 0;
map->pmap = pmap;
map->min_offset = min;
map->max_offset = max;
map->flags = 0;
- map->root = NULL;
+ map->root = &map->header;
map->timestamp = 0;
map->busy = 0;
}
@@ -900,10 +901,6 @@
vm_map_entry_t ltree, rtree;
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
* pointer where addr would go. llist and rlist are the two
@@ -914,31 +911,11 @@
*/
llist = NULL;
rlist = NULL;
- for (;;) {
+ do {
/* root is never NULL in here. */
- if (addr < root->start) {
- 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) {
+ if (addr >= root->end) {
y = root->right;
- if (y == NULL)
- break;
- if (addr >= y->end && y->right != NULL) {
+ if (y != NULL && addr >= y->end) {
/* Rotate left and put y on llist. */
root->right = y->left;
y->left = root;
@@ -952,8 +929,36 @@
llist = root;
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
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.
+ */
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
}
/*
@@ -1016,18 +1021,13 @@
entry->next->prev = entry;
after_where->next = entry;
- 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;
- }
+ 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);
entry->adj_free = entry->next->start - entry->end;
vm_map_entry_set_max_free(entry);
map->root = entry;
@@ -1042,14 +1042,10 @@
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);
- }
+ 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;
@@ -1111,13 +1107,11 @@
* "address" is the map's header.
*/
cur = map->root;
- if (cur == NULL)
- *entry = &map->header;
- else if (address >= cur->start && cur->end > address) {
+ if (address >= cur->start && cur->end > address) {
*entry = cur;
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
* restructures the binary search tree; it does not otherwise
@@ -1128,40 +1122,25 @@
if (!locked)
sx_downgrade(&map->lock);
- /*
- * If "address" is contained within a map entry, the new root
- * is that map entry. Otherwise, the new root is a map entry
- * immediately before or after "address".
- */
- if (address >= cur->start) {
- *entry = cur;
- if (cur->end > address)
- return (TRUE);
- } else
- *entry = cur->prev;
+ *entry = cur;
+ if (cur->end > address)
+ return (TRUE);
} else
/*
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
- for (;;) {
- if (address < cur->start) {
- if (cur->left == NULL) {
- *entry = cur->prev;
- break;
- }
+ do {
+ if (cur->end <= address) {
+ *entry = cur;
+ cur = cur->right;
+ } else if (address < cur->start) {
cur = cur->left;
- } else if (cur->end > address) {
+ } else {
*entry = cur;
return (TRUE);
- } else {
- if (cur->right == NULL) {
- *entry = cur;
- break;
- }
- cur = cur->right;
}
- }
+ } while (curr != NULL);
return (FALSE);
}
@@ -1410,20 +1389,11 @@
}
/*
- * 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
* start, and this is the last comparison where address
* wrap might be a problem.
*/
+ map->root = vm_map_entry_splay(start, map->root);
st = (start > map->root->end) ? start : map->root->end;
if (length <= map->root->end + map->root->adj_free - st) {
*addr = st;

File Metadata

Mime Type
text/plain
Expires
Sat, Apr 5, 9:18 PM (9 h, 10 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
17397596
Default Alt Text
D13999.id38255.diff (6 KB)

Event Timeline