Skip to contentSkip to conversation

locking/rwsem: Minor twists to improve rwsem performance

PATCH Superseded Waiman Long 2 participants 10 messages Feb 22, 2017 – Feb 27, 2017 Locking primitives

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

cover locking/rwsem: Minor twists to improve rwsem performance

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(-)
Signature · 1 line
1.8.3.1
author reviewer
#1 lore raw

PATCH 1/3 locking/rwsem: Check wait_list without lock if spinner present

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

---
 kernel/locking/rwsem-xadd.c | 11 +++++++++++
 1 file changed, 11 insertions(+)
kernel/locking/rwsem-xadd.c +11 -0
index 34e727f..b5d7055 100644
@@ -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;
Signature · 1 line
1.8.3.1
#2 lore raw

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

Quoted 5 lines · 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.

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.

kernel/locking/rwsem-xadd.c struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) · line 621

Quoted 7 lines
kernel/locking/rwsem-xadd.c +7 -0
+		/*
+		 * 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

author reviewer
#3 lore raw

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

Quoted 8 lines · Davidlohr Bueso
Quoted 5 lines · 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.

Quoted 6 lines

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?

Quoted 10 lines

kernel/locking/rwsem-xadd.c struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) · line 621

Quoted 7 lines
kernel/locking/rwsem-xadd.c +7 -0
+        /*
+         * 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

author reviewer
#4 lore raw

PATCH 2/3 locking/rwsem: move down rwsem_down_read_failed()

In reply to 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.

---
 kernel/locking/rwsem-xadd.c | 96 ++++++++++++++++++++++-----------------------
 1 file changed, 48 insertions(+), 48 deletions(-)
kernel/locking/rwsem-xadd.c +48 -48
index b5d7055..fb6d6f3 100644
@@ -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 *
Signature · 1 line
1.8.3.1
#5 lore raw

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

Quoted 3 lines · 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.

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

author reviewer
#6 lore raw

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

Quoted 6 lines · Davidlohr Bueso
Quoted 3 lines · 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.

Quoted 6 lines

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

author reviewer
#7 lore raw

PATCH 3/3 locking/rwsem: Stop active read lock ASAP

In reply to 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%.

---
 kernel/locking/rwsem-xadd.c | 33 ++++++++++++++++++++++++++-------
 1 file changed, 26 insertions(+), 7 deletions(-)
kernel/locking/rwsem-xadd.c +26 -7
index fb6d6f3..6080afc 100644
@@ -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);
Signature · 1 line
1.8.3.1
#8 lore raw

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

Quoted 6 lines · Waiman Long

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

author reviewer
#9 lore raw

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

Quoted 9 lines · Davidlohr Bueso
Quoted 6 lines · Waiman Long

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

Quoted 5 lines

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