Finding deadlocks fast: data reduction helps pinpoint errors

| 0 Comments
In the previous tutorial I showed how LID and LIA, our deadlock detection tools, could be used to pinpoint lock inversions and show you deadlocks which are lurking in your code. The examples used were very simple, with only the two locks involved in each lock acquisition sequence. Real code is seldom so clean.

Real world code's use of locks can be surprisingly complex; object oriented encapsulation hides the use of locks inside of objects and layered designs may use locks in the layers that call into your code and may use locks in the layers that you call into. Deadlocks caused by lock inversions involve two locks but there may be many more locks being used by the code that causes the lock inversion. Our tools build graphs of the locks that are taken by your code and then search those graphs for lock inversions. Once problems are found we reduce the graphs to just the locks that cause the problem, stripping away complexity and exposing the details that let you remove the potential deadlock from your code. An example probably helps...
#include <windows.h>

CRITICAL_SECTION crit1;
CRITICAL_SECTION crit2;
CRITICAL_SECTION crit3;
CRITICAL_SECTION crit4;

void Sequence1()
{
   EnterCriticalSection(&crit1);
   EnterCriticalSection(&crit3);
   EnterCriticalSection(&crit4);
   EnterCriticalSection(&crit2);
   LeaveCriticalSection(&crit2);
   LeaveCriticalSection(&crit4);
   LeaveCriticalSection(&crit3);
   LeaveCriticalSection(&crit1);
}

void Sequence2()
{
   EnterCriticalSection(&crit1);
   EnterCriticalSection(&crit2);
   LeaveCriticalSection(&crit2);
   LeaveCriticalSection(&crit1);
}

void Inversion()
{
   EnterCriticalSection(&crit2);
   EnterCriticalSection(&crit1);
   LeaveCriticalSection(&crit1);
   LeaveCriticalSection(&crit2);
}

int main(int /*argc*/, char * /*argv[ ]*/)
{
   InitializeCriticalSection(&crit1);
   InitializeCriticalSection(&crit2);
   InitializeCriticalSection(&crit3);
   InitializeCriticalSection(&crit4);

   Sequence1();
   Sequence2();

   Inversion();

   DeleteCriticalSection(&crit4);
   DeleteCriticalSection(&crit3);
   DeleteCriticalSection(&crit2);
   DeleteCriticalSection(&crit1);

   return 0;
}
This is similar to the previous simple example, but Sequence1() involves more locks. The output from LIA is as follows:

****************New Log*****************
Target process has terminated
Process "C:\Reduction.exe" exit code: 0
Checking 10 locks in 9 lock acquisition sequences for inversions
Complete in: 5ms

Lock inversions detected!

Lock inversion in acquisition of locks 5 and 8
Primary lock acquisition sequence: 5 @ 27, 8 @ 30
Executed on thread: 1 [5208]
Secondary lock acquisition sequence: 8 @ 33, 5 @ 34
Executed on thread: 1 [5208]
---
Location: 27
C:\reduction.cpp(14) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 30
C:\reduction.cpp(17) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 33
C:\reduction.cpp(34) : Inversion
C:\reduction.cpp(50) : main
---
Location: 34
C:\reduction.cpp(35) : Inversion
C:\reduction.cpp(50) : main
---
Lock inversion in acquisition of locks 5 and 8
Primary lock acquisition sequence: 5 @ 31, 8 @ 32
Executed on thread: 1 [5208]
Secondary lock acquisition sequence: 8 @ 33, 5 @ 34
Executed on thread: 1 [5208]
---
Location: 31
C:\reduction.cpp(26) : Sequence2
C:\reduction.cpp(48) : main
---
Location: 32
C:\reduction.cpp(27) : Sequence2
C:\reduction.cpp(48) : main
---

Note that you are only being shown the locks involved in the lock inversion, crit1 and crit2. The actual raw data that LIA is using can sometimes be useful, though usually it's only really useful to us if you think you've found a bug!

You can see the raw, unreduced, data by passing the -raw command line switch to LID or LIA. With -raw the output from LIA is as follows:

****************New Log*****************
Target process has terminated
Process "C:\Reduction.exe" exit code: 0
Checking 10 locks in 9 lock acquisition sequences for inversions
Complete in: 5ms

Lock inversions detected!

Lock inversion in acquisition of locks 5 and 8
Primary lock acquisition sequence: 5 @ 27, 6 @ 28, 7 @ 29, 8 @ 30
Executed on thread: 1 [5964]
Secondary lock acquisition sequence: 8 @ 33, 5 @ 34
Executed on thread: 1 [5964]
---
Location: 27
C:\reduction.cpp(14) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 28
C:\reduction.cpp(15) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 29
C:\reduction.cpp(16) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 30
C:\reduction.cpp(17) : Sequence1
C:\reduction.cpp(47) : main
---
Location: 33
C:\reduction.cpp(34) : Inversion
C:\reduction.cpp(50) : main
---
Location: 34
C:\reduction.cpp(35) : Inversion
C:\reduction.cpp(50) : main
---
Lock inversion in acquisition of locks 5 and 8
Primary lock acquisition sequence: 5 @ 31, 8 @ 32
Executed on thread: 1 [5964]
Secondary lock acquisition sequence: 8 @ 33, 5 @ 34
Executed on thread: 1 [5964]
---
Location: 31
C:\reduction.cpp(26) : Sequence2
C:\reduction.cpp(48) : main
---
Location: 32
C:\reduction.cpp(27) : Sequence2
C:\reduction.cpp(48) : main
---
Lock inversion in acquisition of locks 8 and 5
Primary lock acquisition sequence: 8 @ 33, 5 @ 34
Executed on thread: 1 [5964]
Secondary lock acquisition sequence: 5 @ 27, 6 @ 28, 7 @ 29, 8 @ 30
Executed on thread: 1 [5964]
Secondary lock acquisition sequence: 5 @ 31, 8 @ 32
Executed on thread: 1 [5964]
---

As you can see this shows all four locks in Sequence1() and additionally shows a third inversion. If you look carefully at the extra inversion you'll see that it's simply the "other" view of the inversions that we already have. The data reduction process that the tools use is done in two steps. The first removes the "inverse" sequences, such as that third sequence in the output above. This means that we don't show a sequence as a primary sequence if we've already located it as a secondary sequence in another lock inversion. The second stage removes any locks not directly involved in the deadlock. You can play around with the data reduction using -reduce1 to remove the inverse sequences and -reduce2 to reduce each sequence to its key locks.

Whilst it's unlikely that you'll find the unreduced data of much interest, it's good to know that no matter how complicated your lock usage we'll reduce it down to show you exactly where you need to look to remove potential deadlocks.

Leave a comment

About this Entry

Finding lock inversions before they become deadlocks was the previous entry in this blog.

Save time debugging: ignore single threaded lock inversions is the next entry in this blog.

This is where we write about the development of Lock Explorer, a suite of tools for locating lock inversions, finding deadlocks before they happen and investigating lock usage, contention and performance in multi-threaded code.

Find recent content on the main index or look in the archives to find all content.