Otdfbt

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).

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

Well, if you only hold one lock at a time, the second case never arises.

If you do actually have to acquire multiple locks, then reducing the number of locks (ideally to one) is better than making sure to acquire them in the right order.

But there are situations where my code could loop back upon itself in convoluted ways,

if you have complex logic sharing data, you're going to have a hard time.

The easiest way to make your multi-threaded code correct is to not share data in the first place: factor out components that can run asynchronously on their own data, and communicate with them via message queues.

The second easiest is to split your code into tasks, run using std::async or in your own threadpool with std::packaged_task or similar - it's more general than the thread-per-component style, but you have to take some care about inter-task dependencies (and the scheduling overhead can dominate if you have lots of very fine-grained tasks).

In both cases you're specifically trying to package a chunk of data, and the only code that can operate on it, together. Communication then happens by explicitly passing ownership via message queues or promises/futures.

Note that even if you can get your complex-code-operating-on-shared-data correct (and, even less likely, prove that it's correct to some reasonable standard), all the locking, un-locking, stalling and cache misses often eat away at any hoped-for performance improvement.

If you're not already doing so, strict use of RAII can help make locking more deterministic. The only functions that are allowed to lock anything are constructors, and the only functions that unlock are destructors.

This may well end up with creating a "Locker" class, whose only function is to manage one lock. Creating a Locker object locks the resource, and destroying the object unlocks it again. If a function wants to use a protected object, simply create a Locker object as a local variable in that function. RAII takes care of the rest.

Strict use of RAII prevents locks being left locked by accident, particularly if the code takes an unexpected path. That includes exceptions.

Modeling with proof assistant, such as TLA+.  You can model behaviors, protocols, algorithms, and it can search for deadlocks, race conditions, etc..  There are a number of guides on the web, such as https://learntla.com/introduction

The big cloud service providers use TLA+ to verify their systems — they've found very obscure bugs in lots of areas doing this, above and beyond mere testing. See http://cacm.acm.org/magazines/2015/4/184701-how-amazon-web-services-uses-formal-methods/fulltext

You might find thread safety analysis annotations of interest. Provided you can structure your code so the model fits, it provides a cheap way to check that things are OK. (The checks are also in gcc.)