并發(fā)編程：亂序執(zhí)行的那些事兒
并發(fā)編程：亂序執(zhí)行的那些事兒
FOCUS
什么是亂序執(zhí)行
亂序執(zhí)行，簡單說就是程序里面的代碼的執(zhí)行順序，有可能會被編譯器、CPU 根據(jù)某種策略調(diào)整順序（俗稱，“打亂”）——雖然從單線程的角度看，亂序執(zhí)行不影響執(zhí)行結(jié)果。
為什么需要亂序執(zhí)行
主要原因是 CPU 內(nèi)部采用流水線技術(shù)。抽象且簡化地看，一個 CPU 指令的執(zhí)行過程可以分成 4 個階段：取指、譯碼、執(zhí)行、寫回。
這 4 個階段分別由 4 個獨立物理執(zhí)行單元來完成。這種情況下，如果指令之間沒有依賴關(guān)系，后一條指令并不需要等到前一條指令完全執(zhí)行完成再開始執(zhí)行。而是前一條指令完成取指之后，后一條指令便可以開始執(zhí)行取指操作。
比較理想的情況如下圖所示：指令之間無依賴，可以使流水線的并行度最大化。
在按序執(zhí)行的情況下，一旦遇到指令依賴的情況，流水線就會停滯。比如：
指令 1: Load R3 <- R1(0) ? ?# 從內(nèi)存中加載數(shù)據(jù)到 R3 寄存器
指令 2: Add ?R3 <- R3, R1 ? # 加法，依賴指令 1 的執(zhí)行結(jié)果
指令 3: Sub ?R1 <- R6, R7 ? # 減法
指令 4: Add ?R4 <- R6, R8 ? # 加法
上面的偽代碼中，指令 2 依賴指令 1 的執(zhí)行結(jié)果。在指令 1 執(zhí)行完成之前，指令 2 無法執(zhí)行，這會讓流水線的執(zhí)行效率大大降低。
觀察到，指令 3 和指令 4 對其它指令沒有依賴，可以考慮將這兩條指令”亂序“到指令 2 之前。
這樣，流水線執(zhí)行單元就可以盡可能處于工作狀態(tài)。
總的來說，通過亂序執(zhí)行，合理調(diào)整指令的執(zhí)行順序，可以提高流水線的運行效率，讓指令的執(zhí)行能夠盡可能地并行起來。
Compiler Fence
在多線程的環(huán)境下，亂序執(zhí)行的存在，很容易打破一些預(yù)期，造成一些意想不到的問題。
亂序執(zhí)行有兩種情況：
在編譯期，編譯器進(jìn)行指令重排。
在運行期，CPU 進(jìn)行指令亂序執(zhí)行。
我們先來看一個編譯器指令重排的例子：
#include <atomic>
// 按序遞增發(fā)號器
std::atomic<int> timestamp_oracle{0};
// 當(dāng)前處理的號碼
int now_serving_ts{0};
int shared_value;
int compute();
void memory_reorder() {
? ?// 原子地獲取一個號碼
? ?int ts = timestamp_oracle.fetch_add(1);
? ?// 加鎖：判斷當(dāng)前是否輪到這個號碼，否則就循環(huán)等
? ?while (now_serving_ts != ts);
? ?// 臨界區(qū)：開始處理請求
? ?shared_value = compute();
? ?
? ?// 編譯器 memory barrier
? ?asm volatile("" : : : "memory");
? ?// 解鎖：下一個要處理的號碼
? ?now_serving_ts = ts + 1;
}
簡單解釋一下這段代碼：
這個程序通過維護(hù)一個“發(fā)號器 timestamp_oracle”，來實現(xiàn)按順序處理每個線程的請求。
每個線程先從“發(fā)號器”取一個號，然后不停判斷當(dāng)前是否輪到自己執(zhí)行，類似自旋鎖的邏輯。
每個線程執(zhí)行完，將“號碼”切換到下一個。
在 O1 的編譯優(yōu)化選項下，編譯出來的匯編指令沒有被重排（通過左右兩邊的代碼行背景色就可以看出來）。
在 O2 的編譯優(yōu)化選項下，出現(xiàn)了指令被重排了，并且這里的指令重排打破了程序的預(yù)期，先切換了 now_serving_ts，再更新 shared_value，導(dǎo)致 shared_value 可能被并發(fā)修改。
為了阻止編譯器重排這兩句代碼的指令，需要在它們之間插入一個 compiler fence。
asm volatile("": : :"memory");
這個是 GCC 擴(kuò)展的 compiler fence 的寫法。這條指令告訴編譯器（GCC 官方文檔）：
防止這條 fence 指令上方的內(nèi)存訪問操作被移到下方，同時防止下方的內(nèi)存訪問操作移到上面，也就是防止了亂序。
讓編譯器把所有緩存在寄存器中的內(nèi)存變量 flush 到內(nèi)存中，然后重新從內(nèi)存中讀取這些值。
對于第 2 點，有時候我們只需要刷新部分變量。刷新所有寄存器并不一定完全符合我們的預(yù)期，并且會引入不必要的開銷。GCC 支持指定變量的 compiler fence。
write(x)
asm volatile("": "=m"(y) : "m"(x):)
read(y)
中間的內(nèi)聯(lián)匯編指令告訴編譯器不要把 write(x) 和 read(y) 這兩個操作亂序。
CPU Fence
先來看一個例子：
int x = 0;
int y = 0;
int r0, r1;
// CPU1
void f1()
{
? ?x = 1;
? ?asm volatile("": : :"memory");
? ?r0 = y;
}
// CPU2
void f2()
{
? ?y = 1;
? ?asm volatile("": : :"memory");
? ?r1 = x;
}
上面的例子中，由于 compiler fence 的存在，編譯器不會對函數(shù) f1 和函數(shù) f2 內(nèi)部的指令進(jìn)行重排。
此時，如果 CPU 執(zhí)行時也沒有亂序，是不可能出現(xiàn) r0 == 0 && r1 == 0 的情況的。不幸的是，由于 CPU 亂序執(zhí)行的存在，這種情況是可能發(fā)生的?？聪旅孢@個例子：
#include <iostream>
#include <thread>
int x = 0;
int y = 0;
int r0 = 100;
int r1 = 100;
void f1() {
? ?x = 1;
? ?asm volatile("": : :"memory");
? ?r0 = y;
}
void f2() {
? ?y = 1;
? ?asm volatile("": : :"memory");
? ?r1 = x;
}
void init() {
? ?x = 0;
? ?y = 0;
? ?r0 = 100;
? ?r1 = 100;
}
bool check() {
? ?return r0 == 0 && r1 == 0;
}
std::atomic<bool> wait1{true};
std::atomic<bool> wait2{true};
std::atomic<bool> stop{false};
void loop1() {
? ?while(!stop.load(std::memory_order_relaxed)) {
? ? ? ?while (wait1.load(std::memory_order_relaxed));
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?f1();
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?wait1.store(true, std::memory_order_relaxed);
? ?}
}
void loop2() {
? ?while (!stop.load(std::memory_order_relaxed)) {
? ? ? ?while (wait2.load(std::memory_order_relaxed));
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?f2();
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?wait2.store(true, std::memory_order_relaxed);
? ?}
}
int main() {
? ?std::thread thread1(loop1);
? ?std::thread thread2(loop2);
? ?long count = 0;
? ?while(true) {
? ? ? ?count++;
? ? ? ?init();
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?wait1.store(false, std::memory_order_relaxed);
? ? ? ?wait2.store(false, std::memory_order_relaxed);
? ? ? ?while (!wait1.load(std::memory_order_relaxed));
? ? ? ?while (!wait2.load(std::memory_order_relaxed));
? ? ? ?asm volatile("" ::: "memory");
? ? ? ?if (check()) {
? ? ? ? ? ?std::cout << "test count " << count << ": r0 == " << r0 << " && r1 == " << r1 << std::endl;
? ? ? ? ? ?break;
? ? ? ?} else {
? ? ? ? ? ?if (count % 10000 == 0) {
? ? ? ? ? ? ? ?std::cout << "test count " << count << ": OK" << std::endl;
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?stop.store(true);
? ?wait1.store(false);
? ?wait2.store(false);
? ?thread1.join();
? ?thread2.join();
? ?return 0;
}
上面的程序可以很輕易就運行出 r0 == 0 && r1 == 0 的結(jié)果，比如：
test count 56: r0 == 0 && r1 == 0
為了防止 CPU 亂序執(zhí)行，需要使用 CPU fence。我們可以將函數(shù) f1 和 f2 中的 compiler fence 修改為 CPU fence：
void f1() {
? ?x = 1;
? ?asm volatile("mfence": : :"memory");
? ?r0 = y;
}
void f2() {
? ?y = 1;
? ?asm volatile("mfence": : :"memory");
? ?r1 = x;
}
如此，便不會出現(xiàn) r0 == 0 && r1 == 0 的情況了。
總結(jié)
指令亂序執(zhí)行主要由兩種因素導(dǎo)致：
編譯期指令重排。
運行期 CPU 亂序執(zhí)行。
無論是編譯期的指令重排還是 CPU 的亂序執(zhí)行，主要都是為了讓 CPU 內(nèi)部的指令流水線可以“充滿”，提高指令執(zhí)行的并行度。
上面舉的插入 fence 的例子都是使用了 GCC 的擴(kuò)展語法，實際上 C++ 標(biāo)準(zhǔn)庫已經(jīng)提供了類似的封裝：std::atomic_thread_fence，跨平臺且可讀性更好。
一些無鎖編程、追求極致性能的場景可能會需要手動在合適的地方插入合適 fence，這里涉及的細(xì)節(jié)太多，非常容易出錯。原子變量操作根據(jù)不同的 memory order 會自動插入合適的 fence，建議優(yōu)先考慮使用原子變量。
發(fā)布于 2021-09-25 16:59
并發(fā)
評論千萬條，友善第一條
6 條評論
默認(rèn)
最新
不吃香菜的大頭怪
x86會亂序執(zhí)行但是結(jié)果會順序提交 造成x86 TSO的原因是store buffer
2021-12-15
追萊恩
是的，x86只有示例這種StoreLoad亂序
05-06
CopyCoder
越學(xué)越不會了。
2022-07-19
天高地遠(yuǎn)
老哥，這個左邊c++右邊匯編的軟件或者網(wǎng)站是什么呀，感覺好方便
05-31
天高地遠(yuǎn)
FOCUS
非常感謝
05-31
FOCUS
作者
godbolt.org/
05-31
Intel CPU漏洞技術(shù)解讀：都是緩存惹的禍！
云杉網(wǎng)絡(luò)
技術(shù)創(chuàng)造價值
背景
2017年6月1日，Google的安全團(tuán)隊向Intel、AMD、ARM報了一個硬件級的漏洞，造成的危害是內(nèi)核數(shù)據(jù)泄露，修復(fù)該漏洞的代價是至少30%的性能損失。2017年末Linux內(nèi)核社區(qū)推出了KPTI「Kernel Page Table Isolation」補丁，Linus Torvalds在內(nèi)核郵件列表上毫不留情地抨擊了Intel。
安全人員將這兩個漏洞命名為Meltdown和Spectre；Meltdown目前只存在于Intel的處理器和部分ARM處理器，Spectre存在于一切有亂序執(zhí)行的現(xiàn)代處理器架構(gòu)里面，包括AMD。從原理上來說漏洞無法徹底修復(fù)。
本次的漏洞會對所有云廠商造成較大影響，已經(jīng)有跡象表明有黑客在利用漏洞攻擊云系統(tǒng)。Microsoft Azure中國區(qū)已發(fā)布公告稱，將于北京時間2018 年 1 月 4 日上午 11:30 開始自動重啟受影響的虛擬機(jī)，并全部關(guān)閉向部分客戶開放的自助維護(hù)窗口；AWS也發(fā)送了通知郵件聲稱本周五將進(jìn)行重大安全更新。
原因
一切還是要從CPU指令執(zhí)行的框架——流水線說起。Intel當(dāng)然不至于明知你要用一個用戶態(tài)的進(jìn)程讀取Kernel內(nèi)存還會給你許可。但現(xiàn)代CPU流水線的設(shè)計，尤其是和性能優(yōu)化相關(guān)的流水線的特性，讓這一切充滿了變數(shù)。
給所有還沒有看過云杉網(wǎng)絡(luò)連載的系列文章《x86高性能編程箋注系列》的讀者一點背景知識的介紹：
x86 CPU為了優(yōu)化性能，在處理器架構(gòu)方面做了很多努力。諸如“多級緩存”這一類的特性，是大家都比較熟悉的概念。還有一些特性，比如分支預(yù)測和亂序執(zhí)行，也都是一些可以從并行性等方面有效提升程序性能的特性，并且它們也都是組成流水線的幾個關(guān)鍵環(huán)節(jié)。即便你暫時還不能準(zhǔn)確理解其含義，但望文生義，也能看出來這肯定是兩個熵增的過程。熵增帶來無序，無序就會帶來更多漏洞。
緩存的困境
講緩存，必然先掛一張memory hierarchy鎮(zhèn)樓：
不過我要說的和這個沒太大關(guān)系?，F(xiàn)在需要考慮的是，如果能讀取到內(nèi)核地址的內(nèi)容，那這部分內(nèi)容最終肯定是跑到緩存中去了，因為真正直接和CPU核心交互的存儲器，就是緩存。這對一級緩存（L1 Cache，業(yè)內(nèi)也常用縮寫L1$，取cash之音）提出的要求就是，必須要非常快，唯有如此才能跟上CPU處理核心的速度。
Side Notes: 為什么在不考慮成本的情況下緩存不是越大越好，也是因為當(dāng)緩存規(guī)模越大，查找某一特定數(shù)據(jù)就會越慢。而緩存首先要滿足的要求就是快，其他的都是次要的。
根據(jù)內(nèi)核的基本知識我們知道，進(jìn)程運行時都有一個虛擬地址「Virtual address」和其所對應(yīng)的物理地址「physical address」。
從虛擬地址到物理地址的翻譯轉(zhuǎn)換也由CPU通過page table完成。Page table并不儲存在CPU里，但近期查找到的Page table entry「PTE」都像數(shù)據(jù)一樣，緩存在了CPU中的translation lookaside buffer「TLB」里。為了不再過多堆砌術(shù)語和名詞，畫張圖說明一下：
當(dāng)CPU根據(jù)程序要求需要讀取某個地址上的數(shù)據(jù)時，首先會在L1 Cache中查找。為了適應(yīng)CPU的速度，L1緩存實現(xiàn)為Virtually indexed physically tagged「VIPT」的形式，即用虛擬地址即可直接讀取該虛擬地址對應(yīng)的物理地址的內(nèi)容，而不再需要多加一道轉(zhuǎn)換的工序。
如果L1 Cache miss，則會在下級緩存中查找。但越過L1 Cache之后，對L2$和L3$的速度要求就不再這么嚴(yán)苛。此時CPU core給出的虛擬地址請求會先通過TLB轉(zhuǎn)換為物理地址，再送入下級緩存中查找。而檢查進(jìn)程有沒有權(quán)限讀取某一地址這一過程，僅在地址轉(zhuǎn)換的時候發(fā)生，而這種轉(zhuǎn)換和檢查是需要時間的，所以有意地安排在了L1 Cache之后。
L1緩存這種必須求“快”的特性，成了整個事件的楔子。
分支預(yù)測
分支預(yù)測是一種提高流水線執(zhí)行效率的手段。在遇到if..else..這種程序執(zhí)行的分支時，可以通過以往的歷史記錄判斷哪一分支是最可能被執(zhí)行的分支，并在分支判斷條件真正返回判斷結(jié)果之前提前執(zhí)行分支的代碼。詳情可以在上面提到的連載文章中閱讀。
需要強調(diào)的是，提前執(zhí)行的分支代碼，即便事后證明不是正確的分支，其執(zhí)行過程中所讀取的數(shù)據(jù)也可以進(jìn)入L1緩存。在Intel的官網(wǎng)文檔《Intel? 64 and IA-32 Architectures Optimization Reference Manual》第2.3.5.2節(jié)中指：
L1 DCache Loads:
- Be carried out speculatively, before preceding branches are resolved.
- Take cache misses out of order and in an overlapped manner.
Show you the [偽] code:
if (likely(A < B)) { ? ?value = *(kernel_address_pointer);}
當(dāng)分支判斷條件A < B被預(yù)測為真時，CPU會去提前執(zhí)行對內(nèi)核地址的讀取。當(dāng)實際條件為A > B時，雖然內(nèi)核的值不會真正寫入寄存器（沒有retire），但會存入L1 Cache，再加之上一節(jié)介紹的，獲取L1 Cache的值毋須地址轉(zhuǎn)換，毋須權(quán)限檢查，這就為內(nèi)核信息的泄漏創(chuàng)造了可能。
從理論上來講，如果可以控制程序的分支判斷，并且可以獲取L1緩存中的數(shù)據(jù)（這個沒有直接方法，但可以通過其他間接手法）的話，就完全可以獲取內(nèi)核信息。而分支預(yù)測這種特性是不能隨隨便便就關(guān)閉的，這也就是這次問題會如此棘手的原因。
亂序執(zhí)行
還有一個原因是亂序執(zhí)行，但原理大致類似。亂序執(zhí)行是Intel在1995年首次引入Pentium Pro處理器的機(jī)制。其過程首先是將我們在匯編代碼中看到的指令“打散”，成為更細(xì)粒度的微指令「micro-operations」，更小的指令粒度將會帶來更多的亂序排列的組合，CPU真正執(zhí)行的是這些微指令。
沒有數(shù)據(jù)依賴的微指令在有相應(yīng)執(zhí)行資源的情況下亂序并行執(zhí)行，進(jìn)而提升程序的并行程度，提高程序性能。但引入的問題是，讀取內(nèi)核數(shù)據(jù)的微指令可能會在流水線發(fā)出exception之前將內(nèi)核數(shù)據(jù)寫入L1 Cache。與分支選擇一樣，為通過用戶態(tài)進(jìn)程獲取內(nèi)核代碼提供了可能。
限于篇幅，更詳細(xì)的內(nèi)容讀者可以在國外安全團(tuán)隊發(fā)布的消息中獲取。
后續(xù)
剛剛查閱之前連載中的一些細(xì)節(jié)的時候，看到在“流水線”那一章里寫過這樣一段話：
在面對問題的時候，人總是會傾向于引入一個更復(fù)雜的機(jī)制來解決問題，多級流水線就是一個例子。復(fù)雜可以反映出技術(shù)的改良，但“復(fù)雜”本身就是一個新的問題。這也許就是矛盾永遠(yuǎn)不會消失，技術(shù)也不會停止進(jìn)步的原因。但“為學(xué)日益，為道日損”，愈發(fā)復(fù)雜的機(jī)制總會在某個時機(jī)之下發(fā)生大破大立，但可能現(xiàn)在時機(jī)還沒有到來:D
很難講現(xiàn)在是不是就是所謂的那個“時機(jī)”。雖然對整個行業(yè)都產(chǎn)生了負(fù)面影響，但我對此仍保持樂觀。因為這就是事物自然發(fā)展的一個正常過程。性能損失并不是一件壞事，尤其是對牙膏廠的用戶來說。
◆◆◆
作者簡介
張攀
一個不耽誤碼字的網(wǎng)工
張攀，云杉網(wǎng)絡(luò)工程師，專注于x86網(wǎng)絡(luò)軟件的開發(fā)與性能優(yōu)化，深度參與ONF/OPNFV/ONOS等組織及社區(qū)，曾任ONF測試工作組副主席。
編輯于 2018-01-05 14:12
漏洞
安全漏洞
評論千萬條，友善第一條
6 條評論
默認(rèn)
最新
驍龍800
講了一大堆教科書上的東西，就是沒講漏洞本身
2018-01-08
呵呵忙
這個回答看著好像是要解釋漏洞，結(jié)果只是裝模作樣地科普了一番
2018-01-09
知乎用戶0nC45a
性能損失怎么就不是壞事了？
2018-01-12
打王者被ELO制裁
Spectre存在于一切有亂序執(zhí)行的現(xiàn)代處理器架構(gòu)里面，包括AMD
還有mips芯片龍芯呢，難道不是亂序執(zhí)行的架構(gòu)么
2018-01-08
xingshi he
坐等更新
2018-01-08
Sartner
下次擠牙膏恐怕要擠一大坨
2018-01-07
