How to trace the source of deadlocks

In this article I explain how you can use the principles of tracing tools to find the sequence of events that lead to a deadlock. A deadlock is a cyclic dependency, for example where action A cannot continue because it is waiting for a resource to be unlocked by action B, however action B is waiting on A before continuing.

Deadlocks are one of the many banes of multi-threaded development for dynamically scheduled systems. Even though the locations of the deadlock itself are easy enough to find, establishing how we got to that point is often a harder task.

Access to resources is managed by access control locks, such as semaphores or mutexes. In figure 1 (below) this is represented by a chain of tasks claiming locks and locks claimed by tasks. Task and lock can only be in one of three dependency states:

• Task is waiting to claim a lock (task depends on lock)
• Lock is claimed by a task (lock depends on task)
• Task is not waiting and lock is not claimed (no dependencies)

Figure 1: A chain of tasks claiming locks and locks claimed by tasks

Knowing the state of each task and lock combination in the system is enough to confirm a deadlock and show the sequence of locks that lead up to this.

Note that, when dealing with binary semaphores and mutexes, these dependency relationships are a many-to-one relationship. This makes the state-machine of the relationships deterministic. So, at any point in a system, taking a snapshot of this state machine leaves us with the job of traversing this state machine to establish if there are any loops. Such a loop indicates a cyclic dependency and therefore a deadlock.

Figure 2: A cyclic dependency

Implementing tracing functions

The first task in establishing a deadlock is to be able to record the state of the system. We can do this by wrapping any instance of lock_claim and lock_release functions with wrappers. The wrappers store key trace data at several key stages for both an attempt to lock and release. This data includes the state of the last lock attempt, the task ID and the lock ID

• Prior to a lock attempt as WAITING
• After the lock attempt, logging the outcome as either CLAIMED or RELEASED

One implementation option is to maintain the state machine of dependencies in memory. However, this can be costly in terms of time for something that should ideally operate at high-speed. Also, only recording the last dependency link for each object can mean that the history of execution can be lost.

In this situation, a better option could be to produce a trace. Every semaphore operation is logged so all the state machine history is preserved. A deadlock can be detected by using the trace to reconstruct the state machine of the resource locks and to detect the cyclic dependency indicating the deadlock.

Although we haven't considered the case of timeouts here, this could be handled by timestamping the trace entries. Without special handling, a deadlock that occurs due to a timed lock request (i.e. one which will time out) will still be detected. This is not necessarily a problem, even though this may be considered a false-positive, as requests that are timing out due to deadlocks in the system are not typically thought of as healthy.

There are many ways to implement the trace recording and collection, for example: logging to a memory buffer, writing to an I/O port or using a tracing debugger.

It's worth noting at this point that RapiTask, provides a framework for this type of instrumentation and data collection, which can make it easier to collect the information necessary to perform this type of analysis.