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: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 11:44:46
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
+/**
+ * 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))
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
Let us pain bike sheds :-)
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: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 14:13:15
On Fri, Jun 04, 2021 at 01:44:37PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
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))
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
Let us pain bike sheds :-)
I have felt that pain many times... ;-)
Here is what I see thus far from these two threads:
1. volatile_if() as above. Nice ease of use, but might be suboptimal
on architectures where a branch is slower than an acquire load.
2. #1, but with my preferred name of ctrl_dep_if() instead of
volatile_if().
3. READ_ONCE_CTRL() like back in the old days. This has the
advantage of giving the compiler more information, but has
problems with relaxed atomic RMW operations.
4. A full (fool?) solution based on #3 would also include _ctrl
suffixed atomic RMW operations.
5. Your bikeshed color here!
Thanx, Paul
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-04 14:25:52
On Fri, Jun 04, 2021 at 12:12:07PM +0200, Peter Zijlstra wrote:
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>
Is there any interest in doing the same sort of thing for switch
statements? A similar approach would probably work, but maybe people
don't care about it.
Alan
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
On Fri, Jun 04, 2021 at 01:44:37PM +0200, Peter Zijlstra wrote:
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
In standard C statements do not have qualifiers. Unless you can
convince the ISO C committee to have them on "if", you will have a very
hard time convincing any serious compiler to do this.
Segher
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); }))
It isn't needed at all here. cbnz does not write to the condition
register. Neither does it change or access memory, but the "memory"
clobber is to force a false dependency. Writing "cc" as well looks a
bit confusing, given that.
Segher
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
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 16:11:55
On Fri, Jun 04, 2021 at 10:35:18AM -0500, Segher Boessenkool wrote:
On Fri, Jun 04, 2021 at 01:44:37PM +0200, Peter Zijlstra wrote:
quoted
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
In standard C statements do not have qualifiers. Unless you can
convince the ISO C committee to have them on "if", you will have a very
hard time convincing any serious compiler to do this.
While some people like talking to the Committee, I would much rather
explore language extensions with the compiler communities. Such
extensions can then make their way into the Committee once they show
their usefulness.
The whole statement qualifier thing was something that was proposed by a
tools person, although I can't really remember who. I'm not much married
to it, but since it's been the only actual suggestion from a tools
person, it's stuck.
If you have another proposal on how to express this; one you'd rather
see implemented, I'm all ears.
But the fact is that we really do depend on this. And we seem to be
growing more of them, not less.
Data dependencies, control dependencies and address dependencies, C
doesn't really like them, we rely on them. It would be awesome if we can
fix this.
Hi!
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.
Yes, C is still not a portable assembler.
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.
@@ -80,6 +80,19 @@ do { \___p1;\})+#ifndef __ASSEMBLY__+/* Guarantee a conditional branch that depends on @cond. */+static__always_inlineboolvolatile_cond(boolcond)+{+asm_volatile_goto("and. %0,%0,%0; bne %l[l_yes]"+::"r"(cond):"cc","memory":l_yes);+returnfalse;+l_yes:+returntrue;+}+#define volatile_cond volatile_cond+#endif
"cmpwi" is ever so slightly better than "and.". And you can write "cr0"
instead of "cc" more explicitely (it means the same thing though).
I didn't find a description of the expected precise semantics anywhere
in this patch. This however is the most important thing required here!
Segher
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.
On Fri, Jun 4, 2021 at 3:12 AM Peter Zijlstra [off-list ref] wrote:
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).
Why is "volatile_if()" not just
#define barier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
because that should essentially cause the same thing - the compiler
should be *forced* to create one conditional branch (because "barrier"
is an asm that can't be done on the false side, so it can't do it with
arithmetic or other games), and after that we're done.
No need for per-architecture "asm goto" games. No new memory barriers.
No actual new code generation (except for the empty asm volatile that
is a barrier).
Linus
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 16:34:06
On Fri, Jun 04, 2021 at 11:09:55AM -0500, Segher Boessenkool wrote:
I didn't find a description of the expected precise semantics anywhere
in this patch. This however is the most important thing required here!
Fair enough; so a control-dependency is a LOAD->STORE memory ordering
provided by conditional branches.
The conditional branch instruction itself must have a data dependency on
a previous LOAD, while the branch itself guards a STORE. Then because
speculative STOREs result in out-of-thin-air values, the STORE must not
become visible until the branch is decided, which can only be done if
the LOAD is complete.
We make use of this, and would like the compiler to not ruin this code
pattern for us.
So we need the STORE to say inside the selection statement, we need the
LOAD not be optimized away, and we need the conditional branch to be
emitted.
Alternatively, we need the LOAD to be upgraded to a LOAD-ACQUIRE (an
option on platforms where this is sufficiently cheap). Which will also
ensure the STORE happens after.
So we can force the LOAD using READ_ONCE() (a volatile cast).
We can prohibit hoisting by adding a compiler barrier to the expression.
And then we use asm goto() to force emit a conditional branch. Combined
this leaves the compiler very little room to mess things up, but it does
produce sub-optimal code, and doesn't allow the LOAD-ACQUIRE upgrade
Will would like (but he can't always have that anyway due to our other
use of asm()).
We also have a 'CONTROL DEPENDENCIES' section in
Documentation/memory-barriers.txt for further reading.
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 16:37:52
On Fri, Jun 04, 2021 at 09:30:01AM -0700, Linus Torvalds wrote:
On Fri, Jun 4, 2021 at 3:12 AM Peter Zijlstra [off-list ref] wrote:
quoted
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).
Why is "volatile_if()" not just
#define barier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
because that should essentially cause the same thing - the compiler
should be *forced* to create one conditional branch (because "barrier"
is an asm that can't be done on the false side, so it can't do it with
arithmetic or other games), and after that we're done.
No need for per-architecture "asm goto" games. No new memory barriers.
No actual new code generation (except for the empty asm volatile that
is a barrier).
Because we weren't sure compilers weren't still allowed to optimize the
branch away. If compiler folks can guarantee us your thing (along with
maybe the BUILD_BUG_ON(__builtin_constant_p(cond)) thing) always shall
generate a conditional branch instruction, then Yay!
On Fri, Jun 04, 2021 at 06:10:55PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 10:35:18AM -0500, Segher Boessenkool wrote:
quoted
On Fri, Jun 04, 2021 at 01:44:37PM +0200, Peter Zijlstra wrote:
quoted
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
In standard C statements do not have qualifiers. Unless you can
convince the ISO C committee to have them on "if", you will have a very
hard time convincing any serious compiler to do this.
While some people like talking to the Committee, I would much rather
explore language extensions with the compiler communities. Such
extensions can then make their way into the Committee once they show
their usefulness.
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
If you have another proposal on how to express this; one you'd rather
see implemented, I'm all ears.
I would love to see something that meshes well with the rest of C. But
there is no 1-1 translation from C code to machine code (not in either
direction), so anything that more or less depends on that will always
be awkward. If you can actually express the dependency in your source
code that will get us 95% to where we want to be.
Data dependencies, control dependencies and address dependencies, C
doesn't really like them, we rely on them. It would be awesome if we can
fix this.
Yes. The problem is that C is a high-level language. All C semantics
are expressed on a an "as-if" level, never as "do this, then that" --
well, of course that *is* what it says, it's an imperative language just
like most, but that is just how you *think* about things on a conceptual
level, there is nothing that says the machine code has to do the same
thing in the same order as you wrote!
Segher
On Fri, Jun 04, 2021 at 06:37:22PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 09:30:01AM -0700, Linus Torvalds wrote:
quoted
Why is "volatile_if()" not just
#define barier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
because that should essentially cause the same thing - the compiler
should be *forced* to create one conditional branch (because "barrier"
is an asm that can't be done on the false side, so it can't do it with
arithmetic or other games), and after that we're done.
No need for per-architecture "asm goto" games. No new memory barriers.
No actual new code generation (except for the empty asm volatile that
is a barrier).
Because we weren't sure compilers weren't still allowed to optimize the
branch away.
barrier_true is a volatile asm, so it should be executed on the real
machine exactly as often as on the abstract machine (and in order with
other side effects). And the && short-circuits, so you will always have
the same effect as a branch. But there of course is nothing that forces
there to be a branch (as a silly example, the compiler could convert
some control flow to go via computed return addresses).
Segher
On Fri, Jun 4, 2021 at 9:37 AM Peter Zijlstra [off-list ref] wrote:
quoted
Why is "volatile_if()" not just
#define barier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
Because we weren't sure compilers weren't still allowed to optimize the
branch away.
This isn't about some "compiler folks think".
The above CANNOT be compiled any other way than with a branch.
A compiler that optimizes a branch away is simply broken.
Of course, the actual condition (ie "x" above) has to be something
that the compiler cannot statically determine is a constant, but since
the whole - and only - point is that there will be a READ_ONCE() or
similar there, that's not an issue.
The compiler *cannot* just say "oh, I'll do that 'volatile asm
barrier' whether the condition is true or not". That would be a
fundamental compiler bug.
It's as if we wrote
if (x) y++;
and the compiler went "Oh, I'll just increment 'y' unconditionally by
one, I'm sure the programmer doesn't mind, the conditional on 'x' is
immaterial".
No. That's not a C compiler. That's a stinking piece of buggy shit.
The compiler has to honor the conditional.
In that "y++" case, a compiler can decide to do it without a branch,
and basically rewrite the above as
y += !!x;
but with a "volatile asm", that would be a bug.
Of course, we might want to make sure that the compiler doesn't go
"oh, empty asm, I can ignore it", but if that's the case then it's not
about "volatile_if()" any more, at that point it's "oh, the compiler
broke our 'barrier()' implementation", and we have bigger issues.
Linus
On Fri, Jun 04, 2021 at 10:10:29AM -0700, Linus Torvalds wrote:
The compiler *cannot* just say "oh, I'll do that 'volatile asm
barrier' whether the condition is true or not". That would be a
fundamental compiler bug.
Yes.
Of course, we might want to make sure that the compiler doesn't go
"oh, empty asm, I can ignore it",
It isn't allowed to do that. GCC has this arguable misfeature where it
doesn't show empty asm in the assembler output, but that has no bearing
on anything but how human-readable the output is.
Segher
On Fri, Jun 4, 2021 at 10:27 AM Segher Boessenkool
[off-list ref] wrote:
quoted
Of course, we might want to make sure that the compiler doesn't go
"oh, empty asm, I can ignore it",
It isn't allowed to do that. GCC has this arguable misfeature where it
doesn't show empty asm in the assembler output, but that has no bearing
on anything but how human-readable the output is.
That sounds about right, but we have had people talking about the
compiler looking inside the asm string before.
So it worries me that some compiler person might at some point go all
breathy-voice on us and say "I am altering the deal. Pray I don't
alter it any further".
Side note: when grepping for what "barrier()" does on different
architectures and different compilers, I note that yes, it really is
just an empty asm volatile with a "memory" barrier. That should in all
way sbe sufficient.
BUT.
There's this really odd comment in <linux/compiler-intel.h> that talks
about some "ECC" compiler:
/* Intel ECC compiler doesn't support gcc specific asm stmts.
* It uses intrinsics to do the equivalent things.
*/
and it defines it as "__memory_barrier()". This seems to be an ia64 thing, but:
- I cannot get google to find me any documentation on such an intrinsic
- it seems to be bogus anyway, since we have "asm volatile" usage in
at least arch/ia64/mm/tlb.c
So I do note that "barrier()" has an odd definition in one odd ia64
case, and I can't find the semantics for it.
Admittedly I also cannot find it in myself to care. I don't think that
"Intel ECC" compiler case actually exists, and even if it does I don't
think itanium is relevant any more. But it was an odd detail on what
"barrier()" actually might mean to the compiler.
Linus
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-04 18:23:59
On Fri, Jun 04, 2021 at 10:10:29AM -0700, Linus Torvalds wrote:
On Fri, Jun 4, 2021 at 9:37 AM Peter Zijlstra [off-list ref] wrote:
quoted
quoted
Why is "volatile_if()" not just
#define barier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
Because we weren't sure compilers weren't still allowed to optimize the
branch away.
This isn't about some "compiler folks think".
The above CANNOT be compiled any other way than with a branch.
A compiler that optimizes a branch away is simply broken.
Of course, the actual condition (ie "x" above) has to be something
that the compiler cannot statically determine is a constant, but since
the whole - and only - point is that there will be a READ_ONCE() or
similar there, that's not an issue.
In fact there is one weird case where it is an issue (mentioned in
memory-barriers.txt):
If some obscure arch-specific header file does:
#define FOO 1
and an unwitting programmer writes:
volatile_if (READ_ONCE(*y) % FOO == 0)
WRITE_ONCE(*z, 5);
then the compiler _can_ statically determine that the condition is a
constant, in spite of the READ_ONCE, but this fact isn't apparent to the
programmer. The generated object code will include both the read and
the write, but there won't necessarily be any ordering between them.
I don't know if cases like this exist in the kernel. It wouldn't be
surprising if they did though, particularly in situations where a
feature (like multi-level page tables) may be compiled away.
Alan
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.
Hi!
On Fri, Jun 04, 2021 at 10:38:43AM -0700, Linus Torvalds wrote:
On Fri, Jun 4, 2021 at 10:27 AM Segher Boessenkool
[off-list ref] wrote:
quoted
quoted
Of course, we might want to make sure that the compiler doesn't go
"oh, empty asm, I can ignore it",
It isn't allowed to do that. GCC has this arguable misfeature where it
doesn't show empty asm in the assembler output, but that has no bearing
on anything but how human-readable the output is.
That sounds about right, but we have had people talking about the
compiler looking inside the asm string before.
So it worries me that some compiler person might at some point go all
breathy-voice on us and say "I am altering the deal. Pray I don't
alter it any further".
GCC will never do that. And neither will any other compiler that claims
to implement the GCC asm extensions, if they are true to their word.
GCC *does* look inside the assembler template to estimate what code size
this asm will generate, and it tries to be pessimistic about its
estimate so that this will always work, but it always is possible to
mislead the compiler here, precisely because it does not actually
pretend it understands assembler code (think .irp or anything with
assembler macros for example). In very rare cases this leads to
(assembler) errors ("jump target out of range", that kind of thing).
The most effective workaround is to write less silly code ;-) And of
course this is documented, see
<https://gcc.gnu.org/onlinedocs/gcc/Size-of-an-asm.html>
Side note: when grepping for what "barrier()" does on different
architectures and different compilers, I note that yes, it really is
just an empty asm volatile with a "memory" barrier. That should in all
way sbe sufficient.
BUT.
There's this really odd comment in <linux/compiler-intel.h> that talks
about some "ECC" compiler:
/* Intel ECC compiler doesn't support gcc specific asm stmts.
* It uses intrinsics to do the equivalent things.
*/
and it defines it as "__memory_barrier()". This seems to be an ia64 thing, but:
"ecc" apparently was "icc" but for Itanium. It ceased to exist some
time in the 2.4 era apparently. It was still used in 2003. Searching
for "ecpc" (the C++ compiler driver) will find a bit more.
- I cannot get google to find me any documentation on such an intrinsic
- it seems to be bogus anyway, since we have "asm volatile" usage in
at least arch/ia64/mm/tlb.c
So I do note that "barrier()" has an odd definition in one odd ia64
case, and I can't find the semantics for it.
Admittedly I also cannot find it in myself to care.
Yeah, I love code archaeology, but I have work to do as well :-)
I don't think that
"Intel ECC" compiler case actually exists, and even if it does I don't
think itanium is relevant any more. But it was an odd detail on what
"barrier()" actually might mean to the compiler.
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 18:55:30
On Fri, Jun 04, 2021 at 11:40:47AM -0500, Segher Boessenkool wrote:
On Fri, Jun 04, 2021 at 06:10:55PM +0200, Peter Zijlstra wrote:
quoted
On Fri, Jun 04, 2021 at 10:35:18AM -0500, Segher Boessenkool wrote:
quoted
On Fri, Jun 04, 2021 at 01:44:37PM +0200, Peter Zijlstra wrote:
quoted
On naming (sorry Paul for forgetting that in the initial mail); while I
think using the volatile qualifier for the language feature (can we haz
plz, kthxbai) makes perfect sense, Paul felt that we might use a
'better' name for the kernel use, ctrl_dep_if() was proposed.
In standard C statements do not have qualifiers. Unless you can
convince the ISO C committee to have them on "if", you will have a very
hard time convincing any serious compiler to do this.
While some people like talking to the Committee, I would much rather
explore language extensions with the compiler communities. Such
extensions can then make their way into the Committee once they show
their usefulness.
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
Once we have some experience with a language extension, the official
syntax for a standardized version of that extension can be bikeshedded.
Committees being what they are, what we use in the meantime will
definitely not be what is chosen, so there is not a whole lot of point
in worrying about the exact syntax in the meantime. ;-)
quoted
If you have another proposal on how to express this; one you'd rather
see implemented, I'm all ears.
I would love to see something that meshes well with the rest of C. But
there is no 1-1 translation from C code to machine code (not in either
direction), so anything that more or less depends on that will always
be awkward. If you can actually express the dependency in your source
code that will get us 95% to where we want to be.
quoted
Data dependencies, control dependencies and address dependencies, C
doesn't really like them, we rely on them. It would be awesome if we can
fix this.
Yes. The problem is that C is a high-level language. All C semantics
are expressed on a an "as-if" level, never as "do this, then that" --
well, of course that *is* what it says, it's an imperative language just
like most, but that is just how you *think* about things on a conceptual
level, there is nothing that says the machine code has to do the same
thing in the same order as you wrote!
Which is exactly why these conversations are often difficult. There is
a tension between pushing the as-if rule as far as possible within the
compiler on the one hand and allowing developers to write code that does
what is needed on the other. ;-)
Thanx, Paul
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
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 19:18:12
On Fri, Jun 04, 2021 at 12:24:07PM -0500, Segher Boessenkool wrote:
On Fri, Jun 04, 2021 at 10:10:29AM -0700, Linus Torvalds wrote:
quoted
The compiler *cannot* just say "oh, I'll do that 'volatile asm
barrier' whether the condition is true or not". That would be a
fundamental compiler bug.
Yes.
So we can all agree on something like this?
#define volatile_if(x) \
if (({ _Bool __x = (x); BUILD_BUG_ON(__builtin_constant_p(__x)); __x; }) && \
({ barrier(); 1; }))
Do we keep volatile_if() or do we like ctrl_dep_if() better?
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.
On Fri, Jun 04, 2021 at 11:55:26AM -0700, Paul E. McKenney wrote:
On Fri, Jun 04, 2021 at 11:40:47AM -0500, Segher Boessenkool wrote:
quoted
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
Once we have some experience with a language extension, the official
syntax for a standardized version of that extension can be bikeshedded.
Committees being what they are, what we use in the meantime will
definitely not be what is chosen, so there is not a whole lot of point
in worrying about the exact syntax in the meantime. ;-)
I am only saying that it is unlikely any compiler that is used in
production will want to experiment with "volatile if".
quoted
I would love to see something that meshes well with the rest of C. But
there is no 1-1 translation from C code to machine code (not in either
direction), so anything that more or less depends on that will always
be awkward. If you can actually express the dependency in your source
code that will get us 95% to where we want to be.
^^^
quoted
quoted
Data dependencies, control dependencies and address dependencies, C
doesn't really like them, we rely on them. It would be awesome if we can
fix this.
Yes. The problem is that C is a high-level language. All C semantics
are expressed on a an "as-if" level, never as "do this, then that" --
well, of course that *is* what it says, it's an imperative language just
like most, but that is just how you *think* about things on a conceptual
level, there is nothing that says the machine code has to do the same
thing in the same order as you wrote!
Which is exactly why these conversations are often difficult. There is
a tension between pushing the as-if rule as far as possible within the
compiler on the one hand and allowing developers to write code that does
what is needed on the other. ;-)
There is a tension between what users expect from the compiler and what
actually is promised. The compiler is not pushing the as-if rule any
further than it always has: it just becomes better at optimising over
time. The as-if rule is and always has been absolute.
What is needed to get any progress is for user expectations to be
feasible and not contradict existing requirements. See "^^^" above.
Segher
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 20:40:46
On Fri, Jun 04, 2021 at 02:53:01PM -0500, Segher Boessenkool wrote:
On Fri, Jun 04, 2021 at 11:55:26AM -0700, Paul E. McKenney wrote:
quoted
On Fri, Jun 04, 2021 at 11:40:47AM -0500, Segher Boessenkool wrote:
quoted
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
Once we have some experience with a language extension, the official
syntax for a standardized version of that extension can be bikeshedded.
Committees being what they are, what we use in the meantime will
definitely not be what is chosen, so there is not a whole lot of point
in worrying about the exact syntax in the meantime. ;-)
I am only saying that it is unlikely any compiler that is used in
production will want to experiment with "volatile if".
That unfortunately matches my experience over quite a few years. But if
something can be implemented using existing extensions, the conversations
often get easier. Especially given many more people are now familiar
with concurrency.
quoted
quoted
I would love to see something that meshes well with the rest of C. But
there is no 1-1 translation from C code to machine code (not in either
direction), so anything that more or less depends on that will always
be awkward. If you can actually express the dependency in your source
code that will get us 95% to where we want to be.
^^^
quoted
quoted
quoted
Data dependencies, control dependencies and address dependencies, C
doesn't really like them, we rely on them. It would be awesome if we can
fix this.
Yes. The problem is that C is a high-level language. All C semantics
are expressed on a an "as-if" level, never as "do this, then that" --
well, of course that *is* what it says, it's an imperative language just
like most, but that is just how you *think* about things on a conceptual
level, there is nothing that says the machine code has to do the same
thing in the same order as you wrote!
Which is exactly why these conversations are often difficult. There is
a tension between pushing the as-if rule as far as possible within the
compiler on the one hand and allowing developers to write code that does
what is needed on the other. ;-)
There is a tension between what users expect from the compiler and what
actually is promised. The compiler is not pushing the as-if rule any
further than it always has: it just becomes better at optimising over
time. The as-if rule is and always has been absolute.
Heh! The fact that the compiler has become better at optimizing
over time is exactly what has been pushing the as-if rule further.
The underlying problem is that it is often impossible to write large
applications (such as the Linux kernel) completely within the confines of
the standard. Thus, most large applications, and especially concurrent
applications, are vulnerable to either the compiler becoming better
at optimizing or compilers pushing the as-if rule, however you want to
say it.
What is needed to get any progress is for user expectations to be
feasible and not contradict existing requirements. See "^^^" above.
Or additional requirements need to be accepted by the various compilation
powers that be. Failing to acknowledge valid new user expectations is
after all an excellent path to obsolescence.
Thanx, Paul
From: "Paul E. McKenney" <paulmck@kernel.org> Date: 2021-06-04 20:43:18
On Fri, Jun 04, 2021 at 09:17:56PM +0200, Peter Zijlstra wrote:
On Fri, Jun 04, 2021 at 12:24:07PM -0500, Segher Boessenkool wrote:
quoted
On Fri, Jun 04, 2021 at 10:10:29AM -0700, Linus Torvalds wrote:
quoted
The compiler *cannot* just say "oh, I'll do that 'volatile asm
barrier' whether the condition is true or not". That would be a
fundamental compiler bug.
Yes.
So we can all agree on something like this?
#define volatile_if(x) \
if (({ _Bool __x = (x); BUILD_BUG_ON(__builtin_constant_p(__x)); __x; }) && \
({ barrier(); 1; }))
As long as this prevents compilers from causing trouble with things like
conditional-move instructions, I am good. I don't know that this trouble
actually exists, but I never have been able to get official confirmation
one way or the other. :-/
Do we keep volatile_if() or do we like ctrl_dep_if() better?
I like ctrl_dep_if() because that is what it does, but I don't feel all
that strongly about it.
Thanx, Paul
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
From: Peter Zijlstra <peterz@infradead.org> Date: 2021-06-04 22:06:08
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().
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.
We do actually have uses what use a 'regular' store, and not a
WRITE_ONCE(). And I think for those the added barrier() might make a
difference.
At the very least the perf ring-buffer case uses memcpy().
On my part I'm deeply distrusting some of the C language committee
proposals I've seen regarding this stuff, and I'm maybe worrying too
much, but I'd rather not have to debug anything like this when they do
manage to make it go bad.
On top of that, I think having the construct is good for documenting
intent and possibly some of the concurrency analyzers can make use of
it.
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 03:14:08
On Fri, Jun 04, 2021 at 12:09:26PM -0700, Linus Torvalds wrote:
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.
This may be a minor point, but can that loophole be closed as follows?
define volatile_if(x) \
if ((({ _Bool __x = (x); BUILD_BUG_ON(__builtin_constant_p(__x)); __x; }) && \
({ barrier(); 1; })) || ({ barrier(); 0; }))
(It's now a little later at night than when I usually think about this
sort of thing, so my brain isn't firing on all its cylinders. Forgive
me if this is a dumb question.)
Alan
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
On Fri, Jun 4, 2021 at 8:14 PM Alan Stern [off-list ref] wrote:
quoted
then I could in theory see teh compiler doing that WRITE_ONCE() as
some kind of non-control dependency.
This may be a minor point, but can that loophole be closed as follows?
Note that it's actually entirely sufficient to have the barrier just
on one side.
I brought it up mainly as an oddity, and that it can result in the
compiler generating different code for the two different directions.
The reason that it is sufficient is that with the barrier in place (on
either side), the compiler really can't do much. It can't join either
of the sides, because it has to do that barrier on one side before any
common code.
In fact, even if the compiler decides to first do a conditional call
just around the barrier, and then do any common code (and then do
_another_ conditional branch), it still did that conditional branch
first, and the problem is solved. The CPU doesn't care, it will have
to resolve the branch before any subsequent stores are finalized.
Of course, if the compiler creates a conditional call just around the
barrier, and the barrier is empty (like we do now), and the compiler
leaves no mark of it in the result (like it does seem to do for empty
asm stataments), I could imagine some optimizing assembler (or linker)
screwing things up for us, and saying "a conditional branch to the
next instruction can just be removed).
At that point, we've lost again, and it's a toolchain issue. I don't
think that issue can currently happen, but it's an example of yet
another really subtle problem that *could* happen even if *we* do
everything right.
I also do not believe that any of our code that has this pattern would
have that situation where the compiler would generate a branch over
just the barrier. It's kind of similar to Paul's example in that
sense. When we use volatile_if(), the two sides are very very
different entirely regardless of the barrier, so in practice I think
this is all entirely moot.
Linus
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 Fri, Jun 04, 2021 at 01:40:42PM -0700, Paul E. McKenney wrote:
On Fri, Jun 04, 2021 at 02:53:01PM -0500, Segher Boessenkool wrote:
quoted
On Fri, Jun 04, 2021 at 11:55:26AM -0700, Paul E. McKenney wrote:
quoted
On Fri, Jun 04, 2021 at 11:40:47AM -0500, Segher Boessenkool wrote:
quoted
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
Once we have some experience with a language extension, the official
syntax for a standardized version of that extension can be bikeshedded.
Committees being what they are, what we use in the meantime will
definitely not be what is chosen, so there is not a whole lot of point
in worrying about the exact syntax in the meantime. ;-)
I am only saying that it is unlikely any compiler that is used in
production will want to experiment with "volatile if".
That unfortunately matches my experience over quite a few years. But if
something can be implemented using existing extensions, the conversations
often get easier. Especially given many more people are now familiar
with concurrency.
This was about the syntax "volatile if", not about the concept, let's
call that "volatile_if". And no, it was not me who brought this up :-)
quoted
quoted
Which is exactly why these conversations are often difficult. There is
a tension between pushing the as-if rule as far as possible within the
compiler on the one hand and allowing developers to write code that does
what is needed on the other. ;-)
There is a tension between what users expect from the compiler and what
actually is promised. The compiler is not pushing the as-if rule any
further than it always has: it just becomes better at optimising over
time. The as-if rule is and always has been absolute.
Heh! The fact that the compiler has become better at optimizing
over time is exactly what has been pushing the as-if rule further.
The underlying problem is that it is often impossible to write large
applications (such as the Linux kernel) completely within the confines of
the standard. Thus, most large applications, and especially concurrent
applications, are vulnerable to either the compiler becoming better
at optimizing or compilers pushing the as-if rule, however you want to
say it.
Oh definitely. But there is nothing the compiler can do about most
cases of undefined behaviour: it cannot detect it, and there is no way
it *can* be handled sanely. Take for example dereferencing a pointer
that does not point to an object.
Segher
On Sat, Jun 05, 2021 at 09:29:03PM -0400, Alan Stern 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.
And that is a simple fact, since the same assembler code (at the same
spot in the program) will do the same thing no matter how that ended up
there.
And the compiler always is allowed to duplicate, join, delete, you name
it, inline assembler code. The only thing that it cares about is
semantics of the code, just like for any other code.
Segher
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
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: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-06 13:45:37
On Sun, Jun 06, 2021 at 06:53:36AM -0500, Segher Boessenkool wrote:
On Sat, Jun 05, 2021 at 09:29:03PM -0400, Alan Stern 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.
And that is a simple fact, since the same assembler code (at the same
spot in the program) will do the same thing no matter how that ended up
there.
Sure. But the same assembler code at two different spots in the program
might not do the same thing. (Think of code that stores the current EIP
register's value into a variable.)
So while de-duplicating such code may be allowed, it will give rise to
observable results at execution time.
Alan
And the compiler always is allowed to duplicate, join, delete, you name
it, inline assembler code. The only thing that it cares about is
semantics of the code, just like for any other code.
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 4:56 AM Segher Boessenkool
[off-list ref] wrote:
And that is a simple fact, since the same assembler code (at the same
spot in the program) will do the same thing no matter how that ended up
there.
The thing is, that's exactl;y what gcc violates.
The example - you may not have been cc'd personally on that one - was
something like
if (READ_ONCE(a)) {
barrier();
WRITE_ONCE(b,1);
} else {
barrier();
WRITE_ONCE(b, 1);
}
and currently because gcc thinks "same exact code", it will actually
optimize this to (pseudo-asm):
LD A
"empty asm"
ST $1,B
which is very much NOT equivalent to
LD A
BEQ over
"empty asm"
ST $1,B
JMP join
over:
"empty asm"
ST $1,B
join:
and that's the whole point of the barriers.
It's not equivalent exactly because of memory ordering. In the first
case, there is no ordering on weak architectures. In the second case,
there is always an ordering, because of CPU consistency guarantees.
And no, gcc doesn't understand about memory ordering. But that's
exactly why we use inline asms.
And the compiler always is allowed to duplicate, join, delete, you name
it, inline assembler code. The only thing that it cares about is
semantics of the code, just like for any other code.
See, but it VIOLATES the semantics of the code.
You can't join those two empty asm's (and then remove the branch),
because the semantics of the code really aren't the same any more if
you do. Truly.
Linus
From: Alan Stern <stern@rowland.harvard.edu> Date: 2021-06-06 18:23:10
On Sun, Jun 06, 2021 at 11:04:49AM -0700, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 4:56 AM Segher Boessenkool
[off-list ref] wrote:
quoted
And that is a simple fact, since the same assembler code (at the same
spot in the program) will do the same thing no matter how that ended up
there.
The thing is, that's exactl;y what gcc violates.
The example - you may not have been cc'd personally on that one - was
something like
if (READ_ONCE(a)) {
barrier();
WRITE_ONCE(b,1);
} else {
barrier();
WRITE_ONCE(b, 1);
}
and currently because gcc thinks "same exact code", it will actually
optimize this to (pseudo-asm):
LD A
"empty asm"
ST $1,B
which is very much NOT equivalent to
LD A
BEQ over
"empty asm"
ST $1,B
JMP join
over:
"empty asm"
ST $1,B
join:
and that's the whole point of the barriers.
It's not equivalent exactly because of memory ordering. In the first
case, there is no ordering on weak architectures. In the second case,
there is always an ordering, because of CPU consistency guarantees.
And no, gcc doesn't understand about memory ordering. But that's
exactly why we use inline asms.
quoted
And the compiler always is allowed to duplicate, join, delete, you name
it, inline assembler code. The only thing that it cares about is
semantics of the code, just like for any other code.
See, but it VIOLATES the semantics of the code.
You can't join those two empty asm's (and then remove the branch),
because the semantics of the code really aren't the same any more if
you do. Truly.
To be fair, the same argument applies even without the asm code. The
compiler will translate
if (READ_ONCE(a))
WRITE_ONCE(b, 1);
else
WRITE_ONCE(b, 1);
to
LD A
ST $1,B
intstead of
LD A
BEQ over
ST $1,B
JMP join
over:
ST $1,B
join:
And these two are different for the same memory ordering reasons as
above.
Alan
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
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
On Sun, Jun 06, 2021 at 11:04:49AM -0700, Linus Torvalds wrote:
if (READ_ONCE(a)) {
barrier();
WRITE_ONCE(b,1);
} else {
barrier();
WRITE_ONCE(b, 1);
}
and currently because gcc thinks "same exact code", it will actually
optimize this to (pseudo-asm):
LD A
"empty asm"
ST $1,B
which is very much NOT equivalent to
LD A
BEQ over
"empty asm"
ST $1,B
JMP join
over:
"empty asm"
ST $1,B
join:
and that's the whole point of the barriers.
You didn't use a barrier with these semantics though. There is nothing
in that code that guarantees a branch.
See, but it VIOLATES the semantics of the code.
The code violates your expectations of the code.
You can't join those two empty asm's (and then remove the branch),
because the semantics of the code really aren't the same any more if
you do. Truly.
You truly should have written a branch in tthe asm if you truly wanted
a branch instruction.
Segher
On Sun, Jun 6, 2021 at 11:22 AM Alan Stern [off-list ref] wrote:
To be fair, the same argument applies even without the asm code. The
compiler will translate
Yes, yes.
But that is literally why the asm exists in the first place.
It's supposed to be the barrier that makes sure that doesn't happen.
So your point that "but this would happen without the asm" is missing
the whole point. This is exactly the thing that the asm is supposed to
avoid.
And it actually works fine when just one side has the barrier, because
then no merging can take place, because there is nothing to merge.
That's why my suggested fix for "volatile_if()" was this #define
#define barrier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())
because now code like
volatile_if (READ_ONCE(a))
WRITE_ONCE(b, 1);
else
WRITE_ONCE(b, 1);
would force that branch. And it's actually fine to merge the
"WRITE(b,1)", as loing as the branch exists, so the above can (and
does) compile to
LD A
BEQ over
"empty asm"
over:
ST $1,B
and the above is actually perfectly valid code and actually solves the
problem, even if it admittedly looks entirely insane.
With that crazy "conditional jump over nothing" the store to B is
ordered wrt the load from A on real machines.
And again: I do not believe we actually have this kind of code in the
kernel. I could imagine some CPU turning "conditional branch over
nothing" into a nop-op internally, and losing the ordering. And that's
ok, exactly because the above kind of code that *only* does the
WRITE_ONCE() and nothing else is crazy and stupid.
So don't get hung up on the "branch over nothing", that's just for
this insane unreal example.
But I *could* see us having something where both branches do end up
writing to "B", and it might even be the first thing both branches end
up doing. Not the *only* thing they do, but "B" might be a flag for "I
am actively working on this issue", and I could see a situation where
we care that the read of "A" (which might be what specifies *what* the
issue is) would need to be ordered with regards to that "I'm working
on it" flag.
IOW, another CPU might want to know *what* somebody is working on, and do
/* Is somebody working on this */
if (READ_ONCE(B)) {
smp_rmb();
READ_ONCE(A); <- this is what they are working on
and the ordering requirement in this all is that B has to be written
after A has been read.
So while the example code is insane and pointless (and you shouldn't
read *too* much into it), conceptually the notion of that pattern of
if (READ_ONCE(a)) {
WRITE_ONCE(b,1);
.. do something ..
} else {
WRITE_ONCE(b,1);
.. do something else ..
}
is not insane or entirely unrealistic - the WRITE_ONCE() might
basically be an ACK for "I have read the value of A and will act on
it".
Odd? Yes. Unusual? Yes. Do we do this now? No. But it does worry me
that we don't seem to have a good way to add that required barrier.
Adding it on one side is good, and works, but what if somebody then does
volatile_if (READ_ONCE(a))
WRITE_ONCE(b, 1);
else {
barrier();
WRITE_ONCE(b, 1);
}
and now we end up with it on both sides again, and then the second
barrier basically undoes the first one..
Linus
On Sun, Jun 6, 2021 at 11:43 AM Segher Boessenkool
[off-list ref] wrote:
You truly should have written a branch in tthe asm if you truly wanted
a branch instruction.
That's exactly what I don't want to do, and what the original patch by
PeterZ did.
Why?
Because then we need to write that stupid pointless branch for every
single architecture.
And to work well, it needs "asm goto", which is so recent that a lot
of compilers don't support it (thank God for clang dragging gcc
kicking and screaming to implement it at all - I'd asked for it over a
decade ago).
So you get bad code generation in a lot of cases, which entirely
obviates the _point_ of this all - which is that we can avoid an
expensive operation (a memory barrier) by just doing clever code
generation.
So if we can't get the clever code generation, it's all pretty much
moot, imnsho.
A working barrier "just fixes it".
I suspect the best we can do is to just work around the gcc badness
with that __COUNTER__ trick of mine. The lack of a reliable comment
character is the biggest issue with that trick.
Linus
On Sun, Jun 6, 2021 at 11:48 AM Linus Torvalds
[off-list ref] wrote:
And to work well, it needs "asm goto", which is so recent that a lot
of compilers don't support it (thank God for clang dragging gcc
kicking and screaming to implement it at all - I'd asked for it over a
decade ago).
Oh, actually, I'm wrong on this.
We don't need an output from the asm (the output ends up being in the
targets), so we can use the old-style asm goto that we've been relying
on for a long time.
So the main code generation problem is just (a) all the architectures
and (b) we'd have to use a fixed conditional against zero.
Linus
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:01:50
On Sun, Jun 06, 2021 at 06:36:51AM -0500, Segher Boessenkool wrote:
On Fri, Jun 04, 2021 at 01:40:42PM -0700, Paul E. McKenney wrote:
quoted
On Fri, Jun 04, 2021 at 02:53:01PM -0500, Segher Boessenkool wrote:
quoted
On Fri, Jun 04, 2021 at 11:55:26AM -0700, Paul E. McKenney wrote:
quoted
On Fri, Jun 04, 2021 at 11:40:47AM -0500, Segher Boessenkool wrote:
quoted
My point is that you ask compiler developers to paint themselves into a
corner if you ask them to change such fundamental C syntax.
Once we have some experience with a language extension, the official
syntax for a standardized version of that extension can be bikeshedded.
Committees being what they are, what we use in the meantime will
definitely not be what is chosen, so there is not a whole lot of point
in worrying about the exact syntax in the meantime. ;-)
I am only saying that it is unlikely any compiler that is used in
production will want to experiment with "volatile if".
That unfortunately matches my experience over quite a few years. But if
something can be implemented using existing extensions, the conversations
often get easier. Especially given many more people are now familiar
with concurrency.
This was about the syntax "volatile if", not about the concept, let's
call that "volatile_if". And no, it was not me who brought this up :-)
I agree that it is likely that the syntax "volatile if" would be at best
a very reluctantly acquired taste among most of the committee. But some
might point to the evolving semantics of "auto" as a counter-example,
to say nothing of the celebrated spaceship operator. Me, I am not
all that worried about the exact syntax.
quoted
quoted
quoted
Which is exactly why these conversations are often difficult. There is
a tension between pushing the as-if rule as far as possible within the
compiler on the one hand and allowing developers to write code that does
what is needed on the other. ;-)
There is a tension between what users expect from the compiler and what
actually is promised. The compiler is not pushing the as-if rule any
further than it always has: it just becomes better at optimising over
time. The as-if rule is and always has been absolute.
Heh! The fact that the compiler has become better at optimizing
over time is exactly what has been pushing the as-if rule further.
The underlying problem is that it is often impossible to write large
applications (such as the Linux kernel) completely within the confines of
the standard. Thus, most large applications, and especially concurrent
applications, are vulnerable to either the compiler becoming better
at optimizing or compilers pushing the as-if rule, however you want to
say it.
Oh definitely. But there is nothing the compiler can do about most
cases of undefined behaviour: it cannot detect it, and there is no way
it *can* be handled sanely. Take for example dereferencing a pointer
that does not point to an object.
Almost.
The compiler's use of provenance allows detection in some cases.
For a stupid example, please see https://godbolt.org/z/z9cWvqdhE.
Less stupidly, this sort of thing can be quite annoying to people trying
to use ABA-tolerant concurrent algorithms. See for example P1726R4
[1] (update in progress) and for an even more controversial proposal,
P2188R1 [2]. The Lifo Singly Linked Push algorithm described beginning
on page 14 of [1] is a simple example of an ABA-tolerant algorithm that
was already in use when I first programmed a computer. ;-)
Thanx, Paul
[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1726r4.pdf
[2] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2188r1.html
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
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 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
On Sun, Jun 06, 2021 at 11:48:32AM -0700, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 11:43 AM Segher Boessenkool
[off-list ref] wrote:
quoted
You truly should have written a branch in tthe asm if you truly wanted
a branch instruction.
That's exactly what I don't want to do, and what the original patch by
PeterZ did.
Yes, I know. But it is literally the *only* way to *always* get a
conditional branch: by writing one.
And to work well, it needs "asm goto", which is so recent that a lot
of compilers don't support it (thank God for clang dragging gcc
kicking and screaming to implement it at all - I'd asked for it over a
decade ago).
GCC has had it since 2009.
So you get bad code generation in a lot of cases, which entirely
obviates the _point_ of this all - which is that we can avoid an
expensive operation (a memory barrier) by just doing clever code
generation.
So if we can't get the clever code generation, it's all pretty much
moot, imnsho.
On Sun, Jun 6, 2021 at 12:56 PM Segher Boessenkool
[off-list ref] wrote:
Yes, I know. But it is literally the *only* way to *always* get a
conditional branch: by writing one.
The thing is, I don't actually believe you.
The barrier() thing can work - all we need to do is to simply make it
impossible for gcc to validly create anything but a conditional
branch.
If either side of the thing have an asm that cannot be combined, gcc
simply doesn't have any choice in the matter. There's no other valid
model than a conditional branch around it (of some sort - doing an
indirect branch that has a data dependency isn't wrong either, it just
wouldn't be something that a sane compiler would generate because it's
obviously much slower and more complicated).
We are very used to just making the compiler generate the code we
need. That is, fundamentally, what any use of inline asm is all about.
We want the compiler to generate all the common cases and all the
regular instructions.
The conditional branch itself - and the instructions leading up to it
- are exactly those "common regular instructions" that we'd want the
compiler to generate. That is in fact more true here than for most
inline asm, exactly because there are so many different possible
combinations of conditional branches (equal, not equal, less than,..)
and so many ways to generate the code that generates the condition.
So we are much better off letting the compiler do all that for us -
it's very much what the compiler is good at.
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
On Sun, Jun 06, 2021 at 01:11:53PM -0700, Linus Torvalds wrote:
On Sun, Jun 6, 2021 at 12:56 PM Segher Boessenkool
[off-list ref] wrote:
quoted
Yes, I know. But it is literally the *only* way to *always* get a
conditional branch: by writing one.
The thing is, I don't actually believe you.
Fortune favours the bold!
The barrier() thing can work - all we need to do is to simply make it
impossible for gcc to validly create anything but a conditional
branch.
And the only foolproof way of doing that is by writing a branch.
If either side of the thing have an asm that cannot be combined, gcc
simply doesn't have any choice in the matter. There's no other valid
model than a conditional branch around it (of some sort - doing an
indirect branch that has a data dependency isn't wrong either, it just
wouldn't be something that a sane compiler would generate because it's
obviously much slower and more complicated).
Or push something to the stack and return. Or rewrite the whole thing
as an FSM. Or or or.
(And yes, there are existing compilers that can do both of these things
on some code).
We are very used to just making the compiler generate the code we
need. That is, fundamentally, what any use of inline asm is all about.
We want the compiler to generate all the common cases and all the
regular instructions.
The conditional branch itself - and the instructions leading up to it
- are exactly those "common regular instructions" that we'd want the
compiler to generate. That is in fact more true here than for most
inline asm, exactly because there are so many different possible
combinations of conditional branches (equal, not equal, less than,..)
and so many ways to generate the code that generates the condition.
So we are much better off letting the compiler do all that for us -
it's very much what the compiler is good at.
Yes, exactly.
I am saying that if you depend on that some C code you write will result
in some particular machine code, without actually *forcing* the compiler
to output that exact machine code, then you will be disappointed. Maybe
not today, and maybe it will take years, if you are lucky.
(s/forcing/instructing/ of course, compilers have feelings too!)
Segher