Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758214AbcLAOHL (ORCPT ); Thu, 1 Dec 2016 09:07:11 -0500 Received: from mail-wj0-f196.google.com ([209.85.210.196]:35508 "EHLO mail-wj0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757961AbcLAOHH (ORCPT ); Thu, 1 Dec 2016 09:07:07 -0500 From: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= To: linux-kernel@vger.kernel.org Cc: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= , Peter Zijlstra , Ingo Molnar , Maarten Lankhorst , Daniel Vetter , Chris Wilson , dri-devel@lists.freedesktop.org Subject: [PATCH v2 05/11] locking/ww_mutex: Add waiters in stamp order Date: Thu, 1 Dec 2016 15:06:48 +0100 Message-Id: <1480601214-26583-6-git-send-email-nhaehnle@gmail.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1480601214-26583-1-git-send-email-nhaehnle@gmail.com> References: <1480601214-26583-1-git-send-email-nhaehnle@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5802 Lines: 188 From: Nicolai Hähnle Add regular waiters in stamp order. Keep adding waiters that have no context in FIFO order and take care not to starve them. While adding our task as a waiter, back off if we detect that there is a waiter with a lower stamp in front of us. Make sure to call lock_contended even when we back off early. v2: - rein in the indentation of __ww_mutex_add_waiter a bit - set contending_lock in __ww_mutex_add_waiter (Chris Wilson) Cc: Peter Zijlstra Cc: Ingo Molnar Cc: Maarten Lankhorst Cc: Daniel Vetter Cc: Chris Wilson Cc: dri-devel@lists.freedesktop.org Signed-off-by: Nicolai Hähnle --- include/linux/mutex.h | 3 ++ kernel/locking/mutex.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 83 insertions(+), 7 deletions(-) diff --git a/include/linux/mutex.h b/include/linux/mutex.h index b97870f..118a3b6 100644 --- a/include/linux/mutex.h +++ b/include/linux/mutex.h @@ -20,6 +20,8 @@ #include #include +struct ww_acquire_ctx; + /* * Simple, straightforward mutexes with strict semantics: * @@ -75,6 +77,7 @@ static inline struct task_struct *__mutex_owner(struct mutex *lock) struct mutex_waiter { struct list_head list; struct task_struct *task; + struct ww_acquire_ctx *ww_ctx; #ifdef CONFIG_DEBUG_MUTEXES void *magic; #endif diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 585627f..d63eebb 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -628,6 +628,51 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct ww_acquire_ctx *ctx) return 0; } +static inline int __sched +__ww_mutex_add_waiter(struct mutex_waiter *waiter, + struct mutex *lock, + struct ww_acquire_ctx *ww_ctx) +{ + struct mutex_waiter *cur; + + if (!ww_ctx) { + list_add_tail(&waiter->list, &lock->wait_list); + return 0; + } + + /* + * Add the waiter before the first waiter with a higher stamp. + * Waiters without a context are skipped to avoid starving + * them. + */ + list_for_each_entry(cur, &lock->wait_list, list) { + if (!cur->ww_ctx) + continue; + + if (__ww_mutex_stamp_after(ww_ctx, cur->ww_ctx)) { + /* Back off immediately if necessary. */ + if (ww_ctx->acquired > 0) { +#ifdef CONFIG_DEBUG_MUTEXES + struct ww_mutex *ww; + + ww = container_of(lock, struct ww_mutex, base); + DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock); + ww_ctx->contending_lock = ww; +#endif + return -EDEADLK; + } + + continue; + } + + list_add_tail(&waiter->list, &cur->list); + return 0; + } + + list_add_tail(&waiter->list, &lock->wait_list); + return 0; +} + /* * Lock a mutex (possibly interruptible), slowpath: */ @@ -677,15 +722,25 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, debug_mutex_lock_common(lock, &waiter); debug_mutex_add_waiter(lock, &waiter, task); - /* add waiting tasks to the end of the waitqueue (FIFO): */ - list_add_tail(&waiter.list, &lock->wait_list); + lock_contended(&lock->dep_map, ip); + + if (!use_ww_ctx) { + /* add waiting tasks to the end of the waitqueue (FIFO): */ + list_add_tail(&waiter.list, &lock->wait_list); + } else { + /* Add in stamp order, waking up waiters that must back off. */ + ret = __ww_mutex_add_waiter(&waiter, lock, ww_ctx); + if (ret) + goto err_early_backoff; + + waiter.ww_ctx = ww_ctx; + } + waiter.task = task; if (__mutex_waiter_is_first(lock, &waiter)) __mutex_set_flag(lock, MUTEX_FLAG_WAITERS); - lock_contended(&lock->dep_map, ip); - set_task_state(task, state); for (;;) { /* @@ -693,8 +748,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, * mutex_unlock() handing the lock off to us, do a trylock * before testing the error conditions to make sure we pick up * the handoff. + * + * For w/w locks, we always need to do this even if we're not + * currently the first waiter, because we may have been the + * first waiter during the unlock. */ - if (__mutex_trylock(lock, first)) + if (__mutex_trylock(lock, use_ww_ctx || first)) goto acquired; /* @@ -716,7 +775,20 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, spin_unlock_mutex(&lock->wait_lock, flags); schedule_preempt_disabled(); - if (!first && __mutex_waiter_is_first(lock, &waiter)) { + if (use_ww_ctx && ww_ctx) { + /* + * Always re-check whether we're in first position. We + * don't want to spin if another task with a lower + * stamp has taken our position. + * + * We also may have to set the handoff flag again, if + * our position at the head was temporarily taken away. + */ + first = __mutex_waiter_is_first(lock, &waiter); + + if (first) + __mutex_set_flag(lock, MUTEX_FLAG_HANDOFF); + } else if (!first && __mutex_waiter_is_first(lock, &waiter)) { first = true; __mutex_set_flag(lock, MUTEX_FLAG_HANDOFF); } @@ -728,7 +800,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, * or we must see its unlock and acquire. */ if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) || - __mutex_trylock(lock, first)) + __mutex_trylock(lock, use_ww_ctx || first)) break; spin_lock_mutex(&lock->wait_lock, flags); @@ -761,6 +833,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, err: __set_task_state(task, TASK_RUNNING); mutex_remove_waiter(lock, &waiter, task); +err_early_backoff: spin_unlock_mutex(&lock->wait_lock, flags); debug_mutex_free_waiter(&waiter); mutex_release(&lock->dep_map, 1, ip); -- 2.7.4