Documentation/RCU/Design/Data-Structures/Data-Structures.html

   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.&nbsp;McKenney</p>
   9
  10 <h3>Introduction</h3>
  11
  12 This document describes RCU's major data structures and their relationship
  13 to 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
  39 data structures maintain the state in such a way as to allow RCU readers
  40 to execute extremely quickly, while also processing the RCU grace periods
  41 requested by updaters in an efficient and extremely scalable fashion.
  42 The efficiency and scalability of RCU updaters is provided primarily
  43 by 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
  48 containing a tree of <tt>rcu_node</tt> structures.
  49 Each 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
  51 are <tt>NR_CPUS</tt> number of <tt>rcu_data</tt> structures,
  52 one for each possible CPU.
  53 This structure is adjusted at boot time, if needed, to handle the
  54 common case where <tt>nr_cpu_ids</tt> is much less than
  55 <tt>NR_CPUs</tt>.
  56 For example, a number of Linux distributions set <tt>NR_CPUs=4096</tt>,
  57 which results in a three-level <tt>rcu_node</tt> tree.
  58 If the actual hardware has only 16 CPUs, RCU will adjust itself
  59 at 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
  62 such as quiescent states, dyntick-idle transitions,
  63 and CPU hotplug operations to be processed efficiently
  64 and scalably.
  65 Quiescent states are recorded by the per-CPU <tt>rcu_data</tt> structures,
  66 and other events are recorded by the leaf-level <tt>rcu_node</tt>
  67 structures.
  68 All of these events are combined at each level of the tree until finally
  69 grace periods are completed at the tree's root <tt>rcu_node</tt>
  70 structure.
  71 A grace period can be completed at the root once every CPU
  72 (or, in the case of <tt>CONFIG_PREEMPT_RCU</tt>, task)
  73 has passed through a quiescent state.
  74 Once a grace period has completed, record of that fact is propagated
  75 back down the tree.
  76
  77 </p><p>As can be seen from the diagram, on a 64-bit system
  78 a two-level tree with 64 leaves can accommodate 1,024 CPUs, with a fanout
  79 of 64 at the root and a fanout of 16 at the leaves.
  80
  81 <table>
  82 <tr><th>&nbsp;</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>-&gt;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>&nbsp;</td></tr>
 117 </table>
 118
 119 <p>If your system has more than 1,024 CPUs (or more than 512 CPUs on
 120 a 32-bit system), then RCU will automatically add more levels to the
 121 tree.
 122 For example, if you are crazy enough to build a 64-bit system with 65,536
 123 CPUs, 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
 128 accommodates up to 4,194,304 CPUs, though only a mere 524,288 CPUs for
 129 32-bit systems.
 130 On the other hand, you can set <tt>CONFIG_RCU_FANOUT</tt> to be
 131 as small as 2 if you wish, which would permit only 16 CPUs, which
 132 is useful for testing.
 133
 134 </p><p>This multi-level combining tree allows us to get most of the
 135 performance and scalability
 136 benefits of partitioning, even though RCU grace-period detection is
 137 inherently a global operation.
 138 The trick here is that only the last CPU to report a quiescent state
 139 into a given <tt>rcu_node</tt> structure need advance to the <tt>rcu_node</tt>
 140 structure at the next level up the tree.
 141 This means that at the leaf-level <tt>rcu_node</tt> structure, only
 142 one access out of sixteen will progress up the tree.
 143 For the internal <tt>rcu_node</tt> structures, the situation is even
 144 more extreme:  Only one access out of sixty-four will progress up
 145 the tree.
 146 Because the vast majority of the CPUs do not progress up the tree,
 147 the lock contention remains roughly constant up the tree.
 148 No matter how many CPUs there are in the system, at most 64 quiescent-state
 149 reports per grace period will progress all the way to the root
 150 <tt>rcu_node</tt> structure, thus ensuring that the lock contention
 151 on 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,
 154 keeping lock contention under control at all tree levels regardless
 155 of the level of loading on the system.
 156
 157 </p><p>The Linux kernel actually supports multiple flavors of RCU
 158 running concurrently, so RCU builds separate data structures for each
 159 flavor.
 160 For example, for <tt>CONFIG_TREE_RCU=y</tt> kernels, RCU provides
 161 rcu_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
 166 reason the Linux kernel provides <tt>CONFIG_NO_HZ_IDLE</tt>, which
 167 turns off the scheduling-clock interrupts on idle CPUs, which in
 168 turn allows those CPUs to attain deeper sleep states and to consume
 169 less energy.
 170 CPUs whose scheduling-clock interrupts have been turned off are
 171 said to be in <i>dyntick-idle mode</i>.
 172 RCU must handle dyntick-idle CPUs specially
 173 because RCU would otherwise wake up each CPU on every grace period,
 174 which would defeat the whole purpose of <tt>CONFIG_NO_HZ_IDLE</tt>.
 175 RCU uses the <tt>rcu_dynticks</tt> structure to track
 176 which 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
 181 for all flavors of RCU.
 182 Therefore, a single <tt>rcu_dynticks</tt> structure is allocated per
 183 CPU, and all of a given CPU's <tt>rcu_data</tt> structures share
 184 that <tt>rcu_dynticks</tt>, as shown in the figure.
 185
 186 </p><p>Kernels built with <tt>CONFIG_PREEMPT_RCU</tt> support
 187 rcu_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
 192 RCU callbacks, either directly via <tt>call_rcu()</tt> and
 193 friends (namely <tt>call_rcu_bh()</tt> and <tt>call_rcu_sched()</tt>),
 194 there being a separate interface per flavor of RCU)
 195 or indirectly via <tt>synchronize_rcu()</tt> and friends.
 196 RCU callbacks are represented by <tt>rcu_head</tt> structures,
 197 which are queued on <tt>rcu_data</tt> structures while they are
 198 waiting 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.
 204 Lesser data structures will be introduced with the algorithms that
 205 make use of them.
 206
 207 </p><p>Note that each of the data structures in the above figure has
 208 its 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
 223 very different ideas about the state of RCU at any given time.
 224 For but one example, awareness of the start or end of a given RCU
 225 grace period propagates slowly through the data structures.
 226 This slow propagation is absolutely necessary for RCU to have good
 227 read-side performance.
 228 If this balkanized implementation seems foreign to you, one useful
 229 trick is to consider each instance of these data structures to be
 230 a different person, each having the usual slightly different
 231 view of reality.
 232
 233 </p><p>The general role of each of these data structures is as
 234 follows:
 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
 288 RCU's data structures are related, you are done.
 289 Otherwise, each of the following sections give more details on
 290 the <tt>rcu_state</tt>, <tt>rcu_node</tt>, <tt>rcu_data</tt>,
 291 and <tt>rcu_dynticks</tt> data structures.
 292
 293 <h3><a name="The rcu_state Structure">
 294 The <tt>rcu_state</tt> Structure</a></h3>
 295
 296 <p>The <tt>rcu_state</tt> structure is the base structure that
 297 represents a flavor of RCU.
 298 This structure forms the interconnection between the
 299 <tt>rcu_node</tt> and <tt>rcu_data</tt> structures,
 300 tracks grace periods, contains the lock used to
 301 synchronize with CPU-hotplug events,
 302 and maintains state used to force quiescent states when
 303 grace periods extend too long,
 304
 305 </p><p>A few of the <tt>rcu_state</tt> structure's fields are discussed,
 306 singly and in groups, in the following sections.
 307 The more specialized fields are covered in the discussion of their
 308 use.
 309
 310 <h5>Relationship to rcu_node and rcu_data Structures</h5>
 311
 312 This portion of the <tt>rcu_state</tt> structure is declared
 313 as 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>&nbsp;</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>&nbsp;</td></tr>
 342 </table>
 343
 344 <p>The <tt>rcu_node</tt> tree is embedded into the
 345 <tt>-&gt;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
 350 breadth-first traversal of the tree is implemented as a simple
 351 linear scan of the array, which is in fact what the
 352 <tt>rcu_for_each_node_breadth_first()</tt> macro does.
 353 This macro is used at the beginning and ends of grace periods.
 354
 355 </p><p>Each entry of the <tt>-&gt;level</tt> array references
 356 the first <tt>rcu_node</tt> structure on the corresponding level
 357 of 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
 363 first child of the root <tt>rcu_node</tt>, and finally the second
 364 element 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
 367 rather 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>-&gt;rda</tt> field references a per-CPU
 372 pointer to the corresponding CPU's <tt>rcu_data</tt> structure.
 373
 374 </p><p>All of these fields are constant once initialization is complete,
 375 and 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
 380 as 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
 388 the <tt>-&gt;gpnum</tt> field contains the number of the grace
 389 period that started most recently.
 390 The <tt>-&gt;completed</tt> field contains the number of the
 391 grace period that completed most recently.
 392 If the two fields are equal, the RCU grace period that most recently
 393 started has already completed, and therefore the corresponding
 394 flavor of RCU is idle.
 395 If <tt>-&gt;gpnum</tt> is one greater than <tt>-&gt;completed</tt>,
 396 then <tt>-&gt;gpnum</tt> gives the number of the current RCU
 397 grace period, which has not yet completed.
 398 Any other combination of values indicates that something is broken.
 399 These two fields are protected by the root <tt>rcu_node</tt>'s
 400 <tt>-&gt;lock</tt> field.
 401
 402 </p><p>There are <tt>-&gt;gpnum</tt> and <tt>-&gt;completed</tt> fields
 403 in the <tt>rcu_node</tt> and <tt>rcu_data</tt> structures
 404 as well.
 405 The fields in the <tt>rcu_state</tt> structure represent the
 406 most current values, and those of the other structures are compared
 407 in order to detect the start of a new grace period in a distributed
 408 fashion.
 409 The 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
 415 as 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>-&gt;gp_max</tt> field tracks the duration of the longest
 424 grace period in jiffies.
 425 It is protected by the root <tt>rcu_node</tt>'s <tt>-&gt;lock</tt>.
 426
 427 <p>The <tt>-&gt;name</tt> field points to the name of the RCU flavor
 428 (for example, &ldquo;rcu_sched&rdquo;), and is constant.
 429 The <tt>-&gt;abbr</tt> field contains a one-character abbreviation,
 430 for example, &ldquo;s&rdquo; for RCU-sched.
 431
 432 <h3><a name="The rcu_node Structure">
 433 The <tt>rcu_node</tt> Structure</a></h3>
 434
 435 <p>The <tt>rcu_node</tt> structures form the combining
 436 tree that propagates quiescent-state
 437 information from the leaves to the root and also that propagates
 438 grace-period information from the root down to the leaves.
 439 They provides local copies of the grace-period state in order
 440 to allow this information to be accessed in a synchronized
 441 manner without suffering the scalability limitations that
 442 would otherwise be imposed by global locking.
 443 In <tt>CONFIG_PREEMPT_RCU</tt> kernels, they manage the lists
 444 of tasks that have blocked while in their current
 445 RCU read-side critical section.
 446 In <tt>CONFIG_PREEMPT_RCU</tt> with
 447 <tt>CONFIG_RCU_BOOST</tt>, they manage the
 448 per-<tt>rcu_node</tt> priority-boosting
 449 kernel threads (kthreads) and state.
 450 Finally, they record CPU-hotplug state in order to determine
 451 which CPUs should be ignored during a given grace period.
 452
 453 </p><p>The <tt>rcu_node</tt> structure's fields are discussed,
 454 singly 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
 459 as 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>-&gt;parent</tt> pointer references the <tt>rcu_node</tt>
 471 one level up in the tree, and is <tt>NULL</tt> for the root
 472 <tt>rcu_node</tt>.
 473 The RCU implementation makes heavy use of this field to push quiescent
 474 states up the tree.
 475 The <tt>-&gt;level</tt> field gives the level in the tree, with
 476 the root being at level zero, its children at level one, and so on.
 477 The <tt>-&gt;grpnum</tt> field gives this node's position within
 478 the children of its parent, so this number can range between 0 and 31
 479 on 32-bit systems and between 0 and 63 on 64-bit systems.
 480 The <tt>-&gt;level</tt> and <tt>-&gt;grpnum</tt> fields are
 481 used only during initialization and for tracing.
 482 The <tt>-&gt;grpmask</tt> field is the bitmask counterpart of
 483 <tt>-&gt;grpnum</tt>, and therefore always has exactly one bit set.
 484 This mask is used to clear the bit corresponding to this <tt>rcu_node</tt>
 485 structure in its parent's bitmasks, which are described later.
 486 Finally, the <tt>-&gt;grplo</tt> and <tt>-&gt;grphi</tt> fields
 487 contain 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
 491 synchronization.
 492
 493 <h5>Synchronization</h5>
 494
 495 <p>This field of the <tt>rcu_node</tt> structure is declared
 496 as 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,
 503 unless otherwise stated.
 504 That said, all of the fields in this structure can be accessed without
 505 locking for tracing purposes.
 506 Yes, this can result in confusing traces, but better some tracing confusion
 507 than 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
 512 as 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
 520 the <tt>rcu_state</tt> structure.
 521 They each may lag up to one behind their <tt>rcu_state</tt>
 522 counterparts.
 523 If a given <tt>rcu_node</tt> structure's <tt>-&gt;gpnum</tt> and
 524 <tt>-&gt;complete</tt> fields are equal, then this <tt>rcu_node</tt>
 525 structure believes that RCU is idle.
 526 Otherwise, as with the <tt>rcu_state</tt> structure,
 527 the <tt>-&gt;gpnum</tt> field will be one greater than the
 528 <tt>-&gt;complete</tt> fields, with <tt>-&gt;gpnum</tt>
 529 indicating which grace period this <tt>rcu_node</tt> believes
 530 is still being waited for.
 531
 532 </p><p>The <tt>&gt;gpnum</tt> field of each <tt>rcu_node</tt>
 533 structure is updated at the beginning
 534 of each grace period, and the <tt>-&gt;completed</tt> fields are
 535 updated 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
 540 combining tree.
 541
 542 </p><p>This portion of the <tt>rcu_node</tt> structure has fields
 543 as 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>-&gt;qsmask</tt> field tracks which of this
 553 <tt>rcu_node</tt> structure's children still need to report
 554 quiescent states for the current normal grace period.
 555 Such children will have a value of 1 in their corresponding bit.
 556 Note that the leaf <tt>rcu_node</tt> structures should be
 557 thought of as having <tt>rcu_data</tt> structures as their
 558 children.
 559 Similarly, the <tt>-&gt;expmask</tt> field tracks which
 560 of this <tt>rcu_node</tt> structure's children still need to report
 561 quiescent states for the current expedited grace period.
 562 An expedited grace period has
 563 the same conceptual properties as a normal grace period, but the
 564 expedited implementation accepts extreme CPU overhead to obtain
 565 much lower grace-period latency, for example, consuming a few
 566 tens of microseconds worth of CPU time to reduce grace-period
 567 duration from milliseconds to tens of microseconds.
 568 The <tt>-&gt;qsmaskinit</tt> field tracks which of this
 569 <tt>rcu_node</tt> structure's children cover for at least
 570 one online CPU.
 571 This mask is used to initialize <tt>-&gt;qsmask</tt>,
 572 and <tt>-&gt;expmaskinit</tt> is used to initialize
 573 <tt>-&gt;expmask</tt> and the beginning of the
 574 normal and expedited grace periods, respectively.
 575
 576 <table>
 577 <tr><th>&nbsp;</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&nbsp;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&nbsp;1 is running
 599                 <tt>force_quiescent_state()</tt>,
 600                 and notices that CPU&nbsp;0 has been in dyntick idle mode,
 601                 which qualifies as an extended quiescent state.
 602                 </font><p>
 603         <li>    <font color="ffffff">CPU&nbsp;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&nbsp;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&nbsp;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&nbsp;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>-&gt;gpnum</tt> and <tt>-&gt;completed</tt>.
 632 </font></td></tr>
 633 <tr><td>&nbsp;</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
 639 midst of their RCU read-side critical sections, and these tasks
 640 must be tracked explicitly.
 641 The details of exactly why and how they are tracked will be covered
 642 in a separate article on RCU read-side processing.
 643 For now, it is enough to know that the <tt>rcu_node</tt>
 644 structure 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>-&gt;blkd_tasks</tt> field is a list header for
 654 the list of blocked and preempted tasks.
 655 As tasks undergo context switches within RCU read-side critical
 656 sections, their <tt>task_struct</tt> structures are enqueued
 657 (via the <tt>task_struct</tt>'s <tt>-&gt;rcu_node_entry</tt>
 658 field) onto the head of the <tt>-&gt;blkd_tasks</tt> list for the
 659 leaf <tt>rcu_node</tt> structure corresponding to the CPU
 660 on which the outgoing context switch executed.
 661 As these tasks later exit their RCU read-side critical sections,
 662 they remove themselves from the list.
 663 This list is therefore in reverse time order, so that if one of the tasks
 664 is blocking the current grace period, all subsequent tasks must
 665 also be blocking that same grace period.
 666 Therefore, a single pointer into this list suffices to track
 667 all tasks blocking a given grace period.
 668 That pointer is stored in <tt>-&gt;gp_tasks</tt> for normal
 669 grace periods and in <tt>-&gt;exp_tasks</tt> for expedited
 670 grace periods.
 671 These last two fields are <tt>NULL</tt> if either there is
 672 no grace period in flight or if there are no blocked tasks
 673 preventing that grace period from completing.
 674 If either of these two pointers is referencing a task that
 675 removes itself from the <tt>-&gt;blkd_tasks</tt> list,
 676 then that task must advance the pointer to the next task on
 677 the list, or set the pointer to <tt>NULL</tt> if there
 678 are no subsequent tasks on the list.
 679
 680 </p><p>For example, suppose that tasks&nbsp;T1, T2, and&nbsp;T3 are
 681 all hard-affinitied to the largest-numbered CPU in the system.
 682 Then if task&nbsp;T1 blocked in an RCU read-side
 683 critical section, then an expedited grace period started,
 684 then task&nbsp;T2 blocked in an RCU read-side critical section,
 685 then a normal grace period started, and finally task&nbsp;3 blocked
 686 in an RCU read-side critical section, then the state of the
 687 last leaf <tt>rcu_node</tt> structure's blocked-task list
 688 would be as shown below:
 689
 690 </p><p><img src="blkd_task.svg" alt="blkd_task.svg" width="60%">
 691
 692 </p><p>Task&nbsp;T1 is blocking both grace periods, task&nbsp;T2 is
 693 blocking only the normal grace period, and task&nbsp;T3 is blocking
 694 neither grace period.
 695 Note that these tasks will not remove themselves from this list
 696 immediately upon resuming execution.
 697 They will instead remain on the list until they execute the outermost
 698 <tt>rcu_read_unlock()</tt> that ends their RCU read-side critical
 699 section.
 700
 701 <p>
 702 The <tt>-&gt;wait_blkd_tasks</tt> field indicates whether or not
 703 the 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
 708 C-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
 720 10
 721 11 #ifdef CONFIG_RCU_FANOUT_LEAF
 722 12 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
 723 13 #else
 724 14 # ifdef CONFIG_64BIT
 725 15 # define RCU_FANOUT_LEAF 64
 726 16 # else
 727 17 # define RCU_FANOUT_LEAF 32
 728 18 # endif
 729 19 #endif
 730 20
 731 21 #define RCU_FANOUT_1        (RCU_FANOUT_LEAF)
 732 22 #define RCU_FANOUT_2        (RCU_FANOUT_1 * RCU_FANOUT)
 733 23 #define RCU_FANOUT_3        (RCU_FANOUT_2 * RCU_FANOUT)
 734 24 #define RCU_FANOUT_4        (RCU_FANOUT_3 * RCU_FANOUT)
 735 25
 736 26 #if NR_CPUS &lt;= RCU_FANOUT_1
 737 27 #  define RCU_NUM_LVLS        1
 738 28 #  define NUM_RCU_LVL_0        1
 739 29 #  define NUM_RCU_NODES        NUM_RCU_LVL_0
 740 30 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0 }
 741 31 #  define RCU_NODE_NAME_INIT  { "rcu_node_0" }
 742 32 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0" }
 743 33 #  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0" }
 744 34 #elif NR_CPUS &lt;= RCU_FANOUT_2
 745 35 #  define RCU_NUM_LVLS        2
 746 36 #  define NUM_RCU_LVL_0        1
 747 37 #  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
 748 38 #  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
 749 39 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
 750 40 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1" }
 751 41 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1" }
 752 42 #  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1" }
 753 43 #elif NR_CPUS &lt;= RCU_FANOUT_3
 754 44 #  define RCU_NUM_LVLS        3
 755 45 #  define NUM_RCU_LVL_0        1
 756 46 #  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
 757 47 #  define NUM_RCU_LVL_2        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
 758 48 #  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
 759 49 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
 760 50 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
 761 51 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
 762 52 #  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" }
 763 53 #elif NR_CPUS &lt;= RCU_FANOUT_4
 764 54 #  define RCU_NUM_LVLS        4
 765 55 #  define NUM_RCU_LVL_0        1
 766 56 #  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
 767 57 #  define NUM_RCU_LVL_2        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
 768 58 #  define NUM_RCU_LVL_3        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
 769 59 #  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
 770 60 #  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
 771 61 #  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
 772 62 #  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
 773 63 #  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" }
 774 64 #else
 775 65 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
 776 66 #endif
 777 </pre>
 778
 779 <p>The maximum number of levels in the <tt>rcu_node</tt> structure
 780 is currently limited to four, as specified by lines&nbsp;21-24
 781 and the structure of the subsequent &ldquo;if&rdquo; statement.
 782 For 32-bit systems, this allows 16*32*32*32=524,288 CPUs, which
 783 should be sufficient for the next few years at least.
 784 For 64-bit systems, 16*64*64*64=4,194,304 CPUs is allowed, which
 785 should see us through the next decade or so.
 786 This four-level tree also allows kernels built with
 787 <tt>CONFIG_RCU_FANOUT=8</tt> to support up to 4096 CPUs,
 788 which might be useful in very large systems having eight CPUs per
 789 socket (but please note that no one has yet shown any measurable
 790 performance degradation due to misaligned socket and <tt>rcu_node</tt>
 791 boundaries).
 792 In addition, building kernels with a full four levels of <tt>rcu_node</tt>
 793 tree permits better testing of RCU's combining-tree code.
 794
 795 </p><p>The <tt>RCU_FANOUT</tt> symbol controls how many children
 796 are permitted at each non-leaf level of the <tt>rcu_node</tt> tree.
 797 If the <tt>CONFIG_RCU_FANOUT</tt> Kconfig option is not specified,
 798 it is set based on the word size of the system, which is also
 799 the Kconfig default.
 800
 801 </p><p>The <tt>RCU_FANOUT_LEAF</tt> symbol controls how many CPUs are
 802 handled by each leaf <tt>rcu_node</tt> structure.
 803 Experience has shown that allowing a given leaf <tt>rcu_node</tt>
 804 structure to handle 64 CPUs, as permitted by the number of bits in
 805 the <tt>-&gt;qsmask</tt> field on a 64-bit system, results in
 806 excessive contention for the leaf <tt>rcu_node</tt> structures'
 807 <tt>-&gt;lock</tt> fields.
 808 The number of CPUs per leaf <tt>rcu_node</tt> structure is therefore
 809 limited to 16 given the default value of <tt>CONFIG_RCU_FANOUT_LEAF</tt>.
 810 If <tt>CONFIG_RCU_FANOUT_LEAF</tt> is unspecified, the value
 811 selected is based on the word size of the system, just as for
 812 <tt>CONFIG_RCU_FANOUT</tt>.
 813 Lines&nbsp;11-19 perform this computation.
 814
 815 </p><p>Lines&nbsp;21-24 compute the maximum number of CPUs supported by
 816 a single-level (which contains a single <tt>rcu_node</tt> structure),
 817 two-level, three-level, and four-level <tt>rcu_node</tt> tree,
 818 respectively, given the fanout specified by <tt>RCU_FANOUT</tt>
 819 and <tt>RCU_FANOUT_LEAF</tt>.
 820 These 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>
 825 C-preprocessor variables, respectively.
 826
 827 </p><p>These variables are used to control the C-preprocessor <tt>#if</tt>
 828 statement spanning lines&nbsp;26-66 that computes the number of
 829 <tt>rcu_node</tt> structures required for each level of the tree,
 830 as well as the number of levels required.
 831 The number of levels is placed in the <tt>NUM_RCU_LVLS</tt>
 832 C-preprocessor variable by lines&nbsp;27, 35, 44, and&nbsp;54.
 833 The number of <tt>rcu_node</tt> structures for the topmost level
 834 of the tree is always exactly one, and this value is unconditionally
 835 placed into <tt>NUM_RCU_LVL_0</tt> by lines&nbsp;28, 36, 45, and&nbsp;55.
 836 The rest of the levels (if any) of the <tt>rcu_node</tt> tree
 837 are computed by dividing the maximum number of CPUs by the
 838 fanout supported by the number of levels from the current level down,
 839 rounding up.  This computation is performed by lines&nbsp;37,
 840 46-47, and&nbsp;56-58.
 841 Lines&nbsp;31-33, 40-42, 50-52, and&nbsp;62-63 create initializers
 842 for lockdep lock-class names.
 843 Finally, lines&nbsp;64-66 produce an error if the maximum number of
 844 CPUs is too large for the specified fanout.
 845
 846 <h3><a name="The rcu_segcblist Structure">
 847 The <tt>rcu_segcblist</tt> Structure</a></h3>
 848
 849 The <tt>rcu_segcblist</tt> structure maintains a segmented list of
 850 callbacks 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];
 862 10   unsigned long gp_seq[RCU_CBLIST_NSEGS];
 863 11   long len;
 864 12   long len_lazy;
 865 13 };
 866 </pre>
 867
 868 <p>
 869 The 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>-&gt;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>
 885 The <tt>-&gt;head</tt> pointer references the first callback or
 886 is <tt>NULL</tt> if the list contains no callbacks (which is
 887 <i>not</i> the same as being empty).
 888 Each element of the <tt>-&gt;tails[]</tt> array references the
 889 <tt>-&gt;next</tt> pointer of the last callback in the corresponding
 890 segment of the list, or the list's <tt>-&gt;head</tt> pointer if
 891 that segment and all previous segments are empty.
 892 If the corresponding segment is empty but some previous segment is
 893 not empty, then the array element is identical to its predecessor.
 894 Older callbacks are closer to the head of the list, and new callbacks
 895 are added at the tail.
 896 This relationship between the <tt>-&gt;head</tt> pointer, the
 897 <tt>-&gt;tails[]</tt> array, and the callbacks is shown in this
 898 diagram:
 899
 900 </p><p><img src="nxtlist.svg" alt="nxtlist.svg" width="40%">
 901
 902 </p><p>In this figure, the <tt>-&gt;head</tt> pointer references the
 903 first
 904 RCU callback in the list.
 905 The <tt>-&gt;tails[RCU_DONE_TAIL]</tt> array element references
 906 the <tt>-&gt;head</tt> pointer itself, indicating that none
 907 of the callbacks is ready to invoke.
 908 The <tt>-&gt;tails[RCU_WAIT_TAIL]</tt> array element references callback
 909 CB&nbsp;2's <tt>-&gt;next</tt> pointer, which indicates that
 910 CB&nbsp;1 and CB&nbsp;2 are both waiting on the current grace period,
 911 give or take possible disagreements about exactly which grace period
 912 is the current one.
 913 The <tt>-&gt;tails[RCU_NEXT_READY_TAIL]</tt> array element
 914 references the same RCU callback that <tt>-&gt;tails[RCU_WAIT_TAIL]</tt>
 915 does, which indicates that there are no callbacks waiting on the next
 916 RCU grace period.
 917 The <tt>-&gt;tails[RCU_NEXT_TAIL]</tt> array element references
 918 CB&nbsp;4's <tt>-&gt;next</tt> pointer, indicating that all the
 919 remaining RCU callbacks have not yet been assigned to an RCU grace
 920 period.
 921 Note that the <tt>-&gt;tails[RCU_NEXT_TAIL]</tt> array element
 922 always references the last RCU callback's <tt>-&gt;next</tt> pointer
 923 unless the callback list is empty, in which case it references
 924 the <tt>-&gt;head</tt> pointer.
 925
 926 <p>
 927 There is one additional important special case for the
 928 <tt>-&gt;tails[RCU_NEXT_TAIL]</tt> array element: It can be <tt>NULL</tt>
 929 when this list is <i>disabled</i>.
 930 Lists are disabled when the corresponding CPU is offline or when
 931 the corresponding CPU's callbacks are offloaded to a kthread,
 932 both 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
 937 as grace periods advance.
 938
 939 </p><p>The <tt>-&gt;gp_seq[]</tt> array records grace-period
 940 numbers corresponding to the list segments.
 941 This is what allows different CPUs to have different ideas as to
 942 which is the current grace period while still avoiding premature
 943 invocation of their callbacks.
 944 In particular, this allows CPUs that go idle for extended periods
 945 to determine which of their callbacks are ready to be invoked after
 946 reawakening.
 947
 948 </p><p>The <tt>-&gt;len</tt> counter contains the number of
 949 callbacks in <tt>-&gt;head</tt>, and the
 950 <tt>-&gt;len_lazy</tt> contains the number of those callbacks that
 951 are known to only free memory, and whose invocation can therefore
 952 be safely deferred.
 953
 954 <p><b>Important note</b>: It is the <tt>-&gt;len</tt> field that
 955 determines whether or not there are callbacks associated with
 956 this <tt>rcu_segcblist</tt> structure, <i>not</i> the <tt>-&gt;head</tt>
 957 pointer.
 958 The 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
 960 all at once at callback-invocation time.
 961 If callback invocation must be postponed, for example, because a
 962 high-priority process just woke up on this CPU, then the remaining
 963 callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment.
 964 Either way, the <tt>-&gt;len</tt> and <tt>-&gt;len_lazy</tt> counts
 965 are adjusted after the corresponding callbacks have been invoked, and so
 966 again it is the <tt>-&gt;len</tt> count that accurately reflects whether
 967 or not there are callbacks associated with this <tt>rcu_segcblist</tt>
 968 structure.
 969 Of course, off-CPU sampling of the <tt>-&gt;len</tt> count requires
 970 the use of appropriate synchronization, for example, memory barriers.
 971 This synchronization can be a bit subtle, particularly in the case
 972 of <tt>rcu_barrier()</tt>.
 973
 974 <h3><a name="The rcu_data Structure">
 975 The <tt>rcu_data</tt> Structure</a></h3>
 976
 977 <p>The <tt>rcu_data</tt> maintains the per-CPU state for the
 978 corresponding flavor of RCU.
 979 The fields in this structure may be accessed only from the corresponding
 980 CPU (and from tracing) unless otherwise stated.
 981 This structure is the
 982 focus of quiescent-state detection and RCU callback queuing.
 983 It also tracks its relationship to the corresponding leaf
 984 <tt>rcu_node</tt> structure to allow more-efficient
 985 propagation of quiescent states up the <tt>rcu_node</tt>
 986 combining tree.
 987 Like the <tt>rcu_node</tt> structure, it provides a local
 988 copy of the grace-period information to allow for-free
 989 synchronized
 990 access to this information from the corresponding CPU.
 991 Finally, this structure records past dyntick-idle state
 992 for the corresponding CPU and also tracks statistics.
 993
 994 </p><p>The <tt>rcu_data</tt> structure's fields are discussed,
 995 singly 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
