[PATCH v3 0/4] fixes, cleanups for rcu/dev

[PATCH v3 0/4] fixes, cleanups for rcu/dev

[Joel Fernandes]

Hi Paul,

Here are some patches reworked with a few comments on few of the patches
from previous series: https://lkml.org/lkml/2018/5/13/296

4/4 is a new addition which fixes a potential issue.

Please disregard the v2, and consider this v3 instead, since that v2 was
a pure patch generation mess. thanks!

Joel Fernandes (4):
  rcu: Add comment documenting how rcu_seq_snap works
  rcu: Cleanup the variables used to request a new grace period
  rcu: Use better variable names in funnel locking loop
  rcu: Unlock non-start node only after accessing its gp_seq_needed

 include/trace/events/rcu.h | 15 +++----
 kernel/rcu/rcu.h           | 33 +++++++++++++++-
 kernel/rcu/tree.c          | 80 +++++++++++++++++++++-----------------
 3 files changed, 85 insertions(+), 43 deletions(-)

-- 
2.17.0.441.gb46fe60e1d-goog

[PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Joel Fernandes]

rcu_seq_snap may be tricky to decipher. Lets document how it works with
an example to make it easier.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
 1 file changed, 32 insertions(+), 1 deletion(-)

diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
index 0453a7d12b3f..d4396c96f614 100644
--- a/kernel/rcu/rcu.h
+++ b/kernel/rcu/rcu.h
@@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
 	WRITE_ONCE(*sp, rcu_seq_endval(sp));
 }
 
-/* Take a snapshot of the update side's sequence number. */
+/*
+ * rcu_seq_snap - Take a snapshot of the update side's sequence number.
+ *
+ * This function returns the earliest value of the grace-period sequence number
+ * that will indicate that a full grace period has elapsed since the current
+ * time.  Once the grace-period sequence number has reached this value, it will
+ * be safe to invoke all callbacks that have been registered prior to the
+ * current time. This value is the current grace-period number plus two to the
+ * power of the number of low-order bits reserved for state, then rounded up to
+ * the next value in which the state bits are all zero.
+ *
+ * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
+ * the seq is used to track if a GP is in progress or not, its sufficient if we
+ * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
+ *
+ * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
+ * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
+ * to account for the shift due to 2 state bits. Now, if the current seq is
+ * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
+ * is already in progress so the next GP that a future call back will be queued
+ * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
+ * the 2 lower bits by adding 0b11. Incase the lower bit was set, the overflow
+ * will cause the extra +1 to the GP, along with the usual +1 explained before.
+ * This gives us GP+2. Finally we mask the lower to bits by ~0x3 incase the
+ * overflow didn't occur. This masking is needed because incase RCU was idle
+ * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
+ * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
+ *
+ * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
+ * which can be generalized to:
+ * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
+ */
 static inline unsigned long rcu_seq_snap(unsigned long *sp)
 {
 	unsigned long s;
-- 
2.17.0.441.gb46fe60e1d-goog

[PATCH v3 2/4] rcu: Cleanup the variables used to request a new grace period

[Joel Fernandes]

The 'c' variable was used previously to store the grace period that is
being requested. However it is not very meaningful since the gp_seq
conversions. This patch replaces it with gp_seq_req indicating that
this is the grace period that was requested. Also updating tracing with
the new name.

Previous patch discussion is at:
https://patchwork.kernel.org/patch/10396579/

Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
---
 include/trace/events/rcu.h | 15 ++++++------
 kernel/rcu/tree.c          | 50 ++++++++++++++++++++++----------------
 2 files changed, 37 insertions(+), 28 deletions(-)

diff --git a/include/trace/events/rcu.h b/include/trace/events/rcu.h
index 5373bc61ae08..a8d07feff6a0 100644
--- a/include/trace/events/rcu.h
+++ b/include/trace/events/rcu.h
@@ -103,15 +103,16 @@ TRACE_EVENT(rcu_grace_period,
  */
 TRACE_EVENT(rcu_future_grace_period,
 
-	TP_PROTO(const char *rcuname, unsigned long gp_seq, unsigned long c,
-		 u8 level, int grplo, int grphi, const char *gpevent),
+	TP_PROTO(const char *rcuname, unsigned long gp_seq,
+		 unsigned long gp_seq_req, u8 level, int grplo, int grphi,
+		 const char *gpevent),
 
-	TP_ARGS(rcuname, gp_seq, c, level, grplo, grphi, gpevent),
+	TP_ARGS(rcuname, gp_seq, gp_seq_req, level, grplo, grphi, gpevent),
 
 	TP_STRUCT__entry(
 		__field(const char *, rcuname)
 		__field(unsigned long, gp_seq)
-		__field(unsigned long, c)
+		__field(unsigned long, gp_seq_req)
 		__field(u8, level)
 		__field(int, grplo)
 		__field(int, grphi)
@@ -121,7 +122,7 @@ TRACE_EVENT(rcu_future_grace_period,
 	TP_fast_assign(
 		__entry->rcuname = rcuname;
 		__entry->gp_seq = gp_seq;
-		__entry->c = c;
+		__entry->gp_seq_req = gp_seq_req;
 		__entry->level = level;
 		__entry->grplo = grplo;
 		__entry->grphi = grphi;
@@ -129,7 +130,7 @@ TRACE_EVENT(rcu_future_grace_period,
 	),
 
 	TP_printk("%s %lu %lu %u %d %d %s",
-		  __entry->rcuname, __entry->gp_seq, __entry->c, __entry->level,
+		  __entry->rcuname, __entry->gp_seq, __entry->gp_seq_req, __entry->level,
 		  __entry->grplo, __entry->grphi, __entry->gpevent)
 );
 
@@ -751,7 +752,7 @@ TRACE_EVENT(rcu_barrier,
 #else /* #ifdef CONFIG_RCU_TRACE */
 
 #define trace_rcu_grace_period(rcuname, gp_seq, gpevent) do { } while (0)
-#define trace_rcu_future_grace_period(rcuname, gp_seq, c, \
+#define trace_rcu_future_grace_period(rcuname, gp_seq, gp_seq_req, \
 				      level, grplo, grphi, event) \
 				      do { } while (0)
 #define trace_rcu_grace_period_init(rcuname, gp_seq, level, grplo, grphi, \
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 2c06e1ab90cd..0ffd41ba304f 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1518,13 +1518,18 @@ void rcu_cpu_stall_reset(void)
 
 /* Trace-event wrapper function for trace_rcu_future_grace_period.  */
 static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
-			      unsigned long c, const char *s)
+			      unsigned long gp_seq_req, const char *s)
 {
-	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gp_seq, c,
+	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gp_seq, gp_seq_req,
 				      rnp->level, rnp->grplo, rnp->grphi, s);
 }
 
 /*
+ * rcu_start_this_gp - Request the start of a particular grace period
+ * @rnp: The leaf node of the CPU from which to start.
+ * @rdp: The rcu_data corresponding to the CPU from which to start.
+ * @gp_seq_req: The gp_seq of the grace period to start.
+ *
  * Start the specified grace period, as needed to handle newly arrived
  * callbacks.  The required future grace periods are recorded in each
  * rcu_node structure's ->gp_seq_needed field.  Returns true if there
@@ -1532,9 +1537,11 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  *
  * The caller must hold the specified rcu_node structure's ->lock, which
  * is why the caller is responsible for waking the grace-period kthread.
+ *
+ * Returns true if the GP thread needs to be awakened else false.
  */
 static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
-			      unsigned long c)
+			      unsigned long gp_seq_req)
 {
 	bool ret = false;
 	struct rcu_state *rsp = rdp->rsp;
@@ -1550,25 +1557,27 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	 * not be released.
 	 */
 	raw_lockdep_assert_held_rcu_node(rnp);
-	trace_rcu_this_gp(rnp, rdp, c, TPS("Startleaf"));
+	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
 	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
 		if (rnp_root != rnp)
 			raw_spin_lock_rcu_node(rnp_root);
-		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, c) ||
-		    rcu_seq_started(&rnp_root->gp_seq, c) ||
+		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
+		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
 		    (rnp != rnp_root &&
 		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
-			trace_rcu_this_gp(rnp_root, rdp, c, TPS("Prestarted"));
+			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
+					  TPS("Prestarted"));
 			goto unlock_out;
 		}
-		rnp_root->gp_seq_needed = c;
+		rnp_root->gp_seq_needed = gp_seq_req;
 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
 			/*
 			 * We just marked the leaf, and a grace period
 			 * is in progress, which means that rcu_gp_cleanup()
 			 * will see the marking.  Bail to reduce contention.
 			 */
-			trace_rcu_this_gp(rnp, rdp, c, TPS("Startedleaf"));
+			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
+					  TPS("Startedleaf"));
 			goto unlock_out;
 		}
 		if (rnp_root != rnp && rnp_root->parent != NULL)
@@ -1579,14 +1588,14 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 
 	/* If GP already in progress, just leave, otherwise start one. */
 	if (rcu_gp_in_progress(rsp)) {
-		trace_rcu_this_gp(rnp_root, rdp, c, TPS("Startedleafroot"));
+		trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("Startedleafroot"));
 		goto unlock_out;
 	}
-	trace_rcu_this_gp(rnp_root, rdp, c, TPS("Startedroot"));
+	trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("Startedroot"));
 	WRITE_ONCE(rsp->gp_flags, rsp->gp_flags | RCU_GP_FLAG_INIT);
 	rsp->gp_req_activity = jiffies;
 	if (!rsp->gp_kthread) {
-		trace_rcu_this_gp(rnp_root, rdp, c, TPS("NoGPkthread"));
+		trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("NoGPkthread"));
 		goto unlock_out;
 	}
 	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
@@ -1595,9 +1604,9 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	if (rnp != rnp_root)
 		raw_spin_unlock_rcu_node(rnp_root);
 	/* Push furthest requested GP to leaf node and rcu_data structure. */
-	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, c)) {
-		rnp->gp_seq_needed = c;
-		rdp->gp_seq_needed = c;
+	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req)) {
+		rnp->gp_seq_needed = gp_seq_req;
+		rdp->gp_seq_needed = gp_seq_req;
 	}
 	return ret;
 }
@@ -1608,14 +1617,13 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  */
 static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
