有关原子操作和 cache 一致性问题

liuiang

顺便多谢楼主，学到很多东西。

wait_rabbit

zylthinking 发表于 2013-01-06 12:06
而且， 一直不是很清楚这类打架情况 MESI  会怎么处理， 在 CPU1 read invalidate 获得最新值， 立马被 CPU 0 的 invalidate 给将值抢回去， 那么 CPU 1 在继续执行前， 会再次发出invalidate吗？..

这个打架问题我是这样理解的。

如果 cpu 1 read invalidate 获取了最新值， 那么 cpu 0 的状态就转换为“shared”，就必须在获得 cpu  1 的许可之后，才能进行下一步操作，这个就是强制延迟了。不过我不清楚如果这个最新值被 2 个以上的 cpu 取得的话（比如 cpu 1 和 cpu 2 都获取了），是不是需要这 2 个cpu都同意才行？而这 2 个 cpu 之间是不是也得有个什么交流？想想就复杂了。

wait_rabbit

zylthinking 发表于 2013-01-06 13:13

首先揭示一个错误， 照这个帖子的理解， 其实是可以得出 MESI 能够解决任何多线程同步问题的， 因为任意不同步， 都会被 MESI 的 read probe, read probe before write 给同步， 这显然是不正确的
...

这个完全同意，我也是在想如果 MESI 真的能够一把搞定，那内核各种同步方式纯粹是自找没事儿。

zylthinking 发表于 2013-01-06 13:13

那么再看汇编层面， 照现象来看， cnt 应该没有被优化成寄存器， CPU 0 的操作其实可以分解为
load cnt to r1
set r2 = r1 + 1
mov r2 to cnt
这三个操作，  cache 一致性保证了第一个语句时是一致的； 但在执行第二条语句时， 很可能 CPU 1 已经将 cnt 变成 0  了， 但 r1 是寄存器， 和 cnt 在 CPU 0 看来， 根本没有关系，  和 其有关系的是  L1 缓存中的entry, 那么 CPU 0做的操作就是将L1缓存失效， 但不影响 r1, 自然最终结果是不影响 r2, 最后 store r2 到 cnt 时， CPU 0的 read probe before write将 L1 entry 中的对应值更新为 0, 但有什么关系呢， r2还是会覆盖这个值， 导致的结果就是 CPU 1的 cnt = 0 操作被丢弃。.

我觉得在逻辑上说得通，毕竟 automic64_t 也就是一个 long int 加了 volatile 罢了，直接对内存操作，就正好解决了这个问题。

zylthinking 发表于 2013-01-06 13:13
如果这个分析是正确的， 2楼的内存屏障代码， 很可能达不到目的， 甚至就内存屏障原理而言， 用在这个情景下， 似乎没觉得有什么理由， 毕竟， 想把内存屏障当作锁来使用， 根本就是一个错误..

内存屏障这个东东一直都挺放心不下的，就知道在概念上是为了防止乱序。但我觉得乱序是不是应该分两种情况，一种是处理器自己内部的乱序，一个是编译器自作聪明造成的乱序。这两者有什么具体的区别吗？

另外一个问题是，在多 cpu 情况下，这个内存屏障又是如何生效的。比如如下情况：

1. 
   
2. 
   
3. cpu 0                                  cpu 1
   
4. 
   
5. data = xxoo;        
   
6. wmb();                                if (flag) {
   
7. flag = 1;                                   do_ooxx(data);
   
8.                                      }
   
9. 
   

复制代码

很显然，如果 cpu 0 不加屏障，那么 cpu 1 很可能会直接挂掉。

但是现在这种加了屏障的情况下，我觉得似乎仍然有问题，还是在于cache一致性。 假设 data 和 flag 分别保存在 cache 0 中的不同列，如果 data 所在列比较繁忙，那么相应的更新消息有可能会比 flag 发送得晚，导致 cpu 1 先收到 flag 的值，这样 cpu 1 下一步就死翘翘了。

如果按照所谓的配对使用原则，给 cpu 1 加上读屏障：

1. 
   
2. cpu 0                                  cpu 1
   
3. 
   
4. data = xxoo;        
   
5. wmb();                                if (flag) {
   
6. flag = 1;                                rmb();                     
   
7.                                         do_ooxx(data);
   
8.                                      }
   
9. 
   

复制代码

似乎仍然不能阻止上述情况下 cpu 1 先读到 flag 的值。那么，究竟这个内存屏障是如何起到作用的呢？有劳了。

wait_rabbit

回复 11# liuiang


我这叫抛砖引玉， 感谢兄台的回帖，同样受益颇多。

liuiang

楼主的理解没有什么问题，从软件角度来说，内存屏障与cache一致性没有什么关系。

你加上rmb()之后的程序一定是正确的。

对于CPU0来说，内存屏障的语义是：如果wmb()在data和flag之间，任何其他CPU（当然需要rmb()的配合），都会先感知到data发生了变化，然后flag才发生变化，

不会出现data所在bank繁忙而flag先被更新的情况，因为那样违背语义。

不过Alpah处理器有一个依赖屏障，正是要解决这个繁忙的问题，但----依赖屏障是一个比read屏障更弱的屏障，用rmb()也能解决问题。

zylthinking

编译器乱序叫做优化屏障， 其实就是 asm 关键字前加上一个 volatile, 作为提示之前之后各成一组， 不可跨组排序指令。

至于第二个问题， 我只能针对 arm 解释， x86 等没看过； 以下是 arm 手册表述：

