* Mathieu Desnoyers ([email protected]) wrote: > Hi, > > I just found a race in the replace vs del operations in rculfhash. This > would be introduced by commit:
Just to show that I am not making this up, I came up with a test-case to reproduce it: test_urcu_hash 0 2 20 -A -s -M 1 -N 1 -O 1 (2 threads, doing replace/del, with a hash table that has only a single key for all values). After just a couple of seconds, either the program hangs, or, more often, I get: *** glibc detected *** /media/truecrypt1/compudj/doc/userspace-rcu/tests/.libs/test_urcu_hash: malloc(): memory corruption (fast): 0x00007ffff3a29e25 *** Program received signal SIGSEGV, Segmentation fault. With my fix below, the problem disappears. I'll push the fix into the master branch right away. Thanks, Mathieu > > commit db00ccc36e7fb04ce8044fb1be7964acd1de6ae0 > Author: Mathieu Desnoyers <[email protected]> > Date: Mon Dec 19 16:45:51 2011 -0500 > > 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. > > Here is the race: > > Initially in hash table: A > > T0 T1 > replace A by B > del A > read A->next > -> check REMOVED flag, not set yet. > read A->next > -> check REMOVED flag, not set yet. > cmpxchg A->next to set REMOVED flag > -> cmpxchg succeeds > uatomic_or to set REMOVED flag > uatomic_xchg to atomically set the > REMOVAL_OWNER flag > -> first to set the flag. > Replace returns node -> free(A) Del success -> free(A) > > With this race, we have a double-free. > > The problem with the replace code is that it does not set the > "REMOVAL_OWNER" flag. Here is the fix I propose for this bug: > > diff --git a/rculfhash.c b/rculfhash.c > index b26a690..e9cf062 100644 > --- a/rculfhash.c > +++ b/rculfhash.c > @@ -735,12 +735,6 @@ int is_removed(struct cds_lfht_node *node) > } > > 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 ((unsigned long) node) & BUCKET_FLAG; > @@ -765,6 +759,12 @@ struct cds_lfht_node *flag_removal_owner(struct > cds_lfht_node *node) > } > > 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) > { > return (struct cds_lfht_node *) END_VALUE; > @@ -894,6 +894,12 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned long > size, > } > 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 > @@ -906,10 +912,12 @@ int _cds_lfht_replace(struct cds_lfht *ht, unsigned > long size, > * 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; > > Thoughts ? > > Thanks, > > Mathieu > > -- > Mathieu Desnoyers > Operating System Efficiency R&D Consultant > EfficiOS Inc. > http://www.efficios.com > > _______________________________________________ > lttng-dev mailing list > [email protected] > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ lttng-dev mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
