locking/qspinlock: Improve determinism for x86

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) <[email protected]>

---
 kernel/locking/qspinlock.c |   56 +++++++++++++++++++++------------------------
 1 file changed, 27 insertions(+), 29 deletions(-)

While working my way through the code again; I felt the comments could use help.

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 kernel/locking/qspinlock.c |   40 ++++++++++++++++++++++++++++------------
 1 file changed, 28 insertions(+), 12 deletions(-)

kernel/locking/qspinlock.c +0 -0

@@ -326,16 +326,23 @@ void queued_spin_lock_slowpath(struct qs
 	/*
 	 * trylock || pending

kernel/locking/qspinlock.c +3 -0

 	if (unlikely(val & ~_Q_LOCKED_MASK)) {
+
+		/* Undo PENDING if we set it. */
 		if (!(val & _Q_PENDING_MASK))
 			clear_pending(lock);
+
 		goto queue;
 	}
 

kernel/locking/qspinlock.c +17 -8

 	 *
 	 * 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.

@@ -474,16 +481,25 @@ void queued_spin_lock_slowpath(struct qs
 	 */
 
 	/*
-	 * In the PV case we might already have _Q_LOCKED_VAL set.
+	 * In the PV case we might already have _Q_LOCKED_VAL set, because
+	 * of lock stealing; therefore we must also allow:
 	 *
-	 * The atomic_cond_read_acquire() call above has provided the
-	 * necessary acquire semantics required for locking.
-	 */
-	if (((val & _Q_TAIL_MASK) == tail) &&
-	    atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
-		goto release; /* No contention */
+	 * n,0,1 -> 0,0,1
+	 *
+	 * Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the
+	 *       above wait condition, therefore any concurrent setting of
+	 *       PENDING will make the uncontended transition fail.
+	 */
+	if ((val & _Q_TAIL_MASK) == tail) {
+		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
+			goto release; /* No contention */
+	}
 
-	/* Either somebody is queued behind us or _Q_PENDING_VAL is set */
+	/*
+	 * Either somebody is queued behind us or _Q_PENDING_VAL got set
+	 * which will then detect the remaining tail and queue behind us
+	 * ensuring we'll see a @next.
+	 */
 	set_locked(lock);
 
 	/*

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 334

Quoted 4 lines · Peter Zijlstra

kernel/locking/qspinlock.c +2 -1

+
 	/*
-	 * If we observe any contention; undo and queue.
+	 * If we observe contention, there was a concurrent lock.

Nit: I think "concurrent lock" is confusing here, because that implies to me that the lock was actually taken behind our back, which isn't necessarily the case. How about "there is a concurrent locker"?

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 339

Quoted 5 lines

kernel/locking/qspinlock.c +4 -0

+	 *
+	 * Undo and queue; our setting of PENDING might have made the
+	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
+	 * on @next to become !NULL.
 	 */

Hmm, but it could also fail another concurrent set of PENDING (and the lock could just be held the entire time).

Quoted 9 lines

kernel/locking/qspinlock.c +3 -0

 	if (unlikely(val & ~_Q_LOCKED_MASK)) {
+
+		/* Undo PENDING if we set it. */
 		if (!(val & _Q_PENDING_MASK))
 			clear_pending(lock);
+
 		goto queue;
 	}

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 476

Quoted 6 lines

kernel/locking/qspinlock.c +1 -1

@@ -466,7 +473,7 @@ void queued_spin_lock_slowpath(struct qs
 	 * claim the lock:
 	 *
 	 * n,0,0 -> 0,0,1 : lock, uncontended
-	 * *,*,0 -> *,*,1 : lock, contended
+	 * *,0,0 -> *,0,1 : lock, contended

Pending can be set behind our back in the contended case, in which case we take the lock with a single byte store and don't clear pending. You mention this in the updated comment below, but I think we should leave this comment alone.

Quoted 9 lines · Will Deacon

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 334

Quoted 4 lines · Peter Zijlstra

kernel/locking/qspinlock.c +2 -1

+
 	/*
-	 * If we observe any contention; undo and queue.
+	 * If we observe contention, there was a concurrent lock.

Nit: I think "concurrent lock" is confusing here, because that implies to me that the lock was actually taken behind our back, which isn't necessarily the case. How about "there is a concurrent locker"?

Yes, that's better.

Quoted 8 lines

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 339

Quoted 5 lines

kernel/locking/qspinlock.c +4 -0

+	 *
+	 * Undo and queue; our setting of PENDING might have made the
+	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
+	 * on @next to become !NULL.
 	 */

Hmm, but it could also fail another concurrent set of PENDING (and the lock could just be held the entire time).

Right. What I wanted to convey was that is we observe _any_ contention, we must abort and queue, because of that above condition failing and waiting on @next.

The other cases weren't as critical, but that one really does require us to queue in order to make forward progress.

Or did I misunderstand your concern?

Quoted 9 lines

Quoted 9 lines

kernel/locking/qspinlock.c +3 -0

 	if (unlikely(val & ~_Q_LOCKED_MASK)) {
+
+		/* Undo PENDING if we set it. */
 		if (!(val & _Q_PENDING_MASK))
 			clear_pending(lock);
+
 		goto queue;
 	}

Quoted 11 lines

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 476

Quoted 6 lines

kernel/locking/qspinlock.c +1 -1

@@ -466,7 +473,7 @@ void queued_spin_lock_slowpath(struct qs
 	 * claim the lock:
 	 *
 	 * n,0,0 -> 0,0,1 : lock, uncontended
-	 * *,*,0 -> *,*,1 : lock, contended
+	 * *,0,0 -> *,0,1 : lock, contended

Pending can be set behind our back in the contended case, in which case we take the lock with a single byte store and don't clear pending. You mention this in the updated comment below, but I think we should leave this comment alone.

Ah, so the reason I write it like so is because when we get here, val.locked_pending == 0, per the atomic_cond_read_acquire() condition.

Quoted 2 lines

Ah, so the reason I write it like so is because when we get here, val.locked_pending == 0, per the atomic_cond_read_acquire() condition.

Ah, and I vaguely remember discussing this before. The way I read these transition diagrams, I find it most useful if they correspond to the lock word in memory. That way, it makes it clear about exactly which fields are stable, and which can be concurrently modified. So in the comment above, saying:

	 *,*,0 -> *,*,1 : lock, contended

is really helpful, because it clearly says "we're taking the lock, but the rest of the lock word could be modified by others at the same time", whereas saying:

	 *,0,0 -> *,0,1 : lock, contended

implies to me that pending is stable and cannot be set concurrently.

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

Quoted 10 lines · Peter Zijlstra

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

Quoted 7 lines

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

The split can cause some changes in behavior. The 3rd locker observes the pending bit and set tail. The split load of the 2nd locker may make it observe the tail and backout of the pending loop. As a result, the 2nd locker will acquire the lock after the third locker in this case. That won't happen with the original code.

I am not saying this is a problem. It is just something we should take note on.

Quoted 25 lines · Waiman Long

Quoted 10 lines · Peter Zijlstra

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

Quoted 7 lines

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

The split can cause some changes in behavior. The 3rd locker observes the pending bit and set tail. The split load of the 2nd locker may make it observe the tail and backout of the pending loop. As a result, the 2nd locker will acquire the lock after the third locker in this case. That won't happen with the original code.

Quoted 2 lines

I am not saying this is a problem. It is just something we should take note on.

Right, good one. Yes that can happen.

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

- when the last queued lock holder acquires the lock (uncontended), we clear the tail and set the lock byte. By first setting the pending bit this cmpxchg will fail and the later load must then see the remaining tail.

Another interesting scenario is where there are only 2 threads:

	lock := (0,0,0)

	CPU 0			CPU 1

	lock()			lock()
	  trylock(-> 0,0,1)       trylock() /* fail */
	    return;               xchg_relaxed(pending, 1) (-> 0,1,1)
				  mb()
				  val = smp_load_acquire(*lock);

Where, without the mb() the load would've been allowed to return 0 for the locked byte.

[*] there is a fun scenario where the 3rd locker observes the pending bit, but before it sets the tail, the 1st lock (owner) unlocks and the 2nd locker acquires the lock, leaving us with a temporary 0,0,1 state. But this is not different between fetch_or or this new method.

Suggested-by Will Deacon <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 arch/x86/include/asm/qspinlock.h |    2 +
 kernel/locking/qspinlock.c       |   56 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 57 insertions(+), 1 deletion(-)

arch/x86/include/asm/qspinlock.h +2 -0

@@ -9,6 +9,8 @@
 
 #define _Q_PENDING_LOOPS	(1 << 9)
 
+#define _Q_NO_FETCH_OR
+
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 extern void native_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val);
 extern void __pv_init_lock_hash(void);

kernel/locking/qspinlock.c +55 -1

@@ -232,6 +232,60 @@ static __always_inline u32 xchg_tail(str
 #endif /* _Q_PENDING_BITS == 8 */
 
 /**
+ * set_pending_fetch_acquire - fetch the whole lock value and set pending and locked
+ * @lock : Pointer to queued spinlock structure
+ * Return: The previous lock value
+ *
+ * *,*,* -> *,1,*
+ */
+static __always_inline u32 set_pending_fetch_acquire(struct qspinlock *lock)
+{
+#if defined(_Q_NO_FETCH_OR) && _Q_PENDING_BITS == 8
+	u32 val;
+
+	/*
+	 * For the !LL/SC archs that do not have a native atomic_fetch_or
+	 * but do have a native xchg (x86) we can do trickery and avoid the
+	 * cmpxchg-loop based fetch-or to improve determinism.
+	 *
+	 * We first xchg the pending byte to set PENDING, and then issue a load
+	 * for the rest of the word and mask out the pending byte to compute a
+	 * 'full' value.
+	 */
+	val = xchg_relaxed(&lock->pending, 1) << _Q_PENDING_OFFSET;
+	/*
+	 * Ensures the tail load happens after the xchg().
+	 *
+	 *	   lock  unlock    (a)
+	 *   xchg ---------------.
+	 *    (b)  lock  unlock  +----- fetch_or
+	 *   load ---------------'
+	 *	   lock  unlock    (c)
+	 *
+	 * For both lock and unlock, (a) and (c) are the same as fetch_or(),
+	 * since either are fully before or after. The only new case is (b),
+	 * where a concurrent lock or unlock can interleave with the composite
+	 * operation.
+	 *
+	 * In either case, it is the queueing case that is of interrest, otherwise
+	 * the whole operation is covered by the xchg() and the tail will be 0.
+	 *
+	 * For lock-(b); we only care if we set the PENDING bit or not. If we lost
+	 * the PENDING race, we queue. Otherwise we'd observe the tail anyway.
+	 *
+	 * For unlock-(b); since we'll have set PENDING, the uncontended claim
+	 * will fail and we'll observe a !0 tail.
+	 */
+	smp_mb__after_atomic();
+	val |= atomic_read_acquire(&lock->val) & ~_Q_PENDING_MASK;
+
+	return val;
+#else
+	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
  *

@@ -328,7 +382,7 @@ void queued_spin_lock_slowpath(struct qs
 	 *
 	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
 	 */
-	val = atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);
+	val = set_pending_fetch_acquire(lock);
 
 	/*
 	 * If we observe contention, there was a concurrent lock.

Quoted 35 lines · Peter Zijlstra

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

- when the last queued lock holder acquires the lock (uncontended), we clear the tail and set the lock byte. By first setting the pending bit this cmpxchg will fail and the later load must then see the remaining tail.

Another interesting scenario is where there are only 2 threads:

	lock := (0,0,0)

	CPU 0			CPU 1

	lock()			lock()
	  trylock(-> 0,0,1)       trylock() /* fail */
	    return;               xchg_relaxed(pending, 1) (-> 0,1,1)
				  mb()
				  val = smp_load_acquire(*lock);

Quoted 2 lines

Where, without the mb() the load would've been allowed to return 0 for the locked byte.

If this were true, we would have a violation of "coherence":

Quoted 36 lines · Andrea Parri

Quoted 35 lines · Peter Zijlstra

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

- when the last queued lock holder acquires the lock (uncontended), we clear the tail and set the lock byte. By first setting the pending bit this cmpxchg will fail and the later load must then see the remaining tail.

Another interesting scenario is where there are only 2 threads:

	lock := (0,0,0)

	CPU 0			CPU 1

	lock()			lock()
	  trylock(-> 0,0,1)       trylock() /* fail */
	    return;               xchg_relaxed(pending, 1) (-> 0,1,1)
				  mb()
				  val = smp_load_acquire(*lock);

Quoted 4 lines

Quoted 2 lines

Where, without the mb() the load would've been allowed to return 0 for the locked byte.

If this were true, we would have a violation of "coherence":

The thing is, this is mixed size, see:

https://www.cl.cam.ac.uk/~pes20/popl17/mixed-size.pdf

If I remember things correctly (I've not reread that paper recently) it is allowed for:

	old = xchg(pending,1);
	val = smp_load_acquire(*lock);

to be re-ordered like:

	val = smp_load_acquire(*lock);
	old = xchg(pending, 1);

with the exception that it will fwd the pending byte into the later load, so we get:

	val = (val & _Q_PENDING_MASK) | (old << _Q_PENDING_OFFSET);

for 'free'.

LKMM in particular does _NOT_ deal with mixed sized atomics _at_all_.

With the addition of smp_mb__after_atomic(), we disallow the load to be done prior to the xchg(). It might still fwd the more recent pending byte from its store buffer, but at least the other bytes must not be earlier.

Quoted 1 line

LKMM in particular does _NOT_ deal with mixed sized atomics _at_all_.

True, but it is nothing conceptually new to deal with: there're Cat models that handle mixed-size accesses, just give it time.

Quoted 4 lines · Andrea Parri

Quoted 1 line

LKMM in particular does _NOT_ deal with mixed sized atomics _at_all_.

True, but it is nothing conceptually new to deal with: there're Cat models that handle mixed-size accesses, just give it time.

Sure, but until that time I must not rely on (and thus not use) LKMM for qspinlock things.

So while your argument about coherence might be true -- I'll have to think about it; litmus tests are out the window.

Quoted 8 lines · Peter Zijlstra

Quoted 4 lines · Andrea Parri

Quoted 1 line

LKMM in particular does _NOT_ deal with mixed sized atomics _at_all_.

True, but it is nothing conceptually new to deal with: there're Cat models that handle mixed-size accesses, just give it time.

Sure, but until that time I must not rely on (and thus not use) LKMM for qspinlock things.

This is way too generic to be agreed ;D

Quoted 2 lines

So while your argument about coherence might be true -- I'll have to think about it; litmus tests are out the window.

You trimmed the litmus test I gave you.

Sent: 26 September 2018 12:01

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have.

On x86 we cannot do fetch_or with a single instruction and end up using a cmpxchg loop, this reduces determinism. Replace the fetch_or with a very tricky composite xchg8 + load.

The basic idea is that we use xchg8 to test-and-set the pending bit (when it is a byte) and then a load to fetch the whole word. Using two instructions of course opens a window we previously did not have. In particular the ordering between pending and tail is of interrest, because that is where the split happens.

The claim is that if we order them, it all works out just fine. There are two specific cases where the pending,tail state changes:

- when the 3rd lock(er) comes in and finds pending set, it'll queue and set tail; since we set tail while pending is set, the ordering is split is not important (and not fundamentally different form fetch_or). [*]

- when the last queued lock holder acquires the lock (uncontended), we clear the tail and set the lock byte. By first setting the pending bit this cmpxchg will fail and the later load must then see the remaining tail.

Another interesting scenario is where there are only 2 threads:

	lock := (0,0,0)

	CPU 0			CPU 1

	lock()			lock()
	  trylock(-> 0,0,1)       trylock() /* fail */
	    return;               xchg_relaxed(pending, 1) (-> 0,1,1)
				  mb()
				  val = smp_load_acquire(*lock);

Where, without the mb() the load would've been allowed to return 0 for the locked byte.

[*] there is a fun scenario where the 3rd locker observes the pending bit, but before it sets the tail, the 1st lock (owner) unlocks and the 2nd locker acquires the lock, leaving us with a temporary 0,0,1 state. But this is not different between fetch_or or this new method.

Suggested-by Will Deacon <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 arch/x86/include/asm/qspinlock.h |    2 +
 kernel/locking/qspinlock.c       |   56 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 57 insertions(+), 1 deletion(-)

arch/x86/include/asm/qspinlock.h +2 -0

@@ -9,6 +9,8 @@
 
 #define _Q_PENDING_LOOPS	(1 << 9)
 
+#define _Q_NO_FETCH_OR
+
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 extern void native_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val);
 extern void __pv_init_lock_hash(void);

kernel/locking/qspinlock.c +11 -0

@@ -232,6 +232,60 @@ static __always_inline u32 xchg_tail(str
 #endif /* _Q_PENDING_BITS == 8 */
 
 /**
+ * set_pending_fetch_acquire - fetch the whole lock value and set pending and locked
+ * @lock : Pointer to queued spinlock structure
+ * Return: The previous lock value
+ *
+ * *,*,* -> *,1,*
+ */
+static __always_inline u32 set_pending_fetch_acquire(struct qspinlock *lock)
+{
+#if defined(_Q_NO_FETCH_OR) && _Q_PENDING_BITS == 8
+	u32 val;
+

kernel/locking/qspinlock.c +13 -0

+	/*
+	 * Ensures the tail load happens after the xchg().
+	 *
+	 *	   lock  unlock    (a)
+	 *   xchg ---------------.
+	 *    (b)  lock  unlock  +----- fetch_or
+	 *   load ---------------'
+	 *	   lock  unlock    (c)
+	 *
+	 * For both lock and unlock, (a) and (c) are the same as fetch_or(),
+	 * since either are fully before or after. The only new case is (b),
+	 * where a concurrent lock or unlock can interleave with the composite
+	 * operation.

Hi Peter,

Thanks for chewing up my afternoon ;)

Quoted 18 lines

/**
+ * set_pending_fetch_acquire - fetch the whole lock value and set pending and locked
+ * @lock : Pointer to queued spinlock structure
+ * Return: The previous lock value
+ *
+ * *,*,* -> *,1,*
+ */

kernel/locking/qspinlock.c +10 -0

+static __always_inline u32 set_pending_fetch_acquire(struct qspinlock *lock)
+{
+#if defined(_Q_NO_FETCH_OR) && _Q_PENDING_BITS == 8
+	u32 val;
+
+	/*
+	 * For the !LL/SC archs that do not have a native atomic_fetch_or
+	 * but do have a native xchg (x86) we can do trickery and avoid the
+	 * cmpxchg-loop based fetch-or to improve determinism.
+	 *

kernel/locking/qspinlock.c static __always_inline u32 xchg_tail(str · line 255

Quoted 5 lines

kernel/locking/qspinlock.c +5 -0

+	 * We first xchg the pending byte to set PENDING, and then issue a load
+	 * for the rest of the word and mask out the pending byte to compute a
+	 * 'full' value.
+	 */
+	val = xchg_relaxed(&lock->pending, 1) << _Q_PENDING_OFFSET;

If we make this an xchg_acquire(), can we drop the smp_mb__after_atomic() and use a plain atomic_read() to get the rest of the word?

But actually,
consider this scenario with your patch:

1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set pending.

2. CPU1 comes in and sets pending, spins on locked

3. CPU2 sees a pending and locked val, and is about to enter the head of the waitqueue (i.e. it's right before xchg_tail()).

4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s it, so pending and locked are now 0.

5. CPU0 sets pending and reads back zeroes for the other fields

6. CPU0 clears pending and sets locked -- it now has the lock

7. CPU2 updates tail, sees it's at the head of the waitqueue and spins for locked and pending to go clear. However, it reads a stale value from step (4) and attempts the atomic_try_cmpxchg() to take the lock.

8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this point we're hosed, because both CPU2 and CPU0 have the lock.

Is there something I'm missing that means this can't happen? I suppose cacheline granularity ends up giving serialisation between (4) and (7), but I'd *much* prefer not to rely on that because it feels horribly fragile.

Another idea I was playing with was adding test_and_set_bit_acquire() for this, because x86 has an instruction for that, right?

kernel/locking/qspinlock.c static __always_inline u32 xchg_tail(str · line 264

Quoted 9 lines

kernel/locking/qspinlock.c +9 -0

+	/*
+	 * Ensures the tail load happens after the xchg().
+	 *
+	 *	   lock  unlock    (a)
+	 *   xchg ---------------.
+	 *    (b)  lock  unlock  +----- fetch_or
+	 *   load ---------------'
+	 *	   lock  unlock    (c)
+	 *

I failed miserably at parsing this comment :(

I think the main issue is that I don't understand how to read the little diagram you've got.

Quoted 1 line · Will Deacon

Thanks for chewing up my afternoon ;)

I'll get you a beer in EDI ;-)

Quoted 16 lines

But actually,
consider this scenario with your patch:

1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set pending.

2. CPU1 comes in and sets pending, spins on locked

3. CPU2 sees a pending and locked val, and is about to enter the head of the waitqueue (i.e. it's right before xchg_tail()).

4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s it, so pending and locked are now 0.

5. CPU0 sets pending and reads back zeroes for the other fields

Quoted 8 lines

6. CPU0 clears pending and sets locked -- it now has the lock

7. CPU2 updates tail, sees it's at the head of the waitqueue and spins for locked and pending to go clear. However, it reads a stale value from step (4) and attempts the atomic_try_cmpxchg() to take the lock.

8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this point we're hosed, because both CPU2 and CPU0 have the lock.

Let me draw a picture of that..

CPU0 CPU1 CPU2 CPU3

0) lock

						  trylock -> (0,0,1)

1)lock
trylock /* fail */

2) lock

		  trylock /* fail */
		  tas-pending -> (0,1,1)
		  wait-locked

3) lock
trylock /* fail */ tas-pending /* fail */

4) unlock -> (0,1,0)

		  clr_pnd_set_lck -> (0,0,1)
		  unlock -> (0,0,0)

5) tas-pending -> (0,1,0)

    read-val -> (0,1,0)
6)  clr_pnd_set_lck -> (0,0,1)
7)				  xchg_tail -> (n,0,1)
				  load_acquire <- (n,0,0) (from-4)

8) cmpxchg /* fail */
set_locked()

Quoted 4 lines

Is there something I'm missing that means this can't happen? I suppose cacheline granularity ends up giving serialisation between (4) and (7), but I'd *much* prefer not to rely on that because it feels horribly fragile.

Well, on x86 atomics are fully ordered, so the xchg_tail() does in fact have smp_mb() in and that should order it sufficient for that not to happen I think.

But in general, yes ick. Alternatively, making xchg_tail an ACQUIRE doesn't seem too far out..

Quoted 2 lines

Another idea I was playing with was adding test_and_set_bit_acquire() for this, because x86 has an instruction for that, right?

LOCK BTS, yes. So it can do a full 32bit RmW, but it cannot return the old value of the word, just the old bit (in CF).

I suppose you get rid of the whole mixed size thing, but you still have the whole two instruction thing.

Quoted 12 lines

kernel/locking/qspinlock.c static __always_inline u32 xchg_tail(str · line 264

Quoted 9 lines

kernel/locking/qspinlock.c +9 -0

+	/*
+	 * Ensures the tail load happens after the xchg().
+	 *
+	 *	   lock  unlock    (a)
+	 *   xchg ---------------.
+	 *    (b)  lock  unlock  +----- fetch_or
+	 *   load ---------------'
+	 *	   lock  unlock    (c)
+	 *

I failed miserably at parsing this comment :(

Quoted 2 lines

I think the main issue is that I don't understand how to read the little diagram you've got.

Where fetch_or() is indivisible and has happens-before (a) and happens-after (c), the new thing is in fact divisible and has happens-in-between (b).

Of the happens-in-between (b), we can either get a new concurrent locker, or make progress of an extant concurrent locker because an unlock happened.

But the rest of the text might indeed be very confused. I think I wrote the bulk of that when I was in fact doing a xchg16 on locked_pending, but that's fundamentally broken. I did edit it afterwards, but that might have just made it worse.

Quoted 36 lines · Peter Zijlstra

Let me draw a picture of that..

CPU0 CPU1 CPU2 CPU3

0) lock

						  trylock -> (0,0,1)

1)lock
trylock /* fail */

2) lock

		  trylock /* fail */
		  tas-pending -> (0,1,1)
		  wait-locked

3) lock
trylock /* fail */ tas-pending /* fail */

4) unlock -> (0,1,0)

		  clr_pnd_set_lck -> (0,0,1)
		  unlock -> (0,0,0)

5) tas-pending -> (0,1,0)

    read-val -> (0,1,0)
