当前位置： 首页 > news >正文

数据结构day6——内核链表

news 2025/7/2 11:03:07

在 Linux 内核开发中，链表是最基础且重要的数据结构之一。与普通链表不同，Linux 内核采用了一种非常巧妙的 "通用链表" 设计，它不直接包含数据，而是将数据结构嵌入其中，从而实现了一种高度灵活、可复用的链表机制。本文将深入解析 Linux 内核链表的设计思想、实现原理及应用场景。

一、传统链表的局限性

传统链表的实现方式通常是将数据直接包含在节点结构中：

// 传统链表节点结构
typedef struct Student {char name[50];int age;struct Student *next;  // 指向下一个节点的指针
} Student;

这种设计存在以下局限性：

  • 类型不通用：每个链表只能存储特定类型的数据
  • 代码冗余：为每种数据类型都需要实现一套链表操作函数
  • 扩展性差：如果需要在不同链表间共享节点，实现复杂

二、Linux 内核链表的设计思想

Linux 内核链表采用了一种完全不同的设计思路：链表节点只包含指针域，而数据结构通过嵌入这个节点来实现链表功能。核心代码如下：

// 内核链表节点定义（include/linux/list.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;
}

这种设计的精妙之处在于：链表节点不再包含数据，而是数据结构包含链表节点。通过这种方式，任何数据结构都可以轻松接入链表系统。

三、内核链表的核心实现

1. 节点操作函数

内核提供了一系列用于操作链表的函数：

// 添加新节点到链表头部（头插法）
static inline void list_add(struct list_head *new, struct list_head *head) {__list_add(new, head, head->next);
}// 添加新节点到链表尾部（尾插法）
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 *entry) {__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;
}// 判断链表是否为空
static inline int list_empty(const struct list_head *head) {return head->next == head;
}

2. 从链表节点到数据结构的转换

内核链表的核心是通过container_of宏从链表节点指针获取包含它的数据结构指针：

// 获取包含链表节点的结构体指针
#define container_of(ptr, type, member) ({                      \const typeof( ((type *)0)->member ) *__mptr = (ptr);    \(type *)( (char *)__mptr - offsetof(type,member) );})// offsetof宏计算成员在结构体中的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

3. 遍历链表的宏

内核提供了安全遍历链表的宏：

// 遍历链表
#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)// 安全遍历（允许删除当前节点）
#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_entry(pos, head, member)                          \for (pos = list_entry((head)->next, typeof(*pos), member);          \&pos->member != (head);                                          \pos = list_entry(pos->member.next, typeof(*pos), member))

四、内核链表的应用示例

下面通过一个实际例子展示如何在内核模块中使用链表：

#include <linux/module.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>// 定义包含链表节点的数据结构
struct person {char name[20];int age;struct list_head list;  // 嵌入的链表节点
};// 定义链表头
static LIST_HEAD(person_list);static int __init person_init(void) {struct person *p1, *p2, *p3;// 分配并初始化第一个personp1 = kmalloc(sizeof(*p1), GFP_KERNEL);strcpy(p1->name, "Alice");p1->age = 25;INIT_LIST_HEAD(&p1->list);// 分配并初始化第二个personp2 = kmalloc(sizeof(*p2), GFP_KERNEL);strcpy(p2->name, "Bob");p2->age = 30;INIT_LIST_HEAD(&p2->list);// 分配并初始化第三个personp3 = kmalloc(sizeof(*p3), GFP_KERNEL);strcpy(p3->name, "Charlie");p3->age = 35;INIT_LIST_HEAD(&p3->list);// 添加到链表list_add_tail(&p1->list, &person_list);list_add_tail(&p2->list, &person_list);list_add_tail(&p3->list, &person_list);// 遍历链表并打印struct person *pos;list_for_each_entry(pos, &person_list, list) {printk(KERN_INFO "Name: %s, Age: %d\n", pos->name, pos->age);}return 0;
}static void __exit person_exit(void) {struct person *pos, *next;// 安全遍历并删除所有节点list_for_each_safe(pos, next, &person_list) {list_del(&pos->list);kfree(pos);}printk(KERN_INFO "Person module unloaded\n");
}module_init(person_init);
module_exit(person_exit);MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Example of Linux Kernel Linked List");

五、内核链表的优势与注意事项

优势

  1. 高度通用性：一个链表可以包含不同类型的数据结构，只要它们都嵌入了list_head
  2. 代码复用：所有链表操作函数只需实现一次
  3. 节省内存：链表节点无需额外存储数据指针
  4. 安全遍历：提供安全遍历宏，允许在遍历过程中删除节点

