^-^
后端技术_手写死锁检测组件
最近更新：2024-09-23   |   字数总计：1.5k   |   阅读估时：8分钟   |   阅读量：次
  1. 判断死锁
    1. 矩阵有向图
    2. Hook技术实现死锁检测

判断死锁

  • 判断有向图是否有环

矩阵有向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// graph.h
#ifndef GRAPH_H

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long int uint64;
#define MAX		100
enum Type {PROCESS, RESOURCE};
struct source_type {
	uint64 id;
	enum Type type;
	uint64 lock_id;
	int degress;
};
struct vertex {
	struct source_type s;
	struct vertex *next;
};

struct task_graph {
	struct vertex list[MAX];
	int num;
	struct source_type locklist[MAX];
	int lockidx;
	pthread_mutex_t mutex;
};

struct vertex *create_vertex(struct source_type type);

int search_vertex( struct task_graph *tg, struct source_type type);

void add_vertex(struct task_graph *tg, struct source_type type);

int add_edge(struct task_graph *tg, struct source_type from, struct source_type to);

int verify_edge(struct task_graph *tg, struct source_type i, struct source_type j) ;

int remove_edge(struct task_graph *tg, struct source_type from, struct source_type to) ;

void print_deadlock(struct task_graph *tg, int *path, int k) ;

int DFS(struct task_graph *tg, int idx, int* visited, int* path, int *k , int *deadlock) ;

int search_for_cycle(struct task_graph *tg, int idx, int* visited, int* path, int *k, int *deadlock);

int search_empty_lock(struct task_graph *tg, uint64 lock) ;

int search_lock(struct task_graph *tg, uint64 lock) ;

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// graph.c
#define _GNU_SOURCE
#include "graph.h"

struct vertex *create_vertex(struct source_type type) {
	struct vertex *tex = (struct vertex *)malloc(sizeof(struct vertex ));
	tex->s = type;
	tex->next = NULL;
	return tex;
}

int search_vertex( struct task_graph *tg, struct source_type type) {
	int i = 0;
	for (i = 0;i < tg->num;i ++) {
		if (tg->list[i].s.type == type.type && tg->list[i].s.id == type.id) {
			return i;
		}
	}
	return -1;
}

void add_vertex(struct task_graph *tg, struct source_type type) {
	if (search_vertex(tg, type) == -1) {
		tg->list[tg->num].s = type;
		tg->list[tg->num].next = NULL;
		tg->num ++;
	}
}

int add_edge(struct task_graph *tg, struct source_type from, struct source_type to) {
	add_vertex(tg, from);
	add_vertex(tg, to);
	struct vertex *v = &(tg->list[search_vertex(tg, from)]);
	while (v->next != NULL) {
		v = v->next;
	}
	v->next = create_vertex(to);
}


int verify_edge(struct task_graph *tg, struct source_type i, struct source_type j) {
	if (tg->num == 0) return 0;
	int idx = search_vertex(tg, i);
	if (idx == -1) {
		return 0;
	}
	struct vertex *v = &(tg->list[idx]);
	while (v != NULL) {
		if (v->s.id == j.id) return 1;
		v = v->next;
	}
	return 0;
}


int remove_edge(struct task_graph *tg, struct source_type from, struct source_type to) {
	int idxi = search_vertex(tg, from);
	int idxj = search_vertex(tg, to);
	if (idxi != -1 && idxj != -1) {
		struct vertex *v = &tg->list[idxi];
		struct vertex *remove;
		while (v->next != NULL) {
			if (v->next->s.id == to.id) {
				remove = v->next;
				v->next = v->next->next;
				free(remove);
				break;
			}
			v = v->next;
		}
	}
}


void print_deadlock(struct task_graph *tg, int *path, int k) {
	int i = 0;
	printf("cycle : ");
	for (i = 0;i < k-1;i ++) {
		printf("%ld --> ", tg->list[path[i]].s.id);
	}
	printf("%ld\n", tg->list[path[i]].s.id);
}

int DFS(struct task_graph *tg, int idx, int* visited, int* path, int *k , int *deadlock) {
	struct vertex *ver = &tg->list[idx];
	if (visited[idx] == 1) {
		path[(*k)++] = idx;
		print_deadlock(tg, path, *k);
		(*deadlock) = 1;
		return 0;
	}

	visited[idx] = 1;
	path[(*k)++] = idx;

	while (ver->next != NULL) {
		DFS(tg, search_vertex(tg, ver->next->s), visited, path, k, deadlock);
		(*k) --;
		ver = ver->next;
	}
	return 1;
}


