svn commit: r249427 - head/sys/vm

[Alan Cox]

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;