rtmutex: multiple candidate owners without unrelated boosting

Current rtmutex just supports one pending owner only, this patch make any rtmutex can have multiple candidate owners.

In this changelog I use "pending owner" and "candidate owner" without distinguishing, they are the same meaning. But I think the name "candidate owner" is more suitable, so I only use "candidate owner" in the code.

In current rtmutex, the pending owner may be boosted by the tasks in the rtmutex waitlist when the pending owner is deboosted or a task in the waitlist is boosted. This boosting is unrelated, because the pending owner does not really take the rtmutex. It is not reasonable.

Example.

time1:
A(high prio) onwers the rtmutex.
B(mid prio) and C (low prio) in the waitlist.

time2
A release the lock, B becomes the pending owner
A(or other high prio task) continues to run. B's prio is lower than A, so B is just queued at the runqueue.

time3
A or other high prio task sleeps, but we have passed some time The B and C's prio are changed in the period (time2 ~ time3) due to boosting or deboosting. Now C has the priority higher than B. ***Is it reasonable that C has to boost B and help B to get the rtmutex?

NO!! I think, it is unrelated/unneed boosting before B really owns the rtmutex. We should give C a change to beat B and win the rtmutex.

This is the motivation of this patch.

An approach(wrong): when C's priority become higher and B, we deprive the pending ownership from B and give it to C and wakeup C. But this approach may lead to livelock.

So my approach: just give pending ownership(candidate ownership) to C and wakeup C. Thus we have multiple candidate owners(B and C). Any candidate owner is not boosted until it really owns the rtmutex.

The candidate ownership is assigned to the top waiter always when
1) unlock time
2) the top waiter is changed

If any candidate owner is running and calls try_to_take_rt_mutex(), it will win unconditionally and really own the lock.

How to indicate a candidate owner?
1) add a variable can_seq in the struct rtmutex, it is increased when unlock (with waiters queued).
2) when a waiter is assigned candidate ownership:

   waiter->cand_seq = rtmutex->cand_seq, waiter->cand_owner = 1;

So a waiter is candidate owner when if and only if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)

Other advantage of this patch:
1) The states of a rtmutex are reduced a half, easier to read the code.

2) the codes become shorter.

3) pending owner is not dequeued: they will retain FIFO when it is stolen.

4) like normal mutex, unlock path just do very little work and wakeup candidate owner. candidate owner dequeue its waiter when it wins the lock.

disadvantage
1) the size of struct rtmutex is slightly larger. (I can send another patch to reduce it if anyone needs)

Not advantage nor disadvantage
1) Even we support multiple candidate owners, we hardly cause "thundering herd" the number of candidate owners is likely 1.

2) two APIs are changed.
rt_mutex_owner() will not return pending owner rt_mutex_next_owner() always return the top owner, it is a candidate owner.
will not return NULL if we only have a pending owner.
I have fixed the code that use these APIs.

need updated after this patch is accepted
1) Document/*
2) the testcase scripts/rt-tester/t4-l2-pi-deboost.tst

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/rtmutex.h |    2 
 kernel/futex.c          |   25 +--
 kernel/rtmutex.c        |  339 +++++++++++++++++++-----------------------------
 kernel/rtmutex_common.h |   20 --
 4 files changed, 155 insertions(+), 231 deletions(-)

include/linux/rtmutex.h +2 -0

index 8d522ff..155ddb3 100644
@@ -24,11 +24,13 @@ extern int max_lock_depth; /* for sysctl */
  * @wait_lock:	spinlock to protect the structure
  * @wait_list:	pilist head to enqueue waiters in priority order
  * @owner:	the mutex owner
+ * @cand_seq:	the sequence number for candidate owners
  */
 struct rt_mutex {
 	raw_spinlock_t		wait_lock;
 	struct plist_head	wait_list;
 	struct task_struct	*owner;
+	unsigned long		cand_seq; /* don't need to init it! */
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 	int			save_state;
 	const char 		*name, *file;

kernel/futex.c +9 -16

index 6c683b3..6db2b92 100644
@@ -778,15 +778,6 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 
 	/*
-	 * This happens when we have stolen the lock and the original
-	 * pending owner did not enqueue itself back on the rt_mutex.
-	 * Thats not a tragedy. We know that way, that a lock waiter
-	 * is on the fly. We make the futex_q waiter the pending owner.
-	 */
-	if (!new_owner)
-		new_owner = this->task;
-
-	/*
 	 * We pass it to the next owner. (The WAITERS bit is always
 	 * kept enabled while there is PI state around. We must also
 	 * preserve the owner died bit.)

@@ -1508,8 +1499,8 @@ static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
 
 	/*
 	 * We are here either because we stole the rtmutex from the
-	 * pending owner or we are the pending owner which failed to
-	 * get the rtmutex. We have to replace the pending owner TID
+	 * candidate owner or we are the candidate owner which failed to
+	 * get the rtmutex. We have to replace the candidate owner TID
 	 * in the user space variable. This must be atomic as we have
 	 * to preserve the owner died bit here.
 	 *

@@ -1560,7 +1551,7 @@ retry:
 
 	/*
 	 * To handle the page fault we need to drop the hash bucket
-	 * lock here. That gives the other task (either the pending
+	 * lock here. That gives the other task (either the candidate
 	 * owner itself or the task which stole the rtmutex) the
 	 * chance to try the fixup of the pi_state. So once we are
 	 * back from handling the fault we need to check the pi_state

@@ -1647,18 +1638,20 @@ static int fixup_owner(u32 __user *uaddr, int fshared, struct futex_q *q,
 		/*
 		 * pi_state is incorrect, some other task did a lock steal and
 		 * we returned due to timeout or signal without taking the
-		 * rt_mutex. Too late. We can access the rt_mutex_owner without
-		 * locking, as the other task is now blocked on the hash bucket
-		 * lock. Fix the state up.
+		 * rt_mutex. Too late.
 		 */
+		raw_spin_lock(&q->pi_state->pi_mutex.wait_lock);
 		owner = rt_mutex_owner(&q->pi_state->pi_mutex);
+		if (!owner)
+			owner = rt_mutex_next_owner(&q->pi_state->pi_mutex);
+		raw_spin_unlock(&q->pi_state->pi_mutex.wait_lock);
 		ret = fixup_pi_state_owner(uaddr, q, owner, fshared);
 		goto out;
 	}
 
 	/*
 	 * Paranoia check. If we did not take the lock, then we should not be
-	 * the owner, nor the pending owner, of the rt_mutex.
+	 * the owner of the rt_mutex.
 	 */
 	if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
 		printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "

kernel/rtmutex.c +138 -201

index a960481..f5c8065 100644
@@ -20,41 +20,32 @@
 /*
  * lock->owner state tracking:
  *
- * lock->owner holds the task_struct pointer of the owner. Bit 0 and 1
- * are used to keep track of the "owner is pending" and "lock has
- * waiters" state.
+ * lock->owner holds the task_struct pointer of the owner. Bit 0
+ * are used to keep track of the "lock has waiters" state.
  *
- * owner	bit1	bit0
- * NULL		0	0	lock is free (fast acquire possible)
- * NULL		0	1	invalid state
- * NULL		1	0	Transitional State*
- * NULL		1	1	invalid state
- * taskpointer	0	0	lock is held (fast release possible)
- * taskpointer	0	1	task is pending owner
- * taskpointer	1	0	lock is held and has waiters
- * taskpointer	1	1	task is pending owner and lock has more waiters
+ * owner	bit0
+ * NULL		0	lock is free (fast acquire possible)
+ * NULL		1	lock is free and has waiters and candidate owners*
+ * taskpointer	0	lock is held (fast release possible)
+ * taskpointer	1	lock is held and has waiters
  *
- * Pending ownership is assigned to the top (highest priority)
- * waiter of the lock, when the lock is released. The thread is woken
- * up and can now take the lock. Until the lock is taken (bit 0
- * cleared) a competing higher priority thread can steal the lock
- * which puts the woken up thread back on the waiters list.
+ * Candidate ownership is assigned to the top (highest priority) waiter
+ * of the lock, when the lock is released or the top waiter of the lock
+ * is changed. The thread(s) is(are) woken up and can now take the lock.
  *
  * The fast atomic compare exchange based acquire and release is only
- * possible when bit 0 and 1 of lock->owner are 0.
+ * possible when bit 0 of lock->owner are 0.
  *
- * (*) There's a small time where the owner can be NULL and the
- * "lock has waiters" bit is set.  This can happen when grabbing the lock.
- * To prevent a cmpxchg of the owner releasing the lock, we need to set this
- * bit before looking at the lock, hence the reason this is a transitional
- * state.
+ * (*) It also can be a transitional state when grabbing the lock
+ * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
+ * we need to set the bit0 before looking at the lock, and the owner may be
+ * NULL in this small time, hence this can be a transitional state.
  */
 
 static void
-rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner,
-		   unsigned long mask)
+rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner)
 {
-	unsigned long val = (unsigned long)owner | mask;
+	unsigned long val = (unsigned long)owner;
 
 	if (rt_mutex_has_waiters(lock))
 		val |= RT_MUTEX_HAS_WAITERS;

@@ -203,15 +194,15 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 	 * reached or the state of the chain has changed while we
 	 * dropped the locks.
 	 */
-	if (!waiter || !waiter->task)
+	if (!waiter)
 		goto out_unlock_pi;
 
 	/*
 	 * Check the orig_waiter state. After we dropped the locks,
 	 * the previous owner of the lock might have released the lock
-	 * and made us the pending owner:
+	 * and made us candidate owner:
 	 */
-	if (orig_waiter && !orig_waiter->task)
+	if (orig_waiter && orig_waiter->cand_owner)
 		goto out_unlock_pi;
 
 	/*

@@ -254,6 +245,22 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 
 	/* Release the task */
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	if (!rt_mutex_owner(lock)) {
+		/*
+		 * the lock is free and has waiters, set the top waiter
+		 * as a new candidate owner when it is not set.
+		 */
+		if (top_waiter != rt_mutex_top_waiter(lock)) {
+			top_waiter = rt_mutex_top_waiter(lock);
+			top_waiter->cand_seq = lock->cand_seq;
+			if (!top_waiter->cand_owner) {
+				top_waiter->cand_owner = 1;
+				wake_up_process(top_waiter->task);
+			}
+		}
+		raw_spin_unlock(&lock->wait_lock);
+		goto out_put_task;
+	}
 	put_task_struct(task);
 
 	/* Grab the next task */

@@ -296,78 +303,16 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 }
 
 /*
- * Optimization: check if we can steal the lock from the
- * assigned pending owner [which might not have taken the
- * lock yet]:
- */
-static inline int try_to_steal_lock(struct rt_mutex *lock,
-				    struct task_struct *task)
-{
-	struct task_struct *pendowner = rt_mutex_owner(lock);
-	struct rt_mutex_waiter *next;
-	unsigned long flags;
-
-	if (!rt_mutex_owner_pending(lock))
-		return 0;
-
-	if (pendowner == task)
-		return 1;
-
-	raw_spin_lock_irqsave(&pendowner->pi_lock, flags);
-	if (task->prio >= pendowner->prio) {
-		raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-		return 0;
-	}
-
-	/*
-	 * Check if a waiter is enqueued on the pending owners
-	 * pi_waiters list. Remove it and readjust pending owners
-	 * priority.
-	 */
-	if (likely(!rt_mutex_has_waiters(lock))) {
-		raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-		return 1;
-	}
-
-	/* No chain handling, pending owner is not blocked on anything: */
-	next = rt_mutex_top_waiter(lock);
-	plist_del(&next->pi_list_entry, &pendowner->pi_waiters);
-	__rt_mutex_adjust_prio(pendowner);
-	raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-
-	/*
-	 * We are going to steal the lock and a waiter was
-	 * enqueued on the pending owners pi_waiters queue. So
-	 * we have to enqueue this waiter into
-	 * task->pi_waiters list. This covers the case,
-	 * where task is boosted because it holds another
-	 * lock and gets unboosted because the booster is
-	 * interrupted, so we would delay a waiter with higher
-	 * priority as task->normal_prio.
-	 *
-	 * Note: in the rare case of a SCHED_OTHER task changing
-	 * its priority and thus stealing the lock, next->task
-	 * might be task:
-	 */
-	if (likely(next->task != task)) {
-		raw_spin_lock_irqsave(&task->pi_lock, flags);
-		plist_add(&next->pi_list_entry, &task->pi_waiters);
-		__rt_mutex_adjust_prio(task);
-		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-	}
-	return 1;
-}
-
-/*
  * Try to take an rt-mutex
  *
- * This fails
- * - when the lock has a real owner
- * - when a different pending owner exists and has higher priority than current
- *
  * Must be called with lock->wait_lock held.
+ *
+ * @lock:	the lock to be acquired.
+ * @task:	the task which want to acquire the lock
+ * @waiter:	the waiter queued to the lock's wait list. (could be NULL)
  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

@@ -390,15 +335,73 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 
-	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock, current))
+	if (rt_mutex_owner(lock))
 		return 0;
 
+	/*
+	 * It is a queued waiter.
+	 *
+	 * Is it a candidate owner? If it is, it will win unconditionally.
+	 * And it defeats the other candidate owner(s) (if any) and
+	 * steal lock from them.
+	 */
+	if (waiter) {
+		/* candidate owner? */
+		if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)
+			goto get_lock;
+
+		/*
+		 * top waiter must be a candidate owner.
+		 * But checking it again is not a bad thing.
+		 */
+		if (waiter == rt_mutex_top_waiter(lock))
+			goto get_lock;
+	}
+
+	/*
+	 * Does it defeat the candidate owner(s) and steal lock from them?
+	 *
+	 * Note: in the rare case of a task is boosted but its waiter has not
+	 * been requeued in the lock's wait list yet, thus it can also steal
+	 * the lock.
+	 */
+	if (rt_mutex_has_waiters(lock)) {
+		if (task->prio >= rt_mutex_top_waiter(lock)->list_entry.prio)
+			return 0;
+	}
+
+get_lock:
+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+
+		raw_spin_lock_irqsave(&task->pi_lock, flags);
+
+		/* remove the queued waiter. */
+		if (waiter) {
+			plist_del(&waiter->list_entry, &lock->wait_list);
+			task->pi_blocked_on = NULL;
+		}
+
+		/*
+		 * We have to enqueue the top waiter(if have) into
+		 * task->pi_waiters list and would get boost from it.
+		 */
+		if (rt_mutex_has_waiters(lock)) {
+			top = rt_mutex_top_waiter(lock);
+			top->pi_list_entry.prio = top->list_entry.prio;
+			plist_add(&top->pi_list_entry, &task->pi_waiters);
+			__rt_mutex_adjust_prio(task);
+		}
+		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	}
+
 	/* We got the lock. */
 	debug_rt_mutex_lock(lock);
 
-	rt_mutex_set_owner(lock, current, 0);
+	rt_mutex_set_owner(lock, task);
 
-	rt_mutex_deadlock_account_lock(lock, current);
+	rt_mutex_deadlock_account_lock(lock, task);
 
 	return 1;
 }

@@ -424,6 +427,7 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 	__rt_mutex_adjust_prio(task);
 	waiter->task = task;
 	waiter->lock = lock;
+	waiter->cand_owner = 0;
 	plist_node_init(&waiter->list_entry, task->prio);
 	plist_node_init(&waiter->pi_list_entry, task->prio);
 

