[PATCH tip/core/rcu 10/14] documentation: Explain why rcu_read_lock() needs no barrier()

From: Paul E. McKenney
Date: Wed Feb 24 2016 - 00:12:13 EST

Next message: Paul E. McKenney: "[PATCH tip/core/rcu 0/13] Miscellaneous fixes for 4.6"
Previous message: Paul E. McKenney: "[PATCH tip/core/rcu 02/14] documentation: Fix control dependency and identical stores"
In reply to: Paul E. McKenney: "Re: [PATCH tip/core/rcu 02/14] documentation: Fix control dependency and identical stores"
Next in thread: Paul E. McKenney: "[PATCH tip/core/rcu 09/14] documentation: Add documentation for RCU's major data structures"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

This commit adds a Quick Quiz whose answer explains why the compiler
code reordering enabled by CONFIG_PREEMPT=n's empty rcu_read_lock()
and rcu_read_unlock() functions does not hinder RCU's ability to figure
out which RCU read-side critical sections have completed and not.

Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
---
.../RCU/Design/Requirements/Requirements.html | 130 ++++++++++++++-------
.../RCU/Design/Requirements/Requirements.htmlx | 28 +++++
2 files changed, 115 insertions(+), 43 deletions(-)

diff --git a/Documentation/RCU/Design/Requirements/Requirements.html b/Documentation/RCU/Design/Requirements/Requirements.html
index 59acd82e67d4..2a56031bfdd4 100644
--- a/Documentation/RCU/Design/Requirements/Requirements.html
+++ b/Documentation/RCU/Design/Requirements/Requirements.html
@@ -583,6 +583,17 @@ The first and second guarantees require unbelievably strict ordering!
Are all these memory barriers really required?
 <a href="#qq6answer">Answer</a>

+<a name="Quick Quiz 7">Quick Quiz 7:</a>
+You claim that <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
+generate absolutely no code in some kernel builds.
+This means that the compiler might arbitrarily rearrange consecutive
+RCU read-side critical sections.
+Given such rearrangement, if a given RCU read-side critical section
+is done, how can you be sure that all prior RCU read-side critical
+sections are done?
+Won't the compiler rearrangements make that impossible to determine?
+ <a href="#qq7answer">Answer</a>
+

Note that these memory-barrier requirements do not replace the fundamental
RCU requirement that a grace period wait for all pre-existing readers.
@@ -626,9 +637,9 @@ inconvenience can be avoided through use of the
<tt>call_rcu()</tt> and <tt>kfree_rcu()</tt> API members
described later in this document.

-<a name="Quick Quiz 7">Quick Quiz 7:</a>
+<a name="Quick Quiz 8">Quick Quiz 8:</a>
But how does the upgrade-to-write operation exclude other readers?
- <a href="#qq7answer">Answer</a>
+ <a href="#qq8answer">Answer</a>


This guarantee allows lookup code to be shared between read-side
@@ -714,9 +725,9 @@ to do significant reordering.
This is by design: Any significant ordering constraints would slow down
these fast-path APIs.

-<a name="Quick Quiz 8">Quick Quiz 8:</a>
+<a name="Quick Quiz 9">Quick Quiz 9:</a>
Can't the compiler also reorder this code?
- <a href="#qq8answer">Answer</a>
+ <a href="#qq9answer">Answer</a>

<h3><a name="Readers Do Not Exclude Updaters">Readers Do Not Exclude Updaters</a></h3>

@@ -769,10 +780,10 @@ new readers can start immediately after <tt>synchronize_rcu()</tt>
starts, and <tt>synchronize_rcu()</tt> is under no
obligation to wait for these new readers.

-<a name="Quick Quiz 9">Quick Quiz 9:</a>
+<a name="Quick Quiz 10">Quick Quiz 10:</a>
Suppose that synchronize_rcu() did wait until all readers had completed.
Would the updater be able to rely on this?
- <a href="#qq9answer">Answer</a>
+ <a href="#qq10answer">Answer</a>

<h3><a name="Grace Periods Don't Partition Read-Side Critical Sections">
Grace Periods Don't Partition Read-Side Critical Sections</a></h3>
@@ -969,11 +980,11 @@ grace period.
As a result, an RCU read-side critical section cannot partition a pair
of RCU grace periods.

