[PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Paul E. McKenney]

Hello!

In the process of writing up the mechanical proof of correctness for the
dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
in rcu_enter_nohz() and rcu_exit_nohz().  This patch puts them in the
right place and adds a comment.  The key thing to keep in mind is that
rcu_enter_nohz() is -exiting- the mode that can legally execute RCU
read-side critical sections.  The memory barrier must be between any
potential RCU read-side critical sections and the increment of the per-CPU
dynticks_progress_counter, and thus must come -before- this increment.
And vice versa for rcu_exit_nohz().

The locking in the scheduler is probably saving us for the moment.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---

 rcupreempt.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff -urpNa -X dontdiff linux-2.6.25-rc6/include/linux/rcupreempt.h linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h
--- linux-2.6.25-rc6/include/linux/rcupreempt.h	2008-03-16 17:45:16.000000000 -0700
+++ linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h	2008-03-16 17:59:24.000000000 -0700
@@ -87,15 +87,15 @@ DECLARE_PER_CPU(long, dynticks_progress_
 
 static inline void rcu_enter_nohz(void)
 {
+	mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
 	__get_cpu_var(dynticks_progress_counter)++;
 	WARN_ON(__get_cpu_var(dynticks_progress_counter) & 0x1);
-	mb();
 }
 
 static inline void rcu_exit_nohz(void)
 {
-	mb();
 	__get_cpu_var(dynticks_progress_counter)++;
+	mb(); /* CPUs seeing ++ must see subsequent RCU read-side crit sects */
 	WARN_ON(!(__get_cpu_var(dynticks_progress_counter) & 0x1));
 }
 

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Nick Piggin]

On Monday 17 March 2008 12:08, Paul E. McKenney wrote:
> Hello!
>
> In the process of writing up the mechanical proof of correctness for the
> dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
> in rcu_enter_nohz() and rcu_exit_nohz().  This patch puts them in the
> right place and adds a comment.  The key thing to keep in mind is that
> rcu_enter_nohz() is -exiting- the mode that can legally execute RCU
> read-side critical sections.  The memory barrier must be between any
> potential RCU read-side critical sections and the increment of the per-CPU
> dynticks_progress_counter, and thus must come -before- this increment.
> And vice versa for rcu_exit_nohz().
>
> The locking in the scheduler is probably saving us for the moment.
>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>
>  rcupreempt.h |    4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff -urpNa -X dontdiff linux-2.6.25-rc6/include/linux/rcupreempt.h
> linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h ---
> linux-2.6.25-rc6/include/linux/rcupreempt.h	2008-03-16 17:45:16.000000000
> -0700 +++
> linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h	2008-03-16
> 17:59:24.000000000 -0700 @@ -87,15 +87,15 @@ DECLARE_PER_CPU(long,
> dynticks_progress_
>
>  static inline void rcu_enter_nohz(void)
>  {
> +	mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
>  	__get_cpu_var(dynticks_progress_counter)++;
>  	WARN_ON(__get_cpu_var(dynticks_progress_counter) & 0x1);
> -	mb();
>  }
>
>  static inline void rcu_exit_nohz(void)
>  {
> -	mb();
>  	__get_cpu_var(dynticks_progress_counter)++;
> +	mb(); /* CPUs seeing ++ must see subsequent RCU read-side crit sects */
>  	WARN_ON(!(__get_cpu_var(dynticks_progress_counter) & 0x1));
>  }

Can you make these smp_mb() as well?

Thanks,
Nick

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Paul E. McKenney]

