什么是futex？Futex用戶和內(nèi)核空間接口API是什么？

編者按：對于Linux系統(tǒng)編程來說，競爭和同步是繞不開的話題。之前分享過Java的對象鎖，有讀者說自己不做Java不太能理解，這次分享Linux中很基礎(chǔ)的同步機制：futex，內(nèi)容包括基本接口定義和對于優(yōu)先級反轉(zhuǎn)的處理，希望對大家的技術(shù)成長有幫助。

一、什么是futex？

futex是Fast Userspace muTEX的縮寫，該機制是由Rusty Russell、Hubertus Franke和Mathew Kirkwood在2.5.7版本的內(nèi)核中引入，雖然名字中有互斥鎖（mutex）的含義，但實際它是一種用于用戶空間應(yīng)用程序的通用同步工具（基于futex可以在userspace實現(xiàn)互斥鎖、讀寫鎖、condition variable等同步機制）。Futex組成包括：

內(nèi)核空間的等待隊列

用戶空間層的32-bit futex word（所有平臺都是32bit，包括64位平臺）

在沒有競爭的場景下，鎖的獲取和釋放性能都非常高，不需要內(nèi)核的參與，僅僅是通過用戶空間的原子操作來修改futex word的狀態(tài)即可。在有競爭的場景下，如果線程無法獲取futex鎖，那么把自己放入到 wait queue中（陷入內(nèi)核，有系統(tǒng)調(diào)用的開銷），而在owner task釋放鎖的時候，如果檢測到有競爭（等待隊列中有阻塞任務(wù)），就會通過系統(tǒng)調(diào)用來喚醒等待隊列中的任務(wù)，使其恢復(fù)執(zhí)行，繼續(xù)去持鎖。如果沒有競爭，那么也無需陷入內(nèi)核。

二、Futex用戶和內(nèi)核空間接口API是什么？

Futex接口函數(shù)的原型如下：

Futex系統(tǒng)調(diào)用的復(fù)雜性體現(xiàn)在其參數(shù)上，要理解futex需要充分理解其參數(shù)：

futex系統(tǒng)調(diào)用支持各種各樣的操作碼，如下：

1、FUTEX_WAIT：如果futex word中仍然保存著參數(shù)val給定的值，那么當(dāng)前線程則進(jìn)入睡眠，等待FUTEX_WAKE的操作喚醒它。

2、FUTEX_WAKE：最多喚醒val個等待在futex word上的線程。Val或者等于1（喚醒1個等待線程）或者等于INT_MAX（喚醒全部等待線程）

3、FUTEX_WAIT_BITSET：同F(xiàn)UTEX_WAIT，只不過多提供一個mask的參數(shù)

4、FUTEX_WAKE_BITSET：同F(xiàn)UTEX_WAKE，只不過多提供一個mask參數(shù)用來選擇喚醒哪一個waiter。

5、FUTEX_LOCK_PI：PI版本的FUTEX_WAIT

6、FUTEX_UNLOCK_PI：PI版本的FUTEX_WAKE

7、FUTEX_REQUEUE：這個操作包括喚醒和移動隊列兩個動作。喚醒val個等待在uaddr上的waiter，如果還有其他的waiter，那么將這些等待在uaddr的waiter轉(zhuǎn)移到uaddr2的等待隊列上去（最多轉(zhuǎn)移val2個waiter）

8、FUTEX_CMP_REQUEUE：同上，不過需要對比val3這個uaddr的期望值。

除了futex wait和wake這樣的基本操作，futex還有其他應(yīng)用在復(fù)雜場景的操作碼，由于在手機場景沒有使用，本文不再介紹。

我們整理各個操作碼的參數(shù)如下：

三、對于normal futex，內(nèi)核中如何組織等待隊列？

Futex相關(guān)的數(shù)據(jù)結(jié)構(gòu)組織如下圖所示：

