smp_cond_load_acquire + cmpwait

This new form allows using hardware assisted waiting.

Requested-by Will Deacon<[email protected]>

Suggested-by Linus Torvalds<[email protected]>

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

---
  include/linux/compiler.h   |   25 +++++++++++++++++++------
  kernel/locking/qspinlock.c |   12 ++++++------
  kernel/sched/core.c        |    8 ++++----
  kernel/sched/sched.h       |    2 +-
  kernel/smp.c               |    2 +-
  5 files changed, 31 insertions(+), 18 deletions(-)

include/linux/compiler.h +9 -6

@@ -305,21 +305,34 @@ static __always_inline void __write_once
  })
 
  /**
- * smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering
+ * smp_cond_load_acquire() - (Spin) wait for cond with ACQUIRE ordering
+ * @ptr: pointer to the variable to wait on
   * @cond: boolean expression to wait for
   *
   * Equivalent to using smp_load_acquire() on the condition variable but employs
   * the control dependency of the wait to reduce the barrier on many platforms.
   *
+ * Due to C lacking lambda expressions we load the value of *ptr into a
+ * pre-named variable @VAL to be used in @cond.
+ *
   * The control dependency provides a LOAD->STORE order, the additional RMB
   * provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order,
   * aka. ACQUIRE.
   */
-#define smp_cond_acquire(cond)	do {		\
-	while (!(cond))				\
-		cpu_relax();			\
-	smp_rmb(); /* ctrl + rmb := acquire */	\
-} while (0)
+#ifndef smp_cond_load_acquire
+#define smp_cond_load_acquire(ptr, cond_expr) ({		\
+	typeof(ptr) __PTR = (ptr);				\
+	typeof(*ptr) VAL;					\

Use smp_cond_load_acquire() to make better use of the hardware assisted 'spin' wait on arm64.

Arguably the second hunk is the more horrid abuse possible, but avoids having to use cmpwait (see next patch) directly. Also, this makes 'clever' (ab)use of the cond+rmb acquire to omit the acquire from cmpxchg().

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

---
kernel/locking/qrwlock.c | 18 ++++--------------

1 file changed, 4 insertions(+), 14 deletions(-)

kernel/locking/qrwlock.c +0 -0

