From mboxrd@z Thu Jan 1 00:00:00 1970 From: Raghavendra K T Subject: Re: [PATCH RFC 1/2] qspinlock: Introducing a 4-byte queue spinlock implementation Date: Thu, 01 Aug 2013 15:41:33 +0530 Message-ID: <51FA3455.1000607@linux.vnet.ibm.com> References: <1375324631-32868-1-git-send-email-Waiman.Long@hp.com> <1375324631-32868-2-git-send-email-Waiman.Long@hp.com> <20130801094029.GK3008@twins.programming.kicks-ass.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Return-path: Received: from e23smtp08.au.ibm.com ([202.81.31.141]:54324 "EHLO e23smtp08.au.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751418Ab3HAKFf (ORCPT ); Thu, 1 Aug 2013 06:05:35 -0400 Received: from /spool/local by e23smtp08.au.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 1 Aug 2013 20:02:19 +1000 In-Reply-To: <20130801094029.GK3008@twins.programming.kicks-ass.net> Sender: linux-arch-owner@vger.kernel.org List-ID: To: Peter Zijlstra Cc: Waiman Long , Thomas Gleixner , Ingo Molnar , "H. Peter Anvin" , Arnd Bergmann , linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, Steven Rostedt , Andrew Morton , Richard Weinberger , Catalin Marinas , Greg Kroah-Hartman , Matt Fleming , Herbert Xu , Akinobu Mita , Rusty Russell , Michel Lespinasse , Andi Kleen , Rik van Riel , "Paul E. McKenney" , Linus Torvalds , George Spelvin , Harvey Harrison On 08/01/2013 03:10 PM, Peter Zijlstra wrote: > On Wed, Jul 31, 2013 at 10:37:10PM -0400, Waiman Long wrote: > > OK, so over-all I rather like the thing. It might be good to include a > link to some MCS lock description, sadly wikipedia doesn't have an > article on the concept :/ > > http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf > > That seems like nice (short-ish) write-up of the general algorithm. > >> +typedef struct qspinlock { >> + union { >> + struct { >> + u8 locked; /* Bit lock */ >> + u8 reserved; >> + u16 qcode; /* Wait queue code */ >> + }; >> + u32 qlock; >> + }; >> +} arch_spinlock_t; > >> +static __always_inline void queue_spin_unlock(struct qspinlock *lock) >> +{ >> + barrier(); >> + ACCESS_ONCE(lock->locked) = 0; > > Its always good to add comments with barriers.. > >> + smp_wmb(); >> +} > >> +/* >> + * The queue node structure >> + */ >> +struct qnode { >> + struct qnode *next; >> + u8 wait; /* Waiting flag */ >> + u8 used; /* Used flag */ >> +#ifdef CONFIG_DEBUG_SPINLOCK >> + u16 cpu_nr; /* CPU number */ >> + void *lock; /* Lock address */ >> +#endif >> +}; >> + >> +/* >> + * The 16-bit wait queue code is divided into the following 2 fields: >> + * Bits 0-1 : queue node index >> + * Bits 2-15: cpu number + 1 >> + * >> + * The current implementation will allow a maximum of (1<<14)-1 = 16383 CPUs. > > I haven't yet read far enough to figure out why you need the -1 thing, > but effectively you're restricted to 15k due to this. > It is exactly 16k-1 not 15k That is because CPU_CODE of 1 to 16k represents cpu 0..16k-1 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from e23smtp08.au.ibm.com ([202.81.31.141]:54324 "EHLO e23smtp08.au.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751418Ab3HAKFf (ORCPT ); Thu, 1 Aug 2013 06:05:35 -0400 Received: from /spool/local by e23smtp08.au.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 1 Aug 2013 20:02:19 +1000 Message-ID: <51FA3455.1000607@linux.vnet.ibm.com> Date: Thu, 01 Aug 2013 15:41:33 +0530 From: Raghavendra K T MIME-Version: 1.0 Subject: Re: [PATCH RFC 1/2] qspinlock: Introducing a 4-byte queue spinlock implementation References: <1375324631-32868-1-git-send-email-Waiman.Long@hp.com> <1375324631-32868-2-git-send-email-Waiman.Long@hp.com> <20130801094029.GK3008@twins.programming.kicks-ass.net> In-Reply-To: <20130801094029.GK3008@twins.programming.kicks-ass.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-arch-owner@vger.kernel.org List-ID: To: Peter Zijlstra Cc: Waiman Long , Thomas Gleixner , Ingo Molnar , "H. Peter Anvin" , Arnd Bergmann , linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, Steven Rostedt , Andrew Morton , Richard Weinberger , Catalin Marinas , Greg Kroah-Hartman , Matt Fleming , Herbert Xu , Akinobu Mita , Rusty Russell , Michel Lespinasse , Andi Kleen , Rik van Riel , "Paul E. McKenney" , Linus Torvalds , George Spelvin , Harvey Harrison , "Chandramouleeswaran, Aswin" , "Norton, Scott J" Message-ID: <20130801101133.c1DXoiBw8r3do_Zbd0S9-eya6AjKTRWA_NXZh42xbOE@z> On 08/01/2013 03:10 PM, Peter Zijlstra wrote: > On Wed, Jul 31, 2013 at 10:37:10PM -0400, Waiman Long wrote: > > OK, so over-all I rather like the thing. It might be good to include a > link to some MCS lock description, sadly wikipedia doesn't have an > article on the concept :/ > > http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf > > That seems like nice (short-ish) write-up of the general algorithm. > >> +typedef struct qspinlock { >> + union { >> + struct { >> + u8 locked; /* Bit lock */ >> + u8 reserved; >> + u16 qcode; /* Wait queue code */ >> + }; >> + u32 qlock; >> + }; >> +} arch_spinlock_t; > >> +static __always_inline void queue_spin_unlock(struct qspinlock *lock) >> +{ >> + barrier(); >> + ACCESS_ONCE(lock->locked) = 0; > > Its always good to add comments with barriers.. > >> + smp_wmb(); >> +} > >> +/* >> + * The queue node structure >> + */ >> +struct qnode { >> + struct qnode *next; >> + u8 wait; /* Waiting flag */ >> + u8 used; /* Used flag */ >> +#ifdef CONFIG_DEBUG_SPINLOCK >> + u16 cpu_nr; /* CPU number */ >> + void *lock; /* Lock address */ >> +#endif >> +}; >> + >> +/* >> + * The 16-bit wait queue code is divided into the following 2 fields: >> + * Bits 0-1 : queue node index >> + * Bits 2-15: cpu number + 1 >> + * >> + * The current implementation will allow a maximum of (1<<14)-1 = 16383 CPUs. > > I haven't yet read far enough to figure out why you need the -1 thing, > but effectively you're restricted to 15k due to this. > It is exactly 16k-1 not 15k That is because CPU_CODE of 1 to 16k represents cpu 0..16k-1