---
tags: 2022 linux kernel
---
# 2022q1 Homework5 (quiz5)
contributed by < [`Risheng1128`](https://github.com/Risheng1128) >
> [作業說明](https://hackmd.io/@sysprog/linux2022-homework5)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz5)
## 測驗 `1`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，指出可改進之處並實作
> 是否有必要先將數值轉成字串？用十進位的角度處理運算是否產生額外的計算負擔？
- [ ] Linux 核心原始程式碼 [lib/math/prime_numbers.c](https://github.com/torvalds/linux/blob/master/lib/math/prime_numbers.c) 有類似的程式碼，請解釋其作用、裡頭 [RCU](https://hackmd.io/@sysprog/linux-rcu) 的使用情境，及針對執行時間的改進
:::
## 測驗 `2`
:::info
延伸問題:
- [ ] 解釋上述程式碼運作原理，指出可改進之處並實作
- [ ] 上述程式碼開啟多個 reader 時，無法通過 [ThreadSanitizer](https://clang.llvm.org/docs/ThreadSanitizer.html)，請指出具體問題並克服
- [ ] 比較 [RCU](https://hackmd.io/@sysprog/linux-rcu) 和 hazard pointer (HP)，探討為何 Linux 不採用 HP 而是另外發展 RCU
:::
### 初始化
首先從實作中兩個重要的結構 `domain_t` 及 `hp_t` 開始討論
```c
typedef struct {
hp_t *pointers; // hazard pointers
hp_t *retired; // retire list
void (*deallocator)(void *);
} domain_t;
typedef struct __hp {
uintptr_t ptr;
struct __hp *next;
} hp_t;
```
從結構定義可以很明顯的看出兩種結構分別的用意
- `domain_t` 用來建立管理 hazard pointer 和 retire list 的結構，其中 `deallocator` 是用來釋放記憶體的函式指標
- `hp_t` 為一般的 linked list 實作，用來儲存共享資料，並加進 hazard pointer 或 retire list ，`ptr` 則是正在讀取的資料的地址
以上述的結構定義可以得到和題目一樣的架構
接著討論結構的建立以及釋放，實作為函式 `init` 及 `deinit`
```c
// 共享資料
typedef struct {
unsigned int v1, v2, v3;
} config_t;
static config_t *shared_config;
static domain_t *config_dom;
void init()
{
// 建立共享資料，且初始 (v1,v2,v3) = (0,0,0)
shared_config = create_config();
// Create a new domain on the heap
config_dom = domain_new((void *)delete_config);
if (!config_dom)
err(EXIT_FAILURE, "domain_new");
}
void deinit()
{
delete_config(shared_config);
domain_free(config_dom);
}
```
函式 `init` 的部份，一共做了兩件事
- 建立資料 (型態為 `config_t`) ，並且由指標 `shared_config` 指著，以下為函式 `create_config` 的實作
```c
config_t *create_config()
{
config_t *out = calloc(1, sizeof(config_t));
if (!out)
err(EXIT_FAILURE, "calloc");
return out;
}
```
- 建立 hazard pointer 的整個架構，並且由指標 `config_dom` 指著，以下為函式 `domain_new` 的實作
```c
domain_t *domain_new(void (*deallocator)(void *))
{
domain_t *dom = calloc(1, sizeof(domain_t));
if (!dom)
return NULL;
dom->deallocator = deallocator;
return dom;
}
```
函式 `deinit` 則是將 `shared_config` 和 `config_dom` 分別釋放，以下為函式實作
```c
void delete_config(config_t *conf)
{
assert(conf);
free(conf);
}
void domain_free(domain_t *dom)
{
if (!dom)
return;
if (dom->pointers)
list_free(&dom->pointers); // 釋放 hazard pointer
if (dom->retired)
list_free(&dom->retired); // 釋放 retired list
free(dom);
}
```
### Reader Thread
程式主要執行的部份可以分為 `reader thread` 及 `writer thread` ，首先討論 `reader thread` 的部份
```c=
static void *reader_thread(void *arg)
{
(void) arg;
for (int i = 0; i < N_ITERS; ++i) {
config_t *safe_config =
(config_t *) load(config_dom, (uintptr_t *) &shared_config);
if (!safe_config)
err(EXIT_FAILURE, "load");
print_config("read config ", safe_config);
drop(config_dom, (uintptr_t) safe_config);
}
return NULL;
}
```
函式 `reader_thread` 最主要的步驟就是先將讀取資料(這邊是 `shared_config`) 加進 hazard pointer (`line 7`) ，成功之後進行資料讀取的動作 (`line 11`) ，最後將該節點從 hazard pointer 移除 (`line 12`)
接著分析資料加進 hazard pointer 的實作部份，即函式 `load`
```c=
/*
* Load a safe pointer to a shared object. This pointer must be passed to
* `drop` once it is no longer needed. Returns 0 (NULL) on error.
*/
uintptr_t load(domain_t *dom, const uintptr_t *prot_ptr)
{
const uintptr_t nullptr = 0;
while (1) {
uintptr_t val = atomic_load(prot_ptr);
// 判斷 val 所擁有的資料是否已經在 hazard pointer 裡
hp_t *node = list_insert_or_append(&dom->pointers, val);
if (!node)
return 0;
/* Hazard pointer inserted successfully */
if (atomic_load(prot_ptr) == val)
return val;
/*
* This pointer is being retired by another thread - remove this hazard
* pointer and try again. We first try to remove the hazard pointer we
* just used. If someone else used it to drop the same pointer, we walk
* the list.
*/
uintptr_t tmp = val;
if (!atomic_cas(&node->ptr, &tmp, &nullptr))
list_remove(&dom->pointers, val);
}
}
```
首先判斷 `val` 是否已經存在於 hazard pointer 裡 (`line 12`) ，接著判斷 hazard pointer 是否加入成功 (`line 17`) ，如果是就回傳資料的地址 `val` ，如果否就繼續判斷 `val` 是否在 retired list 裡，如果是就從 retired list 移除 (`line 28`)
```c
/* Attempt to find an empty node to store value, otherwise append a new node.
* Returns the node containing the newly added value.
*/
hp_t *list_insert_or_append(hp_t **head, uintptr_t ptr)
{
hp_t *node;
bool need_alloc = true;
LIST_ITER (head, node) {
uintptr_t expected = atomic_load(&node->ptr);
/* atomic_cas: 判斷 node->ptr 和 expected 是否相等
* 若相等則回傳 1，反之則回傳 0
* 如果相同表示該資料已經存在於 hazard pointer 裡，因此不需要創新的空間
*/
if (expected == 0 && atomic_cas(&node->ptr, &expected, &ptr)) {
need_alloc = false;
break;
}
}
if (need_alloc)
node = list_append(head, ptr);
return node;
}
/* Allocate a new node with specified value and append to list */
static hp_t *list_append(hp_t **head, uintptr_t ptr)
{
hp_t *new = calloc(1, sizeof(hp_t));
if (!new)
return NULL;
new->ptr = ptr;
hp_t *old = atomic_load(head);
// 將節點加在 linked list 的頭
do {
new->next = old;
} while (!atomic_cas(head, &old, &new));
return new;
}
```
函式 `list_insert_or_append`
- 變數 `need_alloc` 判斷是否需要建立新的節點
- 對 hazard pointer 的 linked list 進行走訪
- 如果資料已經存在，則不需要新增節點，直接回傳已經存在的節點即可
- 如果不存在則使用函式 `list_append` 新增節點到 hazard pointer 的 linked list 上-
函式 `list_append`
- 將新的節點加在 linked list 頭的位置
最後討論函式 `drop` 的部份
```c
/*
* Drop a safe pointer to a shared object. This pointer (`safe_val`) must have
* come from `load`
*/
void drop(domain_t *dom, uintptr_t safe_val)
{
if (!list_remove(&dom->pointers, safe_val))
__builtin_unreachable();
}
```
函式 `drop` 主要的功能是將 hazard pointer 裡儲存資料 `safe_val` 的節點移除
```c
/* Remove a node from the list with the specified value */
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 如果成立，nullptr 複製到 node->ptr，即移除節點並回傳 true
if (expected == ptr && atomic_cas(&node->ptr, &expected, &nullptr))
return true;
}
return false;
}
```
從函式 `list_remove` 可以得知移除節點的方式是利用巨集函式 `atomic_cas` ，當 `node->ptr` 等於 `expected` 時， `nullptr` 會複製給 `node->ptr`
最後總結 reader thread 的執行步驟
:::success
1. 取得目標讀取資料的 safe pointer
2. 印出讀取資料
3. 將資料從 hazard pointer 中移除
:::
### Writer Thread
以下分析 writer thread 執行的函式
```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();
print_config("updating config", new_config);
swap(config_dom, (uintptr_t *) &shared_config, (uintptr_t) new_config,
0);
print_config("updated config ", new_config);
}
return NULL;
}
```
函式 `writer_thread` 一共執行以下步驟
- 建立新資料的結構
- 將新的資料和舊的資料交換
- 釋放舊的資料
```c
/* Swaps the contents of a shared pointer with a new pointer. The old value will
* be deallocated by calling the `deallocator` function for the domain, provided
* when `domain_new` was called. If `flags` is 0, this function will wait
* until no more references to the old object are held in order to deallocate
* it. If flags is `DEFER_DEALLOC`, the old object will only be deallocated
* if there are already no references to it; otherwise the cleanup will be done
* the next time `cleanup` is called.
*/
void swap(domain_t *dom, uintptr_t *prot_ptr, uintptr_t new_val, int flags)
{
// new_val 寫進 prot_ptr，並回傳舊的 prot_ptr 給 old_obj
const uintptr_t old_obj = atomic_exchange(prot_ptr, new_val);
// 把舊的資料釋放
cleanup_ptr(dom, old_obj, flags);
}
```
函式 `swap` 將新的資料地址 `new_val` 複製到指標 `prot_ptr` 所指到的地址，並且釋放原本的資料 `old_obj`
```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);
}
}
```
函式 `cleanup_ptr` 會根據不同的情況釋放空間
- 直接釋放
- 放進 retired list
- 等待到 reader thread 讀取完畢再釋放
```c
/* Returns 1 if the list currently contains an node with the specified value */
bool list_contains(hp_t **head, uintptr_t ptr)
{
hp_t *node;
LIST_ITER (head, node) {
if (atomic_load(&node->ptr) == ptr)
return true;
}
return false;
}
```
函式 `list_contains` 用來判斷 linked list 裡是否包含儲存資料 `ptr` 的節點
### 可改進之處
Sign in with Wallet
Connect another wallet