DeadLock 탐지(C++)

#pragma once
//#include <map>
//#include <set>
//#include <vector>
//#include <stack>
//#include <unordered_map>

using namespace std;
class DeadLockProfiler
{
public:
	void PushLock(const char* name);
	void PopLock(const char* name);
	void CheckCycle();

private:

	void Dfs(int32 index);

private:
	unordered_map<const char*, int32> _nameToId;
	unordered_map<int32, const char*> _idToName;
	stack<int32> _lockStack; // tls에 선언해야 할듯?
	map<int32, set<int32>> _lockHistory;
	Mutex _lock;

private:
	vector<int32> _discoverOrder;
	int32 _discoverCount = 0;
	vector<bool> _finished;
	vector<int32> _parent;
};

 

#include "pch.h"
#include "DeadLockProfiler.h"

void DeadLockProfiler::PushLock(const char* name) {

	LockGuard guard(_lock);

	//아이디 찾기 or 발급
	int32 lockId = 0;

	auto findIt = _nameToId.find(name);
	if (findIt == _nameToId.end()) {
		lockId = static_cast<int32>(_nameToId.size());
		_nameToId[name] = lockId;
		_idToName[lockId] = name;
	}
	else {
		lockId = findIt->second;
	}

	//잡고 있는 락이 있다면
	if (_lockStack.empty() == false) {

		// 기존에 발견되지 않은 케이스라면 데드락 다시 확인
		const int32 prevId = _lockStack.top();
		if (lockId != prevId) { // 재귀호출은 deadLock이 아님 싸이클 확인할 필요 없음
			set<int32>& history = _lockHistory[prevId];
			if (history.find(lockId) == history.end()) {
				history.insert(lockId);
				CheckCycle();
			}
		}
	}

	_lockStack.push(lockId);

}

void DeadLockProfiler::PopLock(const char* name)
{
	LockGuard guard(_lock);

	if (_lockStack.empty()) {
		CRASH("MULTIPLE_UNLOCK");
	}

	int32 lockId = _nameToId[name];
	if (_lockStack.top() != lockId)
		CRASH("INVALID_UNLOCK");

	_lockStack.pop();
}

void DeadLockProfiler::CheckCycle()
{
	const int32 lockCount = static_cast<int32>(_nameToId.size());
	_discoverOrder = vector<int32>(lockCount, -1);
	_discoverCount = 0;
	_finished = vector<bool>(lockCount, false);
	_parent = vector<int32>(lockCount, -1);

	for (int32 lockId = 0; lockId < lockCount; lockId++) {
		Dfs(lockId);
	}

	_discoverOrder.clear();
	_finished.clear();
	_parent.clear();
}

void DeadLockProfiler::Dfs(int32 here)
{

	if (_discoverOrder[here] != -1)
		return;

	_discoverOrder[here] = _discoverCount++;

	// 모든 인접한 정점을 순회한다.
	auto findIt = _lockHistory.find(here);
	if (findIt == _lockHistory.end()) { // 현재 lock에 간선이 없음
		_finished[here] = true;
		return;
	}

	set<int32>& nextSet = findIt->second;
	for (int32 there : nextSet) {
		//아직 방문한 적이 없다면 방문함.
		if (_discoverOrder[there] == -1) {
			_parent[there] = here;
			Dfs(there);
			continue;
		}

		//here가 there보다 먼저 발견되었다면, there는 here의 후손이다. (순방향)
		if (_discoverOrder[here] < _discoverOrder[there])
			continue;

		if (_finished[there] == false) {

			printf("%s -> %s\n", _idToName[here], _idToName[there]);

			int32 now = here;
			while (true) {
				printf("%s -> %s\n", _idToName[_parent[now]], _idToName[now]);
				now = _parent[now];
				if (now == there)
					break;
			}
			CRASH("DEADLOCK_DETECTED");
		}

	}

	_finished[here] = true;


}