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

linux内核数据结构分析之链表

article 2025/3/24 15:52:16

我们知道，常规的链表结点是定义成一个结构体，里面包含了结点数据，以及指向前后结点的指针，比如：
typedef list_node_data_type int;

typedef struct list_node{
    list_node_data_type list_data;
    struct list_node *pre;
    struct list_node *next;
}list_node
以上就是一个常规双向链表的结构体定义。

但是，在Linux内核中，链表的定义却带有一些技巧。

接下来好好聊聊这个问题。

参考：

Linux内核中的数据结构的一点认识_华清远见教育科技集团 (hqyj.com)

【linux kernel】linux内核数据结构分析之链表 - 知乎 (zhihu.com)

Linux内核中实现了一套经典的链表操作，定义在/include/linux/list.h文件中，其没有对应的c文件，就在头文件中以内联函数的形式来提供一系列API的。

结点结构体

打开内核源码中的 include/linux/list.h头文件，就可以看到内核中声明的一些与链表操作相关的结构体定义和函数接口。内核中使用更多的是双向循环链表。我们就看一看内核中双向循环链表的精妙之处吧。

我们通过点击跳转，可以跳转到类型定义types.h中，首先看链表节点的结构体的定义：

怎么样，奇怪吗？

为什么结点定义里只有指针，没有结点数据？

大家都可以看到，该结构体的成员仅包含了两个指向前和后的两个结构体指针，但是在该结构体中却没有数据成员，那么到时候链表中没有任何数据，这样的链表有什么用呢?其实这就是内核链表设计的巧妙之处，因为在整个内核中需要使用链表来存放的数据类型太多了，因此如果将内核的数据结构定义成固定的话，就会增加大量的结构体类型的定义，而内核将数据成员的定义变的灵活了，就是当用到什么样的数据时就临时添加什么数据，那到底是怎么做的呢?这种情况下怎么把目标数据和这个只有指针的结点给关联起来呢？

首先，毫无疑问，结点数据肯定是要有的。

另外要明确，只提供基础的指针结点，只是为了简化链表指针的操作，这样，不管在哪里用到链表，对于链表前后指向的操作都是一致的，不同的是，各个地方的结点数据是不一样的。

举个例子，假如我们需要在某个地方使用链表，链表里需要放一个int类型的结点数据，那么就可以在使用的地方再定义一个这样的结构体。
struct Data{
    int a;
    struct list_head p;
};
其中成员a是我们的数据，而链表结点的变量变成了我们新结构体类型的成员。这样定义的话，只需要将其中的成员p添加到一个双向循环链表中，通过成员p我们就可以得到我们的数据成员a。可以这样比喻，就是成员p就是一个晾衣架，有很多晾衣架都挂在一个晾衣杆上，但是每个晾衣架上挂什么衣服就比较随便了。只要我们找到一个晾衣架就可以立刻得到挂在上边的衣服了。

container_of宏定义

但是，这里还有个问题需要解决，那就是，怎么能通过结构体的某个成员来获取另一个成员的值呢？这就需要内核中定义的一个container_of宏定义：

container_of 的主要作用是通过给定的结构体成员的地址来获取整个结构体的起始地址。这在处理复杂的数据结构，如链表时非常有用。

参数解析

ptr：这是指向结构体成员的指针。

type：这是包含该成员的结构体的类型。

member：这是结构体中成员的名称，通过这个名称可以确定成员在结构体中的偏移量。

这里的成员指的就是结构体里定义的的链表变量，举例说明
#include <stdio.h>
#include <stddef.h>

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

// 定义结构体
struct my_struct {
    int data;
    char name[20];
    struct list_head list;
};

// 定义链表节点结构体
struct list_head {
    struct list_head *next, *prev;
};

int main() {
    // 创建一个 my_struct 实例
    struct my_struct my_instance = {
        .data = 42,
        .name = "example",
        .list = {NULL, NULL}
    };

    // 获取 list 成员的地址
    struct list_head *list_ptr = &my_instance.list;

    // 使用 container_of 获取 my_struct 的地址
    struct my_struct *parent = container_of(list_ptr, struct my_struct, list);

    // 打印结果
    printf("my_instance address: %p\n", (void *)&my_instance);
    printf("parent address: %p\n", (void *)parent);
    printf("parent->data: %d\n", parent->data);
    printf("parent->name: %s\n", parent->name);

    return 0;
}
实现方式

