[数据结构与算法] linux 内核链表使用

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> linux 内核链表使用 -> 正文阅读

[数据结构与算法]linux 内核链表使用

linux 内核链表使用

List

下面是截取内核源码，有部分修改方便自己测试使用

#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H

// include/linux/types.h
struct list_head {
	struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

// 初始化链表，前驱和后继都指向自己
static inline void INIT_LIST_HEAD(struct list_head *list){
    list->next = list;
	list->prev = list;
}

// 往链表插入节点内部方法 prv <=> new <=> next 
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{

	next->prev = new;
	new->next = next;
	new->prev = prev;
    prev->next = new;
}

// 在head 节点插入 new 节点，head <=> new <=> head->next（利于堆栈实现）
static inline void list_add(struct list_head *new, struct list_head *head){
	__list_add(new, head, head->next);
}


// 在head 节点插入 new 节点，head->prev <=> new <=> head （利于队列实现）
static inline void list_add_tail(struct list_head *new, struct list_head *head){
	__list_add(new, head->prev, head);
}

// 删除节点内部方法
static inline void __list_del(struct list_head * prev, struct list_head * next){
	next->prev = prev;
    prev->next = next;
}

// 删除entry节点，并时prev = NULL
static inline void __list_del_clearprev(struct list_head *entry){
	__list_del(entry->prev, entry->next);
	entry->prev = NULL;
}
// 删除entry节点
static inline void __list_del_entry(struct list_head *entry){
	__list_del(entry->prev, entry->next);
}

// 删除entry节点， 使entry->next，prev 为null (在Linux内部为非法值，访问产生缺页中断)
static inline void list_del(struct list_head *entry){
	__list_del_entry(entry);
	entry->next = NULL;
	entry->prev = NULL;
}

// new 节点 替换 old 节点
static inline void list_replace(struct list_head *old,struct list_head *new){
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

// new 节点 替换 old 节点，并初始化 old
static inline void list_replace_init(struct list_head *old, struct list_head *new){
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}

// 交换两个节点位置
static inline void list_swap(struct list_head *entry1, struct list_head *entry2){
	struct list_head *pos = entry2->prev;

	list_del(entry2);
	list_replace(entry1, entry2);
	if (pos == entry1)
		pos = entry2;
	list_add(entry1, pos);
}

// 删除entry节点，并初始化entry
static inline void list_del_init(struct list_head *entry){
	__list_del_entry(entry);
	INIT_LIST_HEAD(entry);
}

// 删除list 节点，并将其添加到head节点后 
static inline void list_move(struct list_head *list, struct list_head *head){
	__list_del_entry(list);
	list_add(list, head);
}

// 删除list 节点，并将其添加到head节点前
static inline void list_move_tail(struct list_head *list, struct list_head *head){
	__list_del_entry(list);
	list_add_tail(list, head);
}

// 确定MEMBER 成员在TYPE 结构体的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 知道type 结构体的 member 成员指针 ptr, 获取该结构体的指针
#define container_of(ptr, type, member) ({                      \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
	(type *)( (char *)__mptr - offsetof(type,member) );})

#define list_entry(ptr, type, member) container_of(ptr, type, member)

// 从链表ptr头 获取第一个元素
#define list_first_entry(ptr, type, member)	list_entry((ptr)->next, type, member)
// 从链表ptr头 获取最后一个元素
#define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member)

// 从链表ptr头 获取第一个元素，如果链表如空返回 NULL
#define list_first_entry_or_null(ptr, type, member) ({ \
	struct list_head *head__ = (ptr); \
	struct list_head *pos__ = READ_ONCE(head__->next); \
	pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
})

// 从结构体pos 获取下一个元素
#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

// 从结构体pos 获取前一个元素
#define list_prev_entry(pos, member) \
	list_entry((pos)->member.prev, typeof(*(pos)), member)

// 链表节点遍历，从表头head开始，逐项向后（next方向）移动pos，直至又回到head，基于列表不变的基础上
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

// 在当前pos 节点继续遍历
#define list_for_each_continue(pos, head) \
	for (pos = pos->next; pos != (head); pos = pos->next)

