Finding lock inversions before they become deadlocks

| 0 Comments
As I mentioned before, deadlocks occur because of lock inversions, that is one thread is holding lock 1 and requires lock 2 and another thread is holding lock 2 and requires lock1.
TwoThreadsDeadlocked.png

Our tools help you find lock inversions in your code without requiring deadlocks to occur, all you need to do is run the code under our Lock Inversion Detector, LID, or our Lock Inversion Analyser, LIA.
Both tools work in a similar way, the only difference is that LIA does more work and pinpoints the exact call stacks that produce the lock inversions within your code. LID simply lists the number of lock inversions and brief details of which threads and locks were involved.

How do we detect lock inversions? We instrument your code as it runs and track lock manipulations. At present we only track critical section usage but we're planning to add new lock types, such as mutexes and also instrument events and waits. Note that we don't require source code for this but if you don't have source code then the reports generated from LIA are less useful - possibly just that a lock inversion IS present inside some third-party code.

As the Lock Inversion Detector runs we build lock acquisition graphs for each thread. We then compare these graphs and determine if any lock inversions are present.

Lets look at a simple example.
#include <windows.h>

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

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

void Sequence2()
{
   EnterCriticalSection(&crit3);
   LeaveCriticalSection(&crit3);
}

void Sequence3()
{
   EnterCriticalSection(&crit4);
   LeaveCriticalSection(&crit4);
}

void Sequence4()
{
   EnterCriticalSection(&crit2);
   LeaveCriticalSection(&crit2);
}

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

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

   Sequence1();

   EnterCriticalSection(&crit1);
   Sequence2();
   Sequence3();
   Sequence4();
   LeaveCriticalSection(&crit1);

   Sequence5();

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

   return 0;
}
Here we create four critical section objects, initialise them and then lock them in four different sequences. All of the sequences that involve locks 1 & 2 lock them in the same order and so no lock inversions are created.

If we build this example and run it under LID we will see the following output:

SimpleSequnceLID.png
The reason that LID shows 10 locks in 7 sequences rather than 4 locks in 4 sequences is that the runtime libraries that we link with use their own locks and LID tracks those as well as the locks that we create in our example.

The results from running under LIA is slightly different:

SimpleSequnceLIA.png
LIA has identified 9 sequences rather than LIDs 7. This is because LIA includes the precise location of the lock manipulation in the sequence details whereas LID, for example, counts sequences 1 and 4 as the same sequence.

If we introduce some lock inversions into the example we can see how the tools detect them for us.
#include <windows.h>

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

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

void Sequence2()
{
   EnterCriticalSection(&crit3);
   LeaveCriticalSection(&crit3);
}

void Sequence3()
{
   EnterCriticalSection(&crit4);
   LeaveCriticalSection(&crit4);
}

void Sequence4()
{
   EnterCriticalSection(&crit2);
   LeaveCriticalSection(&crit2);
}

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

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

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

void Sequence8Inversion()
{
   EnterCriticalSection(&crit3);
   EnterCriticalSection(&crit1);
   LeaveCriticalSection(&crit1);
   LeaveCriticalSection(&crit3);
}

void Sequence9Inversion()
{
   EnterCriticalSection(&crit4);
   EnterCriticalSection(&crit1);
   LeaveCriticalSection(&crit1);
   LeaveCriticalSection(&crit4);
}

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

   Sequence1();

   EnterCriticalSection(&crit1);
   Sequence2();
   Sequence3();
   Sequence4();
   LeaveCriticalSection(&crit1);

   Sequence5();

   Sequence6Inversion();
   Sequence7Inversion();
   Sequence8Inversion();
   Sequence9Inversion();

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

   return 0;
}
Note that the inversions acquire the locks in a different order. If Sequence1 was called from one thread and Sequence6Inversion() was called from another thread then a deadlock would be possible as one thread locks crit1 first and then tries to obtain crit2 and the other thread locks crit2 first and then tries to lock crit1.
TwoThreadsDeadlocked.png
LID produces the following report:

SingleThreadLockInversionLID.png

Note that LID gives you some information, it tells you that there ARE lock inversions, but doesn't tell you where. If you were running LID as part of your development process then this may well be enough for you. You could look at the last code change and work out where the bug is. It's far faster to use LIA though.

The output from LIA is much more comprehensive, so we'll look at the log file that is generated instead of a screen shot. The full log can be found here. We'll look at pieces of it as we go along. First lets look at the details we get for the first lock inversion that is detected.

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

Lock inversions detected!

