#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
#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)));
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.
{
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)
{
*/
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;
new_next = clear_flag(next);
(void) uatomic_cmpxchg(&iter_prev->p.next, iter, new_next);
}
+ return;
}
static
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);
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;
return -ENOENT;
}
-static
-void init_table_hash(struct cds_lfht *ht, unsigned long i,
- unsigned long len)
-{
- unsigned long j;
-
- for (j = 0; j < len; j++) {
- struct cds_lfht_node *new_node =
- (struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
-
- dbg_printf("init hash entry: i %lu j %lu hash %lu\n",
- i, j, !i ? 0 : (1UL << (i - 1)) + j);
- new_node->p.reverse_hash =
- bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
- if (CMM_LOAD_SHARED(ht->in_progress_destroy))
- break;
- }
-}
-
/*
* Holding RCU read lock to protect _cds_lfht_add against memory
* reclaim that could be performed by other call_rcu worker threads (ABA
* problem).
+ *
+ * TODO: when we reach a certain length, we can split this population phase over
+ * many worker threads, based on the number of CPUs available in the system.
+ * This should therefore take care of not having the expand lagging behind too
+ * many concurrent insertion threads by using the scheduler's ability to
+ * schedule dummy node population fairly with insertions.
*/
static
-void init_table_link(struct cds_lfht *ht, unsigned long i, unsigned long len)
+void init_table_populate(struct cds_lfht *ht, unsigned long i, unsigned long len)
{
unsigned long j;
struct cds_lfht_node *new_node =
(struct cds_lfht_node *) &ht->t.tbl[i]->nodes[j];
- dbg_printf("init link: i %lu j %lu hash %lu\n",
+ dbg_printf("init populate: i %lu j %lu hash %lu\n",
i, j, !i ? 0 : (1UL << (i - 1)) + j);
+ new_node->p.reverse_hash =
+ bit_reverse_ulong(!i ? 0 : (1UL << (i - 1)) + j);
(void) _cds_lfht_add(ht, !i ? 0 : (1UL << (i - 1)),
new_node, 0, 1);
if (CMM_LOAD_SHARED(ht->in_progress_destroy))
ht->t.tbl[i] = calloc(1, sizeof(struct rcu_level)
+ (len * sizeof(struct _cds_lfht_node)));
- /* Set all dummy nodes reverse hash values for a level */
- init_table_hash(ht, i, len);
-
/*
- * Link all dummy nodes into the table. Concurrent
- * add/remove are helping us.
+ * Set all dummy nodes reverse hash values for a level and
+ * link all dummy nodes into the table.
*/
- init_table_link(ht, i, len);
+ init_table_populate(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;
*
* Logical removal and garbage collection can therefore be done in batch or on a
* node-per-node basis, as long as the guarantee above holds.
+ *
+ * TODO: when we reach a certain length, we can split this removal over many
+ * worker threads, based on the number of CPUs available in the system. This
+ * should take care of not letting resize process lag behind too many concurrent
+ * updater threads actively inserting into the hash table.
*/
static
void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
}
}
-struct cds_lfht *cds_lfht_new(cds_lfht_hash_fct hash_fct,
+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,
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;
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;
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;
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;
}
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.
else
(nr_dummy)++;
node = clear_flag(next);
- } while (node);
+ } while (!is_end(node));
dbg_printf("number of dummy nodes: %lu\n", nr_dummy);
}
projects / urcu.git / blobdiff