[PATCH tip/core/rcu 0/3] Polling RCU grace-period interfaces for v5.13

[PATCH tip/core/rcu 0/3] Polling RCU grace-period interfaces for v5.13

[Paul E. McKenney]

Hello!

This series provides additional polling interfaces for RCU, so that
an updater may initiate and poll for completion of an RCU grace period
despite never being invoked from a sleepable region of code.  These are
similar to the corresponding SRCU interfaces, give or take additional
restrictions to avoid deadlock with the scheduler.

1.	Provide polling interfaces for Tree RCU grace periods.

2.	Provide polling interfaces for Tiny RCU grace periods.

3.	Test start_poll_synchronize_rcu() and
	poll_state_synchronize_rcu().

						Thanx, Paul

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

 include/linux/rcutiny.h |   11 ++++---
 include/linux/rcutree.h |    2 +
 kernel/rcu/rcutorture.c |   12 ++------
 kernel/rcu/tiny.c       |   40 +++++++++++++++++++++++++++
 kernel/rcu/tree.c       |   70 ++++++++++++++++++++++++++++++++++++++++++++----
 5 files changed, 116 insertions(+), 19 deletions(-)

[PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[paulmck]

From: "Paul E. McKenney" <paulmck@kernel.org>

There is a need for a non-blocking polling interface for RCU grace
periods, so this commit supplies start_poll_synchronize_rcu() and
poll_state_synchronize_rcu() for this purpose.  Note that the existing
get_state_synchronize_rcu() may be used if future grace periods are
inevitable (perhaps due to a later call_rcu() invocation).  The new
start_poll_synchronize_rcu() is to be used if future grace periods
might not otherwise happen.  Finally, poll_state_synchronize_rcu()
provides a lockless check for a grace period having elapsed since
the corresponding call to either of the get_state_synchronize_rcu()
or start_poll_synchronize_rcu().

As with get_state_synchronize_rcu(), the return value from either
get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
to a later call to either poll_state_synchronize_rcu() or the existing
(might_sleep) cond_synchronize_rcu().

Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 include/linux/rcutree.h |  2 ++
 kernel/rcu/tree.c       | 70 +++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 67 insertions(+), 5 deletions(-)

diff --git a/include/linux/rcutree.h b/include/linux/rcutree.h
index df578b7..b89b541 100644
--- a/include/linux/rcutree.h
+++ b/include/linux/rcutree.h
@@ -41,6 +41,8 @@ void rcu_momentary_dyntick_idle(void);
 void kfree_rcu_scheduler_running(void);
 bool rcu_gp_might_be_stalled(void);
 unsigned long get_state_synchronize_rcu(void);
+unsigned long start_poll_synchronize_rcu(void);
+bool poll_state_synchronize_rcu(unsigned long oldstate);
 void cond_synchronize_rcu(unsigned long oldstate);
 
 void rcu_idle_enter(void);
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index da6f521..8e0a140 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3774,8 +3774,8 @@ EXPORT_SYMBOL_GPL(synchronize_rcu);
  * get_state_synchronize_rcu - Snapshot current RCU state
  *
  * Returns a cookie that is used by a later call to cond_synchronize_rcu()
- * to determine whether or not a full grace period has elapsed in the
- * meantime.
+ * or poll_state_synchronize_rcu() to determine whether or not a full
+ * grace period has elapsed in the meantime.
  */
 unsigned long get_state_synchronize_rcu(void)
 {
@@ -3789,13 +3789,73 @@ unsigned long get_state_synchronize_rcu(void)
 EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
 
 /**
+ * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
+ *
+ * Returns a cookie that is used by a later call to cond_synchronize_rcu()
+ * or poll_state_synchronize_rcu() to determine whether or not a full
+ * grace period has elapsed in the meantime.  If the needed grace period
+ * is not already slated to start, notifies RCU core of the need for that
+ * grace period.
+ *
+ * Interrupts must be enabled for the case where it is necessary to awaken
+ * the grace-period kthread.
+ */
+unsigned long start_poll_synchronize_rcu(void)
+{
+	unsigned long flags;
+	unsigned long gp_seq = get_state_synchronize_rcu();
+	bool needwake;
+	struct rcu_data *rdp;
+	struct rcu_node *rnp;
+
+	lockdep_assert_irqs_enabled();
+	local_irq_save(flags);
+	rdp = this_cpu_ptr(&rcu_data);
+	rnp = rdp->mynode;
+	raw_spin_lock_rcu_node(rnp); // irqs already disabled.
+	needwake = rcu_start_this_gp(rnp, rdp, gp_seq);
+	raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
+	if (needwake)
+		rcu_gp_kthread_wake();
+	return gp_seq;
+}
+EXPORT_SYMBOL_GPL(start_poll_synchronize_rcu);
+
+/**
+ * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
+ *
+ * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
+ *
+ * If a full RCU grace period has elapsed since the earlier call from
+ * which oldstate was obtained, return @true, otherwise return @false.
+ * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
+ *
+ * Yes, this function does not take counter wrap into account.
+ * But counter wrap is harmless.  If the counter wraps, we have waited for
+ * more than 2 billion grace periods (and way more on a 64-bit system!).
+ * Those needing to keep oldstate values for very long time periods
+ * (many hours even on 32-bit systems) should check them occasionally
+ * and either refresh them or set a flag indicating that the grace period
+ * has completed.
+ */
+bool poll_state_synchronize_rcu(unsigned long oldstate)
+{
+	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
+		smp_mb(); /* Ensure GP ends before subsequent accesses. */
+		return true;
+	}
+	return false;
+}
+EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu);
+
+/**
  * cond_synchronize_rcu - Conditionally wait for an RCU grace period
  *
  * @oldstate: return value from earlier call to get_state_synchronize_rcu()
  *
  * If a full RCU grace period has elapsed since the earlier call to
- * get_state_synchronize_rcu(), just return.  Otherwise, invoke
- * synchronize_rcu() to wait for a full grace period.
+ * get_state_synchronize_rcu() or start_poll_synchronize_rcu(), just return.
+ * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
  *
  * Yes, this function does not take counter wrap into account.  But
  * counter wrap is harmless.  If the counter wraps, we have waited for
@@ -3804,7 +3864,7 @@ EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
  */
 void cond_synchronize_rcu(unsigned long oldstate)
 {
-	if (!rcu_seq_done(&rcu_state.gp_seq, oldstate))
+	if (!poll_state_synchronize_rcu(oldstate))
 		synchronize_rcu();
 	else
 		smp_mb(); /* Ensure GP ends before subsequent accesses. */
-- 
2.9.5

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> From: "Paul E. McKenney" <paulmck@kernel.org>
> 
> There is a need for a non-blocking polling interface for RCU grace
> periods, so this commit supplies start_poll_synchronize_rcu() and
> poll_state_synchronize_rcu() for this purpose.  Note that the existing
> get_state_synchronize_rcu() may be used if future grace periods are
> inevitable (perhaps due to a later call_rcu() invocation).  The new
> start_poll_synchronize_rcu() is to be used if future grace periods
> might not otherwise happen.

By future grace period, you mean if a grace period has been started right
_before_ we start polling, right?


> Finally, poll_state_synchronize_rcu()
> provides a lockless check for a grace period having elapsed since
> the corresponding call to either of the get_state_synchronize_rcu()
> or start_poll_synchronize_rcu().
> 
> As with get_state_synchronize_rcu(), the return value from either
> get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> to a later call to either poll_state_synchronize_rcu() or the existing
> (might_sleep) cond_synchronize_rcu().
> 
> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
[...]
>  /**
> + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> + *
> + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> + * or poll_state_synchronize_rcu() to determine whether or not a full
> + * grace period has elapsed in the meantime.  If the needed grace period
> + * is not already slated to start, notifies RCU core of the need for that
> + * grace period.
> + *
> + * Interrupts must be enabled for the case where it is necessary to awaken
> + * the grace-period kthread.
> + */
> +unsigned long start_poll_synchronize_rcu(void)
> +{
> +	unsigned long flags;
> +	unsigned long gp_seq = get_state_synchronize_rcu();
> +	bool needwake;
> +	struct rcu_data *rdp;
> +	struct rcu_node *rnp;
> +
> +	lockdep_assert_irqs_enabled();
> +	local_irq_save(flags);
> +	rdp = this_cpu_ptr(&rcu_data);
> +	rnp = rdp->mynode;
> +	raw_spin_lock_rcu_node(rnp); // irqs already disabled.
> +	needwake = rcu_start_this_gp(rnp, rdp, gp_seq);

I'm a bit surprised we don't start a new grace period instead of snapshotting
the current one.

So if we do this:

   //start grace period gp_num=5

   old = p;
   rcu_assign_pointer(p, new);

   num = start_poll_synchronize_rcu(); // num = 5

   //grace period ends, start new gp_num=6

   poll_state_synchronize_rcu(num); // rcu seq is done

   kfree(old);

Isn't there a risk that other CPUs still see the old pointer?

Of course I know I'm missing something obvious :-)

Thanks.

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
>  /**
> + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> + *
> + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> + * or poll_state_synchronize_rcu() to determine whether or not a full
> + * grace period has elapsed in the meantime.  If the needed grace period
> + * is not already slated to start, notifies RCU core of the need for that
> + * grace period.
> + *
> + * Interrupts must be enabled for the case where it is necessary to awaken
> + * the grace-period kthread.
> + */
> +unsigned long start_poll_synchronize_rcu(void)
> +{
> +	unsigned long flags;
> +	unsigned long gp_seq = get_state_synchronize_rcu();

Ah! It's using rcu_seq_snap() and not rcu_seq_current() and therefore it's
waiting for a safe future grace period, right?

If so, please discard my previous email.

Thanks.

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Fri, Mar 12, 2021 at 01:26:47PM +0100, Frederic Weisbecker wrote:
> On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> >  /**
> > + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> > + *
> > + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> > + * or poll_state_synchronize_rcu() to determine whether or not a full
> > + * grace period has elapsed in the meantime.  If the needed grace period
> > + * is not already slated to start, notifies RCU core of the need for that
> > + * grace period.
> > + *
> > + * Interrupts must be enabled for the case where it is necessary to awaken
> > + * the grace-period kthread.
> > + */
> > +unsigned long start_poll_synchronize_rcu(void)
> > +{
> > +	unsigned long flags;
> > +	unsigned long gp_seq = get_state_synchronize_rcu();
> 
> Ah! It's using rcu_seq_snap() and not rcu_seq_current() and therefore it's
> waiting for a safe future grace period, right?

Exactly!  ;-)

							Thanx, Paul

> If so, please discard my previous email.
> 
> Thanks.

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> +/**
> + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> + *
> + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> + *
> + * If a full RCU grace period has elapsed since the earlier call from
> + * which oldstate was obtained, return @true, otherwise return @false.
> + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> + *
> + * Yes, this function does not take counter wrap into account.
> + * But counter wrap is harmless.  If the counter wraps, we have waited for
> + * more than 2 billion grace periods (and way more on a 64-bit system!).
> + * Those needing to keep oldstate values for very long time periods
> + * (many hours even on 32-bit systems) should check them occasionally
> + * and either refresh them or set a flag indicating that the grace period
> + * has completed.
> + */
> +bool poll_state_synchronize_rcu(unsigned long oldstate)
> +{
> +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> +		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> +		return true;
> +	}
> +	return false;
> +}
> +EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu);
> +
> +/**
>   * cond_synchronize_rcu - Conditionally wait for an RCU grace period
>   *
>   * @oldstate: return value from earlier call to get_state_synchronize_rcu()
>   *
>   * If a full RCU grace period has elapsed since the earlier call to
> - * get_state_synchronize_rcu(), just return.  Otherwise, invoke
> - * synchronize_rcu() to wait for a full grace period.
> + * get_state_synchronize_rcu() or start_poll_synchronize_rcu(), just return.
> + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
>   *
>   * Yes, this function does not take counter wrap into account.  But
>   * counter wrap is harmless.  If the counter wraps, we have waited for
> @@ -3804,7 +3864,7 @@ EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
>   */
>  void cond_synchronize_rcu(unsigned long oldstate)
>  {
> -	if (!rcu_seq_done(&rcu_state.gp_seq, oldstate))
> +	if (!poll_state_synchronize_rcu(oldstate))
>  		synchronize_rcu();
>  	else
>  		smp_mb(); /* Ensure GP ends before subsequent accesses. */

poll_state_synchronize_rcu() already does the full barrier.

> -- 
> 2.9.5
> 

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Tue, Mar 16, 2021 at 03:47:22PM +0100, Frederic Weisbecker wrote:
> On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> > +/**
> > + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> > + *
> > + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> > + *
> > + * If a full RCU grace period has elapsed since the earlier call from
> > + * which oldstate was obtained, return @true, otherwise return @false.
> > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > + *
> > + * Yes, this function does not take counter wrap into account.
> > + * But counter wrap is harmless.  If the counter wraps, we have waited for
> > + * more than 2 billion grace periods (and way more on a 64-bit system!).
> > + * Those needing to keep oldstate values for very long time periods
> > + * (many hours even on 32-bit systems) should check them occasionally
> > + * and either refresh them or set a flag indicating that the grace period
> > + * has completed.
> > + */
> > +bool poll_state_synchronize_rcu(unsigned long oldstate)
> > +{
> > +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> > +		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> > +		return true;
> > +	}
> > +	return false;
> > +}
> > +EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu);
> > +
> > +/**
> >   * cond_synchronize_rcu - Conditionally wait for an RCU grace period
> >   *
> >   * @oldstate: return value from earlier call to get_state_synchronize_rcu()
> >   *
> >   * If a full RCU grace period has elapsed since the earlier call to
> > - * get_state_synchronize_rcu(), just return.  Otherwise, invoke
> > - * synchronize_rcu() to wait for a full grace period.
> > + * get_state_synchronize_rcu() or start_poll_synchronize_rcu(), just return.
> > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> >   *
> >   * Yes, this function does not take counter wrap into account.  But
> >   * counter wrap is harmless.  If the counter wraps, we have waited for
> > @@ -3804,7 +3864,7 @@ EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
> >   */
> >  void cond_synchronize_rcu(unsigned long oldstate)
> >  {
> > -	if (!rcu_seq_done(&rcu_state.gp_seq, oldstate))
> > +	if (!poll_state_synchronize_rcu(oldstate))
> >  		synchronize_rcu();
> >  	else
> >  		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> 
> poll_state_synchronize_rcu() already does the full barrier.

Right you are!  Good catch, thank you!!!

I will fold removing this smp_mb() in with attribution.

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> +/**
> + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> + *
> + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> + *
> + * If a full RCU grace period has elapsed since the earlier call from
> + * which oldstate was obtained, return @true, otherwise return @false.
> + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> + *
> + * Yes, this function does not take counter wrap into account.
> + * But counter wrap is harmless.  If the counter wraps, we have waited for
> + * more than 2 billion grace periods (and way more on a 64-bit system!).
> + * Those needing to keep oldstate values for very long time periods
> + * (many hours even on 32-bit systems) should check them occasionally
> + * and either refresh them or set a flag indicating that the grace period
> + * has completed.
> + */
> +bool poll_state_synchronize_rcu(unsigned long oldstate)
> +{
> +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> +		smp_mb(); /* Ensure GP ends before subsequent accesses. */

Also as usual I'm a bit lost with the reason behind those memory barriers.
So this is ordering the read on rcu_state.gp_seq against something (why not an
smp_rmb() btw?). And what does it pair with?

Thanks.

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Tue, Mar 16, 2021 at 04:17:50PM +0100, Frederic Weisbecker wrote:
> On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> > +/**
> > + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> > + *
> > + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> > + *
> > + * If a full RCU grace period has elapsed since the earlier call from
> > + * which oldstate was obtained, return @true, otherwise return @false.
> > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > + *
> > + * Yes, this function does not take counter wrap into account.
> > + * But counter wrap is harmless.  If the counter wraps, we have waited for
> > + * more than 2 billion grace periods (and way more on a 64-bit system!).
> > + * Those needing to keep oldstate values for very long time periods
> > + * (many hours even on 32-bit systems) should check them occasionally
> > + * and either refresh them or set a flag indicating that the grace period
> > + * has completed.
> > + */
> > +bool poll_state_synchronize_rcu(unsigned long oldstate)
> > +{
> > +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> > +		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> 
> Also as usual I'm a bit lost with the reason behind those memory barriers.
> So this is ordering the read on rcu_state.gp_seq against something (why not an
> smp_rmb() btw?). And what does it pair with?

Because it needs to order subsequent writes as well as reads.

It is ordering whatever the RCU user wishes to put after the call to
poll_state_synchronize_rcu() with whatever the RCU user put before
whatever started the grace period that just now completed.  Please
see the synchronize_rcu() comment header for the statement of the
guarantee.  Or that of call_rcu().

For more detail on how these guarantees are implemented, please see
Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst
and its many diagrams.

There are a lot of memory barriers that pair and form larger cycles to
implement this guarantee.  Pretty much all of the calls to the infamous
smp_mb__after_unlock_lock() macro form cycles involving this barrier,
for example.

Please do not hesitate to ask more questions.  This underpins RCU.

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Tue, Mar 16, 2021 at 09:51:01AM -0700, Paul E. McKenney wrote:
> On Tue, Mar 16, 2021 at 04:17:50PM +0100, Frederic Weisbecker wrote:
> > On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> > > +/**
> > > + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> > > + *
> > > + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> > > + *
> > > + * If a full RCU grace period has elapsed since the earlier call from
> > > + * which oldstate was obtained, return @true, otherwise return @false.
> > > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > > + *
> > > + * Yes, this function does not take counter wrap into account.
> > > + * But counter wrap is harmless.  If the counter wraps, we have waited for
> > > + * more than 2 billion grace periods (and way more on a 64-bit system!).
> > > + * Those needing to keep oldstate values for very long time periods
> > > + * (many hours even on 32-bit systems) should check them occasionally
> > > + * and either refresh them or set a flag indicating that the grace period
> > > + * has completed.
> > > + */
> > > +bool poll_state_synchronize_rcu(unsigned long oldstate)
> > > +{
> > > +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> > > +		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> > 
> > Also as usual I'm a bit lost with the reason behind those memory barriers.
> > So this is ordering the read on rcu_state.gp_seq against something (why not an
> > smp_rmb() btw?). And what does it pair with?
> 
> Because it needs to order subsequent writes as well as reads.
> 
> It is ordering whatever the RCU user wishes to put after the call to
> poll_state_synchronize_rcu() with whatever the RCU user put before
> whatever started the grace period that just now completed.  Please
> see the synchronize_rcu() comment header for the statement of the
> guarantee.  Or that of call_rcu().

I see. OTOH the update side's CPU had to report a quiescent state for the
requested grace period to complete. As the quiescent state propagated along
with full ordering up to the root rnp, everything that happened before
rcu_seq_done() should appear before and everything that happened after
rcu_seq_done() should appear after.

Now in the case the update side's CPU is not the last CPU that reported
a quiescent state (and thus not the one that propagated every subsequent
CPUs QS to the final "rcu_state.gp_seq"), the full barrier after rcu_seq_done()
is necessary to order against all the CPUs that reported a QS after the
update side's CPU.

Is that right?


> 
> For more detail on how these guarantees are implemented, please see
> Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst
> and its many diagrams.

Indeed, very useful documentation!

> 
> There are a lot of memory barriers that pair and form larger cycles to
> implement this guarantee.  Pretty much all of the calls to the infamous
> smp_mb__after_unlock_lock() macro form cycles involving this barrier,
> for example.
> 
> Please do not hesitate to ask more questions.  This underpins RCU.

Careful what you wish! ;-)

Thanks.

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Thu, Mar 18, 2021 at 03:59:52PM +0100, Frederic Weisbecker wrote:
> On Tue, Mar 16, 2021 at 09:51:01AM -0700, Paul E. McKenney wrote:
> > On Tue, Mar 16, 2021 at 04:17:50PM +0100, Frederic Weisbecker wrote:
> > > On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> > > > +/**
> > > > + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> > > > + *
> > > > + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> > > > + *
> > > > + * If a full RCU grace period has elapsed since the earlier call from
> > > > + * which oldstate was obtained, return @true, otherwise return @false.
> > > > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > > > + *
> > > > + * Yes, this function does not take counter wrap into account.
> > > > + * But counter wrap is harmless.  If the counter wraps, we have waited for
> > > > + * more than 2 billion grace periods (and way more on a 64-bit system!).
> > > > + * Those needing to keep oldstate values for very long time periods
> > > > + * (many hours even on 32-bit systems) should check them occasionally
> > > > + * and either refresh them or set a flag indicating that the grace period
> > > > + * has completed.
> > > > + */
> > > > +bool poll_state_synchronize_rcu(unsigned long oldstate)
> > > > +{
> > > > +	if (rcu_seq_done(&rcu_state.gp_seq, oldstate)) {
> > > > +		smp_mb(); /* Ensure GP ends before subsequent accesses. */
> > > 
> > > Also as usual I'm a bit lost with the reason behind those memory barriers.
> > > So this is ordering the read on rcu_state.gp_seq against something (why not an
> > > smp_rmb() btw?). And what does it pair with?
> > 
> > Because it needs to order subsequent writes as well as reads.
> > 
> > It is ordering whatever the RCU user wishes to put after the call to
> > poll_state_synchronize_rcu() with whatever the RCU user put before
> > whatever started the grace period that just now completed.  Please
> > see the synchronize_rcu() comment header for the statement of the
> > guarantee.  Or that of call_rcu().
> 
> I see. OTOH the update side's CPU had to report a quiescent state for the
> requested grace period to complete. As the quiescent state propagated along
> with full ordering up to the root rnp, everything that happened before
> rcu_seq_done() should appear before and everything that happened after
> rcu_seq_done() should appear after.
> 
> Now in the case the update side's CPU is not the last CPU that reported
> a quiescent state (and thus not the one that propagated every subsequent
> CPUs QS to the final "rcu_state.gp_seq"), the full barrier after rcu_seq_done()
> is necessary to order against all the CPUs that reported a QS after the
> update side's CPU.
> 
> Is that right?

That is the way I see it.  ;-)

> > For more detail on how these guarantees are implemented, please see
> > Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst
> > and its many diagrams.
> 
> Indeed, very useful documentation!

Glad you like it!

> > There are a lot of memory barriers that pair and form larger cycles to
> > implement this guarantee.  Pretty much all of the calls to the infamous
> > smp_mb__after_unlock_lock() macro form cycles involving this barrier,
> > for example.
> > 
> > Please do not hesitate to ask more questions.  This underpins RCU.
> 
> Careful what you wish! ;-)

;-) ;-) ;-)

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> From: "Paul E. McKenney" <paulmck@kernel.org>
> 
> There is a need for a non-blocking polling interface for RCU grace
> periods, so this commit supplies start_poll_synchronize_rcu() and
> poll_state_synchronize_rcu() for this purpose.  Note that the existing
> get_state_synchronize_rcu() may be used if future grace periods are
> inevitable (perhaps due to a later call_rcu() invocation).  The new
> start_poll_synchronize_rcu() is to be used if future grace periods
> might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> provides a lockless check for a grace period having elapsed since
> the corresponding call to either of the get_state_synchronize_rcu()
> or start_poll_synchronize_rcu().
> 
> As with get_state_synchronize_rcu(), the return value from either
> get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> to a later call to either poll_state_synchronize_rcu() or the existing
> (might_sleep) cond_synchronize_rcu().

