From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 10:13:02
Hi!
With optimizing compilers becoming more and more agressive and C so far
refusing to acknowledge the concept of control-dependencies even while
we keep growing the amount of reliance on them, things will eventually
come apart.
There have been talks with toolchain people on how to resolve this; one
suggestion was allowing the volatile qualifier on branch statements like
'if', but so far no actual compiler has made any progress on this.
Rather than waiting any longer, provide our own construct based on that
suggestion. The idea is by Alan Stern and refined by Paul and myself.
Code generation is sub-optimal (for the weak architectures) since we're
forced to convert the condition into another and use a fixed conditional
branch instruction, but shouldn't be too bad.
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
This construct should place control dependencies on a stronger footing
until such time that the compiler folks get around to accepting them :-)
I've converted most architectures we care about, and the rest will get
an extra smp_mb() by means of the 'generic' fallback implementation (for
now).
I've converted the control dependencies I remembered and those found
with a search for smp_acquire__after_ctrl_dep(), there might be more.
Compile tested only (alpha, arm, arm64, x86_64, powerpc, powerpc64, s390
and sparc64).
Suggested-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
arch/arm/include/asm/barrier.h | 11 +++++++++++
arch/arm64/include/asm/barrier.h | 11 +++++++++++
arch/powerpc/include/asm/barrier.h | 13 +++++++++++++
arch/s390/include/asm/barrier.h | 3 +++
arch/sparc/include/asm/barrier_64.h | 3 +++
arch/x86/include/asm/barrier.h | 16 ++++++++++++++++
include/asm-generic/barrier.h | 38 ++++++++++++++++++++++++++++++++++++-
include/linux/refcount.h | 2 +-
ipc/mqueue.c | 2 +-
ipc/msg.c | 2 +-
kernel/events/ring_buffer.c | 8 ++++----
kernel/locking/rwsem.c | 4 ++--
kernel/sched/core.c | 2 +-
kernel/smp.c | 2 +-
14 files changed, 105 insertions(+), 12 deletions(-)
@@ -713,7 +713,7 @@ static int wq_sleep(struct mqueue_inode_info *info, int sr,time=schedule_hrtimeout_range_clock(timeout,0,HRTIMER_MODE_ABS,CLOCK_REALTIME);-if(READ_ONCE(ewp->state)==STATE_READY){+volatile_if(READ_ONCE(ewp->state)==STATE_READY){/* see MQ_BARRIER for purpose/pairing */smp_acquire__after_ctrl_dep();retval=0;
@@ -941,8 +941,8 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, long count, int state)*exittheslowpathandreturnimmediatelyasits*RWSEM_READER_BIAShasalreadybeensetinthecount.*/-if(!(atomic_long_read(&sem->count)&-(RWSEM_WRITER_MASK|RWSEM_FLAG_HANDOFF))){+volatile_if(!(atomic_long_read(&sem->count)&+(RWSEM_WRITER_MASK|RWSEM_FLAG_HANDOFF))){/* Provide lock ACQUIRE */smp_acquire__after_ctrl_dep();raw_spin_unlock_irq(&sem->wait_lock);
From: Will Deacon <will@kernel.org> Date: 2021-06-04 10:44:08
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
With optimizing compilers becoming more and more agressive and C so far
refusing to acknowledge the concept of control-dependencies even while
we keep growing the amount of reliance on them, things will eventually
come apart.
There have been talks with toolchain people on how to resolve this; one
suggestion was allowing the volatile qualifier on branch statements like
'if', but so far no actual compiler has made any progress on this.
Rather than waiting any longer, provide our own construct based on that
suggestion. The idea is by Alan Stern and refined by Paul and myself.
Code generation is sub-optimal (for the weak architectures) since we're
forced to convert the condition into another and use a fixed conditional
branch instruction, but shouldn't be too bad.
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
quoted hunk
This construct should place control dependencies on a stronger footing
until such time that the compiler folks get around to accepting them :-)
I've converted most architectures we care about, and the rest will get
an extra smp_mb() by means of the 'generic' fallback implementation (for
now).
I've converted the control dependencies I remembered and those found
with a search for smp_acquire__after_ctrl_dep(), there might be more.
Compile tested only (alpha, arm, arm64, x86_64, powerpc, powerpc64, s390
and sparc64).
Suggested-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
arch/arm/include/asm/barrier.h | 11 +++++++++++
arch/arm64/include/asm/barrier.h | 11 +++++++++++
arch/powerpc/include/asm/barrier.h | 13 +++++++++++++
arch/s390/include/asm/barrier.h | 3 +++
arch/sparc/include/asm/barrier_64.h | 3 +++
arch/x86/include/asm/barrier.h | 16 ++++++++++++++++
include/asm-generic/barrier.h | 38 ++++++++++++++++++++++++++++++++++++-
include/linux/refcount.h | 2 +-
ipc/mqueue.c | 2 +-
ipc/msg.c | 2 +-
kernel/events/ring_buffer.c | 8 ++++----
kernel/locking/rwsem.c | 4 ++--
kernel/sched/core.c | 2 +-
kernel/smp.c | 2 +-
14 files changed, 105 insertions(+), 12 deletions(-)
@@ -156,6 +156,17 @@ do { \(typeof(*p))__u.__val;\})+/* Guarantee a conditional branch that depends on @cond. */+static__always_inline_Boolvolatile_cond(_Boolcond)
The thing I really dislike about this is that, if the compiler _does_
emit a conditional branch for the C 'if', then we get a pair of branch
instructions in close proximity to each other which the predictor is likely
to hate. I wouldn't be surprised if an RCpc acquire heading the dependency
actually performs better on modern arm64 cores in the general case.
So I think that's an argument for doing this in the compiler...
Will
From: Will Deacon <will@kernel.org> Date: 2021-06-04 11:13:46
On Fri, Jun 04, 2021 at 11:43:59AM +0100, Will Deacon wrote:
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
quoted
With optimizing compilers becoming more and more agressive and C so far
refusing to acknowledge the concept of control-dependencies even while
we keep growing the amount of reliance on them, things will eventually
come apart.
There have been talks with toolchain people on how to resolve this; one
suggestion was allowing the volatile qualifier on branch statements like
'if', but so far no actual compiler has made any progress on this.
Rather than waiting any longer, provide our own construct based on that
suggestion. The idea is by Alan Stern and refined by Paul and myself.
Code generation is sub-optimal (for the weak architectures) since we're
forced to convert the condition into another and use a fixed conditional
branch instruction, but shouldn't be too bad.
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
Thinking more on this, an alternative angle would be having READ_ONCE_CTRL()
instead of volatile_if. That would then expand (on arm64) to either
something like:
LDR X0, [X1]
CBNZ X0, 1f // Dummy ctrl
1:
or, with LTO:
LDAPR X0, [X1] // RCpc
and we'd avoid the redundancy.
Will
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 11:32:16
On Fri, Jun 04, 2021 at 11:44:00AM +0100, Will Deacon wrote:
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
quoted
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
#ifdef CONFIG_LTO
/* Because __READ_ONCE() is load-acquire */
#define volatile_cond(cond) (cond)
#else
....
#endif
Doesn't work? Bit naf, but I'm thinking it ought to do.
quoted
This construct should place control dependencies on a stronger footing
until such time that the compiler folks get around to accepting them :-)
I've converted most architectures we care about, and the rest will get
an extra smp_mb() by means of the 'generic' fallback implementation (for
now).
I've converted the control dependencies I remembered and those found
with a search for smp_acquire__after_ctrl_dep(), there might be more.
Compile tested only (alpha, arm, arm64, x86_64, powerpc, powerpc64, s390
and sparc64).
Suggested-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
@@ -156,6 +156,17 @@ do { \(typeof(*p))__u.__val;\})+/* Guarantee a conditional branch that depends on @cond. */+static__always_inline_Boolvolatile_cond(_Boolcond)
Is _Bool to fix some awful header mess?
Yes, header soup :/ Idem for the lack of true and false.
The thing I really dislike about this is that, if the compiler _does_
emit a conditional branch for the C 'if', then we get a pair of branch
instructions in close proximity to each other which the predictor is likely
to hate. I wouldn't be surprised if an RCpc acquire heading the dependency
actually performs better on modern arm64 cores in the general case.
jump_label / static_branch relies on asm goto inside if to get optimized
away, so I'm fairly confident this will not result in a double branch,
because yes, that would blow.
So I think that's an argument for doing this in the compiler...
Don't get me wrong, I would _LOVE_ for the compilers to do this. This
really is just a stop-gap solution to ensure we don't get to debug 'FUN'
stuff.
From: Will Deacon <will@kernel.org> Date: 2021-06-04 13:44:30
On Fri, Jun 04, 2021 at 01:31:48PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 11:44:00AM +0100, Will Deacon wrote:
quoted
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
quoted
quoted
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
#ifdef CONFIG_LTO
/* Because __READ_ONCE() is load-acquire */
#define volatile_cond(cond) (cond)
#else
....
#endif
Doesn't work? Bit naf, but I'm thinking it ought to do.
The problem is with relaxed atomic RMWs; we don't upgrade those to acquire
atm as they're written in asm, but we'd need volatile_cond() to work with
them. It's a shame, because we only have RCsc RMWs on arm64, so it would
be a bit more expensive.
quoted
quoted
+/**
+ * volatile_if() - Provide a control-dependency
+ *
+ * volatile_if(READ_ONCE(A))
+ * WRITE_ONCE(B, 1);
+ *
+ * will ensure that the STORE to B happens after the LOAD of A. Normally a
+ * control dependency relies on a conditional branch having a data dependency
+ * on the LOAD and an architecture's inability to speculate STOREs. IOW, this
+ * provides a LOAD->STORE order.
+ *
+ * Due to optimizing compilers extra care is needed; as per the example above
+ * the LOAD must be 'volatile' qualified in order to ensure the compiler
+ * actually emits the load, such that the data-dependency to the conditional
+ * branch can be formed.
+ *
+ * Secondly, the compiler must be prohibited from lifting anything out of the
+ * selection statement, as this would obviously also break the ordering.
+ *
+ * Thirdly, and this is the tricky bit, architectures that allow the
+ * LOAD->STORE reorder must ensure the compiler actually emits the conditional
+ * branch instruction, this isn't possible in generic.
+ *
+ * See the volatile_cond() wrapper.
+ */
+#define volatile_if(cond) if (volatile_cond(cond))
The thing I really dislike about this is that, if the compiler _does_
emit a conditional branch for the C 'if', then we get a pair of branch
instructions in close proximity to each other which the predictor is likely
to hate. I wouldn't be surprised if an RCpc acquire heading the dependency
actually performs better on modern arm64 cores in the general case.
jump_label / static_branch relies on asm goto inside if to get optimized
away, so I'm fairly confident this will not result in a double branch,
because yes, that would blow.
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 13:56:35
On Fri, Jun 04, 2021 at 02:44:22PM +0100, Will Deacon wrote:
On Fri, Jun 04, 2021 at 01:31:48PM +0200, Peter Zijlstra wrote:
quoted
On Fri, Jun 04, 2021 at 11:44:00AM +0100, Will Deacon wrote:
quoted
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
quoted
quoted
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
#ifdef CONFIG_LTO
/* Because __READ_ONCE() is load-acquire */
#define volatile_cond(cond) (cond)
#else
....
#endif
Doesn't work? Bit naf, but I'm thinking it ought to do.
The problem is with relaxed atomic RMWs; we don't upgrade those to acquire
atm as they're written in asm, but we'd need volatile_cond() to work with
them. It's a shame, because we only have RCsc RMWs on arm64, so it would
be a bit more expensive.
Urgh, I see. Compiler can't really help in that case either I'm afraid.
They'll never want to modify loads that originate in an asm(). They'll
say to use the C11 _Atomic crud.
From: Will Deacon <will@kernel.org> Date: 2021-06-04 15:14:04
On Fri, Jun 04, 2021 at 03:56:16PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 02:44:22PM +0100, Will Deacon wrote:
quoted
On Fri, Jun 04, 2021 at 01:31:48PM +0200, Peter Zijlstra wrote:
quoted
On Fri, Jun 04, 2021 at 11:44:00AM +0100, Will Deacon wrote:
quoted
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
quoted
quoted
Usage of volatile_if requires the @cond to be headed by a volatile load
(READ_ONCE() / atomic_read() etc..) such that the compiler is forced to
emit the load and the branch emitted will have the required
data-dependency. Furthermore, volatile_if() is a compiler barrier, which
should prohibit the compiler from lifting anything out of the selection
statement.
When building with LTO on arm64, we already upgrade READ_ONCE() to an RCpc
acquire. In this case, it would be really good to avoid having the dummy
conditional branch somehow, but I can't see a good way to achieve that.
#ifdef CONFIG_LTO
/* Because __READ_ONCE() is load-acquire */
#define volatile_cond(cond) (cond)
#else
....
#endif
Doesn't work? Bit naf, but I'm thinking it ought to do.
The problem is with relaxed atomic RMWs; we don't upgrade those to acquire
atm as they're written in asm, but we'd need volatile_cond() to work with
them. It's a shame, because we only have RCsc RMWs on arm64, so it would
be a bit more expensive.
Urgh, I see. Compiler can't really help in that case either I'm afraid.
They'll never want to modify loads that originate in an asm(). They'll
say to use the C11 _Atomic crud.
Indeed. That's partly what led me down the route of thinking about "control
ordering" to sit between relaxed and acquire. So you have READ_ONCE_CTRL()
instead of this, but then we can't play your asm goto trick.
If we could push the memory access _and_ the branch down into the new
volatile_if helper, a bit like we do for smp_cond_load_*(), that would
help but it makes the thing a lot harder to use.
In fact, maybe it's actually necessary to bundle the load and branch
together. I looked at some of the examples of compilers breaking control
dependencies from memory-barriers.txt and the "boolean short-circuit"
example seems to defeat volatile_if:
void foo(int *x, int *y)
{
volatile_if (READ_ONCE(*x) || 1 > 0)
WRITE_ONCE(*y, 42);
}
Although we get a conditional branch emitted, it's headed by an immediate
move instruction and the result of the load is discarded:
38: d503233f paciasp
3c: b940001f ldr wzr, [x0]
40: 52800028 mov w8, #0x1 // #1
44: b5000068 cbnz x8, 50 <foo+0x18>
48: d50323bf autiasp
4c: d65f03c0 ret
50: d503249f bti j
54: 52800548 mov w8, #0x2a // #42
58: b9000028 str w8, [x1]
5c: d50323bf autiasp
60: d65f03c0 ret
Will
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 15:22:16
On Fri, Jun 04, 2021 at 04:13:57PM +0100, Will Deacon wrote:
In fact, maybe it's actually necessary to bundle the load and branch
together. I looked at some of the examples of compilers breaking control
dependencies from memory-barriers.txt and the "boolean short-circuit"
example seems to defeat volatile_if:
void foo(int *x, int *y)
{
volatile_if (READ_ONCE(*x) || 1 > 0)
WRITE_ONCE(*y, 42);
}
Yeah, I'm not too bothered about this. Broken is broken.
If this were a compiler feature, the above would be a compile error. But
alas, we're not there yet :/ and the best we get to say at this point
is: don't do that then.
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-04 15:36:13
On Fri, Jun 04, 2021 at 05:22:04PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 04:13:57PM +0100, Will Deacon wrote:
quoted
In fact, maybe it's actually necessary to bundle the load and branch
together. I looked at some of the examples of compilers breaking control
dependencies from memory-barriers.txt and the "boolean short-circuit"
example seems to defeat volatile_if:
void foo(int *x, int *y)
{
volatile_if (READ_ONCE(*x) || 1 > 0)
WRITE_ONCE(*y, 42);
}
Yeah, I'm not too bothered about this. Broken is broken.
If this were a compiler feature, the above would be a compile error. But
alas, we're not there yet :/ and the best we get to say at this point
is: don't do that then.
This is an example of a "syntactic" dependency versus a "semantic"
dependency. We shouldn't expect syntactic control dependencies to be
preserved.
As a rule, people don't write non-semantic dependencies on purpose. But
they can occur in some situations, thanks to definitions the programmer
isn't aware of. One example would be:
(In some obscure header file): #define NUM_FOO 1
(Then in real code): if (READ_ONCE(*x) % NUM_FOO) ...
Alan
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 15:42:41
On Fri, Jun 04, 2021 at 05:22:04PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 04:13:57PM +0100, Will Deacon wrote:
quoted
In fact, maybe it's actually necessary to bundle the load and branch
together. I looked at some of the examples of compilers breaking control
dependencies from memory-barriers.txt and the "boolean short-circuit"
example seems to defeat volatile_if:
void foo(int *x, int *y)
{
volatile_if (READ_ONCE(*x) || 1 > 0)
WRITE_ONCE(*y, 42);
}
Yeah, I'm not too bothered about this. Broken is broken.
If this were a compiler feature, the above would be a compile error. But
alas, we're not there yet :/ and the best we get to say at this point
is: don't do that then.
Ha! Fixed it for you:
#define volatile_if(cond) if (({ bool __t = (cond); BUILD_BUG_ON(__builtin_constant_p(__t)); volatile_cond(__t); }))
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-04 15:51:57
On Fri, Jun 04, 2021 at 05:42:28PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 05:22:04PM +0200, Peter Zijlstra wrote:
quoted
On Fri, Jun 04, 2021 at 04:13:57PM +0100, Will Deacon wrote:
quoted
In fact, maybe it's actually necessary to bundle the load and branch
together. I looked at some of the examples of compilers breaking control
dependencies from memory-barriers.txt and the "boolean short-circuit"
example seems to defeat volatile_if:
void foo(int *x, int *y)
{
volatile_if (READ_ONCE(*x) || 1 > 0)
WRITE_ONCE(*y, 42);
}
Yeah, I'm not too bothered about this. Broken is broken.
If this were a compiler feature, the above would be a compile error. But
alas, we're not there yet :/ and the best we get to say at this point
is: don't do that then.
Ha! Fixed it for you:
#define volatile_if(cond) if (({ bool __t = (cond); BUILD_BUG_ON(__builtin_constant_p(__t)); volatile_cond(__t); }))
That won't help with more complicated examples, such as:
volatile_if (READ_ONCE(*x) * 0 + READ_ONCE(*y))
Alan
That won't help with more complicated examples, such as:
volatile_if (READ_ONCE(*x) * 0 + READ_ONCE(*y))
That's effectively:
volatile_if (READ_ONCE(*y))
WRITE_ONCE(*y, 42);
which is a valid, but daft, LOAD->STORE order, no? A compiler might
maybe be able to WARN on that, but that's definitely beyond what we can
do with macros.
Sorry, what I meant to write was:
volatile_if (READ_ONCE(*x) * 0 + READ_ONCE(*y))
WRITE_ONCE(*z, 42);
where there is no ordering between *x and *z. It's not daft, and yes, a
macro won't be able to warn about it.
Alan
which is a valid, but daft, LOAD->STORE order, no? A compiler might
maybe be able to WARN on that, but that's definitely beyond what we can
do with macros.
On Fri, Jun 4, 2021 at 11:27 AM Alan Stern [off-list ref] wrote:
volatile_if (READ_ONCE(*x) * 0 + READ_ONCE(*y))
WRITE_ONCE(*z, 42);
where there is no ordering between *x and *z.
I wouldn't worry about it.
I think a compiler is allowed to optimize away stupid code.
I get upset when a compiler says "oh, that's undefined, so I will
ignore the obvious meaning of it", but that's a different thing
entirely.
I really wish that the C standards group showed some spine, and said
"there is no undefined, there is only implementation-defined". That
would solve a *lot* of problems.
But I also realize that will never happen. Because "spine" and "good
taste" is not something that I've ever heard of happening in an
industry standards committee.
Side note: it is worth noting that my version of "volatile_if()" has
an added little quirk: it _ONLY_ orders the stuff inside the
if-statement.
I do think it's worth not adding new special cases (especially that
"asm goto" hack that will generate worse code than the compiler could
do), but it means that
x = READ_ONCE(ptr);
volatile_if (x > 0)
WRITE_ONCE(*z, 42);
has an ordering, but if you write it as
x = READ_ONCE(ptr);
volatile_if (x <= 0)
return;
WRITE_ONCE(*z, 42);
then I could in theory see teh compiler doing that WRITE_ONCE() as
some kind of non-control dependency.
That said, I don't actually see how the compiler could do anything
that actually broke the _semantics_ of the code. Yes, it could do the
write using a magical data dependency on the conditional and turning
it into a store on a conditional address instead (before doing the
branch), but honestly, I don't see how that would actually break
anything.
So this is more of a "in theory, the two sides are not symmetric". The
"asm volatile" in a barrier() will force the compiler to generate the
branch, and the memory clobber in barrier() will most certainly force
any stores inside the "volatile_if()" to be after the branch.
But because the memory clobber is only inside the if-statement true
case, the false case could have the compiler migrate any code in that
false thing to before the if.
Again, semantics do matter, and I don't see how the compiler could
actually break the fundamental issue of "load->conditional->store is a
fundamental ordering even without memory barriers because of basic
causality", because you can't just arbitrarily generate speculative
stores that would be visible to others.
But at the same time, that's *such* a fundamental rule that I really
am intrigued why people think "volatile_if()" is needed in reality (as
opposed to some "in theory, the compiler can know things that are
unknowable thanks to a magical oracle" BS argument)
Linus
On Fri, Jun 4, 2021 at 12:09 PM Linus Torvalds
[off-list ref] wrote:
Again, semantics do matter, and I don't see how the compiler could
actually break the fundamental issue of "load->conditional->store is a
fundamental ordering even without memory barriers because of basic
causality", because you can't just arbitrarily generate speculative
stores that would be visible to others.
This, after all, is why we trust that the *hardware* can't do it.
Even if the hardware mis-speculates and goes down the wrong branch,
and speculatively does the store when it shouldn't have, we don't
care: we know that such a speculative store can not possibly become
semantically visible (*) to other threads.
For all the same reasons, I don't see how a compiler can violate
causal ordering of the code (assuming, again, that the test is
_meaningful_ - if we write nonsensical code, that's a different
issue).
If we have compilers that create speculative stores that are visible
to other threads, we need to fix them.
Linus
(*) By "semantically visible" I intend to avoid the whole timing/cache
pattern kind of non-semantic visibility that is all about the spectre
leakage kind of things.
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 20:56:02
On Fri, Jun 04, 2021 at 12:18:43PM -0700, Linus Torvalds wrote:
On Fri, Jun 4, 2021 at 12:09 PM Linus Torvalds
[off-list ref] wrote:
quoted
Again, semantics do matter, and I don't see how the compiler could
actually break the fundamental issue of "load->conditional->store is a
fundamental ordering even without memory barriers because of basic
causality", because you can't just arbitrarily generate speculative
stores that would be visible to others.
This, after all, is why we trust that the *hardware* can't do it.
Even if the hardware mis-speculates and goes down the wrong branch,
and speculatively does the store when it shouldn't have, we don't
care: we know that such a speculative store can not possibly become
semantically visible (*) to other threads.
For all the same reasons, I don't see how a compiler can violate
causal ordering of the code (assuming, again, that the test is
_meaningful_ - if we write nonsensical code, that's a different
issue).
I am probably missing your point, but something like this:
if (READ_ONCE(x))
y = 42;
else
y = 1729;
Can in theory be transformed into something like this:
y = 1729;
if (READ_ONCE(x))
y = 42;
The usual way to prevent it is to use WRITE_ONCE().
Fortunately, register sets are large, and gcc manages to do a single
store and use only %eax.
Thanx, Paul
If we have compilers that create speculative stores that are visible
to other threads, we need to fix them.
Linus
(*) By "semantically visible" I intend to avoid the whole timing/cache
pattern kind of non-semantic visibility that is all about the spectre
leakage kind of things.
On Fri, Jun 4, 2021 at 1:56 PM Paul E. McKenney [off-list ref] wrote:
The usual way to prevent it is to use WRITE_ONCE().
The very *documentation example* for "volatile_if()" uses that WRITE_ONCE().
IOW, the patch that started this discussion has this comment in it:
+/**
+ * volatile_if() - Provide a control-dependency
+ *
+ * volatile_if(READ_ONCE(A))
+ * WRITE_ONCE(B, 1);
+ *
+ * will ensure that the STORE to B happens after the LOAD of A.
and my point is that I don't see *ANY THEORETICALLY POSSIBLE* way that
that "volatile_if()" could not be just a perfectly regular "if ()".
Can you?
Because we *literally* depend on the fundamental concept of causality
to make the hardware not re-order those operations.
That is the WHOLE AND ONLY point of this whole construct: we're
avoiding a possibly expensive hardware barrier operation, because we
know we have a more fundamental barrier that is INHERENT TO THE
OPERATION.
And I cannot for the life of me see how a compiler can break that
fundamental concept of causality either.
Seriously. Tell me how a compiler could _possibly_ turn that into
something that breaks the fundamental causal relationship. The same
fundamental causal relationship that is the whole and only reason we
don't need a memory barrier for the hardware.
And no, there is not a way in hell that the above can be written with
some kind of semantically visible speculative store without the
compiler being a total pile of garbage that wouldn't be usable for
compiling a kernel with.
If your argument is that the compiler can magically insert speculative
stores that can then be overwritten later, then MY argument is that
such a compiler could do that for *ANYTHING*. "volatile_if()" wouldn't
save us.
If that's valid compiler behavior in your opinion, then we have
exactly two options:
(a) give up
(b) not use that broken garbage of a compiler.
So I can certainly accept the patch with the simpler implementation of
"volatile_if()", but dammit, I want to see an actual real example
arguing for why it would be relevant and why the compiler would need
our help.
Because the EXACT VERY EXAMPLE that was in the patch as-is sure as
hell is no such thing.
If the intent is to *document* that "this conditional is part of a
load-conditional-store memory ordering pattern, then that is one
thing. But if that's the intent, then we might as well just write it
as
#define volatile_if(x) if (x)
and add a *comment* about why this kind of sequence doesn't need a
memory barrier.
I'd much rather have that kind of documentation, than have barriers
that are magical for theoretical compiler issues that aren't real, and
don't have any grounding in reality.
Without a real and valid example of how this could matter, this is
just voodoo programming.
We don't actually need to walk three times widdershins around the
computer before compiling the kernel.That's not how kernel development
works.
And we don't need to add a "volatile_if()" with magical barriers that
have no possibility of having real semantic meaning.
So I want to know what the semantic meaning of volatile_if() would be,
and why it fixes anything that a plain "if()" wouldn't. I want to see
the sequence where that "volatile_if()" actually *fixes* something.
Linus
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 21:40:22
On Fri, Jun 04, 2021 at 02:27:49PM -0700, Linus Torvalds wrote:
On Fri, Jun 4, 2021 at 1:56 PM Paul E. McKenney [off-list ref] wrote:
quoted
The usual way to prevent it is to use WRITE_ONCE().
The very *documentation example* for "volatile_if()" uses that WRITE_ONCE().
Whew! ;-)
IOW, the patch that started this discussion has this comment in it:
+/**
+ * volatile_if() - Provide a control-dependency
+ *
+ * volatile_if(READ_ONCE(A))
+ * WRITE_ONCE(B, 1);
+ *
+ * will ensure that the STORE to B happens after the LOAD of A.
and my point is that I don't see *ANY THEORETICALLY POSSIBLE* way that
that "volatile_if()" could not be just a perfectly regular "if ()".
Can you?
I cannot, maybe due to failure of imagination. But please see below.
Because we *literally* depend on the fundamental concept of causality
to make the hardware not re-order those operations.
That is the WHOLE AND ONLY point of this whole construct: we're
avoiding a possibly expensive hardware barrier operation, because we
know we have a more fundamental barrier that is INHERENT TO THE
OPERATION.
And I cannot for the life of me see how a compiler can break that
fundamental concept of causality either.
Seriously. Tell me how a compiler could _possibly_ turn that into
something that breaks the fundamental causal relationship. The same
fundamental causal relationship that is the whole and only reason we
don't need a memory barrier for the hardware.
And no, there is not a way in hell that the above can be written with
some kind of semantically visible speculative store without the
compiler being a total pile of garbage that wouldn't be usable for
compiling a kernel with.
If your argument is that the compiler can magically insert speculative
stores that can then be overwritten later, then MY argument is that
such a compiler could do that for *ANYTHING*. "volatile_if()" wouldn't
save us.
If that's valid compiler behavior in your opinion, then we have
exactly two options:
(a) give up
(b) not use that broken garbage of a compiler.
So I can certainly accept the patch with the simpler implementation of
"volatile_if()", but dammit, I want to see an actual real example
arguing for why it would be relevant and why the compiler would need
our help.
Because the EXACT VERY EXAMPLE that was in the patch as-is sure as
hell is no such thing.
If the intent is to *document* that "this conditional is part of a
load-conditional-store memory ordering pattern, then that is one
thing. But if that's the intent, then we might as well just write it
as
#define volatile_if(x) if (x)
and add a *comment* about why this kind of sequence doesn't need a
memory barrier.
I'd much rather have that kind of documentation, than have barriers
that are magical for theoretical compiler issues that aren't real, and
don't have any grounding in reality.
Without a real and valid example of how this could matter, this is
just voodoo programming.
We don't actually need to walk three times widdershins around the
computer before compiling the kernel.That's not how kernel development
works.
And we don't need to add a "volatile_if()" with magical barriers that
have no possibility of having real semantic meaning.
So I want to know what the semantic meaning of volatile_if() would be,
and why it fixes anything that a plain "if()" wouldn't. I want to see
the sequence where that "volatile_if()" actually *fixes* something.
Here is one use case:
volatile_if(READ_ONCE(A)) {
WRITE_ONCE(B, 1);
do_something();
} else {
WRITE_ONCE(B, 1);
do_something_else();
}
With plain "if", the compiler is within its rights to do this:
tmp = READ_ONCE(A);
WRITE_ONCE(B, 1);
if (tmp)
do_something();
else
do_something_else();
On x86, still no problem. But weaker hardware could now reorder the
store to B before the load from A. With volatile_if(), this reordering
would be prevented.
Thanx, Paul
On Fri, Jun 4, 2021 at 2:40 PM Paul E. McKenney [off-list ref] wrote:
Here is one use case:
volatile_if(READ_ONCE(A)) {
WRITE_ONCE(B, 1);
do_something();
} else {
WRITE_ONCE(B, 1);
do_something_else();
}
With plain "if", the compiler is within its rights to do this:
tmp = READ_ONCE(A);
WRITE_ONCE(B, 1);
if (tmp)
do_something();
else
do_something_else();
On x86, still no problem. But weaker hardware could now reorder the
store to B before the load from A. With volatile_if(), this reordering
would be prevented.
But *should* it be prevented? For code like the above?
I'm not really seeing that the above is a valid code sequence.
Sure, that "WRITE_ONCE(B, 1)" could be seen as a lock release, and
then it would be wrong to have the read of 'A' happen after the lock
has actually been released. But if that's the case, then it should
have used a smp_store_release() in the first place, not a
WRITE_ONCE().
So I don't see the above as much of a valid example of actual
READ/WRITE_ONCE() use.
If people use READ/WRITE_ONCE() like the above, and they actually
depend on that kind of ordering, I think that code is likely wrong to
begin with. Using "volatile_if()" doesn't make it more valid.
Now, part of this is that I do think that in *general* we should never
use this very suble load-cond-store pattern to begin with. We should
strive to use more smp_load_acquire() and smp_store_release() if we
care about ordering of accesses. They are typically cheap enough, and
if there's much of an ordering issue, they are the right things to do.
I think the whole "load-to-store ordering" subtle non-ordered case is
for very very special cases, when you literally don't have a general
memory ordering, you just have an ordering for *one* very particular
access. Like some of the very magical code in the rw-semaphore case,
or that smp_cond_load_acquire().
IOW, I would expect that we have a handful of uses of this thing. And
none of them have that "the conditional store is the same on both
sides" pattern, afaik.
And immediately when the conditional store is different, you end up
having a dependency on it that orders it.
But I guess I can accept the above made-up example as an "argument",
even though I feel it is entirely irrelevant to the actual issues and
uses we have.
Linus
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-05 14:57:42
On Fri, Jun 04, 2021 at 03:19:11PM -0700, Linus Torvalds wrote:
Now, part of this is that I do think that in *general* we should never
use this very suble load-cond-store pattern to begin with. We should
strive to use more smp_load_acquire() and smp_store_release() if we
care about ordering of accesses. They are typically cheap enough, and
if there's much of an ordering issue, they are the right things to do.
I think the whole "load-to-store ordering" subtle non-ordered case is
for very very special cases, when you literally don't have a general
memory ordering, you just have an ordering for *one* very particular
access. Like some of the very magical code in the rw-semaphore case,
or that smp_cond_load_acquire().
IOW, I would expect that we have a handful of uses of this thing. And
none of them have that "the conditional store is the same on both
sides" pattern, afaik.
And immediately when the conditional store is different, you end up
having a dependency on it that orders it.
But I guess I can accept the above made-up example as an "argument",
even though I feel it is entirely irrelevant to the actual issues and
uses we have.
Indeed, the expansion of the currently proposed version of
volatile_if (A) {
B;
} else {
C;
}
is basically the same as
if (A) {
barrier();
B;
} else {
barrier();
C;
}
which is just about as easy to write by hand. (For some reason my
fingers don't like typing "volatile_"; the letters tend to get
scrambled.)
So given that:
1. Reliance on control dependencies is uncommon in the kernel,
and
2. The loads in A could just be replaced with load_acquires
at a low penalty (or store-releases could go into B and C),
it seems that we may not need volatile_if at all! The only real reason
for having it in the first place was to avoid the penalty of
load-acquire on architectures where it has a significant cost, when the
control dependency would provide the necessary ordering for free. Such
architectures are getting less and less common.
Alan
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-06 00:14:21
On Sat, Jun 05, 2021 at 10:57:39AM -0400, Alan Stern wrote:
On Fri, Jun 04, 2021 at 03:19:11PM -0700, Linus Torvalds wrote:
quoted
Now, part of this is that I do think that in *general* we should never
use this very suble load-cond-store pattern to begin with. We should
strive to use more smp_load_acquire() and smp_store_release() if we
care about ordering of accesses. They are typically cheap enough, and
if there's much of an ordering issue, they are the right things to do.
I think the whole "load-to-store ordering" subtle non-ordered case is
for very very special cases, when you literally don't have a general
memory ordering, you just have an ordering for *one* very particular
access. Like some of the very magical code in the rw-semaphore case,
or that smp_cond_load_acquire().
IOW, I would expect that we have a handful of uses of this thing. And
none of them have that "the conditional store is the same on both
sides" pattern, afaik.
And immediately when the conditional store is different, you end up
having a dependency on it that orders it.
But I guess I can accept the above made-up example as an "argument",
even though I feel it is entirely irrelevant to the actual issues and
uses we have.
Indeed, the expansion of the currently proposed version of
volatile_if (A) {
B;
} else {
C;
}
is basically the same as
if (A) {
barrier();
B;
} else {
barrier();
C;
}
which is just about as easy to write by hand. (For some reason my
fingers don't like typing "volatile_"; the letters tend to get
scrambled.)
So given that:
1. Reliance on control dependencies is uncommon in the kernel,
and
2. The loads in A could just be replaced with load_acquires
at a low penalty (or store-releases could go into B and C),
it seems that we may not need volatile_if at all! The only real reason
for having it in the first place was to avoid the penalty of
load-acquire on architectures where it has a significant cost, when the
control dependency would provide the necessary ordering for free. Such
architectures are getting less and less common.
That does sound good, but...
Current compilers beg to differ at -O2: https://godbolt.org/z/5K55Gardn
------------------------------------------------------------------------
#define READ_ONCE(x) (*(volatile typeof(x) *)&(x))
#define WRITE_ONCE(x, val) (READ_ONCE(x) = (val))
#define barrier() __asm__ __volatile__("": : :"memory")
int x, y;
int main(int argc, char *argv[])
{
if (READ_ONCE(x)) {
barrier();
WRITE_ONCE(y, 1);
} else {
barrier();
WRITE_ONCE(y, 1);
}
return 0;
}
------------------------------------------------------------------------
Both gcc and clang generate a load followed by a store, with no branch.
ARM gets the same results from both compilers.
As Linus suggested, removing one (but not both!) invocations of barrier()
does cause a branch to be emitted, so maybe that is a way forward.
Assuming it is more than just dumb luck, anyway. :-/
Thanx, Paul
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-06 01:29:07
On Sat, Jun 05, 2021 at 05:14:18PM -0700, Paul E. McKenney wrote:
On Sat, Jun 05, 2021 at 10:57:39AM -0400, Alan Stern wrote:
quoted
Indeed, the expansion of the currently proposed version of
volatile_if (A) {
B;
} else {
C;
}
is basically the same as
if (A) {
barrier();
B;
} else {
barrier();
C;
}
That does sound good, but...
Current compilers beg to differ at -O2: https://godbolt.org/z/5K55Gardn
------------------------------------------------------------------------
#define READ_ONCE(x) (*(volatile typeof(x) *)&(x))
#define WRITE_ONCE(x, val) (READ_ONCE(x) = (val))
#define barrier() __asm__ __volatile__("": : :"memory")
int x, y;
int main(int argc, char *argv[])
{
if (READ_ONCE(x)) {
barrier();
WRITE_ONCE(y, 1);
} else {
barrier();
WRITE_ONCE(y, 1);
}
return 0;
}
------------------------------------------------------------------------
Both gcc and clang generate a load followed by a store, with no branch.
ARM gets the same results from both compilers.
As Linus suggested, removing one (but not both!) invocations of barrier()
does cause a branch to be emitted, so maybe that is a way forward.
Assuming it is more than just dumb luck, anyway. :-/
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
Alan
On Sat, Jun 5, 2021 at 6:29 PM Alan Stern [off-list ref] wrote:
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
That's actually a feature in some cases, ie the ability to do CSE on
asm statements (ie the "always has the same output" optimization that
the docs talk about).
So gcc has always looked at the asm string for that reason, afaik.
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
There is a statement of "Under certain circumstances, GCC may
duplicate (or remove duplicates of) your assembly code when
optimizing" and a suggestion of using "%=" to generate a unique
instance of an asm.
Which might actually be a good idea for "barrier()", just in case.
However, the problem with that is that I don't think we are guaranteed
to have a universal comment character for asm statements.
IOW, it might be a good idea to do something like
#define barrier() \
__asm__ __volatile__("# barrier %=": : :"memory")
but I'm not 100% convinced that '#' is always a comment in asm code,
so the above might not actually build everywhere.
However, *testing* the above (in my config, where '#' does work as a
comment character) shows that gcc doesn't actually consider them to be
distinct EVEN THEN, and will still merge two barrier statements.
That's distressing.
So the gcc docs are actively wrong, and %= does nothing - it will
still compare as the exact same inline asm, because the string
equality testing is apparently done before any expansion.
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
And again - the above works only as long as "#" is a valid comment
character in the assembler. And I have this very dim memory of us
having comments in inline asm, and it breaking certain configurations
(for when the assembler that the compiler uses is a special
human-unfriendly one that only accepts compiler output).
You could make even more disgusting hacks, and have it generate something like
.pushsection .discard.barrier
.long #id
.popsection
instead of a comment. We already expect that to work and have generic
inline asm cases that generate code like that.
Linus
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-06 04:43:40
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
On Sat, Jun 5, 2021 at 6:29 PM Alan Stern [off-list ref] wrote:
quoted
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
That's actually a feature in some cases, ie the ability to do CSE on
asm statements (ie the "always has the same output" optimization that
the docs talk about).
Agreed, albeit reluctantly. ;-)
So gcc has always looked at the asm string for that reason, afaik.
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
There is a statement of "Under certain circumstances, GCC may
duplicate (or remove duplicates of) your assembly code when
optimizing" and a suggestion of using "%=" to generate a unique
instance of an asm.
So gcc might some day note a do-nothing asm and duplicate it for
the sole purpose of collapsing the "then" and "else" clauses. I
guess I need to keep my paranoia for the time being, then. :-/
Which might actually be a good idea for "barrier()", just in case.
However, the problem with that is that I don't think we are guaranteed
to have a universal comment character for asm statements.
IOW, it might be a good idea to do something like
#define barrier() \
__asm__ __volatile__("# barrier %=": : :"memory")
but I'm not 100% convinced that '#' is always a comment in asm code,
so the above might not actually build everywhere.
However, *testing* the above (in my config, where '#' does work as a
comment character) shows that gcc doesn't actually consider them to be
distinct EVEN THEN, and will still merge two barrier statements.
That's distressing.
If I keep the old definition of barrier() and make a barrier1() as
you defined above:
#define barrier1() __asm__ __volatile__("# barrier %=": : :"memory")
Then putting barrier() in the "then" clause and barrier1() in the
"else" clause works, though clang 12 for whatever reason generates
an extra jump in that case. https://godbolt.org/z/YhbcsxsxG
Increasing the optimization level gets rid of the extra jump.
Of course, there is no guarantee that gcc won't learn about
assembler constants. :-/
So the gcc docs are actively wrong, and %= does nothing - it will
still compare as the exact same inline asm, because the string
equality testing is apparently done before any expansion.
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
And again - the above works only as long as "#" is a valid comment
character in the assembler. And I have this very dim memory of us
having comments in inline asm, and it breaking certain configurations
(for when the assembler that the compiler uses is a special
human-unfriendly one that only accepts compiler output).
You could make even more disgusting hacks, and have it generate something like
.pushsection .discard.barrier
.long #id
.popsection
instead of a comment. We already expect that to work and have generic
inline asm cases that generate code like that.
On Sat, Jun 05, 2021 at 09:43:33PM -0700, Paul E. McKenney wrote:
So gcc might some day note a do-nothing asm and duplicate it for
the sole purpose of collapsing the "then" and "else" clauses. I
guess I need to keep my paranoia for the time being, then. :-/
Or a "do-something" asm, even. What it does is make sure it is executed
on the real machine exactly like on the abstract machine. That is how C
is defined, what a compiler *does*.
The programmer does not have any direct control over the generated code.
Of course, there is no guarantee that gcc won't learn about
assembler constants. :-/
I am not sure what you call an "assembler constant" here. But you can
be sure that GCC will not start doing anything here. GCC does not try
to understand what you wrote in an inline asm, it just fills in the
operands and that is all. It can do all the same things to it that it
can do to any other code of course: duplicate it, deduplicate it,
frobnicate it, etc.
Segher
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-06 19:07:06
On Sun, Jun 06, 2021 at 08:17:40AM -0500, Segher Boessenkool wrote:
On Sat, Jun 05, 2021 at 09:43:33PM -0700, Paul E. McKenney wrote:
quoted
So gcc might some day note a do-nothing asm and duplicate it for
the sole purpose of collapsing the "then" and "else" clauses. I
guess I need to keep my paranoia for the time being, then. :-/
Or a "do-something" asm, even. What it does is make sure it is executed
on the real machine exactly like on the abstract machine. That is how C
is defined, what a compiler *does*.
The programmer does not have any direct control over the generated code.
I am not looking for direct control, simply sufficient influence. ;-)
quoted
Of course, there is no guarantee that gcc won't learn about
assembler constants. :-/
I am not sure what you call an "assembler constant" here. But you can
be sure that GCC will not start doing anything here. GCC does not try
to understand what you wrote in an inline asm, it just fills in the
operands and that is all. It can do all the same things to it that it
can do to any other code of course: duplicate it, deduplicate it,
frobnicate it, etc.
Apologies, that "assembler constants" should have been "assembler
comments".
Thanx, Paul
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
On Sat, Jun 5, 2021 at 6:29 PM Alan Stern [off-list ref] wrote:
quoted
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
That's actually a feature in some cases, ie the ability to do CSE on
asm statements (ie the "always has the same output" optimization that
the docs talk about).
So gcc has always looked at the asm string for that reason, afaik.
GCC does not pretend it can understand the asm. But it can see when
two asm statements are identical.
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
Why would that be? "asm volatile" does not prevent optimisation. It
says this code has some unspecified side effect, and that is all! All
the usual C rules cover everything needed: the same side effects have to
be executed in the same order on the real machine as they would on the
abstract machine.
There is a statement of "Under certain circumstances, GCC may
duplicate (or remove duplicates of) your assembly code when
optimizing" and a suggestion of using "%=" to generate a unique
instance of an asm.
"%=" outputs a number unique for every output instruction (the whole asm
is one instruction; these are GCC internal instructions, not the same
thing as machine instructions). This will not help here. The actual
thing the manual says is
Under certain circumstances, GCC may duplicate (or remove duplicates
of) your assembly code when optimizing. This can lead to unexpected
duplicate symbol errors during compilation if your 'asm' code defines
symbols or labels. Using '%=' may help resolve this problem.
It helps prevent duplicated symbols and labels. It does not do much
else.
Which might actually be a good idea for "barrier()", just in case.
However, the problem with that is that I don't think we are guaranteed
to have a universal comment character for asm statements.
That's right. But ";#" works on most systems, you may be able to use
that?
IOW, it might be a good idea to do something like
#define barrier() \
__asm__ __volatile__("# barrier %=": : :"memory")
but I'm not 100% convinced that '#' is always a comment in asm code,
so the above might not actually build everywhere.
Some assemblers use ";", some use "!", and there are more variations.
But this will not do what you want. "%=" is output as a unique number
*after* everything GCC has done with the asm.
However, *testing* the above (in my config, where '#' does work as a
comment character) shows that gcc doesn't actually consider them to be
distinct EVEN THEN, and will still merge two barrier statements.
Yes, the insns have the same templates, will output the exact same to
the generated assembler code, so are CSEd.
So the gcc docs are actively wrong, and %= does nothing - it will
still compare as the exact same inline asm, because the string
equality testing is apparently done before any expansion.
They are not wrong. Maybe the doc could be clearer though? Patches
welcome.
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
__COUNTER__ is a preprocessor thing, much more like what you want here:
this does its work *before* everything the compiler does, while %= does
its thing *after* :-)
(Not that I actually understand what you are trying to do with this).
Segher
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-06 13:48:05
On Sun, Jun 06, 2021 at 07:59:55AM -0500, Segher Boessenkool wrote:
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
quoted
On Sat, Jun 5, 2021 at 6:29 PM Alan Stern [off-list ref] wrote:
quoted
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
That's actually a feature in some cases, ie the ability to do CSE on
asm statements (ie the "always has the same output" optimization that
the docs talk about).
So gcc has always looked at the asm string for that reason, afaik.
GCC does not pretend it can understand the asm. But it can see when
two asm statements are identical.
How similar do two asm strings have to be before they are considered
identical? For instance, do changes to the amount of leading or
trailing whitespace matter?
Or what about including an empty assembly statement in one but not the
other?
Alan
On Sun, Jun 06, 2021 at 09:47:49AM -0400, Alan Stern wrote:
quoted
GCC does not pretend it can understand the asm. But it can see when
two asm statements are identical.
How similar do two asm strings have to be before they are considered
identical? For instance, do changes to the amount of leading or
trailing whitespace matter?
They have to be identical to be considered identical.
Or what about including an empty assembly statement in one but not the
other?
On Sun, Jun 6, 2021 at 6:03 AM Segher Boessenkool
[off-list ref] wrote:
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
quoted
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
Why would that be? "asm volatile" does not prevent optimisation.
Sure it does.
That's the whole and only *POINT* of the "volatile".
It's the same as a vol;atile memory access. That very much prevents
certain optimizations. You can't just join two volatile reads or
writes, because they have side effects.
And the exact same thing is true of inline asm. Even when they are
*identical*, inline asms have side effects that gcc simply doesn't
understand.
And yes, those side effects can - and do - include "you can't just merge these".
It says this code has some unspecified side effect, and that is all!
And that should be sufficient. But gcc then violates it, because gcc
doesn't understand the side effects.
Now, the side effects may be *subtle*, but they are very very real.
Just placement of code wrt a branch will actually affect memory
ordering, as that one example was.
quoted
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
__COUNTER__ is a preprocessor thing, much more like what you want here:
this does its work *before* everything the compiler does, while %= does
its thing *after* :-)
(Not that I actually understand what you are trying to do with this).
See my previous email for why two barriers in two different code
sequences cannot just be joined into one and moved into the common
parent. It actually is semantically meaningful *where* they are, and
they are distinct barriers.
The case we happen to care about is memory ordering issues. The
example quoted may sound pointless and insane, and I actually don't
believe we have real code that triggers the issue, because whenever we
have a conditional barrier, the two sides of the conditional are
generally so different that gcc would never merge any of it anyway.
So the issue is mostly theoretical, but we do have code that is fairly
critical, and that depends on memory ordering, and on some weakly
ordered machines (which is where all these problems would happen),
actual explicit memory barriers are also <i>much</i> too expensive.
End result: we have code that depends on the fact that a read-to-write
ordering exists if there is a data dependency or a control dependency
between the two. No actual expensive CPU instruction to specify the
ordering, because the ordering is implicit in the code flow itself.
But that's what we need a compiler barrier for in the first place -
the compiler certainly doesn't understand about this very subtle
memory ordering issue, and we want to make sure that the code sequence
*remains* that "if A then write B".
Linus
On Sun, Jun 06, 2021 at 11:25:46AM -0700, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 6:03 AM Segher Boessenkool
[off-list ref] wrote:
quoted
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
quoted
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
Why would that be? "asm volatile" does not prevent optimisation.
Sure it does.
That's the whole and only *POINT* of the "volatile".
It's the same as a vol;atile memory access. That very much prevents
certain optimizations. You can't just join two volatile reads or
writes, because they have side effects.
You can though. In exactly this same way:
volatile int x;
void g(int);
void f(int n) { if (n) g(x); else g(x); }
==>
f:
movl x(%rip), %edi
jmp g
You can do whatever you want with code with side effects. The only
thing required is that the side effects are executed as often as before
and in the same order. Merging identical sides of a diamond is just
fine.
And the exact same thing is true of inline asm. Even when they are
*identical*, inline asms have side effects that gcc simply doesn't
understand.
Only volatile asm does (including all asm without outputs). But that
still does not mean GCC cannot manipulate the asm!
And yes, those side effects can - and do - include "you can't just merge these".
They do not. That is not what a side effect is.
quoted
It says this code has some unspecified side effect, and that is all!
And that should be sufficient. But gcc then violates it, because gcc
doesn't understand the side effects.
Now, the side effects may be *subtle*, but they are very very real.
Just placement of code wrt a branch will actually affect memory
ordering, as that one example was.
You have a different definition of "side effect" than C does apparently.
5.1.2.3/2:
Accessing a volatile object, modifying an object, modifying a file, or
calling a function that does any of those operations are all side
effects, which are changes in the state of the execution environment.
Evaluation of an expression in general includes both value
computations and initiation of side effects. Value computation for an
lvalue expression includes determining the identity of the designated
object.
But that's what we need a compiler barrier for in the first place -
the compiler certainly doesn't understand about this very subtle
memory ordering issue, and we want to make sure that the code sequence
*remains* that "if A then write B".
The compiler doesn't magically understand your intention, no. Some real
work will need to be done to make this work.
Segher
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-06 18:41:55
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
On Sat, Jun 5, 2021 at 6:29 PM Alan Stern [off-list ref] wrote:
quoted
Interesting. And changing one of the branches from barrier() to __asm__
__volatile__("nop": : :"memory") also causes a branch to be emitted. So
even though the compiler doesn't "look inside" assembly code, it does
compare two pieces at least textually and apparently assumes if they are
identical then they do the same thing.
That's actually a feature in some cases, ie the ability to do CSE on
asm statements (ie the "always has the same output" optimization that
the docs talk about).
So gcc has always looked at the asm string for that reason, afaik.
I think it's something of a bug when it comes to "asm volatile", but
the documentation isn't exactly super-specific.
There is a statement of "Under certain circumstances, GCC may
duplicate (or remove duplicates of) your assembly code when
optimizing" and a suggestion of using "%=" to generate a unique
instance of an asm.
Which might actually be a good idea for "barrier()", just in case.
However, the problem with that is that I don't think we are guaranteed
to have a universal comment character for asm statements.
IOW, it might be a good idea to do something like
#define barrier() \
__asm__ __volatile__("# barrier %=": : :"memory")
but I'm not 100% convinced that '#' is always a comment in asm code,
so the above might not actually build everywhere.
However, *testing* the above (in my config, where '#' does work as a
comment character) shows that gcc doesn't actually consider them to be
distinct EVEN THEN, and will still merge two barrier statements.
That's distressing.
So the gcc docs are actively wrong, and %= does nothing - it will
still compare as the exact same inline asm, because the string
equality testing is apparently done before any expansion.
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
And again - the above works only as long as "#" is a valid comment
character in the assembler. And I have this very dim memory of us
having comments in inline asm, and it breaking certain configurations
(for when the assembler that the compiler uses is a special
human-unfriendly one that only accepts compiler output).
You could make even more disgusting hacks, and have it generate something like
.pushsection .discard.barrier
.long #id
.popsection
instead of a comment. We already expect that to work and have generic
inline asm cases that generate code like that.
I tried the experiment with this code:
#define READ_ONCE(x) (*(volatile typeof(x) *)&(x))
#define WRITE_ONCE(x, val) (READ_ONCE(x) = (val))
#define barrier() __asm__ __volatile__("": : :"memory")
int x, y;
int main(int argc, char *argv[])
{
if (READ_ONCE(x)) {
barrier();
y = 1;
} else {
y = 1;
}
return 0;
}
The output from gcc -O2 is:
main:
mov eax, DWORD PTR x[rip]
test eax, eax
je .L2
.L2:
mov DWORD PTR y[rip], 1
The output from clang is essentially the same (the mov and test are
replaced by a cmp).
This does what we want, but I wouldn't bet against a future
optimization pass getting rid of the "useless" test and branch.
Alan
From: Jakub Jelinek <hidden> Date: 2021-06-06 18:59:44
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
I think just
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
should be enough (or "X" instead of "i" if some arch uses -fpic and will not
accept small constants in PIC code), for CSE gcc compares that the asm template
string and all arguments are the same.
As for volatile, that is implicit on asm without any output operands and
it is about whether the inline asm can be DCEd, not whether it can be CSEd.
Jakub
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-06 19:15:43
On Sun, Jun 06, 2021 at 08:59:22PM +0200, Jakub Jelinek wrote:
On Sat, Jun 05, 2021 at 08:41:00PM -0700, Linus Torvalds wrote:
quoted
Something like this *does* seem to work:
#define ____barrier(id) __asm__ __volatile__("#" #id: : :"memory")
#define __barrier(id) ____barrier(id)
#define barrier() __barrier(__COUNTER__)
which is "interesting" or "disgusting" depending on how you happen to feel.
I think just
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
should be enough (or "X" instead of "i" if some arch uses -fpic and will not
accept small constants in PIC code), for CSE gcc compares that the asm template
string and all arguments are the same.
As for volatile, that is implicit on asm without any output operands and
it is about whether the inline asm can be DCEd, not whether it can be CSEd.
Jakub
On Sun, Jun 6, 2021 at 11:59 AM Jakub Jelinek [off-list ref] wrote:
I think just
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
should be enough
Oh, I like that. Much better.
It avoids all the issues with comments etc, and because it's not using
__COUNTER__ as a string, it doesn't need the preprocessor games with
double expansion either.
So yeah, that seems like a nice solution to the issue, and should make
the barriers all unique to the compiler.
Linus
On Sun, Jun 06, 2021 at 12:22:44PM -0700, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 11:59 AM Jakub Jelinek [off-list ref] wrote:
quoted
I think just
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
should be enough
Oh, I like that. Much better.
It avoids all the issues with comments etc, and because it's not using
__COUNTER__ as a string, it doesn't need the preprocessor games with
double expansion either.
So yeah, that seems like a nice solution to the issue, and should make
the barriers all unique to the compiler.
__COUNTER__ is a preprocessor thing as well, and it may not do all that
you expect. Ex.:
===
#define fm() __COUNTER__
int gm(void) { return fm(); }
int hm(void) { return fm(); }
int fi(void) { return __COUNTER__; }
int gi(void) { return fi(); }
int hi(void) { return fi(); }
===
The macro version here works as you would hope, but the inlined one has
the same number everywhere.
Segher
From: Alexander Monakov <hidden> Date: 2021-06-06 21:19:29
On Sun, 6 Jun 2021, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 11:59 AM Jakub Jelinek [off-list ref] wrote:
quoted
I think just
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
should be enough
Oh, I like that. Much better.
It avoids all the issues with comments etc, and because it's not using
__COUNTER__ as a string, it doesn't need the preprocessor games with
double expansion either.
So yeah, that seems like a nice solution to the issue, and should make
the barriers all unique to the compiler.
It also plants a nice LTO time-bomb (__COUNTER__ values will be unique
only within each LTO input unit, not across all of them).
Alexander
On Sun, Jun 6, 2021 at 2:19 PM Alexander Monakov [off-list ref] wrote:
quoted
So yeah, that seems like a nice solution to the issue, and should make
the barriers all unique to the compiler.
It also plants a nice LTO time-bomb (__COUNTER__ values will be unique
only within each LTO input unit, not across all of them).
That could be an issue in other circumstances, but for at least
volatile_if() that doesn't much matter. The decision there is purely
local, and it's literally about the two sides of the conditional not
being merged.
Now, an optimizing linker or assembler can of course do anything at
all in theory: and if that ends up being an issue we'd have to have
some way to actually propagate the barrier from being just a compiler
thing. Right now gcc doesn't even output the barrier in the assembly
code, so it's invisible to any optimizing assembler/linker thing.
But I don't think that's an issue with what _currently_ goes on in an
assembler or linker - not even a smart one like LTO.
And such things really are independent of "volatile_if()". We use
barriers for other things where we need to force some kind of
operation ordering, and right now the only thing that re-orders
accesses etc is the compiler.
Btw, since we have compiler people on line, the suggested 'barrier()'
isn't actually perfect for this particular use:
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
in the general barrier case, we very much want to have that "memory"
clobber, because the whole point of the general barrier case is that
we want to make sure that the compiler doesn't cache memory state
across it (ie the traditional use was basically what we now use
"cpu_relax()" for, and you would use it for busy-looping on some
condition).
In the case of "volatile_if()", we actually would like to have not a
memory clobber, but a "memory read". IOW, it would be a barrier for
any writes taking place, but reads can move around it.
I don't know of any way to express that to the compiler. We've used
hacks for it before (in gcc, BLKmode reads turn into that kind of
barrier in practice, so you can do something like make the memory
input to the asm be a big array). But that turned out to be fairly
unreliable, so now we use memory clobbers even if we just mean "reads
random memory".
Example: variable_test_bit(), which generates a "bt" instruction, does
: "m" (*(unsigned long *)addr), "Ir" (nr) : "memory");
and the memory clobber is obviously wrong: 'bt' only *reads* memory,
but since the whole reason we use it is that it's not just that word
at address 'addr', in order to make sure that any previous writes are
actually stable in memory, we use that "memory" clobber.
It would be much nicer to have a "memory read" marker instead, to let
the compiler know "I need to have done all pending writes to memory,
but I can still cache read values over this op because it doesn't
_change_ memory".
Anybody have ideas or suggestions for something like that?
Linus
Example: variable_test_bit(), which generates a "bt" instruction, does
: "m" (*(unsigned long *)addr), "Ir" (nr) : "memory");
and the memory clobber is obviously wrong: 'bt' only *reads* memory,
but since the whole reason we use it is that it's not just that word
at address 'addr', in order to make sure that any previous writes are
actually stable in memory, we use that "memory" clobber.
It would be much nicer to have a "memory read" marker instead, to let
the compiler know "I need to have done all pending writes to memory,
but I can still cache read values over this op because it doesn't
_change_ memory".
Anybody have ideas or suggestions for something like that?
The obvious thing is to try and mark the function as pure. But when
applied to a static inline, gcc seems to read the contents and say "nah,
you have something here that declares itself to possibly write to
memory". Replacing with a call to an extern function marked pure does
indeed cause gcc to cache the value of y*z, so in theory this should be
possible, if one could convince gcc to "trust me, this really is a pure
function".
https://godbolt.org/z/s4546K6Pj
Rasmus
memory". Replacing with a call to an extern function marked pure does
indeed cause gcc to cache the value of y*z, so in theory this should be
possible, if one could convince gcc to "trust me, this really is a pure
function".
Don't know why I didn't think to check before sending, but FWIW clang
doesn't need convincing, it already takes the __pure at face value and
caches y*z.
Rasmus
From: Alexander Monakov <hidden> Date: 2021-06-07 08:01:47
On Sun, 6 Jun 2021, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 2:19 PM Alexander Monakov [off-list ref] wrote:
quoted
quoted
So yeah, that seems like a nice solution to the issue, and should make
the barriers all unique to the compiler.
It also plants a nice LTO time-bomb (__COUNTER__ values will be unique
only within each LTO input unit, not across all of them).
That could be an issue in other circumstances, but for at least
volatile_if() that doesn't much matter. The decision there is purely
local, and it's literally about the two sides of the conditional not
being merged.
Now, an optimizing linker or assembler can of course do anything at
all in theory: and if that ends up being an issue we'd have to have
some way to actually propagate the barrier from being just a compiler
thing. Right now gcc doesn't even output the barrier in the assembly
code, so it's invisible to any optimizing assembler/linker thing.
But I don't think that's an issue with what _currently_ goes on in an
assembler or linker - not even a smart one like LTO.
And such things really are independent of "volatile_if()". We use
barriers for other things where we need to force some kind of
operation ordering, and right now the only thing that re-orders
accesses etc is the compiler.
Uhh... I was not talking about some (non-existent) "optimizing linker".
LTO works by relaunching the compiler from the linker and letting it
consume multiple translation units (which are fully preprocessed by that
point). So the very thing you wanted to avoid -- such barriers appearing
in close proximity where they can be deduplicated -- may arise after a
little bit of cross-unit inlining.
My main point here is that using __COUNTER__ that way (making things
"unique" for the compiler) does not work in general when LTO enters the
picture. As long as that is remembered, I'm happy.
Btw, since we have compiler people on line, the suggested 'barrier()'
isn't actually perfect for this particular use:
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
in the general barrier case, we very much want to have that "memory"
clobber, because the whole point of the general barrier case is that
we want to make sure that the compiler doesn't cache memory state
across it (ie the traditional use was basically what we now use
"cpu_relax()" for, and you would use it for busy-looping on some
condition).
In the case of "volatile_if()", we actually would like to have not a
memory clobber, but a "memory read". IOW, it would be a barrier for
any writes taking place, but reads can move around it.
I don't know of any way to express that to the compiler. We've used
hacks for it before (in gcc, BLKmode reads turn into that kind of
barrier in practice, so you can do something like make the memory
input to the asm be a big array). But that turned out to be fairly
unreliable, so now we use memory clobbers even if we just mean "reads
random memory".
So the barrier which is a compiler barrier but not a machine barrier is
__atomic_signal_fence(model), but internally GCC will not treat it smarter
than an asm-with-memory-clobber today.
Example: variable_test_bit(), which generates a "bt" instruction, does
: "m" (*(unsigned long *)addr), "Ir" (nr) : "memory");
and the memory clobber is obviously wrong: 'bt' only *reads* memory,
but since the whole reason we use it is that it's not just that word
at address 'addr', in order to make sure that any previous writes are
actually stable in memory, we use that "memory" clobber.
It would be much nicer to have a "memory read" marker instead, to let
the compiler know "I need to have done all pending writes to memory,
but I can still cache read values over this op because it doesn't
_change_ memory".
Anybody have ideas or suggestions for something like that?
In the specific case of 'bt', the offset cannot be negative, so I think you
can simply spell out the extent of the array being accessed:
: "m" *(unsigned long (*)[-1UL / 8 / sizeof(long) + 1])addr
In the general case (possibility of negative offsets, or no obvious base to
supply), have you considered adding a "wild read" through a char pointer
that is initialized in a non-transparent way? Like this:
char *wild_pointer;
asm(""
: "=X"(wild_pointer)
: "X"(base1)
, "X"(base2)); // unknown value related to given base pointers
asm("pattern"
: // normal outputs
: // normal inputs
, "m"(*wild_pointer));
The "X" constraint in theory should not tie up neither a register nor a stack
slot.
Alexander
From: Marco Elver <elver@google.com> Date: 2021-06-07 08:28:11
On Mon, 7 Jun 2021 at 10:02, Alexander Monakov [off-list ref] wrote:
On Sun, 6 Jun 2021, Linus Torvalds wrote:
[...]
quoted
On Sun, Jun 6, 2021 at 2:19 PM Alexander Monakov [off-list ref] wrote:
[...]
quoted
Btw, since we have compiler people on line, the suggested 'barrier()'
isn't actually perfect for this particular use:
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
in the general barrier case, we very much want to have that "memory"
clobber, because the whole point of the general barrier case is that
we want to make sure that the compiler doesn't cache memory state
across it (ie the traditional use was basically what we now use
"cpu_relax()" for, and you would use it for busy-looping on some
condition).
In the case of "volatile_if()", we actually would like to have not a
memory clobber, but a "memory read". IOW, it would be a barrier for
any writes taking place, but reads can move around it.
I don't know of any way to express that to the compiler. We've used
hacks for it before (in gcc, BLKmode reads turn into that kind of
barrier in practice, so you can do something like make the memory
input to the asm be a big array). But that turned out to be fairly
unreliable, so now we use memory clobbers even if we just mean "reads
random memory".
So the barrier which is a compiler barrier but not a machine barrier is
__atomic_signal_fence(model), but internally GCC will not treat it smarter
than an asm-with-memory-clobber today.
FWIW, Clang seems to be cleverer about it, and seems to do the optimal
thing if I use a __atomic_signal_fence(__ATOMIC_RELEASE):
https://godbolt.org/z/4v5xojqaY
Thanks,
-- Marco
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-07 15:28:12
On Mon, Jun 07, 2021 at 10:27:10AM +0200, Marco Elver wrote:
On Mon, 7 Jun 2021 at 10:02, Alexander Monakov [off-list ref] wrote:
quoted
On Sun, 6 Jun 2021, Linus Torvalds wrote:
[...]
quoted
quoted
On Sun, Jun 6, 2021 at 2:19 PM Alexander Monakov [off-list ref] wrote:
[...]
quoted
quoted
Btw, since we have compiler people on line, the suggested 'barrier()'
isn't actually perfect for this particular use:
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
in the general barrier case, we very much want to have that "memory"
clobber, because the whole point of the general barrier case is that
we want to make sure that the compiler doesn't cache memory state
across it (ie the traditional use was basically what we now use
"cpu_relax()" for, and you would use it for busy-looping on some
condition).
In the case of "volatile_if()", we actually would like to have not a
memory clobber, but a "memory read". IOW, it would be a barrier for
any writes taking place, but reads can move around it.
I don't know of any way to express that to the compiler. We've used
hacks for it before (in gcc, BLKmode reads turn into that kind of
barrier in practice, so you can do something like make the memory
input to the asm be a big array). But that turned out to be fairly
unreliable, so now we use memory clobbers even if we just mean "reads
random memory".
So the barrier which is a compiler barrier but not a machine barrier is
__atomic_signal_fence(model), but internally GCC will not treat it smarter
than an asm-with-memory-clobber today.
FWIW, Clang seems to be cleverer about it, and seems to do the optimal
thing if I use a __atomic_signal_fence(__ATOMIC_RELEASE):
https://godbolt.org/z/4v5xojqaY
Indeed it does! But I don't know of a guarantee for that helpful
behavior.
Thanx, Paul
From: Marco Elver <elver@google.com> Date: 2021-06-07 17:05:23
On Mon, Jun 07, 2021 at 08:28AM -0700, Paul E. McKenney wrote:
On Mon, Jun 07, 2021 at 10:27:10AM +0200, Marco Elver wrote:
quoted
On Mon, 7 Jun 2021 at 10:02, Alexander Monakov [off-list ref] wrote:
quoted
On Sun, 6 Jun 2021, Linus Torvalds wrote:
[...]
quoted
quoted
On Sun, Jun 6, 2021 at 2:19 PM Alexander Monakov [off-list ref] wrote:
[...]
quoted
quoted
Btw, since we have compiler people on line, the suggested 'barrier()'
isn't actually perfect for this particular use:
#define barrier() __asm__ __volatile__("" : : "i" (__COUNTER__) : "memory")
in the general barrier case, we very much want to have that "memory"
clobber, because the whole point of the general barrier case is that
we want to make sure that the compiler doesn't cache memory state
across it (ie the traditional use was basically what we now use
"cpu_relax()" for, and you would use it for busy-looping on some
condition).
In the case of "volatile_if()", we actually would like to have not a
memory clobber, but a "memory read". IOW, it would be a barrier for
any writes taking place, but reads can move around it.
I don't know of any way to express that to the compiler. We've used
hacks for it before (in gcc, BLKmode reads turn into that kind of
barrier in practice, so you can do something like make the memory
input to the asm be a big array). But that turned out to be fairly
unreliable, so now we use memory clobbers even if we just mean "reads
random memory".
So the barrier which is a compiler barrier but not a machine barrier is
__atomic_signal_fence(model), but internally GCC will not treat it smarter
than an asm-with-memory-clobber today.
FWIW, Clang seems to be cleverer about it, and seems to do the optimal
thing if I use a __atomic_signal_fence(__ATOMIC_RELEASE):
https://godbolt.org/z/4v5xojqaY
Indeed it does! But I don't know of a guarantee for that helpful
behavior.
Is there a way we can interpret the standard in such a way that it
should be guaranteed?
If yes, it should be easy to add tests to the compiler repos for
snippets that the Linux kernel relies on (if we decide to use
__atomic_signal_fence() for this).
If no, we can still try to add tests to the compiler repos, but may
receive some push-back at the very latest when some optimization pass
decides to break it. Because the argument then is that it's well within
the language standard.
Adding language extensions will likely be met with resistance, because
some compiler folks are afraid of creating language forks (the reason
why we have '-enable-trivial-auto-var-init-zero-knowing-it-will-be-removed-from-clang').
That could be solved if we declare Linux-C a "standard", and finally get
-std=linux or such, at which point asking for "volatile if" directly
would probably be easier without jumping through hoops.
The jumping-through-hoops variant would probably be asking for a
__builtin primitive that allows constructing volatile_if() (if we can't
bend existing primitives to do what we want).
Thanks,
-- Marco
From: Marco Elver <elver@google.com> Date: 2021-06-08 09:31:55
On Mon, 7 Jun 2021 at 19:04, Marco Elver [off-list ref] wrote:
[...]
quoted
quoted
quoted
So the barrier which is a compiler barrier but not a machine barrier is
__atomic_signal_fence(model), but internally GCC will not treat it smarter
than an asm-with-memory-clobber today.
FWIW, Clang seems to be cleverer about it, and seems to do the optimal
thing if I use a __atomic_signal_fence(__ATOMIC_RELEASE):
https://godbolt.org/z/4v5xojqaY
Indeed it does! But I don't know of a guarantee for that helpful
behavior.
Is there a way we can interpret the standard in such a way that it
should be guaranteed?
I figured out why it works, and unfortunately it's suboptimal codegen.
In LLVM __atomic_signal_fence() turns into a real IR instruction,
which when lowered to asm just doesn't emit anything. But most
optimizations happen before in IR, and a "fence" cannot be removed.
Essentially imagine there's an invisible instruction, which explains
why it does what it does. Sadly we can't rely on that.
The jumping-through-hoops variant would probably be asking for a
__builtin primitive that allows constructing volatile_if() (if we can't
bend existing primitives to do what we want).
I had a think about this. I think if we ask for some primitive
compiler support, "volatile if" as the target is suboptimal design,
because it somewhat limits composability (and of course make it hard
to get as an extension). That primitive should probably also support
for/while/switch. But "volatile if" would also preclude us from
limiting the scope of the source of forced dependency, e.g. say we
have "if (A && B)", but we only care about A.
The cleaner approach would be an expression wrapper, e.g. "if
(ctrl_depends(A) && B) { ... }".
I imagine syntactically it'd be similar to __builtin_expect(..). I
think that's also easier to request an extension for, say
__builtin_ctrl_depends(expr). (If that is appealing, we can try and
propose it as std::ctrl_depends() along with std::dependent_ptr<>.)
Thoughts?
Thanks,
-- Marco
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-08 11:24:27
On Tue, Jun 08, 2021 at 11:30:36AM +0200, Marco Elver wrote:
The cleaner approach would be an expression wrapper, e.g. "if
(ctrl_depends(A) && B) { ... }".
I imagine syntactically it'd be similar to __builtin_expect(..). I
think that's also easier to request an extension for, say
__builtin_ctrl_depends(expr). (If that is appealing, we can try and
propose it as std::ctrl_depends() along with std::dependent_ptr<>.)
Thoughts?
Works for me; and note how it mirrors how we implemented volatile_if()
in the first place, by doing an expression wrapper.
__builtin_ctrl_depends(expr) would have to:
- ensure !__builtin_const_p(expr) (A)
- imply an acquire compiler fence (B)
- ensure cond-branch is emitted (C)
*OR*
- ensure !__builtin_const_p(expr); (A)
- upgrade the load in @expr to load-acquire (D)
A)
This all hinges on there actually being a LOAD, if expr is constant, we
have a malformed program and can emit a compiler error.
B)
We want to capture any store, not just volatile stores that come after.
The example here is a ring-buffer that loads the (head and) tail pointer
to check for space and then writes data elements. It would be
'cumbersome' to have all the data writes as volatile.
C)
We depend on the load-to-branch data dependency to guard the store to
provide the LOAD->STORE memory order.
D)
Upgrading LOAD to LOAD-ACQUIRE also provides LOAD->STORE ordering, but
it does require that the compiler has access to the LOAD in the first
place, which isn't a given seeing how much asm() we have around. Also
the achitecture should have a sheep LOAD-ACQUIRE in the first place,
otherwise there's no point.
If this is done, the branch is allowed to be optimized away if the
compiler so wants.
Now, Will will also want to allow the load-acquire to be run-time
patched between the RCsc and RCpc variant depending on what ARMv8
extentions are available, which will be 'interesting' (although I can
think of ways to actually do that, one would be to keep a special
section that tracks the location of these __builtin_ctrl_depends()
generated load-acquire instruction).
On Tue, Jun 08, 2021 at 01:22:58PM +0200, Peter Zijlstra wrote:
Works for me; and note how it mirrors how we implemented volatile_if()
in the first place, by doing an expression wrapper.
__builtin_ctrl_depends(expr) would have to:
- ensure !__builtin_const_p(expr) (A)
Why would it be an error if __builtin_constant_p(expr)? In many
programs the compiler can figure out some expression does never change.
Having a control dependency on sometthing like that is not erroneous.
- imply an acquire compiler fence (B)
- ensure cond-branch is emitted (C)
(C) is almost impossible to do. This should be reformulated to talk
about the effect of the generated code, instead.
*OR*
- ensure !__builtin_const_p(expr); (A)
- upgrade the load in @expr to load-acquire (D)
So that will only work if there is exactly one read from memory in expr?
That is problematic.
This needs some work.
Segher
From: Marco Elver <elver@google.com> Date: 2021-06-09 12:44:47
On Tue, 8 Jun 2021 at 17:30, Segher Boessenkool
[off-list ref] wrote:
On Tue, Jun 08, 2021 at 01:22:58PM +0200, Peter Zijlstra wrote:
quoted
Works for me; and note how it mirrors how we implemented volatile_if()
in the first place, by doing an expression wrapper.
__builtin_ctrl_depends(expr) would have to:
- ensure !__builtin_const_p(expr) (A)
Why would it be an error if __builtin_constant_p(expr)? In many
programs the compiler can figure out some expression does never change.
Having a control dependency on sometthing like that is not erroneous.
quoted
- imply an acquire compiler fence (B)
- ensure cond-branch is emitted (C)
(C) is almost impossible to do. This should be reformulated to talk
about the effect of the generated code, instead.
quoted
*OR*
- ensure !__builtin_const_p(expr); (A)
- upgrade the load in @expr to load-acquire (D)
So that will only work if there is exactly one read from memory in expr?
That is problematic.
This needs some work.
There is a valid concern that something at the level of the memory
model requires very precise specification in terms of language
semantics and not generated code. Otherwise it seems difficult to get
compiler folks onboard. And coming up with such a specification may
take a while, especially if we have to venture in the realm of the
C11/C++11 memory model while still trying to somehow make it work for
the LKMM. That seems like a very tricky maze we may want to avoid.
An alternative design would be to use a statement attribute to only
enforce (C) ("__attribute__((mustcontrol))" ?). The rest can be
composed through existing primitives I think (the compiler barriers
need optimizing though), which should give us ctrl_depends().
At least for Clang, it should be doable: https://reviews.llvm.org/D103958
Thanks,
-- Marco
On Wed, Jun 09, 2021 at 02:44:08PM +0200, Marco Elver wrote:
On Tue, 8 Jun 2021 at 17:30, Segher Boessenkool
[off-list ref] wrote:
quoted
This needs some work.
There is a valid concern that something at the level of the memory
model requires very precise specification in terms of language
semantics and not generated code.
Yup, exactly. Especially because the meaning of generated code is hard
to describe, and even much more so if you do not limit yourself to a
single machine architecture.
Otherwise it seems difficult to get
compiler folks onboard.
It isn't just difficult to get us on board without it, we know it just
is impossible to do anything sensible without it.
And coming up with such a specification may
take a while,
Yes.
especially if we have to venture in the realm of the
C11/C++11 memory model while still trying to somehow make it work for
the LKMM. That seems like a very tricky maze we may want to avoid.
Well, you only need to use the saner parts of the memory model (not the
full thing), and extensions are fine as well of course.
An alternative design would be to use a statement attribute to only
enforce (C) ("__attribute__((mustcontrol))" ?).
Statement attributes only exist for empty statements. It is unclear how
(and if!) we could support it for general statements.
Some new builtin seems to fit the requirements better? I haven't looked
too closely though.
Segher
Some new builtin seems to fit the requirements better? I haven't looked
too closely though.
I had a longer discussion with someone offline about it, and the
problem with a builtin is similar to the "memory_order_consume
implementation problem" -- you might have an expression that uses the
builtin in some function without any control, and merely returns the
result of the expression as a result. If that function is in another
compilation unit, it then becomes difficult to propagate this
information without somehow making it part of the type system.
Therefore, by using a statement attribute on conditional control
statements, we do not even have this problem. It seems cleaner
syntactically than having a __builtin_() that is either approximate,
or gives an error if used in the wrong context.
Hence the suggestion for a very simple attribute, which also
side-steps this problem.
Thanks,
-- Marco