[PATCH-tip v2 0/3] locking/rwsem: Minor twists to improve rwsem performance

[PATCH-tip v2 0/3] locking/rwsem: Minor twists to improve rwsem performance

[Waiman Long]

v1->v2:
 - Replace trylock with a more light-weight raw_spin_is_locked()
   call to reduce overhead.
 - Run fio test in addition to rwsem microbenchmark.

This patch set introduces minor changes to the rwsem code path to
provide minor performance improvement especially with short critical
sections.

Patch 1 checks wait_list without lock when spinners are present.

Patch 2 moves down the rwsem_down_read_failed() function after the
optimistic spinning section so that functions in that section can
be used.

Patch 3 undoes active read lock ASAP when either the spinners are
present or the wait_lock isn't free.

Waiman Long (3):
  locking/rwsem: Check wait_list without lock if spinner present
  locking/rwsem: relocate rwsem_down_read_failed()
  locking/rwsem: Stop active read lock ASAP

 kernel/locking/rwsem-xadd.c | 129 ++++++++++++++++++++++++++------------------
 1 file changed, 76 insertions(+), 53 deletions(-)

-- 
1.8.3.1

[PATCH-tip v2 1/3] locking/rwsem: Check wait_list without lock if spinner present

[Waiman Long]

In rwsem_wake(), we can safely check the wait_list to see if waiters
are present without lock when there are spinners to fall back on in
case we miss a waiter.  The advantage is that we can save a pair of
spin_lock/unlock calls when the wait_list is empty. This translates
to a reduction in latency and hence slightly better performance.

The raw_spin_trylock_irqsave() call is also being replaced by a
raw_spin_is_locked() to reduce the overhead of irqsave/irqrestore
especially when the trylock fails.

On a 2-socket 36-core x86-64 E5-2699 v3 system, a rwsem microbenchmark
was run with 36 locking threads doing 1 million writer lock/unlock
operations each, the resulting locking rates (avg of 3 runs) on a
4.11-rc1 based kernel were 4,923 Mop/s and 5,136 Mop/s without and
with the patch respectively. That was an increase of about 4%.

On the same system, a 36-thread fio direct IO random write test to
the same 2GB file on a XFS formatted ramdisk was run. The aggregated
bandwidth was 1564.4 MB/s and 1593.0 MB/s before and after the
patch. That was an increase of about 2%.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/rwsem-xadd.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index 34e727f..f31dd61b 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -587,7 +587,7 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 
 	/*
 	 * If a spinner is present, it is not necessary to do the wakeup.
-	 * Try to do wakeup only if the trylock succeeds to minimize
+	 * Try to do wakeup only if the wait_lock is free to minimize
 	 * spinlock contention which may introduce too much delay in the
 	 * unlock operation.
 	 *
@@ -595,7 +595,7 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 	 *    ---------------		-----------------------
 	 * [S]   osq_unlock()		[L]   osq
 	 *	 MB			      RMB
-	 * [RmW] rwsem_try_write_lock() [RmW] spin_trylock(wait_lock)
+	 * [RmW] rwsem_try_write_lock() [RmW] spin_is_locked(wait_lock)
 	 *
 	 * Here, it is important to make sure that there won't be a missed
 	 * wakeup while the rwsem is free and the only spinning writer goes
@@ -611,12 +611,18 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 		 * state is consulted before reading the wait_lock.
 		 */
 		smp_rmb();
-		if (!raw_spin_trylock_irqsave(&sem->wait_lock, flags))
+
+		/*
+		 * Normally checking wait_list without wait_lock isn't safe
+		 * as we may miss an incoming waiter. With spinners present,
+		 * however, we have someone to fall back on in case that
+		 * happens.
+		 */
+		if (list_empty(&sem->wait_list) ||
+		    raw_spin_is_locked(&sem->wait_lock))
 			return sem;
-		goto locked;
 	}
 	raw_spin_lock_irqsave(&sem->wait_lock, flags);
