LLC slice 哈希:一条物理地址怎么被拆进十几个缓存分片,以及没公开的哈希函数怎么被逆向
在 缓存替换策略 里我们讨论过一个 cache set 内部怎么选人淘汰,在 写分配与写回策略 里看过命中后的数据怎么落地。这两篇都默认末级缓存(Last Level Cache,LLC)是一整块。真实的多核处理器里,LLC 被切成十几个甚至几十个分片(slice),散布在 ring/mesh 总线的各个节点上——一条物理地址到底进哪个 slice,由一个不公开的哈希函数说了算。这一篇就讲这个 LLC slice 哈希。
本文要回答的问题
- LLC 为什么要分片,不分片会遇到什么物理障碍?
- 一条物理地址从发出到命中某个 slice,中间经过哪几步?
- slice 哈希函数要防什么——冲突、偏斜各指什么?
- Intel 从不公布哈希公式,研究者是怎么把它逆向出来的?
- 这件事对性能分析和安全攻防有什么实际意义?
一、为什么 LLC 必须分片
先看矛盾。一个 8 核桌面 CPU 的 LLC 通常有 16~24MB,如果做成一整块,它到每个核的距离不可能相等——离得远的核访问延迟会显著变差,而且这么大的阵列本身读出延迟就高。更麻烦的是所有核的末级请求都往一个地方挤,单一入口的带宽根本撑不住。
工程上的解法是把 LLC 按容量均切成 S 份(S 常等于核数或核数的两倍),每份贴着某个核或总线节点放,这叫 SNUCA(静态非一致缓存访问):每个 slice 容量、相联度、替换逻辑都一样,区别只在「离你多远」。L1/L2 miss 之后,请求不再发往「那个大 LLC」,而是先算出一个 slice 编号,再把请求路由到对应的节点。路由靠片上互连(ring 或 mesh)完成,所以 slice 距离不同,LLC 命中延迟也不同——这就是为什么现代 CPU 的 LLC 延迟不是一个数,而是一个 30~70 拍的区间。
这张图里最关键的一点是:slice 哈希只作用于 slice 的选择,不改变 slice 内部的寻址。进了 slice 之后,set index 和 tag 还是照老办法从地址里切——换句话说,LLC 分片是在「S 个小 cache 里选一个」这一层加的选择器,每个小 cache 内部的组织方式与不分片的 cache 完全一致,替换策略也照旧(见 缓存替换策略)。
二、哈希函数要解决的两个问题:冲突与偏斜
最朴素的方案是直接取地址的中间几位当 slice 编号,比如 slice = PA[10:7]。这在顺序访问下工作得很好——连续的 cache line 会轮流落到不同 slice,天然条带化。但真实程序的地址分布不是均匀的,朴素方案会栽在两个坑里:
坑一:冲突(conflict)。 很多程序的访问步长是 2 的幂(遍历一个 4KB 对齐的二维数组、按页扫描),如果哈希只取少数几个低位,步长为 2^k 的访问序列会把所有 line 砸进同一个 slice。一个 slice 被打爆、其他 slice 闲置,等效 LLC 容量直接缩水 S 倍,miss 率暴涨。
坑二:偏斜(skew)。 即使不是恶意步长,地址位本身的分布也不均匀——高位地址在进程空间内变化缓慢,低位变化快。取固定几位做 slice 号,长期看各 slice 的负载会系统性失衡,热的更热。
所以真实的 slice 哈希是一个 XOR 折叠网络:从物理地址里挑 10~20 个位,每个输出位都是若干输入位异或的结果。异或的好处是只要参与位里有一个是均匀分布的,输出就近似均匀;多个输出位用不同的输入组合,能把「步长为 2 的幂」这类坏序列打散到所有 slice 上。以 Sandy Bridge 时代被逆向出的一个 2-slice 哈希为例,输出位是 PA 的第 6 到第 32 位中约 17 个位的异或——单个地址位翻转,slice 归属就可能变,步长规律被彻底搅碎。
| 设计目标 | 朴素位截取 | XOR 折叠哈希 |
|---|---|---|
| 顺序访问条带化 | 好 | 好 |
| 2 的幂步长防冲突 | 差(全砸一个 slice) | 好(被打散) |
| 地址分布偏斜 | 敏感 | 不敏感 |
| 硬件代价 | 零 | 几十个异或门,1 拍内算完 |
| 可预测性 | 完全可预测 | 不公开即不可预测 |
哈希计算只有几十个异或门,在请求路径上加不到一拍延迟,这是它能常驻硬件的原因。
三、Intel 不公布,那就逆向出来
Intel 的优化手册从不写 slice 哈希公式(AMD 的部分型号在公开文档里给过)。但研究者和攻防双方都需要它,于是逆向工程成了一门小产业。经典玩法分四步:
第一步:造地址对。 利用 huge page 或 pagemap 拿到可控的物理地址,构造大量「只差一个或少数几个地址位」的地址对。
第二步:观测 slice 归属。 同一 slice 的两条 line 会共享该 slice 的容量和端口,表现为逐出冲突或访问延迟差异。用 Prime+Probe 式的时序测量,判断两个地址是否落在同一 slice——这就是分类器。
第三步:学出函数。 把「同 slice / 不同 slice」的标签和地址位喂给一个逐位假设检验:如果翻转地址位 i 会改变分类结果,说明位 i 参与了哈希。再逐对测试位之间的异或关系,最终解出一个线性方程组——因为哈希是纯 XOR 网络,整个函数是 GF(2) 上的线性系统,几千个样本就够解出来。
第四步:验证。 用解出的公式预测一批新地址的 slice 归属,再用时序测量抽查,全对即收工。
2015 年前后 Sandy Bridge/Ivy Bridge 的哈希就是这样被完全公开的,后续 Skylake 引入 mesh 和更复杂的非 slice 对齐分布(部分型号 slice 数不是 2 的幂,输出要经过一次取模或查表),逆向难度上了一个台阶,但方法论没变:只要哈希只依赖物理地址且是确定函数,时序侧信道就一定能把它磨出来。讽刺的是,「不公开」防不住逆向,却实实在在地挡住了认真做性能调优的人——这也是为什么近年不少声音呼吁厂商直接公开公式。
四、对性能分析和安全的实际意义
性能侧。 知道 slice 哈希,才能解释一些反直觉现象:为什么把数据结构按 2 的幂对齐后 LLC miss 率反而上升(哈希前的坏步长、或哈希与 set index 的不良叠加);为什么 TLB 与页表遍历缓存 层面换了大页之后 LLC 行为也变了(物理地址位分布变了,slice 均衡随之变化)。做 硬件预取器 类实验时,跨 slice 的请求分布也决定了你在核上测到的带宽是不是互连的真实上限。排 IPC 问题时,LLC 延迟区间拉宽往往就是 slice 距离在作怪,这点在 IPC 瓶颈拆解 的框架里属于「内存子系统等待」。
安全侧。 几乎所有 LLC 侧信道(Prime+Probe、Flush+Reload 的跨核变体)都要先解决「目标地址在哪个 slice」——哈希未公开时这是攻击的第一道门槛,哈希被逆向后攻击者可以精准构造冲突集,防御方也可以反过来用它做 slice 感知的页着色隔离。可以说,slice 哈希是缓存攻防地图上每一场战役的开场哨。
这一篇在知识体系里的位置
本篇是微架构长尾层,向上承接 缓存替换策略 与 写分配与写回策略(单个 slice 内部的组织),向旁连接 TLB 与页表遍历缓存(物理地址从哪来)、硬件预取器(地址流形态怎么影响 slice 负载)与 IPC 瓶颈拆解(slice 距离如何落进可测的延迟数字)。
总结
LLC slice 哈希是多核处理器把一条物理地址分发到十几个缓存分片的 XOR 折叠网络:它用几十个异或门换取顺序访问的条带化、2 的幂步长的防冲突和长期负载的均衡;厂商不公开公式,但哈希是纯线性函数,时序侧信道加 GF(2) 方程组就能完整逆向——理解它,才能解释 LLC 延迟区间、容量缩水和一切跨核缓存攻防。