Plagued by multithreaded bugs

Question

On my new team that I manage, the majority of our code is platform, TCP socket, and http networking code. All C++. Most of it originated from other developers that have left the team. The current developers on the team are very smart, but mostly junior in terms of experience.

Our biggest problem: multi-threaded concurrency bugs. Most of our class libraries are written to be asynchronous by use of some thread pool classes. Methods on the class libraries often enqueue long running taks onto the thread pool from one thread and then the callback methods of that class get invoked on a different thread. As a result, we have a lot of edge case bugs involving incorrect threading assumptions. This results in subtle bugs that go beyond just having critical sections and locks to guard against concurrency issues.

What makes these problems even harder is that the attempts to fix are often incorrect. Some mistakes I've observed the team attempting (or within the legacy code itself) includes something like the following:

Common mistake #1 - Fixing concurrency issue by just put a lock around the shared data, but forgetting about what happens when methods don't get called in an expected order. Here's a very simple example:

void Foo::OnHttpRequestComplete(statuscode status)
{
    m_pBar->DoSomethingImportant(status);
}

void Foo::Shutdown()
{
    m_pBar->Cleanup();
    delete m_pBar;
    m_pBar=nullptr;
}

So now we have a bug in which Shutdown could get called while OnHttpNetworkRequestComplete is occuring on. A tester finds the bug, captures the crash dump, and assigns the bug to a developer. He in turn fixes the bug like this.

void Foo::OnHttpRequestComplete(statuscode status)
{
    AutoLock lock(m_cs);
    m_pBar->DoSomethingImportant(status);
}

void Foo::Shutdown()
{
    AutoLock lock(m_cs);
    m_pBar->Cleanup();
    delete m_pBar;
    m_pBar=nullptr;
}

The above fix looks good until you realize there's an even more subtle edge case. What happens if Shutdown gets called before OnHttpRequestComplete gets called back? The real world examples my team has are even more complex, and the edge cases are even harder to spot during the code review process.

Common Mistake #2 - fixing deadlock issues by blindly exiting the lock, wait for the other thread to finish, then re-enter the lock - but without handling the case that the object just got updated by the other thread!

Common Mistake #3 - Even though the objects are reference counted, the shutdown sequence "releases" it's pointer. But forgets to wait for the thread that is still running to release it's instance. As such, components are shutdown cleanly, then spurious or late callbacks are invoked on an object in an state not expecting any more calls.

There are other edge cases, but the bottom line is this:

Multithreaded programming is just plain hard, even for smart people.

As I catch these mistakes, I spend time discussing the errors with each developer on developing a more appropriate fix. But I suspect they are often confused on how to solve each issue because of the enormous amount of legacy code that the "right" fix will involve touching.

We're going to be shipping soon, and I'm sure the patches we're applying will hold for the upcoming release. Afterwards, we're going to have some time to improve the code base and refactor where needed. We won't have time to just re-write everything. And the majority of the code isn't all that bad. But I'm looking to refactor code such that threading issues can be avoided altogether.

One approach I am considering is this. For each significant platform feature, have a dedicated single thread where all events and network callbacks get marshalled onto. Similar to COM apartment threading in Windows with use of a message loop. Long blocking operations could still get dispatched to a work pool thread, but the completion callback is invoked on on the component's thread. Components could possibly even share the same thread. Then all the class libraries running inside the thread can be written under the assumption of a single threaded world.

Before I go down that path, I am also very interested if there are other standard techniques or design patterns for dealing with multithreaded issues. And I have to emphasize - something beyond a book that describes the basics of mutexes and semaphores. What do you think?

I am also interested in any other approaches to take towards a refactoring process. Including any of the following:

1. Literature or papers on design patterns around threads. Something beyond an introduction to mutexes and semaphores. We don't need massive parallelism either, just ways to design an object model so as to handle asynchronous events from other threads correctly.

2. Ways to diagram the threading of various components, so that it will be easy to study and evolve solutions for. (That is, a UML equivalent for discussing threads across objects and classes)

3. Educating your development team on the issues with multithreaded code.

4. What would you do?

Answer 1

Your code has significant other issues apart from just that. Manually deleting a pointer? Calling a cleanup function? Owch. Also, as accurately pointed out in the question comment, you don't use RAII for your lock, which is another fairly epic fail and guarantees that when DoSomethingImportant throws an exception, terrible things happen.

The fact that this multithreaded bug is occurring is just a symptom of the core problem- your code has extremely bad semantics in any threading situation and you're using completely unreliable tools and ex-idioms. If I were you, I'd be amazed that it functions with a single thread, let alone more.

Common Mistake #3 - Even though the objects are reference counted, the shutdown sequence "releases" it's pointer. But forgets to wait for the thread that is still running to release it's instance. As such, components are shutdown cleanly, then spurious or late callbacks are invoked on an object in an state not expecting any more calls.

The whole point of reference counting is that the thread has already released it's instance. Because if not, then it cannot be destroyed because the thread still has a reference.

