Re: [RFC][PATCH] Fix hang in posix_locks_deadlock()

J. Bruce Fields
2007-10-28T17:47:21Z

On Fri, Oct 26, 2007 at 06:47:08PM -0400, J. Bruce Fields wrote:
> Hm. After another look: assume we have four tasks, t1, t2, t3, and t4.
> Assume t1 and t2 share the same current->files (so they're the same
> "owner" for the purpose of posix_same_owner()). Assume:
>
> t1 is waiting on a conflicting lock held by t3.
> t2 is waiting on a conflicting lock held by t4.
>
> Now suppose t4 requests a lock that conflicts with a lock held by t1 and
> t2. The list_for_each_entry() above will search for a task with t1 or
> t2 as owner, which is waiting on a lock. If it finds t1 first, the loop
> won't be noticed, so t4 will be put to sleep. Now we have a loop; t3
> can release its lock (it no longer matters), and we'll have
>
> t2 waiting on a conflicting lock held by t4, and
> t4 waiting on a conflicting lock held by t2.
>
> If a new task t5 then requests a lock conflicting with the one held by
> t2, then the above function will go into an infinite loop. I think.
>
> Consider the directed graph with each vertex representing the set of all
> tasks sharing the same file table, and each edge representing the
> relationship "a task at this vertex is waiting on a lock held by a task
> on another vertex". The existance of multiple tasks with the same file
> table means that we can no longer assume that each vertex has outdegree
> at most one, so we have to switch to an algorithm that works on an
> arbitrary directed graph. That sounds painful.
>
> Am I right about that, and about the example above? It'd be interesting
> to code it up just to make sure.
>
> If so, one can imagine various bandaids, but maybe we should just rip
> out the deadlock detection completely.... It's hard to imagine it being
> really useful anyway.

OK, well I cooked up a similar example, which was kind of fun, and
verified that I can indeed lock up the kernel this way.

The only way this can happen, though, is if you already have deadlocked
threads--that is to say, two threads that are each waiting on posix file
locks held by the other. (Or a similar cycle of length more than 2.) So
hopefully your application is doing some other kind of deadlock
detection (e.g. by killing threads that block for too long); otherwise
it already has a bug.

--b.