Re: Control Dependencies vs C Compilers

* Peter Zijlstra:

On Tue, Oct 06, 2020 at 11:20:01PM +0200, Florian Weimer wrote:

quoted

* Peter Zijlstra:

quoted

Our Documentation/memory-barriers.txt has a Control Dependencies section
(which I shall not replicate here for brevity) which lists a number of
caveats. But in general the work-around we use is:

	x = READ_ONCE(*foo);
	if (x > 42)
		WRITE_ONCE(*bar, 1);

Where READ/WRITE_ONCE() cast the variable volatile. The volatile
qualifier dissuades the compiler from assuming it knows things and we
then hope it will indeed emit the branch like we'd expect.


Now, hoping the compiler generates correct code is clearly not ideal and
very dangerous indeed. Which is why my question to the compiler folks
assembled here is:

  Can we get a C language extention for this?

For what exactly?

A branch that cannot be optimized away and prohibits lifting stores
over. One possible suggestion would be allowing the volatile keyword as
a qualifier to if.

	x = *foo;
	volatile if (x > 42)
		*bar = 1;

This would tell the compiler that the condition is special in that it
must emit a conditional branch instruction and that it must not lift
stores (or sequence points) over it.

But it's not the if statement, but the expression in it, right?  So this
would not be a valid transformation:

 	x = *foo;
        bool flag = x > 42;
 	volatile if (flag)
 		*bar = 1;

And if we had this:

 	unsigned x = *foo;
 	volatile if (x >= 17 && x < 42)
 		*bar = 1;

Would it be valid to transform this into (assuming that I got the
arithmetic correct):

 	unsigned x = *foo;
 	volatile if ((x - 17) < 25)
 		*bar = 1;

Or would this destroy the magic because arithmetic happens on the value
before the comparison?

quoted

But not using READ_ONCE and WRITE_ONCE?

I'm OK with READ_ONCE(), but the WRITE_ONCE() doesn't help much, if
anything. The compiler is always allowed to lift stores, regardless of
the qualifiers used.

I would hope that with some level of formalization, it can be shown that
no additional synchronization is necessary beyond the load/conditional
sequence.

quoted

I think in GCC, they are called __atomic_load_n(foo, __ATOMIC_RELAXED)
and __atomic_store_n(foo, __ATOMIC_RELAXED).  GCC can't optimize relaxed
MO loads and stores because the C memory model is defective and does not
actually guarantee the absence of out-of-thin-air values (a property it
was supposed to have).

AFAIK people want to get that flaw in the C memory model fixed (which to
me seemd like a very good idea).

It's been a long time since people realized that this problem exists,
with several standard releases since then.

Thanks,
Florian
-- 
Red Hat GmbH, https://de.redhat.com/ , Registered seat: Grasbrunn,
Commercial register: Amtsgericht Muenchen, HRB 153243,
Managing Directors: Charles Cachera, Brian Klemm, Laurie Krebs, Michael O'Neill

On Wed, Oct 07, 2020 at 12:20:41PM +0200, Florian Weimer wrote:

* Peter Zijlstra:

quoted

A branch that cannot be optimized away and prohibits lifting stores
over. One possible suggestion would be allowing the volatile keyword as
a qualifier to if.

	x = *foo;
	volatile if (x > 42)
		*bar = 1;

This would tell the compiler that the condition is special in that it
must emit a conditional branch instruction and that it must not lift
stores (or sequence points) over it.

But it's not the if statement, but the expression in it, right? 

No, it *IS* the if statement, the magic is a conditional branch
instruction and the fact that CPUs are not allowed to speculate stores
(which would lead to instant OOTA).

So this would not be a valid transformation:

 	x = *foo;
        bool flag = x > 42;
 	volatile if (flag)
 		*bar = 1;

It would be valid, it still ensures the load of *foo happens before the
store of *bar.

And if we had this:

 	unsigned x = *foo;
 	volatile if (x >= 17 && x < 42)
 		*bar = 1;

Would it be valid to transform this into (assuming that I got the
arithmetic correct):

 	unsigned x = *foo;
 	volatile if ((x - 17) < 25)
 		*bar = 1;

Or would this destroy the magic because arithmetic happens on the value
before the comparison?

Nope, that'd still be good. The critical part is that the resolution of
the conditional branch depend on the load. All these transformations
preserve that.

So we use the data dependency between the load and the branch
instruction coupled with the inability to speculate stores, to generate
a LOAD to STORE ordering.

quoted

quoted

But not using READ_ONCE and WRITE_ONCE?

I'm OK with READ_ONCE(), but the WRITE_ONCE() doesn't help much, if
anything. The compiler is always allowed to lift stores, regardless of
the qualifiers used.

I would hope that with some level of formalization, it can be shown that
no additional synchronization is necessary beyond the load/conditional
sequence.

Agreed. Those are the critical part, the tricky bit is ensuring the
compiler doesn't lift stuff over the condition.