// 在当前pos 节点往前遍历
#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

// 安全遍历一个链表，通过传入两个参数pos,n 可以在链表中删除pos
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

#define list_for_each_prev_safe(pos, n, head) \
	for (pos = (head)->prev, n = pos->prev; \
	     pos != (head); \
	     pos = n, n = pos->prev)

#define list_entry_is_head(pos, head, member)				\
	(&pos->member == (head))

// 遍历链表，但是获得是结构体
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     !list_entry_is_head(pos, head, member);			\
	     pos = list_next_entry(pos, member))

// 反向遍历链表
#define list_for_each_entry_reverse(pos, head, member)			\
	for (pos = list_last_entry(head, typeof(*pos), member);		\
	     !list_entry_is_head(pos, head, member); 			\
	     pos = list_prev_entry(pos, member))

// 以安全的方式遍历链表
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_first_entry(head, typeof(*pos), member),	\
		n = list_next_entry(pos, member);			\
	     !list_entry_is_head(pos, head, member); 			\
	     pos = n, n = list_next_entry(n, member))

#endif

用户态测试

形成的数据结果如图

在这里插入图片描述

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

#include "list.h"

/*
整体需求：
type2 组成一条链表，里面的每个节点包含 type1 类型的链表
*/

struct type1{
    int value;
    struct list_head list;
};

struct type2 {
    int id;
    struct type1 item;
    struct list_head list;
};

int id_count = 0;
struct type2 src;

int find_by_id (int id,struct type2 **tmp) {
    struct list_head *pos;
    list_for_each(pos, &(src.list)){
        *tmp = list_entry(pos, struct type2, list);
        if ((*tmp)->id == id) {
            return 0;
        }
    }
    return -1;
}

int add_type2(int * id) {
    struct type2 *tmp;
    tmp = malloc(sizeof(struct type2));
    INIT_LIST_HEAD(&(tmp->item.list));
    id_count ++;
    tmp->id = id_count;
    *id = id_count;
    list_add(&(tmp->list),&(src.list));
    return 0;
}

int del_type2(int id){
    struct type2 *tmp;
    struct type1 *prev, *next;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    list_for_each_entry_safe(prev, next, &(tmp->item.list), list) {
        if(prev) {
            list_del(&(prev->list));
            free(prev);
        }
    }
    list_del(&(tmp->list));
    free(tmp);
    return 0;
}

int add_type1(int id,int value) {
    struct type2 *tmp;
    struct type1 *item_tmp;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    item_tmp = malloc(sizeof(struct type1));
    item_tmp->value = value;
    list_add(&(item_tmp->list),&(tmp->item.list));
    return 0;
}

int del_type1(int id,int value) {
    struct type2 *tmp;
    struct list_head *type1_ptr;
    struct type1 *item_tmp;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    // 释放 plr_sync_item
    list_for_each(type1_ptr, &(tmp->item.list)){
        item_tmp = list_entry(type1_ptr, struct type1, list);
        if (item_tmp->value == value) {
            list_del(type1_ptr);
            free(item_tmp);
            return 0;
        }
    }
    return -1;
}
// 销毁数据
int del() {
    struct type2 *tmp_prev,*tmp_next;
    struct type1 *type2_prev,*type2_next;
    list_for_each_entry_safe(tmp_prev,tmp_next,&(src.list),list) {
        if (!tmp_prev) {
            printf("error\n");
            continue;
        }
        list_for_each_entry_safe(type2_prev,type2_next,&(tmp_prev->item.list),list) {
            if (type2_prev) {
                list_del(&(type2_prev->list));
                free(type2_prev);
            }
        }
        list_del(&(tmp_prev->list));
        free(tmp_prev);
    }
    return 0;
}

int print_list() {
    struct type2 *tmp;
    struct type1 *type1_tmp;
    printf("----------------------------\n");
    list_for_each_entry(tmp,&(src.list),list) {
        printf("id=%d:",tmp->id);
        list_for_each_entry(type1_tmp,&(tmp->item.list),list) {
            printf("%d, ",type1_tmp->value);
        }
        printf("\n");
    }
    return 0;
}

