25

Recently I've been working on projects that heavily use threading. I think that I'm OK at designing them; use stateless design as much as possible, lock access to all resources that more than one thread needs, etc. My experience in functional programming has helped that immensely.

However, when reading other people's thread code, I get confused. I am debugging a deadlock right now, and since the coding style and design are different from my personal style, I am having a difficult time seeing potential deadlock conditions.

What do you look for when debugging deadlocks?

  • I'm asking this here instead of SO because I want more general pointers about debugging deadlocks, not a specific answer to my problem. – Michael K Jan 26 '11 at 14:57
  • Strategies I can think of are logging (as several others have pointed out), actually examining the deadlock graph of who's-waiting-for-a-lock-held-by-whom (see stackoverflow.com/questions/3483094/… for some pointers) and lock annotations (see clang.llvm.org/docs/ThreadSafetyAnalysis.html ). Even if it's not your code, you might try to convince the author to add annotations-- they'll probably find bugs and fix them (possibly including yours) in the process. – Don Hatch May 1 '15 at 1:20
23

If the situation is a real deadlock (i.e. two threads hold two different locks, but at least one thread wants a lock the other thread holds) then you need to first abandon all pre-conceptions of how the threads order locking. Assume nothing. You may want to remove all comments from the code you're looking at, as those comments may cause you to believe something that doesn't hold true. It's hard to emphasize this enough: assume nothing.

After that, determine what locks get held while a thread attempts to lock something else. If you can, ensure that a thread unlocks in reverse order from locking. Even better, ensure that a thread holds only one lock at a time.

Painstakingly work through a thread's execution, and examine all locking events. At each lock, determine whether a thread holds other locks, and if so, under what circumstances another thread, doing a similar execution path, can get to the locking event under consideration.

It's certainly possible you will not find the problem before you run out of time or money.

  • 4
    +1 Wow, that's pessimistic...ain't it the truth, though. It's a given that you can't find all bugs. Thanks for the suggestions! – Michael K Jan 26 '11 at 16:21
  • Bruce,your charactarization of "real deadlock" is surprising to me. I thought a deadlock between two threads is when each is waiting for a lock that the other holds. Your definition seems to also include the case that a thread, while holding one lock, waits to acquire a second lock that is currently held by a different thread. That doesn't sound like deadlock to me; is it?? – Don Hatch May 1 '15 at 0:36
  • @DonHatch - I phrased it poorly. The situation you describe isn't deadlock. I had hoped to convey the messiness of debugging a situation that includes a thread holding lock A, then trying to acquire lock B, while the thread that holds lock B is trying to acquire lock A. Maybe. Or maybe the situation is a lot more complicated. You just need to keep a very open mind about the order of lock acquisition. Examine all assumptions. Trust nothing. – Bruce Ediger May 1 '15 at 2:00
  • +1 suggesting to carefully read the code and examine all lock operation in isolation. Much easier to look at a complex graph by carefully examine a single node than it is to try and see the whole thing at once. How many times have I found the problem just by staring at the code and running different scenarios in my head. – Newtopian Sep 29 '16 at 14:01
11
  1. As others have said...if you can get useful information for logging then try that first as it is the easiest thing to do.

  2. Identify the locks that are involved. Change all the mutex/semaphores that wait forever to timed waits...something ridiculously long like 5 mins. Log the error when it times out. This will at least point you in the direction of one of the locks that is involved in the issue. Depending the variability of the timing you might get lucky and find both locks after a few runs. Use function failure code's/conditions to log a pseudo stack trace after the timed wait fails to identify how you got there in the first place. This should help you identify the thread that is involved in the issue.

  3. Another thing that you could try is building a wrapper library around your mutex/semaphore services. Track what threads have each mutex and what threads are waiting on the mutex. Build a monitor thread that checks how long threads have been blocking. Trigger on some reasonable duration and dump the state information that you are tracking.

At some point, plain old code inspection is going to be necessary.

6

First step (as Péter says) is logging. Though in my experience this is often problematic. In heavy parallel processing this is often not possible. I had to debug something similar with a neural network once, that processed 100k of nodes per second. The error happened only after several hours and even a single line of output slowed down things so much, that it would have taken days. If logging is possible, concentrate less on the data, but more on the flow of the program, until you know in which part it happens. Just a simple line at the beginning of each function and if you can find the right function, split that in smaller chunks.

