fix misplaced mb() in rcu_enter/exit_nohz()

PATCH In review Paul E. McKenney 5 participants 11 messages Mar 17, 2008 – Mar 19, 2008 RCU

lore

Share & tools

lore

Paul E. McKenney

author

2008-03-17 01:08 UTC #0 lore raw

PATCH 1/1 fix misplaced mb() in rcu_enter/exit_nohz()

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 <[email protected]>

---

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

include/linux/rcupreempt.h +2 -2

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
@@ -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));
 }

Nick Piggin

2008-03-17 03:09 UTC #1 lore raw

Quoted 33 lines · 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 <[email protected]>
---
 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)
{
include/linux/rcupreempt.h +1 -0
+	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);

include/linux/rcupreempt.h DECLARE_PER_CPU(long, dynticks_progress_ · line 100

Quoted 10 lines

include/linux/rcupreempt.h +1 -2

-	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

Paul E. McKenney

author

2008-03-17 05:54 UTC #2 lore raw

Quoted 37 lines · Nick Piggin

Quoted 36 lines · 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 <[email protected]>
---
 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)
{
(quoted diff) +1 -1
+	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();
 }

Quoted 9 lines

Review
Quoted 7 lines
static inline void rcu_exit_nohz(void)
{
(quoted diff) +1 -1
-	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 <[email protected]>

---

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

include/linux/rcupreempt.h +2 -2

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
@@ -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));
 }

Steven Rostedt

reviewer Acked-by

2008-03-17 15:43 UTC #3 lore raw

Quoted 5 lines · Paul E. McKenney

Quoted 2 lines
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 <[email protected]>

Quoted 2 lines

Signed-off-by Paul E. McKenney <[email protected]>

-- Steve

Oleg Nesterov

2008-03-17 18:25 UTC #4 lore raw

In reply to Paul E. McKenney

Quoted 4 lines · Paul E. McKenney

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.

Paul E. McKenney

author

2008-03-17 19:06 UTC #5 lore raw

Quoted 7 lines · Oleg Nesterov

Quoted 4 lines · Paul E. McKenney
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. ;-)

Quoted 12 lines

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;
		}

Quoted 1 line

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

Oleg Nesterov

2008-03-17 20:18 UTC #6 lore raw

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

Quoted 11 lines · Paul E. McKenney

Quoted 7 lines · Oleg Nesterov
Quoted 4 lines · Paul E. McKenney
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 ...

Quoted 7 lines

Quoted 7 lines
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);

Quoted 8 lines

Quoted 6 lines
		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.

Quoted 4 lines

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.

Paul E. McKenney

author

2008-03-17 20:44 UTC #7 lore raw

Quoted 15 lines · Oleg Nesterov

(to clarify: my question is completely offtopic to this patch)
Quoted 13 lines · Paul E. McKenney
Quoted 12 lines · Oleg Nesterov
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;
		}

Quoted 5 lines

Quoted 3 lines
Quoted 1 line
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. ;-)

Quoted 10 lines

Quoted 4 lines
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

Quoted 8 lines

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

Oleg Nesterov

2008-03-17 21:23 UTC #8 lore raw

Quoted 32 lines · Paul E. McKenney

Quoted 15 lines · Oleg Nesterov
(to clarify: my question is completely offtopic to this patch)
Quoted 13 lines · Paul E. McKenney
Quoted 12 lines · Oleg Nesterov
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;
		}
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
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. ;-)
Quoted 7 lines
Quoted 4 lines
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.

Quoted 7 lines

Quoted 3 lines
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.

Heiko Carstens

2008-03-18 12:42 UTC #9 lore raw

In reply to Paul E. McKenney

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Oleg Nesterov
(to clarify: my question is completely offtopic to this patch)
Quoted 13 lines · Paul E. McKenney
Quoted 12 lines · Oleg Nesterov
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;
		}

Quoted 7 lines

Quoted 5 lines
Quoted 3 lines
Quoted 1 line
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.

Quoted 7 lines

Quoted 7 lines
Quoted 4 lines
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.

Quoted 7 lines

Quoted 3 lines
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 :)

Paul E. McKenney

author

2008-03-19 19:45 UTC #10 lore raw

Quoted 21 lines · Heiko Carstens

Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Oleg Nesterov
(to clarify: my question is completely offtopic to this patch)
Quoted 16 lines · Paul E. McKenney
Quoted 12 lines · Oleg Nesterov
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;
		}
Quoted 1 line
Don't we need smp_mb() after cpu_set() ?
S390's memory model is quite strong, so it might not be needed.

Quoted 8 lines

Quoted 3 lines
Quoted 1 line
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

Quoted 21 lines

Btw. the code sequence above will go away soon anyway, since I'm converting our code to the generic NO_HZ infrastructure.
Quoted 7 lines
Quoted 7 lines
Quoted 4 lines
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.
Quoted 7 lines
Quoted 3 lines
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 :)