Skip to contentSkip to conversation

Uses for memory barriers

DISCUSSION Alan Stern 5 participants 21 messages Sep 8, 2006 – Sep 12, 2006 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Alan Stern

author
#1 lore raw
Quoted 9 lines · Oliver Neukum

It seems you are correct.
Therefore the correct code on CPU 1 would be:

y = -1;
b = 1;
//mb();
//x = a;
while (y < 0) relax();

Quoted 6 lines

mb();
x = a;

assert(x==1 || y==1); //???

And yes, it is confusing. I've been forced to change my mind twice.

Again you have misunderstood. The original code was _not_ incorrect. I was asking: Given the code as stated, would the assertion ever fail?

The code _was_ correct for my purposes, namely, to illustrate a technical point about the behavior of memory barriers.

Alan

#2 lore raw

Am Freitag, 8. September 2006 23:26 schrieb Alan Stern:

Quoted 14 lines · Oliver Neukum
Quoted 13 lines

It seems you are correct.
Therefore the correct code on CPU 1 would be:

y = -1;
b = 1;
//mb();
//x = a;
while (y < 0) relax();

mb();
x = a;

Quoted 6 lines
Quoted 3 lines

assert(x==1 || y==1); //???

And yes, it is confusing. I've been forced to change my mind twice.

Again you have misunderstood. The original code was _not_ incorrect. I was asking: Given the code as stated, would the assertion ever fail?

I claim the right to call code that fails its own assertions incorrect. :-)

Quoted 2 lines

The code _was_ correct for my purposes, namely, to illustrate a technical point about the behavior of memory barriers.

I would say that the code may fail the assertion purely based on the formal definition of a memory barrier. And do so in a subtle and inobvious way.

Regards
Oliver

author
#3 lore raw
Quoted 4 lines · Oliver Neukum
Quoted 2 lines

Again you have misunderstood. The original code was _not_ incorrect. I was asking: Given the code as stated, would the assertion ever fail?

I claim the right to call code that fails its own assertions incorrect. :-)

Touche!

Quoted 6 lines
Quoted 2 lines

The code _was_ correct for my purposes, namely, to illustrate a technical point about the behavior of memory barriers.

I would say that the code may fail the assertion purely based on the formal definition of a memory barrier. And do so in a subtle and inobvious way.

But what _is_ the formal definition of a memory barrier? I've never seen one that was complete and correct.

Alan Stern

#4 lore raw

Am Samstag, 9. September 2006 00:25 schrieb Alan Stern:

Quoted 12 lines · Oliver Neukum
Quoted 5 lines
Quoted 3 lines

Again you have misunderstood. The original code was _not_ incorrect. I was asking: Given the code as stated, would the assertion ever fail?

I claim the right to call code that fails its own assertions incorrect. :-)

Touche!

Quoted 3 lines
Quoted 2 lines

The code _was_ correct for my purposes, namely, to illustrate a technical point about the behavior of memory barriers.

Quoted 6 lines
Quoted 3 lines

I would say that the code may fail the assertion purely based on the formal definition of a memory barrier. And do so in a subtle and inobvious way.

But what _is_ the formal definition of a memory barrier? I've never seen one that was complete and correct.

I' d say "mb();" is "rmb();wmb();"

and they work so that:

CPU 0

a = TRUE;
wmb();
b = TRUE;

CPU 1

if (b) {
	rmb();
	assert(a);
}

is correct. Possibly that is not a complete definition though.

Regards
Oliver

author
#5 lore raw
Quoted 13 lines · Oliver Neukum
Quoted 2 lines

But what _is_ the formal definition of a memory barrier? I've never seen one that was complete and correct.

I' d say "mb();" is "rmb();wmb();"

and they work so that:

CPU 0

a = TRUE;
wmb();
b = TRUE;

Quoted 8 lines

CPU 1

if (b) {
	rmb();
	assert(a);
}

is correct. Possibly that is not a complete definition though.

It isn't. Paul has agreed that this assertion:

	CPU 0				CPU 1
	-----				-----
	while (x == 0) relax();		x = -1;
	x = a;				y = b;
	mb();				mb();
	b = 1;				a = 1;
					while (x < 0) relax();
					assert(x==0 || y==0);

