From owner-svn-src-all@FreeBSD.ORG Sat May 11 18:01:42 2013 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id 30CCBBD5; Sat, 11 May 2013 18:01:42 +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 237B41EC; Sat, 11 May 2013 18:01:42 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.6/8.14.6) with ESMTP id r4BI1gAX000540; Sat, 11 May 2013 18:01:42 GMT (envelope-from alc@svn.freebsd.org) Received: (from alc@localhost) by svn.freebsd.org (8.14.6/8.14.5/Submit) id r4BI1gpu000539; Sat, 11 May 2013 18:01:42 GMT (envelope-from alc@svn.freebsd.org) Message-Id: <201305111801.r4BI1gpu000539@svn.freebsd.org> From: Alan Cox Date: Sat, 11 May 2013 18:01:41 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r250520 - 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-all@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 11 May 2013 18:01:42 -0000 Author: alc Date: Sat May 11 18:01:41 2013 New Revision: 250520 URL: http://svnweb.freebsd.org/changeset/base/250520 Log: To reduce the amount of arithmetic performed in the various radix tree functions, reverse the numbering scheme for the levels. The highest numbered level in the tree now appears near the root instead of the leaves. 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 Sat May 11 17:58:26 2013 (r250519) +++ head/sys/vm/vm_radix.c Sat May 11 18:01:41 2013 (r250520) @@ -91,7 +91,7 @@ __FBSDID("$FreeBSD$"); /* Returns one unit associated with specified level. */ #define VM_RADIX_UNITLEVEL(lev) \ - ((vm_pindex_t)1 << ((VM_RADIX_LIMIT - (lev)) * VM_RADIX_WIDTH)) + ((vm_pindex_t)1 << ((lev) * VM_RADIX_WIDTH)) struct vm_radix_node { vm_pindex_t rn_owner; /* Owner of record. */ @@ -150,8 +150,7 @@ static __inline int vm_radix_slot(vm_pindex_t index, uint16_t level) { - return ((index >> ((VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH)) & - VM_RADIX_MASK); + return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); } /* Trims the key after the specified level. */ @@ -161,9 +160,9 @@ vm_radix_trimkey(vm_pindex_t index, uint vm_pindex_t ret; ret = index; - if (level < VM_RADIX_LIMIT) { - ret >>= (VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH; - ret <<= (VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH; + if (level > 0) { + ret >>= level * VM_RADIX_WIDTH; + ret <<= level * VM_RADIX_WIDTH; } return (ret); } @@ -234,7 +233,7 @@ vm_radix_keydiff(vm_pindex_t index1, vm_ __func__, (uintmax_t)index1)); index1 ^= index2; - for (clev = 0;; clev++) + for (clev = VM_RADIX_LIMIT;; clev--) if (vm_radix_slot(index1, clev) != 0) return (clev); } @@ -247,8 +246,8 @@ static __inline boolean_t vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx) { - if (rnode->rn_clev > 0) { - idx = vm_radix_trimkey(idx, rnode->rn_clev - 1); + if (rnode->rn_clev < VM_RADIX_LIMIT) { + idx = vm_radix_trimkey(idx, rnode->rn_clev + 1); return (idx != rnode->rn_owner); } return (FALSE); @@ -384,7 +383,7 @@ vm_radix_insert(struct vm_radix *rtree, __func__, (uintmax_t)index); clev = vm_radix_keydiff(m->pindex, index); tmp = vm_radix_node_get(vm_radix_trimkey(index, - clev - 1), 2, clev); + clev + 1), 2, clev); *parentp = tmp; vm_radix_addpage(tmp, index, clev, page); vm_radix_addpage(tmp, m->pindex, clev, m); @@ -408,7 +407,7 @@ vm_radix_insert(struct vm_radix *rtree, */ newind = rnode->rn_owner; clev = vm_radix_keydiff(newind, index); - tmp = vm_radix_node_get(vm_radix_trimkey(index, clev - 1), 2, + tmp = vm_radix_node_get(vm_radix_trimkey(index, clev + 1), 2, clev); *parentp = tmp; vm_radix_addpage(tmp, index, clev, page); @@ -545,7 +544,7 @@ ascend: */ goto ascend; descend: - KASSERT(rnode->rn_clev < VM_RADIX_LIMIT, + KASSERT(rnode->rn_clev > 0, ("vm_radix_lookup_ge: pushing leaf's parent")); KASSERT(tos < VM_RADIX_LIMIT, ("vm_radix_lookup_ge: stack overflow")); @@ -658,7 +657,7 @@ ascend: */ goto ascend; descend: - KASSERT(rnode->rn_clev < VM_RADIX_LIMIT, + KASSERT(rnode->rn_clev > 0, ("vm_radix_lookup_le: pushing leaf's parent")); KASSERT(tos < VM_RADIX_LIMIT, ("vm_radix_lookup_le: stack overflow"));