[PATCH 0/2] srcu: Optimize when srcu_gp_start_if_needed() holds

[PATCH 0/2] srcu: Optimize when srcu_gp_start_if_needed() holds

[Pingfan Liu]

This series optimizes and remove some code under the condition that
srcu_gp_start_if_needed() holds the srcu read lock.

Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: rcu@vger.kernel.org

Pingfan Liu (2):
  srcu: Remove needless rcu_seq_done() check while holding read lock
  srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

 kernel/rcu/srcutree.c | 15 ++++++---------
 1 file changed, 6 insertions(+), 9 deletions(-)

-- 
2.31.1

[PATCH 1/2] srcu: Remove needless rcu_seq_done() check while holding read lock

[Pingfan Liu]

As the code changes, now, srcu_gp_start_if_needed() holds the srcu read
lock, gets the gp_seq snap and call srcu_funnel_gp_start() passing that
snap value.

As the rcu_seq_snap() promises "a full grace period has elapsed since
the current time".  In srcu_funnel_gp_start(), the statement
  rcu_seq_done(&ssp->srcu_gp_seq, s)
always return false.

The same condition stands for srcu_funnel_exp_start(). Hence removing
all the checks of rcu_seq_done().

Test info:
  Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
without any failure.

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: rcu@vger.kernel.org
---
 kernel/rcu/srcutree.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 1c304fec89c0..7df59fc8073e 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -851,8 +851,7 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
 	if (snp)
 		for (; snp != NULL; snp = snp->srcu_parent) {
 			sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
-			if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
-			    (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
+			if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))
 				return;
 			spin_lock_irqsave_rcu_node(snp, flags);
 			sgsne = snp->srcu_gp_seq_needed_exp;
@@ -878,6 +877,9 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
  *
  * Note that this function also does the work of srcu_funnel_exp_start(),
  * in some cases by directly invoking it.
+ *
+ * The srcu read lock should be hold around this function. And s is a seq snap
+ * after holding that lock.
  */
 static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 				 unsigned long s, bool do_norm)
@@ -898,8 +900,6 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 	if (snp_leaf)
 		/* Each pass through the loop does one level of the srcu_node tree. */
 		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
-			if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != snp_leaf)
-				return; /* GP already done and CBs recorded. */
 			spin_lock_irqsave_rcu_node(snp, flags);
 			snp_seq = snp->srcu_have_cbs[idx];
 			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
@@ -935,9 +935,8 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 	if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
 		WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
 
-	/* If grace period not already done and none in progress, start it. */
-	if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
-	    rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
+	/* If grace period not already in progress, start it. */
+	if (rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
 		WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
 		srcu_gp_start(ssp);
 
-- 
2.31.1

[PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Pingfan Liu]

At present, snp->srcu_have_cbs[idx] is updated by either
srcu_funnel_gp_start() or srcu_gp_end().

But as the code changes, now, srcu_funnel_gp_start() is called with srcu
read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
whose counter field always proceeds that of the srcu_gp_seq by one or two.

If the seq snap only proceeds by one, the state machine should be in
state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
machine from moving ahead. So when srcu_gp_end() updates
snp->srcu_have_cbs[idx], the idx must be the past idx for
srcu_funnel_gp_start() that is cared by nobody.

So removing the unnecessary updating in srcu_gp_end().

Test info:
  Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
without any failure.

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: rcu@vger.kernel.org
---
 kernel/rcu/srcutree.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 7df59fc8073e..c54d6c04751f 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
 			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
 			if (last_lvl)
 				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
-			snp->srcu_have_cbs[idx] = gpseq;
-			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
 			sgsne = snp->srcu_gp_seq_needed_exp;
 			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
 				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
-- 
2.31.1

RE: [PATCH 1/2] srcu: Remove needless rcu_seq_done() check while holding read lock

[Zhang, Qiang1]

>
>As the code changes, now, srcu_gp_start_if_needed() holds the srcu read
>lock, gets the gp_seq snap and call srcu_funnel_gp_start() passing that
>snap value.
>
>As the rcu_seq_snap() promises "a full grace period has elapsed since
>the current time".  In srcu_funnel_gp_start(), the statement
>  rcu_seq_done(&ssp->srcu_gp_seq, s)
>always return false.

Hi Pingfan

Please correct me if I understand your commit message incorrectly. because the srcu_gp_start_if_needed() is
protected  by srcu read lock,  and the  rcu_seq_snap()  seq is a  at the end of the current or next srcu grace period, 
so as long as we are still in the srcu_gp_start_if_needed(), it also means that we are in SRCU critical section.
the current or next srcu grace period will not end, it also means that we can not invoke rcu_seq_end() to update 
'ssp->secu_gp_seq' , so the rcu_seq_done(&ssp->srcu_gp_seq, s) is always return false.

Thanks
Zqiang

>
>The same condition stands for srcu_funnel_exp_start(). Hence removing
>all the checks of rcu_seq_done().
>
>Test info:
>  Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
>without any failure.
>
>Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
>Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: rcu@vger.kernel.org
---
 kernel/rcu/srcutree.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index 1c304fec89c0..7df59fc8073e 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -851,8 +851,7 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
 	if (snp)
 		for (; snp != NULL; snp = snp->srcu_parent) {
 			sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
-			if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
-			    (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
+			if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))
 				return;
 			spin_lock_irqsave_rcu_node(snp, flags);
 			sgsne = snp->srcu_gp_seq_needed_exp;
@@ -878,6 +877,9 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
  *
  * Note that this function also does the work of srcu_funnel_exp_start(),
  * in some cases by directly invoking it.
+ *
+ * The srcu read lock should be hold around this function. And s is a seq snap
+ * after holding that lock.
  */
 static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 				 unsigned long s, bool do_norm)
