跟我学C++中级篇—Linux内核中链表分析-平芜编程栈

一、链表

链表是开发者学习数据结构时最初的一种数据结构，它的应用是非常广泛的。而且在实际的开发，特别是面试中，对链表的各种应用都是无法绕开的。一些常见的算法也是以链表为基础的。链表的应用形式有很多，一般在教材中学习到的也就是开发中常见到的链表其基本的应用方式如下：

//双向链表structlist{intiValue;int*pData;structlist*pNext;// 下一个节点structlist*pPev;// 前一个节点};

可以把链表当成一个一个索链的结点，它们通过指针象“铁环一样”紧紧的链接在一起，形成一条索链一样的表。

二、内核中的链表与传统链表对比

看过内核源码的开发者可能在内核中也看到过链表的定义形势，会发现与教材中的传统的链表有些不同。下面先看一下内核中的代码的链表定义：

//双向链表structlist_head{structlist_head*next,*prev;};//linux-6.9.12/virt/kvm/eventfd.cstruct_ioeventfd{structlist_headlist;u64 addr;intlength;structeventfd_ctx*eventfd;u64 datamatch;structkvm_io_devicedev;u8 bus_idx;bool wildcard;};

把上面的链表代码和教材中的链表代码比较，大家可以发现有什么不同么？最典型的就是教材中的链表包含着数据本身，而在内核中则是数据本身包含链表（这样说可能不太准确，但容易理解）。所以内核中这种链表也可以称为侵入式链表。另外，这种链表可以嵌入到任何的数据结构中形成链表，其通用性非常强，应用非常灵活。对于这种链表，其具体的操作时间复杂度为O(1)，相对来说要稳定，同时，这种链表不再参与数据本身的内存分配和回收，在设计上将数据结构与数据进行了解耦。最后，这种数据链表内存中的数据存储连续，对缓存友好，访问速度快。这也是内核中使用这种链表的一个重要原因。

三、应用分析

理解内核中这种双向循环链表，需要明白几个主要的宏：

//自己指向自己，前向和后向都如此，形成一个空的循环链表#defineLIST_HEAD_INIT(name){&(name),&(name)}#defineLIST_HEAD(name)\structlist_headname=LIST_HEAD_INIT(name)/** * INIT_LIST_HEAD - Initialize a list_head structure * @list: list_head structure to be initialized. * * Initializes the list_head to point to itself. If it is a list header, * the result is an empty list. */staticinlinevoidINIT_LIST_HEAD(structlist_head*list){WRITE_ONCE(list->next,list);WRITE_ONCE(list->prev,list);}//写入数据#define__WRITE_ONCE(x,val)\do{\*(volatiletypeof(x)*)&(x)=(val);\}while(0)#defineWRITE_ONCE(x,val)\do{\compiletime_assert_rwonce_type(x);\__WRITE_ONCE(x,val);\}while(0)#ifdefined(__x86_64__)#definesmp_store_release(p,v)\do{\barrier();\WRITE_ONCE(*p,v);\}while(0)//遍历，内核中还有数个相类似的实现/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */#definelist_for_each(pos,head)\for(pos=(head)->next;!list_is_head(pos,(head));pos=pos->next)/** * list_for_each_reverse - iterate backwards over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */#definelist_for_each_reverse(pos,head)\for(pos=(head)->prev;pos!=(head);pos=pos->prev)

这也算内核的特点，底层大量使用了宏来处理一些基础的数据结构和相关的算法定义。只要掌握了这些底层的宏处理，那么在阅读相关的数据结构和算法处理时，就基本没有什么问题了。
实际的应用上，这种链表与普通链表的整体用法没有本质不同，但在一些细节上却有自己的特点，主要有：

使用container_of宏来处理数据结构与链表节点指针关系
看下内核中的源码：

//typeof:用于类型检查，确保传入的指针为成员类型指针#definetypeof_member(T,m)typeof(((T*)0)->m)/** * 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. */#definecontainer_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)));})/** * container_of_const - cast a member of a structure out to the containing * structure and preserve the const-ness of the pointer * @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. */#definecontainer_of_const(ptr,type,member)\_Generic(ptr,\consttypeof(*(ptr))*:((consttype*)container_of(ptr,type,member)),\default:((type*)container_of(ptr,type,member))\)//__builtin_offsetof GCC中内置的一个函数，用来计算struct中特定成员相对于起始地址的字节偏移量#undefoffsetof#defineoffsetof(TYPE,MEMBER)__builtin_offsetof(TYPE,MEMBER)