@@ -436,6 +440,9 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 
+	if (!owner)
+		return 0;
+
 	if (waiter == rt_mutex_top_waiter(lock)) {
 		raw_spin_lock_irqsave(&owner->pi_lock, flags);
 		plist_del(&top_waiter->pi_list_entry, &owner->pi_waiters);

@@ -472,21 +479,19 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 /*
  * Wake up the next waiter on the lock.
  *
- * Remove the top waiter from the current tasks waiter list and from
- * the lock waiter list. Set it as pending owner. Then wake it up.
+ * Remove the top waiter from the current tasks waiter list.
+ * Set it as a candidate owner. Then wake it up.
  *
  * Called with lock->wait_lock held.
  */
 static void wakeup_next_waiter(struct rt_mutex *lock)
 {
 	struct rt_mutex_waiter *waiter;
-	struct task_struct *pendowner;
 	unsigned long flags;
 
 	raw_spin_lock_irqsave(&current->pi_lock, flags);
 
 	waiter = rt_mutex_top_waiter(lock);
-	plist_del(&waiter->list_entry, &lock->wait_list);
 
 	/*
 	 * Remove it from current->pi_waiters. We do not adjust a

@@ -495,37 +500,14 @@ static void wakeup_next_waiter(struct rt_mutex *lock)
 	 * lock->wait_lock.
 	 */
 	plist_del(&waiter->pi_list_entry, &current->pi_waiters);
-	pendowner = waiter->task;
-	waiter->task = NULL;
+	waiter->cand_owner = 1;
+	waiter->cand_seq = ++lock->cand_seq;
 
-	rt_mutex_set_owner(lock, pendowner, RT_MUTEX_OWNER_PENDING);
+	rt_mutex_set_owner(lock, NULL);
 
 	raw_spin_unlock_irqrestore(&current->pi_lock, flags);
 
-	/*
-	 * Clear the pi_blocked_on variable and enqueue a possible
-	 * waiter into the pi_waiters list of the pending owner. This
-	 * prevents that in case the pending owner gets unboosted a
-	 * waiter with higher priority than pending-owner->normal_prio
-	 * is blocked on the unboosted (pending) owner.
-	 */
-	raw_spin_lock_irqsave(&pendowner->pi_lock, flags);
-
-	WARN_ON(!pendowner->pi_blocked_on);
-	WARN_ON(pendowner->pi_blocked_on != waiter);
-	WARN_ON(pendowner->pi_blocked_on->lock != lock);
-
-	pendowner->pi_blocked_on = NULL;
-
-	if (rt_mutex_has_waiters(lock)) {
-		struct rt_mutex_waiter *next;
-
-		next = rt_mutex_top_waiter(lock);
-		plist_add(&next->pi_list_entry, &pendowner->pi_waiters);
-	}
-	raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-
-	wake_up_process(pendowner);
+	wake_up_process(waiter->task);
 }
 
 /*

@@ -543,11 +525,13 @@ static void remove_waiter(struct rt_mutex *lock,
 
 	raw_spin_lock_irqsave(&current->pi_lock, flags);
 	plist_del(&waiter->list_entry, &lock->wait_list);
-	waiter->task = NULL;
 	current->pi_blocked_on = NULL;
 	raw_spin_unlock_irqrestore(&current->pi_lock, flags);
 
-	if (first && owner != current) {
+	if (!owner)
+		return;
+
+	if (first) {
 
 		raw_spin_lock_irqsave(&owner->pi_lock, flags);
 

@@ -614,22 +598,21 @@ void rt_mutex_adjust_pi(struct task_struct *task)
  * 			 or TASK_UNINTERRUPTIBLE)
  * @timeout:		 the pre-initialized and started timer, or NULL for none
  * @waiter:		 the pre-initialized rt_mutex_waiter
- * @detect_deadlock:	 passed to task_blocks_on_rt_mutex
  *
  * lock->wait_lock must be held by the caller.
  */
 static int __sched
 __rt_mutex_slowlock(struct rt_mutex *lock, int state,
 		    struct hrtimer_sleeper *timeout,
-		    struct rt_mutex_waiter *waiter,
-		    int detect_deadlock)
+		    struct rt_mutex_waiter *waiter)
 {
 	int ret = 0;
 
 	for (;;) {
 		/* Try to acquire the lock: */
-		if (try_to_take_rt_mutex(lock))
+		if (try_to_take_rt_mutex(lock, current, waiter))
 			break;
+		waiter->cand_owner = 0;
 
 		/*
 		 * TASK_INTERRUPTIBLE checks for signals and

@@ -645,39 +628,11 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,
 				break;
 		}
 
-		/*
-		 * waiter->task is NULL the first time we come here and
-		 * when we have been woken up by the previous owner
-		 * but the lock got stolen by a higher prio task.
-		 */
-		if (!waiter->task) {
-			ret = task_blocks_on_rt_mutex(lock, waiter, current,
-						      detect_deadlock);
-			/*
-			 * If we got woken up by the owner then start loop
-			 * all over without going into schedule to try
-			 * to get the lock now:
-			 */
-			if (unlikely(!waiter->task)) {
-				/*
-				 * Reset the return value. We might
-				 * have returned with -EDEADLK and the
-				 * owner released the lock while we
-				 * were walking the pi chain.
-				 */
-				ret = 0;
-				continue;
-			}
-			if (unlikely(ret))
-				break;
-		}
-
 		raw_spin_unlock(&lock->wait_lock);
 
 		debug_rt_mutex_print_deadlock(waiter);
 
-		if (waiter->task)
-			schedule_rt_mutex(lock);
+		schedule_rt_mutex(lock);
 
 		raw_spin_lock(&lock->wait_lock);
 		set_current_state(state);

@@ -698,12 +653,11 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 	int ret = 0;
 
 	debug_rt_mutex_init_waiter(&waiter);
-	waiter.task = NULL;
 
 	raw_spin_lock(&lock->wait_lock);
 
 	/* Try to acquire the lock again: */
-	if (try_to_take_rt_mutex(lock)) {
+	if (try_to_take_rt_mutex(lock, current, NULL)) {
 		raw_spin_unlock(&lock->wait_lock);
 		return 0;
 	}

@@ -717,12 +671,14 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 			timeout->task = NULL;
 	}
 
-	ret = __rt_mutex_slowlock(lock, state, timeout, &waiter,
-				  detect_deadlock);
+	ret = task_blocks_on_rt_mutex(lock, &waiter, current, detect_deadlock);
+
+	if (likely(!ret))
+		ret = __rt_mutex_slowlock(lock, state, timeout, &waiter);
 
 	set_current_state(TASK_RUNNING);
 
-	if (unlikely(waiter.task))
+	if (unlikely(ret))
 		remove_waiter(lock, &waiter);
 
 	/*

@@ -737,14 +693,6 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 	if (unlikely(timeout))
 		hrtimer_cancel(&timeout->timer);
 
-	/*
-	 * Readjust priority, when we did not get the lock. We might
-	 * have been the pending owner and boosted. Since we did not
-	 * take the lock, the PI boost has to go.
-	 */
-	if (unlikely(ret))
-		rt_mutex_adjust_prio(current);
-
 	debug_rt_mutex_free_waiter(&waiter);
 
 	return ret;

@@ -762,7 +710,7 @@ rt_mutex_slowtrylock(struct rt_mutex *lock)
 
 	if (likely(rt_mutex_owner(lock) != current)) {
 
-		ret = try_to_take_rt_mutex(lock);
+		ret = try_to_take_rt_mutex(lock, current, NULL);
 		/*
 		 * try_to_take_rt_mutex() sets the lock waiters
 		 * bit unconditionally. Clean this up.

@@ -992,7 +940,7 @@ void rt_mutex_init_proxy_locked(struct rt_mutex *lock,
 {
 	__rt_mutex_init(lock, NULL);
 	debug_rt_mutex_proxy_lock(lock, proxy_owner);
-	rt_mutex_set_owner(lock, proxy_owner, 0);
+	rt_mutex_set_owner(lock, proxy_owner);
 	rt_mutex_deadlock_account_lock(lock, proxy_owner);
 }
 

@@ -1008,7 +956,7 @@ void rt_mutex_proxy_unlock(struct rt_mutex *lock,
 			   struct task_struct *proxy_owner)
 {
 	debug_rt_mutex_proxy_unlock(lock);
-	rt_mutex_set_owner(lock, NULL, 0);
+	rt_mutex_set_owner(lock, NULL);
 	rt_mutex_deadlock_account_unlock(proxy_owner);
 }
 

@@ -1034,20 +982,14 @@ int rt_mutex_start_proxy_lock(struct rt_mutex *lock,
 
 	raw_spin_lock(&lock->wait_lock);
 
-	mark_rt_mutex_waiters(lock);
-
-	if (!rt_mutex_owner(lock) || try_to_steal_lock(lock, task)) {
-		/* We got the lock for task. */
-		debug_rt_mutex_lock(lock);
-		rt_mutex_set_owner(lock, task, 0);
+	if (try_to_take_rt_mutex(lock, task, NULL)) {
 		raw_spin_unlock(&lock->wait_lock);
-		rt_mutex_deadlock_account_lock(lock, task);
 		return 1;
 	}
 
 	ret = task_blocks_on_rt_mutex(lock, waiter, task, detect_deadlock);
 
-	if (ret && !waiter->task) {
+	if (ret && waiter->cand_owner) {
 		/*
 		 * Reset the return value. We might have
 		 * returned with -EDEADLK and the owner

@@ -1056,6 +998,10 @@ int rt_mutex_start_proxy_lock(struct rt_mutex *lock,
 		 */
 		ret = 0;
 	}
+
+	if (unlikely(ret))
+		remove_waiter(lock, waiter);
+
 	raw_spin_unlock(&lock->wait_lock);
 
 	debug_rt_mutex_print_deadlock(waiter);

@@ -1110,12 +1056,11 @@ int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
 
 	set_current_state(TASK_INTERRUPTIBLE);
 
-	ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter,
-				  detect_deadlock);
+	ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter);
 
 	set_current_state(TASK_RUNNING);
 
-	if (unlikely(waiter->task))
+	if (unlikely(ret))
 		remove_waiter(lock, waiter);
 
 	/*

@@ -1126,13 +1071,5 @@ int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
 
 	raw_spin_unlock(&lock->wait_lock);
 
-	/*
-	 * Readjust priority, when we did not get the lock. We might have been
-	 * the pending owner and boosted. Since we did not take the lock, the
-	 * PI boost has to go.
-	 */
-	if (unlikely(ret))
-		rt_mutex_adjust_prio(current);
-
 	return ret;
 }

kernel/rtmutex_common.h +6 -14

index 97a2f81..178d659 100644
@@ -43,12 +43,16 @@ extern void schedule_rt_mutex_test(struct rt_mutex *lock);
  * @list_entry:		pi node to enqueue into the mutex waiters list
  * @pi_list_entry:	pi node to enqueue into the mutex owner waiters list
  * @task:		task reference to the blocked task
+ * @cand_owner:		did it became candidate owner
+ * @cand_seq:		sequence number for checking for candidate owner
  */
 struct rt_mutex_waiter {
 	struct plist_node	list_entry;
 	struct plist_node	pi_list_entry;
 	struct task_struct	*task;
 	struct rt_mutex		*lock;
+	int			cand_owner;
+	unsigned long		cand_seq;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 	unsigned long		ip;
 	struct pid		*deadlock_task_pid;

@@ -91,9 +95,8 @@ task_top_pi_waiter(struct task_struct *p)
 /*
  * lock->owner state tracking:
  */
-#define RT_MUTEX_OWNER_PENDING	1UL
-#define RT_MUTEX_HAS_WAITERS	2UL
-#define RT_MUTEX_OWNER_MASKALL	3UL
+#define RT_MUTEX_HAS_WAITERS	1UL
+#define RT_MUTEX_OWNER_MASKALL	1UL
 
 static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock)
 {

@@ -101,17 +104,6 @@ static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock)
 		((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);
-}
-
-static inline unsigned long rt_mutex_owner_pending(struct rt_mutex *lock)
-{
-	return (unsigned long)lock->owner & RT_MUTEX_OWNER_PENDING;
-}
-
 /*
  * PI-futex support (proxy locking functions, etc.):
  */

scripts/rt-tester/check-all.sh +0 -0

old mode 100644
new mode 100755

scripts/rt-tester/rt-tester.py +0 -0

old mode 100644
new mode 100755

Quoted 7 lines

This is the motivation of this patch.

An approach(wrong): when C's priority become higher and B, we deprive the pending ownership from B and give it to C and wakeup C. But this approach may lead to livelock.

I'm curious to how this can cause a livelock. I'm not doubting you, but I just woke up, and I'm only half way through my first cup of coffee.

Quoted 8 lines

So my approach: just give pending ownership(candidate ownership) to C and wakeup C. Thus we have multiple candidate owners(B and C). Any candidate owner is not boosted until it really owns the rtmutex.

The candidate ownership is assigned to the top waiter always when
1) unlock time
2) the top waiter is changed

(not looking at the code itself yet) How is a candidate ownership changed when the top waiter is changed?

Or is that only when the lock
has been unlocked and the current candidate hasn't taken it yet?

Quoted 4 lines

If any candidate owner is running and calls try_to_take_rt_mutex(), it will win unconditionally and really own the lock.

(still not looking at code :-)  What happens if another high prio process comes along and tries to take the lock before the candidate gets there. That high prio task should still steal the lock. The candidate will lose it then.

Quoted 9 lines

How to indicate a candidate owner?
1) add a variable can_seq in the struct rtmutex, it is increased when unlock (with waiters queued).
2) when a waiter is assigned candidate ownership:
   waiter->cand_seq = rtmutex->cand_seq, waiter->cand_owner = 1; So a waiter is candidate owner when if and only if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)

Again, what happens when another high prio task comes along and takes the lock? Does cand_owner turn to zero? (Almost done with my coffee, then I'll look at code. Or maybe after a second cup, rtmutex requires two cups to review code).

Quoted 4 lines

Other advantage of this patch:
1) The states of a rtmutex are reduced a half, easier to read the code.

This is good.

Quoted 1 line

2) the codes become shorter.

This is also good.

Quoted 1 line

3) pending owner is not dequeued: they will retain FIFO when it is stolen.

I don't quite understand this part.

Quoted 3 lines

4) like normal mutex, unlock path just do very little work and wakeup candidate owner. candidate owner dequeue its waiter when it wins the lock.

