Java之指令重排序

背景

問題出現(xiàn)

今天遇到了一個(gè)NullPointerException伞芹，雖然量不大，但是很怪異，大致長(zhǎng)這個(gè)樣子

image.png

這是個(gè)什么空指針？居然說我LinkedList.iterator().hasNext()方法有問題趣避？可是我就是正常的調(diào)用hasNext()啊，怎么就拋出來這種異常了呢新翎？

問題初分析

• 調(diào)用LinkedList.iterator().hasNext()相關(guān)的代碼是出現(xiàn)在預(yù)加載場(chǎng)景里的程帕，而預(yù)加載其實(shí)大多數(shù)是在異步線程里進(jìn)行的住练，出問題的地方恰好是異步線程和UI線程共同訪問LinkedList的地方(UI線程里add，異步線程里poll)骆捧，然后我們就會(huì)很自然的想到是不是因?yàn)樵赼dd和poll的過程中發(fā)生了線程切換導(dǎo)致的呢?

LinkedList實(shí)現(xiàn)(Java8之前)

源碼

• Link

private static final class Link<ET> {
    ET data;

    Link<ET> previous, next;

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}

Link其實(shí)就是我們所說的Node, 從這里可以看出來這是一個(gè)雙向鏈表

• LinkedList()

public LinkedList() {
    voidLink = new Link<E>(null, null, null);
    voidLink.previous = voidLink;
    voidLink.next = voidLink;
}

voidLink也是一個(gè)Link類型澎羞，LinkedList為了方便管理，內(nèi)部實(shí)現(xiàn)其實(shí)是一個(gè)循環(huán)雙向鏈表敛苇，voidLink就是連接首尾的那個(gè)節(jié)點(diǎn)，使用這么一個(gè)voidLink也可以減少大量空指針判斷和保護(hù)顺呕，若鏈表為空枫攀，voidLink的previous和next都指向自己

• LinkedList#poll() -> LinkedList#removeFirst() ->LinkedList#removeFirstImpl()

private E removeFirstImpl() {
    Link<E> first = voidLink.next;
    if (first != voidLink) {
        Link<E> next = first.next;
        voidLink.next = next;
        next.previous = voidLink;
        size--;
        modCount++;
        return first.data;
    }
    throw new NoSuchElementException();
}

這也就是LinkedList的出隊(duì)操作了，驚訝的發(fā)現(xiàn)并沒有任何一個(gè)中間環(huán)節(jié)使鏈表上的某一個(gè)指針指向了null株茶，那再來看一下add方法

• LinkedList#add() -> LinkedList#addLastImpl()

private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

這是對(duì)應(yīng)的入隊(duì)操作来涨，也沒有發(fā)現(xiàn)任何一個(gè)中間步驟讓鏈表上的某個(gè)指針指向null，那再來看下報(bào)錯(cuò)的地方

• LinkedList#itertator() -> LinkedList#listIterator(0) -> new LinkedIterator(LinkedList, int)

LinkIterator(LinkedList<ET> object, int location) {
    list = object;
    expectedModCount = list.modCount;
    if (location >= 0 && location <= list.size) {
        // pos ends up as -1 if list is empty, it ranges from -1 to
        // list.size - 1
        // if link == voidLink then pos must == -1
        link = list.voidLink;
        if (location < list.size / 2) {
            for (pos = -1; pos + 1 < location; pos++) {
                link = link.next;
            }
        } else {
            for (pos = list.size; pos >= location; pos--) {
                link = link.previous;
            }
        }
    } else {
        throw new IndexOutOfBoundsException();
    }
}

最終一系列的調(diào)用启盛，調(diào)用到這個(gè)構(gòu)造方法里蹦掐，location恒等于0，也就是說必然執(zhí)行到

link = link.previous;

• 報(bào)錯(cuò)的地方 LinkedListIterator#hasNext()

public boolean hasNext() {
    return link.previous != list.voidLink;
}

報(bào)錯(cuò)信息顯示這個(gè)link是空僵闯，這個(gè)link是LinkIterator的一個(gè)成員變量

private static final class LinkIterator<ET> implements ListIterator<ET> {
    int pos, expectedModCount;

    final LinkedList<ET> list;

    Link<ET> link, lastLink;
    //...
}