Data Memory Barrier (DMB)
The DMB instruction is a data memory barrier. The processor that executes the DMB instruction is referred to as the executing processor, Pe. The DMB instruction takes the required shareability domain and required access types as arguments. If the required shareability is Full system then the operation applies to all observers within the system.
A DMB creates two groups of memory accesses, Group A and Group B:
Group A
Contains:
• All explicit memory accesses of the required access types from observers in the same required shareability domain as Pe that are observed by Pe before the DMB instruction. These accesses include any accesses of the required access types and required shareability domain performed by Pe.
• All loads of required access types from observers in the same required shareability domain as Pe that have been observed by any given observer, Py, in the same required shareability domain as Pe before Py has performed a memory access that is a member of Group A.
Contains:
• All explicit memory accesses of the required access types by Pe that occur in program
order after the DMB instruction.
• All explicit memory accesses of the required access types by any given observer Px in the same required shareability domain as Pe that can only occur after Px has observed a store that is a member of Group B.
Group B
Any observer with the same required shareability domain as Pe observes all members of Group A before it observes any member of Group B to the extent that those group members are required to be observed, as determined by the shareability and cacheability of the memory locations accessed by the group members. Where members of Group A and Group B access the same memory-mapped peripheral, all members of Group A will be visible at the memory-mapped peripheral before any members of Group B are visible at that peripheral.

因此， wmb 套上屏障的描述， 产生的语意就是保证屏障前后在写操作完成的顺序是按代码顺序来的。 但不保证被观察到的顺序也是按顺序来的， 这就是为什么需要 rmb 的原因， rmb 保证观察顺序与代码顺序的一致性； 因此， 如果能观察到 flag 的更改， 则肯定能观察到 data 的更改， 因为 wmb 保证了 data 的更改一定比 flag 的更改先完成。

假设 data 和 flag 分别保存在 cache 0 中的不同列，如果 data 所在列比较繁忙，那么相应的更新消息有可能会比 flag 发送得晚，导致 cpu 1 先收到 flag 的值，这样 cpu 1 下一步就死翘翘了。

从 MESI 的角度， 似乎这个描述也有问题吧， 我也不是很懂 MESI ,只是猜测；
首先， write 方是 CPU 0, CPU 0 在写之前， 发送RFO 消息， 这个消息invalidate  其他 CPU 的cache, 然后才写； 在 invalidate 完成之前， 他应该会等待一个特定延时， 以保证所有 CPU 全部收到了这个消息； 而一旦写到 cache, 它并没有发什么更新消息， 而是其他 CPU 在使用值之前， 主动查询， 由于 wmb 保证在 CPU 0 本地 cache, data 更新一定在 flag 前完成， 而 rmb 保证 其他CPU 一定是先查询flag, 那么一旦 flag 查询结果是更新后的值， 自然后继的 data 查询不可能查到旧值。

hmsghnh

明显，问题由于cnt++; 不是原子操作。改成原子操作应该就没这问题了。这里加内存屏障应该没什么作用吧。

不知道你们说了一大堆硬件的cache同步有什么关系。cnt = 0; 这个人家cache肯定保证写进去了，只是又被新的cnt++给覆盖了而已。

blake326

mkjjjjjjjjj

wait_rabbit

zylthinking 发表于 2013-01-07 10:02
编译器乱序叫做优化屏障， 其实就是 asm 关键字前加上一个 volatile, 作为提示之前之后各成一组， 不可跨组 ...

  辛苦辛苦，受益匪浅。

因为不怎么懂汇编（只看得懂add mov 一类简单的操作），所以特地查了一下。

1. 
   
2. #define rmb() asm volatile("lfence":::"memory")
   
3. 
   
4. lfence：在lfence 指令前的读操作必须在 lfence 指令后的读操作前完成。
   

复制代码

这就是处理器自身的保证了。

话说我一直有个问题不大清楚，比如 MESI 协议，它总应该有一个最小的时间粒度吧（发出一条消息，至收到一条响应消息），而 cpu 的两条指令之间也有一个最小时间粒度。不知道这两个粒度在数量级上到底相差多少。

zylthinking 发表于 2013-01-07 10:02
首先， write 方是 CPU 0, CPU 0 在写之前， 发送RFO 消息， 这个消息invalidate  其他 CPU 的cache, 然后才写； 在 invalidate 完成之前， 他应该会等待一个特定延时， 以保证所有 CPU 全部收到了这个消息； 而一旦写到 cache, 它并没有发什么更新消息， 而是其他 CPU 在使用值之前， 主动查询， 由于 wmb 保证在 CPU 0 本地 cache, data 更新一定在 flag 前完成， 而 rmb 保证 其他CPU 一定是先查询flag, 那么一旦 flag 查询结果是更新后的值， 自然后继的 data 查询不可能查到旧值。...

zyl 兄这个描述更严谨，我前边的表述有误。就是那个红字部分，应该不是一个特定延时（特定延时显然不靠谱，万一出啥事儿了，延时不管用咋办），而是等待所有的 cpu 都返回 “invalidate acknowledge”响应消息。

wait_rabbit

liuiang 发表于 2013-01-07 09:26
楼主的理解没有什么问题，从软件角度来说，内存屏障与cache一致性没有什么关系。

你加上rmb()之后的程序 ...

多谢liu兄，我一时想错了。

=============

我的本意不是指 cpu 0 写 cache 的顺序，而是 指 cpu 0 发送 MESI 消息给 cpu 1 的顺序。有可能是 flag 的消息先发送，而 data 后发送。

后果就是： cpu 1 的 flag 所在 cache，由于 read invalidate 得到了最新值（1），但是 data 所在 cache 由于没有收到消息，从而认为自己的数据就是正确的。