# 2021q3 Homework2 (hp)
contributed by < `st9540808` >
###### tags: `linux2021`
## 1. 解釋程式碼運作原理
程式碼中有用到 C 語言的 atomic 操作標準函式庫，如 `atomic_store` 等等，因此想說先理解這部分的原理。
### atomic 和 memory order 的差異
atomic 確保任何記憶體的操作不會被其他指令所打斷，處理器會提供特殊的指令以實作這類型的操作，例如 CAS 和 LL/SC。
memory order 則是確保規範對記憶體操作的順序，編譯器做最佳化時可能會重排指令，雖然程式的效果都是一致的，但是有可能會更改某幾個變數操作的順序。再加上現代處理器因為支援亂序執行，指令執行的先後順序也會改變，這會跟硬體的 memory model 有關，不同的 memory model 在執行時期會做不同的 memory reorder。
> 其實在看資料發現有兩種不同的 reorder，一種是 ==instruction reorder== 指的是由於編譯器優化或 OOO 造成的指令並非以 program order 執行，另一種是 ==memory reorder==，由於現代處理器都有 write buffer 和 cache，就算指令是 inorder 執行的也不能確保記憶體操作順序一致。
atomic 是存取共享記憶體上的變數唯一正確的方式，而之所以 memory order 會跟 atomic 綁在一起，我想是因為存取共享變數後，我們同時會想確保與其他記憶體操作的先後關係，單獨使用 atomic 操作是沒辦法確保指令不被 reorder 和操作被可見的順序，所以才會造成 data race (執行結果完全取決於不同處理器的執行速度)。
> ```
> Proc0 Proc1
> (1) A = 1 (3) B = 1
> (2) print B (4) print A
> ```
> 很多教材會拿這個當作範例，對 A 和 B 變數的操作規範了 memory order，我們才能確保操作順序且其為可見的，所以只會印出 "01" (順序 1,2,3,4) 或 "11" (順序 "1,3,2,4")，而不會印出其他結果。
### Memory Consistency
擷取自 CS149 PARALLEL COMPUTING:
> - Memory consistency defines the behavior of reads and writes to ***different*** location (as observed by other processors)
> - Consistency deals with when writes to X propagate to other processors, ***relative*** to reads and writes to other address.
Memory Consistency 在乎的是對某一變數的寫入或讀取，相對於其他變數的順序，會用以下四種 memory operation order 來 model，底下 X 和 Y 代表不同的變數，
- **W~X~ ➔ R~Y~** **(Store-Load)** 在 TSO (Total Store Ordering) 的機器上只允許這個順序重排，也就是讀取 Y 可能會比寫入 X 先完成，這是因為 W~X~ 只會寫入 write buffer，並還沒有 commit 到快取或是記憶體
- **R~X~ ➔ R~Y~** **(Load-Load)**
- **R~X~ ➔ W~Y~** **(Load-Store)** OOO 可能會重排以上兩個操作
- **W~X~ ➔ W~Y~** **(Store-Store)** 寫入 write buffer 之後的 commit 順序可能反轉，例如前一個 cache miss 而後一個 cache hit。
Sequential Consistency
~ All processor issue loads and stores in program order. A sequential consistency memory system maintains all four memory operation orderings.
Sequential Consistency 確保每個處理器的 memory operation 都如原始程式指令排列的順序執行，但因為這種 model 的執行效率太低了，每一個指令都必須等待上一個指令完成，並且其結果是對其他處理器是可見才能繼續執行，所以才有 Relaxed Memory Model，會對記憶體操作做最佳化。
> 參考: [stanford cs149 Lecture 11: Memory Consistency + Implementation Synchronization](http://cs149.stanford.edu/fall20/lecture/consistency/)
memory order 實作上會使用 memory barrier 或是特殊指令，依據架構會有所不同。
:::info
稍微看一下 release 和 sequential consistency 編譯的結果有何差別
原始程式碼
```c
atomic_uintptr_t sd;
int ex;
int seq_cst(int num) {
ex = 5;
atomic_store_explicit(&sd, 42, memory_order_seq_cst);
}
int release(int num) {
ex = 5;
atomic_store_explicit(&sd, 42, memory_order_release);
}
```
x86-64-gcc 11.2 產生以下指令
```x86
seq_cst:
mov DWORD PTR ex[rip], 5
mov eax, 42
xchg rax, QWORD PTR sd[rip]
ret
release:
mov DWORD PTR ex[rip], 5
mov QWORD PTR sd[rip], 42
ret
```
`xchg` 指令隱含了 `LOCK`，對某個 cache line 取得 exclusive access，其效果會等同於一個 full memory barrier。另外在 release 沒有看到 `xchg`，推測由於 x86 架構是 strong memory model (遵守 TSO)，在 Load-Load, Store-Store, Load-Store 情況下是安全的，因此不用擔心 `ex = 5` 會比下一個 load 先執行完成。
<br>
> 另外發現在 ARM64 架構下產生的指令 seq_cst 和 release 會是相同的，而且沒有 `dmb`，在 ARM (32 bit) 才會產生 `dmb`，以後再補原因
> [time=Tue, Aug 10, 2021 12:38 AM]
> 參考: [AArch64 memory model](https://developer.arm.com/documentation/102376/0100/Normal-memory)
:::
memory order 共有六種類型，只列出最重要的 acquire/release，他們是單向的 barrier
- load acquire: barrier 之後的指令不能在 barrier ==之前==執行
- store release: barrier 之前的指令不能被重排至 barrier ==之後==
先看程式碼中有用到的 atomic 和規範 memory order 的操作
```c
uintptr_t list_hp_protect_release(list_hp_t *hp, int ihp, uintptr_t ptr)
{
atomic_store_explicit(&hp->hp[tid()][ihp], ptr, memory_order_release);
return ptr;
}
```
`memory_order_release` 代表這行指令之前的所有指令，都不能重排到這行指令之後，因此能確保當 `atomic_store_explicit` 執行完成後，之前的操作對於其他處理器都是可見的。
### `list_t` 如何做節點的刪除？
#### `list_hp_retire`
`list_hp_retire` 這個函式的功能是做 memory reclamation，當目前 retire list 中的元素個數超過 `HP_THRESHOLD_R` 時會掃過所有 hazard pointer，值得注意的是 hazard pointer 為 ==single-writer multiple-reader shared pointers==，意思是某一組 hazard pointer 只會被某一特定的執行緒寫入，而會被很多個執行緒讀取 (在本題為執行 `list_delete` 的執行緒)。
Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects 中提到：
> *If a retired node is not matched by any of the hazard pointers, then it is safe for this node to be reclaimed. Otherwise, the thread keeps the node until its next scan of the hazard pointers.*
```c
retirelist_t *rl = hp->rl[tid() * CLPAD];
```
也就是說 `list_hp_retire` 會找到某個特定執行緒的 retire list (以上述程式碼 `hp->rl[tid() * CLPAD]` 取得) 與所有 harzard pointer 的差集 (set difference)，其結果就是可以被安全釋放的節點。
至於為何可以確定這個差集的節點不會再被存取呢？原因是在 `list_delete` 函式中使用了 `get_marked` 巨集標示這個節點，只要 `node->next` 被 `get_marked` 標註了，代表有個執行緒正常是刪除它 (更準確地說是被 logically deleted)，所以我們只要用 `is_marked` 巨集檢查就能確認物件是否正被刪除。
#### `list_delete`
```c=
bool list_delete(list_t *list, list_key_t key)
{
list_node_t *curr, *next;
atomic_uintptr_t *prev;
while (true) {
if (!__list_find(list, &key, &prev, &curr, &next)) {
/* if node containing key does not exist, return false
*/
list_hp_clear(list->hp);
return false;
}
uintptr_t tmp = get_unmarked(next);
if (!atomic_compare_exchange_strong(&curr->next, &tmp,
get_marked(next)))
continue;
tmp = get_unmarked(curr);
if (atomic_compare_exchange_strong(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;
}
}
```
- 第 15 行將 `curr->next` 標註，而 `curr` 是即將被刪除的節點。
- 第 20 行用 CAS 嘗試修改 `prev` 指向 `next`，也就是將 `curr` 從鏈結串列移除，如果失敗代表 `prev` 被其他執行緒修改了，目前已經不是指向 `curr`，就不用將 `curr` 放到 retire list。
:::warning
目前還是不知道到底 `prev` 在什麼時候會被修改
:::
- 確認已經刪除 (logically deleted) 之後就能清空 hazard pointer (21,24 行)，
### 操作 hazard pointers
> *When a thread assigns a reference (i.e., a node’s address) to one of its hazard pointers, it basically **announces** to other threads that it may use that reference in a hazardous manner (e.g., access the contents of the node without further validation of the reference), so that other threads will refrain from reclaiming or reusing the node until the reference is no longer hazardous. This announcement (i.e., setting the hazard pointer) must take place before the node is retired.*
當執行緒要存取節點時，必須把節點的位址賦值到 harzard pointer (`list->hp`) 中，避免 `list_hp_retire` 回收節點的記憶體資源，整個程式碼中只有在 `__list_find` 中會寫入 harzard pointer。
#### `__list_find`
`__list_find` 執行過程中會存取三個 `list_t` 中的節點，它的功能是找到一個大於等於 key 的節點放到 `curr`，
這也是為什麼每一個執行緒都有三個 harzard pointer
- `prev` 從 `head` 開始
### 統計結果
```
retry : 85
contains : 0
traversal : 21130987
fail : 1
del : 0
ins : 1
load : 63475932
store : 4097
deletes : 4098
inserts : 4098
```
關掉 TSAN 之後可以跑比較快，而且我試好多次才有 `CAS` 失敗的情況。
deletes 和 inserts 之所以為 4098，在 `list_insert` 總共 new 出來的節點共 32 * 128 = 4096 個 (`N_THREADS` / 2 * `N_ELEMENTS`)，另外還要為 `list_t` 物件的兩個資料成員 `head` 和 `tail` 分配記憶體，所以總共 4096 + 2 = 4098
## 2. 指出改進空間並著手實作
嘗試在 `list_hp_retire` 使用較為寬鬆的 memory order
```diff
void list_hp_retire(list_hp_t *hp, uintptr_t ptr)
{
...
for (size_t iret = 0; iret < rl->size; iret++) {
uintptr_t obj = rl->list[iret];
bool can_delete = true;
for (int itid = 0; itid < HP_MAX_THREADS && can_delete; itid++) {
for (int ihp = hp->max_hps - 1; ihp >= 0; ihp--) {
- if (atomic_load(&hp->hp[itid][ihp]) == obj) {
+ if (atomic_load_explicit(&hp->hp[itid][ihp],
+ memory_order_acquire) == obj) {
can_delete = false;
break;
}
}
}
...
}
}
```
TSAN 沒有印出錯誤，但從原程式碼的執行時間來看，效能並沒有明顯的提升，應該要直接測量 `list_hp_retire` 所耗費的時間會比較好。
bpftrace 時間量測命令
```shell!
$ sudo bpftrace -e 'uprobe:./list:list_hp_retire {@start[tid] = nsecs; } uretprobe:./list:list_hp_retire /@start[tid]/ { printf("%d\n", nsecs - @start[tid]); delete(@start[tid]); }' > test
```
原始程式碼 `list_hp_retire` 所需時間如下，單位 ns
```
Min. 1st Qu. Median Mean 3rd Qu. Max.
2100 2300 2400 2820 2700 23900
```
修改後所需的時間：
```
Min. 1st Qu. Median Mean 3rd Qu. Max.
2100 2300 2400 2830 2700 35000
```
看起來完全沒有變快。
## 3. 對比 rcu_list 和跟上述 Hazard pointer 手法有何異同
## 4. rcu_list 實作缺陷與改進
Sign in with Wallet
Connect another wallet