# [Linux 核心設計](http://hackfoldr.org/linux/): RCU 同步機制 Copyright (**慣C**) 2019 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ## 點題 中國共產黨中央在 2019 年甫到來,即聲明「[中國人不打中國人](https://www.nownews.com/news/20190102/3151705/)」並表示「[願以最大誠意、盡最大努力爭取和平統一](https://newtalk.tw/news/view/2019-01-02/188674)」,儘管難以分辨真偽,不過在 Linux 核心中,「lock 不打 lock」的確是自 2002 年以來的共識,恰好在[九二共識](https://zh.wikipedia.org/zh-tw/%E4%B9%9D%E4%BA%8C%E5%85%B1%E8%AD%98)發布後的 10 年後,Linux 核心針對提升 scalability 而引入 RCU (Read-Copy Update),並且「盡最大努力」避免 lock 的存在,逐步實現「和平統一」。 RCU 作為 Linux 核心的同步機制之,允許多個 reader 在單一 writer 更新資料的同時,得以在不需要 lock 的前提,正確讀取資料。等一下,reader 可能讀到更新前或更新後的資料,但這樣怎麼會有「共識」呢? 本講座先回顧 spinlcok, rwlock 和 seqlock 的基本原理,複習在多核處理器中,對於共享資料處理所用到的 lock 成本,本質上是來自 mutual exclusion,但 RCU 則完全屏棄這樣的思維,採用 lock-free 機制來確保同步。Linux 核心近 20 年間朝向 scalability 和 realtime 做了頗多調整,RCU 自然就是反映這樣變化的同步機制,講座也會一併探討應用場景和 Real-Time Preemption and RCU 議題。 ## 和平統一: Universal Scalability Law (USL) $C(N)={\frac {N}{1+\alpha (N-1)+\beta N(N-1)}}$ 對於可擴展性 (scalability)的數學定義,透過給定的 $N$(使用者數量,或者是系統實體處理器數量),計算 $C$ (系統容量) 來建立模型,其中 $\alpha$ 和 $\beta$ 參數表示資源爭奪或對於共享資源的等待 (queueing)。 > Since there are no topological dependencies, C(N) can model symmetric multiprocessors, multicores, clusters, and GRID architectures. Also, because each of the three terms has a definite physical meaning, they can be employed as a heuristic to determine where to make performance improvements in hardware platforms or software applications. ![](https://i.imgur.com/De3fRtS.png) > If α and β are both zero, the system scales perfectly — throughput is proportional to load (or to processors in the system). > If α is slightly positive it indicates that part of the workload is not scalable. Hence the curve plateaus to the right. Another way of thinking about this is that some (shared) resource is approaching 100% utilization. > If in addition β is slightly positive, it implies that some resource is contended: for example, preliminary processing of new jobs steals time from the main task that finishes the jobs. [Neil Gunther](https://en.wikipedia.org/wiki/Neil_J._Gunther) 博士在 2008 年於[How to Quantify Scalability](http://www.perfdynamics.com/Manifesto/USLscalability.html) 一文總結: > The universal scalability law is equivalent to the synchronous queueing bound on throughput in a modified Machine Repairman with state-dependent service times. $\beta = 0$ 時,對應到 [Amdahl's law](https://en.wikipedia.org/wiki/Amdahl%27s_law): > Amdahl's law for parallel speedup is equivalent to the synchronous queueing bound on throughput in a Machine Repairman model of a multiprocessor. ![](https://i.imgur.com/AUcj9SO.png) 延伸閱讀: * [Scalability Modeling using Universal Scalability Law (USL)](https://wso2.com/blog/research/scalability-modeling-using-universal-scalability-law) * [Scalability is Quantifiable: The Universal Scalability Law | Data Council NYC '18](https://www.youtube.com/watch?v=EfOXY5XY9s8), Baron Schwartz 在多處理器環境中,光看單一應用程式的 cycle 數量,不足以得知真實的資源耗費,這是因為: * Operating System Code Paths * Inter-Cache Coherency traffic * Memory Bus contention * Lock synchronisation * I/O serialisation ## spinlock spinlock 是 Linux 中使用非常頻繁的 locking 機制。當 Process A 申請 lock 成功後,Process B 申請鎖就會失敗,但不會引發排程,一如粒子原地自旋 (spin)。 ![](https://i.imgur.com/yY4CWP4.png) > 出處: [Discovery of Electron Spin](http://www.quantum-field-theory.net/discovery-electron-spin/) 原地轉到 Process A 釋放 lock 為止,由於不會 sleep,也不會引發 schedule 的特性使然,在 interrupt context 中,資料的保護通常採用 spinlock。 ![](https://i.imgur.com/EwV16F3.png) > 出處: [Locking in OS Kernels for SMP Systems](http://irl.cs.ucla.edu/~yingdi/web/paperreading/smp_locking.pdf) > While CPU 1 (in process context) is holding the lock, any incoming interrupt requests on CPU 1 are stalled until the lock is released. An interrupt on CPU 2 busy waits on the lock, but it does not deadlock. > After CPU 1 releases the lock, CPU 2 (in interrupt context) obtains it, and CPU 1 (now executing the interrupt handler) waits for CPU 2 to release it. 若多個 process 申請 lock 的時候,當第一個申請 lock 成功的 process 在釋放時,其他 process 即刻處於競爭的關係,因此會造成不公平 (可能會有某個 process 頻繁持有 lock)。現在的 Linux 採用 [Ticket lock](https://en.wikipedia.org/wiki/Ticket_lock) 排隊機制,也就是說,誰先申請,誰就先得到 lock。 ![](https://i.imgur.com/kDDoYZY.png) > 出處: [洽公不再苦等 全新叫號系統打造有感服務](https://www.digitimes.com.tw/iot/article.asp?cat=158&id=0000336117_gda0vx9z265is66zsx556), 2007 對應到真實世界的案例,是銀行的辦事大廳通常會有多個窗口同步進行,並採用取號排隊。當你去銀行辦理業務時,首先會去取號機器領取號碼牌,上面寫著特定的流水號,然後你就可排隊等待,而且大廳內還會有醒目的顯示器,標注「請 xxx 號到 1 號窗口辦理」字樣,可能也會搭配自動廣播。每辦理完一個顧客的業務,顯示器上面的數字都會遞增。等待的顧客都會對比自己手上寫的編號和顯示器上面是否一致,若一致,即可去前台辦理業務。 試想以下情境:倘若剛開始營業,顧客 A 是本日第一個顧客,去取號機器領取 `0` 號 (`next` 數值) 號碼牌,然後看到顯示器上顯示 `0` (`owner` 數值),顧客 A 就知道現在輪到自己辦理業務。顧客 A 到前台辦理業務 (acquire lock) 的過程中,顧客 B 來了。同樣,顧客 B 去取號機器拿到 `1` 號 (`next` 數值) 號碼牌。然後顧客 B 靜候通知,而顧客 A 依舊辦理業務,此時顧客 C 也來了。顧客 C 去取號機器拿到`2` 號 (`next` 數值) 號碼牌。顧客 C 也靜靜找個座位等待。終於,顧客 A 的業務辦完了 (release lock),然後顯示器上面顯示 `1`(`owner` 數值),顧客 B 和 C 都比對顯示器上面的數字和自己手中號碼牌的數字是否相等。顧客 B 終於可辦理業務了 (acquire lock),但顧客 C 依然等待中。直到顧客 B 的業務辦完了 (release lock),然後顯示器上面顯示`2` (`owner` 數值),顧客 C 終於開始辦理業務 (acquire lock)。一旦顧客 C 的業務處理後 (release lock),這 3 個顧客都辦完了業務離開了,留下一個銀行櫃檯服務員。最終,顯示器上面顯示 `3` (`owner` 數值),取號機的下一個排隊號也是 3 號 (`next` 數值),無人辦理業務,也就是說 lock 處於釋放狀態。 Linux 針對每個 spinlock 會有兩個計數器: * `next` * `owner` 初始值皆為 `0`,當 Process A 申請 lock 時,會判斷 next 和 owner 的值是否相等。如果相等就代表 lock 可申請成功,否則原地自旋,直到 owner 和 next 的值相等才會退出自旋。假設 Process A 申請 lock 成功,然後 next 加 1,此時 `owner` 值為 `0`,`next` 值為`1`。Process B 也申請鎖,保存 next 得值到區域變數 tmp (內含值為 1) 中。由於 next 和 owner 值不相等,因此原地自旋讀取 owner 的值,判斷 owner 和 tmp 是否相等,直到相等退出自旋狀態。當然 next 的值還是加 1,變成 2。一旦 Process A 釋放 lock 後,會將 owner 的值加 1,那麼此時 Process B 的 owner 和 tmp 的值都是 1,因此 Process B 獲得鎖。當 Process B 釋放 lock 後,同樣會將 owner 的值加 1。最後 owner 和 next 都等於2,代表沒有 process 持有 lock。next 記錄著申請 lock 的次數,而 owner 是 process 持有 lock 的計數值。 :::info 以下 Linux 核心程式碼採用 [v4.20](https://elixir.bootlin.com/linux/v4.20/source),硬體架構是 Aarch32 (`arm`) / Aarch64 (`arm64`)。為了行文便利,程式碼做了適度排版和編輯,請一併參照原始程式碼。 ::: 首先定義描述 spinlock 的結構體 `arch_spinlock_t`,檔案 [arch/arm/include/asm/spinlock_types.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock_types.h) ```clike typedef struct { union { unsigned int slock; struct __raw_tickets { unsigned short owner; unsigned short next; } tickets; }; } arch_spinlock_t; ``` 如上所述,我們需要兩個計數器,分別是 owner 和 next。因為採用 `union` 宣告,無號整數 `slock` 佔用的記憶體空間涵蓋 owner 和 next。下面是申請 lock 操作 `arch_spin_lock` 的實作,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L56) ```clike static inline void arch_spin_lock(arch_spinlock_t *lock) { arch_spinlock_t old_lock; old_lock.slock = lock->slock; /* 1 */ lock->tickets.next++; /* 2 */ while (old_lock.tickets.next != old_lock.tickets.owner) { /* 3 */ wfe(); /* 4 */ old_lock.tickets.owner = lock->tickets.owner; /* 5 */ } } ``` 1. 延伸上面的案例,顧客從取號機得到號碼牌; 2. 取號機更新下個顧客將要拿到的排隊號; 3. 查閱顯示器,判斷是否輪到自己了; 4. `wfe` 是 Arm 架構的 [WFE (wait for event)](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka15473.html) 指令,讓 ARM 核進入低功耗模式。當 process 拿不到 lock 之際,只是原地自旋不如 CPU 進入休眠,可節省能源消耗。但這樣睡去後,該在何時醒來呢?就是等到持有 lock 的 process 釋放時,醒來判斷是否可以持有 lock。若不能獲得 lock,繼續睡眠即可。對應到真實世界的比喻,就是銀行顧客在大廳先打盹,等到廣播下一位排隊者時,醒來檢查是否輪到自己; 5. 前台已為上一個顧客辦理完成業務,剩下排隊的顧客都要抬頭看一下顯示器是不是輪到自己; 釋放 lock 的操作相比之下就很簡單,以上方銀行辦理業務的例子來說,釋放 lock 的操作僅僅是顯示器上面的排隊號加 `1`,也就是說,僅需要將`owner` 計數值遞增 1即可。`arch_spin_unlock` 實現如下,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L107) ```clike static inline void arch_spin_unlock(arch_spinlock_t *lock) { lock->tickets.owner++; dsb_sev(); } ``` dsb_sev() 對應到 Arm 架構的 [SEV 指令](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0204j/Cjafcggi.html),可發送訊號給所有處理器核。當 process 無法獲取 lock 的時候,會使用 WFE 指令讓 CPU 睡眠。現在釋放 lock,自然要喚醒所有睡眠的 CPU,醒來檢查自己是否可獲取 lock。 ## semaphore semaphore 是 process 間通信處理同步互斥的機制。負責協調各個 process ,保證他們能夠正確、合理地使用共享資源。和 spinlock 最大差異在於:無法獲取 semaphore 的 process 可以 sleep,因此會導致 schedule。 ![](https://i.imgur.com/opGlAN9.png) 為了記錄可用資源的數量,需要 `count` 計數器來標記目前可用資源數量,伴隨著另一個描述多少人等待的資料結構,在 Linux 核心中就是一個 doubly-linked list。實作程式碼如下,檔案 [include/linux/semaphore.h](include/linux/semaphore.h): ```clike struct semaphore { unsigned int count; struct list_head wait_list; }; ``` 在 Linux 中,還需要一個結構體記錄目前的 process 的資訊(`task_struct`),檔案 [include/linux/semaphore.h](include/linux/semaphore.h): ```clike struct semaphore_waiter { struct list_head list; struct task_struct *task; }; ``` `semaphore_waiter` 結構體的 `list` 成員是當 process 無法獲取 semaphore 的時候,加入到 semaphore 的 `wait_list` 成員。task成員就是記錄後續被喚醒的 proces 資訊。 1965 年荷蘭籍電腦科學家 [Edsger W. Dijkstra](https://en.wikipedia.org/wiki/Edsger_W._Dijkstra) 發展出解決資料同步議題的 semaphore 機制,後者就像是個管理系統資源的計數器,於是 semaphore 有時也稱為 Dijkstra Counters。 在 semaphore 的操作中,semaphore 控制內含的 counter 數值的增加或減少。若 semaphore 內在的 counter 達成 `0` 之際,任何新進來的 process/thread 會試圖把 counter 減少並必須等待直到另一個 process/thread 來增加其 counter。於是主要的操作如下: * `P` = `down` (記憶為「坐下去/卡位」) = `wait` / sleep,用來指示出目前的資源不能使用 (因為別的 process/thread 正在使用) * P 的全名是 "proberen te verlagen ",是荷蘭語,通常翻譯成「試圖減去 1」 * `V` = `up` (記憶為「還原」) = wakeup / `signal`,用來指示出目前的資源可供使用 (因為目前沒有別的 process/thread 在使用) * V 的全名是 "verhogen",荷蘭語表「加 1」的意思 注意 semaphore 的初始值可以是 `0`,表示沒有保存下來的 wakeup 操作,也就是只做單次 signal 用。 在 Linux 核心中,採用 `down` 和 `up` 來命名這兩項主要操作。 申請 semaphore 的 `down` 實作如下,檔案 [kernel/locking/semaphore.c](https://elixir.bootlin.com/linux/v4.20/source/kernel/locking/semaphore.c#L54) ```clike void down(struct semaphore *sem) { struct semaphore_waiter waiter; if (sem->count > 0) { sem->count--; /* 1 */ return; } waiter.task = current; /* 2 */ list_add_tail(&waiter.list, &sem->wait_list); /* 2 */ schedule(); /* 3 */ } ``` 1. 如果 semaphore 標記的資源還有剩餘,自然可成功獲取 semaphore。只需要遞減 counter; 2. 既然無法獲取 semaphore,就需將目前的 process 掛入 semaphore 的 `wait_list`; 3. `schedule()` 是觸發排程器,主動讓出 CPU 使用權。在讓出之前,需要將目前 process 從 runqueue 上移除; 釋放 semaphore 的實作如下,檔案 [kernel/locking/semaphore.c](https://elixir.bootlin.com/linux/v4.20/source/kernel/locking/semaphore.c#L179) ```clike void up(struct semaphore *sem) { struct semaphore_waiter waiter; if (list_empty(&sem->wait_list)) { sem->count++; /* 1 */ return; } waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list); list_del(&waiter->list); /* 2 */ wake_up_process(waiter->task); /* 2 */ } ``` 1. 如果 `wait_list` 沒有 process,那麼只需要增加 counter; 2. 從 `wait_list` 開頭取出第一個 process,並從 linked list 上移除。然後就是喚醒該 process; ## read-write lock (rwlock) 無論是 spinlock 還是 semaphore,在同一時間僅能有一個 process 進入 critical section (CS)。對於有些情況,我們可區分讀寫操作,進而提出最佳化機制,讓 read 操作的 process 可以並行 (concurrent) 運作。對於 write 操作僅限於一個 process 進入 CS。這種同步機制就是 rwlock,一般具有以下幾種性質: * 同一時間僅有一個 writer process 進入 CS; * 在沒有 writer process 進入 CS 時,同時可有多個 reader process 進入 CS; * reader process 和 writer process 不可以同時進入 CS; 讀寫鎖有兩種: 1. semaphore 類型 (rw_semaphore); 2. spinlock 類型; 以下講解 spinlock 類型。 ![](https://i.imgur.com/QJjTvM9.png) > [公廁一塵不染的背後,廁所清潔工付出的艱辛該不該被尊重?](https://kknews.cc/news/qqb695b.html) 以男廁來類比,男士進入廁所就相當於 reader 進入 CS,因為有多個男士進廁所,而清潔人員進入男廁就相當於 writer 進入 CS。 是想這情境:男士 A 發現清潔人員不在打掃廁所,就進入廁所。隨後男士 B 和男士 C 同時也進入廁所。然後清潔人員準備打掃廁所,發現有男士在廁所裡面,因此只能附近等待。之後,男士們 A, B, C 都離開廁所,清潔人員迅速進入廁所打掃,這時男士 D 去上廁所,發現清潔人員在裡面忙碌,只好在門口等著。用這現實案例可得知,writer (清潔人員) 具有排他性,reader (欲如廁的男士) 可以並行進入 CS。 既然我們允許多個 reader 進入 CS,因此我們需要一個計數統計 reader的方法。同時,由於 writer 永遠只會有一個進入 CS,因此只需要一個 bit 標記是否有 writer process 進入 CS。Linux 核心講究效率,將這兩個計數器合而為一,只用一個 32-bit unsigned int 表示: * 最高位 (bit 31): 代表是否有 writer 進入 CS; * 低 31 位(bit 30 - bit 0): 統計 reader 個數; ``` +----+-------------------------------------------------+ | 31 | 30 0 | +----+-------------------------------------------------+ | | | +----> [0:30] Read Thread Counter +-------------------------> [31] Write Thread Counter ``` 描述 rwlock 只需要一個變數,在 Linux 核心如此定義其結構,檔案 [arch/arm/include/asm/spinlock_types.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock_types.h#L30) ```clike typedef struct { volatile unsigned int lock; } arch_rwlock_t; ``` 既然區分讀寫操作,因此會有各自的申請讀寫 lock 函式,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L207) ```clike static inline void arch_read_lock(arch_rwlock_t *rw) { unsigned long tmp, tmp2; prefetchw(&rw->lock); __asm__ __volatile__( "1: ldrex %0, [%2]\n" " adds %0, %0, #1\n" " strexpl %1, %0, [%2]\n" WFE("mi") " rsbpls %0, %1, #0\n" " bmi 1b" : "=&r" (tmp), "=&r" (tmp2) : "r" (&rw->lock) : "cc"); smp_mb(); } ``` 上面的 inline assembly 對應等價的 C 程式如下 (有 exclusive monitor): ```clike do { wfe(); tmp = rw->lock; tmp++; /* 1 */ } while(tmp & (1 << 31)); /* 2 */ rw->lock = tmp; ``` 1. 增加 reader 計數,最後會更新到 `rw->lock` 中; 2. 更新 `rw->lock` 前提是沒有 writer,因此這裡會判斷是否有 writer 已進入 CS,也就是檢查 `rw->lock` 變數的 bit 31。如果已有 writer 進入 CS,就在這裡停駐,並透過 `WFE` 指令讓 CPU 睡眠,類似之前介紹 spinlock 的實作機制; 當 reader 離開 CS 時會呼叫 `read_unlock` 釋放 lock,後者的實作機制如下,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L226) ```clike static inline void arch_read_unlock(arch_rwlock_t *rw) { unsigned long tmp, tmp2; smp_mb(); prefetchw(&rw->lock); __asm__ __volatile__( "1: ldrex %0, [%2]\n" " sub %0, %0, #1\n" " strex %1, %0, [%2]\n" " teq %1, #0\n" " bne 1b" : "=&r" (tmp), "=&r" (tmp2) : "r" (&rw->lock) : "cc"); if (tmp == 0) dsb_sev(); } ``` 上面的 inline assembly 等價於以下 C 程式碼: ```clike rw->lock--; ``` 不難發現,實作機制類似 `spin_unlock`。遞減 reader 計數,然後使用 `SEV` 指令喚醒所有的 CPU,檢查等待狀態的 process 是否可獲取 lock。 看完 read 操作,繼續看 write 操作的實作方式,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L139) ```clike static inline void arch_write_lock(arch_rwlock_t *rw) { unsigned long tmp; prefetchw(&rw->lock); __asm__ __volatile__( "1: ldrex %0, [%1]\n" " teq %0, #0\n" WFE("ne") " strexeq %0, %2, [%1]\n" " teq %0, #0\n" " bne 1b" : "=&r" (tmp) : "r" (&rw->lock), "r" (0x80000000) : "cc"); smp_mb(); } ``` 上面的 inline assembly 等價於以下 C 程式: ```clike do { wfe(); tmp = rw->lock; } while (tmp); /* 1 */ rw->lock = 1 << 31; /* 2 */ ``` 1. 由於 writer 具排他性 (reader 和 writer 不得同時進入 CS),因此這裡只有 `rw->lock` 的值為 0 之際,目前的 writer 才可以進入 CS; 2. 設定 `rw->lock` 的 bit 31,代表有 writer 進入 CS; 當 writer 離開 CS 時,會呼叫 `write_unlock` 釋放 lock。`write_unlock` 實作如下,檔案 [arch/arm/include/asm/spinlock.h](https://elixir.bootlin.com/linux/v4.20/source/arch/arm/include/asm/spinlock.h#L182) ```clike static inline void arch_write_unlock(arch_rwlock_t *rw) { smp_mb(); __asm__ __volatile__( "str %1, [%0]\n" : : "r" (&rw->lock), "r" (0) : "cc"); dsb_sev(); /* 2 */ } ``` 上面的 inline assembly 等價於以下 C 程式: ```clike rw->lock = 0; /* 1 */ ``` 1. 同樣由於 writer 具排他性,因此只需要將 `rw->lock` 指派為 `0` 即可。代表沒有任何 process 進入 CS。畢竟是因為同一時間只能有一個 writer 進入 CS,當這個 writer 離開 CS 時,必定意味著現在沒有任何 process 進入 CS; 2. 使用 `SEV` 指令喚醒所有的 CPU,檢查等待狀態的 process 是否可獲取 lock; [Passive Reader-Writer Lock : Scalable Read-mostly Synchronization Using Passive Reader-Writer Locks](https://ipads.se.sjtu.edu.cn/pub/projects/prwlock),上海交通大學 [陳海波教授](https://ipads.se.sjtu.edu.cn/pub/members/haibo_chen) 領導開發的 prwlock,針對 Linux v3.8 進行修改。 ![](https://i.imgur.com/jBFIpf2.png) 1. When a running task is going to sleep on a condition, it is removed from Run-queue and inserted into PWake-queue. 2. The processes check whether the tasks in PWake-queue meet their conditions. If so, they are moved to the Run-queue from the PWake-queue. 3. A task in Run-queue is selected to execute by scheduler. 4. If no runnable tasks on the core, the idle cores use monitor & mwait instructions to sleep on a global word. 5. When a writer finishes its work, it wakens up the idle cores by touch the word. ## Queued/MCS Spinlock 取自 Davidlohr Bueso 的 [Futex Scaling for Multi-core Systems](https://www.slideshare.net/davidlohr/futex-scaling-for-multicore-systems) ![](https://i.imgur.com/IxRvo5B.png) ![](https://i.imgur.com/7KuAw2Y.png) 延伸閱讀: [Much Ado About Blocking: Wait/Wake in the Linux Kernel](https://www.slideshare.net/davidlohr/much-ado-about-blocking-waitwakke-in-the-linux-kernel) ## lock 不打 lock! lock 對 scalability 衝擊極大。 - [ ] UNSW Advanced Operating System 教材 [SMP, Multicore, Memory Ordering & Locking](https://www.cse.unsw.edu.au/~cs9242/18/lectures/08-smp_locking.pdf) 指出一個血淋淋的教訓 實驗環境: * Linux 2.6.35-rc5 (relatively old, but problems are representative of issues in recent kernels too) * Off-the-shelf 48-core server (AMD) ![](https://i.imgur.com/BxzAMuV.png) ![](https://i.imgur.com/A7bkoCP.png) [Exim](https://www.exim.org/) 是一套由劍橋大學發展的 message transfer agent (MTA),實驗指出,在處理器核數超過 40 後,throughput 不升反降,而且耗費在核心的時間大幅增加。 透過 oprofile 指出效能瓶頸: ![](https://i.imgur.com/EEQC7yg.png) 發現 [Exim](https://www.exim.org/) 透過 `open` 系統呼叫去派送電子郵件時,`open` 系統呼叫的 Linux 實作花了很多時間在查詢 mount table: ```clike struct vfsmount *lookup_mnt(struct path *path) { struct vfsmount *mnt; spin_lock(&vfsmount_lock); mnt = hash_get(mnts, path); spin_unlock(&vfsmount_lock); return mnt; } ``` 但 `spin_lock` 和 `spin_unlock` 之間的區域看似很短,會是影響 scalability 的關鍵嗎? ticket spin locks 是 non-scalable 的實作。 ![](https://i.imgur.com/t16rsvb.png) (對照 Page 96-109) 僅是避免 lock collapse 是不夠的! 參照 [An Overview of Linux Kernel Lock Improvements](https://www.slideshare.net/davidlohr/linuxcon-2014lockingfinal), Davidlohr Bueso (2014) 延伸閱讀 [多核處理器和 spinlock](https://hackmd.io/s/rJbXgzz-4) 為了徹底改善問題,我們需要另闢蹊蹺: * Lock-free algorithms * Allow safe concurrent access without excessive serialisation * 有很多技巧和途徑,在 Linux 核心中,我們探討以下: - Sequential locks (seqlock) - Read-Copy-Update (RCU) ## seqlock ![](https://i.imgur.com/PJrGQqH.png) * The idea is to keep a sequence number that is updated (twice) every time a set of variables is updated, once at the start, and once after the variables are consistent again. While a writer is active (and the data may be inconsistent) the sequence number is odd; while the data is consistent the sequence is even. * The reader grabs a copy of the sequence at the start of its section, spinning if the result is odd. At the end of the section, it rereads the sequence, if it is different from the first read value, the section is repeated. * This is in effect an optimistic multi-reader lock. Writers need to protect against each other, but if there is a single writer (which is often the case) then the spinlocks can be omitted. A writer can delay a reader; readers do not delay writers – there’s no need as in a standard multi-reader lock for writers to delay until all readers are finished. * This is used amongst other places in Linux for protecting the variables containing the current time-of-day. ## RCU - [ ] [Introduction to RCU Concepts](http://events17.linuxfoundation.org/sites/events/files/slides/userspace-rcu-tutorial-linuxcon-2013.pdf), Paul E. McKenney ![](https://i.imgur.com/Xr2BVrv.png) ![](https://i.imgur.com/k4yeDmQ.png) ![](https://i.imgur.com/GFu2l9e.png) 應用場景: * 需要 concurrent reading and writing - 例: directory entry cache replacement * 低度運算和儲存的負擔 - 例: storage overhead in directory cache * Deterministic completion times - 例: non-maskable interrupt handlers in real-time systems * NMI 處理程式 ![](https://i.imgur.com/lHCyFt2.png) 現代的伺服器在前方面板上有個實體的 NMI 按鈕: ![](https://i.imgur.com/x0FTWm8.png) > [Dell PowerEdge 2650: Diagnostic Indicators](http://alexandre.julie.free.fr/dtc.smartelearning.com/training/docs/pe2650/troubleshooting_indicators.html) watchdog interrupt 可傳送到 NMI,進而得到系統出現問題(比如 hard lock,檢測在中斷禁止情況下的 deadlock) 的現場資訊,而不是僅僅重啟。Hard lockup detector 使用一個週期性的 NMI 來檢測中斷被長時間關閉而導致嚴重的問題(hard lockup)。 ```clike rcu_list_t nmi_list; spinlock_t nmi_list_lock; void handle_nmi() { rcu_read_lock(); rcu_list_for_each(&nmi_list, handler_t cb) cb(); rcu_read_unlock(); } void register_nmi_handler(handler_t cb) { spin_lock(&nmi_list_lock); rcu_list_add(&nmi_list, cb); spin_unlock(&nmi_list_lock); } void unregister_nmi_handler(handler_t cb) { spin_lock(&nmi_list_lock); rcu_list_remove(cb); spin_unlock(&nmi_list_lock); synchronize_rcu(); } ``` > RCU list 函式包含必要的 `rcu_dereference` 和 `rcu_assign_pointer` 呼叫 參見: [Using RCU to Protect Dynamic NMI Handlers](https://www.kernel.org/doc/Documentation/RCU/NMI-RCU.txt) spinlock 是互斥的,任何時候只有一個thread(reader or writer)進入 CS,rwlock 則允許多個 reader 並行,提高效能。不過,reader 和 writer 不能並行,RCU 解除了這些限制,允許一個 writer (不能多個 writer 進入 CS) 和多個 reader 並行。以下圖例: ![](https://i.imgur.com/JW1ls3W.png) rwlock 允許多個 reader 並行,因此在上圖中,三個 rwlock reader 並行無誤。當 rwlock writer 試圖進入時 (垂直紅色虛線),只能 spin,直到所有的 reader 退出 CS。一旦有 rwlock writer 在 CS,任何的 reader 都不能進入,直到 writer 完成資料更新,離開 CS。綠色的 reader 又可運作。 rwlock 的一個特點就是 deterministic,白色的 reader 一定是讀取的是 old data,而綠色的 reader 一定獲取的是 writer 更新之後的 new data。 RCU和傳統的 lock 機制不同,當 RCU writer/updater 進入 CS 之際,即便是有 reader 在也無妨,它可長驅直入,不需要 spin。同樣,即便有一個 updater 正在 CS 裡面工作,這並不能阻擋 RCU reader 的步伐。由此可見,RCU 的並行能力優於 rwlock,特別如果考慮 CPU 的數目比較多的情況,那些處於 spin 狀態的 CPU 在無謂的消耗,將會嚴重影響 scalability,隨著 CPU 的數目增加,rwlock 效能不斷下降。RCU reader 和 updater 由於可並行,因此這時的被保護的資料有兩份,一份是舊的,一份是新的,對於白色的 RCU reader,其讀取的資料可能是舊的,也可能是新的,和資料存取的時間息息相關。當然,當 RCU update 完成更新後,新啟動的 RCU reader (綠色區塊) 讀取的一定是新的資料。 - [ ] [Multiprocessor Synchronization using Read-Copy Update](https://os.inf.tu-dresden.de/Studium/DOS/SS2011/06-RCU.pdf) ![](https://i.imgur.com/RanpL5A.png) > [Lock-free Data Structures. The Inside. RCU](https://kukuruku.co/post/lock-free-data-structures-the-inside-rcu/) 延伸閱讀: [Linux 核心同步機制之(七):RCU 基礎](http://www.wowotech.net/kernel_synchronization/rcu_fundamentals.html) - [ ] [Kernel Scalability](https://pdos.csail.mit.edu/6.828/2018/lec/l-rcu.pdf), Adam Belay * Kernels often have data that is read much more often than it is modified * Network tables: routing, ARP * File descriptor arrays, most types of system call state * RCU optimizes for these use cases * Over 10K RCU API uses in the Linux Kernel! * Goals * Concurrent reads even during updates * Low space overhead * Low execution overhead ![](https://i.imgur.com/9DkRx6N.png) ==When to free old objects?== * Idea: Can safely free objects when they are no longer “reachable” * Usually only one pointer to an RCU object * Can’t be copied, stored on the stack, or in registers (except inside critical sections) * Need to define a “quiescent period”, after which it’s safe to free * Wait until all cores have passed through a context switch * Pointer can only be dereferenced inside a critical section * Read critical sections disable preemption ==Why disable preemption during RCU read critical sections?== * If we didn’t, waiting for all cores to context switch wouldn’t be an effective quiescent period * A task could still hold a pointer to an RCU object while it is preempted * Hard to determine when its safe to free * Unless we wait until all current tasks are killed * Need to define a read critical section such that references to RCU objects can’t persist outside the section 概念上的 RCU APIs: ```clike void rcu_read_lock() { preempt_disable[cpu_id()]++; } void rcu_read_unlock() { preempt_disable[cpu_id()]--; } void synchronize_rcu(void) { for_each_cpu(intcpu)run_on(cpu); } ``` 實際 RCU APIs: * `rcu_read_lock()`: Begin an RCU critical section * `rcu_read_unlock()`: End an RCU critical section * `synchronize_rcu()`: Wait for existing RCU critical sections to complete * `call_rcu(callback, argument)`: Call the callback when existing RCU critical sections complete * `rcu_dereference(pointer)`: Signal the intent to dereference a pointer in an RCU critical section * `rcu_dereference_protected(pointer, check)`: signals the intent to dereference a pointer outside of an RCU critical section * `rcu_assign_pointer(pointer_addr, pointer)`: Assign a value to a pointer that is read in RCU critical sections 用 [rcu-examples](https://github.com/jinb-park/rcu_example) 解說 [Notes on Read-Copy Update](https://read.seas.harvard.edu/~kohler/class/cs261-f11/rcu.html) [深入理解 Linux 的 RCU 機制](https://cloud.tencent.com/developer/article/1006204) [Yet another introduction to Linux RCU](https://www.slideshare.net/vh21/yet-another-introduction-of-linux-rcu) [Using RCU for linked lists — a case study](https://lwn.net/Articles/610972/) [Hierarchical RCU](https://lwn.net/Articles/305782/) [Real-Time Preemption and RCU](https://lwn.net/Articles/128228/) [sleepable RCU的實現](http://www.wowotech.net/kernel_synchronization/linux2-6-23-RCU.html) [Verification of Tree-Based HierarchicalRead-Copy Update in the Linux Kerne](http://www.kroening.com/papers/date2018-rcu.pdf) * [srcu-cbmc](https://github.com/torvalds/linux/tree/master/tools/testing/selftests/rcutorture/formal/srcu-cbmc): Linux 核心內部極少數引入 [形式化驗證](https://hackmd.io/s/H1xxp3pF0) 的程式碼