從邏輯上看，通過futex實現(xiàn)的互斥鎖和內(nèi)核中的互斥鎖mutex是一樣的（通過futex實現(xiàn)的讀寫鎖的概念和內(nèi)核的rwsem也是一樣，不再贅述），只不過futex互斥鎖是分裂開的：futex word和等待隊列是分別在用戶空間和內(nèi)核空間，內(nèi)核的mutex互斥鎖可以講把待隊列頭放置在mutex對象上，但是對于futex，我們沒有對應(yīng)的內(nèi)核鎖對象，因此我們就需要一個算法將futex word和其等待隊列映射起來。為了管理掛入等待隊列的futex阻塞任務(wù)，內(nèi)核建立了一個hansh table如下：

在初始化的時候，內(nèi)核會構(gòu)建hashsize個futex hash bucket結(jié)構(gòu)，每個bucket用來管理futex鏈表（hash key相同）。futex_hash_bucket數(shù)據(jù)結(jié)構(gòu)定義如下：

每一個等待在futex word的task都有一個futex_q對象（后文稱之futex阻塞任務(wù)對象），根據(jù)其哈希值掛入不同的隊列：

通過上面的數(shù)據(jù)結(jié)構(gòu)，只要有了futex word，那么我們就能根據(jù)hash key定位到其掛入的鏈表。當(dāng)然，為了精準(zhǔn)的匹配，還需要其futex key完全相等，具體請參考match_futex函數(shù)。關(guān)于優(yōu)先級繼承相關(guān)的成員后面會詳細(xì)描述。

四、Futex wait的流程為何？

futex_wait函數(shù)的流程如下：

1、如果參數(shù)中給定了timeout，那么調(diào)用futex_setup_timer來創(chuàng)建一個hrtimer來打斷futex wait阻塞狀態(tài)。

2、通過三元組計算futex hash key，對于process-private類型的futex word，hash key是根據(jù)進(jìn)程地址空間和futex word的虛擬地址來計算，也就是說三元組是( current->mm, address, 0 )。對于share類型的futex word，它會被放置到共享的內(nèi)存中（通過mmap或者shmat）。在這種場景下，futex word在不同進(jìn)程中有不同的虛擬地址，但是物理地址是相同的，通過地址空間中的虛擬地址來計算hash key是行不通的。因此share類型的futex word使用的三元組( inode->i_sequence, page->index, offset_within_page )這樣的組合來計算hash key。具體的細(xì)節(jié)請參考get_futex_key函數(shù)。

3、有了hash key，我們就可以通過這個key找到哈希表中對應(yīng)的表頭（后文稱之hash bucket）。由于后續(xù)會把本次futex阻塞任務(wù)對象（futex_q）掛入hash bucket，因此需要上鎖。

4、在真正插入鏈表之前還需要校驗用戶空間傳遞來的期望值是否發(fā)生了變化（表示用戶空間有其他線程對該futex word進(jìn)行了修改），如果保持不變，那么就可以放心插隊了，否則返回EWOULDBLOCK，當(dāng)然，不要忘記解鎖。

5、插隊動作是在futex_wait_queue_me函數(shù)中完成。插隊是考慮了優(yōu)先級的：對于rt線程，優(yōu)先級高的排在隊首，低的在隊尾。對于cfs任務(wù)，不按照優(yōu)先級排隊，而是采用了FIFO這樣的公平策略。同樣的，完成插隊后不要忘記解鎖。

6、馬上就要阻塞了，如果參數(shù)中給定了timeout，這時候就需要啟動步驟1中設(shè)置的hrtimer了。

7、在真正阻塞之前，還要進(jìn)一步進(jìn)行驗證，畢竟這時候有可能其他的執(zhí)行線索（可能是其他線程的futex wake，也可能是timeout callback）完成出隊操作。這時候就不能阻塞，否者這個線程可能再也無法醒來。

8、在步驟7中阻塞后，可能有多個喚醒場景：如果任務(wù)被正常喚醒（futex wake喚醒），那么其實已經(jīng)完成出隊的動作，這時候直接返回即可，當(dāng)然，如果有啟動hrtimer，我們需要取消它。

9、如果本次futex阻塞任務(wù)對象（futex_q）仍然掛在hash bucket的鏈表上，那表示是有異常發(fā)生，需要進(jìn)行相應(yīng)的處理并在當(dāng)前上下文完成出隊。具體有兩種情況：超時或者被信號打斷。

