# 2021q3 Homework2 (hp)
contributed by < `demonsome` >
###### tags: `2021 Summer - Linux kernel`
> [第 2 週測驗題題目](https://hackmd.io/@sysprog/linux2021-summer-quiz2)
## 延伸問題
**1. 解釋上述程式碼運作原理**
我們先從主程式開始:
```c=
int main(void)
{
list_t *list = list_new();
pthread_t thr[N_THREADS];
for (size_t i = 0; i < N_THREADS; i++)
pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
list);
for (size_t i = 0; i < N_THREADS; i++)
pthread_join(thr[i], NULL);
for (size_t i = 0; i < N_ELEMENTS; i++) {
for (size_t j = 0; j < tid_v_base; j++)
list_delete(list, (uintptr_t) &elements[j][i]);
}
list_destroy(list);
fprintf(stderr, "inserts = %zu, deletes = %zu\n", atomic_load(&inserts),
atomic_load(&deletes));
return 0;
}
```
我們可以發現主程式一開始建立了一個 list 後，再創造了64個 [POSIX thread](https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html) (pthread) 。提到 pthread ，這種執行緒可在多個核心並行以提升程式執行效能。然而，並行程式設計的挑戰在於多個運算核心對共享資源的存取的問題。
這次的作業探討了 lock-free 的 hazard pointer 結構在並行程式上執行的可行性。這裡建立 pthread 是為了測試這個使用 hazard pointer 的 list 結構。檢視它的新增節點 (insert) 、刪除節點 (delete) 計數是否一致。
**結構 Harzard pointer list 初始化**
初始化 list 的函式如下:
```c=
list_t *list_new(void)
{
list_t *list = calloc(1, sizeof(*list));
assert(list);
list_node_t *head = list_node_new(0), *tail = list_node_new(UINTPTR_MAX);
assert(head), assert(tail);
list_hp_t *hp = list_hp_new(3, __list_node_delete);
atomic_init(&head->next, (uintptr_t) tail);
*list = (list_t){.hp = hp};
atomic_init(&list->head, (uintptr_t) head);
atomic_init(&list->tail, (uintptr_t) tail);
return list;
}
```
list 初始化時，創造兩個 node ，其一是 head node 其 key 值是0，另一個是 tail node 其 key 值是 `uintptr_t` 的最大值 ( $2^{16}$ -1 , or higher)。此外，建立了一個 hazard pointer 的 list (struct `list_hp_t `)。最後，以 atomic 的方式初始化 head 與 tail 指標，以及 head node 與 tail node 之間的連結。
我們進一步去檢查建立 `list_hp_t` 的函式 `list_hp_new()` 如下:
```c=
list_hp_t *list_hp_new(size_t max_hps, list_hp_deletefunc_t *deletefunc)
{
list_hp_t *hp = aligned_alloc(128, sizeof(*hp));
assert(hp);
if (max_hps == 0)
max_hps = HP_MAX_HPS;
*hp = (list_hp_t){.max_hps = max_hps, .deletefunc = deletefunc};
for (int i = 0; i < HP_MAX_THREADS; i++) {
hp->hp[i] = calloc(CLPAD * 2, sizeof(hp->hp[i][0]));
hp->rl[i * CLPAD] = calloc(1, sizeof(*hp->rl[0]));
for (int j = 0; j < hp->max_hps; j++)
atomic_init(&hp->hp[i][j], 0);
hp->rl[i * CLPAD]->list = calloc(HP_MAX_RETIRED, sizeof(uintptr_t));
}
return hp;
}
```
程式初始化了一個對齊128的 `list_hp_t` ，而 `list_hp_t` 的結構如下:
```c=
struct list_hp {
int max_hps;
alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];
alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];
list_hp_deletefunc_t *deletefunc;
};
```
在這個例子，`max_hps` 會被設成3，而指標 `deletefunc` 指向 `__list_node_delete()` ，一個釋放節點的函式。
此外，此結構中包含了一個二維的指標陣列 `hp`，即 Hazard pointer(s) 。以及一個二維的指標陣列 `rl`，即 Retire list 。
其中，指標陣列 `hp` 的第二個維度是最大的 thread 數，也就是說， 這裡分配給每個 thread 一串 Hazard pointers。
**pthread 的建立**
主程式中 [`pthread_create`](https://man7.org/linux/man-pages/man3/pthread_create.3.html) 函式創造 pthread ，並將指標 `list` 作為引數傳入`delete_thread()` 「或」`insert_thread()` 起始常式 (start routine)。注意到這個起始常式是由 i 值的奇偶決定的。當 i 是奇數，起始常式是 `delete_thread()` 否則是 `insert_thread()` 。
```c=
pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread, list);
```
這兩個 start routine 分別呼叫了 `list_insert()` 及 `list_delete()` 對 list 進行128個節點的插入以及刪除。2個函式都需要2個引數，一個是指標 `list` ，另一個是 key 值，程式碼如下:
```c=
static void *insert_thread(void *arg)
{
list_t *list = (list_t *) arg;
for (size_t i = 0; i < N_ELEMENTS; i++)
(void) list_insert(list, (uintptr_t) &elements[tid()][i]);
return NULL;
}
static void *delete_thread(void *arg)
{
list_t *list = (list_t *) arg;
for (size_t i = 0; i < N_ELEMENTS; i++)
(void) list_delete(list, (uintptr_t) &elements[tid()][i]);
return NULL;
}
```
注意到插入/刪除的節點以 `(uintptr_t) &elements[tid()][i]` 作為 key 值。 `tid()` 返回值作為 `element` 這個靜態二維陣列的索引值。 `tid` 相關程式碼如下:
```c=
#define TID_UNKNOWN -1
static thread_local int tid_v = TID_UNKNOWN;
static atomic_int_fast32_t tid_v_base = ATOMIC_VAR_INIT(0);
static inline int tid(void)
{
if (tid_v == TID_UNKNOWN) {
tid_v = atomic_fetch_add(&tid_v_base, 1);
assert(tid_v < HP_MAX_THREADS);
}
return tid_v;
}
```
整數型態的 `tid_v` 變數被 `static thread_local` keyword 所修飾，代表 `tid_v` 只有在各自的 thread 中看的到，他的生命週期侷限在 thread 的出生到死亡之間。且因為是靜態變數，只會初始化一次。
`tid()` 被呼叫時，如果 `tid_v` 仍然是初值，就把它改成 `tid_v_base` 加一，這表示每一個 thread 只會對 `tid_v_base` 加一並指派給 `tid_v` 。
總而言之，當我們創造了64個並行的 pthread ， pthread 會由插入/刪除節點的 start routine 開始執行。接著，每個 thread 呼叫 `tid()` 對 `tid_v_base` 靜態變數以 atomic 的方式加一，每個 thread 只會執行一次加一。其後， `tid_v_base` 的值會被回傳，作為 `element` 指標陣列的索引值。 `element` 被 dereferenced 後的位址傳入 `list_delete()` 及 `list_delete()` 作為 key 值。
**list 節點的插入/刪除**
<<[Lock-Free Data Structures](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B2561FF75B93F8C70CC44DF6079CB81B?doi=10.1.1.98.3363&rep=rep1&type=pdf)>> 文中第5章 "Garbage Collector, Where Are Thou?" 提到了 lock-free 的基本概念。演算法對於 Map (指的是共享資源) 的 lookup function 不實作 lock，而對 Map 的 update function 實作 CAS operation ，如此以確保 Map 的更新是 atomic 的。因此，當我們要刪去舊的 Map 時，需要有一個 garbage collector 來檢查舊的 Map 有沒有正在被其他 thread lookup。只有確保沒人 lookup 時，我們才能刪除舊 Map 。
<<[Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)>> 文中則提到 Hazard pointer 結構的實作方式，這裡整理了一些重點:
* 使用 Hazard pointer 結構的前提是 Write-Rarely-Read-Many
* Hazard pointer 結構能滿足 wait-free
* 每個 reader thread 擁有一個 Hazard pointer 。當 Hazard pointer 指向一個 Map，代表該 Map 可能有 thread 正在讀取，可以 remove 它，但不能 delete 它
* 每個 thread 有自己的 private list 叫做 retire list。這個 retire list 存放了被取代的 Map
* Retire list 中被取代 Map 累積到一定數量時， thread 會去檢查 (scan) 這些 Map 有沒有被所有 thread 的 Hazard pointer 指向。若沒有，才可以刪除
回到程式實作，因為 thread 在共享的 list (論文中指的 Map) 上新增或刪除節點，都是 update operaion ，故都要先對 Hazard pointer 進行 scan 。以下是 `list_insert()` 程式碼:
```c=
bool list_insert(list_t *list, list_key_t key)
{
list_node_t *curr = NULL, *next = NULL;
atomic_uintptr_t *prev = NULL;
list_node_t *node = list_node_new(key);
while (true) {
if (__list_find(list, &key, &prev, &curr, &next)) {
list_node_destroy(node);
list_hp_clear(list->hp);
return false;
}
atomic_store_explicit(&node->next, (uintptr_t) curr,
memory_order_relaxed);
uintptr_t tmp = get_unmarked(curr);
if (atomic_compare_exchange_strong(prev, &tmp, (uintptr_t) node)) {
list_hp_clear(list->hp);
return true;
}
}
}
```
我們可以發現 `__list_find()` 相當於上述對 retire list 執行 scan 的動作，一旦發現要插入的節點被某個 thread 的 Hazard pointer 指向，則將插入的節點刪除並返回。否則，將節點加入 list 中。
**2. 指出改進空間並著手實作**
先來看一下 list.c 的執行時間:
```
time ./list
inserts = 4098, deletes = 4098
real 0m28.477s
user 0m28.316s
sys 0m0.060s
```
總執行時間約為28秒，主要由這個使用者程序的使用的 CPU 時間佔據。
觀察 `__list_find()` 函式中的片段如下，我們可以發現搜尋是依 linked list 的順序往下找的。雖然 hazard pointer 的數量是固定的，但是在多層 loop 下執行還是相當耗時。
故我打算參考 <<[Lock-Free Data Structures](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B2561FF75B93F8C70CC44DF6079CB81B?doi=10.1.1.98.3363&rep=rep1&type=pdf)>> 文中第2章來實作 hashtable ，將 hazard pointer 結構化，以降低搜尋的 overhead。
```c=
try_again:
prev = &list->head;
curr = (list_node_t *) atomic_load(prev);
(void) list_hp_protect_ptr(list->hp, HP_CURR, (uintptr_t) curr);
if (atomic_load(prev) != get_unmarked(curr))
goto try_again;
while (true) {
if (!get_unmarked_node(curr))
return false;
next = (list_node_t *) atomic_load(&get_unmarked_node(curr)->next);
(void) list_hp_protect_ptr(list->hp, HP_NEXT, get_unmarked(next));
if (atomic_load(&get_unmarked_node(curr)->next) != (uintptr_t) next)
break;
if (get_unmarked(next) == atomic_load((atomic_uintptr_t *) &list->tail))
break;
if (atomic_load(prev) != get_unmarked(curr))
goto try_again;
if (get_unmarked_node(next) == next) {
if (!(get_unmarked_node(curr)->key < *key)) {
*par_curr = curr;
*par_prev = prev;
*par_next = next;
return get_unmarked_node(curr)->key == *key;
}
prev = &get_unmarked_node(curr)->next;
(void) list_hp_protect_release(list->hp, HP_PREV,
get_unmarked(curr));
} else {
uintptr_t tmp = get_unmarked(curr);
if (!atomic_compare_exchange_strong(prev, &tmp, get_unmarked(next)))
goto try_again;
list_hp_retire(list->hp, get_unmarked(curr));
}
curr = next;
(void) list_hp_protect_release(list->hp, HP_CURR, get_unmarked(next));
}
*par_curr = curr;
*par_prev = prev;
*par_next = next;
```
**3. 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？**
Sign in with Wallet
Connect another wallet