Skip to contentSkip to conversation

rwsem: Fine tuning

PATCH In review Davidlohr Bueso 5 participants 22 messages Jan 30, 2015 – Feb 18, 2015 Locking primitives

lore
Share & tools
lore
#0 lore raw

v2 cover rwsem: Fine tuning

Hello,

First two patches are self descriptive obvious add-ons.

The rest are performance enhancements for write-mostly workloads. While this is not our priority (use mutexes instead!!), there are cases where heavy use of writers can severely hurt rwsem performance. For instance, we got reports[1] of writer only issues when converting the i_mmap_rwsem from mutex, on a workload that pathologically pounds on this lock for vma operations:

- 81.20% execl [kernel.kallsyms] [k] osq_lock
- 100.00% mutex_optimistic_spin
__mutex_lock_slowpath
- mutex_lock
+ 47.71% unlink_file_vma
+ 34.91% vma_adjust
+ 17.38% vma_link

This is enough to make small differences painfully evident. These changes (particularly patch 5/5) recover most (~75%) of the performance regression. Patches 3- 5 deal with optimistic spinning fine tuning. Details are in the individual patches. Passes multiple x86-64 tests.

Thanks!

Changes since v1 (https://lkml.org/lkml/2015/1/26/34):

- Redid patch 2.

- Improved "Check for active lock before bailing on spinning" patch to consider checking if the lock has a new owner.

- Dropped patch 5, will send a new patch later disabling preemption in the slowpath to get rid of the barriers (assuming testing goes well) without missing wakeups. It's not very related to the patches in this series anyway.

Davidlohr Bueso (5):
locking/rwsem: Use task->state helpers
locking/rwsem: Document barrier need when waking tasks locking/rwsem: Set lock ownership ASAP
locking/rwsem: Avoid deceiving lock spinners locking/rwsem: Check for active lock before bailing on spinning

 kernel/locking/mutex.c          |  2 +-
 kernel/locking/rwsem-spinlock.c |  9 +++++-
 kernel/locking/rwsem-xadd.c     | 66 ++++++++++++++++++++++++++++-------------
 kernel/locking/rwsem.c          | 22 +-------------
 kernel/locking/rwsem.h          | 20 +++++++++++++
 5 files changed, 76 insertions(+), 43 deletions(-)
 create mode 100644 kernel/locking/rwsem.h
Signature · 1 line
2.1.4
#1 lore raw

PATCH v2 1/5 locking/rwsem: Use task->state helpers

Call __set_task_state() instead of assigning the new state directly. These interfaces also aid CONFIG_DEBUG_ATOMIC_SLEEP environments, keeping track of who last changed the state.

---
 kernel/locking/rwsem-spinlock.c | 2 +-
 kernel/locking/rwsem-xadd.c     | 3 +--
 2 files changed, 2 insertions(+), 3 deletions(-)
kernel/locking/rwsem-spinlock.c +1 -1
index 2c93571..2555ae1 100644
@@ -154,7 +154,7 @@ void __sched __down_read(struct rw_semaphore *sem)
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}
 
-	tsk->state = TASK_RUNNING;
+	__set_task_state(tsk, TASK_RUNNING);
  out:
 	;
 }
kernel/locking/rwsem-xadd.c +1 -2
index 7628c3f..2f7cc40 100644
@@ -242,8 +242,7 @@ struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 		schedule();
 	}
 
-	tsk->state = TASK_RUNNING;
-
+	__set_task_state(tsk, TASK_RUNNING);
 	return sem;
 }
 EXPORT_SYMBOL(rwsem_down_read_failed);
Signature · 1 line
2.1.4
#2 lore raw

PATCH v2 2/5 locking/rwsem: Document barrier need when waking tasks

In reply to Davidlohr Bueso

The need for the smp_mb in __rwsem_do_wake should be properly documented. Applies to both xadd and spinlock variants.

---
 kernel/locking/rwsem-spinlock.c | 7 +++++++
 kernel/locking/rwsem-xadd.c     | 7 +++++++
 2 files changed, 14 insertions(+)
kernel/locking/rwsem-spinlock.c +7 -0
index 2555ae1..3a50485 100644
@@ -85,6 +85,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
 
 		list_del(&waiter->list);
 		tsk = waiter->task;
+		/*
+		 * Make sure we do not wakeup the next reader before
+		 * setting the nil condition to grant the next reader;
+		 * otherwise we could miss the wakeup on the other
+		 * side and end up sleeping again. See the pairing
+		 * in rwsem_down_read_failed().
+		 */
 		smp_mb();
 		waiter->task = NULL;
 		wake_up_process(tsk);
