OFD locks and deadlock detection

Hi Jeff,

I just happened to notice :

commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
Author: Jeff Layton <[email protected]>
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

Quoted 33 lines · On Mon, 19 May 2014 15:18:13 +0200 "Michael Kerrisk (man-pages)"…

Hi Jeff,

I just happened to notice :

commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
Author: Jeff Layton <[email protected]>
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?

Quoted 5 lines

cheers,

Michael

(note: I'm no longer with Red Hat, so [email protected] 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.

Quoted 36 lines · Jeff Layton

Quoted 33 lines · On Mon, 19 May 2014 15:18:13 +0200 "Michael Kerrisk (man-pages)"…

Hi Jeff,

I just happened to notice :

commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
Author: Jeff Layton <[email protected]>
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?

Quoted 7 lines

Quoted 5 lines

cheers,

Michael

(note: I'm no longer with Red Hat, so [email protected] no longer works)

Ahh -- okay. Caches cleared.

Quoted 1 line

Sounds fine to me.

Okay.

Quoted 2 lines

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?)

Quoted 4 lines

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.

Quoted 49 lines · On Mon, 19 May 2014 20:36:45 +0200 "Michael Kerrisk (man-pages)"…

Quoted 36 lines · Jeff Layton

Quoted 33 lines · On Mon, 19 May 2014 15:18:13 +0200 "Michael Kerrisk (man-pages)"…

Hi Jeff,

I just happened to notice :

commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
Author: Jeff Layton <[email protected]>
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?

Quoted 7 lines

Quoted 5 lines

cheers,

Michael

(note: I'm no longer with Red Hat, so [email protected] no longer works)

Ahh -- okay. Caches cleared.

Quoted 1 line

Sounds fine to me.

Quoted 9 lines

Okay.

Quoted 2 lines

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.

Quoted 5 lines

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 74 lines · Jeff Layton

Quoted 49 lines · On Mon, 19 May 2014 20:36:45 +0200 "Michael Kerrisk (man-pages)"…

Quoted 36 lines · Jeff Layton

Quoted 33 lines · On Mon, 19 May 2014 15:18:13 +0200 "Michael Kerrisk (man-pages)"…

Hi Jeff,

I just happened to notice :

commit 57b65325fe34ec4c917bc4e555144b4a94d9e1f7
Author: Jeff Layton <[email protected]>
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?

Quoted 7 lines

Quoted 5 lines

cheers,

Michael

(note: I'm no longer with Red Hat, so [email protected] no longer works)

Ahh -- okay. Caches cleared.

Quoted 1 line

Sounds fine to me.

Quoted 9 lines

Okay.

Quoted 2 lines

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.

Quoted 3 lines

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.

?

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

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.

Quoted 8 lines

Quoted 3 lines

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.