rwsem: fix missed wakeup due to reordering of load
PATCH 1/1 rwsem: fix missed wakeup due to reordering of load
If a spinner is present, there is a chance that the load of rwsem_has_spinner() in rwsem_wake() can be reordered with respect to decrement of rwsem count in __up_write() leading to wakeup being missed.
spinning writer up_write caller
--------------- -----------------------
[S] osq_unlock() [L] osq
spin_lock(wait_lock)
sem->count=0xFFFFFFFF00000001
+0xFFFFFFFF00000000
count=sem->count
MB
sem->count=0xFFFFFFFE00000001
-0xFFFFFFFF00000001
RMB
spin_trylock(wait_lock)
return rwsem_try_write_lock(count)
spin_unlock(wait_lock)
schedule()
Reordering of atomic_long_sub_return_release() in __up_write() and rwsem_has_spinner() in rwsem_wake() can cause missing of wakeup in up_write() context. In spinning writer, sem->count and local variable count is 0XFFFFFFFE00000001. It would result in rwsem_try_write_lock() failing to acquire rwsem and spinning writer going to sleep in rwsem_down_write_failed().
The smp_rmb() will make sure that the spinner state is consulted after sem->count is updated in up_write context.
--- kernel/locking/rwsem-xadd.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+)
kernel/locking/rwsem-xadd.c +45 -0
@@ -586,6 +586,51 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)DEFINE_WAKE_Q (wake_q);/* +* If a spinner is present, there is a chance that the load of +* rwsem_has_spinner() in rwsem_wake() can be reordered with +* respect to decrement of rwsem count in __up_write() leading +* to wakeup being missed. +* +* spinning writer up_write caller +* --------------- ----------------------- +* [S] osq_unlock() [L] osq +* spin_lock(wait_lock) +* sem->count=0xFFFFFFFF00000001 +* +0xFFFFFFFF00000000 +* count=sem->count +* MB +* sem->count=0xFFFFFFFE00000001 +* -0xFFFFFFFF00000001 +* RMB +* spin_trylock(wait_lock) +* return +* rwsem_try_write_lock(count) +* spin_unlock(wait_lock) +* schedule() +* +* Reordering of atomic_long_sub_return_release() in __up_write() +* and rwsem_has_spinner() in rwsem_wake() can cause missing of +* wakeup in up_write() context. In spinning writer, sem->count +* and local variable count is 0XFFFFFFFE00000001. It would result +* in rwsem_try_write_lock() failing to acquire rwsem and spinning +* writer going to sleep in rwsem_down_write_failed(). +* +* +* The RMB in below example is to make sure that the spinner state is +* consulted after sem->count is updated in up_write context. +* This would guarantee trylock on rwsem is successful +* in rwsem_down_write_failed(). +* spinning writer up_write caller +* --------------- ----------------------- +* [S] osq_unlock() atomic_update(sem->count) +* RMB +* atomic_update(sem->count) [L] osq +* MB +* rwsem_try_write_lock(count) +*/ +smp_rmb (); + +/* * If a spinner is present, 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
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc., is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Peter Zijlstra
maintainerWTH did you not Cc the people that commented on your patch last time?
Quoted 5 lines · Prateek Sood
If a spinner is present, there is a chance that the load of
rwsem_has_spinner()inrwsem_wake()can be reordered with respect to decrement of rwsem count in__up_write()leading to wakeup being missed.
Quoted 11 lines
spinning writer up_write caller
--------------- -----------------------
[S] osq_unlock() [L] osq
spin_lock(wait_lock)
sem->count=0xFFFFFFFF00000001
+0xFFFFFFFF00000000
count=sem->count
MB
sem->count=0xFFFFFFFE00000001
-0xFFFFFFFF00000001
RMBThis doesn't make sense, it appears to order a STORE against something else.
Quoted 5 lines
spin_trylock(wait_lock)return
rwsem_try_write_lock(count)spin_unlock(wait_lock)
schedule()
Peter Zijlstra
maintainerQuoted 21 lines · Peter Zijlstra
WTH did you not Cc the people that commented on your patch last time?
Quoted 5 lines · Prateek Sood
If a spinner is present, there is a chance that the load of
rwsem_has_spinner()inrwsem_wake()can be reordered with respect to decrement of rwsem count in__up_write()leading to wakeup being missed.Quoted 11 lines
spinning writer up_write caller --------------- ----------------------- [S] osq_unlock() [L] osq spin_lock(wait_lock) sem->count=0xFFFFFFFF00000001 +0xFFFFFFFF00000000 count=sem->count MB sem->count=0xFFFFFFFE00000001 -0xFFFFFFFF00000001 RMB
Quoted 8 lines
This doesn't make sense, it appears to order a STORE against something else.
Quoted 5 lines
spin_trylock(wait_lock)return
rwsem_try_write_lock(count)spin_unlock(wait_lock)
schedule()
Is this what you wanted to write?
--- kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)
kernel/locking/rwsem-xadd.c +27 -0
@@ -613,6 +613,33 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)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, 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
Peter Zijlstra
maintainerQuoted 25 lines · Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
WTH did you not Cc the people that commented on your patch last time?
Quoted 5 lines · Prateek Sood
If a spinner is present, there is a chance that the load of
rwsem_has_spinner()inrwsem_wake()can be reordered with respect to decrement of rwsem count in__up_write()leading to wakeup being missed.Quoted 11 lines
spinning writer up_write caller --------------- ----------------------- [S] osq_unlock() [L] osq spin_lock(wait_lock) sem->count=0xFFFFFFFF00000001 +0xFFFFFFFF00000000 count=sem->count MB sem->count=0xFFFFFFFE00000001 -0xFFFFFFFF00000001 RMBThis doesn't make sense, it appears to order a STORE against something else.
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines
spin_trylock(wait_lock)return
rwsem_try_write_lock(count)spin_unlock(wait_lock)
schedule()Is this what you wanted to write?
And ideally there should be a comment near the atomic_long_add_return() in __rwsem_down_write_failed_common() to indicate we rely on the implied smp_mb() before it -- just in case someone goes and makes it atomic_long_add_return_relaxed().
And I suppose someone should look at the waiting branch of that thing too.. because I'm not sure what happens if waiting is true but count isn't big enough.
I bloody hate the rwsem code, that BIAS stuff forever confuses me. I have a start at rewriting the thing to put the owner in the lock word just like we now do for mutex, but never seem to get around to finishing it.
Quoted 42 lines
--- kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)kernel/locking/rwsem-xadd.c +27
-0@@ -613,6 +613,33 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)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, 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
Quoted 82 lines · Peter Zijlstra
Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
WTH did you not Cc the people that commented on your patch last time?
Quoted 5 lines · Prateek Sood
If a spinner is present, there is a chance that the load of
rwsem_has_spinner()inrwsem_wake()can be reordered with respect to decrement of rwsem count in__up_write()leading to wakeup being missed.Quoted 11 lines
spinning writer up_write caller --------------- ----------------------- [S] osq_unlock() [L] osq spin_lock(wait_lock) sem->count=0xFFFFFFFF00000001 +0xFFFFFFFF00000000 count=sem->count MB sem->count=0xFFFFFFFE00000001 -0xFFFFFFFF00000001 RMBThis doesn't make sense, it appears to order a STORE against something else.
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines
spin_trylock(wait_lock)return
rwsem_try_write_lock(count)spin_unlock(wait_lock)
schedule()Is this what you wanted to write?
And ideally there should be a comment near the
atomic_long_add_return()in__rwsem_down_write_failed_common()to indicate we rely on the impliedsmp_mb()before it -- just in case someone goes and makes itatomic_long_add_return_relaxed().And I suppose someone should look at the waiting branch of that thing too.. because I'm not sure what happens if waiting is true but count isn't big enough.
I bloody hate the rwsem code, that BIAS stuff forever confuses me. I have a start at rewriting the thing to put the owner in the lock word just like we now do for mutex, but never seem to get around to finishing it.
Quoted 34 lines
--- kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)kernel/locking/rwsem-xadd.c +22
-0@@ -613,6 +613,33 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)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 +*
Quoted 8 lines
kernel/locking/rwsem-xadd.c struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) · line 645
Quoted 8 lines
kernel/locking/rwsem-xadd.c +5
-0+* exists (r0=1 /\ r1=0) +*/ +smp_rmb (); + +/* * If a spinner is present, 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
Thanks Peter for your suggestion on comments.
I will resend the patch with updated comments
Signature · 3 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc., is a member of Code Aurora Forum, a Linux Foundation Collaborative Project