-	unsigned long c = rnp->gp_seq;
 	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	needmore = ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed);
 	if (!needmore)
 		rnp->gp_seq_needed = rnp->gp_seq; /* Avoid counter wrap. */
-	trace_rcu_this_gp(rnp, rdp, c,
+	trace_rcu_this_gp(rnp, rdp, rnp->gp_seq,
 			  needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;
 }
@@ -1651,7 +1659,7 @@ static void rcu_gp_kthread_wake(struct rcu_state *rsp)
 static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
 			       struct rcu_data *rdp)
 {
-	unsigned long c;
+	unsigned long gp_seq_req;
 	bool ret = false;
 
 	raw_lockdep_assert_held_rcu_node(rnp);
@@ -1670,9 +1678,9 @@ static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
 	 * accelerating callback invocation to an earlier grace-period
 	 * number.
 	 */
-	c = rcu_seq_snap(&rsp->gp_seq);
-	if (rcu_segcblist_accelerate(&rdp->cblist, c))
-		ret = rcu_start_this_gp(rnp, rdp, c);
+	gp_seq_req = rcu_seq_snap(&rsp->gp_seq);
+	if (rcu_segcblist_accelerate(&rdp->cblist, gp_seq_req))
+		ret = rcu_start_this_gp(rnp, rdp, gp_seq_req);
 
 	/* Trace depending on how much we were able to accelerate. */
 	if (rcu_segcblist_restempty(&rdp->cblist, RCU_WAIT_TAIL))
-- 
2.17.0.441.gb46fe60e1d-goog

[PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Joel Fernandes]

The funnel locking loop in rcu_start_this_gp uses rcu_root as a
temporary variable while walking the combining tree. This causes a
tiresome exercise of a code reader reminding themselves that rcu_root
may not be root. Lets just call it rnp, and rename other variables as
well to be more appropriate.

Original patch: https://patchwork.kernel.org/patch/10396577/

Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
---
 kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
 1 file changed, 25 insertions(+), 23 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 0ffd41ba304f..879c67a31116 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 
 /*
  * rcu_start_this_gp - Request the start of a particular grace period
- * @rnp: The leaf node of the CPU from which to start.
+ * @rnp_start: The leaf node of the CPU from which to start.
  * @rdp: The rcu_data corresponding to the CPU from which to start.
  * @gp_seq_req: The gp_seq of the grace period to start.
  *
@@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  *
  * Returns true if the GP thread needs to be awakened else false.
  */
-static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
+static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
 			      unsigned long gp_seq_req)
 {
 	bool ret = false;
 	struct rcu_state *rsp = rdp->rsp;
-	struct rcu_node *rnp_root;
+	struct rcu_node *rnp, *rnp_root = NULL;
 
 	/*
 	 * Use funnel locking to either acquire the root rcu_node
@@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	 * scan the leaf rcu_node structures.  Note that rnp->lock must
 	 * not be released.
 	 */
-	raw_lockdep_assert_held_rcu_node(rnp);
-	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
-	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
-		if (rnp_root != rnp)
-			raw_spin_lock_rcu_node(rnp_root);
-		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
-		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
-		    (rnp != rnp_root &&
-		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
-			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
+	raw_lockdep_assert_held_rcu_node(rnp_start);
+	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
+	for (rnp = rnp_start; 1; rnp = rnp->parent) {
+		if (rnp != rnp_start)
+			raw_spin_lock_rcu_node(rnp);
+		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
+		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
+		    (rnp != rnp_start &&
+		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
+			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
 					  TPS("Prestarted"));
 			goto unlock_out;
 		}
-		rnp_root->gp_seq_needed = gp_seq_req;
-		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
+		rnp->gp_seq_needed = gp_seq_req;
+		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {
 			/*
 			 * We just marked the leaf, and a grace period
 			 * is in progress, which means that rcu_gp_cleanup()
 			 * will see the marking.  Bail to reduce contention.
 			 */
-			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
+			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
 					  TPS("Startedleaf"));
 			goto unlock_out;
 		}
-		if (rnp_root != rnp && rnp_root->parent != NULL)
-			raw_spin_unlock_rcu_node(rnp_root);
-		if (!rnp_root->parent)
+		if (rnp != rnp_start && rnp->parent != NULL)
+			raw_spin_unlock_rcu_node(rnp);
+		if (!rnp->parent) {
+			rnp_root = rnp;
 			break;  /* At root, and perhaps also leaf. */
+		}
 	}
 
 	/* If GP already in progress, just leave, otherwise start one. */
@@ -1601,11 +1603,11 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
 	ret = true;  /* Caller must wake GP kthread. */
 unlock_out:
-	if (rnp != rnp_root)
-		raw_spin_unlock_rcu_node(rnp_root);
+	if (rnp != rnp_start)
+		raw_spin_unlock_rcu_node(rnp);
 	/* Push furthest requested GP to leaf node and rcu_data structure. */
-	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req)) {
-		rnp->gp_seq_needed = gp_seq_req;
+	if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req)) {
+		rnp_start->gp_seq_needed = gp_seq_req;
 		rdp->gp_seq_needed = gp_seq_req;
 	}
 	return ret;
-- 
2.17.0.441.gb46fe60e1d-goog

[PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Joel Fernandes]

We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
after the access.

Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
---
 kernel/rcu/tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 879c67a31116..efbd21b2a1a6 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1603,13 +1603,13 @@ static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
 	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
 	ret = true;  /* Caller must wake GP kthread. */
 unlock_out:
-	if (rnp != rnp_start)
-		raw_spin_unlock_rcu_node(rnp);
 	/* Push furthest requested GP to leaf node and rcu_data structure. */
 	if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req)) {
 		rnp_start->gp_seq_needed = gp_seq_req;
 		rdp->gp_seq_needed = gp_seq_req;
 	}
+	if (rnp != rnp_start)
+		raw_spin_unlock_rcu_node(rnp);
 	return ret;
 }
 
-- 
2.17.0.441.gb46fe60e1d-goog

Re: [PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Randy Dunlap]

On 05/20/2018 09:42 PM, Joel Fernandes wrote:
> rcu_seq_snap may be tricky to decipher. Lets document how it works with
> an example to make it easier.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
>  1 file changed, 32 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> index 0453a7d12b3f..d4396c96f614 100644
> --- a/kernel/rcu/rcu.h
> +++ b/kernel/rcu/rcu.h
> @@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
>  	WRITE_ONCE(*sp, rcu_seq_endval(sp));
>  }
>  
> -/* Take a snapshot of the update side's sequence number. */
> +/*
> + * rcu_seq_snap - Take a snapshot of the update side's sequence number.
> + *
> + * This function returns the earliest value of the grace-period sequence number
> + * that will indicate that a full grace period has elapsed since the current
> + * time.  Once the grace-period sequence number has reached this value, it will
> + * be safe to invoke all callbacks that have been registered prior to the
> + * current time. This value is the current grace-period number plus two to the
> + * power of the number of low-order bits reserved for state, then rounded up to
> + * the next value in which the state bits are all zero.
> + *
> + * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
> + * the seq is used to track if a GP is in progress or not, its sufficient if we

                                                              it's

> + * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
> + *
> + * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
> + * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
> + * to account for the shift due to 2 state bits. Now, if the current seq is
> + * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
> + * is already in progress so the next GP that a future call back will be queued
> + * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
> + * the 2 lower bits by adding 0b11. Incase the lower bit was set, the overflow

                                       In case

> + * will cause the extra +1 to the GP, along with the usual +1 explained before.
> + * This gives us GP+2. Finally we mask the lower to bits by ~0x3 incase the

                                                                    in case

> + * overflow didn't occur. This masking is needed because incase RCU was idle

                                                            in case

> + * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
> + * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
> + *
> + * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
> + * which can be generalized to:
> + * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
> + */
>  static inline unsigned long rcu_seq_snap(unsigned long *sp)
>  {
>  	unsigned long s;
> 

cheers.
-- 
~Randy

Re: [PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Joel Fernandes]

On Sun, May 20, 2018 at 09:50:25PM -0700, Randy Dunlap wrote:
> On 05/20/2018 09:42 PM, Joel Fernandes wrote:
> > rcu_seq_snap may be tricky to decipher. Lets document how it works with
> > an example to make it easier.
> > 
> > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > ---
> >  kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
> >  1 file changed, 32 insertions(+), 1 deletion(-)
> > 
> > diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> > index 0453a7d12b3f..d4396c96f614 100644
> > --- a/kernel/rcu/rcu.h
> > +++ b/kernel/rcu/rcu.h
> > @@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
> >  	WRITE_ONCE(*sp, rcu_seq_endval(sp));
> >  }
> >  
> > -/* Take a snapshot of the update side's sequence number. */
> > +/*
> > + * rcu_seq_snap - Take a snapshot of the update side's sequence number.
> > + *
> > + * This function returns the earliest value of the grace-period sequence number
> > + * that will indicate that a full grace period has elapsed since the current
> > + * time.  Once the grace-period sequence number has reached this value, it will
> > + * be safe to invoke all callbacks that have been registered prior to the
> > + * current time. This value is the current grace-period number plus two to the
> > + * power of the number of low-order bits reserved for state, then rounded up to
> > + * the next value in which the state bits are all zero.
> > + *
> > + * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
> > + * the seq is used to track if a GP is in progress or not, its sufficient if we
> 
>                                                               it's
> 
> > + * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
> > + *
> > + * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
> > + * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
> > + * to account for the shift due to 2 state bits. Now, if the current seq is
> > + * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
> > + * is already in progress so the next GP that a future call back will be queued
> > + * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
> > + * the 2 lower bits by adding 0b11. Incase the lower bit was set, the overflow
> 
>                                        In case
> 
> > + * will cause the extra +1 to the GP, along with the usual +1 explained before.
> > + * This gives us GP+2. Finally we mask the lower to bits by ~0x3 incase the
> 
>                                                                     in case
> 
> > + * overflow didn't occur. This masking is needed because incase RCU was idle
> 
>                                                             in case
> 
> > + * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
> > + * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
> > + *
> > + * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
> > + * which can be generalized to:
> > + * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
> > + */
> >  static inline unsigned long rcu_seq_snap(unsigned long *sp)
> >  {
> >  	unsigned long s;
> > 
> 
> cheers.
> -- 
> ~Randy

Thanks Randy. Fixed, updated patch below. Paul, let me know if you want
me to send it separately or if you can pick it up from below.

Also I realize I need some better automated tools to catch these issues
(spelling errors in commit, diffs etc). Probably checkpatch.pl should
have such checks for these common things too.

----------8<----------

>From 1c1f8ce04bca656a3c07e555048545d4a59e44cf Mon Sep 17 00:00:00 2001
From: Joel Fernandes <joel@joelfernandes.org>
Date: Sun, 20 May 2018 19:37:18 -0700
Subject: [PATCH v3.5] rcu: Add comment documenting how rcu_seq_snap works

rcu_seq_snap may be tricky to decipher. Lets document how it works with
an example to make it easier.

Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
---
 kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
 1 file changed, 32 insertions(+), 1 deletion(-)

diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
index 0453a7d12b3f..00df3da98317 100644
--- a/kernel/rcu/rcu.h
+++ b/kernel/rcu/rcu.h
@@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
 	WRITE_ONCE(*sp, rcu_seq_endval(sp));
 }
 
