linux-kernel - Re: [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering no-transitivity 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] [day] [month] [year] [list]

Message-ID: <CAJhHMCBRRtKwytqM4uj5_O38yR1XBQ5vquJHF=b1s8cXs=5UyA@mail.gmail.com>
Date:	Sun, 7 Sep 2014 13:10:37 -0400
From:	Pranith Kumar <bobby.prani@...il.com>
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Ingo Molnar <mingo@...nel.org>,
	Lai Jiangshan <laijs@...fujitsu.com>,
	Dipankar Sarma <dipankar@...ibm.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	Josh Triplett <josh@...htriplett.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Peter Zijlstra <peterz@...radead.org>,
	Steven Rostedt <rostedt@...dmis.org>,
	David Howells <dhowells@...hat.com>,
	Eric Dumazet <edumazet@...gle.com>, dvhart@...ux.intel.com,
	Frédéric Weisbecker <fweisbec@...il.com>,
	Oleg Nesterov <oleg@...hat.com>
Subject: Re: [PATCH tip/core/rcu 1/3] memory-barriers: Fix control-ordering
 no-transitivity example

On Thu, Aug 28, 2014 at 2:12 PM, Paul E. McKenney
<paulmck@...ux.vnet.ibm.com> wrote:
> From: "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
>
> The control-ordering example demonstrating lack of transitivity had
> multiple problems.  This commit fixes them.
>
> Reported-by: Nikolay Samofatov <nikolay.samofatov@...il.com>
> Signed-off-by: Paul E. McKenney <paulmck@...ux.vnet.ibm.com>

Reviewed-by: Pranith Kumar <bobby.prani@...il.com>

> ---
>  Documentation/memory-barriers.txt | 28 +++++++++++++++++-----------
>  1 file changed, 17 insertions(+), 11 deletions(-)
>
> diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
> index a4de88fb55f0..d67c508eb660 100644
> --- a/Documentation/memory-barriers.txt
> +++ b/Documentation/memory-barriers.txt
> @@ -697,30 +697,36 @@ should do something like the following:
>         }
>
>  Finally, control dependencies do -not- provide transitivity.  This is
> -demonstrated by two related examples:
> +demonstrated by two related examples, with the initial values of
> +x and y both being zero:
>
>         CPU 0                     CPU 1
>         =====================     =====================
>         r1 = ACCESS_ONCE(x);      r2 = ACCESS_ONCE(y);
> -       if (r1 >= 0)              if (r2 >= 0)
> +       if (r1 > 0)               if (r2 > 0)
>           ACCESS_ONCE(y) = 1;       ACCESS_ONCE(x) = 1;
>
>         assert(!(r1 == 1 && r2 == 1));
>
>  The above two-CPU example will never trigger the assert().  However,
>  if control dependencies guaranteed transitivity (which they do not),
> -then adding the following two CPUs would guarantee a related assertion:
> +then adding the following CPU would guarantee a related assertion:
>
> -       CPU 2                     CPU 3
> -       =====================     =====================
> -       ACCESS_ONCE(x) = 2;       ACCESS_ONCE(y) = 2;
> +       CPU 2
> +       =====================
> +       ACCESS_ONCE(x) = 2;
> +
> +       assert(!(r1 == 2 && r2 == 1 && x == 2)); /* FAILS!!! */
>
> -       assert(!(r1 == 2 && r2 == 2 && x == 1 && y == 1)); /* FAILS!!! */
> +But because control dependencies do -not- provide transitivity, the above
> +assertion can fail after the combined three-CPU example completes.  If you
> +need the three-CPU example to provide ordering, you will need smp_mb()
> +between the loads and stores in the CPU 0 and CPU 1 code fragments,
> +that is, just before or just after the "if" statements.
>
> -But because control dependencies do -not- provide transitivity, the
> -above assertion can fail after the combined four-CPU example completes.
> -If you need the four-CPU example to provide ordering, you will need
> -smp_mb() between the loads and stores in the CPU 0 and CPU 1 code fragments.
> +These two examples are the LB and WWC litmus tests from this paper:
> +http://www.cl.cam.ac.uk/users/pes20/ppc-supplemental/test6.pdf and this
> +site: https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html.
>
>  In summary:
>
> --
> 1.8.1.5
>



-- 
Pranith
--
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/