[src/trunk]: src Merge radixtree changes from yamt-pagecache.

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

details:   https://anonhg.NetBSD.org/src/rev/e615f756f22b
branches:  trunk
changeset: 465865:e615f756f22b
user:      ad <ad%NetBSD.org@localhost>
date:      Thu Dec 05 18:32:25 2019 +0000

description:
Merge radixtree changes from yamt-pagecache.

diffstat:

 common/lib/libc/gen/radixtree.c |  691 ++++++++++++++++++++++++++-------------
 sys/sys/radixtree.h             |   21 +-
 2 files changed, 463 insertions(+), 249 deletions(-)

diffs (truncated from 1178 to 300 lines):

diff -r 8d49a02289e4 -r e615f756f22b common/lib/libc/gen/radixtree.c
--- a/common/lib/libc/gen/radixtree.c   Thu Dec 05 17:52:06 2019 +0000
+++ b/common/lib/libc/gen/radixtree.c   Thu Dec 05 18:32:25 2019 +0000
@@ -1,7 +1,7 @@
-/*     $NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $      */
+/*     $NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $        */
 
 /*-
- * Copyright (c)2011 YAMAMOTO Takashi,
+ * Copyright (c)2011,2012,2013 YAMAMOTO Takashi,
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -29,46 +29,90 @@
 /*
  * radixtree.c
  *
- * this is an implementation of radix tree, whose keys are uint64_t and leafs
+ * Overview:
+ *
+ * This is an implementation of radix tree, whose keys are uint64_t and leafs
  * are user provided pointers.
  *
- * leaf nodes are just void * and this implementation doesn't care about
- * what they actually point to.  however, this implementation has an assumption
- * about their alignment.  specifically, this implementation assumes that their
- * 2 LSBs are zero and uses them internally.
+ * Leaf nodes are just void * and this implementation doesn't care about
+ * what they actually point to.  However, this implementation has an assumption
+ * about their alignment.  Specifically, this implementation assumes that their
+ * 2 LSBs are always zero and uses them for internal accounting.
+ *
+ * Intermediate nodes and memory allocation:
  *
- * intermediate nodes are automatically allocated and freed internally and
- * basically users don't need to care about them.  only radix_tree_insert_node
- * function can allocate memory for intermediate nodes and thus can fail for
- * ENOMEM.
+ * Intermediate nodes are automatically allocated and freed internally and
+ * basically users don't need to care about them.  The allocation is done via
+ * pool_cache_get(9) for _KERNEL, malloc(3) for userland, and alloc() for
+ * _STANDALONE environment.  Only radix_tree_insert_node function can allocate
+ * memory for intermediate nodes and thus can fail for ENOMEM.
+ *
+ * Memory Efficiency:
+ *
+ * It's designed to work efficiently with dense index distribution.
+ * The memory consumption (number of necessary intermediate nodes) heavily
+ * depends on the index distribution.  Basically, more dense index distribution
+ * consumes less nodes per item.  Approximately,
+ *
+ *  - the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
+ *    it would look like the following.
  *
- * efficiency:
- * it's designed to work efficiently with dense index distribution.
- * the memory consumption (number of necessary intermediate nodes)
- * heavily depends on index distribution.  basically, more dense index
- * distribution consumes less nodes per item.
- * approximately,
- * the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
- * the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
+ *     root (t_height=1)
+ *      |
+ *      v
+ *      [ | | | ]   (intermediate node.  RADIX_TREE_PTR_PER_NODE=4 in this fig)
+ *       | | | |
+ *       v v v v
+ *       p p p p    (items)
+ *
+ *  - the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
+ *    it would look like the following if RADIX_TREE_MAX_HEIGHT=3.
  *
- * gang lookup:
- * this implementation provides a way to lookup many nodes quickly via
+ *     root (t_height=3)
+ *      |
+ *      v
+ *      [ | | | ]
+ *           |
+ *           v
+ *           [ | | | ]
+ *                |
+ *                v
+ *                [ | | | ]
+ *                   |
+ *                   v
+ *                   p
+ *
+ * The height of tree (t_height) is dynamic.  It's smaller if only small
+ * index values are used.  As an extreme case, if only index 0 is used,
+ * the corresponding value is directly stored in the root of the tree
+ * (struct radix_tree) without allocating any intermediate nodes.  In that
+ * case, t_height=0.
+ *
+ * Gang lookup:
+ *
+ * This implementation provides a way to scan many nodes quickly via
  * radix_tree_gang_lookup_node function and its varients.
  *
- * tags:
- * this implementation provides tagging functionality to allow quick
- * scanning of a subset of leaf nodes.  leaf nodes are untagged when
- * inserted into the tree and can be tagged by radix_tree_set_tag function.
- * radix_tree_gang_lookup_tagged_node function and its variants returns
- * only leaf nodes with the given tag.  to reduce amount of nodes to visit for
+ * Tags:
+ *
+ * This implementation provides tagging functionality, which allows quick
+ * scanning of a subset of leaf nodes.  Leaf nodes are untagged when inserted
+ * into the tree and can be tagged by radix_tree_set_tag function.
+ * radix_tree_gang_lookup_tagged_node function and its variants returns only
+ * 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 2011/11/02 13:49:43 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
@@ -78,7 +122,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.18 2019/12/05 18:32:25 ad Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
@@ -137,15 +181,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
  *
@@ -219,7 +254,7 @@
 /*
  * radix_tree_init_tree:
  *
- * initialize a tree.
+ * Initialize a tree.
  */
 
 void
