Design/Data-Structures/Data-Structures.rst

20 to execute extremely quickly, while also processing the RCU grace periods
46 grace periods are completed at the tree's root ``rcu_node``
48 A grace period can be completed at the root once every CPU
51 Once a grace period has completed, record of that fact is propagated
102 and scalability benefits of partitioning, even though RCU grace-period
112 there are in the system, at most 64 quiescent-state reports per grace
121 RCU updaters wait for normal grace periods by registering RCU callbacks,
125 while they are waiting for a grace period to elapse, as shown in the
145 example, awareness of the start or end of a given RCU grace period
155    ``rcu_node`` and ``rcu_data`` structures, tracks grace periods,
158    grace-period state, and maintains state used to force quiescent
159    states when grace periods extend too long,
162    propagates grace-period information from the root to the leaves. It
163    provides local copies of the grace-period state in order to allow
172    ignored during a given grace period.
178    copy of the grace-period information to allow for-free synchronized
197 between the ``rcu_node`` and ``rcu_data`` structures, tracks grace
199 and maintains state used to force quiescent states when grace periods
240 macro does. This macro is used at the beginning and ends of grace
274 RCU grace periods are numbered, and the ``->gp_seq`` field contains the
275 current grace-period sequence number. The bottom two bits are the state
276 of the current grace period, which can be zero for not yet started or
285 in order to detect the beginnings and ends of grace periods in a
295 | and update it directly when starting a new grace period?              |
313 | 5. Result: Lots of lock acquisitions with no grace period progress    |
316 | grace period counter without immediately affecting what CPUs see in   |
333 The ``->gp_max`` field tracks the duration of the longest grace period
345 propagates grace-period information from the root down to the leaves.
346 They provides local copies of the grace-period state in order to allow
354 determine which CPUs should be ignored during a given grace period.
426 beginning and the end of each grace period.
428 The ``->gp_seq_needed`` fields record the furthest-in-the-future grace
444 | the end of the grace period. Modulo-arithmetic comparisons therefore  |
465 grace period. Such children will have a value of 1 in their
470 current expedited grace period. An expedited grace period has the same
471 conceptual properties as a normal grace period, but the expedited
473 grace-period latency, for example, consuming a few tens of microseconds
474 worth of CPU time to reduce grace-period duration from milliseconds to
479 expedited grace periods, respectively.
489 | Lockless grace-period computation! Such a tantalizing possibility!    |
493 |    wakes up, it notices that the current RCU grace period needs it to |
504 | #. But CPU 1 beats it to the punch, completing the current grace      |
506 | #. CPU 0 now reports its quiescent state for the wrong grace period.  |
507 |    That grace period might now end before the RCU read-side critical  |
511 | of the bits with updating of the grace-period sequence number in      |
539 one of the tasks is blocking the current grace period, all subsequent
540 tasks must also be blocking that same grace period. Therefore, a single
542 grace period. That pointer is stored in ``->gp_tasks`` for normal grace
543 periods and in ``->exp_tasks`` for expedited grace periods. These last
544 two fields are ``NULL`` if either there is no grace period in flight or
545 if there are no blocked tasks preventing that grace period from
553 RCU read-side critical section, then an expedited grace period started,
555 grace period started, and finally task 3 blocked in an RCU read-side
561 Task T1 is blocking both grace periods, task T2 is blocking only the
562 normal grace period, and task T3 is blocking neither grace period. Note
569 grace period is waiting on a blocked task.
724 #. ``RCU_DONE_TAIL``: Callbacks whose grace periods have elapsed. These
726 #. ``RCU_WAIT_TAIL``: Callbacks that are waiting for the current grace
728    grace period is current, hence the ``->gp_seq`` field.
729 #. ``RCU_NEXT_READY_TAIL``: Callbacks waiting for the next grace period
732    grace period.
753 are both waiting on the current grace period, give or take possible
754 disagreements about exactly which grace period is the current one. The
757 there are no callbacks waiting on the next RCU grace period. The
760 been assigned to an RCU grace period. Note that the
773 ``RCU_DONE_TAIL`` list segments as grace periods advance.
775 The ``->gp_seq[]`` array records grace-period numbers corresponding to
777 ideas as to which is the current grace period while still avoiding
822 copy of the grace-period information to allow for-free synchronized
882 | All this replication of the grace period numbers can only cause       |
893 | a previously sampled quiescent state to the wrong grace period are    |
930 whenever it notices that another RCU grace period has completed. The CPU
931 detects the completion of an RCU grace period by noticing that the value
935 each grace period.
1047 algorithms use asynchronous grace periods. In contrast, when using
1048 algorithms that block waiting for RCU grace periods, RCU users need not
1118 tasks-RCU grace period, ``->rcu_tasks_holdout`` is set if the current
1119 tasks-RCU grace period is waiting on this task,