memory-model/Documentation/explanation.txt

15   7. THE PROGRAM ORDER RELATION: po AND po-loc
18   10. THE READS-FROM RELATION: rf, rfi, and rfe
19   11. CACHE COHERENCE AND THE COHERENCE ORDER RELATION: co, coi, and coe
20   12. THE FROM-READS RELATION: fr, fri, and fre
22   14. PROPAGATION ORDER RELATION: cumul-fence
26   18. THE PRESERVED PROGRAM ORDER RELATION: ppo
28   20. THE HAPPENS-BEFORE RELATION: hb
29   21. THE PROPAGATES-BEFORE RELATION: pb
55 through 12 (THE FROM_READS RELATION) describe the fundamental
327 THE PROGRAM ORDER RELATION: po AND po-loc
330 The most important relation between events is program order (po).  You
338 This is inherently a single-CPU relation; two instructions executing
342 po-loc is a sub-relation of po.  It links two memory accesses when the
421 memory model cannot assume there is a fixed program order relation
429 We say that two events are linked by a dependency relation when the
489 THE READS-FROM RELATION: rf, rfi, and rfe
492 The reads-from relation (rf) links a write event to a read event when
504 Usage of the rf relation implicitly assumes that loads will always
555 CACHE COHERENCE AND THE COHERENCE ORDER RELATION: co, coi, and coe
670 Just like the po relation, co is inherently an ordering -- it is not
672 just like with the rf relation, we distinguish between stores that
682 THE FROM-READS RELATION: fr, fri, and fre
685 The from-reads relation (fr) can be a little difficult for people to
710 As with rf, rfi, and rfe, we subdivide the fr relation into fri (when
714 Note that the fr relation is determined entirely by the rf and co
829 PROPAGATION ORDER RELATION: cumul-fence
834 though smp_wmb() isn't A-cumulative.  The cumul-fence relation is
955 where the rmw relation links the read and write events making up each
959 THE PRESERVED PROGRAM ORDER RELATION: ppo
964 "preserved program order") relation, which links the po-earlier
965 instruction to the po-later instruction and is thus a sub-relation of
1019 includes address dependencies to loads in the ppo relation.
1160 THE HAPPENS-BEFORE RELATION: hb
1163 The happens-before relation (hb) links memory accesses that have to
1164 execute in a certain order.  hb includes the ppo relation and two
1190 The third relation included in hb is like ppo, in that it only links
1193 cache coherence.  The relation is called prop, and it links two events
1290 would generate a cycle in the hb relation: The fence would create a ppo
1292 prop relation would give an hb link from the second load to the first.
1297 The formal definition of the prop relation involves a coe or fre link,
1340 In summary, the fact that the hb relation links memory access events
1344 The LKMM defines yet another relation connected to times of
1350 THE PROPAGATES-BEFORE RELATION: pb
1353 The propagates-before (pb) relation capitalizes on the special
1425 In summary, the fact that the pb relation links events in the order
1506 rcu-link relation.  rcu-link encompasses a very general notion of
1513 The formal definition of the rcu-link relation is more than a little
1515 relation, and the details don't matter unless you want to comb through
1530 	that this relation is "inverted": It links the end of the
1533 If we think of the rcu-link relation as standing for an extended
1541 The LKMM goes on to define the rcu-order relation as a sequence of
1557 The rcu-order relation is important because the Grace Period Guarantee
1592 The rcu-fence relation is a simple extension of rcu-order.  While
1596 the strong-fence relation links events that are separated by an
1611 Finally, the LKMM defines the RCU-before (rb) relation in terms of
1613 relation was defined in terms of strong-fence.  We will omit the
1618 Guarantee by requiring that the rb relation does not contain a cycle.
1640 relation, and R is po-before the grace period S.  Thus we have:
1654 discussion of the rcu-link relation earlier) that S and U are related
2040 relation (vis), where X ->vis Y is defined to hold if there is an
2410 various relation must not contain a cycle) doesn't apply to plain
2438 contribute to the ppo relation), but at the moment it seems that this
2450 definition of the prop relation makes the initial coe or fre part
2451 optional, and it doesn't require the events linked by the relation to
2490 relation, they do contribute to it indirectly.  Namely, when there is
2497 to undermine this relation if sufficient care is not taken.