10、如果設(shè)置了超期時間，那么在當(dāng)前上下文會定義hrtimer_sleeper的對象，如果的確是超期喚醒的話，在timer的上下文中會把hrtimer_sleeper中的task成員清掉（設(shè)置為NULL），通過這個可以判斷是否是超期喚醒。

11、如果當(dāng)前任務(wù)有pending的信號，那說明是被信號打斷。如果沒有pending信號，那說明是spurious wakeup，需要再嘗試一次futex入隊操作。

12、一般而言，如果被信號打斷，直接返回ERESTARTSYS，讓用戶空間程序自己決定怎么后續(xù)處理就OK了。但是有一種情況例外，那就是設(shè)置了timeout（即還沒有超期就被信號打斷），這種場景需要restart syscall。

五、Futex wake的流程為何？

相比futex_wait，futex_wake就比較簡單了，其核心操作就是出隊和喚醒futex wait阻塞的任務(wù)，具體流程如下：

1、首先通過hash key找到對應(yīng)的hash bucket，這個操作和futex_wait中是一樣的。

2、hash bucket中的鏈表上的futex阻塞任務(wù)對象（futex_q）只是由于hash key相同而走到一起的，實際上并非一定是對應(yīng)的futex word，因此我們需要遍歷鏈表進(jìn)行匹配。具體匹配的準(zhǔn)則就是三元組完全相等。

3、三元組相等只能說明futex word是對應(yīng)上了，但是futex機制也提供了用戶可以控制喚醒的方法：比特匹配。在futex wait的時候，上層的應(yīng)用程序可以傳遞bitset參數(shù)來標(biāo)記自己（FUTEX_WAIT_BITSET），在futex wake的時候，應(yīng)用程序會傳遞bitset參數(shù)來通知內(nèi)核自己想要喚醒哪些線程（FUTEX_WAKE_BITSET）。對于FUTEX_WAIT和FUTEX_WAKE，bitset做了特殊處理，設(shè)置為FUTEX_BITSET_MATCH_ANY，即futex wake的時候可以喚醒任何阻塞在該futex word的線程。

4、除了bitset，futex wake還可以控制喚醒線程的個數(shù)。為了完成多個線程的喚醒，這里使用了喚醒隊列（wake queue）。當(dāng)找到匹配的futex_q的時候，將其從hash bucket的隊列中刪除，加入到喚醒隊列上來。需要注意的是：在進(jìn)行這些隊列操作的時候需要持有hash buck的自旋鎖。

5、完成指定數(shù)量的掃描之后會結(jié)束遍歷，調(diào)用wake_up_q將wake queue的任務(wù)逐個喚醒。

六、Futex requeue是什么鬼？

在講requeue流程之前我們需要先明白為何會有requeue這個op code。我們以java中的wait-notify機制來說明這個問題。我們有如下的java代碼：

Java中的Wait和notify的功能是native實現(xiàn)，在虛擬機提供支持。Synchronized是java內(nèi)嵌鎖，在虛擬機對應(yīng)monitor lock（互斥鎖），A臨界區(qū)和B臨界區(qū)都由monitor lock保護，確保了只有一個線程進(jìn)入。為了確保A、B臨界區(qū)的先后關(guān)系（A臨界區(qū)需要等待B臨界區(qū)的事件通知），我們引入了condition varible。在wait-notify場景中有兩個等待隊列：一個是monitor lock的等待隊列，另外一個是condition varible的等待隊列。而對于wait而言，它需要涉及兩個等待隊列的操作：一個是釋放monitor lock（喚醒其等待隊列的任務(wù)），一個是阻塞在條件變量上（把自己掛入其等待隊列）。如果沒有requeue，那么這樣的操作需要兩次futex的系統(tǒng)調(diào)用，有了futex requeue，一次futex就OK了。

了解了requeue的由來，其流程也是非常的簡單，特別是有了上面兩節(jié)futex wait和futex wake基礎(chǔ)。Requeue的流程如下（requeue有normal requeue和pi requeue，這里我們主要描述normal requeue的流程）：