注意事项

  1. 内核环境限制：内核链表只能在内核空间使用，用户空间需使用类似实现
  2. 内存管理：使用kmalloc分配内存，需确保在适当时候释放
  3. 并发安全：在多处理器环境中使用时，需考虑并发访问问题，通常需要配合自旋锁等同步机制
  4. 遍历安全：使用list_for_each_safe进行可能删除节点的遍历操作

六、用户空间实现内核链表

虽然内核链表是为内核开发设计的，但我们也可以在用户空间实现类似的机制：

#include <stdio.h>
#include <stdlib.h>
#include <stddef.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;
}// 添加新节点到链表头部
static inline void list_add(struct list_head *new, struct list_head *head) {new->next = head->next;new->prev = head;head->next->prev = new;head->next = new;
}// 从链表中删除节点
static inline void list_del(struct list_head *entry) {entry->prev->next = entry->next;entry->next->prev = entry->prev;
}// 判断链表是否为空
static inline int list_empty(const struct list_head *head) {return head->next == head;
}// container_of宏实现
#define container_of(ptr, type, member) ({                      \const typeof( ((type *)0)->member ) *__mptr = (ptr);    \(type *)( (char *)__mptr - offsetof(type,member) );})// offsetof宏实现
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)// 遍历链表
#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)// 遍历链表并获取包含它的数据结构
#define list_for_each_entry(pos, head, member)                          \for (pos = container_of((head)->next, typeof(*pos), member);          \&pos->member != (head);                                          \pos = container_of(pos->member.next, typeof(*pos), member))// 用户空间示例
typedef struct {int id;char name[50];struct list_head list;
} User;int main() {LIST_HEAD(user_list);// 创建并添加用户User *user1 = malloc(sizeof(User));user1->id = 1;strcpy(user1->name, "张三");INIT_LIST_HEAD(&user1->list);list_add(&user1->list, &user_list);User *user2 = malloc(sizeof(User));user2->id = 2;strcpy(user2->name, "李四");INIT_LIST_HEAD(&user2->list);list_add(&user2->list, &user_list);// 遍历链表User *pos;list_for_each_entry(pos, &user_list, list) {printf("ID: %d, 姓名: %s\n", pos->id, pos->name);}// 释放内存list_for_each_entry(pos, &user_list, list) {list_del(&pos->list);free(pos);}return 0;
}

七、总结

Linux 内核链表是一种设计精巧、高效灵活的数据结构，它通过将链表节点嵌入到数据结构中，实现了链表操作的高度复用。这种设计思想不仅在内核开发中广泛应用，也为用户空间的软件开发提供了很好的借鉴。

理解和掌握内核链表的原理与使用方法，对于深入理解 Linux 内核工作机制、开发高性能系统软件具有重要意义。通过合理应用内核链表，可以编写出更加简洁、高效且易于维护的代码

http://www.lqws.cn/news/597961.html

相关文章：

  • 修改Spatial-MLLM项目，使其专注于无人机航拍视频的空间理解
  • ESP32-S3开发板深度评测：AI语音识别与图像处理全面解析
  • [2025CVPR]DE-GANs:一种高效的生成对抗网络
  • Android屏幕共享+WebSocket实现传输截图
  • 【代码审计】安全审核常见漏洞修复策略
  • Vue 3 中的 `h` 函数详解
  • android RecyclerView隐藏整个Item后,该Item还占位留白问题
  • 【Java编程动手学】Java的“三体”世界：JVM、JRE、JDK的共生之道
  • 从 0 到 1 构建可视化限流演示：React + Framer Motion 实现 Token Bucket 动画
  • 折线图多数据处理
  • 基于Halcon平台的常规OCR与深度OCR性能对比分析
  • 前端技术栈 —— HTML、CSS和JavaScirpt执行环境
  • 热血三国野地名将列表
  • 如何hack边缘的kubelet修改Cgroup数值
  • 事务隔离级别深度解析：机制、语法与实战指
  • Jenkins生态与拓展：构建现代化DevOps工具链的终极指南
  • android apk签名
  • Django打造智能Web机器人控制平台
  • mac部署dify
  • 每日一练：找到初始输入字符串 I
  • 第三方软件测试服务包含哪些类别？功能、性能、安全性测试全解析
  • Vue Vue-route （2）
  • ChatGPT、DeepSeek等大语言模型助力高效办公、论文与项目撰写、数据分析、机器学习与深度学习建模
  • 定时器的设计
  • 关于小波降噪、小波增强、小波去雾的原理区分
  • 1、lombok注解不生效
  • RIP 技术深度解析
  • Linux CentOS环境下Java连接MySQL数据库指南
  • 口重启Spring Boot项目中，通过接口实现应用重启是运维场景中的常见需求。以下是三种主流实现方案及其详细步骤和注意事项：
  • 图像处理专业书籍以及网络资源总结