Skip to contentSkip to conversation

Fix RCU race in access of nohz_cpu_mask

PATCH Oleg Nesterov 15 participants 33 messages Dec 8, 2005 – Mar 31, 2006

lore
Share & tools
lore
#0 lore raw
Quoted 11 lines · 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.
...

(quoted diff) +0 -2
@@ -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);

Review static void rcu_start_batch(struct rcu_c · line 255

Quoted 10 lines
(quoted diff) +3 -1
-
                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.

#1 lore raw
Quoted 3 lines · Oleg Nesterov

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?

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#2 lore raw
Quoted 10 lines · Srivatsa Vaddagiri
Quoted 3 lines · Oleg Nesterov

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:

Quoted 5 lines
        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?

Quoted 3 lines

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.

#3 lore raw
Quoted 15 lines · Oleg Nesterov
Quoted 14 lines · Srivatsa Vaddagiri
Quoted 3 lines · Oleg Nesterov

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 */
Quoted 7 lines
Quoted 1 line
        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 ]

Quoted 10 lines

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:

Quoted 7 lines

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.

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#4 lore raw
Quoted 12 lines · Srivatsa Vaddagiri
Quoted 9 lines · Oleg Nesterov
Quoted 3 lines
        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) ?

Quoted 6 lines

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 ?).

Quoted 1 line

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

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

Oleg.

#5 lore raw

Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

[Changed the subject line to be more generic in the interest of wider audience]

We seem to be having some confusion over the exact semantics of smp_mb().

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

Quoted 1 line

From IA-32 manual (download.intel.com/design/Pentium4/manuals/25366817.pdf

Page 271):

"Memory mapped devices and other I/O devices on the bus are often sensitive to the order of writes to their I/O buffers. I/O instructions can be used to (the IN and OUT instructions) impose strong write ordering on such accesses as follows. Prior to executing an I/O instruction, the processor waits for all

						___________________________

previous instructions in the program to complete and for all buffered
_____________________________________________________________________
writes to drain to memory. Only instruction fetch and page tables walks can
_________________________
pass I/O instructions. Execution of subsequent instructions do not begin until the processor determines that the I/O instruction has been completed."

Synchronization mechanisms in multiple-processor systems may depend upon a strong memory-ordering model. Here, a program can use a locking instruction such as the XCHG instruction or the LOCK prefix to insure that a read-modify-write operation on memory is carried out atomically. Locking operations typically operate like I/O operations in that they wait for all

							 _________________

previous instructions to complete and for all buffered writes to drain to
_________________________________________________________________________
memory (see Section 7.1.2, “Bus Locking”).
______

Program synchronization can also be carried out with serializing instructions (see Section 7.4). These instructions are typically used at critical procedure or task boundaries to force completion of all previous instructions before a jump to a new section of code or a context switch occurs. Like the I/O and locking instructions, the processor waits until all previous instructions have

		      ________________________________________________________

been completed and all buffered writes have been drained to memory before
_________________________________________________________________________
executing the serializing instruction."
_____________________________________

Quoted 1 line

From this, looks like we can interpret that IA-32 processor will wait for all

writes to drain to memory (implies cache invalidation on other CPUs?) *before* executing the synchronizing instruction?

Question is can this be generalized for other CPUs too?

Quoted 31 lines · Oleg Nesterov
Quoted 12 lines · Srivatsa Vaddagiri
Quoted 9 lines · Oleg Nesterov
Quoted 3 lines
        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) ?

Quoted 6 lines

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 ?).

Quoted 1 line

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

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

Oleg.

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#6 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 7 lines · Srivatsa Vaddagiri

[Changed the subject line to be more generic in the interest of wider audience]

We seem to be having some confusion over the exact semantics of smp_mb().

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

I doubt it. That's definitely not true of smp_wmb(), which boils down to __asm__ __volatile__ ("": : :"memory") on SMP i386 (which the constrains how the compiler orders write instructions, but is otherwise a nop. i386 has in-order writes.).

