Rcu synchronization of a list

Rcu synchronization of a list

[Nikolay Borisov]

Hello,

I'm currently dealing with a synchronization scheme which utilizes RCU
but I'm observing a race condition. So I have an rcu-enabled list, which
contains various entries. The add/delete paths of the list are protected
by a single spin_lock. I'm observing the following thing happening:

T1             		T2
1. init_count
			2. delete_group
3.incr_count

So 'init_count' checks the list for a particular entry under
rcu_read_lock and will either return the existing one if it finds it, or
create a new entry and insert it in the list with the modification
spin_lock held. incr_count essentially checks the list again and should
return the entry which init_count returned (either the newly created one
or the existing entry). However, what I'm observing is an assertion
which fires in incr_count because it can't find the entry. The only
place where the list is being deleted from is from delete_group.

Having such a scheme what is the correct way to provide synchronization,
it seems that op. 1 and 3 need to be atomic w.r.t to op2? Does this fall
outside of the scope of the RCU protection scheme?

Regards,
Nikolay

Re: Rcu synchronization of a list

[Paul E. McKenney]

On Fri, May 27, 2016 at 12:40:51PM +0300, Nikolay Borisov wrote:
> Hello,
> 
> I'm currently dealing with a synchronization scheme which utilizes RCU
> but I'm observing a race condition. So I have an rcu-enabled list, which
> contains various entries. The add/delete paths of the list are protected
> by a single spin_lock. I'm observing the following thing happening:
> 
> T1             		T2
> 1. init_count
> 			2. delete_group
> 3.incr_count
> 
> So 'init_count' checks the list for a particular entry under
> rcu_read_lock and will either return the existing one if it finds it, or
> create a new entry and insert it in the list with the modification
> spin_lock held. incr_count essentially checks the list again and should
> return the entry which init_count returned (either the newly created one
> or the existing entry). However, what I'm observing is an assertion
> which fires in incr_count because it can't find the entry. The only
> place where the list is being deleted from is from delete_group.
> 
> Having such a scheme what is the correct way to provide synchronization,
> it seems that op. 1 and 3 need to be atomic w.r.t to op2? Does this fall
> outside of the scope of the RCU protection scheme?

There are a number of ways of making this work.  The most common one is to
only look up a given RCU-protected structure once for a given usage, and
to confine all uses for a given lookup to be within a given RCU read-side
critical section.  In this approach, the incr_count() function would be
passed the pointer provided by init_count(), so that their would be no
second lookup operation.  There would also need to be an rcu_read_lock()
preceding the call to init_count() and the matching rcu_read_unlock()
would need to follow the call to incr_count().

Another approach would be for T1 to flag the entry, and then have
delete_group() refrain from removing flagged entries.

Yet another approach would be for T1 to link the entries of interest
into a secondary data structure, which delete_group() does not touch.
Of course, delete_group() would need to avoid freeing any entries that
are on this secondary data structure.

There are other approaches, but your choice will depend on what semantics
your are trying to provide.

							Thanx, Paul