@@ -898,8 +900,6 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 	if (snp_leaf)
 		/* Each pass through the loop does one level of the srcu_node tree. */
 		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
-			if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != snp_leaf)
-				return; /* GP already done and CBs recorded. */
 			spin_lock_irqsave_rcu_node(snp, flags);
 			snp_seq = snp->srcu_have_cbs[idx];
 			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
@@ -935,9 +935,8 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 	if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
 		WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
 
-	/* If grace period not already done and none in progress, start it. */
-	if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
-	    rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
+	/* If grace period not already in progress, start it. */
+	if (rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
 		WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
 		srcu_gp_start(ssp);
 
-- 
2.31.1

[PATCH] srcu: Eliminate the case that snp_seq bigger than snap in srcu_funnel_gp_start()

[Pingfan Liu]

Since the srcu read lock is still held during srcu_funnel_gp_start(),
the seq snap should be the largest number for the slot
srcu_have_cbs[idx].

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: rcu@vger.kernel.org
---
 include/linux/rcupdate.h |  1 +
 kernel/rcu/srcutree.c    | 10 +++++-----
 2 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
index 08605ce7379d..a09007236660 100644
--- a/include/linux/rcupdate.h
+++ b/include/linux/rcupdate.h
@@ -32,6 +32,7 @@
 #include <linux/context_tracking_irq.h>
 
 #define ULONG_CMP_GE(a, b)	(ULONG_MAX / 2 >= (a) - (b))
+#define ULONG_CMP_GT(a, b)	(ULONG_MAX / 2 > (a) - (b))
 #define ULONG_CMP_LT(a, b)	(ULONG_MAX / 2 < (a) - (b))
 #define ulong2long(a)		(*(long *)(&(a)))
 #define USHORT_CMP_GE(a, b)	(USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
index c54d6c04751f..057752db1125 100644
--- a/kernel/rcu/srcutree.c
+++ b/kernel/rcu/srcutree.c
@@ -900,14 +900,14 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
 		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
 			spin_lock_irqsave_rcu_node(snp, flags);
 			snp_seq = snp->srcu_have_cbs[idx];
-			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
+			/* s should be the biggest in the current slot. Hence only LE is
+			 * valid
+			 */
+			BUG_ON(ULONG_CMP_GT(snp_seq, s));
+			if (!srcu_invl_snp_seq(snp_seq) && (snp_seq == s)) {
 				if (snp == snp_leaf && snp_seq == s)
 					snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
 				spin_unlock_irqrestore_rcu_node(snp, flags);
-				if (snp == snp_leaf && snp_seq != s) {
-					srcu_schedule_cbs_sdp(sdp, do_norm ? SRCU_INTERVAL : 0);
-					return;
-				}
 				if (!do_norm)
 					srcu_funnel_exp_start(ssp, snp, s);
 				return;
-- 
2.31.1

Re: [PATCH] srcu: Eliminate the case that snp_seq bigger than snap in srcu_funnel_gp_start()

[Pingfan Liu]

Sorry for the fragment, but I am just aware of this and think it is
better to fold into the same series.

Thanks,

    Pingfan

On Sun, Nov 20, 2022 at 11:20 PM Pingfan Liu <kernelfans@gmail.com> wrote:
>
> Since the srcu read lock is still held during srcu_funnel_gp_start(),
> the seq snap should be the largest number for the slot
> srcu_have_cbs[idx].
>
> Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Frederic Weisbecker <frederic@kernel.org>
> Cc: Josh Triplett <josh@joshtriplett.org>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> To: rcu@vger.kernel.org
> ---
>  include/linux/rcupdate.h |  1 +
>  kernel/rcu/srcutree.c    | 10 +++++-----
>  2 files changed, 6 insertions(+), 5 deletions(-)
>
> diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
> index 08605ce7379d..a09007236660 100644
> --- a/include/linux/rcupdate.h
> +++ b/include/linux/rcupdate.h
> @@ -32,6 +32,7 @@
>  #include <linux/context_tracking_irq.h>
>
>  #define ULONG_CMP_GE(a, b)     (ULONG_MAX / 2 >= (a) - (b))
> +#define ULONG_CMP_GT(a, b)     (ULONG_MAX / 2 > (a) - (b))
>  #define ULONG_CMP_LT(a, b)     (ULONG_MAX / 2 < (a) - (b))
>  #define ulong2long(a)          (*(long *)(&(a)))
>  #define USHORT_CMP_GE(a, b)    (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index c54d6c04751f..057752db1125 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -900,14 +900,14 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>                 for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
>                         spin_lock_irqsave_rcu_node(snp, flags);
>                         snp_seq = snp->srcu_have_cbs[idx];
> -                       if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
> +                       /* s should be the biggest in the current slot. Hence only LE is
> +                        * valid
> +                        */
> +                       BUG_ON(ULONG_CMP_GT(snp_seq, s));
> +                       if (!srcu_invl_snp_seq(snp_seq) && (snp_seq == s)) {
>                                 if (snp == snp_leaf && snp_seq == s)
>                                         snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
>                                 spin_unlock_irqrestore_rcu_node(snp, flags);
> -                               if (snp == snp_leaf && snp_seq != s) {
> -                                       srcu_schedule_cbs_sdp(sdp, do_norm ? SRCU_INTERVAL : 0);
> -                                       return;
> -                               }
>                                 if (!do_norm)
>                                         srcu_funnel_exp_start(ssp, snp, s);
>                                 return;
> --
> 2.31.1
>

Re: [PATCH 1/2] srcu: Remove needless rcu_seq_done() check while holding read lock

[Pingfan Liu]

On Sun, Nov 20, 2022 at 05:00:43AM +0000, Zhang, Qiang1 wrote:
> >
> >As the code changes, now, srcu_gp_start_if_needed() holds the srcu read
> >lock, gets the gp_seq snap and call srcu_funnel_gp_start() passing that
> >snap value.
> >
> >As the rcu_seq_snap() promises "a full grace period has elapsed since
> >the current time".  In srcu_funnel_gp_start(), the statement
> >  rcu_seq_done(&ssp->srcu_gp_seq, s)
> >always return false.
> 
> Hi Pingfan
> 
> Please correct me if I understand your commit message incorrectly. because the srcu_gp_start_if_needed() is
> protected  by srcu read lock,  and the  rcu_seq_snap()  seq is a  at the end of the current or next srcu grace period, 
> so as long as we are still in the srcu_gp_start_if_needed(), it also means that we are in SRCU critical section.
> the current or next srcu grace period will not end, it also means that we can not invoke rcu_seq_end() to update 
> 'ssp->secu_gp_seq' , so the rcu_seq_done(&ssp->srcu_gp_seq, s) is always return false.
> 

Yes, you totally got it.

Thanks

	Pingfan

> Thanks
> Zqiang
> 
> >
> >The same condition stands for srcu_funnel_exp_start(). Hence removing
> >all the checks of rcu_seq_done().
> >
> >Test info:
> >  Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> >without any failure.
> >
> >Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> >Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Frederic Weisbecker <frederic@kernel.org>
> Cc: Josh Triplett <josh@joshtriplett.org>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> To: rcu@vger.kernel.org
> ---
>  kernel/rcu/srcutree.c | 13 ++++++-------
>  1 file changed, 6 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 1c304fec89c0..7df59fc8073e 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -851,8 +851,7 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
>  	if (snp)
>  		for (; snp != NULL; snp = snp->srcu_parent) {
>  			sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
> -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
> -			    (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
> +			if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))
>  				return;
>  			spin_lock_irqsave_rcu_node(snp, flags);
>  			sgsne = snp->srcu_gp_seq_needed_exp;
> @@ -878,6 +877,9 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
>   *
>   * Note that this function also does the work of srcu_funnel_exp_start(),
>   * in some cases by directly invoking it.
> + *
> + * The srcu read lock should be hold around this function. And s is a seq snap
> + * after holding that lock.
>   */
>  static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  				 unsigned long s, bool do_norm)
> @@ -898,8 +900,6 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  	if (snp_leaf)
>  		/* Each pass through the loop does one level of the srcu_node tree. */
>  		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
> -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != snp_leaf)
> -				return; /* GP already done and CBs recorded. */
>  			spin_lock_irqsave_rcu_node(snp, flags);
>  			snp_seq = snp->srcu_have_cbs[idx];
>  			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
> @@ -935,9 +935,8 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  	if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
>  		WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
>  
> -	/* If grace period not already done and none in progress, start it. */
> -	if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
> -	    rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
> +	/* If grace period not already in progress, start it. */
> +	if (rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
>  		WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
>  		srcu_gp_start(ssp);
>  
> -- 
> 2.31.1
> 

Re: [PATCH 1/2] srcu: Remove needless rcu_seq_done() check while holding read lock

[Paul E. McKenney]

On Sun, Nov 20, 2022 at 11:40:13AM +0800, Pingfan Liu wrote:
> As the code changes, now, srcu_gp_start_if_needed() holds the srcu read
> lock, gets the gp_seq snap and call srcu_funnel_gp_start() passing that
> snap value.
> 
> As the rcu_seq_snap() promises "a full grace period has elapsed since
> the current time".  In srcu_funnel_gp_start(), the statement
>   rcu_seq_done(&ssp->srcu_gp_seq, s)
> always return false.
> 
> The same condition stands for srcu_funnel_exp_start(). Hence removing
> all the checks of rcu_seq_done().
> 
> Test info:
>   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> without any failure.

Nice catch!!!  And I do appreciate the testing.

But if we are going to do this, let's please also place lockdep assertions
in srcu_funnel_exp_start() and srcu_funnel_gp_start() to verify that these
functions are in fact invoked within an SRCU read-side critical section.
Also a WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_gp_seq, s)), please.

