Re: [PATCH v5 3/3] locking/mutex: Ensure forward progress of waiter-spinner

[Waiman Long <waiman.long@hpe.com>]

On 08/10/2016 02:25 PM, 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. So 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 as there is an existing 4-byte hole. 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 15b521a..0912964 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);
> @@ -337,9 +338,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) {
> @@ -359,6 +372,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.
>   		 */
> @@ -390,18 +414,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(),


The following is the updated patch that should fix the build error in 
non-x86 platform.

Cheers,
Longman

================================ cut here ================================

locking/mutex: Ensure forward progress of waiter-spinner

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. So 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 as there is an existing 4-byte hole. 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 |   21 +++++++++++++++++++++
  2 files changed, 22 insertions(+), 0 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 15b521a..02d8029 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);
@@ -337,6 +338,12 @@ 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) {
@@ -359,6 +366,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;
+            goto relax;
+        }
+
+        /*
           * If there's an owner, wait for it to either
           * release the lock or go to sleep.
           */
@@ -391,6 +409,7 @@ static bool mutex_optimistic_spin(struct mutex *lock,
          if (!owner && (need_resched() || rt_task(task)))
              break;

+relax:
          /*
           * The cpu_relax() call is a compiler barrier which forces
           * everything in this loop to be re-loaded. We don't need
@@ -402,6 +421,8 @@ static bool mutex_optimistic_spin(struct mutex *lock,

      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