侵入式链表

# 侵入式链表 - 数据结构实战 来源：https://www.data-structures-in-practice.com/intrusive-linked-lists/ 本文将介绍什么是侵入式链表，以及它们如何在Linux中用于管理进程。 ## 什么是侵入式链表？ 侵入式链表是链表 (https://www.data-structures-in-practice.com/linked-lists/) 的一种变体，其链接结构被嵌入在待链接的数据结构本身中。 在典型的链表实现中，一个链表节点包含一个指向链接数据的`data`指针和一个指向链表中下一个节点的`next`指针。 #### 图1：普通链表 在侵入式链表的实现中，链表节点包含指向下一个链表节点的`next`指针，但没有`data`指针，因为链表结构本身已嵌入到链接对象中。 #### 图2：侵入式链表 用于侵入式单向链表的`list`结构体包含一个指向另一个链表节点的`next`指针： ```c typedef struct list { struct list *next; } list; ``` 这个`list`结构体随后被嵌入到需要被链接的结构体中。例如，你可能有一个包含`val`成员的`item`结构体： ```c typedef struct item { int val; list items; } item; ``` 要将一个新项目`i2`添加到`i1`的链表中，你需要将`i1`的`items.next`指针设置为`i2.items`的地址： ```c item* i1 = create_item(16); item* i2 = create_item(18); i1->items.next = &i2->items; ``` 要访问包含链表节点的对象，你可以首先获取链表对象的地址（例如`i1.items.next`的值）。然后，从该地址减去链表成员在结构体中的**偏移量**。 **偏移量**是一个成员距离其所在结构体起始位置的字节数。 #### 图3：包含嵌入式链表的对象的地址 假设一个`list`对象位于内存地址`0x18`，属于对象`i2`。`list`成员在`item`数据结构起始位置的偏移量为8字节。因此，`i2`对象的起始地址是`0x18 - 8 = 0x10`。 在GCC编译的C语言中，可以通过将指针变量强制转换为`void*`指针（在GCC编译下`void*`的大小为1字节）来从指针中减去字节数。这样你就可以直接从指针值中减去字节数，而不会被缩放为`num * sizeof(structure)`： ```c item* _i2 = (void *)(i1->items.next) - 8; ``` *注意：在C语言中对void指针进行指针算术运算是非法的，但GCC支持此特性。Linux使用GCC编译，因此可以对void指针进行指针算术运算。* 减去绝对值的可移植性较差，因为不同的CPU架构下数据类型可能有不同的大小。更好的方法是使用`offsetof`宏。`offsetof`返回一个成员相对于其所在结构体的偏移量（以字节为单位）： ```c item* _s2 = (void *)(i1->items.next) - (offsetof(item, items)); ``` 总结如下： - 链表节点被嵌入在一个容器对象中。 - 链表节点指向另一个嵌入在链接对象中的链表节点。 - 通过将链表对象的内存地址减去链表成员的偏移量，来计算链接对象的基地址。 经过这一系列指针运算，你可能在想，正常人为什么会选择使用侵入式链表而不是普通链表。 使用侵入式链表而非非侵入式链表的主要原因有两个： - 更少的内存分配。 - 更少的缓存抖动。 对于非侵入式链表，创建一个新对象并将其添加到链表中需要两次内存分配：一次用于对象，一次用于链表节点。而对于侵入式链表，你只需要分配一个对象（因为链表节点已嵌入对象中）。这意味着需要处理的错误更少，因为内存分配可能失败的情况减少了一半。 侵入式链表也更少受到缓存抖动的影响。遍历一个非侵入式链表节点需要解引用链表节点，然后再解引用链表数据。而侵入式链表只需要解引用下一个链表节点即可。 在研究Linux如何使用链表管理进程之前，你需要了解双向链表和循环链表。 ## 双向链表和循环链表 双向链表和循环链表是单向链表的变体。Linux使用循环双向链表，所以本节将介绍这两种变体。 **双向链表**是一种同时保留指向下一个节点和上一个节点指针的链表。 #### 图4：双向链表 这种链表结构会包含一个额外的`prev`指针： ```c typedef struct dlist { struct dlist *next; struct dlist *prev; } dlist; ``` 双向链表使得删除和插入操作更容易，因为你只需要引用单个节点就可以执行删除或插入。 链表的另一种变体是**循环链表**。循环链表是一种永远不会指向空值的链表。相反，最后一个节点指向第一个节点。在循环双向链表中，第一个节点也指向最后一个节点。 #### 图5：循环双向链表 循环链表使得从任何节点遍历整个链表变得很容易，无需维护对特定链表头的引用： ```c void list_print_each(list* node) { list* start = node; do { printf("%d,", node->val); node = node->next; } while (node != start); } ``` Linux中最流行的链表就是循环双向链表。 ## Linux中的链表 Linux广泛使用链表。它们用于各种任务，从跟踪空闲内存块到遍历每个运行的进程。在Linux 5.2中，搜索`struct list_head`结构体会返回超过10,000个结果。 在Linux中，链表节点的添加和删除操作远比遍历操作频繁。对正常使用下的Linux进行分析发现，遍历操作仅占链表操作总数的6%。其中，28%的遍历发生在空链表上，或者仅访问了一个节点（更多信息请参阅Rusty Russel对链表的分析 (http://rusty.ozlabs.org/?p=168)）。 正如Rusty的分析所表明的，Linux主要使用链表来维护对象列表，适用于遍历不频繁或链表规模较小的情况。 Linux包含几种不同的链表结构。最流行的是侵入式循环双向链表。 ### 实现侵入式链表 Linux的循环双向链表定义在 `include/linux/list.h` (https://elixir.bootlin.com/linux/v5.2/source/include/linux/list.h) 中。 该链表结构命名为`list_head`。它包含一个`next`和一个`prev`指针： ```c struct list_head { struct list_head *next, *prev; }; ``` 你通过在将被制成链表的结构体中嵌入`list_head`成员来创建对象的链表： ```c struct atmel_sha_drv { struct list_head head; // .. }; ``` 新的链表可以是静态初始化或动态初始化的。 静态初始化的链表可以使用`LIST_HEAD_INIT`宏： ```c static struct atmel_sha_drv atmel_sha = { .dev_list = LIST_HEAD_INIT(atmel_sha.dev_list), // .. }; ``` `LIST_HEAD_INIT`展开后将链表节点的`next`和`prev`指针设置为指向自身： ```c #define LIST_HEAD_INIT(name) { &(name), &(name) } ``` 要动态初始化一个链表，你可以使用`INIT_LIST_HEAD`宏。通常会单独保留一个`list_head`作为头节点： ```c static struct list_head hole_cache; INIT_LIST_HEAD(&hole_cache); ``` `INIT_LIST_HEAD`接收一个`list`节点的指针。同样，链表的`next`和`prev`指针被设置为指向自身： ```c static inline void INIT_LIST_HEAD(struct list_head *list) { WRITE_ONCE(list->next, list); list->prev = list; } ``` *注意：`WRITE_ONCE`宏用于防止赋值时发生不必要的编译器优化。* 链表初始化后，可以使用`list_add`添加新项目： ```c struct hole { // .. struct list_head list; }; static struct hole initholes[64]; // .. for(i = 0; i < 64; i++) list_add(&(initholes[i].list), &hole_cache); ``` `list_add`接受一个头节点指针和一个待插入节点的指针。然后它调用`__list_add`在`head`节点和`head->next`之间插入新节点： ```c static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } ``` `__list_add`重新分配指针以添加新的链表节点： ```c static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { // .. next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); } ``` Linux提供了一个`list_entry`宏来访问包含链表节点的数据结构： ```c struct hole *ret; ret = list_entry(hole_cache.next, struct hole, list); ``` 这使用了本文前面提到的`offsetof`技巧。`list_entry`展开为一个`container_of`宏： ```c #define list_entry(ptr, type, member) \ container_of(ptr, type, member) ``` `container_of`宏通过从`list_head`对象的地址中减去链表节点的偏移量来计算容器对象的地址： ```c #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ ((type *)(__mptr - offsetof(type, member))); }) ``` 这就是Linux中侵入式链表的基本实现。 ### 跟踪进程 在POSIX标准中，进程是程序的一个执行实例。内核的核心职责之一就是创建进程并调度它们，使每个进程都运行适当的时间。 在内部，Linux将进程称为**任务**。当任务被创建时，它们会被添加到一个**任务链表**中。当Linux需要遍历每一个任务时（例如向每个进程发送信号），就会使用这个链表。 Linux将任务表示为一个`task_struct`。`task_struct`包含一个名为`tasks`的`list_head`成员，用于链接任务： ```c struct task_struct { // .. pid_t pid; // .. struct list_head tasks; // .. }; ``` 初始任务`init_task`是静态分配的，其`tasks`字段被初始化为以自身为头： ```c struct task_struct init_task = { // .. .tasks = LIST_HEAD_INIT(init_task.tasks), }; ``` 后续创建的任务将被添加到这个任务链表中。 在Linux中，新任务是通过fork创建的。这在`copy_process`函数中实现，该函数通过调用`dup_task_struct`从当前执行的进程（`current`）创建一个新的`task_struct`： ```c struct task_struct *copy_process( // .. ) { struct task_struct *p; // .. p = dup_task_struct(current, node); // .. } ``` 新任务创建后，通过以`init_task.tasks`的地址调用`list_add_tail_rcu`将其添加到任务链表中： ```c struct task_struct *copy_process( // .. ) { // .. list_add_tail_rcu(&p->tasks, &init_task.tasks); } ``` `list_add_tail_rcu`是前面`list_add`函数的一个变体。它使用RCU，这是一种支持单个写者和多个读者并发的同步机制（此处不深入细节）。`list_add_tail_rcu`的效果是将新创建任务的`tasks`节点添加到`init_task`任务链表的尾部。 如前所述，任务链表主要用于内核需要对每个任务执行操作时。例如，当计算机进入休眠模式时冻结任务，在进行在线补丁时将任务切换到更新版本的内核，或者向每个进程发送信号。这些使用场景大多不常见，因此遍历链表中每个项目的效率不是主要问题。 一个向每个进程发送信号的场景是同时按下SysRq键和e键，这将终止所有进程。 *注意：SysReq是一个在80年代添加的按键，Linux为其添加了默认的快捷键组合。* 内核注册了一个处理函数，当按下SysRq + e键时调用。该处理函数调用`send_sig_all`，并传入`SIGTERM`，从而向除`init`进程和内核任务外的所有进程发送`SIGTERM`信号。它通过`for_each_process`宏实现。从代码中可以看出，如果进程是内核线程或`init`任务，它将不做任何操作，否则调用`do_send_sig_info`。 ```c static void send_sig_all(int sig) { struct task_struct *p; // .. for_each_process(p) { if (p->flags & PF_KTHREAD) continue; if (is_global_init(p)) continue; do_send_sig_info(sig, SEND_SIG_PRIV, p, PIDTYPE_MAX); } // .. } ``` 至此，全是宏。`for_each_process`宏展开成一个`for`循环，该循环通过改变`p`的值来遍历链表中的每一项。从`init_task`开始，它使用`next_task`宏到达链表中的下一个任务： ```c #define for_each_process(p) \ for (p = &init_task ; (p = next_task(p)) != &init_task ; ) ``` `next_task`宏展开为`list_entry_rcu`，以从链表头指针获取下一个`task_struct`： ```c #define next_task(p) \ list_entry_rcu((p)->tasks.next, struct task_struct, `tasks`) ``` `list_entry_rcu`本身也是一个宏，它展开为`container_of`宏，然后获取容器结构体的基地址。 值得注意的是，`tasks`链表并不是Linux维护任务引用的唯一方式。它还创建了一个字典数据结构（idr），可以提供常数时间的访问，用于从给定的pid快速访问`task`对象。这比遍历整个任务链表要高效得多。 ## 结论 侵入式链表是普通链表一个有趣的替代方案，它减少了缓存抖动和内存分配。 Linux大量使用侵入式链表，通常是在链表较短或很少被遍历的情况下。如果你计划成为一名内核黑客，你应该熟悉侵入式链表。