kernel/locking/rwsem-xadd.c +7 -0
index 2f7cc40..82aba46 100644
@@ -186,6 +186,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, enum rwsem_wake_type wake_type)
 		waiter = list_entry(next, struct rwsem_waiter, list);
 		next = waiter->list.next;
 		tsk = waiter->task;
+		/*
+		 * Make sure we do not wakeup the next reader before
+		 * setting the nil condition to grant the next reader;
+		 * otherwise we could miss the wakeup on the other
+		 * side and end up sleeping again. See the pairing
+		 * in rwsem_down_read_failed().
+		 */
 		smp_mb();
 		waiter->task = NULL;
 		wake_up_process(tsk);
Signature · 1 line
2.1.4
#3 lore raw

[tip:locking/core] locking/rwsem: Document barrier need when waking tasks

locking/rwsem: Document barrier need when waking tasks
Commit-ID:  49e4b2bcf7b812e985e65b6c8a0255b1520a6e7e
Gitweb:     http://git.kernel.org/tip/49e4b2bcf7b812e985e65b6c8a0255b1520a6e7e
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Fri, 30 Jan 2015 01:14:24 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 18 Feb 2015 16:57:10 +0100

locking/rwsem: Document barrier need when waking tasks

The need for the smp_mb() in __rwsem_do_wake() should be properly documented. Applies to both xadd and spinlock variants.

---
 kernel/locking/rwsem-spinlock.c | 7 +++++++
 kernel/locking/rwsem-xadd.c     | 7 +++++++
 2 files changed, 14 insertions(+)
kernel/locking/rwsem-spinlock.c +7 -0
index 2555ae1..3a50485 100644
@@ -85,6 +85,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
 
 		list_del(&waiter->list);
 		tsk = waiter->task;
+		/*
+		 * Make sure we do not wakeup the next reader before
+		 * setting the nil condition to grant the next reader;
+		 * otherwise we could miss the wakeup on the other
+		 * side and end up sleeping again. See the pairing
+		 * in rwsem_down_read_failed().
+		 */
 		smp_mb();
 		waiter->task = NULL;
 		wake_up_process(tsk);
kernel/locking/rwsem-xadd.c +7 -0
index 2f7cc40..82aba46 100644
@@ -186,6 +186,13 @@ __rwsem_do_wake(struct rw_semaphore *sem, enum rwsem_wake_type wake_type)
 		waiter = list_entry(next, struct rwsem_waiter, list);
 		next = waiter->list.next;
 		tsk = waiter->task;
+		/*
+		 * Make sure we do not wakeup the next reader before
+		 * setting the nil condition to grant the next reader;
+		 * otherwise we could miss the wakeup on the other
+		 * side and end up sleeping again. See the pairing
+		 * in rwsem_down_read_failed().
+		 */
 		smp_mb();
 		waiter->task = NULL;
 		wake_up_process(tsk);
#4 lore raw

PATCH v2 3/5 locking/rwsem: Set lock ownership ASAP

In reply to Davidlohr Bueso

In order to optimize the spinning step, we need to set the lock owner as soon as the lock is acquired; after a successful counter cmpxchg operation, that is. This is particularly useful as rwsems need to set the owner to nil for readers, so there is a greater chance of falling out of the spinning. Currently we only set the owner much later in the game, in the more generic level -- latency can be specially bad when waiting for a node->next pointer when releasing the osq in up_write calls.

As such, update the owner inside rwsem_try_write_lock (when the lock is obtained after blocking) and rwsem_try_write_lock_unqueued (when the lock is obtained while spinning). This requires creating a new internal rwsem.h header to share the owner related calls.

Also cleanup some headers for mutex and rwsem.

---
 kernel/locking/mutex.c      |  2 +-
 kernel/locking/rwsem-xadd.c |  8 ++++++--
 kernel/locking/rwsem.c      | 22 +---------------------
 kernel/locking/rwsem.h      | 20 ++++++++++++++++++++
 4 files changed, 28 insertions(+), 24 deletions(-)
 create mode 100644 kernel/locking/rwsem.h
kernel/locking/mutex.c +1 -1
index c67a60b..166355e 100644
@@ -25,7 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
-#include "mcs_spinlock.h"
+#include <linux/osq_lock.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,
kernel/locking/rwsem-xadd.c +6 -2
index 82aba46..07713e5 100644
@@ -14,8 +14,9 @@
 #include <linux/init.h>
 #include <linux/export.h>
 #include <linux/sched/rt.h>
+#include <linux/osq_lock.h>
 
