linux学习17，内核中链表的设计与实现

上一节较为详细的讨论了 linux 中的系统调用，接下来几节将学习 linux 内核中的基本数据结构的设计和实现。本节先来看看 linux 内核中的链表。

链表和数组有些相似

链表是基于 C语言指针的，看了我《C语言入门》系列文章的朋友应该记得这张图:

指针 p2 指向一块内存，可以通过 p2 修改该内存里保存的数值。链表其实也是类似的，只不过链表是一个挨一个“串起来”的：

这种形式的数据结构和静态数组有些相似，不过链表包含的元素都是动态创建插入的，编译的时候并不需要知道要创建多少元素，而且链表的每个元素创建时间可能差异比较大，所以各个链表元素在内存中往往也不是连续的。

也正是因为链表的各个元素在内存中不像数组元素那样连续，所以链表才需要额外的“连接方式”将这些元素连接起来，指针正是一种非常合适的“连接方式”。

如果使用基本数据类型定义链表，例如：

int* a;
int* b;
int* c;
a = b;
b = c;

这样的确定义了一个链表，但是却没有任何意义，因为它真的只是一个链表，无法存储任何额外的信息。所以，链表一般都是用复合数据类型定义，常用的是结构体数据类型，这样一来，一个基本的链表可以如下定义：

struct node{
    void* data;
    struct node* next;
};

这样就很好用了，next 成员负责连接下一个（数据结构一模一样的）节点，data 成员则负责存储数据，如果 data 成员不方便存储所有数据，还可以随时增加数据成员。这样的数据结构简图如下：

在某些链表中，每个节点还可以指向前一个节点：

struct node{
    void* data;
    struct node* prev;
    struct node* next;
};

它的数据结构简图如下：

因为这种链表可以同时向前和向后连接，所有常被称作“双向链表”。

上面介绍的两种链表，两端的节点常常是指向 NULL 的，表示链表的起点和终点。但是有的链表两端节点并不指向 NULL，而是分别指向首尾，这样就形成了“环形链表”，请看下图：

linux 内核常使用的标准链表就是环形双向链表，这主要是因为环形双向链表有最大的灵活性。

访问链表元素

访问数组元素时既可以线性访问，也可以随机访问。这是因为数组的各个元素在内存中是紧密排列的，只需知道其中一个元素的地址，其他元素的地址都可以简单的推算出来。

而链表的各个元素在内存中并不连续，所以只能通过 next 或者 prev 指针线性访问。例如先访问节点 1，然后利用节点 1 的next 指针访问节点 2，再利用节点 2 的next 指针访问节点 3。

当然了，访问链表也可以从任意指定的节点开始。如果链表是环形链表，则从任意一个节点都能够遍历所有链表元素。如果是双向链表，则从某个节点出发，既可以向前访问，也可以向后访问。

这是一种最简单的沿着链表访问元素的方法，也是最适合访问链表的方法。如果需要随机访问数据，则就不应该使用链表的数据类型了。链表最适合使用在需要遍历所有元素，以及需要动态插入删除数据的场景。

linux 内核中的链表的设计和实现

一般情况下，定义链表时都是通过在数据内部添加 prev 和 next 指针实现的，请看：

struct fox{
    int tail_len;
    int weight;
    struct fox* prev;
    struct fox* next;
};

上面的 C语言代码使用 prev 和 next 指针定义了一个双向链表，然后又插入了尾巴长度和体重两个成员，用于描述 fox(狐狸) ，这就相当于“把数据结构”塞入链表。

linux 内核使用链表的方式与众不同，它不是将数据结构塞入链表，而是把链表塞入数据结构。linux 内核的链表相关C语言代码在 <linux/list.h> 中声明：

struct list_head {
     struct list_head *next, *prev;
};

可以看出，这是相当简单的双向链表，next 指针指向下一个节点，prev 指向前一个。list_head 并没有存储其他数据的地方，那怎样使用呢？按照上面的说法，linux 内核“将链表塞入数据结构”，请看C语言代码：

struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};

这样链表就能存储其他数据了，访问下一个节点可以使用 fox 中的 list.next，访问前一个节点可以使用 list.prev。为了操作更方便，linux 内核还定义了一些链表操作函数，例如 list_add() 可以方便的将新节点加入链表，INIT_LIST_HEAD() 初始化链表等待：

不过 linux 内核提供的这些方法接收的参数都是 struct list_head 型的，而链表中的 next、prev 只是我们想使用的结构体中的成员而已，要是只知道 next、prev 的地址，怎样访问结构体的其他成员呢？这就要借助于 container_of() 宏了，它的 C 语言代码如下，请看：

#define container_of(ptr, type, member) ({          \
     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

通过 container_of 宏，linux 内核可以很方便的访问结构体的其他成员。这是因为在 C语言中，给定结构体中的变量偏移在编译时地址就被 ABI 固定下来了。

下面分析一下 container_of 宏，以 struct fox 为例：

struct fox{
    int tail_len;
    int weight;
    struct list_head list;
};
struct fox f;

已知 list 的地址，如何求 f 的地址呢？其实很简单，将 list 的地址减去 list 在 struct fox 中的偏移就可以了。

container_of 宏就是这样的思路：

const typeof( ((type *)0)->member ) *__mptr = (ptr);

这一句定义了一个和 member 同类型的指针 __mptr，并将 ptr 的地址传递给它。

 (type *)( (char *)__mptr - offsetof(type,member) );})

这一句的目的就是将 __mptr 减去 member 在 type 中的偏移，执行完毕之后就得到了 f 的地址，这时再访问其他成员就不难了。

offsetof 的宏定义如下，也是非常简单的：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

到这里，我们就清楚了linux 内核常用的标准链表的定义和基本使用方法。事实上，linux 内核还定义了一些其他比较方便操作链表的宏和方法，限于篇幅，下一节再说了。