6)  clr_pnd_set_lck -> (0,0,1)
7)				  xchg_tail -> (n,0,1)
				  load_acquire <- (n,0,0) (from-4)

8) cmpxchg /* fail */
set_locked()

Quoted 4 lines

Is there something I'm missing that means this can't happen? I suppose cacheline granularity ends up giving serialisation between (4) and (7), but I'd *much* prefer not to rely on that because it feels horribly fragile.

Quoted 3 lines

Well, on x86 atomics are fully ordered, so the xchg_tail() does in fact have smp_mb() in and that should order it sufficient for that not to happen I think.

Hmm, does that actually help, though? I still think you're relying on the cache-coherence protocol to serialise the xchg() on pending before the xchg_tail(), which I think is fragile because they don't actually overlap.

consider this scenario with your patch:

1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set pending.

2. CPU1 comes in and sets pending, spins on locked

3. CPU2 sees a pending and locked val, and is about to enter the head of the waitqueue (i.e. it's right before xchg_tail()).

4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s it, so pending and locked are now 0.

5. CPU0 sets pending and reads back zeroes for the other fields

6. CPU0 clears pending and sets locked -- it now has the lock

7. CPU2 updates tail, sees it's at the head of the waitqueue and spins for locked and pending to go clear. However, it reads a stale value from step (4) and attempts the atomic_try_cmpxchg() to take the lock.

8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this point we're hosed, because both CPU2 and CPU0 have the lock.

Quoted 21 lines

consider this scenario with your patch:

1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set pending.

2. CPU1 comes in and sets pending, spins on locked

3. CPU2 sees a pending and locked val, and is about to enter the head of the waitqueue (i.e. it's right before xchg_tail()).

4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s it, so pending and locked are now 0.

5. CPU0 sets pending and reads back zeroes for the other fields

6. CPU0 clears pending and sets locked -- it now has the lock

7. CPU2 updates tail, sees it's at the head of the waitqueue and spins for locked and pending to go clear. However, it reads a stale value from step (4) and attempts the atomic_try_cmpxchg() to take the lock.

Quoted 2 lines

8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this point we're hosed, because both CPU2 and CPU0 have the lock.

Thanks for pointing this out. I am wondering: can't we have a similar
scenario with the current code (i.e., w/o these patches): what prevents the scenario reported below, following Peter's diagram, from happening?

CPU0 CPU1 CPU2 CPU3

0) lock

						  trylock -> (0,0,1)

1)lock
trylock /* fail */