int search_for_cycle(struct task_graph *tg, int idx, int* visited, int* path, int *k, int *deadlock) {
	struct vertex *ver = &tg->list[idx];
	visited[idx] = 1;
	(*k) = 0;
	path[(*k)++] = idx;
	while (ver->next != NULL) {
		int i = 0;
		for (i = 0;i < tg->num;i ++) {
			if (i == idx) continue;
			visited[i] = 0;
		}

		for (i = 1;i <= MAX;i ++) {
			path[i] = -1;
		}
		(*k) = 1;

		DFS(tg, search_vertex(tg, ver->next->s), visited, path, k, deadlock);
		ver = ver->next;
	}

}

int search_empty_lock(struct task_graph *tg, uint64 lock) {

	int i = 0;
	
	for (i = 0;i < tg->lockidx;i ++) {
		
		if (tg->locklist[i].lock_id == 0) {
			return i;
		}
	}

	return tg->lockidx;

}

int search_lock(struct task_graph *tg, uint64 lock) {

	int i = 0;
	
	for (i = 0;i < tg->lockidx;i ++) {
		
		if (tg->locklist[i].lock_id == lock) {
			return i;
		}
	}

	return -1;
}

Hook技术实现死锁检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
// build : gcc -o deadlock graph.c deadlock.c -lpthread -ldl

#define _GNU_SOURCE
#include <dlfcn.h>

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdint.h>
#include "graph.h"

#define ENABLE_HOOK 1

#if ENABLE_HOOK

int path[MAX+1];
int visited[MAX];
int k = 0;
int deadlock = 0;
struct task_graph *tg = NULL;

// 原语操作1
void lock_before(uint64_t tid, uint64_t lockaddr)
{
    int idx = 0;
    for (idx=0 ; idx<tg->lockidx ; idx++) {
        if (tg->locklist[idx].lock_id == lockaddr) { // 该资源已经有线程占用了，此时加入一条等待边
            struct source_type from;
            from.id = tid;
            from.type = PROCESS;
            add_vertex(tg, from);

            struct source_type to;
            to.id = tg->locklist[idx].id;
            to.type = PROCESS;
            add_vertex(tg, to);

            tg->locklist[idx].degress ++;
            if (!verify_edge( tg,from, to))
                add_edge(tg, from, to);
        }
    }
}

// 原语操作2
void lock_after(uint64_t tid, uint64_t lockaddr)
{
    // 在申请资源成功时会走到这里
    int idx = 0;
	if (-1 == (idx = search_lock(tg, lockaddr))) { 
        // 该资源以前没有被人占用过，从原先的空间里写入一个点
		int eidx = search_empty_lock(tg, lockaddr);
		tg->locklist[eidx].id = tid;
		tg->locklist[eidx].lock_id = lockaddr;
		tg->lockidx ++;
	} else {
        // 该资源以前被人占用过，但是目前该线程成功加锁了，所以要消除原来的边
		struct source_type from;
		from.id = tid;
		from.type = PROCESS;
		add_vertex(tg, from);
		struct source_type to;
		to.id = tg->locklist[idx].id;
		to.type = PROCESS;
		add_vertex(tg, to);

		tg->locklist[idx].degress --;
		if (verify_edge(tg, from, to))
			remove_edge(tg, from, to);
		tg->locklist[idx].id = tid;
	}
}

// 原语操作3
void unlock_after(uint64_t tid, uint64_t lockaddr)
{
    int idx = search_lock(tg, lockaddr);
    // 将该点的内容清空，之后再重复使用
	if (tg->locklist[idx].degress == 0) {
		tg->locklist[idx].id = 0;
		tg->locklist[idx].lock_id = 0;
	}

}

// hook pthread_mutex_lock
typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
pthread_mutex_lock_t pthread_mutex_lock_f;

typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);
pthread_mutex_unlock_t pthread_mutex_unlock_f;

int pthread_mutex_lock(pthread_mutex_t *mutex){
    pthread_t selfid = pthread_self();
    lock_before((uint16_t)selfid, (uint16_t)mutex);
    pthread_mutex_lock_f(mutex);
    lock_after((uint16_t)selfid, (uint16_t)mutex);
    printf("[%s:%s:%d] pthread_mutex_lock, selfid:%ld, %p\n", __FILE__, __func__, __LINE__, selfid, mutex);
}