It's all a matter of personal taste but if I may suggest some namespace
modifications:

get_state_synchronize_rcu() -> synchronize_rcu_poll_start_raw()
start_poll_synchronize_rcu() -> synchronize_rcu_poll_start()
poll_state_synchronize_rcu() -> synchronize_rcu_poll()
cond_synchronize_rcu() -> synchronize_rcu_cond()

But it's up to you really.

>  /**
> + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> + *
> + * Returns a cookie that is used by a later call to cond_synchronize_rcu()

It may be worth noting that calling start_poll_synchronize_rcu() and then
pass the cookie to cond_synchronize_rcu() soon after may end up waiting for
one more grace period.

> + * or poll_state_synchronize_rcu() to determine whether or not a full
> + * grace period has elapsed in the meantime.  If the needed grace period
> + * is not already slated to start, notifies RCU core of the need for that
> + * grace period.
> + *
> + * Interrupts must be enabled for the case where it is necessary to awaken
> + * the grace-period kthread.
> + */
> +unsigned long start_poll_synchronize_rcu(void)
> +{
> +	unsigned long flags;
> +	unsigned long gp_seq = get_state_synchronize_rcu();
> +	bool needwake;
> +	struct rcu_data *rdp;
> +	struct rcu_node *rnp;
[...]
> +
> +/**
> + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> + *
> + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> + *
> + * If a full RCU grace period has elapsed since the earlier call from
> + * which oldstate was obtained, return @true, otherwise return @false.
> + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.

Rephrase suggestion for the last sentence:

"In case of failure, it's up to the caller to try polling again later or
invoke synchronize_rcu() to wait for a new full grace period to complete."


In any case: Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Thanks!

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Fri, Mar 19, 2021 at 02:58:54PM +0100, Frederic Weisbecker wrote:
> On Wed, Mar 03, 2021 at 04:26:30PM -0800, paulmck@kernel.org wrote:
> > From: "Paul E. McKenney" <paulmck@kernel.org>
> > 
> > There is a need for a non-blocking polling interface for RCU grace
> > periods, so this commit supplies start_poll_synchronize_rcu() and
> > poll_state_synchronize_rcu() for this purpose.  Note that the existing
> > get_state_synchronize_rcu() may be used if future grace periods are
> > inevitable (perhaps due to a later call_rcu() invocation).  The new
> > start_poll_synchronize_rcu() is to be used if future grace periods
> > might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> > provides a lockless check for a grace period having elapsed since
> > the corresponding call to either of the get_state_synchronize_rcu()
> > or start_poll_synchronize_rcu().
> > 
> > As with get_state_synchronize_rcu(), the return value from either
> > get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> > to a later call to either poll_state_synchronize_rcu() or the existing
> > (might_sleep) cond_synchronize_rcu().
> 
> It's all a matter of personal taste but if I may suggest some namespace
> modifications:
> 
> get_state_synchronize_rcu() -> synchronize_rcu_poll_start_raw()
> start_poll_synchronize_rcu() -> synchronize_rcu_poll_start()
> poll_state_synchronize_rcu() -> synchronize_rcu_poll()
> cond_synchronize_rcu() -> synchronize_rcu_cond()
> 
> But it's up to you really.

I am concerned about starting anything "synchronize_rcu" if that
thing doesn't unconditionally wait for a grace period.  "What do
you mean that there was no grace period?  Don't you see that call to
synchronize_rcu_poll_start_raw()???"

This objection doesn't apply to cond_synchronize_rcu(), but it is
already in use, so any name change should be worked with the users.
All two of them.  ;-)

> >  /**
> > + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> > + *
> > + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> 
> It may be worth noting that calling start_poll_synchronize_rcu() and then
> pass the cookie to cond_synchronize_rcu() soon after may end up waiting for
> one more grace period.

You mean this sequence of events?

1.	cookie = start_poll_synchronize_rcu()

2.	The grace period corresponding to cookie is almost over...

3.	cond_synchronize_rcu() checks the cookie and sees that the
	grace period has not yet expired.

4.	The grace period corresponding to cookie completes.

5.	Someone else starts a grace period.

6.	cond_synchronize_rcu() invokes synchronize_rcu(), which waits
	for the just-started grace period plus another grace period.
	Thus, there has been no fewer than three full grace periods
	between the call to start_poll_synchronize_rcu() and the
	return from cond_synchronize_rcu().

Yes, this can happen!  And it can be worse, for example, it is quite
possible that cond_synchronize_rcu() would be preempted for multiple
grace periods at step 5, in which case it would still wait for almost
two additional grace periods.

Or are you thinking of something else?

> > + * or poll_state_synchronize_rcu() to determine whether or not a full
> > + * grace period has elapsed in the meantime.  If the needed grace period
> > + * is not already slated to start, notifies RCU core of the need for that
> > + * grace period.
> > + *
> > + * Interrupts must be enabled for the case where it is necessary to awaken
> > + * the grace-period kthread.
> > + */
> > +unsigned long start_poll_synchronize_rcu(void)
> > +{
> > +	unsigned long flags;
> > +	unsigned long gp_seq = get_state_synchronize_rcu();
> > +	bool needwake;
> > +	struct rcu_data *rdp;
> > +	struct rcu_node *rnp;
> [...]
> > +
> > +/**
> > + * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> > + *
> > + * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> > + *
> > + * If a full RCU grace period has elapsed since the earlier call from
> > + * which oldstate was obtained, return @true, otherwise return @false.
> > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> 
> Rephrase suggestion for the last sentence:
> 
> "In case of failure, it's up to the caller to try polling again later or
> invoke synchronize_rcu() to wait for a new full grace period to complete."

How about like this?

/**
 * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
 *
 * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
 *
 * If a full RCU grace period has elapsed since the earlier call from
 * which oldstate was obtained, return @true, otherwise return @false.
 * If @false is returned, it is the caller's responsibilty to invoke this
 * function later on until it does return @true.  Alternatively, the caller
 * can explicitly wait for a grace period, for example, by passing @oldstate
 * to cond_synchronize_rcu() or by directly invoking synchronize_rcu().
 *
 * Yes, this function does not take counter wrap into account.
 * But counter wrap is harmless.  If the counter wraps, we have waited for
 * more than 2 billion grace periods (and way more on a 64-bit system!).
 * Those needing to keep oldstate values for very long time periods
 * (many hours even on 32-bit systems) should check them occasionally
 * and either refresh them or set a flag indicating that the grace period
 * has completed.
 */

> In any case: Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Thank you, I will apply it at the next rebase.

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Fri, Mar 19, 2021 at 10:51:16AM -0700, Paul E. McKenney wrote:
> On Fri, Mar 19, 2021 at 02:58:54PM +0100, Frederic Weisbecker wrote:
> > It's all a matter of personal taste but if I may suggest some namespace
> > modifications:
> > 
> > get_state_synchronize_rcu() -> synchronize_rcu_poll_start_raw()
> > start_poll_synchronize_rcu() -> synchronize_rcu_poll_start()
> > poll_state_synchronize_rcu() -> synchronize_rcu_poll()
> > cond_synchronize_rcu() -> synchronize_rcu_cond()
> > 
> > But it's up to you really.
> 
> I am concerned about starting anything "synchronize_rcu" if that
> thing doesn't unconditionally wait for a grace period.  "What do
> you mean that there was no grace period?  Don't you see that call to
> synchronize_rcu_poll_start_raw()???"

I see, that could indeed be confusing.

> 
> This objection doesn't apply to cond_synchronize_rcu(), but it is
> already in use, so any name change should be worked with the users.
> All two of them.  ;-)

Probably not worth it. We have cond_resched() as a schedule() counterpart
for a reference after all.

> > >  /**
> > > + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> > > + *
> > > + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> > 
> > It may be worth noting that calling start_poll_synchronize_rcu() and then
> > pass the cookie to cond_synchronize_rcu() soon after may end up waiting for
> > one more grace period.
> 
> You mean this sequence of events?
> 
> 1.	cookie = start_poll_synchronize_rcu()
> 
> 2.	The grace period corresponding to cookie is almost over...
> 
> 3.	cond_synchronize_rcu() checks the cookie and sees that the
> 	grace period has not yet expired.
> 
> 4.	The grace period corresponding to cookie completes.
> 
> 5.	Someone else starts a grace period.
> 
> 6.	cond_synchronize_rcu() invokes synchronize_rcu(), which waits
> 	for the just-started grace period plus another grace period.
> 	Thus, there has been no fewer than three full grace periods
> 	between the call to start_poll_synchronize_rcu() and the
> 	return from cond_synchronize_rcu().
> 
> Yes, this can happen!  And it can be worse, for example, it is quite
> possible that cond_synchronize_rcu() would be preempted for multiple
> grace periods at step 5, in which case it would still wait for almost
> two additional grace periods.
> 
> Or are you thinking of something else?

I didn't even think that far.
My scenario was:

1.	cookie = start_poll_synchronize_rcu()
 
 
2.	cond_synchronize_rcu() checks the cookie and sees that the
	grace period has not yet expired. So it calls synchronize_rcu()
	which queues a callback.

3.	The grace period for the cookie eventually completes.

4.	The callback queued in 2. gets assigned a new grace period number.
	That new grace period starts.

5.	The new grace period completes and synchronize_rcu() returns.


But I think this is due to some deep misunderstanding from my end.


> > > + * If a full RCU grace period has elapsed since the earlier call from
> > > + * which oldstate was obtained, return @true, otherwise return @false.
> > > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > 
> > Rephrase suggestion for the last sentence:
> > 
> > "In case of failure, it's up to the caller to try polling again later or
> > invoke synchronize_rcu() to wait for a new full grace period to complete."
> 
> How about like this?
> 
> /**
>  * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
>  *
>  * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
>  *
>  * If a full RCU grace period has elapsed since the earlier call from
>  * which oldstate was obtained, return @true, otherwise return @false.
>  * If @false is returned, it is the caller's responsibilty to invoke this
>  * function later on until it does return @true.  Alternatively, the caller
>  * can explicitly wait for a grace period, for example, by passing @oldstate
>  * to cond_synchronize_rcu() or by directly invoking synchronize_rcu().

Yes very nice!

Thanks!

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Paul E. McKenney]

On Fri, Mar 19, 2021 at 11:10:40PM +0100, Frederic Weisbecker wrote:
> On Fri, Mar 19, 2021 at 10:51:16AM -0700, Paul E. McKenney wrote:
> > On Fri, Mar 19, 2021 at 02:58:54PM +0100, Frederic Weisbecker wrote:
> > > It's all a matter of personal taste but if I may suggest some namespace
> > > modifications:
> > > 
> > > get_state_synchronize_rcu() -> synchronize_rcu_poll_start_raw()
> > > start_poll_synchronize_rcu() -> synchronize_rcu_poll_start()
> > > poll_state_synchronize_rcu() -> synchronize_rcu_poll()
> > > cond_synchronize_rcu() -> synchronize_rcu_cond()
> > > 
> > > But it's up to you really.
> > 
> > I am concerned about starting anything "synchronize_rcu" if that
> > thing doesn't unconditionally wait for a grace period.  "What do
> > you mean that there was no grace period?  Don't you see that call to
> > synchronize_rcu_poll_start_raw()???"
> 
> I see, that could indeed be confusing.
> 
> > This objection doesn't apply to cond_synchronize_rcu(), but it is
> > already in use, so any name change should be worked with the users.
> > All two of them.  ;-)
> 
> Probably not worth it. We have cond_resched() as a schedule() counterpart
> for a reference after all.

Good point!

> > > >  /**
> > > > + * start_poll_state_synchronize_rcu - Snapshot and start RCU grace period
> > > > + *
> > > > + * Returns a cookie that is used by a later call to cond_synchronize_rcu()
> > > 
> > > It may be worth noting that calling start_poll_synchronize_rcu() and then
> > > pass the cookie to cond_synchronize_rcu() soon after may end up waiting for
> > > one more grace period.
> > 
> > You mean this sequence of events?
> > 
> > 1.	cookie = start_poll_synchronize_rcu()
> > 
> > 2.	The grace period corresponding to cookie is almost over...
> > 
> > 3.	cond_synchronize_rcu() checks the cookie and sees that the
> > 	grace period has not yet expired.
> > 
> > 4.	The grace period corresponding to cookie completes.
> > 
> > 5.	Someone else starts a grace period.
> > 
> > 6.	cond_synchronize_rcu() invokes synchronize_rcu(), which waits
> > 	for the just-started grace period plus another grace period.
> > 	Thus, there has been no fewer than three full grace periods
> > 	between the call to start_poll_synchronize_rcu() and the
> > 	return from cond_synchronize_rcu().
> > 
> > Yes, this can happen!  And it can be worse, for example, it is quite
> > possible that cond_synchronize_rcu() would be preempted for multiple
> > grace periods at step 5, in which case it would still wait for almost
> > two additional grace periods.
> > 
> > Or are you thinking of something else?
> 
> I didn't even think that far.
> My scenario was:
> 
> 1.	cookie = start_poll_synchronize_rcu()
>  
>  
> 2.	cond_synchronize_rcu() checks the cookie and sees that the
> 	grace period has not yet expired. So it calls synchronize_rcu()
> 	which queues a callback.
> 
> 3.	The grace period for the cookie eventually completes.
> 
> 4.	The callback queued in 2. gets assigned a new grace period number.
> 	That new grace period starts.
> 
> 5.	The new grace period completes and synchronize_rcu() returns.
> 
> 
> But I think this is due to some deep misunderstanding from my end.

You mean like this?

	oldstate = start_poll_synchronize_rcu();
	// Why wait?  Beat the rush!!!
	cond_synchronize_rcu(oldstate);

This would be a bit silly (why not just call synchronize_rcu()?),
and yes, this would unconditionally get you an extra RCU grace period.
Then again, any call to cond_synchronize_rcu() before the desired grace
period has expired will get you an extra grace period, and maybe more.

So a given use case either needs to not care about the added latency
or have a high probability of invoking cond_synchronize_rcu() after
the desired grace period has expired.

> > > > + * If a full RCU grace period has elapsed since the earlier call from
> > > > + * which oldstate was obtained, return @true, otherwise return @false.
> > > > + * Otherwise, invoke synchronize_rcu() to wait for a full grace period.
> > > 
> > > Rephrase suggestion for the last sentence:
> > > 
> > > "In case of failure, it's up to the caller to try polling again later or
> > > invoke synchronize_rcu() to wait for a new full grace period to complete."
> > 
> > How about like this?
> > 
> > /**
> >  * poll_state_synchronize_rcu - Conditionally wait for an RCU grace period
> >  *
> >  * @oldstate: return from call to get_state_synchronize_rcu() or start_poll_synchronize_rcu()
> >  *
> >  * If a full RCU grace period has elapsed since the earlier call from
> >  * which oldstate was obtained, return @true, otherwise return @false.
> >  * If @false is returned, it is the caller's responsibilty to invoke this
> >  * function later on until it does return @true.  Alternatively, the caller
> >  * can explicitly wait for a grace period, for example, by passing @oldstate
> >  * to cond_synchronize_rcu() or by directly invoking synchronize_rcu().
> 
> Yes very nice!

You got it!

							Thanx, Paul

Re: [PATCH tip/core/rcu 1/3] rcu: Provide polling interfaces for Tree RCU grace periods

[Frederic Weisbecker]

On Fri, Mar 19, 2021 at 04:38:48PM -0700, Paul E. McKenney wrote:
> > I didn't even think that far.
> > My scenario was:
> > 
> > 1.	cookie = start_poll_synchronize_rcu()
> >  
> >  
> > 2.	cond_synchronize_rcu() checks the cookie and sees that the
> > 	grace period has not yet expired. So it calls synchronize_rcu()
> > 	which queues a callback.
> > 
> > 3.	The grace period for the cookie eventually completes.
> > 
> > 4.	The callback queued in 2. gets assigned a new grace period number.
> > 	That new grace period starts.
> > 
> > 5.	The new grace period completes and synchronize_rcu() returns.
> > 
> > 
> > But I think this is due to some deep misunderstanding from my end.
> 
> You mean like this?
> 
> 	oldstate = start_poll_synchronize_rcu();
> 	// Why wait?  Beat the rush!!!
> 	cond_synchronize_rcu(oldstate);
> 
> This would be a bit silly (why not just call synchronize_rcu()?),
> and yes, this would unconditionally get you an extra RCU grace period.
> Then again, any call to cond_synchronize_rcu() before the desired grace
> period has expired will get you an extra grace period, and maybe more.
> 
> So a given use case either needs to not care about the added latency
> or have a high probability of invoking cond_synchronize_rcu() after
> the desired grace period has expired.

Fair point!

Thanks.

[PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[paulmck]

From: "Paul E. McKenney" <paulmck@kernel.org>

There is a need for a non-blocking polling interface for RCU grace
periods, so this commit supplies start_poll_synchronize_rcu() and
poll_state_synchronize_rcu() for this purpose.  Note that the existing
get_state_synchronize_rcu() may be used if future grace periods are
inevitable (perhaps due to a later call_rcu() invocation).  The new
start_poll_synchronize_rcu() is to be used if future grace periods
might not otherwise happen.  Finally, poll_state_synchronize_rcu()
provides a lockless check for a grace period having elapsed since
the corresponding call to either of the get_state_synchronize_rcu()
or start_poll_synchronize_rcu().

As with get_state_synchronize_rcu(), the return value from either
get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
to a later call to either poll_state_synchronize_rcu() or the existing
(might_sleep) cond_synchronize_rcu().

Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 include/linux/rcutiny.h | 11 ++++++-----
 kernel/rcu/tiny.c       | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 46 insertions(+), 5 deletions(-)

diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
index 2a97334..69108cf4 100644
--- a/include/linux/rcutiny.h
+++ b/include/linux/rcutiny.h
@@ -17,14 +17,15 @@
 /* Never flag non-existent other CPUs! */
 static inline bool rcu_eqs_special_set(int cpu) { return false; }
 
-static inline unsigned long get_state_synchronize_rcu(void)
-{
-	return 0;
-}
+unsigned long get_state_synchronize_rcu(void);
+unsigned long start_poll_synchronize_rcu(void);
+bool poll_state_synchronize_rcu(unsigned long oldstate);
 
 static inline void cond_synchronize_rcu(unsigned long oldstate)
 {
-	might_sleep();
+	if (poll_state_synchronize_rcu(oldstate))
+		return;
+	synchronize_rcu();
 }
 
 extern void rcu_barrier(void);
diff --git a/kernel/rcu/tiny.c b/kernel/rcu/tiny.c
index aa897c3..c8a029f 100644
--- a/kernel/rcu/tiny.c
+++ b/kernel/rcu/tiny.c
@@ -32,12 +32,14 @@ struct rcu_ctrlblk {
 	struct rcu_head *rcucblist;	/* List of pending callbacks (CBs). */
 	struct rcu_head **donetail;	/* ->next pointer of last "done" CB. */
 	struct rcu_head **curtail;	/* ->next pointer of last CB. */
+	unsigned long gp_seq;		/* Grace-period counter. */
 };
 
 /* Definition for rcupdate control block. */
 static struct rcu_ctrlblk rcu_ctrlblk = {
 	.donetail	= &rcu_ctrlblk.rcucblist,
 	.curtail	= &rcu_ctrlblk.rcucblist,
+	.gp_seq		= 0 - 300UL,
 };
 
 void rcu_barrier(void)
@@ -56,6 +58,7 @@ void rcu_qs(void)
 		rcu_ctrlblk.donetail = rcu_ctrlblk.curtail;
 		raise_softirq_irqoff(RCU_SOFTIRQ);
 	}