2) lock

		  trylock /* fail */
		  fetch_or_acquire -> (0,1,1)
		  wait-locked

3) lock
trylock /* fail */ goto queue

4) unlock -> (0,1,0)

		  clr_pnd_set_lck -> (0,0,1)
		  unlock -> (0,0,0)

5) fetch_or_acquire -> (0,1,0)
6) clr_pnd_set_lck -> (0,0,1)
7) xchg_tail -> (n,0,1)

				  load_acquire <- (n,0,0) (from-4)

8) cmpxchg /* fail */
set_locked()

Quoted 24 lines · Andrea Parri

Quoted 23 lines

consider this scenario with your patch:

1. CPU0 sees a locked val, and is about to do your xchg_relaxed() to set pending.

2. CPU1 comes in and sets pending, spins on locked

3. CPU2 sees a pending and locked val, and is about to enter the head of the waitqueue (i.e. it's right before xchg_tail()).

4. The locked holder unlock()s, CPU1 takes the lock() and then unlock()s it, so pending and locked are now 0.

5. CPU0 sets pending and reads back zeroes for the other fields

6. CPU0 clears pending and sets locked -- it now has the lock

7. CPU2 updates tail, sees it's at the head of the waitqueue and spins for locked and pending to go clear. However, it reads a stale value from step (4) and attempts the atomic_try_cmpxchg() to take the lock.

8. CPU2 will fail the cmpxchg(), but then go ahead and set locked. At this point we're hosed, because both CPU2 and CPU0 have the lock.

Quoted 3 lines

Thanks for pointing this out. I am wondering: can't we have a similar
scenario with the current code (i.e., w/o these patches): what prevents the scenario reported below, following Peter's diagram, from happening?

The xchg_tail() in step (7) reads from the fetch_or_acquire() in step (5), so I don't think we can see a stale value in the subsequent (overlapping) acquire load.

Will

Quoted 26 lines

CPU0 CPU1 CPU2 CPU3

0) lock

						  trylock -> (0,0,1)