And it makes sense that wmb() wouldn't wait for writes: RCU needs constraints on the order in which writes become visible, but has very week constraints on when they do. Waiting for writes to flush would hurt performance.

Andrew Wade

#7 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 14 lines · Andrew James Wade
Quoted 7 lines · Srivatsa Vaddagiri

[Changed the subject line to be more generic in the interest of wider audience]

We seem to be having some confusion over the exact semantics of smp_mb().

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

I doubt it. That's definitely not true of smp_wmb(), which boils down to __asm__ __volatile__ ("": : :"memory") on SMP i386 (which the constrains how the compiler orders write instructions, but is otherwise a nop. i386 has in-order writes.).

Quoted 4 lines

And it makes sense that wmb() wouldn't wait for writes: RCU needs constraints on the order in which writes become visible, but has very week constraints on when they do. Waiting for writes to flush would hurt performance.

On the contrary. I did some digging and asking and thinking about this for the Unreliable Guide to Kernel Locking, years ago:

wmb() means all writes preceeding will complete before any writes following are started.
rmb() means all reads preceeding will complete before any reads following are started.
mb() means all reads and writes preceeding will complete before any reads and writes following are started.

This does not map to all the possibilities, nor does it take advantage of all architectures, but it's generally sufficient without getting insanely complex.

Hope that clarifies,
Rusty.

Signature · 1 line
 ccontrol: http://ozlabs.org/~rusty/ccontrol
#8 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 21 lines · Rusty Russell
Quoted 12 lines · Andrew James Wade
Quoted 5 lines · Srivatsa Vaddagiri

We seem to be having some confusion over the exact semantics of smp_mb().

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

I doubt it. That's definitely not true of smp_wmb(), which boils down to __asm__ __volatile__ ("": : :"memory") on SMP i386 (which the constrains how the compiler orders write instructions, but is otherwise a nop. i386 has in-order writes.).

Quoted 4 lines

And it makes sense that wmb() wouldn't wait for writes: RCU needs constraints on the order in which writes become visible, but has very week constraints on when they do. Waiting for writes to flush would hurt performance.

On the contrary. I did some digging and asking and thinking about this for the Unreliable Guide to Kernel Locking, years ago:

Quoted 6 lines

wmb() means all writes preceeding will complete before any writes following are started.
rmb() means all reads preceeding will complete before any reads following are started.
mb() means all reads and writes preceeding will complete before any reads and writes following are started.

FWIW, wmb() on IA64 does not require that preceding stores are flushed to main memory. It only requires that they be "made visible to other processors in the coherence domain". "visible" means that the updated value must reach (at least) an externally snooped cache. There is no requirement that the preceding stores be flushed all the way to main memory, the updates only have to get as far as a cache level that other cpus can see. The cache snooping takes care of flushing to main memory when necessary.

IA64 does have a memory fence that stalls the cpu until the data is "accepted by the external platform". That format is expensive and is only used for memory mapped I/O, where the data really does have to read the memory before the cpu can perform its next operation. For example, in the mmiowb() case.

#9 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 10 lines · Keith Owens
Quoted 9 lines

On the contrary. I did some digging and asking and thinking about this for the Unreliable Guide to Kernel Locking, years ago:

wmb() means all writes preceeding will complete before any writes following are started.
rmb() means all reads preceeding will complete before any reads following are started.
mb() means all reads and writes preceeding will complete before any reads and writes following are started.

Quoted 8 lines

FWIW, wmb() on IA64 does not require that preceding stores are flushed to main memory. It only requires that they be "made visible to other processors in the coherence domain". "visible" means that the updated value must reach (at least) an externally snooped cache. There is no requirement that the preceding stores be flushed all the way to main memory, the updates only have to get as far as a cache level that other cpus can see. The cache snooping takes care of flushing to main memory when necessary.

