[PATCH] Fix RCU race in access of nohz_cpu_mask

[PATCH] Fix RCU race in access of nohz_cpu_mask

[Srivatsa Vaddagiri]

Accessing  nohz_cpu_mask before incrementing rcp->cur is racy. It can
cause tickless idle CPUs to be included in rsp->cpumask, which will
extend graceperiods unnecessarily.

Patch below (against 2.6.15-rc5-mm1) fixes this race. It has been tested using 
extensions to RCU torture module that forces various CPUs to become idle.

Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com>

---

 linux-2.6.15-rc5-mm1-root/kernel/rcupdate.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff -puN kernel/rcupdate.c~rcu-lock kernel/rcupdate.c
--- linux-2.6.15-rc5-mm1/kernel/rcupdate.c~rcu-lock	2005-12-05 15:28:33.000000000 +0530
+++ linux-2.6.15-rc5-mm1-root/kernel/rcupdate.c	2005-12-05 15:28:40.000000000 +0530
@@ -244,15 +244,15 @@ static void rcu_start_batch(struct rcu_c
 
 	if (rcp->next_pending &&
 			rcp->completed == rcp->cur) {
-		/* Can't change, since spin lock held. */
-		cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);
-
 		rcp->next_pending = 0;
 		/* next_pending == 0 must be visible in __rcu_process_callbacks()
 		 * before it can see new value of cur.
 		 */
 		smp_wmb();
 		rcp->cur++;
+		smp_mb();
+		cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);
+
 	}
 }
 

_


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Andrew Morton]

Srivatsa Vaddagiri <vatsa@in.ibm.com> wrote:
>
> +		smp_mb();
> +		cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);

Please always include a comment when adding a barrier.  Because it's often
not obvious to the reader what that barrier is actually doing.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Oleg Nesterov]

Srivatsa Vaddagiri wrote:
>
> Accessing  nohz_cpu_mask before incrementing rcp->cur is racy. It can
> cause tickless idle CPUs to be included in rsp->cpumask, which will
> extend graceperiods unnecessarily.
> ...
> @@ -244,15 +244,15 @@ static void rcu_start_batch(struct rcu_c
>
>         if (rcp->next_pending &&
>                         rcp->completed == rcp->cur) {
> -               /* Can't change, since spin lock held. */
> -               cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);
> -
>                 rcp->next_pending = 0;
>                 /* next_pending == 0 must be visible in __rcu_process_callbacks()
>                  * before it can see new value of cur.
>                  */
>                 smp_wmb();
>                 rcp->cur++;
> +               smp_mb();
> +               cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);
> +

Could you explain why this patch makes any difference?

grep shows the only user of nohz_cpu_mask in arch/s390/kernel/time.c,
start_hz_timer() and stop_hz_timer().

I can't see how this change can prevent idle cpus to be included in
->cpumask, cpu can add itself to nohz_cpu_mask right after some other
cpu started new grace period.

I think cpu should call cpu_quiet() after adding itself to nohz mask
to eliminate this race.

No?

Oleg.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Srivatsa Vaddagiri]

On Thu, Dec 08, 2005 at 10:31:06PM +0300, Oleg Nesterov wrote:
> I can't see how this change can prevent idle cpus to be included in
> ->cpumask, cpu can add itself to nohz_cpu_mask right after some other
> cpu started new grace period.

Yes that can happen, but if they check for rcu_pending right after that
it will prevent them from going tickless atleast (which will prevent grace
periods from being unnecessarily extended). Something like below:


	CPU0					CPU1



	rcp->cur++;	/* New GP */		

	smp_mb();

	rsp->cpumask = 0x3

						cpu_set(1, nohz_cpu_mask);

						rcu_pending()? 
						 - Yes,
						   cpu_clear(1, nohz_cpu_mask);
						   Abort going tickless


Ideally we would have needed a smp_mb() in CPU1 also between setting CPU1
in nohz_cpu_mask and checking for rcu_pending(), but I guess it is not needed
in s390 because of its strong ordering?

-- 


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Srivatsa Vaddagiri]

On Thu, Dec 08, 2005 at 10:31:06PM +0300, Oleg Nesterov wrote:
> I think cpu should call cpu_quiet() after adding itself to nohz mask
> to eliminate this race.

