From: Jakob <jakobkoschel@gmail.com>
To: Jann Horn <jannh@google.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
linux-arch <linux-arch@vger.kernel.org>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
Thomas Gleixner <tglx@linutronix.de>,
Arnd Bergman <arnd@arndb.de>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Andrew Morton <akpm@linux-foundation.org>,
Kees Cook <keescook@chromium.org>,
Mike Rapoport <rppt@kernel.org>,
"Gustavo A. R. Silva" <gustavo@embeddedor.com>,
Brian Johannesmeyer <bjohannesmeyer@gmail.com>,
Cristiano Giuffrida <c.giuffrida@vu.nl>,
"Bos, H.J." <h.j.bos@vu.nl>
Subject: Re: [RFC PATCH 01/13] list: introduce speculative safe list_for_each_entry()
Date: Wed, 23 Feb 2022 15:32:34 +0100 [thread overview]
Message-ID: <B50C7C66-0D24-48E7-9F04-F5BAD277DF7A@gmail.com> (raw)
In-Reply-To: <CAG48ez0m6V12dPVwZMQ9gi0ig7ELf_+KbLArE02SD5cYrZvH-w@mail.gmail.com>
> On 18. Feb 2022, at 17:29, Jann Horn <jannh@google.com> wrote:
>
> On Thu, Feb 17, 2022 at 7:48 PM Jakob Koschel <jakobkoschel@gmail.com> 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 <bjohannesmeyer@gmail.com>
>> Signed-off-by: Brian Johannesmeyer <bjohannesmeyer@gmail.com>
>> Signed-off-by: Jakob Koschel <jakobkoschel@gmail.com>
>
> 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.
next prev parent reply other threads:[~2022-02-23 14:32 UTC|newest]
Thread overview: 70+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-02-17 18:48 [RFC PATCH 00/13] Proposal for speculative safe list iterator Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 01/13] list: introduce speculative safe list_for_each_entry() Jakob Koschel
2022-02-17 19:29 ` Greg Kroah-Hartman
2022-02-18 16:29 ` Jann Horn
2022-02-18 16:29 ` Jann Horn
2022-02-23 14:32 ` Jakob [this message]
2022-02-19 19:44 ` Jann Horn
2022-02-17 18:48 ` [RFC PATCH 02/13] scripts: coccinelle: adapt to find list_for_each_entry nospec issues Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 03/13] usb: remove the usage of the list iterator after the loop Jakob Koschel
2022-02-17 19:28 ` Linus Torvalds
2022-02-23 14:13 ` Jakob
2022-02-23 14:16 ` Jakob
2022-02-24 10:33 ` Greg Kroah-Hartman
2022-02-24 17:56 ` Linus Torvalds
[not found] ` <6d191223d93249a98511177d4af08420@pexch012b.vu.local>
2022-02-24 10:46 ` Cristiano Giuffrida
2022-02-24 11:26 ` Greg Kroah-Hartman
2022-02-23 18:47 ` Linus Torvalds
2022-02-23 19:23 ` Linus Torvalds
2022-02-23 19:43 ` Linus Torvalds
2022-02-23 20:24 ` Arnd Bergmann
2022-02-23 20:43 ` Linus Torvalds
2022-02-23 20:48 ` Arnd Bergmann
2022-02-23 21:53 ` Linus Torvalds
2022-02-24 16:04 ` Nathan Chancellor
2022-02-23 20:54 ` Linus Torvalds
2022-02-23 22:21 ` David Laight
2022-02-25 21:36 ` Uecker, Martin
2022-02-25 22:02 ` Linus Torvalds
2022-02-26 1:21 ` Martin Uecker
2022-02-27 18:12 ` Miguel Ojeda
2022-02-28 7:08 ` Martin Uecker
2022-02-28 13:49 ` Miguel Ojeda
2022-03-01 20:26 ` Linus Torvalds
2022-03-02 7:27 ` Martin Uecker
2022-02-26 12:42 ` Segher Boessenkool
2022-02-26 22:14 ` Arnd Bergmann
2022-02-26 23:03 ` Linus Torvalds
2022-02-27 1:19 ` Segher Boessenkool
2022-02-27 1:09 ` Segher Boessenkool
2022-02-27 7:10 ` David Laight
2022-02-27 11:32 ` Segher Boessenkool
2022-02-27 18:09 ` Miguel Ojeda
2022-02-27 20:17 ` Segher Boessenkool
2022-02-27 21:04 ` Linus Torvalds
2022-02-28 6:15 ` David Laight
2022-02-27 22:43 ` Miguel Ojeda
2022-02-27 21:28 ` Arnd Bergmann
2022-02-27 22:43 ` Segher Boessenkool
2022-02-17 18:48 ` [RFC PATCH 04/13] vfio/mdev: " Jakob Koschel
2022-02-18 15:12 ` Jason Gunthorpe
2022-02-23 14:18 ` Jakob
2022-02-23 19:06 ` Linus Torvalds
2022-02-23 19:12 ` Jason Gunthorpe
2022-02-23 19:31 ` Linus Torvalds
2022-02-23 20:15 ` Jakob
2022-02-23 20:22 ` Linus Torvalds
2022-02-23 22:08 ` Jakob
2022-02-23 20:19 ` Rasmus Villemoes
2022-02-23 20:34 ` Linus Torvalds
2022-02-17 18:48 ` [RFC PATCH 05/13] drivers/perf: " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 06/13] ARM: mmp: " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 07/13] udp_tunnel: " Jakob Koschel
2022-02-23 20:00 ` Christophe JAILLET
2022-02-24 6:20 ` Dan Carpenter
2022-02-17 18:48 ` [RFC PATCH 08/13] net: dsa: future proof usage of " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 09/13] drbd: " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 10/13] powerpc/spufs: " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 11/13] ath6kl: remove use " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 12/13] staging: greybus: audio: Remove usage " Jakob Koschel
2022-02-17 18:48 ` [RFC PATCH 13/13] scsi: mpt3sas: comment about invalid usage of the list iterator Jakob Koschel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=B50C7C66-0D24-48E7-9F04-F5BAD277DF7A@gmail.com \
--to=jakobkoschel@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=arnd@arndb.de \
--cc=bjohannesmeyer@gmail.com \
--cc=c.giuffrida@vu.nl \
--cc=gregkh@linuxfoundation.org \
--cc=gustavo@embeddedor.com \
--cc=h.j.bos@vu.nl \
--cc=jannh@google.com \
--cc=keescook@chromium.org \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=rppt@kernel.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).