<!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>January 27, 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>
At the end we have the
<a href="#Answers to Quick Quizzes">answers to the quick quizzes</a>.
<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.