08. mcentral：中心缓存的 span 管理

08. mcentral中心缓存的 span 管理摘要mcentral 是 TCMalloc 内存分配器的中心缓存层作为 mcache线程缓存和 mheap全局堆之间的桥梁。它通过partial[2]/full[2]双缓冲设计实现零数据搬移的角色互换采用四级查找策略partialSwept → partialUnswept → fullUnswept → grow高效分配 span并通过 spanBudget100 机制平衡清扫开销与空间浪费。mcentral 的核心价值在于为同 size class 的所有 P 提供共享的 span 池减少对全局堆锁的竞争。1. mcentral 是什么mcentral是 TCMalloc 分级缓存架构中的第二级缓存。在上一篇 07. mcache.refill 中我们提到mcache 的 span 用尽后会调用mcentral.cacheSpan()获取新 span。现在我们把视角移到 mcentral 内部。mcentral.go开头的注释解释了它的本质// Central free lists.//// See malloc.go for an overview.//// The mcentral doesnt actually contain the list of free objects; the mspan does.// Each mcentral is two lists of mspans: those with free objects (c-nonempty)// and those that are completely allocated (c-empty).— mcentral.go:5-11一句话理解mcentral不直接管理空闲对象——空闲对象仍然躺在 mspan 自己的分配位图里。mcentral 只负责管理一批 mspan按有没有空闲槽位分成partial部分空闲和full完全分配两类集合。在mheap中每种 spanClass 对应一个 mcentral构成一个数组// mheap.go示意central[numSpanClasses]struct{mcentral mcentral pad[cpu.CacheLinePadSize-unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte}— mheap.gocentral 数组含 cache line padding 防伪共享每个 P 有一个 mcache但 mcentral 是全局的、按 class 划分的。也就是说同一种 size class 的所有 mcentral 只有一份多个 P 会竞争同一个 mcentral因此 mcentral 内部需要并发控制spanSet 的无锁操作 sweep 期间的锁。这就是为什么它比 mcache 慢、但比 mheap 快。2. 结构全解partial[2] / full[2] 双缓冲mcentral结构体只有 4 个字段// Central list of free objects of a given size.typemcentralstruct{_sys.NotInHeap spanclass spanClass// partial and full contain two mspan sets: one of swept in-use// spans, and one of unswept in-use spans. These two trade// roles on each GC cycle. The unswept set is drained either by// allocation or by the background sweeper in every GC cycle,// so only two roles are necessary.//// sweepgen is increased by 2 on each GC cycle, so the swept// spans are in partial[sweepgen/2%2] and the unswept spans are in// partial[1-sweepgen/2%2]. Sweeping pops spans from the// unswept set and pushes spans that are still in-use on the// swept set. Likewise, allocating an in-use span pushes it// on the swept set.partial[2]spanSet// list of spans with a free objectfull[2]spanSet// list of spans with no free objects}— mcentral.go:22-46字段类型含义spanclassspanClass该 mcentral 负责的 size class含 scan/noscan 维度partial[2]spanSet部分空闲的 span 集合还有空闲槽位full[2]spanSet完全分配的 span 集合无空闲槽位为什么 partial 和 full 各有两个因为每个集合内部又按 GC 状态分成两半已清扫swept和未清扫unswept。partial[0]/partial[1]部分空闲的 span其中一个是已清扫另一个是未清扫full[0]/full[1]完全分配的 span同样一个是已清扫一个是未清扫spanSet 是什么spanSet是并发安全的无锁 span 集合用 spine block 两级结构 原子索引实现无锁 Push/Pop。具体见 15. spanSet。这里只需知道它支持并发的push/pop。四个访问器函数封装了索引计算func(c*mcentral)partialUnswept(sweepgenuint32)*spanSet{returnc.partial[1-sweepgen/2%2]}func(c*mcentral)partialSwept(sweepgenuint32)*spanSet{returnc.partial[sweepgen/2%2]}func(c*mcentral)fullUnswept(sweepgenuint32)*spanSet{returnc.full[1-sweepgen/2%2]}func(c*mcentral)fullSwept(sweepgenuint32)*spanSet{returnc.full[sweepgen/2%2]}— mcentral.go:59-793. 双缓冲设计精髓角色互换零数据搬移这是 mcentral 最优雅的设计。每个 GC 周期mheap_.sweepgen 2于是sweepgen/2%2在 0 和 1 之间交替已清扫和未清扫的集合自动互换角色数组里的数据不需要移动一个字节图 8-1mcentral 双缓冲设计swept / unswept 角色互换为什么只需要两个角色源码注释给出了精辟的解释// The unswept set is drained either by allocation or by the background// sweeper in every GC cycle, so only two roles are necessary.— mcentral.go:28-30未清扫集合在每个 GC 周期内必定会被清空要么被分配路径清扫要么被后台清扫器清扫所以最多只需要区分当前周期的未清扫集合和当前周期的已清扫集合两个角色。多一个都浪费少一个都不够。具体机制假设当前sweepgen 0partial[0] 已清扫partialSweptpartial[1] 未清扫partialUnswept分配路径从partial[0]直接 pop 使用从未清扫集合 pop 出来的 span 需要先 sweep后台清扫器从partial[1]/full[1]弹出 span 清扫扫完有空的推入partial[0]仍满的推入full[0]GC 结束sweepgen 2现在sweepgen/2%2 1于是partial[0]变成了未清扫它里面装的是上代清扫过的、被缓存使用的 spanpartial[1]变成了已清扫为什么被缓存使用的 span 会出现在未清扫里下一节uncacheSpan会讲到一个 span 在 sweep 之后被某个 P 缓存sweepgen 设为3。这个 span 离开缓存时它的 sweepgen 会先被降回当前代而它在上一代 sweep 时的旧集合索引1-sweepgen/2%2在新周期解读下就成了未清扫。这就是为什么上代已清扫的 span会出现在本代未清扫集合里——它需要在新的 GC 周期里重新被清扫验证因为缓存期间可能又有对象被分配/回收。零数据搬移的代价数组本身不动但未清扫集合里可能混着其实已经扫过的 span。因此注释里特别提醒// Some parts of the sweeper can sweep arbitrary spans, and hence// cant remove them from the unswept set, but will add the span// to the appropriate swept list. As a result, the parts of the// sweeper and mcentral that do consume from the unswept list may// encounter swept spans, and these should be ignored.— mcentral.go:39-43这就是为什么cacheSpan里对 unswept 集合的 pop 要做tryAcquire校验见第 4 节。4. cacheSpan四级查找策略cacheSpan是 mcentral 的核心分配函数被 mcache 的refill调用。它按由快到慢的顺序做四级查找图 8-2cacheSpan 的四级查找策略// Allocate a span to use in an mcache.func(c*mcentral)cacheSpan()*mspan{// Deduct credit for this span allocation and sweep if necessary.spanBytes:uintptr(gc.SizeClassToNPages[c.spanclass.sizeclass()])*pageSizedeductSweepCredit(spanBytes,0)...spanBudget:100vars*mspanvarsl sweepLocker// ① Try partial swept spans first.sg:mheap_.sweepgenifsc.partialSwept(sg).pop();s!nil{gotohavespan}slsweep.active.begin()ifsl.valid{// ② Now try partial unswept spans.for;spanBudget0;spanBudget--{sc.partialUnswept(sg).pop()ifsnil{break}ifs,ok:sl.tryAcquire(s);ok{// 我们抢到了这个 span清扫后使用s.sweep(true)sweep.active.end(sl)gotohavespan}// 没抢到它正在/已经被异步清扫器处理忽略}// ③ Now try full unswept spans, sweeping them...for;spanBudget0;spanBudget--{sc.fullUnswept(sg).pop()ifsnil{break}ifs,ok:sl.tryAcquire(s);ok{s.sweep(true)// 检查清扫后有没有空闲freeIndex:s.nextFreeIndex()iffreeIndex!s.nelems{s.freeindexfreeIndex sweep.active.end(sl)gotohavespan}// 扫完还是满的放回 fullSweptc.fullSwept(sg).push(s.mspan)}}sweep.active.end(sl)}...// ④ We failed to get a span from the mcentral so get one from mheap.sc.grow()ifsnil{returnnil}havespan:// 初始化 allocCachen:int(s.nelems)-int(s.allocCount)ifn0||s.freeindexs.nelems||s.allocCounts.nelems{throw(span has no free objects)}freeByteBase:s.freeindex^(64-1)whichByte:freeByteBase/8s.refillAllocCache(whichByte)// Adjust the allocCache so that s.freeindex corresponds to the low bit in// s.allocCache.s.allocCaches.freeindex%64returns}— mcentral.go:82-199四级查找的详细分析级别来源是否清扫成本源码位置①partialSwept否已清扫O(1) popmcentral.go:114-116②partialUnswept是sweep 后复用sweep 尝试mcentral.go:121-138③fullUnswept是sweep 后可能复用sweep 尝试mcentral.go:141-160④grow()mheap新分配全局锁 可能 mmapmcentral.go:171-174① partialSwept最快的路径ifsc.partialSwept(sg).pop();s!nil{gotohavespan}— mcentral.go:114-116已清扫且部分空闲的 span 是最理想的候选——内存干净、有现成的空闲槽位直接拿走即可。这是每次 GC 后大量存在的最常见场景。② ③ partialUnswept / fullUnswept清扫后复用这两级的关键是sweepLocker.tryAcquireifs,ok:sl.tryAcquire(s);ok{// 我们抢到了这个 span清扫后使用s.sweep(true)...}— mcentral.go:126-131为什么需要 tryAcquire因为第 3 节说过未清扫集合里可能混着被其他清扫者抢占的 span。tryAcquire用原子的方式尝试认领这个 span 的清扫权成功这个 P 负责清扫它扫完直接使用partial或检查有没有空闲full失败它正在被异步清扫器处理当前 P 直接跳过——绝不能重复清扫第 ③ 级有个特殊处理如果 full span 扫完之后仍然没有空闲槽位所有对象都存活那就把它放回fullSwept继续尝试下一个freeIndex:s.nextFreeIndex()iffreeIndex!s.nelems{s.freeindexfreeIndexgotohavespan// 扫出空闲了用这个}c.fullSwept(sg).push(s.mspan)// 扫完还是满的放回已清扫的 full— mcentral.go:150-157havespanallocCache 重建无论从哪一级拿到 span最终都汇聚到havespan标签havespan:freeByteBase:s.freeindex^(64-1)whichByte:freeByteBase/8// 重建 64 位空闲缓存s.refillAllocCache(whichByte)// 让 freeindex 对应 allocCache 的最低位s.allocCaches.freeindex%64returns— mcentral.go:177-198refillAllocCache从allocBits位图重建 64 位补码缓存allocCache freeindex % 64把 freeindex 对齐到低位——这样 mcache 的nextFreeFast就能直接用 CTZtrailingzeros指令 O(1) 找到第一个空闲槽位。这正好接上 06. Small 对象分配 讲的快速路径。5. spanBudget 100清扫开销与空间浪费的权衡spanBudget是cacheSpan里最有意思的工程参数// If we sweep spanBudget spans without finding any free// space, just allocate a fresh span. This limits the amount// of time we can spend trying to find free space and// amortizes the cost of small object sweeping over the// benefit of having a full free span to allocate from. By// setting this to 100, we limit the space overhead to 1%.spanBudget:100— mcentral.go:94-107它解决什么问题想象一个极端场景堆里有很多 partial/full 的 unswept span每个只有一两个空闲槽位。如果无限循环扫下去一个cacheSpan调用可能清扫几十上百个 span分配延迟飙高虽然吞吐未必差。spanBudget 100设了一个上限最多尝试清扫 100 个 unswept spanpartial 和 full 各占额度找不到就放弃直接grow()分配新 span。为什么 100 恰好对应1% 空间开销假设每个被扫的 span 平均只提供一个空闲槽位而每个 span 通常有几十上百个对象。扫 100 个 span 只为拿到 1 个槽位新分配的 span 里就会留下约 1% 的浪费空间本来可以全用上的。100这个值正好把空间开销控制在 ~1% 以内。权衡的本质方向选择后果增大 budget多扫几个 span空间浪费更小但分配延迟更高减小 budget少扫 span早分配新 span延迟更低但空间浪费更大 100平衡点延迟可控空间开销 ~1%已知局限源码注释也承认这是个折中方案最坏情况下可能扫 100 个 span 才拿到一个槽位延迟被限制但吞吐很差。TODO 里提到将来可以用持续的 free-to-used 预算来替代。// TODO(austin,mknyszek): This still has bad worst-case// throughput. For example, this could find just one free slot// on the 100th swept span. That limits allocation latency, but// still has very poor throughput. We could instead keep a// running free-to-used budget and switch to fresh span// allocation if the budget runs low.— mcentral.go:101-1066. uncacheSpan归还逻辑与 stale 判定uncacheSpan是cacheSpan的逆操作被 mcache 的refill和releaseAll调用用于把 mcache 用完的 span 归还给 mcentral。// Return span from an mcache.//// s must have a span class corresponding to this// mcentral and it must not be empty.func(c*mcentral)uncacheSpan(s*mspan){ifs.allocCount0{throw(uncaching span but s.allocCount 0)}sg:mheap_.sweepgen stale:s.sweepgensg1// Fix up sweepgen.ifstale{// Span was cached before sweep began. Its our// responsibility to sweep it.//// Set sweepgen to indicate its not cached but needs// sweeping and cant be allocated from. sweep will// set s.sweepgen to indicate s is swept.atomic.Store(s.sweepgen,sg-1)}else{// Indicate that s is no longer cached.atomic.Store(s.sweepgen,sg)}// Put the span in the appropriate place.ifstale{// 已 stale直接清扫清扫会把 span 放到正确的列表ss:sweepLocked{s}ss.sweep(false)}else{ifint(s.nelems)-int(s.allocCount)0{// 还有空闲放回 partialSweptc.partialSwept(sg).push(s)}else{// 没有空闲放回 fullSweptc.fullSwept(sg).push(s)}}}— mcentral.go:205-248stale 判定这个 span 是漏网之鱼吗stale:s.sweepgensg1— mcentral.go:211回顾 sweepgen 状态表sg1表示sweep 之前就被缓存的 span。当一个 span 在上一轮 GC 的 sweep 开始前就被 mcache 缓存了sweepgen 旧代1那么新 GC 周期开始时它逃过了清扫——因为它当时在 mcache 手里不在任何 mcentral 列表里。这样的 span 归还时就是stale过期的它需要被清扫内存里可能有垃圾对象直接调用ss.sweep(false)就地清扫清扫逻辑会自动把它放到正确的 partial/full、swept/unswept 列表ifstale{atomic.Store(s.sweepgen,sg-1)// 标记为需要清扫ss:sweepLocked{s}ss.sweep(false)// 立即清扫}— mcentral.go:214-221, 236-237非 stale 路径直接归类如果 span 不是 stalesweepgen sg或sg3它已经清扫过了只需按空闲情况归类ifint(s.nelems)-int(s.allocCount)0{c.partialSwept(sg).push(s)// 还有空闲槽位 partial}else{c.fullSwept(sg).push(s)// 全满了 full}— mcentral.go:239-246注意永远只 push 到 swept 列表。因为uncacheSpan归还的 span 都是清扫过的或刚被当场清扫的放进 swept 列表才能被cacheSpan的第 ① 级直接复用。为什么不用 sweepLocker注释解释了原因// We dont use a sweepLocker here. Stale cached spans// arent in the global sweep lists, so mark termination// itself holds up sweep completion until all mcaches// have been swept.— mcentral.go:232-235stale span 不在全局清扫列表里没有并发清扫者会碰它因此不需要锁mark termination 阶段会等所有 mcache 都清扫完才继续。7. grow从 mheap 获取新 span四级查找全部落空时cacheSpan调用grow()直接从 mheap 要一个新的 span// grow allocates a new empty span from the heap and initializes it for cs size class.func(c*mcentral)grow()*mspan{npages:uintptr(gc.SizeClassToNPages[c.spanclass.sizeclass()])s:mheap_.alloc(npages,c.spanclass)ifsnil{returnnil}s.initHeapBits()returns}— mcentral.go:250-259关键点页数查询gc.SizeClassToNPages[spc.sizeclass()]查到该 size class 对应的页数1~10 页然后调mheap.alloc(npages, spanclass)。返回 nil 语义mheap_.alloc失败OOM返回 nilcacheSpan会把它透传给refill后者throw(out of memory)。初始化位图s.initHeapBits()建立 span 的堆位图heapBits为后续 GC 扫描指针做准备。grow 的意义grow让 mcentral 永远有一个兜底即使堆里所有 span 都被用满也总能从 mheap 拿到全新的页。这也把 mcentral 的复杂性控制在有限范围内——它不必保证 100% 找到旧 span找不到就造一个新的。8. 调用链串联把 mcentral 的四个核心函数放回整体架构中mcache.refill(spc) [07] ├─ uncacheSpan(旧 span) [08] 归还 │ ├─ stale? s.sweep(false) 直接清扫 │ └─ 非 stale partialSwept / fullSwept └─ cacheSpan() [08] 分配 ├─ ① partialSwept.pop() 已清扫部分空闲O(1) ├─ ② partialUnswept sweep 未清扫部分空闲budget100 ├─ ③ fullUnswept sweep 未清扫满 spanbudget100 └─ ④ grow() mheap.alloc() [09]mheap.central[spc].mcentral ├─ partial[2] / full[2] spanSet 双缓冲 ├─ cacheSpan() 四级查找分配 ├─ uncacheSpan() 归还 stale 清扫 └─ grow() mheap 兜底— 参见大纲附录 B.1mcentral 把mcache 的本地无锁和mheap 的全局加锁之间的鸿沟填上了它对每个 size class 提供独立的、带双缓冲优化的 span 池让大部分 span 周转不触碰全局堆锁。下一篇 09. mheap 将进入全局堆管理器看mheap.alloc内部的页分配和 span 初始化。小结机制用途源码位置partial[2]/full[2]按 GC 状态分双缓冲 spanSetmcentral.go:22-46角色互换sweepgen/2%2索引取反零数据搬移mcentral.go:59-79四级查找partialSwept partialUnswept fullUnswept growmcentral.go:82-199spanBudget 100限制清扫开销空间浪费 ≤1%mcentral.go:107tryAcquire认领 unswept span 的清扫权防止重复清扫mcentral.go:126stale 判定sweepgen sg1直接清扫归还mcentral.go:211,236grow从 mheap 分配新 span initHeapBitsmcentral.go:250-259