linux-kernel - Re: [PATCH] documentation: Fix two-CPU control-dependency example

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: <101f5108-663e-7fa4-ac2b-e790320e4e6f@gmail.com>
Date:   Thu, 20 Jul 2017 06:33:26 +0900
From:   Akira Yokosawa <akiyks@...il.com>
To:     "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:     linux-doc@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] documentation: Fix two-CPU control-dependency example

On 2017/07/20 2:43, Paul E. McKenney wrote:
> On Mon, Jul 17, 2017 at 05:24:42PM +0900, Akira Yokosawa wrote:
>> >From b798b9b631e237d285aa8699da00bfb8ced33bea Mon Sep 17 00:00:00 2001
>> From: Akira Yokosawa <akiyks@...il.com>
>> Date: Mon, 17 Jul 2017 16:25:33 +0900
>> Subject: [PATCH] documentation: Fix two-CPU control-dependency example
>>
>> In commit 5646f7acc95f ("memory-barriers: Fix control-ordering
>> no-transitivity example"), the operator in "if" statement of
>> the two-CPU example was modified from ">=" to ">".
>> Now the example misses the point because there is no party
>> who will modify "x" nor "y". So each CPU performs only the
>> READ_ONCE().
>>
>> The point of this example is to use control dependency for ordering,
>> and the WRITE_ONCE() should always be executed.
>>
>> So it was correct prior to the above mentioned commit. Partial
>> revert of the commit (with context adjustments regarding other
>> changes thereafter) restores the point.
>>
>> Note that the three-CPU example demonstrating the lack of
>> transitivity stands regardless of this partial revert.
>>
>> Signed-off-by: Akira Yokosawa <akiyks@...il.com>
> 
> Hello, Akira,
> 
> You are quite right that many compilers would generate straightforward
> code for the code fragment below, and in that case, the assertion could
> never trigger due to either TSO or control dependencies, depending on
> the architecture this was running on.
> 
> However, if the compiler was too smart for our good, it could figure
> out that "x" and "y" only take on the values zero and one, so that
> the "if" would always be taken.  At that point, the compiler could
> simply ignore the "if" with the result shown below.
> 
>> ---
>>  Documentation/memory-barriers.txt | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
>> index c4ddfcd..c1ebe99 100644
>> --- a/Documentation/memory-barriers.txt
>> +++ b/Documentation/memory-barriers.txt
>> @@ -851,7 +851,7 @@ demonstrated by two related examples, with the initial values of
>>  	CPU 0                     CPU 1
>>  	=======================   =======================
>>  	r1 = READ_ONCE(x);        r2 = READ_ONCE(y);
>> -	if (r1 > 0)               if (r2 > 0)
>> +	if (r1 >= 0)              if (r2 >= 0)
>>  	  WRITE_ONCE(y, 1);         WRITE_ONCE(x, 1);
>>
>>  	assert(!(r1 == 1 && r2 == 1));
> 
> Original program:
> 
>  	CPU 0                     CPU 1
>  	=======================   =======================
>  	r1 = READ_ONCE(x);        r2 = READ_ONCE(y);
> 	if (r1 >= 0)              if (r2 >= 0)
>  	  WRITE_ONCE(y, 1);         WRITE_ONCE(x, 1);
> 
>  	assert(!(r1 == 1 && r2 == 1));
> 
> Enthusiastically optimized program:
> 
>  	CPU 0                     CPU 1
>  	=======================   =======================
>  	r1 = READ_ONCE(x);        r2 = READ_ONCE(y);
>  	WRITE_ONCE(y, 1);         WRITE_ONCE(x, 1);
> 
>  	assert(!(r1 == 1 && r2 == 1));
> 
> This optimized version could trigger the assertion.
> 
> So we do need to stick with the ">" comparison.

Well but,

Current example:

 	CPU 0                     CPU 1
 	=======================   =======================
 	r1 = READ_ONCE(x);        r2 = READ_ONCE(y);
	if (r1 > 0)               if (r2 > 0)
 	  WRITE_ONCE(y, 1);         WRITE_ONCE(x, 1);

	assert(!(r1 == 1 && r2 == 1));

Such a clever compiler might be able to prove that "x" and "y"
are never modified and end up in the following:

 	CPU 0                     CPU 1
 	=======================   =======================
 	r1 = READ_ONCE(x);        r2 = READ_ONCE(y);

	assert(!(r1 == 1 && r2 == 1));

This means it is impossible to describe this example in C,
doesn't it?

What am I missing here?

            Thanks, Akira

> That said, I very much welcome critical reviews of memory-barriers.txt,
> so please do feel free to continue doing that!
> 
> 							Thanx, Paul
> 
>