From 03ec1aebe1d8eaa2b03a12b501e5b988efc0a6d0 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 5 Jun 2013 16:48:30 -0400 Subject: [PATCH] rcuja API: remove dependency on hlist - introduce cds_ja_for_each_duplicate_rcu() Signed-off-by: Mathieu Desnoyers --- rcuja/rcuja-internal.h | 16 +++++ rcuja/rcuja.c | 129 ++++++++++++++++-------------------- tests/test_urcu_ja.c | 144 ++++++++++++++++++++--------------------- urcu/rcuja.h | 20 ++++-- 4 files changed, 157 insertions(+), 152 deletions(-) diff --git a/rcuja/rcuja-internal.h b/rcuja/rcuja-internal.h index 9b1daca..1a3346b 100644 --- a/rcuja/rcuja-internal.h +++ b/rcuja/rcuja-internal.h @@ -190,6 +190,22 @@ int rcuja_delete_ht(struct cds_lfht *ht); __attribute__((visibility("protected"))) void free_cds_ja_node(struct cds_ja *ja, struct cds_ja_inode *node); +/* + * Iterate through duplicates returned by cds_ja_lookup*() + * Receives a struct cds_ja_node * as parameter, which is used as start + * of duplicate list and loop cursor. + */ +#define cds_ja_for_each_duplicate(pos) \ + for (; (pos) != NULL; (pos) = (pos)->next) + +/* + * Iterate through duplicates returned by cds_ja_lookup*() + * Safe against removal of entries during traversal. + */ +#define cds_ja_for_each_duplicate_safe(_pos, _next) \ + for (; (_pos) != NULL ? ((_next) = (_pos)->next, 1) : 0; \ + (_pos) = (_next)) + //#define DEBUG #ifdef __linux__ diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 4d1f2b4..29b7d8b 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -1707,20 +1707,19 @@ int ja_node_clear_ptr(struct cds_ja *ja, return ret; } -struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key) +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; - struct cds_hlist_head head = { NULL }; if (caa_unlikely(key > ja->key_max)) - return head; + return NULL; tree_depth = ja->tree_depth; node_flag = rcu_dereference(ja->root); /* level 0: root node */ if (!ja_node_ptr(node_flag)) - return head; + return NULL; for (i = 1; i < tree_depth; i++) { uint8_t iter_key; @@ -1730,22 +1729,20 @@ struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t 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 head; + return NULL; } /* Last level lookup succeded. We got an actual match. */ - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } -struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) +struct cds_ja_node *cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) { int tree_depth, level; struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH]; - struct cds_hlist_head head = { NULL }; if (caa_unlikely(key > ja->key_max || !key)) - return head; + return NULL; memset(cur_node_depth, 0, sizeof(cur_node_depth)); tree_depth = ja->tree_depth; @@ -1754,7 +1751,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) /* level 0: root node */ if (!ja_node_ptr(node_flag)) - return head; + return NULL; for (level = 1; level < tree_depth; level++) { uint8_t iter_key; @@ -1770,8 +1767,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) if (level == tree_depth) { /* Last level lookup succeded. We got an equal match. */ - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } /* @@ -1795,7 +1791,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) if (!level) { /* Reached the root and could not find a left sibling. */ - return head; + return NULL; } level++; @@ -1817,8 +1813,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) assert(level == tree_depth); - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } /* @@ -1852,7 +1847,6 @@ int ja_attach_node(struct cds_ja *ja, { struct cds_ja_shadow_node *shadow_node = NULL, *parent_shadow_node = NULL; - struct cds_hlist_head head; struct cds_ja_inode_flag *iter_node_flag, *iter_dest_node_flag; int ret, i; struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH]; @@ -1921,9 +1915,7 @@ int ja_attach_node(struct cds_ja *ja, } /* Create new branch, starting from bottom */ - CDS_INIT_HLIST_HEAD(&head); - cds_hlist_add_head_rcu(&child_node->list, &head); - iter_node_flag = (struct cds_ja_inode_flag *) head.next; + iter_node_flag = (struct cds_ja_inode_flag *) child_node; for (i = ja->tree_depth - 1; i >= (int) level; i--) { uint8_t iter_key; @@ -2003,9 +1995,9 @@ end: } /* - * Lock the parent containing the hlist head pointer, and add node to list of - * duplicates. Failure can happen if concurrent update changes the - * parent before we get the lock. We return -EAGAIN in that case. + * Lock the parent containing the pointer to list of duplicates, and add + * node to this list. Failure can happen if concurrent update changes + * the parent before we get the lock. We return -EAGAIN in that case. * Return 0 on success, negative error value on failure. */ static @@ -2026,7 +2018,12 @@ int ja_chain_node(struct cds_ja *ja, ret = -EAGAIN; goto end; } - cds_hlist_add_head_rcu(&node->list, (struct cds_hlist_head *) node_flag_ptr); + /* + * Add node to head of list. 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); end: rcuja_shadow_unlock(shadow_node); return ret; @@ -2312,8 +2309,7 @@ int ja_unchain_node(struct cds_ja *ja, struct cds_ja_node *node) { struct cds_ja_shadow_node *shadow_node; - struct cds_hlist_node *hlist_node; - struct cds_hlist_head hlist_head; + struct cds_ja_node *iter_node, **iter_node_ptr, **prev_node_ptr = NULL; int ret = 0, count = 0, found = 0; shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag); @@ -2323,28 +2319,30 @@ int ja_unchain_node(struct cds_ja *ja, ret = -EAGAIN; goto end; } - hlist_head.next = (struct cds_hlist_node *) ja_node_ptr(node_flag); /* - * Retry if another thread removed all but one of duplicates - * since check (this check was performed without lock). - * Ensure that the node we are about to remove is still in the - * list (while holding lock). + * Find the previous node's next pointer pointing to our node, + * so we can update it. Retry if another thread removed all but + * one of duplicates since check (this check was performed + * without lock). Ensure that the node we are about to remove is + * still in the list (while holding lock). No need for RCU + * traversal here since we hold the lock on the parent. */ - cds_hlist_for_each_rcu(hlist_node, &hlist_head) { - if (count == 0) { - /* FIXME: currently a work-around */ - hlist_node->prev = (struct cds_hlist_node *) node_flag_ptr; - } + iter_node_ptr = (struct cds_ja_node **) node_flag_ptr; + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + cds_ja_for_each_duplicate(iter_node) { count++; - if (hlist_node == &node->list) + if (iter_node == node) { + prev_node_ptr = iter_node_ptr; found++; + } + iter_node_ptr = &iter_node->next; } assert(found <= 1); if (!found || count == 1) { ret = -EAGAIN; goto end; } - cds_hlist_del_rcu(&node->list); + CMM_STORE_SHARED(*prev_node_ptr, node->next); /* * Validate that we indeed removed the node from linked list. */ @@ -2419,22 +2417,17 @@ retry: key); return -ENOENT; } else { - struct cds_hlist_head hlist_head; - struct cds_hlist_node *hlist_node; - struct cds_ja_node *entry, *match = NULL; + struct cds_ja_node *iter_node, *match = NULL; int count = 0; - hlist_head.next = - (struct cds_hlist_node *) ja_node_ptr(node_flag); - cds_hlist_for_each_entry_rcu(entry, - hlist_node, - &hlist_head, - list) { - dbg_printf("cds_ja_del: compare %p with entry %p\n", node, entry); - if (entry == node) - match = entry; + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + cds_ja_for_each_duplicate_rcu(iter_node) { + dbg_printf("cds_ja_del: compare %p with iter_node %p\n", node, iter_node); + if (iter_node == node) + match = iter_node; count++; } + if (!match) { dbg_printf("cds_ja_del: no node match for node %p key %" PRIu64 "\n", node, key); return -ENOENT; @@ -2549,17 +2542,13 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (i = 0; i < nr_child; i++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; uint8_t v; ja_linear_node_get_ith_pos(type, node, i, &v, &iter); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - rcu_free_node(entry); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } break; @@ -2577,17 +2566,13 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (j = 0; j < nr_child; j++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; uint8_t v; ja_linear_node_get_ith_pos(type, pool, j, &v, &iter); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - rcu_free_node(entry); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } } @@ -2601,16 +2586,12 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (i = 0; i < JA_ENTRY_PER_NODE; i++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; iter = ja_pigeon_node_get_ith_pos(type, node, i); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - rcu_free_node(entry); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } break; diff --git a/tests/test_urcu_ja.c b/tests/test_urcu_ja.c index 7230ec6..c252290 100644 --- a/tests/test_urcu_ja.c +++ b/tests/test_urcu_ja.c @@ -257,11 +257,11 @@ int test_8bit_key(void) printf("Test #2: successful key lookup (8-bit).\n"); for (key = 0; key < 200; key++) { - struct cds_hlist_head head; + struct cds_ja_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - if (cds_hlist_empty(&head)) { + node = cds_ja_lookup(test_ja, key); + if (!node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } @@ -270,11 +270,11 @@ int test_8bit_key(void) printf("OK\n"); printf("Test #3: unsuccessful key lookup (8-bit).\n"); for (key = 200; key < 240; key++) { - struct cds_hlist_head head; + struct cds_ja_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - if (!cds_hlist_empty(&head)) { + node = cds_ja_lookup(test_ja, key); + if (node) { fprintf(stderr, "Error unexpected lookup node %" PRIu64 "\n", key); @@ -285,25 +285,25 @@ int test_8bit_key(void) printf("OK\n"); printf("Test #4: remove keys (8-bit).\n"); for (key = 0; key < 200; key++) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); - if (!node) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } + node = caa_container_of(ja_node, struct ja_test_node, node); ret = cds_ja_del(test_ja, key, &node->node); if (ret) { fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key); assert(0); } rcu_free_test_node(node); - head = cds_ja_lookup(test_ja, key); - if (!cds_hlist_empty(&head)) { - fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next); + ja_node = cds_ja_lookup(test_ja, key); + if (ja_node) { + fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node); assert(0); } rcu_read_unlock(); @@ -328,18 +328,18 @@ int test_8bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; key = ka[i] + ka_test_offset; rcu_read_lock(); - head = cds_ja_lookup_lower_equal(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup_lower_equal(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); + node = caa_container_of(ja_node, struct ja_test_node, node); if (node->key != ka[i]) { fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", ka[i], key, node->key); @@ -349,18 +349,18 @@ int test_8bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; key = ka[i]; /* without offset */ rcu_read_lock(); - head = cds_ja_lookup_lower_equal(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup_lower_equal(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); + node = caa_container_of(ja_node, struct ja_test_node, node); if (node->key != ka[i]) { fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", ka[i], key, node->key); @@ -415,11 +415,11 @@ int test_16bit_key(void) printf("Test #2: successful key lookup (16-bit).\n"); for (key = 0; key < 10000; key++) { //for (key = 0; key < 65536; key+=256) { - struct cds_hlist_head head; + struct cds_ja_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - if (cds_hlist_empty(&head)) { + node = cds_ja_lookup(test_ja, key); + if (!node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } @@ -428,11 +428,11 @@ int test_16bit_key(void) printf("OK\n"); printf("Test #3: unsuccessful key lookup (16-bit).\n"); for (key = 11000; key <= 11002; key++) { - struct cds_hlist_head head; + struct cds_ja_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - if (!cds_hlist_empty(&head)) { + node = cds_ja_lookup(test_ja, key); + if (node) { fprintf(stderr, "Error unexpected lookup node %" PRIu64 "\n", key); @@ -444,25 +444,25 @@ int test_16bit_key(void) printf("Test #4: remove keys (16-bit).\n"); for (key = 0; key < 10000; key++) { //for (key = 0; key < 65536; key+=256) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); - if (!node) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } + node = caa_container_of(ja_node, struct ja_test_node, node); ret = cds_ja_del(test_ja, key, &node->node); if (ret) { fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key); assert(0); } rcu_free_test_node(node); - head = cds_ja_lookup(test_ja, key); - if (!cds_hlist_empty(&head)) { - fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next); + ja_node = cds_ja_lookup(test_ja, key); + if (ja_node) { + fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node); assert(0); } rcu_read_unlock(); @@ -487,18 +487,18 @@ int test_16bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; key = ka[i] + ka_test_offset; rcu_read_lock(); - head = cds_ja_lookup_lower_equal(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup_lower_equal(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); + node = caa_container_of(ja_node, struct ja_test_node, node); if (node->key != ka[i]) { fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", ka[i], key, node->key); @@ -508,18 +508,18 @@ int test_16bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; key = ka[i]; /* without offset */ rcu_read_lock(); - head = cds_ja_lookup_lower_equal(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup_lower_equal(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); + node = caa_container_of(ja_node, struct ja_test_node, node); if (node->key != ka[i]) { fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", ka[i], key, node->key); @@ -585,18 +585,17 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #2: successful key lookup (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; struct ja_test_node *node; - struct cds_hlist_node *pos; int count = 0; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } - cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) { + cds_ja_for_each_duplicate_rcu(ja_node) { count++; } if (count != nr_dup) { @@ -611,11 +610,11 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_hlist_head head; + struct cds_ja_node *ja_node; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key + 42); - if (!cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup(test_ja, key + 42); + if (ja_node) { fprintf(stderr, "Error unexpected lookup node %" PRIu64 "\n", key + 42); @@ -630,38 +629,34 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #4: remove keys (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_hlist_head head; - struct ja_test_node *node; - struct cds_hlist_node *pos; + struct cds_ja_node *ja_node; int count = 0; rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); + ja_node = cds_ja_lookup(test_ja, key); - - cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) { - struct cds_hlist_head testhead; + cds_ja_for_each_duplicate_rcu(ja_node) { + struct cds_ja_node *test_ja_node; + struct ja_test_node *node; count++; - if (!node) { - fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); - assert(0); - } + node = caa_container_of(ja_node, + struct ja_test_node, node); ret = cds_ja_del(test_ja, key, &node->node); if (ret) { fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key); assert(0); } rcu_free_test_node(node); - testhead = cds_ja_lookup(test_ja, key); - if (count < nr_dup && cds_hlist_empty(&testhead)) { + test_ja_node = cds_ja_lookup(test_ja, key); + if (count < nr_dup && !test_ja_node) { fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n"); assert(0); } } - head = cds_ja_lookup(test_ja, key); - if (!cds_hlist_empty(&head)) { - fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next); + ja_node = cds_ja_lookup(test_ja, key); + if (ja_node) { + fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node); assert(0); } rcu_read_unlock(); @@ -747,7 +742,7 @@ static void *test_ja_rw_thr_reader(void *_count) { unsigned long long *count = _count; - struct cds_hlist_head head; + struct cds_ja_node *ja_node; uint64_t key; printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", @@ -768,8 +763,8 @@ void *test_ja_rw_thr_reader(void *_count) /* note: only looking up ulong keys */ key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset; key *= key_mul; - head = cds_ja_lookup(test_ja, key); - if (cds_hlist_empty(&head)) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { if (validate_lookup) { printf("[ERROR] Lookup cannot find initial node.\n"); exit(-1); @@ -810,7 +805,6 @@ static void *test_ja_rw_thr_writer(void *_count) { struct wr_count *count = _count; - struct cds_hlist_head head; uint64_t key; int ret; @@ -858,6 +852,7 @@ void *test_ja_rw_thr_writer(void *_count) } rcu_read_unlock(); } else { + struct cds_ja_node *ja_node; struct ja_test_node *node; /* May delete */ @@ -867,9 +862,11 @@ void *test_ja_rw_thr_writer(void *_count) rcu_read_lock(); - head = cds_ja_lookup(test_ja, key); - node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list); - if (node) { + ja_node = cds_ja_lookup(test_ja, key); + /* Remove first entry */ + if (ja_node) { + node = caa_container_of(ja_node, + struct ja_test_node, node); ret = cds_ja_del(test_ja, key, &node->node); if (!ret) { rcu_free_test_node(node); @@ -910,7 +907,6 @@ void *test_ja_rw_thr_writer(void *_count) static int do_mt_populate_ja(void) { - struct cds_hlist_head head; uint64_t iter; int ret; diff --git a/urcu/rcuja.h b/urcu/rcuja.h index a6407b6..f8cba6a 100644 --- a/urcu/rcuja.h +++ b/urcu/rcuja.h @@ -36,9 +36,12 @@ extern "C" { #endif +/* + * Duplicate nodes with the same key are chained into a singly-linked + * list. The last item of this list has a NULL next pointer. + */ struct cds_ja_node { - /* Linked list of nodes with same key */ - struct cds_hlist_node list; + struct cds_ja_node *next; }; struct cds_ja; @@ -55,8 +58,8 @@ void cds_ja_node_init(struct cds_ja_node *node) { } -struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key); -struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, +struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key); +struct cds_ja_node *cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key); int cds_ja_add(struct cds_ja *ja, uint64_t key, @@ -80,6 +83,15 @@ struct cds_ja *cds_ja_new(unsigned int key_bits) int cds_ja_destroy(struct cds_ja *ja, void (*rcu_free_node_cb)(struct cds_ja_node *node)); +/* + * Iterate through duplicates returned by cds_ja_lookup*() + * This must be done while rcu_read_lock() is held. + * Receives a struct cds_ja_node * as parameter, which is used as start + * of duplicate list and loop cursor. + */ +#define cds_ja_for_each_duplicate_rcu(pos) \ + for (; (pos) != NULL; (pos) = rcu_dereference((pos)->next)) + #ifdef __cplusplus } #endif -- 2.34.1