+	WRITE_ONCE(rcu_ctrlblk.gp_seq, rcu_ctrlblk.gp_seq + 1);
 	local_irq_restore(flags);
 }
 
@@ -177,6 +180,43 @@ void call_rcu(struct rcu_head *head, rcu_callback_t func)
 }
 EXPORT_SYMBOL_GPL(call_rcu);
 
+/*
+ * Return a grace-period-counter "cookie".  For more information,
+ * see the Tree RCU header comment.
+ */
+unsigned long get_state_synchronize_rcu(void)
+{
+	return READ_ONCE(rcu_ctrlblk.gp_seq);
+}
+EXPORT_SYMBOL_GPL(get_state_synchronize_rcu);
+
+/*
+ * Return a grace-period-counter "cookie" and ensure that a future grace
+ * period completes.  For more information, see the Tree RCU header comment.
+ */
+unsigned long start_poll_synchronize_rcu(void)
+{
+	unsigned long gp_seq = get_state_synchronize_rcu();
+
+	if (unlikely(is_idle_task(current))) {
+		/* force scheduling for rcu_qs() */
+		resched_cpu(0);
+	}
+	return gp_seq;
+}
+EXPORT_SYMBOL_GPL(start_poll_synchronize_rcu);
+
+/*
+ * Return true if the grace period corresponding to oldstate has completed
+ * and false otherwise.  For more information, see the Tree RCU header
+ * comment.
+ */
+bool poll_state_synchronize_rcu(unsigned long oldstate)
+{
+	return READ_ONCE(rcu_ctrlblk.gp_seq) != oldstate;
+}
+EXPORT_SYMBOL_GPL(poll_state_synchronize_rcu);
+
 void __init rcu_init(void)
 {
 	open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
-- 
2.9.5

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Frederic Weisbecker]