-#include "mcs_spinlock.h"
+#include "rwsem.h"
 
 /*
  * Guide to the rw_semaphore's count field for common values.
@@ -265,6 +266,7 @@ static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
 		    RWSEM_ACTIVE_WRITE_BIAS) == RWSEM_WAITING_BIAS) {
 		if (!list_is_singular(&sem->wait_list))
 			rwsem_atomic_update(RWSEM_WAITING_BIAS, sem);
+		rwsem_set_owner(sem);
 		return true;
 	}
 
@@ -284,8 +286,10 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
 			return false;
 
 		old = cmpxchg(&sem->count, count, count + RWSEM_ACTIVE_WRITE_BIAS);
-		if (old == count)
+		if (old == count) {
+			rwsem_set_owner(sem);
 			return true;
+		}
 
 		count = old;
 	}
kernel/locking/rwsem.c +1 -21
index e2d3bc7..205be0c 100644
@@ -9,29 +9,9 @@
 #include <linux/sched.h>
 #include <linux/export.h>
 #include <linux/rwsem.h>
-
 #include <linux/atomic.h>
 
-#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
-static inline void rwsem_set_owner(struct rw_semaphore *sem)
-{
-	sem->owner = current;
-}
-
-static inline void rwsem_clear_owner(struct rw_semaphore *sem)
-{
-	sem->owner = NULL;
-}
-
-#else
-static inline void rwsem_set_owner(struct rw_semaphore *sem)
-{
-}
-
-static inline void rwsem_clear_owner(struct rw_semaphore *sem)
-{
-}
-#endif
+#include "rwsem.h"
 
 /*
  * lock for reading
kernel/locking/rwsem.h new file +20 -0
new file mode 100644
index 0000000..870ed9a
@@ -0,0 +1,20 @@
+#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
+static inline void rwsem_set_owner(struct rw_semaphore *sem)
+{
+	sem->owner = current;
+}
+
+static inline void rwsem_clear_owner(struct rw_semaphore *sem)
+{
+	sem->owner = NULL;
+}
+
+#else
+static inline void rwsem_set_owner(struct rw_semaphore *sem)
+{
+}
+
+static inline void rwsem_clear_owner(struct rw_semaphore *sem)
+{
+}
+#endif
Signature · 1 line
2.1.4
#5 lore raw

[tip:locking/core] locking/rwsem: Set lock ownership ASAP

locking/rwsem: Set lock ownership ASAP
Commit-ID:  7a215f89a0335582292ec6f3edaa3abd570da75a
Gitweb:     http://git.kernel.org/tip/7a215f89a0335582292ec6f3edaa3abd570da75a
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Fri, 30 Jan 2015 01:14:25 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 18 Feb 2015 16:57:13 +0100

locking/rwsem: Set lock ownership ASAP

In order to optimize the spinning step, we need to set the lock owner as soon as the lock is acquired; after a successful counter cmpxchg operation, that is. This is particularly useful as rwsems need to set the owner to nil for readers, so there is a greater chance of falling out of the spinning. Currently we only set the owner much later in the game, in the more generic level -- latency can be specially bad when waiting for a node->next pointer when releasing the osq in up_write calls.

As such, update the owner inside rwsem_try_write_lock (when the lock is obtained after blocking) and rwsem_try_write_lock_unqueued (when the lock is obtained while spinning). This requires creating a new internal rwsem.h header to share the owner related calls.

Also cleanup some headers for mutex and rwsem.

---
 kernel/locking/mutex.c      |  2 +-
 kernel/locking/rwsem-xadd.c |  8 ++++++--
 kernel/locking/rwsem.c      | 22 +---------------------
 kernel/locking/rwsem.h      | 20 ++++++++++++++++++++
 4 files changed, 28 insertions(+), 24 deletions(-)
kernel/locking/mutex.c +1 -1
index 59cd6c3..43bf25e 100644
@@ -25,7 +25,7 @@
 #include <linux/spinlock.h>
 #include <linux/interrupt.h>
 #include <linux/debug_locks.h>
-#include "mcs_spinlock.h"
+#include <linux/osq_lock.h>
 
 /*
  * In the DEBUG case we are using the "NULL fastpath" for mutexes,
kernel/locking/rwsem-xadd.c +6 -2
index 82aba46..07713e5 100644
@@ -14,8 +14,9 @@
 #include <linux/init.h>
 #include <linux/export.h>
 #include <linux/sched/rt.h>
+#include <linux/osq_lock.h>
 
-#include "mcs_spinlock.h"
+#include "rwsem.h"
 
 /*
  * Guide to the rw_semaphore's count field for common values.
@@ -265,6 +266,7 @@ static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
 		    RWSEM_ACTIVE_WRITE_BIAS) == RWSEM_WAITING_BIAS) {
 		if (!list_is_singular(&sem->wait_list))
 			rwsem_atomic_update(RWSEM_WAITING_BIAS, sem);
+		rwsem_set_owner(sem);
 		return true;
 	}
 
@@ -284,8 +286,10 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
 			return false;
 
 		old = cmpxchg(&sem->count, count, count + RWSEM_ACTIVE_WRITE_BIAS);
-		if (old == count)
+		if (old == count) {
+			rwsem_set_owner(sem);
 			return true;
+		}
 
 		count = old;
 	}
kernel/locking/rwsem.c +1 -21
index e2d3bc7..205be0c 100644
@@ -9,29 +9,9 @@
 #include <linux/sched.h>
 #include <linux/export.h>
 #include <linux/rwsem.h>
-
 #include <linux/atomic.h>
 
-#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
-static inline void rwsem_set_owner(struct rw_semaphore *sem)
-{
-	sem->owner = current;
-}
-
-static inline void rwsem_clear_owner(struct rw_semaphore *sem)
-{
-	sem->owner = NULL;
-}
-
-#else
-static inline void rwsem_set_owner(struct rw_semaphore *sem)
-{
-}
-
-static inline void rwsem_clear_owner(struct rw_semaphore *sem)
-{
-}
-#endif
+#include "rwsem.h"
 
 /*
  * lock for reading
kernel/locking/rwsem.h new file +20 -0
new file mode 100644
index 0000000..870ed9a
@@ -0,0 +1,20 @@
+#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
+static inline void rwsem_set_owner(struct rw_semaphore *sem)
+{
+	sem->owner = current;
+}
+
+static inline void rwsem_clear_owner(struct rw_semaphore *sem)
+{
+	sem->owner = NULL;
+}
+
+#else
+static inline void rwsem_set_owner(struct rw_semaphore *sem)
+{
+}
+
+static inline void rwsem_clear_owner(struct rw_semaphore *sem)
+{
+}
+#endif
#6 lore raw

PATCH v2 4/5 locking/rwsem: Avoid deceiving lock spinners

In reply to Davidlohr Bueso

When readers hold the semaphore, the ->owner is nil. As such, and unlike mutexes, '!owner' does not necessarily imply that the lock is free. This will cause writers to potentially spin excessively as they've been mislead to thinking they have a chance of acquiring the lock, instead of blocking.

This patch therefore enhances the counter check when the owner is not set by the time we've broken out of the loop. Otherwise we can return true as a new owner has the lock and thus we want to continue spinning. While at it, we can make rwsem_spin_on_owner() less ambiguos and return right away under need_resched conditions.

---
 kernel/locking/rwsem-xadd.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
kernel/locking/rwsem-xadd.c +15 -6
index 07713e5..1c0d11e 100644
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
-		if (need_resched())
-			break;
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+
 	/*
-	 * We break out the loop above on need_resched() or when the
-	 * owner changed, which is a sign for heavy contention. Return
-	 * success only when sem->owner is NULL.
+	 * When the owner is not set, the lock could be free or
+	 * held by readers. Check the counter to verify the
+	 * state.
 	 */
