首页 > 代码库 > Linux内核中的算法和数据结构

Linux内核中的算法和数据结构

2024-09-14 08:37:49   217人阅读

算法和数据结构纷繁复杂，但是对于Linux Kernel开发人员来说重点了解Linux内核中使用到的算法和数据结构很有必要。

在一个国外问答平台stackexchange.com的Theoretical Computer Science子板有一篇讨论实际使用中的算法和数据结构，Vijay D做出的详细的解答，其中有一部分是Basic Data Structures and Algorithms in the Linux Kernel对Linux内核中使用到的算法和数据结构做出的归纳整理。详情参考这里。

同时有一篇中文翻译在https://linux.cn/article-2317-1.html可以找到。

下面就以Vijay D的回答作为蓝本进行学习总结。

测试方法准备

由于需要在内核中进行代码测试验证，完整编译安装内核比较耗时耗力。准备采用module形式来验证。

Makefile

obj-m:=linked-list.o

KERNELBUILD:=/lib/modules/$(shell uname -r)/build

default:
        make -C ${KERNELBUILD} M=$(shell pwd) modules
clean:
        rm -rf *.o *.cmd *.ko *.mod.c .tmp_versions

linked-list.c

#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>

int linked_list_init(void)
{
    printk("%s\n", __func__);
    return 0;
}

void linked_list_exit(void)
{
    printk("%s\n", __func__);
}

module_init(linked_list_init);
module_exit(linked_list_exit);
MODULE_AUTHOR("Arnold Lu");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Linked list test");

安装module

sudo insmod linked-list.ko

查找安装情况

lsmod | grep linked-list

执行log

<4>[621267.946711] linked_list_init
<4>[621397.154534] linked_list_exit

删除module

sudo rmmod linked-list

 

链表、双向链表、无锁链表

Linux内核中的算法和数据结构


联系
我们