双链表是最常用的数据结构之一,在Linux内核中也不例外。下图表示了双链表在内核中的实现:

Linux中的双链表

可以看出,链表的组织是循环的,即第一个元素的前一项是链表中的最后一项,最后一项的下一项是链表的第一项。

我们在用到双链表时,通常会这样定义结构体:

内核提供了下列结构:

这样在需要双链表的结构中只需要加入一个 struct list_head 结构的成员:

在两个连续的链表项中间插入一个新项时,可以调用 list_add 函数:

它又把添加任务交给了 __list_add:

调用 list_add_tail 可以将新元素插入到目标链表之前:

删除操作也非常的简单:

将删除项的 next 和 prev 指向 LIST_POISON1 和 LIST_POISON2 用于调试,它们在 <poison.h>中定义:

它们都是非空指针,但对它们进行解引用会导致页错误,可以用于验证是否使用了未初始化的链表项。一个初始化过的链表项的前一项和后一项都是自己:

如果想在删除元素的同时把它初始化,可以调用 list_del_init:

list_replace 可以用新元素替换旧元素:

与 list_del_init 类似,被替换的旧元素也可以同时被初始化:

list_move 可以将某一元素从链表中删除并将其添加到指定元素之后,其实现也非常直观:

也可以将其插入到指定元素之前:

list_is_last 用于判断某一项是否是链表的最后一项:

list_empty 用于判断链表是否为空:

这里的空并不是指没有任何元素,而是只有一个头结点,因为头结点通常不包含元素的信息,可以认为只有头结点的链表是空的。

考虑这样一种情况:如果在调用此函数期间,另一CPU调用 __list_add 添加一个元素,并且只执行到设置 prev 指针,也就是说 head->next 还是等于 head 但 head->prev 已经不等于 head 了,那么 list_empty 还会返回1。

list_empty_careful 用来测试这种情况,可以避免在测试的同时链表也在被修改而导致的测试错误:

如果需要测试链表是否只包含一个元素,可以调用 list_is_singular:

list_rotate_left 用于将某一项与它的后一项交换位置:

list_cut_position 用于将一个链表分裂成两个:

head 是原链表的头结点,entry 是这个链表中的一项,list 用来接收 entryentry 前面的元素,entry 的后一项将作为以 head 为头结点的链表的第一项。

list_cut_position 做了简单的判断。如果原链表为空,就没有分裂的必要了;如果只有一个元素并且 entry 既不是头结点又不是唯一的元素结点,也不会分裂;如果 entry 是头结点,就仅仅初始化 list 头结点。否则,就把分裂的任务交给 __list_cut_position。分裂过程可以用下图说明:

Linux中的双链表的分裂

表头和表尾之间的连线没有画出来,实际上它们是存在的。

内核不仅提供了分裂操作,也提供了合并操作:

以 list_splice 为例,下图说明了合并的过程:

Linux中的双链表的合并

如果内核只有这些那就太无趣了。 考虑如何遍历一个链表?比如有一个班级,属于这个班级的学生用链表组织,如果不使用内核的这种通用实现,那么可能需要这样定义结构体:

这样遍历所有学生并没有什么困难:

但使用通用实现后,结构的定义将变为:

这时遍历 s_list 是毫无意义的,因为真正的有用信息在它的宿主 struct student 结构中。注意,链表成员并不一定是宿主结构的第一个成员,所以我们不能假定链表指针指向的位置和宿主的首地址相同,甚至一个结构也可能在多个链表中。

内核提供了遍历链表的宏:

list_for_each_entry_safe 可以安全的遍历。如果在遍历链表的同时删除了元素,就无法查找到它的下一个元素。list_for_each_entry_safe 先用 n 保存了下一个元素,可以解决这种问题。

它们的实现不是很直观,下面我们以 list_for_each_entry 为例,利用该宏遍历学生:

将宏定义展开,看看这个 for 循环到底做了什么:

再看看 list_entry 的定义:

ptr 是一个指向链表元素的指针,type 是宿主的类型,member 指定了宿主中哪个成员表示当前链表的链表元素。

list_entry 用来查找链表元素的宿主的实例,它是通过容器机制实现的:

typeof 是 GNU C 扩展的关键字,可以获取参数的类型。比如 int x; typeof(x) 的结果就是 int。点这里了解更多

offsetof 用于获取结构中某一成员相对于结构首地址的偏移量,它的定义如下:

在我们的例子中,将 offsetof 展开就是:

通过类型转换,将 0 转换为指向 struct student 的指针。这是可以的,因为我们没有对这个进行解引用。然后通过 -> 和 & 操作获取 s_list 的地址,也就是相对于 struct student 的首地址(这里它的首地址是0)的偏移量。

再来看 container_of 的实现。它先定义了一个类型为 struct list_head 的变量,它指向宿主中的 struct list_head成员,再将其转换成 char * 类型,保证与偏移量的减法运算是按字节计算的。这样就计算出了宿主的首地址。