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

wait_rabbit

今天建了两个模型，被结果彻底弄迷糊了，特向大家请教。

============================ 我是美丽的分割线 =================================

模型1：

开启 3 个内核线程，分别绑定在 cpu0 、cpu1、cpu2 上。thread 0 作一个计数器，thread 1 每隔 5 秒将 cnt 备份为 cnt_bk，然后清零 cnt，thread 2 每隔 5 秒打印 cnt_bk。

1. int cnt;
   
2. int cnt_bk;
   
3. 
   
4. (cpu0)                 
   
5. 
   
6. while(1) {      
   
7.         xxoo;      
   
8.         cnt++;
   
9.         ooxx;                                                
   
10. }
    
11.                                        
    
12. 
    
13. (cpu1)   
    
14. 
    
15. while(1) {
    
16.         msleep(5000);
    
17.         cnt_bk = cnt;
    
18.         cnt = 0;
    
19. }
    
20. 
    
21. (cpu2)
    
22. 
    
23. while(1) {
    
24.         msleep(5000);
    
25.         printk("%d\n", cnt_bk);
    
26. }

复制代码

分析：在第一个 5 秒之前， 只有 cpu 0 的 cache 0 中保存有 cnt 的值，根据 MESI 协议，其状态应当为“shared”。当第一个 5 秒 到来之际，cpu 1 的 cache 1 中第一次存入 cnt，并将其存入 cnt_bk 中，然后对 cnt 清零，这时 cpu 1 使用一个“read invalidate”消息。于是 cpu 0 上 cache 0 中 cnt 缓存变得无效，cpu 1 将 0 写入 cache 1中后，cache 1 状态转换为“modified”。然后 cpu 0 继续累加，使用 “read invalidate” 从 cpu 1 的 cache 1 窥视到新的 cnt 值 0，紧接着使 cache 1 中的新值 0 无效，于是 cpu 0 的 cache 状态转换为 “modified”。最后 cpu 0 将 cnt++ 后的值 1 通过“writeback” 写入内存。当下一个 5 秒到来之际， cpu 1 应该从内存中获取最新的 cnt 值。

预测： 假设 cnt 在 5 秒内的正常增长值为 1 亿，那么每次打印出来的 cnt_bk 也应该为 1 亿。

结果： 每次打印出来的 cnt_bk ，大多数为 1 亿，有少量的 2 亿，偶尔还会出现 3 亿。

猜测原因： 从现象上看，是 cpu 1 对 cnt 的清零动作并没有产生效果，似乎 cache 0 和 cache 1 之间的信号延时了？但这个延时达到了 5 秒，甚至是 10 秒之久。这就让人觉得不可思议了。不知道 cpu 1 到底是如何读出 2亿 这个不正常的值？


============================ 我是美丽的分割线 =================================


于是我更改模型，将全部数据使用原子操作。这回就一切 ok 了，打印值都为 1 亿。

1. 
   
2. automic64_t cnt;
   
3. automic64_t cnt_bk;
   
4. 
   
5. cpu0
   
6. 
   
7. while(1) {
   
8.         xxoo;
   
9.         automic64_inc(&cnt);
   
10.         ooxx;
    
11. }
    
12. 
    
13. (cpu1)   
    
14. 
    
15. while(1) {
    
16.         msleep(5000);
    
17.         automic64_set(&cnt_bk, automic64_read(&cnt));
    
18.         automic64_set(&cnt, 0);
    
19. }
    
20. 
    
21. (cpu2)
    
22. 
    
23. while(1) {
    
24.         msleep(5000);
    
25.         printk("%d\n", automic64_read(&cnt_bk));
    
26. }

复制代码

分析： 第 5 秒到来时，cpu 1 会先发出一个 ”read invalidate“ 信号，cpu 0 收到之后便会使自己的 cache 无效，然后 cpu 1 锁住总线，再将 cnt 清零，并写入自己的 cache 1，然后解除总线锁定。cpu 0 由于“read invalidate”，于是从 cpu 1 的 cache 1 获取新的 cnt 值 0，然后进行下一步操作。所以一切正常。


============================ 我是美丽的分割线 =================================

评论：最后寡人悲催地发现，除了模型 2 会锁总线之外，上边两个模型的分析流程简直就是一模一样的。在 MESI 协议下，锁总线的意义究竟何在呢？模型 1 到底哪里出了问题？还是我的分析过程完全就是错的？还请大家不吝赐教。

liuiang

本段代码并不能从根本上解决这个问题，所以是错误的，小朋友不要参考~~~~，留下来程序是作为反面教材用的~~~~~~~

1. #include <stdio.h>
   
2. #include <pthread.h>
   
3. 
   
4. unsigned int cnt;
   
5. unsigned int cnt_bk;
   
6. 
   
7. void * cpu0(void * arg)
   
8. {
   
9.     while(1) {
   
10.         __asm__ __volatile__(
    
11.             "mfence\n\t"
    
12.             "incl %0\n\t"
    
13.             "mfence"
    
14.             : "=m" (cnt)
    
15.             : "m" (cnt)
    
16.             :"memory");
    
17.     }
    
18. }
    