如剛才所分析卧抗，這個(gè)link明明在LinkedListIterator的構(gòu)造方法里賦值成了voidLink.previous,而這個(gè)voidLink.previous在LinkedList構(gòu)造方法里就賦值成了它自己啊，在之后的poll()和add()之后都不會(huì)再有任何一個(gè)中間步驟變成null鳖粟，那問題出在哪里了社裆？

問題可能出在哪里

• 審視整個(gè)流程，只有在LinkedList的構(gòu)造器里面voidLink.previous曾經(jīng)短暫的等于了null向图，但是這個(gè)賦值動(dòng)作是在構(gòu)造器里泳秀，那問題也只能是出在這里了，出問題的原因也只可能是Java虛擬機(jī)把字節(jié)碼指令重排序了榄攀，也就是說把構(gòu)造器里的賦值動(dòng)作放到了ret指令后面嗜傅，導(dǎo)致先返回了對(duì)象地址之后才執(zhí)行賦值操作
• 類似問題：?jiǎn)卫膁ouble check

public class PreloadManager {
    private volatile static PreloadManager sInstance;
    public static PreloadManager getInstance() {
        if (sInstance == null) {
            synchronized(PreloadManager.class) {
                if (sInstance == null) {
                    sInstance = new PreloadManager();
                }
            }
        }
        return sInstance;
    }
    //...
}

sInstance必須要用volatile修飾，有的同學(xué)可能說是為了保證線程可見性檩赢，但是其實(shí)synchronized也可以保證線程可見性(有興趣的同學(xué)可以自己去驗(yàn)證一下)吕嘀，那volatile是為了什么呢？答案是禁止指令重排序(雖然這種說法并不嚴(yán)謹(jǐn))

image.png

因?yàn)間etInstance里面都加上了同步synchronized保護(hù)漠畜，所以假如執(zhí)行構(gòu)造器的時(shí)候進(jìn)行了指令重排序币他，先執(zhí)行了ret指令，把對(duì)象地址賦值給了sInstance變量之后憔狞，才進(jìn)行構(gòu)造器里的賦值蝴悉，這時(shí)候恰好進(jìn)行了線程切換，切換到了線程B瘾敢，這個(gè)時(shí)候如果線程A也恰好進(jìn)行了從工作內(nèi)存寫入到堆內(nèi)存(這是JVM里的概念拍冠，從計(jì)算機(jī)硬件的角度來說就是從高速緩存中寫入到主存中尿这，注：JVM并沒有規(guī)定應(yīng)該何時(shí)進(jìn)行寫入，所以加上了“如果”兩個(gè)字)庆杜，那么就會(huì)檢測(cè)到sInstance不是null射众，然后訪問成員變量，問題就出現(xiàn)了

• 問：synchronized在這里就沒有用了嗎晃财？
• 答：synchronized/鎖在不發(fā)生競(jìng)態(tài)時(shí)確實(shí)沒有互斥叨橱，另外synchronized有線程可見性也表明了synchronized也是有內(nèi)存屏障(稍后會(huì)講到)，看了下面的內(nèi)容再回來仔細(xì)體會(huì)一下断盛，發(fā)現(xiàn)synchronized在這里提供的barrier對(duì)上述這種多線程問題來說----沒卵用

那么問題就確定了罗洗，就是在構(gòu)造器里因?yàn)橹嘏乓鸬膯栴}！再來貼一下這段代碼

public LinkedList() {
    voidLink = new Link<E>(null, null, null);
    voidLink.previous = voidLink;
    voidLink.next = voidLink;
}

也就是說重排序之后钢猛，線程切換恰好發(fā)生在new Link(null, null, null)的時(shí)候伙菜，導(dǎo)致在另外一個(gè)線程調(diào)用iterator()時(shí)，LinkIterator.link被賦值給了voidLink.previous命迈，然后就出現(xiàn)了空指針贩绕，這個(gè)問題可以使用volatile解決，那么這個(gè)volatile為什么會(huì)有作用呢壶愤？

指令重排序/線程可見性