-/* Take a snapshot of the update side's sequence number. */
+/*
+ * rcu_seq_snap - Take a snapshot of the update side's sequence number.
+ *
+ * This function returns the earliest value of the grace-period sequence number
+ * that will indicate that a full grace period has elapsed since the current
+ * time.  Once the grace-period sequence number has reached this value, it will
+ * be safe to invoke all callbacks that have been registered prior to the
+ * current time. This value is the current grace-period number plus two to the
+ * power of the number of low-order bits reserved for state, then rounded up to
+ * the next value in which the state bits are all zero.
+ *
+ * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
+ * the seq is used to track if a GP is in progress or not, its sufficient if we
+ * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
+ *
+ * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
+ * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
+ * to account for the shift due to 2 state bits. Now, if the current seq is
+ * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
+ * is already in progress so the next GP that a future call back will be queued
+ * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
+ * the 2 lower bits by adding 0b11. In case the lower bit was set, the overflow
+ * will cause the extra +1 to the GP, along with the usual +1 explained before.
+ * This gives us GP+2. Finally we mask the lower to bits by ~0x3 in case the
+ * overflow didn't occur. This masking is needed because in case RCU was idle
+ * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
+ * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
+ *
+ * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
+ * which can be generalized to:
+ * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
+ */
 static inline unsigned long rcu_seq_snap(unsigned long *sp)
 {
 	unsigned long s;
-- 
2.17.0.441.gb46fe60e1d-goog

Re: [PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Randy Dunlap]

On 05/20/2018 10:48 PM, Joel Fernandes wrote:

> ----------8<----------
> 
> From 1c1f8ce04bca656a3c07e555048545d4a59e44cf Mon Sep 17 00:00:00 2001
> From: Joel Fernandes <joel@joelfernandes.org>
> Date: Sun, 20 May 2018 19:37:18 -0700
> Subject: [PATCH v3.5] rcu: Add comment documenting how rcu_seq_snap works
> 
> rcu_seq_snap may be tricky to decipher. Lets document how it works with
> an example to make it easier.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
>  1 file changed, 32 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> index 0453a7d12b3f..00df3da98317 100644
> --- a/kernel/rcu/rcu.h
> +++ b/kernel/rcu/rcu.h
> @@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
>  	WRITE_ONCE(*sp, rcu_seq_endval(sp));
>  }
>  
> -/* Take a snapshot of the update side's sequence number. */
> +/*
> + * rcu_seq_snap - Take a snapshot of the update side's sequence number.
> + *
> + * This function returns the earliest value of the grace-period sequence number
> + * that will indicate that a full grace period has elapsed since the current
> + * time.  Once the grace-period sequence number has reached this value, it will
> + * be safe to invoke all callbacks that have been registered prior to the
> + * current time. This value is the current grace-period number plus two to the
> + * power of the number of low-order bits reserved for state, then rounded up to
> + * the next value in which the state bits are all zero.
> + *
> + * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
> + * the seq is used to track if a GP is in progress or not, its sufficient if we

                                                              it's

> + * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
> + *
> + * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
> + * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
> + * to account for the shift due to 2 state bits. Now, if the current seq is
> + * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
> + * is already in progress so the next GP that a future call back will be queued
> + * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
> + * the 2 lower bits by adding 0b11. In case the lower bit was set, the overflow
> + * will cause the extra +1 to the GP, along with the usual +1 explained before.
> + * This gives us GP+2. Finally we mask the lower to bits by ~0x3 in case the
> + * overflow didn't occur. This masking is needed because in case RCU was idle
> + * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
> + * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
> + *
> + * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
> + * which can be generalized to:
> + * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
> + */
>  static inline unsigned long rcu_seq_snap(unsigned long *sp)
>  {
>  	unsigned long s;
> 


-- 
~Randy

Re: [PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Joe Perches]

On Sun, 2018-05-20 at 22:48 -0700, Joel Fernandes wrote:
> Also I realize I need some better automated tools to catch these issues
> (spelling errors in commit, diffs etc). Probably checkpatch.pl should
> have such checks for these common things too.

checkpatch already does typo checking using the input file
scripts/spelling.txt.

You are welcome to add more typos to that file.

and fyi: 'incase||in case' is not there, perhaps because
it is a alternate spelling of encase, but it does seem
every use of "incase" in the kernel should be "in case"

$ git grep -w -i incase | wc -l
43

Re: [PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Paul E. McKenney]

On Sun, May 20, 2018 at 09:42:19PM -0700, Joel Fernandes wrote:
> The funnel locking loop in rcu_start_this_gp uses rcu_root as a
> temporary variable while walking the combining tree. This causes a
> tiresome exercise of a code reader reminding themselves that rcu_root
> may not be root. Lets just call it rnp, and rename other variables as
> well to be more appropriate.
> 
> Original patch: https://patchwork.kernel.org/patch/10396577/
> 
> Signed-off-by: Joel Fernandes <joel@joelfernandes.org>

Nice!

Please see feedback interspersed below.

						Thanx, Paul

> ---
>  kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
>  1 file changed, 25 insertions(+), 23 deletions(-)
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 0ffd41ba304f..879c67a31116 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> 
>  /*
>   * rcu_start_this_gp - Request the start of a particular grace period
> - * @rnp: The leaf node of the CPU from which to start.
> + * @rnp_start: The leaf node of the CPU from which to start.
>   * @rdp: The rcu_data corresponding to the CPU from which to start.
>   * @gp_seq_req: The gp_seq of the grace period to start.
>   *
> @@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
>   *
>   * Returns true if the GP thread needs to be awakened else false.
>   */
> -static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> +static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
>  			      unsigned long gp_seq_req)
>  {
>  	bool ret = false;
>  	struct rcu_state *rsp = rdp->rsp;
> -	struct rcu_node *rnp_root;
> +	struct rcu_node *rnp, *rnp_root = NULL;

Unless I am going blind, this patch really isn't using rnp_root.  It
could be removed.

> 
>  	/*
>  	 * Use funnel locking to either acquire the root rcu_node
> @@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
>  	 * scan the leaf rcu_node structures.  Note that rnp->lock must
>  	 * not be released.
>  	 */
> -	raw_lockdep_assert_held_rcu_node(rnp);
> -	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
> -	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> -		if (rnp_root != rnp)
> -			raw_spin_lock_rcu_node(rnp_root);
> -		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
> -		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
> -		    (rnp != rnp_root &&
> -		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
> -			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
> +	raw_lockdep_assert_held_rcu_node(rnp_start);
> +	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
> +	for (rnp = rnp_start; 1; rnp = rnp->parent) {
> +		if (rnp != rnp_start)
> +			raw_spin_lock_rcu_node(rnp);
> +		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
> +		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
> +		    (rnp != rnp_start &&
> +		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
> +			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
>  					  TPS("Prestarted"));
>  			goto unlock_out;
>  		}
> -		rnp_root->gp_seq_needed = gp_seq_req;
> -		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> +		rnp->gp_seq_needed = gp_seq_req;
> +		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {

The original had a performance bug, which is quite a bit more obvious
given the new names, so thank you for that!  The above statement should
instead be as follows:

		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {

It does not make sense to keep checking the starting rcu_node because
changes to ->gp_seq happen first at the top of the tree.  So we might
take an earlier exit by checking the current rnp instead of rechecking
rnp_start over and over.

Please feel free to make this change, which is probably best as a separate
patch.  That way this rename patch can remain a straightforward rename patch.

>  			/*
>  			 * We just marked the leaf, and a grace period
>  			 * is in progress, which means that rcu_gp_cleanup()
>  			 * will see the marking.  Bail to reduce contention.
>  			 */
> -			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> +			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
>  					  TPS("Startedleaf"));
>  			goto unlock_out;
>  		}
> -		if (rnp_root != rnp && rnp_root->parent != NULL)
> -			raw_spin_unlock_rcu_node(rnp_root);
> -		if (!rnp_root->parent)
> +		if (rnp != rnp_start && rnp->parent != NULL)
> +			raw_spin_unlock_rcu_node(rnp);
> +		if (!rnp->parent) {
> +			rnp_root = rnp;

Since rnp_root is otherwise unused in the new version, the above statement
can be dropped along with the "if" statement's braces and the declaration.

>  			break;  /* At root, and perhaps also leaf. */
> +		}
>  	}
> 
>  	/* If GP already in progress, just leave, otherwise start one. */
> @@ -1601,11 +1603,11 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
>  	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
>  	ret = true;  /* Caller must wake GP kthread. */
>  unlock_out:
> -	if (rnp != rnp_root)
> -		raw_spin_unlock_rcu_node(rnp_root);
> +	if (rnp != rnp_start)
> +		raw_spin_unlock_rcu_node(rnp);
>  	/* Push furthest requested GP to leaf node and rcu_data structure. */
> -	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req)) {
> -		rnp->gp_seq_needed = gp_seq_req;
> +	if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req)) {
> +		rnp_start->gp_seq_needed = gp_seq_req;
>  		rdp->gp_seq_needed = gp_seq_req;
>  	}
>  	return ret;
> -- 
> 2.17.0.441.gb46fe60e1d-goog
> 

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Paul E. McKenney]

