All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v4 0/3] locking/mutex: Enable optimistic spinning of lock waiter
@ 2016-07-18 20:39 Waiman Long
  2016-07-18 20:39 ` [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() Waiman Long
                   ` (2 more replies)
  0 siblings, 3 replies; 12+ messages in thread
From: Waiman Long @ 2016-07-18 20:39 UTC (permalink / raw)
  To: Ingo Molnar
  Cc: Peter Zijlstra, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, Waiman Long

v3->v4:
 - Replace patch 3 by a new one to add a flag to ensure forward
   progress of the waiter-spinner.

v2->v3:
 - Remove patch 4 as it is not useful.
 - Allow need_resched() check for waiter & add more comments about
   changes to address issues raised by PeterZ.

v1->v2:
 - Set task state to running before doing optimistic spinning.
 - Add 2 more patches to handle possible missed wakeups and wasteful
   spinning in try_to_wake_up() function.

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

Patch 1 modifies the mutex_optimistic_spin() function to enable it
to be called by a waiter-spinner that doesn't need to go into the OSQ.

Patch 2 modifies the mutex locking slowpath to make the waiter call
mutex_optimistic_spin() to do spinning after being waken up.

Patch 3 adds a new flag to give priority to the waiter-spinner to
acquire the lock, thus ensuring forward progress.

Waiman Long (3):
  locking/mutex: Add waiter parameter to mutex_optimistic_spin()
  locking/mutex: Enable optimistic spinning of woken task in wait queue
  locking/mutex: Ensure forward progress of waiter-spinner

 include/linux/mutex.h  |    1 +
 kernel/locking/mutex.c |  116 ++++++++++++++++++++++++++++++++++++------------
 2 files changed, 88 insertions(+), 29 deletions(-)

^ permalink raw reply	[flat|nested] 12+ messages in thread

* [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin()
  2016-07-18 20:39 [PATCH v4 0/3] locking/mutex: Enable optimistic spinning of lock waiter Waiman Long
@ 2016-07-18 20:39 ` Waiman Long
  2016-08-08 17:26   ` Peter Zijlstra
  2016-07-18 20:39 ` [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue Waiman Long
  2016-07-18 20:39 ` [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner Waiman Long
  2 siblings, 1 reply; 12+ messages in thread
From: Waiman Long @ 2016-07-18 20:39 UTC (permalink / raw)
  To: Ingo Molnar
  Cc: Peter Zijlstra, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, Waiman Long, 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 |   66 +++++++++++++++++++++++++++++++++--------------
 1 files changed, 46 insertions(+), 20 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 79d2d76..79fd6b8 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,42 @@ 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. As the waiter has slept for a while, it should have priority to
+ * get the lock over the regular spinners. So going to wait at the end of
+ * the OSQ isn't fair to the waiter. Instead, it will spin on the lock
+ * directly and concurrently with the spinner at the head of the OSQ, if
+ * present. There may be a bit more cacheline contention in this case.
+ * The waiter also 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) {
+		/*
+		 * The purpose of the mutex_can_spin_on_owner() function is
+		 * to eliminate the overhead of osq_lock() and osq_unlock()
+		 * in case spinning isn't possible. As a waiter-spinner
+		 * is not going to take OSQ lock anyway, there is no need
+		 * to call mutex_can_spin_on_owner().
+		 */
+		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 +371,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 +382,8 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 			}
 
 			mutex_set_owner(lock);
-			osq_unlock(&lock->osq);
-			return true;
+			acquired = true;
+			break;
 		}
 
 		/*
@@ -380,14 +404,15 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 		cpu_relax_lowlatency();
 	}
 
-	osq_unlock(&lock->osq);
+	if (!waiter)
+		osq_unlock(&lock->osq);
 done:
 	/*
 	 * If we fell out of the spin path because of need_resched(),
 	 * reschedule now, before we try-lock the mutex. This avoids getting
 	 * scheduled out right after we obtained the mutex.
 	 */
