From owner-svn-src-head@FreeBSD.ORG Fri Apr 12 20:21:28 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 8FF4C6F2; Fri, 12 Apr 2013 20:21:28 +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 835E41BDD; Fri, 12 Apr 2013 20:21:28 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.6/8.14.6) with ESMTP id r3CKLSUi041180; Fri, 12 Apr 2013 20:21:28 GMT (envelope-from alc@svn.freebsd.org) Received: (from alc@localhost) by svn.freebsd.org (8.14.6/8.14.5/Submit) id r3CKLS0i041179; Fri, 12 Apr 2013 20:21:28 GMT (envelope-from alc@svn.freebsd.org) Message-Id: <201304122021.r3CKLS0i041179@svn.freebsd.org> From: Alan Cox Date: Fri, 12 Apr 2013 20:21:28 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r249427 - 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: Fri, 12 Apr 2013 20:21:28 -0000 Author: alc Date: Fri Apr 12 20:21:28 2013 New Revision: 249427 URL: http://svnweb.freebsd.org/changeset/base/249427 Log: Although we perform path compression to reduce the height of the trie and the number of interior nodes, we always create 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 first step in eliminating those unnecessary level zero interior nodes. Specifically, it updates all of the lookup functions so that they do not require a level zero interior node at the root. 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 Fri Apr 12 20:10:27 2013 (r249426) +++ head/sys/vm/vm_radix.c Fri Apr 12 20:21:28 2013 (r249427) @@ -270,11 +270,7 @@ vm_radix_addlev(vm_pindex_t *idx, boolea for (; levels[ilev] == FALSE || vm_radix_slot(*idx, ilev) == (VM_RADIX_COUNT - 1); ilev--) if (ilev == 0) - break; - KASSERT(ilev > 0 || levels[0], - ("%s: levels back-scanning problem", __func__)); - if (ilev == 0 && vm_radix_slot(*idx, ilev) == (VM_RADIX_COUNT - 1)) - return (1); + return (1); wrapidx = *idx; *idx = vm_radix_trimkey(*idx, ilev); *idx += VM_RADIX_UNITLEVEL(ilev); @@ -295,11 +291,7 @@ vm_radix_declev(vm_pindex_t *idx, boolea for (; levels[ilev] == FALSE || vm_radix_slot(*idx, ilev) == 0; ilev--) if (ilev == 0) - break; - KASSERT(ilev > 0 || levels[0], - ("%s: levels back-scanning problem", __func__)); - if (ilev == 0 && vm_radix_slot(*idx, ilev) == 0) - return (1); + return (1); wrapidx = *idx; *idx = vm_radix_trimkey(*idx, ilev); *idx |= VM_RADIX_UNITLEVEL(ilev) - 1; @@ -474,17 +466,16 @@ vm_radix_lookup(struct vm_radix *rtree, rnode = vm_radix_getroot(rtree); while (rnode != NULL) { - if (vm_radix_keybarr(rnode, index)) - return (NULL); - slot = vm_radix_slot(index, rnode->rn_clev); - rnode = rnode->rn_child[slot]; if (vm_radix_isleaf(rnode)) { m = vm_radix_topage(rnode); if (m->pindex == index) return (m); else - return (NULL); - } + break; + } else if (vm_radix_keybarr(rnode, index)) + break; + slot = vm_radix_slot(index, rnode->rn_clev); + rnode = rnode->rn_child[slot]; } return (NULL); } @@ -505,12 +496,21 @@ vm_radix_lookup_ge(struct vm_radix *rtre int loops = 0; #endif + rnode = vm_radix_getroot(rtree); + if (rnode == NULL) + return (NULL); + else if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); + if (m->pindex >= index) + return (m); + else + return (NULL); + } restart: KASSERT(++loops < 1000, ("%s: too many loops", __func__)); for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++) maplevels[difflev] = FALSE; - rnode = vm_radix_getroot(rtree); - while (rnode != NULL) { + for (;;) { maplevels[rnode->rn_clev] = TRUE; /* @@ -532,6 +532,7 @@ restart: } else index = vm_radix_trimkey(rnode->rn_owner, difflev); + rnode = vm_radix_getroot(rtree); goto restart; } slot = vm_radix_slot(index, rnode->rn_clev); @@ -572,6 +573,7 @@ restart: if (rnode->rn_clev == 0 || vm_radix_addlev(&index, maplevels, rnode->rn_clev - 1) > 0) break; + rnode = vm_radix_getroot(rtree); goto restart; descend: rnode = child; @@ -595,12 +597,21 @@ vm_radix_lookup_le(struct vm_radix *rtre int loops = 0; #endif + rnode = vm_radix_getroot(rtree); + if (rnode == NULL) + return (NULL); + else if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); + if (m->pindex <= index) + return (m); + else + return (NULL); + } restart: KASSERT(++loops < 1000, ("%s: too many loops", __func__)); for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++) maplevels[difflev] = FALSE; - rnode = vm_radix_getroot(rtree); - while (rnode != NULL) { + for (;;) { maplevels[rnode->rn_clev] = TRUE; /* @@ -622,6 +633,7 @@ restart: } else if (vm_radix_declev(&index, maplevels, difflev) > 0) break; + rnode = vm_radix_getroot(rtree); goto restart; } slot = vm_radix_slot(index, rnode->rn_clev); @@ -663,6 +675,7 @@ restart: if (rnode->rn_clev == 0 || vm_radix_declev(&index, maplevels, rnode->rn_clev - 1) > 0) break; + rnode = vm_radix_getroot(rtree); goto restart; descend: rnode = child;