指令重排序与内存屏障

一本正经地胡闹 2021-03-31

展开全文

从老版glibc的一个bug说开来

之前我在公众号中，发表过这么一篇文章：

这篇文章里面提到了老版本的glibc（2.13以前）中的排序函数qsort()有一个在并发时会出现core dump的bug。那段代码如下：

void qsort_r(void* b, size_t n, size_t s, __compar_d_fn_t cmp, void* arg) {
    size_t size = n * s;
    char* tmp = NULL;
    struct msort_param p;

    /* For large object sizes use indirect sorting.  */
    if (s > 32) {
        size = 2 * n * sizeof(void*) + s;
    }

    if (size < 1024)
        /* The temporary array is small, so put it on the stack.  */
    {
        p.t = __alloca(size);
    } else {
        /* We should avoid allocating too much memory since this might
        have to be backed up by swap space.  */
        static long int phys_pages;
        static int pagesize;

        if (phys_pages == 0) {
            phys_pages = __sysconf(_SC_PHYS_PAGES);

            if (phys_pages == -1) {
                phys_pages = (long int)(~0ul >> 1);
            }

            phys_pages /= 4;

            pagesize = __sysconf(_SC_PAGESIZE);
        }

        /* If the memory requirements are too high don't allocate memory.  */
        if (size / pagesize > (size_t) phys_pages) {
            _quicksort(b, n, s, cmp, arg);
            return;
        }
... ...

core dump原因就是用到了两个static的变量：

      static long int phys_pages;
      static int pagesize;

static变量默认会初始化成0。

 if (size / pagesize > (size_t) phys_pages) {

这种除法操作并发的时候会出现除0，导致coredump。也就是pagesize = 0，而单看串行逻辑，上述代码没有问题。因为前面pagesize已经被赋值了：

            pagesize = __sysconf(_SC_PAGESIZE);

这个就是读取系统配置，获取页的大小赋值给pagesize。

那么为什么会core呢？首要原因当然是pagesize的赋值的if其判断条件不是pagesize为0，而是phys_pages 是否为0。因此存在race condition，phys_pages被赋值，但是pagesize还没走到赋值的位置的时候，其他线程开始做qsort排序，导致跳过了这个if，直接去做了那个除法操作。

所以见过一些老代码在服务初始化的时候，先用qsort()给随机数做一下排序，目的就是给这两个static变量初始化。

为此，有人给老版的glibc提过修复的merge request：

https:///bugzilla/show_bug.cgi?id=11655

主要改动的diff是：

-      if (phys_pages == 0)
+      if (phys_pages == 0 || pagesize == 0)
        {
          phys_pages = __sysconf (_SC_PHYS_PAGES);

修改判断条件，将两个静态变量是否为0都判断了一遍。很简单易懂是吧，看着也能解决这个并发的bug，但是最终glibc没有合入这个修改。而这其中的原因呢，就要引出今天我们的议题了：编译器和CPU会对指令进行重排序！

先看下最终glibc的修改版(glibc 2.13开始）是这样：

    if (pagesize == 0) {
      phys_pages = __sysconf (_SC_PHYS_PAGES);

      if (phys_pages == -1)
        phys_pages = (long int) (~0ul >> 1);

      phys_pages /= 4;

      /* Make sure phys_pages is written to memory.  */
      atomic_write_barrier ();

      pagesize = __sysconf (_SC_PAGESIZE);
    }

这段代码和之前版本的主要diff有二，第一是if条件中改为直接判断pagesize，没有用 || 去判断两个static变量是否为0；第二呢就是在pagesize真正被赋值之前加入了一个atomic_write_barrier() 后面会讲到。

剧透一下，这段代码的含义就是用汇编语言，在这里加入了一个内存屏障。好了，开始讲讲什么是指令重排序，什么是内存屏障吧！

指令重排序

编译器为了提高程序的性能，有时不会按照程序代码对应的指令顺序来执行，而是乱序执行（Out-of-order execution）。比如我们用gcc编译器都用过O2参数。当然了说乱序有点夸张，它是在保证程序结果不变的情况下，对看似没有关联的语句进行重排序。然而它的重排序有个弊病，就是它仅能从单线程的串行逻辑角度去判断两个语句有没有依赖关系。不能判断多线程环境下的依赖关系。因而会导致问题。

当然不仅编译器，CPU也会对程序进行优化，从而导致指令的重排。

前文所述的那个没被合入的merge request，如果合入则最终代码如下：

        if (phys_pages == 0 || pagesize == 0) {
            phys_pages = __sysconf(_SC_PHYS_PAGES);

            if (phys_pages == -1) {
                phys_pages = (long int)(~0ul >> 1);
            }

            phys_pages /= 4;

            pagesize = __sysconf(_SC_PAGESIZE);
        }
        if (size / pagesize > (size_t) phys_pages) {
            _quicksort(b, n, s, cmp, arg);
            return;
        }

在第一个if块中，其实phys_pages和pagesize是没有依赖关系的，所以直接可能被优化成这样执行：

        if (phys_pages == 0 || pagesize == 0) {
            pagesize = __sysconf(_SC_PAGESIZE);

            phys_pages = __sysconf(_SC_PHYS_PAGES);

            if (phys_pages == -1) {
                phys_pages = (long int)(~0ul >> 1);
            }

            phys_pages /= 4; 
        }
        if (size / pagesize > (size_t) phys_pages) {
            _quicksort(b, n, s, cmp, arg);
            return;
        }

这样又会产生一种新的race condition，那就是某个线程中的qsort其pagesize和phys_pages都通过__sysconf()赋值完成了，但是phys_pages /=4;还没有被执行，彼时另外一个线程又在执行qsort，导致它判断pagesize和phys_pages都不等于0了，就跳过了if直接执行：

        if (size / pagesize > (size_t) phys_pages) {

这个时候的phys_pages是还没有除以4的，所以这个除法虽然不core了，但整个表达式的逻辑也不正确！

内存屏障

内存屏障（memory barrier）又叫内存栅栏（memory fence），其目的就是用来阻挡CPU对指令的重排序。我们再看下glibc最终修改后的代码。

    if (pagesize == 0) {
      phys_pages = __sysconf (_SC_PHYS_PAGES);

      if (phys_pages == -1)
        phys_pages = (long int) (~0ul >> 1);

      phys_pages /= 4;

      /* Make sure phys_pages is written to memory.  */
      atomic_write_barrier ();

      pagesize = __sysconf (_SC_PAGESIZE);
    }

atomic_write_barrier()，顾名思义就是加一个”写类型“的内存屏障，其实它是一个宏，展开为：

__asm('':::'memory')

这个就是通过嵌入汇编代码的方式加了一个内存屏障。让phys_pages成功写入之后再去给pagesize赋值（根据注释也可见一斑）。

此外前面我有提到，编译器和CPU都会导致指令的重排序。这里的 __asm('':::'memory') 其实加的是编译器的内存屏障（也叫优化屏障），也就是说它能阻止编译器不会对这段代码重排序，并不会阻止CPU的重排序。那么CPU不需要管吗？

X86的内存模型

在谈及CPU时，通常会把变量的读操作称为load，变量的写操作称为store。两两组合因而会出现4类读写操作：

LoadLoad屏障：保证前面的Load在后面的Load之1前完成
StoreStore屏障：保证前面的Store在后面的Store之前完成
LoadStore屏障：保证前面的Load在后面的Store之前完成
StoreLoad屏障：保证前面的Store在后面的Load之前完成。

对于我们常见的x86 架构的CPU来说，它有一个相对强大的内存模型。它能直接保证前面三种屏障，也就是说不需要去写汇编指令去阻止CPU对前面三种类型读写操作的重排。但x86 CPU无法保证StoreLoad类型的屏障。对于我前面所讲的qsort的例子，这个场景并不属于StoreLoad。貌似是StoreStore，先后对两个变量进行写入。所以不需要给CPU加内存屏障。

当然如果要加的话，也有办法是这样写：

__asm volatile ('mfence' ::: 'memory')

mfence是针对CPU的内存屏障。

内存屏障与MESI

看完前面的内容，相信你已经认识到内存屏障对于阻止编译器和CPU指令重排序的作用，但其实CPU的内存屏障却不止如此，还记得本系列的上一篇文章介绍了CPU的缓存一致性协议MESI吗？

其实内存屏障与MESI也有关系。

CPU的内存屏障如果只是保证指令顺序不会乱，也未必会让程序执行符合预期。因为MESI为了提升性能，引入了Store Buffer和Invalidate Queue。所以内存屏障还有其他功能：

写类型的内存屏障还能触发内存的强制更新，让Store Buffer中的数据立刻回写到内存中。读类型的内存屏障会让Invalidate Queue中的缓存行在后面的load之前全部标记为失效。

顺带一提，X86 CPU是没有实现Invalidate Queue的。

参考资料

https://en./wiki/Out-of-order_execution
https://en./wiki/Memory_ordering
Who ordered memory fences on an x86?
https://www.ics./~aburtsev/cs5460/lectures/lecture13-memory-ordering/lecture13-memory-barriers.pdf
https://mechanical-sympathy./2011/07/memory-barriersfences.html