如何图文玩转内核链表list，从这五个点入手！
在Linux内核中，提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的，但是list_head的引入，使得内核数据结构也可以拥有面向对象的特性，通过使用操作list_head 的通用接口很容易实现代码的重用，有点类似于C++的继承机制（希望有机会写篇文章研究一下C语言的面向对象机制）。
首先找到list_head结构体定义，kernel/inclue/linux/types.h 如下：
需要注意的一点是，头结点head是不使用的，这点需要注意。
使用list_head组织的链表的结构如下图所示：
然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中：
一. 创建链表
内核提供了下面的这些接口来初始化链表：
如： 可以通过 LIST_HEAD（mylist） 进行初始化一个链表，mylist的prev 和 next 指针都是指向自己
但是如果只是利用mylist这样的结构体实现链表就没有什么实际意义了，因为正常的链表都是为了遍历结构体中的其它有意义的字段而创建的，而我们mylist中只有 prev和next指针，却没有实际有意义的字段数据，所以毫无意义。
综上，我们可以创建一个宿主结构，然后在此结构中再嵌套mylist字段，宿主结构又有其它的字段（进程描述符 task_struct，页面管理的page结构，等就是采用这种方法创建链表的）。为简便理解，定义如下：
创建链表，并初始化
这样我们的链表就初始化完毕，链表头的myhead就prev 和 next指针分别指向myhead自己了，如下图：
【文章福利】小编推荐自己的Linux内核技术交流群:【891587639】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100名进群领取，额外赠送一份价值699的内核资料包（含视频教程、电子书、实战项目及代码)
二. 添加节点
内核已经提供了添加节点的接口了
1. list_add
如下所示。根据注释可知，是在链表头head后方插入一个新节点new。
list_add再调用__list_add接口
其实就是在myhead链表头后和链表头后第一个节点之间插入一个新节点。然后这个新的节点就变成了链表头后的第一个节点了。
接着上面步骤创建1个节点然后插入到myhead之后
然后在创建第二个节点，同样把它插入到header_task之后
list_add
以此类推，每次插入一个新节点，都是紧靠着header节点，而之前插入的节点依次排序靠后，那最后一个节点则是第一次插入header后的那个节点。最终可得出：先来的节点靠后，而后来的节点靠前，"先进后出，后进先出"。所以此种结构类似于 stack"堆栈"， 而header_task就类似于内核stack中的栈顶指针esp，它都是紧靠着最后push到栈的元素。
2. list_add_tail 接口
上面所讲的list_add接口是从链表头头后添加的节点。同样，内核也提供了从链表尾处向前添加节点的接口list_add_tail.让我们来看一下它的具体实现。
从注释可得出：
在一个特定的链表头前面插入一个节点
这个方法很适用于队列的实现（why？）
进一步把__list_add（）展开如下：
所以，很清楚明了， list_add_tail就相当于在链表头前方依次插入新的节点（也可理解为在链表尾部开始插入节点，此时，header节点既是为节点，保持不变）
利用上面分析list_add接口的方法可画出数据结构图形如下。
（1）创建一个链表头（实际上应该是表尾）代码参考第一节;
（2）插入第一个节点 node1.list ， 调用
（3） 插入第二个节点node2.list，调用
依此类推，每次插入的新节点都是紧挨着 header_task表尾，而插入的第一个节点my_first_task排在了第一位，my_second_task排在了第二位，可得出：先插入的节点排在前面，后插入的节点排在后面，"先进先出，后进后出"，这不正是队列的特点吗（First in First out）！
三. 删除节点
内核同样在list.h文件中提供了删除节点的接口 list_del（）， 让我们看一下它的实现流程
利用list_del（struct list_head *entry） 接口就可以删除链表中的任意节点了，但需注意，前提条件是这个节点是已知的，既在链表中真实存在，切prev，next指针都不为NULL。
四. 链表遍历
内核是同过下面这个宏定义来完成对list_head链表进行遍历的，如下 ：
上面这种方式是从前向后遍历的，同样也可以使用下面的宏反向遍历：
而且，list.h 中也提供了list_replace（节点替换） list_move（节点移位） ，翻转，查找等接口，这里就不在一一分析了。
五. 宿主结构
1.找出宿主结构 list_entry（ptr， type， member）
上面的所有操作都是基于list_head这个链表进行的，涉及的结构体也都是：
其实，正如文章一开始所说，我们真正更关心的是包含list_head这个结构体字段的宿主结构体，因为只有定位到了宿主结构体的起始地址，我们才能对对宿主结构体中的其它有意义的字段进行操作。
那我们如何根据list这个字段的地址而找到宿主结构node1的位置呢？list.h中定义如下：
list.h中提供了list_entry宏来实现对应地址的转换，但最终还是调用了container_of宏，所以container_of宏的伟大之处不言而喻。
2 container_of
做linux驱动开发的同学是不是想到了LDD3这本书中经常使用的一个非常经典的宏定义！
在LDD3这本书中的第三章字符设备驱动，以及第十四章驱动设备模型中多次提到，我觉得这个宏应该是内核最经典的宏之一。那接下来让我们揭开她的面纱：
此宏在内核代码 kernel/include/linux/kernel.h中定义（此处kernel版本为3.10;新版本4.13之后此宏定义改变，但实现思想保持一致）
而offsetof定义在 kernel/include/linux/stddef.h ，如下：
举个例子，来简单分析一下container_of内部实现机制。
例如:
展开container_of宏，探究内部的实现：
获取成员变量b的类型 ，这里获取的就是short 类型。这是GNU_C的扩展语法。
用获取的变量类型，定义了一个指针变量 __mptr ，并且将成员变量 b的首地址赋值给它
这里的offsetof（struct test，b）是用来计算成员b在这个struct test 结构体的偏移。__mptr
是成员b的首地址, 现在 减去成员b在结构体里面的偏移值，算出来的是不是这个结构体的首地址呀 。
3. 宿主结构的遍历
我们可以根据结构体中成员变量的地址找到宿主结构的地址，并且我们可以对成员变量所建立的链表进行遍历，那我们是不是也可以通过某种方法对宿主结构进行遍历呢？
答案肯定是可以的，内核在list.h中提供了下面的宏：
其中，list_first_entry 和 list_next_entry宏都定义在list.h中，分别代表：获取第一个真正的宿主结构的地址;获取下一个宿主结构的地址。它们的实现都是利用list_entry宏。
最终实现了宿主结构的遍历
首先pos定位到第一个宿主结构地址，然后循环获取下一个宿主结构地址，如果查到宿主结构中的member成员变量（宿主结构中struct list_head定义的字段）地址为head，则退出，从而实现了宿主结构的遍历。如果要循环对宿主结构中的其它成员变量进行操作，这个遍历操作就显得特别有意义了。
我们用上面的 nod结构举个例子：
