diff options
author | alc <alc@FreeBSD.org> | 2013-04-27 16:44:59 +0000 |
---|---|---|
committer | alc <alc@FreeBSD.org> | 2013-04-27 16:44:59 +0000 |
commit | 046db6cecd043a6833060897f100e549196cfceb (patch) | |
tree | c03e67f9c2aa1d0a3ad598af20d676727f599ed9 /sys/vm/vm_radix.c | |
parent | 0fe12ef2b741f04664ec83b3eeeb20c4d9f049f0 (diff) | |
download | FreeBSD-src-046db6cecd043a6833060897f100e549196cfceb.zip FreeBSD-src-046db6cecd043a6833060897f100e549196cfceb.tar.gz |
Avoid some lookup restarts in vm_radix_lookup_{ge,le}().
Sponsored by: EMC / Isilon Storage Division
Diffstat (limited to 'sys/vm/vm_radix.c')
-rw-r--r-- | sys/vm/vm_radix.c | 46 |
1 files changed, 24 insertions, 22 deletions
diff --git a/sys/vm/vm_radix.c b/sys/vm/vm_radix.c index 10ecff3..a9c565a 100644 --- a/sys/vm/vm_radix.c +++ b/sys/vm/vm_radix.c @@ -527,26 +527,26 @@ restart: maplevels[rnode->rn_clev] = TRUE; /* - * If the keys differ before the current bisection node - * the search key might rollback to the earliest - * available bisection node, or to the smaller value - * in the current domain (if the owner is bigger than the + * If the keys differ before the current bisection node, + * then the search key might rollback to the earliest + * available bisection node or to the smallest key + * in the current node (if the owner is bigger than the * search key). * The maplevels array records any node has been seen * at a given level. This aids the search for a valid * bisection node. */ if (vm_radix_keybarr(rnode, index)) { - difflev = vm_radix_keydiff(index, rnode->rn_owner); if (index > rnode->rn_owner) { + difflev = vm_radix_keydiff(index, + rnode->rn_owner); if (vm_radix_addlev(&index, maplevels, difflev) > 0) break; + rnode = vm_radix_getroot(rtree); + goto restart; } else - index = vm_radix_trimkey(rnode->rn_owner, - difflev); - rnode = vm_radix_getroot(rtree); - goto restart; + index = rnode->rn_owner; } slot = vm_radix_slot(index, rnode->rn_clev); child = rnode->rn_child[slot]; @@ -628,26 +628,28 @@ restart: maplevels[rnode->rn_clev] = TRUE; /* - * If the keys differ before the current bisection node - * the search key might rollback to the earliest - * available bisection node, or to the higher value - * in the current domain (if the owner is smaller than the + * If the keys differ before the current bisection node, + * then the search key might rollback to the earliest + * available bisection node or to the largest key + * in the current node (if the owner is smaller than the * search key). * The maplevels array records any node has been seen * at a given level. This aids the search for a valid * bisection node. */ if (vm_radix_keybarr(rnode, index)) { - difflev = vm_radix_keydiff(index, rnode->rn_owner); if (index > rnode->rn_owner) { - index = vm_radix_trimkey(rnode->rn_owner, - difflev); - index |= VM_RADIX_UNITLEVEL(difflev) - 1; - } else if (vm_radix_declev(&index, maplevels, - difflev) > 0) - break; - rnode = vm_radix_getroot(rtree); - goto restart; + index = rnode->rn_owner + VM_RADIX_COUNT * + VM_RADIX_UNITLEVEL(rnode->rn_clev) - 1; + } else { + difflev = vm_radix_keydiff(index, + rnode->rn_owner); + if (vm_radix_declev(&index, maplevels, + difflev) > 0) + break; + rnode = vm_radix_getroot(rtree); + goto restart; + } } slot = vm_radix_slot(index, rnode->rn_clev); child = rnode->rn_child[slot]; |