Re: [Threads-devel] lock order debugging

From: Anthony Williams (anthony_at_[hidden])
Date: 2007-07-23 03:22:19

Frank Mori Hess <fmhess_at_[hidden]> writes:

> I'm toying with the idea of making a boost mutex wrapper class that tracks 
> and reports lock-ordering problems at runtime.  The tracking might be 
> turned on/off with a preprocessor define.  I'm curious if the experts 
> think this is worthwhile, or something better done at another level (like 
> using helgrind for instance)?  It would use BGL to build up a global 
> directed graph that has the lock ordering information.  As long as the 
> graph remains acyclic, there should be no lock ordering problems.  Each 
> thread would have to maintain its own list of the mutexes it currently has 
> locked.

That's an interesting idea --- by keeping track of the order in which locks
are taken, you can identify potential sources of deadlock before they
occur. In order to verify that they are indeed sources of deadlock, the
results will need to be checked manually afterwards, to verify that
potentially-deadlocking regions of code are running concurrently --- it is
possible that one thread is finished before the other is started. However, it
would be a potentially useful tool.

I have code for a mutex that checks for deadlock at runtime --- every thread
that tries to lock a checked mutex registers that it is waiting for that
mutex, and then when the lock is acquired it flags the mutex to identify the
owning thread. When a thread registers that it is waiting on a mutex, the
chain is followed --- which thread currently owns the mutex? Is it waiting on
another mutex? and so forth, until we either reach a thread that is not
waiting (we're fine), or a thread that is waiting on a mutex owned by the
original thread (deadlock).

I also have an incomplete prototype of a "levelled" mutex --- each mutex is
assigned a level, and threads may only lock a mutex with a higher level than
any currently locked. This enforces an ordering on mutex locks, which will
therefore prevent deadlock. It is not something that is usable in every
situation, though.

Anthony
-- 
Anthony Williams
Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL