X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=f3c96880fc6dc12c920a204bf284be14f688c16c;hp=4abf27a9a5dd5e9f56f97d669de88e58705e741d;hb=33c7c748c098dfc963c934fde62328169834c1ed;hpb=98f969fc5e7fcd7dcc260dde0ef788e8df50775a diff --git a/rculfhash.c b/rculfhash.c index 4abf27a..f3c9688 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -38,7 +38,7 @@ #include #include -#define DEBUG /* Test */ +//#define DEBUG /* Test */ #ifdef DEBUG #define dbg_printf(args...) printf(args) @@ -47,17 +47,27 @@ #endif #define CHAIN_LEN_TARGET 4 -#define CHAIN_LEN_RESIZE_THRESHOLD 16 +#define CHAIN_LEN_RESIZE_THRESHOLD 8 #ifndef max #define max(a, b) ((a) > (b) ? (a) : (b)) #endif +/* + * The removed flag needs to be updated atomically with the pointer. + * The dummy flag does not require to be updated atomically with the + * pointer, but it is added as a pointer low bit flag to save space. + */ +#define REMOVED_FLAG (1UL << 0) +#define DUMMY_FLAG (1UL << 1) +#define FLAGS_MASK ((1UL << 2) - 1) + struct rcu_table { unsigned long size; /* always a power of 2 */ unsigned long resize_target; + int resize_initiated; struct rcu_head head; - struct rcu_ht_node *tbl[0]; + struct _rcu_ht_node *tbl[0]; }; struct rcu_ht { @@ -66,6 +76,7 @@ struct rcu_ht { ht_compare_fct compare_fct; unsigned long hash_seed; pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ + unsigned int in_progress_resize, in_progress_destroy; void (*ht_call_rcu)(struct rcu_head *head, void (*func)(struct rcu_head *head)); }; @@ -133,30 +144,138 @@ unsigned long bit_reverse_ulong(unsigned long v) } /* - * Algorithm to find the log2 of a 32-bit unsigned integer. - * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup - * Originally from Public Domain. + * fls: returns the position of the most significant bit. + * Returns 0 if no bit is set, else returns the position of the most + * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit). */ -static const char LogTable256[256] = +#if defined(__i386) || defined(__x86_64) +static inline +unsigned int fls_u32(uint32_t x) { -#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n - -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, - LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), - LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) -}; + int r; + + asm("bsrl %1,%0\n\t" + "jnz 1f\n\t" + "movl $-1,%0\n\t" + "1:\n\t" + : "=r" (r) : "rm" (x)); + return r + 1; +} +#define HAS_FLS_U32 +#endif + +#if defined(__x86_64) +static inline +unsigned int fls_u64(uint64_t x) +{ + long r; + + asm("bsrq %1,%0\n\t" + "jnz 1f\n\t" + "movq $-1,%0\n\t" + "1:\n\t" + : "=r" (r) : "rm" (x)); + return r + 1; +} +#define HAS_FLS_U64 +#endif + +#ifndef HAS_FLS_U64 +static __attribute__((unused)) +unsigned int fls_u64(uint64_t x) +{ + unsigned int r = 64; + + if (!x) + return 0; + + if (!(x & 0xFFFFFFFF00000000ULL)) { + x <<= 32; + r -= 32; + } + if (!(x & 0xFFFF000000000000ULL)) { + x <<= 16; + r -= 16; + } + if (!(x & 0xFF00000000000000ULL)) { + x <<= 8; + r -= 8; + } + if (!(x & 0xF000000000000000ULL)) { + x <<= 4; + r -= 4; + } + if (!(x & 0xC000000000000000ULL)) { + x <<= 2; + r -= 2; + } + if (!(x & 0x8000000000000000ULL)) { + x <<= 1; + r -= 1; + } + return r; +} +#endif + +#ifndef HAS_FLS_U32 +static __attribute__((unused)) +unsigned int fls_u32(uint32_t x) +{ + unsigned int r = 32; + + if (!x) + return 0; + if (!(x & 0xFFFF0000U)) { + x <<= 16; + r -= 16; + } + if (!(x & 0xFF000000U)) { + x <<= 8; + r -= 8; + } + if (!(x & 0xF0000000U)) { + x <<= 4; + r -= 4; + } + if (!(x & 0xC0000000U)) { + x <<= 2; + r -= 2; + } + if (!(x & 0x80000000U)) { + x <<= 1; + r -= 1; + } + return r; +} +#endif + +unsigned int fls_ulong(unsigned long x) +{ +#if (CAA_BITS_PER_lONG == 32) + return fls_u32(x); +#else + return fls_u64(x); +#endif +} + +int get_count_order_u32(uint32_t x) +{ + int order; -uint32_t log2_u32(uint32_t v) + order = fls_u32(x) - 1; + if (x & (x - 1)) + order++; + return order; +} + +int get_count_order_ulong(unsigned long x) { - uint32_t t, tt; + int order; - if ((tt = (v >> 16))) - return (t = (tt >> 8)) - ? 24 + LogTable256[t] - : 16 + LogTable256[tt]; - else - return (t = (v >> 8)) - ? 8 + LogTable256[t] - : LogTable256[v]; + order = fls_ulong(x) - 1; + if (x & (x - 1)) + order++; + return order; } static @@ -166,29 +285,44 @@ static void check_resize(struct rcu_ht *ht, struct rcu_table *t, uint32_t chain_len) { + if (chain_len > 100) + dbg_printf("rculfhash: WARNING: large chain length: %u.\n", + chain_len); if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) ht_resize_lazy(ht, t, - log2_u32(chain_len - CHAIN_LEN_TARGET)); + get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1))); } static struct rcu_ht_node *clear_flag(struct rcu_ht_node *node) { - return (struct rcu_ht_node *) (((unsigned long) node) & ~0x1); + return (struct rcu_ht_node *) (((unsigned long) node) & ~FLAGS_MASK); } static int is_removed(struct rcu_ht_node *node) { - return ((unsigned long) node) & 0x1; + return ((unsigned long) node) & REMOVED_FLAG; } static struct rcu_ht_node *flag_removed(struct rcu_ht_node *node) { - return (struct rcu_ht_node *) (((unsigned long) node) | 0x1); + return (struct rcu_ht_node *) (((unsigned long) node) | REMOVED_FLAG); } +static +int is_dummy(struct rcu_ht_node *node) +{ + return ((unsigned long) node) & DUMMY_FLAG; +} + +static +struct rcu_ht_node *flag_dummy(struct rcu_ht_node *node) +{ + return (struct rcu_ht_node *) (((unsigned long) node) | DUMMY_FLAG); +} + static unsigned long _uatomic_max(unsigned long *ptr, unsigned long v) { @@ -203,124 +337,205 @@ unsigned long _uatomic_max(unsigned long *ptr, unsigned long v) return v; } +/* + * Remove all logically deleted nodes from a bucket up to a certain node key. + */ static -void _ht_add(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node) +void _ht_gc_bucket(struct rcu_ht_node *dummy, struct rcu_ht_node *node) { - struct rcu_ht_node *iter_prev = NULL, *iter = NULL; + struct rcu_ht_node *iter_prev, *iter, *next, *new_next; - if (!t->size) - return; for (;;) { - uint32_t chain_len = 0; - - iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]); - assert(iter_prev); - assert(iter_prev->reverse_hash <= node->reverse_hash); + iter_prev = dummy; + /* We can always skip the dummy node initially */ + iter = rcu_dereference(iter_prev->p.next); + assert(iter_prev->p.reverse_hash <= node->p.reverse_hash); for (;;) { - iter = clear_flag(rcu_dereference(iter_prev->next)); - if (unlikely(!iter)) + if (unlikely(!clear_flag(iter))) + return; + if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash) + return; + next = rcu_dereference(clear_flag(iter)->p.next); + if (is_removed(next)) break; - if (iter->reverse_hash > node->reverse_hash) - break; - iter_prev = iter; - check_resize(ht, t, ++chain_len); + iter_prev = clear_flag(iter); + iter = next; } + assert(!is_removed(iter)); + if (is_dummy(iter)) + new_next = flag_dummy(clear_flag(next)); + else + new_next = clear_flag(next); + (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); + } +} + +static +struct rcu_ht_node *_ht_add(struct rcu_ht *ht, struct rcu_table *t, + struct rcu_ht_node *node, int unique, int dummy) +{ + struct rcu_ht_node *iter_prev, *iter, *next, *new_node, *new_next, + *dummy_node; + struct _rcu_ht_node *lookup; + unsigned long hash, index, order; + + if (!t->size) { + assert(dummy); + node->p.next = flag_dummy(NULL); + return node; /* Initial first add (head) */ + } + hash = bit_reverse_ulong(node->p.reverse_hash); + for (;;) { + uint32_t chain_len = 0; + /* - * add in iter_prev->next: TODO: check for helping - * delete, for lock-freedom... + * iter_prev points to the non-removed node prior to the + * insert location. */ - if (is_removed(iter)) - continue; - assert(node != iter); - node->next = iter; + index = hash & (t->size - 1); + order = get_count_order_ulong(index + 1); + lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)]; + iter_prev = (struct rcu_ht_node *) lookup; + /* We can always skip the dummy node initially */ + iter = rcu_dereference(iter_prev->p.next); + assert(iter_prev->p.reverse_hash <= node->p.reverse_hash); + for (;;) { + if (unlikely(!clear_flag(iter))) + goto insert; + if (clear_flag(iter)->p.reverse_hash > node->p.reverse_hash) + goto insert; + next = rcu_dereference(clear_flag(iter)->p.next); + if (is_removed(next)) + goto gc_node; + if (unique + && !is_dummy(next) + && !ht->compare_fct(node->key, node->key_len, + clear_flag(iter)->key, + clear_flag(iter)->key_len)) + return clear_flag(iter); + /* Only account for identical reverse hash once */ + if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash + && !is_dummy(next)) + check_resize(ht, t, ++chain_len); + iter_prev = clear_flag(iter); + iter = next; + } + insert: + assert(node != clear_flag(iter)); + assert(!is_removed(iter_prev)); assert(iter_prev != node); - if (uatomic_cmpxchg(&iter_prev->next, iter, node) != iter) - continue; - break; + if (!dummy) + node->p.next = clear_flag(iter); + else + node->p.next = flag_dummy(clear_flag(iter)); + if (is_dummy(iter)) + new_node = flag_dummy(node); + else + new_node = node; + if (uatomic_cmpxchg(&iter_prev->p.next, iter, + new_node) != iter) + continue; /* retry */ + else + goto gc_end; + gc_node: + assert(!is_removed(iter)); + if (is_dummy(iter)) + new_next = flag_dummy(clear_flag(next)); + else + new_next = clear_flag(next); + (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); + /* retry */ } +gc_end: + /* Garbage collect logically removed nodes in the bucket */ + index = hash & (t->size - 1); + order = get_count_order_ulong(index + 1); + lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)]; + dummy_node = (struct rcu_ht_node *) lookup; + _ht_gc_bucket(dummy_node, node); + return node; } static int _ht_remove(struct rcu_ht *ht, struct rcu_table *t, struct rcu_ht_node *node) { - struct rcu_ht_node *iter_prev, *iter, *next, *old; - unsigned long chain_len; - int found, ret = 0; + struct rcu_ht_node *dummy, *next, *old; + struct _rcu_ht_node *lookup; int flagged = 0; + unsigned long hash, index, order; -retry: - chain_len = 0; - found = 0; - iter_prev = rcu_dereference(t->tbl[node->hash & (t->size - 1)]); - assert(iter_prev); - assert(iter_prev->reverse_hash <= node->reverse_hash); - for (;;) { - iter = clear_flag(rcu_dereference(iter_prev->next)); - if (unlikely(!iter)) - break; - if (unlikely(iter->reverse_hash > node->reverse_hash)) - break; - if (iter == node) { - found = 1; - break; - } - iter_prev = iter; - } - if (!found) { - ret = -ENOENT; - goto end; - } - next = rcu_dereference(iter->next); - if (!flagged) { - if (is_removed(next)) { - ret = -ENOENT; + /* logically delete the node */ + old = rcu_dereference(node->p.next); + do { + next = old; + if (is_removed(next)) goto end; - } - /* set deletion flag */ - if ((old = uatomic_cmpxchg(&iter->next, next, - flag_removed(next))) != next) { - if (old == flag_removed(next)) { - ret = -ENOENT; - goto end; - } else { - goto retry; - } - } - flagged = 1; - } + assert(!is_dummy(next)); + old = uatomic_cmpxchg(&node->p.next, next, + flag_removed(next)); + } while (old != next); + + /* We performed the (logical) deletion. */ + flagged = 1; + /* - * Remove the element from the list. - * Retry if there has been a concurrent add before us. - * Retry if the prev node has been deleted. - * There cannot be a concurrent delete for our position, because - * we won the deletion flag cmpxchg. - * If there is a concurrent add after us, our deletion flag - * makes it busy-loop (FIXME: not lock-free). + * Ensure that the node is not visible to readers anymore: lookup for + * the node, and remove it (along with any other logically removed node) + * if found. */ - if (uatomic_cmpxchg(&iter_prev->next, iter, clear_flag(next)) != iter) - goto retry; + hash = bit_reverse_ulong(node->p.reverse_hash); + index = hash & (t->size - 1); + order = get_count_order_ulong(index + 1); + lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)]; + dummy = (struct rcu_ht_node *) lookup; + _ht_gc_bucket(dummy, node); end: - return ret; + /* + * Only the flagging action indicated that we (and no other) + * removed the node from the hash. + */ + if (flagged) { + assert(is_removed(rcu_dereference(node->p.next))); + return 0; + } else + return -ENOENT; } static void init_table(struct rcu_ht *ht, struct rcu_table *t, - unsigned long first, unsigned long len) -{ - unsigned long i, end; - - end = first + len; - for (i = first; i < end; i++) { - /* Update table size when power of two */ - if (i != 0 && !(i & (i - 1))) - t->size = i; - t->tbl[i] = calloc(1, sizeof(struct rcu_ht_node)); - t->tbl[i]->dummy = 1; - t->tbl[i]->hash = i; - t->tbl[i]->reverse_hash = bit_reverse_ulong(i); - _ht_add(ht, t, t->tbl[i]); + unsigned long first_order, unsigned long len_order) +{ + unsigned long i, end_order; + + dbg_printf("rculfhash: init table: first_order %lu end_order %lu\n", + first_order, first_order + len_order); + end_order = first_order + len_order; + t->size = !first_order ? 0 : (1UL << (first_order - 1)); + for (i = first_order; i < end_order; i++) { + unsigned long j, len; + + len = !i ? 1 : 1UL << (i - 1); + dbg_printf("rculfhash: init order %lu len: %lu\n", i, len); + t->tbl[i] = calloc(len, sizeof(struct _rcu_ht_node)); + for (j = 0; j < len; j++) { + dbg_printf("rculfhash: init entry: i %lu j %lu hash %lu\n", + i, j, !i ? 0 : (1UL << (i - 1)) + j); + struct rcu_ht_node *new_node = + (struct rcu_ht_node *) &t->tbl[i][j]; + new_node->p.reverse_hash = + bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j); + (void) _ht_add(ht, t, new_node, 0, 1); + if (CMM_LOAD_SHARED(ht->in_progress_destroy)) + break; + } + /* Update table size */ + t->size = !i ? 1 : (1UL << i); + dbg_printf("rculfhash: init new size: %lu\n", t->size); + if (CMM_LOAD_SHARED(ht->in_progress_destroy)) + break; } - t->resize_target = t->size = end; + t->resize_target = t->size; + t->resize_initiated = 0; } struct rcu_ht *ht_new(ht_hash_fct hash_fct, @@ -331,19 +546,22 @@ struct rcu_ht *ht_new(ht_hash_fct hash_fct, void (*func)(struct rcu_head *head))) { struct rcu_ht *ht; + unsigned long order; ht = calloc(1, sizeof(struct rcu_ht)); ht->hash_fct = hash_fct; ht->compare_fct = compare_fct; ht->hash_seed = hash_seed; ht->ht_call_rcu = ht_call_rcu; + ht->in_progress_resize = 0; /* this mutex should not nest in read-side C.S. */ pthread_mutex_init(&ht->resize_mutex, NULL); + order = get_count_order_ulong(max(init_size, 1)) + 1; ht->t = calloc(1, sizeof(struct rcu_table) - + (max(init_size, 1) * sizeof(struct rcu_ht_node *))); + + (order * sizeof(struct _rcu_ht_node *))); ht->t->size = 0; pthread_mutex_lock(&ht->resize_mutex); - init_table(ht, ht->t, 0, max(init_size, 1)); + init_table(ht, ht->t, 0, order); pthread_mutex_unlock(&ht->resize_mutex); return ht; } @@ -351,40 +569,61 @@ struct rcu_ht *ht_new(ht_hash_fct hash_fct, struct rcu_ht_node *ht_lookup(struct rcu_ht *ht, void *key, size_t key_len) { struct rcu_table *t; - struct rcu_ht_node *node; - unsigned long hash, reverse_hash; + struct rcu_ht_node *node, *next; + struct _rcu_ht_node *lookup; + unsigned long hash, reverse_hash, index, order; hash = ht->hash_fct(key, key_len, ht->hash_seed); reverse_hash = bit_reverse_ulong(hash); t = rcu_dereference(ht->t); - node = rcu_dereference(t->tbl[hash & (t->size - 1)]); + index = hash & (t->size - 1); + order = get_count_order_ulong(index + 1); + lookup = &t->tbl[order][index & ((1UL << (order - 1)) - 1)]; + dbg_printf("rculfhash: lookup hash %lu index %lu order %lu aridx %lu\n", + hash, index, order, index & ((1UL << (order - 1)) - 1)); + node = (struct rcu_ht_node *) lookup; for (;;) { if (unlikely(!node)) break; - if (unlikely(node->reverse_hash > reverse_hash)) { + if (unlikely(node->p.reverse_hash > reverse_hash)) { node = NULL; break; } - if (!ht->compare_fct(node->key, node->key_len, key, key_len)) { - if (unlikely(is_removed(rcu_dereference(node->next)))) - node = NULL; - break; + next = rcu_dereference(node->p.next); + if (likely(!is_removed(next)) + && !is_dummy(next) + && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) { + break; } - node = clear_flag(rcu_dereference(node->next)); + node = clear_flag(next); } + assert(!node || !is_dummy(rcu_dereference(node->p.next))); return node; } void ht_add(struct rcu_ht *ht, struct rcu_ht_node *node) { struct rcu_table *t; + unsigned long hash; + + hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); + node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); + + t = rcu_dereference(ht->t); + (void) _ht_add(ht, t, node, 0, 0); +} + +struct rcu_ht_node *ht_add_unique(struct rcu_ht *ht, struct rcu_ht_node *node) +{ + struct rcu_table *t; + unsigned long hash; - node->hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); - node->reverse_hash = bit_reverse_ulong((unsigned long) node->hash); + hash = ht->hash_fct(node->key, node->key_len, ht->hash_seed); + node->p.reverse_hash = bit_reverse_ulong((unsigned long) hash); t = rcu_dereference(ht->t); - _ht_add(ht, t, node); + return _ht_add(ht, t, node, 1, 0); } int ht_remove(struct rcu_ht *ht, struct rcu_ht_node *node) @@ -400,20 +639,31 @@ int ht_delete_dummy(struct rcu_ht *ht) { struct rcu_table *t; struct rcu_ht_node *node; - unsigned long i; + struct _rcu_ht_node *lookup; + unsigned long order, i; t = ht->t; /* Check that the table is empty */ - node = t->tbl[0]; + lookup = &t->tbl[0][0]; + node = (struct rcu_ht_node *) lookup; do { - if (!node->dummy) + node = clear_flag(node)->p.next; + if (!is_dummy(node)) return -EPERM; - node = node->next; - } while (node); + assert(!is_removed(node)); + } while (clear_flag(node)); /* Internal sanity check: all nodes left should be dummy */ - for (i = 0; i < t->size; i++) { - assert(t->tbl[i]->dummy); - free(t->tbl[i]); + for (order = 0; order < get_count_order_ulong(t->size) + 1; order++) { + unsigned long len; + + len = !order ? 1 : 1UL << (order - 1); + for (i = 0; i < len; i++) { + dbg_printf("rculfhash: delete order %lu i %lu hash %lu\n", + order, i, + bit_reverse_ulong(t->tbl[order][i].reverse_hash)); + assert(is_dummy(t->tbl[order][i].next)); + } + free(t->tbl[order]); } return 0; } @@ -426,6 +676,10 @@ int ht_destroy(struct rcu_ht *ht) { int ret; + /* Wait for in-flight resize operations to complete */ + CMM_STORE_SHARED(ht->in_progress_destroy, 1); + while (uatomic_read(&ht->in_progress_resize)) + poll(NULL, 0, 100); /* wait for 100ms */ ret = ht_delete_dummy(ht); if (ret) return ret; @@ -434,6 +688,36 @@ int ht_destroy(struct rcu_ht *ht) return ret; } +void ht_count_nodes(struct rcu_ht *ht, + unsigned long *count, + unsigned long *removed) +{ + struct rcu_table *t; + struct rcu_ht_node *node, *next; + struct _rcu_ht_node *lookup; + unsigned long nr_dummy = 0; + + *count = 0; + *removed = 0; + + t = rcu_dereference(ht->t); + /* Count non-dummy nodes in the table */ + lookup = &t->tbl[0][0]; + node = (struct rcu_ht_node *) lookup; + do { + next = rcu_dereference(node->p.next); + if (is_removed(next)) { + assert(!is_dummy(next)); + (*removed)++; + } else if (!is_dummy(next)) + (*count)++; + else + (nr_dummy)++; + node = clear_flag(next); + } while (node); + dbg_printf("rculfhash: number of dummy nodes: %lu\n", nr_dummy); +} + static void ht_free_table_cb(struct rcu_head *head) { @@ -446,23 +730,25 @@ void ht_free_table_cb(struct rcu_head *head) static void _do_ht_resize(struct rcu_ht *ht) { - unsigned long new_size, old_size; + unsigned long new_size, old_size, old_order, new_order; struct rcu_table *new_t, *old_t; old_t = ht->t; old_size = old_t->size; + old_order = get_count_order_ulong(old_size) + 1; new_size = CMM_LOAD_SHARED(old_t->resize_target); - dbg_printf("rculfhash: resize from %lu to %lu buckets\n", - old_size, new_size); if (old_size == new_size) return; + new_order = get_count_order_ulong(new_size) + 1; + printf("rculfhash: resize from %lu (order %lu) to %lu (order %lu) buckets\n", + old_size, old_order, new_size, new_order); new_t = malloc(sizeof(struct rcu_table) - + (new_size * sizeof(struct rcu_ht_node *))); + + (new_order * sizeof(struct _rcu_ht_node *))); assert(new_size > old_size); memcpy(&new_t->tbl, &old_t->tbl, - old_size * sizeof(struct rcu_ht_node *)); - init_table(ht, new_t, old_size, new_size - old_size); + old_order * sizeof(struct _rcu_ht_node *)); + init_table(ht, new_t, old_order, new_order - old_order); /* Changing table and size atomically wrt lookups */ rcu_assign_pointer(ht->t, new_t); ht->ht_call_rcu(&old_t->head, ht_free_table_cb); @@ -483,6 +769,7 @@ void ht_resize(struct rcu_ht *ht, int growth) target_size = resize_target_update(t, growth); if (t->size < target_size) { + CMM_STORE_SHARED(t->resize_initiated, 1); pthread_mutex_lock(&ht->resize_mutex); _do_ht_resize(ht); pthread_mutex_unlock(&ht->resize_mutex); @@ -500,6 +787,8 @@ void do_resize_cb(struct rcu_head *head) _do_ht_resize(ht); pthread_mutex_unlock(&ht->resize_mutex); free(work); + cmm_smp_mb(); /* finish resize before decrement */ + uatomic_dec(&ht->in_progress_resize); } static @@ -509,9 +798,12 @@ void ht_resize_lazy(struct rcu_ht *ht, struct rcu_table *t, int growth) unsigned long target_size; target_size = resize_target_update(t, growth); - if (t->size < target_size) { + if (!CMM_LOAD_SHARED(t->resize_initiated) && t->size < target_size) { + uatomic_inc(&ht->in_progress_resize); + cmm_smp_mb(); /* increment resize count before calling it */ work = malloc(sizeof(*work)); work->ht = ht; ht->ht_call_rcu(&work->head, do_resize_cb); + CMM_STORE_SHARED(t->resize_initiated, 1); } }