Skip to content

Commit 792bf4d

Browse files
torvaldstorvalds
committed
Merge branch 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip
Pull RCU updates from Ingo Molnar: "The biggest RCU changes in this cycle were: - Convert RCU's BUG_ON() and similar calls to WARN_ON() and similar. - Replace calls of RCU-bh and RCU-sched update-side functions to their vanilla RCU counterparts. This series is a step towards complete removal of the RCU-bh and RCU-sched update-side functions. ( Note that some of these conversions are going upstream via their respective maintainers. ) - Documentation updates, including a number of flavor-consolidation updates from Joel Fernandes. - Miscellaneous fixes. - Automate generation of the initrd filesystem used for rcutorture testing. - Convert spin_is_locked() assertions to instead use lockdep. ( Note that some of these conversions are going upstream via their respective maintainers. ) - SRCU updates, especially including a fix from Dennis Krein for a bag-on-head-class bug. - RCU torture-test updates" * 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: (112 commits) rcutorture: Don't do busted forward-progress testing rcutorture: Use 100ms buckets for forward-progress callback histograms rcutorture: Recover from OOM during forward-progress tests rcutorture: Print forward-progress test age upon failure rcutorture: Print time since GP end upon forward-progress failure rcutorture: Print histogram of CB invocation at OOM time rcutorture: Print GP age upon forward-progress failure rcu: Print per-CPU callback counts for forward-progress failures rcu: Account for nocb-CPU callback counts in RCU CPU stall warnings rcutorture: Dump grace-period diagnostics upon forward-progress OOM rcutorture: Prepare for asynchronous access to rcu_fwd_startat torture: Remove unnecessary "ret" variables rcutorture: Affinity forward-progress test to avoid housekeeping CPUs rcutorture: Break up too-long rcu_torture_fwd_prog() function rcutorture: Remove cbflood facility torture: Bring any extra CPUs online during kernel startup rcutorture: Add call_rcu() flooding forward-progress tests rcutorture/formal: Replace synchronize_sched() with synchronize_rcu() tools/kernel.h: Replace synchronize_sched() with synchronize_rcu() net/decnet: Replace rcu_barrier_bh() with rcu_barrier() ...
2 parents eed9688 + 4bbfd74 commit 792bf4d

File tree

88 files changed

+4187
-4014
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

88 files changed

+4187
-4014
lines changed

‎Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg

Lines changed: 0 additions & 499 deletions
This file was deleted.

‎Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg

Lines changed: 0 additions & 695 deletions
This file was deleted.

‎Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg

Lines changed: 0 additions & 741 deletions
This file was deleted.

‎Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg

Lines changed: 319 additions & 515 deletions
Loading

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

Lines changed: 55 additions & 118 deletions
Original file line numberDiff line numberDiff line change
@@ -23,8 +23,6 @@ <h3>Introduction</h3>
2323
The <tt>rcu_segcblist</tt> Structure</a>
2424
<li> <a href="#The rcu_data Structure">
2525
The <tt>rcu_data</tt> Structure</a>
26-
<li> <a href="#The rcu_dynticks Structure">
27-
The <tt>rcu_dynticks</tt> Structure</a>
2826
<li> <a href="#The rcu_head Structure">
2927
The <tt>rcu_head</tt> Structure</a>
3028
<li> <a href="#RCU-Specific Fields in the task_struct Structure">
@@ -127,9 +125,11 @@ <h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
127125
</p><p>RCU currently permits up to a four-level tree, which on a 64-bit system
128126
accommodates up to 4,194,304 CPUs, though only a mere 524,288 CPUs for
129127
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.
128+
On the other hand, you can set both <tt>CONFIG_RCU_FANOUT</tt> and
129+
<tt>CONFIG_RCU_FANOUT_LEAF</tt> to be as small as 2, which would result
130+
in a 16-CPU test using a 4-level tree.
131+
This can be useful for testing large-system capabilities on small test
132+
machines.
133133

134134
</p><p>This multi-level combining tree allows us to get most of the
135135
performance and scalability
@@ -154,44 +154,9 @@ <h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
154154
keeping lock contention under control at all tree levels regardless
155155
of the level of loading on the system.
156156

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-
191157
</p><p>RCU updaters wait for normal grace periods by registering
192158
RCU callbacks, either directly via <tt>call_rcu()</tt> and
193159
friends (namely <tt>call_rcu_bh()</tt> and <tt>call_rcu_sched()</tt>),
194-
there being a separate interface per flavor of RCU)
195160
or indirectly via <tt>synchronize_rcu()</tt> and friends.
196161
RCU callbacks are represented by <tt>rcu_head</tt> structures,
197162
which are queued on <tt>rcu_data</tt> structures while they are
@@ -214,9 +179,6 @@ <h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
214179
<li> Each <tt>rcu_node</tt> structure has a spinlock.
215180
<li> The fields in <tt>rcu_data</tt> are private to the corresponding
216181
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.
220182
</ol>
221183

