Channels ▼
RSS

Design

Deadlock-Proof Your Code: Part 1


Listing 2 is functionally identical to the deadlocking code of Listing 1, except that it adds thread and lock tracking as described above and provides for surrogate locks as described above. As many surrogate locks are created as are called for, while deadlocks continue to be averted until the run completes. In this code, self-aware lock (*SelfAwareLock) API wrapper functions are substituted in place of several standard Windows API function calls coded in Listing 1. You can achieve the same wrapper effect in production code if you arrange dynamic interception of the necessary API functions via object code runtime patching or via other means. Your intercepts can be set up at or near the start of the run or when a relevant component is loaded into the process.


/*  Listing 2: No more deadlocks  */

#include <windows.h>
#include <stdio.h>

// Constants
const long kSuccess = 0;
const long kFailure = 1;
const long  kTextAreaSize = 100;
const short kNumThreads = 2;

// Globals
CRITICAL_SECTION L1;
CRITICAL_SECTION L2;
int iSharedIntegerCounter = 0x61;			// ASCII 'a'
char szSharedTextBase[kTextAreaSize];
char *pSharedText = szSharedTextBase;

// Function prototypes, same as in Listing 1
DWORD WINAPI FuncA(void *vp);
DWORD WINAPI FuncB(void *vp);

// Deadlock-proofing structures and function declarations follow.

// This is our thread tracking structure.
typedef struct tag_TThread_t
{
	HANDLE hThread;
	DWORD  TID;
	void *pHoldingSALock;
	void *pWaitingSALock;
	CRITICAL_SECTION *pSurrogateLock;
	tag_TThread_t *next;
} TrackedThread_t;

// This is our lock tracking structure.
typedef struct tag_SALock_t
{
	CRITICAL_SECTION *lock;
	TrackedThread_t *pOwningTThread;
	TrackedThread_t *pWaitingTThread;
	BOOL bEntering;
	DWORD callerAddr;
	tag_SALock_t *next;
} SelfAwareLock_t;

// This structure associates a tracked thread with a tracked lock.
typedef struct tag_HeldSALock_t
{
	SelfAwareLock_t *pSALock;
	CRITICAL_SECTION *pSurrogateLock;
	tag_HeldSALock_t *next;
} HeldSALock_t;

// These are pointers to lists of tracked threads and locks.
TrackedThread_t *TThread;
SelfAwareLock_t *SALock;

// This lock protects the thread and lock tracking data itself.
CRITICAL_SECTION SALockCS;

// Function prototypes specific to deadlock-proofing method
//
// The following functions are called in lieu of the standard threading 
// API functions as described here.  They act as wrappers for those 
// functions.
//
// Instead of CreateThread():
HANDLE CreateAndTrackThread(
			LPTHREAD_START_ROUTINE lpStartAddress, 
			LPVOID lpParameter, 
			LPDWORD lpThreadId
);
// Instead of CloseHandle() on a thread:
DWORD CloseTrackedThread(
			HANDLE hThread
);
// Instead of ExitThread():
void ExitTrackedThread(
			DWORD dwExitCode
);
// Instead of InitializeCriticalSection():
void InitializeSelfAwareLock(
			CRITICAL_SECTION *lock
);
// Instead of EnterCriticalSection():
void AcquireSelfAwareLock(
			CRITICAL_SECTION *lock, 
			DWORD callerAddr
);
// Instead of LeaveCriticalSection():
void ReleaseSelfAwareLock(
			CRITICAL_SECTION 
			*lock
);
// This next function releases all of the locks currently held by a 
// thread.  There is no equivalent Windows API function.
void ReleaseThreadsLocks(
			TrackedThread_t *pTThread
);

// The following code would deadlock without our watchdog methods.

