memory-model/Documentation/explanation.txt

30   22. RCU RELATIONS: rcu-link, rcu-gp, rcu-rscsi, rcu-order, rcu-fence, and rb
876 	Rcu: This requires that RCU read-side critical sections and
877 	grace periods obey the rules of RCU, in particular, the
887 "rcu" and "plain-coherence" axioms are specific to the LKMM.
1430 RCU RELATIONS: rcu-link, rcu-gp, rcu-rscsi, rcu-order, rcu-fence, and rb
1433 RCU (Read-Copy-Update) is a powerful synchronization mechanism.  It
1442 As far as memory models are concerned, RCU's main feature is its
1460 Here is a simple example of RCU in action:
1491 In the kernel's implementations of RCU, the requirements for stores
1493 suitable places in the RCU-related code.  Thus, if a critical section
1506 rcu-link relation.  rcu-link encompasses a very general notion of
1507 "before": If E and F are RCU fence events (i.e., rcu_read_lock(),
1509 E ->rcu-link F includes cases where E is po-before some memory-access
1513 The formal definition of the rcu-link relation is more than a little
1517 about rcu-link is the information in the preceding paragraph.
1519 The LKMM also defines the rcu-gp and rcu-rscsi relations.  They bring
1523 	E ->rcu-gp F means that E and F are in fact the same event,
1527 	E ->rcu-rscsi F means that E and F are the rcu_read_unlock()
1533 If we think of the rcu-link relation as standing for an extended
1534 "before", then X ->rcu-gp Y ->rcu-link Z roughly says that X is a
1538 after X ends.)  Similarly, X ->rcu-rscsi Y ->rcu-link Z says that X is
1541 The LKMM goes on to define the rcu-order relation as a sequence of
1542 rcu-gp and rcu-rscsi links separated by rcu-link links, in which the
1543 number of rcu-gp links is >= the number of rcu-rscsi links.  For
1546 	X ->rcu-gp Y ->rcu-link Z ->rcu-rscsi T ->rcu-link U ->rcu-gp V
1548 would imply that X ->rcu-order V, because this sequence contains two
1549 rcu-gp links and one rcu-rscsi link.  (It also implies that
1550 X ->rcu-order T and Z ->rcu-order V.)  On the other hand:
1552 	X ->rcu-rscsi Y ->rcu-link Z ->rcu-rscsi T ->rcu-link U ->rcu-gp V
1554 does not imply X ->rcu-order V, because the sequence contains only
1555 one rcu-gp link but two rcu-rscsi links.
1557 The rcu-order relation is important because the Grace Period Guarantee
1558 means that rcu-order links act kind of like strong fences.  In
1559 particular, E ->rcu-order F implies not only that E begins before F
1563 fence event is linked to itself by rcu-order as a degenerate case.)
1568 	G ->rcu-gp W ->rcu-link Z ->rcu-rscsi F.
1590 covered by rcu-order.
1592 The rcu-fence relation is a simple extension of rcu-order.  While
1593 rcu-order only links certain fence events (calls to synchronize_rcu(),
1594 rcu_read_lock(), or rcu_read_unlock()), rcu-fence links any events
1595 that are separated by an rcu-order link.  This is analogous to the way
1597 smp_mb() fence event (as mentioned above, rcu-order links act kind of
1598 like strong fences).  Written symbolically, X ->rcu-fence Y means
1601 	X ->po E ->rcu-order F ->po Y.
1605 every CPU before Y executes.  Thus rcu-fence is sort of a
1607 synchronize_rcu()), rcu-fence is able to link events on different
1608 CPUs.  (Perhaps this fact should lead us to say that rcu-fence isn't
1611 Finally, the LKMM defines the RCU-before (rb) relation in terms of
1612 rcu-fence.  This is done in essentially the same way as the pb
1619 Equivalently, this "rcu" axiom requires that there are no events E
1620 and F with E ->rcu-link F ->rcu-order E.  Or to put it a third way,
1621 the axiom requires that there are no cycles consisting of rcu-gp and
1622 rcu-rscsi alternating with rcu-link, where the number of rcu-gp links
1623 is >= the number of rcu-rscsi links.
1639 critical section), Q is "before" R in the sense used by the rcu-link
1642 	L ->rcu-link S.
1654 discussion of the rcu-link relation earlier) that S and U are related
1655 by rcu-link:
1657 	S ->rcu-link U.
1659 Since S is a grace period we have S ->rcu-gp S, and since L and U are
1660 the start and end of the critical section C we have U ->rcu-rscsi L.
1663 	S ->rcu-gp S ->rcu-link U ->rcu-rscsi L ->rcu-link S,
1665 a forbidden cycle.  Thus the "rcu" axiom rules out this violation of
1669 works out in practice.  Consider the RCU code example from above, this
1694 also Y ->po U, we get S ->rcu-link U.  In addition, S ->rcu-gp S
1699 yields L ->rcu-link S.  And since L and U are the start and end of a
1700 critical section, we have U ->rcu-rscsi L.
1702 Then U ->rcu-rscsi L ->rcu-link S ->rcu-gp S ->rcu-link U is a
1703 forbidden cycle, violating the "rcu" axiom.  Hence the outcome is not
1740 that U0 ->rcu-rscsi L0 ->rcu-link S1 ->rcu-gp S1 ->rcu-link U2 ->rcu-rscsi
1741 L2 ->rcu-link U0.  However this cycle is not forbidden, because the
1742 sequence of relations contains fewer instances of rcu-gp (one) than of
1743 rcu-rscsi (two).  Consequently the outcome is allowed by the LKMM.
1770 addition to normal RCU.  The ideas involved are much the same as
1774 rcu-order sequence (the srcu-rscsi links must be paired with srcu-gp
2272 assumption like this one, some usages typical of RCU would count as
2339 Well, normal fences don't -- but rcu-fence can!  Here's an example:
2361 before the grace period in P0 does, because RCU's Grace-Period
2365 from the READ_ONCE() to the WRITE_ONCE() gives rise to an rcu-link
2368 This means there is an rcu-fence link from P1's "y = 2" store to P0's
2409 happens-before, propagates-before, and rcu axioms (which state that
2517 Interestingly, RCU and locking each introduce the possibility of