Lock inversion in acquisition of locks 5 and 6
Primary lock acquisition sequence: 5 @ 27, 6 @ 28
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 35, 5 @ 36
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 37, 5 @ 38
Executed on thread: 1 [3972]
---
Location: 27
C:\singlethreadlockinversion.cpp(14) : Sequence1
C:\singlethreadlockinversion.cpp(85) : main
---
Location: 28
C:\singlethreadlockinversion.cpp(15) : Sequence1
C:\singlethreadlockinversion.cpp(85) : main
---
Location: 35
C:\singlethreadlockinversion.cpp(48) : Sequence6Inversion
C:\singlethreadlockinversion.cpp(95) : main
---
Location: 36
C:\singlethreadlockinversion.cpp(49) : Sequence6Inversion
C:\singlethreadlockinversion.cpp(95) : main
---
Location: 37
C:\singlethreadlockinversion.cpp(56) : Sequence7Inversion
C:\singlethreadlockinversion.cpp(96) : main
---
Location: 38
C:\singlethreadlockinversion.cpp(57) : Sequence7Inversion
C:\singlethreadlockinversion.cpp(96) : main
---

Apart from showing more inversions than LID (for the same reasons that I explained above), the main difference between LID and LIA in this case is that LIA is displaying the exact lines where the lock inversion occurs.

This first lock inversion shows the problems caused by Sequence6Inversion() and Sequence7Inversion() where crit1 and crit2 are acquired in different orders.

Lock inversion in acquisition of locks 5 and 6
Primary lock acquisition sequence: 5 @ 27, 6 @ 28
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 35, 5 @ 36
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 37, 5 @ 38
Executed on thread: 1 [3972]

You can see from the following location listing that you get the exact line number of where the lock is taken.

---
Location: 27
C:\singlethreadlockinversion.cpp(14) : Sequence1
C:\singlethreadlockinversion.cpp(85) : main
---
Location: 28
C:\singlethreadlockinversion.cpp(15) : Sequence1
C:\singlethreadlockinversion.cpp(85) : main
---
Location: 35
C:\singlethreadlockinversion.cpp(48) : Sequence6Inversion
C:\singlethreadlockinversion.cpp(95) : main
---
Location: 36
C:\singlethreadlockinversion.cpp(49) : Sequence6Inversion
C:\singlethreadlockinversion.cpp(95) : main
---
Location: 37
C:\singlethreadlockinversion.cpp(56) : Sequence7Inversion
C:\singlethreadlockinversion.cpp(96) : main
---
Location: 38
C:\singlethreadlockinversion.cpp(57) : Sequence7Inversion
C:\singlethreadlockinversion.cpp(96) : main
---

The next two lock inversions are due to Sequence4 and Sequence5. Both of these also acquire crit1 before crit2 and therefore Sequence6Inversion() and Sequence7Inversion() also create problems here. You will see that location information is only displayed once, the first time that it is needed in a lock inversion, so we don't duplicate the call stacks for locations 35 and 36. The log will contain one copy of each location used in any of the sequences; when the call stacks are deeper you'll be happy for this optimisation as it reduces the size of the log file considerably.

Lock inversion in acquisition of locks 5 and 6
Primary lock acquisition sequence: 5 @ 29, 6 @ 32
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 35, 5 @ 36
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 37, 5 @ 38
Executed on thread: 1 [3972]
---
Location: 29
C:\singlethreadlockinversion.cpp(87) : main
---
Location: 32
C:\singlethreadlockinversion.cpp(34) : Sequence4
C:\singlethreadlockinversion.cpp(90) : main
---
Lock inversion in acquisition of locks 5 and 6
Primary lock acquisition sequence: 5 @ 33, 6 @ 34
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 35, 5 @ 36
Executed on thread: 1 [3972]
Secondary lock acquisition sequence: 6 @ 37, 5 @ 38
Executed on thread: 1 [3972]
---
Location: 33
C:\singlethreadlockinversion.cpp(40) : Sequence5
C:\singlethreadlockinversion.cpp(93) : main
---
Location: 34
C:\singlethreadlockinversion.cpp(41) : Sequence5
C:\singlethreadlockinversion.cpp(93) : main
---

The final two pinpoint the problem caused by Sequence3() and Sequence8Inversion() and by Sequence4() and Sequence9Inversion().

Hopefully this introduction has demonstrated the power and simplicity of using both LID and LIA. Later tutorials will cover more advanced usage.

Leave a comment

About this Entry

Where do deadlocks come from? was the previous entry in this blog.

Finding deadlocks fast: data reduction helps pinpoint errors 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.