Re: [RFC] tools/memory-model: Rule out OOTA

Am 1/9/2025 um 5:17 PM schrieb Alan Stern:
> On Wed, Jan 08, 2025 at 08:22:07PM +0100, Jonas Oberhauser wrote:
>>
>>
>> Am 1/8/2025 um 7:47 PM schrieb Alan Stern:
>>> On Wed, Jan 08, 2025 at 06:33:05PM +0100, Jonas Oberhauser wrote:
>>>>
>>>>
>>>> Am 1/7/2025 um 5:09 PM schrieb Alan Stern:
>>>>> Is this really valid?  In the example above, if there were no other
>>>>> references to a or b in the rest of the program, the compiler could
>>>>> eliminate them entirely.
>>>>
>>>> In the example above, this is not possible, because the address of a/b have
>>>> escaped the function and are not deallocated before synchronization happens.
>>>> Therefore the compiler must assume that a/b are accessed inside the compiler
>>>> barrier.
>>>
>>> I'm not quite sure what you mean by that, but if the compiler has access
>>> to the entire program and can do a global analysis then it can recognize
>>> cases where accesses that may seem to be live aren't really.
>>
>> Even for trivial enough cases where the compiler has access to all the
>> source, compiler barriers should be opaque to the compiler.
>>
>> Since it is opaque,
>>
>>    *a = 1;
>>    compiler_barrier();
>>
>> might as well be
>>
>>    *a = 1;
>>    *d = *a; // *d is in device memory
>>
>> and so in my opinion the compiler needs to ensure that the value of *a right
>> before the compiler barrier is 1.
>>
>> Of course, only if the address of *a could be possibly legally known to the
>> opaque code in the compiler barrier.
> 
> What do you mean by "opaque code in the compiler barrier"?  The
> compiler_barrier() instruction doesn't generate any code at all; it
> merely directs the compiler not to carry any knowledge about values
> stored in memory from one side of the barrier to the other.

What I mean by "opaque" is that the compiler does not analyze the code 
inside the compiler barrier, so it must treat it as a black box that 
could manipulate memory arbitrarily within the limitation that it can 
not guess the address of memory.

So for example, in

   int a = 1;
   barrier();
   a = 2;
   //...

the compiler does not know how the code inside barrier() accesses 
memory, including volatile memory.
But it knows that it can not access `a`, because the address of `a` has 
never escaped before the barrier().

So it can change this to:

   barrier();
   int a = 2;
   // ...

But if we let the address of `a` escape, for example with some external 
function foo(int*):

   int a;
   foo(&a);
   a = 1;
   barrier();
   a = 2;
   // ...

Then the compiler has to assume that the code of foo and barrier might 
be something like this:

foo(p) { SPECIAL_VARIABLE = p; }
barrier() { TURN_THE_BREAKS_ON = *SPECIAL_VARIABLE; }

and it must make sure that the value of `a` before barrier() is 1.

That is at least my understanding.

In fact, even if `a` is unused after a=2, the compiler can only 
eliminate `a` in the former case, but in the latter case, still needs to 
ensure that the value of `a` before barrier() is 1 (but it can eliminate 
a=2).


> 
> Note that it does _not_ necessarily prevent the compiler from carrying
> knowledge that a memory location is unused from one side of the barrier
> to the other.

Yes, or even merging/moving assignments to the memory location across a 
barrier(), as in the example above.


>>> However, I admit this objection doesn't really apply to Linux kernel
>>> programming.
>>>
>>>>>    (Whether the result could count as OOTA is
>>>>> open to question, but that's not the point.)  Is it not possible that a
>>>>> compiler might find other ways to defeat your intentions?
>>>>
>>>> The main point (which I already mentioned in the previous e-mail) is if the
>>>> object is deallocated without synchronization (or never escapes the function
>>>> in the first place).
>>>>
>>>> And indeed, any such case renders the added rule unsound. It is in a sense
>>>> unrelated to OOTA; cases where the load/store can be elided are never OOTA.
>>>
>>> That is a matter of definition.  In our paper, Paul and I described
>>> instances of OOTA in which all the accesses have been optimized away as
>>> "trivial".
>>
>> Yes, by OOTA I mean a rwdep;rfe cycle.
>>
>> In the absence of data races, such a cycle can't be optimized away because
>> it is created with volatile/compiler-barrier-protected accesses.
> 
> That wasn't true in the C++ context of the paper Paul and I worked on.
> Of course, C++ is not our current context here.

Yes, you are completely correct. In C++ (or pure C), where data races 
are prevented by compiler/language-builtins rather than with 
compiler-barriers/volatiles, all my assumptions break.

That is because the compiler absolutely knows that an atomic_store(&x) 
does not access any memory location other than x, so it can do a lot 
more "harmful" optimizations.

That's why I said such a language model should just exclude global OOTA 
by fiat.

I have to read your paper again (I think I read it a few months ago) to 
understand if the trivial OOTA would make even that vague axiom unsound
(my intuition says that if the OOTA is never observed by influencing the 
side-effect, then forbidding OOTA makes no difference to the set of 
"observable behaviors" of a C++ program even there is a trivial OOTA, 
and if the OOTA has visible side-effects, then it is acceptable for the 
compiler not to do the "optimization" that turns it into a trivial OOTA 
and choose some other optimization instead, so we can as well forbid the 
compiler from doing it).

> What I was trying to get at above is that compiler-barrier protection
> does not necessarily guarantee that non-volatile accesses can't be
> optimized away.  (However, it's probably safe for us to make such an
> assumption here.)

Yes, I agree.

>> It seems the ideal solution is to let Live be defined by the tools, which
>> should keep up with or exceed the analysis done by state-of-art compilers.
> 
> I don't think it works that way in practice.  :-)

Yeah... maybe not :(

Best wishes,
   jonas