mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
To: linux-kernel@vger.kernel.org
Cc: mingo@kernel.org, jiangshanlai@gmail.com, dipankar@in.ibm.com,
	akpm@linux-foundation.org, mathieu.desnoyers@efficios.com,
	josh@joshtriplett.org, tglx@linutronix.de, peterz@infradead.org,
	rostedt@goodmis.org, dhowells@redhat.com, edumazet@google.com,
	fweisbec@gmail.com, oleg@redhat.com, joel@joelfernandes.org,
	"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Subject: [PATCH tip/core/rcu 29/40] doc: Update data-structure documentation for ->gp_seq
Date: Mon, 25 Jun 2018 17:08:48 -0700	[thread overview]
Message-ID: <20180626000859.23572-29-paulmck@linux.vnet.ibm.com> (raw)
In-Reply-To: <20180626000841.GA15696@linux.vnet.ibm.com>

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 .../Data-Structures/Data-Structures.html      | 118 ++++++++++--------
 1 file changed, 63 insertions(+), 55 deletions(-)

diff --git a/Documentation/RCU/Design/Data-Structures/Data-Structures.html b/Documentation/RCU/Design/Data-Structures/Data-Structures.html
index 6c06e10bd04b..f5120a00f511 100644
--- a/Documentation/RCU/Design/Data-Structures/Data-Structures.html
+++ b/Documentation/RCU/Design/Data-Structures/Data-Structures.html
@@ -380,31 +380,26 @@ and therefore need no protection.
 as follows:
 
 <pre>
-  1   unsigned long gpnum;
-  2   unsigned long completed;
+  1   unsigned long gp_seq;
 </pre>
 
 <p>RCU grace periods are numbered, and
-the <tt>-&gt;gpnum</tt> field contains the number of the grace
-period that started most recently.
-The <tt>-&gt;completed</tt> field contains the number of the
-grace period that completed most recently.
-If the two fields are equal, the RCU grace period that most recently
-started has already completed, and therefore the corresponding
-flavor of RCU is idle.
-If <tt>-&gt;gpnum</tt> is one greater than <tt>-&gt;completed</tt>,
-then <tt>-&gt;gpnum</tt> gives the number of the current RCU
-grace period, which has not yet completed.
-Any other combination of values indicates that something is broken.
-These two fields are protected by the root <tt>rcu_node</tt>'s
+the <tt>-&gt;gp_seq</tt> field contains the current grace-period
+sequence number.
+The bottom two bits are the state of the current grace period,
+which can be zero for not yet started or one for in progress.
+In other words, if the bottom two bits of <tt>-&gt;gp_seq</tt> are
+zero, the corresponding flavor of RCU is idle.
+Any other value in the bottom two bits indicates that something is broken.
+This field is protected by the root <tt>rcu_node</tt> structure's
 <tt>-&gt;lock</tt> field.
 
-</p><p>There are <tt>-&gt;gpnum</tt> and <tt>-&gt;completed</tt> fields
+</p><p>There are <tt>-&gt;gp_seq</tt> fields
 in the <tt>rcu_node</tt> and <tt>rcu_data</tt> structures
 as well.
 The fields in the <tt>rcu_state</tt> structure represent the
-most current values, and those of the other structures are compared
-in order to detect the start of a new grace period in a distributed
+most current value, and those of the other structures are compared
+in order to detect the beginnings and ends of grace periods in a distributed
 fashion.
 The values flow from <tt>rcu_state</tt> to <tt>rcu_node</tt>
 (down the tree from the root to the leaves) to <tt>rcu_data</tt>.
@@ -512,27 +507,47 @@ than to be heisenbugged out of existence.
 as follows:
 
 <pre>
-  1   unsigned long gpnum;
-  2   unsigned long completed;
+  1   unsigned long gp_seq;
+  2   unsigned long gp_seq_needed;
 </pre>
 
-<p>These fields are the counterparts of the fields of the same name in
-the <tt>rcu_state</tt> structure.
-They each may lag up to one behind their <tt>rcu_state</tt>
-counterparts.
-If a given <tt>rcu_node</tt> structure's <tt>-&gt;gpnum</tt> and
-<tt>-&gt;complete</tt> fields are equal, then this <tt>rcu_node</tt>
+<p>The <tt>rcu_node</tt> structures' <tt>-&gt;gp_seq</tt> fields are
+the counterparts of the field of the same name in the <tt>rcu_state</tt>
+structure.
+They each may lag up to one step behind their <tt>rcu_state</tt>
+counterpart.
+If the bottom two bits of a given <tt>rcu_node</tt> structure's
+<tt>-&gt;gp_seq</tt> field is zero, then this <tt>rcu_node</tt>
 structure believes that RCU is idle.
