(Deadlock Detector 개발) Shared library 활용 Deadlock with Mutex Locks Detect하기 + 코드

Shared Library의 Dynamic Loading

C에서는 shared object를 compile할 때가 아니라 runtime 때 load할 수 있게 해준다.

이 때 load된 함수들과 변수들은 실제 코드에 합쳐지게 된다.

예를 들어, 우리가 짠 rand() 함수를 가져오고 싶으면 다음과 같은 코드를 library file로 만들어준다.

#define _GNU_SOURCE

static int count = 0 ;

int rand()
{
    return count++ ; 
}

library file을 만드는 명령어는 다음과 같다.

gcc -shared -fPIC -o my_rand.so my_rand.c -ldl

만들어진 my_rand library file을 다음과 같은 파일과 함께 실행시켜줘보자

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int 
main ()
{
    int i ;

    srand(time(0x0)) ;

    for (i = 0 ; i < 10 ; i++) {
        printf("%d\n", rand()) ;
    }
}

명령어는 다음과 같다.

LD_PRELOAD=./my_rand.so ./my_rand

결과

만약 근데 우리가 함수를 직접 구현하지 않고 해당 똑같은 이름의 함수를 부르고 직접 부르고 싶다면

ex. rand() 함수 내에서 실제 rand() 함수를 구현하고 싶다면 어떻게 해야할까?

dlsym를 사용하자!

#define _GNU_SOURCE

static int count = 0 ;
int (*rand_cp)();
int rand()
{
    rand_cp = dlsym(RTLD_NEXT, "rand") ;
    return rand_cp() ; 
}    

dlsym을 사용하면 rand함수 내에서 원래 rand함수의 유사한 함수를 만들어줄 수 있다. 여기서는 rand_cp라는 function에 원래 rand 함수로 향하는 pointer를 얻게 한다.

결과

그럼 이제 보조 툴은 알았으니 배운 걸 코드로 짜보자.

문제 이해

Shared Library를 활용해서 Pthread에서 mutex lock이 deadlock에 걸린 경우를 찾아보자.

저번 post에서 이야기한 Resource Allocation Graph를 활용해서 Cycle 발생시 Deadlock 발생으로 간주하고 코드를 짜보자.

방법

pthread_mutex_lock과 pthread_mutex_unlock을 intercept한다.

lock인 경우에 해당 thread(P)와 resource(R) 사이의 P->R edge를 추가해준다.

Edge를 추가할 때 마다 Cycle을 확인하는데 이것은 DFS를 활용한다.

이때 만약 mutex의 주인이 없으면 R->P로 edge를 변경시켜준다.

unlock인 경우에는 R->P edge를 삭제한다.

과정

P가 R을 Acquire하려고 하면 P->R edge가 생긴다.
P가 R을 wait하다가 잡으면 P->R edge가 R->P edge로 변하게 된다.
P가 R을 release하면 R->P edge가 사라진다.

제한사항

현재 코드에서는 thread(P)의 최대 개수를 10개, mutex(R)의 최대 개수를 100개로 한정한다.

코드

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>
#include <execinfo.h>
#include <unistd.h>
#include <sys/syscall.h>

#define NUM_P 10
#define NUM_R 100
#define NUM_V NUM_P + NUM_R

int arr[NUM_V][NUM_V];

int V[NUM_V];

int count_P = 0;
int count_R = NUM_P;

int add_P(int id){
    if(count_P < NUM_P) V[count_P] = id;
    return count_P++;
}

int add_R(int id){
    if(count_R < NUM_V) V[count_R] = id;
    return count_R++;
}

int find_P(int id){
    for(int i = 0; i < count_P; i++){
        if(V[i] == id) return i;
    }
    return add_P(id);
}

int find_R(int id){
    for(int i = NUM_P; i < count_R; i++){
        if(V[i] == id) return i;
    }
    return add_R(id);
}