long main(long argc, char **argv)
{
	long status = kSuccess;

	HANDLE hThreads[kNumThreads];
	DWORD TID1, TID2;

	InitializeSelfAwareLock(&L1);
	InitializeSelfAwareLock(&L2);

	// Create two threads.
	hThreads[0] = CreateAndTrackThread(
					&FuncA, 
					(void *)1, 
					&TID1);
	if (hThreads[0] == NULL) 
	{
		printf("Error creating thread.\n");
		status = kFailure;
	}
	else
	{
		hThreads[1] = CreateAndTrackThread(
					&FuncB, 
					(void *)1, 
					&TID2);
		if (hThreads[1] == NULL) 
		{
			printf("Error creating thread.\n");
			status = kFailure;
		}
	}

	if (status == kSuccess)
	{
		DWORD wfmo = 
		     WaitForMultipleObjects(kNumThreads, hThreads, TRUE, INFINITE);
		int LastError = GetLastError();

		DeleteCriticalSection(&L1);
		DeleteCriticalSection(&L2);

		// Close the thread handles.
		CloseTrackedThread(hThreads[0]);
		CloseTrackedThread(hThreads[1]);
	}

	// Add a NULL terminator to our 'a' - 'z' string, and display it.
	*pSharedText = '\0';
	printf("%s\n", szSharedTextBase);
	return(status);	
}

DWORD WINAPI FuncA(void *vp)
{
	static int count = 13;
	DWORD callerAddr = (DWORD) &FuncA;
	AcquireSelfAwareLock(&L1, callerAddr);

	if (count-- > 0)
	{
		*(pSharedText++) = iSharedIntegerCounter++;
		FuncB(vp);
		ReleaseSelfAwareLock(&L1);
	}
	ExitTrackedThread(0);
	return(0);
}

DWORD WINAPI FuncB(void *vp)
{
	static int count = 13;
	DWORD callerAddr = (DWORD) &FuncB;
	AcquireSelfAwareLock(&L2, callerAddr);

	if (count-- > 0)
	{
		*(pSharedText++) = iSharedIntegerCounter++;
		FuncA(vp);
		ReleaseSelfAwareLock(&L2);
	}
	ExitTrackedThread(0);
	return(0);
}

// Functions implementing the deadlock-proofing method follow.

// This function looks up tracking information for the specified thread.
//
TrackedThread_t * FindTrackedThread(
		DWORD dwThreadId, 
		TrackedThread_t **prevTThread
)
{
	TrackedThread_t *pTThread = TThread;
	if (prevTThread)
	{
		*prevTThread = NULL;
	}

	while (pTThread && dwThreadId != pTThread->TID)
	{
		if (prevTThread)
		{
			*prevTThread = pTThread;
		}
		pTThread = pTThread->next;
	}
	return pTThread;
}

// This function looks up tracking information for the specified thread.
//
TrackedThread_t * FindTrackedThreadByHandle(
		HANDLE hThread, 
		TrackedThread_t **prevTThread
)
{
	TrackedThread_t *pTThread = TThread;
	if (prevTThread)
	{
		*prevTThread = NULL;
	}

	while (pTThread && hThread != pTThread->hThread)
	{
		if (prevTThread)
		{
			*prevTThread = pTThread;
		}
		pTThread = pTThread->next;
	}
	return pTThread;
}

// This function launches and tracks new threads.
// Call it in lieu of CreateThread() on Windows.
//
HANDLE CreateAndTrackThread(
		LPTHREAD_START_ROUTINE lpStartAddress, 
		LPVOID lpParameter, 
		LPDWORD lpThreadId
)
{
	static BOOL bFirstPass = TRUE;

	// Allocate our thread tracking structure.
	TrackedThread_t *pTThread = 
	                   (TrackedThread_t *) malloc(sizeof(TrackedThread_t));
	TrackedThread_t *formerTThread;

	// Make sure we can protect our thread and lock tracking data.
	if (bFirstPass)
	{
		InitializeCriticalSection(&SALockCS);
		bFirstPass = FALSE;
	}

	// Create the thread.
	pTThread->hThread = CreateThread(NULL, 
						0,
						lpStartAddress, 
						(void *)1, 
						0, 
						&pTThread->TID);

	// Add it to the start of the tracked thread list.
	EnterCriticalSection(&SALockCS);
	formerTThread = TThread;
	TThread = pTThread;
	TThread->next = formerTThread;
	lpThreadId = &pTThread->TID;
	pTThread->pHoldingSALock = NULL;
	pTThread->pWaitingSALock = NULL;
	pTThread->pSurrogateLock = NULL;
	LeaveCriticalSection(&SALockCS);
	return pTThread->hThread;
}

