(here's #3.) ----- Forwarded message from "Paul E. McKenney" <paul...@linux.vnet.ibm.com> -----
Date: Wed, 4 Dec 2013 14:46:58 -0800 From: "Paul E. McKenney" <paul...@linux.vnet.ibm.com> To: linux-kernel@vger.kernel.org Cc: mi...@kernel.org, la...@cn.fujitsu.com, dipan...@in.ibm.com, a...@linux-foundation.org, mathieu.desnoy...@efficios.com, j...@joshtriplett.org, n...@us.ibm.com, t...@linutronix.de, pet...@infradead.org, rost...@goodmis.org, dhowe...@redhat.com, eduma...@google.com, dar...@dvhart.com, fweis...@gmail.com, s...@mit.edu, "Paul E. McKenney" <paul...@linux.vnet.ibm.com>, Richard Henderson <r...@twiddle.net>, Ivan Kokshaysky <i...@jurassic.park.msu.ru>, Matt Turner <matts...@gmail.com>, Russell King <li...@arm.linux.org.uk>, Arnd Bergmann <a...@arndb.de>, Olof Johansson <o...@lixom.net>, Catalin Marinas <catalin.mari...@arm.com>, Will Deacon <will.dea...@arm.com>, Haavard Skinnemoen <hskinnem...@gmail.com>, Hans-Christian Egtvedt <egtv...@samfundet.no>, Mike Frysinger <vap...@gentoo.org>, Mark Salter <msal...@redhat.com>, Aurelien Jacquiot <a-jacqu...@ti.com>, Mikael Starvik <star...@axis.com>, Jesper Nilsson <jesper.nils...@axis.com>, Yoshinori Sato <ys...@users.sourceforge.jp>, Richard Kuo <r...@codeaurora.org>, Tony Luck <tony.l...@intel.com>, Fenghua Yu <fenghua...@intel.com>, Hirokazu Takata <tak...@linux-m32r.org>, Geert Uytterhoeven <ge...@linux-m68k.org>, James Hogan <james.ho...@imgtec.com>, Michal Simek <mon...@monstr.eu>, Ralf Baechle <r...@linux-mips.org>, Koichi Yasutake <yasutake.koi...@jp.panasonic.com>, Jonas Bonn <jo...@southpole.se>, "James E.J. Bottomley" <j...@parisc-linux.org>, Helge Deller <del...@gmx.de>, Benjamin Herrenschmidt <b...@kernel.crashing.org>, Paul Mackerras <pau...@samba.org>, Anatolij Gustschin <ag...@denx.de>, Josh Boyer <jwbo...@gmail.com>, Matt Porter <mpor...@kernel.crashing.org>, Vitaly Bordug <v...@kernel.crashing.org>, Kumar Gala <ga...@kernel.crashing.org>, Martin Schwidefsky <schwidef...@de.ibm.com>, Heiko Carstens <heiko.carst...@de.ibm.com>, Chen Liqin <liqin.li...@gmail.com>, Lennox Wu <lennox...@gmail.com>, Paul Mundt <let...@linux-sh.org>, "David S. Miller" <da...@davemloft.net>, Chris Metcalf <cmetc...@tilera.com>, Jeff Dike <jd...@addtoit.com>, Richard Weinberger <rich...@nod.at>, Guan Xuetao <g...@mprc.pku.edu.cn>, Ingo Molnar <mi...@redhat.com>, "H. Peter Anvin" <h...@zytor.com>, Chris Zankel <ch...@zankel.net>, Max Filippov <jcmvb...@gmail.com> Subject: [PATCH tip/core/locking 3/4] Documentation/memory-barriers.txt: Prohibit speculative writes From: "Paul E. McKenney" <paul...@linux.vnet.ibm.com> No SMP architecture currently supporting Linux allows speculative writes, so this commit updates Documentation/memory-barriers.txt to prohibit them in Linux core code. It also records restrictions on their use. Signed-off-by: Peter Zijlstra <pet...@infradead.org> Signed-off-by: Paul E. McKenney <paul...@linux.vnet.ibm.com> Cc: Richard Henderson <r...@twiddle.net> Cc: Ivan Kokshaysky <i...@jurassic.park.msu.ru> Cc: Matt Turner <matts...@gmail.com> Cc: Russell King <li...@arm.linux.org.uk> Cc: Arnd Bergmann <a...@arndb.de> Cc: Olof Johansson <o...@lixom.net> Cc: Catalin Marinas <catalin.mari...@arm.com> Cc: Will Deacon <will.dea...@arm.com> Cc: Haavard Skinnemoen <hskinnem...@gmail.com> Cc: Hans-Christian Egtvedt <egtv...@samfundet.no> Cc: Mike Frysinger <vap...@gentoo.org> Cc: Mark Salter <msal...@redhat.com> Cc: Aurelien Jacquiot <a-jacqu...@ti.com> Cc: Mikael Starvik <star...@axis.com> Cc: Jesper Nilsson <jesper.nils...@axis.com> Cc: David Howells <dhowe...@redhat.com> Cc: Yoshinori Sato <ys...@users.sourceforge.jp> Cc: Richard Kuo <r...@codeaurora.org> Cc: Tony Luck <tony.l...@intel.com> Cc: Fenghua Yu <fenghua...@intel.com> Cc: Hirokazu Takata <tak...@linux-m32r.org> Cc: Geert Uytterhoeven <ge...@linux-m68k.org> Cc: James Hogan <james.ho...@imgtec.com> Cc: Michal Simek <mon...@monstr.eu> Cc: Ralf Baechle <r...@linux-mips.org> Cc: Koichi Yasutake <yasutake.koi...@jp.panasonic.com> Cc: Jonas Bonn <jo...@southpole.se> Cc: "James E.J. Bottomley" <j...@parisc-linux.org> Cc: Helge Deller <del...@gmx.de> Cc: Benjamin Herrenschmidt <b...@kernel.crashing.org> Cc: Paul Mackerras <pau...@samba.org> Cc: Anatolij Gustschin <ag...@denx.de> Cc: Josh Boyer <jwbo...@gmail.com> Cc: Matt Porter <mpor...@kernel.crashing.org> Cc: Vitaly Bordug <v...@kernel.crashing.org> Cc: Kumar Gala <ga...@kernel.crashing.org> Cc: Martin Schwidefsky <schwidef...@de.ibm.com> Cc: Heiko Carstens <heiko.carst...@de.ibm.com> Cc: Chen Liqin <liqin.li...@gmail.com> Cc: Lennox Wu <lennox...@gmail.com> Cc: Paul Mundt <let...@linux-sh.org> Cc: "David S. Miller" <da...@davemloft.net> Cc: Chris Metcalf <cmetc...@tilera.com> Cc: Jeff Dike <jd...@addtoit.com> Cc: Richard Weinberger <rich...@nod.at> Cc: Guan Xuetao <g...@mprc.pku.edu.cn> Cc: Thomas Gleixner <t...@linutronix.de> Cc: Ingo Molnar <mi...@redhat.com> Cc: "H. Peter Anvin" <h...@zytor.com> Cc: Chris Zankel <ch...@zankel.net> Cc: Max Filippov <jcmvb...@gmail.com> --- Documentation/memory-barriers.txt | 183 ++++++++++++++++++++++++++++++++++++-- 1 file changed, 175 insertions(+), 8 deletions(-) diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt index 2d22da095a60..3e4429ef1458 100644 --- a/Documentation/memory-barriers.txt +++ b/Documentation/memory-barriers.txt @@ -571,11 +571,10 @@ dependency barrier to make it work correctly. Consider the following bit of code: q = ACCESS_ONCE(a); - if (p) { - <data dependency barrier> - q = ACCESS_ONCE(b); + if (q) { + <data dependency barrier> /* BUG: No data dependency!!! */ + p = ACCESS_ONCE(b); } - x = *q; This will not have the desired effect because there is no actual data dependency, but rather a control dependency that the CPU may short-circuit @@ -584,11 +583,176 @@ the load from b as having happened before the load from a. In such a case what's actually required is: q = ACCESS_ONCE(a); - if (p) { + if (q) { <read barrier> - q = ACCESS_ONCE(b); + p = ACCESS_ONCE(b); } - x = *q; + +However, stores are not speculated. This means that ordering -is- provided +in the following example: + + q = ACCESS_ONCE(a); + if (ACCESS_ONCE(q)) { + ACCESS_ONCE(b) = p; + } + +Please note that ACCESS_ONCE() is not optional! Without the ACCESS_ONCE(), +the compiler is within its rights to transform this example: + + q = a; + if (q) { + b = p; /* BUG: Compiler can reorder!!! */ + do_something(); + } else { + b = p; /* BUG: Compiler can reorder!!! */ + do_something_else(); + } + +into this, which of course defeats the ordering: + + b = p; + q = a; + if (q) + do_something(); + else + do_something_else(); + +Worse yet, if the compiler is able to prove (say) that the value of +variable a is always non-zero, it would be well within its rights +to optimize the original example by eliminating the "if" statement +as follows: + + q = a; + b = p; /* BUG: Compiler can reorder!!! */ + do_something(); + +The solution is again ACCESS_ONCE(), which preserves the ordering between +the load from variable a and the store to variable b: + + q = ACCESS_ONCE(a); + if (q) { + ACCESS_ONCE(b) = p; + do_something(); + } else { + ACCESS_ONCE(b) = p; + do_something_else(); + } + +You could also use barrier() to prevent the compiler from moving +the stores to variable b, but barrier() would not prevent the +compiler from proving to itself that a==1 always, so ACCESS_ONCE() +is also needed. + +It is important to note that control dependencies absolutely require a +a conditional. For example, the following "optimized" version of +the above example breaks ordering: + + q = ACCESS_ONCE(a); + ACCESS_ONCE(b) = p; /* BUG: No ordering vs. load from a!!! */ + if (q) { + /* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */ + do_something(); + } else { + /* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */ + do_something_else(); + } + +It is of course legal for the prior load to be part of the conditional, +for example, as follows: + + if (ACCESS_ONCE(a) > 0) { + ACCESS_ONCE(b) = q / 2; + do_something(); + } else { + ACCESS_ONCE(b) = q / 3; + do_something_else(); + } + +This will again ensure that the load from variable a is ordered before the +stores to variable b. + +In addition, you need to be careful what you do with the local variable q, +otherwise the compiler might be able to guess the value and again remove +the needed conditional. For example: + + q = ACCESS_ONCE(a); + if (q % MAX) { + ACCESS_ONCE(b) = p; + do_something(); + } else { + ACCESS_ONCE(b) = p; + do_something_else(); + } + +If MAX is defined to be 1, then the compiler knows that (q % MAX) is +equal to zero, in which case the compiler is within its rights to +transform the above code into the following: + + q = ACCESS_ONCE(a); + ACCESS_ONCE(b) = p; + do_something_else(); + +This transformation loses the ordering between the load from variable a +and the store to variable b. If you are relying on this ordering, you +should do something like the following: + + q = ACCESS_ONCE(a); + BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */ + if (q % MAX) { + ACCESS_ONCE(b) = p; + do_something(); + } else { + ACCESS_ONCE(b) = p; + do_something_else(); + } + +Finally, control dependencies do -not- provide transitivity. This is +demonstrated by two related examples: + + CPU 0 CPU 1 + ===================== ===================== + r1 = ACCESS_ONCE(x); r2 = ACCESS_ONCE(y); + 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: + + CPU 2 CPU 3 + ===================== ===================== + ACCESS_ONCE(x) = 2; ACCESS_ONCE(y) = 2; + + 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 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. + +In summary: + + (*) Control dependencies can order prior loads against later stores. + However, they do -not- guarantee any other sort of ordering: + Not prior loads against later loads, nor prior stores against + later anything. If you need these other forms of ordering, + use smb_rmb(), smp_wmb(), or, in the case of prior stores and + later loads, smp_mb(). + + (*) Control dependencies require at least one run-time conditional + between the prior load and the subsequent store. If the compiler + is able to optimize the conditional away, it will have also + optimized away the ordering. Careful use of ACCESS_ONCE() can + help to preserve the needed conditional. + + (*) Control dependencies require that the compiler avoid reordering the + dependency into nonexistence. Careful use of ACCESS_ONCE() or + barrier() can help to preserve your control dependency. + + (*) Control dependencies do -not- provide transitivity. If you + need transitivity, use smp_mb(). SMP BARRIER PAIRING @@ -1083,7 +1247,10 @@ compiler from moving the memory accesses either side of it to the other side: barrier(); -This is a general barrier - lesser varieties of compiler barrier do not exist. +This is a general barrier -- there are no read-read or write-write variants +of barrier(). Howevever, ACCESS_ONCE() can be thought of as a weak form +for barrier() that affects only the specific accesses flagged by the +ACCESS_ONCE(). The compiler barrier has no direct effect on the CPU, which may then reorder things however it wishes. -- 1.8.1.5 ----- End forwarded message ----- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/