Windows System Software -- Consulting, Training, Development -- Unique Expertise, Guaranteed Results

Introducing Reader/Writer Spin Locks

I regularly enjoy teasing my file system developer colleagues over the pain they suffer about whether some structure should be stored in paged pool or nonpaged pool or exactly which type of locking primitive they should use for a particular task.  “You should switch to writing device drivers,” I tell them.  “It’s much easier. In the land of device drivers, all pool is nonpaged and all locks are spin.”

It’s plain fact that the life of a device driver writer is easy in some ways.  However, I do admit that sometimes, just sometimes, I get a bit jealous over the variety of locking choices available to devs who never have to be concerned about running at IRQL DISPATCH_LEVEL or higher.  Over the years, I’ve particularly lusted over ERESOURCES.

ERESOURCES are locks that can be acquired in either shared mode or exclusive mode.  When acquired shared, the lock allows multiple threads to simultaneously read from a data area.  When acquired exclusive, the lock ensures that there’s only one accessor to a data area and thus allows the data to be updated atomically.  Because ERESOURCES allow multiple simultaneous readers of a given data area but only a single writer, this category of lock is most often referred to as a reader/writer lock.

One problem with ERESOURCES is that they can only be used in code running at less than IRQL DISPATCH_LEVEL.  That pretty much leaves them out of contention as a possible solution for most device driver work.  And there hasn’t been any sort of reader/writer lock documented as being available for use at IRQL DISPATCH_LEVEL.  That is, there hasn’t been one until the introduction of the WDK for Windows 8.

Reader/Writer Spin Locks

The WDK for Windows 8 tells us that starting in Vista SP1, Windows includes support for Reader/Writer Spin Locks.  These locks are just what their name implies: they are spin locks that can be acquired in either shared mode (for reading, but not modifying, shared data) or exclusive mode (for reading and modifying shared data).  Because they’re spin locks, they can be acquired at IRQLs less than or equal to DISPATCH_LEVEL.

Reader/Writer Spin Locks are wonderful additions to the driver writer’s tool chest.  Here at OSR, we’ve been using them on OS versions as early as Windows 7 without any problem.  Using Reader/Writer Spin Locks keeps us from having to choose between (a) acquiring a “regular” Spin Lock when you want to read some data, thereby guaranteeing data integrity but blocking anyone else who might simultaneously want to read that same data, and (b) acquiring no lock at all to read the data, thus risking data inconsistency due to the possibility that the data could be changed while you’re in the process of reading it.

Reader/Writer Spin Locks can be useful in all sorts of situations.  Consider the case when you have a block of statistics.  Prior to the introduction of Reader/Writer Spin Locks you would guard the structure holding those statistics with a traditional Spin Lock.  That means that only one thread could access the statistics at a time, regardless of whether that thread wanted to read or update those statistics.  With Reader/Writer Spin Locks, however, when you just want to read the statistics you would acquire the lock shared by calling ExAcquireSpinLockShared.  While you’re holding the lock shared, other threads can also acquire the lock shared and simultaneously read the data.  When you need to update the statistics, you acquire the lock exclusive by calling ExAcquireSpinLockExclusive.  This blocks all other acquisitions of the lock, and once the lock is granted allows you exclusive access to the statistics so you can perform your update.

Acquiring and Releasing Reader/Writer Spin Locks

There are a few interesting things about the implementation of Reader/Writer Spin Locks that are worthy of note.  First, notice that the functions are part of the Executive and not the Kernel.   So, instead of calling, for example, KeAcquireSpinLock as we’ve been used to, the functions for Reader/Writer Spin Locks are ExAcquireSpinLockXxxx.  Also, note that the data type for Reader/Writer Spin Locks is an EX_SPIN_LOCK, as opposed to the KSPIN_LOCK used for traditional Spin Locks.  Yay!  Let’s hear it for strong data typing.  You must allocate space for the EX_SPIN_LOCK structure in nonpaged memory.  Prior to the first use of a Reader/Writer Spin Lock you’re required to initialize the EX_SPIN_LOCK by setting it to zero.

Here’s an example of the definition of a Reader/Writer Spin Lock in a driver’s device context:

Note that this satisfies the requirement for the lock being in nonpaged memory because a driver’s device context is always stored in nonpaged memory.  You would initialize that lock prior to its first use by simply setting its value to zero:

The function call you use to acquire the Reader/Writer Spin Lock indicates whether you want to acquire that lock in shared or exclusive mode.  To acquire a Reader/Writer Spin Lock in shared mode call the following function:

