Skip to contentSkip to conversation

locking/core patches

PATCH In review Peter Zijlstra 6 participants 35 messages Feb 10, 2014 – Feb 26, 2014

Subsystems (3)
lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

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

author maintainer
#1 lore raw

PATCH 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,
author maintainer
#2 lore raw

PATCH 2/8 mutex: In mutex_can_spin_on_owner(), return false if task need_resched()

In reply to Peter Zijlstra

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.

---
 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_owne
 	struct task_struct *owner;
 	int retval = 1;
 
+	if (need_resched())
+		return 0;
+
 	rcu_read_lock();
 	owner = ACCESS_ONCE(lock->owner);
 	if (owner)
author maintainer
#3 lore raw

Re: [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.

---
 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_owne
 	struct task_struct *owner;
 	int retval = 1;
 
+	if (need_resched())
+		return 0;
+
 	rcu_read_lock();
 	owner = ACCESS_ONCE(lock->owner);
 	if (owner)
author maintainer
#4 lore raw

PATCH 3/8 mutex: Modify the way optimistic spinners are queued

In reply to Peter Zijlstra

The 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);
#5 lore raw

Re: [PATCH 3/8] mutex: Modify the way optimistic spinners are queued

Quoted 23 lines · Peter Zijlstra
---
 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? :)

author maintainer
#6 lore raw

Re: [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.. :-/

author maintainer
#7 lore raw

PATCH 4/8 mutex: Unlock the mutex without the wait_lock

In reply to Peter Zijlstra

When 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_t
 	if (__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 =
author maintainer
#8 lore raw

PATCH 5/8 locking, mutex: Cancelable MCS lock for adaptive spinning

In reply to Peter Zijlstra

Since 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 c
 	INIT_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);
#9 lore raw

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;
+}
author maintainer
#10 lore raw

Re: [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;
+}
#11 lore raw

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.

author maintainer
#12 lore raw

Re: [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 the oqs_wait_next() path, which aren't necessary when node->next != NULL.

Quoted 6 lines

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.

True all; now if only we had a useful benchmark so we could test if it makes a difference or not :-)

#13 lore raw

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 the oqs_wait_next() path, which aren't necessary when node->next != NULL.

Quoted 6 lines

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.

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

#14 lore raw

Re: [PATCH 5/8] locking, mutex: Cancelable MCS lock for adaptive spinning

In reply to Peter Zijlstra
Quoted 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?

author maintainer
#15 lore raw

Re: [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?

Reviewed-by
#16 lore raw

Re: [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.

author maintainer
#17 lore raw

PATCH 6/8 mutex: Extra reschedule point

In reply to Peter Zijlstra

Add 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);
 
#18 lore raw

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().

author maintainer
#19 lore raw

PATCH 7/8 locking: Introduce qrwlock

In reply to Peter Zijlstra

This 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).

[peterz: near complete rewrite]
---
 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

#20 lore raw

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            20573

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

#21 lore raw

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

author maintainer
#22 lore raw

Re: [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

author maintainer
#23 lore raw

Re: [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 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 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.

#24 lore raw

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

#25 lore raw

Re: [PATCH 7/8] locking: Introduce qrwlock

In reply to Peter Zijlstra
Quoted 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 remote

I 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

author maintainer
#26 lore raw

PATCH 8/8 x86,locking: Enable qrwlock

In reply to Peter Zijlstra

Make x86 use the fair rwlock_t.

Implement the custom queue_write_unlock() for best performance.

[peterz: near complete rewrite]
---
 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_wait
 		cpu_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 */
#27 lore raw
In reply to Peter Zijlstra
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.

author maintainer
#28 lore raw
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 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     99

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

#29 lore raw
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 childS std_dev JTI :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     99

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

#30 lore raw
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 childS std_dev JTI :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     99

What 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

author maintainer
#31 lore raw
Quoted 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.. :-)

#32 lore raw
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

#33 lore raw
In reply to Andrew Morton
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     99

What 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%

#34 lore raw
In reply to Peter Zijlstra
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     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.

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