Skip to contentSkip to conversation

rwsem: fix missed wakeup due to reordering of load

PATCH In review Prateek Sood 2 participants 5 messages Aug 23, 2017 – Sep 7, 2017 Locking primitives

lore
Share & tools
lore
#0 lore raw

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
index 34e727f..5c687f6 100644
@@ -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.
maintainer
#1 lore raw

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() in rwsem_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

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()

maintainer
#2 lore raw
Quoted 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() in rwsem_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
index 02f660666ab8..813b5d3654ce 100644
@@ -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
maintainer
#3 lore raw
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() in rwsem_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

This 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
index 02f660666ab8..813b5d3654ce 100644
@@ -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
#4 lore raw
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() in rwsem_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

This 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 34 lines
---
 kernel/locking/rwsem-xadd.c | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
kernel/locking/rwsem-xadd.c +22 -0
index 02f660666ab8..813b5d3654ce 100644
@@ -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