Skip to contentSkip to conversation

Switch arm64 over to qrwlock

PATCH Superseded Will Deacon 7 participants 20 messages Oct 6, 2017 – Oct 11, 2017

Subsystems (4)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

v2 cover Switch arm64 over to qrwlock

Hi all,

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

Cheers,

Will

--->8

Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct __qrwlock locking/atomic: Add atomic_cond_read_acquire kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpath

 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 include/asm-generic/atomic-long.h       |   3 +
 include/asm-generic/qrwlock.h           |  20 +---
 include/asm-generic/qrwlock_types.h     |  15 ++-
 include/linux/atomic.h                  |   4 +
 kernel/locking/qrwlock.c                |  83 +++-------------
 9 files changed, 58 insertions(+), 255 deletions(-)
Signature · 1 line
2.1.4
#1 lore raw

PATCH v2 1/5 kernel/locking: Use struct qrwlock instead of struct __qrwlock

There's no good reason to keep the internal structure of struct qrwlock hidden from qrwlock.h, particularly as it's actually needed for unlock and ends up being abstracted independently behind the __qrwlock_write_byte function.

Stop pretending we can hide this stuff, and move the __qrwlock definition into qrwlock, removing the __qrwlock_write_byte nastiness and using the same struct definition everywhere instead.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 include/asm-generic/qrwlock.h       | 12 +-----------
 include/asm-generic/qrwlock_types.h | 15 +++++++++++++--
 kernel/locking/qrwlock.c            | 26 ++------------------------
 3 files changed, 16 insertions(+), 37 deletions(-)
include/asm-generic/qrwlock.h +1 -11
index 50925327b0a8..02c0a768e6b0 100644
@@ -129,22 +129,12 @@ static inline void queued_read_unlock(struct qrwlock *lock)
 }
 
 /**
- * __qrwlock_write_byte - retrieve the write byte address of a queue rwlock
- * @lock : Pointer to queue rwlock structure
- * Return: the write byte address of a queue rwlock
- */
-static inline u8 *__qrwlock_write_byte(struct qrwlock *lock)
-{
-	return (u8 *)lock + 3 * IS_BUILTIN(CONFIG_CPU_BIG_ENDIAN);
-}
-
-/**
  * queued_write_unlock - release write lock of a queue rwlock
  * @lock : Pointer to queue rwlock structure
  */
 static inline void queued_write_unlock(struct qrwlock *lock)
 {
-	smp_store_release(__qrwlock_write_byte(lock), 0);
+	smp_store_release(&lock->wmode, 0);
 }
 
 /*
include/asm-generic/qrwlock_types.h +13 -2
index 0abc6b6062fb..507f2dc51bba 100644
@@ -9,12 +9,23 @@
  */
 
 typedef struct qrwlock {
-	atomic_t		cnts;
+	union {
+		atomic_t cnts;
+		struct {
+#ifdef __LITTLE_ENDIAN
+			u8 wmode;	/* Writer mode   */
+			u8 rcnts[3];	/* Reader counts */
+#else
+			u8 rcnts[3];	/* Reader counts */
+			u8 wmode;	/* Writer mode   */
+#endif
+		};
+	};
 	arch_spinlock_t		wait_lock;
 } arch_rwlock_t;
 
 #define	__ARCH_RW_LOCK_UNLOCKED {		\
-	.cnts = ATOMIC_INIT(0),			\
+	{ .cnts = ATOMIC_INIT(0), },		\
 	.wait_lock = __ARCH_SPIN_LOCK_UNLOCKED,	\
 }
 
kernel/locking/qrwlock.c +2 -24
index 2655f26ec882..1af791e37348 100644
@@ -23,26 +23,6 @@
 #include <linux/spinlock.h>
 #include <asm/qrwlock.h>
 
-/*
- * This internal data structure is used for optimizing access to some of
- * the subfields within the atomic_t cnts.
- */
-struct __qrwlock {
-	union {
-		atomic_t cnts;
-		struct {
-#ifdef __LITTLE_ENDIAN
-			u8 wmode;	/* Writer mode   */
-			u8 rcnts[3];	/* Reader counts */
-#else
-			u8 rcnts[3];	/* Reader counts */
-			u8 wmode;	/* Writer mode   */
-#endif
-		};
-	};
-	arch_spinlock_t	lock;
-};
-
 /**
  * rspin_until_writer_unlock - inc reader count & spin until writer is gone
  * @lock  : Pointer to queue rwlock structure
@@ -125,10 +105,8 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 	 * or wait for a previous writer to go away.
 	 */
 	for (;;) {
-		struct __qrwlock *l = (struct __qrwlock *)lock;
-
-		if (!READ_ONCE(l->wmode) &&
-		   (cmpxchg_relaxed(&l->wmode, 0, _QW_WAITING) == 0))
+		if (!READ_ONCE(lock->wmode) &&
+		   (cmpxchg_relaxed(&lock->wmode, 0, _QW_WAITING) == 0))
 			break;
 
 		cpu_relax();
Signature · 1 line
2.1.4
#2 lore raw

PATCH v2 2/5 locking/atomic: Add atomic_cond_read_acquire

In reply to Will Deacon

smp_cond_load_acquire provides a way to spin on a variable with acquire semantics until some conditional expression involing the variable is satisfied. Architectures such as arm64 can potentially enter a low-power state, waking up only when the value of the variable changes, which reduces the system impact of tight polling loops.

This patch makes the same interface available to users of atomic_t, atomic64_t and atomic_long_t, rather than require messy accesses to the structure internals.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 include/asm-generic/atomic-long.h | 3 +++
 include/linux/atomic.h            | 4 ++++
 2 files changed, 7 insertions(+)
include/asm-generic/atomic-long.h +3 -0
index 288cc9e96395..f2d97b782031 100644
@@ -243,4 +243,7 @@ static inline long atomic_long_add_unless(atomic_long_t *l, long a, long u)
 #define atomic_long_inc_not_zero(l) \
 	ATOMIC_LONG_PFX(_inc_not_zero)((ATOMIC_LONG_PFX(_t) *)(l))
 
+#define atomic_long_cond_read_acquire(v, c) \
+	ATOMIC_LONG_PFX(_cond_read_acquire)((ATOMIC_LONG_PFX(_t) *)(v), (c))
+
 #endif  /*  _ASM_GENERIC_ATOMIC_LONG_H  */
include/linux/atomic.h +4 -0
index 40d6bfec0e0d..0aeb2b3f4578 100644
@@ -653,6 +653,8 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 }
 #endif
 