On Mon, Mar 17, 2008 at 02:09:06PM +1100, Nick Piggin wrote:
> On Monday 17 March 2008 12:08, Paul E. McKenney wrote:
> > Hello!
> >
> > In the process of writing up the mechanical proof of correctness for the
> > dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
> > in rcu_enter_nohz() and rcu_exit_nohz().  This patch puts them in the
> > right place and adds a comment.  The key thing to keep in mind is that
> > rcu_enter_nohz() is -exiting- the mode that can legally execute RCU
> > read-side critical sections.  The memory barrier must be between any
> > potential RCU read-side critical sections and the increment of the per-CPU
> > dynticks_progress_counter, and thus must come -before- this increment.
> > And vice versa for rcu_exit_nohz().
> >
> > The locking in the scheduler is probably saving us for the moment.
> >
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > ---
> >
> >  rcupreempt.h |    4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> >
> > diff -urpNa -X dontdiff linux-2.6.25-rc6/include/linux/rcupreempt.h
> > linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h ---
> > linux-2.6.25-rc6/include/linux/rcupreempt.h	2008-03-16 17:45:16.000000000
> > -0700 +++
> > linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h	2008-03-16
> > 17:59:24.000000000 -0700 @@ -87,15 +87,15 @@ DECLARE_PER_CPU(long,
> > dynticks_progress_
> >
> >  static inline void rcu_enter_nohz(void)
> >  {
> > +	mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
> >  	__get_cpu_var(dynticks_progress_counter)++;
> >  	WARN_ON(__get_cpu_var(dynticks_progress_counter) & 0x1);
> > -	mb();
> >  }
> >
> >  static inline void rcu_exit_nohz(void)
> >  {
> > -	mb();
> >  	__get_cpu_var(dynticks_progress_counter)++;
> > +	mb(); /* CPUs seeing ++ must see subsequent RCU read-side crit sects */
> >  	WARN_ON(!(__get_cpu_var(dynticks_progress_counter) & 0x1));
> >  }
> 
> Can you make these smp_mb() as well?

Can't see why not, now that you mention it.  Steve, anything Nick and
I are missing here?  (See updated patch below.)

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---

 rcupreempt.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff -urpNa -X dontdiff linux-2.6.25-rc6/include/linux/rcupreempt.h linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h
--- linux-2.6.25-rc6/include/linux/rcupreempt.h	2008-03-16 17:45:16.000000000 -0700
+++ linux-2.6.25-rc6-rcu_nohz-fix/include/linux/rcupreempt.h	2008-03-16 22:53:07.000000000 -0700
@@ -87,15 +87,15 @@ DECLARE_PER_CPU(long, dynticks_progress_
 
 static inline void rcu_enter_nohz(void)
 {
+	smp_mb(); /* CPUs seeing ++ must see prior RCU read-side crit sects */
 	__get_cpu_var(dynticks_progress_counter)++;
 	WARN_ON(__get_cpu_var(dynticks_progress_counter) & 0x1);
-	mb();
 }
 
 static inline void rcu_exit_nohz(void)
 {
-	mb();
 	__get_cpu_var(dynticks_progress_counter)++;
+	smp_mb(); /* CPUs seeing ++ must see later RCU read-side crit sects */
 	WARN_ON(!(__get_cpu_var(dynticks_progress_counter) & 0x1));
 }
 

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Steven Rostedt]

On Sun, 16 Mar 2008, Paul E. McKenney wrote:
> >
> > Can you make these smp_mb() as well?
>
> Can't see why not, now that you mention it.  Steve, anything Nick and
> I are missing here?  (See updated patch below.)

Not that I can see.

Acked-by: Steven Rostedt <srostedt@redhat.com>
>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

-- Steve

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Oleg Nesterov]

On 03/16, Paul E. McKenney wrote:
> 
> In the process of writing up the mechanical proof of correctness for the
> dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
> in rcu_enter_nohz() and rcu_exit_nohz().

Can't comment this patch, there is no rcu_enter_nohz() in my rcupreempt.h ;)

I'm not sure the code below is up to date, but what I have in
arch/s390/kernel/time.c is:

	stop_hz_timer:

		cpu_set(cpu, nohz_cpu_mask);
		
		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
			cpu_clear(cpu, nohz_cpu_mask);
			return;
		}

Don't we need smp_mb() after cpu_set() ?

Oleg.

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Paul E. McKenney]

