RWLock: 只有資料結構以及原理 ......

第 11 屆 iThome 鐵人賽

DAY 13

自我挑戰組

Linux Inside - Synchronization & Interrupt系列第 14 篇

11th鐵人賽

ian910297

2019-09-16 12:01:54

4414 瀏覽

分享至

我們已經從 Spinlock, Semaphore, Mutex 開始介紹，沿途還也研究了 Lock 與 Lock-Free 的設計，接下來會研究 RWLock 以及 RCU，兩者都是特化出來的機制，至於 SeqLock 就不做細部介紹，因為我打算觀摩 RWLock 以及 RCU 在專案中的應用，Scalability 的實驗可能只能先略過

Reader/Writer Lock

參考

Linux内核读写信号量实现
這篇我覺得實在寫得很好，可以從狀態機就直接看了當的理解程式碼的運作
Linux 核心設計: RCU 同步機制
一如既往的大雜燴，反正 jServ 老師每次都是把相關的東西，全部重頭介紹一次，當然如果只看大概介紹，其實還是不知道他怎麼做，這比較像是起個頭

RWLock 的規則是長這樣

同一時間允許一個 Writer 獲得 Lock
同一時間允許多個 Reader 獲得 Lock
同一時間 Reader 跟 Writer 不能同時獲得 Lock

可以使用狀態機來了解以上這三個規則的意義為何

Linux kernel 中有 R/W semaphore，就是指 RWLock，所以他的 API 是用 down_xxx up_xxx 下去做命名

資料結構

我們一樣先從資料結構開始看吧

include/linux/rwsem.h

struct rw_semaphore {
	atomic_long_t count;
	/*
	 * Write owner or one of the read owners as well flags regarding
	 * the current state of the rwsem. Can be used as a speculative
	 * check to see if the write owner is running on the cpu.
	 */
	atomic_long_t owner;
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* spinner MCS lock */
#endif
	raw_spinlock_t wait_lock;
	struct list_head wait_list;
};

count
主要是透過 count 這個數值來作控制，我們可以從程式碼的註解來看，他每個 bit 的定義是什麼
```
/*
 * On 64-bit architectures, the bit definitions of the count are:
 *
 * Bit  0    - writer locked bit
 * Bit  1    - waiters present bit
 * Bit  2    - lock handoff bit
 * Bits 3-7  - reserved
 * Bits 8-62 - 55-bit reader count
 * Bit  63   - read fail bit
 *
 * On 32-bit architectures, the bit definitions of the count are:
 *
 * Bit  0    - writer locked bit
 * Bit  1    - waiters present bit
 * Bit  2    - lock handoff bit
 * Bits 3-7  - reserved
 * Bits 8-30 - 23-bit reader count
 * Bit  31   - read fail bit
 * 
 * etc.
 * 
 * */
```
各使用一個 bit 來了解現在有沒有 Writer 或者 Waiter 存在，然後絕大部分的 bit 都用來計算 Reade 的數量

32 位元與 64 位元的架構，主要是差在允許存在的 Reader 數量多寡

handoff 就 google 翻譯來看，是指不可觸摸，

read fail bit 這個東西就很機車了，他是用來防止 Reader 夠多的時候，造成 count 變成負數，因為這樣就溢位了，在 Commit 中我們可以看到，他們把 read fail bit 稱作 guard bit
owner
osq
如以前提過的，覺得有些狀況不用作 Context Switch
wait_lock
鎖住 wait_list 的 Lock
wait_list
waiter 的 list
kernel/locking/rwsem.c

enum rwsem_waiter_type {
	RWSEM_WAITING_FOR_WRITE,
	RWSEM_WAITING_FOR_READ
};

struct rwsem_waiter {
	struct list_head list;
	struct task_struct *task;
	enum rwsem_waiter_type type;
	unsigned long timeout;
	unsigned long last_rowner;
};

程式碼

API 們

上鎖
- void down_read(struct rw_semaphore *sem);
- int down_read_trylock(struct rw_semaphore *sem);
- void down_write(struct rw_semaphore *sem);
- int down_write_trylock(struct rw_semaphore *sem);
釋放
- void up_read(struct rw_semaphore *sem);
- void up_write(struct rw_semaphore *sem);
- void downgrade_write(struct rw_semaphore *sem);

當然還有其他 API 不過這邊就是大概講一下而已

在開始研究邏輯之前，先看一下其中一個涵式

kernel/locking/rwsem.c

/*
 * lock for reading
 */
void __sched down_read(struct rw_semaphore *sem)
{
	might_sleep();
	rwsem_acquire_read(&sem->dep_map, 0, 0, _RET_IP_);

	LOCK_CONTENDED(sem, __down_read_trylock, __down_read);
}