On Wed, Mar 03, 2021 at 04:26:31PM -0800, paulmck@kernel.org wrote:
> From: "Paul E. McKenney" <paulmck@kernel.org>
> 
> There is a need for a non-blocking polling interface for RCU grace
> periods, so this commit supplies start_poll_synchronize_rcu() and
> poll_state_synchronize_rcu() for this purpose.  Note that the existing
> get_state_synchronize_rcu() may be used if future grace periods are
> inevitable (perhaps due to a later call_rcu() invocation).  The new
> start_poll_synchronize_rcu() is to be used if future grace periods
> might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> provides a lockless check for a grace period having elapsed since
> the corresponding call to either of the get_state_synchronize_rcu()
> or start_poll_synchronize_rcu().
> 
> As with get_state_synchronize_rcu(), the return value from either
> get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> to a later call to either poll_state_synchronize_rcu() or the existing
> (might_sleep) cond_synchronize_rcu().
> 
> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> ---
>  include/linux/rcutiny.h | 11 ++++++-----
>  kernel/rcu/tiny.c       | 40 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 46 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
> index 2a97334..69108cf4 100644
> --- a/include/linux/rcutiny.h
> +++ b/include/linux/rcutiny.h
> @@ -17,14 +17,15 @@
>  /* Never flag non-existent other CPUs! */
>  static inline bool rcu_eqs_special_set(int cpu) { return false; }
>  
> -static inline unsigned long get_state_synchronize_rcu(void)
> -{
> -	return 0;
> -}
> +unsigned long get_state_synchronize_rcu(void);
> +unsigned long start_poll_synchronize_rcu(void);
> +bool poll_state_synchronize_rcu(unsigned long oldstate);
>  
>  static inline void cond_synchronize_rcu(unsigned long oldstate)
>  {
> -	might_sleep();
> +	if (poll_state_synchronize_rcu(oldstate))
> +		return;
> +	synchronize_rcu();

Perhaps cond_synchronize_rcu() could stay as it was. If it might
call synchronize_rcu() then it inherits its constraint to be
called from a quiescent state.

Thanks.

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Paul E. McKenney]