will not fail. I think this would not be true if either of the mb() statements were replaced with {rmb(); wmb();}.

To put it another way, {rmb(); wmb();} guarantees that any preceding read will complete before any following read and any preceding write will complete before any following write. However it does not guarantee that any preceding read will complete before any following write, whereas mb() does guarantee that. (To whatever extent these statements make sense.)

Alan

#6 lore raw
Quoted 35 lines · Alan Stern
Quoted 13 lines · Oliver Neukum
Quoted 2 lines

But what _is_ the formal definition of a memory barrier? I've never seen one that was complete and correct.

I' d say "mb();" is "rmb();wmb();"

and they work so that:

CPU 0

a = TRUE;
wmb();
b = TRUE;

Quoted 8 lines

CPU 1

if (b) {
	rmb();
	assert(a);
}

is correct. Possibly that is not a complete definition though.

It isn't. Paul has agreed that this assertion:

	CPU 0				CPU 1
	-----				-----
	while (x == 0) relax();		x = -1;
	x = a;				y = b;
	mb();				mb();
	b = 1;				a = 1;
					while (x < 0) relax();
					assert(x==0 || y==0);
Quoted 8 lines

will not fail. I think this would not be true if either of the mb() statements were replaced with {rmb(); wmb();}.

To put it another way, {rmb(); wmb();} guarantees that any preceding read will complete before any following read and any preceding write will complete before any following write. However it does not guarantee that any preceding read will complete before any following write, whereas mb() does guarantee that. (To whatever extent these statements make sense.)

This is a summary of the Linux memory-barrier semantics as I understand them:

1. A given CPU will always perceive its own memory operations
as occuring in program order.

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs. This is "coherence". (And this is the property that I was forgetting about when I first looked at your second example.)

3. A given type of memory barrier, when executed on a given CPU,
causes that CPU's prior accesses of the corresponding type to be perceived by other CPUs as having occurred before the given CPU's subsequent accesses of the corresponding type.

The types of memory barriers are rmb(), which segregates only reads, wmb(), which segregates only writes, and mb(), which segregates both. There is also mmiowb(), which is like wmb(), but gives additional ordering guarantees that extend to I/O busses, such as PCI bridges.

Alan is quite correct when he says that rmb();wmb(); is not necessarily equivalent to mb(). For example:

Sequence 1 Sequence 2

load A load A
store B store B
mb() rmb();wmb()
load C load C
store D store D

In sequence 1, other CPUs will see the load from A and the store to B both preceding the load from C and the store to D. In sequence 2, other CPUs might well see the store to D preceding the load from A, or, conversely, the store to B following the load from C. This second scenario might seem unlikely, but there is real hardware that has similar properties (e.g., ppc's separately ordering accesses to cached and to non-cached memory).

In all these cases, of course, these other CPUs would themselves be needing to use memory barriers to order their own accesses.

You guys asked!!!

Thanx, Paul

author
#7 lore raw
Quoted 10 lines · Paul E. McKenney

This is a summary of the Linux memory-barrier semantics as I understand them:

1. A given CPU will always perceive its own memory operations
as occuring in program order.

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs. This is "coherence". (And this is the property that I was forgetting about when I first looked at your second example.)

...

This can't be right. Together 1 and 2 would obviate the need for wmb(). The CPU doing "STORE A; STORE B" will always see the operations occuring in program order by 1, and hence every other CPU would always see them occurring in the same order by 2 -- even without wmb().

Either 2 is too strong, or else what you mean by "perceived" isn't sufficiently clear.

Alan Stern

#8 lore raw
Quoted 7 lines

This can't be right. Together 1 and 2 would obviate the need for wmb(). The CPU doing "STORE A; STORE B" will always see the operations occuring in program order by 1, and hence every other CPU would always see them occurring in the same order by 2 -- even without wmb().

Either 2 is too strong, or else what you mean by "perceived" isn't sufficiently clear.

2. is only for multiple stores to a _single_ memory location -- you use wmb() to order stores to _separate_ memory locations.

Segher

#9 lore raw
Quoted 7 lines · Segher Boessenkool
Quoted 7 lines

This can't be right. Together 1 and 2 would obviate the need for wmb().
The CPU doing "STORE A; STORE B" will always see the operations occuring
in program order by 1, and hence every other CPU would always see them occurring in the same order by 2 -- even without wmb().

Quoted 5 lines
Quoted 2 lines

Either 2 is too strong, or else what you mean by "perceived" isn't sufficiently clear.

2. is only for multiple stores to a _single_ memory location -- you use wmb() to order stores to _separate_ memory locations.

Precisely!!!

Thanx, Paul

#10 lore raw
In reply to Alan Stern
Quoted 12 lines · Alan Stern
Quoted 10 lines · Paul E. McKenney

This is a summary of the Linux memory-barrier semantics as I understand them:

1. A given CPU will always perceive its own memory operations
as occuring in program order.

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs. This is "coherence". (And this is the property that I was forgetting about when I first looked at your second example.)

Quoted 6 lines

...

This can't be right. Together 1 and 2 would obviate the need for wmb(). The CPU doing "STORE A; STORE B" will always see the operations occuring in program order by 1, and hence every other CPU would always see them occurring in the same order by 2 -- even without wmb().

Not so. A and B are different memory locations, hence #2 does not apply to the "STORE A; STORE B" sequence.

Quoted 2 lines

Either 2 is too strong, or else what you mean by "perceived" isn't sufficiently clear.

The key phrase is "to a given -single- memory location". ;-)