1)lock
trylock /* fail */

2) lock

		  trylock /* fail */
		  fetch_or_acquire -> (0,1,1)
		  wait-locked

3) lock
trylock /* fail */ goto queue

4) unlock -> (0,1,0)

		  clr_pnd_set_lck -> (0,0,1)
		  unlock -> (0,0,0)

5) fetch_or_acquire -> (0,1,0)
6) clr_pnd_set_lck -> (0,0,1)
7) xchg_tail -> (n,0,1)

				  load_acquire <- (n,0,0) (from-4)

8) cmpxchg /* fail */
set_locked()

In particular this ordering ensures a concurrent unlock cannot trigger the uncontended handoff. Also it ensures that if the xchg() happens after a (successful) trylock, we must observe that LOCKED bit.

Quoted 3 lines · Peter Zijlstra

In particular this ordering ensures a concurrent unlock cannot trigger the uncontended handoff. Also it ensures that if the xchg() happens after a (successful) trylock, we must observe that LOCKED bit.

so I backported a bunch of atomic files and qspinlock back to v4.9-RT in order to get these patches applied. The backported kernel booted and showed the same symptomps within seconds (those I reported last FR). With those three patches ontop I have the Core2Duo 10 minutes in testing without any issues…

Remember that 4.14 took almost 8 hours to fail, so I'd recommend not to cheer too much. Let's see what it tells us in 48 hours.