int main() {
    int opt;
    int type1_id;
    int value;
    INIT_LIST_HEAD(&(src.list));
    while(~scanf("%d",&opt)) {
        switch (opt) {
        case 1: {
            add_type2(&type1_id);
            break;
        }
        case 2: {
            scanf("%d",&value);
            del_type2(value);
            break;
        }
        case 3: {
            scanf("%d",&value);
            add_type1(type1_id,value);
            break;
        }
        case 4: {
            scanf("%d",&value);
            del_type1(type1_id,value);
            break;
        }
        }
        print_list();
    }
    del();
    print_list();
    return 0;
}

输入测试

# test.log
1
3 1
3 2
1
3 3
3 4
4 4
2 1

在这里插入图片描述

内核模块测试

参考编写Linux内核模块/驱动程序，并提供ioctl接口

内核模块

#include <linux/init.h>  // __init,__exit macro
#include <linux/module.h> // included for all kernel modules
#include <linux/ioctl.h>
#include <linux/uaccess.h> // copy_from_user
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/fs.h>  // file_operation is defined in this header
#include <linux/device.h> 
#include <linux/err.h> // PTR_ERR

/*
整体需求：
type2 组成一条链表，里面的每个节点包含 type1 类型的链表
*/
#define ERR(fmt, args...) printk(KERN_ERR "%s()-%d: " fmt "\n", __func__, __LINE__, ##args)
#define DBG(fmt, args...) printk(KERN_DEBUG "%s()-%d: " fmt "\n", __func__, __LINE__, ##args)

struct type1{
    int value;
    struct list_head list;
};

struct type2 {
    int id;
    struct type1 item;
    struct list_head list;
};

struct param{
    int value;
    int id;
};

int      majorNumber;
struct   class*  list_test_module_class = NULL;
struct   device* list_test_module_device = NULL;

//define device name 
#define DEVICE_NAME "list_test"
#define CLASS_NAME  "list_test_module"

int id_count = 0;
struct type2 src;

// iotcl 命令相关定义
#define PLR_SYNC_MAGIC	'l'
#define ADD_TYPE2 _IOR(PLR_SYNC_MAGIC, 1,int)
#define DEL_TYPE2 _IOW(PLR_SYNC_MAGIC, 2,int)
#define ADD_TYPE1 _IOW(PLR_SYNC_MAGIC, 3,struct param)
#define DEL_TYPE1 _IOW(PLR_SYNC_MAGIC, 4,struct param)
#define PRINT _IO(PLR_SYNC_MAGIC,5)

// 用户态调用ioctl 回调函数
static long list_test_module_ioctl(struct file *, unsigned int, unsigned long);

struct file_operations ply_sync_ops = {
    .owner = THIS_MODULE,
    .unlocked_ioctl = list_test_module_ioctl
};

// 模块初始化，退出函数
static int __init list_test_init(void);
static void __exit list_test_exit(void);

// 链表操作相关函数
int add_type2(int *id);
int del_type2(int id);
int add_type1(int id,int value);
int del_type1(int id,int value);
int del(void);
int print_list(void);

static int __init list_test_init(void) {
    DBG("list_test_init enter");
    majorNumber = register_chrdev(0, DEVICE_NAME, &ply_sync_ops);
    if(majorNumber < 0){
        ERR("[TestModule:] Failed to register a major number.");
        return majorNumber;
    }
    DBG("[TestModule:] Successful to register a major number %d.", majorNumber);
    //接下来，注册设备类
    list_test_module_class = class_create(THIS_MODULE, CLASS_NAME);
    if(IS_ERR(list_test_module_class)){
        unregister_chrdev(majorNumber, DEVICE_NAME);
        ERR("[TestModule:] Class device register failed!");
        return PTR_ERR(list_test_module_class);
    }
    DBG("[TestModule:] Class device register success!");
    //最后，使用device_create函数注册设备驱动
    list_test_module_device = device_create(list_test_module_class, NULL, MKDEV(majorNumber, 0), NULL, DEVICE_NAME);
    if (IS_ERR(list_test_module_device)){ 
        class_destroy(list_test_module_class);
        unregister_chrdev(majorNumber, DEVICE_NAME);
        ERR("Failed to create the device");
        return PTR_ERR(list_test_module_device);
    }
    // 初始化链表
    INIT_LIST_HEAD(&(src.list));
    DBG("list_test_init exit");
    return 0;
}

