Linux 内核数据结构之链表：深入解析与实践指南

在软件开发和系统编程中，链表是一种基础且强大的数据结构，用于高效地管理动态集合。然而，传统教科书中教授的链表实现方式通常要求为每一种数据类型定义一套独立的节点结构体和操作函数，这在像 Linux 内核这样庞大、涉及成千上万种数据类型的项目中，会导致大量的代码重复和维护负担。

为了解决这个问题，Linux 内核采用了一种独具匠心的实现方式：将链表结构本身与数据域分离。这种实现不仅是内核高效运作的基石，其设计思想也因其通用性和高性能而被广泛借鉴到用户态程序中。本文将深入剖析 Linux 内核链表的实现原理、常用操作、最佳实践，并辅以示例代码。

目录#

  1. 传统链表的局限
  2. Linux 内核链表的精妙设计
  3. 内核链表的实现剖析
  4. 核心宏详解：container_of 与 offsetof
  5. 完整示例：一个简单的任务管理器
  6. 常见操作与最佳实践
  7. 内核链表 vs. 传统链表
  8. 总结
  9. 参考

1. 传统链表的局限#

在进入正题之前，我们先回顾一下传统链表的实现。假设我们需要管理一个进程列表，我们通常会这样定义：

// 传统链表实现
struct my_task {
    int pid;
    char name[64];
    struct my_task *prev; // 指向前一个任务节点
    struct my_task *next; // 指向后一个任务节点
};

这种方式的问题在于：

  • 代码冗余：如果我们需要再管理一个“设备”列表，就必须重新定义一个包含 prev 和 next 指针的 struct my_device。
  • 功能重复：为 my_task 链表和 my_device 链表编写的插入、删除、遍历等函数逻辑几乎完全相同，但却需要写两套。
  • 维护困难：当需要修改链表算法（例如，升级为双向循环链表）时，需要修改所有相关数据结构的代码。

2. Linux 内核链表的精妙设计#

Linux 内核链表的核心思想是**“侵入式链表”**。它不将数据塞入链表节点，而是将链表节点“侵入”到宿主数据结构中。

具体来说，内核定义了一个独立的、仅包含前后指针的通用链表结构 struct list_head。任何需要被链接的数据结构，只需在其内部嵌入一个 list_head 成员即可。所有链表操作（增、删、改、查）都只关心这个 list_head 成员。当需要访问宿主数据结构时，再通过巧妙的指针运算来获取其首地址。

这种设计实现了完美的解耦：链表操作与具体数据类型无关。

3. 内核链表的实现剖析#

3.1 核心结构体：list_head#

这个结构体定义在 include/linux/types.h 中，极其简单：

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

一个使用内核链表的数据结构示例如下：

// 使用 Linux 内核链表风格
struct my_task {
    int pid;
    char name[64];
    struct list_head list; // 嵌入的链表节点
};
 
struct my_device {
    unsigned int dev_id;
    char dev_name[32];
    struct list_head list; // 同样是 list_head，但属于不同的链表
};

现在，struct my_task 和 struct my_device 可以共用同一套链表操作函数。

3.2 初始化链表#

内核提供了两种初始化方法：

  1. 编译时初始化：使用 LIST_HEAD 宏。

    // 声明并初始化一个名为 task_list 的链表头
static LIST_HEAD(task_list);

  2. 运行时初始化：使用 INIT_LIST_HEAD 宏。

    struct list_head my_list;
INIT_LIST_HEAD(&my_list);
 
// 或者初始化宿主结构体内的 list 成员
struct my_task *task = kmalloc(sizeof(*task), GFP_KERNEL);
task->pid = 1;
INIT_LIST_HEAD(&task->list); // 初始化该节点，使其指向自己

3.3 添加节点#

最常用的添加操作是 list_add 和 list_add_tail。

  • list_add(new, head): 将新节点 new 添加到 head 节点之后，即头部插入（栈式，LIFO）。
  • list_add_tail(new, head): 将新节点 new 添加到 head 节点之前，即尾部插入（队列式，FIFO）。
struct my_task *new_task = create_task(123, "kworker");
list_add_tail(&new_task->list, &task_list); // 将新任务加到队列末尾

3.4 删除节点#

使用 list_del 函数。

// 假设 curr_task 是一个指向某个 my_task 的指针
list_del(&curr_task->list);

重要提示：list_del 只是将节点从链表中移除，并不会释放该节点占用的内存。内存释放需要开发者手动处理。

3.5 遍历链表#

遍历是链表最常用的操作，也是最体现内核链表精妙之处的地方。

基础遍历宏：list_for_each

struct list_head *pos;
list_for_each(pos, &task_list) {
    // 此时 pos 是一个指向 list_head 的指针
    // 我们需要通过 pos 找到它所属的 my_task 结构体
}

核心宏：list_for_each_entry 这是最常用、最方便的宏，它直接返回宿主结构的指针。

struct my_task *task_pos;
list_for_each_entry(task_pos, &task_list, list) {
    // 第一个参数：指向宿主结构体的指针，在循环中自动赋值
    // 第二个参数：链表头
    // 第三个参数：宿主结构体中 list_head 成员的名字（这里是 "list"）
    printk("PID: %d, Name: %s\n", task_pos->pid, task_pos->name);
}

4. 核心宏详解：container_of 与 offsetof#