Hmm, this seems tricky. I kind of remember going this path and hitting issues before.

Quoted 5 lines

disadvantage
1) the size of struct rtmutex is slightly larger. (I can send another patch to reduce it if anyone needs)

If we do go this way, we would want to shrink this struct. The -rt patch (which this came from) turns almost all spinlocks into rtmutexes, so any small increase in this struct will result in a huge bloat of the kernel.

Quoted 4 lines

Not advantage nor disadvantage
1) Even we support multiple candidate owners, we hardly cause "thundering herd" the number of candidate owners is likely 1.

This is because a candidate is only created when the lock is first unlocked or it is unlocked and a lower prio waiter is boosted above the current candidate, correct?

Quoted 10 lines

2) two APIs are changed.
   rt_mutex_owner() will not return pending owner rt_mutex_next_owner() always return the top owner, it is a candidate owner. will not return NULL if we only have a pending owner.
   I have fixed the code that use these APIs.

need updated after this patch is accepted
1) Document/*
2) the testcase scripts/rt-tester/t4-l2-pi-deboost.tst

Quoted 1 line

Signed-off-by Lai Jiangshan <[email protected]>

I'll put this on my todo list to review.

Thanks!

Quoted 11 lines · Steven Rostedt

Quoted 7 lines

This is the motivation of this patch.

An approach(wrong): when C's priority become higher and B, we deprive the pending ownership from B and give it to C and wakeup C. But this approach may lead to livelock.

I'm curious to how this can cause a livelock. I'm not doubting you, but I just woke up, and I'm only half way through my first cup of coffee.

if B is deprived, B has go to sleep again. In rare condition, B,C 's priority are changed frequent, the pending ownership is given to B/ deprived from B and given to C/ deprived from C and given to B
......

No task can go forward, it is a kind of livelock.

Quoted 6 lines

Quoted 6 lines

So my approach: just give pending ownership(candidate ownership) to C and wakeup C. Thus we have multiple candidate owners(B and C). Any candidate owner is not boosted until it really owns the rtmutex.

Quoted 6 lines

Quoted 3 lines

The candidate ownership is assigned to the top waiter always when
1) unlock time
2) the top waiter is changed

(not looking at the code itself yet) How is a candidate ownership changed when the top waiter is changed?

candidate ownerships will not changed until some task really owns it. when the top waiter is changed, the top waiter is also assigned candidate ownership. The candidate ownerships are not stored in struct rtmutex, they are store in the corresponding waiters.

Quoted 2 lines

Or is that only when the lock
has been unlocked and the current candidate hasn't taken it yet?

Yes, the current candidate hasn't taken it yet, it is just woken up.

Quoted 9 lines

Quoted 4 lines

If any candidate owner is running and calls try_to_take_rt_mutex(), it will win unconditionally and really own the lock.

(still not looking at code :-) What happens if another high prio process comes along and tries to take the lock before the candidate gets there. That high prio task should still steal the lock. The candidate will lose it then.

Another higher prio task will steal the lock before the candidate gets there. The candidates will go to sleep again.

Quoted 10 lines

Quoted 9 lines

How to indicate a candidate owner?
1) add a variable can_seq in the struct rtmutex, it is increased when unlock (with waiters queued).
2) when a waiter is assigned candidate ownership:

   waiter->cand_seq = rtmutex->cand_seq, waiter->cand_owner = 1;

So a waiter is candidate owner when if and only if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)

Quoted 4 lines

Again, what happens when another high prio task comes along and takes the lock? Does cand_owner turn to zero? (Almost done with my coffee, then I'll look at code. Or maybe after a second cup, rtmutex requires two cups to review code).

After this lucky high prio task release the lock, the lock->cand_seq is increased. so there is no candidate owner until we assign new candidate owners. (we will assign a new one immediately)

Quoted 13 lines

Quoted 6 lines

Other advantage of this patch:
1) The states of a rtmutex are reduced a half, easier to read the code.

This is good.

Quoted 1 line

2) the codes become shorter.

This is also good.

Quoted 3 lines

Quoted 1 line

3) pending owner is not dequeued: they will retain FIFO when it is stolen.

I don't quite understand this part.

if B C have the some priority and are queued in the waitlist of a lock which is owned by A. A release it. B is assigned pending ownership and dequeued. But D steal the lock and B is enqueued. Now, the top waiter is C, not B. It breaks FIFO.

Quoted 5 lines

Quoted 4 lines

4) like normal mutex, unlock path just do very little work and wakeup candidate owner. candidate owner dequeue its waiter when it wins the lock.

Quoted 2 lines

Hmm, this seems tricky. I kind of remember going this path and hitting issues before.

if we have only one pending owner, we must do something for the pending owner and prepared it to be boosted when needed, so it's not possible that the unlock path just do very little work.

multiple candidates make things simpler.

Quoted 19 lines · Lai Jiangshan

Quoted 11 lines · Steven Rostedt

Quoted 7 lines

This is the motivation of this patch.

An approach(wrong): when C's priority become higher and B, we deprive the pending ownership from B and give it to C and wakeup C. But this approach may lead to livelock.

I'm curious to how this can cause a livelock. I'm not doubting you, but I just woke up, and I'm only half way through my first cup of coffee.

if B is deprived, B has go to sleep again. In rare condition, B,C 's priority are changed frequent, the pending ownership is given to B/ deprived from B and given to C/ deprived from C and given to B
......

Quoted 1 line

No task can go forward, it is a kind of livelock.

Hmm, to have C and B change prios frequently, they will need to either have someone in some for loop doing chrt on them (which is just bad), or have lots of RT tasks constantly blocking on tasks that they own, which is also bad. I find this far from a livelock, and any case that does this would have more issues than causing a livelock here.

Not advantage nor disadvantage
1) Even we support multiple candidate owners, we hardly cause "thundering herd" the number of candidate owners is likely 1.

2) two APIs are changed.
rt_mutex_owner() will not return pending owner rt_mutex_next_owner() always return the top owner, it is a candidate owner.
will not return NULL if we only have a pending owner.
I have fixed the code that use these APIs.

include/linux/rtmutex.h +3 -1

+	}
 	put_task_struct(task);
 
  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

@@ -390,15 +335,73 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 

include/linux/rtmutex.h +18 -0

+	 */
+	if (rt_mutex_has_waiters(lock)) {
+		if (task->prio >= rt_mutex_top_waiter(lock)->list_entry.prio)
+			return 0;
+	}
+
+get_lock:
+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+
+		raw_spin_lock_irqsave(&task->pi_lock, flags);
+
+		/* remove the queued waiter. */
+		if (waiter) {
+			plist_del(&waiter->list_entry, &lock->wait_list);
+			task->pi_blocked_on = NULL;
+		}

Quoted 9 lines

include/linux/rtmutex.h +1 -0

@@ -24,11 +24,13 @@ extern int max_lock_depth; /* for sysctl */
  * @wait_lock:	spinlock to protect the structure
  * @wait_list:	pilist head to enqueue waiters in priority order
  * @owner:	the mutex owner