-	return sem->owner == NULL;
+	count = READ_ONCE(sem->count);
+	return (count == 0 || count == RWSEM_WAITING_BIAS);
 }
 
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
Signature · 1 line
2.1.4
#7 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 34 lines · Davidlohr Bueso

When readers hold the semaphore, the ->owner is nil. As such, and unlike mutexes, '!owner' does not necessarily imply that the lock is free. This will cause writers to potentially spin excessively as they've been mislead to thinking they have a chance of acquiring the lock, instead of blocking.

This patch therefore enhances the counter check when the owner is not set by the time we've broken out of the loop. Otherwise we can return true as a new owner has the lock and thus we want to continue spinning. While at it, we can make rwsem_spin_on_owner() less ambiguos and return right away under need_resched conditions.

---
 kernel/locking/rwsem-xadd.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
kernel/locking/rwsem-xadd.c +5 -2
index 07713e5..1c0d11e 100644
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
-		if (need_resched())
-			break;
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 10 lines
kernel/locking/rwsem-xadd.c +5 -0
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership. Now during heavy lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads. This was the assumption in the older code. The trade
off may or may not be worth it depending on how big the thread switching overhead is and how long the lock is held.

It will be good to have a few data points to make sure that this change is beneficial.

Quoted 4 lines
kernel/locking/rwsem-xadd.c +0 -3
 	/*
-	 * We break out the loop above on need_resched() or when the
-	 * owner changed, which is a sign for heavy contention. Return
-	 * success only when sem->owner is NULL.

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 366

Quoted 10 lines
kernel/locking/rwsem-xadd.c +5 -1
+	 * When the owner is not set, the lock could be free or
+	 * held by readers. Check the counter to verify the
+	 * state.
 	 */
