locking/rwsem: Fix rwsem waiter optimistic spinning problem with RT tasks
Subsystems (2)
Waiman Long
reviewerv2 cover locking/rwsem: Fix rwsem waiter optimistic spinning problem with RT tasks
v2:
- Add an additional patch to limit the # of first waiter optimistic spinning in the writer slowpath.
It turns out the current waiter optimistic spinning code does not work that well if we have RT tasks in the mix. This patch series include two different fixes to resolve those issues.
Waiman Long (2):
locking/rwsem: Prevent non-first waiter from spinning in down_write()
slowpath
locking/rwsem: Limit # of null owner retries for handoff writer
kernel/locking/rwsem.c | 31 ++++++++++++++++++++++++++----- 1 file changed, 26 insertions(+), 5 deletions(-)
Signature · 1 line
2.31.1
Waiman Long
reviewerPATCH v2 1/2 locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
A non-first waiter can potentially spin in the for loop of rwsem_down_write_slowpath() without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:
Non-first waiter First waiter Lock holder
---------------- ------------ -----------
Acquire wait_lock
rwsem_try_write_lock():
Set handoff bit if RT or
wait too long
Set waiter->handoff_set
Release wait_lock
Acquire wait_lock
Inherit waiter->handoff_set
Release wait_lock
Clear owner
Release lock
if (waiter.handoff_set) {
rwsem_spin_on_owner(();
if (OWNER_NULL)
goto trylock_again;
}
trylock_again:
Acquire wait_lock
rwsem_try_write_lock():
if (first->handoff_set && (waiter != first))
return false; Release wait_lock
It is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
--- kernel/locking/rwsem.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-)
kernel/locking/rwsem.c +10 -3
@@ -636,6 +636,11 @@ static inline bool rwsem_try_write_lock(struct rw_semaphore *sem, new = count;if (count &RWSEM_LOCK_MASK ) { +/* +* A waiter (first or not) can set the handoff bit +* if it is an RT task or wait in the wait queue +* for too long. +*/ if (has_handoff || (!rt_task (waiter->task) && !time_after (jiffies, waiter->timeout)))return false;
@@ -651,11 +656,13 @@ static inline bool rwsem_try_write_lock(struct rw_semaphore *sem, }while (!atomic_long_try_cmpxchg_acquire (&sem->count, &count, new));/* -* We have either acquired the lock with handoff bit cleared or -* set the handoff bit. +* We have either acquired the lock with handoff bit cleared or set +* the handoff bit. Only the first waiter can have its handoff_set +* set here to enable optimistic spinning in slowpath loop. */ if (new &RWSEM_FLAG_HANDOFF ) { - waiter->handoff_set = true; +if (waiter == first) + waiter->handoff_set = true;lockevent_inc (rwsem_wlock_handoff);return false; }
Signature · 1 line
2.31.1
Re: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
Hi,
Quoted 29 lines · Waiman Long
A non-first waiter can potentially spin in the for loop of
rwsem_down_write_slowpath()without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:Non-first waiter First waiter Lock holder ---------------- ------------ ----------- Acquire wait_lock rwsem_try_write_lock(): Set handoff bit if RT or wait too long Set waiter->handoff_set Release wait_lock Acquire wait_lock Inherit waiter->handoff_set Release wait_lock Clear owner Release lock if (waiter.handoff_set) { rwsem_spin_on_owner((); if (OWNER_NULL) goto trylock_again; } trylock_again: Acquire wait_lock rwsem_try_write_lock(): if (first->handoff_set && (waiter != first)) return false; Release wait_lock
Quoted 6 lines
It is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
Fixes d257cc8cb8d5 ("locking/rwsem: Make handoff bit handling more consistent")Signed-off-by Waiman Long <[email protected]>
Since this patch is tested and it covers the mentioned scenario.
-Mukesh
Quoted 37 lines
--- kernel/locking/rwsem.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-)kernel/locking/rwsem.c +10
-3@@ -636,6 +636,11 @@ static inline bool rwsem_try_write_lock(struct rw_semaphore *sem, new = count;if (count &RWSEM_LOCK_MASK ) { +/* +* A waiter (first or not) can set the handoff bit +* if it is an RT task or wait in the wait queue +* for too long. +*/ if (has_handoff || (!rt_task (waiter->task) && !time_after (jiffies, waiter->timeout)))return false;@@ -651,11 +656,13 @@ static inline bool rwsem_try_write_lock(struct rw_semaphore *sem, }while (!atomic_long_try_cmpxchg_acquire (&sem->count, &count, new));/* -* We have either acquired the lock with handoff bit cleared or -* set the handoff bit. +* We have either acquired the lock with handoff bit cleared or set +* the handoff bit. Only the first waiter can have its handoff_set +* set here to enable optimistic spinning in slowpath loop. */ if (new &RWSEM_FLAG_HANDOFF ) { - waiter->handoff_set = true; +if (waiter == first) + waiter->handoff_set = true;lockevent_inc (rwsem_wlock_handoff); return false }
Peter Zijlstra
maintainerRe: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
In reply to Waiman LongQuoted 27 lines · Waiman Long
A non-first waiter can potentially spin in the for loop of
rwsem_down_write_slowpath()without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:Non-first waiter First waiter Lock holder ---------------- ------------ ----------- Acquire wait_lock rwsem_try_write_lock(): Set handoff bit if RT or wait too long Set waiter->handoff_set Release wait_lock Acquire wait_lock Inherit waiter->handoff_set Release wait_lock Clear owner Release lock if (waiter.handoff_set) { rwsem_spin_on_owner((); if (OWNER_NULL) goto trylock_again; } trylock_again: Acquire wait_lock rwsem_try_write_lock(): if (first->handoff_set && (waiter != first)) return false;
Quoted 6 lines
Release
wait_lockIt is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)
Re: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
On 13 Oct 2022 12:02:09 +0200 Peter Zijlstra <[email protected]>
Quoted 30 lines · Waiman Long
Quoted 29 lines
A non-first waiter can potentially spin in the for loop of
rwsem_down_write_slowpath()without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:Non-first waiter First waiter Lock holder ---------------- ------------ ----------- Acquire wait_lock rwsem_try_write_lock(): Set handoff bit if RT or wait too long Set waiter->handoff_set Release wait_lock Acquire wait_lock Inherit waiter->handoff_set Release wait_lock Clear owner Release lock if (waiter.handoff_set) { rwsem_spin_on_owner((); if (OWNER_NULL) goto trylock_again; } trylock_again: Acquire wait_lock rwsem_try_write_lock(): if (first->handoff_set && (waiter != first)) return false;Release
wait_lock
Quoted 6 lines
Quoted 4 lines
It is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)
Given a simple coding of "better handoff", with care to avoid change added to fast path, I see no bonus except for preventing non-first waiters from spinning.
Hillf
+++ b/kernel/locking/rwsem.c
@@ -429,6 +429,7 @@ static void rwsem_mark_wake(struct rw_se
if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
if (wake_type == RWSEM_WAKE_ANY) {
+ atomic_long_set(&sem->owner, (long)waiter->task);
/*
* Mark writer at the front of the queue for wakeup.
* Until the task is actually later awoken later by
@@ -752,7 +753,7 @@ rwsem_owner_state(struct task_struct *ow
static noinline enum owner_state
rwsem_spin_on_owner(struct rw_semaphore *sem)
{
- struct task_struct *new, *owner;
+ struct task_struct *new, *owner, *me = current;
unsigned long flags, new_flags;
enum owner_state state;
@@ -762,6 +763,8 @@ rwsem_spin_on_owner(struct rw_semaphore
state = rwsem_owner_state(owner, flags); if (state != OWNER_WRITER)
return state;
+ if (owner == me)
+ return OWNER_NULL;
for (;;) {
/*
@@ -772,7 +775,10 @@ rwsem_spin_on_owner(struct rw_semaphore
*/
new = rwsem_owner_flags(sem, &new_flags); if ((new != owner) || (new_flags != flags)) {
- state = rwsem_owner_state(new, new_flags);
+ if (new == me)
+ state = OWNER_NULL;
+ else
+ state = rwsem_owner_state(new, new_flags);
break;
}
Re: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
On 13 Oct 2022 21:15:05 +0800 Hillf Danton <[email protected]>
Quoted 6 lines
On 13 Oct 2022 12:02:09 +0200 Peter Zijlstra <[email protected]>
Quoted 5 lines · Waiman Long
Quoted 4 lines
It is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
Quoted 6 lines
Quoted 2 lines
So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)
Given a simple coding of "better handoff", with care to avoid change added to fast path, I see no bonus except for preventing non-first waiters from spinning.
Spin with a line in fast path cut.
Prevent non-first waiters from spinning too much by 1) not clearing lock owner before releasing rwsem because new acquirer will set it and 2) setting owner to the first waiter instead while waking lock waiters up in bid to force non-first spinners to take a break.
Note, first waiter spinning longer than thought still makes trouble but it is not addressed here because of known cure.
Hillf
+++ b/kernel/locking/rwsem.c
@@ -429,6 +429,7 @@ static void rwsem_mark_wake(struct rw_se
if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
if (wake_type == RWSEM_WAKE_ANY) {
+ atomic_long_set(&sem->owner, (long)waiter->task);
/*
* Mark writer at the front of the queue for wakeup.
* Until the task is actually later awoken later by
@@ -752,7 +753,7 @@ rwsem_owner_state(struct task_struct *ow
static noinline enum owner_state
rwsem_spin_on_owner(struct rw_semaphore *sem)
{
- struct task_struct *new, *owner;
+ struct task_struct *new, *owner, *me = current;
unsigned long flags, new_flags;
enum owner_state state;
@@ -762,6 +763,8 @@ rwsem_spin_on_owner(struct rw_semaphore
state = rwsem_owner_state(owner, flags); if (state != OWNER_WRITER)
return state;
+ if (owner == me)
+ return OWNER_NULL;
for (;;) {
/*
@@ -772,7 +775,10 @@ rwsem_spin_on_owner(struct rw_semaphore
*/
new = rwsem_owner_flags(sem, &new_flags); if ((new != owner) || (new_flags != flags)) {
- state = rwsem_owner_state(new, new_flags);
+ if (new == me)
+ state = OWNER_NULL;
+ else
+ state = rwsem_owner_state(new, new_flags);
break;
}
@@ -1360,10 +1366,7 @@ static inline void __up_write(struct rw_
DEBUG_RWSEMS_WARN_ON((rwsem_owner(sem) != current) &&
!rwsem_test_oflags(sem, RWSEM_NONSPINNABLE), sem);
- preempt_disable();
- rwsem_clear_owner(sem);
tmp = atomic_long_fetch_add_release(-RWSEM_WRITER_LOCKED, &sem->count);
- preempt_enable();
if (unlikely(tmp & RWSEM_FLAG_WAITERS))
rwsem_wake(sem);
}
Waiman Long
reviewerRe: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
In reply to Peter ZijlstraQuoted 30 lines · Peter Zijlstra
Quoted 29 lines · Waiman Long
A non-first waiter can potentially spin in the for loop of
rwsem_down_write_slowpath()without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:Non-first waiter First waiter Lock holder ---------------- ------------ ----------- Acquire wait_lock rwsem_try_write_lock(): Set handoff bit if RT or wait too long Set waiter->handoff_set Release wait_lock Acquire wait_lock Inherit waiter->handoff_set Release wait_lock Clear owner Release lock if (waiter.handoff_set) { rwsem_spin_on_owner((); if (OWNER_NULL) goto trylock_again; } trylock_again: Acquire wait_lock rwsem_try_write_lock(): if (first->handoff_set && (waiter != first)) return false; Release wait_lock
Quoted 6 lines
Quoted 4 lines
It is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)
I understand your desire to make the rwsem handoff process more like what mutex is currently doing. I certainly think it is doable and will put this in my todo list. However, that needs to be done at unlock and wakeup time. I expect that will require moderate amount of code changes which will make it not that suitable for backporting to the stable releases.
I would like to see these simple fixes get merged first and then we can work on a major revamp of the handoff code. What do you think?
Cheers,
Longman
Waiman Long
reviewerRe: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath
Quoted 35 lines · Waiman Long
Quoted 34 lines · Peter Zijlstra
Quoted 33 lines · Waiman Long
A non-first waiter can potentially spin in the for loop of
rwsem_down_write_slowpath()without sleeping but fail to acquire the lock even if the rwsem is free if the following sequence happens:Non-first waiter First waiter Lock holder ---------------- ------------ ----------- Acquire
wait_lock
rwsem_try_write_lock():
Set handoff bit if RT or
wait too long
Setwaiter->handoff_set
Releasewait_lock
Acquirewait_lockInheritwaiter->handoff_setReleasewait_lockClear owner
Release lock if (waiter.handoff_set) { rwsem_spin_on_owner(();
if (OWNER_NULL)
gototrylock_again;
}
trylock_again:
Acquirewait_lock
rwsem_try_write_lock():
if (first->handoff_set&& (waiter != first)) return false;
Releasewait_lockIt is especially problematic if the non-first waiter is an RT task and it is running on the same CPU as the first waiter as this can lead to live lock.
Quoted 7 lines
Quoted 2 lines
So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)
I understand your desire to make the rwsem handoff process more like what mutex is currently doing. I certainly think it is doable and will put this in my todo list. However, that needs to be done at unlock and wakeup time. I expect that will require moderate amount of code changes which will make it not that suitable for backporting to the stable releases.
I would like to see these simple fixes get merged first and then we can work on a major revamp of the handoff code. What do you think?
I am planning to post additional patches on top to rework the handoff code sometimes next week, but I will keep these fix patches for the stable releases.
Cheers,
Longman
Waiman Long
reviewerPATCH v2 2/2 locking/rwsem: Limit # of null owner retries for handoff writer
In reply to Waiman LongCommit 91d2a812dfb9 ("locking/rwsem: Make handoff writer optimistically spin on owner") assumes that when the owner field is changed to NULL, the lock will become free soon. That assumption may not be correct especially if the handoff writer doing the spinning is a RT task which may preempt another task from completing its action of either freeing the rwsem or properly setting up owner.
To prevent this live lock scenario, we have to limit the number of trylock attempts without sleeping. The current limit is now set to 8 to allow enough time for the other task to hopefully complete its action.
By adding new lock events to track the number of NULL owner retries with handoff flag set before a successful trylock when running a 96 threads locking microbenchmark with equal number of readers and writers running on a 2-core 96-thread system for 15 seconds, the following stats are obtained. Note that none of locking threads are RT tasks.
Retries of successful trylock Count
----------------------------- -----
1 1738 2 19
3 11
4 2
5 1
6 1
7 1
8 0
X 1
The last row is the one failed attempt that needs more than 8 retries. So a retry count maximum of 8 should capture most of them if no RT task is in the mix.
--- kernel/locking/rwsem.c | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)
kernel/locking/rwsem.c +16 -2
@@ -1123,6 +1123,7 @@ static struct rw_semaphore __sched * rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) {struct rwsem_waiter waiter; +int null_owner_retries;DEFINE_WAKE_Q (wake_q);/* do optimistic spinning and steal lock if possible */
@@ -1164,7 +1165,7 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state)set_current_state (state);trace_contention_begin (sem,LCB_F_WRITE ); -for (;;) { +for (null_owner_retries =0 ;;) {if (rwsem_try_write_lock (sem, &waiter)) {/* rwsem_try_write_lock() implies ACQUIRE on success */ break ;
@@ -1190,8 +1191,21 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) owner_state =rwsem_spin_on_owner (sem);preempt_enable (); -if (owner_state ==OWNER_NULL ) +/* +* owner is NULL doesn't guarantee the lock is free. +* An incoming reader will temporarily increment the +* reader count without changing owner and the +* rwsem_try_write_lock() will fails if the reader +* is not able to decrement it in time. Allow 8 +* trylock attempts when hitting a NULL owner before +* going to sleep. +*/ +if ((owner_state ==OWNER_NULL ) && + (null_owner_retries <8 )) { + null_owner_retries++; goto trylock_again; + } + null_owner_retries =0 ; }schedule ();
Signature · 1 line
2.31.1
Re: [PATCH v2 2/2] locking/rwsem: Limit # of null owner retries for handoff writer
Hi,
Quoted 67 lines · Waiman Long
Commit
91d2a812dfb9("locking/rwsem: Make handoff writer optimistically spin on owner") assumes that when the owner field is changed to NULL, the lock will become free soon. That assumption may not be correct especially if the handoff writer doing the spinning is a RT task which may preempt another task from completing its action of either freeing the rwsem or properly setting up owner.To prevent this live lock scenario, we have to limit the number of trylock attempts without sleeping. The current limit is now set to 8 to allow enough time for the other task to hopefully complete its action.
By adding new lock events to track the number of NULL owner retries with handoff flag set before a successful trylock when running a 96 threads locking microbenchmark with equal number of readers and writers running on a 2-core 96-thread system for 15 seconds, the following stats are obtained. Note that none of locking threads are RT tasks.
Retries of successful trylock Count ----------------------------- ----- 1 17382 19
3 11
4 2
5 1
6 1
7 1
8 0
X 1The last row is the one failed attempt that needs more than 8 retries. So a retry count maximum of 8 should capture most of them if no RT task is in the mix.
Fixes 91d2a812dfb9 ("locking/rwsem: Make handoff writer optimistically spin on owner")Reported-by Mukesh Ojha <[email protected]>Signed-off-by Waiman Long <[email protected]>--- kernel/locking/rwsem.c | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)kernel/locking/rwsem.c +3
-2@@ -1123,6 +1123,7 @@ static struct rw_semaphore __sched * rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) {struct rwsem_waiter waiter; +int null_owner_retries;DEFINE_WAKE_Q (wake_q);/* do optimistic spinning and steal lock if possible */ @@ -1164,7 +1165,7 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state)set_current_state (state);trace_contention_begin (sem,LCB_F_WRITE ); -for (;;) { +for (null_owner_retries =0 ;;) {if (rwsem_try_write_lock (sem, &waiter)) {/* rwsem_try_write_lock() implies ACQUIRE on success */ break ;@@ -1190,8 +1191,21 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) owner_state =rwsem_spin_on_owner (sem);preempt_enable (); -if (owner_state ==OWNER_NULL ) +/*
kernel/locking/rwsem.c rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) · line 1204
Quoted 10 lines
kernel/locking/rwsem.c +10
-0+* owner is NULL doesn't guarantee the lock is free. +* An incoming reader will temporarily increment the +* reader count without changing owner and the +* rwsem_try_write_lock() will fails if the reader +* is not able to decrement it in time. Allow 8 +* trylock attempts when hitting a NULL owner before +* going to sleep. +*/ +if ((owner_state ==OWNER_NULL ) && + (null_owner_retries <8 )) {
define MAX_NULL_OWNER_RETRY 8
??
kernel/locking/rwsem.c rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) · line 1210
Quoted 6 lines
kernel/locking/rwsem.c +3
-0+ null_owner_retries++; goto trylock_again; + } + null_owner_retries =0 ; }
Thanks for considering this patch.
LGTM.
-Mukesh
Quoted 1 line
kernel/locking/rwsem.c +0
-0schedule ();