# Linux 内核侵入式链表：struct list_head

> 内核链表不是"链表里装数据"，而是"数据里嵌链表节点"。这个翻转是理解所有 `list_head` 用法的起点。

## 零、一句话认知：侵入式链表

传统链表是"容器模式"——先有 `struct node { data; node *next; }`，数据是节点的一部分。内核链表反过来——节点嵌入在数据里：`struct my_struct { int data; struct list_head list; }`。

这样做的后果：
- 一个结构体可以同时挂在多条链表上（每条链一个 `list_head` 字段）
- 节点只存前后指针，不关心包含它的数据结构是什么
- `container_of()` 宏从节点指针反推出包含它的结构体指针

```bash
传统链表:                              内核侵入式链表:
┌─────┐    ┌─────┐    ┌─────┐          ┌──────────┐     ┌──────────┐
│node │ → │node │ → │node │          │ my_struct │     │ my_struct │
│data │   │data │   │data │          │  data=1   │     │  data=2   │
│next │   │next │   │next │          │ ┌──────┐  │ →  │ ┌──────┐  │
└─────┘   └─────┘   └─────┘          │ │list  │──┼────│→│list  │──┼→...
                                      │ └──────┘  │ ←──│ └──────┘  │
                                      └──────────┘     └──────────┘
```

## 一、核心数据结构

### 1.1 struct list_head —— 链表节点（嵌入在宿主结构体中）

```c
// include/linux/types.h
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};
```

节点本身只有两个指针，不包含数据 payload。可嵌入到任意结构体中使用。

### 1.2 list_head 的两种语义：头 vs 节点

同一个 `struct list_head` 扮演两种角色，靠用法区分：

| 角色 | 含义 | 初始化方式 |
|------|------|------------|
| **链表头** | 不承载数据，`next`/`prev` 指向首/尾节点；空链表时指向自身 | `LIST_HEAD(name)` 或 `INIT_LIST_HEAD(&head)` |
| **节点** | 嵌入在承载数据的宿主结构体中，是链表上的一个元素 | `INIT_LIST_HEAD(&node->list)` |

空链表形态：`head.next == &head` 且 `head.prev == &head`。这是判断 `list_empty()` 的根据。

```c
// 定义并初始化一个链表头
static LIST_HEAD(my_list);  // 展开: struct list_head my_list = { &my_list, &my_list }
// 或动态初始化
struct list_head head;
INIT_LIST_HEAD(&head);      // head->next = &head; head->prev = &head;
```

## 二、基本操作

### 2.1 添加

```c
// include/linux/list.h
// 添加到 head 后面（头插法）
void list_add(struct list_head *new, struct list_head *head);
// 添加到 head 前面（尾插法，即加到链表末尾）
void list_add_tail(struct list_head *new, struct list_head *head);
```

内部实现就是对 `prev`/`next` 的四指针调整，等价于：

```bash
list_add(new, head):
    new->next = head->next;
    new->prev = head;
    head->next->prev = new;
    head->next = new;
```

### 2.2 删除

```c
void list_del(struct list_head *entry);       // 删除节点（不重新初始化）
void list_del_init(struct list_head *entry);  // 删除并 INIT_LIST_HEAD（安全）
```

`list_del` 删完后 `entry->next` / `entry->prev` 被设为 `LIST_POISON1` / `LIST_POISON2`（调试用毒化指针），防止 use-after-free 时还能遍历。

`list_del_init` 删完后将 entry 重新初始化为自环（空节点），对 `list_empty(entry)` 返回 true——常用于"从链表上摘下再挂到别处"的场景。

### 2.3 移动与拼接

```c
// 将 list 节点从原链表移到 head 后面
void list_move(struct list_head *list, struct list_head *head);
// 将 list 节点从原链表移到 head 前面（移到末尾）
void list_move_tail(struct list_head *list, struct list_head *head);
// 将整个 src 链表（不含 src 头）拼接到 head 后面
void list_splice(const struct list_head *src, struct list_head *head);
// 同 list_splice，但 src 链表头随后被重新初始化
void list_splice_init(struct list_head *src, struct list_head *head);
```

