期末考试结束，继续更新。本篇是《Linux内核学习笔记》系列的第四篇。

利用内核提供的现成数据结构，我们更容易写出kernel-style、高效、bug-free的代码。

本文面向有数据结构和算法基础的读者，仅仅讲述kernel中的实现思想。

1. 链表

Linux的链表是双向循环链表，实现于include/linux/list.h。

通常我们实现的链表以及STL中的链表，都是将数据结构放入链表节点，例如我们可以在结构体末尾添加next指针。在Linux中，链表指针被封装为结构体，用户需要使用链表时，在自定义的结构中追加一个链表指针结构体即可。

这一结构体定义如下。

// In <linux/types.h>
struct list_head {
	struct list_head *next, *prev;
};

接下来的例子我们使用一个名为fox的数据结构。

struct fox {
	unsigned long tail_length;
	unsigned long weight;
	bool is_fantastic;
	struct list_head list;
};

1.1. 构建

链表的使用和内存管理解耦。使用者通常需要为链表节点申请内存空间，然后用INIT_LIST_HEAD进行初始化，例如：

struct fox *red_fox;
red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL);
// init data...
INIT_LIST_HEAD(&red_fox->list);

INIT_LIST_HEAD将list_head结构体的两个指针都指向自身。

如果用户选择静态创建链表，内核也提供了相应的初始化方式。

struct fox red_fox = {
	// init all other data here
	.list = LIST_HEAD_INIT(red_fox.list)
};

LIST_HEAD_INIT展开后是一个初始化列表，两个成员均为list_head结构体自身的地址。

1.2. 操作

可以分为两种：

• 表层，但是可能产生冗余操作；
• 里层，但更加直接高效。以双下划线开头，例如__list_add。

注意，传入函数的必须是已初始化过的链表节点。内核数据结构没有义务对指针合法性作判断。

表层函数支持的部分操作：

• 在某节点前/后添加节点
• 删除某给定节点
• 将某节点和来自外部的节点交换位置
• 将某节点移动到另一节点前/后
• 旋转环形链表

里层函数支持的部分操作：

• 在两相邻节点之间插入新节点
• 删除两相邻节点间的节点

这些操作非常简单，只需要对链表指针结构进行操作，不需要涉及父结构内容。

1.3. 遍历

有一个问题：沿着list_head得到的还是list_head，怎么才能拿到父结构的指针？

其实每个结构的所有成员在编译时就确定了它们在结构体中的相对位置。下面的代码会得到list相对结构体fox开始的偏移量：

int offset = (void *)&((struct fox *)0)->list - (void *)0;

对任意的list_head指针，我们为其减去这段偏移量，不就得到fox结构体开始的位置了？

struct fox *red_fox = (void *)ptr - offset;

<linux/kernel.h>中给出了Linux内核对此问题的回答：

// In <linux/kernel.h>
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

大致原理和前述不会差太多。

<linux/list.h>则将其封装为链表中的一个基本方法。

// In <linux/list.h>

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

有了这样的方法，我们就可以愉快地遍历链表中的每一个fox节点啦。遍历的方法都是通过宏封装的，这里不再赘述实现，有需要去头文件查就可以了。

2. 队列

队列实现于<linux/kfifo.h>。它和list_head不一样，也不应该一样——这次则更像STL中queue的实现。用list_head可以轻松实现一个队列，那kfifo的优势又是什么呢？

• 队列数据结构会管内存分配；
• 队列数据连续存放在缓冲区，是流式数据（即是按字节排列而不是结构体排列）；
• 是一个同步队列。

2.1. 构建

内核提供三种方式。

• 直接从内核获取动态内存，使用kfifo_alloc；
• 要自己分配数据缓冲区，使用kfifo_init；
• 产生静态的kfifo，使用DECLARE_KFIFO、INIT_KFIFO。

链表就不能通过第一种方式进行初始化。不管是从栈获取还是动态申请，总之就是要有已经准备好的内存才行。

2.2. 操作

入队、出队等等，这里不再赘述。

2.3. 重置

用kfifo_reset清空数据。

2.4. 撤销

动态申请的kfifo需要显式调用kfifo_free撤销。其他方式得到的kfifo就是自己从哪搞来的内存自己还到哪去（笑

3. 哈希链表

哈希链表hlist_head和hlist_node也是普通的、线性的链表，但和list_head有不同之处。

3.1. 哈希链表原理

hlist_head定义如下：

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

可以看到哈希链表是哈希表的一部分，其实也就是哈希表的一个bucket。hlist_node有一个诡异的二级指针pprev，指向上一个节点的first或next。

可以想到，哈希表是以空间换时间。hlist_head比list_head占用空间小了一半，那哈希表数列的占用空间就小了一半。

但是，由于每个hlist_node的上游节点可能是hlist_node，也可能是hlist_head，所以不方便用一个指针来表示前驱。好在这两种节点都有个hlist_node *成员，因此可以将前驱的类型统一为hlist_node **。