第2章 数据结构的使用

内核中有很多数据结构本身并没有实际意义，它们扮演的是辅助角色，为实现某些特殊目的“穿针引线”，比如下面介绍的几种，可以辅助实现数据结构之间关系。也有某些数据结构，特别适用于某些特定场景，实现某些特定功能，比如位图。

2.1 关系型数据结构

程序=数据结构+算法，数据结构指的是数据与数据之间的逻辑关系，算法指的是解决特定问题的步骤和方法。逻辑关系本身就是现实的反映与抽象，理解逻辑关系是理解程序的关键，本节将讲述实现一对一、一对多和多对多关系的常用数据结构和方法。

2.1.1 一对一关系

一对一的关系随处可见，结构体与其成员、很多结构体与结构体之间都是这种关系。结构体与成员的一对一关系简单明了，两个结构体之间的一对一关系有指针和内嵌（包含）两种表达方式，代码如下。

第二种方式的主要优点是对一对一关系体现得比较清晰，同时也方便管理，因为通过container_of宏（内核定义好的）可以由b计算出a的位置，而不再需要多一个指向a的指针。

然而第二种方式并不一定是最好的，要视逻辑而定。比如男人和妻子，通常是一对一，如果采用内嵌的方式首先造成的是逻辑混乱，男人结构体中多了一些不属于男人的成员（即妻子）；其次，并不是每个男人都有妻子，有些是单身，用指针表示就是NULL，内嵌无疑浪费了空间。所以，要满足逻辑合理、有a就有b这两个条件，采用这种方式才是比较恰当的。

安全性是程序的首要要求，而合理的逻辑是安全性重要的前提，违背逻辑的程序即使当前“安全”，在程序不断维护和更新的过程中，随着开发人员的变动，隐患迟早会爆发。

2.1.2 一对多关系

一对多关系在内核中一般由链表或树实现，由于数组的大小是固定的，除非在特殊情况下，才会采用数组。用链表实现有多种常用方式，包括list_head、hlist_head/hlist_node、rb_root/rb_node（红黑树）等数据结构。下面以branch（树枝）和leaf（树叶）为例进行分析。

最简单的方式是单向链表，该方式直接明了，只需要leaf结构体内包含一个leaf类型的指针字段即可，代码如下。中断部分的irq_desc和irqaction结构体使用的就是这种方式。

branch包含指向链接头的指针，leaf对象通过next串联起来，如图2-1所示。

由图2-1可见该方式的局限在于不能通过一个leaf访问前一个leaf对象，当然也不能方便地在某个元素前面插入新结点或删除当前结点，正因为缺乏灵活性，它一般用在只需要通过branch访问leaf的情况下。一般情况下，链表中所有的点都被称为结点，其中链表头被称为头结点。为了更好地区分头结点和其他结点，在本书中分别称之为链表头和链表的（普通）元素。

在需要方便地进行遍历、插入和删除等操作的情况下，上面的方式过于笨拙，可以使用双向链表。内核中已经提供了list_head、hlist_head等数据结构来满足该需求。branch的head字段是该链表的头，每一个相关的leaf都通过node字段链接起来，list_head的使用如下。

利用这个双向链表和container_of等宏，就可以方便地满足遍历、插入和删除等操作，list_head定义如下。

组成的结构如图2-2所示。

从上图可见，真正串联起来的是list_head，而不是branch或者leaf。不过有了list_head，通过container_of宏就可以得到branch和leaf了。内核提供了很多list_head相关的函数和宏，其中一部分如表2-1所示。

list_head链表的头与链表的元素是相同的结构，所以无论传递给各操作的参数是链表头还是元素编译器都不会报错。但它们代表的意义不同，有些操作对参数是有要求的，比如list_delete不能以链表头为参数，否则branch的list相关字段被置为LIST_POISON1/LIST_POISON2，整个链表将不复存在。

另外，需要特别注意的是，也正是由于list_delete删除元素后会重置它的prev、next字段，所以不带safe后缀的操作（如list_for_each_entry），获得元素后不能进行删除当前元素的操作，否则无法完成遍历操作。有safe后缀的操作会使用n临时复制当前元素的链表关系，使用n继续遍历，所以不存在该问题。

list_head有一个兄弟，即hlist_head/hlist_node。顾名思义，hlist_head表示链表头，hlist_node表示链表元素，它们的定义如下。

hlist_head的first字段的值是链表第一个node的地址，hlist_node的next字段是指向下一个node的指针，pprev字段的值等于前一个node的next字段的地址。如果分别以curr、prev和next表示当前、前一个和下一个node的地址，那么curr->next==next，curr->pprev==&prev->next都成立。