static void __exit list_test_exit(void)
{
    DBG("list_test_exit enter");

    // 退出时，依次清理生成的device, class和chrdev
    // 这样就将系统/dev下的设备文件删除，并自动注销了/proc/devices的设备
    device_destroy(list_test_module_class, MKDEV(majorNumber, 0));
    class_destroy(list_test_module_class);
    unregister_chrdev(majorNumber, DEVICE_NAME);

    // 销毁链表
    del();

    DBG("list_test_init exot");

}

//本模块ioctl回调函数的实现
static long list_test_module_ioctl(struct file *file,        /* ditto */
                 unsigned int cmd,      /* number and param for ioctl */
                 unsigned long param)
{
    /* ioctl回调函数中一般都使用switch结构来处理不同的输入参数（cmd） */
    int ret = -EINVAL; // 表示 无效的参数，包括参数值、类型或数目无效等
    struct param info;
    switch(cmd){
    case ADD_TYPE2:{    
        ret = add_type2((int *)param);
        break;
    }
    case DEL_TYPE2: {
        ret = del_type2(param);
        break;
    }
    case ADD_TYPE1: {
        // 先从用户态复制数据
        ret = copy_from_user(&info, (struct param __user *)param, sizeof(info));
        // 拷贝发生错误
        if (ret) 
            return -EFAULT;
        ret = add_type1(info.id,info.value);
        break;
    }
    case DEL_TYPE1: {
        // 先从用户态复制数据
        ret = copy_from_user(&info, (struct param __user *)param, sizeof(info));
        // 拷贝发生错误
        if (ret) 
            return -EFAULT;
        ret = del_type1(info.id,info.value);
        break;
    }
    case PRINT: {
        print_list();
        break;
    }
    default:
        ERR("[TestModule:] Unknown ioctl cmd!");
    }
    return ret;
}

int find_by_id (int id,struct type2 **tmp) {
    struct list_head *pos;
    list_for_each(pos, &(src.list)){
        *tmp = list_entry(pos, struct type2, list);
        if ((*tmp)->id == id) {
            return 0;
        }
    }
    return -1;
}

int add_type2(int *id) {
    struct type2 *tmp;
    tmp = kmalloc(sizeof(struct type2),GFP_KERNEL);
    INIT_LIST_HEAD(&(tmp->item.list));
    id_count ++;
    tmp->id = id_count;
    *id = id_count;
    list_add(&(tmp->list),&(src.list));
    return 0;
}

int del_type2(int id){
    struct type2 *tmp;
    struct type1 *prev, *next;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    list_for_each_entry_safe(prev, next, &(tmp->item.list), list) {
        if(prev) {
            list_del(&(prev->list));
            kfree(prev);
        }
    }
    list_del(&(tmp->list));
    kfree(tmp);
    return 0;
}

int add_type1(int id,int value) {
    struct type2 *tmp;
    struct type1 *item_tmp;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    item_tmp = kmalloc(sizeof(struct type1),GFP_KERNEL);
    item_tmp->value = value;
    list_add(&(item_tmp->list),&(tmp->item.list));
    return 0;
}

int del_type1(int id,int value) {
    struct type2 *tmp;
    struct list_head *type1_ptr;
    struct type1 *item_tmp;
    int ret = find_by_id(id,&tmp);
    if (ret) 
        return ret;
    // 释放 list_test_item
    list_for_each(type1_ptr, &(tmp->item.list)){
        item_tmp = list_entry(type1_ptr, struct type1, list);
        if (item_tmp->value == value) {
            list_del(type1_ptr);
            kfree(item_tmp);
            return 0;
        }
    }
    return -1;
}

