locking/mutex: Prevent lock starvation when spinning is enabled

Hi Jason,

[auto build test ERROR on tip/locking/core]
[also build test ERROR on v4.8-rc1 next-20160809]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url: https://github.com/0day-ci/linux/commits/Jason-Low/locking-mutex-Prevent-lock-starvation-when-spinning-is-enabled/20160811-034327
config: x86_64-randconfig-x013-201632 (attached as .config)
compiler: gcc-6 (Debian 6.1.1-9) 6.1.1 20160705 reproduce:

        # save the attached .config to linux build tree
        make ARCH=x86_64 

All error/warnings (new ones prefixed by >>):

kernel/locking/mutex.c: In function 'do_yield_to_waiter':

Quoted 1 line

Quoted 1 line

kernel/locking/mutex.c:441:10: error: 'struct mutex' has no member named 'yield_to_waiter'

     if (lock->yield_to_waiter != true)
             ^~
   kernel/locking/mutex.c:442:7: error: 'struct mutex' has no member named 'yield_to_waiter'
      lock->yield_to_waiter = true;
          ^~
   kernel/locking/mutex.c: In function 'clear_yield_to_waiter':
   kernel/locking/mutex.c:447:6: error: 'struct mutex' has no member named 'yield_to_waiter'
     lock->yield_to_waiter = false;
         ^~
   kernel/locking/mutex.c: In function 'need_yield_to_waiter':
   kernel/locking/mutex.c:452:13: error: 'struct mutex' has no member named 'yield_to_waiter'
     return lock->yield_to_waiter;
                ^~

Imre reported an issue where threads are getting starved when trying to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed sleeping on a mutex because other threads can continually steal the lock in the fastpath and/or through optimistic spinning.

Waiman has developed patches that allow waiters to return to optimistic spinning, thus reducing the probability that starvation occurs. However, Imre still sees this starvation problem in the workloads when optimistic spinning is disabled.

This patch adds an additional boolean to the mutex that gets used in the CONFIG_SMP && !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies whether or not other threads need to yield to a waiter and gets set when a waiter spends too much time waiting for the mutex. The threshold is currently set to 16 wakeups, and once the wakeup threshold is exceeded, other threads must yield to the top waiter. The flag gets cleared immediately after the top waiter acquires the mutex.

kernel/locking/mutex.c +3 -2

@@ -917,11 +976,12 @@ EXPORT_SYMBOL(mutex_trylock);
 int __sched
 __ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
 {
-	int ret;
+	int ret = 1;
 
 	might_sleep();
 
-	ret = __mutex_fastpath_lock_retval(&lock->base.count);
+	if (!need_yield_to_waiter(lock))
+		ret = __mutex_fastpath_lock_retval(&lock->base.count);
 
 	if (likely(!ret)) {
 		ww_mutex_set_context_fastpath(lock, ctx);

Imre reported an issue where threads are getting starved when trying to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed sleeping on a mutex because other threads can continually steal the lock in the fastpath and/or through optimistic spinning.

Waiman has developed patches that allow waiters to return to optimistic spinning, thus reducing the probability that starvation occurs. However, Imre still sees this starvation problem in the workloads when optimistic spinning is disabled.

This patch adds an additional boolean to the mutex that gets used in the CONFIG_SMP&& !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies whether or not other threads need to yield to a waiter and gets set when a waiter spends too much time waiting for the mutex. The threshold is currently set to 16 wakeups, and once the wakeup threshold is exceeded, other threads must yield to the top waiter. The flag gets cleared immediately after the top waiter acquires the mutex.

This prevents waiters from getting starved without sacrificing much much performance, as lock stealing is still allowed and only temporarily disabled when it is detected that a waiter has been waiting for too long.

Reported-by Imre Deak<[email protected]>

Signed-off-by Jason Low<[email protected]>

---
v1->v2:
- Addressed Waiman's suggestions of needing the yield_to_waiter flag only in the CONFIG_SMP case.

- Make sure to only clear the flag if the thread is the top waiter.

- Refactor code to clear flag into an inline function.

- Rename 'loops' variable name to 'wakeups'.

  include/linux/mutex.h  |  2 ++
  kernel/locking/mutex.c | 83 +++++++++++++++++++++++++++++++++++++++++++-------
  2 files changed, 74 insertions(+), 11 deletions(-)

include/linux/mutex.h +2 -0

index 2cb7531..5643a233 100644
@@ -57,6 +57,8 @@ struct mutex {
  #endif
  #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
  	struct optimistic_spin_queue osq; /* Spinner MCS lock */
+#elif defined(CONFIG_SMP)
+	bool yield_to_waiter; /* Prevent starvation when spinning disabled */
  #endif
  #ifdef CONFIG_DEBUG_MUTEXES
  	void			*magic;

kernel/locking/mutex.c +41 -1

index a70b90d..faf31a0 100644
@@ -55,6 +55,8 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
  	mutex_clear_owner(lock);
  #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
  	osq_lock_init(&lock->osq);
+#elif defined(CONFIG_SMP)
+	lock->yield_to_waiter = false;
  #endif
 
  	debug_mutex_init(lock, name, key);

@@ -71,6 +73,9 @@ EXPORT_SYMBOL(__mutex_init);
   */
  __visible void __sched __mutex_lock_slowpath(atomic_t *lock_count);
 
+
+static inline bool need_yield_to_waiter(struct mutex *lock);
+
  /**
   * mutex_lock - acquire the mutex
   * @lock: the mutex to be acquired

@@ -99,7 +104,10 @@ void __sched mutex_lock(struct mutex *lock)
  	 * The locking fastpath is the 1->0 transition from
  	 * 'unlocked' into 'locked' state.
  	 */
-	__mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
+	if (!need_yield_to_waiter(lock))
+		__mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
+	else
+		__mutex_lock_slowpath(&lock->count);
  	mutex_set_owner(lock);
  }
 

@@ -398,12 +406,51 @@ done:
 
  	return false;
  }
+
+static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups)
+{
+	return;
+}
+
+static inline void clear_yield_to_waiter(struct mutex *lock)
+{
+	return;
+}
+
+static inline bool need_yield_to_waiter(struct mutex *lock)
+{
+	return false;
+}
+
  #else
  static bool mutex_optimistic_spin(struct mutex *lock,
  				  struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx)
  {
  	return false;
  }