-	return sem->owner == NULL;
+	count = READ_ONCE(sem->count);
+	return (count == 0 || count == RWSEM_WAITING_BIAS);
 }
 
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)

Thanks.

Tim

#8 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 42 lines · Tim Chen
Quoted 41 lines · Davidlohr Bueso

When readers hold the semaphore, the ->owner is nil. As such, and unlike mutexes, '!owner' does not necessarily imply that the lock is free. This will cause writers to potentially spin excessively as they've been mislead to thinking they have a chance of acquiring the lock, instead of blocking.

This patch therefore enhances the counter check when the owner is not set by the time we've broken out of the loop. Otherwise we can return true as a new owner has the lock and thus we want to continue spinning. While at it, we can make rwsem_spin_on_owner() less ambiguos and return right away under need_resched conditions.

---
 kernel/locking/rwsem-xadd.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
kernel/locking/rwsem-xadd.c +7 -2
index 07713e5..1c0d11e 100644
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
-		if (need_resched())
-			break;
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
Quoted 8 lines

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 3 lines
kernel/locking/rwsem-xadd.c +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Under heavy contention, time spinning will force us to ultimately block anyway.

Thanks,
Davidlohr

#9 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 14 lines
Quoted 10 lines

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 5 lines
kernel/locking/rwsem-xadd.c +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 6 lines
Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Under heavy contention, time spinning will force us to ultimately block anyway.

The question is under heavy contention, if we are going to block anyway, won't it be more advantageous not to continue spinning so we can use the cycles for useful task? The original code assumes that if the lock has switched owner, then we are under heavy contention and we can stop spinning and block. I think it'll be useful to have some data comparing the two behaviors.

Thanks.

Tim

#10 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 17 lines · Tim Chen
Quoted 17 lines
Quoted 9 lines

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 4 lines
kernel/locking/rwsem-xadd.c +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Quoted 6 lines
Quoted 2 lines

Under heavy contention, time spinning will force us to ultimately block anyway.

The question is under heavy contention, if we are going to block anyway, won't it be more advantageous not to continue spinning so we can use the cycles for useful task?

Hi Tim,

Now that we have the OSQ logic, under heavy contention, there will still only be 1 thread that is spinning on owner at a time. So if another thread is able to obtain the lock before the spinner, we're only sending the top spinner of the lock to the slowpath. As long as the new lock owner is running, there is a chance for this top spinner to obtain the lock, and spinning would be useful.

Since we have the need_resched() checks, this thread will block when there really is another task that should run over the spinning thread.

#11 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 21 lines · Jason Low
Quoted 20 lines · Tim Chen
Quoted 19 lines
Quoted 9 lines

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 4 lines
kernel/locking/rwsem-xadd.c +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Under heavy contention, time spinning will force us to ultimately block anyway.

Quoted 8 lines
Quoted 3 lines

The question is under heavy contention, if we are going to block anyway, won't it be more advantageous not to continue spinning so we can use the cycles for useful task?

Hi Tim,

Now that we have the OSQ logic, under heavy contention, there will still only be 1 thread that is spinning on owner at a time.

That's true. We cannot have the lock grabbed by a new write contender as any new writer contender of the lock will be queued by the OSQ logic. Only the
thread doing the optimistic spin is attempting write lock. In other word, switching of write owner of the rwsem to a new owner cannot happen. Either write owner stay as the original one, or we don't have a write owner. So using test of write owner switching as an indicator of congestion is incorrect.

If my reasoning above is sound, then the check

+ if (READ_ONCE(sem->owner))
+ return true; /* new owner, continue spinning */
+

is unnecessary and can be removed, as we cannot have a new write owner of the rwsem, other than the thread doing optimistic spinning.

Tim

#12 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 31 lines · Tim Chen
Quoted 21 lines · Jason Low
Quoted 20 lines · Tim Chen
Quoted 19 lines
Quoted 9 lines

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 4 lines
kernel/locking/rwsem-xadd.c +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Under heavy contention, time spinning will force us to ultimately block anyway.

Quoted 8 lines
Quoted 3 lines

The question is under heavy contention, if we are going to block anyway, won't it be more advantageous not to continue spinning so we can use the cycles for useful task?

Hi Tim,

Now that we have the OSQ logic, under heavy contention, there will still only be 1 thread that is spinning on owner at a time.

Quoted 6 lines

That's true. We cannot have the lock grabbed by a new write contender as any new writer contender of the lock will be queued by the OSQ logic. Only the
thread doing the optimistic spin is attempting write lock. In other word, switching of write owner of the rwsem to a new owner cannot happen.

Another thread can still obtain the write lock in the fast path though right? We try to obtain the write lock once before calling rwsem_down_write_failed().

