From owner-svn-src-head@freebsd.org Mon Jun 10 21:34:08 2019 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 46E5115C9E5A; Mon, 10 Jun 2019 21:34:08 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id E62858E25D; Mon, 10 Jun 2019 21:34:07 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id C0128200F5; Mon, 10 Jun 2019 21:34:07 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id x5ALY7DY083836; Mon, 10 Jun 2019 21:34:07 GMT (envelope-from dougm@FreeBSD.org) Received: (from dougm@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id x5ALY71Y083835; Mon, 10 Jun 2019 21:34:07 GMT (envelope-from dougm@FreeBSD.org) Message-Id: <201906102134.x5ALY71Y083835@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dougm set sender to dougm@FreeBSD.org using -f From: Doug Moore Date: Mon, 10 Jun 2019 21:34:07 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r348881 - head/sys/vm X-SVN-Group: head X-SVN-Commit-Author: dougm X-SVN-Commit-Paths: head/sys/vm X-SVN-Commit-Revision: 348881 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: E62858E25D X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-2.97 / 15.00]; local_wl_from(0.00)[FreeBSD.org]; NEURAL_HAM_MEDIUM(-1.00)[-0.999,0]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; NEURAL_HAM_SHORT(-0.97)[-0.974,0]; ASN(0.00)[asn:11403, ipnet:2610:1c1:1::/48, country:US] X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 10 Jun 2019 21:34:08 -0000 Author: dougm Date: Mon Jun 10 21:34:07 2019 New Revision: 348881 URL: https://svnweb.freebsd.org/changeset/base/348881 Log: The computations of vm_map_splay_split and vm_map_splay_merge touch both children of every entry on the search path as part of updating values of the max_free field. By comparing the max_free values of an entry and its child on the search path, the code can avoid accessing the child off the path in cases where the max_free value decreases along the path. Specifically, this patch changes splay_split so that the max_free field of every entry on the search path is replaced, temporarily, by the max_free field from its child not on the search path or, if the child in that direction is NULL, then a difference between start and end values of two pointers already available in the split code, without following any next or prev pointers. However, to find that max_free value does not require looking toward that other child if either the child on the search path has a lower max_free value, or the current max_free value is zero, because in either case we know that the value of max_free for the other child is the value we already have. So, the changes to vm_entry_splay_split make sure that we know all the off-search-path entries we will need to complete the splay, without looking at all of them. There is an exception at the bottom of the search path where we cannot rely on the max_free value in the direction of the NULL pointer that ends the search, because of the behavior of entry-clipping code. The corresponding change to vm_splay_entry_merge makes it simpler, since it's just reversing pointers and updating running maxima. In a test intended to exercise vigorously the vm_map implementation, the effect of this change was to reduce the data cache miss rate by 10-14% and the running time by 5-7%. Tested by: pho Reviewed by: alc Approved by: kib (mentor) MFC after: 1 month Differential Revision: https://reviews.freebsd.org/D19826 Modified: head/sys/vm/vm_map.c Modified: head/sys/vm/vm_map.c ============================================================================== --- head/sys/vm/vm_map.c Mon Jun 10 21:27:21 2019 (r348880) +++ head/sys/vm/vm_map.c Mon Jun 10 21:34:07 2019 (r348881) @@ -962,55 +962,92 @@ vm_map_entry_set_behavior(vm_map_entry_t entry, u_char } /* - * vm_map_entry_set_max_free: + * vm_map_entry_max_free_{left,right}: * - * Set the max_free field in a vm_map_entry. + * Compute the size of the largest free gap between two entries, + * one the root of a tree and the other the ancestor of that root + * that is the least or greatest ancestor found on the search path. */ -static inline void -vm_map_entry_set_max_free(vm_map_entry_t entry) +static inline vm_size_t +vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor) { - vm_map_entry_t child; - vm_size_t max_left, max_right; - 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); + return (root->left != NULL ? + root->left->max_free : root->start - left_ancestor->end); } -#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; \ +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 ? + root->right->max_free : right_ancestor->start - root->end); +} + +#define SPLAY_LEFT_STEP(root, y, rlist, test) do { \ + vm_size_t max_free; \ + \ + /* \ + * Infer root->right->max_free == root->max_free when \ + * y->max_free < root->max_free || root->max_free == 0. \ + * Otherwise, look right to find it. \ + */ \ + y = root->left; \ + 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) \ + max_free = vm_map_entry_max_free_right(root, rlist); \ + if (y != NULL && (test)) { \ + /* Rotate right and make y root. */ \ + root->left = y->right; \ + y->right = root; \ + if (max_free < y->max_free) \ + root->max_free = max_free = MAX(max_free, \ + vm_map_entry_max_free_left(root, y)); \ + root = y; \ + y = root->left; \ + } \ + /* Copy right->max_free. Put root on rlist. */ \ + root->max_free = max_free; \ + KASSERT(max_free == vm_map_entry_max_free_right(root, rlist), \ + ("%s: max_free not copied from right", __func__)); \ + 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; \ +#define SPLAY_RIGHT_STEP(root, y, llist, test) do { \ + vm_size_t max_free; \ + \ + /* \ + * Infer root->left->max_free == root->max_free when \ + * y->max_free < root->max_free || root->max_free == 0. \ + * Otherwise, look left to find it. \ + */ \ + y = root->right; \ + 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) \ + max_free = vm_map_entry_max_free_left(root, llist); \ + if (y != NULL && (test)) { \ + /* Rotate left and make y root. */ \ + root->right = y->left; \ + y->left = root; \ + if (max_free < y->max_free) \ + root->max_free = max_free = MAX(max_free, \ + vm_map_entry_max_free_right(root, y)); \ + root = y; \ + y = root->right; \ + } \ + /* Copy left->max_free. Put root on llist. */ \ + root->max_free = max_free; \ + KASSERT(max_free == vm_map_entry_max_free_left(root, llist), \ + ("%s: max_free not copied from left", __func__)); \ + root->right = llist; \ + llist = root; \ + root = y; \ } while (0) /* @@ -1019,18 +1056,21 @@ vm_map_entry_set_max_free(vm_map_entry_t entry) * 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. + * 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 + * values in &map->header. */ static vm_map_entry_t -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_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length, + vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist) { - vm_map_entry_t llist, rlist; - vm_map_entry_t y; + vm_map_entry_t llist, rlist, root, y; - llist = NULL; - rlist = NULL; + llist = rlist = &map->header; + root = map->root; while (root != NULL && root->max_free >= length) { + KASSERT(llist->end <= root->start && root->end <= rlist->start, + ("%s: root not within tree bounds", __func__)); if (addr < root->start) { SPLAY_LEFT_STEP(root, y, rlist, y->max_free >= length && addr < y->start); @@ -1069,44 +1109,65 @@ vm_map_splay_findprev(vm_map_entry_t root, vm_map_entr *iolist = llist; } +static inline void +vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b) +{ + vm_map_entry_t tmp; + + tmp = *b; + *b = *a; + *a = tmp; +} + /* * 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) +static void +vm_map_splay_merge(vm_map_t map, vm_map_entry_t root, + vm_map_entry_t llist, vm_map_entry_t rlist) { - vm_map_entry_t y; + vm_map_entry_t prev; + vm_size_t max_free_left, max_free_right; - while (llist != NULL) { - y = llist->right; - llist->right = ltree; - vm_map_entry_set_max_free(llist); - ltree = llist; - llist = y; + max_free_left = vm_map_entry_max_free_left(root, llist); + if (llist != &map->header) { + prev = root->left; + do { + /* + * The max_free values of the children of llist are in + * llist->max_free and max_free_left. Update with the + * max value. + */ + llist->max_free = max_free_left = + MAX(llist->max_free, max_free_left); + vm_map_entry_swap(&llist->right, &prev); + vm_map_entry_swap(&prev, &llist); + } while (llist != &map->header); + root->left = prev; } - while (rlist != NULL) { - y = rlist->left; - rlist->left = rtree; - vm_map_entry_set_max_free(rlist); - rtree = rlist; - rlist = y; - } - - /* - * Final assembly: add ltree and rtree as subtrees of root. - */ - root->left = ltree; - root->right = rtree; - vm_map_entry_set_max_free(root); - - return (root); + max_free_right = vm_map_entry_max_free_right(root, rlist); + if (rlist != &map->header) { + prev = root->right; + do { + /* + * The max_free values of the children of rlist are in + * rlist->max_free and max_free_right. Update with the + * max value. + */ + rlist->max_free = max_free_right = + MAX(rlist->max_free, max_free_right); + vm_map_entry_swap(&rlist->left, &prev); + vm_map_entry_swap(&prev, &rlist); + } while (rlist != &map->header); + root->right = prev; + } + root->max_free = MAX(max_free_left, max_free_right); + map->root = root; } /* - * vm_map_entry_splay: + * vm_map_splay: * * The Sleator and Tarjan top-down splay algorithm with the * following variation. Max_free must be computed bottom-up, so @@ -1123,14 +1184,14 @@ vm_map_splay_merge(vm_map_entry_t root, * Returns: the new root. */ static vm_map_entry_t -vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root) +vm_map_splay(vm_map_t map, vm_offset_t addr) { - vm_map_entry_t llist, rlist; + vm_map_entry_t llist, rlist, root; - root = vm_map_splay_split(addr, 0, root, &llist, &rlist); + root = vm_map_splay_split(map, addr, 0, &llist, &rlist); if (root != NULL) { /* do nothing */ - } else if (llist != NULL) { + } else if (llist != &map->header) { /* * Recover the greatest node in the left * subtree and make it the root. @@ -1138,7 +1199,7 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro root = llist; llist = root->right; root->right = NULL; - } else if (rlist != NULL) { + } else if (rlist != &map->header) { /* * Recover the least node in the right * subtree and make it the root. @@ -1150,8 +1211,9 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro /* There is no root. */ return (NULL); } - return (vm_map_splay_merge(root, llist, rlist, - root->left, root->right)); + vm_map_splay_merge(map, root, llist, rlist); + VM_MAP_ASSERT_CONSISTENT(map); + return (root); } /* @@ -1160,8 +1222,7 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t ro * Insert/remove entries from maps. */ static void -vm_map_entry_link(vm_map_t map, - vm_map_entry_t entry) +vm_map_entry_link(vm_map_t map, vm_map_entry_t entry) { vm_map_entry_t llist, rlist, root; @@ -1170,15 +1231,14 @@ vm_map_entry_link(vm_map_t map, map->nentries, entry); VM_MAP_ASSERT_LOCKED(map); map->nentries++; - root = map->root; - root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); + 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 == 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; + entry->prev = llist; + entry->next = rlist; + llist->next = rlist->prev = entry; + entry->left = entry->right = NULL; + vm_map_splay_merge(map, entry, llist, rlist); VM_MAP_ASSERT_CONSISTENT(map); } @@ -1189,19 +1249,13 @@ enum unlink_merge_type { }; static void -vm_map_entry_unlink(vm_map_t map, - vm_map_entry_t entry, - enum unlink_merge_type op) +vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry, + enum unlink_merge_type op) { vm_map_entry_t llist, rlist, root, y; VM_MAP_ASSERT_LOCKED(map); - 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); + root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); KASSERT(root != NULL, ("vm_map_entry_unlink: unlink object not mapped")); @@ -1226,11 +1280,11 @@ vm_map_entry_unlink(vm_map_t map, case UNLINK_MERGE_NONE: vm_map_splay_findprev(root, &llist); vm_map_splay_findnext(root, &rlist); - if (llist != NULL) { + if (llist != &map->header) { root = llist; llist = root->right; root->right = NULL; - } else if (rlist != NULL) { + } else if (rlist != &map->header) { root = rlist; rlist = root->left; root->left = NULL; @@ -1238,10 +1292,13 @@ vm_map_entry_unlink(vm_map_t map, root = NULL; break; } + y = entry->next; + y->prev = entry->prev; + y->prev->next = y; if (root != NULL) - root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); - map->root = root; + vm_map_splay_merge(map, root, llist, rlist); + else + map->root = NULL; VM_MAP_ASSERT_CONSISTENT(map); map->nentries--; CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map, @@ -1262,15 +1319,13 @@ vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry vm_map_entry_t llist, rlist, root; VM_MAP_ASSERT_LOCKED(map); - root = map->root; - root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); + root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist); KASSERT(root != NULL, ("%s: resize object not mapped", __func__)); vm_map_splay_findnext(root, &rlist); root->right = NULL; entry->end += grow_amount; - map->root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); + vm_map_splay_merge(map, root, llist, rlist); VM_MAP_ASSERT_CONSISTENT(map); CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p", __func__, map, map->nentries, entry); @@ -1316,8 +1371,7 @@ vm_map_lookup_entry( * change the map. Thus, the map's timestamp need not change * on a temporary upgrade. */ - map->root = cur = vm_map_entry_splay(address, cur); - VM_MAP_ASSERT_CONSISTENT(map); + cur = vm_map_splay(map, address); if (!locked) sx_downgrade(&map->lock); @@ -1604,11 +1658,10 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s * After splay, if start comes before root node, then there * must be a gap from start to the root. */ - root = vm_map_splay_split(start, length, map->root, - &llist, &rlist); + root = vm_map_splay_split(map, start, length, &llist, &rlist); if (root != NULL) start = root->end; - else if (rlist != NULL) { + else if (rlist != &map->header) { root = rlist; rlist = root->left; root->left = NULL; @@ -1617,8 +1670,7 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s llist = root->right; root->right = NULL; } - map->root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); + vm_map_splay_merge(map, root, llist, rlist); VM_MAP_ASSERT_CONSISTENT(map); if (start + length <= root->start) return (start); @@ -1639,40 +1691,32 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_s /* * Splay for the least large-enough gap in the right subtree. */ - llist = NULL; - rlist = NULL; - for (left_length = 0; ; - left_length = root->left != NULL ? - root->left->max_free : root->start - llist->end) { + llist = rlist = &map->header; + for (left_length = 0;; + left_length = vm_map_entry_max_free_left(root, llist)) { if (length <= left_length) SPLAY_LEFT_STEP(root, y, rlist, - length <= (y->left != NULL ? - y->left->max_free : y->start - llist->end)); + length <= vm_map_entry_max_free_left(y, llist)); else SPLAY_RIGHT_STEP(root, y, llist, - length > (y->left != NULL ? - y->left->max_free : y->start - root->end)); + length > vm_map_entry_max_free_left(y, root)); if (root == NULL) break; } root = llist; llist = root->right; - if ((y = rlist) == NULL) - root->right = NULL; - else { + root->right = NULL; + if (rlist != &map->header) { + y = rlist; 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); + vm_map_splay_merge(map, y, &map->header, rlist); + y->max_free = MAX( + vm_map_entry_max_free_left(y, root), + vm_map_entry_max_free_right(y, &map->header)); root->right = y; - vm_map_entry_set_max_free(root); } - map->root = root; + vm_map_splay_merge(map, root, llist, &map->header); VM_MAP_ASSERT_CONSISTENT(map); return (root->end); }