All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86"
@ 2018-12-18 17:48 Sebastian Andrzej Siewior
  2018-12-18 17:48 ` [PATCH STABLE v4.19 1/2] locking/qspinlock: Re-order code Sebastian Andrzej Siewior
                   ` (2 more replies)
  0 siblings, 3 replies; 5+ messages in thread
From: Sebastian Andrzej Siewior @ 2018-12-18 17:48 UTC (permalink / raw)
  To: stable
  Cc: Peter Zijlstra, Will Deacon, Thomas Gleixner, Daniel Wagner, bigeasy

this is a backport of commit 7aa54be297655 ("locking/qspinlock, x86:
Provide liveness guarantee") for the v4.19 stable tree.

Initially I assumed that this was merged late in v4.19-rc but actually
it is just part v4.20-rc1.

For v4.19, most things are already in the tree. The GEN_BINARY_RMWcc
macro is still "old" and I skipped the documentation update.


Sebastian

^ permalink raw reply	[flat|nested] 5+ messages in thread

* [PATCH STABLE v4.19 1/2] locking/qspinlock: Re-order code
  2018-12-18 17:48 [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sebastian Andrzej Siewior
@ 2018-12-18 17:48 ` Sebastian Andrzej Siewior
  2018-12-18 17:48 ` [PATCH STABLE v4.19 2/2] locking/qspinlock, x86: Provide liveness guarantee Sebastian Andrzej Siewior
  2018-12-18 20:50 ` [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sasha Levin
  2 siblings, 0 replies; 5+ messages in thread
From: Sebastian Andrzej Siewior @ 2018-12-18 17:48 UTC (permalink / raw)
  To: stable
  Cc: Peter Zijlstra, Will Deacon, Thomas Gleixner, Daniel Wagner,
	bigeasy, Linus Torvalds, andrea.parri, longman, Ingo Molnar

From: Peter Zijlstra <peterz@infradead.org>

commit 53bf57fab7321fb42b703056a4c80fc9d986d170 upstream.

Flip the branch condition after atomic_fetch_or_acquire(_Q_PENDING_VAL)
such that we loose the indent. This also result in a more natural code
flow IMO.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Acked-by: Will Deacon <will.deacon@arm.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: andrea.parri@amarulasolutions.com
Cc: longman@redhat.com
Link: https://lkml.kernel.org/r/20181003130257.156322446@infradead.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
---
 kernel/locking/qspinlock.c | 56 ++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 29 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index bfaeb05123ff6..ec343276f975e 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -330,39 +330,37 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	 * 0,0,1 -> 0,1,1 ; pending
 	 */
 	val = atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);
-	if (!(val & ~_Q_LOCKED_MASK)) {
-		/*
-		 * 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) {
-			atomic_cond_read_acquire(&lock->val,
-						 !(VAL & _Q_LOCKED_MASK));
-		}
-
-		/*
-		 * take ownership and clear the pending bit.
-		 *
-		 * *,1,0 -> *,0,1
-		 */
-		clear_pending_set_locked(lock);
-		qstat_inc(qstat_lock_pending, true);
-		return;
+	/*
+	 * If we observe any contention; undo and queue.
+	 */
+	if (unlikely(val & ~_Q_LOCKED_MASK)) {
+		if (!(val & _Q_PENDING_MASK))
+			clear_pending(lock);
+		goto queue;
 	}
 
 	/*
-	 * If pending was clear but there are waiters in the queue, then
-	 * we need to undo our setting of pending before we queue ourselves.
+	 * We're pending, wait for the owner to go away.
+	 *
+	 * 0,1,1 -> 0,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_PENDING_MASK))
-		clear_pending(lock);
+	if (val & _Q_LOCKED_MASK)
+		atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_MASK));
+
+	/*
+	 * take ownership and clear the pending bit.
+	 *
+	 * 0,1,0 -> 0,0,1
+	 */
+	clear_pending_set_locked(lock);
+	qstat_inc(qstat_lock_pending, true);
+	return;
 
 	/*
 	 * End of pending bit optimistic spinning and beginning of MCS
-- 
2.20.1

^ permalink raw reply related	[flat|nested] 5+ messages in thread

* [PATCH STABLE v4.19 2/2] locking/qspinlock, x86: Provide liveness guarantee
  2018-12-18 17:48 [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sebastian Andrzej Siewior
  2018-12-18 17:48 ` [PATCH STABLE v4.19 1/2] locking/qspinlock: Re-order code Sebastian Andrzej Siewior
@ 2018-12-18 17:48 ` Sebastian Andrzej Siewior
  2018-12-18 20:50 ` [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sasha Levin
  2 siblings, 0 replies; 5+ messages in thread
From: Sebastian Andrzej Siewior @ 2018-12-18 17:48 UTC (permalink / raw)
  To: stable
  Cc: Peter Zijlstra, Will Deacon, Thomas Gleixner, Daniel Wagner,
	bigeasy, Linus Torvalds, andrea.parri, longman, Ingo Molnar

From: Peter Zijlstra <peterz@infradead.org>

commit 7aa54be2976550f17c11a1c3e3630002dea39303 upstream.

On x86 we cannot do fetch_or() with a single instruction and thus end up
using a cmpxchg loop, this reduces determinism. Replace the fetch_or()
with a composite operation: tas-pending + load.

Using two instructions of course opens a window we previously did not
have. Consider the scenario:

	CPU0		CPU1		CPU2

 1)	lock
	  trylock -> (0,0,1)

 2)			lock
			  trylock /* fail */

 3)	unlock -> (0,0,0)

 4)					lock
					  trylock -> (0,0,1)

 5)			  tas-pending -> (0,1,1)
			  load-val <- (0,1,0) from 3

 6)			  clear-pending-set-locked -> (0,0,1)

			  FAIL: _2_ owners

