Skip to contentSkip to conversation

locking/rwsem: Fix rwsem waiter optimistic spinning problem with RT tasks

PATCH Superseded Waiman Long 4 participants 10 messages Oct 12, 2022 – Oct 14, 2022

Subsystems (2)

v2 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

v2 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
author reviewer
#1 lore raw

PATCH 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.

Fixes d257cc8cb8d5 ("locking/rwsem: Make handoff bit handling more consistent")
---
 kernel/locking/rwsem.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)
kernel/locking/rwsem.c +10 -3
index 44873594de03..3839b38608da 100644
@@ -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
#2 lore raw

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

Since this patch is tested and it covers the mentioned scenario.

Reviewed-and-Tested-by Mukesh Ojha <[email protected]>

-Mukesh

Quoted 37 lines
---
  kernel/locking/rwsem.c | 13 ++++++++++---
  1 file changed, 10 insertions(+), 3 deletions(-)
kernel/locking/rwsem.c +10 -3
index 44873594de03..3839b38608da 100644
@@ -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
  	}
maintainer
#3 lore raw

Re: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath

In reply to Waiman Long
Quoted 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_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.

So why not do a better handoff? Specifically, have the owner set owner to first-waiter instead of NULL ? (like the normal mutex code)

#4 lore raw

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;
}

#5 lore raw

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);
}

author reviewer
#6 lore raw

Re: [PATCH v2 1/2] locking/rwsem: Prevent non-first waiter from spinning in down_write() slowpath

In reply to Peter Zijlstra
Quoted 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

author reviewer
#7 lore raw

Re: [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
     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.

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

author reviewer
#8 lore raw

PATCH v2 2/2 locking/rwsem: Limit # of null owner retries for handoff writer

In reply to 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                     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.

Fixes 91d2a812dfb9 ("locking/rwsem: Make handoff writer optimistically spin on owner")
---
 kernel/locking/rwsem.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
kernel/locking/rwsem.c +16 -2
index 3839b38608da..12eb093328f2 100644
@@ -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
#9 lore raw

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                     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.

Fixes 91d2a812dfb9 ("locking/rwsem: Make handoff writer optimistically spin on owner")
---
  kernel/locking/rwsem.c | 18 ++++++++++++++++--
  1 file changed, 16 insertions(+), 2 deletions(-)
kernel/locking/rwsem.c +3 -2
index 3839b38608da..12eb093328f2 100644
@@ -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.

Reviewed-and-Tested-by Mukesh Ojha <[email protected]>

-Mukesh

Quoted 1 line
kernel/locking/rwsem.c +0 -0
  		schedule();