-locked:
 
 	if (!list_empty(&sem->wait_list))
 		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
-- 
1.8.3.1

[PATCH-tip v2 2/3] locking/rwsem: relocate rwsem_down_read_failed()

[Waiman Long]

The rwsem_down_read_failed() function was relocted from above the
optimistic spinning section to below that section. This enables
it to use functions in that section in future patches. There is no
code change.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/rwsem-xadd.c | 96 ++++++++++++++++++++++-----------------------
 1 file changed, 48 insertions(+), 48 deletions(-)

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index f31dd61b..be638ca 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -219,54 +219,6 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 }
 
 /*
- * Wait for the read lock to be granted
- */
-__visible
-struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
-{
-	long count, adjustment = -RWSEM_ACTIVE_READ_BIAS;
-	struct rwsem_waiter waiter;
-	DEFINE_WAKE_Q(wake_q);
-
-	waiter.task = current;
-	waiter.type = RWSEM_WAITING_FOR_READ;
-
-	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
-		adjustment += RWSEM_WAITING_BIAS;
-	list_add_tail(&waiter.list, &sem->wait_list);
-
-	/* we're now waiting on the lock, but no longer actively locking */
-	count = atomic_long_add_return(adjustment, &sem->count);
-
-	/*
-	 * If there are no active locks, wake the front queued process(es).
-	 *
-	 * If there are no writers and we are first in the queue,
-	 * wake our own waiter to join the existing active readers !
-	 */
-	if (count == RWSEM_WAITING_BIAS ||
-	    (count > RWSEM_WAITING_BIAS &&
-	     adjustment != -RWSEM_ACTIVE_READ_BIAS))
-		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
-
-	raw_spin_unlock_irq(&sem->wait_lock);
-	wake_up_q(&wake_q);
-
-	/* wait to be given the lock */
-	while (true) {
-		set_current_state(TASK_UNINTERRUPTIBLE);
-		if (!waiter.task)
-			break;
-		schedule();
-	}
-
-	__set_current_state(TASK_RUNNING);
-	return sem;
-}
-EXPORT_SYMBOL(rwsem_down_read_failed);
-
-/*
  * This function must be called with the sem->wait_lock held to prevent
  * race conditions between checking the rwsem wait list and setting the
  * sem->count accordingly.
@@ -461,6 +413,54 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
 #endif
 
 /*
+ * Wait for the read lock to be granted
+ */
+__visible
+struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
+{
+	long count, adjustment = -RWSEM_ACTIVE_READ_BIAS;
+	struct rwsem_waiter waiter;
+	DEFINE_WAKE_Q(wake_q);
+
+	waiter.task = current;
+	waiter.type = RWSEM_WAITING_FOR_READ;
+
+	raw_spin_lock_irq(&sem->wait_lock);
+	if (list_empty(&sem->wait_list))
+		adjustment += RWSEM_WAITING_BIAS;
+	list_add_tail(&waiter.list, &sem->wait_list);
+
+	/* we're now waiting on the lock, but no longer actively locking */
+	count = atomic_long_add_return(adjustment, &sem->count);
+
+	/*
+	 * If there are no active locks, wake the front queued process(es).
+	 *
+	 * If there are no writers and we are first in the queue,
+	 * wake our own waiter to join the existing active readers !
+	 */
+	if (count == RWSEM_WAITING_BIAS ||
+	    (count > RWSEM_WAITING_BIAS &&
+	     adjustment != -RWSEM_ACTIVE_READ_BIAS))
+		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
+
+	raw_spin_unlock_irq(&sem->wait_lock);
+	wake_up_q(&wake_q);
+
+	/* wait to be given the lock */
+	while (true) {
+		set_current_state(TASK_UNINTERRUPTIBLE);
+		if (!waiter.task)
+			break;
+		schedule();
+	}
+
+	__set_current_state(TASK_RUNNING);
+	return sem;
+}
+EXPORT_SYMBOL(rwsem_down_read_failed);
+
+/*
  * Wait until we successfully acquire the write lock
  */
 static inline struct rw_semaphore *