19. void * cpu1(void * arg)
    
20. {
    
21.     while(1) {
    
22.         sleep(5);
    
23.         __asm__ __volatile__("mfence":::"memory");
    
24.         cnt_bk = cnt;
    
25.         cnt = 0;
    
26.         __asm__ __volatile__("mfence":::"memory");
    
27.     }
    
28. }
    
29. void * cpu2(void * arg)
    
30. {
    
31.     while(1) {
    
32.         sleep(5);
    
33.         printf("cnt_bk = 0x%08x\n", cnt_bk);
    
34.     }
    
35. }
    
36. 
    
37. int main(int argc, char * argv[])
    
38. {
    
39.     pthread_t taskId1, taskId2, taskId3;
    
40. 
    
41.     pthread_create(&taskId1, NULL, cpu0, NULL);
    
42.     pthread_create(&taskId2, NULL, cpu1, NULL);
    
43.     pthread_create(&taskId3, NULL, cpu2, NULL);
    
44. 
    
45.     void * tret;
    
46.     pthread_join(taskId1, &tret);
    
47.     pthread_join(taskId2, &tret);
    
48.     pthread_join(taskId3, &tret);
    
49. 
    
50.     return 0;
    
51. }

复制代码

wait_rabbit

回复 2# liuiang

大贤，您直接用内存屏障应该是没问题的。

我想不明白的是，第一个模型中，我分析的那个 MESI 协议为神马不起作用。似乎这里不关乱序的事情吧。如果能够确保 cache一致性，读取应该都能得到正确的值。




   

zylthinking

mark 一把， 我也想不明白;
不会是 cpu0 刚刚变成invalidate, 然后马上 ++, 导致 cpu1 刚刚获得的值立马invalidate, 然后这两个就这样拉锯， 导致cnt = 0 总是无法写出？
有脚趾头想似乎也能知道太不可能了。。。。。。。。。， 好歹也是 5秒。。。。。。。

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

liuiang

问题不是出在cache一致性协议上，而是出在write buffer上。


编辑：前半句没问题，后半句的描述不全面，事实上write buffer只是问题的一个方面，仅牵扯到incl的读部分。

zylthinking

liuiang 发表于 2013-01-06 12:17
问题不是出在cache一致性协议上，而是出在write buffer上。

跟 write buffer 有什么关系？cpu 1 的invalidate 似乎必须是cpu 0 将值更新到内存而不仅仅是write buffer 就算完的； 不对， 我也不确定会不会更新到内存， 但如果 CPU 0侦测到 read invalid request 是肯定返回的最新值的， 相同，  CPU 1 也会返回其最新值； 也就是 0， 和 0 更新没更新到 内存 没太多关系

zylthinking

貌似明白了， 这个其实和cache一致性， 和write buffer 都没有任何关系， 而是和寄存器有关系

首先揭示一个错误， 照这个帖子的理解， 其实是可以得出 MESI 能够解决任何多线程同步问题的， 因为任意不同步， 都会被 MESI 的 read probe, read probe before write 给同步， 这显然是不正确的
剩下的问题就简单了， 就是 cache 一致性在什么时候起作用， 自然是 read 的时候， 往细了说， 恐怕牵扯的就太多了， 我也不了解， 往粗了说应该可以说是 CPU 将值load 进寄存器的那一瞬间， 在这个时候， 可以保证是一致的（自然， 在更细粒度看来， 估计是错误的说法）

那么再看汇编层面， 照现象来看， 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 操作被丢弃。

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

liuiang

二楼程序无法从根本上解决楼主问题，根本问题还是write buffer中的数据不能强行flush出。x86貌似有个WBINVD的指令吧，不过只能工作在内核态。

另外CPUID这类串行指令不确定是否能解决该问题，你们有时间可以试试看，木有多少理论根据的。


编辑：此楼也不靠谱，write buffer只是一个方面。另外WBINVD和CPUID都不能解决这个问题。

zylthinking

liuiang 发表于 2013-01-06 14:22
二楼程序无法从根本上解决楼主问题，根本问题还是write buffer中的数据不能强行flush出。x86貌似有个WBINVD ...

就我目前理解而言， 你的代码根本就是错误的； 你的代码达不到目的， 如果出 2 亿 3 亿的， 还会照样出； 而且， 你将内存屏障当作临界区来用， 更是根本性的错误
严格来说， 你将 mfence 从你代码中去掉， 和你加上几乎没有区别； 你代码中真正起了一点作用的其实是incl 了一个内存地址， 想借助汇编语句单条语句的原子性； 但实际上也未必能如愿， 实际的情况是， 在多核下， 单条汇编指令的原子性已经不能保证了， 就算不是所有的汇编指令， 至少你这个 incl memory 应该包含在其中

liuiang

貌似此题不用lock前缀，也不用锁，是无法解决的啊~~~~~

即使WBINVD貌似也不行。