X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=9398a222bcd526fc4d3dcd1f86e851a02a17ced4;hb=refs%2Fheads%2Furcu%2Frcuja-range;hp=94f004e602602be22fad1f526151e56b28cb8b88;hpb=86d700e9c533736a7a8918333a1e754500b7dde2;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 94f004e..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 = NULL; + 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); @@ -400,24 +401,23 @@ struct cds_ja_inode_flag *ja_linear_node_get_direction(const struct cds_ja_type 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; - ptr = rcu_dereference(pointers[match_idx]); - return ptr; + return rcu_dereference(match_ptr); } static @@ -1606,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 */ @@ -1672,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; } @@ -1784,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); @@ -1820,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: @@ -2146,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; @@ -2186,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; @@ -2238,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); @@ -2254,6 +2276,7 @@ retry: parent_attach_node_flag, attach_node_flag_ptr, attach_node_flag, + last_node, node); } if (ret == -EAGAIN || ret == -EEXIST) @@ -2509,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; @@ -2678,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);