|
|
|
Deadlock Detection monitors the driver's use of resources which need to be locked — spin locks, mutexes, and fast mutexes. This Driver Verifier option will detect code logic that has the potential to cause a deadlock at some future point.
The Deadlock Detection option of Driver Verifier, along with the !deadlock kernel debugger extension, is an effective tool for making sure your code avoids poor use of these resources.
This Driver Verifier option is only available in Windows XP and later.
A deadlock is caused when two or more threads come into conflict over some resource, in such a way that no execution is possible.
The most common form of deadlock occurs when two or more threads wait for a resource that is owned by the other thread. This is illustrated as follows:
| Thread 1 | Thread 2 |
|---|---|
| Takes Lock A | Takes Lock B |
| Requests Lock B | Requests Lock A |
If both sequences happen at the same time, Thread 1 will never get Lock B because it is owned by Thread 2, and Thread 2 will never get Lock A because it is owned by Thread 1. At best this causes the threads involved to halt, and at worst causes the system to stop responding.
Deadlocks are not limited to two threads and two resources. Three-way deadlocks between three threads and three locks are common — and even five-part or six-part deadlocks occur occasionally. These deadlocks require a certain degree of "bad luck" since they rely on a number of things happening simultaneously. However, the farther apart the lock acquisitions are, the more likely these become.
Single-thread deadlocks can occur when a thread attempts to take a lock that it already owns.
The common denominator among all deadlocks is that lock hierarchy is not respected. Whenever it is necessary to have more than one lock acquired at a time, each lock should have a clear precedence. If A is taken before B at one point and B before C at another, the hierarchy is A-B-C. This means that A must never be acquired after B or C, and B must not be acquired after A.
Lock hierarchy should be followed even when there is no possibility of a deadlock, since in the process of maintaining the code it will be easy for a deadlock to be accidentally introduced.
The most unambiguous deadlocks are the result of owned resources. These include spin locks, mutexes, fast mutexes, and ERESOURCEs.
Resources that are signaled rather than acquired (such as events and LPC ports) tend to cause much more ambiguous deadlocks. It is of course possible, and all too common, for code to misuse these resources in such a way that two threads will end up waiting on each other indefinitely. However, since these resources are not actually owned by any one thread, it is not possible to identify the delinquent thread with any degree of certainty.
The Deadlock Detection option of Driver Verifier looks for potential deadlocks involving spin locks, mutexes, and fast mutexes. It does not monitor the use of ERESOURCEs, nor does it monitor the use of nonowned resources.
Driver Verifier's Deadlock Detection routines find lock hierarchy violations that are not necessarily simultaneous. Most of the time, these violations identify code paths that will deadlock when given the chance.
To find potential deadlocks, Driver Verifier builds a graph of resource acquisition order and checks for loops. If you were to create a node for each resource, and draw an arrow any time one lock is acquired before another, then path loops would represent lock hierarchy violations.
Driver Verifier will issue a bug check when one of these violations is discovered. This will happen before any actual deadlocks occur.
Note Even if the conflicting code paths can never happen simultaneously, they should still be rewritten if they involve lock hierarchy violations. Such code is a "deadlock waiting to happen" that could cause real deadlocks if the code is rewritten slightly.
When Deadlock Detection finds a violation, it will issue bug check 0xC4. The first parameter of this bug check will indicate the exact violation. Possible violations include:
See Bug Check 0xC4 (DRIVER_VERIFIER_DETECTED_VIOLATION) for a list of the bug check parameters.
Once Deadlock Detection finds a violation, the !deadlock kernel debugger extension can be used to investigate exactly what has occurred. It can display the lock hierarchy topology as well as the call stacks for each thread at the time the locks were originally acquired.
For best results, the driver in question should be running on a checked build of Windows, since that allows the kernel to obtain more complete run-time stack traces.
There is a detailed example of the !deadlock extension, as well as general information about debugger extensions, in the documentation in the Debugging Tools for Windows package. See Debugging Tools for NT-Based Operating Systems for details.
The Deadlock Detection option can be activated by using the Driver Verifier Manager graphical interface or the verifier.exe command line. This activation will take effect after the next boot. See Selecting Driver Verifier Options for details.
The Deadlock Detection option is not used for graphics drivers, since display drivers and kernel-mode printer drivers cannot directly own resources. If selected, it has no effect.