Design/Data-Structures/Data-Structures.rst

28 of ``rcu_node`` structures. Each leaf node of the ``rcu_node`` tree has up
34 which results in a three-level ``rcu_node`` tree.
36 at boot time, resulting in an ``rcu_node`` tree with only a single node.
43 and other events are recorded by the leaf-level ``rcu_node``
46 grace periods are completed at the tree's root ``rcu_node``
66 | ``rcu_node`` structures than further up the tree. Therefore, if the   |
67 | leaf ``rcu_node`` structures have fanout of 64, the contention on     |
70 | for the leaves of the ``rcu_node`` tree.                              |
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.           |
90 65,536 CPUs, RCU would configure the ``rcu_node`` tree as follows:
104 the last CPU to report a quiescent state into a given ``rcu_node``
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,
108 internal ``rcu_node`` structures, the situation is even more extreme:
113 period will progress all the way to the root ``rcu_node`` structure,
114 thus ensuring that the lock contention on that root ``rcu_node``
138    are protected by the corresponding root ``rcu_node`` structure's lock.
139 #. Each ``rcu_node`` structure has a spinlock.
155    ``rcu_node`` and ``rcu_data`` structures, tracks grace periods,
160 #. ``rcu_node``: This structure forms the combining tree that propagates
169    ``CONFIG_RCU_BOOST``, it manages the per-\ ``rcu_node``
175    to the corresponding leaf ``rcu_node`` structure to allow
176    more-efficient propagation of quiescent states up the ``rcu_node``
177    combining tree. Like the ``rcu_node`` structure, it provides a local
189 following sections give more details on the ``rcu_state``, ``rcu_node``
197 between the ``rcu_node`` and ``rcu_data`` structures, tracks grace
206 Relationship to rcu_node and rcu_data Structures
213      1   struct rcu_node node[NUM_RCU_NODES];
214      2   struct rcu_node *level[NUM_RCU_LVLS + 1];
220 | Wait a minute! You said that the ``rcu_node`` structures formed a     |
232 The ``rcu_node`` tree is embedded into the ``->node[]`` array as shown
243 Each entry of the ``->level`` array references the first ``rcu_node``
250 ``rcu_node`` structure, the first element references the first child of
251 the root ``rcu_node``, and finally the second element references the
252 first leaf ``rcu_node`` structure.
280 the root ``rcu_node`` structure's ``->lock`` field.
282 There are ``->gp_seq`` fields in the ``rcu_node`` and ``rcu_data``
286 distributed fashion. The values flow from ``rcu_state`` to ``rcu_node``
292 | Given that the root rcu_node structure has a gp_seq field,            |
294 | Why not just use the root rcu_node's gp_seq as the official record    |
334 in jiffies. It is protected by the root ``rcu_node``'s ``->lock``.
340 The ``rcu_node`` Structure
343 The ``rcu_node`` structures form the combining tree that propagates
352 manage the per-\ ``rcu_node`` priority-boosting kernel threads
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:
366      1   struct rcu_node *parent;
373 The ``->parent`` pointer references the ``rcu_node`` one level up in the
374 tree, and is ``NULL`` for the root ``rcu_node``. The RCU implementation
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:
412 This portion of the ``rcu_node`` structure is declared as follows:
419 The ``rcu_node`` structures' ``->gp_seq`` fields are the counterparts of
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
466 corresponding bit. Note that the leaf ``rcu_node`` structures should be
468 Similarly, the ``->expmask`` field tracks which of this ``rcu_node``
476 ``rcu_node`` structure's children cover for at least one online CPU.
503 |    its quiescent state up the ``rcu_node`` tree.                      |
522 know that the ``rcu_node`` structure tracks them.
535 ``->blkd_tasks`` list for the leaf ``rcu_node`` structure corresponding
556 critical section, then the state of the last leaf ``rcu_node``
571 Sizing the ``rcu_node`` Array
574 The ``rcu_node`` array is sized via a series of C-preprocessor
646 The maximum number of levels in the ``rcu_node`` structure is currently
656 ``rcu_node`` boundaries). In addition, building kernels with a full four
657 levels of ``rcu_node`` tree permits better testing of RCU's
661 each non-leaf level of the ``rcu_node`` tree. If 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
669 excessive contention for the leaf ``rcu_node`` structures' ``->lock``
670 fields. The number of CPUs per leaf ``rcu_node`` structure is therefore
677 single-level (which contains a single ``rcu_node`` structure),
678 two-level, three-level, and four-level ``rcu_node`` tree, respectively,
685 spanning lines 26-66 that computes the number of ``rcu_node`` structures
689 ``rcu_node`` structures for the topmost level of the tree is always
692 (if any) of the ``rcu_node`` tree are computed by dividing the maximum
819 its relationship to the corresponding leaf ``rcu_node`` structure to
820 allow more-efficient propagation of quiescent states up the ``rcu_node``
821 combining tree. Like the ``rcu_node`` structure, it provides a local
838      2   struct rcu_node *mynode;
843 ``->mynode`` field references the corresponding ``rcu_node`` structure.
869 in the ``rcu_state`` and ``rcu_node`` structures. The
871 name in the rcu_node structure. They may each lag up to one behind their
872 ``rcu_node`` counterparts, but in ``CONFIG_NO_HZ_IDLE`` and
933 its leaf ``rcu_node`` structure. Recall that each ``rcu_node``
1097     5   struct rcu_node *rcu_blocked_node;
1112 ``->rcu_blocked_node`` field references the ``rcu_node`` structure whose
1134      1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
1149 root ``rcu_node`` structure.
1152 advantage of the layout of the ``rcu_node`` structures in the
1156 array, thus traversing only the leaf ``rcu_node`` structures.
1161 | What does ``rcu_for_each_leaf_node()`` do if the ``rcu_node`` tree    |
1174 contains a combining tree of ``rcu_node`` and ``rcu_data`` structures.