# Reading [The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/) (8) # Completions 這邊書上解釋得很好就不多說了，跑出來的結果也符合預期 ``` ~ # insmod workspace/completions.ko [ 12.746763] completions: loading out-of-tree module taints kernel. [ 12.750578] completions example [ 12.752543] Turn the crank [ 12.752878] Flywheel spins up ``` # 同步 我自己的理解是，不論mutex,spinlock,semaphore都是設計來保護一段程式碼的執行，至於為何要保護這段程式碼原因可能是 * 有更改到數個threads共用的resource * 限制某個資源同時訪問的threads數量 針對第一種狀況，要特別注意的就是這個想要保護的resource(特別是mutex或spinlock的lock)必須在mutex或spinlock保護的區間更動才會有效，如果這些resource在其他程式片段被更動，可能會出現不符預期的狀況。 概念上，想要完美同步只有atomic operation或是disable preemption，但是atomic operation實在是太麻煩了要處理，例如: * Lock contention * Cache line bouncing 可能還會造成CPU stalling使的效率降低。至於disable preemption或disable interrupt則是降低多處理器的功能，代價也很大。另外atomic operation只保證該指令不會被中斷，如果有複雜的任務要atomic執行就沒辦法保證這數條指令是"一起照順序的執行"(critical section)，所以這些同步技術是必要的。 換句話說只要善用atomic operation和disable preemption和smp_mb(內存屏障，保證存取執行順序)就可以設計自己的同步演算法。 # Spinlock * 拿不到lock的threads會busy waiting，占用cpu資源 * 由於其他threads是占用cpu空轉，所以夾住的code盡量不要做太複雜的計算導致整體效能下降 但是如果沒有特別指定disable preemption，spinlock夾住的code還是會被interrupt，沒有處理好的話有可能在interrupt的過程破壞critical section的目的，一般來說，spinlock會使用raw_spin_lock_irqsave()，保障interrupt safe。因為這個函數disable preemption，在執行lock和unlock中間的code是不允許interrupt發生，並且用內存屏障保證被夾住的code執行的順序。 最糟糕的情況就是，程式A進入lock保護的區塊，但是過程中有其他threads觸發了interrupt讓程式B執行(如果lock中間不是disable preemption)，B成功執行，然而B也想用這個lock，但是程式A已經占用了，程式B因此進入等待，由於B沒有執行完成，除非有其他中斷進來停下B，否則B形成deadlock。 ### 補充 kernel裡面現在主要使用的lock algo是[queue spinlock](https://elixir.bootlin.com/linux/v6.15-rc7/source/kernel/locking/qspinlock.c#L109)，包裝MCS lock使global lock(qspinlock)的大小剛好是32bits(相容性的問題)，加入pending的機制，第一個沒拿到lock的thread會pending直到lock被釋放，其他等不到lock和pending或有其他競爭者在MCS waiting list的情況才會加入MCS lock，MCS lock的holder會global spinning([qspinlock](https://elixir.bootlin.com/linux/v6.15-rc7/source/kernel/locking/qspinlock.c#L328))，直到qspinlock被釋放且沒有pending的thread，MCS lock的holder才會得到qspinlock並釋放MCS lock，其他的則會local spinning([MCS lock](https://elixir.bootlin.com/linux/v6.15-rc7/source/kernel/locking/qspinlock.c#L291))。 詳細的過程可以看[這篇](http://www.wowotech.net/kernel_synchronization/queued_spinlock.html)，講得很好 # Semaphore 先看定義 ```c struct semaphore { raw_spinlock_t lock; unsigned int count; struct list_head wait_list; }; ``` 為和中間有個spinlock，目的就是讓count和wait_list的update是critical的，由於更新這些變數是比較快速完成的，所以使用spinlock是比較正確的方式。 根據[這篇](https://lwn.net/Articles/928026/)，semaphore現在使用的原則是counting semaphore，限制進入該程式碼的threads的數量。 Counting semaphore顧名思義就是有一個大於0的count，當down()發生時，如果count大於0，count會減1(用spinlock保護)並繼續執行，否則，會被sleep，直到up()發生將該threads從wait_list叫醒，另外，如果up()發生時wait_list沒有東西則count加1，進入的thread可以up()讓其他thread成功down()，但是wake的thread是由fifo的wait_list決定(link list)，確保公平性。這樣一來count一定是大於等於0的數字，詳細可看[這裡](https://elixir.bootlin.com/linux/v6.11.8/source/kernel/locking/semaphore.c)。 在過去binary semaphore和mutex是有一樣的功能，但是因為binary semaphore太常使用了，所以又特化出mutex，針對binary semaphore的情況做很多優化並加強安全性。至於原本的semaphore退化成counting semaphore，在第六版之後的kernel定義也從 ```c #define DEFINE_SEMAPHORE(name) \ struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1) ``` 改成 ```c #define DEFINE_SEMAPHORE(_name, _n) \ struct semaphore _name = __SEMAPHORE_INITIALIZER(_name, _n) ``` 多了一個參數，強迫使用者要設定count的值，而不是預設成binary semaphore(意味著除非有特殊必要，binary semaphore就是用mutex取代) # Mutex (binary semaphore pro max版本XD) Mutex不像semaphore會直接sleep被block的threads，也不像spinlock會持續佔著cpu資源，linux開發者選擇了先spinning(MCS lock)之後sleep，目的是假設在可以接受的時間內拿到lock，就先busy waiting(避免context switch)，等不到的情況才sleep。 透過這樣優化使mutex在大部分的狀態下都比binary semaphore更優秀。 ```clike struct mutex { atomic_long_t owner; raw_spinlock_t wait_lock; #ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* Spinner MCS lock */ #endif struct list_head wait_list; ... }; ``` 就像semaphore這裡的spinlock也是為了保護wait_list的更新，osq(optimistic_spin_queue)是為了避免sleep 造成context switch(如果current lock holder很快是放掉lock的話)。 對了還有件事要提，在disable preemption 或Atomic context不要sleep(spinlock保護的區塊使用mutex)，會浪費cpu資源或醒不來XD。可以使用might_sleep()在有可能會sleep的片段前面，當這段Code被atomic context執行時它會show warning，方便debug。 ```c might_sleep(); mutex_lock(&some_mutex); // Do stuff... mutex_unlock(&some_mutex); ``` TODO: Read [mutex解說](http://www.wowotech.net/kernel_synchronization/504.html) [Lockless Algo](https://lwn.net/Articles/844224/)