G1 复制 Evac：BFS 拷贝循环的设计思想与解决方案

G1 复制 EvacBFS 拷贝循环的设计思想与解决方案关键词G1、Evacuation、复制、BFS、任务队列、工作窃取、转发指针、PLAB、协商终止姊妹篇《G1 新生代GC并行疏散暂停整体设计根处理、RSet 扫描与对象复制的协同》把根处理、RSet、复制 Evac 框进同一个 STW 阶段本文聚焦三者之中最后一程——复制 Evac 本身对象是怎样被搬离 CSet 的。1. 背景为什么需要 BFS 拷贝循环前两步根处理、RSet 扫描把图入口边收集进了工作线程的任务队列——栈上的引用、全局结构里的指针、脏卡上指向 CSet 的引用全都以引用槽位的形式排进队列。但入口边只是第一跳真正要做的是把一个对象搬走之后它内部字段引用的子对象也要跟着搬子对象的子对象又要搬……直到整张存活子图都被搬到新位置Survivor / Old。这段沿图遍历并疏散的工作就是复制 EvacEvacuation的拷贝循环在代码里对应G1ParEvacuateFollowersClosure::do_void。它是G1ParTask::work三大阶段里的最后一程也是真正把字节从 from-space 搬到 to-space 的地方。本文要回答的核心问题是为什么这个循环是队列驱动、广度优先BFS“的而不是更直觉的递归深搜DFS”这背后解决了哪些设计难题2. 核心设计挑战把遍历一张可能极深、极大的对象图并搬家这件事交给 N 个 GC 线程并行做难点非常集中图可能极深长链表、深层嵌套结构、超大对象数组深度没有上界。若用原生 C 递归遍历深度一上来就栈溢出。必须并行且均衡几十个线程同时搬运谁也不能因为分到一大坨而拖垮整个 STW。需要一种能被偷任务的负载均衡机制。不重不漏同一个对象会被多个字段、多个线程从不同路径引用可能被反复入队。绝不能搬两次也不能漏搬一次。分配竞争所有线程都在往同一批 Region 里写新对象如果每次分配都争全局锁并行度立刻归零。停顿可控超大数组一旦被一次扫描可能把整个暂停时间撑爆必须可切片、可续扫。队列有界但任务不能丢可被窃取、小而快的本地队列容量有限但 BFS 的爆发式入队可能瞬间把它填满塞满后的任务不能丢否则对象图遍历断裂、漏搬对象。安全收尾队列空了不代表结束——别的线程可能正把新任务偷过去。需要一种大家都真的空了的判定。G1 用六套设计逐一化解。3. 设计一任务队列驱动的层级展开BFS 语义整个拷贝循环的核心隐喻是一个任务队列。队列里存放的最小单元是StarTask——它编码的不是一个对象而是一个引用所在的槽位比如字段在内存中的地址oop* p。处理一个任务时发生的事情是从槽位p读出对象 → 若它在回收集合CSet里则把它疏散到新位置 → 把新地址就地写回p。注意写回原槽位这一步它意味着无论是根里的指针、还是某个对象字段里的指针修复方式完全统一——都是找到槽位、改掉里面的值。这把修根和修字段两种动作在机制上归一了。而出队处理一个对象时它内部的所有字段引用并不会被立即递归深入去搬而是被压回任务队列留待后续轮次处理。StarTask里只有当前层的直接孩子没有孙子。这就是所谓 BFS广度优先的本质——层级扩张处理完当前对象只把它的孩子入队孩子生出的孙子在下一轮才轮到。这套设计一举解决两个问题不爆 C 栈遍历状态从原生调用栈挪到了堆上分配的任务队列遍历深度与 C 栈无关深度再大也不溢出。队列成为并行的单元正因为待办事项都在队列里闲线程才能去偷忙线程的队列——并行工作窃取才成为可能见设计二。递归 DFS 是单线、不可中断、不可偷的根本无法并行化。附带收益是空间局部性一批同时可达的对象在被同一线程扫到时会被它自己的 PLAB 相邻分配在 to-space 里天然挨得近后续访问缓存命中率更高DFS 则会沿一条深路径把对象撒得到处都是。4. 设计二三层循环 工作窃取并行搬运与负载均衡do_void把上述队列驱动思想落成一个清晰的三层结构第一层排干自己的队列。线程开始先把自己本地队列里的任务全部处理完——先排溢出栈、再排本地栈。先排溢出栈是为了让别的线程能尽早偷到任务别让活儿憋在自己手里。本地队列为何会有溢出栈、为何必须先排它下一节 设计三 专门展开。第二层从别人那偷 边偷边排。只要还能从别的线程队列里偷到一个任务就处理它然后立刻排干自己的队列。偷到任务说明有活儿排干自己则是避免任务堆积、让偷窃链路一直流动。第三层协商终止。当自己队列空了、也偷不到任何任务时线程向一个全局的协商终止器报到。只有当所有线程都空、且无人能再偷到任务全体才安全退出。这保证了对象图无遗漏、无死锁。工作窃取是负载均衡的关键某个线程若分到了一大坨深图它会先把任务铺进队列旁边闲着的线程立刻来偷、分摊压力。于是谁分到多少不再由初始划分决定而由运行时动态平衡。这正是 G1 能跑满多核疏散的前提。5. 设计三有界本地队列与溢出栈兜底任务不丢的安全网工作窃取能成立的前提是本地任务队列可以被偷。在 G1 里RefToScanQueue就是OverflowTaskQueueStarTask而真正进入TaskQueueSet、被别的线程steal到的是它内部那个固定容量的GenericTaskQueue。为了偷取高效这个本地队列被刻意做成有界的容量由编译期常量TASKQUEUE_SIZE决定64 位下117约 13 万个StarTask槽位32 位下114约 1.6 万个。容量有限是为了让队列始终是一个紧凑数组——pop_global的无锁偷取靠bottom/top索引完成队列越小越能待在缓存里偷取成本与缓存命中率才可控若队列无限膨胀偷取就会变慢、局部性也会垮掉。但有界与BFS 会爆发式产生孩子天然冲突处理一个大对象可能一次喷出成百上千个孩子深图遍历中某线程也会短期积压远超本地队列容量的任务。一旦本地队列写满push就会失败。这些任务不能丢——丢了就意味着对象图遍历断裂、漏搬对象是比慢更严重的错误。G1 的解法是溢出栈兜底OverflowTaskQueue在固定本地队列之外挂了一个无界的StackE, F成员_overflow_stack。push的语义被改写——先试着压进有界本地队列若满了就透明地溢到这个无界栈上push对外永远返回成功。于是热路径上仍然是小而快的本地队列极端积压时又有无限容量的安全网保证任何任务都不会因队列满而丢失。溢出栈还有一个决定全局行为的属性它不参与工作窃取。窃取只看TaskQueueSet里的GenericTaskQueue溢出栈是每个线程私有的别人偷不到。这就解释了 设计二 第一层先排溢出栈、再排本地栈的由来——压在自己溢出栈里的活儿只有自己能消化若先排本地队列、把溢出栈留到最后这些活儿会一直憋在手里、别的线程帮不上忙。trim_queue的实际顺序是先把溢出栈里的任务逐个pop_overflow取出尝试try_push_to_taskqueue推回可偷的本地队列推得动就让别的线程来偷推不动才就地dispatch_reference处理溢出栈排干后才pop_local处理本地队列外层do ... while (!is_empty())循环则一直跑到本地队列和溢出栈同时为空才停下。注意is_empty()在这里被重写过——它要求两者都空才为真所以溢出栈里的残留任务同样会挡住线程进入协商终止确保不让任何活儿漏在终止之前。6. 设计四转发指针幂等重复入队安全一个对象很可能被多个字段引用、被多个线程从不同路径入队。如果每次入队都真的搬一次结果就会错乱。G1 的解法是在对象的mark word 里装转发指针forwarding pointer第一个处理该对象的线程把它搬到新位置并在原对象 mark word 上标记已搬迁、写入新地址。之后任何线程再遇到这个对象发现 mark word 已标记就直接取出转发指针——绝不二次拷贝。这个机制让宽队列里出现重复任务变得廉价且安全重复入队几乎零成本一次 mark word 判读结果幂等。它也是前一篇 RSet 扫描里卡片惰性认领允许良性竞争的底气——既然重复处理会被转发指针去重那扫描时偶尔多扫一次就无伤大雅。7. 设计五PLAB 无锁分配避免分配竞争搬一个对象必然要在 to-spaceSurvivor 或 Old 的 Region里给它分配一块新内存。若所有线程都去抢全局 Region 的分配位置需要加锁或 CAS并行度会被分配锁拖垮。G1 的解法是PLABPer-thread / Parallel GC Allocation Buffer每线程并行分配缓冲每个工作线程在G1ParScanThreadState里持有自己私有的小块内存内部用指针碰撞无锁分配——新对象只在本线程的_top上做指针加法绝大多数拷贝走这条零竞争的快路径。只有当本线程的 PLAB 不够用时才走慢路径退役旧 PLAB、从全局 Region 批发一大块新内存填进 PLAB 再分特别大的对象则绕过 PLAB 直接分配避免为一个大对象浪费整块缓冲。PLAB 大小还能自适应调优在太大碎片浪费和太小频繁批发之间取平衡。这样拷贝循环的读旧、写新、更新指针三件事里最热的写新几乎全程无锁并行度才真正跑得满。8. 设计六部分数组切片 协商终止可控与收尾队列驱动还顺手解决了两个收尾难题超大对象数组切片。一个巨大的对象数组如百万长度的int[]若一次性扫描它的全部元素、把元素里指向 CSet 的引用都处理掉这次扫描本身就可能把暂停时间撑爆。G1 的做法是首次处理时只把数组切成ParGCArrayScanChunk大小的块先处理第一块剩下的用部分数组掩码标记后重新压回队列。后续谁偷到这个切片任务就接着处理下一块处理不完再切片续压。如此循环超大数组被平滑成多次小扫描既控停顿又限内存占用。协商终止兜底正确性。第三层循环的协商终止器不只是性能优化更是正确性保障它确保只有在所有队列都空 无人正持有可偷任务时全体才退出。任何漏网的活儿都会让终止协商失败、线程继续巡查从而杜绝图没搬完就收工的致命错误。附带地拷贝过程还顺带完成年龄统计、晋升阈值判定、存活字节计数等这些数据供后续 GC 策略计算但它们不属于拷贝循环的核心设计此处略过。9. 拷贝的本质动作剥掉机制复制 Evac 的核心只有两步循环取出一个引用槽位 → 处理它若指向 CSet则疏散对象、装转发指针、把新地址写回槽内若不在 CSet则按需维护记忆集脏卡说明它指向别区、需更新对应 RSet。然后扫描新对象的字段把其中指向 CSet 的字段槽位压回队列——不递归深入留待下一轮。整个过程由根处理 RSet 扫描喂入的初始入口边驱动沿对象图层级扩张直到队列在所有线程间彻底流干。每个被搬走的对象都留下转发指针保证后续引用修复幂等。10. 与根处理、RSet 扫描的关系把三块放回同一张图复制 Evac 是这条流水线的发动机[根处理] ─┐ ├─► 入口边堆外 堆内 RSet汇入同一任务队列 [RSet 扫描]─┘ │ ▼ [BFS 拷贝循环] 沿队列广度优先疏散整张子图 队列驱动 / 工作窃取 / 溢出栈兜底 / 转发指针幂等 / PLAB 无锁根处理、RSet 扫描负责找入口边它们把任务塞进队列后便功成身退BFS 拷贝循环负责沿边搬家它把队列里每一跳都展开成搬对象 修指针 把孩子入队直到图搬完三者通过同一个任务队列串联——前两者的产出正是后者的输入。也正是因为这层关系复制 Evac 自己不需要知道入口来自根还是脏卡它只认队列队列里是什么槽位就修什么槽位。这种统一的队列接口是 G1 疏散流水线能复用、能并行、能正确收尾的根本原因。11. 小结G1 复制 EvacBFS 拷贝循环的设计精髓可以凝练为六句话设计解决的问题核心思路任务队列驱动 层级展开避免 C 栈溢出、支撑并行队列存引用槽位只把直接孩子入队不递归深入修根与修字段机制归一三层循环 工作窃取并行负载均衡排干自己 → 偷别人处理 → 协商终止忙线程铺队列、闲线程来偷有界本地队列 溢出栈兜底本地队列小快但会满、任务不能丢本地队列固定容量保证偷取高效满则透明溢到无界_overflow_stack溢出栈私有不可偷故先排溢出再排本地转发指针幂等重复入队不重不漏mark word 装转发指针首搬者安装、后续者取地址绝不二次拷贝PLAB 无锁分配避免分配竞争每线程私有缓冲、指针碰撞快路径仅慢路径才向 Region 批发部分数组切片 协商终止停顿可控、安全收尾超大数组切块续扫终止器确保所有队列流干才退出它与前两步一起构成 G1 在可控停顿内完成增量回收的完整闭环根处理与 RSet 给出图的入口BFS 拷贝循环完成图的遍历与搬迁。