linux-kernel - Re: Confused about hlist_unhashed

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 for Android: free password hash cracker in your pocket

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

Message-ID: <CANn89iKmSBPKJGw--WaJJhCdu2wz2aq-ve+E8z=gfsYj6Zom_A@mail.gmail.com>
Date:   Fri, 31 Jan 2020 09:06:27 -0800
From:   Eric Dumazet <edumazet@...gle.com>
To:     Will Deacon <will@...nel.org>
Cc:     Thomas Gleixner <tglx@...utronix.de>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        "the arch/x86 maintainers" <x86@...nel.org>,
        LKML <linux-kernel@...r.kernel.org>,
        Peter Zijlstra <peterz@...radead.org>
Subject: Re: Confused about hlist_unhashed_lockless()

On Fri, Jan 31, 2020 at 8:57 AM Will Deacon <will@...nel.org> wrote:
>
> On Fri, Jan 31, 2020 at 08:48:05AM -0800, Eric Dumazet wrote:
> > On Fri, Jan 31, 2020 at 8:43 AM Will Deacon <will@...nel.org> wrote:
> > > I just ran into c54a2744497d ("list: Add hlist_unhashed_lockless()")
> > > but I'm a bit confused about what it's trying to achieve. It also seems
> > > to have been merged without any callers (even in -next) -- was that
> > > intentional?
> > >
> > > My main source of confusion is the lack of memory barriers. For example,
> > > if you look at the following pair of functions:
> > >
> > >
> > > static inline int hlist_unhashed_lockless(const struct hlist_node *h)
> > > {
> > >         return !READ_ONCE(h->pprev);
> > > }
> > >
> > > static inline void hlist_add_before(struct hlist_node *n,
> > >                                     struct hlist_node *next)
> > > {
> > >         WRITE_ONCE(n->pprev, next->pprev);
> > >         WRITE_ONCE(n->next, next);
> > >         WRITE_ONCE(next->pprev, &n->next);
> > >         WRITE_ONCE(*(n->pprev), n);
> > > }
> > >
> > >
> > > Then running these two concurrently on the same node means that
> > > hlist_unhashed_lockless() doesn't really tell you anything about whether
> > > or not the node is reachable in the list (i.e. there is another node
> > > with a next pointer pointing to it). In other words, I think all of
> > > these outcomes are permitted:
> > >
> > >         hlist_unhashed_lockless(n)      n reachable in list
> > >         0                               0 (No reordering)
> > >         0                               1 (No reordering)
> > >         1                               0 (No reordering)
> > >         1                               1 (Reorder first and last WRITE_ONCEs)
> > >
> > > So I must be missing some details about the use-case here. Please could
> > > you enlighten me? The RCU implementation permits only the first three
> > > outcomes afaict, why not use that and leave non-RCU hlist as it was?
> > >
> >
> > I guess the following has been lost :
>
> Thanks, although...
>
> > Author: Eric Dumazet <edumazet@...gle.com>
> > Date:   Thu Nov 7 11:23:14 2019 -0800
> >
> >     timer: use hlist_unhashed_lockless() in timer_pending()
> >
> >     timer_pending() is mostly used in lockless contexts.
>
> ... my point above still stands: the value returned by
> hlist_unhashed_lockless() doesn't tell you anything about whether or
> not the timer is reachable in the hlist or not. The comment above
> timer_pending() also states that:
>
>   | Callers must ensure serialization wrt. other operations done to
>   | this timer, e.g. interrupt contexts, or other CPUs on SMP.
>
> If that is intended to preclude list operations, shouldn't we use an
> RCU hlist instead of throwing {READ,WRITE}_ONCE() at the problem to
> shut the sanitiser up without actually fixing anything? :(


Sorry, but timer_pending() requires no serialization.

The only thing we need is a READ_ONCE() so that compiler is not allowed
to optimize out stuff like

loop() {
   if (timer_pending())
      something;
}