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
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 | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+)
kernel/locking/rwsem-xadd.c +34 -0
@@ -585,6 +585,40 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)unsigned long flags;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 +* 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() here is to make sure that the spinner state is +* consulted after sem->count is updated in up_write context. +*/ +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
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.
Waiman Long
reviewerQuoted 28 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.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 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()andrwsem_has_spinner()inrwsem_wake()can cause missing of wakeup inup_write()context. In spinning writer,sem->countand local variable count is0XFFFFFFFE00000001. It would result inrwsem_try_write_lock()failing to acquire rwsem and spinning writer going to sleep inrwsem_down_write_failed().
Quoted 4 lines
The
smp_rmb()will make sure that the spinner state is consulted aftersem->countis updated inup_writecontext.Signed-off-by Prateek Sood <[email protected]>
Did you actually observe that the reordering happens?
I am not sure if some architectures can actually speculatively execute instruction ahead of a branch and then ahead into a function call. I know it can happen if the function call is inlined, but rwsem_wake() will not be inlined into __up_read() or __up_write().
Even if that is the case, I am not sure if smp_rmb() alone is enough to guarantee the ordering as I think it will depend on how the atomic_long_sub_return_release() is implmented.
Cheers,
Longman
Peter Zijlstra
maintainerQuoted 1 line · Waiman Long
atomic_long_sub_return_release()is implmented.
I've not had time to really thing about the problem at hand, but this I can answer:
TSO (x86, s390, sparc): fully serialized
PPC: lwsync; ll/sc (RCpc)
ARM64: ll/sc-release (RCsc)
other: smp_mb(); atomic_sub_return_relaxed();
Quoted 32 lines · Waiman Long
Quoted 31 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.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 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()andrwsem_has_spinner()inrwsem_wake()can cause missing of wakeup inup_write()context. In spinning writer,sem->countand local variable count is0XFFFFFFFE00000001. It would result inrwsem_try_write_lock()failing to acquire rwsem and spinning writer going to sleep inrwsem_down_write_failed().The
smp_rmb()will make sure that the spinner state is consulted aftersem->countis updated inup_writecontext.
Quoted 8 lines
Quoted 1 line
Signed-off-by Prateek Sood <[email protected]>Did you actually observe that the reordering happens?
I am not sure if some architectures can actually speculatively execute instruction ahead of a branch and then ahead into a function call. I know it can happen if the function call is inlined, but
rwsem_wake()will not be inlined into__up_read()or__up_write().
Branches/control dependencies targeting a read do not necessarily preserve program order; this is for example the case for PowerPC and ARM.
I'd not expect more than a compiler barrier from a function call (in fact, not even that if the function happens to be inlined).
Quoted 4 lines
Even if that is the case, I am not sure if
smp_rmb()alone is enough to guarantee the ordering as I think it will depend on how theatomic_long_sub_return_release()is implmented.
AFAICT, the pattern under discussion is MP with:
- a store-release to osq->tail(unlock) followed by a store to sem->count,
separated by a MB (from atomic_long_add_return()) on CPU0;
- a load of sem->count (for atomic_long_sub_return_release()) followed by
a load of osq->tail (rwsem_has_spinner()) on CPU1.
Thus a RMW between the two loads suffices to forbid the weak behaviour.
Andrea
Quoted 4 lines
Cheers,
Longman
Peter Zijlstra
maintainerQuoted 42 lines · Andrea Parri
Quoted 32 lines · Waiman Long
Quoted 31 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.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 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()andrwsem_has_spinner()inrwsem_wake()can cause missing of wakeup inup_write()context. In spinning writer,sem->countand local variable count is0XFFFFFFFE00000001. It would result inrwsem_try_write_lock()failing to acquire rwsem and spinning writer going to sleep inrwsem_down_write_failed().The
smp_rmb()will make sure that the spinner state is consulted aftersem->countis updated inup_writecontext.Quoted 8 lines
Quoted 1 line
Signed-off-by Prateek Sood <[email protected]>Did you actually observe that the reordering happens?
I am not sure if some architectures can actually speculatively execute instruction ahead of a branch and then ahead into a function call. I know it can happen if the function call is inlined, but
rwsem_wake()will not be inlined into__up_read()or__up_write().
Quoted 5 lines
Branches/control dependencies targeting a read do not necessarily preserve program order; this is for example the case for PowerPC and ARM.
I'd not expect more than a compiler barrier from a function call (in fact, not even that if the function happens to be inlined).
Indeed. Reads can be speculated by deep out-of-order CPUs no problem. That's what branch predictors are for.
Quoted 10 lines
Quoted 3 lines
Even if that is the case, I am not sure if
smp_rmb()alone is enough to guarantee the ordering as I think it will depend on how theatomic_long_sub_return_release()is implmented.AFAICT, the pattern under discussion is MP with:
- a store-release to
osq->tail(unlock)followed by a store tosem->count,separated by a MB (from atomic_long_add_return()) on CPU0;- a load of
sem->count(foratomic_long_sub_return_release()) followed by
Which is a regular load, as 'release' only need apply to the store.
Quoted 3 lines
a load of osq->tail (rwsem_has_spinner()) on CPU1.Thus a RMW between the two loads suffices to forbid the weak behaviour.
Agreed.
Peter Zijlstra
maintainerQuoted 29 lines · Prateek Sood
kernel/locking/rwsem-xadd.c +21
-0@@ -585,6 +585,40 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)unsigned long flags;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 +* spin_trylock(wait_lock) +* return +* rwsem_try_write_lock(count) +* spin_unlock(wait_lock) +* schedule()
kernel/locking/rwsem-xadd.c struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) · line 618
Quoted 10 lines
kernel/locking/rwsem-xadd.c +10
-0+* +* 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() here is to make sure that the spinner state is +* consulted after sem->count is updated in up_write context.
I feel that comment can use help.. for example the RMB you add below is not present at all.
kernel/locking/rwsem-xadd.c struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) · line 624
Quoted 6 lines
kernel/locking/rwsem-xadd.c +3
-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
Your patch is whitespace damaged, all the indentation on the + lines is with spaces. Please resend with \t.