Index: head/sys/vm/vm_map.h =================================================================== --- head/sys/vm/vm_map.h +++ head/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 */ @@ -175,9 +173,12 @@ /* * A map is a set of map entries. These map entries are - * organized both as a binary search tree and as a doubly-linked - * list. Both structures are ordered based upon the start and - * end addresses contained within each map entry. + * organized as a threaded binary search tree. Both structures + * are ordered based upon the start and end addresses contained + * within each map entry. The largest gap between an entry in a + * subtree and one of its neighbors is saved in the max_free + * field, and that field is updated when the tree is + * restructured. * * Sleator and Tarjan's top-down splay algorithm is employed to * control height imbalance in the binary search tree. @@ -185,10 +186,12 @@ * The map's min offset value is stored in map->header.end, and * its max offset value is stored in map->header.start. These * values act as sentinels for any forward or backward address - * scan of the list. The map header has a special value for the - * eflags field, MAP_ENTRY_HEADER, that is set initially, is - * never changed, and prevents an eflags match of the header - * with any other map entry. + * scan of the list. The right and left fields of the map + * header point to the first and list map entries. The map + * header has a special value for the eflags field, + * MAP_ENTRY_HEADER, that is set initially, is never changed, + * and prevents an eflags match of the header with any other map + * entry. * * List of locks * (c) const until freed @@ -424,14 +427,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: head/sys/vm/vm_map.c =================================================================== --- head/sys/vm/vm_map.c +++ head/sys/vm/vm_map.c @@ -896,7 +896,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; @@ -904,6 +903,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; @@ -977,7 +977,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); } @@ -985,7 +985,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); } @@ -994,16 +994,22 @@ * * Find the {predecessor, successor} of the entry by taking one step * in the appropriate direction and backtracking as much as necessary. + * vm_map_entry_succ is defined in vm_map.h. */ 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. */ - static inline vm_size_t vm_size_max(vm_size_t a, vm_size_t b) { @@ -1011,7 +1017,8 @@ 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_map_entry_t z; \ vm_size_t max_free; \ \ /* \ @@ -1023,16 +1030,20 @@ 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 (max_free < y->max_free) \ + z = y->right; \ + if (z != root) { \ + root->left = z; \ + y->right = root; \ + if (max_free < y->max_free) \ + root->max_free = max_free = \ + vm_size_max(max_free, z->max_free); \ + } else if (max_free < y->max_free) \ root->max_free = max_free = \ - vm_size_max(max_free, \ - vm_map_entry_max_free_left(root, y)); \ + vm_size_max(max_free, root->start - y->end);\ root = y; \ y = root->left; \ } \ @@ -1042,10 +1053,11 @@ ("%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_map_entry_t z; \ vm_size_t max_free; \ \ /* \ @@ -1057,16 +1069,20 @@ 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 (max_free < y->max_free) \ + z = y->left; \ + if (z != root) { \ + root->right = z; \ + y->left = root; \ + if (max_free < y->max_free) \ + root->max_free = max_free = \ + vm_size_max(max_free, z->max_free); \ + } else if (max_free < y->max_free) \ root->max_free = max_free = \ - vm_size_max(max_free, \ - vm_map_entry_max_free_right(root, y)); \ + vm_size_max(max_free, y->start - root->end);\ root = y; \ y = root->right; \ } \ @@ -1076,61 +1092,73 @@ ("%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 vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length, vm_map_entry_t *llist, vm_map_entry_t *rlist) { - vm_map_entry_t root, y; + vm_map_entry_t left, right, root, y; - *llist = *rlist = &map->header; + left = right = &map->header; root = map->root; while (root != NULL && root->max_free >= length) { - KASSERT((*llist)->end <= root->start && - root->end <= (*rlist)->start, + KASSERT(left->end <= root->start && + root->end <= right->start, ("%s: root not within tree bounds", __func__)); if (addr < root->start) { - SPLAY_LEFT_STEP(root, y, *rlist, + SPLAY_LEFT_STEP(root, y, left, right, y->max_free >= length && addr < y->start); } else if (addr >= root->end) { - SPLAY_RIGHT_STEP(root, y, *llist, + SPLAY_RIGHT_STEP(root, y, left, right, y->max_free >= length && addr >= y->end); } else break; } + *llist = left; + *rlist = right; return (root); } static __always_inline void vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *rlist) { - vm_map_entry_t hi, y; + vm_map_entry_t hi, right, y; - hi = root->right; - while (hi != NULL) - SPLAY_LEFT_STEP(hi, y, *rlist, true); + right = *rlist; + hi = root->right == right ? NULL : root->right; + if (hi == NULL) + return; + do + SPLAY_LEFT_STEP(hi, y, root, right, true); + while (hi != NULL); + *rlist = right; } static __always_inline void vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist) { - vm_map_entry_t lo, y; + vm_map_entry_t left, lo, y; - lo = root->left; - while (lo != NULL) - SPLAY_RIGHT_STEP(lo, y, *llist, true); + left = *llist; + lo = root->left == left ? NULL : root->left; + if (lo == NULL) + return; + do + SPLAY_RIGHT_STEP(lo, y, left, root, true); + while (lo != NULL); + *llist = left; } static inline void @@ -1178,9 +1206,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); } @@ -1197,7 +1226,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); } @@ -1233,9 +1263,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); } @@ -1252,7 +1283,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); } @@ -1267,6 +1299,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. * @@ -1332,9 +1372,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), @@ -1352,7 +1389,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); @@ -1377,11 +1414,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; @@ -1435,7 +1471,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; /* @@ -1482,18 +1518,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); } @@ -1760,7 +1801,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); @@ -1782,7 +1823,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); /* @@ -1792,10 +1833,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; @@ -1812,7 +1853,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; @@ -4961,6 +5001,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 @@ -4969,7 +5010,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, @@ -4977,23 +5018,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));