-<a name="Quick Quiz 10">Quick Quiz 10:</a>
+<a name="Quick Quiz 11">Quick Quiz 11:</a>
How long a sequence of grace periods, each separated by an RCU read-side
critical section, would be required to partition the RCU read-side
critical sections at the beginning and end of the chain?
- <a href="#qq10answer">Answer</a>
+ <a href="#qq11answer">Answer</a>

<h3><a name="Disabling Preemption Does Not Block Grace Periods">
Disabling Preemption Does Not Block Grace Periods</a></h3>
@@ -1127,9 +1138,9 @@ synchronization primitives be legal within RCU read-side critical sections,
including spinlocks, sequence locks, atomic operations, reference
counters, and memory barriers.

-<a name="Quick Quiz 11">Quick Quiz 11:</a>
+<a name="Quick Quiz 12">Quick Quiz 12:</a>
What about sleeping locks?
- <a href="#qq11answer">Answer</a>
+ <a href="#qq12answer">Answer</a>


It often comes as a surprise that many algorithms do not require a
@@ -1354,12 +1365,12 @@ write an RCU callback function that takes too long.
Long-running operations should be relegated to separate threads or
(in the Linux kernel) workqueues.

-<a name="Quick Quiz 12">Quick Quiz 12:</a>
+<a name="Quick Quiz 13">Quick Quiz 13:</a>
Why does line 19 use <tt>rcu_access_pointer()</tt>?
After all, <tt>call_rcu()</tt> on line 25 stores into the
structure, which would interact badly with concurrent insertions.
Doesn't this mean that <tt>rcu_dereference()</tt> is required?
- <a href="#qq12answer">Answer</a>
+ <a href="#qq13answer">Answer</a>


However, all that <tt>remove_gp_cb()</tt> is doing is
@@ -1406,14 +1417,14 @@ This was due to the fact that RCU was not heavily used within DYNIX/ptx,
so the very few places that needed something like
<tt>synchronize_rcu()</tt> simply open-coded it.

-<a name="Quick Quiz 13">Quick Quiz 13:</a>
+<a name="Quick Quiz 14">Quick Quiz 14:</a>
Earlier it was claimed that <tt>call_rcu()</tt> and
<tt>kfree_rcu()</tt> allowed updaters to avoid being blocked
by readers.
But how can that be correct, given that the invocation of the callback
and the freeing of the memory (respectively) must still wait for
a grace period to elapse?
- <a href="#qq13answer">Answer</a>
+ <a href="#qq14answer">Answer</a>


But what if the updater must wait for the completion of code to be
@@ -1838,11 +1849,11 @@ kthreads to be spawned.
Therefore, invoking <tt>synchronize_rcu()</tt> during scheduler
initialization can result in deadlock.

-<a name="Quick Quiz 14">Quick Quiz 14:</a>
+<a name="Quick Quiz 15">Quick Quiz 15:</a>
So what happens with <tt>synchronize_rcu()</tt> during
scheduler initialization for <tt>CONFIG_PREEMPT=n</tt>
kernels?
- <a href="#qq14answer">Answer</a>
+ <a href="#qq15answer">Answer</a>


I learned of these boot-time requirements as a result of a series of
@@ -2547,10 +2558,10 @@ If you needed to wait on multiple different flavors of SRCU
(but why???), you would need to create a wrapper function resembling
<tt>call_my_srcu()</tt> for each SRCU flavor.

-<a name="Quick Quiz 15">Quick Quiz 15:</a>
+<a name="Quick Quiz 16">Quick Quiz 16:</a>
But what if I need to wait for multiple RCU flavors, but I also need
the grace periods to be expedited?
- <a href="#qq15answer">Answer</a>
+ <a href="#qq16answer">Answer</a>


Again, it is usually better to adjust the RCU read-side critical sections
@@ -2827,18 +2838,51 @@ adhered to the as-if rule than it is to actually adhere to it!