+
+#define MUTEX_WAKEUP_THRESHOLD 16
+
+static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups)
+{
+	*wakeups += 1;
+
+	if (*wakeups<  MUTEX_WAKEUP_THRESHOLD)
+		return;
+
+	if (lock->yield_to_waiter != true)
+		lock->yield_to_waiter = true;
+}
+
+static inline void clear_yield_to_waiter(struct mutex *lock)
+{

Quoted 37 lines · Jason Low

kernel/locking/mutex.c +31 -0

+static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups)
+{
+	return;
+}
+
+static inline void clear_yield_to_waiter(struct mutex *lock)
+{
+	return;
+}
+
+static inline bool need_yield_to_waiter(struct mutex *lock)
+{
+	return false;
+}
+
  #else
  static bool mutex_optimistic_spin(struct mutex *lock,
  				  struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx)
  {
  	return false;
  }
+
+#define MUTEX_WAKEUP_THRESHOLD 16
+
+static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups)
+{
+	*wakeups += 1;
+
+	if (*wakeups<  MUTEX_WAKEUP_THRESHOLD)
+		return;
+
+	if (lock->yield_to_waiter != true)
+		lock->yield_to_waiter = true;
+}
+
+static inline void clear_yield_to_waiter(struct mutex *lock)
+{

kernel/locking/mutex.c done:

Quoted 10 lines

kernel/locking/mutex.c +7 -0

+	lock->yield_to_waiter = false;
+}
+
+static inline bool need_yield_to_waiter(struct mutex *lock)
+{
+	return lock->yield_to_waiter;
+}
  #endif
 
  _

The *yield* helper functions should be in a separate conditional compilation block as the declaration of yield_to_waiter may not match the helper functions with certain combination of config variables.

Something like

#if !defined(CONFIG_MUTEX_SPIN_ON_OWNER) && defined(CONFIG_SMP)
...
#else
...
#endif

Imre reported an issue where threads are getting starved when trying to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed sleeping on a mutex because other threads can continually steal the lock in the fastpath and/or through optimistic spinning.

Waiman has developed patches that allow waiters to return to optimistic spinning, thus reducing the probability that starvation occurs. However, Imre still sees this starvation problem in the workloads when optimistic spinning is disabled.

This patch adds an additional boolean to the mutex that gets used in the CONFIG_SMP && !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies whether or not other threads need to yield to a waiter and gets set when a waiter spends too much time waiting for the mutex. The threshold is currently set to 16 wakeups, and once the wakeup threshold is exceeded, other threads must yield to the top waiter. The flag gets cleared immediately after the top waiter acquires the mutex.

2016-08-11 2:44 GMT+08:00 Jason Low <[email protected]>:

Quoted 10 lines

Imre reported an issue where threads are getting starved when trying to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed sleeping on a mutex because other threads can continually steal the lock in the fastpath and/or through optimistic spinning.

Waiman has developed patches that allow waiters to return to optimistic spinning, thus reducing the probability that starvation occurs. However, Imre still sees this starvation problem in the workloads when optimistic spinning is disabled.

Quoted 7 lines

This patch adds an additional boolean to the mutex that gets used in the CONFIG_SMP && !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies whether or not other threads need to yield to a waiter and gets set when a waiter spends too much time waiting for the mutex. The threshold is currently set to 16 wakeups, and once the wakeup threshold is exceeded, other threads must yield to the top waiter. The flag gets cleared immediately after the top waiter acquires the mutex.

