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

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

[Waiman Long]

v4->v5:
 - Clean up some comments in source files submit logs as suggested
   by PeterZ.

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 |  109 +++++++++++++++++++++++++++++++++++-------------
 2 files changed, 81 insertions(+), 29 deletions(-)

[PATCH v5 1/3] 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 |   62 ++++++++++++++++++++++++++++++++---------------
 1 files changed, 42 insertions(+), 20 deletions(-)

diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index a70b90d..3bcbbd1 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -273,11 +273,16 @@ 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 as the the woken waiter will set it to -1,
+ * if necessary.
  */
-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 +307,37 @@ 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. The waiter-spinner will spin on the lock directly and concurrently
+ * with the spinner at the head of the OSQ, if present.
  */
 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 +367,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 +378,8 @@ static bool mutex_optimistic_spin(struct mutex *lock,
 			}
 
 			mutex_set_owner(lock);
-			osq_unlock(&lock->osq);
-			return true;
+			acquired = true;
+			break;
 		}
 
 		/*
@@ -380,14 +400,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 +417,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 +542,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 v5 2/3] 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 alleviate 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
help to reduce the live-locking chance.

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 3bcbbd1..15b521a 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;
 
 	if (use_ww_ctx) {
@@ -567,7 +568,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
@@ -602,6 +603,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);
@@ -612,6 +619,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);
@@ -622,6 +632,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

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

[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. 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(),
-- 
1.7.1

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

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 7063 bytes --]

Hi Waiman,

[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/Waiman-Long/locking-mutex-Enable-optimistic-spinning-of-lock-waiter/20160811-074736
config: arm-multi_v7_defconfig (attached as .config)
compiler: arm-linux-gnueabi-gcc (Debian 5.4.0-6) 5.4.0 20160609
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=arm 

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

   In file included from arch/arm/include/asm/bitops.h:28:0,
                    from include/linux/bitops.h:36,
                    from include/linux/kernel.h:10,
                    from include/asm-generic/bug.h:13,
                    from arch/arm/include/asm/bug.h:59,
                    from include/linux/bug.h:4,
                    from include/linux/thread_info.h:11,
                    from include/asm-generic/current.h:4,
                    from ./arch/arm/include/generated/asm/current.h:1,
                    from include/linux/mutex.h:13,
                    from kernel/locking/mutex.c:20:
   kernel/locking/mutex.c: In function 'mutex_optimistic_spin':
>> arch/arm/include/asm/barrier.h:18:21: error: expected expression before '__asm__'
    #define dmb(option) __asm__ __volatile__ ("dmb " #option : : : "memory")
                        ^
>> arch/arm/include/asm/barrier.h:61:20: note: in expansion of macro 'dmb'
    #define __smp_mb() dmb(ish)
                       ^
>> include/asm-generic/barrier.h:76:18: note: in expansion of macro '__smp_mb'
    #define smp_mb() __smp_mb()
                     ^
>> arch/arm/include/asm/processor.h:80:23: note: in expansion of macro 'smp_mb'
    #define cpu_relax()   smp_mb()
                          ^
   arch/arm/include/asm/processor.h:85:47: note: in expansion of macro 'cpu_relax'
    #define cpu_relax_lowlatency()                cpu_relax()
                                                  ^
   kernel/locking/mutex.c:355:10: note: in expansion of macro 'cpu_relax_lowlatency'
     for (;; cpu_relax_lowlatency()) {
             ^

vim +/__asm__ +18 arch/arm/include/asm/barrier.h

9f97da78b David Howells      2012-03-28  12  #define wfi()	__asm__ __volatile__ ("wfi" : : : "memory")
9f97da78b David Howells      2012-03-28  13  #endif
9f97da78b David Howells      2012-03-28  14  
9f97da78b David Howells      2012-03-28  15  #if __LINUX_ARM_ARCH__ >= 7
3ea128065 Will Deacon        2013-05-10  16  #define isb(option) __asm__ __volatile__ ("isb " #option : : : "memory")
3ea128065 Will Deacon        2013-05-10  17  #define dsb(option) __asm__ __volatile__ ("dsb " #option : : : "memory")
3ea128065 Will Deacon        2013-05-10 @18  #define dmb(option) __asm__ __volatile__ ("dmb " #option : : : "memory")
9f97da78b David Howells      2012-03-28  19  #elif defined(CONFIG_CPU_XSC3) || __LINUX_ARM_ARCH__ == 6
3ea128065 Will Deacon        2013-05-10  20  #define isb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c5, 4" \
9f97da78b David Howells      2012-03-28  21  				    : : "r" (0) : "memory")
3ea128065 Will Deacon        2013-05-10  22  #define dsb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c10, 4" \
9f97da78b David Howells      2012-03-28  23  				    : : "r" (0) : "memory")
3ea128065 Will Deacon        2013-05-10  24  #define dmb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c10, 5" \
9f97da78b David Howells      2012-03-28  25  				    : : "r" (0) : "memory")
9f97da78b David Howells      2012-03-28  26  #elif defined(CONFIG_CPU_FA526)
3ea128065 Will Deacon        2013-05-10  27  #define isb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c5, 4" \
9f97da78b David Howells      2012-03-28  28  				    : : "r" (0) : "memory")
3ea128065 Will Deacon        2013-05-10  29  #define dsb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c10, 4" \
9f97da78b David Howells      2012-03-28  30  				    : : "r" (0) : "memory")
3ea128065 Will Deacon        2013-05-10  31  #define dmb(x) __asm__ __volatile__ ("" : : : "memory")
9f97da78b David Howells      2012-03-28  32  #else
3ea128065 Will Deacon        2013-05-10  33  #define isb(x) __asm__ __volatile__ ("" : : : "memory")
3ea128065 Will Deacon        2013-05-10  34  #define dsb(x) __asm__ __volatile__ ("mcr p15, 0, %0, c7, c10, 4" \
9f97da78b David Howells      2012-03-28  35  				    : : "r" (0) : "memory")
3ea128065 Will Deacon        2013-05-10  36  #define dmb(x) __asm__ __volatile__ ("" : : : "memory")
9f97da78b David Howells      2012-03-28  37  #endif
9f97da78b David Howells      2012-03-28  38  
f81309067 Russell King       2015-06-01  39  #ifdef CONFIG_ARM_HEAVY_MB
4e1f8a6f1 Russell King       2015-06-03  40  extern void (*soc_mb)(void);
f81309067 Russell King       2015-06-01  41  extern void arm_heavy_mb(void);
f81309067 Russell King       2015-06-01  42  #define __arm_heavy_mb(x...) do { dsb(x); arm_heavy_mb(); } while (0)
f81309067 Russell King       2015-06-01  43  #else
f81309067 Russell King       2015-06-01  44  #define __arm_heavy_mb(x...) dsb(x)
f81309067 Russell King       2015-06-01  45  #endif
f81309067 Russell King       2015-06-01  46  
520319de0 Masahiro Yamada    2016-06-21  47  #if defined(CONFIG_ARM_DMA_MEM_BUFFERABLE) || defined(CONFIG_SMP)
f81309067 Russell King       2015-06-01  48  #define mb()		__arm_heavy_mb()
9f97da78b David Howells      2012-03-28  49  #define rmb()		dsb()
f81309067 Russell King       2015-06-01  50  #define wmb()		__arm_heavy_mb(st)
1077fa36f Alexander Duyck    2014-12-11  51  #define dma_rmb()	dmb(osh)
1077fa36f Alexander Duyck    2014-12-11  52  #define dma_wmb()	dmb(oshst)
9f97da78b David Howells      2012-03-28  53  #else
48aa820f1 Rob Herring        2012-08-21  54  #define mb()		barrier()
48aa820f1 Rob Herring        2012-08-21  55  #define rmb()		barrier()
48aa820f1 Rob Herring        2012-08-21  56  #define wmb()		barrier()
1077fa36f Alexander Duyck    2014-12-11  57  #define dma_rmb()	barrier()
1077fa36f Alexander Duyck    2014-12-11  58  #define dma_wmb()	barrier()
9f97da78b David Howells      2012-03-28  59  #endif
9f97da78b David Howells      2012-03-28  60  
2b1f3de10 Michael S. Tsirkin 2015-12-27 @61  #define __smp_mb()	dmb(ish)
2b1f3de10 Michael S. Tsirkin 2015-12-27  62  #define __smp_rmb()	__smp_mb()
2b1f3de10 Michael S. Tsirkin 2015-12-27  63  #define __smp_wmb()	dmb(ishst)
9f97da78b David Howells      2012-03-28  64  

:::::: The code at line 18 was first introduced by commit
:::::: 3ea128065ed20d33bd02ff6dab689f88e38000be ARM: barrier: allow options to be passed to memory barrier instructions

:::::: TO: Will Deacon <will.deacon@arm.com>
:::::: CC: Will Deacon <will.deacon@arm.com>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 38558 bytes --]

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

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 3837 bytes --]

Hi Waiman,

[auto build test ERROR on tip/locking/core]
[also build test ERROR on v4.8-rc1]
[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/Waiman-Long/locking-mutex-Enable-optimistic-spinning-of-lock-waiter/20160811-074736
config: arm-sunxi_defconfig (attached as .config)
compiler: arm-linux-gnueabi-gcc (Debian 5.4.0-6) 5.4.0 20160609
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=arm 

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

   In file included from include/linux/compiler.h:58:0,
                    from include/uapi/linux/stddef.h:1,
                    from include/linux/stddef.h:4,
                    from include/uapi/linux/posix_types.h:4,
                    from include/uapi/linux/types.h:13,
                    from include/linux/types.h:5,
                    from include/linux/thread_info.h:10,
                    from include/asm-generic/current.h:4,
                    from ./arch/arm/include/generated/asm/current.h:1,
                    from include/linux/mutex.h:13,
                    from kernel/locking/mutex.c:20:
   kernel/locking/mutex.c: In function 'mutex_optimistic_spin':
>> include/linux/compiler-gcc.h:15:19: error: expected expression before '__asm__'
    #define barrier() __asm__ __volatile__("": : :"memory")
                      ^
>> arch/arm/include/asm/processor.h:82:23: note: in expansion of macro 'barrier'
    #define cpu_relax()   barrier()
                          ^
>> arch/arm/include/asm/processor.h:85:47: note: in expansion of macro 'cpu_relax'
    #define cpu_relax_lowlatency()                cpu_relax()
                                                  ^
>> kernel/locking/mutex.c:355:10: note: in expansion of macro 'cpu_relax_lowlatency'
     for (;; cpu_relax_lowlatency()) {
             ^

vim +/cpu_relax +85 arch/arm/include/asm/processor.h

^1da177e4 include/asm-arm/processor.h      Linus Torvalds  2005-04-16  76  
^1da177e4 include/asm-arm/processor.h      Linus Torvalds  2005-04-16  77  unsigned long get_wchan(struct task_struct *p);
^1da177e4 include/asm-arm/processor.h      Linus Torvalds  2005-04-16  78  
5dab26af1 arch/arm/include/asm/processor.h Will Deacon     2011-03-04  79  #if __LINUX_ARM_ARCH__ == 6 || defined(CONFIG_ARM_ERRATA_754327)
534be1d5a arch/arm/include/asm/processor.h Will Deacon     2010-06-21  80  #define cpu_relax()			smp_mb()
534be1d5a arch/arm/include/asm/processor.h Will Deacon     2010-06-21  81  #else
^1da177e4 include/asm-arm/processor.h      Linus Torvalds  2005-04-16 @82  #define cpu_relax()			barrier()
534be1d5a arch/arm/include/asm/processor.h Will Deacon     2010-06-21  83  #endif
^1da177e4 include/asm-arm/processor.h      Linus Torvalds  2005-04-16  84  
3a6bfbc91 arch/arm/include/asm/processor.h Davidlohr Bueso 2014-06-29 @85  #define cpu_relax_lowlatency()                cpu_relax()
3a6bfbc91 arch/arm/include/asm/processor.h Davidlohr Bueso 2014-06-29  86  
815d5ec86 include/asm-arm/processor.h      Al Viro         2006-01-12  87  #define task_pt_regs(p) \
32d39a935 include/asm-arm/processor.h      Al Viro         2006-01-12  88  	((struct pt_regs *)(THREAD_START_SP + task_stack_page(p)) - 1)

:::::: The code at line 85 was first introduced by commit
:::::: 3a6bfbc91df04b081a44d419e0260bad54abddf7 arch, locking: Ciao arch_mutex_cpu_relax()

:::::: TO: Davidlohr Bueso <davidlohr@hp.com>
:::::: CC: Ingo Molnar <mingo@kernel.org>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 20003 bytes --]

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

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 4398 bytes --]

Hi Waiman,

[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/Waiman-Long/locking-mutex-Enable-optimistic-spinning-of-lock-waiter/20160811-074736
config: sparc64-defconfig (attached as .config)
compiler: sparc64-linux-gnu-gcc (Debian 5.4.0-6) 5.4.0 20160609
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=sparc64 

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

   In file included from arch/sparc/include/asm/processor.h:4:0,
                    from include/linux/mutex.h:19,
                    from kernel/locking/mutex.c:20:
   kernel/locking/mutex.c: In function 'mutex_optimistic_spin':
>> arch/sparc/include/asm/processor_64.h:208:21: error: expected expression before 'asm'
    #define cpu_relax() asm volatile("\n99:\n\t"   \
                        ^
>> arch/sparc/include/asm/processor_64.h:219:32: note: in expansion of macro 'cpu_relax'
    #define cpu_relax_lowlatency() cpu_relax()
                                   ^
   kernel/locking/mutex.c:355:10: note: in expansion of macro 'cpu_relax_lowlatency'
     for (;; cpu_relax_lowlatency()) {
             ^

vim +/cpu_relax +219 arch/sparc/include/asm/processor_64.h

f5e706ad8 include/asm-sparc/processor_64.h      Sam Ravnborg    2008-07-17  202  
187818cd6 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-28  203  /* Please see the commentary in asm/backoff.h for a description of
08f800730 arch/sparc/include/asm/processor_64.h Adam Buchbinder 2016-03-04  204   * what these instructions are doing and how they have been chosen.
187818cd6 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-28  205   * To make a long story short, we are trying to yield the current cpu
187818cd6 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-28  206   * strand during busy loops.
187818cd6 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-28  207   */
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27 @208  #define cpu_relax()	asm volatile("\n99:\n\t"			\
270c10e00 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  209  				     "rd	%%ccr, %%g0\n\t"	\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  210  				     "rd	%%ccr, %%g0\n\t"	\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  211  				     "rd	%%ccr, %%g0\n\t"	\
187818cd6 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-28  212  				     ".section	.pause_3insn_patch,\"ax\"\n\t"\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  213  				     ".word	99b\n\t"		\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  214  				     "wr	%%g0, 128, %%asr27\n\t"	\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  215  				     "nop\n\t"				\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  216  				     "nop\n\t"				\
e9b9eb59f arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  217  				     ".previous"			\
270c10e00 arch/sparc/include/asm/processor_64.h David S. Miller 2012-10-27  218  				     ::: "memory")
3a6bfbc91 arch/sparc/include/asm/processor_64.h Davidlohr Bueso 2014-06-29 @219  #define cpu_relax_lowlatency() cpu_relax()
f5e706ad8 include/asm-sparc/processor_64.h      Sam Ravnborg    2008-07-17  220  
f5e706ad8 include/asm-sparc/processor_64.h      Sam Ravnborg    2008-07-17  221  /* Prefetch support.  This is tuned for UltraSPARC-III and later.
f5e706ad8 include/asm-sparc/processor_64.h      Sam Ravnborg    2008-07-17  222   * UltraSPARC-I will treat these as nops, and UltraSPARC-II has

:::::: The code at line 219 was first introduced by commit
:::::: 3a6bfbc91df04b081a44d419e0260bad54abddf7 arch, locking: Ciao arch_mutex_cpu_relax()

:::::: TO: Davidlohr Bueso <davidlohr@hp.com>
:::::: CC: Ingo Molnar <mingo@kernel.org>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 17070 bytes --]

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

[Waiman Long]

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

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

[Peter Zijlstra]

On Thu, Aug 11, 2016 at 11:01:27AM -0400, Waiman Long wrote:
> The following is the updated patch that should fix the build error in
> non-x86 platform.
> 

This patch was whitespace challenged, but I think I munged it properly.

I've also stuck something based on Jason's patch on top. Please have a
look at:

  https://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/log/?h=locking/core

compile tested only so far..

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

[Imre Deak]

On to, 2016-08-18 at 17:58 +0200, Peter Zijlstra wrote:
> On Thu, Aug 11, 2016 at 11:01:27AM -0400, Waiman Long wrote:
> > The following is the updated patch that should fix the build error
> > in
> > non-x86 platform.
> > 
> 
> This patch was whitespace challenged, but I think I munged it
> properly.
> 
> I've also stuck something based on Jason's patch on top. Please have
> a
> look at:
> 
>   https://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/log/?
> h=locking/core
> 
> compile tested only so far..

It works for me and fixes my test case.

Nitpick: "Try-acquire now that we got woken at the head of the queue."
would be more accurate by also adding "or received a signal."

--Imre

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

[Jason Low]

On Thu, 2016-08-18 at 17:58 +0200, Peter Zijlstra wrote:
> On Thu, Aug 11, 2016 at 11:01:27AM -0400, Waiman Long wrote:
> > The following is the updated patch that should fix the build error in
> > non-x86 platform.
> > 
> 
> This patch was whitespace challenged, but I think I munged it properly.
> 
> I've also stuck something based on Jason's patch on top. Please have a
> look at:
> 
>   https://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/log/?h=locking/core

Should we convert the flags back to type 'bool'? We're using them as
booleans and we could also leave unneeded space available in case we
ever need to squeeze some more variable(s) in the structure.

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

[Peter Zijlstra]

On Thu, Aug 18, 2016 at 11:04:40AM -0700, Jason Low wrote:
> On Thu, 2016-08-18 at 17:58 +0200, Peter Zijlstra wrote:
> > On Thu, Aug 11, 2016 at 11:01:27AM -0400, Waiman Long wrote:
> > > The following is the updated patch that should fix the build error in
> > > non-x86 platform.
> > > 
> > 
> > This patch was whitespace challenged, but I think I munged it properly.
> > 
> > I've also stuck something based on Jason's patch on top. Please have a
> > look at:
> > 
> >   https://git.kernel.org/cgit/linux/kernel/git/peterz/queue.git/log/?h=locking/core
> 
> Should we convert the flags back to type 'bool'? 

No,

> We're using them as
> booleans and we could also leave unneeded space available in case we
> ever need to squeeze some more variable(s) in the structure.

Because sizeof(bool) is undefined, that then leaves sizeof(struct mutex)
and alignof(struct mutex) and its exact layout also undefined.

Never use bool in aggregate types.

Of course, an actual implementation needs a sizeof(bool) to translate
things, but these are defined in the architecture ABI, not in the
language. And having struct mutex change depending on whatever an
architecture ABI chooses is very bad form.