Date: Sun, 23 Oct 2011 01:19:01 +0000 (UTC) From: Jeff Roberson <jeff@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r226646 - user/attilio/vmcontention/sys/vm Message-ID: <201110230119.p9N1J1kX003986@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: jeff Date: Sun Oct 23 01:19:01 2011 New Revision: 226646 URL: http://svn.freebsd.org/changeset/base/226646 Log: - Implement vm_radix_lookup_le(). - Fix vm_radix_lookupn() when max == -1 by making the end parameter inclusive. Modified: user/attilio/vmcontention/sys/vm/vm_radix.c user/attilio/vmcontention/sys/vm/vm_radix.h Modified: user/attilio/vmcontention/sys/vm/vm_radix.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_radix.c Sat Oct 22 23:34:37 2011 (r226645) +++ user/attilio/vmcontention/sys/vm/vm_radix.c Sun Oct 23 01:19:01 2011 (r226646) @@ -218,8 +218,8 @@ vm_radix_lookup(struct vm_radix *rtree, } /* - * Looks up as many as cnt values between start and end and stores them - * in the caller allocated array out. The next index can be used to + * Looks up as many as cnt values between start and end inclusive, and stores + * them in the caller allocated array out. The next index can be used to * restart the scan. This optimizes forward scans in the tree. */ int @@ -242,10 +242,8 @@ vm_radix_lookupn(struct vm_radix *rtree, max = VM_RADIX_MAX(rtree->rt_height); if (start > max) return 0; - if (end > max + 1) - end = max + 1; - if (end == 0) - end = -1; + if (end > max || end == 0) + end = max; restart: loops++; if (loops > 1000) @@ -281,7 +279,7 @@ restart: CTR5(KTR_VM, "lookupn: start %p end %p inc %d mask 0x%lX slot %d", (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot); - for (; slot < VM_RADIX_COUNT && start < end; + for (; slot < VM_RADIX_COUNT && start <= end; slot++, start += inc) { child = rnode->rn_child[slot]; if (child) @@ -300,11 +298,11 @@ restart: * * Detect start wrapping back to 0 and return in this case. */ - if (start < end && start != 0) + if (start <= end && start != 0) goto restart; goto out; } - for (; outidx < cnt && slot < VM_RADIX_COUNT && start < end; + for (; outidx < cnt && slot < VM_RADIX_COUNT && start <= end; slot++, start++) { val = rnode->rn_child[slot]; if (val == NULL) @@ -316,7 +314,7 @@ restart: * otherwise the caller will simply call us again to fulfill the * same request after the structures are pushed out of cache. */ - if (outidx < cnt && start < end) + if (outidx < cnt && start <= end) goto restart; out: @@ -326,32 +324,82 @@ out: } /* - * Look up any entry at a position greater or equal to index. + * Look up any entry at a position less than or equal to index. */ void * -vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) +vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) { + struct vm_radix_node *rnode; + struct vm_radix_node *child; vm_pindex_t max; - void *val; - int n; + vm_pindex_t inc; + int slot; + int level; + int loops = 0; + CTR2(KTR_VM, + "lookup_le: tree %p, index %p", rtree, (void *)index); + if (rtree->rt_root == NULL) + return (NULL); max = VM_RADIX_MAX(rtree->rt_height); - n = vm_radix_lookupn(rtree, index, max + 1, &val, 1, &max); - if (n) - return (val); + if (index > max || index == 0) + index = max; +restart: + loops++; + if (loops > 1000) + panic("vm_radix_looku_le: looping %d\n", loops); + /* + * Search the tree from the top for any leaf node holding an index + * lower than 'index'. + */ + level = rtree->rt_height - 1; + rnode = rtree->rt_root; + while (rnode) { + slot = vm_radix_slot(index, level); + CTR5(KTR_VM, + "lookup_le: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)index, level, slot, rnode->rn_child[slot]); + if (level == 0) + break; + /* + * If we don't have an exact match we must start our search + * from the next leaf and adjust our index appropriately. + */ + if ((child = rnode->rn_child[slot]) == NULL) { + /* + * Calculate how much to decrement our index by + * based on the tree level. We must set the + * lower bits to start from the end of the next + * leaf. + */ + inc = 1LL << (level * VM_RADIX_WIDTH); + index |= VM_RADIX_MAX(level); + index -= inc; + slot--; + CTR4(KTR_VM, + "lookup_le: start %p inc %ld mask 0x%lX slot %d", + (void *)index, inc, VM_RADIX_MAX(level), slot); + for (; slot >= 0; slot--, index -= inc) { + child = rnode->rn_child[slot]; + if (child) + break; + } + } + rnode = child; + level--; + } + if (rnode) { + for (; slot >= 0; slot--, index--) { + if (rnode->rn_child[slot]) + return (rnode->rn_child[slot]); + } + } + if (index != -1) + goto restart; return (NULL); } /* - * Look up any entry at a position less than or equal to index. - */ -void * -vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) -{ - return NULL; -} - -/* * Remove the specified index from the tree. If possible the height of the * tree is adjusted after deletion. The value stored at index is returned * panics if the key is not present. Modified: user/attilio/vmcontention/sys/vm/vm_radix.h ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_radix.h Sat Oct 22 23:34:37 2011 (r226645) +++ user/attilio/vmcontention/sys/vm/vm_radix.h Sun Oct 23 01:19:01 2011 (r226646) @@ -57,8 +57,21 @@ void *vm_radix_remove(struct vm_radix *, void *vm_radix_lookup(struct vm_radix *, vm_pindex_t); int vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end, void **out, int cnt, vm_pindex_t *next); -void *vm_radix_lookup_ge(struct vm_radix *, vm_pindex_t); void *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t); void vm_radix_shrink(struct vm_radix *); +/* + * Look up any entry at a position greater or equal to index. + */ +static inline void * +vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) +{ + vm_pindex_t unused; + void *val; + + if (vm_radix_lookupn(rtree, index, 0, &val, 1, &unused)) + return (val); + return (NULL); +} + #endif /* !_VM_RADIX_H_ */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201110230119.p9N1J1kX003986>