1000 as 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>-&gt;cpu</tt> field contains the number of the
1012 corresponding CPU, the <tt>-&gt;rsp</tt> pointer references
1013 the corresponding <tt>rcu_state</tt> structure (and is most frequently
1014 used to locate the name of the corresponding flavor of RCU for tracing),
1015 and the <tt>-&gt;mynode</tt> field references the corresponding
1016 <tt>rcu_node</tt> structure.
1017 The <tt>-&gt;mynode</tt> is used to propagate quiescent states
1018 up the combining tree.
1019 <p>The <tt>-&gt;dynticks</tt> pointer references the
1020 <tt>rcu_dynticks</tt> structure corresponding to this
1021 CPU.
1022 Recall that a single per-CPU instance of the <tt>rcu_dynticks</tt>
1023 structure is shared among all flavors of RCU.
1024 These first four fields are constant and therefore require not
1025 synchronization.
1026
1027 </p><p>The <tt>-&gt;grpmask</tt> field indicates the bit in
1028 the <tt>-&gt;mynode-&gt;qsmask</tt> corresponding to this
1029 <tt>rcu_data</tt> structure, and is also used when propagating
1030 quiescent states.
1031 The <tt>-&gt;beenonline</tt> flag is set whenever the corresponding
1032 CPU comes online, which means that the debugfs tracing need not dump
1033 out 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
1038 as 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>
1050 fields are the counterparts of the fields of the same name
1051 in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures.
1052 They may each lag up to one behind their <tt>rcu_node</tt>
1053 counterparts, but in <tt>CONFIG_NO_HZ_IDLE</tt> and
1054 <tt>CONFIG_NO_HZ_FULL</tt> kernels can lag
1055 arbitrarily far behind for CPUs in dyntick-idle mode (but these counters
1056 will catch up upon exit from dyntick-idle mode).
1057 If a given <tt>rcu_data</tt> structure's <tt>-&gt;gpnum</tt> and
1058 <tt>-&gt;complete</tt> fields are equal, then this <tt>rcu_data</tt>
1059 structure believes that RCU is idle.
1060 Otherwise, as with the <tt>rcu_state</tt> and <tt>rcu_node</tt>
1061 structure,
1062 the <tt>-&gt;gpnum</tt> field will be one greater than the
1063 <tt>-&gt;complete</tt> fields, with <tt>-&gt;gpnum</tt>
1064 indicating which grace period this <tt>rcu_data</tt> believes
1065 is still being waited for.
1066
1067 <table>
1068 <tr><th>&nbsp;</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>&nbsp;</td></tr>
1087 </table>
1088
1089 <p>The <tt>-&gt;cpu_no_qs</tt> flag indicates that the
1090 CPU has not yet passed through a quiescent state,
1091 while the <tt>-&gt;core_needs_qs</tt> flag indicates that the
1092 RCU core needs a quiescent state from the corresponding CPU.
1093 The <tt>-&gt;gpwrap</tt> field indicates that the corresponding
1094 CPU has remained idle for so long that the <tt>completed</tt>
1095 and <tt>gpnum</tt> counters are in danger of overflow, which
1096 will cause the CPU to disregard the values of its counters on
1097 its next exit from idle.
1098 Finally, the <tt>rcu_qs_ctr_snap</tt> field is used to detect
1099 cases where a given operation has resulted in a quiescent state
1100 for all flavors of RCU, for example, <tt>cond_resched()</tt>
1101 when RCU has indicated a need for quiescent states.
1102
1103 <h5>RCU Callback Handling</h5>
1104
1105 <p>In the absence of CPU-hotplug events, RCU callbacks are invoked by
1106 the same CPU that registered them.
1107 This is strictly a cache-locality optimization: callbacks can and
1108 do get invoked on CPUs other than the one that registered them.
1109 After all, if the CPU that registered a given callback has gone
1110 offline before the callback can be invoked, there really is no other
1111 choice.
1112
1113 </p><p>This portion of the <tt>rcu_data</tt> structure is declared
1114 as follows:
1115
1116 <pre>
1117  1 struct rcu_segcblist cblist;
1118  2 long qlen_last_fqs_check;
1119  3 unsigned long n_cbs_invoked;
1120  4 unsigned long n_nocbs_invoked;
1121  5 unsigned long n_cbs_orphaned;
1122  6 unsigned long n_cbs_adopted;
1123  7 unsigned long n_force_qs_snap;
1124  8 long blimit;
1125 </pre>
1126
1127 <p>The <tt>-&gt;cblist</tt> structure is the segmented callback list
1128 described earlier.
1129 The CPU advances the callbacks in its <tt>rcu_data</tt> structure
1130 whenever it notices that another RCU grace period has completed.
1131 The CPU detects the completion of an RCU grace period by noticing
1132 that the value of its <tt>rcu_data</tt> structure's
1133 <tt>-&gt;completed</tt> field differs from that of its leaf
1134 <tt>rcu_node</tt> structure.
1135 Recall that each <tt>rcu_node</tt> structure's
1136 <tt>-&gt;completed</tt> field is updated at the end of each
1137 grace period.
1138
1139 <p>
1140 The <tt>-&gt;qlen_last_fqs_check</tt> and
1141 <tt>-&gt;n_force_qs_snap</tt> coordinate the forcing of quiescent
1142 states from <tt>call_rcu()</tt> and friends when callback
1143 lists grow excessively long.
1144
1145 </p><p>The <tt>-&gt;n_cbs_invoked</tt>,
1146 <tt>-&gt;n_cbs_orphaned</tt>, and <tt>-&gt;n_cbs_adopted</tt>
1147 fields count the number of callbacks invoked,
1148 sent to other CPUs when this CPU goes offline,
1149 and received from other CPUs when those other CPUs go offline.
1150 The <tt>-&gt;n_nocbs_invoked</tt> is used when the CPU's callbacks
1151 are offloaded to a kthread.
1152
1153 <p>
1154 Finally, the <tt>-&gt;blimit</tt> counter is the maximum number of
1155 RCU callbacks that may be invoked at a given time.
1156
1157 <h5>Dyntick-Idle Handling</h5>
1158
1159 <p>This portion of the <tt>rcu_data</tt> structure is declared
1160 as follows:
1161
1162 <pre>
1163   1   int dynticks_snap;
1164   2   unsigned long dynticks_fqs;
1165 </pre>
1166
1167 The <tt>-&gt;dynticks_snap</tt> field is used to take a snapshot
1168 of the corresponding CPU's dyntick-idle state when forcing
1169 quiescent states, and is therefore accessed from other CPUs.
1170 Finally, the <tt>-&gt;dynticks_fqs</tt> field is used to
1171 count the number of times this CPU is determined to be in
1172 dyntick-idle state, and is used for tracing and debugging purposes.
1173
1174 <h3><a name="The rcu_dynticks Structure">
1175 The <tt>rcu_dynticks</tt> Structure</a></h3>
1176
1177 <p>The <tt>rcu_dynticks</tt> maintains the per-CPU dyntick-idle state
1178 for the corresponding CPU.
1179 Unlike the other structures, <tt>rcu_dynticks</tt> is not
1180 replicated over the different flavors of RCU.
1181 The fields in this structure may be accessed only from the corresponding
1182 CPU (and from tracing) unless otherwise stated.
1183 Its fields are as follows:
1184
1185 <pre>
1186   1   long dynticks_nesting;
1187   2   long dynticks_nmi_nesting;
1188   3   atomic_t dynticks;
1189   4   bool rcu_need_heavy_qs;
1190   5   unsigned long rcu_qs_ctr;
1191   6   bool rcu_urgent_qs;
1192 </pre>
1193
1194 <p>The <tt>-&gt;dynticks_nesting</tt> field counts the
1195 nesting depth of process execution, so that in normal circumstances
1196 this counter has value zero or one.
1197 NMIs, irqs, and tracers are counted by the <tt>-&gt;dynticks_nmi_nesting</tt>
1198 field.
1199 Because NMIs cannot be masked, changes to this variable have to be
1200 undertaken carefully using an algorithm provided by Andy Lutomirski.
1201 The initial transition from idle adds one, and nested transitions
1202 add two, so that a nesting level of five is represented by a
1203 <tt>-&gt;dynticks_nmi_nesting</tt> value of nine.
1204 This counter can therefore be thought of as counting the number
1205 of reasons why this CPU cannot be permitted to enter dyntick-idle
1206 mode, aside from process-level transitions.
1207
1208 <p>However, it turns out that when running in non-idle kernel context,
1209 the Linux kernel is fully capable of entering interrupt handlers that
1210 never exit and perhaps also vice versa.
1211 Therefore, whenever the <tt>-&gt;dynticks_nesting</tt> field is
1212 incremented up from zero, the <tt>-&gt;dynticks_nmi_nesting</tt> field
1213 is set to a large positive number, and whenever the
1214 <tt>-&gt;dynticks_nesting</tt> field is decremented down to zero,
1215 the the <tt>-&gt;dynticks_nmi_nesting</tt> field is set to zero.
1216 Assuming that the number of misnested interrupts is not sufficient
1217 to overflow the counter, this approach corrects the
1218 <tt>-&gt;dynticks_nmi_nesting</tt> field every time the corresponding
1219 CPU enters the idle loop from process context.
1220
1221 </p><p>The <tt>-&gt;dynticks</tt> field counts the corresponding
1222 CPU's transitions to and from dyntick-idle mode, so that this counter
1223 has an even value when the CPU is in dyntick-idle mode and an odd
1224 value otherwise.
1225
1226 </p><p>The <tt>-&gt;rcu_need_heavy_qs</tt> field is used
1227 to record the fact that the RCU core code would really like to
1228 see a quiescent state from the corresponding CPU, so much so that
1229 it is willing to call for heavy-weight dyntick-counter operations.
1230 This flag is checked by RCU's context-switch and <tt>cond_resched()</tt>
1231 code, which provide a momentary idle sojourn in response.
1232
1233 </p><p>The <tt>-&gt;rcu_qs_ctr</tt> field is used to record
1234 quiescent states from <tt>cond_resched()</tt>.
1235 Because <tt>cond_resched()</tt> can execute quite frequently, this
1236 must be quite lightweight, as in a non-atomic increment of this
1237 per-CPU field.
1238
1239 </p><p>Finally, the <tt>-&gt;rcu_urgent_qs</tt> field is used to record
1240 the fact that the RCU core code would really like to see a quiescent
1241 state from the corresponding CPU, with the various other fields indicating
1242 just how badly RCU wants this quiescent state.
1243 This flag is checked by RCU's context-switch and <tt>cond_resched()</tt>
1244 code, which, if nothing else, non-atomically increment <tt>-&gt;rcu_qs_ctr</tt>
1245 in response.
1246
1247 <table>
1248 <tr><th>&nbsp;</th></tr>
1249 <tr><th align="left">Quick Quiz:</th></tr>
1250 <tr><td>
1251         Why not simply combine the <tt>-&gt;dynticks_nesting</tt>
1252         and <tt>-&gt;dynticks_nmi_nesting</tt> counters into a
1253         single counter that just counts the number of reasons that
1254         the corresponding CPU is non-idle?
1255 </td></tr>
1256 <tr><th align="left">Answer:</th></tr>
1257 <tr><td bgcolor="#ffffff"><font color="ffffff">
1258         Because this would fail in the presence of interrupts whose
1259         handlers never return and of handlers that manage to return
1260         from a made-up interrupt.
1261 </font></td></tr>
1262 <tr><td>&nbsp;</td></tr>
1263 </table>
1264
1265 <p>Additional fields are present for some special-purpose
1266 builds, and are discussed separately.
1267
1268 <h3><a name="The rcu_head Structure">
1269 The <tt>rcu_head</tt> Structure</a></h3>
1270
1271 <p>Each <tt>rcu_head</tt> structure represents an RCU callback.
1272 These structures are normally embedded within RCU-protected data
1273 structures whose algorithms use asynchronous grace periods.
1274 In contrast, when using algorithms that block waiting for RCU grace periods,
1275 RCU users need not provide <tt>rcu_head</tt> structures.
1276
1277 </p><p>The <tt>rcu_head</tt> structure has fields as follows:
1278
1279 <pre>
1280   1   struct rcu_head *next;
1281   2   void (*func)(struct rcu_head *head);
1282 </pre>
1283
1284 <p>The <tt>-&gt;next</tt> field is used
1285 to link the <tt>rcu_head</tt> structures together in the
1286 lists within the <tt>rcu_data</tt> structures.
1287 The <tt>-&gt;func</tt> field is a pointer to the function
1288 to be called when the callback is ready to be invoked, and
1289 this function is passed a pointer to the <tt>rcu_head</tt>
1290 structure.
1291 However, <tt>kfree_rcu()</tt> uses the <tt>-&gt;func</tt>
1292 field to record the offset of the <tt>rcu_head</tt>
1293 structure within the enclosing RCU-protected data structure.
1294
1295 </p><p>Both of these fields are used internally by RCU.
1296 From the viewpoint of RCU users, this structure is an
1297 opaque &ldquo;cookie&rdquo;.
1298
1299 <table>
1300 <tr><th>&nbsp;</th></tr>
1301 <tr><th align="left">Quick Quiz:</th></tr>
1302 <tr><td>
1303         Given that the callback function <tt>-&gt;func</tt>
1304         is passed a pointer to the <tt>rcu_head</tt> structure,
1305         how is that function supposed to find the beginning of the
1306         enclosing RCU-protected data structure?
1307 </td></tr>
1308 <tr><th align="left">Answer:</th></tr>
1309 <tr><td bgcolor="#ffffff"><font color="ffffff">
1310         In actual practice, there is a separate callback function per
1311         type of RCU-protected data structure.
1312         The callback function can therefore use the <tt>container_of()</tt>
1313         macro in the Linux kernel (or other pointer-manipulation facilities
1314         in other software environments) to find the beginning of the
1315         enclosing structure.
1316 </font></td></tr>
1317 <tr><td>&nbsp;</td></tr>
1318 </table>
1319
1320 <h3><a name="RCU-Specific Fields in the task_struct Structure">
1321 RCU-Specific Fields in the <tt>task_struct</tt> Structure</a></h3>
1322
1323 <p>The <tt>CONFIG_PREEMPT_RCU</tt> implementation uses some
1324 additional fields in the <tt>task_struct</tt> structure:
1325
1326 <pre>
1327  1 #ifdef CONFIG_PREEMPT_RCU
1328  2   int rcu_read_lock_nesting;
1329  3   union rcu_special rcu_read_unlock_special;
1330  4   struct list_head rcu_node_entry;
1331  5   struct rcu_node *rcu_blocked_node;
1332  6 #endif /* #ifdef CONFIG_PREEMPT_RCU */
1333  7 #ifdef CONFIG_TASKS_RCU
1334  8   unsigned long rcu_tasks_nvcsw;
1335  9   bool rcu_tasks_holdout;
1336 10   struct list_head rcu_tasks_holdout_list;
1337 11   int rcu_tasks_idle_cpu;
1338 12 #endif /* #ifdef CONFIG_TASKS_RCU */
1339 </pre>
1340
1341 <p>The <tt>-&gt;rcu_read_lock_nesting</tt> field records the
1342 nesting level for RCU read-side critical sections, and
1343 the <tt>-&gt;rcu_read_unlock_special</tt> field is a bitmask
1344 that records special conditions that require <tt>rcu_read_unlock()</tt>
1345 to do additional work.
1346 The <tt>-&gt;rcu_node_entry</tt> field is used to form lists of
1347 tasks that have blocked within preemptible-RCU read-side critical
1348 sections and the <tt>-&gt;rcu_blocked_node</tt> field references
1349 the <tt>rcu_node</tt> structure whose list this task is a member of,
1350 or <tt>NULL</tt> if it is not blocked within a preemptible-RCU
1351 read-side critical section.
1352
1353 <p>The <tt>-&gt;rcu_tasks_nvcsw</tt> field tracks the number of
1354 voluntary context switches that this task had undergone at the
1355 beginning of the current tasks-RCU grace period,
1356 <tt>-&gt;rcu_tasks_holdout</tt> is set if the current tasks-RCU
1357 grace period is waiting on this task, <tt>-&gt;rcu_tasks_holdout_list</tt>
1358 is a list element enqueuing this task on the holdout list,
1359 and <tt>-&gt;rcu_tasks_idle_cpu</tt> tracks which CPU this
1360 idle task is running, but only if the task is currently running,
1361 that is, if the CPU is currently idle.
1362
1363 <h3><a name="Accessor Functions">
1364 Accessor Functions</a></h3>
1365
1366 <p>The following listing shows the
1367 <tt>rcu_get_root()</tt>, <tt>rcu_for_each_node_breadth_first</tt>,
1368 <tt>rcu_for_each_nonleaf_node_breadth_first()</tt>, and
1369 <tt>rcu_for_each_leaf_node()</tt> function and macros:
1370
1371 <pre>
1372   1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
1373   2 {
1374   3   return &amp;rsp-&gt;node[0];
1375   4 }
1376   5
1377   6 #define rcu_for_each_node_breadth_first(rsp, rnp) \
1378   7   for ((rnp) = &amp;(rsp)-&gt;node[0]; \
1379   8        (rnp) &lt; &amp;(rsp)-&gt;node[NUM_RCU_NODES]; (rnp)++)
1380   9
1381  10 #define rcu_for_each_nonleaf_node_breadth_first(rsp, rnp) \
1382  11   for ((rnp) = &amp;(rsp)-&gt;node[0]; \
1383  12        (rnp) &lt; (rsp)-&gt;level[NUM_RCU_LVLS - 1]; (rnp)++)
1384  13
1385  14 #define rcu_for_each_leaf_node(rsp, rnp) \
1386  15   for ((rnp) = (rsp)-&gt;level[NUM_RCU_LVLS - 1]; \
1387  16        (rnp) &lt; &amp;(rsp)-&gt;node[NUM_RCU_NODES]; (rnp)++)
1388 </pre>
1389
1390 <p>The <tt>rcu_get_root()</tt> simply returns a pointer to the
1391 first element of the specified <tt>rcu_state</tt> structure's
1392 <tt>-&gt;node[]</tt> array, which is the root <tt>rcu_node</tt>
1393 structure.
1394
1395 </p><p>As noted earlier, the <tt>rcu_for_each_node_breadth_first()</tt>
1396 macro takes advantage of the layout of the <tt>rcu_node</tt>
1397 structures in the <tt>rcu_state</tt> structure's
1398 <tt>-&gt;node[]</tt> array, performing a breadth-first traversal by
1399 simply traversing the array in order.
1400 The <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> macro operates
1401 similarly, but traverses only the first part of the array, thus excluding
1402 the leaf <tt>rcu_node</tt> structures.
1403 Finally, the <tt>rcu_for_each_leaf_node()</tt> macro traverses only
1404 the last part of the array, thus traversing only the leaf
1405 <tt>rcu_node</tt> structures.
1406
1407 <table>
1408 <tr><th>&nbsp;</th></tr>
1409 <tr><th align="left">Quick Quiz:</th></tr>
1410 <tr><td>
1411         What do <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> and
1412         <tt>rcu_for_each_leaf_node()</tt> do if the <tt>rcu_node</tt> tree
1413         contains only a single node?
1414 </td></tr>
1415 <tr><th align="left">Answer:</th></tr>
1416 <tr><td bgcolor="#ffffff"><font color="ffffff">
1417         In the single-node case,
1418         <tt>rcu_for_each_nonleaf_node_breadth_first()</tt> is a no-op
1419         and <tt>rcu_for_each_leaf_node()</tt> traverses the single node.
1420 </font></td></tr>
1421 <tr><td>&nbsp;</td></tr>
1422 </table>
1423
1424 <h3><a name="Summary">
1425 Summary</a></h3>
1426
1427 So each flavor of RCU is represented by an <tt>rcu_state</tt> structure,
1428 which contains a combining tree of <tt>rcu_node</tt> and
1429 <tt>rcu_data</tt> structures.
1430 Finally, in <tt>CONFIG_NO_HZ_IDLE</tt> kernels, each CPU's dyntick-idle
1431 state is tracked by an <tt>rcu_dynticks</tt> structure.
1432
1433 If you made it this far, you are well prepared to read the code
1434 walkthroughs in the other articles in this series.
1435
1436 <h3><a name="Acknowledgments">
1437 Acknowledgments</a></h3>
1438
1439 I owe thanks to Cyrill Gorcunov, Mathieu Desnoyers, Dhaval Giani, Paul
1440 Turner, Abhishek Srivastava, Matt Kowalczyk, and Serge Hallyn
1441 for helping me get this document into a more human-readable state.
1442
1443 <h3><a name="Legal Statement">
1444 Legal Statement</a></h3>
1445
1446 <p>This work represents the view of the author and does not necessarily
1447 represent the view of IBM.
1448
1449 </p><p>Linux is a registered trademark of Linus Torvalds.
1450
1451 </p><p>Other company, product, and service names may be trademarks or
1452 service marks of others.
1453
1454 </body></html>