with memory references that are not protected by READ_ONCE() and
WRITE_ONCE(). Without them, the compiler is within its rights to
do all sorts of "creative" transformations, which are covered in
- the Compiler Barrier section.
+ the COMPILER BARRIER section.
(*) It _must_not_ be assumed that independent loads and stores will be issued
in the order given. This means that for:
This enforces the occurrence of one of the two implications, and prevents the
third possibility from arising.
+A data-dependency barrier must also order against dependent writes:
+
+ CPU 1 CPU 2
+ =============== ===============
+ { A == 1, B == 2, C = 3, P == &A, Q == &C }
+ B = 4;
+ <write barrier>
+ WRITE_ONCE(P, &B);
+ Q = READ_ONCE(P);
+ <data dependency barrier>
+ *Q = 5;
+
+The data-dependency barrier must order the read into Q with the store
+into *Q. This prohibits this outcome:
+
+ (Q == B) && (B == 4)
+
+Please note that this pattern should be rare. After all, the whole point
+of dependency ordering is to -prevent- writes to the data structure, along
+with the expensive cache misses associated with those writes. This pattern
+can be used to record rare error conditions and the like, and the ordering
+prevents such records from being lost.
+
+
[!] Note that this extremely counterintuitive situation arises most easily on
machines with split caches, so that, for example, one cache bank processes
even-numbered cache lines and the other bank processes odd-numbered cache
but the old value of the variable B (2).
-Another example of where data dependency barriers might be required is where a
-number is read from memory and then used to calculate the index for an array
-access:
-
- CPU 1 CPU 2
- =============== ===============
- { M[0] == 1, M[1] == 2, M[3] = 3, P == 0, Q == 3 }
- M[1] = 4;
- <write barrier>
- WRITE_ONCE(P, 1);
- Q = READ_ONCE(P);
- <data dependency barrier>
- D = M[Q];
-
-
The data dependency barrier is very important to the RCU system,
for example. See rcu_assign_pointer() and rcu_dereference() in
include/linux/rcupdate.h. This permits the current target of an RCU'd
use smp_rmb(), smp_wmb(), or, in the case of prior stores and
later loads, smp_mb().
- (*) If both legs of the "if" statement begin with identical stores
- to the same variable, a barrier() statement is required at the
- beginning of each leg of the "if" statement.
+ (*) If both legs of the "if" statement begin with identical stores to
+ the same variable, then those stores must be ordered, either by
+ preceding both of them with smp_mb() or by using smp_store_release()
+ to carry out the stores. Please note that it is -not- sufficient
+ to use barrier() at beginning of each leg of the "if" statement,
+ as optimizing compilers do not necessarily respect barrier()
+ in this case.
(*) Control dependencies require at least one run-time conditional
between the prior load and the subsequent store, and this
(*) Control dependencies require that the compiler avoid reordering the
dependency into nonexistence. Careful use of READ_ONCE() or
atomic{,64}_read() can help to preserve your control dependency.
- Please see the Compiler Barrier section for more information.
+ Please see the COMPILER BARRIER section for more information.
(*) Control dependencies pair normally with other types of barriers.
Transitivity is a deeply intuitive notion about ordering that is not
always provided by real computer systems. The following example
-demonstrates transitivity (also called "cumulativity"):
+demonstrates transitivity:
CPU 1 CPU 2 CPU 3
======================= ======================= =======================
General barriers are therefore required to ensure that all CPUs agree
on the combined order of CPU 1's and CPU 2's accesses.
-To reiterate, if your code requires transitivity, use general barriers
-throughout.
+General barriers provide "global transitivity", so that all CPUs will
+agree on the order of operations. In contrast, a chain of release-acquire
+pairs provides only "local transitivity", so that only those CPUs on
+the chain are guaranteed to agree on the combined order of the accesses.
+For example, switching to C code in deference to Herman Hollerith:
+
+ int u, v, x, y, z;
+
+ void cpu0(void)
+ {
+ r0 = smp_load_acquire(&x);
+ WRITE_ONCE(u, 1);
+ smp_store_release(&y, 1);
+ }
+
+ void cpu1(void)
+ {
+ r1 = smp_load_acquire(&y);
+ r4 = READ_ONCE(v);
+ r5 = READ_ONCE(u);
+ smp_store_release(&z, 1);
+ }
+
+ void cpu2(void)
+ {
+ r2 = smp_load_acquire(&z);
+ smp_store_release(&x, 1);
+ }
+
+ void cpu3(void)
+ {
+ WRITE_ONCE(v, 1);
+ smp_mb();
+ r3 = READ_ONCE(u);
+ }
+
+Because cpu0(), cpu1(), and cpu2() participate in a local transitive
+chain of smp_store_release()/smp_load_acquire() pairs, the following
+outcome is prohibited:
+
+ r0 == 1 && r1 == 1 && r2 == 1
+
+Furthermore, because of the release-acquire relationship between cpu0()
+and cpu1(), cpu1() must see cpu0()'s writes, so that the following
+outcome is prohibited:
+
+ r1 == 1 && r5 == 0
+
+However, the transitivity of release-acquire is local to the participating
+CPUs and does not apply to cpu3(). Therefore, the following outcome
+is possible:
+
+ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
+
+As an aside, the following outcome is also possible:
+
+ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0 && r5 == 1
+
+Although cpu0(), cpu1(), and cpu2() will see their respective reads and
+writes in order, CPUs not involved in the release-acquire chain might
+well disagree on the order. This disagreement stems from the fact that
+the weak memory-barrier instructions used to implement smp_load_acquire()
+and smp_store_release() are not required to order prior stores against
+subsequent loads in all cases. This means that cpu3() can see cpu0()'s
+store to u as happening -after- cpu1()'s load from v, even though
+both cpu0() and cpu1() agree that these two operations occurred in the
+intended order.
+
+However, please keep in mind that smp_load_acquire() is not magic.
+In particular, it simply reads from its argument with ordering. It does
+-not- ensure that any particular value will be read. Therefore, the
+following outcome is possible:
+
+ r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
+
+Note that this outcome can happen even on a mythical sequentially
+consistent system where nothing is ever reordered.
+
+To reiterate, if your code requires global transitivity, use general
+barriers throughout.
========================
the following:
a = 0;
- /* Code that does not store to variable a. */
+ ... Code that does not store to variable a ...
a = 0;
The compiler sees that the value of variable 'a' is already zero, so
wrong guess:
WRITE_ONCE(a, 0);
- /* Code that does not store to variable a. */
+ ... Code that does not store to variable a ...
WRITE_ONCE(a, 0);
(*) The compiler is within its rights to reorder memory accesses unless
SMP memory barriers are reduced to compiler barriers on uniprocessor compiled
systems because it is assumed that a CPU will appear to be self-consistent,
and will order overlapping accesses correctly with respect to itself.
+However, see the subsection on "Virtual Machine Guests" below.
[!] Note that SMP memory barriers _must_ be used to control the ordering of
references to shared memory on SMP systems, though the use of locking instead
is sufficient.
Mandatory barriers should not be used to control SMP effects, since mandatory
-barriers unnecessarily impose overhead on UP systems. They may, however, be
-used to control MMIO effects on accesses through relaxed memory I/O windows.
-These are required even on non-SMP systems as they affect the order in which
-memory operations appear to a device by prohibiting both the compiler and the
-CPU from reordering them.
+barriers impose unnecessary overhead on both SMP and UP systems. They may,
+however, be used to control MMIO effects on accesses through relaxed memory I/O
+windows. These barriers are required even on non-SMP systems as they affect
+the order in which memory operations appear to a device by prohibiting both the
+compiler and the CPU from reordering them.
There are some more advanced barrier functions:
See the subsection on "Cache Coherency" above.
+VIRTUAL MACHINE GUESTS
+-------------------
+
+Guests running within virtual machines might be affected by SMP effects even if
+the guest itself is compiled without SMP support. This is an artifact of
+interfacing with an SMP host while running an UP kernel. Using mandatory
+barriers for this use-case would be possible but is often suboptimal.
+
+To handle this case optimally, low-level virt_mb() etc macros are available.
+These have the same effect as smp_mb() etc when SMP is enabled, but generate
+identical code for SMP and non-SMP systems. For example, virtual machine guests
+should use virt_mb() rather than smp_mb() when synchronizing against a
+(possibly SMP) host.
+
+These are equivalent to smp_mb() etc counterparts in all other respects,
+in particular, they do not control MMIO effects: to control
+MMIO effects, use mandatory barriers.
============
EXAMPLE USES
projects / linux-2.6-block.git / blobdiff