222184
<p>It is important to note that different data structures can have
@@ -272,11 +234,6 @@ <h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
272234
access to this information from the corresponding CPU.
273235
Finally, this structure records past dyntick-idle state
274236
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.
280237
<li> <tt>rcu_head</tt>:
281238
This structure represents RCU callbacks, and is the
282239
only structure allocated and managed by RCU users.
@@ -287,14 +244,14 @@ <h3><a name="Data-Structure Relationships">Data-Structure Relationships</a></h3>
287244
<p>If all you wanted from this article was a general notion of how
288245
RCU's data structures are related, you are done.
289246
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.
247+
the <tt>rcu_state</tt>, <tt>rcu_node</tt> and <tt>rcu_data</tt> data
248+
structures.
292249

293250
<h3><a name="The rcu_state Structure">
294251
The <tt>rcu_state</tt> Structure</a></h3>
295252

296253
<p>The <tt>rcu_state</tt> structure is the base structure that
297-
represents a flavor of RCU.
254+
represents the state of RCU in the system.
298255
This structure forms the interconnection between the
299256
<tt>rcu_node</tt> and <tt>rcu_data</tt> structures,
300257
tracks grace periods, contains the lock used to
@@ -389,7 +346,7 @@ <h5>Grace-Period Tracking</h5>
389346
The bottom two bits are the state of the current grace period,
390347
which can be zero for not yet started or one for in progress.
391348
In other words, if the bottom two bits of <tt>-&gt;gp_seq</tt> are
392-
zero, the corresponding flavor of RCU is idle.
349+
zero, then RCU is idle.
393350
Any other value in the bottom two bits indicates that something is broken.
394351
This field is protected by the root <tt>rcu_node</tt> structure's
395352
<tt>-&gt;lock</tt> field.
@@ -419,10 +376,10 @@ <h5>Miscellaneous</h5>
419376
grace period in jiffies.
420377
It is protected by the root <tt>rcu_node</tt>'s <tt>-&gt;lock</tt>.
421378

422-
<p>The <tt>-&gt;name</tt> field points to the name of the RCU flavor
423-
(for example, &ldquo;rcu_sched&rdquo;), and is constant.
424-
The <tt>-&gt;abbr</tt> field contains a one-character abbreviation,
425-
for example, &ldquo;s&rdquo; for RCU-sched.
379+
<p>The <tt>-&gt;name</tt> and <tt>-&gt;abbr</tt> fields distinguish
380+
between preemptible RCU (&ldquo;rcu_preempt&rdquo; and &ldquo;p&rdquo;)
381+
and non-preemptible RCU (&ldquo;rcu_sched&rdquo; and &ldquo;s&rdquo;).
382+
These fields are used for diagnostic and tracing purposes.
426383

427384
<h3><a name="The rcu_node Structure">
428385
The <tt>rcu_node</tt> Structure</a></h3>
@@ -971,25 +928,31 @@ <h3><a name="The rcu_segcblist Structure">
971928
pointer.
972929
The reason for this is that all the ready-to-invoke callbacks
973930
(that is, those in the <tt>RCU_DONE_TAIL</tt> segment) are extracted
974-
all at once at callback-invocation time.
931+
all at once at callback-invocation time (<tt>rcu_do_batch</tt>), due
932+
to which <tt>-&gt;head</tt> may be set to NULL if there are no not-done
933+
callbacks remaining in the <tt>rcu_segcblist</tt>.
975934
If callback invocation must be postponed, for example, because a
976935
high-priority process just woke up on this CPU, then the remaining
977-
callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment.
978-
Either way, the <tt>-&gt;len</tt> and <tt>-&gt;len_lazy</tt> counts
979-
are adjusted after the corresponding callbacks have been invoked, and so
980-
again it is the <tt>-&gt;len</tt> count that accurately reflects whether
981-
or not there are callbacks associated with this <tt>rcu_segcblist</tt>
982-
structure.
936+
callbacks are placed back on the <tt>RCU_DONE_TAIL</tt> segment and
937+
<tt>-&gt;head</tt> once again points to the start of the segment.
938+
In short, the head field can briefly be <tt>NULL</tt> even though the
939+
CPU has callbacks present the entire time.
940+
Therefore, it is not appropriate to test the <tt>-&gt;head</tt> pointer
941+
for <tt>NULL</tt>.
942+
943+
<p>In contrast, the <tt>-&gt;len</tt> and <tt>-&gt;len_lazy</tt> counts
944+
are adjusted only after the corresponding callbacks have been invoked.
945+
This means that the <tt>-&gt;len</tt> count is zero only if
946+
the <tt>rcu_segcblist</tt> structure really is devoid of callbacks.
983947
Of course, off-CPU sampling of the <tt>-&gt;len</tt> count requires
984-
the use of appropriate synchronization, for example, memory barriers.
948+
careful use of appropriate synchronization, for example, memory barriers.
985949
This synchronization can be a bit subtle, particularly in the case
986950
of <tt>rcu_barrier()</tt>.
987951