1、Requeue涉及兩個futex，分別用uaddr1和uaddr2表示。這里需要喚醒nr_wake個uaddr1上的線程，同時把其上的nr_requeue個等待任務(wù)對象轉(zhuǎn)移到uaddr2對應(yīng)的等待隊列上。首先調(diào)用get_futex_key獲取兩個futex的hash key，并根據(jù)hash key找到對應(yīng)的hash bucket（hash_futex函數(shù)）

2、如果是FUTEX_CMP_REQUEUE，那么我們還需要校驗uaddr1中的值。需要特別說明的是：這里涉及內(nèi)核空間訪問用戶空間的變量，讀操作是一個非常復(fù)雜的過程，具體參考get_futex_value_locked函數(shù)。這些邏輯和本文的主題關(guān)系不大，就不再贅述了。

3、遍歷uaddr1 等待隊列上的所有等待任務(wù)對象（futex_q），將nr_wake個futex_q通過mark_wake_futex暫存在wake_q喚醒隊列上。通過requeue_futex將uaddr1 等待隊列上nr_requeue個futex_q對象轉(zhuǎn)移到uaddr2的等待隊列上。注意，這些操作需要持有兩個hash bucket的自旋鎖。

4、調(diào)用wake_up_q函數(shù)喚醒之前掛入喚醒隊列的任務(wù)

七、為何futex要支持PI？

Non-PI futex引起的優(yōu)先級翻轉(zhuǎn)（priority inversion）問題如下圖所示：

低優(yōu)先級任務(wù)C首先持鎖，這樣當(dāng)高優(yōu)先級任務(wù)A試圖持鎖失敗進(jìn)入D狀態(tài)。一般而言，C任務(wù)臨界區(qū)比較短，完成之后就釋放鎖，任務(wù)A就可以執(zhí)行了。然而，在C執(zhí)行過程中，中等優(yōu)先級的任務(wù)B被喚醒，搶占了任務(wù)C的執(zhí)行，這時候，所有優(yōu)先級在A和C之間的任務(wù)都可以搶占C的執(zhí)行，從而使得任務(wù)A無法在確定的時間內(nèi)獲取到CPU資源。

PI futex中的PI就是priority inheritance，可以通過優(yōu)先級繼承的方法來解決系統(tǒng)中出現(xiàn)的優(yōu)先級翻轉(zhuǎn)問題。具體的方法就是當(dāng)任務(wù)A持鎖失敗的時候，鎖的owner task（即任務(wù)C）需要臨時性的把優(yōu)先級提升至任務(wù)A的優(yōu)先級。而在釋放鎖的時候，將其優(yōu)先級進(jìn)行恢復(fù)原值。

當(dāng)然，上面只是一個簡單的例子，實際系統(tǒng)會涉及更多的鎖和線程，但原理類似。對于線程，我們需要記錄：

1、該線程持鎖哪些鎖，這些鎖的top waiter是誰，對所有的top waiter按照優(yōu)先級進(jìn)行排序。

2、該線程阻塞在哪一把鎖上

對于鎖，我們需要記錄：

1、該鎖的owner是誰

2、阻塞在該鎖的線程們（按照優(yōu)先級進(jìn)行排序）。

注意，這里我們把優(yōu)先級最高的那個阻塞線程叫做該所的top waiter。

有了這些信息，我們需要維持一個準(zhǔn)則就OK了：一個任務(wù)的臨時優(yōu)先級應(yīng)該提升至其持有鎖的top waiter線程中最高的那個優(yōu)先級。

八、Rt mutex的原理為何？

PI-futex是通過rt mutex來實現(xiàn)的，因此我們這里簡單的聊一聊內(nèi)核的這個PI-aware mutex。

從rt mutex的視角看任務(wù)：

rt_mutex_waiter用來抽象一個阻塞在rt mutex的任務(wù)：task成員指向這個任務(wù)，lock成員指向?qū)?yīng)的rt mutex對象，tree_entry是掛入blocker紅黑樹的節(jié)點，rt mutex對象的waiters成員就是這顆紅黑樹的根節(jié)點（wait_lock成員用來保護紅黑樹的操作）。而owner則指向持鎖的任務(wù)。需要特別說明的是waiters這個紅黑樹是按照任務(wù)優(yōu)先級排序的，left most節(jié)點就是對應(yīng)該鎖的top waiter。

