*/
#define REMOVED_FLAG (1UL << 0)
#define BUCKET_FLAG (1UL << 1)
-#define FLAGS_MASK ((1UL << 2) - 1)
+#define REMOVAL_OWNER_FLAG (1UL << 2)
+#define FLAGS_MASK ((1UL << 3) - 1)
/* Value of the end pointer. Should not interact with flags. */
#define END_VALUE NULL
return (struct cds_lfht_node *) (((unsigned long) node) | BUCKET_FLAG);
}
+static
+int is_removal_owner(struct cds_lfht_node *node)
+{
+ return ((unsigned long) node) & REMOVAL_OWNER_FLAG;
+}
+
+static
+struct cds_lfht_node *flag_removal_owner(struct cds_lfht_node *node)
+{
+ return (struct cds_lfht_node *) (((unsigned long) node) | REMOVAL_OWNER_FLAG);
+}
+
static
struct cds_lfht_node *get_end(void)
{
new_next = clear_flag(next);
(void) uatomic_cmpxchg(&iter_prev->next, iter, new_next);
}
- return;
}
static
* next pointer, they will either skip the old node due
* to the removal flag and see the new node, or use
* 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.
*/
ret_next = uatomic_cmpxchg(&old_node->next,
old_next, flag_removed(new_node));
static
int _cds_lfht_del(struct cds_lfht *ht, unsigned long size,
- struct cds_lfht_node *node,
- int bucket_removal)
+ struct cds_lfht_node *node)
{
- struct cds_lfht_node *bucket, *next, *old;
+ struct cds_lfht_node *bucket, *next;
if (!node) /* Return -ENOENT if asked to delete NULL node */
return -ENOENT;
/* logically delete the node */
assert(!is_bucket(node));
assert(!is_removed(node));
- old = rcu_dereference(node->next);
- do {
- struct cds_lfht_node *new_next;
+ assert(!is_removal_owner(node));
- next = old;
- if (caa_unlikely(is_removed(next)))
- return -ENOENT;
- if (bucket_removal)
- assert(is_bucket(next));
- else
- assert(!is_bucket(next));
- new_next = flag_removed(next);
- old = uatomic_cmpxchg(&node->next, next, new_next);
- } while (old != next);
+ /*
+ * We are first checking if the node had previously been
+ * logically removed (this check is not atomic with setting the
+ * logical removal flag). Return -ENOENT if the node had
+ * previously been removed.
+ */
+ next = rcu_dereference(node->next);
+ if (caa_unlikely(is_removed(next)))
+ return -ENOENT;
+ assert(!is_bucket(next));
+ /*
+ * We set the REMOVED_FLAG unconditionally. Note that there may
+ * be more than one concurrent thread setting this flag.
+ * Knowing which wins the race will be known after the garbage
+ * collection phase, stay tuned!
+ */
+ uatomic_or(&node->next, REMOVED_FLAG);
/* We performed the (logical) deletion. */
/*
_cds_lfht_gc_bucket(bucket, node);
assert(is_removed(rcu_dereference(node->next)));
- return 0;
+ /*
+ * Last phase: atomically exchange node->next with a version
+ * having "REMOVAL_OWNER_FLAG" set. If the returned node->next
+ * pointer did _not_ have "REMOVAL_OWNER_FLAG" set, we now own
+ * the node and win the removal race.
+ * It is interesting to note that all "add" paths are forbidden
+ * to change the next pointer starting from the point where the
+ * REMOVED_FLAG is set, so here using a read, followed by a
+ * xchg() suffice to guarantee that the xchg() will ever only
+ * set the "REMOVAL_OWNER_FLAG" (or change nothing if the flag
+ * was already set).
+ */
+ if (!is_removal_owner(uatomic_xchg(&node->next,
+ flag_removal_owner(node->next))))
+ return 0;
+ else
+ return -ENOENT;
}
static
assert(i > MIN_TABLE_ORDER);
ht->flavor->read_lock();
for (j = size + start; j < size + start + len; j++) {
- struct cds_lfht_node *fini_node = bucket_at(ht, j);
+ struct cds_lfht_node *fini_bucket = bucket_at(ht, j);
+ struct cds_lfht_node *parent_bucket = bucket_at(ht, j - size);
assert(j >= size && j < (size << 1));
dbg_printf("remove entry: order %lu index %lu hash %lu\n",
i, j, j);
- fini_node->reverse_hash = bit_reverse_ulong(j);
- (void) _cds_lfht_del(ht, size, fini_node, 1);
+ /* Set the REMOVED_FLAG to freeze the ->next for gc */
+ uatomic_or(&fini_bucket->next, REMOVED_FLAG);
+ _cds_lfht_gc_bucket(parent_bucket, fini_bucket);
}
ht->flavor->read_unlock();
}
int ret;
size = rcu_dereference(ht->size);
- ret = _cds_lfht_del(ht, size, iter->node, 0);
+ ret = _cds_lfht_del(ht, size, iter->node);
if (!ret) {
hash = bit_reverse_ulong(iter->node->reverse_hash);
ht_count_del(ht, size, hash);
projects / urcu.git / blobdiff