From patchwork Thu Apr 5 16:58:58 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132866 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6520059ljb; Thu, 5 Apr 2018 09:59:12 -0700 (PDT) X-Google-Smtp-Source: AIpwx4+w9mDVyDsLdfOhDZHLrzaEKBvRB4fbBuvs+GrlOKdJ1MXgF9y6iC/60D/bgn0ZIN3WKHEB X-Received: by 10.99.119.79 with SMTP id s76mr15008556pgc.291.1522947552359; Thu, 05 Apr 2018 09:59:12 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947552; cv=none; d=google.com; s=arc-20160816; b=fc5c0VVVz9D9iWaW9zgsnazWV924NFBevsch6CvVoq84WmjeOEZTNLNgLpX9WdCTMW GPrEVi9efHLNTwW2ogI0ZIHkGhNGVnuBMt1k5ZWM65BNdmwvcv6DanUhbKJpJ1wlzU88 eaQD4wQTJxsiN663S/38JfOMpQpYiMt+5KX0dscsnEl8EM9yWMBaW7H+XcfZUrckiox7 JEVCnlfxXg8KwhuZUKcezs4mMM2M37iFdTqilm4efs45bdh/IrS+az/WWEFqdxglr90S w2kXMFprwdfdtO9yCeJEvEqmkyFNlA/DQBHR2JU9QSsDNxNpPgMBmHl7oSM1ERiPqjpv FJ9A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=DW4Kf+pGDNjkNsFL6OaB3IDEm4KpxDFOzxcMP2UGVD8=; b=K0DSsdxZRgOdNA/NXr/smla6J5mPlJ2aOBGz0F8jY8oJZb2cpXx4X3Tb0JiLtT9llK AVx+b6s1N/MIL5+DlzXL1AMwTNK3whYSU1Pf+nx45EJyc6SOmHQVlqCts5PvEiVrK3wv GSPsSJWKwbhTLgXuuWWOPQPW59+F9qlQjCy1zbtROhfZo3ghVpj3Vjzm5RhmoITS51K9 eRofAFAYoWU333ZMqHVb6f3iusxGefgOmHlMyMDxC8Op6Q2OdL0TjP6vUpY96jKfvPPX qbfViKHDVaeNNzc6pcewpY9sBmUQmV+Y6PcnMawFs8hj0/0aG4F1ABJzpbm52vzg/QO+ Q7tQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id q12-v6si6717025pll.419.2018.04.05.09.59.12; Thu, 05 Apr 2018 09:59:12 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751544AbeDEQ65 (ORCPT + 29 others); Thu, 5 Apr 2018 12:58:57 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:57300 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751268AbeDEQ6z (ORCPT ); Thu, 5 Apr 2018 12:58:55 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 220B41596; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id E85D13F5B1; Thu, 5 Apr 2018 09:58:54 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 8BEC51AE5448; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 01/10] locking/qspinlock: Don't spin on pending->locked transition in slowpath Date: Thu, 5 Apr 2018 17:58:58 +0100 Message-Id: <1522947547-24081-2-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org If a locker taking the qspinlock slowpath reads a lock value indicating that only the pending bit is set, then it will spin whilst the concurrent pending->locked transition takes effect. Unfortunately, there is no guarantee that such a transition will ever be observed since concurrent lockers could continuously set pending and hand over the lock amongst themselves, leading to starvation. Whilst this would probably resolve in practice, it means that it is not possible to prove liveness properties about the lock and means that lock acquisition time is unbounded. Remove the pending->locked spinning from the slowpath and instead queue explicitly if pending is set. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 10 ---------- 1 file changed, 10 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index d880296245c5..a192af2fe378 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -306,16 +306,6 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) return; /* - * wait for in-progress pending->locked hand-overs - * - * 0,1,0 -> 0,0,1 - */ - if (val == _Q_PENDING_VAL) { - while ((val = atomic_read(&lock->val)) == _Q_PENDING_VAL) - cpu_relax(); - } - - /* * trylock || pending * * 0,0,0 -> 0,0,1 ; trylock From patchwork Thu Apr 5 16:58:59 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132874 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6521907ljb; Thu, 5 Apr 2018 10:00:51 -0700 (PDT) X-Google-Smtp-Source: AIpwx4/WGeEc8c2Bi2CpFjr8ZOckxgtks3opWmySrSDS9wD6wR/lovgJkQu7dv+eclKvJUnynriH X-Received: by 10.99.124.92 with SMTP id l28mr15252173pgn.51.1522947651216; Thu, 05 Apr 2018 10:00:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947651; cv=none; d=google.com; s=arc-20160816; b=R/SgKTbcK1gToIyUGlw0dxfJ1/JNkqu7V/a1V4y/NfiHdQYbDYdcGuNw/IAe8JDdfO R+mOatUHAydjxxqGUA8V/ZfWLZWPmLhjiuVJR9ZrA3hewo7TFW6P+Kp0+jhGb3VHbj1Z NnBtr2okK1vBkMxF7MDPg/FV55g+Q0Nasr2MDFk5MBRtT6GbGq9jcijjJXZwIa9W7any DdFEfehnxs662A8uIfrG8qZ5C+D2+5yEWeYazSa/+cdf0imQroPzQYWXBYhtXInkDN1w KZd1J7RuSBd2XstxVCqUvFC8SNa9KDvATpJb9QCET7A5eO5JqMDJJ0yF2w4T55+IMV18 e1Cg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=KyMEwV8eFB8S12VuJuTbcszLwyh/uE8p8fueN27CrzU=; b=M1aGbMFKbV6ML26bFNIg1ZE7xZDkMSzmqhelP0kMVxlR0uFVFxqVcYerCVHvPOU5xF EBPx95IXmtfyuy8aYZdWzv37sQJJZ6Y0IfVgkp7FUlNgkssKhEo8MKBBxjO5bSwMHgaQ SJV2LD7ccArHVqwlRZHKfoZxjjhkyhLMRtGArl7hE434iyYcp4YQBkF2ppLxcLORvDKR Fm+LJzrNMQAy/d0g/sxsm/w8Z490BXJ82IGpEIEX5+n1QuhEjEIZYD4zM/JoVFZ2uGm/ UuXIsbpcfTuJdzV5ZkSMZSpGoBi9kPnkNhNNR6uUEsmCUuhBP1DJJ+ao5cXmCyoEN7fj O7/g== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id s2-v6si6306213plq.353.2018.04.05.10.00.50; Thu, 05 Apr 2018 10:00:51 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752081AbeDERAr (ORCPT + 29 others); Thu, 5 Apr 2018 13:00:47 -0400 Received: from foss.arm.com ([217.140.101.70]:57316 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750786AbeDEQ6z (ORCPT ); Thu, 5 Apr 2018 12:58:55 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 32C1815AB; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 04CB03F5C1; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 9D9821AE555F; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 02/10] locking/qspinlock: Remove unbounded cmpxchg loop from locking slowpath Date: Thu, 5 Apr 2018 17:58:59 +0100 Message-Id: <1522947547-24081-3-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The qspinlock locking slowpath utilises a "pending" bit as a simple form of an embedded test-and-set lock that can avoid the overhead of explicit queuing in cases where the lock is held but uncontended. This bit is managed using a cmpxchg loop which tries to transition the uncontended lock word from (0,0,0) -> (0,0,1) or (0,0,1) -> (0,1,1). Unfortunately, the cmpxchg loop is unbounded and lockers can be starved indefinitely if the lock word is seen to oscillate between unlocked (0,0,0) and locked (0,0,1). This could happen if concurrent lockers are able to take the lock in the cmpxchg loop without queuing and pass it around amongst themselves. This patch fixes the problem by unconditionally setting _Q_PENDING_VAL using atomic_fetch_or, and then inspecting the old value to see whether we need to spin on the current lock owner, or whether we now effectively hold the lock. The tricky scenario is when concurrent lockers end up queuing on the lock and the lock becomes available, causing us to see a lockword of (n,0,0). With pending now set, simply queuing could lead to deadlock as the head of the queue may not have observed the pending flag being cleared. Conversely, if the head of the queue did observe pending being cleared, then it could transition the lock from (n,0,0) -> (0,0,1) meaning that any attempt to "undo" our setting of the pending bit could race with a concurrent locker trying to set it. We handle this race by preserving the pending bit when taking the lock after reaching the head of the queue and leaving the tail entry intact if we saw pending set, because we know that the tail is going to be updated shortly. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 80 ++++++++++++++++++++-------------------------- 1 file changed, 35 insertions(+), 45 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index a192af2fe378..b75361d23ea5 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -294,7 +294,7 @@ static __always_inline u32 __pv_wait_head_or_lock(struct qspinlock *lock, void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) { struct mcs_spinlock *prev, *next, *node; - u32 new, old, tail; + u32 old, tail; int idx; BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS)); @@ -306,58 +306,48 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) return; /* + * If we observe any contention; queue. + */ + if (val & ~_Q_LOCKED_MASK) + goto queue; + + /* * trylock || pending * * 0,0,0 -> 0,0,1 ; trylock * 0,0,1 -> 0,1,1 ; pending */ - for (;;) { + val = atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val); + if (!(val & ~_Q_LOCKED_MASK)) { /* - * If we observe any contention; queue. + * we're pending, wait for the owner to go away. + * + * *,1,1 -> *,1,0 + * + * this wait loop must be a load-acquire such that we match the + * store-release that clears the locked bit and create lock + * sequentiality; this is because not all + * clear_pending_set_locked() implementations imply full + * barriers. */ - if (val & ~_Q_LOCKED_MASK) - goto queue; - - new = _Q_LOCKED_VAL; - if (val == new) - new |= _Q_PENDING_VAL; - + if (val & _Q_LOCKED_MASK) + smp_cond_load_acquire(&lock->val.counter, + !(VAL & _Q_LOCKED_MASK)); /* - * Acquire semantic is required here as the function may - * return immediately if the lock was free. + * take ownership and clear the pending bit. + * + * *,1,0 -> *,0,1 */ - old = atomic_cmpxchg_acquire(&lock->val, val, new); - if (old == val) - break; - - val = old; - } - - /* - * we won the trylock - */ - if (new == _Q_LOCKED_VAL) + clear_pending_set_locked(lock); return; + } /* - * we're pending, wait for the owner to go away. - * - * *,1,1 -> *,1,0 - * - * this wait loop must be a load-acquire such that we match the - * store-release that clears the locked bit and create lock - * sequentiality; this is because not all clear_pending_set_locked() - * implementations imply full barriers. - */ - smp_cond_load_acquire(&lock->val.counter, !(VAL & _Q_LOCKED_MASK)); - - /* - * take ownership and clear the pending bit. - * - * *,1,0 -> *,0,1 + * If pending was clear but there are waiters in the queue, then + * we need to undo our setting of pending before we queue ourselves. */ - clear_pending_set_locked(lock); - return; + if (!(val & _Q_PENDING_MASK)) + atomic_andnot(_Q_PENDING_VAL, &lock->val); /* * End of pending bit optimistic spinning and beginning of MCS @@ -461,15 +451,15 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * claim the lock: * * n,0,0 -> 0,0,1 : lock, uncontended - * *,0,0 -> *,0,1 : lock, contended + * *,*,0 -> *,*,1 : lock, contended * - * If the queue head is the only one in the queue (lock value == tail), - * clear the tail code and grab the lock. Otherwise, we only need - * to grab the lock. + * If the queue head is the only one in the queue (lock value == tail) + * and nobody is pending, clear the tail code and grab the lock. + * Otherwise, we only need to grab the lock. */ for (;;) { /* In the PV case we might already have _Q_LOCKED_VAL set */ - if ((val & _Q_TAIL_MASK) != tail) { + if ((val & _Q_TAIL_MASK) != tail || (val & _Q_PENDING_MASK)) { set_locked(lock); break; } From patchwork Thu Apr 5 16:59:00 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132865 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6519896ljb; Thu, 5 Apr 2018 09:59:01 -0700 (PDT) X-Google-Smtp-Source: AIpwx4/910dIuMVh8w2VozZZOvBkJ5QjG8m6ECBXBukWBvzrx9afUsdgWwwIoWh4h8IzuzXVIbaw X-Received: by 2002:a17:902:28e4:: with SMTP id f91-v6mr24239119plb.336.1522947541501; Thu, 05 Apr 2018 09:59:01 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947541; cv=none; d=google.com; s=arc-20160816; b=DYcjcTzCSwVgvulnaIFqqA56DN3covMLrDcaRNRqo5WWRDGV/eTezzD8x+J/TMVc3s 9CCfwcjlkKKMO//lulWjZZ1yNV7NBpkdLFlNBYdWrU6cbKVambYVgGJy5Z7rJE2SWqtY LLHybdTdOlCaHtztxwGaqrdX5HaFQtc/5P/wdeGNHlNrFhAuWYxog2PfF13sbq2iSUmL P8aJbi5O2L9JCI9yL9/pSBfZI9xhxvVTD82jBqOGPDjzkzY4+62olkznbwmFkjV8evVJ Scg2COV6s8t5H5/Jddq/bVbkuO65CgUlNVMnqv0DnosiJzvY+dWIL2UdEeUh6Mb+ltJA lctw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=Lp2wDP5tLq2BpDPtRM56uGztsnEKtAtLu0Z8rnqw5oo=; b=KXIZsh3eK2kpCoswfBx1WZAQX7UydDNPVTAepST5t1fPHWafNdWySUcZNQl2KRTsnE zbx+RcGo+N2BgEKFRMjG68j0EhebevtUmDcRSg952tCmrorgh44P56Czw3jbkxHeZg4W yc/9PP+CJ5UmW806hVHrG0UdoCVSOQ+7C/bB1+ApfCkvE3r8+fpTY6DNUfFCNzZz2/Qk unE2hNq/JDg9wQx9Sj/GDeU+bvgKUqrqUBDhgfFqw+bL4Fv/eXOr3M1ijWzOrPh8iMBD QrNYawDR2khLMjHxv+TOaDZRhL8HgaqpqU0Cg8YAANK2GM9yX8+JJm3UGbgScohdtMcb 3lpw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id q12-v6si6717025pll.419.2018.04.05.09.59.01; Thu, 05 Apr 2018 09:59:01 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751606AbeDEQ66 (ORCPT + 29 others); Thu, 5 Apr 2018 12:58:58 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:57324 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751361AbeDEQ6z (ORCPT ); Thu, 5 Apr 2018 12:58:55 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 463971650; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 185373F25D; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id ADE361AE5562; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 03/10] locking/qspinlock: Kill cmpxchg loop when claiming lock from head of queue Date: Thu, 5 Apr 2018 17:59:00 +0100 Message-Id: <1522947547-24081-4-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org When a queued locker reaches the head of the queue, it claims the lock by setting _Q_LOCKED_VAL in the lockword. If there isn't contention, it must also clear the tail as part of this operation so that subsequent lockers can avoid taking the slowpath altogether. Currently this is expressed as a cmpxchg loop that practically only runs up to two iterations. This is confusing to the reader and unhelpful to the compiler. Rewrite the cmpxchg loop without the loop, so that a failed cmpxchg implies that there is contention and we just need to write to _Q_LOCKED_VAL without considering the rest of the lockword. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 19 ++++++++----------- 1 file changed, 8 insertions(+), 11 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index b75361d23ea5..cdfa7b7328a8 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -457,24 +457,21 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * and nobody is pending, clear the tail code and grab the lock. * Otherwise, we only need to grab the lock. */ - for (;;) { - /* In the PV case we might already have _Q_LOCKED_VAL set */ - if ((val & _Q_TAIL_MASK) != tail || (val & _Q_PENDING_MASK)) { - set_locked(lock); - break; - } + + /* In the PV case we might already have _Q_LOCKED_VAL set */ + if ((val & _Q_TAIL_MASK) == tail) { /* * The smp_cond_load_acquire() call above has provided the - * necessary acquire semantics required for locking. At most - * two iterations of this loop may be ran. + * necessary acquire semantics required for locking. */ old = atomic_cmpxchg_relaxed(&lock->val, val, _Q_LOCKED_VAL); if (old == val) - goto release; /* No contention */ - - val = old; + goto release; /* No contention */ } + /* Either somebody is queued behind us or _Q_PENDING_VAL is set */ + set_locked(lock); + /* * contended path; wait for next if not observed yet, release. */ From patchwork Thu Apr 5 16:59:01 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132875 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6522221ljb; Thu, 5 Apr 2018 10:01:02 -0700 (PDT) X-Google-Smtp-Source: AIpwx4/SBeJJFwWiaV6T1epX9OWZud6Io0V/6jmuC60fKsCBkwBe6B4mDxQcghbOp6yYujySE939 X-Received: by 2002:a17:902:2943:: with SMTP id g61-v6mr24018925plb.238.1522947662237; Thu, 05 Apr 2018 10:01:02 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947662; cv=none; d=google.com; s=arc-20160816; b=UFZ+N7NHQQmuq5Ta80Wqby7nwxWZZumNuYBYsGQbhXC3dPMAUnt9GMQADCJQWU995f kikIY5O3Z+d005cemrWo3+ECejNTNDTGFKRcXO9vHLz3EDWquNuo6cvurBuJvFZhHcih yB64+Puoi/sHZ8xRGTT+pUCLxv3ddOGMCOqAxpj+Xp5nVuSfjRHfGXaRImAcxBw4e8an Eaoea1IMCUgVciEF6YbfRkjkl+ukfFE8mpWWZ2bw/jE51plx4g3KpnbbfQvzUtttc2bp tl8daf6lQjeaD2QTLkdq78N08f2LDNJHL5IAL2ev/pQsjdmNPxj7pHHX4flL6Ig2cljf rrRA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=aGC+/IWuWBRpqe+yYopyg4Shsr9fKLlcqMfJr5NkoRA=; b=G5BARJnKim8Skibr3lQXEFDP/Ejr5XdnircpLKowvl2Bhuu7f8nFKHvDWTjVZMol2F ssGgXjnMq0pFKaLqxVc6IMR9ex52CLUmuzz4J2nf6xvHfj5J2kSuQxGVTG6A9XiknJYV HwnBsl2DMc/OwmUxCQoGBvFvKQ2O8O4gipmFDGu8pa6GplpmMH+0cdrv4y4oABjpOlXz I9RDT8hazc6KDBXVTmQmtk7IHSBNDWBO4QqvPphR96weCpcwDuchczCexOvQ5vMZrKzf cLdscwlhJP5BsVjrHc8fFkBYOGnui0s10WRDqSGcJu9jlI1oq34i41KJ7ujutdzh+h5X DDCA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id n10-v6si5951773plk.689.2018.04.05.10.01.01; Thu, 05 Apr 2018 10:01:02 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752049AbeDERAq (ORCPT + 29 others); Thu, 5 Apr 2018 13:00:46 -0400 Received: from foss.arm.com ([217.140.101.70]:57352 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751363AbeDEQ6z (ORCPT ); Thu, 5 Apr 2018 12:58:55 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 584AB165C; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 2A4943F5B1; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id C15781AE55A3; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 04/10] locking/qspinlock: Use atomic_cond_read_acquire Date: Thu, 5 Apr 2018 17:59:01 +0100 Message-Id: <1522947547-24081-5-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Rather than dig into the counter field of the atomic_t inside the qspinlock structure so that we can call smp_cond_load_acquire, use atomic_cond_read_acquire instead, which operates on the atomic_t directly. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index cdfa7b7328a8..291e1526d27b 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -331,8 +331,8 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * barriers. */ if (val & _Q_LOCKED_MASK) - smp_cond_load_acquire(&lock->val.counter, - !(VAL & _Q_LOCKED_MASK)); + atomic_cond_read_acquire(&lock->val, + !(VAL & _Q_LOCKED_MASK)); /* * take ownership and clear the pending bit. * @@ -433,8 +433,8 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * * The PV pv_wait_head_or_lock function, if active, will acquire * the lock and return a non-zero value. So we have to skip the - * smp_cond_load_acquire() call. As the next PV queue head hasn't been - * designated yet, there is no way for the locked value to become + * atomic_cond_read_acquire() call. As the next PV queue head hasn't + * been designated yet, there is no way for the locked value to become * _Q_SLOW_VAL. So both the set_locked() and the * atomic_cmpxchg_relaxed() calls will be safe. * @@ -444,7 +444,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) if ((val = pv_wait_head_or_lock(lock, node))) goto locked; - val = smp_cond_load_acquire(&lock->val.counter, !(VAL & _Q_LOCKED_PENDING_MASK)); + val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK)); locked: /* @@ -461,7 +461,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) /* In the PV case we might already have _Q_LOCKED_VAL set */ if ((val & _Q_TAIL_MASK) == tail) { /* - * The smp_cond_load_acquire() call above has provided the + * The atomic_cond_read_acquire() call above has provided the * necessary acquire semantics required for locking. */ old = atomic_cmpxchg_relaxed(&lock->val, val, _Q_LOCKED_VAL); From patchwork Thu Apr 5 16:59:02 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132871 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6520951ljb; Thu, 5 Apr 2018 10:00:08 -0700 (PDT) X-Google-Smtp-Source: AIpwx4/5ifwkFE+fTVLweKzI7BXCpkC5CrpH+EAo5tDiR40Mgx21B1DIgToREXOzrNoDr042nyFT X-Received: by 10.101.75.66 with SMTP id k2mr15297689pgt.66.1522947608489; Thu, 05 Apr 2018 10:00:08 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947608; cv=none; d=google.com; s=arc-20160816; b=OGQZyHax+UUDoJSWW6RC5OLctrl8aK6FABZ7ABF3iLUSWsNH5zPTy3SDTZeLzlxPTv EMOK5KBYgC9sO6zYZeqi/z3CE98nCBjV2GoFr7d825QgHXqU2pirpTM+ncdN6LVpbSi0 DLdk7PIDH4n0jPTGmRBTX4KV0g9re4kUVHhcvKK1OeaM86WAarAGngIF4g+kEHd0H97K FX+GUc6JRjzNa3MWfnCB6clowctJK0oMBLQGYiR2dihVMUjpvXQoFUYOGnsXckGFhmFS FNb5Qrb3fo9qRc0UZDw5VK4l3eFtR9Lj4yAhvsEwMl4SSD6Dc1hbEHDEbTnWFPLNFg10 xciA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=irkULNHmtNPgNAdekth1s68Hkl75EPNE3ReOorX3J4o=; b=Q4GXNaAy06AgwzDUcnFPdfJ90fX8frcjzA1+eDDZi9vUj96aP5HQfrwZZL463kDDKR +LjlgbwU0qF6b9ds668pv4amTj81KLADS+kf50Z5AncgfMM3RmTYLLNNjv1nSxziLHk5 Qh1VKIKzwtQ1c6uh23KX7kRcF1N//h1w/K3AmuyjnaGwqdPj3wEndHZ3n0S8jVrJETSA kJ3noZiBFAV+cFm2AW/L9nBs5DTWwEfeqhEmItHLl6vyyggULA+WbVYNtTmaSzRUKxdl n6uRALHJgOD3yAFH9YoCUEa/xkC6U+e+1wQmHxDQhLEIu4gyNX6NdWpVXBeh67/4aSnS /n9g== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id o5-v6si6400875pll.667.2018.04.05.10.00.08; Thu, 05 Apr 2018 10:00:08 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752014AbeDERAF (ORCPT + 29 others); Thu, 5 Apr 2018 13:00:05 -0400 Received: from foss.arm.com ([217.140.101.70]:57372 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751392AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 0C69C1684; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id D175C3F5B1; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id D3C711AE55A6; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Jason Low , Will Deacon Subject: [PATCH 05/10] locking/mcs: Use smp_cond_load_acquire() in mcs spin loop Date: Thu, 5 Apr 2018 17:59:02 +0100 Message-Id: <1522947547-24081-6-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Jason Low For qspinlocks on ARM64, we would like to use WFE instead of purely spinning. Qspinlocks internally have lock contenders spin on an MCS lock. Update arch_mcs_spin_lock_contended() such that it uses the new smp_cond_load_acquire() so that ARM64 can also override this spin loop with its own implementation using WFE. On x86, this can also be cheaper than spinning on smp_load_acquire(). Signed-off-by: Jason Low Signed-off-by: Will Deacon --- kernel/locking/mcs_spinlock.h | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) -- 2.1.4 diff --git a/kernel/locking/mcs_spinlock.h b/kernel/locking/mcs_spinlock.h index f046b7ce9dd6..5e10153b4d3c 100644 --- a/kernel/locking/mcs_spinlock.h +++ b/kernel/locking/mcs_spinlock.h @@ -23,13 +23,15 @@ struct mcs_spinlock { #ifndef arch_mcs_spin_lock_contended /* - * Using smp_load_acquire() provides a memory barrier that ensures - * subsequent operations happen after the lock is acquired. + * Using smp_cond_load_acquire() provides the acquire semantics + * required so that subsequent operations happen after the + * lock is acquired. Additionally, some architectures such as + * ARM64 would like to do spin-waiting instead of purely + * spinning, and smp_cond_load_acquire() provides that behavior. */ #define arch_mcs_spin_lock_contended(l) \ do { \ - while (!(smp_load_acquire(l))) \ - cpu_relax(); \ + smp_cond_load_acquire(l, VAL); \ } while (0) #endif From patchwork Thu Apr 5 16:59:03 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132873 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6521485ljb; Thu, 5 Apr 2018 10:00:34 -0700 (PDT) X-Google-Smtp-Source: AIpwx49lafJiZdUs07YjxMAY0i7ABh3Ro+TCpKVQaXOU4GFeOICHR9HhM/2el8dsc0wysEqZvHxF X-Received: by 10.98.73.214 with SMTP id r83mr17862932pfi.76.1522947634311; Thu, 05 Apr 2018 10:00:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947634; cv=none; d=google.com; s=arc-20160816; b=AANccoiADOxDXh023MYU80dp8e8GyzDGjVKxiAG0Lrl66zfx/99RZzHYRXbgsNdTR/ AnQ1gnaqFeCzLwscIl744+yje+DFw8pJCfGxe2YjwQZKfH9lYa5YnIGgZplnkxvDAkrX HqY7QJxGJF3iVxdrCELpjz75FW2uqGchnMSWjVnrkmTOOhdpz4/Yk+sRSFuRdstE5ofw x4NUz+D8BAmPnBq6i6oJSXJH4krzwqbQVHeSsAz9zGVhcKoiEHAvddJAjwCPrOQzNhGZ Qz8apTy1ILBLD3xf6yaI49eBXxrh+A/O5XjnAy2VA4PtMNRPjgo2Zra4ORddnEuKTedB HrBA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=Rrf0RML/T5OFaLbrRAtnAfQ0xdG6DHae23xzfq0+onA=; b=KCpuZLC31920WLfVVB3AbKvOH3H6IWQ0FwaKhWvizZVXsotcWEWKHESNo6ZmDtVnoH gxEt/+pH7w7h5dfUrXChnjdpimA+VXP3tOWeXldcsl1bww/FY8ELCcKIqj/iRcTH0DsO MILbeeddo1PxfeggGiSpis3refeSSSg5DlhVoE+7lNprn6Pk8Cd8wfj/MeVtN7hQxTwF kbtINp+fIeupq6ckd4b8vepiuFisDO1sFxQziPhpJoOriuKOMKjuVw0OcFw9SXzZTg07 jJAQcnDW3nF8L+qBq+rgE/SFmKho/PD+PmN/7Ub6SHklqt4iTwztU74QoIxVrg4XlZpX gjXQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id s2-v6si6306213plq.353.2018.04.05.10.00.34; Thu, 05 Apr 2018 10:00:34 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751645AbeDERAb (ORCPT + 29 others); Thu, 5 Apr 2018 13:00:31 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:57368 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751389AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 020CB165D; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id C85293F25D; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id E2CB11AE55A7; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 06/10] barriers: Introduce smp_cond_load_relaxed and atomic_cond_read_relaxed Date: Thu, 5 Apr 2018 17:59:03 +0100 Message-Id: <1522947547-24081-7-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Whilst we currently provide smp_cond_load_acquire and atomic_cond_read_acquire, there are cases where the ACQUIRE semantics are not required because of a subsequent fence or release operation once the conditional loop has exited. This patch adds relaxed versions of the conditional spinning primitives to avoid unnecessary barrier overhead on architectures such as arm64. Signed-off-by: Will Deacon --- include/asm-generic/barrier.h | 27 +++++++++++++++++++++------ include/linux/atomic.h | 2 ++ 2 files changed, 23 insertions(+), 6 deletions(-) -- 2.1.4 diff --git a/include/asm-generic/barrier.h b/include/asm-generic/barrier.h index fe297b599b0a..305e03b19a26 100644 --- a/include/asm-generic/barrier.h +++ b/include/asm-generic/barrier.h @@ -221,18 +221,17 @@ do { \ #endif /** - * smp_cond_load_acquire() - (Spin) wait for cond with ACQUIRE ordering + * smp_cond_load_relaxed() - (Spin) wait for cond with no ordering guarantees * @ptr: pointer to the variable to wait on * @cond: boolean expression to wait for * - * Equivalent to using smp_load_acquire() on the condition variable but employs - * the control dependency of the wait to reduce the barrier on many platforms. + * Equivalent to using READ_ONCE() on the condition variable. * * Due to C lacking lambda expressions we load the value of *ptr into a * pre-named variable @VAL to be used in @cond. */ -#ifndef smp_cond_load_acquire -#define smp_cond_load_acquire(ptr, cond_expr) ({ \ +#ifndef smp_cond_load_relaxed +#define smp_cond_load_relaxed(ptr, cond_expr) ({ \ typeof(ptr) __PTR = (ptr); \ typeof(*ptr) VAL; \ for (;;) { \ @@ -241,10 +240,26 @@ do { \ break; \ cpu_relax(); \ } \ - smp_acquire__after_ctrl_dep(); \ VAL; \ }) #endif +/** + * smp_cond_load_acquire() - (Spin) wait for cond with ACQUIRE ordering + * @ptr: pointer to the variable to wait on + * @cond: boolean expression to wait for + * + * Equivalent to using smp_load_acquire() on the condition variable but employs + * the control dependency of the wait to reduce the barrier on many platforms. + */ +#ifndef smp_cond_load_acquire +#define smp_cond_load_acquire(ptr, cond_expr) ({ \ + typeof(*ptr) _val; \ + _val = smp_cond_load_relaxed(ptr, cond_expr); \ + smp_acquire__after_ctrl_dep(); \ + _val; \ +}) +#endif + #endif /* !__ASSEMBLY__ */ #endif /* __ASM_GENERIC_BARRIER_H */ diff --git a/include/linux/atomic.h b/include/linux/atomic.h index 8b276fd9a127..01ce3997cb42 100644 --- a/include/linux/atomic.h +++ b/include/linux/atomic.h @@ -654,6 +654,7 @@ static inline int atomic_dec_if_positive(atomic_t *v) } #endif +#define atomic_cond_read_relaxed(v, c) smp_cond_load_relaxed(&(v)->counter, (c)) #define atomic_cond_read_acquire(v, c) smp_cond_load_acquire(&(v)->counter, (c)) #ifdef CONFIG_GENERIC_ATOMIC64 @@ -1075,6 +1076,7 @@ static inline long long atomic64_fetch_andnot_release(long long i, atomic64_t *v } #endif +#define atomic64_cond_read_relaxed(v, c) smp_cond_load_relaxed(&(v)->counter, (c)) #define atomic64_cond_read_acquire(v, c) smp_cond_load_acquire(&(v)->counter, (c)) #include From patchwork Thu Apr 5 16:59:04 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132872 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6521114ljb; Thu, 5 Apr 2018 10:00:18 -0700 (PDT) X-Google-Smtp-Source: AIpwx49LsvxrqUJ/rRF1i8sRxXsh6Q5/0iDAk+tkPRUNh2FkJYLQoQDdisRiVolfkOwUom2n8YmE X-Received: by 2002:a17:902:d88a:: with SMTP id b10-v6mr13925355plz.172.1522947618666; Thu, 05 Apr 2018 10:00:18 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947618; cv=none; d=google.com; s=arc-20160816; b=LteDwDQq9XSh342ZXaHzBuWTAhrzPLGoUiogtrssYNYhZF+CH1nbzo5l9lqoTMZ55s PuvKH7x5+BxoJSMQEEHtgxG1Xq61Sweujd+VuaTKA1n4Mzq0BKLysfaXWrlDRXhb+16e Xd836XfQMVzC4P4bBe6/op0lx39h3dGRR+T+YEncnBX5wJkFORof2ti5+vSAmJJMlgtf OERwbkhty4Eip+We+4IOxCcYx1Hyz4AP2zZ9cDxoZsWpbmvOGLz0vHJPPrjf04I/6+tC TVGV36S5TsKW9xqkjoyrp5ISmvR0zzoNfaQKPNFhd7sHNF+yOe/2p86ve1C+9iQxTS4W fg6g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=WsiWjn4m3F5hpl1lY0xSgbFVq1KRUeIlMsuWixvPx8o=; b=ZTf0Q18K9c5BX2Ialog9YXdGpaocaTr6EqydRMFI9BohXJX1/PNh61X8gW3LGHyS+L ozjRZF+94j+iC7VLBFG0m4Cyn6T6Ojrn/RlePPwNjgwIDIZDkbMq9Y+ljQafBXCwBp21 /qKkX3SWFYZC0eS5tLeZjxTpLMY9xC5HlhY3HPnahfTmUNTDCNKLsxtyIBXo2eNLlRrV 1zZqT5hbHAjEYAyfrgHmkW4Se18eNizeQwGoXAjxHAj9U+f73sUjUhOrQ1QYZO0DVarr 74VBgrEUH60Wk1Fe4xeexLQGFDEHjcguvwgpGYOicnarO+iiLwleipOnLcaC+6sBCyap cNZQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id o5-v6si6400875pll.667.2018.04.05.10.00.18; Thu, 05 Apr 2018 10:00:18 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751974AbeDERAE (ORCPT + 29 others); Thu, 5 Apr 2018 13:00:04 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:57378 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751401AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 14F2E1688; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id DAB163F5C1; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 02CD81AE55A8; Thu, 5 Apr 2018 17:59:08 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 07/10] locking/qspinlock: Use smp_cond_load_relaxed to wait for next node Date: Thu, 5 Apr 2018 17:59:04 +0100 Message-Id: <1522947547-24081-8-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org When a locker reaches the head of the queue and takes the lock, a concurrent locker may enqueue and force the lock holder to spin whilst its node->next field is initialised. Rather than open-code a READ_ONCE/cpu_relax() loop, this can be implemented using smp_cond_load_relaxed instead. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 291e1526d27b..c8b57d375b49 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -475,10 +475,8 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) /* * contended path; wait for next if not observed yet, release. */ - if (!next) { - while (!(next = READ_ONCE(node->next))) - cpu_relax(); - } + if (!next) + next = smp_cond_load_relaxed(&node->next, (VAL)); arch_mcs_spin_unlock_contended(&next->locked); pv_kick_node(lock, next); From patchwork Thu Apr 5 16:59:05 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132868 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6520356ljb; Thu, 5 Apr 2018 09:59:31 -0700 (PDT) X-Google-Smtp-Source: AIpwx494Est7/+dpJjEet5UfGBXOUBhi/XeGEua0OOlX8795uki2cAqWqDGSKpa7KtUyZuxhTMiw X-Received: by 10.101.78.8 with SMTP id r8mr8147055pgt.343.1522947571330; Thu, 05 Apr 2018 09:59:31 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947571; cv=none; d=google.com; s=arc-20160816; b=p7AhfObmvx75wVqGaoPbSHaVHebHIH+dkIHiX1zlO0bEmHKu/G/uAqGSE52+VCc2+I 5bNLlhu0DLcn90pzYCE7H1eWyw8YbXWW9VvxdpUpokboiyvxqvXJUUsOAjYy9gZu9Lha G16crrM63/G1vmTB2i8JoAi3CN1343fgyD29vgBIe3AfUsl34gWWkhrgqEVD75EHAVL3 m1yvGXZe3CLjLJhAKAzoQl8onN3BqNuPG5+84YPr87N8Hvl7JU3WYvjdT60sb2m0G1Z/ 6FOGI3M/bCZ9ngtg2b7OynJ7iSrJKlDGbuB/NAFE4i6ht4gfq23TKEarfYMOSbnLwm7W GI8Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=HISKFdXhXolpgcR10X/kA+LKCeD/VmAI1BfSbbtNGFk=; b=FuzG2mx4GvOqxJNqlyUnssE9ZVWNR64zj7dAY4cVRRAeLwq2Z+3tJQYdWki7/I6rfu /GA7PuDWqVdiTNn02vtm6gA9TkGKwPSMjhcY7a0c/7mnzGF1XD/MShbMHPIP2uamseO5 wAyApANAEpq+twEo4KwvRYkWUdfRE/XXEnPV5s6lcHbsFNWb/gIeA0UAYZBIP4MiJnG5 t3O5CHFu2GoRBbhoTKD1q+eASh9IavMnq8eaPXteKHLWzoEQrlFCjCS3YhInNkpR8kc4 6srLceUgfA2xj1YLaccadMyvutVVBq2u1slQcQzvuSuwZJ2cr7aiRybYW0Wa7El6TIl5 il1g== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id 34-v6si3750982plp.543.2018.04.05.09.59.31; Thu, 05 Apr 2018 09:59:31 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751913AbeDEQ70 (ORCPT + 29 others); Thu, 5 Apr 2018 12:59:26 -0400 Received: from usa-sjc-mx-foss1.foss.arm.com ([217.140.101.70]:57390 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751415AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 21E91168F; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id E46403F7D7; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 1143D1AE55A9; Thu, 5 Apr 2018 17:59:09 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 08/10] locking/qspinlock: Merge struct __qspinlock into struct qspinlock Date: Thu, 5 Apr 2018 17:59:05 +0100 Message-Id: <1522947547-24081-9-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org struct __qspinlock provides a handy union of fields so that subcomponents of the lockword can be accessed by name, without having to manage shifts and masks explicitly and take endianness into account. This is useful in qspinlock.h and also potentially in arch headers, so move the struct __qspinlock into struct qspinlock and kill the extra definition. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- arch/x86/include/asm/qspinlock.h | 2 +- arch/x86/include/asm/qspinlock_paravirt.h | 3 +- include/asm-generic/qspinlock_types.h | 32 +++++++++++++++++++-- kernel/locking/qspinlock.c | 46 ++----------------------------- kernel/locking/qspinlock_paravirt.h | 34 ++++++++--------------- 5 files changed, 46 insertions(+), 71 deletions(-) -- 2.1.4 Acked-by: Boqun Feng diff --git a/arch/x86/include/asm/qspinlock.h b/arch/x86/include/asm/qspinlock.h index 5e16b5d40d32..90b0b0ed8161 100644 --- a/arch/x86/include/asm/qspinlock.h +++ b/arch/x86/include/asm/qspinlock.h @@ -16,7 +16,7 @@ */ static inline void native_queued_spin_unlock(struct qspinlock *lock) { - smp_store_release((u8 *)lock, 0); + smp_store_release(&lock->locked, 0); } #ifdef CONFIG_PARAVIRT_SPINLOCKS diff --git a/arch/x86/include/asm/qspinlock_paravirt.h b/arch/x86/include/asm/qspinlock_paravirt.h index 923307ea11c7..9ef5ee03d2d7 100644 --- a/arch/x86/include/asm/qspinlock_paravirt.h +++ b/arch/x86/include/asm/qspinlock_paravirt.h @@ -22,8 +22,7 @@ PV_CALLEE_SAVE_REGS_THUNK(__pv_queued_spin_unlock_slowpath); * * void __pv_queued_spin_unlock(struct qspinlock *lock) * { - * struct __qspinlock *l = (void *)lock; - * u8 lockval = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0); + * u8 lockval = cmpxchg(&lock->locked, _Q_LOCKED_VAL, 0); * * if (likely(lockval == _Q_LOCKED_VAL)) * return; diff --git a/include/asm-generic/qspinlock_types.h b/include/asm-generic/qspinlock_types.h index 034acd0c4956..0763f065b975 100644 --- a/include/asm-generic/qspinlock_types.h +++ b/include/asm-generic/qspinlock_types.h @@ -29,13 +29,41 @@ #endif typedef struct qspinlock { - atomic_t val; + union { + atomic_t val; + + /* + * By using the whole 2nd least significant byte for the + * pending bit, we can allow better optimization of the lock + * acquisition for the pending bit holder. + */ +#ifdef __LITTLE_ENDIAN + struct { + u8 locked; + u8 pending; + }; + struct { + u16 locked_pending; + u16 tail; + }; +#else + struct { + u16 tail; + u16 locked_pending; + }; + struct { + u8 reserved[2]; + u8 pending; + u8 locked; + }; +#endif + }; } arch_spinlock_t; /* * Initializier */ -#define __ARCH_SPIN_LOCK_UNLOCKED { ATOMIC_INIT(0) } +#define __ARCH_SPIN_LOCK_UNLOCKED { .val = ATOMIC_INIT(0) } /* * Bitfields in the atomic value: diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index c8b57d375b49..3ad8786a47e2 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -114,40 +114,6 @@ static inline __pure struct mcs_spinlock *decode_tail(u32 tail) #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK) -/* - * By using the whole 2nd least significant byte for the pending bit, we - * can allow better optimization of the lock acquisition for the pending - * bit holder. - * - * This internal structure is also used by the set_locked function which - * is not restricted to _Q_PENDING_BITS == 8. - */ -struct __qspinlock { - union { - atomic_t val; -#ifdef __LITTLE_ENDIAN - struct { - u8 locked; - u8 pending; - }; - struct { - u16 locked_pending; - u16 tail; - }; -#else - struct { - u16 tail; - u16 locked_pending; - }; - struct { - u8 reserved[2]; - u8 pending; - u8 locked; - }; -#endif - }; -}; - #if _Q_PENDING_BITS == 8 /** * clear_pending_set_locked - take ownership and clear the pending bit. @@ -159,9 +125,7 @@ struct __qspinlock { */ static __always_inline void clear_pending_set_locked(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - - WRITE_ONCE(l->locked_pending, _Q_LOCKED_VAL); + WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL); } /* @@ -176,13 +140,11 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock) */ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) { - struct __qspinlock *l = (void *)lock; - /* * Use release semantics to make sure that the MCS node is properly * initialized before changing the tail code. */ - return (u32)xchg_release(&l->tail, + return (u32)xchg_release(&lock->tail, tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET; } @@ -237,9 +199,7 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) */ static __always_inline void set_locked(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - - WRITE_ONCE(l->locked, _Q_LOCKED_VAL); + WRITE_ONCE(lock->locked, _Q_LOCKED_VAL); } diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h index 6ee477765e6c..2711940429f5 100644 --- a/kernel/locking/qspinlock_paravirt.h +++ b/kernel/locking/qspinlock_paravirt.h @@ -87,8 +87,6 @@ struct pv_node { #define queued_spin_trylock(l) pv_hybrid_queued_unfair_trylock(l) static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - /* * Stay in unfair lock mode as long as queued mode waiters are * present in the MCS wait queue but the pending bit isn't set. @@ -97,7 +95,7 @@ static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock) int val = atomic_read(&lock->val); if (!(val & _Q_LOCKED_PENDING_MASK) && - (cmpxchg_acquire(&l->locked, 0, _Q_LOCKED_VAL) == 0)) { + (cmpxchg_acquire(&lock->locked, 0, _Q_LOCKED_VAL) == 0)) { qstat_inc(qstat_pv_lock_stealing, true); return true; } @@ -117,16 +115,12 @@ static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock) #if _Q_PENDING_BITS == 8 static __always_inline void set_pending(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - - WRITE_ONCE(l->pending, 1); + WRITE_ONCE(lock->pending, 1); } static __always_inline void clear_pending(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - - WRITE_ONCE(l->pending, 0); + WRITE_ONCE(lock->pending, 0); } /* @@ -136,10 +130,8 @@ static __always_inline void clear_pending(struct qspinlock *lock) */ static __always_inline int trylock_clear_pending(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; - - return !READ_ONCE(l->locked) && - (cmpxchg_acquire(&l->locked_pending, _Q_PENDING_VAL, + return !READ_ONCE(lock->locked) && + (cmpxchg_acquire(&lock->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL) == _Q_PENDING_VAL); } #else /* _Q_PENDING_BITS == 8 */ @@ -384,7 +376,6 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev) static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node) { struct pv_node *pn = (struct pv_node *)node; - struct __qspinlock *l = (void *)lock; /* * If the vCPU is indeed halted, advance its state to match that of @@ -413,7 +404,7 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node) * the hash table later on at unlock time, no atomic instruction is * needed. */ - WRITE_ONCE(l->locked, _Q_SLOW_VAL); + WRITE_ONCE(lock->locked, _Q_SLOW_VAL); (void)pv_hash(lock, pn); } @@ -428,7 +419,6 @@ static u32 pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node) { struct pv_node *pn = (struct pv_node *)node; - struct __qspinlock *l = (void *)lock; struct qspinlock **lp = NULL; int waitcnt = 0; int loop; @@ -479,13 +469,13 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node) * * Matches the smp_rmb() in __pv_queued_spin_unlock(). */ - if (xchg(&l->locked, _Q_SLOW_VAL) == 0) { + if (xchg(&lock->locked, _Q_SLOW_VAL) == 0) { /* * The lock was free and now we own the lock. * Change the lock value back to _Q_LOCKED_VAL * and unhash the table. */ - WRITE_ONCE(l->locked, _Q_LOCKED_VAL); + WRITE_ONCE(lock->locked, _Q_LOCKED_VAL); WRITE_ONCE(*lp, NULL); goto gotlock; } @@ -493,7 +483,7 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node) WRITE_ONCE(pn->state, vcpu_hashed); qstat_inc(qstat_pv_wait_head, true); qstat_inc(qstat_pv_wait_again, waitcnt); - pv_wait(&l->locked, _Q_SLOW_VAL); + pv_wait(&lock->locked, _Q_SLOW_VAL); /* * Because of lock stealing, the queue head vCPU may not be @@ -518,7 +508,6 @@ pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node) __visible void __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked) { - struct __qspinlock *l = (void *)lock; struct pv_node *node; if (unlikely(locked != _Q_SLOW_VAL)) { @@ -547,7 +536,7 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked) * Now that we have a reference to the (likely) blocked pv_node, * release the lock. */ - smp_store_release(&l->locked, 0); + smp_store_release(&lock->locked, 0); /* * At this point the memory pointed at by lock can be freed/reused, @@ -573,7 +562,6 @@ __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked) #ifndef __pv_queued_spin_unlock __visible void __pv_queued_spin_unlock(struct qspinlock *lock) { - struct __qspinlock *l = (void *)lock; u8 locked; /* @@ -581,7 +569,7 @@ __visible void __pv_queued_spin_unlock(struct qspinlock *lock) * unhash. Otherwise it would be possible to have multiple @lock * entries, which would be BAD. */ - locked = cmpxchg_release(&l->locked, _Q_LOCKED_VAL, 0); + locked = cmpxchg_release(&lock->locked, _Q_LOCKED_VAL, 0); if (likely(locked == _Q_LOCKED_VAL)) return; From patchwork Thu Apr 5 16:59:06 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132870 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6520666ljb; Thu, 5 Apr 2018 09:59:51 -0700 (PDT) X-Google-Smtp-Source: AIpwx48lkWTUeZqzl7lePCiO9Hj6aTyB1PGCLU382OrsNJt2Qxd5g5k0gwjMZdsyVxnsq+pFzdk3 X-Received: by 2002:a17:902:3341:: with SMTP id a59-v6mr23636132plc.68.1522947591584; Thu, 05 Apr 2018 09:59:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947591; cv=none; d=google.com; s=arc-20160816; b=TXuJ6tRo1A66oQ0tiAwj2mjzEj6b77zhrYZsavO6X5twWCDhBhTB6Y1lpo1Vm15PGE 9yp0rrLl2aq0hLWGhUL3MxxJvaNL/LPqJhnvBdq8GZRmasuTEruR7JDMM3WdgFmbK3Av XEBn7teXIKazo7p0QmmmBbkR9LZslv2dBf/jwqTvX45nkfDceGy755ItMvEOs9alVegZ qGrBLeSAE6DANn//zq56zSBcVlYs0UTjQ7KTNIJtsjX8MwxEcsjSSCxAoM1t2UZNRr+B 8nP12rBumnfZJc1js0U8DDwBt/eicgAnfSrRGNkhiHQhlqFBJ3T9AdKMwiN9V7TX/FZm YD0Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=rLT3J5NT3Po6sGkKekSQxoftE0EryCGY3wZKvMbGpfQ=; b=vvbP8ObF2kjH4Qh/8r9y8+jj94D2eF3mt3uhP7v1sWgqnNo3TZ9+weWoSIOIyGKuqn eCwCoRGM+bCkCoswfRI1G6b3Kj98MPEqXDz9VuJhs72QyKTawKFJv+PnlpbKEjNPGf+7 6kuyoqjf9He9Wt+Ox1MA/5U/jXYQsB/T7v9XPRhzvBFaScTRTQHkrZHw2riq6E4CUVGL thWrB+mi2RPmaesTisOj7TAcn4ZxHwsT56j1btMDApqoIIhVOFoCyvFJei0fhRMnoNTO W5VrdlV0vqpOj2UW+iA5SLEz/D8FTs5xXdpnEynS06j4V+8SVmXkAwL99DpaqrFhQPNp Yirg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id p64si5706075pga.492.2018.04.05.09.59.51; Thu, 05 Apr 2018 09:59:51 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751759AbeDEQ7W (ORCPT + 29 others); Thu, 5 Apr 2018 12:59:22 -0400 Received: from foss.arm.com ([217.140.101.70]:57396 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751461AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 25D9316A3; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id ECCEC3F7DB; Thu, 5 Apr 2018 09:58:55 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 1F8AC1AE55AA; Thu, 5 Apr 2018 17:59:09 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 09/10] locking/qspinlock: Make queued_spin_unlock use smp_store_release Date: Thu, 5 Apr 2018 17:59:06 +0100 Message-Id: <1522947547-24081-10-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org A qspinlock can be unlocked simply by writing zero to the locked byte. This can be implemented in the generic code, so do that and remove the arch-specific override for x86 in the !PV case. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- arch/x86/include/asm/qspinlock.h | 17 ++++++----------- include/asm-generic/qspinlock.h | 2 +- 2 files changed, 7 insertions(+), 12 deletions(-) -- 2.1.4 diff --git a/arch/x86/include/asm/qspinlock.h b/arch/x86/include/asm/qspinlock.h index 90b0b0ed8161..cc77cbb01432 100644 --- a/arch/x86/include/asm/qspinlock.h +++ b/arch/x86/include/asm/qspinlock.h @@ -7,6 +7,12 @@ #include #include +#ifdef CONFIG_PARAVIRT_SPINLOCKS +extern void native_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val); +extern void __pv_init_lock_hash(void); +extern void __pv_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val); +extern void __raw_callee_save___pv_queued_spin_unlock(struct qspinlock *lock); + #define queued_spin_unlock queued_spin_unlock /** * queued_spin_unlock - release a queued spinlock @@ -19,12 +25,6 @@ static inline void native_queued_spin_unlock(struct qspinlock *lock) smp_store_release(&lock->locked, 0); } -#ifdef CONFIG_PARAVIRT_SPINLOCKS -extern void native_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val); -extern void __pv_init_lock_hash(void); -extern void __pv_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val); -extern void __raw_callee_save___pv_queued_spin_unlock(struct qspinlock *lock); - static inline void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) { pv_queued_spin_lock_slowpath(lock, val); @@ -40,11 +40,6 @@ static inline bool vcpu_is_preempted(long cpu) { return pv_vcpu_is_preempted(cpu); } -#else -static inline void queued_spin_unlock(struct qspinlock *lock) -{ - native_queued_spin_unlock(lock); -} #endif #ifdef CONFIG_PARAVIRT diff --git a/include/asm-generic/qspinlock.h b/include/asm-generic/qspinlock.h index b37b4ad7eb94..a8ed0a352d75 100644 --- a/include/asm-generic/qspinlock.h +++ b/include/asm-generic/qspinlock.h @@ -100,7 +100,7 @@ static __always_inline void queued_spin_unlock(struct qspinlock *lock) /* * unlock() needs release semantics: */ - (void)atomic_sub_return_release(_Q_LOCKED_VAL, &lock->val); + smp_store_release(&lock->locked, 0); } #endif From patchwork Thu Apr 5 16:59:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 132869 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp6520518ljb; Thu, 5 Apr 2018 09:59:42 -0700 (PDT) X-Google-Smtp-Source: AIpwx49B+i2kWjGOUMqk7MEQmSXeKqHAn7zRBPp6R6GaeMEjOVzHPjWp4TD4XhHdLuR9VLm32c48 X-Received: by 2002:a17:902:e81:: with SMTP id 1-v6mr24486768plx.158.1522947582000; Thu, 05 Apr 2018 09:59:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1522947581; cv=none; d=google.com; s=arc-20160816; b=DUDJHnrrSX/7YuDH22h3MCsDWe3zhD/MXjfyUwDf41BrTSC/OGU3c+Nosbx50AJxPA Ftq3HuwwxCOKgoVRxfeuY7lIvTxGg2bMLjL9hPiRkvBZtBlT2M90uLhflYD2Xz6xwVic bkMxyYhnyg5V2n6sZY20N6sqaQEt92AV9CyO1pREb3Q2+UjXISTJhyNxloYbDV3iAxmP 8jXf6rVm7qJI4tOo5A/kIy2orNTzz98SvNC06azQxJLklfSvo12GJSCBUj3UuhKm8sov xfEd87YNrjLDtlwkt9JE0d9ugq6kYGoFxD34M5N++P9D53X9yt4zbz/v2HOwBLKr4w6A m4BQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=7meFwI0hsLGAO8hGmKmgQ28G1uBBJm6cf4uagWRfbkU=; b=RZi2Y7zpTbZIaux2stuNc8/x/2AB5n+7NlKjXnDmOhTbEtV0ePiMewiRc6A5+7g3nk oPoxzeWoA8A4vsapnC00kRJ3zonfibLmMgHE91KyHCRVlQhEO12/bGTRfQykIfrjzv2S Spm/p4XD6qKaa3aATSLowt+Db5jmk5Ym/Ojm3v+0sbu+Mx0nN2RGNHCICji+Is6bg4NS OYWE4Heibg/GmrsDLnYDsUcJ1QSxrHERQ6G9KlBMS5mshq3lsuAcWFj/hnanvV6CGGtE XO6lJdgD5mbV1g2CUBleSjpf0I8hat6m2lE+F2yj5SkLfY3fl8asSsR4xRBw7f45azDY i+Dg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id p64si5706075pga.492.2018.04.05.09.59.41; Thu, 05 Apr 2018 09:59:41 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751849AbeDEQ7Z (ORCPT + 29 others); Thu, 5 Apr 2018 12:59:25 -0400 Received: from foss.arm.com ([217.140.101.70]:57404 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751469AbeDEQ64 (ORCPT ); Thu, 5 Apr 2018 12:58:56 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 2F6DB16BA; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: from edgewater-inn.cambridge.arm.com (usa-sjc-imap-foss1.foss.arm.com [10.72.51.249]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 01D353F7F3; Thu, 5 Apr 2018 09:58:56 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 306311AE55AC; Thu, 5 Apr 2018 17:59:09 +0100 (BST) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: linux-arm-kernel@lists.infradead.org, peterz@infradead.org, mingo@kernel.org, boqun.feng@gmail.com, paulmck@linux.vnet.ibm.com, catalin.marinas@arm.com, Will Deacon Subject: [PATCH 10/10] locking/qspinlock: Elide back-to-back RELEASE operations with smp_wmb() Date: Thu, 5 Apr 2018 17:59:07 +0100 Message-Id: <1522947547-24081-11-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1522947547-24081-1-git-send-email-will.deacon@arm.com> References: <1522947547-24081-1-git-send-email-will.deacon@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The qspinlock slowpath must ensure that the MCS node is fully initialised before it can be reached by another other CPU. This is currently enforced by using a RELEASE operation when updating the tail and also when linking the node into the waitqueue (since the control dependency off xchg_tail is insufficient to enforce sufficient ordering -- see 95bcade33a8a ("locking/qspinlock: Ensure node is initialised before updating prev->next")). Back-to-back RELEASE operations may be expensive on some architectures, particularly those that implement them using fences under the hood. We can replace the two RELEASE operations with a single smp_wmb() fence and use RELAXED operations for the subsequent publishing of the node. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 3ad8786a47e2..42c61f7b37c5 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -141,10 +141,10 @@ static __always_inline void clear_pending_set_locked(struct qspinlock *lock) static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) { /* - * Use release semantics to make sure that the MCS node is properly - * initialized before changing the tail code. + * We can use relaxed semantics since the caller ensures that the + * MCS node is properly initialized before updating the tail. */ - return (u32)xchg_release(&lock->tail, + return (u32)xchg_relaxed(&lock->tail, tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET; } @@ -178,10 +178,11 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail) for (;;) { new = (val & _Q_LOCKED_PENDING_MASK) | tail; /* - * Use release semantics to make sure that the MCS node is - * properly initialized before changing the tail code. + * We can use relaxed semantics since the caller ensures that + * the MCS node is properly initialized before updating the + * tail. */ - old = atomic_cmpxchg_release(&lock->val, val, new); + old = atomic_cmpxchg_relaxed(&lock->val, val, new); if (old == val) break; @@ -340,12 +341,17 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) goto release; /* + * Ensure that the initialisation of @node is complete before we + * publish the updated tail and potentially link @node into the + * waitqueue. + */ + smp_wmb(); + + /* * We have already touched the queueing cacheline; don't bother with * pending stuff. * * p,*,* -> n,*,* - * - * RELEASE, such that the stores to @node must be complete. */ old = xchg_tail(lock, tail); next = NULL; @@ -356,15 +362,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) */ if (old & _Q_TAIL_MASK) { prev = decode_tail(old); - - /* - * We must ensure that the stores to @node are observed before - * the write to prev->next. The address dependency from - * xchg_tail is not sufficient to ensure this because the read - * component of xchg_tail is unordered with respect to the - * initialisation of @node. - */ - smp_store_release(&prev->next, node); + WRITE_ONCE(prev->next, node); pv_wait_node(node, prev); arch_mcs_spin_lock_contended(&node->locked);