-	if (need_resched()) {
+	if (!acquired && need_resched()) {
 		/*
 		 * We _should_ have TASK_RUNNING here, but just in case
 		 * we do not, make it so, otherwise we might get stuck.
@@ -396,11 +421,12 @@ done:
 		schedule_preempt_disabled();
 	}
 
-	return false;
+	return acquired;
 }
 #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;
 }
@@ -520,7 +546,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

^ permalink raw reply related	[flat|nested] 12+ messages in thread

* [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue
  2016-07-18 20:39 [PATCH v4 0/3] locking/mutex: Enable optimistic spinning of lock waiter Waiman Long
  2016-07-18 20:39 ` [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() Waiman Long
@ 2016-07-18 20:39 ` Waiman Long
  2016-08-08 17:29   ` Peter Zijlstra
  2016-07-18 20:39 ` [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner Waiman Long
  2 siblings, 1 reply; 12+ messages in thread
From: Waiman Long @ 2016-07-18 20:39 UTC (permalink / raw)
  To: Ingo Molnar
  Cc: Peter Zijlstra, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, 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 |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 79fd6b8..adb21aa 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -535,6 +535,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;
 
 	if (use_ww_ctx) {
@@ -571,7 +572,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
@@ -606,6 +607,15 @@ __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
+		 * The state has to be set to running to avoid another waker
+		 * spinning on the on_cpu flag while the woken waiter is
+		 * spinning on the mutex.
+		 */
+		acquired = mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
+						 true);
 		spin_lock_mutex(&lock->wait_lock, flags);
 	}
 	__set_task_state(task, TASK_RUNNING);
@@ -616,6 +626,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);
@@ -626,6 +639,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

^ permalink raw reply related	[flat|nested] 12+ messages in thread

