From patchwork Wed Nov 23 11:25:22 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: 9443007 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 B6079600BA for ; Wed, 23 Nov 2016 11:25:56 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8C8DA1FE95 for ; Wed, 23 Nov 2016 11:25:56 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7F93F2236A; Wed, 23 Nov 2016 11:25:56 +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 E69BD1FE95 for ; Wed, 23 Nov 2016 11:25:55 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 9FF3E6E81D; Wed, 23 Nov 2016 11:25:52 +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 E5DA86E81E for ; Wed, 23 Nov 2016 11:25:50 +0000 (UTC) Received: by mail-wm0-x242.google.com with SMTP id g23so1687528wme.1 for ; Wed, 23 Nov 2016 03:25:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=lispeFPdqesPthrJx0EWuXGhWEt7PWVivL+DhoYbABw=; b=bCFulsoQXTE4ovCAKR68k/ChV0Ne2Fm3OZbAMLg344UsQG/5rAVmN0xYXBZsq7Mlsc pwbFR2dYKodhDjHo1AxZbbf+ORD63f5BGIY7aGvLUvqkpOJx4pA7Nfp7bMzPC16CFJJp ayj7FNLJAfKbEW9c44dY+kbG6fVm9lYF5zKVb9Cdl8EC9a5gD1XSd9E8LDH2HQdkNlv0 7eY8Rw9sEQXtU/1SN0biAkRWfAim8DsvATnXHEkmmT9+FE1FCFNivta556X+ps+Rk/QY OWX0Tp7ikBRjlQIvdzgIKiH/27m+/CAdiW7/b2cDayUJjGQBzOGq5LqcV8zeV6FmEu3L Iy+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=lispeFPdqesPthrJx0EWuXGhWEt7PWVivL+DhoYbABw=; b=RY2FhKQLHPRB6A2UBAJS2DkC6CfeiXRT+Y4/YwcC8KfKg3yoy+UsfBAGaJP17aIZ/k VH10H5bGZKrwUhf29wP0QbJK4EIzdusEUZwktjCaw2yVNmnX55CyqVvfFO3kcwBSjGjE XXXVKnihTiwmBDf2OhfiS8pvbYDRT4nBeWxbZFertdjtjdFC1raQy4qG/qPiJ1TitYG9 20Vttr1H4KHfIZgKpESZMacgxhDJnYlfysSYpgJTu8IYW5CGtk8ICnm6nMP1T/Y3kvJZ dzf7CPUKi5vXGFabfJeVEASolAvXG2aQS5Gw1yt07ADpD033ld3lMyk1EI3Zf0tT+gK0 Wz1Q== X-Gm-Message-State: AKaTC00Nk+QPDRXy1TCJC1K49oPsShjaz42t677tGXtzzm0nJy/MCqFUbOoIFvXqwBQxzQ== X-Received: by 10.28.189.69 with SMTP id n66mr6577864wmf.35.1479900349351; Wed, 23 Nov 2016 03:25:49 -0800 (PST) Received: from cassiopeia.fritz.box ([2001:a61:1157:fa01:f4ca:31b1:e109:5ff4]) by smtp.gmail.com with ESMTPSA id c133sm2264367wme.12.2016.11.23.03.25.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 23 Nov 2016 03:25:48 -0800 (PST) From: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= To: linux-kernel@vger.kernel.org Subject: [PATCH 1/4] locking/ww_mutex: Fix a deadlock affecting ww_mutexes Date: Wed, 23 Nov 2016 12:25:22 +0100 Message-Id: <1479900325-28358-1-git-send-email-nhaehnle@gmail.com> X-Mailer: git-send-email 2.7.4 MIME-Version: 1.0 Cc: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= , Peter Zijlstra , dri-devel@lists.freedesktop.org, Ingo Molnar , stable@vger.kernel.org, Maarten Lankhorst 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 Fix a race condition involving 4 threads and 2 ww_mutexes as indicated in the following example. Acquire context stamps are ordered like the thread numbers, i.e. thread #1 should back off when it encounters a mutex locked by thread #0 etc. Thread #0 Thread #1 Thread #2 Thread #3 --------- --------- --------- --------- lock(ww) success lock(ww') success lock(ww) lock(ww) . . . unlock(ww) part 1 lock(ww) . . . success . . . . . unlock(ww) part 2 . back off lock(ww') . . . (stuck) (stuck) Here, unlock(ww) part 1 is the part that sets lock->base.count to 1 (without being protected by lock->base.wait_lock), meaning that thread #0 can acquire ww in the fast path or, much more likely, the medium path in mutex_optimistic_spin. Since lock->base.count == 0, thread #0 then won't wake up any of the waiters in ww_mutex_set_context_fastpath. Then, unlock(ww) part 2 wakes up _only_the_first_ waiter of ww. This is thread #2, since waiters are added at the tail. Thread #2 wakes up and backs off since it sees ww owned by a context with a lower stamp. Meanwhile, thread #1 is never woken up, and so it won't back off its lock on ww'. So thread #0 gets stuck waiting for ww' to be released. This patch fixes the deadlock by waking up all waiters in the slow path of ww_mutex_unlock. We have an internal test case for amdgpu which continuously submits command streams from tens of threads, where all command streams reference hundreds of GPU buffer objects with a lot of overlap in the buffer lists between command streams. This test reliably caused a deadlock, and while I haven't completely confirmed that it is exactly the scenario outlined above, this patch does fix the test case. v2: - use wake_q_add - add additional explanations Cc: Peter Zijlstra Cc: Ingo Molnar Cc: Chris Wilson Cc: Maarten Lankhorst Cc: dri-devel@lists.freedesktop.org Cc: stable@vger.kernel.org Reviewed-by: Christian König (v1) Signed-off-by: Nicolai Hähnle Reviewed-by: Daniel Vetter --- kernel/locking/mutex.c | 33 +++++++++++++++++++++++++++++---- 1 file changed, 29 insertions(+), 4 deletions(-) diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index a70b90d..7fbf9b4 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -409,6 +409,9 @@ static bool mutex_optimistic_spin(struct mutex *lock, __visible __used noinline void __sched __mutex_unlock_slowpath(atomic_t *lock_count); +static __used noinline +void __sched __mutex_unlock_slowpath_wakeall(atomic_t *lock_count); + /** * mutex_unlock - release the mutex * @lock: the mutex to be released @@ -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); } EXPORT_SYMBOL(ww_mutex_unlock); @@ -716,7 +726,7 @@ EXPORT_SYMBOL_GPL(__ww_mutex_lock_interruptible); * Release the lock, slowpath: */ static inline void -__mutex_unlock_common_slowpath(struct mutex *lock, int nested) +__mutex_unlock_common_slowpath(struct mutex *lock, int nested, int wake_all) { unsigned long flags; WAKE_Q(wake_q); @@ -740,7 +750,14 @@ __mutex_unlock_common_slowpath(struct mutex *lock, int nested) mutex_release(&lock->dep_map, nested, _RET_IP_); debug_mutex_unlock(lock); - if (!list_empty(&lock->wait_list)) { + if (wake_all) { + struct mutex_waiter *waiter; + + list_for_each_entry(waiter, &lock->wait_list, list) { + debug_mutex_wake_waiter(lock, waiter); + wake_q_add(&wake_q, waiter->task); + } + } else if (!list_empty(&lock->wait_list)) { /* get the first entry from the wait-list: */ struct mutex_waiter *waiter = list_entry(lock->wait_list.next, @@ -762,7 +779,15 @@ __mutex_unlock_slowpath(atomic_t *lock_count) { struct mutex *lock = container_of(lock_count, struct mutex, count); - __mutex_unlock_common_slowpath(lock, 1); + __mutex_unlock_common_slowpath(lock, 1, 0); +} + +static void +__mutex_unlock_slowpath_wakeall(atomic_t *lock_count) +{ + struct mutex *lock = container_of(lock_count, struct mutex, count); + + __mutex_unlock_common_slowpath(lock, 1, 1); } #ifndef CONFIG_DEBUG_LOCK_ALLOC