小议C语言标准库排序函数qsort曾经的bug

                                 背景

曾经在某厂工作期间，发现大量C++项目的代码，都在用qsort()而非std::sort()来排序。不知道是出于某种特殊的动机，还是仅仅是历史原因。这倒也罢，紧接着我发现所有C++的Server项目，在main函数中靠前的位置都有一段特殊代码。用qsort给一个个数超过1024的随机数数组做一下排序。一时不明就里，百度一番后才发现qsort在多线程中调用会有bug，需要在多线程逻辑开始之前做一次排序来避免。

                              问题描述

但是，这仅仅是旧版的glibc。gblic 2.13以前的qsort实现有问题，在长达20年的岁月里，qsort都并非是线程安全的，在多线程环境中中调用qsort会有除0的风险，从而导致core dump。然而在后来的新版本中早已修复了这一bug，所以其实现在不需要做事先的初始化操作了！老同事们。

可以用ldd --version命令查看一下glibc的版本。注意不是gcc的版本！

原因是它内部使用了static变量，所以qsort不是严格意义上的线程安全函数。之所以没有一棒子打死说它不安全，那是因为有回避风险的途径。

解决方法就是在开启多线程处理之前，在主线程中(比如main函数开始位置)用qsort随便跑一次排序（要大于1024个元素），这样就能给其中的static变量做初始化。

我们直接看一份2.12源码，阅读stdlib/msort.c。下面请原谅这个代码风格，这就是源码！】

看一下，qsort()

void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
  return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
}

本质调用的是 qsort_r()。再简单看一下qsort_r() 【格式化了一下……】

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;
        }
... ...

可以看到两个static的变量：

  static long int phys_pages;
      static int pagesize;

这两个变量是控制需要分配多少内存的。大概就是就是页的数量和页大小。这两个变量之所以是static，那是因为获取这两个值貌似只需要获取一次，不需要每次排序都获取一遍，因此用了static。同时因为是static的，所以会自动初始化为0（static变量在bss段中，bss段整个空间会被清零）。

最下面有个size/pagesize，就是coredump的元凶。pagesize赋值的地方是它上面的if中，if的准入条件是另外一个变量phys_pages==0。也就是说在多线程的时候，可能一个线程进入到了if中，执行完：

phys_pages =__sysconf(_SC_PHYS_PAGES);

phys_pages有值了，但是pagesize的赋值操作在下一句，这个 间隙 之中。有另外一个线程走到了 if。判断 phys_pages 不为0了。开始了size / pagesize 的除0之旅……从而引发coredump。

                              解决方案

而从2.13版本开始，这个if是这样的：

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);
    }   
    if (size / pagesize > (size_t) phys_pages) {
       _quicksort (b, n, s, cmp, arg);
      return;
    }

可以看下这个if准入条件里面判断的是pagesize了。也许你会说，那phy_pages会不会没被写入就参与下面的比较了呢？

size / pagesize > (size_t) phys_pages

尽管不会除0，但是比较结果是不是不符合预期啊？

如果程序能严格按照代码的语句顺序执行的话，其实不会。因为给pagesize赋值是最后一句，如果pagesize 在if判断中不等于0，那么它前面的语句应该都执行过了，因此phy_pages应该是赋好值的。

但是这是理论上的，为了提高性能，实际可能出现指令的重排序。导致结果并不一定按照语句顺序来执行。因此glibc又给qsort加了一层保障。

仔细看if 逻辑内，在pagesize赋值之前也多了一句：atomic_write_barrier();

这其实不是一个函数，而是一个宏，展开为：

__asm ("" ::: "memory")

这其实不是标准C代码，这是GCC扩展支持的在C程序中嵌入汇编的语法。加入了一个内存屏障。

我对体系结构了解有限，但据我理解，内存屏障是保证指令不会被重排的（保证phys_page先赋好值），看注释也是保证 phys_pages先写入内存，然后再给pagesize赋值。

有网友曾找到了这个bug曾有被报出来的记录：

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

其中也提供了bug fix的方案。但实际这里面提供的fix方案并没有被合入到主干。尽管它看起来更简单易懂：

-      if (phys_pages == 0)
+      if (phys_pages == 0 || pagesize == 0)