OSRLogo
OSRLogoOSRLogoOSRLogo x OSR Custom Development Services
OSRLogo
x

Everything Windows Driver Development

x
x
x
GoToHomePage xLoginx
 
 

    Tue, 14 Aug 2018     117715 members

   Login
   Join


 
 
Contents
  Online Dump Analyzer
OSR Dev Blog
The NT Insider
Downloads
ListServer / Forum
Driver Jobs
  Express Links
  · The NT Insider Digital Edition - May-June 2016 Now Available!
  · Windows 8.1 Update: VS Express Now Supported
  · HCK Client install on Windows N versions
  · There's a WDFSTRING?
  · When CAN You Call WdfIoQueueP...ously

ERESOURCEs Close Cousin: Implementing Reader/Writer Locks in User-Mode

Being primarily kernel mode programmers at OSR, we have gotten into the habit of using Reader/Writer locks.   These locks, known as Executive Resources (EResources), are great because they can be used at IRQLs less than DISPATCH_LEVEL and allow shared readers and exclusive writers.   In addition they also allow a thread recursive access, as long as the acquisition type is compatible with the lock’s current acquisition level.

That being said, it has always baffled us, at OSR, why something similar to EResourceswas never available in user mode.    We recently had a need to move a piece of software that previously ran in kernel mode to user mode and that software happened to use EResourcesas its primary locking model.   Our choices were either to reengineer the locking model used by the code or to implement EResourcesemantics in user mode.    Our choice was to implement EResourcesemantics in user mode and this article documents our implementation.

Overview

We’re going to assume that readers of this article are familiar with EResources, but realize that some people are not, so for the unfamiliar here’s an overview…..

As we mentioned previously an ERESOURCE is a reader/writer lock.   This lock can be acquired in 1 of 2 modes, either shared or exclusive   As the modes imply this lock can be held simultaneously by multiple readers (EResourceacquired in shared mode)  or by one writer (EResourceacquired in exclusive mode). 

When a thread attempts to acquire an ERESOURCE, it can specify whether or not it wants to wait if the specified ERESOURCE is not immediately available.   If it elects to wait, the thread will be put into a wait state until such time as the lock becomes available, otherwise the acquisition of the ERESOURCE will fail.  An ERESOURCE can be acquired by a thread recursively as long as the acquisition type (i.e. shared or exclusive) is compatible with the current acquisition type of the lock.   What this means is that if a thread holds a lock exclusive and tries to require the lock shared, the acquisition will be granted.   If, however, the thread holds the lock shared and tries to reacquire the lock exclusive, a deadlock will occur (as it does in kernel mode) since the desired acquisition type is incompatible with the currently held acquisition type.    Threads other than the current thread can attempt to acquire the ERESOURCE also and will only be allowed access if the mode of the request is compatible with the current state of the lock. So, for example, if Thread A owns the ERESOURCE shared, Thread B will also be allowed access to the ERESOURCE  if it attempts to acquire it shared.  If it tries to acquire the ERESOURCE exclusively, access will be denied (i.e. it will either be blocked if the user specified to wait for the ERESOURCE , or a status will be returned indicating that the ERESOURCE was not acquired).

Other features of ERESOURCE are:

  • If an ERESOURCE is held exclusively, it can be converted to shared access
  • Users can check to see if an EResourceis currently held exclusively or shared
  • Users can check to retrieve the number of Shared Waiters or Exclusive Waiters for an ERESOURCE.
  • EResourcesmust be initialized before being used and must be deleted when they are finished being used.

Now that the basics have been explained, let’s see the functions available to us.

Functions

In order to use OSRERESOURCEs (our version of ERESOURCEs) there are a set of functions that the user has available to them.   The functions are listed in Figure 1.

Figure 1 - OSRERESOURCE Functions

To use an OSRERESOURCE the caller would call OSRInitializeResourcein some initialization routine, and then call one of the OSRAcquireResourceXXXLite functions where XXX is either shared or exclusive. After doing some work it would then call OsrReleaseResourceto release the held resource.   Finally, when done with the resource, the user would call OSRDeleteResourceLite to delete the resource.