• 有關(guān)指令重排序的講解網(wǎng)上有很多淑倾，我也就不盜圖了，其實(shí)這本來就是很正常的一件事公你，現(xiàn)代處理器都是亂序執(zhí)行的踊淳，這樣可以提高吞吐量(當(dāng)某些指令不在指令緩存中時(shí)，需要從主存中加載指令到高速緩存中陕靠，這個(gè)時(shí)間對(duì)于CPU來說是很長(zhǎng)的迂尝，亂序執(zhí)行允許CPU執(zhí)行后面的指令而不是等待當(dāng)前IO，這種情況主要出現(xiàn)在跳轉(zhuǎn)指令)剪芥，只要保證執(zhí)行結(jié)果和順序執(zhí)行的是一致的就OK垄开。
• 同樣每個(gè)CPU都有自己的高速緩存(L1, L2)，當(dāng)某個(gè)指令執(zhí)行到寫回時(shí)税肪，也許并沒有把緩存中的數(shù)據(jù)寫入到CPU共有的內(nèi)存中去(L3和內(nèi)存)溉躲，這樣也就導(dǎo)致了線程可見性
• 因?yàn)椴灰粯拥奶幚砥鞑捎貌灰粯拥闹噶罴陨鲜鲂袨榭赡苡泻芏喾N益兄，Java內(nèi)存模型的引入其實(shí)也就是提供一種更高的抽象锻梳，把這些處理丟給JVM去適配(比如hotspot分了各個(gè)操作系統(tǒng)的版本)，而Java開發(fā)者只需要寫一樣的代碼就可以有意義的執(zhí)行結(jié)果净捅。

Java內(nèi)存模型的有關(guān)原則

(以下內(nèi)容是抄過來的)

happens-before原則

1. 程序次序規(guī)則：一個(gè)線程內(nèi)疑枯，按照代碼順序，書寫在前面的操作先行發(fā)生于書寫在后面的操作蛔六；
2. 鎖定規(guī)則：一個(gè)unLock操作先行發(fā)生于后面對(duì)同一個(gè)鎖額lock操作荆永；
3. volatile變量規(guī)則：對(duì)一個(gè)變量的寫操作先行發(fā)生于后面對(duì)這個(gè)變量的讀操作废亭；
4. 傳遞規(guī)則：如果操作A先行發(fā)生于操作B，而操作B又先行發(fā)生于操作C具钥，則可以得出操作A先行發(fā)生于操作C豆村；
5. 線程啟動(dòng)規(guī)則：Thread對(duì)象的start()方法先行發(fā)生于此線程的每個(gè)一個(gè)動(dòng)作；
6. 線程中斷規(guī)則：對(duì)線程interrupt()方法的調(diào)用先行發(fā)生于被中斷線程的代碼檢測(cè)到中斷事件的發(fā)生骂删；
7. 線程終結(jié)規(guī)則：線程中所有的操作都先行發(fā)生于線程的終止檢測(cè)掌动，我們可以通過Thread.join()方法結(jié)束、Thread.isAlive()的返回值手段檢測(cè)到線程已經(jīng)終止執(zhí)行桃漾；
8. 對(duì)象終結(jié)規(guī)則：一個(gè)對(duì)象的初始化完成先行發(fā)生于他的finalize()方法的開始坏匪；

as-if-serial

as-if-serial 語義的意思指:不管怎么重排序撬统， 單線程下的執(zhí)行結(jié)果不能被改變(簡(jiǎn)直就是廢話)

數(shù)據(jù)依賴性

如果兩個(gè)操作訪問同一個(gè)變量，其中一個(gè)為寫操作敦迄，此時(shí)這兩個(gè)操作之間存在數(shù)據(jù)依賴性恋追。編譯器和處理器不會(huì)改變存在數(shù)據(jù)依賴性關(guān)系的兩個(gè)操作的執(zhí)行順序，即不會(huì)重排序罚屋。

volatile語義

提醒

Java的規(guī)范要求只需要保證亂序在單線程里看起來和順序執(zhí)行一樣就OK了

內(nèi)存屏障(Memory Barrier)

既然前面講了問題所在苦囱，也說到了volatile能解決這個(gè)問題，那到底為啥能解決呢脾猛？

CPU的角度

其實(shí)這種問題不只是出現(xiàn)在Java上撕彤，畢竟一切的盡頭都是機(jī)器指令，所以只要運(yùn)行在計(jì)算機(jī)上都會(huì)有這種問題猛拴，所以其實(shí)指令集也針對(duì)亂序在多線程時(shí)出現(xiàn)的問題做出了拓展羹铅，這里我們以x86為例

