Keeping ExInterlocked* operations interlocked
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.
November 6th, 2006 at 9:29 pm
[…] A few days ago I wrote about how to keep ExInterlocked*() operations interlocked. Well, the same thing goes for NDIS drivers. […]
December 18th, 2007 at 6:25 am
i use ExInterlockedInsertHeadList for get a pointer(char *),it’s address is not changed ,but the content is destoryed,
i cant understand the reuslt very much
December 18th, 2007 at 9:52 am
Sounds to me like memory corruption. Try testing your driver under PREfast and/or Static Driver Verifier. They’re good at finding stuff like this.