LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: tip-bot for Will Deacon <tipbot@zytor.com>
To: linux-tip-commits@vger.kernel.org
Cc: mingo@kernel.org, linux-kernel@vger.kernel.org,
	tglx@linutronix.de, peterz@infradead.org, hpa@zytor.com,
	will.deacon@arm.com, torvalds@linux-foundation.org,
	longman@redhat.com
Subject: [tip:locking/core] locking/qspinlock: Remove unbounded cmpxchg() loop from locking slowpath
Date: Fri, 27 Apr 2018 02:39:08 -0700	[thread overview]
Message-ID: <tip-59fb586b4a07b4e1a0ee577140ab4842ba451acd@git.kernel.org> (raw)
In-Reply-To: <1524738868-31318-6-git-send-email-will.deacon@arm.com>

Commit-ID:  59fb586b4a07b4e1a0ee577140ab4842ba451acd
Gitweb:     https://git.kernel.org/tip/59fb586b4a07b4e1a0ee577140ab4842ba451acd
Author:     Will Deacon <will.deacon@arm.com>
AuthorDate: Thu, 26 Apr 2018 11:34:19 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 27 Apr 2018 09:48:47 +0200

locking/qspinlock: Remove unbounded cmpxchg() loop from locking slowpath

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.

Signed-off-by: Will Deacon <will.deacon@arm.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Acked-by: Waiman Long <longman@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: boqun.feng@gmail.com
Cc: linux-arm-kernel@lists.infradead.org
Cc: paulmck@linux.vnet.ibm.com
Link: http://lkml.kernel.org/r/1524738868-31318-6-git-send-email-will.deacon@arm.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/locking/qspinlock.c          | 102 ++++++++++++++++++++----------------
 kernel/locking/qspinlock_paravirt.h |   5 --
 2 files changed, 58 insertions(+), 49 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index a0f7976348f8..e06f67e021d9 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -127,6 +127,17 @@ static inline __pure struct mcs_spinlock *decode_tail(u32 tail)
 #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK)
 
 #if _Q_PENDING_BITS == 8
+/**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ *
+ * *,1,* -> *,0,*
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	WRITE_ONCE(lock->pending, 0);
+}
+
 /**
  * clear_pending_set_locked - take ownership and clear the pending bit.
  * @lock: Pointer to queued spinlock structure
@@ -162,6 +173,17 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
 
 #else /* _Q_PENDING_BITS == 8 */
 