+#define atomic_cond_read_acquire(v, c)	smp_cond_load_acquire(&(v)->counter, (c))
+
 #ifdef CONFIG_GENERIC_ATOMIC64
 #include <asm-generic/atomic64.h>
 #endif
@@ -1072,6 +1074,8 @@ static inline long long atomic64_fetch_andnot_release(long long i, atomic64_t *v
 }
 #endif
 
+#define atomic64_cond_read_acquire(v, c)	smp_cond_load_acquire(&(v)->counter, (c))
+
 #include <asm-generic/atomic-long.h>
 
 #endif /* _LINUX_ATOMIC_H */
Signature · 1 line
2.1.4
#3 lore raw

PATCH v2 3/5 kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock

In reply to Will Deacon

The qrwlock slowpaths involve spinning when either a prospective reader is waiting for a concurrent writer to drain, or a prospective writer is waiting for concurrent readers to drain. In both of these situations, atomic_cond_read_acquire can be used to avoid busy-waiting and make use of any backoff functionality provided by the architecture.

This patch replaces the open-code loops and rspin_until_writer_unlock implementation with atomic_cond_read_acquire. The write mode transition zero to _QW_WAITING is left alone, since (a) this doesn't need acquire semantics and (b) should be fast.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 kernel/locking/qrwlock.c | 47 +++++++++++------------------------------------
 1 file changed, 11 insertions(+), 36 deletions(-)
kernel/locking/qrwlock.c +11 -36
index 1af791e37348..b7ea4647c74d 100644
@@ -24,23 +24,6 @@
 #include <asm/qrwlock.h>
 
 /**
- * rspin_until_writer_unlock - inc reader count & spin until writer is gone
- * @lock  : Pointer to queue rwlock structure
- * @writer: Current queue rwlock writer status byte
- *
- * In interrupt context or at the head of the queue, the reader will just
- * increment the reader count & wait until the writer releases the lock.
- */
-static __always_inline void
-rspin_until_writer_unlock(struct qrwlock *lock, u32 cnts)
-{
-	while ((cnts & _QW_WMASK) == _QW_LOCKED) {
-		cpu_relax();
-		cnts = atomic_read_acquire(&lock->cnts);
-	}
-}
-
-/**
  * queued_read_lock_slowpath - acquire read lock of a queue rwlock
  * @lock: Pointer to queue rwlock structure
  * @cnts: Current qrwlock lock value
@@ -53,13 +36,12 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	if (unlikely(in_interrupt())) {
 		/*
 		 * Readers in interrupt context will get the lock immediately
-		 * if the writer is just waiting (not holding the lock yet).
-		 * The rspin_until_writer_unlock() function returns immediately
-		 * in this case. Otherwise, they will spin (with ACQUIRE
-		 * semantics) until the lock is available without waiting in
-		 * the queue.
+		 * if the writer is just waiting (not holding the lock yet),
+		 * so spin with ACQUIRE semantics until the lock is available
+		 * without waiting in the queue.
 		 */
-		rspin_until_writer_unlock(lock, cnts);
+		atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK)
+					 != _QW_LOCKED);
 		return;
 	}
 	atomic_sub(_QR_BIAS, &lock->cnts);
@@ -68,14 +50,14 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	 * Put the reader into the wait queue
 	 */
 	arch_spin_lock(&lock->wait_lock);
+	atomic_add(_QR_BIAS, &lock->cnts);
 
 	/*
 	 * The ACQUIRE semantics of the following spinning code ensure
 	 * that accesses can't leak upwards out of our subsequent critical
 	 * section in the case that the lock is currently held for write.
 	 */
