news 2026/9/30 2:30:28

LKDS2.Linux内核的双向链表代码解析(2) 遍历算法

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
LKDS2.Linux内核的双向链表代码解析(2) 遍历算法

目录

1.list_for_each_entry系列

正向遍历: list_for_each_entry

list_entry --> ★container_of★

container_of实验

内核中contain_of的常见应用

★contain_of速记图

list_entry == container_of

list_first_entry和list_last_entry

list_next_entry

list_prev_entry

list_entry_is_head

遍历算法框架

反向遍历: list_for_each_entry_reverse

2.list_for_each系列

正向遍历: list_for_each

正向遍历: list_for_each_continue

反向遍历: list_for_each_prev

算链表节点总数: list_count_nodes()

接着LKDS1.Linux内核的双向链表代码解析(1) 初始化、插入、删除文章继续分析

实现遍历算法的有2种: list_for_each_entry系列、list_for_each系列

1.list_for_each_entry系列

正向遍历

list_for_each_entry

/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */ #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member) /** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */ #define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member) /** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member))

list_for_each_entry里面会使用list_first_entry、list_next_entry,后两者的内部实现依靠list_entry,所以这里先讲list_entry

list_entry --> ★container_of★

list_entry内部实现使用了container_of

/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member)

container_of这个宏非常著名,经常出现在各个分析内核的网络文章中,也出现在《Linux Kernel Development》 、 《Professional Linux kernel architecture》、《Linux Device Drivers》等经典内核著作中,定义在/include/linux/container_of.h中:

/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * * WARNING: any const qualifier of @ptr is lost. * Do not use container_of() in new code. */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ static_assert(__same_type(*(ptr), ((type *)0)->member) || \ __same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); })

static_assert可以不用管,简化为:

/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * * WARNING: any const qualifier of @ptr is lost. * Do not use container_of() in new code. */ #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ ((type *)(__mptr - offsetof(type, member))); })

从注释中得出container_of的作用: 从结构体成员的地址反推出结构体的首地址

,这个反推的算法我曾经在OS20.【Linux】进程状态(2) 僵尸进程、孤儿进程和进程优先级文章讲过,文中有一个重要的观点:

如果结构体存储在地址为0的地方(只是利用这个特性获取成员的偏移量),那么成员变量的地址就等于成员变量在结构体在的偏移量

其实container_of也是这样做的,对于结构体的其中一个成员,该宏的ptr指向该成员的存储的空间位置,type是结构体的类型,member是该成员在结构体中定义的名字

container_of里面使用了offsetof宏,定义在/include/linux/stddef.h中:

#undef offsetof #define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)

__builtin_offsetof并没有在内核里面定义,从名字builtin可以看到,这个是GCC/Clang编译器内置的宏

其实早期的内核是直接利用空指针获取成员的偏移量的,比如v2.6.0:

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

结论: offsetof负责获取结构体成员的偏移量

回到container_of分析,先复制ptr为__mptr,之后让__mptr减去member成员在结构体内的偏移量,这样修改后的__mptr就指向实际结构体对象的首地址

为什么内核要多次一举使用__mptr? 这里做个实验

container_of实验

test_container_of.c写入:

#include <stdio.h> #include <stddef.h> //stddef内置了offsetof实现 #undef offsetof #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #define container_of(ptr, type, member) ({ \ ((type *)(ptr - offsetof(type, member))); }) struct a { int var1; short var2; char var3; float var4; double var5; }; int main() { struct a a_obj; a_obj.var1=1; a_obj.var2=2; a_obj.var3='a'; a_obj.var4=1.5; a_obj.var5=2; struct a* pa=container_of(&(a_obj.var4),struct a,var4); printf("%c\n",pa->var3); //按理来说,应该输出字符a return 0; }

编译:

gcc -g test_container_of.c -o test_container_of.out

运行结果: 按理来说,应该输出字符a,但什么都没有输出:

问题出在哪里? 这里使用gdb调试,先在printf("%c",pa->var3)下断点,接着运行:

停在了第27行位置:

