Numbered Queued Spinlocks in the WRK

By Alexander Schmidt

In a recent post, we covered the implementation of in-stack queued spinlocks, the recommended method to use queued spinlocks in drivers. In this article, we would like to extend the discussion to a second class of queued spinlocks: numbered queued spinlocks. These well-known locks use per processor, pre-allocated memory to store the processor's queue item. In this article, we will give a short overview over the existing queued spinlocks in the WRK, how they are initialized and how they are used.

The following queued spinlocks are defined in the WRK (public\sdk\inc\ntkeapi.h:128). Please note that this definition is contained in every Windows Driver Development Kit (WDK) as well.

typedef enum _KSPIN_LOCK_QUEUE_NUMBER {
    LockQueueDispatcherLock,
    LockQueueUnusedSpare1,
    LockQueuePfnLock,
    LockQueueSystemSpaceLock,
    LockQueueVacbLock,
    LockQueueMasterLock,
    LockQueueNonPagedPoolLock,
    LockQueueIoCancelLock,
    LockQueueWorkQueueLock,
    LockQueueIoVpbLock,
    LockQueueIoDatabaseLock,
    LockQueueIoCompletionLock,
    LockQueueNtfsStructLock,
    LockQueueAfdWorkQueueLock,
    LockQueueBcbLock,
    LockQueueMmNonPagedPoolLock,
    LockQueueUnusedSpare16,
    LockQueueTimerTableLock,
    LockQueueMaximumLock = LockQueueTimerTableLock + LOCK_QUEUE_TIMER_TABLE_LOCKS
} KSPIN_LOCK_QUEUE_NUMBER, *PKSPIN_LOCK_QUEUE_NUMBER;

The processor control block (KPRCB) contains a field LockQueue (base\ntos\inc\i386.h:1109, for x86 platforms), which is an array of LockQueueMaximumLock KSPIN_LOCK_QUEUE elements. The KSPIN_LOCK_QUEUE structure has the following layout:

typedef struct _KSPIN_LOCK_QUEUE
{
    struct _KSPIN_LOCK_QUEUE * volatile Next;
    PKSPIN_LOCK volatile Lock;
} KSPIN_LOCK_QUEUE, *PKSPIN_LOCK_QUEUE;

The first field (Next) is used for queueing up multiple queue items when multiple processors compete for a spinlock. The Lock field is pointer to the spinlock that should be acquired. When using numbered spinlocks, this field must be initialized prior to invoking any acquire/release function, as otherwise the mapping from the queue number to the actual lock wouldn't work. The WRK therefore initializes the set of numbered queued spinlocks upon system initalization in the KiInitSpinLocks (base\ntos\ke\kiinit.c:131), for which we show an excerpt here:

    // further function code omitted here ...  

    Prcb->LockQueue[LockQueueDispatcherLock].Next = NULL;
    Prcb->LockQueue[LockQueueDispatcherLock].Lock = &KiDispatcherLock;

    Prcb->LockQueue[LockQueueUnusedSpare1].Next = NULL;
    Prcb->LockQueue[LockQueueUnusedSpare1].Lock = NULL;

    Prcb->LockQueue[LockQueuePfnLock].Next = NULL;
    Prcb->LockQueue[LockQueuePfnLock].Lock = &MmPfnLock;

    // further function code omitted here ...

To acquire a queued spinlock the following API can be used:

KIRQL
FASTCALL
KeAcquireQueuedSpinLock (
    __in KSPIN_LOCK_QUEUE_NUMBER Number
    );

That is, knowing the queue number is enough information to acquire the queued spinlock on the current processor. The acquire and release process is the same for in-stack and numbered queued spinlocks, which we covered here. For the sake of completeness, we present the mapping betwen spinlock queue number and the actual lock here:

• LockQueueDispatcherLock - KiDispatcherLock
• LockQueuePfnLock - MmPfnLock
• LockQueueSystemSpaceLock - MmSystemSpaceLock
• LockQueueBcbLock - CcBcbSpinLock
• LockQueueMasterLock - CcMasterSpinLock
• LockQueueNonPagedPoolLock - NonPagedPoolLock
• LockQueueWorkQueueLock - CcWorkQueueSpinLock
• LockQueueVacbLock - CcVacbSpinLock
• LockQueueIoCancelLock - IopCancelSpinLock
• LockQueueIoVpbLock - IopVpbSpinLock
• LockQueueIoDatabaseLock - IopDatabaseLock
• LockQueueIoCompletionLock - IopCompletionLock
• LockQueueNtfsStructLock - NtfsStructLock
• LockQueueAfdWorkQueueLock - AfdWorkQueueSpinLock
• LockQueueMmNonPagedPoolLock - MmNonPagedPoolLock

Please note the two locks MmNonPagedPoolLock and NonPagedPoolLock. It's interesting that they share the same name except for the prefix. But we will cover them in a later post.

The question about numbered queued spinlock that remains is that if they are basically the same as in-stack queued spinlocks, why are they used anyway? Well, the ultimate answer can only be given by a responsible kernel developer. However, in our opinion, the reason for the "invention" of numbered queued spinlocks has its cause probably in software evolution. When queued spinlocks were introduced to the kernel, most of the important, high-contention locks were transformed from ordinary spinlocks to queued spinlocks. Unfortunately the API for queued spinlocks is different than the spinlock version, as the queued spinlocks require a lock handle for the release operation. With providing the numbered queue indirection, storing the handle and refactoring the code is reduced to a minimum (as for changing the signature of the acquire/release functions) and more or less transparent for the rest of the kernel. But that's just my opinion. If you do not agree on that, please let us know 🙂

Comments