From: Leonid Yegoshin <hidden> Date: 2016-01-14 20:47:16
On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
quoted
An the only point - please use an appropriate SYNC_* barriers instead of
heavy bold hammer. That stuff was design explicitly to support the
requirements of Documentation/memory-barriers.txt
That's madness. That document changes from version to version as to what
we _think_ the actual hardware does. It is _NOT_ a specification.
You cannot design hardware from that. Its incomplete and fails to
specify a bunch of things. It not a mathematically sound definition of a
memory model.
Please stop referring to that document for what a particular barrier
_should_ do. Explain what MIPS does, so we can attempt to integrate
this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
upon our understanding of hardware and improve the Linux memory model.
I am afraid I can't help you here. It is very complicated stuff and a
model is actually doesn't fit your assumptions about CPUs well without
some simplifications which are based on what you want to have.
I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire etc
(basing on that document). And at least two CPU models were tested with
my patches (see it in LMO) for that last year and that instructions are
implemented now in engineering kernel.
If you have something else in mind, you can ask me. But I prefer to do
not deviate too much from Documentation/memory-barriers.txt, for exam -
if it asks to have memory barrier somewhere, then I assume the code
should have it, and please - don't ask me a test which violates the
current version of document recommendations.
For a moment I don't see a significant changes in this document for MIPS
Arch at least 1.5 year, and the only significant point is that MIPS CPU
Arch doesn't have yet smp_read_barrier_depends() and smp_rmb() should be
used instead.
- Leonid.
From: Paul E. McKenney <hidden> Date: 2016-01-14 20:48:51
On Thu, Jan 14, 2016 at 12:12:53PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 04:04 AM, Will Deacon wrote:
quoted
Consequently, it's important that the architecture back-ends
implement these portable primitives (e.g. smp_mb()) in a way that
satisfies the kernel memory model so that core code doesn't need
to worry about the underlying architecture for synchronisation
purposes.
It seems you don't listen me. I said multiple times - MIPS
implementation of
SYNC_RMB/SYNC_WMB/SYNC_MB/SYNC_ACQUIRE/SYNC_RELEASE instructions
matches the description of
smp_rmb/smp_wmb/smp_mb/sync_acquire/sync_release from
Documentation/memory-barriers.txt file.
What else do you want from me - RTL or microArch design for that?
I suspect that it is more likely that we are talking past each other.
This stuff is subtle and although we have better ways of talking about
it than (say) ten years ago, it is subtle. Two ways of talking about
it are herd and ppcmem.
The overview of ppcmem (AKA armmem and cppmem) is here:
https://www.cl.cam.ac.uk/~pes20/ppcmem/help.html
The intro to herd is here: http://arxiv.org/pdf/1308.6810v5.pdf
It may be downloaded here: http://diy.inria.fr/herd/
As a very rough rule of thumb, herd is faster and easier to use
and ppcmem is more precise.
So SYNC_RMB is intended to implement smp_rmb(), correct?
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer. For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
Does that help?
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-14 21:01:34
I need some time to understand your test examples. However,
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA DEPENDENCY
BARRIERS" section recommendation to have data dependency barrier between
read of a shared pointer/index and read the shared data based on that
pointer. If you have this two reads, it doesn't matter the rest of
scenario, you should put the dependency barrier in code anyway. If you
don't do it in WRC+addr+addr scenario then after years it can be easily
changed to different scenario which fits some of scenario in "DATA
DEPENDENCY BARRIERS" section and fails.
Transitivity is
Peter Zijlstra recently wrote: "In particular we're very much all
'confused' about the various notions of transitivity". I am confused
too, so - please use some more simple way to explain your words. Sorry,
but we need a common ground first.
- Leonid.
From: Leonid Yegoshin <hidden> Date: 2016-01-14 21:25:06
On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
So SYNC_RMB is intended to implement smp_rmb(), correct?
Yes.
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
If smp_read_barrier_depends() is used to separate not only two reads but
read pointer and WRITE basing on that pointer (example below) - yes. I
just doesn't see any example of this in famous
Documentation/memory-barriers.txt and had no chance to know what you use
it in this way too.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer.
I can't see that requirement anywhere in Documents directory. I mean -
the words "write through a dereference of that pointer" or similar for
smp_read_barrier_depends.
For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
It is not so simple, I mean "local ordering for address and data
dependencies". Local ordering is NOT enough. It happens that current
MIPS R6 doesn't require in your example smp_read_barrier_depends() but
in discussion it comes out that it may not. Because without
smp_read_barrier_depends() your example can be a part of Will's
WRC+addr+addr and we found some design which easily can bump into this
test. And that design actually performs "local ordering for address and
data dependencies" too.
- Leonid.
From: Paul E. McKenney <hidden> Date: 2016-01-14 21:29:39
On Thu, Jan 14, 2016 at 01:01:05PM -0800, Leonid Yegoshin wrote:
I need some time to understand your test examples. However,
Understood.
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
quoted
Transitivity is
Peter Zijlstra recently wrote: "In particular we're very much all
'confused' about the various notions of transitivity". I am confused
too, so - please use some more simple way to explain your words.
Sorry, but we need a common ground first.
OK, how about an example? (Z6.3 in the ppcmem naming scheme.)
int x, y, z;
void cpu0(void)
{
WRITE_ONCE(x, 1);
smp_wmb();
WRITE_ONCE(y, 1);
}
void cpu1(void)
{
WRITE_ONCE(y, 2);
smp_wmb();
WRITE_ONCE(z, 1);
}
void cpu2(void)
{
r1 = READ_ONCE(z);
smp_rmb();
r2 = read_once(x);
}
If smp_rmb() and smp_wmb() provided transitive ordering, then cpu2()
would see cpu0()'s ordering. But they do not, so the ordering is
visible at best to the adjacent CPU. This means that the final value
of y can be 2, while at the same time r1==1 && r2==0.
Now the full barrier, smp_mb(), does provide transitive ordering,
so if the three barriers in the above example are replaced with
smp_mb() the y==2 && r1==1 && r2==0 outcome will be prohibited.
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(), as do RCU grace periods. The exact interactions
between transitive and non-transitive ordering is a work in progress.
That said, if a series of transitive segments ends in a write, which
connects to a single non-transitive segment starting with a read,
you should be good. And in fact in the example above, you can replace
the smp_wmb()s with smp_mb() and leave the smp_rmb() and still
prohibit the "cyclic" outcome.
If you want a more formal definition, I must refer you back to the
ppcmem and herd references.
Does that help?
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-14 21:35:05
On Thu, Jan 14, 2016 at 12:46:43PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
quoted
An the only point - please use an appropriate SYNC_* barriers instead of
heavy bold hammer. That stuff was design explicitly to support the
requirements of Documentation/memory-barriers.txt
That's madness. That document changes from version to version as to what
we _think_ the actual hardware does. It is _NOT_ a specification.
You cannot design hardware from that. Its incomplete and fails to
specify a bunch of things. It not a mathematically sound definition of a
memory model.
Please stop referring to that document for what a particular barrier
_should_ do. Explain what MIPS does, so we can attempt to integrate
this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
upon our understanding of hardware and improve the Linux memory model.
I am afraid I can't help you here. It is very complicated stuff and
a model is actually doesn't fit your assumptions about CPUs well
without some simplifications which are based on what you want to
have.
I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire
etc (basing on that document). And at least two CPU models were
tested with my patches (see it in LMO) for that last year and that
instructions are implemented now in engineering kernel.
If you have something else in mind, you can ask me. But I prefer to
do not deviate too much from Documentation/memory-barriers.txt, for
exam - if it asks to have memory barrier somewhere, then I assume
the code should have it, and please - don't ask me a test which
violates the current version of document recommendations.
For a moment I don't see a significant changes in this document for
MIPS Arch at least 1.5 year, and the only significant point is that
MIPS CPU Arch doesn't have yet smp_read_barrier_depends() and
smp_rmb() should be used instead.
Is SYNC_ACQUIRE a memory-barrier instruction that orders prior loads
against later loads and stores? If so, and if MIPS does not do
ordering based on address and data dependencies, I suggest making
read_barrier_depends() be a SYNC_ACQUIRE rather than SYNC_RMB.
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-14 21:37:19
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
quoted
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a barrier.
I don't see a common points between this and that in your answer, sorry.
- Leonid.
From: Leonid Yegoshin <hidden> Date: 2016-01-14 21:46:18
On 01/14/2016 01:34 PM, Paul E. McKenney wrote:
On Thu, Jan 14, 2016 at 12:46:43PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
quoted
An the only point - please use an appropriate SYNC_* barriers instead of
heavy bold hammer. That stuff was design explicitly to support the
requirements of Documentation/memory-barriers.txt
That's madness. That document changes from version to version as to what
we _think_ the actual hardware does. It is _NOT_ a specification.
You cannot design hardware from that. Its incomplete and fails to
specify a bunch of things. It not a mathematically sound definition of a
memory model.
Please stop referring to that document for what a particular barrier
_should_ do. Explain what MIPS does, so we can attempt to integrate
this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
upon our understanding of hardware and improve the Linux memory model.
I am afraid I can't help you here. It is very complicated stuff and
a model is actually doesn't fit your assumptions about CPUs well
without some simplifications which are based on what you want to
have.
I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire
etc (basing on that document). And at least two CPU models were
tested with my patches (see it in LMO) for that last year and that
instructions are implemented now in engineering kernel.
If you have something else in mind, you can ask me. But I prefer to
do not deviate too much from Documentation/memory-barriers.txt, for
exam - if it asks to have memory barrier somewhere, then I assume
the code should have it, and please - don't ask me a test which
violates the current version of document recommendations.
For a moment I don't see a significant changes in this document for
MIPS Arch at least 1.5 year, and the only significant point is that
MIPS CPU Arch doesn't have yet smp_read_barrier_depends() and
smp_rmb() should be used instead.
Is SYNC_ACQUIRE a memory-barrier instruction that orders prior loads
against later loads and stores?
If so, and if MIPS does not do
ordering based on address and data dependencies, I suggest making
read_barrier_depends() be a SYNC_ACQUIRE rather than SYNC_RMB.
I understood that, after I see the example of using it.
Please consider to add that into Documentation/memory-barriers.txt (it
is not easy to find that this barrier is used for shared WRITE basing on
shared pointer), it would be helpful.
- Leonid.
From: Paul E. McKenney <hidden> Date: 2016-01-14 22:21:15
On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
quoted
So SYNC_RMB is intended to implement smp_rmb(), correct?
Yes.
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
If smp_read_barrier_depends() is used to separate not only two reads
but read pointer and WRITE basing on that pointer (example below) -
yes. I just doesn't see any example of this in famous
Documentation/memory-barriers.txt and had no chance to know what you
use it in this way too.
Well, Documentation/memory-barriers.txt was intended as a guide for Linux
kernel hackers, and not for hardware architects. The need for something
more precise has become clear over the past year or two, and I am working
on it with some heavy-duty memory-model folks. But all previous memory
models have been for a specific CPU architecture, so doing one for the
intersection of several is offering up some complications. I therefore
cannot yet provide a completion date.
That said, I still suggest use of SYNC_ACQUIRE for read_barrier_depends().
quoted
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer.
I can't see that requirement anywhere in Documents directory. I mean
- the words "write through a dereference of that pointer" or similar
for smp_read_barrier_depends.
No worries, I will add one. Please see the end of this message for an
initial patch.
Please understand that Documentation/memory-barriers.txt is a living
document:
v4.4: Two changes
v4.3: Three changes
v4.2: Six changes
v4.1: Three changes
v4.0: Two changes
It tends to change as we locate corner cases either in hardware or
in software use cases/APIs.
quoted
For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
It is not so simple, I mean "local ordering for address and data
dependencies". Local ordering is NOT enough. It happens that current
MIPS R6 doesn't require in your example smp_read_barrier_depends()
but in discussion it comes out that it may not. Because without
smp_read_barrier_depends() your example can be a part of Will's
WRC+addr+addr and we found some design which easily can bump into
this test. And that design actually performs "local ordering for
address and data dependencies" too.
As noted in another email in this thread, I do not believe that
WRC+addr+addr needs to be prohibited. Sounds like Will and I need to
get our story straight, though.
Will?
Thanx, Paul
------------------------------------------------------------------------
commit 955720966e216b00613fcf60188d507c103f0e80
Author: Paul E. McKenney [off-list ref]
Date: Thu Jan 14 14:17:04 2016 -0800
documentation: Subsequent writes ordered by rcu_dereference()
The current memory-barriers.txt does not address the possibility of
a write to a dereferenced pointer. This should be rare, but when it
happens, we need that write -not- to be clobbered by the initialization.
This commit therefore adds an example showing a data dependency ordering
a later data-dependent write.
Reported-by: Leonid Yegoshin [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
@@ -555,6 +555,30 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising.+A data-dependency barrier must also order against dependent writes:++ CPU 1 CPU 2+ =============== ===============+ { A == 1, B == 2, C = 3, P == &A, Q == &C }+ B = 4;+ <write barrier>+ WRITE_ONCE(P, &B);+ Q = READ_ONCE(P);+ <data dependency barrier>+ *Q = 5;++The data-dependency barrier must order the read into Q with the store+into *Q. This prohibits this outcome:++ (Q == B) && (B == 4)++Please note that this pattern should be rare. After all, the whole point+of dependency ordering is to -prevent- writes to the data structure, along+with the expensive cache misses associated with those writes. This pattern+can be used to record rare error conditions and the like, and the ordering+prevents such records from being lost.++ [!] Note that this extremely counterintuitive situation arises most easily on machines with split caches, so that, for example, one cache bank processes even-numbered cache lines and the other bank processes odd-numbered cache
From: Paul E. McKenney <hidden> Date: 2016-01-14 22:25:05
On Thu, Jan 14, 2016 at 01:45:44PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 01:34 PM, Paul E. McKenney wrote:
quoted
On Thu, Jan 14, 2016 at 12:46:43PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
quoted
An the only point - please use an appropriate SYNC_* barriers instead of
heavy bold hammer. That stuff was design explicitly to support the
requirements of Documentation/memory-barriers.txt
That's madness. That document changes from version to version as to what
we _think_ the actual hardware does. It is _NOT_ a specification.
You cannot design hardware from that. Its incomplete and fails to
specify a bunch of things. It not a mathematically sound definition of a
memory model.
Please stop referring to that document for what a particular barrier
_should_ do. Explain what MIPS does, so we can attempt to integrate
this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
upon our understanding of hardware and improve the Linux memory model.
I am afraid I can't help you here. It is very complicated stuff and
a model is actually doesn't fit your assumptions about CPUs well
without some simplifications which are based on what you want to
have.
I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire
etc (basing on that document). And at least two CPU models were
tested with my patches (see it in LMO) for that last year and that
instructions are implemented now in engineering kernel.
If you have something else in mind, you can ask me. But I prefer to
do not deviate too much from Documentation/memory-barriers.txt, for
exam - if it asks to have memory barrier somewhere, then I assume
the code should have it, and please - don't ask me a test which
violates the current version of document recommendations.
For a moment I don't see a significant changes in this document for
MIPS Arch at least 1.5 year, and the only significant point is that
MIPS CPU Arch doesn't have yet smp_read_barrier_depends() and
smp_rmb() should be used instead.
quoted
Is SYNC_ACQUIRE a memory-barrier instruction that orders prior loads
against later loads and stores?
OK, it does look like it should work. Of course, if you can rely
on straight address/data dependencies, that would be even better.
quoted
If so, and if MIPS does not do
ordering based on address and data dependencies, I suggest making
read_barrier_depends() be a SYNC_ACQUIRE rather than SYNC_RMB.
I understood that, after I see the example of using it.
Please consider to add that into Documentation/memory-barriers.txt
(it is not easy to find that this barrier is used for shared WRITE
basing on shared pointer), it would be helpful.
Actually, the Linux kernel doesn't have an acquire barrier, just an
smp_load_acquire(). Or did someone sneak one in while I wasn't looking? ;-)
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-14 22:55:39
On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
quoted
quoted
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a
barrier. I don't see a common points between this and that in your
answer, sorry.
Me, I am wondering what WRC+addr+addr has to do with anything at all.
<Going back through earlier email>
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
earlier example, which needs to provide ordering.
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time. This leads me to believe that your smp_mb() needs
to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
discussion in this thread.
Suppose you have something like this:
void cpu0(void)
{
WRITE_ONCE(a, 1);
SYNC_MB();
r0 = READ_ONCE(b);
}
void cpu1(void)
{
WRITE_ONCE(b, 1);
SYNC_MB();
r1 = READ_ONCE(c);
}
void cpu2(void)
{
WRITE_ONCE(c, 1);
SYNC_MB();
r2 = READ_ONCE(d);
}
void cpu3(void)
{
WRITE_ONCE(d, 1);
SYNC_MB();
r3 = READ_ONCE(a);
}
Does your hardware guarantee that it is not possible for all of r0,
r1, r2, and r3 to be equal to zero at the end of the test, assuming
that a, b, c, and d are all initially zero, and the four functions
above run concurrently? There are many similar litmus tests for other
combinations of reads and writes, but this is perhaps the nastiest from
a hardware viewpoint. Does SYNC_MB() provide sufficient ordering for
this sort of situation?
Another (more academic) case is this one, with x and y initially zero:
void cpu0(void)
{
WRITE_ONCE(x, 1);
}
void cpu1(void)
{
WRITE_ONCE(y, 1);
}
void cpu2(void)
{
r1 = READ_ONCE(x, 1);
SYNC_MB();
r2 = READ_ONCE(y, 1);
}
void cpu3(void)
{
r3 = READ_ONCE(y, 1);
SYNC_MB();
r4 = READ_ONCE(x, 1);
}
Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
Now, I don't know of any specific use cases for this pattern, but it
is greatly beloved of some of the old-school concurrency community,
so it is likely to crop up at some point, despite my best efforts. :-/
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-14 23:04:48
On 01/14/2016 02:24 PM, Paul E. McKenney wrote:
Actually, the Linux kernel doesn't have an acquire barrier, just an
smp_load_acquire(). Or did someone sneak one in while I wasn't looking?
That was an exactly starting point for this discussion. This patch just
pulls out from MIPS files smp_load_acquire() and smp_store_release().
However, I put into LMO half year ago the patch
http://patchwork.linux-mips.org/patch/10506/ which replaces a generic
smp_mb with MIPS specific smp_release/acquire in that functions. This
patch also fixes use of SYNCs barriers in spin_locks/atomics/bitops for
Imagination MIPS CPUs too - it is just absent now for any Imagination
MIPS CPUs!
Michael later pointed me that it can be returned back with his series of
patches but discussion was already here.
- Leonid.
From: Leonid Yegoshin <hidden> Date: 2016-01-14 23:34:41
On 01/14/2016 02:55 PM, Paul E. McKenney wrote:
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr.
(He actually asked twice about this and that too but skip this)
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time. This leads me to believe that your smp_mb() needs
to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
discussion in this thread.
Don't be fooled here by words "ordered" and "completed" - it is HW
design items and actually written poorly.
Just assume that SYNC_MB is absolutely the same as SYNC for any CPU and
coherent device (besides performance). The difference can be in
non-coherent devices because SYNC actually tries to make a barrier for
them too. In some SoCs it is just the same because there is no need to
barrier a non-coherent device (device register access usually strictly
ordered... if there is no bridge in between).
Suppose you have something like this:
...
Does your hardware guarantee that it is not possible for all of r0,
r1, r2, and r3 to be equal to zero at the end of the test, assuming
that a, b, c, and d are all initially zero, and the four functions
above run concurrently?
It is assumed to be so from Arch point of view. HW bugs are possible, of
course.
Another (more academic) case is this one, with x and y initially zero:
...
Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
It is assumed to be so from Arch point of view. HW bugs are possible, of
course.
Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
implemented some time but nobody made it in Linux kernel (it was used by
some vendor for non-Linux system). For that reason my patch for
lightweight SYNCs has an option - implement it or implement a generic
SYNC. It is possible that some vendor did it in different way but nobody
knows or test it. But as a minimum - SYNC must be implemented in
spinlocks/atomics/bitops, in recent P5600 it is proven that read can
pass write in atomics.
MIPS R6 is a different story, I verified lightweight SYNCs from the
beginning and it also should use SYNCs.
- Leonid.
From: Paul E. McKenney <hidden> Date: 2016-01-15 00:48:12
On Thu, Jan 14, 2016 at 03:33:40PM -0800, Leonid Yegoshin wrote:
On 01/14/2016 02:55 PM, Paul E. McKenney wrote:
quoted
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr.
(He actually asked twice about this and that too but skip this)
Fair enough! ;-)
quoted
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time. This leads me to believe that your smp_mb() needs
to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
discussion in this thread.
Don't be fooled here by words "ordered" and "completed" - it is HW
design items and actually written poorly.
Just assume that SYNC_MB is absolutely the same as SYNC for any CPU
and coherent device (besides performance). The difference can be in
non-coherent devices because SYNC actually tries to make a barrier
for them too. In some SoCs it is just the same because there is no
need to barrier a non-coherent device (device register access
usually strictly ordered... if there is no bridge in between).
So smp_mb() can be SYNC_MB. However, mb() needs to be SYNC for MMIO
purposes, correct?
quoted
Suppose you have something like this:
...
Does your hardware guarantee that it is not possible for all of r0,
r1, r2, and r3 to be equal to zero at the end of the test, assuming
that a, b, c, and d are all initially zero, and the four functions
above run concurrently?
It is assumed to be so from Arch point of view. HW bugs are
possible, of course.
Indeed!
quoted
Another (more academic) case is this one, with x and y initially zero:
...
Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
It is assumed to be so from Arch point of view. HW bugs are
possible, of course.
Looks to me like smp_mb() can be SYNC_MB, then.
Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
implemented some time but nobody made it in Linux kernel (it was
used by some vendor for non-Linux system). For that reason my patch
for lightweight SYNCs has an option - implement it or implement a
generic SYNC. It is possible that some vendor did it in different
way but nobody knows or test it. But as a minimum - SYNC must be
implemented in spinlocks/atomics/bitops, in recent P5600 it is
proven that read can pass write in atomics.
MIPS R6 is a different story, I verified lightweight SYNCs from the
beginning and it also should use SYNCs.
So you need to build a different kernel for some types of MIPS systems?
Or do you do boot-time rewriting, like a number of other arches do?
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-15 01:07:48
On 01/14/2016 04:47 PM, Paul E. McKenney wrote:
On Thu, Jan 14, 2016 at 03:33:40PM -0800, Leonid Yegoshin wrote:
quoted
Don't be fooled here by words "ordered" and "completed" - it is HW
design items and actually written poorly.
Just assume that SYNC_MB is absolutely the same as SYNC for any CPU
and coherent device (besides performance). The difference can be in
non-coherent devices because SYNC actually tries to make a barrier
for them too. In some SoCs it is just the same because there is no
need to barrier a non-coherent device (device register access
usually strictly ordered... if there is no bridge in between).
So smp_mb() can be SYNC_MB. However, mb() needs to be SYNC for MMIO
purposes, correct?
Absolutely. For MIPS R2 which is not Octeon.
quoted
Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
implemented some time but nobody made it in Linux kernel (it was
used by some vendor for non-Linux system). For that reason my patch
for lightweight SYNCs has an option - implement it or implement a
generic SYNC. It is possible that some vendor did it in different
way but nobody knows or test it. But as a minimum - SYNC must be
implemented in spinlocks/atomics/bitops, in recent P5600 it is
proven that read can pass write in atomics.
MIPS R6 is a different story, I verified lightweight SYNCs from the
beginning and it also should use SYNCs.
So you need to build a different kernel for some types of MIPS systems?
Or do you do boot-time rewriting, like a number of other arches do?
I don't know. I would like to have responses. Ralf asked Maciej about
old systems and that came nowhere. Even rewrite - don't know what to do
with that: no lightweight SYNC or no SYNC at all - yes, it is still
possible that SYNC on some systems can be too heavy or even harmful,
nobody tested that.
- Leonid.
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-15 08:56:17
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-15 09:14:18
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
quoted
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
And smp_load_acquire()/smp_store_release() are RCpc because TSO archs
and PPC. the atomic*_{acquire,release}() are RCpc because PPC and
LOCK,UNLOCK are similarly RCpc because of PPC.
Now we'd like PPC to stick a SYNC in either LOCK or UNLOCK so at least
the locks are RCsc again, but they resist for performance reasons but
waver because they don't want to be the ones finding all the nasty bugs
because they're the only one.
Now the thing I worry about, and still have not had an answer to is if
weakly ordered MIPS will end up being RCsc or RCpc for their locks if
they get implemented with SYNC_ACQUIRE and SYNC_RELEASE instead of the
current SYNC.
From: Will Deacon <hidden> Date: 2016-01-15 09:58:18
Paul,
On Thu, Jan 14, 2016 at 02:20:46PM -0800, Paul E. McKenney wrote:
On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
quoted
It is not so simple, I mean "local ordering for address and data
dependencies". Local ordering is NOT enough. It happens that current
MIPS R6 doesn't require in your example smp_read_barrier_depends()
but in discussion it comes out that it may not. Because without
smp_read_barrier_depends() your example can be a part of Will's
WRC+addr+addr and we found some design which easily can bump into
this test. And that design actually performs "local ordering for
address and data dependencies" too.
As noted in another email in this thread, I do not believe that
WRC+addr+addr needs to be prohibited. Sounds like Will and I need to
get our story straight, though.
I think you figured this out while I was sleeping, but just to confirm:
1. The MIPS64 ISA doc [1] talks about SYNC in a way that applies only
to memory accesses appearing in *program-order* before the SYNC
2. We need WRC+sync+addr to work, which means that the SYNC in P1 must
also capture the store in P0 as being "before" the barrier. Leonid
reckons it works, but his explanation [2] focussed on the address
dependency in P2 as to why this works. If that is the case (i.e.
address dependency provides global transitivity), then WRC+addr+addr
should also work (even though its not required).
3. It seems that WRC+addr+addr doesn't work, so I'm still suspicious
about WRC+sync+addr, because neither the architecture document or
Leonid's explanation tell me that it should be forbidden.
Will
[1] https://imgtec.com/?do-download=4302
[2] http://lkml.kernel.org/r/569565DA.2010903@imgtec.com (scroll to the end)
From: Will Deacon <hidden> Date: 2016-01-15 10:24:42
On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
quoted
quoted
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a
barrier. I don't see a common points between this and that in your
answer, sorry.
Me, I am wondering what WRC+addr+addr has to do with anything at all.
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
<Going back through earlier email>
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
earlier example, which needs to provide ordering.
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time.
I couldn't make that leap. In particular, the manual's "Detailed
Description" sections explicitly refer to program-order:
Every synchronizable specified memory instruction (loads or stores or
both) that occurs in the instruction stream before the SYNC
instruction must reach a stage in the load/store datapath after which
no instruction re-ordering is possible before any synchronizable
specified memory instruction which occurs after the SYNC instruction
in the instruction stream reaches the same stage in the load/store
datapath.
Will
[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2016-January/399765.html
From: Paul E. McKenney <hidden> Date: 2016-01-15 17:48:33
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
quoted
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
Good point!
Using grace periods in place of smp_mb() also provides strong/global
transitivity, but also insanely high latencies. ;-)
The patch below updates Documentation/memory-barriers.txt to define
local vs. global transitivity. The corresponding ppcmem litmus test
is included below as well.
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
Thanx, Paul
------------------------------------------------------------------------
PPC local-transitive
""
{
0:r1=1; 0:r2=u; 0:r3=v; 0:r4=x; 0:r5=y; 0:r6=z;
1:r1=1; 1:r2=u; 1:r3=v; 1:r4=x; 1:r5=y; 1:r6=z;
2:r1=1; 2:r2=u; 2:r3=v; 2:r4=x; 2:r5=y; 2:r6=z;
3:r1=1; 3:r2=u; 3:r3=v; 3:r4=x; 3:r5=y; 3:r6=z;
}
P0 | P1 | P2 | P3 ;
lwz r9,0(r4) | lwz r9,0(r5) | lwz r9,0(r6) | stw r1,0(r3) ;
lwsync | lwsync | lwsync | sync ;
stw r1,0(r2) | lwz r8,0(r3) | stw r1,0(r7) | lwz r9,0(r2) ;
lwsync | lwz r7,0(r2) | | ;
stw r1,0(r5) | lwsync | | ;
| stw r1,0(r6) | | ;
exists
(* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r8=0 /\ 3:r9=0) *)
(* (0:r9=1 /\ 1:r9=1 /\ 2:r9=1) *)
(* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0) *)
(0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0)
------------------------------------------------------------------------
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney [off-list ref]
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra [off-list ref]
Reported-by: Will Deacon [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
@@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes. General barriers are therefore required to ensure that all CPUs agree on the combined order of CPU 1's and CPU 2's accesses.-To reiterate, if your code requires transitivity, use general barriers-throughout.+General barriers provide "global transitivity", so that all CPUs will+agree on the order of operations. In contrast, a chain of release-acquire+pairs provides only "local transitivity", so that only those CPUs on+the chain are guaranteed to agree on the combined order of the accesses.+For example, switching to C code in deference to Herman Hollerith:++ int u, v, x, y, z;++ void cpu0(void)+ {+ r0 = smp_load_acquire(&x);+ WRITE_ONCE(u, 1);+ smp_store_release(&y, 1);+ }++ void cpu1(void)+ {+ r1 = smp_load_acquire(&y);+ r4 = READ_ONCE(v);+ r5 = READ_ONCE(u);+ smp_store_release(&z, 1);+ }++ void cpu2(void)+ {+ r2 = smp_load_acquire(&z);+ smp_store_release(&x, 1);+ }++ void cpu3(void)+ {+ WRITE_ONCE(v, 1);+ smp_mb();+ r3 = READ_ONCE(u);+ }++Because cpu0(), cpu1(), and cpu2() participate in a local transitive+chain of smp_store_release()/smp_load_acquire() pairs, the following+outcome is prohibited:++ r0 == 1 && r1 == 1 && r2 == 1++Furthermore, because of the release-acquire relationship between cpu0()+and cpu1(), cpu1() must see cpu0()'s writes, so that the following+outcome is prohibited:++ r1 == 1 && r5 == 0++However, the transitivity of release-acquire is local to the participating+CPUs and does not apply to cpu3(). Therefore, the following outcome+is possible:++ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0++Although cpu0(), cpu1(), and cpu2() will see their respective reads and+writes in order, CPUs not involved in the release-acquire chain might+well disagree on the order. This disagreement stems from the fact that+the weak memory-barrier instructions used to implement smp_load_acquire()+and smp_store_release() are not required to order prior stores against+subsequent loads in all cases. This means that cpu3() can see cpu0()'s+store to u as happening -after- cpu1()'s load from v, even though+both cpu0() and cpu1() agree that these two operations occurred in the+intended order.++However, please keep in mind that smp_load_acquire() is not magic.+In particular, it simply reads from its argument with ordering. It does+-not- ensure that any particular value will be read. Therefore, the+following outcome is possible:++ r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0++Note that this outcome can happen even on a mythical sequentially+consistent system where nothing is ever reordered.++To reiterate, if your code requires global transitivity, use general+barriers throughout. ========================
From: Paul E. McKenney <hidden> Date: 2016-01-15 17:53:34
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
quoted
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
Hoping my memory-barrier.txt patch helps here...
And smp_load_acquire()/smp_store_release() are RCpc because TSO archs
and PPC. the atomic*_{acquire,release}() are RCpc because PPC and
LOCK,UNLOCK are similarly RCpc because of PPC.
Now we'd like PPC to stick a SYNC in either LOCK or UNLOCK so at least
the locks are RCsc again, but they resist for performance reasons but
waver because they don't want to be the ones finding all the nasty bugs
because they're the only one.
I believe that the relevant proverb said something about starving to
death between two bales of hay... ;-)
Now the thing I worry about, and still have not had an answer to is if
weakly ordered MIPS will end up being RCsc or RCpc for their locks if
they get implemented with SYNC_ACQUIRE and SYNC_RELEASE instead of the
current SYNC.
It would be good to have better clarity on this, no two ways about it.
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-15 17:54:30
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
quoted
On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
quoted
quoted
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a
barrier. I don't see a common points between this and that in your
answer, sorry.
Me, I am wondering what WRC+addr+addr has to do with anything at all.
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
quoted
<Going back through earlier email>
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
earlier example, which needs to provide ordering.
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time.
I couldn't make that leap. In particular, the manual's "Detailed
Description" sections explicitly refer to program-order:
Every synchronizable specified memory instruction (loads or stores or
both) that occurs in the instruction stream before the SYNC
instruction must reach a stage in the load/store datapath after which
no instruction re-ordering is possible before any synchronizable
specified memory instruction which occurs after the SYNC instruction
in the instruction stream reaches the same stage in the load/store
datapath.
Will
[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2016-January/399765.html
All good points. I think we all agree that the MIPS documentation could
use significant help. And given that I work for the company that produced
the analogous documentation for PowerPC, that is saying something. ;-)
We simply can't know if MIPS's memory ordering is sufficient for the
Linux kernel given its current implementation of the ordering primitives
and its current documentation.
I feel a bit better than I did earlier due to Leonid's response to my
earlier litmus-test examples. But I do recommend some serious stress
testing of MIPS on a good set of litmus tests. Much nicer finding issues
that way than as random irreproducible strange behavior!
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-15 18:55:04
On 01/15/2016 01:57 AM, Will Deacon wrote:
Paul,
I think you figured this out while I was sleeping, but just to confirm:
1. The MIPS64 ISA doc [1] talks about SYNC in a way that applies only
to memory accesses appearing in *program-order* before the SYNC
2. We need WRC+sync+addr to work, which means that the SYNC in P1 must
also capture the store in P0 as being "before" the barrier. Leonid
reckons it works, but his explanation [2] focussed on the address
dependency in P2 as to why this works. If that is the case (i.e.
address dependency provides global transitivity), then WRC+addr+addr
should also work (even though its not required).
No, it is not correct. There is one old design which provides access to
core (thread0 + thread1) write-buffers for threads load in advance of it
is visible to other cores. It means, that WRC+sync+addr passes because
of SYNC in write thread and register dependency inside other thread but
WRC+addr+addr may fail because other core may get a stale data.
From: Paul E. McKenney <hidden> Date: 2016-01-15 19:29:07
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
quoted
On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
quoted
On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
quoted
quoted
On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
quoted
The WRC+addr+addr is OK because data dependencies are not required to be
transitive, in other words, they are not required to flow from one CPU to
another without the help of an explicit memory barrier.
I don't see any reliable way to fit WRC+addr+addr into "DATA
DEPENDENCY BARRIERS" section recommendation to have data dependency
barrier between read of a shared pointer/index and read the shared
data based on that pointer. If you have this two reads, it doesn't
matter the rest of scenario, you should put the dependency barrier
in code anyway. If you don't do it in WRC+addr+addr scenario then
after years it can be easily changed to different scenario which
fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
fails.
The trick is that lockless_dereference() contains an
smp_read_barrier_depends():
#define lockless_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
(_________p1); \
})
Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a
barrier. I don't see a common points between this and that in your
answer, sorry.
Me, I am wondering what WRC+addr+addr has to do with anything at all.
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
Thanx, Paul
PS. And yes, working through this does help me understand the
benefits of fake dependencies. Why do you ask? ;-)
------------------------------------------------------------------------
PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
P0 | P1 | P2 ;
stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
| stw r2,0(r3) | lwz r9,0(r8) ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-15 21:27:59
On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
quoted
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
Hoping my memory-barrier.txt patch helps here...
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
of the stores looses a conflict, and if that scenario matters. If it
does, we should inspect the same case for other barriers.
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-15 21:29:50
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
Yeah, or a version of them in C that we can 'compile'?
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney [off-list ref]
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra [off-list ref]
Reported-by: Will Deacon [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
I think it fails to mention smp_mb__after_release_acquire(), although I
suspect we didn't actually introduce the primitive yet, which raises the
point, do we want to?
From: Paul E. McKenney <hidden> Date: 2016-01-15 21:59:21
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
quoted
quoted
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
Hoping my memory-barrier.txt patch helps here...
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
But I will admit that there are some rather strange litmus tests that
challenge this cycle-centric view, for example, the one shown below.
It turns out that herd and ppcmem disagree on the outcome. (The Power
architects side with ppcmem.)
And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
of the stores looses a conflict, and if that scenario matters. If it
does, we should inspect the same case for other barriers.
Indeed. I am still working on how these should be described. My
current thought is to be quite conservative on what ordering is
actually respected, however, the current task is formalizing how
RCU plays with the rest of the memory model.
Thanx, Paul
------------------------------------------------------------------------
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
From: Paul E. McKenney <hidden> Date: 2016-01-15 22:08:35
On Fri, Jan 15, 2016 at 10:29:12PM +0100, Peter Zijlstra wrote:
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
quoted
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
Yeah, or a version of them in C that we can 'compile'?
That would be good as well. I am guessing that architecture-specific
litmus tests will also be needed, but you are right that
architecture-independent versions are higher priority.
quoted
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney [off-list ref]
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra [off-list ref]
Reported-by: Will Deacon [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
I think it fails to mention smp_mb__after_release_acquire(), although I
suspect we didn't actually introduce the primitive yet, which raises the
point, do we want to?
Well, it is not in v4.4. I believe that we need good use cases before
we add it.
Thanx, Paul
From: Herbert Xu <herbert@gondor.apana.org.au> Date: 2016-01-18 08:22:36
Paul E. McKenney [off-list ref] wrote:
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer. For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
Does that help?
From: Paul E. McKenney <hidden> Date: 2016-01-18 15:46:50
On Mon, Jan 18, 2016 at 04:19:29PM +0800, Herbert Xu wrote:
Paul E. McKenney [off-list ref] wrote:
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer. For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
Does that help?
This is crazy! smp_rmb started out being strictly stronger than
smp_read_barrier_depends, when did this stop being the case?
Hello, Herbert!
It is true that most Linux kernel code relies only on the read-read
properties of dependencies, but the read-write properties are useful.
Admittedly relatively rarely, but useful.
The better comparison for smp_read_barrier_depends(), especially in
its rcu_dereference*() form, is smp_load_acquire().
Thanx, Paul
From: Will Deacon <hidden> Date: 2016-01-25 14:41:51
On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
quoted
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
Nope, it was pretty baffling!
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
The code above looks correct to me (in that it matches WRC+addrs),
but your litmus test:
From: Will Deacon <hidden> Date: 2016-01-25 16:43:01
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
quoted
On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
quoted
quoted
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
Hoping my memory-barrier.txt patch helps here...
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
Do you have some examples of this? I'm struggling to make it work in my
mind, or are you talking specifically in the context of the kernel
memory model?
But I will admit that there are some rather strange litmus tests that
challenge this cycle-centric view, for example, the one shown below.
It turns out that herd and ppcmem disagree on the outcome. (The Power
architects side with ppcmem.)
quoted
And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
of the stores looses a conflict, and if that scenario matters. If it
does, we should inspect the same case for other barriers.
Indeed. I am still working on how these should be described. My
current thought is to be quite conservative on what ordering is
actually respected, however, the current task is formalizing how
RCU plays with the rest of the memory model.
Thanx, Paul
------------------------------------------------------------------------
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
The double negatives don't help here! (it is forbidden to guarantee that
z is not always 2).
Will
From: Will Deacon <hidden> Date: 2016-01-25 18:03:09
Hi Paul,
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
quoted
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
Good point!
Using grace periods in place of smp_mb() also provides strong/global
transitivity, but also insanely high latencies. ;-)
The patch below updates Documentation/memory-barriers.txt to define
local vs. global transitivity. The corresponding ppcmem litmus test
is included below as well.
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
I too would like to have the litmus tests in the kernel so that we can
refer to them from memory-barriers.txt. Ideally they wouldn't be targetted
to a particular arch, however.
i.e. we should rewrite this using READ_ONCE/WRITE_ONCE and smp_mb() etc.
quoted hunk
------------------------------------------------------------------------
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney [off-list ref]
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra [off-list ref]
Reported-by: Will Deacon [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
@@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes. General barriers are therefore required to ensure that all CPUs agree on the combined order of CPU 1's and CPU 2's accesses.-To reiterate, if your code requires transitivity, use general barriers-throughout.+General barriers provide "global transitivity", so that all CPUs will+agree on the order of operations. In contrast, a chain of release-acquire+pairs provides only "local transitivity", so that only those CPUs on+the chain are guaranteed to agree on the combined order of the accesses.
Thanks for having a go at this. I tried defining something axiomatically,
but got stuck pretty quickly. In my scheme, I used "data-directed
transitivity" instead of "local transitivity", since the latter seems to
be a bit of a misnomer.
+For example, switching to C code in deference to Herman Hollerith:
+
+ int u, v, x, y, z;
+
+ void cpu0(void)
+ {
+ r0 = smp_load_acquire(&x);
+ WRITE_ONCE(u, 1);
+ smp_store_release(&y, 1);
+ }
+
+ void cpu1(void)
+ {
+ r1 = smp_load_acquire(&y);
+ r4 = READ_ONCE(v);
+ r5 = READ_ONCE(u);
+ smp_store_release(&z, 1);
+ }
+
+ void cpu2(void)
+ {
+ r2 = smp_load_acquire(&z);
+ smp_store_release(&x, 1);
+ }
+
+ void cpu3(void)
+ {
+ WRITE_ONCE(v, 1);
+ smp_mb();
+ r3 = READ_ONCE(u);
+ }
+
+Because cpu0(), cpu1(), and cpu2() participate in a local transitive
+chain of smp_store_release()/smp_load_acquire() pairs, the following
+outcome is prohibited:
+
+ r0 == 1 && r1 == 1 && r2 == 1
+
+Furthermore, because of the release-acquire relationship between cpu0()
+and cpu1(), cpu1() must see cpu0()'s writes, so that the following
+outcome is prohibited:
+
+ r1 == 1 && r5 == 0
+
+However, the transitivity of release-acquire is local to the participating
+CPUs and does not apply to cpu3(). Therefore, the following outcome
+is possible:
+
+ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
I think you should be completely explicit and include r5 == 1 here, too.
Also -- where would you add the smp_mb__after_release_acquire to fix
(i.e. forbid) this? Immediately after cpu1()'s read of y?
+Although cpu0(), cpu1(), and cpu2() will see their respective reads and
+writes in order, CPUs not involved in the release-acquire chain might
+well disagree on the order. This disagreement stems from the fact that
+the weak memory-barrier instructions used to implement smp_load_acquire()
+and smp_store_release() are not required to order prior stores against
+subsequent loads in all cases. This means that cpu3() can see cpu0()'s
+store to u as happening -after- cpu1()'s load from v, even though
+both cpu0() and cpu1() agree that these two operations occurred in the
+intended order.
+
+However, please keep in mind that smp_load_acquire() is not magic.
+In particular, it simply reads from its argument with ordering. It does
+-not- ensure that any particular value will be read. Therefore, the
+following outcome is possible:
+
+ r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
+
+Note that this outcome can happen even on a mythical sequentially
+consistent system where nothing is ever reordered.
I'm not sure this last bit is strictly necessary. If somebody thinks that
acquire/release involve some sort of implicit synchronisation, I think
they may have bigger problems with memory-barriers.txt.
Will
From: Paul E. McKenney <hidden> Date: 2016-01-26 05:33:42
On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
quoted
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
Nope, it was pretty baffling!
"It is a service that I provide." ;-)
quoted
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
The code above looks correct to me (in that it matches WRC+addrs),
but your litmus test:
You are quite correct! How about the following?
As before, both herd and ppcmem say that the cycle is allowed, as
expected, given non-transitive ordering. To prohibit the cycle, P1
needs a suitable memory-barrier instruction.
Thanx, Paul
------------------------------------------------------------------------
PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
P0 | P1 | P2 ;
stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
| stw r2,0(r8) | lwz r9,0(r8) ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)
--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
From: Paul E. McKenney <hidden> Date: 2016-01-26 06:08:53
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
quoted
On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
quoted
quoted
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
Hoping my memory-barrier.txt patch helps here...
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
Do you have some examples of this? I'm struggling to make it work in my
mind, or are you talking specifically in the context of the kernel
memory model?
Now that you mention it, maybe it would be best to keep the transitive
and non-transitive separate for the time being anyway. Just because it
might be possible to deal with does not necessarily mean that we should
be encouraging it. ;-)
quoted
But I will admit that there are some rather strange litmus tests that
challenge this cycle-centric view, for example, the one shown below.
It turns out that herd and ppcmem disagree on the outcome. (The Power
architects side with ppcmem.)
quoted
And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
of the stores looses a conflict, and if that scenario matters. If it
does, we should inspect the same case for other barriers.
Indeed. I am still working on how these should be described. My
current thought is to be quite conservative on what ordering is
actually respected, however, the current task is formalizing how
RCU plays with the rest of the memory model.
Thanx, Paul
------------------------------------------------------------------------
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
The double negatives don't help here! (it is forbidden to guarantee that
z is not always 2).
Yes, this is a weird one, and I don't know of any use of it.
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-26 06:12:20
On Mon, Jan 25, 2016 at 06:02:34PM +0000, Will Deacon wrote:
Hi Paul,
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
quoted
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
quoted
So smp_mb() provides transitivity, as do pairs of smp_store_release()
and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
Good point!
Using grace periods in place of smp_mb() also provides strong/global
transitivity, but also insanely high latencies. ;-)
The patch below updates Documentation/memory-barriers.txt to define
local vs. global transitivity. The corresponding ppcmem litmus test
is included below as well.
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
I too would like to have the litmus tests in the kernel so that we can
refer to them from memory-barriers.txt. Ideally they wouldn't be targetted
to a particular arch, however.
i.e. we should rewrite this using READ_ONCE/WRITE_ONCE and smp_mb() etc.
Yep!
quoted
------------------------------------------------------------------------
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney [off-list ref]
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra [off-list ref]
Reported-by: Will Deacon [off-list ref]
Signed-off-by: Paul E. McKenney [off-list ref]
@@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes. General barriers are therefore required to ensure that all CPUs agree on the combined order of CPU 1's and CPU 2's accesses.-To reiterate, if your code requires transitivity, use general barriers-throughout.+General barriers provide "global transitivity", so that all CPUs will+agree on the order of operations. In contrast, a chain of release-acquire+pairs provides only "local transitivity", so that only those CPUs on+the chain are guaranteed to agree on the combined order of the accesses.
Thanks for having a go at this. I tried defining something axiomatically,
but got stuck pretty quickly. In my scheme, I used "data-directed
transitivity" instead of "local transitivity", since the latter seems to
be a bit of a misnomer.
I figured that "local" meant local to the CPUs participating in the
release-acquire chain. As opposed to smp_mb() chains where the ordering
is "global" as in visible to all CPUs, whether on the chain or not.
Does that help?
quoted
+For example, switching to C code in deference to Herman Hollerith:
+
+ int u, v, x, y, z;
+
+ void cpu0(void)
+ {
+ r0 = smp_load_acquire(&x);
+ WRITE_ONCE(u, 1);
+ smp_store_release(&y, 1);
+ }
+
+ void cpu1(void)
+ {
+ r1 = smp_load_acquire(&y);
+ r4 = READ_ONCE(v);
+ r5 = READ_ONCE(u);
+ smp_store_release(&z, 1);
+ }
+
+ void cpu2(void)
+ {
+ r2 = smp_load_acquire(&z);
+ smp_store_release(&x, 1);
+ }
+
+ void cpu3(void)
+ {
+ WRITE_ONCE(v, 1);
+ smp_mb();
+ r3 = READ_ONCE(u);
+ }
+
+Because cpu0(), cpu1(), and cpu2() participate in a local transitive
+chain of smp_store_release()/smp_load_acquire() pairs, the following
+outcome is prohibited:
+
+ r0 == 1 && r1 == 1 && r2 == 1
+
+Furthermore, because of the release-acquire relationship between cpu0()
+and cpu1(), cpu1() must see cpu0()'s writes, so that the following
+outcome is prohibited:
+
+ r1 == 1 && r5 == 0
+
+However, the transitivity of release-acquire is local to the participating
+CPUs and does not apply to cpu3(). Therefore, the following outcome
+is possible:
+
+ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
I think you should be completely explicit and include r5 == 1 here, too.
Good point -- I added this as an additional outcome:
r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0 && r5 == 1
Also -- where would you add the smp_mb__after_release_acquire to fix
(i.e. forbid) this? Immediately after cpu1()'s read of y?
That sounds plausible, but we would first have to agree on exactly
what smp_mb__after_release_acquire() did. ;-)
quoted
+Although cpu0(), cpu1(), and cpu2() will see their respective reads and
+writes in order, CPUs not involved in the release-acquire chain might
+well disagree on the order. This disagreement stems from the fact that
+the weak memory-barrier instructions used to implement smp_load_acquire()
+and smp_store_release() are not required to order prior stores against
+subsequent loads in all cases. This means that cpu3() can see cpu0()'s
+store to u as happening -after- cpu1()'s load from v, even though
+both cpu0() and cpu1() agree that these two operations occurred in the
+intended order.
+
+However, please keep in mind that smp_load_acquire() is not magic.
+In particular, it simply reads from its argument with ordering. It does
+-not- ensure that any particular value will be read. Therefore, the
+following outcome is possible:
+
+ r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
+
+Note that this outcome can happen even on a mythical sequentially
+consistent system where nothing is ever reordered.
I'm not sure this last bit is strictly necessary. If somebody thinks that
acquire/release involve some sort of implicit synchronisation, I think
they may have bigger problems with memory-barriers.txt.
Agreed. But unless I add text like this occasionally, such people could
easily read through much of memory-barriers.txt and think that they did
in fact understand it. So I have to occasionally trip an assertion in
their brain. Or try to... :-/
Thanx, Paul
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-26 10:16:37
On Mon, Jan 25, 2016 at 10:12:11PM -0800, Paul E. McKenney wrote:
On Mon, Jan 25, 2016 at 06:02:34PM +0000, Will Deacon wrote:
quoted
Thanks for having a go at this. I tried defining something axiomatically,
but got stuck pretty quickly. In my scheme, I used "data-directed
transitivity" instead of "local transitivity", since the latter seems to
be a bit of a misnomer.
I figured that "local" meant local to the CPUs participating in the
release-acquire chain. As opposed to smp_mb() chains where the ordering
is "global" as in visible to all CPUs, whether on the chain or not.
Does that help?
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-26 10:19:50
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
quoted
quoted
quoted
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
Do you have some examples of this? I'm struggling to make it work in my
mind, or are you talking specifically in the context of the kernel
memory model?
Now that you mention it, maybe it would be best to keep the transitive
and non-transitive separate for the time being anyway. Just because it
might be possible to deal with does not necessarily mean that we should
be encouraging it. ;-)
So isn't smp_mb__after_unlock_lock() exactly such a scenario? And would
not someone trying to implement RCsc locks using locally transitive
RELEASE/ACQUIRE operations need exactly this stuff?
That is, I am afraid we need to cover the mix of local and global
transitive operations at least in overview.
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-26 10:24:13
On Thu, Jan 14, 2016 at 02:20:46PM -0800, Paul E. McKenney wrote:
On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
quoted
So SYNC_RMB is intended to implement smp_rmb(), correct?
Yes.
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
If smp_read_barrier_depends() is used to separate not only two reads
but read pointer and WRITE basing on that pointer (example below) -
yes. I just doesn't see any example of this in famous
Documentation/memory-barriers.txt and had no chance to know what you
use it in this way too.
Well, Documentation/memory-barriers.txt was intended as a guide for Linux
kernel hackers, and not for hardware architects.
Yeah, this goes under the header: memory-barriers.txt is _NOT_ a
specification (I seem to keep repeating this).
------------------------------------------------------------------------
commit 955720966e216b00613fcf60188d507c103f0e80
Author: Paul E. McKenney [off-list ref]
Date: Thu Jan 14 14:17:04 2016 -0800
documentation: Subsequent writes ordered by rcu_dereference()
The current memory-barriers.txt does not address the possibility of
a write to a dereferenced pointer. This should be rare,
How are these rare? Isn't:
rcu_read_lock()
obj = rcu_dereference(ptr);
if (!atomic_inc_not_zero(&obj->ref))
obj = NULL;
rcu_read_unlock();
a _very_ common thing to do?
@@ -1,3 +1,4 @@+ ============================ LINUX KERNEL MEMORY BARRIERS ============================
@@ -5,6 +6,22 @@ By: David Howells <dhowells@redhat.com> Paul E. McKenney <paulmck@linux.vnet.ibm.com>+==========+DISCLAIMER+==========++This document is not a specification; it is intentionally (for the sake of+brevity) and unintentionally (due to being human) incomplete. This document is+meant as a guide to using the various memory barriers provided by Linux, but+in case of any doubt (and there are many) please ask.++I repeat, this document is not a specification of what Linux expects from+hardware.++=====+INDEX+=====+ Contents: (*) Abstract memory access model.
@@ -1,3 +1,4 @@+ ============================ LINUX KERNEL MEMORY BARRIERS ============================
@@ -5,6 +6,22 @@ By: David Howells <dhowells@redhat.com> Paul E. McKenney <paulmck@linux.vnet.ibm.com>+==========+DISCLAIMER+==========++This document is not a specification; it is intentionally (for the sake of+brevity) and unintentionally (due to being human) incomplete. This document is+meant as a guide to using the various memory barriers provided by Linux, but+in case of any doubt (and there are many) please ask.
It might be worth adding you and me to the top of the file, to save Paul
Cc'ing us on questions (get_maintainer.pl points at poor old Corbet for
this file).
But yes, it seems that something like this is required.
Will
From: Will Deacon <hidden> Date: 2016-01-26 12:10:27
On Mon, Jan 25, 2016 at 05:06:46PM -0800, Paul E. McKenney wrote:
On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
quoted
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
Nope, it was pretty baffling!
"It is a service that I provide." ;-)
quoted
quoted
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
The code above looks correct to me (in that it matches WRC+addrs),
but your litmus test:
From: Will Deacon <hidden> Date: 2016-01-26 12:16:21
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
Tricky, but I think it still works out if the coherence order of z is as
I described above. The line of reasoning is weird though -- I ended up
considering the two cases where P0 reads z before and after it reads x
and what that means for the read of y.
Will
Hi Will,
On Tue, Jan 26, 2016 at 12:16:09PM +0000, Will Deacon wrote:
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
Tricky, but I think it still works out if the coherence order of z is as
I described above. The line of reasoning is weird though -- I ended up
considering the two cases where P0 reads z before and after it reads x
^^^^^^^^^^^^^^^
Because of the fact that two reads on the same processors can't be
executed simultaneously? I feel like this is exactly something herd
missed.
and what that means for the read of y.
And the reasoning on PPC is similar, so looks like the read of z on P0
is a necessary condition for the exists clause to be forbidden.
Regards,
Boqun
Hi Paul,
On Mon, Jan 18, 2016 at 07:46:29AM -0800, Paul E. McKenney wrote:
On Mon, Jan 18, 2016 at 04:19:29PM +0800, Herbert Xu wrote:
quoted
Paul E. McKenney [off-list ref] wrote:
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer. For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
Does that help?
This is crazy! smp_rmb started out being strictly stronger than
smp_read_barrier_depends, when did this stop being the case?
Hello, Herbert!
It is true that most Linux kernel code relies only on the read-read
properties of dependencies, but the read-write properties are useful.
Admittedly relatively rarely, but useful.
The better comparison for smp_read_barrier_depends(), especially in
its rcu_dereference*() form, is smp_load_acquire().
Confused..
I recall that last time you and Linus came into a conclusion that even
on Alpha, a barrier for read->write with data dependency is unnecessary:
http://article.gmane.org/gmane.linux.kernel/2077661
And in an earlier mail of that thread, Linus made his point that
smp_read_barrier_depends() should only be used to order read->read.
So right now, are we going to extend the semantics of
smp_read_barrier_depends()? Can we just make smp_read_barrier_depends()
still only work for read->read, and assume all the architectures won't
reorder read->write with data dependency, so that the code above having
a smp_rmb() also works?
Regards,
Boqun
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-26 17:23:18
On Wed, Jan 27, 2016 at 12:52:07AM +0800, Boqun Feng wrote:
I recall that last time you and Linus came into a conclusion that even
on Alpha, a barrier for read->write with data dependency is unnecessary:
http://article.gmane.org/gmane.linux.kernel/2077661
And in an earlier mail of that thread, Linus made his point that
smp_read_barrier_depends() should only be used to order read->read.
So right now, are we going to extend the semantics of
smp_read_barrier_depends()? Can we just make smp_read_barrier_depends()
still only work for read->read, and assume all the architectures won't
reorder read->write with data dependency, so that the code above having
a smp_rmb() also works?
That discussions was about control dependencies. So writes that _depend_
on a prior read having an explicit value.
So something like:
struct foo *x = READ_ONCE(*ptr);
smp_read_barrier_depends()
if (x->val == 5)
x->bar = 5;
In that case, the load of x->val must be complete and its value
determined _before_ the store to x->bar can happen.
This is distinct from:
struct foo *x = READ_ONCE(*ptr);
smp_read_barrier_depends();
x->bar = 5;
And its the second case where smp_read_barrier_depends() read->write
order matters.
This case is complete BS. Stop perpetuating it. I already removed a
number of bogus cases of it, and I removed the incorrect documentation
that had this crap.
It's called "smp_READ_barrier_depends()" for a reason.
Alpha is the only one that needs it, and alpha needs it only for
dependent READS.
It's not called smp_read_write_barrier_depends(). It's not called
"smp_mb_depends()". It's a weaker form of "smp_rmb()", nothing else.
So alpha does have an implied dependency chain from a read to a
subsequent dependent write, and does not need any extra barriers.
Alpha does *not* have a dependency chain from a read to a subsequent
read, which is why we need that horrible crappy
smp_read_barrier_depends(). But it's the only reason.
This is the alpha reference manual wrt read-to-write dependency:
5.6.1.7 Definition of Dependence Constraint
The depends relation (DP) is defined as follows. Given u and v
issued by processor Pi, where u
is a read or an instruction fetch and v is a write, u precedes v
in DP order (written u DP v, that
is, v depends on u) in either of the following situations:
=E2=80=A2 u determines the execution of v, the location accessed by v,=
or
the value written by v.
=E2=80=A2 u determines the execution or address or value of another
memory access z that precedes
v or might precede v (that is, would precede v in some execution
path depending
on the value read by u) by processor issue constraint (see Section 5.6.=
1.3).
Note that the dependence barrier honors not only control flow, but
address and data values too. This is a different syntax than we use,
but 'u' is the READ_ONCE, and 'v' is the write. Any data, address or
conditional dependency between the two implies an ordering.
So no, "smp_read_barrier_depends()" is *ONLY* about two reads, where
the second read is data-dependent on the first. Nothing else.
So if you _ever_ see a "smp_read_barrier_depends()" that isn't about a
barrier between two reads, then that is a bug.
The above code is crap. It's exactly as much crap as
a =3D READ_ONCE(x);
smp_rmb();
WRITE_ONCE(b, y);
because a "rmb()" simply doesn't have anything to do with
read-vs-subsequent-write ordering.
Linus
From: Paul E. McKenney <hidden> Date: 2016-01-26 22:00:04
On Tue, Jan 26, 2016 at 12:16:09PM +0000, Will Deacon wrote:
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
Tricky, but I think it still works out if the coherence order of z is as
I described above. The line of reasoning is weird though -- I ended up
considering the two cases where P0 reads z before and after it reads x
and what that means for the read of y.
By "works out" you mean that ARM prohibits the outcome?
BTW, I never have seen a real-world use for this case. At the moment
it is mostly a cautionary tale about memory-model corner cases and
tools.
Thanx, Paul
This case is complete BS. Stop perpetuating it. I already removed a
number of bogus cases of it, and I removed the incorrect documentation
that had this crap.
If I understand your objection correctly, you want the above pattern
expressed either like this:
struct foo *x = rcu_dereference(*ptr);
x->bar = 5;
Or like this:
struct foo *x = lockless_dereference(*ptr);
x->bar = 5;
Or am I missing your point?
It's called "smp_READ_barrier_depends()" for a reason.
Alpha is the only one that needs it, and alpha needs it only for
dependent READS.
It's not called smp_read_write_barrier_depends(). It's not called
"smp_mb_depends()". It's a weaker form of "smp_rmb()", nothing else.
So alpha does have an implied dependency chain from a read to a
subsequent dependent write, and does not need any extra barriers.
Alpha does *not* have a dependency chain from a read to a subsequent
read, which is why we need that horrible crappy
smp_read_barrier_depends(). But it's the only reason.
This is the alpha reference manual wrt read-to-write dependency:
5.6.1.7 Definition of Dependence Constraint
The depends relation (DP) is defined as follows. Given u and v
issued by processor Pi, where u
is a read or an instruction fetch and v is a write, u precedes v
in DP order (written u DP v, that
is, v depends on u) in either of the following situations:
• u determines the execution of v, the location accessed by v, or
the value written by v.
• u determines the execution or address or value of another
memory access z that precedes
v or might precede v (that is, would precede v in some execution
path depending
on the value read by u) by processor issue constraint (see Section 5.6.1.3).
Note that the dependence barrier honors not only control flow, but
address and data values too. This is a different syntax than we use,
but 'u' is the READ_ONCE, and 'v' is the write. Any data, address or
conditional dependency between the two implies an ordering.
So no, "smp_read_barrier_depends()" is *ONLY* about two reads, where
the second read is data-dependent on the first. Nothing else.
So if you _ever_ see a "smp_read_barrier_depends()" that isn't about a
barrier between two reads, then that is a bug.
And the smp_read_barrier_depends() in both rcu_dereference() and
in lockless_dereference() is ordering the read-to-read case and the
underlying hardware is ordering the read-to-write case on weakly ordered
hardware.
Or, again, am I missing your point?
Thanx, Paul
The above code is crap. It's exactly as much crap as
a = READ_ONCE(x);
smp_rmb();
WRITE_ONCE(b, y);
because a "rmb()" simply doesn't have anything to do with
read-vs-subsequent-write ordering.
Linus
From: Paul E. McKenney <hidden> Date: 2016-01-26 22:00:37
On Tue, Jan 26, 2016 at 11:24:02AM +0100, Peter Zijlstra wrote:
On Thu, Jan 14, 2016 at 02:20:46PM -0800, Paul E. McKenney wrote:
quoted
On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
quoted
On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
quoted
So SYNC_RMB is intended to implement smp_rmb(), correct?
Yes.
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
If smp_read_barrier_depends() is used to separate not only two reads
but read pointer and WRITE basing on that pointer (example below) -
yes. I just doesn't see any example of this in famous
Documentation/memory-barriers.txt and had no chance to know what you
use it in this way too.
Well, Documentation/memory-barriers.txt was intended as a guide for Linux
kernel hackers, and not for hardware architects.
Yeah, this goes under the header: memory-barriers.txt is _NOT_ a
specification (I seem to keep repeating this).
quoted
------------------------------------------------------------------------
commit 955720966e216b00613fcf60188d507c103f0e80
Author: Paul E. McKenney [off-list ref]
Date: Thu Jan 14 14:17:04 2016 -0800
documentation: Subsequent writes ordered by rcu_dereference()
The current memory-barriers.txt does not address the possibility of
a write to a dereferenced pointer. This should be rare,
How are these rare? Isn't:
rcu_read_lock()
obj = rcu_dereference(ptr);
if (!atomic_inc_not_zero(&obj->ref))
obj = NULL;
rcu_read_unlock();
a _very_ common thing to do?
It is, but it provides its own barriers, so does not need to rely on
dependency ordering.
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-26 22:00:45
On Tue, Jan 26, 2016 at 11:19:27AM +0100, Peter Zijlstra wrote:
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
quoted
quoted
quoted
quoted
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
Do you have some examples of this? I'm struggling to make it work in my
mind, or are you talking specifically in the context of the kernel
memory model?
Now that you mention it, maybe it would be best to keep the transitive
and non-transitive separate for the time being anyway. Just because it
might be possible to deal with does not necessarily mean that we should
be encouraging it. ;-)
So isn't smp_mb__after_unlock_lock() exactly such a scenario? And would
not someone trying to implement RCsc locks using locally transitive
RELEASE/ACQUIRE operations need exactly this stuff?
That is, I am afraid we need to cover the mix of local and global
transitive operations at least in overview.
True, but we haven't gotten to locking yet. That said, I would argue
that smp_mb__after_unlock_lock() upgrades locks to transitive, and
thus would not be an exception to the "no combining transitive and
non-transitive steps in cycles" rule.
Thanx, Paul
@@ -1,3 +1,4 @@+ ============================ LINUX KERNEL MEMORY BARRIERS ============================
@@ -5,6 +6,22 @@ By: David Howells <dhowells@redhat.com> Paul E. McKenney <paulmck@linux.vnet.ibm.com>+==========+DISCLAIMER+==========++This document is not a specification; it is intentionally (for the sake of+brevity) and unintentionally (due to being human) incomplete. This document is+meant as a guide to using the various memory barriers provided by Linux, but+in case of any doubt (and there are many) please ask.
It might be worth adding you and me to the top of the file, to save Paul
Cc'ing us on questions (get_maintainer.pl points at poor old Corbet for
this file).
But yes, it seems that something like this is required.
So Peter, would you like to update your patch to include yourself
and Will as authors?
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-26 22:01:56
On Wed, Jan 27, 2016 at 12:52:07AM +0800, Boqun Feng wrote:
Hi Paul,
On Mon, Jan 18, 2016 at 07:46:29AM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 18, 2016 at 04:19:29PM +0800, Herbert Xu wrote:
quoted
Paul E. McKenney [off-list ref] wrote:
quoted
You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
The reason for this is that smp_read_barrier_depends() must order the
pointer load against any subsequent read or write through a dereference
of that pointer. For example:
p = READ_ONCE(gp);
smp_rmb();
r1 = p->a; /* ordered by smp_rmb(). */
p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
In contrast:
p = READ_ONCE(gp);
smp_read_barrier_depends();
r1 = p->a; /* ordered by smp_read_barrier_depends(). */
p->b = 42; /* ordered by smp_read_barrier_depends(). */
r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
Again, if your hardware maintains local ordering for address
and data dependencies, you can have read_barrier_depends() and
smp_read_barrier_depends() be no-ops like they are for most
architectures.
Does that help?
This is crazy! smp_rmb started out being strictly stronger than
smp_read_barrier_depends, when did this stop being the case?
Hello, Herbert!
It is true that most Linux kernel code relies only on the read-read
properties of dependencies, but the read-write properties are useful.
Admittedly relatively rarely, but useful.
The better comparison for smp_read_barrier_depends(), especially in
its rcu_dereference*() form, is smp_load_acquire().
Confused..
I recall that last time you and Linus came into a conclusion that even
on Alpha, a barrier for read->write with data dependency is unnecessary:
http://article.gmane.org/gmane.linux.kernel/2077661
And in an earlier mail of that thread, Linus made his point that
smp_read_barrier_depends() should only be used to order read->read.
Those examples involved read-to-write with conditionals, as in:
if (READ_ONCE(a))
WRITE_ONCE(b, 1);
Without the "if", no ordering is guaranteed on weakly ordered CPUs.
(The volatile accesses keep ordering within the compiler for once...
So right now, are we going to extend the semantics of
smp_read_barrier_depends()? Can we just make smp_read_barrier_depends()
still only work for read->read, and assume all the architectures won't
reorder read->write with data dependency, so that the code above having
a smp_rmb() also works?
The semantics of smp_read_barrier_depends() has been both read-to-write
and read-to-read for some time now, this patch just catches the
documentation up with reality.
Thanx, Paul
This case is complete BS. Stop perpetuating it. I already removed a
number of bogus cases of it, and I removed the incorrect documentation
that had this crap.
If I understand your objection correctly, you want the above pattern
expressed either like this:
struct foo *x = rcu_dereference(*ptr);
x->bar = 5;
Or like this:
struct foo *x = lockless_dereference(*ptr);
x->bar = 5;
Or am I missing your point?
You are entirely missing the point.
You might as well just write it as
struct foo x = READ_ONCE(*ptr);
x->bar = 5;
because that "smp_read_barrier_depends()" does NOTHING wrt the second write.
So what I am saying is simple: anybody who writes that
"smp_read_barrier_depends()" in there is just ttoally and completely
WRONG, and the fact that Peter wrote it out after I removed several
instances of that bloody f*cking idiocy is disturbing.
Don't do it. It's BS. It's wrong. Don't make excuses for it.
Linus
On Tue, Jan 26, 2016 at 2:15 PM, Linus Torvalds
[off-list ref] wrote:
You might as well just write it as
struct foo x = READ_ONCE(*ptr);
x->bar = 5;
because that "smp_read_barrier_depends()" does NOTHING wrt the second write.
Just to clarify: on alpha it adds a memory barrier, but that memory
barrier is useless.
On non-alpha, it is a no-op, and obviously does nothing simply because
it generates no code.
So if anybody believes that the "smp_read_barrier_depends()" does
something, they are *wrong*.
And if anybody sends out an email with that smp_read_barrier_depends()
in an example, they are actively just confusing other people, which is
even worse than just being wrong. Which is why I jumped in.
So stop perpetuating the myth that smp_read_barrier_depends() does
something here. It does not. It's a bug, and it has become this "mind
virus" for some people that seem to believe that it does something.
I had to remove this crap once from the kernel already, see commit
105ff3cbf225 ("atomic: remove all traces of READ_ONCE_CTRL() and
atomic*_read_ctrl()").
I don't want to ever see that broken construct again. And I want to
make sure that everybody is educated about how broken it was. I'm
extremely unhappy that it came up again.
If it turns out that some architecture does actually need a barrier
between a read and a dependent write, then that will mean that
(a) we'll have to make up a _new_ barrier, because
"smp_read_barrier_depends()" is not that barrier. We'll presumably
then have to make that new barrier part of "rcu_derefence()" and
friends.
(b) we will have found an architecture with even worse memory
ordering semantics than alpha, and we'll have to stop castigating
alpha for being the worst memory ordering ever.
but I sincerely hope that we'll never find that kind of broken architecture.
Linus
From: Paul E. McKenney <hidden> Date: 2016-01-26 23:29:31
On Tue, Jan 26, 2016 at 02:33:40PM -0800, Linus Torvalds wrote:
On Tue, Jan 26, 2016 at 2:15 PM, Linus Torvalds
[off-list ref] wrote:
quoted
You might as well just write it as
struct foo x = READ_ONCE(*ptr);
x->bar = 5;
because that "smp_read_barrier_depends()" does NOTHING wrt the second write.
Just to clarify: on alpha it adds a memory barrier, but that memory
barrier is useless.
No trailing data-dependent read, so agreed, no smp_read_barrier_depends()
needed. That said, I believe that we should encourage rcu_dereference*()
or lockless_dereference() instead of READ_ONCE() for documentation
reasons, though.
On non-alpha, it is a no-op, and obviously does nothing simply because
it generates no code.
So if anybody believes that the "smp_read_barrier_depends()" does
something, they are *wrong*.
The other problem with smp_read_barrier_depends() is that it is often
a pain figuring out which prior load it is supposed to apply to.
Hence my preference for rcu_dereference*() and lockless_dereference().
And if anybody sends out an email with that smp_read_barrier_depends()
in an example, they are actively just confusing other people, which is
even worse than just being wrong. Which is why I jumped in.
So stop perpetuating the myth that smp_read_barrier_depends() does
something here. It does not. It's a bug, and it has become this "mind
virus" for some people that seem to believe that it does something.
It looks like I should add words to memory-barriers.txt de-emphasizing
smp_read_barrier_depends(). I will take a look at that.
I had to remove this crap once from the kernel already, see commit
105ff3cbf225 ("atomic: remove all traces of READ_ONCE_CTRL() and
atomic*_read_ctrl()").
I don't want to ever see that broken construct again. And I want to
make sure that everybody is educated about how broken it was. I'm
extremely unhappy that it came up again.
Well, if it makes you feel better, that was control dependencies and this
was data dependencies. So it was not -exactly- the same. ;-)
(Sorry, couldn't resist...)
If it turns out that some architecture does actually need a barrier
between a read and a dependent write, then that will mean that
(a) we'll have to make up a _new_ barrier, because
"smp_read_barrier_depends()" is not that barrier. We'll presumably
then have to make that new barrier part of "rcu_derefence()" and
friends.
Agreed. We can worry about whether or not we replace the current
smp_read_barrier_depends() with that new barrier when and if such
hardware appears.
(b) we will have found an architecture with even worse memory
ordering semantics than alpha, and we'll have to stop castigating
alpha for being the worst memory ordering ever.
;-) ;-) ;-)
but I sincerely hope that we'll never find that kind of broken architecture.
Apparently at least some hardware vendors are reading memory-barriers.txt,
so perhaps the odds of that kind of breakage have reduced.
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-26 23:37:48
On Tue, Jan 26, 2016 at 12:10:10PM +0000, Will Deacon wrote:
On Mon, Jan 25, 2016 at 05:06:46PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
quoted
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
quoted
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
Nope, it was pretty baffling!
"It is a service that I provide." ;-)
quoted
quoted
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
The code above looks correct to me (in that it matches WRC+addrs),
but your litmus test:
As before, both herd and ppcmem say that the cycle is allowed, as
expected, given non-transitive ordering. To prohibit the cycle, P1
needs a suitable memory-barrier instruction.
------------------------------------------------------------------------
PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
P0 | P1 | P2 ;
stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
| stw r2,0(r8) | lwz r9,0(r8) ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)
Agreed.
OK, thank you! Would you agree that it would be good to replace the
current xor-based fake-dependency litmus tests with tests having real
dependencies?
Thanx, Paul
On Tue, Jan 26, 2016 at 3:29 PM, Paul E. McKenney
[off-list ref] wrote:
No trailing data-dependent read, so agreed, no smp_read_barrier_depends()
needed. That said, I believe that we should encourage rcu_dereference*()
or lockless_dereference() instead of READ_ONCE() for documentation
reasons, though.
I agree that that is likely the right thing to do in pretty much all situations.
In theory, there might be performance situations where we'd want to
actively avoid the smp_read_barrier_depends() inherent in those, but
considering that it's only a performance issue on alpha, and we
probably have all of two or three people using Linux on alpha, it's a
pretty theoretical performance worry.
Linus
From: Paul E. McKenney <hidden> Date: 2016-01-27 00:57:44
On Tue, Jan 26, 2016 at 03:45:23PM -0800, Linus Torvalds wrote:
On Tue, Jan 26, 2016 at 3:29 PM, Paul E. McKenney
[off-list ref] wrote:
quoted
No trailing data-dependent read, so agreed, no smp_read_barrier_depends()
needed. That said, I believe that we should encourage rcu_dereference*()
or lockless_dereference() instead of READ_ONCE() for documentation
reasons, though.
I agree that that is likely the right thing to do in pretty much all situations.
In theory, there might be performance situations where we'd want to
actively avoid the smp_read_barrier_depends() inherent in those, but
considering that it's only a performance issue on alpha, and we
probably have all of two or three people using Linux on alpha, it's a
pretty theoretical performance worry.
On Tue, Jan 26, 2016 at 03:29:21PM -0800, Paul E. McKenney wrote:
On Tue, Jan 26, 2016 at 02:33:40PM -0800, Linus Torvalds wrote:
quoted
On Tue, Jan 26, 2016 at 2:15 PM, Linus Torvalds
[off-list ref] wrote:
quoted
You might as well just write it as
struct foo x = READ_ONCE(*ptr);
x->bar = 5;
because that "smp_read_barrier_depends()" does NOTHING wrt the second write.
Just to clarify: on alpha it adds a memory barrier, but that memory
barrier is useless.
No trailing data-dependent read, so agreed, no smp_read_barrier_depends()
needed. That said, I believe that we should encourage rcu_dereference*()
or lockless_dereference() instead of READ_ONCE() for documentation
reasons, though.
quoted
On non-alpha, it is a no-op, and obviously does nothing simply because
it generates no code.
So if anybody believes that the "smp_read_barrier_depends()" does
something, they are *wrong*.
The other problem with smp_read_barrier_depends() is that it is often
a pain figuring out which prior load it is supposed to apply to.
Hence my preference for rcu_dereference*() and lockless_dereference().
Because semantically speaking, rcu_derefence*() and
lockless_dereference() are CONSUME(i.e. data/address dependent
read->read and read->write pairs are ordered), whereas
smp_read_barrier_depends() only guarantees read->read pairs with data
dependency are ordered, right?
If so, maybe we need to call it out in memory-barriers.txt, for example:
@@ -1703,8 +1703,8 @@ There are some more advanced barrier functions: (*) lockless_dereference();- This can be thought of as a pointer-fetch wrapper around the- smp_read_barrier_depends() data-dependency barrier.+ This is a load, and any load or store that has a data dependency on the+ value returned by this load won't be reordered before this load. This is also similar to rcu_dereference(), but in cases where object lifetime is handled by some mechanism other than RCU, for
Regards,
Boqun
quoted
And if anybody sends out an email with that smp_read_barrier_depends()
in an example, they are actively just confusing other people, which is
even worse than just being wrong. Which is why I jumped in.
So stop perpetuating the myth that smp_read_barrier_depends() does
something here. It does not. It's a bug, and it has become this "mind
virus" for some people that seem to believe that it does something.
It looks like I should add words to memory-barriers.txt de-emphasizing
smp_read_barrier_depends(). I will take a look at that.
quoted
I had to remove this crap once from the kernel already, see commit
105ff3cbf225 ("atomic: remove all traces of READ_ONCE_CTRL() and
atomic*_read_ctrl()").
I don't want to ever see that broken construct again. And I want to
make sure that everybody is educated about how broken it was. I'm
extremely unhappy that it came up again.
Well, if it makes you feel better, that was control dependencies and this
was data dependencies. So it was not -exactly- the same. ;-)
(Sorry, couldn't resist...)
quoted
If it turns out that some architecture does actually need a barrier
between a read and a dependent write, then that will mean that
(a) we'll have to make up a _new_ barrier, because
"smp_read_barrier_depends()" is not that barrier. We'll presumably
then have to make that new barrier part of "rcu_derefence()" and
friends.
Agreed. We can worry about whether or not we replace the current
smp_read_barrier_depends() with that new barrier when and if such
hardware appears.
quoted
(b) we will have found an architecture with even worse memory
ordering semantics than alpha, and we'll have to stop castigating
alpha for being the worst memory ordering ever.
;-) ;-) ;-)
quoted
but I sincerely hope that we'll never find that kind of broken architecture.
Apparently at least some hardware vendors are reading memory-barriers.txt,
so perhaps the odds of that kind of breakage have reduced.
Thanx, Paul
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-27 07:52:08
On Tue, Jan 26, 2016 at 02:33:40PM -0800, Linus Torvalds wrote:
If it turns out that some architecture does actually need a barrier
between a read and a dependent write, then that will mean that
(a) we'll have to make up a _new_ barrier, because
"smp_read_barrier_depends()" is not that barrier. We'll presumably
then have to make that new barrier part of "rcu_derefence()" and
friends.
(b) we will have found an architecture with even worse memory
ordering semantics than alpha, and we'll have to stop castigating
alpha for being the worst memory ordering ever.
but I sincerely hope that we'll never find that kind of broken architecture.
So for a moment it looked like MIPS wanted to equal or surpass Alpha in
this respect.
And Paul made the point that smp_read_barrier_depends() really should
be smp_aquire_barrier_depends() in that we rely on both dependent reads
and writes to be ordered against the initial pointer load.
Now, as you've made abundantly clear, Alpha does this, although it needs
the little extra help in the dependent read department.
The 'problem' is that someone seemed to have used our
Documentation/memory-barriers.txt as a specification for what hardware
is permitted and we require. And in that light Paul noted that
read_barrier_depends really should be considered an
acquire_barrier_depends and order both dependent reads and writes
against the (prior) read (if nothing else already does).
Now clearly, any sane architecture doesn't need anything like this, but
again our document doesn't seem to judge. That is, from reading the
document one can get the impression is a perfectly fine thing to do.
Nowhere does our disdain for this thing show.
On Jan 26, 2016 23:51, "Peter Zijlstra" [off-list ref] wrote:
So for a moment it looked like MIPS wanted to equal or surpass Alpha in
this respect.
If there is an architecture that I'd expect to try to take the "sucks more"
crown, MIPS would be it. They've already done the "worst cache award"
thing, and are proud members of the "stupid branch delay slot" crowd. MIPS
historically even did the "delayed load slot".
The only mistake they've never done, AFAIK, is to have a rotating register
file.
At the same time, the "load-to-dependent-store" thing you really have to
*work* at doing wrong. It's not enough to just have bad taste and
incompetent architects. You really have to spend real effort to screw up
that badly. It's really hard to do by mistake.
So I suspect that even MIPS can't get it wrong.
Linus
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-27 08:36:20
On Tue, Jan 26, 2016 at 12:11:43PM -0800, Paul E. McKenney wrote:
So Peter, would you like to update your patch to include yourself
and Will as authors?
Sure, here goes.
---
Subject: documentation: Add disclaimer
It appears people are reading this document as a requirements list for
building hardware. This is not the intent of this document. Nor is it
particularly suited for this purpose.
The primary purpose of this document is our collective attempt to define
a set of primitives that (hopefully) allow us to write correct code on
the myriad of SMP platforms Linux supports.
Its a definite work in progress as our understanding of these platforms,
and memory ordering in general, progresses.
Nor does being mentioned in this document mean we think its a
particularly good idea; the data dependency barrier required by Alpha
being a prime example. Yes we have it, no you're insane to require it
when building new hardware.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
Documentation/memory-barriers.txt | 18 +++++++++++++++++-
1 file changed, 17 insertions(+), 1 deletion(-)
@@ -4,8 +4,24 @@ By: David Howells <dhowells@redhat.com> Paul E. McKenney <paulmck@linux.vnet.ibm.com>+ Will Deacon <will.deacon@arm.com>+ Peter Zijlstra <peterz@infradead.org>-Contents:+==========+DISCLAIMER+==========++This document is not a specification; it is intentionally (for the sake of+brevity) and unintentionally (due to being human) incomplete. This document is+meant as a guide to using the various memory barriers provided by Linux, but+in case of any doubt (and there are many) please ask.++I repeat, this document is not a specification of what Linux expects from+hardware.++========+CONTENTS+======== (*) Abstract memory access model.
From: Peter Zijlstra <peterz@infradead.org> Date: 2016-01-27 08:39:37
On Tue, Jan 26, 2016 at 12:13:39PM -0800, Paul E. McKenney wrote:
On Tue, Jan 26, 2016 at 11:19:27AM +0100, Peter Zijlstra wrote:
quoted
So isn't smp_mb__after_unlock_lock() exactly such a scenario? And would
not someone trying to implement RCsc locks using locally transitive
RELEASE/ACQUIRE operations need exactly this stuff?
That is, I am afraid we need to cover the mix of local and global
transitive operations at least in overview.
True, but we haven't gotten to locking yet.
The mythical smp_mb__after_release_acquire() then ;-)
(and yes, I know you're going to say we don't have that)
That said, I would argue
that smp_mb__after_unlock_lock() upgrades locks to transitive, and
thus would not be an exception to the "no combining transitive and
non-transitive steps in cycles" rule.
But But But ;-) It does that exactly by combining. I suspect this is
(partly) the source of your SC chains with one PC link example.
From: Will Deacon <hidden> Date: 2016-01-27 10:12:10
On Wed, Jan 27, 2016 at 09:35:46AM +0100, Peter Zijlstra wrote:
On Tue, Jan 26, 2016 at 12:11:43PM -0800, Paul E. McKenney wrote:
quoted
So Peter, would you like to update your patch to include yourself
and Will as authors?
Sure, here goes.
---
Subject: documentation: Add disclaimer
It appears people are reading this document as a requirements list for
building hardware. This is not the intent of this document. Nor is it
particularly suited for this purpose.
The primary purpose of this document is our collective attempt to define
a set of primitives that (hopefully) allow us to write correct code on
the myriad of SMP platforms Linux supports.
Its a definite work in progress as our understanding of these platforms,
and memory ordering in general, progresses.
Nor does being mentioned in this document mean we think its a
particularly good idea; the data dependency barrier required by Alpha
being a prime example. Yes we have it, no you're insane to require it
when building new hardware.
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
Documentation/memory-barriers.txt | 18 +++++++++++++++++-
1 file changed, 17 insertions(+), 1 deletion(-)
OK, thank you! Would you agree that it would be good to replace the
current xor-based fake-dependency litmus tests with tests having real
dependencies?
Yes, because it would look a lot more like real (kernel) code.
Will
From: Will Deacon <hidden> Date: 2016-01-27 10:26:08
On Tue, Jan 26, 2016 at 11:58:20AM -0800, Paul E. McKenney wrote:
On Tue, Jan 26, 2016 at 12:16:09PM +0000, Will Deacon wrote:
quoted
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
Tricky, but I think it still works out if the coherence order of z is as
I described above. The line of reasoning is weird though -- I ended up
considering the two cases where P0 reads z before and after it reads x
and what that means for the read of y.
By "works out" you mean that ARM prohibits the outcome?
On Thu, Jan 14, 2016 at 04:47:53PM -0800, Paul E. McKenney wrote:
So you need to build a different kernel for some types of MIPS systems?
Yes. We can't really do without. Classic MIPS code is not relocatable
without the complexity of PIC code as used by ELF DSOs - and their
performanc penalty. Plus we have a number of architecture revisions
ovr the decades, big and little endian, 32 and 64 bit as the major
stumbling stones. There however are groups of similar systems that
can share kernel binaries.
Or do you do boot-time rewriting, like a number of other arches do?
We don't rewrite the code (as in the .text of the vmlinux binary) but we
do runtime code generation for a few highly performance sensitive area
of the kernel code such as copy_page() or TLB exception handlers. This
allows more flexibility than just inserting templates into the kernel
code. Downside - it means we have some of the complexity of as and ld
in the kernel.
Ralf
From: Maciej W. Rozycki <hidden> Date: 2016-01-27 11:26:12
On Fri, 15 Jan 2016, Leonid Yegoshin wrote:
quoted
So you need to build a different kernel for some types of MIPS systems?
Or do you do boot-time rewriting, like a number of other arches do?
I don't know. I would like to have responses. Ralf asked Maciej about old
systems and that came nowhere. Even rewrite - don't know what to do with that:
no lightweight SYNC or no SYNC at all - yes, it is still possible that SYNC on
some systems can be too heavy or even harmful, nobody tested that.
I don't recall being asked; mind that I might not get to messages I have
not been cc-ed in a timely manner and I may miss some altogether. With
the amount of mailing list traffic that passes by me my scanner may fail
to trigger. Sorry if this causes anybody trouble, but such is life.
Coincidentally, I have just posted some notes on SYNC in a different
thread, see <http://lkml.iu.edu/hypermail/linux/kernel/1601.3/03080.html>.
There's a reference to an older message of mine there too. I hope this
answers your questions.
Maciej
From: Maciej W. Rozycki <hidden> Date: 2016-01-27 12:09:10
On Wed, 27 Jan 2016, Ralf Baechle wrote:
quoted
So you need to build a different kernel for some types of MIPS systems?
Yes. We can't really do without. Classic MIPS code is not relocatable
without the complexity of PIC code as used by ELF DSOs - and their
performanc penalty. Plus we have a number of architecture revisions
ovr the decades, big and little endian, 32 and 64 bit as the major
stumbling stones. There however are groups of similar systems that
can share kernel binaries.
Matt (cc-ed) has recently posted patches to add support for a relocatable
kernel, implemented without the usual overhead of PIC code. It works by
retaining relocations in a fully-linked binary and then simply replaying
the work the static linker does when assigning addresses, as the image
loaded is copied to its intended destination at an early bootstrap stage.
See:
<http://www.linux-mips.org/cgi-bin/mesg.cgi?a=linux-mips&i=1449137297-30464-1-git-send-email-matt.redfearn%40imgtec.com>
for details.
I think this framework can be reused by carefully choosing instructions
used in early bootstrap code, up to the relocation stage, so that it is
runnable anywhere (not the same as PIC!) like early ld.so initialisation
and then loading the whole attached image starting from an address where
RAM does exist on target hardware.
Endianness is a different matter, obviously we can't build a single image
for both, although for distributions' sake an approach similar to one used
with bi-endian firmware (for hardware which has an easy way to switch the
endianness, e.g. a physical jumper or a configuration bit stored in flash
memory; not to be confused with the reverse user endianness mode) might be
feasible, by glueing two kernel images together and then selecting the
right one early in bootstrap, perhaps again reusing Matt's framework.
I'm not sure if this is worth the effort though, I suspect the usage level
of this feature would be minimal.
All in all I think making a generic MIPS kernel just might be feasible,
but with the diversity of options available the effort required would be
enormous. NetBSD for example I believe supports building a kernel that
correctly runs on both R3000 (MIPS I, 32-bit) and R4000 (MIPS III, 64-bit)
DEC hardware (as did DEC Ultrix, the vendor OS for these systems). These
processors are different enough from each other that you cannot use the
same code for cache, memory and exception management in an OS kernel --
backward compatibility is only provided for user software. That proves
the concept, however in a very limited way only, not even covering SMP,
and their R4000 kernel does not support 64-bit userland I believe. They
still have completely separate ports for other MIPS hardware, such as for
Broadcom SiByte SB-1 (MIPS64r1) processors.
Maciej
From: David Howells <dhowells@redhat.com> Date: 2016-01-27 14:57:21
Peter Zijlstra [off-list ref] wrote:
+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
+DISCLAIMER
+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
+
+This document is not a specification; it is intentionally (for the sake=
of
+brevity) and unintentionally (due to being human) incomplete. This docu=
ment is
+meant as a guide to using the various memory barriers provided by Linux=
, but
+in case of any doubt (and there are many) please ask.
+
+I repeat, this document is not a specification of what Linux expects fr=
om
+hardware.
The purpose of this document is twofold:
(1) to specify the minimum functionality that one can rely on for any
particular barrier, and
(2) to provide a guide as to how to use the barriers that are available.
Note that an architecture can provide more than the minimum requirement fo=
r
any particular barrier, but if the barrier provides less than that, it is
incorrect.
Note also that it is possible that a barrier may be a no-op for an
architecture because the way that arch works renders an explicit barrier
unnecessary in that case.
+
Can you bung an extra blank line in here if you have to redo this at all?
From: Paul E. McKenney <hidden> Date: 2016-01-28 00:40:52
On Wed, Jan 27, 2016 at 10:25:46AM +0000, Will Deacon wrote:
On Tue, Jan 26, 2016 at 11:58:20AM -0800, Paul E. McKenney wrote:
quoted
On Tue, Jan 26, 2016 at 12:16:09PM +0000, Will Deacon wrote:
quoted
On Mon, Jan 25, 2016 at 10:03:22PM -0800, Paul E. McKenney wrote:
quoted
On Mon, Jan 25, 2016 at 04:42:43PM +0000, Will Deacon wrote:
quoted
On Fri, Jan 15, 2016 at 01:58:53PM -0800, Paul E. McKenney wrote:
quoted
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
That really hurts. Assuming that the "assert(!(z=2))" is actually there
to constrain the coherence order of z to be {0->1->2}, then I think that
this test is forbidden on arm using dmb instead of lwsync. That said, I
also don't think the Rz=1 in P0 changes anything.
What about the smp_wmb() variant of dmb that orders only stores?
Tricky, but I think it still works out if the coherence order of z is as
I described above. The line of reasoning is weird though -- I ended up
considering the two cases where P0 reads z before and after it reads x
and what that means for the read of y.
By "works out" you mean that ARM prohibits the outcome?
Yes, that's my understanding.
Very good, we have agreement between the two architectures, then. ;-)
Thanx, Paul
From: Paul E. McKenney <hidden> Date: 2016-01-28 00:40:58
On Wed, Jan 27, 2016 at 02:57:07PM +0000, David Howells wrote:
Peter Zijlstra [off-list ref] wrote:
quoted
+==========
+DISCLAIMER
+==========
+
+This document is not a specification; it is intentionally (for the sake of
+brevity) and unintentionally (due to being human) incomplete. This document is
+meant as a guide to using the various memory barriers provided by Linux, but
+in case of any doubt (and there are many) please ask.
+
+I repeat, this document is not a specification of what Linux expects from
+hardware.
The purpose of this document is twofold:
(1) to specify the minimum functionality that one can rely on for any
particular barrier, and
(2) to provide a guide as to how to use the barriers that are available.
Note that an architecture can provide more than the minimum requirement for
any particular barrier, but if the barrier provides less than that, it is
incorrect.
Note also that it is possible that a barrier may be a no-op for an
architecture because the way that arch works renders an explicit barrier
unnecessary in that case.
quoted
+
Can you bung an extra blank line in here if you have to redo this at all?
From: Paul E. McKenney <hidden> Date: 2016-01-28 00:46:00
On Wed, Jan 27, 2016 at 10:04:47AM +0800, Boqun Feng wrote:
quoted hunk
On Tue, Jan 26, 2016 at 03:29:21PM -0800, Paul E. McKenney wrote:
quoted
On Tue, Jan 26, 2016 at 02:33:40PM -0800, Linus Torvalds wrote:
quoted
On Tue, Jan 26, 2016 at 2:15 PM, Linus Torvalds
[off-list ref] wrote:
quoted
You might as well just write it as
struct foo x = READ_ONCE(*ptr);
x->bar = 5;
because that "smp_read_barrier_depends()" does NOTHING wrt the second write.
Just to clarify: on alpha it adds a memory barrier, but that memory
barrier is useless.
No trailing data-dependent read, so agreed, no smp_read_barrier_depends()
needed. That said, I believe that we should encourage rcu_dereference*()
or lockless_dereference() instead of READ_ONCE() for documentation
reasons, though.
quoted
On non-alpha, it is a no-op, and obviously does nothing simply because
it generates no code.
So if anybody believes that the "smp_read_barrier_depends()" does
something, they are *wrong*.
The other problem with smp_read_barrier_depends() is that it is often
a pain figuring out which prior load it is supposed to apply to.
Hence my preference for rcu_dereference*() and lockless_dereference().
Because semantically speaking, rcu_derefence*() and
lockless_dereference() are CONSUME(i.e. data/address dependent
read->read and read->write pairs are ordered), whereas
smp_read_barrier_depends() only guarantees read->read pairs with data
dependency are ordered, right?
If so, maybe we need to call it out in memory-barriers.txt, for example:
@@ -1703,8 +1703,8 @@ There are some more advanced barrier functions: (*) lockless_dereference();- This can be thought of as a pointer-fetch wrapper around the- smp_read_barrier_depends() data-dependency barrier.+ This is a load, and any load or store that has a data dependency on the+ value returned by this load won't be reordered before this load.
This is a good start, but more is needed to warn people off of
smp_read_barrier_depends(). But yes, better explanation would be good.
Thanx, Paul
This is also similar to rcu_dereference(), but in cases where
object lifetime is handled by some mechanism other than RCU, for
Regards,
Boqun
quoted
quoted
And if anybody sends out an email with that smp_read_barrier_depends()
in an example, they are actively just confusing other people, which is
even worse than just being wrong. Which is why I jumped in.
So stop perpetuating the myth that smp_read_barrier_depends() does
something here. It does not. It's a bug, and it has become this "mind
virus" for some people that seem to believe that it does something.
It looks like I should add words to memory-barriers.txt de-emphasizing
smp_read_barrier_depends(). I will take a look at that.
quoted
I had to remove this crap once from the kernel already, see commit
105ff3cbf225 ("atomic: remove all traces of READ_ONCE_CTRL() and
atomic*_read_ctrl()").
I don't want to ever see that broken construct again. And I want to
make sure that everybody is educated about how broken it was. I'm
extremely unhappy that it came up again.
Well, if it makes you feel better, that was control dependencies and this
was data dependencies. So it was not -exactly- the same. ;-)
(Sorry, couldn't resist...)
quoted
If it turns out that some architecture does actually need a barrier
between a read and a dependent write, then that will mean that
(a) we'll have to make up a _new_ barrier, because
"smp_read_barrier_depends()" is not that barrier. We'll presumably
then have to make that new barrier part of "rcu_derefence()" and
friends.
Agreed. We can worry about whether or not we replace the current
smp_read_barrier_depends() with that new barrier when and if such
hardware appears.
quoted
(b) we will have found an architecture with even worse memory
ordering semantics than alpha, and we'll have to stop castigating
alpha for being the worst memory ordering ever.
;-) ;-) ;-)
quoted
but I sincerely hope that we'll never find that kind of broken architecture.
Apparently at least some hardware vendors are reading memory-barriers.txt,
so perhaps the odds of that kind of breakage have reduced.
Thanx, Paul
From: Leonid Yegoshin <hidden> Date: 2016-01-28 00:48:49
On 01/27/2016 03:26 AM, Maciej W. Rozycki wrote:
On Fri, 15 Jan 2016, Leonid Yegoshin wrote:
quoted
quoted
So you need to build a different kernel for some types of MIPS systems?
Or do you do boot-time rewriting, like a number of other arches do?
I don't know. I would like to have responses. Ralf asked Maciej about old
systems and that came nowhere. Even rewrite - don't know what to do with that:
no lightweight SYNC or no SYNC at all - yes, it is still possible that SYNC on
some systems can be too heavy or even harmful, nobody tested that.
do you have an R4000 / R4600 / R5000 / R7000 / SiByte system at hand to
test this?
I should be able to check R4400 (that is virtually the same as R4000)
next week or so. As to SiByte -- not before next month I'm afraid. I
don't have access to any of the other processors you named. You may
want to find a better person if you want to accept this change soon.
Maciej
... and that stops forever...
- Leonid.