So as you can see OSRERESOURCEs are pretty easy to use.   Since this is a user mode library free for anyone to use, I guess it would be a good thing to discuss what is going on underneath the covers of the OSRERESOURCE implementation, so that is what we’ll discuss next.

Underneath the Covers of OSRERESOURCEs

In this section we will discuss how we implemented OSRERESOURCEs.  Our implementation creates a Dynamic Link Library called “UMERESOURCE.DLL”   This DLL has a set of “C” interfaces that we listed in Table 1 that are defined in the include file “UMERESOURCE.H”.   These interfaces work on an OSRERESOURCEstructure and are backed by a “C++” OSREResource class which is defined in “ERESOURCE.H”.   The OSRERESOURCE  class and associated OSRERESOURCE_STATE structure are defined in Figure 2.

 

// This structure keeps track of the state of the resource.  We need
// to know how the resource was acquired and how many times it was
// recursively acquired.
//
typedef struct _OSRERESOURCE_STATE
{
    union {
        struct {
            ULONG   State;          // Acquisition State
            ULONG   AcquireCount;   // Count of times acquired
        };
        ULONGLONG   Reserved;
    };
} OSRERESOURCE_STATE, *POSRERESOURCE_STATE;
 
 
class OSREResource : public CObject
{
public:
OSREResource();
virtual ~OSREResource();
 
enum {
ACQUIRED_NONE,
ACQUIRED_SHARED,
ACQUIRED_EXCLUSIVE
} ACQUIRED_STATE;
 
BOOLEAN AcquireResourceExclusive(BOOLEAN Wait);
BOOLEAN AcquireResourceShared(BOOLEAN Wait);
BOOLEAN AcquireSharedStarveExclusive(BOOLEAN Wait);
BOOLEAN IsResourceAcquiredExclusive();
BOOLEAN IsResourceAcquiredShared();
VOID ReleaseResource();
VOID ConvertExclusiveToShared();
VOID ReleaseResourceForThread(ERESOURCE_THREAD ResourceThreadId);
ULONG GetSharedWaiterCount();
ULONG GetExclusiveWaiterCount();
NTSTATUS InitializeResource();
NTSTATUS DeleteResource();
 
private:
mutable CRITICAL_SECTION m_CriticalSection;
 
typedef std::map CMapThreadToLockState;
CMapThreadToLockState m_LockStateMap;
 
volatile DWORD m_SharedCount;
volatile DWORD m_StarveExclusiveCount;
volatile DWORD m_ExclusiveCount;
volatile DWORD m_SharedWaitersCount;
volatile DWORD m_ExclusiveWaitersCount;
HANDLE m_WaitEventHandle;
BOOLEAN m_Initialized;
};
 
Figure 2—OSREResource Class and OSRERESOURCE_STATE Structure
 
 
This class contains:

 

  • m_CriticalSectionwhich is used by the code to synchronize access to the OSREResourcedata structures, ensuring that only one thread is accessing them at one time.  
  • m_LockStateMaptable which maps a Thread identifier to its resource state (i.e. the mode in which it acquired the lock).   This resource state is an OSRERESOURCE_STATE structure, defined in Table 2, which is composed of 2 fields, Stateand AcquireCount.   Stateis used to keep track of how the resource was acquired,  ACQUIRED_NONE, ACQUIRED_SHARED, or ACQUIRED_ EXCLUSIVE,  and AcquireCountis used to keep track of the number of times the thread has acquired the resource (remember that resources can be acquired recursively). 
  • m_WaitEventHandle– the handle to the notification event that all threads wait on when trying to acquire the resource.
  • m_SharedCount– number of shared holders of the resource.   Since threads can hold the resource recursively this does not necessarily reflect the number of threads holding the resource simultaneously.
  • m_StarveExclusiveCount – number of threads waiting to acquire the resource in shared mode, but want to starve exclusive waiters.  
  • m_ExclusiveCount– number of exclusive holders of the resource, which is usually one, but since a thread can acquire resource lock recursively, this count would reflect that.
  • m_SharedWaitersCount– number of threads waiting to acquire the resource in shared mode.
  • m_ExclusiveWaitersCount– number of threads waiting to acquire the resource in exclusive mode.
  • m_Initialized– Boolean indicating whether or not the resource was initialized by a call to OSRInitializeResource.

