Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/yamt-pagecache]: src radix_tree_gang_lookup_node and its variants: add a...
details: https://anonhg.NetBSD.org/src/rev/cb2cd234c3b5
branches: yamt-pagecache
changeset: 770838:cb2cd234c3b5
user: yamt <yamt%NetBSD.org@localhost>
date: Fri Nov 25 13:58:11 2011 +0000
description:
radix_tree_gang_lookup_node and its variants: add a option to stop on a hole.
diffstat:
common/lib/libc/gen/radixtree.c | 225 ++++++++++++++++++++++++++++++---------
sys/sys/radixtree.h | 10 +-
2 files changed, 174 insertions(+), 61 deletions(-)
diffs (truncated from 472 to 300 lines):
diff -r 1f9774902df3 -r cb2cd234c3b5 common/lib/libc/gen/radixtree.c
--- a/common/lib/libc/gen/radixtree.c Thu Nov 24 15:26:56 2011 +0000
+++ b/common/lib/libc/gen/radixtree.c Fri Nov 25 13:58:11 2011 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $ */
+/* $NetBSD: radixtree.c,v 1.17.2.1 2011/11/25 13:58:11 yamt Exp $ */
/*-
* Copyright (c)2011 YAMAMOTO Takashi,
@@ -68,7 +68,7 @@
#include <sys/cdefs.h>
#if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17.2.1 2011/11/25 13:58:11 yamt Exp $");
#include <sys/param.h>
#include <sys/errno.h>
#include <sys/pool.h>
@@ -78,7 +78,7 @@
#include <lib/libsa/stand.h>
#endif /* defined(_STANDALONE) */
#else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.17.2.1 2011/11/25 13:58:11 yamt Exp $");
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
@@ -511,7 +511,7 @@
void **vpp;
KASSERT(p != NULL);
- KASSERT(entry_compose(p, 0) == p);
+ KASSERT(entry_tagmask(entry_compose(p, 0)) == 0);
vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0);
if (vpp == NULL) {
return ENOMEM;
@@ -538,7 +538,7 @@
void *oldp;
KASSERT(p != NULL);
- KASSERT(entry_compose(p, 0) == p);
+ KASSERT(entry_tagmask(entry_compose(p, 0)) == 0);
vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
KASSERT(vpp != NULL);
oldp = *vpp;
@@ -665,8 +665,8 @@
static inline unsigned int
__attribute__((__always_inline__))
gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path,
- void **results, unsigned int maxresults, const unsigned int tagmask,
- bool reverse)
+ void **results, const unsigned int maxresults, const unsigned int tagmask,
+ const bool reverse, const bool dense)
{
/*
@@ -696,7 +696,10 @@
!entry_match_p(*path_pptr(t, path, lastidx), tagmask));
nfound = 0;
if (lastidx == RADIX_TREE_INVALID_HEIGHT) {
- if (reverse) {
+ /*
+ * requested idx is beyond the right-most node.
+ */
+ if (reverse && !dense) {
lastidx = 0;
vpp = path_pptr(t, path, lastidx);
goto descend;
@@ -718,6 +721,8 @@
if (nfound == maxresults) {
return nfound;
}
+ } else if (dense) {
+ return nfound;
}
scan_siblings:
/*
@@ -784,24 +789,34 @@
* returns the number of nodes found, up to maxresults.
* returning less than maxresults means there are no more nodes.
*
+ * if dense == true, this function stops scanning when it founds a hole of
+ * indexes. ie. an index for which radix_tree_lookup_node would returns NULL.
+ * if dense == false, this function skips holes and continue scanning until
+ * maxresults nodes are found or it reaches the limit of the index range.
+ *
* the result of this function is semantically equivalent to what could be
* obtained by repeated calls of radix_tree_lookup_node with increasing index.
- * but this function is much faster when node indexes are distributed sparsely.
+ * but this function is expected to be computationally cheaper when looking up
+ * multiple nodes at once. especially, it's expected to be much cheaper when
+ * node indexes are distributed sparsely.
*
- * note that this function doesn't return exact values of node indexes of
- * found nodes. if they are important for a caller, it's the caller's
- * responsibility to check them, typically by examinining the returned nodes
- * using some caller-specific knowledge about them.
+ * note that this function doesn't return index values of found nodes.
+ * thus, in the case of dense == false, if index values are important for
+ * a caller, it's the caller's responsibility to check them, typically
+ * by examinining the returned nodes using some caller-specific knowledge
+ * about them.
+ * in the case of dense == true, a node returned via results[N] is always for
+ * the index (idx + N).
*/
unsigned int
radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx,
- void **results, unsigned int maxresults)
+ void **results, unsigned int maxresults, bool dense)
{
struct radix_tree_path path;
gang_lookup_init(t, idx, &path, 0);
- return gang_lookup_scan(t, &path, results, maxresults, 0, false);
+ return gang_lookup_scan(t, &path, results, maxresults, 0, false, dense);
}
/*
@@ -813,12 +828,12 @@
unsigned int
radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx,
- void **results, unsigned int maxresults)
+ void **results, unsigned int maxresults, bool dense)
{
struct radix_tree_path path;
gang_lookup_init(t, idx, &path, 0);
- return gang_lookup_scan(t, &path, results, maxresults, 0, true);
+ return gang_lookup_scan(t, &path, results, maxresults, 0, true, dense);
}
/*
@@ -830,13 +845,15 @@
unsigned int
radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx,
- void **results, unsigned int maxresults, radix_tree_tagid_t tagid)
+ void **results, unsigned int maxresults, bool dense,
+ radix_tree_tagid_t tagid)
{
struct radix_tree_path path;
const unsigned int tagmask = tagid_to_mask(tagid);
gang_lookup_init(t, idx, &path, tagmask);
- return gang_lookup_scan(t, &path, results, maxresults, tagmask, false);
+ return gang_lookup_scan(t, &path, results, maxresults, tagmask, false,
+ dense);
}
/*
@@ -848,13 +865,15 @@
unsigned int
radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx,
- void **results, unsigned int maxresults, radix_tree_tagid_t tagid)
+ void **results, unsigned int maxresults, bool dense,
+ radix_tree_tagid_t tagid)
{
struct radix_tree_path path;
const unsigned int tagmask = tagid_to_mask(tagid);
gang_lookup_init(t, idx, &path, tagmask);
- return gang_lookup_scan(t, &path, results, maxresults, tagmask, true);
+ return gang_lookup_scan(t, &path, results, maxresults, tagmask, true,
+ dense);
}
/*
@@ -868,6 +887,10 @@
radix_tree_get_tag(struct radix_tree *t, uint64_t idx,
radix_tree_tagid_t tagid)
{
+ /*
+ * the following two implementations should behave same.
+ * the former one was chosen because it seems faster.
+ */
#if 1
const unsigned int tagmask = tagid_to_mask(tagid);
void **vpp;
@@ -1036,16 +1059,34 @@
radix_tree_dump(t);
assert(radix_tree_lookup_node(t, 0) == NULL);
assert(radix_tree_lookup_node(t, 1000) == NULL);
- assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 0);
- assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
- assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
- assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 0);
- assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) == 0);
- assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, 0) == 0);
- assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 0);
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0);
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0);
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) ==
+ 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) ==
+ 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
+ == 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 0)
== 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 0)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 0)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
+ false, 0) == 0);
+ assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
+ true, 0) == 0);
assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
- 0) == 0);
+ false, 0) == 0);
+ assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
+ true, 0) == 0);
assert(radix_tree_empty_tree_p(t));
assert(radix_tree_empty_tagged_tree_p(t, 0));
assert(radix_tree_empty_tagged_tree_p(t, 1));
@@ -1056,19 +1097,35 @@
assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0);
assert(radix_tree_lookup_node(t, 1000) == NULL);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1);
+ assert(results[0] == (void *)0xdeadbea0);
+ memset(results, 0, sizeof(results));
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1);
assert(results[0] == (void *)0xdeadbea0);
- assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0);
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) ==
+ 1);
assert(results[0] == (void *)0xdeadbea0);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) ==
+ 1);
+ assert(results[0] == (void *)0xdeadbea0);
+ memset(results, 0, sizeof(results));
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
+ == 1);
assert(results[0] == (void *)0xdeadbea0);
- assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 0)
== 0);
- assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
== 0);
+ assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
+ false, 0) == 0);
+ assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
+ true, 0) == 0);
assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0);
assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0);
assert(!radix_tree_empty_tree_p(t));
@@ -1076,19 +1133,34 @@
assert(radix_tree_lookup_node(t, 0) == NULL);
assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1);
+ assert(results[0] == (void *)0xdeadbea0);
+ assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0);
+ memset(results, 0, sizeof(results));
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 1);
assert(results[0] == (void *)0xdeadbea0);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 1);
assert(results[0] == (void *)0xdeadbea0);
- assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false)
+ == 0);
+ assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true)
+ == 0);
+ memset(results, 0, sizeof(results));
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
+ == 1);
memset(results, 0, sizeof(results));
- assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
+ assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
+ == 1);
assert(results[0] == (void *)0xdeadbea0);
- assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 0)
+ == 0);
+ assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
== 0);
- assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
Home |
Main Index |
Thread Index |
Old Index