#13 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 39 lines · Jason Low
Quoted 31 lines · Tim Chen
Quoted 21 lines · Jason Low
Quoted 20 lines · Tim Chen
Quoted 19 lines
Quoted 9 lines

Review

Quoted 4 lines
(quoted diff) +3 -0
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Do you have some comparison data of whether it is more advantageous to continue spinning when owner changes? After the above change, rwsem will behave more like a spin lock for write lock and will keep spinning when the lock changes ownership.

But recall we still abort when need_resched, so the spinning isn't infinite. Never has been.

Quoted 3 lines

Now during heavy
lock contention, if we don't continue spinning and sleep, we may use the clock cycles for actually running other threads.

Under heavy contention, time spinning will force us to ultimately block anyway.

Quoted 8 lines
Quoted 3 lines

The question is under heavy contention, if we are going to block anyway, won't it be more advantageous not to continue spinning so we can use the cycles for useful task?

Hi Tim,

Now that we have the OSQ logic, under heavy contention, there will still only be 1 thread that is spinning on owner at a time.

Quoted 6 lines

That's true. We cannot have the lock grabbed by a new write contender as any new writer contender of the lock will be queued by the OSQ logic. Only the
thread doing the optimistic spin is attempting write lock. In other word, switching of write owner of the rwsem to a new owner cannot happen.

Quoted 5 lines

Another thread can still obtain the write lock in the fast path though right? We try to obtain the write lock once before calling rwsem_down_write_failed().

True. The change owner check is still needed then.

Thinking more about this, I now agree that continue spinning is the right thing. The possible number of threads contending for write locking has been greatly reduced by OSQ logic. Most of the time any new threads doing write locking attempt will do that only once and then go directly to the OSQ. The probability of success of retrying write lock by the thread at head of OSQ is high so we should do it.

Davidlohr, you can add my Ack for this patch.

Thanks.

Tim

maintainer
#14 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

In reply to Tim Chen
Quoted 15 lines · Tim Chen

That's true. We cannot have the lock grabbed by a new write contender as any new writer contender of the lock will be queued by the OSQ logic. Only the
thread doing the optimistic spin is attempting write lock. In other word, switching of write owner of the rwsem to a new owner cannot happen. Either write owner stay as the original one, or we don't have a write owner. So using test of write owner switching as an indicator of congestion is incorrect.

If my reasoning above is sound, then the check

kernel/locking/rwsem-xadd.c +3 -0
+       if (READ_ONCE(sem->owner))
+               return true; /* new owner, continue spinning */
+
Quoted 3 lines

is unnecessary and can be removed, as we cannot have a new write owner of the rwsem, other than the thread doing optimistic spinning.

I have read the rest of the thread; but the one thing that I didn't see is trylocks, trylocks can always come in an steal things regardless of the OSQ stuff.

#15 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 16 lines · Peter Zijlstra
Quoted 15 lines · Tim Chen

That's true. We cannot have the lock grabbed by a new write contender as any new writer contender of the lock will be queued by the OSQ logic. Only the
thread doing the optimistic spin is attempting write lock. In other word, switching of write owner of the rwsem to a new owner cannot happen. Either write owner stay as the original one, or we don't have a write owner. So using test of write owner switching as an indicator of congestion is incorrect.

If my reasoning above is sound, then the check

(quoted diff) +3 -0
+       if (READ_ONCE(sem->owner))
+               return true; /* new owner, continue spinning */
+
Quoted 7 lines
Quoted 3 lines

is unnecessary and can be removed, as we cannot have a new write owner of the rwsem, other than the thread doing optimistic spinning.

I have read the rest of the thread; but the one thing that I didn't see is trylocks, trylocks can always come in an steal things regardless of the OSQ stuff.

Jason also pointed that out. So the owner change check is needed after all. Now because of the OSQ logic, even if owner has changed, the likelihood that the spinner at the head of OSQ will acquire the lock is high. So it should continue to spin.

That's because any new threads coming in will try lock only once, and go to the OSQ. It is unlikely that they will trylock at the precise moment when the owner release the lock as they do not continue to spin on the lock. The contention from new threads are low.

So letting the thread at head of OSQ to continue to spin is probably the right thing to do.

Tim

maintainer
#16 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

In reply to Davidlohr Bueso
Quoted 12 lines · Davidlohr Bueso

+++ b/kernel/locking/rwsem-xadd.c

kernel/locking/rwsem-xadd.c +5 -0
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 10 lines
kernel/locking/rwsem-xadd.c +5 -0
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Same concern as Tim; also the mutex code seems to terminate the spin when owner changes. And I think we want to have writers behave similar to mutexes, no?

