Re: [RFC][PATCH -v2 4/4] locking/mutex: Add lock handoff to avoid starvation

[Peter Zijlstra <peterz@infradead.org>]

On Fri, Aug 26, 2016 at 07:40:34PM -0400, Waiman Long wrote:
> On 08/26/2016 11:18 AM, Peter Zijlstra wrote:

> >Still need to look at adding spinning to the handoff case.
> >Also need to look at writing (much) better changelogs, they stink.
> >
> 
> I have looked at the handoff code and I didn't see any problem.

So I found (or rather the buildbot did) a problem with it.

locking-selftest has testcases like:


	lock(&A);
	if (trylock(&A))
		/* fail */

  and

	ww_lock(&A)
	if (ww_lock(&A) != -EDEADLK)
		/* fail */

But with the 'trylock' accepting the lock if owner==current, in order to
accept the hand-off, this breaks in interesting ways.

Now, ARCH_MIN_TASKALIGN is at least 8 (mips, s390, parisc) which would
give us one more FLAG bit to play with.


The below seems to make things happy again..


--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -53,8 +53,9 @@ EXPORT_SYMBOL(__mutex_init);
 
 #define MUTEX_FLAG_WAITERS	0x01
 #define MUTEX_FLAG_HANDOFF	0x02
+#define MUTEX_FLAG_GIFT		0x04
 
-#define MUTEX_FLAGS		0x03
+#define MUTEX_FLAGS		0x07
 
 static inline struct task_struct *__owner_task(unsigned long owner)
 {
@@ -66,33 +67,6 @@ static inline unsigned long __owner_flag
 	return owner & MUTEX_FLAGS;
 }
 
-/*
- * Actual trylock that will work on any unlocked state.
- */
-static inline bool __mutex_trylock(struct mutex *lock)
-{
-	unsigned long owner, curr = (unsigned long)current;
-
-	owner = atomic_long_read(&lock->owner);
-	for (;;) { /* must loop, can race against a flag */
-		unsigned long old;
-
-		if (__owner_task(owner)) {
-			if ((unsigned long)__owner_task(owner) == curr)
-				return true;
-
-			return false;
-		}
-
-		old = atomic_long_cmpxchg_acquire(&lock->owner, owner,
-						  curr | __owner_flags(owner));
-		if (old == owner)
-			return true;
-
-		owner = old;
-	}
-}
-
 #ifndef CONFIG_DEBUG_LOCK_ALLOC
 /*
  * Optimistic trylock that only works in the uncontended case. Make sure to
@@ -134,6 +108,10 @@ static inline bool __mutex_waiter_is_fir
 	return list_first_entry(&lock->wait_list, struct mutex_waiter, list) == waiter;
 }
 
+/*
+ * Give up ownership to a specific task, when @task = NULL, this is equivalent
+ * to a regular unlock.
+ */
 static void __mutex_handoff(struct mutex *lock, struct task_struct *task)
 {
 	unsigned long owner = atomic_long_read(&lock->owner);
@@ -146,7 +124,15 @@ static void __mutex_handoff(struct mutex
 #endif
 
 		new = (owner & MUTEX_FLAG_WAITERS);
-		new |= (unsigned long)task;
+		if (task) {
+			/*
+			 * To distinguish between a recursive lock attempt
+			 * and having been given the lock by someone else
+			 * we need to set the GIFT bit.
+			 */
+			new |= MUTEX_FLAG_GIFT; /* clear HANDOFF, set GIFT */
+			new |= (unsigned long)task;
+		}
 
 		old = atomic_long_cmpxchg(&lock->owner, owner, new);
 		if (old == owner)
@@ -154,6 +140,50 @@ static void __mutex_handoff(struct mutex
 
 		owner = old;
 	}
+}
+
+/*
+ * Someone handed us its lock ownership using __mutex_handoff(), say thank you
+ * and accept this nice gift.
+ */
+static bool __mutex_accept(struct mutex *lock, unsigned long owner)
+{
+	if (!(owner & MUTEX_FLAG_GIFT))
+		return false;
+
+	if (__owner_task(owner) != current)
+		return false;
+
+	__mutex_clear_flag(lock, MUTEX_FLAG_GIFT);
+	smp_mb__after_atomic(); /* ACQUIRE */
+	return true;
+}
+
+/*
+ * Actual trylock that will work on any unlocked state.
+ */
+static inline bool __mutex_trylock(struct mutex *lock)
+{
+	unsigned long owner, curr = (unsigned long)current;
+
+	owner = atomic_long_read(&lock->owner);
+	for (;;) { /* must loop, can race against a flag */
+		unsigned long old;
+
+		if (__owner_task(owner)) {
+			if (unlikely(owner & MUTEX_FLAG_GIFT))
+				return __mutex_accept(lock, owner);
+
+			return false;
+		}
+
+		old = atomic_long_cmpxchg_acquire(&lock->owner, owner,
+						  curr | __owner_flags(owner));
+		if (old == owner)
+			return true;
+
+		owner = old;
+	}
 }
 
 #ifndef CONFIG_DEBUG_LOCK_ALLOC