Spin Locks

Spin Locks

To help you synchronize access to shared data in the symmetric multiprocessing world of Windows XP, the kernel lets you define any number of spin lock objects. To acquire a spin lock, code on one CPU executes an atomic operation that tests and then sets a memory variable in such a way that no other CPU can access the variable until the operation completes. If the test indicates that the lock was previously free, the program continues. If the test indicates that the lock was previously held, the program repeats the test-and-set in a tight loop: it spins. Eventually the owner releases the lock by resetting the variable, whereupon one of the waiting CPUs test-and-set operations will report the lock as free.

Figure 4-3 illustrates the concept of using a spin lock. Suppose we have some resource that might be used simultaneously on two different CPUs. To make the example concrete, imagine that the resource is the LIST_ENTRY cell that anchors a linked list of IRPs. The list might be accessed by one or more dispatch routines, a cancel routine, a DPC routine, and perhaps others as well. Any number of these routines might be executing simultaneously on different CPUs and trying to modify the list anchor. To prevent chaos, we associate a spin lock with this resource.

Figure 4-3. Using a spin lock to guard a shared resource.

Suppose now that code executing on CPU A wants to access the shared resource at time t1. It acquires the spin lock and begins its access. Shortly afterward, at time t2, code executing on CPU B also wants to access the same resource. The CPU-B program tries to acquire the spin lock. Since CPU A currently owns the spin lock, CPU B spins in a tight loop, continually checking and rechecking the spin lock to see whether it has become free. When CPU A releases the lock at time t3, CPU B finds the lock free and claims it. Then CPU B has unfettered access to the resource. Finally, at time t4, CPU B finishes its access and releases the lock.

I want to be very clear about how a spin lock and a shared resource come to be associated. We make the association when we design the driver. We decide that we will access the resource only while owning the spin lock. The operating system isn t aware of our decision. Furthermore, we can define as many spin locks as we want, to guard as many shared resources as we want.

Some Facts About Spin Locks

You need to know several important facts about spin locks. First of all, if a CPU already owns a spin lock and tries to obtain it a second time, the CPU will deadlock. No usage counter or owner identifier is associated with a spin lock; somebody either owns the lock or not. If you try to acquire the lock when it s owned, you ll wait until the owner releases it. If your CPU happens to already be the owner, the code that would release the lock can never execute because you re spinning in a tight loop testing and setting the lock variable.

CAUTION
You can certainly avoid the deadlock that occurs when a CPU tries to acquire a spin lock it already owns by following this rule: make sure that the subroutine that claims the lock releases it and never tries to claim it twice, and then don t call any other subroutine while you own the lock. There s no policeman in the operating system to ensure you don t call other subroutines it s just an engineering rule of thumb that will help you avoid an inadvertent mistake. The danger you re guarding against is that you (or some maintenance programmer who follows in your footsteps) might forget that you ve already claimed a certain spin lock. I ll tell you about an ugly exception to this salutary rule in Chapter 5, when I discuss IRP cancel routines.

In addition, acquiring a spin lock raises the IRQL to DISPATCH_LEVEL automatically. Consequently, code that acquires a lock must be in nonpaged memory and must not block the thread in which it runs. (There is an exception in Windows XP and later systems. KeAcquireInterruptSpinLock raises the IRQL to the DIRQL for an interrupt and claims the spin lock associated with the interrupt.)

As an obvious corollary of the previous fact, you can request a spin lock only when you re running at or below DISPATCH_LEVEL. Internally, the kernel is able to acquire spin locks at an IRQL higher than DISPATCH_LEVEL, but you and I are unable to accomplish that feat.

Another fact about spin locks is that very little useful work occurs on a CPU that s waiting for a spin lock. The spinning happens at DISPATCH_LEVEL with interrupts enabled, so a CPU that s waiting for a spin lock can service hardware interrupts. But to avoid harming performance, you need to minimize the amount of work you do while holding a spin lock that some other CPU is likely to want.

Two CPUs can simultaneously hold two different spin locks, by the way. This arrangement makes sense: you associate a spin lock with a certain shared resource, or some collection of shared resources. There s no reason to hold up processing related to different resources protected by different spin locks.

As it happens, there are separate uniprocessor and multiprocessor kernels. The Windows XP setup program decides which kernel to install after inspecting the computer. The multiprocessor kernel implements spin locks as I ve just described. The uniprocessor kernel realizes, however, that another CPU can t be in the picture, so it implements spin locks a bit more simply. On a uniprocessor system, acquiring a spin lock raises the IRQL to DISPATCH_LEVELand does nothing else. Do you see how you still get the synchronization benefit from claiming the so-called lock in this case? For some piece of code to attempt to claim the same spin lock (or any other spin lock, actually, but that s not the point here), it would have to be running at or below DISPATCH_LEVEL you can request a lock starting at or below DISPATCH_LEVEL only. But we already know that s impossible because, once you re above PASSIVE_LEVEL, you can t be interrupted by any other activity that would run at the same or a lower IRQL. Q., as we used to say in my high school geometry class, E.D.

