Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言

80 阅读 0 评论 53 点赞

我是靠谱客的博主清脆发夹，最近开发中收集的这篇文章主要介绍Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

死锁检测

死锁产生原因
构建一个死锁
使用hook检测死锁
- dlsym()函数
- pthread_self()函数
- hook使用场景
- 使用步骤
- 示例代码
使用图算法检测死锁
- 图的构建
- 图的使用
- 示例代码
总结
后言

死锁产生原因

死锁，是指多个线程或者进程在运行过程中因争夺资源而造成的一种僵局，当进程或者线程处于这种僵持状态，若无外力作用，它们将无法再向前推进。
如下图所示，线程 A 想获取线程 B 的锁，线程 B 想获取线程 C 的锁，线程 C 想获取线程 D 的锁，线程 D 想获取线程 A 的锁，从而构建了一个资源获取环。

如果有两个及以上的CPU占用率达到100%时，极可能是程序进入死锁状态。

死锁的存在是因为有资源获取环的存在，所以只要能检测出资源获取环，就等同于检测出死锁的存在。

构建一个死锁

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_funcA(void *arg)
{
	pthread_mutex_lock(&mutex1);
	sleep(1);
	pthread_mutex_lock(&mutex2);

	printf("funcA --> n");

	pthread_mutex_unlock(&mutex2);
	pthread_mutex_unlock(&mutex1);
}

void *thread_funcB(void *arg)
{
	pthread_mutex_lock(&mutex2);
	sleep(1);
	pthread_mutex_lock(&mutex3);

	printf("funcB --> n");

	pthread_mutex_unlock(&mutex3);
	pthread_mutex_unlock(&mutex2);
}

void *thread_funcC(void *arg)
{
	pthread_mutex_lock(&mutex3);
	sleep(1);
	pthread_mutex_lock(&mutex4);

	printf("funcC --> n");

	pthread_mutex_unlock(&mutex4);
	pthread_mutex_unlock(&mutex3);
}

void *thread_funcD(void *arg)
{
	pthread_mutex_lock(&mutex4);
	sleep(1);
	pthread_mutex_lock(&mutex1);

	printf("funcD --> n");

	pthread_mutex_unlock(&mutex1);
	pthread_mutex_unlock(&mutex4);
}


int main()
{
	pthread_t tid[4] = { 0 };
	
	pthread_create(&tid[0], NULL, thread_funcA, NULL);
	pthread_create(&tid[1], NULL, thread_funcB, NULL);
	pthread_create(&tid[2], NULL, thread_funcC, NULL);
	pthread_create(&tid[3], NULL, thread_funcD, NULL);

	pthread_join(tid[0], NULL);
	pthread_join(tid[1], NULL);
	pthread_join(tid[2], NULL);
	pthread_join(tid[3], NULL);

	return 0;
}

使用hook检测死锁

dlsym()函数

获取共享对象或可执行文件中符号的地址。
函数原型：

#include <dlfcn.h>

void *dlsym(void *handle, const char *symbol);

#define _GNU_SOURCE
#include <dlfcn.h>

void *dlvsym(void *handle, char *symbol, char *version);

// Link with -ldl.

描述：
函数dlsym()接受dlopen()返回的动态加载共享对象的“句柄”以及以空结尾的符号名，并返回该符号加载到内存中的地址。如果在指定对象或加载对象时dlopen()自动加载的任何共享对象中找不到该符号，dlsym()将返回NULL。（dlsym()执行的搜索是通过这些共享对象的依赖关系树进行的广度优先搜索。）

由于符号的值实际上可能是NULL（因此，dlsym()的NULL返回值不必指示错误），因此测试错误的正确方法是调用dlerror()以清除任何旧的错误条件，然后调用dlsym。

handle中可以指定两个特殊的伪句柄：

代码	含义
RTLD_DEFAULT	使用默认共享对象搜索顺序查找所需符号的第一个匹配项。搜索将包括可执行文件及其依赖项中的全局符号，以及使用RTLD_GLOBAL标志动态加载的共享对象中的符号。
RTLD_NEXT	在当前对象之后，按搜索顺序查找所需符号的下一个匹配项。这允许在另一个共享对象中为函数提供包装，例如，预加载共享对象中的函数定义可以查找并调用另一共享对象中提供的“真实”函数（或者在预加载有多层的情况下，函数的“下一个”定义）。

函数dlvsym（）的作用与dlsym（）相同，但使用版本字符串作为附加参数。

返回值：
成功时，这些函数返回与符号关联的地址。
失败时，返回NULL；可以使用dlerror()诊断错误的原因。

pthread_self()函数

获取调用线程的ID。
函数原型：

#include <pthread.h>

