Killing POSIX deadlock detection

Killing POSIX deadlock detection

[Matthew Wilcox]

On Sun, Jun 06, 2004 at 01:04:22PM +1000, Stephen Rothwell wrote:
> Here's my (contrived) example:
> 
> Process P1 contains threads T1 and T2
> Process P2
> 
> I am using "process id" and "thread id" in the POSIX sense.  These are
> exclusive, whole file locks for simplicity.
> 
> T1 locks file F1 -> lock (P1, F1)
> P2 locks file F2 -> lock (P2, F2)
> P2 locks file F1 -> blocks against (P1, F1)
> T1 locks file F2 -> blocks against (P2, F2)

Less contrived example -- T2 locks file F2.  We report deadlock here too,
even though T1 is about to unlock file F1.

I pointed this out over a year ago when NPTL first went in and nobody
seemed interested in having the discussion then.  All I got was a private
reply from Andi Kleen suggesting that we shouldn't remove it.

So, final call.  Any objections to never returning -EDEADLCK?

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: Killing POSIX deadlock detection

[Trond Myklebust]

På su , 06/06/2004 klokka 09:27, skreiv Matthew Wilcox:
\
> > T1 locks file F1 -> lock (P1, F1)
> > P2 locks file F2 -> lock (P2, F2)
> > P2 locks file F1 -> blocks against (P1, F1)
> > T1 locks file F2 -> blocks against (P2, F2)
> 
> Less contrived example -- T2 locks file F2.  We report deadlock here too,
> even though T1 is about to unlock file F1.

So what is better: report an error and give the user a chance to
recover, or allowing the potential deadlock?
Only the user can resolve problems such as the above threaded problem,
given the SuS definitions.

> So, final call.  Any objections to never returning -EDEADLCK?

Yes: As Chuck points out, that is a fairly nasty change of the userland
API.

Worse: it is a change that fixes only one problem for only a minority of
users (those that combine locking over multiple NPTL threads - a
situation which after the "fix" remains just as poorly defined) at the
expense of reintroducing a series of deadlocking problems for those
single threaded users that rely on the EDEADLK (and have done so
throughout the entire 2.4.x series).

Finally, EDEADLK does actually appear to be mandatory to implement in
SUSv3, given that it states:

        A potential for deadlock occurs if a process controlling a
        locked region is put to sleep by attempting to lock another
        process' locked region. If the system detects that sleeping
        until a locked region is unlocked would cause a deadlock,
        fcntl() shall fail with an [EDEADLK] error.
        
(again see
http://www.opengroup.org/onlinepubs/009695399/functions/fcntl.html)

Trond

Re: Killing POSIX deadlock detection

[Eric W. Biederman]

Trond Myklebust <trond.myklebust@fys.uio.no> writes:

> På su , 06/06/2004 klokka 09:27, skreiv Matthew Wilcox:
> \
> > > T1 locks file F1 -> lock (P1, F1)
> > > P2 locks file F2 -> lock (P2, F2)
> > > P2 locks file F1 -> blocks against (P1, F1)
> > > T1 locks file F2 -> blocks against (P2, F2)
> > 
> > Less contrived example -- T2 locks file F2.  We report deadlock here too,
> > even though T1 is about to unlock file F1.

There is a fairly sane linux specific definition here.  We should
track these things not by pid or tid, but by struct files_struct.

> So what is better: report an error and give the user a chance to
> recover, or allowing the potential deadlock?

Reading the SUS definition below we should only report a deadlock when
it is certain. 

For multiple processes with the same set of file descriptors open
that is an interesting graph problem.  Unless there is nothing
another process can do, to remove the deadlock situation.

> Only the user can resolve problems such as the above threaded problem,
> given the SuS definitions.
> 
> > So, final call.  Any objections to never returning -EDEADLCK?
> 
> Yes: As Chuck points out, that is a fairly nasty change of the userland
> API.

???? Failing to detect a deadlock is not a change in the API.
It is simply a change in behavior.

> Worse: it is a change that fixes only one problem for only a minority of
> users (those that combine locking over multiple NPTL threads - a
> situation which after the "fix" remains just as poorly defined) at the
> expense of reintroducing a series of deadlocking problems for those
> single threaded users that rely on the EDEADLK (and have done so
> throughout the entire 2.4.x series).

Relying on EDEADLK is broken.  That is about as bad as relying on 
getting -EACCESS instead of SIGSEGV.

Detecting deadlocks is certainly a quality of implementation issue.
But unless my memory is shaky detecting deadlocks is a hard problem.

Perhaps what we should do is simply not attempt to detect deadlocks
involving threaded processes.

With threads the problems escalates from one of cycle detection
to something fairly weird.
 
> Finally, EDEADLK does actually appear to be mandatory to implement in
> SUSv3, given that it states:
> 
>         A potential for deadlock occurs if a process controlling a
>         locked region is put to sleep by attempting to lock another
>         process' locked region. If the system detects that sleeping
>         until a locked region is unlocked would cause a deadlock,
>         fcntl() shall fail with an [EDEADLK] error.
>         
> (again see
> http://www.opengroup.org/onlinepubs/009695399/functions/fcntl.html)

Hmm.  I don't see that the system is required to detect a deadlock.
Just what it does after it has detected one.

Eric

Re: Killing POSIX deadlock detection

[Trond Myklebust]

På su , 06/06/2004 klokka 16:09, skreiv Eric W. Biederman:
> Trond Myklebust <trond.myklebust@fys.uio.no> writes:
> 
> > På su , 06/06/2004 klokka 09:27, skreiv Matthew Wilcox:
> > \
> > > > T1 locks file F1 -> lock (P1, F1)
> > > > P2 locks file F2 -> lock (P2, F2)
> > > > P2 locks file F1 -> blocks against (P1, F1)
> > > > T1 locks file F2 -> blocks against (P2, F2)
> > > 
> > > Less contrived example -- T2 locks file F2.  We report deadlock here too,
> > > even though T1 is about to unlock file F1.
> 
> There is a fairly sane linux specific definition here.  We should
> track these things not by pid or tid, but by struct files_struct.

RTFC... Look carefully in fs/locks.c at stuff like posix_same_owner().
We currently use both the tgid and the struct files_struct (although
there are a few notable bugs where we only check the one or the
other)...

That is, however, a definition which breaks the SUS standards, and it
therefore ends up introducing pathologies such as the steal_locks crap.
struct files_struct is NOT a sane basis for tracking locks.

> > Yes: As Chuck points out, that is a fairly nasty change of the userland
> > API.
> 
> ???? Failing to detect a deadlock is not a change in the API.
> It is simply a change in behavior.

It is a change in functionality from one where potential deadlocks are
detected and reported as errors to one where deadlocks are suddenly
possible. Are you saying that functionality is not a part of the API?


> Perhaps what we should do is simply not attempt to detect deadlocks
> involving threaded processes.

So how do you define (and detect) a threaded process?

Trond

RE: Killing POSIX deadlock detection

[Lever, Charles]

> So, final call.  Any objections to never returning -EDEADLCK?

not an objection, but a consideration.

is this a change that belongs in 2.6?  it does significantly change the
behavior of the system call API, and could "break" applications.

unless this fixes a significant bug, perhaps it should wait for 2.7?
that would give fair warning to developers who need to fix their broken
programs.