Page MenuHomeFreeBSD
Files F153211234

D13999.id38455.diff
No OneTemporary
Actions

D13999.id38455.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;
}
@@ -894,15 +897,11 @@
* Returns: the new root.
*/
static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root, vm_map_entry_t *io)
{
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;
/*
* Pass One: Splay down the tree until we find addr or a NULL
@@ -914,46 +913,82 @@
*/
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;
+ /* Rotate left. */
+ x->right = y->left;
+ 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;
+ /* 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;
+ /* 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 {
- /* 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 (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) {
+ /* Install the new item as tree root */
+ root = *io;
+ *io = NULL;
}
/*
@@ -1015,22 +1050,9 @@
entry->next = after_where->next;
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;
- }
+ after_where->adj_free = entry->start - after_where->end;
entry->adj_free = entry->next->start - entry->end;
- vm_map_entry_set_max_free(entry);
- map->root = entry;
+ map->root = vm_map_splay(entry->start, map->root, &entry);
}
static void
@@ -1040,22 +1062,18 @@
vm_map_entry_t next, prev, root;
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;
next = entry->next;
next->prev = prev;
prev->next = next;
+ prev->adj_free = next->start - prev->end;
+ if (entry != map->root)
+ vm_map_entry_splay(entry->start, map->root, NULL);
+ root = vm_map_entry_splay(entry->start, entry->left, NULL);
+ root->right = entry->right;
+ vm_map_entry_set_max_free(root);
+ map->root = root;
+
map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
map->nentries, entry);
@@ -1081,7 +1099,7 @@
* root and making the change there.
*/
if (entry != map->root)
- map->root = vm_map_entry_splay(entry->start, map->root);
+ map->root = vm_map_entry_splay(entry->start, map->root, NULL);
entry->adj_free = entry->next->start - entry->end;
vm_map_entry_set_max_free(entry);
@@ -1107,61 +1125,52 @@
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
* "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
* change the map. Thus, the map's timestamp need not change
* on a temporary upgrade.
*/
- map->root = cur = vm_map_entry_splay(address, cur);
+ map->root = cur = vm_map_entry_splay(address, cur, NULL);
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 +1412,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, NULL);
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
Mon, Apr 20, 8:17 PM (19 h, 5 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31862267
Default Alt Text
D13999.id38455.diff (8 KB)

Event Timeline