Memory Barrier Definitions

Hi,

I have been working through a number of issues that became significant on Power4 based systems, and wanted to start some discussion to understand which other platforms are impacted in a similar way.

The fundamental issue is that Power4 is weakly consistent and the PowerPC architecture definitions for memory reference ordering do not necessarily mesh well with the current Linux barrier primitive use. Obviously, we are not the only weakc platform, but I suspect the degree and latencies we see push things more than most systems. What is less clear to me is how much PPC memory barrier symantics have in common with other systems; presumably there are some which are similar.

As a specific example, on PowerPC the following memory barriers are defined:

eieio: Orders all I/O references & store/store to system memory, but seperatly
lwsync: Orders load/load, store/store, and load/store, only to system memory
sync: Orders everything

In terms of cycles, eieio is relatively cheap, lwsync is perhaps 100's, while sync is measured in the 1000's. The key is that only a sync orders both system memory and I/O space references and it is very expensive, so it should only be used where absolutely necessary, like in a driver.

Linux defines (more or less) the following barriers:
mb, rmb, wmb, smp_mb, smp_wmb, smp_rmb

An example of where these primitives get us into trouble is the use of wmb() to order two stores which are only to system memory (where a lwsync would do for ppc64) and for a store to system memory followed by a store to I/O (many examples in drivers). Here ppc64 requires a sync. Therefore we must always pay the high price and use a sync for wmb().

A solution was pointed out by Rusty Russell that we should probabily be using smp_*mb() for system memory ordering and reserve the *mb() calls for when ordering against I/O is also required. There does seem to be some limited cases where this has been done, but in general *mb() are used in most parts of the kernel.

Any thoughts if making better use of the smp_* macros would be the right approach?

Thanks -

Dave Engebretsen

For pure compiler level ordering we have barrier()

Alan

Sure, but none of these issues I think need disscussion are a compiler reordering. Perhaps you are just pointing out another barrier primitive to provide a more complete listing? There are some others, such as the *before_atomic* that will require a seperate discussion, I think.

In case my point was not clear, I'll restate: where PowerPC (at a minimum) gets into trouble is with the seperate ordering between references to system memory and to I/O space with respect to the various forms of processor memory barrier instructions. It is _very_ expensive to blindly force all memory references to be ordered completely to the seperate spaces. The use of wmb(), rmb(), and mb() is overloaded in the context of PowerPC.

Dave.

I think I follow

You have

Compiler ordering
CPU v CPU memory ordering
CPU v I/O memory ordering
I/O v I/O memory ordering

and our current heirarchy is a little bit more squashed than that. I'd agree. We actually hit a corner case of this on the IDT winchip x86 where we run relaxed store ordering and have to define wmb() as a locked add of zero to the top of stack - which does have a penalty that isnt needed for CPU ordering.

How much of this impacts Mips64 ?

Alan

In terms of the MIPS{32|64} ISA, the current primitives seem fine; there's only 1 option defined in the ISA: 'sync'. Order for all off-cache accesses is guaranteed around a sync.

It gets a bit more complicated when you talk about what particular implementations do, and ordering rules for uncached vs cached accesses, but to the best of my knowledge there aren't any fundamental problems as described for the PPC.

-Justin

PPC also guarantees every ordering when using the 'sync' instruction, so that will give correctness at the price of a 1000 cycles or so. You refer to different rules for cached vs uncached on other implementations -- that is the essence of our problem. Are there different barrier instructions in MIPS which provide different levels of performance for different ordering enforcements?

Dave.

No, there aren't. The implementation details can affect which primitives need to explicitly sync, though.

For instance, the BRCM1250 makes some guarantees about visibility of uncached writes that aren't strictly required by the architecture spec.

-Justin

I am curious what the definition of memory barriers is for IA64, Sparc, and x86-64.

to the existing mb, wmb, and rmb semantics, incluing ordering between system memory and I/O space. Is that an accurate assesment?

IA64 has both the mf and mf.a instructions, one for system memory the other for I/O space. What is required for ordering of references between the spaces? That is not clear to me looking at the ia64 headers.

Thanks for any input -

Dave.

Dave> I am curious what the definition of memory barriers is for Dave> IA64, Sparc, and x86-64.

I'm not sure it's enough to look just at the memory barriers. The barriers only make sense within the memory ordering model defined for each architecture. For ia64, this is defined in Section 4.4.7 of the System Architecture Guide, which is available at:

