一、什么是futex？

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

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

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

在沒有競(jìng)爭(zhēng)的場(chǎng)景下，鎖的獲取和釋放性能都非常高，不需要內(nèi)核的參與，僅僅是通過(guò)用戶空間的原子操作來(lái)修改futex word的狀態(tài)即可。在有競(jìng)爭(zhēng)的場(chǎng)景下，如果線程無(wú)法獲取futex鎖，那么把自己放入到 wait queue中（陷入內(nèi)核，有系統(tǒng)調(diào)用的開銷），而在owner task釋放鎖的時(shí)候，如果檢測(cè)到有競(jìng)爭(zhēng)（等待隊(duì)列中有阻塞任務(wù)），就會(huì)通過(guò)系統(tǒng)調(diào)用來(lái)喚醒等待隊(duì)列中的任務(wù)，使其恢復(fù)執(zhí)行，繼續(xù)去持鎖。如果沒有競(jìng)爭(zhēng)，那么也無(wú)需陷入內(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個(gè)等待在futex word上的線程。Val或者等于1（喚醒1個(gè)等待線程）或者等于INT_MAX（喚醒全部等待線程）

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

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

5、FUTEX_LOCK_PI：PI版本的FUTEX_WAIT

6、FUTEX_UNLOCK_PI：PI版本的FUTEX_WAKE

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

8、FUTEX_CMP_REQUEUE：同上，不過(guò)需要對(duì)比val3這個(gè)uaddr的期望值。

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

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

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ? ?

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

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

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

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

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

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

四、Futex wait的流程為何？

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

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

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

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

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

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

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

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

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

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

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

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

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

五、Futex wake的流程為何？

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

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

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

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

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

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

六、Futex requeue是什么鬼？

在講requeue流程之前我們需要先明白為何會(huì)有requeue這個(gè)op code。我們以java中的wait-notify機(jī)制來(lái)說(shuō)明這個(gè)問(wèn)題。我們有如下的java代碼：

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

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

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

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

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

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

文章篇幅過(guò)長(zhǎng) 下文繼續(xù)講解?

原文作者：內(nèi)核工匠