D.4.2.3.1 Grace-Period State Machine Overview

The state (recorded in rcu_try_flip_state) can take on the following values:

Figure: Preemptible RCU State Machine
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptStates}}

The grace period state machine cycles through these states sequentially, as shown in Figure [*].

Figure: Preemptible RCU State Machine Timeline
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptTimeline}}

Figure [*] shows how the state machine operates over time. The states are shown along the figure's left-hand side and the relevant events are shown along the timeline, with time proceeding in the downward direction. We will elaborate on this figure when we validate the algorithm in a later section.

In the meantime, here are some important things to note:

  1. The increment of the rcu_ctrlblk.completed counter might be observed at different times by different CPUs, as indicated by the blue oval. However, after a given CPU has acknowledged the increment, it is required to use the new counter. Therefore, once all CPUs have acknowledged, the old counter can only be decremented.
  2. A given CPU advances its callback lists just before acknowledging the counter increment.
  3. The blue oval represents the fact that memory reordering might cause different CPUs to see the increment at different times. This means that a given CPU might believe that some other CPU has jumped the gun, using the new value of the counter before the counter was actually incremented. In fact, in theory, a given CPU might see the next increment of the rcu_ctrlblk.completed counter as early as the last preceding memory barrier. (Note well that this sentence is very imprecise. If you intend to do correctness proofs involving memory barriers, please see Appendix [*].
  4. Because rcu_read_lock() does not contain any memory barriers, the corresponding RCU read-side critical sections might be reordered by the CPU to follow the rcu_read_unlock(). Therefore, the memory barriers are required to ensure that the actions of the RCU read-side critical sections have in fact completed.
  5. As we will see, the fact that different CPUs can see the counter flip happening at different times means that a single trip through the state machine is not sufficient for a grace period: multiple trips are required.

Paul E. McKenney 2011-12-16