类型转换和地址计算：首先将成员的地址转换为 void 指针，然后通过减去该成员在结构体中的偏移量（使用 offsetof 宏），从而得到结构体的起始地址。

宏定义：container_of 实际上是一个宏，它在编译时展开，不涉及运行时的函数调用开销。这使得它的效率非常高。

在 Linux 内核的链表实现中，每个节点通常包含两个指向前后节点的指针。通过 container_of，可以从节点指针获取到整个链表节点的结构体，从而访问节点的其他成员。

在管理复杂的数据结构时，经常需要从一个已知的成员回溯到整个结构体，container_of 提供了一种简洁高效的方法来实现这一点。

总的来说，container_of 是Linux内核中一个极其重要的工具，它通过简单的宏定义实现了从结构体成员地址到结构体首地址的转换，极大地简化了复杂数据结构的处理。对于Linux内核开发者来说，熟练掌握container_of的使用是编写高效、可维护代码的关键。

container_of 的工作原理

container_of 的工作原理可以分为以下几步：

获取成员的类型：

使用 typeof 获取成员的类型。

例如，typeof(((type *)0)->member) 获取 member 的类型。

计算成员的偏移量：

使用 offsetof 宏计算 member 在结构体中的偏移量。

offsetof(type, member) 返回 member 在 type 结构体中的偏移量（以字节为单位）。

计算结构体的起始地址：

将成员的地址减去偏移量，得到结构体的起始地址。

(char *)__mptr - offsetof(type, member) 将指针转换为 char *，以便进行字节级别的计算。

offsetof 宏

offsetof 是一个标准宏，用于计算结构体成员的偏移量。它的定义如下：
#define offsetof(type, member) ((size_t)&((type *)0)->member)
(type *)0：将 0 强制转换为 type * 类型的指针。

&((type *)0)->member：获取 member 的地址。

(size_t)：将地址转换为 size_t 类型，表示偏移量。

container_of 的应用场景

链表：

在 Linux 内核中，链表通常是通过嵌入 struct list_head 实现的。通过 container_of，可以从链表节点获取包含它的结构体。

设备驱动：

在设备驱动中，通常将设备相关的数据嵌入到一个结构体中。通过 container_of，可以从设备指针获取包含它的结构体。

回调函数：

在回调函数中，通常只能访问某些特定的数据。通过 container_of，可以从这些数据获取完整的上下文。

container_of 的示例

假设有以下结构体：
struct my_struct {
    int data;
    char name[20];
    struct list_head list;
};
list 是一个链表节点，嵌入在 my_struct 中。

如果你知道 list 的地址，可以通过 container_of 获取 my_struct 的地址。
struct list_head *list_ptr; // 假设这是已知的链表节点指针

// 使用 container_of 获取包含 list_ptr 的 my_struct 结构体的地址
struct my_struct *parent = container_of(list_ptr, struct my_struct, list);

这种情况下，是每个结构体都是链表的一个结点，还是一个结构体里面包含了有多个结点的链表呢？因为这种设计下的链表里不直接存放数据，所以，需要跟所在结构体绑定，这时候，更像是每个结构体实体都是链表的一个结点。那如果一个结构体里面包含了两个链表呢？

linux一个结构体里面包含了两个list_head是什么情况

在 Linux 内核中，一个结构体包含两个 list_head 的情况通常是为了实现多重链表（Multiple Lists）。这种设计允许同一个结构体实例同时存在于多个链表中，从而支持更复杂的数据组织和管理。

1. 为什么需要两个 list_head？

多重链表：一个结构体可能需要同时属于多个链表。例如：

一个设备可能同时存在于“设备列表”和“驱动程序列表”中。

一个任务可能同时存在于“就绪队列”和“等待队列”中。

灵活性：通过多个 list_head，可以更灵活地组织和管理数据。

2. 示例场景

