Linux Mutex機制分析ifdef CONFIG_MUTEX_SPIN_ON_OWNERendififdef CONFIG_DEBUG_MUTEXESendififdef CONFIG_DEBUG_LOCK_ALLOC

Linux Mutex機制分析

背景

Read the fucking source code! --By 魯迅

A picture is worth a thousand words. --By 高爾基

說明：

Kernel版本：4.14

ARM64處理器，Contex-A53，雙核

使用工具：Source Insight 3.5， Visio

1. 概述

   Mutex互斥鎖是Linux核心中用于互斥操作的一種同步原語；

互斥鎖是一種休眠鎖，鎖争用時可能存在程序的睡眠與喚醒，context的切換帶來的代價較高，适用于加鎖時間較長的場景；

互斥鎖每次隻允許一個程序進入臨界區，有點類似于二值信号量；

互斥鎖在鎖争用時，在鎖被持有時，選擇自選等待，而不立即進行休眠，可以極大的提高性能，這種機制（optimistic spinning）也應用到了讀寫信号量上；

互斥鎖的缺點是互斥鎖對象的結構較大，會占用更多的CPU緩存和記憶體空間；

與信号量相比，互斥鎖的性能與擴充性都更好，是以，在核心中總是會優先考慮互斥鎖；

互斥鎖按為了提高性能，提供了三條路徑處理：快速路徑，中速路徑，慢速路徑；

前戲都已經講完了，來看看實際的實作過程吧。

1. optimistic spinning

   2.1 MCS鎖

上文中提到過Mutex在實作過程中，采用了optimistic spinning自旋等待機制，這個機制的核心就是基于MCS鎖機制來實作的；

MCS鎖機制是由John Mellor Crummey和Michael Scott在論文中《algorithms for scalable synchronization on shared-memory multiprocessors》提出的，并以他倆的名字來命名；

MCS鎖機制要解決的問題是：在多CPU系統中，自旋鎖都在同一個變量上進行自旋，在擷取鎖時會将包含鎖的cache line移動到本地CPU，這種cache-line bouncing會很大程度影響性能；

MCS鎖機制的核心思想：每個CPU都配置設定一個自旋鎖結構體，自旋鎖的申請者（per-CPU）在local-CPU變量上自旋，這些結構體組建成一個連結清單，申請者自旋等待前驅節點釋放該鎖；

osq(optimistci spinning queue)是基于MCS算法的一個具體實作，并經過了疊代優化；

2.2 osq流程分析

optimistic spinning，樂觀自旋，到底有多樂觀呢？當發現鎖被持有時，optimistic spinning相信持有者很快就能把鎖釋放，是以它選擇自旋等待，而不是睡眠等待，這樣也就能減少程序切換帶來的開銷了。

看一下資料結構吧：

osq_lock如下：

osq加鎖有幾種情況：

無人持有鎖，那是最理想的狀态，直接傳回；

有人持有鎖，将目前的Node加入到OSQ隊列中，在沒有高優先級任務搶占時，自旋等待前驅節點釋放鎖；

自旋等待過程中，如果遇到高優先級任務搶占，那麼需要做的事情就是将之前加入到OSQ隊列中的目前節點，從OSQ隊列中移除，移除的過程又分為三個步驟，分别是處理prev前驅節點的next指針指向、目前節點Node的next指針指向、以及将prev節點與next後繼節點連接配接；

加鎖過程中使用了原子操作，來確定正确性；

osq_unlock如下：

解鎖時也分為幾種情況：

無人争用該鎖，那直接可以釋放鎖；

擷取目前節點指向的下一個節點，如果下一個節點不為NULL，則将下一個節點解鎖；

目前節點的下一個節點為NULL，則調用osq_wait_next，來等待擷取下一個節點，并在擷取成功後對下一個節點進行解鎖；

從解鎖的情況可以看出，這個過程相當于鎖的傳遞，從上一個節點傳遞給下一個節點；

在加鎖和解鎖的過程中，由于可能存在操作來更改osq隊列，是以都調用了osq_wait_next來擷取下一個确定的節點：

1. mutex

   3.1 資料結構

終于來到了主題了，先看一下資料結構：

struct mutex {

atomic_long_t        owner;           //原子計數，用于指向鎖持有者的task struct結構
spinlock_t        wait_lock;              //自旋鎖，用于wait_list連結清單的保護操作           

ifdef CONFIG_MUTEX_SPIN_ON_OWNER

struct optimistic_spin_queue osq; /* Spinner MCS lock */        //osq鎖           

endif

struct list_head    wait_list;          //連結清單，用于管理所有在該互斥鎖上睡眠的程序           

ifdef CONFIG_DEBUG_MUTEXES

void            *magic;           

ifdef CONFIG_DEBUG_LOCK_ALLOC

struct lockdep_map    dep_map;           

};