A and B are presumably -different- memory locations. However, if A and B are aliases for the same memory location, then the wmb() would in fact be unnecessary. But, again, I am assuming that they are different, so that #2 does not apply.

Thanx, Paul

#11 lore raw
In reply to Paul E. McKenney
Quoted 2 lines

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

All CPUs that _do_ see two stores to the same memory location happening, will see them occurring in the same order -- not all CPUs seeing a later store will necessarily see the earlier stores.

Segher

#12 lore raw
In reply to Paul E. McKenney

Am Montag, 11. September 2006 18:21 schrieb Paul E. McKenney:

Quoted 2 lines

1.      A given CPU will always perceive its own memory operations as occuring in program order.

Is this true for physical memory if virtually indexed caches are involved?

Regards
Oliver

#13 lore raw
Quoted 6 lines · Oliver Neukum

Am Montag, 11. September 2006 18:21 schrieb Paul E. McKenney:

Quoted 2 lines

1.      A given CPU will always perceive its own memory operations as occuring in program order.

Is this true for physical memory if virtually indexed caches are involved?

As I understand it, in systems with virtually indexed caches, the OS must take care to ensure that a given cacheline appears only once in the cache, even if it is mapped to multiple virtual addresses. If an OS failed to do this, then, as far as I can see, all bets are off. Curt Schimmel's book "UNIX(R) Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers" is an excellent guide to the issues posed by virtually indexed and virtually tagged caches.

In principle, one could construct a virtually indexed/tagged CPU cache that automatically ejected any line with a conflicting physical address (given that lookups are presumably much more frequent than loading new cache lines), but I have no idea if any real hardware takes this approach. I have had the good fortune to always work with physically tagged/indexed caches. ;-)

Thanx, Paul

#14 lore raw
In reply to Paul E. McKenney
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

David

#15 lore raw

Am Dienstag, 12. September 2006 11:01 schrieb David Howells:

Quoted 10 lines
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

Does it make sense? If you do:
mov #x, $a
wmb
mov #y, $b
wmb
mov #z, $a

The CPU must not discard any write. If you do

mov #x, $a
mov #y, $b
wmb
mov #z, $a

The first store to $a is superfluous if you have only inter-CPU issues in mind.

Regards
Oliver

#16 lore raw
Quoted 21 lines · Oliver Neukum

Am Dienstag, 12. September 2006 11:01 schrieb David Howells:

Quoted 10 lines
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

Does it make sense? If you do:
mov #x, $a
wmb
mov #y, $b
wmb
mov #z, $a

The CPU must not discard any write. If you do

Quoted 7 lines

mov #x, $a
mov #y, $b
wmb
mov #z, $a

The first store to $a is superfluous if you have only inter-CPU issues in mind.

In both cases, the CPU might "discard" the write, if there are no intervening reads or writes to the same location. The only difference between your two examples is the ordering of the first store to $a and the store to $b. In your first example, other CPUs must see the first store to $a as happening first, while in your second example, other CPUs might see the store to $b as happening first.

