Linux内核链表分析

摘 要：Linux内核代码博大精深，《深入理解linux内核》译者曾在译者序中把它形容为“覆压三百余里，隔离天日”、“廊腰缦回，檐牙高啄；各抱地势，钩心斗角。” [ 1 ]，可见其内容之丰富、结构之庞杂。Linux内核经过这么多年的发展，而这个内核双向链表却依旧存在，足以体现出内核链表运行的稳定性，就连Linux社区的黑客们也都为这个链表的设计感到自豪。

关键词：内核；Linux；数据结构；内核链表；List

中图分类号：G642 文献标识码：B/A

Linux内核中通常使用的是双向循环链表，本文链表摘自Linux内核版本为4.8.9的List[include/linux/list.h]。

内核链表设计思想。如图1，内核链表结点只有前驱和后继指针没有数据域，这样设计是为链表提供了一致的访问接口。和传统链表相比，内核链表不是在链表结构中包含数据，而是在数据结构中包含链表节点。

从图1中我们可以看到Linux内核链表的结点和部分接口声明。链表数据结构的定义很简单，那Linux内核链表是怎么存储数据的呢？

我们可以通过图2看到，内核链表使用方式是在数据结構中包含链表结点，每个数据结构又通过双向循环链表进行关联着。一个头结点head牵引着多个记录结点entry，每个entry结点又被数据结构node包含着，既能为链表提供了一致的访问接口，又能将数据进行双向循环关联，可见内核链表设计之精妙。

内核链表使用的时候每个entry在node结构体中的声明位置是不固定的，在entry声明位置未知的情况下，我们要如何对每个数据结点node进行遍历的呢？其实我们可以使用著名的宏（offsetof、container_of）计算出结构体成员变量的地址，然后进行遍历。

为什么Linux内核设计者要花这么大的力气，设计成这样的链表，还要通过这么高深的宏定义来解决一个遍历问题？其实花这么大力气是值得的，目的为了节省内存，内核设计者非常珍惜内存的使用。在结构体中有个内存对齐的概念，也是一个用空间换时间的作用，加快cpu的访问速度。这样一来一个结构体占用多少的内存不仅仅是结构体成员变量所占内存的总和，成员变量的定义位置也会对结构体占用的内存产生影响。

那如何抛弃上面的两个宏，还能实现链表的遍历呢？其实我们可以把entry的定义放在结构体内的第一个位置或者最后一个位置，放在最后一个位置需要再计算下node结构体的大小。

国内的企业一般也就是把entry放在第一个位置，可以实现不使用offsetof、container_of宏就能达到链表遍历的目的，这样list_head的地址也就是node的地址，然后通过将list_head的地址强制转换为node的地址，即可实现遍历。

参考文献：

[1] Daniel P. Bovet & Marco Cesati. 深入理解LINUX内核[J].中国电力出版社，2015.

[2] W. Richard Stevens & Stephen A. Rago. UNIX环境高级编程[J].人民邮电出版社，2016.

[3] W.Richard Stevens. UNIX网络编程，卷2 [J].人民邮电出版社，2016.

通讯作者：华中伟