linux-kernel - Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 24 Mar 2020 17:20:45 +0100
From:   Jann Horn <jannh@...gle.com>
To:     Will Deacon <will@...nel.org>
Cc:     kernel list <linux-kernel@...r.kernel.org>,
        Eric Dumazet <edumazet@...gle.com>,
        Kees Cook <keescook@...omium.org>,
        Maddie Stone <maddiestone@...gle.com>,
        Marco Elver <elver@...gle.com>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        kernel-team <kernel-team@...roid.com>,
        Kernel Hardening <kernel-hardening@...ts.openwall.com>
Subject: Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

On Tue, Mar 24, 2020 at 4:37 PM Will Deacon <will@...nel.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.)