- 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);