pthread_t pthread_self(void);

// Compile and link with -pthread.

说明：
函数的作用是返回调用线程的ID。这与创建此线程的pthread_create()调用中*thread中返回的值相同。

返回值：

此函数始终成功，返回调用线程的ID。

hook使用场景

（1）实现自己的协议栈，通过hook posix api。

使用步骤

（1）构建函数指针
（2）定义与目标函数一样的类型

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

pthread_mutex_lock_t	pthread_mutex_lock_f;
pthread_mutex_unlock_t	pthread_mutex_unlock_f;

（3）具体函数实现，函数名与目标函数名一致

int pthread_mutex_lock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

	printf("pthread_mutex_lock: %ld, %pn", selfid, mutex);
	// ...
	return 0;
}

int pthread_mutex_unlock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

	printf("pthread_mutex_unlock: %ld, %pn", selfid, mutex);
	// ...
	return 0;
}

（4）调用dlsym()函数，即钩子。

int init_hook()
{
	pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
	pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
	// ...
	return 0;
}

示例代码

#define _GNU_SOURCE
#include <dlfcn.h>


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


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

pthread_mutex_lock_t	pthread_mutex_lock_f;
pthread_mutex_unlock_t	pthread_mutex_unlock_f;

int pthread_mutex_lock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

	pthread_mutex_lock_f(mutex);
	printf("pthread_mutex_lock: %ld, %pn", selfid, mutex);
	
	return 0;
}

int pthread_mutex_unlock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

	pthread_mutex_unlock_f(mutex);
	printf("pthread_mutex_unlock: %ld, %pn", selfid, mutex);

	return 0;
}

int init_hook()
{
	pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
	pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
	return 0;
}

#if 1 // debug

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_funcA(void *arg)
{
	pthread_mutex_lock(&mutex1);
	sleep(1);
	pthread_mutex_lock(&mutex2);

	printf("funcA --> n");

	pthread_mutex_unlock(&mutex2);
	pthread_mutex_unlock(&mutex1);
}

void *thread_funcB(void *arg)
{
	pthread_mutex_lock(&mutex2);
	sleep(1);
	pthread_mutex_lock(&mutex3);

	printf("funcB --> n");

	pthread_mutex_unlock(&mutex3);
	pthread_mutex_unlock(&mutex2);
}

void *thread_funcC(void *arg)
{
	pthread_mutex_lock(&mutex3);
	sleep(1);
	pthread_mutex_lock(&mutex4);

	printf("funcC --> n");

	pthread_mutex_unlock(&mutex4);
	pthread_mutex_unlock(&mutex3);
}

void *thread_funcD(void *arg)
{
	pthread_mutex_lock(&mutex4);
	sleep(1);
	pthread_mutex_lock(&mutex1);

	printf("funcD --> n");

	pthread_mutex_unlock(&mutex1);
	pthread_mutex_unlock(&mutex4);
}


int main()
{

	init_hook();

	pthread_t tid[4] = { 0 };
	
	pthread_create(&tid[0], NULL, thread_funcA, NULL);
	pthread_create(&tid[1], NULL, thread_funcB, NULL);
	pthread_create(&tid[2], NULL, thread_funcC, NULL);
	pthread_create(&tid[3], NULL, thread_funcD, NULL);

	pthread_join(tid[0], NULL);
	pthread_join(tid[1], NULL);
	pthread_join(tid[2], NULL);
	pthread_join(tid[3], NULL);

	return 0;
}

#endif

缺点：这种方式在少量锁情况下还可以分析，在大量锁使用的情况，分析过程极为困难。

使用图算法检测死锁

死锁检测可以利用图算法，检测有向图是否有环。

图的构建

（1）矩阵

	指向 1	指向 2	指向 3	指向 …
节点 1
节点 2
节点 3
节点 …

（2）邻接表
数据结构原理示意图：

“图”连接：

图的使用

先新增节点再新增边。
（1）每创建一个线程，新增一个节点；注意，不是线程创建的时候就要加节点（有些线程不会用到锁），而是线程调用锁（以互斥锁为例，pthread_mutex_lock() ）的时候才添加节点。
（2）线程加锁（以互斥锁为例，pthread_mutex_lock() ）的时候，并且检测到锁已经占用，则新增一条边。
（3）移除边，调用锁（以互斥锁为例，pthread_mutex_lock() ）前，如果此时锁没有被占用，并且该边存在，则移除边。
（4）移除节点是在解锁之后。

三个原语操作：
（1）加锁之前的操作，lock_before()；
（2）加锁之后的操作，lock_after()；
（3）解锁之后的操作，unlock_after()；

示例代码

#define _GNU_SOURCE
#include <dlfcn.h>

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define ENABLE_GRAPH	1

#if ENABLE_GRAPH

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

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

#include <unistd.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 task_graph *tg = NULL;
int path[MAX + 1];
int visited[MAX];
int k = 0;
int deadlock = 0;

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 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 source_type type) {

	if (search_vertex(type) == -1) {

		tg->list[tg->num].s = type;
		tg->list[tg->num].next = NULL;
		tg->num++;

	}

}


int add_edge(struct source_type from, struct source_type to) {

	add_vertex(from);
	add_vertex(to);

	struct vertex *v = &(tg->list[search_vertex(from)]);

	while (v->next != NULL) {
		v = v->next;
	}

	v->next = create_vertex(to);

}


int verify_edge(struct source_type i, struct source_type j) {

	if (tg->num == 0) return 0;

	int idx = search_vertex(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 source_type from, struct source_type to) {

	int idxi = search_vertex(from);
	int idxj = search_vertex(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(void) {

	int i = 0;

	printf("deadlock : ");
	for (i = 0; i < k - 1; i++) {

		printf("%ld --> ", tg->list[path[i]].s.id);

	}

	printf("%ldn", tg->list[path[i]].s.id);

}

int DFS(int idx) {

	struct vertex *ver = &tg->list[idx];
	if (visited[idx] == 1) {

		path[k++] = idx;
		print_deadlock();
		deadlock = 1;

		return 0;
	}

	visited[idx] = 1;
	path[k++] = idx;

	while (ver->next != NULL) {

		DFS(search_vertex(ver->next->s));
		k--;

		ver = ver->next;

	}


	return 1;

}


int search_for_cycle(int idx) {



	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(search_vertex(ver->next->s));
		ver = ver->next;
	}

}


#endif





int search_lock(uint64 lock) {

	int i = 0;

	for (i = 0; i < tg->lockidx; i++) {

		if (tg->locklist[i].lock_id == lock) {
			return i;
		}
	}

	return -1;
}

int search_empty_lock(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 inc(int *value, int add) {

	int old;

	__asm__ volatile(
		"lock;xaddl %2, %1;"
		: "=a"(old)
		: "m"(*value), "a" (add)
		: "cc", "memory"
		);

	return old;
}


void lock_before(uint64 thread_id, uint64 lockaddr) {


	int idx = 0;
	// list<threadid, toThreadid>

	for (idx = 0; idx < tg->lockidx; idx++) {
		
		if ((tg->locklist[idx].lock_id == lockaddr)) { // 如果锁已存在

#if 1

			struct source_type from;
			from.id = thread_id;
			from.type = PROCESS;
			add_vertex(from);	// 添加节点

			struct source_type to;
			to.id = tg->locklist[idx].id;
			tg->locklist[idx].degress++; // 统计抢锁的用户
			to.type = PROCESS;
			add_vertex(to);

			if (!verify_edge(from, to)) {// 如果边不存在
				add_edge(from, to); // 则加边
			}
#else
			struct source_type from;
			from.id = thread_id;
			from.type = PROCESS;

			struct source_type to;
			to.id = tg->locklist[idx].id;
			tg->locklist[idx].degress++;
			to.type = PROCESS;

			add_edge(from, to); // 加边

#endif

		}
	}
}

void lock_after(uint64 thread_id, uint64 lockaddr) {

	int idx = 0;
	if (-1 == (idx = search_lock(lockaddr))) {  // 锁不存在，lock list opera 
		
		/*添加新的节点*/

		int eidx = search_empty_lock(lockaddr);

		tg->locklist[eidx].id = thread_id;
		tg->locklist[eidx].lock_id = lockaddr;

		inc(&tg->lockidx, 1);//原子操作

	}
	else {

		/* 当A调用lock时，B已占用，就建立了边，
		当B释放锁并且A抢到锁，需要把之前加的边移除*/

		struct source_type from;
		from.id = thread_id;
		from.type = PROCESS;

		struct source_type to;
		to.id = tg->locklist[idx].id;
		tg->locklist[idx].degress--;
		to.type = PROCESS;

		if (verify_edge(from, to)) //如果边存在
			remove_edge(from, to); // 则移除


		tg->locklist[idx].id = thread_id;

	}

}

void unlock_after(uint64 thread_id, uint64 lockaddr) {


	int idx = search_lock(lockaddr);

	if (tg->locklist[idx].degress == 0) {//用户数为0才删除节点
		tg->locklist[idx].id = 0;
		tg->locklist[idx].lock_id = 0;
		//inc(&tg->lockidx, -1);
	}

}

/********************* 检测死锁 start ***************************/

void check_dead_lock(void) {

	int i = 0;

	deadlock = 0;
	for (i = 0; i < tg->num; i++) {
		if (deadlock == 1) break;
		search_for_cycle(i);
	}

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

}


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);

}

/********************* 检测死锁 end ***************************/


/********************* hook start ***************************/

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

pthread_mutex_lock_t	pthread_mutex_lock_f;
pthread_mutex_unlock_t	pthread_mutex_unlock_f;

int pthread_mutex_lock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

#if ENABLE_GRAPH

	lock_before(selfid, (uint64)mutex);

	pthread_mutex_lock_f(mutex);
	lock_after(selfid, (uint64)mutex);

#else

	pthread_mutex_lock_f(mutex);

#endif

	printf("pthread_mutex_lock: %ld, %pn", selfid, mutex);
	
	return 0;
}