Things changed to make the rcu_seq_done() unnecessary, so they could just
as easily change again.

							Thanx, Paul

> Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Frederic Weisbecker <frederic@kernel.org>
> Cc: Josh Triplett <josh@joshtriplett.org>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> To: rcu@vger.kernel.org
> ---
>  kernel/rcu/srcutree.c | 13 ++++++-------
>  1 file changed, 6 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 1c304fec89c0..7df59fc8073e 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -851,8 +851,7 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
>  	if (snp)
>  		for (; snp != NULL; snp = snp->srcu_parent) {
>  			sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
> -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
> -			    (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
> +			if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))
>  				return;
>  			spin_lock_irqsave_rcu_node(snp, flags);
>  			sgsne = snp->srcu_gp_seq_needed_exp;
> @@ -878,6 +877,9 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
>   *
>   * Note that this function also does the work of srcu_funnel_exp_start(),
>   * in some cases by directly invoking it.
> + *
> + * The srcu read lock should be hold around this function. And s is a seq snap
> + * after holding that lock.
>   */
>  static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  				 unsigned long s, bool do_norm)
> @@ -898,8 +900,6 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  	if (snp_leaf)
>  		/* Each pass through the loop does one level of the srcu_node tree. */
>  		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
> -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != snp_leaf)
> -				return; /* GP already done and CBs recorded. */
>  			spin_lock_irqsave_rcu_node(snp, flags);
>  			snp_seq = snp->srcu_have_cbs[idx];
>  			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
> @@ -935,9 +935,8 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
>  	if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
>  		WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
>  
> -	/* If grace period not already done and none in progress, start it. */
> -	if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
> -	    rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
> +	/* If grace period not already in progress, start it. */
> +	if (rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
>  		WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
>  		srcu_gp_start(ssp);
>  
> -- 
> 2.31.1
> 

Re: [PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Paul E. McKenney]

On Sun, Nov 20, 2022 at 11:40:14AM +0800, Pingfan Liu wrote:
> At present, snp->srcu_have_cbs[idx] is updated by either
> srcu_funnel_gp_start() or srcu_gp_end().
> 
> But as the code changes, now, srcu_funnel_gp_start() is called with srcu
> read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
> whose counter field always proceeds that of the srcu_gp_seq by one or two.
> 
> If the seq snap only proceeds by one, the state machine should be in
> state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
> machine from moving ahead. So when srcu_gp_end() updates
> snp->srcu_have_cbs[idx], the idx must be the past idx for
> srcu_funnel_gp_start() that is cared by nobody.
> 
> So removing the unnecessary updating in srcu_gp_end().

This looks plausible, good eyes!

But is there a debug check that could verify that this is unnecessary?
Logical reasoning is all well and good, but the actual system always
wins arguments.  ;-)

							Thanx, Paul

