企业官网建设流程全解析

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

【免费下载链接】protobufProtocol Buffers - Google's data interchange format项目地址: https://gitcode.com/GitHub_Trending/pr/protobuf

本文基于 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 提供了两种语义不同的生命周期协同原语，理解它们的分工是理解整个机制的前提：

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 的——它不保证总是真正的尾部，但保证是列表中的合法节点。

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

1. 不相交集合用于判断两个 arena 是否已经融合，并为整个融合组提供一个统一的引用计数；
2. 链表用于在引用计数归零时释放所有成员，以及实现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 的根时：

1. 第一步：D 的父是 C，把 D 直接指向 C 的父 B——D 到根的距离减半；
2. 第二步：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）：

1. 融合快速检查：若新加的有向引用的from与to已经融合（upb_Arena_IsFused(from, to)为 true），则它们互相可达，包含有向边的路径必然存在，直接断言失败。源码第一行if (upb_Arena_IsFused(from, to)) return true;即此优化。
2. 定位融合组成员：要检查from融合组的所有出边引用，必须访问与from融合的每个 arena。由于融合操作可能与检查竞争，不能依赖从（可能变化的）融合根出发。做法与SpaceAllocated相同：先用previous_or_tail向后遍历到链表段起点，再向前遍历。
3. 沿组前扫 + 引用 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的统计是弱一致但单调的。

深入阅读建议从 upb/mem/arena.h 的 API 契约出发，再对照 upb/mem/arena.c 的实现与 upb/mem/arena_test.cc 的并发测试，最后可参考 upb 总体设计文档 了解 arena 在 upb 内存模型中的整体定位。

【免费下载链接】protobufProtocol Buffers - Google's data interchange format项目地址: https://gitcode.com/GitHub_Trending/pr/protobuf