[patch] PI-futex: -V3

[Ingo Molnar <mingo@elte.hu>]

this is version -V3 of the PI-futex patchset (ontop of current -mm plus 
the -V2 delta patch). Changes since -V2:

 - do the -> set_current_state() cleanups for real
 - make plist_add() more readable
 - whitespace cleanups in kernel/futex.c
 - further cleanups in rtmutex_common.h
 - fix cornercase race in the PI-locking code (it triggered in the -rt tree)

Signed-off-by: Ingo Molnar <mingo@elte.hu>

----

 kernel/futex.c          |    4 
 kernel/rtmutex.c        |  245 +++++++++++++++++++++++++-----------------------
 kernel/rtmutex_common.h |    6 -
 lib/plist.c             |    3 
 4 files changed, 136 insertions(+), 122 deletions(-)

Index: linux-pi-futex.mm.q/kernel/futex.c
===================================================================
--- linux-pi-futex.mm.q.orig/kernel/futex.c
+++ linux-pi-futex.mm.q/kernel/futex.c
@@ -425,7 +425,7 @@ void exit_pi_state_list(struct task_stru
 	 */
 	spin_lock(&curr->pi_lock);
 	while (!list_empty(head)) {
-		
+
 		next = head->next;
 		pi_state = list_entry(next, struct futex_pi_state, list);
 		key = pi_state->key;
@@ -439,7 +439,7 @@ void exit_pi_state_list(struct task_stru
 			spin_unlock(&hb->lock);
 			continue;
 		}
-		
+
 		list_del_init(&pi_state->list);
 
 		WARN_ON(pi_state->owner != curr);
Index: linux-pi-futex.mm.q/kernel/rtmutex.c
===================================================================
--- linux-pi-futex.mm.q.orig/kernel/rtmutex.c
+++ linux-pi-futex.mm.q/kernel/rtmutex.c
@@ -173,11 +173,12 @@ static int lock_pi_chain(struct rt_mutex
 	struct task_struct *owner;
 	struct rt_mutex *nextlock, *lock = act_lock;
 	struct rt_mutex_waiter *nextwaiter;
+	int deadlock_detect;
 
 	/*
 	 * Debugging might turn deadlock detection on, unconditionally:
 	 */
-	detect_deadlock = debug_rt_mutex_detect_deadlock(detect_deadlock);
+	deadlock_detect = debug_rt_mutex_detect_deadlock(detect_deadlock);
 
 	for (;;) {
 		owner = rt_mutex_owner(lock);
@@ -185,7 +186,7 @@ static int lock_pi_chain(struct rt_mutex
 		/* Check for circular dependencies */
 		if (unlikely(owner->pi_locked_by == current)) {
 			debug_rt_mutex_deadlock(detect_deadlock, waiter, lock);
-			return detect_deadlock ? -EDEADLK : 0;
+			return detect_deadlock ? -EDEADLK : 1;
 		}
 
 		while (!spin_trylock(&owner->pi_lock)) {
@@ -211,7 +212,7 @@ static int lock_pi_chain(struct rt_mutex
 
 		/* End of chain? */
 		if (!nextwaiter)
-			return 0;
+			return 1;
 
 		nextlock = nextwaiter->lock;
 
@@ -223,7 +224,7 @@ static int lock_pi_chain(struct rt_mutex
 			list_del_init(&owner->pi_lock_chain);
 			owner->pi_locked_by = NULL;
 			spin_unlock(&owner->pi_lock);
-			return detect_deadlock ? -EDEADLK : 0;
+			return detect_deadlock ? -EDEADLK : 1;
 		}
 
 		/* Try to get nextlock->wait_lock: */
@@ -242,7 +243,7 @@ static int lock_pi_chain(struct rt_mutex
 		 * for userspace locks), we have to walk the full chain
 		 * unconditionally.
 		 */
-		if (detect_deadlock)
+		if (deadlock_detect)
 			continue;
 
 		/*
@@ -255,11 +256,11 @@ static int lock_pi_chain(struct rt_mutex
 			/* If the top waiter has higher priority, stop: */
 			if (rt_mutex_top_waiter(lock)->list_entry.prio <=
 			    waiter->list_entry.prio)
-				return 0;
+				return 1;
 		} else {
 			/* If nextwaiter is not the top waiter, stop: */
 			if (rt_mutex_top_waiter(lock) != nextwaiter)
-				return 0;
+				return 1;
 		}
 	}
 }
@@ -340,103 +341,6 @@ static void adjust_pi_chain(struct rt_mu
 }
 
 /*
- * Task blocks on lock.
- *
- * Prepare waiter and potentially propagate our priority into the pi chain.
- *
- * This must be called with lock->wait_lock held.
- */
-static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
-				   struct rt_mutex_waiter *waiter,
-				   int detect_deadlock __IP_DECL__)
-{
-	int res = 0;
-	struct rt_mutex_waiter *top_waiter = waiter;
-	LIST_HEAD(lock_chain);
-
-	waiter->task = current;
-	waiter->lock = lock;
-	debug_rt_mutex_reset_waiter(waiter);
-
-	spin_lock(&current->pi_lock);
-	current->pi_locked_by = current;
-	plist_node_init(&waiter->list_entry, current->prio);
-	plist_node_init(&waiter->pi_list_entry, current->prio);
-
-	/* Get the top priority waiter of the lock: */
-	if (rt_mutex_has_waiters(lock))
-		top_waiter = rt_mutex_top_waiter(lock);
-	plist_add(&waiter->list_entry, &lock->wait_list);
-
-	current->pi_blocked_on = waiter;
-
-	/*
-	 * Call adjust_prio_chain, when waiter is the new top waiter
-	 * or when deadlock detection is requested:
-	 */
-	if (waiter != rt_mutex_top_waiter(lock) &&
-	    !debug_rt_mutex_detect_deadlock(detect_deadlock))
-		goto out;
-
-	/* Try to lock the full chain: */
-	res = lock_pi_chain(lock, waiter, &lock_chain, 1, detect_deadlock);
-
-	if (likely(!res))
-		adjust_pi_chain(lock, waiter, top_waiter, &lock_chain);
-
-	/* Common case: we managed to lock it: */
-	if (res != -EBUSY)
-		goto out_unlock;
-
-	/* Rare case: we hit some other task running a pi chain operation: */
-	unlock_pi_chain(&lock_chain);
-
-	plist_del(&waiter->list_entry, &lock->wait_list);
-	current->pi_blocked_on = NULL;
-	current->pi_locked_by = NULL;
-	spin_unlock(&current->pi_lock);
-	fixup_rt_mutex_waiters(lock);
-
-	spin_unlock(&lock->wait_lock);
-
-	spin_lock(&pi_conflicts_lock);
-
-	spin_lock(&current->pi_lock);
-	current->pi_locked_by = current;
-	spin_lock(&lock->wait_lock);
-	if (!rt_mutex_owner(lock)) {
-		waiter->task = NULL;
-		spin_unlock(&pi_conflicts_lock);
-		goto out;
-	}
-	plist_node_init(&waiter->list_entry, current->prio);
-	plist_node_init(&waiter->pi_list_entry, current->prio);
-
-	/* Get the top priority waiter of the lock: */
-	if (rt_mutex_has_waiters(lock))
-		top_waiter = rt_mutex_top_waiter(lock);
-	plist_add(&waiter->list_entry, &lock->wait_list);
-
-	current->pi_blocked_on = waiter;
-
-	/* Lock the full chain: */
-	res = lock_pi_chain(lock, waiter, &lock_chain, 0, detect_deadlock);
-
-	/* Drop the conflicts lock before adjusting: */
-	spin_unlock(&pi_conflicts_lock);
-
-	if (likely(!res))
-		adjust_pi_chain(lock, waiter, top_waiter, &lock_chain);
-
- out_unlock:
-	unlock_pi_chain(&lock_chain);
- out:
-	current->pi_locked_by = NULL;
-	spin_unlock(&current->pi_lock);
-	return res;
-}
-
-/*
  * Optimization: check if we can steal the lock from the
  * assigned pending owner [which might not have taken the
  * lock yet]:
@@ -542,6 +446,117 @@ static int try_to_take_rt_mutex(struct r
 }
 
 /*
+ * Task blocks on lock.
+ *
+ * Prepare waiter and potentially propagate our priority into the pi chain.
+ *
+ * This must be called with lock->wait_lock held.
+ * return values: 1: waiter queued, 0: got the lock,
+ *		  -EDEADLK: deadlock detected.
+ */
+static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
+				   struct rt_mutex_waiter *waiter,
+				   int detect_deadlock __IP_DECL__)
+{
+	struct rt_mutex_waiter *top_waiter = waiter;
+	LIST_HEAD(lock_chain);
+	int res = 1;
+
+	waiter->task = current;
+	waiter->lock = lock;
+	debug_rt_mutex_reset_waiter(waiter);
+
+	spin_lock(&current->pi_lock);
+	current->pi_locked_by = current;
+	plist_node_init(&waiter->list_entry, current->prio);
+	plist_node_init(&waiter->pi_list_entry, current->prio);
+
+	/* Get the top priority waiter of the lock: */
+	if (rt_mutex_has_waiters(lock))
+		top_waiter = rt_mutex_top_waiter(lock);
+	plist_add(&waiter->list_entry, &lock->wait_list);
+
+	current->pi_blocked_on = waiter;
+
+	/*
+	 * Call adjust_prio_chain, when waiter is the new top waiter
+	 * or when deadlock detection is requested:
+	 */
+	if (waiter != rt_mutex_top_waiter(lock) &&
+	    !debug_rt_mutex_detect_deadlock(detect_deadlock))
+		goto out_unlock_pi;
+
+	/* Try to lock the full chain: */
+	res = lock_pi_chain(lock, waiter, &lock_chain, 1, detect_deadlock);
+
+	if (likely(res == 1))
+		adjust_pi_chain(lock, waiter, top_waiter, &lock_chain);
+
+	/* Common case: we managed to lock it: */
+	if (res != -EBUSY)
+		goto out_unlock_chain_pi;
+
+	/* Rare case: we hit some other task running a pi chain operation: */
+	unlock_pi_chain(&lock_chain);
+
+	plist_del(&waiter->list_entry, &lock->wait_list);
+	current->pi_blocked_on = NULL;
+	current->pi_locked_by = NULL;
+	spin_unlock(&current->pi_lock);
+	fixup_rt_mutex_waiters(lock);
+
+	spin_unlock(&lock->wait_lock);
+
+	/*
+	 * Here we have dropped all locks, and take the global
+	 * pi_conflicts_lock. We have to redo all the work, no
+	 * previous information about the lock is valid anymore:
+	 */
+	spin_lock(&pi_conflicts_lock);
+
+	spin_lock(&lock->wait_lock);
+	if (try_to_take_rt_mutex(lock __IP__)) {
+		/*
+		 * Rare race: against all odds we got the lock.
+		 */
+		res = 0;
+		goto out;
+	}
+
+	WARN_ON(!rt_mutex_owner(lock) || rt_mutex_owner(lock) == current);
+
+	spin_lock(&current->pi_lock);
+	current->pi_locked_by = current;
+
+	plist_node_init(&waiter->list_entry, current->prio);
+	plist_node_init(&waiter->pi_list_entry, current->prio);
+
+	/* Get the top priority waiter of the lock: */
+	if (rt_mutex_has_waiters(lock))
+		top_waiter = rt_mutex_top_waiter(lock);
+	plist_add(&waiter->list_entry, &lock->wait_list);
+
+	current->pi_blocked_on = waiter;
+
+	/* Lock the full chain: */
+	res = lock_pi_chain(lock, waiter, &lock_chain, 0, detect_deadlock);
+
+	/* Drop the conflicts lock before adjusting: */
+	spin_unlock(&pi_conflicts_lock);
+
+	if (likely(res == 1))
+		adjust_pi_chain(lock, waiter, top_waiter, &lock_chain);
+
+ out_unlock_chain_pi:
+	unlock_pi_chain(&lock_chain);
+ out_unlock_pi:
+	current->pi_locked_by = NULL;
+	spin_unlock(&current->pi_lock);
+ out:
+	return res;
+}
+
+/*
  * Wake up the next waiter on the lock.
  *
  * Remove the top waiter from the current tasks waiter list and from
@@ -641,11 +656,11 @@ static int remove_waiter(struct rt_mutex
 
 	spin_lock(&pi_conflicts_lock);
 
+	spin_lock(&lock->wait_lock);
+
 	spin_lock(&current->pi_lock);
 	current->pi_locked_by = current;
 
-	spin_lock(&lock->wait_lock);
-
 	/* We might have been woken up: */
 	if (!waiter->task) {
 		spin_unlock(&pi_conflicts_lock);
@@ -709,7 +724,7 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 
 	BUG_ON(rt_mutex_owner(lock) == current);
 
-	set_task_state(current, state);
+	set_current_state(state);
 
 	/* Setup the timer, when timeout != NULL */
 	if (unlikely(timeout))
@@ -743,10 +758,10 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 		if (!waiter.task) {
 			ret = task_blocks_on_rt_mutex(lock, &waiter,
 						      detect_deadlock __IP__);
-			if (ret == -EDEADLK)
+			/* got the lock or deadlock: */
+			if (ret == 0 || ret == -EDEADLK)
 				break;
-			if (ret == -EBUSY)
-				continue;
+			ret = 0;
 		}
 
 		spin_unlock_irqrestore(&lock->wait_lock, flags);
@@ -757,10 +772,10 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 			schedule_rt_mutex(lock);
 
 		spin_lock_irqsave(&lock->wait_lock, flags);
-		set_task_state(current, state);
+		set_current_state(state);
 	}
 
-	set_task_state(current, TASK_RUNNING);
+	set_current_state(TASK_RUNNING);
 
 	if (unlikely(waiter.task))
 		remove_waiter(lock, &waiter __IP__);
@@ -806,11 +821,9 @@ rt_mutex_slowtrylock(struct rt_mutex *lo
 		ret = try_to_take_rt_mutex(lock __IP__);
 		/*
 		 * try_to_take_rt_mutex() sets the lock waiters
-		 * bit. We might be the only waiter. Check if this
-		 * needs to be cleaned up.
+		 * bit unconditionally. Clean this up.
 		 */
-		if (!ret)
-			fixup_rt_mutex_waiters(lock);
+		fixup_rt_mutex_waiters(lock);
 	}
 
 	spin_unlock_irqrestore(&lock->wait_lock, flags);
Index: linux-pi-futex.mm.q/kernel/rtmutex_common.h
===================================================================
--- linux-pi-futex.mm.q.orig/kernel/rtmutex_common.h
+++ linux-pi-futex.mm.q/kernel/rtmutex_common.h
@@ -98,18 +98,18 @@ task_top_pi_waiter(struct task_struct *p
 static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock)
 {
 	return (struct task_struct *)
-		((unsigned long)((lock)->owner) & ~RT_MUTEX_OWNER_MASKALL);
+		((unsigned long)lock->owner & ~RT_MUTEX_OWNER_MASKALL);
 }
 
 static inline struct task_struct *rt_mutex_real_owner(struct rt_mutex *lock)
 {
  	return (struct task_struct *)
-		((unsigned long)((lock)->owner) & ~RT_MUTEX_HAS_WAITERS);
+		((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);
 }
 
 static inline unsigned long rt_mutex_owner_pending(struct rt_mutex *lock)
 {
-	return ((unsigned long)((lock)->owner) & RT_MUTEX_OWNER_PENDING);
+	return (unsigned long)lock->owner & RT_MUTEX_OWNER_PENDING;
 }
 
 /*
Index: linux-pi-futex.mm.q/lib/plist.c
===================================================================
--- linux-pi-futex.mm.q.orig/lib/plist.c
+++ linux-pi-futex.mm.q/lib/plist.c
@@ -38,7 +38,7 @@ void plist_add(struct plist_node *node, 
 
 	WARN_ON(!plist_node_empty(node));
 
-	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
+	list_for_each_entry(iter, &head->prio_list, plist.prio_list) {
 		if (node->prio < iter->prio)
 			goto lt_prio;
 		else if (node->prio == iter->prio) {
@@ -46,6 +46,7 @@ void plist_add(struct plist_node *node, 
 					struct plist_node, plist.prio_list);
 			goto eq_prio;
 		}
+	}
 
 lt_prio:
 	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/