988952
<h3><a name="The rcu_data Structure">
989953
The <tt>rcu_data</tt> Structure</a></h3>
990954

991-
<p>The <tt>rcu_data</tt> maintains the per-CPU state for the
992-
corresponding flavor of RCU.
955+
<p>The <tt>rcu_data</tt> maintains the per-CPU state for the RCU subsystem.
993956
The fields in this structure may be accessed only from the corresponding
994957
CPU (and from tracing) unless otherwise stated.
995958
This structure is the
@@ -1015,30 +978,19 @@ <h5>Connection to Other Data Structures</h5>
1015978

1016979
<pre>
1017980
1 int cpu;
1018-
2 struct rcu_state *rsp;
1019-
3 struct rcu_node *mynode;
1020-
4 struct rcu_dynticks *dynticks;
1021-
5 unsigned long grpmask;
1022-
6 bool beenonline;
981+
2 struct rcu_node *mynode;
982+
3 unsigned long grpmask;
983+
4 bool beenonline;
1023984
</pre>
1024985

1025986
<p>The <tt>-&gt;cpu</tt> field contains the number of the
1026-
corresponding CPU, the <tt>-&gt;rsp</tt> pointer references
1027-
the corresponding <tt>rcu_state</tt> structure (and is most frequently
1028-
used to locate the name of the corresponding flavor of RCU for tracing),
1029-
and the <tt>-&gt;mynode</tt> field references the corresponding
1030-
<tt>rcu_node</tt> structure.
987+
corresponding CPU and the <tt>-&gt;mynode</tt> field references the
988+
corresponding <tt>rcu_node</tt> structure.
1031989
The <tt>-&gt;mynode</tt> is used to propagate quiescent states
1032990
up the combining tree.
1033-
<p>The <tt>-&gt;dynticks</tt> pointer references the
1034-
<tt>rcu_dynticks</tt> structure corresponding to this
1035-
CPU.
1036-
Recall that a single per-CPU instance of the <tt>rcu_dynticks</tt>
1037-
structure is shared among all flavors of RCU.
1038-
These first four fields are constant and therefore require not
1039-
synchronization.
991+
These two fields are constant and therefore do not require synchronization.
1040992

1041-
</p><p>The <tt>-&gt;grpmask</tt> field indicates the bit in
993+
<p>The <tt>-&gt;grpmask</tt> field indicates the bit in
1042994
the <tt>-&gt;mynode-&gt;qsmask</tt> corresponding to this
1043995
<tt>rcu_data</tt> structure, and is also used when propagating
1044996
quiescent states.
@@ -1057,12 +1009,12 @@ <h5>Quiescent-State and Grace-Period Tracking</h5>
10571009
3 bool cpu_no_qs;
10581010
4 bool core_needs_qs;
10591011
5 bool gpwrap;
1060-
6 unsigned long rcu_qs_ctr_snap;
10611012
</pre>
10621013

1063-
<p>The <tt>-&gt;gp_seq</tt> and <tt>-&gt;gp_seq_needed</tt>
1064-
fields are the counterparts of the fields of the same name
1065-
in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures.
1014+
<p>The <tt>-&gt;gp_seq</tt> field is the counterpart of the field of the same
1015+
name in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures. The
1016+
<tt>-&gt;gp_seq_needed</tt> field is the counterpart of the field of the same
1017+
name in the rcu_node</tt> structure.
10661018
They may each lag up to one behind their <tt>rcu_node</tt>
10671019
counterparts, but in <tt>CONFIG_NO_HZ_IDLE</tt> and
10681020
<tt>CONFIG_NO_HZ_FULL</tt> kernels can lag
@@ -1103,10 +1055,6 @@ <h5>Quiescent-State and Grace-Period Tracking</h5>
11031055
<tt>gp_seq</tt> counter is in danger of overflow, which
11041056
will cause the CPU to disregard the values of its counters on
11051057
its next exit from idle.
1106-
Finally, the <tt>rcu_qs_ctr_snap</tt> field is used to detect
1107-
cases where a given operation has resulted in a quiescent state
1108-
for all flavors of RCU, for example, <tt>cond_resched()</tt>
1109-
when RCU has indicated a need for quiescent states.
11101058