Thanx, Paul

#17 lore raw

Am Dienstag, 12. September 2006 16:55 schrieb Paul E. McKenney:

Quoted 27 lines · Oliver Neukum
Quoted 26 lines

Am Dienstag, 12. September 2006 11:01 schrieb David Howells:

Quoted 10 lines
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

Does it make sense? If you do:
mov #x, $a
wmb
mov #y, $b
wmb
mov #z, $a

The CPU must not discard any write. If you do

mov #x, $a
mov #y, $b
wmb
mov #z, $a

Quoted 5 lines
Quoted 2 lines

The first store to $a is superfluous if you have only inter-CPU issues in mind.

In both cases, the CPU might "discard" the write, if there are no intervening reads or writes to the same location. The only difference between your

How can it know that?

Quoted 4 lines

two examples is the ordering of the first store to $a and the store to $b. In your first example, other CPUs must see the first store to $a as happening first, while in your second example, other CPUs might see the store to $b as happening first.

There's no way in the second case a CPU might tell whether the first write ever happened.

Regards
Oliver

#18 lore raw
Quoted 28 lines · Oliver Neukum

Am Dienstag, 12. September 2006 16:55 schrieb Paul E. McKenney:

Quoted 27 lines · Oliver Neukum
Quoted 26 lines

Am Dienstag, 12. September 2006 11:01 schrieb David Howells:

Quoted 10 lines
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

Does it make sense? If you do:
mov #x, $a
wmb
mov #y, $b
wmb
mov #z, $a

The CPU must not discard any write. If you do

mov #x, $a
mov #y, $b
wmb
mov #z, $a

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

The first store to $a is superfluous if you have only inter-CPU issues in mind.

In both cases, the CPU might "discard" the write, if there are no intervening reads or writes to the same location. The only difference between your

How can it know that?

If the CPU starts off owning both cache lines, and if there are no intervening invalidation requests from other CPUs, then the writing CPU knows that there could not possibly have been any intervening writes.

Quoted 7 lines
Quoted 4 lines

two examples is the ordering of the first store to $a and the store to $b. In your first example, other CPUs must see the first store to $a as happening first, while in your second example, other CPUs might see the store to $b as happening first.

There's no way in the second case a CPU might tell whether the first write ever happened.

With one important exception -- the CPU that did the write knows. There is no requirement that each and every CPU see each and every write. The only requirement is that the sequence of values that each CPU sees for a single given variable is consistent with that of each other CPU.

Thanx, Paul

#19 lore raw
In reply to Oliver Neukum
Quoted 4 lines
Quoted 2 lines

In both cases, the CPU might "discard" the write, if there are no intervening reads or writes to the same location. The only difference between your

How can it know that?

Because it holds the cache line in the "O" (owned) state, for example.

And it doesn't matter how a CPU would do this; the only thing that matters is that you do not assume anything that is not guaranteed by the model.

Segher

#20 lore raw
In reply to David Howells
Quoted 7 lines · David Howells
Quoted 2 lines · Paul E. McKenney

2. All stores to a given single memory location will be perceived
as having occurred in the same order by all CPUs.

Does that take into account a CPU combining or discarding coincident memory operations?

I believe so.

Quoted 2 lines

For instance, a CPU asked to issue two writes to the same location may discard the first if it hasn't done it yet.

If I understand your example correctly, in that case, all CPUs would agree that the given CPU's stores happened consecutively. Yes, they might not see the intermediate value, but their view of the sequence of values would be consistent with the given CPU's pair of stores having happened at a specific place in the sequence of values.

This is not peculiar to this situation -- consider the following:

	CPU 0		CPU 1		CPU 2		CPU 3

	A=1
			Q1=A				Q3=A
					A=2
							A=3
			Q2=A				Q4=A

None of the CPUs saw CPU 2's first assignment A=2, but all of their reads are consistent with the 1,2,3 sequence of values. Your example (if I understand it correctly) is simply a special case where the pair of assignments happened on a single CPU.

Thanx, Paul

#21 lore raw
In reply to Alan Stern

I'd state it as:

mb() _implies_ both rmb() and wmb(), but is more complete than both since it _also_ partially orders reads and writes with respect to each other.

David