Linux侵入式链表详解

侵入式链表详解

目录

1. 什么是侵入式链表
2. 与传统链表的对比
3. 侵入式链表的优势
4. Linux内核中的实现
5. 核心数据结构
6. 核心操作函数
7. container_of宏详解
8. 使用示例
9. 应用场景
10. 总结

什么是侵入式链表

**侵入式链表（Intrusive Linked List）**是一种特殊的链表实现方式，它的特点是：链表节点直接嵌入到数据结构内部，而不是通过指针指向独立的数据节点。

在侵入式链表中，链表节点（list_head）是数据结构的一个成员，而不是独立存在的。这种设计使得链表操作更加高效，并且不需要额外的内存分配。

核心思想

与传统链表的对比

传统链表（非侵入式）

传统链表通常采用以下结构：

// 传统链表节点结构structlist_node{void*data;// 指向实际数据structlist_node*next;// 指向下一个节点structlist_node*prev;// 指向前一个节点};

特点：

• 链表节点和数据是分离的
• 需要额外的指针来存储数据
• 每次访问数据都需要解引用
• 内存布局不连续

说明：list_node中的data字段是一个指针，指向实际的数据对象，数据对象和链表节点在内存中是分离的。

自包含链表（专用链表节点）

还有一种常见的链表实现方式，数据直接嵌入在链表节点中：

// 自包含链表节点结构structlist_node{inta;// 数据直接嵌入在节点中structlist_node*next;// 指向下一个节点structlist_node*prev;// 指向前一个节点};

特点：

• 数据直接存储在链表节点中，不是指针
• 链表节点就是数据结构本身
• 不需要额外的指针来访问数据
• 内存布局连续，但只适用于单一数据类型
• 简单直接，适合特定场景

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

适用场景：

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

侵入式链表

侵入式链表的结构：

// 侵入式链表节点结构structlist_head{structlist_head*next;// 指向下一个节点structlist_head*prev;// 指向前一个节点};// 数据结构中包含list_headstructmy_data{intvalue;charname[32];structlist_headlist;// 链表节点嵌入在数据结构中};

特点：

• 链表节点直接嵌入在数据结构中
• 不需要额外的指针存储数据
• 通过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结构体

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

这是侵入式链表的核心数据结构，只包含两个指针，非常简洁。

初始化宏

// 初始化宏定义#defineLIST_HEAD_INIT(name){&(name),&(name)}// 声明并初始化链表头#defineLIST_HEAD(name)\structlist_headname=LIST_HEAD_INIT(name)// 初始化函数staticinlinevoidINIT_LIST_HEAD(structlist_head*list){WRITE_ONCE(list->next,list);list->prev=list;}

初始化后的状态：

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

核心操作函数

1. 添加节点

list_add - 在头部添加

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

list_add_tail - 在尾部添加

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

__list_add - 内部插入函数

/** * __list_add - 在两个已知节点之间插入新节点 * @new: 新节点 * @prev: 前一个节点 * @next: 后一个节点 */staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_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: 要删除的节点 * * 注意：删除后节点处于未定义状态 */staticinlinevoidlist_del(structlist_head*entry){__list_del_entry(entry);entry->next=LIST_POISON1;// 设置为毒药指针，便于调试entry->prev=LIST_POISON2;}staticinlinevoid__list_del_entry(structlist_head*entry){if(!__list_del_entry_valid(entry))return;__list_del(entry->prev,entry->next);}staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next->prev=prev;WRITE_ONCE(prev->next,next);}

list_del_init - 删除并重新初始化

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

3. 遍历链表

list_for_each - 遍历链表节点

/** * list_for_each - 遍历链表 * @pos: 用作循环游标的list_head指针 * @head: 链表头 */#definelist_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在数据结构中的成员名 */#definelist_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在数据结构中的成员名 */#definelist_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: 链表头 */staticinlineintlist_empty(conststructlist_head*head){returnREAD_ONCE(head->next)==head;}

list_move - 移动节点

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

container_of宏详解

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

宏定义

/** * container_of - 从成员指针获取包含它的结构体指针 * @ptr: 成员指针 * @type: 结构体类型 * @member: 成员在结构体中的名称 */#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)->member)*__mptr=(ptr);\(type*)((char*)__mptr-offsetof(type,member));})

工作原理

1. offsetof宏

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

原理：

• 将0强制转换为TYPE*类型
• 访问MEMBER成员，得到成员相对于结构体起始地址的偏移量
• 由于基址是0，所以&((TYPE *)0)->MEMBER就是偏移量

示例：

structmy_data{intvalue;// 偏移量: 0charname[32];// 偏移量: 4structlist_headlist;// 偏移量: 36 (假设)};// offsetof(struct my_data, list) = 36

2. container_of计算过程

假设我们有：

structmy_data{intvalue;structlist_headlist;};structmy_data*data;structlist_head*list_ptr=&data->list;

现在要从list_ptr获取data：

// 步骤1: 获取list成员的类型并验证consttypeof(((structmy_data*)0)->list)*__mptr=list_ptr;// 步骤2: 将指针转换为char*以便进行字节级运算char*__mptr_char=(char*)__mptr;// 步骤3: 减去偏移量得到结构体起始地址structmy_data*result=(structmy_data*)(__mptr_char-offsetof(structmy_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// 定义数据结构structstudent{intid;charname[32];intage;structlist_headlist;// 链表节点};intmain(void){// 初始化链表头LIST_HEAD(student_list);// 创建学生数据structstudent*s1=malloc(sizeof(structstudent));s1->id=1;strcpy(s1->name,"Alice");s1->age=20;INIT_LIST_HEAD(&s1->list);structstudent*s2=malloc(sizeof(structstudent));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);// 遍历链表structstudent*pos;list_for_each_entry(pos,&student_list,list){printf("ID: %d, Name: %s, Age: %d\n",pos->id,pos->name,pos->age);}// 清理list_for_each_entry_safe(pos,n,&student_list,list){list_del(&pos->list);free(pos);}return0;}

示例2：多个链表

// 一个对象可以同时属于多个链表structtask{intpid;charname[32];structlist_headrun_list;// 运行队列structlist_headwait_list;// 等待队列structlist_headall_tasks;// 所有任务列表};// 初始化structtask*t=malloc(sizeof(structtask));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);voidenqueue(structlist_head*item){list_add_tail(item,&queue);}structlist_head*dequeue(void){if(list_empty(&queue))returnNULL;structlist_head*item=queue.next;list_del(item);returnitem;}

示例4：实现栈

// 使用list_add实现LIFO栈LIST_HEAD(stack);voidpush(structlist_head*item){list_add(item,&stack);}structlist_head*pop(void){if(list_empty(&stack))returnNULL;structlist_head*item=stack.next;list_del(item);returnitem;}

应用场景

1. Linux内核

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

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

2. 高性能系统编程

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

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

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

structprocess{intpid;structlist_headrunq;// 运行队列structlist_headwaitq;// 等待队列structlist_headchildren;// 子进程列表structlist_headsiblings;// 兄弟进程列表};

总结

侵入式链表的优点

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

侵入式链表的缺点

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

适用场景

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

关键要点

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