Protocol Buffers upb Arena 融合与单向引用：锁-free 生命周期协同设计与源码解析

2026-09-06 21:34:07作者：牧宁李

本文基于 protobuf 仓库中的 upb 设计文档 arena_fusion.md，系统讲解 upb 内存分配器中两个 arena 生命周期协同机制——upb_Arena_Fuse（双向融合）与 upb_Arena_RefArena（单向引用）的设计动机、混合数据结构、lock-free 操作流程与调试期环检测算法，并结合 arena.c 与 arena_test.cc 的源码实现与并发测试用例，帮助读者理解“跨 arena 指针不悬垂”这一问题的完整解决方案。

1. 问题背景：μpb 的线程兼容模型与跨 arena 悬垂指针

upb 是 Protocol Buffers 仓库中一个独立的、面向高性能的 C 语言 runtime（位于 upb/ 目录）。它遵循一条清晰的线程兼容模型：只有对 const 指针的操作才允许从多个线程并发执行；任何非 const 操作不得彼此竞争，也不得与对 const 指针的操作竞争。

在这个模型下，单 arena 内部不存在悬垂指针（所有对象同生共死），但一旦出现“一个 arena 中的消息持有指向另一个 arena 中消息的指针”，问题就来了：先释放的那个 arena 会让对方的指针瞬间悬空。典型场景是：子消息先在独立的 arena 中构造，随后被 set 到父消息上——父 arena 若先被释放，父消息里指向子消息的指针就失效了。

upb 总体设计文档对这一问题的描述是：当存在多个 arena 且彼此有指针引用时，需要一种原语来保证引用不会变成悬垂指针。upb 给出的原语就是 fuse：

// Fuses the lifetimes of `a` and `b`.  None of the blocks from `a` or `b`
// will be freed until both arenas are freed.
UPB_API bool upb_Arena_Fuse(const upb_Arena* a, const upb_Arena* b);

upb_Arena_Fuse 通过把两个 arena 的生命周期绑定在一起，保证所有传递性融合的 arena 引用计数都归零之前，没有任何一个会被释放。这样把父 arena 与子 arena 融合后，子的生命周期就被父“挂住”了，无需复制子消息。设计文档还给出了量化参考：Fuse 是一个相对廉价的操作，量级约为 150ns，且对参与融合的 arena 数量近似 O(1)（真实复杂度是增长极慢的逆 Ackermann 函数）。

2. 两种协同方式：双向 Fusion 与单向 Reference

upb 提供了两种语义不同的生命周期协同原语，理解它们的分工是理解整个机制的前提：

原语	方向性	线程安全	典型用途
`upb_Arena_Fuse(a, b)`	双向、生命周期完全一致	线程安全（lock-free）	父 arena 与子 arena 互相持有指针
`upb_Arena_RefArena(from, to)`	单向，`to` 只需活得比 `from` 长	对 `to` 线程安全，对 `from` 不保证	只有一方持有指向另一方的指针

2.1 Fusion 的并发定位

文档明确指出：修改引用计数和执行 fusion 都是线程安全的。如果需要在多线程场景下“共享同一 arena 生命周期地并发分配”，推荐的做法是：共享一个 const upb_Arena* parent，每个线程再创建自己专属的 arena，然后把线程 arena 与 parent 融合。

与此形成对比的是：单纯的引用计数并不能帮助多线程并发分配，它只解决“多个对象观察同一个 arena 时的生命周期同步”问题——单线程下多个写入者可持有非 const 指针，多线程下多个读者持有 const 指针。

2.2 不可融合的限制：初始块

从源码 upb_Arena_Fuse 可以看到一条重要的实际约束：

// Do not fuse initial blocks since we cannot lifetime extend them.
// Any other fuse scenario is allowed.
if (_upb_ArenaInternal_HasInitialBlock(ai1) ||
    _upb_ArenaInternal_HasInitialBlock(ai2)) {
  return false;
}

如果一个 arena 是用用户提供的初始块（upb_Arena_Init(mem, n, alloc) 中 mem 非空）创建的，它的内存寿命由调用者管理，无法被延长，因此 任何涉及初始块 arena 的跨 arena 融合都会直接返回 false（与自身融合除外）。arena_test.cc 中的 FuseWithInitialBlock 测试正是穷举验证了这一规则。同理，upb_Arena_RefArena 也拒绝给拥有初始块的 arena 增加引用。

