Re: [PATCH -v4 5/8] locking/mutex: Add lock handoff to avoid starvation

[Chris Wilson]

On Fri, Oct 07, 2016 at 04:52:48PM +0200, Peter Zijlstra wrote:
> Implement lock handoff to avoid lock starvation.
> 
> Lock starvation is possible because mutex_lock() allows lock stealing,
> where a running (or optimistic spinning) task beats the woken waiter
> to the acquire.
> 
> Lock stealing is an important performance optimization because waiting
> for a waiter to wake up and get runtime can take a significant time,
> during which everyboy would stall on the lock.
> 
> The down-side is of course that it allows for starvation.
> 
> This patch has the waiter requesting a handoff if it fails to acquire
> the lock upon waking. This re-introduces some of the wait time,
> because once we do a handoff we have to wait for the waiter to wake up
> again.
> 
> A future patch will add a round of optimistic spinning to attempt to
> alleviate this penalty, but if that turns out to not be enough, we can
> add a counter and only request handoff after multiple failed wakeups.
> 
> There are a few tricky implementation details:
> 
>  - accepting a handoff must only be done in the wait-loop. Since the
>    handoff condition is owner == current, it can easily cause
>    recursive locking trouble.
> 
>  - accepting the handoff must be careful to provide the ACQUIRE
>    semantics.
> 
>  - having the HANDOFF bit set on unlock requires care, we must not
>    clear the owner.
> 
>  - we must be careful to not leave HANDOFF set after we've acquired
>    the lock. The tricky scenario is setting the HANDOFF bit on an
>    unlocked mutex.

There's a hole along the interruptible path - we leave the HANDOFF bit
set, even though the first waiter returns with -EINTR. The unlock then
sees the HANDOFF, assigns it to the next waiter, but that waiter does a
racy check to decide if it is first, decides it is not and so skips the
trylock and also returns with -EINTR. (i.e. invalidating the

                /*
                 * Here we order against unlock; we must either see it change
                 * state back to RUNNING and fall through the next schedule(),
                 * or we must see its unlock and acquire.
                 */

as we may not reach the next schedule). Repeating the
__mutex_waiter_is_first() after acquiring the wait_lock is sufficient,
as is clearing the HANDOFF bit before -EINTR.

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 9b349619f431..6f7e3bf0d595 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -684,6 +684,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
                 * against mutex_unlock() and wake-ups do not go missing.
                 */
                if (unlikely(signal_pending_state(state, task))) {
+                       if (first)
+                               __mutex_clear_flag(lock, MUTEX_FLAG_HANDOFF);
                        ret = -EINTR;
                        goto err;
                }

Though I expect you will be able to find a better solution.
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre