Page MenuHomeFreeBSD
Files F137347990

D17794.id51784.diff
No OneTemporary
Actions

D17794.id51784.diff
View Options

Index: sys/vm/vm_map.h
===================================================================
--- sys/vm/vm_map.h
+++ sys/vm/vm_map.h
@@ -106,7 +106,6 @@
vm_offset_t start; /* start address */
vm_offset_t end; /* end address */
vm_offset_t next_read; /* vaddr of the next sequential read */
- vm_size_t adj_free; /* amount of adjacent free space */
vm_size_t max_free; /* max free space in subtree */
union vm_map_object object; /* object I point to */
vm_ooffset_t offset; /* offset into object */
Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -798,7 +798,9 @@
map->header.end = min;
map->header.start = max;
map->flags = 0;
- map->root = NULL;
+ map->root = map->header.right = &map->header;
+ map->header.left = NULL;
+ map->header.max_free = max - min;
map->timestamp = 0;
map->busy = 0;
}
@@ -864,100 +866,98 @@
static inline void
vm_map_entry_set_max_free(vm_map_entry_t entry)
{
+ vm_size_t max_left, max_right;
- entry->max_free = entry->adj_free;
- if (entry->left != NULL && entry->left->max_free > entry->max_free)
- entry->max_free = entry->left->max_free;
- if (entry->right != NULL && entry->right->max_free > entry->max_free)
- entry->max_free = entry->right->max_free;
+ max_left = (entry->left != NULL) ? entry->left->max_free :
+ entry->start - entry->prev->end;
+ max_right = (entry->right != NULL) ? entry->right->max_free :
+ entry->next->start - entry->end;
+ entry->max_free = MAX(max_left, max_right);
}
/*
- * vm_map_entry_splay:
- *
- * The Sleator and Tarjan top-down splay algorithm with the
- * following variation. Max_free must be computed bottom-up, so
- * on the downward pass, maintain the left and right spines in
- * reverse order. Then, make a second pass up each side to fix
- * 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 map must be locked, and leaves it so.
- *
- * Returns: the new root.
+ * Walk down the tree until we find addr or a NULL pointer where addr would go,
+ * breaking off left and right subtrees of nodes less than, or greater than
+ * addr. llist and rlist are the two sides in reverse order (bottom-up), with
+ * llist linked by the right pointer and rlist linked by the left pointer in the
+ * vm_map_entry.
*/
static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+vm_map_entry_splay_split(vm_offset_t addr, vm_map_entry_t root,
+ vm_map_entry_t *l_list, vm_map_entry_t *r_list)
{
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);
-
- /*
- * Pass One: Splay down the tree until we find addr or a NULL
- * pointer where addr would go. llist and rlist are the two
- * sides in reverse order (bottom-up), with llist linked by
- * the right pointer and rlist linked by the left pointer in
- * the vm_map_entry. Wait until Pass Two to set max_free on
- * the two spines.
- */
- llist = NULL;
- rlist = NULL;
+ llist = *l_list;
+ rlist = *r_list;
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;
+ /*
+ * Examine the start node of an entry before the end node if and
+ * only if we arrive at the entry by following a right pointer.
+ * Assume we arrive at the root via a left pointer.
+ */
+ while (addr >= root->end) {
+ y = root->right;
+ if (y != NULL && addr >= y->start) {
+ /* Rotate left. */
+ root->right = y->left;
+ y->left = 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;
+ if (addr < root->end)
+ break;
+ y = root->right;
+
}
- } else if (addr >= root->end) {
- y = root->right;
- if (y == NULL)
+ /* Put root on llist. */
+ root->right = llist;
+ llist = root;
+ root = y;
+ if (root == NULL || addr < root->start)
break;
- if (addr >= y->end && y->right != NULL) {
- /* Rotate left and put y on llist. */
- root->right = y->left;
- y->left = root;
+ }
+ if (root == NULL || addr >= root->start)
+ break;
+
+ while (addr < root->start) {
+ y = root->left;
+ if (y != NULL && addr < y->end) {
+ /* Rotate right. */
+ root->left = y->right;
+ y->right = root;
vm_map_entry_set_max_free(root);
- root = y->right;
- y->right = llist;
- llist = y;
- } else {
- /* Put root on llist. */
- root->right = llist;
- llist = root;
root = y;
+ if (addr >= root->start)
+ break;
+ y = root->left;
}
- } else
+ /* Put root on rlist. */
+ root->left = rlist;
+ rlist = root;
+ root = y;
+ if (root == NULL || addr >= root->end)
+ break;
+ }
+ if (root == NULL || addr < root->end)
break;
}
+ *l_list = llist;
+ *r_list = rlist;
+ return (root);
+}
+
+/*
+ * Walk back up the two spines, flip the pointers and set max_free. The
+ * subtrees of the root go at the bottom of llist and rlist.
+ */
+static vm_map_entry_t
+vm_map_entry_splay_merge(vm_map_entry_t root,
+ vm_map_entry_t llist, vm_map_entry_t rlist,
+ vm_map_entry_t ltree, vm_map_entry_t rtree)
+{
+ vm_map_entry_t y;
- /*
- * Pass Two: Walk back up the two spines, flip the pointers
- * 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;
@@ -965,7 +965,7 @@
ltree = llist;
llist = y;
}
- rtree = root->right;
+
while (rlist != NULL) {
y = rlist->left;
rlist->left = rtree;
@@ -980,10 +980,48 @@
root->left = ltree;
root->right = rtree;
vm_map_entry_set_max_free(root);
-
return (root);
}
+/*
+ * vm_map_entry_splay:
+ *
+ * The Sleator and Tarjan top-down splay algorithm with the
+ * following variation. Max_free must be computed bottom-up, so
+ * on the downward pass, maintain the left and right spines in
+ * reverse order. Then, make a second pass up each side to fix
+ * 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
+ * the next lower entry if addr is not in the tree.
+ *
+ * The map must be locked, and leaves it so.
+ *
+ */
+static vm_map_entry_t
+vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+{
+ vm_map_entry_t llist, rlist;
+
+ llist = rlist = NULL;
+ root = vm_map_entry_splay_split(addr, root, &llist, &rlist);
+ if (root == 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.
+ */
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
+ }
+ return (vm_map_entry_splay_merge(root, llist, rlist,
+ root->left, root->right));
+}
+
/*
* vm_map_entry_{un,}link:
*
@@ -991,41 +1029,24 @@
*/
static void
vm_map_entry_link(vm_map_t map,
- vm_map_entry_t after_where,
vm_map_entry_t entry)
{
+ vm_map_entry_t llist, rlist, root;
- CTR4(KTR_VM,
- "vm_map_entry_link: map %p, nentries %d, entry %p, after %p", map,
- map->nentries, entry, after_where);
+ CTR3(KTR_VM,
+ "vm_map_entry_link: map %p, nentries %d, entry %p", map,
+ map->nentries, entry);
VM_MAP_ASSERT_LOCKED(map);
- KASSERT(after_where->end <= entry->start,
- ("vm_map_entry_link: prev end %jx new start %jx overlap",
- (uintmax_t)after_where->end, (uintmax_t)entry->start));
- KASSERT(entry->end <= after_where->next->start,
- ("vm_map_entry_link: new end %jx next start %jx overlap",
- (uintmax_t)entry->end, (uintmax_t)after_where->next->start));
-
map->nentries++;
- entry->prev = after_where;
- 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;
- }
- entry->adj_free = entry->next->start - entry->end;
- vm_map_entry_set_max_free(entry);
+ root = map->root;
+ llist = rlist = NULL;
+ root = vm_map_entry_splay_split(entry->start, root, &llist, &rlist);
+ KASSERT(root == NULL,
+ ("vm_map_entry_link: link object already mapped"));
+ entry->prev = llist;
+ entry->next = rlist;
+ llist->next = rlist->prev = entry;
+ root = vm_map_entry_splay_merge(entry, llist, rlist, NULL, NULL);
map->root = entry;
}
@@ -1033,25 +1054,20 @@
vm_map_entry_unlink(vm_map_t map,
vm_map_entry_t entry)
{
- vm_map_entry_t next, prev, root;
+ vm_map_entry_t llist, rlist, 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);
- }
+ llist = rlist = NULL;
+ root = vm_map_entry_splay_split(entry->start, map->root, &llist, &rlist);
+ KASSERT(root != NULL,
+ ("vm_map_entry_unlink: unlink object not mapped"));
+ vm_map_entry_splay_split(entry->start, root->left, &llist, &rlist);
+ vm_map_entry_splay_split(entry->start, root->right, &llist, &rlist);
+ llist->next = rlist;
+ rlist->prev = llist;
+ /* Make the predecessor of the entry the new root */
+ root = vm_map_entry_splay_merge(llist, llist->right, rlist, NULL, NULL);
map->root = root;
-
- prev = entry->prev;
- next = entry->next;
- next->prev = prev;
- prev->next = next;
map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
map->nentries, entry);
@@ -1078,8 +1094,6 @@
*/
if (entry != map->root)
map->root = vm_map_entry_splay(entry->start, map->root);
-
- entry->adj_free = entry->next->start - entry->end;
vm_map_entry_set_max_free(entry);
}
@@ -1099,21 +1113,31 @@
vm_offset_t address,
vm_map_entry_t *entry) /* OUT */
{
- vm_map_entry_t cur;
+ vm_map_entry_t cur, lbound;
boolean_t locked;
+ /*
+ * If the address is out of range, fail immediately.
+ */
+ if (address < vm_map_min(map)) {
+ *entry = &map->header;
+ return (FALSE);
+ }
+ if (address >= vm_map_max(map)) {
+ *entry = map->header.prev;
+ 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
@@ -1123,42 +1147,40 @@
map->root = cur = vm_map_entry_splay(address, cur);
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;
- } else
+ } else {
/*
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
+ lbound = NULL;
for (;;) {
- if (address < cur->start) {
- if (cur->left == NULL) {
- *entry = cur->prev;
+ /*
+ * Examine the start node of an entry before the end
+ * node if and only if we arrive at the entry by
+ * following a right pointer. Assume we arrive at the
+ * root via a left pointer.
+ */
+ while (address >= cur->end) {
+ lbound = cur;
+ cur = cur->right;
+ if (cur == NULL || address < cur->start)
break;
- }
+ }
+ if (cur == NULL || address >= cur->start)
+ break;
+ while (address < cur->start) {
cur = cur->left;
- } else if (cur->end > address) {
- *entry = cur;
- return (TRUE);
- } else {
- if (cur->right == NULL) {
- *entry = cur;
+ if (cur == NULL || address >= cur->end)
break;
- }
- cur = cur->right;
}
+ if (cur == NULL || address < cur->end)
+ break;
}
- return (FALSE);
+ if (cur == NULL)
+ cur = lbound;
+ }
+ *entry = cur;
+ return (cur->end > address);
}
/*
@@ -1350,7 +1372,7 @@
/*
* Insert the new entry into the list
*/
- vm_map_entry_link(map, prev_entry, new_entry);
+ vm_map_entry_link(map, new_entry);
if ((new_entry->eflags & MAP_ENTRY_GUARD) == 0)
map->size += new_entry->end - new_entry->start;
@@ -1376,11 +1398,11 @@
* Find the first fit (lowest VM address) for "length" free bytes
* beginning at address >= start in the given map.
*
- * In a vm_map_entry, "adj_free" is the amount of free space
- * adjacent (higher address) to this entry, and "max_free" is the
- * maximum amount of contiguous free space in its subtree. This
- * allows finding a free region in one path down the tree, so
- * O(log n) amortized with splay trees.
+ * In a vm_map_entry, "max_free" is the maximum amount of
+ * contiguous free space between an entry in its subtree and a
+ * neighbor of that entry. This allows finding a free region in
+ * one path down the tree, so O(log n) amortized with splay
+ * trees.
*
* The map must be locked, and leaves it so.
*
@@ -1392,7 +1414,6 @@
vm_offset_t *addr) /* OUT */
{
vm_map_entry_t entry;
- vm_offset_t st;
/*
* Request must fit within min/max VM address and must avoid
@@ -1402,35 +1423,21 @@
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.
*/
- st = (start > map->root->end) ? start : map->root->end;
- if (length <= map->root->end + map->root->adj_free - st) {
- *addr = st;
+ map->root = vm_map_entry_splay(start, map->root);
+ entry = map->root;
+ start = MAX(start, entry->end);
+ if (length <= entry->next->start - start) {
+ *addr = start;
return (0);
}
/* With max_free, can immediately tell if no solution. */
- entry = map->root->right;
+ entry = entry->right;
if (entry == NULL || length > entry->max_free)
return (1);
@@ -1442,11 +1449,16 @@
while (entry != NULL) {
if (entry->left != NULL && entry->left->max_free >= length)
entry = entry->left;
- else if (entry->adj_free >= length) {
- *addr = entry->end;
+ else if (entry->left == NULL &&
+ entry->start - entry->prev->end >= length) {
+ *addr = entry->prev->end;
return (0);
- } else
+ } else if (entry->right != NULL)
entry = entry->right;
+ else {
+ *addr = entry->end;
+ return (0);
+ }
}
/* Can't get here, so panic if we do. */
@@ -1797,7 +1809,7 @@
if (new_entry->cred != NULL)
crhold(entry->cred);
- vm_map_entry_link(map, entry->prev, new_entry);
+ vm_map_entry_link(map, new_entry);
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
vm_object_reference(new_entry->object.vm_object);
@@ -1879,7 +1891,7 @@
if (new_entry->cred != NULL)
crhold(entry->cred);
- vm_map_entry_link(map, entry, new_entry);
+ vm_map_entry_link(map, new_entry);
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
vm_object_reference(new_entry->object.vm_object);
@@ -3532,8 +3544,7 @@
* Insert the entry into the new map -- we know we're
* inserting at the end of the new map.
*/
- vm_map_entry_link(new_map, new_map->header.prev,
- new_entry);
+ vm_map_entry_link(new_map, new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry);
/*
@@ -3560,8 +3571,7 @@
new_entry->wired_count = 0;
new_entry->object.vm_object = NULL;
new_entry->cred = NULL;
- vm_map_entry_link(new_map, new_map->header.prev,
- new_entry);
+ vm_map_entry_link(new_map, new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry);
vm_map_copy_entry(old_map, new_map, old_entry,
new_entry, fork_charge);
@@ -3584,8 +3594,7 @@
new_entry->max_protection = old_entry->max_protection;
new_entry->inheritance = VM_INHERIT_ZERO;
- vm_map_entry_link(new_map, new_map->header.prev,
- new_entry);
+ vm_map_entry_link(new_map, new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry);
new_entry->cred = curthread->td_ucred;

File Metadata

Mime Type
text/plain
Expires
Sun, Nov 23, 4:54 PM (9 h, 28 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
26021837
Default Alt Text
D17794.id51784.diff (17 KB)

Event Timeline