On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> after the access.

Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
so nothing else is accessing it.  Or at least that is the intent.  ;-)

One exception is CPU hotplug, but in that case, only the CPU doing the
hotplugging is allowed to touch rdp->gp_seq_needed and even then only
while the incoming/outgoing CPU is inactive.

							Thanx, Paul

> Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
> ---
>  kernel/rcu/tree.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index 879c67a31116..efbd21b2a1a6 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -1603,13 +1603,13 @@ static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
>  	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
>  	ret = true;  /* Caller must wake GP kthread. */
>  unlock_out:
> -	if (rnp != rnp_start)
> -		raw_spin_unlock_rcu_node(rnp);
>  	/* Push furthest requested GP to leaf node and rcu_data structure. */
>  	if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req)) {
>  		rnp_start->gp_seq_needed = gp_seq_req;
>  		rdp->gp_seq_needed = gp_seq_req;
>  	}
> +	if (rnp != rnp_start)
> +		raw_spin_unlock_rcu_node(rnp);
>  	return ret;
>  }
> 
> -- 
> 2.17.0.441.gb46fe60e1d-goog
> 

Re: [PATCH v3 2/4] rcu: Cleanup the variables used to request a new grace period

[Paul E. McKenney]

On Sun, May 20, 2018 at 09:42:18PM -0700, Joel Fernandes wrote:
> The 'c' variable was used previously to store the grace period that is
> being requested. However it is not very meaningful since the gp_seq
> conversions. This patch replaces it with gp_seq_req indicating that
> this is the grace period that was requested. Also updating tracing with
> the new name.
> 
> Previous patch discussion is at:
> https://patchwork.kernel.org/patch/10396579/
> 
> Signed-off-by: Joel Fernandes <joel@joelfernandes.org>

Very good, I have queued this for review and testing.  I reworked the
commit log a bit, please see below for the version that I have queued.

							Thanx, Paul

------------------------------------------------------------------------

commit e7296d223f4ea37a7dcb089fb1bdc8c78651d276
Author: Joel Fernandes <joelaf@google.com>
Date:   Sun May 20 21:42:18 2018 -0700

    rcu: Rename the grace-period-request variables and parameters
    
    The name 'c' is used for variables and parameters holding the requested
    grace-period sequence number.  However it is no longer very meaningful
    given the conversions from ->gpnum and (especially) ->completed to
    ->gp_seq. This commit therefore renames 'c' to 'gp_seq_req'.
    
    Previous patch discussion is at:
    https://patchwork.kernel.org/patch/10396579/
    
    Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/include/trace/events/rcu.h b/include/trace/events/rcu.h
index 5373bc61ae08..a8d07feff6a0 100644
--- a/include/trace/events/rcu.h
+++ b/include/trace/events/rcu.h
@@ -103,15 +103,16 @@ TRACE_EVENT(rcu_grace_period,
  */
 TRACE_EVENT(rcu_future_grace_period,
 
-	TP_PROTO(const char *rcuname, unsigned long gp_seq, unsigned long c,
-		 u8 level, int grplo, int grphi, const char *gpevent),
+	TP_PROTO(const char *rcuname, unsigned long gp_seq,
+		 unsigned long gp_seq_req, u8 level, int grplo, int grphi,
+		 const char *gpevent),
 
-	TP_ARGS(rcuname, gp_seq, c, level, grplo, grphi, gpevent),
+	TP_ARGS(rcuname, gp_seq, gp_seq_req, level, grplo, grphi, gpevent),
 
 	TP_STRUCT__entry(
 		__field(const char *, rcuname)
 		__field(unsigned long, gp_seq)
-		__field(unsigned long, c)
+		__field(unsigned long, gp_seq_req)
 		__field(u8, level)
 		__field(int, grplo)
 		__field(int, grphi)
@@ -121,7 +122,7 @@ TRACE_EVENT(rcu_future_grace_period,
 	TP_fast_assign(
 		__entry->rcuname = rcuname;
 		__entry->gp_seq = gp_seq;
-		__entry->c = c;
+		__entry->gp_seq_req = gp_seq_req;
 		__entry->level = level;
 		__entry->grplo = grplo;
 		__entry->grphi = grphi;
@@ -129,7 +130,7 @@ TRACE_EVENT(rcu_future_grace_period,
 	),
 
 	TP_printk("%s %lu %lu %u %d %d %s",
-		  __entry->rcuname, __entry->gp_seq, __entry->c, __entry->level,
+		  __entry->rcuname, __entry->gp_seq, __entry->gp_seq_req, __entry->level,
 		  __entry->grplo, __entry->grphi, __entry->gpevent)
 );
 
@@ -751,7 +752,7 @@ TRACE_EVENT(rcu_barrier,
 #else /* #ifdef CONFIG_RCU_TRACE */
 
 #define trace_rcu_grace_period(rcuname, gp_seq, gpevent) do { } while (0)
-#define trace_rcu_future_grace_period(rcuname, gp_seq, c, \
+#define trace_rcu_future_grace_period(rcuname, gp_seq, gp_seq_req, \
 				      level, grplo, grphi, event) \
 				      do { } while (0)
 #define trace_rcu_grace_period_init(rcuname, gp_seq, level, grplo, grphi, \
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 030a12839d97..106bd8d62c67 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1518,13 +1518,18 @@ void rcu_cpu_stall_reset(void)
 
 /* Trace-event wrapper function for trace_rcu_future_grace_period.  */
 static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
-			      unsigned long c, const char *s)
+			      unsigned long gp_seq_req, const char *s)
 {
-	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gp_seq, c,
+	trace_rcu_future_grace_period(rdp->rsp->name, rnp->gp_seq, gp_seq_req,
 				      rnp->level, rnp->grplo, rnp->grphi, s);
 }
 
 /*
+ * rcu_start_this_gp - Request the start of a particular grace period
+ * @rnp: The leaf node of the CPU from which to start.
+ * @rdp: The rcu_data corresponding to the CPU from which to start.
+ * @gp_seq_req: The gp_seq of the grace period to start.
+ *
  * Start the specified grace period, as needed to handle newly arrived
  * callbacks.  The required future grace periods are recorded in each
  * rcu_node structure's ->gp_seq_needed field.  Returns true if there
@@ -1532,9 +1537,11 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  *
  * The caller must hold the specified rcu_node structure's ->lock, which
  * is why the caller is responsible for waking the grace-period kthread.
+ *
+ * Returns true if the GP thread needs to be awakened else false.
  */
 static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
-			      unsigned long c)
+			      unsigned long gp_seq_req)
 {
 	bool ret = false;
 	struct rcu_state *rsp = rdp->rsp;
@@ -1550,25 +1557,27 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	 * not be released.
 	 */
 	raw_lockdep_assert_held_rcu_node(rnp);
-	trace_rcu_this_gp(rnp, rdp, c, TPS("Startleaf"));
+	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
 	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
 		if (rnp_root != rnp)
 			raw_spin_lock_rcu_node(rnp_root);
-		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, c) ||
-		    rcu_seq_started(&rnp_root->gp_seq, c) ||
+		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
+		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
 		    (rnp != rnp_root &&
 		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
-			trace_rcu_this_gp(rnp_root, rdp, c, TPS("Prestarted"));
+			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
+					  TPS("Prestarted"));
 			goto unlock_out;
 		}
-		rnp_root->gp_seq_needed = c;
+		rnp_root->gp_seq_needed = gp_seq_req;
 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
 			/*
 			 * We just marked the leaf, and a grace period
 			 * is in progress, which means that rcu_gp_cleanup()
 			 * will see the marking.  Bail to reduce contention.
 			 */
-			trace_rcu_this_gp(rnp, rdp, c, TPS("Startedleaf"));
+			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
+					  TPS("Startedleaf"));
 			goto unlock_out;
 		}
 		if (rnp_root != rnp && rnp_root->parent != NULL)
@@ -1579,14 +1588,14 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 
 	/* If GP already in progress, just leave, otherwise start one. */
 	if (rcu_gp_in_progress(rsp)) {
-		trace_rcu_this_gp(rnp_root, rdp, c, TPS("Startedleafroot"));
+		trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("Startedleafroot"));
 		goto unlock_out;
 	}
-	trace_rcu_this_gp(rnp_root, rdp, c, TPS("Startedroot"));
+	trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("Startedroot"));
 	WRITE_ONCE(rsp->gp_flags, rsp->gp_flags | RCU_GP_FLAG_INIT);
 	rsp->gp_req_activity = jiffies;
 	if (!rsp->gp_kthread) {
-		trace_rcu_this_gp(rnp_root, rdp, c, TPS("NoGPkthread"));
+		trace_rcu_this_gp(rnp_root, rdp, gp_seq_req, TPS("NoGPkthread"));
 		goto unlock_out;
 	}
 	trace_rcu_grace_period(rsp->name, READ_ONCE(rsp->gp_seq), TPS("newreq"));
@@ -1595,9 +1604,9 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	if (rnp != rnp_root)
 		raw_spin_unlock_rcu_node(rnp_root);
 	/* Push furthest requested GP to leaf node and rcu_data structure. */
-	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, c)) {
-		rnp->gp_seq_needed = c;
-		rdp->gp_seq_needed = c;
+	if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req)) {
+		rnp->gp_seq_needed = gp_seq_req;
+		rdp->gp_seq_needed = gp_seq_req;
 	}
 	return ret;
 }
@@ -1608,14 +1617,13 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  */
 static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
-	unsigned long c = rnp->gp_seq;
 	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	needmore = ULONG_CMP_LT(rnp->gp_seq, rnp->gp_seq_needed);
 	if (!needmore)
 		rnp->gp_seq_needed = rnp->gp_seq; /* Avoid counter wrap. */
