X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=0bcbb1e832a5ab41c4d4357c0dafa4ff87832db7;hp=0f36899371dc2d0958306023b78ae1c3834e92da;hb=4f6e90b73cb103d7d49b8b4838c5f48c3d15b02e;hpb=7801dadd3a4f6ae9e40b2c858e5f97a01897d7dc diff --git a/rculfhash.c b/rculfhash.c index 0f36899..0bcbb1e 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -91,12 +91,32 @@ * the "dummy node" tables. * - There is one dummy node table per hash index order. The size of * each dummy node table is half the number of hashes contained in - * this order. - * - call_rcu is used to garbage-collect the old order table. + * this order (except for order 0). + * - synchronzie_rcu is used to garbage-collect the old dummy node table. * - The per-order dummy node tables contain a compact version of the * hash table nodes. These tables are invariant after they are * populated into the hash table. - * + * + * Dummy node tables: + * + * hash table hash table the last all dummy node tables + * order size dummy node 0 1 2 3 4 5 6(index) + * table size + * 0 1 1 1 + * 1 2 1 1 1 + * 2 4 2 1 1 2 + * 3 8 4 1 1 2 4 + * 4 16 8 1 1 2 4 8 + * 5 32 16 1 1 2 4 8 16 + * 6 64 32 1 1 2 4 8 16 32 + * + * When growing/shrinking, we only focus on the last dummy node table + * which size is (!order ? 1 : (1 << (order -1))). + * + * Example for growing/shrinking: + * grow hash table from order 5 to 6: init the index=6 dummy node table + * shrink hash table from order 6 to 5: fini the index=6 dummy node table + * * A bit of ascii art explanation: * * Order index is the off-by-one compare to the actual power of 2 because @@ -119,12 +139,9 @@ * * order bits reverse * 0 0 000 000 - * | - * 1 | 1 001 100 <- <- - * | | | | - * 2 | | 2 010 010 | | + * 1 | 1 001 100 <- + * 2 | | 2 010 010 <- | * | | | 3 011 110 | <- | - * | | | | | | | * 3 -> | | | 4 100 001 | | * -> | | 5 101 101 | * -> | 6 110 011 @@ -854,12 +871,6 @@ void _cds_lfht_add(struct cds_lfht *ht, assert(!is_dummy(node)); assert(!is_removed(node)); - if (!size) { - assert(dummy); - assert(!unique_ret); - node->p.next = flag_dummy(get_end()); - return; /* Initial first add (head) */ - } lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash)); for (;;) { uint32_t chain_len = 0; @@ -877,22 +888,38 @@ void _cds_lfht_add(struct cds_lfht *ht, goto insert; if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)) goto insert; + /* dummy node is the first node of the identical-hash-value chain */ if (dummy && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) goto insert; + next = rcu_dereference(clear_flag(iter)->p.next); if (unlikely(is_removed(next))) goto gc_node; + + /* uniquely add */ if (unique_ret && !is_dummy(next) - && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash - && !ht->compare_fct(node->key, node->key_len, - clear_flag(iter)->key, - clear_flag(iter)->key_len)) { - unique_ret->node = clear_flag(iter); - unique_ret->next = next; + && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash) { + struct cds_lfht_iter d_iter = { .node = node, .next = iter, }; + + /* + * uniquely adding inserts the node as the first + * node of the identical-hash-value node chain. + * + * This semantic ensures no duplicated keys + * should ever be observable in the table + * (including observe one node by one node + * by forward iterations) + */ + cds_lfht_next_duplicate(ht, &d_iter); + if (!d_iter.node) + goto insert; + + *unique_ret = d_iter; return; } + /* Only account for identical reverse hash once */ if (iter_prev->p.reverse_hash != clear_flag(iter)->p.reverse_hash && !is_dummy(next)) @@ -945,10 +972,9 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, { struct cds_lfht_node *dummy, *next, *old; struct _cds_lfht_node *lookup; - int flagged = 0; if (!node) /* Return -ENOENT if asked to delete NULL node */ - goto end; + return -ENOENT; /* logically delete the node */ assert(!is_dummy(node)); @@ -959,7 +985,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, next = old; if (unlikely(is_removed(next))) - goto end; + return -ENOENT; if (dummy_removal) assert(is_dummy(next)); else @@ -967,9 +993,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, new_next = flag_removed(next); old = uatomic_cmpxchg(&node->p.next, next, new_next); } while (old != next); - /* We performed the (logical) deletion. */ - flagged = 1; /* * Ensure that the node is not visible to readers anymore: lookup for @@ -979,17 +1003,9 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, lookup = lookup_bucket(ht, size, bit_reverse_ulong(node->p.reverse_hash)); dummy = (struct cds_lfht_node *) lookup; _cds_lfht_gc_bucket(dummy, node); -end: - /* - * 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; - } + + assert(is_removed(rcu_dereference(node->p.next))); + return 0; } static @@ -1062,16 +1078,17 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i, { unsigned long j; + assert(i > 0); ht->cds_lfht_rcu_read_lock(); for (j = start; j < start + len; j++) { struct cds_lfht_node *new_node = (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j]; dbg_printf("init populate: i %lu j %lu hash %lu\n", - i, j, !i ? 0 : (1UL << (i - 1)) + j); + i, j, (1UL << (i - 1)) + j); new_node->p.reverse_hash = - bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j); - _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)), + bit_reverse_ulong((1UL << (i - 1)) + j); + _cds_lfht_add(ht, 1UL << (i - 1), new_node, NULL, 1); } ht->cds_lfht_rcu_read_unlock(); @@ -1093,21 +1110,21 @@ void init_table_populate(struct cds_lfht *ht, unsigned long i, static void init_table(struct cds_lfht *ht, - unsigned long first_order, unsigned long len_order) + unsigned long first_order, unsigned long last_order) { - unsigned long i, end_order; + unsigned long i; - dbg_printf("init table: first_order %lu end_order %lu\n", - first_order, first_order + len_order); - end_order = first_order + len_order; - for (i = first_order; i < end_order; i++) { + dbg_printf("init table: first_order %lu last_order %lu\n", + first_order, last_order); + assert(first_order > 0); + for (i = first_order; i <= last_order; i++) { unsigned long len; - len = !i ? 1 : 1UL << (i - 1); + len = 1UL << (i - 1); dbg_printf("init order %lu len: %lu\n", i, len); /* Stop expand if the resize target changes under us */ - if (CMM_LOAD_SHARED(ht->t.resize_target) < (!i ? 1 : (1UL << i))) + if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i)) break; ht->t.tbl[i] = calloc(1, len * sizeof(struct _cds_lfht_node)); @@ -1123,9 +1140,9 @@ void init_table(struct cds_lfht *ht, * Update table size. */ cmm_smp_wmb(); /* populate data before RCU size */ - CMM_STORE_SHARED(ht->t.size, !i ? 1 : (1UL << i)); + CMM_STORE_SHARED(ht->t.size, 1UL << i); - dbg_printf("init new size: %lu\n", !i ? 1 : (1UL << i)); + dbg_printf("init new size: %lu\n", 1UL << i); if (CMM_LOAD_SHARED(ht->in_progress_destroy)) break; } @@ -1162,17 +1179,17 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i, { unsigned long j; + assert(i > 0); ht->cds_lfht_rcu_read_lock(); for (j = start; j < start + len; j++) { struct cds_lfht_node *fini_node = (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j]; dbg_printf("remove entry: i %lu j %lu hash %lu\n", - i, j, !i ? 0 : (1UL << (i - 1)) + j); + i, j, (1UL << (i - 1)) + j); fini_node->p.reverse_hash = - bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j); - (void) _cds_lfht_del(ht, !i ? 0 : (1UL << (i - 1)), - fini_node, 1); + bit_reverse_ulong((1UL << (i - 1)) + j); + (void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1); } ht->cds_lfht_rcu_read_unlock(); } @@ -1193,19 +1210,18 @@ void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len) static void fini_table(struct cds_lfht *ht, - unsigned long first_order, unsigned long len_order) + unsigned long first_order, unsigned long last_order) { - long i, end_order; + long i; void *free_by_rcu = NULL; - dbg_printf("fini table: first_order %lu end_order %lu\n", - first_order, first_order + len_order); - end_order = first_order + len_order; + dbg_printf("fini table: first_order %lu last_order %lu\n", + first_order, last_order); assert(first_order > 0); - for (i = end_order - 1; i >= first_order; i--) { + for (i = last_order; i >= first_order; i--) { unsigned long len; - len = !i ? 1 : 1UL << (i - 1); + len = 1UL << (i - 1); dbg_printf("fini order %lu len: %lu\n", i, len); /* Stop shrink if the resize target changes under us */ @@ -1246,6 +1262,45 @@ void fini_table(struct cds_lfht *ht, } } +static +void cds_lfht_create_dummy(struct cds_lfht *ht, unsigned long size) +{ + struct _cds_lfht_node *prev, *node; + unsigned long order, len, i, j; + + ht->t.tbl[0] = calloc(1, sizeof(struct _cds_lfht_node)); + assert(ht->t.tbl[0]); + + dbg_printf("create dummy: order %lu index %lu hash %lu\n", 0, 0, 0); + ht->t.tbl[0]->nodes[0].next = flag_dummy(get_end()); + ht->t.tbl[0]->nodes[0].reverse_hash = 0; + + for (order = 1; order < get_count_order_ulong(size) + 1; order++) { + len = 1UL << (order - 1); + ht->t.tbl[order] = calloc(1, len * sizeof(struct _cds_lfht_node)); + assert(ht->t.tbl[order]); + + i = 0; + prev = ht->t.tbl[i]->nodes; + for (j = 0; j < len; j++) { + if (j & (j - 1)) { /* Between power of 2 */ + prev++; + } else if (j) { /* At each power of 2 */ + i++; + prev = ht->t.tbl[i]->nodes; + } + + node = &ht->t.tbl[order]->nodes[j]; + dbg_printf("create dummy: order %lu index %lu hash %lu\n", + order, j, j + len); + node->next = prev->next; + assert(is_dummy(node->next)); + node->reverse_hash = bit_reverse_ulong(j + len); + prev->next = flag_dummy((struct cds_lfht_node *)node); + } + } +} + struct cds_lfht *_cds_lfht_new(cds_lfht_hash_fct hash_fct, cds_lfht_compare_fct compare_fct, unsigned long hash_seed, @@ -1285,14 +1340,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, MIN_TABLE_SIZE)) + 1; ht->flags = flags; - ht->cds_lfht_rcu_thread_offline(); - pthread_mutex_lock(&ht->resize_mutex); - ht->t.resize_target = 1UL << (order - 1); - init_table(ht, 0, order); - pthread_mutex_unlock(&ht->resize_mutex); - ht->cds_lfht_rcu_thread_online(); + order = get_count_order_ulong(max(init_size, MIN_TABLE_SIZE)); + ht->t.resize_target = 1UL << order; + cds_lfht_create_dummy(ht, 1UL << order); + ht->t.size = 1UL << order; return ht; } @@ -1596,12 +1648,12 @@ void _do_cds_lfht_grow(struct cds_lfht *ht, { unsigned long old_order, new_order; - old_order = get_count_order_ulong(old_size) + 1; - new_order = get_count_order_ulong(new_size) + 1; + old_order = get_count_order_ulong(old_size); + new_order = get_count_order_ulong(new_size); dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n", old_size, old_order, new_size, new_order); assert(new_size > old_size); - init_table(ht, old_order, new_order - old_order); + init_table(ht, old_order + 1, new_order); } /* called with resize mutex held */ @@ -1612,14 +1664,14 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht, unsigned long old_order, new_order; 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; + old_order = get_count_order_ulong(old_size); + new_order = get_count_order_ulong(new_size); dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n", old_size, old_order, new_size, new_order); assert(new_size < old_size); /* Remove and unlink all dummy nodes to remove. */ - fini_table(ht, new_order, old_order - new_order); + fini_table(ht, new_order + 1, old_order); }