svn commit: r346152 - stable/12/sys/vm
Konstantin Belousov
kib at FreeBSD.org
Tue Sep 3 14:06:46 UTC 2019
Author: kib
Date: Fri Apr 12 14:59:28 2019
New Revision: 346152
URL: https://svnweb.freebsd.org/changeset/base/346152
Log:
MFC r345702,r345954:
Eliminate adj_free field from vm_map_entry.
Modified:
stable/12/sys/vm/vm_kern.c
stable/12/sys/vm/vm_map.c
stable/12/sys/vm/vm_map.h
Directory Properties:
stable/12/ (props changed)
Modified: stable/12/sys/vm/vm_kern.c
==============================================================================
--- stable/12/sys/vm/vm_kern.c Fri Apr 12 14:18:16 2019 (r346151)
+++ stable/12/sys/vm/vm_kern.c Fri Apr 12 14:59:28 2019 (r346152)
@@ -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: stable/12/sys/vm/vm_map.c
==============================================================================
--- stable/12/sys/vm/vm_map.c Fri Apr 12 14:18:16 2019 (r346151)
+++ stable/12/sys/vm/vm_map.c Fri Apr 12 14:59:28 2019 (r346152)
@@ -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: stable/12/sys/vm/vm_map.h
==============================================================================
--- stable/12/sys/vm/vm_map.h Fri Apr 12 14:18:16 2019 (r346151)
+++ stable/12/sys/vm/vm_map.h Fri Apr 12 14:59:28 2019 (r346152)
@@ -106,7 +106,7 @@ 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 pad_adj_free; /* pad */
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 +402,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-stable-12
mailing list