X-Git-Url: http://git.lttng.org./?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=a16385b06f0f923dc5e2c603a7d3948057411d09;hb=28fd1038095007b48a9f81ee13cadcdff62853ef;hp=ef7619bd3fe6a6a8d62a28abe8917e08f75a964b;hpb=36305a3db8c572e25a6335c9384a5112bdfd8148;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index ef7619b..a16385b 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" @@ -370,7 +370,7 @@ 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 = NULL; unsigned int i; int match_idx = -1, match_v; @@ -389,10 +389,14 @@ 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; @@ -412,7 +416,6 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type 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; } @@ -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; } } @@ -1883,6 +1886,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 +1924,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 +1946,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 +2146,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; @@ -2227,11 +2254,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 +2277,7 @@ retry: parent_attach_node_flag, attach_node_flag_ptr, attach_node_flag, + last_node, node); } if (ret == -EAGAIN || ret == -EEXIST) @@ -2646,91 +2681,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) { @@ -2780,16 +2730,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)