[PATCH 0/2] locking/mutex: Enable optimistic spinning of lock waiter

[PATCH 0/2] locking/mutex: Enable optimistic spinning of lock waiter

[Waiman Long]

This patchset is a variant of PeterZ's "locking/mutex: Avoid spinner
vs waiter starvation" patch. The major difference is that the
waiter-spinner won't enter into the OSQ used by the spinners. Instead,
it will spin directly on the lock in parallel with the queue head
of the OSQ. So there will be a bit more cacheline contention on the
lock cacheline, but that shouldn't cause noticeable impact on system
performance.

This patchset tries to address 2 issues with Peter's patch:

 1) Ding Tianhong still find that hanging task could happen in some cases.
 2) Jason Low found that there was performance regression for some AIM7
    workloads.

By making the waiter-spinner to spin directly on the mutex, it will
increase the chance for the waiter-spinner to get the lock instead
of waiting in the OSQ for its turn.

My own test on a 4-socket E7-4820 v3 system showed a regression of
about 4% in the high_systime workload with Peter's patch which this
new patch effectively eliminates.

Waiman Long (2):
  locking/mutex: Add waiter parameter to mutex_optimistic_spin()
  locking/mutex: Enable optimistic spinning of woken task in wait queue

 kernel/locking/mutex.c |   68 ++++++++++++++++++++++++++++++++++-------------
 1 files changed, 49 insertions(+), 19 deletions(-)

[PATCH 1/2] locking/mutex: Add waiter parameter to mutex_optimistic_spin()

[Waiman Long]

This patch adds a new waiter parameter to the mutex_optimistic_spin()
function to prepare it to be used by a waiter-spinner that doesn't
need to go into the OSQ as there can only be one waiter-spinner which
is the head of the waiting queue.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
---
 kernel/locking/mutex.c |   55 ++++++++++++++++++++++++++++++++---------------
 1 files changed, 37 insertions(+), 18 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 0551c21..3c41448 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -273,11 +273,15 @@ static inline int mutex_can_spin_on_owner(struct mutex *lock)
 
 /*
  * Atomically try to take the lock when it is available
+ *
+ * For waiter-spinner, the count needs to be set to -1 first which will be
+ * cleared to 0 later on if the list becomes empty. For regular spinner,
+ * the count will be set to 0.
  */
