linux-kernel - Re: Rcu synchronization of a list

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20160527102726.GN3924@linux.vnet.ibm.com>
Date:	Fri, 27 May 2016 03:27:26 -0700
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Nikolay Borisov <n.borisov.lkml@...il.com>
Cc:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	"Linux-Kernel@...r. Kernel. Org" <linux-kernel@...r.kernel.org>
Subject: Re: Rcu synchronization of a list

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