@@ -231,9 +266,9 @@
 }
 
 /*
- * radix_tree_init_tree:
+ * radix_tree_fini_tree:
  *
- * clean up a tree.
+ * Finish using a tree.
  */
 
 void
@@ -244,6 +279,12 @@
        KASSERT(t->t_height == 0);
 }
 
+/*
+ * radix_tree_empty_tree_p:
+ *
+ * Return if the tree is empty.
+ */
+
 bool
 radix_tree_empty_tree_p(struct radix_tree *t)
 {
@@ -251,11 +292,20 @@
        return t->t_root == NULL;
 }
 
+/*
+ * radix_tree_empty_tree_p:
+ *
+ * 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;
 }
 
@@ -318,6 +368,9 @@
        struct radix_tree_node *n;
 
 #if defined(_KERNEL)
+       /*
+        * note that pool_cache_get can block.
+        */
        n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT);
 #else /* defined(_KERNEL) */
 #if defined(_STANDALONE)
@@ -492,17 +545,17 @@
 /*
  * radix_tree_insert_node:
  *
- * insert the node at idx.
- * it's illegal to insert NULL.
- * it's illegal to insert a non-aligned pointer.
+ * Insert the node at the given index.
+ *
+ * It's illegal to insert NULL.  It's illegal to insert a non-aligned pointer.
  *
- * this function returns ENOMEM if necessary memory allocation failed.
- * otherwise, this function returns 0.
+ * This function returns ENOMEM if necessary memory allocation failed.
+ * Otherwise, this function returns 0.
  *
- * note that inserting a node can involves memory allocation for intermediate
- * nodes.  if _KERNEL, it's done with no-sleep IPL_NONE memory allocation.
+ * Note that inserting a node can involves memory allocation for intermediate
+ * nodes.  If _KERNEL, it's done with no-sleep IPL_NONE memory allocation.
  *
- * for the newly inserted node, all tags are cleared.
+ * For the newly inserted node, all tags are cleared.
  */
 
 int
@@ -511,7 +564,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;
@@ -524,11 +577,12 @@
 /*
  * radix_tree_replace_node:
  *
- * replace a node at the given index with the given node.
- * return the old node.
- * it's illegal to try to replace a node which has not been inserted.
+ * Replace a node at the given index with the given node and return the
+ * replaced one.
  *
- * this function doesn't change tags.
+ * It's illegal to try to replace a node which has not been inserted.
+ *
+ * This function keeps tags intact.
  */
 
 void *
@@ -538,7 +592,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;
@@ -550,8 +604,9 @@
 /*
  * radix_tree_remove_node:
  *
- * remove the node at idx.
- * it's illegal to try to remove a node which has not been inserted.
+ * Remove the node at the given index.
+ *
+ * It's illegal to try to remove a node which has not been inserted.
  */
 
 void *
@@ -625,8 +680,8 @@
 /*
  * radix_tree_lookup_node:
  *
- * returns the node at idx.