D.3.3 Initialization

Figure: Initialized RCU Data Layout
\resizebox{6in}{!}{\includegraphics{appendix/rcuimpl/RCUTreeInit}}

This section walks through the initialization code, which links the main data structures together as shown in Figure [*]. The yellow region represents fields in the rcu_state data structure, including the ->node array, individual elements of which are shown in pink, matching the convention used in Section [*]. The blue boxes each represent one rcu_data structure, and the group of blue boxes makes up a set of per-CPU rcu_data structures.

The ->levelcnt[] array is initialized at compile time, as is ->level[0], but the rest of the values and pointers are filled in by the functions described in the following sections. The figure shows a two-level hierarchy, but one-level and three-level hierarchies are possible as well. Each element of the ->levelspread[] array gives the number of children per node at the corresponding level of the hierarchy. In the figure, therefore, the root node has two children and the nodes at the leaf level each have three children. Each element of the levelcnt[] array indicates how many nodes there are on the corresponding level of the hierarchy: 1 at the root level, 2 at the leaf level, and 6 at the rcu_data level--and any extra elements are unused and left as zero. Each element of the ->level[] array references the first node of the corresponding level of the rcu_node hierarchy, and each element of the ->rda[] array references the corresponding CPU's rcu_data structure. The ->parent field of each rcu_node structure references its parent, except for the root rcu_node structure, which has a NULL ->parent pointer. Finally, the ->mynode field of each rcu_data structure references its parent rcu_node structure.

Quick Quiz D.33: How does the code traverse a given path through the rcu_node hierarchy from root to leaves? End Quick Quiz

Again, the following sections walk through the code that builds this structure.



Subsections
Paul E. McKenney 2011-12-16