lkml.org 
[lkml]   [2007]   [Oct]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [RFC, PATCH] locks: remove posix deadlock detection
    From
    On Sun, Oct 28, 2007 at 04:41:57PM -0600, Matthew Wilcox wrote:
    > On Sun, Oct 28, 2007 at 05:50:30PM -0400, Trond Myklebust wrote:
    > > > You can't fix the false EDEADLK detection without solving the halting
    > > > problem. Best of luck with that.
    > >
    > > I can see that it would be difficult to do efficiently, but basically,
    > > this boils down to finding a circular path in a graph. That is hardly an
    > > unsolvable issue...
    >
    > Bzzt. You get a false deadlock with multiple threads like so:
    >
    > Thread A of task B takes lock 1
    > Thread C of task D takes lock 2
    > Thread C of task D blocks on lock 1
    > Thread E of task B blocks on lock 2

    Oh neat, I missed that case, thanks for pointing it out.

    > We currently declare deadlock at this point (unless the deadlock detection
    > code has changed since I last looked at it), despite thread A being about
    > to release lock 1. Oh, and by the way, thread E is capable of releasing
    > lock 1, so you can't just say "well, detect by thread instead of by task".
    >
    > So the only way I can see to accurately detect deadlock is to simulate
    > the future execution of all threads in task B to see if any of them
    > will release lock 1 without first gaining lock 2.

    Hm. It's annoying, but I'm not convinced it's *that* annoying. We're
    not trying to predict whether a deadlock could arise as the result of
    future behavior. We're just trying to determine whether granting the
    current lock request results in an immediate deadlock consisting purely
    of posix file locks.

    But yes, I'm assume it's possible, for example, that a thread-exit could
    race with a lock request, with the result that we see no deadlock at the
    time we handle the lock request, even though at that point the last task
    with the ability to solve the problem is already exiting.

    Supposing that we're willing to permit the request in such cases and
    return EDEADLK only in cases where we're positive there's a deadlock, is
    there still some useful subset of cases where we could return EDEADLK?
    For example, could we take note of tasks that, when they block on a
    lock, have a current->files with reference count one, and only follow
    cycles consisting of such blocks?

    I'm still not convinced it's worth the trouble, but I suspect you're
    overstating the difficulty.

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

    \
     
     \ /
      Last update: 2007-10-29 03:13    [W:2.234 / U:0.032 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site