+ * @cand_seq:	the sequence number for candidate owners
  */
 struct rt_mutex {

include/linux/rtmutex.h extern int max_lock_depth; /* for sysctl */ · line 33

Quoted 4 lines

include/linux/rtmutex.h +1 -0

 	raw_spinlock_t		wait_lock;
 	struct plist_head	wait_list;
 	struct task_struct	*owner;
+	unsigned long		cand_seq; /* don't need to init it! */

I really do not like unitialized stuff. Omitting this init saves ZERO performance wise and it's going to confuse the hell out of someone who tries to debug this code.

include/linux/rtmutex.h static int rt_mutex_adjust_prio_chain(struct task_struct *task, · line 251

Quoted 10 lines

include/linux/rtmutex.h +4 -0

 	/*

@@ -254,6 +245,22 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 
 	/* Release the task */
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	if (!rt_mutex_owner(lock)) {
+		/*
+		 * the lock is free and has waiters, set the top waiter
+		 * as a new candidate owner when it is not set.

It took me a while to grok this comment. It should read:

/*
* If the requeue above changed the top waiter, then we need to
* make it a candidate owner and possibly wake it up. */

Right ?

include/linux/rtmutex.h static int rt_mutex_adjust_prio_chain(struct task_struct *task, · line 253

Quoted 3 lines

include/linux/rtmutex.h +2 -0

+		 */
+		if (top_waiter != rt_mutex_top_waiter(lock)) {

Shouldn't this:

- clear cand_owner on the previous top_waiter ?
- increment the cand_seq ?

If we increment cand_seq, then we can get rid of cand_owner completely as waiter->cand_seq == lock->cand_seq should be sufficient. And it would automatically prefer the new top waiter and not give the lock to some random on the fly task.

include/linux/rtmutex.h static int rt_mutex_adjust_prio_chain(struct task_struct *task, · line 262

Quoted 10 lines

include/linux/rtmutex.h +9 -0

+			top_waiter = rt_mutex_top_waiter(lock);
+			top_waiter->cand_seq = lock->cand_seq;
+			if (!top_waiter->cand_owner) {
+				top_waiter->cand_owner = 1;
+				wake_up_process(top_waiter->task);
+			}
+		}
+		raw_spin_unlock(&lock->wait_lock);
+		goto out_put_task;

If I understand correctly, then this is the equivalent to the original breakout based on !task->pi_blocked_on, right ?

Quoted 19 lines

include/linux/rtmutex.h +4 -2

+	}
 	put_task_struct(task);
 
  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

@@ -390,15 +335,73 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 
-	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock, current))
+	if (rt_mutex_owner(lock))
 		return 0;
 

include/linux/rtmutex.h static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 346

Quoted 6 lines

include/linux/rtmutex.h +6 -0

+	/*
+	 * It is a queued waiter.
+	 *
+	 * Is it a candidate owner? If it is, it will win unconditionally.
+	 * And it defeats the other candidate owner(s) (if any) and
+	 * steal lock from them.

Why ? If the boost code changes the top waiter and wakes up the new candidate, then this new one really should get the lock and the old on the fly candidate should queue itself back.

include/linux/rtmutex.h static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 358

Quoted 13 lines

include/linux/rtmutex.h +12 -0

+	 */
+	if (waiter) {
+		/* candidate owner? */
+		if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)
+			goto get_lock;
+
+		/*
+		 * top waiter must be a candidate owner.
+		 * But checking it again is not a bad thing.
+		 */
+		if (waiter == rt_mutex_top_waiter(lock))
+			goto get_lock;

Huch ? This should never happen and therefor this should be a WARN_ON_ONCE(). We really do not put "checking is not a bad thing" code in such a fragile and complex construct. Something is very wrong when you ever hit this.

include/linux/rtmutex.h static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 366

Quoted 8 lines

include/linux/rtmutex.h +8 -0

+	}
+
+	/*
+	 * Does it defeat the candidate owner(s) and steal lock from them?
+	 *
+	 * Note: in the rare case of a task is boosted but its waiter has not
+	 * been requeued in the lock's wait list yet, thus it can also steal
+	 * the lock.

How should this happen with the new code ? The waiter remains in the wait list and boosting does not change that. So that comment is misleading.

Quoted 25 lines

include/linux/rtmutex.h +24 -0

+	 */
+	if (rt_mutex_has_waiters(lock)) {
+		if (task->prio >= rt_mutex_top_waiter(lock)->list_entry.prio)
+			return 0;
+	}
+
+get_lock:
+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+
+		raw_spin_lock_irqsave(&task->pi_lock, flags);
+
+		/* remove the queued waiter. */
+		if (waiter) {
+			plist_del(&waiter->list_entry, &lock->wait_list);
+			task->pi_blocked_on = NULL;
+		}
+
+		/*
+		 * We have to enqueue the top waiter(if have) into
+		 * task->pi_waiters list and would get boost from it.
+		 */
+		if (rt_mutex_has_waiters(lock)) {

include/linux/rtmutex.h static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 394

Quoted 4 lines

include/linux/rtmutex.h +4 -0

+			top = rt_mutex_top_waiter(lock);
+			top->pi_list_entry.prio = top->list_entry.prio;
+			plist_add(&top->pi_list_entry, &task->pi_waiters);
+			__rt_mutex_adjust_prio(task);

Why should we boost ? Because we can have several candidates on the fly and we don't care which one is the highest prio candidate? That looks wrong.

Quoted 3 lines

include/linux/rtmutex.h +2 -0

+		}
+		raw_spin_unlock_irqrestore(&task->pi_lock, flags);

include/linux/rtmutex.h static int task_blocks_on_rt_mutex(struct rt_mutex *lock, · line 430

Quoted 5 lines

include/linux/rtmutex.h +1 -0

@@ -424,6 +427,7 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 	__rt_mutex_adjust_prio(task);
 	waiter->task = task;
 	waiter->lock = lock;
+	waiter->cand_owner = 0;

This should init waiter->cand_seq to RTMUTEX_CAND_SEQ_MAX and get rid of cand_owner.

include/linux/rtmutex.h static int task_blocks_on_rt_mutex(struct rt_mutex *lock, · line 431

Quoted 2 lines

include/linux/rtmutex.h +1 -0

+	waiter->cand_seq = ++lock->cand_seq;

If we make cand_seq an indicator then we need to do

   lock->cand_seq = (lock->cand_seq + 1) & ~RTMUTEX_CAND_SEQ_MAX;

include/linux/rtmutex.h int rt_mutex_finish_proxy_lock(struct rt_mutex *lock, · line 1114

Quoted 6 lines

include/linux/rtmutex.h +0 -2

@@ -1110,12 +1056,11 @@ int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
 
 	set_current_state(TASK_INTERRUPTIBLE);
 
-	ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter,
-				  detect_deadlock);

Hmm, so we loose the deadlock detection in that case. Not sure whether it matters though.

All in all I like the idea and I think we should give it a try, but I definitely want to test a patch against -RT, as this will shake out all problems in no time.

But this may lead to livelock if we do deprive candidate ownership as I mentioned (the mail I reply to Steven)

Any random on the fly task is a reasonable task for the owner in this patch.

A(assigned the first candidate ownership), B, C, D, E... are in the waitlist. But before new owner really take the lock, B, D 's priority are raised and they became the top waiter at least once, (D is the top at the end, D, B, A, C, E....) B and D are also candidate owners. In my patch, A, B, D have the chance to compete the lock, they are all reasonable because they are candidate owners, including A!

OK, let's consider the same case but without this patch.
A is assigned the pending ownership. B, C, D, E... are in the waitlist, But before new owner really take the lock, B, D 's priority are raised. In the end, only A can complete the lock, B and D just do boost A and help A. only A!

Summary, the reason I will give the lock to some random on the fly task which is one of the candidate owners:
1) avoid livelock

2) no worse than the code without this patch.

Quoted 14 lines

kernel/rtmutex.c static int rt_mutex_adjust_prio_chain(struct task_struct *task, · line 262

Quoted 11 lines

kernel/rtmutex.c +9 -0

+			top_waiter = rt_mutex_top_waiter(lock);
+			top_waiter->cand_seq = lock->cand_seq;
+			if (!top_waiter->cand_owner) {
+				top_waiter->cand_owner = 1;
+				wake_up_process(top_waiter->task);
+			}
+		}
+		raw_spin_unlock(&lock->wait_lock);
+		goto out_put_task;

If I understand correctly, then this is the equivalent to the original breakout based on !task->pi_blocked_on, right ?

Correct, original breakout when !pending_owner_task->pi_bocked_on, but candidate owners are still in the waitlist and ->pi_bocked_on still pointers to its waiter. Now we breakout when the lock has no owner(but has candidate owner(s) on the fly, we don't boost it).

Quoted 19 lines

Quoted 19 lines

kernel/rtmutex.c +4 -2

+	}
 	put_task_struct(task);
 
  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

@@ -390,15 +335,73 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 
-	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock, current))
+	if (rt_mutex_owner(lock))
 		return 0;
 

Quoted 10 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 346

Quoted 6 lines

kernel/rtmutex.c +6 -0

+	/*
+	 * It is a queued waiter.
+	 *
+	 * Is it a candidate owner? If it is, it will win unconditionally.
+	 * And it defeats the other candidate owner(s) (if any) and
+	 * steal lock from them.

Why ? If the boost code changes the top waiter and wakes up the new candidate, then this new one really should get the lock and the old on the fly candidate should queue itself back.

See above, all candidate owner have the chance to compete the lock. It is required for avoiding the livelock.

If we have other way to avoiding the livelock, we will use only one candidate owner, you, Steven and I will very happy.

Quoted 20 lines

Quoted 4 lines

kernel/rtmutex.c +2 -0

+	 */
+	if (waiter) {

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 358

Quoted 10 lines

kernel/rtmutex.c +10 -0

+		/* candidate owner? */
+		if (waiter->cand_owner && waiter->cand_seq == lock->cand_seq)
+			goto get_lock;
+
+		/*
+		 * top waiter must be a candidate owner.
+		 * But checking it again is not a bad thing.
+		 */
+		if (waiter == rt_mutex_top_waiter(lock))
+			goto get_lock;

Huch ? This should never happen and therefor this should be a WARN_ON_ONCE(). We really do not put "checking is not a bad thing" code in such a fragile and complex construct. Something is very wrong when you ever hit this.

Quoted 12 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 366

Quoted 8 lines

kernel/rtmutex.c +8 -0

+	}
+
+	/*
+	 * Does it defeat the candidate owner(s) and steal lock from them?
+	 *
+	 * Note: in the rare case of a task is boosted but its waiter has not
+	 * been requeued in the lock's wait list yet, thus it can also steal
+	 * the lock.

How should this happen with the new code ? The waiter remains in the wait list and boosting does not change that. So that comment is misleading.

When someone boosted current task p, but it fail to take the p->pi_block_on->lock->wait_lock,

and current task p success take it and call try_to_take_rt_mutex() before p->pi_block_on is requeued in the waitlist. current task should also have chance to win the lock even it is not candidate owner/top waiter. It will win when it has the higher priority than the top waiter.

Quoted 27 lines

Quoted 27 lines

kernel/rtmutex.c +24 -0

+	 */
+	if (rt_mutex_has_waiters(lock)) {
+		if (task->prio >= rt_mutex_top_waiter(lock)->list_entry.prio)
+			return 0;
+	}
+
+get_lock:
+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+
+		raw_spin_lock_irqsave(&task->pi_lock, flags);
+
+		/* remove the queued waiter. */
+		if (waiter) {
+			plist_del(&waiter->list_entry, &lock->wait_list);
+			task->pi_blocked_on = NULL;
+		}
+
+		/*
+		 * We have to enqueue the top waiter(if have) into
+		 * task->pi_waiters list and would get boost from it.
+		 */
+		if (rt_mutex_has_waiters(lock)) {

Quoted 8 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 394

Quoted 4 lines

kernel/rtmutex.c +4 -0

+			top = rt_mutex_top_waiter(lock);
+			top->pi_list_entry.prio = top->list_entry.prio;
+			plist_add(&top->pi_list_entry, &task->pi_waiters);
+			__rt_mutex_adjust_prio(task);

Why should we boost ? Because we can have several candidates on the fly and we don't care which one is the highest prio candidate? That looks wrong.

A really owner should (be boosted)/(prepare to be booted) by the waiters. such code is also needed in original code.

Quoted 5 lines

Quoted 4 lines

(quoted diff) +2 -0

+		}
+		raw_spin_unlock_irqrestore(&task->pi_lock, flags);

Quoted 8 lines