container_of首先将链表的指针类型转化为void的__mptr,然后用offsetof来获取成员到对象起始地址的偏移量（所以是((T)0),而((T*)0)->m就是与0的偏移量，不用再作减法），此时再用__mptr减去偏移量的绝对值，则可以得到包含指针成员变量的对象的地址。
2. 支持相同数据在多个链表的处理
这是一种比较特殊的应用，就是说一个数据对象可以在多个链表中进行访问处理，如下面的代码：

//arch/x86/kvm/svm/svm.hstructkvm_sev_info{bool active;/* SEV enabled guest */bool es_active;/* SEV-ES enabled guest */unsignedintasid;/* ASID used for this guest */unsignedinthandle;/* SEV firmware handle */intfd;/* SEV device fd */unsignedlongpages_locked;/* Number of pages locked */structlist_headregions_list;/* List of registered regions */u64 ap_jump_table;/* SEV-ES AP Jump Table address */structkvm*enc_context_owner;/* Owner of copied encryption context */structlist_headmirror_vms;/* List of VMs mirroring */structlist_headmirror_entry;/* Use as a list entry of mirrors */structmisc_cg*misc_cg;/* For misc cgroup accounting */atomic_tmigration_in_progress;};//arch/x86/kvm/svm/svm.cstaticintsev_guest_init(structkvm*kvm,structkvm_sev_cmd*argp){structkvm_sev_info*sev=&to_kvm_svm(kvm)->sev_info;......INIT_LIST_HEAD(&sev->regions_list);INIT_LIST_HEAD(&sev->mirror_vms);......returnret;}

广泛使用宏来进行链表的操作
这个除了前面的一些初始化等操作，最典型的就是遍历：

//以下为几个遍历的方法，还有很多，可参看相关文件#definelist_for_each(pos,head)\for(pos=(head)->next;!list_is_head(pos,(head));pos=pos->next)#definelist_for_each_reverse(pos,head)\for(pos=(head)->prev;pos!=(head);pos=pos->prev)#definelist_for_each_rcu(pos,head)\for(pos=rcu_dereference((head)->next);\!list_is_head(pos,(head));\pos=rcu_dereference(pos->next))#definelist_for_each_continue(pos,head)\for(pos=pos->next;!list_is_head(pos,(head));pos=pos->next)#definelist_for_each_safe(pos,n,head)\for(pos=(head)->next,n=pos->next;\!list_is_head(pos,(head));\pos=n,n=pos->next)#definelist_for_each_prev_safe(pos,n,head)\for(pos=(head)->prev,n=pos->prev;\!list_is_head(pos,(head));\pos=n,n=pos->prev)

通用的链表相关接口
这此只简单的说明一下，在“include/linux/list.h”中有插入（头插、尾插和中间插入）、删除、交换、切片、替代等等。

这种链表当然也有其不足之处，主要有：

需要修改数据结构引入链表相关的数据定义
实现较为复杂（包括container_of等一系列宏的使用）
维护调试相对复杂

四、应用场景

一般来说，这种链表会应用于以下几种场景：

内核相关的系统编程
多链表数据结构的应用
内存操作对大小及性能操作要求较高的场合
其它一些特定的应用

一般来说，这种侵入式链表应该不算主流应用的方式，但在某些方面很有应用价值。

五、内核中的例子

具体的用法如下：

//drivers/base/core.c//设备固件节点（两个fwnode_handle）的依赖关系创建即consumer（消费者）supplier（供应者）staticint__fwnode_link_add(structfwnode_handle*con,structfwnode_handle*sup,u8 flags){structfwnode_link*link;list_for_each_entry(link,&sup->consumers,s_hook)if(link->consumer==con){link->flags|=flags;return0;}link=kzalloc(sizeof(*link),GFP_KERNEL);if(!link)return-ENOMEM;link->supplier=sup;INIT_LIST_HEAD(&link->s_hook);link->consumer=con;INIT_LIST_HEAD(&link->c_hook);link->flags=flags;list_add(&link->s_hook,&sup->consumers);list_add(&link->c_hook,&con->suppliers);pr_debug("%pfwf Linked as a fwnode consumer to %pfwf\n",con,sup);return0;}