linux - Documentation/RCU/Design/Data-Structures/Data-Structures.rst

1196 lines · 57.3 KiB

1	===================================================
2	A Tour Through TREE_RCU's Data Structures [LWN.net]
3	===================================================
4
5	December 18, 2016
6
7	This article was contributed by Paul E. McKenney
8
9	Introduction
10	============
11
12	This document describes RCU's major data structures and their relationship
13	to each other.
14
15	Data-Structure Relationships
16	============================
17
18	RCU is for all intents and purposes a large state machine, and its
19	data structures maintain the state in such a way as to allow RCU readers
20	to execute extremely quickly, while also processing the RCU grace periods
21	requested by updaters in an efficient and extremely scalable fashion.
22	The efficiency and scalability of RCU updaters is provided primarily
23	by a combining tree, as shown below:
24
25	.. kernel-figure:: BigTreeClassicRCU.svg
26
27	This diagram shows an enclosing ``rcu_state`` structure containing a tree
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.
31	This structure is adjusted at boot time, if needed, to handle the common
32	case where ``nr_cpu_ids`` is much less than ``NR_CPUs``.
33	For example, a number of Linux distributions set ``NR_CPUs=4096``,
34	which results in a three-level ``rcu_node`` tree.
35	If the actual hardware has only 16 CPUs, RCU will adjust itself
36	at boot time, resulting in an ``rcu_node`` tree with only a single node.
37
38	The purpose of this combining tree is to allow per-CPU events
39	such as quiescent states, dyntick-idle transitions,
40	and CPU hotplug operations to be processed efficiently
41	and scalably.
42	Quiescent states are recorded by the per-CPU ``rcu_data`` structures,
43	and other events are recorded by the leaf-level ``rcu_node``
44	structures.
45	All of these events are combined at each level of the tree until finally
46	grace periods are completed at the tree's root ``rcu_node``
47	structure.
48	A grace period can be completed at the root once every CPU
49	(or, in the case of ``CONFIG_PREEMPT_RCU``, task)
50	has passed through a quiescent state.
51	Once a grace period has completed, record of that fact is propagated
52	back down the tree.
53
54	As can be seen from the diagram, on a 64-bit system
55	a two-level tree with 64 leaves can accommodate 1,024 CPUs, with a fanout
56	of 64 at the root and a fanout of 16 at the leaves.
57
58	+-----------------------------------------------------------------------+
59	\| Quick Quiz: \|
60	+-----------------------------------------------------------------------+
61	\| Why isn't the fanout at the leaves also 64? \|
62	+-----------------------------------------------------------------------+
63	\| Answer: \|
64	+-----------------------------------------------------------------------+
65	\| Because there are more types of events that affect the leaf-level \|
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 \|
69	\| on a wide variety of systems has shown that a fanout of 16 works well \|
70	\| for the leaves of the ``rcu_node`` tree. \|
71	\| \|
72	\| Of course, further experience with systems having hundreds or \|
73	\| thousands of CPUs may demonstrate that the fanout for the non-leaf \|
74	\| ``rcu_node`` structures must also be reduced. Such reduction can be \|
75	\| easily carried out when and if it proves necessary. In the meantime, \|
76	\| if you are using such a system and running into contention problems \|
77	\| on the non-leaf ``rcu_node`` structures, you may use the \|
78	\| ``CONFIG_RCU_FANOUT`` kernel configuration parameter to reduce the \|
79	\| non-leaf fanout as needed. \|
80	\| \|
81	\| Kernels built for systems with strong NUMA characteristics might \|
82	\| also need to adjust ``CONFIG_RCU_FANOUT`` so that the domains of \|
83	\| the ``rcu_node`` structures align with hardware boundaries. \|
84	\| However, there has thus far been no need for this. \|
85	+-----------------------------------------------------------------------+
86
87	If your system has more than 1,024 CPUs (or more than 512 CPUs on a
88	32-bit system), then RCU will automatically add more levels to the tree.
89	For example, if you are crazy enough to build a 64-bit system with
90	65,536 CPUs, RCU would configure the ``rcu_node`` tree as follows:
91
92	.. kernel-figure:: HugeTreeClassicRCU.svg
93
94	RCU currently permits up to a four-level tree, which on a 64-bit system
95	accommodates up to 4,194,304 CPUs, though only a mere 524,288 CPUs for
96	32-bit systems. On the other hand, you can set both
97	``CONFIG_RCU_FANOUT`` and ``CONFIG_RCU_FANOUT_LEAF`` to be as small as
98	2, which would result in a 16-CPU test using a 4-level tree. This can be
99	useful for testing large-system capabilities on small test machines.
100
101	This multi-level combining tree allows us to get most of the performance
102	and scalability benefits of partitioning, even though RCU grace-period
103	detection is inherently a global operation. The trick here is that only
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,
107	only one access out of sixteen will progress up the tree. For the
108	internal ``rcu_node`` structures, the situation is even more extreme:
109	Only one access out of sixty-four will progress up the tree. Because the
110	vast majority of the CPUs do not progress up the tree, the lock
111	contention remains roughly constant up the tree. No matter how many CPUs
112	there are in the system, at most 64 quiescent-state reports per grace
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``
115	structure remains acceptably low.
116
117	In effect, the combining tree acts like a big shock absorber, keeping
118	lock contention under control at all tree levels regardless of the level
119	of loading on the system.
120
121	RCU updaters wait for normal grace periods by registering RCU callbacks,
122	either directly via ``call_rcu()`` or indirectly via
123	``synchronize_rcu()`` and friends. RCU callbacks are represented by
124	``rcu_head`` structures, which are queued on ``rcu_data`` structures
125	while they are waiting for a grace period to elapse, as shown in the
126	following figure:
127
128	.. kernel-figure:: BigTreePreemptRCUBHdyntickCB.svg
129
130	This figure shows how ``TREE_RCU``'s and ``PREEMPT_RCU``'s major data
131	structures are related. Lesser data structures will be introduced with
132	the algorithms that make use of them.
133
134	Note that each of the data structures in the above figure has its own
135	synchronization:
136
137	#. Each ``rcu_state`` structures has a lock and a mutex, and some fields
138	are protected by the corresponding root ``rcu_node`` structure's lock.
139	#. Each ``rcu_node`` structure has a spinlock.
140	#. The fields in ``rcu_data`` are private to the corresponding CPU,
141	although a few can be read and written by other CPUs.
142
143	It is important to note that different data structures can have very
144	different ideas about the state of RCU at any given time. For but one
145	example, awareness of the start or end of a given RCU grace period
146	propagates slowly through the data structures. This slow propagation is
147	absolutely necessary for RCU to have good read-side performance. If this
148	balkanized implementation seems foreign to you, one useful trick is to
149	consider each instance of these data structures to be a different
150	person, each having the usual slightly different view of reality.
151
152	The general role of each of these data structures is as follows:
153
154	#. ``rcu_state``: This structure forms the interconnection between the
155	``rcu_node`` and ``rcu_data`` structures, tracks grace periods,
156	serves as short-term repository for callbacks orphaned by CPU-hotplug
157	events, maintains ``rcu_barrier()`` state, tracks expedited
158	grace-period state, and maintains state used to force quiescent
159	states when grace periods extend too long,
160	#. ``rcu_node``: This structure forms the combining tree that propagates
161	quiescent-state information from the leaves to the root, and also
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
164	this information to be accessed in a synchronized manner without
165	suffering the scalability limitations that would otherwise be imposed
166	by global locking. In ``CONFIG_PREEMPT_RCU`` kernels, it manages the
167	lists of tasks that have blocked while in their current RCU read-side
168	critical section. In ``CONFIG_PREEMPT_RCU`` with
169	``CONFIG_RCU_BOOST``, it manages the per-\ ``rcu_node``
170	priority-boosting kernel threads (kthreads) and state. Finally, it
171	records CPU-hotplug state in order to determine which CPUs should be
172	ignored during a given grace period.
173	#. ``rcu_data``: This per-CPU structure is the focus of quiescent-state
174	detection and RCU callback queuing. It also tracks its relationship
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
178	copy of the grace-period information to allow for-free synchronized
179	access to this information from the corresponding CPU. Finally, this
180	structure records past dyntick-idle state for the corresponding CPU
181	and also tracks statistics.
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.
186
187	If all you wanted from this article was a general notion of how RCU's
188	data structures are related, you are done. Otherwise, each of the
189	following sections give more details on the ``rcu_state``, ``rcu_node``
190	and ``rcu_data`` data structures.
191
192	The ``rcu_state`` Structure
193	~~~~~~~~~~~~~~~~~~~~~~~~~~~
194
195	The ``rcu_state`` structure is the base structure that represents the
196	state of RCU in the system. This structure forms the interconnection
197	between the ``rcu_node`` and ``rcu_data`` structures, tracks grace
198	periods, contains the lock used to synchronize with CPU-hotplug events,
199	and maintains state used to force quiescent states when grace periods
200	extend too long,
201
202	A few of the ``rcu_state`` structure's fields are discussed, singly and
203	in groups, in the following sections. The more specialized fields are
204	covered in the discussion of their use.
205
206	Relationship to rcu_node and rcu_data Structures
207	''''''''''''''''''''''''''''''''''''''''''''''''
208
209	This portion of the ``rcu_state`` structure is declared as follows:
210
211	::
212
213	1 struct rcu_node node[NUM_RCU_NODES];
214	2 struct rcu_node *level[NUM_RCU_LVLS + 1];
215	3 struct rcu_data __percpu *rda;
216
217	+-----------------------------------------------------------------------+
218	\| Quick Quiz: \|
219	+-----------------------------------------------------------------------+
220	\| Wait a minute! You said that the ``rcu_node`` structures formed a \|
221	\| tree, but they are declared as a flat array! What gives? \|
222	+-----------------------------------------------------------------------+
223	\| Answer: \|
224	+-----------------------------------------------------------------------+
225	\| The tree is laid out in the array. The first node In the array is the \|
226	\| head, the next set of nodes in the array are children of the head \|
227	\| node, and so on until the last set of nodes in the array are the \|
228	\| leaves. \|
229	\| See the following diagrams to see how this works. \|
230	+-----------------------------------------------------------------------+
231
232	The ``rcu_node`` tree is embedded into the ``->node[]`` array as shown
233	in the following figure:
234
235	.. kernel-figure:: TreeMapping.svg
236
237	One interesting consequence of this mapping is that a breadth-first
238	traversal of the tree is implemented as a simple linear scan of the
239	array, which is in fact what the ``rcu_for_each_node_breadth_first()``
240	macro does. This macro is used at the beginning and ends of grace
241	periods.
242
243	Each entry of the ``->level`` array references the first ``rcu_node``
244	structure on the corresponding level of the tree, for example, as shown
245	below:
246
247	.. kernel-figure:: TreeMappingLevel.svg
248
249	The zero\ :sup:`th` element of the array references the root
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.
253
254	For whatever it is worth, if you draw the tree to be tree-shaped rather
255	than array-shaped, it is easy to draw a planar representation:
256
257	.. kernel-figure:: TreeLevel.svg
258
259	Finally, the ``->rda`` field references a per-CPU pointer to the
260	corresponding CPU's ``rcu_data`` structure.
261
262	All of these fields are constant once initialization is complete, and
263	therefore need no protection.
264
265	Grace-Period Tracking
266	'''''''''''''''''''''
267
268	This portion of the ``rcu_state`` structure is declared as follows:
269
270	::
271
272	1 unsigned long gp_seq;
273
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
277	one for in progress. In other words, if the bottom two bits of
278	``->gp_seq`` are zero, then RCU is idle. Any other value in the bottom
279	two bits indicates that something is broken. This field is protected by
280	the root ``rcu_node`` structure's ``->lock`` field.
281
282	There are ``->gp_seq`` fields in the ``rcu_node`` and ``rcu_data``
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
285	in order to detect the beginnings and ends of grace periods in a
286	distributed fashion. The values flow from ``rcu_state`` to ``rcu_node``
287	(down the tree from the root to the leaves) to ``rcu_data``.
288
289	+-----------------------------------------------------------------------+
290	\| Quick Quiz: \|
291	+-----------------------------------------------------------------------+
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? \|
294	\| Why not just use the root rcu_node's gp_seq as the official record \|
295	\| and update it directly when starting a new grace period? \|
296	+-----------------------------------------------------------------------+
297	\| Answer: \|
298	+-----------------------------------------------------------------------+
299	\| On single-node RCU trees (where the root node is also a leaf), \|
300	\| updating the root node's gp_seq immediately would create unnecessary \|
301	\| lock contention. Here's why: \|
302	\| \|
303	\| If we did rcu_seq_start() directly on the root node's gp_seq: \|
304	\| \|
305	\| 1. All CPUs would immediately see their node's gp_seq from their rdp's\|
306	\| gp_seq, in rcu_pending(). They would all then invoke the RCU-core. \|
307	\| 2. Which calls note_gp_changes() and try to acquire the node lock. \|
308	\| 3. But rnp->qsmask isn't initialized yet (happens later in \|
309	\| rcu_gp_init()) \|
310	\| 4. So each CPU would acquire the lock, find it can't determine if it \|
311	\| needs to report quiescent state (no qsmask), update rdp->gp_seq, \|
312	\| and release the lock. \|
313	\| 5. Result: Lots of lock acquisitions with no grace period progress \|
314	\| \|
315	\| By having a separate rcu_state.gp_seq, we can increment the official \|
316	\| grace period counter without immediately affecting what CPUs see in \|
317	\| their nodes. The hierarchical propagation in rcu_gp_init() then \|
318	\| updates the root node's gp_seq and qsmask together under the same lock\|
319	\| acquisition, avoiding this useless contention. \|
320	+-----------------------------------------------------------------------+
321
322	Miscellaneous
323	'''''''''''''
324
325	This portion of the ``rcu_state`` structure is declared as follows:
326
327	::
328
329	1 unsigned long gp_max;
330	2 char abbr;
331	3 char *name;
332
333	The ``->gp_max`` field tracks the duration of the longest grace period
334	in jiffies. It is protected by the root ``rcu_node``'s ``->lock``.
335
336	The ``->name`` and ``->abbr`` fields distinguish between preemptible RCU
337	(“rcu_preempt” and “p”) and non-preemptible RCU (“rcu_sched” and “s”).
338	These fields are used for diagnostic and tracing purposes.
339
340	The ``rcu_node`` Structure
341	~~~~~~~~~~~~~~~~~~~~~~~~~~
342
343	The ``rcu_node`` structures form the combining tree that propagates
344	quiescent-state information from the leaves to the root and also that
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
347	this information to be accessed in a synchronized manner without
348	suffering the scalability limitations that would otherwise be imposed by
349	global locking. In ``CONFIG_PREEMPT_RCU`` kernels, they manage the lists
350	of tasks that have blocked while in their current RCU read-side critical
351	section. In ``CONFIG_PREEMPT_RCU`` with ``CONFIG_RCU_BOOST``, they
352	manage the per-\ ``rcu_node`` priority-boosting kernel threads
353	(kthreads) and state. Finally, they record CPU-hotplug state in order to
354	determine which CPUs should be ignored during a given grace period.
355
356	The ``rcu_node`` structure's fields are discussed, singly and in groups,
357	in the following sections.
358
359	Connection to Combining Tree
360	''''''''''''''''''''''''''''
361
362	This portion of the ``rcu_node`` structure is declared as follows:
363
364	::
365
366	1 struct rcu_node *parent;
367	2 u8 level;
368	3 u8 grpnum;
369	4 unsigned long grpmask;
370	5 int grplo;
371	6 int grphi;
372
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
375	makes heavy use of this field to push quiescent states up the tree. The
376	``->level`` field gives the level in the tree, with the root being at
377	level zero, its children at level one, and so on. The ``->grpnum`` field
378	gives this node's position within the children of its parent, so this
379	number can range between 0 and 31 on 32-bit systems and between 0 and 63
380	on 64-bit systems. The ``->level`` and ``->grpnum`` fields are used only
381	during initialization and for tracing. The ``->grpmask`` field is the
382	bitmask counterpart of ``->grpnum``, and therefore always has exactly
383	one bit set. This mask is used to clear the bit corresponding to this
384	``rcu_node`` structure in its parent's bitmasks, which are described
385	later. Finally, the ``->grplo`` and ``->grphi`` fields contain the
386	lowest and highest numbered CPU served by this ``rcu_node`` structure,
387	respectively.
388
389	All of these fields are constant, and thus do not require any
390	synchronization.
391
392	Synchronization
393	'''''''''''''''
394
395	This field of the ``rcu_node`` structure is declared as follows:
396
397	::
398
399	1 raw_spinlock_t lock;
400
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
403	can be accessed without locking for tracing purposes. Yes, this can
404	result in confusing traces, but better some tracing confusion than to be
405	heisenbugged out of existence.
406
407	.. _grace-period-tracking-1:
408
409	Grace-Period Tracking
410	'''''''''''''''''''''
411
412	This portion of the ``rcu_node`` structure is declared as follows:
413
414	::
415
416	1 unsigned long gp_seq;
417	2 unsigned long gp_seq_needed;
418
419	The ``rcu_node`` structures' ``->gp_seq`` fields are the counterparts of
420	the field of the same name in the ``rcu_state`` structure. They each may
421	lag up to one step behind their ``rcu_state`` counterpart. If the bottom
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.
424
425	The ``>gp_seq`` field of each ``rcu_node`` structure is updated at the
426	beginning and the end of each grace period.
427
428	The ``->gp_seq_needed`` fields record the furthest-in-the-future grace
429	period request seen by the corresponding ``rcu_node`` structure. The
430	request is considered fulfilled when the value of the ``->gp_seq`` field
431	equals or exceeds that of the ``->gp_seq_needed`` field.
432
433	+-----------------------------------------------------------------------+
434	\| Quick Quiz: \|
435	+-----------------------------------------------------------------------+
436	\| Suppose that this ``rcu_node`` structure doesn't see a request for a \|
437	\| very long time. Won't wrapping of the ``->gp_seq`` field cause \|
438	\| problems? \|
439	+-----------------------------------------------------------------------+
440	\| Answer: \|
441	+-----------------------------------------------------------------------+
442	\| No, because if the ``->gp_seq_needed`` field lags behind the \|
443	\| ``->gp_seq`` field, the ``->gp_seq_needed`` field will be updated at \|
444	\| the end of the grace period. Modulo-arithmetic comparisons therefore \|
445	\| will always get the correct answer, even with wrapping. \|
446	+-----------------------------------------------------------------------+
447
448	Quiescent-State Tracking
449	''''''''''''''''''''''''
450
451	These fields manage the propagation of quiescent states up the combining
452	tree.
453
454	This portion of the ``rcu_node`` structure has fields as follows:
455
456	::
457
458	1 unsigned long qsmask;
459	2 unsigned long expmask;
460	3 unsigned long qsmaskinit;
461	4 unsigned long expmaskinit;
462
463	The ``->qsmask`` field tracks which of this ``rcu_node`` structure's
464	children still need to report quiescent states for the current normal
465	grace period. Such children will have a value of 1 in their
466	corresponding bit. Note that the leaf ``rcu_node`` structures should be
467	thought of as having ``rcu_data`` structures as their children.
468	Similarly, the ``->expmask`` field tracks which of this ``rcu_node``
469	structure's children still need to report quiescent states for the
470	current expedited grace period. An expedited grace period has the same
471	conceptual properties as a normal grace period, but the expedited
472	implementation accepts extreme CPU overhead to obtain much lower
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
475	tens of microseconds. The ``->qsmaskinit`` field tracks which of this
476	``rcu_node`` structure's children cover for at least one online CPU.
477	This mask is used to initialize ``->qsmask``, and ``->expmaskinit`` is
478	used to initialize ``->expmask`` and the beginning of the normal and
479	expedited grace periods, respectively.
480
481	+-----------------------------------------------------------------------+
482	\| Quick Quiz: \|
483	+-----------------------------------------------------------------------+
484	\| Why are these bitmasks protected by locking? Come on, haven't you \|
485	\| heard of atomic instructions??? \|
486	+-----------------------------------------------------------------------+
487	\| Answer: \|
488	+-----------------------------------------------------------------------+
489	\| Lockless grace-period computation! Such a tantalizing possibility! \|
490	\| But consider the following sequence of events: \|
491	\| \|
492	\| #. CPU 0 has been in dyntick-idle mode for quite some time. When it \|
493	\| wakes up, it notices that the current RCU grace period needs it to \|
494	\| report in, so it sets a flag where the scheduling clock interrupt \|
495	\| will find it. \|
496	\| #. Meanwhile, CPU 1 is running ``force_quiescent_state()``, and \|
497	\| notices that CPU 0 has been in dyntick idle mode, which qualifies \|
498	\| as an extended quiescent state. \|
499	\| #. CPU 0's scheduling clock interrupt fires in the middle of an RCU \|
500	\| read-side critical section, and notices that the RCU core needs \|
501	\| something, so commences RCU softirq processing. \|
502	\| #. CPU 0's softirq handler executes and is just about ready to report \|
503	\| its quiescent state up the ``rcu_node`` tree. \|
504	\| #. But CPU 1 beats it to the punch, completing the current grace \|
505	\| period and starting a new one. \|
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 \|
508	\| section. If that happens, disaster will ensue. \|
509	\| \|
510	\| So the locking is absolutely required in order to coordinate clearing \|
511	\| of the bits with updating of the grace-period sequence number in \|
512	\| ``->gp_seq``. \|
513	+-----------------------------------------------------------------------+
514
515	Blocked-Task Management
516	'''''''''''''''''''''''
517
518	``PREEMPT_RCU`` allows tasks to be preempted in the midst of their RCU
519	read-side critical sections, and these tasks must be tracked explicitly.
520	The details of exactly why and how they are tracked will be covered in a
521	separate article on RCU read-side processing. For now, it is enough to
522	know that the ``rcu_node`` structure tracks them.
523
524	::
525
526	1 struct list_head blkd_tasks;
527	2 struct list_head *gp_tasks;
528	3 struct list_head *exp_tasks;
529	4 bool wait_blkd_tasks;
530
531	The ``->blkd_tasks`` field is a list header for the list of blocked and
532	preempted tasks. As tasks undergo context switches within RCU read-side
533	critical sections, their ``task_struct`` structures are enqueued (via
534	the ``task_struct``'s ``->rcu_node_entry`` field) onto the head of the
535	``->blkd_tasks`` list for the leaf ``rcu_node`` structure corresponding
536	to the CPU on which the outgoing context switch executed. As these tasks
537	later exit their RCU read-side critical sections, they remove themselves
538	from the list. This list is therefore in reverse time order, so that if
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
541	pointer into this list suffices to track all tasks blocking a given
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
546	completing. If either of these two pointers is referencing a task that
547	removes itself from the ``->blkd_tasks`` list, then that task must
548	advance the pointer to the next task on the list, or set the pointer to
549	``NULL`` if there are no subsequent tasks on the list.
550
551	For example, suppose that tasks T1, T2, and T3 are all hard-affinitied
552	to the largest-numbered CPU in the system. Then if task T1 blocked in an
553	RCU read-side critical section, then an expedited grace period started,
554	then task T2 blocked in an RCU read-side critical section, then a normal
555	grace period started, and finally task 3 blocked in an RCU read-side
556	critical section, then the state of the last leaf ``rcu_node``
557	structure's blocked-task list would be as shown below:
558
559	.. kernel-figure:: blkd_task.svg
560
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
563	that these tasks will not remove themselves from this list immediately
564	upon resuming execution. They will instead remain on the list until they
565	execute the outermost ``rcu_read_unlock()`` that ends their RCU
566	read-side critical section.
567
568	The ``->wait_blkd_tasks`` field indicates whether or not the current
569	grace period is waiting on a blocked task.
570
571	Sizing the ``rcu_node`` Array
572	'''''''''''''''''''''''''''''
573
574	The ``rcu_node`` array is sized via a series of C-preprocessor
575	expressions as follows:
576
577	::
578
579	1 #ifdef CONFIG_RCU_FANOUT
580	2 #define RCU_FANOUT CONFIG_RCU_FANOUT
581	3 #else
582	4 # ifdef CONFIG_64BIT
583	5 # define RCU_FANOUT 64
584	6 # else
585	7 # define RCU_FANOUT 32
586	8 # endif
587	9 #endif
588	10
589	11 #ifdef CONFIG_RCU_FANOUT_LEAF
590	12 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
591	13 #else
592	14 # ifdef CONFIG_64BIT
593	15 # define RCU_FANOUT_LEAF 64
594	16 # else
595	17 # define RCU_FANOUT_LEAF 32
596	18 # endif
597	19 #endif
598	20
599	21 #define RCU_FANOUT_1 (RCU_FANOUT_LEAF)
600	22 #define RCU_FANOUT_2 (RCU_FANOUT_1 * RCU_FANOUT)
601	23 #define RCU_FANOUT_3 (RCU_FANOUT_2 * RCU_FANOUT)
602	24 #define RCU_FANOUT_4 (RCU_FANOUT_3 * RCU_FANOUT)
603	25
604	26 #if NR_CPUS <= RCU_FANOUT_1
605	27 # define RCU_NUM_LVLS 1
606	28 # define NUM_RCU_LVL_0 1
607	29 # define NUM_RCU_NODES NUM_RCU_LVL_0
608	30 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0 }
609	31 # define RCU_NODE_NAME_INIT { "rcu_node_0" }
610	32 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0" }
611	33 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0" }
612	34 #elif NR_CPUS <= RCU_FANOUT_2
613	35 # define RCU_NUM_LVLS 2
614	36 # define NUM_RCU_LVL_0 1
615	37 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
616	38 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
617	39 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
618	40 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1" }
619	41 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1" }
620	42 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1" }
621	43 #elif NR_CPUS <= RCU_FANOUT_3
622	44 # define RCU_NUM_LVLS 3
623	45 # define NUM_RCU_LVL_0 1
624	46 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
625	47 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
626	48 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
627	49 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
628	50 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
629	51 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
630	52 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" }
631	53 #elif NR_CPUS <= RCU_FANOUT_4
632	54 # define RCU_NUM_LVLS 4
633	55 # define NUM_RCU_LVL_0 1
634	56 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
635	57 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
636	58 # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
637	59 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
638	60 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
639	61 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
640	62 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
641	63 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" }
642	64 #else
643	65 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
644	66 #endif
645
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
648	subsequent “if” statement. For 32-bit systems, this allows
649	163232*32=524,288 CPUs, which should be sufficient for the next few
650	years at least. For 64-bit systems, 166464*64=4,194,304 CPUs is
651	allowed, which should see us through the next decade or so. This
652	four-level tree also allows kernels built with ``CONFIG_RCU_FANOUT=8``
653	to support up to 4096 CPUs, which might be useful in very large systems
654	having eight CPUs per socket (but please note that no one has yet shown
655	any measurable performance degradation due to misaligned socket and
656	``rcu_node`` boundaries). In addition, building kernels with a full four
657	levels of ``rcu_node`` tree permits better testing of RCU's
658	combining-tree code.
659
660	The ``RCU_FANOUT`` symbol controls how many children are permitted at
661	each non-leaf level of the ``rcu_node`` tree. If the
662	``CONFIG_RCU_FANOUT`` Kconfig option is not specified, it is set based
663	on the word size of the system, which is also the Kconfig default.
664
665	The ``RCU_FANOUT_LEAF`` symbol controls how many CPUs are handled by
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
668	number of bits in the ``->qsmask`` field on a 64-bit system, results in
669	excessive contention for the leaf ``rcu_node`` structures' ``->lock``
670	fields. The number of CPUs per leaf ``rcu_node`` structure is therefore
671	limited to 16 given the default value of ``CONFIG_RCU_FANOUT_LEAF``. If
672	``CONFIG_RCU_FANOUT_LEAF`` is unspecified, the value selected is based
673	on the word size of the system, just as for ``CONFIG_RCU_FANOUT``.
674	Lines 11-19 perform this computation.
675
676	Lines 21-24 compute the maximum number of CPUs supported by a
677	single-level (which contains a single ``rcu_node`` structure),
678	two-level, three-level, and four-level ``rcu_node`` tree, respectively,
679	given the fanout specified by ``RCU_FANOUT`` and ``RCU_FANOUT_LEAF``.
680	These numbers of CPUs are retained in the ``RCU_FANOUT_1``,
681	``RCU_FANOUT_2``, ``RCU_FANOUT_3``, and ``RCU_FANOUT_4`` C-preprocessor
682	variables, respectively.
683
684	These variables are used to control the C-preprocessor ``#if`` statement
685	spanning lines 26-66 that computes the number of ``rcu_node`` structures
686	required for each level of the tree, as well as the number of levels
687	required. The number of levels is placed in the ``NUM_RCU_LVLS``
688	C-preprocessor variable by lines 27, 35, 44, and 54. The number of
689	``rcu_node`` structures for the topmost level of the tree is always
690	exactly one, and this value is unconditionally placed into
691	``NUM_RCU_LVL_0`` by lines 28, 36, 45, and 55. The rest of the levels
692	(if any) of the ``rcu_node`` tree are computed by dividing the maximum
693	number of CPUs by the fanout supported by the number of levels from the
694	current level down, rounding up. This computation is performed by
695	lines 37, 46-47, and 56-58. Lines 31-33, 40-42, 50-52, and 62-63 create
696	initializers for lockdep lock-class names. Finally, lines 64-66 produce
697	an error if the maximum number of CPUs is too large for the specified
698	fanout.
699
700	The ``rcu_segcblist`` Structure
701	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
702
703	The ``rcu_segcblist`` structure maintains a segmented list of callbacks
704	as follows:
705
706	::
707
708	1 #define RCU_DONE_TAIL 0
709	2 #define RCU_WAIT_TAIL 1
710	3 #define RCU_NEXT_READY_TAIL 2
711	4 #define RCU_NEXT_TAIL 3
712	5 #define RCU_CBLIST_NSEGS 4
713	6
714	7 struct rcu_segcblist {
715	8 struct rcu_head *head;
716	9 struct rcu_head **tails[RCU_CBLIST_NSEGS];
717	10 unsigned long gp_seq[RCU_CBLIST_NSEGS];
718	11 long len;
719	12 long len_lazy;
720	13 };
721
722	The segments are as follows:
723
724	#. ``RCU_DONE_TAIL``: Callbacks whose grace periods have elapsed. These
725	callbacks are ready to be invoked.
726	#. ``RCU_WAIT_TAIL``: Callbacks that are waiting for the current grace
727	period. Note that different CPUs can have different ideas about which
728	grace period is current, hence the ``->gp_seq`` field.
729	#. ``RCU_NEXT_READY_TAIL``: Callbacks waiting for the next grace period
730	to start.
731	#. ``RCU_NEXT_TAIL``: Callbacks that have not yet been associated with a
732	grace period.
733
734	The ``->head`` pointer references the first callback or is ``NULL`` if
735	the list contains no callbacks (which is not the same as being empty).
736	Each element of the ``->tails[]`` array references the ``->next``
737	pointer of the last callback in the corresponding segment of the list,
738	or the list's ``->head`` pointer if that segment and all previous
739	segments are empty. If the corresponding segment is empty but some
740	previous segment is not empty, then the array element is identical to
741	its predecessor. Older callbacks are closer to the head of the list, and
742	new callbacks are added at the tail. This relationship between the
743	``->head`` pointer, the ``->tails[]`` array, and the callbacks is shown
744	in this diagram:
745
746	.. kernel-figure:: nxtlist.svg
747
748	In this figure, the ``->head`` pointer references the first RCU callback
749	in the list. The ``->tails[RCU_DONE_TAIL]`` array element references the
750	``->head`` pointer itself, indicating that none of the callbacks is
751	ready to invoke. The ``->tails[RCU_WAIT_TAIL]`` array element references
752	callback CB 2's ``->next`` pointer, which indicates that CB 1 and CB 2
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
755	``->tails[RCU_NEXT_READY_TAIL]`` array element references the same RCU
756	callback that ``->tails[RCU_WAIT_TAIL]`` does, which indicates that
757	there are no callbacks waiting on the next RCU grace period. The
758	``->tails[RCU_NEXT_TAIL]`` array element references CB 4's ``->next``
759	pointer, indicating that all the remaining RCU callbacks have not yet
760	been assigned to an RCU grace period. Note that the
761	``->tails[RCU_NEXT_TAIL]`` array element always references the last RCU
762	callback's ``->next`` pointer unless the callback list is empty, in
763	which case it references the ``->head`` pointer.
764
765	There is one additional important special case for the
766	``->tails[RCU_NEXT_TAIL]`` array element: It can be ``NULL`` when this
767	list is disabled. Lists are disabled when the corresponding CPU is
768	offline or when the corresponding CPU's callbacks are offloaded to a
769	kthread, both of which are described elsewhere.
770
771	CPUs advance their callbacks from the ``RCU_NEXT_TAIL`` to the
772	``RCU_NEXT_READY_TAIL`` to the ``RCU_WAIT_TAIL`` to the
773	``RCU_DONE_TAIL`` list segments as grace periods advance.
774
775	The ``->gp_seq[]`` array records grace-period numbers corresponding to
776	the list segments. This is what allows different CPUs to have different
777	ideas as to which is the current grace period while still avoiding
778	premature invocation of their callbacks. In particular, this allows CPUs
779	that go idle for extended periods to determine which of their callbacks
780	are ready to be invoked after reawakening.
781
782	The ``->len`` counter contains the number of callbacks in ``->head``,
783	and the ``->len_lazy`` contains the number of those callbacks that are
784	known to only free memory, and whose invocation can therefore be safely
785	deferred.
786
787	.. important::
788
789	It is the ``->len`` field that determines whether or
790	not there are callbacks associated with this ``rcu_segcblist``
791	structure, not the ``->head`` pointer. The reason for this is that all
792	the ready-to-invoke callbacks (that is, those in the ``RCU_DONE_TAIL``
793	segment) are extracted all at once at callback-invocation time
794	(``rcu_do_batch``), due to which ``->head`` may be set to NULL if there
795	are no not-done callbacks remaining in the ``rcu_segcblist``. If
796	callback invocation must be postponed, for example, because a
797	high-priority process just woke up on this CPU, then the remaining
798	callbacks are placed back on the ``RCU_DONE_TAIL`` segment and
799	``->head`` once again points to the start of the segment. In short, the
800	head field can briefly be ``NULL`` even though the CPU has callbacks
801	present the entire time. Therefore, it is not appropriate to test the
802	``->head`` pointer for ``NULL``.
803
804	In contrast, the ``->len`` and ``->len_lazy`` counts are adjusted only
805	after the corresponding callbacks have been invoked. This means that the
806	``->len`` count is zero only if the ``rcu_segcblist`` structure really
807	is devoid of callbacks. Of course, off-CPU sampling of the ``->len``
808	count requires careful use of appropriate synchronization, for example,
809	memory barriers. This synchronization can be a bit subtle, particularly
810	in the case of ``rcu_barrier()``.
811
812	The ``rcu_data`` Structure
813	~~~~~~~~~~~~~~~~~~~~~~~~~~
814
815	The ``rcu_data`` maintains the per-CPU state for the RCU subsystem. The
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
818	of quiescent-state detection and RCU callback queuing. It also tracks
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
822	copy of the grace-period information to allow for-free synchronized
823	access to this information from the corresponding CPU. Finally, this
824	structure records past dyntick-idle state for the corresponding CPU and
825	also tracks statistics.
826
827	The ``rcu_data`` structure's fields are discussed, singly and in groups,
828	in the following sections.
829
830	Connection to Other Data Structures
831	'''''''''''''''''''''''''''''''''''
832
833	This portion of the ``rcu_data`` structure is declared as follows:
834
835	::
836
837	1 int cpu;
838	2 struct rcu_node *mynode;
839	3 unsigned long grpmask;
840	4 bool beenonline;
841
842	The ``->cpu`` field contains the number of the corresponding CPU and the
843	``->mynode`` field references the corresponding ``rcu_node`` structure.
844	The ``->mynode`` is used to propagate quiescent states up the combining
845	tree. These two fields are constant and therefore do not require
846	synchronization.
847
848	The ``->grpmask`` field indicates the bit in the ``->mynode->qsmask``
849	corresponding to this ``rcu_data`` structure, and is also used when
850	propagating quiescent states. The ``->beenonline`` flag is set whenever
851	the corresponding CPU comes online, which means that the debugfs tracing
852	need not dump out any ``rcu_data`` structure for which this flag is not
853	set.
854
855	Quiescent-State and Grace-Period Tracking
856	'''''''''''''''''''''''''''''''''''''''''
857
858	This portion of the ``rcu_data`` structure is declared as follows:
859
860	::
861
862	1 unsigned long gp_seq;
863	2 unsigned long gp_seq_needed;
864	3 bool cpu_no_qs;
865	4 bool core_needs_qs;
866	5 bool gpwrap;
867
868	The ``->gp_seq`` field is the counterpart of the field of the same name
869	in the ``rcu_state`` and ``rcu_node`` structures. The
870	``->gp_seq_needed`` field is the counterpart of the field of the same
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
873	``CONFIG_NO_HZ_FULL`` kernels can lag arbitrarily far behind for CPUs in
874	dyntick-idle mode (but these counters will catch up upon exit from
875	dyntick-idle mode). If the lower two bits of a given ``rcu_data``
876	structure's ``->gp_seq`` are zero, then this ``rcu_data`` structure
877	believes that RCU is idle.
878
879	+-----------------------------------------------------------------------+
880	\| Quick Quiz: \|
881	+-----------------------------------------------------------------------+
882	\| All this replication of the grace period numbers can only cause \|
883	\| massive confusion. Why not just keep a global sequence number and be \|
884	\| done with it??? \|
885	+-----------------------------------------------------------------------+
886	\| Answer: \|
887	+-----------------------------------------------------------------------+
888	\| Because if there was only a single global sequence numbers, there \|
889	\| would need to be a single global lock to allow safely accessing and \|
890	\| updating it. And if we are not going to have a single global lock, we \|
891	\| need to carefully manage the numbers on a per-node basis. Recall from \|
892	\| the answer to a previous Quick Quiz that the consequences of applying \|
893	\| a previously sampled quiescent state to the wrong grace period are \|
894	\| quite severe. \|
895	+-----------------------------------------------------------------------+
896
897	The ``->cpu_no_qs`` flag indicates that the CPU has not yet passed
898	through a quiescent state, while the ``->core_needs_qs`` flag indicates
899	that the RCU core needs a quiescent state from the corresponding CPU.
900	The ``->gpwrap`` field indicates that the corresponding CPU has remained
901	idle for so long that the ``gp_seq`` counter is in danger of overflow,
902	which will cause the CPU to disregard the values of its counters on its
903	next exit from idle.
904
905	RCU Callback Handling
906	'''''''''''''''''''''
907
908	In the absence of CPU-hotplug events, RCU callbacks are invoked by the
909	same CPU that registered them. This is strictly a cache-locality
910	optimization: callbacks can and do get invoked on CPUs other than the
911	one that registered them. After all, if the CPU that registered a given
912	callback has gone offline before the callback can be invoked, there
913	really is no other choice.
914
915	This portion of the ``rcu_data`` structure is declared as follows:
916
917	::
918
919	1 struct rcu_segcblist cblist;
920	2 long qlen_last_fqs_check;
921	3 unsigned long n_cbs_invoked;
922	4 unsigned long n_nocbs_invoked;
923	5 unsigned long n_cbs_orphaned;
924	6 unsigned long n_cbs_adopted;
925	7 unsigned long n_force_qs_snap;
926	8 long blimit;
927
928	The ``->cblist`` structure is the segmented callback list described
929	earlier. The CPU advances the callbacks in its ``rcu_data`` structure
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
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
935	each grace period.
936
937	The ``->qlen_last_fqs_check`` and ``->n_force_qs_snap`` coordinate the
938	forcing of quiescent states from ``call_rcu()`` and friends when
939	callback lists grow excessively long.
940
941	The ``->n_cbs_invoked``, ``->n_cbs_orphaned``, and ``->n_cbs_adopted``
942	fields count the number of callbacks invoked, sent to other CPUs when
943	this CPU goes offline, and received from other CPUs when those other
944	CPUs go offline. The ``->n_nocbs_invoked`` is used when the CPU's
945	callbacks are offloaded to a kthread.
946
947	Finally, the ``->blimit`` counter is the maximum number of RCU callbacks
948	that may be invoked at a given time.
949
950	Dyntick-Idle Handling
951	'''''''''''''''''''''
952
953	This portion of the ``rcu_data`` structure is declared as follows:
954
955	::
956
957	1 int watching_snap;
958	2 unsigned long dynticks_fqs;
959
960	The ``->watching_snap`` field is used to take a snapshot of the
961	corresponding CPU's dyntick-idle state when forcing quiescent states,
962	and is therefore accessed from other CPUs. Finally, the
963	``->dynticks_fqs`` field is used to count the number of times this CPU
964	is determined to be in dyntick-idle state, and is used for tracing and
965	debugging purposes.
966
967	This portion of the rcu_data structure is declared as follows:
968
969	::
970
971	1 long nesting;
972	2 long nmi_nesting;
973	3 atomic_t dynticks;
974	4 bool rcu_need_heavy_qs;
975	5 bool rcu_urgent_qs;
976
977	These fields in the rcu_data structure maintain the per-CPU dyntick-idle
978	state for the corresponding CPU. The fields may be accessed only from
979	the corresponding CPU (and from tracing) unless otherwise stated.
980
981	The ``->nesting`` field counts the nesting depth of process
982	execution, so that in normal circumstances this counter has value zero
983	or one. NMIs, irqs, and tracers are counted by the
984	``->nmi_nesting`` field. Because NMIs cannot be masked, changes
985	to this variable have to be undertaken carefully using an algorithm
986	provided by Andy Lutomirski. The initial transition from idle adds one,
987	and nested transitions add two, so that a nesting level of five is
988	represented by a ``->nmi_nesting`` value of nine. This counter
989	can therefore be thought of as counting the number of reasons why this
990	CPU cannot be permitted to enter dyntick-idle mode, aside from
991	process-level transitions.
992
993	However, it turns out that when running in non-idle kernel context, the
994	Linux kernel is fully capable of entering interrupt handlers that never
995	exit and perhaps also vice versa. Therefore, whenever the
996	``->nesting`` field is incremented up from zero, the
997	``->nmi_nesting`` field is set to a large positive number, and
998	whenever the ``->nesting`` field is decremented down to zero,
999	the ``->nmi_nesting`` field is set to zero. Assuming that
1000	the number of misnested interrupts is not sufficient to overflow the
1001	counter, this approach corrects the ``->nmi_nesting`` field
1002	every time the corresponding CPU enters the idle loop from process
1003	context.
1004
1005	The ``->dynticks`` field counts the corresponding CPU's transitions to
1006	and from either dyntick-idle or user mode, so that this counter has an
1007	even value when the CPU is in dyntick-idle mode or user mode and an odd
1008	value otherwise. The transitions to/from user mode need to be counted
1009	for user mode adaptive-ticks support (see Documentation/timers/no_hz.rst).
1010
1011	The ``->rcu_need_heavy_qs`` field is used to record the fact that the
1012	RCU core code would really like to see a quiescent state from the
1013	corresponding CPU, so much so that it is willing to call for
1014	heavy-weight dyntick-counter operations. This flag is checked by RCU's
1015	context-switch and ``cond_resched()`` code, which provide a momentary
1016	idle sojourn in response.
1017
1018	Finally, the ``->rcu_urgent_qs`` field is used to record the fact that
1019	the RCU core code would really like to see a quiescent state from the
1020	corresponding CPU, with the various other fields indicating just how
1021	badly RCU wants this quiescent state. This flag is checked by RCU's
1022	context-switch path (``rcu_note_context_switch``) and the cond_resched
1023	code.
1024
1025	+-----------------------------------------------------------------------+
1026	\| Quick Quiz: \|
1027	+-----------------------------------------------------------------------+
1028	\| Why not simply combine the ``->nesting`` and \|
1029	\| ``->nmi_nesting`` counters into a single counter that just \|
1030	\| counts the number of reasons that the corresponding CPU is non-idle? \|
1031	+-----------------------------------------------------------------------+
1032	\| Answer: \|
1033	+-----------------------------------------------------------------------+
1034	\| Because this would fail in the presence of interrupts whose handlers \|
1035	\| never return and of handlers that manage to return from a made-up \|
1036	\| interrupt. \|
1037	+-----------------------------------------------------------------------+
1038
1039	Additional fields are present for some special-purpose builds, and are
1040	discussed separately.
1041
1042	The ``rcu_head`` Structure
1043	~~~~~~~~~~~~~~~~~~~~~~~~~~
1044
1045	Each ``rcu_head`` structure represents an RCU callback. These structures
1046	are normally embedded within RCU-protected data structures whose
1047	algorithms use asynchronous grace periods. In contrast, when using
1048	algorithms that block waiting for RCU grace periods, RCU users need not
1049	provide ``rcu_head`` structures.
1050
1051	The ``rcu_head`` structure has fields as follows:
1052
1053	::
1054
1055	1 struct rcu_head *next;
1056	2 void (func)(struct rcu_head head);
1057
1058	The ``->next`` field is used to link the ``rcu_head`` structures
1059	together in the lists within the ``rcu_data`` structures. The ``->func``
1060	field is a pointer to the function to be called when the callback is
1061	ready to be invoked, and this function is passed a pointer to the
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.
1065
1066	Both of these fields are used internally by RCU. From the viewpoint of
1067	RCU users, this structure is an opaque “cookie”.
1068
1069	+-----------------------------------------------------------------------+
1070	\| Quick Quiz: \|
1071	+-----------------------------------------------------------------------+
1072	\| Given that the callback function ``->func`` is passed a pointer to \|
1073	\| the ``rcu_head`` structure, how is that function supposed to find the \|
1074	\| beginning of the enclosing RCU-protected data structure? \|
1075	+-----------------------------------------------------------------------+
1076	\| Answer: \|
1077	+-----------------------------------------------------------------------+
1078	\| In actual practice, there is a separate callback function per type of \|
1079	\| RCU-protected data structure. The callback function can therefore use \|
1080	\| the ``container_of()`` macro in the Linux kernel (or other \|
1081	\| pointer-manipulation facilities in other software environments) to \|
1082	\| find the beginning of the enclosing structure. \|
1083	+-----------------------------------------------------------------------+
1084
1085	RCU-Specific Fields in the ``task_struct`` Structure
1086	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1087
1088	The ``CONFIG_PREEMPT_RCU`` implementation uses some additional fields in
1089	the ``task_struct`` structure:
1090
1091	::
1092
1093	1 #ifdef CONFIG_PREEMPT_RCU
1094	2 int rcu_read_lock_nesting;
1095	3 union rcu_special rcu_read_unlock_special;
1096	4 struct list_head rcu_node_entry;
1097	5 struct rcu_node *rcu_blocked_node;
1098	6 #endif /* #ifdef CONFIG_PREEMPT_RCU */
1099	7 #ifdef CONFIG_TASKS_RCU
1100	8 unsigned long rcu_tasks_nvcsw;
1101	9 bool rcu_tasks_holdout;
1102	10 struct list_head rcu_tasks_holdout_list;
1103	11 int rcu_tasks_idle_cpu;
1104	12 #endif /* #ifdef CONFIG_TASKS_RCU */
1105
1106	The ``->rcu_read_lock_nesting`` field records the nesting level for RCU
1107	read-side critical sections, and the ``->rcu_read_unlock_special`` field
1108	is a bitmask that records special conditions that require
1109	``rcu_read_unlock()`` to do additional work. The ``->rcu_node_entry``
1110	field is used to form lists of tasks that have blocked within
1111	preemptible-RCU read-side critical sections and the
1112	``->rcu_blocked_node`` field references the ``rcu_node`` structure whose
1113	list this task is a member of, or ``NULL`` if it is not blocked within a
1114	preemptible-RCU read-side critical section.
1115
1116	The ``->rcu_tasks_nvcsw`` field tracks the number of voluntary context
1117	switches that this task had undergone at the beginning of the current
1118	tasks-RCU grace period, ``->rcu_tasks_holdout`` is set if the current
1119	tasks-RCU grace period is waiting on this task,
1120	``->rcu_tasks_holdout_list`` is a list element enqueuing this task on
1121	the holdout list, and ``->rcu_tasks_idle_cpu`` tracks which CPU this
1122	idle task is running, but only if the task is currently running, that
1123	is, if the CPU is currently idle.
1124
1125	Accessor Functions
1126	~~~~~~~~~~~~~~~~~~
1127
1128	The following listing shows the ``rcu_get_root()``,
1129	``rcu_for_each_node_breadth_first`` and ``rcu_for_each_leaf_node()``
1130	function and macros:
1131
1132	::
1133
1134	1 static struct rcu_node rcu_get_root(struct rcu_state rsp)
1135	2 {
1136	3 return &rsp->node[0];
1137	4 }
1138	5
1139	6 #define rcu_for_each_node_breadth_first(rsp, rnp) \
1140	7 for ((rnp) = &(rsp)->node[0]; \
1141	8 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
1142	9
1143	10 #define rcu_for_each_leaf_node(rsp, rnp) \
1144	11 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \
1145	12 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
1146
1147	The ``rcu_get_root()`` simply returns a pointer to the first element of
1148	the specified ``rcu_state`` structure's ``->node[]`` array, which is the
1149	root ``rcu_node`` structure.
1150
1151	As noted earlier, the ``rcu_for_each_node_breadth_first()`` macro takes
1152	advantage of the layout of the ``rcu_node`` structures in the
1153	``rcu_state`` structure's ``->node[]`` array, performing a breadth-first
1154	traversal by simply traversing the array in order. Similarly, the
1155	``rcu_for_each_leaf_node()`` macro traverses only the last part of the
1156	array, thus traversing only the leaf ``rcu_node`` structures.
1157
1158	+-----------------------------------------------------------------------+
1159	\| Quick Quiz: \|
1160	+-----------------------------------------------------------------------+
1161	\| What does ``rcu_for_each_leaf_node()`` do if the ``rcu_node`` tree \|
1162	\| contains only a single node? \|
1163	+-----------------------------------------------------------------------+
1164	\| Answer: \|
1165	+-----------------------------------------------------------------------+
1166	\| In the single-node case, ``rcu_for_each_leaf_node()`` traverses the \|
1167	\| single node. \|
1168	+-----------------------------------------------------------------------+
1169
1170	Summary
1171	~~~~~~~
1172
1173	So the state of RCU is represented by an ``rcu_state`` structure, which
1174	contains a combining tree of ``rcu_node`` and ``rcu_data`` structures.
1175	Finally, in ``CONFIG_NO_HZ_IDLE`` kernels, each CPU's dyntick-idle state
1176	is tracked by dynticks-related fields in the ``rcu_data`` structure. If
1177	you made it this far, you are well prepared to read the code
1178	walkthroughs in the other articles in this series.
1179
1180	Acknowledgments
1181	~~~~~~~~~~~~~~~
1182
1183	I owe thanks to Cyrill Gorcunov, Mathieu Desnoyers, Dhaval Giani, Paul
1184	Turner, Abhishek Srivastava, Matt Kowalczyk, and Serge Hallyn for
1185	helping me get this document into a more human-readable state.
1186
1187	Legal Statement
1188	~~~~~~~~~~~~~~~
1189
1190	This work represents the view of the author and does not necessarily
1191	represent the view of IBM.
1192
1193	Linux is a registered trademark of Linus Torvalds.
1194
1195	Other company, product, and service names may be trademarks or service
1196	marks of others.