-	cnts = atomic_fetch_add_acquire(_QR_BIAS, &lock->cnts);
-	rspin_until_writer_unlock(lock, cnts);
+	atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK) != _QW_LOCKED);
 
 	/*
 	 * Signal the next one in queue to become queue head
@@ -90,8 +72,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);
 
@@ -113,15 +93,10 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 	}
 
 	/* 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;
-
-		cpu_relax();
-	}
+	do {
+		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
+	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
+					_QW_LOCKED) != _QW_WAITING);
 unlock:
 	arch_spin_unlock(&lock->wait_lock);
 }
Signature · 1 line
2.1.4
#4 lore raw

Re: [PATCH v2 3/5] kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock

kernel/locking/qrwlock.c void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)

Quoted 50 lines · Will Deacon

The qrwlock slowpaths involve spinning when either a prospective reader is waiting for a concurrent writer to drain, or a prospective writer is waiting for concurrent readers to drain. In both of these situations, atomic_cond_read_acquire can be used to avoid busy-waiting and make use of any backoff functionality provided by the architecture.

This patch replaces the open-code loops and rspin_until_writer_unlock implementation with atomic_cond_read_acquire. The write mode transition zero to _QW_WAITING is left alone, since (a) this doesn't need acquire semantics and (b) should be fast.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 kernel/locking/qrwlock.c | 47 +++++++++++------------------------------------
 1 file changed, 11 insertions(+), 36 deletions(-)
kernel/locking/qrwlock.c +0 -17
index 1af791e37348..b7ea4647c74d 100644
@@ -24,23 +24,6 @@
 #include <asm/qrwlock.h>
 
 /**
- * rspin_until_writer_unlock - inc reader count & spin until writer is gone
- * @lock  : Pointer to queue rwlock structure
- * @writer: Current queue rwlock writer status byte
- *
- * In interrupt context or at the head of the queue, the reader will just
- * increment the reader count & wait until the writer releases the lock.
- */
-static __always_inline void
-rspin_until_writer_unlock(struct qrwlock *lock, u32 cnts)
-{
-	while ((cnts & _QW_WMASK) == _QW_LOCKED) {
-		cpu_relax();
-		cnts = atomic_read_acquire(&lock->cnts);
-	}
-}
-
-/**
  * queued_read_lock_slowpath - acquire read lock of a queue rwlock
  * @lock: Pointer to queue rwlock structure
  * @cnts: Current qrwlock lock value
@@ -53,13 +36,12 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)

So the second parameter(@cnts) could be removed entirely, right? Any reason we still keep it?

Regards,
Boqun

Quoted 35 lines
kernel/locking/qrwlock.c +7 -8
 	if (unlikely(in_interrupt())) {
 		/*
 		 * Readers in interrupt context will get the lock immediately
-		 * if the writer is just waiting (not holding the lock yet).
-		 * The rspin_until_writer_unlock() function returns immediately
-		 * in this case. Otherwise, they will spin (with ACQUIRE
-		 * semantics) until the lock is available without waiting in
-		 * the queue.
+		 * if the writer is just waiting (not holding the lock yet),
+		 * so spin with ACQUIRE semantics until the lock is available
+		 * without waiting in the queue.
 		 */
-		rspin_until_writer_unlock(lock, cnts);
+		atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK)
+					 != _QW_LOCKED);
 		return;
 	}
 	atomic_sub(_QR_BIAS, &lock->cnts);
@@ -68,14 +50,14 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	 * Put the reader into the wait queue
 	 */
 	arch_spin_lock(&lock->wait_lock);
+	atomic_add(_QR_BIAS, &lock->cnts);
 
 	/*
 	 * The ACQUIRE semantics of the following spinning code ensure
 	 * that accesses can't leak upwards out of our subsequent critical
 	 * section in the case that the lock is currently held for write.
 	 */
-	cnts = atomic_fetch_add_acquire(_QR_BIAS, &lock->cnts);
-	rspin_until_writer_unlock(lock, cnts);
+	atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK) != _QW_LOCKED);
 
 	/*
 	 * Signal the next one in queue to become queue head

[...]

#5 lore raw

Re: [PATCH v2 3/5] kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock

Quoted 46 lines · Boqun Feng
Quoted 45 lines · Will Deacon

The qrwlock slowpaths involve spinning when either a prospective reader is waiting for a concurrent writer to drain, or a prospective writer is waiting for concurrent readers to drain. In both of these situations, atomic_cond_read_acquire can be used to avoid busy-waiting and make use of any backoff functionality provided by the architecture.

This patch replaces the open-code loops and rspin_until_writer_unlock implementation with atomic_cond_read_acquire. The write mode transition zero to _QW_WAITING is left alone, since (a) this doesn't need acquire semantics and (b) should be fast.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 kernel/locking/qrwlock.c | 47 +++++++++++------------------------------------
 1 file changed, 11 insertions(+), 36 deletions(-)
kernel/locking/qrwlock.c +0 -16
index 1af791e37348..b7ea4647c74d 100644
@@ -24,23 +24,6 @@
 #include <asm/qrwlock.h>
 
 /**
- * rspin_until_writer_unlock - inc reader count & spin until writer is gone
- * @lock  : Pointer to queue rwlock structure
- * @writer: Current queue rwlock writer status byte
- *
- * In interrupt context or at the head of the queue, the reader will just
- * increment the reader count & wait until the writer releases the lock.
- */
-static __always_inline void
-rspin_until_writer_unlock(struct qrwlock *lock, u32 cnts)
-{
-	while ((cnts & _QW_WMASK) == _QW_LOCKED) {
-		cpu_relax();
-		cnts = atomic_read_acquire(&lock->cnts);
-	}
-}
-
Quoted 8 lines

kernel/locking/qrwlock.c void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)