list_for_each_entry 的强大功能源于两个底层宏：offsetof 和 container_of。它们允许我们通过结构体成员的地址反推其所属结构体的地址。

  • offsetof(TYPE, MEMBER)：计算成员 MEMBER 在结构体 TYPE 中的偏移量。
  • container_of(ptr, type, member)：
    • ptr：指向结构体成员的指针。
    • type：宿主结构体的类型。
    • member：成员在结构体中的名称。
    • 返回值：宿主结构体的首地址。

其简化实现如下：

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

工作原理：

  1. ((type *)0)->member：将地址 0 强制转换为 type 指针，然后访问其 member 成员。这并非真的访问 0 地址，而是在编译时计算 member 的偏移量。
  2. offsetof(type, member)：直接计算出偏移量。
  3. (char *)__mptr - offsetof(type, member)：将成员的实际地址 __mptr 减去它在结构体中的偏移量，就得到了宿主结构体的起始地址。

因此，list_for_each_entry(task_pos, &task_list, list) 在内部就是通过每个节点的 list 地址，利用 container_of 计算出对应的 struct my_task 的地址，然后赋值给 task_pos。

5. 完整示例：一个简单的任务管理器#

以下是一个在用户态模拟内核链表用法的完整程序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// 模拟 Linux 内核的 list_head
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 *prev, struct list_head *next) {
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
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 *prev, struct list_head *next) {
    next->prev = prev;
    prev->next = next;
}
static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}
 
// 遍历宏
#define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type, member) );})
#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))
 
// 宿主数据结构
struct my_task {
    int pid;
    char name[64];
    struct list_head list;
};
 
int main() {
    LIST_HEAD(task_list); // 定义并初始化任务链表头
 
    // 创建几个任务
    struct my_task t1 = { .pid = 1, .name = "init" };
    struct my_task t2 = { .pid = 2, .name = "bash" };
    struct my_task t3 = { .pid = 3, .name = "top" };
    INIT_LIST_HEAD(&t1.list);
    INIT_LIST_HEAD(&t2.list);
    INIT_LIST_HEAD(&t3.list);
 
    // 将任务添加到链表尾部
    list_add_tail(&t1.list, &task_list);
    list_add_tail(&t2.list, &task_list);
    list_add_tail(&t3.list, &task_list);
 
    // 遍历并打印所有任务
    struct my_task *task;
    printf("Tasks in the list:\n");
    list_for_each_entry(task, &task_list, list) {
        printf("  PID: %d, Name: %s\n", task->pid, task->name);
    }
 
    // 删除 PID=2 的任务
    list_for_each_entry(task, &task_list, list) {
        if (task->pid == 2) {
            list_del(&task->list);
            printf("\nTask %d deleted.\n", task->pid);
            break;
        }
    }
 
    // 再次遍历
    printf("\nTasks after deletion:\n");
    list_for_each_entry(task, &task_list, list) {
        printf("  PID: %d, Name: %s\n", task->pid, task->name);
    }
 
    return 0;
}

6. 常见操作与最佳实践#

6.1 判断链表是否为空#

使用 list_empty 函数。

if (list_empty(&task_list)) {
    printk("The task list is empty.\n");
}

6.2 安全的遍历并删除#

如果在遍历过程中需要删除当前节点，直接使用 list_for_each_entry 然后调用 list_del 会导致问题，因为删除操作会破坏用于遍历的 next 指针。此时应使用安全遍历宏 list_for_each_entry_safe。

struct my_task *task_pos, *task_next;
list_for_each_entry_safe(task_pos, task_next, &task_list, list) {
    if (some_condition_to_delete(task_pos)) {
        list_del(&task_pos->list);
        kfree(task_pos); // 安全地释放内存
    }
}

这个宏在遍历开始时预先保存了下一个节点的指针，因此即使当前节点被删除，遍历也能正确继续。

6.3 其他常用操作#

  • list_move(&node->list, &new_head)：将节点从一个链表移动到另一个链表。
  • list_splice(&list1, &list2)：将链表 list1 的所有节点合并到 list2 中。
  • list_is_last(&node->list, &head)：判断节点是否是链表的最后一个节点。

7. 内核链表 vs. 传统链表#

特性传统链表Linux 内核链表
代码复用性差，每种数据类型需一套实现极佳，一套实现用于所有类型
内存效率较好，节点即数据更好，小对象可嵌入，减少内存分配次数
类型安全编译时类型安全依赖 container_of，有一定风险但可通过编程规范避免
易用性直观，易于理解初学有门槛，但熟悉后非常方便
主要应用通用应用程序操作系统内核、高性能基础库

8. 总结#

Linux 内核的链表实现是一个经典的设计模式（侵入式链表），它通过将链表操作与具体数据分离，实现了极高的代码复用和灵活性。其核心奥秘在于 list_head 结构体和强大的 container_of 宏。

掌握这种数据结构，不仅有助于理解和阅读 Linux 内核源码，更能将这种高效的设计思想应用到自己的项目中，尤其是在开发需要高性能和低开销的基础库时。记住关键的最佳实践：使用 _safe 版本宏进行可能删除节点的遍历，并手动管理节点内存的分配与释放。

9. 参考#

  1. Linux Kernel Source Code, include/linux/list.h
  2. Linux Kernel Source Code, include/linux/kernel.h (for container_of)
  3. Understanding the Linux Kernel, by Daniel P. Bovet and Marco Cesati
  4. The Linux Kernel Linked List Explained
2026-03