Unix GC 重制版

# Unix GC 重制版 – Moe 的 VR 博客 来源：https://mohandacherir.github.io/Qdiv7/posts/unix_new_gc/ ## 引言 AF\_UNIX 垃圾回收器是内核中一个有趣的组成部分。它的存在是因为套接字可以通过 `SCM_RIGHTS` 发送，但可能变得无法从用户空间访问，而内核却仍保持它们存活，这不利于内存效率；在这种情况下，垃圾回收器会介入来释放它们。不久前，该子系统在一个图/强连通分量模型的基础上被完全重写；但它仍然容易出错。本文从头到尾讲解这次重写，并讨论一个释放后使用（Use-After-Free）漏洞。 --- ## AF\_UNIX 垃圾回收器 — 背景 一个子系统级别的垃圾回收器负责回收那些无法通过用户空间句柄再访问到的内核对象。对于 AF_UNIX，入口点是 `unix_gc()`： ```c static DECLARE_WORK(unix_gc_work, __unix_gc); void unix_gc(void) { WRITE_ONCE(gc_in_progress, true); queue_work(system_dfl_wq, &unix_gc_work); } ``` 其实际主体是 `__unix_gc()`： ```c static void __unix_gc(struct work_struct *work) { struct sk_buff_head hitlist; struct sk_buff *skb; spin_lock(&unix_gc_lock); if (!unix_graph_maybe_cyclic) { spin_unlock(&unix_gc_lock); goto skip_gc; } __skb_queue_head_init(&hitlist); if (unix_graph_grouped) unix_walk_scc_fast(&hitlist); else unix_walk_scc(&hitlist); spin_unlock(&unix_gc_lock); skb_queue_walk(&hitlist, skb) { if (UNIXCB(skb).fp) UNIXCB(skb).fp->dead = true; } __skb_queue_purge_reason(&hitlist, SKB_DROP_REASON_SOCKET_CLOSE); skip_gc: WRITE_ONCE(gc_in_progress, false); } ``` ### `unix_sock` 结构 ```c struct unix_sock { /* 注意：sk 必须是第一个成员 */ struct sock sk; /* 继承 */ struct unix_address *addr; /* 绑定的名称 */ struct path path; /* 绑定的文件系统路径 */ struct mutex iolock, bindlock; struct sock *peer; /* 连接的对端 */ struct list_head link; atomic_long_t inflight; /* [1] SCM_RIGHTS 文件描述符计数 */ /* ... */ struct sk_buff *oob_skb; }; ``` 对 GC 关键的是 **`inflight`** (**[1]**)。当一个套接字的 `struct file *` 作为 SCM_RIGHTS 载荷在传输中 —— 由进程 A 发送，尚未被进程 B 接收时，该套接字被称为“飞行中”（inflight）。每次发送时，`inflight` 递增；每次接收时，`inflight` 递减。GC 寻找满足 **`file_count == inflight`** 的套接字：剩下的唯一引用是困在其他套接字接收队列中的那些，即用户空间句柄再也无法访问它们。LWN 文章《AF_UNIX GC 重制》(https://lwn.net/Articles/966730/) 表述得更简洁： > 假设我们将 AF_UNIX 套接字 A 的 fd 发送给 B，同时将 B 的 fd 发送给 A，然后 `close()` 两个套接字。创建时，每个套接字的 `struct file` 初始有一个引用。交换 fd 后，两个引用计数都增加到 2。然后 `close()` 将两者减为 1。从此时起，没有人能再触碰到这个文件/套接字。然而，`struct file` 的引用计数为 1，因此永远不会调用 AF_UNIX 套接字的 `release()` 函数。这就是为什么我们需要跟踪所有飞行中的 AF_UNIX 套接字并运行垃圾回收。 内核维护一个全局计数器 `unix_tot_inflight`，每次进入飞行状态时递增，每次被接收时递减。 ### GC 何时运行 有 **两个** 触发条件： 1. 飞行中套接字过多： ```c if (READ_ONCE(unix_tot_inflight) > UNIX_INFLIGHT_TRIGGER_GC && !READ_ONCE(gc_in_progress)) unix_gc(); ``` （`UNIX_INFLIGHT_TRIGGER_GC == 16000`。） 2. 套接字关闭时，如果有任何飞行中的套接字： ```c static const struct proto_ops unix_stream_ops = { .family = PF_UNIX, .owner = THIS_MODULE, .release = unix_release, /* ... */ }; static void unix_release_sock(struct sock *sk, int embrion) { /* ... */ if (READ_ONCE(unix_tot_inflight)) unix_gc(); } ``` --- ## 旧的 GC 2024 年之前的收集器在 Google 安全研究团队（P0）的博文《Linux 内核垃圾回收的量子态》(https://projectzero.google/2022/08/the-quantum-state-of-linux-kernel.html) 中有详细描述，该文既介绍了算法，也介绍了 2021 年一个 Android 野外利用。那篇文章是推荐的配套阅读；这里只给出单行总结：旧的 GC 遍历飞行图，标记循环，并检查 `inflight != refcount` 以决定每个循环是否可回收。 下面是一个漂亮的 mermaid 图： --- ## 新的 GC 根据 GC 重制 (https://lwn.net/Articles/966730/) 公告： > [它] 替换了当前的 GC 实现，后者会锁住每个飞行中套接字的接收队列，并需要在其他地方做一些巧妙处理。新的 GC 不锁每个套接字的队列以最小化影响，并且在飞行中 fd 图形没有循环引用或形状没有变化时尽量轻量。 ### 图表示 每个飞行中套接字成为一个 **顶点**；每个在 SCM_RIGHTS cmsg 中携带的 `struct file *` 成为一条有向 **边**（`前驱 → 后继`）。 示例 — 将 A 发送给 C，C 发送给 D，B 发送给 D。三个飞行中套接字（A、B、C — 不包括 D），形成如下图形： ```mermaid graph LR; A[前驱顶点] -->|边 (A->C)| C[后继顶点]; B[前驱顶点] -->|边 (B->D)| D[后继顶点]; C -->|边 (C->D)| D; ``` 然后 Tarjan 算法将该图划分为强连通分量（SCC）。**为什么是 SCC？** 对于任意有向图，任何包含多于一个顶点的 SCC 必然至少包含一个循环： ```mermaid graph LR; A --> B; B --> C; C --> A; ``` 循环是顶点可回收的 **必要但不充分** 条件：回收需要顶点是飞行中的，并且无法从用户空间访问（`file_count == out_degree`）。不在任何循环中的套接字不可能是相互固定的垃圾，会被跳过。 ### `__unix_gc` 如何分派 ```c static void __unix_gc(struct work_struct *work) { struct sk_buff_head hitlist; /* [2] 最终要释放的 skb 命中的列表 */ struct sk_buff *skb; /* ... */ __skb_queue_head_init(&hitlist); /* [2.5] */ if (!unix_graph_maybe_cyclic) { /* [3] 快速退出 */ spin_unlock(&unix_gc_lock); goto skip_gc; } /* ... */ } ``` 每次添加一条两个端点都在飞行中的新边时，`unix_graph_maybe_cyclic` 会被置为真： ```c static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge) { struct unix_vertex *vertex = edge->predecessor->vertex; if (!vertex) { vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry); vertex->index = unix_vertex_unvisited_index; /* ... */ } vertex->out_degree++; list_add_tail(&edge->vertex_entry, &vertex->edges); unix_update_graph(unix_edge_successor(edge)); } static void unix_update_graph(struct unix_vertex *vertex) { /* 如果接收套接字不在飞行中，则不可能形成循环引用。 */ if (!vertex) return; WRITE_ONCE(unix_graph_state, UNIX_GRAPH_MAYBE_CYCLIC); unix_graph_grouped = false; } ``` 注意 `unix_update_graph()` **也** 会将 `unix_graph_grouped = false` 重置，强制下一次 GC 从头重建 SCC。 慢速路径和快速路径之间的分派： ```c if (unix_graph_grouped) unix_walk_scc_fast(&hitlist); else unix_walk_scc(&hitlist); ``` ### 慢速路径 —— `unix_walk_scc()` 这才是实际构建 SCC 的地方： ```c static void unix_walk_scc(struct sk_buff_head *hitlist) { unsigned long last_index = UNIX_VERTEX_INDEX_START; unix_graph_maybe_cyclic = false; unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START; while (!list_empty(&unix_unvisited_vertices)) { struct unix_vertex *vertex; vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); __unix_walk_scc(vertex, &last_index, hitlist); } list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices); swap(unix_vertex_unvisited_index, unix_vertex_grouped_index); unix_graph_grouped = true; } ``` 索引从 `UNIX_VERTEX_INDEX_START == 2` 开始。在遍历开始时，图被 **假定** 为无环；只有当实际发现循环时，遍历才将其恢复为有环。 > **复杂度说明。** 外层的 `while` 只有在图是由不连通的子图组成的 **森林** 时才会多次迭代。对于任何弱连通图 G(V, E)，单次迭代就能访问所有顶点。整体开销为 `O(|V| + |E|)`。 ### Tarjan 算法 Tarjan 算法接受一个有向图并产生其 SCC。每个顶点最终属于唯一一个 SCC；没有入环或出环的顶点形成一个平凡的单一 SCC。其思想是深度优先搜索，每个顶点初始标记为 `(index, scc_index) = (k, k)`，其中 `k` 单调递增，然后邻居的 `scc_index` 值向上传播回栈，使得同一循环中的所有顶点收敛到该循环中最小的 `scc_index`。参见 Wikipedia 页面 (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) 以获取正式描述。 匹配内核原地迭代形式的伪代码： ``` 对于每个未访问的顶点 v： __unix_walk_scc(v, last_index, hitlist) __unix_walk_scc(v, last_index, hitlist): vertex_S, edge_S, edge |------------------------------------| next_vertex: vertex_S.push(v) v.index <- last_index v.scc_index <- last_index last_index += 1 for each edge e: (v, w) in the Graph: // w == e.successor if vertex w is not yet visited: edge_S.push(e: (v, w)) v <- w goto next_vertex |------------------------------| -> prev_vertex: // 从递归返回 edge = edge_S.pop() // 回溯 w <- v v <- edge.predecessor.vertex v.scc_index = min(v.scc_index, w.scc_index) else if w is not in another SCC: v.scc_index = min(v.scc_index, w.scc_index) |-----------------------------------------------| if v.index == v.scc_index: scc <- {} scc_dead <- true // vertex_S == [SCC(0)][SCC(1)][...][SCC(N)] // 将 [v ...] 切分到 `scc` 中 scc <- [v ...] while scc is not empty: u <- scc.pop() unix_visited_vertices.add(u) u.index <- unix_vertex_grouped_index if scc_dead: scc_dead <- unix_vertex_dead(v) if scc_dead: unix_collect_skb(&scc, hitlist) else: if unix_vertex_max_scc_index < v.scc_index: unix_vertex_max_scc_index <- vertex.scc_index if not unix_graph_maybe_cyclic: unix_graph_maybe_cyclic <- unix_scc_cyclic(&scc) |-----------------------------------------------| if edge_stack is not empty goto prev_vertex ``` ### 快速路径 —— `unix_walk_scc_fast()` 当图自上次 GC 以来形状未改变时（`unix_graph_grouped == true`），SCC 被原样重用： ```c static void unix_walk_scc_fast(struct sk_buff_head *hitlist) { unix_graph_maybe_cyclic = false; while (!list_empty(&unix_unvisited_vertices)) { /* [4] */ struct unix_vertex *vertex; struct list_head scc; bool scc_dead = true; vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); list_add(&scc, &vertex->scc_entry); list_for_each_entry_reverse(vertex, &scc, scc_entry) { /* [5] */ list_move_tail(&vertex->entry, &unix_visited_vertices); /* [6] */ if (scc_dead) scc_dead = unix_vertex_dead(vertex); /* [7] */ } if (scc_dead) unix_collect_skb(&scc, hitlist); else if (!unix_graph_maybe_cyclic) unix_graph_maybe_cyclic = unix_scc_cyclic(&scc); list_del(&scc); } list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices); } ``` 快速路径以逆序遍历每个缓存的 SCC（**[5]**），将每个顶点移动到已访问列表（**[6]**），并对它运行 `unix_vertex_dead()`（**[7]**）。如果 SCC 中的每个顶点都通过了检查，则整个 SCC 被追加到命中列表中供清理。 --- ## CVE-2025-40214 — kCTF 条目 ### 补丁 ```diff diff --git a/net/unix/garbage.c b/net/unix/garbage.c index 684ab03137b6c..65396a4e1b07e 100644 --- a/net/unix/garbage.c +++ b/net/unix/garbage.c @@ -145,6 +145,7 @@ enum unix_vertex_index { }; static unsigned long unix_vertex_unvisited_index = UNIX_VERTEX_INDEX_MARK1; +static unsigned long unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START; static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge) { @@ -153,6 +154,7 @@ static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge) if (!vertex) { vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry); vertex->index = unix_vertex_unvisited_index; + vertex->scc_index = ++unix_vertex_max_scc_index; vertex->out_degree = 0; INIT_LIST_HEAD(&vertex->edges); INIT_LIST_HEAD(&vertex->scc_entry); @@ -489,10 +491,15 @@ prev_vertex: scc_dead = unix_vertex_dead(v); } - if (scc_dead) + if (scc_dead) { unix_collect_skb(&scc, hitlist); - else if (!unix_graph_maybe_cyclic) - unix_graph_maybe_cyclic = unix_scc_cyclic(&scc); + } else { + if (unix_vertex_max_scc_index < vertex->scc_index) + unix_vertex_max_scc_index = vertex->scc_index; + + if (!unix_graph_maybe_cyclic) + unix_graph_maybe_cyclic = unix_scc_cyclic(&scc); + } list_del(&scc); } @@ -507,6 +514,7 @@ static void unix_walk_scc(struct sk_buff_head *hitlist) unsigned long last_index = UNIX_VERTEX_INDEX_START; unix_graph_maybe_cyclic = false; + unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START; /* 精确访问每个顶点一次。 * __unix_walk_scc() 将已访问顶点移动到 unix_visited_vertices。 ``` ### 根本原因： `unix_add_edge()` 初始化一个新分配的 `struct unix_vertex` 的 `index`、`out_degree`、`edges` 和 `scc_entry` 字段，但没有初始化 `scc_index`。该字段读取的是之前 slab 占用者写入的内容。快速路径的死 SCC 检查（`unix_vertex_dead()`）比较顶点间 `scc_index` 以决定一条出边是否离开 SCC： ```c if (next_vertex->scc_index != vertex->scc_index) return false; /* 边离开 SCC → 顶点不是死的 */ ``` 如果我们能让一个新分配的顶点继承与一个活跃的、由用户持有的套接字的顶点 **相同** 的 `scc_index` 值，那么死 SCC 检查就会对该活跃套接字返回 `true`，进而清空其接收队列；结果：它携带的每个文件发生逻辑上的释放后使用。 补丁通过单调递增的计数器 `unix_vertex_max_scc_index` 无条件修复此问题，该计数器在每次新的 `unix_add_edge()` 时被分配，确保不会发生意外的别名。 作者描述了他产生该漏洞的策略 (https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=60e6489f8e3b086bd1130ad4450a2c112e863791)： ``` 1) 堆喷塑形 `out_degree` 2) 构建 A→embryo(B) 以及 X→X + 慢速 GC 3) accept(B), B→C, close(A), 快速 GC ``` 通过阅读此文，我设计了另一种策略，仍然非常接近作者的： ``` 1) 仍然进行喷塑 2) B ↔ A (双套接字 SCC → 两者 scc_index=2) 3) A → C 4) C → D close A, close B GC → 快速路径 → A 被错误宣布为死 ``` **阶段 1 - 喷塑顶点** `struct unix_vertex` 在 x86_64 上大小为 **72 字节**，因此它落在 `kmalloc-96` 缓存中。为了使漏洞具有确定性，我们需要该缓存空闲列表的顶部包含一个顶点，其 `scc_index` 字段包含 `UNIX_VERTEX_INDEX_START == 2`。因此，我们构建一个 N(> 1) 个循环 AF_UNIX 套接字的环，关闭所有本地 fd 以触发 GC。慢速遍历访问每个顶点，运行 Tarjan；因为我们的环形成一个 SCC，其中的每个顶点在作为命中列表的一部分被释放之前，都被设置了 `scc_index = 2`。这些顶点 **仍然带有 `scc_index = 2`** 被放回 `kmalloc-96` 空闲列表。 **阶段 2 - `B ↔ A` 循环** 创建循环后，慢速遍历给 A 和 B 都赋了 `scc_index = 2`，且两者都未被释放。`unix_graph_grouped` 翻转为 `true`，快速路径为下一次 GC 就绪。该循环本身是循环的，所以 `unix_graph_maybe_cyclic` 保持为真。这 **消除了** embryo 变体中对 `sk-X → sk-X` 自环的 **需求**。 **阶段 3 - 虚假链，然后关闭并触发** 每次通过一个之前不是前驱的套接字发送时，会在 `unix_add_edge()` 中触发一次新的 `unix_vertex` kmalloc。空闲列表顶部仍然有阶段 1 的残留 `scc_index=2`，所以每个新顶点都读回 `scc_index = 2`。`sk-C` 和 `sk-D` 在发送时不在飞行中，因此 `unix_update_graph(successor)` 对每个都解析为 `NULL`，并且 `unix_graph_grouped` 保持为真。快速路径保持就绪。 `close(skA)` 将其 `file_count` 降低到与 `out_degree` 匹配（死检查的前提条件）。快速路径运行，由于 `sk-A` 合法的 `scc_index=2` 与 `sk-A→sk-C` 边上后继者的新生且残留的 `scc_index=2` 别名，`unix_vertex_dead(sk-A)`