• sfence: 內(nèi)存寫屏障，保證這條指令前的所有的存儲(chǔ)指令必須在這條指令之前執(zhí)行愉昆，并且在執(zhí)行此條指令時(shí)把寫入到CPU的私有緩存的數(shù)據(jù)刷到公有內(nèi)存(以下均簡(jiǎn)稱主存)
• lfence: 內(nèi)存讀屏障职员，保證這條指令后的所有讀取指令在這條指令后執(zhí)行，并且執(zhí)行此條指令時(shí)跛溉，清空CPU的讀取緩存焊切，也就是說強(qiáng)制接下來的load從主存中取數(shù)據(jù)
• mfence: full barrier，代價(jià)最大的barrier芳室，有上述兩種barrier的效果专肪，當(dāng)然也是最穩(wěn)健的的barrier
• lock: 這個(gè)是一種同步指令，也可以禁止lock前的指令和之后的指令重排序(有興趣的同學(xué)可以去看一看這個(gè)指令堪侯，這個(gè)指令稍微復(fù)雜一些嚎尤，可以實(shí)現(xiàn)的功能也很多，我就不貼了)抖格，lock也許是很多JVM底層使用的指令

上述只是x86指令集下的相關(guān)指令诺苹，不同的指令集可能barrier的效果并不一樣咕晋，fence和lock是兩種實(shí)現(xiàn)內(nèi)存屏障的方式(畢竟一個(gè)指令集很龐大)

Java的抽象

Java這個(gè)時(shí)候又來了一波抽象，他把barrier分成了4種

注意兑宇，這是Java內(nèi)存模型里的內(nèi)存屏障，只是Java的規(guī)范粱坤，對(duì)于不同的處理器/指令集隶糕，JVM有不同的實(shí)現(xiàn)方式，比如有可能在x86上一個(gè)StoreLoad會(huì)使用mfence去實(shí)現(xiàn)(當(dāng)然這只是我的意淫)

再次說明一下站玄，這四個(gè)barrier是JVM內(nèi)存模型的規(guī)范枚驻，而不是具體的字節(jié)碼指令，因?yàn)槟憧梢钥吹絭olatile變量在字節(jié)碼中只是一個(gè)標(biāo)志位株旷，javap搞出來的字節(jié)碼中并沒有任何的barriers再登，只是說JVM執(zhí)行引擎會(huì)在執(zhí)行時(shí)會(huì)插一個(gè)對(duì)應(yīng)的屏障，或者說在JIT/AOT生成機(jī)器指令的時(shí)候插一條對(duì)應(yīng)邏輯的barriers晾剖，說句人話锉矢，這個(gè)barrier不是javac插的！所以你通過javap看不到钞瀑，如果想要看到volatile的作用沈撞，可以把字節(jié)碼轉(zhuǎn)成匯編(很多很多)，具體指令如下

java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly [ClassName]

提醒

到這里我們可以看到雕什，其實(shí)不存在任何一種指令能夠禁止亂序執(zhí)行缠俺，我們能做到的只是把這一堆指令根據(jù)"分段"，比如在指令中插入一條full barrier指令贷岸，然后所有指令被分成了兩段壹士，barrier前面的我們稱之為程序段A，后面的稱之為程序段B偿警，通過barrier我們能夠保證A所有指令的執(zhí)行都在B之前躏救，也就是說，程序段A和B分別都是亂序執(zhí)行的。

再舉個(gè)例子盒使，假如我們?cè)谝粋€(gè)變量的賦值前后各加一個(gè)barrier

full barrier;
instance = new Singleton(); //C
full barrier;

那么在外界看起來就好像是禁止了C處指令重排一樣崩掘，其實(shí)C處又可以拆成一堆指令，這一堆指令在兩個(gè)barrier之間其實(shí)又是亂序的

對(duì)于內(nèi)存屏障的使用

volatile

上面我們說了volatile的兩大語義：

• 保證線程可見性
• "禁止"指令重排序(Java5之后引入/修復(fù)的)

現(xiàn)在我們來看看JVM到底會(huì)對(duì)volatile進(jìn)行怎么樣的處理

