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

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

[Waiman Long]

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 trylock fails.

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

 kernel/locking/rwsem-xadd.c | 126 +++++++++++++++++++++++++++-----------------
 1 file changed, 78 insertions(+), 48 deletions(-)

-- 
1.8.3.1

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

[Waiman Long]

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.

On a 2-socket 36-core 72-thread x86-64 E5-2699 v3 system, a rwsem
microbenchmark was run with 36 locking threads (one/core) doing 1
million writer lock/unlock operations each, the resulting locking
rates (avg of 4 runs) on a 4.10 kernel were 7,755 Mop/s and 8,276
Mop/s without and with the patch respectively. That was an increase
of about 7%.

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

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index 34e727f..b5d7055 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -611,6 +611,17 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 		 * state is consulted before reading the wait_lock.
 		 */
 		smp_rmb();
+
+		/*
+		 * 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. This can save a pair of spin_lock/unlock calls
+		 * when there is no waiter.
+		 */
+		if (list_empty(&sem->wait_list))
+			return sem;
+
 		if (!raw_spin_trylock_irqsave(&sem->wait_lock, flags))
 			return sem;
 		goto locked;
-- 
1.8.3.1

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

[Davidlohr Bueso]

On Wed, 22 Feb 2017, Waiman Long wrote:

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

This benefit is only seen in (rare) situations where there are only
writers with short hold times, no? I don't really have any objection
as I doubt the additional load will have any impact on the common case,
but it would still be nice to have more data for other benchmarks where
the lock is at least shared at times -- ie: a good thing to measure is
also fault, mmap related benchmarks.

>+		/*
>+		 * 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. This can save a pair of spin_lock/unlock calls
>+		 * when there is no waiter.
>+		 */

I would drop the last part regarding saving the spin_lock, it should be
evident from the code.

Thanks,
Davidlohr

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

[Waiman Long]

On 02/26/2017 01:49 PM, Davidlohr Bueso wrote:
> On Wed, 22 Feb 2017, Waiman Long wrote:
>
>> 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.
>
> This benefit is only seen in (rare) situations where there are only
> writers with short hold times, no? I don't really have any objection
> as I doubt the additional load will have any impact on the common case,
> but it would still be nice to have more data for other benchmarks where
> the lock is at least shared at times -- ie: a good thing to measure is
> also fault, mmap related benchmarks.

If a up_write() or up_read() coincides with a writer attempting to lock
(down_write). The unlocker may go into the wake_rwsem path even if on
one is on the wait queue. In this case, this patch can save an unneeded
spin_lock/unlock. This was what happened in the microbenchmark that I used.

The additional load shouldn't have any noticeable performance impact as
the wait_list need to be read sooner or later anyway. BTW, can you
suggest a good benchmark for testing fault, mmap related code paths?

>> +        /*
>> +         * 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. This can save a pair of spin_lock/unlock calls
>> +         * when there is no waiter.
>> +         */
>
> I would drop the last part regarding saving the spin_lock, it should be
> evident from the code. 

I will do that.

Cheers,
Longman

[PATCH-tip 2/3] locking/rwsem: move down rwsem_down_read_failed()

[Waiman Long]

Move the rwsem_down_read_failed() function down to below the
optimistic spinning section as it is going to use function in that
section in a later patch.

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 b5d7055..fb6d6f3 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

Re: [PATCH-tip 2/3] locking/rwsem: move down rwsem_down_read_failed()

[Davidlohr Bueso]

On Wed, 22 Feb 2017, Waiman Long wrote:

>Move the rwsem_down_read_failed() function down to below the
>optimistic spinning section as it is going to use function in that
>section in a later patch.

So the title is a bit ambiguous, and I would argue that this
should be folded into patch 3, and just mention it in the
changelog.

Thanks,
Davidlohr

Re: [PATCH-tip 2/3] locking/rwsem: move down rwsem_down_read_failed()