Thanks,

tglx

Back when Will did his qspinlock determinism patches, we were left with one cmpxchg loop on x86 due to the use of atomic_fetch_or(). Will proposed a nifty trick:

http://lkml.kernel.org/r/[email protected]

But at the time we didn't pursue it. This series implements that and argues for its correctness. In particular it places an smp_mb__after_atomic() in between the two operations, which forces the load to come after the store (which is free on x86 anyway).

In particular this ordering ensures a concurrent unlock cannot trigger the uncontended handoff. Also it ensures that if the xchg() happens after a (successful) trylock, we must observe that LOCKED bit.

Quoted 11 lines · Peter Zijlstra

Back when Will did his qspinlock determinism patches, we were left with one cmpxchg loop on x86 due to the use of atomic_fetch_or(). Will proposed a nifty trick:

http://lkml.kernel.org/r/[email protected]

But at the time we didn't pursue it. This series implements that and argues for its correctness. In particular it places an smp_mb__after_atomic() in between the two operations, which forces the load to come after the store (which is free on x86 anyway).

Quoted 3 lines

In particular this ordering ensures a concurrent unlock cannot trigger the uncontended handoff. Also it ensures that if the xchg() happens after a (successful) trylock, we must observe that LOCKED bit.

When you said "concurrent unlock cannot trigger the uncontended handoff", are you saying the current code has this uncontended handoff problem or just when comparing to doing a load first followed by xchg()?

