Linux 侵入式链表详解

说明： 数据字段（如 int a）直接嵌入在链表节点结构体中，链表节点本身就是数据容器。

适用场景：

• 数据类型简单且固定
• 不需要存储复杂数据结构
• 适合教学示例和简单应用

侵入式链表

侵入式链表的结构：

// 侵入式链表节点结构
struct list_head {
    struct list_head* next; // 指向下一个节点
    struct list_head* prev; // 指向前一个节点
};

// 数据结构中包含 list_head
struct my_data {
    int value;
    char name[32];
    struct list_head list; // 链表节点嵌入在数据结构中
};

特点：

• 链表节点直接嵌入在数据结构中
• 不需要额外的指针存储数据
• 通过 container_of宏从节点指针获取完整数据结构
• 内存布局更紧凑

说明： list_head直接嵌入在 my_data结构体中，数据对象和链表节点在内存中是连续的，通过 list成员连接。

三种链表类型对比总结

侵入式链表的优势

1. 内存效率高

• 无额外指针开销：不需要额外的指针来存储数据
• 内存布局紧凑：数据连续存储，缓存友好

2. 性能优势

• 减少内存分配：不需要为链表节点单独分配内存
• 减少指针解引用：数据访问路径更短
• 更好的缓存局部性：数据连续存储，提高缓存命中率

3. 灵活性

• 一个对象可以同时属于多个链表：只需在结构中包含多个 list_head成员
• 类型无关：链表操作不关心数据类型，通用性强

4. 适合系统编程

• 零开销抽象：编译后几乎没有额外开销
• 适合内核开发：Linux 内核广泛使用

Linux 内核中的实现

Linux 内核在 include/linux/list.h中实现了完整的侵入式双向链表。这是经过多年优化的工业级实现。

文件位置

linux-4.14.7/include/linux/list.h 

核心数据结构

list_head 结构体

struct list_head {
    struct list_head* next; // 指向下一个节点
    struct list_head* 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) {
    WRITE_ONCE(list->next, list);
    list->prev = list;
}

初始化后的状态：

• next和 prev都指向自身
• 形成一个空的双向循环链表

核心操作函数

1. 添加节点

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_add - 内部插入函数

/**
 * __list_add - 在两个已知节点之间插入新节点
 * @new: 新节点
 * @prev: 前一个节点
 * @next: 后一个节点
 */
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) {
    if (!__list_add_valid(new, prev, next)) return;
    next->prev = new;
    new->next = next;
    new->prev = prev;
    WRITE_ONCE(prev->next, new);
}

2. 删除节点

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;
}

static inline void __list_del_entry(struct list_head *entry) {
    if (!__list_del_entry_valid(entry)) return;
    __list_del(entry->prev, entry->next);
}

static inline void __list_del(struct list_head *prev, struct list_head *next) {
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
}

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);
}

3. 遍历链表

list_for_each - 遍历链表节点

/**
 * list_for_each - 遍历链表
 * @pos: 用作循环游标的 list_head 指针
 * @head: 链表头
 */
#define list_for_each(pos, head) \
    for(pos = (head)->next; pos != (head); pos = pos->next)

list_for_each_entry - 遍历链表中的数据

/**
 * list_for_each_entry - 遍历链表中的数据项
 * @pos: 用作循环游标的数据结构指针
 * @head: 链表头
 * @member: list_head 在数据结构中的成员名
 */
#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 - 安全遍历（允许删除）

/**
 * list_for_each_entry_safe - 安全遍历，允许在遍历时删除节点
 * @pos: 用作循环游标的数据结构指针
 * @n: 另一个数据结构指针，用作临时存储
 * @head: 链表头
 * @member: list_head 在数据结构中的成员名
 */
#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))

4. 其他常用操作

list_empty - 判断链表是否为空

/**
 * list_empty - 判断链表是否为空
 * @head: 链表头
 */
static inline int list_empty(const struct list_head *head) {
    return READ_ONCE(head->next) == head;
}

list_move - 移动节点

/**
 * list_move - 将节点从一个链表移动到另一个链表头部
 * @list: 要移动的节点
 * @head: 目标链表头
 */
static inline void list_move(struct list_head *list, struct list_head *head) {
    __list_del_entry(list);
    list_add(list, head);
}

container_of 宏详解

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

宏定义

/**
 * container_of - 从成员指针获取包含它的结构体指针
 * @ptr: 成员指针
 * @type: 结构体类型
 * @member: 成员在结构体中的名称
 */
#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，所以 &((TYPE *)0)->MEMBER就是偏移量

示例：

struct my_data {
    int value; // 偏移量：0
    char name[32]; // 偏移量：4
    struct list_head list; // 偏移量：36 (假设)
};
// offsetof(struct my_data, list) = 36

2. container_of 计算过程

假设我们有：

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

现在要从 list_ptr获取 data：

// 步骤 1: 获取 list 成员的类型并验证
const typeof(((struct my_data*)0)->list) *__mptr = list_ptr;
// 步骤 2: 将指针转换为 char*以便进行字节级运算
char *__mptr_char = (char*)__mptr;
// 步骤 3: 减去偏移量得到结构体起始地址
struct my_data* result = (struct my_data*)(__mptr_char - offsetof(struct my_data, list));

内存布局示意：

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

为什么需要 typeof

typeof用于类型检查，确保传入的 ptr确实是 member类型的指针，提高代码安全性。

使用示例

示例 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);

示例 3：实现队列

// 使用 list_add_tail 实现 FIFO 队列
LIST_HEAD(queue);
void enqueue(struct list_head* item) {
    list_add_tail(item, &queue);
}
struct list_head* dequeue(void) {
    if (list_empty(&queue)) return NULL;
    struct list_head* item = queue.next;
    list_del(item);
    return item;
}

示例 4：实现栈

// 使用 list_add 实现 LIFO 栈
LIST_HEAD(stack);
void push(struct list_head* item) {
    list_add(item, &stack);
}
struct list_head* pop(void) {
    if (list_empty(&stack)) return NULL;
    struct list_head* item = stack.next;
    list_del(item);
    return item;
}

应用场景

1. Linux 内核

Linux 内核中广泛使用侵入式链表：

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

2. 高性能系统编程

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

3. 需要多链表管理的场景

当一个对象需要同时属于多个链表时，侵入式链表特别有用：

struct process {
    int pid;
    struct list_head runq; // 运行队列
    struct list_head waitq; // 等待队列
    struct list_head children; // 子进程列表
    struct list_head siblings; // 兄弟进程列表
};

总结

侵入式链表的优点

1. 内存效率高：无额外指针开销
2. 性能优秀：缓存友好，访问速度快
3. 灵活性强：一个对象可属于多个链表
4. 类型无关：通用性强，代码复用性好

侵入式链表的缺点

1. 侵入性：需要修改数据结构，添加 list_head成员
2. 学习曲线：container_of宏的理解需要一定时间
3. 调试困难：指针操作较多，调试相对复杂

适用场景

• ✅ 系统编程（内核、驱动）
• ✅ 性能敏感的应用
• ✅ 需要多链表管理的场景
• ✅ 内存受限的环境
• ❌ 简单的用户态应用（可能过度设计）

关键要点

1. 理解 container_of宏：这是侵入式链表的精髓
2. 正确使用遍历宏：区分普通遍历和安全遍历
3. 注意内存管理：删除节点后要释放内存
4. 理解循环链表：链表头指向自身表示空链表