How to check whether existing code base can deadlock

I’m improving/expanding a somewhat large code base, and I’ve introduced multithreading into it. But with the possibility of introducing code that could deadlock, which is nigh impossible to test for with black box testing alone, I want to at least get some reassurance my code is correct. I’ve already adhered to best practices, like never have more than one lock locked at a time, always lock multiple locks in the same order, etc. But there are situations where my code could loop back upon itself in convoluted ways, which makes this hard to enforce.

There are three ways I see that might achieve this;

1. Heavy code review sessions with lots of eyes and lots of notes being taken.

I feel that this could however easily miss a few interactions. And even if the current code base is proven to be correct, a few weeks/months of tweaking by different developers would make all notes and proofs obsolete again, necessitating a new review cycle, which is extremely impractical.

2: Employ software to extract a call graph out of my code base.

I’ve already tried a few tools, and while they’ll produce nice call graphs, it still takes manual inspection to see which functions lock what, and how that bubbles up through the call graph. And again, as with the option above: change the code base, and it’s necessary to redo the checks again.

3: Add tags to all lock-taking functions, and bubble up these tags in the function call stack.

The idea being that every unique lock gets it’s own tag, and functions taking more than one lock should be tagged with all these tags. This way (potentially) incompatible function calls should stand out like a sore thumb.

This one looks promising in that the code base is now self-explanatory, so that changes to the code do not necessitate a new code review (well, as long as the people making the changes take care to adhere to the tagging of course). But most function names would become very unwieldy, certainly the more top level ones which gather a lot of cruft due to the amount of lower level locking functions they call. Plus that (in my case) some functions just can’t be tagged this way (C++ constructors and overloaded operators e.g.), so I’d have to forego these constructs and add explicit “Init()” and “Copy()” functions all over the place…

Does anyone have a better approach to this? Or is a code review and adhering to best practices the best I can do? If it matters, I’m using C++ here, but not the .Net version (so no reflection and such).