How to detect circular calls?

I've been looking for causes for deadlocks and strategies/tools to avoid and detect them.

Another potential cause for deadlocks is to have blocking functions calling other blocking functions in a circular way, so that eventually a call never returns.

Sometimes this is hard to discover, specially in very large projects.

So, are there any tools/libraries/techiques that allow to automate the detection of circular calls in a program?

EDIT: I code mostly in C and C++ so, if possible, give any information about the topic that is applicable to those languages.

Nevertheless, it seems this topic is scarcely covered in SO, so answers for other languages are ok too. although maybe those deserve a topic of its own if someon开发者_JAVA技巧e finds it relevant

Thanks.

---

Circular (or recursive) calls that try to acquire the same non-reentrant lock are one of the easiest to debug blocking scenarios: locking is deterministic, and can be easily checked. When the application locks, fire up the debugger and look at the stack trace to understand what locks are held and why.

As to general solutions for the problem of locking... you can look into some libraries that provide mutex ordering, and detect when you are trying to lock on a mutex out of order. This type of solutions might be complex to implement correctly, but once in place it ensures that you cannot enter a deadlock condition, as it forces all processes to obtain the locks in the same order (i.e. if process A holds lock La, and it tries to acquire lock Lb for which the ordering is correct, then it can either succeed or lock, but whichever process is holding lock Lb cannot try to lock La as the ordering constraint would not be met).

---

If you are on Linux there 2 Valgrind tools for detecting deadlocks and race conditions: Helgrind, DRD. They both complement each other and it's worth to check for thread errors by both of them.

---

In linux you can use valgrind to detect deadlocks, use --tool=helgrind.

---

Best way to detect deadlocks (IMO) is to make a test program that calls all the functions in a random order in like 30 different threads 10000s of times.

If you get a deadlock you can use VS2010 "Parallel Stacks" window. Debug->Windows->Parallel Stacks
This window will show you all the stacks, so you can find the methods that are deadlocking.

A simple strategy I use to write thread-safe objects:
A thread safe object should be safe when its public methods are called, so you don't get deadlocks when it is used.

So, the idea is to just lock all the public methods that access the object's data.
Besides that you need to insure that within the class' code you never call a public method. If you need to use one of the public methods, then make that method private, and wrap the private method with a public method that locks and then calls it.

If you want better lock granularity you could just create objects for each part that has its own lock, and lock it like I suggested. Then use encapsulation to combine those classes to the one class.

Example:

class Blah {
  MyData data;
  Lock lock;
public:
  DataItem GetData(int index)
  { 
     ReadLock read(lock);
     return LocalGetData(index);
  }
  DataItem FindData(string key)
  {
     ReadLock read(lock);
     DataItem item;
     //find the item, can use LocalGetData() to get the item without deadlocking
     return item;

  }
  void PutData(DataItem item)
  {
    ReadLock write(lock); 
    //put item in database
  }

private:

  DataItem LocalGetData(int index)
  {
    return data[index];
  }
} 

---

You could find a tool that builds a call graph, and check the graph for cycles.

Otherwise, there are a number of strategies for detecting deadlocks or other circularities, but they all depend on having some sort of supporting infrastructure in place.

There are deadlock avoidance strategies, having to do with assigning lock priorities and ordering the locks according to priority. These require code changes and enforcing the standards, though.