From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6F99CC433EF for ; Fri, 18 Feb 2022 16:30:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237926AbiBRQah (ORCPT ); Fri, 18 Feb 2022 11:30:37 -0500 Received: from mxb-00190b01.gslb.pphosted.com ([23.128.96.19]:42046 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237406AbiBRQad (ORCPT ); Fri, 18 Feb 2022 11:30:33 -0500 Received: from mail-lf1-x135.google.com (mail-lf1-x135.google.com [IPv6:2a00:1450:4864:20::135]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D10A217E97E for ; Fri, 18 Feb 2022 08:30:16 -0800 (PST) Received: by mail-lf1-x135.google.com with SMTP id j15so6427152lfe.11 for ; Fri, 18 Feb 2022 08:30:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=312lapKwafxiS2MTjPJeJeudqKLuqKmyJULFLFuRBRY=; b=CSnkaVF1tUHg9btEqNzLCWt4jG+0S94ZEQOsehqLGYk57c0fNxkCwHWdO/Xl1gKqem Gg/f14dX+7wWYzFYheYfoZyx2BS8B2SQDBdK7bNwuGG8Wv5LBxRoK4Q5NUSDBKT2nvFM wKwFZ03p+TxfPINCCCHya0gBtsi157a40o0HTkMT8nu7qTm4aDcDRkheX2TfAQ/1+atK wu1Zkvm9JQ3V6JnPaN40HGfEZRnJtlSSpqYwVFP1L5bzKmS2+CwVr5BcY445k9CIESu9 uJvguLH/z3ujJMwfYHdstVPHP27R/8BUj+sRdHT0ukT0oKwgznkO7rKokZLYn0r5/Yez Dylw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=312lapKwafxiS2MTjPJeJeudqKLuqKmyJULFLFuRBRY=; b=Cuxf8IKl4ZgskN2w3CNxCSGzTn+rsjsVtPYS8BQtbo56mg7oHFmKpd1dg1oS2vuSm+ J3g+hQmgm7anl2siOh7v2Ouu/qcVcHrkRJPOFhB+eOwqLS8XEa5mBRmRhkmOSIJZCKmh jog/wxsNIikcts+eYHhDfvUOdeFkBMbG2vhGe1vG5KUHa4Oz/Dd6DAQOhdlsIRIUZykU 55eUBM/EL/Vf6iBHc9+50Atbs/3MgDRn+yMwQ7M8y0RaBKMMxubRNihRT8DNVUz2CJC0 xWSONQAQhWMA0x2MvBqyBUI1qnnLas4/mqll1lp1iRr8Ihrjh8y3lmu3frU6gZgflj3N Z8qw== X-Gm-Message-State: AOAM530ho6icRkDxl4UUX2w1o4qUIbxcu6Cl9LqJ7tGOEX98nv6BjYWx lSqGGC1VAGz2FHYjFSoUpdyyUbwF9Lcg/bbL7FmR6g== X-Google-Smtp-Source: ABdhPJz5qGIkghROC2DmhXeLI1kRTQMiyE1CPE9Z6IYObgWq2hfondwj22K8KKj0a4/flTwBJ324HRBwNTjQT1617ZA= X-Received: by 2002:a05:6512:b83:b0:443:161a:e467 with SMTP id b3-20020a0565120b8300b00443161ae467mr5871108lfv.315.1645201814922; Fri, 18 Feb 2022 08:30:14 -0800 (PST) MIME-Version: 1.0 References: <20220217184829.1991035-1-jakobkoschel@gmail.com> <20220217184829.1991035-2-jakobkoschel@gmail.com> In-Reply-To: <20220217184829.1991035-2-jakobkoschel@gmail.com> From: Jann Horn Date: Fri, 18 Feb 2022 17:29:48 +0100 Message-ID: Subject: Re: [RFC PATCH 01/13] list: introduce speculative safe list_for_each_entry() To: Jakob Koschel Cc: Linus Torvalds , linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org, Greg Kroah-Hartman , Thomas Gleixner , Arnd Bergman , Andy Shevchenko , Andrew Morton , Kees Cook , Mike Rapoport , "Gustavo A. R. Silva" , Brian Johannesmeyer , Cristiano Giuffrida , "Bos, H.J." Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, Feb 17, 2022 at 7:48 PM 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 > Signed-off-by: Brian Johannesmeyer > Signed-off-by: Jakob Koschel 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); \ }) )