4

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

  • Is there a particular reason you only are concerned about deadlocks and not other multi-threading issues such as race conditions? – JimmyJames May 30 at 17:17
  • I think I already set up the code to be invulnerable to race conditions; I mostly package the data together with it's lock, hide it behind a Get method, and exclusively use RAII locker objects to control temporary access. It's more threads interacting with each other that I fear I have lost oversight of, where each thread could hold more than one lock shared between them... – Carl Colijn May 30 at 17:29
  • Even the strongest developers have a hard time getting multi-threading right. I would highly recommend you treat your solution with a great deal of suspicion. The best attitude is to assume it's wrong and try to prove otherwise. I don't mean this as a slight. Even if you are the greatest multi-threading programmer the world has ever seen, there are likely problems with your code. C++ is especially unforgiving for this, to my knowledge/recollection. – JimmyJames May 30 at 18:10
  • It seems that C++ 11 added a memory model so the situation is less dire than my ancient experience with this. – JimmyJames May 30 at 18:38
  • I wonder if ScenGen could be of any use to you. (No affiliation) – Dom May 30 at 20:19
7

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.

  • Quick reassurance: performance is not an issue here (plenty of cycles to burn, relatively speaking). – Carl Colijn May 30 at 17:00
  • For the rest: I've indeed already replaced some combined lock-and-get methods by a quick temporary internal lock and returning a copy instead, but this is not feasible in all situations, since data does need to be updated real time in all places. And I mostly always acquire only one lock at a time, but in some circumstances I need more, and the code doing so might be able to indirectly circle back upon itself or on other paths/threads also needing these already acquired locks, so order is thus also sometimes an issue. – Carl Colijn May 30 at 17:00
  • It's hard to reconcile "performance is not an issue" with "data does need to be updated in real time in all places", because if you can afford to be a little slow, you can probably afford to push all mutations through a single thread to induce total ordering with no synchronization but the message queue. It's obviously hard to discuss specifics without a lot of detail, though. – Useless May 30 at 20:34
  • Ah, sorry for the confusion (wrong terminology there); real-time not as in split-second accurate, but if some shared data changes all threads using it should pick up on it next time they would use it (as opposed to them getting away with stale cached copies). – Carl Colijn May 30 at 21:12
1

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.

  • Thanks for the excellent suggestion! I already employ RAII as much as possible though, and have several 'Locker' classes at work already :) – Carl Colijn May 30 at 13:02
0

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

  • Oofff... I see you picked up my mention of "proving" there :) But it's more that I want a "good enough" estimate that the code is fine, not a formal bulletproof proof. TIA+ certainly is nice, but a bit overkill here; it would mean we'd have to write our code base again in pseudo code for the checker to check. – Carl Colijn May 30 at 16:51
  • @CarlColijn I was considering mention that the title of your question didn't match the body, because you aren't actually asking for a proof. – Trixie Wolf May 30 at 16:59
  • @TrixieWolf: good call -- I've updated the title to match. But I'm glad Erik added this answer; it's too late for my situation, but when I start a new project from scratch it might be useful to have this from the start. – Carl Colijn May 30 at 17:04
0

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

  • Thanks for that! There are some annotations that check for deadlock, but they all revolve around me specifying that a specific order of locking should be followed or that the caller may not hold certain locks. It seems this only checks for deadlock within a tread, and not so much between threads? In my case the problem is more that I have multiple processes all interacting in (somewhat) hard to determine ways, and they all need to access diverse data sources, sometimes more than one at a time. – Carl Colijn May 30 at 16:49
  • These locks are across threads (as they have to be), so when you annotate that a function/method can't be called when such a lock is held (or that a lock must be held when it's called) then that's a global assertion, not one within a thread. If you have a situation where a method sometimes needs a lock and sometimes doesn't then the annotations won't help. (If you're starting from scratch maybe that says your program structure needs changing, but I understand completely that for an existing codebase that might not be an option.) – Bruce Stephens May 30 at 17:23
  • The docu for EXCLUDES e.g. mentions This annotation is used to prevent deadlock. Many mutex implementations are not re-entrant, so deadlock can occur if the function acquires the mutex a second time. Re-entrancy is not really an issue in my case; it's more interprocess 2-lock-wrong-order deadlock I'm worried about. And indeed some functions need to lock 2 locks in succession, and locking is often only required on some code paths (e.g. syncing of shared data if needed and/or if it is ready). – Carl Colijn May 30 at 17:39
  • You're right, I think I confused myself. Generally, the annotations do require a particular (simple) structure of lock usage. If a program can be arranged to do that then the annotations provide a cheap way to check (and so maintain) correctness, but it sounds like your existing codebase (like many) may well not be suitable. – Bruce Stephens May 30 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.