前言
这是以读书笔记的形式记录的关于 memory barrier 背后细节的一篇文章, 某些篇幅可能会直接引用到原文, 而不会在本文中再次赘述. 所以可能会需要一份原文.
Intorduction
为什么要引入 memory barriers. 参考原文了解, 一句话来描述的话是因为编译期指令乱序以及 cpu 乱序执行的存在, 所以需要引入 memory barrier. 原文这里并未介绍什么是 memory barriers, 大概是字如其名显而易见了吧.
reordering memory references，按我理解会进行 memory reference reorder 的操作有编译期的乱序，cpu的乱序执行以及 cpu cache 的存在而带来的副作用. 其中编译乱序以及乱序执行都是很简单明了的, 就是打乱指令的顺序, 使用 memory barriers 之后可以确保 barrier 之前的指令不会排到 barrer 之后, barrier 之后的指令不会排到 barrier 之前, 完美解决了此类问题. 所以原文并未过多介绍编译乱序与 CPU 乱序, 而是重点描述了 CPU cache.
an evil that stems from the fact that CPUs are orders of magnitude faster than are both the interconnects between them and the memory they are attempting to access. 按我理解这句话是说由于 CPU 自身速度远高于 CPU 之间互联的速度, 远高于 CPU 与 memory 之间互联的速度这个事实导致了 evil 的产生. 这里 CPU 自身速度是指 CPU 指令执行的速度以及 CPU 访问寄存器的速度. CPU 之间互联是指 CPU cache line 之间的互联, 参见 Figure1. CPU 与 memory 之间互联速度慢导致 cache 的引入, cache 的引入意味着各个 cpu 之间必须要进行通信来进行 cache 管理, 然后 cpu 之间互联速度慢导致了 store buffer, invalid queue 的引入, 即通过 store buffer, invalid queue 来减少 cpu 之间, cpu 与 memory 之间通信的次数. 而 store buffer, invalid queue 的引入导致了 evil 产生.
1 Cache Structure
CPU, CPU cache, memory 的宏观结构, 参见 Figure 1; 按我理解, 这里 CPU0, CPU1 均是一个单独的 CPU, 其内有若干个 CPU 核心. 这里 Cache 是多级 Cache, 级别越高, 容量越小, 访存速度越快; 每一个 cpu 核心都具有自己的高级 cache, 低级 cache 被同属于同一个 CPU 内的所有核心共享. cache lines; cache line 是 Cpu cache 与 memory 数据交换的最小单位.
CPU cache 结构; 参见 Figure 2, This cache has sixteen ‘sets’ and two ‘ways’ for a total of 32 ‘lines’. 每一个 ‘line’ 对应着一个 cache entry, which can contain a 256-byte cache line. CacheEntry 中并不单单仅有个 256-byte 的 cache line, 还会有一些其他字段, CacheEntry 的大概定义如下:
type CacheEntry struct {
// 当前 cache entry 对应的内存物理地址. 注意这里不是虚拟地址.
phyaddr uintptr
cacheline [256]byte
state byte // state, 存放着当前 CacheEntry 的 MESI 状态
}
In hardware parlance, this is a two-way set-associative cache, and is analogous to a software hash table with sixteen buckets, where each bucket’s hash chain is limited to at most two elements. The size (32 cache lines in this case) and the associativity (two in this case) are collectively called the cache’s ‘geometry’. 这里将 memory 按照 cache line 大小划分为 block 序列, “phyaddr” 中存放着是 memory block 的首地址, 从原文 “in addition to that line’s physical address” 来看这里存放的是物理地址而不是虚拟地址, 事实上琢磨一下之后可以发现这里确实应该存放物理地址. 通过 “memory block 首地址 % cache set size”(由于 cache set size 是 2^n, 所以取余可以用位于来实现) 运算可以得到 memory block 所在的 set, 再根据当前 set 内 cache entry 空闲状态来最终确认 memory block 所在的 cache entry.
CPU cache 与 memory 之间的关联; 前面提过 Cpu cache 与 memory 数据交换的最小单位是 cache line, 这里假设 cache line 256byte. 这里可以将 memory 以 256byte 为大小划分为 block 序列. 当访问 addr 发生 cache miss 时, 会将 addr 所在的 memory block 加载到 cpu cache 中. 由于 memory block 首地址 must be 256-byte aligned, the low eight bits of each address are zero, and the choice of hardware hash function means that the next-higher four bits match the hash line number, 这里之所以说 four bits 这么个具体数字是原文举例使用的 cache 具有 16 个 sets, 取余 16 得到的结果可不就是 next higher four bits 嘛.
cpu cache 与 memory 在一些场景下的交互, 参见原文; 并以此引入了 cache-coherency protocols.
2 Cache-Coherence Protocols
cache coherence protocol, 缓存一致性协议, Cache-coherency protocols manage cache-line states so as to prevent inconsistent or lost data. 在现实世界 CPU 内部实现中, 缓存一致性协议往往具有多达数十数百的 state. 原文出于教学目的使用了 four-state MESI cache-coherence protocol.
2.1 MESI States
MESI 具有哪些状态, 以及每个状态蕴含了哪些事实, 参见原文介绍. 比如处于 modified 状态蕴含着如下事实:
- cache 仅被当前 cpu 拥有.
- 当前 cpu 对该 cache 有过写操作, 最新数据仅存在于当前 cache 中.
原文这里对状态蕴含了哪些事实介绍地不是很严谨, 比如原文这里指出处于 shared 状态的 cache line 中的数据与内存保持一致. 但是在原文后面却又有了处于 shared 状态的 cache line 其内数据较之内存而言会更新.
各个 CPU cache line 之间可直接通信来交换数据以及控制命令. 我一直以为 cache line 不会在 CPU cache 之间流转的, 现在看来还是会的, 毕竟 cache 与 cache 之间的通信效率应该还是远大于 cache 与 memory 的.
2.2 MESI Protocol Messages
MESI Protocol Messages, 介绍了在 the CPUs are on a single shared bus 这种场景下, 实现 mesi 协议所需要的信息, 具体需要哪些 messages 参见原文. 这里有一些我也没搞懂的细节, 比如在 read response 中，cache 与 memory 是如何商议谁来响应的呢？处于 modified 的 cache 在响应之后自身状态如何变化呢？invalidate，invalidate ack 中，当 cache 中不存在指定 cache line 时是否还会返回 invalidate ack？如果由于故障导致 cache 无法回复 invalidate ack，又该怎么样呢？此时那个等待回复的 CPU 会一直 hangup 么? 暂且不管这些细节了, 继续往下看吧.
single shared bus 的通信模型; 原文并未介绍而且我也不是很了解, 这个根据原文支离片碎的信息总结的; 需要通过 single shared bus 进行通信的设备都挂载到 bus 上, single shared bus 一次只需要一个设备发送信息, 当多个设备同时想要发送信息时需要竞争类似加锁一样的机制最终只有一个设备拿到发送权. 按我理解此时把 cpu 与 cpu cache 作为一个整体了，这里各种 MESI Protocol Messages 是指这个 cpu cache 整体与其他 cpu cache 整体通信时会用到的 message，在整体内 cpu 与自己的 cache 通信并不会用到这一套。
2.3 MESI State Diagram
本节根据 MESI 各个状态以及之前定义的 message 信息，讲述了 Mesi 状态如何切换。具体参考原文。按我理解，这里的描述不是很严谨，所以我才会有这么多疑问。
Q: 事务a中如果 write back 被其他 cache 截胡导致write back未写入 memory 而是写入了其他 cache 该咋整？ Q: 事务h为何要 write back？shared 状态时 cache 与 memory 一致啊 Q: 事务 f 为啥没有 writeback，shared 要求与 memory 保持一致，所以从 modified 到 shared 势必需要 write back 的吧 Q: 事务 c 与事务 j 结合来看，modified 状态可就丢失了啊 Q: 事务 k 如果 read responses 来自 memory 可咋整 Q: 根据事务 k 与事务 j, 结合 2.4 Table1 为何在读取时, 是 invalid -> shared? 此时并没有其他 CPU 持有 cache line, 变为 exclusive 岂不是更贴切? 而且变为 exclusive 后续 CPU 在 store 数据时也不需要再发现 invalidate message 了么.
同样的, 这些疑问暂且也就放着吧, 不影响后面的学习.
2.4 MESI Protocol Example
本节以 single-line direct-mapped caches in a four-CPU system 为模型演示了在一组操作下时 CPU cache line 状态是如何变化的. 这里 ‘single line direct mapped caches’ 原文并未详细介绍是个什么结构, 按我理解应该是个 one set one way 的 cache, 此时 address 0x0, address 0x8 对应着同一个 cache entry.
3 Stores Result in Unnecessary Stalls
参见原文, 原文提供了一个场景, 在原生 MESI 协议中, 存在某些不必要的 stall(阻塞). 为了优化掉这种不必要的 stall, 引入后面的章节.
3.1 Store Buffers
StoreBuffer; 为了解决上面提到的 stall 而引入的 StoreBuffer 组件, 参见原文中图了解 store buffers 位于系统中的位置. CPU 写操作只需写入到 store buffer, 这样的写入对 cpu cache, memory 来说是不可见的, 所以以 cpu cache, memory 的视角来看就是什么都没有发生过, 所以zhe’li不需要额外的协议交互. 此时就可以避免第3节的 stall 现象。
3.2 Store Forwarding
首先原文举了个例子演示了在引入上述 Store buffer 之后存在的一个 bug，bug的表现参见原文，bug 的主要原因在于 store buffer 存放着最新数据，但是 CPU 在读取操作中仅会读取 cache 与 memory 导致读取到了老数据。所以引入了 Store forward，cpu 在读取操作中会优先读取 store buffer。
按我理解, 这时的 store buffer 更像是更高一级的 cache，而且是是个仅在 cpu 内部存在的 local cache. 对 store buffer 的读写操作对 cpu cache, memory 那一级来说是完全不可见的，以 cpu cache, memory 视角来看读写就像从未发生过一样, 所以不需要涉及到 MESI 协议交互从而减少了 stall, 提高了效率. 但正由于读写不涉及到 MESI 导致可能会出现不一致的情况。这里举个例子，cpu0 分配内存拿个一个指针，更新指针指向的内容，把指针本身以 relaxed 语义原子写入某个变量中; cpu1 同样 relaxed 语义加载该变量拿到指针值，cpu1 对指针值解引用看到的指针指向内容可能还是 cpu0 修改前的, 因为 cpu0 的修改操作可能仍在 cpu0 的 store buffer 中。所以才引入了 C++ 中 acquire release 这些语义。
3.3 Store Buffers and Memory Barriers
在介绍 mb 之前，原文首先举了个例子演示了在没有 mb 时会存在的一个不一致性案例，参见原文了解具体信息. 这里有很多细节，比如并不是 store 动作总会写入到 store buffer 中，而是在指定地址尚未存在于 cache 中才会写入. 同时还会发送个 read invalidate(而不是 invalidate), 为何会发送 read invalidate 而不是 invalidate 原文最后会有答案。
The memory barrier smp_mb() will cause the CPU to flush its store buffer before applying each subsequent store to its variable’s cache line. The CPU could either simply stall until the store buffer was empty before proceeding, or it could use the store buffer to hold subsequent stores until all of the prior entries in the store buffer had been applied.
在引入 mb 之后解决了之前案例的不一致性，参见原文了解。注意这里 mb 的位置，以及一些细节比如 CPU 执行 mb 时会给当前 store buffer 所有 entry 设置 mark，会在最后一个 marked entry 从 store buffer 中刷新出去的同时刷新 store buffer 中剩余 entry(之前还在想如果 b 一直在 store buffer 中对外不可见该咋整)。
4.3 Invalidate Queues and Memory Barriers
invalidate queues，是指 CPU 在收到其他 CPU 发来的 invalidate request 时，queues it, and immediately responds to it. 本来我以为 cache invalidate 一个 cache line 是个很快的操作没必要整这种优化吧. 后来想到此时还可能会涉及到 writeback，即将被 invalidate 的那个 cache entry 中 cache line 的内容写入到内存中. 以及还会破坏 cpu 的局部性，毕竟一个 cache entry 中存放着 256byte 的 cache line 内容, 都 invalidate 了会有些可惜。
invalidate queue 机制随之带来的不一致的案例，参见原文。所以再次需要 memory barrier 指令。
memory barrier 指令与 invalidate queue 的交互，the memory barrier instructions can interact with the invalidate queue, so that when a given CPU executes a memory barrier, it marks all the entries currently in its invalidate queue, and forces any subsequent load to wait until all marked entries have been applied to the CPU’s cache. 利用这种 memory barrier 可以解决上面那个不一致的案例, 具体参考原文.
5 Read and Write Memory Barriers
现实世界中，一般是把操作 store buffer，操作 invalidate queue 的指令拆分开来. 即 Roughly speaking, a “read memory barrier” marks only the invalidate queue and a “write memory barrier” marks only the store buffer, while a full-fledged memory barrier does both.
上述中的 barrier 指令，除了具有操作 store buffer, invalidate queue 的功能之外; 还会确保编译器乱序，CPU 乱序不会将 barrier 之前的指令乱序到 barrier 之后，以及不会把 barrier 之后的指令乱序到 barrier 之前。参见原文了解 read barrier, write barrier, full barrier 指令在这方面的功效。
8 Are Memory Barriers Forever?
memory barrier 是不是系统必需？各方分别提出各自看法，具体参见原文。总之随着硬件发展，可能以后就不需要 memory barrier 了。这么说来就像 Golang 之父 Rob Pike 在 Less is exponentially more 中说的
One thing that really bothered me—and I think Ken and Robert as well—was the new C++ memory model with atomic types. It just felt wrong to put such a microscopically-defined set of details into an already over-burdened type system. It also seemed short-sighted, since it’s likely that hardware will change significantly in the next decade and it would be unwise to couple the language too tightly to today’s hardware.
所以 C++11 引入各种姿势的 memory order 真的是个明智的做法么？按我理解可能不是一个明智的做法, 但至少是个符合工程实践的做法, 毕竟现有的 CPU 中具有 memory barrier, 为了充分压榨发挥出 CPU 的最佳性能, C++ 中需要引入这么个抽象.