The prototype for the function to acquire a Reader/Writer Spin Lock in exclusive mode is similar:

As with traditional Spin Locks, there are ExAcquireSpinLock SharedAtDpcLevel and ExAcquireSpinLockExclusiveAtDpcLevel functions that you can optionally use if you know in advance that you’re code will always be running at IRQL DISPATCH_LEVEL when you attempt to acquire the lock.  This would be the case, for example, when you acquire a Reader/Writer Spin Lock from a DPC.  These functions provide the small optimization of assuming the current IRQL is already set and not calling KeRaiseIRQL to raise the IRQL to DISPATCH_LEVEL before attempting to acquire the lock.

The function you call to release a Reader/Writer Spin Lock depends on the mode in which you acquired the lock.  If you acquired the lock shared, you would call ExReleaseSpinLock Shared, which has the following prototype:

Similarly, to release a lock you’ve acquired in exclusive mode, you callthe following function:

If you acquired the lock with one of the ExAcquireSpinLockXxxAt DpcLevel calls, you must release the lock by calling the matching ExReleaseSpinLockXxxxFromDpcLevel function.  Note the acquire call is “AtDpcLevel” and the release call is “FromDpcLevel”, thus preserving the naming pattern established by the traditional Spin Lock functions.

Finally, there’s a function that lets you attempt to “promote” to exclusive mode a Reader/Writer Spin Lock that you’re holding in shared mode.  The prototype for this function is:

This function returns TRUE if the lock was successfully promoted from shared mode to exclusive mode, and FALSE otherwise.  The promotion from shared to exclusive will only work if no other threads are holding the lock shared and there are no threads waiting to acquire the lock exclusive.  One thing that’s easy to overlook whenever you use ExTryToConvertSharedSpinLock Exclusive is that you must call the correct function based on the mode of the lock when you release it.  In other words, if your call to ExTryToConvertSharedSpinLockExclusive succeeds, you hold the lock in exclusive mode, and therefore must release it by calling ExReleaseSpinLockExclusive.  Likewise, if your call to ExTryToConvertSharedSpinLockExclusive fails you still own the lock in shared mode, and must call ExReleaseSpinLockShared to release it.

Having to know the mode in which you’re holding the Reader/Writer Spin Lock so you can use the matching call to release it is annoying. Some people might claim it provides nice built-in documentation, but all I see is a built-in opportunity for a bug or a cut/paste error.  When you release an ERESOURCE, you simply call a common release function and the function knows if you were holding the lock shared or exclusive.  Perhaps that’s not really a fair comparison, because ERESOURCES have much more overhead than Reader/Writer Spin Locks.  However, even given the low cost algorithm Windows uses for Reader/Writer Spin Locks, the release function could in fact know whether the lock was currently held shared or exclusive and just “do the right thing.”  See the sidebar, Why Not a Single Function for Release at the conclusion of this article for an extended discussion of why there isn’t a single release function.

Why Not a Single Function for Release?
When you want to release a Reader/Writer Spin Lock, you have to call the function that matches the mode in which you’re holding the lock. If you’re holding the lock shared, you need to call ExReleaseSpinLockShared. If you’re holding it exclusive, you need to call ExReleaseSpinLockExclusive. Screw up and you screw up the lock. It’s dumb, if you ask me. Just another unnecessary opportunity to create a bug.

So why don’t we have a common release function for Reader/Writer Spin Locks? Well, one reason is almost certainly the desire to keep the overhead for releasing locks as absolutely low as possible. But I suspect the real reason is rooted in history. If you look at WDM.H, you’ll see that the traditional (non-reader/writer) Spin Locks all have alternate names that start with Ex instead of Ke:

I bet you didn’t know that! These executive names for the kernel spin lock functions have in fact been defined since the earliest days of Windows NT. And now that we have Reader/Writer Spin Locks, if we wanted to have a common function for releasing the lock without regard to whether we were holding it shared or exclusive, what would we name that function? Well, if we were to follow the current naming pattern you would probably want to name that function ExReleaseSpinLock. But, oooops! We already have a function with that name. And if we named it something out of the pattern such as ExReleaseReaderWriterSpinLock, that would just be an opportunity for developers to create a bug by accidentally coding ExReleaseSpinLock anyhow. Perhaps having to know the mode that you’re holding the lock so you can call the appropriate function to release it isn’t so bad after all. Oh well, whatever, never mind.

