| Message ID | 20221120034014.7390-3-kernelfans@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | srcu: Optimize when srcu_gp_start_if_needed() holds | expand |
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 >
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 > >
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 > > >
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 > > > >
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 > > > > >
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);
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(-)