+/**
+ * clear_pending - clear the pending bit.
+ * @lock: Pointer to queued spinlock structure
+ *
+ * *,1,* -> *,0,*
+ */
+static __always_inline void clear_pending(struct qspinlock *lock)
+{
+	atomic_andnot(_Q_PENDING_VAL, &lock->val);
+}
+
 /**
  * clear_pending_set_locked - take ownership and clear the pending bit.
  * @lock: Pointer to queued spinlock structure
@@ -266,7 +288,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));
@@ -289,59 +311,51 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 					       (VAL != _Q_PENDING_VAL) || !cnt--);
 	}
 
+	/*
+	 * 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))
+		clear_pending(lock);
 
 	/*
 	 * End of pending bit optimistic spinning and beginning of MCS
@@ -445,15 +459,15 @@ locked:
 	 * 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;
 		}
diff --git a/kernel/locking/qspinlock_paravirt.h b/kernel/locking/qspinlock_paravirt.h
index 2711940429f5..2dbad2f25480 100644
--- a/kernel/locking/qspinlock_paravirt.h
+++ b/kernel/locking/qspinlock_paravirt.h
@@ -118,11 +118,6 @@ static __always_inline void set_pending(struct qspinlock *lock)
 	WRITE_ONCE(lock->pending, 1);
 }
 
-static __always_inline void clear_pending(struct qspinlock *lock)
-{
-	WRITE_ONCE(lock->pending, 0);
-}
-
 /*
  * The pending bit check in pv_queued_spin_steal_lock() isn't a memory
  * barrier. Therefore, an atomic cmpxchg_acquire() is used to acquire the

  parent reply	other threads:[~2018-04-27  9:39 UTC|newest]

Thread overview: 41+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-26 10:34 [PATCH v3 00/14] kernel/locking: qspinlock improvements Will Deacon
2018-04-26 10:34 ` [PATCH v3 01/14] barriers: Introduce smp_cond_load_relaxed and atomic_cond_read_relaxed Will Deacon
2018-04-27  9:36   ` [tip:locking/core] locking/barriers: Introduce smp_cond_load_relaxed() and atomic_cond_read_relaxed() tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 02/14] locking/qspinlock: Merge struct __qspinlock into struct qspinlock Will Deacon
2018-04-27  9:37   ` [tip:locking/core] locking/qspinlock: Merge 'struct __qspinlock' into 'struct qspinlock' tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 03/14] locking/qspinlock: Bound spinning on pending->locked transition in slowpath Will Deacon
2018-04-27  9:37   ` [tip:locking/core] " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 04/14] locking/qspinlock/x86: Increase _Q_PENDING_LOOPS upper bound Will Deacon
2018-04-27  9:38   ` [tip:locking/core] " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 05/14] locking/qspinlock: Remove unbounded cmpxchg loop from locking slowpath Will Deacon
2018-04-26 15:53   ` Peter Zijlstra
2018-04-26 16:55     ` Will Deacon
2018-04-28 12:45       ` Peter Zijlstra
2018-04-30  8:53         ` Will Deacon
2018-04-26 20:16   ` Waiman Long
2018-04-27 10:16     ` Will Deacon
2018-04-27 11:01       ` [tip:locking/core] locking/qspinlock: Remove duplicate clear_pending() function from PV code tip-bot for Will Deacon
2018-04-27 13:09       ` [PATCH v3 05/14] locking/qspinlock: Remove unbounded cmpxchg loop from locking slowpath Waiman Long
2018-04-27  9:39   ` tip-bot for Will Deacon [this message]
2018-04-26 10:34 ` [PATCH v3 06/14] locking/qspinlock: Kill cmpxchg loop when claiming lock from head of queue Will Deacon
2018-04-27  9:39   ` [tip:locking/core] locking/qspinlock: Kill cmpxchg() " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 07/14] locking/qspinlock: Use atomic_cond_read_acquire Will Deacon
2018-04-27  9:40   ` [tip:locking/core] locking/qspinlock: Use atomic_cond_read_acquire() tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 08/14] locking/mcs: Use smp_cond_load_acquire() in mcs spin loop Will Deacon
2018-04-27  9:40   ` [tip:locking/core] locking/mcs: Use smp_cond_load_acquire() in MCS " tip-bot for Jason Low
2018-04-26 10:34 ` [PATCH v3 09/14] locking/qspinlock: Use smp_cond_load_relaxed to wait for next node Will Deacon
2018-04-27  9:41   ` [tip:locking/core] locking/qspinlock: Use smp_cond_load_relaxed() " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 10/14] locking/qspinlock: Make queued_spin_unlock use smp_store_release Will Deacon
2018-04-27  9:42   ` [tip:locking/core] locking/qspinlock: Use smp_store_release() in queued_spin_unlock() tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 11/14] locking/qspinlock: Elide back-to-back RELEASE operations with smp_wmb() Will Deacon
2018-04-27  9:42   ` [tip:locking/core] " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 12/14] locking/qspinlock: Use try_cmpxchg instead of cmpxchg when locking Will Deacon
2018-04-27  9:43   ` [tip:locking/core] locking/qspinlock: Use try_cmpxchg() instead of cmpxchg() " tip-bot for Will Deacon
2018-04-26 10:34 ` [PATCH v3 13/14] locking/qspinlock: Add stat tracking for pending vs slowpath Will Deacon
2018-04-27  9:43   ` [tip:locking/core] locking/qspinlock: Add stat tracking for pending vs. slowpath tip-bot for Waiman Long
2018-04-26 10:34 ` [PATCH v3 14/14] MAINTAINERS: Add myself as a co-maintainer for LOCKING PRIMITIVES Will Deacon
2018-04-26 15:55   ` Peter Zijlstra
2018-04-27  9:44   ` [tip:locking/core] MAINTAINERS: Add myself as a co-maintainer for the locking subsystem tip-bot for Will Deacon
2018-04-26 15:54 ` [PATCH v3 00/14] kernel/locking: qspinlock improvements Peter Zijlstra
2018-04-27  9:33   ` Ingo Molnar
2018-04-26 20:18 ` Waiman Long

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=tip-59fb586b4a07b4e1a0ee577140ab4842ba451acd@git.kernel.org \
    --to=tipbot@zytor.com \
    --cc=hpa@zytor.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-tip-commits@vger.kernel.org \
    --cc=longman@redhat.com \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --cc=will.deacon@arm.com \
    --subject='Re: [tip:locking/core] locking/qspinlock: Remove unbounded cmpxchg() loop from locking slowpath' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).