-	trace_rcu_this_gp(rnp, rdp, c,
+	trace_rcu_this_gp(rnp, rdp, rnp->gp_seq,
 			  needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;
 }
@@ -1651,7 +1659,7 @@ static void rcu_gp_kthread_wake(struct rcu_state *rsp)
 static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
 			       struct rcu_data *rdp)
 {
-	unsigned long c;
+	unsigned long gp_seq_req;
 	bool ret = false;
 
 	raw_lockdep_assert_held_rcu_node(rnp);
@@ -1670,9 +1678,9 @@ static bool rcu_accelerate_cbs(struct rcu_state *rsp, struct rcu_node *rnp,
 	 * accelerating callback invocation to an earlier grace-period
 	 * number.
 	 */
-	c = rcu_seq_snap(&rsp->gp_seq);
-	if (rcu_segcblist_accelerate(&rdp->cblist, c))
-		ret = rcu_start_this_gp(rnp, rdp, c);
+	gp_seq_req = rcu_seq_snap(&rsp->gp_seq);
+	if (rcu_segcblist_accelerate(&rdp->cblist, gp_seq_req))
+		ret = rcu_start_this_gp(rnp, rdp, gp_seq_req);
 
 	/* Trace depending on how much we were able to accelerate. */
 	if (rcu_segcblist_restempty(&rdp->cblist, RCU_WAIT_TAIL))

Re: [PATCH v3 2/4] rcu: Cleanup the variables used to request a new grace period

[Joel Fernandes]

On Mon, May 21, 2018 at 04:39:34PM -0700, Paul E. McKenney wrote:
> On Sun, May 20, 2018 at 09:42:18PM -0700, Joel Fernandes wrote:
> > The 'c' variable was used previously to store the grace period that is
> > being requested. However it is not very meaningful since the gp_seq
> > conversions. This patch replaces it with gp_seq_req indicating that
> > this is the grace period that was requested. Also updating tracing with
> > the new name.
> > 
> > Previous patch discussion is at:
> > https://patchwork.kernel.org/patch/10396579/
> > 
> > Signed-off-by: Joel Fernandes <joel@joelfernandes.org>
> 
> Very good, I have queued this for review and testing.  I reworked the
> commit log a bit, please see below for the version that I have queued.

Yes, commit log looks good, thanks for queuing it!

thanks,

 - Joel
 

Re: [PATCH v3 1/4] rcu: Add comment documenting how rcu_seq_snap works

[Paul E. McKenney]

On Sun, May 20, 2018 at 10:48:26PM -0700, Joel Fernandes wrote:
> On Sun, May 20, 2018 at 09:50:25PM -0700, Randy Dunlap wrote:
> > On 05/20/2018 09:42 PM, Joel Fernandes wrote:
> > > rcu_seq_snap may be tricky to decipher. Lets document how it works with
> > > an example to make it easier.
> > > 
> > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > > ---
> > >  kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
> > >  1 file changed, 32 insertions(+), 1 deletion(-)
> > > 
> > > diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> > > index 0453a7d12b3f..d4396c96f614 100644
> > > --- a/kernel/rcu/rcu.h
> > > +++ b/kernel/rcu/rcu.h
> > > @@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
> > >  	WRITE_ONCE(*sp, rcu_seq_endval(sp));
> > >  }
> > >  
> > > -/* Take a snapshot of the update side's sequence number. */
> > > +/*
> > > + * rcu_seq_snap - Take a snapshot of the update side's sequence number.
> > > + *
> > > + * This function returns the earliest value of the grace-period sequence number
> > > + * that will indicate that a full grace period has elapsed since the current
> > > + * time.  Once the grace-period sequence number has reached this value, it will
> > > + * be safe to invoke all callbacks that have been registered prior to the
> > > + * current time. This value is the current grace-period number plus two to the
> > > + * power of the number of low-order bits reserved for state, then rounded up to
> > > + * the next value in which the state bits are all zero.
> > > + *
> > > + * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
> > > + * the seq is used to track if a GP is in progress or not, its sufficient if we
> > 
> >                                                               it's
> > 
> > > + * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
> > > + *
> > > + * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
> > > + * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
> > > + * to account for the shift due to 2 state bits. Now, if the current seq is
> > > + * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
> > > + * is already in progress so the next GP that a future call back will be queued
> > > + * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
> > > + * the 2 lower bits by adding 0b11. Incase the lower bit was set, the overflow
> > 
> >                                        In case
> > 
> > > + * will cause the extra +1 to the GP, along with the usual +1 explained before.
> > > + * This gives us GP+2. Finally we mask the lower to bits by ~0x3 incase the
> > 
> >                                                                     in case
> > 
> > > + * overflow didn't occur. This masking is needed because incase RCU was idle
> > 
> >                                                             in case
> > 
> > > + * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
> > > + * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
> > > + *
> > > + * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
> > > + * which can be generalized to:
> > > + * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
> > > + */
> > >  static inline unsigned long rcu_seq_snap(unsigned long *sp)
> > >  {
> > >  	unsigned long s;
> > > 
> > 
> > cheers.
> > -- 
> > ~Randy
> 
> Thanks Randy. Fixed, updated patch below. Paul, let me know if you want
> me to send it separately or if you can pick it up from below.
> 
> Also I realize I need some better automated tools to catch these issues
> (spelling errors in commit, diffs etc). Probably checkpatch.pl should
> have such checks for these common things too.

Indeed it does!

Please resend this with the updated rnp_start patch, with the additional
change noted by Randy.  Or just change to "it is", which allows you to
have one less situation where you need to worry about the apostrophes.

							Thanx, Paul

> ----------8<----------
> 
> >From 1c1f8ce04bca656a3c07e555048545d4a59e44cf Mon Sep 17 00:00:00 2001
> From: Joel Fernandes <joel@joelfernandes.org>
> Date: Sun, 20 May 2018 19:37:18 -0700
> Subject: [PATCH v3.5] rcu: Add comment documenting how rcu_seq_snap works
> 
> rcu_seq_snap may be tricky to decipher. Lets document how it works with
> an example to make it easier.
> 
> Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> ---
>  kernel/rcu/rcu.h | 33 ++++++++++++++++++++++++++++++++-
>  1 file changed, 32 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> index 0453a7d12b3f..00df3da98317 100644
> --- a/kernel/rcu/rcu.h
> +++ b/kernel/rcu/rcu.h
> @@ -91,7 +91,38 @@ static inline void rcu_seq_end(unsigned long *sp)
>  	WRITE_ONCE(*sp, rcu_seq_endval(sp));
>  }
> 
> -/* Take a snapshot of the update side's sequence number. */
> +/*
> + * rcu_seq_snap - Take a snapshot of the update side's sequence number.
> + *
> + * This function returns the earliest value of the grace-period sequence number
> + * that will indicate that a full grace period has elapsed since the current
> + * time.  Once the grace-period sequence number has reached this value, it will
> + * be safe to invoke all callbacks that have been registered prior to the
> + * current time. This value is the current grace-period number plus two to the
> + * power of the number of low-order bits reserved for state, then rounded up to
> + * the next value in which the state bits are all zero.
> + *
> + * For example, since RCU_SEQ_STATE_MASK=3 and the least significant bit of
> + * the seq is used to track if a GP is in progress or not, its sufficient if we
> + * add (6+1) and mask with ~3 to get the next GP. Let's see why with an example:
> + *
> + * Say the current seq is 12 which is 0b1100 (GP is 3 and state bits are 0b00).
> + * To get to the next GP number of 4, we have to add 0b100 to this (0x1 << 2)
> + * to account for the shift due to 2 state bits. Now, if the current seq is
> + * 13 (GP is 3 and state bits are 0b01), then it means the current grace period
> + * is already in progress so the next GP that a future call back will be queued
> + * to run at is GP+2 = 5, not 4. To account for the extra +1, we just overflow
> + * the 2 lower bits by adding 0b11. In case the lower bit was set, the overflow
> + * will cause the extra +1 to the GP, along with the usual +1 explained before.
> + * This gives us GP+2. Finally we mask the lower to bits by ~0x3 in case the
> + * overflow didn't occur. This masking is needed because in case RCU was idle
> + * (no GP in progress so lower 2 bits are 0b00), then the overflow of the lower
> + * 2 state bits wouldn't occur, so we mask to zero out those lower 2 bits.
> + *
> + * In other words, the next seq can be obtained by (0b11 + 0b100) & (~0b11)
> + * which can be generalized to:
> + * seq + (RCU_SEQ_STATE_MASK + (RCU_SEQ_STATE_MASK + 1)) & (~RCU_SEQ_STATE_MASK)
> + */
>  static inline unsigned long rcu_seq_snap(unsigned long *sp)
>  {
>  	unsigned long s;
> -- 
> 2.17.0.441.gb46fe60e1d-goog
> 

Re: [PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Joel Fernandes]

On Mon, May 21, 2018 at 04:13:57PM -0700, Paul E. McKenney wrote:
> > ---
> >  kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
> >  1 file changed, 25 insertions(+), 23 deletions(-)
> > 
> > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > index 0ffd41ba304f..879c67a31116 100644
> > --- a/kernel/rcu/tree.c
> > +++ b/kernel/rcu/tree.c
> > @@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > 
> >  /*
> >   * rcu_start_this_gp - Request the start of a particular grace period
> > - * @rnp: The leaf node of the CPU from which to start.
> > + * @rnp_start: The leaf node of the CPU from which to start.
> >   * @rdp: The rcu_data corresponding to the CPU from which to start.
> >   * @gp_seq_req: The gp_seq of the grace period to start.
> >   *
> > @@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> >   *
> >   * Returns true if the GP thread needs to be awakened else false.
> >   */
> > -static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > +static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
> >  			      unsigned long gp_seq_req)
> >  {
> >  	bool ret = false;
> >  	struct rcu_state *rsp = rdp->rsp;
> > -	struct rcu_node *rnp_root;
> > +	struct rcu_node *rnp, *rnp_root = NULL;
> 
> Unless I am going blind, this patch really isn't using rnp_root.  It
> could be removed.

Its just limitation of the diff tools. Your eyes are just fine and doing
great based on your review comments ;)

The rnp_root is used after we break out of the loop.

> > 
> >  	/*
> >  	 * Use funnel locking to either acquire the root rcu_node
> > @@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> >  	 * scan the leaf rcu_node structures.  Note that rnp->lock must
> >  	 * not be released.
> >  	 */
> > -	raw_lockdep_assert_held_rcu_node(rnp);
> > -	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
> > -	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> > -		if (rnp_root != rnp)
> > -			raw_spin_lock_rcu_node(rnp_root);
> > -		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
> > -		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
> > -		    (rnp != rnp_root &&
> > -		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
> > -			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
> > +	raw_lockdep_assert_held_rcu_node(rnp_start);
> > +	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
> > +	for (rnp = rnp_start; 1; rnp = rnp->parent) {
> > +		if (rnp != rnp_start)
> > +			raw_spin_lock_rcu_node(rnp);
> > +		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
> > +		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
> > +		    (rnp != rnp_start &&
> > +		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
> > +			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> >  					  TPS("Prestarted"));
> >  			goto unlock_out;
> >  		}
> > -		rnp_root->gp_seq_needed = gp_seq_req;
> > -		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > +		rnp->gp_seq_needed = gp_seq_req;
> > +		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {
> 
> The original had a performance bug, which is quite a bit more obvious
> given the new names, so thank you for that!  The above statement should
> instead be as follows:
> 
> 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> 
> It does not make sense to keep checking the starting rcu_node because
> changes to ->gp_seq happen first at the top of the tree.  So we might
> take an earlier exit by checking the current rnp instead of rechecking
> rnp_start over and over.
> 
> Please feel free to make this change, which is probably best as a separate
> patch.  That way this rename patch can remain a straightforward rename patch.

Yes, sounds like a nice optimization and I'm glad my variable renaming helped
;) I feel I should have seen it too. I can make this change and send out
with my next series as you suggest.

> >  			/*
> >  			 * We just marked the leaf, and a grace period
> >  			 * is in progress, which means that rcu_gp_cleanup()
> >  			 * will see the marking.  Bail to reduce contention.
> >  			 */
> > -			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > +			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
> >  					  TPS("Startedleaf"));
> >  			goto unlock_out;
> >  		}
> > -		if (rnp_root != rnp && rnp_root->parent != NULL)
> > -			raw_spin_unlock_rcu_node(rnp_root);
> > -		if (!rnp_root->parent)
> > +		if (rnp != rnp_start && rnp->parent != NULL)
> > +			raw_spin_unlock_rcu_node(rnp);
> > +		if (!rnp->parent) {
> > +			rnp_root = rnp;
> 
> Since rnp_root is otherwise unused in the new version, the above statement
> can be dropped along with the "if" statement's braces and the declaration.

Actually rnp_root is needed for tracing calls after we breakout of the loop.

thanks!

 - Joel
 

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Joel Fernandes]