* [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner
  2016-07-18 20:39 [PATCH v4 0/3] locking/mutex: Enable optimistic spinning of lock waiter Waiman Long
  2016-07-18 20:39 ` [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() Waiman Long
  2016-07-18 20:39 ` [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue Waiman Long
@ 2016-07-18 20:39 ` Waiman Long
  2016-08-08 17:37   ` Peter Zijlstra
  2 siblings, 1 reply; 12+ messages in thread
From: Waiman Long @ 2016-07-18 20:39 UTC (permalink / raw)
  To: Ingo Molnar
  Cc: Peter Zijlstra, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, Waiman Long

As both an optimistic spinner and a waiter-spinner (a woken task from
the wait queue spinning) can be spinning on the lock at the same time,
we cannot ensure forward progress for the waiter-spinner. Therefore,
it is possible for the waiter-spinner to be starved of getting the
lock, though not likely.

This patch adds a flag to indicate that a waiter-spinner is
spinning and hence has priority over the acquisition of the lock. A
waiter-spinner sets this flag while spinning. An optimistic spinner
will check this flag and yield if set. This essentially makes the
waiter-spinner jump to the head of the optimistic spinning queue to
acquire the lock.

There will be no increase in size for the mutex structure for 64-bit
architectures. For 32-bit architectures, there will be a size increase
of 4 bytes.

Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
---
 include/linux/mutex.h  |    1 +
 kernel/locking/mutex.c |   36 +++++++++++++++++++++++++++---------
 2 files changed, 28 insertions(+), 9 deletions(-)

diff --git a/include/linux/mutex.h b/include/linux/mutex.h
index 2cb7531..f8e91ad 100644
--- a/include/linux/mutex.h
+++ b/include/linux/mutex.h
@@ -57,6 +57,7 @@ struct mutex {
 #endif
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
 	struct optimistic_spin_queue osq; /* Spinner MCS lock */
+	int waiter_spinning;
 #endif
 #ifdef CONFIG_DEBUG_MUTEXES
 	void			*magic;
diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index adb21aa..52225bd 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -55,6 +55,7 @@ __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);
+	lock->waiter_spinning = false;
 #endif
 
 	debug_mutex_init(lock, name, key);
@@ -341,9 +342,21 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 		 */
 		if (!osq_lock(&lock->osq))
 			goto done;
+	} else {
+		/*
+		 * Turn on the waiter spinning flag to discourage the spinner
+		 * from getting the lock.
+		 */
+		lock->waiter_spinning = true;
 	}
 
-	while (true) {
+	/*
+	 * The cpu_relax_lowlatency() call is a compiler barrier which forces
+	 * everything in this loop to be re-loaded. We don't need memory
+	 * barriers as we'll eventually observe the right values at the cost
+	 * of a few extra spins.
+	 */
+	for (;; cpu_relax_lowlatency()) {
 		struct task_struct *owner;
 
 		if (use_ww_ctx && ww_ctx->acquired > 0) {
@@ -363,6 +376,17 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 		}
 
 		/*
+		 * For regular opt-spinner, it waits until the waiter_spinning
+		 * flag isn't set. This will ensure forward progress for
+		 * the waiter spinner.
+		 */
+		if (!waiter && READ_ONCE(lock->waiter_spinning)) {
+			if (need_resched())
+				break;
+			continue;
+		}
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
@@ -394,18 +418,12 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 		 */
 		if (!owner && (need_resched() || rt_task(task)))
 			break;
-
-		/*
-		 * The cpu_relax() call is a compiler barrier which forces
-		 * everything in this loop to be re-loaded. We don't need
-		 * memory barriers as we'll eventually observe the right
-		 * values at the cost of a few extra spins.
-		 */
-		cpu_relax_lowlatency();
 	}
 
 	if (!waiter)
 		osq_unlock(&lock->osq);
+	else
+		lock->waiter_spinning = false;
 done:
 	/*
 	 * If we fell out of the spin path because of need_resched(),
-- 
1.7.1

^ permalink raw reply related	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin()
  2016-07-18 20:39 ` [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() Waiman Long
@ 2016-08-08 17:26   ` Peter Zijlstra
  2016-08-09 17:36     ` Waiman Long
  0 siblings, 1 reply; 12+ messages in thread
From: Peter Zijlstra @ 2016-08-08 17:26 UTC (permalink / raw)
  To: Waiman Long
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, Waiman Long

On Mon, Jul 18, 2016 at 04:39:24PM -0400, Waiman Long wrote:
> @@ -302,22 +306,42 @@ 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. As the waiter has slept for a while, it should have priority to
> + * get the lock over the regular spinners. So going to wait at the end of
> + * the OSQ isn't fair to the waiter.

If the OSQ lock were a full FIFO it would in fact be fair, but its not
and things can drop out the middle and go (back) to sleep.

This has nothing to do with the end or not.

> Instead, it will spin on the lock
> + * directly and concurrently with the spinner at the head of the OSQ, if
> + * present. 

Note that this isn't starvation proof in any way.

>     There may be a bit more cacheline contention in this case.

This is relevant how ?

> + * The waiter also needs to set the lock to -1 instead of 0 on lock
> + * acquisition.

This is unrelated to the previous bits and thus should not be in the
same paragraph. Also, a 'why' would be more helpful.

>   */
>  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)
>  {

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue
  2016-07-18 20:39 ` [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue Waiman Long
@ 2016-08-08 17:29   ` Peter Zijlstra
  2016-08-09 17:49     ` Waiman Long
  0 siblings, 1 reply; 12+ messages in thread
From: Peter Zijlstra @ 2016-08-08 17:29 UTC (permalink / raw)
  To: Waiman Long
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On Mon, Jul 18, 2016 at 04:39:25PM -0400, Waiman Long wrote:
> 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.

No, two spinners are not in fact starvation proof. It makes the reported
life-lock scenario much less likely, but it does not guarantee anything.

> +		/*
> +		 * Optimistically spinning on the mutex without the wait lock

There should either be a '.' at the end of that line, or the next line
should not start with a capital.

Also, I don't see how the two sentences are related, should they be in
the same paragraph?

> +		 * The state has to be set to running to avoid another waker
> +		 * spinning on the on_cpu flag while the woken waiter is
> +		 * spinning on the mutex.
> +		 */
> +		acquired = mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx,
> +						 true);
>  		spin_lock_mutex(&lock->wait_lock, flags);
>  	}
>  	__set_task_state(task, TASK_RUNNING);

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner
  2016-07-18 20:39 ` [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner Waiman Long
@ 2016-08-08 17:37   ` Peter Zijlstra
  2016-08-09 18:00     ` Waiman Long
  0 siblings, 1 reply; 12+ messages in thread
From: Peter Zijlstra @ 2016-08-08 17:37 UTC (permalink / raw)
  To: Waiman Long
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On Mon, Jul 18, 2016 at 04:39:26PM -0400, Waiman Long wrote:
> As both an optimistic spinner and a waiter-spinner (a woken task from
> the wait queue spinning) can be spinning on the lock at the same time,
> we cannot ensure forward progress for the waiter-spinner. Therefore,
> it is possible for the waiter-spinner to be starved of getting the
> lock, though not likely.

Right; yet your previous two changelogs/comments implied otherwise.

> This patch adds a flag to indicate that a waiter-spinner is
> spinning and hence has priority over the acquisition of the lock. A
> waiter-spinner sets this flag while spinning. An optimistic spinner
> will check this flag and yield if set. This essentially makes the
> waiter-spinner jump to the head of the optimistic spinning queue to
> acquire the lock.
> 
> There will be no increase in size for the mutex structure for 64-bit
> architectures. For 32-bit architectures, there will be a size increase
> of 4 bytes.

Alternative might be to use the LSB of mutex::owner, but that's going to
be somewhat icky too.

I'm not sure the 32bit platforms are going to be excited about growing
struct mutex...

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin()
  2016-08-08 17:26   ` Peter Zijlstra
@ 2016-08-09 17:36     ` Waiman Long
  0 siblings, 0 replies; 12+ messages in thread
From: Waiman Long @ 2016-08-09 17:36 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak, Waiman Long

On 08/08/2016 01:26 PM, Peter Zijlstra wrote:
> On Mon, Jul 18, 2016 at 04:39:24PM -0400, Waiman Long wrote:
>> @@ -302,22 +306,42 @@ 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. As the waiter has slept for a while, it should have priority to
>> + * get the lock over the regular spinners. So going to wait at the end of
>> + * the OSQ isn't fair to the waiter.
> If the OSQ lock were a full FIFO it would in fact be fair, but its not
> and things can drop out the middle and go (back) to sleep.
>
> This has nothing to do with the end or not.

Yes, the OSQ is not strictly FIFO, but the wait queue is. There is a 
much higher chance of lock starvation if the waiter is put at the end of 
the OSQ instead of in front of it. I will change the wordings to 
illustrate this fact.

>> Instead, it will spin on the lock
>> + * directly and concurrently with the spinner at the head of the OSQ, if
>> + * present.
> Note that this isn't starvation proof in any way.

Patch 1 by itself isn't starvation-proof. Coupled with patch 3 that put 
the waiter-spinner in front of OSQ, we will have a much higher chance to 
avoid lock starvation. We can also completely block optimistic spinning 
if the waiter can't get the lock after a certain number of wakeup-sleep 
cycles, if the goal is to make it starvation proof.

>
>>      There may be a bit more cacheline contention in this case.
> This is relevant how ?

It is just that there will be one more CPU contending on the lock cacheline.

>
>> + * The waiter also needs to set the lock to -1 instead of 0 on lock
>> + * acquisition.
> This is unrelated to the previous bits and thus should not be in the
> same paragraph. Also, a 'why' would be more helpful.

Will explain a bit more in the comments.

Regards,
Longman

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue
  2016-08-08 17:29   ` Peter Zijlstra
@ 2016-08-09 17:49     ` Waiman Long
  0 siblings, 0 replies; 12+ messages in thread
From: Waiman Long @ 2016-08-09 17:49 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On 08/08/2016 01:29 PM, Peter Zijlstra wrote:
> On Mon, Jul 18, 2016 at 04:39:25PM -0400, Waiman Long wrote:
>> 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.
> No, two spinners are not in fact starvation proof. It makes the reported
> life-lock scenario much less likely, but it does not guarantee anything.

Yes, I should have said reducing the chance of live-locking.

>> +		/*
>> +		 * Optimistically spinning on the mutex without the wait lock
> There should either be a '.' at the end of that line, or the next line
> should not start with a capital.
>
> Also, I don't see how the two sentences are related, should they be in
> the same paragraph?

Sorry for the missing '.', and I will split it into 2 paragraphs.

Cheers,
Longman

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner
  2016-08-08 17:37   ` Peter Zijlstra
@ 2016-08-09 18:00     ` Waiman Long
  2016-08-10  9:29       ` Peter Zijlstra
  0 siblings, 1 reply; 12+ messages in thread
From: Waiman Long @ 2016-08-09 18:00 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On 08/08/2016 01:37 PM, Peter Zijlstra wrote:
> On Mon, Jul 18, 2016 at 04:39:26PM -0400, Waiman Long wrote:
>> As both an optimistic spinner and a waiter-spinner (a woken task from
>> the wait queue spinning) can be spinning on the lock at the same time,
>> we cannot ensure forward progress for the waiter-spinner. Therefore,
>> it is possible for the waiter-spinner to be starved of getting the
>> lock, though not likely.
> Right; yet your previous two changelogs/comments implied otherwise.
>
>> This patch adds a flag to indicate that a waiter-spinner is
>> spinning and hence has priority over the acquisition of the lock. A
>> waiter-spinner sets this flag while spinning. An optimistic spinner
>> will check this flag and yield if set. This essentially makes the
>> waiter-spinner jump to the head of the optimistic spinning queue to
>> acquire the lock.
>>
>> There will be no increase in size for the mutex structure for 64-bit
>> architectures. For 32-bit architectures, there will be a size increase
>> of 4 bytes.
> Alternative might be to use the LSB of mutex::owner, but that's going to
> be somewhat icky too.

I was thinking about doing that. However, the owner field is used in 
quite a number of places. It may be a bit risky to change all of them.

> I'm not sure the 32bit platforms are going to be excited about growing
> struct mutex...

Or we can make this a 64-bit architecture specific change if the 
increase in mutex size is a real concern. Actually, we don't need to use 
a list_head structure for wait_list. It can be just a pointer to 
mutex_waiter that has the list_head structure. This can save a pointer 
from the structure.

Cheers,
Longman

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner
  2016-08-09 18:00     ` Waiman Long
@ 2016-08-10  9:29       ` Peter Zijlstra
  2016-08-10 17:51         ` Waiman Long
  0 siblings, 1 reply; 12+ messages in thread
From: Peter Zijlstra @ 2016-08-10  9:29 UTC (permalink / raw)
  To: Waiman Long
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On Tue, Aug 09, 2016 at 02:00:00PM -0400, Waiman Long wrote:
> >Alternative might be to use the LSB of mutex::owner, but that's going to
> >be somewhat icky too.
> 
> I was thinking about doing that. However, the owner field is used in quite a
> number of places. It may be a bit risky to change all of them.

Agreed.

> >I'm not sure the 32bit platforms are going to be excited about growing
> >struct mutex...
> 
> Or we can make this a 64-bit architecture specific change if the increase in
> mutex size is a real concern. Actually, we don't need to use a list_head
> structure for wait_list. It can be just a pointer to mutex_waiter that has
> the list_head structure. This can save a pointer from the structure.

Just grow the thing, we can poke at it later if we get complaints.

^ permalink raw reply	[flat|nested] 12+ messages in thread

* Re: [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner
  2016-08-10  9:29       ` Peter Zijlstra
@ 2016-08-10 17:51         ` Waiman Long
  0 siblings, 0 replies; 12+ messages in thread
From: Waiman Long @ 2016-08-10 17:51 UTC (permalink / raw)
  To: Peter Zijlstra
  Cc: Ingo Molnar, linux-kernel, Linus Torvalds, Ding Tianhong,
	Jason Low, Davidlohr Bueso, Paul E. McKenney, Thomas Gleixner,
	Will Deacon, Tim Chen, Imre Deak

On 08/10/2016 05:29 AM, Peter Zijlstra wrote:
> On Tue, Aug 09, 2016 at 02:00:00PM -0400, Waiman Long wrote:
>>> Alternative might be to use the LSB of mutex::owner, but that's going to
>>> be somewhat icky too.
>> I was thinking about doing that. However, the owner field is used in quite a
>> number of places. It may be a bit risky to change all of them.
> Agreed.
>

It will be easier to do that for rwsem as the owner field isn't used for 
the debug code, unlike the mutex.

Cheers,
Longman

^ permalink raw reply	[flat|nested] 12+ messages in thread

end of thread, other threads:[~2016-08-10 19:12 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-07-18 20:39 [PATCH v4 0/3] locking/mutex: Enable optimistic spinning of lock waiter Waiman Long
2016-07-18 20:39 ` [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() Waiman Long
2016-08-08 17:26   ` Peter Zijlstra
2016-08-09 17:36     ` Waiman Long
2016-07-18 20:39 ` [PATCH v4 2/3] locking/mutex: Enable optimistic spinning of woken task in wait queue Waiman Long
2016-08-08 17:29   ` Peter Zijlstra
2016-08-09 17:49     ` Waiman Long
2016-07-18 20:39 ` [PATCH v4 3/3] locking/mutex: Ensure forward progress of waiter-spinner Waiman Long
2016-08-08 17:37   ` Peter Zijlstra
2016-08-09 18:00     ` Waiman Long
2016-08-10  9:29       ` Peter Zijlstra
2016-08-10 17:51         ` Waiman Long

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.