// This function exits the specified thread and cleans up tracking for it.
// Call it in lieu of CloseHandle() on Windows.
//
DWORD CloseTrackedThread(HANDLE hThread)
{
	TrackedThread_t *prevTThread;
	TrackedThread_t *nextTThread;
	TrackedThread_t *pTThread = 
	                      FindTrackedThreadByHandle(hThread, &prevTThread);

	// End the thread.
	DWORD dwRetVal = CloseHandle(hThread);

	// Take it off the tracked thread list.
	if (pTThread)
	{
		EnterCriticalSection(&SALockCS);
		ReleaseThreadsLocks(pTThread);
		nextTThread = pTThread->next;

		if (prevTThread)
		{
			prevTThread->next = nextTThread;
		}
		else if (TThread = pTThread)
		{
			TThread = nextTThread;
		}
		else
		{
			// Shouldn't get here.
			DebugBreak();
		}

		// Deallocate our thread tracking structure.
		LeaveCriticalSection(&SALockCS);
		free(pTThread);
	}
	return dwRetVal;
}

// This function exits the current thread and cleans up tracking for it.
// Call it in lieu of ExitThread() on Windows.
//
void ExitTrackedThread(DWORD dwExitCode)
{
	TrackedThread_t *prevTThread;
	TrackedThread_t *nextTThread;
	TrackedThread_t *pTThread;
	HeldSALock_t *pHeldSALock;
	CRITICAL_SECTION *pSurrogateLock;

	// Look up the current thread.
	DWORD dwThreadId = GetCurrentThreadId();
	EnterCriticalSection(&SALockCS);
	pTThread = FindTrackedThread(dwThreadId, &prevTThread);

	// Take it off the tracked thread list.
	if (pTThread)
	{
		ReleaseThreadsLocks(pTThread);
		nextTThread = pTThread->next;

		if (prevTThread)
		{
			prevTThread->next = nextTThread;
		}
		else if (TThread = pTThread)
		{
			TThread = nextTThread;
		}
		else
		{
			// Shouldn't get here.
			DebugBreak();
		}

		// Deallocate our thread tracking structure along with tracking for 
		// any held locks.
		//
		pHeldSALock = (HeldSALock_t *) pTThread->pHoldingSALock;
		while (pHeldSALock)
		{
			pSurrogateLock = pHeldSALock->pSurrogateLock;
			pHeldSALock = pHeldSALock->next;
			free(pHeldSALock);
		}
		free(pTThread);
	}

	// End the thread.
	LeaveCriticalSection(&SALockCS);
	ExitThread(0);
}

// This function looks up tracking for the specified lock.
//
SelfAwareLock_t * FindSelfAwareLock(CRITICAL_SECTION *lock)
{
	SelfAwareLock_t *pSALock = SALock;
	while (pSALock && lock != pSALock->lock)
	{
		pSALock = pSALock->next;
	}
	return pSALock;
}

// Given a lock tracking structure, this function looks up the surrogate 
// lock, if any, that's currently set up to take the place of the specified 
// lock.
//
CRITICAL_SECTION * FindSurrogateLock(SelfAwareLock_t *pSALock)
{
	CRITICAL_SECTION *pSurrogateLock = NULL;
	TrackedThread_t *pTThread = TThread;
	HeldSALock_t *pHeldSALock;

	while (pTThread)
	{
		if (pTThread->pHoldingSALock)
		{
			pHeldSALock = (HeldSALock_t *) pTThread->pHoldingSALock;
			while (pHeldSALock)
			{
				if (pHeldSALock->pSurrogateLock &&
					pHeldSALock->pSALock == pSALock)
				{
					pSurrogateLock = pHeldSALock->pSurrogateLock;
					break;
				}
				pHeldSALock = pHeldSALock->next;
			}
		}
		pTThread = pTThread->next;
	}

	return pSurrogateLock;
}