The code which implements this class uses the m_CriticalSectionto synchronize access to the rest of the OSREResourcedata, while the m_LockStateMapis used to keep track of each holder of the resource, the mode of acquisition (State), and the number of times that the acquisition was made since a holder could acquire the resource recursively (AcquireCount).  The data members’ m_SharedCountand m_ExclusiveCountare also used to keep track of the acquisition counts.

For any thread which tries to acquire the OSREResourceand elects to wait for the resource, the m_WaitEventHandle is the handle to the event that the thread will wait on.   This event is called a “NotificationEvent”. What this means is that unlike a “SynchronizationEvent” where only the first waiting thread is woken up, when the event is set, all waiting threads are woken up. This means that each awakened thread has the possibility of acquiring the resource.  Consider the scenario where a thread holds the resource exclusively and 10 threads are waiting to acquire the resource shared.  In our implementation all the shared waiters will be awakened when the exclusive holder releases the resources and will be able to acquire the resource.

Since the source code is readily available for download, we don’t want to spend a lot of time going through it.   What we do want to do however is go over AcquireResourceSharedand ReleaseResourceto at least give you a feel for how the code works.

AcquireResourceShared

Figure 3 contains the AcquireResourceSharedfunction.   As the name implies, this function attempts to acquire the OSRERESOURCE shared and if it cannot, waits if the user indicated wait for the resource to become available.   Remember that our code acquires m_CriticalSectionto ensure proper synchronization when access the class data structures.

 

BOOLEAN OSREResource::AcquireResourceShared(BOOLEAN Wait)
{
DWORD cThread = GetCurrentThreadId();
ULONG loopCount = 0;
EnterCriticalSection(&m_CriticalSection);
 
                   m_SharedWaitersCount++;
 
while(TRUE) {
// See if we already own the lock.
//
CMapThreadToLockState::iterator ite = m_LockStateMap.find(cThread);
if(ite != m_LockStateMap.end()) {
//
// We already own it, let's see what access we already have.
//
ite->second.AcquireCount++;
if(ite->second.State & ACQUIRED_SHARED) {
// We already have it shared, so just bump the count.
//
m_SharedCount++;
} else if(ite->second.State & ACQUIRED_EXCLUSIVE) {
// We have it exclusive, so just give it to the caller exclusive
//
m_ExclusiveCount++;
}
                                                      m_SharedWaitersCount--;
LeaveCriticalSection(&m_CriticalSection);
return TRUE;
} else if(m_ExclusiveCount || m_ExclusiveWaitersCount) {
// Someone else owns it exclusive or there are exclusive waiters, so we have to wait.
//
if(!Wait) {
                                                          m_SharedWaitersCount--;
   LeaveCriticalSection(&m_CriticalSection);
   break;
}
LeaveCriticalSection(&m_CriticalSection);
WaitForSingleObject(m_WaitEventHandle,INFINITE);
// Add a wait loop to prevent this thread from hogging the CPU.  The event gets set 
                      // when the holder releases the lock and we have to ensure that everyone gets a chance
// to run before continuing.
//
loopCount++;
if(loopCount == 5) {
Sleep(200);
loopCount = 0;
}
EnterCriticalSection(&m_CriticalSection);
continue;
} else {
// Nobody has it or wants it, so we will take it. We reset the event, so that it is no
                      // longer signaled. Anyone who was waiting for the event should already be woken up.
//
OSRERESOURCE_STATE state;
state.State = ACQUIRED_SHARED;
state.AcquireCount = 1;
m_SharedCount++;
                                                      m_SharedWaitersCount--;
m_LockStateMap.insert(std::make_pair(cThread,state));
                                                      ResetEvent(m_WaitEventHandle);
LeaveCriticalSection(&m_CriticalSection);
return TRUE;
}
}
return FALSE;
}

}Figure 3 - AcquireResourceShared

