Linux 侵入式链表详解

这里 list_head 直接嵌入在 my_data 中。数据对象和链表节点在内存中是连续的，通过 container_of 宏从节点指针反推完整结构体地址。

侵入式链表的优势

为什么 Linux 内核偏爱这种设计？主要有四点原因：

1. 内存效率高：不需要额外的指针来存储数据，内存布局紧凑，减少了碎片。
2. 性能优势：减少了一次内存分配，且数据访问路径更短。更重要的是，由于数据与节点在一起，CPU 缓存命中率更高。
3. 灵活性：一个对象可以同时属于多个链表。只需在结构体中包含多个 list_head 成员即可。
4. 零开销抽象：编译后几乎没有额外开销，非常适合内核开发等对性能敏感的场景。

Linux 内核中的实现

Linux 内核在 include/linux/list.h 中实现了完整的侵入式双向链表。这是经过多年优化的工业级实现，所有内核开发者都需要熟悉它。

核心数据结构与初始化

list_head 结构体

struct list_head {
    struct list_head *next; // 指向下一个节点
    struct list_head *prev; // 指向前一个节点
};

只包含两个指针，非常简洁。

初始化宏

// 声明并初始化链表头
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 初始化函数
static inline void INIT_LIST_HEAD(struct list_head *list) {
    WRITE_ONCE(list->next, list);
    list->prev = list;
}

初始化后的状态是 next 和 prev 都指向自身，形成一个空的双向循环链表。这意味着判断链表是否为空只需要检查 head->next == head。

核心操作函数

添加节点

list_add - 在头部添加

/**
 * list_add - 在链表头部添加新节点
 * @new: 要添加的新节点
 * @head: 链表头
 *
 * 在 head 之后插入 new 节点，适合实现栈（LIFO）
 */
static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}

list_add_tail - 在尾部添加

/**
 * list_add_tail - 在链表尾部添加新节点
 * @new: 要添加的新节点
 * @head: 链表头
 *
 * 在 head 之前插入 new 节点，适合实现队列（FIFO）
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head) {
    __list_add(new, head->prev, head);
}

删除节点

list_del - 删除节点

/**
 * list_del - 从链表中删除节点
 * @entry: 要删除的节点
 *
 * 注意：删除后节点处于未定义状态
 */
static inline void list_del(struct list_head *entry) {
    __list_del_entry(entry);
    entry->next = LIST_POISON1; // 设置为毒药指针，便于调试
    entry->prev = LIST_POISON2;
}

list_del_init - 删除并重新初始化

/**
 * list_del_init - 删除节点并重新初始化
 * @entry: 要删除的节点
 *
 * 删除后节点可以重新使用
 */
static inline void list_del_init(struct list_head *entry) {
    __list_del_entry(entry);
    INIT_LIST_HEAD(entry);
}

遍历链表

list_for_each - 遍历链表节点

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

list_for_each_entry - 遍历链表中的数据

这是最常用的宏，它会自动帮你拿到结构体指针。

#define list_for_each_entry(pos, head, member) \
    for (pos = list_first_entry(head, typeof(*pos), member); \
         &pos->member != (head); \
         pos = list_next_entry(pos, member))

list_for_each_entry_safe - 安全遍历

如果在遍历时需要删除节点，必须使用这个带 _safe 后缀的版本，因为它会提前保存下一个节点的指针。

#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); \
         &pos->member != (head); \
         pos = n, n = list_next_entry(n, member))

container_of 宏详解

container_of 宏是侵入式链表的灵魂。它的功能是从结构体成员的指针获取整个结构体的指针。

宏定义

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

工作原理

1. offsetof 宏

#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

原理很简单：将 0 强制转换为 TYPE* 类型，然后取 MEMBER 的地址。因为基址是 0，所以得到的就是成员相对于结构体起始地址的偏移量。

2. 计算过程

假设我们有如下结构：

struct my_data {
    int value;
    struct list_head list;
};
struct my_data *data;
struct list_head *list_ptr = &data->list;

现在要从 list_ptr 获取 data：

1. 获取成员类型：typeof(((struct my_data*)0)->list) 确保类型匹配。
2. 字节运算：将指针转为 char* 以便进行字节级减法。
3. 减去偏移量：result = (struct my_data*)(__mptr_char - offsetof(...))。

内存布局示意：

地址：0x1000 0x1024 [my_data] [list]
      ^           ^
      |           |
   data       list_ptr
   offsetof = 0x1024 - 0x1000 = 0x24
   从 list_ptr 获取 data: data = list_ptr - offsetof = 0x1024 - 0x24 = 0x1000 ✓

使用示例

示例 1：基本使用

#include <stdio.h>
#include <stdlib.h>
#include "list.h" // 假设包含了 list.h

// 定义数据结构
struct student {
    int id;
    char name[32];
    int age;
    struct list_head list; // 链表节点
};

int main(void) {
    // 初始化链表头
    LIST_HEAD(student_list);

    // 创建学生数据
    struct student *s1 = malloc(sizeof(struct student));
    s1->id = 1;
    strcpy(s1->name, "Alice");
    s1->age = 20;
    INIT_LIST_HEAD(&s1->list);

    struct student *s2 = malloc(sizeof(struct student));
    s2->id = 2;
    strcpy(s2->name, "Bob");
    s2->age = 21;
    INIT_LIST_HEAD(&s2->list);

    // 添加到链表
    list_add(&s1->list, &student_list);
    list_add(&s2->list, &student_list);

    // 遍历链表
    struct student *pos;
    list_for_each_entry(pos, &student_list, list) {
        printf("ID: %d, Name: %s, Age: %d\n", pos->id, pos->name, pos->age);
    }

    // 清理
    struct student *n;
    list_for_each_entry_safe(pos, n, &student_list, list) {
        list_del(&pos->list);
        free(pos);
    }
    return 0;
}

示例 2：多链表管理

一个对象可以同时属于多个链表，这在进程调度中很常见：

struct task {
    int pid;
    char name[32];
    struct list_head run_list;   // 运行队列
    struct list_head wait_list;  // 等待队列
    struct list_head all_tasks;  // 所有任务列表
};

// 初始化
struct task *t = malloc(sizeof(struct task));
INIT_LIST_HEAD(&t->run_list);
INIT_LIST_HEAD(&t->wait_list);
INIT_LIST_HEAD(&t->all_tasks);

// 添加到不同链表
list_add(&t->run_list, &run_queue);
list_add(&t->all_tasks, &task_list);

应用场景

1. Linux 内核

内核中无处不在：

• 进程管理：进程链表、运行队列
• 内存管理：页框链表、伙伴系统
• 文件系统：inode 链表、dentry 缓存
• 网络协议栈：sk_buff 链表

2. 高性能系统编程

• 嵌入式系统：资源受限环境
• 实时系统：低延迟要求
• 游戏引擎：性能敏感场景

总结

侵入式链表通过牺牲一点代码的可读性（需要修改结构体），换取了极高的内存效率和性能。掌握它的关键点在于：

1. 理解 container_of：这是从成员指针反推结构体的核心。
2. 正确使用遍历宏：区分普通遍历和安全遍历，防止删除节点时崩溃。
3. 注意内存管理：删除节点后要记得释放内存，或者使用 list_del_init 保持节点可用。
4. 理解循环链表：链表头指向自身表示空链表，这是判断结束条件的依据。

对于系统编程、驱动开发或任何对内存敏感的应用，这都是必备的基础知识。