Lines Matching full:rcu
30 22. RCU RELATIONS: rcu-link, rcu-gp, rcu-rscsi, rcu-order, rcu-fence, and rb
929 Rcu: This requires that RCU read-side critical sections and
930 grace periods obey the rules of RCU, in particular, the
940 "rcu" and "plain-coherence" axioms are specific to the LKMM.
1513 RCU RELATIONS: rcu-link, rcu-gp, rcu-rscsi, rcu-order, rcu-fence, and rb
1516 RCU (Read-Copy-Update) is a powerful synchronization mechanism. It
1525 As far as memory models are concerned, RCU's main feature is its
1543 Here is a simple example of RCU in action:
1574 In the kernel's implementations of RCU, the requirements for stores
1576 suitable places in the RCU-related code. Thus, if a critical section
1589 rcu-link relation. rcu-link encompasses a very general notion of
1590 "before": If E and F are RCU fence events (i.e., rcu_read_lock(),
1592 E ->rcu-link F includes cases where E is po-before some memory-access
1596 The formal definition of the rcu-link relation is more than a little
1600 about rcu-link is the information in the preceding paragraph.
1602 The LKMM also defines the rcu-gp and rcu-rscsi relations. They bring
1606 E ->rcu-gp F means that E and F are in fact the same event,
1610 E ->rcu-rscsi F means that E and F are the rcu_read_unlock()
1616 If we think of the rcu-link relation as standing for an extended
1617 "before", then X ->rcu-gp Y ->rcu-link Z roughly says that X is a
1621 after X ends.) Similarly, X ->rcu-rscsi Y ->rcu-link Z says that X is
1624 The LKMM goes on to define the rcu-order relation as a sequence of
1625 rcu-gp and rcu-rscsi links separated by rcu-link links, in which the
1626 number of rcu-gp links is >= the number of rcu-rscsi links. For
1629 X ->rcu-gp Y ->rcu-link Z ->rcu-rscsi T ->rcu-link U ->rcu-gp V
1631 would imply that X ->rcu-order V, because this sequence contains two
1632 rcu-gp links and one rcu-rscsi link. (It also implies that
1633 X ->rcu-order T and Z ->rcu-order V.) On the other hand:
1635 X ->rcu-rscsi Y ->rcu-link Z ->rcu-rscsi T ->rcu-link U ->rcu-gp V
1637 does not imply X ->rcu-order V, because the sequence contains only
1638 one rcu-gp link but two rcu-rscsi links.
1640 The rcu-order relation is important because the Grace Period Guarantee
1641 means that rcu-order links act kind of like strong fences. In
1642 particular, E ->rcu-order F implies not only that E begins before F
1646 fence event is linked to itself by rcu-order as a degenerate case.)
1651 G ->rcu-gp W ->rcu-link Z ->rcu-rscsi F.
1673 covered by rcu-order.
1675 The rcu-fence relation is a simple extension of rcu-order. While
1676 rcu-order only links certain fence events (calls to synchronize_rcu(),
1677 rcu_read_lock(), or rcu_read_unlock()), rcu-fence links any events
1678 that are separated by an rcu-order link. This is analogous to the way
1680 smp_mb() fence event (as mentioned above, rcu-order links act kind of
1681 like strong fences). Written symbolically, X ->rcu-fence Y means
1684 X ->po E ->rcu-order F ->po Y.
1688 every CPU before Y executes. Thus rcu-fence is sort of a
1690 synchronize_rcu()), rcu-fence is able to link events on different
1691 CPUs. (Perhaps this fact should lead us to say that rcu-fence isn't
1694 Finally, the LKMM defines the RCU-before (rb) relation in terms of
1695 rcu-fence. This is done in essentially the same way as the pb
1702 Equivalently, this "rcu" axiom requires that there are no events E
1703 and F with E ->rcu-link F ->rcu-order E. Or to put it a third way,
1704 the axiom requires that there are no cycles consisting of rcu-gp and
1705 rcu-rscsi alternating with rcu-link, where the number of rcu-gp links
1706 is >= the number of rcu-rscsi links.
1722 critical section), Q is "before" R in the sense used by the rcu-link
1725 L ->rcu-link S.
1737 discussion of the rcu-link relation earlier) that S and U are related
1738 by rcu-link:
1740 S ->rcu-link U.
1742 Since S is a grace period we have S ->rcu-gp S, and since L and U are
1743 the start and end of the critical section C we have U ->rcu-rscsi L.
1746 S ->rcu-gp S ->rcu-link U ->rcu-rscsi L ->rcu-link S,
1748 a forbidden cycle. Thus the "rcu" axiom rules out this violation of
1752 works out in practice. Consider the RCU code example from above, this
1777 also Y ->po U, we get S ->rcu-link U. In addition, S ->rcu-gp S
1782 yields L ->rcu-link S. And since L and U are the start and end of a
1783 critical section, we have U ->rcu-rscsi L.
1785 Then U ->rcu-rscsi L ->rcu-link S ->rcu-gp S ->rcu-link U is a
1786 forbidden cycle, violating the "rcu" axiom. Hence the outcome is not
1823 that U0 ->rcu-rscsi L0 ->rcu-link S1 ->rcu-gp S1 ->rcu-link U2 ->rcu-rscsi
1824 L2 ->rcu-link U0. However this cycle is not forbidden, because the
1825 sequence of relations contains fewer instances of rcu-gp (one) than of
1826 rcu-rscsi (two). Consequently the outcome is allowed by the LKMM.
1853 normal RCU. The ideas involved are much the same as above, with new
1856 differences between RCU read-side critical sections and their SRCU
1864 sections. They differ from RCU read-side critical sections in the
1867 1. Unlike the analogous RCU primitives, synchronize_srcu(),
1873 another; the SRCU version of the RCU Guarantee applies only
2516 assumption like this one, some usages typical of RCU would count as
2583 Well, normal fences don't -- but rcu-fence can! Here's an example:
2605 before the grace period in P0 does, because RCU's Grace-Period
2609 from the READ_ONCE() to the WRITE_ONCE() gives rise to an rcu-link
2612 This means there is an rcu-fence link from P1's "y = 2" store to P0's
2653 happens-before, propagates-before, and rcu axioms (which state that
2768 Interestingly, RCU and locking each introduce the possibility of