<!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_segcblist Structure">
The <tt>rcu_segcblist</tt> Structure</a>
<li> <a href="#The rcu_data Structure">
The <tt>rcu_data</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