There is a subtle difference between this patch and Waiman's. Waiman's patch will boost any waiter-spinner which is woken up, however, this patch will boost the top waiter once the number of any waiter-spinners woken up reaches the threshold.

We can't get any benefit if the
resource holder which top waiter is waiting for still not release the resource.

Hi Wanpeng,

Quoted 19 lines · Wanpeng Li

2016-08-11 2:44 GMT+08:00 Jason Low <[email protected]>:

Quoted 10 lines

Imre reported an issue where threads are getting starved when trying to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed sleeping on a mutex because other threads can continually steal the lock in the fastpath and/or through optimistic spinning.

Waiman has developed patches that allow waiters to return to optimistic spinning, thus reducing the probability that starvation occurs. However, Imre still sees this starvation problem in the workloads when optimistic spinning is disabled.

Quoted 7 lines

This patch adds an additional boolean to the mutex that gets used in the CONFIG_SMP && !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies whether or not other threads need to yield to a waiter and gets set when a waiter spends too much time waiting for the mutex. The threshold is currently set to 16 wakeups, and once the wakeup threshold is exceeded, other threads must yield to the top waiter. The flag gets cleared immediately after the top waiter acquires the mutex.

Quoted 4 lines

There is a subtle difference between this patch and Waiman's. Waiman's patch will boost any waiter-spinner which is woken up, however, this patch will boost the top waiter once the number of any waiter-spinners woken up reaches the threshold.

Correct, since when spinning is disabled, we still want to generally allow other threads to steal the lock even if there are waiters in order to keep performance good, and only yield the lock when a waiter is getting 'starved'.

Quoted 3 lines

We can't get any benefit if the
resource holder which top waiter is waiting for still not release the resource.

If the resource holder does not release the resource, that sounds like an issue with the lock holder.

Unless you're referring to how this doesn't provide immediate benefit to the top waiter,

in which case, I think that is okay since the goal of
the patch is to prevent starvation. We tried disabling 'lock stealing' anytime there are waiters and that proved to reduce performance by quite a bit in some workloads.

kernel/locking/mutex.c +0 -0

@@ -556,8 +604,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * other waiters. We only attempt the xchg if the count is
 		 * non-negative in order to avoid unnecessary xchg operations:
 		 */

Quoted 13 lines · Jason Low

kernel/locking/mutex.c +5 -1

@@ -556,8 +604,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * other waiters. We only attempt the xchg if the count is
 		 * non-negative in order to avoid unnecessary xchg operations:
 		 */
-		if (atomic_read(&lock->count) >= 0 &&
+		if ((!need_yield_to_waiter(lock) || wakeups > 1) &&
+		    atomic_read(&lock->count) >= 0 &&
 		    (atomic_xchg_acquire(&lock->count, -1) == 1))
+			if (wakeups > 1)
+				clear_yield_to_waiter(lock);
+
 			break;
 

Review __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, · line 615

Quoted 1 line

(quoted diff) +0 -0

 		/*

There's some { } gone missing there...

Also, I think I'll change it to avoid that extra wakeups > 1 condition..

Quoted 14 lines · Peter Zijlstra

Quoted 13 lines · Jason Low

kernel/locking/mutex.c +5 -1

@@ -556,8 +604,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		 * other waiters. We only attempt the xchg if the count is
 		 * non-negative in order to avoid unnecessary xchg operations:
 		 */
-		if (atomic_read(&lock->count) >= 0 &&
+		if ((!need_yield_to_waiter(lock) || wakeups > 1) &&
+		    atomic_read(&lock->count) >= 0 &&
 		    (atomic_xchg_acquire(&lock->count, -1) == 1))
+			if (wakeups > 1)
+				clear_yield_to_waiter(lock);
+
 			break;
 

Quoted 5 lines

Review __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, · line 615

Quoted 1 line

(quoted diff) +0 -0

 		/*

There's some { } gone missing there...

Also, I think I'll change it to avoid that extra wakeups > 1 condition..

Also, its broken, even if we should not trylock, we should still very much xchg(-1) to mark the lock as having waiters.

include/linux/mutex.h struct mutex { · line 64

Quoted 13 lines · Jason Low

include/linux/mutex.h +2 -0

index 2cb7531..5643a233 100644
@@ -57,6 +57,8 @@ struct mutex {
  #endif
  #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
  	struct optimistic_spin_queue osq; /* Spinner MCS lock */
+#elif defined(CONFIG_SMP)
+	bool yield_to_waiter; /* Prevent starvation when spinning disabled */
  #endif
  #ifdef CONFIG_DEBUG_MUTEXES
  	void			*magic;

Isn't this also possible on !SMP&& PREEMPT ?