On Mon, May 21, 2018 at 04:25:38PM -0700, Paul E. McKenney wrote:
> On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> > We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> > after the access.
> 
> Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
> the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
> so nothing else is accessing it.  Or at least that is the intent.  ;-)

I was talking about protecting the internal node's rnp->gp_seq_needed, not
the rnp_start's gp_seq_needed.

We are protecting them in the loop:

like this:
for(...)
	if (rnp != rnp_start)
		raw_spin_lock_rcu_node(rnp);
	[...]
	// access rnp->gp_seq and rnp->gp_seq_needed
	[...]
	if (rnp != rnp_start)
		raw_spin_unlock_rcu_node(rnp);

But we don't need to do such protection in unlock_out ? I'm sorry if I'm
missing something, but I'm wondering if rnp->gp_seq_needed of an internal
node can be accessed locklessly, then why can't that be done also in the
funnel locking loop - after all we are holding the rnp_start's lock through
out right?

thanks!

 - Joel
 

Re: [PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Paul E. McKenney]

On Mon, May 21, 2018 at 05:00:16PM -0700, Joel Fernandes wrote:
> On Mon, May 21, 2018 at 04:13:57PM -0700, Paul E. McKenney wrote:
> > > ---
> > >  kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
> > >  1 file changed, 25 insertions(+), 23 deletions(-)
> > > 
> > > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > > index 0ffd41ba304f..879c67a31116 100644
> > > --- a/kernel/rcu/tree.c
> > > +++ b/kernel/rcu/tree.c
> > > @@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > 
> > >  /*
> > >   * rcu_start_this_gp - Request the start of a particular grace period
> > > - * @rnp: The leaf node of the CPU from which to start.
> > > + * @rnp_start: The leaf node of the CPU from which to start.
> > >   * @rdp: The rcu_data corresponding to the CPU from which to start.
> > >   * @gp_seq_req: The gp_seq of the grace period to start.
> > >   *
> > > @@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > >   *
> > >   * Returns true if the GP thread needs to be awakened else false.
> > >   */
> > > -static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > +static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
> > >  			      unsigned long gp_seq_req)
> > >  {
> > >  	bool ret = false;
> > >  	struct rcu_state *rsp = rdp->rsp;
> > > -	struct rcu_node *rnp_root;
> > > +	struct rcu_node *rnp, *rnp_root = NULL;
> > 
> > Unless I am going blind, this patch really isn't using rnp_root.  It
> > could be removed.
> 
> Its just limitation of the diff tools. Your eyes are just fine and doing
> great based on your review comments ;)
> 
> The rnp_root is used after we break out of the loop.
> 
> > > 
> > >  	/*
> > >  	 * Use funnel locking to either acquire the root rcu_node
> > > @@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > >  	 * scan the leaf rcu_node structures.  Note that rnp->lock must
> > >  	 * not be released.
> > >  	 */
> > > -	raw_lockdep_assert_held_rcu_node(rnp);
> > > -	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
> > > -	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> > > -		if (rnp_root != rnp)
> > > -			raw_spin_lock_rcu_node(rnp_root);
> > > -		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
> > > -		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
> > > -		    (rnp != rnp_root &&
> > > -		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
> > > -			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
> > > +	raw_lockdep_assert_held_rcu_node(rnp_start);
> > > +	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
> > > +	for (rnp = rnp_start; 1; rnp = rnp->parent) {
> > > +		if (rnp != rnp_start)
> > > +			raw_spin_lock_rcu_node(rnp);
> > > +		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
> > > +		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
> > > +		    (rnp != rnp_start &&
> > > +		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
> > > +			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > >  					  TPS("Prestarted"));
> > >  			goto unlock_out;
> > >  		}
> > > -		rnp_root->gp_seq_needed = gp_seq_req;
> > > -		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > > +		rnp->gp_seq_needed = gp_seq_req;
> > > +		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {
> > 
> > The original had a performance bug, which is quite a bit more obvious
> > given the new names, so thank you for that!  The above statement should
> > instead be as follows:
> > 
> > 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > 
> > It does not make sense to keep checking the starting rcu_node because
> > changes to ->gp_seq happen first at the top of the tree.  So we might
> > take an earlier exit by checking the current rnp instead of rechecking
> > rnp_start over and over.
> > 
> > Please feel free to make this change, which is probably best as a separate
> > patch.  That way this rename patch can remain a straightforward rename patch.
> 
> Yes, sounds like a nice optimization and I'm glad my variable renaming helped
> ;) I feel I should have seen it too. I can make this change and send out
> with my next series as you suggest.
> 
> > >  			/*
> > >  			 * We just marked the leaf, and a grace period
> > >  			 * is in progress, which means that rcu_gp_cleanup()
> > >  			 * will see the marking.  Bail to reduce contention.
> > >  			 */
> > > -			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > > +			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
> > >  					  TPS("Startedleaf"));
> > >  			goto unlock_out;
> > >  		}
> > > -		if (rnp_root != rnp && rnp_root->parent != NULL)
> > > -			raw_spin_unlock_rcu_node(rnp_root);
> > > -		if (!rnp_root->parent)
> > > +		if (rnp != rnp_start && rnp->parent != NULL)
> > > +			raw_spin_unlock_rcu_node(rnp);
> > > +		if (!rnp->parent) {
> > > +			rnp_root = rnp;
> > 
> > Since rnp_root is otherwise unused in the new version, the above statement
> > can be dropped along with the "if" statement's braces and the declaration.
> 
> Actually rnp_root is needed for tracing calls after we breakout of the loop.

But at that point, rnp_root is equal to rnp, so rnp_root still isn't
really needed, correct?

							Thanx, Paul

Re: [PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Joel Fernandes]

On Mon, May 21, 2018 at 05:19:25PM -0700, Paul E. McKenney wrote:
> On Mon, May 21, 2018 at 05:00:16PM -0700, Joel Fernandes wrote:
> > On Mon, May 21, 2018 at 04:13:57PM -0700, Paul E. McKenney wrote:
> > > > ---
> > > >  kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
> > > >  1 file changed, 25 insertions(+), 23 deletions(-)
> > > > 
> > > > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > > > index 0ffd41ba304f..879c67a31116 100644
> > > > --- a/kernel/rcu/tree.c
> > > > +++ b/kernel/rcu/tree.c
> > > > @@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > 
> > > >  /*
> > > >   * rcu_start_this_gp - Request the start of a particular grace period
> > > > - * @rnp: The leaf node of the CPU from which to start.
> > > > + * @rnp_start: The leaf node of the CPU from which to start.
> > > >   * @rdp: The rcu_data corresponding to the CPU from which to start.
> > > >   * @gp_seq_req: The gp_seq of the grace period to start.
> > > >   *
> > > > @@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > >   *
> > > >   * Returns true if the GP thread needs to be awakened else false.
> > > >   */
> > > > -static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > +static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
> > > >  			      unsigned long gp_seq_req)
> > > >  {
> > > >  	bool ret = false;
> > > >  	struct rcu_state *rsp = rdp->rsp;
> > > > -	struct rcu_node *rnp_root;
> > > > +	struct rcu_node *rnp, *rnp_root = NULL;
> > > 
> > > Unless I am going blind, this patch really isn't using rnp_root.  It
> > > could be removed.
> > 
> > Its just limitation of the diff tools. Your eyes are just fine and doing
> > great based on your review comments ;)
> > 
> > The rnp_root is used after we break out of the loop.
> > 
> > > > 
> > > >  	/*
> > > >  	 * Use funnel locking to either acquire the root rcu_node
> > > > @@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > >  	 * scan the leaf rcu_node structures.  Note that rnp->lock must
> > > >  	 * not be released.
> > > >  	 */
> > > > -	raw_lockdep_assert_held_rcu_node(rnp);
> > > > -	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
> > > > -	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> > > > -		if (rnp_root != rnp)
> > > > -			raw_spin_lock_rcu_node(rnp_root);
> > > > -		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
> > > > -		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
> > > > -		    (rnp != rnp_root &&
> > > > -		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
> > > > -			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
> > > > +	raw_lockdep_assert_held_rcu_node(rnp_start);
> > > > +	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
> > > > +	for (rnp = rnp_start; 1; rnp = rnp->parent) {
> > > > +		if (rnp != rnp_start)
> > > > +			raw_spin_lock_rcu_node(rnp);
> > > > +		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
> > > > +		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
> > > > +		    (rnp != rnp_start &&
> > > > +		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
> > > > +			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > > >  					  TPS("Prestarted"));
> > > >  			goto unlock_out;
> > > >  		}
> > > > -		rnp_root->gp_seq_needed = gp_seq_req;
> > > > -		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > > > +		rnp->gp_seq_needed = gp_seq_req;
> > > > +		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {
> > > 
> > > The original had a performance bug, which is quite a bit more obvious
> > > given the new names, so thank you for that!  The above statement should
> > > instead be as follows:
> > > 
> > > 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > > 
> > > It does not make sense to keep checking the starting rcu_node because
> > > changes to ->gp_seq happen first at the top of the tree.  So we might
> > > take an earlier exit by checking the current rnp instead of rechecking
> > > rnp_start over and over.
> > > 
> > > Please feel free to make this change, which is probably best as a separate
> > > patch.  That way this rename patch can remain a straightforward rename patch.
> > 
> > Yes, sounds like a nice optimization and I'm glad my variable renaming helped
> > ;) I feel I should have seen it too. I can make this change and send out
> > with my next series as you suggest.
> > 
> > > >  			/*
> > > >  			 * We just marked the leaf, and a grace period
> > > >  			 * is in progress, which means that rcu_gp_cleanup()
> > > >  			 * will see the marking.  Bail to reduce contention.
> > > >  			 */
> > > > -			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > > > +			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
> > > >  					  TPS("Startedleaf"));
> > > >  			goto unlock_out;
> > > >  		}
> > > > -		if (rnp_root != rnp && rnp_root->parent != NULL)
> > > > -			raw_spin_unlock_rcu_node(rnp_root);
> > > > -		if (!rnp_root->parent)
> > > > +		if (rnp != rnp_start && rnp->parent != NULL)
> > > > +			raw_spin_unlock_rcu_node(rnp);
> > > > +		if (!rnp->parent) {
> > > > +			rnp_root = rnp;
> > > 
> > > Since rnp_root is otherwise unused in the new version, the above statement
> > > can be dropped along with the "if" statement's braces and the declaration.
> > 
> > Actually rnp_root is needed for tracing calls after we breakout of the loop.
> 
> But at that point, rnp_root is equal to rnp, so rnp_root still isn't
> really needed, correct?

You are right. Sorry about that, so I'll change the tracepoints that follow
to use rnp, as you suggested.

thanks,

 - Joel

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Paul E. McKenney]