kernel/rtmutex.c static int task_blocks_on_rt_mutex(struct rt_mutex *lock, · line 430

Quoted 5 lines

kernel/rtmutex.c +1 -0

@@ -424,6 +427,7 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 	__rt_mutex_adjust_prio(task);
 	waiter->task = task;
 	waiter->lock = lock;
+	waiter->cand_owner = 0;

This should init waiter->cand_seq to RTMUTEX_CAND_SEQ_MAX and get rid of cand_owner.

good! thanks.

Quoted 18 lines

kernel/rtmutex.c static void wakeup_next_waiter(struct rt_mutex *lock) · line 504

Quoted 3 lines

kernel/rtmutex.c +1 -0

+	waiter->cand_seq = ++lock->cand_seq;

If we make cand_seq an indicator then we need to do

   lock->cand_seq = (lock->cand_seq + 1) & ~RTMUTEX_CAND_SEQ_MAX;

kernel/rtmutex.c int rt_mutex_finish_proxy_lock(struct rt_mutex *lock, · line 1114

Quoted 6 lines

kernel/rtmutex.c +0 -2

@@ -1110,12 +1056,11 @@ int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
 
 	set_current_state(TASK_INTERRUPTIBLE);
 
-	ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter,
-				  detect_deadlock);

Hmm, so we loose the deadlock detection in that case. Not sure whether it matters though.

Quoted 4 lines

All in all I like the idea and I think we should give it a try, but I definitely want to test a patch against -RT, as this will shake out all problems in no time.

Thanks,
Lai

kernel/rtmutex.c +5 -0

+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+
+		raw_spin_lock_irqsave(&task->pi_lock, flags);

Quoted 5 lines · Lai Jiangshan

+     if (waiter || rt_mutex_has_waiters(lock)) {
+             unsigned long flags;
+             struct rt_mutex_waiter *top;

kernel/rtmutex.c +2 -0

+
+             raw_spin_lock_irqsave(&task->pi_lock, flags);

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 359

Quoted 10 lines

kernel/rtmutex.c +10 -0

+
+             /* remove the queued waiter. */
+             if (waiter) {
+                     plist_del(&waiter->list_entry, &lock->wait_list);
+                     task->pi_blocked_on = NULL;
+             }
+
+             /*
+              * We have to enqueue the top waiter(if have) into
+              * task->pi_waiters list and would get boost from it.

No, we don't get boosted from it. We just have to enqueue it into pi_waiters list. There is no boosting happening at this point. Please be very careful with the comments in this code.

Otherwise this looks really interesting. Still this wants to be ported to -rt and stress tested there.

Quoted 21 lines · Thomas Gleixner

Quoted 5 lines · Lai Jiangshan

+     if (waiter || rt_mutex_has_waiters(lock)) {
+             unsigned long flags;
+             struct rt_mutex_waiter *top;

kernel/rtmutex.c +2 -0

+
+             raw_spin_lock_irqsave(&task->pi_lock, flags);

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 359

Quoted 10 lines

kernel/rtmutex.c +10 -0

+
+             /* remove the queued waiter. */
+             if (waiter) {
+                     plist_del(&waiter->list_entry, &lock->wait_list);
+                     task->pi_blocked_on = NULL;
+             }
+
+             /*
+              * We have to enqueue the top waiter(if have) into
+              * task->pi_waiters list and would get boost from it.

No, we don't get boosted from it. We just have to enqueue it into pi_waiters list. There is no boosting happening at this point. Please be very careful with the comments in this code.

Quoted 3 lines

Otherwise this looks really interesting. Still this wants to be ported to -rt and stress tested there.

Hi, Thomas,

Where can I find the code of stress testcases?

RT itself will stress test the rtmutex code as much as it goes as we convert almost every lock into a rtmutex there.

Steven, could you have a look at that ?

Quoted 21 lines · Thomas Gleixner

Quoted 5 lines · Lai Jiangshan

kernel/rtmutex.c +5 -0

+     if (waiter || rt_mutex_has_waiters(lock)) {
+             unsigned long flags;
+             struct rt_mutex_waiter *top;
+
+             raw_spin_lock_irqsave(&task->pi_lock, flags);

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 359

Quoted 10 lines

kernel/rtmutex.c +10 -0

+
+             /* remove the queued waiter. */
+             if (waiter) {
+                     plist_del(&waiter->list_entry,&lock->wait_list);
+                     task->pi_blocked_on = NULL;
+             }
+
+             /*
+              * We have to enqueue the top waiter(if have) into
+              * task->pi_waiters list and would get boost from it.

No, we don't get boosted from it. We just have to enqueue it into pi_waiters list. There is no boosting happening at this point. Please be very careful with the comments in this code.

Quoted 3 lines

Otherwise this looks really interesting. Still this wants to be ported to -rt and stress tested there.

Hi, Thomas,

Where can I find the code of stress testcases?

Quoted 3 lines

Hi, Thomas,

Where can I find the code of stress testcases?

See http://rt.wiki.kernel.org, There are several benchmarks available for RT there.

I believe there are some built-int rt-mutex testers as well:\
CONFIG_RT_MUTEX_TESTER

On 12/17/2010 04:33 AM, Darren Hart wrote:

I also try to port it to -rt. Steven, have you ported it to -rt?

Quoted 3 lines · Lai Jiangshan

On 12/17/2010 04:33 AM, Darren Hart wrote:

I also try to port it to -rt. Steven, have you ported it to -rt?

I'm porting it now. -rt does a a bit to the rtmutex.c code, and I spent a bit of time cleaning it up. I finally got your patch to compile, and now I'm debugging it ;-)

I'm hoping to have it ready to post tomorrow.

Signed-off-by Lai Jiangshan <[email protected]>

---
 kernel/futex.c          |   26 +---
 kernel/rtmutex.c        |  306 ++++++++++++++++--------------------------------
 kernel/rtmutex_common.h |   16 --
 3 files changed, 116 insertions(+), 232 deletions(-)

kernel/futex.c +0 -0

index 6c683b3..5f4ea5f 100644

kernel/futex.c +0 -9

 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 
 	/*
-	 * This happens when we have stolen the lock and the original
-	 * pending owner did not enqueue itself back on the rt_mutex.
-	 * Thats not a tragedy. We know that way, that a lock waiter
-	 * is on the fly. We make the futex_q waiter the pending owner.
-	 */
-	if (!new_owner)
-		new_owner = this->task;
-
-	/*
 	 * We pass it to the next owner. (The WAITERS bit is always
 	 * kept enabled while there is PI state around. We must also
 	 * preserve the owner died bit.)

kernel/futex.c +5 -1

 		 */
+		raw_spin_lock(&q->pi_state->pi_mutex.wait_lock);
 		owner = rt_mutex_owner(&q->pi_state->pi_mutex);
+		if (!owner)
+			owner = rt_mutex_next_owner(&q->pi_state->pi_mutex);
+		raw_spin_unlock(&q->pi_state->pi_mutex.wait_lock);
 		ret = fixup_pi_state_owner(uaddr, q, owner, fshared);
 		goto out;
 	}
 
 	/*
 	 * Paranoia check. If we did not take the lock, then we should not be
-	 * the owner, nor the pending owner, of the rt_mutex.
+	 * the owner of the rt_mutex.
 	 */
 	if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
 		printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "

kernel/rtmutex.c +0 -0

index a960481..53b9b49 100644

kernel/rtmutex.c +0 -11

  *
- * owner	bit1	bit0
- * NULL		0	0	lock is free (fast acquire possible)
- * NULL		0	1	invalid state
- * NULL		1	0	Transitional State*
- * NULL		1	1	invalid state
- * taskpointer	0	0	lock is held (fast release possible)
- * taskpointer	0	1	task is pending owner
- * taskpointer	1	0	lock is held and has waiters
- * taskpointer	1	1	task is pending owner and lock has more waiters
- *
- * Pending ownership is assigned to the top (highest priority)

kernel/rtmutex.c +2 -3

  */
 
 static void
-rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner,
-		   unsigned long mask)
+rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner)
 {
-	unsigned long val = (unsigned long)owner | mask;
+	unsigned long val = (unsigned long)owner;
 
 	if (rt_mutex_has_waiters(lock))
 		val |= RT_MUTEX_HAS_WAITERS;

kernel/rtmutex.c +12 -65

-	 * and made us the pending owner:
 	 */
-	if (orig_waiter && !orig_waiter->task)
+	if (orig_waiter && !rt_mutex_owner(orig_lock))
 		goto out_unlock_pi;
 
 	/*

@@ -254,6 +241,17 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 
 	/* Release the task */
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	if (!rt_mutex_owner(lock)) {
+		/*
+		 * If the requeue above changed the top waiter, then we need
+		 * to wake the new top waiter up to try to get the lock.
+		 */
+
+		if (top_waiter != rt_mutex_top_waiter(lock))
+			wake_up_process(rt_mutex_top_waiter(lock)->task);
+		raw_spin_unlock(&lock->wait_lock);
+		goto out_put_task;
+	}
 	put_task_struct(task);
 
 	/* Grab the next task */

@@ -296,78 +294,16 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 }
 
 /*
- * Optimization: check if we can steal the lock from the
- * assigned pending owner [which might not have taken the
- * lock yet]:
- */
-static inline int try_to_steal_lock(struct rt_mutex *lock,
-				    struct task_struct *task)
-{
-	struct task_struct *pendowner = rt_mutex_owner(lock);
-	struct rt_mutex_waiter *next;
-	unsigned long flags;
-
-	if (!rt_mutex_owner_pending(lock))
-		return 0;
-
-	if (pendowner == task)
-		return 1;
-
-	raw_spin_lock_irqsave(&pendowner->pi_lock, flags);
-	if (task->prio >= pendowner->prio) {
-		raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-		return 0;
-	}
-
-	/*
-	 * Check if a waiter is enqueued on the pending owners
-	 * pi_waiters list. Remove it and readjust pending owners
-	 * priority.
-	 */
-	if (likely(!rt_mutex_has_waiters(lock))) {
-		raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-		return 1;
-	}
-
-	/* No chain handling, pending owner is not blocked on anything: */
-	next = rt_mutex_top_waiter(lock);
-	plist_del(&next->pi_list_entry, &pendowner->pi_waiters);
-	__rt_mutex_adjust_prio(pendowner);
-	raw_spin_unlock_irqrestore(&pendowner->pi_lock, flags);
-
-	/*
-	 * We are going to steal the lock and a waiter was
-	 * enqueued on the pending owners pi_waiters queue. So
-	 * we have to enqueue this waiter into
-	 * task->pi_waiters list. This covers the case,
-	 * where task is boosted because it holds another
-	 * lock and gets unboosted because the booster is
-	 * interrupted, so we would delay a waiter with higher
-	 * priority as task->normal_prio.
-	 *
-	 * Note: in the rare case of a SCHED_OTHER task changing
-	 * its priority and thus stealing the lock, next->task
-	 * might be task:
-	 */
-	if (likely(next->task != task)) {
-		raw_spin_lock_irqsave(&task->pi_lock, flags);
-		plist_add(&next->pi_list_entry, &task->pi_waiters);
-		__rt_mutex_adjust_prio(task);
-		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-	}
-	return 1;
-}
-
-/*

kernel/rtmutex.c +2 -1

  */
