Implementing a Critical Section: The Optex

[Previous] [Next]

Critical sections have always fascinated me. After all, if they're just user-mode objects, why can't I implement them myself? Why do I need operating system support to make critical sections work? Also, if I write my own critical section, I might want to add features to it and enhance it in some way. At the very least, I would want it to track which thread currently owns the resource. A critical section implementation that did so would help me to resolve deadlock problems in my code; I could use a debugger to discover which thread was not releasing the resource.

So without further ado, let's take a look at how critical sections are implemented. I keep saying that critical sections are user-mode objects. In reality, this isn't 100 percent true. If a thread attempts to enter a critical section that is owned by another thread, the thread is placed in a wait state. The only way for it to enter a wait state is for it to transition from user mode to kernel mode. A user-mode thread can stop doing useful work by spinning, but that is hardly an efficient wait state, hence you should avoid it.

So critical sections must include some kernel object that can cause a thread to enter an efficient wait state. A critical section is fast because this kernel object is used only if there is contention for the critical section. As long as threads can immediately gain access to a resource, use the resource, and release it without contention from other threads, the kernel object is not used and the thread never leaves user mode. In most applications, two (or more) threads rarely contend for a critical section simultaneously.

The Optex.h and Optex.cpp files (shown in Figure 10-1) show my implementation of a critical section. I call my critical section an optex (which stands for optimized mutex) and have implemented it as a C++ class. Once you understand this code, you'll see why critical sections are faster than mutex kernel objects.

Since I implement my own critical section, I can add useful features to it. For instance, my COptex class allows threads in different processes to synchronize themselves on it. This is a fantastic addition—now I have a high-performance mechanism for communicating between threads in different processes.

To use my optex, you simply declare a COptex object. There are three possible constructors for this object:

 COptex::(DWORD dwSpinCount = 4000); COptex::(PCSTR pszName, DWORD dwSpinCount = 4000); COptex::(PCWSTR pszName, DWORD dwSpinCount = 4000); 

The first constructor creates a COptex object that you can use only to synchronize threads of a single process. This type of optex has much less overhead than a cross-process optex. The other two constructors let you create an optex that can be used by threads in multiple processes. For the pszName parameter, you must pass an ANSI or Unicode string that uniquely identifies each shared optex. To have two or more processes share a single optex, both processes must instantiate a COptex object, passing the same string name.

A thread enters and leaves a COptex object by calling its Enter and Leave methods:

 void COptex::Enter(); void COptex::Leave(); 

I've even included methods that are the equivalent of a critical section's TryEnterCriticalSection and SetCriticalSectionSpinCount functions:

 BOOL COptex::TryEnter(); void COptex::SetSpinCount(DWORD dwSpinCount); 

You can call the last method, shown below, if you need to know whether an optex is a single-process or cross-process optex. (You rarely need to call this function, but the internal method functions call it occasionally.)

 BOOL COptex::IsSingleProcessOptex() const; 

Those are all the (public) functions you need to know to use the optex. Now I'll explain how the optex works. Basically, an optex (and a critical section, for that matter) contains a number of member variables. These variables reflect the state of the optex. In my Optex.h file, most of these members are in a SHAREDINFO structure and a few are members of the class itself. The table below describes each member's purpose.

Member	Description
m_lLockCount	Indicates the number of times that threads attempt to enter the optex. This value is 0 if no thread is entering the optex.
m_dwThreadId	Indicates the unique ID of the thread owning the optex. The value is 0 if no thread owns the optex.
m_lRecurseCount	Indicates the number of times the optex is owned by the owning thread. The value is 0 if the optex is unowned.
m_hevt	This is the handle of an event kernel object, which is used only if a thread attempts to enter the optex while another thread owns it. Kernel handles are process-relative, which is why this member is not in the SHAREDINFO structure.
m_dwSpinCount	Indicates the number of times that the thread attempting to enter the optex should try before waiting on the event kernel object. This value is always 0 on a uniprocessor machine.
m_hfm	This is the handle of a file-mapping kernel object, which is used when multiple processes share a single optex. Kernel handles are process-relative, which is why this member is not in the SHAREDINFO structure. This value is always NULL for a single-process optex.
m_psi	This is the pointer to the potentially shared optex data members. Memory addresses are process-relative, which is why this member is not in the SHAREDINFO structure. For a single-process optex, this points to a heap-allocated block. For a multiprocess optex, it points to a memory-mapped file.