-Otherwise, as with the <tt>rcu_state</tt> structure,
-the <tt>-&gt;gpnum</tt> field will be one greater than the
-<tt>-&gt;complete</tt> fields, with <tt>-&gt;gpnum</tt>
-indicating which grace period this <tt>rcu_node</tt> believes
-is still being waited for.
+</p><p>The <tt>&gt;gp_seq</tt> field of each <tt>rcu_node</tt>
+structure is updated at the beginning and the end
+of each grace period.
+
+<p>The <tt>-&gt;gp_seq_needed</tt> fields record the
+furthest-in-the-future grace period request seen by the corresponding
+<tt>rcu_node</tt> structure.  The request is considered fulfilled when
+the value of the <tt>-&gt;gp_seq</tt> field equals or exceeds that of
+the <tt>-&gt;gp_seq_needed</tt> field.
 
-</p><p>The <tt>&gt;gpnum</tt> field of each <tt>rcu_node</tt>
-structure is updated at the beginning
-of each grace period, and the <tt>-&gt;completed</tt> fields are
-updated at the end of each grace period.
+<table>
+<tr><th>&nbsp;</th></tr>
+<tr><th align="left">Quick Quiz:</th></tr>
+<tr><td>
+	Suppose that this <tt>rcu_node</tt> structure doesn't see
+	a request for a very long time.
+	Won't wrapping of the <tt>-&gt;gp_seq</tt> field cause
+	problems?
+</td></tr>
+<tr><th align="left">Answer:</th></tr>
+<tr><td bgcolor="#ffffff"><font color="ffffff">
+	No, because if the <tt>-&gt;gp_seq_needed</tt> field lags behind the
+	<tt>-&gt;gp_seq</tt> field, the <tt>-&gt;gp_seq_needed</tt> field
+	will be updated at the end of the grace period.
+	Modulo-arithmetic comparisons therefore will always get the
+	correct answer, even with wrapping.
+</font></td></tr>
+<tr><td>&nbsp;</td></tr>
+</table>
 
 <h5>Quiescent-State Tracking</h5>
 
@@ -626,9 +641,8 @@ normal and expedited grace periods, respectively.
 	</ol>
 
 	<p><font color="ffffff">So the locking is absolutely required in
-	order to coordinate
-	clearing of the bits with the grace-period numbers in
-	<tt>-&gt;gpnum</tt> and <tt>-&gt;completed</tt>.
+	order to coordinate clearing of the bits with updating of the
+	grace-period sequence number in <tt>-&gt;gp_seq</tt>.
 </font></td></tr>
 <tr><td>&nbsp;</td></tr>
 </table>
@@ -1038,15 +1052,15 @@ out any <tt>rcu_data</tt> structure for which this flag is not set.
 as follows:
 
 <pre>
-  1   unsigned long completed;
-  2   unsigned long gpnum;
+  1   unsigned long gp_seq;
+  2   unsigned long gp_seq_needed;
   3   bool cpu_no_qs;
   4   bool core_needs_qs;
   5   bool gpwrap;
   6   unsigned long rcu_qs_ctr_snap;
 </pre>
 
-<p>The <tt>completed</tt> and <tt>gpnum</tt>
+<p>The <tt>-&gt;gp_seq</tt> and <tt>-&gt;gp_seq_needed</tt>
 fields are the counterparts of the fields of the same name
 in the <tt>rcu_state</tt> and <tt>rcu_node</tt> structures.
 They may each lag up to one behind their <tt>rcu_node</tt>
@@ -1054,15 +1068,9 @@ counterparts, but in <tt>CONFIG_NO_HZ_IDLE</tt> and
 <tt>CONFIG_NO_HZ_FULL</tt> kernels can lag
 arbitrarily far behind for CPUs in dyntick-idle mode (but these counters
 will catch up upon exit from dyntick-idle mode).
-If a given <tt>rcu_data</tt> structure's <tt>-&gt;gpnum</tt> and
-<tt>-&gt;complete</tt> fields are equal, then this <tt>rcu_data</tt>
+If the lower two bits of a given <tt>rcu_data</tt> structure's
+<tt>-&gt;gp_seq</tt> are zero, then this <tt>rcu_data</tt>
 structure believes that RCU is idle.
-Otherwise, as with the <tt>rcu_state</tt> and <tt>rcu_node</tt>
-structure,
-the <tt>-&gt;gpnum</tt> field will be one greater than the
-<tt>-&gt;complete</tt> fields, with <tt>-&gt;gpnum</tt>
-indicating which grace period this <tt>rcu_data</tt> believes
-is still being waited for.
 
 <table>
 <tr><th>&nbsp;</th></tr>
@@ -1070,13 +1078,13 @@ is still being waited for.
 <tr><td>
 	All this replication of the grace period numbers can only cause
 	massive confusion.
-	Why not just keep a global pair of counters and be done with it???
+	Why not just keep a global sequence number and be done with it???
 </td></tr>
 <tr><th align="left">Answer:</th></tr>
 <tr><td bgcolor="#ffffff"><font color="ffffff">
-	Because if there was only a single global pair of grace-period
+	Because if there was only a single global sequence
 	numbers, there would need to be a single global lock to allow
-	safely accessing and updating them.
+	safely accessing and updating it.
 	And if we are not going to have a single global lock, we need
 	to carefully manage the numbers on a per-node basis.
 	Recall from the answer to a previous Quick Quiz that the consequences