Quoted 5 lines
kernel/locking/qrwlock.c +0 -1
-/**
  * queued_read_lock_slowpath - acquire read lock of a queue rwlock
  * @lock: Pointer to queue rwlock structure
  * @cnts: Current qrwlock lock value
@@ -53,13 +36,12 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)

So the second parameter(@cnts) could be removed entirely, right? Any reason we still keep it?

Well spotted! I'll remove it.

Will

#6 lore raw

PATCH v2 4/5 arm64: locking: Move rwlock implementation over to qrwlocks

In reply to Will Deacon

Now that the qrwlock can make use of WFE, remove our homebrew rwlock code in favour of the generic queued implementation.

---
 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 4 files changed, 20 insertions(+), 168 deletions(-)
arch/arm64/Kconfig +17 -0
index 0df64a6a56d4..6d32c9b0d4bb 100644
@@ -22,7 +22,24 @@ config ARM64
 	select ARCH_HAS_STRICT_MODULE_RWX
 	select ARCH_HAS_TICK_BROADCAST if GENERIC_CLOCKEVENTS_BROADCAST
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG if ACPI_APEI_SEA
+	select ARCH_INLINE_READ_LOCK if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQSAVE if !PREEMPT
 	select ARCH_USE_CMPXCHG_LOCKREF
+	select ARCH_USE_QUEUED_RWLOCKS
 	select ARCH_SUPPORTS_MEMORY_FAILURE
 	select ARCH_SUPPORTS_ATOMIC_RMW
 	select ARCH_SUPPORTS_NUMA_BALANCING
arch/arm64/include/asm/Kbuild +1 -0
index 2326e39d5892..e63d0a8312de 100644
@@ -16,6 +16,7 @@ generic-y += mcs_spinlock.h
 generic-y += mm-arch-hooks.h
 generic-y += msi.h
 generic-y += preempt.h
+generic-y += qrwlock.h
 generic-y += rwsem.h
 generic-y += segment.h
 generic-y += serial.h
arch/arm64/include/asm/spinlock.h +1 -163

170 lines not on this page · raw message

arch/arm64/include/asm/spinlock_types.h +1 -5
index 55be59a35e3f..6b856012c51b 100644
@@ -36,10 +36,6 @@ typedef struct {
 
 #define __ARCH_SPIN_LOCK_UNLOCKED	{ 0 , 0 }
 
-typedef struct {
-	volatile unsigned int lock;
-} arch_rwlock_t;
-
-#define __ARCH_RW_LOCK_UNLOCKED		{ 0 }
+#include <asm-generic/qrwlock_types.h>
 
 #endif
Signature · 1 line
2.1.4
reviewer
#7 lore raw

Re: [PATCH v2 4/5] arm64: locking: Move rwlock implementation over to qrwlocks

Quoted 30 lines · Will Deacon

Now that the qrwlock can make use of WFE, remove our homebrew rwlock code in favour of the generic queued implementation.

---
 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 4 files changed, 20 insertions(+), 168 deletions(-)
arch/arm64/Kconfig +11 -0
index 0df64a6a56d4..6d32c9b0d4bb 100644
@@ -22,7 +22,24 @@ config ARM64
 	select ARCH_HAS_STRICT_MODULE_RWX
 	select ARCH_HAS_TICK_BROADCAST if GENERIC_CLOCKEVENTS_BROADCAST
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG if ACPI_APEI_SEA
+	select ARCH_INLINE_READ_LOCK if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_IRQ if !PREEMPT

arch/arm64/Kconfig config ARM64 · line 45

Quoted 10 lines
arch/arm64/Kconfig +6 -0
+	select ARCH_INLINE_WRITE_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQSAVE if !PREEMPT
 	select ARCH_USE_CMPXCHG_LOCKREF
+	select ARCH_USE_QUEUED_RWLOCKS
 	select ARCH_SUPPORTS_MEMORY_FAILURE
 	select ARCH_SUPPORTS_ATOMIC_RMW
 	select ARCH_SUPPORTS_NUMA_BALANCING

Inlining is good for performance, but it may come with an increase in kernel text size. Inlining unlock and unlock_irq are OK, but the other inlines will increase the text size of the kernel. Have you measured how much size increase will that be? Is there any concern about the increased text size?

Cheers,
Longman

#8 lore raw

Re: [PATCH v2 4/5] arm64: locking: Move rwlock implementation over to qrwlocks

Hi Waiman,

Quoted 39 lines · Waiman Long
Quoted 38 lines · Will Deacon

Now that the qrwlock can make use of WFE, remove our homebrew rwlock code in favour of the generic queued implementation.

---
 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 4 files changed, 20 insertions(+), 168 deletions(-)
arch/arm64/Kconfig +17 -0
index 0df64a6a56d4..6d32c9b0d4bb 100644
@@ -22,7 +22,24 @@ config ARM64
 	select ARCH_HAS_STRICT_MODULE_RWX
 	select ARCH_HAS_TICK_BROADCAST if GENERIC_CLOCKEVENTS_BROADCAST
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG if ACPI_APEI_SEA
+	select ARCH_INLINE_READ_LOCK if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_READ_UNLOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_WRITE_LOCK_IRQSAVE if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_BH if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQ if !PREEMPT
+	select ARCH_INLINE_WRITE_UNLOCK_IRQSAVE if !PREEMPT
 	select ARCH_USE_CMPXCHG_LOCKREF
+	select ARCH_USE_QUEUED_RWLOCKS
 	select ARCH_SUPPORTS_MEMORY_FAILURE
Quoted 8 lines

arch/arm64/Kconfig config ARM64 · line 45

Quoted 2 lines
arch/arm64/Kconfig +0 -0
 	select ARCH_SUPPORTS_ATOMIC_RMW
 	select ARCH_SUPPORTS_NUMA_BALANCING

Inlining is good for performance, but it may come with an increase in kernel text size. Inlining unlock and unlock_irq are OK, but the other inlines will increase the text size of the kernel. Have you measured how much size increase will that be? Is there any concern about the increased text size?

Yes, I did look at the disassembly and bloat-o-meter results. Inlining these functions means that the fastpath sits entirely within a 64-byte cacheline and bloat-o-meter shows a relatively small increase in vmlinux size for a defconfig build with CONFIG_PREEMPT disabled:

Total: Before=13800924, After=13812904, chg +0.09%

(I also just noticed my typos in ARCH_INLINE_{READ.WRITE}_UNLOCK_IRQSAVE so I regenerated the numbers!)

Will

reviewer
#9 lore raw

Re: [PATCH v2 4/5] arm64: locking: Move rwlock implementation over to qrwlocks

Quoted 13 lines · Will Deacon

Hi Waiman,

Quoted 6 lines

Inlining is good for performance, but it may come with an increase in kernel text size. Inlining unlock and unlock_irq are OK, but the other inlines will increase the text size of the kernel. Have you measured how much size increase will that be? Is there any concern about the increased text size?

Yes, I did look at the disassembly and bloat-o-meter results. Inlining these functions means that the fastpath sits entirely within a 64-byte cacheline and bloat-o-meter shows a relatively small increase in vmlinux size for a defconfig build with CONFIG_PREEMPT disabled:

Quoted 4 lines

Total: Before=13800924, After=13812904, chg +0.09%

(I also just noticed my typos in ARCH_INLINE_{READ.WRITE}_UNLOCK_IRQSAVE so I regenerated the numbers!)

The size increase looks small enough. That may largely due to the fact that rwlocks aren't as frequently used as spinlocks, so the number of call sites are not that many. Anyway, I am OK with that. I just want to make sure that people are aware of this.

Cheers,
Longman

#10 lore raw

PATCH v2 5/5 kernel/locking: Prevent slowpath writers getting held up by fastpath

In reply to Will Deacon

When a prospective writer takes the qrwlock locking slowpath due to the lock being held, it attempts to cmpxchg the wmode field from 0 to _QW_WAITING so that concurrent lockers also take the slowpath and queue on the spinlock accordingly, allowing the lockers to drain.

Unfortunately, this isn't fair, because a fastpath writer that comes in after the lock is made available but before the _QW_WAITING flag is set can effectively jump the queue. If there is a steady stream of prospective writers, then the waiter will be held off indefinitely.

This patch restores fairness by separating _QW_WAITING and _QW_LOCKED into two distinct fields: _QW_LOCKED continues to occupy the bottom byte of the lockword so that it can be cleared unconditionally when unlocking, but _QW_WAITING now occupies what used to be the bottom bit of the reader count. This then forces the slow-path for concurrent lockers.

Cc Peter Zijlstra <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Waiman Long <[email protected]>
Cc Boqun Feng <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
---
 include/asm-generic/qrwlock.h       | 10 +++++-----
 include/asm-generic/qrwlock_types.h |  8 ++++----
 kernel/locking/qrwlock.c            | 20 +++++---------------
 3 files changed, 14 insertions(+), 24 deletions(-)
include/asm-generic/qrwlock.h +5 -5
index 02c0a768e6b0..63cb7d347b25 100644
@@ -40,10 +40,10 @@
  *       |      rd      | wr |
  *       +----+----+----+----+
  */