For the context of the problem that we are dealing with, I think this fact that writes are made "visible" to other CPUs (before smp_mb() finishes and before other reads are started) is good enough.

Oleg, with all these inputs, I consider the patch I had sent to be correct. Let me know if you still have some lingering doubts!

P.S :- Thanks to everybody who reponded clarifying this subject.

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#10 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 2 lines · Srivatsa Vaddagiri

Oleg, with all these inputs, I consider the patch I had sent to be correct.

Yes, I think so. My suspects were due to my misunderstanding. I was wrong when I said that we can ignore rmb() part of mb() in case when start_hz_timer() runs after rcu_start_batch().

	rcp->cur++;
	// ->cur will be visible to other cpus
	// _before_ we will *READ* nohz_cpu_mask.
	// we don't have any 'timing' problems.
	// In other words: if another cpu does not
	// see the new value - we did not read this
	// mask yet.
	smp_mb();

Thanks for your patience.

Quoted 1 line

P.S :- Thanks to everybody who reponded clarifying this subject.

Yes! it was really helpful, thanks to all. I think it would be great to have Paul's very clear (and short!) explanation somewhere in Documentation/.

Oleg.

#11 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 7 lines · Oleg Nesterov
Quoted 1 line · Srivatsa Vaddagiri

P.S :- Thanks to everybody who reponded clarifying this subject.

Yes! it was really helpful, thanks to all. I think it would be great to have Paul's very clear (and short!) explanation somewhere in Documentation/.

Glad you liked it!

I need to do an RCU documentation update soon anyway, so will include memory barriers in that update.

Thanx, Paul

#12 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

In reply to Rusty Russell
Quoted 6 lines · Rusty Russell
Quoted 5 lines · Andrew James Wade
Quoted 4 lines · Srivatsa Vaddagiri

[Changed the subject line to be more generic in the interest of wider audience]

We seem to be having some confusion over the exact semantics of smp_mb().

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

I doubt it. That's definitely not true of smp_wmb(), which boils down to __asm__ __volatile__ ("": : :"memory") on SMP i386 (which the constrains how the compiler orders write instructions, but is otherwise a nop. i386 has in-order writes.).

Hrrm, after doing a bit of reading on cache-coherency, verifying that the corresponding cache-lines on other CPUs are invalidated can (sometimes) be done quite quickly, so waiting for that before issuing reads might not destroy performance. I still doubt that i386es do thing this way, but I don't think it matters (see below).

Quoted 11 lines
Quoted 5 lines

And it makes sense that wmb() wouldn't wait for writes: RCU needs constraints on the order in which writes become visible, but has very week constraints on when they do. Waiting for writes to flush would hurt performance.

On the contrary. I did some digging and asking and thinking about this for the Unreliable Guide to Kernel Locking, years ago:

wmb() means all writes preceeding will complete before any writes following are started.

What does it mean for a write to start? For that matter, what does it mean for a write to complete?

I think my focusing on the hardware details (of which I am woefully ignorant) was a mistake: the hardware can really do whatever it wants so long as it implements the expected abstract machine model, and it is ordering that matters in that model. So it makes sense that ordering, not time, is what the definitions of the memory barriers focus on.

I think that Oleg's question:

Quoted 3 lines

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) ?

is really just about the timeliness with which writes before a smp_mb() become visible to other CPUs. Does Linux run on architectures in which writes are not propagated in a timely manner (that is: other CPUs can read stale values for a "considerable" time)? I rather doubt it.

But with a proviso to my answer: the compiler will happily hoist reads out of loops. So writes won't necessarily get read in a timely manner.

Andrew

#13 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 16 lines · Andrew James Wade
Quoted 6 lines · Rusty Russell
Quoted 5 lines · Andrew James Wade
Quoted 4 lines · Srivatsa Vaddagiri

[Changed the subject line to be more generic in the interest of wider audience]

