rcuja: extend tests, more fixes

[userspace-rcu.git] / rcuja / rcuja.c

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index ff018e682cf4b6265bcfb35e8b1898bcc276acd2..75113954ccdb9dee09193a41321002b623bd6cfd 100644 (file)
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -71,9 +71,10 @@ struct cds_ja_type {
 #define JA_PTR_MASK    (~JA_TYPE_MASK)
 
 #define JA_ENTRY_PER_NODE      256UL
-#define JA_BITS_PER_BYTE       3
+#define JA_LOG2_BITS_PER_BYTE  3U
+#define JA_BITS_PER_BYTE       (1U << JA_LOG2_BITS_PER_BYTE)
 
-#define JA_MAX_DEPTH   5       /* Maximum depth, including leafs */
+#define JA_MAX_DEPTH   9       /* Maximum depth, including leafs */
 
 /*
  * Entry for NULL node is at index 8 of the table. It is never encoded
@@ -411,7 +412,9 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_nth(const struct cds_ja_type *type,
 
        assert(type->type_class == RCU_JA_PIGEON);
        child_node_flag = &((struct cds_ja_inode_flag **) node->u.data)[n];
-       if (caa_unlikely(child_node_flag_ptr))
+       dbg_printf("ja_pigeon_node_get_nth child_node_flag_ptr %p\n",
+               child_node_flag);
+       if (caa_unlikely(child_node_flag_ptr) && *child_node_flag)
                *child_node_flag_ptr = child_node_flag;
        return rcu_dereference(*child_node_flag);
 }
@@ -601,7 +604,8 @@ int ja_node_recompact_add(struct cds_ja *ja,
        }
 
 retry:         /* for fallback */
-       dbg_printf("Recompact to type %d\n", new_type_index);
+       dbg_printf("Recompact from type %d to type %d\n",
+                       old_type_index, new_type_index);
        new_type = &ja_types[new_type_index];
        new_node = alloc_cds_ja_node(new_type);
        if (!new_node)
@@ -762,11 +766,15 @@ struct cds_hlist_head *cds_ja_lookup(struct cds_ja *ja, uint64_t key)
                return NULL;
 
        for (i = 1; i < tree_depth; i++) {
+               uint8_t iter_key;
+
+               iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
                node_flag = ja_node_get_nth(node_flag, NULL,
-                       (unsigned char) key);
+                       iter_key);
+               dbg_printf("cds_ja_lookup iter key lookup %u finds node_flag %p\n",
+                               (unsigned int) iter_key, node_flag);
                if (!ja_node_ptr(node_flag))
                        return NULL;
-               key >>= JA_BITS_PER_BYTE;
        }
 
        /* Last level lookup succeded. We got an actual match. */
@@ -791,7 +799,7 @@ int ja_attach_node(struct cds_ja *ja,
                struct cds_ja_inode_flag *node_flag,
                struct cds_ja_inode_flag *parent_node_flag,
                uint64_t key,
-               unsigned int depth,
+               unsigned int level,
                struct cds_ja_node *child_node)
 {
        struct cds_ja_shadow_node *shadow_node = NULL,
@@ -805,7 +813,8 @@ int ja_attach_node(struct cds_ja *ja,
        struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH];
        int nr_created_nodes = 0;
 
-       dbg_printf("Attach node at depth %u\n", depth);
+       dbg_printf("Attach node at level %u (node %p, node_flag %p)\n",
+               level, node, node_flag);
 
        assert(node);
        shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
@@ -837,12 +846,15 @@ int ja_attach_node(struct cds_ja *ja,
        }
        created_nodes[nr_created_nodes++] = iter_node_flag;
 
-       for (i = ja->tree_depth - 1; i >= (int) depth; i--) {
-               dbg_printf("branch creation level %d, key %" PRIu64 "\n",
-                               i, key >> (JA_BITS_PER_BYTE * (i - 2)));
+       for (i = ja->tree_depth; i > (int) level; i--) {
+               uint8_t iter_key;
+
+               iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - i)));
+               dbg_printf("branch creation level %d, key %u\n",
+                               i - 1, (unsigned int) iter_key);
                iter_dest_node_flag = NULL;
                ret = ja_node_set_nth(ja, &iter_dest_node_flag,
-                       key >> (JA_BITS_PER_BYTE * (i - 2)),
+                       iter_key,
                        iter_node_flag,
                        NULL);
                if (ret)