-#define	_QW_WAITING	1		/* A writer is waiting	   */
-#define	_QW_LOCKED	0xff		/* A writer holds the lock */
-#define	_QW_WMASK	0xff		/* Writer mask		   */
-#define	_QR_SHIFT	8		/* Reader count shift	   */
+#define	_QW_WAITING	0x100		/* A writer is waiting	   */
+#define	_QW_LOCKED	0x0ff		/* A writer holds the lock */
+#define	_QW_WMASK	0x1ff		/* Writer mask		   */
+#define	_QR_SHIFT	9		/* Reader count shift	   */
 #define _QR_BIAS	(1U << _QR_SHIFT)
 
 /*
@@ -134,7 +134,7 @@ static inline void queued_read_unlock(struct qrwlock *lock)
  */
 static inline void queued_write_unlock(struct qrwlock *lock)
 {
-	smp_store_release(&lock->wmode, 0);
+	smp_store_release(&lock->wlocked, 0);
 }
 
 /*
include/asm-generic/qrwlock_types.h +4 -4
index 507f2dc51bba..8af752acbdc0 100644
@@ -13,11 +13,11 @@ typedef struct qrwlock {
 		atomic_t cnts;
 		struct {
 #ifdef __LITTLE_ENDIAN
-			u8 wmode;	/* Writer mode   */
-			u8 rcnts[3];	/* Reader counts */
+			u8 wlocked;	/* Locked for write? */
+			u8 __lstate[3];
 #else
-			u8 rcnts[3];	/* Reader counts */
-			u8 wmode;	/* Writer mode   */
+			u8 __lstate[3];
+			u8 wlocked;	/* Locked for write? */
 #endif
 		};
 	};
kernel/locking/qrwlock.c +5 -15
index b7ea4647c74d..e940f2c2b4f2 100644
@@ -40,8 +40,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 		 * so spin with ACQUIRE semantics until the lock is available
 		 * without waiting in the queue.
 		 */
-		atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK)
-					 != _QW_LOCKED);
+		atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));
 		return;
 	}
 	atomic_sub(_QR_BIAS, &lock->cnts);
@@ -57,7 +56,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock, u32 cnts)
 	 * that accesses can't leak upwards out of our subsequent critical
 	 * section in the case that the lock is currently held for write.
 	 */
-	atomic_cond_read_acquire(&lock->cnts, (VAL & _QW_WMASK) != _QW_LOCKED);
+	atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));
 
 	/*
 	 * Signal the next one in queue to become queue head
@@ -80,19 +79,10 @@ void queued_write_lock_slowpath(struct qrwlock *lock)
 	    (atomic_cmpxchg_acquire(&lock->cnts, 0, _QW_LOCKED) == 0))
 		goto unlock;
 
-	/*
-	 * Set the waiting flag to notify readers that a writer is pending,
-	 * or wait for a previous writer to go away.
-	 */
-	for (;;) {
-		if (!READ_ONCE(lock->wmode) &&
-		   (cmpxchg_relaxed(&lock->wmode, 0, _QW_WAITING) == 0))
-			break;
-
-		cpu_relax();
-	}
+	/* Set the waiting flag to notify readers that a writer is pending */
+	atomic_add(_QW_WAITING, &lock->cnts);
 