On Sun, Mar 21, 2021 at 11:28:55PM +0100, Frederic Weisbecker wrote:
> On Wed, Mar 03, 2021 at 04:26:31PM -0800, paulmck@kernel.org wrote:
> > From: "Paul E. McKenney" <paulmck@kernel.org>
> > 
> > There is a need for a non-blocking polling interface for RCU grace
> > periods, so this commit supplies start_poll_synchronize_rcu() and
> > poll_state_synchronize_rcu() for this purpose.  Note that the existing
> > get_state_synchronize_rcu() may be used if future grace periods are
> > inevitable (perhaps due to a later call_rcu() invocation).  The new
> > start_poll_synchronize_rcu() is to be used if future grace periods
> > might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> > provides a lockless check for a grace period having elapsed since
> > the corresponding call to either of the get_state_synchronize_rcu()
> > or start_poll_synchronize_rcu().
> > 
> > As with get_state_synchronize_rcu(), the return value from either
> > get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> > to a later call to either poll_state_synchronize_rcu() or the existing
> > (might_sleep) cond_synchronize_rcu().
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > ---
> >  include/linux/rcutiny.h | 11 ++++++-----
> >  kernel/rcu/tiny.c       | 40 ++++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 46 insertions(+), 5 deletions(-)
> > 
> > diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
> > index 2a97334..69108cf4 100644
> > --- a/include/linux/rcutiny.h
> > +++ b/include/linux/rcutiny.h
> > @@ -17,14 +17,15 @@
> >  /* Never flag non-existent other CPUs! */
> >  static inline bool rcu_eqs_special_set(int cpu) { return false; }
> >  
> > -static inline unsigned long get_state_synchronize_rcu(void)
> > -{
> > -	return 0;
> > -}
> > +unsigned long get_state_synchronize_rcu(void);
> > +unsigned long start_poll_synchronize_rcu(void);
> > +bool poll_state_synchronize_rcu(unsigned long oldstate);
> >  
> >  static inline void cond_synchronize_rcu(unsigned long oldstate)
> >  {
> > -	might_sleep();
> > +	if (poll_state_synchronize_rcu(oldstate))
> > +		return;
> > +	synchronize_rcu();
> 
> Perhaps cond_synchronize_rcu() could stay as it was. If it might
> call synchronize_rcu() then it inherits its constraint to be
> called from a quiescent state.

As in leave the might_sleep()?  How about something like this?

static inline void cond_synchronize_rcu(unsigned long oldstate)
{
	if (!poll_state_synchronize_rcu(oldstate))
		synchronize_rcu();
	else
		might_sleep();
}

One advantage of this is that the Tiny and Tree implementations
become identical and can then be consolidated.

Or did I miss your point?

						Thanx, Paul

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Frederic Weisbecker]