We seem to be having some confusion over the exact semantics of smp_mb().

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines

Specifically, are all stores preceding smp_mb() guaranteed to have finished (committed to memory/corresponding cache-lines on other CPUs invalidated) *before* successive loads are issued?

I doubt it. That's definitely not true of smp_wmb(), which boils down to __asm__ __volatile__ ("": : :"memory") on SMP i386 (which the constrains how the compiler orders write instructions, but is otherwise a nop. i386 has in-order writes.).

Quoted 5 lines

Hrrm, after doing a bit of reading on cache-coherency, verifying that the corresponding cache-lines on other CPUs are invalidated can (sometimes) be done quite quickly, so waiting for that before issuing reads might not destroy performance. I still doubt that i386es do thing this way, but I don't think it matters (see below).

Hardware designers need only be concerned with how things -appear- to the software. They can and do use optimizations that get the effect of waiting without actually waiting. For example, an x86 CPU need not -really- keep writes ordered as long as the software cannot tell that they have become misordered. This may sound strange, but one important example would be a CPU doing writes that are to variables that it knows do not appear in any other CPU's cache. In this sort of case, the CPU could reorder the writes until such time as it detected a request from another CPU requsting a cache line containing one of the variables.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

And it makes sense that wmb() wouldn't wait for writes: RCU needs constraints on the order in which writes become visible, but has very week constraints on when they do. Waiting for writes to flush would hurt performance.

Quoted 8 lines
Quoted 5 lines

On the contrary. I did some digging and asking and thinking about this for the Unreliable Guide to Kernel Locking, years ago:

wmb() means all writes preceeding will complete before any writes following are started.

What does it mean for a write to start? For that matter, what does it mean for a write to complete?

Potentially many things in both cases:

o Fetching the store instruction that will do the write.

o Determining that all instructions whose execution logically
precedes the write are free of fatal errors (e.g., page faults, exceptions, traps, ...).

o Determining the exact value that is to be written (which might
have been computed by prior instructions).

o Determining the exact address that is to be written to (which
also might have been computed by prior instructions).

o Determining that the store instruction itself is free of
fatal errors. Note that it might be necessary to compute the address to be sure.

o Determining that no hardware interrupt will precede the
completion of the store instruction.

o Storing the value to one of the CPU's write buffers (which

	is not yet in the coherence region represented by the CPU's
	cache).

o Starting the process of fetching the cache line into which
the value is to be stored.

o Starting the process of invalidating the corresponding cache
line from all the other CPUs' caches.

o Receiving the cache line into which the value is to be stored.

o Storing the value to the CPU's cache, which involves combining
the value to be written with the rest of the cache line.

o Responding to the first request for the corresponding cache
line from some other CPU.

o Completing the process of invalidating the corresponding cache
line from all the other CPUs' caches. Note that Alpha's weak memory-barrier semantics allow this step to complete long after the value is stored into the writing CPU's cache.

o Storing the value to physical DRAM.

Most of these steps can execute in parallel or out of order. And a CPU designer would gleefully point out -lots- of steps I have omitted, some for the sake of brevity, others out of ignorance.

You asked!!!

Quoted 5 lines

I think my focusing on the hardware details (of which I am woefully ignorant) was a mistake: the hardware can really do whatever it wants so long as it implements the expected abstract machine model, and it is ordering that matters in that model. So it makes sense that ordering, not time, is what the definitions of the memory barriers focus on.

Yes, maintaining one's sanity requires taking a very simplified view of memory ordering, especially since no two CPUs order memory references in exactly the same way.

Quoted 8 lines

I think that Oleg's question:

Quoted 3 lines

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) ?

is really just about the timeliness with which writes before a smp_mb() become visible to other CPUs. Does Linux run on architectures in which writes are not propagated in a timely manner (that is: other CPUs can read stale values for a "considerable" time)? I rather doubt it.