-	/* When no more readers, set the locked flag */
+	/* When no more readers or writers, set the locked flag */
 	do {
 		atomic_cond_read_acquire(&lock->cnts, VAL == _QW_WAITING);
 	} while (atomic_cmpxchg_relaxed(&lock->cnts, _QW_WAITING,
Signature · 1 line
2.1.4
#11 lore raw
In reply to Will Deacon
Quoted 12 lines · Will Deacon

Hi all,

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

I've updated my branch if you're after the full patch stack:

Quoted 8 lines

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

Cheers,

Will

Hi Will,

I tested your patches with locktorture and found measurable performance regression. I also respin the patch of Jan Glauber [1], and I also tried Jan's patch with patch 5 from this series. Numbers differ a lot from my previous measurements, but since that I changed working station and use qemu with the support of parallel threads.

                        Spinlock        Read-RW lock    Write-RW lock
Vanilla:                129804626       12340895        14716138
This series:            113718002       10982159        13068934
Jan patch:              117977108       11363462        13615449
Jan patch + #5:         121483176       11696728        13618967

The bottomline of discussion [1] was that queued locks are more effective when SoC has many CPUs. And 4 is not many. My measurement was made on the 4-CPU machine, and it seems it confirms that. Does it make sense to make queued locks default for many-CPU machines only?

There were 2 preparing patches in the series:
[PATCH 1/3] kernel/locking: #include <asm/spinlock.h> in qrwlock and
[PATCH 2/3] asm-generic: don't #include <linux/atomic.h> in qspinlock_types.h

1st patch is not needed anymore because Babu Moger submitted similar patch that is already in mainline: 9ab6055f95903 ("kernel/locking: Fix compile error with qrwlock.c"). Could you revisit second patch?

[1] https://lkml.org/lkml/2017/5/3/330

Yury

maintainer
#12 lore raw
Quoted 2 lines · Yury Norov

The bottomline of discussion [1] was that queued locks are more effective when SoC has many CPUs. And 4 is not many.

qspinlock, yes. qrwlock not, as it fully depends on arch_spinlock_t for the queueing. qrwlock is just a generic rwlock_t implementation.

#13 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Yury Norov

The bottomline of discussion [1] was that queued locks are more effective when SoC has many CPUs. And 4 is not many.

qspinlock, yes. qrwlock not, as it fully depends on arch_spinlock_t for the queueing. qrwlock is just a generic rwlock_t implementation.

Yup, and once I've knocked qrwlocks on the head I'll go take a look at qspinlock. Either way, I'll keep our ticket implementation around because
(a) it's a tonne simpler (b) I don't have data to suggest that it sucks and
(c) there's been formal work to show that various parts of it are correct.

rwlock on the other hand has been shown to be broken, I know that it sucks and there's not been any formal work, so I'll be glad to see the back of it!

Will

#14 lore raw
In reply to Yury Norov

Hi Yury,

Quoted 27 lines · Yury Norov
Quoted 8 lines · Will Deacon

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

Quoted 7 lines

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

I tested your patches with locktorture and found measurable performance regression. I also respin the patch of Jan Glauber [1], and I also tried Jan's patch with patch 5 from this series. Numbers differ a lot from my previous measurements, but since that I changed working station and use qemu with the support of parallel threads.

                        Spinlock        Read-RW lock    Write-RW lock
Vanilla:                129804626       12340895        14716138
This series:            113718002       10982159        13068934
Jan patch:              117977108       11363462        13615449
Jan patch + #5:         121483176       11696728        13618967
Quoted 4 lines

The bottomline of discussion [1] was that queued locks are more effective when SoC has many CPUs. And 4 is not many. My measurement was made on the 4-CPU machine, and it seems it confirms that. Does it make sense to make queued locks default for many-CPU machines only?

Just to confirm, you're running this under qemu on an x86 host, using full AArch64 system emulation? If so, I really don't think we should base the merits of qrwlocks on arm64 around this type of configuration. Given that you work for a silicon vendor, could you try running on real arm64 hardware instead, please? My measurements on 6-core and 8-core systems look a lot better with qrwlock than what we currently have in mainline, and they also fix a real starvation issue reported by Jeremy [1].

I'd also add that lock fairness comes at a cost, so I'd expect a small drop in total throughput for some workloads. I encourage you to try passing different arguments to locktorture to see this in action. For example, on an 8-core machine:

# insmod ./locktorture.ko nwriters_stress=2 nreaders_stress=8 torture_type="rw_lock_irq" stat_interval=2

-rc3:

  Writes:  Total: 6612  Max/Min: 0/0   Fail: 0
  Reads :  Total: 1265230  Max/Min: 0/0   Fail: 0
  Writes:  Total: 6709  Max/Min: 0/0   Fail: 0
  Reads :  Total: 1916418  Max/Min: 0/0   Fail: 0
  Writes:  Total: 6725  Max/Min: 0/0   Fail: 0
  Reads :  Total: 5103727  Max/Min: 0/0   Fail: 0

notice how the writers are really struggling here (you only have to tweak a bit more and you get RCU stalls, lose interrupts etc).

With the qrwlock:

  Writes:  Total: 47962  Max/Min: 0/0   Fail: 0
  Reads :  Total: 277903  Max/Min: 0/0   Fail: 0
  Writes:  Total: 100151  Max/Min: 0/0   Fail: 0
  Reads :  Total: 525781  Max/Min: 0/0   Fail: 0
  Writes:  Total: 155284  Max/Min: 0/0   Fail: 0
  Reads :  Total: 767703  Max/Min: 0/0   Fail: 0

which is an awful lot better for maximum latency and fairness, despite the much lower reader count.

Quoted 8 lines

There were 2 preparing patches in the series:
[PATCH 1/3] kernel/locking: #include <asm/spinlock.h> in qrwlock and
[PATCH 2/3] asm-generic: don't #include <linux/atomic.h> in qspinlock_types.h

1st patch is not needed anymore because Babu Moger submitted similar patch that is already in mainline: 9ab6055f95903 ("kernel/locking: Fix compile error with qrwlock.c"). Could you revisit second patch?

Sorry, not sure what you're asking me to do here.

Will

[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534299.html

#15 lore raw
Quoted 35 lines · Will Deacon

Hi Yury,

Quoted 27 lines · Yury Norov
Quoted 8 lines · Will Deacon

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

Quoted 7 lines

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

I tested your patches with locktorture and found measurable performance regression. I also respin the patch of Jan Glauber [1], and I also tried Jan's patch with patch 5 from this series. Numbers differ a lot from my previous measurements, but since that I changed working station and use qemu with the support of parallel threads.

                        Spinlock        Read-RW lock    Write-RW lock
Vanilla:                129804626       12340895        14716138
This series:            113718002       10982159        13068934
Jan patch:              117977108       11363462        13615449
Jan patch + #5:         121483176       11696728        13618967
Quoted 4 lines

The bottomline of discussion [1] was that queued locks are more effective when SoC has many CPUs. And 4 is not many. My measurement was made on the 4-CPU machine, and it seems it confirms that. Does it make sense to make queued locks default for many-CPU machines only?

Quoted 5 lines

Just to confirm, you're running this under qemu on an x86 host, using full AArch64 system emulation? If so, I really don't think we should base the merits of qrwlocks on arm64 around this type of configuration. Given that you work for a silicon vendor, could you try running on real arm64 hardware instead, please?

I don't have the hardware access at the moment. I'll run the test when I'll get it.

Quoted 40 lines

My measurements on 6-core and 8-core systems look a lot better with qrwlock than what we currently have in mainline, and they also fix a real starvation issue reported by Jeremy [1].

I'd also add that lock fairness comes at a cost, so I'd expect a small drop in total throughput for some workloads. I encourage you to try passing different arguments to locktorture to see this in action. For example, on an 8-core machine:

# insmod ./locktorture.ko nwriters_stress=2 nreaders_stress=8 torture_type="rw_lock_irq" stat_interval=2

-rc3:

  Writes:  Total: 6612  Max/Min: 0/0   Fail: 0
  Reads :  Total: 1265230  Max/Min: 0/0   Fail: 0
  Writes:  Total: 6709  Max/Min: 0/0   Fail: 0
  Reads :  Total: 1916418  Max/Min: 0/0   Fail: 0
  Writes:  Total: 6725  Max/Min: 0/0   Fail: 0
  Reads :  Total: 5103727  Max/Min: 0/0   Fail: 0

notice how the writers are really struggling here (you only have to tweak a bit more and you get RCU stalls, lose interrupts etc).

With the qrwlock:

  Writes:  Total: 47962  Max/Min: 0/0   Fail: 0
  Reads :  Total: 277903  Max/Min: 0/0   Fail: 0
  Writes:  Total: 100151  Max/Min: 0/0   Fail: 0
  Reads :  Total: 525781  Max/Min: 0/0   Fail: 0
  Writes:  Total: 155284  Max/Min: 0/0   Fail: 0
  Reads :  Total: 767703  Max/Min: 0/0   Fail: 0

which is an awful lot better for maximum latency and fairness, despite the much lower reader count.

Quoted 5 lines

There were 2 preparing patches in the series:
[PATCH 1/3] kernel/locking: #include <asm/spinlock.h> in qrwlock and
[PATCH 2/3] asm-generic: don't #include <linux/atomic.h> in qspinlock_types.h

Quoted 5 lines
Quoted 3 lines

1st patch is not needed anymore because Babu Moger submitted similar patch that is already in mainline: 9ab6055f95903 ("kernel/locking: Fix compile error with qrwlock.c"). Could you revisit second patch?

Sorry, not sure what you're asking me to do here.

It removes unneeded #include <linux/atomic.h> in include/asm-generic/qspinlock_types.h. Could you or someone else take it upstream?

Quoted 3 lines

Will

[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534299.html

#16 lore raw
Quoted 11 lines · Yury Norov
Quoted 10 lines · Will Deacon
Quoted 8 lines · Yury Norov

There were 2 preparing patches in the series:
[PATCH 1/3] kernel/locking: #include <asm/spinlock.h> in qrwlock and
[PATCH 2/3] asm-generic: don't #include <linux/atomic.h> in qspinlock_types.h

1st patch is not needed anymore because Babu Moger submitted similar patch that is already in mainline: 9ab6055f95903 ("kernel/locking: Fix compile error with qrwlock.c"). Could you revisit second patch?

Quoted 5 lines
Quoted 1 line

Sorry, not sure what you're asking me to do here.

It removes unneeded #include <linux/atomic.h> in include/asm-generic/qspinlock_types.h. Could you or someone else take it upstream?

My patch implements qrwlocks, not qspinlocks, so it's a bit weird to take this random patch in the same series. Given that Arnd acked it, I'd suggest either sending it through him, or leaving it until I get round to looking at qspinlock for arm64 (see my reply to Peter).

Will

reviewer Tested-by on the v2 series
#17 lore raw
In reply to Will Deacon
Quoted 30 lines · Will Deacon

Hi all,

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

Cheers,

Will

--->8

Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct __qrwlock locking/atomic: Add atomic_cond_read_acquire kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpath

Quoted 11 lines
 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 include/asm-generic/atomic-long.h       |   3 +
 include/asm-generic/qrwlock.h           |  20 +---
 include/asm-generic/qrwlock_types.h     |  15 ++-
 include/linux/atomic.h                  |   4 +
 kernel/locking/qrwlock.c                |  83 +++-------------
 9 files changed, 58 insertions(+), 255 deletions(-)

I had done some performance test of your patch on a 1 socket Cavium CN8880 system with 32 cores. I used my locking stress test which produced the following results with 16 locking threads at various mixes of reader & writer threads on 4.14-rc4 based kernels. The numbers are the minimum/average/maximum locking operations done per locking threads in a 10 seconds period. A minimum number of 1 means there is at least 1 thread that cannot acquire the lock during the test period.

w/o qrwlock patch with qrwlock patch
----------------- ------------------
16 readers 793,024/1,169,763/1,684,751 1,060,127/1,198,583/1,331,003

12 readers 1,162,760/1,641,714/2,162,939 1,685,334/2,099,088/2,338,461
4 writers 1/ 1/ 1 25,540/ 195,975/ 392,232

8 readers 2,135,670/2,391,612/2,737,564 2,985,686/3,359,048/3,870,423
8 writers 1/ 19,867/ 88,173 119,078/ 559,604/1,112,769

4 readers 1,194,917/1,250,876/1,299,304 3,611,059/4,653,775/6,268,370
12 writers 176,156/1,088,513/2,594,534 7,664/ 795,393/1,841,961

16 writers 35,007/1,094,608/1,954,457 1,618,915/1,633,077/1,645,637

It can be seen that qrwlock performed much better than the original rwlock implementation.

Cheers,
Longman

Tested-by on the v2 series
#18 lore raw
In reply to Will Deacon

Hi,

Quoted 10 lines · Will Deacon

Hi all,

This is version two of the patches I posted yesterday:

   http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

Quoted 6 lines

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

I've been doing perf comparisons with the rwlock fairness patch I posted last week on a single socket thunderx and the baseline rwlock. For most cases where the ratio of read/writers is similar (uncontended readers/writers, single writer/lots readers, etc) the absolute number of lock acquisitions is very similar (within a few percent one way or the other).

In this regard both patches are light years ahead of the current arm64 rwlock. The unfairness of the current rwlock allows significantly higher lock acquisition counts (say 4x at 30Readers:1Writer) at the expense of complete writer starvation (or a ~43k:1 ratio at a 30R:1W per locktorture). This is untenable.

The qrwlock does an excellent job of maintaining the ratio of reader/writer acquisitions proportional to the number of readers/writers until the total lockers exceeds the number of cores where the ratios start to far exceed the reader/writer ratios (440:1 acquisitions @ 96R:1W)

In comparison the other patch tends to favor the writers more, so at a ratio of 48R/1W, the readers are only grabbing the lock at a ratio of 15:1. This flatter curve continues past the number of cores with the readers having a 48:1 advantage with 96R/1W. That said the total lock acquisition counts remain very similar (with maybe a slight advantage to the non queued patch with 1 writer and 12-30 readers) despite the writer acquiring the lock at a higher frequency. OTOH, if the number of writers is closer to the number of readers (24R:24W) then the writers have about a 1.5X bias over the readers independent of the number of reader/writers. This bias seems to be the common multiplier given a reader/writer ratio with those patches and doesn't account for possible single thread starvation.

Of course, I've been running other tests as well and the system seems to be behaving as expected (likely better than the rwlock patches under stress). I will continue to test this on a couple other platforms.

In the meantime:

Quoted 25 lines

Cheers,

Will

--->8

Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct __qrwlock locking/atomic: Add atomic_cond_read_acquire kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpath

  arch/arm64/Kconfig                      |  17 ++++
  arch/arm64/include/asm/Kbuild           |   1 +
  arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
  arch/arm64/include/asm/spinlock_types.h |   6 +-
  include/asm-generic/atomic-long.h       |   3 +
  include/asm-generic/qrwlock.h           |  20 +---
  include/asm-generic/qrwlock_types.h     |  15 ++-
  include/linux/atomic.h                  |   4 +
  kernel/locking/qrwlock.c                |  83 +++-------------
  9 files changed, 58 insertions(+), 255 deletions(-)
Tested-by on the v2 series
#19 lore raw
In reply to Will Deacon
Quoted 30 lines · Will Deacon

Hi all,

This is version two of the patches I posted yesterday:

http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html

I'd normally leave it longer before posting again, but Peter had a good suggestion to rework the layout of the lock word, so I wanted to post a version that follows that approach.

I've updated my branch if you're after the full patch stack:

git://git.kernel.org/pub/scm/linux/kernel/git/will/linux.git qrwlock

As before, all comments (particularly related to testing and performance) welcome!

Cheers,

Will

--->8

Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct __qrwlock locking/atomic: Add atomic_cond_read_acquire kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpath

Quoted 11 lines
 arch/arm64/Kconfig                      |  17 ++++
 arch/arm64/include/asm/Kbuild           |   1 +
 arch/arm64/include/asm/spinlock.h       | 164 +-------------------------------
 arch/arm64/include/asm/spinlock_types.h |   6 +-
 include/asm-generic/atomic-long.h       |   3 +
 include/asm-generic/qrwlock.h           |  20 +---
 include/asm-generic/qrwlock_types.h     |  15 ++-
 include/linux/atomic.h                  |   4 +
 kernel/locking/qrwlock.c                |  83 +++-------------
 9 files changed, 58 insertions(+), 255 deletions(-)

Applied on 4.14-rc4, I tested these patches with multiple combinations of readers:writers . These patches help prevent writer starvation in every combination that I tested. Without these patches, when the reader:writer ratio is 2:1, it's trivial for me to see acquisitions of 250:1 (@ 2R:1W).

After applying the qrwlock patches, I see the acquisition ratios level out to around ~1.6:1 (@ 2R:1W), which is quite an improvement.

Thanks Will!

Signature · 4 lines
Adam Wallis
Qualcomm Datacenter Technologies as an affiliate of Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project.