// This function sets up tracking for a new lock.
// Call it in lieu of InitializeCriticalSection() on Windows.
//
void InitializeSelfAwareLock(CRITICAL_SECTION *lock)
{
	SelfAwareLock_t *pSALock = 
	                   (SelfAwareLock_t *) malloc(sizeof(SelfAwareLock_t));
	SelfAwareLock_t *formerSALock;
	InitializeCriticalSection(lock);
	pSALock->lock = lock;
	formerSALock = SALock;
	SALock = pSALock;
	SALock->next = formerSALock;
	pSALock->pOwningTThread = NULL;
	pSALock->pWaitingTThread = NULL;
	pSALock->callerAddr = 0;
	return;
}

// This function acquires a lock, causing the current thread to wait if 
// another thread is holding the lock.  It will acquire a surrogate lock
// instead of the specified lock, if that's necessary to avoid a deadlock.
// Call it in lieu of EnterCriticalSection() on Windows.
//
void AcquireSelfAwareLock(CRITICAL_SECTION *lock, DWORD callerAddr)
{
	SelfAwareLock_t *pWaitingSALock = NULL;
	TrackedThread_t *pWaitingTThread = NULL;
	TrackedThread_t *pOwningTThread = NULL;
	SelfAwareLock_t *pSALock = NULL;
	CRITICAL_SECTION *pSurrogateLock = NULL;
	TrackedThread_t *pCurrentTThread = NULL;
	HeldSALock_t *lastHeldLock = NULL;
	HeldSALock_t *thisHeldLock = NULL;
	DWORD dwThreadId = GetCurrentThreadId();
	BOOL bEnter = TRUE;

	// Look up tracking data for the specified lock and for the current 
	// thread.
	//
	EnterCriticalSection(&SALockCS);
	pSALock = FindSelfAwareLock(lock);
	pCurrentTThread = FindTrackedThread(dwThreadId, NULL);

	if (pSALock)
	{
		pSALock->bEntering = TRUE;

		// If the lock we need is owned by another thread...
		if (pSALock->pOwningTThread && 
		    pSALock->pOwningTThread != pCurrentTThread)
		{
			pOwningTThread = pSALock->pOwningTThread;

			// ...and if that thread is waiting on a lock we own...
			if (pOwningTThread->pWaitingSALock)
			{
				pWaitingSALock = 
				        (SelfAwareLock_t *) pOwningTThread->pWaitingSALock;
				if (pOwningTThread == pWaitingSALock->pWaitingTThread ||
					pOwningTThread->pSurrogateLock)
				{
					// ...then don't grab this lock.
					bEnter = FALSE;
				}
			}
		}

		if (bEnter)
		{
			if (pCurrentTThread)
			{
				pSALock->bEntering = TRUE;
				lastHeldLock =
				          (HeldSALock_t *) pCurrentTThread->pHoldingSALock;

				// We might wait awhile.  Track this.
				pSALock->pWaitingTThread = pCurrentTThread;
				pCurrentTThread->pWaitingSALock = pSALock;
				pSALock->callerAddr = callerAddr;
				LeaveCriticalSection(&SALockCS);

				// We may have substituted another lock in place of the 
				// specified lock.  Such a surrogate lock exists until no 
				// thread holds it anymore, then the original lock can be 
				// safely used again.
				//
				pSurrogateLock = FindSurrogateLock(pSALock);
			}

			if (pSurrogateLock)
			{
				EnterCriticalSection(pSurrogateLock);
			}
			else
			{
				EnterCriticalSection(lock);
			}

			if (pCurrentTThread)
			{
				// If we were waiting, we no longer are.  Clear that tracking.
				pCurrentTThread->pWaitingSALock = NULL;
				pSALock->pWaitingTThread = NULL;

				EnterCriticalSection(&SALockCS);
				pSALock->callerAddr = 0;
				pSALock->pOwningTThread = pCurrentTThread;

				// Track held locks per thread.
				thisHeldLock = (HeldSALock_t *) malloc(sizeof(HeldSALock_t));
				thisHeldLock->pSALock = pSALock;
				thisHeldLock->next = lastHeldLock;
				pCurrentTThread->pHoldingSALock = (void *) thisHeldLock;

				// If another thead was about to deadlock with the current 
				// thread and averted the deadlock by creating a surrogate 
				// lock and continuing, then grab that surrogate lock here 
				// to prevent a race condition.
				//
				thisHeldLock->pSurrogateLock = 
				                           pCurrentTThread->pSurrogateLock;
				LeaveCriticalSection(&SALockCS);

				if (pCurrentTThread->pSurrogateLock)
				{
					EnterCriticalSection(pCurrentTThread->pSurrogateLock);
				}

				pSALock->bEntering = FALSE;
			}
		}
		else if (pCurrentTThread && pOwningTThread)
		{
			// Instead of deadlocking, create another lock that the thread 
			// competing with us can wait on.  Then continue.
			//
			pOwningTThread->pSurrogateLock = 
			    (CRITICAL_SECTION *) malloc(sizeof(CRITICAL_SECTION));
			InitializeCriticalSection(pOwningTThread->pSurrogateLock);
			HeldSALock_t *lastHeldLock = 
					  (HeldSALock_t *) pCurrentTThread->pHoldingSALock;
			HeldSALock_t *thisHeldLock = 
					 (HeldSALock_t *) malloc(sizeof(HeldSALock_t));
			thisHeldLock->pSALock = NULL;
			thisHeldLock->pSurrogateLock = pOwningTThread->pSurrogateLock;
			thisHeldLock->next = lastHeldLock;
			pCurrentTThread->pHoldingSALock = (void *) thisHeldLock;
			LeaveCriticalSection(&SALockCS);
			
			EnterCriticalSection(pOwningTThread->pSurrogateLock);
			EnterCriticalSection(&SALockCS);
			pCurrentTThread->pWaitingSALock = NULL;
			pOwningTThread->pWaitingSALock = (void *) thisHeldLock;
			pSALock->bEntering = FALSE;
			LeaveCriticalSection(&SALockCS);
		}
	}

	return;
}