在使用mutex時，有以下幾點需要注意的：

一次隻能有一個程序能持有互斥鎖；

隻有鎖的持有者能進行解鎖操作；

禁止多次解鎖操作；

禁止遞歸加鎖操作；

mutex結構隻能通過API進行初始化；

mutex結構禁止通過memset或者拷貝來進行初始化；

已經被持有的mutex鎖禁止被再次初始化；

mutex不允許在硬體或軟體上下文（tasklets, timer）中使用；

3.2 加鎖流程分析

從mutex_lock加鎖來看一下大概的流程：

mutex_lock為了提高性能，分為三種路徑處理，優先使用快速和中速路徑來處理，如果條件不滿足則會跳轉到慢速路徑來處理，慢速路徑中會進行睡眠和排程，是以開銷也是最大的。

3.2.1 fast-path

快速路徑是在__mutex_trylock_fast中實作的，該函數的實作也很簡單，直接調用atomic_long_cmpxchg_release(&lock->owner, 0UL, curr)函數來進行判斷，如果lock->owner == 0表明鎖未被持有，将curr指派給lock->owner辨別curr程序持有該鎖，并直接傳回；

lock->owner不等于0，表明鎖被持有，需要進入下一個路徑來處理了；

3.2.2 mid-path

中速路徑和慢速路徑的處理都是在__mutex_lock_common中實作的；

__mutex_lock_common的傳入參數為(lock, TASK_INTERRUPTIBLE, 0, NULL, _RET_IP_, false)，該函數中很多路徑覆寫不到，接下來的分析也會剔除掉無效代碼；

中速路徑的核心代碼如下：

當發現mutex鎖的持有者正在運作（另一個CPU）時，可以不進行睡眠排程，而可以選擇自選等待，當鎖持有者正在運作時，它很有可能很快會釋放鎖，這個就是樂觀自旋的原因；

自旋等待的條件是持有鎖者正在臨界區運作，自旋等待才有價值；

__mutex_trylock_or_owner函數用于嘗試擷取鎖，如果擷取失敗則傳回鎖的持有者。互斥鎖的結構體中owner字段，分為兩個部分：1）鎖持有者程序的task_struct（由于L1_CACHE_BYTES對齊，低位比特沒有使用）；2）MUTEX_FLAGS部分，也就是對應低三位，如下：

MUTEX_FLAG_WAITERS：比特0，辨別存在非空等待者連結清單，在解鎖的時候需要執行喚醒操作；

MUTEX_FLAG_HANDOFF：比特1，表明解鎖的時候需要将鎖傳遞給頂部的等待者；

MUTEX_FLAG_PICKUP：比特2，表明鎖的交接準備已經做完了，可以等待被取走了；

mutex_optimistic_spin用于執行樂觀自旋，理想的情況下鎖持有者執行完釋放，目前程序就能很快的擷取到鎖。實際需要考慮，如果鎖的持有者如果在臨界區被排程出去了，task_struct->on_cpu == 0，那麼需要結束自旋等待了，否則豈不是傻傻等待了。

mutex_can_spin_on_owner：進入自旋前檢查一下，如果目前程序需要排程，或者鎖的持有者已經被排程出去了，那麼直接就傳回了，不需要做接下來的osq_lock/oqs_unlock工作了，節省一些額外的overhead；

osq_lock用于確定隻有一個等待者參與進來自旋，防止大量的等待者蜂擁而至來擷取互斥鎖；

for(;;)自旋過程中調用__mutex_trylock_or_owner來嘗試擷取鎖，擷取到後皆大歡喜，直接傳回即可；

mutex_spin_on_owner，判斷不滿足自旋等待的條件，那麼傳回，讓我們進入慢速路徑吧，畢竟不能強求；

3.2.3 slow-path

慢速路徑的主要代碼流程如下：

從for(;;)部分的流程可以看到，當沒有擷取到鎖時，會調用schedule_preempt_disabled将本身的任務進行切換出去，睡眠等待，這也是它慢的原因了；

3.3 釋放鎖流程分析

釋放鎖的流程相對來說比較簡單，也分為快速路徑與慢速路徑，快速路徑隻有在調試的時候打開；

慢速路徑釋放鎖，針對三種不同的MUTEX_FLAG來進行判斷處理，并最終喚醒等待在該鎖上的任務；

參考

Generic Mutex Subsystem

MCS locks and qspinlocks

歡迎關注個人公衆号，持續分享核心相關文章

作者：LoyenWang

出處：

https://www.cnblogs.com/LoyenWang/