That would require rsp->lock to be taken on every idle CPU that wishes to go
tickless. IMO that may not be a good idea.

-- 


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Oleg Nesterov]

Srivatsa Vaddagiri wrote:
> 
> On Thu, Dec 08, 2005 at 10:31:06PM +0300, Oleg Nesterov wrote:
> > I can't see how this change can prevent idle cpus to be included in
> > ->cpumask, cpu can add itself to nohz_cpu_mask right after some other
> > cpu started new grace period.
> 
> Yes that can happen, but if they check for rcu_pending right after that
> it will prevent them from going tickless atleast (which will prevent grace
> periods from being unnecessarily extended). Something like below:
> 
>         CPU0                                    CPU1
> 
>         rcp->cur++;     /* New GP */
> 
>         smp_mb();

I think I need some education on memory barriers.

Does this mb() garantees that the new value of ->cur will be visible
on other cpus immediately after smp_mb() (so that rcu_pending() will
notice it) ?

My understanding is that it only garantees that all stores before it
must be visible before any store after mb. (yes, mb implies rmb, but
I think it does not matter if CPU1 adds itself to nonhz mask after
CPU0 reads nohz_cpu_mask). This means that CPU1 can read the stale
value of ->cur. I guess I am wrong, but I can't prove it to myself.

Could you please clarify this?

Even simpler question:

CPU0
	var = 1;
	wmb();

after that CPU1 does rmb().

Does it garantees that CPU1 will see the new value of var?

> Ideally we would have needed a smp_mb() in CPU1 also between setting CPU1
> in nohz_cpu_mask and checking for rcu_pending(), but I guess it is not needed
> in s390 because of its strong ordering?

I don't know, but please note that s390's definition of smp_mb__after_atomic_inc()
is not a 'nop'.

Oleg.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Srivatsa Vaddagiri]

On Fri, Dec 09, 2005 at 10:17:38PM +0300, Oleg Nesterov wrote:
> Srivatsa Vaddagiri wrote:
> > 
> > On Thu, Dec 08, 2005 at 10:31:06PM +0300, Oleg Nesterov wrote:
> > > I can't see how this change can prevent idle cpus to be included in
> > > ->cpumask, cpu can add itself to nohz_cpu_mask right after some other
> > > cpu started new grace period.
> > 
> > Yes that can happen, but if they check for rcu_pending right after that
> > it will prevent them from going tickless atleast (which will prevent grace
> > periods from being unnecessarily extended). Something like below:
> > 
> >         CPU0                                    CPU1
> > 
> >         rcp->cur++;     /* New GP */
> > 
> >         smp_mb();
> 
> I think I need some education on memory barriers.
> 
> Does this mb() garantees that the new value of ->cur will be visible
> on other cpus immediately after smp_mb() (so that rcu_pending() will
> notice it) ?

AFAIK the new value of ->cur should be visible to other CPUs when smp_mb() 
returns. Here's a definition of smp_mb() from Paul's article:

smp_mb(): "memory barrier" that orders both loads and stores. This means loads 
and stores preceding the memory barrier are committed to memory before any 
loads and stores following the memory barrier.

[ http://www.linuxjournal.com/article/8211 ]

> My understanding is that it only garantees that all stores before it
> must be visible before any store after mb. (yes, mb implies rmb, but
> I think it does not matter if CPU1 adds itself to nonhz mask after
> CPU0 reads nohz_cpu_mask). This means that CPU1 can read the stale
> value of ->cur. I guess I am wrong, but I can't prove it to myself.
> 
> Could you please clarify this?
> 
> Even simpler question:
> 
> CPU0
> 	var = 1;
> 	wmb();
> 
> after that CPU1 does rmb().
> 
> Does it garantees that CPU1 will see the new value of var?

Again, going by the above article, I would expect CPU1 to see the new value of 
var.


-- 


Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Oleg Nesterov]