假设我们有一个结构体 struct task，表示一个任务。这个任务可能同时存在于以下两个链表中：

就绪队列：所有准备运行的任务。

等待队列：所有等待某个事件的任务。
struct task {
    int id;
    char name[20];
    struct list_head ready_list;  // 用于就绪队列
    struct list_head wait_list;   // 用于等待队列
};
3. 如何使用两个 list_head

每个 list_head 用于将结构体链接到不同的链表中。以下是一个简单的示例：

定义链表头
LIST_HEAD(ready_queue);  // 就绪队列
LIST_HEAD(wait_queue);   // 等待队列
创建任务并添加到链表中
struct task *task1 = kmalloc(sizeof(struct task), GFP_KERNEL);
task1->id = 1;
strcpy(task1->name, "Task 1");

// 将 task1 添加到就绪队列
list_add(&task1->ready_list, &ready_queue);

// 将 task1 添加到等待队列
list_add(&task1->wait_list, &wait_queue);
遍历链表
// 遍历就绪队列
struct list_head *pos;
list_for_each(pos, &ready_queue) {
    struct task *task = container_of(pos, struct task, ready_list);
    printk("Ready Task: %s\n", task->name);
}

// 遍历等待队列
list_for_each(pos, &wait_queue) {
    struct task *task = container_of(pos, struct task, wait_list);
    printk("Waiting Task: %s\n", task->name);
}
4. container_of 的使用

由于一个结构体中有多个 list_head，在使用 container_of 时需要指定正确的 list_head 成员。

例如：

从 ready_list 获取 struct task：
struct task *task = container_of(ready_list_ptr, struct task, ready_list);
从 wait_list 获取 struct task：
struct task *task = container_of(wait_list_ptr, struct task, wait_list);
5. 实际应用场景

场景 1：设备管理

在内核中，一个设备可能同时存在于以下链表中：

全局设备列表：所有设备的列表。

驱动程序设备列表：某个驱动程序管理的设备列表。
struct device {
    int id;
    char name[20];
    struct list_head global_list;  // 全局设备列表
    struct list_head driver_list;  // 驱动程序设备列表
};
场景 2：任务调度

在任务调度中，一个任务可能同时存在于以下链表中：

就绪队列：所有准备运行的任务。

等待队列：所有等待某个事件的任务。
struct task {
    int id;
    char name[20];
    struct list_head ready_list;  // 就绪队列
    struct list_head wait_list;   // 等待队列
};
6. 注意事项

链表独立性：每个 list_head 是独立的，操作一个链表不会影响另一个链表。

内存管理：确保在释放结构体时，将其从所有链表中移除。

正确使用 container_of：在使用 container_of 时，确保指定正确的 list_head 成员。

8. 总结

一个结构体包含两个 list_head 是为了支持多重链表，允许同一个结构体实例同时存在于多个链表中。

这种设计在内核中非常常见，例如设备管理、任务调度等场景。

使用 container_of 时，需要指定正确的 list_head 成员。

通过多个 list_head，可以更灵活地组织和管理数据。

链表操作的实现

有了上面的知识打底，我们再来继续看看这些链表操作的实现过程。

初始化链表头

看实现可知，LIST_HEAD宏和INIT_LIST_HEAD内联函数都能初始化一个链表头，这个节点本身并不存储任何实际的数据，而是作为整个链表的起点或终点。在链表中，每个节点都包含两个指针，分别指向前一个节点和后一个节点。LIST_HEAD宏和INIT_LIST_HEAD内联函数初始化的头部节点，其前后指针都指向它自身，形成一个空链表的状态。通过头部节点，可以很容易地判断链表是否为空（即头部节点的下一个指针是否指向它自身）。

LIST_HEAD宏和INIT_LIST_HEAD内联函数在功能上有所重叠，但也存在一些细微的区别和使用场景的不同。

首先，用LIST_HEAD宏定义来初始化一个头结点，这实际是在LIST_HEAD所在文件中定义了一个叫做“name”的全局变量，而INIT_LIST_HEAD就是传递进入一个链表结点当做头结点。

INIT_LIST_HEAD：它通过一个内联函数将链表头的next和prev指针都初始化为指向自身，表示链表为空。

