Kernel Mustard

Cancel-safe queues are a fantastic addition to Windows from back in the XP timeframe, and I have come to rely on them in my drivers. There are a couple of important extra rules that aren’t reflected in the documentation that you should be aware of, though.

Rule #1

If you read the documentation for IoCsqInsertIrp or IoCsqInsertIrpEx, you’ll find that the routine can be called at <= DISPATCH_LEVEL. While this is true, you cannot call it while holding a spin lock.

To see why this is true, consider the case where a dispatch routine receives an IRP, and before it can queue the IRP, another thread swoops in and cancels it. If this happens, someone should call the cancel routine, and that someone is IoCsqInsertIrp. It eventually calls CsqCompleteCanceledIrp, which calls IoCompleteRequest with a status of STATUS_CANCELLED.

(Note the double-L. Very bad news for a guy who can’t spell in the first place. I’ll be looking that one up for the rest of my life.)

The rest should be obvious: it is in fact illegal to call IoCompleteRequest while holding a lock, which is exactly what winds up happening in this case. Therefore, you can’t call IoCsqInsertIrp or IoCsqInsertIrpEx while holding a lock.

Rule #2

The second rule is related to when IoCsqInsertIrpEx marks an IRP pending. The rule is simple: If the supplied CsqInsertIrpEx callback returns STATUS_SUCCESS, the IRP is marked pending. Otherwise, it’s not.

In the case of IoCsqInsertIrp, the IRP is unconditionally marked pending. This is even quasi-documented by the WDK cancel sample, but the corresponding startio sample doesn’t say anything about the behavior of IoCsqInsertIrpEx, which I had always assumed was the same based on that comment. It’s not.

Neither of these rules show up in the docs (at least as of now), so hopefully this will save some confusion down the road.

To continue on yesterday’s discussion of interlocked lists, let’s explore the nature of the interlocking done by the ExInterlocked* APIs. The ExInterlockedRemoveHeadList documentation says the following about its spin lock argument:

You must use this spin lock only with the ExInterlockedXxxList routines.

The documentation page provides a hint as to why this is the case:

The ExInterlockedRemoveHeadList routine can be called at any IRQL.

The reason that this function can be called from any IRQL is that the function acquires the spin lock at the highest IRQL in the system. To understand why this is important, we have to examine another kind of race condition – priority inversion deadlocks.

Recall that the kernel operates on a prioritization scheme implemented using IRQLs. Normal tasks run as PASSIVE_LEVEL, drivers run at some higher IRQL (called DIRQL), and other tasks happen at various points in between. (See the DDK or any introductory driver book for more information on this.) Drivers typically acquire spin locks at DISPATCH_LEVEL, which is below all DIRQLs.

A priority inversion deadlock can happen if a driver acquires a spin lock at DISPATCH_LEVEL, and while holding that lock, is interrupted by hardware. An interrupt service routine is invoked on behalf of the hardware, and runs at DIRQL. If the ISR tries to acquire that same lock, a deadlock will occur: the ISR will spin forever, waiting for the driver to release the lock, but the driver is stuck suspended until the ISR returns.

With that in mind, let’s come back to the ExInterlocked* functions. Suppose you try to acquire the spin lock at DISPATCH_LEVEL (with KeAcquireSpinLock), perhaps for the purpose of removing an entry from the list. Suppose that your hardware interrupts in the middle of your operation, and your ISR lands on the same CPU you were just operating on. If you then call something like ExInterlockedInsertHeadList, you’ll deadlock. The lower-priority routine will own the lock, and the higher-priority routine will wait forever trying to acquire it.

The solution is to follow the documentation’s advice and always use that spin lock exclusively with ExInterlocked* routines. When you use ExInterlockedInsertHeadList from any routine (not just an ISR), it raises the IRQL to the highest IRQL possible on that CPU, which masks out everything else in your driver – even ISRs. This prevents the priority inversion.

For what it’s worth, the documentation used to say something like ExInterlocked routines are only interlocked with respect to each other. The new wording says less but is much clearer in my opinion.

UPDATE: clarified wording to prevent deliberate mis-interpretation.