list_for_each_entry() selects either the correct value (pos) or a safe
value for the additional mispredicted iteration (NULL) for the list
iterator.
list_for_each_entry() calls select_nospec(), which performs
a branch-less select.
On x86, this select is performed via a cmov. Otherwise, it's performed
via various shift/mask/etc. operations.
Kasper Acknowledgements: Jakob Koschel, Brian Johannesmeyer, Kaveh
Razavi, Herbert Bos, Cristiano Giuffrida from the VUSec group at VU
Amsterdam.
Co-developed-by: Brian Johannesmeyer <[email protected]>
Signed-off-by: Brian Johannesmeyer <[email protected]>
Signed-off-by: Jakob Koschel <[email protected]>
---
arch/x86/include/asm/barrier.h | 12 ++++++++++++
include/linux/list.h | 3 ++-
include/linux/nospec.h | 16 ++++++++++++++++
3 files changed, 30 insertions(+), 1 deletion(-)
diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h
index 35389b2af88e..722797ad74e2 100644
--- a/arch/x86/include/asm/barrier.h
+++ b/arch/x86/include/asm/barrier.h
@@ -48,6 +48,18 @@ static inline unsigned long array_index_mask_nospec(unsigned long index,
/* Override the default implementation from linux/nospec.h. */
#define array_index_mask_nospec array_index_mask_nospec
+/* Override the default implementation from linux/nospec.h. */
+#define select_nospec(cond, exptrue, expfalse) \
+({ \
+ typeof(exptrue) _out = (exptrue); \
+ \
+ asm volatile("test %1, %1\n\t" \
+ "cmove %2, %0" \
+ : "+r" (_out) \
+ : "r" (cond), "r" (expfalse)); \
+ _out; \
+})
+
/* Prevent speculative execution past this barrier. */
#define barrier_nospec() alternative("", "lfence", X86_FEATURE_LFENCE_RDTSC)
diff --git a/include/linux/list.h b/include/linux/list.h
index dd6c2041d09c..1a1b39fdd122 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -636,7 +636,8 @@ static inline void list_splice_tail_init(struct list_head *list,
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
- !list_entry_is_head(pos, head, member); \
+ ({ bool _cond = !list_entry_is_head(pos, head, member); \
+ pos = select_nospec(_cond, pos, NULL); _cond; }); \
pos = list_next_entry(pos, member))
/**
diff --git a/include/linux/nospec.h b/include/linux/nospec.h
index c1e79f72cd89..ca8ed81e4f9e 100644
--- a/include/linux/nospec.h
+++ b/include/linux/nospec.h
@@ -67,4 +67,20 @@ int arch_prctl_spec_ctrl_set(struct task_struct *task, unsigned long which,
/* Speculation control for seccomp enforced mitigation */
void arch_seccomp_spec_mitigate(struct task_struct *task);
+/**
+ * select_nospec - select a value without using a branch; equivalent to:
+ * cond ? exptrue : expfalse;
+ */
+#ifndef select_nospec
+#define select_nospec(cond, exptrue, expfalse) \
+({ \
+ unsigned long _t = (unsigned long) (exptrue); \
+ unsigned long _f = (unsigned long) (expfalse); \
+ unsigned long _c = (unsigned long) (cond); \
+ OPTIMIZER_HIDE_VAR(_c); \
+ unsigned long _m = -((_c | -_c) >> (BITS_PER_LONG - 1)); \
+ (typeof(exptrue)) ((_t & _m) | (_f & ~_m)); \
+})
+#endif
+
#endif /* _LINUX_NOSPEC_H */
--
2.25.1
On Thu, Feb 17, 2022 at 07:48:17PM +0100, Jakob Koschel wrote:
> list_for_each_entry() selects either the correct value (pos) or a safe
> value for the additional mispredicted iteration (NULL) for the list
> iterator.
> list_for_each_entry() calls select_nospec(), which performs
> a branch-less select.
>
> On x86, this select is performed via a cmov. Otherwise, it's performed
> via various shift/mask/etc. operations.
>
> Kasper Acknowledgements: Jakob Koschel, Brian Johannesmeyer, Kaveh
> Razavi, Herbert Bos, Cristiano Giuffrida from the VUSec group at VU
> Amsterdam.
>
> Co-developed-by: Brian Johannesmeyer <[email protected]>
> Signed-off-by: Brian Johannesmeyer <[email protected]>
> Signed-off-by: Jakob Koschel <[email protected]>
> ---
> arch/x86/include/asm/barrier.h | 12 ++++++++++++
> include/linux/list.h | 3 ++-
> include/linux/nospec.h | 16 ++++++++++++++++
> 3 files changed, 30 insertions(+), 1 deletion(-)
>
> diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h
> index 35389b2af88e..722797ad74e2 100644
> --- a/arch/x86/include/asm/barrier.h
> +++ b/arch/x86/include/asm/barrier.h
> @@ -48,6 +48,18 @@ static inline unsigned long array_index_mask_nospec(unsigned long index,
> /* Override the default implementation from linux/nospec.h. */
> #define array_index_mask_nospec array_index_mask_nospec
>
> +/* Override the default implementation from linux/nospec.h. */
> +#define select_nospec(cond, exptrue, expfalse) \
> +({ \
> + typeof(exptrue) _out = (exptrue); \
> + \
> + asm volatile("test %1, %1\n\t" \
> + "cmove %2, %0" \
> + : "+r" (_out) \
> + : "r" (cond), "r" (expfalse)); \
> + _out; \
> +})
> +
> /* Prevent speculative execution past this barrier. */
> #define barrier_nospec() alternative("", "lfence", X86_FEATURE_LFENCE_RDTSC)
>
> diff --git a/include/linux/list.h b/include/linux/list.h
> index dd6c2041d09c..1a1b39fdd122 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -636,7 +636,8 @@ static inline void list_splice_tail_init(struct list_head *list,
> */
> #define list_for_each_entry(pos, head, member) \
> for (pos = list_first_entry(head, typeof(*pos), member); \
> - !list_entry_is_head(pos, head, member); \
> + ({ bool _cond = !list_entry_is_head(pos, head, member); \
> + pos = select_nospec(_cond, pos, NULL); _cond; }); \
> pos = list_next_entry(pos, member))
>
You are not "introducing" a new macro for this, you are modifying the
existing one such that all users of it now have the select_nospec() call
in it.
Is that intentional? This is going to hit a _lot_ of existing entries
that probably do not need it at all.
Why not just create list_for_each_entry_nospec()?
thanks,
greg k-h
On Thu, Feb 17, 2022 at 7:48 PM Jakob Koschel <[email protected]> wrote:
> list_for_each_entry() selects either the correct value (pos) or a safe
> value for the additional mispredicted iteration (NULL) for the list
> iterator.
> list_for_each_entry() calls select_nospec(), which performs
> a branch-less select.
>
> On x86, this select is performed via a cmov. Otherwise, it's performed
> via various shift/mask/etc. operations.
>
> Kasper Acknowledgements: Jakob Koschel, Brian Johannesmeyer, Kaveh
> Razavi, Herbert Bos, Cristiano Giuffrida from the VUSec group at VU
> Amsterdam.
>
> Co-developed-by: Brian Johannesmeyer <[email protected]>
> Signed-off-by: Brian Johannesmeyer <[email protected]>
> Signed-off-by: Jakob Koschel <[email protected]>
Yeah, I think this is the best way to do this without deeply intrusive
changes to how lists are represented in memory.
Some notes on the specific implementation:
> arch/x86/include/asm/barrier.h | 12 ++++++++++++
> include/linux/list.h | 3 ++-
> include/linux/nospec.h | 16 ++++++++++++++++
> 3 files changed, 30 insertions(+), 1 deletion(-)
>
> diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h
> index 35389b2af88e..722797ad74e2 100644
> --- a/arch/x86/include/asm/barrier.h
> +++ b/arch/x86/include/asm/barrier.h
> @@ -48,6 +48,18 @@ static inline unsigned long array_index_mask_nospec(unsigned long index,
> /* Override the default implementation from linux/nospec.h. */
> #define array_index_mask_nospec array_index_mask_nospec
>
> +/* Override the default implementation from linux/nospec.h. */
> +#define select_nospec(cond, exptrue, expfalse) \
> +({ \
> + typeof(exptrue) _out = (exptrue); \
> + \
> + asm volatile("test %1, %1\n\t" \
This shouldn't need "volatile", because it is only necessary if _out
is actually used. Using "volatile" here could prevent optimizing out
useless code. OPTIMIZER_HIDE_VAR() also doesn't use "volatile".
> + "cmove %2, %0" \
> + : "+r" (_out) \
> + : "r" (cond), "r" (expfalse)); \
> + _out; \
> +})
I guess the idea is probably to also add code like this for other
important architectures, in particular arm64?
It might also be a good idea to rename the arch-overridable macro to
something like "arch_select_nospec" and then have a wrapper macro in
include/linux/nospec.h that takes care of type safety issues.
The current definition of the macro doesn't warn if you pass in
incompatible pointer types, like this:
int *bogus_pointer_mix(int cond, int *a, long *b) {
return select_nospec(cond, a, b);
}
and if you pass in integers of different sizes, it may silently
truncate to the size of the smaller one - this C code:
long wrong_int_conversion(int cond, int a, long b) {
return select_nospec(cond, a, b);
}
generates this assembly:
wrong_int_conversion:
test %edi, %edi
cmove %rdx, %esi
movslq %esi, %rax
ret
It might be a good idea to add something like a
static_assert(__same_type(...), ...) to protect against that.
> /* Prevent speculative execution past this barrier. */
> #define barrier_nospec() alternative("", "lfence", X86_FEATURE_LFENCE_RDTSC)
>
> diff --git a/include/linux/list.h b/include/linux/list.h
> index dd6c2041d09c..1a1b39fdd122 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -636,7 +636,8 @@ static inline void list_splice_tail_init(struct list_head *list,
> */
> #define list_for_each_entry(pos, head, member) \
> for (pos = list_first_entry(head, typeof(*pos), member); \
> - !list_entry_is_head(pos, head, member); \
> + ({ bool _cond = !list_entry_is_head(pos, head, member); \
> + pos = select_nospec(_cond, pos, NULL); _cond; }); \
> pos = list_next_entry(pos, member))
I wonder if it'd look nicer to write it roughly like this:
#define NOSPEC_TYPE_CHECK(_guarded_var, _cond) \
({ \
bool __cond = (_cond); \
typeof(_guarded_var) *__guarded_var = &(_guarded_var); \
*__guarded_var = select_nospec(__cond, *__guarded_var, NULL); \
__cond; \
})
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
NOSPEC_TYPE_CHECK(head, !list_entry_is_head(pos, head, member)); \
pos = list_next_entry(pos, member))
I think having a NOSPEC_TYPE_CHECK() like this makes it semantically
clearer, and easier to add in other places? But I don't know if the
others agree...
> /**
> diff --git a/include/linux/nospec.h b/include/linux/nospec.h
> index c1e79f72cd89..ca8ed81e4f9e 100644
> --- a/include/linux/nospec.h
> +++ b/include/linux/nospec.h
> @@ -67,4 +67,20 @@ int arch_prctl_spec_ctrl_set(struct task_struct *task, unsigned long which,
> /* Speculation control for seccomp enforced mitigation */
> void arch_seccomp_spec_mitigate(struct task_struct *task);
>
> +/**
> + * select_nospec - select a value without using a branch; equivalent to:
> + * cond ? exptrue : expfalse;
> + */
> +#ifndef select_nospec
> +#define select_nospec(cond, exptrue, expfalse) \
> +({ \
> + unsigned long _t = (unsigned long) (exptrue); \
> + unsigned long _f = (unsigned long) (expfalse); \
> + unsigned long _c = (unsigned long) (cond); \
> + OPTIMIZER_HIDE_VAR(_c); \
> + unsigned long _m = -((_c | -_c) >> (BITS_PER_LONG - 1)); \
> + (typeof(exptrue)) ((_t & _m) | (_f & ~_m)); \
> +})
> +#endif
(As a sidenote, it might be easier to implement a conditional zeroing
primitive than a generic conditional select primitive if that's all
you need, something like:
#define cond_nullptr_nospec(_cond, _exp) \
({ \
unsigned long __exp = (unsigned long)(_exp); \
unsigned long _mask = 0UL - !(_cond); \
OPTIMIZER_HIDE_VAR(_mask); \
(typeof(_exp)) (_mask & __exp); \
})
)
On Thu, Feb 17, 2022 at 8:29 PM Greg Kroah-Hartman
<[email protected]> wrote:
> On Thu, Feb 17, 2022 at 07:48:17PM +0100, Jakob Koschel wrote:
> > list_for_each_entry() selects either the correct value (pos) or a safe
> > value for the additional mispredicted iteration (NULL) for the list
> > iterator.
> > list_for_each_entry() calls select_nospec(), which performs
> > a branch-less select.
[...]
> > #define list_for_each_entry(pos, head, member) \
> > for (pos = list_first_entry(head, typeof(*pos), member); \
> > - !list_entry_is_head(pos, head, member); \
> > + ({ bool _cond = !list_entry_is_head(pos, head, member); \
> > + pos = select_nospec(_cond, pos, NULL); _cond; }); \
> > pos = list_next_entry(pos, member))
> >
>
> You are not "introducing" a new macro for this, you are modifying the
> existing one such that all users of it now have the select_nospec() call
> in it.
>
> Is that intentional? This is going to hit a _lot_ of existing entries
> that probably do not need it at all.
>
> Why not just create list_for_each_entry_nospec()?
My understanding is that almost all uses of `list_for_each_entry()`
currently create type-confused "pos" pointers when they terminate.
(As a sidenote, I've actually seen this lead to a bug in some
out-of-tree code in the past, where someone had a construct like this:
list_for_each_entry(element, ...) {
if (...)
break; /* found the element we were looking for */
}
/* use element here */
and then got a "real" type confusion bug from that when no matching
element was found.)
*Every time* you have a list_for_each_entry() iteration over some list
where the list_head that you start from is not embedded in the same
struct as the element list_heads (which is the normal case), and you
don't break from the iteration early, a bogus type-confused pointer
(which might not even be part of the same object as the real list
head, but instead some random out-of-bounds memory in front of it) is
assigned to "pos" (which I think is probably already a violation of
the C standard, but whatever), and this means that almost every
list_for_each_entry() loop ends with a branch that, when
misspeculated, leads to speculative accesses to a type-confused
pointer.
And once you're speculatively accessing type-confused pointers, and
especially if you start writing to them or loading more pointers from
them, it's really hard to reason about what might happen, just like
with "normal" type confusion bugs.
If we don't want to keep this performance hit, then in the long term
it might be a good idea to refactor away the (hideous) idea that the
head of a list and its elements are exactly the same type and
everything's just one big circular thing. Then we could change the
data structures so that this speculative confusion can't happen
anymore and avoid this explicit speculation avoidance on list
iteration.
But for now, I think we probably need this.
On Thu, Feb 17, 2022 at 7:48 PM Jakob Koschel <[email protected]> wrote:
> list_for_each_entry() selects either the correct value (pos) or a safe
> value for the additional mispredicted iteration (NULL) for the list
> iterator.
> list_for_each_entry() calls select_nospec(), which performs
> a branch-less select.
>
> On x86, this select is performed via a cmov. Otherwise, it's performed
> via various shift/mask/etc. operations.
[...]
> #define list_for_each_entry(pos, head, member) \
> for (pos = list_first_entry(head, typeof(*pos), member); \
> - !list_entry_is_head(pos, head, member); \
> + ({ bool _cond = !list_entry_is_head(pos, head, member); \
> + pos = select_nospec(_cond, pos, NULL); _cond; }); \
> pos = list_next_entry(pos, member))
Actually I do have one ugly question about this:
Is NULL a good/safe choice here?
We already know that CPUs try very aggressively to do store-to-load
forwarding. Until now, my mental model of store-to-load forwarding was
basically: "The CPU has to guess whether the linear addresses will be
the same, and once it knows the linear addresses, it can verify
whether that guess was correct."
But of course that can't really be the whole mechanism, because many
architectures guarantee that if you access the same physical page
through multiple linear addresses, everything stays coherent. So I'm
wondering: Are there basically two stages of speculation based on
address guesses? A first stage where the CPU guesses whether the
linear addresses are the same, and a second stage where it assumes
that different linear addresses also map to different physical
addresses, or something like that?
And so, if we don't have a TLB entry for NULL, and we misspeculate
through a speculative write to an object of type A at NULL and then a
speculative read (at the same offset) from an object of type B at
NULL, will we get speculative type confusion through the nonexistent
object at NULL that lasts until either the branches are resolved or
the page walk for NULL reports back that there is no page at NULL?
(Also, it's been known for a long time that speculative accesses to
NULL can be a performance problem, too:
https://lwn.net/Articles/444336/)
So I'm wondering whether, on 64-bit architectures that have canonical
address bits, it would be safer and also reduce the amount of useless
pagetable walks to try to butcher up the canonical bits of the address
somehow so that the CPU can quickly see that the access is bogus,
without potentially having to do a pagetable walk first.
> On 18. Feb 2022, at 17:29, Jann Horn <[email protected]> wrote:
>
> On Thu, Feb 17, 2022 at 7:48 PM Jakob Koschel <[email protected]> wrote:
>> list_for_each_entry() selects either the correct value (pos) or a safe
>> value for the additional mispredicted iteration (NULL) for the list
>> iterator.
>> list_for_each_entry() calls select_nospec(), which performs
>> a branch-less select.
>>
>> On x86, this select is performed via a cmov. Otherwise, it's performed
>> via various shift/mask/etc. operations.
>>
>> Kasper Acknowledgements: Jakob Koschel, Brian Johannesmeyer, Kaveh
>> Razavi, Herbert Bos, Cristiano Giuffrida from the VUSec group at VU
>> Amsterdam.
>>
>> Co-developed-by: Brian Johannesmeyer <[email protected]>
>> Signed-off-by: Brian Johannesmeyer <[email protected]>
>> Signed-off-by: Jakob Koschel <[email protected]>
>
> Yeah, I think this is the best way to do this without deeply intrusive
> changes to how lists are represented in memory.
>
> Some notes on the specific implementation:
>
>> arch/x86/include/asm/barrier.h | 12 ++++++++++++
>> include/linux/list.h | 3 ++-
>> include/linux/nospec.h | 16 ++++++++++++++++
>> 3 files changed, 30 insertions(+), 1 deletion(-)
>>
>> diff --git a/arch/x86/include/asm/barrier.h b/arch/x86/include/asm/barrier.h
>> index 35389b2af88e..722797ad74e2 100644
>> --- a/arch/x86/include/asm/barrier.h
>> +++ b/arch/x86/include/asm/barrier.h
>> @@ -48,6 +48,18 @@ static inline unsigned long array_index_mask_nospec(unsigned long index,
>> /* Override the default implementation from linux/nospec.h. */
>> #define array_index_mask_nospec array_index_mask_nospec
>>
>> +/* Override the default implementation from linux/nospec.h. */
>> +#define select_nospec(cond, exptrue, expfalse) \
>> +({ \
>> + typeof(exptrue) _out = (exptrue); \
>> + \
>> + asm volatile("test %1, %1\n\t" \
>
> This shouldn't need "volatile", because it is only necessary if _out
> is actually used. Using "volatile" here could prevent optimizing out
> useless code. OPTIMIZER_HIDE_VAR() also doesn't use "volatile".
>
>> + "cmove %2, %0" \
>> + : "+r" (_out) \
>> + : "r" (cond), "r" (expfalse)); \
>> + _out; \
>> +})
>
> I guess the idea is probably to also add code like this for other
> important architectures, in particular arm64?
yes indeed, with a fallback of using the shifting/masking mechanism for
other archs.
>
>
> It might also be a good idea to rename the arch-overridable macro to
> something like "arch_select_nospec" and then have a wrapper macro in
> include/linux/nospec.h that takes care of type safety issues.
>
> The current definition of the macro doesn't warn if you pass in
> incompatible pointer types, like this:
>
> int *bogus_pointer_mix(int cond, int *a, long *b) {
> return select_nospec(cond, a, b);
> }
>
> and if you pass in integers of different sizes, it may silently
> truncate to the size of the smaller one - this C code:
>
> long wrong_int_conversion(int cond, int a, long b) {
> return select_nospec(cond, a, b);
> }
>
> generates this assembly:
>
> wrong_int_conversion:
> test %edi, %edi
> cmove %rdx, %esi
> movslq %esi, %rax
> ret
>
> It might be a good idea to add something like a
> static_assert(__same_type(...), ...) to protect against that.
These are good points, thank you for your input. Will be good to incorporate.
>
>> /* Prevent speculative execution past this barrier. */
>> #define barrier_nospec() alternative("", "lfence", X86_FEATURE_LFENCE_RDTSC)
>>
>> diff --git a/include/linux/list.h b/include/linux/list.h
>> index dd6c2041d09c..1a1b39fdd122 100644
>> --- a/include/linux/list.h
>> +++ b/include/linux/list.h
>> @@ -636,7 +636,8 @@ static inline void list_splice_tail_init(struct list_head *list,
>> */
>> #define list_for_each_entry(pos, head, member) \
>> for (pos = list_first_entry(head, typeof(*pos), member); \
>> - !list_entry_is_head(pos, head, member); \
>> + ({ bool _cond = !list_entry_is_head(pos, head, member); \
>> + pos = select_nospec(_cond, pos, NULL); _cond; }); \
>> pos = list_next_entry(pos, member))
>
> I wonder if it'd look nicer to write it roughly like this:
>
> #define NOSPEC_TYPE_CHECK(_guarded_var, _cond) \
> ({ \
> bool __cond = (_cond); \
> typeof(_guarded_var) *__guarded_var = &(_guarded_var); \
> *__guarded_var = select_nospec(__cond, *__guarded_var, NULL); \
> __cond; \
> })
>
> #define list_for_each_entry(pos, head, member) \
> for (pos = list_first_entry(head, typeof(*pos), member); \
> NOSPEC_TYPE_CHECK(head, !list_entry_is_head(pos, head, member)); \
> pos = list_next_entry(pos, member))
>
> I think having a NOSPEC_TYPE_CHECK() like this makes it semantically
> clearer, and easier to add in other places? But I don't know if the
> others agree...
That sounds like a good idea. I wonder if the pointer and dereference in
NOSPEC_TYPE_CHECK() simply get optimized away. Or why you can't simply
use _guarded_var directly instead of a pointer to it.
>
>> /**
>> diff --git a/include/linux/nospec.h b/include/linux/nospec.h
>> index c1e79f72cd89..ca8ed81e4f9e 100644
>> --- a/include/linux/nospec.h
>> +++ b/include/linux/nospec.h
>> @@ -67,4 +67,20 @@ int arch_prctl_spec_ctrl_set(struct task_struct *task, unsigned long which,
>> /* Speculation control for seccomp enforced mitigation */
>> void arch_seccomp_spec_mitigate(struct task_struct *task);
>>
>> +/**
>> + * select_nospec - select a value without using a branch; equivalent to:
>> + * cond ? exptrue : expfalse;
>> + */
>> +#ifndef select_nospec
>> +#define select_nospec(cond, exptrue, expfalse) \
>> +({ \
>> + unsigned long _t = (unsigned long) (exptrue); \
>> + unsigned long _f = (unsigned long) (expfalse); \
>> + unsigned long _c = (unsigned long) (cond); \
>> + OPTIMIZER_HIDE_VAR(_c); \
>> + unsigned long _m = -((_c | -_c) >> (BITS_PER_LONG - 1)); \
>> + (typeof(exptrue)) ((_t & _m) | (_f & ~_m)); \
>> +})
>> +#endif
>
> (As a sidenote, it might be easier to implement a conditional zeroing
> primitive than a generic conditional select primitive if that's all
> you need, something like:
>
> #define cond_nullptr_nospec(_cond, _exp) \
> ({ \
> unsigned long __exp = (unsigned long)(_exp); \
> unsigned long _mask = 0UL - !(_cond); \
> OPTIMIZER_HIDE_VAR(_mask); \
> (typeof(_exp)) (_mask & __exp); \
> })
>
> )
Ah yes, if NULL is actually the value to choose, this might be good enough.