| blob | 7eb47ac25ad772bdc25b812e016982d974752f8c |
3 <html>
12 This document describes RCU's major data structures and their relationship
13 to each other.
15 <ol>
17 Data-Structure Relationships</a>
31 Accessor Functions</a>
32 </ol>
34 At the end we have the
39 <p>RCU is for all intents and purposes a large state machine, and its
40 data structures maintain the state in such a way as to allow RCU readers
41 to execute extremely quickly, while also processing the RCU grace periods
42 requested by updaters in an efficient and extremely scalable fashion.
43 The efficiency and scalability of RCU updaters is provided primarily
44 by a combining tree, as shown below:
53 one for each possible CPU.
54 This structure is adjusted at boot time, if needed, to handle the
59 If the actual hardware has only 16 CPUs, RCU will adjust itself
62 </p><p>The purpose of this combining tree is to allow per-CPU events
63 such as quiescent states, dyntick-idle transitions,
64 and CPU hotplug operations to be processed efficiently
65 and scalably.
68 structures.
69 All of these events are combined at each level of the tree until finally
71 structure.
72 A grace period can be completed at the root once every CPU
74 has passed through a quiescent state.
75 Once a grace period has completed, record of that fact is propagated
76 back down the tree.
82 <table>
85 <tr><td>
86 Why isn't the fanout at the leaves also 64?
87 </td></tr>
90 Because there are more types of events that affect the leaf-level
94 becomes excessive.
95 Experimentation on a wide variety of systems has shown that a fanout
97 </font>
100 systems having hundreds or thousands of CPUs may demonstrate
102 must also be reduced.
103 Such reduction can be easily carried out when and if it proves
104 necessary.
105 In the meantime, if you are using such a system and running into
108 parameter to reduce the non-leaf fanout as needed.
109 </font>
112 strong NUMA characteristics might also need to adjust
115 However, there has thus far been no need for this.
116 </font></td></tr>
118 </table>
121 a 32-bit system), then RCU will automatically add more levels to the
122 tree.
130 32-bit systems.
133 is useful for testing.
135 </p><p>This multi-level combining tree allows us to get most of the
136 performance and scalability
137 benefits of partitioning, even though RCU grace-period detection is
138 inherently a global operation.
139 The trick here is that only the last CPU to report a quiescent state
141 structure at the next level up the tree.
143 one access out of sixteen will progress up the tree.
145 more extreme: Only one access out of sixty-four will progress up
146 the tree.
147 Because the vast majority of the CPUs do not progress up the tree,
148 the lock contention remains roughly constant up the tree.
149 No matter how many CPUs there are in the system, at most 64 quiescent-state
150 reports per grace period will progress all the way to the root
154 </p><p>In effect, the combining tree acts like a big shock absorber,
155 keeping lock contention under control at all tree levels regardless
156 of the level of loading on the system.
158 </p><p>The Linux kernel actually supports multiple flavors of RCU
159 running concurrently, so RCU builds separate data structures for each
160 flavor.
162 rcu_sched and rcu_bh, as shown below:
166 </p><p>Energy efficiency is increasingly important, and for that
168 turns off the scheduling-clock interrupts on idle CPUs, which in
169 turn allows those CPUs to attain deeper sleep states and to consume
170 less energy.
171 CPUs whose scheduling-clock interrupts have been turned off are
173 RCU must handle dyntick-idle CPUs specially
174 because RCU would otherwise wake up each CPU on every grace period,
177 which CPUs are in dyntick idle mode, as shown below:
179 </p><p><img src="BigTreeClassicRCUBHdyntick.svg" alt="BigTreeClassicRCUBHdyntick.svg" width="33%">
181 </p><p>However, if a CPU is in dyntick-idle mode, it is in that mode
182 for all flavors of RCU.
188 rcu_preempt in addition to rcu_sched and rcu_bh, as shown below:
190 </p><p><img src="BigTreePreemptRCUBHdyntick.svg" alt="BigTreePreemptRCUBHdyntick.svg" width="35%">
192 </p><p>RCU updaters wait for normal grace periods by registering
195 there being a separate interface per flavor of RCU)
199 waiting for a grace period to elapse, as shown in the following figure:
201 </p><p><img src="BigTreePreemptRCUBHdyntickCB.svg" alt="BigTreePreemptRCUBHdyntickCB.svg" width="40%">
205 Lesser data structures will be introduced with the algorithms that
206 make use of them.
208 </p><p>Note that each of the data structures in the above figure has
209 its own synchronization:
211 <p><ol>
213 and some fields are protected by the corresponding root
217 CPU, although a few can be read and written by other CPUs.
219 to the corresponding CPU, although a few can be read by
220 other CPUs.
221 </ol>
223 <p>It is important to note that different data structures can have
224 very different ideas about the state of RCU at any given time.
225 For but one example, awareness of the start or end of a given RCU
226 grace period propagates slowly through the data structures.
227 This slow propagation is absolutely necessary for RCU to have good
228 read-side performance.
229 If this balkanized implementation seems foreign to you, one useful
230 trick is to consider each instance of these data structures to be
231 a different person, each having the usual slightly different
232 view of reality.
234 </p><p>The general role of each of these data structures is as
235 follows:
237 </p><ol>
239 This structure forms the interconnection between the
241 tracks grace periods, serves as short-term repository
242 for callbacks orphaned by CPU-hotplug events,
244 tracks expedited grace-period state,
245 and maintains state used to force quiescent states when
246 grace periods extend too long,
248 tree that propagates quiescent-state
249 information from the leaves to the root, and also propagates
250 grace-period information from the root to the leaves.
251 It provides local copies of the grace-period state in order
252 to allow this information to be accessed in a synchronized
253 manner without suffering the scalability limitations that
254 would otherwise be imposed by global locking.
256 of tasks that have blocked while in their current
257 RCU read-side critical section.
261 kernel threads (kthreads) and state.
262 Finally, it records CPU-hotplug state in order to determine
263 which CPUs should be ignored during a given grace period.
265 focus of quiescent-state detection and RCU callback queuing.
266 It also tracks its relationship to the corresponding leaf
269 combining tree.
271 copy of the grace-period information to allow for-free
272 synchronized
273 access to this information from the corresponding CPU.
274 Finally, this structure records past dyntick-idle state
275 for the corresponding CPU and also tracks statistics.
277 This per-CPU structure tracks the current dyntick-idle
278 state for the corresponding CPU.
280 structure is not replicated per RCU flavor.
282 This structure represents RCU callbacks, and is the
283 only structure allocated and managed by RCU users.
285 within the RCU-protected data structure.
286 </ol>
288 <p>If all you wanted from this article was a general notion of how
289 RCU's data structures are related, you are done.
290 Otherwise, each of the following sections give more details on
298 represents a flavor of RCU.
299 This structure forms the interconnection between the
301 tracks grace periods, contains the lock used to
302 synchronize with CPU-hotplug events,
303 and maintains state used to force quiescent states when
304 grace periods extend too long,
307 singly and in groups, in the following sections.
308 The more specialized fields are covered in the discussion of their
309 use.
314 as follows:
316 <pre>
317 1 struct rcu_node node[NUM_RCU_NODES];
319 3 struct rcu_data __percpu *rda;
320 </pre>
322 <table>
325 <tr><td>
326 Wait a minute!
328 but they are declared as a flat array!
329 What gives?
330 </td></tr>
333 The tree is laid out in the array.
334 The first node In the array is the head, the next set of nodes in the
335 array are children of the head node, and so on until the last set of
336 nodes in the array are the leaves.
337 </font>
340 this works.
341 </font></td></tr>
343 </table>
350 </p><p>One interesting consequence of this mapping is that a
351 breadth-first traversal of the tree is implemented as a simple
352 linear scan of the array, which is in fact what the
354 This macro is used at the beginning and ends of grace periods.
358 of the tree, for example, as shown below:
367 </p><p>For whatever it is worth, if you draw the tree to be tree-shaped
368 rather than array-shaped, it is easy to draw a planar representation:
375 </p><p>All of these fields are constant once initialization is complete,
376 and therefore need no protection.
381 as follows:
383 <pre>
384 1 unsigned long gpnum;
385 2 unsigned long completed;
386 </pre>
388 <p>RCU grace periods are numbered, and
390 period that started most recently.
392 grace period that completed most recently.
393 If the two fields are equal, the RCU grace period that most recently
394 started has already completed, and therefore the corresponding
395 flavor of RCU is idle.
398 grace period, which has not yet completed.
399 Any other combination of values indicates that something is broken.
405 as well.
407 most current values, and those of the other structures are compared
408 in order to detect the start of a new grace period in a distributed
409 fashion.
416 as follows:
418 <pre>
419 1 unsigned long gp_max;
420 2 char abbr;
421 3 char *name;
422 </pre>
425 grace period in jiffies.
437 tree that propagates quiescent-state
438 information from the leaves to the root and also that propagates
439 grace-period information from the root down to the leaves.
440 They provides local copies of the grace-period state in order
441 to allow this information to be accessed in a synchronized
442 manner without suffering the scalability limitations that
443 would otherwise be imposed by global locking.
445 of tasks that have blocked while in their current
446 RCU read-side critical section.
450 kernel threads (kthreads) and state.
451 Finally, they record CPU-hotplug state in order to determine
452 which CPUs should be ignored during a given grace period.
455 singly and in groups, in the following sections.
460 as follows:
462 <pre>
463 1 struct rcu_node *parent;
464 2 u8 level;
465 3 u8 grpnum;
466 4 unsigned long grpmask;
467 5 int grplo;
468 6 int grphi;
469 </pre>
474 The RCU implementation makes heavy use of this field to push quiescent
475 states up the tree.
477 the root being at level zero, its children at level one, and so on.
482 used only during initialization and for tracing.
486 structure in its parent's bitmasks, which are described later.
488 contain the lowest and highest numbered CPU served by this
491 </p><p>All of these fields are constant, and thus do not require any
492 synchronization.
497 as follows:
499 <pre>
500 1 raw_spinlock_t lock;
501 </pre>
503 <p>This field is used to protect the remaining fields in this structure,
504 unless otherwise stated.
505 That said, all of the fields in this structure can be accessed without
506 locking for tracing purposes.
507 Yes, this can result in confusing traces, but better some tracing confusion
508 than to be heisenbugged out of existence.
513 as follows:
515 <pre>
516 1 unsigned long gpnum;
517 2 unsigned long completed;
518 </pre>
520 <p>These fields are the counterparts of the fields of the same name in
523 counterparts.
526 structure believes that RCU is idle.
531 is still being waited for.
534 structure is updated at the beginning
536 updated at the end of each grace period.
540 <p>These fields manage the propagation of quiescent states up the
541 combining tree.
544 as follows:
546 <pre>
547 1 unsigned long qsmask;
548 2 unsigned long expmask;
549 3 unsigned long qsmaskinit;
550 4 unsigned long expmaskinit;
551 </pre>
555 quiescent states for the current normal grace period.
556 Such children will have a value of 1 in their corresponding bit.
559 children.
562 quiescent states for the current expedited grace period.
563 An expedited grace period has
564 the same conceptual properties as a normal grace period, but the
565 expedited implementation accepts extreme CPU overhead to obtain
566 much lower grace-period latency, for example, consuming a few
567 tens of microseconds worth of CPU time to reduce grace-period
568 duration from milliseconds to tens of microseconds.
571 one online CPU.
575 normal and expedited grace periods, respectively.
577 <table>
580 <tr><td>
581 Why are these bitmasks protected by locking?
582 Come on, haven't you heard of atomic instructions???
583 </td></tr>
586 Lockless grace-period computation! Such a tantalizing possibility!
587 </font>
590 </font>
592 <ol>
594 mode for quite some time.
595 When it wakes up, it notices that the current RCU
596 grace period needs it to report in, so it sets a
597 flag where the scheduling clock interrupt will find it.
598 </font><p>
602 which qualifies as an extended quiescent state.
603 </font><p>
605 interrupt fires in the
606 middle of an RCU read-side critical section, and notices
607 that the RCU core needs something, so commences RCU softirq
608 processing.
609 </font>
610 <p>
612 executes and is just about ready
614 tree.
615 </font><p>
617 completing the current
618 grace period and starting a new one.
619 </font><p>
621 state for the wrong
622 grace period.
623 That grace period might now end before the RCU read-side
624 critical section.
625 If that happens, disaster will ensue.
626 </font>
627 </ol>
630 order to coordinate
631 clearing of the bits with the grace-period numbers in
633 </font></td></tr>
635 </table>
640 midst of their RCU read-side critical sections, and these tasks
641 must be tracked explicitly.
642 The details of exactly why and how they are tracked will be covered
643 in a separate article on RCU read-side processing.
645 structure tracks them.
647 <pre>
648 1 struct list_head blkd_tasks;
649 2 struct list_head *gp_tasks;
650 3 struct list_head *exp_tasks;
651 4 bool wait_blkd_tasks;
652 </pre>
655 the list of blocked and preempted tasks.
656 As tasks undergo context switches within RCU read-side critical
661 on which the outgoing context switch executed.
662 As these tasks later exit their RCU read-side critical sections,
663 they remove themselves from the list.
664 This list is therefore in reverse time order, so that if one of the tasks
665 is blocking the current grace period, all subsequent tasks must
666 also be blocking that same grace period.
667 Therefore, a single pointer into this list suffices to track
668 all tasks blocking a given grace period.
671 grace periods.
673 no grace period in flight or if there are no blocked tasks
674 preventing that grace period from completing.
675 If either of these two pointers is referencing a task that
677 then that task must advance the pointer to the next task on
679 are no subsequent tasks on the list.
682 all hard-affinitied to the largest-numbered CPU in the system.
683 Then if task T1 blocked in an RCU read-side
684 critical section, then an expedited grace period started,
685 then task T2 blocked in an RCU read-side critical section,
687 in an RCU read-side critical section, then the state of the
689 would be as shown below:
694 blocking only the normal grace period, and task T3 is blocking
695 neither grace period.
696 Note that these tasks will not remove themselves from this list
697 immediately upon resuming execution.
698 They will instead remain on the list until they execute the outermost
700 section.
702 <p>
704 the current grace period is waiting on a blocked task.
709 C-preprocessor expressions as follows:
711 <pre>
712 1 #ifdef CONFIG_RCU_FANOUT
713 2 #define RCU_FANOUT CONFIG_RCU_FANOUT
714 3 #else
715 4 # ifdef CONFIG_64BIT
717 6 # else
719 8 # endif
720 9 #endif
721 10
722 11 #ifdef CONFIG_RCU_FANOUT_LEAF
723 12 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
724 13 #else
725 14 # ifdef CONFIG_64BIT
727 16 # else
729 18 # endif
730 19 #endif
731 20
732 21 #define RCU_FANOUT_1 (RCU_FANOUT_LEAF)
733 22 #define RCU_FANOUT_2 (RCU_FANOUT_1 * RCU_FANOUT)
734 23 #define RCU_FANOUT_3 (RCU_FANOUT_2 * RCU_FANOUT)
735 24 #define RCU_FANOUT_4 (RCU_FANOUT_3 * RCU_FANOUT)
736 25
740 29 # define NUM_RCU_NODES NUM_RCU_LVL_0
741 30 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0 }
748 37 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
749 38 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
750 39 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
757 46 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
758 47 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
759 48 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
760 49 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
767 56 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
768 57 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
769 58 # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
770 59 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
771 60 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
773 62 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
774 63 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" }
775 64 #else
777 66 #endif
778 </pre>
784 should be sufficient for the next few years at least.
786 should see us through the next decade or so.
787 This four-level tree also allows kernels built with
789 which might be useful in very large systems having eight CPUs per
790 socket (but please note that no one has yet shown any measurable
792 boundaries).
794 tree permits better testing of RCU's combining-tree code.
799 it is set based on the word size of the system, which is also
800 the Kconfig default.
805 structure to handle 64 CPUs, as permitted by the number of bits in
812 selected is based on the word size of the system, just as for
821 These numbers of CPUs are retained in the
826 C-preprocessor variables, respectively.
831 as well as the number of levels required.
835 of the tree is always exactly one, and this value is unconditionally
838 are computed by dividing the maximum number of CPUs by the
839 fanout supported by the number of levels from the current level down,
843 for lockdep lock-class names.
845 CPUs is too large for the specified fanout.
851 corresponding flavor of RCU.
852 The fields in this structure may be accessed only from the corresponding
853 CPU (and from tracing) unless otherwise stated.
854 This structure is the
855 focus of quiescent-state detection and RCU callback queuing.
856 It also tracks its relationship to the corresponding leaf
859 combining tree.
861 copy of the grace-period information to allow for-free
862 synchronized
863 access to this information from the corresponding CPU.
864 Finally, this structure records past dyntick-idle state
865 for the corresponding CPU and also tracks statistics.
868 singly and in groups, in the following sections.
873 as follows:
875 <pre>
876 1 int cpu;
877 2 struct rcu_state *rsp;
878 3 struct rcu_node *mynode;
879 4 struct rcu_dynticks *dynticks;
880 5 unsigned long grpmask;
881 6 bool beenonline;
882 </pre>
887 used to locate the name of the corresponding flavor of RCU for tracing),
891 up the combining tree.
894 CPU.
896 structure is shared among all flavors of RCU.
897 These first four fields are constant and therefore require not
898 synchronization.
903 quiescent states.
905 CPU comes online, which means that the debugfs tracing need not dump
911 as follows:
913 <pre>
914 1 unsigned long completed;
915 2 unsigned long gpnum;
916 3 bool cpu_no_qs;
917 4 bool core_needs_qs;
918 5 bool gpwrap;
919 6 unsigned long rcu_qs_ctr_snap;
920 </pre>
923 fields are the counterparts of the fields of the same name
928 arbitrarily far behind for CPUs in dyntick-idle mode (but these counters
929 will catch up upon exit from dyntick-idle mode).
932 structure believes that RCU is idle.
934 structure,
938 is still being waited for.
940 <table>
943 <tr><td>
944 All this replication of the grace period numbers can only cause
945 massive confusion.
946 Why not just keep a global pair of counters and be done with it???
947 </td></tr>
950 Because if there was only a single global pair of grace-period
951 numbers, there would need to be a single global lock to allow
952 safely accessing and updating them.
953 And if we are not going to have a single global lock, we need
954 to carefully manage the numbers on a per-node basis.
955 Recall from the answer to a previous Quick Quiz that the consequences
956 of applying a previously sampled quiescent state to the wrong
957 grace period are quite severe.
958 </font></td></tr>
960 </table>
963 CPU has not yet passed through a quiescent state,
965 RCU core needs a quiescent state from the corresponding CPU.
969 will cause the CPU to disregard the values of its counters on
970 its next exit from idle.
972 cases where a given operation has resulted in a quiescent state
977 <p>In the absence of CPU-hotplug events, RCU callbacks are invoked by
978 the same CPU that registered them.
979 This is strictly a cache-locality optimization: callbacks can and
980 do get invoked on CPUs other than the one that registered them.
981 After all, if the CPU that registered a given callback has gone
982 offline before the callback can be invoked, there really is no other
983 choice.
986 as follows:
988 <pre>
989 1 struct rcu_head *nxtlist;
990 2 struct rcu_head **nxttail[RCU_NEXT_SIZE];
991 3 unsigned long nxtcompleted[RCU_NEXT_SIZE];
992 4 long qlen_lazy;
993 5 long qlen;
994 6 long qlen_last_fqs_check;
995 7 unsigned long n_force_qs_snap;
996 8 unsigned long n_cbs_invoked;
997 9 unsigned long n_cbs_orphaned;
998 10 unsigned long n_cbs_adopted;
999 11 long blimit;
1000 </pre>
1004 older callbacks near the head and newer ones near the tail.
1005 Each segment contains callbacks with the corresponding relationship
1006 to the current grace period.
1007 The pointer out of the end of each of the four segments is referenced
1012 grace period), and
1014 with a specific grace period)
1015 respectively, as shown in the following figure.
1020 first
1021 RCU callback in the list.
1024 of the callbacks is ready to invoke.
1030 does, which indicates that there are no callbacks waiting on the next
1031 RCU grace period.
1034 remaining RCU callbacks have not yet been assigned to an RCU grace
1035 period.
1038 unless the callback list is empty, in which case it references
1041 </p><p>CPUs advance their callbacks from the
1044 as grace periods advance.
1046 whenever it notices that another RCU grace period has completed.
1047 The CPU detects the completion of an RCU grace period by noticing
1053 grace period.
1056 numbers corresponding to the list segments.
1057 This allows CPUs that go idle for extended periods to determine
1058 which of their callbacks are ready to be invoked after reawakening.
1063 are known to only free memory, and whose invocation can therefore
1064 be safely deferred.
1068 lists grow excessively long.
1072 fields count the number of callbacks invoked,
1073 sent to other CPUs when this CPU goes offline,
1074 and received from other CPUs when those other CPUs go offline.
1076 RCU callbacks that may be invoked at a given time.
1081 as follows:
1083 <pre>
1084 1 int dynticks_snap;
1085 2 unsigned long dynticks_fqs;
1086 </pre>
1089 of the corresponding CPU's dyntick-idle state when forcing
1090 quiescent states, and is therefore accessed from other CPUs.
1092 count the number of times this CPU is determined to be in
1093 dyntick-idle state, and is used for tracing and debugging purposes.
1099 for the corresponding CPU.
1101 replicated over the different flavors of RCU.
1102 The fields in this structure may be accessed only from the corresponding
1103 CPU (and from tracing) unless otherwise stated.
1104 Its fields are as follows:
1106 <pre>
1107 1 int dynticks_nesting;
1108 2 int dynticks_nmi_nesting;
1109 3 atomic_t dynticks;
1110 </pre>
1113 nesting depth of normal interrupts.
1114 In addition, this counter is incremented when exiting dyntick-idle
1115 mode and decremented when entering it.
1116 This counter can therefore be thought of as counting the number
1117 of reasons why this CPU cannot be permitted to enter dyntick-idle
1118 mode, aside from non-maskable interrupts (NMIs).
1120 field, except that NMIs that interrupt non-dyntick-idle execution
1121 are not counted.
1124 CPU's transitions to and from dyntick-idle mode, so that this counter
1125 has an even value when the CPU is in dyntick-idle mode and an odd
1126 value otherwise.
1128 <table>
1131 <tr><td>
1132 Why not just count all NMIs?
1133 Wouldn't that be simpler and less error prone?
1134 </td></tr>
1137 It seems simpler only until you think hard about how to go about
1140 </font></td></tr>
1142 </table>
1144 <p>Additional fields are present for some special-purpose
1145 builds, and are discussed separately.
1151 These structures are normally embedded within RCU-protected data
1152 structures whose algorithms use asynchronous grace periods.
1153 In contrast, when using algorithms that block waiting for RCU grace periods,
1158 <pre>
1159 1 struct rcu_head *next;
1160 2 void (*func)(struct rcu_head *head);
1161 </pre>
1167 to be called when the callback is ready to be invoked, and
1169 structure.
1172 structure within the enclosing RCU-protected data structure.
1174 </p><p>Both of these fields are used internally by RCU.
1175 From the viewpoint of RCU users, this structure is an
1178 <table>
1181 <tr><td>
1184 how is that function supposed to find the beginning of the
1185 enclosing RCU-protected data structure?
1186 </td></tr>
1189 In actual practice, there is a separate callback function per
1190 type of RCU-protected data structure.
1192 macro in the Linux kernel (or other pointer-manipulation facilities
1193 in other software environments) to find the beginning of the
1194 enclosing structure.
1195 </font></td></tr>
1197 </table>
1205 <pre>
1206 1 #ifdef CONFIG_PREEMPT_RCU
1207 2 int rcu_read_lock_nesting;
1208 3 union rcu_special rcu_read_unlock_special;
1209 4 struct list_head rcu_node_entry;
1210 5 struct rcu_node *rcu_blocked_node;
1211 6 #endif /* #ifdef CONFIG_PREEMPT_RCU */
1212 7 #ifdef CONFIG_TASKS_RCU
1213 8 unsigned long rcu_tasks_nvcsw;
1214 9 bool rcu_tasks_holdout;
1215 10 struct list_head rcu_tasks_holdout_list;
1216 11 int rcu_tasks_idle_cpu;
1217 12 #endif /* #ifdef CONFIG_TASKS_RCU */
1218 </pre>
1221 nesting level for RCU read-side critical sections, and
1224 to do additional work.
1226 tasks that have blocked within preemptible-RCU read-side critical
1230 read-side critical section.
1233 voluntary context switches that this task had undergone at the
1234 beginning of the current tasks-RCU grace period,
1237 is a list element enqueuing this task on the holdout list,
1239 idle task is running, but only if the task is currently running,
1240 that is, if the CPU is currently idle.
1243 Accessor Functions</a></h3>
1245 <p>The following listing shows the
1250 <pre>
1251 1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
1252 2 {
1254 4 }
1255 5
1256 6 #define rcu_for_each_node_breadth_first(rsp, rnp) \
1259 9
1260 10 #define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \
1263 13
1264 14 #define rcu_for_each_leaf_node(rsp, rnp) \
1267 </pre>
1272 structure.
1278 simply traversing the array in order.
1280 similarly, but traverses only the first part of the array, thus excluding
1283 the last part of the array, thus traversing only the leaf
1286 <table>
1289 <tr><td>
1292 contains only a single node?
1293 </td></tr>
1296 In the single-node case,
1299 </font></td></tr>
1301 </table>
1304 Summary</a></h3>
1312 If you made it this far, you are well prepared to read the code
1313 walkthroughs in the other articles in this series.
1316 Acknowledgments</a></h3>
1318 I owe thanks to Cyrill Gorcunov, Mathieu Desnoyers, Dhaval Giani, Paul
1319 Turner, Abhishek Srivastava, Matt Kowalczyk, and Serge Hallyn
1320 for helping me get this document into a more human-readable state.
1323 Legal Statement</a></h3>
1325 <p>This work represents the view of the author and does not necessarily
1326 represent the view of IBM.
1328 </p><p>Linux is a registered trademark of Linus Torvalds.
1330 </p><p>Other company, product, and service names may be trademarks or
1331 service marks of others.
1333 </body></html>