指令重排序與內(nèi)存屏障

一本正經(jīng)地胡鬧 2021-03-31

展開全文

從老版glibc的一個bug說開來

之前我在公眾號中,，發(fā)表過這么一篇文章：

這篇文章里面提到了老版本的glibc（2.13以前）中的排序函數(shù)qsort()有一個在并發(fā)時會出現(xiàn)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) {

這種除法操作并發(fā)的時候會出現(xiàn)除0,，導(dǎo)致coredump。也就是pagesize = 0,，而單看串行邏輯,，上述代碼沒有問題。因為前面pagesize已經(jīng)被賦值了：

            pagesize = __sysconf(_SC_PAGESIZE);

這個就是讀取系統(tǒng)配置,，獲取頁的大小賦值給pagesize,。

那么為什么會core呢？首要原因當(dāng)然是pagesize的賦值的if其判斷條件不是pagesize為0，而是phys_pages 是否為0,。因此存在race condition,，phys_pages被賦值，但是pagesize還沒走到賦值的位置的時候,，其他線程開始做qsort排序,，導(dǎo)致跳過了這個if，直接去做了那個除法操作,。

所以見過一些老代碼在服務(wù)初始化的時候,，先用qsort()給隨機數(shù)做一下排序，目的就是給這兩個static變量初始化,。

為此,，有人給老版的glibc提過修復(fù)的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);

修改判斷條件，將兩個靜態(tài)變量是否為0都判斷了一遍,。很簡單易懂是吧,，看著也能解決這個并發(fā)的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() 后面會講到,。

劇透一下,，這段代碼的含義就是用匯編語言，在這里加入了一個內(nèi)存屏障,。好了,，開始講講什么是指令重排序，什么是內(nèi)存屏障吧,！

指令重排序

編譯器為了提高程序的性能,，有時不會按照程序代碼對應(yīng)的指令順序來執(zhí)行，而是亂序執(zhí)行（Out-of-order execution）,。比如我們用gcc編譯器都用過O2參數(shù),。當(dāng)然了說亂序有點夸張，它是在保證程序結(jié)果不變的情況下,，對看似沒有關(guān)聯(lián)的語句進行重排序,。然而它的重排序有個弊病，就是它僅能從單線程的串行邏輯角度去判斷兩個語句有沒有依賴關(guān)系,。不能判斷多線程環(huán)境下的依賴關(guān)系,。因而會導(dǎo)致問題。

當(dāng)然不僅編譯器,，CPU也會對程序進行優(yōu)化,，從而導(dǎo)致指令的重排。

前文所述的那個沒被合入的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是沒有依賴關(guān)系的，所以直接可能被優(yōu)化成這樣執(zhí)行：

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

這樣又會產(chǎn)生一種新的race condition,，那就是某個線程中的qsort其pagesize和phys_pages都通過__sysconf()賦值完成了,，但是phys_pages /=4;還沒有被執(zhí)行，彼時另外一個線程又在執(zhí)行qsort,，導(dǎo)致它判斷pagesize和phys_pages都不等于0了,，就跳過了if直接執(zhí)行：

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

這個時候的phys_pages是還沒有除以4的，所以這個除法雖然不core了,，但整個表達式的邏輯也不正確,！

內(nèi)存屏障

內(nèi)存屏障（memory barrier）又叫內(nèi)存柵欄（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()，顧名思義就是加一個”寫類型“的內(nèi)存屏障,，其實它是一個宏,，展開為：

__asm('':::'memory')

這個就是通過嵌入?yún)R編代碼的方式加了一個內(nèi)存屏障。讓phys_pages成功寫入之后再去給pagesize賦值（根據(jù)注釋也可見一斑）,。

此外前面我有提到,，編譯器和CPU都會導(dǎo)致指令的重排序。這里的 __asm('':::'memory') 其實加的是編譯器的內(nèi)存屏障（也叫優(yōu)化屏障）,，也就是說它能阻止編譯器不會對這段代碼重排序,，并不會阻止CPU的重排序。那么CPU不需要管嗎,？

X86的內(nèi)存模型

在談及CPU時,，通常會把變量的讀操作稱為load，變量的寫操作稱為store,。兩兩組合因而會出現(xiàn)4類讀寫操作：

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

對于我們常見的x86 架構(gòu)的CPU來說，它有一個相對強大的內(nèi)存模型,。它能直接保證前面三種屏障,，也就是說不需要去寫匯編指令去阻止CPU對前面三種類型讀寫操作的重排。但x86 CPU無法保證StoreLoad類型的屏障,。對于我前面所講的qsort的例子,，這個場景并不屬于StoreLoad,。貌似是StoreStore，先后對兩個變量進行寫入,。所以不需要給CPU加內(nèi)存屏障,。

當(dāng)然如果要加的話，也有辦法是這樣寫：

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

mfence是針對CPU的內(nèi)存屏障,。

內(nèi)存屏障與MESI

看完前面的內(nèi)容,，相信你已經(jīng)認識到內(nèi)存屏障對于阻止編譯器和CPU指令重排序的作用，但其實CPU的內(nèi)存屏障卻不止如此,，還記得本系列的上一篇文章介紹了CPU的緩存一致性協(xié)議MESI嗎,？

其實內(nèi)存屏障與MESI也有關(guān)系。

CPU的內(nèi)存屏障如果只是保證指令順序不會亂,，也未必會讓程序執(zhí)行符合預(yù)期,。因為MESI為了提升性能，引入了Store Buffer和Invalidate Queue,。所以內(nèi)存屏障還有其他功能：

寫類型的內(nèi)存屏障還能觸發(fā)內(nèi)存的強制更新,，讓Store Buffer中的數(shù)據(jù)立刻回寫到內(nèi)存中。讀類型的內(nèi)存屏障會讓Invalidate Queue中的緩存行在后面的load之前全部標(biāo)記為失效,。

順帶一提,，X86 CPU是沒有實現(xiàn)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

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息,，謹防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點擊一鍵舉報,。