[src/yamt-pagecache]: src make tag-variants of radix tree functions take and ...

[yamt <yamt%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/14a367ac44b5
branches:  yamt-pagecache
changeset: 770883:14a367ac44b5
user:      yamt <yamt%NetBSD.org@localhost>
date:      Wed Aug 01 21:09:27 2012 +0000

description:
make tag-variants of radix tree functions take and return a mask of tags
rather than tag ids so that they can deal with multiple tags at once.

diffstat:

 common/lib/libc/gen/radixtree.c |  328 +++++++++++++++++++++------------------
 sys/sys/radixtree.h             |   17 +-
 2 files changed, 189 insertions(+), 156 deletions(-)

diffs (truncated from 647 to 300 lines):

diff -r bddc832ff86f -r 14a367ac44b5 common/lib/libc/gen/radixtree.c
--- a/common/lib/libc/gen/radixtree.c   Wed Jun 13 14:18:49 2012 +0000
+++ b/common/lib/libc/gen/radixtree.c   Wed Aug 01 21:09:27 2012 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: radixtree.c,v 1.17.2.3 2012/06/13 14:18:49 yamt Exp $  */
+/*     $NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $  */
 
 /*-
  * Copyright (c)2011,2012 YAMAMOTO Takashi,
@@ -75,12 +75,17 @@
  * leaf nodes with the given tag.  To reduce amount of nodes to visit for
  * these functions, this implementation keeps tagging information in internal
  * intermediate nodes and quickly skips uninterested parts of a tree.
+ *
+ * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are
+ * identified by an zero-origin numbers, tagid.  For the current implementation,
+ * RADIX_TREE_TAG_ID_MAX is 2.  A set of tags is described as a bitmask tagmask,
+ * which is a bitwise OR of (1 << tagid).
  */
 
 #include <sys/cdefs.h>
 
 #if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17.2.3 2012/06/13 14:18:49 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
@@ -90,7 +95,7 @@
 #include <lib/libsa/stand.h>
 #endif /* defined(_STANDALONE) */
 #else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.17.2.3 2012/06/13 14:18:49 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.17.2.4 2012/08/01 21:09:27 yamt Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
@@ -149,15 +154,6 @@
        return (entry_tagmask(p) & tagmask) != 0;
 }
 
-static inline unsigned int
-tagid_to_mask(radix_tree_tagid_t id)
-{
-
-       KASSERT(id >= 0);
-       KASSERT(id < RADIX_TREE_TAG_ID_MAX);
-       return 1U << id;
-}
-
 /*
  * radix_tree_node: an intermediate node
  *
@@ -274,13 +270,15 @@
  *
  * Return true if the tree has any nodes with the given tag.  Otherwise
  * return false.
+ *
+ * It's illegal to call this function with tagmask 0.
  */
 
 bool
-radix_tree_empty_tagged_tree_p(struct radix_tree *t, radix_tree_tagid_t tagid)
+radix_tree_empty_tagged_tree_p(struct radix_tree *t, unsigned int tagmask)
 {
-       const unsigned int tagmask = tagid_to_mask(tagid);
 
+       KASSERT(tagmask != 0);
        return (entry_tagmask(t->t_root) & tagmask) == 0;
 }
 
@@ -873,16 +871,17 @@
  *
  * Same as radix_tree_gang_lookup_node except that this one only returns
  * nodes tagged with tagid.
+ *
+ * It's illegal to call this function with tagmask 0.
  */
 
 unsigned int
 radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx,