quoted

quoted

I think in GCC, they are called __atomic_load_n(foo, __ATOMIC_RELAXED)
and __atomic_store_n(foo, __ATOMIC_RELAXED).  GCC can't optimize relaxed
MO loads and stores because the C memory model is defective and does not
actually guarantee the absence of out-of-thin-air values (a property it
was supposed to have).

AFAIK people want to get that flaw in the C memory model fixed (which to
me seemd like a very good idea).

It's been a long time since people realized that this problem exists,
with several standard releases since then.

I've been given to believe it is a hard problem. Personally I hold the
opinion that prohibiting store speculation (of all kinds) is both
necesary and sufficient to avoid OOTA. But I have 0 proof for that.

On Wed, Oct 07, 2020 at 01:50:54PM +0200, Peter Zijlstra wrote:

On Wed, Oct 07, 2020 at 12:20:41PM +0200, Florian Weimer wrote:

quoted

* Peter Zijlstra:

[ . . . ]

quoted

quoted

quoted

I think in GCC, they are called __atomic_load_n(foo, __ATOMIC_RELAXED)
and __atomic_store_n(foo, __ATOMIC_RELAXED).  GCC can't optimize relaxed
MO loads and stores because the C memory model is defective and does not
actually guarantee the absence of out-of-thin-air values (a property it
was supposed to have).

AFAIK people want to get that flaw in the C memory model fixed (which to
me seemd like a very good idea).

It's been a long time since people realized that this problem exists,
with several standard releases since then.

I've been given to believe it is a hard problem. Personally I hold the
opinion that prohibiting store speculation (of all kinds) is both
necesary and sufficient to avoid OOTA. But I have 0 proof for that.

There are proofs for some definitions of store speculation, for example,
as proposed by Demsky and Boehm [1] and as prototyped by Demsky's student,
Peizhao Ou [2].  But these require marking all accesses and end up being
optimized variants of acquire load and release store.  One optimization
is that if you have a bunch of loads followed by a bunch of stores,
the compiler can emit a single memory-barrier instruction between the
last load and the first store.

I am not a fan of this approach.

Challenges include:

o	Unmarked accesses.  Compilers are quite aggressive about
	moving normal code.

o	Separately compiled code.  For example, does the compiler have
	unfortunatel optimization opportunities when "volatile if" 
	appears in one translation unit and the dependent stores in
	some other translation unit?

o	LTO, as has already been mentioned in this thread.

Probably other issues as well, but a starting point.

							Thanx, Paul

[1]	https://dl.acm.org/doi/10.1145/2618128.2618134
	"Outlawing ghosts: avoiding out-of-thin-air results"
	Hans-J. Boehm and Brian Demsky.

[2]	https://escholarship.org/uc/item/2vm546k1
	"An Initial Study of Two Approaches to Eliminating Out-of-Thin-Air
	Results" Peizhao Ou.

On Wed, Oct 07, 2020 at 10:11:07AM -0700, Paul E. McKenney wrote:

Challenges include:

o	Unmarked accesses.  Compilers are quite aggressive about
	moving normal code.

Which is why this thread exists :-) We wants to dis-allow lifting the
stores over our volatile-if.

o	Separately compiled code.  For example, does the compiler have
	unfortunatel optimization opportunities when "volatile if" 
	appears in one translation unit and the dependent stores in
	some other translation unit?

It can hardly lift anything outside a TU (barring the next point). So I
don't see how it can go wrong here. This is in fact the case with the
perf ringbuffer. The ctrl-dep lives in a different TU from the
stores.

o	LTO, as has already been mentioned in this thread.

So I would probably advocate the volatile-if to be a full sync point,
and LTO would have to preserve that.

On Wed, Oct 07, 2020 at 11:07:17PM +0200, Peter Zijlstra wrote:

On Wed, Oct 07, 2020 at 10:11:07AM -0700, Paul E. McKenney wrote:

quoted

Challenges include:

o	Unmarked accesses.  Compilers are quite aggressive about
	moving normal code.

Which is why this thread exists :-) We wants to dis-allow lifting the
stores over our volatile-if.

Of course.  But you should expect this point to be a continual source
of shock and surprise to compiler folks.  ;-)

quoted

o	Separately compiled code.  For example, does the compiler have
	unfortunatel optimization opportunities when "volatile if" 
	appears in one translation unit and the dependent stores in
	some other translation unit?

It can hardly lift anything outside a TU (barring the next point). So I
don't see how it can go wrong here. This is in fact the case with the
perf ringbuffer. The ctrl-dep lives in a different TU from the
stores.

I don't see how it could either, but I have been surprised before.

quoted

o	LTO, as has already been mentioned in this thread.

So I would probably advocate the volatile-if to be a full sync point,
and LTO would have to preserve that.

Completely agreed!  And probably not the only place that LTO needs
to be reined in a bit.

							Thanx, Paul