On Mon, May 21, 2018 at 05:07:34PM -0700, Joel Fernandes wrote:
> On Mon, May 21, 2018 at 04:25:38PM -0700, Paul E. McKenney wrote:
> > On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> > > We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> > > after the access.
> > 
> > Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
> > the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
> > so nothing else is accessing it.  Or at least that is the intent.  ;-)
> 
> I was talking about protecting the internal node's rnp->gp_seq_needed, not
> the rnp_start's gp_seq_needed.

Ah, good point, I missed the "if" condition.  This can be argued to work,
sort of, given that we still hold the leaf rcu_node structure's lock,
so that there is a limit to how far grace periods can advance.

But the code would of course be much cleaner with your change.

> We are protecting them in the loop:
> 
> like this:
> for(...)
> 	if (rnp != rnp_start)
> 		raw_spin_lock_rcu_node(rnp);
> 	[...]
> 	// access rnp->gp_seq and rnp->gp_seq_needed
> 	[...]
> 	if (rnp != rnp_start)
> 		raw_spin_unlock_rcu_node(rnp);
> 
> But we don't need to do such protection in unlock_out ? I'm sorry if I'm
> missing something, but I'm wondering if rnp->gp_seq_needed of an internal
> node can be accessed locklessly, then why can't that be done also in the
> funnel locking loop - after all we are holding the rnp_start's lock through
> out right?

I was focused on the updates, and missed the rnp->gp_seq_req access in the
"if" statement.  The current code does sort of work, but only assuming
that the compiler doesn't tear the load, and so your change would help.
Could you please resend with your other two updated patches?  It depends
on one of the earlier patches, so does not apply cleanly as-is.  I could
hand-apply it, but that sounds like a good way to make your updated
series fail to apply.  ;-)

But could you also make the commit log explicitly call out the "if"
condition as being the offending access?

							Thanx, Paul

Re: [PATCH v3 3/4] rcu: Use better variable names in funnel locking loop

[Paul E. McKenney]

On Mon, May 21, 2018 at 05:19:51PM -0700, Joel Fernandes wrote:
> On Mon, May 21, 2018 at 05:19:25PM -0700, Paul E. McKenney wrote:
> > On Mon, May 21, 2018 at 05:00:16PM -0700, Joel Fernandes wrote:
> > > On Mon, May 21, 2018 at 04:13:57PM -0700, Paul E. McKenney wrote:
> > > > > ---
> > > > >  kernel/rcu/tree.c | 48 ++++++++++++++++++++++++-----------------------
> > > > >  1 file changed, 25 insertions(+), 23 deletions(-)
> > > > > 
> > > > > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > > > > index 0ffd41ba304f..879c67a31116 100644
> > > > > --- a/kernel/rcu/tree.c
> > > > > +++ b/kernel/rcu/tree.c
> > > > > @@ -1526,7 +1526,7 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > > 
> > > > >  /*
> > > > >   * rcu_start_this_gp - Request the start of a particular grace period
> > > > > - * @rnp: The leaf node of the CPU from which to start.
> > > > > + * @rnp_start: The leaf node of the CPU from which to start.
> > > > >   * @rdp: The rcu_data corresponding to the CPU from which to start.
> > > > >   * @gp_seq_req: The gp_seq of the grace period to start.
> > > > >   *
> > > > > @@ -1540,12 +1540,12 @@ static void trace_rcu_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > >   *
> > > > >   * Returns true if the GP thread needs to be awakened else false.
> > > > >   */
> > > > > -static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > > +static bool rcu_start_this_gp(struct rcu_node *rnp_start, struct rcu_data *rdp,
> > > > >  			      unsigned long gp_seq_req)
> > > > >  {
> > > > >  	bool ret = false;
> > > > >  	struct rcu_state *rsp = rdp->rsp;
> > > > > -	struct rcu_node *rnp_root;
> > > > > +	struct rcu_node *rnp, *rnp_root = NULL;
> > > > 
> > > > Unless I am going blind, this patch really isn't using rnp_root.  It
> > > > could be removed.
> > > 
> > > Its just limitation of the diff tools. Your eyes are just fine and doing
> > > great based on your review comments ;)
> > > 
> > > The rnp_root is used after we break out of the loop.
> > > 
> > > > > 
> > > > >  	/*
> > > > >  	 * Use funnel locking to either acquire the root rcu_node
> > > > > @@ -1556,34 +1556,36 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> > > > >  	 * scan the leaf rcu_node structures.  Note that rnp->lock must
> > > > >  	 * not be released.
> > > > >  	 */
> > > > > -	raw_lockdep_assert_held_rcu_node(rnp);
> > > > > -	trace_rcu_this_gp(rnp, rdp, gp_seq_req, TPS("Startleaf"));
> > > > > -	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> > > > > -		if (rnp_root != rnp)
> > > > > -			raw_spin_lock_rcu_node(rnp_root);
> > > > > -		if (ULONG_CMP_GE(rnp_root->gp_seq_needed, gp_seq_req) ||
> > > > > -		    rcu_seq_started(&rnp_root->gp_seq, gp_seq_req) ||
> > > > > -		    (rnp != rnp_root &&
> > > > > -		     rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))) {
> > > > > -			trace_rcu_this_gp(rnp_root, rdp, gp_seq_req,
> > > > > +	raw_lockdep_assert_held_rcu_node(rnp_start);
> > > > > +	trace_rcu_this_gp(rnp_start, rdp, gp_seq_req, TPS("Startleaf"));
> > > > > +	for (rnp = rnp_start; 1; rnp = rnp->parent) {
> > > > > +		if (rnp != rnp_start)
> > > > > +			raw_spin_lock_rcu_node(rnp);
> > > > > +		if (ULONG_CMP_GE(rnp->gp_seq_needed, gp_seq_req) ||
> > > > > +		    rcu_seq_started(&rnp->gp_seq, gp_seq_req) ||
> > > > > +		    (rnp != rnp_start &&
> > > > > +		     rcu_seq_state(rcu_seq_current(&rnp->gp_seq)))) {
> > > > > +			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > > > >  					  TPS("Prestarted"));
> > > > >  			goto unlock_out;
> > > > >  		}
> > > > > -		rnp_root->gp_seq_needed = gp_seq_req;
> > > > > -		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > > > > +		rnp->gp_seq_needed = gp_seq_req;
> > > > > +		if (rcu_seq_state(rcu_seq_current(&rnp_start->gp_seq))) {
> > > > 
> > > > The original had a performance bug, which is quite a bit more obvious
> > > > given the new names, so thank you for that!  The above statement should
> > > > instead be as follows:
> > > > 
> > > > 		if (rcu_seq_state(rcu_seq_current(&rnp->gp_seq))) {
> > > > 
> > > > It does not make sense to keep checking the starting rcu_node because
> > > > changes to ->gp_seq happen first at the top of the tree.  So we might
> > > > take an earlier exit by checking the current rnp instead of rechecking
> > > > rnp_start over and over.
> > > > 
> > > > Please feel free to make this change, which is probably best as a separate
> > > > patch.  That way this rename patch can remain a straightforward rename patch.
> > > 
> > > Yes, sounds like a nice optimization and I'm glad my variable renaming helped
> > > ;) I feel I should have seen it too. I can make this change and send out
> > > with my next series as you suggest.
> > > 
> > > > >  			/*
> > > > >  			 * We just marked the leaf, and a grace period
> > > > >  			 * is in progress, which means that rcu_gp_cleanup()
> > > > >  			 * will see the marking.  Bail to reduce contention.
> > > > >  			 */
> > > > > -			trace_rcu_this_gp(rnp, rdp, gp_seq_req,
> > > > > +			trace_rcu_this_gp(rnp_start, rdp, gp_seq_req,
> > > > >  					  TPS("Startedleaf"));
> > > > >  			goto unlock_out;
> > > > >  		}
> > > > > -		if (rnp_root != rnp && rnp_root->parent != NULL)
> > > > > -			raw_spin_unlock_rcu_node(rnp_root);
> > > > > -		if (!rnp_root->parent)
> > > > > +		if (rnp != rnp_start && rnp->parent != NULL)
> > > > > +			raw_spin_unlock_rcu_node(rnp);
> > > > > +		if (!rnp->parent) {
> > > > > +			rnp_root = rnp;
> > > > 
> > > > Since rnp_root is otherwise unused in the new version, the above statement
> > > > can be dropped along with the "if" statement's braces and the declaration.
> > > 
> > > Actually rnp_root is needed for tracing calls after we breakout of the loop.
> > 
> > But at that point, rnp_root is equal to rnp, so rnp_root still isn't
> > really needed, correct?
> 
> You are right. Sorry about that, so I'll change the tracepoints that follow
> to use rnp, as you suggested.

Sounds good, thank you!

							Thanx, Paul

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Paul E. McKenney]

On Mon, May 21, 2018 at 05:28:23PM -0700, Paul E. McKenney wrote:
> On Mon, May 21, 2018 at 05:07:34PM -0700, Joel Fernandes wrote:
> > On Mon, May 21, 2018 at 04:25:38PM -0700, Paul E. McKenney wrote:
> > > On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> > > > We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> > > > after the access.
> > > 
> > > Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
> > > the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
> > > so nothing else is accessing it.  Or at least that is the intent.  ;-)
> > 
> > I was talking about protecting the internal node's rnp->gp_seq_needed, not
> > the rnp_start's gp_seq_needed.
> 
> Ah, good point, I missed the "if" condition.  This can be argued to work,
> sort of, given that we still hold the leaf rcu_node structure's lock,
> so that there is a limit to how far grace periods can advance.
> 
> But the code would of course be much cleaner with your change.
> 
> > We are protecting them in the loop:
> > 
> > like this:
> > for(...)
> > 	if (rnp != rnp_start)
> > 		raw_spin_lock_rcu_node(rnp);
> > 	[...]
> > 	// access rnp->gp_seq and rnp->gp_seq_needed
> > 	[...]
> > 	if (rnp != rnp_start)
> > 		raw_spin_unlock_rcu_node(rnp);
> > 
> > But we don't need to do such protection in unlock_out ? I'm sorry if I'm
> > missing something, but I'm wondering if rnp->gp_seq_needed of an internal
> > node can be accessed locklessly, then why can't that be done also in the
> > funnel locking loop - after all we are holding the rnp_start's lock through
> > out right?
> 
> I was focused on the updates, and missed the rnp->gp_seq_req access in the
> "if" statement.  The current code does sort of work, but only assuming
> that the compiler doesn't tear the load, and so your change would help.
> Could you please resend with your other two updated patches?  It depends
> on one of the earlier patches, so does not apply cleanly as-is.  I could
> hand-apply it, but that sounds like a good way to make your updated
> series fail to apply.  ;-)
> 
> But could you also make the commit log explicitly call out the "if"
> condition as being the offending access?

Never mind, me being stupid.  I need to apply this change to the original
commit "rcu: Make rcu_nocb_wait_gp() check if GP already requested", which
I have done with this attribution:

[ paulmck: Move lock release past "if" as suggested by Joel Fernandes. ]

I have rebased my stack on top of the updated commit.

							Thanx, Paul

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Joel Fernandes]