### 2.4 判空与替换

```c
int list_empty(const struct list_head *head);          // head->next == head ?
int list_empty_careful(const struct list_head *head);  // 同时检查 next 和 prev
void list_replace(struct list_head *old, struct list_head *new);  // 原子替换
```

`list_empty_careful` 在无锁场景下更安全——检查 `head->next == head && head->prev == head`，但仅在与 `list_empty_careful` 配对使用时才可靠。

## 三、遍历 —— 最常用的部分

### 3.1 遍历节点本身（不常用）

```c
// 从 head 的下一个开始，每次取 pos（struct list_head *）
struct list_head *pos;
list_for_each(pos, head) {
    // pos 指向的是链表节点，不是包含数据的结构体
}
```

### 3.2 list_for_each_entry —— 遍历包含数据的结构体（★最常用）

```c
// include/linux/list.h
#define list_for_each_entry(pos, head, member) \
    for (pos = list_first_entry(head, typeof(*pos), member); \
         !list_entry_is_head(pos, head, member);            \
         pos = list_next_entry(pos, member))
```

参数含义：

- **`pos`**：循环变量，类型是你嵌入 `list_head` 的那个结构体的指针
- **`head`**：链表头的指针
- **`member`**：`list_head` 字段在你结构体中的名字

```c
// 示例: 遍历 task_struct 的子进程链表
struct task_struct *child;
list_for_each_entry(child, &current->signal->thread_head, thread_group) {
    // 这里的 child 已经是 task_struct *，不需要手动 container_of
}
```

### 3.3 container_of —— 这一切的基础

```c
// include/linux/container_of.h
#define container_of(ptr, type, member) \
    ({ \
        const typeof(((type *)0)->member) *__mptr = (ptr); \
        (type *)((char *)__mptr - offsetof(type, member)); \
    })
```

给定一个成员的指针 `ptr`、包含它的结构体类型 `type`、成员名 `member`，算出包含它的结构体的地址。核心是 `offsetof` 获取 member 在 type 中的偏移，再从 ptr 减去这个偏移。

```c
// 示例: 从 list_head 节点反推 task_struct
struct task_struct *task = container_of(node, struct task_struct, thread_group);
```

**为什么需要 `char *` 转换？** 指针运算以指向类型的大小为单位。转为 `char *` 后偏移就按字节计算——`offsetof` 返回的正是字节偏移。

### 3.4 安全遍历 —— 遍历过程中可能删除节点

```c
#define list_for_each_entry_safe(pos, n, head, member) \
    for (pos = list_first_entry(head, typeof(*pos), member), \
         n   = list_next_entry(pos, member);               \
         !list_entry_is_head(pos, head, member);            \
         pos = n, n = list_next_entry(n, member))
```

多一个 `n` 参数——预先保存下一个节点指针。删除 `pos` 后还能继续遍历。普通 `list_for_each_entry` 删除 `pos` 后再取 `pos->member.next` 就是 use-after-free。

```c
struct task_struct *child, *next;
list_for_each_entry_safe(child, next, &current->children, sibling) {
    if (child->exit_state) {
        list_del_init(&child->sibling);  // 安全删除
    }
}
```

### 3.5 反向遍历

```c
list_for_each_entry_reverse(pos, head, member);       // 从尾到头
list_for_each_entry_safe_reverse(pos, n, head, member);// 安全反向
```

## 四、hlist —— 哈希表优化的变体

```plantuml
@startuml
skinparam class {
    BorderColor #333
    HeaderBackgroundColor #E8E8E8
}
class "struct hlist_head" as hhead {
    + first : hlist_node *
}
class "struct hlist_node" as hnode {
    + next : hlist_node *
    + pprev : hlist_node **
}
class "struct list_head" as lhead {
    + next : list_head *
    + prev : list_head *
}
hhead -[hidden]right-> lhead : vs
hnode -[hidden]right-> lhead
note bottom of hhead
  节省一个指针 (无 prev)
  first=NULL 表示空
end note
note bottom of hnode
  pprev 是 "指向前一个节点的 next/pprev 指针的指针"
  通过 **pprev 修改前驱的 next 来删除自己
end note
@enduml
```

hlist 是 `list_head` 的变体，为哈希表桶（bucket）做了优化：

- **`hlist_head`** 只有一个 `first` 指针（省一半内存——哈希表有大量桶）
- **`hlist_node`** 有 `next` 和 `pprev`（而非 `prev`）。`pprev` 是 **指向前一个节点的 next 指针的指针**——这样从 hlist_head 和 hlist_node 删除都能用同一套代码

操作接口与 list_head 平行：

```c
// include/linux/list.h
#define HLIST_HEAD(name) { .first = NULL }
// 遍历
#define hlist_for_each_entry(pos, head, member) ...
// 添加
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h);
// 删除 —— hlist_del 不需要知道 head！因为 pprev 直接指向要修改的指针
static inline void hlist_del(struct hlist_node *n);
```

`hlist_del` 不需要 head 参数——这正是 `pprev` 设计的精妙之处：`*pprev` 就是前驱节点（或 hlist_head）中指向当前节点的指针，直接改它就行。

## 五、常见模式与陷阱

### 5.1 一个结构体多条链表

同一个 `task_struct` 挂在多张链上，每条链一个 `list_head` 字段：

```c
struct task_struct {
    // ...
    struct list_head tasks;       // 全局 task 链表 (init_task.tasks)
    struct list_head children;    // 子进程链表 (父进程的 children 头)
    struct list_head sibling;     // 兄弟进程链 (挂在父进程 children 上的节点)
    struct list_head thread_group;// 线程组链表
    // ...
};
```

`sibling` 既是 `children` 链表上的节点（被父进程遍历），也是自己的 `sibling` 节点的容器——"节点"和"头"的语义在这里无缝切换。

### 5.2 不要在遍历普通版本中删除

```c
// 错误 —— pos 被释放后访问 pos->member.next
list_for_each_entry(pos, head, member) {
    if (should_delete(pos))
        list_del(&pos->member);  // pos 可能已释放!
}
// 正确 —— 用 _safe 版本
list_for_each_entry_safe(pos, n, head, member) {
    if (should_delete(pos))
        list_del(&pos->member);
}
```

### 5.3 空链表判断

```c
if (list_empty(&head)) {
    // 链表为空: head->next == &head
}
```

不要在 RCU 场景用 `list_empty` 判断空——RCU 遍历通过 `list_for_each_entry_rcu` 走，删除不立即生效，`list_empty` 可能看到中间态。

### 5.4 取首元素

```c
struct my_struct *first = list_first_entry(&head, struct my_struct, list);
struct my_struct *last  = list_last_entry(&head, struct my_struct, list);
// 安全版本——空链表返回 NULL
struct my_struct *first_or_null = list_first_entry_or_null(&head, struct my_struct, list);
```

## 六、小结

```bash
        list_head 操作速查
        ──────────────────────────────────────────────
        初始化:   LIST_HEAD / INIT_LIST_HEAD
        添加:     list_add / list_add_tail
        删除:     list_del / list_del_init
        移动:     list_move / list_move_tail
        拼接:     list_splice / list_splice_init
        遍历:     list_for_each_entry         ← 最常用
                  list_for_each_entry_safe    ← 遍历中可能删除
        判空:     list_empty / list_empty_careful
        取首:     list_first_entry / list_first_entry_or_null
        取尾:     list_last_entry
        ──────────────────────────────────────────────
        hlist:    hlist_for_each_entry (哈希桶优化版)
```

**核心心法**：

1. **侵入式设计**：数据嵌节点，不是节点装数据。一个结构体可以挂多条链。
2. **`container_of`**：从节点推宿主，整个遍历体系建立在这个宏上。
3. **`list_for_each_entry` vs `_safe`**：只要循环体可能删除，就用 `_safe` 版本。
4. **hlist 的 `pprev`**：二级指针让删除不需要知道 head——哈希表桶删除的高效实现。