From 869cc745bfbd1d8fda8b1dae1a8882b85393cdfa Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Tue, 1 May 2018 16:26:46 -0700 Subject: doc: Update memory-ordering documentation for ->gp-seq Signed-off-by: Paul E. McKenney --- .../Memory-Ordering/Tree-RCU-Memory-Ordering.html | 22 +- .../Design/Memory-Ordering/TreeRCU-gp-cleanup.svg | 123 ++++++----- .../Design/Memory-Ordering/TreeRCU-gp-init-1.svg | 16 +- .../Design/Memory-Ordering/TreeRCU-gp-init-3.svg | 56 ++--- .../RCU/Design/Memory-Ordering/TreeRCU-gp.svg | 237 +++++++++++---------- .../RCU/Design/Memory-Ordering/TreeRCU-qs.svg | 12 +- 6 files changed, 243 insertions(+), 223 deletions(-) (limited to 'Documentation/RCU') diff --git a/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html b/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html index 8651b0b4fd79..a346ce0116eb 100644 --- a/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html +++ b/Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html @@ -357,7 +357,7 @@ parts, starting in this section with the various phases of grace-period initialization.

The first ordering-related grace-period initialization action is to -increment the rcu_state structure's ->gpnum +advance the rcu_state structure's ->gp_seq grace-period-number counter, as shown below:

TreeRCU-gp-init-1.svg @@ -388,7 +388,7 @@ its last CPU and if the next rcu_node structure has no online CPUs).

The final rcu_gp_init() pass through the rcu_node tree traverses breadth-first, setting each rcu_node structure's -->gpnum field to the newly incremented value from the +->gp_seq field to the newly advanced value from the rcu_state structure, as shown in the following diagram.

