目录1.list_for_each_entry系列正向遍历: list_for_each_entrylist_entry -- ★container_of★container_of实验内核中contain_of的常见应用★contain_of速记图list_entry container_oflist_first_entry和list_last_entrylist_next_entrylist_prev_entrylist_entry_is_head遍历算法框架反向遍历: list_for_each_entry_reverse2.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_entrylist_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.var11; a_obj.var22; a_obj.var3a; a_obj.var41.5; a_obj.var52; struct a* pacontainer_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.itest_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.var11; a_obj.var22; a_obj.var3a; a_obj.var41.5; a_obj.var52; 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 -stdc99 -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.var11; a_obj.var22; a_obj.var3a; a_obj.var41.5; a_obj.var52; struct a* pacontainer_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_entrylist_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_headlist_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_continuelist_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_reverselist_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_reverselist_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_continuelist_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; }