From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751868AbcE0K1n (ORCPT ); Fri, 27 May 2016 06:27:43 -0400 Received: from e33.co.us.ibm.com ([32.97.110.151]:42883 "EHLO e33.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751063AbcE0K1l (ORCPT ); Fri, 27 May 2016 06:27:41 -0400 X-IBM-Helo: d03dlp01.boulder.ibm.com X-IBM-MailFrom: paulmck@linux.vnet.ibm.com X-IBM-RcptTo: linux-kernel@vger.kernel.org Date: Fri, 27 May 2016 03:27:26 -0700 From: "Paul E. McKenney" To: Nikolay Borisov Cc: Mathieu Desnoyers , "Linux-Kernel@Vger. Kernel. Org" Subject: Re: Rcu synchronization of a list Message-ID: <20160527102726.GN3924@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <57481623.9060003@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <57481623.9060003@gmail.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 16052710-0009-0000-0000-000037C6524A X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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