參考
這邊要介紹的就是 arch_spin_lock
LOCK_CONTENDED
#define LOCK_CONTENDED(_lock, try, lock) \
lock(_lock)
static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{
__acquire(lock);
arch_spin_lock(&lock->raw_lock);
}
#define arch_spin_lock(l) queued_spin_lock(l)
在看 queued_spin_lock 之前，我們要先了解一下他的資料結構
typedef struct qspinlock {
union {
atomic_t val;
/*
* By using the whole 2nd least significant byte for the
* pending bit, we can allow better optimization of the lock
* acquisition for the pending bit holder.
*/
#ifdef __LITTLE_ENDIAN
struct {
u8 locked;
u8 pending;
};
struct {
u16 locked_pending;
u16 tail;
};
#else
struct {
u16 tail;
u16 locked_pending;
};
struct {
u8 reserved[2];
u8 pending;
u8 locked;
};
#endif
};
} arch_spinlock_t;
/*
* Initializier
*/
#define __ARCH_SPIN_LOCK_UNLOCKED { { .val = ATOMIC_INIT(0) } }
/*
* Bitfields in the atomic value:
*
* When NR_CPUS < 16K
* 0- 7: locked byte 長度剛好是一個 WORD
* 8: pending 第一個等待的處理器，設置 pending
* 9-15: not used
* 16-17: tail index tail 使用哪一個 mcs_node
* 18-31: tail cpu (+1) tail 的 CPU 處理器編號+1
*
* When NR_CPUS >= 16K
* 0- 7: locked byte
* 8: pending
* 9-10: tail index
* 11-31: tail cpu (+1)
*/
Little-Endian & Big-Endian 有關
參考 Big-Endian 與 Little-Endian 的差異與判斷程式碼
這代表在記憶體中儲存資料的方式，依照機器不同會有所不同，假設現在有一個數字是 0x12345678，他在記憶體中儲存的方式可能會長得不一樣，而這種方式可能會影響到我們寫程式的時候，作指標操作阿，還是什麼的，儲存結構如下：
記憶體位置由左到右代表由低到高
Big-Endian
low high
-----------------------------
| 0x12 | 0x34 | 0x56 | 0x78 |
-----------------------------
a a+1 a+2 a+3
low high
-----------------------------
| 0x78 | 0x56 | 0x34 | 0x12 |
-----------------------------
a a+1 a+2 a+3
通常 intel 系列的電腦都是 Little-Endian 的架構，如果想使用 C 語言測試自己的電腦是什麼種架構，可以使用 union 的技巧來判斷
註解中有提到，每個 bit 的意義為何
0-7 Lock8 未使用16-17 MCS 中的哪一顆 CPU18-31 Queue 末端的處理器數量為什麼還沒有提到 mcs_spinlock 中存在的 next 等資料結構？？這樣到底要怎麼建立 Queue？？？
這跟 struct page 有關，如果使用之前 mcs_spinlock 的資料結構，跟 struct page 搭不太起來，在 struct page 中就算只是增加一個 bit 的大小，也都會對系統產生巨大影響，更多資訊可以參考 Cramming more into struct page，那已經完全是 Memory Model 範疇，在此不多作研究
queued_spin_lock 資料結構#define arch_spin_lock(l) queued_spin_lock(l)
static __always_inline void queued_spin_lock(struct qspinlock *lock)
{
u32 val;
val = atomic_cmpxchg_acquire(&lock->val, 0, _Q_LOCKED_VAL);
if (likely(val == 0))
return;
queued_spin_lock_slowpath(lock, val);
}
核心操作這只跟兩個涵式有關
atomic_cmpxchg_acquire 沒啥重點，就是最後跑去呼叫 CAS ，當然這中間又包了很多層結構，因為每個處理器架構的 CAS 實作不太相同
#define __raw_cmpxchg(ptr, old, new, size, lock) \
({ \
__typeof__(*(ptr)) __ret; \
__typeof__(*(ptr)) __old = (old); \
__typeof__(*(ptr)) __new = (new); \
\
volatile u32 *__ptr = (volatile u32 *)(ptr); \
asm volatile(lock "cmpxchgl %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory"); \
\
__ret; \
})
涵式回傳的數值為 __ret ，是指 __old 的意思
queued_spin_lock_slowpath
如果現在沒辦法直接獲得 Lock，就會進入到這個涵式中，但他的程式碼有點太長，所以我們只擷取重點來看
看到以下註解，描述了在 queued_spin_lock 中存在的邏輯，可以想像成狀態機的概念，將整個邏輯分類為三種 blah blah blah，我不從程式碼一行一行解釋，會舉例來說，如果有第二個 Thread 要要求 Lock，那麼程式邏輯會長怎樣，與 MCS Lock 又有何不同
/**
* queued_spin_lock_slowpath - acquire the queued spinlock
* @lock: Pointer to queued spinlock structure
* @val: Current value of the queued spinlock 32-bit word
*
* (queue tail, pending bit, lock value)
*
* fast : slow : unlock
* : :
* uncontended (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
* : | ^--------.------. / :
* : v \ \ | :
* pending : (0,1,1) +--> (0,1,0) \ | :
* : | ^--' | | :
* : v | | :
* uncontended : (n,x,y) +--> (n,0,0) --' | :
* queue : | ^--' | :
* : v | :
* contended : (*,x,y) +--> (*,0,0) ---> (*,0,1) -' :
* queue : ^--' :
*/
繼續研究程式後，終於找到了 mcs_spinlock 在哪邊，他被宣告在一個 qnode 底下，而每顆 CPU 會有四個 qnode，paravirt_XXXX 的部份不用理他，那跟虛擬化有關，目前我還看不懂@@
#define MAX_NODES 4
static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[MAX_NODES]);
struct qnode {
struct mcs_spinlock mcs;
#ifdef CONFIG_PARAVIRT_SPINLOCKS
long reserved[2];
#endif
};
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
int count; /* nesting count, see qspinlock.c */
};
那把目光轉回 mcs_spinlock 與 qnode，為什麼需要宣告四個 qnode？？？在 MCS Lock 中不是每顆 CPU 只需要持有一個 mcs_spinlock 即可形成 Queue 嗎？？？
這是因為要跟 Linux Kernel 中既存的 API 作結合，也就是以下四種中斷：
程式碼的中的註解有解釋，最多一顆 CPU 只能有 4 個 qnode ，但不確定是否是一個 qnode 對應一種中斷，還是怎樣？？關於中斷的更多解釋，留待我們介紹完 Synchronization 之後再做探討
queued_spin_lock_slowpath 邏輯參考 [知其然不知其所以然-32] Queued Spinlock
#define arch_spin_lock(l) queued_spin_lock(l)
static __always_inline void queued_spin_lock(struct qspinlock *lock)
{
u32 val;
val = atomic_cmpxchg_acquire(&lock->val, 0, _Q_LOCKED_VAL);
if (likely(val == 0))
return;
queued_spin_lock_slowpath(lock, val);
}
第一個 Thread 要求 Lock
現在沒有人在競爭 Lock ，那麼第一個要求 Lock 的 Thread 所獲得的回傳值是 0，且 _Q_LOCKED_VAL 被更改為 1
因為回傳值是 0 ，涵式執行完，會在下個判斷式就直接結束，不會前進到 queued_spin_lock_slowpath
第二個 Thread 要求 Lock
因為已經有一個 Thread 取得 Lock，假設現在有第二個 Thread 要取得 Lock，他就會進入 queued_spin_lock_slowpath
Lock((queue tail, pending bit, lock value)) 結構長這樣 L(0, 0, 1)
因為他現在正在等待所以 Lock 結構會變換為 L(0, 1, 1)，pending bit 被設定為 1 了
注意，這個時候我們還沒有建立 Queue，只有兩個 Thread 的情況，還沒有必要建立 Queue
第三個 Thread 要求 Lock
目前的 Lock 數值是 L(0, 1, 1) ，因為已經有一個 Thread 正在 pending 的狀態，所以第三個 Thread 會導向去 Queue 中
queue:
lockevent_inc(lock_slowpath);
pv_queue:
// 這時還只是 head
node = this_cpu_ptr(&qnodes[0].mcs);
idx = node->count++;
tail = encode_tail(smp_processor_id(), idx);
// 根據 index 去抓 mcs_node 出來
node = grab_mcs_node(node, idx);
再對照到最上面邏輯的註解，可以發現當 Lock 數值為 L(0, 1, 1) 的時候，下一個要求的 Thread 就必須建立 Queue 了，而建立 Queue，又有分為 uncontented queue 以及 contended queue 兩個狀態
uncontended 與 contended 的差別在於 pending bits 到底存不存在，如果 pending bit 被設為 1 ，則代表 contended
第四個 Thread 要求 Lock
blah blah blah
到這邊，我覺得這樣大概了解就好了，一直看 Code 看心得＝＝，很遺憾我還是不知道四個 qnode 的設計反應在哪裡？但我不打算改動這邊的程式碼，時間有限不想看得那麼仔細＝＝
參考 Deadlock, Starvation, and Livelock
大致了解了 Queued Spinlock 邏輯，而 Livelock 這個部份無關 Queued Spinlock，就只是想介紹，因為在看 jServ 老師的影片時，他是在介紹 Spinlock 的時候，順便介紹 Livelock，所以我也仿照
Livelock 是指使用 Lock 會產生的一個特殊狀況，可能在使用 Semaphore, Mutex 又或者是 Spinlock 時發生
大家一般都知道 Deadlock 是指程式卡住了，完全不會動作，比如說以下程式：
pthread_mutex_t mutex;
pthread_mutex_init(&mutex);
pthread_mutex_lock(&mutex);
pthread_mutex_lock(&mutex);// deadlock
pthread_mutex_unlock(&mutex);
pthread_mutex_unlock(&mutex);
如果沒有特別宣告 Recursive 的屬性，這樣就會造成 Deadlock 了，那什麼是 Livelock？？Livelock 指的是程式一直在運行，但是實際上程式執行的流程，只是不斷的作判斷，並沒有執行什麼任務，是一種很特殊的 Resource Starvation ，參考以下程式
var l1 = .... // lock object like semaphore or mutex etc
var l2 = .... // lock object like semaphore or mutex etc
// Thread1
Thread.Start(()=> {
while (true) {
if (!l1.Lock(1000)) {
continue;
}
if (!l2.Lock(1000)) {
continue;
}
/// critical section
}
);
// Thread2
Thread.Start(()=> {
while (true) {
if (!l2.Lock(1000)) {
continue;
}
if (!l1.Lock(1000)) {
continue;
}
// critical section
}
);
Thread 1 先要求 l1 Lock，再要求 l2 Lock，任一個要求失敗的話，就直接進入下一層迴圈
Thread 2 先要求 l2 Lock，再要求 l1 Lock，任一個要求失敗的話，就直接進入下一層迴圈
但這個時候 l1 被 Thread 1 持有，而 l2 被 Thread 2 持有，雖然迴圈一直在運作，但是完全無法執行 CS 的內容
這個例子可能沒有很好理解，參考 Understanding Deadlock, Livelock and Starvation with Code Examples in Java，現在有兩組人馬：歹徒跟警察，警察要看到人質走出來才會給附贖金，歹徒要看到贖金才會釋放人質，因為沒有人要退一步，所以就會無限的僵持下去，但雙方都還在正常運作，這也是一種 Livelock
要有效避免 Livelock 沒有什麼既定的方法，根據每個案例會有點區別
明天家裡也是有點事情，原本要講 Semaphore 然後接 Mutex，但這兩個東西的文章我還沒閱讀完，現在可能會講 lockdep 因為已經有很完整的中文解釋，不太需要動腦== 但 ...... 如果要講 lockdep 我會想一些 Lab 來做的！
iThome鐵人賽
看影片追技術