1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" 2 "http://www.w3.org/TR/html4/loose.dtd"> 3 <html> 4 <head><title>A Tour Through TREE_RCU's Data Structures [LWN.net]</title> 5 <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> 6 7 <p>December 18, 2016</p> 8 <p>This article was contributed by Paul E. McKenney</p> 9 10<h3>Introduction</h3> 11 12This document describes RCU's major data structures and their relationship 13to each other. 14 15<ol> 16<li> <a href="#Data-Structure Relationships"> 17 Data-Structure Relationships</a> 18<li> <a href="#The rcu_state Structure"> 19 The <tt>rcu_state</tt> Structure</a> 20<li> <a href="#The rcu_node Structure"> 21 The <tt>rcu_node</tt> Structure</a> 22<li> <a href="#The rcu_segcblist Structure"> 23 The <tt>rcu_segcblist</tt> Structure</a> 24<li> <a href="#The rcu_data Structure"> 25 The <tt>rcu_data</tt> Structure</a> 26<li> <a href="#The rcu_dynticks Structure"> 27 The <tt>rcu_dynticks</tt> Structure</a> 28<li> <a href="#The rcu_head Structure"> 29 The <tt>rcu_head</tt> Structure</a> 30<li> <a href="#RCU-Specific Fields in the task_struct Structure"> 31 RCU-Specific Fields in the <tt>task_struct</tt> Structure</a> 32<li> <a href="#Accessor Functions"> 33 Accessor Functions</a> 34</ol> 35 36<h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3> 37 38<p>RCU is for all intents and purposes a large state machine, and its 39data structures maintain the state in such a way as to allow RCU readers 40to execute extremely quickly, while also processing the RCU grace periods 41requested by updaters in an efficient and extremely scalable fashion. 42The efficiency and scalability of RCU updaters is provided primarily 43by a combining tree, as shown below: 44 45</p><p><img src="BigTreeClassicRCU.svg" alt="BigTreeClassicRCU.svg" width="30%"> 46 47</p><p>This diagram shows an enclosing <tt>rcu_state</tt> structure 48containing a tree of <tt>rcu_node</tt> structures. 49Each leaf node of the <tt>rcu_node</tt> tree has up to 16 50<tt>rcu_data</tt> structures associated with it, so that there 51are <tt>NR_CPUS</tt> number of <tt>rcu_data</tt> structures, 52one for each possible CPU. 53This structure is adjusted at boot time, if needed, to handle the 54common case where <tt>nr_cpu_ids</tt> is much less than 55<tt>NR_CPUs</tt>. 56For example, a number of Linux distributions set <tt>NR_CPUs=4096</tt>, 57which results in a three-level <tt>rcu_node</tt> tree. 58If the actual hardware has only 16 CPUs, RCU will adjust itself 59at boot time, resulting in an <tt>rcu_node</tt> tree with only a single node. 60 61</p><p>The purpose of this combining tree is to allow per-CPU events 62such as quiescent states, dyntick-idle transitions, 63and CPU hotplug operations to be processed efficiently 64and scalably. 65Quiescent states are recorded by the per-CPU <tt>rcu_data</tt> structures, 66and other events are recorded by the leaf-level <tt>rcu_node</tt> 67structures. 68All of these events are combined at each level of the tree until finally 69grace periods are completed at the tree's root <tt>rcu_node</tt> 70structure. 71A grace period can be completed at the root once every CPU 72(or, in the case of <tt>CONFIG_PREEMPT_RCU</tt>, task) 73has passed through a quiescent state. 74Once a grace period has completed, record of that fact is propagated 75back down the tree. 76 77</p><p>As can be seen from the diagram, on a 64-bit system 78a two-level tree with 64 leaves can accommodate 1,024 CPUs, with a fanout 79of 64 at the root and a fanout of 16 at the leaves. 80 81<table> 82<tr><th> </th></tr> 83<tr><th align="left">Quick Quiz:</th></tr> 84<tr><td> 85 Why isn't the fanout at the leaves also 64? 86</td></tr> 87<tr><th align="left">Answer:</th></tr> 88<tr><td bgcolor="#ffffff"><font color="ffffff"> 89 Because there are more types of events that affect the leaf-level 90 <tt>rcu_node</tt> structures than further up the tree. 91 Therefore, if the leaf <tt>rcu_node</tt> structures have fanout of 92 64, the contention on these structures' <tt>->structures</tt> 93 becomes excessive. 94 Experimentation on a wide variety of systems has shown that a fanout 95 of 16 works well for the leaves of the <tt>rcu_node</tt> tree. 96 </font> 97 98 <p><font color="ffffff">Of course, further experience with 99 systems having hundreds or thousands of CPUs may demonstrate 100 that the fanout for the non-leaf <tt>rcu_node</tt> structures 101 must also be reduced. 102 Such reduction can be easily carried out when and if it proves 103 necessary. 104 In the meantime, if you are using such a system and running into 105 contention problems on the non-leaf <tt>rcu_node</tt> structures, 106 you may use the <tt>CONFIG_RCU_FANOUT</tt> kernel configuration 107 parameter to reduce the non-leaf fanout as needed. 108 </font> 109 110 <p><font color="ffffff">Kernels built for systems with 111 strong NUMA characteristics might also need to adjust 112 <tt>CONFIG_RCU_FANOUT</tt> so that the domains of the 113 <tt>rcu_node</tt> structures align with hardware boundaries. 114 However, there has thus far been no need for this. 115</font></td></tr> 116<tr><td> </td></tr> 117</table> 118 119<p>If your system has more than 1,024 CPUs (or more than 512 CPUs on 120a 32-bit system), then RCU will automatically add more levels to the 121tree. 122For example, if you are crazy enough to build a 64-bit system with 65,536 123CPUs, RCU would configure the <tt>rcu_node</tt> tree as follows: 124 125</p><p><img src="HugeTreeClassicRCU.svg" alt="HugeTreeClassicRCU.svg" width="50%"> 126 127</p><p>RCU currently permits up to a four-level tree, which on a 64-bit system 128accommodates up to 4,194,304 CPUs, though only a mere 524,288 CPUs for 12932-bit systems. 130On the other hand, you can set <tt>CONFIG_RCU_FANOUT</tt> to be 131as small as 2 if you wish, which would permit only 16 CPUs, which 132is useful for testing. 133 134</p><p>This multi-level combining tree allows us to get most of the 135performance and scalability 136benefits of partitioning, even though RCU grace-period detection is 137inherently a global operation. 138The trick here is that only the last CPU to report a quiescent state 139into a given <tt>rcu_node</tt> structure need advance to the <tt>rcu_node</tt> 140structure at the next level up the tree. 141This means that at the leaf-level <tt>rcu_node</tt> structure, only 142one access out of sixteen will progress up the tree. 143For the internal <tt>rcu_node</tt> structures, the situation is even 144more extreme: Only one access out of sixty-four will progress up 145the tree. 146Because the vast majority of the CPUs do not progress up the tree, 147the lock contention remains roughly constant up the tree. 148No matter how many CPUs there are in the system, at most 64 quiescent-state 149reports per grace period will progress all the way to the root 150<tt>rcu_node</tt> structure, thus ensuring that the lock contention 151on that root <tt>rcu_node</tt> structure remains acceptably low. 152 153</p><p>In effect, the combining tree acts like a big shock absorber, 154keeping lock contention under control at all tree levels regardless 155of the level of loading on the system. 156 157</p><p>The Linux kernel actually supports multiple flavors of RCU 158running concurrently, so RCU builds separate data structures for each 159flavor. 160For example, for <tt>CONFIG_TREE_RCU=y</tt> kernels, RCU provides 161rcu_sched and rcu_bh, as shown below: 162 163</p><p><img src="BigTreeClassicRCUBH.svg" alt="BigTreeClassicRCUBH.svg" width="33%"> 164 165</p><p>Energy efficiency is increasingly important, and for that 166reason the Linux kernel provides <tt>CONFIG_NO_HZ_IDLE</tt>, which 167turns off the scheduling-clock interrupts on idle CPUs, which in 168turn allows those CPUs to attain deeper sleep states and to consume 169less energy. 170CPUs whose scheduling-clock interrupts have been turned off are 171said to be in <i>dyntick-idle mode</i>. 172RCU must handle dyntick-idle CPUs specially 173because RCU would otherwise wake up each CPU on every grace period, 174which would defeat the whole purpose of <tt>CONFIG_NO_HZ_IDLE</tt>. 175RCU uses the <tt>rcu_dynticks</tt> structure to track 176which CPUs are in dyntick idle mode, as shown below: 177 178</p><p><img src="BigTreeClassicRCUBHdyntick.svg" alt="BigTreeClassicRCUBHdyntick.svg" width="33%"> 179 180</p><p>However, if a CPU is in dyntick-idle mode, it is in that mode 181for all flavors of RCU. 182Therefore, a single <tt>rcu_dynticks</tt> structure is allocated per 183CPU, and all of a given CPU's <tt>rcu_data</tt> structures share 184that <tt>rcu_dynticks</tt>, as shown in the figure. 185 186</p><p>Kernels built with <tt>CONFIG_PREEMPT_RCU</tt> support 187rcu_preempt in addition to rcu_sched and rcu_bh, as shown below: 188 189</p><p><img src="BigTreePreemptRCUBHdyntick.svg" alt="BigTreePreemptRCUBHdyntick.svg" width="35%"> 190 191</p><p>RCU updaters wait for normal grace periods by registering 192RCU callbacks, either directly via <tt>call_rcu()</tt> and 193friends (namely <tt>call_rcu_bh()</tt> and <tt>call_rcu_sched()</tt>), 194there being a separate interface per flavor of RCU) 195or indirectly via <tt>synchronize_rcu()</tt> and friends. 196RCU callbacks are represented by <tt>rcu_head</tt> structures, 197which are queued on <tt>rcu_data</tt> structures while they are 198waiting for a grace period to elapse, as shown in the following figure: 199 200</p><p><img src="BigTreePreemptRCUBHdyntickCB.svg" alt="BigTreePreemptRCUBHdyntickCB.svg" width="40%"> 201 202</p><p>This figure shows how <tt>TREE_RCU</tt>'s and 203<tt>PREEMPT_RCU</tt>'s major data structures are related. 204Lesser data structures will be introduced with the algorithms that 205make use of them. 206 207</p><p>Note that each of the data structures in the above figure has 208its own synchronization: 209 210<p><ol> 211<li> Each <tt>rcu_state</tt> structures has a lock and a mutex, 212 and some fields are protected by the corresponding root 213 <tt>rcu_node</tt> structure's lock. 214<li> Each <tt>rcu_node</tt> structure has a spinlock. 215<li> The fields in <tt>rcu_data</tt> are private to the corresponding 216 CPU, although a few can be read and written by other CPUs. 217<li> Similarly, the fields in <tt>rcu_dynticks</tt> are private 218 to the corresponding CPU, although a few can be read by 219 other CPUs. 220</ol> 221 222<p>It is important to note that different data structures can have 223very different ideas about the state of RCU at any given time. 224For but one example, awareness of the start or end of a given RCU 225grace period propagates slowly through the data structures. 226This slow propagation is absolutely necessary for RCU to have good 227read-side performance. 228If this balkanized implementation seems foreign to you, one useful 229trick is to consider each instance of these data structures to be 230a different person, each having the usual slightly different 231view of reality. 232 233</p><p>The general role of each of these data structures is as 234follows: 235 236</p><ol> 237<li> <tt>rcu_state</tt>: 238 This structure forms the interconnection between the 239 <tt>rcu_node</tt> and <tt>rcu_data</tt> structures, 240 tracks grace periods, serves as short-term repository 241 for callbacks orphaned by CPU-hotplug events, 242 maintains <tt>rcu_barrier()</tt> state, 243 tracks expedited grace-period state, 244 and maintains state used to force quiescent states when 245 grace periods extend too long, 246<li> <tt>rcu_node</tt>: This structure forms the combining 247 tree that propagates quiescent-state 248 information from the leaves to the root, and also propagates 249 grace-period information from the root to the leaves. 250 It provides local copies of the grace-period state in order 251 to allow this information to be accessed in a synchronized 252 manner without suffering the scalability limitations that 253 would otherwise be imposed by global locking. 254 In <tt>CONFIG_PREEMPT_RCU</tt> kernels, it manages the lists 255 of tasks that have blocked while in their current 256 RCU read-side critical section. 257 In <tt>CONFIG_PREEMPT_RCU</tt> with 258 <tt>CONFIG_RCU_BOOST</tt>, it manages the 259 per-<tt>rcu_node</tt> priority-boosting 260 kernel threads (kthreads) and state. 261 Finally, it records CPU-hotplug state in order to determine 262 which CPUs should be ignored during a given grace period. 263<li> <tt>rcu_data</tt>: This per-CPU structure is the 264 focus of quiescent-state detection and RCU callback queuing. 265 It also tracks its relationship to the corresponding leaf 266 <tt>rcu_node</tt> structure to allow more-efficient 267 propagation of quiescent states up the <tt>rcu_node</tt> 268 combining tree. 269 Like the <tt>rcu_node</tt> structure, it provides a local 270 copy of the grace-period information to allow for-free 271 synchronized 272 access to this information from the corresponding CPU. 273 Finally, this structure records past dyntick-idle state 274 for the corresponding CPU and also tracks statistics. 275<li> <tt>rcu_dynticks</tt>: 276 This per-CPU structure tracks the current dyntick-idle 277 state for the corresponding CPU. 278 Unlike the other three structures, the <tt>rcu_dynticks</tt> 279 structure is not replicated per RCU flavor. 280<li> <tt>rcu_head</tt>: 281 This structure represents RCU callbacks, and is the 282 only structure allocated and managed by RCU users. 283 The <tt>rcu_head</tt> structure is normally embedded 284 within the RCU-protected data structure. 285</ol> 286 287<p>If all you wanted from this article was a general notion of how 288RCU's data structures are related, you are done. 289Otherwise, each of the following sections give more details on 290the <tt>rcu_state</tt>, <tt>rcu_node</tt>, <tt>rcu_data</tt>, 291and <tt>rcu_dynticks</tt> data structures. 292 293<h3><a name="The rcu_state Structure"> 294The <tt>rcu_state</tt> Structure</a></h3> 295 296<p>The <tt>rcu_state</tt> structure is the base structure that 297represents a flavor of RCU. 298This structure forms the interconnection between the 299<tt>rcu_node</tt> and <tt>rcu_data</tt> structures, 300tracks grace periods, contains the lock used to 301synchronize with CPU-hotplug events, 302and maintains state used to force quiescent states when 303grace periods extend too long, 304 305</p><p>A few of the <tt>rcu_state</tt> structure's fields are discussed, 306singly and in groups, in the following sections. 307The more specialized fields are covered in the discussion of their 308use. 309 310<h5>Relationship to rcu_node and rcu_data Structures</h5> 311 312This portion of the <tt>rcu_state</tt> structure is declared 313as follows: 314 315<pre> 316 1 struct rcu_node node[NUM_RCU_NODES]; 317 2 struct rcu_node *level[NUM_RCU_LVLS + 1]; 318 3 struct rcu_data __percpu *rda; 319</pre> 320 321<table> 322<tr><th> </th></tr> 323<tr><th align="left">Quick Quiz:</th></tr> 324<tr><td> 325 Wait a minute! 326 You said that the <tt>rcu_node</tt> structures formed a tree, 327 but they are declared as a flat array! 328 What gives? 329</td></tr> 330<tr><th align="left">Answer:</th></tr> 331<tr><td bgcolor="#ffffff"><font color="ffffff"> 332 The tree is laid out in the array. 333 The first node In the array is the head, the next set of nodes in the 334 array are children of the head node, and so on until the last set of 335 nodes in the array are the leaves. 336 </font> 337 338 <p><font color="ffffff">See the following diagrams to see how 339 this works. 340</font></td></tr> 341<tr><td> </td></tr> 342</table> 343 344<p>The <tt>rcu_node</tt> tree is embedded into the 345<tt>->node[]</tt> array as shown in the following figure: 346 347</p><p><img src="TreeMapping.svg" alt="TreeMapping.svg" width="40%"> 348 349</p><p>One interesting consequence of this mapping is that a 350breadth-first traversal of the tree is implemented as a simple 351linear scan of the array, which is in fact what the 352<tt>rcu_for_each_node_breadth_first()</tt> macro does. 353This macro is used at the beginning and ends of grace periods. 354 355</p><p>Each entry of the <tt>->level</tt> array references 356the first <tt>rcu_node</tt> structure on the corresponding level 357of the tree, for example, as shown below: 358 359</p><p><img src="TreeMappingLevel.svg" alt="TreeMappingLevel.svg" width="40%"> 360 361</p><p>The zero<sup>th</sup> element of the array references the root 362<tt>rcu_node</tt> structure, the first element references the 363first child of the root <tt>rcu_node</tt>, and finally the second 364element references the first leaf <tt>rcu_node</tt> structure. 365 366</p><p>For whatever it is worth, if you draw the tree to be tree-shaped 367rather than array-shaped, it is easy to draw a planar representation: 368 369</p><p><img src="TreeLevel.svg" alt="TreeLevel.svg" width="60%"> 370 371</p><p>Finally, the <tt>->rda</tt> field references a per-CPU 372pointer to the corresponding CPU's <tt>rcu_data</tt> structure. 373 374</p><p>All of these fields are constant once initialization is complete, 375and therefore need no protection. 376 377<h5>Grace-Period Tracking</h5> 378 379<p>This portion of the <tt>rcu_state</tt> structure is declared 380as follows: 381 382<pre> 383 1 unsigned long gpnum; 384 2 unsigned long completed; 385</pre> 386 387<p>RCU grace periods are numbered, and 388the <tt>->gpnum</tt> field contains the number of the grace 389period that started most recently. 390The <tt>->completed</tt> field contains the number of the 391grace period that completed most recently. 392If the two fields are equal, the RCU grace period that most recently 393started has already completed, and therefore the corresponding 394flavor of RCU is idle. 395If <tt>->gpnum</tt> is one greater than <tt>->completed</tt>, 396then <tt>->gpnum</tt> gives the number of the current RCU 397grace period, which has not yet completed. 398Any other combination of values indicates that something is broken. 399These two fields are protected by the root <tt>rcu_node</tt>'s 400<tt>->lock</tt> field. 401 402</p><p>There are <tt>->gpnum</tt> and <tt>->completed</tt> fields 403in the <tt>rcu_node</tt> and <tt>rcu_data</tt> structures 404as well. 405The fields in the <tt>rcu_state</tt> structure represent the 406most current values, and those of the other structures are compared 407in order to detect the start of a new grace period in a distributed 408fashion. 409The values flow from <tt>rcu_state</tt> to <tt>rcu_node</tt> 410(down the tree from the root to the leaves) to <tt>rcu_data</tt>. 411 412<h5>Miscellaneous</h5> 413 414<p>This portion of the <tt>rcu_state</tt> structure is declared 415as follows: 416 417<pre> 418 1 unsigned long gp_max; 419 2 char abbr; 420 3 char *name; 421</pre> 422 423<p>The <tt>->gp_max</tt> field tracks the duration of the longest 424grace period in jiffies. 425It is protected by the root <tt>rcu_node</tt>'s <tt>->lock</tt>. 426 427<p>The <tt>->name</tt> field points to the name of the RCU flavor 428(for example, “rcu_sched”), and is constant. 429The <tt>->abbr</tt> field contains a one-character abbreviation, 430for example, “s” for RCU-sched. 431 432<h3><a name="The rcu_node Structure"> 433The <tt>rcu_node</tt> Structure</a></h3> 434 435<p>The <tt>rcu_node</tt> structures form the combining 436tree that propagates quiescent-state 437information from the leaves to the root and also that propagates 438grace-period information from the root down to the leaves. 439They provides local copies of the grace-period state in order 440to allow this information to be accessed in a synchronized 441manner without suffering the scalability limitations that 442would otherwise be imposed by global locking. 443In <tt>CONFIG_PREEMPT_RCU</tt> kernels, they manage the lists 444of tasks that have blocked while in their current 445RCU read-side critical section. 446In <tt>CONFIG_PREEMPT_RCU</tt> with 447<tt>CONFIG_RCU_BOOST</tt>, they manage the 448per-<tt>rcu_node</tt> priority-boosting 449kernel threads (kthreads) and state. 450Finally, they record CPU-hotplug state in order to determine 451which CPUs should be ignored during a given grace period. 452 453</p><p>The <tt>rcu_node</tt> structure's fields are discussed, 454singly and in groups, in the following sections. 455 456<h5>Connection to Combining Tree</h5> 457 458<p>This portion of the <tt>rcu_node</tt> structure is declared 459as follows: 460 461<pre> 462 1 struct rcu_node *parent; 463 2 u8 level; 464 3 u8 grpnum; 465 4 unsigned long grpmask; 466 5 int grplo; 467 6 int grphi; 468</pre> 469 470<p>The <tt>->parent</tt> pointer references the <tt>rcu_node</tt> 471one level up in the tree, and is <tt>NULL</tt> for the root 472<tt>rcu_node</tt>. 473The RCU implementation makes heavy use of this field to push quiescent 474states up the tree. 475The <tt>->level</tt> field gives the level in the tree, with 476the root being at level zero, its children at level one, and so on. 477The <tt>->grpnum</tt> field gives this node's position within 478the children of its parent, so this number can range between 0 and 31 479on 32-bit systems and between 0 and 63 on 64-bit systems. 480The <tt>->level</tt> and <tt>->grpnum</tt> fields are 481used only during initialization and for tracing. 482The <tt>->grpmask</tt> field is the bitmask counterpart of 483<tt>->grpnum</tt>, and therefore always has exactly one bit set. 484This mask is used to clear the bit corresponding to this <tt>rcu_node</tt> 485structure in its parent's bitmasks, which are described later. 486Finally, the <tt>->grplo</tt> and <tt>->grphi</tt> fields 487contain the lowest and highest numbered CPU served by this 488<tt>rcu_node</tt> structure, respectively. 489 490</p><p>All of these fields are constant, and thus do not require any 491synchronization. 492 493<h5>Synchronization</h5> 494 495<p>This field of the <tt>rcu_node</tt> structure is declared 496as follows: 497 498<pre> 499 1 raw_spinlock_t lock; 500</pre> 501 502<p>This field is used to protect the remaining fields in this structure, 503unless otherwise stated. 504That said, all of the fields in this structure can be accessed without 505locking for tracing purposes. 506Yes, this can result in confusing traces, but better some tracing confusion 507than to be heisenbugged out of existence. 508 509<h5>Grace-Period Tracking</h5> 510 511<p>This portion of the <tt>rcu_node</tt> structure is declared 512as follows: 513 514<pre> 515 1 unsigned long gpnum; 516 2 unsigned long completed; 517</pre> 518 519<p>These fields are the counterparts of the fields of the same name in 520the <tt>rcu_state</tt> structure. 521They each may lag up to one behind their <tt>rcu_state</tt> 522counterparts. 523If a given <tt>rcu_node</tt> structure's <tt>->gpnum</tt> and 524<tt>->complete</tt> fields are equal, then this <tt>rcu_node</tt> 525structure believes that RCU is idle. 526Otherwise, as with the <tt>rcu_state</tt> structure, 527the <tt>->gpnum</tt> field will be one greater than the 528<tt>->complete</tt> fields, with <tt>->gpnum</tt> 529indicating which grace period this <tt>rcu_node</tt> believes 530is still being waited for. 531 532</p><p>The <tt>>gpnum</tt> field of each <tt>rcu_node</tt> 533structure is updated at the beginning 534of each grace period, and the <tt>->completed</tt> fields are 535updated at the end of each grace period. 536 537<h5>Quiescent-State Tracking</h5> 538 539<p>These fields manage the propagation of quiescent states up the 540combining tree. 541 542</p><p>This portion of the <tt>rcu_node</tt> structure has fields 543as follows: 544 545<pre> 546 1 unsigned long qsmask; 547 2 unsigned long expmask; 548 3 unsigned long qsmaskinit; 549 4 unsigned long expmaskinit; 550</pre> 551 552<p>The <tt>->qsmask</tt> field tracks which of this 553<tt>rcu_node</tt> structure's children still need to report 554quiescent states for the current normal grace period. 555Such children will have a value of 1 in their corresponding bit. 556Note that the leaf <tt>rcu_node</tt> structures should be 557thought of as having <tt>rcu_data</tt> structures as their 558children. 559Similarly, the <tt>->expmask</tt> field tracks which 560of this <tt>rcu_node</tt> structure's children still need to report 561quiescent states for the current expedited grace period. 562An expedited grace period has 563the same conceptual properties as a normal grace period, but the 564expedited implementation accepts extreme CPU overhead to obtain 565much lower grace-period latency, for example, consuming a few 566tens of microseconds worth of CPU time to reduce grace-period 567duration from milliseconds to tens of microseconds. 568The <tt>->qsmaskinit</tt> field tracks which of this 569<tt>rcu_node</tt> structure's children cover for at least 570one online CPU. 571This mask is used to initialize <tt>->qsmask</tt>, 572and <tt>->expmaskinit</tt> is used to initialize 573<tt>->expmask</tt> and the beginning of the 574normal and expedited grace periods, respectively. 575 576<table> 577<tr><th> </th></tr> 578<tr><th align="left">Quick Quiz:</th></tr> 579<tr><td> 580 Why are these bitmasks protected by locking? 581 Come on, haven't you heard of atomic instructions??? 582</td></tr> 583<tr><th align="left">Answer:</th></tr> 584<tr><td bgcolor="#ffffff"><font color="ffffff"> 585 Lockless grace-period computation! Such a tantalizing possibility! 586 </font> 587 588 <p><font color="ffffff">But consider the following sequence of events: 589 </font> 590 591 <ol> 592 <li> <font color="ffffff">CPU 0 has been in dyntick-idle 593 mode for quite some time. 594 When it wakes up, it notices that the current RCU 595 grace period needs it to report in, so it sets a 596 flag where the scheduling clock interrupt will find it. 597 </font><p> 598 <li> <font color="ffffff">Meanwhile, CPU 1 is running 599 <tt>force_quiescent_state()</tt>, 600 and notices that CPU 0 has been in dyntick idle mode, 601 which qualifies as an extended quiescent state. 602 </font><p> 603 <li> <font color="ffffff">CPU 0's scheduling clock 604 interrupt fires in the 605 middle of an RCU read-side critical section, and notices 606 that the RCU core needs something, so commences RCU softirq 607 processing. 608 </font> 609 <p> 610 <li> <font color="ffffff">CPU 0's softirq handler 611 executes and is just about ready 612 to report its quiescent state up the <tt>rcu_node</tt> 613 tree. 614 </font><p> 615 <li> <font color="ffffff">But CPU 1 beats it to the punch, 616 completing the current 617 grace period and starting a new one. 618 </font><p> 619 <li> <font color="ffffff">CPU 0 now reports its quiescent 620 state for the wrong 621 grace period. 622 That grace period might now end before the RCU read-side 623 critical section. 624 If that happens, disaster will ensue. 625 </font> 626 </ol> 627 628 <p><font color="ffffff">So the locking is absolutely required in 629 order to coordinate 630 clearing of the bits with the grace-period numbers in 631 <tt>->gpnum</tt> and <tt>->completed</tt>. 632</font></td></tr> 633<tr><td> </td></tr> 634</table> 635 636<h5>Blocked-Task Management</h5> 637 638<p><tt>PREEMPT_RCU</tt> allows tasks to be preempted in the 639midst of their RCU read-side critical sections, and these tasks 640must be tracked explicitly. 641The details of exactly why and how they are tracked will be covered 642in a separate article on RCU read-side processing. 643For now, it is enough to know that the <tt>rcu_node</tt> 644structure tracks them. 645 646<pre> 647 1 struct list_head blkd_tasks; 648 2 struct list_head *gp_tasks; 649 3 struct list_head *exp_tasks; 650 4 bool wait_blkd_tasks; 651</pre> 652 653<p>The <tt>->blkd_tasks</tt> field is a list header for 654the list of blocked and preempted tasks. 655As tasks undergo context switches within RCU read-side critical 656sections, their <tt>task_struct</tt> structures are enqueued 657(via the <tt>task_struct</tt>'s <tt>->rcu_node_entry</tt> 658field) onto the head of the <tt>->blkd_tasks</tt> list for the 659leaf <tt>rcu_node</tt> structure corresponding to the CPU 660on which the outgoing context switch executed. 661As these tasks later exit their RCU read-side critical sections, 662they remove themselves from the list. 663This list is therefore in reverse time order, so that if one of the tasks 664is blocking the current grace period, all subsequent tasks must 665also be blocking that same grace period. 666Therefore, a single pointer into this list suffices to track 667all tasks blocking a given grace period. 668That pointer is stored in <tt>->gp_tasks</tt> for normal 669grace periods and in <tt>->exp_tasks</tt> for expedited 670grace periods. 671These last two fields are <tt>NULL</tt> if either there is 672no grace period in flight or if there are no blocked tasks 673preventing that grace period from completing. 674If either of these two pointers is referencing a task that 675removes itself from the <tt>->blkd_tasks</tt> list, 676then that task must advance the pointer to the next task on 677the list, or set the pointer to <tt>NULL</tt> if there 678are no subsequent tasks on the list. 679 680</p><p>For example, suppose that tasks T1, T2, and T3 are 681all hard-affinitied to the largest-numbered CPU in the system. 682Then if task T1 blocked in an RCU read-side 683critical section, then an expedited grace period started, 684then task T2 blocked in an RCU read-side critical section, 685then a normal grace period started, and finally task 3 blocked 686in an RCU read-side critical section, then the state of the 687last leaf <tt>rcu_node</tt> structure's blocked-task list 688would be as shown below: 689 690</p><p><img src="blkd_task.svg" alt="blkd_task.svg" width="60%"> 691 692</p><p>Task T1 is blocking both grace periods, task T2 is 693blocking only the normal grace period, and task T3 is blocking 694neither grace period. 695Note that these tasks will not remove themselves from this list 696immediately upon resuming execution. 697They will instead remain on the list until they execute the outermost 698<tt>rcu_read_unlock()</tt> that ends their RCU read-side critical 699section. 700 701<p> 702The <tt>->wait_blkd_tasks</tt> field indicates whether or not 703the current grace period is waiting on a blocked task. 704 705<h5>Sizing the <tt>rcu_node</tt> Array</h5> 706 707<p>The <tt>rcu_node</tt> array is sized via a series of 708C-preprocessor expressions as follows: 709 710<pre> 711 1 #ifdef CONFIG_RCU_FANOUT 712 2 #define RCU_FANOUT CONFIG_RCU_FANOUT 713 3 #else 714 4 # ifdef CONFIG_64BIT 715 5 # define RCU_FANOUT 64 716 6 # else 717 7 # define RCU_FANOUT 32 718 8 # endif 719 9 #endif 72010 72111 #ifdef CONFIG_RCU_FANOUT_LEAF 72212 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF 72313 #else 72414 # ifdef CONFIG_64BIT 72515 # define RCU_FANOUT_LEAF 64 72616 # else 72717 # define RCU_FANOUT_LEAF 32 72818 # endif 72919 #endif 73020 73121 #define RCU_FANOUT_1 (RCU_FANOUT_LEAF) 73222 #define RCU_FANOUT_2 (RCU_FANOUT_1 * RCU_FANOUT) 73323 #define RCU_FANOUT_3 (RCU_FANOUT_2 * RCU_FANOUT) 73424 #define RCU_FANOUT_4 (RCU_FANOUT_3 * RCU_FANOUT) 73525 73626 #if NR_CPUS <= RCU_FANOUT_1 73727 # define RCU_NUM_LVLS 1 73828 # define NUM_RCU_LVL_0 1 73929 # define NUM_RCU_NODES NUM_RCU_LVL_0 74030 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0 } 74131 # define RCU_NODE_NAME_INIT { "rcu_node_0" } 74232 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0" } 74333 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0" } 74434 #elif NR_CPUS <= RCU_FANOUT_2 74535 # define RCU_NUM_LVLS 2 74636 # define NUM_RCU_LVL_0 1 74737 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) 74838 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1) 74939 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1 } 75040 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1" } 75141 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1" } 75242 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1" } 75343 #elif NR_CPUS <= RCU_FANOUT_3 75444 # define RCU_NUM_LVLS 3 75545 # define NUM_RCU_LVL_0 1 75646 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2) 75747 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) 75848 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2) 75949 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 } 76050 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2" } 76151 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" } 76252 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" } 76353 #elif NR_CPUS <= RCU_FANOUT_4 76454 # define RCU_NUM_LVLS 4 76555 # define NUM_RCU_LVL_0 1 76656 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3) 76757 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2) 76858 # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1) 76959 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) 77060 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 } 77161 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" } 77262 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" } 77363 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" } 77464 #else 77565 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS" 77666 #endif 777</pre> 778 779<p>The maximum number of levels in the <tt>rcu_node</tt> structure 780is currently limited to four, as specified by lines 21-24 781and the structure of the subsequent “if” statement. 782For 32-bit systems, this allows 16*32*32*32=524,288 CPUs, which 783should be sufficient for the next few years at least. 784For 64-bit systems, 16*64*64*64=4,194,304 CPUs is allowed, which 785should see us through the next decade or so. 786This four-level tree also allows kernels built with 787<tt>CONFIG_RCU_FANOUT=8</tt> to support up to 4096 CPUs, 788which might be useful in very large systems having eight CPUs per 789socket (but please note that no one has yet shown any measurable 790performance degradation due to misaligned socket and <tt>rcu_node</tt> 791boundaries). 792In addition, building kernels with a full four levels of <tt>rcu_node</tt> 793tree permits better testing of RCU's combining-tree code. 794 795</p><p>The <tt>RCU_FANOUT</tt> symbol controls how many children 796are permitted at each non-leaf level of the <tt>rcu_node</tt> tree. 797If the <tt>CONFIG_RCU_FANOUT</tt> Kconfig option is not specified, 798it is set based on the word size of the system, which is also 799the Kconfig default. 800 801</p><p>The <tt>RCU_FANOUT_LEAF</tt> symbol controls how many CPUs are 802handled by each leaf <tt>rcu_node</tt> structure. 803Experience has shown that allowing a given leaf <tt>rcu_node</tt> 804structure to handle 64 CPUs, as permitted by the number of bits in 805the <tt>->qsmask</tt> field on a 64-bit system, results in 806excessive contention for the leaf <tt>rcu_node</tt> structures' 807<tt>->lock</tt> fields. 808The number of CPUs per leaf <tt>rcu_node</tt> structure is therefore 809limited to 16 given the default value of <tt>CONFIG_RCU_FANOUT_LEAF</tt>. 810If <tt>CONFIG_RCU_FANOUT_LEAF</tt> is unspecified, the value 811selected is based on the word size of the system, just as for 812<tt>CONFIG_RCU_FANOUT</tt>. 813Lines 11-19 perform this computation. 814 815</p><p>Lines 21-24 compute the maximum number of CPUs supported by 816a single-level (which contains a single <tt>rcu_node</tt> structure), 817two-level, three-level, and four-level <tt>rcu_node</tt> tree, 818respectively, given the fanout specified by <tt>RCU_FANOUT</tt> 819and <tt>RCU_FANOUT_LEAF</tt>. 820These numbers of CPUs are retained in the 821<tt>RCU_FANOUT_1</tt>, 822<tt>RCU_FANOUT_2</tt>, 823<tt>RCU_FANOUT_3</tt>, and 824<tt>RCU_FANOUT_4</tt> 825C-preprocessor variables, respectively. 826 827</p><p>These variables are used to control the C-preprocessor <tt>#if</tt> 828statement spanning lines 26-66 that computes the number of 829<tt>rcu_node</tt> structures required for each level of the tree, 830as well as the number of levels required. 831The number of levels is placed in the <tt>NUM_RCU_LVLS</tt> 832C-preprocessor variable by lines 27, 35, 44, and 54. 833The number of <tt>rcu_node</tt> structures for the topmost level 834of the tree is always exactly one, and this value is unconditionally 835placed into <tt>NUM_RCU_LVL_0</tt> by lines 28, 36, 45, and 55. 836The rest of the levels (if any) of the <tt>rcu_node</tt> tree 837are computed by dividing the maximum number of CPUs by the 838fanout supported by the number of levels from the current level down, 839rounding up. This computation is performed by lines 37, 84046-47, and 56-58. 841Lines 31-33, 40-42, 50-52, and 62-63 create initializers 842for lockdep lock-class names. 843Finally, lines 64-66 produce an error if the maximum number of 844CPUs is too large for the specified fanout. 845 846<h3><a name="The rcu_segcblist Structure"> 847The <tt>rcu_segcblist</tt> Structure</a></h3> 848 849The <tt>rcu_segcblist</tt> structure maintains a segmented list of 850callbacks as follows: 851 852<pre> 853 1 #define RCU_DONE_TAIL 0 854 2 #define RCU_WAIT_TAIL 1 855 3 #define RCU_NEXT_READY_TAIL 2 856 4 #define RCU_NEXT_TAIL 3 857 5 #define RCU_CBLIST_NSEGS 4 858 6 859 7 struct rcu_segcblist { 860 8 struct rcu_head *head; 861 9 struct rcu_head **tails[RCU_CBLIST_NSEGS]; 86210 unsigned long gp_seq[RCU_CBLIST_NSEGS]; 86311 long len; 86412 long len_lazy; 86513 }; 866</pre> 867 868<p> 869The segments are as follows: 870 871<ol> 872<li> <tt>RCU_DONE_TAIL</tt>: Callbacks whose grace periods have elapsed. 873 These callbacks are ready to be invoked. 874<li> <tt>RCU_WAIT_TAIL</tt>: Callbacks that are waiting for the 875 current grace period. 876 Note that different CPUs can have different ideas about which 877 grace period is current, hence the <tt>->gp_seq</tt> field. 878<li> <tt>RCU_NEXT_READY_TAIL</tt>: Callbacks waiting for the next 879 grace period to start. 880<li> <tt>RCU_NEXT_TAIL</tt>: Callbacks that have not yet been 881 associated with a grace period. 882</ol> 883 884<p> 885The <tt>->head</tt> pointer references the first callback or 886is <tt>NULL</tt> if the list contains no callbacks (which is 887<i>not</i> the same as being empty). 888Each element of the <tt>->tails[]</tt> array references the 889<tt>->next</tt> pointer of the last callback in the corresponding 890segment of the list, or the list's <tt>->head</tt> pointer if 891that segment and all previous segments are empty. 892If the corresponding segment is empty but some previous segment is 893not empty, then the array element is identical to its predecessor. 894Older callbacks are closer to the head of the list, and new callbacks 895are added at the tail. 896This relationship between the <tt>->head</tt> pointer, the 897<tt>->tails[]</tt> array, and the callbacks is shown in this 898diagram: 899 900</p><p><img src="nxtlist.svg" alt="nxtlist.svg" width="40%"> 901 902</p><p>In this figure, the <tt>->head</tt> pointer references the 903first 904RCU callback in the list. 905The <tt>->tails[RCU_DONE_TAIL]</tt> array element references 906the <tt>->head</tt> pointer itself, indicating that none 907of the callbacks is ready to invoke. 908The <tt>->tails[RCU_WAIT_TAIL]</tt> array element references callback 909CB 2's <tt>->next</tt> pointer, which indicates that 910CB 1 and CB 2 are both waiting on the current grace period, 911give or take possible disagreements about exactly which grace period 912is the current one. 913The <tt>->tails[RCU_NEXT_READY_TAIL]</tt> array element 914references the same RCU callback that <tt>->tails[RCU_WAIT_TAIL]</tt> 915does, which indicates that there are no callbacks waiting on the next 916RCU grace period. 917The <tt>->tails[RCU_NEXT_TAIL]</tt> array element references 918CB 4's <tt>->next</tt> pointer, indicating that all the 919remaining RCU callbacks have not yet been assigned to an RCU grace 920period. 921Note that the <tt>->tails[RCU_NEXT_TAIL]</tt> array element 922always references the last RCU callback's <tt>->next</tt> pointer 923unless the callback list is empty, in which case it references 924the <tt>->head</tt> pointer. 925 926<p> 927There is one additional important special case for the 928<tt>->tails[RCU_NEXT_TAIL]</tt> array element: It can be <tt>NULL</tt> 929when this list is <i>disabled</i>. 930Lists are disabled when the corresponding CPU is offline or when 931the corresponding CPU's callbacks are offloaded to a kthread, 932both of which are described elsewhere. 933 934</p><p>CPUs advance their callbacks from the 935<tt>RCU_NEXT_TAIL</tt> to the <tt>RCU_NEXT_READY_TAIL</tt> to the 936<tt>RCU_WAIT_TAIL</tt> to the <tt>RCU_DONE_TAIL</tt> list segments 937as grace periods advance. 938 939</p><p>The <tt>->gp_seq[]</tt> array records grace-period 940numbers corresponding to the list segments. 941This is what allows different CPUs to have different ideas as to 942which is the current grace period while still avoiding premature 943invocation of their callbacks. 944In particular, this allows CPUs that go idle for extended periods 945to determine which of their callbacks are ready to be invoked after 946reawakening. 947 948</p><p>The <tt>->len</tt> counter contains the number of 949callbacks in <tt>->head</tt>, and the 950<tt>->len_lazy</tt> contains the number of those callbacks that 951are known to only free memory, and whose invocation can therefore 952be safely deferred. 953 954<p><b>Important note</b>: It is the <tt>->len</tt> field that 955determines whether or not there are callbacks associated with 956this <tt>rcu_segcblist</tt> structure, <i>not</i> the <tt>->head</tt> 957pointer. 958The reason for this is that all the ready-to-invoke callbacks 959(that is, those in the <tt>RCU_DONE_TAIL</tt> segment) are extracted 960all at once at callback-invocation time. 961If callback invocation must be postponed, for example, because a 962high-priority process just woke up on this CPU, then the remaining 963callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment. 964Either way, the <tt>->len</tt> and <tt>->len_lazy</tt> counts 965are adjusted after the corresponding callbacks have been invoked, and so 966again it is the <tt>->len</tt> count that accurately reflects whether 967or not there are callbacks associated with this <tt>rcu_segcblist</tt> 968structure. 969Of course, off-CPU sampling of the <tt>->len</tt> count requires 970the use of appropriate synchronization, for example, memory barriers. 971This synchronization can be a bit subtle, particularly in the case 972of <tt>rcu_barrier()</tt>. 973 974<h3><a name="The rcu_data Structure"> 975The <tt>rcu_data</tt> Structure</a></h3> 976 977<p>The <tt>rcu_data</tt> maintains the per-CPU state for the 978corresponding flavor of RCU. 979The fields in this structure may be accessed only from the corresponding 980CPU (and from tracing) unless otherwise stated. 981This structure is the 982focus of quiescent-state detection and RCU callback queuing. 983It also tracks its relationship to the corresponding leaf 984<tt>rcu_node</tt> structure to allow more-efficient 985propagation of quiescent states up the <tt>rcu_node</tt> 986combining tree. 987Like the <tt>rcu_node</tt> structure, it provides a local 988copy of the grace-period information to allow for-free 989synchronized 990access to this information from the corresponding CPU. 991Finally, this structure records past dyntick-idle state 992for the corresponding CPU and also tracks statistics. 993 994</p><p>The <tt>rcu_data</tt> structure's fields are discussed, 995singly and in groups, in the following sections. 996 997<h5>Connection to Other Data Structures</h5> 998 999<p>This portion of the <tt>rcu_data</tt> structure is declared 1000as follows: 1001 1002<pre> 1003 1 int cpu; 1004 2 struct rcu_state *rsp; 1005 3 struct rcu_node *mynode; 1006 4 struct rcu_dynticks *dynticks; 1007 5 unsigned long grpmask; 1008 6 bool beenonline; 1009</pre> 1010 1011<p>The <tt>->cpu</tt> field contains the number of the 1012corresponding CPU, the <tt>->rsp</tt> pointer references 1013the corresponding <tt>rcu_state</tt> structure (and is most frequently 1014used to locate the name of the corresponding flavor of RCU for tracing), 1015and the <tt>->mynode</tt> field references the corresponding 1016<tt>rcu_node</tt> structure. 1017The <tt>->mynode</tt> is used to propagate quiescent states 1018up the combining tree. 1019<p>The <tt>->dynticks</tt> pointer references the 1020<tt>rcu_dynticks</tt> structure corresponding to this 1021CPU. 1022Recall that a single per-CPU instance of the <tt>rcu_dynticks</tt> 1023structure is shared among all flavors of RCU. 1024These first four fields are constant and therefore require not 1025synchronization. 1026 1027</p><p>The <tt>->grpmask</tt> field indicates the bit in 1028the <tt>->mynode->qsmask</tt> corresponding to this 1029<tt>rcu_data</tt> structure, and is also used when propagating 1030quiescent states. 1031The <tt>->beenonline</tt> flag is set whenever the corresponding 1032CPU comes online, which means that the debugfs tracing need not dump 1033out any <tt>rcu_data</tt> structure for which this flag is not set. 1034 1035<h5>Quiescent-State and Grace-Period Tracking</h5> 1036 1037<p>This portion of the <tt>rcu_data</tt> structure is declared 1038as follows: 1039 1040<pre> 1041 1 unsigned long completed; 1042 2 unsigned long gpnum; 1043 3 bool cpu_no_qs; 1044 4 bool core_needs_qs; 1045 5 bool gpwrap; 1046 6 unsigned long rcu_qs_ctr_snap; 1047</pre> 1048 1049<p>The <tt>completed</tt> and <tt>gpnum</tt> 1050fields are the counterparts of the fields of the same name 1051in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures. 1052They may each lag up to one behind their <tt>rcu_node</tt> 1053counterparts, but in <tt>CONFIG_NO_HZ_IDLE</tt> and 1054<tt>CONFIG_NO_HZ_FULL</tt> kernels can lag 1055arbitrarily far behind for CPUs in dyntick-idle mode (but these counters 1056will catch up upon exit from dyntick-idle mode). 1057If a given <tt>rcu_data</tt> structure's <tt>->gpnum</tt> and 1058<tt>->complete</tt> fields are equal, then this <tt>rcu_data</tt> 1059structure believes that RCU is idle. 1060Otherwise, as with the <tt>rcu_state</tt> and <tt>rcu_node</tt> 1061structure, 1062the <tt>->gpnum</tt> field will be one greater than the 1063<tt>->complete</tt> fields, with <tt>->gpnum</tt> 1064indicating which grace period this <tt>rcu_data</tt> believes 1065is still being waited for. 1066 1067<table> 1068<tr><th> </th></tr> 1069<tr><th align="left">Quick Quiz:</th></tr> 1070<tr><td> 1071 All this replication of the grace period numbers can only cause 1072 massive confusion. 1073 Why not just keep a global pair of counters and be done with it??? 1074</td></tr> 1075<tr><th align="left">Answer:</th></tr> 1076<tr><td bgcolor="#ffffff"><font color="ffffff"> 1077 Because if there was only a single global pair of grace-period 1078 numbers, there would need to be a single global lock to allow 1079 safely accessing and updating them. 1080 And if we are not going to have a single global lock, we need 1081 to carefully manage the numbers on a per-node basis. 1082 Recall from the answer to a previous Quick Quiz that the consequences 1083 of applying a previously sampled quiescent state to the wrong 1084 grace period are quite severe. 1085</font></td></tr> 1086<tr><td> </td></tr> 1087</table> 1088 1089<p>The <tt>->cpu_no_qs</tt> flag indicates that the 1090CPU has not yet passed through a quiescent state, 1091while the <tt>->core_needs_qs</tt> flag indicates that the 1092RCU core needs a quiescent state from the corresponding CPU. 1093The <tt>->gpwrap</tt> field indicates that the corresponding 1094CPU has remained idle for so long that the <tt>completed</tt> 1095and <tt>gpnum</tt> counters are in danger of overflow, which 1096will cause the CPU to disregard the values of its counters on 1097its next exit from idle. 1098Finally, the <tt>rcu_qs_ctr_snap</tt> field is used to detect 1099cases where a given operation has resulted in a quiescent state 1100for all flavors of RCU, for example, <tt>cond_resched_rcu_qs()</tt>. 1101 1102<h5>RCU Callback Handling</h5> 1103 1104<p>In the absence of CPU-hotplug events, RCU callbacks are invoked by 1105the same CPU that registered them. 1106This is strictly a cache-locality optimization: callbacks can and 1107do get invoked on CPUs other than the one that registered them. 1108After all, if the CPU that registered a given callback has gone 1109offline before the callback can be invoked, there really is no other 1110choice. 1111 1112</p><p>This portion of the <tt>rcu_data</tt> structure is declared 1113as follows: 1114 1115<pre> 1116 1 struct rcu_segcblist cblist; 1117 2 long qlen_last_fqs_check; 1118 3 unsigned long n_cbs_invoked; 1119 4 unsigned long n_nocbs_invoked; 1120 5 unsigned long n_cbs_orphaned; 1121 6 unsigned long n_cbs_adopted; 1122 7 unsigned long n_force_qs_snap; 1123 8 long blimit; 1124</pre> 1125 1126<p>The <tt>->cblist</tt> structure is the segmented callback list 1127described earlier. 1128The CPU advances the callbacks in its <tt>rcu_data</tt> structure 1129whenever it notices that another RCU grace period has completed. 1130The CPU detects the completion of an RCU grace period by noticing 1131that the value of its <tt>rcu_data</tt> structure's 1132<tt>->completed</tt> field differs from that of its leaf 1133<tt>rcu_node</tt> structure. 1134Recall that each <tt>rcu_node</tt> structure's 1135<tt>->completed</tt> field is updated at the end of each 1136grace period. 1137 1138<p> 1139The <tt>->qlen_last_fqs_check</tt> and 1140<tt>->n_force_qs_snap</tt> coordinate the forcing of quiescent 1141states from <tt>call_rcu()</tt> and friends when callback 1142lists grow excessively long. 1143 1144</p><p>The <tt>->n_cbs_invoked</tt>, 1145<tt>->n_cbs_orphaned</tt>, and <tt>->n_cbs_adopted</tt> 1146fields count the number of callbacks invoked, 1147sent to other CPUs when this CPU goes offline, 1148and received from other CPUs when those other CPUs go offline. 1149The <tt>->n_nocbs_invoked</tt> is used when the CPU's callbacks 1150are offloaded to a kthread. 1151 1152<p> 1153Finally, the <tt>->blimit</tt> counter is the maximum number of 1154RCU callbacks that may be invoked at a given time. 1155 1156<h5>Dyntick-Idle Handling</h5> 1157 1158<p>This portion of the <tt>rcu_data</tt> structure is declared 1159as follows: 1160 1161<pre> 1162 1 int dynticks_snap; 1163 2 unsigned long dynticks_fqs; 1164</pre> 1165 1166The <tt>->dynticks_snap</tt> field is used to take a snapshot 1167of the corresponding CPU's dyntick-idle state when forcing 1168quiescent states, and is therefore accessed from other CPUs. 1169Finally, the <tt>->dynticks_fqs</tt> field is used to 1170count the number of times this CPU is determined to be in 1171dyntick-idle state, and is used for tracing and debugging purposes. 1172 1173<h3><a name="The rcu_dynticks Structure"> 1174The <tt>rcu_dynticks</tt> Structure</a></h3> 1175 1176<p>The <tt>rcu_dynticks</tt> maintains the per-CPU dyntick-idle state 1177for the corresponding CPU. 1178Unlike the other structures, <tt>rcu_dynticks</tt> is not 1179replicated over the different flavors of RCU. 1180The fields in this structure may be accessed only from the corresponding 1181CPU (and from tracing) unless otherwise stated. 1182Its fields are as follows: 1183 1184<pre> 1185 1 int dynticks_nesting; 1186 2 int dynticks_nmi_nesting; 1187 3 atomic_t dynticks; 1188 4 bool rcu_need_heavy_qs; 1189 5 unsigned long rcu_qs_ctr; 1190 6 bool rcu_urgent_qs; 1191</pre> 1192 1193<p>The <tt>->dynticks_nesting</tt> field counts the 1194nesting depth of normal interrupts. 1195In addition, this counter is incremented when exiting dyntick-idle 1196mode and decremented when entering it. 1197This counter can therefore be thought of as counting the number 1198of reasons why this CPU cannot be permitted to enter dyntick-idle 1199mode, aside from non-maskable interrupts (NMIs). 1200NMIs are counted by the <tt>->dynticks_nmi_nesting</tt> 1201field, except that NMIs that interrupt non-dyntick-idle execution 1202are not counted. 1203 1204</p><p>The <tt>->dynticks</tt> field counts the corresponding 1205CPU's transitions to and from dyntick-idle mode, so that this counter 1206has an even value when the CPU is in dyntick-idle mode and an odd 1207value otherwise. 1208 1209</p><p>The <tt>->rcu_need_heavy_qs</tt> field is used 1210to record the fact that the RCU core code would really like to 1211see a quiescent state from the corresponding CPU, so much so that 1212it is willing to call for heavy-weight dyntick-counter operations. 1213This flag is checked by RCU's context-switch and <tt>cond_resched()</tt> 1214code, which provide a momentary idle sojourn in response. 1215 1216</p><p>The <tt>->rcu_qs_ctr</tt> field is used to record 1217quiescent states from <tt>cond_resched()</tt>. 1218Because <tt>cond_resched()</tt> can execute quite frequently, this 1219must be quite lightweight, as in a non-atomic increment of this 1220per-CPU field. 1221 1222</p><p>Finally, the <tt>->rcu_urgent_qs</tt> field is used to record 1223the fact that the RCU core code would really like to see a quiescent 1224state from the corresponding CPU, with the various other fields indicating 1225just how badly RCU wants this quiescent state. 1226This flag is checked by RCU's context-switch and <tt>cond_resched()</tt> 1227code, which, if nothing else, non-atomically increment <tt>->rcu_qs_ctr</tt> 1228in response. 1229 1230<table> 1231<tr><th> </th></tr> 1232<tr><th align="left">Quick Quiz:</th></tr> 1233<tr><td> 1234 Why not just count all NMIs? 1235 Wouldn't that be simpler and less error prone? 1236</td></tr> 1237<tr><th align="left">Answer:</th></tr> 1238<tr><td bgcolor="#ffffff"><font color="ffffff"> 1239 It seems simpler only until you think hard about how to go about 1240 updating the <tt>rcu_dynticks</tt> structure's 1241 <tt>->dynticks</tt> field. 1242</font></td></tr> 1243<tr><td> </td></tr> 1244</table> 1245 1246<p>Additional fields are present for some special-purpose 1247builds, and are discussed separately. 1248 1249<h3><a name="The rcu_head Structure"> 1250The <tt>rcu_head</tt> Structure</a></h3> 1251 1252<p>Each <tt>rcu_head</tt> structure represents an RCU callback. 1253These structures are normally embedded within RCU-protected data 1254structures whose algorithms use asynchronous grace periods. 1255In contrast, when using algorithms that block waiting for RCU grace periods, 1256RCU users need not provide <tt>rcu_head</tt> structures. 1257 1258</p><p>The <tt>rcu_head</tt> structure has fields as follows: 1259 1260<pre> 1261 1 struct rcu_head *next; 1262 2 void (*func)(struct rcu_head *head); 1263</pre> 1264 1265<p>The <tt>->next</tt> field is used 1266to link the <tt>rcu_head</tt> structures together in the 1267lists within the <tt>rcu_data</tt> structures. 1268The <tt>->func</tt> field is a pointer to the function 1269to be called when the callback is ready to be invoked, and 1270this function is passed a pointer to the <tt>rcu_head</tt> 1271structure. 1272However, <tt>kfree_rcu()</tt> uses the <tt>->func</tt> 1273field to record the offset of the <tt>rcu_head</tt> 1274structure within the enclosing RCU-protected data structure. 1275 1276</p><p>Both of these fields are used internally by RCU. 1277From the viewpoint of RCU users, this structure is an 1278opaque “cookie”. 1279 1280<table> 1281<tr><th> </th></tr> 1282<tr><th align="left">Quick Quiz:</th></tr> 1283<tr><td> 1284 Given that the callback function <tt>->func</tt> 1285 is passed a pointer to the <tt>rcu_head</tt> structure, 1286 how is that function supposed to find the beginning of the 1287 enclosing RCU-protected data structure? 1288</td></tr> 1289<tr><th align="left">Answer:</th></tr> 1290<tr><td bgcolor="#ffffff"><font color="ffffff"> 1291 In actual practice, there is a separate callback function per 1292 type of RCU-protected data structure. 1293 The callback function can therefore use the <tt>container_of()</tt> 1294 macro in the Linux kernel (or other pointer-manipulation facilities 1295 in other software environments) to find the beginning of the 1296 enclosing structure. 1297</font></td></tr> 1298<tr><td> </td></tr> 1299</table> 1300 1301<h3><a name="RCU-Specific Fields in the task_struct Structure"> 1302RCU-Specific Fields in the <tt>task_struct</tt> Structure</a></h3> 1303 1304<p>The <tt>CONFIG_PREEMPT_RCU</tt> implementation uses some 1305additional fields in the <tt>task_struct</tt> structure: 1306 1307<pre> 1308 1 #ifdef CONFIG_PREEMPT_RCU 1309 2 int rcu_read_lock_nesting; 1310 3 union rcu_special rcu_read_unlock_special; 1311 4 struct list_head rcu_node_entry; 1312 5 struct rcu_node *rcu_blocked_node; 1313 6 #endif /* #ifdef CONFIG_PREEMPT_RCU */ 1314 7 #ifdef CONFIG_TASKS_RCU 1315 8 unsigned long rcu_tasks_nvcsw; 1316 9 bool rcu_tasks_holdout; 131710 struct list_head rcu_tasks_holdout_list; 131811 int rcu_tasks_idle_cpu; 131912 #endif /* #ifdef CONFIG_TASKS_RCU */ 1320</pre> 1321 1322<p>The <tt>->rcu_read_lock_nesting</tt> field records the 1323nesting level for RCU read-side critical sections, and 1324the <tt>->rcu_read_unlock_special</tt> field is a bitmask 1325that records special conditions that require <tt>rcu_read_unlock()</tt> 1326to do additional work. 1327The <tt>->rcu_node_entry</tt> field is used to form lists of 1328tasks that have blocked within preemptible-RCU read-side critical 1329sections and the <tt>->rcu_blocked_node</tt> field references 1330the <tt>rcu_node</tt> structure whose list this task is a member of, 1331or <tt>NULL</tt> if it is not blocked within a preemptible-RCU 1332read-side critical section. 1333 1334<p>The <tt>->rcu_tasks_nvcsw</tt> field tracks the number of 1335voluntary context switches that this task had undergone at the 1336beginning of the current tasks-RCU grace period, 1337<tt>->rcu_tasks_holdout</tt> is set if the current tasks-RCU 1338grace period is waiting on this task, <tt>->rcu_tasks_holdout_list</tt> 1339is a list element enqueuing this task on the holdout list, 1340and <tt>->rcu_tasks_idle_cpu</tt> tracks which CPU this 1341idle task is running, but only if the task is currently running, 1342that is, if the CPU is currently idle. 1343 1344<h3><a name="Accessor Functions"> 1345Accessor Functions</a></h3> 1346 1347<p>The following listing shows the 1348<tt>rcu_get_root()</tt>, <tt>rcu_for_each_node_breadth_first</tt>, 1349<tt>rcu_for_each_nonleaf_node_breadth_first()</tt>, and 1350<tt>rcu_for_each_leaf_node()</tt> function and macros: 1351 1352<pre> 1353 1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp) 1354 2 { 1355 3 return &rsp->node[0]; 1356 4 } 1357 5 1358 6 #define rcu_for_each_node_breadth_first(rsp, rnp) \ 1359 7 for ((rnp) = &(rsp)->node[0]; \ 1360 8 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++) 1361 9 1362 10 #define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \ 1363 11 for ((rnp) = &(rsp)->node[0]; \ 1364 12 (rnp) < (rsp)->level[NUM_RCU_LVLS - 1]; (rnp)++) 1365 13 1366 14 #define rcu_for_each_leaf_node(rsp, rnp) \ 1367 15 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \ 1368 16 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++) 1369</pre> 1370 1371<p>The <tt>rcu_get_root()</tt> simply returns a pointer to the 1372first element of the specified <tt>rcu_state</tt> structure's 1373<tt>->node[]</tt> array, which is the root <tt>rcu_node</tt> 1374structure. 1375 1376</p><p>As noted earlier, the <tt>rcu_for_each_node_breadth_first()</tt> 1377macro takes advantage of the layout of the <tt>rcu_node</tt> 1378structures in the <tt>rcu_state</tt> structure's 1379<tt>->node[]</tt> array, performing a breadth-first traversal by 1380simply traversing the array in order. 1381The <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> macro operates 1382similarly, but traverses only the first part of the array, thus excluding 1383the leaf <tt>rcu_node</tt> structures. 1384Finally, the <tt>rcu_for_each_leaf_node()</tt> macro traverses only 1385the last part of the array, thus traversing only the leaf 1386<tt>rcu_node</tt> structures. 1387 1388<table> 1389<tr><th> </th></tr> 1390<tr><th align="left">Quick Quiz:</th></tr> 1391<tr><td> 1392 What do <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> and 1393 <tt>rcu_for_each_leaf_node()</tt> do if the <tt>rcu_node</tt> tree 1394 contains only a single node? 1395</td></tr> 1396<tr><th align="left">Answer:</th></tr> 1397<tr><td bgcolor="#ffffff"><font color="ffffff"> 1398 In the single-node case, 1399 <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> is a no-op 1400 and <tt>rcu_for_each_leaf_node()</tt> traverses the single node. 1401</font></td></tr> 1402<tr><td> </td></tr> 1403</table> 1404 1405<h3><a name="Summary"> 1406Summary</a></h3> 1407 1408So each flavor of RCU is represented by an <tt>rcu_state</tt> structure, 1409which contains a combining tree of <tt>rcu_node</tt> and 1410<tt>rcu_data</tt> structures. 1411Finally, in <tt>CONFIG_NO_HZ_IDLE</tt> kernels, each CPU's dyntick-idle 1412state is tracked by an <tt>rcu_dynticks</tt> structure. 1413 1414If you made it this far, you are well prepared to read the code 1415walkthroughs in the other articles in this series. 1416 1417<h3><a name="Acknowledgments"> 1418Acknowledgments</a></h3> 1419 1420I owe thanks to Cyrill Gorcunov, Mathieu Desnoyers, Dhaval Giani, Paul 1421Turner, Abhishek Srivastava, Matt Kowalczyk, and Serge Hallyn 1422for helping me get this document into a more human-readable state. 1423 1424<h3><a name="Legal Statement"> 1425Legal Statement</a></h3> 1426 1427<p>This work represents the view of the author and does not necessarily 1428represent the view of IBM. 1429 1430</p><p>Linux is a registered trademark of Linus Torvalds. 1431 1432</p><p>Other company, product, and service names may be trademarks or 1433service marks of others. 1434 1435</body></html> 1436
