# 2021q3 Homework2 (hp)
contributed by < `ccs100203` >
###### tags: `linux2021q3`
> [quiz2](https://hackmd.io/@sysprog/linux2021-summer-quiz2)
- reference
[Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf)
[A Pragmatic Implementation of Non-Blocking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)
[並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree)
[並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-atomics)
- source
[hp_list](https://github.com/sysprog21/concurrent-programs/tree/master/hp_list)
[concurrent-ll](https://github.com/jserv/concurrent-ll)
## 解釋程式碼運作原理
程式以 lock-free 以及 hazard pointer 的手法，建立相同量的 thread 做 insert / delete 的動作，上圖為 hazard pointer 的結構示意。
### Struct
```cpp
typedef struct {
int size;
uintptr_t *list;
} retirelist_t;
```
Hazard pointer 中使用到的 retire list 的結構
```cpp
#define CLPAD (128 / sizeof(uintptr_t))
typedef struct list_hp list_hp_t;
typedef void(list_hp_deletefunc_t)(void *);
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;
};
```
Hazard pointer 的主要結構
- `alignas(128) atomic_uintptr_t *hp[HP_MAX_THREADS];`
`hp` 的實作是用一個類似二維陣列去儲存整個 hazard pointer 的內容
用 `HP_MAX_THREADS` 去決定 row 有多少，是因為每條 Thread 都要有自己的 hazard pointer，這部份可以從示意圖中看出來，詳細則在 [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf) 中描述。
- [alignas](https://en.cppreference.com/w/cpp/language/alignas) 定義在 C++ 11 中，可在宣告時用來對齊
>the declaration or definition of a **class/struct/union** or **enumeration**;
the declaration of a **non-bitfield class data member**;
the declaration of a **variable**, **except** that it cannot be applied to the following:
a **function parameter**;
**the exception parameter of a catch clause**.
對齊可以避免 false sharing 以及 cacheline coherence 所造成的影響，retirelist 中使用的 `CLPAD` 就是來協助 cacheline padding 的。
==為何是對齊 128 尚未釐清==
- `max_hps` 決定了每條 thread 中的 hazard pointer 有多少容量 (==實作中貌似未檢查==)
- `alignas(128) retirelist_t *rl[HP_MAX_THREADS * CLPAD];`
每個 Thread 會有 `CLPAD` 個 retire list
```cpp
typedef uintptr_t list_key_t;
typedef struct list_node {
alignas(128) uint32_t magic;
alignas(128) atomic_uintptr_t next;
list_key_t key;
} list_node_t;
/* Per list variables */
typedef struct list {
atomic_uintptr_t head, tail;
list_hp_t *hp;
} list_t;
```
此程式的結構都包裝在 `list_t` 之內，以其為 list 的主體。
- `magic` 協助驗證正確性，確保該 node 的記憶體範圍並未被其他部份修改到。
- `key` 是 list 與 hazard pointer 中用來索引的 index，會以 tid 為依據。
### Tid
```cpp
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，以遞增的方式對每條 thread 進行編號，存放在具有 [thread_local](https://www.gnu.org/software/libc/manual/html_node/ISO-C-Thread_002dlocal-Storage.html) 性質的 `tid_v` 中，代表該變數在每個 thread 具有獨立性，並有 thread storage duration。
`atomic_int_fast32_t` 這個 type 在 [std::atomic](https://en.cppreference.com/w/cpp/atomic/atomic) 及 [Fixed width integer types](https://en.cppreference.com/w/cpp/types/integer) 之中有解釋，在 C++ 11 後有分成 `int8_t`, `int_fast8_t`, `int_least8_t`。
- `int8_t` 剛好 8 bit 的 int
- `int_fast8_t` 進行操作最快的 int，但是至少 8 bit
- `int_least8_t` 該 int 使用最少的 bit，但是至少 8 bit
### Find
`__list_find` 是此程式的核心，這裡會以 lock-free 的手法，並讓 list 維持 ascending，以及讓某些條件下的 node 放入 retire list。回傳 true 代表找到該 `key` 在 list 內，並藉由 pointer to pointer 的方式回傳給 caller。
```cpp=
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);
if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
TRACE(retry);
goto try_again;
}
```
- `prev` 的作用像是存放 `curr` 的複本，用來對照當前的 `curr` 是否已經被更改，是以 pointer to pointer 的方式。
- `try_again:` 的作用是當程式發現當前操作的指標有被其他 thread 更動過時，就會重做
- `list_hp_protect_ptr` 會將操作的節點放入 hazard pointer 中，代表當前的 thread 正在使用，作為避免被刪除的保護
- 第 14~17 行，確認此時的 `prev` 與 `curr` 是否相同，不同就要重做
:::info
2021/08/20
可以確認 `head` 是否被 mark
:::
```cpp=18
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));
/* On a CAS failure, the search function, "__list_find," will simply
* have to go backwards in the list until an unmarked element is found
* from which the search in increasing key order can be started.
*/
if (ATOMIC_LOAD(&get_unmarked_node(curr)->next) != (uintptr_t) next) {
TRACE(retry);
goto try_again;
}
if (ATOMIC_LOAD(prev) != get_unmarked(curr)) {
TRACE(retry);
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); // FFF
}
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 (!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);
}
}
```
while 會對 list 進行尋訪，並找到適當的插入位置 (由小到大)，在找到 `curr->key >= key` 或 tail 之前不會讓迴圈結束。而如果中途有找到 marked node，則會將該 node 放入 retire list 內，不作為回傳的結果使用。
- 第 21 行會將 `next` 也放入 hazard pointer 之中。再來會確認 local 的 `next` 是否與 list 中的 `next` 相同，因為有可能已經被插入新的節點了，也確認 `prev` 是否還等於 `curr`。
- 第 35 行 `get_unmarked_node(next) == next` 是利用到 [A Pragmatic Implementation of Non-Blocking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf) 的手法，被標記的 memory 區塊代表他是已經準備被刪除的了，所以就不會將此 `next` 作為要使用的下一個 node。
- 已經被 mark 的節點，會在第 45 行的 else，先通過 [CAS](https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html) 確定還是當前的 `next`，然後用 `list_hp_retire` 將他放入 retire list裡，並進行處理。
- 未被 mark 的節點，會先透過 `(get_unmarked_node(curr)->key < *key)` 確認是否符合條件，要注意第 40 行的判斷，會回傳 true 讓程式不插入相同 `key` 值的節點。
- 使用 `list_hp_protect_release` 將需要保護的 node 放入 hazard pointer 之中，利用 release 的 memory order 確保在這之前的 store 都以寫入。
### Insert
```cpp=
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 (CAS(prev, &tmp, (uintptr_t) node)) {
list_hp_clear(list->hp);
return true;
}
TRACE(ins);
}
}
```
第 6 行會先利用 `list_node_new` 根據傳入的 `key` 創一個新的 node，藉由 `__list_find` 得到插入的位置，要注意回傳 true 則代表有重複節點，所以把現在新創立的 destroy 並從 hazard pointer 中移除。
再來程式會將新的 `node` 的 `next` 先指向 `curr`
```graphviz
digraph graphname{
node[shape=box]
curr[shape=plaintext,fontcolor=red]
prev[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label="node"]
NULL1[label=NULL,shape=plaintext]
// NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
// indirect[shape=plaintext,fontcolor=blue]
prev->curr->B
}
A->B->C->NULL1
D->B
}
```
再來先透過 CAS 確保 `prev` 的位置還未被換過，然後將 `node` 放入原本 `curr` 的位置中
```graphviz
digraph graphname{
node[shape=box]
curr[shape=plaintext,fontcolor=red]
prev[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label="node"]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
curr->B
}
{
rank="same"
prev->D
}
A->D->B->C->NULL1
}
```
#### list_node_new
```cpp
list_node_t *list_node_new(list_key_t key)
{
list_node_t *node = aligned_alloc(128, sizeof(*node));
assert(node);
*node = (list_node_t){.magic = LIST_MAGIC, .key = key};
(void) atomic_fetch_add(&inserts, 1);
return node;
}
```
利用 [aligned_alloc](https://linux.die.net/man/3/aligned_alloc) 確保配置的空間對齊 128。
使用 [atomic_fetch_add](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html) 操作 `inserts`，紀錄插入的次數。
### Delete
```cpp=
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)) {
list_hp_clear(list->hp);
return false;
}
uintptr_t tmp = get_unmarked(next);
if (!CAS(&curr->next, &tmp, get_marked(next))) {
TRACE(del);
continue;
}
tmp = get_unmarked(curr);
if (CAS(prev, &tmp, get_unmarked(next))) {
list_hp_clear(list->hp);
list_hp_retire(list->hp, get_unmarked(curr)); // DDD
} else {
list_hp_clear(list->hp);
}
return true;
}
}
```
用 `__list_find` 查找要刪除的節點是否在 list 中，沒有的話記得先從 hazard pointer 將當前保護的 memory 移掉再返回。
第 13 行的 CAS 不僅確保 `next` 未被更動，將 `next` mark 可以確保不會被其他 thread 使用。
第 19 行的 CAS 先是確保 `prev` 與 `curr` 尚未被動過，然後將 `next` unmark 並放入原本 list 內 `curr` 的位置，藉此將 `curr` 從 list 中移除。移除後的 `curr` 就交由 `list_hp_retire` 去處理。
### Retire
在 [Lock-Free Data Structures with Hazard Pointers](https://erdani.org/publications/cuj-2004-12.pdf) 中有提及 retire list 的原理，當 list 內的東西達到一定量時，在這邊是利用 `HP_THRESHOLD_R`，會去查找所有 hazard pointer 的內容，確認要刪除的 memory 不在 hazard pointer 的保護中，來判斷 retire list 內的記憶體是否可以釋放掉。
```cpp=
void list_hp_retire(list_hp_t *hp, uintptr_t ptr)
{
retirelist_t *rl = hp->rl[tid() * CLPAD];
rl->list[rl->size++] = ptr;
assert(rl->size < HP_MAX_RETIRED);
if (rl->size < HP_THRESHOLD_R)
return;
```
將傳入的 `ptr` 放入該 thread 對應的 retire list 中。
再藉由 `HP_THRESHOLD_R` 去判斷是否要開始進行回收的動作，因為程式的 `HP_THRESHOLD_R` 設為 0，所以每次有節點放入就會立刻進行查找的動作。(==或許可以參照論文的建議將其調大==)
```cpp=9
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) {
can_delete = false;
break;
}
}
}
if (can_delete) {
size_t bytes = (rl->size - iret) * sizeof(rl->list[0]);
memmove(&rl->list[iret], &rl->list[iret + 1], bytes);
rl->size--;
hp->deletefunc((void *) obj); // RRR
}
}
}
```
第 9 行，會以每一個 retire list 內的節點，去 hazard pointer 中進行查找，如果有找到就會將 `can_delete` 設為 false，代表還不能刪除。
最後如果可以刪除，會利用 [memmove](https://man7.org/linux/man-pages/man3/memmove.3.html) 將 `iret` 之後記憶體空間往前移，覆蓋掉被刪除的位置，藉以達到從 retire list 中移除的效果，同時可以維持該陣列的結構。並將要刪除的節點傳入 `deletefunc` 刪除。(在程式中是 `__list_node_delete`)
#### Delete Function
```cpp
void list_node_destroy(list_node_t *node)
{
if (!node)
return;
assert(node->magic == LIST_MAGIC);
free(node);
(void) atomic_fetch_add(&deletes, 1);
}
static void __list_node_delete(void *arg)
{
list_node_t *node = (list_node_t *) arg;
list_node_destroy(node);
}
```
`free` 之前，會先對照 `LIST_MAGIC` 是否相同，藉由比對 [magic number](https://en.wikipedia.org/wiki/Magic_number_(programming)) 來判斷該記憶體位置沒有被不正確的更改，保證程式的正確性。
同樣利用 [atomic_fetch_add](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html) 操作 `deletes`，紀錄刪除的次數。
## 程式改進空間
1. 128 / 2 改成 128 >> 1
2. find 中，try again 到 while 之間驗證 prev 跟 curr 的必要性
3. max_hps 沒檢查，沒做上限
4. memmove 效率? 雖然 intel 有對其優化
5. 論文中有提及 hash table of hazard pointer, hazard pointer / retire list 用其他更方便搜尋的結構跟使用其他搜尋演算法
## 對比 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list)，解釋同為 lock-free 演算法，跟上述 [Hazard pointer](https://en.wikipedia.org/wiki/Hazard_pointer) 手法有何異同？能否指出 rcu_list 實作缺陷並改進？
TODO
Sign in with Wallet
Connect another wallet