# 2022q1 Homework5 (quiz5)
contributed by < `Korin777` >
## 測驗二
### 程式研讀
#### 程式運作
* reader 會透過 `load 函式` 來讀 `shared_config` 並透過 `list_insert_or_append 函式` 將正在使用的 config 插入 `config_dom->pointer`(即為 hazard pointer) ， reader 印出 config 後在透過 `drop 函式` 將 config 從 hazard pointer 移除
* writer 透過 `swap 函式` 更新 `shared_config` ， 並將舊的 config 透過 `cleanup_ptr 函式` 釋放
* 只有一個 writer 時 ， updating config 到 updated config 中間 ， read config 會印出兩種不同的 config ， 一個是舊的一個新的 config ， 等到 updated config 後 read config 所印出的 config 才會一致
##### load
```c
uintptr_t load(domain_t *dom, const uintptr_t *prot_ptr)
{
const uintptr_t nullptr = 0;
while (1) {
// reader 讀 shared_config 並將它插入 config_dom->pointers(hazard pointer)
uintptr_t val = atomic_load(prot_ptr);
hp_t *node = list_insert_or_append(&dom->pointers, val);
if (!node)
return 0;
/* 如果 prot_ptr != val 表示 writer 已寫入新的 config ,
* 如果 reader 讀到舊的 val 且尚未插入 hazard pointer ,
* writer 就去寫入新的 value 並釋放舊的 val 就會發生錯誤 ,
* 因此要避免上述狀況
*/
if (atomic_load(prot_ptr) == val)
return val;
// 重讀 shared_config 前先把剛插入的 hazard pointer 移除
uintptr_t tmp = val;
if (!atomic_cas(&node->ptr, &tmp, &nullptr))
list_remove(&dom->pointers, val);
}
}
```
##### list_remove
```c
bool list_remove(hp_t **head, uintptr_t ptr)
{
hp_t *node;
const uintptr_t nullptr = 0;
LIST_ITER (head, node) {
uintptr_t expected = atomic_load(&node->ptr);
if (expected == ptr && atomic_cas(&node->ptr, &expected, &nullptr))
return true;
}
return false;
}
```
* `list_remove` 不會將 node 從 link list 移除 ， 而是將該 node 變為空的 node 讓其他人可以使用
##### drop
```c
void drop(domain_t *dom, uintptr_t safe_val)
{
if (!list_remove(&dom->pointers, safe_val))
__builtin_unreachable();
}
```
* `__builtin_unreachable` 能讓 compiler 改變 branch 的順序(e.g. if 先往外面執行) 及消除 dead code (e.g. if 內的 `ret`) ， 這裡的 `list_remove 函式` 也不該 return false (因為 hazard pointer 的移出不該失敗) ， 若走到 `__builtin_unreachable()` 也能讓我們得知在 `drop 函式` 發生錯誤了
##### swap
```c
void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags)
{
// 更新新的 shared_config
const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
cleanup_ptr(dom, old_obj, flags);
}
```
##### cleanup_ptr
```c
static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags)
{
if (!list_contains(&dom->pointers, ptr)) { /* deallocate straight away */
dom->deallocator((void *) ptr);
} else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
list_insert_or_append(&dom->retired, ptr);
} else { /* Spin until all readers are done, then deallocate */
while (list_contains(&dom->pointers, ptr))
;
dom->deallocator((void *) ptr);
}
}
```
* 若 `flag` 為 0 則 writer 一直等到 hazard pointer 沒此 config 在釋放它
* 若 `flag` 為 1 則 writer 將此 config 插入 `config_dom->retired`(即 retired list , 之後在透過 `cleanup 函式`來釋放) ， 因此 writer 不須等待 reader 繼續更新 config
### 改進
#### 發現
雖然程式有實做 retire list ， 但 `writer_thread` 傳入 `cleanup_ptr 函式` 的 flags 為 0 ， 因此不會將要移除的 config 插入 retire list 而會用 busy waiting 的方式來釋放舊的 config
#### 實做
```c
static void *writer_thread(void *arg)
{
(void) arg;
hp_t *local_retired = NULL, *tmp;
for (int i = 0; i < N_ITERS / 2; ++i) {
cleanup(config_dom,1, (uintptr_t) &local_retired);
config_t *new_config = create_config();
new_config->v1 = rand();
new_config->v2 = rand();
new_config->v3 = rand();
// 將 new_config 插入 hazard pointer
list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
print_config("updating config", new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
1, (uintptr_t) &local_retired);
print_config("updated config ", new_config);
// 將 new_config 移出 hazard pointer
drop(config_dom, (uintptr_t) new_config);
}
while(local_retired)
cleanup(config_dom,1, (uintptr_t) &local_retired);
return NULL;
}
```
* 原本的 retired list 是 global 的 ， 所有 writer 都能存取到 ， 但這裡我將 retired list 改為 local 的 。 每個 writer 需要將自己替換掉的 `shared_config` 加入自己的 `local_retired` 並負責釋放此 config
* writer 結束前必須確保自己負責的 config 都已經釋放了
* retired list 改為 local 的好處有讓對 retired list 操作不再需要用 atomic operation ; 而每個 config 被唯一一個 writer 保存 ， 因此 traverse retired list 的路徑也可以減少
```c
void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags, uintptr_t local_retire)
{
// 更新新的 shared_config
const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
cleanup_ptr(dom, old_obj, flags, local_retire);
}
static void cleanup_ptr(domain_t *dom, uintptr_t ptr, int flags, uintptr_t local_retire)
{
if (!list_contains(&dom->pointers, ptr)) { /* deallocate straight away */
dom->deallocator((void *) ptr);
} else if (flags & DEFER_DEALLOC) { /* Defer deallocation for later */
independent_list_append(local_retire, ptr);
} else { /* Spin until all readers are done, then deallocate */
while (list_contains(&dom->pointers, ptr))
;
dom->deallocator((void *) ptr);
}
}
void cleanup(domain_t *dom, int flags, uintptr_t local_retired)
{
hp_t *node;
for(node = *(hp_t **)local_retired; node;) {
uintptr_t ptr = node->ptr;
hp_t *retire_node, *tmp;
tmp = node;
node = node->next;
if (!ptr)
continue;
if (!list_contains(&dom->pointers, ptr))
if(independent_list_remove(local_retired, ptr))
dom->deallocator((void *) ptr);
}
}
```
* 傳入 writer 的 local retired list 及更換操作 retired list 的函式 `independent_list_remove`、`independent_list_append`
```c
#define INDEPENDNET_LIST_ITER(head, node) \
for (node = *head; node; node = node->next)
static hp_t *independent_list_append(hp_t **head, uintptr_t ptr)
{
hp_t *new = calloc(1, sizeof(hp_t));
if (!new)
return NULL;
new->ptr = ptr;
new->next = *head;
*head = new;
return new;
}
bool independent_list_remove(hp_t **head, uintptr_t ptr)
{
hp_t *node, *prev = NULL;
const uintptr_t nullptr = 0;
INDEPENDNET_LIST_ITER (head, node) {
if (node->ptr == ptr) {
if(prev)
prev->next = node->next;
else
*head = node->next;
free(node);
return true;
}
prev = node;
}
return false;
}
```
* 因為 retired list 改為 local 的 ， 在插入及移除可以不用 atomic operation
#### 比較 retired list 與 busy waiting
N_ITERS 固定為 10000
##### writer 固定為 4 個 ， 增加 reader 數量
* 使用 busy wating 和 retired list 的執行時間差異不大
##### reader 固定為 4 個 ， 增加 writer 數量
* 當 writer 為 8 個時 busy waiting 的時間大幅增加 (註：有時當 writer 為 8 個時 busy waiting 的時間還是可以跟 retired list 差不多)
* 執行程式並透過 perf 來觀察程式熱點
* 使用 retired list 時 ， 在各函式所佔的百分比大致相差不多 ， 佔比較多的有 `list_insert_or_append`、`list_remove`、`syscall_exit_to_user_mode`、`__random` ， 其中 `random` 函式似乎會使用到 futex
* 使用 busy waiting 時 ， 可以發現在 `list_contains` 佔了 90% 以上 ， 而 `cleanup_ptr` 則佔了 5％ 左右 。 會卡在這裡的原因就是要等 reader 及其他 writer drop 掉插入 hardzrad pointer 的 config ， 因此 writer 一直透過 `list_contains` 來查看 hardzrad pointer
* retired list 和 busy wating 還有一個不同的地方是 ， retired list 的 print config 和 updating/updated config 的交錯會比較頻繁 ， 因為 writer 不用等 reader
### 開啟多個 writer 無法通過 ThreadSanitizer
```c
static void *writer_thread(void *arg)
{
(void) arg;
for (int i = 0; i < N_ITERS / 2; ++i) {
config_t *new_config = create_config();
new_config->v1 = rand();
new_config->v2 = rand();
new_config->v3 = rand();
// 將 new_config 插入 hazard pointer
list_insert_or_append(&config_dom->pointers, (uintptr_t) new_config);
print_config("updating config", new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
0);
print_config("updated config ", new_config);
// 將 new_config 移出 hazard pointer
drop(config_dom, (uintptr_t) new_config);
}
return NULL;
}
```
#### 問題
* 原本只有一個 writer ， `new_config` 並不會被動到 ， 而當開啟多個 writer `new_config` 就有可能受到其他 writer 的操作
* e.g.
1. writer1 在 `print_config("updated config ", new_config)` 前停下換 writer2 執行
2. writer2 經過 `swap 函式` 換掉 `shared_config` 並取得 `old_obj`(即 writer1 的 `new_config`) 在透過 `cleanup_ptr 函式` 查看是否能釋放它 ， 這時要是剛好沒有 reader 在使用它 ， writer2 就能將它釋放 ， writer2 停下換 writer1 執行
3. writer1 此時要印出 `new_config` 就會發生問題
#### 解決方法
* 在進入 `swap 函式` 前 ， 先將 `new_config` 插入 hazard pointer 讓其他 writer 必須等待而無法將它釋放 ， 等 writer 不用使用到 `new_config` 後在透過 `drop 函式` 將它從 hazard pointer 移除 ， 這時其他 writer 便能將它釋放
### 比較 RCU 和 hazard pointer (HP)
#### RCU
* reader
* 透過 `rcu_read_lock`、`rcu_read_unlock` 所建立的 critical section 來保護資料
* `rcu_read_lock` : 通知 reclaimer 自己進入 crtical section
* rcu_read_unlock : 通知 reclaimer 自己離開 crtical section
* updater
* removal
* 透過 spinlock 確保同時只有一個 writer 在更新資料
* writer 先複製一份舊的資料並更新它 ， 接著用此替換掉舊的資料
* reclamation
* 透過 `synchronize_rcu`、`call_rcu` 來釋放資料
* `synchronize_rcu` : block updater 直到 pre-existing RCU
read-side critical sections 都完成
* `call_rcu` : updater 不會被 block ， pre-existing RCU
read-side 都完成才會執行註冊的 callback function
#### RCU 和 HP 的差異
1. 在 reader 方面 RCU 不會用到 lock 及 atomic operation ; HP 則需要在使用到 shared data 及 hazard pointer 時使用 atomic operation ， 若拿到的 shared data 為舊的就要重新讀取。
2. 在 writer 方面 ， RCU 透過 spinlock 來確保同時只有一個 writer 在更新 shared data ; HP 則是透過 atomic operation
3. RCU 透過 crical section 來保護 reader 正在使用的 shared data ; HP 則透過 hazard pointer 來保護
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz5)
:::warning
對照研讀 [hp_list](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list) 程式碼，這是測驗題後續改進的實作
:notes: jserv
:::
### 研讀 [hp_list](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list)
#### 程式運作
* thread 間共享一個 key 值遞增且唯一的 link list
* 每個 thread 有自己的 hazard pointer 及 retired list
* insert thread 負責新增節點 ; delete thread 負責移除節點(logically delete) 並嘗試將它 physically delete 。 兩者皆會透過 `__list_find 函式` 嘗試將經過的 logically delete 節點 physically delete
* logically delete: 將欲移除 node 的 next 所指向的地址的最後一個 bit 改為 1 (因記憶體對齊的緣故 , 原本記憶體位置的最後一個 bit 為 0)
* physically delete: 將 node 從 link list 上移除(尚未釋放) 並加到 retired list
* [並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree#Concurrent-Linked-List) 提到 concurrent linked list 會發生的問題
```c
// 先 insert 且做到一半:
node_10_next = atomic_load(&(node_10->next))
node_20->next = node_10_next
// 換 delete:
head_next = atomic_load(&(H->next))
CAS(&(H->next), head_next, head->next->next)
// 回到 insert:
CAS(&(node_10->next), node_10_next, node_20) // error
```
原本的 delete 過程中並不會更動到 node_10->next , 所以 insert 如期執行而產生錯誤的結果 ; 而 logically delete 就是透過改變 node_10->next 來避免上述問題
#### __list_find
```c
static bool __list_find(list_t *list,
list_key_t *key,
atomic_uintptr_t **par_prev,
list_node_t **par_curr,
list_node_t **par_next)
{
atomic_uintptr_t *prev = NULL;
list_node_t *curr = NULL, *next = NULL;
try_again:
prev = &list->head;
curr = (list_node_t *) ATOMIC_LOAD(prev);
(void) list_hp_protect_ptr(list->hp, HP_CURR, (uintptr_t) curr);
// 確保沒有其他人新增 node 在curr 前或插入 hp 前 curr 被其他人釋放
if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
TRACE(retry);
goto try_again;
}
while (true) {
if (is_marked(curr))
TRACE(contains);
next = (list_node_t *) ATOMIC_LOAD(&get_unmarked_node(curr)->next);
(void) list_hp_protect_ptr(list->hp, HP_NEXT, get_unmarked(next));
// 確保沒有其他人新增 node 在 next 前或插入 hp 前 next 被其他人釋放
if (ATOMIC_LOAD(&get_unmarked_node(curr)->next) != (uintptr_t) next) {
TRACE(retry);
goto try_again;
}
// 確保沒有其他人新增 node 在 curr 正前面
if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
TRACE(retry);
goto try_again;
}
// curr 沒被 logically delete
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 { // 查看是否能 physically delete , 將 curr 加到 retired list
uintptr_t tmp = get_unmarked(curr);
// 確保沒人新增 node 在 curr 正前面及 curr 還沒被 physically delete
if (!CAS(prev, &tmp, get_unmarked(next))) {
TRACE(retry);
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));
TRACE(traversal);
}
}
```
* par_curr: 持有的 key 大於等於所要尋找的 key 的 node
* par_prev: node->next 為 par_curr 的 pointer 地址
* par_next: par_curr->next 的值
* return value: 若 key 存在回傳 true , 反之回傳 false
* 會將 par_curr 及其前後一個 node 插入 hp , 這 3 個 node 就是 thread 正在使用的 data , 用完後透過 list_hp_clear 從 hazard pointer 移除
#### list_insert
```c
bool list_insert(list_t *list, list_key_t key)
{
// curr 為新增 node 的 next , *prev 為
list_node_t *curr = NULL, *next = NULL;
atomic_uintptr_t *prev = NULL;
list_node_t *node = list_node_new(key);
while (true) {
// key 已經存在了
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);
/* *prev 應該與 get_unmarked(curr) 相等 , 不是的話就
* 表示有其他 thread 新增 node 在 curr 正前方或前一個
* node 已經 physically delete , 則必須重來
*/
if (CAS(prev, &tmp, (uintptr_t) node)) {
list_hp_clear(list->hp);
return true;
}
TRACE(ins);
}
}
```
#### list_delete
```c
bool list_delete(list_t *list, list_key_t key)
{
list_node_t *curr, *next;
atomic_uintptr_t *prev;
while (true) {
// key 不存在
if (!__list_find(list, &key, &prev, &curr, &next)) {
list_hp_clear(list->hp);
return false;
}
uintptr_t tmp = get_unmarked(next);
/* 將 curr logically delete , curr->next 應該與 get_unmarked(next)
* 相等 , 不是的話就表示有其他 thread 新增 node 在 curr 正後方或 curr 已經被 logically delete , 則必須重來
*/
if (!CAS(&curr->next, &tmp, get_marked(next))) {
TRACE(del);
continue;
}
// 若沒人新增 node 在 curr 正前面且 curr 還沒被 physically delete , 將 curr physically delete
tmp = get_unmarked(curr);
if (CAS(prev, &tmp, get_unmarked(next))) {
list_hp_clear(list->hp);
list_hp_retire(list->hp, get_unmarked(curr));
} else {
list_hp_clear(list->hp);
}
return true;
}
}
```
:::warning
TODO: 討論上述實作是否能避免 [ABA Problem](https://en.wikipedia.org/wiki/ABA_problem)?
:notes: jserv
:::
### 討論 ABA 問題
* 根據 [ABA Problem](https://en.wikipedia.org/wiki/ABA_problem) 所舉的例子
* 假設 link list 一開始為 (head,0) -> (0x4,1) -> (0x8,2) -> (0xc,3) -> (tail,UINTPTR_MAX)
* (address,data)
thread1 先執行
```c
// list_delete 1
prev = &head->next;
curr = 0x4;
next = 0x8;
tmp = 0x8;
```
thrad1 在執行 `CAS(&curr->next, &tmp, get_marked(next))` 前被 thread2 中斷
```c
// list_delete 1
{
prev = &head->next;
curr = 0x4;
next = 0x8;
tmp = 0x8;
// logically delete , marked 0x4->next
CAS(&curr->next, &tmp, get_marked(next))
// physically delete , head -> 0x8 -> 0xc -> tail
CAS(prev, &tmp, get_unmarked(next))
}
// list_delete 2
{
prev = &head->next;
curr = 0x8;
next = 0xc;
tmp = 0xc;
// logically delete , marked 0x8->next
CAS(&curr->next, &tmp, get_marked(next))
// physically delete , head -> 0xc -> tail
CAS(prev, &tmp, get_unmarked(next))
}
// list_insert 1 , 假設 new_node 地址剛好為 0x4
{
prev = &head->next;
curr = 0xc;
ATOMIC_STORE_EXPLICIT // new_node->next = 0xc
// head->next = 0x4 , head -> 0x4 -> 0xc -> tail
CAS(prev, &tmp, (uintptr_t) new_node)
}
```
回到 thread1 執行
```c
/* prev = &head->next;
* curr = 0x4;
* next = 0x8;
* tmp = 0x8;
* head -> 0x4 -> 0xc -> tail
*/
CAS(&curr->next, &tmp, get_marked(next))
tmp = curr;
// 可能會產生 ABA 問題
CAS(prev, &tmp, get_unmarked(next))
```
* 此時的 curr 為 thread2 插入的 , curr->next 為 0xc , 所以第一個 CAS 不會將 curr logically delete , 在這個狀況下會重新執行 list_delete
* 如果 thread2 不只新增了 0x4 還新增了 0x8 , 則 link list 為 `head -> 0x4 -> 0x8 -> 0xc -> tail` , 這時第一個 CAS 就可以將 curr logically delete 並執行第二個 CAS , 而第二個 CAS 也可以將 curr physically delete , 就會產生先執行的 delete 去移除後面 insert 近來的 node 的情況 。 不過實際上 thread1 會將 `head,0x4,0x8` 插入 harzard pointer 來延緩 physically delete , 因為記憶體還沒被釋放 , 所以 thread2 所新增的節點記憶體位置應該不會在 0x4 及 0x8 , 因此上述的情況應該也不會發生。
* 就上述情況 , 此實做能避免 wekipedia 所舉出的 ABA 問題
參考資料 ：
[What optimizations does __builtin_unreachable facilitate?](https://stackoverflow.com/questions/54764535/what-optimizations-does-builtin-unreachable-facilitate)
[What is RCU? -- "Read, Copy, Update"](https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt)
Sign in with Wallet
Connect another wallet