svn commit: r226952 - user/attilio/vmcontention/sys/vm
Jeff Roberson
jeff at FreeBSD.org
Sun Oct 30 22:57:43 UTC 2011
Author: jeff
Date: Sun Oct 30 22:57:42 2011
New Revision: 226952
URL: http://svn.freebsd.org/changeset/base/226952
Log:
- Extract part of vm_radix_lookupn() into a function that just finds the
first leaf page in a specified range. This permits us to make many
search & operate functions without much code duplication.
- Make a generic iterator for radix items.
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 Sun Oct 30 22:20:17 2011 (r226951)
+++ user/attilio/vmcontention/sys/vm/vm_radix.c Sun Oct 30 22:57:42 2011 (r226952)
@@ -364,30 +364,25 @@ vm_radix_color(struct vm_radix *rtree, v
}
/*
- * 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 restart the scan. This optimizes forward scans in the tree.
+ * Find the first leaf with a valid node between *startp and end. Return
+ * the index of the first valid item in the leaf in *startp.
*/
-int
-vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
- vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
+static struct vm_radix_node *
+vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end)
{
struct vm_radix_node *rnode;
+ vm_pindex_t start;
vm_pindex_t inc;
int slot;
int level;
- void *val;
- int outidx;
- CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
- rtree, (void *)start, (void *)end);
- outidx = 0;
+ start = *startp;
restart:
level = vm_radix_height(rtree, &rnode);
- if (rnode == NULL || start > VM_RADIX_MAX(level))
- goto out;
- if (end && start >= end)
+ if (start > VM_RADIX_MAX(level) || (end && start >= end)) {
+ rnode = NULL;
goto out;
+ }
/*
* Search the tree from the top for any leaf node holding an index
* between start and end.
@@ -395,7 +390,7 @@ restart:
for (level--; level; level--) {
slot = vm_radix_slot(start, level);
CTR5(KTR_VM,
- "lookupn: tree %p, index %p, level %d, slot %d, child %p",
+ "leaf: tree %p, index %p, level %d, slot %d, child %p",
rtree, (void *)start, level, slot, rnode->rn_child[slot]);
if (rnode->rn_child[slot] != NULL) {
rnode = rnode->rn_child[slot];
@@ -412,12 +407,14 @@ restart:
start += inc;
slot++;
CTR5(KTR_VM,
- "lookupn: start %p end %p inc %d mask 0x%lX slot %d",
+ "leaf: 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; slot++, start += inc) {
- if (end != 0 && start >= end)
+ if (end != 0 && start >= end) {
+ rnode = NULL;
goto out;
+ }
if (rnode->rn_child[slot]) {
rnode = rnode->rn_child[slot];
break;
@@ -426,33 +423,81 @@ restart:
if (slot == VM_RADIX_COUNT)
goto restart;
}
- slot = vm_radix_slot(start, 0);
- for (; slot < VM_RADIX_COUNT; slot++, start++) {
+
+out:
+ *startp = start;
+ return (rnode);
+}
+
+
+
+/*
+ * 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 restart the scan. This optimizes forward scans in the tree.
+ */
+int
+vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
+ vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next)
+{
+ struct vm_radix_node *rnode;
+ void *val;
+ int slot;
+ int outidx;
+
+ CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p",
+ rtree, (void *)start, (void *)end);
+ if (rtree->rt_root == 0)
+ return (0);
+ outidx = 0;
+ while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
+ slot = vm_radix_slot(start, 0);
+ for (; slot < VM_RADIX_COUNT; slot++, start++) {
+ if (end != 0 && start >= end)
+ goto out;
+ val = vm_radix_match(rnode->rn_child[slot], color);
+ if (val == NULL)
+ continue;
+ CTR4(KTR_VM,
+ "lookupn: tree %p index %p slot %d found child %p",
+ rtree, (void *)start, slot, val);
+ out[outidx] = val;
+ if (++outidx == cnt)
+ goto out;
+ }
if (end != 0 && start >= end)
- goto out;
- val = vm_radix_match(rnode->rn_child[slot], color);
- if (val == NULL)
- continue;
- CTR4(KTR_VM,
- "lookupn: tree %p index %p slot %d found child %p",
- rtree, (void *)start, slot, val);
- out[outidx++] = val;
- if (outidx == cnt)
- goto out;
+ break;
}
- /*
- * Go fetch the next page to fill the requested number of pages
- * otherwise the caller will simply call us again to fulfill the
- * same request after the structures are pushed out of cache.
- */
- if ((end == 0 || start < end))
- goto restart;
out:
*next = start;
-
return (outidx);
}
+void
+vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end,
+ int color, void (*iter)(void *))
+{
+ struct vm_radix_node *rnode;
+ void *val;
+ int slot;
+
+ if (rtree->rt_root == 0)
+ return;
+ while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) {
+ slot = vm_radix_slot(start, 0);
+ for (; slot < VM_RADIX_COUNT; slot++, start++) {
+ if (end != 0 && start >= end)
+ return;
+ val = vm_radix_match(rnode->rn_child[slot], color);
+ if (val)
+ iter(val);
+ }
+ if (end != 0 && start >= end)
+ return;
+ }
+}
+
+
/*
* Look up any entry at a position less than or equal to index.
*/
Modified: user/attilio/vmcontention/sys/vm/vm_radix.h
==============================================================================
--- user/attilio/vmcontention/sys/vm/vm_radix.h Sun Oct 30 22:20:17 2011 (r226951)
+++ user/attilio/vmcontention/sys/vm/vm_radix.h Sun Oct 30 22:57:42 2011 (r226952)
@@ -74,12 +74,14 @@ void vm_radix_shrink(struct vm_radix *)
/*
* Functions which work on specified colors. (object, vm_page_queue_free locks)
*/
-void *vm_radix_color(struct vm_radix *, vm_pindex_t, int color);
-void *vm_radix_lookup(struct vm_radix *, vm_pindex_t, int color);
-int vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start,
- vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next);
-void *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t, int color);
-void *vm_radix_remove(struct vm_radix *, vm_pindex_t, int color);
+void *vm_radix_color(struct vm_radix *, vm_pindex_t, int);
+void *vm_radix_lookup(struct vm_radix *, vm_pindex_t, int);
+int vm_radix_lookupn(struct vm_radix *, vm_pindex_t, vm_pindex_t, int,
+ void **, int, vm_pindex_t *);
+void *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t, int);
+void *vm_radix_remove(struct vm_radix *, vm_pindex_t, int);
+void vm_radix_foreach(struct vm_radix *, vm_pindex_t, vm_pindex_t, int,
+ void (*)(void *));
/*
* Look up any entry at a position greater or equal to index.
More information about the svn-src-user
mailing list