X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rculfhash.c;h=08d024c10996833462c94e1ea96162f609502195;hb=68ec5c872d091abdc5aa52b1a661142e490f93c9;hp=1391b6bb630102c18138ffe953e745e806808d62;hpb=7fb6f7638628c96521849489b11eaceb473f280b;p=urcu.git diff --git a/rculfhash.c b/rculfhash.c index 1391b6b..08d024c 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -167,14 +167,9 @@ #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 the minimum table size. */ -#define MIN_TABLE_SIZE 128 +#define MIN_TABLE_SIZE 1 #if (CAA_BITS_PER_LONG == 32) #define MAX_TABLE_ORDER 32 @@ -199,6 +194,9 @@ #define DUMMY_FLAG (1UL << 1) #define FLAGS_MASK ((1UL << 2) - 1) +/* Value of the end pointer. Should not interact with flags. */ +#define END_VALUE NULL + struct ht_items_count { unsigned long add, remove; } __attribute__((aligned(CAA_CACHE_LINE_SIZE))); @@ -246,6 +244,12 @@ struct rcu_resize_work { struct cds_lfht *ht; }; +static +struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, + unsigned long size, + struct cds_lfht_node *node, + int unique, int dummy); + /* * Algorithm to reverse bits in a word by lookup table, extended to * 64-bit words. @@ -651,7 +655,19 @@ struct cds_lfht_node *flag_dummy(struct cds_lfht_node *node) { return (struct cds_lfht_node *) (((unsigned long) node) | DUMMY_FLAG); } - + +static +struct cds_lfht_node *get_end(void) +{ + return (struct cds_lfht_node *) END_VALUE; +} + +static +int is_end(struct cds_lfht_node *node) +{ + return clear_flag(node) == (struct cds_lfht_node *) END_VALUE; +} + static unsigned long _uatomic_max(unsigned long *ptr, unsigned long v) { @@ -699,7 +715,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node */ assert(dummy != node); for (;;) { - if (unlikely(!clear_flag(iter))) + if (unlikely(is_end(iter))) return; if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)) return; @@ -716,6 +732,7 @@ void _cds_lfht_gc_bucket(struct cds_lfht_node *dummy, struct cds_lfht_node *node new_next = clear_flag(next); (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); } + return; } static @@ -733,7 +750,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, assert(!is_removed(node)); if (!size) { assert(dummy); - node->p.next = flag_dummy(NULL); + node->p.next = flag_dummy(get_end()); return node; /* Initial first add (head) */ } hash = bit_reverse_ulong(node->p.reverse_hash); @@ -752,7 +769,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, iter = rcu_dereference(iter_prev->p.next); assert(iter_prev->p.reverse_hash <= node->p.reverse_hash); for (;;) { - if (unlikely(!clear_flag(iter))) + if (unlikely(is_end(iter))) goto insert; if (likely(clear_flag(iter)->p.reverse_hash > node->p.reverse_hash)) goto insert; @@ -796,6 +813,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht, new_next = flag_dummy(clear_flag(next)); else new_next = clear_flag(next); + assert(new_next != NULL); (void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next); /* retry */ } @@ -831,6 +849,7 @@ int _cds_lfht_remove(struct cds_lfht *ht, unsigned long size, assert(is_dummy(next)); else assert(!is_dummy(next)); + assert(next != NULL); old = uatomic_cmpxchg(&node->p.next, next, flag_removed(next)); } while (old != next); @@ -940,11 +959,11 @@ void init_table(struct cds_lfht *ht, init_table_link(ht, i, len); /* - * Update table size (after init for now, because no - * concurrent updater help (TODO)). + * Update table size. */ cmm_smp_wmb(); /* populate data before RCU size */ CMM_STORE_SHARED(ht->t.size, !i ? 1 : (1UL << i)); + dbg_printf("init new size: %lu\n", !i ? 1 : (1UL << i)); if (CMM_LOAD_SHARED(ht->in_progress_destroy)) break; @@ -1087,7 +1106,7 @@ struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct, struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len) { - struct cds_lfht_node *node, *next; + struct cds_lfht_node *node, *next, *dummy_node; struct _cds_lfht_node *lookup; unsigned long hash, reverse_hash, index, order, size; @@ -1100,10 +1119,15 @@ struct cds_lfht_node *cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key lookup = &ht->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 & (!order ? 0 : ((1UL << (order - 1)) - 1))); - node = (struct cds_lfht_node *) lookup; + dummy_node = (struct cds_lfht_node *) lookup; + /* We can always skip the dummy node initially */ + node = rcu_dereference(dummy_node->p.next); + node = clear_flag(node); for (;;) { - if (unlikely(!node)) + if (unlikely(is_end(node))) { + node = NULL; break; + } if (unlikely(node->p.reverse_hash > reverse_hash)) { node = NULL; break; @@ -1135,8 +1159,10 @@ struct cds_lfht_node *cds_lfht_next(struct cds_lfht *ht, node = clear_flag(next); for (;;) { - if (unlikely(!node)) + if (unlikely(is_end(node))) { + node = NULL; break; + } if (unlikely(node->p.reverse_hash > reverse_hash)) { node = NULL; break; @@ -1176,7 +1202,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, size = rcu_dereference(ht->t.size); ret = _cds_lfht_add(ht, size, node, 1, 0); - if (ret != node) + if (ret == node) ht_count_add(ht, size); return ret; } @@ -1208,7 +1234,7 @@ int cds_lfht_delete_dummy(struct cds_lfht *ht) if (!is_dummy(node)) return -EPERM; assert(!is_removed(node)); - } while (clear_flag(node)); + } while (!is_end(node)); /* * size accessed without rcu_dereference because hash table is * being destroyed. @@ -1274,7 +1300,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht, else (nr_dummy)++; node = clear_flag(next); - } while (node); + } while (!is_end(node)); dbg_printf("number of dummy nodes: %lu\n", nr_dummy); }