Page MenuHomeFreeBSD
Files F151149202

D21964.id65043.diff
No OneTemporary
Actions

D21964.id65043.diff
View Options

Index: sys/vm/vm_map.h
===================================================================
--- sys/vm/vm_map.h
+++ sys/vm/vm_map.h
@@ -99,10 +99,8 @@
* Also included is control information for virtual copy operations.
*/
struct vm_map_entry {
- struct vm_map_entry *prev; /* previous entry */
- struct vm_map_entry *next; /* next entry */
- struct vm_map_entry *left; /* left child in binary search tree */
- struct vm_map_entry *right; /* right child in binary search tree */
+ struct vm_map_entry *left; /* left child or previous entry */
+ struct vm_map_entry *right; /* right child or next entry */
vm_offset_t start; /* start address */
vm_offset_t end; /* end address */
vm_offset_t next_read; /* vaddr of the next sequential read */
@@ -424,14 +422,21 @@
vm_map_entry_first(vm_map_t map)
{
- return (map->header.next);
+ return (map->header.right);
}
static inline vm_map_entry_t
vm_map_entry_succ(vm_map_entry_t entry)
{
+ vm_map_entry_t after;
- return (entry->next);
+ after = entry->right;
+ if (after->left->start > entry->start) {
+ do
+ after = after->left;
+ while (after->left != entry);
+ }
+ return (after);
}
#define VM_MAP_ENTRY_FOREACH(it, map) \
Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -885,7 +885,6 @@
_vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
{
- map->header.next = map->header.prev = &map->header;
map->header.eflags = MAP_ENTRY_HEADER;
map->needs_wakeup = FALSE;
map->system_map = 0;
@@ -893,6 +892,7 @@
map->header.end = min;
map->header.start = max;
map->flags = 0;
+ map->header.left = map->header.right = &map->header;
map->root = NULL;
map->timestamp = 0;
map->busy = 0;
@@ -966,7 +966,7 @@
vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
{
- return (root->left != NULL ?
+ return (root->left != left_ancestor ?
root->left->max_free : root->start - left_ancestor->end);
}
@@ -974,7 +974,7 @@
vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
{
- return (root->right != NULL ?
+ return (root->right != right_ancestor ?
root->right->max_free : right_ancestor->start - root->end);
}
@@ -987,8 +987,15 @@
static inline vm_map_entry_t
vm_map_entry_pred(vm_map_entry_t entry)
{
+ vm_map_entry_t prior;
- return (entry->prev);
+ prior = entry->left;
+ if (prior->right->start < entry->start) {
+ do
+ prior = prior->right;
+ while (prior->right != entry);
+ }
+ return (prior);
}
/* vm_map_entry_succ is defined in vm_map.h. */
@@ -1000,7 +1007,7 @@
return (a > b ? a : b);
}
-#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \
+#define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \
vm_size_t max_free; \
\
/* \
@@ -1012,12 +1019,14 @@
max_free = root->max_free; \
KASSERT(max_free >= vm_map_entry_max_free_right(root, rlist), \
("%s: max_free invariant fails", __func__)); \
- if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
+ if (y == llist ? max_free > 0 : max_free - 1 < y->max_free) \
max_free = vm_map_entry_max_free_right(root, rlist); \
- if (y != NULL && (test)) { \
+ if (y != llist && (test)) { \
/* Rotate right and make y root. */ \
- root->left = y->right; \
- y->right = root; \
+ if (y->right != root) { \
+ root->left = y->right; \
+ y->right = root; \
+ } \
if (max_free < y->max_free) \
root->max_free = max_free = \
vm_size_max(max_free, \
@@ -1031,10 +1040,10 @@
("%s: max_free not copied from right", __func__)); \
root->left = rlist; \
rlist = root; \
- root = y; \
+ root = y != llist ? y : NULL; \
} while (0)
-#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \
+#define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do { \
vm_size_t max_free; \
\
/* \
@@ -1046,12 +1055,14 @@
max_free = root->max_free; \
KASSERT(max_free >= vm_map_entry_max_free_left(root, llist), \
("%s: max_free invariant fails", __func__)); \
- if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free) \
+ if (y == rlist ? max_free > 0 : max_free - 1 < y->max_free) \
max_free = vm_map_entry_max_free_left(root, llist); \
- if (y != NULL && (test)) { \
+ if (y != rlist && (test)) { \
/* Rotate left and make y root. */ \
- root->right = y->left; \
- y->left = root; \
+ if (y->left != root) { \
+ root->right = y->left; \
+ y->left = root; \
+ } \
if (max_free < y->max_free) \
root->max_free = max_free = \
vm_size_max(max_free, \
@@ -1065,17 +1076,17 @@
("%s: max_free not copied from left", __func__)); \
root->right = llist; \
llist = root; \
- root = y; \
+ root = y != rlist ? y : NULL; \
} while (0)
/*
- * 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, and both lists terminated by &map->header. This function, and
- * the subsequent call to vm_map_splay_merge, rely on the start and end address
+ * Walk down the tree until we find addr or a gap where addr would go, breaking
+ * off left and right subtrees of nodes less than, or greater than addr. Treat
+ * subtrees with root->max_free < length as empty trees. 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, and both
+ * lists terminated by &map->header. This function, and the subsequent call to
+ * vm_map_splay_merge_{left,right,pred,succ}, rely on the start and end address
* values in &map->header.
*/
static __always_inline vm_map_entry_t
@@ -1091,10 +1102,10 @@
root->end <= (*rlist)->start,
("%s: root not within tree bounds", __func__));
if (addr < root->start) {
- SPLAY_LEFT_STEP(root, y, *rlist,
+ SPLAY_LEFT_STEP(root, y, *llist, *rlist,
y->max_free >= length && addr < y->start);
} else if (addr >= root->end) {
- SPLAY_RIGHT_STEP(root, y, *llist,
+ SPLAY_RIGHT_STEP(root, y, *llist, *rlist,
y->max_free >= length && addr >= y->end);
} else
break;
@@ -1107,9 +1118,9 @@
{
vm_map_entry_t hi, y;
- hi = root->right;
+ hi = root->right == *rlist ? NULL : root->right;
while (hi != NULL)
- SPLAY_LEFT_STEP(hi, y, *rlist, true);
+ SPLAY_LEFT_STEP(hi, y, root, *rlist, true);
}
static __always_inline void
@@ -1117,9 +1128,9 @@
{
vm_map_entry_t lo, y;
- lo = root->left;
+ lo = root->left == *llist ? NULL : root->left;
while (lo != NULL)
- SPLAY_RIGHT_STEP(lo, y, *llist, true);
+ SPLAY_RIGHT_STEP(lo, y, *llist, root, true);
}
static inline void
@@ -1167,9 +1178,10 @@
max_free = root->start - llist->end;
if (llist != header) {
max_free = vm_map_splay_merge_left_walk(header, root,
- NULL, max_free, llist);
+ root, max_free, llist);
} else {
- root->left = NULL;
+ root->left = header;
+ header->right = root;
}
return (max_free);
}
@@ -1186,7 +1198,8 @@
max_free = vm_map_entry_max_free_left(root, llist);
if (llist != header) {
max_free = vm_map_splay_merge_left_walk(header, root,
- root->left, max_free, llist);
+ root->left == llist ? root : root->left,
+ max_free, llist);
}
return (max_free);
}
@@ -1222,9 +1235,10 @@
max_free = rlist->start - root->end;
if (rlist != header) {
max_free = vm_map_splay_merge_right_walk(header, root,
- NULL, max_free, rlist);
+ root, max_free, rlist);
} else {
- root->right = NULL;
+ root->right = header;
+ header->left = root;
}
return (max_free);
}
@@ -1241,7 +1255,8 @@
max_free = vm_map_entry_max_free_right(root, rlist);
if (rlist != header) {
max_free = vm_map_splay_merge_right_walk(header, root,
- root->right, max_free, rlist);
+ root->right == rlist ? root : root->right,
+ max_free, rlist);
}
return (max_free);
}
@@ -1256,6 +1271,14 @@
* the pointers and compute max_free. The time bound is O(log n)
* amortized.
*
+ * The tree is threaded, which means that there are no null pointers.
+ * When a node has no left child, its left pointer points to its
+ * predecessor, which the last ancestor on the search path from the root
+ * where the search branched right. Likewise, when a node has no right
+ * child, its right pointer points to its successor. The map header node
+ * is the predecessor of the first map entry, and the successor of the
+ * last.
+ *
* 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.
*
@@ -1321,9 +1344,6 @@
root = vm_map_splay_split(map, entry->start, 0, &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 = entry;
root->max_free = vm_size_max(
vm_map_splay_merge_pred(header, root, llist),
@@ -1341,7 +1361,7 @@
vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry,
enum unlink_merge_type op)
{
- vm_map_entry_t header, llist, rlist, root, y;
+ vm_map_entry_t header, llist, rlist, root;
vm_size_t max_free_left, max_free_right;
VM_MAP_ASSERT_LOCKED(map);
@@ -1366,11 +1386,10 @@
rlist = root->left;
max_free_left = vm_map_splay_merge_pred(header, root, llist);
max_free_right = vm_map_splay_merge_right(header, root, rlist);
- } else
+ } else {
+ header->left = header->right = header;
root = NULL;
- y = entry->next;
- y->prev = entry->prev;
- y->prev->next = y;
+ }
if (root != NULL)
root->max_free = vm_size_max(max_free_left, max_free_right);
map->root = root;
@@ -1424,7 +1443,7 @@
vm_offset_t address,
vm_map_entry_t *entry) /* OUT */
{
- vm_map_entry_t cur, header, lbound;
+ vm_map_entry_t cur, header, lbound, ubound;
boolean_t locked;
/*
@@ -1471,18 +1490,23 @@
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
- lbound = header;
- do {
+ lbound = ubound = header;
+ for (;;) {
if (address < cur->start) {
+ ubound = cur;
cur = cur->left;
+ if (cur == lbound)
+ break;
} else if (cur->end <= address) {
lbound = cur;
cur = cur->right;
+ if (cur == ubound)
+ break;
} else {
*entry = cur;
return (TRUE);
}
- } while (cur != NULL);
+ }
*entry = lbound;
return (FALSE);
}
@@ -1749,7 +1773,7 @@
gap_end = rlist->start;
if (root != NULL) {
start = root->end;
- if (root->right != NULL)
+ if (root->right != rlist)
gap_end = start;
max_free_left = vm_map_splay_merge_left(header, root, llist);
max_free_right = vm_map_splay_merge_right(header, root, rlist);
@@ -1771,7 +1795,7 @@
return (start);
/* With max_free, can immediately tell if no solution. */
- if (root->right == NULL || length > root->right->max_free)
+ if (root->right == header || length > root->right->max_free)
return (vm_map_max(map) - length + 1);
/*
@@ -1781,10 +1805,10 @@
for (left_length = 0;;
left_length = vm_map_entry_max_free_left(root, llist)) {
if (length <= left_length)
- SPLAY_LEFT_STEP(root, y, rlist,
+ SPLAY_LEFT_STEP(root, y, llist, rlist,
length <= vm_map_entry_max_free_left(y, llist));
else
- SPLAY_RIGHT_STEP(root, y, llist,
+ SPLAY_RIGHT_STEP(root, y, llist, rlist,
length > vm_map_entry_max_free_left(y, root));
if (root == NULL)
break;
@@ -1801,7 +1825,6 @@
y->max_free = vm_size_max(
vm_map_splay_merge_pred(root, y, root),
vm_map_splay_merge_right(header, y, rlist));
- root->right = y;
root->max_free = vm_size_max(max_free_left, y->max_free);
}
map->root = root;
@@ -4954,6 +4977,7 @@
_vm_map_assert_consistent(vm_map_t map, int check)
{
vm_map_entry_t entry, prev;
+ vm_map_entry_t cur, header, lbound, ubound;
vm_size_t max_left, max_right;
#ifdef DIAGNOSTIC
@@ -4962,7 +4986,7 @@
if (enable_vmmap_check != check)
return;
- prev = &map->header;
+ header = prev = &map->header;
VM_MAP_ENTRY_FOREACH(entry, map) {
KASSERT(prev->end <= entry->start,
("map %p prev->end = %jx, start = %jx", map,
@@ -4970,23 +4994,39 @@
KASSERT(entry->start < entry->end,
("map %p start = %jx, end = %jx", map,
(uintmax_t)entry->start, (uintmax_t)entry->end));
- KASSERT(entry->end <= vm_map_entry_succ(entry)->start,
- ("map %p end = %jx, next->start = %jx", map,
- (uintmax_t)entry->end,
- (uintmax_t)vm_map_entry_succ(entry)->start));
- KASSERT(entry->left == NULL ||
+ KASSERT(entry->left == header ||
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 ||
+ KASSERT(entry->right == header ||
entry->start < entry->right->start,
("map %p start = %jx, right->start = %jx", map,
(uintmax_t)entry->start, (uintmax_t)entry->right->start));
- max_left = vm_map_entry_max_free_left(entry,
- vm_map_entry_pred(entry));
- max_right = vm_map_entry_max_free_right(entry,
- vm_map_entry_succ(entry));
- KASSERT(entry->max_free == MAX(max_left, max_right),
+ cur = map->root;
+ lbound = ubound = header;
+ for (;;) {
+ if (entry->start < cur->start) {
+ ubound = cur;
+ cur = cur->left;
+ KASSERT(cur != lbound,
+ ("map %p cannot find %jx",
+ map, entry->start));
+ } else if (cur->end <= entry->start) {
+ lbound = cur;
+ cur = cur->right;
+ KASSERT(cur != ubound,
+ ("map %p cannot find %jx",
+ map, entry->start));
+ } else {
+ KASSERT(cur == entry,
+ ("map %p cannot find %jx",
+ map, entry->start));
+ break;
+ }
+ }
+ max_left = vm_map_entry_max_free_left(entry, lbound);
+ max_right = vm_map_entry_max_free_right(entry, ubound);
+ KASSERT(entry->max_free == vm_size_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));

File Metadata

Mime Type
text/plain
Expires
Tue, Apr 7, 10:36 AM (18 h, 54 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31023164
Default Alt Text
D21964.id65043.diff (14 KB)

Event Timeline