<a name="qq7answer"></a>
Quick Quiz 7:
-But how does the upgrade-to-write operation exclude other readers?
+You claim that <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
+generate absolutely no code in some kernel builds.
+This means that the compiler might arbitrarily rearrange consecutive
+RCU read-side critical sections.
+Given such rearrangement, if a given RCU read-side critical section
+is done, how can you be sure that all prior RCU read-side critical
+sections are done?
+Won't the compiler rearrangements make that impossible to determine?

Answer:
-It doesn't, just like normal RCU updates, which also do not exclude
-RCU readers.
+In cases where <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
+generate absolutely no code, RCU infers quiescent states only at
+special locations, for example, within the scheduler.
+Because calls to <tt>schedule()</tt> had better prevent calling-code
+accesses to shared variables from being rearranged across the call to
+<tt>schedule()</tt>, if RCU detects the end of a given RCU read-side
+critical section, it will necessarily detect the end of all prior
+RCU read-side critical sections, no matter how aggressively the
+compiler scrambles the code.
+
+
+Again, this all assumes that the compiler cannot scramble code across
+calls to the scheduler, out of interrupt handlers, into the idle loop,
+into user-mode code, and so on.
+But if your kernel build allows that sort of scrambling, you have broken
+far more than just RCU!

<a href="#Quick%20Quiz%207">Back to Quick Quiz 7.</a>

<a name="qq8answer"></a>
Quick Quiz 8:
+But how does the upgrade-to-write operation exclude other readers?
+
+
+Answer:
+It doesn't, just like normal RCU updates, which also do not exclude
+RCU readers.
+
+
+<a href="#Quick%20Quiz%208">Back to Quick Quiz 8.</a>
+
+<a name="qq9answer"></a>
+Quick Quiz 9:
Can't the compiler also reorder this code?

@@ -2848,10 +2892,10 @@ No, the volatile casts in <tt>READ_ONCE()</tt> and
this particular case.

-<a href="#Quick%20Quiz%208">Back to Quick Quiz 8.</a>
+<a href="#Quick%20Quiz%209">Back to Quick Quiz 9.</a>

-<a name="qq9answer"></a>
-Quick Quiz 9:
+<a name="qq10answer"></a>
+Quick Quiz 10:
Suppose that synchronize_rcu() did wait until all readers had completed.
Would the updater be able to rely on this?

@@ -2866,10 +2910,10 @@ Therefore, the code following
in any case.

-<a href="#Quick%20Quiz%209">Back to Quick Quiz 9.</a>
+<a href="#Quick%20Quiz%2010">Back to Quick Quiz 10.</a>

-<a name="qq10answer"></a>
-Quick Quiz 10:
+<a name="qq11answer"></a>
+Quick Quiz 11:
How long a sequence of grace periods, each separated by an RCU read-side
critical section, would be required to partition the RCU read-side
critical sections at the beginning and end of the chain?
@@ -2883,10 +2927,10 @@ Therefore, even in practice, RCU users must abide by the theoretical rather
than the practical answer.

-<a href="#Quick%20Quiz%2010">Back to Quick Quiz 10.</a>
+<a href="#Quick%20Quiz%2011">Back to Quick Quiz 11.</a>

-<a name="qq11answer"></a>
-Quick Quiz 11:
+<a name="qq12answer"></a>
+Quick Quiz 12:
What about sleeping locks?

@@ -2914,10 +2958,10 @@ the mutex was not immediately available.
Either way, <tt>mutex_trylock()</tt> returns immediately without sleeping.

-<a href="#Quick%20Quiz%2011">Back to Quick Quiz 11.</a>
+<a href="#Quick%20Quiz%2012">Back to Quick Quiz 12.</a>

-<a name="qq12answer"></a>
-Quick Quiz 12:
+<a name="qq13answer"></a>
+Quick Quiz 13:
Why does line 19 use <tt>rcu_access_pointer()</tt>?
After all, <tt>call_rcu()</tt> on line 25 stores into the
structure, which would interact badly with concurrent insertions.
@@ -2933,10 +2977,10 @@ is released on line 25, which in turn means that
<tt>rcu_access_pointer()</tt> suffices.

-<a href="#Quick%20Quiz%2012">Back to Quick Quiz 12.</a>
+<a href="#Quick%20Quiz%2013">Back to Quick Quiz 13.</a>