void add_E(int proc, int res){
    int i = find_P(proc);
    int j = find_R(res);
    printf("[%d, %d] Edge 생성\n", i, j);
    arr[i][j] = 1;
}

void transpose_E(int proc, int res){
    int i = find_R(res);
    int j = find_P(proc);
    printf("[%d, %d] Edge 삭제\n", j, i);
    printf("[%d, %d] Edge 생성\n", i, j);
    arr[j][i] = 0;
    arr[i][j] = 1;
}

void release_E(int proc, int res){
    int i = find_R(res);
    int j = find_P(proc);
    printf("[%d, %d] Edge 삭제\n", i, j);
    arr[i][j] = 0;
}

int DFS(int i, int *visited){
    for(int j = 0; j < NUM_V; j++){
        if(arr[i][j]){
            if(visited[j] == 1) return 1;

            visited[j] = 1;
            return DFS(j, visited);
        }
    }
    return 0;
}

int isCycle(int proc){
    int visited[NUM_V] = {0,};
    int i = find_P(proc);
    visited[i] = 1;
    return DFS(i, visited);
}



int (*pthread_create_cp)(pthread_t *, const pthread_attr_t *, void *(*) (void *), void *);
int (*pthread_mutex_init_cp)(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrictattr);
int (*pthread_mutex_lock_cp)(pthread_mutex_t *mutex);
int (*pthread_mutex_unlock_cp)(pthread_mutex_t *mutex);

int pthread_mutex_lock(pthread_mutex_t *mutex){

    pthread_mutex_lock_cp = dlsym(RTLD_NEXT, "pthread_mutex_lock") ;

    int P = syscall(SYS_gettid);
    int R = mutex;

    add_E(P, R);
    if(isCycle(P) == 1) printf("deadlock이요~\n");
    if(mutex->__data.__owner == 0) transpose_E(P, R);

    return pthread_mutex_lock_cp(mutex);
}

int pthread_mutex_unlock(pthread_mutex_t *mutex){

    pthread_mutex_unlock_cp = dlsym(RTLD_NEXT, "pthread_mutex_unlock") ;

    int P = syscall(SYS_gettid);
    int R = mutex;

    release_E(P, R);

    return pthread_mutex_unlock_cp(mutex);
}

결과

Dinning_deadlock과 같이 돌렸을 때

LD_PRELOAD=./my_mutex.so ./dinning_deadlock 

[0, 10] Edge 생성
[0, 10] Edge 삭제
[10, 0] Edge 생성
[1, 11] Edge 생성
[1, 11] Edge 삭제
[11, 1] Edge 생성
[2, 12] Edge 생성
[2, 12] Edge 삭제
[12, 2] Edge 생성
[0, 12] Edge 생성
[3, 13] Edge 생성
[3, 13] Edge 삭제
[13, 3] Edge 생성
[4, 14] Edge 생성
[4, 14] Edge 삭제
[14, 4] Edge 생성
[3, 10] Edge 생성
[1, 13] Edge 생성
[2, 14] Edge 생성
[4, 11] Edge 생성
deadlock이요~

ABBA와 같이 돌렸을 때

LD_PRELOAD=./my_mutex.so ./dinning_deadlock 

[0, 10] Edge 생성
[0, 10] Edge 삭제
[10, 0] Edge 생성
[1, 11] Edge 생성
[1, 11] Edge 삭제
[11, 1] Edge 생성
[0, 11] Edge 생성
[1, 10] Edge 생성
deadlock이요~

느낀점

그래프를 링크드리스트로 구현해볼까 하다가 결국에는 그냥 안전하게 array로 구현했다. 조금 아쉬움이 남는다.

일단, 제일 큰 문제는 지난 포스트에서 이야기했듯이 하나의 리소스를 여러명이 동시에 접근할 수 있게 된다면 아래 그림과 같이 Cycle이 발생하는게 항상 deadlock이 발생하지 않는다는 점이다.

이 문제에 대한 답이 좀 필요할 것 같다. 일단 고생했다!