http://developer.intel.com/design/itanium/downloads/24531803s.htm

Dave> From what I can tell, sparc and x86-64 are like alpha and map Dave> directly
Dave> to the existing mb, wmb, and rmb semantics, incluing ordering Dave> between system memory and I/O space. Is that an accurate Dave> assesment?

Dave> IA64 has both the mf and mf.a instructions, one for system Dave> memory the other for I/O space.

The ia64 memory ordering model is quite orthogonal to the one that Linux uses (which is based on the Alpha instructions): Linux distinguishes between read and write memory barriers. ia64 uses an acquire/release model instead. An acquire orders all *later* memory accesses and a release orders all *earlier* accesses (regardless of whether they are reads or writes). Another difference is that the acquire/release semantics is attached to load/store instructions, respectively. This means that in an ideal world, ia64 would rarely need to use the memory barrier instruction.

Now, finding a way to abstract all the differences accross architectures in a way that's easy to use and allows for optimal implementation on each architecture may not be easy. This problem also shows up with user-level thread libraries and I have had on and off discussions about this with Hans Boehm, but neither of us has really had time to work on it seriously. In truth, it is also the case that for Itanium and Itanium 2, the cost of "mf" is small enough that there hasn't been a huge need to get this exactly right. But when reworking the memory ordering model of Linux, it might just as well be taken into account.

Dave> What is required for ordering
Dave> of references between the spaces? That is not clear to me Dave> looking at the ia64 headers.

Look at Table 4-15 in the above document (on page 2-70). I/O space is simply a memory-mapped region that is mapped uncached. In the table, the row "Sequential" refers to uncached memory. The quick summary is that normal loads/stores to memory are not automatically ordered with respect to accesses to uncached memory.

