Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933536AbdGTBal (ORCPT ); Wed, 19 Jul 2017 21:30:41 -0400 Received: from mail-pf0-f193.google.com ([209.85.192.193]:36325 "EHLO mail-pf0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932149AbdGTBaj (ORCPT ); Wed, 19 Jul 2017 21:30:39 -0400 Date: Thu, 20 Jul 2017 09:31:41 +0800 From: Boqun Feng To: "Paul E. McKenney" Cc: Akira Yokosawa , linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH] documentation: Fix two-CPU control-dependency example Message-ID: <20170720013112.fmrml6abdhi2nqdt@tardis> References: <0d60072f-3848-a2b7-ce18-e1ed317b5c09@gmail.com> <20170719174334.GH3730@linux.vnet.ibm.com> <101f5108-663e-7fa4-ac2b-e790320e4e6f@gmail.com> <20170719215602.GK3730@linux.vnet.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170719215602.GK3730@linux.vnet.ibm.com> User-Agent: NeoMutt/20170609 (1.8.3) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5933 Lines: 158 On Wed, Jul 19, 2017 at 02:56:02PM -0700, Paul E. McKenney wrote: > On Thu, Jul 20, 2017 at 06:33:26AM +0900, Akira Yokosawa wrote: > > 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 > > >> 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 > > > > > > 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: > > Hi Akira, I wouldn't call that compiler a clever one, it's a broken one ;-) So here is the thing: READ_ONCE() is a *volatile* load, which means the compiler has to generate code that actually does a load, so the values of r1 and r2 depend on the loads, therefore, a sane compiler will not optimize the if()s out because the volatile semantics of READ_ONCE(). Otherwise, I think we have a lot more to worry about than this case. > > 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? > > That is a matter of some debate, but it has gotten increasingly more > difficult to get C to do one's bidding over the decades. > > > What am I missing here? > > The compiler has to work harder in your example case, so it is probably > just a matter of time. In the original with ">=", all the compiler needed > to do was look at all the assignments and the initial value. In the > original, it also had to do reasoning based on control dependencies > (which are not yet part of the C standard). > > But yes, the degree to which a compiler can optimize atomics is a matter > of some debate. Here is a proposal to let the developer choose: > Hi Paul, I know the compiler could optimize atomics in very interesting ways, but this case is about volatile, so I guess our case is still fine? ;-) > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0062r1.html > Great material to wake up mind in the morning! Thanks. Regards, Boqun > What are your thoughts on this? > > Thanx, Paul > > > 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 > > > > > > > > >