Srivatsa Vaddagiri wrote:
> 
> On Fri, Dec 09, 2005 at 10:17:38PM +0300, Oleg Nesterov wrote:
> > >         rcp->cur++;     /* New GP */
> > >
> > >         smp_mb();
> >
> > I think I need some education on memory barriers.
> >
> > Does this mb() garantees that the new value of ->cur will be visible
> > on other cpus immediately after smp_mb() (so that rcu_pending() will
> > notice it) ?
> 
> AFAIK the new value of ->cur should be visible to other CPUs when smp_mb()
> returns. Here's a definition of smp_mb() from Paul's article:
> 
> smp_mb(): "memory barrier" that orders both loads and stores. This means loads
> and stores preceding the memory barrier are committed to memory before any
> loads and stores following the memory barrier.

Thanks, but this definition talks about ordering, it does not say
anything about the time when stores are really commited to memory
(and does it mean also that cache-lines are invalidated on other
cpus ?).

> [ http://www.linuxjournal.com/article/8211 ]

And thanks for this link, now I have some understanding about
read_barrier_depends() ...

Oleg.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Paul E. McKenney]

On Sat, Dec 10, 2005 at 09:55:35PM +0300, Oleg Nesterov wrote:
> Srivatsa Vaddagiri wrote:
> > 
> > On Fri, Dec 09, 2005 at 10:17:38PM +0300, Oleg Nesterov wrote:
> > > >         rcp->cur++;     /* New GP */
> > > >
> > > >         smp_mb();
> > >
> > > I think I need some education on memory barriers.
> > >
> > > Does this mb() garantees that the new value of ->cur will be visible
> > > on other cpus immediately after smp_mb() (so that rcu_pending() will
> > > notice it) ?
> > 
> > AFAIK the new value of ->cur should be visible to other CPUs when smp_mb()
> > returns. Here's a definition of smp_mb() from Paul's article:
> > 
> > smp_mb(): "memory barrier" that orders both loads and stores. This means loads
> > and stores preceding the memory barrier are committed to memory before any
> > loads and stores following the memory barrier.
> 
> Thanks, but this definition talks about ordering, it does not say
> anything about the time when stores are really commited to memory
> (and does it mean also that cache-lines are invalidated on other
> cpus ?).

Think of a pair of CPUs (creatively named "CPU 0" and "CPU 1") with
a cache-coherent interconnect between them.  Then:

1.	wmb() guarantees that any writes preceding the wmb() will
	be seen by the interconnect before any writes following the
	wmb().  But this applies -only- to the writes executed by
	the CPU doing the wmb().

2.	rmb() guarantees that any changes seen by the interconnect
	preceding the rmb() will be seen by any reads following the
	rmb().  Again, this applies only to reads executed by the
	CPU doing the wmb().  However, the changes might be due to
	any CPU.

3.	mb() combines the guarantees made by rmb() and wmb().

All CPUs but Alpha make stronger guarantees.  On those CPUs, you can
replace "interconnect" in #1 above with "all CPUs", and you can replace
"seen by the interconnect" in #2 above with "caused by any CPU".
Rumor has it that more recent Alpha CPUs also have stronger memory
barriers, but I have thus far been unable to confirm this.

On with the rest of the definitions:

4.	smp_wmb(), smp_rmb(), and smb_mb() do nothing in UP kernels,
	but do the corresponding memory barrier in SMP kernels.

5.	read_barrier_depends() is rmb() on Alpha, and nop on other
	CPUs.  Non-Alpha CPUs guarantee that if CPU 0 does the
	following, where p->a is initially zero and global_pointer->a
	is initially 1:

		p->a = 2;
		smp_wmb();
		global_pointer = p;

	and if CPU 1 does:

		x = global_pointer->a;

	then the value of x will be either 1 or 2, never zero.  On Alpha,
	strange though it may seem (and it did seem strange to me when I
	first encountered it!), the value of x could well be zero.
	To get the same guarantee on Alpha as on the other CPUs, the
	assignment to x must instead be as follows:

		tmp = global_pointer;
		read_memory_depends();
		x = tmp->a;

	or, equivalently:

		x = rcu_dereference(global_pointer)->a;

	There is an smp_read_barrier_depends() that takes effect only
	in an SMP kernel, similar to smp_wmb() and friends.

This example may seem quite strange, but the need for the barrier
follows directly from the definition #1, which makes its ordering
guarantee only to the -interconnect-, -not- to the other CPUs.

> > [ http://www.linuxjournal.com/article/8211 ]

Hmm...  That one does look familiar.  ;-)

