Message-ID: <20240929002428.38f37f54.gary@garyguo.net>
Date: Sun, 29 Sep 2024 00:24:28 +0100
From: Gary Guo <gary@...yguo.net>
To: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Linus Torvalds <torvalds@...ux-foundation.org>,
 linux-kernel@...r.kernel.org, Greg Kroah-Hartman
 <gregkh@...uxfoundation.org>, Sebastian Andrzej Siewior
 <bigeasy@...utronix.de>, "Paul E. McKenney" <paulmck@...nel.org>, Will
 Deacon <will@...nel.org>, Peter Zijlstra <peterz@...radead.org>, Boqun Feng
 <boqun.feng@...il.com>, Alan Stern <stern@...land.harvard.edu>, John Stultz
 <jstultz@...gle.com>, Neeraj Upadhyay <Neeraj.Upadhyay@....com>, Frederic
 Weisbecker <frederic@...nel.org>, Joel Fernandes <joel@...lfernandes.org>,
 Josh Triplett <josh@...htriplett.org>, Uladzislau Rezki <urezki@...il.com>,
 Steven Rostedt <rostedt@...dmis.org>, Lai Jiangshan
 <jiangshanlai@...il.com>, Zqiang <qiang.zhang1211@...il.com>, Ingo Molnar
 <mingo@...hat.com>, Waiman Long <longman@...hat.com>, Mark Rutland
 <mark.rutland@....com>, Thomas Gleixner <tglx@...utronix.de>, Vlastimil
 Babka <vbabka@...e.cz>, maged.michael@...il.com, Mateusz Guzik
 <mjguzik@...il.com>, Jonas Oberhauser <jonas.oberhauser@...weicloud.com>,
 rcu@...r.kernel.org, linux-mm@...ck.org, lkmm@...ts.linux.dev,
 github@...pov.com, llvm@...ts.linux.dev
Subject: Re: [PATCH 1/2] compiler.h: Introduce ptr_eq() to preserve address
 dependency

Cc: Nikita Popov <github@...pov.com>
Cc: llvm@...ts.linux.dev

On Sat, 28 Sep 2024 09:51:27 -0400
Mathieu Desnoyers <mathieu.desnoyers@...icios.com> 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 <torvalds@...ux-foundation.org>
> Suggested-by: Boqun Feng <boqun.feng@...il.com>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
> Reviewed-by: Boqun Feng <boqun.feng@...il.com>
> Acked-by: "Paul E. McKenney" <paulmck@...nel.org>
> Cc: Greg Kroah-Hartman <gregkh@...uxfoundation.org>
> Cc: Sebastian Andrzej Siewior <bigeasy@...utronix.de>
> Cc: "Paul E. McKenney" <paulmck@...nel.org>
> Cc: Will Deacon <will@...nel.org>
> Cc: Peter Zijlstra <peterz@...radead.org>
> Cc: Boqun Feng <boqun.feng@...il.com>
> Cc: Alan Stern <stern@...land.harvard.edu>
> Cc: John Stultz <jstultz@...gle.com>
> Cc: Neeraj Upadhyay <Neeraj.Upadhyay@....com>
> Cc: Linus Torvalds <torvalds@...ux-foundation.org>
> Cc: Boqun Feng <boqun.feng@...il.com>
> Cc: Frederic Weisbecker <frederic@...nel.org>
> Cc: Joel Fernandes <joel@...lfernandes.org>
> Cc: Josh Triplett <josh@...htriplett.org>
> Cc: Uladzislau Rezki <urezki@...il.com>
> Cc: Steven Rostedt <rostedt@...dmis.org>
> Cc: Lai Jiangshan <jiangshanlai@...il.com>
> Cc: Zqiang <qiang.zhang1211@...il.com>
> Cc: Ingo Molnar <mingo@...hat.com>
> Cc: Waiman Long <longman@...hat.com>
> Cc: Mark Rutland <mark.rutland@....com>
> Cc: Thomas Gleixner <tglx@...utronix.de>
> Cc: Vlastimil Babka <vbabka@...e.cz>
> Cc: maged.michael@...il.com
> Cc: Mateusz Guzik <mjguzik@...il.com>
> Cc: Gary Guo <gary@...yguo.net>
> Cc: Jonas Oberhauser <jonas.oberhauser@...weicloud.com>
> Cc: rcu@...r.kernel.org
> Cc: linux-mm@...ck.org
> Cc: lkmm@...ts.linux.dev
> ---
>  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__)
>  
>  /**

Powered by blists - more mailing lists