---
tags: linux kernel, linux2022
---
# 2022q1 Homework5 (quiz6)
contributed by < [linjohnss](https://github.com/linjohnss) >
> [2022q1 第 6 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz6)
## 測驗 `1`
> 利用 clone 實做 user level 的 thread 函式庫
### 程式碼實做原理
#### 函數使用
```c
int main()
{
mutex_init(&lock);
mutex_init(&rwlock);
spin_init(&print_lock);
atomic_init(&n_readers_in, 0);
atomic_init(&n_writers_in, 0);
thread_t readers[5], writers[5];
for (int i = 0; i < 5; i++) {
thread_create(&readers[i], f1, NULL);
thread_create(&writers[i], f2, NULL);
}
for (int i = 0; i < 5; i++) {
thread_join(writers[i], NULL);
thread_join(readers[i], NULL);
}
return 0;
}
```
首先初始化 `mutex`, `spin`, `atomic`
接著 `create` 10 個 thread（5 個 reader, 5 個 writer）
最後分別 `join` 這 10 個 thread
```shell
Reader process in
Reader process in
Reader process out
Reader process out
Writer process in
Writers process out
Writer process in
Writers process out
Reader process in
Reader process out
Reader process in
Reader process out
Writer process in
Writers process out
Writer process in
Writers process out
Writer process in
Writers process out
Reader process in
Reader process out
```
會有 10 個 reader 的 in, out 與 10 個 writer 的 in, out
## 測驗 `2`
### lock-free
在並行程式設計中，存取共同記憶體時，使用 mutex 是最直觀的方式，然而 mutex 容易造成 thread 互相阻塞的機會。為了提高程式的運行效能，可以改用 lock-free 結構來處理。
### 何種情境要考慮 ABA Problem
在執行 [CAS](https://en.wikipedia.org/wiki/Compare-and-swap) 時，若 thread1 在讀取的間隔中，有其他 thread2 修改該值，使得 thread1 誤以為值並未改變，造成非預期的結果。
> stack:top → A → B → C
> thread1 run pop and gets interrupted before the compare_exchange_weak
> thread2 pop twice and push A back
> stack:top → A → C
> thread1 will error assigning B as new head node
### [lock-free hash table](https://gist.github.com/jserv/c3823ea893e08607b432827a11ec4b69) 如何避免 ABA Problem?
#### Hazard pointer
根據[2022q1 第 5 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz5#%E6%B8%AC%E9%A9%97-2)描述
> Hazard pointer 是其中一種 lock-free 處理記憶體釋放的解決方案，其原理是讀取端執行緒對指標進行識別，指標 (特別是指向的記憶體區塊) 若要釋放時，==會事先保存，延遲到確認沒有讀取端執行緒，才進行真正的釋放==。
在 hazard pointer 架構中，每個 thread 首先需要各自維護的兩個關鍵集合是：
- hazard pointer: 儲存此 thread 正在存取的指標，因此該指標不能直接被釋放
- retire list: 被這個 thread 要求釋放的指標，但實際尚未釋放
因此要安全的釋放記憶體，其基本想法就是：
- 每個執行緒放在 hazard pointer 中的指標尚不能被釋放
- 每個執行緒要求釋放的指標先放在 retire list 中
- 掃描 retire list 可以得知所有執行緒皆不使用的指標，則可將其真正的釋放給作業系統
#### 程式碼的作法
在 `destroy_node_later` 中，分別用 `free_later` 釋放 `node->key`、`node->value` 與 `node`，不會直接釋放記憶體而是根據不同型態決定其釋放空間的方式
```c=20
static void destroy_node_later(void *opaque, hashmap_kv_t *node)
{
/* free all of these later in case other threads are using them */
free_later((void *) node->key, free);
free_later(node->value, opaque);
free_later(node, free);
}
```
### 程式碼運作原理
#### hashmap 結構
首先，查看 hashmap 的資料結構，其定義在 `hashmap.h`：
```c
/* links in the linked lists that each bucket uses */
typedef struct hashmap_keyval {
struct hashmap_keyval *next;
const void *key;
void *value;
} hashmap_kv_t;
/* main hashmap struct with buckets of linked lists */
typedef struct {
hashmap_kv_t **buckets;
uint32_t n_buckets;
uint32_t length; /* total count of entries */
/* pointer to the hash and comparison functions */
uint64_t (*hash)(const void *key);
uint8_t (*cmp)(const void *x, const void *y);
/* custom memory management of internal linked lists */
void *opaque;
hashmap_kv_t *(*create_node)(void *opaque, const void *key, void *data);
void (*destroy_node)(void *opaque, hashmap_kv_t *node);
} hashmap_t;
```
為一個由`n_buckets` 個 `hashmap_kv_t` 單相串接而成的結構
另外包含兩個 function pointer `hash` 與 `cmp`
利用 `hashmap_new`、`hashmap_get`、`hashmap_put`、`hashmap_del` 對 hashmap 進行操作
#### hashmap_put
hashmap_put 負責將 `value` 根據 `key` 放入 `map` 中
```c
/* Put the given key-value pair in the map.
* @return true if an existing matching key was replaced.
*/
bool hashmap_put(hashmap_t *map, const void *key, void *value);
```
先根據 `key` 找到對應的 `bucket_index`
```c=67
uint32_t bucket_index = map->hash(key) % map->n_buckets;
```
接著在 while 迴圈中，負找到對應的 `bucket_index` 中 `key` 是否已存在
`prev` 紀錄前一個節點
```c=80
prev = NULL;
if (head) {
for (kv = head; kv; kv = kv->next) {
if (map->cmp(key, kv->key) == 0)
break;
prev = kv;
}
}
```
若 `kv` 存在，更新該節點的 `value`
分為兩種狀況：
1. 存在前一個節點 `prev`：
需要更新 `prev->next`，將 `next` 接上去，故 `KKKK` = `&prev->next`
然後對 `kv` 執行 `destroy_node`
```c=100
if (__atomic_compare_exchange(KKKK, &kv, &next, false,
__ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
/* this node, key and value are never again used by this */
map->destroy_node(map->opaque, kv);
return true;
}
```
2. 不存在前一個節點 `prev`，即為 `head`：
需要更新 `head->next`，將 `next` 接上去，故 `QQQQ` = `&map->buckets[bucket_index]`
然後對 `kv` 執行 `destroy_node`
```c=112
if (__atomic_compare_exchange(QQQQ, &kv,
&next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
map->destroy_node(map->opaque, kv);
return true;
}
```
若 `kv` 不存在，代表未發現 `key`，需要建立節點並當成新的 `head`
需要更新 `map->buckets[bucket_index]`，將 `next` 接上去
以 `__atomic_fetch_add` 的方式將 `map->length` 加 1
```c=133
if (__atomic_compare_exchange(&map->buckets[bucket_index], &head,
&next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_add(&map->length, 1, __ATOMIC_SEQ_CST);
return false;
}
```
#### hashmap_del
刪除 `key` 對應的節點，並保證在 multiple threads 同時刪除同一個 `key` 時，只會刪除一次
```c
/* Remove the given key-value pair in the map.
* @return true if a key was found.
* This operation is guaranteed to return true just once, if multiple threads
* are attempting to delete the same key.
*/
bool hashmap_del(hashmap_t *map, const void *key);
```
同 `hashmap_put` 要先找到對應的 `bucket_index`
判斷是否找到目標 `match`
判斷 `prev` 是否存在
1. `prev` 存在：
需要更新 `prev->next`，將 `match->next` 接上去，故 `ZZZZ` = `&prev->next`
以 `__atomic_fetch_sub` 的方式將 `map->length` 減 1
然後對 `kv` 執行 `destroy_node`
```c=171
if (__atomic_compare_exchange(ZZZZ, &match, &match->next,
false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_sub(&map->length, 1, __ATOMIC_SEQ_CST);
map->destroy_node(map->opaque, match);
return true;
}
```
2. `prev` 不存在，`match` 即為 `head`：
```c=181
if (__atomic_compare_exchange(&map->buckets[bucket_index], &match,
&match->next, false, __ATOMIC_SEQ_CST,
__ATOMIC_SEQ_CST)) {
__atomic_fetch_sub(&map->length, 1, __ATOMIC_SEQ_CST);
map->destroy_node(map->opaque, match);
return true;
}
```
### hashmap_put 考慮因素
#### 最佳的情況下，時間複雜度是 O(1)
hashmap 在沒有發生 collision 時的時間複雜度是 O(1)
本次所使用的 hash function 是直接 mod
```c
static uint64_t hash_uint32(const void *key)
{
return *(uint32_t *) key;
}
```
#### hash function 處理 collision 的作法
***Separate chaining***
發生 collision 將相同 index 的 node 串接在一起
選擇 key mod 7 作為 hash function，輸入 50, 700, 76, 85, 92, 73, 101
```graphviz
digraph dfd2{
rankdir=LR
node[shape=record]
input1 [label="50"];
input2 [label="700"];
input3 [label="76"];
input4 [label="85"];
input5 [label="92"];
input6 [label="73"];
input7 [label="101"];
hashmap [label = "<f0> hashmap|{<f1> 0\n |<f2> \n}|{<f3> 1\n |<f4> \n}|{<f5> 2\n |<f6> \n}|{<f7> 3\n |<f8> \n}|{<f9> 4\n |<f10> \n}|{<f11> 5\n |<f12> \n}|{<f13> 6\n |<f14> \n}"];
output1 [label="50"];
output2 [label="700"];
output3 [label="76"];
output4 [label="85"];
output5 [label="92"];
output6 [label="73"];
output7 [label="101"];
input1 -> hashmap:f3
input2 -> hashmap:f1
input3 -> hashmap:f13
input4 -> hashmap:f3
input5 -> hashmap:f3
input6 -> hashmap:f7
input7 -> hashmap:f7
hashmap:f4 -> output1 -> output4 -> output5
hashmap:f2 -> output2
hashmap:f14 -> output3
hashmap:f8 -> output6 -> output7
}
```
***Open addressing***
發生 collision 則往下接續尋找空的欄位，並插入空的欄位
選擇 key mod 7 作為 hash function，輸入 50, 700, 76, 85, 92, 73, 101
```graphviz
digraph dfd2{
rankdir=LR
node[shape=record]
input1 [label="50"];
input2 [label="700"];
input3 [label="76"];
input4 [label="85"];
input5 [label="92"];
input6 [label="73"];
input7 [label="101"];
hashmap [label = "<f0> hashmap|{<f1> 0\n |<f2> \n}|{<f3> 1\n |<f4> \n}|{<f5> 2\n |<f6> \n}|{<f7> 3\n |<f8> \n}|{<f9> 4\n |<f10> \n}|{<f11> 5\n |<f12> \n}|{<f13> 6\n |<f14> \n}"];
output1 [label="50"];
output2 [label="700"];
output3 [label="76"];
output4 [label="85"];
output5 [label="92"];
output6 [label="73"];
output7 [label="101"];
input1 -> hashmap:f3
input2 -> hashmap:f1
input3 -> hashmap:f13
input4 -> hashmap:f3
input5 -> hashmap:f3
input6 -> hashmap:f7
input7 -> hashmap:f7
hashmap:f4 -> output1
hashmap:f6 -> output4
hashmap:f8 -> output5
hashmap:f2 -> output2
hashmap:f14 -> output3
hashmap:f10 -> output6
hashmap:f12 -> output7
}
```
因為使用到 link list，Separate chaining 對於未知數量的 inputs 不用擔心 hash map 滿了，但 Separate chaining 相較於 Open addressing 會有高的效能損失。Open addressing 仰賴精準的 hash map 大小估計，進而避免越是後面的輸入其探查數量就急遽增高，因為碰到位子先有人佔的機率會愈來愈高。
#### 目前的 hashmap 採用何種手段？
目前 hashmap 採用 Separate chaining
發生 collision 時，也就是 `hashmap_put` 中 `head` 存在，程式會接著找尋 `head` 後續串接的 node，代表每個 `bucket` 是由一條 link list 組成
```c=80
if (head) {
for (kv = head; kv; kv = kv->next) {
if (map->cmp(key, kv->key) == 0)
break;
prev = kv;
}
}
```
並且當 `kv` 不存在時，會先將 `next->next` 指向 `head`，代表當發生 collision 時，會將新的節點插入至 link list 的開頭
```c=129
if (head) /* make sure the reference to existing nodes is kept */
next->next = head;
```
#### hashmap_put_retries 的作用?
`hashmap_put` 有三個在執行 `__atomic_compare_exchange` 負責紀錄失敗次數的指標
- hashmap_put_replace_fail
- hashmap_put_head_fail
- hashmap_put_retries
#### free later
free later 是先將要釋放記憶體的資料加到一個 link list `buffer`，後續呼叫 `free_later_exit` 時才會將 `buffer` 中的資料釋放
`list_t` 的結構包含 `head` 與紀錄長度的 `length`，每一個 `list_node_t` 包含串接下一個 `node` 的指標，與紀錄資料的 `val`
```c
typedef struct list_node {
struct list_node *next;
void *val;
} list_node_t;
typedef struct {
list_node_t *head;
uint32_t length;
} list_t;
```
`free_later_t` 為 link list `val` 存放的資料結構，包含欲釋放的變數 `var` 與 function pointer `free` 可以用於決定變數釋放的時機
```c
typedef struct {
void *var;
void (*free)(void *var);
} free_later_t;
```
當我們呼叫 `free_later_exit` 就會釋放 `buffer` 中的記憶體
```c
int free_later_exit()
{
/* purge anything that is buffered */
free_later_run();
/* stage and purge anything that was unbuffered */
free_later_stage();
free_later_run();
/* release memory for the buffer */
free(buffer);
buffer = NULL;
return 0;
}
```
### 程式碼改進
#### `free_later_run` 會試圖存取已經被釋放的空間
```c=137
for (list_node_t *n = buffer_prev->head; n; n = n->next) {
free_later_t *v = n->val;
v->free(v->var);
free(n);
}
```
Sign in with Wallet
Connect another wallet