Author: dougm
Date: Wed Jun 26 03:12:57 2019
New Revision: 349405
URL: https://svnweb.freebsd.org/changeset/base/349405
Log:
Revert r349393, which leads to an assertion failure on bootup, in
vm_map_stack_locked.
Reported by: l...@lerctr.org
Approved by: kib, markj (mentors, implicit)
Modified:
head/sys/vm/vm_map.c
head/sys/vm/vm_map.h
Modified: head/sys/vm/vm_map.c
==============================================================================
--- head/sys/vm/vm_map.c Wed Jun 26 03:06:57 2019 (r349404)
+++ head/sys/vm/vm_map.c Wed Jun 26 03:12:57 2019 (r349405)
@@ -983,17 +983,6 @@ vm_map_entry_max_free_right(vm_map_entry_t root, vm_ma
root->right->max_free : right_ancestor->start - root->end);
}
-/*
- * vm_map_splay_split, vm_map_splay_merge:
- *
- * The Sleator and Tarjan top-down splay algorithm with the following
- * variation. Max_free must be computed bottom-up, so on the downward
- * pass (vm_map_splay_split), maintain the left and right spines in
- * reverse order, and ensure that the max_free values for those nodes
- * store the values of their descendents not on the search path. Later,
- * make a second pass up each side (vm_map_splay_merge) to fix the
- * pointers and compute max_free. The time bound is O(log n) amortized.
- */
#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
vm_size_t max_free; \
\
@@ -1177,6 +1166,56 @@ vm_map_splay_merge(vm_map_t map, vm_map_entry_t root,
}
/*
+ * vm_map_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_splay(vm_map_t map, vm_offset_t addr)
+{
+ vm_map_entry_t llist, rlist, root;
+
+ root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
+ if (root != NULL) {
+ /* do nothing */
+ } else if (llist != &map->header) {
+ /*
+ * Recover the greatest node in the left
+ * subtree and make it the root.
+ */
+ root = llist;
+ llist = root->right;
+ root->right = NULL;
+ } else if (rlist != &map->header) {
+ /*
+ * 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);
+ }
+ vm_map_splay_merge(map, root, llist, rlist);
+ VM_MAP_ASSERT_CONSISTENT(map);
+ return (root);
+}
+
+/*
* vm_map_entry_{un,}link:
*
* Insert/remove entries from maps.
@@ -1292,133 +1331,81 @@ vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry
}
/*
- * vm_map_lookup_helper: [ internal use only ]
+ * vm_map_lookup_entry: [ internal use only ]
*
- * Finds the map entry containing (or adjacent to) the specified address
- * in the given map; the entry is returned in the "entry" parameter. The
- * boolean result indicates whether the address is actually contained in
- * the map. If the address is not contained in the map, parameter lesseq
- * determines whether the entry provided is before or after the address.
- * If the address is contained in the map, parameter nbr, if not NULL, is
- * where the next or previous entry is saved, depending on the value of
- * eflags in the found entry.
+ * Finds the map entry containing (or
+ * immediately preceding) the specified address
+ * in the given map; the entry is returned
+ * in the "entry" parameter. The boolean
+ * result indicates whether the address is
+ * actually contained in the map.
*/
-static bool
-vm_map_lookup_helper(vm_map_t map, vm_offset_t addr, bool lesseq,
- vm_map_entry_t *entry, vm_map_entry_t *nbr) /* OUT */
+boolean_t
+vm_map_lookup_entry(
+ vm_map_t map,
+ vm_offset_t address,
+ vm_map_entry_t *entry) /* OUT */
{
- vm_map_entry_t llist, rlist, root;
- bool locked, found;
+ vm_map_entry_t cur, lbound;
+ boolean_t locked;
/*
* If the map is empty, then the map entry immediately preceding
- * "addr" is the map's header.
+ * "address" is the map's header.
*/
- root = map->root;
- if (root == NULL) {
+ cur = map->root;
+ if (cur == NULL) {
*entry = &map->header;
- return (false);
+ return (FALSE);
}
+ if (address >= cur->start && cur->end > address) {
+ *entry = cur;
+ return (TRUE);
+ }
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.
*/
- root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
- found = root != NULL;
- *entry = root;
- if (root != NULL) {
- if (nbr == NULL)
- ; /* Ignore. */
- else if ((root->eflags & MAP_ENTRY_STACK_GAP_DN) != 0) {
- vm_map_splay_findnext(root, &rlist);
- *nbr = rlist;
- } else {
- vm_map_splay_findprev(root, &llist);
- *nbr = llist;
- }
- } else if (llist != &map->header) {
- /*
- * Recover the greatest node in the left
- * subtree and make it the root.
- */
- *entry = lesseq ? llist : rlist;
- root = llist;
- llist = root->right;
- root->right = NULL;
- } else {
- /*
- * Recover the least node in the right
- * subtree and make it the root.
- */
- *entry = lesseq ? llist : rlist;
- root = rlist;
- rlist = root->left;
- root->left = NULL;
- }
- vm_map_splay_merge(map, root, llist, rlist);
- VM_MAP_ASSERT_CONSISTENT(map);
+ cur = vm_map_splay(map, address);
if (!locked)
sx_downgrade(&map->lock);
- return (found);
+
+ /*
+ * 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 = &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 "addr".
+ * standard binary search tree lookup for "address".
*/
- llist = rlist = &map->header;
+ lbound = &map->header;
do {
- if (addr < root->start) {
- rlist = root;
- root = root->left;
- } else if (root->end <= addr) {
- llist = root;
- root = root->right;
+ if (address < cur->start) {
+ cur = cur->left;
+ } else if (cur->end <= address) {
+ lbound = cur;
+ cur = cur->right;
} else {
- *entry = root;
- if (nbr == NULL);
- else if ((root->eflags & MAP_ENTRY_STACK_GAP_DN) != 0) {
- /* Make nbr the successor to root. */
- if (root->right != NULL) {
- rlist = root->right;
- while (rlist->left != NULL)
- rlist = rlist->left;
- }
- *nbr = rlist;
- } else {
- /* Make nbr the predecessor to root. */
- if (root->left != NULL) {
- llist = root->left;
- while (llist->right != NULL)
- llist = llist->right;
- }
- *nbr = llist;
- }
- return (true);
+ *entry = cur;
+ return (TRUE);
}
- } while (root != NULL);
- *entry = lesseq ? llist : rlist;
- return (false);
+ } while (cur != NULL);
+ *entry = lbound;
+ return (FALSE);
}
-bool
-vm_map_lookup_entry(vm_map_t map, vm_offset_t addr,
- vm_map_entry_t *entry) /* OUT */
-{
- return (vm_map_lookup_helper(map, addr, true, entry, NULL));
-}
-
-static bool
-vm_map_lookup_entry_ge(vm_map_t map, vm_offset_t addr,
- vm_map_entry_t *entry) /* OUT */
-{
- return (vm_map_lookup_helper(map, addr, false, entry, NULL));
-}
-
/*
* vm_map_insert:
*
@@ -1435,7 +1422,7 @@ int
vm_map_insert(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
vm_offset_t start, vm_offset_t end, vm_prot_t prot, vm_prot_t max, int cow)
{
- vm_map_entry_t new_entry, prev_entry;
+ vm_map_entry_t new_entry, prev_entry, temp_entry;
struct ucred *cred;
vm_eflags_t protoeflags;
vm_inherit_t inheritance;
@@ -1460,9 +1447,11 @@ vm_map_insert(vm_map_t map, vm_object_t object, vm_oof
* Find the entry prior to the proposed starting address; if it's part
* of an existing entry, this range is bogus.
*/
- if (vm_map_lookup_entry(map, start, &prev_entry))
+ if (vm_map_lookup_entry(map, start, &temp_entry))
return (KERN_NO_SPACE);
+ prev_entry = temp_entry;
+
/*
* Assert that the next entry doesn't overlap the end point.
*/
@@ -2325,8 +2314,10 @@ vm_map_submap(
VM_MAP_RANGE_CHECK(map, start, end);
- if (vm_map_lookup_entry_ge(map, start, &entry))
+ if (vm_map_lookup_entry(map, start, &entry)) {
vm_map_clip_start(map, entry, start);
+ } else
+ entry = entry->next;
vm_map_clip_end(map, entry, end);
@@ -2481,7 +2472,8 @@ again:
VM_MAP_RANGE_CHECK(map, start, end);
- vm_map_lookup_entry_ge(map, start, &entry);
+ if (!vm_map_lookup_entry(map, start, &entry))
+ entry = entry->next;
/*
* Make a first pass to check for protection violations.
@@ -2671,9 +2663,11 @@ vm_map_madvise(
*/
VM_MAP_RANGE_CHECK(map, start, end);
- if (vm_map_lookup_entry_ge(map, start, &entry)) {
+ if (vm_map_lookup_entry(map, start, &entry)) {
if (modify_map)
vm_map_clip_start(map, entry, start);
+ } else {
+ entry = entry->next;
}
if (modify_map) {
@@ -2805,6 +2799,7 @@ vm_map_inherit(vm_map_t map, vm_offset_t start, vm_off
vm_inherit_t new_inheritance)
{
vm_map_entry_t entry;
+ vm_map_entry_t temp_entry;
switch (new_inheritance) {
case VM_INHERIT_NONE:
@@ -2819,8 +2814,11 @@ vm_map_inherit(vm_map_t map, vm_offset_t start, vm_off
return (KERN_SUCCESS);
vm_map_lock(map);
VM_MAP_RANGE_CHECK(map, start, end);
- if (vm_map_lookup_entry_ge(map, start, &entry))
+ if (vm_map_lookup_entry(map, start, &temp_entry)) {
+ entry = temp_entry;
vm_map_clip_start(map, entry, start);
+ } else
+ entry = temp_entry->next;
while (entry->start < end) {
vm_map_clip_end(map, entry, end);
if ((entry->eflags & MAP_ENTRY_GUARD) == 0 ||
@@ -2853,8 +2851,10 @@ vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offs
user_unwire = (flags & VM_MAP_WIRE_USER) ? TRUE : FALSE;
vm_map_lock(map);
VM_MAP_RANGE_CHECK(map, start, end);
- if (!vm_map_lookup_entry_ge(map, start, &first_entry)) {
- if ((flags & VM_MAP_WIRE_HOLESOK) == 0) {
+ if (!vm_map_lookup_entry(map, start, &first_entry)) {
+ if (flags & VM_MAP_WIRE_HOLESOK)
+ first_entry = first_entry->next;
+ else {
vm_map_unlock(map);
return (KERN_INVALID_ADDRESS);
}
@@ -2882,9 +2882,11 @@ vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offs
* Specifically, the entry may have been
* clipped, merged, or deleted.
*/
- if (!vm_map_lookup_entry_ge(map, saved_start,
+ if (!vm_map_lookup_entry(map, saved_start,
&tmp_entry)) {
- if ((flags & VM_MAP_WIRE_HOLESOK) == 0)
{
+ if (flags & VM_MAP_WIRE_HOLESOK)
+ tmp_entry = tmp_entry->next;
+ else {
if (saved_start == start) {
/*
* First_entry has been
deleted.
@@ -2942,9 +2944,11 @@ vm_map_unwire(vm_map_t map, vm_offset_t start, vm_offs
done:
need_wakeup = FALSE;
if (first_entry == NULL) {
- result = vm_map_lookup_entry_ge(map, start, &first_entry);
- KASSERT(result || (flags & VM_MAP_WIRE_HOLESOK) != 0,
- ("vm_map_unwire: lookup failed"));
+ result = vm_map_lookup_entry(map, start, &first_entry);
+ if (!result && (flags & VM_MAP_WIRE_HOLESOK))
+ first_entry = first_entry->next;
+ else
+ KASSERT(result, ("vm_map_unwire: lookup failed"));
}
for (entry = first_entry; entry->start < end; entry = entry->next) {
/*
@@ -3086,8 +3090,10 @@ vm_map_wire_locked(vm_map_t map, vm_offset_t start, vm
prot |= VM_PROT_WRITE;
user_wire = (flags & VM_MAP_WIRE_USER) ? TRUE : FALSE;
VM_MAP_RANGE_CHECK(map, start, end);
- if (!vm_map_lookup_entry_ge(map, start, &first_entry)) {
- if ((flags & VM_MAP_WIRE_HOLESOK) == 0)
+ if (!vm_map_lookup_entry(map, start, &first_entry)) {
+ if (flags & VM_MAP_WIRE_HOLESOK)
+ first_entry = first_entry->next;
+ else
return (KERN_INVALID_ADDRESS);
}
last_timestamp = map->timestamp;
@@ -3113,9 +3119,11 @@ vm_map_wire_locked(vm_map_t map, vm_offset_t start, vm
* Specifically, the entry may have been
* clipped, merged, or deleted.
*/
- if (!vm_map_lookup_entry_ge(map, saved_start,
+ if (!vm_map_lookup_entry(map, saved_start,
&tmp_entry)) {
- if ((flags & VM_MAP_WIRE_HOLESOK) == 0)
{
+ if (flags & VM_MAP_WIRE_HOLESOK)
+ tmp_entry = tmp_entry->next;
+ else {
if (saved_start == start) {
/*
* first_entry has been
deleted.
@@ -3248,9 +3256,11 @@ vm_map_wire_locked(vm_map_t map, vm_offset_t start, vm
done:
need_wakeup = FALSE;
if (first_entry == NULL) {
- result = vm_map_lookup_entry_ge(map, start, &first_entry);
- KASSERT(result || (flags & VM_MAP_WIRE_HOLESOK) != 0,
- ("vm_map_wire: lookup failed"));
+ result = vm_map_lookup_entry(map, start, &first_entry);
+ if (!result && (flags & VM_MAP_WIRE_HOLESOK))
+ first_entry = first_entry->next;
+ else
+ KASSERT(result, ("vm_map_wire: lookup failed"));
}
for (entry = first_entry; entry->start < end; entry = entry->next) {
/*
@@ -3351,8 +3361,7 @@ vm_map_sync(
if (!vm_map_lookup_entry(map, start, &entry)) {
vm_map_unlock_read(map);
return (KERN_INVALID_ADDRESS);
- }
- if (start == end) {
+ } else if (start == end) {
start = entry->start;
end = entry->end;
}
@@ -3407,10 +3416,9 @@ vm_map_sync(
start += size;
vm_object_deallocate(object);
vm_map_lock_read(map);
- if (last_timestamp == map->timestamp)
+ if (last_timestamp == map->timestamp ||
+ !vm_map_lookup_entry(map, start, ¤t))
current = current->next;
- else
- vm_map_lookup_entry_ge(map, start, ¤t);
}
vm_map_unlock_read(map);
@@ -3543,6 +3551,7 @@ int
vm_map_delete(vm_map_t map, vm_offset_t start, vm_offset_t end)
{
vm_map_entry_t entry;
+ vm_map_entry_t first_entry;
VM_MAP_ASSERT_LOCKED(map);
if (start == end)
@@ -3551,8 +3560,12 @@ vm_map_delete(vm_map_t map, vm_offset_t start, vm_offs
/*
* Find the start of the region, and clip it
*/
- if (vm_map_lookup_entry_ge(map, start, &entry))
+ if (!vm_map_lookup_entry(map, start, &first_entry))
+ entry = first_entry->next;
+ else {
+ entry = first_entry;
vm_map_clip_start(map, entry, start);
+ }
/*
* Step through all entries in this region
@@ -3570,22 +3583,29 @@ vm_map_delete(vm_map_t map, vm_offset_t start, vm_offs
vm_map_entry_system_wired_count(entry) != 0)) {
unsigned int last_timestamp;
vm_offset_t saved_start;
+ vm_map_entry_t tmp_entry;
saved_start = entry->start;
entry->eflags |= MAP_ENTRY_NEEDS_WAKEUP;
last_timestamp = map->timestamp;
(void) vm_map_unlock_and_wait(map, 0);
vm_map_lock(map);
- if (last_timestamp + 1 == map->timestamp)
- continue;
-
- /*
- * Look again for the entry because the map was
- * modified while it was unlocked. Specifically, the
- * entry may have been clipped, merged, or deleted.
- */
- if (vm_map_lookup_entry_ge(map, saved_start, &entry))
- vm_map_clip_start(map, entry, saved_start);
+ if (last_timestamp + 1 != map->timestamp) {
+ /*
+ * Look again for the entry because the map was
+ * modified while it was unlocked.
+ * Specifically, the entry may have been
+ * clipped, merged, or deleted.
+ */
+ if (!vm_map_lookup_entry(map, saved_start,
+ &tmp_entry))
+ entry = tmp_entry->next;
+ else {
+ entry = tmp_entry;
+ vm_map_clip_start(map, entry,
+ saved_start);
+ }
+ }
continue;
}
vm_map_clip_end(map, entry, end);
@@ -3660,9 +3680,11 @@ vm_map_check_protection(vm_map_t map, vm_offset_t star
vm_prot_t protection)
{
vm_map_entry_t entry;
+ vm_map_entry_t tmp_entry;
- if (!vm_map_lookup_entry(map, start, &entry))
+ if (!vm_map_lookup_entry(map, start, &tmp_entry))
return (FALSE);
+ entry = tmp_entry;
while (start < end) {
/*
@@ -4098,7 +4120,7 @@ static int
vm_map_stack_locked(vm_map_t map, vm_offset_t addrbos, vm_size_t max_ssize,
vm_size_t growsize, vm_prot_t prot, vm_prot_t max, int cow)
{
- vm_map_entry_t new_entry;
+ vm_map_entry_t new_entry, prev_entry;
vm_offset_t bot, gap_bot, gap_top, top;
vm_size_t init_ssize, sgp;
int orient, rv;
@@ -4126,13 +4148,13 @@ vm_map_stack_locked(vm_map_t map, vm_offset_t addrbos,
init_ssize = max_ssize - sgp;
/* If addr is already mapped, no go */
- if (vm_map_lookup_entry_ge(map, addrbos, &new_entry))
+ if (vm_map_lookup_entry(map, addrbos, &prev_entry))
return (KERN_NO_SPACE);
/*
* If we can't accommodate max_ssize in the current mapping, no go.
*/
- if (new_entry->start < addrbos + max_ssize)
+ if (prev_entry->next->start < addrbos + max_ssize)
return (KERN_NO_SPACE);
/*
@@ -4159,6 +4181,7 @@ vm_map_stack_locked(vm_map_t map, vm_offset_t addrbos,
rv = vm_map_insert(map, NULL, 0, bot, top, prot, max, cow);
if (rv != KERN_SUCCESS)
return (rv);
+ new_entry = prev_entry->next;
KASSERT(new_entry->end == top || new_entry->start == bot,
("Bad entry start/end for new stack entry"));
KASSERT((orient & MAP_STACK_GROWS_DOWN) == 0 ||
@@ -4217,18 +4240,19 @@ vm_map_growstack(vm_map_t map, vm_offset_t addr, vm_ma
vmemlim = lim_cur(curthread, RLIMIT_VMEM);
retry:
/* If addr is not in a hole for a stack grow area, no need to grow. */
- if (gap_entry == NULL &&
- !vm_map_lookup_helper(map, addr, true, &gap_entry, &stack_entry))
+ if (gap_entry == NULL && !vm_map_lookup_entry(map, addr, &gap_entry))
return (KERN_FAILURE);
if ((gap_entry->eflags & MAP_ENTRY_GUARD) == 0)
return (KERN_SUCCESS);
if ((gap_entry->eflags & MAP_ENTRY_STACK_GAP_DN) != 0) {
+ stack_entry = gap_entry->next;
if ((stack_entry->eflags & MAP_ENTRY_GROWS_DOWN) == 0 ||
stack_entry->start != gap_entry->end)
return (KERN_FAILURE);
grow_amount = round_page(stack_entry->start - addr);
grow_down = true;
} else if ((gap_entry->eflags & MAP_ENTRY_STACK_GAP_UP) != 0) {
+ stack_entry = gap_entry->prev;
if ((stack_entry->eflags & MAP_ENTRY_GROWS_UP) == 0 ||
stack_entry->end != gap_entry->start)
return (KERN_FAILURE);
Modified: head/sys/vm/vm_map.h
==============================================================================
--- head/sys/vm/vm_map.h Wed Jun 26 03:06:57 2019 (r349404)
+++ head/sys/vm/vm_map.h Wed Jun 26 03:12:57 2019 (r349405)
@@ -415,7 +415,7 @@ int vm_map_lookup (vm_map_t *, vm_offset_t, vm_prot_t,
int vm_map_lookup_locked(vm_map_t *, vm_offset_t, vm_prot_t, vm_map_entry_t *,
vm_object_t *,
vm_pindex_t *, vm_prot_t *, boolean_t *);
void vm_map_lookup_done (vm_map_t, vm_map_entry_t);
-bool vm_map_lookup_entry(vm_map_t, vm_offset_t, vm_map_entry_t *);
+boolean_t vm_map_lookup_entry (vm_map_t, vm_offset_t, vm_map_entry_t *);
int vm_map_protect (vm_map_t, vm_offset_t, vm_offset_t, vm_prot_t, boolean_t);
int vm_map_remove (vm_map_t, vm_offset_t, vm_offset_t);
void vm_map_simplify_entry(vm_map_t map, vm_map_entry_t entry);
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