> Test info:
>   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> without any failure.
> 
> Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Frederic Weisbecker <frederic@kernel.org>
> Cc: Josh Triplett <josh@joshtriplett.org>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> To: rcu@vger.kernel.org
> ---
>  kernel/rcu/srcutree.c | 2 --
>  1 file changed, 2 deletions(-)
> 
> diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> index 7df59fc8073e..c54d6c04751f 100644
> --- a/kernel/rcu/srcutree.c
> +++ b/kernel/rcu/srcutree.c
> @@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
>  			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
>  			if (last_lvl)
>  				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> -			snp->srcu_have_cbs[idx] = gpseq;
> -			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
>  			sgsne = snp->srcu_gp_seq_needed_exp;
>  			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
>  				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> -- 
> 2.31.1
> 

Re: [PATCH] srcu: Eliminate the case that snp_seq bigger than snap in srcu_funnel_gp_start()

[Paul E. McKenney]

On Sun, Nov 20, 2022 at 11:23:46PM +0800, Pingfan Liu wrote:
> Sorry for the fragment, but I am just aware of this and think it is
> better to fold into the same series.

Very well, I look forward to seeing the new version of this series.

						Thanx, Paul

> Thanks,
> 
>     Pingfan
> 
> On Sun, Nov 20, 2022 at 11:20 PM Pingfan Liu <kernelfans@gmail.com> wrote:
> >
> > Since the srcu read lock is still held during srcu_funnel_gp_start(),
> > the seq snap should be the largest number for the slot
> > srcu_have_cbs[idx].
> >
> > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > Cc: Frederic Weisbecker <frederic@kernel.org>
> > Cc: Josh Triplett <josh@joshtriplett.org>
> > Cc: Steven Rostedt <rostedt@goodmis.org>
> > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > To: rcu@vger.kernel.org
> > ---
> >  include/linux/rcupdate.h |  1 +
> >  kernel/rcu/srcutree.c    | 10 +++++-----
> >  2 files changed, 6 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
> > index 08605ce7379d..a09007236660 100644
> > --- a/include/linux/rcupdate.h
> > +++ b/include/linux/rcupdate.h
> > @@ -32,6 +32,7 @@
> >  #include <linux/context_tracking_irq.h>
> >
> >  #define ULONG_CMP_GE(a, b)     (ULONG_MAX / 2 >= (a) - (b))
> > +#define ULONG_CMP_GT(a, b)     (ULONG_MAX / 2 > (a) - (b))
> >  #define ULONG_CMP_LT(a, b)     (ULONG_MAX / 2 < (a) - (b))
> >  #define ulong2long(a)          (*(long *)(&(a)))
> >  #define USHORT_CMP_GE(a, b)    (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index c54d6c04751f..057752db1125 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -900,14 +900,14 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
> >                 for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
> >                         spin_lock_irqsave_rcu_node(snp, flags);
> >                         snp_seq = snp->srcu_have_cbs[idx];
> > -                       if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
> > +                       /* s should be the biggest in the current slot. Hence only LE is
> > +                        * valid
> > +                        */
> > +                       BUG_ON(ULONG_CMP_GT(snp_seq, s));
> > +                       if (!srcu_invl_snp_seq(snp_seq) && (snp_seq == s)) {
> >                                 if (snp == snp_leaf && snp_seq == s)
> >                                         snp->srcu_data_have_cbs[idx] |= sdp->grpmask;
> >                                 spin_unlock_irqrestore_rcu_node(snp, flags);
> > -                               if (snp == snp_leaf && snp_seq != s) {
> > -                                       srcu_schedule_cbs_sdp(sdp, do_norm ? SRCU_INTERVAL : 0);
> > -                                       return;
> > -                               }
> >                                 if (!do_norm)
> >                                         srcu_funnel_exp_start(ssp, snp, s);
> >                                 return;
> > --
> > 2.31.1
> >

Re: [PATCH 1/2] srcu: Remove needless rcu_seq_done() check while holding read lock

[Pingfan Liu]

On Mon, Nov 21, 2022 at 05:13:45PM -0800, Paul E. McKenney wrote:
> On Sun, Nov 20, 2022 at 11:40:13AM +0800, Pingfan Liu wrote:
> > As the code changes, now, srcu_gp_start_if_needed() holds the srcu read
> > lock, gets the gp_seq snap and call srcu_funnel_gp_start() passing that
> > snap value.
> > 
> > As the rcu_seq_snap() promises "a full grace period has elapsed since
> > the current time".  In srcu_funnel_gp_start(), the statement
> >   rcu_seq_done(&ssp->srcu_gp_seq, s)
> > always return false.
> > 
> > The same condition stands for srcu_funnel_exp_start(). Hence removing
> > all the checks of rcu_seq_done().
> > 
> > Test info:
> >   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> > without any failure.
> 
> Nice catch!!!  And I do appreciate the testing.
> 
> But if we are going to do this, let's please also place lockdep assertions
> in srcu_funnel_exp_start() and srcu_funnel_gp_start() to verify that these
> functions are in fact invoked within an SRCU read-side critical section.
> Also a WARN_ON_ONCE(rcu_seq_done(&ssp->srcu_gp_seq, s)), please.
> 

OK, I will do both.

> Things changed to make the rcu_seq_done() unnecessary, so they could just
> as easily change again.
> 

Yes. It is wise to prevent from the future variation.

Thanks,

	Pingfan

> 							Thanx, Paul
> 
> > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > Cc: Frederic Weisbecker <frederic@kernel.org>
> > Cc: Josh Triplett <josh@joshtriplett.org>
> > Cc: Steven Rostedt <rostedt@goodmis.org>
> > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > To: rcu@vger.kernel.org
> > ---
> >  kernel/rcu/srcutree.c | 13 ++++++-------
> >  1 file changed, 6 insertions(+), 7 deletions(-)
> > 
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index 1c304fec89c0..7df59fc8073e 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -851,8 +851,7 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
> >  	if (snp)
> >  		for (; snp != NULL; snp = snp->srcu_parent) {
> >  			sgsne = READ_ONCE(snp->srcu_gp_seq_needed_exp);
> > -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) ||
> > -			    (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s)))
> > +			if (!srcu_invl_snp_seq(sgsne) && ULONG_CMP_GE(sgsne, s))
> >  				return;
> >  			spin_lock_irqsave_rcu_node(snp, flags);
> >  			sgsne = snp->srcu_gp_seq_needed_exp;
> > @@ -878,6 +877,9 @@ static void srcu_funnel_exp_start(struct srcu_struct *ssp, struct srcu_node *snp
> >   *
> >   * Note that this function also does the work of srcu_funnel_exp_start(),
> >   * in some cases by directly invoking it.
> > + *
> > + * The srcu read lock should be hold around this function. And s is a seq snap
> > + * after holding that lock.
> >   */
> >  static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
> >  				 unsigned long s, bool do_norm)
> > @@ -898,8 +900,6 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
> >  	if (snp_leaf)
> >  		/* Each pass through the loop does one level of the srcu_node tree. */
> >  		for (snp = snp_leaf; snp != NULL; snp = snp->srcu_parent) {
> > -			if (rcu_seq_done(&ssp->srcu_gp_seq, s) && snp != snp_leaf)
> > -				return; /* GP already done and CBs recorded. */
> >  			spin_lock_irqsave_rcu_node(snp, flags);
> >  			snp_seq = snp->srcu_have_cbs[idx];
> >  			if (!srcu_invl_snp_seq(snp_seq) && ULONG_CMP_GE(snp_seq, s)) {
> > @@ -935,9 +935,8 @@ static void srcu_funnel_gp_start(struct srcu_struct *ssp, struct srcu_data *sdp,
> >  	if (!do_norm && ULONG_CMP_LT(ssp->srcu_gp_seq_needed_exp, s))
> >  		WRITE_ONCE(ssp->srcu_gp_seq_needed_exp, s);
> >  
> > -	/* If grace period not already done and none in progress, start it. */
> > -	if (!rcu_seq_done(&ssp->srcu_gp_seq, s) &&
> > -	    rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
> > +	/* If grace period not already in progress, start it. */
> > +	if (rcu_seq_state(ssp->srcu_gp_seq) == SRCU_STATE_IDLE) {
> >  		WARN_ON_ONCE(ULONG_CMP_GE(ssp->srcu_gp_seq, ssp->srcu_gp_seq_needed));
> >  		srcu_gp_start(ssp);
> >  
> > -- 
> > 2.31.1
> > 

Re: [PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Pingfan Liu]

On Mon, Nov 21, 2022 at 05:19:16PM -0800, Paul E. McKenney wrote:
> On Sun, Nov 20, 2022 at 11:40:14AM +0800, Pingfan Liu wrote:
> > At present, snp->srcu_have_cbs[idx] is updated by either
> > srcu_funnel_gp_start() or srcu_gp_end().
> > 
> > But as the code changes, now, srcu_funnel_gp_start() is called with srcu
> > read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
> > whose counter field always proceeds that of the srcu_gp_seq by one or two.
> > 
> > If the seq snap only proceeds by one, the state machine should be in
> > state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
> > machine from moving ahead. So when srcu_gp_end() updates
> > snp->srcu_have_cbs[idx], the idx must be the past idx for
> > srcu_funnel_gp_start() that is cared by nobody.
> > 
> > So removing the unnecessary updating in srcu_gp_end().
> 
> This looks plausible, good eyes!
> 
> But is there a debug check that could verify that this is unnecessary?
> Logical reasoning is all well and good, but the actual system always
> wins arguments.  ;-)
> 

Agree. Reasoning may miss some ground and render a wrong result.

But it is a little hard to demonstrate the past idx is not accessed. I
will go on to figure a way out.


Thanks,

	Pingfan

> 							Thanx, Paul
> 
> > Test info:
> >   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> > without any failure.
> > 
> > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > Cc: Frederic Weisbecker <frederic@kernel.org>
> > Cc: Josh Triplett <josh@joshtriplett.org>
> > Cc: Steven Rostedt <rostedt@goodmis.org>
> > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > To: rcu@vger.kernel.org
> > ---
> >  kernel/rcu/srcutree.c | 2 --
> >  1 file changed, 2 deletions(-)
> > 
> > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > index 7df59fc8073e..c54d6c04751f 100644
> > --- a/kernel/rcu/srcutree.c
> > +++ b/kernel/rcu/srcutree.c
> > @@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
> >  			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
> >  			if (last_lvl)
> >  				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > -			snp->srcu_have_cbs[idx] = gpseq;
> > -			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> >  			sgsne = snp->srcu_gp_seq_needed_exp;
> >  			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> >  				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > -- 
> > 2.31.1
> > 

Re: [PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Paul E. McKenney]

On Tue, Nov 22, 2022 at 05:59:12PM +0800, Pingfan Liu wrote:
> On Mon, Nov 21, 2022 at 05:19:16PM -0800, Paul E. McKenney wrote:
> > On Sun, Nov 20, 2022 at 11:40:14AM +0800, Pingfan Liu wrote:
> > > At present, snp->srcu_have_cbs[idx] is updated by either
> > > srcu_funnel_gp_start() or srcu_gp_end().
> > > 
> > > But as the code changes, now, srcu_funnel_gp_start() is called with srcu
> > > read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
> > > whose counter field always proceeds that of the srcu_gp_seq by one or two.
> > > 
> > > If the seq snap only proceeds by one, the state machine should be in
> > > state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
> > > machine from moving ahead. So when srcu_gp_end() updates
> > > snp->srcu_have_cbs[idx], the idx must be the past idx for
> > > srcu_funnel_gp_start() that is cared by nobody.
> > > 
> > > So removing the unnecessary updating in srcu_gp_end().
> > 
> > This looks plausible, good eyes!
> > 
> > But is there a debug check that could verify that this is unnecessary?
> > Logical reasoning is all well and good, but the actual system always
> > wins arguments.  ;-)
> > 
> 
> Agree. Reasoning may miss some ground and render a wrong result.
> 
> But it is a little hard to demonstrate the past idx is not accessed. I
> will go on to figure a way out.

On a 64-bit system especially, it should be easy to generate a pattern
that never actually occurs.  Even on a 32-bit system, aren't there bit
patterns in the low-order bits that never occur?

Wouldn't it be possible to check for those?

							Thanx, Paul

> Thanks,
> 
> 	Pingfan
> 
> > 							Thanx, Paul
> > 
> > > Test info:
> > >   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> > > without any failure.
> > > 
> > > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > > Cc: Frederic Weisbecker <frederic@kernel.org>
> > > Cc: Josh Triplett <josh@joshtriplett.org>
> > > Cc: Steven Rostedt <rostedt@goodmis.org>
> > > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > To: rcu@vger.kernel.org
> > > ---
> > >  kernel/rcu/srcutree.c | 2 --
> > >  1 file changed, 2 deletions(-)
> > > 
> > > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > > index 7df59fc8073e..c54d6c04751f 100644
> > > --- a/kernel/rcu/srcutree.c
> > > +++ b/kernel/rcu/srcutree.c
> > > @@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
> > >  			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
> > >  			if (last_lvl)
> > >  				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > -			snp->srcu_have_cbs[idx] = gpseq;
> > > -			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > >  			sgsne = snp->srcu_gp_seq_needed_exp;
> > >  			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > >  				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > -- 
> > > 2.31.1
> > > 

Re: [PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Pingfan Liu]

On Tue, Nov 22, 2022 at 06:45:49AM -0800, Paul E. McKenney wrote:
> On Tue, Nov 22, 2022 at 05:59:12PM +0800, Pingfan Liu wrote:
> > On Mon, Nov 21, 2022 at 05:19:16PM -0800, Paul E. McKenney wrote:
> > > On Sun, Nov 20, 2022 at 11:40:14AM +0800, Pingfan Liu wrote:
> > > > At present, snp->srcu_have_cbs[idx] is updated by either
> > > > srcu_funnel_gp_start() or srcu_gp_end().
> > > > 
> > > > But as the code changes, now, srcu_funnel_gp_start() is called with srcu
> > > > read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
> > > > whose counter field always proceeds that of the srcu_gp_seq by one or two.
> > > > 
> > > > If the seq snap only proceeds by one, the state machine should be in
> > > > state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
> > > > machine from moving ahead. So when srcu_gp_end() updates
> > > > snp->srcu_have_cbs[idx], the idx must be the past idx for
> > > > srcu_funnel_gp_start() that is cared by nobody.
> > > > 
> > > > So removing the unnecessary updating in srcu_gp_end().
> > > 
> > > This looks plausible, good eyes!
> > > 
> > > But is there a debug check that could verify that this is unnecessary?
> > > Logical reasoning is all well and good, but the actual system always
> > > wins arguments.  ;-)
> > > 
> > 
> > Agree. Reasoning may miss some ground and render a wrong result.
> > 
> > But it is a little hard to demonstrate the past idx is not accessed. I
> > will go on to figure a way out.
> 
> On a 64-bit system especially, it should be easy to generate a pattern
> that never actually occurs.  Even on a 32-bit system, aren't there bit
> patterns in the low-order bits that never occur?
> 
> Wouldn't it be possible to check for those?
> 

I had thought about that way, but that means a write and cache invalid.

While on the other way, I still rely on the logic to add some check
code, which should be avoided.

Finally, I turn back to the way which you suggested. But I have a new
plan for this patch. So I will send out V2 for the other two patches.

As for this one, it will come in the next series.

Thanks,

	Pingfan


> 							Thanx, Paul
> 
> > Thanks,
> > 
> > 	Pingfan
> > 
> > > 							Thanx, Paul
> > > 
> > > > Test info:
> > > >   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> > > > without any failure.
> > > > 
> > > > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > > > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > > > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > > > Cc: Frederic Weisbecker <frederic@kernel.org>
> > > > Cc: Josh Triplett <josh@joshtriplett.org>
> > > > Cc: Steven Rostedt <rostedt@goodmis.org>
> > > > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > > To: rcu@vger.kernel.org
> > > > ---
> > > >  kernel/rcu/srcutree.c | 2 --
> > > >  1 file changed, 2 deletions(-)
> > > > 
> > > > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > > > index 7df59fc8073e..c54d6c04751f 100644
> > > > --- a/kernel/rcu/srcutree.c
> > > > +++ b/kernel/rcu/srcutree.c
> > > > @@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
> > > >  			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
> > > >  			if (last_lvl)
> > > >  				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > > -			snp->srcu_have_cbs[idx] = gpseq;
> > > > -			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > > >  			sgsne = snp->srcu_gp_seq_needed_exp;
> > > >  			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > > >  				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > > -- 
> > > > 2.31.1
> > > > 

Re: [PATCH 2/2] srcu: Remove needless updating of srcu_have_cbs in srcu_gp_end()

[Paul E. McKenney]

On Wed, Nov 23, 2022 at 09:29:17PM +0800, Pingfan Liu wrote:
> On Tue, Nov 22, 2022 at 06:45:49AM -0800, Paul E. McKenney wrote:
> > On Tue, Nov 22, 2022 at 05:59:12PM +0800, Pingfan Liu wrote:
> > > On Mon, Nov 21, 2022 at 05:19:16PM -0800, Paul E. McKenney wrote:
> > > > On Sun, Nov 20, 2022 at 11:40:14AM +0800, Pingfan Liu wrote:
> > > > > At present, snp->srcu_have_cbs[idx] is updated by either
> > > > > srcu_funnel_gp_start() or srcu_gp_end().
> > > > > 
> > > > > But as the code changes, now, srcu_funnel_gp_start() is called with srcu
> > > > > read lock held. And its input parameter s, s = rcu_seq_snap(&ssp->srcu_gp_seq),
> > > > > whose counter field always proceeds that of the srcu_gp_seq by one or two.
> > > > > 
> > > > > If the seq snap only proceeds by one, the state machine should be in
> > > > > state SRCU_STATE_IDLE, the held srcu read lock will prevent the state
> > > > > machine from moving ahead. So when srcu_gp_end() updates
> > > > > snp->srcu_have_cbs[idx], the idx must be the past idx for
> > > > > srcu_funnel_gp_start() that is cared by nobody.
> > > > > 
> > > > > So removing the unnecessary updating in srcu_gp_end().
> > > > 
> > > > This looks plausible, good eyes!
> > > > 
> > > > But is there a debug check that could verify that this is unnecessary?
> > > > Logical reasoning is all well and good, but the actual system always
> > > > wins arguments.  ;-)
> > > > 
> > > 
> > > Agree. Reasoning may miss some ground and render a wrong result.
> > > 
> > > But it is a little hard to demonstrate the past idx is not accessed. I
> > > will go on to figure a way out.
> > 
> > On a 64-bit system especially, it should be easy to generate a pattern
> > that never actually occurs.  Even on a 32-bit system, aren't there bit
> > patterns in the low-order bits that never occur?
> > 
> > Wouldn't it be possible to check for those?
> 
> I had thought about that way, but that means a write and cache invalid.

Which would be one reason to do it only within kernels built with
CONFIG_PROVE_RCU=y.  In addition, this write occurs only rarely, so its
effect on overall performance should be extremely small.

> While on the other way, I still rely on the logic to add some check
> code, which should be avoided.

The eternal vulnerabilty of logic is that it is always based on
assumptions, which cannot be proven correct, only invalidated.  ;-)