@@ -1091,8 +1099,8 @@ CPU has not yet passed through a quiescent state,
 while the <tt>-&gt;core_needs_qs</tt> flag indicates that the
 RCU core needs a quiescent state from the corresponding CPU.
 The <tt>-&gt;gpwrap</tt> field indicates that the corresponding
-CPU has remained idle for so long that the <tt>completed</tt>
-and <tt>gpnum</tt> counters are in danger of overflow, which
+CPU has remained idle for so long that the
+<tt>gp_seq</tt> counter is in danger of overflow, which
 will cause the CPU to disregard the values of its counters on
 its next exit from idle.
 Finally, the <tt>rcu_qs_ctr_snap</tt> field is used to detect
@@ -1130,10 +1138,10 @@ The CPU advances the callbacks in its <tt>rcu_data</tt> structure
 whenever it notices that another RCU grace period has completed.
 The CPU detects the completion of an RCU grace period by noticing
 that the value of its <tt>rcu_data</tt> structure's
-<tt>-&gt;completed</tt> field differs from that of its leaf
+<tt>-&gt;gp_seq</tt> field differs from that of its leaf
 <tt>rcu_node</tt> structure.
 Recall that each <tt>rcu_node</tt> structure's
-<tt>-&gt;completed</tt> field is updated at the end of each
+<tt>-&gt;gp_seq</tt> field is updated at the beginnings and ends of each
 grace period.
 
 <p>
-- 
2.17.1


  parent reply	other threads:[~2018-06-26  0:11 UTC|newest]

Thread overview: 41+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-06-26  0:08 [PATCH tip/core/rcu 0/40] RCU ->gp_seq conversion for v4.19 Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 01/40] rcu: Introduce grace-period sequence numbers Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 02/40] rcu: Move rcu_gp_slow() to ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 03/40] rcu: Make rcutorture's batches-completed API use ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 04/40] rcu: Convert rcu_check_gp_kthread_starvation() to GP sequence number Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 05/40] rcu: Make quiescent-state reporting use ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 06/40] rcu: Convert conditional grace-period primitives to ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 07/40] rcu: Move RCU's grace-period-change code " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 08/40] rcu: Convert rcu_gpnum_ovf() " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 09/40] rcu: Move rcu_implicit_dynticks_qs() " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 10/40] rcu: Move rcu_try_advance_all_cbs() " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 11/40] rcu: Move rcu_nocb_gp_get() " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 12/40] rcu: Move rcu_gp_in_progress() " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 13/40] rcu: Convert ->rcu_iw_gpnum " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 14/40] rcu: Convert ->completedqs " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 15/40] rcu: Convert grace-period requests " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 16/40] rcu: Make RCU CPU stall warnings use ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 17/40] rcutorture: Convert rcutorture_get_gp_data() to ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 18/40] rcu: Move from ->need_future_gp[] to ->gp_seq_needed Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 19/40] rcu: Make rcu_nocb_wait_gp() check if GP already requested Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 20/40] rcu: Convert rcu_grace_period tracepoint to gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 21/40] rcu: Convert rcu_future_grace_period " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 22/40] rcu: Convert rcu_grace_period_init " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 23/40] rcu: Convert rcu_preempt_task tracepoint to ->gp_seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 24/40] rcu: Convert rcu_unlock_preempted_task " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 25/40] rcu: Convert rcu_quiescent_state_report " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 26/40] rcu: Convert rcu_fqs " Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 27/40] rcu: Remove ->gpnum and ->completed Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 28/40] rcu: Make simple callback acceleration refer to rdp->gp_seq_needed Paul E. McKenney
2018-06-26  0:08 ` Paul E. McKenney [this message]
2018-06-26  0:08 ` [PATCH tip/core/rcu 30/40] doc: Update memory-ordering documentation for ->gp-seq Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 31/40] doc: Update RCU CPU stall-warning documentation Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 32/40] rcu: Don't funnel-lock above leaf node if GP in progress Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 33/40] rcu: Produce last "CleanupMore" trace only if late-breaking request Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 34/40] rcu: Fix cpustart tracepoint gp_seq number Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 35/40] rcu: Make rcu_start_this_gp() check for grace period already started Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 36/40] rcutorture: Correctly handle grace-period sequence wrap Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 37/40] rcu: Regularize resetting of rcu_data wrap indicator Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 38/40] rcu: Rename the grace-period-request variables and parameters Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 39/40] rcu: Use better variable names in funnel locking loop Paul E. McKenney
2018-06-26  0:08 ` [PATCH tip/core/rcu 40/40] rcu: Identify grace period is in progress as we advance up the tree Paul E. McKenney

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180626000859.23572-29-paulmck@linux.vnet.ibm.com \
    --to=paulmck@linux.vnet.ibm.com \
    --cc=akpm@linux-foundation.org \
    --cc=dhowells@redhat.com \
    --cc=dipankar@in.ibm.com \
    --cc=edumazet@google.com \
    --cc=fweisbec@gmail.com \
    --cc=jiangshanlai@gmail.com \
    --cc=joel@joelfernandes.org \
    --cc=josh@joshtriplett.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mathieu.desnoyers@efficios.com \
    --cc=mingo@kernel.org \
    --cc=oleg@redhat.com \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=tglx@linutronix.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®