-<a name="qq13answer"></a>
-Quick Quiz 13:
+<a name="qq14answer"></a>
+Quick Quiz 14:
Earlier it was claimed that <tt>call_rcu()</tt> and
<tt>kfree_rcu()</tt> allowed updaters to avoid being blocked
by readers.
@@ -2957,10 +3001,10 @@ next update as soon as it has invoked <tt>call_rcu()</tt> or
grace period.

-<a href="#Quick%20Quiz%2013">Back to Quick Quiz 13.</a>
+<a href="#Quick%20Quiz%2014">Back to Quick Quiz 14.</a>

-<a name="qq14answer"></a>
-Quick Quiz 14:
+<a name="qq15answer"></a>
+Quick Quiz 15:
So what happens with <tt>synchronize_rcu()</tt> during
scheduler initialization for <tt>CONFIG_PREEMPT=n</tt>
kernels?
@@ -2976,10 +3020,10 @@ so it is still necessary to avoid invoking <tt>synchronize_rcu()</tt>
during scheduler initialization.

-<a href="#Quick%20Quiz%2014">Back to Quick Quiz 14.</a>
+<a href="#Quick%20Quiz%2015">Back to Quick Quiz 15.</a>

-<a name="qq15answer"></a>
-Quick Quiz 15:
+<a name="qq16answer"></a>
+Quick Quiz 16:
But what if I need to wait for multiple RCU flavors, but I also need
the grace periods to be expedited?

@@ -2991,7 +3035,7 @@ But if that is nevertheless a problem, you can use workqueues or multiple
kthreads to wait on the various expedited grace periods concurrently.

-<a href="#Quick%20Quiz%2015">Back to Quick Quiz 15.</a>
+<a href="#Quick%20Quiz%2016">Back to Quick Quiz 16.</a>

</body></html>
diff --git a/Documentation/RCU/Design/Requirements/Requirements.htmlx b/Documentation/RCU/Design/Requirements/Requirements.htmlx
index 6ff4966672e2..98da30ca84c4 100644
--- a/Documentation/RCU/Design/Requirements/Requirements.htmlx
+++ b/Documentation/RCU/Design/Requirements/Requirements.htmlx
@@ -682,6 +682,34 @@ That said, it is much easier to fool yourself into believing that you have
adhered to the as-if rule than it is to actually adhere to it!
@@QQE@@

+@@QQ@@
+You claim that <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
+generate absolutely no code in some kernel builds.
+This means that the compiler might arbitrarily rearrange consecutive
+RCU read-side critical sections.
+Given such rearrangement, if a given RCU read-side critical section
+is done, how can you be sure that all prior RCU read-side critical
+sections are done?
+Won't the compiler rearrangements make that impossible to determine?
+@@QQA@@
+In cases where <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt>
+generate absolutely no code, RCU infers quiescent states only at
+special locations, for example, within the scheduler.
+Because calls to <tt>schedule()</tt> had better prevent calling-code
+accesses to shared variables from being rearranged across the call to
+<tt>schedule()</tt>, if RCU detects the end of a given RCU read-side
+critical section, it will necessarily detect the end of all prior
+RCU read-side critical sections, no matter how aggressively the
+compiler scrambles the code.
+
+
+Again, this all assumes that the compiler cannot scramble code across
+calls to the scheduler, out of interrupt handlers, into the idle loop,
+into user-mode code, and so on.
+But if your kernel build allows that sort of scrambling, you have broken
+far more than just RCU!
+@@QQE@@
+

Note that these memory-barrier requirements do not replace the fundamental
RCU requirement that a grace period wait for all pre-existing readers.
--
2.5.2

Next message: Paul E. McKenney: "[PATCH tip/core/rcu 0/13] Miscellaneous fixes for 4.6"
Previous message: Paul E. McKenney: "[PATCH tip/core/rcu 02/14] documentation: Fix control dependency and identical stores"
In reply to: Paul E. McKenney: "Re: [PATCH tip/core/rcu 02/14] documentation: Fix control dependency and identical stores"
Next in thread: Paul E. McKenney: "[PATCH tip/core/rcu 09/14] documentation: Add documentation for RCU's major data structures"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]