Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20220217184829.1991035-1-jakobkoschel@gmail.com>
 <20220217184829.1991035-2-jakobkoschel@gmail.com> <Yg6iCS0XZB6EtMP7@kroah.com>
In-Reply-To: <Yg6iCS0XZB6EtMP7@kroah.com>
From:   Jann Horn <jannh@google.com>
Date:   Fri, 18 Feb 2022 17:29:50 +0100
Message-ID: <CAG48ez2OgMThMd_EDA=ekFXy5=sWYmLuSshj1jiMvzpuy84M2Q@mail.gmail.com>
Subject: Re: [RFC PATCH 01/13] list: introduce speculative safe list_for_each_entry()
To:     Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc:     Jakob Koschel <jakobkoschel@gmail.com>,
        Linus Torvalds <torvalds@linux-foundation.org>,
        linux-kernel@vger.kernel.org, linux-arch@vger.kernel.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>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Thu, Feb 17, 2022 at 8:29 PM Greg Kroah-Hartman
<gregkh@linuxfoundation.org> 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.