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

Source file repositories/reference/linux-study-clean/Documentation/RCU/Design/Data-Structures/Data-Structures.rst

File Facts

System
Linux kernel
Corpus path
Documentation/RCU/Design/Data-Structures/Data-Structures.rst
Extension
.rst
Size
58697 bytes
Lines
1197
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

===================================================
A Tour Through TREE_RCU's Data Structures [LWN.net]
===================================================

December 18, 2016

This article was contributed by Paul E. McKenney

Introduction
============

This document describes RCU's major data structures and their relationship
to each other.

Data-Structure Relationships
============================

RCU is for all intents and purposes a large state machine, and its
data structures maintain the state in such a way as to allow RCU readers
to execute extremely quickly, while also processing the RCU grace periods
requested by updaters in an efficient and extremely scalable fashion.
The efficiency and scalability of RCU updaters is provided primarily
by a combining tree, as shown below:

.. kernel-figure:: BigTreeClassicRCU.svg

This diagram shows an enclosing ``rcu_state`` structure containing a tree
of ``rcu_node`` structures. Each leaf node of the ``rcu_node`` tree has up
to 16 ``rcu_data`` structures associated with it, so that there are
``NR_CPUS`` number of ``rcu_data`` structures, one for each possible CPU.
This structure is adjusted at boot time, if needed, to handle the common
case where ``nr_cpu_ids`` is much less than ``NR_CPUs``.
For example, a number of Linux distributions set ``NR_CPUs=4096``,
which results in a three-level ``rcu_node`` tree.
If the actual hardware has only 16 CPUs, RCU will adjust itself
at boot time, resulting in an ``rcu_node`` tree with only a single node.

The purpose of this combining tree is to allow per-CPU events
such as quiescent states, dyntick-idle transitions,
and CPU hotplug operations to be processed efficiently
and scalably.
Quiescent states are recorded by the per-CPU ``rcu_data`` structures,
and other events are recorded by the leaf-level ``rcu_node``
structures.
All of these events are combined at each level of the tree until finally
grace periods are completed at the tree's root ``rcu_node``
structure.
A grace period can be completed at the root once every CPU
(or, in the case of ``CONFIG_PREEMPT_RCU``, task)
has passed through a quiescent state.
Once a grace period has completed, record of that fact is propagated
back down the tree.

As can be seen from the diagram, on a 64-bit system
a two-level tree with 64 leaves can accommodate 1,024 CPUs, with a fanout
of 64 at the root and a fanout of 16 at the leaves.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| Why isn't the fanout at the leaves also 64?                           |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Because there are more types of events that affect the leaf-level     |
| ``rcu_node`` structures than further up the tree. Therefore, if the   |
| leaf ``rcu_node`` structures have fanout of 64, the contention on     |
| these structures' ``->structures`` becomes excessive. Experimentation |
| on a wide variety of systems has shown that a fanout of 16 works well |
| for the leaves of the ``rcu_node`` tree.                              |

Annotation

Implementation Notes