Re: [Threads-devel] lock order debugging

From: Frank Mori Hess (fmhess_at_[hidden])
Date: 2007-07-24 17:37:17

On Tuesday 24 July 2007 03:23, Kai Brüning wrote:
> >That would avoid the potentially large overhead of analyzing my
> > directed graph for cycles.  I wonder if there's a good way to
> > dynamically assign levels to mutexes as they are added to the graph.
>
> If I am not mistaken, dynamically assigning the levels changes the
> nature of this approach substantially.

I was only speculating (prematurely) on optimizing the DAG by storing some 
additional "level" information in the nodes, which would have to be 
updated as new edges and nodes are added (probably obliterating any 
benefit).

> With statically assigned levels, the programmer has to structure the
> locking needs of the code in levels based on his knowledge of program
> structure. While not bullet proof without 100% test coverage, I consider
> this idea a deadlock avoidance approach. I'd consider a level conflict
> more a bug than a normal runtime event - level checking might even be
> switched off in release mode.
>
> With dynamically assigned levels I'd expect that any change in the flow
> of control can result in a level conflict somewhere. This makes it hard
> to be confident that testing eliminated all potential deadlocks, which
> makes this more a deadlock detection approach in my eyes. That is, code
> will have to be able to recover from a would-be deadlock situation, e.g.
> by throwing an exception.

No, this is meant to be a bug-detection tool, definitely able to be 
switched off for releases.  Using a DAG to keep track of lock ordering can 
be made to detect anything a leveled mutex scheme would find, it's just 
more flexible and can work with less user effort.  The downsides are it 
takes O(num_nodes + num_edges) to verify the graph has no cycles, instead 
of everything being constant time with a leveled mutex.  Also, the DAG 
scheme is more complicated.

To make the DAG scheme act just like the leveled mutex, you would do two 
things:
1) Allow the user to specify that multiple mutex objects should be 
represented by a single node in the graph (all the mutexes with level N 
would be one node).
2) Allow manual initialization of the graph with user-specified nodes and 
edges.  Actually, the user could just execute an otherwise useless 
sequence of mutex locking at program startup to initialize the graph.

However, the DAG would additionally allow the user to manually specify as 
much or as little of the locking heirarchy at initialization as he likes.  
Mutexes with no level specified could still be added to the DAG and 
checked as they are encountered.  Or, the user could specify that a group 
of mutexes are all the same level without bothering to specify what that 
level is exactly, which would just make every mutex in the group share the 
same node in the DAG.

-- 
Frank