D.2.6 State Machine

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

At a sufficiently high level, Linux-kernel RCU implementations can be thought of as high-level state machines as shown in Figure [*]. The common-case path through this state machine on a busy system goes through the two uppermost loops, initializing at the beginning of each grace period (GP), waiting for quiescent states (QS), and noting when each CPU passes through its first quiescent state for a given grace period. On such a system, quiescent states will occur on each context switch, or, for CPUs that are either idle or executing user-mode code, each scheduling-clock interrupt. CPU-hotplug events will take the state machine through the ``CPU Offline'' box, while the presence of ``holdout'' CPUs that fail to pass through quiescent states quickly enough will exercise the path through the ``Send resched IPIs to Holdout CPUs'' box. RCU implementations that avoid unnecessarily awakening dyntick-idle CPUs will mark those CPUs as being in an extended quiescent state, taking the ``Y'' branch out of the ``CPUs in dyntick-idle Mode?'' decision diamond (but note that CPUs in dyntick-idle mode will not be sent resched IPIs). Finally, if CONFIG_RCU_CPU_STALL_DETECTOR is enabled, truly excessive delays in reaching quiescent states will exercise the ``Complain About Holdout CPUs'' path.

Quick Quiz D.10: But doesn't this state diagram indicate that dyntick-idle CPUs will get hit with reschedule IPIs? Won't that wake them up? End Quick Quiz

Figure: RCU State Machine and Hierarchical RCU Data Structures
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/TreeRCUStateMachine}}

The events in the above state schematic interact with different data structures, as shown in Figure [*]. However, the state schematic does not directly translate into C code for any of the RCU implementations. Instead, these implementations are coded as an event-driven system within the kernel. Therefore, the following section describes some ``use cases'', or ways in which the RCU algorithm traverses the above state schematic as well as the relevant data structures.

Paul E. McKenney 2011-12-16