From 3d8fe30760fd4fb67ce24b5aa011ab75f680a904 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 24 Aug 2012 17:30:02 -0400 Subject: [PATCH] rcuja: free all leaf nodes at destruction Signed-off-by: Mathieu Desnoyers --- rcuja/rcuja-internal.h | 77 ++++++++++++-- rcuja/rcuja-shadow-nodes.c | 44 ++++---- rcuja/rcuja.c | 203 +++++++++++++++++++++++-------------- tests/test_urcu_ja.c | 31 +++++- tests/test_urcu_ja.h | 2 - urcu/hlist.h | 4 + 6 files changed, 252 insertions(+), 109 deletions(-) diff --git a/rcuja/rcuja-internal.h b/rcuja/rcuja-internal.h index 74ee728..82ab158 100644 --- a/rcuja/rcuja-internal.h +++ b/rcuja/rcuja-internal.h @@ -28,15 +28,43 @@ #include #include +/* + * Number of least significant pointer bits reserved to represent the + * child type. + */ +#define JA_TYPE_BITS 3 +#define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS) +#define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) +#define JA_PTR_MASK (~JA_TYPE_MASK) + +#define JA_ENTRY_PER_NODE 256UL +#define JA_LOG2_BITS_PER_BYTE 3U +#define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE) + +#define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */ + +/* + * Entry for NULL node is at index 8 of the table. It is never encoded + * in flags. + */ +#define NODE_INDEX_NULL 8 + +/* + * Number of removals needed on a fallback node before we try to shrink + * it. + */ +#define JA_FALLBACK_REMOVAL_COUNT 8 + /* Never declared. Opaque type used to store flagged node pointers. */ struct cds_ja_inode_flag; +struct cds_ja_inode; /* * Shadow node contains mutex and call_rcu head associated with a node. */ struct cds_ja_shadow_node { struct cds_lfht_node ht_node; /* hash table node */ - struct cds_ja_inode *node; /* reverse mapping and hash table key */ + struct cds_ja_inode_flag *node_flag; /* reverse mapping and hash table key */ /* * mutual exclusion on all nodes belonging to the same tree * position (e.g. both nodes before and after recompaction @@ -45,8 +73,9 @@ struct cds_ja_shadow_node { pthread_mutex_t *lock; unsigned int nr_child; /* number of children in node */ struct rcu_head head; /* for deferred node and shadow node reclaim */ - int is_root; /* is it a root node ? */ int fallback_removal_count; /* removals left keeping fallback */ + int level; /* level in the tree */ + struct cds_ja *ja; /* toplevel judy array */ }; struct cds_ja { @@ -62,17 +91,50 @@ struct cds_ja { unsigned long nr_fallback; /* Number of fallback nodes used */ }; +static inline +struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, + unsigned long type) +{ + assert(type < (1UL << JA_TYPE_BITS)); + return (struct cds_ja_inode_flag *) (((unsigned long) node) | type); +} + +static inline +struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) +{ + return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK); +} + +static inline +unsigned long ja_node_type(struct cds_ja_inode_flag *node) +{ + unsigned long type; + + if (ja_node_ptr(node) == NULL) { + return NODE_INDEX_NULL; + } + type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK); + assert(type < (1UL << JA_TYPE_BITS)); + return type; +} + +__attribute__((visibility("protected"))) +void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, + struct cds_ja_inode_flag *node_flag, + void (*free_node_cb)(struct rcu_head *head)); + __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, - struct cds_ja_inode *node); + struct cds_ja_inode_flag *node_flag); __attribute__((visibility("protected"))) void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node); __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, - struct cds_ja_inode *new_node, - struct cds_ja_shadow_node *inherit_from); + struct cds_ja_inode_flag *new_node_flag, + struct cds_ja_shadow_node *inherit_from, + struct cds_ja *ja); /* rcuja_shadow_clear flags */ enum { @@ -82,13 +144,14 @@ enum { __attribute__((visibility("protected"))) int rcuja_shadow_clear(struct cds_lfht *ht, - struct cds_ja_inode *node, + struct cds_ja_inode_flag *node_flag, struct cds_ja_shadow_node *shadow_node, unsigned int flags); __attribute__((visibility("protected"))) void rcuja_shadow_prune(struct cds_lfht *ht, - unsigned int flags); + unsigned int flags, + void (*free_node_cb)(struct rcu_head *head)); __attribute__((visibility("protected"))) struct cds_lfht *rcuja_create_ht(const struct rcu_flavor_struct *flavor); diff --git a/rcuja/rcuja-shadow-nodes.c b/rcuja/rcuja-shadow-nodes.c index d6e4ff5..983adef 100644 --- a/rcuja/rcuja-shadow-nodes.c +++ b/rcuja/rcuja-shadow-nodes.c @@ -171,12 +171,12 @@ int match_pointer(struct cds_lfht_node *node, const void *key) struct cds_ja_shadow_node *shadow = caa_container_of(node, struct cds_ja_shadow_node, ht_node); - return (key == shadow->node); + return (key == shadow->node_flag); } __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, - struct cds_ja_inode *node) + struct cds_ja_inode_flag *node_flag) { struct cds_lfht_iter iter; struct cds_lfht_node *lookup_node; @@ -186,8 +186,8 @@ struct cds_ja_shadow_node *rcuja_shadow_lookup_lock(struct cds_lfht *ht, flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); - cds_lfht_lookup(ht, hash_pointer(node, hash_seed), - match_pointer, node, &iter); + cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), + match_pointer, node_flag, &iter); lookup_node = cds_lfht_iter_get_node(&iter); if (!lookup_node) { @@ -221,8 +221,9 @@ void rcuja_shadow_unlock(struct cds_ja_shadow_node *shadow_node) __attribute__((visibility("protected"))) struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, - struct cds_ja_inode *new_node, - struct cds_ja_shadow_node *inherit_from) + struct cds_ja_inode_flag *new_node_flag, + struct cds_ja_shadow_node *inherit_from, + struct cds_ja *ja) { struct cds_ja_shadow_node *shadow_node; struct cds_lfht_node *ret_node; @@ -232,7 +233,8 @@ struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, if (!shadow_node) return NULL; - shadow_node->node = new_node; + shadow_node->node_flag = new_node_flag; + shadow_node->ja = ja; /* * Lock can be inherited from previous node at this position. */ @@ -250,9 +252,9 @@ struct cds_ja_shadow_node *rcuja_shadow_set(struct cds_lfht *ht, flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); ret_node = cds_lfht_add_unique(ht, - hash_pointer(new_node, hash_seed), + hash_pointer(new_node_flag, hash_seed), match_pointer, - new_node, + new_node_flag, &shadow_node->ht_node); flavor->read_unlock(); @@ -276,7 +278,7 @@ void free_shadow_node_and_node(struct rcu_head *head) { struct cds_ja_shadow_node *shadow_node = caa_container_of(head, struct cds_ja_shadow_node, head); - free(shadow_node->node); + free(ja_node_ptr(shadow_node->node_flag)); free(shadow_node); } @@ -294,15 +296,15 @@ void free_shadow_node_and_node_and_lock(struct rcu_head *head) { struct cds_ja_shadow_node *shadow_node = caa_container_of(head, struct cds_ja_shadow_node, head); - assert(!shadow_node->is_root); - free(shadow_node->node); + assert(shadow_node->level); + free(ja_node_ptr(shadow_node->node_flag)); free(shadow_node->lock); free(shadow_node); } __attribute__((visibility("protected"))) int rcuja_shadow_clear(struct cds_lfht *ht, - struct cds_ja_inode *node, + struct cds_ja_inode_flag *node_flag, struct cds_ja_shadow_node *shadow_node, unsigned int flags) { @@ -315,8 +317,8 @@ int rcuja_shadow_clear(struct cds_lfht *ht, flavor = cds_lfht_rcu_flavor(ht); flavor->read_lock(); - cds_lfht_lookup(ht, hash_pointer(node, hash_seed), - match_pointer, node, &iter); + cds_lfht_lookup(ht, hash_pointer(node_flag, hash_seed), + match_pointer, node_flag, &iter); lookup_node = cds_lfht_iter_get_node(&iter); if (!lookup_node) { ret = -ENOENT; @@ -339,7 +341,7 @@ int rcuja_shadow_clear(struct cds_lfht *ht, ret = cds_lfht_del(ht, lookup_node); if (!ret) { if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) - && !shadow_node->is_root) { + && shadow_node->level) { if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node_and_lock); @@ -373,7 +375,8 @@ rcu_unlock: */ __attribute__((visibility("protected"))) void rcuja_shadow_prune(struct cds_lfht *ht, - unsigned int flags) + unsigned int flags, + void (*free_node_cb)(struct rcu_head *head)) { const struct rcu_flavor_struct *flavor; struct cds_ja_shadow_node *shadow_node; @@ -389,7 +392,12 @@ void rcuja_shadow_prune(struct cds_lfht *ht, ret = cds_lfht_del(ht, &shadow_node->ht_node); if (!ret) { if ((flags & RCUJA_SHADOW_CLEAR_FREE_NODE) - && !shadow_node->is_root) { + && shadow_node->level) { + if (shadow_node->level == shadow_node->ja->tree_depth - 1) { + rcuja_free_all_children(shadow_node, + shadow_node->node_flag, + free_node_cb); + } if (flags & RCUJA_SHADOW_CLEAR_FREE_LOCK) { flavor->update_call_rcu(&shadow_node->head, free_shadow_node_and_node_and_lock); diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 6b54219..12cce1d 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -61,33 +61,6 @@ struct cds_ja_type { uint16_t pool_size_order; /* pool size */ }; -/* - * Number of least significant pointer bits reserved to represent the - * child type. - */ -#define JA_TYPE_BITS 3 -#define JA_TYPE_MAX_NR (1UL << JA_TYPE_BITS) -#define JA_TYPE_MASK (JA_TYPE_MAX_NR - 1) -#define JA_PTR_MASK (~JA_TYPE_MASK) - -#define JA_ENTRY_PER_NODE 256UL -#define JA_LOG2_BITS_PER_BYTE 3U -#define JA_BITS_PER_BYTE (1U << JA_LOG2_BITS_PER_BYTE) - -#define JA_MAX_DEPTH 9 /* Maximum depth, including leafs */ - -/* - * Entry for NULL node is at index 8 of the table. It is never encoded - * in flags. - */ -#define NODE_INDEX_NULL 8 - -/* - * Number of removals needed on a fallback node before we try to shrink - * it. - */ -#define JA_FALLBACK_REMOVAL_COUNT 8 - /* * Iteration on the array to find the right node size for the number of * children stops when it reaches .max_child == 256 (this is the largest @@ -266,33 +239,6 @@ enum ja_recompact { JA_RECOMPACT_DEL, }; -static -struct cds_ja_inode_flag *ja_node_flag(struct cds_ja_inode *node, - unsigned long type) -{ - assert(type < (1UL << JA_TYPE_BITS)); - return (struct cds_ja_inode_flag *) (((unsigned long) node) | type); -} - -static -struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) -{ - return (struct cds_ja_inode *) (((unsigned long) node) & JA_PTR_MASK); -} - -static -unsigned long ja_node_type(struct cds_ja_inode_flag *node) -{ - unsigned long type; - - if (ja_node_ptr(node) == NULL) { - return NODE_INDEX_NULL; - } - type = (unsigned int) ((unsigned long) node & JA_TYPE_MASK); - assert(type < (1UL << JA_TYPE_BITS)); - return type; -} - struct cds_ja_inode *alloc_cds_ja_node(const struct cds_ja_type *ja_type) { return calloc(1U << ja_type->order, sizeof(char)); @@ -699,7 +645,7 @@ int ja_node_recompact(enum ja_recompact mode, const struct cds_ja_type *old_type, struct cds_ja_inode *old_node, struct cds_ja_shadow_node *shadow_node, - struct cds_ja_inode_flag **old_node_flag, uint8_t n, + struct cds_ja_inode_flag **old_node_flag_ptr, uint8_t n, struct cds_ja_inode_flag *child_node_flag, struct cds_ja_inode_flag **nullify_node_flag_ptr) { @@ -707,10 +653,12 @@ int ja_node_recompact(enum ja_recompact mode, struct cds_ja_inode *new_node; struct cds_ja_shadow_node *new_shadow_node = NULL; const struct cds_ja_type *new_type; - struct cds_ja_inode_flag *new_node_flag; + struct cds_ja_inode_flag *new_node_flag, *old_node_flag; int ret; int fallback = 0; + old_node_flag = *old_node_flag_ptr; + switch (mode) { case JA_RECOMPACT: new_type_index = old_type_index; @@ -743,7 +691,7 @@ retry: /* for fallback */ return -ENOMEM; new_node_flag = ja_node_flag(new_node, new_type_index); dbg_printf("Recompact inherit lock from %p\n", shadow_node); - new_shadow_node = rcuja_shadow_set(ja->ht, new_node, shadow_node); + new_shadow_node = rcuja_shadow_set(ja->ht, new_node_flag, shadow_node, ja); if (!new_shadow_node) { free(new_node); return -ENOMEM; @@ -863,8 +811,8 @@ skip_copy: n, child_node_flag); assert(!ret); } - /* Return pointer to new recompacted node through old_node_flag */ - *old_node_flag = new_node_flag; + /* Return pointer to new recompacted node through old_node_flag_ptr */ + *old_node_flag_ptr = new_node_flag; if (old_node) { int flags; @@ -876,7 +824,7 @@ skip_copy: */ if (new_type_index == NODE_INDEX_NULL) flags = RCUJA_SHADOW_CLEAR_FREE_LOCK; - ret = rcuja_shadow_clear(ja->ht, old_node, shadow_node, + ret = rcuja_shadow_clear(ja->ht, old_node_flag, shadow_node, flags); assert(!ret); } @@ -888,7 +836,7 @@ end: fallback_toosmall: /* fallback if next pool is too small */ assert(new_shadow_node); - ret = rcuja_shadow_clear(ja->ht, new_node, new_shadow_node, + ret = rcuja_shadow_clear(ja->ht, new_node_flag, new_shadow_node, RCUJA_SHADOW_CLEAR_FREE_NODE); assert(!ret); @@ -1037,14 +985,14 @@ int ja_attach_node(struct cds_ja *ja, level, node, node_flag); assert(node); - shadow_node = rcuja_shadow_lookup_lock(ja->ht, node); + shadow_node = rcuja_shadow_lookup_lock(ja->ht, node_flag); if (!shadow_node) { ret = -EAGAIN; goto end; } if (parent_node) { parent_shadow_node = rcuja_shadow_lookup_lock(ja->ht, - parent_node); + parent_node_flag); if (!parent_shadow_node) { ret = -EAGAIN; goto unlock_shadow; @@ -1107,7 +1055,7 @@ check_error: if (i) flags |= RCUJA_SHADOW_CLEAR_FREE_NODE; tmpret = rcuja_shadow_clear(ja->ht, - ja_node_ptr(created_nodes[i]), + created_nodes[i], NULL, flags); assert(!tmpret); @@ -1136,8 +1084,7 @@ int ja_chain_node(struct cds_ja *ja, { struct cds_ja_shadow_node *shadow_node; - shadow_node = rcuja_shadow_lookup_lock(ja->ht, - ja_node_ptr(parent_node_flag)); + shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag); if (!shadow_node) return -EAGAIN; cds_hlist_add_head_rcu(&node->list, head); @@ -1252,7 +1199,7 @@ int ja_detach_node(struct cds_ja *ja, struct cds_ja_shadow_node *shadow_node; shadow_node = rcuja_shadow_lookup_lock(ja->ht, - ja_node_ptr(snapshot[i])); + snapshot[i]); if (!shadow_node) { ret = -EAGAIN; goto end; @@ -1273,7 +1220,7 @@ int ja_detach_node(struct cds_ja *ja, if (shadow_node->nr_child > 1 || i == 1) { /* Lock parent and break */ shadow_node = rcuja_shadow_lookup_lock(ja->ht, - ja_node_ptr(snapshot[i - 1])); + snapshot[i - 1]); if (!shadow_node) { ret = -EAGAIN; goto end; @@ -1289,7 +1236,7 @@ int ja_detach_node(struct cds_ja *ja, * to recompact parent. */ shadow_node = rcuja_shadow_lookup_lock(ja->ht, - ja_node_ptr(snapshot[i - 2])); + snapshot[i - 2]); if (!shadow_node) { ret = -EAGAIN; goto end; @@ -1310,7 +1257,7 @@ int ja_detach_node(struct cds_ja *ja, for (i = 0; i < nr_clear; i++) { ret = rcuja_shadow_clear(ja->ht, - shadow_nodes[i]->node, + shadow_nodes[i]->node_flag, shadow_nodes[i], RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK); @@ -1342,8 +1289,7 @@ int ja_unchain_node(struct cds_ja *ja, struct cds_ja_shadow_node *shadow_node; int ret = 0; - shadow_node = rcuja_shadow_lookup_lock(ja->ht, - ja_node_ptr(parent_node_flag)); + shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag); if (!shadow_node) return -EAGAIN; /* @@ -1496,13 +1442,13 @@ struct cds_ja *_cds_ja_new(unsigned int key_bits, * Note: we should not free this node until judy array destroy. */ root_shadow_node = rcuja_shadow_set(ja->ht, - ja_node_ptr((struct cds_ja_inode_flag *) &ja->root), - NULL); + (struct cds_ja_inode_flag *) &ja->root, + NULL, ja); if (!root_shadow_node) { ret = -ENOMEM; goto ht_node_error; } - root_shadow_node->is_root = 1; + root_shadow_node->level = 0; return ja; @@ -1516,16 +1462,119 @@ 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 (*free_node_cb)(struct rcu_head *head)) +{ + const struct rcu_flavor_struct *flavor; + unsigned int type_index; + struct cds_ja_inode *node; + const struct cds_ja_type *type; + + flavor = cds_lfht_rcu_flavor(shadow_node->ja->ht); + 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_hlist_head head; + struct cds_ja_node *entry; + struct cds_hlist_node *pos; + 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_rcu(entry, pos, &head, list) { + flavor->update_call_rcu(&entry->head, free_node_cb); + } + } + 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_hlist_head head; + struct cds_ja_node *entry; + struct cds_hlist_node *pos; + uint8_t v; + + ja_linear_node_get_ith_pos(type, node, j, &v, &iter); + if (!iter) + continue; + head.next = (struct cds_hlist_node *) iter; + cds_hlist_for_each_entry_rcu(entry, pos, &head, list) { + flavor->update_call_rcu(&entry->head, free_node_cb); + } + } + } + break; + } + case RCU_JA_NULL: + break; + case RCU_JA_PIGEON: + { + uint8_t nr_child; + unsigned int i; + + nr_child = shadow_node->nr_child; + 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; + + 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_rcu(entry, pos, &head, list) { + flavor->update_call_rcu(&entry->head, free_node_cb); + } + } + break; + } + default: + assert(0); + } +} + /* * There should be no more concurrent add to the judy array while it is * being destroyed (ensured by the caller). */ -int cds_ja_destroy(struct cds_ja *ja) +int cds_ja_destroy(struct cds_ja *ja, + void (*free_node_cb)(struct rcu_head *head)) { int ret; rcuja_shadow_prune(ja->ht, - RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK); + RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK, + free_node_cb); ret = rcuja_delete_ht(ja->ht); if (ret) return ret; diff --git a/tests/test_urcu_ja.c b/tests/test_urcu_ja.c index d933bae..7b64575 100644 --- a/tests/test_urcu_ja.c +++ b/tests/test_urcu_ja.c @@ -123,14 +123,14 @@ void rcu_copy_mutex_unlock(void) } } -#if 0 void free_node_cb(struct rcu_head *head) { struct ja_test_node *node = - caa_container_of(head, struct ja_test_node, head); + caa_container_of(head, struct ja_test_node, node.head); free(node); } +#if 0 static void test_delete_all_nodes(struct cds_lfht *ht) { @@ -233,8 +233,29 @@ int test_8bit_key(void) rcu_read_unlock(); } printf("OK\n"); + printf("Test #4: remove keys (8-bit).\n"); + for (key = 0; key < 200; key++) { + struct cds_hlist_head head; + 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) { + fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); + assert(0); + } + ret = cds_ja_del(test_ja, key, &node->node); + if (ret) { + fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key); + assert(0); + } + call_rcu(&node->node.head, free_node_cb); + rcu_read_unlock(); + } + printf("OK\n"); - ret = cds_ja_destroy(test_ja); + ret = cds_ja_destroy(test_ja, free_node_cb); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; @@ -304,7 +325,7 @@ int test_16bit_key(void) } printf("OK\n"); - ret = cds_ja_destroy(test_ja); + ret = cds_ja_destroy(test_ja, free_node_cb); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; @@ -390,7 +411,7 @@ int test_sparse_key(unsigned int bits) printf("OK\n"); } - ret = cds_ja_destroy(test_ja); + ret = cds_ja_destroy(test_ja, free_node_cb); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; diff --git a/tests/test_urcu_ja.h b/tests/test_urcu_ja.h index 1e90987..3174613 100644 --- a/tests/test_urcu_ja.h +++ b/tests/test_urcu_ja.h @@ -107,8 +107,6 @@ extern struct cds_ja *test_ja; struct ja_test_node { struct cds_ja_node node; uint64_t key; /* for testing */ - /* cache-cold for iteration */ - struct rcu_head head; }; static inline struct ja_test_node * diff --git a/urcu/hlist.h b/urcu/hlist.h index 222a59a..15e672b 100644 --- a/urcu/hlist.h +++ b/urcu/hlist.h @@ -39,6 +39,10 @@ static inline void CDS_INIT_HLIST_HEAD(struct cds_hlist_head *ptr) #define cds_hlist_entry(ptr, type, member) \ ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member))) +/* Get first entry from a list. Assumes the hlist is not empty. */ +#define cds_hlist_first_entry(ptr, type, member) \ + cds_list_entry((ptr)->next, type, member) + static inline int cds_hlist_empty(struct cds_hlist_head *head) { return !head->next; -- 2.34.1