@@ -851,11 +863,14 @@ int ja_attach_node(struct cds_ja *ja,
                iter_node_flag = iter_dest_node_flag;
        }
 
-       if (depth > 1) {
+       if (level > 1) {
+               uint8_t iter_key;
+
+               iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - level)));
                /* We need to use set_nth on the previous level. */
                iter_dest_node_flag = node_flag;
                ret = ja_node_set_nth(ja, &iter_dest_node_flag,
-                       key >> (JA_BITS_PER_BYTE * (depth - 2)),
+                       iter_key,
                        iter_node_flag,
                        shadow_node);
                if (ret)
@@ -923,7 +938,6 @@ int cds_ja_add(struct cds_ja *ja, uint64_t key,
                struct cds_ja_node *new_node)
 {
        unsigned int tree_depth, i;
-       uint64_t iter_key;
        struct cds_ja_inode_flag **node_flag_ptr;       /* in parent */
        struct cds_ja_inode_flag *node_flag,
                *parent_node_flag,
@@ -937,7 +951,6 @@ int cds_ja_add(struct cds_ja *ja, uint64_t key,
 retry:
        dbg_printf("cds_ja_add attempt: key %" PRIu64 ", node %p\n",
                key, new_node);
-       iter_key = key;
        parent2_node_flag = NULL;
        parent_node_flag =
                (struct cds_ja_inode_flag *) &ja->root; /* Use root ptr address as key for mutex */
@@ -946,6 +959,10 @@ retry:
 
        /* Iterate on all internal levels */
        for (i = 1; i < tree_depth; i++) {
+               uint8_t iter_key;
+
+               dbg_printf("cds_ja_add iter node_flag_ptr %p node_flag %p\n",
+                               *node_flag_ptr, node_flag);
                if (!ja_node_ptr(node_flag)) {
                        ret = ja_attach_node(ja, node_flag_ptr,
                                        parent_node_flag, parent2_node_flag,
@@ -955,12 +972,14 @@ retry:
                        else
                                goto end;
                }
+               iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
                parent2_node_flag = parent_node_flag;
                parent_node_flag = node_flag;
                node_flag = ja_node_get_nth(node_flag,
                        &node_flag_ptr,
-                       (unsigned char) iter_key);
-               iter_key >>= JA_BITS_PER_BYTE;
+                       iter_key);
+               dbg_printf("cds_ja_add iter key lookup %u finds node_flag %p node_flag_ptr %p\n",
+                               (unsigned int) iter_key, node_flag, *node_flag_ptr);
        }
 
        /*
@@ -968,6 +987,8 @@ retry:
         * level, or chain it if key is already present.
         */
        if (!ja_node_ptr(node_flag)) {
+               dbg_printf("cds_ja_add last node_flag_ptr %p node_flag %p\n",
+                               *node_flag_ptr, node_flag);
                ret = ja_attach_node(ja, node_flag_ptr, parent_node_flag,
                                parent2_node_flag, key, i, new_node);
        } else {
@@ -1011,7 +1032,7 @@ struct cds_ja *_cds_ja_new(unsigned int key_bits,
 
        /* ja->root is NULL */
        /* tree_depth 0 is for pointer to root node */
-       ja->tree_depth = (key_bits >> JA_BITS_PER_BYTE) + 1;
+       ja->tree_depth = (key_bits >> JA_LOG2_BITS_PER_BYTE) + 1;
        assert(ja->tree_depth <= JA_MAX_DEPTH);
        ja->ht = rcuja_create_ht(flavor);
        if (!ja->ht)
@@ -1027,6 +1048,7 @@ struct cds_ja *_cds_ja_new(unsigned int key_bits,
                ret = -ENOMEM;
                goto ht_node_error;
        }
+       root_shadow_node->is_root = 1;
 
        return ja;