Use std::shared_ptr. When all threads have released (and nobody, therefore, can be calling the function, as they have no pointer to it), then the destructor is called. This is guaranteed safe.

Secondly, use a real threading library, like Intel's Thread Building Blocks or Microsoft's Parallel Patterns Library. Writing your own is time-consuming and unreliable and your code is full of threading details which it doesn't need. Doing your own locks is just as bad as doing your own memory management. They have already implemented many general-purpose very useful threading idioms which work correctly for your use.

Answer 2

Other posters have commented well on what should be done to fix the core issues. This post is concerned with the more immediate problem of patching the legacy code well-enough to buy you time to redo everything the right way. In other words, this isn't the right way to do things, its just a way to limp along for now.

Your idea of consolidating key events is a good start. I would go so far as to use a single dispatch thread to handle all key synchronization events, wherever there is order dependency. Setup a thread-safe message queue and wherever you currently perform concurrency sensitive operations (allocations, cleanups, callbacks, etc.), instead send a message to that thread and have it perform or trigger the operation. The idea is that this one thread controls all work-unit starts, stops, allocations, and cleanups.

The dispatch thread does not solve the problems you described, it just consolidates them in one place. You still have to worry about events/messages occurring in unexpected order. Events with significant run-times will still need to be sent off to other threads, so there are still issues with concurrency on shared data. One way to mitigate that is to avoid passing data by reference. Whenever possible, the data in dispatch messages should be copies which will be owned by the recipient. (This is along the lines of making data immutable that others have mentioned.)

The advantage of this dispatch approach is that within the dispatch thread you have a kind of safe-haven where you at least know that certain operations are occurring sequentially. The disadvantage is that it creates a bottleneck and extra CPU overhead. I suggest not worrying about either of those things at first: focus on gaining some measure of correct operation first by moving as much as you can into the dispatch thread. Then do some profiling to see what is taking up the most CPU time and begin shifting it back out of the dispatch thread using correct multithreading techniques.

Again, what I'm describing is not the right way to do things, but its a process that can move you toward the right way in increments that are small enough to meet commercial deadlines.

Answer 3

Based on the code shown, you have a pile of WTF. It is extremely difficult if not impossible to incrementally fix a poorly written multi-threaded application. Tell the owners that the application will never be reliable without significant rework. Give them an estimate based on inspecting and reworking every bit of the code that is interacting with shared objects. First give them an estimate for the inspection. Then you can give an estimate for the rework.

When you do rework the code, you should plan to write the code so that it provably correct. If you don't know how to do that, find someone who does, or you will end up in the same place.

Answer 4

Common mistake #1 - Fixing concurrency issue by just put a lock around the shared data, but forgetting about what happens when methods don't get called in an expected order. Here's a very simple example:

The mistake here is not the "forgetting", but the "not fixing it". If you have things happening in an unexpected order, you have a problem. You should solve it instead of trying to work around it (slapping a lock onto something is usually a work-around).

You should try to adapt the actor model/messaging to a certain degree and to have separation of concern. The role of Foo is clearly to handle some kind of HTTP communication. If you want to design your system to do this in parallel, it's the layer above that must handle object lifecycles and access synchronization accordingly.

Trying to have a number of threads operate on the same mutable data is hard. But it's also rarely necessary. All common cases that demand this, have already been abstracted into more manageable concepts and implemented a number of times for about any major imperative language. You just have to use them.

Answer 5

If you have some time to dedicate to refactoring your application, I would advise you to take a look at the actor model (see e.g. Theron, Casablanca, libcppa, CAF for C++ implementations).

Actors are objects that run concurrently and communicate with each other only using asynchronous message exchange. So, all the problems of thread management, mutexes, deadlocks, etc, are dealt with by an actor implementation library and you can concentrate on implementing the behaviour of your objects (actors), which boils down to repeating the loop

1. Receive message
2. Perform computation
3. Send message(s) / create / kill other actors.

One approach for you could be to do some reading on the topic first, and possibly have a look at one library or two to see if the actor model can be integrated in your code.

I have been using (a simplified version of) this model in a project of mine for a few months now and I am amazed by how robust it is.

Answer 6

Your problems are pretty bad, but typical of poor use of C++. Code review will fix some of these problems. 30 minutes, one set of eyeballs yeilds 90% of the results.(citation for this is googleable)

#1 Problem You need to ensure there is a strict lock hierachy to prevent your locking deadlocking.

If you replace Autolock with a wrapper and a macro you can do this.

Keep a static global map of locks created in the back of your wrapper. You use a macro to insert the finename and line number information into the Autolock wrapper constructor.

You'll also need a static dominator graph.

Now inside lock you have to update the dominator graph, and if you get an ordering change you assert an error and abort.

After extensive testing you may be rid of most of the latent deadlocks.

The code is left as an exercise for the student.

Problem #2 will then go away ( mostly)

Your archientctual solution is going to work. I've used it before in mission and life crtical systems. My take on it is this

• Pass immutable objects or make copies of them before passing.

• Don't share data via public variables or getters.

• External events come in via a multithreaded dispatch in to a queue serviced by one thread. Now you can sort-of reason about Event handling.

