Static deadlock analysis

Deadlocks are always, at the base of it, caused by different threads locking sets of objects in different orders. Is anyone aware of any tool which can do a sort of "static deadlock analysis" of a library? By this, I mean examine trajectories though possible call stacks, and find cases where locks are acquired in varying orders. You can simply run an application and watch to see if it deadlocks; but a library represents many possible applications, and whereas some of those may be fine, others may deadlock because of errors in the library.

Of course, one way to deal with this would be to design things properly from the start; this doesn't help if the codebase already exists. And another approach would be an extensive, and expensive, code review, but there is no guarantee that would find all the issues.

Anyway, has anyone ever heard of a tool that does anything like this automatically?

That would be interesting ... it would take an unusual understanding of possible sequential passes through code. Too hard for me anyhow.

Some thread package - Doug Lea? - has a method that takes an array of things you'd like to synchronize on. It sorts the array in "natural" order and locks objects in that order. So a bunch of different clients could ask for diffrent overlapping combinations of objects and always get them in the proper order. I thought that was pretty clever, probably need to go look up how it works.

Hi,

I used to use JProbe to profile and test apps. JProbe used to give wornings indicating possible deadlocks.

Same features are probably in OptimizeIt and JProfiler.

The biggest problem with deadlock is its only apperent at runtime and may depend on the ThreadScheduler. So you may find a tool that will analize the code and indicate that its style may lead to deadlock.

Let us know if you find anything usefull.

Thanks Yaroslav -- you're right, JProbe has a kind of lock-order analysis as a component of their Threadalyzer tool:

Lock Order Analyzer
The Lock Order analyzer predicts possible deadlocks by tracking the order in which locks are acquired, and reporting cases where concurrent threads need to hold the same lock and the same time.

But I'm concerned about the word "tracking" which implies to me that it watches a running app, as opposed to doing static analysis. It's really easy to find deadlocks in a real app, in my experience: you just run the sections you're testing in a loop on a multiprocessor machine, and your deadlock will turn up soon enough. I'm more interested in testing possible applications that don't yet exist, but which use a library which includes possibly faulty synchronization primitives.