X-Git-Url: http://git.lttng.org./?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=9f135b08ee5ebd5d8d70b32ae0277b0917957512;hb=4bea9b8d1f7e8bb0c0c2f6657236f5b4166e56d4;hp=e5145ea36a3b22dbec54cd4a45eeefe7334e343a;hpb=48cbe00177cd135553ee34d2f443c351b53b6d25;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index e5145ea..9f135b0 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -128,7 +128,7 @@ const struct cds_ja_type ja_types[] = { * Upon node removal below min_child, if child pool is filled * beyond capacity, we roll back to pigeon. */ - { .type_class = RCU_JA_PIGEON, .min_child = 89, .max_child = ja_type_7_max_child, .order = 10, }, + { .type_class = RCU_JA_PIGEON, .min_child = 83, .max_child = ja_type_7_max_child, .order = 10, }, { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, }, }; @@ -176,7 +176,7 @@ const struct cds_ja_type ja_types[] = { * Upon node removal below min_child, if child pool is filled * beyond capacity, we roll back to pigeon. */ - { .type_class = RCU_JA_PIGEON, .min_child = 101, .max_child = ja_type_7_max_child, .order = 11, }, + { .type_class = RCU_JA_PIGEON, .min_child = 95, .max_child = ja_type_7_max_child, .order = 11, }, { .type_class = RCU_JA_NULL, .min_child = 0, .max_child = ja_type_8_max_child, }, }; @@ -244,11 +244,6 @@ enum ja_recompact { JA_RECOMPACT_DEL, }; -static -unsigned long node_fallback_count_distribution[JA_ENTRY_PER_NODE]; -static -unsigned long nr_nodes_allocated, nr_nodes_freed; - static struct cds_ja_inode *_ja_node_mask_ptr(struct cds_ja_inode_flag *node) { @@ -291,7 +286,9 @@ struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) } } -struct cds_ja_inode *alloc_cds_ja_node(const struct cds_ja_type *ja_type) +static +struct cds_ja_inode *alloc_cds_ja_node(struct cds_ja *ja, + const struct cds_ja_type *ja_type) { size_t len = 1U << ja_type->order; void *p; @@ -302,15 +299,15 @@ struct cds_ja_inode *alloc_cds_ja_node(const struct cds_ja_type *ja_type) return NULL; } memset(p, 0, len); - uatomic_inc(&nr_nodes_allocated); + uatomic_inc(&ja->nr_nodes_allocated); return p; } -void free_cds_ja_node(struct cds_ja_inode *node) +void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node) { free(node); if (node) - uatomic_inc(&nr_nodes_freed); + uatomic_inc(&ja->nr_nodes_freed); } #define __JA_ALIGN_MASK(v, mask) (((v) + (mask)) & ~(mask)) @@ -1238,7 +1235,7 @@ retry: /* for fallback */ old_type_index, new_type_index); new_type = &ja_types[new_type_index]; if (new_type_index != NODE_INDEX_NULL) { - new_node = alloc_cds_ja_node(new_type); + new_node = alloc_cds_ja_node(ja, new_type); if (!new_node) return -ENOMEM; @@ -1285,7 +1282,7 @@ retry: /* for fallback */ dbg_printf("Recompact inherit lock from %p\n", shadow_node); new_shadow_node = rcuja_shadow_set(ja->ht, new_node_flag, shadow_node, ja, level); if (!new_shadow_node) { - free_cds_ja_node(new_node); + free_cds_ja_node(ja, new_node); return -ENOMEM; } if (fallback) @@ -1409,7 +1406,7 @@ skip_copy: dbg_printf("Using fallback for %u children, node type index: %u, mode %s\n", new_shadow_node->nr_child, old_type_index, mode == JA_RECOMPACT_ADD_NEXT ? "add_next" : (mode == JA_RECOMPACT_DEL ? "del" : "add_same")); - uatomic_inc(&node_fallback_count_distribution[new_shadow_node->nr_child]); + uatomic_inc(&ja->node_fallback_count_distribution[new_shadow_node->nr_child]); } /* Return pointer to new recompacted node through old_node_flag_ptr */ @@ -1674,6 +1671,27 @@ int ja_attach_node(struct cds_ja *ja, goto unlock_parent; } + /* + * Perform a lookup query to handle the case where + * old_node_flag_ptr is NULL. We cannot use it to check if the + * node has been populated between RCU lookup and mutex + * acquisition. + */ + if (!old_node_flag_ptr) { + uint8_t iter_key; + struct cds_ja_inode_flag *lookup_node_flag; + struct cds_ja_inode_flag **lookup_node_flag_ptr; + + iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - level))); + lookup_node_flag = ja_node_get_nth(attach_node_flag, + &lookup_node_flag_ptr, + iter_key); + if (lookup_node_flag) { + ret = -EEXIST; + goto unlock_parent; + } + } + if (attach_node_flag_ptr && ja_node_ptr(*attach_node_flag_ptr) != ja_node_ptr(attach_node_flag)) { /* @@ -1701,8 +1719,10 @@ int ja_attach_node(struct cds_ja *ja, iter_key, iter_node_flag, NULL, i); - if (ret) + if (ret) { + dbg_printf("branch creation error %d\n", ret); goto check_error; + } created_nodes[nr_created_nodes++] = iter_dest_node_flag; iter_node_flag = iter_dest_node_flag; } @@ -1726,8 +1746,10 @@ int ja_attach_node(struct cds_ja *ja, iter_key, iter_node_flag, shadow_node, level - 1); - if (ret) + if (ret) { + dbg_printf("branch publish error %d\n", ret); goto check_error; + } /* * Attach branch */ @@ -1793,8 +1815,10 @@ end: return ret; } -int cds_ja_add(struct cds_ja *ja, uint64_t key, - struct cds_ja_node *new_node) +static +int _cds_ja_add(struct cds_ja *ja, uint64_t key, + struct cds_ja_node *new_node, + struct cds_ja_node **unique_node_ret) { unsigned int tree_depth, i; struct cds_ja_inode_flag *attach_node_flag, @@ -1847,6 +1871,7 @@ retry: if (!ja_node_ptr(node_flag)) { dbg_printf("cds_ja_add NULL parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n", parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag); + attach_node_flag = parent_node_flag; attach_node_flag_ptr = parent_node_flag_ptr; parent_attach_node_flag = parent2_node_flag; @@ -1858,8 +1883,14 @@ retry: node_flag, key, i, new_node); } else { + if (unique_node_ret) { + *unique_node_ret = (struct cds_ja_node *) ja_node_ptr(node_flag); + return -EEXIST; + } + dbg_printf("cds_ja_add duplicate parent2_node_flag %p parent_node_flag %p node_flag_ptr %p node_flag %p\n", parent2_node_flag, parent_node_flag, node_flag_ptr, node_flag); + attach_node_flag = node_flag; attach_node_flag_ptr = node_flag_ptr; parent_attach_node_flag = parent_node_flag; @@ -1876,6 +1907,25 @@ retry: return ret; } +int cds_ja_add(struct cds_ja *ja, uint64_t key, + struct cds_ja_node *new_node) +{ + return _cds_ja_add(ja, key, new_node, NULL); +} + +struct cds_ja_node *cds_ja_add_unique(struct cds_ja *ja, uint64_t key, + struct cds_ja_node *new_node) +{ + int ret; + struct cds_ja_node *ret_node; + + ret = _cds_ja_add(ja, key, new_node, &ret_node); + if (ret == -EEXIST) + return ret_node; + else + return new_node; +} + /* * Note: there is no need to lookup the pointer address associated with * each node's nth item after taking the lock: it's already been done by @@ -2312,7 +2362,7 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, struct cds_hlist_node *pos, *tmp; uint8_t v; - ja_linear_node_get_ith_pos(type, node, j, &v, &iter); + ja_linear_node_get_ith_pos(type, pool, j, &v, &iter); if (!iter) continue; head.next = (struct cds_hlist_node *) iter; @@ -2351,19 +2401,45 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, } static -void print_debug_fallback_distribution(void) +void print_debug_fallback_distribution(struct cds_ja *ja) { int i; fprintf(stderr, "Fallback node distribution:\n"); for (i = 0; i < JA_ENTRY_PER_NODE; i++) { - if (!node_fallback_count_distribution[i]) + if (!ja->node_fallback_count_distribution[i]) continue; fprintf(stderr, " %3u: %4lu\n", - i, node_fallback_count_distribution[i]); + i, ja->node_fallback_count_distribution[i]); } } +static +void print_ja_debug_info(struct cds_ja *ja) +{ + double fallback_ratio; + unsigned long na, nf, nr_fallback; + + fallback_ratio = (double) uatomic_read(&ja->nr_fallback); + fallback_ratio /= (double) uatomic_read(&ja->nr_nodes_allocated); + nr_fallback = uatomic_read(&ja->nr_fallback); + if (nr_fallback) + fprintf(stderr, + "[warning] RCU Judy Array used %lu fallback node(s) (ratio: %g)\n", + uatomic_read(&ja->nr_fallback), + fallback_ratio); + + na = uatomic_read(&ja->nr_nodes_allocated); + nf = uatomic_read(&ja->nr_nodes_freed); + if (na != nf) { + fprintf(stderr, "[error] Judy array leaked %ld nodes. Allocated: %lu, freed: %lu.\n", + (long) na - nf, na, nf); + } + dbg_printf("Nodes allocated: %lu, Nodes freed: %lu.\n", na, nf); + if (nr_fallback) + print_debug_fallback_distribution(ja); +} + /* * There should be no more concurrent add to the judy array while it is * being destroyed (ensured by the caller). @@ -2382,16 +2458,12 @@ int cds_ja_destroy(struct cds_ja *ja, ret = rcuja_delete_ht(ja->ht); if (ret) return ret; + + /* Wait for in-flight call_rcu free to complete. */ + flavor->barrier(); + flavor->thread_online(); - if (uatomic_read(&ja->nr_fallback)) - fprintf(stderr, - "[warning] RCU Judy Array used %lu fallback node(s)\n", - uatomic_read(&ja->nr_fallback)); - fprintf(stderr, "Nodes allocated: %lu, Nodes freed: %lu. Fallback ratio: %g\n", - uatomic_read(&nr_nodes_allocated), - uatomic_read(&nr_nodes_freed), - (double) uatomic_read(&ja->nr_fallback) / (double) uatomic_read(&nr_nodes_allocated)); - print_debug_fallback_distribution(); + print_ja_debug_info(ja); free(ja); return 0; }