Design/Data-Structures/Data-Structures.rst

27 This diagram shows an enclosing ``rcu_state`` structure containing a tree
31 This structure is adjusted at boot time, if needed, to handle the common
47 structure.
105 structure need advance to the ``rcu_node`` structure at the next level
106 up the tree. This means that at the leaf-level ``rcu_node`` structure,
113 period will progress all the way to the root ``rcu_node`` structure,
115 structure remains acceptably low.
138    are protected by the corresponding root ``rcu_node`` structure's lock.
139 #. Each ``rcu_node`` structure has a spinlock.
154 #. ``rcu_state``: This structure forms the interconnection between the
160 #. ``rcu_node``: This structure forms the combining tree that propagates
173 #. ``rcu_data``: This per-CPU structure is the focus of quiescent-state
175    to the corresponding leaf ``rcu_node`` structure to allow
177    combining tree. Like the ``rcu_node`` structure, it provides a local
180    structure records past dyntick-idle state for the corresponding CPU
182 #. ``rcu_head``: This structure represents RCU callbacks, and is the
183    only structure allocated and managed by RCU users. The ``rcu_head``
184    structure is normally embedded within the RCU-protected data
185    structure.
195 The ``rcu_state`` structure is the base structure that represents the
196 state of RCU in the system. This structure forms the interconnection
202 A few of the ``rcu_state`` structure's fields are discussed, singly and
209 This portion of the ``rcu_state`` structure is declared as follows:
244 structure on the corresponding level of the tree, for example, as shown
250 ``rcu_node`` structure, the first element references the first child of
252 first leaf ``rcu_node`` structure.
260 corresponding CPU's ``rcu_data`` structure.
268 This portion of the ``rcu_state`` structure is declared as follows:
280 the root ``rcu_node`` structure's ``->lock`` field.
283 structures as well. The fields in the ``rcu_state`` structure represent
292 | Given that the root rcu_node structure has a gp_seq field,            |
293 | why does RCU maintain a separate gp_seq in the rcu_state structure?   |
325 This portion of the ``rcu_state`` structure is declared as follows:
356 The ``rcu_node`` structure's fields are discussed, singly and in groups,
362 This portion of the ``rcu_node`` structure is declared as follows:
384 ``rcu_node`` structure in its parent's bitmasks, which are described
386 lowest and highest numbered CPU served by this ``rcu_node`` structure,
395 This field of the ``rcu_node`` structure is declared as follows:
401 This field is used to protect the remaining fields in this structure,
402 unless otherwise stated. That said, all of the fields in this structure
412 This portion of the ``rcu_node`` structure is declared as follows:
420 the field of the same name in the ``rcu_state`` structure. They each may
422 two bits of a given ``rcu_node`` structure's ``->gp_seq`` field is zero,
423 then this ``rcu_node`` structure believes that RCU is idle.
425 The ``>gp_seq`` field of each ``rcu_node`` structure is updated at the
429 period request seen by the corresponding ``rcu_node`` structure. The
436 | Suppose that this ``rcu_node`` structure doesn't see a request for a  |
454 This portion of the ``rcu_node`` structure has fields as follows:
463 The ``->qsmask`` field tracks which of this ``rcu_node`` structure's
469 structure's children still need to report quiescent states for the
476 ``rcu_node`` structure's children cover for at least one online CPU.
522 know that the ``rcu_node`` structure tracks them.
535 ``->blkd_tasks`` list for the leaf ``rcu_node`` structure corresponding
557 structure's blocked-task list would be as shown below:
646 The maximum number of levels in the ``rcu_node`` structure is currently
647 limited to four, as specified by lines 21-24 and the structure of the
666 each leaf ``rcu_node`` structure. Experience has shown that allowing a
667 given leaf ``rcu_node`` structure to handle 64 CPUs, as permitted by the
670 fields. The number of CPUs per leaf ``rcu_node`` structure is therefore
677 single-level (which contains a single ``rcu_node`` structure),
703 The ``rcu_segcblist`` structure maintains a segmented list of callbacks
791    structure, *not* the ``->head`` pointer. The reason for this is that all
806 ``->len`` count is zero only if the ``rcu_segcblist`` structure really
816 fields in this structure may be accessed only from the corresponding CPU
817 (and from tracing) unless otherwise stated. This structure is the focus
819 its relationship to the corresponding leaf ``rcu_node`` structure to
821 combining tree. Like the ``rcu_node`` structure, it provides a local
824 structure records past dyntick-idle state for the corresponding CPU and
827 The ``rcu_data`` structure's fields are discussed, singly and in groups,
833 This portion of the ``rcu_data`` structure is declared as follows:
843 ``->mynode`` field references the corresponding ``rcu_node`` structure.
849 corresponding to this ``rcu_data`` structure, and is also used when
852 need not dump out any ``rcu_data`` structure for which this flag is not
858 This portion of the ``rcu_data`` structure is declared as follows:
871 name in the rcu_node structure. They may each lag up to one behind their
876 structure's ``->gp_seq`` are zero, then this ``rcu_data`` structure
915 This portion of the ``rcu_data`` structure is declared as follows:
928 The ``->cblist`` structure is the segmented callback list described
929 earlier. The CPU advances the callbacks in its ``rcu_data`` structure
932 of its ``rcu_data`` structure's ``->gp_seq`` field differs from that of
933 its leaf ``rcu_node`` structure. Recall that each ``rcu_node``
934 structure's ``->gp_seq`` field is updated at the beginnings and ends of
953 This portion of the ``rcu_data`` structure is declared as follows:
967 This portion of the rcu_data structure is declared as follows:
977 These fields in the rcu_data structure maintain the per-CPU dyntick-idle
1045 Each ``rcu_head`` structure represents an RCU callback. These structures
1051 The ``rcu_head`` structure has fields as follows:
1062 ``rcu_head`` structure. However, ``kfree_rcu()`` uses the ``->func``
1063 field to record the offset of the ``rcu_head`` structure within the
1064 enclosing RCU-protected data structure.
1067 RCU users, this structure is an opaque “cookie”.
1073 | the ``rcu_head`` structure, how is that function supposed to find the |
1074 | beginning of the enclosing RCU-protected data structure?              |
1079 | RCU-protected data structure. The callback function can therefore use |
1082 | find the beginning of the enclosing structure.                        |
1089 the ``task_struct`` structure:
1112 ``->rcu_blocked_node`` field references the ``rcu_node`` structure whose
1148 the specified ``rcu_state`` structure's ``->node[]`` array, which is the
1149 root ``rcu_node`` structure.
1153 ``rcu_state`` structure's ``->node[]`` array, performing a breadth-first
1173 So the state of RCU is represented by an ``rcu_state`` structure, which
1176 is tracked by dynticks-related fields in the ``rcu_data`` structure. If