3. 核心数据结构：混合 DSF + 双向链表

文档指出，每个 arena 只用三个指针大小的成员来追踪 arena 之间的关系，它们共同实现了一个“混合不相交集合森林（Disjoint Set Forest）+ 双向链表”：

// Tagged pointer - tracked as black arrows in diagrams
UPB_ATOMIC(uintptr_t) parent_or_count;
// Linked list - tracked as red arrows in diagrams
UPB_ATOMIC(struct upb_ArenaInternal*) next;
// Linked list - previous tracked as blue arrows in diagrams, tail as dashed
UPB_ATOMIC(uintptr_t) previous_or_tail;

在源码 upb_ArenaInternal 定义中，这三个成员的完整语义是：

parent_or_count（低 bit 标签指针）：低 bit 为 0 时是父节点指针，低 bit 为 1 时是引用计数（左移 1 位后存储）。根节点存计数，非根存父指针。
next：融合组内单向链表的后继指针，列表以 NULL 结尾。根节点始终是链表头。
previous_or_tail（低 bit 标签指针）：低 bit 为 0 时是前驱节点指针（保证 a->previous_or_tail->next == a）；低 bit 为 1 时是该根节点对其链表尾的缓存（没有融合子节点的根指向自身）。这个尾指针是 best-effort 的——它不保证总是真正的尾部，但保证是列表中的合法节点。

两套结构的分工在文档中写得很清楚：

不相交集合用于判断两个 arena 是否已经融合，并为整个融合组提供一个统一的引用计数；
链表用于在引用计数归零时释放所有成员，以及实现 upb_Arena_SpaceAllocated 的统计遍历。

两者的一致性关系是：以不相交集合的判定为准（根相同即视为已融合）；链表保证在计数归零前一定收敛，但与并发的 fuse 竞争期间可能只追踪融合 arena 的一个子集。

4. 查找根节点：路径分裂（Path Splitting）

一组融合 arena 由其树的根节点唯一标识。查找某 arena 的根，就是沿 parent_or_count 指针向上走，直到遇到一个存的是计数而非父指针的节点——那就是根。

源码实现 _upb_Arena_FindRoot 用路径分裂（path splitting）代替经典路径压缩：每次向上跨越一个节点时，就把当前节点直接挂到它的祖父节点上（upb_Atomic_Store(&ai->parent_or_count, poc, ...)），使每个被遍历节点到根的距离减半。用文档中的例子说明：给定链 A <- B <- C <- D（箭头指父），查询 D 的根时：

第一步：D 的父是 C，把 D 直接指向 C 的父 B——D 到根的距离减半；
第二步：C 的父是 B，把 C 直接指向 B 的父 A——C 也变短了；

若再次查询 D 的根，后续所有查找只需一步。对同一融合组内一批节点的重复查询会很快收敛到 O(1)。实现上还有一个内存序细节：若 arena 本身是根，读计数用 memory_order_relaxed 即可；慢路径（有父节点）则使用 acquire 序重新加载——注释解释在 ARM 上重新加载比 fence 更便宜（LDA vs DMB ISH）。

5. 融合流程详解：六步 lock-free 操作

以融合 C 和 D 为例（等价于融合它们的根 A 和 B——两个根各自带着 refs=2 与 refs=3 的计数和各自的链表）。整个流程在源码 _upb_Arena_DoFuse 与 _upb_Arena_DoFuseArenaLists 中实现，可以拆成文档所述的六个阶段。

5.1 前置：识别根并确定方向

Fusion 首先分别找出两个 arena 的根；若它们已经同根，则无事可做。为了避免环，总是把高地址的根融合进低地址的根（源码中用 (uintptr_t)r1.root > (uintptr_t)r2.root 交换顺序）。

5.2 传递引用计数（Pass refcount）

一旦父节点即将改变，所有后续的计数操作都会切换到新根。为了避免在旧根上仍有活动引用时把新根的计数减到 0，实现先把被合并方（r2）的引用计数加到新根（r1）上：

uintptr_t r2_untagged_count = r2.tagged_count & ~1;
uintptr_t with_r2_refs = r1.tagged_count + r2_untagged_count;
if (!upb_Atomic_CompareExchangeStrong(
        &r1.root->parent_or_count, &r1.tagged_count, with_r2_refs,
        memory_order_release, memory_order_acquire)) {
  return NULL;
}

