← 返回信息流
AI 资讯Hacker News·3 小时前

Unix GC Remastered

AI 深度解读

Unix GC Remastered：Linux 内核 AF_UNIX 垃圾回收机制的深度重构

背景

在 Linux 内核中，AF_UNIX（Unix 域套接字）子系统包含一个独特的垃圾回收（Garbage Collection, GC）机制。这一机制的存在源于 Unix 域套接字的一项特殊能力：通过 SCM_RIGHTS 控制消息（Control Message）在内核态传递文件描述符（fd）。

通常情况下，用户空间通过文件描述符持有对内核对象（如 socket）的引用。然而，当 socket 通过 SCM_RIGHTS 发送时，如果发送方关闭了 socket，而接收方尚未接收或处理该 fd，或者双方都关闭了 socket，就会出现一种“幽灵”状态：内核中仍保留着 socket 的结构体（struct file），但用户空间已经没有任何句柄可以访问它。如果不进行清理，这些孤立的内核对象会持续占用内存，导致内存泄漏。

为了解决这个问题，内核引入了 AF_UNIX 垃圾回收器。近期，该子系统经历了一次彻底的重写，从传统的遍历算法转向基于图论和强连通分量（Strongly-Connected-Components, SCC）的新模型。尽管新模型旨在提高效率和安全性，但本文指出其实现中仍存在潜在的 Use-After-Free（释放后使用）漏洞风险。

核心内容

1. 垃圾回收的触发与基本逻辑

AF_UNIX 的垃圾回收入口点是 unix_gc() 函数，它通过工作队列（workqueue）异步执行实际的清理工作 __unix_gc()。

触发条件： GC 主要在以下两种情况下被触发：

  1. Inflight 数量过多：当处于“飞行中”（inflight）状态的 socket 数量超过阈值 UNIX_INFLIGHT_TRIGGER_GC（默认为 16000）时。
  2. Socket 关闭：当某个 socket 被关闭，且当前存在任何 inflight 状态的 socket 时。

核心数据结构： 关键的结构体是 struct unix_sock，其中字段 inflight 至关重要。

  • Inflight 的定义：当一个 socket 的 struct file * 作为 SCM_RIGHTS 的载荷在进程间传递时，该 socket 被视为“inflight”。
  • 计数机制：每次发送 socket，inflight 计数加 1；每次接收并确认，计数减 1。内核还维护一个全局计数器 unix_tot_inflight。
  • GC 目标：GC 寻找那些 file_count == inflight 的 socket。这意味着除了被其他 socket 的接收队列捕获的引用外，没有任何用户空间句柄能再触及该 socket。这些就是需要被回收的“垃圾”。

2. 旧版 GC 的局限性

在 2024 年之前的旧版实现中，GC 算法直接遍历 inflight 图，标记循环，并检查 inflight != refcount 来决定是否收集。

  • 缺点：旧实现需要锁定每个 inflight socket 的接收队列，这会导致严重的性能开销和锁竞争。此外，该算法在 Android 等环境中曾引发过安全漏洞（如 2021 年的利用案例）。

3. 新版 GC 的设计哲学

新版 GC 的核心目标是最小化锁的影响并提高轻量级效率。

  • 图表示法：每个 inflight socket 成为图中的一个顶点（Vertex）；每个通过 SCM_RIGHTS 传递的 struct file * 成为一条有向边（Edge，从发送者指向接收者）。
  • 惰性更新：只有当图中存在循环引用时，GC 才需要执行复杂的清理工作。如果没有循环，或者图的结构没有更新，GC 可以快速跳过。

4. 新算法：基于 Tarjan 算法的强连通分量（SCC）

新版 GC 使用 Tarjan 算法将 inflight 图划分为强连通分量（SCCs）。

  • 为什么使用 SCC？

    • 在有向图中，任何包含多个顶点的 SCC 必然包含至少一个循环。
    • 循环是收集的必要条件，但不是充分条件。收集还需要满足顶点是 inflight 且不可达用户空间。
    • 不在任何循环中的 socket 不可能形成相互锁定的垃圾，因此可以直接跳过。

  • 执行流程：

    1. 快速路径（Fast Path）：如果全局标志 unix_graph_grouped 为真，说明图的结构上次已分组且未变化，直接复用之前的 SCC 结果。
    2. 慢速路径（Slow Path）：如果 unix_graph_grouped 为假（例如新边加入导致图结构变化），则重新运行 Tarjan 算法构建 SCC。
    3. 图状态管理：
      • unix_graph_maybe_cyclic：当新边的两个端点都处于 inflight 状态时，标记为可能循环。
      • unix_update_graph()：当新边加入时，重置 unix_graph_grouped = false，强制下次 GC 重新计算。

  • Tarjan 算法简述： 该算法通过深度优先搜索（DFS）遍历图。每个顶点被赋予单调递增的索引 (index, scc_index)。通过回溯时传播 scc_index 值，循环中的所有顶点最终会收敛于该循环中最小的 scc_index。最终，每个顶点恰好属于一个 SCC。

  • 复杂度： 端到端的时间复杂度为 $O(|V| + |E|)$，其中 $V$ 是顶点数，$E$ 是边数。对于弱连通图，单次迭代即可访问所有顶点。

5. 潜在漏洞：Use-After-Free

尽管新算法在逻辑上更清晰，但文章指出其在实际内核实现中仍存在 bug-prone（易出错）的问题。特别是在处理 hitlist（待释放的 sk_buff 列表）和标记 socket 为 dead 的过程中，如果并发处理不当，可能导致在释放内存后仍被引用，从而引发 Use-After-Free 漏洞。

关键要点

  • 问题根源：Unix 域套接字通过 SCM_RIGHTS 传递 fd 时，若用户空间失去引用但内核仍持有，需 GC 机制防止内存泄漏。
  • 旧版缺陷：旧 GC 需锁定每个 socket 的接收队列，性能差且存在已知安全漏洞。
  • 新版核心：引入基于图的模型，使用 Tarjan 算法计算强连通分量（SCC），仅对存在循环引用的 socket 进行回收。
  • 性能优化：
    • 通过 unix_graph_maybe_cyclic 和 unix_graph_grouped 标志位实现快速跳过。
    • 避免在每次 GC 时锁定所有 socket 队列，减少锁竞争。
  • 算法复杂度：新算法的时间复杂度为线性 $O(|V| + |E|)$，效率显著优于旧版。
  • 安全风险：尽管算法改进，但内核实现的复杂性仍可能导致 Use-After-Free 等内存安全漏洞，需仔细审查并发逻辑。

意义与影响

  1. 内核性能提升：新 GC 机制通过减少锁竞争和引入快速路径，显著降低了 AF_UNIX 套接字在高频 fd 传递场景下的开销，提升了系统整体性能。
  2. 安全性增强：通过更精确的图分析，新算法能够更准确地识别和回收孤儿 socket，减少因内存泄漏导致的系统不稳定。同时，对旧版已知漏洞的修复提升了内核的安全性。
  3. 内核开发范式：此次重写展示了 Linux 内核从简单启发式算法向更严谨的图论算法演进的趋势。这种基于 SCC 的方法为其他内核子系统的资源管理提供了参考。
  4. 持续的安全挑战：文章指出的 Use-After-Free 风险提醒开发者，即使算法设计正确，内核并发编程的复杂性仍极易引入漏洞。这强调了内核代码审计和形式化验证的重要性。

总之，AF_UNIX GC 的重写是

相关推荐

查看原文 →mohandacherir.github.io