与list_head相比，hlist的链表头与链表元素的数据结构是不同的，而且hlist_head占用内存与list_head相比小了一半。存在多个同质的双向链表的情况下，链表头占的空间就值得考虑节省了。内核中很多地方使用了它，这些链表头存于数组、哈希表、树结构中，节省的空间是比较可观的。

另外，hlist_head不能直接访问链表的最后一个元素，必须遍历每一个元素才能达到目的，而list_head链表头的prev字段就指向链表最后一个元素。因此，hlist_head并不适用于FIFO（First In First Out）的需求中。

内核也提供了hlist_head的相关操作，大多与list_head的操作相似，如表2-2所示。

与list_head相同，不带safe后缀的操作（如hlist_for_each_entry）获得元素后，不能进行删除当前元素的操作，否则无法完成遍历操作。

红黑树、基数（radix）树等结构也会用在一对多的关系中，它们涉及比较有趣的算法，在对查询与增删改等性能要求较高的地方使用较多，相关知识可参考算法方面的书籍，内核中提供的函数可参考rbtree.h和radix-tree.h等文件。

2.1.3 多对多关系

多对多关系相对复杂，它并不能像一对多关系那样可以简单地通过将list_head等的结点包含到结构体中来实现。在教与学范畴内，教师和学生关系属于多对多关系，下面就以teacher和student结构体为例分析（链表以list_head为例）。

一个教师可以有多个学生，从数据结构的角度看，teacher包含list_head链表头，每个student对象都可以通过list_head结点访问到，list_head结点链接到teacher包含的头上，如图2-3所示。

本质上，一对关系就需要一个结点，比如学生A（S_A）是教师A（T_A）的学生，需要一个结点链接到T_A包含的链表头；同时，学生A也是教师B的学生，也需要一个结点链接到T_B包含的链表头。针对该情况，一个学生可以属于多个链表，所以简单地将list_head的结点包含到student结构体中是无法实现多对多关系的（因为指针指向的唯一性，list_head属于且仅属于一个链表）。

可行的做法是将list_head独立于student结构体，并配合一个指向student对象的指针来定位结点所关联的student对象，如下。

该方案的结构如图2-4所示。

这样从student对象的角度，会有多个指针指向它，也有多个结点与它关联，如此它就可以与多个链表产生关系了。

同样，一个学生可以有多个教师，也会遇到一个teacher对象会出现在多个student的链表中的问题，那就需要定义一个t_connection结构体，如下。

由于这种关系是相互的，如果S_A是T_A的学生，那么T_A必然是S_A的老师；如果S_A不是T_A的学生，那么T_A必然也不是S_A的老师。反之亦然。所以可以将s_connection和t_connection合并起来，具体代码如下。

到此，教师和学生的多对多关系就可以完整地用程序实现了，具体代码如下。

connection结构体的s_node字段链接到teacher结构体head_for_student_list字段表示的链表头，t_node字段链接到student结构体head_for_teacher_list字段表示的链表头，这个错落有致的关系网就完毕了。

老师T_A有S_A和S_B两个学生的关系，老师T_B有S_A一个学生的关系，如图2-5所示。

input子系统的三个关键结构体input_dev、input_handler、input_handle就是如此实现的，input_dev和input_handler是多对多的关系，input_handle就相当于这里的connection。

并不是每个多对多的关系中两个connection结构体都可以合并的，有些关系并不是相互的，比如男生和女生的暗恋关系。A男暗恋B女，B女却不一定暗恋A男；A男的链表关联B女，B女的链表不一定关联A男。两个connection结构体合并在一起明显浪费空间，如果强行利用多余的空间，岂不逻辑混乱。

2.2 位操作数据结构

位图（bitmap），以每一位（bit）来存放或表示某种状态，这样一个字节（byte）就可以表示8个元素的状态，可以极大地节省内存。一个bit只有0和1两个值，所以它也只适用于每个元素都是“非黑即白”的场景，比如打开和关闭、被占用和空闲等。

位图的本质是一段物理连续的存储空间，其中每一位表示一个元素的状态。比如申请新的文件描述符fd时，某一个bit为1，表示该bit对应的fd已被占用；为0，则表示fd可用。该bit相对于起始位置的偏移量就是fd的值。我们不妨假设表示fd的这段连续内存内容从低位到高位是 (11111111，11111111，10…)，第17位可用，那么得到的fd可能就是17。

实际上多数程序员对位图并不陌生，人们可能经常使用一个整数来表示某些状态，比如很多函数的flags等类似的参数，会在自己的函数中操作这个整数的位来更改它的状态，或者根据它的状态来决定函数的行为。这其实也可以算作位图的一种，只不过一个整数一般最多表示32或者64个元素，位图可以表示的元素可以更多。除此之外，它们在逻辑上可能也有些许差别，位图表示的元素一般都是同质化的，而操作整数的情况可能逻辑上要复杂些。

