Re: [PATCH v2 4/4] futex: Avoid taking hb lock if nothing to wakeup

[Peter Zijlstra <peterz@infradead.org>]

On Tue, Dec 10, 2013 at 09:22:08AM -0800, Davidlohr Bueso wrote:
> On Tue, 2013-12-10 at 17:57 +0100, Peter Zijlstra wrote:
> > > @@ -106,24 +108,40 @@
> > >   * This would cause the waiter on CPU 0 to wait forever because it
> > >   * missed the transition of the user space value from val to newval
> > >   * and the waker did not find the waiter in the hash bucket queue.
> > > + * The correct serialization ensures that a waiter either observes
> > > + * the changed user space value before blocking or is woken by a
> > > + * concurrent waker:
> > >   *
> > >   * CPU 0                               CPU 1
> > >   * val = *futex;
> > >   * sys_futex(WAIT, futex, val);
> > >   *   futex_wait(futex, val);
> > > + *
> > > + *   mb(); <-- paired with ------
> > > + *                              |
> > > + *   lock(hash_bucket(futex));  |
> > > + *                              |
> > > + *   uval = *futex;             |
> > > + *                              |        *futex = newval;
> > > + *                              |        sys_futex(WAKE, futex);
> > > + *                              |          futex_wake(futex);
> > > + *                              |
> > > + *                              -------->   mb();
> > >   *   if (uval == val)
> > > + *     queue();
> > >   *     unlock(hash_bucket(futex));
> > > + *     schedule();                         if (!queue_empty())
> > > + *                                           lock(hash_bucket(futex));
> > > + *                                           wake_waiters(futex);
> > > + *                                           unlock(hash_bucket(futex));
> > > + *
> > > + * The length of the list is tracked with atomic ops (hb->waiters),
> > > + * providing the necessary memory barriers for the waiters. For the
> > > + * waker side, however, we rely on get_futex_key_refs(), using either
> > > + * ihold() or the atomic_inc(), for shared futexes. The former provides
> > > + * a full mb on all architectures. For architectures that do not have an
> > > + * implicit barrier in atomic_inc/dec, we explicitly add it - please
> > > + * refer to futex_get_mm() and hb_waiters_inc/dec().
> > >   */

> > It isn't at all explained what purpose the memory barriers serve.
> 
> Why doesn't this explain it?

Because you failed to explain what is ordered against what and what
the resulting order guarantees.

> "The correct serialization ensures that a waiter either observes
> the changed user space value before blocking or is woken by a
> concurrent waker."

Or both. For the given case:

X = Y = 0

w[X]=1  w[Y]=1
MB	MB
r[Y]=y	r[X]=x

x==1 && y==1 is a valid result. The only invalid result is both 0.

But then we're still short of how we end up at that guarantee.

> Perhaps adding an example?
>  plist_add()    |    uaddr = newval
>  smp_mb()       |    smp_mb()
>  verify uaddr   |    plist_head_empty()

Except of course you don't actually use plist_add() and
plist_head_empty() for anything much at all, only creating more
confusion.

Just add the waiters variable and explicitly mention what you're doing.