Switch arm64 over to qrwlock
v3 cover Switch arm64 over to qrwlock
Hello,
This is version three of the patches previously posted here:
v1: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html
v2: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534981.html
Changes since v2 include:
* Drop unused cnt argument
* Fix typo in UNLOCK Kconfig inlining options
* Added Tested-by tags
Thanks to all of those who provided review and testing feedback!
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 | 37 ++----- include/asm-generic/qrwlock_types.h | 15 ++- include/linux/atomic.h | 4 + kernel/locking/qrwlock.c | 86 +++-------------- 9 files changed, 61 insertions(+), 272 deletions(-)
Signature · 1 line
2.1.4
PATCH v3 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.
--- 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
@@ -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
@@ -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
@@ -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
tip-bot for Will Deacon
merge bot[tip:locking/core] locking/qrwlock: Use 'struct qrwlock' instead of 'struct __qrwlock'
locking/qrwlock: Use 'struct qrwlock' instead of 'struct __qrwlock'
Commit-ID: e0d02285f16e8d5810f3d5d5e8a5886ca0015d3b Gitweb: https://git.kernel.org/tip/e0d02285f16e8d5810f3d5d5e8a5886ca0015d3b Author: Will Deacon <[email protected]> AuthorDate: Thu, 12 Oct 2017 13:20:47 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 25 Oct 2017 10:57:24 +0200
locking/qrwlock: 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.
--- 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
@@ -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
@@ -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
@@ -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 ();
PATCH v3 2/5 locking/atomic: Add atomic_cond_read_acquire
In reply to Will Deaconsmp_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.
--- 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
@@ -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
@@ -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
tip-bot for Will Deacon
merge bot[tip:locking/core] locking/atomic: Add atomic_cond_read_acquire()
locking/atomic: Add atomic_cond_read_acquire()
Commit-ID: 4df714be4dcf40bfb0d4af0f851a6e1977afa02e Gitweb: https://git.kernel.org/tip/4df714be4dcf40bfb0d4af0f851a6e1977afa02e Author: Will Deacon <[email protected]> AuthorDate: Thu, 12 Oct 2017 13:20:48 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 25 Oct 2017 10:57:24 +0200
locking/atomic: Add atomic_cond_read_acquire()
smp_cond_load_acquire() provides a way to spin on a variable with acquire semantics until some conditional expression involving 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.
--- 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
@@ -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
@@ -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 */
PATCH v3 3/5 kernel/locking: Use atomic_cond_read_acquire when spinning in qrwlock
In reply to Will DeaconThe 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.
--- include/asm-generic/qrwlock.h | 4 ++-- kernel/locking/qrwlock.c | 50 +++++++++++-------------------------------- 2 files changed, 14 insertions(+), 40 deletions(-)
include/asm-generic/qrwlock.h +2 -2
@@ -49,7 +49,7 @@/* * External function declarations */ -extern void queued_read_lock_slowpath (struct qrwlock *lock,u32 cnts); +extern void queued_read_lock_slowpath (struct qrwlock *lock);extern void queued_write_lock_slowpath (struct qrwlock *lock);/**
@@ -100,7 +100,7 @@ static inline void queued_read_lock(struct qrwlock *lock)return ;/* The slowpath will decrement the reader count, if necessary. */ -queued_read_lock_slowpath (lock, cnts); +queued_read_lock_slowpath (lock); }/**
kernel/locking/qrwlock.c +12 -38
90 lines not on this page · raw message
Signature · 1 line
2.1.4
tip-bot for Will Deacon
merge bot[tip:locking/core] locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwlock
locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwlock
Commit-ID: b519b56e378ee82caf9b079b04f5db87dedc3251 Gitweb: https://git.kernel.org/tip/b519b56e378ee82caf9b079b04f5db87dedc3251 Author: Will Deacon <[email protected]> AuthorDate: Thu, 12 Oct 2017 13:20:49 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 25 Oct 2017 10:57:24 +0200
locking/qrwlock: Use atomic_cond_read_acquire() when spinning in qrwlock
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.
--- include/asm-generic/qrwlock.h | 4 ++-- kernel/locking/qrwlock.c | 50 +++++++++++-------------------------------- 2 files changed, 14 insertions(+), 40 deletions(-)
include/asm-generic/qrwlock.h +2 -2
@@ -49,7 +49,7 @@/* * External function declarations */ -extern void queued_read_lock_slowpath (struct qrwlock *lock,u32 cnts); +extern void queued_read_lock_slowpath (struct qrwlock *lock);extern void queued_write_lock_slowpath (struct qrwlock *lock);/**
@@ -100,7 +100,7 @@ static inline void queued_read_lock(struct qrwlock *lock)return ;/* The slowpath will decrement the reader count, if necessary. */ -queued_read_lock_slowpath (lock, cnts); +queued_read_lock_slowpath (lock); }/**
kernel/locking/qrwlock.c +12 -38
90 lines not on this page · raw message
PATCH v3 4/5 arm64: locking: Move rwlock implementation over to qrwlocks
In reply to Will DeaconNow 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
@@ -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_IRQRESTORE 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_IRQRESTORE 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
@@ -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
@@ -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
tip-bot for Will Deacon
merge bot[tip:locking/core] locking/qrwlock, arm64: Move rwlock implementation over to qrwlocks
locking/qrwlock, arm64: Move rwlock implementation over to qrwlocks
Commit-ID: 087133ac90763cd339b6b67f2998f87dcc136c52 Gitweb: https://git.kernel.org/tip/087133ac90763cd339b6b67f2998f87dcc136c52 Author: Will Deacon <[email protected]> AuthorDate: Thu, 12 Oct 2017 13:20:50 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 25 Oct 2017 10:57:25 +0200
locking/qrwlock, arm64: Move rwlock implementation over to qrwlocks
Now that the qrwlock can make use of WFE, remove our homebrewed 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
@@ -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_IRQRESTORE 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_IRQRESTORE 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
@@ -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
@@ -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
PATCH v3 5/5 kernel/locking: Prevent slowpath writers getting held up by fastpath
In reply to Will DeaconWhen 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.
--- include/asm-generic/qrwlock.h | 23 +++++------------------ include/asm-generic/qrwlock_types.h | 8 ++++---- kernel/locking/qrwlock.c | 20 +++++--------------- 3 files changed, 14 insertions(+), 37 deletions(-)
include/asm-generic/qrwlock.h +5 -18
@@ -26,24 +26,11 @@/* * Writer states & reader shift and bias. -* -* | +0 | +1 | +2 | +3 | -* ----+----+----+----+----+ -* LE | 78 | 56 | 34 | 12 | 0x12345678 -* ----+----+----+----+----+ -* | wr | rd | -* +----+----+----+----+ -* -* ----+----+----+----+----+ -* BE | 12 | 34 | 56 | 78 | 0x12345678 -* ----+----+----+----+----+ -* | 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 +121,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
@@ -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
@@ -39,8 +39,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock)* 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);
@@ -56,7 +55,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock)* 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
@@ -79,19 +78,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
tip-bot for Will Deacon
merge bot[tip:locking/core] locking/qrwlock: Prevent slowpath writers getting held up by fastpath
locking/qrwlock: Prevent slowpath writers getting held up by fastpath
Commit-ID: d133166146333e1f13fc81c0e6c43c8d99290a8a Gitweb: https://git.kernel.org/tip/d133166146333e1f13fc81c0e6c43c8d99290a8a Author: Will Deacon <[email protected]> AuthorDate: Thu, 12 Oct 2017 13:20:51 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Wed, 25 Oct 2017 10:57:25 +0200
locking/qrwlock: Prevent slowpath writers getting held up by fastpath
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.
--- include/asm-generic/qrwlock.h | 23 +++++------------------ include/asm-generic/qrwlock_types.h | 8 ++++---- kernel/locking/qrwlock.c | 20 +++++--------------- 3 files changed, 14 insertions(+), 37 deletions(-)
include/asm-generic/qrwlock.h +5 -18
@@ -26,24 +26,11 @@/* * Writer states & reader shift and bias. -* -* | +0 | +1 | +2 | +3 | -* ----+----+----+----+----+ -* LE | 78 | 56 | 34 | 12 | 0x12345678 -* ----+----+----+----+----+ -* | wr | rd | -* +----+----+----+----+ -* -* ----+----+----+----+----+ -* BE | 12 | 34 | 56 | 78 | 0x12345678 -* ----+----+----+----+----+ -* | 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 +121,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
@@ -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
@@ -39,8 +39,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock)* 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);
@@ -56,7 +55,7 @@ void queued_read_lock_slowpath(struct qrwlock *lock)* 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
@@ -79,19 +78,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,
Quoted 26 lines · Will Deacon
Hello,
This is version three of the patches previously posted here:
v1: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html
v2: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534981.htmlChanges since v2 include:
* Drop unused cnt argument
* Fix typo in UNLOCKKconfiginlining options
* Added Tested-by tagsThanks to all of those who provided review and testing feedback!
Will
--->8
Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct__qrwlocklocking/atomic: Addatomic_cond_read_acquirekernel/locking: Useatomic_cond_read_acquirewhen 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 | 37 ++----- include/asm-generic/qrwlock_types.h | 15 ++- include/linux/atomic.h | 4 + kernel/locking/qrwlock.c | 86 +++-------------- 9 files changed, 61 insertions(+), 272 deletions(-)
Will, I see the same performance improvements that I was getting in v2 of the patch. I will continue to run these patches on multiple systems over the next few weeks, months for stability/functionality testing as well.
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.
Hi all,
Quoted 5 lines · Will Deacon
This is version three of the patches previously posted here:
v1: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html
v2: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534981.html
Quoted 7 lines
Changes since v2 include:
* Drop unused cnt argument
* Fix typo in UNLOCKKconfiginlining options
* Added Tested-by tagsThanks to all of those who provided review and testing feedback!
I've not had any more feedback on this and the testing results are very encouraging so I'd like to merge it for 4.15. However, it might make more sense for the whole thing to go via -tip instead.
Ingo, Peter: what do you prefer?
Will
Quoted 21 lines
Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct__qrwlocklocking/atomic: Addatomic_cond_read_acquirekernel/locking: Useatomic_cond_read_acquirewhen spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpatharch/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 | 37 ++----- include/asm-generic/qrwlock_types.h | 15 ++- include/linux/atomic.h | 4 + kernel/locking/qrwlock.c | 86 +++-------------- 9 files changed, 61 insertions(+), 272 deletions(-)Signature · 1 line
2.1.4
Ingo, Peter,
Would you be willing to merge this via -tip, please? I'm happy to rebase/repost as required, but the code is in good shape now.
Will
Quoted 43 lines · Will Deacon
Quoted 5 lines · Will Deacon
This is version three of the patches previously posted here:
v1: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534666.html
v2: http://lists.infradead.org/pipermail/linux-arm-kernel/2017-October/534981.htmlQuoted 7 lines
Changes since v2 include:
* Drop unused cnt argument
* Fix typo in UNLOCKKconfiginlining options
* Added Tested-by tagsThanks to all of those who provided review and testing feedback!
I've not had any more feedback on this and the testing results are very encouraging so I'd like to merge it for 4.15. However, it might make more sense for the whole thing to go via -tip instead.
Ingo, Peter: what do you prefer?
Will
Quoted 21 lines
Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct__qrwlocklocking/atomic: Addatomic_cond_read_acquirekernel/locking: Useatomic_cond_read_acquirewhen spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpatharch/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 | 37 ++----- include/asm-generic/qrwlock_types.h | 15 ++- include/linux/atomic.h | 4 + kernel/locking/qrwlock.c | 86 +++-------------- 9 files changed, 61 insertions(+), 272 deletions(-)Signature · 1 line
2.1.4
Quoted 4 lines · Will Deacon
Ingo, Peter,
Would you be willing to merge this via -tip, please? I'm happy to rebase/repost as required, but the code is in good shape now.
Sure, will do it tomorrow!
Thanks,
Ingo
Peter Zijlstra
maintainerQuoted 9 lines · Ingo Molnar
Quoted 4 lines · Will Deacon
Ingo, Peter,
Would you be willing to merge this via -tip, please? I'm happy to rebase/repost as required, but the code is in good shape now.
Sure, will do it tomorrow!
Yeah, ACK on this.
Hi, all.
Quoted 4 lines · Will Deacon
I've not had any more feedback on this and the testing results are very encouraging so I'd like to merge it for 4.15. However, it might make more sense for the whole thing to go via -tip instead.
Quoted 24 lines
Ingo, Peter: what do you prefer?
Will
Quoted 20 lines
Will Deacon (5):
kernel/locking: Use struct qrwlock instead of struct__qrwlocklocking/atomic: Addatomic_cond_read_acquirekernel/locking: Useatomic_cond_read_acquirewhen spinning in qrwlock
arm64: locking: Move rwlock implementation over to qrwlocks kernel/locking: Prevent slowpath writers getting held up by fastpatharch/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 | 37 ++----- include/asm-generic/qrwlock_types.h | 15 ++- include/linux/atomic.h | 4 + kernel/locking/qrwlock.c | 86 +++-------------- 9 files changed, 61 insertions(+), 272 deletions(-)Signature · 1 line
2.1.4
I am very interested in this change.
Can you share the testing result for me?
Or Test methods, especially test suite and so on.
I would like to further test the performance.
Thanks.
Cheng Jian