[1/2] compiler.h: Introduce ptr_eq() to preserve address dependency

Commit Message

Mathieu Desnoyers Sept. 28, 2024, 1:51 p.m. UTC

Compiler CSE and SSA GVN optimizations can cause the address dependency
of addresses returned by rcu_dereference to be lost when comparing those
pointers with either constants or previously loaded pointers.

Introduce ptr_eq() to compare two addresses while preserving the address
dependencies for later use of the address. It should be used when
comparing an address returned by rcu_dereference().

This is needed to prevent the compiler CSE and SSA GVN optimizations
from replacing the registers holding @a or @b based on their
equality, which does not preserve address dependencies and allows the
following misordering speculations:

- If @b is a constant, the compiler can issue the loads which depend
  on @a before loading @a.
- If @b is a register populated by a prior load, weakly-ordered
  CPUs can speculate loads which depend on @a before loading @a.

The same logic applies with @a and @b swapped.

The compiler barrier() is ineffective at fixing this issue.
It does not prevent the compiler CSE from losing the address dependency:

int fct_2_volatile_barriers(void)
{
    int *a, *b;

    do {
        a = READ_ONCE(p);
        asm volatile ("" : : : "memory");
        b = READ_ONCE(p);
    } while (a != b);
    asm volatile ("" : : : "memory");  <----- barrier()
    return *b;
}

With gcc 14.2 (arm64):

fct_2_volatile_barriers:
        adrp    x0, .LANCHOR0
        add     x0, x0, :lo12:.LANCHOR0
.L2:
        ldr     x1, [x0]    <------ x1 populated by first load.
        ldr     x2, [x0]
        cmp     x1, x2
        bne     .L2
        ldr     w0, [x1]    <------ x1 is used for access which should depend on b.
        ret

On weakly-ordered architectures, this lets CPU speculation use the
result from the first load to speculate "ldr w0, [x1]" before
"ldr x2, [x0]".
Based on the RCU documentation, the control dependency does not prevent
the CPU from speculating loads.

Suggested-by: Linus Torvalds <[e-mail]>
Suggested-by: Boqun Feng <[e-mail]>
Signed-off-by: Mathieu Desnoyers <[e-mail]>
Reviewed-by: Boqun Feng <[e-mail]>
Acked-by: "Paul E. McKenney" <[e-mail]>
Cc: Greg Kroah-Hartman <[e-mail]>
Cc: Sebastian Andrzej Siewior <[e-mail]>
Cc: "Paul E. McKenney" <[e-mail]>
Cc: Will Deacon <[e-mail]>
Cc: Peter Zijlstra <[e-mail]>
Cc: Boqun Feng <[e-mail]>
Cc: Alan Stern <[e-mail]>
Cc: John Stultz <[e-mail]>
Cc: Neeraj Upadhyay <[e-mail]>
Cc: Linus Torvalds <[e-mail]>
Cc: Boqun Feng <[e-mail]>
Cc: Frederic Weisbecker <[e-mail]>
Cc: Joel Fernandes <[e-mail]>
Cc: Josh Triplett <[e-mail]>
Cc: Uladzislau Rezki <[e-mail]>
Cc: Steven Rostedt <[e-mail]>
Cc: Lai Jiangshan <[e-mail]>
Cc: Zqiang <[e-mail]>
Cc: Ingo Molnar <[e-mail]>
Cc: Waiman Long <[e-mail]>
Cc: Mark Rutland <[e-mail]>
Cc: Thomas Gleixner <[e-mail]>
Cc: Vlastimil Babka <[e-mail]>
Cc: [e-mail]
Cc: Mateusz Guzik <[e-mail]>
Cc: Gary Guo <[e-mail]>
Cc: Jonas Oberhauser <[e-mail]>
Cc: [e-mail]
Cc: [e-mail]
Cc: [e-mail]
---
 include/linux/compiler.h | 62 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

Comments

Alan Stern Sept. 28, 2024, 2:49 p.m. UTC | #1

On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
> Compiler CSE and SSA GVN optimizations can cause the address dependency
> of addresses returned by rcu_dereference to be lost when comparing those
> pointers with either constants or previously loaded pointers.
> 
> Introduce ptr_eq() to compare two addresses while preserving the address
> dependencies for later use of the address. It should be used when
> comparing an address returned by rcu_dereference().
> 
> This is needed to prevent the compiler CSE and SSA GVN optimizations
> from replacing the registers holding @a or @b based on their

"Replacing" isn't the right word.  What the compiler does is use one 
rather than the other.  Furthermore, the compiler can play these games 
even with values that aren't in registers.

You should just say: "... from using @a (or @b) in places where the 
source refers to @b (or @a) (based on the fact that after the 
comparison, the two are known to be equal), which does not ..."

> equality, which does not preserve address dependencies and allows the
> following misordering speculations:
> 
> - If @b is a constant, the compiler can issue the loads which depend
>   on @a before loading @a.
> - If @b is a register populated by a prior load, weakly-ordered
>   CPUs can speculate loads which depend on @a before loading @a.

It shouldn't matter whether @a and @b are constants, registers, or 
anything else.  All that matters is that the compiler uses the wrong 
one, which allows weakly ordered CPUs to speculate loads you wouldn't 
expect it to, based on the source code alone.

