Can lock ordering be enforced / detected to prevent deadlocks?

Question

I have inherited a big project with long history, and my task is to fix a bunch of deadlocks that have been reported over the years.

I understand the nature of a few deadlocks, and can reproduce them consistently using some carefully-placed Sleeps and other forced-timings.

But, fixing the deadlocks is not so simple. The code was not written with any strategy with regards to locking resources. I can hand-craft solutions for every deadlock, but much of it boils down to a problem of lock ordering.

For example, Worker 1:

Acquires resource A
{
  ...
  Acquires resource B
  {
    ...
  }
}

While worker 2 does this:

Acquires resource B
{
  ...
  Acquires resource A
  {
    ...
  }
}

So my question is: What is the best way to detect and/or enforce lock ordering problems in the code? Static analysis? Is there a compile-time way to detect this (ideal)? Or must I resort to detecting this kind of problem at runtime?

Any help is appreciated.

Answer 1

There is a simple strategy that finds potential deadlocks. Deadlocks happen if one bit of code locks A, then B, while another bit of code locks B, then A. If they do this at the wrong time, it's a deadlock. If they do that at a time when no harm is done, it's a potential deadlock. Assuming the first code is correct, then the second code shouldn't try to use the locks in that order (you must decide which code is wrong and which is right).

Assign an integer value to each lock. Say lock A = 100, lock B = 130. Then you make a rule: When holding a lock with value X, another lock must only acquired if it has a value Y > X. The code locking B then A violates the condition.

Obviously that needs some encapsulating of all locks to actually check this. If you find a violation, you have to decide whether to change the code or the value assigned to a lock, until you stop finding potential deadlocks.