從任務(wù)的視角來看rt mutex：

為了支持rt mutex，task struct也增加了若干的成員，最重要的就是pi_waiters。由于一個任務(wù)可以持有多把鎖，每把鎖都有top waiter，因此和一個任務(wù)關(guān)聯(lián)的top waiter也有非常多，這些top waiter形成了一個紅黑樹（同樣也是按照優(yōu)先級排序），pi_waiters成員就是這顆紅黑樹的根節(jié)點。這顆紅黑樹的left most的任務(wù)優(yōu)先級就是實現(xiàn)優(yōu)先級繼承協(xié)議中規(guī)定要臨時提升的優(yōu)先級。pi_top_task成員指向了left most節(jié)點對應(yīng)的任務(wù)對象，我們稱之top pi waiter。Task struct的pi_blocked_on成員則指向其阻塞的rt_mutex_waiter對象。

有了上面的基本概念之后，我們講一下PI chain的概念。首先看看任務(wù)和鎖的基本關(guān)系，如下圖所示：

在上面的圖片中，task 1持有了Lock A和Lock B，阻塞在Lock C上。一個任務(wù)只能阻塞在一個鎖上，所以紅色箭頭只能是從任務(wù)到鎖，不能分叉。由于一個任務(wù)可以持有多把鎖，所以黑色箭頭會有多個鎖指向一個任務(wù)，即多把鎖匯聚于任務(wù)。有了這個基本的關(guān)系圖之后，我們可以形成更加復(fù)雜的任務(wù)和鎖的邏輯圖，如下：

在上面這張圖中有四條PI chain：

1、Lock D--->task 2

2、task 4--->Lock D--->task 2

3、Lock A--->task 1--->Lock C--->task 2

4、task 3--->Lock B--->task 1--->Lock C--->task 2

為了能夠讓PI正常起作用，PI chain中的任務(wù)必須維持這樣的關(guān)系：處于PI chain中右端的任務(wù)的優(yōu)先級必須大于等于PI chain中左端的任務(wù)們。我們以第四條PI chain為例，任務(wù)2的優(yōu)先級必須大于等于任務(wù)1和任務(wù)3的優(yōu)先級，而任務(wù)1的優(yōu)先級必須要大于等于任務(wù)3的優(yōu)先級。

九、PI futex和rt mutex有什么關(guān)系？

熟悉Linux的工程師都了解內(nèi)核中的mutex互斥鎖以及支持PI的互斥鎖版本rt mutex。如果想讓用戶空間的互斥鎖實現(xiàn)優(yōu)先級繼承的功能，那么其實不需要futex模塊實現(xiàn)復(fù)雜的PI chain，實際上對PI狀態(tài)的跟蹤是通過rt mutex代理來完成的，原理圖如下：

我們先看接口部分，normal futex使用FUTEX_WAIT和FUTEX_WAKE操作碼來完成阻塞和喚醒的動作。對于PI futex而言，F(xiàn)UTEX_LOCK_PI用來執(zhí)行上鎖，而FUTEX_UNLOCK_PI用來完成解鎖。這里的lock和unlock其實是對futex的代理rt mutex而言的。

無論是normal futex還是PI futex，阻塞于futex的任務(wù)都會有一個futex_q對象與之對應(yīng)。對于normal futex，有了futex_q對象，掛入等待隊列和將其喚醒的功能都能輕松實現(xiàn)。對于PI futex，我們不僅僅需要掛入隊列和喚醒任務(wù)，最重要的是我們需要根據(jù)PI chain完成任務(wù)優(yōu)先級的調(diào)整。為了完成這個功能，需要兩個額外的對象，一個是rt_mutex_waiter，表示一個阻塞在rt mutex的任務(wù)，其rt mutex指針指向了其阻塞在哪個rt mutex上。另外一個是futex_pi_state對象，它記錄了優(yōu)先級翻轉(zhuǎn)的信息，包括該用戶空間上層鎖對應(yīng)的內(nèi)核態(tài)的rt mutex，rt mutex的owner任務(wù)的信息等。

