硬件模型

Memory barrier跟cache的实现有很强的相关性, 掌握cache的实现硬件对理解memory barrier很有帮助. 以基本的MESI协议为例, 它主要实现了4种状态:

• Modified. Cache lines in the “modified” state can thus be said to be “owned” by the CPU. Because this cache holds the only up-to-date copy of the data, this cache is ultimately responsible for either writing it back to memory or handing it off to some other cache, and must do so before reusing this line to hold other data.
• Exclusive. The “exclusive” state is very similar to the “modified” state, the single exception being that the cache line has not yet been modified by the corresponding CPU, which in turn means that the copy of the cache line’s data that resides in memory is up-to-date. However, since the CPU can store to this line.
• Shared. A line in the “shared” state might be replicated in at least one other CPU’s cache, so that this CPU is not permitted to store to the line without first consulting with other CPUs. As with the “exclusive” state, because the corresponding value in memory is up to date, this cache can discard this data without writing it back to memory or handing it off to some other CPU.
• Invalid. A line in the “invalid” state is empty, in other words, it holds no data. When new data enters the cache, it is placed into a cache line that was in the “invalid” state if possible. This approach is preferred because replacing a line in any other state could result in an expensive cache miss should the replaced line be referenced in the future.

MESI保证一条cache line在任意时刻最多只有一个owner, 这样所有的写操作都是串行的, 而不会出现同一时刻有多个owner的情况, 那样不同的CPU就可能读到不同的值了.

如果只是上面的架构, 那么从硬件角度就比较容易做到访问cache的顺序和程序顺序一致, 从而不用额外的memory barrier. 但是上面的实现会有性能问题, 所以又引人了2样东西:

• Store buffer. 如果当前cpu没有该cacheline, 那么在写的时候需要读取cacheline的内容 (cacheline还有其他的数据), 不论是从其他cpu读还是从内存读都没有必要是同步的, 毕竟这里只是写而已. 通过引入store buffer, 把要写的数据暂时放在这里, 读cacheline就可以后台做了.
• Invalidate Queue. store buffer太小, 满了的话相当于又回到从前, 这个时候需要从store buffer清理出空间, 这样原来的异步操作又变回同步了. 这里比较慢的地方是对方cpu invalidate cacheline会比较慢 (read慢应该也没太好的办法), 所以加上了invalidate queue, 对方cpu在收到通知后马上ack, 实际apply invalidate message的时间自己决定.

加上上面的store buffers和invalidate queue之后, 系统变成这样了:

这样就相当于在读写两端都引人了另外一层缓冲, memory barrier也就有了必要.

Memory Barrier

Write Memory Barrier

先考虑store buffer引入的问题, 如果在CPU0上执行以下指令可能出现什么情况?

a = 1;
b = 1;

虽然program order是先写a再写b, 因为store buffer存在, 可能会出现:

1. 执行a = 1, 因为cacheline不在本cpu的cache中, 所以暂时存在store buffer中 (不能写cacheline), 这个时候还是会发出read invalidate消息出去, 但是不用等消息的ack返回即可执行下一条指令
2. 执行b = 1, 因为本cpu是该cacheline的owner, 直接就写到cacheline去了
3. 其他cpu收到1发出去的read invalidate消息

上面的步骤可以看出, 在2-3之间的窗口, 对其它cpu而言, b的可见性早于a, 也就是说其它cpu读到b = 1时, 可能还看不到a的修改. 这样我们就需要增加write memory barrier来保证其它cpu至少有办法保证先看到a的修改. 这里的有办法指的是其他cpu也需要配合. 我们把代码修改成这样:

a = 1;
smp_wmb();
b = 1;

那么write memory barrier怎么实现呢? 暴力点的可以在b写cacheline之前, 把所有store buffer给flush完, 确保其它cpu先收到invalidate消息 (收到该消息就表示那个cpu的数据已经更新), 轻量级一点的可以把b也放到store buffer去, 按照先进先出的顺序写cache.

Read Memory Barrier

再考虑invalidate queue引入的问题, cpu0上依然执行上面加过的代码, 在cpu1上执行如下代码:

while (b == 0) continue;
assert(a == 1);

考虑如下场景:

1. cpu0上的初始状态a是shared, b是modified, a = 0发出invalidate消息到cpu1, 并且收到ack后写cache, b因为是owner直接写cache
2. cpu1去cpu0上读b, 返回1, 退出while循环
3. cpu1读a, 注意这个时候cpu1上a的cacheline还是shared, 还没来得及apply invalidate消息, 也就是说读到一个老的值, 从而assert失败

为了确保能读到a的新值, 进行如下修改:

while (b == 0) continue;
smp_rmb();
assert(a == 1);

那么read memory barrier可以怎么实现呢? 暴力点可以在读a前, 把invalidate queue中的所有消息都apply一遍.

Full Memory Barrier

既然有了read/write memory barrier, 那是不是一起使用就是一个full memory barrier了呢?

smp_wmb + smp_rmb != smp_mb

注意write memory barrier只管#StoreStore的顺序, read memory barrier只管#LoadLoad的顺序, full memory barrier还要管#StoreLoad和#LoadStore的顺序, 比如在x86上, write memory barrier和read memory barrier分别都可以为空, 但是full memory barrier却不能.

• write memory barrier. 像上面说的, 轻量级的实现只需要保序, 并不需要flush所有store buffer
• read memory barrier. 同样只需要对#LoadLoad保序, 如果前面都没有未完成的load, 那么什么都不用做

一般来说, full memory barrier会同时flush store buffer和apply invalidate queue. 为什么x86上 (还有其他的架构比如spark) 不允许#StoreStore, #LoadLoad, #LoadStore乱序, 却单独允许#StoreLoad出现? 大胆猜测一下, 要防止#StoreLoad乱序, 需要在每次load的时候隐式的flush store buffer, 这个代价非常大, 而其他类型的开销则比较小, 特别地, invalidate queue有可能实现的非常快, 比如hash, 甚至不使用invalidate queue?

举个例子

这个是之前我们使用的内核上碰到的一个问题, 后来定位到是upstream已经解了的一个memory barrier的问题.

/* Use either while holding wait_queue_head_t::lock or when used for wakeups
 * with an extra smp_mb() like:
 *
 *      CPU0 - waker                    CPU1 - waiter
 *
 *                                      for (;;) {
 *      @cond = true;                     prepare_to_wait(&wq, &wait, state);
 *      smp_mb();                         // smp_mb() from set_current_state()
 *      if (waitqueue_active(wq))         if (@cond)
 *        wake_up(wq);                      break;
 *                                        schedule();
 *                                      }
 *                                      finish_wait(&wq, &wait);
 *
 * Because without the explicit smp_mb() it's possible for the
 * waitqueue_active() load to get hoisted over the @cond store such that we'll
 * observe an empty wait list while the waiter might not observe @cond.
 *
 * Also note that this 'optimization' trades a spin_lock() for an smp_mb(),
 * which (when the lock is uncontended) are of roughly equal cost.
 */
static inline int waitqueue_active(wait_queue_head_t *q)
{
    return !list_empty(&q->task_list);
}

问题出现在调用这个函数的地方:

unlock_new_inode(struct inode *inode)
{
    lockdep_annotate_inode_mutex_key(inode);
    spin_lock(&inode->i_lock);
    WARN_ON(!(inode->i_state & I_NEW));
    inode->i_state &= ~I_NEW;               // <-- @cond
    smp_mb();                               // <-- missing
    wake_up_bit(&inode->i_state, __I_NEW);  // <-- waitqueue_active()
    spin_unlock(&inode->i_lock);
}