int pthread_mutex_unlock(pthread_mutex_t *mutex)
{
	pthread_t selfid = pthread_self();

	pthread_mutex_unlock_f(mutex);

#if ENABLE_GRAPH
	unlock_after(selfid, (uint64)mutex);
#endif

	printf("pthread_mutex_unlock: %ld, %pn", selfid, mutex);

	return 0;
}

int init_hook()
{
	pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");
	pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
	return 0;
}

/********************* hook end ***************************/

#if 1 // debug

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_funcA(void *arg)
{
	pthread_mutex_lock(&mutex1);
	sleep(1);
	pthread_mutex_lock(&mutex2);

	printf("funcA --> n");

	pthread_mutex_unlock(&mutex2);
	pthread_mutex_unlock(&mutex1);
}

void *thread_funcB(void *arg)
{
	pthread_mutex_lock(&mutex2);
	sleep(1);
	pthread_mutex_lock(&mutex3);

	printf("funcB --> n");

	pthread_mutex_unlock(&mutex3);
	pthread_mutex_unlock(&mutex2);
}

void *thread_funcC(void *arg)
{
	pthread_mutex_lock(&mutex3);
	sleep(1);
	pthread_mutex_lock(&mutex4);

	printf("funcC --> n");

	pthread_mutex_unlock(&mutex4);
	pthread_mutex_unlock(&mutex3);
}

void *thread_funcD(void *arg)
{
	pthread_mutex_lock(&mutex4);
	sleep(1);
	pthread_mutex_lock(&mutex1);

	printf("funcD --> n");

	pthread_mutex_unlock(&mutex1);
	pthread_mutex_unlock(&mutex4);
}


int main()
{

	init_hook();

#if ENABLE_GRAPH

	start_check();
	printf("start check dead lock.n");
#endif

	pthread_t tid[4] = { 0 };
	
	pthread_create(&tid[0], NULL, thread_funcA, NULL);
	pthread_create(&tid[1], NULL, thread_funcB, NULL);
	pthread_create(&tid[2], NULL, thread_funcC, NULL);
	pthread_create(&tid[3], NULL, thread_funcD, NULL);

	pthread_join(tid[0], NULL);
	pthread_join(tid[1], NULL);
	pthread_join(tid[2], NULL);
	pthread_join(tid[3], NULL);

	return 0;
}

#endif

总结

死锁的产生是因为多线程之间存在交叉申请锁的情况，因争夺资源而造成的一种僵局。
hook使用：
（1）定义与目标函数一样的类型；
（2）具体函数实现，函数名与目标函数名一致；
（3）调用dlsym()函数，初始化hook。

死锁检测可以使用图算法，通过检测有向图是否有环判断是否有死锁。

后言

本专栏知识点是通过<零声教育>的系统学习，进行梳理总结写下文章，对c/c++linux系统提升感兴趣的读者，可以点击链接,详细查看详细的服务:C/C++服务器

最后

以上就是清脆发夹为你收集整理的Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言的全部内容，希望文章能够帮你解决Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Linux基础组件
浏览次数：80 次浏览
发布日期：2023-10-31 10:11:40
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_18_f1_14__7__18_y.html

Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言

概述

死锁检测

死锁产生原因

构建一个死锁

使用hook检测死锁

dlsym()函数

pthread_self()函数

hook使用场景

使用步骤

示例代码

使用图算法检测死锁

图的构建

图的使用

示例代码

总结

后言

最后

评论列表共有 0 条评论

发表评论取消回复

Linux基础组件之死锁检测死锁产生原因构建一个死锁使用hook检测死锁使用图算法检测死锁总结后言

概述

死锁检测

死锁产生原因

构建一个死锁

使用hook检测死锁

dlsym()函数

pthread_self()函数

hook使用场景

使用步骤

示例代码

使用图算法检测死锁

图的构建

图的使用

示例代码

总结

后言

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复