> The same logic applies with @a and @b swapped.
> 
> The compiler barrier() is ineffective at fixing this issue.
> It does not prevent the compiler CSE from losing the address dependency:
> 
> int fct_2_volatile_barriers(void)
> {
>     int *a, *b;
> 
>     do {
>         a = READ_ONCE(p);
>         asm volatile ("" : : : "memory");
>         b = READ_ONCE(p);
>     } while (a != b);
>     asm volatile ("" : : : "memory");  <----- barrier()
>     return *b;
> }
> 
> With gcc 14.2 (arm64):
> 
> fct_2_volatile_barriers:
>         adrp    x0, .LANCHOR0
>         add     x0, x0, :lo12:.LANCHOR0
> .L2:
>         ldr     x1, [x0]    <------ x1 populated by first load.
>         ldr     x2, [x0]
>         cmp     x1, x2
>         bne     .L2
>         ldr     w0, [x1]    <------ x1 is used for access which should depend on b.
>         ret
> 
> On weakly-ordered architectures, this lets CPU speculation use the
> result from the first load to speculate "ldr w0, [x1]" before
> "ldr x2, [x0]".
> Based on the RCU documentation, the control dependency does not prevent
> the CPU from speculating loads.
> 
> Suggested-by: Linus Torvalds <[e-mail]>
> Suggested-by: Boqun Feng <[e-mail]>
> Signed-off-by: Mathieu Desnoyers <[e-mail]>
> Reviewed-by: Boqun Feng <[e-mail]>
> Acked-by: "Paul E. McKenney" <[e-mail]>
> Cc: Greg Kroah-Hartman <[e-mail]>
> Cc: Sebastian Andrzej Siewior <[e-mail]>
> Cc: "Paul E. McKenney" <[e-mail]>
> Cc: Will Deacon <[e-mail]>
> Cc: Peter Zijlstra <[e-mail]>
> Cc: Boqun Feng <[e-mail]>
> Cc: Alan Stern <[e-mail]>
> Cc: John Stultz <[e-mail]>
> Cc: Neeraj Upadhyay <[e-mail]>
> Cc: Linus Torvalds <[e-mail]>
> Cc: Boqun Feng <[e-mail]>
> Cc: Frederic Weisbecker <[e-mail]>
> Cc: Joel Fernandes <[e-mail]>
> Cc: Josh Triplett <[e-mail]>
> Cc: Uladzislau Rezki <[e-mail]>
> Cc: Steven Rostedt <[e-mail]>
> Cc: Lai Jiangshan <[e-mail]>
> Cc: Zqiang <[e-mail]>
> Cc: Ingo Molnar <[e-mail]>
> Cc: Waiman Long <[e-mail]>
> Cc: Mark Rutland <[e-mail]>
> Cc: Thomas Gleixner <[e-mail]>
> Cc: Vlastimil Babka <[e-mail]>
> Cc: [e-mail]
> Cc: Mateusz Guzik <[e-mail]>
> Cc: Gary Guo <[e-mail]>
> Cc: Jonas Oberhauser <[e-mail]>
> Cc: [e-mail]
> Cc: [e-mail]
> Cc: [e-mail]
> ---
>  include/linux/compiler.h | 62 ++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 62 insertions(+)
> 
> diff --git a/include/linux/compiler.h b/include/linux/compiler.h
> index 2df665fa2964..f26705c267e8 100644
> --- a/include/linux/compiler.h
> +++ b/include/linux/compiler.h
> @@ -186,6 +186,68 @@ void ftrace_likely_update(struct ftrace_likely_data *f, int val,
>  	__asm__ ("" : "=r" (var) : "0" (var))
>  #endif
>  
> +/*
> + * Compare two addresses while preserving the address dependencies for
> + * later use of the address. It should be used when comparing an address
> + * returned by rcu_dereference().
> + *
> + * This is needed to prevent the compiler CSE and SSA GVN optimizations
> + * from replacing the registers holding @a or @b based on their
> + * equality, which does not preserve address dependencies and allows the
> + * following misordering speculations:
> + *
> + * - If @b is a constant, the compiler can issue the loads which depend
> + *   on @a before loading @a.
> + * - If @b is a register populated by a prior load, weakly-ordered
> + *   CPUs can speculate loads which depend on @a before loading @a.
> + *
> + * The same logic applies with @a and @b swapped.

This could be more concise, and it should be more general (along the 
same lines as the description above).

> + *
> + * Return value: true if pointers are equal, false otherwise.
> + *
> + * The compiler barrier() is ineffective at fixing this issue. It does
> + * not prevent the compiler CSE from losing the address dependency:
> + *
> + * int fct_2_volatile_barriers(void)
> + * {
> + *     int *a, *b;
> + *
> + *     do {
> + *         a = READ_ONCE(p);
> + *         asm volatile ("" : : : "memory");
> + *         b = READ_ONCE(p);
> + *     } while (a != b);
> + *     asm volatile ("" : : : "memory");  <-- barrier()
> + *     return *b;
> + * }
> + *
> + * With gcc 14.2 (arm64):
> + *
> + * fct_2_volatile_barriers:
> + *         adrp    x0, .LANCHOR0
> + *         add     x0, x0, :lo12:.LANCHOR0
> + * .L2:
> + *         ldr     x1, [x0]  <-- x1 populated by first load.
> + *         ldr     x2, [x0]
> + *         cmp     x1, x2
> + *         bne     .L2
> + *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
> + *         ret
> + *
> + * On weakly-ordered architectures, this lets CPU speculation use the
> + * result from the first load to speculate "ldr w0, [x1]" before
> + * "ldr x2, [x0]".
> + * Based on the RCU documentation, the control dependency does not
> + * prevent the CPU from speculating loads.

IMO, this lengthy explanation is not needed in the source code.  Just 
refer interested readers to the commit description.  You're repeating 
the same text verbatim, after all.

(Or if you firmly believe that this explanation _does_ belong in the 
code, then omit it from the commit description.  There's no need to say 
everything twice.)

Alan Stern

> + */
> +static __always_inline
> +int ptr_eq(const volatile void *a, const volatile void *b)
> +{
> +	OPTIMIZER_HIDE_VAR(a);
> +	OPTIMIZER_HIDE_VAR(b);
> +	return a == b;
> +}
> +
>  #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
>  
>  /**
> -- 
> 2.39.2
>

Mathieu Desnoyers Sept. 28, 2024, 3:30 p.m. UTC | #2

On 2024-09-28 16:49, Alan Stern wrote:
> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
[...]
>> +/*
>> + * Compare two addresses while preserving the address dependencies for
>> + * later use of the address. It should be used when comparing an address
>> + * returned by rcu_dereference().
>> + *
>> + * This is needed to prevent the compiler CSE and SSA GVN optimizations
>> + * from replacing the registers holding @a or @b based on their
>> + * equality, which does not preserve address dependencies and allows the
>> + * following misordering speculations:
>> + *
>> + * - If @b is a constant, the compiler can issue the loads which depend
>> + *   on @a before loading @a.
>> + * - If @b is a register populated by a prior load, weakly-ordered
>> + *   CPUs can speculate loads which depend on @a before loading @a.
>> + *
>> + * The same logic applies with @a and @b swapped.
[...]
>> + *
>> + * Return value: true if pointers are equal, false otherwise.
>> + *
>> + * The compiler barrier() is ineffective at fixing this issue. It does
>> + * not prevent the compiler CSE from losing the address dependency:
>> + *
>> + * int fct_2_volatile_barriers(void)
>> + * {
>> + *     int *a, *b;
>> + *
>> + *     do {
>> + *         a = READ_ONCE(p);
>> + *         asm volatile ("" : : : "memory");
>> + *         b = READ_ONCE(p);
>> + *     } while (a != b);
>> + *     asm volatile ("" : : : "memory");  <-- barrier()
>> + *     return *b;
>> + * }
>> + *
>> + * With gcc 14.2 (arm64):
>> + *
>> + * fct_2_volatile_barriers:
>> + *         adrp    x0, .LANCHOR0
>> + *         add     x0, x0, :lo12:.LANCHOR0
>> + * .L2:
>> + *         ldr     x1, [x0]  <-- x1 populated by first load.
>> + *         ldr     x2, [x0]
>> + *         cmp     x1, x2
>> + *         bne     .L2
>> + *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
>> + *         ret
>> + *
>> + * On weakly-ordered architectures, this lets CPU speculation use the
>> + * result from the first load to speculate "ldr w0, [x1]" before
>> + * "ldr x2, [x0]".
>> + * Based on the RCU documentation, the control dependency does not
>> + * prevent the CPU from speculating loads.
> 
> IMO, this lengthy explanation is not needed in the source code.  Just
> refer interested readers to the commit description.  You're repeating
> the same text verbatim, after all.
> 
> (Or if you firmly believe that this explanation _does_ belong in the
> code, then omit it from the commit description.  There's no need to say
> everything twice.)
> 

Linus asked for this code/asm example to be in the comment:

   https://lore.kernel.org/lkml/CAHk-=wgBgh5U+dyNaN=[e-mail]/

I agree that it may be a bit verbose for the comment.

Linus, do you want the explanation wrt compiler barriers not being
enough (with C/asm example) in the comment above ptr_eq() or in
the commit message ?

Thanks,

Mathieu

Mathieu Desnoyers Sept. 28, 2024, 3:32 p.m. UTC | #3

On 2024-09-28 16:49, Alan Stern wrote:
> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>> Compiler CSE and SSA GVN optimizations can cause the address dependency
>> of addresses returned by rcu_dereference to be lost when comparing those
>> pointers with either constants or previously loaded pointers.
>>
>> Introduce ptr_eq() to compare two addresses while preserving the address
>> dependencies for later use of the address. It should be used when
>> comparing an address returned by rcu_dereference().
>>
>> This is needed to prevent the compiler CSE and SSA GVN optimizations
>> from replacing the registers holding @a or @b based on their
> 
> "Replacing" isn't the right word.  What the compiler does is use one
> rather than the other.  Furthermore, the compiler can play these games
> even with values that aren't in registers.
> 
> You should just say: "... from using @a (or @b) in places where the
> source refers to @b (or @a) (based on the fact that after the
> comparison, the two are known to be equal), which does not ..."

OK.

> 
>> equality, which does not preserve address dependencies and allows the
>> following misordering speculations:
>>
>> - If @b is a constant, the compiler can issue the loads which depend
>>    on @a before loading @a.
>> - If @b is a register populated by a prior load, weakly-ordered
>>    CPUs can speculate loads which depend on @a before loading @a.
> 
> It shouldn't matter whether @a and @b are constants, registers, or
> anything else.  All that matters is that the compiler uses the wrong
> one, which allows weakly ordered CPUs to speculate loads you wouldn't
> expect it to, based on the source code alone.

I only partially agree here.

On weakly-ordered architectures, indeed we don't care whether the
issue is caused by the compiler reordering the code (constant)
or the CPU speculating the load (registers).

However, on strongly-ordered architectures, AFAIU, only the constant
case is problematic (compiler reordering the dependent load), because
CPU speculating the loads across the control dependency is not an
issue.

So am I tempted to keep examples that clearly state whether
the issue is caused by compiler reordering instructions, or by
CPU speculation.

> 
>> The same logic applies with @a and @b swapped.
>>
>> The compiler barrier() is ineffective at fixing this issue.
>> It does not prevent the compiler CSE from losing the address dependency:
>>
>> int fct_2_volatile_barriers(void)
>> {
>>      int *a, *b;
>>
>>      do {
>>          a = READ_ONCE(p);
>>          asm volatile ("" : : : "memory");
>>          b = READ_ONCE(p);
>>      } while (a != b);
>>      asm volatile ("" : : : "memory");  <----- barrier()
>>      return *b;
>> }
>>
>> With gcc 14.2 (arm64):
>>
>> fct_2_volatile_barriers:
>>          adrp    x0, .LANCHOR0
>>          add     x0, x0, :lo12:.LANCHOR0
>> .L2:
>>          ldr     x1, [x0]    <------ x1 populated by first load.
>>          ldr     x2, [x0]
>>          cmp     x1, x2
>>          bne     .L2
>>          ldr     w0, [x1]    <------ x1 is used for access which should depend on b.
>>          ret
>>
>> On weakly-ordered architectures, this lets CPU speculation use the
>> result from the first load to speculate "ldr w0, [x1]" before
>> "ldr x2, [x0]".
>> Based on the RCU documentation, the control dependency does not prevent
>> the CPU from speculating loads.
>>
[...]
>> diff --git a/include/linux/compiler.h b/include/linux/compiler.h
>> index 2df665fa2964..f26705c267e8 100644
>> --- a/include/linux/compiler.h
>> +++ b/include/linux/compiler.h
>> @@ -186,6 +186,68 @@ void ftrace_likely_update(struct ftrace_likely_data *f, int val,
>>   	__asm__ ("" : "=r" (var) : "0" (var))
>>   #endif
>>   
>> +/*
>> + * Compare two addresses while preserving the address dependencies for
>> + * later use of the address. It should be used when comparing an address
>> + * returned by rcu_dereference().
>> + *
>> + * This is needed to prevent the compiler CSE and SSA GVN optimizations
>> + * from replacing the registers holding @a or @b based on their
>> + * equality, which does not preserve address dependencies and allows the

Replacing with:

  * This is needed to prevent the compiler CSE and SSA GVN optimizations
  * from using @a (or @b) in places where the source refers to @b (or @a)
  * based on the fact that after the comparison, the two are known to be
  * equal, which does not preserve address dependencies and allows the
  * following misordering speculations:

>> + * following misordering speculations:
>> + *
>> + * - If @b is a constant, the compiler can issue the loads which depend
>> + *   on @a before loading @a.
>> + * - If @b is a register populated by a prior load, weakly-ordered
>> + *   CPUs can speculate loads which depend on @a before loading @a.
>> + *
>> + * The same logic applies with @a and @b swapped.
> 
> This could be more concise, and it should be more general (along the
> same lines as the description above).

As per my earlier comment, I would prefer to keep the examples specific
rather than general so it is clear which scenarios are problematic on
weakly vs strongly ordered architectures.

[...]

Thanks,

Mathieu

Alan Stern Sept. 28, 2024, 3:49 p.m. UTC | #4

On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
> On 2024-09-28 16:49, Alan Stern wrote:
> > On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
> > > equality, which does not preserve address dependencies and allows the
> > > following misordering speculations:
> > > 
> > > - If @b is a constant, the compiler can issue the loads which depend
> > >    on @a before loading @a.
> > > - If @b is a register populated by a prior load, weakly-ordered
> > >    CPUs can speculate loads which depend on @a before loading @a.
> > 
> > It shouldn't matter whether @a and @b are constants, registers, or
> > anything else.  All that matters is that the compiler uses the wrong
> > one, which allows weakly ordered CPUs to speculate loads you wouldn't
> > expect it to, based on the source code alone.
> 
> I only partially agree here.
> 
> On weakly-ordered architectures, indeed we don't care whether the
> issue is caused by the compiler reordering the code (constant)
> or the CPU speculating the load (registers).
> 
> However, on strongly-ordered architectures, AFAIU, only the constant
> case is problematic (compiler reordering the dependent load), because

I thought you were trying to prevent the compiler from using one pointer 
instead of the other, not trying to prevent it from reordering anything. 
Isn't this the point the documentation wants to get across when it says 
that comparing pointers can be dangerous?

> CPU speculating the loads across the control dependency is not an
> issue.
> 
> So am I tempted to keep examples that clearly state whether
> the issue is caused by compiler reordering instructions, or by
> CPU speculation.

Isn't it true that on strongly ordered CPUs, a compiler barrier is 
sufficient to prevent the rcu_dereference() problem?  So the whole idea 
behind ptr_eq() is that it prevents the problem on all CPUs.

You can make your examples as specific as you like, but the fact remains 
that ptr_eq() is meant to prevent situations where both:

	The compiler uses the wrong pointer for a load, and

	The CPU performs the load earlier than you want.

If either one of those doesn't hold then the problem won't arise.

Alan Stern

Mathieu Desnoyers Sept. 28, 2024, 3:55 p.m. UTC | #5

On 2024-09-28 17:49, Alan Stern wrote:
> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>> On 2024-09-28 16:49, Alan Stern wrote:
>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>> equality, which does not preserve address dependencies and allows the
>>>> following misordering speculations:
>>>>
>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>     on @a before loading @a.
>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>     CPUs can speculate loads which depend on @a before loading @a.
>>>
>>> It shouldn't matter whether @a and @b are constants, registers, or
>>> anything else.  All that matters is that the compiler uses the wrong
>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>> expect it to, based on the source code alone.
>>
>> I only partially agree here.
>>
>> On weakly-ordered architectures, indeed we don't care whether the
>> issue is caused by the compiler reordering the code (constant)
>> or the CPU speculating the load (registers).
>>
>> However, on strongly-ordered architectures, AFAIU, only the constant
>> case is problematic (compiler reordering the dependent load), because
> 
> I thought you were trying to prevent the compiler from using one pointer
> instead of the other, not trying to prevent it from reordering anything.
> Isn't this the point the documentation wants to get across when it says
> that comparing pointers can be dangerous?

The motivation for introducing ptr_eq() is indeed because the
compiler barrier is not sufficient to prevent the compiler from
using one pointer instead of the other.

But it turns out that ptr_eq() is also a good tool to prevent the
compiler from reordering loads in case where the comparison is
done against a constant.

> 
>> CPU speculating the loads across the control dependency is not an
>> issue.
>>
>> So am I tempted to keep examples that clearly state whether
>> the issue is caused by compiler reordering instructions, or by
>> CPU speculation.
> 
> Isn't it true that on strongly ordered CPUs, a compiler barrier is
> sufficient to prevent the rcu_dereference() problem?  So the whole idea
> behind ptr_eq() is that it prevents the problem on all CPUs.

Correct. But given that we have ptr_eq(), it's good to show how it
equally prevents the compiler from reordering address-dependent loads
(comparison with constant) *and* prevents the compiler from using
one pointer rather than the other (comparison between two non-constant
pointers) which affects speculation on weakly-ordered CPUs.

> You can make your examples as specific as you like, but the fact remains
> that ptr_eq() is meant to prevent situations where both:
> 
> 	The compiler uses the wrong pointer for a load, and
> 
> 	The CPU performs the load earlier than you want.
> 
> If either one of those doesn't hold then the problem won't arise.

Correct.

Thanks,

Mathieu

Alan Stern Sept. 28, 2024, 9:15 p.m. UTC | #6

On Sat, Sep 28, 2024 at 11:55:22AM -0400, Mathieu Desnoyers wrote:
> On 2024-09-28 17:49, Alan Stern wrote:
> > On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
> > > On 2024-09-28 16:49, Alan Stern wrote:
> > > > On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
> > > > > equality, which does not preserve address dependencies and allows the
> > > > > following misordering speculations:
> > > > > 
> > > > > - If @b is a constant, the compiler can issue the loads which depend
> > > > >     on @a before loading @a.
> > > > > - If @b is a register populated by a prior load, weakly-ordered
> > > > >     CPUs can speculate loads which depend on @a before loading @a.
> > > > 
> > > > It shouldn't matter whether @a and @b are constants, registers, or
> > > > anything else.  All that matters is that the compiler uses the wrong
> > > > one, which allows weakly ordered CPUs to speculate loads you wouldn't
> > > > expect it to, based on the source code alone.
> > > 
> > > I only partially agree here.
> > > 
> > > On weakly-ordered architectures, indeed we don't care whether the
> > > issue is caused by the compiler reordering the code (constant)
> > > or the CPU speculating the load (registers).
> > > 
> > > However, on strongly-ordered architectures, AFAIU, only the constant
> > > case is problematic (compiler reordering the dependent load), because
> > 
> > I thought you were trying to prevent the compiler from using one pointer
> > instead of the other, not trying to prevent it from reordering anything.
> > Isn't this the point the documentation wants to get across when it says
> > that comparing pointers can be dangerous?
> 
> The motivation for introducing ptr_eq() is indeed because the
> compiler barrier is not sufficient to prevent the compiler from
> using one pointer instead of the other.
> 
> But it turns out that ptr_eq() is also a good tool to prevent the
> compiler from reordering loads in case where the comparison is
> done against a constant.

Isn't that the same thing?  A constant pointer like &x is still a  
pointer.  What you want to do is compare p with &x without allowing the 
compiler to then replace *p with *&x (or just x).

> > Isn't it true that on strongly ordered CPUs, a compiler barrier is
> > sufficient to prevent the rcu_dereference() problem?  So the whole idea
> > behind ptr_eq() is that it prevents the problem on all CPUs.
> 
> Correct. But given that we have ptr_eq(), it's good to show how it
> equally prevents the compiler from reordering address-dependent loads
> (comparison with constant) *and* prevents the compiler from using
> one pointer rather than the other (comparison between two non-constant
> pointers) which affects speculation on weakly-ordered CPUs.

I don't see how these two things differ from each other.  In the 
comparison-with-a-constant case, how is the compiler reordering 
anything?  Isn't it just using the constant address rather than the 
loaded pointer and thereby breaking the address dependency?

Alan stern

Alan Huang Sept. 28, 2024, 10:26 p.m. UTC | #7

2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
> 
> On 2024-09-28 17:49, Alan Stern wrote:
>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>> equality, which does not preserve address dependencies and allows the
>>>>> following misordering speculations:
>>>>> 
>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>    on @a before loading @a.
>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>    CPUs can speculate loads which depend on @a before loading @a.
>>>> 
>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>> anything else.  All that matters is that the compiler uses the wrong
>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>> expect it to, based on the source code alone.
>>> 
>>> I only partially agree here.
>>> 
>>> On weakly-ordered architectures, indeed we don't care whether the
>>> issue is caused by the compiler reordering the code (constant)
>>> or the CPU speculating the load (registers).
>>> 
>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>> case is problematic (compiler reordering the dependent load), because
>> I thought you were trying to prevent the compiler from using one pointer
>> instead of the other, not trying to prevent it from reordering anything.
>> Isn't this the point the documentation wants to get across when it says
>> that comparing pointers can be dangerous?
> 
> The motivation for introducing ptr_eq() is indeed because the
> compiler barrier is not sufficient to prevent the compiler from
> using one pointer instead of the other.

barrier_data(&b) prevents that.

> 
> But it turns out that ptr_eq() is also a good tool to prevent the
> compiler from reordering loads in case where the comparison is
> done against a constant.
> 
>>> CPU speculating the loads across the control dependency is not an
>>> issue.
>>> 
>>> So am I tempted to keep examples that clearly state whether
>>> the issue is caused by compiler reordering instructions, or by
>>> CPU speculation.
>> Isn't it true that on strongly ordered CPUs, a compiler barrier is
>> sufficient to prevent the rcu_dereference() problem?  So the whole idea
>> behind ptr_eq() is that it prevents the problem on all CPUs.
> 
> Correct. But given that we have ptr_eq(), it's good to show how it
> equally prevents the compiler from reordering address-dependent loads
> (comparison with constant) *and* prevents the compiler from using
> one pointer rather than the other (comparison between two non-constant
> pointers) which affects speculation on weakly-ordered CPUs.
> 
>> You can make your examples as specific as you like, but the fact remains
>> that ptr_eq() is meant to prevent situations where both:
>> The compiler uses the wrong pointer for a load, and
>> The CPU performs the load earlier than you want.
>> If either one of those doesn't hold then the problem won't arise.
> 
> Correct.
> 
> Thanks,
> 
> Mathieu
> 
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
> 
>

Gary Guo Sept. 28, 2024, 11:24 p.m. UTC | #8

Cc: Nikita Popov <[e-mail]>
Cc: [e-mail]

On Sat, 28 Sep 2024 09:51:27 -0400
Mathieu Desnoyers <[e-mail]> wrote:

> Compiler CSE and SSA GVN optimizations can cause the address dependency
> of addresses returned by rcu_dereference to be lost when comparing those
> pointers with either constants or previously loaded pointers.
> 
> Introduce ptr_eq() to compare two addresses while preserving the address
> dependencies for later use of the address. It should be used when
> comparing an address returned by rcu_dereference().
> 
> This is needed to prevent the compiler CSE and SSA GVN optimizations
> from replacing the registers holding @a or @b based on their
> equality, which does not preserve address dependencies and allows the
> following misordering speculations:
> 
> - If @b is a constant, the compiler can issue the loads which depend
>   on @a before loading @a.
> - If @b is a register populated by a prior load, weakly-ordered
>   CPUs can speculate loads which depend on @a before loading @a.
> 
> The same logic applies with @a and @b swapped.
> 
> The compiler barrier() is ineffective at fixing this issue.
> It does not prevent the compiler CSE from losing the address dependency:
> 
> int fct_2_volatile_barriers(void)
> {
>     int *a, *b;
> 
>     do {
>         a = READ_ONCE(p);
>         asm volatile ("" : : : "memory");
>         b = READ_ONCE(p);
>     } while (a != b);
>     asm volatile ("" : : : "memory");  <----- barrier()
>     return *b;
> }
> 
> With gcc 14.2 (arm64):
> 
> fct_2_volatile_barriers:
>         adrp    x0, .LANCHOR0
>         add     x0, x0, :lo12:.LANCHOR0
> .L2:
>         ldr     x1, [x0]    <------ x1 populated by first load.
>         ldr     x2, [x0]
>         cmp     x1, x2
>         bne     .L2
>         ldr     w0, [x1]    <------ x1 is used for access which should depend on b.
>         ret
> 
> On weakly-ordered architectures, this lets CPU speculation use the
> result from the first load to speculate "ldr w0, [x1]" before
> "ldr x2, [x0]".
> Based on the RCU documentation, the control dependency does not prevent
> the CPU from speculating loads.

I recall seeing Nikita Popov (nikic) doing work related to this to LLVM
so it respects pointer provenances much better and doesn't randomly
replace pointers with others if they compare equal. So I tried to
reproduce this example on clang, which seems to generate the correct
code, loading from *b instead of *a.

The generated code with "ptr_eq" however produces one extra move
instruction which is not necessary.

I digged into the LLVM source code to see if this behaviour is that we
can rely on, and found that the GVN in use is very careful with
replacing pointers [1].

Essentially:
* null can be replaced
* constant addresses can be replaced <-- bad for this use case
* pointers originate from the same value (getUnderlyingObject).

So it appears to me that if we can ensure that neither a or b come
from a constant address then the OPTIMIZER_HIDE_VAR might be
unnecessary for clang? This should be testable with __builtin_constant_p.

Not necessary worth additional complexity handling clang specially, but
I think this is GCC/clang difference is worth pointing out.

I cc'ed nikic and clang-built-linux mailing list, please correct me if
I'm wrong.

[1]: https://github.com/llvm/llvm-project/blob/6558e5615ae9e6af6168b0a363808854fd66663f/llvm/lib/Analysis/Loads.cpp#L777-L788

Best,
Gary

> 
> Suggested-by: Linus Torvalds <[e-mail]>
> Suggested-by: Boqun Feng <[e-mail]>
> Signed-off-by: Mathieu Desnoyers <[e-mail]>
> Reviewed-by: Boqun Feng <[e-mail]>
> Acked-by: "Paul E. McKenney" <[e-mail]>
> Cc: Greg Kroah-Hartman <[e-mail]>
> Cc: Sebastian Andrzej Siewior <[e-mail]>
> Cc: "Paul E. McKenney" <[e-mail]>
> Cc: Will Deacon <[e-mail]>
> Cc: Peter Zijlstra <[e-mail]>
> Cc: Boqun Feng <[e-mail]>
> Cc: Alan Stern <[e-mail]>
> Cc: John Stultz <[e-mail]>
> Cc: Neeraj Upadhyay <[e-mail]>
> Cc: Linus Torvalds <[e-mail]>
> Cc: Boqun Feng <[e-mail]>
> Cc: Frederic Weisbecker <[e-mail]>
> Cc: Joel Fernandes <[e-mail]>
> Cc: Josh Triplett <[e-mail]>
> Cc: Uladzislau Rezki <[e-mail]>
> Cc: Steven Rostedt <[e-mail]>
> Cc: Lai Jiangshan <[e-mail]>
> Cc: Zqiang <[e-mail]>
> Cc: Ingo Molnar <[e-mail]>
> Cc: Waiman Long <[e-mail]>
> Cc: Mark Rutland <[e-mail]>
> Cc: Thomas Gleixner <[e-mail]>
> Cc: Vlastimil Babka <[e-mail]>
> Cc: [e-mail]
> Cc: Mateusz Guzik <[e-mail]>
> Cc: Gary Guo <[e-mail]>
> Cc: Jonas Oberhauser <[e-mail]>
> Cc: [e-mail]
> Cc: [e-mail]
> Cc: [e-mail]
> ---
>  include/linux/compiler.h | 62 ++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 62 insertions(+)
> 
> diff --git a/include/linux/compiler.h b/include/linux/compiler.h
> index 2df665fa2964..f26705c267e8 100644
> --- a/include/linux/compiler.h
> +++ b/include/linux/compiler.h
> @@ -186,6 +186,68 @@ void ftrace_likely_update(struct ftrace_likely_data *f, int val,
>  	__asm__ ("" : "=r" (var) : "0" (var))
>  #endif
>  
> +/*
> + * Compare two addresses while preserving the address dependencies for
> + * later use of the address. It should be used when comparing an address
> + * returned by rcu_dereference().
> + *
> + * This is needed to prevent the compiler CSE and SSA GVN optimizations
> + * from replacing the registers holding @a or @b based on their
> + * equality, which does not preserve address dependencies and allows the
> + * following misordering speculations:
> + *
> + * - If @b is a constant, the compiler can issue the loads which depend
> + *   on @a before loading @a.
> + * - If @b is a register populated by a prior load, weakly-ordered
> + *   CPUs can speculate loads which depend on @a before loading @a.
> + *
> + * The same logic applies with @a and @b swapped.
> + *
> + * Return value: true if pointers are equal, false otherwise.
> + *
> + * The compiler barrier() is ineffective at fixing this issue. It does
> + * not prevent the compiler CSE from losing the address dependency:
> + *
> + * int fct_2_volatile_barriers(void)
> + * {
> + *     int *a, *b;
> + *
> + *     do {
> + *         a = READ_ONCE(p);
> + *         asm volatile ("" : : : "memory");
> + *         b = READ_ONCE(p);
> + *     } while (a != b);
> + *     asm volatile ("" : : : "memory");  <-- barrier()
> + *     return *b;
> + * }
> + *
> + * With gcc 14.2 (arm64):
> + *
> + * fct_2_volatile_barriers:
> + *         adrp    x0, .LANCHOR0
> + *         add     x0, x0, :lo12:.LANCHOR0
> + * .L2:
> + *         ldr     x1, [x0]  <-- x1 populated by first load.
> + *         ldr     x2, [x0]
> + *         cmp     x1, x2
> + *         bne     .L2
> + *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
> + *         ret
> + *

> + * On weakly-ordered architectures, this lets CPU speculation use the
> + * result from the first load to speculate "ldr w0, [x1]" before
> + * "ldr x2, [x0]".
> + * Based on the RCU documentation, the control dependency does not
> + * prevent the CPU from speculating loads.
> + */
> +static __always_inline
> +int ptr_eq(const volatile void *a, const volatile void *b)
> +{
> +	OPTIMIZER_HIDE_VAR(a);
> +	OPTIMIZER_HIDE_VAR(b);
> +	return a == b;
> +}
> +
>  #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
>  
>  /**

Boqun Feng Sept. 28, 2024, 11:55 p.m. UTC | #9

On Sun, Sep 29, 2024, at 6:26 AM, Alan Huang wrote:
> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>> 
>> On 2024-09-28 17:49, Alan Stern wrote:
>>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>>> equality, which does not preserve address dependencies and allows the
>>>>>> following misordering speculations:
>>>>>> 
>>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>>    on @a before loading @a.
>>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>>    CPUs can speculate loads which depend on @a before loading @a.
>>>>> 
>>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>>> anything else.  All that matters is that the compiler uses the wrong
>>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>>> expect it to, based on the source code alone.
>>>> 
>>>> I only partially agree here.
>>>> 
>>>> On weakly-ordered architectures, indeed we don't care whether the
>>>> issue is caused by the compiler reordering the code (constant)
>>>> or the CPU speculating the load (registers).
>>>> 
>>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>>> case is problematic (compiler reordering the dependent load), because
>>> I thought you were trying to prevent the compiler from using one pointer
>>> instead of the other, not trying to prevent it from reordering anything.
>>> Isn't this the point the documentation wants to get across when it says
>>> that comparing pointers can be dangerous?
>> 
>> The motivation for introducing ptr_eq() is indeed because the
>> compiler barrier is not sufficient to prevent the compiler from
>> using one pointer instead of the other.
>
> barrier_data(&b) prevents that.
>

It prevents that because it acts as barrier() + OPTIMIZER_HIDE_VAR(b).
I don’t see much value of using that since we can resolve the problem
with OPTIMIZER_HIDE_VAR() alone.

Regards,
Boqun

>> 
>> But it turns out that ptr_eq() is also a good tool to prevent the
>> compiler from reordering loads in case where the comparison is
>> done against a constant.
>> 
>>>> CPU speculating the loads across the control dependency is not an
>>>> issue.
>>>> 
>>>> So am I tempted to keep examples that clearly state whether
>>>> the issue is caused by compiler reordering instructions, or by
>>>> CPU speculation.
>>> Isn't it true that on strongly ordered CPUs, a compiler barrier is
>>> sufficient to prevent the rcu_dereference() problem?  So the whole idea
>>> behind ptr_eq() is that it prevents the problem on all CPUs.
>> 
>> Correct. But given that we have ptr_eq(), it's good to show how it
>> equally prevents the compiler from reordering address-dependent loads
>> (comparison with constant) *and* prevents the compiler from using
>> one pointer rather than the other (comparison between two non-constant
>> pointers) which affects speculation on weakly-ordered CPUs.
>> 
>>> You can make your examples as specific as you like, but the fact remains
>>> that ptr_eq() is meant to prevent situations where both:
>>> The compiler uses the wrong pointer for a load, and
>>> The CPU performs the load earlier than you want.
>>> If either one of those doesn't hold then the problem won't arise.
>> 
>> Correct.
>> 
>> Thanks,
>> 
>> Mathieu
>> 
>> 
>> -- 
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com
>> 
>>

Alan Huang Sept. 29, 2024, 12:20 a.m. UTC | #10

2024年9月29日 07:55，Boqun Feng <[e-mail]> wrote：
> 
> 
> 
> On Sun, Sep 29, 2024, at 6:26 AM, Alan Huang wrote:
>> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>> 
>>> On 2024-09-28 17:49, Alan Stern wrote:
>>>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>>>> equality, which does not preserve address dependencies and allows the
>>>>>>> following misordering speculations:
>>>>>>> 
>>>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>>>   on @a before loading @a.
>>>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>>>   CPUs can speculate loads which depend on @a before loading @a.
>>>>>> 
>>>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>>>> anything else.  All that matters is that the compiler uses the wrong
>>>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>>>> expect it to, based on the source code alone.
>>>>> 
>>>>> I only partially agree here.
>>>>> 
>>>>> On weakly-ordered architectures, indeed we don't care whether the
>>>>> issue is caused by the compiler reordering the code (constant)
>>>>> or the CPU speculating the load (registers).
>>>>> 
>>>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>>>> case is problematic (compiler reordering the dependent load), because
>>>> I thought you were trying to prevent the compiler from using one pointer
>>>> instead of the other, not trying to prevent it from reordering anything.
>>>> Isn't this the point the documentation wants to get across when it says
>>>> that comparing pointers can be dangerous?
>>> 
>>> The motivation for introducing ptr_eq() is indeed because the
>>> compiler barrier is not sufficient to prevent the compiler from
>>> using one pointer instead of the other.
>> 
>> barrier_data(&b) prevents that.
>> 
> 
> It prevents that because it acts as barrier() + OPTIMIZER_HIDE_VAR(b).
> I don’t see much value of using that since we can resolve the problem
> with OPTIMIZER_HIDE_VAR() alone.

Yeah, barrier_data generates more instructions.

> 
> Regards,
> Boqun
> 
>>> 
>>> But it turns out that ptr_eq() is also a good tool to prevent the
>>> compiler from reordering loads in case where the comparison is
>>> done against a constant.
>>> 
>>>>> CPU speculating the loads across the control dependency is not an
>>>>> issue.
>>>>> 
>>>>> So am I tempted to keep examples that clearly state whether
>>>>> the issue is caused by compiler reordering instructions, or by
>>>>> CPU speculation.
>>>> Isn't it true that on strongly ordered CPUs, a compiler barrier is
>>>> sufficient to prevent the rcu_dereference() problem?  So the whole idea
>>>> behind ptr_eq() is that it prevents the problem on all CPUs.
>>> 
>>> Correct. But given that we have ptr_eq(), it's good to show how it
>>> equally prevents the compiler from reordering address-dependent loads
>>> (comparison with constant) *and* prevents the compiler from using
>>> one pointer rather than the other (comparison between two non-constant
>>> pointers) which affects speculation on weakly-ordered CPUs.
>>> 
>>>> You can make your examples as specific as you like, but the fact remains
>>>> that ptr_eq() is meant to prevent situations where both:
>>>> The compiler uses the wrong pointer for a load, and
>>>> The CPU performs the load earlier than you want.
>>>> If either one of those doesn't hold then the problem won't arise.
>>> 
>>> Correct.
>>> 
>>> Thanks,
>>> 
>>> Mathieu
>>> 
>>> 
>>> -- 
>>> Mathieu Desnoyers
>>> EfficiOS Inc.
>>> https://www.efficios.com

Mathieu Desnoyers Sept. 29, 2024, 10:36 a.m. UTC | #11

On 2024-09-29 01:24, Gary Guo wrote:
> Cc: Nikita Popov <[e-mail]>
> Cc: [e-mail]
> 
> On Sat, 28 Sep 2024 09:51:27 -0400
> Mathieu Desnoyers <[e-mail]> wrote:
> 
>> Compiler CSE and SSA GVN optimizations can cause the address dependency
>> of addresses returned by rcu_dereference to be lost when comparing those
>> pointers with either constants or previously loaded pointers.
>>
>> Introduce ptr_eq() to compare two addresses while preserving the address
>> dependencies for later use of the address. It should be used when
>> comparing an address returned by rcu_dereference().
>>
>> This is needed to prevent the compiler CSE and SSA GVN optimizations
>> from replacing the registers holding @a or @b based on their
>> equality, which does not preserve address dependencies and allows the
>> following misordering speculations:
>>
>> - If @b is a constant, the compiler can issue the loads which depend
>>    on @a before loading @a.
>> - If @b is a register populated by a prior load, weakly-ordered
>>    CPUs can speculate loads which depend on @a before loading @a.
>>
>> The same logic applies with @a and @b swapped.
>>
>> The compiler barrier() is ineffective at fixing this issue.
>> It does not prevent the compiler CSE from losing the address dependency:
>>
>> int fct_2_volatile_barriers(void)
>> {
>>      int *a, *b;
>>
>>      do {
>>          a = READ_ONCE(p);
>>          asm volatile ("" : : : "memory");
>>          b = READ_ONCE(p);
>>      } while (a != b);
>>      asm volatile ("" : : : "memory");  <----- barrier()
>>      return *b;
>> }
>>
>> With gcc 14.2 (arm64):
>>
>> fct_2_volatile_barriers:
>>          adrp    x0, .LANCHOR0
>>          add     x0, x0, :lo12:.LANCHOR0
>> .L2:
>>          ldr     x1, [x0]    <------ x1 populated by first load.
>>          ldr     x2, [x0]
>>          cmp     x1, x2
>>          bne     .L2
>>          ldr     w0, [x1]    <------ x1 is used for access which should depend on b.
>>          ret
>>
>> On weakly-ordered architectures, this lets CPU speculation use the
>> result from the first load to speculate "ldr w0, [x1]" before
>> "ldr x2, [x0]".
>> Based on the RCU documentation, the control dependency does not prevent
>> the CPU from speculating loads.
> 
> I recall seeing Nikita Popov (nikic) doing work related to this to LLVM
> so it respects pointer provenances much better and doesn't randomly
> replace pointers with others if they compare equal. So I tried to
> reproduce this example on clang, which seems to generate the correct
> code, loading from *b instead of *a.
> 
> The generated code with "ptr_eq" however produces one extra move
> instruction which is not necessary.
> 
> I digged into the LLVM source code to see if this behaviour is that we
> can rely on, and found that the GVN in use is very careful with
> replacing pointers [1].
> 
> Essentially:
> * null can be replaced
> * constant addresses can be replaced <-- bad for this use case
> * pointers originate from the same value (getUnderlyingObject).
> 
> So it appears to me that if we can ensure that neither a or b come
> from a constant address then the OPTIMIZER_HIDE_VAR might be
> unnecessary for clang? This should be testable with __builtin_constant_p.
> 
> Not necessary worth additional complexity handling clang specially, but
> I think this is GCC/clang difference is worth pointing out.

Thanks for the thorough analysis of the clang GVN behavior. It confirms
my observations.

AFAIU, your proposal is to add a clang-specific #ifdef to eliminate one
mov from register to register (and thus free one register) when ptr_eq()
is used.

I'm not sure the gain (removing this extra mov) is worth it if what we
lose is robustness.

This would make the code dependent on current clang GVN optimization
design choices which are really specific to the compiler implementation
rather than guaranteed by the C standard. How can we be sure it won't
subtly break with a future clang version ?

If we think about it purely from a compiler optimization perspective,
using the content of the earliest loaded register allows weakly-ordered
CPUs to speculate following loads sooner. It's only when address
dependencies are needed (e.g. RCU) that this is unwanted. Am I missing
other cases where it is preferable to preserve address dependencies ?

Thanks,

Mathieu

> 
> I cc'ed nikic and clang-built-linux mailing list, please correct me if
> I'm wrong.
> 
> [1]: https://github.com/llvm/llvm-project/blob/6558e5615ae9e6af6168b0a363808854fd66663f/llvm/lib/Analysis/Loads.cpp#L777-L788
> 
> Best,
> Gary
> 
>>
>> Suggested-by: Linus Torvalds <[e-mail]>
>> Suggested-by: Boqun Feng <[e-mail]>
>> Signed-off-by: Mathieu Desnoyers <[e-mail]>
>> Reviewed-by: Boqun Feng <[e-mail]>
>> Acked-by: "Paul E. McKenney" <[e-mail]>
>> Cc: Greg Kroah-Hartman <[e-mail]>
>> Cc: Sebastian Andrzej Siewior <[e-mail]>
>> Cc: "Paul E. McKenney" <[e-mail]>
>> Cc: Will Deacon <[e-mail]>
>> Cc: Peter Zijlstra <[e-mail]>
>> Cc: Boqun Feng <[e-mail]>
>> Cc: Alan Stern <[e-mail]>
>> Cc: John Stultz <[e-mail]>
>> Cc: Neeraj Upadhyay <[e-mail]>
>> Cc: Linus Torvalds <[e-mail]>
>> Cc: Boqun Feng <[e-mail]>
>> Cc: Frederic Weisbecker <[e-mail]>
>> Cc: Joel Fernandes <[e-mail]>
>> Cc: Josh Triplett <[e-mail]>
>> Cc: Uladzislau Rezki <[e-mail]>
>> Cc: Steven Rostedt <[e-mail]>
>> Cc: Lai Jiangshan <[e-mail]>
>> Cc: Zqiang <[e-mail]>
>> Cc: Ingo Molnar <[e-mail]>
>> Cc: Waiman Long <[e-mail]>
>> Cc: Mark Rutland <[e-mail]>
>> Cc: Thomas Gleixner <[e-mail]>
>> Cc: Vlastimil Babka <[e-mail]>
>> Cc: [e-mail]
>> Cc: Mateusz Guzik <[e-mail]>
>> Cc: Gary Guo <[e-mail]>
>> Cc: Jonas Oberhauser <[e-mail]>
>> Cc: [e-mail]
>> Cc: [e-mail]
>> Cc: [e-mail]
>> ---
>>   include/linux/compiler.h | 62 ++++++++++++++++++++++++++++++++++++++++
>>   1 file changed, 62 insertions(+)
>>
>> diff --git a/include/linux/compiler.h b/include/linux/compiler.h
>> index 2df665fa2964..f26705c267e8 100644
>> --- a/include/linux/compiler.h
>> +++ b/include/linux/compiler.h
>> @@ -186,6 +186,68 @@ void ftrace_likely_update(struct ftrace_likely_data *f, int val,
>>   	__asm__ ("" : "=r" (var) : "0" (var))
>>   #endif
>>   
>> +/*
>> + * Compare two addresses while preserving the address dependencies for
>> + * later use of the address. It should be used when comparing an address
>> + * returned by rcu_dereference().
>> + *
>> + * This is needed to prevent the compiler CSE and SSA GVN optimizations
>> + * from replacing the registers holding @a or @b based on their
>> + * equality, which does not preserve address dependencies and allows the
>> + * following misordering speculations:
>> + *
>> + * - If @b is a constant, the compiler can issue the loads which depend
>> + *   on @a before loading @a.
>> + * - If @b is a register populated by a prior load, weakly-ordered
>> + *   CPUs can speculate loads which depend on @a before loading @a.
>> + *
>> + * The same logic applies with @a and @b swapped.
>> + *
>> + * Return value: true if pointers are equal, false otherwise.
>> + *
>> + * The compiler barrier() is ineffective at fixing this issue. It does
>> + * not prevent the compiler CSE from losing the address dependency:
>> + *
>> + * int fct_2_volatile_barriers(void)
>> + * {
>> + *     int *a, *b;
>> + *
>> + *     do {
>> + *         a = READ_ONCE(p);
>> + *         asm volatile ("" : : : "memory");
>> + *         b = READ_ONCE(p);
>> + *     } while (a != b);
>> + *     asm volatile ("" : : : "memory");  <-- barrier()
>> + *     return *b;
>> + * }
>> + *
>> + * With gcc 14.2 (arm64):
>> + *
>> + * fct_2_volatile_barriers:
>> + *         adrp    x0, .LANCHOR0
>> + *         add     x0, x0, :lo12:.LANCHOR0
>> + * .L2:
>> + *         ldr     x1, [x0]  <-- x1 populated by first load.
>> + *         ldr     x2, [x0]
>> + *         cmp     x1, x2
>> + *         bne     .L2
>> + *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
>> + *         ret
>> + *
> 
>> + * On weakly-ordered architectures, this lets CPU speculation use the
>> + * result from the first load to speculate "ldr w0, [x1]" before
>> + * "ldr x2, [x0]".
>> + * Based on the RCU documentation, the control dependency does not
>> + * prevent the CPU from speculating loads.
>> + */
>> +static __always_inline
>> +int ptr_eq(const volatile void *a, const volatile void *b)
>> +{
>> +	OPTIMIZER_HIDE_VAR(a);
>> +	OPTIMIZER_HIDE_VAR(b);
>> +	return a == b;
>> +}
>> +
>>   #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
>>   
>>   /**
>

Jonas Oberhauser Sept. 30, 2024, 8:57 a.m. UTC | #12

Am 9/29/2024 um 12:26 AM schrieb Alan Huang:
> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>
>> On 2024-09-28 17:49, Alan Stern wrote:
>>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>>> equality, which does not preserve address dependencies and allows the
>>>>>> following misordering speculations:
>>>>>>
>>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>>     on @a before loading @a.
>>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>>     CPUs can speculate loads which depend on @a before loading @a.
>>>>>
>>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>>> anything else.  All that matters is that the compiler uses the wrong
>>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>>> expect it to, based on the source code alone.
>>>>
>>>> I only partially agree here.
>>>>
>>>> On weakly-ordered architectures, indeed we don't care whether the
>>>> issue is caused by the compiler reordering the code (constant)
>>>> or the CPU speculating the load (registers).
>>>>
>>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>>> case is problematic (compiler reordering the dependent load), because
>>> I thought you were trying to prevent the compiler from using one pointer
>>> instead of the other, not trying to prevent it from reordering anything.
>>> Isn't this the point the documentation wants to get across when it says
>>> that comparing pointers can be dangerous?
>>
>> The motivation for introducing ptr_eq() is indeed because the
>> compiler barrier is not sufficient to prevent the compiler from
>> using one pointer instead of the other.
> 
> barrier_data(&b) prevents that.

I don't think one barrier_data can garantuee preventing this, because 
right after doing the comparison, the compiler still could do b=a.

In that case you would be guaranteed to use the value in b, but that 
value is not the value loaded into b originally but rather the value 
loaded into a, and hence your address dependency goes to the wrong load 
still.

However, doing

barrier_data(&b);
if (a == b) {
    barrier();
    foo(*b);
}

might maybe prevent it, because after the address of b is escaped, the 
compiler might no longer be allowed to just do b=a;, but I'm not sure if 
that is completely correct, since the compiler knows b==a and no other 
thread can be concurrently modifying a or b. Therefore, given that the 
compiler knows the hardware, it might know that assigning b=a would not 
cause any  race-related issues even if another thread was reading b 
concurrently.

Finally, it may be only a combination of barrier_data and making b 
volatile could be guaranteed to solve the issue, but the code will be 
very obscure compared to using ptr_eq.

   jonas

Alan Huang Sept. 30, 2024, 9:15 a.m. UTC | #13

2024年9月30日 16:57，Jonas Oberhauser <[e-mail]> 写道：
> 
> 
> 
> Am 9/29/2024 um 12:26 AM schrieb Alan Huang:
>> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>> 
>>> On 2024-09-28 17:49, Alan Stern wrote:
>>>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>>>> equality, which does not preserve address dependencies and allows the
>>>>>>> following misordering speculations:
>>>>>>> 
>>>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>>>    on @a before loading @a.
>>>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>>>    CPUs can speculate loads which depend on @a before loading @a.
>>>>>> 
>>>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>>>> anything else.  All that matters is that the compiler uses the wrong
>>>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>>>> expect it to, based on the source code alone.
>>>>> 
>>>>> I only partially agree here.
>>>>> 
>>>>> On weakly-ordered architectures, indeed we don't care whether the
>>>>> issue is caused by the compiler reordering the code (constant)
>>>>> or the CPU speculating the load (registers).
>>>>> 
>>>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>>>> case is problematic (compiler reordering the dependent load), because
>>>> I thought you were trying to prevent the compiler from using one pointer
>>>> instead of the other, not trying to prevent it from reordering anything.
>>>> Isn't this the point the documentation wants to get across when it says
>>>> that comparing pointers can be dangerous?
>>> 
>>> The motivation for introducing ptr_eq() is indeed because the
>>> compiler barrier is not sufficient to prevent the compiler from
>>> using one pointer instead of the other.
>> barrier_data(&b) prevents that.
> 
> I don't think one barrier_data can garantuee preventing this, because right after doing the comparison, the compiler still could do b=a.
> 
> In that case you would be guaranteed to use the value in b, but that value is not the value loaded into b originally but rather the value loaded into a, and hence your address dependency goes to the wrong load still.

After barrier_data(&b), *b will be loaded from memory, you mean even if *b is loaded from memory, the address dependency goes to the wrong load still?

> 
> However, doing
> 
> barrier_data(&b);
> if (a == b) {
>   barrier();
>   foo(*b);
> }
> 
> might maybe prevent it, because after the address of b is escaped, the compiler might no longer be allowed to just do b=a;, but I'm not sure if that is completely correct, since the compiler knows b==a and no other thread can be concurrently modifying a or b. Therefore, given that the compiler knows the hardware, it might know that assigning b=a would not cause any  race-related issues even if another thread was reading b concurrently.
> 
> Finally, it may be only a combination of barrier_data and making b volatile could be guaranteed to solve the issue, but the code will be very obscure compared to using ptr_eq.
> 
>  jonas

Alan Huang Sept. 30, 2024, 9:27 a.m. UTC | #14

2024年9月30日 17:15，Alan Huang <[e-mail]> 写道：
> 
> 2024年9月30日 16:57，Jonas Oberhauser <[e-mail]> 写道：
>> 
>> 
>> 
>> Am 9/29/2024 um 12:26 AM schrieb Alan Huang:
>>> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>>> 
>>>> On 2024-09-28 17:49, Alan Stern wrote:
>>>>> On Sat, Sep 28, 2024 at 11:32:18AM -0400, Mathieu Desnoyers wrote:
>>>>>> On 2024-09-28 16:49, Alan Stern wrote:
>>>>>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>>>>>> equality, which does not preserve address dependencies and allows the
>>>>>>>> following misordering speculations:
>>>>>>>> 
>>>>>>>> - If @b is a constant, the compiler can issue the loads which depend
>>>>>>>>   on @a before loading @a.
>>>>>>>> - If @b is a register populated by a prior load, weakly-ordered
>>>>>>>>   CPUs can speculate loads which depend on @a before loading @a.
>>>>>>> 
>>>>>>> It shouldn't matter whether @a and @b are constants, registers, or
>>>>>>> anything else.  All that matters is that the compiler uses the wrong
>>>>>>> one, which allows weakly ordered CPUs to speculate loads you wouldn't
>>>>>>> expect it to, based on the source code alone.
>>>>>> 
>>>>>> I only partially agree here.
>>>>>> 
>>>>>> On weakly-ordered architectures, indeed we don't care whether the
>>>>>> issue is caused by the compiler reordering the code (constant)
>>>>>> or the CPU speculating the load (registers).
>>>>>> 
>>>>>> However, on strongly-ordered architectures, AFAIU, only the constant
>>>>>> case is problematic (compiler reordering the dependent load), because
>>>>> I thought you were trying to prevent the compiler from using one pointer
>>>>> instead of the other, not trying to prevent it from reordering anything.
>>>>> Isn't this the point the documentation wants to get across when it says
>>>>> that comparing pointers can be dangerous?
>>>> 
>>>> The motivation for introducing ptr_eq() is indeed because the
>>>> compiler barrier is not sufficient to prevent the compiler from
>>>> using one pointer instead of the other.
>>> barrier_data(&b) prevents that.
>> 
>> I don't think one barrier_data can garantuee preventing this, because right after doing the comparison, the compiler still could do b=a.
>> 
>> In that case you would be guaranteed to use the value in b, but that value is not the value loaded into b originally but rather the value loaded into a, and hence your address dependency goes to the wrong load still.
> 
> After barrier_data(&b), *b will be loaded from memory, you mean even if *b is loaded from memory, the address dependency goes to the wrong load still?

Sorry, *b should b.

> 
>> 
>> However, doing
>> 
>> barrier_data(&b);
>> if (a == b) {
>>  barrier();
>>  foo(*b);
>> }
>> 
>> might maybe prevent it, because after the address of b is escaped, the compiler might no longer be allowed to just do b=a;, but I'm not sure if that is completely correct, since the compiler knows b==a and no other thread can be concurrently modifying a or b. Therefore, given that the compiler knows the hardware, it might know that assigning b=a would not cause any  race-related issues even if another thread was reading b concurrently.
>> 
>> Finally, it may be only a combination of barrier_data and making b volatile could be guaranteed to solve the issue, but the code will be very obscure compared to using ptr_eq.
>> 
>> jonas

Jonas Oberhauser Sept. 30, 2024, 9:33 a.m. UTC | #15

Am 9/30/2024 um 11:27 AM schrieb Alan Huang:
> 2024年9月30日 17:15，Alan Huang <[e-mail]> 写道：
>>
>> 2024年9月30日 16:57，Jonas Oberhauser <[e-mail]> 写道：
>>>
>>>
>>>
>>> Am 9/29/2024 um 12:26 AM schrieb Alan Huang:
>>>> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>>>>
>>>>> The motivation for introducing ptr_eq() is indeed because the
>>>>> compiler barrier is not sufficient to prevent the compiler from
>>>>> using one pointer instead of the other.
>>>> barrier_data(&b) prevents that.
>>>
>>> I don't think one barrier_data can garantuee preventing this, because right after doing the comparison, the compiler still could do b=a.
>>>
>>> In that case you would be guaranteed to use the value in b, but that value is not the value loaded into b originally but rather the value loaded into a, and hence your address dependency goes to the wrong load still.
>>
>> After barrier_data(&b), *b will be loaded from memory, you mean even if *b is loaded from memory, the address dependency goes to the wrong load still?
> 
> Sorry, *b should b.

That's exactly what I meant to say. In my understanding, it can happen 
like this:

a = READ_ONCE(*p);
...
b = READ_ONCE(*p);
if (a == b) {
    b = a; // inserted by compiler

    barrier_data(&b);

    foo(*b); // compiler definitely use the current value in b
}



In the end, the address dependency is from the first load, and the CPU 
can speculatively (with register renaming, forwarding etc) execute

a = READ_ONCE(*p);
b2 = a; // speculatively
tmp = load *b2 // speculatively
b1 = READ_ONCE(*p);
if (a == b1) { // confirmed
    foo(tmp);
}


best wishes,
   jonas

Jonas Oberhauser Sept. 30, 2024, 9:42 a.m. UTC | #16

Am 9/28/2024 um 11:15 PM schrieb Alan Stern:
> On Sat, Sep 28, 2024 at 11:55:22AM -0400, Mathieu Desnoyers wrote:
>> On 2024-09-28 17:49, Alan Stern wrote:
>>> Isn't it true that on strongly ordered CPUs, a compiler barrier is
>>> sufficient to prevent the rcu_dereference() problem?  So the whole idea
>>> behind ptr_eq() is that it prevents the problem on all CPUs.
>>
>> Correct. But given that we have ptr_eq(), it's good to show how it
>> equally prevents the compiler from reordering address-dependent loads
>> (comparison with constant) *and* prevents the compiler from using
>> one pointer rather than the other (comparison between two non-constant
>> pointers) which affects speculation on weakly-ordered CPUs.
> 
> I don't see how these two things differ from each other.  In the
> comparison-with-a-constant case, how is the compiler reordering
> anything?  Isn't it just using the constant address rather than the
> loaded pointer and thereby breaking the address dependency?

I also currently don't see any major difference between the constant and 
register case. The point is that the address is known before loading 
into b, and hence the compiler + hardware can speculatively load *b 
before loading into b.

The only difference is how far before loading into b the address is known.

Best wishes,
   jonas

Alan Huang Sept. 30, 2024, 10:12 a.m. UTC | #17

On Sep 30, 2024, at 17:33, Jonas Oberhauser <[e-mail]> wrote:
> 
> 
> 
> Am 9/30/2024 um 11:27 AM schrieb Alan Huang:
>> 2024年9月30日 17:15，Alan Huang <[e-mail]> 写道：
>>> 
>>> 2024年9月30日 16:57，Jonas Oberhauser <[e-mail]> 写道：
>>>> 
>>>> 
>>>> 
>>>> Am 9/29/2024 um 12:26 AM schrieb Alan Huang:
>>>>> 2024年9月28日 23:55，Mathieu Desnoyers <[e-mail]> wrote：
>>>>>> 
>>>>>> The motivation for introducing ptr_eq() is indeed because the
>>>>>> compiler barrier is not sufficient to prevent the compiler from
>>>>>> using one pointer instead of the other.
>>>>> barrier_data(&b) prevents that.
>>>> 
>>>> I don't think one barrier_data can garantuee preventing this, because right after doing the comparison, the compiler still could do b=a.
>>>> 
>>>> In that case you would be guaranteed to use the value in b, but that value is not the value loaded into b originally but rather the value loaded into a, and hence your address dependency goes to the wrong load still.
>>> 
>>> After barrier_data(&b), *b will be loaded from memory, you mean even if *b is loaded from memory, the address dependency goes to the wrong load still?
>> Sorry, *b should b.
> 
> That's exactly what I meant to say. In my understanding, it can happen like this:
> 
> a = READ_ONCE(*p);
> ...
> b = READ_ONCE(*p);
> if (a == b) {
>   b = a; // inserted by compiler
> 
>   barrier_data(&b);
> 
>   foo(*b); // compiler definitely use the current value in b
> }
> 
> 
> 
> In the end, the address dependency is from the first load, and the CPU can speculatively (with register renaming, forwarding etc) execute
> 
> a = READ_ONCE(*p);
> b2 = a; // speculatively
> tmp = load *b2 // speculatively
> b1 = READ_ONCE(*p);
> if (a == b1) { // confirmed
>   foo(tmp);
> }

I get it now, thanks for the explanation.

> 
> 
> best wishes,
>  jonas
>

Paul E. McKenney Sept. 30, 2024, 11:04 a.m. UTC | #18

On Mon, Sep 30, 2024 at 11:42:11AM +0200, Jonas Oberhauser wrote:
> 
> 
> Am 9/28/2024 um 11:15 PM schrieb Alan Stern:
> > On Sat, Sep 28, 2024 at 11:55:22AM -0400, Mathieu Desnoyers wrote:
> > > On 2024-09-28 17:49, Alan Stern wrote:
> > > > Isn't it true that on strongly ordered CPUs, a compiler barrier is
> > > > sufficient to prevent the rcu_dereference() problem?  So the whole idea
> > > > behind ptr_eq() is that it prevents the problem on all CPUs.
> > > 
> > > Correct. But given that we have ptr_eq(), it's good to show how it
> > > equally prevents the compiler from reordering address-dependent loads
> > > (comparison with constant) *and* prevents the compiler from using
> > > one pointer rather than the other (comparison between two non-constant
> > > pointers) which affects speculation on weakly-ordered CPUs.
> > 
> > I don't see how these two things differ from each other.  In the
> > comparison-with-a-constant case, how is the compiler reordering
> > anything?  Isn't it just using the constant address rather than the
> > loaded pointer and thereby breaking the address dependency?
> 
> I also currently don't see any major difference between the constant and
> register case. The point is that the address is known before loading into b,
> and hence the compiler + hardware can speculatively load *b before loading
> into b.
> 
> The only difference is how far before loading into b the address is known.

In theory, true.  In practice, in the register case, you need a little
more bad luck for the compiler to be able to exploit your mistake.

Still, it is indeed far better to attain a state of bliss by keeping
the compiler ignorant.

							Thanx, Paul

Jonas Oberhauser Sept. 30, 2024, 11:26 a.m. UTC | #19

Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>> Compiler CSE and SSA GVN optimizations can cause the address dependency
>> of addresses returned by rcu_dereference to be lost when comparing those
>> pointers with either constants or previously loaded pointers.
>>
>> Introduce ptr_eq() to compare two addresses while preserving the address
>> dependencies for later use of the address. It should be used when
>> comparing an address returned by rcu_dereference().
>>
>> This is needed to prevent the compiler CSE and SSA GVN optimizations
>> from replacing the registers holding @a or @b based on their
> 
> "Replacing" isn't the right word.  What the compiler does is use one
> rather than the other.  Furthermore, the compiler can play these games
> even with values that aren't in registers.
> 
> You should just say: "... from using @a (or @b) in places where the
> source refers to @b (or @a) (based on the fact that after the
> comparison, the two are known to be equal), which does not ..."

I should also point out that it is not enough to prevent the compiler 
from using @a instead of @b.

It must also be prevented from assigning @b=@a, which it is often 
allowed to do after finding @a==@b.

Best wishes,
   jonas

Jonas Oberhauser Sept. 30, 2024, 12:06 p.m. UTC | #20

Am 9/30/2024 um 1:04 PM schrieb Paul E. McKenney:
> On Mon, Sep 30, 2024 at 11:42:11AM +0200, Jonas Oberhauser wrote:
>>
>>
>> I also currently don't see any major difference between the constant and
>> register case. The point is that the address is known before loading into b,
>> and hence the compiler + hardware can speculatively load *b before loading
>> into b.
> 
> In theory, true.  In practice, in the register case, you need a little
> more bad luck for the compiler to be able to exploit your mistake.

If there's one thing I've never run out of, then it is bad luck with 
technology.

   jonas

Paul E. McKenney Sept. 30, 2024, 1:54 p.m. UTC | #21

On Mon, Sep 30, 2024 at 02:06:12PM +0200, Jonas Oberhauser wrote:
> 
> 
> Am 9/30/2024 um 1:04 PM schrieb Paul E. McKenney:
> > On Mon, Sep 30, 2024 at 11:42:11AM +0200, Jonas Oberhauser wrote:
> > > 
> > > 
> > > I also currently don't see any major difference between the constant and
> > > register case. The point is that the address is known before loading into b,
> > > and hence the compiler + hardware can speculatively load *b before loading
> > > into b.
> > 
> > In theory, true.  In practice, in the register case, you need a little
> > more bad luck for the compiler to be able to exploit your mistake.
> 
> If there's one thing I've never run out of, then it is bad luck with
> technology.

Careful!  Someone might try to recruit you as tester.  ;-)

							Thanx, Paul

Alan Stern Sept. 30, 2024, 4:43 p.m. UTC | #22

On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> 
> 
> Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
> > > Compiler CSE and SSA GVN optimizations can cause the address dependency
> > > of addresses returned by rcu_dereference to be lost when comparing those
> > > pointers with either constants or previously loaded pointers.
> > > 
> > > Introduce ptr_eq() to compare two addresses while preserving the address
> > > dependencies for later use of the address. It should be used when
> > > comparing an address returned by rcu_dereference().
> > > 
> > > This is needed to prevent the compiler CSE and SSA GVN optimizations
> > > from replacing the registers holding @a or @b based on their
> > 
> > "Replacing" isn't the right word.  What the compiler does is use one
> > rather than the other.  Furthermore, the compiler can play these games
> > even with values that aren't in registers.
> > 
> > You should just say: "... from using @a (or @b) in places where the
> > source refers to @b (or @a) (based on the fact that after the
> > comparison, the two are known to be equal), which does not ..."
> 
> I should also point out that it is not enough to prevent the compiler from
> using @a instead of @b.
> 
> It must also be prevented from assigning @b=@a, which it is often allowed to
> do after finding @a==@b.

Wouldn't that be a bug?  Consider this litmus test:

int x = 0;
int y = 45;
int z = 0;

void P0(int *x, int *y, int *z) {
	int r1, r2;

	r1 = READ_ONCE(*x);
	r2 = READ_ONCE(*y);
	if (r1 == r2) {
		WRITE_ONCE(*z, 1);
		// L1: WRITE_ONCE(*y, r1);
	}
}

void P1(int *x, int *y) {
	int r3;

	WRITE_ONCE(*x, 45);
	WRITE_ONCE(*y, 56);
	r3 = READ_ONCE(*y);
}

exists (z=1 /\ 1:r3=45)		(* Not allowed *)

If the compiler were to make the extra assignment (basically, 
uncommenting the line marked L1) then the exists clause could be 
satisfied.  That would indicate there's a bug in the compiler.

Alan

Jonas Oberhauser Sept. 30, 2024, 5:05 p.m. UTC | #23

Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
>>
>>
>> Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
>>> On Sat, Sep 28, 2024 at 09:51:27AM -0400, Mathieu Desnoyers wrote:
>>>> Compiler CSE and SSA GVN optimizations can cause the address dependency
>>>> of addresses returned by rcu_dereference to be lost when comparing those
>>>> pointers with either constants or previously loaded pointers.
>>>>
>>>> Introduce ptr_eq() to compare two addresses while preserving the address
>>>> dependencies for later use of the address. It should be used when
>>>> comparing an address returned by rcu_dereference().
>>>>
>>>> This is needed to prevent the compiler CSE and SSA GVN optimizations
>>>> from replacing the registers holding @a or @b based on their
>>>
>>> "Replacing" isn't the right word.  What the compiler does is use one
>>> rather than the other.  Furthermore, the compiler can play these games
>>> even with values that aren't in registers.
>>>
>>> You should just say: "... from using @a (or @b) in places where the
>>> source refers to @b (or @a) (based on the fact that after the
>>> comparison, the two are known to be equal), which does not ..."
>>
>> I should also point out that it is not enough to prevent the compiler from
>> using @a instead of @b.
>>
>> It must also be prevented from assigning @b=@a, which it is often allowed to
>> do after finding @a==@b.
> 
> Wouldn't that be a bug? 

That's why I said that it is often allowed to do it. In your case it 
wouldn't, but it is often possible when a and b are non-atomic & 
non-volatile (and haven't escaped, and I believe sometimes even then).

It happens for example here with GCC 14.1.0 -O3:

int fct_hide(void)
{
     int *a, *b;

     do {
         a = READ_ONCE(p);
         asm volatile ("" : : : "memory");
         b = READ_ONCE(p);
     } while (a != b);
     OPTIMIZER_HIDE_VAR(b);
     return *b;
}



         ldr     r1, [r2]
         ldr     r3, [r2]
         cmp     r1, r3
         bne     .L6
         mov     r3, r1   // nay...
         ldr     r0, [r3] // yay!
         bx      lr


Have fun,

    jonas

Alan Stern Sept. 30, 2024, 6:53 p.m. UTC | #24

On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> 
> 
> Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > 
> > > 
> > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > 
> > > I should also point out that it is not enough to prevent the compiler from
> > > using @a instead of @b.
> > > 
> > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > do after finding @a==@b.
> > 
> > Wouldn't that be a bug?
> 
> That's why I said that it is often allowed to do it. In your case it
> wouldn't, but it is often possible when a and b are non-atomic &
> non-volatile (and haven't escaped, and I believe sometimes even then).
> 
> It happens for example here with GCC 14.1.0 -O3:
> 
> int fct_hide(void)
> {
>     int *a, *b;
> 
>     do {
>         a = READ_ONCE(p);
>         asm volatile ("" : : : "memory");
>         b = READ_ONCE(p);
>     } while (a != b);
>     OPTIMIZER_HIDE_VAR(b);
>     return *b;
> }
> 
> 
> 
>         ldr     r1, [r2]
>         ldr     r3, [r2]
>         cmp     r1, r3
>         bne     .L6
>         mov     r3, r1   // nay...

A totally unnecessary instruction, which accomplishes nothing other than 
to waste time, space, and energy.  But nonetheless, allowed -- I agree.

The people in charge of GCC's optimizer might like to hear about this, 
if they're not already aware of it...

>         ldr     r0, [r3] // yay!
>         bx      lr

One could argue that in this example the compiler _has_ used *a instead 
of *b.  However, such an argument would have more force if we had 
described what we are talking about more precisely.

Yes, we do want to prevent compilers from doing this.  I'm not sure that 
it really needs to be mentioned in the comments or commit description, 
though.

Alan

David Laight Oct. 1, 2024, 5:11 p.m. UTC | #25

From: Alan Stern
> Sent: 30 September 2024 19:53
> 
> On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> >
> >
> > Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > >
> > > >
> > > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > >
> > > > I should also point out that it is not enough to prevent the compiler from
> > > > using @a instead of @b.
> > > >
> > > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > > do after finding @a==@b.
> > >
> > > Wouldn't that be a bug?
> >
> > That's why I said that it is often allowed to do it. In your case it
> > wouldn't, but it is often possible when a and b are non-atomic &
> > non-volatile (and haven't escaped, and I believe sometimes even then).
> >
> > It happens for example here with GCC 14.1.0 -O3:
> >
> > int fct_hide(void)
> > {
> >     int *a, *b;
> >
> >     do {
> >         a = READ_ONCE(p);
> >         asm volatile ("" : : : "memory");
> >         b = READ_ONCE(p);
> >     } while (a != b);
> >     OPTIMIZER_HIDE_VAR(b);
> >     return *b;
> > }
> >
> >
> >
> >         ldr     r1, [r2]
> >         ldr     r3, [r2]
> >         cmp     r1, r3
> >         bne     .L6
> >         mov     r3, r1   // nay...
> 
> A totally unnecessary instruction, which accomplishes nothing other than
> to waste time, space, and energy.  But nonetheless, allowed -- I agree.
> 
> The people in charge of GCC's optimizer might like to hear about this,
> if they're not already aware of it...
> 
> >         ldr     r0, [r3] // yay!
> >         bx      lr
> 
> One could argue that in this example the compiler _has_ used *a instead
> of *b.  However, such an argument would have more force if we had
> described what we are talking about more precisely.

The 'mov r3, r1' has nothing to do with 'a'.
It is a more general problem that OPTIMISER_HIDE_VAR() pretty much
always ends up allocating a different internal 'register' for the
output and then allocating a separate physical rehgister.

There doesn't seem to be a later optimisation path to remove
'pointless' register moves.

	David

> 
> Yes, we do want to prevent compilers from doing this.  I'm not sure that
> it really needs to be mentioned in the comments or commit description,
> though.
> 
> Alan

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Alan Stern Oct. 1, 2024, 10:57 p.m. UTC | #26

On Tue, Oct 01, 2024 at 05:11:05PM +0000, David Laight wrote:
> From: Alan Stern
> > Sent: 30 September 2024 19:53
> > 
> > On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> > >
> > >
> > > Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > > > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > > >
> > > > >
> > > > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > > >
> > > > > I should also point out that it is not enough to prevent the compiler from
> > > > > using @a instead of @b.
> > > > >
> > > > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > > > do after finding @a==@b.
> > > >
> > > > Wouldn't that be a bug?
> > >
> > > That's why I said that it is often allowed to do it. In your case it
> > > wouldn't, but it is often possible when a and b are non-atomic &
> > > non-volatile (and haven't escaped, and I believe sometimes even then).
> > >
> > > It happens for example here with GCC 14.1.0 -O3:
> > >
> > > int fct_hide(void)
> > > {
> > >     int *a, *b;
> > >
> > >     do {
> > >         a = READ_ONCE(p);
> > >         asm volatile ("" : : : "memory");
> > >         b = READ_ONCE(p);
> > >     } while (a != b);
> > >     OPTIMIZER_HIDE_VAR(b);
> > >     return *b;
> > > }
> > >
> > >
> > >
> > >         ldr     r1, [r2]
> > >         ldr     r3, [r2]
> > >         cmp     r1, r3
> > >         bne     .L6
> > >         mov     r3, r1   // nay...
> > 
> > A totally unnecessary instruction, which accomplishes nothing other than
> > to waste time, space, and energy.  But nonetheless, allowed -- I agree.
> > 
> > The people in charge of GCC's optimizer might like to hear about this,
> > if they're not already aware of it...
> > 
> > >         ldr     r0, [r3] // yay!
> > >         bx      lr
> > 
> > One could argue that in this example the compiler _has_ used *a instead
> > of *b.  However, such an argument would have more force if we had
> > described what we are talking about more precisely.
> 
> The 'mov r3, r1' has nothing to do with 'a'.

What do you mean by that?  At this point in the program, a is the 
variable whose value is stored in r1 and b is the variable whose value 
is stored in r3.  "mov r3, r1" copies the value from r1 into r3 and is 
therefore equivalent to executing "b = a".  (That is why I said one 
could argue that the "return *b" statement uses the value of *a.)  Thus 
it very much does have something to do with "a".

> It is a more general problem that OPTIMISER_HIDE_VAR() pretty much
> always ends up allocating a different internal 'register' for the
> output and then allocating a separate physical rehgister.

What output are you referring to?  Does OPTIMISER_HIDE_VAR() have an 
output?  If it does, the source program above ignores it, discarding any 
returned value.

> There doesn't seem to be a later optimisation path to remove
> 'pointless' register moves.

That would be a good thing to add, then.

Alan

David Laight Oct. 2, 2024, 8:13 a.m. UTC | #27

From: 'Alan Stern'
> Sent: 01 October 2024 23:57
> 
> On Tue, Oct 01, 2024 at 05:11:05PM +0000, David Laight wrote:
> > From: Alan Stern
> > > Sent: 30 September 2024 19:53
> > >
> > > On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> > > >
> > > >
> > > > Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > > > > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > > > >
> > > > > >
> > > > > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > > > >
> > > > > > I should also point out that it is not enough to prevent the compiler from
> > > > > > using @a instead of @b.
> > > > > >
> > > > > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > > > > do after finding @a==@b.
> > > > >
> > > > > Wouldn't that be a bug?
> > > >
> > > > That's why I said that it is often allowed to do it. In your case it
> > > > wouldn't, but it is often possible when a and b are non-atomic &
> > > > non-volatile (and haven't escaped, and I believe sometimes even then).
> > > >
> > > > It happens for example here with GCC 14.1.0 -O3:
> > > >
> > > > int fct_hide(void)
> > > > {
> > > >     int *a, *b;
> > > >
> > > >     do {
> > > >         a = READ_ONCE(p);
> > > >         asm volatile ("" : : : "memory");
> > > >         b = READ_ONCE(p);
> > > >     } while (a != b);
> > > >     OPTIMIZER_HIDE_VAR(b);
> > > >     return *b;
> > > > }
> > > >
> > > >
> > > >
> > > >         ldr     r1, [r2]
> > > >         ldr     r3, [r2]
> > > >         cmp     r1, r3
> > > >         bne     .L6
> > > >         mov     r3, r1   // nay...
> > >
> > > A totally unnecessary instruction, which accomplishes nothing other than
> > > to waste time, space, and energy.  But nonetheless, allowed -- I agree.
> > >
> > > The people in charge of GCC's optimizer might like to hear about this,
> > > if they're not already aware of it...
> > >
> > > >         ldr     r0, [r3] // yay!
> > > >         bx      lr
> > >
> > > One could argue that in this example the compiler _has_ used *a instead
> > > of *b.  However, such an argument would have more force if we had
> > > described what we are talking about more precisely.
> >
> > The 'mov r3, r1' has nothing to do with 'a'.
> 
> What do you mean by that?  At this point in the program, a is the
> variable whose value is stored in r1 and b is the variable whose value
> is stored in r3.  "mov r3, r1" copies the value from r1 into r3 and is
> therefore equivalent to executing "b = a".  (That is why I said one
> could argue that the "return *b" statement uses the value of *a.)  Thus
> it very much does have something to do with "a".

After the cmp and bne r1 and r3 have the same value.
The compiler tracks that and will use either register later.
That can never matter.
Remember the compiler tracks values (in pseudo/internal registers)
not variables.

> > It is a more general problem that OPTIMISER_HIDE_VAR() pretty much
> > always ends up allocating a different internal 'register' for the
> > output and then allocating a separate physical rehgister.
> 
> What output are you referring to?  Does OPTIMISER_HIDE_VAR() have an
> output?  If it does, the source program above ignores it, discarding any
> returned value.

Look up OPTIMISER_HIDE_VAR(x) it basically x = f(x) where f() is
the identity operation:
	asm ("" : "+r"(x))
I'll bet that gcc allocates a separate internal/pseudo register
for the result so wants to do y = f(x).
Probably generating y = x; y = f(y);
(The 'mov' might be after the asm, but I think that would get
optimised away - the listing file might help.)

So here the compiler has just decided to reuse the register that
held the other of a/b for the extra temporary.

	David

> 
> > There doesn't seem to be a later optimisation path to remove
> > 'pointless' register moves.
> 
> That would be a good thing to add, then.
> 
> Alan

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Alan Stern Oct. 2, 2024, 2:14 p.m. UTC | #28

On Wed, Oct 02, 2024 at 08:13:15AM +0000, David Laight wrote:
> From: 'Alan Stern'
> > Sent: 01 October 2024 23:57
> > 
> > On Tue, Oct 01, 2024 at 05:11:05PM +0000, David Laight wrote:
> > > From: Alan Stern
> > > > Sent: 30 September 2024 19:53
> > > >
> > > > On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> > > > >
> > > > >
> > > > > Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > > > > > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > > > > >
> > > > > > >
> > > > > > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > > > > >
> > > > > > > I should also point out that it is not enough to prevent the compiler from
> > > > > > > using @a instead of @b.
> > > > > > >
> > > > > > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > > > > > do after finding @a==@b.
> > > > > >
> > > > > > Wouldn't that be a bug?
> > > > >
> > > > > That's why I said that it is often allowed to do it. In your case it
> > > > > wouldn't, but it is often possible when a and b are non-atomic &
> > > > > non-volatile (and haven't escaped, and I believe sometimes even then).
> > > > >
> > > > > It happens for example here with GCC 14.1.0 -O3:
> > > > >
> > > > > int fct_hide(void)
> > > > > {
> > > > >     int *a, *b;
> > > > >
> > > > >     do {
> > > > >         a = READ_ONCE(p);
> > > > >         asm volatile ("" : : : "memory");
> > > > >         b = READ_ONCE(p);
> > > > >     } while (a != b);
> > > > >     OPTIMIZER_HIDE_VAR(b);
> > > > >     return *b;
> > > > > }
> > > > >
> > > > >
> > > > >
> > > > >         ldr     r1, [r2]
> > > > >         ldr     r3, [r2]
> > > > >         cmp     r1, r3
> > > > >         bne     .L6
> > > > >         mov     r3, r1   // nay...
> > > >
> > > > A totally unnecessary instruction, which accomplishes nothing other than
> > > > to waste time, space, and energy.  But nonetheless, allowed -- I agree.
> > > >
> > > > The people in charge of GCC's optimizer might like to hear about this,
> > > > if they're not already aware of it...
> > > >
> > > > >         ldr     r0, [r3] // yay!
> > > > >         bx      lr
> > > >
> > > > One could argue that in this example the compiler _has_ used *a instead
> > > > of *b.  However, such an argument would have more force if we had
> > > > described what we are talking about more precisely.
> > >
> > > The 'mov r3, r1' has nothing to do with 'a'.
> > 
> > What do you mean by that?  At this point in the program, a is the
> > variable whose value is stored in r1 and b is the variable whose value
> > is stored in r3.  "mov r3, r1" copies the value from r1 into r3 and is
> > therefore equivalent to executing "b = a".  (That is why I said one
> > could argue that the "return *b" statement uses the value of *a.)  Thus
> > it very much does have something to do with "a".
> 
> After the cmp and bne r1 and r3 have the same value.
> The compiler tracks that and will use either register later.
> That can never matter.

The whole point of this thread is that sometimes it _does_ matter.  Not 
on x86, but on weakly ordered architectures where using the wrong 
register will bypass a dependency and allow the CPU to speculatively 
load values earlier than the programmer wants it to.

> Remember the compiler tracks values (in pseudo/internal registers)
> not variables.
> 
> > > It is a more general problem that OPTIMISER_HIDE_VAR() pretty much
> > > always ends up allocating a different internal 'register' for the
> > > output and then allocating a separate physical rehgister.
> > 
> > What output are you referring to?  Does OPTIMISER_HIDE_VAR() have an
> > output?  If it does, the source program above ignores it, discarding any
> > returned value.
> 
> Look up OPTIMISER_HIDE_VAR(x) it basically x = f(x) where f() is
> the identity operation:
> 	asm ("" : "+r"(x))
> I'll bet that gcc allocates a separate internal/pseudo register
> for the result so wants to do y = f(x).
> Probably generating y = x; y = f(y);
> (The 'mov' might be after the asm, but I think that would get
> optimised away - the listing file might help.)
> 
> So here the compiler has just decided to reuse the register that
> held the other of a/b for the extra temporary.

I think you've got this backward.  As mentioned above, a is originally 
in r1 and b is in r3.  The source says OPTIMIZER_HIDE_VAR(b), so you're 
saying that gcc should be copying r3 into a separate internal/pseudo 
register.  But instead it's copying r1.

Alan

David Laight Oct. 2, 2024, 3:24 p.m. UTC | #29

From: 'Alan Stern'
> Sent: 02 October 2024 15:15
> 
> On Wed, Oct 02, 2024 at 08:13:15AM +0000, David Laight wrote:
> > From: 'Alan Stern'
> > > Sent: 01 October 2024 23:57
> > >
> > > On Tue, Oct 01, 2024 at 05:11:05PM +0000, David Laight wrote:
> > > > From: Alan Stern
> > > > > Sent: 30 September 2024 19:53
> > > > >
> > > > > On Mon, Sep 30, 2024 at 07:05:06PM +0200, Jonas Oberhauser wrote:
> > > > > >
> > > > > >
> > > > > > Am 9/30/2024 um 6:43 PM schrieb Alan Stern:
> > > > > > > On Mon, Sep 30, 2024 at 01:26:53PM +0200, Jonas Oberhauser wrote:
> > > > > > > >
> > > > > > > >
> > > > > > > > Am 9/28/2024 um 4:49 PM schrieb Alan Stern:
> > > > > > > >
> > > > > > > > I should also point out that it is not enough to prevent the compiler from
> > > > > > > > using @a instead of @b.
> > > > > > > >
> > > > > > > > It must also be prevented from assigning @b=@a, which it is often allowed to
> > > > > > > > do after finding @a==@b.
> > > > > > >
> > > > > > > Wouldn't that be a bug?
> > > > > >
> > > > > > That's why I said that it is often allowed to do it. In your case it
> > > > > > wouldn't, but it is often possible when a and b are non-atomic &
> > > > > > non-volatile (and haven't escaped, and I believe sometimes even then).
> > > > > >
> > > > > > It happens for example here with GCC 14.1.0 -O3:
> > > > > >
> > > > > > int fct_hide(void)
> > > > > > {
> > > > > >     int *a, *b;
> > > > > >
> > > > > >     do {
> > > > > >         a = READ_ONCE(p);
> > > > > >         asm volatile ("" : : : "memory");
> > > > > >         b = READ_ONCE(p);
> > > > > >     } while (a != b);
> > > > > >     OPTIMIZER_HIDE_VAR(b);
> > > > > >     return *b;
> > > > > > }
> > > > > >
> > > > > >
> > > > > >
> > > > > >         ldr     r1, [r2]
> > > > > >         ldr     r3, [r2]
> > > > > >         cmp     r1, r3
> > > > > >         bne     .L6
> > > > > >         mov     r3, r1   // nay...
> > > > >
> > > > > A totally unnecessary instruction, which accomplishes nothing other than
> > > > > to waste time, space, and energy.  But nonetheless, allowed -- I agree.
> > > > >
> > > > > The people in charge of GCC's optimizer might like to hear about this,
> > > > > if they're not already aware of it...
> > > > >
> > > > > >         ldr     r0, [r3] // yay!
> > > > > >         bx      lr
> > > > >
> > > > > One could argue that in this example the compiler _has_ used *a instead
> > > > > of *b.  However, such an argument would have more force if we had
> > > > > described what we are talking about more precisely.
> > > >
> > > > The 'mov r3, r1' has nothing to do with 'a'.
> > >
> > > What do you mean by that?  At this point in the program, a is the
> > > variable whose value is stored in r1 and b is the variable whose value
> > > is stored in r3.  "mov r3, r1" copies the value from r1 into r3 and is
> > > therefore equivalent to executing "b = a".  (That is why I said one
> > > could argue that the "return *b" statement uses the value of *a.)  Thus
> > > it very much does have something to do with "a".
> >
> > After the cmp and bne r1 and r3 have the same value.
> > The compiler tracks that and will use either register later.
> > That can never matter.
> 
> The whole point of this thread is that sometimes it _does_ matter.  Not
> on x86, but on weakly ordered architectures where using the wrong
> register will bypass a dependency and allow the CPU to speculatively
> load values earlier than the programmer wants it to.
> 
> > Remember the compiler tracks values (in pseudo/internal registers)
> > not variables.
> >
> > > > It is a more general problem that OPTIMISER_HIDE_VAR() pretty much
> > > > always ends up allocating a different internal 'register' for the
> > > > output and then allocating a separate physical rehgister.
> > >
> > > What output are you referring to?  Does OPTIMISER_HIDE_VAR() have an
> > > output?  If it does, the source program above ignores it, discarding any
> > > returned value.
> >
> > Look up OPTIMISER_HIDE_VAR(x) it basically x = f(x) where f() is
> > the identity operation:
> > 	asm ("" : "+r"(x))
> > I'll bet that gcc allocates a separate internal/pseudo register
> > for the result so wants to do y = f(x).
> > Probably generating y = x; y = f(y);
> > (The 'mov' might be after the asm, but I think that would get
> > optimised away - the listing file might help.)
> >
> > So here the compiler has just decided to reuse the register that
> > held the other of a/b for the extra temporary.
> 
> I think you've got this backward.  As mentioned above, a is originally
> in r1 and b is in r3.  The source says OPTIMIZER_HIDE_VAR(b), so you're
> saying that gcc should be copying r3 into a separate internal/pseudo
> register.  But instead it's copying r1.

I think I know what you are trying to do, and you just fail.
Whether something can work is another matter, but that code
can't ever work.

Inside if (a == b) the compiler will always use the same register
for references to a and b - because it knows they have the same value.

Possibly something like:
	c = b;
	OPTIMISER_HIDE_VAR(c);
	if (a == c) {
		*b
will ensure that there isn't a speculative load from *a.
You'll get at least one register-register move - but they are safe.
Otherwise you'll need to put the condition inside an asm block.

	David

> 
> Alan

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Alan Stern Oct. 3, 2024, 1:50 a.m. UTC | #30

On Wed, Oct 02, 2024 at 03:24:45PM +0000, David Laight wrote:
> I think I know what you are trying to do, and you just fail.
> Whether something can work is another matter, but that code
> can't ever work.
> 
> Inside if (a == b) the compiler will always use the same register
> for references to a and b - because it knows they have the same value.

According to the other people in this discussion who have actually tried 
using this code, it _does_ work (at least some of the time).

However, I'm not one of those people and so I leave it up to them to 
decide how to respond to this critique.

Alan

> Possibly something like:
> 	c = b;
> 	OPTIMISER_HIDE_VAR(c);
> 	if (a == c) {
> 		*b
> will ensure that there isn't a speculative load from *a.
> You'll get at least one register-register move - but they are safe.
> Otherwise you'll need to put the condition inside an asm block.
> 
> 	David

Mathieu Desnoyers Oct. 3, 2024, 1:23 p.m. UTC | #31

On 2024-10-03 03:50, 'Alan Stern' wrote:
> On Wed, Oct 02, 2024 at 03:24:45PM +0000, David Laight wrote:
>> I think I know what you are trying to do, and you just fail.
>> Whether something can work is another matter, but that code
>> can't ever work.
>>
>> Inside if (a == b) the compiler will always use the same register
>> for references to a and b - because it knows they have the same value.
> 
> According to the other people in this discussion who have actually tried
> using this code, it _does_ work (at least some of the time).
> 
> However, I'm not one of those people and so I leave it up to them to
> decide how to respond to this critique.

I suspect that David's comment is about this specific example that
was given in this leg of the email thread:

https://lore.kernel.org/lkml/[e-mail]/

> > > > > int fct_hide(void)
> > > > > > {
> > > > > >     int *a, *b;
> > > > > >
> > > > > >     do {
> > > > > >         a = READ_ONCE(p);
> > > > > >         asm volatile ("" : : : "memory");
> > > > > >         b = READ_ONCE(p);
> > > > > >     } while (a != b);
> > > > > >     OPTIMIZER_HIDE_VAR(b);
> > > > > >     return *b;
> > > > > > } 

This indeed cannot work because the hide var is done
on @b after it was compared with @a, so after the compiler
was free to use any of the registers due to the equality.

Another example that does *not* work is if we try to hide
vars on the inputs of the equality, and then proceed to do the
comparison on the resulting temporaries, e.g.:

int fct_hide(void)
{
      int *a, *b;

      do {
          a = READ_ONCE(p);
          asm volatile ("" : : : "memory");
          b = READ_ONCE(p);
      } while (OPTIMIZER_HIDE_VAR(a) != OPTIMIZER_HIDE_VAR(b));
      return *b;
}

The reason why this does *not* work is because the compiler is
free to use either temporaries for *b at the end, because they
were deemed identical.

What _does_ work however are the following two approaches:

1) Perform the equality check on the original variables, creating
new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
rest of their use, therefore making sure the pointer dereference
are not derived from versions of the variables which were compared
with another pointer. (as suggested by Boqun)

2) Perform the equality check on the versions resulting of hiding
both variables, making sure those versions of the variables are
not dereferenced afterwards. (as suggested by Linus)

Thanks,

Mathieu


> 
> Alan
> 
>> Possibly something like:
>> 	c = b;
>> 	OPTIMISER_HIDE_VAR(c);
>> 	if (a == c) {
>> 		*b
>> will ensure that there isn't a speculative load from *a.
>> You'll get at least one register-register move - but they are safe.
>> Otherwise you'll need to put the condition inside an asm block.
>>
>> 	David

David Laight Oct. 3, 2024, 5:07 p.m. UTC | #32

...
> What _does_ work however are the following two approaches:
> 
> 1) Perform the equality check on the original variables, creating
> new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
> rest of their use, therefore making sure the pointer dereference
> are not derived from versions of the variables which were compared
> with another pointer. (as suggested by Boqun)

If that is
	a1 = a; OPTIMISER_HIDE_VAR(a1);
	b1 = b; OPTIMISER_HIDE_BAR(b1);
	if (a != b}
		return;
	// code using a1 and b1
then can't the compiler first flip it to:
	if (a != b)
		return;
	a1 = a; OPTIMISER_HIDE_VAR(a1);
	b1 = b; OPTIMISER_HIDE_VAR(b1);
and then replace the last line with:
	b1 = a; OPTIMISER_HIDE_VAR(b1);
which isn't intended at all.
		
	
OTOH if you do:
	a1 = a; OPTIMISER_HIDE_VAR(a1);
	b1 = b; OPTIMISER_HIDE_VAR(b1);
	if (a1 != b1)
		return;
	// code using a and b
(which I think is)

> 2) Perform the equality check on the versions resulting of hiding
> both variables, making sure those versions of the variables are
> not dereferenced afterwards. (as suggested by Linus)

then the compiler can't possibly reverse the asm blocks.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Mathieu Desnoyers Oct. 3, 2024, 6 p.m. UTC | #33

On 2024-10-03 19:07, David Laight wrote:
> ...
>> What _does_ work however are the following two approaches:
>>
>> 1) Perform the equality check on the original variables, creating
>> new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
>> rest of their use, therefore making sure the pointer dereference
>> are not derived from versions of the variables which were compared
>> with another pointer. (as suggested by Boqun)
> 
> If that is
> 	a1 = a; OPTIMISER_HIDE_VAR(a1);
> 	b1 = b; OPTIMISER_HIDE_BAR(b1);
> 	if (a != b}
> 		return;
> 	// code using a1 and b1
> then can't the compiler first flip it to:
> 	if (a != b)
> 		return;
> 	a1 = a; OPTIMISER_HIDE_VAR(a1);
> 	b1 = b; OPTIMISER_HIDE_VAR(b1);
> and then replace the last line with:
> 	b1 = a; OPTIMISER_HIDE_VAR(b1);
> which isn't intended at all.

Good point, so I suspect Boqun's ADDRESS_EQ() suggestion did not work:

https://lore.kernel.org/lkml/ZvX12_1mK8983cXm@boqun-archlinux/
> 		
> 	
> OTOH if you do:
> 	a1 = a; OPTIMISER_HIDE_VAR(a1);
> 	b1 = b; OPTIMISER_HIDE_VAR(b1);
> 	if (a1 != b1)
> 		return;
> 	// code using a and b
> (which I think is)

This is in line with Linus' suggestion, which is the approach I
retained.

> 
>> 2) Perform the equality check on the versions resulting of hiding
>> both variables, making sure those versions of the variables are
>> not dereferenced afterwards. (as suggested by Linus)
> 
> then the compiler can't possibly reverse the asm blocks.

Indeed.

Thanks,

Mathieu

> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)

Jonas Oberhauser Oct. 7, 2024, 11:54 a.m. UTC | #34

Am 10/3/2024 um 3:23 PM schrieb Mathieu Desnoyers:
> What _does_ work however are the following two approaches:
> 
> 1) Perform the equality check on the original variables, creating
> new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
> rest of their use, therefore making sure the pointer dereference
> are not derived from versions of the variables which were compared
> with another pointer. (as suggested by Boqun)

This should not be guaranteed to work, because right after the 
comparison the compiler can do b=a, then it doesn't matter how much you 
hide afterwards.

However it might work if you escape the addresses of a and b first, in 
which case the compiler will not do b=a anymore, but it might force the 
compiler to put a and b on the stack, which has some performance impact.

> 
> 2) Perform the equality check on the versions resulting of hiding
> both variables, making sure those versions of the variables are
> not dereferenced afterwards. (as suggested by Linus)
> 


jonas

David Laight Oct. 7, 2024, 1:18 p.m. UTC | #35

From: Jonas Oberhauser
> Sent: 07 October 2024 12:55
> 
> Am 10/3/2024 um 3:23 PM schrieb Mathieu Desnoyers:
> > What _does_ work however are the following two approaches:
> >
> > 1) Perform the equality check on the original variables, creating
> > new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
> > rest of their use, therefore making sure the pointer dereference
> > are not derived from versions of the variables which were compared
> > with another pointer. (as suggested by Boqun)
> 
> This should not be guaranteed to work, because right after the
> comparison the compiler can do b=a, then it doesn't matter how much you
> hide afterwards.
> 
> However it might work if you escape the addresses of a and b first, in
> which case the compiler will not do b=a anymore, but it might force the
> compiler to put a and b on the stack, which has some performance impact.

Nope, as pointed out last week, the compiler can move the 'a == b'
check to before the OPTIMISER_HID_VAR() and then use the same register
for both of them.

> > 2) Perform the equality check on the versions resulting of hiding
> > both variables, making sure those versions of the variables are
> > not dereferenced afterwards. (as suggested by Linus)

That (and other things) could usefully use:
#define OPTIMISER_HIDE_VALUE(x) \
	({ __auto_type _x = x; OPTIMISER_HIDE_VAR(_x); _x; })
You'll almost certainly end up with a register-register move
even if 'x' isn't used afterwards.

The calling could just become:
	if (a == OPTIMISER_HIDE_VALUE(b) ...
since it is likely that you only care about one of the pointers.
(Actually isn't hiding one of them always enough?)

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Mathieu Desnoyers Oct. 7, 2024, 1:21 p.m. UTC | #36

On 2024-10-07 15:18, David Laight wrote:
> From: Jonas Oberhauser
>> Sent: 07 October 2024 12:55
>>
>> Am 10/3/2024 um 3:23 PM schrieb Mathieu Desnoyers:
>>> What _does_ work however are the following two approaches:
>>>
>>> 1) Perform the equality check on the original variables, creating
>>> new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
>>> rest of their use, therefore making sure the pointer dereference
>>> are not derived from versions of the variables which were compared
>>> with another pointer. (as suggested by Boqun)
>>
>> This should not be guaranteed to work, because right after the
>> comparison the compiler can do b=a, then it doesn't matter how much you
>> hide afterwards.
>>
>> However it might work if you escape the addresses of a and b first, in
>> which case the compiler will not do b=a anymore, but it might force the
>> compiler to put a and b on the stack, which has some performance impact.
> 
> Nope, as pointed out last week, the compiler can move the 'a == b'
> check to before the OPTIMISER_HID_VAR() and then use the same register
> for both of them.

Yes.

> 
>>> 2) Perform the equality check on the versions resulting of hiding
>>> both variables, making sure those versions of the variables are
>>> not dereferenced afterwards. (as suggested by Linus)
> 
> That (and other things) could usefully use:
> #define OPTIMISER_HIDE_VALUE(x) \
> 	({ __auto_type _x = x; OPTIMISER_HIDE_VAR(_x); _x; })
> You'll almost certainly end up with a register-register move
> even if 'x' isn't used afterwards.

Yes.

> 
> The calling could just become:
> 	if (a == OPTIMISER_HIDE_VALUE(b) ...
> since it is likely that you only care about one of the pointers.
> (Actually isn't hiding one of them always enough?)

Linus asked that we hide both inputs, otherwise it's really asking
for trouble in terms of API misuse.

Thanks,

Mathieu

> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)

Jonas Oberhauser Oct. 7, 2024, 2:59 p.m. UTC | #37

Am 10/7/2024 um 3:18 PM schrieb David Laight:
> From: Jonas Oberhauser
>> Sent: 07 October 2024 12:55
>>
>> Am 10/3/2024 um 3:23 PM schrieb Mathieu Desnoyers:
>>> What _does_ work however are the following two approaches:
>>>
>>> 1) Perform the equality check on the original variables, creating
>>> new versions (with OPTIMIZER_HIDE_VAR) of both variables for the
>>> rest of their use, therefore making sure the pointer dereference
>>> are not derived from versions of the variables which were compared
>>> with another pointer. (as suggested by Boqun)
>>
>> This should not be guaranteed to work, because right after the
>> comparison the compiler can do b=a, then it doesn't matter how much you
>> hide afterwards.
>>
>> However it might work if you escape the addresses of a and b first, in
>> which case the compiler will not do b=a anymore, but it might force the
>> compiler to put a and b on the stack, which has some performance impact.
> 
> Nope, as pointed out last week, the compiler can move the 'a == b'
> check to before the OPTIMISER_HID_VAR() and then use the same register
> for both of them.
> 

Since the addresses of a and b have escaped, I don't think it can still 
put them into the same register (or memory location).

Other threads could be temporarily modifying (inside the escape code) or 
concurrently reading (after the escape code) the two variables 
independently.

Something in the direction of

a = ...;
...
b = ...;

escape(&a);
escape(&b);
if (a == b) {
    OPTIMIZER_HIDE_VAR(b);
    *b;
}


Here doing b=a after a==b would (from the point of view of compiler) 
potentially introduce a data race.

As I pointed out earlier, the compiler might be able to prove that it is 
a benign data race though and theoretically still do b=a. But if you 
declare b as volatile on top...

Anyways, the ptr_eq way is much more obvious.

   jonas

Patch

diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index 2df665fa2964..f26705c267e8 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -186,6 +186,68 @@  void ftrace_likely_update(struct ftrace_likely_data *f, int val,
 	__asm__ ("" : "=r" (var) : "0" (var))
 #endif
 
+/*
+ * Compare two addresses while preserving the address dependencies for
+ * later use of the address. It should be used when comparing an address
+ * returned by rcu_dereference().
+ *
+ * This is needed to prevent the compiler CSE and SSA GVN optimizations
+ * from replacing the registers holding @a or @b based on their
+ * equality, which does not preserve address dependencies and allows the
+ * following misordering speculations:
+ *
+ * - If @b is a constant, the compiler can issue the loads which depend
+ *   on @a before loading @a.
+ * - If @b is a register populated by a prior load, weakly-ordered
+ *   CPUs can speculate loads which depend on @a before loading @a.
+ *
+ * The same logic applies with @a and @b swapped.
+ *
+ * Return value: true if pointers are equal, false otherwise.
+ *
+ * The compiler barrier() is ineffective at fixing this issue. It does
+ * not prevent the compiler CSE from losing the address dependency:
+ *
+ * int fct_2_volatile_barriers(void)
+ * {
+ *     int *a, *b;
+ *
+ *     do {
+ *         a = READ_ONCE(p);
+ *         asm volatile ("" : : : "memory");
+ *         b = READ_ONCE(p);
+ *     } while (a != b);
+ *     asm volatile ("" : : : "memory");  <-- barrier()
+ *     return *b;
+ * }
+ *
+ * With gcc 14.2 (arm64):
+ *
+ * fct_2_volatile_barriers:
+ *         adrp    x0, .LANCHOR0
+ *         add     x0, x0, :lo12:.LANCHOR0
+ * .L2:
+ *         ldr     x1, [x0]  <-- x1 populated by first load.
+ *         ldr     x2, [x0]
+ *         cmp     x1, x2
+ *         bne     .L2
+ *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
+ *         ret
+ *
+ * On weakly-ordered architectures, this lets CPU speculation use the
+ * result from the first load to speculate "ldr w0, [x1]" before
+ * "ldr x2, [x0]".
+ * Based on the RCU documentation, the control dependency does not
+ * prevent the CPU from speculating loads.
+ */
+static __always_inline
+int ptr_eq(const volatile void *a, const volatile void *b)
+{
+	OPTIMIZER_HIDE_VAR(a);
+	OPTIMIZER_HIDE_VAR(b);
+	return a == b;
+}
+
 #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
 
 /**