Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Date:   Tue, 24 Mar 2020 17:26:52 +0100
From:   Greg KH <greg@kroah.com>
To:     Jann Horn <jannh@google.com>
Cc:     Will Deacon <will@kernel.org>,
        kernel list <linux-kernel@vger.kernel.org>,
        Eric Dumazet <edumazet@google.com>,
        Kees Cook <keescook@chromium.org>,
        Maddie Stone <maddiestone@google.com>,
        Marco Elver <elver@google.com>,
        "Paul E . McKenney" <paulmck@kernel.org>,
        Peter Zijlstra <peterz@infradead.org>,
        Thomas Gleixner <tglx@linutronix.de>,
        kernel-team <kernel-team@android.com>,
        Kernel Hardening <kernel-hardening@lists.openwall.com>
Subject: Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with
 data_race()
Message-ID: <20200324162652.GA2518046@kroah.com>
References: <20200324153643.15527-1-will@kernel.org>
 <20200324153643.15527-4-will@kernel.org>
 <CAG48ez1yTbbXn__Kf0csf8=LCFL+0hR0EyHNZsryN8p=SsLp5Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAG48ez1yTbbXn__Kf0csf8=LCFL+0hR0EyHNZsryN8p=SsLp5Q@mail.gmail.com>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Tue, Mar 24, 2020 at 05:20:45PM +0100, Jann Horn wrote:
> On Tue, Mar 24, 2020 at 4:37 PM Will Deacon <will@kernel.org> wrote:
> > Some list predicates can be used locklessly even with the non-RCU list
> > implementations, since they effectively boil down to a test against
> > NULL. For example, checking whether or not a list is empty is safe even
> > in the presence of a concurrent, tearing write to the list head pointer.
> > Similarly, checking whether or not an hlist node has been hashed is safe
> > as well.
> >
> > Annotate these lockless list predicates with data_race() and READ_ONCE()
> > so that KCSAN and the compiler are aware of what's going on. The writer
> > side can then avoid having to use WRITE_ONCE() in the non-RCU
> > implementation.
> [...]
> >  static inline int list_empty(const struct list_head *head)
> >  {
> > -       return READ_ONCE(head->next) == head;
> > +       return data_race(READ_ONCE(head->next) == head);
> >  }
> [...]
> >  static inline int hlist_unhashed(const struct hlist_node *h)
> >  {
> > -       return !READ_ONCE(h->pprev);
> > +       return data_race(!READ_ONCE(h->pprev));
> >  }
> 
> This is probably valid in practice for hlist_unhashed(), which
> compares with NULL, as long as the most significant byte of all kernel
> pointers is non-zero; but I think list_empty() could realistically
> return false positives in the presence of a concurrent tearing store?
> This could break the following code pattern:
> 
> /* optimistic lockless check */
> if (!list_empty(&some_list)) {
>   /* slowpath */
>   mutex_lock(&some_mutex);
>   list_for_each(tmp, &some_list) {
>     ...
>   }
>   mutex_unlock(&some_mutex);
> }
> 
> (I'm not sure whether patterns like this appear commonly though.)


I would hope not as the list could go "empty" before the lock is
grabbed.  That pattern would be wrong.

thanks,

greg k-h