> Finally, I turn back to the way which you suggested. But I have a new
> plan for this patch. So I will send out V2 for the other two patches.
> 
> As for this one, it will come in the next series.

Looking forward to seeing it, then.

							Thanx, Paul

> Thanks,
> 
> 	Pingfan
> 
> 
> > 							Thanx, Paul
> > 
> > > Thanks,
> > > 
> > > 	Pingfan
> > > 
> > > > 							Thanx, Paul
> > > > 
> > > > > Test info:
> > > > >   Running "tools/testing/selftests/rcutorture/bin/kvm.sh --allcpus --duration 10h --configs 18*SRCU-P"
> > > > > without any failure.
> > > > > 
> > > > > Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
> > > > > Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> > > > > Cc: "Paul E. McKenney" <paulmck@kernel.org>
> > > > > Cc: Frederic Weisbecker <frederic@kernel.org>
> > > > > Cc: Josh Triplett <josh@joshtriplett.org>
> > > > > Cc: Steven Rostedt <rostedt@goodmis.org>
> > > > > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > > > To: rcu@vger.kernel.org
> > > > > ---
> > > > >  kernel/rcu/srcutree.c | 2 --
> > > > >  1 file changed, 2 deletions(-)
> > > > > 
> > > > > diff --git a/kernel/rcu/srcutree.c b/kernel/rcu/srcutree.c
> > > > > index 7df59fc8073e..c54d6c04751f 100644
> > > > > --- a/kernel/rcu/srcutree.c
> > > > > +++ b/kernel/rcu/srcutree.c
> > > > > @@ -783,8 +783,6 @@ static void srcu_gp_end(struct srcu_struct *ssp)
> > > > >  			last_lvl = snp >= ssp->level[rcu_num_lvls - 1];
> > > > >  			if (last_lvl)
> > > > >  				cbs = ss_state < SRCU_SIZE_BIG || snp->srcu_have_cbs[idx] == gpseq;
> > > > > -			snp->srcu_have_cbs[idx] = gpseq;
> > > > > -			rcu_seq_set_state(&snp->srcu_have_cbs[idx], 1);
> > > > >  			sgsne = snp->srcu_gp_seq_needed_exp;
> > > > >  			if (srcu_invl_snp_seq(sgsne) || ULONG_CMP_LT(sgsne, gpseq))
> > > > >  				WRITE_ONCE(snp->srcu_gp_seq_needed_exp, gpseq);
> > > > > -- 
> > > > > 2.31.1
> > > > >