lkml.org 
[lkml]   [2013]   [Dec]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH v2 4/4] futex: Avoid taking hb lock if nothing to wakeup
    From
    Date
    On Tue, 2013-12-10 at 17:57 +0100, Peter Zijlstra wrote:
    > On Tue, Dec 03, 2013 at 01:45:27AM -0800, Davidlohr Bueso wrote:
    > > --- a/kernel/futex.c
    > > +++ b/kernel/futex.c
    > > @@ -82,10 +82,12 @@
    > > * The waker side modifies the user space value of the futex and calls
    > > * futex_wake(). It computes the hash bucket and acquires the hash
    > > * bucket lock. Then it looks for waiters on that futex in the hash
    > > - * bucket and wakes them.
    > > - *
    > > - * Note that the spin_lock serializes waiters and wakers, so that the
    > > - * following scenario is avoided:
    > > + * bucket and wakes them.
    >
    > Why not let this be the start of a new paragraph?
    >
    > > In scenarios where wakeups are called and no
    > > + * tasks are blocked on a futex, taking the hb spinlock can be avoided
    > > + * and simply return. In order for this optimization to work, ordering
    > > + * guarantees must exist so that the waiter being added to the list is
    > > + * acknowledged when the list is concurrently being checked by the waker,
    > > + * avoiding scenarios like the following:
    > > *
    > > * CPU 0 CPU 1
    > > * val = *futex;
    > > @@ -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().
    > > */
    >
    > This comment actually confuses me :/

    Well that explains where the required barriers are coming from.

    >
    > It isn't at all explained what purpose the memory barriers serve.

    Why doesn't this explain it?

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

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

    Thanks,
    Davidlohr



    \
     
     \ /
      Last update: 2013-12-10 19:01    [W:4.276 / U:0.284 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site