From patchwork Wed Dec 21 18:46:34 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Nicolai_H=C3=A4hnle?= X-Patchwork-Id: 9483631 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id E8FA2601D3 for ; Wed, 21 Dec 2016 18:47:06 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DCB8028419 for ; Wed, 21 Dec 2016 18:47:06 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D1A7D28458; Wed, 21 Dec 2016 18:47:06 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 5D49028419 for ; Wed, 21 Dec 2016 18:47:06 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 98A1F6E0F0; Wed, 21 Dec 2016 18:47:02 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from mail-wm0-x242.google.com (mail-wm0-x242.google.com [IPv6:2a00:1450:400c:c09::242]) by gabe.freedesktop.org (Postfix) with ESMTPS id 0A51F6E0F0 for ; Wed, 21 Dec 2016 18:46:56 +0000 (UTC) Received: by mail-wm0-x242.google.com with SMTP id m203so32030418wma.3 for ; Wed, 21 Dec 2016 10:46:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=P2T4XKLs1u9IrLm4zndhdYyhASysGDuhXdQ7YiKzH4I=; b=RPcdI4uQpQqFxCPEvTuOm51Dv3wQQ+qK2fnwbtd6/BeIMwqmEhjRWXau2bQDNNnsWU hExTVL7V8sd0jfUfDS/9AhDkxFLhaLq/ZA2w63/vKcOWTVnRnDDvXURabDR/1xp7TZfS NPVG/gcbMwFjpU0LJYgOT2QZ/4Fab0+UKOwEvSYjMo0Sezu3+QNLTRKfeBN5HqJX6a3W NOd3Qj7D5kppevySCQq4UJYTqr9CvfuGJjCPeoXslsmfQ0RQTFPOHtuRpEBOLvjoMnN7 BW2nqfIWCWpf2OD7UJfgDMgKl0By+0iTK9yZW0r7aCcIWTko29zu61X28h+qNZcpK18L 6VWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=P2T4XKLs1u9IrLm4zndhdYyhASysGDuhXdQ7YiKzH4I=; b=nSC2T9vsbeDXHPk863A4TYTO+7qKQX5X2ia4Jz9lWTDF+RVpaJUv/srPzmYHun8KyX MbHeXkz20mmFQHHNlE4e8Z8hsSaLflmzMGhUksSLfMOf0b/6V3ZF3SLtQl8YehH2qokd JAvLGf5IiBHz3LmpArM6Fo/3DgfWsrCgjtaQ/k4zUYEoMTe0Qw7KRsu6G0kwYqe474pO WTRDp2LwoW2K9bzZpsylq69dz5cW7OWs1Qg0Xel5lVDHf9J/zo+V2RNBZxvkPI+uRp3C gyjSMrRExcT0RLaxrqZ4/YyPAA6oUvPFp6+hJeNQKzWH/48la5jnhRVXP63tGCXz73ml c40A== X-Gm-Message-State: AIkVDXIKRHcjFwh7QwY7/8pOSpGHL2f+dkcaGEIu+bvOPDUt9cy3fMgRHqrD7wCO3tOqfg== X-Received: by 10.28.9.131 with SMTP id 125mr8135465wmj.22.1482346014299; Wed, 21 Dec 2016 10:46:54 -0800 (PST) Received: from cassiopeia.fritz.box ([2001:a61:110a:1701:2511:6687:1ba5:b45b]) by smtp.gmail.com with ESMTPSA id ke6sm31840526wjb.21.2016.12.21.10.46.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 21 Dec 2016 10:46:53 -0800 (PST) From: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= To: linux-kernel@vger.kernel.org Subject: [PATCH v3 06/12] locking/ww_mutex: Add waiters in stamp order Date: Wed, 21 Dec 2016 19:46:34 +0100 Message-Id: <1482346000-9927-7-git-send-email-nhaehnle@gmail.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1482346000-9927-1-git-send-email-nhaehnle@gmail.com> References: <1482346000-9927-1-git-send-email-nhaehnle@gmail.com> MIME-Version: 1.0 Cc: Maarten Lankhorst , =?UTF-8?q?Nicolai=20H=C3=A4hnle?= , Peter Zijlstra , dri-devel@lists.freedesktop.org, Ingo Molnar X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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. For w/w mutexes, being first in the wait list is only stable when taking the lock without a context. Therefore, the purpose of the first flag is split into two: 'first' remains to indicate whether we want to spin optimistically, while 'handoff' indicates that we should be prepared to accept a handoff. For w/w locking with a context, we always accept handoffs after the first schedule(), to handle the following sequence of events: 1. Task #0 unlocks and hands off to Task #2 which is first in line 2. Task #1 adds itself in front of Task #2 3. Task #2 wakes up and must accept the handoff even though it is no longer first in line v2: - rein in the indentation of __ww_mutex_add_waiter a bit - set contending_lock in __ww_mutex_add_waiter (Chris Wilson) v3: - split 'first' into 'first' and 'handoff' to avoid moving the trylock calls around so much - scan the wait_list in reverse order in __ww_mutex_add_waiter 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 | 97 +++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 91 insertions(+), 9 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 282c6de..5b1ca20 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -620,6 +620,52 @@ __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; + struct list_head *pos; + + 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. + */ + pos = &lock->wait_list; + list_for_each_entry_reverse(cur, &lock->wait_list, list) { + if (!cur->ww_ctx) + continue; + + if (__ww_ctx_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; + } + + break; + } + + pos = &cur->list; + } + + list_add_tail(&waiter->list, pos); + return 0; +} + /* * Lock a mutex (possibly interruptible), slowpath: */ @@ -632,6 +678,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, struct mutex_waiter waiter; unsigned long flags; bool first = false; + bool handoff = false; struct ww_mutex *ww; int ret; @@ -665,15 +712,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 (;;) { /* @@ -682,7 +739,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, * before testing the error conditions to make sure we pick up * the handoff. */ - if (__mutex_trylock(lock, first)) + if (__mutex_trylock(lock, handoff)) goto acquired; /* @@ -711,13 +768,34 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, * or we must see its unlock and acquire. */ - if (!first && __mutex_waiter_is_first(lock, &waiter)) { - first = true; + 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); + + /* + * Always be prepared to accept a handoff after the + * first wait, because we may have been the first + * waiter during unlock. + */ + handoff = true; + } else if (!first && __mutex_waiter_is_first(lock, &waiter)) { + first = handoff = true; __mutex_set_flag(lock, MUTEX_FLAG_HANDOFF); } - if ((first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) || - __mutex_trylock(lock, first)) + if ((first && + mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, true)) || + __mutex_trylock(lock, handoff)) break; spin_lock_mutex(&lock->wait_lock, flags); @@ -746,6 +824,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);