lkml.org 
[lkml]   [2016]   [Nov]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH 1/4] locking/ww_mutex: Fix a deadlock affecting ww_mutexes
    From
    Date
    On 23.11.2016 15:25, Daniel Vetter wrote:
    > On Wed, Nov 23, 2016 at 03:03:36PM +0100, Peter Zijlstra wrote:
    >> On Wed, Nov 23, 2016 at 12:25:22PM +0100, Nicolai Hähnle wrote:
    >>> @@ -473,7 +476,14 @@ void __sched ww_mutex_unlock(struct ww_mutex *lock)
    >>> */
    >>> mutex_clear_owner(&lock->base);
    >>> #endif
    >>> - __mutex_fastpath_unlock(&lock->base.count, __mutex_unlock_slowpath);
    >>> + /*
    >>> + * A previously _not_ waiting task may acquire the lock via the fast
    >>> + * path during our unlock. In that case, already waiting tasks may have
    >>> + * to back off to avoid a deadlock. Wake up all waiters so that they
    >>> + * can check their acquire context stamp against the new owner.
    >>> + */
    >>> + __mutex_fastpath_unlock(&lock->base.count,
    >>> + __mutex_unlock_slowpath_wakeall);
    >>> }
    >>
    >> So doing a wake-all has obvious issues with thundering herd etc.. Also,
    >> with the new mutex, you'd not be able to do hand-off, which would
    >> introduce starvation cases.
    >>
    >> Ideally we'd iterate the blocked list and pick the waiter with the
    >> earliest stamp, or we'd maintain the list in stamp order instead of
    >> FIFO, for ww_mutex.
    >
    > Not sure we'll win that much, at least I think we still need to wake up
    > everyone with earlier stamp than the one of the task that just released
    > the lock. Otherwise there's deadlocks. So just cuts the wakeups in half,
    > on average.
    >
    > What we could do is do a handoff-hint with the timestamp of earliest task
    > we believe should get the lock. Everyone with a later timestamp that gets
    > woken then knows that they definitely have a deadlock situation and need
    > to back off (thread 2 in the example).
    >
    > thread 1 would get woken, and would be able to take the lock, except when
    > thread 0 successfully raced it and stole the lock. And anyone else racing
    > in with later timestamps would also immediately back off, ensuring
    > fairness.

    I did consider maintaining stamp order in the waiter list and originally
    decided against it because I just wanted a simple and conservative fix
    to avoid adding new regressions.

    Now that a different approach is needed for >= 4.9 anyway mostly due to
    the hand-off logic, I'm reconsidering this.

    I do believe we can win a bit by keeping the wait list sorted, if we
    also make sure that waiters don't add themselves in the first place if
    they see that a deadlock situation cannot be avoided.

    I will probably want to extend struct mutex_waiter with
    ww_mutex-specific fields to facilitate this (i.e. ctx pointer, perhaps
    stamp as well to reduce pointer-chasing). That should be fine since it
    lives on the stack.

    In the meantime, I'd appreciate it if patch #1 could be accepted as-is
    for stable updates to <= 4.8. It fixes a real (if rare) bug, and the
    stampede inefficiency isn't a problem in practice at least for GPU
    applications.

    Thanks,
    Nicolai

    >
    > Without thinking it through in detail this is a PI issue, except that we
    > replace boosting with wakeup&back-off. Could we perhaps steal something
    > from rt mutexes to make it fair&efficient?
    > -Daniel
    >

    \
     
     \ /
      Last update: 2016-11-24 12:27    [W:4.317 / U:0.152 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site