locking/rwsem: Rwsem rearchitecture part 2
Waiman Long
reviewerv2 cover locking/rwsem: Rwsem rearchitecture part 2
v2:
- Move the negative reader count checking patch (patch 12->10) forward to before the merge owner to count patch as suggested by Linus & expand the comment.
- Change the reader-owned rwsem spinning from count based to time based to have better control of the max time allowed.
This is part 2 of a 3-part (0/1/2) series to rearchitect the internal operation of rwsem.
part 0: merged into tip
part 1: https://lore.kernel.org/lkml/[email protected]/
This patchset revamps the current rwsem-xadd implementation to make it saner and easier to work with. It also implements the following 3 new features:
1) Waiter lock handoff
2) Reader optimistic spinning
3) Store write-lock owner in the atomic count (x86-64 only)
Waiter lock handoff is similar to the mechanism currently in the mutex code. This ensures that lock starvation won't happen.
Reader optimistic spinning enables readers to acquire the lock more quickly. So workloads that use a mix of readers and writers should see an increase in performance as long as the reader critical sections are short.
Finally, storing the write-lock owner into the count will allow optimistic spinners to get to the lock holder's task structure more quickly and eliminating the timing gap where the write lock is acquired but the owner isn't known yet. This is important for RT tasks where spinning on a lock with an unknown owner is not allowed.
Because of the fact that multiple readers can share the same lock, there is a natural preference for readers when measuring in term of locking throughput as more readers are likely to get into the locking fast path than the writers. With waiter lock handoff, we are not going to starve the writers.
On a 8-socket 120-core 240-thread IvyBridge-EX system with 120 reader and writer locking threads, the min/mean/max locking operations done in a 5-second testing window before the patchset were:
120 readers, Iterations Min/Mean/Max = 399/400/401 120 writers, Iterations Min/Mean/Max = 400/33,389/211,359
After the patchset, they became:
120 readers, Iterations Min/Mean/Max = 584/10,266/26,609 120 writers, Iterations Min/Mean/Max = 22,080/29,016/38,728
So it was much fairer to readers. With less locking threads, the readers were preferred than writers.
Patch 1 implements a new rwsem locking scheme similar to what qrwlock is current doing. Write lock is done by atomic_cmpxchg() while read lock is still being done by atomic_add().
Patch 2 implments lock handoff to prevent lock starvation.
Patch 3 removes rwsem_wake() wakeup optimization as it doesn't work with lock handoff.
Patch 4 makes rwsem_spin_on_owner() returns owner state.
Patch 5 disallows RT tasks to spin on a rwsem with unknown owner.
Patch 6 makes reader wakeup to wake almost all the readers in the wait queue instead of just those in the front.
Patch 7 enables reader to spin on a writer-owned rwsem.
Patch 8 enables a writer to spin on a reader-owned rwsem for at most 25us.
Patch 9 adds some new rwsem owner access helper functions.
Patch 10 handles the case of too many readers by reserving the sign bit to designate that a reader lock attempt will fail and the locking reader will be put to sleep. This will ensure that we will not overflow the reader count.
Patch 11 merges the write-lock owner task pointer into the count. Only 64-bit count has enough space to provide a reasonable number of bits for reader count. This is for x86-64 only for the time being.
Patch 12 eliminates redundant computation of the merged owner-count.
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBridge-EX system with equal numbers of readers and writers (mixed) before and after this patchset were:
# of Threads Before Patch After Patch
------------ ------------ -----------
2 1,179 9,436
4 1,505 8,268
8 721 7,041
16 575 7,652
32 70 2,189
64 39 534Waiman Long (12):
locking/rwsem: Implement a new locking scheme locking/rwsem: Implement lock handoff to prevent lock starvation locking/rwsem: Remove rwsem_wake() wakeup optimization locking/rwsem: Make rwsem_spin_on_owner() return owner state locking/rwsem: Ensure an RT task will not spin on reader locking/rwsem: Wake up almost all readers in wait queue locking/rwsem: Enable readers spinning on writer locking/rwsem: Enable time-based spinning on reader-owned rwsem locking/rwsem: Add more rwsem owner access helpers locking/rwsem: Guard against making count negative locking/rwsem: Merge owner into count on x86-64 locking/rwsem: Remove redundant computation of writer lock word
kernel/locking/lock_events_list.h | 4 + kernel/locking/rwsem-xadd.c | 635 +++++++++++++++++++----------- kernel/locking/rwsem.c | 3 +- kernel/locking/rwsem.h | 290 +++++++++++--- 4 files changed, 647 insertions(+), 285 deletions(-)
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 1/12 locking/rwsem: Implement a new locking scheme
The current way of using various reader, writer and waiting biases in the rwsem code are confusing and hard to understand. I have to reread the rwsem count guide in the rwsem-xadd.c file from time to time to remind myself how this whole thing works. It also makes the rwsem code harder to be optimized.
To make rwsem more sane, a new locking scheme similar to the one in qrwlock is now being used. The atomic long count has the following bit definitions:
Bit 0 - writer locked bit Bit 1 - waiters present bit
Bits 2-7 - reserved for future extension
Bits 8-X - reader count (24/56 bits)
The cmpxchg instruction is now used to acquire the write lock. The read lock is still acquired with xadd instruction, so there is no change here. This scheme will allow up to 16M/64P active readers which should be more than enough. We can always use some more reserved bits if necessary.
With that change, we can deterministically know if a rwsem has been write-locked. Looking at the count alone, however, one cannot determine for certain if a rwsem is owned by readers or not as the readers that set the reader count bits may be in the process of backing out. So we still need the reader-owned bit in the owner field to be sure.
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) of the benchmark on a 8-socket 120-core IvyBridge-EX system before and after the patch were as follows:
Before Patch After Patch
# of Threads wlock rlock wlock rlock
------------ ----- ----- ----- -----
1 30,659 31,341 31,055 31,283
2 8,909 16,457 9,884 17,659
4 9,028 15,823 8,933 20,233
8 8,410 14,212 7,230 17,140
16 8,217 25,240 7,479 24,607The locking rates of the benchmark on a Power8 system were as follows:
Before Patch After Patch
# of Threads wlock rlock wlock rlock
------------ ----- ----- ----- -----
1 12,963 13,647 13,275 13,601
2 7,570 11,569 7,902 10,829
4 5,232 5,516 5,466 5,435
8 5,233 3,386 5,467 3,168The locking rates of the benchmark on a 2-socket ARM64 system were as follows:
Before Patch After Patch
# of Threads wlock rlock wlock rlock
------------ ----- ----- ----- -----
1 21,495 21,046 21,524 21,074
2 5,293 10,502 5,333 10,504
4 5,325 11,463 5,358 11,631
8 5,391 11,712 5,470 11,680The performance are roughly the same before and after the patch. There are run-to-run variations in performance. Runs with higher variances usually have higher throughput.
--- kernel/locking/rwsem-xadd.c | 147 ++++++++++++------------------------ kernel/locking/rwsem.h | 74 +++++++++--------- 2 files changed, 86 insertions(+), 135 deletions(-)
kernel/locking/rwsem-xadd.c +49 -98
@@ -9,6 +9,8 @@* * Optimistic spinning by Tim Chen <[email protected]> * and Davidlohr Bueso <[email protected]>. Based on mutexes. +* +* Rwsem count bit fields re-definition by Waiman Long <[email protected]>. */ #include <linux/rwsem.h> #include <linux/init.h>
@@ -22,52 +24,20 @@#include "rwsem.h" /* -* Guide to the rw_semaphore's count field for common values. -* (32-bit case illustrated, similar for 64-bit) -* -* 0x0000000X (1) X readers active or attempting lock, no writer waiting -* X = #active_readers + #readers attempting to lock -* (X*ACTIVE_BIAS) -* -* 0x00000000 rwsem is unlocked, and no one is waiting for the lock or -* attempting to read lock or write lock. -* -* 0xffff000X (1) X readers active or attempting lock, with waiters for lock -* X = #active readers + # readers attempting lock -* (X*ACTIVE_BIAS + WAITING_BIAS) -* (2) 1 writer attempting lock, no waiters for lock -* X-1 = #active readers + #readers attempting lock -* ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS) -* (3) 1 writer active, no waiters for lock -* X-1 = #active readers + #readers attempting lock -* ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS) -* -* 0xffff0001 (1) 1 reader active or attempting lock, waiters for lock -* (WAITING_BIAS + ACTIVE_BIAS) -* (2) 1 writer active or attempting lock, no waiters for lock -* (ACTIVE_WRITE_BIAS) +* Guide to the rw_semaphore's count field. * -* 0xffff0000 (1) There are writers or readers queued but none active -* or in the process of attempting lock. -* (WAITING_BIAS) -* Note: writer can attempt to steal lock for this count by adding -* ACTIVE_WRITE_BIAS in cmpxchg and checking the old count +* When the RWSEM_WRITER_LOCKED bit in count is set, the lock is owned +* by a writer. * -* 0xfffe0001 (1) 1 writer active, or attempting lock. Waiters on queue. -* (ACTIVE_WRITE_BIAS + WAITING_BIAS) -* -* Note: Readers attempt to lock by adding ACTIVE_BIAS in down_read and checking -* the count becomes more than 0 for successful lock acquisition, -* i.e. the case where there are only readers or nobody has lock. -* (1st and 2nd case above). -* -* Writers attempt to lock by adding ACTIVE_WRITE_BIAS in down_write and -* checking the count becomes ACTIVE_WRITE_BIAS for successful lock -* acquisition (i.e. nobody else has lock or attempts lock). If -* unsuccessful, in rwsem_down_write_failed, we'll check to see if there -* are only waiters but none active (5th case above), and attempt to -* steal the lock. +* The lock is owned by readers when +* (1) the RWSEM_WRITER_LOCKED isn't set in count, +* (2) some of the reader bits are set in count, and +* (3) the owner field has RWSEM_READ_OWNED bit set. * +* Having some reader bits set is not enough to guarantee a readers owned +* lock as the readers may be in the process of backing out from the count +* and a writer has just released the lock. So another writer may steal +* the lock immediately after that. */ /*
@@ -113,9 +83,8 @@ enum rwsem_wake_type {/* * handle the lock release when processes blocked on it that can now run -* - if we come here from up_xxxx(), then: -* - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed) -* - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so) +* - if we come here from up_xxxx(), then the RWSEM_FLAG_WAITERS bit must +* have been set. * - there must be someone on the queue * - the wait_lock must be held by the caller * - tasks are marked for wakeup, the caller must later invoke wake_up_q()
@@ -159,22 +128,11 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,* so we can bail out early if a writer stole the lock. */ if (wake_type !=RWSEM_WAKE_READ_OWNED ) { - adjustment =RWSEM_ACTIVE_READ_BIAS ; - try_reader_grant: + adjustment =RWSEM_READER_BIAS ; oldcount =atomic_long_fetch_add (adjustment, &sem->count); -if (unlikely (oldcount <RWSEM_WAITING_BIAS )) { -/* -* If the count is still less than RWSEM_WAITING_BIAS -* after removing the adjustment, it is assumed that -* a writer has stolen the lock. We have to undo our -* reader grant. -*/ -if (atomic_long_add_return (-adjustment, &sem->count) < -RWSEM_WAITING_BIAS ) -return ; - -/* Last active locker left. Retry waking readers. */ - goto try_reader_grant; +if (unlikely (oldcount &RWSEM_WRITER_MASK )) { +atomic_long_sub (adjustment, &sem->count); +return ; }/* * Set it to reader-owned to give spinners an early
@@ -214,11 +172,11 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,wake_q_add_safe (wake_q, tsk); } - adjustment = woken *RWSEM_ACTIVE_READ_BIAS - adjustment; + adjustment = woken *RWSEM_READER_BIAS - adjustment;lockevent_cond_inc (rwsem_wake_reader, woken);if (list_empty (&sem->wait_list)) {/* hit end of list above */ - adjustment -=RWSEM_WAITING_BIAS ; + adjustment -=RWSEM_FLAG_WAITERS ; }if (adjustment)
@@ -232,22 +190,15 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,*/ static inline bool rwsem_try_write_lock (long count,struct rw_semaphore *sem) { -/* -* Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS. -*/ -if (count !=RWSEM_WAITING_BIAS ) +long new; + +if (RWSEM_COUNT_LOCKED (count))return false; -/* -* Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there -* are other tasks on the wait list, we need to add on WAITING_BIAS. -*/ - count =list_is_singular (&sem->wait_list) ? -RWSEM_ACTIVE_WRITE_BIAS : -RWSEM_ACTIVE_WRITE_BIAS +RWSEM_WAITING_BIAS ; + new = count +RWSEM_WRITER_LOCKED - + (list_is_singular (&sem->wait_list) ?RWSEM_FLAG_WAITERS :0 ); -if (atomic_long_cmpxchg_acquire (&sem->count,RWSEM_WAITING_BIAS , count) - ==RWSEM_WAITING_BIAS ) { +if (atomic_long_try_cmpxchg_acquire (&sem->count, &count, new)) {rwsem_set_owner (sem);return true; }
@@ -263,9 +214,9 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem) {long count =atomic_long_read (&sem->count); -while (!count || count ==RWSEM_WAITING_BIAS ) { +while (!RWSEM_COUNT_LOCKED (count)) {if (atomic_long_try_cmpxchg_acquire (&sem->count, &count, - count +RWSEM_ACTIVE_WRITE_BIAS )) { + count +RWSEM_WRITER_LOCKED )) {rwsem_set_owner (sem);lockevent_inc (rwsem_opt_wlock);return true;
@@ -422,7 +373,7 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem) static inline struct rw_semaphore __sched *__rwsem_down_read_failed_common (struct rw_semaphore *sem,int state) { -long count, adjustment = -RWSEM_ACTIVE_READ_BIAS ; +long count, adjustment = -RWSEM_READER_BIAS ;struct rwsem_waiter waiter;DEFINE_WAKE_Q (wake_q);
@@ -434,16 +385,16 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)/* * In case the wait queue is empty and the lock isn't owned * by a writer, this reader can exit the slowpath and return -* immediately as its RWSEM_ACTIVE_READ_BIAS has already -* been set in the count. +* immediately as its RWSEM_READER_BIAS has already been +* set in the count. */ -if (atomic_long_read (&sem->count) >=0 ) { +if (!(atomic_long_read (&sem->count) &RWSEM_WRITER_MASK )) {raw_spin_unlock_irq (&sem->wait_lock);rwsem_set_reader_owned (sem);lockevent_inc (rwsem_rlock_fast);return sem; } - adjustment +=RWSEM_WAITING_BIAS ; + adjustment +=RWSEM_FLAG_WAITERS ; }list_add_tail (&waiter.list, &sem->wait_list);
@@ -456,9 +407,8 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)* 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 )) +if (!RWSEM_COUNT_LOCKED (count) || + (!(count &RWSEM_WRITER_MASK ) && (adjustment &RWSEM_FLAG_WAITERS )))__rwsem_mark_wake (sem,RWSEM_WAKE_ANY , &wake_q);raw_spin_unlock_irq (&sem->wait_lock);
@@ -486,7 +436,7 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state) out_nolock:list_del (&waiter.list);if (list_empty (&sem->wait_list)) -atomic_long_add (-RWSEM_WAITING_BIAS , &sem->count); +atomic_long_andnot (RWSEM_FLAG_WAITERS , &sem->count);raw_spin_unlock_irq (&sem->wait_lock);__set_current_state (TASK_RUNNING );lockevent_inc (rwsem_rlock_fail);
@@ -519,9 +469,6 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)struct rw_semaphore *ret = sem;DEFINE_WAKE_Q (wake_q); -/* undo write bias from down_write operation, stop active locking */ - count =atomic_long_sub_return (RWSEM_ACTIVE_WRITE_BIAS , &sem->count); -/* do optimistic spinning and steal lock if possible */ if (rwsem_optimistic_spin (sem))return sem;
@@ -541,16 +488,18 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)list_add_tail (&waiter.list, &sem->wait_list); -/* we're now waiting on the lock, but no longer actively locking */ +/* we're now waiting on the lock */ if (waiting) { count =atomic_long_read (&sem->count);/* * If there were already threads queued before us and there are -* no active writers, the lock must be read owned; so we try to -* wake any read locks that were queued ahead of us. +* no active writers and some readers, the lock must be read +* owned; so we try to any read locks that were queued ahead +* of us. */ -if (count >RWSEM_WAITING_BIAS ) { +if (!(count &RWSEM_WRITER_MASK ) && + (count &RWSEM_READER_MASK )) {__rwsem_mark_wake (sem,RWSEM_WAKE_READERS , &wake_q);/* * The wakeup is normally called _after_ the wait_lock
@@ -567,8 +516,9 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)wake_q_init (&wake_q); } - }else - count =atomic_long_add_return (RWSEM_WAITING_BIAS , &sem->count); + }else { + count =atomic_long_add_return (RWSEM_FLAG_WAITERS , &sem->count); + }/* wait until we successfully acquire the lock */ set_current_state (state);
@@ -585,7 +535,8 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)schedule ();lockevent_inc (rwsem_sleep_writer);set_current_state (state); - }while ((count =atomic_long_read (&sem->count)) &RWSEM_ACTIVE_MASK ); + count =atomic_long_read (&sem->count); + }while (RWSEM_COUNT_LOCKED (count));raw_spin_lock_irq (&sem->wait_lock); }
@@ -601,7 +552,7 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)raw_spin_lock_irq (&sem->wait_lock);list_del (&waiter.list);if (list_empty (&sem->wait_list)) -atomic_long_add (-RWSEM_WAITING_BIAS , &sem->count); +atomic_long_andnot (RWSEM_FLAG_WAITERS , &sem->count);else __rwsem_mark_wake (sem,RWSEM_WAKE_ANY , &wake_q);raw_spin_unlock_irq (&sem->wait_lock);
kernel/locking/rwsem.h +37 -37
139 lines not on this page · raw message
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 2/12 locking/rwsem: Implement lock handoff to prevent lock starvation
In reply to Waiman LongBecause of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.
The mutex code has a lock handoff mechanism to prevent lock starvation. This patch implements a similar lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter in the queue after at least a 5ms waiting period. The waiting period is used to avoid discouraging lock stealing too much to affect performance.
A rwsem microbenchmark was run for 5 seconds on a 8-socket 120-core 240-thread IvyBridge-EX system with a v5.1 based kernel and 240 write_lock threads with 5us sleep critical section.
Before the patch, the min/mean/max numbers of locking operations for the locking threads were 1/2,433/320,955. After the patch, the figures became 891/1,807/3,174. It can be seen that the rwsem became much more fair, though there was a drop of about 26% in the mean locking operations done which was a tradeoff of having better fairness.
--- kernel/locking/lock_events_list.h | 2 + kernel/locking/rwsem-xadd.c | 154 ++++++++++++++++++++++-------- kernel/locking/rwsem.h | 23 +++-- 3 files changed, 134 insertions(+), 45 deletions(-)
kernel/locking/lock_events_list.h +2 -0
@@ -61,7 +61,9 @@ LOCK_EVENT(rwsem_opt_fail) /* # of failed opt-spinnings */ LOCK_EVENT(rwsem_rlock) /* # of read locks acquired */ LOCK_EVENT(rwsem_rlock_fast) /* # of fast read locks acquired */ LOCK_EVENT(rwsem_rlock_fail) /* # of failed read lock acquisitions */ +LOCK_EVENT(rwsem_rlock_handoff) /* # of read lock handoffs */ LOCK_EVENT(rwsem_rtrylock) /* # of read trylock calls */ LOCK_EVENT(rwsem_wlock) /* # of write locks acquired */ LOCK_EVENT(rwsem_wlock_fail) /* # of failed write lock acquisitions */ +LOCK_EVENT(rwsem_wlock_handoff) /* # of write lock handoffs */ LOCK_EVENT(rwsem_wtrylock) /* # of write trylock calls */
kernel/locking/rwsem-xadd.c +116 -38
288 lines not on this page · raw message
kernel/locking/rwsem.h +16 -7
@@ -45,7 +45,8 @@* * Bit 0 - writer locked bit * Bit 1 - waiters present bit -* Bits 2-7 - reserved +* Bit 2 - lock handoff bit +* Bits 3-7 - reserved * Bits 8-X - 24-bit (32-bit) or 56-bit reader count * * atomic_long_fetch_add() is used to obtain reader lock, whereas
@@ -53,14 +54,20 @@*/ #define RWSEM_WRITER_LOCKED (1UL << 0)#define RWSEM_FLAG_WAITERS (1UL << 1) +#define RWSEM_FLAG_HANDOFF (1UL << 2) +#define RWSEM_READER_SHIFT 8#define RWSEM_READER_BIAS (1UL << RWSEM_READER_SHIFT)#define RWSEM_READER_MASK (~(RWSEM_READER_BIAS - 1))#define RWSEM_WRITER_MASK RWSEM_WRITER_LOCKED#define RWSEM_LOCK_MASK (RWSEM_WRITER_MASK|RWSEM_READER_MASK) -#define RWSEM_READ_FAILED_MASK (RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS) +#define RWSEM_READ_FAILED_MASK (RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS|\ + RWSEM_FLAG_HANDOFF)#define RWSEM_COUNT_LOCKED (c) ((c) & RWSEM_LOCK_MASK) +#define RWSEM_COUNT_HANDOFF (c) ((c) & RWSEM_FLAG_HANDOFF) +#define RWSEM_COUNT_LOCKED_OR_HANDOFF (c) \ + ((c) & (RWSEM_LOCK_MASK|RWSEM_FLAG_HANDOFF))#ifdef CONFIG_RWSEM_SPIN_ON_OWNER /*
@@ -167,7 +174,7 @@ extern struct rw_semaphore *rwsem_down_read_failed(struct rw_semaphore *sem);extern struct rw_semaphore *rwsem_down_read_failed_killable (struct rw_semaphore *sem);extern struct rw_semaphore *rwsem_down_write_failed (struct rw_semaphore *sem);extern struct rw_semaphore *rwsem_down_write_failed_killable (struct rw_semaphore *sem); -extern struct rw_semaphore *rwsem_wake (struct rw_semaphore *sem); +extern struct rw_semaphore *rwsem_wake (struct rw_semaphore *sem,long count);extern struct rw_semaphore *rwsem_downgrade_wake (struct rw_semaphore *sem);/*
@@ -265,7 +272,7 @@ static inline void __up_read(struct rw_semaphore *sem) tmp =atomic_long_add_return_release (-RWSEM_READER_BIAS , &sem->count);if (unlikely ((tmp & (RWSEM_LOCK_MASK |RWSEM_FLAG_WAITERS )) ==RWSEM_FLAG_WAITERS )) -rwsem_wake (sem); +rwsem_wake (sem, tmp); }/*
@@ -273,11 +280,13 @@ static inline void __up_read(struct rw_semaphore *sem)*/ static inline void __up_write (struct rw_semaphore *sem) { +long tmp; +DEBUG_RWSEMS_WARN_ON (sem->owner != current, sem);rwsem_clear_owner (sem); -if (unlikely (atomic_long_fetch_add_release (-RWSEM_WRITER_LOCKED , - &sem->count) &RWSEM_FLAG_WAITERS )) -rwsem_wake (sem); + tmp =atomic_long_fetch_add_release (-RWSEM_WRITER_LOCKED , &sem->count); +if (unlikely (tmp &RWSEM_FLAG_WAITERS )) +rwsem_wake (sem, tmp); }/*
Signature · 1 line
2.18.1
Peter Zijlstra
maintainerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
Quoted 9 lines · Waiman Long
Because of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.
The mutex code has a lock handoff mechanism to prevent lock starvation. This patch implements a similar lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter in the queue after at least a 5ms waiting period. The waiting period is used to avoid discouraging lock stealing too much to affect performance.
So the mutex code doesn't have that timeout, it foces the handoff if the top waiter fails to acquire.
I don't find the above sufficiently justifies the additional complexity. What were the numbers with the simple scheme vs this etc..
Waiman Long
reviewerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Waiman Long
Because of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.
The mutex code has a lock handoff mechanism to prevent lock starvation. This patch implements a similar lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter in the queue after at least a 5ms waiting period. The waiting period is used to avoid discouraging lock stealing too much to affect performance.
Quoted 5 lines
So the mutex code doesn't have that timeout, it foces the handoff if the top waiter fails to acquire.
I don't find the above sufficiently justifies the additional complexity. What were the numbers with the simple scheme vs this etc..
When the handoff bit is set, it stops the lock from being acquired by anyone else until the front waiter is woken up, scheduled and take the lock. Doing that too frequently will impede the throughput when the rwsem is highly contended. I can ran some performance test to show the difference it can make.
I have also been thinking about having the front waiter set the handoff bit and then spin on owner so that it can acquire the lock immediately after it is freed. It will be a follow up patch.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
In reply to Waiman LongQuoted 1 line · Waiman Long
+#define
RWSEM_WAIT_TIMEOUT((HZ - 1)/200 + 1)
Given the choices in HZ, the above seems fairly 'optimistic'.
Waiman Long
reviewerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
Quoted 3 lines · Peter Zijlstra
Quoted 1 line · Waiman Long
+#define
RWSEM_WAIT_TIMEOUT((HZ - 1)/200 + 1)Given the choices in HZ, the above seems fairly 'optimistic'.
I can tighten it up and make it less "optimistic" :-)
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
In reply to Waiman LongQuoted 9 lines · Waiman Long
Because of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.
The mutex code has a lock handoff mechanism to prevent lock starvation. This patch implements a similar lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter in the queue after at least a 5ms waiting period. The waiting period is used to avoid discouraging lock stealing too much to affect performance.
I would say the handoff it not at all similar to the mutex code. It is in fact radically different.
Quoted 6 lines
kernel/locking/rwsem-xadd.c +2
-0@@ -131,6 +138,15 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem, adjustment =RWSEM_READER_BIAS ; oldcount =atomic_long_fetch_add (adjustment, &sem->count);if (unlikely (oldcount &RWSEM_WRITER_MASK )) { +/* +* Initiate handoff to reader, if applicable.
kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem, · line 152
Quoted 10 lines
kernel/locking/rwsem-xadd.c +7
-0+*/ +if (!(oldcount &RWSEM_FLAG_HANDOFF ) && +time_after (jiffies, waiter->timeout)) { + adjustment -=RWSEM_FLAG_HANDOFF ; +lockevent_inc (rwsem_rlock_handoff); + } +atomic_long_sub (adjustment, &sem->count);return ; }
That confuses the heck out of me...
The above seems to rely on __rwsem_mark_wake() to be fully serialized (and it is, by ->wait_lock, but that isn't spelled out anywhere) such that we don't get double increment of FLAG_HANDOFF.
So there is NO __rwsem_mark_wake() vs __wesem_mark_wake() race like:
CPU0 CPU1
oldcount = atomic_long_fetch_add(adjustment, &sem->count)
oldcount = atomic_long_fetch_add(adjustment, &sem->count)
if (!(oldcount & HANDOFF))
adjustment -= HANDOFF;if (!(oldcount & HANDOFF)) adjustment -= HANDOFF;
atomic_long_sub(adjustment)
atomic_long_sub(adjustment)
*whoops* double negative decrement of HANDOFF (aka double increment).
However there is another site that fiddles with the HANDOFF bit, namely __rwsem_down_write_failed_common(), and that does:
+ atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);
_OUTSIDE_ of ->wait_lock, which would yield:
CPU0 CPU1
oldcount = atomic_long_fetch_add(adjustment, &sem->count)
atomic_long_or(HANDOFF)
if (!(oldcount & HANDOFF))
adjustment -= HANDOFF; atomic_long_sub(adjustment)
*whoops*, incremented HANDOFF on HANDOFF.
And there's not a comment in sight that would elucidate if this is possible or not.
Also:
+ atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);
+ first++;
+
+ /*
+ * Make sure the handoff bit is seen by + * others before proceeding. + */
+ smp_mb__after_atomic();
That comment is utter nonsense. smp_mb() doesn't (and cannot) 'make visible'. There needs to be order between two memops on both sides.
Waiman Long
reviewerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
Quoted 5 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long
Because of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.
Quoted 8 lines
Quoted 5 lines
The mutex code has a lock handoff mechanism to prevent lock starvation. This patch implements a similar lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter in the queue after at least a 5ms waiting period. The waiting period is used to avoid discouraging lock stealing too much to affect performance.
I would say the handoff it not at all similar to the mutex code. It is in fact radically different.
I mean they are similar in concept. Of course, the implementations are quite different.
Quoted 33 lines
Quoted 6 lines
kernel/locking/rwsem-xadd.c +2
-0@@ -131,6 +138,15 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem, adjustment =RWSEM_READER_BIAS ; oldcount =atomic_long_fetch_add (adjustment, &sem->count);if (unlikely (oldcount &RWSEM_WRITER_MASK )) { +/* +* Initiate handoff to reader, if applicable. kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem, · line 152
Quoted 10 lines
kernel/locking/rwsem-xadd.c +7
-0+*/ +if (!(oldcount &RWSEM_FLAG_HANDOFF ) && +time_after (jiffies, waiter->timeout)) { + adjustment -=RWSEM_FLAG_HANDOFF ; +lockevent_inc (rwsem_rlock_handoff); + } +atomic_long_sub (adjustment, &sem->count);return ; }That confuses the heck out of me...
The above seems to rely on
__rwsem_mark_wake()to be fully serialized (and it is, by ->wait_lock, but that isn't spelled out anywhere) such that we don't get double increment ofFLAG_HANDOFF.So there is NO
__rwsem_mark_wake()vs__wesem_mark_wake()race like:CPU0 CPU1
oldcount =
atomic_long_fetch_add(adjustment, &sem->count)oldcount = atomic_long_fetch_add(adjustment, &sem->count)if (!(oldcount & HANDOFF)) adjustment -= HANDOFF;
Quoted 7 lines
if (!(oldcount & HANDOFF)) adjustment -= HANDOFF;
atomic_long_sub(adjustment)
atomic_long_sub(adjustment)*whoops* double negative decrement of HANDOFF (aka double increment).
Yes, __rwsem_mark_wake() is always called with wait_lock held. I can add a lockdep_assert() statement to clarify this point.
Quoted 17 lines
However there is another site that fiddles with the HANDOFF bit, namely
__rwsem_down_write_failed_common(), and that does:+
atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);_OUTSIDE_ of ->wait_lock, which would yield:
CPU0 CPU1
oldcount =
atomic_long_fetch_add(adjustment, &sem->count)
atomic_long_or(HANDOFF)if (!(oldcount & HANDOFF)) adjustment -= HANDOFF;
Quoted 8 lines
atomic_long_sub(adjustment)*whoops*, incremented HANDOFF on HANDOFF.
And there's not a comment in sight that would elucidate if this is possible or not.
A writer can only set the handoff bit if it is the first waiter in the queue. If it is the first waiter, a racing __rwsem_mark_wake() will see that the first waiter is a writer and so won't go into the reader path. I know I something don't spell out all the conditions that may look obvious to me but not to others. I will elaborate more in comments.
Quoted 11 lines
Also:
kernel/locking/rwsem-xadd.c +8
-0+atomic_long_or (RWSEM_FLAG_HANDOFF , &sem->count); + first++; + +/* +* Make sure the handoff bit is seen by +* others before proceeding. +*/ +smp_mb__after_atomic ();
Quoted 3 lines
That comment is utter nonsense.
smp_mb()doesn't (and cannot) 'make visible'. There needs to be order between two memops on both sides.
I kind of add that for safety. I will take some time to rethink if it is really necessary.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH-tip v2 02/12] locking/rwsem: Implement lock handoff to prevent lock starvation
Quoted 27 lines · Waiman Long
Quoted 16 lines · Peter Zijlstra
However there is another site that fiddles with the HANDOFF bit, namely
__rwsem_down_write_failed_common(), and that does:+
atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);_OUTSIDE_ of ->wait_lock, which would yield:
CPU0 CPU1
oldcount =
atomic_long_fetch_add(adjustment, &sem->count)
atomic_long_or(HANDOFF)if (!(oldcount & HANDOFF)) adjustment -= HANDOFF;Quoted 8 lines
atomic_long_sub(adjustment)*whoops*, incremented HANDOFF on HANDOFF.
And there's not a comment in sight that would elucidate if this is possible or not.
Quoted 5 lines
A writer can only set the handoff bit if it is the first waiter in the queue. If it is the first waiter, a racing
__rwsem_mark_wake()will see that the first waiter is a writer and so won't go into the reader path. I know I something don't spell out all the conditions that may look obvious to me but not to others. I will elaborate more in comments.
Aah, indeed.
Waiman Long
reviewerPATCH v2 3/12 locking/rwsem: Remove rwsem_wake() wakeup optimization
In reply to Waiman LongWith the commit 59aabfc7e959 ("locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()"), the rwsem_wake() forgoes doing a wakeup if the wait_lock cannot be directly acquired and an optimistic spinning locker is present. This can help performance by avoiding spinning on the wait_lock when it is contended.
With the later commit 133e89ef5ef3 ("locking/rwsem: Enable lockless waiter wakeup(s)"), the performance advantage of the above optimization diminishes as the average wait_lock hold time become much shorter.
By supporting rwsem lock handoff, we can no longer relies on the fact that the presence of an optimistic spinning locker will ensure that the lock will be acquired by a task soon. This can lead to missed wakeup and application hang. So the commit 59aabfc7e959 ("locking/rwsem:
Reduce spinlock contention in wakeup after up_read()/up_write()") will have to be reverted.
--- kernel/locking/rwsem-xadd.c | 74 ------------------------------------- 1 file changed, 74 deletions(-)
kernel/locking/rwsem-xadd.c +0 -74
@@ -372,25 +372,11 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)lockevent_cond_inc (rwsem_opt_fail, !taken); return taken; } - -/* -* Return true if the rwsem has active spinner -*/ -static inline bool rwsem_has_spinner (struct rw_semaphore *sem) -{ -return osq_is_locked (&sem->osq); -} -#else static bool rwsem_optimistic_spin (struct rw_semaphore *sem) {return false; } - -static inline bool rwsem_has_spinner (struct rw_semaphore *sem) -{ -return false; -}#endif /*
@@ -662,67 +648,7 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem, long count)unsigned long flags;DEFINE_WAKE_Q (wake_q); -/* -* __rwsem_down_write_failed_common(sem) -* rwsem_optimistic_spin(sem) -* osq_unlock(sem->osq) -* ... -* atomic_long_add_return(&sem->count) -* -* - VS - -* -* __up_write() -* if (atomic_long_sub_return_release(&sem->count) < 0) -* rwsem_wake(sem) -* osq_is_locked(&sem->osq) -* -* And __up_write() must observe !osq_is_locked() when it observes the -* atomic_long_add_return() in order to not miss a wakeup. -* -* This boils down to: -* -* [S.rel] X = 1 [RmW] r0 = (Y += 0) -* MB RMB -* [RmW] Y += 1 [L] r1 = X -* -* exists (r0=1 /\ r1=0) -*/ -smp_rmb (); - -/* -* If a spinner is present and the handoff flag isn't set, it is -* not necessary to do the wakeup. -* -* Try to do wakeup only if the trylock succeeds to minimize -* spinlock contention which may introduce too much delay in the -* unlock operation. -* -* spinning writer up_write/up_read caller -* --------------- ----------------------- -* [S] osq_unlock() [L] osq -* MB RMB -* [RmW] rwsem_try_write_lock() [RmW] spin_trylock(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 -* to sleep without taking the rwsem. Even when the spinning writer -* is just going to break out of the waiting loop, it will still do -* a trylock in rwsem_down_write_failed() before sleeping. IOW, if -* rwsem_has_spinner() is true, it will guarantee at least one -* trylock attempt on the rwsem later on. -*/ -if (rwsem_has_spinner (sem) && !RWSEM_COUNT_HANDOFF (count)) { -/* -* The smp_rmb() here is to make sure that the spinner -* state is consulted before reading the wait_lock. -*/ -smp_rmb (); -if (!raw_spin_trylock_irqsave (&sem->wait_lock, flags)) -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);
Signature · 1 line
2.18.1
Re: [PATCH-tip v2 03/12] locking/rwsem: Remove rwsem_wake() wakeup optimization
Quoted 17 lines · Waiman Long
With the commit
59aabfc7e959("locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()"), therwsem_wake()forgoes doing a wakeup if thewait_lockcannot be directly acquired and an optimistic spinning locker is present. This can help performance by avoiding spinning on thewait_lockwhen it is contended.With the later commit
133e89ef5ef3("locking/rwsem: Enable lockless waiter wakeup(s)"), the performance advantage of the above optimization diminishes as the averagewait_lockhold time become much shorter.By supporting rwsem lock handoff, we can no longer relies on the fact that the presence of an optimistic spinning locker will ensure that the lock will be acquired by a task soon. This can lead to missed wakeup and application hang. So the commit
59aabfc7e959("locking/rwsem:
Reduce spinlock contention in wakeup after up_read()/up_write()") will have to be reverted.
Quoted 3 lines
Signed-off-by Waiman Long <[email protected]>---
kernel/locking/rwsem-xadd.c| 74 -------------------------------------
I very much like removing this code. It was rather crazy.
Waiman Long
reviewerPATCH v2 4/12 locking/rwsem: Make rwsem_spin_on_owner() return owner state
In reply to Waiman LongThis patch modifies rwsem_spin_on_owner() to return four possible values to better reflect the state of lock holder which enables us to make a better decision of what to do next.
In the special case that there is no active lock and the handoff bit is set, optimistic spinning has to be stopped.
--- kernel/locking/rwsem-xadd.c | 40 ++++++++++++++++++++++++++++++------- kernel/locking/rwsem.h | 5 +++++ 2 files changed, 38 insertions(+), 7 deletions(-)
kernel/locking/rwsem-xadd.c +33 -7
@@ -281,14 +281,30 @@ static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem) }/* -* Return true only if we can still spin on the owner field of the rwsem. +* Return the folowing 4 values depending on the lock owner state. +* OWNER_NULL : owner is currently NULL +* OWNER_WRITER: when owner changes and is a writer +* OWNER_READER: when owner changes and the new owner may be a reader. +* OWNER_NONSPINNABLE: +* when optimistic spinning has to stop because either the +* owner stops running, is unknown, or its timeslice has +* been used up. */ -static noinline bool rwsem_spin_on_owner(struct rw_semaphore *sem) +enum owner_state { +OWNER_NULL =1 <<0 , +OWNER_WRITER =1 <<1 , +OWNER_READER =1 <<2 , +OWNER_NONSPINNABLE =1 <<3 , +}; +#define OWNER_SPINNABLE (OWNER_NULL | OWNER_WRITER) + +static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem) {struct task_struct *owner =READ_ONCE (sem->owner); +long count;if (!is_rwsem_owner_spinnable (owner)) -return false; +return OWNER_NONSPINNABLE ;rcu_read_lock ();while (owner && (READ_ONCE (sem->owner) == owner)) {
@@ -306,7 +322,7 @@ static noinline bool rwsem_spin_on_owner(struct rw_semaphore *sem)*/ if (need_resched () || !owner_on_cpu (owner)) {rcu_read_unlock (); -return false; +return OWNER_NONSPINNABLE ; }cpu_relax ();
@@ -315,9 +331,19 @@ static noinline bool rwsem_spin_on_owner(struct rw_semaphore *sem)/* * If there is a new owner or the owner is not set, we continue -* spinning. +* spinning except when here is no active locks and the handoff bit +* is set. In this case, we have to stop spinning. */ -return is_rwsem_owner_spinnable (READ_ONCE (sem->owner)); + owner =READ_ONCE (sem->owner); +if (!is_rwsem_owner_spinnable (owner)) +return OWNER_NONSPINNABLE ; +if (owner && !is_rwsem_owner_reader (owner)) +return OWNER_WRITER ; + + count =atomic_long_read (&sem->count); +if (RWSEM_COUNT_HANDOFF (count) && !RWSEM_COUNT_LOCKED (count)) +return OWNER_NONSPINNABLE ; +return !owner ?OWNER_NULL :OWNER_READER ; }static bool rwsem_optimistic_spin (struct rw_semaphore *sem)
@@ -340,7 +366,7 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)* 2) readers own the lock as we can't determine if they are * actively running or not. */ -while (rwsem_spin_on_owner (sem)) { +while (rwsem_spin_on_owner (sem) &OWNER_SPINNABLE ) {/* * Try to acquire the lock */
kernel/locking/rwsem.h +5 -0
@@ -119,6 +119,11 @@ static inline bool is_rwsem_owner_spinnable(struct task_struct *owner)return !((unsigned long )owner &RWSEM_ANONYMOUSLY_OWNED ); } +static inline bool is_rwsem_owner_reader (struct task_struct *owner) +{ +return (unsigned long )owner &RWSEM_READER_OWNED ; +} +/* * Return true if rwsem is owned by an anonymous writer or readers. */
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 5/12 locking/rwsem: Ensure an RT task will not spin on reader
In reply to Waiman LongAn RT task can do optimistic spinning only if the lock holder is actually running. If the state of the lock holder isn't known, there is a possibility that high priority of the RT task may block forward progress of the lock holder if it happens to reside on the same CPU. This will lead to deadlock. So we have to make sure that an RT task will not spin on a reader-owned rwsem.
When the owner is temporarily set to NULL, it is more tricky to decide if an RT task should stop spinning as it may be a temporary state where another writer may have just stolen the lock which then failed the task's trylock attempt. So one more retry is allowed to make sure that the lock is not spinnable by an RT task.
When testing on a 8-socket IvyBridge-EX system, the one additional retry seems to improve locking performance of RT write locking threads under heavy contentions. The table below shows the locking rates (in kops/s) with various write locking threads before and after the patch.
Locking threads Pre-patch Post-patch
--------------- --------- -----------
4 2,753 2,608
8 2,529 2,520
16 1,727 1,918
32 1,263 1,956
64 889 1,343--- kernel/locking/rwsem-xadd.c | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-)
kernel/locking/rwsem-xadd.c +29 -7
@@ -349,6 +349,8 @@ static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem)static bool rwsem_optimistic_spin (struct rw_semaphore *sem) {bool taken = false; +bool is_rt_task =rt_task (current); +int prev_owner_state =OWNER_NULL ;preempt_disable ();
@@ -366,7 +368,12 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)* 2) readers own the lock as we can't determine if they are * actively running or not. */ -while (rwsem_spin_on_owner (sem) &OWNER_SPINNABLE ) { +for (;;) { +enum owner_state owner_state =rwsem_spin_on_owner (sem); + +if (!(owner_state &OWNER_SPINNABLE )) +break ; +/* * Try to acquire the lock */
@@ -376,13 +383,28 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem) }/* -* When there's no owner, we might have preempted between the -* owner acquiring the lock and setting the owner field. If -* we're an RT task that will live-lock because we won't let -* the owner complete. +* An RT task cannot do optimistic spinning if it cannot +* be sure the lock holder is running or live-lock may +* happen if the current task and the lock holder happen +* to run in the same CPU. +* +* When there's no owner or is reader-owned, an RT task +* will stop spinning if the owner state is not a writer +* at the previous iteration of the loop. This allows the +* RT task to recheck if the task that steals the lock is +* a spinnable writer. If so, it can keeps on spinning. +* +* If the owner is a writer, the need_resched() check is +* done inside rwsem_spin_on_owner(). If the owner is not +* a writer, need_resched() check needs to be done here. */ -if (!sem->owner && (need_resched () ||rt_task (current))) -break ; +if (owner_state !=OWNER_WRITER ) { +if (need_resched ()) +break ; +if (is_rt_task && (prev_owner_state !=OWNER_WRITER )) +break ; + } + prev_owner_state = owner_state;/* * The cpu_relax() call is a compiler barrier which forces
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 6/12 locking/rwsem: Wake up almost all readers in wait queue
In reply to Waiman LongWhen the front of the wait queue is a reader, other readers immediately following the first reader will also be woken up at the same time. However, if there is a writer in between. Those readers behind the writer will not be woken up.
Because of optimistic spinning, the lock acquisition order is not FIFO anyway. The lock handoff mechanism will ensure that lock starvation will not happen.
Assuming that the lock hold times of the other readers still in the queue will be about the same as the readers that are being woken up, there is really not much additional cost other than the additional latency due to the wakeup of additional tasks by the waker. Therefore all the readers up to a maximum of 256 in the queue are woken up when the first waiter is a reader to improve reader throughput.
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBridge-EX system with equal numbers of readers and writers before and after this patch were as follows:
# of Threads Pre-Patch Post-patch
------------ --------- ----------
4 1,641 1,674
8 731 1,062
16 564 924
32 78 300
64 38 195
240 50 149There is no performance gain at low contention level. At high contention level, however, this patch gives a pretty decent performance boost.
--- kernel/locking/rwsem-xadd.c | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-)
kernel/locking/rwsem-xadd.c +17 -4
@@ -88,6 +88,13 @@ enum rwsem_wake_type {*/ #define RWSEM_WAIT_TIMEOUT ((HZ - 1)/200 + 1) +/* +* We limit the maximum number of readers that can be woken up for a +* wake-up call to not penalizing the waking thread for spending too +* much time doing it. +*/ +#define MAX_READERS_WAKEUP 0x100 +/* * handle the lock release when processes blocked on it that can now run * - if we come here from up_xxxx(), then the RWSEM_FLAG_WAITERS bit must
@@ -158,16 +165,16 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem, }/* -* Grant an infinite number of read locks to the readers at the front -* of the queue. We know that woken will be at least 1 as we accounted -* for above. Note we increment the 'active part' of the count by the +* Grant up to MAX_READERS_WAKEUP read locks to all the readers in the +* queue. We know that woken will be at least 1 as we accounted for +* above. Note we increment the 'active part' of the count by the * number of readers before waking any processes up. */ list_for_each_entry_safe (waiter, tmp, &sem->wait_list, list) {struct task_struct *tsk;if (waiter->type ==RWSEM_WAITING_FOR_WRITE ) -break ; +continue ; woken++; tsk = waiter->task;
@@ -186,6 +193,12 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,* after setting the reader waiter to nil. */ wake_q_add_safe (wake_q, tsk); + +/* +* Limit # of readers that can be woken up per wakeup call. +*/ +if (woken >=MAX_READERS_WAKEUP ) +break ; } adjustment = woken *RWSEM_READER_BIAS - adjustment;
Signature · 1 line
2.18.1
Re: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
Quoted 9 lines · Waiman Long
When the front of the wait queue is a reader, other readers immediately following the first reader will also be woken up at the same time. However, if there is a writer in between. Those readers behind the writer will not be woken up.
Because of optimistic spinning, the lock acquisition order is not FIFO anyway. The lock handoff mechanism will ensure that lock starvation will not happen.
Quoted 6 lines
Assuming that the lock hold times of the other readers still in the queue will be about the same as the readers that are being woken up, there is really not much additional cost other than the additional latency due to the wakeup of additional tasks by the waker. Therefore all the readers up to a maximum of 256 in the queue are woken up when the first waiter is a reader to improve reader throughput.
Before we stopped waking readers when a writer was encountered but would otherwise wakeup _all_ readers. I don't understand why you want to limit this to MAX_READERS_WAKEUP, otherwise I agree it's nice to skip the writer and continue waking readers in the queue (with the handoff guarantees obviously).
Would it not be better to do the MAX_READERS_WAKEUP limit only when a writer is found?
Thanks,
Davidlohr
Waiman Long
reviewerRe: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
Quoted 25 lines · Davidlohr Bueso
Quoted 9 lines · Waiman Long
When the front of the wait queue is a reader, other readers immediately following the first reader will also be woken up at the same time. However, if there is a writer in between. Those readers behind the writer will not be woken up.
Because of optimistic spinning, the lock acquisition order is not FIFO anyway. The lock handoff mechanism will ensure that lock starvation will not happen.
Quoted 6 lines
Assuming that the lock hold times of the other readers still in the queue will be about the same as the readers that are being woken up, there is really not much additional cost other than the additional latency due to the wakeup of additional tasks by the waker. Therefore all the readers up to a maximum of 256 in the queue are woken up when the first waiter is a reader to improve reader throughput.
Before we stopped waking readers when a writer was encountered but would otherwise wakeup _all_ readers. I don't understand why you want to limit this to
MAX_READERS_WAKEUP, otherwise I agree it's nice to skip the writer and continue waking readers in the queue (with the handoff
guarantees obviously).
Quoted 5 lines
Would it not be better to do the
MAX_READERS_WAKEUPlimit only when a writer is found?Thanks,
Davidlohr
There are 2 major reasons why there is a limit.
1) It will be unfair to the task that needs to spend so much of its own CPU time to wake up too many readers.
2) I want to avoid the extreme case that there are more than 32k readers in the wait queue and make the count overflow.
Cheers,
Longman
Re: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
Quoted 4 lines · Waiman Long
There are 2 major reasons why there is a limit.
1) It will be unfair to the task that needs to spend so much of its own CPU time to wake up too many readers.
This has never been a problem before.
Quoted 2 lines
2) I want to avoid the extreme case that there are more than 32k readers in the wait queue and make the count overflow.
But in this case the readers are already on the queue.
Thanks,
Davidlohr
Re: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
Quoted 5 lines · Bueso
Quoted 2 lines · Waiman Long
2) I want to avoid the extreme case that there are more than 32k readers in the wait queue and make the count overflow.
But in this case the readers are already on the queue.
Never mind this.
But the limit could still be enlarged just to prevent overflows in the case where there are only readers.
Waiman Long
reviewerRe: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
Quoted 7 lines · Davidlohr Bueso
Quoted 5 lines · Bueso
Quoted 3 lines · Waiman Long
2) I want to avoid the extreme case that there are more than 32k readers
in the wait queue and make the count overflow.
Quoted 7 lines
Quoted 1 line
But in this case the readers are already on the queue.
Never mind this.
But the limit could still be enlarged just to prevent overflows in the case
where there are only readers.
The limit is kind of arbitrary. We can certainly increase it if 256 is seemed too low.
Cheers,
Longman
Waiman Long
reviewerRe: [PATCH-tip v2 06/12] locking/rwsem: Wake up almost all readers in wait queue
In reply to Davidlohr BuesoQuoted 8 lines · Davidlohr Bueso
Quoted 4 lines · Waiman Long
There are 2 major reasons why there is a limit.
1) It will be unfair to the task that needs to spend so much of its own CPU time to wake up too many readers.
This has never been a problem before.
In real workloads, you seldom have more than a couple dozens of readers waiting in the queue.
Cheers,
Longman
Waiman Long
reviewerPATCH v2 7/12 locking/rwsem: Enable readers spinning on writer
In reply to Waiman LongThis patch enables readers to optimistically spin on a
rwsem when it is owned by a writer instead of going to sleep directly. The rwsem_can_spin_on_owner() function is extracted out of rwsem_optimistic_spin() and is called directly by __rwsem_down_read_failed_common() and __rwsem_down_write_failed_common().
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBrige-EX system with equal numbers of readers and writers before and after the patch were as follows:
# of Threads Pre-patch Post-patch
------------ --------- ----------
4 1,674 1,684
8 1,062 1,074
16 924 900
32 300 458
64 195 208
128 164 168
240 149 143The performance change wasn't significant in this case, but this change is required by a follow-on patch.
--- kernel/locking/lock_events_list.h | 1 + kernel/locking/rwsem-xadd.c | 88 ++++++++++++++++++++++++++----- kernel/locking/rwsem.h | 3 ++ 3 files changed, 80 insertions(+), 12 deletions(-)
kernel/locking/lock_events_list.h +1 -0
@@ -56,6 +56,7 @@ LOCK_EVENT(rwsem_sleep_reader) /* # of reader sleeps */ LOCK_EVENT(rwsem_sleep_writer) /* # of writer sleeps */ LOCK_EVENT(rwsem_wake_reader) /* # of reader wakeups */ LOCK_EVENT(rwsem_wake_writer) /* # of writer wakeups */ +LOCK_EVENT(rwsem_opt_rlock) /* # of read locks opt-spin acquired */ LOCK_EVENT(rwsem_opt_wlock) /* # of write locks opt-spin acquired */ LOCK_EVENT(rwsem_opt_fail) /* # of failed opt-spinnings */ LOCK_EVENT(rwsem_rlock) /* # of read locks acquired */
kernel/locking/rwsem-xadd.c +76 -12
157 lines not on this page · raw message
kernel/locking/rwsem.h +3 -0
@@ -65,9 +65,12 @@ RWSEM_FLAG_HANDOFF)#define RWSEM_COUNT_LOCKED (c) ((c) & RWSEM_LOCK_MASK) +#define RWSEM_COUNT_WLOCKED (c) ((c) & RWSEM_WRITER_MASK)#define RWSEM_COUNT_HANDOFF (c) ((c) & RWSEM_FLAG_HANDOFF)#define RWSEM_COUNT_LOCKED_OR_HANDOFF (c) \ ((c) & (RWSEM_LOCK_MASK|RWSEM_FLAG_HANDOFF)) +#define RWSEM_COUNT_WLOCKED_OR_HANDOFF (c) \ + ((c) & (RWSEM_WRITER_MASK | RWSEM_FLAG_HANDOFF))#ifdef CONFIG_RWSEM_SPIN_ON_OWNER /*
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 8/12 locking/rwsem: Enable time-based spinning on reader-owned rwsem
In reply to Waiman LongWhen the rwsem is owned by reader, writers stop optimistic spinning simply because there is no easy way to figure out if all the readers are actively running or not. However, there are scenarios where the readers are unlikely to sleep and optimistic spinning can help performance.
This patch provides a simple mechanism for spinning on a reader-owned rwsem by a writer. It is a time threshold based spinning where the allowable spinning time can vary from 10us to 25us depending on the condition of the rwsem.
When the time threshold is exceeded, a bit will be set in the owner field to indicate that no more optimistic spinning will be allowed on this rwsem until it becomes writer owned again. Not even readers is allowed to acquire the reader-locked rwsem by optimistic spinning for fairness.
The time taken for each iteration of the reader-owned rwsem spinning loop varies. Below are sample minimum elapsed times for 16 iterations of the loop.
System Time for 16 Iterations
------ ----------------------
1-socket Skylake ~800ns 4-socket Broadwell ~300ns 2-socket ThunderX2 (arm64) ~250ns
When the lock cacheline is contended, we can see up to almost 10X increase in elapsed time. So 25us will be at most 500, 1300 and 1600 iterations for each of the above systems.
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBridge-EX system with equal numbers of readers and writers before and after this patch were as follows:
# of Threads Pre-patch Post-patch
------------ --------- ----------
2 1,759 6,684
4 1,684 6,738
8 1,074 7,222
16 900 7,163
32 458 7,316
64 208 520
128 168 425
240 143 474This patch gives a big boost in performance for mixed reader/writer workloads.
With 32 locking threads, the rwsem lock event data were:
rwsem_opt_fail=79850
rwsem_opt_nospin=5069
rwsem_opt_rlock=597484
rwsem_opt_wlock=957339
rwsem_sleep_reader=57782
rwsem_sleep_writer=55663
With 64 locking threads, the data looked like:
rwsem_opt_fail=346723
rwsem_opt_nospin=6293
rwsem_opt_rlock=1127119
rwsem_opt_wlock=1400628
rwsem_sleep_reader=308201
rwsem_sleep_writer=72281
So a lot more threads acquired the lock in the slowpath and more threads went to sleep.
--- kernel/locking/lock_events_list.h | 1 + kernel/locking/rwsem-xadd.c | 76 +++++++++++++++++++++++++++++-- kernel/locking/rwsem.h | 45 ++++++++++++++---- 3 files changed, 107 insertions(+), 15 deletions(-)
kernel/locking/lock_events_list.h +1 -0
@@ -59,6 +59,7 @@ LOCK_EVENT(rwsem_wake_writer) /* # of writer wakeups */ LOCK_EVENT(rwsem_opt_rlock) /* # of read locks opt-spin acquired */ LOCK_EVENT(rwsem_opt_wlock) /* # of write locks opt-spin acquired */ LOCK_EVENT(rwsem_opt_fail) /* # of failed opt-spinnings */ +LOCK_EVENT(rwsem_opt_nospin) /* # of disabled reader opt-spinnings */ LOCK_EVENT(rwsem_rlock) /* # of read locks acquired */ LOCK_EVENT(rwsem_rlock_fast) /* # of fast read locks acquired */ LOCK_EVENT(rwsem_rlock_fail) /* # of failed read lock acquisitions */
kernel/locking/rwsem-xadd.c +71 -5
123 lines not on this page · raw message
kernel/locking/rwsem.h +35 -10
73 lines not on this page · raw message
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 9/12 locking/rwsem: Add more rwsem owner access helpers
In reply to Waiman LongBefore combining owner and count, we are adding two new helpers for accessing the owner value in the rwsem.
1) struct task_struct *rwsem_get_owner(struct rw_semaphore *sem)
2) bool is_rwsem_reader_owned(struct rw_semaphore *sem)
--- kernel/locking/rwsem-xadd.c | 15 ++++++++++----- kernel/locking/rwsem.c | 3 +-- kernel/locking/rwsem.h | 32 ++++++++++++++++++++++++++------ 3 files changed, 37 insertions(+), 13 deletions(-)
kernel/locking/rwsem-xadd.c +10 -5
@@ -312,7 +312,7 @@ static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)preempt_disable ();rcu_read_lock (); - owner =READ_ONCE (sem->owner); + owner =rwsem_get_owner (sem);if (owner) { ret =is_rwsem_owner_spinnable (owner) && (is_rwsem_owner_reader (owner) ||owner_on_cpu (owner));
@@ -344,15 +344,21 @@ enum owner_state { static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem) { -struct task_struct *owner =READ_ONCE (sem->owner); +struct task_struct *owner =rwsem_get_owner (sem);long count;if (!is_rwsem_owner_spinnable (owner))return OWNER_NONSPINNABLE ;rcu_read_lock (); -while (owner && !is_rwsem_owner_reader (owner) - && (READ_ONCE (sem->owner) == owner)) { +while (owner && !is_rwsem_owner_reader (owner)) { +struct task_struct *new_owner =rwsem_get_owner (sem); + +if (new_owner != owner) { + owner = new_owner; +break ;/* The owner has changed */ + } +/* * Ensure we emit the owner->on_cpu, dereference _after_ * checking sem->owner still matches owner, if that fails,
@@ -379,7 +385,6 @@ static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem)* spinning except when here is no active locks and the handoff bit * is set. In this case, we have to stop spinning. */ - owner =READ_ONCE (sem->owner);if (!is_rwsem_owner_spinnable (owner))return OWNER_NONSPINNABLE ;if (owner && !is_rwsem_owner_reader (owner))
kernel/locking/rwsem.c +1 -2
@@ -198,8 +198,7 @@ EXPORT_SYMBOL(down_write_killable_nested);void up_read_non_owner (struct rw_semaphore *sem) { -DEBUG_RWSEMS_WARN_ON (!((unsigned long )sem->owner &RWSEM_READER_OWNED ), - sem); +DEBUG_RWSEMS_WARN_ON (!is_rwsem_reader_owned (sem), sem);__up_read (sem); }
kernel/locking/rwsem.h +26 -6
@@ -92,6 +92,11 @@ static inline void rwsem_clear_owner(struct rw_semaphore *sem)WRITE_ONCE (sem->owner,NULL ); } +static inline struct task_struct *rwsem_get_owner (struct rw_semaphore *sem) +{ +return READ_ONCE (sem->owner); +} +/* * The task_struct pointer of the last owning reader will be left in * the owner field.
@@ -136,6 +141,23 @@ static inline bool is_rwsem_spinnable(struct rw_semaphore *sem)return is_rwsem_owner_spinnable (READ_ONCE (sem->owner)); } +/* +* Return true if the rwsem is owned by a reader. +*/ +static inline bool is_rwsem_reader_owned (struct rw_semaphore *sem) +{ +#ifdef CONFIG_DEBUG_RWSEMS +/* +* Check the count to see if it is write-locked. +*/ +long count =atomic_long_read (&sem->count); + +if (count &RWSEM_WRITER_MASK ) +return false; +#endif +return (unsigned long )sem->owner &RWSEM_READER_OWNED ; +} +/* * Return true if rwsem is owned by an anonymous writer or readers. */
@@ -156,6 +178,7 @@ static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem) {unsigned long val = (unsigned long )current |RWSEM_READER_OWNED |RWSEM_ANONYMOUSLY_OWNED ; +if (READ_ONCE (sem->owner) == (struct task_struct *)val)cmpxchg_relaxed ((unsigned long *)&sem->owner, val,RWSEM_READER_OWNED |RWSEM_ANONYMOUSLY_OWNED );
@@ -218,8 +241,7 @@ static inline void __down_read(struct rw_semaphore *sem)if (unlikely (atomic_long_fetch_add_acquire (RWSEM_READER_BIAS , &sem->count) &RWSEM_READ_FAILED_MASK )) {rwsem_down_read_failed (sem); -DEBUG_RWSEMS_WARN_ON (!((unsigned long )sem->owner & -RWSEM_READER_OWNED ), sem); +DEBUG_RWSEMS_WARN_ON (!is_rwsem_reader_owned (sem), sem); }else {rwsem_set_reader_owned (sem); }
@@ -231,8 +253,7 @@ static inline int __down_read_killable(struct rw_semaphore *sem) &sem->count) & RWSEM_READ_FAILED_MASK)) { if (IS_ERR(rwsem_down_read_failed_killable(sem))) return -EINTR; - DEBUG_RWSEMS_WARN_ON(!((unsigned long)sem->owner & - RWSEM_READER_OWNED), sem); + DEBUG_RWSEMS_WARN_ON(!is_rwsem_reader_owned(sem), sem); } else {rwsem_set_reader_owned (sem); }
@@ -299,8 +320,7 @@ static inline void __up_read(struct rw_semaphore *sem) {long tmp; -DEBUG_RWSEMS_WARN_ON (!((unsigned long )sem->owner &RWSEM_READER_OWNED ), - sem); +DEBUG_RWSEMS_WARN_ON (!is_rwsem_reader_owned (sem), sem);rwsem_clear_reader_owned (sem); tmp =atomic_long_add_return_release (-RWSEM_READER_BIAS , &sem->count); if (unlikely((tmp & (RWSEM_LOCK_MASK|RWSEM_FLAG_WAITERS))
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 10/12 locking/rwsem: Guard against making count negative
In reply to Waiman LongThe upper bits of the count field is used as reader count. When sufficient number of active readers are present, the most significant bit will be set and the count becomes negative. If the number of active readers keep on piling up, we may eventually overflow the reader counts. This is not likely to happen unless the number of bits reserved for reader count is reduced because those bits are need for other purpose.
To prevent this count overflow from happening, the most significant bit is now treated as a guard bit (RWSEM_FLAG_READFAIL). Read-lock attempts will now fail for both the fast and optimistic spinning paths whenever this bit is set. So all those extra readers will be put to sleep in the wait queue. Wakeup will not happen until the reader count reaches 0.
--- kernel/locking/rwsem-xadd.c | 38 +++++++++++++++++++----- kernel/locking/rwsem.h | 59 ++++++++++++++++++++++++++----------- 2 files changed, 73 insertions(+), 24 deletions(-)
kernel/locking/rwsem-xadd.c +31 -7
@@ -92,7 +92,8 @@ enum rwsem_wake_type {/* * We limit the maximum number of readers that can be woken up for a * wake-up call to not penalizing the waking thread for spending too -* much time doing it. +* much time doing it as well as the unlikely possiblity of overflowing +* the reader count. */ #define MAX_READERS_WAKEUP 0x100
@@ -558,12 +559,35 @@ rwsem_waiter_is_first(struct rw_semaphore *sem, struct rwsem_waiter *waiter)* Wait for the read lock to be granted */ static inline struct rw_semaphore __sched * -__rwsem_down_read_failed_common (struct rw_semaphore *sem,int state) +__rwsem_down_read_failed_common (struct rw_semaphore *sem,int state,long count) { -long count, adjustment = -RWSEM_READER_BIAS ; +long adjustment = -RWSEM_READER_BIAS ;struct rwsem_waiter waiter;DEFINE_WAKE_Q (wake_q); +if (unlikely (count <0 )) { +/* +* The sign bit has been set meaning that too many active +* readers are present. We need to decrement reader count & +* enter wait queue immediately to avoid overflowing the +* reader count. +* +* As preemption is not disabled, there is a remote +* possibility that premption can happen in the narrow +* timing window between incrementing and decrementing +* the reader count and the task is put to sleep for a +* considerable amount of time. If sufficient number +* of such unfortunate sequence of events happen, we +* may still overflow the reader count. It is extremely +* unlikey, though. If this is a concern, we should consider +* disable preemption during this timing window to make +* sure that such unfortunate event will not happen. +*/ +atomic_long_add (-RWSEM_READER_BIAS , &sem->count); + adjustment =0 ; + goto queue; + } +if (!rwsem_can_spin_on_owner (sem)) goto queue;
@@ -664,16 +688,16 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state) } __visible struct rw_semaphore * __sched -rwsem_down_read_failed(struct rw_semaphore *sem) +rwsem_down_read_failed(struct rw_semaphore *sem, long cnt) { -return __rwsem_down_read_failed_common (sem,TASK_UNINTERRUPTIBLE ); +return __rwsem_down_read_failed_common (sem,TASK_UNINTERRUPTIBLE , cnt); }EXPORT_SYMBOL (rwsem_down_read_failed); __visible struct rw_semaphore * __sched -rwsem_down_read_failed_killable(struct rw_semaphore *sem) +rwsem_down_read_failed_killable(struct rw_semaphore *sem, long cnt) { -return __rwsem_down_read_failed_common (sem,TASK_KILLABLE ); +return __rwsem_down_read_failed_common (sem,TASK_KILLABLE , cnt); }EXPORT_SYMBOL (rwsem_down_read_failed_killable);
kernel/locking/rwsem.h +42 -17
96 lines not on this page · raw message
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 11/12 locking/rwsem: Merge owner into count on x86-64
In reply to Waiman LongWith separate count and owner, there are timing windows where the two values are inconsistent. That can cause problem when trying to figure out the exact state of the rwsem. For instance, a RT task will stop optimistic spinning if the lock is acquired by a writer but the owner field isn't set yet. That can be solved by combining the count and owner together in a single atomic value.
On 32-bit architectures, there aren't enough bits to hold both. 64-bit architectures, however, can have enough bits to do that. For x86-64, the physical address can use up to 52 bits. That is 4PB of memory. That leaves 12 bits available for other use. The task structure pointer is aligned to the L1 cache size. That means another 6 bits (64 bytes cacheline) will be available. Reserving 2 bits for status flags, we will have 16 bits for the reader count and the read fail bit. That can supports up to (32k-1) readers.
The owner value will still be duplicated in the owner field as that will ease debugging when looking at core dump.
This change is currently enabled for x86-64 only. Other 64-bit architectures may be enabled in the future if the need arises.
With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBridge-EX system with writer-only locking threads and then equal numbers of readers and writers (mixed) before patch and after this and subsequent related patches were as follows:
Before Patch After Patch
# of Threads wlock mixed wlock mixed
------------ ----- ----- ----- -----
1 30,422 31,034 30,323 30,379
2 6,427 6,684 7,804 9,436
4 6,742 6,738 7,568 8,268
8 7,092 7,222 5,679 7,041
16 6,882 7,163 6,848 7,652
32 7,458 7,316 7,975 2,189
64 7,906 520 8,269 534
128 1,680 425 8,047 448In the single thread case, the complex write-locking operation does introduce a little bit of overhead (about 0.3%). For the contended cases, except for some anomalies in the data, there is no evidence that this change will adversely impact performance.
When running the same microbenchmark with RT locking threads instead, we got the following results:
Before Patch After Patch
# of Threads wlock mixed wlock mixed
------------ ----- ----- ----- -----
2 4,065 3,642 4,756 5,062
4 2,254 1,907 3,460 2,496
8 2,386 964 3,012 1,964
16 2,095 1,596 3,083 1,862
32 2,388 530 3,717 359
64 1,424 322 4,060 401
128 1,642 510 4,488 628It is obvious that RT tasks can benefit pretty significantly with this set of patches.
--- kernel/locking/rwsem-xadd.c | 11 ++-- kernel/locking/rwsem.h | 101 +++++++++++++++++++++++++++++++++--- 2 files changed, 103 insertions(+), 9 deletions(-)
kernel/locking/rwsem-xadd.c +8 -3
@@ -27,11 +27,11 @@/* * Guide to the rw_semaphore's count field. * -* When the RWSEM_WRITER_LOCKED bit in count is set, the lock is owned -* by a writer. +* When any of the RWSEM_WRITER_MASK bits in count is set, the lock is +* owned by a writer. * * The lock is owned by readers when -* (1) the RWSEM_WRITER_LOCKED isn't set in count, +* (1) none of the RWSEM_WRITER_MASK bits is set in count, * (2) some of the reader bits are set in count, and * (3) the owner field has RWSEM_READ_OWNED bit set. *
@@ -47,6 +47,11 @@void __init_rwsem (struct rw_semaphore *sem,const char *name,struct lock_class_key *key) { +/* +* We should support at least (4k-1) concurrent readers +*/ +BUILD_BUG_ON (sizeof (long ) *8 -RWSEM_READER_SHIFT <12 ); +#ifdef CONFIG_DEBUG_LOCK_ALLOC /* * Make sure we are not reinitializing a held semaphore:
kernel/locking/rwsem.h +95 -6
153 lines not on this page · raw message
Signature · 1 line
2.18.1
Waiman Long
reviewerPATCH v2 12/12 locking/rwsem: Remove redundant computation of writer lock word
In reply to Waiman LongOn 64-bit architectures, each rwsem writer will have its unique lock word for acquiring the lock. Right now, the writer code recomputes the lock word every time it tries to acquire the lock. This is a waste of time. The lock word is now cached and reused when it is needed.
On 32-bit architectures, the extra constant argument to rwsem_try_write_lock() and rwsem_try_write_lock_unqueued() should be optimized out by the compiler.
--- kernel/locking/rwsem-xadd.c | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-)
kernel/locking/rwsem-xadd.c +14 -11
@@ -230,8 +230,8 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,* race conditions between checking the rwsem wait list and setting the * sem->count accordingly. */ -static inline bool -rwsem_try_write_lock (long count,struct rw_semaphore *sem,bool first) +static inline bool rwsem_try_write_lock (long count,struct rw_semaphore *sem, +const long wlock,bool first) {long new;
@@ -241,7 +241,7 @@ rwsem_try_write_lock(long count, struct rw_semaphore *sem, bool first)if (!first &&RWSEM_COUNT_HANDOFF (count))return false; - new = (count & ~RWSEM_FLAG_HANDOFF ) +RWSEM_WRITER_LOCKED - + new = (count & ~RWSEM_FLAG_HANDOFF ) + wlock - (list_is_singular (&sem->wait_list) ?RWSEM_FLAG_WAITERS :0 );if (atomic_long_try_cmpxchg_acquire (&sem->count, &count, new)) {
@@ -280,13 +280,14 @@ static inline bool rwsem_try_read_lock_unqueued(struct rw_semaphore *sem)/* * Try to acquire write lock before the writer has been put on wait queue. */ -static inline bool rwsem_try_write_lock_unqueued (struct rw_semaphore *sem) +static inline bool rwsem_try_write_lock_unqueued (struct rw_semaphore *sem, +const long wlock) {long count =atomic_long_read (&sem->count);while (!RWSEM_COUNT_LOCKED_OR_HANDOFF (count)) {if (atomic_long_try_cmpxchg_acquire (&sem->count, &count, - count +RWSEM_WRITER_LOCKED )) { + count + wlock)) {rwsem_set_owner (sem);lockevent_inc (rwsem_opt_wlock);return true;
@@ -436,7 +437,7 @@ static inline u64 rwsem_rspin_threshold(struct rw_semaphore *sem) : 25 * NSEC_PER_USEC); } -static bool rwsem_optimistic_spin (struct rw_semaphore *sem,bool wlock) +static bool rwsem_optimistic_spin (struct rw_semaphore *sem,const long wlock) {bool taken = false;bool is_rt_task =rt_task (current);
@@ -465,7 +466,7 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem, bool wlock)/* * Try to acquire the lock */ - taken = wlock ?rwsem_try_write_lock_unqueued (sem) + taken = wlock ?rwsem_try_write_lock_unqueued (sem, wlock) :rwsem_try_read_lock_unqueued (sem);if (taken)
@@ -544,7 +545,8 @@ static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)return false; } -static inline bool rwsem_optimistic_spin (struct rw_semaphore *sem,bool wlock) +static inline bool rwsem_optimistic_spin (struct rw_semaphore *sem, +const long wlock) {return false; }
@@ -601,7 +603,7 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state, long count)*/ atomic_long_add (-RWSEM_READER_BIAS , &sem->count); adjustment =0 ; -if (rwsem_optimistic_spin (sem, false)) { +if (rwsem_optimistic_spin (sem,0 )) {unsigned long flags;/*
@@ -717,10 +719,11 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)struct rwsem_waiter waiter;struct rw_semaphore *ret = sem;DEFINE_WAKE_Q (wake_q); +const long wlock =RWSEM_WRITER_LOCKED ;/* do optimistic spinning and steal lock if possible */ if (rwsem_can_spin_on_owner (sem) && -rwsem_optimistic_spin (sem, true)) +rwsem_optimistic_spin (sem, wlock))return sem;/*
@@ -779,7 +782,7 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)/* wait until we successfully acquire the lock */ set_current_state (state);while (true) { -if (rwsem_try_write_lock (count, sem, first)) +if (rwsem_try_write_lock (count, sem, wlock, first))break ;raw_spin_unlock_irq (&sem->wait_lock);
Signature · 1 line
2.18.1
Quoted 5 lines · Waiman Long
v2:
- Move the negative reader count checking patch (patch 12->10) forward to before the merge owner to count patch as suggested by Linus & expand the comment.
All looks good to me now.
I didn't apply and _test_ any of the patches, but they look sane and the numbers you quote are compelling.
So ack as far as I'm concerned,
Linus
Quoted 23 lines · Waiman Long
# of Threads Before Patch After Patch ------------ ------------ ----------- 2 1,179 9,436 4 1,505 8,268 8 721 7,041 16 575 7,652 32 70 2,189 64 39 534Waiman Long (12):
locking/rwsem: Implement a new locking scheme locking/rwsem: Implement lock handoff to prevent lock starvation locking/rwsem: Removerwsem_wake()wakeup optimization locking/rwsem: Makerwsem_spin_on_owner()return owner state locking/rwsem: Ensure an RT task will not spin on reader locking/rwsem: Wake up almost all readers in wait queue locking/rwsem: Enable readers spinning on writer locking/rwsem: Enable time-based spinning on reader-owned rwsem locking/rwsem: Add more rwsem owner access helpers locking/rwsem: Guard against making count negative locking/rwsem: Merge owner into count on x86-64 locking/rwsem: Remove redundant computation of writer lock word
Quoted 5 lines
kernel/locking/lock_events_list.h | 4 + kernel/locking/rwsem-xadd.c | 635 +++++++++++++++++++----------- kernel/locking/rwsem.c | 3 +- kernel/locking/rwsem.h | 290 +++++++++++--- 4 files changed, 647 insertions(+), 285 deletions(-)
Looks very nice!
With both sets of patches applied they pass all x86 tests, but there's cross-build failures on powerpc32, sparc32 and UML:
kernel/locking/rwsem.h:333:34: error: 'struct rw_semaphore' has no member named 'owner'
Could you please send a delta patch against tip:WIP.locking/core, which is the work-in-progress tree? I'll backmerge the delta patch (and any other updates you might have meanwhil) to the one that introduces the breakage.
Thanks,
Ingo
Waiman Long
reviewerQuoted 37 lines · Ingo Molnar
Quoted 23 lines · Waiman Long
# of Threads Before Patch After Patch ------------ ------------ ----------- 2 1,179 9,436 4 1,505 8,268 8 721 7,041 16 575 7,652 32 70 2,189 64 39 534Waiman Long (12):
locking/rwsem: Implement a new locking scheme locking/rwsem: Implement lock handoff to prevent lock starvation locking/rwsem: Removerwsem_wake()wakeup optimization locking/rwsem: Makerwsem_spin_on_owner()return owner state locking/rwsem: Ensure an RT task will not spin on reader locking/rwsem: Wake up almost all readers in wait queue locking/rwsem: Enable readers spinning on writer locking/rwsem: Enable time-based spinning on reader-owned rwsem locking/rwsem: Add more rwsem owner access helpers locking/rwsem: Guard against making count negative locking/rwsem: Merge owner into count on x86-64 locking/rwsem: Remove redundant computation of writer lock wordQuoted 5 lines
kernel/locking/lock_events_list.h | 4 + kernel/locking/rwsem-xadd.c | 635 +++++++++++++++++++----------- kernel/locking/rwsem.c | 3 +- kernel/locking/rwsem.h | 290 +++++++++++--- 4 files changed, 647 insertions(+), 285 deletions(-)Looks very nice!
With both sets of patches applied they pass all x86 tests, but there's cross-build failures on powerpc32, sparc32 and UML:
kernel/locking/rwsem.h:333:34: error: 'structrw_semaphore' has no member named 'owner'
Quoted 8 lines
Could you please send a delta patch against tip:WIP.locking/core, which is the work-in-progress tree? I'll backmerge the delta patch (and any other updates you might have meanwhil) to the one that introduces the breakage.
Thanks,
Ingo
Sure. I will look into that and fix failures.
Thanks,
Longman