# 2021q3 Homework2 (hp)
contributed by < `fwfly` >
## hp 測試設計
建立 n 個 thread 去對一個 list 做 insert key
然後 n 個 thread 去同一個 list 做 delete key
這樣會同時對一個 list 做新增,刪除跟搜尋(find)而導致 race condition 的問題
最後再用 hp 的方式達到 lock-free 的解法
### Elements 的設計
程式用了 2 維 array 去產生 key.
這個 array 可以記錄給個 insert thread 產生的 key
在 delete 的時候， delete thread 也可以根據拿到的 tid 從 array 中找到 key
##### Bug - delete thread 可能沒有刪到任何的 key
在 main 裡面可以看到 thread 是輪流去產生 delete 跟 insert thread,
所以 delete 跟 insert thread 會有同樣的數目，理想上兩邊剛好可以抵消
```cpp
pthread_create(&thr[i], NULL, (i & 1) ? delete_thread : insert_thread,
list);
```
但是問題出在這邊
```cpp
// 這是 insert thread
(void) list_insert(list, (uintptr_t) &elements[tid()][i]);
// 這是 delete thread
(void) list_delete(list, (uintptr_t) &elements[tid()][i]);
// 這是 tid 的取得方式, 有新的 thread 就給一個 +1 的 tid
tid_v = atomic_fetch_add(&tid_v_base, 1);
```
從上面可以知道 key 是 elements 中每一個 cell 的 address
最後產生的 elements 會是下圖
```
// 這是 elements
tid i
insert 0 1,2,3.......max_elements
delete 1 1,2,3.......max_elements
insert 2 1,2,3.......max_elements
delete 3 1,2,3.......max_elements
insert 4 1,2,3.......max_elements
.....
```
可以看到 delete 跟 insert 是交錯的關係, 所以 delete 永遠不會刪到在 list 中的任何一個 key, 可以簡單地補上 printf 驗證
```cpp
bool list_delete(list_t *list, list_key_t key)
{
printf("LST_DEL%d: %ld\n", tid(), key);
list_node_t *curr, *next;
atomic_uintptr_t *prev;
while (true) {
if (!__list_find(list, &key, &prev, &curr, &next)) {
list_hp_clear(list->hp);
// 請不要把 printf 加在 list_hp_clear 前面, 不確定是否會影響到 hp 的運作
printf("LST_DEL%d: %ld ,res: False\n", tid(), key);
return false;
}
printf("LST_DEL%d: %ld ,res: True\n", tid(), key);
uintptr_t tmp = get_unmarked(next);
```
然後會發現程式都只會印出 False 直到最後一段把 list 全部清除時才會印到 True
這時候才會做到真正的刪除．
所以如果加上這段 printf, 會發現 True 全部集中在最後一段
```
LST_DEL1: 94799338001472 ,res: False
...
...
LST_DEL63: 94799338065928 ,res: False
LST_DEL63: 94799338065936 ,res: False
LST_DEL63: 94799338065944 ,res: False
LST_DEL63: 94799338065952 ,res: False
LST_DEL63: 94799338065960 ,res: False
LST_DEL63: 94799338065968 ,res: False
LST_DEL63: 94799338065976 ,res: False
Delete all
LST_DEL64: 94799338000448
LST_DEL64: 94799338000448 ,res: True
LST_DEL64: 94799338001472
LST_DEL64: 94799338001472 ,res: False
LST_DEL64: 94799338002496
LST_DEL64: 94799338002496 ,res: True
LST_DEL64: 94799338003520
LST_DEL64: 94799338003520 ,res: False
LST_DEL64: 94799338004544
LST_DEL64: 94799338004544 ,res: True
LST_DEL64: 94799338005568
LST_DEL64: 94799338005568 ,res: False
LST_DEL64: 94799338006592
```
#### patch
用兩個 tid_base 分別計算 insert thread 跟 delete thread
因為 elements 是用 idx 去找 key, 所以並不影響原本的程式．
[Patch 的程式碼](https://github.com/fwfly/concurrent-programs/commit/6262ca154a67126a4d968c1d0f75f343b300c145)
經過上面的 patch 後的程式，兩種 thread 確實產生了 race condition, 但是觸發了 ThreadSanitizer: data race 的 error.
```cpp
$ ./list
LST_DEL0: 93989954416704
LST_DEL0: 93989954416704 ,res: True
LST_DEL0: 93989954416712
LST_DEL0: 93989954416712 ,res: True
==================
WARNING: ThreadSanitizer: data race (pid=275662)
Write of size 8 at 0x7b4000010180 by thread T2:
#0 free ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:707 (libtsan.so.0+0x35f25)
#1 list_node_destroy /home/fwfly/project/concurrent-programs/hp_list/main.c:325 (list+0x21af)
#2 __list_node_delete /home/fwfly/project/concurrent-programs/hp_list/main.c:332 (list+0x2209)
#3 list_hp_retire /home/fwfly/project/concurrent-programs/hp_list/main.c:274 (list+0x1d39)
#4 list_delete /home/fwfly/project/concurrent-programs/hp_list/main.c:440 (list+0x269e)
#5 delete_thread /home/fwfly/project/concurrent-programs/hp_list/main.c:497 (list+0x27df)
Previous atomic read of size 8 at 0x7b4000010180 by thread T1:
#0 __tsan_atomic64_load ../../../../src/libsanitizer/tsan/tsan_interface_atomic.cpp:539 (libtsan.so.0+0x7ced7)
#1 __list_find /home/fwfly/project/concurrent-programs/hp_list/main.c:365 (list+0x1fb4)
#2 list_insert /home/fwfly/project/concurrent-programs/hp_list/main.c:401 (list+0x22c1)
#3 insert_thread /home/fwfly/project/concurrent-programs/hp_list/main.c:487 (list+0x243f)
Thread T2 (tid=275665, running) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main /home/fwfly/project/concurrent-programs/hp_list/main.c:509 (list+0x13e0)
Thread T1 (tid=275664, running) created by main thread at:
#0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:962 (libtsan.so.0+0x5ea79)
#1 main /home/fwfly/project/concurrent-programs/hp_list/main.c:509 (list+0x13e0)
SUMMARY: ThreadSanitizer: data race /home/fwfly/project/concurrent-programs/hp_list/main.c:325 in list_node_destroy
```
問題會發生在做 retire node 的部分，要先理解 retire 跟整個 hp 的設計，才能知道為什麼這邊會發生
## 從基本的 list 開始
在 atomic 跟 hp 的幫助下，有點難看出來 atomic 跟 hp 解決了什麼事情,
所以把全部的 atomic 跟 hp 拿掉來實驗看看程式會出現什麼結果．
* prev 用的是 atomic_uintptr_t 去接 node，這是為了要讓 prev 可以做 atomic 操作，但是還不清楚為什麼只有在 prev 上面做這件事情．
## 使用 atomic 來處理 list 中的值
( To do )
## 使用 hp 來處理 concurrent 問題
( To do )
## 並行程式設計中的問題
1. RMW 可能會可能無法完成全部. 可能在做 R 或 M 的途中就會被切到另一個 thread 然讀到舊的值，導致結果產生錯誤 -> atomic operation 可解決
2. 執行順序會被compiler 或 CPU 置換 -> 使用 memory barrier 來確保執行順序正確
3. cache coherence 問題 -> atomic 可以等 cache 同步然後寫入 memory，但是會有效能問題
## Atomics
這次作業的 list.c 裡面的 hazard pointer 的機制是用 c11 的 atomic 去進行實作．所以再踏入 hazard pointer 前，要先了解一下 atomic 怎麼使用．
這次的實作有用到以下幾個 atomic 的 function
atomic_store : 把值給寫進去 atomic object
atomic_store_explicit : 跟 atomic_store 但是可以選擇怎麼處理 memory order
atomic_load : 把 atomic 值從 atomic object 中讀出來
atomic_compare_exchange_strong : 比較 atomic object atomic 跟另一個參數，如果比較大就把 desired 值存到 atomic object 中
get_unmarked ?
get_unmarked_node ?
## References
* [2021 年暑期 Linux 核心 第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-summer-quiz2)
* [atomic_store, atomic_store_explicit](https://en.cppreference.com/w/c/atomic/atomic_store)
* [memory_order](https://en.cppreference.com/w/c/atomic/memory_order)
* [POSIX Shared Memory](http://logan.tw/posts/2018/01/07/posix-shared-memory/)
* [Validating Memory Barriers and Atomic Instructions](https://lwn.net/Articles/470681)
* [内存屏障实验](http://cxd2014.github.io/2018/05/22/memory-barrier/)
* Linux Kernel Scheduler Internals - ch2 Multiprocessing
* [Memory Barriers: a Hardware View for Software Hackers](http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf)
* [每位程式開發者都該知道的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/cpu-caches/cpu-caches-in-the-big-picture.html?q=)
* [gcc tsan_interface_atomic.cpp](https://github.com/gcc-mirror/gcc/blob/master/libsanitizer/tsan/tsan_interface_atomic.cpp)
* [ThreadSanitizer – data race detection in practice](http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35604.pdf)
* [TSan: possible false positive with atomics](https://github.com/google/sanitizers/issues/1009)
* [Hazard Pointers: Safe Memory Reclamation for
Lock-Free Objects](https://www.cs.bgu.ac.il/~satcc112/wiki.files/HazardPointers.pdf)
* [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)
Sign in with Wallet
Connect another wallet