I'm also discussing some of these issues in my book
(http://www.lia64.org/book/) in the Device I/O chapter, but the architecture manual mentioned above is of course the ultimate source if you want all the gory details.

	--david

Hmmm... could you explain more? You're saying that every load is an "acquire" and every store a "release"? Or that they can be flagged that way, but aren't always?

Does this means that an "acquire" means "all accesses after this insn (in the code stream) must occur after this insn (in time)"? Does that only apply to the address that instruction touched, or all?

Confused,
Rusty.

   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy

cc trimmed.

The IA64 default is unordered memory accesses, except for special instructions. From Intel IA-64 Architecture Software Developer's Manual. Volume 1: IA-64 Application Architecture.

4.4.7 Memory Access Ordering

Memory data access ordering must satisfy read-after-write (RAW), write-after-write (WAW), and write-after-read (WAR) data dependencies to the same memory location. In addition, memory writes and flushes must observe control dependencies. Except for these restrictions, reads, writes, and flushes may occur in an order different from the specified program order. Note that no ordering exists between instruction accesses and data accesses or between any two instruction accesses. The mechanisms described below are defined to enforce a particular memory access order. In the following discussion, the terms "previous" and "subsequent" are used to refer to the program specified order. The term "visible" is used to refer to all architecturally visible effects of performing a memory access (at a minimum this involves reading or writing memory).

Memory accesses follow one of four memory ordering semantics:
unordered, release, acquire or fence. Unordered data accesses may become visible in any order. Release data accesses guarantee that all previous data accesses are made visible prior to being made visible themselves. Acquire data accesses guarantee that they are made visible prior to all subsequent data accesses. Fence operations combine the release and acquire semantics into a bi-directional fence, i.e. they guarantee that all previous data accesses are made visible prior to any subsequent data accesses being made visible.

Explicit memory ordering takes the form of a set of instructions:
ordered load and ordered check load (ld.acq, ld.c.clr.acq), ordered store (st.rel), semaphores (cmpxchg, xchg, fetchadd), and memory fence (mf). The ld.acq and ld.c.clr.acq instructions follow acquire semantics. The st.rel follows release semantics. The mf instruction is a fence operation. The xchg, fetchadd.acq, and cmpxchg.acq instructions have acquire semantics. The cmpxchg.rel, and fetchadd.rel instructions have release semantics. The semaphore instructions also have implicit ordering. If there is a write, it will always follow the read. In addition, the read and write will be performed atomically with no intervening accesses to the same memory region.

Rusty> On Wed, 8 May 2002 10:07:08 -0700 David Mosberger

Rusty> Hmmm... could you explain more? You're saying that every Rusty> load is an "acquire" and every store a "release"? Or that Rusty> they can be flagged that way, but aren't always?

The latter: loads can have "acquire" semantics and stores can have "release" semantics. For example, at the assembly level, ld8.acq would be an 8-byte load with acquire semantics, st8.rel an 8-byte store with release semantics. At the C level, acquire/release semantics is used for all accesses to "volatile" variables.

One way to think of all this is that using .acq/.rel for *all* memory accesses will give you a memory model that exactly matches that of a Pentium III.

Rusty> Does this means that an "acquire" means "all accesses after Rusty> this insn (in the code stream) must occur after this insn (in Rusty> time)"?

Yes.

Rusty> Does that only apply to the address that instruction Rusty> touched, or all?

No, the address doesn't matter (data dependencies are always honored).

	--david

OK. So ignoring the fact that you somehow have to attach your barriers to a load or store for the moment, we have before vs. after (ia64), read vs. write (most archs), io vs mem (ppc, ppc64), data dependency vs non-data dependency (alpha), and smp vs up.

{read|write|readwrite} \
	_{before|after|bidir} \
		_{io|mem|iomem} \
			_{dd|nondd} \
				_{smp|nonsmp}

Now, I think the non-data-depends case is so common that it doesn't belong in the name at all, but as a separate macro:

#ifndef __alpha__
	#define data_depends(barrier) (barrier)
#else
	#define data_depends(barrier) (ddep_##barrier)

#endif

Also, assuming that no data dependency on normal memory where it doesn't matter on UP is the default, we can elide those. Also, any barrier mentioning IO can be assumed to be in force even if UP, so those combinations are invalid. Note that UP with CONFIG_PREEMPT counts as SMP here:

	/* Complete all reads from normal memory before any normal
	   memory reads ;which follow this instruction, on SMP or PREEMPT */
	read_before();

	/* Do not begin any reads from normal memory which follow,
	   before any normal reads which preceed this instruction are
	   complete, on SMP or PREEMPT */
	read_after();

	/* read_before(); read_after(); */
	read_bidir();

	/* Complete all reads from IO before any IO reads which follow
	   this instruction. */
	read_before_io();

	/* Complete all reads (IO or memory) before any reads which follow
	   this instruction. */
	read_before_iomem();

	/* Do not begin any IO reads which follow, before any IO reads
	   which preceed this instruction are complete. */
	read_after_io();

	/* Do not begin any reads (IO or memory) which follow, before any
	   reads which preceed this instruction are complete. */
	read_after_iomem();

	/* read_before_io(); read_after_io(); */
	read_bidir_io();

	/* read_before_iomem(); read_after_iomem(); */
	read_bidir_iomem();

	/* read_before(), even if we are non-PREEMPT, non-SMP. */
	read_before_nonsmp();

	/* read_after(), even if we are non-PREEMPT, non-SMP. */
	read_after_nonsmp();

	/* read_before_nonsmp(); read_after_nonsmp(); */
	read_bidir_nonsmp();

Complete for write_* and readwrite_*.

Suggested semantics spin_lock():

	readwrite_after();
	readwrite_after_io();

ie. no interlock between io and memory: if you're doing both (eg acenic) you need to put in your own iomem barrier (this is for the PPC folk).

Questions:
1) Can we elide any others? In particular, can we remove ths _bidir_ ones?
2) Should we prepend a "barr_" prefix?
3) Any variations I missed?

Cheers,
Rusty.

   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy

Rusty> OK. So ignoring the fact that you somehow have to attach Rusty> your barriers to a load or store for the moment, we have Rusty> before vs. after (ia64), read vs. write (most archs), io vs Rusty> mem (ppc, ppc64), data dependency vs non-data dependency Rusty> (alpha), and smp vs up.

An alternative way to think about the ia64 model is that it provides "ordering" variables. Accesses to those variables won't be reordered by the compiler or the CPU and also order other (normally unordered accesses). One way to support this is have an ORDERING attribute for variables (which would expand into "volatile" on ia64). This would have to be complemented by a set of barrier routines which will achieve the desired ordering on machines that don't have the acquire/release model of ia64 (and on ia64, they would expand into nothing).

	--david

Earth to ia64, earth calling...

Until ia64 is a noticeable portion of the installed base, and indeed, until it has shown that it can survive at all, we're not going to design the Linux SMP memory ordering around that architecture.

If that means that ia64 will have to do strange things and maybe cannot take advantage of its strange memory models, that's ok. Because reality rules.

