linux-kernel - Re: [PATCH 1/2] rcu: Comment on the extraneous delta test on rcu_seq_done

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <Z9wjBT3RQDUrFdbE@p200300d06f3e9880e1f174d4afcc9316.dip0.t-ipconnect.de>
Date: Thu, 20 Mar 2025 15:15:33 +0100
From: Frederic Weisbecker <frederic@...nel.org>
To: Joel Fernandes <joelagnelf@...dia.com>
Cc: "Paul E. McKenney" <paulmck@...nel.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Boqun Feng <boqun.feng@...il.com>,
	Neeraj Upadhyay <neeraj.upadhyay@....com>,
	Uladzislau Rezki <urezki@...il.com>,
	Zqiang <qiang.zhang1211@...il.com>, rcu <rcu@...r.kernel.org>
Subject: Re: [PATCH 1/2] rcu: Comment on the extraneous delta test on
 rcu_seq_done_exact()

Le Wed, Mar 19, 2025 at 03:38:31PM -0400, Joel Fernandes a écrit :
> On Tue, Mar 18, 2025 at 11:37:38AM -0700, Paul E. McKenney wrote:
> > On Tue, Mar 18, 2025 at 02:56:18PM +0100, Frederic Weisbecker wrote:
> > > The numbers used in rcu_seq_done_exact() lack some explanation behind
> > > their magic. Especially after the commit:
> > > 
> > >     85aad7cc4178 ("rcu: Fix get_state_synchronize_rcu_full() GP-start detection")
> > > 
> > > which reported a subtle issue where a new GP sequence snapshot was taken
> > > on the root node state while a grace period had already been started and
> > > reflected on the global state sequence but not yet on the root node
> > > sequence, making a polling user waiting on a wrong already started grace
> > > period that would ignore freshly online CPUs.
> > > 
> > > The fix involved taking the snaphot on the global state sequence and
> > > waiting on the root node sequence. And since a grace period is first
> > > started on the global state and only afterward reflected on the root
> > > node, a snapshot taken on the global state sequence might be two full
> > > grace periods ahead of the root node as in the following example:
> > > 
> > > rnp->gp_seq = rcu_state.gp_seq = 0
> > > 
> > >     CPU 0                                           CPU 1
> > >     -----                                           -----
> > >     // rcu_state.gp_seq = 1
> > >     rcu_seq_start(&rcu_state.gp_seq)
> > >                                                     // snap = 8
> > >                                                     snap = rcu_seq_snap(&rcu_state.gp_seq)
> > >                                                     // Two full GP differences
> > >                                                     rcu_seq_done_exact(&rnp->gp_seq, snap)
> > >     // rnp->gp_seq = 1
> > >     WRITE_ONCE(rnp->gp_seq, rcu_state.gp_seq);
> > > 
> > > Add a comment about those expectations and to clarify the magic within
> > > the relevant function.
> > > 
> > > Signed-off-by: Frederic Weisbecker <frederic@...nel.org>
> > 
> > Reviewed-by: Paul E. McKenney <paulmck@...nel.org>
> > 
> > But it would of course be good to get reviews from the others.
> 
> I actually don't agree that the magic in the rcu_seq_done_exact() function about the
> ~2 GPs is related to the lag between rcu_state.gp_seq and root rnp->gp_seq,
> because the small lag can just as well survive with the rcu_seq_done()
> function in the above sequence right?
> 
> The rcu_seq_done_exact() function on the other hand is more about not being
> stuck in the ULONG_MAX/2 guard band, but to actually get to that, you need a
> wrap around to happen and the delta between "rnp->gp_seq" and "snap" to be at
> least ULONG_MAX/2 AFAIU.
> 
> So the only time this magic will matter is if you have a huge delta between
> what is being compared, not just 2 GPs.

You're right, and perhaps I should have made it more specific that my comment
only explains the magic "3" number here, in that if it were "2" instead, there
could be accidents with 2 full GPs difference (which is possible) spuriously
accounted as a wrap around.

Thanks.

> 
> Or, did I miss something?
> 
> (Also sorry about slow email responses this week as I had my presentation
> today and was busy preparing this week and attending other presentations at
> OSPM, I'll provide an update on that soon!).
> 
> thanks,
> 
>  - Joel
> 
> 
> 
> 
> 
> 
> 
> 
> 
> > 
> > > ---
> > >  kernel/rcu/rcu.h | 7 +++++++
> > >  1 file changed, 7 insertions(+)
> > > 
> > > diff --git a/kernel/rcu/rcu.h b/kernel/rcu/rcu.h
> > > index eed2951a4962..7acf1f36dd6c 100644
> > > --- a/kernel/rcu/rcu.h
> > > +++ b/kernel/rcu/rcu.h
> > > @@ -157,6 +157,13 @@ static inline bool rcu_seq_done(unsigned long *sp, unsigned long s)
> > >   * Given a snapshot from rcu_seq_snap(), determine whether or not a
> > >   * full update-side operation has occurred, but do not allow the
> > >   * (ULONG_MAX / 2) safety-factor/guard-band.
> > > + *
> > > + * The token returned by get_state_synchronize_rcu_full() is based on
> > > + * rcu_state.gp_seq but it is tested in poll_state_synchronize_rcu_full()
> > > + * against the root rnp->gp_seq. Since rcu_seq_start() is first called
> > > + * on rcu_state.gp_seq and only later reflected on the root rnp->gp_seq,
> > > + * it is possible that rcu_seq_snap(rcu_state.gp_seq) returns 2 full grace
> > > + * periods ahead of the root rnp->gp_seq.
> > >   */
> > >  static inline bool rcu_seq_done_exact(unsigned long *sp, unsigned long s)
> > >  {
> > > -- 
> > > 2.48.1
> > >