This routine first looks to see if the calling thread already holds the resource by looking for the threads’ Id in the m_LockStateMap.  If the thread is found, then the code updates the ownership counts and returns TRUE to the caller indicating that the resource has been acquired. 

If the thread Id was not found in the m_LockStateMap, the code then checks to see if the resource is held exclusively or if there are threads waiting for the resource exclusively.   If there are, then this indicates that the caller cannot acquire the resource.   What is done next depends on the input Wait parameter.   If this parameter is TRUE, then the caller will wait on the m_WaitEventHandle.   If this parameter is FALSE, the code will return to the caller indicating that the resource was not acquired.

Finally, if the resource is not held exclusively, or if there are no threads waiting for the resource exclusively, then the code inserts an entry into the m_LockStateMap. This entry indicates how the resource was acquired, updates the appropriate counts in the class, and returns to the caller indicating that the resource was acquired.

There is one thing that we must highlight here and it is that the loop code follows the WaitForSingleObject.  Keep in mind that there could be many threads, with various scheduling priorities, wanting to acquire the OSRERESOURCE  in different ways, all waiting for it to become free.   If we automatically gave acquisition of the OSRERESOURCE  to the first thread through the code, we could potentially starve other waiters, since we know that highest priority will almost always get the CPU first.   We didn’t want to keep track of the waiters in a list and heuristically pick the next owner, so we decided to make it somewhat random (BTW, if you don’t like it, change it and let us know what your solution is and why it is better!).   Therefore we have all threads coming out of the WaitForSingleObjectsleeping for about 200 milliseconds, to let all threads that were blocked have time to run through the acquire code again and reassess their access to the lock.

That’s all there is to acquiring the OSRERESOURCE shared, so let’s see how you release it.

ReleaseResource

Figure 4 contains the code for ReleaseResource.  As the name implies, this code releases an owned OSRERESOURCE .  Remember that our code acquires m_Critical Sectionto ensure proper synchronization when accessing the class data structures.

 

VOID OSREResource::ReleaseResource()
{
DWORD cThread = GetCurrentThreadId();
 
EnterCriticalSection(&m_CriticalSection);
 
//
// See if we own the lock.  We'd better.....
//
CMapThreadToLockState::iterator ite = m_LockStateMap.find(cThread);
 
if(ite != m_LockStateMap.end()) {
//
// We own it.   Decrement the ownership count based upon
// our access.
//
if(ite->second.State & ACQUIRED_SHARED) {
m_SharedCount--;
} else {
m_ExclusiveCount--;
}
 
//
// Look at our ownership count in the lowpart of the
// large integer.   If it is 1, then this is our
// last reference to the lock, so we will delete
// ourselves from the ownership map.
//
if(ite->second.AcquireCount == 1) {
//
// erase us, we no longer own the lock.
//
m_LockStateMap.erase(ite);
 
//
// Wake up anyone waiting on access to the lock.
//
SetEvent(m_WaitEventHandle);
} else {
//
// We still have outstanding references....
//
ite->second.AcquireCount--;
}
LeaveCriticalSection(&m_CriticalSection);
} else {
RaiseException(0xC0000002,EXCEPTION_NONCONTINUABLE,0,NULL);
}
}

Figure 4 - ReleaseResource

The first step for the code is to attempt to find the calling thread in the m_LockStateMap, which keeps track of the threads that are currently holding the OSREResource.  If the calling thread is not found in them_LockStateMap structure, the code will raise a 0xC0000002 exception to indicate that the OSREResourcewas not held by the caller.   If the caller was found in the m_LockStateMap, the code will decrement either the m_Shared Countor m_ExclusiveCount field, depending upon how the caller had acquired the OSREResource.