-static inline bool mutex_try_to_acquire(struct mutex *lock)
+static inline bool mutex_try_to_acquire(struct mutex *lock, int waiter)
 {
 	return !mutex_is_locked(lock) &&
-		(atomic_cmpxchg_acquire(&lock->count, 1, 0) == 1);
+		(atomic_cmpxchg_acquire(&lock->count, 1, waiter ? -1 : 0) == 1);
 }
 
 /*
@@ -302,22 +306,33 @@ static inline bool mutex_try_to_acquire(struct mutex *lock)
  *
  * Returns true when the lock was taken, otherwise false, indicating
  * that we need to jump to the slowpath and sleep.
+ *
+ * The waiter flag is set to true if the spinner is a waiter in the wait
+ * queue. It doesn't go into OSQ as there can be only one waiter at the
+ * head of the queue spinning. It is possible that both head waiter and
+ * the head of the OSQ spinning on the lock. So there may be a bit more
+ * cacheline contention in this case. The waiter needs to set the lock
+ * to -1 instead of 0 on lock acquisition.
  */
 static bool mutex_optimistic_spin(struct mutex *lock,
-				  struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx)
+				  struct ww_acquire_ctx *ww_ctx,
+				  const bool use_ww_ctx, int waiter)
 {
 	struct task_struct *task = current;
+	bool acquired = false;
 
-	if (!mutex_can_spin_on_owner(lock))
-		goto done;
+	if (!waiter) {
+		if (!mutex_can_spin_on_owner(lock))
+			goto done;
 
-	/*
-	 * In order to avoid a stampede of mutex spinners trying to
-	 * acquire the mutex all at once, the spinners need to take a
-	 * MCS (queued) lock first before spinning on the owner field.
-	 */
-	if (!osq_lock(&lock->osq))
-		goto done;
+		/*
+		 * In order to avoid a stampede of mutex spinners trying to
+		 * acquire the mutex all at once, the spinners need to take a
+		 * MCS (queued) lock first before spinning on the owner field.
+		 */
+		if (!osq_lock(&lock->osq))
+			goto done;
+	}
 
 	while (true) {
 		struct task_struct *owner;
@@ -347,7 +362,7 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 			break;
 
 		/* Try to acquire the mutex if it is unlocked. */
-		if (mutex_try_to_acquire(lock)) {
+		if (mutex_try_to_acquire(lock, waiter)) {
 			lock_acquired(&lock->dep_map, ip);
 
 			if (use_ww_ctx) {
@@ -358,8 +373,8 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 			}
 
 			mutex_set_owner(lock);
-			osq_unlock(&lock->osq);
-			return true;
+			acquired = true;
+			break;
 		}
 
 		/*
@@ -380,7 +395,10 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 		cpu_relax_lowlatency();
 	}
 
-	osq_unlock(&lock->osq);
+	if (!waiter)
+		osq_unlock(&lock->osq);
+	if (acquired || waiter)
+		return acquired;
 done:
 	/*
 	 * If we fell out of the spin path because of need_resched(),
@@ -400,7 +418,8 @@ done:
 }
 #else
 static bool mutex_optimistic_spin(struct mutex *lock,
-				  struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx)
+				  struct ww_acquire_ctx *ww_ctx,
+				  const bool use_ww_ctx, int waiter)
 {
 	return false;
 }
@@ -517,7 +536,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	preempt_disable();
 	mutex_acquire_nest(&lock->dep_map, subclass, 0, nest_lock, ip);
 
-	if (mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx)) {
+	if (mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, false)) {
 		/* got the lock, yay! */
 		preempt_enable();
 		return 0;
-- 
1.7.1

[PATCH 2/2] locking/mutex: Enable optimistic spinning of woken task in wait queue

[Waiman Long]

Ding Tianhong reported a live-lock situation where a constant stream
of incoming optimistic spinners blocked a task in the wait list from
getting the mutex.

This patch attempts to fix this live-lock condition by enabling the
woken task in the wait queue to enter into an optimistic spinning
loop itself in parallel with the regular spinners in the OSQ. This
should prevent the live-lock condition from happening.

Running the AIM7 benchmarks on a 4-socket E7-4820 v3 system (with ext4
filesystem), the additional spinning of the waiter-spinning improved
performance for the following workloads at high user count:

  Workload	% Improvement
  --------	-------------
  alltests	    3.9%
  disk		    3.4%
  fserver	    2.0%
  long		    3.8%
  new_fserver	   10.5%

The other workloads were about the same as before.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 kernel/locking/mutex.c |   13 ++++++++++++-
 1 files changed, 12 insertions(+), 1 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 3c41448..d29efac 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -531,6 +531,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	bool  acquired = false;	/* True if the lock is acquired */
 	int ret;
 
 	preempt_disable();
@@ -561,7 +562,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	lock_contended(&lock->dep_map, ip);
 
-	for (;;) {
+	while (!acquired) {
 		/*
 		 * Lets try to take the lock again - this is needed even if
 		 * we get here for the first time (shortly after failing to
@@ -596,6 +597,12 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		/* didn't get the lock, go to sleep: */
 		spin_unlock_mutex(&lock->wait_lock, flags);
 		schedule_preempt_disabled();
+
+		/*
+		 * Optimistically spinning on the mutex without the wait lock
+		 */
+		acquired = mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
+						 true);
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 	__set_task_state(task, TASK_RUNNING);
@@ -606,6 +613,9 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		atomic_set(&lock->count, 0);
 	debug_mutex_free_waiter(&waiter);
 
+	if (acquired)
+		goto unlock;
+
 skip_wait:
 	/* got the lock - cleanup and rejoice! */
 	lock_acquired(&lock->dep_map, ip);
@@ -616,6 +626,7 @@ skip_wait:
 		ww_mutex_set_context_slowpath(ww, ww_ctx);
 	}
 
+unlock:
 	spin_unlock_mutex(&lock->wait_lock, flags);
 	preempt_enable();
 	return 0;
-- 
1.7.1

Re: [PATCH 0/2] locking/mutex: Enable optimistic spinning of lock waiter

[Jason Low]

On Tue, 2016-02-09 at 14:47 -0500, Waiman Long wrote:
> This patchset is a variant of PeterZ's "locking/mutex: Avoid spinner
> vs waiter starvation" patch. The major difference is that the
> waiter-spinner won't enter into the OSQ used by the spinners. Instead,
> it will spin directly on the lock in parallel with the queue head
> of the OSQ. So there will be a bit more cacheline contention on the
> lock cacheline, but that shouldn't cause noticeable impact on system
> performance.
> 
> This patchset tries to address 2 issues with Peter's patch:
> 
>  1) Ding Tianhong still find that hanging task could happen in some cases.
>  2) Jason Low found that there was performance regression for some AIM7
>     workloads.

This might help address the hang that Ding reported.

Performance wise, this patchset reduced AIM7 fserver throughput on the 8
socket machine by -70%+ at 1000+ users.

                | fserver JPM
-----------------------------
baseline	| ~450000
Peter's patch	| ~410000
This patchset	| ~100000

My guess is that waiters spinning/acquiring the lock is less efficient,
and this patchset further increases the chance for waiters to
spin/acquire the lock over the fastpath optimistic spinners.

Jason

Re: [PATCH 0/2] locking/mutex: Enable optimistic spinning of lock waiter

[Waiman Long]

On 02/09/2016 04:44 PM, Jason Low wrote:
> On Tue, 2016-02-09 at 14:47 -0500, Waiman Long wrote:
>> This patchset is a variant of PeterZ's "locking/mutex: Avoid spinner
>> vs waiter starvation" patch. The major difference is that the
>> waiter-spinner won't enter into the OSQ used by the spinners. Instead,
>> it will spin directly on the lock in parallel with the queue head
>> of the OSQ. So there will be a bit more cacheline contention on the
>> lock cacheline, but that shouldn't cause noticeable impact on system
>> performance.
>>
>> This patchset tries to address 2 issues with Peter's patch:
>>
>>   1) Ding Tianhong still find that hanging task could happen in some cases.
>>   2) Jason Low found that there was performance regression for some AIM7
>>      workloads.
> This might help address the hang that Ding reported.
>
> Performance wise, this patchset reduced AIM7 fserver throughput on the 8
> socket machine by -70%+ at 1000+ users.
>
>                  | fserver JPM
> -----------------------------
> baseline	| ~450000
> Peter's patch	| ~410000
> This patchset	| ~100000
>
> My guess is that waiters spinning/acquiring the lock is less efficient,
> and this patchset further increases the chance for waiters to
> spin/acquire the lock over the fastpath optimistic spinners.
>
> Jason
>

That was just a configuration error as the CPU scaling governor wasn't 
set to performance. With the performance scaling governor, the 
patchset's performance was comparable to Peter's patch.

Cheers,
Longman