On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> On 03/16, Paul E. McKenney wrote:
> > 
> > In the process of writing up the mechanical proof of correctness for the
> > dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
> > in rcu_enter_nohz() and rcu_exit_nohz().
> 
> Can't comment this patch, there is no rcu_enter_nohz() in my rcupreempt.h ;)

It is in 2.6.25-rc4 and later.  ;-)

> I'm not sure the code below is up to date, but what I have in
> arch/s390/kernel/time.c is:
> 
> 	stop_hz_timer:
> 
> 		cpu_set(cpu, nohz_cpu_mask);
> 		
> 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> 			cpu_clear(cpu, nohz_cpu_mask);
> 			return;
> 		}
> 
> Don't we need smp_mb() after cpu_set() ?

S390's memory model is quite strong, so it might not be needed.  In any
case, if needed, it goes -before- the cpu_set(), because the problems
would arise if prior RCU read-side critical sections were to be reordered
to follow this cpu_set(), right?

Let's see...  In S390, a store cannot be reordered to precede any prior
load or store, so any preceding RCU read-side critical section would be
seen by all CPUs as preceding the shift to nohz mode.  Might be trouble
for the opposite transition...

But last I heard, the s390 guys were thinking in terms of moving to the
generic dynticks model.  If they really are doing so, then the above
code goes away in any case.

							Thanx, Paul

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Oleg Nesterov]

(to clarify: my question is completely offtopic to this patch)

On 03/17, Paul E. McKenney wrote:
>
> On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> > On 03/16, Paul E. McKenney wrote:
> > > 
> > > In the process of writing up the mechanical proof of correctness for the
> > > dynticks/preemptable-RCU interface, I noticed misplaced memory barriers
> > > in rcu_enter_nohz() and rcu_exit_nohz().
> > 
> > Can't comment this patch, there is no rcu_enter_nohz() in my rcupreempt.h ;)
> 
> It is in 2.6.25-rc4 and later.  ;-)

Ah, for some reasons I'm still with -rc2 ...

> > I'm not sure the code below is up to date, but what I have in
> > arch/s390/kernel/time.c is:
> > 
> > 	stop_hz_timer:
> > 
> > 		cpu_set(cpu, nohz_cpu_mask);
> > 		
> > 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> > 			cpu_clear(cpu, nohz_cpu_mask);
> > 			return;
> > 		}
> > 
> > Don't we need smp_mb() after cpu_set() ?
> 
> S390's memory model is quite strong, so it might not be needed.

OK, in that case we shouldn't worry.

> In any
> case, if needed, it goes -before- the cpu_set(), because the problems
> would arise if prior RCU read-side critical sections were to be reordered
> to follow this cpu_set(), right?

No, but it is very possible I missed something.

What if rcu_needs_cpu(cpu) is executed before cpu_set(cpu, nohz_cpu_mask)?
It can miss rcu_start_batch() -> rcp->cur++ and return false, but at the
same time rcu_start_batch() may see nohz_cpu_mask without this CPU.

No?

Oleg.

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Paul E. McKenney]

On Mon, Mar 17, 2008 at 11:17:41PM +0300, Oleg Nesterov wrote:
> (to clarify: my question is completely offtopic to this patch)
> On 03/17, Paul E. McKenney wrote:
> > On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> > > I'm not sure the code below is up to date, but what I have in
> > > arch/s390/kernel/time.c is:
> > > 
> > > 	stop_hz_timer:
> > > 
> > > 		cpu_set(cpu, nohz_cpu_mask);
> > > 		
> > > 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> > > 			cpu_clear(cpu, nohz_cpu_mask);
> > > 			return;
> > > 		}
> > > 
> > > Don't we need smp_mb() after cpu_set() ?
> > 
> > S390's memory model is quite strong, so it might not be needed.
> 
> OK, in that case we shouldn't worry.

I don't know if I would go -that- far.  ;-)