The code then looks at whether or not this is the calling thread’s last reference to the OSRERESOURCE , which would indicate that the OSRERESOURCE  is now free to be acquired by other threads.   It checks for the last reference by looking at the AcquiredCountfield of the returned OSRERESOURCE _STATE structure.   If the AcquireCount is not 1, then the code knows that the OSRERESOURCE is still not available to other acquirers.   If however the AcquireCountfield is 1, then the code knows this is the last reference to the OSRERESOURCE , at which point it can delete the calling threads entry from the m_LockStateMap, and can signal the OSREResource’s event (m_WaitEventHandle).   Signaling the event will cause all the other threads waiting for this OSRERESOURCE to be awakened so that they can attempt to acquire the OSREResource.

Problems

As we mentioned earlier, the code will raise different exceptions if it determines that something bad is going on.   These were added to aid in debugging problems that you may run into and are shown in Figure 5.   As for deadlocks, the only way to debug those is to examine each thread in your application and see what it is waiting for in hopes that you can determine the deadlock.

Figure 5 - Exceptions Thrown by UMERESOURCEDLL

Summary

So there you have it, an OSR implementation of Executive Resources in user mode.   As you can see the code is pretty simple, and provides the advantages of ERESOURCEs to user mode, i.e. a true reader/writer lock.

You will find the code associated with this article at:

http://www.osronline.com/OsrDown.cfm/osreresource.zip?name=osreresource.zip&id=561

User Comments
Rate this article and give us feedback. Do you find anything missing? Share your opinion with the community!
Post Your Comment

"missing a __stdcall on NtCreateEvent"
In reviewing the code we found that a __stdcall call was missing on the definition below, which was mistakenly called PNTCREATEFILE instead of PTNTCREATEEVENT.

// // We need to create a notification event, so that all threads waiting on the // resource event will wakeup and reassesss their access to the resource. // NTSYSAPI NTSTATUS NTAPI NtCreateEvent ( OUT PHANDLE EventHandle, IN ACCESS_MASK DesiredAccess, IN POBJECT_ATTRIBUTES ObjectAttributes OPTIONAL, IN EVENT_TYPE EventType, IN BOOLEAN InitialState );

typedef NTSTATUS (__stdcall *PNTCREATEEVENT)( OUT PHANDLE EventHandle, IN ACCESS_MASK DesiredAccess, IN POBJECT_ATTRIBUTES ObjectAttributes OPTIONAL, IN EVENT_TYPE EventType, IN BOOLEAN InitialState );

Rating:
03-Sep-10, Mark Cariddi


"Slim Reader/Writer"
Actually, we did look at Slim Reader/Writer locks and we did not like them. They cannot be acquired recursively, and did not have a way to check to see if they were already owned.

Rating:
09-Aug-10, Mark Cariddi


"User-mode reader-writer lock"
Hi assume that the windows version you were working on was pre-vista and therefore didn't have Slim Reader/Writer (SRW) Locks?

Rating:
08-Aug-10, eran borovik


Post Your Comments.
Print this article.
Email this article.

Kernel Debugging & Crash Analysis
LAB

Manchester, NH
30 July - 3 Aug 2018

Developing Filter Manager Minifilters
LAB

Manchester, NH
20-24 August 2018

Writing WDF Drivers I: Core Concepts
LAB

Santa Clara/San Jose, CA
10-14 Sept 2018

Writing WDF Drivers II: Advanced Implementation Techniques
LAB

Manchester, NH
16-19 October 2018

 
 
 
 
x
LetUsHelp
 

Need to develop a Windows file system solution?

We've got a kit for that.

Need Windows internals or kernel driver expertise?

Bring us your most challenging project - we can help!

System hangs/crashes?

We've got a special diagnostic team that's standing by.

Visit the OSR Corporate Web site for more information about how OSR can help!

 
bottom nav links