iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 6
0
自我挑戰組

Linux Inside - Synchronization & Interrupt系列 第 6

Spinlock 原始碼觀摩(二) & Livelock

參考

這邊要介紹的就是 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 Spinlock 資料結構

在看 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
  • Little-Endian
low                       high
-----------------------------
| 0x78 | 0x56 | 0x34 | 0x12 |
-----------------------------
   a     a+1    a+2    a+3

通常 intel 系列的電腦都是 Little-Endian 的架構,如果想使用 C 語言測試自己的電腦是什麼種架構,可以使用 union 的技巧來判斷

  • 註解中有提到,每個 bit 的意義為何

    • 0-7 Lock
    • 8 未使用
    • 16-17 MCS 中的哪一顆 CPU
    • 18-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);
}

核心操作這只跟兩個涵式有關

  1. 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 的意思

  1. 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 會有四個 qnodeparavirt_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_spinlockqnode,為什麼需要宣告四個 qnode???在 MCS Lock 中不是每顆 CPU 只需要持有一個 mcs_spinlock 即可形成 Queue 嗎???

這是因為要跟 Linux Kernel 中既存的 API 作結合,也就是以下四種中斷:

  1. task(normal task context)
  2. hardirq(hardware interrupt context)
  3. softirq(software interrupt context)
  4. NMI(non-maskable interrupt context)

程式碼的中的註解有解釋,最多一顆 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);
}
  1. 第一個 Thread 要求 Lock
    現在沒有人在競爭 Lock ,那麼第一個要求 Lock 的 Thread 所獲得的回傳值是 0,且 _Q_LOCKED_VAL 被更改為 1

    因為回傳值是 0 ,涵式執行完,會在下個判斷式就直接結束,不會前進到 queued_spin_lock_slowpath

  2. 第二個 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

  3. 第三個 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 兩個狀態

    uncontendedcontended 的差別在於 pending bits 到底存不存在,如果 pending bit 被設為 1 ,則代表 contended

  4. 第四個 Thread 要求 Lock
    blah blah blah

    到這邊,我覺得這樣大概了解就好了,一直看 Code 看心得==,很遺憾我還是不知道四個 qnode 的設計反應在哪裡?但我不打算改動這邊的程式碼,時間有限不想看得那麼仔細==

Others: Livelock

參考 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 沒有什麼既定的方法,根據每個案例會有點區別

Others

明天家裡也是有點事情,原本要講 Semaphore 然後接 Mutex,但這兩個東西的文章我還沒閱讀完,現在可能會講 lockdep 因為已經有很完整的中文解釋,不太需要動腦== 但 ...... 如果要講 lockdep 我會想一些 Lab 來做的!


上一篇
Spinlock 原始碼觀摩(—)
下一篇
Semaphore
系列文
Linux Inside - Synchronization & Interrupt18

尚未有邦友留言

立即登入留言