> > In any
> > case, if needed, it goes -before- the cpu_set(), because the problems
> > would arise if prior RCU read-side critical sections were to be reordered
> > to follow this cpu_set(), right?
> 
> No, but it is very possible I missed something.
> 
> What if rcu_needs_cpu(cpu) is executed before cpu_set(cpu, nohz_cpu_mask)?
> It can miss rcu_start_batch() -> rcp->cur++ and return false, but at the
> same time rcu_start_batch() may see nohz_cpu_mask without this CPU.

If you mean that the rcu_needs_cpu() executes before the cpu_set() in
the code fragment above, while the rcu_start_batch() executes on some
other CPU?

Hmmm....  Can't see why this wouldn't be a problem, right off-hand,
though I cannot claim to be an s390 expert.

Heiko, thoughts?

							Thanx, Paul

> No?
> 
> Oleg.
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Oleg Nesterov]

On 03/17, Paul E. McKenney wrote:
>
> On Mon, Mar 17, 2008 at 11:17:41PM +0300, Oleg Nesterov wrote:
> > (to clarify: my question is completely offtopic to this patch)
> > On 03/17, Paul E. McKenney wrote:
> > > On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> > > > I'm not sure the code below is up to date, but what I have in
> > > > arch/s390/kernel/time.c is:
> > > > 
> > > > 	stop_hz_timer:
> > > > 
> > > > 		cpu_set(cpu, nohz_cpu_mask);
> > > > 		
> > > > 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> > > > 			cpu_clear(cpu, nohz_cpu_mask);
> > > > 			return;
> > > > 		}
> > > > 
> > > > Don't we need smp_mb() after cpu_set() ?
> > > 
> > > S390's memory model is quite strong, so it might not be needed.
> > 
> > OK, in that case we shouldn't worry.
> 
> I don't know if I would go -that- far.  ;-)
> 
> > > In any
> > > case, if needed, it goes -before- the cpu_set(), because the problems
> > > would arise if prior RCU read-side critical sections were to be reordered
> > > to follow this cpu_set(), right?
> > 
> > No, but it is very possible I missed something.
> > 
> > What if rcu_needs_cpu(cpu) is executed before cpu_set(cpu, nohz_cpu_mask)?
> > It can miss rcu_start_batch() -> rcp->cur++ and return false, but at the
> > same time rcu_start_batch() may see nohz_cpu_mask without this CPU.
> 
> If you mean that the rcu_needs_cpu() executes before the cpu_set() in
> the code fragment above, while the rcu_start_batch() executes on some
> other CPU?

Yes, and __rcu_pending() sees the old value of ->cur.

IOW. Suppose that this CPU reads rcp->cur out of order. To simplify, let's
suppose that stop_hz_timer() on CPU_0 in fact does

	xxx = rcu_needs_cpu(cpu); // false

	// ---- WINDOW ------

	cpu_set(cpu, nohz_cpu_mask);

	if (xxx || local_softirq_pending()) {
		... abort ...
	}

	...proceed...

Another CPU does rcu_start_batch() in the window above. In that case
rcp->cpumask will include CPU_0, and the grace period can't be completed
untill CPU_0 is "woken".

Oleg.

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Heiko Carstens]

On Mon, Mar 17, 2008 at 01:43:57PM -0700, Paul E. McKenney wrote:
> On Mon, Mar 17, 2008 at 11:17:41PM +0300, Oleg Nesterov wrote:
> > (to clarify: my question is completely offtopic to this patch)
> > On 03/17, Paul E. McKenney wrote:
> > > On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> > > > I'm not sure the code below is up to date, but what I have in
> > > > arch/s390/kernel/time.c is:
> > > > 
> > > > 	stop_hz_timer:
> > > > 
> > > > 		cpu_set(cpu, nohz_cpu_mask);
> > > > 		
> > > > 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> > > > 			cpu_clear(cpu, nohz_cpu_mask);
> > > > 			return;
> > > > 		}
> > > > 
> > > > Don't we need smp_mb() after cpu_set() ?
> > > 
> > > S390's memory model is quite strong, so it might not be needed.
> > 
> > OK, in that case we shouldn't worry.
> 
> I don't know if I would go -that- far.  ;-)