The source code is sufficiently commented, so you should have no trouble understanding how the optex works. The important thing to note is that the optex gets its speed because it makes heavy use of the interlocked family of functions. This keeps the code executing in user mode and avoids transitions.

The Optex Sample Application

The Optex ("10 Optex.exe") application, listed in Figure 10-1, tests the COptex class to make sure that it works properly. The source code and resource files for the application are in the 10-Optex directory on this book's companion CD-ROM. I always run the application in the debugger so I can closely watch all the member functions and variables.

When you run the application, it first detects whether it is the first instance of this application running. I do this by creating a named event kernel object. I don't actually use the event object anywhere in the application; I just create it to see if GetLastError returns ERROR_ALREADY_EXISTS. If so, I know that this is the second running instance of the application. I'll explain later why I run two instances of this application.

If this is the first instance, I create a single-process COptex object and call my FirstFunc function. This function performs a series of manipulations on the optex object. A second thread is created that also manipulates the same optex object. At this point, the two threads manipulating the optex are in the same process. You can examine the source code to see what tests I perform. I tried to cover all possible scenarios so that all the code in the COptex class gets a chance to execute.

After testing a single-process optex, I test the cross-process optex. In _tWinMain, when the first call to FirstFunc returns, I create another COptex optex object. But this time, I give the optex a string name of CrossOptexTest. Simply creating an optex with a name makes it a cross-process optex. Next, I call FirstFunc a second time, passing it the address of the cross-process optex. FirstFunc executes basically the same code as it did before. But now, instead of spawning a second thread, it spawns a child process.

This child process is just another instance of the same application. But when it starts executing, it creates the event kernel object and detects that the event object already exists. This is how the second instance of the application knows that it's the second instance and executes different code than the first instance. The first thing that the second instance does is call DebugBreak:

 VOID DebugBreak(); 

This handy function forces a debugger to run and connect itself to the process. This makes it easy for me to debug both instances of this application. The second instance then creates a cross-process optex, passing the same string name. Since the string names are identical, both processes share the optex. By the way, more than two processes can share the same optex.

Now the second instance of the application calls SecondFunc, passing it the address of the cross-process optex. At this point, the same set of tests is performed, but the two threads manipulating the optex are in different processes.

Figure 10-1. The Optex sample application

