locking/core patches
Subsystems (3)
Peter Zijlstra
maintainercover locking/core patches
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99
The second set is the qrwlock, although mostly rewritten by me. I didn't do much with it other than boot and build a kernel. But I like them because of the much better worst case preformance.
Peter Zijlstra
maintainerPATCH 1/8 locking: Move mcs_spinlock.h into kernel/locking/
The mcs_spinlock code is not meant (or suitable) as a generic locking primitive, therefore take it away from the normal includes and place it in kernel/locking/.
This way the locking primitives implemented there can use it as part of their implementation but we do not risk it getting used inapropriately.
--- include/linux/mcs_spinlock.h | 114 ------------------------------------------ kernel/locking/mcs_spinlock.h | 114 ++++++++++++++++++++++++++++++++++++++++++ kernel/locking/mutex.c | 2 3 files changed, 115 insertions(+), 115 deletions(-)
include/linux/mcs_spinlock.h deleted +0 -114
@@ -1,114 +0,0 @@ -/* -* MCS lock defines -* -* This file contains the main data structure and API definitions of MCS lock. -* -* The MCS lock (proposed by Mellor-Crummey and Scott) is a simple spin-lock -* with the desirable properties of being fair, and with each cpu trying -* to acquire the lock spinning on a local variable. -* It avoids expensive cache bouncings that common test-and-set spin-lock -* implementations incur. -*/ -#ifndef __LINUX_MCS_SPINLOCK_H -#define __LINUX_MCS_SPINLOCK_H - -#include <asm/mcs_spinlock.h> - -struct mcs_spinlock { -struct mcs_spinlock *next; -int locked;/* 1 if lock acquired */ -}; - -#ifndef arch_mcs_spin_lock_contended -/* -* Using smp_load_acquire() provides a memory barrier that ensures -* subsequent operations happen after the lock is acquired. -*/ -#define arch_mcs_spin_lock_contended (l) \ -do { \ - while (!(smp_load_acquire(l))) \ - arch_mutex_cpu_relax(); \ -} while (0) -#endif - -#ifndef arch_mcs_spin_unlock_contended -/* -* smp_store_release() provides a memory barrier to ensure all -* operations in the critical section has been completed before -* unlocking. -*/ -#define arch_mcs_spin_unlock_contended (l) \ - smp_store_release((l), 1) -#endif - -/* -* Note: the smp_load_acquire/smp_store_release pair is not -* sufficient to form a full memory barrier across -* cpus for many architectures (except x86) for mcs_unlock and mcs_lock. -* For applications that need a full barrier across multiple cpus -* with mcs_unlock and mcs_lock pair, smp_mb__after_unlock_lock() should be -* used after mcs_lock. -*/ - -/* -* In order to acquire the lock, the caller should declare a local node and -* pass a reference of the node to this function in addition to the lock. -* If the lock has already been acquired, then this will proceed to spin -* on this node->locked until the previous lock holder sets the node->locked -* in mcs_spin_unlock(). -* -* We don't inline mcs_spin_lock() so that perf can correctly account for the -* time spent in this lock function. -*/ -static inline -void mcs_spin_lock (struct mcs_spinlock **lock,struct mcs_spinlock *node) -{ -struct mcs_spinlock *prev; - -/* Init node */ - node->locked =0 ; - node->next =NULL ; - - prev =xchg (lock, node); -if (likely (prev ==NULL )) { -/* -* Lock acquired, don't need to set node->locked to 1. Threads -* only spin on its own node->locked value for lock acquisition. -* However, since this thread can immediately acquire the lock -* and does not proceed to spin on its own node->locked, this -* value won't be used. If a debug mode is needed to -* audit lock status, then set node->locked value here. -*/ -return ; - } -ACCESS_ONCE (prev->next) = node; - -/* Wait until the lock holder passes the lock down. */ -arch_mcs_spin_lock_contended (&node->locked); -} - -/* -* Releases the lock. The caller should pass in the corresponding node that -* was used to acquire the lock. -*/ -static inline -void mcs_spin_unlock (struct mcs_spinlock **lock,struct mcs_spinlock *node) -{ -struct mcs_spinlock *next =ACCESS_ONCE (node->next); - -if (likely (!next)) { -/* -* Release the lock by setting it to NULL -*/ -if (likely (cmpxchg (lock, node,NULL ) == node)) -return ; -/* Wait until the next pointer is set */ -while (!(next =ACCESS_ONCE (node->next))) -arch_mutex_cpu_relax (); - } - -/* Pass lock to next waiter. */ -arch_mcs_spin_unlock_contended (&next->locked); -} - -#endif /* __LINUX_MCS_SPINLOCK_H */
kernel/locking/mcs_spinlock.h new file +114 -0
114 lines not on this page · raw message
kernel/locking/mutex.c +1 -1
@@ -25,7 +25,7 @@#include <linux/spinlock.h> #include <linux/interrupt.h> #include <linux/debug_locks.h> -#include <linux/mcs_spinlock.h> +#include "mcs_spinlock.h" /* * In the DEBUG case we are using the "NULL fastpath" for mutexes,
Peter Zijlstra
maintainerPATCH 2/8 mutex: In mutex_can_spin_on_owner(), return false if task need_resched()
In reply to Peter ZijlstraThe mutex_can_spin_on_owner() function should also return false if the task needs to be rescheduled to avoid entering the MCS queue when it needs to reschedule.
--- kernel/locking/mutex.c | 3 +++ 1 file changed, 3 insertions(+)
kernel/locking/mutex.c +3 -0
@@ -166,6 +166,9 @@ static inline int mutex_can_spin_on_ownestruct task_struct *owner;int retval =1 ; +if (need_resched ()) +return 0 ; +rcu_read_lock (); owner =ACCESS_ONCE (lock->owner);if (owner)
Peter Zijlstra
maintainerRe: [PATCH 2/8] mutex: In mutex_can_spin_on_owner(), return false if task need_resched()
On Mon, Feb 10, 2014 at 08:58:22PM +0100, Peter Zijlstra wrote:
Bah, I forgot Quilt eats the From: headers and I forgot to re-add them. They're still present in the queue, just lost in mailing :/
Quoted 38 lines
The
mutex_can_spin_on_owner()function should also return false if the task needs to be rescheduled to avoid entering the MCS queue when it needs to reschedule.Signed-off-by Jason Low <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/locking/mutex.c | 3 +++ 1 file changed, 3 insertions(+)kernel/locking/mutex.c +3
-0@@ -166,6 +166,9 @@ static inline int mutex_can_spin_on_ownestruct task_struct *owner;int retval =1 ; +if (need_resched ()) +return 0 ; +rcu_read_lock (); owner =ACCESS_ONCE (lock->owner);if (owner)
Peter Zijlstra
maintainerPATCH 3/8 mutex: Modify the way optimistic spinners are queued
In reply to Peter ZijlstraThe mutex->spin_mlock was introduced in order to ensure that only 1 thread spins for lock acquisition at a time to reduce cache line contention. When lock->owner is NULL and the lock->count is still not 1, the spinner(s) will continually release and obtain the lock->spin_mlock. This can generate quite a bit of overhead/contention, and also might just delay the spinner from getting the lock.
This patch modifies the way optimistic spinners are queued by queuing before entering the optimistic spinning loop as oppose to acquiring before every call to mutex_spin_on_owner(). So in situations where the spinner requires a few extra spins before obtaining the lock, then there will only be 1 spinner trying to get the lock and it will avoid the overhead from unnecessarily unlocking and locking the spin_mlock.
--- kernel/locking/mutex.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
kernel/locking/mutex.c +7 -10
@@ -403,9 +403,9 @@ __mutex_lock_common(struct mutex *lock,if (!mutex_can_spin_on_owner (lock)) goto slowpath; +mcs_spin_lock (&lock->mcs_lock);for (;;) {struct task_struct *owner; -struct mcs_spinlock node;if (use_ww_ctx && ww_ctx->acquired >0 ) {struct ww_mutex *ww;
@@ -420,19 +420,16 @@ __mutex_lock_common(struct mutex *lock,* performed the optimistic spinning cannot be done. */ if (ACCESS_ONCE (ww->ctx)) - goto slowpath; +break ; }/* * If there's an owner, wait for it to either * release the lock or go to sleep. */ -mcs_spin_lock (&lock->mcs_lock, &node); owner =ACCESS_ONCE (lock->owner); -if (owner && !mutex_spin_on_owner (lock, owner)) { -mcs_spin_unlock (&lock->mcs_lock, &node); - goto slowpath; - } +if (owner && !mutex_spin_on_owner (lock, owner)) +break ;if ((atomic_read (&lock->count) ==1 ) && (atomic_cmpxchg (&lock->count,1 ,0 ) ==1 )) {
@@ -445,11 +442,10 @@ __mutex_lock_common(struct mutex *lock, }mutex_set_owner (lock); -mcs_spin_unlock (&lock->mcs_lock, &node); +mcs_spin_unlock (&lock->mcs_lock);preempt_enable ();return 0 ; } -mcs_spin_unlock (&lock->mcs_lock, &node);/* * When there's no owner, we might have preempted between the
@@ -458,7 +454,7 @@ __mutex_lock_common(struct mutex *lock,* the owner complete. */ if (!owner && (need_resched () ||rt_task (task))) - goto slowpath; +break ;/* * The cpu_relax() call is a compiler barrier which forces
@@ -468,6 +464,7 @@ __mutex_lock_common(struct mutex *lock,*/ arch_mutex_cpu_relax (); } +mcs_spin_unlock (&lock->mcs_lock); slowpath:#endif spin_lock_mutex (&lock->wait_lock, flags);
Re: [PATCH 3/8] mutex: Modify the way optimistic spinners are queued
Quoted 23 lines · Peter Zijlstra
Signed-off-by Jason Low <[email protected]>Signed-off-by Peter Zijlstra <[email protected]>--- kernel/locking/mutex.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
kernel/locking/mutex.c __mutex_lock_common(struct mutex *lock, · line 406
Quoted 4 lines
kernel/locking/mutex.c +1
-0@@ -403,9 +403,9 @@ __mutex_lock_common(struct mutex *lock,if (!mutex_can_spin_on_owner (lock)) goto slowpath; +mcs_spin_lock (&lock->mcs_lock);
Where did the mcs node go? :)
Peter Zijlstra
maintainerRe: [PATCH 3/8] mutex: Modify the way optimistic spinners are queued
Quoted 3 lines · Jason Low
kernel/locking/mutex.c __mutex_lock_common(struct mutex *lock, · line 406
Quoted 1 line
kernel/locking/mutex.c +1
-0+mcs_spin_lock (&lock->mcs_lock);Where did the mcs node go? :)
Bugger, that's what I get for not compiling each patch in the series.. :-/
Peter Zijlstra
maintainerPATCH 4/8 mutex: Unlock the mutex without the wait_lock
In reply to Peter ZijlstraWhen running workloads that have high contention in mutexes on an 8 socket machine, mutex spinners would often spin for a long time with no lock owner.
The main reason why this is occuring is in __mutex_unlock_common_slowpath(), if __mutex_slowpath_needs_to_unlock(), then the owner needs to acquire the mutex->wait_lock before releasing the mutex (setting lock->count to 1). When the wait_lock is contended, this delays the mutex from being released. We should be able to release the mutex without holding the wait_lock.
--- kernel/locking/mutex.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/locking/mutex.c +4 -4
@@ -673,10 +673,6 @@ __mutex_unlock_common_slowpath(atomic_t struct mutex *lock = container_of(lock_count, struct mutex, count);unsigned long flags; -spin_lock_mutex (&lock->wait_lock, flags); -mutex_release (&lock->dep_map, nested, _RET_IP_); -debug_mutex_unlock (lock); -/* * some architectures leave the lock unlocked in the fastpath failure * case, others need to leave it locked. In the later case we have to
@@ -685,6 +681,10 @@ __mutex_unlock_common_slowpath(atomic_tif (__mutex_slowpath_needs_to_unlock ())atomic_set (&lock->count,1 ); +spin_lock_mutex (&lock->wait_lock, flags); +mutex_release (&lock->dep_map, nested, _RET_IP_); +debug_mutex_unlock (lock); +if (!list_empty (&lock->wait_list)) {/* get the first entry from the wait-list: */ struct mutex_waiter *waiter =
Peter Zijlstra
maintainerPATCH 5/8 locking, mutex: Cancelable MCS lock for adaptive spinning
In reply to Peter ZijlstraSince we want a task waiting for a mutex_lock() to go to sleep and reschedule on need_resched() we must be able to abort the mcs_spin_lock() around the adaptive spin.
Therefore implement a cancelable mcs lock.
--- include/linux/mutex.h | 4 - kernel/locking/Makefile | 2 kernel/locking/mcs_spinlock.c | 167 ++++++++++++++++++++++++++++++++++++++++++ kernel/locking/mcs_spinlock.h | 15 +++ kernel/locking/mutex.c | 10 +- 5 files changed, 191 insertions(+), 7 deletions(-)
include/linux/mutex.h +2 -2
@@ -46,7 +46,7 @@* - detects multi-task circular deadlocks and prints out all affected * locks and tasks (and only those tasks) */ -struct mcs_spinlock ; +struct optimistic_spin_queue ;struct mutex {/* 1: unlocked, 0: locked, negative: locked, possible waiters */ atomic_t count;
@@ -56,7 +56,7 @@ struct mutex {struct task_struct *owner;#endif #ifdef CONFIG_MUTEX_SPIN_ON_OWNER -struct mcs_spinlock *mcs_lock;/* Spinner MCS lock */ +struct optimistic_spin_queue *osq;/* Spinner MCS lock */ #endif #ifdef CONFIG_DEBUG_MUTEXES const char *name;
kernel/locking/Makefile +1 -1
@@ -1,5 +1,5 @@ -obj-y += mutex.o semaphore.o rwsem.o lglock.o +obj-y += mutex.o semaphore.o rwsem.o lglock.o mcs_spinlock.o ifdef CONFIG_FUNCTION_TRACER CFLAGS_REMOVE_lockdep.o = -pg
kernel/locking/mcs_spinlock.c new file +167 -0
167 lines not on this page · raw message
kernel/locking/mcs_spinlock.h +15 -0
@@ -111,4 +111,19 @@ void mcs_spin_unlock(struct mcs_spinlock arch_mcs_spin_unlock_contended(&next->locked); } +/* +* Cancellable version of the MCS lock above. +* +* Intended for adaptive spinning of sleeping locks: +* mutex_lock()/rwsem_down_{read,write}() etc. +*/ + +struct optimistic_spin_queue { +struct optimistic_spin_queue *next, *prev; +int locked;/* 1 if lock acquired */ +}; + +extern bool osq_lock (struct optimistic_spin_queue **lock); +extern void osq_unlock (struct optimistic_spin_queue **lock); +#endif /* __LINUX_MCS_SPINLOCK_H */
kernel/locking/mutex.c +6 -4
@@ -53,7 +53,7 @@ __mutex_init(struct mutex *lock, const cINIT_LIST_HEAD (&lock->wait_list);mutex_clear_owner (lock);#ifdef CONFIG_MUTEX_SPIN_ON_OWNER - lock->mcs_lock =NULL ; + lock->osq =NULL ;#endif debug_mutex_init (lock, name, key);
@@ -403,7 +403,9 @@ __mutex_lock_common(struct mutex *lock,if (!mutex_can_spin_on_owner (lock)) goto slowpath; -mcs_spin_lock (&lock->mcs_lock); +if (!osq_lock (&lock->osq)) + goto slowpath; +for (;;) {struct task_struct *owner;
@@ -442,7 +444,7 @@ __mutex_lock_common(struct mutex *lock, }mutex_set_owner (lock); -mcs_spin_unlock (&lock->mcs_lock); +osq_unlock (&lock->osq);preempt_enable ();return 0 ; }
@@ -464,7 +466,7 @@ __mutex_lock_common(struct mutex *lock,*/ arch_mutex_cpu_relax (); } -mcs_spin_unlock (&lock->mcs_lock); +osq_unlock (&lock->osq); slowpath:#endif spin_lock_mutex (&lock->wait_lock, flags);
Re: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
kernel/locking/mcs_spinlock.c line 159
Quoted 10 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +10
-0+void osq_unlock (struct optimistic_spin_queue **lock) +{ +struct optimistic_spin_queue *node =this_cpu_ptr (&osq_node); +struct optimistic_spin_queue *next; + +/* +* Fast path for the uncontended case. +*/ +if (likely (cmpxchg (lock, node,NULL ) == node)) +return ;
Can we can also add the following code here as I'm noticing next != NULL is the much more likely scenario on my box:
next = xchg(&node->next, NULL);
if (next) {
ACCESS_ONCE(next->locked) = 1;
return;Quoted 4 lines
kernel/locking/mcs_spinlock.c new file +4
-0+ next =osq_wait_next (lock, node,NULL ); +if (next) +ACCESS_ONCE (next->locked) =1 ; +}
Peter Zijlstra
maintainerRe: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 15 lines · Jason Low
kernel/locking/mcs_spinlock.c line 159
Quoted 10 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +10
-0+void osq_unlock (struct optimistic_spin_queue **lock) +{ +struct optimistic_spin_queue *node =this_cpu_ptr (&osq_node); +struct optimistic_spin_queue *next; + +/* +* Fast path for the uncontended case. +*/ +if (likely (cmpxchg (lock, node,NULL ) == node)) +return ;Can we can also add the following code here as I'm noticing next != NULL is the much more likely scenario on my box:
Quoted 4 lines
next = xchg(&node->next, NULL);
if (next) {
ACCESS_ONCE(next->locked) = 1;
return;Is adding that really much faster than the relatively straight path oqs_wait_next() would walk to bit the same exit?
The only reason I pulled out the above cmpxchg() is because its the uncontended fast path, which seems like a special enough case.
Quoted 5 lines
Quoted 4 lines
kernel/locking/mcs_spinlock.c new file +4
-0+ next =osq_wait_next (lock, node,NULL ); +if (next) +ACCESS_ONCE (next->locked) =1 ; +}
Re: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 21 lines · Peter Zijlstra
Quoted 15 lines · Jason Low
kernel/locking/mcs_spinlock.c line 159
Quoted 10 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +10
-0+void osq_unlock (struct optimistic_spin_queue **lock) +{ +struct optimistic_spin_queue *node =this_cpu_ptr (&osq_node); +struct optimistic_spin_queue *next; + +/* +* Fast path for the uncontended case. +*/ +if (likely (cmpxchg (lock, node,NULL ) == node)) +return ;Can we can also add the following code here as I'm noticing next != NULL is the much more likely scenario on my box:
Quoted 4 lines
next = xchg(&node->next, NULL); if (next) { ACCESS_ONCE(next->locked) = 1; return;
Quoted 5 lines
Is adding that really much faster than the relatively straight path
oqs_wait_next()would walk to bit the same exit?The only reason I pulled out the above
cmpxchg()is because its the uncontended fast path, which seems like a special enough case.
So it would avoid 2 extra checks (*lock == node) and (node->next) in the oqs_wait_next() path, which aren't necessary when node->next != NULL.
And I think node->next != NULL can be considered a special enough case after the cmpxchg() fails because in the contended case, we're expecting the node->next to be pointing at something. The only times node->next is NULL after cmpxchg() fails are during a very small race window with the osq_lock(), and when the next node is unqueuing due to need_resched, which is also a very small window.
Peter Zijlstra
maintainerRe: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 10 lines · Jason Low
Quoted 5 lines · Peter Zijlstra
Is adding that really much faster than the relatively straight path
oqs_wait_next()would walk to bit the same exit?The only reason I pulled out the above
cmpxchg()is because its the uncontended fast path, which seems like a special enough case.So it would avoid 2 extra checks (*lock == node) and (
node->next) in theoqs_wait_next()path, which aren't necessary whennode->next!= NULL.
Quoted 6 lines
And I think
node->next!= NULL can be considered a special enough case after thecmpxchg()fails because in the contended case, we're expecting thenode->nextto be pointing at something. The only timesnode->nextis NULL aftercmpxchg()fails are during a very small race window with theosq_lock(), and when the next node is unqueuing due toneed_resched, which is also a very small window.
True all; now if only we had a useful benchmark so we could test if it makes a difference or not :-)
Re: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 18 lines · Peter Zijlstra
Quoted 10 lines · Jason Low
Quoted 5 lines · Peter Zijlstra
Is adding that really much faster than the relatively straight path
oqs_wait_next()would walk to bit the same exit?The only reason I pulled out the above
cmpxchg()is because its the uncontended fast path, which seems like a special enough case.So it would avoid 2 extra checks (*lock == node) and (
node->next) in theoqs_wait_next()path, which aren't necessary whennode->next!= NULL.Quoted 6 lines
And I think
node->next!= NULL can be considered a special enough case after thecmpxchg()fails because in the contended case, we're expecting thenode->nextto be pointing at something. The only timesnode->nextis NULL aftercmpxchg()fails are during a very small race window with theosq_lock(), and when the next node is unqueuing due toneed_resched, which is also a very small window.
Quoted 2 lines
True all; now if only we had a useful benchmark so we could test if it makes a difference or not :-)
Having useful 'perf bench lock' sub-test(s) that mimic the AIM7 workload (and other workloads that excercise locking) would address that concern to a large degree.
Thanks,
Ingo
Re: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
In reply to Peter ZijlstraQuoted 17 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +17
-0+unqueue: +/* +* Step - A -- stabilize @prev +* +* Undo our @prev->next assignment; this will make @prev's +* unlock()/unqueue() wait for a next pointer since @lock points to us +* (or later). +*/ + +for (;;) { +if (prev->next == node && +cmpxchg (&prev->next, node,NULL ) == node) +break ; + +/* +* We can only fail the cmpxchg() racing against an unlock(), +* in which case we should observe @node->locked becomming
kernel/locking/mcs_spinlock.c line 122
Quoted 10 lines
kernel/locking/mcs_spinlock.c new file +10
-0+* true. +*/ +if (smp_load_acquire (&node->locked)) +return true; + +/* +* Or we race against a concurrent unqueue()'s step-B, in which +* case its step-C will write us a new @node->prev pointer. +*/ + prev =ACCESS_ONCE (node->prev);
Should we also add an arch_mutex_cpu_relax() to this loop?
Peter Zijlstra
maintainerRe: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 15 lines · Jason Low
Quoted 13 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +13
-0+unqueue: +/* +* Step - A -- stabilize @prev +* +* Undo our @prev->next assignment; this will make @prev's +* unlock()/unqueue() wait for a next pointer since @lock points to us +* (or later). +*/ + +for (;;) { +if (prev->next == node && +cmpxchg (&prev->next, node,NULL ) == node) +break ;
Quoted 8 lines
kernel/locking/mcs_spinlock.c line 116
Quoted 8 lines
kernel/locking/mcs_spinlock.c new file +8
-0+ +/* +* We can only fail the cmpxchg() racing against an unlock(), +* in which case we should observe @node->locked becomming +* true. +*/ +if (smp_load_acquire (&node->locked)) +return true;
I've stuck on in right about here. So that we don't unduly delay the cmpxchg() after the load of prev.
Quoted 10 lines
kernel/locking/mcs_spinlock.c line 122
Quoted 6 lines
kernel/locking/mcs_spinlock.c new file +6
-0+ +/* +* Or we race against a concurrent unqueue()'s step-B, in which +* case its step-C will write us a new @node->prev pointer. +*/ + prev =ACCESS_ONCE (node->prev);Should we also add an
arch_mutex_cpu_relax()to this loop?
Jason Low
Reviewed-byRe: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning
Quoted 17 lines · Peter Zijlstra
Quoted 13 lines · Jason Low
kernel/locking/mcs_spinlock.c line 116
Quoted 12 lines · Peter Zijlstra
kernel/locking/mcs_spinlock.c new file +12
-0+for (;;) { +if (prev->next == node && +cmpxchg (&prev->next, node,NULL ) == node) +break ; + +/* +* We can only fail the cmpxchg() racing against an unlock(), +* in which case we should observe @node->locked becomming +* true. +*/ +if (smp_load_acquire (&node->locked)) +return true;I've stuck on in right about here. So that we don't unduly delay the
cmpxchg()after the load of prev.
Ok.
Peter Zijlstra
maintainerPATCH 6/8 mutex: Extra reschedule point
In reply to Peter ZijlstraAdd in an extra reschedule in an attempt to avoid getting reschedule the moment we've acquired the lock.
--- kernel/locking/mutex.c | 7 +++++++ 1 file changed, 7 insertions(+)
kernel/locking/mutex.c +7 -0
@@ -468,6 +468,13 @@ __mutex_lock_common(struct mutex *lock, }osq_unlock (&lock->osq); slowpath: +/* +* If we fell out of the spin path because of need_resched(), +* reschedule now, before we try-lock the mutex. This avoids getting +* scheduled out right after we obtained the mutex. +*/ +if (unlikely (need_resched ())) +schedule_preempt_disabled ();#endif spin_lock_mutex (&lock->wait_lock, flags);
Re: [PATCH 6/8] mutex: Extra reschedule point
Quoted 8 lines · On Mon, 10 Feb 2014 20:58:26 +0100 Peter Zijlstra <[email protected]> wrote:
Add in an extra reschedule in an attempt to avoid getting reschedule the moment we've acquired the lock.
...
kernel/locking/mutex.c __mutex_lock_common(struct mutex *lock, · line 477
Quoted 10 lines
kernel/locking/mutex.c +7
-0@@ -468,6 +468,13 @@ __mutex_lock_common(struct mutex *lock, }osq_unlock (&lock->osq); slowpath: +/* +* If we fell out of the spin path because of need_resched(), +* reschedule now, before we try-lock the mutex. This avoids getting +* scheduled out right after we obtained the mutex. +*/ +if (unlikely (need_resched ())) +schedule_preempt_disabled ();
need_resched() already does unlikely().
Peter Zijlstra
maintainerPATCH 7/8 locking: Introduce qrwlock
In reply to Peter ZijlstraThis rwlock uses the arch_spin_lock_t as a waitqueue, and assuming the arch_spin_lock_t is a fair lock (ticket,mcs etc..) the resulting rwlock is a fair lock.
It fits in the same 8 bytes as the regular rwlock_t by folding the reader and writer count into a single integer, using the remaining 4 bytes for the arch_spinlock_t.
Architectures that can single-copy adress bytes can optimize queue_write_unlock() with a 0 write to the LSB (the write count).
--- include/asm-generic/qrwlock.h | 174 ++++++++++++++++++++++++++++++++++++ include/asm-generic/qrwlock_types.h | 16 +++ kernel/Kconfig.locks | 7 + kernel/locking/Makefile | 1 kernel/locking/qrwlock.c | 133 +++++++++++++++++++++++++++ 5 files changed, 331 insertions(+)
include/asm-generic/qrwlock.h new file +174 -0
@@ -0,0 +1,174 @@ +/* +* Queue read/write lock +* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation; either version 2 of the License, or +* (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* (C) Copyright 2013-2014 Hewlett-Packard Development Company, L.P. +* +* Authors: Waiman Long <[email protected]> +*/ +#ifndef __ASM_GENERIC_QRWLOCK_H +#define __ASM_GENERIC_QRWLOCK_H + +#include <linux/types.h> +#include <linux/atomic.h> +#include <asm/barrier.h> +#include <asm/processor.h> + +#include <asm-generic/qrwlock_types.h> + +/* +* Writer states & reader shift and bias +*/ +#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 _QR_BIAS (1U << _QR_SHIFT) + +/* +* External function declarations +*/ +extern void queue_read_lock_slowpath (struct qrwlock *lock); +extern void queue_write_lock_slowpath (struct qrwlock *lock); + +/** +* queue_read_can_lock- would read_trylock() succeed? +* @lock: Pointer to queue rwlock structure +*/ +static inline int queue_read_can_lock (struct qrwlock *lock) +{ +return !(atomic_read (&lock->cnts) & _QW_WMASK); +} + +/** +* queue_write_can_lock- would write_trylock() succeed? +* @lock: Pointer to queue rwlock structure +*/ +static inline int queue_write_can_lock (struct qrwlock *lock) +{ +return !atomic_read (&lock->cnts); +} + +/** +* queue_read_trylock - try to acquire read lock of a queue rwlock +* @lock : Pointer to queue rwlock structure +* Return: 1 if lock acquired, 0 if failed +*/ +static inline int queue_read_trylock (struct qrwlock *lock) +{ +u32 cnts; + + cnts =atomic_read (&lock->cnts); +if (likely (!(cnts & _QW_WMASK))) { + cnts = (u32 )atomic_add_return (_QR_BIAS, &lock->cnts); +if (likely (!(cnts & _QW_WMASK))) +return 1 ; +atomic_sub (_QR_BIAS, &lock->cnts); + } +return 0 ; +} + +/** +* queue_write_trylock - try to acquire write lock of a queue rwlock +* @lock : Pointer to queue rwlock structure +* Return: 1 if lock acquired, 0 if failed +*/ +static inline int queue_write_trylock (struct qrwlock *lock) +{ +u32 cnts; + + cnts =atomic_read (&lock->cnts); +if (unlikely (cnts)) +return 0 ; + +return likely (atomic_cmpxchg (&lock->cnts, + cnts, cnts | _QW_LOCKED) == cnts); +} +/** +* queue_read_lock - acquire read lock of a queue rwlock +* @lock: Pointer to queue rwlock structure +*/ +static inline void queue_read_lock (struct qrwlock *lock) +{ +u32 cnts; + + cnts =atomic_add_return (_QR_BIAS, &lock->cnts); +if (likely (!(cnts & _QW_WMASK))) +return ; + +/* The slowpath will decrement the reader count, if necessary. */ +queue_read_lock_slowpath (lock); +} + +/** +* queue_write_lock - acquire write lock of a queue rwlock +* @lock : Pointer to queue rwlock structure +*/ +static inline void queue_write_lock (struct qrwlock *lock) +{ +/* Optimize for the unfair lock case where the fair flag is 0. */ +if (atomic_cmpxchg (&lock->cnts,0 , _QW_LOCKED) ==0 ) +return ; + +queue_write_lock_slowpath (lock); +} + +/** +* queue_read_unlock - release read lock of a queue rwlock +* @lock : Pointer to queue rwlock structure +*/ +static inline void queue_read_unlock (struct qrwlock *lock) +{ +/* +* Atomically decrement the reader count +*/ +smp_mb__before_atomic_dec (); +atomic_sub (_QR_BIAS, &lock->cnts); +} + +#ifndef queue_write_unlock +/** +* queue_write_unlock - release write lock of a queue rwlock +* @lock : Pointer to queue rwlock structure +*/ +static inline void queue_write_unlock (struct qrwlock *lock) +{ +/* +* If the writer field is atomic, it can be cleared directly. +* Otherwise, an atomic subtraction will be used to clear it. +*/ +smp_mb__before_atomic_dec (); +atomic_sub (_QW_LOCKED, &lock->cnts); +} +#endif + +typedef struct qrwlock arch_rwlock_t ; + +#define __ARCH_RW_LOCK_UNLOCKED { \ + .cnts = ATOMIC_INIT(0), \ + .lock = __ARCH_SPIN_LOCK_UNLOCKED, \ +} + +/* +* Remapping rwlock architecture specific functions to the corresponding +* queue rwlock functions. +*/ +#define arch_read_can_lock (l) queue_read_can_lock(l) +#define arch_write_can_lock (l) queue_write_can_lock(l) +#define arch_read_lock (l) queue_read_lock(l) +#define arch_write_lock (l) queue_write_lock(l) +#define arch_read_trylock (l) queue_read_trylock(l) +#define arch_write_trylock (l) queue_write_trylock(l) +#define arch_read_unlock (l) queue_read_unlock(l) +#define arch_write_unlock (l) queue_write_unlock(l) + +#endif /* __ASM_GENERIC_QRWLOCK_H */
include/asm-generic/qrwlock_types.h new file +16 -0
@@ -0,0 +1,16 @@ +#ifndef __ASM_GENERIC_QRWLOCK_TYPES_H +#define __ASM_GENERIC_QRWLOCK_TYPES_H + +#include <linux/atomic.h> +#include <linux/spinlock_types.h> + +/* +* The queue read/write lock data structure +*/ + +struct qrwlock { +atomic_t cnts; +arch_spinlock_t lock; +}; + +#endif /* __ASM_GENERIC_QRWLOCK_TYPES_H */
kernel/Kconfig.locks +7 -0
@@ -223,3 +223,10 @@ endif config MUTEX_SPIN_ON_OWNER def_bool y depends on SMP && !DEBUG_MUTEXES + +config ARCH_USE_QUEUE_RWLOCK + bool + +config QUEUE_RWLOCK + def_bool y if ARCH_USE_QUEUE_RWLOCK + depends on SMP
kernel/locking/Makefile +1 -0
@@ -23,3 +23,4 @@ obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem-xadd.o obj-$(CONFIG_PERCPU_RWSEM) += percpu-rwsem.o +obj-$(CONFIG_QUEUE_RWLOCK) += qrwlock.o
kernel/locking/qrwlock.c new file +133 -0
133 lines not on this page · raw message
Re: [PATCH 7/8] locking: Introduce qrwlock
Peter,
I had written a test program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock & the other half are remote
The results of the test run are as follows (execution times in ms, smaller is better, qrwlock uses MCS lock for queuing):
R:W ratio = 0:1 (write lock only)
---------------------------------
# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 75/ 0, 76/ 0 44/ 0, 44/ 0 2 924/ 6, 818/ 11 233/ 22, 685/ 1 3 1680/ 67, 1676/ 50 422/ 24, 640/305 4 1727/ 402, 1661/ 620 563/ 85, 694/384 5 2634/ 861, 2746/ 426 787/276, 829/401 6 2969/1196, 2892/ 398 810/307, 968/451 7 3532/1512, 3137/1109 936/387, 1060/512 8 3979/1698, 4190/1526 1134/590, 1120/503
R:W ratio = 1:1
---------------
# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 82/ 0, 81/ 0 65/ 0, 65/ 0 2 844/ 6, 829/ 1 752/ 4, 894/ 2 3 1683/ 65, 1628/ 29 980/ 14, 1046/ 24 4 2661/ 65, 1747/ 609 1356/ 16, 1405/ 13 5 2227/ 868, 2887/ 395 1625/ 32, 1679/ 29 6 2553/ 968, 3924/1319 1935/ 18, 1986/ 65 7 3392/1325, 3674/1430 2302/ 41, 2313/ 83 8 3822/1545, 5163/2103 2654/ 31, 2654/ 67
R:W ratio = 10:1
----------------
# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 86/ 0, 86/ 0 83/ 0, 83/ 0 2 656/ 2, 640/ 3 546/ 2, 635/ 1 3 1154/ 39, 1053/ 64 934/ 27, 968/ 31 4 1810/ 26, 1535/ 399 1357/ 34, 1382/ 52 5 1994/ 495, 2618/ 27 1713/ 52, 1785/ 47 6 2371/ 488, 3099/ 105 2093/ 80, 2131/ 77 7 2846/ 751, 3068/ 689 2495/103, 2527/107 8 3392/1009, 3566/1017 2899/130, 2928/126
For reference, I also made the same measurement for ticket spinlock with essentially no variation in execution time between different threads:
# of spinlock mean threads Local, Remote ------- ------------- 1 70, 70 2 757, 779 3 1892, 1858 4 2818, 2794 5 3829, 3851 6 4957, 5069 7 6209, 6251 8 7524, 7564
In summary,
1) The qrwlock is always faster than the rwlock with the exception of about 8% slowdown with 1:1 read-write lock ratio and 2 contending threads on a remote lock. In the most common case of 1-socket system, qrwlock will not be slower than rwlock.
2) qrwlock has much less variation in execution times (more consistent performance) when compared with rwlock.
3) For rwlock with 2-3 contending threads, remote lock actually performs slightly better than local lock.
4) For qrwlock, local lock performs slightly better than remote lock with less variation in execution time.
As for the use of ticket lock for queuing purpose, the spinlock performance figures above seem to suggest that it will perform worse than MCS lock with even a few contending threads. This is especially a problem with contending threads coming from different nodes.
Below are the performance data with half local and half remote CPUs:
# of threads = 8 R/W ratio rwlock mean/std qrwlock mean/std --------- --------------- ---------------- 0:1 3476/868 1304/484 1:1 3452/975 2984/777 10:1 3215/914 2963/107
The rwlock actually performs slightly better when CPUs have different access times to the lock. The qrwlock, on the other hand, performs slightly worse with much larger variation in execution times.
In the case of ticket spinlock with asymmetric access time (half local CPUs, half remote CPUs), the performance data were:
# of threads spinlock mean
------------ -------------
2 4570
4 9927
6 15197
8 20573Ticket spinlock seems to be 3-5X slower with asymmetric access time. So it may not be such a good idea to replace the MCS lock by a ticket lock in qrwlock. I will take some additional measurement with your patch to see how it perform.
-Longman
Re: [PATCH 7/8] locking: Introduce qrwlock
Quoted 117 lines · Waiman Long
Peter,
I had written a test program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock & the other half are remoteThe results of the test run are as follows (execution times in ms, smaller is better, qrwlock uses MCS lock for queuing):
R:W ratio = 0:1 (write lock only)
---------------------------------# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 75/ 0, 76/ 0 44/ 0, 44/ 0 2 924/ 6, 818/ 11 233/ 22, 685/ 1 3 1680/ 67, 1676/ 50 422/ 24, 640/305 4 1727/ 402, 1661/ 620 563/ 85, 694/384 5 2634/ 861, 2746/ 426 787/276, 829/401 6 2969/1196, 2892/ 398 810/307, 968/451 7 3532/1512, 3137/1109 936/387, 1060/512 8 3979/1698, 4190/1526 1134/590, 1120/503R:W ratio = 1:1
---------------# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 82/ 0, 81/ 0 65/ 0, 65/ 0 2 844/ 6, 829/ 1 752/ 4, 894/ 2 3 1683/ 65, 1628/ 29 980/ 14, 1046/ 24 4 2661/ 65, 1747/ 609 1356/ 16, 1405/ 13 5 2227/ 868, 2887/ 395 1625/ 32, 1679/ 29 6 2553/ 968, 3924/1319 1935/ 18, 1986/ 65 7 3392/1325, 3674/1430 2302/ 41, 2313/ 83 8 3822/1545, 5163/2103 2654/ 31, 2654/ 67R:W ratio = 10:1
----------------# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 86/ 0, 86/ 0 83/ 0, 83/ 0 2 656/ 2, 640/ 3 546/ 2, 635/ 1 3 1154/ 39, 1053/ 64 934/ 27, 968/ 31 4 1810/ 26, 1535/ 399 1357/ 34, 1382/ 52 5 1994/ 495, 2618/ 27 1713/ 52, 1785/ 47 6 2371/ 488, 3099/ 105 2093/ 80, 2131/ 77 7 2846/ 751, 3068/ 689 2495/103, 2527/107 8 3392/1009, 3566/1017 2899/130, 2928/126For reference, I also made the same measurement for ticket spinlock with essentially no variation in execution time between different threads:
# of spinlock mean threads Local, Remote ------- ------------- 1 70, 70 2 757, 779 3 1892, 1858 4 2818, 2794 5 3829, 3851 6 4957, 5069 7 6209, 6251 8 7524, 7564In summary,
1) The qrwlock is always faster than the rwlock with the exception of about 8% slowdown with 1:1 read-write lock ratio and 2 contending threads on a remote lock. In the most common case of 1-socket system, qrwlock will not be slower than rwlock.
2) qrwlock has much less variation in execution times (more consistent performance) when compared with rwlock.
3) For rwlock with 2-3 contending threads, remote lock actually performs slightly better than local lock.
4) For qrwlock, local lock performs slightly better than remote lock with less variation in execution time.
As for the use of ticket lock for queuing purpose, the spinlock performance figures above seem to suggest that it will perform worse than MCS lock with even a few contending threads. This is especially a problem with contending threads coming from different nodes.
Below are the performance data with half local and half remote CPUs:
# of threads = 8 R/W ratio rwlock mean/std qrwlock mean/std --------- --------------- ---------------- 0:1 3476/868 1304/484 1:1 3452/975 2984/777 10:1 3215/914 2963/107The rwlock actually performs slightly better when CPUs have different access times to the lock. The qrwlock, on the other hand, performs slightly worse with much larger variation in execution times.
In the case of ticket spinlock with asymmetric access time (half local CPUs, half remote CPUs), the performance data were:
# of threads spinlock mean ------------ ------------- 2 4570 4 9927 6 15197 8 20573
Quoted 7 lines
Ticket spinlock seems to be 3-5X slower with asymmetric access time. So it may not be such a good idea to replace the MCS lock by a ticket lock in qrwlock. I will take some additional measurement with your patch to see how it perform.
-Longman
Using the same locktest program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock & the other half are remote
Two types of qrwlock are tested:
1) Use MCS lock
2) Use ticket lock
The results of the test run are as follows (execution times in ms, smaller is better):
R:W ratio = 0:1 (write lock only)
---------------------------------
# of ticket lock mean/std MCS lock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 44/ 0, 43/ 0 44/ 0, 44/ 0 2 376/ 21, 504/ 3 231/ 21, 233/ 22 3 969/ 66, 509/ 176 363/ 88, 359/107 4 1689/ 103, 960/ 417 693/263, 502/141 5 2330/ 167, 1575/ 668 769/273, 649/238 6 2802/ 474, 2203/ 884 866/334, 864/329 7 3390/ 499, 2812/1040 1065/461, 1075/316 8 3725/ 613, 3359/1210 1257/552, 1288/493
R:W ratio = 1:1
---------------
# of ticket lock mean/std MCS lock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 66/ 0, 66/ 0 66/ 0, 65/ 0 2 824/ 4, 609/ 13 761/ 2, 774/ 4 3 1440/ 4, 1305/ 57 926/ 19, 989/ 7 4 2080/ 53, 1991/ 58 1371/ 29, 1322/ 33 5 2786/ 71, 2635/ 116 1632/ 82, 1604/ 22 6 3808/ 147, 3584/ 165 1938/102, 1912/ 98 7 4795/ 107, 4593/ 116 2378/ 79, 2279/ 93 8 5498/ 387, 5428/ 370 2614/ 84, 2602/ 63
R:W ratio = 10:1
----------------
# of rwlock mean/std qrwlock mean/std threads Local , Remote Local , Remote ------- --------------------- ---------------------- 1 83/ 0, 84/ 0 83/ 0, 83/ 0 2 577/ 13, 421/ 25 492/ 9, 554/ 1 3 1246/ 16, 1009/ 112 866/ 10, 902/ 49 4 1956/ 29, 1656/ 171 1240/ 33, 1340/ 43 5 2788/ 26, 2480/ 208 1661/ 78, 1685/ 59 6 3723/ 74, 3429/ 207 2068/107, 2064/ 86 7 4629/ 197, 4295/ 303 2484/132, 2464/108 8 5565/ 277, 5406/ 301 2903/161, 2864/135
There are varations in different runs especially for low thread counts. With ticket lock, remote lock access seems to benefit performance especially at low thread counts (2 or 3) with corresponding larger execution time variation. With MCS lock remote lock access generally yield slightly worse performance. Overall speaking, the only case where ticket lock performs better is when with 2 contending threads on a remote lock.
With half local CPUs and half remote CPUs, the performance data were:
R:W ratio = 0:1 (write lock only)
---------------------------------
# of threads ticket lock mean/std MCS lock mean/std ------------ -------------------- ---------------------- 2 518/ 22 294/ 11 4 973/295 604/221 6 1465/580 925/446 8 1721/763 1155/528
R:W ratio = 1:1
---------------
# of threads ticket lock mean/std MCS lock mean/std ------------ -------------------- ---------------------- 2 578/ 2 605/ 11 4 1436/177 1518/182 6 2254/327 2248/206 8 3097/648 2536/838
R:W ratio = 10:1
----------------
# of threads ticket lock mean/std MCS lock mean/std ------------ -------------------- ---------------------- 2 632/ 5 718/ 3 4 1783/153 1733/ 82 6 2815/213 2612/110 8 3911/380 3460/152
Asymmetric access time benefit ticket lock, which performs slightly better than MCS lock at 2 & 4 threads (1:1) and 2 threads (10:1). For MCS lock, asymmetric access time makes the performance slightly worse.
-Longman
Peter Zijlstra
maintainerRe: [PATCH 7/8] locking: Introduce qrwlock
Quoted 10 lines · Waiman Long
Using the same locktest program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock & the other half are remote
I can't find these configurations in the below numbers; esp the first is interesting because most computers out there have no nodes.
Quoted 3 lines
Two types of qrwlock are tested:
1) Use MCS lock
2) Use ticket lock
arch_spinlock_t; you forget that if you change that to an MCS style lock this one goes along for free.
On that; I had a look at your qspinlock and got a massive head-ache so I rewrote it. Aside from being very mess code it also suffered from a few fairness issues in that it is possible (albeit highly unlikely) to steal a lock instead of being properly queued; per your xchg() usage.
The below boots; but I've not done much else with it, so it will probably explode in your face.
--- arch/x86/Kconfig | 1 arch/x86/include/asm/spinlock.h | 2 arch/x86/include/asm/spinlock_types.h | 4 b/arch/x86/include/asm/qspinlock.h | 13 ++ b/include/asm-generic/qspinlock.h | 128 ++++++++++++++++++++++++ b/kernel/locking/qspinlock.c | 178 ++++++++++++++++++++++++++++++++++ kernel/Kconfig.locks | 7 + kernel/locking/Makefile | 1 kernel/locking/mcs_spinlock.h | 1 9 files changed, 335 insertions(+)
arch/x86/Kconfig +1 -0
@@ -17,6 +17,7 @@ config X86_64 depends on 64BIT select X86_DEV_DMA_OPS select ARCH_USE_CMPXCHG_LOCKREF + select ARCH_USE_QUEUE_SPINLOCK ### Arch settings config X86
arch/x86/include/asm/qspinlock.h new file +13 -0
@@ -0,0 +1,13 @@ +#ifndef _ASM_X86_QSPINLOCK_H +#define _ASM_X86_QSPINLOCK_H + +#if !defined(CONFIG_X86_OOSTORE ) && !defined(CONFIG_X86_PPRO_FENCE ) +#define queue_spin_unlock queue_spin_unlock +static __always_inline void queue_spin_unlock(struct qspinlock *lock) +{ +barrier (); +ACCESS_ONCE (*(u8 *)&lock->val) =0 ; +} +#endif + +#endif /* _ASM_X86_QSPINLOCK_H */
arch/x86/include/asm/spinlock.h +2 -0
@@ -43,6 +43,7 @@extern struct static_key paravirt_ticketlocks_enabled; static __always_inline bool static_key_false(struct static_key *key); +#ifndef CONFIG_QUEUE_SPINLOCK #ifdef CONFIG_PARAVIRT_SPINLOCKS static inline void __ticket_enter_slowpath (arch_spinlock_t *lock)
@@ -181,6 +182,7 @@ static __always_inline void arch_spin_lo {arch_spin_lock (lock); } +#endif /* !CONFIG_QUEUE_SPINLOCK */ static inline void arch_spin_unlock_wait (arch_spinlock_t *lock) {
arch/x86/include/asm/spinlock_types.h +4 -0
@@ -11,6 +11,9 @@#define TICKET_SLOWPATH_FLAG ((__ticket_t)0)#endif +#ifdef CONFIG_QUEUE_SPINLOCK +#include <asm-generic/qspinlock.h> +#else #if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))typedef u8 __ticket_t ;typedef u16 __ticketpair_t ;
@@ -33,6 +36,7 @@ typedef struct arch_spinlock { } arch_spinlock_t;#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } +#endif /* CONFIG_QUEUE_SPINLOCK */ #ifdef CONFIG_QUEUE_RWLOCK #include <asm/qrwlock.h>
include/asm-generic/qspinlock.h new file +128 -0
128 lines not on this page · raw message
kernel/Kconfig.locks +7 -0
@@ -224,6 +224,13 @@ config MUTEX_SPIN_ON_OWNER def_bool y depends on SMP && !DEBUG_MUTEXES +config ARCH_USE_QUEUE_SPINLOCK + bool + +config QUEUE_SPINLOCK + def_bool y if ARCH_USE_QUEUE_SPINLOCK + depends on SMP && !PARAVIRT_SPINLOCKS + config ARCH_USE_QUEUE_RWLOCK bool
kernel/locking/Makefile +1 -0
@@ -23,4 +23,5 @@ obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem-xadd.o obj-$(CONFIG_PERCPU_RWSEM) += percpu-rwsem.o +obj-$(CONFIG_QUEUE_SPINLOCK) += qspinlock.o obj-$(CONFIG_QUEUE_RWLOCK) += qrwlock.o
kernel/locking/mcs_spinlock.h +1 -0
@@ -17,6 +17,7 @@struct mcs_spinlock {struct mcs_spinlock *next;int locked;/* 1 if lock acquired */ +int count;/* see qspinlock.c */ };#ifndef arch_mcs_spin_lock_contended
kernel/locking/qspinlock.c new file +178 -0
178 lines not on this page · raw message
Peter Zijlstra
maintainerRe: [PATCH 7/8] locking: Introduce qrwlock
Quoted 15 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long
Using the same locktest program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock & the other half are remoteI can't find these configurations in the below numbers; esp the first is interesting because most computers out there have no nodes.
Quoted 6 lines
Quoted 3 lines
Two types of qrwlock are tested:
1) Use MCS lock
2) Use ticket lock
arch_spinlock_t; you forget that if you change that to an MCS style lock this one goes along for free.
Furthermore; comparing the current rwlock to the ticket-rwlock already shows an improvement, so on that aspect its worth it as well.
And there's also the paravirt people to consider; a fair rwlock will make them unhappy; and I'm hoping that their current paravirt ticket stuff is sufficient to deal with the ticket-rwlock without them having to come and wreck things again.
Similarly; qspinlock needs paravirt support.
Re: [PATCH 7/8] locking: Introduce qrwlock
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Quoted 10 lines · Waiman Long
Using the same locktest program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock& the other half are remoteI can't find these configurations in the below numbers; esp the first is interesting because most computers out there have no nodes.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Two types of qrwlock are tested:
1) Use MCS lock
2) Use ticket lock
arch_spinlock_t; you forget that if you change that to an MCS style lock this one goes along for free.Furthermore; comparing the current rwlock to the ticket-rwlock already shows an improvement, so on that aspect its worth it as well.
As I said in my previous email, I am not against your change.
Quoted 4 lines
And there's also the paravirt people to consider; a fair rwlock will make them unhappy; and I'm hoping that their current paravirt ticket stuff is sufficient to deal with the ticket-rwlock without them having to come and wreck things again.
Actually, my original qrwlock patch has an unfair option. With some minor change, it can be made unfair pretty easily. So we can use the paravirt config macro to change that to unfair if it is what the virtualization people want.
Quoted 3 lines
Similarly; qspinlock needs paravirt support.
The current paravirt code has hard-coded the use of ticket spinlock. That is why I have to disable my qspinlock code if paravirt is enabled.
I have thinking about that paravirt support. Since the waiting tasks are queued up. By maintaining some kind of heart beat signal, it is possible to make the waiting task jump the queue if the previous one in the queue doesn't seem to be alive. I will work on that next once I am done with the current qspinlock patch.
-Longman
Re: [PATCH 7/8] locking: Introduce qrwlock
In reply to Peter ZijlstraQuoted 7 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
Using the same locktest program to repetitively take a single rwlock with programmable number of threads and count their execution times. Each thread takes the lock 5M times on a 4-socket 40-core Westmere-EX system. I bound all the threads to different CPUs with the following 3 configurations:
Quoted 6 lines
Quoted 4 lines
1) Both CPUs and lock are in the same node
2) CPUs and lock are in different nodes
3) Half of the CPUs are in same node as the lock& the other half are remoteI can't find these configurations in the below numbers; esp the first is interesting because most computers out there have no nodes.
I have a local and remote number in the measurement data that I sent out. The local ones are when both CPUs and lock are in the same node. The remote is when they are in different nodes.
Quoted 5 lines
Quoted 3 lines
Two types of qrwlock are tested:
1) Use MCS lock
2) Use ticket lock
arch_spinlock_t; you forget that if you change that to an MCS style lock this one goes along for free.
Yes, I am aware of that. I am not saying that it is a bad idea to use arch_spin_t. I will be happy if your version of qrwlock patch get merged. I am just saying that it maybe a better idea to use MCS lock directly especially in case that the spinlock is not converted to use a MCS-style lock. I will be more happy if that happen.
Quoted 8 lines
On that; I had a look at your qspinlock and got a massive head-ache so I rewrote it. Aside from being very mess code it also suffered from a few fairness issues in that it is possible (albeit highly unlikely) to steal a lock instead of being properly queued; per your
xchg()usage.The below boots; but I've not done much else with it, so it will probably explode in your face.
Thank for looking into my qspinlock patch. I will take a look at your changes and incorporate it to make it more fair. I have already rewritten it along the same line your version of the qrwlock patch. I have done some performance testing at low contention level using my microbenchmark. The qspinlock was indeed slower than ticket lock with 2-4 contending tasks. The break-even point is at 5 contending tasks. To fix this performance deficit, I added an optimized x86 specific contention path for 2 contending tasks so that it would perform better than the ticket lock. It will still be somewhat slower for 3-4 contending tasks, but the 2 contending task case is probably the most common.
With that change, I would say that my qspinlock patch should be good enough as a replacement of ticket spinlock for x86. I will send out an updated qspinlock patch in a day or two when I finish my testing.
-Longman
Peter Zijlstra
maintainerPATCH 8/8 x86,locking: Enable qrwlock
In reply to Peter ZijlstraMake x86 use the fair rwlock_t.
Implement the custom queue_write_unlock() for best performance.
--- arch/x86/Kconfig | 1 + arch/x86/include/asm/qrwlock.h | 18 ++++++++++++++++++ arch/x86/include/asm/spinlock.h | 2 ++ arch/x86/include/asm/spinlock_types.h | 4 ++++ 4 files changed, 25 insertions(+)
arch/x86/Kconfig +1 -0
@@ -119,6 +119,7 @@ config X86 select MODULES_USE_ELF_RELA if X86_64 select CLONE_BACKWARDS if X86_32 select ARCH_USE_BUILTIN_BSWAP + select ARCH_USE_QUEUE_RWLOCK select OLD_SIGSUSPEND3 if X86_32 || IA32_EMULATION select OLD_SIGACTION if X86_32 select COMPAT_OLD_SIGACTION if IA32_EMULATION
arch/x86/include/asm/qrwlock.h new file +18 -0
@@ -0,0 +1,18 @@ +#ifndef _ASM_X86_QRWLOCK_H +#define _ASM_X86_QRWLOCK_H + +#include <asm-generic/qrwlock_types.h> + +#if !defined(CONFIG_X86_OOSTORE ) && !defined(CONFIG_X86_PPRO_FENCE ) +#define queue_write_unlock queue_write_unlock +static inline void queue_write_unlock (struct qrwlock *lock) +{ +barrier (); +ACCESS_ONCE (*(u8 *)&lock->cnts) =0 ; +} +#endif + +#include <asm-generic/qrwlock.h> + +#endif /* _ASM_X86_QRWLOCK_H */ +
arch/x86/include/asm/spinlock.h +2 -0
@@ -188,6 +188,7 @@ static inline void arch_spin_unlock_waitcpu_relax (); } +#ifndef CONFIG_QUEUE_RWLOCK /* * Read-write spinlocks, allowing multiple readers * but only one writer.
@@ -270,6 +271,7 @@ static inline void arch_write_unlock(arc asm volatile(LOCK_PREFIX WRITE_LOCK_ADD(%1) "%0" : "+m" (rw->write) : "i" (RW_LOCK_BIAS) : "memory"); } +#endif /* CONFIG_QUEUE_RWLOCK */ #define arch_read_lock_flags (lock, flags) arch_read_lock(lock)#define arch_write_lock_flags (lock, flags) arch_write_lock(lock)
arch/x86/include/asm/spinlock_types.h +4 -0
@@ -34,6 +34,10 @@ typedef struct arch_spinlock {#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } +#ifdef CONFIG_QUEUE_RWLOCK +#include <asm/qrwlock.h> +#else #include <asm/rwlock.h> +#endif #endif /* _ASM_X86_SPINLOCK_TYPES_H */
Quoted 9 lines · On Mon, 10 Feb 2014 20:58:20 +0100 Peter Zijlstra <[email protected]> wrote:
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99
What do these columns represent? I'm guessing the large improvement was in context switches?
Quoted 3 lines
The second set is the qrwlock, although mostly rewritten by me. I didn't do much with it other than boot and build a kernel. But I like them because of the much better worst case preformance.
Peter Zijlstra
maintainerQuoted 9 lines · Andrew Morton
Quoted 7 lines · On Mon, 10 Feb 2014 20:58:20 +0100 Peter Zijlstra <[email protected]> wrote:
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
Jobs/min/ Jobs/sec/ Time: Time: Time: Time: Running child time
Forks Jobs/min child child parent childU childS std_dev JTI :max :min
Quoted 5 lines
Quoted 2 lines
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99What do these columns represent? I'm guessing the large improvement was in context switches?
I pasted the header from reaim above; I'm not entirely sure what the bloody thing does and I hate that it takes hours to get these numbers :/
Bloody stupid benchmark if you ask me.
Quoted 14 lines · On Tue, 11 Feb 2014 08:17:00 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 9 lines · Andrew Morton
Quoted 7 lines · On Mon, 10 Feb 2014 20:58:20 +0100 Peter Zijlstra <[email protected]> wrote:
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
Jobs/min/ Jobs/sec/ Time: Time: Time: Time: Running child time
Forks Jobs/min child child parent childU childSstd_devJTI :max :min
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99What do these columns represent? I'm guessing the large improvement was in context switches?
I pasted the header from reaim above;
hmpf. I wonder what's the difference between Jobs/min, Jobs/min(child) and Jobs/sec(child), which is not Jobs/min(child) / 60.
Quoted 4 lines
I'm not entirely sure what the
bloody thing does and I hate that it takes hours to get these numbers :/Bloody stupid benchmark if you ask me.
heh, yes, it's stupid how long many benchmarks take. Ditch it. A change like this should be testable with a 30-line microbenchmark which runs in 5 seconds tops.
Quoted 27 lines · Andrew Morton
Quoted 14 lines · On Tue, 11 Feb 2014 08:17:00 +0100 Peter Zijlstra <[email protected]> wrote:
Quoted 9 lines · Andrew Morton
Quoted 7 lines · On Mon, 10 Feb 2014 20:58:20 +0100 Peter Zijlstra <[email protected]> wrote:
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
Jobs/min/ Jobs/sec/ Time: Time: Time: Time: Running child time
Forks Jobs/min child child parent childU childSstd_devJTI :max :minQuoted 7 lines
Quoted 5 lines
Quoted 2 lines
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99What do these columns represent? I'm guessing the large improvement was in context switches?
I pasted the header from reaim above;
hmpf. I wonder what's the difference between Jobs/min, Jobs/min(child) and Jobs/sec(child), which is not Jobs/min(child) / 60.
Quoted 8 lines
Quoted 4 lines
I'm not entirely sure what the bloody thing does and I hate that it takes hours to get these numbers :/
Bloody stupid benchmark if you ask me.
heh, yes, it's stupid how long many benchmarks take. Ditch it. A change like this should be testable with a 30-line microbenchmark which runs in 5 seconds tops.
Another very nice option would be to stick the relevant workload patterns into 'perf bench', calibrate it to emit similar figures (and double check the speedup is similar as well) and thus make it an AIM7 work-alike microbenchmark.
Thanks,
Ingo
Peter Zijlstra
maintainerQuoted 8 lines · Ingo Molnar
Quoted 3 lines
heh, yes, it's stupid how long many benchmarks take. Ditch it. A change like this should be testable with a 30-line microbenchmark which runs in 5 seconds tops.
Another very nice option would be to stick the relevant workload patterns into 'perf bench', calibrate it to emit similar figures (and double check the speedup is similar as well) and thus make it an AIM7 work-alike microbenchmark.
/me stares at Jason and Waiman.. :-)
Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Ingo Molnar
Quoted 3 lines
heh, yes, it's stupid how long many benchmarks take. Ditch it. A change like this should be testable with a 30-line microbenchmark which runs in 5 seconds tops.
Another very nice option would be to stick the relevant workload patterns into 'perf bench', calibrate it to emit similar figures (and double check the speedup is similar as well) and thus make it an AIM7 work-alike microbenchmark.
/me stares at Jason and Waiman.. :-)
It shouldn't be too hard to get the mutex exercising portion of AIM7 into perf. I will discuss with Jason about this when we finish some of the high-priority tasks we currently have.
-Longman
Quoted 6 lines · Andrew Morton
Quoted 4 lines · On Mon, 10 Feb 2014 20:58:20 +0100 Peter Zijlstra <[email protected]> wrote:
Hi all,
I would propose merging the following patches...
Quoted 8 lines
Quoted 5 lines
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99What do these columns represent? I'm guessing the large improvement was in context switches?
Hello,
I also re-tested the mutex patches 1-6 on my 2 and 8 socket machines with the high_systime and fserver AIM7 workloads (ran on disk). The workloads are able to generate contention on the &EXT4_SB(inode->i_sb)->s_orphan_lock mutex. Below are the % improvement in throughput with the patches on a recent tip kernel. The main benefits were on the larger box and when there were higher number of users.
Note: the -0.7% drop in performance for fserver at 10-90 users on the 2 socket machine was mainly due to "[PATCH 6/8] mutex: Extra reschedule point". Without patch 6, there was almost no % difference in throughput between the baseline kernel and kernel with patches 1-5.
8 socket machine:
--------------------------
fserver
--------------------------
users | % improvement
| in throughput
| with patches--------------------------
1000-2000 | +29.2%
--------------------------
100-900 | +10.0%
--------------------------
10-90 | +0.4%
--------------------------
high_systime
--------------------------
users | % improvement
| in throughput
| with patches--------------------------
1000-2000 | +34.9%
--------------------------
100-900 | +49.2%
--------------------------
10-90 | +3.1%
2 socket machine:
--------------------------
fserver
--------------------------
users | % improvement
| in throughput
| with patches--------------------------
1000-2000 | +1.8%
--------------------------
100-900 | +0.0%
--------------------------
10-90 | -0.7%
--------------------------
high_systime
--------------------------
users | % improvement
| in throughput
| with patches--------------------------
1000-2000 | +0.8%
--------------------------
100-900 | +0.4%
--------------------------
10-90 | +0.0%
Quoted 7 lines · Peter Zijlstra
Hi all,
I would propose merging the following patches...
The first set is mostly from Jason and tweaks the mutex adaptive spinning, AIM7 throughput numbers:
Quoted 6 lines
PRE: 100 2000.04 21564.90 2721.29 311.99 3.12 0.01 0.00 99 POST: 100 2000.04 42603.85 5142.80 311.99 3.12 0.00 0.00 99The second set is the qrwlock, although mostly rewritten by me. I didn't do much with it other than boot and build a kernel. But I like them because of the much better worst case preformance.
This series passes a short locktorture test when based on top of current tip/core/locking.
But don't read too much into this... This was in an 8-CPU KVM guest on x86, and locktorture is still a bit on the lame side. But you have to start somewhere!
Thanx, Paul