On Mon, Mar 22, 2021 at 08:47:44AM -0700, Paul E. McKenney wrote:
> On Sun, Mar 21, 2021 at 11:28:55PM +0100, Frederic Weisbecker wrote:
> > On Wed, Mar 03, 2021 at 04:26:31PM -0800, paulmck@kernel.org wrote:
> > > From: "Paul E. McKenney" <paulmck@kernel.org>
> > > 
> > > There is a need for a non-blocking polling interface for RCU grace
> > > periods, so this commit supplies start_poll_synchronize_rcu() and
> > > poll_state_synchronize_rcu() for this purpose.  Note that the existing
> > > get_state_synchronize_rcu() may be used if future grace periods are
> > > inevitable (perhaps due to a later call_rcu() invocation).  The new
> > > start_poll_synchronize_rcu() is to be used if future grace periods
> > > might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> > > provides a lockless check for a grace period having elapsed since
> > > the corresponding call to either of the get_state_synchronize_rcu()
> > > or start_poll_synchronize_rcu().
> > > 
> > > As with get_state_synchronize_rcu(), the return value from either
> > > get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> > > to a later call to either poll_state_synchronize_rcu() or the existing
> > > (might_sleep) cond_synchronize_rcu().
> > > 
> > > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > > ---
> > >  include/linux/rcutiny.h | 11 ++++++-----
> > >  kernel/rcu/tiny.c       | 40 ++++++++++++++++++++++++++++++++++++++++
> > >  2 files changed, 46 insertions(+), 5 deletions(-)
> > > 
> > > diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
> > > index 2a97334..69108cf4 100644
> > > --- a/include/linux/rcutiny.h
> > > +++ b/include/linux/rcutiny.h
> > > @@ -17,14 +17,15 @@
> > >  /* Never flag non-existent other CPUs! */
> > >  static inline bool rcu_eqs_special_set(int cpu) { return false; }
> > >  
> > > -static inline unsigned long get_state_synchronize_rcu(void)
> > > -{
> > > -	return 0;
> > > -}
> > > +unsigned long get_state_synchronize_rcu(void);
> > > +unsigned long start_poll_synchronize_rcu(void);
> > > +bool poll_state_synchronize_rcu(unsigned long oldstate);
> > >  
> > >  static inline void cond_synchronize_rcu(unsigned long oldstate)
> > >  {
> > > -	might_sleep();
> > > +	if (poll_state_synchronize_rcu(oldstate))
> > > +		return;
> > > +	synchronize_rcu();
> > 
> > Perhaps cond_synchronize_rcu() could stay as it was. If it might
> > call synchronize_rcu() then it inherits its constraint to be
> > called from a quiescent state.
> 
> As in leave the might_sleep()?  How about something like this?
> 
> static inline void cond_synchronize_rcu(unsigned long oldstate)
> {
> 	if (!poll_state_synchronize_rcu(oldstate))
> 		synchronize_rcu();
> 	else
> 		might_sleep();
> }
> 
> One advantage of this is that the Tiny and Tree implementations
> become identical and can then be consolidated.
> 
> Or did I miss your point?

But poll_state_synchronize_rcu() checks that the gp_num has changed,
which is not needed for cond_synchronize_rcu() since this it is
only allowed to be called from a QS.

> 
> 						Thanx, Paul

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Paul E. McKenney]

