From db00ccc36e7fb04ce8044fb1be7964acd1de6ae0 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 19 Dec 2011 16:45:51 -0500 Subject: [PATCH] rculfhash: Relax atomicity guarantees required by removal operation The atomicity guarantees for the removal operation do not need to be as strict as a cmpxchg. Use a uatomic_set followed by a xchg on a newly introduced "REMOVAL_OWNER_FLAG" to perform removal. Signed-off-by: Mathieu Desnoyers --- rculfhash.c | 72 +++++++++++++++++++++++++++++++++++++----------- urcu/rculfhash.h | 6 ++-- 2 files changed, 59 insertions(+), 19 deletions(-) diff --git a/rculfhash.c b/rculfhash.c index e5db86c..5220cd5 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -201,7 +201,8 @@ */ #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 @@ -638,6 +639,18 @@ struct cds_lfht_node *flag_bucket(struct cds_lfht_node *node) 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) { @@ -778,6 +791,9 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long size, * 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)); @@ -916,7 +932,7 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, struct cds_lfht_node *node, int bucket_removal) { - 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; @@ -924,20 +940,28 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, /* 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; + if (bucket_removal) + assert(is_bucket(next)); + else + 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. */ /* @@ -949,7 +973,23 @@ int _cds_lfht_del(struct cds_lfht *ht, unsigned long size, _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 diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index de31526..647592b 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -39,8 +39,8 @@ extern "C" { * cds_lfht_node: Contains the next pointers and reverse-hash * value required for lookup and traversal of the hash table. * - * struct cds_lfht_node should be aligned on 4-bytes boundaries because - * the two lower bits are used as flags. + * struct cds_lfht_node should be aligned on 8-bytes boundaries because + * the three lower bits are used as flags. * * struct cds_lfht_node can be embedded into a structure (as a field). * caa_container_of() can be used to get the structure from the struct @@ -53,7 +53,7 @@ extern "C" { struct cds_lfht_node { struct cds_lfht_node *next; /* ptr | BUCKET_FLAG | REMOVED_FLAG */ unsigned long reverse_hash; -} __attribute__((aligned(4))); +} __attribute__((aligned(8))); /* cds_lfht_iter: Used to track state while traversing a hash chain. */ struct cds_lfht_iter { -- 2.34.1