sidebar_image


Usage Details

Enough about syntax and calling patterns.  Let’s now turn our attention to the details of how you use these locks.

You acquire Reader/Writer Spin Locks from code running at IRQL DISPATCH_LEVEL or lower.  Regardless of the mode in which the lock is acquired, there is no timeout on the acquisition attempt and you don’t return from the call until the lock has been acquired.  When you do return, you’re holding the lock and your thread is running at IRQL DISPATCH_LEVEL.  There are no functions available that attempt to acquire the lock and return without waiting if the lock is not immediately available.

It should really go without saying but I’m going to say it anyways:  Reader/Writer Spin Locks and traditional kernel Spin Locks are different data types and cannot be used interchangeably.  You can’t, for example, call KeAcquireSpinLock on an EX_SPIN_LOCK in one place, and call ExAcquireSpinLock Shared on that same EX_SPIN_LOCK in another place.  KeAcquireXxx and KeReleaseXxx can only be used with traditional KSPIN_LOCKs.  And ExAcquireXxx and ExReleaseXxx can only be used on Reader/Writer Spin Locks that always have the EX_SPIN_LOCK data type.

Note that the calls to acquire Reader/Writer Spin Locks differ slightly from the pattern used by KeAcquireSpinLock, in that the ExAcquireSpinLockXxxx functions return the previous IRQL at which the calling thread was running as the function’s return value.  I think that’s rather handy.

So, how do attempts to acquire the lock in various modes simultaneously interact?  If you attempt to acquire the lock in exclusive mode and there are one or more threads that already hold the lock in shared mode, the exclusive mode acquisition attempt will:

  • Block any subsequent requests to obtain the lock shared and
  • Wait until all the current shared holders have released the lock.

This is done to ensure the lock is granted as promptly as possible to an exclusive requestor.

Obviously, only one thread can hold the lock in exclusive mode at a time.  When multiple threads are waiting to acquire the lock in exclusive mode, the lock is granted to waiters in random order.  The way the lock is granted to exclusive waiters very closely resembles the mechanism used for traditional (non-reader/writer) Spin Locks.

The overhead for acquiring a Reader/Writer Spin Lock exclusive is approximately the same as that for a traditional Spin Lock. It’s important to recall what we said previously, that these are not queued locks. Thus, they can suffer from the same propensity as traditional Spin Locks to favor some waiters over others in certain systems.

The overhead of acquiring a Reader/Writer Spin Lock shared is also low and involves little more than an increment, an assign, a test, and an interlocked operation.  Couldn’t be simpler, could it?

We previously described the function ExAcquireSpinLockXxxxAt DpcLevel and noted that it avoids setting the IRQL to DISPATCH_LEVEL like the function ExAcquireSpinLockXxxx does.  At that point we said that calling ExAcquireSpinLockXxxxAtDpc Level can be used as a small optimization when you know in advance that you’re already running at IRQL DISPATCH_LEVEL.  But those of you who like to push beyond the limit of what’s documented might like to know that ExAcquireSpinLock SharedAtDpcLevel preserves the tradition started by KeAcquireSpinLockAtDpcLevel by allowing calls at any IRQL greater than or equal to DISPATCH_LEVEL.  Note the SAL notations (from the WDK for Win8):

The IRQL notation doesn’t require IRQL DISPATCH_LEVEL, it simply requires any IRQL greater than or equal to DISPATCH_LEVEL.  Interesting, eh?  What this does is allow you to construct your own Reader/Writer Spin Locks that work at specific IRQLs greater than IRQL DISPATCH_LEVEL.  Just raise the IRQL to the IRQL of your new spin lock (say, DIRQL), and call ExAcquireSpinLockXxxxAtDpcLevel.  Note that we’re not recommending this.  We’re simply saying that if you need a feature like this, and you don’t mind writing code using a feature that’s neither supported nor documented, this is a possibility.

Summary

Starting in Windows Vista SP1, Windows introduced a cool new set of synchronization primitives:  Reader/Writer Spin Locks.  Using these, you can properly support multiple simultaneous read accessors to shared data, and create code that’s more scalable.  Here at OSR, we’ve used these “new” primitives extensively in code that runs on Windows 7 and later.  We recommend you check them out.

Summary
Article Name
Introducing Reader/Writer Spin Locks
Description
New as of the Windows 8 WDK (and supported back to Vist SP1), reader/writer spin locks are a great addition to the Windows driver developer tool chest
Author