// This function releases a lock.  If a surrogate lock was acquired 
// instead of the specified lock, this function will release the surrogate 
// lock and take it out of play if it's no longer needed.
// Call it in lieu of LeaveCriticalSection() on Windows.
//
void ReleaseSelfAwareLock(CRITICAL_SECTION *lock)
{
	DWORD dwThreadId = GetCurrentThreadId();
	TrackedThread_t *pCurrentTThread = NULL;
	SelfAwareLock_t *pSALock = NULL;
	HeldSALock_t *thisHeldLock = NULL;
	CRITICAL_SECTION *pSurrogateLock = NULL;

	// Look up tracking data for the specified lock and for the current thread.
	//
	EnterCriticalSection(&SALockCS);
	pSALock = FindSelfAwareLock(lock);
	pCurrentTThread = FindTrackedThread(dwThreadId, NULL);

	if (pCurrentTThread)
	{
		// Track the fact that this thread will now hold one less lock.
		thisHeldLock = (HeldSALock_t *) pCurrentTThread->pHoldingSALock;
		pCurrentTThread->pHoldingSALock = thisHeldLock->next;
		pSurrogateLock = thisHeldLock->pSurrogateLock;
		thisHeldLock->pSurrogateLock = NULL;

		if (!pSurrogateLock && thisHeldLock->next && 
		    !thisHeldLock->next->pSALock)
		{
			pSurrogateLock = thisHeldLock->next->pSurrogateLock;
			pCurrentTThread->pHoldingSALock = thisHeldLock->next->next;
			thisHeldLock->next->pSurrogateLock = NULL;
			free(thisHeldLock->next);
		}

		// If this thread grabbed a second lock in a deadlock-avoidance 
		// scenario, release that lock now.
		//
		if (pSurrogateLock)
		{
			LeaveCriticalSection(pSurrogateLock);

			// Note: This relies on the OwningThread element of the 
			//       CRITICAL_SECTION itself.
			//
			if (!pSALock->bEntering)
			{
			if (!pSALock->pOwningTThread && !pSALock->pWaitingTThread)
				{
					pCurrentTThread->pSurrogateLock = NULL;
					free(pSurrogateLock);
				}
			}
		}

		LeaveCriticalSection(&SALockCS);
	}

	LeaveCriticalSection(lock);

	if (pCurrentTThread && pSALock)
	{
		free(thisHeldLock);

		EnterCriticalSection(&SALockCS);
		if (pSALock->pWaitingTThread)
		{
			// Determine which thread now owns the lock, if any.
			//
			// Note: This relies on the OwningThread element of the 
			//       CRITICAL_SECTION itself.
			//
			pSALock->pOwningTThread = 
					   FindTrackedThreadByHandle(lock->OwningThread,
			                                 NULL);
		}
		else
		{
			pSALock->pOwningTThread = NULL;
		}

		pCurrentTThread->pSurrogateLock = NULL;
		LeaveCriticalSection(&SALockCS);
	}
	return;
}

