Re: PI patch against 2.6.16-rt9

[Esben Nielsen <simlo@phys.au.dk>]

On Wed, 29 Mar 2006, Thomas Gleixner wrote:

> On Tue, 2006-03-28 at 23:23 +0100, Esben Nielsen wrote:
> > > If you get to L(x) the underlying dependencies might have changed
> > > already as well as the dependencies x ... n. We might get false
> > > positives in the deadlock detection that way, as a deadlock is an
> > > "atomic" state.
> >
> > As I see it you might detect a circular lock graph "atomically". But is
> > that a "deadlock"? Yes, if you rule out signals and timeouts, this
> > situation does indeed deadlock your program.
> >
> > But if you count in signals and timeouts your algoritm also gives "false
> > positives": You can detect a circular lock but when you return from
> > rt_mutex_slowlock(), a signal is delivered and there is no longer a
> > circular dependency and most important: The program wouldn't be
> > deadlocked even if you didn't ask for deadlock detection and your task in
> > that case would block.
> >
> > I would like to see an examble of a false deadlock. I don't rule them out
> > in the present code. But they might be simple to fix.
>
> Simply the initial lock chain is L1->L2->L3->L4, which is no deadlock.
> Now in the course of your lock dropping L2 gets removed while you are at
> L3 and L5 gets added on top of L4. You follow the chain blindly and
> detect a dealock vs. L5, but its not longer valid. The L2 cleanup is
> blocked by yourself. There is no way to prevent this with your method.
>

Hmm, let me try to write it out

       A                B             C           D
    lock L1           lock L2       lock L3       lock L4
    lock L2           lock L3       lock L4
 traverse to C
 is preempted
                                                  unlock L4
                                    unlock L4
                                    unlock L3
                      unlock L3                   lock L4
                      unlock L2     lock L3
                      lock L3       lock L4

 Continue from C

Ok, I see the problem for _deadlock detection_.  There still is no problem
for PI.



> Your method is tempting, but I do not see how it works out right now.
>

It works for PI. It might give false positives for deadlock detection even
without signals involved. But that might be solved by simply checking
again. If it is stored on a task when they blocked on a lock it
could be seen if they had released and reobtained the task since the last
traversal.

If I should choose between a 100% certain deadlock detection and
rescheduling while doing PI I would choose that latter as that gives a
deterministic RT system. Are there at all applications depending on
deadlock detection or is it only for debug perposes anyway?

Esben

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


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