Re: [PATCH] rtmutex: multiple candidate owners without unrelated boosting

[Thomas Gleixner <tglx@linutronix.de>]

On Wed, 15 Dec 2010, Lai Jiangshan wrote:
> On 12/15/2010 04:07 AM, Thomas Gleixner wrote:
> >> +		 */
> >> +		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.
> 
> 
> If we increment cand_seq, we do deprive candidate ownership from the
> original one and we have only one candidate owner.

Which is good.
 
> 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).

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

I think that's a non realistic scenario. If you have something which
is changing the priority of multiple waiters with high frequency, then
the rtmutex code is the least of your worries.

> 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!

You mean with the current code. Right, that's not pretty but not
really an issue either. I inustrumented that on RT and the situation
happens twice out of 12 Mio.

I'm way more interested in simplifying the code than in handling this
corner case.
 
> 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

There is none.

> 2) no worse than the code without this patch.

That's not an argument at all.
 
> >> -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.
> > 
> > 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.

Have you ever been able to observe that live lock ? If yes, what did
it take to produce it ?
 
> >> +	/*
> >> +	 * 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.
 
Err? If it's not getting the lock then P is hardly the top waiter
simply because the requeue in lock->wait_list did not happen
yet. That's fully serialized.
 
> >> +		/*
> >> +		 * 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);
> > 
> > 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.

No, that's only necessary because you allow multiple possible owners
and you can end up with a lock owner which has less priority than the
highest priority waiter. If you restrict that to the highest prio
waiter then no boosting is necessary at all.

Thanks,

	tglx