-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

kernel/rtmutex.c +15 -0

+	 * 1) there is no waiter
+	 * 2) higher priority than waiters
+	 * 3) it is top waiter
+	 */
+	if (rt_mutex_has_waiters(lock)) {
+		if (task->prio >= rt_mutex_top_waiter(lock)->list_entry.prio) {
+			if (!waiter || waiter != rt_mutex_top_waiter(lock))
+				return 0;
+		}
+	}
+
+	if (waiter || rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		struct rt_mutex_waiter *top;
+

kernel/rtmutex.c +9 -0

+		 */
+		if (rt_mutex_has_waiters(lock)) {
+			top = rt_mutex_top_waiter(lock);
+			top->pi_list_entry.prio = top->list_entry.prio;
+			plist_add(&top->pi_list_entry, &task->pi_waiters);
+		}
+		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	}
+
 	/* We got the lock. */
 	debug_rt_mutex_lock(lock);

On Wed, 2010-12-15 at 16:09 +0800, Lai Jiangshan wrote:

Some English updates.

Quoted 2 lines

Quoted 6 lines

+ * owner bit0
+ * NULL 0 lock is free (fast acquire possible)
+ * NULL 1 lock is free and has waiters and the top waiter
+ * is going to take the lock*
+ * taskpointer 0 lock is held (fast release possible)
+ * taskpointer 1 lock is held and has waiters

* taskpointer 1 lock is held and has waiters*

Quoted 4 lines

*
* The fast atomic compare exchange based acquire and release is only
- * possible when bit 0 and 1 of lock->owner are 0.
+ * possible when bit 0 of lock->owner are 0.

	s/are/is/

Quoted 10 lines

*
- * (*) There's a small time where the owner can be NULL and the
- * "lock has waiters" bit is set. This can happen when grabbing the lock.
- * To prevent a cmpxchg of the owner releasing the lock, we need to set this
- * bit before looking at the lock, hence the reason this is a transitional
- * state.
+ * (*) It also can be a transitional state when grabbing the lock
+ * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
+ * we need to set the bit0 before looking at the lock, and the owner may be
+ * NULL in this small time, hence this can be a transitional state.

* (*) There is a small time when bit 0 is set but there are no
* waiters. This can happen when grabbing the lock in the slow path.
* To prevent a cmpxchg of the owner releasing the lock, we need to
* set this bit before looking at the lock.

Quoted 7 lines

It has called try_to_take_rt_mutex() in __rt_mutex_slowlock(), when timeout or got signal, it returns from __rt_mutex_slowlock() with lock->wait_lock still held, and then calls remove_waiter(),

so we don't need to call try_to_take_rt_mutex() in remove_waiter(). It is strange that remove_waiter() do some "require lock" work.

I think you are correct here. It should never get to this path where !owner && first is true. If we timed out then we either got the lock or we could not. If we could not than owner had to be set or we are not the top waiter. Thus we need:

	if (!owner) {
		BUG_ON(first);
		return;
	}

Quoted 3 lines · Steven Rostedt

On Wed, 2010-12-15 at 16:09 +0800, Lai Jiangshan wrote:

Some English updates.

Updated, Thank you very much.

/*

kernel/rtmutex.c +0 -0

@@ -543,11 +491,13 @@ static void remove_waiter(struct rt_mutex *lock,
 
 	raw_spin_lock_irqsave(&current->pi_lock, flags);

Quoted 4 lines · Lai Jiangshan

/*

kernel/rtmutex.c +0 -0

@@ -543,11 +491,13 @@ static void remove_waiter(struct rt_mutex *lock,
 
 	raw_spin_lock_irqsave(&current->pi_lock, flags);

kernel/rtmutex.c static void remove_waiter(struct rt_mutex *lock, · line 500

Quoted 10 lines

kernel/rtmutex.c +4 -2

 	plist_del(&waiter->list_entry, &lock->wait_list);
-	waiter->task = NULL;
 	current->pi_blocked_on = NULL;
 	raw_spin_unlock_irqrestore(&current->pi_lock, flags);
 
-	if (first && owner != current) {
+	if (!owner)
+		return;
+
+	if (first) {

This is a bug. There's a small chance that the mutex timed out, and at that same time, the owner gave up the lock and woke this task up. Which means this task is the new owner of the lock iff it was the rt_mutex_top_waiter().

The fix is to do this:

	if (!owner) {
		if (first) {
			ret = try_to_take_rt_mutex();
			BUG_ON(!ret);
		}
		return first;
	}

	if (first) {

We need to make remove_waiter return 1 if it took the lock and 0 if it did not, so it can pass this information back to the caller.

	if (unlikely(ret)) {
		if (remove_waiter(...))
			ret = 0;
	}

It has called try_to_take_rt_mutex() in __rt_mutex_slowlock(), when timeout or got signal, it returns from __rt_mutex_slowlock() with lock->wait_lock still held, and then calls remove_waiter(),

so we don't need to call try_to_take_rt_mutex() in remove_waiter(). It is strange that remove_waiter() do some "require lock" work.

It has called try_to_take_rt_mutex() in __rt_mutex_slowlock(), when timeout or got signal, it returns from __rt_mutex_slowlock() with lock->wait_lock still held, and then calls remove_waiter(),

so we don't need to call try_to_take_rt_mutex() in remove_waiter(). It is strange that remove_waiter() do some "require lock" work.

 kernel/futex.c          |   26 +---
 kernel/rtmutex.c        |  306 ++++++++++++++++--------------------------------
 kernel/rtmutex_common.h |   16 --
 3 files changed, 116 insertions(+), 232 deletions(-)

kernel/futex.c +1 -0

index 6c683b3..5f4ea5f 100644
@@ -775,18 +775,10 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
 		return -EINVAL;
 
 	raw_spin_lock(&pi_state->pi_mutex.wait_lock);
+	/* set new owner to the most possible owner(top waiter). */

Quoted 14 lines · Lai Jiangshan

 kernel/futex.c          |   26 +---
 kernel/rtmutex.c        |  306 ++++++++++++++++--------------------------------
 kernel/rtmutex_common.h |   16 --
 3 files changed, 116 insertions(+), 232 deletions(-)

kernel/futex.c +1 -0

index 6c683b3..5f4ea5f 100644
@@ -775,18 +775,10 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
 		return -EINVAL;
 
 	raw_spin_lock(&pi_state->pi_mutex.wait_lock);
+	/* set new owner to the most possible owner(top waiter). */

kernel/futex.c static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this) · line 787

Quoted 10 lines

kernel/futex.c +0 -7

 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 
 	/*
-	 * This happens when we have stolen the lock and the original
-	 * pending owner did not enqueue itself back on the rt_mutex.
-	 * Thats not a tragedy. We know that way, that a lock waiter
-	 * is on the fly. We make the futex_q waiter the pending owner.
-	 */
-	if (!new_owner)
-		new_owner = this->task;

Lai,

Why did you remove this? I just triggered a bug that was caused by rt_mutex_next_owner() returning NULL.

Hmm, reading the comment it looks like it would only return NULL if the next owner woke up and removed itself (which it does not do anymore). But, this code is called unconditionally. I'm thinking we can trigger this if a timeout occurred too.

I guess the real change should just be to the comment.

I can add trace debug to see if that was indeed the case.

After this patch applied, the topwaiter will not be deququed when the lock is released(any waiter is dequeued only when it really get the lock or give up). So the wait list will not be empty if someone is still waiting on.

I thought, in this code, this->task is waiting, so rt_mutex_next_owner() will not return NULL. As you found, my thought is wrong, we should just change the comment.

In current rtmutex, the pending owner may be boosted by the tasks in the rtmutex's waitlist when the pending owner is deboosted or a task in the waitlist is boosted. This boosting is unrelated, because the pending owner does not really take the rtmutex. It is not reasonable.

Quoted 5 lines · Lai Jiangshan

In current rtmutex, the pending owner may be boosted by the tasks in the rtmutex's waitlist when the pending owner is deboosted or a task in the waitlist is boosted. This boosting is unrelated, because the pending owner does not really take the rtmutex. It is not reasonable.

Hi Lai,

Your patch looks like it is proving itself in -rt (after I fixed a bunch of -rt stuff to get your stuff working ;).

Could you repost your patch with the following removed:

Quoted 9 lines · Steven Rostedt

Quoted 5 lines · Lai Jiangshan

In current rtmutex, the pending owner may be boosted by the tasks in the rtmutex's waitlist when the pending owner is deboosted or a task in the waitlist is boosted. This boosting is unrelated, because the pending owner does not really take the rtmutex. It is not reasonable.

Hi Lai,

Quoted 4 lines

Your patch looks like it is proving itself in -rt (after I fixed a bunch of -rt stuff to get your stuff working ;).

Could you repost your patch with the following removed:

Oh, and you can add:

Acked-by Steven Rostedt <[email protected]>

Quoted 15 lines · Steven Rostedt

Quoted 13 lines · Steven Rostedt

Quoted 5 lines · Lai Jiangshan