源码注释解释了为什么要“先加后挂”：把 r1 装为 r2 的父的瞬间，所有竞争中的 free 就立刻可能开始递减 r1 的计数（包括挂起的增量及其 free），因此必须提前把 r2 的引用加进来，让 r1 能够扛住来自 r2 的一切解引用。整个操作过程中传递的总计数被跟踪在 ref_delta 里，如果重试导致过量传递，最后要修正。

5.3 并查（Union）：CAS 原子切换

通过 CAS 把高地址 arena（本例 B）的 parent_or_count 从“计数”换成指向低地址根（A）的指针，原子地消除 B 的引用计数、把它变成 A 的子节点：

if (!upb_Atomic_CompareExchangeStrong(
        &r2.root->parent_or_count, &r2.tagged_count,
        _upb_Arena_TaggedFromPointer(r1.root), memory_order_release,
        memory_order_acquire)) {
  // We'll need to remove the excess refs we added to r1 previously.
  *ref_delta += r2_untagged_count;
  return NULL;
}

若 B 的计数在操作期间发生了变化（或它被融合到了另一个更低地址的 arena），CAS 会失败，整个流程从头再来——失败时把此前多加的引用记入 ref_delta 以便修正。

5.4 引用计数修正（Refcount fixups）

如果 B 的计数在 union 期间发生了变化，就按“最初加进去的计数”与“CAS 时观察到的 B 最终计数”之差，对新根 A 的计数做增减。源码 _upb_Arena_FixupRefs 用一次 relaxed 序的 CAS 完成，注释解释了为什么 relaxed 在此安全：被清理的引用所建立的同步边已由 fuse 操作本身提供，且不存在能与本函数竞争并导致整体归零的合法递减。

5.5 链表融合：从尾节点 CAS 挂接

链表融合的目标是让 A 的尾部指向 B。由于根节点始终是链表头，列表天然无环。实现 _upb_Arena_LinkForward 从 A 的尾指针（previous_or_tail 的 tagged-tail 模式）出发，遍历到真正的尾节点（本例是 C），然后循环 CAS 把该节点的 next 从 NULL 换成 B：

} while (!upb_Atomic_CompareExchangeWeak(  // Replace a NULL next with child.
    &parent_tail->next, &parent_tail_next, child, memory_order_release,
    memory_order_acquire));

完成后 B 从根节点可达（A->C->B->D），最终 free 时能看见它。

5.6 更新尾指针与反向链接

如果停在 5.5，多次连续融合会退化成 O(n²)——每次都要从根遍历整条链表找尾部。因此 _upb_Arena_UpdateParentTail 会把 A 的尾指针更新为 B 侧的尾，使下一次融合不必再遍历 C 和 B。这是 best-effort 操作：并发融合可能已往 B 的列表追加了新节点，尾指针可能指向过期值，但 _upb_Arena_LinkForward 保证最终会找到真尾部。

最后，为了让 upb_Arena_SpaceAllocated 能双向遍历链表，_upb_Arena_LinkBackward 补上双向链表的反向链接：既然 C 已连向 B，就要让 B 的 previous_or_tail 指向 C。此操作把 B 的 previous_or_tail 从 tagged-tail 模式一次性转为 previous 模式，此后值不可变——源码注释论证了这一转换的排他性：只有刚执行完“old_parent_tail->next 从 NULL 变非 NULL”这一独占操作的线程才能执行它。

5.7 顶层入口的重试循环与环检测断言

upb_Arena_Fuse 把上述步骤组织成无限重试循环：

while (true) {
  upb_ArenaInternal* new_root = _upb_Arena_DoFuse(&ai1, &ai2, &ref_delta);
  if (new_root != NULL && _upb_Arena_FixupRefs(new_root, ref_delta)) {
#if UPB_ENABLE_REF_CYCLE_CHECKS
    UPB_ASSERT(!upb_Arena_HasRefChain(a1, a2));
#endif
    return true;
  }
}

任何一步 CAS 失败（返回 NULL）或修正失败都会整体重试，直到融合成功——这正是文档所述“CAS 失败则从头再来”的代码形态。注意融合操作是不可逆的（upb 设计文档明确其 lifetimes 被 irreversibly joined）。

6. 单向引用：`upb_Arena_RefArena`