11111059
<h5>RCU Callback Handling</h5>
11121060

@@ -1179,26 +1127,22 @@ <h5>Dyntick-Idle Handling</h5>
11791127
count the number of times this CPU is determined to be in
11801128
dyntick-idle state, and is used for tracing and debugging purposes.
11811129

1182-
<h3><a name="The rcu_dynticks Structure">
1183-
The <tt>rcu_dynticks</tt> Structure</a></h3>
1184-
1185-
<p>The <tt>rcu_dynticks</tt> maintains the per-CPU dyntick-idle state
1186-
for the corresponding CPU.
1187-
Unlike the other structures, <tt>rcu_dynticks</tt> is not
1188-
replicated over the different flavors of RCU.
1189-
The fields in this structure may be accessed only from the corresponding
1190-
CPU (and from tracing) unless otherwise stated.
1191-
Its fields are as follows:
1130+
<p>
1131+
This portion of the rcu_data structure is declared as follows:
11921132

11931133
<pre>
11941134
1 long dynticks_nesting;
11951135
2 long dynticks_nmi_nesting;
11961136
3 atomic_t dynticks;
11971137
4 bool rcu_need_heavy_qs;
1198-
5 unsigned long rcu_qs_ctr;
1199-
6 bool rcu_urgent_qs;
1138+
5 bool rcu_urgent_qs;
12001139
</pre>
12011140

1141+
<p>These fields in the rcu_data structure maintain the per-CPU dyntick-idle
1142+
state for the corresponding CPU.
1143+
The fields may be accessed only from the corresponding CPU (and from tracing)
1144+
unless otherwise stated.
1145+
12021146
<p>The <tt>-&gt;dynticks_nesting</tt> field counts the
12031147
nesting depth of process execution, so that in normal circumstances
12041148
this counter has value zero or one.
@@ -1240,19 +1184,12 @@ <h3><a name="The rcu_dynticks Structure">
12401184
This flag is checked by RCU's context-switch and <tt>cond_resched()</tt>
12411185
code, which provide a momentary idle sojourn in response.
12421186

1243-
</p><p>The <tt>-&gt;rcu_qs_ctr</tt> field is used to record
1244-
quiescent states from <tt>cond_resched()</tt>.
1245-
Because <tt>cond_resched()</tt> can execute quite frequently, this
1246-
must be quite lightweight, as in a non-atomic increment of this
1247-
per-CPU field.
1248-
12491187
</p><p>Finally, the <tt>-&gt;rcu_urgent_qs</tt> field is used to record
1250-
the fact that the RCU core code would really like to see a quiescent
1251-
state from the corresponding CPU, with the various other fields indicating
1252-
just how badly RCU wants this quiescent state.
1253-
This flag is checked by RCU's context-switch and <tt>cond_resched()</tt>
1254-
code, which, if nothing else, non-atomically increment <tt>-&gt;rcu_qs_ctr</tt>
1255-
in response.
1188+
the fact that the RCU core code would really like to see a quiescent state from
1189+
the corresponding CPU, with the various other fields indicating just how badly
1190+
RCU wants this quiescent state.
1191+
This flag is checked by RCU's context-switch path
1192+
(<tt>rcu_note_context_switch</tt>) and the cond_resched code.
12561193

12571194
<table>
12581195
<tr><th>&nbsp;</th></tr>
@@ -1425,11 +1362,11 @@ <h3><a name="Accessor Functions">
14251362
<h3><a name="Summary">
14261363
Summary</a></h3>
14271364

1428-
So each flavor of RCU is represented by an <tt>rcu_state</tt> structure,
1365+
So the state of RCU is represented by an <tt>rcu_state</tt> structure,
14291366
which contains a combining tree of <tt>rcu_node</tt> and
14301367
<tt>rcu_data</tt> structures.
14311368
Finally, in <tt>CONFIG_NO_HZ_IDLE</tt> kernels, each CPU's dyntick-idle
1432-
state is tracked by an <tt>rcu_dynticks</tt> structure.
1369+
state is tracked by dynticks-related fields in the <tt>rcu_data</tt> structure.
14331370

14341371
If you made it this far, you are well prepared to read the code
14351372
walkthroughs in the other articles in this series.

0 commit comments

Comments
 (0)