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