Documentation updates for 4.5
Subsystems (3)
cover Documentation updates for 4.5
Hello!
This series contains documentation updates, perhaps most notably a first installment of RCU design documentation, which first appeared on LWN
(http://lwn.net/Articles/652156/, http://lwn.net/Articles/652677/, and
http://lwn.net/Articles/653326/). The individual patches are as follows:
1. Add RCU requirements design document.
2-7. Updates to the RCU requirements.
8. Fix memory-barrier.txt typo, courtesy of Chris Metcalf.
Thanx, Paul
------------------------------------------------------------------------
b/Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg | 374 + b/Documentation/RCU/Design/Requirements/RCUApplicability.svg | 237 b/Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg | 639 ++ b/Documentation/RCU/Design/Requirements/Requirements.html | 2967 +++++++++- b/Documentation/RCU/Design/Requirements/Requirements.htmlx | 2809 +++++++++ b/Documentation/RCU/Design/htmlqqz.sh | 108 b/Documentation/memory-barriers.txt | 8 7 files changed, 7069 insertions(+), 73 deletions(-)
PATCH 1/8 documentation: Record RCU requirements
This commit adds RCU requirements as published in a 2015 LWN series. Bringing these requirements in-tree allows them to be updated as changes are discovered.
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 0 -> 100825 bytes .../Design/Requirements/GPpartitionReaders1.svg | 374 +++ .../RCU/Design/Requirements/RCUApplicability.svg | 237 ++ .../Design/Requirements/ReadersPartitionGP1.svg | 639 +++++ .../RCU/Design/Requirements/Requirements.html | 2799 ++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 2643 ++++++++++++++++++ Documentation/RCU/Design/htmlqqz.sh | 108 + 7 files changed, 6800 insertions(+) create mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png create mode 100644 Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg create mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg create mode 100644 Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg create mode 100644 Documentation/RCU/Design/Requirements/Requirements.html create mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlx create mode 100755 Documentation/RCU/Design/htmlqqz.sh
Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png new file binary +0 -0
Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg new file +374 -0
374 lines not on this page · raw message
Documentation/RCU/Design/Requirements/RCUApplicability.svg new file +237 -0
237 lines not on this page · raw message
Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg new file +639 -0
639 lines not on this page · raw message
Documentation/RCU/Design/Requirements/Requirements.html new file +2799 -0
1,750 lines not on this page · raw message
Documentation/RCU/Design/Requirements/Requirements.htmlx new file +2643 -0
2,643 lines not on this page · raw message
Documentation/RCU/Design/htmlqqz.sh new file +108 -0
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.
Josh Triplett
maintainerRe: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 5 lines · Paul E. McKenney
This commit adds RCU requirements as published in a 2015 LWN series. Bringing these requirements in-tree allows them to be updated as changes are discovered.
Signed-off-by Paul E. McKenney <[email protected]>
Quoted 15 lines
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 0 -> 100825 bytes .../Design/Requirements/GPpartitionReaders1.svg | 374 +++ .../RCU/Design/Requirements/RCUApplicability.svg | 237 ++ .../Design/Requirements/ReadersPartitionGP1.svg | 639 +++++ .../RCU/Design/Requirements/Requirements.html | 2799 ++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 2643 ++++++++++++++++++ Documentation/RCU/Design/htmlqqz.sh | 108 + 7 files changed, 6800 insertions(+) create mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png create mode 100644 Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg create mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg create mode 100644 Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg create mode 100644 Documentation/RCU/Design/Requirements/Requirements.html create mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlx
If Requirements.html is machine-generated and shouldn't be hand-edited, and it can be generated without any special tools, then I don't think it should be committed in the tree; I'd suggest putting it in .gitignore and generating it from one of the various "make docs" invocations.
Alternatively, if you want to make sure a usable version is in-tree, you could make the script reversible (easy enough to do if the compiled version includes some marker comments or similar), and then tell people to run it in reverse mode, edit, and run it in forward mode. Then you don't need the .htmlx file at all. :)
Re: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 22 lines · Josh Triplett
Quoted 5 lines · Paul E. McKenney
This commit adds RCU requirements as published in a 2015 LWN series. Bringing these requirements in-tree allows them to be updated as changes are discovered.
Signed-off-by Paul E. McKenney <[email protected]>Quoted 15 lines
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 0 -> 100825 bytes .../Design/Requirements/GPpartitionReaders1.svg | 374 +++ .../RCU/Design/Requirements/RCUApplicability.svg | 237 ++ .../Design/Requirements/ReadersPartitionGP1.svg | 639 +++++ .../RCU/Design/Requirements/Requirements.html | 2799 ++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 2643 ++++++++++++++++++ Documentation/RCU/Design/htmlqqz.sh | 108 + 7 files changed, 6800 insertions(+) create mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png create mode 100644 Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg create mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg create mode 100644 Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg create mode 100644 Documentation/RCU/Design/Requirements/Requirements.html create mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlx
Quoted 4 lines
If Requirements.html is machine-generated and shouldn't be hand-edited, and it can be generated without any special tools, then I don't think it should be committed in the tree; I'd suggest putting it in .gitignore and generating it from one of the various "make docs" invocations.
I considered doing that, but then decided that it is nice for people to be able train their browser directly on the file without having to know what scripts to run.
Hmmm... I suppose I could construct a Makefile that dealt with that though... I will give this some thought, and if it looks good, I will add the Makefiles and "git rm" the .htmlx files.
Quoted 5 lines
Alternatively, if you want to make sure a usable version is in-tree, you could make the script reversible (easy enough to do if the compiled version includes some marker comments or similar), and then tell people to run it in reverse mode, edit, and run it in forward mode. Then you don't need the .htmlx file at all. :)
Decades ago, back when I (against all evidence) believed I could consistently avoid making stupid mistakes, you might have been able to convince me that this was a good idea. ;-)
Thanx, Paul
Josh Triplett
maintainerRe: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 42 lines · Paul E. McKenney
Quoted 22 lines · Josh Triplett
Quoted 5 lines · Paul E. McKenney
This commit adds RCU requirements as published in a 2015 LWN series. Bringing these requirements in-tree allows them to be updated as changes are discovered.
Signed-off-by Paul E. McKenney <[email protected]>Quoted 15 lines
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 0 -> 100825 bytes .../Design/Requirements/GPpartitionReaders1.svg | 374 +++ .../RCU/Design/Requirements/RCUApplicability.svg | 237 ++ .../Design/Requirements/ReadersPartitionGP1.svg | 639 +++++ .../RCU/Design/Requirements/Requirements.html | 2799 ++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 2643 ++++++++++++++++++ Documentation/RCU/Design/htmlqqz.sh | 108 + 7 files changed, 6800 insertions(+) create mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png create mode 100644 Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg create mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg create mode 100644 Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg create mode 100644 Documentation/RCU/Design/Requirements/Requirements.html create mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlxQuoted 4 lines
If Requirements.html is machine-generated and shouldn't be hand-edited, and it can be generated without any special tools, then I don't think it should be committed in the tree; I'd suggest putting it in .gitignore and generating it from one of the various "make docs" invocations.
I considered doing that, but then decided that it is nice for people to be able train their browser directly on the file without having to know what scripts to run.
Hmmm... I suppose I could construct a
Makefilethat dealt with that though... I will give this some thought, and if it looks good, I will add the Makefiles and "git rm" the .htmlx files.Quoted 5 lines
Alternatively, if you want to make sure a usable version is in-tree, you could make the script reversible (easy enough to do if the compiled version includes some marker comments or similar), and then tell people to run it in reverse mode, edit, and run it in forward mode. Then you don't need the .htmlx file at all. :)
Quoted 3 lines
Decades ago, back when I (against all evidence) believed I could consistently avoid making stupid mistakes, you might have been able to convince me that this was a good idea. ;-)
Because you don't want to complicate the script, or because you don't want to accidentally edit the wrong version? (Note that a carefully written script would mean it doesn't matter which version you edit.)
A third alternative would be to include the answers inline right after the questions, and optionally add a tiny bit of JavaScript that hides them by default and lets you click to show the answer. :)
Re: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 43 lines · Josh Triplett
Quoted 42 lines · Paul E. McKenney
Quoted 22 lines · Josh Triplett
Quoted 5 lines · Paul E. McKenney
This commit adds RCU requirements as published in a 2015 LWN series. Bringing these requirements in-tree allows them to be updated as changes are discovered.
Signed-off-by Paul E. McKenney <[email protected]>Quoted 15 lines
--- .../RCU/Design/Requirements/2013-08-is-it-dead.png | Bin 0 -> 100825 bytes .../Design/Requirements/GPpartitionReaders1.svg | 374 +++ .../RCU/Design/Requirements/RCUApplicability.svg | 237 ++ .../Design/Requirements/ReadersPartitionGP1.svg | 639 +++++ .../RCU/Design/Requirements/Requirements.html | 2799 ++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 2643 ++++++++++++++++++ Documentation/RCU/Design/htmlqqz.sh | 108 + 7 files changed, 6800 insertions(+) create mode 100644 Documentation/RCU/Design/Requirements/2013-08-is-it-dead.png create mode 100644 Documentation/RCU/Design/Requirements/GPpartitionReaders1.svg create mode 100644 Documentation/RCU/Design/Requirements/RCUApplicability.svg create mode 100644 Documentation/RCU/Design/Requirements/ReadersPartitionGP1.svg create mode 100644 Documentation/RCU/Design/Requirements/Requirements.html create mode 100644 Documentation/RCU/Design/Requirements/Requirements.htmlxQuoted 4 lines
If Requirements.html is machine-generated and shouldn't be hand-edited, and it can be generated without any special tools, then I don't think it should be committed in the tree; I'd suggest putting it in .gitignore and generating it from one of the various "make docs" invocations.
I considered doing that, but then decided that it is nice for people to be able train their browser directly on the file without having to know what scripts to run.
Hmmm... I suppose I could construct a
Makefilethat dealt with that though... I will give this some thought, and if it looks good, I will add the Makefiles and "git rm" the .htmlx files.Quoted 5 lines
Alternatively, if you want to make sure a usable version is in-tree, you could make the script reversible (easy enough to do if the compiled version includes some marker comments or similar), and then tell people to run it in reverse mode, edit, and run it in forward mode. Then you don't need the .htmlx file at all. :)
Quoted 7 lines
Quoted 3 lines
Decades ago, back when I (against all evidence) believed I could consistently avoid making stupid mistakes, you might have been able to convince me that this was a good idea. ;-)
Because you don't want to complicate the script, or because you don't want to accidentally edit the wrong version? (Note that a carefully written script would mean it doesn't matter which version you edit.)
I prefer the simpler script.
Quoted 3 lines
A third alternative would be to include the answers inline right after the questions, and optionally add a tiny bit of JavaScript that hides them by default and lets you click to show the answer. :)
That does have some advantages. I would welcome a patch that added the JavaScript.
Thanx, Paul
Re: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 1 line · Paul E. McKenney
On Fri, Dec 04, 2015 at 04:38:42PM -0800, Josh Triplett wrote:
[ . . . ]
Quoted 4 lines
Quoted 3 lines
Because you don't want to complicate the script, or because you don't want to accidentally edit the wrong version? (Note that a carefully written script would mean it doesn't matter which version you edit.)
Quoted 8 lines
I prefer the simpler script.
Quoted 3 lines
A third alternative would be to include the answers inline right after the questions, and optionally add a tiny bit of JavaScript that hides them by default and lets you click to show the answer. :)
That does have some advantages. I would welcome a patch that added the JavaScript.
And I did try a CSS approach with this CSS definition:
<style media="screen" type="text/css">
.quick-quiz-wrap {
position: relative;
}
.quick-quiz-wrap .quick-quiz-content {
display: none;
position: absolute;
bottom: -10px;
left: 10px;
right: 10px;
background-color: lightgrey;
padding: 20px;
}
.quick-quiz-wrap:hover .quick-quiz-content {
display: block;
}
</style>I linked to this as follows:
<link rel="stylesheet" type="text/css" href="../quick-quiz.css" media="screen">
And used it like this:
<p><b>Quick Quiz:</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>
<div class="quick-quiz-wrap">
<b>Quick Quiz Answer</b>
<div class="quick-quiz-content">
<p>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.
</div>
</div>
This proved fragile. It worked in trivial cases, but with non-trivial content in a non-trivial document, it refused to show anything on mouse hover. Even in trivial cases, it sometimes made strange choices on where to display the text. At this point, I drop back to the old-school scripted approach. It has the advantage of working consistently and providing good user experience, with the HTML unconditionally present. ;-)
Thanx, Paul
Josh Triplett
maintainerRe: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
In reply to Paul E. McKenneyThe content of the document seems fine; a few comments below on meta-issues.
Documentation/RCU/Design/Requirements/Requirements.html line 4
Quoted 7 lines · Paul E. McKenney
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0@@ -0,0 +1,2799 @@ +<!-- 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">
Nit: these days, this should just be:
<!doctype html>
Documentation/RCU/Design/Requirements/Requirements.html line 7
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+ <html> + <head><title>A Tour Through RCU's Requirements [LWN.net]</title> + <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
Is there a good reason to not use charset=utf-8 here?
Documentation/RCU/Design/Requirements/Requirements.html line 11
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0+ +<h1>A Tour Through RCU's Requirements</h1> + +<p>Copyright IBM Corporation, 2015</p>
If you're aiming for a properly formatted copyright notice, the year typically comes first, followed by the copyright holder. That said, your corporate guidelines presumably have a specific format; is this that format?
Documentation/RCU/Design/Requirements/Requirements.html line 17
Quoted 6 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +6
-0+<p>Author: Paul E. McKenney</p> +<p><i>The initial version of this document appeared in the +<a href="http://lwn.net/">LWN</a> articles +<a href="http://lwn.net/Articles/652156/">here</a>, +<a href="http://lwn.net/Articles/652677/">here</a>, and +<a href="http://lwn.net/Articles/653326/">here</a>.</i></p>
s/http/https/g
Documentation/RCU/Design/Requirements/Requirements.html line 49
Quoted 6 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +6
-0+<p> +All that aside, here are the categories of currently known RCU requirements: +</p> + +<ol> +<li> <a href="#Fundamental Requirements">
Anchors don't typically have spaces in them. This may work in some browsers, but it doesn't validate. You should either use %20 or (better) use a '-'.
Documentation/RCU/Design/Requirements/Requirements.html line 69
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0+<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>.
(Note: when editing anchors, don't forget to handle the target of this in the generation script.)
Documentation/RCU/Design/Requirements/Requirements.html line 164
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +This scenario resembles one of the first uses of RCU in +<a href="http://en.wikipedia.org/wiki/DYNIX">DYNIX/ptx</a>,
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 366
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<p> +However, this temptation must be resisted because there are a +surprisingly large number of ways that the compiler +(to say nothing of +<a href="http://www.openvms.compaq.com/wizard/wiz_2637.html">DEC Alpha CPUs</a>)
This link sadly doesn't seem to work anymore; it redirects to HP's general page on OpenVMS, not a copy of that specific article.o Use this instead, assuming no current live version exists:
https://web.archive.org/web/20120720095054/http://www.openvms.compaq.com/wizard/wiz_2637.html
Documentation/RCU/Design/Requirements/Requirements.html line 1604
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +10
-0+<li> It is also easy to forget to use <tt>rcu_assign_pointer()</tt> + and <tt>rcu_dereference()</tt>, perhaps (incorrectly) + substituting a simple assignment. + To catch this sort of error, a given RCU-protected pointer may be + tagged with <tt>__rcu</tt>, after which running sparse + with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt> will complain + about simple-assignment accesses to that pointer. + Arnd Bergmann made me aware of this requirement, and also + supplied the needed + <a href="http://lwn.net/Articles/376011/">patch series</a>.
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 1640
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<li> Open-coded use of <tt>rcu_assign_pointer()</tt> and + <tt>rcu_dereference()</tt> to create typical linked + data structures can be surprisingly error-prone. + Therefore, RCU-protected + <a href="http://lwn.net/Articles/609973/#RCU List APIs">linked lists</a>
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 1709
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<p> +This all should be quite obvious, but the fact remains that +Linus Torvalds recently had to +<a href="http://marc.info/?l=linux-kernel&m=142905739823385">remind</a> +me of this requirement.
I'd suggest using the lkml.kernel.org redirector for this link, along with a Message-Id.
Documentation/RCU/Design/Requirements/Requirements.html line 1838
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +9
-0+<p> +The name notwithstanding, some Linux-kernel architectures +can have nested NMIs, which RCU must handle correctly. +Andy Lutomirski +<a href="https://lkml.org/lkml/2014/11/21/642">surprised me</a> +with this requirement; +he also kindly surprised me with +<a href="https://lkml.org/lkml/2014/11/22/1">an algorithm</a> +that meets this requirement.
These links should both use lkml.kernel.org as well. Doubly important because lkml.org is often down or has broken messages in its archive.
Documentation/RCU/Design/Requirements/Requirements.html line 1862
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +RCU therefore provides +<tt><a href="http://lwn.net/Articles/217484/">rcu_barrier()</a></tt>,
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 1932
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +This pair of mutual scheduler-RCU requirements came as a +<a href="http://lwn.net/Articles/453002/">complete surprise</a>.
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 2055
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+This requirement made its presence known after users made it +clear that an earlier +<a href="http://lwn.net/Articles/107930/">real-time patch</a>
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 75
Quoted 2 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +2
-0+did not meet their needs, in conjunction with some +<a href="https://lkml.org/lkml/2005/3/17/199">RCU issues</a>
lkml.kernel.org
Documentation/RCU/Design/Requirements/Requirements.html line 2179
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +The +<a href="http://lwn.net/Articles/609973/#RCU Per-Flavor API Table">RCU-bh API</a>
s/http/https/ (and the same for all later lwn links in the document)
- Josh Triplett
Re: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 4 lines · Josh Triplett
The content of the document seems fine; a few comments below on meta-issues.
On Fri, Dec 04, 2015 at 03:50:19PM -0800, Paul E. McKenney wrote:
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html line 4
Quoted 7 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0@@ -0,0 +1,2799 @@ +<!-- 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">Nit: these days, this should just be:
<!doctype html>
Will making this change mean that https://validator.w3.org/ will then require me to make a huge quantity of other changes?
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html line 7
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+ <html> + <head><title>A Tour Through RCU's Requirements [LWN.net]</title> + <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">Is there a good reason to not use charset=utf-8 here?
Beats me. Cargo-culted that one. ;-)
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html line 11
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0+ +<h1>A Tour Through RCU's Requirements</h1> + +<p>Copyright IBM Corporation, 2015</p>If you're aiming for a properly formatted copyright notice, the year typically comes first, followed by the copyright holder. That said, your corporate guidelines presumably have a specific format; is this that format?
Indeed it is. Between you and IBM Legal, I unfortunately must follow IBM Legal's advice. ;-)
Quoted 8 lines
Documentation/RCU/Design/Requirements/Requirements.html line 17
Quoted 6 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +6
-0+<p>Author: Paul E. McKenney</p> +<p><i>The initial version of this document appeared in the +<a href="http://lwn.net/">LWN</a> articles +<a href="http://lwn.net/Articles/652156/">here</a>, +<a href="http://lwn.net/Articles/652677/">here</a>, and +<a href="http://lwn.net/Articles/653326/">here</a>.</i></p>s/http/https/g
Will change.
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html line 49
Quoted 6 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +6
-0+<p> +All that aside, here are the categories of currently known RCU requirements: +</p> + +<ol> +<li> <a href="#Fundamental Requirements">Anchors don't typically have spaces in them. This may work in some browsers, but it doesn't validate. You should either use %20 or (better) use a '-'.
It did when I validated it via https://validator.w3.org/.
Which is why I questioned your changes to the doctype directive.
Alternatively, what are you using to validate this?
Quoted 7 lines
Documentation/RCU/Design/Requirements/Requirements.html line 69
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0+<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>.(Note: when editing anchors, don't forget to handle the target of this in the generation script.)
Good point!
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html line 164
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +This scenario resembles one of the first uses of RCU in +<a href="http://en.wikipedia.org/wiki/DYNIX">DYNIX/ptx</a>,s/http/https/
Will change globally.
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html line 366
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<p> +However, this temptation must be resisted because there are a +surprisingly large number of ways that the compiler +(to say nothing of +<a href="http://www.openvms.compaq.com/wizard/wiz_2637.html">DEC Alpha CPUs</a>)This link sadly doesn't seem to work anymore; it redirects to HP's general page on OpenVMS, not a copy of that specific article.o Use this instead, assuming no current live version exists:
https://web.archive.org/web/20120720095054/http://www.openvms.compaq.com/wizard/wiz_2637.html
Good catch! Its new home is http://h71000.www7.hp.com/wizard/wiz_2637.html.
Quoted 13 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1604
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +10
-0+<li> It is also easy to forget to use <tt>rcu_assign_pointer()</tt> + and <tt>rcu_dereference()</tt>, perhaps (incorrectly) + substituting a simple assignment. + To catch this sort of error, a given RCU-protected pointer may be + tagged with <tt>__rcu</tt>, after which running sparse + with <tt>CONFIG_SPARSE_RCU_POINTER=y</tt> will complain + about simple-assignment accesses to that pointer. + Arnd Bergmann made me aware of this requirement, and also + supplied the needed + <a href="http://lwn.net/Articles/376011/">patch series</a>.s/http/https/
Quoted 7 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1640
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<li> Open-coded use of <tt>rcu_assign_pointer()</tt> and + <tt>rcu_dereference()</tt> to create typical linked + data structures can be surprisingly error-prone. + Therefore, RCU-protected + <a href="http://lwn.net/Articles/609973/#RCU List APIs">linked lists</a>s/http/https/
Will fix these.
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1709
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<p> +This all should be quite obvious, but the fact remains that +Linus Torvalds recently had to +<a href="http://marc.info/?l=linux-kernel&m=142905739823385">remind</a> +me of this requirement.I'd suggest using the lkml.kernel.org redirector for this link, along with a Message-Id.
Quoted 12 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1838
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +9
-0+<p> +The name notwithstanding, some Linux-kernel architectures +can have nested NMIs, which RCU must handle correctly. +Andy Lutomirski +<a href="https://lkml.org/lkml/2014/11/21/642">surprised me</a> +with this requirement; +he also kindly surprised me with +<a href="https://lkml.org/lkml/2014/11/22/1">an algorithm</a> +that meets this requirement.These links should both use lkml.kernel.org as well. Doubly important because lkml.org is often down or has broken messages in its archive.
Good point, will look into finding the Message-IDs...
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1862
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +RCU therefore provides +<tt><a href="http://lwn.net/Articles/217484/">rcu_barrier()</a></tt>,s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 1932
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +This pair of mutual scheduler-RCU requirements came as a +<a href="http://lwn.net/Articles/453002/">complete surprise</a>.
Quoted 7 lines
s/http/https/
Documentation/RCU/Design/Requirements/Requirements.html line 2055
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+This requirement made its presence known after users made it +clear that an earlier +<a href="http://lwn.net/Articles/107930/">real-time patch</a>s/http/https/
Will fix these.
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html line 75
Quoted 2 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +2
-0+did not meet their needs, in conjunction with some +<a href="https://lkml.org/lkml/2005/3/17/199">RCU issues</a>lkml.kernel.org
As above.
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html line 2179
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+<p> +The +<a href="http://lwn.net/Articles/609973/#RCU Per-Flavor API Table">RCU-bh API</a>s/http/https/ (and the same for all later lwn links in the document)
Will fix.
Thanx, Paul
Re: [PATCH tip/core/rcu 1/8] documentation: Record RCU requirements
Quoted 16 lines · Paul E. McKenney
Quoted 4 lines · Josh Triplett
The content of the document seems fine; a few comments below on meta-issues.
On Fri, Dec 04, 2015 at 03:50:19PM -0800, Paul E. McKenney wrote:
Quoted 10 lines
Documentation/RCU/Design/Requirements/Requirements.html line 4
Quoted 7 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0@@ -0,0 +1,2799 @@ +<!-- 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">Nit: these days, this should just be:
<!doctype html>
Quoted 2 lines
Will making this change mean that https://validator.w3.org/ will then require me to make a huge quantity of other changes?
I checked a prominent web site, and they are using the same doctype as I am, so I am keeping this one. However...
Quoted 7 lines
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html line 7
Quoted 3 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +3
-0+ <html> + <head><title>A Tour Through RCU's Requirements [LWN.net]</title> + <meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">Is there a good reason to not use charset=utf-8 here?
Beats me. Cargo-culted that one. ;-)
... they use utf-8, so I changed mine accordingly.
Quoted 20 lines
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html line 11
Quoted 4 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +4
-0+ +<h1>A Tour Through RCU's Requirements</h1> + +<p>Copyright IBM Corporation, 2015</p>If you're aiming for a properly formatted copyright notice, the year typically comes first, followed by the copyright holder. That said, your corporate guidelines presumably have a specific format; is this that format?
Indeed it is. Between you and IBM Legal, I unfortunately must follow IBM Legal's advice. ;-)
Quoted 7 lines
Quoted 6 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +6
-0+<p>Author: Paul E. McKenney</p> +<p><i>The initial version of this document appeared in the +<a href="http://lwn.net/">LWN</a> articles +<a href="http://lwn.net/Articles/652156/">here</a>, +<a href="http://lwn.net/Articles/652677/">here</a>, and +<a href="http://lwn.net/Articles/653326/">here</a>.</i></p>
Quoted 3 lines
Quoted 1 line
s/http/https/g
Will change.
And done, globally, at least for those whose webservers were willing to put up with the change. Which was the vast majority.
[ . . . ]
Quoted 22 lines
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1709
Quoted 5 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +5
-0+<p> +This all should be quite obvious, but the fact remains that +Linus Torvalds recently had to +<a href="http://marc.info/?l=linux-kernel&m=142905739823385">remind</a> +me of this requirement.I'd suggest using the lkml.kernel.org redirector for this link, along with a Message-Id.
Quoted 12 lines
Documentation/RCU/Design/Requirements/Requirements.html line 1838
Quoted 9 lines
Documentation/RCU/Design/Requirements/Requirements.html new file +9
-0+<p> +The name notwithstanding, some Linux-kernel architectures +can have nested NMIs, which RCU must handle correctly. +Andy Lutomirski +<a href="https://lkml.org/lkml/2014/11/21/642">surprised me</a> +with this requirement; +he also kindly surprised me with +<a href="https://lkml.org/lkml/2014/11/22/1">an algorithm</a> +that meets this requirement.These links should both use lkml.kernel.org as well. Doubly important because lkml.org is often down or has broken messages in its archive.
Quoted 1 line
Good point, will look into finding the Message-IDs...
This involves a second click for https://lkml.kernel.org/r/<Message-ID>
Trying https://lkml.kernel.org/g/<Message-ID>. Which works nicely, so sold!
I will let you bug kernel.org about the fact that it translates the URL to the http: form rather than the https: form... But if it did that for the /g/ form, it couldn't find the web page. Never mind!
So all the ones that work have been converted.
Thanx, Paul
PATCH 2/8 Documentation: Record bottom-bit-zero guarantee for ->next
In reply to Paul E. McKenneyThis commit records RCU's guarantee that the bottom bit of the rcu_head structure's ->next field will remain zero for callbacks posted via call_rcu(), but not necessarily for <tt>kfree_rcu()</tt> or some possible future call_rcu_lazy() variant that might one day be created for energy-efficiency purposese.
--- .../RCU/Design/Requirements/Requirements.html | 43 ++++++++++++++++++++++ .../RCU/Design/Requirements/Requirements.htmlx | 43 ++++++++++++++++++++++ 2 files changed, 86 insertions(+)
Documentation/RCU/Design/Requirements/Requirements.html +43 -0
@@ -1678,6 +1678,7 @@ Some of the relevant points of interest are as follows: <li> <a href="#Scheduler and RCU">Scheduler and RCU</a>. <li> <a href="#Tracing and RCU">Tracing and RCU</a>. <li> <a href="#Energy Efficiency">Energy Efficiency</a>. +<li> <a href="#Memory Efficiency">Memory Efficiency</a>. <li> <a href="#Performance, Scalability, Response Time, and Reliability"> Performance, Scalability, Response Time, and Reliability</a>. </ol>
@@ -2006,6 +2007,48 @@ I learned of many of these requirements via angry phone calls: Flaming me on the Linux-kernel mailing list was apparently not sufficient to fully vent their ire at RCU's energy-efficiency bugs! +<h3><a name="Memory Efficiency">Memory Efficiency</a></h3> + +<p> +Although small-memory non-realtime systems can simply use Tiny RCU, +code size is only one aspect of memory efficiency. +Another aspect is the size of the <tt>rcu_head</tt> structure +used by <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt>. +Although this structure contains nothing more than a pair of pointers, +it does appear in many RCU-protected data structures, including +some that are size critical. +The <tt>page</tt> structure is a case in point, as evidenced by +the many occurrences of the <tt>union</tt> keyword within that structure. + +<p> +This need for memory efficiency is one reason that RCU uses hand-crafted +singly linked lists to track the <tt>rcu_head</tt> structures that +are waiting for a grace period to elapse. +It is also the reason why <tt>rcu_head</tt> structures do not contain +debug information, such as fields tracking the file and line of the +<tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> that posted them. +Although this information might appear in debug-only kernel builds at some +point, in the meantime, the <tt>->func</tt> field will often provide +the needed debug information. + +<p> +However, in some cases, the need for memory efficiency leads to even +more extreme measures. +Returning to the <tt>page</tt> structure, the <tt>rcu_head</tt> field +shares storage with a great many other structures that are used at +various points in the corresponding page's lifetime. +In order to correctly resolve certain +<a href="https://lkml.org/lkml/2015/8/19/137">race conditions</a>, +the Linux kernel's memory-management subsystem needs a particular bit +to remain zero during all phases of grace-period processing, +and that bit happens to map to the bottom bit of the +<tt>rcu_head</tt> structure's <tt>->next</tt> field. +RCU makes this guarantee as long as <tt>call_rcu()</tt> +is used to post the callback, as opposed to <tt>kfree_rcu()</tt> +or some future “lazy” +variant of <tt>call_rcu()</tt> that might one day be created for +energy-efficiency purposes. + <h3><a name="Performance, Scalability, Response Time, and Reliability"> Performance, Scalability, Response Time, and Reliability</a></h3>
Documentation/RCU/Design/Requirements/Requirements.htmlx +43 -0
55 lines not on this page · raw message
Signature · 1 line
2.5.2
PATCH 3/8 documentation: Cover requirements controlling stall warnings
In reply to Paul E. McKenneyThis commit adds verbiage on boot and sysfs parameters that can be used to control RCU CPU stall warnings, both to change the timeout and to suppress these warnings entirely.
--- .../RCU/Design/Requirements/Requirements.html | 25 +++++++++++++++++++++- .../RCU/Design/Requirements/Requirements.htmlx | 25 +++++++++++++++++++++- 2 files changed, 48 insertions(+), 2 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +24 -1
@@ -1618,12 +1618,35 @@ guard against mishaps and misuse: supplied the needed <a href="https://lkml.org/lkml/2010/3/18/417">patch</a>. <li> An infinite loop in an RCU read-side critical section will - eventually trigger an RCU CPU stall warning splat. + eventually trigger an RCU CPU stall warning splat, with + the duration of “eventually” being controlled by the + <tt>RCU_CPU_STALL_TIMEOUT</tt> <tt>Kconfig</tt> option, or, + alternatively, by the + <tt>rcupdate.rcu_cpu_stall_timeout</tt> boot/sysfs + parameter. However, RCU is not obligated to produce this splat unless there is a grace period waiting on that particular RCU read-side critical section. + <p> + Some extreme workloads might intentionally delay + RCU grace periods, and systems running those workloads can + be booted with <tt>rcupdate.rcu_cpu_stall_suppress</tt> + to suppress the splats. + This kernel parameter may also be set via <tt>sysfs</tt>. + Furthermore, RCU CPU stall warnings are counter-productive + during sysrq dumps and during panics. + RCU therefore supplies the <tt>rcu_sysrq_start()</tt> and + <tt>rcu_sysrq_end()</tt> API members to be called before + and after long sysrq dumps. + RCU also supplies the <tt>rcu_panic()</tt> notifier that is + automatically invoked at the beginning of a panic to suppress + further RCU CPU stall warnings. + + <p> This requirement made itself known in the early 1990s, pretty much the first time that it was necessary to debug a CPU stall. + That said, the initial implementation in DYNIX/ptx was quite + generic in comparison with that of Linux. <li> Although it would be very good to detect pointers leaking out of RCU read-side critical sections, there is currently no good way of doing this.
Documentation/RCU/Design/Requirements/Requirements.htmlx +24 -1
@@ -1777,12 +1777,35 @@ guard against mishaps and misuse: supplied the needed <a href="https://lkml.org/lkml/2010/3/18/417">patch</a>. <li> An infinite loop in an RCU read-side critical section will - eventually trigger an RCU CPU stall warning splat. + eventually trigger an RCU CPU stall warning splat, with + the duration of “eventually” being controlled by the + <tt>RCU_CPU_STALL_TIMEOUT</tt> <tt>Kconfig</tt> option, or, + alternatively, by the + <tt>rcupdate.rcu_cpu_stall_timeout</tt> boot/sysfs + parameter. However, RCU is not obligated to produce this splat unless there is a grace period waiting on that particular RCU read-side critical section. + <p> + Some extreme workloads might intentionally delay + RCU grace periods, and systems running those workloads can + be booted with <tt>rcupdate.rcu_cpu_stall_suppress</tt> + to suppress the splats. + This kernel parameter may also be set via <tt>sysfs</tt>. + Furthermore, RCU CPU stall warnings are counter-productive + during sysrq dumps and during panics. + RCU therefore supplies the <tt>rcu_sysrq_start()</tt> and + <tt>rcu_sysrq_end()</tt> API members to be called before + and after long sysrq dumps. + RCU also supplies the <tt>rcu_panic()</tt> notifier that is + automatically invoked at the beginning of a panic to suppress + further RCU CPU stall warnings. + + <p> This requirement made itself known in the early 1990s, pretty much the first time that it was necessary to debug a CPU stall. + That said, the initial implementation in DYNIX/ptx was quite + generic in comparison with that of Linux. <li> Although it would be very good to detect pointers leaking out of RCU read-side critical sections, there is currently no good way of doing this.
Signature · 1 line
2.5.2
PATCH 4/8 documentation: Composability analogies
In reply to Paul E. McKenneyThis commit expands on RCU's composability by comparing it to that of transactional memory and of locking.
--- Documentation/RCU/Design/Requirements/Requirements.html | 8 ++++++++ Documentation/RCU/Design/Requirements/Requirements.htmlx | 8 ++++++++ 2 files changed, 16 insertions(+)
Documentation/RCU/Design/Requirements/Requirements.html +8 -0
@@ -1495,6 +1495,14 @@ section, neither of which is conducive to a long-lived and prosperous kernel. <p> +It is worth noting that RCU is not alone in limiting composability. +For example, many transactional-memory implementations prohibit +composing a pair of transactions separated by an irrevocable +operation (for example, a network receive operation). +For another example, lock-based critical sections can be composed +surprisingly freely, but only if deadlock is avoided. + +<p> In short, although RCU read-side critical sections are highly composable, care is required in some situations, just as is the case for any other composable synchronization mechanism.
Documentation/RCU/Design/Requirements/Requirements.htmlx +8 -0
@@ -1654,6 +1654,14 @@ section, neither of which is conducive to a long-lived and prosperous kernel. <p> +It is worth noting that RCU is not alone in limiting composability. +For example, many transactional-memory implementations prohibit +composing a pair of transactions separated by an irrevocable +operation (for example, a network receive operation). +For another example, lock-based critical sections can be composed +surprisingly freely, but only if deadlock is avoided. + +<p> In short, although RCU read-side critical sections are highly composable, care is required in some situations, just as is the case for any other composable synchronization mechanism.
Signature · 1 line
2.5.2
PATCH 5/8 documentation: Expand on scheduler/RCU deadlock requirements
In reply to Paul E. McKenneyThis commit adds a second option for avoiding scheduler/RCU deadlocks, namely that preemption be disabled across the entire RCU read-side critical section in question.
--- Documentation/RCU/Design/Requirements/Requirements.html | 14 +++++++++----- Documentation/RCU/Design/Requirements/Requirements.htmlx | 14 +++++++++----- 2 files changed, 18 insertions(+), 10 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +9 -5
@@ -1942,12 +1942,16 @@ RCU depends on the scheduler, and the scheduler uses RCU to protect some of its data structures. This means the scheduler is forbidden from acquiring the runqueue locks and the priority-inheritance locks -in the middle of an outermost RCU read-side critical section unless -it also releases them before exiting that same -RCU read-side critical section. -This same prohibition also applies to any lock that is acquired +in the middle of an outermost RCU read-side critical section unless either +(1) it releases them before exiting that same +RCU read-side critical section, or +(2) preemption is disabled across +that entire RCU read-side critical section. +This same prohibition also applies (recursively!) to any lock that is acquired while holding any lock to which this prohibition applies. -Violating this rule results in deadlock. +Adhering to this rule prevents preemptible RCU from invoking +<tt>rcu_read_unlock_special()</tt> while either runqueue or +priority-inheritance locks are held, thus avoiding deadlock. <p> For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
Documentation/RCU/Design/Requirements/Requirements.htmlx +9 -5
@@ -2109,12 +2109,16 @@ RCU depends on the scheduler, and the scheduler uses RCU to protect some of its data structures. This means the scheduler is forbidden from acquiring the runqueue locks and the priority-inheritance locks -in the middle of an outermost RCU read-side critical section unless -it also releases them before exiting that same -RCU read-side critical section. -This same prohibition also applies to any lock that is acquired +in the middle of an outermost RCU read-side critical section unless either +(1) it releases them before exiting that same +RCU read-side critical section, or +(2) preemption is disabled across +that entire RCU read-side critical section. +This same prohibition also applies (recursively!) to any lock that is acquired while holding any lock to which this prohibition applies. -Violating this rule results in deadlock. +Adhering to this rule prevents preemptible RCU from invoking +<tt>rcu_read_unlock_special()</tt> while either runqueue or +priority-inheritance locks are held, thus avoiding deadlock. <p> For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
Signature · 1 line
2.5.2
PATCH 6/8 documentation: Clarify RCU memory barriers and requirements
In reply to Paul E. McKenneyThe RCU requirements do not make it absolutely clear that the memory-barrier requirements are not intended to replace the fundamental requirement that all pre-existing RCU readers complete before a grace period completes. This commit therefore pulls the memory-barrier requirements into a separate section and explicitly calls out the relationship between the memory-barrier requirements and the fundamental requirement.
--- .../RCU/Design/Requirements/Requirements.html | 66 +++++++++++++--------- .../RCU/Design/Requirements/Requirements.htmlx | 66 +++++++++++++--------- 2 files changed, 78 insertions(+), 54 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +39 -27
@@ -80,6 +80,8 @@ These are: Grace-Period Guarantee</a> <li> <a href="#Publish-Subscribe Guarantee"> Publish-Subscribe Guarantee</a> +<li> <a href="#Memory-Barrier Guarantees"> + Memory-Barrier Guarantees</a> <li> <a href="#RCU Primitives Guaranteed to Execute Unconditionally"> RCU Primitives Guaranteed to Execute Unconditionally</a> <li> <a href="#Guaranteed Read-to-Write Upgrade">
@@ -499,9 +501,37 @@ might the compiler make use of? <br><a href="#qq4answer">Answer</a> <p> -This simple linked-data-structure scenario clearly demonstrates the need -for RCU's stringent memory-ordering guarantees on systems with more than -one CPU: +In short, RCU's publish-subscribe guarantee is provided by the combination +of <tt>rcu_assign_pointer()</tt> and <tt>rcu_dereference()</tt>. +This guarantee allows data elements to be safely added to RCU-protected +linked data structures without disrupting RCU readers. +This guarantee can be used in combination with the grace-period +guarantee to also allow data elements to be removed from RCU-protected +linked data structures, again without disrupting RCU readers. + +<p> +This guarantee was only partially premeditated. +DYNIX/ptx used an explicit memory barrier for publication, but had nothing +resembling <tt>rcu_dereference()</tt> for subscription, nor did it +have anything resembling the <tt>smp_read_barrier_depends()</tt> +that was later subsumed into <tt>rcu_dereference()</tt>. +The need for these operations made itself known quite suddenly at a +late-1990s meeting with the DEC Alpha architects, back in the days when +DEC was still a free-standing company. +It took the Alpha architects a good hour to convince me that any sort +of barrier would ever be needed, and it then took me a good <i>two</i> hours +to convince them that their documentation did not make this point clear. +More recent work with the C and C++ standards committees have provided +much education on tricks and traps from the compiler. +In short, compilers were much less tricky in the early 1990s, but in +2015, don't even think about omitting <tt>rcu_dereference()</tt>! + +<h3><a name="Memory-Barrier Guarantees">Memory-Barrier Guarantees</a></h3> + +<p> +The previous section's simple linked-data-structure scenario clearly +demonstrates the need for RCU's stringent memory-ordering guarantees on +systems with more than one CPU: <ol> <li> Each CPU that has an RCU read-side critical section that
@@ -554,30 +584,12 @@ Are all these memory barriers <i> really</i> required? <br><a href="#qq6answer">Answer</a> <p> -In short, RCU's publish-subscribe guarantee is provided by the combination -of <tt>rcu_assign_pointer()</tt> and <tt>rcu_dereference()</tt>. -This guarantee allows data elements to be safely added to RCU-protected -linked data structures without disrupting RCU readers. -This guarantee can be used in combination with the grace-period -guarantee to also allow data elements to be removed from RCU-protected -linked data structures, again without disrupting RCU readers. - -<p> -This guarantee was only partially premeditated. -DYNIX/ptx used an explicit memory barrier for publication, but had nothing -resembling <tt>rcu_dereference()</tt> for subscription, nor did it -have anything resembling the <tt>smp_read_barrier_depends()</tt> -that was later subsumed into <tt>rcu_dereference()</tt>. -The need for these operations made itself known quite suddenly at a -late-1990s meeting with the DEC Alpha architects, back in the days when -DEC was still a free-standing company. -It took the Alpha architects a good hour to convince me that any sort -of barrier would ever be needed, and it then took me a good <i>two</i> hours -to convince them that their documentation did not make this point clear. -More recent work with the C and C++ standards committees have provided -much education on tricks and traps from the compiler. -In short, compilers were much less tricky in the early 1990s, but in -2015, don't even think about omitting <tt>rcu_dereference()</tt>! +Note that these memory-barrier requirements do not replace the fundamental +RCU requirement that a grace period wait for all pre-existing readers. +On the contrary, the memory barriers called out in this section must operate in +such a way as to <i>enforce</i> this fundamental requirement. +Of course, different implementations enforce this requirement in different +ways, but enforce it they must. <h3><a name="RCU Primitives Guaranteed to Execute Unconditionally">RCU Primitives Guaranteed to Execute Unconditionally</a></h3>
Documentation/RCU/Design/Requirements/Requirements.htmlx +39 -27
84 lines not on this page · raw message
Signature · 1 line
2.5.2
PATCH 7/8 documentation: Update RCU requirements based on expedited changes
In reply to Paul E. McKenneyBecause RCU-sched expedited grace periods now use IPIs and interact with rcu_read_unlock(), it is no longer sufficient to disable preemption across RCU read-side critical sections that acquire and hold scheduler locks. It is now necessary to instead disable interrupts. This commit documents this change.
--- Documentation/RCU/Design/Requirements/Requirements.html | 12 ++++++++++-- Documentation/RCU/Design/Requirements/Requirements.htmlx | 10 +++++++++- 2 files changed, 19 insertions(+), 3 deletions(-)
Documentation/RCU/Design/Requirements/Requirements.html +10 -2
@@ -1,5 +1,5 @@ <!-- DO NOT HAND EDIT. --> -<!-- Instead, edit Requirements.htmlx and run 'sh htmlqqz.sh Requirements' --> +<!-- Instead, edit Documentation/RCU/Design/Requirements/Requirements.htmlx and run 'sh htmlqqz.sh Documentation/RCU/Design/Requirements/Requirements' --> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html>
@@ -1957,7 +1957,7 @@ the runqueue locks and the priority-inheritance locks in the middle of an outermost RCU read-side critical section unless either (1) it releases them before exiting that same RCU read-side critical section, or -(2) preemption is disabled across +(2) interrupts are disabled across that entire RCU read-side critical section. This same prohibition also applies (recursively!) to any lock that is acquired while holding any lock to which this prohibition applies.
@@ -1966,6 +1966,14 @@ Adhering to this rule prevents preemptible RCU from invoking priority-inheritance locks are held, thus avoiding deadlock. <p> +Prior to v4.4, it was only necessary to disable preemption across +RCU read-side critical sections that acquired scheduler locks. +In v4.4, expedited grace periods started using IPIs, and these +IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath. +Therefore, this expedited-grace-period change required disabling of +interrupts, not just preemption. + +<p> For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt> implementation must be written carefully to avoid similar deadlocks. In particular, <tt>rcu_read_unlock()</tt> must tolerate an
Documentation/RCU/Design/Requirements/Requirements.htmlx +9 -1
@@ -2124,7 +2124,7 @@ the runqueue locks and the priority-inheritance locks in the middle of an outermost RCU read-side critical section unless either (1) it releases them before exiting that same RCU read-side critical section, or -(2) preemption is disabled across +(2) interrupts are disabled across that entire RCU read-side critical section. This same prohibition also applies (recursively!) to any lock that is acquired while holding any lock to which this prohibition applies.
@@ -2133,6 +2133,14 @@ Adhering to this rule prevents preemptible RCU from invoking priority-inheritance locks are held, thus avoiding deadlock. <p> +Prior to v4.4, it was only necessary to disable preemption across +RCU read-side critical sections that acquired scheduler locks. +In v4.4, expedited grace periods started using IPIs, and these +IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath. +Therefore, this expedited-grace-period change required disabling of +interrupts, not just preemption. + +<p> For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt> implementation must be written carefully to avoid similar deadlocks. In particular, <tt>rcu_read_unlock()</tt> must tolerate an
Signature · 1 line
2.5.2
PATCH 8/8 Documentation/memory-barriers.txt: Fix ACCESS_ONCE thinko
In reply to Paul E. McKenneyFrom: Chris Metcalf <[email protected]>
In commit 2ecf810121c7 ("Documentation/memory-barriers.txt: Add needed ACCESS_ONCE() calls to memory-barriers.txt") the statement "Q = P" was converted to "ACCESS_ONCE(Q) = P". This should have been "Q = ACCESS_ONCE(P)". It later became "WRITE_ONCE(Q, P)". This doesn't match the following text, which is "Q = LOAD P". Change the statement to be "Q = READ_ONCE(P)".
--- Documentation/memory-barriers.txt | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
Documentation/memory-barriers.txt +4 -4
@@ -194,7 +194,7 @@ There are some minimal guarantees that may be expected of a CPU: (*) On any given CPU, dependent memory accesses will be issued in order, with respect to itself. This means that for: - WRITE_ONCE(Q, P); smp_read_barrier_depends(); D = READ_ONCE(*Q); + Q = READ_ONCE(P); smp_read_barrier_depends(); D = READ_ONCE(*Q); the CPU will issue the following memory operations:
@@ -202,9 +202,9 @@ There are some minimal guarantees that may be expected of a CPU: and always in that order. On most systems, smp_read_barrier_depends() does nothing, but it is required for DEC Alpha. The READ_ONCE() - and WRITE_ONCE() are required to prevent compiler mischief. Please - note that you should normally use something like rcu_dereference() - instead of open-coding smp_read_barrier_depends(). + is required to prevent compiler mischief. Please note that you + should normally use something like rcu_dereference() instead of + open-coding smp_read_barrier_depends(). (*) Overlapping loads and stores within a particular CPU will appear to be ordered within that CPU. This means that for:
Signature · 1 line
2.5.2
Quoted 7 lines · Paul E. McKenney
Hello!
This series contains documentation updates, perhaps most notably a first installment of RCU design documentation, which first appeared on LWN
(http://lwn.net/Articles/652156/, http://lwn.net/Articles/652677/, and
http://lwn.net/Articles/653326/). The individual patches are as follows:
Quoted 5 lines
1. Add RCU requirements design document.
2-7. Updates to the RCU requirements.
8. Fix memory-barrier.txt typo, courtesy of Chris Metcalf.
I sent two mails worth of feedback to patch 1 that effectively apply to the whole series; one covers the checkin of a generated file, and the other covers various mechanical issues in the document. With those two fixed:
for the whole series