On Mon, Mar 22, 2021 at 08:00:35PM +0100, Frederic Weisbecker wrote:
> On Mon, Mar 22, 2021 at 08:47:44AM -0700, Paul E. McKenney wrote:
> > On Sun, Mar 21, 2021 at 11:28:55PM +0100, Frederic Weisbecker wrote:
> > > On Wed, Mar 03, 2021 at 04:26:31PM -0800, paulmck@kernel.org wrote:
> > > > From: "Paul E. McKenney" <paulmck@kernel.org>
> > > > 
> > > > There is a need for a non-blocking polling interface for RCU grace
> > > > periods, so this commit supplies start_poll_synchronize_rcu() and
> > > > poll_state_synchronize_rcu() for this purpose.  Note that the existing
> > > > get_state_synchronize_rcu() may be used if future grace periods are
> > > > inevitable (perhaps due to a later call_rcu() invocation).  The new
> > > > start_poll_synchronize_rcu() is to be used if future grace periods
> > > > might not otherwise happen.  Finally, poll_state_synchronize_rcu()
> > > > provides a lockless check for a grace period having elapsed since
> > > > the corresponding call to either of the get_state_synchronize_rcu()
> > > > or start_poll_synchronize_rcu().
> > > > 
> > > > As with get_state_synchronize_rcu(), the return value from either
> > > > get_state_synchronize_rcu() or start_poll_synchronize_rcu() is passed in
> > > > to a later call to either poll_state_synchronize_rcu() or the existing
> > > > (might_sleep) cond_synchronize_rcu().
> > > > 
> > > > Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> > > > ---
> > > >  include/linux/rcutiny.h | 11 ++++++-----
> > > >  kernel/rcu/tiny.c       | 40 ++++++++++++++++++++++++++++++++++++++++
> > > >  2 files changed, 46 insertions(+), 5 deletions(-)
> > > > 
> > > > diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
> > > > index 2a97334..69108cf4 100644
> > > > --- a/include/linux/rcutiny.h
> > > > +++ b/include/linux/rcutiny.h
> > > > @@ -17,14 +17,15 @@
> > > >  /* Never flag non-existent other CPUs! */
> > > >  static inline bool rcu_eqs_special_set(int cpu) { return false; }
> > > >  
> > > > -static inline unsigned long get_state_synchronize_rcu(void)
> > > > -{
> > > > -	return 0;
> > > > -}
> > > > +unsigned long get_state_synchronize_rcu(void);
> > > > +unsigned long start_poll_synchronize_rcu(void);
> > > > +bool poll_state_synchronize_rcu(unsigned long oldstate);
> > > >  
> > > >  static inline void cond_synchronize_rcu(unsigned long oldstate)
> > > >  {
> > > > -	might_sleep();
> > > > +	if (poll_state_synchronize_rcu(oldstate))
> > > > +		return;
> > > > +	synchronize_rcu();
> > > 
> > > Perhaps cond_synchronize_rcu() could stay as it was. If it might
> > > call synchronize_rcu() then it inherits its constraint to be
> > > called from a quiescent state.
> > 
> > As in leave the might_sleep()?  How about something like this?
> > 
> > static inline void cond_synchronize_rcu(unsigned long oldstate)
> > {
> > 	if (!poll_state_synchronize_rcu(oldstate))
> > 		synchronize_rcu();
> > 	else
> > 		might_sleep();
> > }
> > 
> > One advantage of this is that the Tiny and Tree implementations
> > become identical and can then be consolidated.
> > 
> > Or did I miss your point?
> 
> But poll_state_synchronize_rcu() checks that the gp_num has changed,
> which is not needed for cond_synchronize_rcu() since this it is
> only allowed to be called from a QS.

Good catch, and thank you!  Back to a single might_sleep() it is!

						Thanx, Paul

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Frederic Weisbecker]