int del() {
    struct type2 *tmp_prev,*tmp_next;
    struct type1 *type2_prev,*type2_next;
    list_for_each_entry_safe(tmp_prev,tmp_next,&(src.list),list) {
        if (!tmp_prev) {
            printk("error\n");
            continue;
        }
        list_for_each_entry_safe(type2_prev,type2_next,&(tmp_prev->item.list),list) {
            if (type2_prev) {
                list_del(&(type2_prev->list));
                kfree(type2_prev);
            }
        }
        list_del(&(tmp_prev->list));
        kfree(tmp_prev);
    }
    return 0;
}

int print_list() {
    struct type2 *tmp;
    struct type1 *type1_tmp;
    printk("----------------------------\n");
    list_for_each_entry(tmp,&(src.list),list) {
        printk("id=%d:",tmp->id);
        list_for_each_entry(type1_tmp,&(tmp->item.list),list) {
            printk("%d, ",type1_tmp->value);
        }
        printk("\n");
    }
    return 0;
}

module_init(list_test_init);
module_exit(list_test_exit);

MODULE_AUTHOR("antrain");
MODULE_DESCRIPTION("kernel list test");
MODULE_LICENSE("GPL");

makefile

MODULE_NAME := test_list
#MODCFLAGS:=-O2 -Wall -DMODULE -D__KERNEL__ -DLINUX -std=c99
#EXTRA_CFLAGS  += $(MODULE_FLAGS) $(CFG_INC) $(CFG_INC)
EXTRA_CFLAGS  += -g -std=gnu99  -Wfatal-errors 

ifneq ($(KERNELRELEASE),)  # kernelspace
obj-m := $(MODULE_NAME).o
else                        # userspace
CURRENT_PATH ?= $(shell pwd)
LINUX_KERNEL ?= $(shell uname -r)
LINUX_KERNEL_PATH ?= /lib/modules/$(LINUX_KERNEL)/build
CURRENT_PATH := $(shell pwd)
modules:
	make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
 
modules_install:
	make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules_install
 
clean:
	make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean
	rm -f modules.order Module.symvers Module.markers
 
.PHNOY:
	modules modules_install clean
 
endif

用户态测试程序

#include <stdlib.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/ioctl.h>
#include <stdio.h>

#define PLR_SYNC_MAGIC	'l'
#define ADD_TYPE2 _IOR(PLR_SYNC_MAGIC, 1,int)
#define DEL_TYPE2 _IOW(PLR_SYNC_MAGIC, 2,int)
#define ADD_TYPE1 _IOW(PLR_SYNC_MAGIC, 3,struct param)
#define DEL_TYPE1 _IOW(PLR_SYNC_MAGIC, 4,struct param)
#define PRINT _IO(PLR_SYNC_MAGIC,5)
struct param{
    int value;
    int id;
};

int main(){
    // 打开设备
    int opt;
    int type1_id;
    int value;
    int ret;
    int fd = open("/dev/list_test",O_RDWR);
    if (fd<0) {
        perror("Failed to open the device...");
        return -1;
    }
    struct param p;
    while(~scanf("%d",&opt)) {
        switch (opt) {
        case 1: {
            ioctl(fd, ADD_TYPE2,&type1_id);
            break;
        }
        case 2: {
            scanf("%d",&value);
            ioctl(fd, DEL_TYPE2,value);
            break;
        }
        case 3: {
            scanf("%d",&value);
            p.id = type1_id;
            p.value = value;
            ioctl(fd, ADD_TYPE1,&p);
            break;
        }
        case 4: {
            scanf("%d",&value);
            p.id = type1_id;
            p.value = value;
            ioctl(fd, DEL_TYPE1,&p);
            break;
        }
        case 5: {
            ioctl(fd,PRINT);
        }
        }
    }
    close(fd);
    return 0;
}

测试

在虚拟机进行测试

# 删除缓存数据
sudo dmesg -C
# 编译
make
# 加载模块
sudo insmod test_list.ko
# 编译
gcc -o test test.c
# 测试数据 test.log
1
3 1
3 2
1
3 3
3 4
5
4 4
5
2 1
5
# 测试, 使用sudo 因为默认添加的设备可能需要权限
sudo ./test < test.log
# 卸载模块
sudo rmmod test_list
# 查看内核输出
dmesg