Date: Sat, 7 Dec 2019 17:14:33 +0000 (UTC) From: Doug Moore <dougm@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r355491 - head/sys/vm Message-ID: <201912071714.xB7HEXaD016835@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: dougm Date: Sat Dec 7 17:14:33 2019 New Revision: 355491 URL: https://svnweb.freebsd.org/changeset/base/355491 Log: Remove the next and prev fields from vm_map_entry, to save a bit of space. Where the vm_map tree now has null pointers, store pointers to next and previous entries in right and left fields, making the binary tree threaded. Have the predecessor and successor functions compute what the prev and next fields previously stored. Reviewed by: markj, kib (previous version) Tested by: pho (previous version) Differential Revision: https://reviews.freebsd.org/D21964 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 Sat Dec 7 17:10:03 2019 (r355490) +++ head/sys/vm/vm_map.c Sat Dec 7 17:14:33 2019 (r355491) @@ -896,7 +896,6 @@ static void _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 @@ _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t mi 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 @@ static inline vm_size_t 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 @@ static inline vm_size_t 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 @@ vm_map_entry_max_free_right(vm_map_entry_t root, vm_ma * * 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 @@ vm_size_max(vm_size_t a, vm_size_t b) 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 @@ vm_size_max(vm_size_t a, vm_size_t b) 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 @@ vm_size_max(vm_size_t a, vm_size_t b) ("%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 @@ vm_size_max(vm_size_t a, vm_size_t b) 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 @@ vm_size_max(vm_size_t a, vm_size_t b) ("%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 @@ vm_map_splay_merge_pred(vm_map_entry_t header, vm_map_ 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 @@ vm_map_splay_merge_left(vm_map_entry_t header, vm_map_ 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 @@ vm_map_splay_merge_succ(vm_map_entry_t header, vm_map_ 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 @@ vm_map_splay_merge_right(vm_map_entry_t header, vm_map 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 @@ vm_map_splay_merge_right(vm_map_entry_t header, vm_map * 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 @@ vm_map_entry_link(vm_map_t map, vm_map_entry_t entry) 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 @@ static void 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 @@ vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry 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_map_lookup_entry( 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 @@ vm_map_lookup_entry( * 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 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s 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 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s 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 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s 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 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s 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 @@ static void _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 @@ _vm_map_assert_consistent(vm_map_t map, int check) 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 @@ _vm_map_assert_consistent(vm_map_t map, int check) 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)); Modified: head/sys/vm/vm_map.h ============================================================================== --- head/sys/vm/vm_map.h Sat Dec 7 17:10:03 2019 (r355490) +++ head/sys/vm/vm_map.h Sat Dec 7 17:14:33 2019 (r355491) @@ -99,10 +99,8 @@ union vm_map_object { * 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 @@ vm_map_entry_system_wired_count(vm_map_entry_t entry) /* * 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 @@ vm_map_entry_system_wired_count(vm_map_entry_t entry) * 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 @@ static inline vm_map_entry_t 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) \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201912071714.xB7HEXaD016835>