Another option is removing parts of the code and data to localise the bug. Maybe even write some small program that takes only some of the classes and runs only the most basic tests (still in several threads of course). Remove everything gui related, for example any output about the actual processing state. (I found the user interface to be the source of the bug often enough)

In your code try to follow the complete logical flow of control between initialising the lock and releasing it. A common error could be to lock at the start of a function, unlock at the end, but have a conditional return statement somewhere in between. Exceptions could prevent releasing too.

  • "Exceptions could prevent releasing" --> I pity languages that do not have scoped variables :/ – Matthieu M. Jan 26 '11 at 18:04
  • 1
    @Matthieu: Having scoped variables and actually using them properly may be two different things. And he asked for possible problems in general, without mentioning a specific language. So this is one thing, that may influence flow of control. – thorsten müller Jan 26 '11 at 20:01
3

My best friends have been print/log statements at interesting places within the code. These usually help me understand better what's really going on inside the app, without disrupting the timing between different threads, which could prevent reproducing the bug.

If that fails, my only remaining method is staring at the code and trying to build up a mental model of the various threads and interactions, and trying to think of possible crazy ways to achieve what apparently has happened :-) But I don't consider myself a very experienced deadlock-slayer. Hopefully others will be able to give better ideas, from which I can learn too :-)

  • 1
    I debugged a couple of dead locks like this today. The trick was to wrap pthread_mutex_lock() with a macro that prints the function, line number, file name and the mutex variable's name (by tokenizing it) before and after acquiring the lock. Do the same for pthread_mutex_unlock() too. When I saw that my thread's froze, I just had to look at the last two messages, there were two threads trying to lock but never finishing it! Now all that's left is add a mechanism to toggle this at runtime. :-) – Plumenator May 3 '12 at 12:34
3

First of all, try to get that code's author. He'll probably have the idea what he had written. even if you two can't pinpoint the problem just by talking, At least you can sit down with him to pinpoint the deadlock portion, which will be much faster than you understanding his/her code without help.

Failing that, like Péter Török said, Logging is probably be the way. As far as I know, Debugger did a bad job on multi-threading environment. try to locate where is the lock is, get a whole what resources are waiting, and in what condition the racing condition occurs.

  • no, logging is your enemy here - when you put slow logging in, you change the behaviour of the program to the point where it is easy to get a program that runs perfectly fine with logging enabled, but deadlocks when the logging is turned off. Its the same kind of problem you'd have when running a program on a single rather than a multicore CPU. – gbjbaanb Oct 22 '12 at 21:41
  • @gbjbaanb, I think saying it's your enemy is far too harsh. Perhaps it would be correct to say it's your best friend, who lets you down once in a while. I'll agree with several other people on this page who say logging is a good first step to take, after examination of the code has failed-- often (in fact most of the time, in my experience) a simple logging strategy will locate the problem easily, and you're done. Otherwise by all means resort to other methods, but I don't think it's good advice to avoid trying what is most often the best tool for the job just because it isn't always helpful. – Don Hatch May 1 '15 at 1:07
0

This question attracts me ;) First of all, consider yourself lucky since you were able to reproduce the issue consistently on every run. If you receive the same exception with the same stacktrace each time then it should be fairly straight-forward. If not, then don't trust the stacktrace that much, instead just monitor the access to the global objects and its state changes during the execution.

0

If you have to debug deadlocks, you're already in trouble. As a rule, use locks for the shortest possible time - or not at all, if possible. Any situation where you take a lock and then go off to non-trivial code should be avoided.

It depends of course on your programming environment, but you should look at things like sequential queues that may allow you to access a resource from a single thread only.

And then there is an old but infallible strategy: Assign a "level" to each lock, starting at level 0. If you take a level 0 lock you are not allowed any other locks. After taking a level 1 lock you may take a level 0 lock. After taking a level 10 lock you can take locks at levels 9 or lower etc.

If you find this impossible to do, you need to fix your code because you will run into deadlocks.

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