TreeRCU-gp-init-1.svg @@ -398,9 +398,9 @@ tree traverses breadth-first, setting each rcu_node structure's to notice that a new grace period has started, as described in the next section. But because the grace-period kthread started the grace period at the -root (with the increment of the rcu_state structure's -->gpnum field) before setting each leaf rcu_node -structure's ->gpnum field, each CPU's observation of +root (with the advancing of the rcu_state structure's +->gp_seq field) before setting each leaf rcu_node +structure's ->gp_seq field, each CPU's observation of the start of the grace period will happen after the actual start of the grace period. @@ -466,7 +466,7 @@ section that the grace period must wait on. But a RCU read-side critical section might have started after the beginning of the grace period - (the ->gpnum++ from earlier), so why should + (the advancing of ->gp_seq from earlier), so why should the grace period wait on such a critical section? Answer: @@ -609,10 +609,8 @@ states outstanding from other CPUs.

Grace-Period Cleanup

Grace-period cleanup first scans the rcu_node tree -breadth-first setting all the ->completed fields equal -to the number of the newly completed grace period, then it sets -the rcu_state structure's ->completed field, -again to the number of the newly completed grace period. +breadth-first advancing all the ->gp_seq fields, then it +advances the rcu_state structure's ->gp_seq field. The ordering effects are shown below:

TreeRCU-gp-cleanup.svg @@ -634,7 +632,7 @@ grace-period cleanup is complete, the next grace period can begin. CPU has reported its quiescent state, but it may be some milliseconds before RCU becomes aware of this. The latest reasonable candidate is once the rcu_state - structure's ->completed field has been updated, + structure's ->gp_seq field has been updated, but it is quite possible that some CPUs have already completed phase two of their updates by that time. In short, if you are going to work with RCU, you need to @@ -647,7 +645,7 @@ grace-period cleanup is complete, the next grace period can begin.

Callback Invocation

Once a given CPU's leaf rcu_node structure's -->completed field has been updated, that CPU can begin +->gp_seq field has been updated, that CPU can begin invoking its RCU callbacks that were waiting for this grace period to end. These callbacks are identified by rcu_advance_cbs(), diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-cleanup.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-cleanup.svg index 754f426b297a..bf84fbab27ee 100644 --- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-cleanup.svg +++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-cleanup.svg @@ -384,11 +384,11 @@ inkscape:window-height="1144" id="namedview208" showgrid="true" - inkscape:zoom="0.70710678" - inkscape:cx="617.89017" - inkscape:cy="542.52419" - inkscape:window-x="86" - inkscape:window-y="28" + inkscape:zoom="0.78716603" + inkscape:cx="513.06403" + inkscape:cy="623.1214" + inkscape:window-x="102" + inkscape:window-y="38" inkscape:window-maximized="0" inkscape:current-layer="g3188-3" fit-margin-top="5" @@ -417,13 +417,15 @@ id="g3188"> ->completed = ->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">rcu_seq_end(&rnp->gp_seq) @@ -502,13 +504,15 @@ ->completed = ->gpnum + id="text202-36-7" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf - ->completed = ->gpnum - rsp->completed = @@ -607,15 +593,6 @@ sodipodi:linespacing="125%">Root - rnp->completed + id="flowPara3362" /> rcu_seq_end(&rsp->gp_seq) + + rcu_seq_end(&rnp->gp_seq) ->completed = ->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf ->completed = ->gpnum + id="text202-36-2" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf ->completed = ->gpnum + id="text202-36-3" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) - ->completed = ->gpnum + rcu_seq_end(&rnp->gp_seq) diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-1.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-1.svg index 0161262904ec..8c207550818f 100644 --- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-1.svg +++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-1.svg @@ -272,13 +272,13 @@ inkscape:window-height="1144" id="namedview208" showgrid="true" - inkscape:zoom="0.70710678" - inkscape:cx="617.89019" - inkscape:cy="636.57143" - inkscape:window-x="697" + inkscape:zoom="2.6330492" + inkscape:cx="524.82797" + inkscape:cy="519.31194" + inkscape:window-x="79" inkscape:window-y="28" inkscape:window-maximized="0" - inkscape:current-layer="svg2" + inkscape:current-layer="g3188" fit-margin-top="5" fit-margin-right="5" fit-margin-left="5" @@ -305,13 +305,15 @@ id="g3188"> rsp->gpnum++ + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">rcu_seq_start(rsp->gp_seq) diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-3.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-3.svg index de6ecc51b00e..d24d7d555dbc 100644 --- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-3.svg +++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp-init-3.svg @@ -19,7 +19,7 @@ id="svg2" version="1.1" inkscape:version="0.48.4 r9939" - sodipodi:docname="TreeRCU-gp-init-2.svg"> + sodipodi:docname="TreeRCU-gp-init-3.svg"> @@ -257,18 +257,22 @@ inkscape:window-width="1087" inkscape:window-height="1144" id="namedview208" - showgrid="false" - inkscape:zoom="0.70710678" + showgrid="true" + inkscape:zoom="0.68224756" inkscape:cx="617.89019" inkscape:cy="625.84293" - inkscape:window-x="697" + inkscape:window-x="54" inkscape:window-y="28" inkscape:window-maximized="0" - inkscape:current-layer="svg2" + inkscape:current-layer="g3153" fit-margin-top="5" fit-margin-right="5" fit-margin-left="5" - fit-margin-bottom="5" /> + fit-margin-bottom="5"> + + ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;font-family:Courier">->gp_seq = rsp->gp_seq @@ -366,13 +370,13 @@ ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq ->gpnum = rsp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg index b13b7b01bb3a..acd73c7ad0f4 100644 --- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg +++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-gp.svg @@ -1070,13 +1070,13 @@ inkscape:window-height="1144" id="namedview208" showgrid="true" - inkscape:zoom="0.6004608" - inkscape:cx="826.65969" - inkscape:cy="483.3047" - inkscape:window-x="66" - inkscape:window-y="28" + inkscape:zoom="0.81932583" + inkscape:cx="840.45848" + inkscape:cy="5052.4242" + inkscape:window-x="787" + inkscape:window-y="24" inkscape:window-maximized="0" - inkscape:current-layer="svg2" + inkscape:current-layer="g4" fit-margin-top="5" fit-margin-right="5" fit-margin-left="5" @@ -1543,15 +1543,6 @@ style="fill:none;stroke-width:0.025in" transform="translate(1749.0282,658.72243)" id="g3188"> - rsp->gpnum++ @@ -1584,6 +1575,17 @@ sodipodi:linespacing="125%">Root + rcu_seq_start(rsp->gp_seq) - ->gpnum = rsp->gpnum @@ -2359,6 +2352,15 @@ sodipodi:linespacing="125%">Root + ->gp_seq = rsp->gp_seq ->gpnum = rsp->gpnum + id="text202-92" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + id="text202-759" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq ->gpnum = rsp->gpnum + id="text202-87" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + id="text202-2" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq Leaf ->gpnum = rsp->gpnum + id="text202-0" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">->gp_seq = rsp->gp_seq - ->gpnum = rsp->gpnum rdp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rdp->gp_seq - ->completed = ->gpnum @@ -4325,6 +4309,17 @@ sodipodi:linespacing="125%">Root + rcu_seq_end(&rnp->gp_seq) ->completed = ->gpnum + id="text202-36-7" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf - ->completed = ->gpnum - rsp->completed = Root - rnp->completed ->completed = ->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf ->completed = ->gpnum + id="text202-36-9" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) Leaf ->completed = ->gpnum + id="text202-36-35" + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rcu_seq_end(&rnp->gp_seq) - ->completed = ->gpnum rcu_do_batch() + rcu_seq_end(&rnp->gp_seq) + rcu_seq_end(&rnp->gp_seq) + rcu_seq_end(&rsp->gp_seq) + ->gp_seq = rsp->gp_seq diff --git a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg index de3992f4cbe1..149bec2a4493 100644 --- a/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg +++ b/Documentation/RCU/Design/Memory-Ordering/TreeRCU-qs.svg @@ -300,13 +300,13 @@ inkscape:window-height="1144" id="namedview208" showgrid="true" - inkscape:zoom="0.70710678" - inkscape:cx="616.47598" - inkscape:cy="595.41964" - inkscape:window-x="813" + inkscape:zoom="0.96484375" + inkscape:cx="507.0191" + inkscape:cy="885.62207" + inkscape:window-x="47" inkscape:window-y="28" inkscape:window-maximized="0" - inkscape:current-layer="g4405" + inkscape:current-layer="g3115" fit-margin-top="5" fit-margin-right="5" fit-margin-left="5" @@ -710,7 +710,7 @@ font-weight="bold" font-size="192" id="text202-6-6" - style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rdp->gpnum + style="font-size:192px;font-style:normal;font-weight:bold;text-anchor:start;fill:#000000;stroke-width:0.025in;font-family:Courier">rdp->gp_seq