Not sure if I can follow you here, but for the smp case cpu_set() is
nothing but a set_bit() which implies both: a memory barrier and a compiler
barrier on s390. The compare and swap instruction used here ensures that
all previous memory accesses will be seen by other cpus.

Btw. the code sequence above will go away soon anyway, since I'm converting
our code to the generic NO_HZ infrastructure.

> > > In any
> > > case, if needed, it goes -before- the cpu_set(), because the problems
> > > would arise if prior RCU read-side critical sections were to be reordered
> > > to follow this cpu_set(), right?
> > 
> > No, but it is very possible I missed something.
> > 
> > What if rcu_needs_cpu(cpu) is executed before cpu_set(cpu, nohz_cpu_mask)?
> > It can miss rcu_start_batch() -> rcp->cur++ and return false, but at the
> > same time rcu_start_batch() may see nohz_cpu_mask without this CPU.
> 
> If you mean that the rcu_needs_cpu() executes before the cpu_set() in
> the code fragment above, while the rcu_start_batch() executes on some
> other CPU?

That should never happen because of the compiler and memory barrier semantics
of cpu_set(). Or... I'm completely misunderstanding you, which wouldn't me
surprise me too much :)

Re: [PATCH] fix misplaced mb() in rcu_enter/exit_nohz()

[Paul E. McKenney]

On Tue, Mar 18, 2008 at 01:42:48PM +0100, Heiko Carstens wrote:
> On Mon, Mar 17, 2008 at 01:43:57PM -0700, Paul E. McKenney wrote:
> > On Mon, Mar 17, 2008 at 11:17:41PM +0300, Oleg Nesterov wrote:
> > > (to clarify: my question is completely offtopic to this patch)
> > > On 03/17, Paul E. McKenney wrote:
> > > > On Mon, Mar 17, 2008 at 09:30:47PM +0300, Oleg Nesterov wrote:
> > > > > I'm not sure the code below is up to date, but what I have in
> > > > > arch/s390/kernel/time.c is:
> > > > > 
> > > > > 	stop_hz_timer:
> > > > > 
> > > > > 		cpu_set(cpu, nohz_cpu_mask);
> > > > > 		
> > > > > 		if (rcu_needs_cpu(cpu) || local_softirq_pending()) {
> > > > > 			cpu_clear(cpu, nohz_cpu_mask);
> > > > > 			return;
> > > > > 		}
> > > > > 
> > > > > Don't we need smp_mb() after cpu_set() ?
> > > > 
> > > > S390's memory model is quite strong, so it might not be needed.
> > > 
> > > OK, in that case we shouldn't worry.
> > 
> > I don't know if I would go -that- far.  ;-)
> 
> Not sure if I can follow you here, but for the smp case cpu_set() is
> nothing but a set_bit() which implies both: a memory barrier and a compiler
> barrier on s390. The compare and swap instruction used here ensures that
> all previous memory accesses will be seen by other cpus.

That should make this work as far as I can see!

							Thanx, Paul

> Btw. the code sequence above will go away soon anyway, since I'm converting
> our code to the generic NO_HZ infrastructure.
> 
> > > > In any
> > > > case, if needed, it goes -before- the cpu_set(), because the problems
> > > > would arise if prior RCU read-side critical sections were to be reordered
> > > > to follow this cpu_set(), right?
> > > 
> > > No, but it is very possible I missed something.
> > > 
> > > What if rcu_needs_cpu(cpu) is executed before cpu_set(cpu, nohz_cpu_mask)?
> > > It can miss rcu_start_batch() -> rcp->cur++ and return false, but at the
> > > same time rcu_start_batch() may see nohz_cpu_mask without this CPU.
> > 
> > If you mean that the rcu_needs_cpu() executes before the cpu_set() in
> > the code fragment above, while the rcu_start_batch() executes on some
> > other CPU?
> 
> That should never happen because of the compiler and memory barrier semantics
> of cpu_set(). Or... I'm completely misunderstanding you, which wouldn't me
> surprise me too much :)