LIST_HEAD：它实际上是一个宏，用于在声明时直接初始化链表头。这个宏展开后会使用LIST_HEAD_INIT来初始化链表头，使其next和prev指针都指向自身。

使用场景

INIT_LIST_HEAD：通常用于在运行时动态地初始化链表头。例如，当链表头是一个结构体成员或需要在运行时分配内存时，可以使用这个宏。

LIST_HEAD：主要用于在编译时静态地声明并初始化链表头。它通常在结构体定义或全局变量声明中使用。

另外，还有个问题让我比较疑惑，那就是为啥这里传入的是个指针

有一段时间，我总觉得这里应该传递进来的是一个二重指针，这样，才能操作传进来的那个指针，如果只是传进来一个指针，那么，这里对list操作，实际上就只是操作list这个局部变量形参本身，而不会影响到传递进来的那个指针变量实参。

但是，这里是不可能出错的，那是为什么呢？

仔细想想，你需要改变传进来之前的那个实参的值吗？答案是不需要的。相反，你还得保留好这个地址值，因为我需要靠这个地址值去操作它里面的成员变量，一个指针，不管是哪个变量接收的，只要指针值不丢失，就可以访问同一片内存空间。

再次强调，什么时候需要传递进入变量的指针，除非你想要通过形参变量去改变传入前的实参变量。

为什么有些链表在初始化时需要传递进入指针的指针呢？这是因为一般定义链表时，都是先定义一个空指针，比如int *p = NULL，然后需要传递到初始化链表的函数里进行初始化，初始化函数里通常会malloc来分配空间，并传递给传入的指针，这时候，就需要改变传递前的实参，所以就需要传递进入实参指针的指针，如果在传递之前已经有了确定的地址值，那么就不用再传递进入实参的指针了。

链表操作示例

在 Linux 内核中，双向链表是通过 struct list_head 实现的。以下是一个完整的使用示例，展示了如何定义链表、初始化链表、添加节点、遍历链表以及删除节点。

定义链表和结构体

首先，定义一个包含链表节点的结构体。
#include <linux/list.h>
#include <linux/kernel.h>
#include <linux/slab.h>  // 用于内存分配

// 自定义结构体，包含链表节点
struct my_struct {
    int data;
    struct list_head list;  // 链表节点
};
初始化链表头

使用 INIT_LIST_HEAD 或 LIST_HEAD 宏初始化链表头。
// 静态初始化链表头
static LIST_HEAD(my_list);

// 或者动态初始化链表头
struct list_head my_list;
INIT_LIST_HEAD(&my_list);
添加节点到链表

使用 list_add 或 list_add_tail 将节点添加到链表中。
// 添加节点到链表头部
struct my_struct *new_entry = kmalloc(sizeof(struct my_struct), GFP_KERNEL);
new_entry->data = 10;
INIT_LIST_HEAD(&new_entry->list);
list_add(&new_entry->list, &my_list);

// 添加节点到链表尾部
struct my_struct *new_entry_tail = kmalloc(sizeof(struct my_struct), GFP_KERNEL);
new_entry_tail->data = 20;
INIT_LIST_HEAD(&new_entry_tail->list);
list_add_tail(&new_entry_tail->list, &my_list);
遍历链表

使用 list_for_each 或 list_for_each_entry 遍历链表。

使用 list_for_each：
struct list_head *pos;
list_for_each(pos, &my_list) {
    struct my_struct *entry = list_entry(pos, struct my_struct, list);
    printk(KERN_INFO "Data: %d\n", entry->data);
}
使用 list_for_each_entry：
struct my_struct *entry;
list_for_each_entry(entry, &my_list, list) {
    printk(KERN_INFO "Data: %d\n", entry->data);
}
删除节点

使用 list_del 删除节点。如果需要安全删除（在遍历时删除），使用 list_for_each_safe 或 list_for_each_entry_safe。

