Documentation updates for 4.7
Subsystems (2)
cover Documentation updates for 4.7
Hello!
This series contains RCU documentation updates:
1. Fix sample code in whatisRCU.txt, courtesy of Yao Dongdong.
2. Add real-time requirements for CPU-bound workloads.
3. Add synchronize_rcu_mult() to the requirements.
4. Explain why rcu_read_lock() needs no barrier().
5. Document illegality of call_rcu() from offline CPUs.
6. Remove unnecessary images from requirements.
7. Get rid of duplicate .htmlx file.
8. Sharpen up the no-readers quick quiz.
9. Emphasize the call_rcu() is illegal from idle.
10. Add documentation for RCU's major data structures.
Thanx, Paul
------------------------------------------------------------------------
/Documentation/RCU/Design/Requirements/Requirements.htmlx | 2872 ---------- Documentation/RCU/Design/Requirements/RCUApplicability.svg | 237 Documentation/RCU/Design/htmlqqz.sh | 108 b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg | 474 + b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg | 499 + b/Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg | 695 ++ b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg | 741 ++ b/Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg | 858 ++ b/Documentation/RCU/Design/Data-Structures/Data-Structures.html | 1333 ++++ b/Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg | 939 +++ b/Documentation/RCU/Design/Data-Structures/TreeLevel.svg | 828 ++ b/Documentation/RCU/Design/Data-Structures/TreeMapping.svg | 305 + b/Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg | 380 + b/Documentation/RCU/Design/Data-Structures/blkd_task.svg | 843 ++ b/Documentation/RCU/Design/Data-Structures/nxtlist.svg | 396 + b/Documentation/RCU/Design/Requirements/Requirements.html | 1167 ++-- b/Documentation/RCU/Design/Requirements/Requirements.htmlx | 149 b/Documentation/RCU/whatisRCU.txt | 22 18 files changed, 9093 insertions(+), 3753 deletions(-)
PATCH 1/10 documentation: Make sample code and documentation consistent
From: Yao Dongdong <[email protected]>
In the chapter 'analogy with reader-writer locking', the sample code uses spinlock_t in reader-writer case. Just correct it so that we can read the document easily.
Signed-off-by Yao Dongdong <[email protected]>
Signed-off-by Paul E. McKenney <[email protected]>
--- Documentation/RCU/whatisRCU.txt | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
Documentation/RCU/whatisRCU.txt +15 -7
@@ -681,22 +681,30 @@ Although RCU can be used in many different ways, a very common use of RCU is analogous to reader-writer locking. The following unified diff shows how closely related RCU and reader-writer locking can be. + @@ -5,5 +5,5 @@ struct el { + int data; + /* Other data fields */ + }; + -rwlock_t listmutex; + +spinlock_t listmutex; + struct el head; + @@ -13,15 +14,15 @@ struct list_head *lp; struct el *p; - - read_lock(); + - read_lock(&listmutex); - list_for_each_entry(p, head, lp) { + rcu_read_lock(); + list_for_each_entry_rcu(p, head, lp) { if (p->key == key) { *result = p->data; - - read_unlock(); + - read_unlock(&listmutex); + rcu_read_unlock(); return 1; } } - - read_unlock(); + - read_unlock(&listmutex); + rcu_read_unlock(); return 0; }
@@ -732,7 +740,7 @@ Or, for those who prefer a side-by-side listing: 5 int data; 5 int data; 6 /* Other data fields */ 6 /* Other data fields */ 7 }; 7 }; - 8 spinlock_t listmutex; 8 spinlock_t listmutex; + 8 rwlock_t listmutex; 8 spinlock_t listmutex; 9 struct el head; 9 struct el head; 1 int search(long key, int *result) 1 int search(long key, int *result)
@@ -740,15 +748,15 @@ Or, for those who prefer a side-by-side listing: 3 struct list_head *lp; 3 struct list_head *lp; 4 struct el *p; 4 struct el *p; 5 5 - 6 read_lock(); 6 rcu_read_lock(); + 6 read_lock(&listmutex); 6 rcu_read_lock(); 7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) { 8 if (p->key == key) { 8 if (p->key == key) { 9 *result = p->data; 9 *result = p->data; -10 read_unlock(); 10 rcu_read_unlock(); +10 read_unlock(&listmutex); 10 rcu_read_unlock(); 11 return 1; 11 return 1; 12 } 12 } 13 } 13 } -14 read_unlock(); 14 rcu_read_unlock(); +14 read_unlock(&listmutex); 14 rcu_read_unlock(); 15 return 0; 15 return 0; 16 } 16 }
Signature · 1 line
2.5.2
PATCH 2/10 documentation: Add real-time requirements from CPU-bound workloads
In reply to Paul E. McKenneyThis commit records RCU's responsibility to avoid degrading latencies of CPUs running tight loops within properly configured workloads, both in kernel and in userspace.
Signed-off-by Paul E. McKenney <[email protected]>
--- Documentation/RCU/Design/Requirements/Requirements.html | 10 +++++++++- Documentation/RCU/Design/Requirements/Requirements.htmlx | 8 ++++++++ 2 files changed, 17 insertions(+), 1 deletion(-)
Documentation/RCU/Design/Requirements/Requirements.html +9 -1
@@ -1,5 +1,5 @@ <!-- DO NOT HAND EDIT. --> -<!-- Instead, edit Documentation/RCU/Design/Requirements/Requirements.htmlx and run 'sh htmlqqz.sh Documentation/RCU/Design/Requirements/Requirements' --> +<!-- Instead, edit Requirements.htmlx and run 'sh htmlqqz.sh Requirements' --> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html>
@@ -2171,6 +2171,14 @@ This real-time requirement motivated the grace-period kthread, which also simplified handling of a number of race conditions. <p> +RCU must avoid degrading real-time response for CPU-bound threads, whether +executing in usermode (which is one use case for +<tt>CONFIG_NO_HZ_FULL=y</tt>) or in the kernel. +That said, CPU-bound loops in the kernel must execute +<tt>cond_resched_rcu_qs()</tt> at least once per few tens of milliseconds +in order to avoid receiving an IPI from RCU. + +<p> Finally, RCU's status as a synchronization primitive means that any RCU failure can result in arbitrary memory corruption that can be extremely difficult to debug.
Documentation/RCU/Design/Requirements/Requirements.htmlx +8 -0
@@ -2338,6 +2338,14 @@ This real-time requirement motivated the grace-period kthread, which also simplified handling of a number of race conditions. <p> +RCU must avoid degrading real-time response for CPU-bound threads, whether +executing in usermode (which is one use case for +<tt>CONFIG_NO_HZ_FULL=y</tt>) or in the kernel. +That said, CPU-bound loops in the kernel must execute +<tt>cond_resched_rcu_qs()</tt> at least once per few tens of milliseconds +in order to avoid receiving an IPI from RCU. + +<p> Finally, RCU's status as a synchronization primitive means that any RCU failure can result in arbitrary memory corruption that can be extremely difficult to debug.
Signature · 1 line
2.5.2
PATCH 3/10 documentation: Add synchronize_rcu_mult() to the requirements
In reply to Paul E. McKenneySigned-off-by Paul E. McKenney <[email protected]>
--- .../RCU/Design/Requirements/Requirements.html | 92 ++++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 82 +++++++++++++++++++ 2 files changed, 174 insertions(+)
Documentation/RCU/Design/Requirements/Requirements.html +92 -0
@@ -2231,6 +2231,8 @@ described in a separate section. <li> <a href="#Sched Flavor">Sched Flavor</a> <li> <a href="#Sleepable RCU">Sleepable RCU</a> <li> <a href="#Tasks RCU">Tasks RCU</a> +<li> <a href="#Waiting for Multiple Grace Periods"> + Waiting for Multiple Grace Periods</a> </ol> <h3><a name="Bottom-Half Flavor">Bottom-Half Flavor</a></h3>
@@ -2480,6 +2482,81 @@ The tasks-RCU API is quite compact, consisting only of <tt>synchronize_rcu_tasks()</tt>, and <tt>rcu_barrier_tasks()</tt>. +<h3><a name="Waiting for Multiple Grace Periods"> +Waiting for Multiple Grace Periods</a></h3> + +<p> +Perhaps you have an RCU protected data structure that is accessed from +RCU read-side critical sections, from softirq handlers, and from +hardware interrupt handlers. +That is three flavors of RCU, the normal flavor, the bottom-half flavor, +and the sched flavor. +How to wait for a compound grace period? + +<p> +The best approach is usually to “just say no!” and +insert <tt>rcu_read_lock()</tt> and <tt>rcu_read_unlock()</tt> +around each RCU read-side critical section, regardless of what +environment it happens to be in. +But suppose that some of the RCU read-side critical sections are +on extremely hot code paths, and that use of <tt>CONFIG_PREEMPT=n</tt> +is not a viable option, so that <tt>rcu_read_lock()</tt> and +<tt>rcu_read_unlock()</tt> are not free. +What then? + +<p> +You <i>could</i> wait on all three grace periods in succession, as follows: + +<blockquote> +<pre> + 1 synchronize_rcu(); + 2 synchronize_rcu_bh(); + 3 synchronize_sched(); +</pre> +</blockquote> + +<p> +This works, but triples the update-side latency penalty. +In cases where this is not acceptable, <tt>synchronize_rcu_mult()</tt> +may be used to wait on all three flavors of grace period concurrently: + +<blockquote> +<pre> + 1 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched); +</pre> +</blockquote> + +<p> +But what if it is necessary to also wait on SRCU? +This can be done as follows: + +<blockquote> +<pre> + 1 static void call_my_srcu(struct rcu_head *head, + 2 void (*func)(struct rcu_head *head)) + 3 { + 4 call_srcu(&my_srcu, head, func); + 5 } + 6 + 7 synchronize_rcu_mult(call_rcu, call_rcu_bh, call_rcu_sched, call_my_srcu); +</pre> +</blockquote> + +<p> +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. + +<p><a name="Quick Quiz 15"><b>Quick Quiz 15</b>:</a> +But what if I need to wait for multiple RCU flavors, but I also need +the grace periods to be expedited? +<br><a href="#qq15answer">Answer</a> + +<p> +Again, it is usually better to adjust the RCU read-side critical sections +to use a single flavor of RCU, but when this is not feasible, you can use +<tt>synchronize_rcu_mult()</tt>. + <h2><a name="Possible Future Changes">Possible Future Changes</a></h2> <p>
@@ -2901,5 +2978,20 @@ during scheduler initialization. </p><p><a href="#Quick%20Quiz%2014"><b>Back to Quick Quiz 14</b>.</a> +<a name="qq15answer"></a> +<p><b>Quick Quiz 15</b>: +But what if I need to wait for multiple RCU flavors, but I also need +the grace periods to be expedited? + + +</p><p><b>Answer</b>: +If you are using expedited grace periods, there should be less penalty +for waiting on them in succession. +But if that is nevertheless a problem, you can use workqueues or multiple +kthreads to wait on the various expedited grace periods concurrently. + + +</p><p><a href="#Quick%20Quiz%2015"><b>Back to Quick Quiz 15</b>.</a> + </body></html>
Documentation/RCU/Design/Requirements/Requirements.htmlx +82 -0
94 lines not on this page · raw message
Signature · 1 line
2.5.2
PATCH 4/10 documentation: Explain why rcu_read_lock() needs no barrier()
In reply to Paul E. McKenneyThis 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 <[email protected]>
--- .../RCU/Design/Requirements/Requirements.html | 130 ++++++++++++++------- .../RCU/Design/Requirements/Requirements.htmlx | 28 +++++ 2 files changed, 115 insertions(+), 43 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +87 -43
@@ -583,6 +583,17 @@ The first and second guarantees require unbelievably strict ordering! Are all these memory barriers <i> really</i> required? <br><a href="#qq6answer">Answer</a> +<p><a name="Quick Quiz 7"><b>Quick Quiz 7</b>:</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? +<br><a href="#qq7answer">Answer</a> + <p> 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. -<p><a name="Quick Quiz 7"><b>Quick Quiz 7</b>:</a> +<p><a name="Quick Quiz 8"><b>Quick Quiz 8</b>:</a> But how does the upgrade-to-write operation exclude other readers? -<br><a href="#qq7answer">Answer</a> +<br><a href="#qq8answer">Answer</a> <p> 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. -<p><a name="Quick Quiz 8"><b>Quick Quiz 8</b>:</a> +<p><a name="Quick Quiz 9"><b>Quick Quiz 9</b>:</a> Can't the compiler also reorder this code? -<br><a href="#qq8answer">Answer</a> +<br><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. -<p><a name="Quick Quiz 9"><b>Quick Quiz 9</b>:</a> +<p><a name="Quick Quiz 10"><b>Quick Quiz 10</b>:</a> Suppose that synchronize_rcu() did wait until all readers had completed. Would the updater be able to rely on this? -<br><a href="#qq9answer">Answer</a> +<br><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. -<p><a name="Quick Quiz 10"><b>Quick Quiz 10</b>:</a> +<p><a name="Quick Quiz 11"><b>Quick Quiz 11</b>:</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? -<br><a href="#qq10answer">Answer</a> +<br><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. -<p><a name="Quick Quiz 11"><b>Quick Quiz 11</b>:</a> +<p><a name="Quick Quiz 12"><b>Quick Quiz 12</b>:</a> What about sleeping locks? -<br><a href="#qq11answer">Answer</a> +<br><a href="#qq12answer">Answer</a> <p> 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. -<p><a name="Quick Quiz 12"><b>Quick Quiz 12</b>:</a> +<p><a name="Quick Quiz 13"><b>Quick Quiz 13</b>:</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? -<br><a href="#qq12answer">Answer</a> +<br><a href="#qq13answer">Answer</a> <p> 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. -<p><a name="Quick Quiz 13"><b>Quick Quiz 13</b>:</a> +<p><a name="Quick Quiz 14"><b>Quick Quiz 14</b>:</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? -<br><a href="#qq13answer">Answer</a> +<br><a href="#qq14answer">Answer</a> <p> 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. -<p><a name="Quick Quiz 14"><b>Quick Quiz 14</b>:</a> +<p><a name="Quick Quiz 15"><b>Quick Quiz 15</b>:</a> So what happens with <tt>synchronize_rcu()</tt> during scheduler initialization for <tt>CONFIG_PREEMPT=n</tt> kernels? -<br><a href="#qq14answer">Answer</a> +<br><a href="#qq15answer">Answer</a> <p> 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. -<p><a name="Quick Quiz 15"><b>Quick Quiz 15</b>:</a> +<p><a name="Quick Quiz 16"><b>Quick Quiz 16</b>:</a> But what if I need to wait for multiple RCU flavors, but I also need the grace periods to be expedited? -<br><a href="#qq15answer">Answer</a> +<br><a href="#qq16answer">Answer</a> <p> 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> <p><b>Quick Quiz 7</b>: -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? </p><p><b>Answer</b>: -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. + +<p> +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! </p><p><a href="#Quick%20Quiz%207"><b>Back to Quick Quiz 7</b>.</a> <a name="qq8answer"></a> <p><b>Quick Quiz 8</b>: +But how does the upgrade-to-write operation exclude other readers? + + +</p><p><b>Answer</b>: +It doesn't, just like normal RCU updates, which also do not exclude +RCU readers. + + +</p><p><a href="#Quick%20Quiz%208"><b>Back to Quick Quiz 8</b>.</a> + +<a name="qq9answer"></a> +<p><b>Quick Quiz 9</b>: 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. -</p><p><a href="#Quick%20Quiz%208"><b>Back to Quick Quiz 8</b>.</a> +</p><p><a href="#Quick%20Quiz%209"><b>Back to Quick Quiz 9</b>.</a> -<a name="qq9answer"></a> -<p><b>Quick Quiz 9</b>: +<a name="qq10answer"></a> +<p><b>Quick Quiz 10</b>: 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. -</p><p><a href="#Quick%20Quiz%209"><b>Back to Quick Quiz 9</b>.</a> +</p><p><a href="#Quick%20Quiz%2010"><b>Back to Quick Quiz 10</b>.</a> -<a name="qq10answer"></a> -<p><b>Quick Quiz 10</b>: +<a name="qq11answer"></a> +<p><b>Quick Quiz 11</b>: 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. -</p><p><a href="#Quick%20Quiz%2010"><b>Back to Quick Quiz 10</b>.</a> +</p><p><a href="#Quick%20Quiz%2011"><b>Back to Quick Quiz 11</b>.</a> -<a name="qq11answer"></a> -<p><b>Quick Quiz 11</b>: +<a name="qq12answer"></a> +<p><b>Quick Quiz 12</b>: What about sleeping locks?
@@ -2914,10 +2958,10 @@ the mutex was not immediately available. Either way, <tt>mutex_trylock()</tt> returns immediately without sleeping. -</p><p><a href="#Quick%20Quiz%2011"><b>Back to Quick Quiz 11</b>.</a> +</p><p><a href="#Quick%20Quiz%2012"><b>Back to Quick Quiz 12</b>.</a> -<a name="qq12answer"></a> -<p><b>Quick Quiz 12</b>: +<a name="qq13answer"></a> +<p><b>Quick Quiz 13</b>: 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. -</p><p><a href="#Quick%20Quiz%2012"><b>Back to Quick Quiz 12</b>.</a> +</p><p><a href="#Quick%20Quiz%2013"><b>Back to Quick Quiz 13</b>.</a> -<a name="qq13answer"></a> -<p><b>Quick Quiz 13</b>: +<a name="qq14answer"></a> +<p><b>Quick Quiz 14</b>: 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. -</p><p><a href="#Quick%20Quiz%2013"><b>Back to Quick Quiz 13</b>.</a> +</p><p><a href="#Quick%20Quiz%2014"><b>Back to Quick Quiz 14</b>.</a> -<a name="qq14answer"></a> -<p><b>Quick Quiz 14</b>: +<a name="qq15answer"></a> +<p><b>Quick Quiz 15</b>: 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. -</p><p><a href="#Quick%20Quiz%2014"><b>Back to Quick Quiz 14</b>.</a> +</p><p><a href="#Quick%20Quiz%2015"><b>Back to Quick Quiz 15</b>.</a> -<a name="qq15answer"></a> -<p><b>Quick Quiz 15</b>: +<a name="qq16answer"></a> +<p><b>Quick Quiz 16</b>: 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. -</p><p><a href="#Quick%20Quiz%2015"><b>Back to Quick Quiz 15</b>.</a> +</p><p><a href="#Quick%20Quiz%2016"><b>Back to Quick Quiz 16</b>.</a> </body></html>
Documentation/RCU/Design/Requirements/Requirements.htmlx +28 -0
@@ -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! <p>@@QQE@@ +<p>@@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? +<p>@@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. + +<p> +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! +<p>@@QQE@@ + <p> Note that these memory-barrier requirements do not replace the fundamental RCU requirement that a grace period wait for all pre-existing readers.
Signature · 1 line
2.5.2
PATCH 5/10 documentation: Document illegality of call_rcu() from offline CPUs
In reply to Paul E. McKenneyThere is already a blanket statement about no member of RCU's API being legal from an offline CPU, but add an explicit note where it states that it is illegal to invoke call_rcu() from an NMI handler.
Signed-off-by Paul E. McKenney <[email protected]>
--- Documentation/RCU/Design/Requirements/Requirements.html | 3 ++- Documentation/RCU/Design/Requirements/Requirements.htmlx | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +2 -1
@@ -1354,7 +1354,8 @@ situations where neither <tt>synchronize_rcu()</tt> nor <tt>synchronize_rcu_expedited()</tt> would be legal, including within preempt-disable code, <tt>local_bh_disable()</tt> code, interrupt-disable code, and interrupt handlers. -However, even <tt>call_rcu()</tt> is illegal within NMI handlers. +However, even <tt>call_rcu()</tt> is illegal within NMI handlers +and from offline CPUs. The callback function (<tt>remove_gp_cb()</tt> in this case) will be executed within softirq (software interrupt) environment within the Linux kernel,
Documentation/RCU/Design/Requirements/Requirements.htmlx +2 -1
@@ -1513,7 +1513,8 @@ situations where neither <tt>synchronize_rcu()</tt> nor <tt>synchronize_rcu_expedited()</tt> would be legal, including within preempt-disable code, <tt>local_bh_disable()</tt> code, interrupt-disable code, and interrupt handlers. -However, even <tt>call_rcu()</tt> is illegal within NMI handlers. +However, even <tt>call_rcu()</tt> is illegal within NMI handlers +and from offline CPUs. The callback function (<tt>remove_gp_cb()</tt> in this case) will be executed within softirq (software interrupt) environment within the Linux kernel,
Signature · 1 line
2.5.2
PATCH 6/10 documentation: Remove unnecessary images from requirements
In reply to Paul E. McKenneyThis commit removes a cutesy cartoon and also a diagram that can just as easily be represented by text.
Reported-by Linus Torvalds <[email protected]>
Signed-off-by Paul E. McKenney <[email protected]>
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 100825 -> 0 bytes .../RCU/Design/Requirements/RCUApplicability.svg | 237 --------------------- .../RCU/Design/Requirements/Requirements.html | 28 ++- .../RCU/Design/Requirements/Requirements.htmlx | 28 ++- 4 files changed, 40 insertions(+), 253 deletions(-) delete mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png delete mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg
Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png deleted binary +0 -0
Documentation/RCU/Design/Requirements/RCUApplicability.svg deleted +0 -237
237 lines not on this page · raw message
Documentation/RCU/Design/Requirements/Requirements.html +20 -8
@@ -1120,12 +1120,27 @@ These classes is covered in the following sections. <h3><a name="Specialization">Specialization</a></h3> <p> -RCU is and always has been intended primarily for read-mostly situations, as -illustrated by the following figure. -This means that RCU's read-side primitives are optimized, often at the +RCU is and always has been intended primarily for read-mostly situations, +which means that RCU's read-side primitives are optimized, often at the expense of its update-side primitives. +Experience thus far is captured by the following list of situations: -<p><img src="RCUApplicability.svg" alt="RCUApplicability.svg" width="70%"></p> +<ol> +<li> Read-mostly data, where stale and inconsistent data is not + a problem: RCU works great! +<li> Read-mostly data, where data must be consistent: + RCU works well. +<li> Read-write data, where data must be consistent: + RCU <i>might</i> work OK. + Or not. +<li> Write-mostly data, where data must be consistent: + RCU is very unlikely to be the right tool for the job, + with the following exceptions, where RCU can provide: + <ol type=a> + <li> Existence guarantees for update-friendly mechanisms. + <li> Wait-free read-side primitives for real-time use. + </ol> +</ol> <p> This focus on read-mostly situations means that RCU must interoperate
@@ -1171,10 +1186,7 @@ some period of time, so the exact wait period is a judgment call. One of our pair of veternarians might wait 30 seconds before pronouncing the cat dead, while the other might insist on waiting a full minute. The two veternarians would then disagree on the state of the cat during -the final 30 seconds of the minute following the last heartbeat, as -fancifully illustrated below: - -<p><img src="2013-08-is-it-dead.png" alt="2013-08-is-it-dead.png" width="431"></p> +the final 30 seconds of the minute following the last heartbeat. <p> Interestingly enough, this same situation applies to hardware.
Documentation/RCU/Design/Requirements/Requirements.htmlx +20 -8
@@ -1257,12 +1257,27 @@ These classes is covered in the following sections. <h3><a name="Specialization">Specialization</a></h3> <p> -RCU is and always has been intended primarily for read-mostly situations, as -illustrated by the following figure. -This means that RCU's read-side primitives are optimized, often at the +RCU is and always has been intended primarily for read-mostly situations, +which means that RCU's read-side primitives are optimized, often at the expense of its update-side primitives. +Experience thus far is captured by the following list of situations: -<p><img src="RCUApplicability.svg" alt="RCUApplicability.svg" width="70%"></p> +<ol> +<li> Read-mostly data, where stale and inconsistent data is not + a problem: RCU works great! +<li> Read-mostly data, where data must be consistent: + RCU works well. +<li> Read-write data, where data must be consistent: + RCU <i>might</i> work OK. + Or not. +<li> Write-mostly data, where data must be consistent: + RCU is very unlikely to be the right tool for the job, + with the following exceptions, where RCU can provide: + <ol type=a> + <li> Existence guarantees for update-friendly mechanisms. + <li> Wait-free read-side primitives for real-time use. + </ol> +</ol> <p> This focus on read-mostly situations means that RCU must interoperate
@@ -1330,10 +1345,7 @@ some period of time, so the exact wait period is a judgment call. One of our pair of veternarians might wait 30 seconds before pronouncing the cat dead, while the other might insist on waiting a full minute. The two veternarians would then disagree on the state of the cat during -the final 30 seconds of the minute following the last heartbeat, as -fancifully illustrated below: - -<p><img src="2013-08-is-it-dead.png" alt="2013-08-is-it-dead.png" width="431"></p> +the final 30 seconds of the minute following the last heartbeat. <p> Interestingly enough, this same situation applies to hardware.
Signature · 1 line
2.5.2
PATCH 7/10 documentation: Get rid of duplicate .htmlx file
In reply to Paul E. McKenneyThis commit uses colors to obscure the quick-quiz answers, thus getting rid of the .htmlx file. Use your mouse to select the answer in order to see the text. Alternatively, use your favorite scripting language to remove all occurences of "<font color="ffffff">" from the file.
Reported-by Linus Torvalds <[email protected]>
Signed-off-by Paul E. McKenney <[email protected]>
--- .../RCU/Design/Requirements/Requirements.html | 889 +++--- .../RCU/Design/Requirements/Requirements.htmlx | 2872 -------------------- Documentation/RCU/Design/htmlqqz.sh | 108 - 3 files changed, 428 insertions(+), 3441 deletions(-) delete mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlx delete mode 100755 Documentation/RCU/Design/htmlqqz.sh
Documentation/RCU/Design/Requirements/Requirements.html +428 -461
@@ -1,5 +1,3 @@ -<!-- DO NOT HAND EDIT. --> -<!-- Instead, edit Requirements.htmlx and run 'sh htmlqqz.sh Requirements' --> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html>
@@ -65,8 +63,8 @@ All that aside, here are the categories of currently known RCU requirements: <p> This is followed by a <a href="#Summary">summary</a>, -which is in turn followed by the inevitable -<a href="#Answers to Quick Quizzes">answers to the quick quizzes</a>. +however, the answers to each quick quiz immediately follows the quiz. +Select the big white space with your mouse to see the answer. <h2><a name="Fundamental Requirements">Fundamental Requirements</a></h2>
@@ -153,13 +151,27 @@ Therefore, the outcome: </blockquote> cannot happen. -<p><a name="Quick Quiz 1"><b>Quick Quiz 1</b>:</a> -Wait a minute! -You said that updaters can make useful forward progress concurrently -with readers, but pre-existing readers will block -<tt>synchronize_rcu()</tt>!!! -Just who are you trying to fool??? -<br><a href="#qq1answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Wait a minute! + You said that updaters can make useful forward progress concurrently + with readers, but pre-existing readers will block + <tt>synchronize_rcu()</tt>!!! + Just who are you trying to fool??? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + First, if updaters do not wish to be blocked by readers, they can use + <tt>call_rcu()</tt> or <tt>kfree_rcu()</tt>, which will + be discussed later. + Second, even when using <tt>synchronize_rcu()</tt>, the other + update-side code does run concurrently with readers, whether + pre-existing or not. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> This scenario resembles one of the first uses of RCU in
@@ -210,9 +222,20 @@ to guarantee that <tt>do_something()</tt> never runs concurrently with <tt>recovery()</tt>, but with little or no synchronization overhead in <tt>do_something_dlm()</tt>. -<p><a name="Quick Quiz 2"><b>Quick Quiz 2</b>:</a> -Why is the <tt>synchronize_rcu()</tt> on line 28 needed? -<br><a href="#qq2answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Why is the <tt>synchronize_rcu()</tt> on line 28 needed? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Without that extra grace period, memory reordering could result in + <tt>do_something_dlm()</tt> executing <tt>do_something()</tt> + concurrently with the last bits of <tt>recovery()</tt>. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> In order to avoid fatal problems such as deadlocks,
@@ -332,12 +355,27 @@ It also prevents any number of “interesting” compiler optimizations, for example, the use of <tt>gp</tt> as a scratch location immediately preceding the assignment. -<p><a name="Quick Quiz 3"><b>Quick Quiz 3</b>:</a> -But <tt>rcu_assign_pointer()</tt> does nothing to prevent the -two assignments to <tt>p->a</tt> and <tt>p->b</tt> -from being reordered. -Can't that also cause problems? -<br><a href="#qq3answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + But <tt>rcu_assign_pointer()</tt> does nothing to prevent the + two assignments to <tt>p->a</tt> and <tt>p->b</tt> + from being reordered. + Can't that also cause problems? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + No, it cannot. + The readers cannot see either of these two fields until + the assignment to <tt>gp</tt>, by which time both fields are + fully initialized. + So reordering the assignments + to <tt>p->a</tt> and <tt>p->b</tt> cannot possibly + cause any problems. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> It is tempting to assume that the reader need not do anything special
@@ -494,11 +532,42 @@ The <tt>rcu_access_pointer()</tt> on line 6 is similar to code protected by the corresponding update-side lock. </ol> -<p><a name="Quick Quiz 4"><b>Quick Quiz 4</b>:</a> -Without the <tt>rcu_dereference()</tt> or the -<tt>rcu_access_pointer()</tt>, what destructive optimizations -might the compiler make use of? -<br><a href="#qq4answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Without the <tt>rcu_dereference()</tt> or the + <tt>rcu_access_pointer()</tt>, what destructive optimizations + might the compiler make use of? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Let's start with what happens to <tt>do_something_gp()</tt> + if it fails to use <tt>rcu_dereference()</tt>. + It could reuse a value formerly fetched from this same pointer. + It could also fetch the pointer from <tt>gp</tt> in a byte-at-a-time + manner, resulting in <i>load tearing</i>, in turn resulting a bytewise + mash-up of two distince pointer values. + It might even use value-speculation optimizations, where it makes + a wrong guess, but by the time it gets around to checking the + value, an update has changed the pointer to match the wrong guess. + Too bad about any dereferences that returned pre-initialization garbage + in the meantime! + </font> + + <p><font color="ffffff"> + For <tt>remove_gp_synchronous()</tt>, as long as all modifications + to <tt>gp</tt> are carried out while holding <tt>gp_lock</tt>, + the above optimizations are harmless. + However, + with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt>, + <tt>sparse</tt> will complain if you + define <tt>gp</tt> with <tt>__rcu</tt> and then + access it without using + either <tt>rcu_access_pointer()</tt> or <tt>rcu_dereference()</tt>. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> In short, RCU's publish-subscribe guarantee is provided by the combination
@@ -571,28 +640,156 @@ systems with more than one CPU: <tt>synchronize_rcu()</tt> migrates in the meantime. </ol> -<p><a name="Quick Quiz 5"><b>Quick Quiz 5</b>:</a> -Given that multiple CPUs can start RCU read-side critical sections -at any time without any ordering whatsoever, how can RCU possibly tell whether -or not a given RCU read-side critical section starts before a -given instance of <tt>synchronize_rcu()</tt>? -<br><a href="#qq5answer">Answer</a> - -<p><a name="Quick Quiz 6"><b>Quick Quiz 6</b>:</a> -The first and second guarantees require unbelievably strict ordering! -Are all these memory barriers <i> really</i> required? -<br><a href="#qq6answer">Answer</a> - -<p><a name="Quick Quiz 7"><b>Quick Quiz 7</b>:</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? -<br><a href="#qq7answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Given that multiple CPUs can start RCU read-side critical sections + at any time without any ordering whatsoever, how can RCU possibly + tell whether or not a given RCU read-side critical section starts + before a given instance of <tt>synchronize_rcu()</tt>? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + If RCU cannot tell whether or not a given + RCU read-side critical section starts before a + given instance of <tt>synchronize_rcu()</tt>, + then it must assume that the RCU read-side critical section + started first. + In other words, a given instance of <tt>synchronize_rcu()</tt> + can avoid waiting on a given RCU read-side critical section only + if it can prove that <tt>synchronize_rcu()</tt> started first. +</font></td></tr> +<tr><td> </td></tr> +</table> + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + The first and second guarantees require unbelievably strict ordering! + Are all these memory barriers <i> really</i> required? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Yes, they really are required. + To see why the first guarantee is required, consider the following + sequence of events: + </font> + + <ol> + <li> <font color="ffffff"> + CPU 1: <tt>rcu_read_lock()</tt> + </font> + <li> <font color="ffffff"> + CPU 1: <tt>q = rcu_dereference(gp); + /* Very likely to return p. */</tt> + </font> + <li> <font color="ffffff"> + CPU 0: <tt>list_del_rcu(p);</tt> + </font> + <li> <font color="ffffff"> + CPU 0: <tt>synchronize_rcu()</tt> starts. + </font> + <li> <font color="ffffff"> + CPU 1: <tt>do_something_with(q->a); + /* No smp_mb(), so might happen after kfree(). */</tt> + </font> + <li> <font color="ffffff"> + CPU 1: <tt>rcu_read_unlock()</tt> + </font> + <li> <font color="ffffff"> + CPU 0: <tt>synchronize_rcu()</tt> returns. + </font> + <li> <font color="ffffff"> + CPU 0: <tt>kfree(p);</tt> + </font> + </ol> + + <p><font color="ffffff"> + Therefore, there absolutely must be a full memory barrier between the + end of the RCU read-side critical section and the end of the + grace period. + </font> + + <p><font color="ffffff"> + The sequence of events demonstrating the necessity of the second rule + is roughly similar: + </font> + + <ol> + <li> <font color="ffffff">CPU 0: <tt>list_del_rcu(p);</tt> + </font> + <li> <font color="ffffff">CPU 0: <tt>synchronize_rcu()</tt> starts. + </font> + <li> <font color="ffffff">CPU 1: <tt>rcu_read_lock()</tt> + </font> + <li> <font color="ffffff">CPU 1: <tt>q = rcu_dereference(gp); + /* Might return p if no memory barrier. */</tt> + </font> + <li> <font color="ffffff">CPU 0: <tt>synchronize_rcu()</tt> returns. + </font> + <li> <font color="ffffff">CPU 0: <tt>kfree(p);</tt> + </font> + <li> <font color="ffffff"> + CPU 1: <tt>do_something_with(q->a); /* Boom!!! */</tt> + </font> + <li> <font color="ffffff">CPU 1: <tt>rcu_read_unlock()</tt> + </font> + </ol> + + <p><font color="ffffff"> + And similarly, without a memory barrier between the beginning of the + grace period and the beginning of the RCU read-side critical section, + CPU 1 might end up accessing the freelist. + </font> + + <p><font color="ffffff"> + The “as if” rule of course applies, so that any + implementation that acts as if the appropriate memory barriers + were in place is a correct implementation. + 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! +</font></td></tr> +<tr><td> </td></tr> +</table> + +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + 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? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + 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. + </font> + + <p><font color="ffffff"> + 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! +</font></td></tr> +<tr><td> </td></tr> +</table> <p> Note that these memory-barrier requirements do not replace the fundamental
@@ -637,9 +834,19 @@ inconvenience can be avoided through use of the <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt> API members described later in this document. -<p><a name="Quick Quiz 8"><b>Quick Quiz 8</b>:</a> -But how does the upgrade-to-write operation exclude other readers? -<br><a href="#qq8answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + But how does the upgrade-to-write operation exclude other readers? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + It doesn't, just like normal RCU updates, which also do not exclude + RCU readers. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> This guarantee allows lookup code to be shared between read-side
@@ -725,9 +932,20 @@ to do significant reordering. This is by design: Any significant ordering constraints would slow down these fast-path APIs. -<p><a name="Quick Quiz 9"><b>Quick Quiz 9</b>:</a> -Can't the compiler also reorder this code? -<br><a href="#qq9answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Can't the compiler also reorder this code? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + No, the volatile casts in <tt>READ_ONCE()</tt> and + <tt>WRITE_ONCE()</tt> prevent the compiler from reordering in + this particular case. +</font></td></tr> +<tr><td> </td></tr> +</table> <h3><a name="Readers Do Not Exclude Updaters">Readers Do Not Exclude Updaters</a></h3>
@@ -780,10 +998,25 @@ 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. -<p><a name="Quick Quiz 10"><b>Quick Quiz 10</b>:</a> -Suppose that synchronize_rcu() did wait until all readers had completed. -Would the updater be able to rely on this? -<br><a href="#qq10answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + Suppose that synchronize_rcu() did wait until all readers had completed. + Would the updater be able to rely on this? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + No. + Even if <tt>synchronize_rcu()</tt> were to wait until + all readers had completed, a new reader might start immediately after + <tt>synchronize_rcu()</tt> completed. + Therefore, the code following + <tt>synchronize_rcu()</tt> cannot rely on there being no readers + in any case. +</font></td></tr> +<tr><td> </td></tr> +</table> <h3><a name="Grace Periods Don't Partition Read-Side Critical Sections"> Grace Periods Don't Partition Read-Side Critical Sections</a></h3>
@@ -980,11 +1213,24 @@ grace period. As a result, an RCU read-side critical section cannot partition a pair of RCU grace periods. -<p><a name="Quick Quiz 11"><b>Quick Quiz 11</b>:</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? -<br><a href="#qq11answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + 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? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + In theory, an infinite number. + In practice, an unknown number that is sensitive to both implementation + details and timing considerations. + Therefore, even in practice, RCU users must abide by the + theoretical rather than the practical answer. +</font></td></tr> +<tr><td> </td></tr> +</table> <h3><a name="Disabling Preemption Does Not Block Grace Periods"> Disabling Preemption Does Not Block Grace Periods</a></h3>
@@ -1153,9 +1399,43 @@ synchronization primitives be legal within RCU read-side critical sections, including spinlocks, sequence locks, atomic operations, reference counters, and memory barriers. -<p><a name="Quick Quiz 12"><b>Quick Quiz 12</b>:</a> -What about sleeping locks? -<br><a href="#qq12answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + What about sleeping locks? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + These are forbidden within Linux-kernel RCU read-side critical + sections because it is not legal to place a quiescent state + (in this case, voluntary context switch) within an RCU read-side + critical section. + However, sleeping locks may be used within userspace RCU read-side + critical sections, and also within Linux-kernel sleepable RCU + <a href="#Sleepable RCU"><font color="ffffff">(SRCU)</font></a> + read-side critical sections. + In addition, the -rt patchset turns spinlocks into a + sleeping locks so that the corresponding critical sections + can be preempted, which also means that these sleeplockified + spinlocks (but not other sleeping locks!) may be acquire within + -rt-Linux-kernel RCU read-side critical sections. + </font> + + <p><font color="ffffff"> + Note that it <i>is</i> legal for a normal RCU read-side + critical section to conditionally acquire a sleeping locks + (as in <tt>mutex_trylock()</tt>), but only as long as it does + not loop indefinitely attempting to conditionally acquire that + sleeping locks. + The key point is that things like <tt>mutex_trylock()</tt> + either return with the mutex held, or return an error indication if + the mutex was not immediately available. + Either way, <tt>mutex_trylock()</tt> returns immediately without + sleeping. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> It often comes as a surprise that many algorithms do not require a
@@ -1378,12 +1658,27 @@ write an RCU callback function that takes too long. Long-running operations should be relegated to separate threads or (in the Linux kernel) workqueues. -<p><a name="Quick Quiz 13"><b>Quick Quiz 13</b>:</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? -<br><a href="#qq13answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + 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? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + Presumably the <tt>->gp_lock</tt> acquired on line 18 excludes + any changes, including any insertions that <tt>rcu_dereference()</tt> + would protect against. + Therefore, any insertions will be delayed until after + <tt>->gp_lock</tt> + is released on line 25, which in turn means that + <tt>rcu_access_pointer()</tt> suffices. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> However, all that <tt>remove_gp_cb()</tt> is doing is
@@ -1430,14 +1725,31 @@ 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. -<p><a name="Quick Quiz 14"><b>Quick Quiz 14</b>:</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? -<br><a href="#qq14answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + 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? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + We could define things this way, but keep in mind that this sort of + definition would say that updates in garbage-collected languages + cannot complete until the next time the garbage collector runs, + which does not seem at all reasonable. + The key point is that in most cases, an updater using either + <tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> can proceed to the + next update as soon as it has invoked <tt>call_rcu()</tt> or + <tt>kfree_rcu()</tt>, without having to wait for a subsequent + grace period. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> But what if the updater must wait for the completion of code to be
@@ -1862,11 +2174,26 @@ kthreads to be spawned. Therefore, invoking <tt>synchronize_rcu()</tt> during scheduler initialization can result in deadlock. -<p><a name="Quick Quiz 15"><b>Quick Quiz 15</b>:</a> -So what happens with <tt>synchronize_rcu()</tt> during -scheduler initialization for <tt>CONFIG_PREEMPT=n</tt> -kernels? -<br><a href="#qq15answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + So what happens with <tt>synchronize_rcu()</tt> during + scheduler initialization for <tt>CONFIG_PREEMPT=n</tt> + kernels? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + In <tt>CONFIG_PREEMPT=n</tt> kernel, <tt>synchronize_rcu()</tt> + maps directly to <tt>synchronize_sched()</tt>. + Therefore, <tt>synchronize_rcu()</tt> works normally throughout + boot in <tt>CONFIG_PREEMPT=n</tt> kernels. + However, your code must also work in <tt>CONFIG_PREEMPT=y</tt> kernels, + so it is still necessary to avoid invoking <tt>synchronize_rcu()</tt> + during scheduler initialization. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> I learned of these boot-time requirements as a result of a series of
@@ -2571,10 +2898,23 @@ 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. -<p><a name="Quick Quiz 16"><b>Quick Quiz 16</b>:</a> -But what if I need to wait for multiple RCU flavors, but I also need -the grace periods to be expedited? -<br><a href="#qq16answer">Answer</a> +<table> +<tr><th> </th></tr> +<tr><th align="left">Quick Quiz:</th></tr> +<tr><td> + But what if I need to wait for multiple RCU flavors, but I also need + the grace periods to be expedited? +</td></tr> +<tr><th align="left">Answer:</th></tr> +<tr><td bgcolor="#ffffff"><font color="ffffff"> + If you are using expedited grace periods, there should be less penalty + for waiting on them in succession. + But if that is nevertheless a problem, you can use workqueues + or multiple kthreads to wait on the various expedited grace + periods concurrently. +</font></td></tr> +<tr><td> </td></tr> +</table> <p> Again, it is usually better to adjust the RCU read-side critical sections
@@ -2678,377 +3018,4 @@ and is provided under the terms of the Creative Commons Attribution-Share Alike 3.0 United States license. -<h3><a name="Answers to Quick Quizzes"> -Answers to Quick Quizzes</a></h3> - -<a name="qq1answer"></a> -<p><b>Quick Quiz 1</b>: -Wait a minute! -You said that updaters can make useful forward progress concurrently -with readers, but pre-existing readers will block -<tt>synchronize_rcu()</tt>!!! -Just who are you trying to fool??? - - -</p><p><b>Answer</b>: -First, if updaters do not wish to be blocked by readers, they can use -<tt>call_rcu()</tt> or <tt>kfree_rcu()</tt>, which will -be discussed later. -Second, even when using <tt>synchronize_rcu()</tt>, the other -update-side code does run concurrently with readers, whether pre-existing -or not. - - -</p><p><a href="#Quick%20Quiz%201"><b>Back to Quick Quiz 1</b>.</a> - -<a name="qq2answer"></a> -<p><b>Quick Quiz 2</b>: -Why is the <tt>synchronize_rcu()</tt> on line 28 needed? - - -</p><p><b>Answer</b>: -Without that extra grace period, memory reordering could result in -<tt>do_something_dlm()</tt> executing <tt>do_something()</tt> -concurrently with the last bits of <tt>recovery()</tt>. - - -</p><p><a href="#Quick%20Quiz%202"><b>Back to Quick Quiz 2</b>.</a> - -<a name="qq3answer"></a> -<p><b>Quick Quiz 3</b>: -But <tt>rcu_assign_pointer()</tt> does nothing to prevent the -two assignments to <tt>p->a</tt> and <tt>p->b</tt> -from being reordered. -Can't that also cause problems? - - -</p><p><b>Answer</b>: -No, it cannot. -The readers cannot see either of these two fields until -the assignment to <tt>gp</tt>, by which time both fields are -fully initialized. -So reordering the assignments -to <tt>p->a</tt> and <tt>p->b</tt> cannot possibly -cause any problems. - - -</p><p><a href="#Quick%20Quiz%203"><b>Back to Quick Quiz 3</b>.</a> - -<a name="qq4answer"></a> -<p><b>Quick Quiz 4</b>: -Without the <tt>rcu_dereference()</tt> or the -<tt>rcu_access_pointer()</tt>, what destructive optimizations -might the compiler make use of? - - -</p><p><b>Answer</b>: -Let's start with what happens to <tt>do_something_gp()</tt> -if it fails to use <tt>rcu_dereference()</tt>. -It could reuse a value formerly fetched from this same pointer. -It could also fetch the pointer from <tt>gp</tt> in a byte-at-a-time -manner, resulting in <i>load tearing</i>, in turn resulting a bytewise -mash-up of two distince pointer values. -It might even use value-speculation optimizations, where it makes a wrong -guess, but by the time it gets around to checking the value, an update -has changed the pointer to match the wrong guess. -Too bad about any dereferences that returned pre-initialization garbage -in the meantime! - -<p> -For <tt>remove_gp_synchronous()</tt>, as long as all modifications -to <tt>gp</tt> are carried out while holding <tt>gp_lock</tt>, -the above optimizations are harmless. -However, -with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt>, -<tt>sparse</tt> will complain if you -define <tt>gp</tt> with <tt>__rcu</tt> and then -access it without using -either <tt>rcu_access_pointer()</tt> or <tt>rcu_dereference()</tt>. - - -</p><p><a href="#Quick%20Quiz%204"><b>Back to Quick Quiz 4</b>.</a> - -<a name="qq5answer"></a> -<p><b>Quick Quiz 5</b>: -Given that multiple CPUs can start RCU read-side critical sections -at any time without any ordering whatsoever, how can RCU possibly tell whether -or not a given RCU read-side critical section starts before a -given instance of <tt>synchronize_rcu()</tt>? - - -</p><p><b>Answer</b>: -If RCU cannot tell whether or not a given -RCU read-side critical section starts before a -given instance of <tt>synchronize_rcu()</tt>, -then it must assume that the RCU read-side critical section -started first. -In other words, a given instance of <tt>synchronize_rcu()</tt> -can avoid waiting on a given RCU read-side critical section only -if it can prove that <tt>synchronize_rcu()</tt> started first. - - -</p><p><a href="#Quick%20Quiz%205"><b>Back to Quick Quiz 5</b>.</a> - -<a name="qq6answer"></a> -<p><b>Quick Quiz 6</b>: -The first and second guarantees require unbelievably strict ordering! -Are all these memory barriers <i> really</i> required? - - -</p><p><b>Answer</b>: -Yes, they really are required. -To see why the first guarantee is required, consider the following -sequence of events: - -<ol> -<li> CPU 1: <tt>rcu_read_lock()</tt> -<li> CPU 1: <tt>q = rcu_dereference(gp); - /* Very likely to return p. */</tt> -<li> CPU 0: <tt>list_del_rcu(p);</tt> -<li> CPU 0: <tt>synchronize_rcu()</tt> starts. -<li> CPU 1: <tt>do_something_with(q->a); - /* No smp_mb(), so might happen after kfree(). */</tt> -<li> CPU 1: <tt>rcu_read_unlock()</tt> -<li> CPU 0: <tt>synchronize_rcu()</tt> returns. -<li> CPU 0: <tt>kfree(p);</tt> -</ol> - -<p> -Therefore, there absolutely must be a full memory barrier between the -end of the RCU read-side critical section and the end of the -grace period. - -<p> -The sequence of events demonstrating the necessity of the second rule -is roughly similar: - -<ol> -<li> CPU 0: <tt>list_del_rcu(p);</tt> -<li> CPU 0: <tt>synchronize_rcu()</tt> starts. -<li> CPU 1: <tt>rcu_read_lock()</tt> -<li> CPU 1: <tt>q = rcu_dereference(gp); - /* Might return p if no memory barrier. */</tt> -<li> CPU 0: <tt>synchronize_rcu()</tt> returns. -<li> CPU 0: <tt>kfree(p);</tt> -<li> CPU 1: <tt>do_something_with(q->a); /* Boom!!! */</tt> -<li> CPU 1: <tt>rcu_read_unlock()</tt> -</ol> - -<p> -And similarly, without a memory barrier between the beginning of the -grace period and the beginning of the RCU read-side critical section, -CPU 1 might end up accessing the freelist. - -<p> -The “as if” rule of course applies, so that any implementation -that acts as if the appropriate memory barriers were in place is a -correct implementation. -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! - - -</p><p><a href="#Quick%20Quiz%206"><b>Back to Quick Quiz 6</b>.</a> - -<a name="qq7answer"></a> -<p><b>Quick Quiz 7</b>: -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? - - -</p><p><b>Answer</b>: -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. - -<p> -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! - - -</p><p><a href="#Quick%20Quiz%207"><b>Back to Quick Quiz 7</b>.</a> - -<a name="qq8answer"></a> -<p><b>Quick Quiz 8</b>: -But how does the upgrade-to-write operation exclude other readers? - - -</p><p><b>Answer</b>: -It doesn't, just like normal RCU updates, which also do not exclude -RCU readers. - - -</p><p><a href="#Quick%20Quiz%208"><b>Back to Quick Quiz 8</b>.</a> - -<a name="qq9answer"></a> -<p><b>Quick Quiz 9</b>: -Can't the compiler also reorder this code? - - -</p><p><b>Answer</b>: -No, the volatile casts in <tt>READ_ONCE()</tt> and -<tt>WRITE_ONCE()</tt> prevent the compiler from reordering in -this particular case. - - -</p><p><a href="#Quick%20Quiz%209"><b>Back to Quick Quiz 9</b>.</a> - -<a name="qq10answer"></a> -<p><b>Quick Quiz 10</b>: -Suppose that synchronize_rcu() did wait until all readers had completed. -Would the updater be able to rely on this? - - -</p><p><b>Answer</b>: -No. -Even if <tt>synchronize_rcu()</tt> were to wait until -all readers had completed, a new reader might start immediately after -<tt>synchronize_rcu()</tt> completed. -Therefore, the code following -<tt>synchronize_rcu()</tt> cannot rely on there being no readers -in any case. - - -</p><p><a href="#Quick%20Quiz%2010"><b>Back to Quick Quiz 10</b>.</a> - -<a name="qq11answer"></a> -<p><b>Quick Quiz 11</b>: -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? - - -</p><p><b>Answer</b>: -In theory, an infinite number. -In practice, an unknown number that is sensitive to both implementation -details and timing considerations. -Therefore, even in practice, RCU users must abide by the theoretical rather -than the practical answer. - - -</p><p><a href="#Quick%20Quiz%2011"><b>Back to Quick Quiz 11</b>.</a> - -<a name="qq12answer"></a> -<p><b>Quick Quiz 12</b>: -What about sleeping locks? - - -</p><p><b>Answer</b>: -These are forbidden within Linux-kernel RCU read-side critical sections -because it is not legal to place a quiescent state (in this case, -voluntary context switch) within an RCU read-side critical section. -However, sleeping locks may be used within userspace RCU read-side critical -sections, and also within Linux-kernel sleepable RCU -<a href="#Sleepable RCU">(SRCU)</a> -read-side critical sections. -In addition, the -rt patchset turns spinlocks into a sleeping locks so -that the corresponding critical sections can be preempted, which -also means that these sleeplockified spinlocks (but not other sleeping locks!) -may be acquire within -rt-Linux-kernel RCU read-side critical sections. - -<p> -Note that it <i>is</i> legal for a normal RCU read-side critical section -to conditionally acquire a sleeping locks (as in <tt>mutex_trylock()</tt>), -but only as long as it does not loop indefinitely attempting to -conditionally acquire that sleeping locks. -The key point is that things like <tt>mutex_trylock()</tt> -either return with the mutex held, or return an error indication if -the mutex was not immediately available. -Either way, <tt>mutex_trylock()</tt> returns immediately without sleeping. - - -</p><p><a href="#Quick%20Quiz%2012"><b>Back to Quick Quiz 12</b>.</a> - -<a name="qq13answer"></a> -<p><b>Quick Quiz 13</b>: -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? - - -</p><p><b>Answer</b>: -Presumably the <tt>->gp_lock</tt> acquired on line 18 excludes -any changes, including any insertions that <tt>rcu_dereference()</tt> -would protect against. -Therefore, any insertions will be delayed until after <tt>->gp_lock</tt> -is released on line 25, which in turn means that -<tt>rcu_access_pointer()</tt> suffices. - - -</p><p><a href="#Quick%20Quiz%2013"><b>Back to Quick Quiz 13</b>.</a> - -<a name="qq14answer"></a> -<p><b>Quick Quiz 14</b>: -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? - - -</p><p><b>Answer</b>: -We could define things this way, but keep in mind that this sort of -definition would say that updates in garbage-collected languages -cannot complete until the next time the garbage collector runs, -which does not seem at all reasonable. -The key point is that in most cases, an updater using either -<tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> can proceed to the -next update as soon as it has invoked <tt>call_rcu()</tt> or -<tt>kfree_rcu()</tt>, without having to wait for a subsequent -grace period. - - -</p><p><a href="#Quick%20Quiz%2014"><b>Back to Quick Quiz 14</b>.</a> - -<a name="qq15answer"></a> -<p><b>Quick Quiz 15</b>: -So what happens with <tt>synchronize_rcu()</tt> during -scheduler initialization for <tt>CONFIG_PREEMPT=n</tt> -kernels? - - -</p><p><b>Answer</b>: -In <tt>CONFIG_PREEMPT=n</tt> kernel, <tt>synchronize_rcu()</tt> -maps directly to <tt>synchronize_sched()</tt>. -Therefore, <tt>synchronize_rcu()</tt> works normally throughout -boot in <tt>CONFIG_PREEMPT=n</tt> kernels. -However, your code must also work in <tt>CONFIG_PREEMPT=y</tt> kernels, -so it is still necessary to avoid invoking <tt>synchronize_rcu()</tt> -during scheduler initialization. - - -</p><p><a href="#Quick%20Quiz%2015"><b>Back to Quick Quiz 15</b>.</a> - -<a name="qq16answer"></a> -<p><b>Quick Quiz 16</b>: -But what if I need to wait for multiple RCU flavors, but I also need -the grace periods to be expedited? - - -</p><p><b>Answer</b>: -If you are using expedited grace periods, there should be less penalty -for waiting on them in succession. -But if that is nevertheless a problem, you can use workqueues or multiple -kthreads to wait on the various expedited grace periods concurrently. - - -</p><p><a href="#Quick%20Quiz%2016"><b>Back to Quick Quiz 16</b>.</a> - - </body></html>
Documentation/RCU/Design/Requirements/Requirements.htmlx deleted +0 -2872
2,014 lines not on this page · raw message
Documentation/RCU/Design/htmlqqz.sh deleted +0 -108
108 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.5.2
Part of the diff is not shown here. View the raw message.
PATCH 8/10 documentation: Sharpen up the no-readers quick quiz
In reply to Paul E. McKenneySigned-off-by Paul E. McKenney <[email protected]>
--- Documentation/RCU/Design/Requirements/Requirements.html | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +8 -5
@@ -1002,18 +1002,21 @@ obligation to wait for these new readers. <tr><th> </th></tr> <tr><th align="left">Quick Quiz:</th></tr> <tr><td> - Suppose that synchronize_rcu() did wait until all readers had completed. - Would the updater be able to rely on this? + Suppose that synchronize_rcu() did wait until <i>all</i> + readers had completed instead of waiting only on + pre-existing readers. + For how long would the updater be able to rely on there + being no readers? </td></tr> <tr><th align="left">Answer:</th></tr> <tr><td bgcolor="#ffffff"><font color="ffffff"> - No. + For no time at all. Even if <tt>synchronize_rcu()</tt> were to wait until all readers had completed, a new reader might start immediately after <tt>synchronize_rcu()</tt> completed. Therefore, the code following - <tt>synchronize_rcu()</tt> cannot rely on there being no readers - in any case. + <tt>synchronize_rcu()</tt> can <i>never</i> rely on there being + no readers. </font></td></tr> <tr><td> </td></tr> </table>
Signature · 1 line
2.5.2
PATCH 9/10 documentation: Emphasize the call_rcu() is illegal from idle
In reply to Paul E. McKenneyAlthough call_rcu()'s fastpath works just fine on an idle CPU, some branches of the slowpath invoke the scheduler, which uses RCU. Therefore, this commit emphasizes the fact that call_rcu() must not be invoked from an idle CPU.
Signed-off-by Paul E. McKenney <[email protected]>
--- Documentation/RCU/Design/Requirements/Requirements.html | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/Design/Requirements/Requirements.html +1 -1
@@ -1650,7 +1650,7 @@ situations where neither <tt>synchronize_rcu()</tt> nor including within preempt-disable code, <tt>local_bh_disable()</tt> code, interrupt-disable code, and interrupt handlers. However, even <tt>call_rcu()</tt> is illegal within NMI handlers -and from offline CPUs. +and from idle and offline CPUs. The callback function (<tt>remove_gp_cb()</tt> in this case) will be executed within softirq (software interrupt) environment within the Linux kernel,
Signature · 1 line
2.5.2
PATCH 10/10 documentation: Add documentation for RCU's major data structures
In reply to Paul E. McKenneyThis commit adds documentation for RCU's major data structures, including rcu_state, rcu_node, rcu_data, rcu_dynticks, and rcu_head.
Signed-off-by Paul E. McKenney <[email protected]>
--- .../Design/Data-Structures/BigTreeClassicRCU.svg | 474 +++++++ .../Design/Data-Structures/BigTreeClassicRCUBH.svg | 499 ++++++++ .../Data-Structures/BigTreeClassicRCUBHdyntick.svg | 695 ++++++++++ .../Data-Structures/BigTreePreemptRCUBHdyntick.svg | 741 +++++++++++ .../BigTreePreemptRCUBHdyntickCB.svg | 858 +++++++++++++ .../Design/Data-Structures/Data-Structures.html | 1333 ++++++++++++++++++++ .../Design/Data-Structures/HugeTreeClassicRCU.svg | 939 ++++++++++++++ .../RCU/Design/Data-Structures/TreeLevel.svg | 828 ++++++++++++ .../RCU/Design/Data-Structures/TreeMapping.svg | 305 +++++ .../Design/Data-Structures/TreeMappingLevel.svg | 380 ++++++ .../RCU/Design/Data-Structures/blkd_task.svg | 843 +++++++++++++ .../RCU/Design/Data-Structures/nxtlist.svg | 396 ++++++ 12 files changed, 8291 insertions(+) create mode 100644 Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg create mode 100644 Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg create mode 100644 Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg create mode 100644 Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg create mode 100644 Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg create mode 100644 Documentation/RCU/Design/Data-Structures/Data-Structures.html create mode 100644 Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg create mode 100644 Documentation/RCU/Design/Data-Structures/TreeLevel.svg create mode 100644 Documentation/RCU/Design/Data-Structures/TreeMapping.svg create mode 100644 Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg create mode 100644 Documentation/RCU/Design/Data-Structures/blkd_task.svg create mode 100644 Documentation/RCU/Design/Data-Structures/nxtlist.svg
Documentation/RCU/Design/Data-Structures/BigTreeClassicRCU.svg new file +474 -0
@@ -0,0 +1,474 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!-- Creator: fig2dev Version 3.2 Patchlevel 5e --> + +<!-- CreationDate: Wed Dec 9 17:28:20 2015 --> + +<!-- Magnification: 3.000 --> + +<svg + xmlns:dc="http://purl.org/dc/elements/1.1/" + xmlns:cc="http://creativecommons.org/ns#" + xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" + xmlns:svg="http://www.w3.org/2000/svg" + xmlns="http://www.w3.org/2000/svg" + xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" + xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" + width="9.1in" + height="8.9in" + viewBox="-66 -66 10932 10707" + id="svg2" + version="1.1" + inkscape:version="0.48.4 r9939" + sodipodi:docname="BigTreeClassicRCU.fig"> + <metadata + id="metadata106"> + <rdf:RDF> + <cc:Work + rdf:about=""> + <dc:format>image/svg+xml</dc:format> + <dc:type + rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> + <dc:title></dc:title> + </cc:Work> + </rdf:RDF> + </metadata> + <defs + id="defs104"> + <marker + inkscape:stockid="Arrow1Mend" + orient="auto" + refY="0.0" + refX="0.0" + id="Arrow1Mend" + style="overflow:visible;"> + <path + id="path3864" + d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " + style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;" + transform="scale(0.4) rotate(180) translate(10,0)" /> + </marker> + </defs> + <sodipodi:namedview + pagecolor="#ffffff" + bordercolor="#666666" + borderopacity="1" + objecttolerance="10" + gridtolerance="10" + guidetolerance="10" + inkscape:pageopacity="0" + inkscape:pageshadow="2" + inkscape:window-width="973" + inkscape:window-height="1137" + id="namedview102" + showgrid="false" + inkscape:zoom="0.9743589" + inkscape:cx="409.50003" + inkscape:cy="400.49997" + inkscape:window-x="915" + inkscape:window-y="24" + inkscape:window-maximized="0" + inkscape:current-layer="g4" /> + <g + style="stroke-width:.025in; fill:none" + id="g4"> + <!-- Line: box --> + <rect + x="0" + y="0" + width="10800" + height="5625" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffff00; " + id="rect6" /> + <!-- Line: box --> + <rect + x="1125" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect8" /> + <!-- Line: box --> + <rect + x="3825" + y="900" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect10" /> + <!-- Line: box --> + <rect + x="6525" + y="3600" + width="2700" + height="1350" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; fill:#ffbfbf; " + id="rect12" /> + <!-- Line --> + <polyline + points="3375,6525 3375,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline14" /> + <!-- Arrowhead on XXXpoint 3375 6525 - 3375 4860--> + <!-- Circle --> + <circle + cx="7425" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle18" /> + <!-- Circle --> + <circle + cx="7875" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle20" /> + <!-- Circle --> + <circle + cx="8325" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle22" /> + <!-- Circle --> + <circle + cx="2025" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle24" /> + <!-- Circle --> + <circle + cx="2475" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle26" /> + <!-- Circle --> + <circle + cx="2925" + cy="6075" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle28" /> + <!-- Circle --> + <circle + cx="4725" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle30" /> + <!-- Circle --> + <circle + cx="5175" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle32" /> + <!-- Circle --> + <circle + cx="5625" + cy="4275" + r="114" + style="fill:#000000;stroke:#000000;stroke-width:21;" + id="circle34" /> + <!-- Line: box --> + <rect + x="2025" + y="6525" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect36" /> + <!-- Line --> + <polyline + points="2475,3600 3975,2310 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline38" /> + <!-- Arrowhead on XXXpoint 2475 3600 - 4116 2190--> + <!-- Line --> + <polyline + points="7875,3600 6372,2310 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline42" /> + <!-- Arrowhead on XXXpoint 7875 3600 - 6231 2190--> + <!-- Line --> + <polyline + points="6975,8775 6975,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline46" /> + <!-- Arrowhead on XXXpoint 6975 8775 - 6975 4860--> + <!-- Line --> + <polyline + points="1575,8775 1575,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline50" /> + <!-- Arrowhead on XXXpoint 1575 8775 - 1575 4860--> + <!-- Line --> + <polyline + points="8775,6525 8775,5046 " + style="stroke:#00d1d1;stroke-width:44.9934641;stroke-linejoin:miter;stroke-linecap:butt;stroke-miterlimit:4;stroke-dasharray:none;marker-end:url(#Arrow1Mend)" + id="polyline54" /> + <!-- Arrowhead on XXXpoint 8775 6525 - 8775 4860--> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="9225" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text58">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="9675" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text60">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="1575" + y="10350" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text62">CPU 0</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="6975" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text64">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="7425" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text66">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="3375" + y="8100" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text68">CPU 15</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="9225" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text70">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="9675" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text72">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="6975" + y="10350" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text74">CPU 1007</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="6930" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text76">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="7380" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text78">rcu_data</text> + <!-- Text --> + <text + xml:space="preserve" + x="8730" + y="8055" + fill="#000000" + font-family="Helvetica" + font-style="normal" + font-weight="normal" + font-size="324" + text-anchor="middle" + id="text80">CPU 1023</text> + <!-- Text --> + <text + xml:space="preserve" + x="225" + y="450" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="start" + id="text82">struct rcu_state</text> + <!-- Text --> + <text + xml:space="preserve" + x="2475" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text84">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="2475" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text86">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="7875" + y="4500" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text88">rcu_node</text> + <!-- Text --> + <text + xml:space="preserve" + x="7875" + y="4050" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text90">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5175" + y="1350" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text92">struct</text> + <!-- Text --> + <text + xml:space="preserve" + x="5175" + y="1800" + fill="#000000" + font-family="Courier" + font-style="normal" + font-weight="bold" + font-size="288" + text-anchor="middle" + id="text94">rcu_node</text> + <!-- Line: box --> + <rect + x="225" + y="8775" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect96" /> + <!-- Line: box --> + <rect + x="5625" + y="8775" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect98" /> + <!-- Line: box --> + <rect + x="7380" + y="6480" + width="2700" + height="1800" + rx="0" + style="stroke:#000000;stroke-width:45; stroke-linejoin:miter; stroke-linecap:butt; " + id="rect100" /> + </g> +</svg>
Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBH.svg new file +499 -0
499 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/BigTreeClassicRCUBHdyntick.svg new file +695 -0
695 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntick.svg new file +741 -0
741 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/BigTreePreemptRCUBHdyntickCB.svg new file +858 -0
591 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/Data-Structures.html new file +1333 -0
1,333 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/HugeTreeClassicRCU.svg new file +939 -0
939 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/TreeLevel.svg new file +828 -0
828 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/TreeMapping.svg new file +305 -0
305 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/TreeMappingLevel.svg new file +380 -0
380 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/blkd_task.svg new file +843 -0
843 lines not on this page · raw message
Documentation/RCU/Design/Data-Structures/nxtlist.svg new file +396 -0
396 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.5.2
Part of the diff is not shown here. View the raw message.
Re: [PATCH tip/core/rcu 10/10] documentation: Add documentation for RCU's major data structures
Hi Paul,
Quoted 3 lines · Paul E. McKenney
This commit adds documentation for RCU's major data structures, including
rcu_state,rcu_node,rcu_data,rcu_dynticks, andrcu_head.
One small thing, you are using term TREE_PREEMPT_RCU throughout the whole document, while I think it has been removed in commit 28f6569ab7d03 ("rcu: Remove redundant TREE_PREEMPT_RCU config option").
so, a "s/TREE_PREEMPT_RCU/PREEMPT_RCU" makes the document more up to date?
Regards,
Boqun
Quoted 2 lines
Signed-off-by Paul E. McKenney <[email protected]>---
[...]
Re: [PATCH tip/core/rcu 10/10] documentation: Add documentation for RCU's major data structures
Quoted 7 lines · Boqun Feng
Hi Paul,
Quoted 3 lines · Paul E. McKenney
This commit adds documentation for RCU's major data structures, including
rcu_state,rcu_node,rcu_data,rcu_dynticks, andrcu_head.
Quoted 6 lines
One small thing, you are using term
TREE_PREEMPT_RCUthroughout the whole document, while I think it has been removed in commit28f6569ab7d03("rcu: Remove redundantTREE_PREEMPT_RCUconfig option").so, a "s/TREE_PREEMPT_RCU/PREEMPT_RCU" makes the document more up to date?
Good catch, will fix!
Thanx, Paul
Quoted 6 lines
Regards,
BoqunQuoted 2 lines
Signed-off-by Paul E. McKenney <[email protected]>---
[...]