On Mon, May 21, 2018 at 09:16:51PM -0700, Paul E. McKenney wrote:
> On Mon, May 21, 2018 at 05:28:23PM -0700, Paul E. McKenney wrote:
> > On Mon, May 21, 2018 at 05:07:34PM -0700, Joel Fernandes wrote:
> > > On Mon, May 21, 2018 at 04:25:38PM -0700, Paul E. McKenney wrote:
> > > > On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> > > > > We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> > > > > after the access.
> > > > 
> > > > Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
> > > > the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
> > > > so nothing else is accessing it.  Or at least that is the intent.  ;-)
> > > 
> > > I was talking about protecting the internal node's rnp->gp_seq_needed, not
> > > the rnp_start's gp_seq_needed.
> > 
> > Ah, good point, I missed the "if" condition.  This can be argued to work,
> > sort of, given that we still hold the leaf rcu_node structure's lock,
> > so that there is a limit to how far grace periods can advance.
> > 
> > But the code would of course be much cleaner with your change.
> > 
> > > We are protecting them in the loop:
> > > 
> > > like this:
> > > for(...)
> > > 	if (rnp != rnp_start)
> > > 		raw_spin_lock_rcu_node(rnp);
> > > 	[...]
> > > 	// access rnp->gp_seq and rnp->gp_seq_needed
> > > 	[...]
> > > 	if (rnp != rnp_start)
> > > 		raw_spin_unlock_rcu_node(rnp);
> > > 
> > > But we don't need to do such protection in unlock_out ? I'm sorry if I'm
> > > missing something, but I'm wondering if rnp->gp_seq_needed of an internal
> > > node can be accessed locklessly, then why can't that be done also in the
> > > funnel locking loop - after all we are holding the rnp_start's lock through
> > > out right?
> > 
> > I was focused on the updates, and missed the rnp->gp_seq_req access in the
> > "if" statement.  The current code does sort of work, but only assuming
> > that the compiler doesn't tear the load, and so your change would help.
> > Could you please resend with your other two updated patches?  It depends
> > on one of the earlier patches, so does not apply cleanly as-is.  I could
> > hand-apply it, but that sounds like a good way to make your updated
> > series fail to apply.  ;-)
> > 
> > But could you also make the commit log explicitly call out the "if"
> > condition as being the offending access?
> 
> Never mind, me being stupid.  I need to apply this change to the original
> commit "rcu: Make rcu_nocb_wait_gp() check if GP already requested", which
> I have done with this attribution:
> 
> [ paulmck: Move lock release past "if" as suggested by Joel Fernandes. ]
> 
> I have rebased my stack on top of the updated commit.

Cool, makes sense. I am assuming this means I don't have to resend this
patch, if I do let me know :)

Either way, once you push your updated tree to kernel.org, I'll double check
to make sure the change is in :)

thanks, good night,

 - Joel

Re: [PATCH v3 4/4] rcu: Unlock non-start node only after accessing its gp_seq_needed

[Paul E. McKenney]

On Mon, May 21, 2018 at 09:43:27PM -0700, Joel Fernandes wrote:
> On Mon, May 21, 2018 at 09:16:51PM -0700, Paul E. McKenney wrote:
> > On Mon, May 21, 2018 at 05:28:23PM -0700, Paul E. McKenney wrote:
> > > On Mon, May 21, 2018 at 05:07:34PM -0700, Joel Fernandes wrote:
> > > > On Mon, May 21, 2018 at 04:25:38PM -0700, Paul E. McKenney wrote:
> > > > > On Sun, May 20, 2018 at 09:42:20PM -0700, Joel Fernandes wrote:
> > > > > > We acquire gp_seq_needed locklessly. To be safe, lets do the unlocking
> > > > > > after the access.
> > > > > 
> > > > > Actually, no, we hold rnp_start's ->lock throughout.  And this CPU (or in
> > > > > the case of no-CBs CPUs, this task) is in charge of rdp->gp_seq_needed,
> > > > > so nothing else is accessing it.  Or at least that is the intent.  ;-)
> > > > 
> > > > I was talking about protecting the internal node's rnp->gp_seq_needed, not
> > > > the rnp_start's gp_seq_needed.
> > > 
> > > Ah, good point, I missed the "if" condition.  This can be argued to work,
> > > sort of, given that we still hold the leaf rcu_node structure's lock,
> > > so that there is a limit to how far grace periods can advance.
> > > 
> > > But the code would of course be much cleaner with your change.
> > > 
> > > > We are protecting them in the loop:
> > > > 
> > > > like this:
> > > > for(...)
> > > > 	if (rnp != rnp_start)
> > > > 		raw_spin_lock_rcu_node(rnp);
> > > > 	[...]
> > > > 	// access rnp->gp_seq and rnp->gp_seq_needed
> > > > 	[...]
> > > > 	if (rnp != rnp_start)
> > > > 		raw_spin_unlock_rcu_node(rnp);
> > > > 
> > > > But we don't need to do such protection in unlock_out ? I'm sorry if I'm
> > > > missing something, but I'm wondering if rnp->gp_seq_needed of an internal
> > > > node can be accessed locklessly, then why can't that be done also in the
> > > > funnel locking loop - after all we are holding the rnp_start's lock through
> > > > out right?
> > > 
> > > I was focused on the updates, and missed the rnp->gp_seq_req access in the
> > > "if" statement.  The current code does sort of work, but only assuming
> > > that the compiler doesn't tear the load, and so your change would help.
> > > Could you please resend with your other two updated patches?  It depends
> > > on one of the earlier patches, so does not apply cleanly as-is.  I could
> > > hand-apply it, but that sounds like a good way to make your updated
> > > series fail to apply.  ;-)
> > > 
> > > But could you also make the commit log explicitly call out the "if"
> > > condition as being the offending access?
> > 
> > Never mind, me being stupid.  I need to apply this change to the original
> > commit "rcu: Make rcu_nocb_wait_gp() check if GP already requested", which
> > I have done with this attribution:
> > 
> > [ paulmck: Move lock release past "if" as suggested by Joel Fernandes. ]
> > 
> > I have rebased my stack on top of the updated commit.
> 
> Cool, makes sense. I am assuming this means I don't have to resend this
> patch, if I do let me know :)

No need.

> Either way, once you push your updated tree to kernel.org, I'll double check
> to make sure the change is in :)

Please see 9624746baf6b ("rcu: Make rcu_nocb_wait_gp() check if GP
already requested") on branch rcu/dev.

								Thanx, Paul