Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

[Jann Horn]

On Tue, Mar 24, 2020 at 5:26 PM Greg KH <greg@xxxxxxxxx> wrote:
> 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@xxxxxxxxxx> 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.

If the list becomes empty in between, the loop just iterates over
nothing, and the effect is no different from what you'd get if you had
bailed out before. But sure, you have to be aware that that can
happen.