12_lock profiler

먼저 Mutex가 3개가 있고, 이들의 잠금 순서는 다음과 같다.

A-B-C

상황 1

아래와 같은 상황은 당연히 deadlock이 일어나지 않는다.


lock(A);
lock(B);
lock(C);
unlock(C);
unlock(B);
unlock(A);

상황 2

아래와 같은 상황도 deadlock이 일어나지 않는다.


lock(A);
lock(B);
unlock(B);
unlock(A);

상황 3

아래와 같은 상황도 deadlock이 일어나지 않는다.


lock(B);
lock(C);
unlock(C);
unlock(B);

상황 4

아래와 같은 상황은 deadlock을 유발할 수 있다.


lock(B);
lock(A);
unlock(A);
unlock(B);

상황 5

아래와 같은 상황은 deadlock을 유발할 수 있다.


lock(C);
lock(B);
unlock(B);
unlock(C);

즉, A-B-C순으로 lock과 unlock을 하지 않으면 deadlock을 유발할 수 있다.

A-B-C와 같은 단순한 구조일 때는 쉽게 데드락을 예방할 수는 있지만


 (사실 단순하다 하더라도 사람은 실수를 할 수 있다.)

위와 같은 구조라면 쉽게 데드락을 예방할 수 없을 것이다.

따라서, 위의 lock과 unlock의 순서를 보장할 수 있는 profiler가 필요하게 된다.

코드

DeadLockProfiler.h


#include <stack>
#include <map>
#include <vector>

using NameToId = unordered_map<const char*, i32>;
using IdToName = unordered_map<i32, const char* >;

class DeadLockProfiler
{
public:
 void push_lock(const char* name);
 void pop_lock(const char* name);
 void check_cycle();

private:
 void dfs(i32 index);

private:
 NameToId   _name_to_ld;
 IdToName   _id_to_name;
 stack<i32>   _lock_stack; // lock 추적
 map<i32, set<i32>>  _lock_history; // 간선에 대한 정보

 Mutex _lock;

private:
 vector<i32> _discover_order; // 노드 순서 기록
 i32 _discorver_count = 0;  // 노드 발견 순서
 vector<bool> _finished;   // Dfs 종료여부
 vector<i32> _parent;
};

DeadLockProfiler.cpp


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

void DeadLockProfiler::push_lock(const char* name)
{
 LockGuard guard(_lock);
 i32 lock_id = 0;

 // find or insert
 auto find_iter = _name_to_ld.find(name);
 if (find_iter == _name_to_ld.end()) {
  lock_id = static_cast<i32>(_name_to_ld.size());
  _name_to_ld[name] = lock_id;
  _id_to_name[lock_id] = name;
 }
 else {
  lock_id = find_iter->second;
 }
  // lock order check
 if (_lock_stack.empty() == false) {
  // Dead lock check
  const i32 prev_id = _lock_stack.top();
  if (lock_id != prev_id) {
   set<i32>& history = _lock_history[prev_id];
   if (history.find(lock_id) == history.end()) {
    history.insert(lock_id);
    check_cycle();
   }
  }
 }

 _lock_stack.push(lock_id);
}

push lock은 mutex에 이름을 부여 하면서 lock을 수행한다.

코드의 설명을 위해 lock은 A, unlock은 ~A와 같이 표현하겠다.

해당 이름의 lock을 찾고 없으면 _name_to_id와 _id_to_name에 insert를 수행한다.

만약, 해당 lock이 마지막으로 들어온 lock과 같으면 dead_lock이 있을 수 없으므로 해당 lock에 대한 id를 _lock_stack에 넣어 기록한다.

반대의 상황이면 DeadLock을 유발할 수 있는지 체크해야한다.

_lock_stack의 가장 위의 lock_id를 가져온다.
만약, 가장 위의 lock_id와 같다면 A->A->~A->~A가 되므로 문제가 생기지 않기에 check할 필요가 없다.
반대의 상황이면 _lock_history를 가져와서 최상위 lock을 한 후 자신이 lock된 적이 있었는지 검사한다.
만약, 처음 lock 되었었다면 history에 기록후 문제가 없는지 check_cycle을 해본다.



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

 if (_lock_stack.empty()) {
  CRASH("MULTIPLE UNLOCK");
 }

 i32 lock_id = _name_to_ld[name];
 if (_lock_stack.top() != lock_id) {
  CRASH("INVALID ID UNLOCK"); // push pop order is wrong
 }

 _lock_stack.pop();
}

_lock_stack이 empty인데 unlock이 들어온다면, lock과 unlock이 매치가 되지 않은 것이므로 해제


void DeadLockProfiler::check_cycle()
{
 const i32 lock_count = static_cast<i32>(_name_to_ld.size());
 _discover_order = vector<i32>(lock_count, -1);
 _discorver_count = 0;
 _finished = vector<bool>(lock_count, -1);
 _parent = vector<i32>(lock_count, -1);

 for (i32 lock_id = 0; lock_id < lock_count; lock_id++) {
  dfs(lock_id);
 }
 _discover_order.clear();
 _finished.clear();
 _parent.clear();
}


void DeadLockProfiler::dfs(i32 here)
{
 if (_discover_order[here] != -1)
  return;

 _discover_order[here] = _discorver_count++;

 auto find_iter = _lock_history.find(here);
 if (find_iter == _lock_history.end()) {
  // 스레드 id가 here인 lock을 잡으면서 다른 lock을 잡은 적이 없다.
  _finished[here] = true;
  return;
 }

 set<i32>& next_set = find_iter->second;

 for (i32 there : next_set) {
  // no visit
  if (_discover_order[there] == -1) {
   _parent[there] = here;
   dfs(there);
   continue;
  }

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

  // 순방향이 아니고 Dfs(there)가 아직 종료하지 않았다면, there는 here의 부모이다(역방향 간선)
  if (_finished[there] == false) {
   printf("%s -> %s\\n", _id_to_name[here], _id_to_name[there]);
   i32 now = here;
   while (true) {
    printf("%s -> %s\\n", _id_to_name[_parent[now]], _id_to_name[now]);
    now = _parent[now];
    if (now == there) {
     break;
    }
   }

   CRASH("DEADLOCK DETECTED");
  }
 }

 _finished[here] = true;
}