Fusion 建立的是双向依赖：融合组内的 arena 生命周期完全一致。但很多场景只需要单向依赖——例如 arena A 中的消息持有指向 arena B 中消息的指针，而反向没有。此时只要求 B 至少活得和 A 一样长。

upb_Arena_RefArena(A, B) 让 A 为 B 增加一次引用；A 被释放时解除对 B 的引用。源码实现的方式是：在 A 中分配一个特殊的 upb_ArenaRef 块（其 upb_MemBlock.size 为 0），其中保存指向 B 的指针；这个块被挂入 A 的 block 链表，在 upb_Arena_Free(A) 时被特殊处理。

_upb_Arena_DoFree 展示了释放顺序的保证：释放时逐个遍历 block，遇到 size == 0 的块就识别为 arena ref，先调用 upb_Arena_DecRefFor 解除对目标 arena 的引用，之后才轮到含这些块的内存块本身被底层 allocator 释放——确保引用块在被释放前一定先于其所在的内存块被处理。

线程安全性上，文档特别强调：upb_Arena_RefArena(A, B) 在与其他针对 A 的操作并发时不是线程安全的（from 参数是 non-const 的，会读写 A 的 block 链表），但对 B 是线程安全的。这一点在 arena.h 的 API 文档中也有对应说明。

6.1 循环引用是错误

文档列出了两类非法用法：

创建引用环，例如 RefArena(A, B); RefArena(B, A)；
在已融合的 arena 之间创建引用。因为 fusion 是双向依赖，Fuse(A, B) 之后再 RefArena(B, A) 会形成 A <-> B -> A 的环。

arena.h 的注释进一步给出了更一般的形式：

// 以下调用序列创建了环 A -> B -> C -> A（不允许）
Fuse(A, B);
Ref(B, C);
Ref(C, A);

并解释 fuse 本身虽可参与“环”，但双向融合不构成环、能被正确回收——所以“禁止融合组内引用”其实是“禁止引用环”这一规则的特例。这些条件在 debug 构建中会被检查（见第 8 节），在 release 构建中属于未定义行为。

7. 统计已分配空间：`upb_Arena_SpaceAllocated`

在 arena 仍存活时遍历链表是有难度的：从根出发不一定能到达自己的节点（并发的 fuse 可能正在进行）。upb_Arena_SpaceAllocated 的解法是从调用者给定的节点出发，沿 previous_or_tail 先向后走、再沿 next 向前走，双向扫描：

这使空间统计是弱一致性的：可能看见 A 和 B 已融合，但在连接它们的 fuse 操作仍在进行期间，SpaceAllocated(B) 看不见 A 的空间；
但统计永远与自身一致，也与所有已完成的 fuse 一致——节点只会被追加或前插到链表中，因此每次从同一点出发的扫描，结果必然是前一次结果的超集（单调不减）；
被引用（RefArena）的 arena 不计入融合组的空间统计，它们只是独立的节点。

源码中的注释同样点明了向后遍历的动机：“our root would get updated by any racing fuses before our target arena became reachable from the root via the linked list; ... we instead iterate forwards and backwards so that we only see the results of completed fuses.”

8. 调试期引用环检测：DFS 算法

为防止“不可回收的 arena”造成的内存泄漏，upb 在 debug 构建（UPB_ENABLE_REF_CYCLE_CHECKS）下，每次创建引用或融合之后运行环检测。环可以由纯引用构成（如 A->B->A），也可以由引用加融合组合而成（如 Fuse(A, B) 后 RefArena(B, A) 构成 A<->B->A）。

8.1 为什么必须在操作之后检查

环检测无法原子地执行。若在融合/引用之前检查，两个并发操作可能各自检查都发现无环、然后各自推进，最终拼出一个环。因此检查放在操作完成之后——此时环若存在就一定能被观测到，debug 下触发断言失败。

以引用链 A->B->C 为例：

若执行 RefArena(C, A)：先添加 C->A 引用，然后检查 C 是否可从 A 到达；遍历发现 A -> B -> C，断言失败；
若执行 Fuse(A, C)：融合发生，遍历发现 C <-> A -> B -> C（融合边可双向穿过），断言失败。

8.2 算法细节