删除特定节点：
struct my_struct *entry, *tmp;
list_for_each_entry_safe(entry, tmp, &my_list, list) {
    if (entry->data == 10) {
        list_del(&entry->list);
        kfree(entry);
    }
}
删除所有节点：
struct my_struct *entry, *tmp;
list_for_each_entry_safe(entry, tmp, &my_list, list) {
    list_del(&entry->list);
    kfree(entry);
}
通过这个示例，你可以掌握 Linux 内核中链表的基本操作。

几个和遍历链表相关的接口

list_entry

list_for_each

list_for_each_safe

list_for_each_entry

list_for_each_entry_safe

在 Linux 内核中，list_entry、list_for_each、list_for_each_safe、list_for_each_entry 和 list_for_each_entry_safe 是用于操作双向链表的常用宏。它们定义在 <linux/list.h> 头文件中，功能和使用场景有所不同。以下是它们的详细说明和区别：

1. list_entry

功能

通过链表节点的指针获取包含该节点的结构体的指针。

原型
list_entry(ptr, type, member)
参数

ptr: 链表节点的指针（struct list_head * 类型）。

type: 包含链表节点的结构体的类型。

member: 链表节点在结构体中的成员名。

使用示例
struct my_struct {
    int data;
    struct list_head list;
};

struct list_head *pos;
list_for_each(pos, &my_list) {
    struct my_struct *entry = list_entry(pos, struct my_struct, list);
    printk(KERN_INFO "Data: %d\n", entry->data);
}
说明

用于从链表节点指针（struct list_head *）获取外层结构体的指针。

2. list_for_each

功能

遍历链表中的每个节点。

原型
list_for_each(pos, head)
参数

pos: 当前链表节点的指针（struct list_head * 类型）。

head: 链表头的指针（struct list_head * 类型）。

使用示例
struct list_head *pos;
list_for_each(pos, &my_list) {
    struct my_struct *entry = list_entry(pos, struct my_struct, list);
    printk(KERN_INFO "Data: %d\n", entry->data);
}
注意事项

不能在遍历时删除节点，否则会导致未定义行为。

3. list_for_each_safe

功能

安全地遍历链表，允许在遍历时删除当前节点。

原型
list_for_each_safe(pos, n, head)
参数

pos: 当前链表节点的指针（struct list_head * 类型）。

n: 临时保存下一个节点的指针（struct list_head * 类型），用于防止删除节点后丢失链表信息。

head: 链表头的指针（struct list_head * 类型）。

使用示例
struct list_head *pos, *n;
list_for_each_safe(pos, n, &my_list) {
    struct my_struct *entry = list_entry(pos, struct my_struct, list);
    if (need_to_remove(entry)) {
        list_del(pos); // 安全删除当前节点
        kfree(entry);   // 释放资源
    }
}
注意事项

适用于需要在遍历时删除节点的场景。

4. list_for_each_entry

功能

直接遍历包含链表节点的结构体，无需手动调用 list_entry。

原型
list_for_each_entry(pos, head, member)
参数

pos: 当前结构体的指针（通常是用户定义的结构体类型）。

head: 链表头的指针（struct list_head * 类型）。

member: 链表节点在结构体中的成员名。

使用示例
struct my_struct {
    int data;
    struct list_head list;
};

struct my_struct *entry;
list_for_each_entry(entry, &my_list, list) {
    printk(KERN_INFO "Data: %d\n", entry->data);
}
注意事项

适用于直接操作包含链表节点的结构体。

5. list_for_each_entry_safe

功能

安全地遍历包含链表节点的结构体，允许在遍历时删除当前节点。

原型
list_for_each_entry_safe(pos, n, head, member)
参数

pos: 当前结构体的指针（用户定义的结构体类型）。

n: 临时保存下一个结构体的指针，用于防止删除节点后丢失链表信息。

head: 链表头的指针（struct list_head * 类型）。

member: 链表节点在结构体中的成员名。

使用示例
struct my_struct *entry, *tmp;
list_for_each_entry_safe(entry, tmp, &my_list, list) {
    if (need_to_remove(entry)) {
        list_del(&entry->list); // 删除节点
        kfree(entry);           // 释放资源
    }
}
注意事项

适用于需要在遍历时删除包含链表节点的结构体的场景。

总结来说，加了entry就不用再额外调用list_entry；加了safe就可以在遍历时删除节点。