From patchwork Wed Dec 21 18:46:35 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: 9483655 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 1F16B601D3 for ; Wed, 21 Dec 2016 18:47:57 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 13CF027D85 for ; Wed, 21 Dec 2016 18:47:57 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0872B27F9E; Wed, 21 Dec 2016 18:47:57 +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 A2EDB27D85 for ; Wed, 21 Dec 2016 18:47:56 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id CF1866F0D7; Wed, 21 Dec 2016 18:47:54 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from mail-wm0-x241.google.com (mail-wm0-x241.google.com [IPv6:2a00:1450:400c:c09::241]) by gabe.freedesktop.org (Postfix) with ESMTPS id 2D3DC6E0F0 for ; Wed, 21 Dec 2016 18:46:57 +0000 (UTC) Received: by mail-wm0-x241.google.com with SMTP id m203so32030551wma.3 for ; Wed, 21 Dec 2016 10:46:57 -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=Vp6ucqSWqBiHxz24GTk+/+ky5xP4tn9wBuQQroHvSQI=; b=SZ2iLs3JOuwqMk4gaNI0cCBCFHf5lv9y69qrXDKuqFud3AKUmvzU40OQAfERnNeckP 1dOJDQ4U2F4eidx+M3JzHwGrRFTaYqBoS63ld58eJGRxfEEFBGHBefMppvdeHilykA6e 2D0YzVydwemK9dmrB++EZJFGhEsPBrdT7YVJUZOkE7hbN+YK4YruqujcRGncw3AHLGWx F0V6Lc8kghHGDkHL45+eJ7kGzpoVgTWoOjoo0tmnvcfO8n2IguDVSqPxpNfwvk0cSV9/ mUhUuVbi6L4bEddGOnyyW2lxW31O/1SsVv5TCYKTrr9lTuRFAJoDgEKD93qmT2em/KYl tXRQ== 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=Vp6ucqSWqBiHxz24GTk+/+ky5xP4tn9wBuQQroHvSQI=; b=XsIljJvKx8m/0CqcOoVOGt/WvTXc6BH4ZOxT57xd/uzBVa7/ieLO+AsUpiOrLUHu/9 VGx1Yh8yhmswTJG/6FUj0SxYtPVGyiEjuGH8hBynuems9Z8cZ8buFH2S18lZesTIKPk9 i8mGu+hdhUmpXQjeo5jBAdmfb3L9AHVesENI4kUQ3OAeUKh6Zdb+hDlNXM6cJpNySa54 shxnoYKn7WGcKviPC4om1AZrhm6Mwvdih2TzW0iX2mmPLWCvuKgPv1jGuXx1YX4i5n/C vG41g0C+bLw1351Kzv38ly+kkd3UQg/2nc0xdCCrQtDJ+NWTDAF6zRYfg9kPtF8PuDe1 0ZNg== X-Gm-Message-State: AIkVDXKQuU6dIt/mPAAzmk46Aeod+RL9lqmkTWLqdH5gikXFSg4+07v3Ine2Exn/YPQrgQ== X-Received: by 10.28.142.16 with SMTP id q16mr6006510wmd.35.1482346015507; Wed, 21 Dec 2016 10:46:55 -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.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 21 Dec 2016 10:46:54 -0800 (PST) From: =?UTF-8?q?Nicolai=20H=C3=A4hnle?= To: linux-kernel@vger.kernel.org Subject: [PATCH v3 07/12] locking/ww_mutex: Notify waiters that have to back off while adding tasks to wait list Date: Wed, 21 Dec 2016 19:46:35 +0100 Message-Id: <1482346000-9927-8-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 While adding our task as a waiter, detect if another task should back off because of us. With this patch, we establish the invariant that the wait list contains at most one (sleeping) waiter with ww_ctx->acquired > 0, and this waiter will be the first waiter with a context. Since only waiters with ww_ctx->acquired > 0 have to back off, this allows us to be much more economical with wakeups. v2: rebase on v2 of earlier patches 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 --- kernel/locking/mutex.c | 41 +++++++++++++++++++++++++++++++---------- 1 file changed, 31 insertions(+), 10 deletions(-) diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 5b1ca20..ee4d152 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -601,23 +601,34 @@ void __sched ww_mutex_unlock(struct ww_mutex *lock) EXPORT_SYMBOL(ww_mutex_unlock); static inline int __sched -__ww_mutex_lock_check_stamp(struct mutex *lock, struct ww_acquire_ctx *ctx) +__ww_mutex_lock_check_stamp(struct mutex *lock, struct mutex_waiter *waiter, + struct ww_acquire_ctx *ctx) { struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx); + struct mutex_waiter *cur; - if (!hold_ctx) - return 0; + if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) + goto deadlock; - if (__ww_ctx_stamp_after(ctx, hold_ctx)) { -#ifdef CONFIG_DEBUG_MUTEXES - DEBUG_LOCKS_WARN_ON(ctx->contending_lock); - ctx->contending_lock = ww; -#endif - return -EDEADLK; + /* + * If there is a waiter in front of us that has a context, then its + * stamp is earlier than ours and we must back off. + */ + cur = waiter; + list_for_each_entry_continue_reverse(cur, &lock->wait_list, list) { + if (cur->ww_ctx) + goto deadlock; } return 0; + +deadlock: +#ifdef CONFIG_DEBUG_MUTEXES + DEBUG_LOCKS_WARN_ON(ctx->contending_lock); + ctx->contending_lock = ww; +#endif + return -EDEADLK; } static inline int __sched @@ -660,6 +671,15 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, } pos = &cur->list; + + /* + * Wake up the waiter so that it gets a chance to back + * off. + */ + if (cur->ww_ctx->acquired > 0) { + debug_mutex_wake_waiter(lock, cur); + wake_up_process(cur->task); + } } list_add_tail(&waiter->list, pos); @@ -753,7 +773,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, } if (use_ww_ctx && ww_ctx && ww_ctx->acquired > 0) { - ret = __ww_mutex_lock_check_stamp(lock, ww_ctx); + ret = __ww_mutex_lock_check_stamp(lock, &waiter, + ww_ctx); if (ret) goto err; }