导读：本文节选自人民邮电出版社出版的《Linux内核编程》一书。本书的三位作者有多年的行业经验：Claudia Salzberg Rodriguez就职于IBM Linux技术中心，从事内核及相关编程工具的开发工作；Gordon Fischer为很多设备开发了Linux和UNIX设备驱动程序；Steve Smolski在半导体行业已经浸染了26年，开发过各种驱动程序和嵌入式系统。该书译者为陈莉君、贺炎和刘霞林。
作者独特的由表及里的讲解方法使得内核编程更易于理解：从用户空间到内核，把内核内在的实现原理与用户级编程的基本原则相联系，系统地追踪了实现功能。这种途径有助于扩大你所了解的Linux知识，加深对内核组成及工作机理的理解。
图书封面：
内核探索工具集
Linux内核中包含许多对象和数据结构，例如内存页面、进程和中断。如果操作系统要高效运行，那么如何及时地从多个对象中引用其中某个对象将是至关重要的。Linux使用链表和二叉搜索树（以及一组辅助例程）先将这些对象分组放入一个容器中，然后再以某种有效的方式查找单个元素。
链表
在计算机科学中，链表是一种常见的数据类型，广泛用于Linux内核中。它在Linux内核中常以循环双向链表的形式出现（参见图2-1）。因此，给定链表中的任一节点，都可以找到其下一节点和上一节点。链表的完整代码存放在头文件include/linux/list.h中。本节讨论链表的主要特征。
图2-1 调用宏INIT_LIST_HEAD后的链表
以下是使用宏LIST_HEAD和INIT_LIST_HEAD初始化链表的代码：
- include/linux/list.h
- 27
- 28 struct list_head {
- 29 struct list_head *next, *prev;
- 30 };
- 31
- 32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
- 33
- 34 #define LIST_HEAD(name) \
- 35 struct list_head name = LIST_HEAD_INIT(name)
- 36
- 37 #define INIT_LIST_HEAD(ptr) do { \
- 38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
- 39 } while (0)
第34行：宏LIST_HEAD根据给定的名字name创建链表的表头。
第37行：宏INIT_LIST_HEAD将表头节点中的prev指针和next指针都初始化为指向表头节点本身，完成这两个宏调用后，name就指向一个空的双向链表 。
相应地，简单的栈和队列也可以由函数list_add()或list_add_tail()分别来实现，工作队列的代码中给出了一个典型的例子：
- kernel/workqueue.c
- 330 list_add(&wq->list, &workqueues);
内核将wq->list加入到系统的工作队列链表workqueues中，因此workqueues就是一个栈形式的队列。
与此类似，下列代码将work->entry添加到链表cwq->worklist的末尾，cwq->worklist因而也被当作队列：
- kernel/workqueue.c
- 84 list_add_tail(&work->entry, &cwq->worklist);
从链表中删除某个元素可以调用函数list_del()。该函数将要删除的链表元素作为参数，删除元素时，仅需修改该元素的下一个节点和前一个节点，使之互相指向对方即可。例如，当销毁一个工作队列时，下列代码可以从系统的工作队列链表中删除该工作队列：
- kernel/workqueue.c
- 382 list_del(&wq->list);
include/linux/list.h中定义了一个特别有用的宏list_for_each_entry：
- include/linux/list.h
- 349 /**
- 350 * list_for_each_entry - iterate over list of given type
- 351 * @pos: the type * to use as a loop counter.
- 352 * @head: the head for your list.
- 353 * @member: the name of the list_struct within the struct.
- 354 */
- 355 #define list_for_each_entry(pos, head, member)
- 356 for (pos = list_entry((head)->next, typeof(*pos), member),
- 357 prefetch(pos->member.next);
- 358 &pos->member != (head);
- 359 pos = list_entry(pos->member.next, typeof(*pos), member),
- 360 prefetch(pos->member.next))
该函数循环遍历整个链表，操作链表中的每个元素。例如，当CPU工作时，将为每个工作队列唤醒一个进程：
- kernel/workqueue.c
- 59 struct workqueue_struct {
- 60 struct cpu_workqueue_struct cpu_wq[NR_CPUS];
- 61 const char *name;
- 62 struct list_head list; /* Empty if single thread */
- 63 };
- ...
- 466 case CPU_ONLINE:
- 467 /* Kick off worker threads. */
- 468 list_for_each_entry(wq, &workqueues, list)
- 469 wake_up_process(wq->cpu_wq[hotcpu].thread);
- 470 break;
该宏展开并使用workqueue_struct wq中的list_head list链表来遍历那些头节点位于工作队列中的链表。如果这看起来让人有点困惑的话，请记住，为了遍历链表并不需要知道我们是哪个链表的成员。当前节点的next指针指向链表的头节点 时，就已经访问到该链表的表尾了。有关工作队列的说明参见图2-2。
图2-2 工作队列链表
与在前一节中讨论过的带有双指针的头节点相反，这里我们还可以修改链表，使其头节点中仅有一个指向第一个元素的指针，这样的头节点应用于散列表（参见第4章），它没有指向链表表尾元素的指针。由于在散列查找中不常用到尾指针，因而这样做可以节省内存空间。
- include/linux/list.h
- 484 struct hlist_head {
- 485 struct hlist_node *first;
- 486 };
- 488 struct hlist_node {
- 489 struct hlist_node *next, **pprev;
- 490 };
- 492 #define HLIST_HEAD_INIT { .first = NULL }
- 493 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
第492行：宏HLIST_HEAD_INIT将指针first置为空指针。
第493行：宏HLIST_HEAD根据名称创建链表，并将指针first置为空指针。
正如我们将会在调度程序、定时器和模块处理例程（module-handling routine）中看到的那样，整个Linux内核的工作队列代码中都用到了这些链表结构。
查找
上一节我们分析了链表中的分组元素。有序表根据链表中每个元素的关键值进行排序（例如，每个元素的关键值均大于其前一元素中对应的值）。如果想要找到某个特定元素（基于其关键值），可以从表头开始，顺序查找整个链表，比较当前节点的关键值与给定的关键值。如果不相等，就继续比较下一个元素，直到找到匹配的值为止。采用这种查找方法时，从链表中查找给定元素所花的时间与其关键值成正比。换句话说，如果增加链表中元素个数，这种线性查找将花费更多时间。
大O表示法
对于查找算法而言，大O表示法常用于从理论上来衡量一个算法找到某给定关键值的执行时间，它代表对于一个给定值n在最坏情况下所花费的查找时间。线性查找的效率是O（n/2），这就意味着，平均来算，找到一个给定关键值必须与链表中的一半元素进行比较。
出处：美国标准和技术协会（www.nist.gov）
对于元素较多的链表而言，为了不使操作系统空等，需要更快地存储和定位给定数据的方法。虽然目前已经实现了很多方法（包括其派生方法），但Linux存储数据时用的另一主要数据结构还是树。
树
树用于Linux内存管理中，能够高效地访问并操作数据。此时，其效率就是用存储和检索数据的快慢程度来衡量的。本节将讨论基本树，重点介绍红黑树，而关于树在Linux下的具体实现及其辅助例程，请参考第6章。在计算机科学中，有根树由节点和边组成（参见图2-3），节点代表数据元素，边代表节点之间的路径。第一个节点，或者说顶层节点，就是有根树的根节点。节点之间的相互关系有父、子、兄弟这三种。每个子节点有且仅有一个父节点（根节点除外），每个父节点可以有一个或多个子节点，互为兄弟的节点有共同的父节点，没有子的节点称为叶节点。树的高度是指从树根到最远的叶节点之间的边数。树的每一行子孙被称为一层。在图2-3中，b和c位于a的下一层，而d、e、f位于a下面两层。查找给定兄弟节点集合中的某一数据元素时，有序树最左边的兄弟节点其值最小，而最右边的兄弟节点其值最大。树通常以链表和数组的形式来实现，而在树中移动的过程就叫树的遍历。
图2-3 有根树
1.二叉树
前面我们用线性查找的方式来查找关键值，在每次循环中比较关键值的大小。如果每次比较都可以将有序表中待处理的节点数目减半呢？
二叉树和链表不同，它是一种非线性的分层数据结构。在二叉树中，每个元素或节点指向一个左子或右子节点，每个子节点又指向它的一个左子或右子节点，以此类推。其节点之间排序的主要规则就是左子节点的关键值小于父节点的关键值，而右子节点的关键值大于或等于父节点的关键值。因此，对于一个给定节点的关键值，其左子树上所有节点的关键值都小于该节点，而其右子树上所有节点的关键值都大于或等于该节点。
往二叉树中存放数据时，首先必须找到适当的插入位置，而每次循环都可以将要查找的数据个数减半。用大O表示法来表示时，其性能（关于查找的次数）就是O log(n)，相比之下，线性查找的性能是O(n/2)。
遍历二叉树的算法比较简单。对于每个节点而言，比较完该节点的关键值后，就可以遍历其左子树或者右子树，因而，二叉树的遍历本身就很方便用递归来实现。下面将讨论其具体实现、辅助函数以及二叉树的类型。
刚才我们提到，二叉树中的节点可以有一个左子节点，或者一个右子节点，或者有左、右两个子节点，也可以没有子节点。有序二叉树的规则是，给定一个节点的值x，其左子节点（包括所有子孙节点）的值小于x，而其右子节点（包括所有子孙节点）的值大于x。由此可知，如果将数据的有序集合插入到二叉树中，将形成一个线性列表，对于一个给定值，其查找速度就会变得和线性查找一样慢。例如，根据数据集[0,1,2,3,4,5,6]创建一颗二叉树时，0是树根；1比0大，是0的右子节点；2比1大，是1的右子节点；而3是2的右子节点，以此类推。
在均高二叉树中，根节点到任意叶节点的距离都是一样远的。节点添加到二叉树中后，为了保证查找的效率，必须进行平衡化处理，这可以通过旋转来实现。插入一个节点后，给定节点e，如果它有一个比任何其他叶节点高两层的左子树，就必须右旋转e。如图2-4所示，e变成h的父节点，e的右子节点则变成h的左子节点。如果每次插入节点后都进行了平衡化处理，那么，每次最多只需要作一次旋转。满足平衡规则（若某节点的子节点是一个叶节点的话，它们之间的间距不会超过1）的二叉树被称为AVL树（这一术语最初是由G.M.Adelson-Velskii和E.M.Landis提出来的）。
图2-4 二叉树的右旋转
2.红黑树
红黑树类似于AVL树，用于Linux内存管理。红黑树就是平衡二叉树，其每个节点都有红或黑的颜色属性。
红黑树的规则如下：
每个节点要么是红色的，要么是黑色的；
如果一个节点是红色的，那么它的所有子节点都是黑色的；
所有叶节点都是黑色的；
从根节点到叶节点的每条路径包含同样多的黑色节点。
AVL树和红黑树的查找效率都是O log(n)，而根据插入（已排序的/未排序的）和查找数据的不同，每次都能得出不同的具体数值。（网上有一些讨论二叉搜索树[BST]性能的文章，有兴趣的话，可以找来看看。）
前面已经提到，许多其他数据结构和相关的查找算法也被应用于计算机科学中。本节的主要目的是，希望通过介绍Linux内核中常用数据结构的基本概念，帮助探索Linux内核。对链表和树结构有一定了解后，就可以更好地理解复杂的操作，例如将在后续章节讨论的内存管理和队列。