# 2021q3 Homework2 (hp)
contributed by < `ekangmonyet` >
###### tags: `linux2021`
## 分析測試範例實作
> [main.c](https://github.com/sysprog21/concurrent-programs/blob/master/hp_list/main.c)
一直覺得測試方法怪怪的，似乎 delete 的 key 和 insert 的 key 完全沒有重疊，因為 `&elements[tid()][i]` 的 `tid()` 都不會一樣。首先移除最後的 cleanup ，這樣 cleanup 期間的 delete 就不會被算進去：
```c=
/*
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);
*/
```
確認 delete count 變成 0 了，證實 `delete_thread` 完全沒在做事。接著將其修改成：
```c=
for (size_t i = 0; i < N_ELEMENTS; i++)
deleted += list_delete(list, (uintptr_t) &elements[tid()-1][i]);
```
因為執行緒 spawn 的順序是交替的，因此 `tid()-1` 便能得到上一個 `insert_thread` 的 `tid` ，形成一邊 insert 一邊 delete 的並行狀況。但執行結果卻依然不符合預期：
```
inserts = 4098, deletes = 3997
```
因為 delete count 的數值變化不定，起初覺得是 race condition 的徵兆，於是給 `delete_thread` 包上一個簡單的迴圈：
```c=
int deleted = 0;
for (int j = 0; j < 100; j++) {
for (size_t i = 0; i < N_ELEMENTS; i++)
deleted += list_delete(list, (uintptr_t) &elements[tid()-1][i]);
if (deleted == N_ELEMENTS) {
printf("\t\t break at %d\n", j);
break;
}
}
```
雖然 delete count 有增加，但結果依然不如預期。突然想到還有已經 "delete" 但未被釋放的可能性，於是在最後把 hazard pointers 都釋放：
```c
list_hp_destory(list->hp)
```
便能穩定得到：
```
inserts = 4098, deletes = 4096
```
（缺少的兩個 node 是沒被指定刪除的頭尾 sentinel node ，為預期行為）
在第六列加入的 `printf` 可觀察到大部分執行緒在第一次便能順利 delete 完，而最大值暫時仍未超過 $50$：
```=
break at 0
break at 0
break at 0
break at 0
break at 1
break at 0
break at 0
break at 1
break at 0
break at 0
break at 0
break at 0
break at 1
break at 6
break at 0
break at 0
break at 0
break at 1
break at 0
break at 0
break at 0
break at 0
break at 0
break at 0
break at 1
break at 2
break at 0
break at 0
break at 0
break at 0
break at 0
break at 0
```
接下來便是時候利用新知識重新回顧之前解構的過程了…
## 解構 (before 2021-08-12)
這是個 strictly-ordered list 的實作，利用 `__list_find()` 來找到下一個 insert 的位置，並可以 delete 任意 key 。機會難得，先把整個程式解構（若程式太難的情況就先去啃[德希達的解構主義](https://zh.wikipedia.org/wiki/%E8%A7%A3%E6%A7%8B%E4%B8%BB%E7%BE%A9)就會發現 Hazard Pointer 其實沒那麼難了）：[github](https://github.com/ekangmonyet/concurrency-lab)
### Single-threaded insert-only implementation
> [list0.c](https://github.com/ekangmonyet/concurrency-lab/blob/master/list0.c)
要設計並行程式，就要先了解並行時會出現的問題。首先實作一個只能 insert 的單執行緒版本。這裡除了 `tid()` 的函式以外都沒有使用任何 atomic operation 。一些對 list 本身的改進也會加在這裡，並用一個簡單的測試來確任執行成功。這版本在 `N_THREADS` $=1$ 的時候可以順利運行，當 `N_THREADS` $>1$ 時 TSAN 便會開時報錯，但當 `N_THREADS` 值不高時還是可以順利執行完成，主要因為現代 CPU 實在太快了，可以發生 race 的窗口非常小，甚至在下一個 thread 開時執行前就已經完成了。
### Lock-free insertion with CAS
> [list2.c](https://github.com/ekangmonyet/concurrency-lab/blob/master/list2.c)
若不需要並行的 deletion ，就沒有記憶體回收的問題。這裡利用 CAS 實作一個 lock-free 的 insertion 。（雖然通過 TSAN 和 `N_THREADS` $=128$ 的測試，但對於正確性還是有所保留…目前還在尋找可更好模擬 race condition 的方法，歡迎告知）
#### 狀況一：多個執行緒同時 insert
```c=
while (true) {
if (__list_find(list, &key, &prev, &curr, &next)) {
return false;
}
atomic_store_explicit(&new->next, (uintptr_t) curr,
memory_order_relaxed);
uintptr_t tmp = (uintptr_t) curr;
if (atomic_compare_exchange_strong(prev, &tmp, (uintptr_t) new)) {
return true;
}
}
```
利用 CAS ，若 `&prev_node->next` 的指標不再是 curr ，表示另一個執行緒在這之間搶先 insert 了，那就重新 find 過。
#### 狀況二：在 find 的過程被 insert
```c=
while (true) {
next = (list_node_t *) atomic_load(&curr->next);
if (!(curr->key < *key)) {
*par_curr = curr;
*par_prev = prev;
*par_next = next;
return (curr->key == *key);
}
prev = &curr->next;
curr = next;
if ((uintptr_t) next == atomic_load(&list->tail))
break;
}
```
:::warning
其實似乎 `curr->next` 可以在 `atomic_load` 之後被換掉，但實際測試時都無法模擬出這狀況…
但在原本的 list.c 可看到這之間加了很多測試，比如確保 next 依然等於 curr->next 等等。
:::
### Lock-free deletion with CAS without resource reclamation
> [list5.c](https://github.com/ekangmonyet/concurrency-lab/blob/master/list5.c)
實作 deletion 時，最複雜的情況就是一個執行緒取得了一個有效的指標後被另一個執行緒 free 掉，產生 Use After Free 的問題。若不釋放和回收記憶體，理論上實作會變得簡單很多。如同預期，若在 delete 後加入 `free(curr)` 便會導致 UAF 的發生。
測試方式：
```c=
static void *delete_thread(void *arg)
{
list_t *list = (list_t *) arg;
int deleted = 0;
for (int i = 0; i < 100000; i++) {
for (size_t i = 0; i < N_ELEMENTS; i++) {
deleted += list_delete(list, (uintptr_t) &elements[tid()-1][i]);
}
if (deleted == N_ELEMENTS)
break;
}
return NULL;
}
```
==TODO:==
- 若計算 delete 的總量會發現小於 insert ，但 list 卻是空的…？？？
- 用相同的測試法發現原本的 `list.c` 也有類似狀況，但 list 不是空的
- ==修正使得 `inserts == deletes`==
- 改進並行刪除的測試
- ~~實踐 pointer marking~~
### ==Manual Simulation of Concurrent Operations==
> [sim1.c](https://github.com/ekangmonyet/concurrency-lab/blob/master/sim1.c)
因為並行產生的 contention 對我來說太難想像，又找不到什麼能做到精準模擬出 contention 的方式（也許以後能利用特製的 intepreter 或是 userspace thread 來控制？），於是手動把函式拆解成幾個部份然後手動執行，模擬出不同執行緒同時呼叫函式的狀況。這樣也能更清楚各情況下 `__list_find()` 應該如何反應。
```graphviz
digraph {
rankdir=LR
200 [color=red]
400 [color=red]
0->100
100->200
200->300
300->400
400->500
500->TAIL
}
```
```c=
state_t *t1 = _list_delete_step1(list, 200, "t1");
_list_delete_step2(t1);
state_t *t2 = _list_delete_step1(list, 400, "t2");
_list_delete_step2(t2);
_list_delete_step3(t1);
_list_delete_step3(t2);
```
利用 `sim1` 模擬發現同時刪除 $200$ 和 $400$ 應該要成功， 因此 `is_marked(curr->next)` 的測試應該發生在 `return curr->key == *key` 前，這樣被標記的節點就依然能夠被 traverse 。根據 **[A Pragmatic Implementation of Non-Blocking List](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)** ：
> Marked references are distinct from normal references but still allow the referred-to node to be determined.
初步改寫 `__list_find()` ==（未在實際 list 上測試！）==：
```c=
if (!(get_unmarked_node(curr)->key < *key)) {
if (is_marked(atomic_load(&curr->next))) {
goto try_again;
}
*par_curr = curr;
*par_prev = prev;
*par_next = next;
return get_unmarked_node(curr)->key == *key;
}
```
利用這方式能簡單描述需要模擬的狀況並實作，如：
```c
/*
* CASE 1: Distinct delete (200, 400)
* Expected: both can be deleted concurrently
*
* CASE 2: Consecutive delete (200, 300)
* Expected: t2 should retry find until 200 is deleted
*/
```
模擬器的部份，`list_find()` 加入 `weak` 參數，開啟後若需要 try again 時便會直接回傳 false 並把 `weak` 設成 false 表示需要 retry。
```c=
#define STOP_IF_WEAK() {if(weak) { *weak=false; return false; }}
// ...
if (is_marked(atomic_load(&curr->next))) {
STOP_IF_WEAK();
goto try_again;
}
// ...
```
利用 state 結構來記錄執行緒的區域變數：
```c=
typedef struct {
const char *t;
list_t *list;
atomic_uintptr_t *prev;
list_node_t *curr;
list_node_t *next;
uintptr_t key;
uintptr_t tmp;
int step;
} state_t;
static void _list_delete_step2(state_t *state)
{
if (!(state->step == 1))
return;
state->tmp = get_unmarked(state->next);
atomic_compare_exchange_strong(&state->curr->next, &state->tmp,
get_marked(state->next));
state->step = 2;
}
```
TODO:
- 把各情況模擬出來並改進 `__list_find()` 的行為使其符合 **Harris (draconic/textbook)** [1] 的演算法
- 引進 TU Wien 大學 [1] 的改進方案
- 加入 benchmarking 比較
[1] - https://github.com/parlab-tuwien/lockfree-linked-list
### Lock-free deletion with Hazard Pointer
終於回到正題，探討利用 Hazard Pointer 來管理應該被釋放的資源，並在確認安全的情況下釋放他們。
# ==work in progress==
## 問題
- 應該要insert 在 0 ( `list->head` ) 和 `UINTPTR_MAX` ( `list->tail` ) 之間
- 解：把 `if (next == list->tail)` 放到 `while()` 最尾端
- `delete_thread` 其實並不會刪除任何 key
- 解：因為執行緒生成的順序，可以把 `delete_thread` 改成刪除 `&elements[tid()-1][i]`
- 若只依賴 `delete_thread` ， delete 的總量會小於 insert
- 推測：仍在 retire list 裡面
- 解釋上述程式碼運作原理
- 指出改進空間並著手實作
- 對比 rcu_list，解釋同為 lock-free 演算法，跟上述 Hazard pointer 手法有何異同？能否指出 rcu_list 實作缺陷並改進？
## 回顧
:::danger
RRR = `hp->deletefunc(ptr)`
NNN = `128`
FFF = `true`
DDD = `list_hp_retire(list->hp, tmp)`
:::
其實測驗前五分鐘長這樣：
:::danger
RRR = `free(ptr)`
NNN = `128`
FFF = ` `
DDD = `free(tmp)`
:::
~~對於能在半小時內找出應該用`hp->deletefunc()`和`list_hp_retire()`其實已經很滿意…~~
### RRR
對 `hp->deletefunc()` 的實際使用不夠了解，但方向算對的
### NNN
並不知道原來 NNN 是要算出 4098 …
解：$($`N_THREADS` $\div 2) \times$ `N_ELEMENTS` $+2$
### FFF
其實是 strictly ordered list ，當找到第一個不小於 key 的節點，測試是否等於 key 便能知道整個 list 是否已經存在 key 。
### DDD
* 這裡的`curr`會改變（`tmp`會落後）
* 總會有人刪，如果 CAS 失敗就是已經被刪除了 成功的就負責呼叫 `list_hp_retire`
## NOTE
- https://github.com/parlab-tuwien/lockfree-linked-list
Sign in with Wallet
Connect another wallet