Re: PI patch against 2.6.16-rt9

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.

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

tglx



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: 2.6.16-rc6-rt1
    ... Try to compile the kernel ... If you have debug deadlock detection enabled it triggers a bug and shows ... You mean that you have to run deadlock detection for all futexes to avoid ... by following the lock chain. ...
    (Linux-Kernel)
  • Re: 2.6.16-rc6-rt1
    ... Try to compile the kernel ... You mean that you have to run deadlock detection for all futexes to avoid ... by following the lock chain. ...
    (Linux-Kernel)
  • Re: Bug in pthread on Debian?
    ... Sounds like you haven't been programming threads long enough to have ... signals and threads don't mix too well. ... their machines if they get deadlock problems. ... Threads can introduce countless bugs into code and applications, ...
    (comp.unix.programmer)
  • Re: robust futex deadlock detection patch
    ... > malicious apps from deadlocking the kernel through the robust futex ... > Deadlock detection is done 'up front' for both POSIX and robust ... > POSIX mutexes will hang if deadlocked, as defined by the POSIX spec. ...
    (Linux-Kernel)
  • Re: Recursion bug in -rt
    ... >>> on the waitqueue so as not to hang the kernel. ... >>> application that it is trying to deadlock itself. ... where you deadlock detection has to be performed ...
    (Linux-Kernel)