深入理解Linux侵入式链表 (从原理到应用)

深入理解Linux侵入式链表 (从原理到应用)

在Linux内核中，侵入式链表是一种广泛使用的数据结构。它通过将链表节点嵌入到数据结构内部，实现了通用性和高效性。本文将带你从零开始，深入理解Linux侵入式链表的实现原理和使用方法。

什么是侵入式链表？

传统链表（如C++ STL list）通常将数据包含在节点中，而侵入式链表则相反：节点嵌入到数据中。在Linux内核中，list_head结构体就是侵入式链表的基石，它只有两个指针prev和next，不包含数据。开发者需要将list_head嵌入到自己的数据结构中，然后通过container_of宏获取包含它的数据结构。

Linux内核中的list_head

在Linux内核源代码中，list_head定义在中：

struct list_head {    struct list_head *next, *prev;};

这个结构不包含数据，只包含前后指针。当我们需要将某个数据结构加入链表时，只需在该结构中添加一个list_head成员。

核心操作与宏

内核提供了一系列操作list_head的函数和宏：

• INIT_LIST_HEAD：初始化链表头
• list_add：在头部添加节点
• list_del：删除节点
• list_entry：通过链表节点获取包含它的数据结构（基于container_of）
• list_for_each：遍历链表

示例代码：使用侵入式链表

假设我们有一个数据结构my_struct，需要将其链接到链表：

struct my_struct {    int data;    struct list_head list;  // 侵入式链表节点};

创建链表头并添加元素：

LIST_HEAD(my_list);  // 定义并初始化链表头struct my_struct a = kmalloc(sizeof(a), GFP_KERNEL);a->data = 42;list_add(&a->list, &my_list);

遍历链表并获取数据结构：

struct my_struct *pos;list_for_each_entry(pos, &my_list, list) {    printk("data: %d", pos->data);}

深入原理：list_entry与container_of

list_entry宏实际上是对container_of的封装。container_of通过结构体中某个成员的指针，计算出整个结构体的起始地址。其原理是利用了编译器计算偏移量的能力。

#define container_of(ptr, type, member) ({          \n    const typeof(((type *)0)->member) *__mptr = (ptr); \n    (type *)((char *)__mptr - offsetof(type, member)); })

这样，给定list指针，就能找到包含它的结构体。

侵入式链表的优缺点

优点：通用性强（一个list_head可加入多个链表），操作高效（无需额外分配节点），类型安全（通过宏保持类型信息）。缺点：对数据结构有侵入性，不能用于基本数据类型，理解门槛稍高。

总结

Linux侵入式链表是内核数据管理的基石，理解它有助于阅读内核代码和编写高效的内核模块。通过本文，你应该掌握了list_head的使用和原理。继续深入学习，你会发现更多精妙的内核数据结构。