From patchwork Wed Apr 11 18:01:09 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 133161 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp896493ljb; Wed, 11 Apr 2018 11:02:34 -0700 (PDT) X-Google-Smtp-Source: AIpwx49+zo3J+UjF+4b38+lBqHICXEBC0Fn9AzUdsxAOogaioV1OkLChmsZL7mkvMbfRr5Jv7wmw X-Received: by 2002:a17:902:864c:: with SMTP id y12-v6mr6050462plt.293.1523469754582; Wed, 11 Apr 2018 11:02:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1523469754; cv=none; d=google.com; s=arc-20160816; b=LTb9jjwRvneS6xQH7+oOcqXzo5NB4HJsXzPvVpiE8y0y0myRCVNJeoCTwuGl9uHd6T 2QNewt/0vZmRh3dNU77FRfHB/fIpEaNhG90jzXg4pNmWM+JkgiX583NFMqnFGigzXgCQ fugLzS3u22sSFwptzZZ8pDi9pnuBLxpGaqXZoUomuFbx6zb96w5HZY6BbZQMhtfHYBIr ImOajBzAusDnydOcRWk0GA3jhp3U9flpNRGYVhKc6DxLlZvS9w3+naaNvZ/l+p/5H7lS uHHSG0ALHYoGvGx8UnRsdCwC/9lfKiIHedW6Ed7vvnpu8mi+/qj4nwPQlhuBKDfNESi8 DKFA== 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=GziclgBxCVLrqFHp0zydwd1uHOP18mZDQqFYJx+XHeM=; b=LIGSpVToXJqlx8HrxdftZKc7vHg3O7T0GRGAPzpjOi2oatBhlW6Tiata9LijORmfnX 1Oo5f2xmoceEL4VVI6FqFfYMYtFdecOww7cNApXVkXSWlxwVIBBrrFIGAVu7UhgKHPNN n93lgP+26vHDcuA4p/ZHa2P7N23Wr5QW1vPbhLGYvr0H9u8jOad0F6lKFcSYMqeipvsm pHrUk8PQujroI32iV48mQHPyZRa8/xxtxxFABf9cGb+e5IzT2aL4AYCqNoGHSuxjKuBG xOC55Lda2dG0E/ZxxSydRKko8dc2C8h/toFG4QfGe2+jK5Zbskc+O/7KDYxGx9Tz5w5m rzAQ== 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 d10si1231452pfn.84.2018.04.11.11.02.34; Wed, 11 Apr 2018 11:02: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 S1752956AbeDKSBJ (ORCPT + 29 others); Wed, 11 Apr 2018 14:01:09 -0400 Received: from foss.arm.com ([217.140.101.70]:52088 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752527AbeDKSBG (ORCPT ); Wed, 11 Apr 2018 14:01:06 -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 5DC5A164F; Wed, 11 Apr 2018 11:01:06 -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 F382E3F614; Wed, 11 Apr 2018 11:01:05 -0700 (PDT) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 683351AE558F; Wed, 11 Apr 2018 19:01:21 +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, longman@redhat.com, Will Deacon Subject: [PATCH v2 02/13] locking/qspinlock: Bound spinning on pending->locked transition in slowpath Date: Wed, 11 Apr 2018 19:01:09 +0100 Message-Id: <1523469680-17699-3-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1523469680-17699-1-git-send-email-will.deacon@arm.com> References: <1523469680-17699-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. Rather than removing the pending->locked spinning from the slowpath altogether (which has been shown to heavily penalise a 2-threaded locking stress test on x86), this patch replaces the explicit spinning with a call to atomic_cond_read_relaxed and allows the architecture to provide a bound on the number of spins. For architectures that can respond to changes in cacheline state in their smp_cond_load implementation, it should be sufficient to use the default bound of 1. Cc: Peter Zijlstra Cc: Ingo Molnar Suggested-by: Waiman Long Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index d880296245c5..396701e8c62d 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -77,6 +77,18 @@ #endif /* + * The pending bit spinning loop count. + * This heuristic is used to limit the number of lockword accesses + * made by atomic_cond_read_relaxed when waiting for the lock to + * transition out of the "== _Q_PENDING_VAL" state. We don't spin + * indefinitely because there's no guarantee that we'll make forward + * progress. + */ +#ifndef _Q_PENDING_LOOPS +#define _Q_PENDING_LOOPS 1 +#endif + +/* * Per-CPU queue node structures; we can never have more than 4 nested * contexts: task, softirq, hardirq, nmi. * @@ -306,13 +318,15 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) return; /* - * wait for in-progress pending->locked hand-overs + * Wait for in-progress pending->locked hand-overs with a bounded + * number of spins so that we guarantee forward progress. * * 0,1,0 -> 0,0,1 */ if (val == _Q_PENDING_VAL) { - while ((val = atomic_read(&lock->val)) == _Q_PENDING_VAL) - cpu_relax(); + int cnt = _Q_PENDING_LOOPS; + val = atomic_cond_read_relaxed(&lock->val, + (VAL != _Q_PENDING_VAL) || !cnt--); } /*