From patchwork Tue Feb 13 13:22:56 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 128234 Delivered-To: patch@linaro.org Received: by 10.46.124.24 with SMTP id x24csp4249801ljc; Tue, 13 Feb 2018 05:23:27 -0800 (PST) X-Google-Smtp-Source: AH8x227D5KtdqWtWI4r9CV4uv0LfrnMnVcPbwtt1MqMcezl1y6or1SbM1Me/vvrEevyVtdEFbHfs X-Received: by 10.101.80.69 with SMTP id k5mr978773pgo.435.1518528206881; Tue, 13 Feb 2018 05:23:26 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1518528206; cv=none; d=google.com; s=arc-20160816; b=lulW4H3b2p1bUys/iZH0GJQ4CdFDrPBSro2UK6Dkbc3pclMwLATpAtCibhf7z7AgDL K9p1cFpEeLq0iLfATkLAxiTc5VX+BHwwG7uuWertGv45Wm14MJfwAqackrwhgL8oz//2 SM9jadH0/de+VVNXyFEGAdk5tP7bzDSgl/WZ+LGYtK99fchQKmPbBp4tz5M4/VdDvkV0 FlwoKPeyF9fEadZcVb/uBavJiui8i8xn34nSxOydAJecZ5RlaPNncl/MdCAynQSFcXAD 0VG7TwIPQBlTzDLJ+49OO7EmbnUuRt51cFNHOWSMK3H1A84E+IMGufG3trS2hplUCKQs WmAQ== 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=hwy+sNwuUEcMIrbMtrjBJeZvyM7AsIBvsMvy3EI0UR8=; b=IWT6n2C5Rdqdez6WBYWhjJwsu8UPgb3ZUL+1FLVavj2OPcqWBlUCAsgzFMJr+DeRJR /VeCWnglitRL0kJ9fL7ZnyIDQCx0/x9Kc/ZwX2JwXM80H6bD2BCSBUnYRw1k7loax7V1 9su2GGVvvV9LKJsj3QO5X+dHLZ2CndjI9XmUvgtaxTNtvEDVlmhiUIiZG7mcPDjzJoeR bg56ypjCR//VV491+Ladhokh9qwhv1eTJjS6i1z2fW4f5Qz+wRULepsCc7yLSNKO3Zku 2nq3fw4ROoj4FuCRQ1pX1ZLeWE+zDw3Vm7gF0FwVWBZLNYl0PhwrDJ4a2YcBtlMjFGcW LfHg== 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 h6-v6si1400595pln.198.2018.02.13.05.23.26; Tue, 13 Feb 2018 05:23:26 -0800 (PST) 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 S935343AbeBMNW6 (ORCPT + 27 others); Tue, 13 Feb 2018 08:22:58 -0500 Received: from foss.arm.com ([217.140.101.70]:57562 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S935118AbeBMNW5 (ORCPT ); Tue, 13 Feb 2018 08:22:57 -0500 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 E06C115AB; Tue, 13 Feb 2018 05:22:56 -0800 (PST) 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 B28DE3F58F; Tue, 13 Feb 2018 05:22:56 -0800 (PST) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 551BB1AE542F; Tue, 13 Feb 2018 13:23:03 +0000 (GMT) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: peterz@infradead.org, mingo@redhat.com, Will Deacon Subject: [PATCH 1/2] locking/qspinlock: Ensure node is initialised before updating prev->next Date: Tue, 13 Feb 2018 13:22:56 +0000 Message-Id: <1518528177-19169-2-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1518528177-19169-1-git-send-email-will.deacon@arm.com> References: <1518528177-19169-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 ends up queuing on the qspinlock locking slowpath, we initialise the relevant mcs node and publish it indirectly by updating the tail portion of the lock word using xchg_tail. If we find that there was a pre-existing locker in the queue, we subsequently update their ->next field to point at our node so that we are notified when it's our turn to take the lock. This can be roughly illustrated as follows: /* Initialise the fields in node and encode a pointer to node in tail */ tail = initialise_node(node); /* * Exchange tail into the lockword using an atomic read-modify-write * operation with release semantics */ old = xchg_tail(lock, tail); /* If there was a pre-existing waiter ... */ if (old & _Q_TAIL_MASK) { prev = decode_tail(old); smp_read_barrier_depends(); /* ... then update their ->next field to point to node. WRITE_ONCE(prev->next, node); } The conditional update of prev->next therefore relies on the address dependency from the result of xchg_tail ensuring order against the prior initialisation of node. However, since the release semantics of the xchg_tail operation apply only to the write portion of the RmW, then this ordering is not guaranteed and it is possible for the CPU to return old before the writes to node have been published, consequently allowing us to point prev->next to an uninitialised node. This patch fixes the problem by making the update of prev->next a RELEASE operation, which also removes the reliance on dependency ordering. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 38ece035039e..348c8cec1042 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -408,14 +408,15 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) */ if (old & _Q_TAIL_MASK) { prev = decode_tail(old); + /* - * The above xchg_tail() is also a load of @lock which - * generates, through decode_tail(), a pointer. The address - * dependency matches the RELEASE of xchg_tail() such that - * the subsequent access to @prev happens after. + * 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. */ - - WRITE_ONCE(prev->next, node); + smp_store_release(&prev->next, node); pv_wait_node(node, prev); arch_mcs_spin_lock_contended(&node->locked); From patchwork Tue Feb 13 13:22:57 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Will Deacon X-Patchwork-Id: 128232 Delivered-To: patch@linaro.org Received: by 10.46.124.24 with SMTP id x24csp4249503ljc; Tue, 13 Feb 2018 05:23:04 -0800 (PST) X-Google-Smtp-Source: AH8x227GWBwp07U5PP66+1exPRwFxMx0jxZ/Fu5IHzy+3EBxDmMjlX3HZMbJQeF+q0XR/ehmZDrT X-Received: by 10.99.43.73 with SMTP id r70mr1034371pgr.316.1518528184524; Tue, 13 Feb 2018 05:23:04 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1518528184; cv=none; d=google.com; s=arc-20160816; b=uzdlcWIalgdRyTf2c2KE2U4cfzPql011Iyy80vmA8Pc0m4tgvexmDX5U5QmKgTdE0I s4kFADebDLSSeA8ZLWLNQ3ufgZjNCWyb8gxb/BWDOyOJYyRCHSJVFgUv81wdZ/1/RAys VK8xxa1ckbfUJUUySU6x1COAhRDYmCw4YgPQkpO/BKUE05Tbr8tSPPcaBcSA2tTP6JgN aDwsH+SSBgVyJ7COPZPo/2RlCLj71b8BwzsNWjMaBD3lmrT/HYCpRQGmo5HXFXr08uA0 O3FsFGaGCvsPKNuR8B1xbzaMezM+OmEfi4Q/c28AuRrtp61wxFmjHRUf/y7DhlgHD8Bm UDSA== 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=sAHxaFj77Cfd93EzPNsc2iU/IqHSi6NswFyevHAaYdQ=; b=cyCMigIiFvT6dJrSOt2FUWV97d4I35wnu4RS3s5ezgrA8VVc/WvcCMKyECdEtUnO8H FH4W9qHHhxSyJKejlW0Lr4yl8xt2X15yZv5vVffOP+2P2b9wbXiaqAeDFitidoy5A52+ OeOt8EVbz55WXSxCNQm/o+IiVrwQglcjSmagchBAM6p+RlrSBy90EV1X5iGADivh7YuM 0djKoYw0FJ5OZoVUrqPEoidecAi16rdX2i63SOT5watLeS0//bD5PiBYF6F+OXx4s8hO x++phVT+iDnmlk8PU0OGSweur/3bHubZCawxJy9M5DTnN/gO/+wEVc4kPqNqWluvJA6Z pm5g== 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 v12si1220501pfl.330.2018.02.13.05.23.04; Tue, 13 Feb 2018 05:23:04 -0800 (PST) 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 S935385AbeBMNXB (ORCPT + 27 others); Tue, 13 Feb 2018 08:23:01 -0500 Received: from foss.arm.com ([217.140.101.70]:57574 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S935174AbeBMNW5 (ORCPT ); Tue, 13 Feb 2018 08:22:57 -0500 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 EF65815BF; Tue, 13 Feb 2018 05:22:56 -0800 (PST) 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 BFFD03F774; Tue, 13 Feb 2018 05:22:56 -0800 (PST) Received: by edgewater-inn.cambridge.arm.com (Postfix, from userid 1000) id 63E7D1AE5431; Tue, 13 Feb 2018 13:23:03 +0000 (GMT) From: Will Deacon To: linux-kernel@vger.kernel.org Cc: peterz@infradead.org, mingo@redhat.com, Will Deacon Subject: [PATCH 2/2] locking/qspinlock: Ensure node->count is updated before initialising node Date: Tue, 13 Feb 2018 13:22:57 +0000 Message-Id: <1518528177-19169-3-git-send-email-will.deacon@arm.com> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1518528177-19169-1-git-send-email-will.deacon@arm.com> References: <1518528177-19169-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 queuing on the qspinlock, the count field for the current CPU's head node is incremented. This needn't be atomic because locking in e.g. IRQ context is balanced and so an IRQ will return with node->count as it found it. However, the compiler could in theory reorder the initialisation of node[idx] before the increment of the head node->count, causing an IRQ to overwrite the initialised node and potentially corrupt the lock state. Avoid the potential for this harmful compiler reordering by placing a barrier() between the increment of the head node->count and the subsequent node initialisation. Cc: Peter Zijlstra Cc: Ingo Molnar Signed-off-by: Will Deacon --- kernel/locking/qspinlock.c | 8 ++++++++ 1 file changed, 8 insertions(+) -- 2.1.4 diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 348c8cec1042..d880296245c5 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -379,6 +379,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) tail = encode_tail(smp_processor_id(), idx); node += idx; + + /* + * Ensure that we increment the head node->count before initialising + * the actual node. If the compiler is kind enough to reorder these + * stores, then an IRQ could overwrite our assignments. + */ + barrier(); + node->locked = 0; node->next = NULL; pv_init_node(node);