Remember that smp_mb() is officially about controlling the order in which values are communicated between the CPU executing the smp_mb() and the interconnect, -not- between a pair of CPUs. In the general case (which includes Alpha), controlling the order in which values are communicated from one CPU to another requires that -both- CPUs execute memory barriers.

Quoted 2 lines

But with a proviso to my answer: the compiler will happily hoist reads out of loops. So writes won't necessarily get read in a timely manner.

Very good!

And this is in fact why smp_wmb() and friends also contain must directives instructing the compiler not to mess with ordering.

Thanx, Paul

#14 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

In reply to Andrew James Wade
Quoted 3 lines · Andrew James Wade

What does it mean for a write to start? For that matter, what does it mean for a write to complete?

wmb() or smp_smb() really makes no guarantees when a write completes (e.g. when another CPU or a device sees the new value) It just guarantees ordering. This means when you do e.g.

        *p = 1;
        wmb();
        *p = 2;
        wmb();

then another CPU will never see 2 before 1 (but possibly it might miss the "1 state completely"). When it actually sees the values (or if it keeps using whatever value was in *p before the first assignment) is undefined.

The definition quoted above is wrong I think. Rusty can you perhaps fix it up?

Quoted 5 lines

I think my focusing on the hardware details (of which I am woefully ignorant) was a mistake: the hardware can really do whatever it wants so long as it implements the expected abstract machine model, and it is ordering that matters in that model. So it makes sense that ordering, not time, is what the definitions of the memory barriers focus on.

Exactly.

Quoted 10 lines
Quoted 3 lines

Does this mb() garantees that the new value of ->cur will be visible
on other cpus immediately after smp_sees 1 or 2 is undefined. mb() (so that rcu_pending() will notice it) ?

is really just about the timeliness with which writes before a smp_mb() become visible to other CPUs. Does Linux run on architectures in which writes are not propagated in a timely manner (that is: other CPUs can read stale values for a "considerable" time)? I rather doubt it.

But with a proviso to my answer: the compiler will happily hoist reads out of loops. So writes won't necessarily get read in a timely manner.

Or just consider interrupts. Any CPU can stop for an very long time at any time as seen by the other CPUs. Or it might take an machine check and come back. You can never make any assumptions about when another CPU sees a write unless you add explicit synchronization like a spinlock.

-Andi

#15 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 14 lines · Andi Kleen
Quoted 3 lines · Andrew James Wade

What does it mean for a write to start? For that matter, what does it mean for a write to complete?

wmb() or smp_smb() really makes no guarantees when a write completes (e.g. when another CPU or a device sees the new value) It just guarantees ordering. This means when you do e.g.

        *p = 1;
        wmb();
        *p = 2;
        wmb();
Quoted 4 lines

then another CPU will never see 2 before 1 (but possibly it might miss the "1 state completely"). When it actually sees the values (or if it keeps using whatever value was in *p before the first assignment) is undefined.

It is OK on the write side, but the corresponding barriers are required on the read side (even on non-Alpha CPUs, since the value of the pointer remains constant).

	Writer			Reader

	p = 1;			p1 = p;
	smp_wmb();		smp_rmb();
	p = 2;			p2 = p;

With these memory barriers in place, if p2 is set to 1, then p1 must also be set to 1. Similarly, if p1 is set to 2, then p2 must also be set to 2. If the smp_rmb() is not present on the read side, then the reading CPU (and compiler) are free to interchange the order of the two assignment statements. As Andi says, memory barriers do not necessarily make reads or writes happen faster, instead they only enforce limited ordering constraints.

If the variable p references MMIO rather than normal memory, then wmb() and rmb() are needed instead of smp_wmb() and smp_rmb(). This is because the I/O device needs to see the accesses ordered even in a UP system.

Thanx, Paul

Quoted 29 lines

The definition quoted above is wrong I think. Rusty can you perhaps fix it up?

Quoted 5 lines