Quoted 12 lines · Waiman Long

Quoted 11 lines · Peter Zijlstra

Back when Will did his qspinlock determinism patches, we were left with one cmpxchg loop on x86 due to the use of atomic_fetch_or(). Will proposed a nifty trick:

http://lkml.kernel.org/r/[email protected]

But at the time we didn't pursue it. This series implements that and argues for its correctness. In particular it places an smp_mb__after_atomic() in between the two operations, which forces the load to come after the store (which is free on x86 anyway).

Quoted 6 lines

Quoted 3 lines

In particular this ordering ensures a concurrent unlock cannot trigger the uncontended handoff. Also it ensures that if the xchg() happens after a (successful) trylock, we must observe that LOCKED bit.

When you said "concurrent unlock cannot trigger the uncontended handoff", are you saying the current code has this uncontended handoff problem or just when comparing to doing a load first followed by xchg()?

In particular I'm talking about this:

locked:
/*
* claim the lock:
*
* n,0,0 -> 0,0,1 : lock, uncontended
* *,0,0 -> *,0,1 : lock, contended
*
* 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.
*/
/*
* In the PV case we might already have _Q_LOCKED_VAL set, because
* of lock stealing; therefore we must also allow:
*
* n,0,1 -> 0,0,1
*
* Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the
* above wait condition, therefore any concurrent setting of
* PENDING will make the uncontended transition fail.
*/
if ((val & _Q_TAIL_MASK) == tail) {
if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
goto release; /* No contention */
}

Here queue head acquires the lock and we take the "uncontended" path. If we set PENDING prior to this, the cmpxchg above will fail, and the later load will observe the tail.