• 在每個(gè) volatile 寫操作的前面插入一個(gè) StoreStore 屏障
• 在每個(gè) volatile 寫操作的后面插入一個(gè) StoreLoad 屏障
• 在每個(gè) volatile 讀操作的后面插入一個(gè) LoadLoad 屏障
• 在每個(gè) volatile 讀操作的后面插入一個(gè) LoadStore 屏障

此處盜一波圖(來自《深入理解Java內(nèi)存模型》少办，網(wǎng)上可以找到)

image.png

image.png

結(jié)合四種屏障的效果我們來看一下volatile是怎么實(shí)現(xiàn)我們最熟知的可見性和解決重排序問題的(上面說到volatile的具體語義已經(jīng)一目了然了苞慢，但是表中的語義貌似和我們平時(shí)對(duì)volatile的認(rèn)知關(guān)系不大)

(volatile的具體語義是指上述表中普通讀寫和volatile讀寫是否可以重排的關(guān)系)

• 可見性：這個(gè)主要體現(xiàn)在對(duì)volatile的寫上面，當(dāng)volatile寫之后執(zhí)行到了萬能的StoreLoad屏障英妓，然后這個(gè)屏障的語義可以把所有的寫操作刷新到公共內(nèi)存中去挽放，并且使得其他緩存中的這個(gè)變量的緩存失效，所以下次在此讀取時(shí)蔓纠，就會(huì)重新從主存中l(wèi)oad
• "禁止"重排序：這個(gè)之前也已經(jīng)解釋清楚了辑畦，兩個(gè)屏障之間仍是可以亂序的，只是保證了barrier兩側(cè)整體之間時(shí)順序的

synchronized

synchronized我們都知道就是鎖腿倚，但是在java中纯出，synchronized也是可以保證線程可見性的，我們知道信號(hào)量只能實(shí)現(xiàn)鎖的功能敷燎，它是沒有我們之前說過的內(nèi)存屏障的功能的潦刃，那其實(shí)synchronized在代碼塊最后也是會(huì)加入一個(gè)barrier的(應(yīng)該是store barrier)

final

final除了我們平時(shí)所理解的語義之外，其實(shí)還蘊(yùn)含著禁止把構(gòu)造器final變量的賦值重排序到構(gòu)造器外面懈叹，實(shí)現(xiàn)方式就是在final變量的寫之后插入一個(gè)store-store barrier

思考

public class Singleton {
    public volatile static Singleton sInstance = new Singleton();
    public LinkedList<String> mList = new LinkedList<>();
    
    public static void main(String[] args) {
        sInstance.mList.add("A");//A
    }
}

在A處，add函數(shù)內(nèi)部是不是也被"框"在(sIntance的)屏障中間了呢分扎？

我認(rèn)為不會(huì)澄成，因?yàn)閟Instance.mList在是一個(gè)load操作，add()又是另外一個(gè)操作畏吓，所以我覺得add應(yīng)該會(huì)在barrier的外面

我的想法是

//store-store barrier
LinkedList<String> list = sInstance.mList;
//store-load barrier
mList.add("A");

(有可能是我理解錯(cuò)了)

性能

內(nèi)存屏障禁止了CPU恣意妄為的重排序墨状，所以肯定是會(huì)降低一定的效率，不過比synchronized應(yīng)該還是要好一些的

建議

也不要過度使用volatile菲饼，如果是多個(gè)線程共有的變量肾砂，而且不能確保是沒問題的，那么最好加上volatile(這也提醒我們宏悦，盡量減少多線程的公有變量)

一開始的問題

• 我自己也模擬著去復(fù)現(xiàn)這個(gè)bug镐确，最終僥幸碰上了一次，自己模擬最重要的還是要看怎么樣去誘導(dǎo)JVM/CPU去重排構(gòu)造函數(shù)
• 這個(gè)問題或許在現(xiàn)在的項(xiàng)目里存在在各個(gè)地方饼煞，但是因?yàn)檫@個(gè)問題恰好是如果重排了源葫，就會(huì)報(bào)NullPointer，那對(duì)于其他場(chǎng)景砖瞧，也許只是一個(gè)基本變量息堂，所以即使出現(xiàn)了重排導(dǎo)致了問題，可能也只是運(yùn)行出現(xiàn)異常，而不是直接crash了

參考

• Wikipedia(wiki是個(gè)好東西)
• 《深入理解Java內(nèi)存模型》