Linux内核链表

大多数人在学习数据结构的时候，链表都是第一个接触的内容，笔者也不列外，虽然自己实现过几种链表，但是在实际工作中，还是Linux内核的链表最为常用（同时笔者也建议大家使用内核链表，因为会了这个，其他的都会了），故总结一篇Linux内核链表的文章。

阅读本文之前，我假设你已经具备基本的链表编写经验。

 内核链表的结构是个双向循环链表，只有指针域，数据域根据使用链表的人的具体需求而定。内核链表设计哲学：

既然链表不能包含万事万物，那么就让万事万物来包含链表。

假设以如下方式组织我们的数据结构：

 创建一个结构体，并将链表放在结构体第一个成员地址处（后面会分析不在首地址时的情况）。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #include "list.h"
 5 
 6 struct person 
 7 {
 8     struct list_head list;
 9     int age;
10 };
11 
12 int main(int argc,char **argv)
13 {
14     int i;
15     struct person *p;
16     struct person person1;
17     struct list_head *pos;
18     
19     INIT_LIST_HEAD(&person1.list);
20 
21     for (i = 0;i < 5;i++) {
22         p = (struct person *)malloc(sizeof(struct person ));
23         p->age=i*10;
24         list_add(&p->list,&person1.list);
25     }
26 
27     list_for_each(pos, &person1.list) {
28         printf("age = %d\n",((struct person *)pos)->age);
29     }
30     
31     return 0;
32 }

我们先定义struct person person1;此时person1就是一个我们需要使用链表来链接的节点，使用链表之前，需要先对链表进行初始化，LIST_HEAD和INIT_LIST_HEAD都可以初始化一个链表，两者的区别是，前者只需要传入链表的名字，就可以初始化完毕了；而后者需要先定义出链表的实体，如前面的person1一样，然后将person1的地址传递给初始化函数即可完成链表的初始化。内核链表的初始化是非常简洁的，让前驱和后继都指向自己。

完成了初始化之后，我们可以像链表中增加节点，先以头插法为例：

 list_add函数，可以在链中增加节点，改函数为头插法，即每次插入的节点都位于上一个节点之前，比如上一个节点是head->1->head，本次使用头插法插入之后，链表结构变成了 head->2->1->head。也就是使用list_add头插法，最后第一个插入的节点，将是链表结构中的第一个节点。

 list_add函数的实现步骤也非常简洁，一定要自己去推演一下这个过程，O（1）的时间复杂度，就4条指针操作，不自己去推演一下这个过程你会少很多心得体会，尤其是在接触过其他的还要考虑头部和尾部特殊情况的链表之后，更会觉得内核链表设计简洁的妙处。list_add函数的第一个参数就是要增加到头结点链表中的数据结构，第二个参数就是头结点，本例中为&person1.list。

本例中增加5个节点，头结点的数据域不重要，可以根据需要利用头结点的数据域，一般而言，头结点数据域不使用，在使用头结点数据域的情况下，一般也仅仅记录链表的长度信息，这个在后面我们可以自己实现一下。

在增加了5个节点之后，我们需要遍历链表，访问其数据域的内容，此时，我们先使用list_for_each函数，遍历链表。

 该函数就是遍历链表，直到出现pos == head时，循环链表就编译完毕了。对于其中的prefetch(pos->next)函数，如果你是在GNU中使用gcc进行程序开发，可以不做更改，直接使用上面的函数即可；但如果你想把其移植到Windows环境中进行使用，可以直接将prefetch(pos->next)该条语句删除即可，因为prefetch函数它通过对数据手工预取的方法，减少了读取延迟，从而提高了性能，也就是prefetch是gcc用来提高效率的函数，如果要移植到非GNU环境，可以换成相应环境的预取函数或者直接删除也可，它并不影响链表的功能。

list_for_each的第一个参数pos，代表位置，需要是struct list_head * 类型，它其实相当于临时变量，在本例中，定义了一个指针pos， struct list_head *pos;用其来遍历链表。

可以遍历链表之后，那么就需要对数据进行打印了。

 本例中的输出，将pos强制换成struct person *类型，然后访问age元素，得到程序输出入下：

 可以发现，list_add头插法，果然是最后插入的先打印，最先插入的最后打印。

其次，为什么笔者要使用printf("age = %d\n",((struct person *)pos)->age);这样的强制类型转换来打印呢？能这样打印的原理是什么呢？

现在回到我们的数据结构：

struct person 
{
  struct list_head list;
  int age;
};

由于我们将链表放在结构体的首地址处，那么此时链表list的地址，和struct person 的地址是一致的，所以通过pos的地址，将其强制转换成struct person *就可以访问age元素了。

前面说到，内核链表是太头结点的，一般而言头结点的数据域我们不使用，但也有使用头结点数据域记录链表长度的实现方法。头结点其实不是必须的，但作为学习，我们可以实现一下，了解其过程：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #include "list.h"
 5 
 6 struct person_head
 7 {
 8     struct list_head list;
 9     int len;
10 };
11 
12 struct person 
13 {
14     struct list_head list;
15     int age;
16 };
17 
18 int main(int argc,char **argv)
19 {
20     int i;
21     struct person *p;
22     struct person_head head;
23     struct list_head *pos;
24     
25     INIT_LIST_HEAD(&head.list);
26     head.len=0;
27 
28     for (i = 0;i < 5;i++) {
29         p = (struct person *)malloc(sizeof(struct person ));
30         p->age=i*10;
31         list_add(&p->list,&head.list);
32     }
33 
34     list_for_each(pos, &head.list) {
35         printf("age = %d\n",((struct person *)pos)->age);
36         head.len++;
37     }
38     printf("list len =%d\n",head.len);
39     
40     return 0;
41 }