We're _not_ going to make up a complicated, big fancy new model. We might tweak the current one a bit. And if that means that some architectures get heavier barriers than they strictly need, then so be it. There are two overriding concerns:

- sanity: maybe it's better to have one mb() that is a sledgehammer but obvious, than it is to have many subtle variations that are just asking for subtle bugs.

- x86 _owns_ the market right now, and we're not going to make up barriers that add overhead to x86. We may add barriers that end up being no-op's on x86 (because it is fairly ordered anyway), but basically it should be designed for the _common_ case, not for some odd-ball architecture that has sold machines mostly for test purposes.

The x86 situation is obviously just today. In five or ten years maybe everybody agrees that we should follow the ia-64 model, and x86 can do strange things that end up being slow.

Linus

Linus> Until ia64 is a noticeable portion of the installed base, and Linus> indeed, until it has shown that it can survive at all, we're Linus> not going to design the Linux SMP memory ordering around that Linus> architecture.

Well, I hope we can *discuss* ideas for models that could accommodate all platforms.

Linus> We're _not_ going to make up a complicated, big fancy new Linus> model. We might tweak the current one a bit. And if that Linus> means that some architectures get heavier barriers than they Linus> strictly need, then so be it. There are two overriding Linus> concerns:

Linus> - sanity: maybe it's better to have one mb() that is a Linus> sledgehammer but obvious, than it is to have many subtle Linus> variations that are just asking for subtle bugs.

I tend to agree.

Linus> - x86 _owns_ the market right now, and we're not going to Linus> make up barriers that add overhead to x86. We may add Linus> barriers that end up being no-op's on x86 (because it is Linus> fairly ordered anyway), but basically it should be designed Linus> for the _common_ case, not for some odd-ball architecture Linus> that has sold machines mostly for test purposes.

Nobody suggested such a thing.

Linus> The x86 situation is obviously just today. In five or ten Linus> years maybe everybody agrees that we should follow the ia-64 Linus> model, and x86 can do strange things that end up being slow.

Geez, how about we spend a little time thinking about it *now*? Perhaps Rusty can come up with a model that will be easy to program for *and* work well for all platforms. Wouldn't that be neat? If not, we can always fall back on the sledge hammer (unlike other platforms, ia64 performance isn't affected much be extraneous memory barriers).

	--david

In message <[email protected]> you wr ite:

NO NO NO. Look at what actually happens now:

	void init_bh(int nr, void (*routine)(void))
	{
		bh_base[nr] = routine;
		mb();
	}

Now, what is this mb() for? Are you sure?

If we can come up with a better fit between the macros and what the code are trying to actually do, we win, even if they all map to the same thing *today*. While we're there, if we can get something that fits with different architectures, great.

Clearer?
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

I don't think it is true for alpha, but it is true
for x86-64. x86-64 by default has strong ordering for most loads/stores. It is possible to use weak ordering for special marked stores. For that there are special read and write and read/write barriers which apply to all memory (not distinction between io space and other memory). In addition there is a way to mark special memory areas as write combining and some other settings, but that is ordered by the normal barriers too.

-Andi

Yep, that is a good summary. And the problem arises from the very large penalty for the syncronization form used for CPU v I/O ordering. You only want to pay that when necessary, certainly not when only CPU v CPU ordering is required. The difference can be on the order of a 1000 cycles (depending on many factors, of course).

Dave.

Yep. Maybe we could have:

CPU v CPU smp_*mb or cpu_*mb
CPU v I/O *mb
I/O v I/O io_*mb

Then again before Linus hits me on the head for hoarding vowels,

http://hypermail.spyroid.com/linux-kernel/archived/2001/week41/1270.html

I should suggest we make these a little less cryptic:

CPU v CPU cpu_{read,write,memory}_barrier
CPU v I/O {read,write,memory}_barrier
I/O v I/O io_{read,write,memory}_barrier

I remember some ia64 implementations have issues. Jesse, could you fill us in again? I think you have problems with out of order loads/stores to noncacheable space, right?

Anton

Both MIPS64 and our NUMA IA64 implementation have weakly ordered I/O. The primitives outlined above should be sufficient to order I/O and memory references on both platforms without unnecessary penalties. Thanks for adding me to the Cc: list, sorry it took me so long to respond.

It might also be good to summarize the ordering issues in a document in the Documentation directory. I've got a little something started (see the ia64 patch for 2.5) for I/O ordering, and I have another document that covers CPU memory ordering too that I could probably contribute.

Thanks,
Jesse