In current rtmutex, the pending owner may be boosted by the tasks in the rtmutex's waitlist when the pending owner is deboosted or a task in the waitlist is boosted. This boosting is unrelated, because the pending owner does not really take the rtmutex. It is not reasonable.

Hi Lai,

Your patch looks like it is proving itself in -rt (after I fixed a bunch of -rt stuff to get your stuff working ;).

Could you repost your patch with the following removed:

Quoted 4 lines

Oh, and you can add:

Acked-by Steven Rostedt <[email protected]>

Actually this would be more appropriate:

Reviewed-by Steven Rostedt <[email protected]>

On 01/13/2011 01:05 AM, Steven Rostedt wrote:

Quoted 1 line · Lai Jiangshan

On 01/13/2011 01:05 AM, Steven Rostedt wrote:

Does not apply to mainline. Can you please redo ?

Thanks,

tglx

Quoted 8 lines · Thomas Gleixner

kernel/rtmutex.c static int rt_mutex_adjust_prio_chain(struct task_struct *task, · line 253

Quoted 2 lines

kernel/rtmutex.c +2 -0

+		 */
+		if (top_waiter != rt_mutex_top_waiter(lock)) {

Shouldn't this:

- clear cand_owner on the previous top_waiter ?
- increment the cand_seq ?

Quoted 4 lines

If we increment cand_seq, then we can get rid of cand_owner completely as waiter->cand_seq == lock->cand_seq should be sufficient. And it would automatically prefer the new top waiter and not give the lock to some random on the fly task.

If we increment cand_seq, we do deprive candidate ownership from the original one and we have only one candidate owner.

If we have just one candidate owner at most, we don't need cand_seq either. we can save it in lock->owner, (like pending owner).

But this may lead to livelock if we do deprive candidate ownership as I mentioned (the mail I reply to Steven)

Any random on the fly task is a reasonable task for the owner in this patch.

A(assigned the first candidate ownership), B, C, D, E... are in the waitlist. But before new owner really take the lock, B, D 's priority are raised and they became the top waiter at least once, (D is the top at the end, D, B, A, C, E....) B and D are also candidate owners. In my patch, A, B, D have the chance to compete the lock, they are all reasonable because they are candidate owners, including A!

OK, let's consider the same case but without this patch.
A is assigned the pending ownership. B, C, D, E... are in the waitlist, But before new owner really take the lock, B, D 's priority are raised. In the end, only A can complete the lock, B and D just do boost A and help A. only A!

Summary, the reason I will give the lock to some random on the fly task which is one of the candidate owners:
1) avoid livelock

2) no worse than the code without this patch.

Quoted 14 lines

Quoted 14 lines

kernel/rtmutex.c +3 -2

-static int try_to_take_rt_mutex(struct rt_mutex *lock)
+static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
+		struct rt_mutex_waiter *waiter)
 {
 	/*
 	 * We have to be careful here if the atomic speedups are

@@ -390,15 +335,73 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock)
 	 */
 	mark_rt_mutex_waiters(lock);
 
-	if (rt_mutex_owner(lock) && !try_to_steal_lock(lock, current))
+	if (rt_mutex_owner(lock))
 		return 0;
 

Quoted 10 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 346

Quoted 6 lines

kernel/rtmutex.c +6 -0

+	/*
+	 * It is a queued waiter.
+	 *
+	 * Is it a candidate owner? If it is, it will win unconditionally.
+	 * And it defeats the other candidate owner(s) (if any) and
+	 * steal lock from them.

Why ? If the boost code changes the top waiter and wakes up the new candidate, then this new one really should get the lock and the old on the fly candidate should queue itself back.

See above, all candidate owner have the chance to compete the lock. It is required for avoiding the livelock.

If we have other way to avoiding the livelock, we will use only one candidate owner, you, Steven and I will very happy.

Quoted 10 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 366

Quoted 6 lines

kernel/rtmutex.c +6 -0

+	/*
+	 * Does it defeat the candidate owner(s) and steal lock from them?
+	 *
+	 * Note: in the rare case of a task is boosted but its waiter has not
+	 * been requeued in the lock's wait list yet, thus it can also steal
+	 * the lock.

How should this happen with the new code ? The waiter remains in the wait list and boosting does not change that. So that comment is misleading.

When someone boosted current task p, but it fail to take the p->pi_block_on->lock->wait_lock, and current task p success take it and call try_to_take_rt_mutex()
before p->pi_block_on is requeued in the waitlist.
current task should also have chance to win the lock even it is
not candidate owner/top waiter. It will win when it has the higher
priority than the top waiter.

Quoted 5 lines

Quoted 5 lines

kernel/rtmutex.c +5 -0

+		/*
+		 * We have to enqueue the top waiter(if have) into
+		 * task->pi_waiters list and would get boost from it.
+		 */
+		if (rt_mutex_has_waiters(lock)) {

Quoted 8 lines

kernel/rtmutex.c static int try_to_take_rt_mutex(struct rt_mutex *lock) · line 394

Quoted 4 lines

kernel/rtmutex.c +4 -0

+			top = rt_mutex_top_waiter(lock);
+			top->pi_list_entry.prio = top->list_entry.prio;
+			plist_add(&top->pi_list_entry, &task->pi_waiters);
+			__rt_mutex_adjust_prio(task);

Why should we boost ? Because we can have several candidates on the fly and we don't care which one is the highest prio candidate? That looks wrong.

A really owner should (be boosted)/(prepare to be booted) by the waiters. such code is also needed in original code.

Quoted 3 lines · Lai Jiangshan

Not advantage nor disadvantage
1) Even we support multiple candidate owners, we hardly cause "thundering herd" the number of candidate owners is likely 1.

I'm not convinced about that function, see comments below

Quoted 5 lines

2) two APIs are changed.
rt_mutex_owner() will not return pending owner rt_mutex_next_owner() always return the top owner, it is a candidate owner.
will not return NULL if we only have a pending owner.
I have fixed the code that use these APIs.

I think we want a separate function which can be used by futex code, but that's a detail.

kernel/futex.c +3 -0

+		 * rt_mutex. Too late.
 		 */
+		raw_spin_lock(&q->pi_state->pi_mutex.wait_lock);
 		owner = rt_mutex_owner(&q->pi_state->pi_mutex);
+		if (!owner)

Quoted 7 lines · Thomas Gleixner

Quoted 3 lines · Lai Jiangshan

Not advantage nor disadvantage
1) Even we support multiple candidate owners, we hardly cause "thundering herd" the number of candidate owners is likely 1.

I'm not convinced about that function, see comments below

Quoted 8 lines

Quoted 5 lines

2) two APIs are changed.
rt_mutex_owner() will not return pending owner rt_mutex_next_owner() always return the top owner, it is a candidate owner.
will not return NULL if we only have a pending owner.
I have fixed the code that use these APIs.

I think we want a separate function which can be used by futex code, but that's a detail.

We do use both functions in the futex code.

Quoted 3 lines

kernel/futex.c +0 -0

@@ -778,15 +778,6 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 

kernel/futex.c static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this) · line 788

Quoted 9 lines

kernel/futex.c +0 -8

 	/*
-	 * This happens when we have stolen the lock and the original
-	 * pending owner did not enqueue itself back on the rt_mutex.
-	 * Thats not a tragedy. We know that way, that a lock waiter
-	 * is on the fly. We make the futex_q waiter the pending owner.
-	 */
-	if (!new_owner)
-		new_owner = this->task;
-

If I'm reading Lai's statement above correctly, the change actually just eliminates the need for the !new_owner check, as in that case it will return current. Is this correct? And indeed, Lai's patch removes it. This looks correct to me.

kernel/futex.c static int fixup_owner(u32 __user *uaddr, int fshared, struct futex_q *q, · line 1652

Quoted 8 lines

kernel/futex.c +0 -3

@@ -1647,18 +1638,20 @@ static int fixup_owner(u32 __user *uaddr, int fshared, struct futex_q *q,
 		/*
 		 * pi_state is incorrect, some other task did a lock steal and
 		 * we returned due to timeout or signal without taking the
-		 * rt_mutex. Too late. We can access the rt_mutex_owner without
-		 * locking, as the other task is now blocked on the hash bucket
-		 * lock. Fix the state up.

How does this patch change this behavior? Removing the comment and adding the lock says that "the other task is now able to contend for the pi_mutex".

Quoted 13 lines

kernel/futex.c +5 -0

+		 * rt_mutex. Too late.
 		 */
+		raw_spin_lock(&q->pi_state->pi_mutex.wait_lock);
 		owner = rt_mutex_owner(&q->pi_state->pi_mutex);
+		if (!owner)
+			owner = rt_mutex_next_owner(&q->pi_state->pi_mutex);
+		raw_spin_unlock(&q->pi_state->pi_mutex.wait_lock);
 		ret = fixup_pi_state_owner(uaddr, q, owner, fshared);
 		goto out;
 	}
 

kernel/futex.c static int fixup_owner(u32 __user *uaddr, int fshared, struct futex_q *q, · line 1654

Quoted 4 lines

kernel/futex.c +1 -1

 	/*
 	 * Paranoia check. If we did not take the lock, then we should not be
-	 * the owner, nor the pending owner, of the rt_mutex.
+	 * the owner of the rt_mutex.

Is this changed because we could now be a "candidate owner" ?

kernel/futex.c static int fixup_owner(u32 __user *uaddr, int fshared, struct futex_q *q, · line 1657

Quoted 5 lines

kernel/futex.c +0 -0

 	 */
 	if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
 		printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "

The other uses of rt_mutex_owner in futex.c don't appear to be impacted by the change in API described above as they just compare the result to current (futex_lock_pi and futex_wait_requeue_pi).

kernel/rtmutex.c +8 -0

+			if (!top_waiter->cand_owner) {
+				top_waiter->cand_owner = 1;
+				wake_up_process(top_waiter->task);
+			}
+		}
+		raw_spin_unlock(&lock->wait_lock);
+		goto out_put_task;
+	}
 	put_task_struct(task);
 
 	/* Grab the next task */

@@ -296,78 +303,16 @@ static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 }