OFD locks and deadlock detection

OFD locks and deadlock detection

[Michael Kerrisk (man-pages)]

Hi Jeff,

I just happened to notice :

    commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
    Author: Jeff Layton <jlayton@redhat.com>
    Date:   Mon Feb 3 12:13:09 2014 -0500

        locks: skip deadlock detection on FL_FILE_PVT locks

And then this thread:

    http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
    From: Jeff Layton <jlayton <at> redhat.com>
    Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
    Date: 2014-01-09 14:19:46 GMT

I think it's pretty important to document that. All implementations
of traditional process-associated (.k.a. "POSIX") locks that I've ever 
come across do detect deadlocks, so it's important to note that OFD locks 
do not.

I plan to add the following text to the fcntl(2) page:

[[
In the current implementation,
no deadlock detection is performed for open file description locks.
(This contrasts with process-associated record locks,
for which the kernel does perform deadlock detection.)
]]

Okay?

cheers,

Michael


-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Re: OFD locks and deadlock detection

[Jeff Layton]

On Mon, 19 May 2014 15:18:13 +0200
"Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:

> Hi Jeff,
> 
> I just happened to notice :
> 
>     commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
>     Author: Jeff Layton <jlayton@redhat.com>
>     Date:   Mon Feb 3 12:13:09 2014 -0500
> 
>         locks: skip deadlock detection on FL_FILE_PVT locks
> 
> And then this thread:
> 
>     http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
>     From: Jeff Layton <jlayton <at> redhat.com>
>     Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
>     Date: 2014-01-09 14:19:46 GMT
> 
> I think it's pretty important to document that. All implementations
> of traditional process-associated (.k.a. "POSIX") locks that I've ever 
> come across do detect deadlocks, so it's important to note that OFD locks 
> do not.
> 
> I plan to add the following text to the fcntl(2) page:
> 
> [[
> In the current implementation,
> no deadlock detection is performed for open file description locks.
> (This contrasts with process-associated record locks,
> for which the kernel does perform deadlock detection.)
> ]]
> 
> Okay?
> 
> cheers,
> 
> Michael
> 
> 