> And thanks for this link, now I have some understanding about
> read_barrier_depends() ...

Let's just say it required much patience and perseverence on the part
of the Alpha architects to explain it to me the first time around.  ;-)

							Thanx, Paul

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Andrew Morton]

"Paul E. McKenney" <paulmck@us.ibm.com> wrote:
>
> 1.	wmb() guarantees that any writes preceding the wmb() will
>  	be seen by the interconnect before any writes following the
>  	wmb().  But this applies -only- to the writes executed by
>  	the CPU doing the wmb().
> 
>  2.	rmb() guarantees that any changes seen by the interconnect
>  	preceding the rmb() will be seen by any reads following the
>  	rmb().  Again, this applies only to reads executed by the
>  	CPU doing the wmb().  However, the changes might be due to
>  	any CPU.
> 
>  3.	mb() combines the guarantees made by rmb() and wmb().

So foo_mb() in preemptible code is potentially buggy.

I guess we assume that a context switch accidentally did enough of the
right types of barriers for things to work OK.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[David S. Miller]

From: Andrew Morton <akpm@osdl.org>
Date: Sun, 11 Dec 2005 20:32:26 -0800

> So foo_mb() in preemptible code is potentially buggy.
> 
> I guess we assume that a context switch accidentally did enough of the
> right types of barriers for things to work OK.

A trap ought to flush all memory operations.

There are some incredibly difficult memory error handling cases if the
cpu does not synchronize all pending memory operations when a trap
occurs.

Failing that, yes, to be absolutely safe we'd need to have some
explicit memory barrier in the context switch.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Nick Piggin]

David S. Miller wrote:
> From: Andrew Morton <akpm@osdl.org>
> Date: Sun, 11 Dec 2005 20:32:26 -0800
> 
> 
>>So foo_mb() in preemptible code is potentially buggy.
>>
>>I guess we assume that a context switch accidentally did enough of the
>>right types of barriers for things to work OK.
> 
> 
> A trap ought to flush all memory operations.
> 
> There are some incredibly difficult memory error handling cases if the
> cpu does not synchronize all pending memory operations when a trap
> occurs.
> 
> Failing that, yes, to be absolutely safe we'd need to have some
> explicit memory barrier in the context switch.

But it isn't that mbs in preemptible code are buggy. If they are
scheduled off then back on the same CPU, the barrier will still
be executed in the expected instruction sequence for that process.

I think the minimum needed is for cpu *migrations* to be memory
barriers. Again, this isn't any particular problem of mb()
instructions - if cpu migrations weren't memory barriers, then
preemptible code isn't even guaranteed ordering with its own memory
operations, which would be quite interesting :)

-- 
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Paul Mackerras]

Andrew Morton writes:

> So foo_mb() in preemptible code is potentially buggy.
> 
> I guess we assume that a context switch accidentally did enough of the
> right types of barriers for things to work OK.

The context switch code on powerpc includes an mb() for exactly this
reason.

Paul.

Re: [PATCH] Fix RCU race in access of nohz_cpu_mask

[Keith Owens]

On Sun, 11 Dec 2005 20:32:26 -0800, 
Andrew Morton <akpm@osdl.org> wrote:
>"Paul E. McKenney" <paulmck@us.ibm.com> wrote:
>>
>> 1.	wmb() guarantees that any writes preceding the wmb() will
>>  	be seen by the interconnect before any writes following the
>>  	wmb().  But this applies -only- to the writes executed by
>>  	the CPU doing the wmb().
>> 
>>  2.	rmb() guarantees that any changes seen by the interconnect
>>  	preceding the rmb() will be seen by any reads following the
>>  	rmb().  Again, this applies only to reads executed by the
>>  	CPU doing the wmb().  However, the changes might be due to
>>  	any CPU.
>> 
>>  3.	mb() combines the guarantees made by rmb() and wmb().
>
>So foo_mb() in preemptible code is potentially buggy.
>
>I guess we assume that a context switch accidentally did enough of the
>right types of barriers for things to work OK.

Not by accident.  Any context switch must flush the memory state from
the old cpu's internal buffers, and that flush must get at least as far
as the globally snoopable cache.  Otherwise the old cpu could still own
partial memory updates from the process, even though the process was
now running on a new cpu.