Optex.cpp

 /****************************************************************************** Module: Optex.cpp Notices: Copyright (c) 2000 Jeffrey Richter ******************************************************************************/ #include "..\CmnHdr.h" /* See Appendix A. */ #include "Optex.h" /////////////////////////////////////////////////////////////////////////////// // 0=multi-CPU, 1=single-CPU, -1=not set yet BOOL COptex::sm_fUniprocessorHost = -1; /////////////////////////////////////////////////////////////////////////////// PSTR COptex::ConstructObjectName(PSTR pszResult, PCSTR pszPrefix, BOOL fUnicode, PVOID pszName) { pszResult[0] = 0; if (pszName == NULL) return(NULL); wsprintfA(pszResult, fUnicode ? "%s%S" : "%s%s", pszPrefix, pszName); return(pszResult); } /////////////////////////////////////////////////////////////////////////////// void COptex::CommonConstructor(DWORD dwSpinCount, BOOL fUnicode, PVOID pszName) { if (sm_fUniprocessorHost == -1) { // This is the 1st object constructed, get the number of CPUs SYSTEM_INFO sinf; GetSystemInfo(&sinf); sm_fUniprocessorHost = (sinf.dwNumberOfProcessors == 1); } m_hevt = m_hfm = NULL; m_psi = NULL; if (pszName == NULL) { // Creating a single-process optex m_hevt = CreateEventA(NULL, FALSE, FALSE, NULL); chASSERT(m_hevt != NULL); m_psi = new SHAREDINFO; chASSERT(m_psi != NULL); ZeroMemory(m_psi, sizeof(*m_psi)); } else { // Creating a cross-process optex // Always use ANSI so that this works on Win9x and Windows 2000 char szResult[100]; ConstructObjectName(szResult, "Optex_Event_", fUnicode, pszName); m_hevt = CreateEventA(NULL, FALSE, FALSE, szResult); chASSERT(m_hevt != NULL); ConstructObjectName(szResult, "Optex_MMF_", fUnicode, pszName); m_hfm = CreateFileMappingA(INVALID_HANDLE_VALUE, NULL, PAGE_READWRITE, 0, sizeof(*m_psi), szResult); chASSERT(m_hfm != NULL); m_psi = (PSHAREDINFO) MapViewOfFile(m_hfm, FILE_MAP_WRITE, 0, 0, 0); chASSERT(m_psi != NULL); // Note: SHAREDINFO's m_lLockCount, m_dwThreadId, and m_lRecurseCount // members need to be initialized to 0. Fortunately, a new pagefile // MMF sets all of its data to 0 when created. This saves us from // some thread synchronization work. } SetSpinCount(dwSpinCount); } /////////////////////////////////////////////////////////////////////////////// COptex::~COptex() { #ifdef _DEBUG if (IsSingleProcessOptex() && (m_psi->m_dwThreadId != 0)) { // A single-process optex shouldn't be destroyed if any thread owns it DebugBreak(); } if (!IsSingleProcessOptex() && (m_psi->m_dwThreadId == GetCurrentThreadId())) { // A cross-process optex shouldn't be destroyed if our thread owns it DebugBreak(); } #endif CloseHandle(m_hevt); if (IsSingleProcessOptex()) { delete m_psi; } else { UnmapViewOfFile(m_psi); CloseHandle(m_hfm); } } /////////////////////////////////////////////////////////////////////////////// void COptex::SetSpinCount(DWORD dwSpinCount) { // No spinning on single CPU machines if (!sm_fUniprocessorHost) InterlockedExchangePointer((PVOID*) &m_psi->m_dwSpinCount, (PVOID) (DWORD_PTR) dwSpinCount); } /////////////////////////////////////////////////////////////////////////////// void COptex::Enter() { // Spin, trying to get the optex if (TryEnter()) return; // We got it, return // We couldn't get the optex, wait for it. DWORD dwThreadId = GetCurrentThreadId(); if (InterlockedIncrement(&m_psi->m_lLockCount) == 1) { // Optex is unowned, let this thread own it once m_psi->m_dwThreadId = dwThreadId; m_psi->m_lRecurseCount = 1; } else { if (m_psi->m_dwThreadId == dwThreadId) { // If optex is owned by this thread, own it again m_psi->m_lRecurseCount++; } else { // Optex is owned by another thread, wait for it WaitForSingleObject(m_hevt, INFINITE); // Optex is unowned, let this thread own it once m_psi->m_dwThreadId = dwThreadId; m_psi->m_lRecurseCount = 1; } } } /////////////////////////////////////////////////////////////////////////////// BOOL COptex::TryEnter() { DWORD dwThreadId = GetCurrentThreadId(); BOOL fThisThreadOwnsTheOptex = FALSE; // Assume a thread owns the optex DWORD dwSpinCount = m_psi->m_dwSpinCount; // How many times to spin do { // If lock count = 0, optex is unowned, we can own it fThisThreadOwnsTheOptex = (0 == InterlockedCompareExchange(&m_psi->m_lLockCount, 1, 0)); if (fThisThreadOwnsTheOptex) { // Optex is unowned, let this thread own it once m_psi->m_dwThreadId = dwThreadId; m_psi->m_lRecurseCount = 1; } else { if (m_psi->m_dwThreadId == dwThreadId) { // If optex is owned by this thread, own it again InterlockedIncrement(&m_psi->m_lLockCount); m_psi->m_lRecurseCount++; fThisThreadOwnsTheOptex = TRUE; } } } while (!fThisThreadOwnsTheOptex && (dwSpinCount— > 0)); // Return whether or not this thread owns the optex return(fThisThreadOwnsTheOptex); } /////////////////////////////////////////////////////////////////////////////// void COptex::Leave() { #ifdef _DEBUG // Only the owning thread can leave the optex if (m_psi->m_dwThreadId != GetCurrentThreadId()) DebugBreak(); #endif // Reduce this thread's ownership of the optex if (—m_psi->m_lRecurseCount > 0) { // We still own the optex InterlockedDecrement(&m_psi->m_lLockCount); } else { // We don't own the optex anymore m_psi->m_dwThreadId = 0; if (InterlockedDecrement(&m_psi->m_lLockCount) > 0) { // Other threads are waiting, the auto-reset event wakes one of them SetEvent(m_hevt); } } } //////////////////////////////// End of File ////////////////////////////////// 

 Optex.h /****************************************************************************** Module name: Optex.h Written by: Jeffrey Richter ******************************************************************************/ #pragma once /////////////////////////////////////////////////////////////////////////////// class COptex { public: COptex(DWORD dwSpinCount = 4000); COptex(PCSTR pszName, DWORD dwSpinCount = 4000); COptex(PCWSTR pszName, DWORD dwSpinCount = 4000); ~COptex(); void SetSpinCount(DWORD dwSpinCount); void Enter(); BOOL TryEnter(); void Leave(); BOOL IsSingleProcessOptex() const; private: typedef struct { DWORD m_dwSpinCount; long m_lLockCount; DWORD m_dwThreadId; long m_lRecurseCount; } SHAREDINFO, *PSHAREDINFO; HANDLE m_hevt; HANDLE m_hfm; PSHAREDINFO m_psi; private: static BOOL sm_fUniprocessorHost; private: void CommonConstructor(DWORD dwSpinCount, BOOL fUnicode, PVOID pszName); PSTR ConstructObjectName(PSTR pszResult, PCSTR pszPrefix, BOOL fUnicode, PVOID pszName); }; /////////////////////////////////////////////////////////////////////////////// inline COptex::COptex(DWORD dwSpinCount) { CommonConstructor(dwSpinCount, FALSE, NULL); } /////////////////////////////////////////////////////////////////////////////// inline COptex::COptex(PCSTR pszName, DWORD dwSpinCount) { CommonConstructor(dwSpinCount, FALSE, (PVOID) pszName); } /////////////////////////////////////////////////////////////////////////////// inline COptex::COptex(PCWSTR pszName, DWORD dwSpinCount) { CommonConstructor(dwSpinCount, TRUE, (PVOID) pszName); } /////////////////////////////////////////////////////////////////////////////// inline COptex::IsSingleProcessOptex() const { return(m_hfm == NULL); } ///////////////////////////////// End of File ///////////////////////////////// 

 Optex.rc //Microsoft Developer Studio generated resource script. // #include "resource.h" #define APSTUDIO_READONLY_SYMBOLS ///////////////////////////////////////////////////////////////////////////// // // Generated from the TEXTINCLUDE 2 resource. // #include "afxres.h" ///////////////////////////////////////////////////////////////////////////// #undef APSTUDIO_READONLY_SYMBOLS ///////////////////////////////////////////////////////////////////////////// // English (U.S.) resources #if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENU) #ifdef _WIN32 LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_US #pragma code_page(1252) #endif //_WIN32 ///////////////////////////////////////////////////////////////////////////// // // Icon // // Icon with lowest ID value placed first to ensure application icon // remains consistent on all systems. IDI_OPTEX ICON DISCARDABLE "Optex.ICO" #ifdef APSTUDIO_INVOKED ///////////////////////////////////////////////////////////////////////////// // // TEXTINCLUDE // 1 TEXTINCLUDE DISCARDABLE BEGIN "resource.h\0" END 2 TEXTINCLUDE DISCARDABLE BEGIN "#include ""afxres.h""\r\n" "\0" END 3 TEXTINCLUDE DISCARDABLE BEGIN "\r\n" "\0" END #endif // APSTUDIO_INVOKED #endif // English (U.S.) resources ///////////////////////////////////////////////////////////////////////////// #ifndef APSTUDIO_INVOKED ///////////////////////////////////////////////////////////////////////////// // // Generated from the TEXTINCLUDE 3 resource. // ///////////////////////////////////////////////////////////////////////////// #endif // not APSTUDIO_INVOKED 

 OptexTest.cpp /****************************************************************************** Module name: OptexTest.cpp Written by: Jeffrey Richter ******************************************************************************/ #include "..\CmnHdr.h" /* See Appendix A. */ #include <tchar.h> #include <process.h> #include "Optex.h" /////////////////////////////////////////////////////////////////////////////// DWORD WINAPI SecondFunc(PVOID pvParam) { COptex& optex = * (COptex*) pvParam; // The primary thread should own the optex here, this should fail chVERIFY(optex.TryEnter() == FALSE); // Wait for the primary thread to give up the optex optex.Enter(); optex.Enter(); // Test recursive ownership chMB("Secondary: Entered the optex\n(Dismiss me 2nd)"); // Leave the optex but we still own it once optex.Leave(); chMB("Secondary: The primary thread should not display a box yet"); optex.Leave(); // The primary thread should be able to run now return(0); } /////////////////////////////////////////////////////////////////////////////// VOID FirstFunc(BOOL fLocal, COptex& optex) { optex.Enter(); // Gain ownership of the optex // Since this thread owns the optex, we should be able to get it again chVERIFY(optex.TryEnter()); HANDLE hOtherThread = NULL; if (fLocal) { // Spawn a secondary thread for testing purposes (pass it the optex) DWORD dwThreadId; hOtherThread = chBEGINTHREADEX(NULL, 0, SecondFunc, (PVOID) &optex, 0, &dwThreadId); } else { // Spawn a secondary process for testing purposes STARTUPINFO si = { sizeof(si) }; PROCESS_INFORMATION pi; TCHAR szPath[MAX_PATH]; GetModuleFileName(NULL, szPath, chDIMOF(szPath)); CreateProcess(NULL, szPath, NULL, NULL, FALSE, 0, NULL, NULL, &si, &pi); hOtherThread = pi.hProcess; CloseHandle(pi.hThread); } // Wait for the second thread to own the optex chMB("Primary: Hit OK to give optex to secondary"); // Let the second thread gain ownership of the optex optex.Leave(); optex.Leave(); // Wait for the second thread to own the optex chMB("Primary: Hit OK to wait for the optex\n(Dismiss me 1st)"); optex.Enter(); // Try to gain ownership back WaitForSingleObject(hOtherThread, INFINITE); CloseHandle(hOtherThread); optex.Leave(); } /////////////////////////////////////////////////////////////////////////////// int WINAPI _tWinMain(HINSTANCE hinstExe, HINSTANCE, PTSTR pszCmdLine, int) { // This event is just used to determine which instance this is. HANDLE hevt = CreateEvent(NULL, FALSE, FALSE, TEXT("OptexTest")); if (GetLastError() != ERROR_ALREADY_EXISTS) { // This is the first instance of this test application // First, let's test the single-process optex COptex optexSingle; // Create a single-process optex FirstFunc(TRUE, optexSingle); // Now, let's test the cross-process optex COptex optexCross("CrossOptexTest"); // Create a cross-process optex FirstFunc(FALSE, optexCross); } else { // This is the second instance of this test application DebugBreak(); // Force debugger connection for tracing // Test the cross-process optex COptex optexCross("CrossOptexTest"); // Create a cross-process optex SecondFunc((PVOID) &optexCross); } CloseHandle(hevt); return(0); } ///////////////////////////////// End of File /////////////////////////////////