X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;ds=sidebyside;f=rcuja%2Frcuja.c;h=75113954ccdb9dee09193a41321002b623bd6cfd;hb=582a6ade5032f98b788f1d8ddae97d44acf46715;hp=ff018e682cf4b6265bcfb35e8b1898bcc276acd2;hpb=f07b240f5d4b2c086abedcdd4f6516753fd934e4;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index ff018e6..7511395 100644 --- 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;