On Mon, Mar 22, 2021 at 12:45:22PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 22, 2021 at 08:00:35PM +0100, Frederic Weisbecker wrote:
> > But poll_state_synchronize_rcu() checks that the gp_num has changed,
> > which is not needed for cond_synchronize_rcu() since this it is
> > only allowed to be called from a QS.
> 
> Good catch, and thank you!  Back to a single might_sleep() it is!

And then: Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Thanks!

Re: [PATCH tip/core/rcu 2/3] rcu: Provide polling interfaces for Tiny RCU grace periods

[Paul E. McKenney]

On Tue, Mar 23, 2021 at 03:02:07PM +0100, Frederic Weisbecker wrote:
> On Mon, Mar 22, 2021 at 12:45:22PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 22, 2021 at 08:00:35PM +0100, Frederic Weisbecker wrote:
> > > But poll_state_synchronize_rcu() checks that the gp_num has changed,
> > > which is not needed for cond_synchronize_rcu() since this it is
> > > only allowed to be called from a QS.
> > 
> > Good catch, and thank you!  Back to a single might_sleep() it is!
> 
> And then: Reviewed-by: Frederic Weisbecker <frederic@kernel.org>

Thank you!  I will apply this on my next rebase.

							Thanx, Paul

[PATCH tip/core/rcu 3/3] rcutorture: Test start_poll_synchronize_rcu() and poll_state_synchronize_rcu()

[paulmck]

From: "Paul E. McKenney" <paulmck@kernel.org>

This commit causes rcutorture to test the new start_poll_synchronize_rcu()
and poll_state_synchronize_rcu() functions.  Because of the difficulty of
determining the nature of a synchronous RCU grace (expedited or not),
the test that insisted that poll_state_synchronize_rcu() detect an
intervening synchronize_rcu() had to be dropped.

Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 kernel/rcu/rcutorture.c | 12 +++---------
 1 file changed, 3 insertions(+), 9 deletions(-)

diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c
index 99657ff..956e6bf 100644
--- a/kernel/rcu/rcutorture.c
+++ b/kernel/rcu/rcutorture.c
@@ -494,6 +494,8 @@ static struct rcu_torture_ops rcu_ops = {
 	.sync		= synchronize_rcu,
 	.exp_sync	= synchronize_rcu_expedited,
 	.get_gp_state	= get_state_synchronize_rcu,
+	.start_gp_poll	= start_poll_synchronize_rcu,
+	.poll_gp_state	= poll_state_synchronize_rcu,
 	.cond_sync	= cond_synchronize_rcu,
 	.call		= call_rcu,
 	.cb_barrier	= rcu_barrier,
@@ -1223,14 +1225,6 @@ rcu_torture_writer(void *arg)
 				WARN_ON_ONCE(1);
 				break;
 			}
-			if (cur_ops->get_gp_state && cur_ops->poll_gp_state)
-				WARN_ONCE(rcu_torture_writer_state != RTWS_DEF_FREE &&
-					  !cur_ops->poll_gp_state(cookie),
-					  "%s: Cookie check 2 failed %s(%d) %lu->%lu\n",
-					  __func__,
-					  rcu_torture_writer_state_getname(),
-					  rcu_torture_writer_state,
-					  cookie, cur_ops->get_gp_state());
 		}
 		WRITE_ONCE(rcu_torture_current_version,
 			   rcu_torture_current_version + 1);
@@ -1589,7 +1583,7 @@ static bool rcu_torture_one_read(struct torture_random_state *trsp, long myid)
 	preempt_enable();
 	if (cur_ops->get_gp_state && cur_ops->poll_gp_state)
 		WARN_ONCE(cur_ops->poll_gp_state(cookie),
-			  "%s: Cookie check 3 failed %s(%d) %lu->%lu\n",
+			  "%s: Cookie check 2 failed %s(%d) %lu->%lu\n",
 			  __func__,
 			  rcu_torture_writer_state_getname(),
 			  rcu_torture_writer_state,
-- 
2.9.5