iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 13
0

光是 rcu_deferencercu_assign_pointer 就能夠產生很多應用了,但在 Kernel 中並不會直接呼叫這兩個涵式作使用,而是將其包裝成更高階的形式,一個 List 的 API,會包裝成下面 struct list_head 的形式下去作使用

struct list_head

參考 Doubly linked list

之前在閱讀原始碼的時候,常常會看到這一個資料結構 struct list_head ,這是 Linux Kernel 中一個方便打包的 List 介面

struct list_head {
    struct list_head *next, *prev;
};

他的結構非常簡單,只包含前向跟後向指標

struct semaphore {
    raw_spinlock_t        lock;
    unsigned int        count;
    struct list_head    wait_list;
};

struct semaphore_waiter {
	struct list_head list;
	struct task_struct *task;
	bool up;
};

使用方法就是將他宣告在你自己的資料結構中,比如在 struct semaphore 結構中的 wait_list 就是 HEAD

但這邊要如何從 HEAD 存取我們的資料結構 struct semaphore_waiter 呢??

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

static noinline void __sched __up(struct semaphore *sem) {
    struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list, 
                                            struct semaphore_waiter, list);
   ....
}

這又會扯回 typeof 這個鬼東西,反正你就是把 HEAD 傳進去,再把目標資料結構傳進去,以及該資料結構中 struct list_head 的名字

這樣就可以透過 container_of 這個涵式取得該位置的資料

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({			\
	const typeof(((type *)0)->member) * __mptr = (ptr);	\
	(type *)((char *)__mptr - offsetof(type, member)); })

參考 Why this 0 in ((type*)0)->member in C?

以上程式碼普片都蠻好閱讀的,只有 (type *)0 看不太懂,這是因為 (type*)->member 是非法的語法,所以在之後加上 NULL pointer,然後在外面再包一層 typeof 即可取得該 Member Pointer __mptr

struct hlist_head

這是 struct list_head 的一個變形,Hash Table 版本的 List

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

光是結構就應用幾個技巧

  1. hlist_head 只有一個 pointer==,節省記憶體
  2. pprev 指向前一個指標的位置

pprev

指向前一個指標這種技巧很難解釋,就是 Linus 認為較棒的指標操作方式

參考 2018q3 Homework1 (linked list 和非連續記憶體操作)

typedef struct list {
    struct list_entry *head;
} list;

typedef struct list_entry {
    int val;
    struct list_entry *next;
} list_entry;

void remove_ptr(list *list, list_entry *target) {
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    list_entry **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

一般的 Linked List 刪除節點長這樣,需要特別判斷是否為 NULL,是不是 Head 阿,但如果是用 **p 的寫法,完全不需要考慮這問題,因為 pp 紀錄的是那個指標的位置,而不是指標指向哪一個記憶體,所以 *pp 就是直接修改該記憶體位置的內容,連結是 完整程式碼

注意:我們傳進去的東西是 list 不是 list_entry ,因為如果是直接傳 list_entry *head 進去涵式中,如果現在要改的是 Head,你會改不到他

至於其他東西我覺得自己閱讀也不會產生什麼障礙@@

rculist

新增

#define hlist_next_rcu(node)	(*((struct hlist_node __rcu **)(&(node)->next)))

static inline void __list_add_rcu(struct list_head *new,
		struct list_head *prev, struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

	new->next = next;
	new->prev = prev;
	rcu_assign_pointer(list_next_rcu(prev), new);
	next->prev = new;
}

static inline void list_add_rcu(struct list_head *new, struct list_head *head)
{
	__list_add_rcu(new, head, head->next);
}

重點在於什麼時候要使用 rcu_assign_pointer,其實非常簡單就能實現一個 RCU list 了

刪除

原版

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}

static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

RCU 版本

static inline void __list_del_entry(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
}

static inline void list_del_rcu(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->prev = LIST_POISON2;
}

刪除的部份看起來跟原本的一模一樣,因為 WRITE_ONCE 已經有確保 Atomic 操作了

但我看不懂為什麼原本的要修改賦予 LIST_POISON1 LIST_POISON2 RCU 版本卻只需要 LIST_POISON2??????????

Others

花了一些時間熟悉其他東西

  1. Session Cookie 之間的關係,以及 Session ID 該如何產生
    之前面試網頁工作的時候,被問到 Session 跟 Cookie 的差別你知道嗎,老實說我不知道== 只知道平常寫程式啥時要用啥而已

    參考

    不作任何摘要解釋,因為這可以獨立再寫一篇文章了,有興趣的可以自己閱讀

  2. rvalue reference
    因為想找個 C C++ 類型的工作,想說來熟悉一下 C++11 14 ,發現這根本是另外一個世界,rvalue reference 真是神奇的設計

    目前在加減看 Effective Modern C++ 中文版:提昇C++11與C++14技術的42個具體作法,真的是各種更新啦,而且他三年要更新一次,我 17 連摸都還沒摸,明年就要出 c++20 ==


上一篇
RCU API 原始碼閱讀
下一篇
近況更新
系列文
Linux Inside - Synchronization & Interrupt18

尚未有邦友留言

立即登入留言