smp cache line并发访问

blake326

smp比如8核，比如我现在有一个数组，a[8] = {0}; 地址是0xd000000;这样a[0]  ~ a[7]都是在同一个cache line中的, 并且每个cpu对应的cacheline都是share状态的。那么考虑下面并发场景：
cpu0 写 a[0] = 0;
cpu1 写 a[1] = 1;
cpu2 写 a[2] = 2;
...
cpu7 写 a[7] = 7;
结果是：
cpu0， 把cache line写成了0，。。。， 然后发出一个inv 广播到其他cpu
cpu1， 把cache line写成了。1.。。， 然后发出一个inv 广播到其他cpu
。。。

问题是：
1. 假设同时发生的，最终cache line的值是多少？
2. 某个cpu 写完自己的cache line，发出去一个inv 广播，然后又收到一个inv 事件，那么这个事件如何处理呢？
3. 这种代码是不是无法保证cache line等于 0,1,2,3,4,5,6,7

chishanmingshen

回复 1# blake326

通过内存中转。比如：给a[1]赋值后，cpu0和cpu1的cache line已经都一样了。
而且，我觉得你这个case，8次操作，仅在第一次操作会发一次inv，并不是8次。

blake326

回复 2# chishanmingshen


    cpu0  写完 a[0] = 0, 会发一个inv事件到其他cpu，其他cpu会inv 相应的cache line，这样就会感知到cache变化，但是假设多个cpu同时写的话，不能保证这个顺序了。

参考：
http://bbs.chinaunix.net/thread-3593865-1-1.html

chishanmingshen

回复 3# blake326


   我觉得你这个问题跟乱序不大涉及。
   可能8次写是乱序的，但是总有一个cpu先让自己的cacheline 从S到M，这样其他的只能读内存了。

   所以最终结果是ok的，虽然损耗时间。

arm-linux-gcc

今天面试刚好被问到了这个问题
最终各个core的inner cache都会是invalid
outter cache最终会是0 1 2 3 ... 7

这种用法性能低下，最好用per-cpu，以达到避免竞争同一个line的目的

wth0722

回复 5# arm-linux-gcc

為什麼outter cache最終會是0 1 2 3 ... 7 ?

我個人認知如下，如有錯幫忙釘正

第一個搶到cache的人會去更新 & invalid

第二搶到cache的，會發現該cache line已經invalid (也就是所謂的write miss)

所以他就寫到記憶體，並在去cache上找一個cache line存放 (他不一定上一個cache line位置)

第二個寫完時，他又去下invalid

第三個搶到cache的，就會跟第二個一樣

以後以此類推


   

arm-linux-gcc

以outter include inner这种情况来说：因为arm cortex-a15就是这种情况
core 0写了inner line，会使得core 1的相应inner line变为invalid，同时core 0的这次写会同步到outter上
core 1写自己的inner line时会发现没有命中，于是就会去outter找有没有能够命中的line，于是发现outter中有能够命中的，于是会写outter，同时也使得core 0的inner变为invalid

cortex-a9则是可以配置成exclusive或inclusive的
exclusive时应该就最终在outter和inner中都没有能够命中的

blake326

回复 7# arm-linux-gcc


core 0写了inner line，会使得core 1的相应inner line变为invalid，同时core 0的这次写会同步到outter上


这个顺序是如何保证的呢？
core1 变成invalid是因为会收到core0的inv request。但是在core1收到inv request之前的话，core1就开始写cache怎么办？

从这个帖子里http://bbs.chinaunix.net/thread-3593865-1-1.html 来说，core0写完cache之后，应该会发出inval request到其他core，并且会接受其他core 的inval 成功的reply。整个逻辑还是搞不清楚现在。



   

blake326

我现在怀疑这种并发访问可能会发生只有cpu2成功写入的结果，例如： 0 0 2 0 0 0 0 0


bbs.chinaunix.net/forum.php?mod=viewthread&tid=1972593
这个里面讲的 Figure 2. Data Destruction by Dirty Cache Lines 问题，感觉有点类似。

blake326

参考cache一致性的一个文档：
http://bbs.chinaunix.net/thread-4070325-1-1.html

基本的mesi协议中，cache存在四种状态e，s，m，i
i invalid， 表示该数据没有对应cache line
e excluisve，表示该数据有效，并且只存在本cpu的cache line中。其他cpu没有cache该数据。
m modify, 表示该数据有效，但是与存储器中的不一致，并且只存在本cpu的cache line中。其他cpu没有cache该数据。
s share, 表示该数据有效，并且多个cpu都有该数据的cache line并且他们的状态都是share。

然后，当CPU对一段存储器进行写操作时，如果这些数据在本地Cache中命中时，其状态可能为E、S、M或者O。
     状态为E或者M时，数据将直接写入到Cache中，并将状态改为M。
     状态为S时，数据将直接写入到Cache中，并将状态改为M，同时其他CPU保存该数据副本的Cache行状态将从S或者O迁移到I(Probe Write Hit)。
     状态为O时，数据将直接写入到Cache中，并将状态改为M，同时其他CPU保存该数据副本的Cache行状态将从S迁移到I(Probe Write Hit)。


这里，我们不管状态o（owner), 其实我现在的问题就是：
     状态为S时，数据将直接写入到Cache中，并将状态改为M，同时其他CPU保存该数据副本的Cache行状态将从S或者O迁移到I(Probe Write Hit)。这个操作是不是原子的？

假设某个时间点，所有cpu该数据都是cache share的。那么这时：
cpu0, 写了 0 0 0 0 0 0 0
cpu1, 写了 0 1 0 0 0 0 0
cpu2，写了 0 0 2 0 0 0 0


如果，该操作时原子的话，那么这种并发疑问就没有了，结果势必会使cache line变成, 0 1 2 3 4 5 6 7。而且怎样保证原子性的呢？