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

struct list_head

參考 Doubly linked list

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

• include/linux/types.h

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 呢？？

• include/linux/list.h

#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 這個涵式取得該位置的資料

• tools/include/linux/kernel.h

#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

• include/linux/types.h

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

新增

• include/linux/rculist.h

#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 的差別你知道嗎，老實說我不知道＝＝ 只知道平常寫程式啥時要用啥而已

   參考

   • 白話 Session 與 Cookie：從經營雜貨店開始
     Overview
   • 淺談 Session 與 Cookie：一起來讀 RFC
     標準演進以及範例
   • 深入 Session 與 Cookie：Express、PHP 與 Rails 的實作 #46
     Framework 中的實作，不過 Framework 我只有比較熟悉 Laravel ，看以上幾個範例沒啥感觸，應該會再去另外研究
   • UUID原理
   • UUID是如何保证唯一性的？
     因為他沒提到 UUID 如何產生，又適用於什麼，這邊補上我看過覺得不錯的介紹

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

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

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