locking/rwsem: Minor twists to improve rwsem performance
Waiman Long
reviewercover 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
Waiman Long
reviewerPATCH 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
@@ -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
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_listto 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 thewait_listis 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
Waiman Long
reviewerRe: [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_listto 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 thewait_listis 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
Waiman Long
reviewerPATCH 2/3 locking/rwsem: move down rwsem_down_read_failed()
In reply to Waiman LongMove 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
@@ -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
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
Waiman Long
reviewerRe: [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
Waiman Long
reviewerPATCH 3/3 locking/rwsem: Stop active read lock ASAP
In reply to Waiman LongCurrently, 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
@@ -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
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
Waiman Long
reviewerRe: [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