Design/Data-Structures/Data-Structures.rst

2 A Tour Through TREE_RCU's Data Structures [LWN.net]
12 This document describes RCU's major data structures and their relationship
19 data structures maintain the state in such a way as to allow RCU readers
28 of ``rcu_node`` structures. Each leaf node of the ``rcu_node`` tree has up
29 to 16 ``rcu_data`` structures associated with it, so that there are
30 ``NR_CPUS`` number of ``rcu_data`` structures, one for each possible CPU.
42 Quiescent states are recorded by the per-CPU ``rcu_data`` structures,
44 structures.
66 | ``rcu_node`` structures than further up the tree. Therefore, if the   |
67 | leaf ``rcu_node`` structures have fanout of 64, the contention on     |
68 | these structures' ``->structures`` becomes excessive. Experimentation |
74 | ``rcu_node`` structures must also be reduced. Such reduction can be   |
77 | on the non-leaf ``rcu_node`` structures, you may use the              |
83 | the ``rcu_node`` structures align with hardware boundaries.           |
108 internal ``rcu_node`` structures, the situation is even more extreme:
124 ``rcu_head`` structures, which are queued on ``rcu_data`` structures
131 structures are related. Lesser data structures will be introduced with
134 Note that each of the data structures in the above figure has its own
137 #. Each ``rcu_state`` structures has a lock and a mutex, and some fields
143 It is important to note that different data structures can have very
146 propagates slowly through the data structures. This slow propagation is
149 consider each instance of these data structures to be a different
152 The general role of each of these data structures is as follows:
155    ``rcu_node`` and ``rcu_data`` structures, tracks grace periods,
188 data structures are related, you are done. Otherwise, each of the
190 and ``rcu_data`` data structures.
197 between the ``rcu_node`` and ``rcu_data`` structures, tracks grace
206 Relationship to rcu_node and rcu_data Structures
220 | Wait a minute! You said that the ``rcu_node`` structures formed a     |
283 structures as well. The fields in the ``rcu_state`` structure represent
284 the most current value, and those of the other structures are compared
310 The ``rcu_node`` structures form the combining tree that propagates
386 The ``rcu_node`` structures' ``->gp_seq`` fields are the counterparts of
433 corresponding bit. Note that the leaf ``rcu_node`` structures should be
434 thought of as having ``rcu_data`` structures as their children.
500 critical sections, their ``task_struct`` structures are enqueued (via
636 excessive contention for the leaf ``rcu_node`` structures' ``->lock``
652 spanning lines 26-66 that computes the number of ``rcu_node`` structures
656 ``rcu_node`` structures for the topmost level of the tree is always
797 Connection to Other Data Structures
836 in the ``rcu_state`` and ``rcu_node`` structures. The
1012 Each ``rcu_head`` structure represents an RCU callback. These structures
1013 are normally embedded within RCU-protected data structures whose
1016 provide ``rcu_head`` structures.
1025 The ``->next`` field is used to link the ``rcu_head`` structures
1026 together in the lists within the ``rcu_data`` structures. The ``->func``
1119 advantage of the layout of the ``rcu_node`` structures in the
1123 array, thus traversing only the leaf ``rcu_node`` structures.
1141 contains a combining tree of ``rcu_node`` and ``rcu_data`` structures.