Protocol Buffers upb Arena 融合与单向引用锁-free 生命周期协同设计与源码解析【免费下载链接】protobufProtocol Buffers - Googles 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 与单向 Referenceupb 提供了两种语义不同的生命周期协同原语理解它们的分工是理解整个机制的前提原语方向性线程安全典型用途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——两个根各自带着 refs2 与 refs3 的计数和各自的链表。整个流程在源码_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 并查UnionCAS 原子切换通过 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)) { // Well need to remove the excess refs we added to r1 previously. *ref_delta r2_untagged_count; return NULL; }若 B 的计数在操作期间发生了变化或它被融合到了另一个更低地址的 arenaCAS 会失败整个流程从头再来——失败时把此前多加的引用记入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_RefArenaFusion 建立的是双向依赖融合组内的 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 都是线程安全”的声明;FuzzFuseSpaceAllocatedRacefuse 与 SpaceAllocated 扫描竞争验证弱一致性与单调性;FuzzFuseIncRefCountRace / FuzzFuseIsFusedRace验证IncRefFor/IsFused的并发安全性FuzzRefArenaRace 与 FuzzFuseRefArenaRace验证 RefArena 对to的线程安全RandomRefArena中特意对同一对 arena 排序避免并发调用from侧竞争死亡测试ArenaDeathTest用 death test 验证ArenaRefCycleThroughFuse、ArenaRefCycleThroughMultipleFuses、ArenaRefFuseCycle等场景下环检测断言确实触发覆盖“纯引用环”“引用多次融合混合环”“融合组内引用”三类非法组合。最小可用的融合示例则很简单见 ArenaFuse 测试创建两个 arenaupb_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 为 UBSpaceAllocated的统计是弱一致但单调的。深入阅读建议从 upb/mem/arena.h 的 API 契约出发再对照 upb/mem/arena.c 的实现与 upb/mem/arena_test.cc 的并发测试最后可参考 upb 总体设计文档 了解 arena 在 upb 内存模型中的整体定位。【免费下载链接】protobufProtocol Buffers - Googles data interchange format项目地址: https://gitcode.com/GitHub_Trending/pr/protobuf创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考