小议C语言标准库排序函数qsort曾经的bug
小议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)
腾讯云开发者
