Perfetto LockFreeTaskRunner 设计解析基于 Slab 的无锁 MPSC 任务执行引擎【免费下载链接】perfettoProduction-grade client-side tracing, profiling, and analysis for complex software systems.项目地址: https://gitcode.com/GitHub_Trending/pe/perfetto导读本文围绕 Perfetto 仓库中的设计文档 lock-free-task-runner.md 展开深入剖析支撑 Perfetto SDK 与设备端服务大部分代码的无锁任务执行引擎base::LockFreeTaskRunner。你将理解它如何在多生产者单消费者MPSC模型下用 Slab 链表 位图实现免锁投递与消费、如何通过 32 个引用计数桶解决棘手的 slab 删除竞态以及它与旧版UnixTaskRunner的兼容性与性能差异。读完本文你可以直接对照 lock_free_task_runner.h 与 lock_free_task_runner.cc 读懂其全部实现细节并为自研无锁队列提供可借鉴的设计范式。一、概述一个跨平台的无锁任务执行引擎base::LockFreeTaskRunner是 Perfetto 核心基础设施之一其头文件位于 include/perfetto/ext/base/lock_free_task_runner.h实现位于 src/base/lock_free_task_runner.cc。它是一个跨平台的**多生产者单消费者Multi-Producer Single-Consumer, MPSC**任务执行引擎允许多个线程安全地调用PostTask()投递任务所有任务都固定由一个指定线程在Run()循环中执行通过精心设计的无锁协议彻底摆脱传统互斥锁mutex同步。它支撑了 Perfetto 的绝大部分代码——无论是 SDK 侧还是设备端 tracing 服务其地位相当于整个项目的事件循环心脏。核心特性原设计文档明确列出如下关键性质无锁、无自旋PostTask()和Run()的时间复杂度有界不使用任何 mutex 或 spinlock极少分配在没有突发即同时未消费任务不超过 2 × 512 1024 个的情况下除了拷贝非平凡的std::functionvoid()所需的分配外不执行任何堆分配顺序兼容与旧版UnixTaskRunner行为兼容任务按相同顺序被取出并执行。相对旧版约 2 倍提速设计文档给出了仓库内基准测试的输出使用perfetto_benchmarks目标见 task_runner_benchmark.cc$ out/rel/perfetto_benchmarks --benchmark_filter.*BM_TaskRunner.* ... ------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------------------------- BM_TaskRunner_SingleThreadedUnixTaskRunner 27778190 ns 27772029 ns 25 BM_TaskRunner_SingleThreadedLockFreeTaskRunner 10381056 ns 10375656 ns 67 BM_TaskRunner_MultiThreadedUnixTaskRunner 567794 ns 344625 ns 2033 BM_TaskRunner_MultiThreadedLockFreeTaskRunner 265943 ns 265754 ns 2749可以看到在单线程场景下LockFreeTaskRunner约为旧版的 2.7 倍多线程场景8 线程竞争投递也约为 2.1 倍。在代码库中的接入方式LockFreeTaskRunner与UnixTaskRunner共同实现 include/perfetto/base/task_runner.h 中定义的TaskRunner抽象接口PostTask(std::functionvoid())投递立即任务PostDelayedTask(std::functionvoid(), uint32_t delay_ms)投递延迟任务AddFileDescriptorWatch(PlatformHandle, std::functionvoid())/RemoveFileDescriptorWatch(PlatformHandle)注册/注销文件描述符Windows 上是句柄监听RunsTasksOnCurrentThread()判断当前线程是否为任务执行线程。值得注意的一个接入细节头文件末尾定义了条件类型MaybeLockFreeTaskRunnerlock_free_task_runner.h由构建标志USE_LOCKFREE_TASKRUNNER决定实际使用哪一个实现using MaybeLockFreeTaskRunner std::conditional_tPERFETTO_FLAGS(USE_LOCKFREE_TASKRUNNER), LockFreeTaskRunner, UnixTaskRunner;该别名被 thread_task_runner.cc 等上层代码直接使用也就是说上层业务代码无需改动即可在两种实现间切换。像src/traced/service/service.cc、src/traced/probes/probes.cc、src/profiling/memory/heapprofd.cc等设备端服务均通过这一机制接入。二、架构术语与整体设计Writer 与 Reader为便于讨论设计文档将参与线程分为两类Writers调用PostTask()的 N 个线程Reader在Run()循环中执行任务的唯一线程即主线程。设计文档特别说明本文只讨论PostTask()的无锁设计PostDelayedTask()与Add/RemoveFileDescriptorWatch()的逻辑与旧版UnixTaskRunner完全一致——它们先跳跃到任务线程上再在主线程操作延迟任务表和 FD 集合。从其他线程调用时这多了一次跳跃hop但设计文档指出(1) 实践中这些调用绝大多数发生在主线程(2) 它们几乎从不位于热点路径上因此代价可接受。Slab 链表MPSC 队列的核心LockFreeTaskRunner采用基于 Slab 的 MPSC 队列。每个 Slab 包含以下组成部分对应 lock_free_task_runner.h 中Slab结构体的字段成员类型访问者作用tasks[]固定 512 槽的任务数组kSlabSizeWriter 写Reader 在对应位图位置位后读存放std::functionvoid()next_task_slotstd::atomicsize_t仅 Writer原子计数器用于预留槽位slab 满时可能超过kSlabSize此时值已无意义tasks_written[]std::arraystd::atomicBitWord, kNumWords512 位发布位图Writer 原子释放-或置位Reader 读标记第 i 槽任务已就绪可消费最终全 1 并保持tasks_read[]非原子的BitWord数组512 位消费位图仅 Reader标记任务已被消费最终也全 1prevSlab*仅 Reader 遍历Writer 仅在建新 Slab 时写入指向链表中的前一个 Slab其中位图每个 word 为sizeof(size_t) * 8位kNumWords kSlabSize / kBitsPerWord64 位平台下即 8 个 word。Slabs 通过prev指针组成单向链表。关键点是这个链表本身不是原子的只有tail_指针是原子的。Reader 是唯一遍历链表者Writer 只访问最新的tailSlab并在需要时追加新 Slab、替换tail_。设计文档给出了链表结构示意tail_ (atomic_shared_ptr) | ▼ ----------------- ----------------- ----------------- | Slab N | | Slab N-1 | | Slab 0 | | tasks: [....] | | tasks: [....] | | tasks: [....] | | next_task_slot | | next_task_slot | | next_task_slot | | prev (sptr) ---------| prev (sptr) ---------| prev nullptr | ----------------- ----------------- -----------------注头文件中的tail_实际类型是std::atomicSlab*而非 atomic shared_ptr原文档示意图保留了早期中间设计的表述从当前源码看引用计数方案已改为下文所述的 32 桶计数见 lock_free_task_runner.h。该设计遵循三条原则单向访问生产者线程只访问 tail Slab绝不回头遍历消费者独占只有主线程沿prev指针回溯并排空任务突发处理当前 Slab 满时由 Writer 自动分配新 Slab。在名义条件下没有数千任务的突发系统中通常只存在两个 Slab。大小为 1 的空闲链表free_slab_避免了对分配器的压力——两个 Slab 在new/delete之间反复切换复用详见 lock_free_task_runner.cc 的AllocNewSlab()/DeleteSlab()。设计权衡O(N) 回溯只保留 tail 指针的单向链表意味着 Reader 的最坏复杂度为 O(N)——它必须遍历整个链表才能拿到最早的任务保证 FIFO。但实践中几乎始终只有两个 Slab如果队列里积压了 1 万10 万个任务遍历链表反而是最不值得担心的问题。该设计的主要妥协是任务数量大时扩展性差因为Run()既变慢遍历链表又更吃栈用递归而非堆来走链表。设计文档注明Perfetto 预期不会有大量积压任务已知的例外如 b/330580374 应被独立修复。三、生产者工作流PostTask() 的无锁协议PostTask()的完整实现见 lock_free_task_runner.cc遵循以下协议加载 tail原子加载当前tail_Slab 指针获取引用计数为该 Slab 递增一个引用计数桶详见第五节预留槽位原子递增next_task_slot获得一个槽位序号处理溢出若 Slab 已满分配新 Slab 并尝试原子更新tail_写入任务把任务写入预留的槽位发布以 release 语义在tasks_written位图中置位使任务对 Reader 可见释放引用计数ScopedRefcount析构时自动递减。其中第 2 步有一个容易被忽略的重要细节递增引用计数后代码会再次加载tail_并比对若发现已经不是同一个 Slab则说明该 Slab 可能在 load 与 refcount 递增之间被 Reader 删除Reader 的 refcount0 检查可能早于我们的递增发生此时直接continue重试。在 seq_cst 顺序下任何后续替换tail_的 CAS 都发生在这次二次 load 之后因此 Reader 之后的引用计数检查必然观察到我们的递增——这是无锁正确性的关键一环。溢出处理当slot kSlabSize时对应实现中的三种情形slot kSlabSize是常见溢出slot kSlabSize是两个以上线程竞争导致的罕见情形设计文档给出了核心代码Slab* new_slab AllocNewSlab(); new_slab-prev slab; new_slab-next_task_slot.store(1, std::memory_order_relaxed); slot 0; if (!tail_.compare_exchange_strong(slab, new_slab)) { // Another thread won the race, retry with their slab new_slab-prev nullptr; DeleteSlab(new_slab); continue; }这与 lock_free_task_runner.cc 的实现逐行对应CAS 失败的线程把新 Slab 的prev置空并归还空闲链表然后重试CAS 成功的线程把新 Slab 的next_task_slot预置为 1因为它自身占用第 0 槽再把scoped_refcount重新绑定到新 Slab 上。另外PostTask()入口有一个PERFETTO_CHECK(closure)断言lock_free_task_runner.cc不允许投递空的std::function因为PopTaskRecursive()以std::function的空性作为退出判据。四、消费者工作流Run() 主循环与任务消费Run() 循环结构主线程的Run()lock_free_task_runner.cc每轮迭代执行任务排空PopNextImmediateTask()取出一个立即任务延迟任务处理PopNextExpiredDelayedTask()取出一个已到期延迟任务FD 轮询以带公平性约束的方式处理 I/O 事件任务执行在 watchdog 保护下运行任务。当前设计每执行一个任务就调用一次poll()有任务时poll_timeout_ms 0。设计文档指出这是可优化的若已知存在任务突发可以背靠背地连续执行任务而省去零超时 poll 的 syscall 开销——但这需要设置上限以防止活锁例如一个设计糟糕的函数不断自我重投递直到某个 socket 收到数据才触发 FD watch。然而设计文档也坦言多年来的测试已经对旧版UnixTaskRunner的严格公平性产生了依赖——测试期望通过IsIdleForTesting()判断事件地平线上是否存在即将到来的 FD watch。正如 Hyrum 定律所示这已成为 TaskRunner 的隐式 API在大量测试被重写并去 flake 之前必须维持。Run()中的 TODO 注释lock_free_task_runner.cc也印证了这一点TestTaskRunner.RunUntilIdle()的微妙语义被测试依赖贸然优化会破坏它们。任务消费算法PopTaskRecursive()PopTaskRecursive()lock_free_task_runner.cc实现消费逻辑递归回溯沿prev指针递归回到最老的 Slab名义条件下通常只回退一个 Slab保证 FIFO 顺序位图扫描对每个 word读取tasks_writtenacquire 语义并与tasks_read取反做 AND得到未消费位unread_word wr_word ~rd_word用CountTrailZeros找到第一个未消费的槽位消费std::move取出任务、槽位置空并在tasks_read中置位安全删除若整个 Slab 的写位图与读位图均已填满且它不是 tailnext_slab非空且对应引用计数桶为 0则将其从链表中摘除并归还。设计文档给出的伪代码std::functionvoid() PopTaskRecursive(Slab* slab, Slab* next_slab) { // First, recursively check older slabs (FIFO ordering) Slab* prev slab-prev; if (prev) { auto task PopTaskRecursive(prev, slab); if (task) return task; } // Then check current slab for published tasks for (size_t w 0; w Slab::kNumWords; w) { BitWord wr_word slab-tasks_written[w].load(std::memory_order_acquire); BitWord rd_word slab-tasks_read[w]; BitWord unread_word wr_word ~rd_word; // Find and consume first unread task... } // Safe slab deletion logic... }删除逻辑在实现中表现为lock_free_task_runner.ccbool slab_fully_consumed words_fully_consumed Slab::kNumWords; const uint32_t bucket HashSlabPtr(slab); if (slab_fully_consumed next_slab refcounts_[bucket].load() 0) { PERFETTO_DCHECK(next_slab-prev slab); next_slab-prev slab-prev; slab-prev nullptr; DeleteSlab(slab); }Quit() 与跨线程退出Quit()lock_free_task_runner.cc必须通过PostTask跳跃到主线程执行避免另一线程写quit_true后主线程立即销毁自身而该线程再调用WakeUp()访问已销毁对象的竞态。Run()退出前还有一个值得注意的收尾循环lock_free_task_runner.cc它会自旋等待所有引用计数桶归零。原因是一个典型的测试竞态线程 1 调用Quit()变为 PostTask主线程看到quit_true返回并销毁 LFTR而线程 1 还在执行 PostTask 的收尾、递减引用计数从而访问已失效内存。五、引用计数系统一个精妙的 Slab 删除竞态竞态的本质表面上看Writer 只访问 tail Slab、绝不回走链表的访问模式大幅简化了同步需求。但设计文档指出一个必须解决的微妙竞态初始条件任务运行器只有一个 Slab S0 且恰好已满tail_ - S0 (full) - nullptr。竞态推演线程 A 读取tail_得到 S0 的地址但在执行原子递增next_task_slot该操作会揭示 Slab 已满之前被抢占挂起slab tail_.load(); // Pre-emption happens here slab-next_task_slot.fetch_add(1); ...线程 B 做同样的事但未被抢占它读到 S0、发现已满、分配新 Slab S1 并替换 tail此时tail_ - S1 - S0 - nullptrRun()线程开始循环发现有两个 Slab注意到 S0 已满、不是 tail于是判定它可以安全删除此时线程 A 恢复执行尝试递增已被删除的 S0 的next_task_slot——use-after-free。根因删除非 tail Slab 本身是安全的Writer 不遍历链表但某个线程可能在该 Slab 还是 tail 时观察到了它而 Reader 无从得知这一点。因此给 Slab 自身加引用计数或其他属性是无济于事的——它解决不了Slab 可能已经消失这一核心问题缓解措施必须在 Slab 之外实施。为什么不用 atomic shared_ptr在 LockFreeTaskRunner 的中间设计中曾用shared_ptrSlab来缓解此问题。非侵入式的 STLshared_ptr通过一个中间控制块把 Slab 与引用计数解耦。然而设计文档明确指出libcxx 对 shared_ptr 的原子访问器在不同线程间交换shared_ptrSlab tail_所必需的是用一个 32 个 mutex 的哈希池实现的参见__get_sp_mut这实际上违背了无锁的初衷。最初的简化缓解方案一个直观的简化方案是每个 Writer 在开始 PostTask 前递增全局引用计数如task_runner.num_writers_active结束后递减。这样 Reader 能随时知道是否有 Writer 处于活跃状态。Reader 侧若num_writers_active 0则跳过删除、留待下一个任务再试。注意这不是 mutex 也不是 spinlock因为没有人等待别人。其正确性建立在如下原则上Writer 只能通过tail_指针观察 SlabReader 只删除非 tail Slab因此它知道tail_指向的并非正在删除的 Slab若没有 Writer 活跃就没有人观察过任何 Slab更不可能观察过被删除的 Slab若某 Writer 在num_writers_active 0检查之后立即活跃在顺序一致性下它必然观察到新的 tail Slab不可能观察到正在被删除的旧 Slab。这个方案能解决竞态但暴露了新问题如果某个 Writer 线程恰好在Run()每次检查时都在投递任务Slab 就永远无法被删除。设计文档认为该场景极不现实——若 Writer 永远活跃假设任务执行时间大于 PostTask 调用时间任务运行器大概率早就被撑爆了。当前方案32 个引用计数桶 哈希映射理想方案是每个 Slab 一个引用计数但如前所述引用计数不能放在 Slab 上它正是用于把关对 Slab 的访问。放在任务运行器中的mapSlab*, atomicint又会造成堆抖动且需要无锁 map。最终采用折中方案固定 32 个引用计数桶通过哈希函数把每个 Slab 映射到一个桶。两个 Slab 可能哈希到同一桶产生假阳性——某 Slab 明明没被引用却因哈希冲突被误判为有引用。但假阳性在此场景下无害最坏情况退化为上述简化方案而它在竞态视角下依然是正确的。实践上这相当于把推迟删除 Slab的概率降低了 32 倍。这正是 lock_free_task_runner.h 中LockFreeTaskRunner::refcounts_std::arraystd::atomicint32_t, kNumRefcountBuckets以及 Writer 使用的ScopedRefcount类所支撑的逻辑。kNumRefcountBuckets 32在头文件的task_runner_internal命名空间中作为常量暴露给测试使用。哈希函数采用SplitMix64lock_free_task_runner.h先清除 ASAN/MTE 的 tag 字节再混合对指针分布非常快速有效static uint32_t HashSlabPtr(Slab* slab) { uint64_t u reinterpret_castuintptr_t(slab); u 0x00FFFFFFFFFFFFFFull; // Clear asan/MTE top byte for tagged pointers. u 0x9E3779B97F4A7C15ull; u (u ^ (u 30)) * 0xBF58476D1CE4E5B9ull; u (u ^ (u 27)) * 0x94D049BB133111EBull; return static_castuint32_t((u ^ (u 31)) % kNumRefcountBuckets); }ScopedRefcountlock_free_task_runner.h在构造时对桶执行fetch_add(1)并在析构时fetch_sub(1)支持移动语义以在溢出路径中把引用从旧 Slab 转移到新 Slab。六、延迟任务处理FlatSet 反向排序延迟任务使用独立的FlatSetDelayedTask容器头文件中DelayedTask定义见 lock_free_task_runner.h维护排序需要一定开销实践中延迟任务通常只有个位数主要用于超时但避免了大多数情况下的分配——FlatSet基于 vector仅在需要扩容时才分配。DelayedTask的operator采用反向排序时间更晚的排前面、更早的排后面这样Run()只需 O(1) 的pop_back()即可取出最早到期的任务lock_free_task_runner.cc相当于用 vector 实现 FIFO 队列。跨线程调用PostDelayedTask()时同样先PostTask跳跃到主线程lock_free_task_runner.cc并借助next_delayed_task_seq_序列号保证同一时间戳下任务的稳定顺序。GetDelayMsToNextTask()返回到下一个到期延迟任务的毫秒数无延迟任务时返回 -1即无限阻塞用于计算poll()超时。七、FD 监听wakeup 事件与公平性Run()每次迭代都会调用UpdateWatchTasks()重建poll()的 fd 列表POSIX 平台并处理revents。PostFileDescriptorWatches()lock_free_task_runner.cc对每个就绪的 fd 投递一个RunFileDescriptorWatch任务wakeup_event_EventFd就地处理并Clear()避免无限递归投递任务普通 watch 通过PostTask转为任务执行并在 POSIX 平台上把 fd 设为负数poll_fds_[i].fd -poll_fds_[i].fd使poll()暂时忽略该 fd直到任务运行后恢复——这是防止同一次就绪事件被反复触发、保证公平性的机制Windows 平台无法用负数标记改用WatchTask::pending标志跟踪代价是每次调用都要重建poll_fds_向量lock_free_task_runner.cc。八、测试与验证仓库通过 task_runner_unittest.cc 对两种 TaskRunner 进行类型参数化测试TYPED_TEST_SUITE(TaskRunnerTest, TaskRunnerTypes, ...)保证LockFreeTaskRunner与UnixTaskRunner行为兼容覆盖立即/延迟任务、跨线程投递、FD watch 注册注销、公平性FileDescriptorWatchesNotStarved、无重复回调、IsIdleForTesting、多线程压力等。针对LockFreeTaskRunner专属逻辑还有三个关键测试NoSlabLeakstask_runner_unittest.cc以突发方式投递最多 10000 个任务断言slabs_allocated() 2验证空闲链表复用机制有效、Slab 不泄漏HashSpreadingtask_runner_unittest.cc对大量 Slab 指针做哈希分布统计断言空桶不超过 4 个12.5%、热点不超过均值的 2.5 倍保证 32 桶方案在实践中分摊均匀RaceOnQuittask_runner_unittest.cc从另一线程对正在运行的 LFTR 调用Quit()覆盖第五节与第四节提到的跨线程退出竞态。MultiThreadedStresstask_runner_unittest.cc用 4 个线程各投递 1000 个任务且每个线程断言自己收到的任务序号严格递增——验证了任务执行顺序与投递顺序一致的兼容性承诺。九、总结设计哲学与适用边界LockFreeTaskRunner的设计精华可归结为三句话用数据结构约束访问模式Writer 只碰 tail、Reader 独占链表把并发问题压缩到tail_与两个位图这几个原子点上用位图做发布/消费屏障tasks_writtenrelease与tasks_readacquire替代了锁的内存序职责用哈希桶引用计数代替逐对象计数把能否安全删除的概率问题转化为 32 桶的近似判定假阳性无害、实现无锁。它的适用边界同样清晰面向低积压、多写者、单读者的场景Perfetto 的典型负载而非海量积压队列——O(N) 链表回溯与递归消费决定了后者会同时牺牲时间与栈空间。对希望在自己的系统中复刻类似方案如日志系统、IPC 调度器的开发者而言本文所述的 Slab 复用、位图发布、桶式引用计数三个技巧都是经过生产验证、可直接借鉴的模式。延伸阅读设计文档原文docs/design-docs/lock-free-task-runner.md头文件与 Slab/ScopedRefcount 定义include/perfetto/ext/base/lock_free_task_runner.h完整实现src/base/lock_free_task_runner.cc基准测试源码src/base/task_runner_benchmark.cc单元测试src/base/task_runner_unittest.cc上层抽象接口include/perfetto/base/task_runner.h【免费下载链接】perfettoProduction-grade client-side tracing, profiling, and analysis for complex software systems.项目地址: https://gitcode.com/GitHub_Trending/pe/perfetto创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Perfetto LockFreeTaskRunner 设计解析：基于 Slab 的无锁 MPSC 任务执行引擎
Perfetto LockFreeTaskRunner 设计解析基于 Slab 的无锁 MPSC 任务执行引擎【免费下载链接】perfettoProduction-grade client-side tracing, profiling, and analysis for complex software systems.项目地址: https://gitcode.com/GitHub_Trending/pe/perfetto导读本文围绕 Perfetto 仓库中的设计文档 lock-free-task-runner.md 展开深入剖析支撑 Perfetto SDK 与设备端服务大部分代码的无锁任务执行引擎base::LockFreeTaskRunner。你将理解它如何在多生产者单消费者MPSC模型下用 Slab 链表 位图实现免锁投递与消费、如何通过 32 个引用计数桶解决棘手的 slab 删除竞态以及它与旧版UnixTaskRunner的兼容性与性能差异。读完本文你可以直接对照 lock_free_task_runner.h 与 lock_free_task_runner.cc 读懂其全部实现细节并为自研无锁队列提供可借鉴的设计范式。一、概述一个跨平台的无锁任务执行引擎base::LockFreeTaskRunner是 Perfetto 核心基础设施之一其头文件位于 include/perfetto/ext/base/lock_free_task_runner.h实现位于 src/base/lock_free_task_runner.cc。它是一个跨平台的**多生产者单消费者Multi-Producer Single-Consumer, MPSC**任务执行引擎允许多个线程安全地调用PostTask()投递任务所有任务都固定由一个指定线程在Run()循环中执行通过精心设计的无锁协议彻底摆脱传统互斥锁mutex同步。它支撑了 Perfetto 的绝大部分代码——无论是 SDK 侧还是设备端 tracing 服务其地位相当于整个项目的事件循环心脏。核心特性原设计文档明确列出如下关键性质无锁、无自旋PostTask()和Run()的时间复杂度有界不使用任何 mutex 或 spinlock极少分配在没有突发即同时未消费任务不超过 2 × 512 1024 个的情况下除了拷贝非平凡的std::functionvoid()所需的分配外不执行任何堆分配顺序兼容与旧版UnixTaskRunner行为兼容任务按相同顺序被取出并执行。相对旧版约 2 倍提速设计文档给出了仓库内基准测试的输出使用perfetto_benchmarks目标见 task_runner_benchmark.cc$ out/rel/perfetto_benchmarks --benchmark_filter.*BM_TaskRunner.* ... ------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------------------------- BM_TaskRunner_SingleThreadedUnixTaskRunner 27778190 ns 27772029 ns 25 BM_TaskRunner_SingleThreadedLockFreeTaskRunner 10381056 ns 10375656 ns 67 BM_TaskRunner_MultiThreadedUnixTaskRunner 567794 ns 344625 ns 2033 BM_TaskRunner_MultiThreadedLockFreeTaskRunner 265943 ns 265754 ns 2749可以看到在单线程场景下LockFreeTaskRunner约为旧版的 2.7 倍多线程场景8 线程竞争投递也约为 2.1 倍。在代码库中的接入方式LockFreeTaskRunner与UnixTaskRunner共同实现 include/perfetto/base/task_runner.h 中定义的TaskRunner抽象接口PostTask(std::functionvoid())投递立即任务PostDelayedTask(std::functionvoid(), uint32_t delay_ms)投递延迟任务AddFileDescriptorWatch(PlatformHandle, std::functionvoid())/RemoveFileDescriptorWatch(PlatformHandle)注册/注销文件描述符Windows 上是句柄监听RunsTasksOnCurrentThread()判断当前线程是否为任务执行线程。值得注意的一个接入细节头文件末尾定义了条件类型MaybeLockFreeTaskRunnerlock_free_task_runner.h由构建标志USE_LOCKFREE_TASKRUNNER决定实际使用哪一个实现using MaybeLockFreeTaskRunner std::conditional_tPERFETTO_FLAGS(USE_LOCKFREE_TASKRUNNER), LockFreeTaskRunner, UnixTaskRunner;该别名被 thread_task_runner.cc 等上层代码直接使用也就是说上层业务代码无需改动即可在两种实现间切换。像src/traced/service/service.cc、src/traced/probes/probes.cc、src/profiling/memory/heapprofd.cc等设备端服务均通过这一机制接入。二、架构术语与整体设计Writer 与 Reader为便于讨论设计文档将参与线程分为两类Writers调用PostTask()的 N 个线程Reader在Run()循环中执行任务的唯一线程即主线程。设计文档特别说明本文只讨论PostTask()的无锁设计PostDelayedTask()与Add/RemoveFileDescriptorWatch()的逻辑与旧版UnixTaskRunner完全一致——它们先跳跃到任务线程上再在主线程操作延迟任务表和 FD 集合。从其他线程调用时这多了一次跳跃hop但设计文档指出(1) 实践中这些调用绝大多数发生在主线程(2) 它们几乎从不位于热点路径上因此代价可接受。Slab 链表MPSC 队列的核心LockFreeTaskRunner采用基于 Slab 的 MPSC 队列。每个 Slab 包含以下组成部分对应 lock_free_task_runner.h 中Slab结构体的字段成员类型访问者作用tasks[]固定 512 槽的任务数组kSlabSizeWriter 写Reader 在对应位图位置位后读存放std::functionvoid()next_task_slotstd::atomicsize_t仅 Writer原子计数器用于预留槽位slab 满时可能超过kSlabSize此时值已无意义tasks_written[]std::arraystd::atomicBitWord, kNumWords512 位发布位图Writer 原子释放-或置位Reader 读标记第 i 槽任务已就绪可消费最终全 1 并保持tasks_read[]非原子的BitWord数组512 位消费位图仅 Reader标记任务已被消费最终也全 1prevSlab*仅 Reader 遍历Writer 仅在建新 Slab 时写入指向链表中的前一个 Slab其中位图每个 word 为sizeof(size_t) * 8位kNumWords kSlabSize / kBitsPerWord64 位平台下即 8 个 word。Slabs 通过prev指针组成单向链表。关键点是这个链表本身不是原子的只有tail_指针是原子的。Reader 是唯一遍历链表者Writer 只访问最新的tailSlab并在需要时追加新 Slab、替换tail_。设计文档给出了链表结构示意tail_ (atomic_shared_ptr) | ▼ ----------------- ----------------- ----------------- | Slab N | | Slab N-1 | | Slab 0 | | tasks: [....] | | tasks: [....] | | tasks: [....] | | next_task_slot | | next_task_slot | | next_task_slot | | prev (sptr) ---------| prev (sptr) ---------| prev nullptr | ----------------- ----------------- -----------------注头文件中的tail_实际类型是std::atomicSlab*而非 atomic shared_ptr原文档示意图保留了早期中间设计的表述从当前源码看引用计数方案已改为下文所述的 32 桶计数见 lock_free_task_runner.h。该设计遵循三条原则单向访问生产者线程只访问 tail Slab绝不回头遍历消费者独占只有主线程沿prev指针回溯并排空任务突发处理当前 Slab 满时由 Writer 自动分配新 Slab。在名义条件下没有数千任务的突发系统中通常只存在两个 Slab。大小为 1 的空闲链表free_slab_避免了对分配器的压力——两个 Slab 在new/delete之间反复切换复用详见 lock_free_task_runner.cc 的AllocNewSlab()/DeleteSlab()。设计权衡O(N) 回溯只保留 tail 指针的单向链表意味着 Reader 的最坏复杂度为 O(N)——它必须遍历整个链表才能拿到最早的任务保证 FIFO。但实践中几乎始终只有两个 Slab如果队列里积压了 1 万10 万个任务遍历链表反而是最不值得担心的问题。该设计的主要妥协是任务数量大时扩展性差因为Run()既变慢遍历链表又更吃栈用递归而非堆来走链表。设计文档注明Perfetto 预期不会有大量积压任务已知的例外如 b/330580374 应被独立修复。三、生产者工作流PostTask() 的无锁协议PostTask()的完整实现见 lock_free_task_runner.cc遵循以下协议加载 tail原子加载当前tail_Slab 指针获取引用计数为该 Slab 递增一个引用计数桶详见第五节预留槽位原子递增next_task_slot获得一个槽位序号处理溢出若 Slab 已满分配新 Slab 并尝试原子更新tail_写入任务把任务写入预留的槽位发布以 release 语义在tasks_written位图中置位使任务对 Reader 可见释放引用计数ScopedRefcount析构时自动递减。其中第 2 步有一个容易被忽略的重要细节递增引用计数后代码会再次加载tail_并比对若发现已经不是同一个 Slab则说明该 Slab 可能在 load 与 refcount 递增之间被 Reader 删除Reader 的 refcount0 检查可能早于我们的递增发生此时直接continue重试。在 seq_cst 顺序下任何后续替换tail_的 CAS 都发生在这次二次 load 之后因此 Reader 之后的引用计数检查必然观察到我们的递增——这是无锁正确性的关键一环。溢出处理当slot kSlabSize时对应实现中的三种情形slot kSlabSize是常见溢出slot kSlabSize是两个以上线程竞争导致的罕见情形设计文档给出了核心代码Slab* new_slab AllocNewSlab(); new_slab-prev slab; new_slab-next_task_slot.store(1, std::memory_order_relaxed); slot 0; if (!tail_.compare_exchange_strong(slab, new_slab)) { // Another thread won the race, retry with their slab new_slab-prev nullptr; DeleteSlab(new_slab); continue; }这与 lock_free_task_runner.cc 的实现逐行对应CAS 失败的线程把新 Slab 的prev置空并归还空闲链表然后重试CAS 成功的线程把新 Slab 的next_task_slot预置为 1因为它自身占用第 0 槽再把scoped_refcount重新绑定到新 Slab 上。另外PostTask()入口有一个PERFETTO_CHECK(closure)断言lock_free_task_runner.cc不允许投递空的std::function因为PopTaskRecursive()以std::function的空性作为退出判据。四、消费者工作流Run() 主循环与任务消费Run() 循环结构主线程的Run()lock_free_task_runner.cc每轮迭代执行任务排空PopNextImmediateTask()取出一个立即任务延迟任务处理PopNextExpiredDelayedTask()取出一个已到期延迟任务FD 轮询以带公平性约束的方式处理 I/O 事件任务执行在 watchdog 保护下运行任务。当前设计每执行一个任务就调用一次poll()有任务时poll_timeout_ms 0。设计文档指出这是可优化的若已知存在任务突发可以背靠背地连续执行任务而省去零超时 poll 的 syscall 开销——但这需要设置上限以防止活锁例如一个设计糟糕的函数不断自我重投递直到某个 socket 收到数据才触发 FD watch。然而设计文档也坦言多年来的测试已经对旧版UnixTaskRunner的严格公平性产生了依赖——测试期望通过IsIdleForTesting()判断事件地平线上是否存在即将到来的 FD watch。正如 Hyrum 定律所示这已成为 TaskRunner 的隐式 API在大量测试被重写并去 flake 之前必须维持。Run()中的 TODO 注释lock_free_task_runner.cc也印证了这一点TestTaskRunner.RunUntilIdle()的微妙语义被测试依赖贸然优化会破坏它们。任务消费算法PopTaskRecursive()PopTaskRecursive()lock_free_task_runner.cc实现消费逻辑递归回溯沿prev指针递归回到最老的 Slab名义条件下通常只回退一个 Slab保证 FIFO 顺序位图扫描对每个 word读取tasks_writtenacquire 语义并与tasks_read取反做 AND得到未消费位unread_word wr_word ~rd_word用CountTrailZeros找到第一个未消费的槽位消费std::move取出任务、槽位置空并在tasks_read中置位安全删除若整个 Slab 的写位图与读位图均已填满且它不是 tailnext_slab非空且对应引用计数桶为 0则将其从链表中摘除并归还。设计文档给出的伪代码std::functionvoid() PopTaskRecursive(Slab* slab, Slab* next_slab) { // First, recursively check older slabs (FIFO ordering) Slab* prev slab-prev; if (prev) { auto task PopTaskRecursive(prev, slab); if (task) return task; } // Then check current slab for published tasks for (size_t w 0; w Slab::kNumWords; w) { BitWord wr_word slab-tasks_written[w].load(std::memory_order_acquire); BitWord rd_word slab-tasks_read[w]; BitWord unread_word wr_word ~rd_word; // Find and consume first unread task... } // Safe slab deletion logic... }删除逻辑在实现中表现为lock_free_task_runner.ccbool slab_fully_consumed words_fully_consumed Slab::kNumWords; const uint32_t bucket HashSlabPtr(slab); if (slab_fully_consumed next_slab refcounts_[bucket].load() 0) { PERFETTO_DCHECK(next_slab-prev slab); next_slab-prev slab-prev; slab-prev nullptr; DeleteSlab(slab); }Quit() 与跨线程退出Quit()lock_free_task_runner.cc必须通过PostTask跳跃到主线程执行避免另一线程写quit_true后主线程立即销毁自身而该线程再调用WakeUp()访问已销毁对象的竞态。Run()退出前还有一个值得注意的收尾循环lock_free_task_runner.cc它会自旋等待所有引用计数桶归零。原因是一个典型的测试竞态线程 1 调用Quit()变为 PostTask主线程看到quit_true返回并销毁 LFTR而线程 1 还在执行 PostTask 的收尾、递减引用计数从而访问已失效内存。五、引用计数系统一个精妙的 Slab 删除竞态竞态的本质表面上看Writer 只访问 tail Slab、绝不回走链表的访问模式大幅简化了同步需求。但设计文档指出一个必须解决的微妙竞态初始条件任务运行器只有一个 Slab S0 且恰好已满tail_ - S0 (full) - nullptr。竞态推演线程 A 读取tail_得到 S0 的地址但在执行原子递增next_task_slot该操作会揭示 Slab 已满之前被抢占挂起slab tail_.load(); // Pre-emption happens here slab-next_task_slot.fetch_add(1); ...线程 B 做同样的事但未被抢占它读到 S0、发现已满、分配新 Slab S1 并替换 tail此时tail_ - S1 - S0 - nullptrRun()线程开始循环发现有两个 Slab注意到 S0 已满、不是 tail于是判定它可以安全删除此时线程 A 恢复执行尝试递增已被删除的 S0 的next_task_slot——use-after-free。根因删除非 tail Slab 本身是安全的Writer 不遍历链表但某个线程可能在该 Slab 还是 tail 时观察到了它而 Reader 无从得知这一点。因此给 Slab 自身加引用计数或其他属性是无济于事的——它解决不了Slab 可能已经消失这一核心问题缓解措施必须在 Slab 之外实施。为什么不用 atomic shared_ptr在 LockFreeTaskRunner 的中间设计中曾用shared_ptrSlab来缓解此问题。非侵入式的 STLshared_ptr通过一个中间控制块把 Slab 与引用计数解耦。然而设计文档明确指出libcxx 对 shared_ptr 的原子访问器在不同线程间交换shared_ptrSlab tail_所必需的是用一个 32 个 mutex 的哈希池实现的参见__get_sp_mut这实际上违背了无锁的初衷。最初的简化缓解方案一个直观的简化方案是每个 Writer 在开始 PostTask 前递增全局引用计数如task_runner.num_writers_active结束后递减。这样 Reader 能随时知道是否有 Writer 处于活跃状态。Reader 侧若num_writers_active 0则跳过删除、留待下一个任务再试。注意这不是 mutex 也不是 spinlock因为没有人等待别人。其正确性建立在如下原则上Writer 只能通过tail_指针观察 SlabReader 只删除非 tail Slab因此它知道tail_指向的并非正在删除的 Slab若没有 Writer 活跃就没有人观察过任何 Slab更不可能观察过被删除的 Slab若某 Writer 在num_writers_active 0检查之后立即活跃在顺序一致性下它必然观察到新的 tail Slab不可能观察到正在被删除的旧 Slab。这个方案能解决竞态但暴露了新问题如果某个 Writer 线程恰好在Run()每次检查时都在投递任务Slab 就永远无法被删除。设计文档认为该场景极不现实——若 Writer 永远活跃假设任务执行时间大于 PostTask 调用时间任务运行器大概率早就被撑爆了。当前方案32 个引用计数桶 哈希映射理想方案是每个 Slab 一个引用计数但如前所述引用计数不能放在 Slab 上它正是用于把关对 Slab 的访问。放在任务运行器中的mapSlab*, atomicint又会造成堆抖动且需要无锁 map。最终采用折中方案固定 32 个引用计数桶通过哈希函数把每个 Slab 映射到一个桶。两个 Slab 可能哈希到同一桶产生假阳性——某 Slab 明明没被引用却因哈希冲突被误判为有引用。但假阳性在此场景下无害最坏情况退化为上述简化方案而它在竞态视角下依然是正确的。实践上这相当于把推迟删除 Slab的概率降低了 32 倍。这正是 lock_free_task_runner.h 中LockFreeTaskRunner::refcounts_std::arraystd::atomicint32_t, kNumRefcountBuckets以及 Writer 使用的ScopedRefcount类所支撑的逻辑。kNumRefcountBuckets 32在头文件的task_runner_internal命名空间中作为常量暴露给测试使用。哈希函数采用SplitMix64lock_free_task_runner.h先清除 ASAN/MTE 的 tag 字节再混合对指针分布非常快速有效static uint32_t HashSlabPtr(Slab* slab) { uint64_t u reinterpret_castuintptr_t(slab); u 0x00FFFFFFFFFFFFFFull; // Clear asan/MTE top byte for tagged pointers. u 0x9E3779B97F4A7C15ull; u (u ^ (u 30)) * 0xBF58476D1CE4E5B9ull; u (u ^ (u 27)) * 0x94D049BB133111EBull; return static_castuint32_t((u ^ (u 31)) % kNumRefcountBuckets); }ScopedRefcountlock_free_task_runner.h在构造时对桶执行fetch_add(1)并在析构时fetch_sub(1)支持移动语义以在溢出路径中把引用从旧 Slab 转移到新 Slab。六、延迟任务处理FlatSet 反向排序延迟任务使用独立的FlatSetDelayedTask容器头文件中DelayedTask定义见 lock_free_task_runner.h维护排序需要一定开销实践中延迟任务通常只有个位数主要用于超时但避免了大多数情况下的分配——FlatSet基于 vector仅在需要扩容时才分配。DelayedTask的operator采用反向排序时间更晚的排前面、更早的排后面这样Run()只需 O(1) 的pop_back()即可取出最早到期的任务lock_free_task_runner.cc相当于用 vector 实现 FIFO 队列。跨线程调用PostDelayedTask()时同样先PostTask跳跃到主线程lock_free_task_runner.cc并借助next_delayed_task_seq_序列号保证同一时间戳下任务的稳定顺序。GetDelayMsToNextTask()返回到下一个到期延迟任务的毫秒数无延迟任务时返回 -1即无限阻塞用于计算poll()超时。七、FD 监听wakeup 事件与公平性Run()每次迭代都会调用UpdateWatchTasks()重建poll()的 fd 列表POSIX 平台并处理revents。PostFileDescriptorWatches()lock_free_task_runner.cc对每个就绪的 fd 投递一个RunFileDescriptorWatch任务wakeup_event_EventFd就地处理并Clear()避免无限递归投递任务普通 watch 通过PostTask转为任务执行并在 POSIX 平台上把 fd 设为负数poll_fds_[i].fd -poll_fds_[i].fd使poll()暂时忽略该 fd直到任务运行后恢复——这是防止同一次就绪事件被反复触发、保证公平性的机制Windows 平台无法用负数标记改用WatchTask::pending标志跟踪代价是每次调用都要重建poll_fds_向量lock_free_task_runner.cc。八、测试与验证仓库通过 task_runner_unittest.cc 对两种 TaskRunner 进行类型参数化测试TYPED_TEST_SUITE(TaskRunnerTest, TaskRunnerTypes, ...)保证LockFreeTaskRunner与UnixTaskRunner行为兼容覆盖立即/延迟任务、跨线程投递、FD watch 注册注销、公平性FileDescriptorWatchesNotStarved、无重复回调、IsIdleForTesting、多线程压力等。针对LockFreeTaskRunner专属逻辑还有三个关键测试NoSlabLeakstask_runner_unittest.cc以突发方式投递最多 10000 个任务断言slabs_allocated() 2验证空闲链表复用机制有效、Slab 不泄漏HashSpreadingtask_runner_unittest.cc对大量 Slab 指针做哈希分布统计断言空桶不超过 4 个12.5%、热点不超过均值的 2.5 倍保证 32 桶方案在实践中分摊均匀RaceOnQuittask_runner_unittest.cc从另一线程对正在运行的 LFTR 调用Quit()覆盖第五节与第四节提到的跨线程退出竞态。MultiThreadedStresstask_runner_unittest.cc用 4 个线程各投递 1000 个任务且每个线程断言自己收到的任务序号严格递增——验证了任务执行顺序与投递顺序一致的兼容性承诺。九、总结设计哲学与适用边界LockFreeTaskRunner的设计精华可归结为三句话用数据结构约束访问模式Writer 只碰 tail、Reader 独占链表把并发问题压缩到tail_与两个位图这几个原子点上用位图做发布/消费屏障tasks_writtenrelease与tasks_readacquire替代了锁的内存序职责用哈希桶引用计数代替逐对象计数把能否安全删除的概率问题转化为 32 桶的近似判定假阳性无害、实现无锁。它的适用边界同样清晰面向低积压、多写者、单读者的场景Perfetto 的典型负载而非海量积压队列——O(N) 链表回溯与递归消费决定了后者会同时牺牲时间与栈空间。对希望在自己的系统中复刻类似方案如日志系统、IPC 调度器的开发者而言本文所述的 Slab 复用、位图发布、桶式引用计数三个技巧都是经过生产验证、可直接借鉴的模式。延伸阅读设计文档原文docs/design-docs/lock-free-task-runner.md头文件与 Slab/ScopedRefcount 定义include/perfetto/ext/base/lock_free_task_runner.h完整实现src/base/lock_free_task_runner.cc基准测试源码src/base/task_runner_benchmark.cc单元测试src/base/task_runner_unittest.cc上层抽象接口include/perfetto/base/task_runner.h【免费下载链接】perfettoProduction-grade client-side tracing, profiling, and analysis for complex software systems.项目地址: https://gitcode.com/GitHub_Trending/pe/perfetto创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考