[Waiman Long]

On 02/26/2017 01:33 PM, Davidlohr Bueso wrote:
> On Wed, 22 Feb 2017, Waiman Long wrote:
>
>> Move the rwsem_down_read_failed() function down to below the
>> optimistic spinning section as it is going to use function in that
>> section in a later patch.
>
> So the title is a bit ambiguous, and I would argue that this
> should be folded into patch 3, and just mention it in the
> changelog.
>
> Thanks,
> Davidlohr

I can reword the title to clarify it a bit more.

The reason why it is a separate patch is because it will make it much
harder to review the third patch otherwise. What you get from the diff
will be a total replacement of one function block by another function
block. I would like to make the review focus on what is actually being
changed.

Cheers,
Longman

[PATCH-tip 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 72-thread x86-64 E5-2699 v3 system, a rwsem
microbenchmark was run with 36 locking threads (one/core) doing 100k
reader and writer lock/unlock operations each, the resulting locking
rates (avg of 3 runs) on a 4.10 kernel were 561.4 Mop/s and 588.8
Mop/s without and with the patch respectively. That was an increase
of about 5%.

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

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index fb6d6f3..6080afc 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -418,20 +418,40 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
 __visible
 struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 {
-	long count, adjustment = -RWSEM_ACTIVE_READ_BIAS;
+	bool first_in_queue = false;
+	long count, adjustment;
 	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))
+	/*
+	 * Undo read bias from down_read operation to stop active locking
+	 * if the lock isn't free which means it may take a while to acquire
+	 * the lock or when spinners are present. Doing that after taking the
+	 * wait_lock may block writer lock stealing for too long impacting
+	 * performance.
+	 */
+	if (rwsem_has_spinner(sem) || !raw_spin_trylock_irq(&sem->wait_lock)) {
+		atomic_long_add(-RWSEM_ACTIVE_READ_BIAS, &sem->count);
+		adjustment = 0;
+		raw_spin_lock_irq(&sem->wait_lock);
+	} else {
+		adjustment = -RWSEM_ACTIVE_READ_BIAS;
+	}
+
+	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 +460,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

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

[Davidlohr Bueso]

On Wed, 22 Feb 2017, Waiman Long wrote:

>On a 2-socket 36-core 72-thread x86-64 E5-2699 v3 system, a rwsem
>microbenchmark was run with 36 locking threads (one/core) doing 100k
>reader and writer lock/unlock operations each, the resulting locking
>rates (avg of 3 runs) on a 4.10 kernel were 561.4 Mop/s and 588.8
>Mop/s without and with the patch respectively. That was an increase
>of about 5%.

iirc this patch is a repost, no? If so, did you get a chance to measure
single file access with direct io as dchinner suggested?

Thanks,
Davidlohr

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

[Waiman Long]

On 02/26/2017 01:58 PM, Davidlohr Bueso wrote:
> On Wed, 22 Feb 2017, Waiman Long wrote:
>
>> On a 2-socket 36-core 72-thread x86-64 E5-2699 v3 system, a rwsem
>> microbenchmark was run with 36 locking threads (one/core) doing 100k
>> reader and writer lock/unlock operations each, the resulting locking
>> rates (avg of 3 runs) on a 4.10 kernel were 561.4 Mop/s and 588.8
>> Mop/s without and with the patch respectively. That was an increase
>> of about 5%.
>
> iirc this patch is a repost, no? If so, did you get a chance to measure
> single file access with direct io as dchinner suggested?
>
> Thanks,
> Davidlohr

Yes, this patch is a derivative of part of the rwsem reader spinning
patch set that I posted before. The major change here in this patch is
from the unconditional spitting into 2 atomic adds to a conditional
spitting depending the on OSQ state and the ability to acquire the
wait_lock immediately without waiting. This should reduce the concern
that you have with the original patch. I will run a single-file direct
I/O test as well. 

Cheers,
Longman