linux-kernel - Re: [PATCH v6 5/6] MCS Lock: Restructure the MCS lock defines and locking code into its own file

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <524B75F0.2070005@hp.com>
Date:	Tue, 01 Oct 2013 21:25:04 -0400
From:	Waiman Long <waiman.long@...com>
To:	Tim Chen <tim.c.chen@...ux.intel.com>
CC:	Jason Low <jason.low2@...com>,
	Paul McKenney <paulmck@...ux.vnet.ibm.com>,
	Ingo Molnar <mingo@...e.hu>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Andrea Arcangeli <aarcange@...hat.com>,
	Alex Shi <alex.shi@...aro.org>,
	Andi Kleen <andi@...stfloor.org>,
	Michel Lespinasse <walken@...gle.com>,
	Davidlohr Bueso <davidlohr.bueso@...com>,
	Matthew R Wilcox <matthew.r.wilcox@...el.com>,
	Dave Hansen <dave.hansen@...el.com>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Rik van Riel <riel@...hat.com>,
	Peter Hurley <peter@...leysoftware.com>,
	linux-kernel@...r.kernel.org, linux-mm <linux-mm@...ck.org>
Subject: Re: [PATCH v6 5/6] MCS Lock: Restructure the MCS lock defines and
 locking code into its own file

On 10/01/2013 05:16 PM, Tim Chen wrote:
> On Tue, 2013-10-01 at 16:01 -0400, Waiman Long wrote:
>>>
>>> The cpu could still be executing out of order load instruction from the
>>> critical section before checking node->locked?  Probably smp_mb() is
>>> still needed.
>>>
>>> Tim
>> But this is the lock function, a barrier() call should be enough to
>> prevent the critical section from creeping up there. We certainly need
>> some kind of memory barrier at the end of the unlock function.
> I may be missing something.  My understanding is that barrier only
> prevents the compiler from rearranging instructions, but not for cpu out
> of order execution (as in smp_mb). So cpu could read memory in the next
> critical section, before node->locked is true, (i.e. unlock has been
> completed).  If we only have a simple barrier at end of mcs_lock, then
> say the code on CPU1 is
>
> 	mcs_lock
> 	x = 1;
> 	...
> 	x = 2;
> 	mcs_unlock
>
> and CPU 2 is
>
> 	mcs_lock
> 	y = x;
> 	...
> 	mcs_unlock
>
> We expect y to be 2 after the "y = x" assignment.  But we
> we may execute the code as
>
> 	CPU1		CPU2
> 		
> 	x = 1;
> 	...		y = x;  ( y=1, out of order load)
> 	x = 2
> 	mcs_unlock
> 			Check node->locked==true
> 			continue executing critical section (y=1 when we expect y=2)
>
> So we get y to be 1 when we expect that it should be 2.  Adding smp_mb
> after the node->locked check in lock code
>
>             ACCESS_ONCE(prev->next) = node;
>             /* Wait until the lock holder passes the lock down */
>             while (!ACCESS_ONCE(node->locked))
>                      arch_mutex_cpu_relax();
>             smp_mb();
>
> should prevent this scenario.
>
> Thanks.
> Tim

If the lock and unlock functions are done right, there should be no 
overlap of critical section. So it is job of the lock/unlock functions 
to make sure that critical section code won't leak out. There should be 
some kind of memory barrier at the beginning of the lock function and 
the end of the unlock function.

The critical section also likely to have branches. The CPU may 
speculatively execute code on the 2 branches, but one of them will be 
discarded once the branch condition is known. Also 
arch_mutex_cpu_relax() is a compiler barrier by itself. So we may not 
need a barrier() after all. The while statement is a branch instruction, 
any code after that can only be speculatively executed and cannot be 
committed until the branch is done.

In x86, the smp_mb() function translated to a mfence instruction which 
cost time. That is why I try to get rid of it if it is not necessary.

Regards,
Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/