Page MenuHomeFreeBSD
Files F163385819

D13999.id38331.diff
No OneTemporary
Actions

D13999.id38331.diff
View Options

Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -796,13 +796,16 @@
{
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->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;
}
@@ -898,11 +901,8 @@
{
vm_map_entry_t llist, rlist;
vm_map_entry_t ltree, rtree;
- vm_map_entry_t y;
-
- /* Special case of empty tree. */
- if (root == NULL)
- return (root);
+ vm_map_entry_t x, y;
+ vm_map_entry_t oroot = root;
/*
* Pass One: Splay down the tree until we find addr or a NULL
@@ -914,46 +914,83 @@
*/
llist = NULL;
rlist = NULL;
- for (;;) {
- /* 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);
+ do {
+ x = root;
+ /* x is never NULL in here. */
+ if (addr >= x->end) {
+ y = x->right;
+ if (y != NULL && addr >= y->end) {
+ root = y->right;
+ /* Put y on llist. */
+ y->right = llist;
+ llist = y;
+ /* Rotate left. */
+ x->right = y->left;
+ y->left = x;
+ vm_map_entry_set_max_free(x);
+ } else if (y != NULL && addr < y->start) {
root = y->left;
+ /* Put y on rlist */
y->left = rlist;
rlist = y;
+ /* Put x on llist. */
+ x->right = llist;
+ llist = x;
} else {
- /* Put root on rlist. */
- root->left = rlist;
- rlist = root;
root = y;
- }
- } else if (addr >= root->end) {
- y = root->right;
- if (y == NULL)
+ /* Put x on llist. */
+ x->right = llist;
+ llist = x;
break;
- if (addr >= y->end && y->right != NULL) {
- /* Rotate left and put y on llist. */
- root->right = y->left;
- y->left = root;
- vm_map_entry_set_max_free(root);
+ }
+ } else if (addr < x->start) {
+ y = x->left;
+ if (y != NULL && addr >= y->end) {
root = y->right;
+ /* Put y on llist. */
y->right = llist;
llist = y;
+ /* Put x on rlist. */
+ x->left = rlist;
+ rlist = x;
+ } else if (y != NULL && addr < y->start) {
+ root = y->left;
+ /* Put y on rlist. */
+ y->left = rlist;
+ rlist = y;
+ /* Rotate right. */
+ x->left = y->right;
+ y->right = x;
+ vm_map_entry_set_max_free(x);
} else {
- /* Put root on llist. */
- root->right = llist;
- llist = root;
root = y;
+ /* Put x on rlist. */
+ x->left = rlist;
+ rlist = x;
+ break;
}
} 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.
+ */
+ KASSERT(llist != NULL,
+ ("vm_map_entry_splay: addr %jx, "
+ "root %p, start %jx, end %jx, "
+ "rlist %p, start %jx, end %jx",
+ (uintmax_t)addr, oroot,
+ (uintmax_t)oroot->start, (uintmax_t)oroot->end,
+ rlist,
+ (uintmax_t)rlist->start, (uintmax_t)rlist->end));
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
}
/*
@@ -1016,18 +1053,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 +1074,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;
@@ -1107,17 +1135,21 @@
boolean_t locked;
/*
+ * If the address is out of range, fail immediately.
+ */
+ if (address < map->min_offset || address >= map->max_offset)
+ return (FALSE);
+
+ /*
* If the map is empty, then the map entry immediately preceding
* "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 +1160,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 (cur != NULL);
return (FALSE);
}
@@ -1403,27 +1420,12 @@
if (start + length > map->max_offset || start + length < start)
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
* 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
Thu, Jul 23, 5:57 PM (8 h, 39 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
35410431
Default Alt Text
D13999.id38331.diff (7 KB)

Event Timeline