// This function releases all of the tracked locks currently owned by 
// the current thread.  If lock tracking is current, invoking this function 
// before the thread terminates will guarantee that the thread won't still 
// hold locks after it's gone, causing a hang.  There's no equivalent 
// Windows API function.
//
void ReleaseThreadsLocks(TrackedThread_t *pTThread)
{
	SelfAwareLock_t *pSALock = NULL;
	CRITICAL_SECTION *pSurrogateLock = NULL;
	HeldSALock_t *pHeldSALock = NULL;

	while (pTThread->pHoldingSALock)
	{
		pHeldSALock = (HeldSALock_t *) pTThread->pHoldingSALock;
		pSALock = pHeldSALock->pSALock;
		pSurrogateLock = pHeldSALock->pSurrogateLock;

		if (pSurrogateLock)
		{
			pTThread->pHoldingSALock = pHeldSALock->next;
			LeaveCriticalSection(pSurrogateLock);
			// Don't free the surrogate lock and HeldSALock_t 
			// here, because an exiting thread might still run 
			// up against these items.
		}
		else if (pSALock)
		{
			ReleaseSelfAwareLock(pSALock->lock);
		}
	}

	return;
}

Listing 2: No more deadlocks

Listing 2 is intended only as a proof of concept and does not exhaustively cover all available Windows synchronization API functions. You'll almost certainly have to modify this code to meet your needs, rather than simply deploy it. The watchdog methods described here, or something similar to them, can fit virtually any platform that supports multithreaded applications. Though the code in Listing 2 is oriented toward native-code applications, the same techniques can be applied to Java or managed applications too. The locks used in the listings are critical sections, but other types of synchronization objects may benefit from similar deadlock protection.

You may be wondering about the overhead of the thread and lock tracking needed to prevent deadlocks. For most programs, the biggest slowdown will occur when locks are acquired and released. A number of memory operations must be performed, at these times, to enable deadlock protection as described here. The performance impact will depend on the number of threads your application creates, the frequency with which it acquires and releases locks, and the number of processors available to it. The memory overhead will be on the order of a fistful of rather small heap blocks, unless your program creates large numbers of threads. This modest overhead may be worthwhile to ensure that your application won't deadlock in the field.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video