<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head><title>A Tour Through TREE_RCU's Data Structures [LWN.net]</title>
<meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<p>December 18, 2016</p>
<p>This article was contributed by Paul E. McKenney</p>
<h3>Introduction</h3>
This document describes RCU's major data structures and their relationship
to each other.
<ol>
<li> <a href="#Data-Structure Relationships">
Data-Structure Relationships</a>
<li> <a href="#The rcu_state Structure">
The <tt>rcu_state</tt> Structure</a>
<li> <a href="#The rcu_node Structure">
The <tt>rcu_node</tt> Structure</a>
<li> <a href="#The rcu_data Structure">
The <tt>rcu_data</tt> Structure</a>
<li> <a href="#The rcu_dynticks Structure">
The <tt>rcu_dynticks</tt> Structure</a>
<li> <a href="#The rcu_head Structure">
The <tt>rcu_head</tt> Structure</a>
<li> <a href="#RCU-Specific Fields in the task_struct Structure">
RCU-Specific Fields in the <tt>task_struct</tt> Structure</a>
<li> <a href="#Accessor Functions">
Accessor Functions</a>
</ol>
<h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
<p>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:
</p><p><img src="BigTreeClassicRCU.svg" alt="BigTreeClassicRCU.svg" width="30%">
</p><p>This diagram shows an enclosing <tt>rcu_state</tt> structure
containing a tree of <tt>rcu_node</tt> structures.
Each leaf node of the <tt>rcu_node</tt> tree has up to 16
<tt>rcu_data</tt> structures associated with it, so that there
are <tt>NR_CPUS</tt> number of <tt>rcu_data</tt> structures,
one for each possible CPU.
This structure is adjusted at boot time, if needed, to handle the
common case where <tt>nr_cpu_ids</tt> is much less than
<tt>NR_CPUs</tt>.
For example, a number of Linux distributions set <tt>NR_CPUs=4096</tt>,
which results in a three-level <tt>rcu_node</tt> tree.
If the actual hardware has only 16 CPUs, RCU will adjust itself
at boot time, resulting in an <tt>rcu_node</tt> tree with only a single node.
</p><p>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 <tt>rcu_d