Working with Spin Locks

To use a spin lock explicitly, allocate storage for a KSPIN_LOCK object in nonpaged memory. Then call KeInitializeSpinLock to initialize the object. Later, while running at or below DISPATCH_LEVEL, acquire the lock, perform the work that needs to be protected from interference, and then release the lock. For example, suppose your device extension contains a spin lock named QLock that you use for guarding access to a special IRP queue you ve set up. You ll initialize this lock in your AddDevice function:

typedef struct _DEVICE_EXTENSION {  KSPIN_LOCK QLock; } DEVICE_EXTENSION, *PDEVICE_EXTENSION;  NTSTATUS AddDevice(...) {  PDEVICE_EXTENSION pdx = ...; KeInitializeSpinLock(&pdx->QLock);  }

Elsewhere in your driver, say in the dispatch function for some type of IRP, you can claim (and quickly release) the lock around some queue manipulation that you need to perform. Note that this function must be in nonpaged memory because it executes for a period of time at an elevated IRQL.

NTSTATUS DispatchSomething(...) { KIRQL oldirql; PDEVICE_EXTENSION pdx = ...; 
 KeAcquireSpinLock(&pdx->QLock, &oldirql);  
 KeReleaseSpinLock(&pdx->QLock, oldirql); }

1. When KeAcquireSpinLock acquires the spin lock, it also raises IRQL to DISPATCH_LEVEL and returns the current (that is, preacquisition) level in the variable to which the second argument points.

2. When KeReleaseSpinLock releases the spin lock, it also lowers IRQL back to the value specified in the second argument.

If you know you re already executing at DISPATCH_LEVEL, you can save a little time by calling two special routines. This technique is appropriate, for example, in DPC, StartIo, and other driver routines that execute at DISPATCH_LEVEL:

KeAcquireSpinLockAtDpcLevel(&pdx->QLock);  KeReleaseSpinLockFromDpcLevel(&pdx->QLock);

Queued Spin Locks

Windows XP introduces a new type of spin lock, called an in-stack queued spin lock, that has a more efficient implementation than a regular spin lock. The mechanics of using this new kind of lock are a bit different from what I just described. You still allocate a KSPIN_LOCK object in nonpaged memory to which all relevant parts of your driver have access, and you still initialize it by calling KeAcquireSpinLock. To acquire and release the lock, however, you use code like the following:

 
KLOCK_QUEUE_HANDLE qh; 
KeAcquireInStackQueuedSpinLock(&pdx->QLock, &qh);  
KeReleaseInStackQueuedSpinLock(&qh);

1. The KLOCK_QUEUE_HANDLE structure is opaque you re not supposed to know what it contains, but you do have to reserve storage for it. The best way to do that is to define an automatic variable (hence the in-stack part of the name).

2. Call KeAcquireInStackQueuedSpinLock instead of KeAcquireSpinLock to acquire the lock, and supply the address of the KLOCK_QUEUE_HANDLE object as the second argument.

3. Call KeReleaseInStackQueuedSpinLock instead of KeReleaseSpinLock to release the lock.

The reason an in-stack queued spin lock is more efficient relates to the performance impact of a standard spin lock. With a standard spin lock, each CPU that is contending for ownership constantly modifies the same memory location. Each modification requires every contending CPU to reload the same dirty cache line. A queued spin lock, introduced for internal use in Windows 2000, avoids this adverse effect by cleverly using interlocked exchange and compare-exchange operations to track users and waiters for a lock. A waiting CPU continually reads (but does not write) a unique memory location. A CPU that releases a lock alters the memory variable on which the next waiter is spinning.

Internal queued spin locks can t be directly used by driver code because they rely on a fixed-size table of lock pointers to which drivers don t have access. Windows XP added the in-stack queued spin lock, which relies on an automatic variable instead of the fixed-size table.

In addition to the two routines I showed you for acquiring and releasing this new kind of spin lock, you can also use two other routines if you know you re already executing at DISPATCH_LEVEL: KeAcquireInStackQueuedSpinLockAtDpcLevel and KeReleaseInStackQueuedSpinLockFromDpcLevel. (Try spelling those names three times fast!)

NOTE
Because Windows versions earlier than XP don t support the in-stack queued spin lock or interrupt spin lock routines, you can t directly call them in a driver intended to be binary portable between versions. The SPINLOCK sample driver shows how to make a run-time decision to use the newer spin locks under XP and the old spin locks otherwise.