Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1220997 > unrolled thread

Re: [RFC][PATCH RT 0/3] RT: Fix trylock deadlock without msleep() hack

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC][PATCH RT 0/3] RT: Fix trylock deadlock without msleep()  hack Steven Rostedt <rostedt@goodmis.org> - 2015-09-08 19:00 +0200
    Re: [RFC][PATCH RT 0/3] RT: Fix trylock deadlock without msleep()  hack Steven Rostedt <rostedt@goodmis.org> - 2015-09-08 21:40 +0200

#1220997 — Re: [RFC][PATCH RT 0/3] RT: Fix trylock deadlock without msleep() hack

On Mon, 7 Sep 2015 10:35:25 +0200 (CEST)
Thomas Gleixner <tglx@linutronix.de> wrote:

> > i.e. I'm not sure the problem is properly specified.
> 
> Right. I omitted some essential information.
> 
>        lock(y->lock);
>        x = y->x;
>        if (!try_lock(x->lock))
> 		....
> 
> Once we drop x->lock, y->x can change. That's why the retry is there.

You mean once we drop y->lock, y->x can change.


> 
> Now on RT the trylock loop can obviously lead to a live lock if the
> try locker preempted the holder of x->lock.
> 
> What Steve is trying to do is to boost the holder of x->lock (task A)
> without actually queueing the task (task B) on the lock wait queue of
> x->lock. To get out of the try-lock loop he calls sched_yield() from
> task B.
> 
> While this works by some definition of works, I really do not like the
> semantical obscurity of this approach.
> 
> 1) The boosting is not related to anything.
> 
>    If the priority of taskB changes then nothing changes the boosting
>    of taskA.
> 
> 2) The boosting stops
> 
> 3) sched_yield() makes me shudder
> 
>    CPU0			CPU1	
> 
>    taskA
>      lock(x->lock)
> 
>    preemption
>    taskC
> 			taskB
> 			  lock(y->lock);
> 			  x = y->x;
> 			  if (!try_lock(x->lock)) {
> 			    unlock(y->lock);
> 			    boost(taskA);
> 			    sched_yield();  <- returns immediately
> 			    
>    So, if taskC has higher priority than taskB and therefor than
>    taskA, taskB will do the lock/trylock/unlock/boost dance in
>    circles.

Yeah, I was aware of this scenario, in which case, it just shows the
nastiness of a spinning trylock. Even with the current situation, the
task is going to constantly be spinning until TaskA can run. The
difference, is that it will let other tasks run during that 1 ms sleep.
The current code works, but as you said, by some definition of works ;-)


> 
>    We can make that worse. If taskB's code looks like this:
> 
> 			  lock(y->lock);
> 			  x = y->x;
> 			  if (!try_lock(x->lock)) {
> 			    unlock(y->lock);
> 			    boost(taskA);
> 			    sched_yield();
> 			    return -EAGAIN;
> 
>   and at the callsite it decides to do something completely different
>   than retrying then taskA stays boosted.

But only till it releases the lock (or any lock). That is, it's a
bounded boost, and not a leak. A leak would have no end.

> 
> So we have already two scenarios where this clearly violates the PI
> rules and I really do not have any interest to debug leaked RT
> priorites.

It's not a leak, it's only bounded by the time it holds that lock. As
the only locks that have this characteristic are spinlock converted to
rtmutex, those should be short.

> 
> I agree with Steve, that the main case where we have this horrible
> msleep() right now - dcache - is complex, but we rather sit down and
> analyze it proper and come up with semantically well defined
> solutions.

I'm happy to have this discussion! That's what RFC patches are for ;-)

I would also be happy if we can come up with a better solution than this
proposal.

-- Steve
--
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/

[toc] | [next] | [standalone]

#1221054

On Tue, 8 Sep 2015 12:59:34 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Mon, 7 Sep 2015 10:35:25 +0200 (CEST)
> Thomas Gleixner <tglx@linutronix.de> wrote:
> > 			    
> >    So, if taskC has higher priority than taskB and therefor than
> >    taskA, taskB will do the lock/trylock/unlock/boost dance in
> >    circles.
> 
> Yeah, I was aware of this scenario, in which case, it just shows the
> nastiness of a spinning trylock. Even with the current situation, the
> task is going to constantly be spinning until TaskA can run. The
> difference, is that it will let other tasks run during that 1 ms sleep.
> The current code works, but as you said, by some definition of works ;-)
>

I thought about this a little more, but did not do any coding yet. Just
wanted to bounce off some ideas.

First, I still want to keep the spin_try_or_boost_lock() logic, maybe
call it, spin_trylock_or_boost() as we are not really boosting the
lock, but the owner.

Still have the requirement that if you don't get the lock, you must
still call cpu_chill().

But to get rid of the three issues you have with my current patch, I
have some ideas.

First let me express the three issues you have to make sure that we are
in-sync.

 Issue #1) The task owning the requested lock is on another CPU and is
  blocked by an even higher task. Thus the trylock spinner hogs its CPU
  preventing further progress of other tasks that want to run on that
  CPU.

 Issue #2) There could be a temporary leak of priority if the caller of
  the trylock_or_boost returns after the cpu_chill() with -EAGAIN and
  does something different.

 Issue #3) The boosting is not related to anything. If the trylock
  spinner gets boosted (or deboosted), there's no trail back to the
  owner of the lock.


To solve the above, we need to keep some state between the failed call
to spin_trylock_or_boost() and cpu_chill() (which is why there would be
a requirement to call cpu_chill() on a failed attempt to acquire the
lock).

We could add a static waiter to the task_struct, such that a failed
spin_trylock_or_boost() would add that waiter to the pi_list of the
owner, and of the waiters of the lock. This waiter will need to have a
flag stating that it's not a blocked task, and that a loop around the
pi locking will not detect it as a deadlock.

Now, if the trylock spinner either blocks on another lock, or fails to
get another trylock_or_boost(), it would unhook this waiter, and do
all the work that is required to unhook it (deboost owners, etc). That
is, a task can only be using one waiter at a time (to prevent any other
strange behaviors). It can only boost one task at a time, it can't be
boosting more than one. The last call to a spin_lock or
spin_trylock_or_boost() always wins (gets to use the waiter).

When the owner of the lock releases the lock, if this waiter is the top
waiter, it will have to grab the task's pi_lock, set the lock pointer to
NULL, and wake it up.

Then, when the trylock spinner gets around to the cpu_chill(), That
code will check if the static waiter of the task_struct is in use. It
will grab its own pi_lock, check if the waiter lock is NULL, if not, it
will go to sleep.


This solves:

 Issue #1) if the lock is still in use, the cpu_chill() will sleep, not
  yield.

 Issue #2) The trylock spinner does not go past the cpu_chill() while
  the last spin_trylock_or_boost() owner has not released the lock. The
  owner will not have leaked that priority.

 Issue #3) Use of a static waiter allows changing of boosting to occur.
  The priority chain will need to be modified to take this into account.


This would be more complex than what I proposed, but it would also
solve the issues that you brought up. The fact that a task can only
block with one waiter (it gives up the last trylock_or_boost if it
needs to block on something else that needs a waiter, or tries another
trylock_or_boost and fails to get the lock) will keep the complexity
down. It would prevent a task being in a chain twice.

Thoughts?

-- Steve
--
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/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web