@@ -53,10 +53,7 @@ struct __qrwlock {

static __always_inline void rspin_until_writer_unlock(struct qrwlock *lock, u32 cnts) {

kernel/locking/qrwlock.c +1 -4

-	while ((cnts & _QW_WMASK) == _QW_LOCKED) {
-		cpu_relax_lowlatency();
-		cnts = atomic_read_acquire(&lock->cnts);
-	}
+	smp_cond_load_acquire(&lock->cnts.counter, (VAL & _QW_WMASK) != _QW_LOCKED);

}

/**

kernel/locking/qrwlock.c +0 -3

@@ -109,8 +106,6 @@ EXPORT_SYMBOL(queued_read_lock_slowpath)
 */
 void queued_write_lock_slowpath(struct qrwlock *lock)
 {
-	u32 cnts;
-
 	/* Put the writer into the wait queue */
 	arch_spin_lock(&lock->wait_lock);
 

@@ -134,15 +129,10 @@ void queued_write_lock_slowpath(struct q
 	}
 
 	/* When no more readers, set the locked flag */
-	for (;;) {

Quoted 52 lines · Peter Zijlstra

Use smp_cond_load_acquire() to make better use of the hardware assisted 'spin' wait on arm64.

Arguably the second hunk is the more horrid abuse possible, but avoids having to use cmpwait (see next patch) directly. Also, this makes 'clever' (ab)use of the cond+rmb acquire to omit the acquire from cmpxchg().

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

---
kernel/locking/qrwlock.c | 18 ++++--------------

1 file changed, 4 insertions(+), 14 deletions(-)

kernel/locking/qrwlock.c +0 -0

@@ -53,10 +53,7 @@ struct __qrwlock {

static __always_inline void rspin_until_writer_unlock(struct qrwlock *lock, u32 cnts) {

kernel/locking/qrwlock.c +1 -4

-    while ((cnts & _QW_WMASK) == _QW_LOCKED) {
-        cpu_relax_lowlatency();
-        cnts = atomic_read_acquire(&lock->cnts);
-    }
+    smp_cond_load_acquire(&lock->cnts.counter, (VAL & _QW_WMASK) != 

_QW_LOCKED);
}

/**

kernel/locking/qrwlock.c +3 -8

@@ -109,8 +106,6 @@ EXPORT_SYMBOL(queued_read_lock_slowpath)
 */
 void queued_write_lock_slowpath(struct qrwlock *lock)
 {
-    u32 cnts;
-
    /* Put the writer into the wait queue */
    arch_spin_lock(&lock->wait_lock);
 

@@ -134,15 +129,10 @@ void queued_write_lock_slowpath(struct q
    }
 
    /* When no more readers, set the locked flag */
-    for (;;) {
-        cnts = atomic_read(&lock->cnts);
-        if ((cnts == _QW_WAITING) &&
-            (atomic_cmpxchg_acquire(&lock->cnts, _QW_WAITING,
-                        _QW_LOCKED) == _QW_WAITING))
-            break;
+    smp_cond_load_acquire(&lock->cnts.counter,
+        (VAL == _QW_WAITING) &&
+        atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING, _QW_LOCKED) 
 == _QW_WAITING);
 

kernel/locking/qrwlock.c void queued_write_lock_slowpath(struct q · line 145

Quoted 1 line

kernel/locking/qrwlock.c +0 -1

-        cpu_relax_lowlatency();

You would need some variant for cpu_relax_lowlatency otherwise you'll be hurting s390, no? fwiw back when I was looking at this, I recall thinking about possibly introducing smp_cond_acquire_lowlatency but never got around to it.

Thanks,
Davidlohr

+#define __CMPWAIT_GEN(w, sz, name) \

+}

Provide the cmpwait() primitive, which will 'spin' wait for a variable to change. Use it to implement smp_cond_load_acquire() and provide an ARM64 implementation.

The ARM64 implementation uses LDXR+WFE to avoid most spinning by letting the hardware go idle while waiting for the exclusive load of the variable to be cancelled (as anybody changing the value must).

I've misplaced my arm64 compiler, so this is not even compile tested.

Suggested-by Will Deacon <[email protected]>

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

---
 arch/arm64/include/asm/cmpxchg.h |   36 +++++++++++++++++++++++++++++
 include/linux/atomic.h           |   47 +++++++++++++++++++++++++++++++++++++++
 include/linux/compiler.h         |   30 ------------------------
 3 files changed, 83 insertions(+), 30 deletions(-)

arch/arm64/include/asm/cmpxchg.h +0 -0

@@ -224,4 +224,40 @@ __CMPXCHG_GEN(_mb)
 	__ret;								\
 })

arch/arm64/include/asm/cmpxchg.h +13 -0

+	  [v] "+Q" (*(unsigned long *)ptr));				\
+}
+
+__CMPWAIT_GEN(w, b, 1);
+__CMPWAIT_GEN(w, h, 2);
+__CMPWAIT_GEN(w,  , 4);
+__CMPWAIT_GEN( ,  , 8);
+
+static inline void __cmpwait(volatile void *ptr, unsigned long val, int size)
+{
+	switch (size) {
+	case 1: return __cmpwait_case_1(ptr, val);
+	case 2: return __cmpwait_case_2(ptr, val);

Thanks for looking at this!

Quoted 1 line

I've misplaced my arm64 compiler, so this is not even compile tested.

Guess what? ;)

make: *** [init] Error 2
make: *** Waiting for unfinished jobs....

(and lot of similar errors).

Looks like you're just missing an #undef in cmpxchg.h.

FWIW, you can pick up arm64 toolchain binaries from:

https://releases.linaro.org/components/toolchain/binaries/latest-5/

Quoted 4 lines

arch/arm64/include/asm/cmpxchg.h +4 -0

+#define __CMPWAIT_GEN(w, sz, name)					\
+void __cmpwait_case_##name(volatile void *ptr, unsigned long val)	\
+{									\
+	unsigned long tmp;						\

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 235

Quoted 5 lines

arch/arm64/include/asm/cmpxchg.h +5 -0

+									\
+	asm volatile(							\
+	"	ldxr" #sz "\t%" #w "[tmp], %[v]\n"			\
+	"	eor	%" #w "[tmp], %" #w "[tmp], %" #w "[val]\n"	\
+	"	cbnz	%" #w "[tmp], 1f\n"				\

Shouldn't this be cbz? (i.e. branch over the wfe if the value is equal to what we wanted?).

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 238

Quoted 3 lines

arch/arm64/include/asm/cmpxchg.h +3 -0

+	"	wfe\n"							\
+	"1:"								\
+	: [tmp] "=&r" (tmp), [val] "=&r" (val),				\

We only read val, so it can be an input operand, no?

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 261

Quoted 2 lines

arch/arm64/include/asm/cmpxchg.h +2 -0

+#define cmpwait(ptr, val) \
+	__cmpwait((ptr), (unsigned long)(val), sizeof(*(ptr)))

We might want to call this cmpwait_relaxed, in case we decide to add fenced versions in the future. Or just make it cmpwait_acquire and remove the smp_rmb() from smp_cond_load_acquire(). Dunno.

Quoted 1 line · Will Deacon

Thanks for looking at this!

n/p, had to se what it would look like etc.. :-)

Quoted 8 lines

Quoted 1 line

I've misplaced my arm64 compiler, so this is not even compile tested.

Guess what? ;)

make: *** [init] Error 2
make: *** Waiting for unfinished jobs....

Quoted 7 lines

(and lot of similar errors).

Looks like you're just missing an #undef in cmpxchg.h.

FWIW, you can pick up arm64 toolchain binaries from:

https://releases.linaro.org/components/toolchain/binaries/latest-5/

Ah, I usually build a whole set from sources; for some reason arm64 didn't build in the latest run. I'll have to kick it.

Quoted 4 lines

Quoted 4 lines

(quoted diff) +4 -0

+#define __CMPWAIT_GEN(w, sz, name)					\
+void __cmpwait_case_##name(volatile void *ptr, unsigned long val)	\
+{									\
+	unsigned long tmp;						\

Quoted 8 lines

Review

Quoted 5 lines

(quoted diff) +5 -0

+									\
+	asm volatile(							\
+	"	ldxr" #sz "\t%" #w "[tmp], %[v]\n"			\
+	"	eor	%" #w "[tmp], %" #w "[tmp], %" #w "[val]\n"	\
+	"	cbnz	%" #w "[tmp], 1f\n"				\

Shouldn't this be cbz? (i.e. branch over the wfe if the value is equal to what we wanted?).

Indeed so.

Quoted 5 lines

Review

Quoted 3 lines

(quoted diff) +3 -0

+	"	wfe\n"							\
+	"1:"								\
+	: [tmp] "=&r" (tmp), [val] "=&r" (val),				\

We only read val, so it can be an input operand, no?

True.. :-)

Quoted 6 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+#define cmpwait(ptr, val) \
+	__cmpwait((ptr), (unsigned long)(val), sizeof(*(ptr)))

We might want to call this cmpwait_relaxed, in case we decide to add fenced versions in the future. Or just make it cmpwait_acquire and remove the smp_rmb() from smp_cond_load_acquire(). Dunno.

This is something I'll very much leave up to you. I have no idea on the tradeoffs involved here.

From 5aa5750d5eeb6e3a42f5547f094dc803f89793bb Mon Sep 17 00:00:00 2001

From 5aa5750d5eeb6e3a42f5547f094dc803f89793bb Mon Sep 17 00:00:00 2001
From: Will Deacon <[email protected]>
Date: Tue, 26 Apr 2016 17:31:53 +0100
Subject: [PATCH] fixup! locking,arm64: Introduce cmpwait()

Signed-off-by Will Deacon <[email protected]>

---
 arch/arm64/include/asm/cmpxchg.h | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

arch/arm64/include/asm/cmpxchg.h +0 -1

index cd7bff6ddedc..9b7113a3f0d7 100644
@@ -225,18 +225,19 @@ __CMPXCHG_GEN(_mb)
 })
 
 #define __CMPWAIT_GEN(w, sz, name)					\
-void __cmpwait_case_##name(volatile void *ptr, unsigned long val)	\

Actually, you're right with cbnz. I only noticed when I came to implement my own version of smp_cond_load_acquire. *sigh*

I have fixups applied locally, so maybe the best thing is for me to send you an arm64 series on top of whatever you post next?

Quoted 11 lines

arch/arm64/include/asm/cmpxchg.h +11 -0

+static inline void __cmpwait(volatile void *ptr, unsigned long val, int size)
+{
+	switch (size) {
+	case 1: return __cmpwait_case_1(ptr, val);
+	case 2: return __cmpwait_case_2(ptr, val);
+	case 4: return __cmpwait_case_4(ptr, val);
+	case 8: return __cmpwait_case_8(ptr, val);
+	default: BUILD_BUG();
+	}
+
+	unreachable();

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 261

Quoted 4 lines

arch/arm64/include/asm/cmpxchg.h +4 -0

+}
+
+#define cmpwait(ptr, val) \
+	__cmpwait((ptr), (unsigned long)(val), sizeof(*(ptr)))

We might want to call this cmpwait_relaxed, in case we decide to add fenced versions in the future. Or just make it cmpwait_acquire and remove the smp_rmb() from smp_cond_load_acquire(). Dunno.

Will

On Tue, Apr 12, 2016 at 05:59:41PM +0100, Will Deacon wrote:
[...]

Quoted 11 lines

Quoted 11 lines

arch/arm64/include/asm/cmpxchg.h +11 -0

+static inline void __cmpwait(volatile void *ptr, unsigned long val, int size)
+{
+	switch (size) {
+	case 1: return __cmpwait_case_1(ptr, val);
+	case 2: return __cmpwait_case_2(ptr, val);
+	case 4: return __cmpwait_case_4(ptr, val);
+	case 8: return __cmpwait_case_8(ptr, val);
+	default: BUILD_BUG();
+	}
+
+	unreachable();

Quoted 9 lines

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 261

Quoted 4 lines

arch/arm64/include/asm/cmpxchg.h +4 -0

+}
+
+#define cmpwait(ptr, val) \
+	__cmpwait((ptr), (unsigned long)(val), sizeof(*(ptr)))

We might want to call this cmpwait_relaxed, in case we decide to add fenced versions in the future. Or just make it cmpwait_acquire and remove the smp_rmb() from smp_cond_load_acquire(). Dunno.

How about replace smp_rmb() with a smp_acquire_barrier__after_cmpwait()? This barrier is designed to provide an ACQUIRE ordering when combining a cmpwait() .

And cmpwait() only has minimal ordering guarantee, but if it is actually an ACQUIRE, then the corresponding smp_acquire_barrier__after_cmpwait() is just empty.

Quoted 27 lines · Boqun Feng

On Tue, Apr 12, 2016 at 05:59:41PM +0100, Will Deacon wrote:
[...]

Quoted 11 lines

Quoted 11 lines

arch/arm64/include/asm/cmpxchg.h +11 -0

+static inline void __cmpwait(volatile void *ptr, unsigned long val, int size)
+{
+	switch (size) {
+	case 1: return __cmpwait_case_1(ptr, val);
+	case 2: return __cmpwait_case_2(ptr, val);
+	case 4: return __cmpwait_case_4(ptr, val);
+	case 8: return __cmpwait_case_8(ptr, val);
+	default: BUILD_BUG();
+	}
+
+	unreachable();

Quoted 9 lines

arch/arm64/include/asm/cmpxchg.h __CMPXCHG_GEN(_mb) · line 261

Quoted 4 lines

arch/arm64/include/asm/cmpxchg.h +4 -0

+}
+
+#define cmpwait(ptr, val) \
+	__cmpwait((ptr), (unsigned long)(val), sizeof(*(ptr)))

We might want to call this cmpwait_relaxed, in case we decide to add fenced versions in the future. Or just make it cmpwait_acquire and remove the smp_rmb() from smp_cond_load_acquire(). Dunno.

How about replace smp_rmb() with a smp_acquire_barrier__after_cmpwait()? This barrier is designed to provide an ACQUIRE ordering when combining a cmpwait() .

Quoted 3 lines

And cmpwait() only has minimal ordering guarantee, but if it is actually an ACQUIRE, then the corresponding smp_acquire_barrier__after_cmpwait() is just empty.

Maybe, but that makes it difficult for me to use a load-acquire instruction for the ACQUIRE case.

Will

How about replace smp_rmb() with a smp_acquire_barrier__after_cmpwait()? This barrier is designed to provide an ACQUIRE ordering when combining a cmpwait() .

And cmpwait() only has minimal ordering guarantee, but if it is actually an ACQUIRE, then the corresponding smp_acquire_barrier__after_cmpwait() is just empty.

We might need this special barrier on ppc, because we can implement it with "isync" given that cmpwait() has control dependency and ctrl+isync is ACQUIRE on ppc.

Thoughts?

Quoted 3 lines · Boqun Feng

How about replace smp_rmb() with a smp_acquire_barrier__after_cmpwait()? This barrier is designed to provide an ACQUIRE ordering when combining a cmpwait() .

That's a horrible name for a barrier :-)

Quoted 9 lines

And cmpwait() only has minimal ordering guarantee, but if it is actually an ACQUIRE, then the corresponding smp_acquire_barrier__after_cmpwait() is just empty.

We might need this special barrier on ppc, because we can implement it with "isync" given that cmpwait() has control dependency and ctrl+isync is ACQUIRE on ppc.

Thoughts?

Provide a PPC specific smp_cond_load_acquire() using ISYNC ?