From owner-svn-src-head@FreeBSD.ORG Mon Apr 15 06:12:01 2013 Return-Path: Delivered-To: svn-src-head@freebsd.org Received: from mx1.freebsd.org (mx1.FreeBSD.org [8.8.178.115]) by hub.freebsd.org (Postfix) with ESMTP id 11BFB5F4; Mon, 15 Apr 2013 06:12:01 +0000 (UTC) (envelope-from alc@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) by mx1.freebsd.org (Postfix) with ESMTP id E8EE7642; Mon, 15 Apr 2013 06:12:00 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.6/8.14.6) with ESMTP id r3F6C0kx099135; Mon, 15 Apr 2013 06:12:00 GMT (envelope-from alc@svn.freebsd.org) Received: (from alc@localhost) by svn.freebsd.org (8.14.6/8.14.5/Submit) id r3F6C0w1099134; Mon, 15 Apr 2013 06:12:00 GMT (envelope-from alc@svn.freebsd.org) Message-Id: <201304150612.r3F6C0w1099134@svn.freebsd.org> From: Alan Cox Date: Mon, 15 Apr 2013 06:12:00 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r249502 - head/sys/vm X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.14 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, 15 Apr 2013 06:12:01 -0000 Author: alc Date: Mon Apr 15 06:12:00 2013 New Revision: 249502 URL: http://svnweb.freebsd.org/changeset/base/249502 Log: Although we perform path compression to reduce the height of the trie and the number of interior nodes, we have previously created a level zero interior node at the root of every non-empty trie, even when that node is not strictly necessary, i.e., it has only one child. This change is the second (and final) step in eliminating those unnecessary level zero interior nodes. Specifically, it updates the deletion and insertion functions so that they do not require a level zero interior node at the root of the trie. For a "buildworld" workload, this change results in a 16.8% reduction in the number of interior nodes allocated and a similar reduction in the average execution time for lookup functions. For example, the average execution time for a call to vm_radix_lookup_ge() is reduced by 22.9%. Reviewed by: attilio, jeff (an earlier version) Sponsored by: EMC / Isilon Storage Division Modified: head/sys/vm/vm_radix.c Modified: head/sys/vm/vm_radix.c ============================================================================== --- head/sys/vm/vm_radix.c Mon Apr 15 05:50:09 2013 (r249501) +++ head/sys/vm/vm_radix.c Mon Apr 15 06:12:00 2013 (r249502) @@ -396,7 +396,8 @@ void vm_radix_insert(struct vm_radix *rtree, vm_page_t page) { vm_pindex_t index, newind; - struct vm_radix_node *parent, *rnode, *tmp; + void **parentp; + struct vm_radix_node *rnode, *tmp; vm_page_t m; int slot; uint16_t clev; @@ -409,34 +410,34 @@ vm_radix_insert(struct vm_radix *rtree, */ rnode = vm_radix_getroot(rtree); if (rnode == NULL) { - rnode = vm_radix_node_get(0, 1, 0); - vm_radix_setroot(rtree, rnode); - vm_radix_addpage(rnode, index, 0, page); + rtree->rt_root = (uintptr_t)page | VM_RADIX_ISLEAF; return; } - do { - slot = vm_radix_slot(index, rnode->rn_clev); - if (vm_radix_isleaf(rnode->rn_child[slot])) { - m = vm_radix_topage(rnode->rn_child[slot]); + parentp = (void **)&rtree->rt_root; + for (;;) { + if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); if (m->pindex == index) panic("%s: key %jx is already present", __func__, (uintmax_t)index); clev = vm_radix_keydiff(m->pindex, index); tmp = vm_radix_node_get(vm_radix_trimkey(index, clev - 1), 2, clev); - rnode->rn_child[slot] = tmp; + *parentp = tmp; vm_radix_addpage(tmp, index, clev, page); vm_radix_addpage(tmp, m->pindex, clev, m); return; - } + } else if (vm_radix_keybarr(rnode, index)) + break; + slot = vm_radix_slot(index, rnode->rn_clev); if (rnode->rn_child[slot] == NULL) { rnode->rn_count++; vm_radix_addpage(rnode, index, rnode->rn_clev, page); return; } - parent = rnode; + parentp = &rnode->rn_child[slot]; rnode = rnode->rn_child[slot]; - } while (!vm_radix_keybarr(rnode, index)); + } /* * A new node is needed because the right insertion level is reached. @@ -447,7 +448,7 @@ vm_radix_insert(struct vm_radix *rtree, clev = vm_radix_keydiff(newind, index); tmp = vm_radix_node_get(vm_radix_trimkey(index, clev - 1), 2, clev); - parent->rn_child[slot] = tmp; + *parentp = tmp; vm_radix_addpage(tmp, index, clev, page); slot = vm_radix_slot(newind, clev); tmp->rn_child[slot] = rnode; @@ -694,8 +695,15 @@ vm_radix_remove(struct vm_radix *rtree, vm_page_t m; int i, slot; - parent = NULL; rnode = vm_radix_getroot(rtree); + if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); + if (m->pindex != index) + panic("%s: invalid key found", __func__); + vm_radix_setroot(rtree, NULL); + return; + } + parent = NULL; for (;;) { if (rnode == NULL) panic("vm_radix_remove: impossible to locate the key"); @@ -708,22 +716,19 @@ vm_radix_remove(struct vm_radix *rtree, rnode->rn_count--; if (rnode->rn_count > 1) break; - if (parent == NULL) { - if (rnode->rn_count == 0) { - vm_radix_node_put(rnode); - vm_radix_setroot(rtree, NULL); - } - break; - } for (i = 0; i < VM_RADIX_COUNT; i++) if (rnode->rn_child[i] != NULL) break; KASSERT(i != VM_RADIX_COUNT, ("%s: invalid node configuration", __func__)); - slot = vm_radix_slot(index, parent->rn_clev); - KASSERT(parent->rn_child[slot] == rnode, - ("%s: invalid child value", __func__)); - parent->rn_child[slot] = rnode->rn_child[i]; + if (parent == NULL) + vm_radix_setroot(rtree, rnode->rn_child[i]); + else { + slot = vm_radix_slot(index, parent->rn_clev); + KASSERT(parent->rn_child[slot] == rnode, + ("%s: invalid child value", __func__)); + parent->rn_child[slot] = rnode->rn_child[i]; + } rnode->rn_count--; rnode->rn_child[i] = NULL; vm_radix_node_put(rnode); @@ -748,7 +753,8 @@ vm_radix_reclaim_allnodes(struct vm_radi if (root == NULL) return; vm_radix_setroot(rtree, NULL); - vm_radix_reclaim_allnodes_int(root); + if (!vm_radix_isleaf(root)) + vm_radix_reclaim_allnodes_int(root); } #ifdef DDB