int pthread_mutex_unlock(pthread_mutex_t *mutex){
    pthread_t selfid = pthread_self();
    
    pthread_mutex_unlock_f(mutex);
    unlock_after((uint16_t)selfid, (uint16_t)mutex);
    printf("[%s:%s:%d] pthread_mutex_unlock, selfid:%ld, %p\n", __FILE__, __func__, __LINE__, selfid, mutex);
}

void init_hook(void)
{
    if(!pthread_mutex_lock_f)
        pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
    if(!pthread_mutex_unlock_f)
        pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
}

void check_dead_lock(void) {
	int i = 0;

	deadlock = 0;
	for (i = 0;i < tg->num;i ++) {
		if (deadlock == 1) break;
        if(tg == NULL)
        {
            printf("check_dead_lock tg == NULL\n");
        }
		search_for_cycle(tg, i, visited, path, &k, &deadlock);
	}

	if (deadlock == 0) {
		printf("no deadlock\n");
	}

}

static void *thread_routine(void *args) {
	while (1) {
		sleep(5);
		check_dead_lock();
	}
}

void start_check(void) {
	tg = (struct task_graph*)malloc(sizeof(struct task_graph));
	tg->num = 0;
	tg->lockidx = 0;
	pthread_t tid;
	pthread_create(&tid, NULL, thread_routine, NULL);
}

#endif

pthread_mutex_t r1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r4 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r5 = PTHREAD_MUTEX_INITIALIZER;

void *t1_cb(void *arg)
{
    pthread_t selfid = pthread_self();
    printf("t1 id:%ld\n", selfid);
    pthread_mutex_lock(&r1);
    sleep(1);
    pthread_mutex_lock(&r2);

    pthread_mutex_unlock(&r2);

    pthread_mutex_unlock(&r1);
}

void *t2_cb(void *arg)
{
    pthread_t selfid = pthread_self();
    printf("t2 id:%ld\n", selfid);
    pthread_mutex_lock(&r2);
    sleep(1);
    pthread_mutex_lock(&r3);

    pthread_mutex_unlock(&r3);
    

    pthread_mutex_unlock(&r2);
}
void *t3_cb(void *arg)
{
    pthread_t selfid = pthread_self();
    printf("t3 id:%ld\n", selfid);
    pthread_mutex_lock(&r3);
    sleep(1);
    pthread_mutex_lock(&r4);

    pthread_mutex_unlock(&r4);
    pthread_mutex_unlock(&r3);
}
void *t4_cb(void *arg)
{
    pthread_t selfid = pthread_self();
    printf("t4 id:%ld\n", selfid);
    pthread_mutex_lock(&r4);
    sleep(1);
    pthread_mutex_lock(&r5);

    pthread_mutex_unlock(&r5);
    pthread_mutex_unlock(&r4);
}
void *t5_cb(void *arg)
{
    pthread_t selfid = pthread_self();
    printf("t5 id:%ld\n", selfid);
    pthread_mutex_lock(&r5);
    sleep(1);
    pthread_mutex_lock(&r1);

    pthread_mutex_unlock(&r1);
    pthread_mutex_unlock(&r5);
}

int main()
{
    init_hook();
    start_check();

    pthread_t t1,t2,t3,t4,t5;

    pthread_create(&t1, NULL, t1_cb, NULL);
    pthread_create(&t2, NULL, t2_cb, NULL);
    pthread_create(&t3, NULL, t3_cb, NULL);
    pthread_create(&t4, NULL, t4_cb, NULL);
    pthread_create(&t5, NULL, t5_cb, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);
    pthread_join(t4, NULL);
    pthread_join(t5, NULL);

    printf("complete\n");
}
2024-03-04 该篇文章被 Cleofwine 归为分类: 服务端

上一篇：后端技术_手写内存泄漏检测组件（施工） 下一篇：后端技术_定时器方案红黑树和时间轮和最小堆
© 2023-2026 Cleofwine / Email / GitHub / 浙ICP备2024136127号
🌙赠我弯弯一枚月，也赠予我晚星⭐ 本站由Hexo驱动｜使用Hexo-theme-A4主题