* - cds_lfht_first followed iteration with cds_lfht_next (and/or
* cds_lfht_next_duplicate, although less common).
*
- * We define "write" operations as any of cds_lfht_add,
+ * We define "write" operations as any of cds_lfht_add, cds_lfht_replace,
* cds_lfht_add_unique (success), cds_lfht_add_replace, cds_lfht_del.
*
* When cds_lfht_add_unique succeeds (returns the node passed as
return BitReverseTable256[v];
}
-static __attribute__((unused))
+#if (CAA_BITS_PER_LONG == 32)
+static
uint32_t bit_reverse_u32(uint32_t v)
{
return ((uint32_t) bit_reverse_u8(v) << 24) |
((uint32_t) bit_reverse_u8(v >> 16) << 8) |
((uint32_t) bit_reverse_u8(v >> 24));
}
-
-static __attribute__((unused))
+#else
+static
uint64_t bit_reverse_u64(uint64_t v)
{
return ((uint64_t) bit_reverse_u8(v) << 56) |
((uint64_t) bit_reverse_u8(v >> 48) << 8) |
((uint64_t) bit_reverse_u8(v >> 56));
}
+#endif
static
unsigned long bit_reverse_ulong(unsigned long v)
static
void alloc_split_items_count(struct cds_lfht *ht)
{
- struct ht_items_count *count;
-
if (nr_cpus_mask == -1) {
ht_init_nr_cpus_mask();
if (nr_cpus_mask < 0)
assert(split_count_mask >= 0);
if (ht->flags & CDS_LFHT_ACCOUNTING) {
- ht->split_count = calloc(split_count_mask + 1, sizeof(*count));
+ ht->split_count = calloc(split_count_mask + 1,
+ sizeof(struct ht_items_count));
assert(ht->split_count);
} else {
ht->split_count = NULL;
return ((unsigned long) node) & REMOVED_FLAG;
}
-static
-struct cds_lfht_node *flag_removed(struct cds_lfht_node *node)
-{
- return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG);
-}
-
static
int is_bucket(struct cds_lfht_node *node)
{
return (struct cds_lfht_node *) (((unsigned long) node) | REMOVAL_OWNER_FLAG);
}
+static
+struct cds_lfht_node *flag_removed_or_removal_owner(struct cds_lfht_node *node)
+{
+ return (struct cds_lfht_node *) (((unsigned long) node) | REMOVED_FLAG | REMOVAL_OWNER_FLAG);
+}
+
static
struct cds_lfht_node *get_end(void)
{
}
assert(old_next == clear_flag(old_next));
assert(new_node != old_next);
+ /*
+ * REMOVAL_OWNER flag is _NEVER_ set before the REMOVED
+ * flag. It is either set atomically at the same time
+ * (replace) or after (del).
+ */
+ assert(!is_removal_owner(old_next));
new_node->next = old_next;
/*
* Here is the whole trick for lock-free replace: we add
* the old node, but will not see the new one.
* This is a replacement of a node with another node
* that has the same value: we are therefore not
- * removing a value from the hash table.
+ * removing a value from the hash table. We set both the
+ * REMOVED and REMOVAL_OWNER flags atomically so we own
+ * the node after successful cmpxchg.
*/
ret_next = uatomic_cmpxchg(&old_node->next,
- old_next, flag_removed(new_node));
+ old_next, flag_removed_or_removal_owner(new_node));
if (ret_next == old_next)
break; /* We performed the replacement. */
old_next = ret_next;
if (caa_unlikely(is_removed(next)))
return -ENOENT;
assert(!is_bucket(next));
+ /*
+ * The del operation semantic guarantees a full memory barrier
+ * before the uatomic_or atomic commit of the deletion flag.
+ */
+ cmm_smp_mb__before_uatomic_or();
/*
* We set the REMOVED_FLAG unconditionally. Note that there may
* be more than one concurrent thread setting this flag.
int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node)
{
- unsigned long size, hash;
+ unsigned long size;
int ret;
size = rcu_dereference(ht->size);
ret = _cds_lfht_del(ht, size, node);
if (!ret) {
+ unsigned long hash;
+
hash = bit_reverse_ulong(node->reverse_hash);
ht_count_del(ht, size, hash);
}
/* Wait for in-flight resize operations to complete */
_CMM_STORE_SHARED(ht->in_progress_destroy, 1);
cmm_smp_mb(); /* Store destroy before load resize */
+ ht->flavor->thread_offline();
while (uatomic_read(&ht->in_progress_resize))
poll(NULL, 0, 100); /* wait for 100ms */
+ ht->flavor->thread_online();
ret = cds_lfht_delete_bucket(ht);
if (ret)
return ret;