View Code

 本例中定义了person_head结构，其数据域保存链表的长度，由于list_for_each会遍历链表，本例仅作为功能说明的实现，记录了链表的长度信息，并打印了链表长度。如果实际开发中需要记录链表的长度或者其他信息，应该封装成相应的函数，同时，增加节点的时候，增加len的计数，删除节点的时候，减少len的计数。

在笔者最早接触到将链表放在结构体第一个成员地址处时，觉得Linux内核链表后面的container_of，offsetof宏为什么如此多余，因为按照上面的方法，根本不再需要container_of，offsetof这样的宏了，甚至当时还觉得内核为什么这么笨，还不更新代码（当然，这也是当时听了某个老师的课说现代的链表已经发展成为上面例子的情况，而内核链表处于不断发展的过程，并没有使用这样最新的方式）。所以笔者在学生时代时学到这里就收手没有再继续下去了，因为我当时认为按照这样的方法就够用了。可是，当我进入到企业工作之后，我发现并不是这样的，因为没有人可以保证链表可以放在结构体的第一个成员地址处，哪怕能够保证，那么在复杂数据结构中，有多个链表怎么办？哪怕你能够保证有一个链表位于结构体的首地址处，那其他的链表怎么办呢？直到那时，我才发现Linux内核那帮设计者们并不笨，而是自己当时的知识面太窄并且项目经验不足（这样同样证明了一个授课老师的知识水平，对学生的影响是很大的，当然，瑕不掩瑜，我内心还是非常感谢当初那位老师的，只是，我需要更强大的力量了^_^）。内核链表设计者们，考虑到了很多情况下，我们根本不能保证每个链表都处于结构体的首地址，所以，也就出现了container_of，offsetof这两个广为人知的宏。

试想，如果将我上面代码中的person结构体位置更改一下：

 将链表不放置在结构体的首地址处，那么前面的代码将不能正常工作了：

因为此时强制类型转换得到地址不再是struct person结构的首地址，进行->age操作时，指针偏移不正确。

 果然，运行之后代码得到的age值不正确，为了解决这一问题，内核链表的开发者们设计出了两个宏：

 我们先来分析offsetof宏，其语法也是非常简洁和简单的，该宏得到的是TYPE（结构体）类型中成员MEMBER相对于结构体的偏移地址。但是，其中有一个知识点需要注意：为什么（(TYPE *)0)->MEMBER这样的代码不会出现段错误，我们都知道，p->next,等价于（*p）.next;那么（(TYPE *)0)->MEMBER，不是应该等价于（*(TYPE *)0).MEMBER吗？这样不就出现了对0地址的解引用操作吗？为什么内核使用这样的代码却没有问题呢？

为了解释这个问题，我们先做一个测试：

 没有问题，现在我们把for_test的参数改为NULL，看看会不会出现段错误：

 注意，此时传递给for_test的参数为NULL，同时为了显示偏移数，我将地址以%u打印，程序输出如下：

 你发现了什么？对，程序并没有奔溃，而且得到了age和list在struct person中偏移量，一个为0，一个为8（笔者的Linux是64bit的）。为什么传递NULL空指针进去，并没有发生错误，难道是我们之前学习的C语言有问题？

没有发生错误，是因为在ABI规范中，编译器处理结构体地址偏移时，使用的是如下方式：

 在编译阶段，编译器就会将结构体的地址以如上方式组织，也就是说，编译器去取得结构体某个成员的地址，就是使用的偏移量，所以，即使传入NULL，也不会出现错误，也就是说，内核的offsetof宏不会有任何问题。

 那么offsetof之所以将0强制类型转换，就是为了得到TYPE结构体中MEMBER的偏移量，最后将偏移量强制类型转换为size_t，这就是offsetof。那么为什么要这样求偏移呢？前面说到了，想在结构体中得到链表的地址，怎么得到地址呢?如果我们知道了链表和结构体的偏移量，那么即使链表不位于结构体首地址处，我们也可以使用链表了啊。

下面，我们对container_of宏做解析：

 其中typeof是GNU中获取变量类型的关键字，如果要将其移植到Windows中，可以再添加一个参数解决，后面会有实验。

现在我们来看，第一句，其实第一句话没有也完全不影响该宏的功能，但是内核链表设计者们为什么要增加这个一个赋值的步骤呢？这是因为宏没有参数检查的功能，增加这个const typeof( ((type *)0)->member ) *__mptr = (ptr)赋值语句之后，如果类型不匹配，会有警告，所以说，内核设计者们不会把没用的东西放在上面。

现在我们来说一下该宏的三个参数，ptr，是指向member的指针，type，是容器结构体的类型，member就是结构体中的成员。用__mptr强制转换成char *类型 减去member在type中的偏移量，得到结果就是container_of宏的作用结果。我们先不考虑container_of宏到底是什么作用，先来看看我们怎么使用它。

Linux内核链表

原文：https://www.cnblogs.com/yangguang-it/p/11667772.html