tools/memory-model/Documentation/glossary.txt

   1 This document contains brief definitions of LKMM-related terms.  Like most
   2 glossaries, it is not intended to be read front to back (except perhaps
   3 as a way of confirming a diagnosis of OCD), but rather to be searched
   4 for specific terms.
   5
   6
   7 Address Dependency:  When the address of a later memory access is computed
   8         based on the value returned by an earlier load, an "address
   9         dependency" extends from that load extending to the later access.
  10         Address dependencies are quite common in RCU read-side critical
  11         sections:
  12
  13          1 rcu_read_lock();
  14          2 p = rcu_dereference(gp);
  15          3 do_something(p->a);
  16          4 rcu_read_unlock();
  17
  18          In this case, because the address of "p->a" on line 3 is computed
  19          from the value returned by the rcu_dereference() on line 2, the
  20          address dependency extends from that rcu_dereference() to that
  21          "p->a".  In rare cases, optimizing compilers can destroy address
  22          dependencies.  Please see Documentation/RCU/rcu_dereference.txt
  23          for more information.
  24
  25          See also "Control Dependency" and "Data Dependency".
  26
  27 Acquire:  With respect to a lock, acquiring that lock, for example,
  28         using spin_lock().  With respect to a non-lock shared variable,
  29         a special operation that includes a load and which orders that
  30         load before later memory references running on that same CPU.
  31         An example special acquire operation is smp_load_acquire(),
  32         but atomic_read_acquire() and atomic_xchg_acquire() also include
  33         acquire loads.
  34
  35         When an acquire load returns the value stored by a release store
  36         to that same variable, then all operations preceding that store
  37         happen before any operations following that load acquire.
  38
  39         See also "Relaxed" and "Release".
  40
  41 Coherence (co):  When one CPU's store to a given variable overwrites
  42         either the value from another CPU's store or some later value,
  43         there is said to be a coherence link from the second CPU to
  44         the first.
  45
  46         It is also possible to have a coherence link within a CPU, which
  47         is a "coherence internal" (coi) link.  The term "coherence
  48         external" (coe) link is used when it is necessary to exclude
  49         the coi case.
  50
  51         See also "From-reads" and "Reads-from".
  52
  53 Control Dependency:  When a later store's execution depends on a test
  54         of a value computed from a value returned by an earlier load,
  55         a "control dependency" extends from that load to that store.
  56         For example:
  57
  58          1 if (READ_ONCE(x))
  59          2   WRITE_ONCE(y, 1);
  60
  61          Here, the control dependency extends from the READ_ONCE() on
  62          line 1 to the WRITE_ONCE() on line 2.  Control dependencies are
  63          fragile, and can be easily destroyed by optimizing compilers.
  64          Please see control-dependencies.txt for more information.
  65
  66          See also "Address Dependency" and "Data Dependency".
  67
  68 Cycle:  Memory-barrier pairing is restricted to a pair of CPUs, as the
  69         name suggests.  And in a great many cases, a pair of CPUs is all
  70         that is required.  In other cases, the notion of pairing must be
  71         extended to additional CPUs, and the result is called a "cycle".
  72         In a cycle, each CPU's ordering interacts with that of the next:
  73
  74         CPU 0                CPU 1                CPU 2
  75         WRITE_ONCE(x, 1);    WRITE_ONCE(y, 1);    WRITE_ONCE(z, 1);
  76         smp_mb();            smp_mb();            smp_mb();
  77         r0 = READ_ONCE(y);   r1 = READ_ONCE(z);   r2 = READ_ONCE(x);
  78
  79         CPU 0's smp_mb() interacts with that of CPU 1, which interacts
  80         with that of CPU 2, which in turn interacts with that of CPU 0
  81         to complete the cycle.  Because of the smp_mb() calls between
  82         each pair of memory accesses, the outcome where r0, r1, and r2
  83         are all equal to zero is forbidden by LKMM.
  84
  85         See also "Pairing".
  86
  87 Data Dependency:  When the data written by a later store is computed based
  88         on the value returned by an earlier load, a "data dependency"
  89         extends from that load to that later store.  For example:
  90
  91          1 r1 = READ_ONCE(x);
  92          2 WRITE_ONCE(y, r1 + 1);
  93
  94         In this case, the data dependency extends from the READ_ONCE()
  95         on line 1 to the WRITE_ONCE() on line 2.  Data dependencies are
  96         fragile and can be easily destroyed by optimizing compilers.
  97         Because optimizing compilers put a great deal of effort into
  98         working out what values integer variables might have, this is
  99         especially true in cases where the dependency is carried through
 100         an integer.
 101
 102         See also "Address Dependency" and "Control Dependency".
 103
 104 From-Reads (fr):  When one CPU's store to a given variable happened
 105         too late to affect the value returned by another CPU's
 106         load from that same variable, there is said to be a from-reads
 107         link from the load to the store.
 108
 109         It is also possible to have a from-reads link within a CPU, which
 110         is a "from-reads internal" (fri) link.  The term "from-reads
 111         external" (fre) link is used when it is necessary to exclude
 112         the fri case.
 113
 114         See also "Coherence" and "Reads-from".
 115
 116 Fully Ordered:  An operation such as smp_mb() that orders all of
 117         its CPU's prior accesses with all of that CPU's subsequent
 118         accesses, or a marked access such as atomic_add_return()
 119         that orders all of its CPU's prior accesses, itself, and
 120         all of its CPU's subsequent accesses.
 121
 122 Marked Access:  An access to a variable that uses an special function or
 123         macro such as "r1 = READ_ONCE(x)" or "smp_store_release(&a, 1)".
 124
 125         See also "Unmarked Access".
 126
 127 Pairing: "Memory-barrier pairing" reflects the fact that synchronizing
 128         data between two CPUs requires that both CPUs their accesses.
 129         Memory barriers thus tend to come in pairs, one executed by
 130         one of the CPUs and the other by the other CPU.  Of course,
 131         pairing also occurs with other types of operations, so that a
 132         smp_store_release() pairs with an smp_load_acquire() that reads
 133         the value stored.
 134
 135         See also "Cycle".
 136
 137 Reads-From (rf):  When one CPU's load returns the value stored by some other
 138         CPU, there is said to be a reads-from link from the second
 139         CPU's store to the first CPU's load.  Reads-from links have the
 140         nice property that time must advance from the store to the load,
 141         which means that algorithms using reads-from links can use lighter
 142         weight ordering and synchronization compared to algorithms using
 143         coherence and from-reads links.
 144
 145         It is also possible to have a reads-from link within a CPU, which
 146         is a "reads-from internal" (rfi) link.  The term "reads-from
 147         external" (rfe) link is used when it is necessary to exclude
 148         the rfi case.
 149
 150         See also Coherence" and "From-reads".
 151
 152 Relaxed:  A marked access that does not imply ordering, for example, a
 153         READ_ONCE(), WRITE_ONCE(), a non-value-returning read-modify-write
 154         operation, or a value-returning read-modify-write operation whose
 155         name ends in "_relaxed".
 156
 157         See also "Acquire" and "Release".
 158
 159 Release:  With respect to a lock, releasing that lock, for example,
 160         using spin_unlock().  With respect to a non-lock shared variable,
 161         a special operation that includes a store and which orders that
 162         store after earlier memory references that ran on that same CPU.
 163         An example special release store is smp_store_release(), but
 164         atomic_set_release() and atomic_cmpxchg_release() also include
 165         release stores.
 166
 167         See also "Acquire" and "Relaxed".
 168
 169 Unmarked Access:  An access to a variable that uses normal C-language
 170         syntax, for example, "a = b[2]";
 171
 172         See also "Marked Access".