X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=9398a222bcd526fc4d3dcd1f86e851a02a17ced4;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=ef7619bd3fe6a6a8d62a28abe8917e08f75a964b;hpb=36305a3db8c572e25a6335c9384a5112bdfd8148;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index ef7619b..9398a22 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -3,7 +3,8 @@ * * Userspace RCU library - RCU Judy Array * - * Copyright 2012 - Mathieu Desnoyers + * Copyright (C) 2000 - 2002 Hewlett-Packard Company + * Copyright 2012-2013 - Mathieu Desnoyers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -25,13 +26,12 @@ #include #include #include +#include #include #include #include -#include #include #include -#include #include "rcuja-internal.h" @@ -290,14 +290,15 @@ struct cds_ja_inode *alloc_cds_ja_node(struct cds_ja *ja, return NULL; } memset(p, 0, len); - uatomic_inc(&ja->nr_nodes_allocated); + if (ja_debug_counters()) + uatomic_inc(&ja->nr_nodes_allocated); return p; } void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node) { free(node); - if (node) + if (ja_debug_counters() && node) uatomic_inc(&ja->nr_nodes_freed); } @@ -370,9 +371,9 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type uint8_t nr_child; uint8_t *values; struct cds_ja_inode_flag **pointers; - struct cds_ja_inode_flag *ptr; + struct cds_ja_inode_flag *ptr, *match_ptr = NULL; unsigned int i; - int match_idx = -1, match_v; + int match_v; assert(type->type_class == RCU_JA_LINEAR || type->type_class == RCU_JA_POOL); assert(dir == JA_LEFT || dir == JA_RIGHT); @@ -389,32 +390,34 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type assert(type->type_class != RCU_JA_LINEAR || nr_child >= type->min_child); values = &node->u.data[1]; + pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]); for (i = 0; i < nr_child; i++) { unsigned int v; v = CMM_LOAD_SHARED(values[i]); + ptr = CMM_LOAD_SHARED(pointers[i]); + if (!ptr) + continue; if (dir == JA_LEFT) { if ((int) v < n && (int) v > match_v) { match_v = v; - match_idx = i; + match_ptr = ptr; } } else { if ((int) v > n && (int) v < match_v) { match_v = v; - match_idx = i; + match_ptr = ptr; } } } - if (match_idx < 0) { + if (!match_ptr) { return NULL; } assert(match_v >= 0 && match_v < JA_ENTRY_PER_NODE); *result_key = (uint8_t) match_v; - pointers = (struct cds_ja_inode_flag **) align_ptr_size(&values[type->max_linear_child]); - ptr = rcu_dereference(pointers[match_idx]); - return ptr; + return rcu_dereference(match_ptr); } static @@ -582,7 +585,7 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type if (child_node_flag) { dbg_printf("ja_pigeon_node_get_left child_node_flag %p\n", child_node_flag); - *result_key = i; + *result_key = (uint8_t) i; return child_node_flag; } } @@ -594,7 +597,7 @@ struct cds_ja_inode_flag *ja_pigeon_node_get_direction(const struct cds_ja_type if (child_node_flag) { dbg_printf("ja_pigeon_node_get_right child_node_flag %p\n", child_node_flag); - *result_key = i; + *result_key = (uint8_t) i; return child_node_flag; } } @@ -1603,7 +1606,8 @@ 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(&ja->node_fallback_count_distribution[new_shadow_node->nr_child]); + if (ja_debug_counters()) + uatomic_inc(&ja->node_fallback_count_distribution[new_shadow_node->nr_child]); } /* Return pointer to new recompacted node through old_node_flag_ptr */ @@ -1669,7 +1673,8 @@ fallback_toosmall: } else { new_type_index++; dbg_printf("Add fallback to type %d\n", new_type_index); - uatomic_inc(&ja->nr_fallback); + if (ja_debug_counters()) + uatomic_inc(&ja->nr_fallback); fallback = 1; goto retry; } @@ -1781,7 +1786,7 @@ struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key) unsigned int tree_depth, i; struct cds_ja_inode_flag *node_flag; - if (caa_unlikely(key > ja->key_max)) + if (caa_unlikely(key > ja->key_max || key == UINT64_MAX)) return NULL; tree_depth = ja->tree_depth; node_flag = rcu_dereference(ja->root); @@ -1817,11 +1822,8 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, switch (mode) { case JA_LOOKUP_BE: - if (caa_unlikely(key > ja->key_max || key == 0)) - return NULL; - break; case JA_LOOKUP_AE: - if (caa_unlikely(key >= ja->key_max)) + if (caa_unlikely(key > ja->key_max || key == UINT64_MAX)) return NULL; break; default: @@ -1883,6 +1885,9 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1))); node_flag = ja_node_get_leftright(cur_node_depth[level - 1], iter_key, &cur_key[level - 1], dir); + dbg_printf("cds_ja_lookup_inequality find sibling from %u at %u finds node_flag %p\n", + (unsigned int) iter_key, (unsigned int) cur_key[level - 1], + node_flag); /* If found left/right sibling, find rightmost/leftmost child. */ if (ja_node_ptr(node_flag)) break; @@ -1918,6 +1923,9 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, } for (; level < tree_depth; level++) { node_flag = ja_node_get_minmax(node_flag, &cur_key[level - 1], dir); + dbg_printf("cds_ja_lookup_inequality find minmax at %u finds node_flag %p\n", + (unsigned int) cur_key[level - 1], + node_flag); if (!ja_node_ptr(node_flag)) break; } @@ -1937,12 +1945,14 @@ struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key, struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja, uint64_t key, uint64_t *result_key) { + dbg_printf("cds_ja_lookup_below_equal key %" PRIu64 "\n", key); return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_BE); } struct cds_ja_node *cds_ja_lookup_above_equal(struct cds_ja *ja, uint64_t key, uint64_t *result_key) { + dbg_printf("cds_ja_lookup_above_equal key %" PRIu64 "\n", key); return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_AE); } @@ -2135,25 +2145,41 @@ int ja_chain_node(struct cds_ja *ja, struct cds_ja_inode_flag *parent_node_flag, struct cds_ja_inode_flag **node_flag_ptr, struct cds_ja_inode_flag *node_flag, + struct cds_ja_node *last_node, struct cds_ja_node *node) { struct cds_ja_shadow_node *shadow_node; - int ret = 0; + struct cds_ja_node *iter_node; + int ret = 0, found = 0; shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag); if (!shadow_node) { return -EAGAIN; } - if (ja_node_ptr(*node_flag_ptr) != ja_node_ptr(node_flag)) { + /* + * Ensure that previous node is still there at end of list. + */ + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + if ((struct cds_ja_node *) ja_node_ptr(*node_flag_ptr) != iter_node) { + ret = -EAGAIN; + goto end; + } + cds_ja_for_each_duplicate(iter_node) { + if (iter_node == last_node) + found = 1; + } + if (!found) { ret = -EAGAIN; goto end; } /* - * Add node to head of list. Safe against concurrent RCU read - * traversals. + * Add node to tail of list to ensure that RCU traversals will + * always see either the prior node or the newly added if + * executed concurrently with a sequence of add followed by del + * on the same key. Safe against concurrent RCU read traversals. */ - node->next = (struct cds_ja_node *) node_flag; - rcu_assign_pointer(*node_flag_ptr, (struct cds_ja_inode_flag *) node); + node->next = NULL; + rcu_assign_pointer(last_node->next, node); end: rcuja_shadow_unlock(shadow_node); return ret; @@ -2175,7 +2201,7 @@ int _cds_ja_add(struct cds_ja *ja, uint64_t key, **node_flag_ptr; int ret; - if (caa_unlikely(key > ja->key_max)) { + if (caa_unlikely(key > ja->key_max || key == UINT64_MAX)) { return -EINVAL; } tree_depth = ja->tree_depth; @@ -2227,11 +2253,18 @@ retry: node_flag, key, i, node); } else { + struct cds_ja_node *iter_node, *last_node = NULL; + if (unique_node_ret) { *unique_node_ret = (struct cds_ja_node *) ja_node_ptr(node_flag); return -EEXIST; } + /* Find last duplicate */ + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + cds_ja_for_each_duplicate_rcu(iter_node) + last_node = iter_node; + 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); @@ -2243,6 +2276,7 @@ retry: parent_attach_node_flag, attach_node_flag_ptr, attach_node_flag, + last_node, node); } if (ret == -EAGAIN || ret == -EEXIST) @@ -2498,7 +2532,7 @@ int cds_ja_del(struct cds_ja *ja, uint64_t key, int nr_snapshot; int ret; - if (caa_unlikely(key > ja->key_max)) + if (caa_unlikely(key > ja->key_max || key == UINT64_MAX)) return -EINVAL; tree_depth = ja->tree_depth; @@ -2646,91 +2680,6 @@ ja_error: return NULL; } -/* - * Called from RCU read-side CS. - */ -__attribute__((visibility("protected"))) -void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, - struct cds_ja_inode_flag *node_flag, - void (*rcu_free_node)(struct cds_ja_node *node)) -{ - unsigned int type_index; - struct cds_ja_inode *node; - const struct cds_ja_type *type; - - node = ja_node_ptr(node_flag); - assert(node != NULL); - type_index = ja_node_type(node_flag); - type = &ja_types[type_index]; - - switch (type->type_class) { - case RCU_JA_LINEAR: - { - uint8_t nr_child = - ja_linear_node_get_nr_child(type, node); - unsigned int i; - - for (i = 0; i < nr_child; i++) { - struct cds_ja_inode_flag *iter; - struct cds_ja_node *node_iter, *n; - uint8_t v; - - ja_linear_node_get_ith_pos(type, node, i, &v, &iter); - node_iter = (struct cds_ja_node *) iter; - cds_ja_for_each_duplicate_safe(node_iter, n) { - rcu_free_node(node_iter); - } - } - break; - } - case RCU_JA_POOL: - { - unsigned int pool_nr; - - for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) { - struct cds_ja_inode *pool = - ja_pool_node_get_ith_pool(type, node, pool_nr); - uint8_t nr_child = - ja_linear_node_get_nr_child(type, pool); - unsigned int j; - - for (j = 0; j < nr_child; j++) { - struct cds_ja_inode_flag *iter; - struct cds_ja_node *node_iter, *n; - uint8_t v; - - ja_linear_node_get_ith_pos(type, pool, j, &v, &iter); - node_iter = (struct cds_ja_node *) iter; - cds_ja_for_each_duplicate_safe(node_iter, n) { - rcu_free_node(node_iter); - } - } - } - break; - } - case RCU_JA_NULL: - break; - case RCU_JA_PIGEON: - { - unsigned int i; - - for (i = 0; i < JA_ENTRY_PER_NODE; i++) { - struct cds_ja_inode_flag *iter; - struct cds_ja_node *node_iter, *n; - - iter = ja_pigeon_node_get_ith_pos(type, node, i); - node_iter = (struct cds_ja_node *) iter; - cds_ja_for_each_duplicate_safe(node_iter, n) { - rcu_free_node(node_iter); - } - } - break; - } - default: - assert(0); - } -} - static void print_debug_fallback_distribution(struct cds_ja *ja) { @@ -2752,6 +2701,9 @@ int ja_final_checks(struct cds_ja *ja) unsigned long na, nf, nr_fallback; int ret = 0; + if (!ja_debug_counters()) + return 0; + fallback_ratio = (double) uatomic_read(&ja->nr_fallback); fallback_ratio /= (double) uatomic_read(&ja->nr_nodes_allocated); nr_fallback = uatomic_read(&ja->nr_fallback); @@ -2780,16 +2732,14 @@ int ja_final_checks(struct cds_ja *ja) * on the Judy array while it is being destroyed (ensured by the * caller). */ -int cds_ja_destroy(struct cds_ja *ja, - void (*free_node_cb)(struct cds_ja_node *node)) +int cds_ja_destroy(struct cds_ja *ja) { const struct rcu_flavor_struct *flavor; int ret; flavor = cds_lfht_rcu_flavor(ja->ht); rcuja_shadow_prune(ja->ht, - RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK, - free_node_cb); + RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK); flavor->thread_offline(); ret = rcuja_delete_ht(ja->ht); if (ret)