比如說以這份程式來講，他三行程式都很重要，不過 rwsem_acquire_read 我們目前還沒有看過，而你一直追下去看會發現，這是跑去呼叫 lock_acquire_shared ，那什麼是 lock_acquire_shared 其實就是 lock_acquire，有沒有一種很熟悉的感覺，沒錯！又回到了 Spinlock 的懷抱，只是這是有些參數被寫死了

linux/include/linux/lockdep.h

#define LOCK_CONTENDED(_lock, try, lock)			\
do {								\
	if (!try(_lock)) {					\
		lock_contended(&(_lock)->dep_map, _RET_IP_);	\
		lock(_lock);					\
	}							\
	lock_acquired(&(_lock)->dep_map, _RET_IP_);			\
} while (0)

之前在 Spinlock 有提到 LOCK_CONTENDED 但那個時候，完全貼錯程式碼，因為我懶得去看＝＝，看人家的文章也不是最新的程式碼，這次去更新了一下，這樣對照上面的程式，就可以發現，傳進去的東西是兩個涵式，先 try 後 lock，反正只要 try 失敗就是接 slow_path_xxx 的涵式，幾乎都是這樣命名的＝＝

down_read

從涵式命名可以發現，其實這些涵式的主體都是 __ 開頭的涵式

#define RWSEM_UNLOCKED_VALUE		0L

#define RWSEM_WRITER_LOCKED	(1UL << 0)
#define RWSEM_FLAG_WAITERS	(1UL << 1)
#define RWSEM_FLAG_HANDOFF	(1UL << 2)
#define RWSEM_FLAG_READFAIL	(1UL << (BITS_PER_LONG - 1))

#define RWSEM_READER_SHIFT	8
#define RWSEM_READER_BIAS	(1UL << RWSEM_READER_SHIFT)
#define RWSEM_READER_MASK	(~(RWSEM_READER_BIAS - 1))
#define RWSEM_WRITER_MASK	RWSEM_WRITER_LOCKED
#define RWSEM_LOCK_MASK		(RWSEM_WRITER_MASK|RWSEM_READER_MASK)
#define RWSEM_READ_FAILED_MASK	(RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS|\
				 RWSEM_FLAG_HANDOFF|RWSEM_FLAG_READFAIL)

static inline int __down_read_trylock(struct rw_semaphore *sem)
{
	/*
	 * Optimize for the case when the rwsem is not locked at all.
	 */
	long tmp = RWSEM_UNLOCKED_VALUE;

	do {
		if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
					tmp + RWSEM_READER_BIAS)) {
			rwsem_set_reader_owned(sem);
			return 1;
		}
	} while (!(tmp & RWSEM_READ_FAILED_MASK));
	return 0;
}

try_lock 算是很好懂的一個涵式，就只是確認他是不是 Unlock ，然後幫他把 Reader 改成 1

!(tmp & RWSEM_READ_FAILED_MASK) 簡單的說就是防止溢位啦，然後他又同時把 Write Handoff 什麼的都寫進去這個 Mask，所以如果發現這個 Mask 是 True，就果斷退出，不是溢位了，就是被佔用了之類的

inline void __down_read(struct rw_semaphore *sem)
{
	if (!rwsem_read_trylock(sem)) {
		rwsem_down_read_slowpath(sem, TASK_UNINTERRUPTIBLE);
		DEBUG_RWSEMS_WARN_ON(!is_rwsem_reader_owned(sem), sem);
	} else {
		rwsem_set_reader_owned(sem);
	}
}

rwsem_read_trylock 是用來確認現在能不能 Lock，不能的話就是要進去 rwsem_down_read_slowpath 了

etc.

Others

每天要刷好幾題 Leetcode ，又要研究一下邏輯跟程式實作，覺得太吃不消了＝＝

blah blah blah 實在是看不太下去，要每個 Lock 都看程式碼真的無法，我決定更改一下方針，大概看一下他資料結構長什麼樣子，搭配人家的心得研究原理大概是什麼

除了以上原因之外，還有一個原因是因為，RWLock 還有 SeqLock 我真的沒什麼興趣，我其實只想研究 RCU 怎麼實作 ...... ，目前正在閱讀 Perfbook

BTW 之後的 Interrupt 部份比較難介紹，因為不同架構中的 Interrupt Handler 真的是差很大，目前還在找一些比較好閱讀的 GIC(Generic Interrupt Controller) 或是 APIC 文章來看，我會盡量避免看 Arm 的文件，因為實在是太多頁了

除此之外，我也想研究一下 Context Switch 的實作，因為前面提到了到底是要 Spin 還是 Context ，但是到底是怎麼作 Context 我卻完全不知道 ... ，也有聽同學講他去面試的時候，有被問到一題「User Mode 跟 Kernel Mode 之間是如何作切換，系統中是怎麼實作」，完全沒什麼頭緒，感覺是一題很綜合性的題目＝＝

Context 的文章我有先找好了，但還沒開始研究