D.3.1.4 RCU Global State
Keywords: perfbook_html

###
D.3.1.4 RCU Global State

The rcu_state structure contains RCU's global state for each instance of RCU (rcu and rcu_bh). It includes fields relating to the hierarchy of rcu_node structures, including the node array itself, the level array that contains pointers to the levels of the hierarchy, the levelcnt array that contains the count of nodes at each level of the hierarchy, the levelspread array that contains the number of children per node for each level of the hierarchy, and the rda array of pointer to each of the CPU's rcu_data structures. The rcu_state structure also contains a number of fields coordinating various details of the current grace period and its interaction with other mechanisms (signaled, gpnum, completed, onofflock, fqslock, jiffies_force_qs, n_force_qs, n_force_qs_lh, n_force_qs_ngp, gp_start, jiffies_stall, and dynticks_completed).

Each of these fields are described below.

- node: This field is the array of rcu_node structures, with the root node of the hierarchy being located at ->node[0]. The size of this array is specified by the NUM_RCU_NODES C-preprocessor macro, which is computed from NR_CPUS and CONFIG_RCU_FANOUT as described in Section . Note that traversing the ->node array starting at element zero has the effect of doing a breadth-first search of the rcu_node hierarchy.
- level: This field is an array of pointers into the node array. The root node of the hierarchy is referenced by ->level[0], the first node of the second level of the hierarchy (if there is one) by ->level[1], and so on. The first leaf node is referenced by ->level[NUM_RCU_LVLS-1], and the size of the level array is thus specified by NUM_RCU_LVLS, which is computed as described in Section . The ->level field is often used in combination with ->node to scan a level of the rcu_node hierarchy, for example, all of the leaf nodes. The elements of ->level are filled in by the boot-time rcu_init_one() function.
- levelcnt: This field is an array containing the number of rcu_node structures in each level of the hierarchy, including the number of rcu_data structures referencing the leaf rcu_node structures, so that this array has one more element than does the ->level array. Note that ->levelcnt[0] will always contain a value of one, corresponding to the single root rcu_node at the top of the hierarchy. This array is initialized with the values NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, and NUM_RCU_LVL_3, which are C-preprocessor macros computed as described in Section . The ->levelcnt field is used to initialize other parts of the hierarchy and for debugging purposes.
- levelspread: Each element of this field contains the desired number of children for the corresponding level of the rcu_node hierarchy. This array's element's values are computed at runtime by one of the two rcu_init_levelspread() functions, selected by the CONFIG_RCU_FANOUT_EXACT kernel parameter.
- rda: Each element of this field contains a pointer to the corresponding CPU's rcu_data structure. This array is initialized at boot time by the RCU_DATA_PTR_INIT() macro.
- signaled: This field is used to maintain state used by the force_quiescent_state() function, as described in Section . This field takes on values as follows:
  - RCU_GP_INIT: This value indicates that the current grace period is still in the process of being initialized, so that force_quiescent_state() should take no action. Of course, grace-period initialization would need to stretch out for three jiffies before this race could arise, but if you have a very large number of CPUs, this race could in fact occur. Once grace-period initialization is complete, this value is set to either RCU_SAVE_DYNTICK (if CONFIG_NO_HZ) or RCU_FORCE_QS otherwise.
  - RCU_SAVE_DYNTICK: This value indicates that force_quiescent_state() should check the dynticks state of any CPUs that have not yet reported quiescent states for the current grace period. Quiescent states will be reported on behalf of any CPUs that are in dyntick-idle mode.
  - RCU_FORCE_QS: This value indicates that force_quiescent_state() should recheck dynticks state along with the online/offline state of any CPUs that have not yet reported quiescent states for the current grace period. The rechecking of dynticks states allows the implementation to handle cases where a given CPU might be in dynticks-idle state, but have been in an irq or NMI handler both times it was checked. If all else fails, a reschedule IPI will be sent to the laggard CPU.
  This field is guarded by the root rcu_node structure's lock.

  Quick Quiz D.26: So what guards the earlier fields in this structure? End Quick Quiz

- gpnum: This field contains the number of the current grace period, or that of the last grace period if no grace period is currently in effect. This field is guarded by the root rcu_node structure's lock, but is frequently accessed (but never modified) without holding this lock.
- completed: This field contains the number of the last completed grace period. As such, it is equal to ->gpnum when there is no grace period in progress, or one less than ->gpnum when there is a grace period in progress. In principle, one could replace this pair of fields with a single boolean, as is done in Classic RCU in some versions of Linux, but in practice race resolution is much simpler given the pair of numbers. This field is guarded by the root rcu_node structure's lock, but is frequently accessed (but never modified) without holding this lock.
- onofflock: This field prevents online/offline processing from running concurrently with grace-period initialization. There is one exception to this: if the rcu_node hierarchy consists of but a single structure, then that single structure's ->lock field will instead take on this job.
- fqslock: This field prevents more than one task from forcing quiescent states with force_quiescent_state().
- jiffies_force_qs: This field contains the time, in jiffies, when force_quiescent_state() should be invoked in order to force CPUs into quiescent states and/or report extended quiescent states. This field is guarded by the root rcu_node structure's lock, but is frequently accessed (but never modified) without holding this lock.
- n_force_qs: This field counts the number of calls to force_quiescent_state() that actually do work, as opposed to leaving early due to the grace period having already completed, some other CPU currently running force_quiescent_state(), or force_quiescent_state() having run too recently. This field is used for tracing and debugging, and is guarded by ->fqslock.
- n_force_qs_lh: This field holds an approximate count of the number of times that force_quiescent_state() returned early due to the ->fqslock being held by some other CPU. This field is used for tracing and debugging, and is not guarded by any lock, hence its approximate nature.
- n_force_qs_ngp: This field counts the number of times that force_quiescent_state() that successfully acquire ->fqslock, but then find that there is no grace period in progress. This field is used for tracing and debugging, and is guarded by ->fqslock.
- gp_start: This field records the time at which the most recent grace period began, in jiffies. This is used to detect stalled CPUs, but only when the CONFIG_RCU_CPU_STALL_DETECTOR kernel parameter is selected. This field is guarded by the root rcu_node's ->lock, but is sometimes accessed (but not modified) outside of this lock.
- jiffies_stall: This field holds the time, in jiffies, at which the current grace period will have extended for so long that it will be appropriate to check for CPU stalls. As with ->gp_start, this field exists only when the CONFIG_RCU_CPU_STALL_DETECTOR kernel parameter is selected. This field is guarded by the root rcu_node's ->lock, but is sometimes accessed (but not modified) outside of this lock.
- dynticks_completed: This field records the value of ->completed at the time when force_quiescent_state() snapshots dyntick state, but is also initialized to an earlier grace period at the beginning of each grace period. This field is used to prevent dyntick-idle quiescent states from a prior grace period from being applied to the current grace period. As such, this field exists only when the CONFIG_NO_HZ kernel parameter is selected. This field is guarded by the root rcu_node's ->lock, but is sometimes accessed (but not modified) outside of this lock.