Page MenuHomeFreeBSD
Files F133287680

D13999.id50452.diff
No OneTemporary
Actions

D13999.id50452.diff
View Options

Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -803,7 +803,10 @@
map->header.end = min;
map->header.start = max;
map->flags = 0;
- map->root = NULL;
+ map->header.left = map->header.right = NULL;
+ map->header.adj_free = max - min;
+ map->header.max_free = map->header.adj_free;
+ map->root = &map->header;
map->timestamp = 0;
map->busy = 0;
}
@@ -878,7 +881,7 @@
}
/*
- * vm_map_entry_splay:
+ * vm_map_splay:
*
* The Sleator and Tarjan top-down splay algorithm with the
* following variation. Max_free must be computed bottom-up, so
@@ -887,23 +890,23 @@
* the pointers and compute max_free. The time bound is O(log n)
* amortized.
*
- * The new root is the vm_map_entry containing "addr", or else an
- * adjacent entry (lower or higher) if addr is not in the tree.
+ * The new root is the vm_map_entry containing "addr", or else
+ * the next lower entry if addr is not in the tree.
*
* The map must be locked, and leaves it so.
*
- * Returns: the new root.
*/
-static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+static void
+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 ltree, rtree;
- vm_map_entry_t y;
+ vm_map_entry_t root, x, y;
- /* Special case of empty tree. */
- if (root == NULL)
- return (root);
+ KASSERT(addr >= map->header.end && addr < map->header.start,
+ ("vm_map_splay: addr %jx, offsets start %jx, end %jx",
+ (uintmax_t)addr,
+ (uintmax_t)map->header.end, (uintmax_t)map->header.start));
/*
* Pass One: Splay down the tree until we find addr or a NULL
@@ -915,46 +918,122 @@
*/
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);
+ root = map->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 x on llist. */
+ x->right = llist;
+ llist = x;
+ /* Put y on rlist. */
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;
- 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 x on rlist. */
+ x->left = rlist;
+ rlist = x;
+ /* Put y on llist. */
y->right = llist;
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 {
- /* 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 &&
+ (io == NULL || *io == NULL)) {
+ /*
+ * With no matching node found, and no new node to
+ * insert, 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.
+ */
+ rtree = NULL;
+ root = llist;
+ llist = llist->right;
+ ltree = root->left;
+ } else if (root == NULL) {
+ /* Install the new item as tree root. */
+ rtree = NULL;
+ root = *io;
+ *io = NULL;
+ ltree = NULL;
+ } else if (io == NULL || *io != NULL) {
+ rtree = root->right;
+ ltree = root->left;
+ } else {
+ /*
+ * 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;
+ *io = root;
+ root = root->left;
+ if (root == NULL) {
+ root = llist;
+ llist = llist->right;
+ } else {
+ 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;
+ }
+ }
+ ltree = root->left;
}
/*
@@ -962,7 +1041,6 @@
* and set max_free. The subtrees of the root go at the
* bottom of llist and rlist.
*/
- ltree = root->left;
while (llist != NULL) {
y = llist->right;
llist->right = ltree;
@@ -970,7 +1048,7 @@
ltree = llist;
llist = y;
}
- rtree = root->right;
+
while (rlist != NULL) {
y = rlist->left;
rlist->left = rtree;
@@ -986,7 +1064,7 @@
root->right = rtree;
vm_map_entry_set_max_free(root);
- return (root);
+ map->root = root;
}
/*
@@ -1016,47 +1094,25 @@
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;
+ vm_map_splay(entry->start, map, &entry);
}
static void
vm_map_entry_unlink(vm_map_t map,
vm_map_entry_t entry)
{
- vm_map_entry_t next, prev, root;
+ vm_map_entry_t next, prev;
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;
+ prev = NULL;
+ vm_map_splay(entry->start, map, &prev);
map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
map->nentries, entry);
@@ -1082,7 +1138,7 @@
* root and making the change there.
*/
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;
vm_map_entry_set_max_free(entry);
@@ -1107,62 +1163,54 @@
vm_map_entry_t cur;
boolean_t locked;
+ /*
+ * If the address is out of range, fail immediately.
+ */
+ if (address < map->header.end || address >= map->header.start) {
+ *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);
+ vm_map_splay(address, map, NULL);
+ cur = map->root;
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);
}
@@ -1407,27 +1455,12 @@
if (start + length > vm_map_max(map) || 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.
*/
+ vm_map_splay(start, map, 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
Sat, Oct 25, 3:54 PM (1 h, 12 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24179664
Default Alt Text
D13999.id50452.diff (10 KB)

Event Timeline