TEXT   49

glossary

Guest on 23rd August 2022 12:34:50 PM

  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.rst
  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, (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.  
  42. Coherence (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.  
  54. Control 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.  
  69. Cycle:  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.  
  88. Data 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.  
  105. From-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.  
  117. Fully 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.  
  123. Happens-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.  
  128. Marked 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.  
  133. Pairing: "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.  
  143. Reads-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.  
  158. Relaxed:  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.  
  165. Release:  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.  
  175. Unmarked Access:  An access to a variable that uses normal C-language
  176.         syntax, for example, "a = b[2]";
  177.  
  178.         See also "Marked Access".

Raw Paste


Login or Register to edit or fork this paste. It's free.