Store Buffer
当cpu需要的数据在其他cpu的cache内时,需要请求,并且等待响应,这显然是一个同步行为,优化的方案也很明显,采用异步。
思路大概是在cpu和cache之间加一个store buffer,cpu可以先将数据写到store buffer,同时给其他cpu发送消息,
然后继续做其它事情,等到收到其它cpu发过来的响应消息,再将数据从store buffer移到cache line。
该方案逻辑上有漏洞,需要细化,我们来看几个漏洞。比如有如下代码:
// 初始状态下,假设a,b值都为0,并且a存在cpu1的cache line中(Shared状态), a = 1; b = a + 1; assert(b == 2);
cpu0 要写入a,将a=1写入store buffer,并发出Read Invalidate消息,继续其他指令。 cpu1 收到Read Invalidate,返回Read Response(包含a=0的cache line)和Invalidate ACK,cpu0 收到Read Response,更新cache line(a=0)。 cpu0 开始执行b=a+1,此时cache line中还没有加载b,于是发出Read Invalidate消息,从内存加载b=0, 同时cache line中已有a=0,于是得到b=1,状态为Modified状态。 cpu0 得到 b=1,断言失败。 cpu0 将store buffer中的a=1推送到cache line,然而为时已晚。
造成这个问题的根源在于对同一个cpu存在对a的两份拷贝,一份在cache,一份在store buffer,而cpu计算b=a+1时,a和b的值都来自cache。
仿佛代码的执行顺序变成了这个样子:
b = a + 1; a = 1; assert(b == 2);
Store Forwarding
store buffer可能导致破坏程序顺序的问题,硬件工程师在store buffer的基础上,又实现了”store forwarding”技术:,
cpu可以直接从store buffer中加载数据,即支持将cpu存入store buffer的数据传递(forwarding)给后续的加载操作,而不经由cache。
但是在高并发场景下仍然存在漏洞,示例如下:
// 初始状态下,假设a,b值都为0,a存在于cpu1的cache中,b存在于cpu0的cache中,均为Exclusive状态,cpu0执行foo函数,cpu1执行bar函数 void foo() { a = 1; b = 1; } void bar() { while (b == 0) continue; assert(a == 1) }
cpu1执行while(b == 0),由于cpu1的Cache中没有b,发出Read b消息 cpu0执行a=1,由于cpu0的cache中没有a,因此它将a(当前值1)写入到store buffer并发出Read Invalidate a消息 cpu0执行b=1,由于b已经存在在cache中,且为Exclusive状态,因此可直接执行写入 cpu0收到Read b消息,将cache中的b(当前值1)返回给cpu1,将b写回到内存,并将cache Line状态改为Shared cpu1收到包含b的cache line,结束while (b == 0)循环 cpu1执行assert(a == 1),由于此时cpu1 cache line中的a仍然为0并且有效(Exclusive),断言失败 cpu1收到Read Invalidate a消息,返回包含a的cache line,并将本地包含a的cache line置为Invalid,然而已经为时已晚。 cpu0收到cpu1传过来的cache line,然后将store buffer中的a(当前值1)刷新到cache line
出现这个问题的原因在于cpu不知道a, b之间的数据依赖,cpu0对a的写入需要和其他cpu通信,因此有延迟,
而对b的写入直接修改本地cache就行,因此b比a先在cache中生效,导致cpu1读到b=1时,a还存在于store buffer中。
从代码的角度来看,foo函数似乎变成了这个样子:
void foo() { b = 1; a = 1; }
foo函数的代码,即使是store forwarding也阻止不了它被cpu"重排",虽然这并没有影响foo函数的正确性,但会影响到所有依赖foo函数赋值顺序的线程。