svn commit: r345702 - head/sys/vm
Konstantin Belousov
kib at FreeBSD.org
Tue Sep 3 14:06:11 UTC 2019
Author: kib
Date: Fri Mar 29 16:53:46 2019
New Revision: 345702
URL: https://svnweb.freebsd.org/changeset/base/345702
Log:
Eliminate adj_free field from vm_map_entry.
Drop the adj_free field from vm_map_entry_t. Refine the max_free field
so that p->max_free is the size of the largest gap with one endpoint
in the subtree rooted at p. Change vm_map_findspace so that, first,
the address-based splay is restricted to tree nodes with large-enough
max_free value, to avoid searching for the right starting point in a
subtree where all the gaps are too small. Second, when the address
search leads to a tree search for the first large-enough gap, that gap
is the subject of a splay-search that brings the gap to the top of the
tree, so that an immediate insertion will take constant time.
Break up the splay code into separate components, one for searching
and breaking up the tree and another for reassembling it. Use these
components, and not splay itself, for linking and unlinking. Drop the
after-where parameter to link, as it is computed as a side-effect of
the splay search.
Submitted by: Doug Moore <dougm at rice.edu>
Reviewed by: markj
Tested by: pho
MFC after: 2 weeks
Differential revision: https://reviews.freebsd.org/D17794
Modified:
head/sys/vm/vm_kern.c
head/sys/vm/vm_map.c
head/sys/vm/vm_map.h
Modified: head/sys/vm/vm_kern.c
==============================================================================
--- head/sys/vm/vm_kern.c Fri Mar 29 16:43:24 2019 (r345701)
+++ head/sys/vm/vm_kern.c Fri Mar 29 16:53:46 2019 (r345702)
@@ -641,7 +641,8 @@ kmap_alloc_wait(vm_map_t map, vm_size_t size)
* to lock out sleepers/wakers.
*/
vm_map_lock(map);
- if (vm_map_findspace(map, vm_map_min(map), size, &addr) == 0)
+ addr = vm_map_findspace(map, vm_map_min(map), size);
+ if (addr + size <= vm_map_max(map))
break;
/* no space now; see if we can ever get space */
if (vm_map_max(map) - vm_map_min(map) < size) {
Modified: head/sys/vm/vm_map.c
==============================================================================
--- head/sys/vm/vm_map.c Fri Mar 29 16:43:24 2019 (r345701)
+++ head/sys/vm/vm_map.c Fri Mar 29 16:53:46 2019 (r345702)
@@ -132,9 +132,6 @@ static int vmspace_zinit(void *mem, int size, int flag
static int vm_map_zinit(void *mem, int ize, int flags);
static void _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min,
vm_offset_t max);
-static int vm_map_alignspace(vm_map_t map, vm_object_t object,
- vm_ooffset_t offset, vm_offset_t *addr, vm_size_t length,
- vm_offset_t max_addr, vm_offset_t alignment);
static void vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map);
static void vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry);
static void vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry);
@@ -672,8 +669,51 @@ _vm_map_assert_locked(vm_map_t map, const char *file,
#define VM_MAP_ASSERT_LOCKED(map) \
_vm_map_assert_locked(map, LOCK_FILE, LOCK_LINE)
+
+static void
+_vm_map_assert_consistent(vm_map_t map)
+{
+ vm_map_entry_t entry;
+ vm_map_entry_t child;
+ vm_size_t max_left, max_right;
+
+ for (entry = map->header.next; entry != &map->header;
+ entry = entry->next) {
+ KASSERT(entry->prev->end <= entry->start,
+ ("map %p prev->end = %jx, start = %jx", map,
+ (uintmax_t)entry->prev->end, (uintmax_t)entry->start));
+ KASSERT(entry->start < entry->end,
+ ("map %p start = %jx, end = %jx", map,
+ (uintmax_t)entry->start, (uintmax_t)entry->end));
+ KASSERT(entry->end <= entry->next->start,
+ ("map %p end = %jx, next->start = %jx", map,
+ (uintmax_t)entry->end, (uintmax_t)entry->next->start));
+ KASSERT(entry->left == NULL ||
+ entry->left->start < entry->start,
+ ("map %p left->start = %jx, start = %jx", map,
+ (uintmax_t)entry->left->start, (uintmax_t)entry->start));
+ KASSERT(entry->right == NULL ||
+ entry->start < entry->right->start,
+ ("map %p start = %jx, right->start = %jx", map,
+ (uintmax_t)entry->start, (uintmax_t)entry->right->start));
+ child = entry->left;
+ max_left = (child != NULL) ? child->max_free :
+ entry->start - entry->prev->end;
+ child = entry->right;
+ max_right = (child != NULL) ? child->max_free :
+ entry->next->start - entry->end;
+ KASSERT(entry->max_free == MAX(max_left, max_right),
+ ("map %p max = %jx, max_left = %jx, max_right = %jx", map,
+ (uintmax_t)entry->max_free,
+ (uintmax_t)max_left, (uintmax_t)max_right));
+ }
+}
+
+#define VM_MAP_ASSERT_CONSISTENT(map) \
+ _vm_map_assert_consistent(map)
#else
#define VM_MAP_ASSERT_LOCKED(map)
+#define VM_MAP_ASSERT_CONSISTENT(map)
#endif
/*
@@ -865,100 +905,117 @@ vm_map_entry_set_behavior(vm_map_entry_t entry, u_char
static inline void
vm_map_entry_set_max_free(vm_map_entry_t entry)
{
+ vm_map_entry_t child;
+ 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;
+ child = entry->left;
+ max_left = (child != NULL) ? child->max_free :
+ entry->start - entry->prev->end;
+ child = entry->right;
+ max_right = (child != NULL) ? child->max_free :
+ entry->next->start - entry->end;
+ entry->max_free = MAX(max_left, max_right);
}
+#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
+ y = root->left; \
+ if (y != NULL && (test)) { \
+ /* Rotate right and make y root. */ \
+ root->left = y->right; \
+ y->right = root; \
+ vm_map_entry_set_max_free(root); \
+ root = y; \
+ y = root->left; \
+ } \
+ /* Put root on rlist. */ \
+ root->left = rlist; \
+ rlist = root; \
+ root = y; \
+} while (0)
+
+#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
+ y = root->right; \
+ if (y != NULL && (test)) { \
+ /* Rotate left and make y root. */ \
+ root->right = y->left; \
+ y->left = root; \
+ vm_map_entry_set_max_free(root); \
+ root = y; \
+ y = root->right; \
+ } \
+ /* Put root on llist. */ \
+ root->right = llist; \
+ llist = root; \
+ root = y; \
+} while (0)
+
/*
- * 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. Treat pointers to nodes with max_free < length as NULL pointers.
+ * 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_splay_split(vm_offset_t addr, vm_size_t length,
+ vm_map_entry_t root, vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist)
{
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;
- for (;;) {
- /* root is never NULL in here. */
+ while (root != NULL && root->max_free >= length) {
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;
- }
+ SPLAY_LEFT_STEP(root, y, rlist,
+ y->max_free >= length && addr < y->start);
} else if (addr >= root->end) {
- y = root->right;
- if (y == NULL)
- 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);
- root = y->right;
- y->right = llist;
- llist = y;
- } else {
- /* Put root on llist. */
- root->right = llist;
- llist = root;
- root = y;
- }
+ SPLAY_RIGHT_STEP(root, y, llist,
+ y->max_free >= length && addr >= y->end);
} else
break;
}
+ *out_llist = llist;
+ *out_rlist = rlist;
+ return (root);
+}
- /*
- * 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;
+static void
+vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist)
+{
+ vm_map_entry_t rlist, y;
+
+ root = root->right;
+ rlist = *iolist;
+ while (root != NULL)
+ SPLAY_LEFT_STEP(root, y, rlist, true);
+ *iolist = rlist;
+}
+
+static void
+vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist)
+{
+ vm_map_entry_t llist, y;
+
+ root = root->left;
+ llist = *iolist;
+ while (root != NULL)
+ SPLAY_RIGHT_STEP(root, y, llist, true);
+ *iolist = llist;
+}
+
+/*
+ * 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_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;
+
while (llist != NULL) {
y = llist->right;
llist->right = ltree;
@@ -966,7 +1023,6 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro
ltree = llist;
llist = y;
}
- rtree = root->right;
while (rlist != NULL) {
y = rlist->left;
rlist->left = rtree;
@@ -986,73 +1042,143 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro
}
/*
+ * 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 if possible) 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)
+{
+ vm_map_entry_t llist, rlist;
+
+ root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
+ if (root != NULL) {
+ /* do nothing */
+ } else if (llist != NULL) {
+ /*
+ * Recover the greatest node in the left
+ * subtree and make it the root.
+ */
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
+ } else if (rlist != NULL) {
+ /*
+ * Recover the least node in the right
+ * subtree and make it the root.
+ */
+ root = rlist;
+ rlist = root->left;
+ root->left = NULL;
+ } else {
+ /* There is no root. */
+ return (NULL);
+ }
+ return (vm_map_splay_merge(root, llist, rlist,
+ root->left, root->right));
+}
+
+/*
* vm_map_entry_{un,}link:
*
* Insert/remove entries from maps.
*/
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;
+ root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+ KASSERT(root == NULL,
+ ("vm_map_entry_link: link object already mapped"));
+ entry->prev = (llist == NULL) ? &map->header : llist;
+ entry->next = (rlist == NULL) ? &map->header : rlist;
+ entry->prev->next = entry->next->prev = entry;
+ root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL);
map->root = entry;
+ VM_MAP_ASSERT_CONSISTENT(map);
}
+enum unlink_merge_type {
+ UNLINK_MERGE_PREV,
+ UNLINK_MERGE_NONE,
+ UNLINK_MERGE_NEXT
+};
+
static void
vm_map_entry_unlink(vm_map_t map,
- vm_map_entry_t entry)
+ vm_map_entry_t entry,
+ enum unlink_merge_type op)
{
- vm_map_entry_t next, prev, root;
+ vm_map_entry_t llist, rlist, root, y;
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 = entry->prev;
+ rlist = entry->next;
+ llist->next = rlist;
+ rlist->prev = llist;
+ root = map->root;
+ root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+ KASSERT(root != NULL,
+ ("vm_map_entry_unlink: unlink object not mapped"));
+
+ switch (op) {
+ case UNLINK_MERGE_PREV:
+ vm_map_splay_findprev(root, &llist);
+ llist->end = root->end;
+ y = root->right;
+ root = llist;
+ llist = root->right;
+ root->right = y;
+ break;
+ case UNLINK_MERGE_NEXT:
+ vm_map_splay_findnext(root, &rlist);
+ rlist->start = root->start;
+ rlist->offset = root->offset;
+ y = root->left;
+ root = rlist;
+ rlist = root->left;
+ root->left = y;
+ break;
+ case UNLINK_MERGE_NONE:
+ vm_map_splay_findprev(root, &llist);
+ vm_map_splay_findnext(root, &rlist);
+ if (llist != NULL) {
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
+ } else if (rlist != NULL) {
+ root = rlist;
+ rlist = root->left;
+ root->left = NULL;
+ } else
+ root = NULL;
+ break;
}
+ if (root != NULL)
+ root = vm_map_splay_merge(root, llist, rlist,
+ root->left, root->right);
map->root = root;
-
- prev = entry->prev;
- next = entry->next;
- next->prev = prev;
- prev->next = next;
+ VM_MAP_ASSERT_CONSISTENT(map);
map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
map->nentries, entry);
@@ -1061,27 +1187,30 @@ vm_map_entry_unlink(vm_map_t map,
/*
* vm_map_entry_resize_free:
*
- * Recompute the amount of free space following a vm_map_entry
- * and propagate that value up the tree. Call this function after
- * resizing a map entry in-place, that is, without a call to
- * vm_map_entry_link() or _unlink().
+ * Recompute the amount of free space following a modified vm_map_entry
+ * and propagate those values up the tree. Call this function after
+ * resizing a map entry in-place by changing the end value, without a
+ * call to vm_map_entry_link() or _unlink().
*
* The map must be locked, and leaves it so.
*/
static void
vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry)
{
+ vm_map_entry_t llist, rlist, root;
- /*
- * Using splay trees without parent pointers, propagating
- * max_free up the tree is done by moving the entry to the
- * root and making the change there.
- */
- 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);
+ VM_MAP_ASSERT_LOCKED(map);
+ root = map->root;
+ root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+ KASSERT(root != NULL,
+ ("vm_map_entry_resize_free: resize_free object not mapped"));
+ vm_map_splay_findnext(root, &rlist);
+ root->right = NULL;
+ map->root = vm_map_splay_merge(root, llist, rlist,
+ root->left, root->right);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map,
+ map->nentries, entry);
}
/*
@@ -1100,7 +1229,7 @@ vm_map_lookup_entry(
vm_offset_t address,
vm_map_entry_t *entry) /* OUT */
{
- vm_map_entry_t cur;
+ vm_map_entry_t cur, lbound;
boolean_t locked;
/*
@@ -1108,12 +1237,15 @@ vm_map_lookup_entry(
* "address" is the map's header.
*/
cur = map->root;
- if (cur == NULL)
+ if (cur == NULL) {
*entry = &map->header;
- else if (address >= cur->start && cur->end > address) {
+ return (FALSE);
+ }
+ if (address >= cur->start && cur->end > address) {
*entry = cur;
return (TRUE);
- } else if ((locked = vm_map_locked(map)) ||
+ }
+ if ((locked = vm_map_locked(map)) ||
sx_try_upgrade(&map->lock)) {
/*
* Splay requires a write lock on the map. However, it only
@@ -1122,6 +1254,7 @@ vm_map_lookup_entry(
* on a temporary upgrade.
*/
map->root = cur = vm_map_entry_splay(address, cur);
+ VM_MAP_ASSERT_CONSISTENT(map);
if (!locked)
sx_downgrade(&map->lock);
@@ -1130,35 +1263,30 @@ vm_map_lookup_entry(
* is that map entry. Otherwise, the new root is a map entry
* immediately before or after "address".
*/
- if (address >= cur->start) {
+ if (address < cur->start) {
+ *entry = &map->header;
+ return (FALSE);
+ }
+ *entry = cur;
+ return (address < cur->end);
+ }
+ /*
+ * Since the map is only locked for read access, perform a
+ * standard binary search tree lookup for "address".
+ */
+ lbound = &map->header;
+ do {
+ if (address < cur->start) {
+ cur = cur->left;
+ } else if (cur->end <= address) {
+ lbound = cur;
+ cur = cur->right;
+ } else {
*entry = cur;
- if (cur->end > address)
- return (TRUE);
- } else
- *entry = cur->prev;
- } 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;
- }
- cur = cur->left;
- } else if (cur->end > address) {
- *entry = cur;
- return (TRUE);
- } else {
- if (cur->right == NULL) {
- *entry = cur;
- break;
- }
- cur = cur->right;
- }
+ return (TRUE);
}
+ } while (cur != NULL);
+ *entry = lbound;
return (FALSE);
}
@@ -1351,7 +1479,7 @@ charged:
/*
* 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;
@@ -1377,23 +1505,22 @@ charged:
* 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.
*
- * Returns: 0 on success, and starting address in *addr,
- * 1 if insufficient space.
+ * Returns: starting address if sufficient space,
+ * vm_map_max(map)-length+1 if insufficient space.
*/
-int
-vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
- vm_offset_t *addr) /* OUT */
+vm_offset_t
+vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length)
{
- vm_map_entry_t entry;
- vm_offset_t st;
+ vm_map_entry_t llist, rlist, root, y;
+ vm_size_t left_length;
/*
* Request must fit within min/max VM address and must avoid
@@ -1401,57 +1528,87 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s
*/
start = MAX(start, vm_map_min(map));
if (start + length > vm_map_max(map) || start + length < start)
- return (1);
+ return (vm_map_max(map) - length + 1);
/* Empty tree means wide open address space. */
- if (map->root == NULL) {
- *addr = start;
- return (0);
- }
+ if (map->root == NULL)
+ return (start);
/*
* 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 = vm_map_splay_split(start, length, map->root,
+ &llist, &rlist);
+ if (root != NULL)
+ start = root->end;
+ else if (rlist != NULL) {
+ root = rlist;
+ rlist = root->left;
+ root->left = NULL;
+ } else {
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
}
+ map->root = vm_map_splay_merge(root, llist, rlist,
+ root->left, root->right);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ if (start + length <= root->start)
+ return (start);
/*
* 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;
- return (0);
- }
+ if (root->right == NULL &&
+ start + length <= vm_map_max(map))
+ return (start);
/* With max_free, can immediately tell if no solution. */
- entry = map->root->right;
- if (entry == NULL || length > entry->max_free)
- return (1);
+ if (root->right == NULL || length > root->right->max_free)
+ return (vm_map_max(map) - length + 1);
/*
- * Search the right subtree in the order: left subtree, root,
- * right subtree (first fit). The previous splay implies that
- * all regions in the right subtree have addresses > start.
+ * Splay for the least large-enough gap in the right subtree.
*/
- while (entry != NULL) {
- if (entry->left != NULL && entry->left->max_free >= length)
- entry = entry->left;
- else if (entry->adj_free >= length) {
- *addr = entry->end;
- return (0);
- } else
- entry = entry->right;
+ llist = NULL;
+ rlist = NULL;
+ for (left_length = 0; ;
+ left_length = root->left != NULL ?
+ root->left->max_free : root->start - llist->end) {
+ if (length <= left_length)
+ SPLAY_LEFT_STEP(root, y, rlist,
+ length <= (y->left != NULL ?
+ y->left->max_free : y->start - llist->end));
+ else
+ SPLAY_RIGHT_STEP(root, y, llist,
+ length > (y->left != NULL ?
+ y->left->max_free : y->start - root->end));
+ if (root == NULL)
+ break;
}
-
- /* Can't get here, so panic if we do. */
- panic("vm_map_findspace: max_free corrupt");
+ root = llist;
+ llist = root->right;
+ if ((y = rlist) == NULL)
+ root->right = NULL;
+ else {
+ rlist = y->left;
+ y->left = NULL;
+ root->right = y->right;
+ }
+ root = vm_map_splay_merge(root, llist, rlist,
+ root->left, root->right);
+ if (y != NULL) {
+ y->right = root->right;
+ vm_map_entry_set_max_free(y);
+ root->right = y;
+ vm_map_entry_set_max_free(root);
+ }
+ map->root = root;
+ VM_MAP_ASSERT_CONSISTENT(map);
+ return (root->end);
}
int
@@ -1532,8 +1689,9 @@ vm_map_alignspace(vm_map_t map, vm_object_t object, vm
VM_MAP_ASSERT_LOCKED(map);
free_addr = *addr;
- KASSERT(!vm_map_findspace(map, free_addr, length, addr) &&
- free_addr == *addr, ("caller provided insufficient free space"));
+ KASSERT(free_addr == vm_map_findspace(map, free_addr, length),
+ ("caller failed to provide space %d at address %p",
+ (int)length, (void*)free_addr));
for (;;) {
/*
* At the start of every iteration, the free space at address
@@ -1559,8 +1717,10 @@ vm_map_alignspace(vm_map_t map, vm_object_t object, vm
* be a valid address, in which case vm_map_findspace() cannot
* be relied upon to fail.
*/
- if (aligned_addr < free_addr ||
- vm_map_findspace(map, aligned_addr, length, addr) ||
+ if (aligned_addr < free_addr)
+ return (KERN_NO_SPACE);
+ *addr = vm_map_findspace(map, aligned_addr, length);
+ if (*addr + length > vm_map_max(map) ||
(max_addr != 0 && *addr + length > max_addr))
return (KERN_NO_SPACE);
free_addr = *addr;
@@ -1672,22 +1832,27 @@ again:
gap = vm_map_max(map) > MAP_32BIT_MAX_ADDR &&
(max_addr == 0 || max_addr > MAP_32BIT_MAX_ADDR) ?
aslr_pages_rnd_64[pidx] : aslr_pages_rnd_32[pidx];
- if (vm_map_findspace(map, curr_min_addr, length +
- gap * pagesizes[pidx], addr))
+ *addr = vm_map_findspace(map, curr_min_addr,
+ length + gap * pagesizes[pidx]);
+ if (*addr + length + gap * pagesizes[pidx] >
++ vm_map_max(map))
goto again;
/* And randomize the start address. */
*addr += (arc4random() % gap) * pagesizes[pidx];
if (max_addr != 0 && *addr + length > max_addr)
goto again;
- } else if (vm_map_findspace(map, curr_min_addr, length, addr) ||
- (max_addr != 0 && *addr + length > max_addr)) {
- if (cluster) {
- cluster = false;
- MPASS(try == 1);
- goto again;
+ } else {
+ *addr = vm_map_findspace(map, curr_min_addr, length);
+ if (*addr + length > vm_map_max(map) ||
+ (max_addr != 0 && *addr + length > max_addr)) {
+ if (cluster) {
+ cluster = false;
+ MPASS(try == 1);
+ goto again;
+ }
+ rv = KERN_NO_SPACE;
+ goto done;
}
- rv = KERN_NO_SPACE;
- goto done;
}
if (find_space != VMFS_ANY_SPACE &&
@@ -1825,18 +1990,12 @@ vm_map_simplify_entry(vm_map_t map, vm_map_entry_t ent
return;
prev = entry->prev;
if (vm_map_mergeable_neighbors(prev, entry)) {
- vm_map_entry_unlink(map, prev);
- entry->start = prev->start;
- entry->offset = prev->offset;
- if (entry->prev != &map->header)
- vm_map_entry_resize_free(map, entry->prev);
+ vm_map_entry_unlink(map, prev, UNLINK_MERGE_NEXT);
vm_map_merged_neighbor_dispose(map, prev);
}
next = entry->next;
if (vm_map_mergeable_neighbors(entry, next)) {
- vm_map_entry_unlink(map, next);
- entry->end = next->end;
- vm_map_entry_resize_free(map, entry);
+ vm_map_entry_unlink(map, next, UNLINK_MERGE_PREV);
vm_map_merged_neighbor_dispose(map, next);
}
}
@@ -1914,7 +2073,7 @@ _vm_map_clip_start(vm_map_t map, vm_map_entry_t entry,
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);
@@ -1996,7 +2155,7 @@ _vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, v
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);
@@ -3132,7 +3291,7 @@ vm_map_entry_delete(vm_map_t map, vm_map_entry_t entry
vm_pindex_t offidxstart, offidxend, count, size1;
vm_size_t size;
- vm_map_entry_unlink(map, entry);
+ vm_map_entry_unlink(map, entry, UNLINK_MERGE_NONE);
object = entry->object.vm_object;
if ((entry->eflags & MAP_ENTRY_GUARD) != 0) {
@@ -3675,8 +3834,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_c
* 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);
/*
@@ -3703,8 +3861,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_c
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);
@@ -3727,8 +3884,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_c
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;
Modified: head/sys/vm/vm_map.h
==============================================================================
--- head/sys/vm/vm_map.h Fri Mar 29 16:43:24 2019 (r345701)
+++ head/sys/vm/vm_map.h Fri Mar 29 16:53:46 2019 (r345702)
@@ -106,7 +106,6 @@ struct vm_map_entry {
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 */
@@ -402,7 +401,7 @@ int vm_map_find_min(vm_map_t, vm_object_t, vm_ooffset_
vm_size_t, vm_offset_t, vm_offset_t, int, vm_prot_t, vm_prot_t, int);
int vm_map_fixed(vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t, vm_size_t,
vm_prot_t, vm_prot_t, int);
-int vm_map_findspace (vm_map_t, vm_offset_t, vm_size_t, vm_offset_t *);
+vm_offset_t vm_map_findspace(vm_map_t, vm_offset_t, vm_size_t);
int vm_map_inherit (vm_map_t, vm_offset_t, vm_offset_t, vm_inherit_t);
void vm_map_init(vm_map_t, pmap_t, vm_offset_t, vm_offset_t);
int vm_map_insert (vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t, vm_offset_t, vm_prot_t, vm_prot_t, int);
More information about the svn-src-all
mailing list