I think my focusing on the hardware details (of which I am woefully ignorant) was a mistake: the hardware can really do whatever it wants so long as it implements the expected abstract machine model, and it is ordering that matters in that model. So it makes sense that ordering, not time, is what the definitions of the memory barriers focus on.

Exactly.

Quoted 10 lines
Quoted 3 lines

Does this mb() garantees that the new value of ->cur will be visible
on other cpus immediately after smp_sees 1 or 2 is undefined. mb() (so that rcu_pending() will notice it) ?

is really just about the timeliness with which writes before a smp_mb() become visible to other CPUs. Does Linux run on architectures in which writes are not propagated in a timely manner (that is: other CPUs can read stale values for a "considerable" time)? I rather doubt it.

But with a proviso to my answer: the compiler will happily hoist reads out of loops. So writes won't necessarily get read in a timely manner.

Or just consider interrupts. Any CPU can stop for an very long time at any time as seen by the other CPUs. Or it might take an machine check and come back. You can never make any assumptions about when another CPU sees a write unless you add explicit synchronization like a spinlock.

-Andi

#16 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 2 lines · Paul E. McKenney

If the variable p references MMIO rather than normal memory, then wmb() and rmb() are needed instead of smp_wmb() and smp_rmb().

mmiowb(), not wmb(). IA64 has a different form of memory fence for I/O space compared to normal memory. MIPS also has a non-empty form of mmiowb().

Quoted 2 lines

This is because the I/O device needs to see the accesses ordered even in a UP system.

Why does mmiowb() map to empty on most systems, including Alpha? Should it not map to wmb() for everything except IA64 and MIPS?

#17 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 8 lines · Keith Owens
Quoted 2 lines · Paul E. McKenney

If the variable p references MMIO rather than normal memory, then wmb() and rmb() are needed instead of smp_wmb() and smp_rmb().

mmiowb(), not wmb(). IA64 has a different form of memory fence for I/O space compared to normal memory. MIPS also has a non-empty form of mmiowb().

New one on me!

Quoted 5 lines
Quoted 2 lines

This is because the I/O device needs to see the accesses ordered even in a UP system.

Why does mmiowb() map to empty on most systems, including Alpha? Should it not map to wmb() for everything except IA64 and MIPS?

Sounds like I am not the only one that it is new to...

There are over four hundred instances of wmb() still in the drivers tree in 2.6.14. I suspect that most of them are for MMIO fencing -- the ones I looked at quickly certainly seem to be.