内核提供了几个宏和函数，可以用来进行位操作，如表2-3所示。

find_first_zero_bit和find_first_bit的第二个参数size是以位（bit）为单位的，find_next_zero_bit和find_next_bit从第offset位（包含offset）开始查找为0和为1的位置，找不到则返回size。

有了以上的宏和函数，可以很方便地找到位图中的某位，比如要获取文件描述符的函数alloc_fd，它最终调用find_next_zero_bit来查找位图中下一个值为0的位，该位的偏移量就是可用的文件描述符。

2.3 模块和内核参数传递

内核的数据结构因为需要供多个模块使用，所以要考虑通用性，而很多模块往往要考虑自身的特性，需要满足自身需求的独特数据结构。模块传递给内核通用参数，从内核获取的也是通用参数，那么它如何通过通用参数来获得属于它的特殊数据呢？在模块内定义全局变量是一个方法，它也不依赖内核的通用参数，除非逻辑需要，全局变量一般并不是首选，下面我们将介绍两种优选方案。

2.3.1 内嵌通用数据结构

inode是一个典型的例子，内核使用inode对象，很多文件系统内部除了inode还需要其他特有信息，定义一个内嵌inode的特殊结构体就可以解决该问题，代码如下。

传递参数给内核的时候，传递my_inode的inode的地址ptr；从内核获得的inode地址，通过container_of(ptr, my_inode, inode)宏就可以获得my_inode对象。

2.3.2 通用结构的私有变量

内核中很多数据结构都定义了类型为void*的私有数据字段，模块可以将它特有的数据赋值给该字段，通过引用该字段就可以获取它的数据。file结构体的private_data、device结构体的driver_data都是这种用法。

内嵌和私有变量方式该如何选择呢？内嵌和对象由模块负责创建；私有变量，为私有数据的字段赋值的时候，对象已经存在了。前者，对象归模块所有；后者，对象一般归内核所有。当然，有些情况下，模块也可以将两种方法一起使用，比如inode除了可以被内嵌外，它本身就有一个i_private字段。

2.4 实例分析

数据结构是基础中的基础，内核中的结构体数不胜数，读者可以从它们的使用范围（模块内部还是内核通用）和数据结构间的关系掌握它们。

2.4.1 模块的封装

内核中经常提起模块，在实现某一特定功能的时候，最好的做法是将它与其他部分独立开，形成一个单独的模块，有利于在未来以最小的改动扩展功能。这并不是说模块是封闭的，它一方面需要调用其他模块的函数，另一方面也需要提供函数供其他模块访问。

在面向对象的编程中，这叫作封装，C语言并没有该概念，但封装的思想是一样的，我们在模块中要尽可能少地透漏实现细节，仅提供必要的函数供外部使用。这样在内部实现变化的时候，对其他模块影响更小，或者说在改变内部实现的时候，需要考虑的因素更少。

同样，在使用其他模块的时候，不要违背其他模块的访问控制意图，虽然在我们试图这么做的时候编译器不会报错。

以inode结构体为例，它主要适用VFS和具体文件系统的实现两种场景。其他模块，比如一个设备驱动一般是不会直接访问它的，而是访问file结构体。从代码角度，通过file->f_inode就可以得到inode，是可行的，甚至在知道具体的文件系统时，可以通过inode获得内嵌它的那个文件系统内定义的xxx_inode。虽然这么做是错误的，但是方法起码是值得斟酌的。

xxx_inode从文件系统的角度不需要为我们的模块负责，但强行“绑定”可能会导致更改xxx_inode变得困难。

所以开发一个新模块，不仅要理清它自身的逻辑，还要理解已有模块数据结构的意图，不要逾越对它们的访问控制。

2.4.2 火眼金睛：看破数据结构

要掌握一个模块，首先要理清模块内的数据结构，数据结构是灵魂，函数是表现。而复杂的模块往往数据结构也是复杂的，主要表现在定义的结构体数量多，而且它们之间的关系错综复杂。

结构体间的关系中，类似指针这类单向引用关系容易理解，较难迅速理清的是间接关系，比如本章讨论的关系型数据结构。这些关系虽然表面上不明显，但还是有些技巧可以快速理清脉络的。

对一个结构体的某个字段，我们要关心字段类型和名字两方面，这句话看似多余却隐藏玄机。

首先，链表或树类型结构，如果区分链表头和元素（树的根和叶），从类型即可区分结构体在链表或树中的地位。

其次，字段类型在很大程度上体现了它的意图，这由类型本身的特性决定。链表一般用来遍历或者查找，红黑树一般用来查找。

最后，如果从类型上看不出门道，可以尝试从字段名入手，链表头的名字多为复数或者带有l(list)等字样。如果依然没有思路，可以借助于代码注释，虽然多数情况下会无功而返。