(note: I'm no longer with Red Hat, so jlayton@redhat.com no longer works)

Sounds fine to me.

FWIW, the deadlock detection for process-associated record locks is
pretty worthless except in certain narrow circumstances.

At some point, we probably should have a discussion as to whether
deadlock detection is really something we want to keep. The current
implementation requires a global spinlock which has obvious
consequences for scalability.

Thanks,
-- 
Jeff Layton <jlayton@poochiereds.net>

Re: OFD locks and deadlock detection

[Michael Kerrisk (man-pages)]

On 05/19/2014 04:28 PM, Jeff Layton wrote:
> On Mon, 19 May 2014 15:18:13 +0200
> "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
> 
>> Hi Jeff,
>>
>> I just happened to notice :
>>
>>     commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
>>     Author: Jeff Layton <jlayton@redhat.com>
>>     Date:   Mon Feb 3 12:13:09 2014 -0500
>>
>>         locks: skip deadlock detection on FL_FILE_PVT locks
>>
>> And then this thread:
>>
>>     http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
>>     From: Jeff Layton <jlayton <at> redhat.com>
>>     Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
>>     Date: 2014-01-09 14:19:46 GMT
>>
>> I think it's pretty important to document that. All implementations
>> of traditional process-associated (.k.a. "POSIX") locks that I've ever 
>> come across do detect deadlocks, so it's important to note that OFD locks 
>> do not.
>>
>> I plan to add the following text to the fcntl(2) page:
>>
>> [[
>> In the current implementation,
>> no deadlock detection is performed for open file description locks.
>> (This contrasts with process-associated record locks,
>> for which the kernel does perform deadlock detection.)
>> ]]
>>
>> Okay?
>>
>> cheers,
>>
>> Michael
>>
>>
> 
> (note: I'm no longer with Red Hat, so jlayton@redhat.com no longer works)

Ahh -- okay. Caches cleared.

> Sounds fine to me.

Okay.

> FWIW, the deadlock detection for process-associated record locks is
> pretty worthless except in certain narrow circumstances.

Can you say some more about that, please? Maybe there's something 
worth putting into the man page. (Are there cases where deadlocks
are not detected?)

> At some point, we probably should have a discussion as to whether
> deadlock detection is really something we want to keep. The current
> implementation requires a global spinlock which has obvious
> consequences for scalability.

Could be tricky. I wonder if there's code out there that depends
on deadlock detection.

Cheers,

Michael

-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Re: OFD locks and deadlock detection

[Jeff Layton]

On Mon, 19 May 2014 20:36:45 +0200
"Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:

> On 05/19/2014 04:28 PM, Jeff Layton wrote:
> > On Mon, 19 May 2014 15:18:13 +0200
> > "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
> > 
> >> Hi Jeff,
> >>
> >> I just happened to notice :
> >>
> >>     commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
> >>     Author: Jeff Layton <jlayton@redhat.com>
> >>     Date:   Mon Feb 3 12:13:09 2014 -0500
> >>
> >>         locks: skip deadlock detection on FL_FILE_PVT locks
> >>
> >> And then this thread:
> >>
> >>     http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
> >>     From: Jeff Layton <jlayton <at> redhat.com>
> >>     Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
> >>     Date: 2014-01-09 14:19:46 GMT
> >>
> >> I think it's pretty important to document that. All implementations
> >> of traditional process-associated (.k.a. "POSIX") locks that I've ever 
> >> come across do detect deadlocks, so it's important to note that OFD locks 
> >> do not.
> >>
> >> I plan to add the following text to the fcntl(2) page:
> >>
> >> [[
> >> In the current implementation,
> >> no deadlock detection is performed for open file description locks.
> >> (This contrasts with process-associated record locks,
> >> for which the kernel does perform deadlock detection.)
> >> ]]
> >>
> >> Okay?
> >>
> >> cheers,
> >>
> >> Michael
> >>
> >>
> > 
> > (note: I'm no longer with Red Hat, so jlayton@redhat.com no longer works)
> 
> Ahh -- okay. Caches cleared.
> 
> > Sounds fine to me.
> 
> Okay.
> 
> > FWIW, the deadlock detection for process-associated record locks is
> > pretty worthless except in certain narrow circumstances.
> 
> Can you say some more about that, please? Maybe there's something 
> worth putting into the man page. (Are there cases where deadlocks
> are not detected?)
> 

Both false negatives and false positives are possible.

Basically what the deadlock detector does is to walk down a chain of
blocked locks and look to see if any of them are waiting on locks that
the process currently owns.

Unfortunately, ownership is defined by the value of current->files. So
if you call clone with CLONE_FILES, you can have two threads of
execution that share lock ownership. If one is holding a lock that the
other wants to wait on, you'll end up getting EDEADLK back even though
it wouldn't necessarily have been a deadlock.

Also, the existing code gives up after searching a chain of 10
dependencies, so it's possible to hit a deadlock anyway if you have a
chain of dependencies that's longer than that.

> > At some point, we probably should have a discussion as to whether
> > deadlock detection is really something we want to keep. The current
> > implementation requires a global spinlock which has obvious
> > consequences for scalability.
> 
> Could be tricky. I wonder if there's code out there that depends
> on deadlock detection.
> 

What I'd probably do first is add Kconfig option so we could compile it
out. Then we can lobby the distros to do so and see who complains.
Deadlock detection is optional in POSIX, so we aren't required to
support it.

-- 
Jeff Layton <jlayton@poochiereds.net>

Re: OFD locks and deadlock detection

[Michael Kerrisk (man-pages)]

On 05/20/2014 11:54 AM, Jeff Layton wrote:
> On Mon, 19 May 2014 20:36:45 +0200
> "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
> 
>> On 05/19/2014 04:28 PM, Jeff Layton wrote:
>>> On Mon, 19 May 2014 15:18:13 +0200
>>> "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
>>>
>>>> Hi Jeff,
>>>>
>>>> I just happened to notice :
>>>>
>>>>     commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
>>>>     Author: Jeff Layton <jlayton@redhat.com>
>>>>     Date:   Mon Feb 3 12:13:09 2014 -0500
>>>>
>>>>         locks: skip deadlock detection on FL_FILE_PVT locks
>>>>
>>>> And then this thread:
>>>>
>>>>     http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
>>>>     From: Jeff Layton <jlayton <at> redhat.com>
>>>>     Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
>>>>     Date: 2014-01-09 14:19:46 GMT
>>>>
>>>> I think it's pretty important to document that. All implementations
>>>> of traditional process-associated (.k.a. "POSIX") locks that I've ever 
>>>> come across do detect deadlocks, so it's important to note that OFD locks 
>>>> do not.
>>>>
>>>> I plan to add the following text to the fcntl(2) page:
>>>>
>>>> [[
>>>> In the current implementation,
>>>> no deadlock detection is performed for open file description locks.
>>>> (This contrasts with process-associated record locks,
>>>> for which the kernel does perform deadlock detection.)
>>>> ]]
>>>>
>>>> Okay?
>>>>
>>>> cheers,
>>>>
>>>> Michael
>>>>
>>>>
>>>
>>> (note: I'm no longer with Red Hat, so jlayton@redhat.com no longer works)
>>
>> Ahh -- okay. Caches cleared.
>>
>>> Sounds fine to me.
>>
>> Okay.
>>
>>> FWIW, the deadlock detection for process-associated record locks is
>>> pretty worthless except in certain narrow circumstances.
>>
>> Can you say some more about that, please? Maybe there's something 
>> worth putting into the man page. (Are there cases where deadlocks
>> are not detected?)
>>
> 
> Both false negatives and false positives are possible.
> 
> Basically what the deadlock detector does is to walk down a chain of
> blocked locks and look to see if any of them are waiting on locks that
> the process currently owns.
> 
> Unfortunately, ownership is defined by the value of current->files. So
> if you call clone with CLONE_FILES, you can have two threads of
> execution that share lock ownership. If one is holding a lock that the
> other wants to wait on, you'll end up getting EDEADLK back even though
> it wouldn't necessarily have been a deadlock.
> 
> Also, the existing code gives up after searching a chain of 10
> dependencies, so it's possible to hit a deadlock anyway if you have a
> chain of dependencies that's longer than that.

Thanks, Jeff, How does the following text for the man page look to you:

       When placing locks with F_SETLKW, the  kernel  detects  dead‐
       locks, whereby two or more processes have their lock requests
       mutually blocked by locks held by the other  processes.   For
       example,  suppose process A holds a write lock on byte 100 of
       a file, and process B holds a write lock  on  byte  200.   If
       each process then attempts to lock the byte already locked by
       the other process  using  F_SETLKW,  then,  without  deadlock
       detection,  both processes would remain blocked indefinitely.
       When the kernel detects such deadlocks, it causes one of  the
       blocking  lock  requests  to  immediately fail with the error
       EDEADLK; an application that encounters such an error  should
       release some of its locks to allow other applications to pro‐
       ceed before attempting regain the  locks  that  it  requires.
       Circular deadlocks involving more than two processes are also
       detected.  Note, however, that there are limitations  to  the
       kernel's deadlock-detection algorithm; see BUGS.

   BUGS
     Deadlock detection
       The  deadlock-detection algorithm employed by the kernel when
       dealing with F_SETLKW requests can yield both false negatives
       (failures  to  detect  deadlocks, leaving a set of deadlocked
       processes blocked indefinitely) and false positives  (EDEADLK
       errors  when  there is no deadlock).  For example, the kernel
       limits the lock depth of its dependency search to  10  steps,
       meaning  that  circular deadlock chains that exceed that size
       will not be detected.  In addition, the  kernel  may  falsely
       indicate  a deadlock when two or more processes created using
       the clone(2) CLONE_FILES flag place locks that appear (to the
       kernel) to conflict.

?

>>> At some point, we probably should have a discussion as to whether
>>> deadlock detection is really something we want to keep. The current
>>> implementation requires a global spinlock which has obvious
>>> consequences for scalability.
>>
>> Could be tricky. I wonder if there's code out there that depends
>> on deadlock detection.
>>
> 
> What I'd probably do first is add Kconfig option so we could compile it
> out. Then we can lobby the distros to do so and see who complains.
> Deadlock detection is optional in POSIX, so we aren't required to
> support it.

Sounds like a reasonable plan. Given the limitations, I suppose
it would be a brave / foolish application that tried to rely
on the kernel's deadlock-detection algorithm, so perhaps
there will be no complaints.

Cheers,

Michael

-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Re: OFD locks and deadlock detection

[Jeff Layton]

On Tue, 20 May 2014 22:22:17 +0200
"Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:

> On 05/20/2014 11:54 AM, Jeff Layton wrote:
> > On Mon, 19 May 2014 20:36:45 +0200
> > "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
> > 
> >> On 05/19/2014 04:28 PM, Jeff Layton wrote:
> >>> On Mon, 19 May 2014 15:18:13 +0200
> >>> "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> wrote:
> >>>
> >>>> Hi Jeff,
> >>>>
> >>>> I just happened to notice :
> >>>>
> >>>>     commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
> >>>>     Author: Jeff Layton <jlayton@redhat.com>
> >>>>     Date:   Mon Feb 3 12:13:09 2014 -0500
> >>>>
> >>>>         locks: skip deadlock detection on FL_FILE_PVT locks
> >>>>
> >>>> And then this thread:
> >>>>
> >>>>     http://thread.gmane.org/gmane.linux.file-systems/81318/focus=81327
> >>>>     From: Jeff Layton <jlayton <at> redhat.com>
> >>>>     Subject: [PATCH v5 13/14] locks: skip deadlock detection on FL_FILE_PVT locks
> >>>>     Date: 2014-01-09 14:19:46 GMT
> >>>>
> >>>> I think it's pretty important to document that. All implementations
> >>>> of traditional process-associated (.k.a. "POSIX") locks that I've ever 
> >>>> come across do detect deadlocks, so it's important to note that OFD locks 
> >>>> do not.
> >>>>
> >>>> I plan to add the following text to the fcntl(2) page:
> >>>>
> >>>> [[
> >>>> In the current implementation,
> >>>> no deadlock detection is performed for open file description locks.
> >>>> (This contrasts with process-associated record locks,
> >>>> for which the kernel does perform deadlock detection.)
> >>>> ]]
> >>>>
> >>>> Okay?
> >>>>
> >>>> cheers,
> >>>>
> >>>> Michael
> >>>>
> >>>>
> >>>
> >>> (note: I'm no longer with Red Hat, so jlayton@redhat.com no longer works)
> >>
> >> Ahh -- okay. Caches cleared.
> >>
> >>> Sounds fine to me.
> >>
> >> Okay.
> >>
> >>> FWIW, the deadlock detection for process-associated record locks is
> >>> pretty worthless except in certain narrow circumstances.
> >>
> >> Can you say some more about that, please? Maybe there's something 
> >> worth putting into the man page. (Are there cases where deadlocks
> >> are not detected?)
> >>
> > 
> > Both false negatives and false positives are possible.
> > 
> > Basically what the deadlock detector does is to walk down a chain of
> > blocked locks and look to see if any of them are waiting on locks that
> > the process currently owns.
> > 
> > Unfortunately, ownership is defined by the value of current->files. So
> > if you call clone with CLONE_FILES, you can have two threads of
> > execution that share lock ownership. If one is holding a lock that the
> > other wants to wait on, you'll end up getting EDEADLK back even though
> > it wouldn't necessarily have been a deadlock.
> > 
> > Also, the existing code gives up after searching a chain of 10
> > dependencies, so it's possible to hit a deadlock anyway if you have a
> > chain of dependencies that's longer than that.
> 
> Thanks, Jeff, How does the following text for the man page look to you:
> 
>        When placing locks with F_SETLKW, the  kernel  detects  dead‐
>        locks, whereby two or more processes have their lock requests
>        mutually blocked by locks held by the other  processes.   For
>        example,  suppose process A holds a write lock on byte 100 of
>        a file, and process B holds a write lock  on  byte  200.   If
>        each process then attempts to lock the byte already locked by
>        the other process  using  F_SETLKW,  then,  without  deadlock
>        detection,  both processes would remain blocked indefinitely.
>        When the kernel detects such deadlocks, it causes one of  the
>        blocking  lock  requests  to  immediately fail with the error
>        EDEADLK; an application that encounters such an error  should
>        release some of its locks to allow other applications to pro‐
>        ceed before attempting regain the  locks  that  it  requires.
>        Circular deadlocks involving more than two processes are also
>        detected.  Note, however, that there are limitations  to  the
>        kernel's deadlock-detection algorithm; see BUGS.
> 
>    BUGS
>      Deadlock detection
>        The  deadlock-detection algorithm employed by the kernel when
>        dealing with F_SETLKW requests can yield both false negatives
>        (failures  to  detect  deadlocks, leaving a set of deadlocked
>        processes blocked indefinitely) and false positives  (EDEADLK
>        errors  when  there is no deadlock).  For example, the kernel
>        limits the lock depth of its dependency search to  10  steps,
>        meaning  that  circular deadlock chains that exceed that size
>        will not be detected.  In addition, the  kernel  may  falsely
>        indicate  a deadlock when two or more processes created using
>        the clone(2) CLONE_FILES flag place locks that appear (to the
>        kernel) to conflict.
> 
> ?
> 

Looks good to me. The only thing I'd suggest is maybe "future proofing"
this by saying that the kernel MAY do deadlock detection (in the event
that we eventually allow it to be compiled out).

> >>> At some point, we probably should have a discussion as to whether
> >>> deadlock detection is really something we want to keep. The current
> >>> implementation requires a global spinlock which has obvious
> >>> consequences for scalability.
> >>
> >> Could be tricky. I wonder if there's code out there that depends
> >> on deadlock detection.
> >>
> > 
> > What I'd probably do first is add Kconfig option so we could compile it
> > out. Then we can lobby the distros to do so and see who complains.
> > Deadlock detection is optional in POSIX, so we aren't required to
> > support it.
> 
> Sounds like a reasonable plan. Given the limitations, I suppose
> it would be a brave / foolish application that tried to rely
> on the kernel's deadlock-detection algorithm, so perhaps
> there will be no complaints.
> 

Well, when we last tried to rip it out altogether some people did
complain, so removing it wholesale probably won't fly...

TBH, I think it's probably a reasonable thing to compile into "debug"
kernels, but when you are reasonably certain that your application
isn't going to hit these sorts of deadlocks, I don't see any reason why
you'd want to take the performance hit for something that's not
terribly reliable anyway.

-- 
Jeff Layton <jlayton@poochiereds.net>