Does it make sense to change things to allow owner changes from NULL, but not to NULL?

Quoted 9 lines
kernel/locking/rwsem-xadd.c +5 -1
 	/*
+	 * When the owner is not set, the lock could be free or
+	 * held by readers. Check the counter to verify the
+	 * state.
 	 */
-	return sem->owner == NULL;
+	count = READ_ONCE(sem->count);
+	return (count == 0 || count == RWSEM_WAITING_BIAS);
 }
#17 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 28 lines · Peter Zijlstra
Quoted 12 lines · Davidlohr Bueso

+++ b/kernel/locking/rwsem-xadd.c

kernel/locking/rwsem-xadd.c +5 -0
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();

kernel/locking/rwsem-xadd.c static inline bool owner_running(struct rw_semaphore *sem, · line 356

Quoted 10 lines
kernel/locking/rwsem-xadd.c +5 -0
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+

Same concern as Tim; also the mutex code seems to terminate the spin when owner changes. And I think we want to have writers behave similar to mutexes, no?

Quoted 2 lines

Does it make sense to change things to allow owner changes from NULL, but not to NULL?

I think it does, yes:

- owner changes to nil: readers can hold the lock. We know the rest.

- owner changes from nil: implies that a writer now holds the mutex. Why should we want to block? We continue to apply the same reasoning why we're spinning in the first place. This is very beneficial if, for instance, we began polling on the owner when the lock is just about to be released. So a few iterations later, the lock owner changes on us and with the current code will make us sleep. With this change, after a few spins it is very likely we'll get the lock. And if not, the need_resched will ultimately kick in and block. Additionally, as Jason pointed out, with osq we have no need to worry about simultaneously spinning on the owner at the same time.

Or am I missing something?

Thanks,
Davidlohr

#18 lore raw

Re: [PATCH 4/5] locking/rwsem: Avoid deceiving lock spinners

Quoted 1 line · Davidlohr Bueso

- owner changes from nil: implies that a writer now holds the mutex. Why

Err... that should say rwsem.

#19 lore raw

[tip:locking/core] locking/rwsem: Avoid deceiving lock spinners

In reply to Davidlohr Bueso
locking/rwsem: Avoid deceiving lock spinners
Commit-ID:  b3fd4f03ca0b9952221f39ae6790e698bf4b39e7
Gitweb:     http://git.kernel.org/tip/b3fd4f03ca0b9952221f39ae6790e698bf4b39e7
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Fri, 30 Jan 2015 01:14:26 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 18 Feb 2015 16:57:16 +0100

locking/rwsem: Avoid deceiving lock spinners

When readers hold the semaphore, the ->owner is nil. As such, and unlike mutexes, '!owner' does not necessarily imply that the lock is free. This will cause writers to potentially spin excessively as they've been mislead to thinking they have a chance of acquiring the lock, instead of blocking.

This patch therefore enhances the counter check when the owner is not set by the time we've broken out of the loop. Otherwise we can return true as a new owner has the lock and thus we want to continue spinning. While at it, we can make rwsem_spin_on_owner() less ambiguos and return right away under need_resched conditions.

---
 kernel/locking/rwsem-xadd.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
kernel/locking/rwsem-xadd.c +15 -6
index 07713e5..1c0d11e 100644
@@ -337,21 +337,30 @@ static inline bool owner_running(struct rw_semaphore *sem,
 static noinline
 bool rwsem_spin_on_owner(struct rw_semaphore *sem, struct task_struct *owner)
 {
+	long count;
+
 	rcu_read_lock();
 	while (owner_running(sem, owner)) {
-		if (need_resched())
-			break;
+		/* abort spinning when need_resched */
+		if (need_resched()) {
+			rcu_read_unlock();
+			return false;
+		}
 
 		cpu_relax_lowlatency();
 	}
 	rcu_read_unlock();
 
+	if (READ_ONCE(sem->owner))
+		return true; /* new owner, continue spinning */
+
 	/*
-	 * We break out the loop above on need_resched() or when the
-	 * owner changed, which is a sign for heavy contention. Return
-	 * success only when sem->owner is NULL.
+	 * When the owner is not set, the lock could be free or
+	 * held by readers. Check the counter to verify the
+	 * state.
 	 */
-	return sem->owner == NULL;
+	count = READ_ONCE(sem->count);
+	return (count == 0 || count == RWSEM_WAITING_BIAS);
 }
 
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
#20 lore raw

PATCH v2 5/5 locking/rwsem: Check for active lock before bailing on spinning

In reply to Davidlohr Bueso

37e9562453b (locking/rwsem: Allow conservative optimistic spinning when readers have lock) forced the default for optimistic spinning to be disabled if the lock owner was nil, which makes much sense for readers. However, while it is not our priority, we can make some optimizations for write-mostly workloads. We can bail the spinning step and still be conservative if there are any active tasks, otherwise there's really no reason not to spin, as the semaphore is most likely unlocked.

This patch recovers most of a Unixbench 'execl' benchmark throughput by sleeping less and making better average system usage:

before:
CPU %user %nice %system %iowait %steal %idle
all 0.60 0.00 8.02 0.00 0.00 91.38

after:
CPU %user %nice %system %iowait %steal %idle
all 1.22 0.00 70.18 0.00 0.00 28.60

---
 kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
kernel/locking/rwsem-xadd.c +17 -10
index 1c0d11e..e4ad019 100644
@@ -298,23 +298,30 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
 static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)
 {
 	struct task_struct *owner;
-	bool on_cpu = false;
+	bool ret = true;
 
 	if (need_resched())
 		return false;
 
 	rcu_read_lock();
 	owner = ACCESS_ONCE(sem->owner);
-	if (owner)
-		on_cpu = owner->on_cpu;
-	rcu_read_unlock();
+	if (!owner) {
+		long count = ACCESS_ONCE(sem->count);
+		/*
+		 * If sem->owner is not set, yet we have just recently entered the
+		 * slowpath with the lock being active, then there is a possibility
+		 * reader(s) may have the lock. To be safe, bail spinning in these
+		 * situations.
+		 */
+		if (count & RWSEM_ACTIVE_MASK)
+			ret = false;
+		goto done;
+	}
 
-	/*
-	 * If sem->owner is not set, yet we have just recently entered the
-	 * slowpath, then there is a possibility reader(s) may have the lock.
-	 * To be safe, avoid spinning in these situations.
-	 */
-	return on_cpu;
+	ret = owner->on_cpu;
+done:
+	rcu_read_unlock();
+	return ret;
 }
 
 static inline bool owner_running(struct rw_semaphore *sem,
Signature · 1 line
2.1.4
#21 lore raw

[tip:locking/core] locking/rwsem: Check for active lock before bailing on spinning

locking/rwsem: Check for active lock before bailing on spinning
Commit-ID:  1a99367023f6ac664365a37fa508b059e31d0e88
Gitweb:     http://git.kernel.org/tip/1a99367023f6ac664365a37fa508b059e31d0e88
Author:     Davidlohr Bueso <[email protected]>
AuthorDate: Fri, 30 Jan 2015 01:14:27 -0800
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 18 Feb 2015 16:57:18 +0100

locking/rwsem: Check for active lock before bailing on spinning

37e9562453b ("locking/rwsem: Allow conservative optimistic spinning when readers have lock") forced the default for optimistic spinning to be disabled if the lock owner was nil, which makes much sense for readers. However, while it is not our priority, we can make some optimizations for write-mostly workloads. We can bail the spinning step and still be conservative if there are any active tasks, otherwise there's really no reason not to spin, as the semaphore is most likely unlocked.

This patch recovers most of a Unixbench 'execl' benchmark throughput by sleeping less and making better average system usage:

before:
CPU %user %nice %system %iowait %steal %idle
all 0.60 0.00 8.02 0.00 0.00 91.38

after:
CPU %user %nice %system %iowait %steal %idle
all 1.22 0.00 70.18 0.00 0.00 28.60

---
 kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
kernel/locking/rwsem-xadd.c +17 -10
index 1c0d11e..e4ad019 100644
@@ -298,23 +298,30 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
 static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)
 {
 	struct task_struct *owner;
-	bool on_cpu = false;
+	bool ret = true;
 
 	if (need_resched())
 		return false;
 
 	rcu_read_lock();
 	owner = ACCESS_ONCE(sem->owner);
-	if (owner)
-		on_cpu = owner->on_cpu;
-	rcu_read_unlock();
+	if (!owner) {
+		long count = ACCESS_ONCE(sem->count);
+		/*
+		 * If sem->owner is not set, yet we have just recently entered the
+		 * slowpath with the lock being active, then there is a possibility
+		 * reader(s) may have the lock. To be safe, bail spinning in these
+		 * situations.
+		 */
+		if (count & RWSEM_ACTIVE_MASK)
+			ret = false;
+		goto done;
+	}
 
-	/*
-	 * If sem->owner is not set, yet we have just recently entered the
-	 * slowpath, then there is a possibility reader(s) may have the lock.
-	 * To be safe, avoid spinning in these situations.
-	 */
-	return on_cpu;
+	ret = owner->on_cpu;
+done:
+	rcu_read_unlock();
+	return ret;
 }
 
 static inline bool owner_running(struct rw_semaphore *sem,