But, given mmiowb(), what is the point of having wmb()? Why are write memory barriers needed in UP kernels if not for MMIO and other hardware-specific accesses? Is your thought that use of wmb() should be phased out in favor of mmiowb()? (Might be a good idea, but doesn't look like we are there yet.)

Thanx, Paul

#18 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 11 lines · Paul E. McKenney
Quoted 8 lines · Keith Owens
Quoted 2 lines · Paul E. McKenney

If the variable p references MMIO rather than normal memory, then wmb() and rmb() are needed instead of smp_wmb() and smp_rmb().

mmiowb(), not wmb(). IA64 has a different form of memory fence for I/O space compared to normal memory. MIPS also has a non-empty form of mmiowb().

New one on me!

Didn't it make only a difference on the Altix or something like that? I suppose they added it only on the drivers for devices supported by SGI.

-Andi

#19 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 7 lines · Andi Kleen
Quoted 6 lines · Paul E. McKenney
Quoted 5 lines · Keith Owens
Quoted 2 lines · Paul E. McKenney

If the variable p references MMIO rather than normal memory, then wmb() and rmb() are needed instead of smp_wmb() and smp_rmb().

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

mmiowb(), not wmb(). IA64 has a different form of memory fence for I/O space compared to normal memory. MIPS also has a non-empty form of mmiowb().

New one on me!

Didn't it make only a difference on the Altix or something like that? I suppose they added it only on the drivers for devices supported by SGI.

It could potentially help on a few other CPUs, but quite a few driver changes would be needed to really bring out the full benefits. I am concerned that the current state leaves a number of CPU families broken -- the empty definitions cannot be good for other weakly ordered CPUs!

Thanx, Paul

#20 lore raw

Re: Semantics of smp_mb()

In reply to Keith Owens

Keith> Why does mmiowb() map to empty on most systems, including Keith> Alpha? Should it not map to wmb() for everything except Keith> IA64 and MIPS?

I think the intention (as spelled out in Documentation/DocBook/deviceiobook.tmpl) is that mmiowb() must be used in conjunction with spinlocks or some other SMP synchronization mechanism. The locks themselves are sufficient ordering on the archs where mmiowb() is a NOP.

One way of thinking about this is that the usually barrier operations like wmb() affect the order of a single CPU's operations -- that is, wmb() is saying that all writes from the current thread of execution before the wmb() become visible before any of the writes from the current after the wmb(). But wmb() doesn't say anything about how one CPU's writes are ordered against anything a different CPU does.

mmiowb() is something else -- it controls the visibility of writes from different CPUs. It says that all writes before the mmiowb() become visible before any writes from any CPU after the mmiowb(). However, this isn't sensible unless we can order the writes between CPUs, and that only makes sense if there's a lock that lets us say that one CPU is executing something after the mmiowb().

- R.

#21 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

In reply to Keith Owens

Roland Dreier got this right. The purpose of the mmiowb is to ensure that writes to I/O devices while holding a spinlock are ordered with respect to writes issued after the original processor releases and a second processor acquires said spinlock.

A MMIO read would be sufficient, but is much heavier weight.

On the SGI MIPS-based systems, the "sync" instruction was used. On the Altix systems, a register on the hub chip is read.

Quoted 1 line

From comments by jejb, we're looking at modifying the mmiowb

API by adding an argument which would be a register to read from if the architecture in question needs ordering in this way but does not have a lighter weight mechanism like the Altix mmiowb. Since there will now need to be a width indication, mmiowb will be replaced with mmiowb[bwlq].

jeremy

#22 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 11 lines · Jeremy Higdon

Roland Dreier got this right. The purpose of the mmiowb is to ensure that writes to I/O devices while holding a spinlock are ordered with respect to writes issued after the original processor releases and a second processor acquires said spinlock.

A MMIO read would be sufficient, but is much heavier weight.

On the SGI MIPS-based systems, the "sync" instruction was used. On the Altix systems, a register on the hub chip is read.

Quoted 6 lines
Quoted 1 line

From comments by jejb, we're looking at modifying the mmiowb

API by adding an argument which would be a register to read from if the architecture in question needs ordering in this way but does not have a lighter weight mechanism like the Altix mmiowb. Since there will now need to be a width indication, mmiowb will be replaced with mmiowb[bwlq].

Any progress on this front? I figured that I would wait to update the ordering document until after this change happened, but if it is going to be awhile, I should proceed with the current API.

Thoughts?

Thanx, Paul

#23 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 19 lines · Paul E. McKenney
Quoted 11 lines · Jeremy Higdon

Roland Dreier got this right. The purpose of the mmiowb is to ensure that writes to I/O devices while holding a spinlock are ordered with respect to writes issued after the original processor releases and a second processor acquires said spinlock.

A MMIO read would be sufficient, but is much heavier weight.

On the SGI MIPS-based systems, the "sync" instruction was used. On the Altix systems, a register on the hub chip is read.

Quoted 6 lines
Quoted 1 line

From comments by jejb, we're looking at modifying the mmiowb

API by adding an argument which would be a register to read from if the architecture in question needs ordering in this way but does not have a lighter weight mechanism like the Altix mmiowb. Since there will now need to be a width indication, mmiowb will be replaced with mmiowb[bwlq].

Quoted 7 lines

Any progress on this front? I figured that I would wait to update the ordering document until after this change happened, but if it is going to be awhile, I should proceed with the current API.

Thoughts?

Thanx, Paul

Brent Casavant was going to be working on this. I'll CC him so that he can indicate the status.

jeremy

#24 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

Quoted 20 lines · Jeremy Higdon
Quoted 19 lines · Paul E. McKenney
Quoted 17 lines · Jeremy Higdon

Roland Dreier got this right. The purpose of the mmiowb is to ensure that writes to I/O devices while holding a spinlock are ordered with respect to writes issued after the original processor releases and a second processor acquires said spinlock.

A MMIO read would be sufficient, but is much heavier weight.

On the SGI MIPS-based systems, the "sync" instruction was used. On the Altix systems, a register on the hub chip is read.

Quoted 1 line

From comments by jejb, we're looking at modifying the mmiowb

API by adding an argument which would be a register to read from if the architecture in question needs ordering in this way but does not have a lighter weight mechanism like the Altix mmiowb. Since there will now need to be a width indication, mmiowb will be replaced with mmiowb[bwlq].

Quoted 8 lines
Quoted 5 lines

Any progress on this front? I figured that I would wait to update the ordering document until after this change happened, but if it is going to be awhile, I should proceed with the current API.

Thoughts?

Brent Casavant was going to be working on this. I'll CC him so that he can indicate the status.

David Howells is documenting memory barriers in the Documentation directory as well.

Thanx, Paul

#25 lore raw

Re: Semantics of smp_mb() [was : Re: [PATCH] Fix RCU race in access of nohz_cpu_mask ]

In reply to Jeremy Higdon

[Unknown author]

Quoted 10 lines
Quoted 10 lines
Quoted 6 lines

From comments by jejb, we're looking at modifying the mmiowb API by adding an argument which would be a register to read from if the architecture in question needs ordering in this way but does not have a lighter weight mechanism like the Altix mmiowb. Since there will now need to be a width indication, mmiowb will be replaced with mmiowb[bwlq].

Any progress on this front? I figured that I would wait to update the ordering document until after this change happened, but if it is going to be awhile, I should proceed with the current API.

I avoided doing this initially on the premise that I shouldn't do things 'just because we might need it in the future' since that way seems to lead to madness. Is there actual hardware that needs an argument to mmiowb() (i.e. that can't just do a read from the system's single bridge or something)?

Jesse

#26 lore raw
In reply to Oleg Nesterov
Quoted 16 lines · Oleg Nesterov
Quoted 15 lines · Srivatsa Vaddagiri
Quoted 9 lines · Oleg Nesterov
Quoted 3 lines
        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:

Quoted 8 lines
Quoted 3 lines

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.

Quoted 1 line
Quoted 1 line

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

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

Quoted 2 lines

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

#27 lore raw

Review

Quoted 13 lines · Paul E. McKenney

1. wmb() guarantees that any writes preceding the wmb() will

(quoted diff) +0 -0
 	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.

#28 lore raw

From: Andrew Morton <[email protected]>
Date: Sun, 11 Dec 2005 20:32:26 -0800

Quoted 4 lines

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.

#29 lore raw
Quoted 10 lines · David S. Miller

From: Andrew Morton <[email protected]>
Date: Sun, 11 Dec 2005 20:32:26 -0800

Quoted 4 lines

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.

Quoted 8 lines

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 :)

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#30 lore raw
In reply to Andrew Morton
Quoted 4 lines · Andrew Morton

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.

#31 lore raw
In reply to Andrew Morton
Quoted 13 lines · Andrew Morton
Quoted 12 lines · Paul E. McKenney

1. wmb() guarantees that any writes preceding the wmb() will

(quoted diff) +0 -0
 	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.
Quoted 6 lines
Quoted 1 line

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.

#32 lore raw
In reply to Oleg Nesterov
Quoted 2 lines · Oleg Nesterov

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.

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