看看pa的值和a_obj对象的地址,发现地址不一样!

为什么地址不一样? 需要看看GCC预处理后替换的代码,才能定位问题:

gcc -E test_container_of.c -o test_container_of.i

test_container_of.i比较长,这里看最后几行:

# 9 "test_container_of.c" struct a { int var1; short var2; char var3; float var4; double var5; }; int main() { struct a a_obj; a_obj.var1=1; a_obj.var2=2; a_obj.var3='a'; a_obj.var4=1.5; a_obj.var5=2; struct a* pa=({ ((struct a *)(&(a_obj.var4) - ((size_t) &((struct a *)0)->var4))); }); printf("%c",pa->var3); return 0; }

注意划线的地方: (struct a *)(&(a_obj.var4)- ((size_t) &((struct a *)0)->var4)

&(a_obj.var4)类型和var4一样,都是float类型,((size_t) &((struct a *)0)->var4)值为8,读者可以通过63.【C语言】再议结构体(上) 结构体的特殊声明和内存对齐文章讲的内存对齐的偏移量的计算方法来算或者直接使用gdb的内置命令查看结构体的各个成员的偏移量:

ptype /o struct a

现在可以知道为什么结果不对了: &(a_obj.var4)是float类型,由于一个float变量占4个字节,那么(struct a *)(&(a_obj.var4)- ((size_t) &((struct a *)0)->var4)在字节层面上是(struct a *)(&(a_obj.var4)-4*((size_t) &((struct a *)0)->var4)

所以内核必须使用__mptr,是void*类型,在GCC扩展语法中,对void*类型的指针+/- 1就等价为+/- 1字节(这其实不符合C语言标准的)读者可以尝试以下代码验证:

#include <stdio.h> int main() { printf("%ld\n",sizeof(void)); return 0; }

编译命令:

gcc test_void_size.c -std=c99 -pedantic-errors -o test_void_size.out

报错:

如果在默认情况下编译是可行的,输出sizeof(void)的大小为1:

gcc test_void_size.c -o test_void_size.out

加上_mptr后,再次测试:

#include <stdio.h> #include <stddef.h> #undef offsetof //stddef内置了offsetof实现,因此先取消原来有的定义后,才能自己定义自己实现的offsetof #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ ((type *)(__mptr - offsetof(type, member))); }) struct a { int var1; short var2; char var3; float var4; double var5; }; int main() { struct a a_obj; a_obj.var1=1; a_obj.var2=2; a_obj.var3='a'; a_obj.var4=1.5; a_obj.var5=2; struct a* pa=container_of(&(a_obj.var4),struct a,var4); printf("%c\n",pa->var3); //按理来说,应该输出字符a return 0; }

运行结果: 正常输出预期字符

内核中contain_of的常见应用

比如rds_tcp_accept_worker(),定义在/net/rds/tcp.c中:

static void rds_tcp_accept_worker(struct work_struct *work) { struct rds_tcp_net *rtn = container_of(work, struct rds_tcp_net, rds_tcp_accept_w); while (rds_tcp_accept_one(rtn) == 0) cond_resched(); }

struct rds_tcp_net定义在/net/rds/tcp.h中:

/* per-network namespace private data for this module */ struct rds_tcp_net { /* serialize "rds_tcp_accept_one" with "rds_tcp_accept_lock" * to protect "rds_tcp_accepted_sock" */ struct mutex rds_tcp_accept_lock; struct socket *rds_tcp_listen_sock; struct socket *rds_tcp_accepted_sock; struct work_struct rds_tcp_accept_w; struct ctl_table_header *rds_tcp_sysctl; const struct ctl_table *ctl_table; int sndbuf_size; int rcvbuf_size; };

struct work_struct定义在/include/linux/workqueue_types.h中:

struct work_struct { atomic_long_t data; struct list_head entry; work_func_t func; #ifdef CONFIG_LOCKDEP struct lockdep_map lockdep_map; #endif };

这些结构体组织起来如下图:

对于结构体嵌套结构体,如下图:

这里不需要管rds_tcp_accept_worker()具体是干什么的,只需要理解container_of是怎么算的:

container_of(work, struct rds_tcp_net, rds_tcp_accept_w)得到的是struct rds_tcp_net对象的首地址

★contain_of速记图

list_entry == container_of

回到list_entry进行分析:

/** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member)

可以发现,list_entry就是container_of换个皮,纯粹是编译期的一个宏别名,但能降低使用者的认知负担,因为list_entry比container_of意思更清晰

更重要的是,list_entry找到的是充当节点的结构体对象的首地址,并将这个地址以type *(包含该节点的结构体类型指针)的形式返回,以便直接访问该结构体的所有成员!!!

不明白上面这句话的,可以看看这个例子,之前在OS17.【Linux】进程基础知识(1)文章讲过task_struct,但并没有讲过怎么串联的

Linux内核有一个全局的进程链表,用于串联所有父子进程,实现是通过task_struct结构体的tasks成员:

struct task_struct { //...... struct list_head tasks; //...... };

上面讲了list_entry宏,那么可以通过tasks来访问task_struct的其它成员,方法是:

list_entry(&xxx,struct task_struct,tasks);

list_first_entry和list_last_entry

list_first_entry内部复用了list_entry:

/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */ #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)

传入list_first_entry的ptr通常是哨兵头节点,这样(ptr)->next就能指向第一个存储有效数据的节点了

同理,list_last_entry内部也复用了list_entry:

/** * list_last_entry - get the last element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */ #define list_last_entry(ptr, type, member) \ list_entry((ptr)->prev, type, member)

由于是带头双向循环链表,那么哨兵头节点的前一个节点就是链表的最后一个节点

list_next_entry
/** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */ #define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member)

对contain_of速记图加上(pos)->member.next、typeof(*(pos))、member说明:

讲完了list_next_entry,顺便讲讲list_prev_entry和list_entry_is_head

list_prev_entry

只是将list_next_entry内部实现的(pos)->member.next改成(pos)->member.prev,不再赘述

/** * list_prev_entry - get the prev element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */ #define list_prev_entry(pos, member) \ list_entry((pos)->member.prev, typeof(*(pos)), member)
list_entry_is_head

判断是否是哨兵头节点,常用于循环结束条件

/** * list_is_head - tests whether @list is the list @head * @list: the entry to test * @head: the head of the list */ static inline int list_is_head(const struct list_head *list, const struct list_head *head) { return list == head; } /** * list_entry_is_head - test if the entry points to the head of the list * @pos: the type * to cursor * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_entry_is_head(pos, head, member) \ list_is_head(&pos->member, (head))
遍历算法框架

回到list_for_each_entry:

/** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member))

2.该宏内部使用的是for循环,从链表的第一个存储有效数据的节点到最后一个存储有效数据的节点,框架是:

for (pos = 第一个节点; pos != 哨兵头节点; pos = pos->next)

list_for_each_entry_continue

list_for_each_entry_continue在list_for_each_entry的基础上,添加了continue功能

/** * list_for_each_entry_continue - continue iteration over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */ #define list_for_each_entry_continue(pos, head, member) \ for (pos = list_next_entry(pos, member); \ !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member))

continue功能体现在"pos = list_next_entry(pos, member)",即从pos的下一个节点开始遍历,一直到链表头结束

list_for_each_entry_continue_reverse

list_for_each_entry_continue_reverse在list_for_each_entry_continue的基础上,添加了reverse功能

/** * list_for_each_entry_continue_reverse - iterate backwards from the given point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Start to iterate over list of given type backwards, continuing after * the current position. */ #define list_for_each_entry_continue_reverse(pos, head, member) \ for (pos = list_prev_entry(pos, member); \ !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member))

从pos的前一个节点开始遍历,一直到链表头结束

list_for_each_entry_from

/** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing from current position. */ #define list_for_each_entry_from(pos, head, member) \ for (; !list_entry_is_head(pos, head, member); \ pos = list_next_entry(pos, member))

对比list_for_each_entry:

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

发现list_for_each_entry_from在list_for_each_entry的基础上,去除了for循环的初始化

for (初始化; 条件; 迭代) { 循环体; }

list_for_each_entry_from是从pos指向的节点开始遍历,一直到链表头结束

list_for_each_entry_from_reverse

list_for_each_entry_from_reverse是list_for_each_entry_from的反向.不再赘述

/** * list_for_each_entry_from_reverse - iterate backwards over list of given type * from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate backwards over list of given type, continuing from current position. */ #define list_for_each_entry_from_reverse(pos, head, member) \ for (; !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member))

反向遍历: list_for_each_entry_reverse

反向遍历就是将list_for_each_entry内部实现倒过来循环就行了,这里给出代码就不分析了

/** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ !list_entry_is_head(pos, head, member); \ pos = list_prev_entry(pos, member))

2.list_for_each系列

正向遍历: list_for_each

使用了for循环来遍历链表的每个节点,但并没有像list_for_each_entry系列那样使用container_of函数

其次传进去的pos被赋值为head->next,即从链表的第一个有效节点开始遍历

/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)

结论: list_for_each根本不打算从list_head反推出宿主结构体,它遍历的是"链表节点本身",不是“包含链表节点的结构体"

正向遍历: list_for_each_continue

list_for_each_continue相比list_for_each,只有一点不一样,list_for_each_continue的pos是从pos->next开始遍历,而不是从链表的第一个有效节点开始遍历,所以称为"continue",有"继续"的含义

/** * list_for_each_continue - continue iteration over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. * * Continue to iterate over a list, continuing after the current position. */ #define list_for_each_continue(pos, head) \ for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)

反向遍历: list_for_each_prev

和list_for_each骨架一样,只不过将list_for_each的内部实现的next改成了prev,不再赘述

/** * list_for_each_prev - iterate over a list backwards * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)

算链表节点总数: list_count_nodes()

就是在list_for_each基础上,增加了计数器count,最终返回count

/** * list_count_nodes - count nodes in the list * @head: the head for your list. */ static inline size_t list_count_nodes(struct list_head *head) { struct list_head *pos; size_t count = 0; list_for_each(pos, head) count++; return count; }
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/9/30 2:30:23

低功耗UPF介绍(一)

一、功耗简介 传统分类&#xff1a; 动态功耗(Dynamic Power)&#xff1a;晶体管门电路翻转时产生的功耗 静态功耗(Static Power)&#xff1a;晶体管不翻转时由非理想效应产生的功耗 业内计算分类&#xff1a; 泄漏功耗(Leakage Power)&#xff1a;由沟道、栅极、衬底等非理想漏…

作者头像 李华
网站建设 2026/9/30 2:29:36

Linux 命令大全之 bye 命令：FTP 交互模式下中断连接并退出客户端

文档教程 【免费下载链接】linux-command Linux命令大全搜索工具&#xff0c;内容包含Linux命令手册、详解、学习、搜集。https://git.io/linux 项目地址&#xff1a; https://gitcode.com/GitHub_Trending/linux/linux-command 点击查看 免费下载 bye 是传统 ftp 客户端在交互…

作者头像 李华
网站建设 2026/9/30 2:29:12

连麦教学，音画同步是底线

同事家孩子在网上学钢琴&#xff0c;一节一对一好几百块&#xff0c;上了几节就不想上了。问原因&#xff0c;说是老师弹一个和弦&#xff0c;孩子这边过了两秒才听见&#xff0c;手还没落下去老师已经讲下一个了。两边越对越乱&#xff0c;孩子越练越没信心&#xff0c;钱白花…

作者头像 李华
网站建设 2026/9/30 2:28:00

基于SpringBoot+Vue的摄影预约系统的设计与实现

温馨提示&#xff1a;本人主页置顶文章(点我)开头有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 一、 项目背景与意义 随着生活水平的提高和社交媒体的普及&#xff0c;人们对个性化、高品质的摄影服务需求日益增长。传统的摄影预约方式&#xff0c;如电话、微信沟通…

作者头像 李华