十、Pi futex邏輯過程

Pi futex主要有兩個邏輯過程：通過FUTEX_LOCK_PI上鎖，通過FUTEX_UNLOCK_PI完成釋放鎖的邏輯。

這里的“上鎖”有點誤導(dǎo)，不是“試圖持鎖”的意思，而是競爭上層鎖失敗之后，陷入內(nèi)核準(zhǔn)備進(jìn)入阻塞狀態(tài)。這里為了記錄PI state，所以需要對代理rt mutex執(zhí)行上鎖的動作（基本上也是會阻塞在rt mutex上）。對于pi futex的。正常futex的部分，例如get hash key、找futex對應(yīng)的hash bucket、插入hash隊列等操作，這里不再描述，主要看PI futex特有的部分。

第一次futex lock pi稍微復(fù)雜一點，需要完成owner持鎖和current task的阻塞在鎖上這兩個動作。注意：這里的鎖指的是rt mutex。當(dāng)線程持上層鎖成功的時候，我們并不能同時對rt mutex持鎖成功并設(shè)置owner，因此這時候并不會有futex系統(tǒng)調(diào)用進(jìn)入內(nèi)核。當(dāng)?shù)谝淮巫枞臅r候，會通過futex系統(tǒng)調(diào)用把owner id傳遞給內(nèi)核，這時候我們需要分配一個futex pi state對象創(chuàng)建一個rt mutex，同時建立這個rt mutex和owner task的關(guān)系：

1、掛入owner task的futex pi state鏈表。一個任務(wù)可以持有多把上層鎖，所以需要鏈表管理，當(dāng)然不一定每一個任務(wù)持有的上層鎖都有對應(yīng)的futex pi state對象，沒有競爭也就不會陷入內(nèi)核調(diào)用FUTEX_LOCK_PI。

2、futex pi state對象的owner成員指向?qū)?yīng)的owner task

第二個重要的動作就是讓current task去獲取rt mutex，上面剛剛設(shè)定了owner，這里current task持鎖的結(jié)果大概率就是會阻塞，不過我們本來就是通過這個阻塞關(guān)系來完成PI 狀態(tài)的跟蹤的。rt_mutex_waiter對象抽象了一個阻塞在rt mutex的任務(wù)，我們需要建立rt_mutex_waiter對象、阻塞任務(wù)和rt mutex的關(guān)系，具體包括：

1、rt_mutex_waiter對象的lock成員指向?qū)?yīng)于的rt mutex，表示該任務(wù)阻塞在這個鎖上。rt_mutex_waiter對象的task成員指向當(dāng)前要阻塞的任務(wù)對象。

2、將rt_mutex_waiter對象插入rt mutex的waiters紅黑樹。

3、task struct的pi_blocked_on設(shè)置為該rt_mutex_waiter對象。

4、對于rt mutex而言，有了新的阻塞任務(wù)，如果優(yōu)先級比目前該rt mutex的top waiter更高的話，那么需要更新owner task的top waiter，將舊的top waiter節(jié)點從紅黑樹中刪除，將新的top waiter插入owner task的top waiter紅黑樹。

5、根據(jù)新的top waiter更新owner task的動態(tài)優(yōu)先級。一旦修改了owner task的優(yōu)先級，那么其相關(guān)的PI chain都需要進(jìn)行優(yōu)先級調(diào)整。

第二次以及后續(xù)的FUTEX_LOCK_PI會簡單一點，因為不需要新建rt mutex對象了，只需要在bucket找到第一個futex_q對象，通過其pi state指針就可以定位rt mutex了。有了rt mutex，通過上鎖即可讓自己阻塞在這個rt mutex上了。

FUTEX_UNLOCK_PI的流程留給讀者自行分析了。

十一、小結(jié)

本文通過問答的形式簡單的介紹了內(nèi)核futex機制，它是上層同步機制的基石。在PI Futex的介紹中，我們對rt mutex淺嘗輒止，讀者未能領(lǐng)略其全貌。





審核編輯：劉清