-- 
1.8.3.1

[PATCH-tip v2 3/3] locking/rwsem: Stop active read lock ASAP

[Waiman Long]

Currently, when down_read() fails, the active read locking isn't undone
until the rwsem_down_read_failed() function grabs the wait_lock. If the
wait_lock is contended, it may takes a while to get the lock. During
that period, writer lock stealing will be disabled because of the
active read lock.

This patch will release the active read lock ASAP when either the
optimisitic spinners are present or the trylock fails so that writer
lock stealing can happen sooner.

On a 2-socket 36-core x86-64 E5-2699 v3 system, a rwsem microbenchmark
was run with 36 locking threads (one/core) doing 50k reader and writer
lock/unlock operations each, the resulting locking rates (avg of 3
runs) on a 4.11-rc1 based kernel were 492.2 Mop/s and 506.4 Mop/s
without and with the patch respectively. That was an increase of
about 3%.

On the same system, a 36-thread fio direct IO random read/write test
(18 read threads & 18 write threads) to the same 2GB file on a XFS
formatted ramdisk was run. The aggregated bandwidths were:

  I/O Type     Before patch   After patch   % Change
  --------     ------------   -----------   --------
  Random read    94.4 MB/s      93.3 MB/s     -1.2%
  Random write  655.5 MB/s     670.9 MB/s     +2.3%

The code change favors write operations. As a result, the read
bandwidth was reduced a bit, but the write bandwidth was increased
proportionally more than the reduction in the read bandwidth.

Signed-off-by: Waiman Long <longman@redhat.com>
---
 kernel/locking/rwsem-xadd.c | 27 ++++++++++++++++++++++-----
 1 file changed, 22 insertions(+), 5 deletions(-)

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index be638ca..45cd58d 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -418,6 +418,7 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
 __visible
 struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 {
+	bool first_in_queue = false;
 	long count, adjustment = -RWSEM_ACTIVE_READ_BIAS;
 	struct rwsem_waiter waiter;
 	DEFINE_WAKE_Q(wake_q);
@@ -425,13 +426,30 @@ struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 	waiter.task = current;
 	waiter.type = RWSEM_WAITING_FOR_READ;
 
+	/*
+	 * Undo read bias from down_read operation to stop active locking if:
+	 * 1) Optimistic spinners are present; or
+	 * 2) the wait_lock isn't free.
+	 * Doing that after taking the wait_lock may otherwise block writer
+	 * lock stealing for too long impacting performance.
+	 */
+	if (rwsem_has_spinner(sem) || raw_spin_is_locked(&sem->wait_lock)) {
+		atomic_long_add(-RWSEM_ACTIVE_READ_BIAS, &sem->count);
+		adjustment = 0;
+	}
+
 	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
+	if (list_empty(&sem->wait_list)) {
 		adjustment += RWSEM_WAITING_BIAS;
+		first_in_queue = true;
+	}
 	list_add_tail(&waiter.list, &sem->wait_list);
 
-	/* we're now waiting on the lock, but no longer actively locking */
-	count = atomic_long_add_return(adjustment, &sem->count);
+	/* we're now waiting on the lock */
+	if (adjustment)
+		count = atomic_long_add_return(adjustment, &sem->count);
+	else
+		count = atomic_long_read(&sem->count);
 
 	/*
 	 * If there are no active locks, wake the front queued process(es).
@@ -440,8 +458,7 @@ struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 	 * wake our own waiter to join the existing active readers !
 	 */
 	if (count == RWSEM_WAITING_BIAS ||
-	    (count > RWSEM_WAITING_BIAS &&
-	     adjustment != -RWSEM_ACTIVE_READ_BIAS))
+	    (count > RWSEM_WAITING_BIAS && first_in_queue))
 		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
 
 	raw_spin_unlock_irq(&sem->wait_lock);
-- 
1.8.3.1