文档描述的检测算法是一个不做记忆化的递归深度优先搜索（DFS）：路径可以双向穿过融合边、单向穿过引用边，目标是找到一条至少包含一条有向边的环。它不是渐近最优的（同一批节点可能被反复遍历），但不分配内存，作为 debug-only 检查足够无侵入。另一个可接受的代价：若环在一个线程上形成、而另一个线程正在做环检查，DFS 可能无限递归——但这种情况本来也会导致断言失败。

具体分三步（对应源码 upb_Arena_HasRefChain）：

融合快速检查：若新加的有向引用的 from 与 to 已经融合（upb_Arena_IsFused(from, to) 为 true），则它们互相可达，包含有向边的路径必然存在，直接断言失败。源码第一行 if (upb_Arena_IsFused(from, to)) return true; 即此优化。
定位融合组成员：要检查 from 融合组的所有出边引用，必须访问与 from 融合的每个 arena。由于融合操作可能与检查竞争，不能依赖从（可能变化的）融合根出发。做法与 SpaceAllocated 相同：先用 previous_or_tail 向后遍历到链表段起点，再向前遍历。
沿组前扫 + 引用 DFS：从段头沿 next 遍历融合组的每个成员 X，检查 X 的所有出边引用 X -> Y：若 Y == to，路径存在，返回 true；否则对 Y 递归继续 DFS，递归返回 true 则 to 经 Y 可达。穷举所有成员及其传递引用后仍未找到路径，返回 false。

该函数的递归形态直接体现在源码中：ref->arena == to || upb_Arena_HasRefChain(ref->arena, to)。RefArena 与 Fuse 两个入口在操作完成后分别调用 UPB_ASSERT(!upb_Arena_HasRefChain(to, from))（注意参数方向）与 UPB_ASSERT(!upb_Arena_HasRefChain(a1, a2)) 来拦截环。

9. 正确性验证：源码中的并发测试矩阵

arena_test.cc 用共享内存的 Environment + 随机操作池对这套 lock-free 机制做了密集的并发压力测试，是理解“哪些操作允许并发”的直接证据：

FuzzFuseFreeRace：随机 fuse 与随机 new/free 竞争；
FuzzFuseFuseRace：多线程并发随机 fuse（对应文档“修改计数与 fuse 都是线程安全”的声明）;
FuzzFuseSpaceAllocatedRace：fuse 与 SpaceAllocated 扫描竞争，验证弱一致性与单调性;
FuzzFuseIncRefCountRace / FuzzFuseIsFusedRace：验证 IncRefFor/IsFused 的并发安全性；
FuzzRefArenaRace 与 FuzzFuseRefArenaRace：验证 RefArena 对 to 的线程安全（RandomRefArena 中特意对同一对 arena 排序，避免并发调用 from 侧竞争）；
死亡测试（ArenaDeathTest）：用 death test 验证 ArenaRefCycleThroughFuse、ArenaRefCycleThroughMultipleFuses、ArenaRefFuseCycle 等场景下环检测断言确实触发，覆盖“纯引用环”“引用+多次融合混合环”“融合组内引用”三类非法组合。

最小可用的融合示例则很简单，见 ArenaFuse 测试：创建两个 arena，upb_Arena_Fuse(arena1, arena2) 成功后，两次 upb_Arena_Free 中只有最后那次真正释放全部内存。

10. 小结与实践要点

语义层面：upb_Arena_Fuse 建立双向、不可逆、生命周期完全一致的关系，解决跨 arena 指针悬垂；upb_Arena_RefArena 建立单向“至少活一样长”的关系，实现成本更低（一次 arena 内分配 + 一次引用计数递增）。选择依据是指针方向：双向互指用 fuse，单向指向用 ref。
并发层面：引用计数操作与 fuse 完全 lock-free 且线程安全；RefArena 只保证 to 侧安全，from 侧必须无竞争；多线程共享生命周期推荐的模式是“const 父 arena + 每线程专属 arena 再 fuse”。
实现层面：三个指针大小的原子成员（标签化 parent_or_count、next、previous_or_tail）同时承载 DSF 与双向链表；路径分裂让根查找快速收敛；低地址根作为合并方向、先加引用后 CAS 换父、失败整体重试，共同构成无锁正确性；尾指针缓存把连续融合从 O(n²) 拉回摊还常数。
使用约束：带初始块的 arena 不能参与融合或作为 ref 的目标；引用环与融合组内引用是错误（debug 断言，release 为 UB）；SpaceAllocated 的统计是弱一致但单调的。