-    void **results, unsigned int maxresults, bool dense,
-    radix_tree_tagid_t tagid)
+    void **results, unsigned int maxresults, bool dense, unsigned int tagmask)
 {
        struct radix_tree_path path;
-       const unsigned int tagmask = tagid_to_mask(tagid);
 
+       KASSERT(tagmask != 0);
        gang_lookup_init(t, idx, &path, tagmask);
        return gang_lookup_scan(t, &path, results, maxresults, tagmask, false,
            dense);
@@ -897,12 +896,11 @@
 
 unsigned int
 radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx,
-    void **results, unsigned int maxresults, bool dense,
-    radix_tree_tagid_t tagid)
+    void **results, unsigned int maxresults, bool dense, unsigned int tagmask)
 {
        struct radix_tree_path path;
-       const unsigned int tagmask = tagid_to_mask(tagid);
 
+       KASSERT(tagmask != 0);
        gang_lookup_init(t, idx, &path, tagmask);
        return gang_lookup_scan(t, &path, results, maxresults, tagmask, true,
            dense);
@@ -911,21 +909,19 @@
 /*
  * radix_tree_get_tag:
  *
- * Return if the tag is set for the node at the given index.  (true if set)
+ * Return the tagmask for the node at the given index.
  *
  * It's illegal to call this function for a node which has not been inserted.
  */
 
-bool
-radix_tree_get_tag(struct radix_tree *t, uint64_t idx,
-    radix_tree_tagid_t tagid)
+unsigned int
+radix_tree_get_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
 {
        /*
         * 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;
 
        vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask);
@@ -933,14 +929,13 @@
                return false;
        }
        KASSERT(*vpp != NULL);
-       return (entry_tagmask(*vpp) & tagmask) != 0;
+       return (entry_tagmask(*vpp) & tagmask);
 #else
-       const unsigned int tagmask = tagid_to_mask(tagid);
        void **vpp;
 
        vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
        KASSERT(vpp != NULL);
-       return (entry_tagmask(*vpp) & tagmask) != 0;
+       return (entry_tagmask(*vpp) & tagmask);
 #endif
 }
 
@@ -950,17 +945,17 @@
  * Set the tag for the node at the given index.
  *
  * It's illegal to call this function for a node which has not been inserted.
+ * It's illegal to call this function with tagmask 0.
  */
 
 void
-radix_tree_set_tag(struct radix_tree *t, uint64_t idx,
-    radix_tree_tagid_t tagid)
+radix_tree_set_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
 {
        struct radix_tree_path path;
-       const unsigned int tagmask = tagid_to_mask(tagid);
        void **vpp;
        int i;
 
+       KASSERT(tagmask != 0);
        vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
        KASSERT(vpp != NULL);
        KASSERT(*vpp != NULL);
@@ -985,17 +980,17 @@
  * Clear the tag for the node at the given index.
  *
  * It's illegal to call this function for a node which has not been inserted.
+ * It's illegal to call this function with tagmask 0.
  */
 
 void
-radix_tree_clear_tag(struct radix_tree *t, uint64_t idx,
-    radix_tree_tagid_t tagid)
+radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
 {
        struct radix_tree_path path;
-       const unsigned int tagmask = tagid_to_mask(tagid);
        void **vpp;
        int i;
 
+       KASSERT(tagmask != 0);
        vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
        KASSERT(vpp != NULL);
        KASSERT(*vpp != NULL);
@@ -1106,29 +1101,29 @@
            == 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)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
            == 0);
-       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
            == 0);
-       assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 1)
            == 0);
-       assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 1)
            == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           false, 0) == 0);
+           false, 1) == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           true, 0) == 0);
+           true, 1) == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
-           false, 0) == 0);
+           false, 1) == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
-           true, 0) == 0);
+           true, 1) == 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));
+       assert(radix_tree_empty_tagged_tree_p(t, 2));
        assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 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));
+       assert(radix_tree_empty_tagged_tree_p(t, 2));
        assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0);
        assert(radix_tree_lookup_node(t, 1000) == NULL);
        memset(results, 0, sizeof(results));
@@ -1153,14 +1148,14 @@
        assert(results[0] == (void *)0xdeadbea0);
        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)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
            == 0);
-       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
            == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           false, 0) == 0);
+           false, 1) == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           true, 0) == 0);
+           true, 1) == 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));
@@ -1188,23 +1183,25 @@
        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, false, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
            == 0);
-       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 0)
+       assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
            == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           false, 0) == 0);
+           false, 1) == 0);
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
-           true, 0) == 0);
-       assert(!radix_tree_get_tag(t, 1000, 0));
+           true, 1) == 0);
        assert(!radix_tree_get_tag(t, 1000, 1));
-       assert(radix_tree_empty_tagged_tree_p(t, 0));
+       assert(!radix_tree_get_tag(t, 1000, 2));
+       assert(radix_tree_get_tag(t, 1000, 2 | 1) == 0);
        assert(radix_tree_empty_tagged_tree_p(t, 1));
-       radix_tree_set_tag(t, 1000, 1);
-       assert(!radix_tree_get_tag(t, 1000, 0));
-       assert(radix_tree_get_tag(t, 1000, 1));
-       assert(radix_tree_empty_tagged_tree_p(t, 0));
-       assert(!radix_tree_empty_tagged_tree_p(t, 1));
+       assert(radix_tree_empty_tagged_tree_p(t, 2));
+       radix_tree_set_tag(t, 1000, 2);
+       assert(!radix_tree_get_tag(t, 1000, 1));
+       assert(radix_tree_get_tag(t, 1000, 2));
+       assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2);
+       assert(radix_tree_empty_tagged_tree_p(t, 1));
+       assert(!radix_tree_empty_tagged_tree_p(t, 2));
        radix_tree_dump(t);
        assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
        assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0);
@@ -1219,26 +1216,27 @@
        assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) ==
            (void *)0xdea0);
        radix_tree_dump(t);
-       assert(!radix_tree_get_tag(t, 0, 1));
-       assert(radix_tree_get_tag(t, 1000, 1));
+       assert(!radix_tree_get_tag(t, 0, 2));
+       assert(radix_tree_get_tag(t, 1000, 2));
        assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
-       radix_tree_set_tag(t, 0, 1);;
-       radix_tree_set_tag(t, UINT64_C(10000000000), 1);
+       radix_tree_set_tag(t, 0, 2);;
+       radix_tree_set_tag(t, UINT64_C(10000000000), 2);