where 5) is our new composite operation. When we consider each part of
the qspinlock state as a separate variable (as we can when
_Q_PENDING_BITS == 8) then the above is entirely possible, because
tas-pending will only RmW the pending byte, so the later load is able
to observe prior tail and lock state (but not earlier than its own
trylock, which operates on the whole word, due to coherence).

To avoid this we need 2 things:

 - the load must come after the tas-pending (obviously, otherwise it
   can trivially observe prior state).

 - the tas-pending must be a full word RmW instruction, it cannot be an XCHGB for
   example, such that we cannot observe other state prior to setting
   pending.

On x86 we can realize this by using "LOCK BTS m32, r32" for
tas-pending followed by a regular load.

Note that observing later state is not a problem:

 - if we fail to observe a later unlock, we'll simply spin-wait for
   that store to become visible.

 - if we observe a later xchg_tail(), there is no difference from that
   xchg_tail() having taken place before the tas-pending.

Suggested-by: Will Deacon <will.deacon@arm.com>
Reported-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Will Deacon <will.deacon@arm.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: andrea.parri@amarulasolutions.com
Cc: longman@redhat.com
Fixes: 59fb586b4a07 ("locking/qspinlock: Remove unbounded cmpxchg() loop from locking slowpath")
Link: https://lkml.kernel.org/r/20181003130957.183726335@infradead.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
[bigeasy: GEN_BINARY_RMWcc macro redo]
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
---
 arch/x86/include/asm/qspinlock.h | 21 +++++++++++++++++++++
 kernel/locking/qspinlock.c       | 17 ++++++++++++++++-
 2 files changed, 37 insertions(+), 1 deletion(-)

diff --git a/arch/x86/include/asm/qspinlock.h b/arch/x86/include/asm/qspinlock.h
index 3e70bed8a978e..055c60a057567 100644
--- a/arch/x86/include/asm/qspinlock.h
+++ b/arch/x86/include/asm/qspinlock.h
@@ -6,9 +6,30 @@
 #include <asm/cpufeature.h>
 #include <asm-generic/qspinlock_types.h>
 #include <asm/paravirt.h>
+#include <asm/rmwcc.h>
 
 #define _Q_PENDING_LOOPS	(1 << 9)
 
+#define queued_fetch_set_pending_acquire queued_fetch_set_pending_acquire
+
+static __always_inline bool __queued_RMW_btsl(struct qspinlock *lock)
+{
+	GEN_BINARY_RMWcc(LOCK_PREFIX "btsl", lock->val.counter,
+			 "I", _Q_PENDING_OFFSET, "%0", c);
+}
+
+static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lock)
+{
+	u32 val = 0;
+
+	if (__queued_RMW_btsl(lock))
+		val |= _Q_PENDING_VAL;
+
+	val |= atomic_read(&lock->val) & ~_Q_PENDING_MASK;
+
+	return val;
+}
+
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 extern void native_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val);
 extern void __pv_init_lock_hash(void);
diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index ec343276f975e..edd75e0c7d961 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -231,6 +231,20 @@ static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
 }
 #endif /* _Q_PENDING_BITS == 8 */
 
+/**
+ * queued_fetch_set_pending_acquire - fetch the whole lock value and set pending
+ * @lock : Pointer to queued spinlock structure
+ * Return: The previous lock value
+ *
+ * *,*,* -> *,1,*
+ */
+#ifndef queued_fetch_set_pending_acquire
+static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lock)
+{
+	return atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);
+}
+#endif
+
 /**
  * set_locked - Set the lock bit and own the lock
  * @lock: Pointer to queued spinlock structure
@@ -329,7 +343,8 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	 * 0,0,0 -> 0,0,1 ; trylock
 	 * 0,0,1 -> 0,1,1 ; pending
 	 */
-	val = atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);
+	val = queued_fetch_set_pending_acquire(lock);
+
 	/*
 	 * If we observe any contention; undo and queue.
 	 */
-- 
2.20.1

^ permalink raw reply related	[flat|nested] 5+ messages in thread

* Re: [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86"
  2018-12-18 17:48 [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sebastian Andrzej Siewior
  2018-12-18 17:48 ` [PATCH STABLE v4.19 1/2] locking/qspinlock: Re-order code Sebastian Andrzej Siewior
  2018-12-18 17:48 ` [PATCH STABLE v4.19 2/2] locking/qspinlock, x86: Provide liveness guarantee Sebastian Andrzej Siewior
@ 2018-12-18 20:50 ` Sasha Levin
  2018-12-18 22:14   ` Sebastian Andrzej Siewior
  2 siblings, 1 reply; 5+ messages in thread
From: Sasha Levin @ 2018-12-18 20:50 UTC (permalink / raw)
  To: Sebastian Andrzej Siewior
  Cc: stable, Peter Zijlstra, Will Deacon, Thomas Gleixner, Daniel Wagner

On Tue, Dec 18, 2018 at 06:48:26PM +0100, Sebastian Andrzej Siewior wrote:
>this is a backport of commit 7aa54be297655 ("locking/qspinlock, x86:
>Provide liveness guarantee") for the v4.19 stable tree.
>
>Initially I assumed that this was merged late in v4.19-rc but actually
>it is just part v4.20-rc1.
>
>For v4.19, most things are already in the tree. The GEN_BINARY_RMWcc
>macro is still "old" and I skipped the documentation update.

I've queued this and the 4.14 series, thank you.

Could you resend the 4.9 series please? it had header errors in each
patch mail, and I'm afraid touching it :)

--
Thanks,
Sasha

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86"
  2018-12-18 20:50 ` [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sasha Levin
@ 2018-12-18 22:14   ` Sebastian Andrzej Siewior
  0 siblings, 0 replies; 5+ messages in thread
From: Sebastian Andrzej Siewior @ 2018-12-18 22:14 UTC (permalink / raw)
  To: Sasha Levin
  Cc: stable, Peter Zijlstra, Will Deacon, Thomas Gleixner, Daniel Wagner

On 2018-12-18 15:50:43 [-0500], Sasha Levin wrote:
> I've queued this and the 4.14 series, thank you.
> 
> Could you resend the 4.9 series please? it had header errors in each
> patch mail, and I'm afraid touching it :)

yeah, that was what Greg said, too :) I just didn't want to send them
all in one go. It is out now and I haven't seen any rejects so far.

Thank you.

> --
> Thanks,
> Sasha

Sebastian

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2018-12-18 22:14 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-18 17:48 [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sebastian Andrzej Siewior
2018-12-18 17:48 ` [PATCH STABLE v4.19 1/2] locking/qspinlock: Re-order code Sebastian Andrzej Siewior
2018-12-18 17:48 ` [PATCH STABLE v4.19 2/2] locking/qspinlock, x86: Provide liveness guarantee Sebastian Andrzej Siewior
2018-12-18 20:50 ` [PATCH STABLE v4.19 0/2] Backport for "cache line starvation on x86" Sasha Levin
2018-12-18 22:14   ` Sebastian Andrzej Siewior

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.