From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755357Ab3AVTcj (ORCPT ); Tue, 22 Jan 2013 14:32:39 -0500 Received: from hrndva-omtalb.mail.rr.com ([71.74.56.122]:4215 "EHLO hrndva-omtalb.mail.rr.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753915Ab3AVTcg (ORCPT ); Tue, 22 Jan 2013 14:32:36 -0500 X-Authority-Analysis: v=2.0 cv=bJmU0YCZ c=1 sm=0 a=rXTBtCOcEpjy1lPqhTCpEQ==:17 a=mNMOxpOpBa8A:10 a=8XPjA_W9iWwA:10 a=5SG0PmZfjMsA:10 a=Q9fys5e9bTEA:10 a=meVymXHHAAAA:8 a=cA-augn98TgA:10 a=h-b-cD0aQrvUf5B23EYA:9 a=PUjeQqilurYA:10 a=rXTBtCOcEpjy1lPqhTCpEQ==:117 X-Cloudmark-Score: 0 X-Authenticated-User: X-Originating-IP: 74.67.115.198 Message-ID: <1358883152.21576.55.camel@gandalf.local.home> Subject: Re: [PATCH v5 01/45] percpu_rwlock: Introduce the global reader-writer lock backend From: Steven Rostedt To: "Srivatsa S. Bhat" Cc: tglx@linutronix.de, peterz@infradead.org, tj@kernel.org, oleg@redhat.com, paulmck@linux.vnet.ibm.com, rusty@rustcorp.com.au, mingo@kernel.org, akpm@linux-foundation.org, namhyung@kernel.org, wangyun@linux.vnet.ibm.com, xiaoguangrong@linux.vnet.ibm.com, rjw@sisk.pl, sbw@mit.edu, fweisbec@gmail.com, linux@arm.linux.org.uk, nikunj@linux.vnet.ibm.com, linux-pm@vger.kernel.org, linux-arch@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linuxppc-dev@lists.ozlabs.org, netdev@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org Date: Tue, 22 Jan 2013 14:32:32 -0500 In-Reply-To: <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> References: <20130122073210.13822.50434.stgit@srivatsabhat.in.ibm.com> <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> Content-Type: text/plain; charset="ISO-8859-15" X-Mailer: Evolution 3.4.4-1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: > A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer > locks can also lead to too many deadlock possibilities which can make it very > hard/impossible to use. This is explained in the example below, which helps > justify the need for a different algorithm to implement flexible Per-CPU > Reader-Writer locks. > > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > write_lock(&my_rwlock); > I thought global locks are now fair. That is, a reader will block if a writer is waiting. Hence, the above should deadlock on the current rwlock_t types. We need to fix those locations (or better yet, remove all rwlocks ;-) -- Steve From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from hrndva-omtalb.mail.rr.com (hrndva-omtalb.mail.rr.com [71.74.56.122]) by ozlabs.org (Postfix) with ESMTP id 51DD92C0082 for ; Wed, 23 Jan 2013 06:32:37 +1100 (EST) Message-ID: <1358883152.21576.55.camel@gandalf.local.home> Subject: Re: [PATCH v5 01/45] percpu_rwlock: Introduce the global reader-writer lock backend From: Steven Rostedt To: "Srivatsa S. Bhat" Date: Tue, 22 Jan 2013 14:32:32 -0500 In-Reply-To: <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> References: <20130122073210.13822.50434.stgit@srivatsabhat.in.ibm.com> <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> Content-Type: text/plain; charset="ISO-8859-15" Mime-Version: 1.0 Cc: linux-doc@vger.kernel.org, peterz@infradead.org, fweisbec@gmail.com, linux-kernel@vger.kernel.org, mingo@kernel.org, linux-arch@vger.kernel.org, linux@arm.linux.org.uk, xiaoguangrong@linux.vnet.ibm.com, wangyun@linux.vnet.ibm.com, paulmck@linux.vnet.ibm.com, nikunj@linux.vnet.ibm.com, linux-pm@vger.kernel.org, rusty@rustcorp.com.au, rjw@sisk.pl, namhyung@kernel.org, tglx@linutronix.de, linux-arm-kernel@lists.infradead.org, netdev@vger.kernel.org, oleg@redhat.com, sbw@mit.edu, tj@kernel.org, akpm@linux-foundation.org, linuxppc-dev@lists.ozlabs.org List-Id: Linux on PowerPC Developers Mail List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: > A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer > locks can also lead to too many deadlock possibilities which can make it very > hard/impossible to use. This is explained in the example below, which helps > justify the need for a different algorithm to implement flexible Per-CPU > Reader-Writer locks. > > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > write_lock(&my_rwlock); > I thought global locks are now fair. That is, a reader will block if a writer is waiting. Hence, the above should deadlock on the current rwlock_t types. We need to fix those locations (or better yet, remove all rwlocks ;-) -- Steve From mboxrd@z Thu Jan 1 00:00:00 1970 From: rostedt@goodmis.org (Steven Rostedt) Date: Tue, 22 Jan 2013 14:32:32 -0500 Subject: [PATCH v5 01/45] percpu_rwlock: Introduce the global reader-writer lock backend In-Reply-To: <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> References: <20130122073210.13822.50434.stgit@srivatsabhat.in.ibm.com> <20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com> Message-ID: <1358883152.21576.55.camel@gandalf.local.home> To: linux-arm-kernel@lists.infradead.org List-Id: linux-arm-kernel.lists.infradead.org On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: > A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer > locks can also lead to too many deadlock possibilities which can make it very > hard/impossible to use. This is explained in the example below, which helps > justify the need for a different algorithm to implement flexible Per-CPU > Reader-Writer locks. > > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > write_lock(&my_rwlock); > I thought global locks are now fair. That is, a reader will block if a writer is waiting. Hence, the above should deadlock on the current rwlock_t types. We need to fix those locations (or better yet, remove all rwlocks ;-) -- Steve