• Data changes that cross threads come into a thread-safe qeuue, get handled by one thread. Make subscriptions. Now you can sort-of reason about data flows.

• If your data needs to go cross-town, publish it to the data queue. That will copy it and pass it to the subscribers asnynchronously. Also breaks all the data dependancies in the program.

This is pretty much an actor model on the cheap. Giorgio's links will help.

Finally, your problem with shut-down objects.

When you are reference counting, you've solved 50%. The other 50% is to refernce count callbacks. Pass callback holders a refernce. Shutdown call then has to wait for zero count on the refcount. Doesn't solve complicated object graphs; that's getting into real garbage collection. ( Which is the motivation ins Java for not make any promises about when or if finalize() will get called; to get you out of programming that way.)

Answer 7

For future explorers: to complement the answer about the actor model I would like to add CSP (communicating sequential processes), with a nod to the larger family of process calculi it's in. CSP is similar to the actor model, but split up differently. You still have a bunch of threads, but they communicate through specific channels, rather than specifically with each other, and both processes must be ready to respectively send and receive before either happens. There's also a formalized language for proving CSP code correct. I'm still transitioning into using CSP heavily, but I've been using it in a few projects for a few months, now, and it's greatly simplified things.

The University of Kent has a C++ implementation (https://www.cs.kent.ac.uk/projects/ofa/c++csp/, cloned at https://github.com/themasterchef/cppcsp2).

Answer 8

Literature or papers on design patterns around threads. Something beyond an introduction to mutexes and semaphores. We don't need massive parallelism either, just ways to design an object model so as to handle asynchronous events from other threads correctly.

I'm currently reading this and it explain all the problems you can get and how to avoid them, in C++ (using the new threading library but I think the global explainations are valid for your case): http://www.amazon.com/C-Concurrency-Action-Practical-Multithreading/dp/1933988770/ref=sr_1_1?ie=UTF8&qid=1337934534&sr=8-1

Ways to diagram the threading of various components, so that it will be easy to study and evolve solutions for. (That is, a UML equivalent for discussing threads across objects and classes)

I personally use a simplified UML and just assume that messages are done asynchronously. Also, this is true between "modules" but inside modules I don't want to have to know.

Educating your development team on the issues with multithreaded code.

The book would help, but I think exercices/prototyping and experienced mentor would be beter.

What would you do?

I would totally avoid having people not understanding concurrency problems work on the project. But I guess you cannot do that, so in your specific case, other than try to make sure the team gets more educated, I have no idea.

Answer 9

You are already on the way by acknowledging the problem and actively looking for a solution. Here's what I would do:

• Sit down and design a threading model for your application. This is a document which answers questions like: Which types of threads do you have? What things should be done in which thread? What different kinds of synchronization patterns should you use? In other words, it should describe the "rules of engagement" when battling multithreading problems.
• Use thread analysis tools to check your codebase for errors. Valgrind has a thread checker called Helgrind which is good at spotting things like shared state being manipulated without proper synchronization. There are most certainly other good tools out there, go look for them.
• Consider migrating away from C++. C++ is a nightmare to write concurrent programs in. My personal choice would be Erlang, but that is a matter of taste.

Answer 10

Looking at your example: As soon as Foo::Shutdown starts executing, it must not be possible to call OnHttpRequestComplete to run anymore. That has nothing to do with any implementation, it just can't work.

You could also argue that Foo::Shutdown shouldn't be callable while a call to OnHttpRequestComplete is running (definitely true) and probably not if a call to OnHttpRequestComplete is still outstanding.

The first thing to get right is not locking etc. but the logic of what is allowed or not. A simple model would be that your class may have zero or more incomplete requests, zero or more completions that haven't been called yet, zero or more completions that are running, and that your object wants to shutdown or not.

Foo::Shutdown would be expected to finish running completions, to run incomplete requests to the point where they can be shutdown if possible, to not allow any more completions to be started, to not allow more requests to be started.

What you need to do: Add specs to your functions saying exactly what they will do. (For example, starting an http request might fail after Shutdown hase been called). And then write your functions so they meet the specs.

Locks are best used only for the tiniest possible amount of time to control modification of shared variables. So you might have a variable "performingShutDown" which is protected by a Lock.

Answer 11

What would you do?

To be honest; I'd run away, quickly.

Concurrency issues are NASTY. Something can work perfectly for months and then (due to the specific timing of several things) suddenly blow up in the customer's face, with no way to figure out what happened, no hope of ever seeing a nice (reproducible) bug report and no way to even be sure it wasn't a hardware glitch that has nothing to do with the software.

Avoiding concurrency problems needs to begin during the design phase, starting with exactly how you're going to do it ("global lock order", actor model, ...). It's not something that you try to fix in a mad panic in the hope that everything won't self-destruct after an upcoming release.

Note that I am not joking here. Your own words ("Most of it originated from other developers that have left the team. The current developers on the team are very smart, but mostly junior in terms of experience.") indicate that all of the experience people have already done what I'm suggesting.