X-Git-Url: https://git.liburcu.org/?a=blobdiff_plain;f=rculfhash.c;h=0c153982a1aac87cf0b785ecc8fe93fcec27fafa;hb=151e7a93d1cb77c3f7c78370ce1eee2c6a49e690;hp=cd60f5f4db8e7409668b3598ec073fdff5ce5752;hpb=1475579ca651164ea74eb0c9f727baad991098af;p=urcu.git diff --git a/rculfhash.c b/rculfhash.c index cd60f5f..0c15398 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -120,11 +120,11 @@ * order bits reverse * 0 0 000 000 * | - * 1 | 1 001 100 <- - * | | | - * 2 | | 2 010 010 | - * | | | 3 011 110 <- | - * | | | | | | + * 1 | 1 001 100 <- <- + * | | | | + * 2 | | 2 010 010 | | + * | | | 3 011 110 | <- | + * | | | | | | | * 3 -> | | | 4 100 001 | | * -> | | 5 101 101 | * -> | 6 110 011 @@ -166,6 +166,16 @@ #define CHAIN_LEN_TARGET 1 #define CHAIN_LEN_RESIZE_THRESHOLD 3 +/* + * Define the minimum table size. Protects against hash table resize overload + * when too many entries are added quickly before the resize can complete. + * This is especially the case if the table could be shrinked to a size of 1. + * TODO: we might want to make the add/remove operations help the resize to + * add or remove dummy nodes when a resize is ongoing to ensure upper-bound on + * chain length. + */ +#define MIN_TABLE_SIZE 128 + #ifndef max #define max(a, b) ((a) > (b) ? (a) : (b)) #endif @@ -201,6 +211,7 @@ struct cds_lfht { cds_lfht_hash_fct hash_fct; cds_lfht_compare_fct compare_fct; unsigned long hash_seed; + int flags; pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */ unsigned int in_progress_resize, in_progress_destroy; void (*cds_lfht_call_rcu)(struct rcu_head *head, @@ -567,6 +578,8 @@ void check_resize(struct cds_lfht *ht, struct rcu_table *t, { unsigned long count; + if (!(ht->flags & CDS_LFHT_AUTO_RESIZE)) + return; count = uatomic_read(&ht->count); /* * Use bucket-local length for small table expand and for @@ -699,7 +712,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, struct rcu_table *t, */ index = hash & (t->size - 1); order = get_count_order_ulong(index + 1); - lookup = &t->tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)]; + lookup = &t->tbl[order]->nodes[index & ((!order ? 0 : (1UL << (order - 1))) - 1)]; iter_prev = (struct cds_lfht_node *) lookup; /* We can always skip the dummy node initially */ iter = rcu_dereference(iter_prev->p.next); @@ -755,7 +768,7 @@ 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]->nodes[index & ((1UL << (order - 1)) - 1)]; + lookup = &t->tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; dummy_node = (struct cds_lfht_node *) lookup; _cds_lfht_gc_bucket(dummy_node, node); return node; @@ -796,18 +809,10 @@ int _cds_lfht_remove(struct cds_lfht *ht, struct rcu_table *t, * if found. */ hash = bit_reverse_ulong(node->p.reverse_hash); - /* - * When removing a dummy node, we need to consider the lower - * order table, so we don't end up looking up the dummy nodes we - * are currently removing. - */ - - if (dummy_removal) - index = hash & ((t->size >> 1) - 1); - else - index = hash & (t->size - 1); + assert(t->size > 0); + index = hash & (t->size - 1); order = get_count_order_ulong(index + 1); - lookup = &t->tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)]; + lookup = &t->tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1)) - 1))]; dummy = (struct cds_lfht_node *) lookup; _cds_lfht_gc_bucket(dummy, node); end: @@ -877,6 +882,8 @@ void fini_table(struct cds_lfht *ht, struct rcu_table *t, len = !i ? 1 : 1UL << (i - 1); dbg_printf("fini order %lu len: %lu\n", i, len); + /* Update table size */ + t->size = 1UL << (i - 1); /* Unlink */ for (j = 0; j < len; j++) { struct cds_lfht_node *new_node = @@ -891,8 +898,6 @@ void fini_table(struct cds_lfht *ht, struct rcu_table *t, break; } ht->cds_lfht_call_rcu(&t->tbl[i]->head, cds_lfht_free_level); - /* Update table size */ - t->size = (i == 1) ? 0 : 1UL << (i - 2); dbg_printf("fini new size: %lu\n", t->size); if (CMM_LOAD_SHARED(ht->in_progress_destroy)) break; @@ -905,6 +910,7 @@ struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct, cds_lfht_compare_fct compare_fct, unsigned long hash_seed, unsigned long init_size, + int flags, void (*cds_lfht_call_rcu)(struct rcu_head *head, void (*func)(struct rcu_head *head)), void (*cds_lfht_synchronize_rcu)(void)) @@ -925,10 +931,11 @@ struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct, ht->percpu_count = alloc_per_cpu_items_count(); /* 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; + order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE)) + 1; ht->t = calloc(1, sizeof(struct cds_lfht) + (order * sizeof(struct rcu_level *))); ht->t->size = 0; + ht->flags = flags; pthread_mutex_lock(&ht->resize_mutex); init_table(ht, ht->t, 0, order); pthread_mutex_unlock(&ht->resize_mutex); @@ -948,9 +955,9 @@ struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key t = rcu_dereference(ht->t); index = hash & (t->size - 1); order = get_count_order_ulong(index + 1); - lookup = &t->tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)]; + lookup = &t->tbl[order]->nodes[index & (!order ? 0 : ((1UL << (order - 1))) - 1)]; dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n", - hash, index, order, index & ((1UL << (order - 1)) - 1)); + hash, index, order, index & (!order ? 0 : ((1UL << (order - 1)) - 1))); node = (struct cds_lfht_node *) lookup; for (;;) { if (unlikely(!node)) @@ -1162,7 +1169,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht, struct rcu_table *old_t, unsigned long old_order, new_order; struct rcu_table *new_t; - new_size = max(new_size, 1); + new_size = max(new_size, MIN_TABLE_SIZE); old_order = get_count_order_ulong(old_size) + 1; new_order = get_count_order_ulong(new_size) + 1; printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n", @@ -1219,19 +1226,18 @@ unsigned long resize_target_update(struct rcu_table *t, } static -unsigned long resize_target_update_count(struct rcu_table *t, - unsigned long count) +void resize_target_update_count(struct rcu_table *t, + unsigned long count) { - count = max(count, 1); - return uatomic_set(&t->resize_target, count); + count = max(count, MIN_TABLE_SIZE); + uatomic_set(&t->resize_target, count); } void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size) { struct rcu_table *t = rcu_dereference(ht->t); - unsigned long target_size; - target_size = resize_target_update_count(t, new_size); + resize_target_update_count(t, new_size); CMM_STORE_SHARED(t->resize_initiated, 1); pthread_mutex_lock(&ht->resize_mutex); _do_cds_lfht_resize(ht); @@ -1277,9 +1283,10 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, struct rcu_table *t, unsigned long count) { struct rcu_resize_work *work; - unsigned long target_size; - target_size = resize_target_update_count(t, count); + if (!(ht->flags & CDS_LFHT_AUTO_RESIZE)) + return; + resize_target_update_count(t, count); if (!CMM_LOAD_SHARED(t->resize_initiated)) { uatomic_inc(&ht->in_progress_resize); cmm_smp_mb(); /* increment resize count before calling it */