---
tags: linux2023
---
# 第 10, 11, 12 週課堂問答簡記
## Chiwawachiwawa
[quiz4](https://hackmd.io/@CWWPPB/H1IyltGW2) 紅黑樹
> 對照 [hamt](https://github.com/mkirchner/hamt), [hamt-bench](https://github.com/mkirchner/hamt-bench)
rbtree 的應用場景: mm, sched (CFS, $3.1)
rb_gen
設計實驗 ==> 檢驗 rbtree 的 locality
規模?
128 op -> 1024 op ->
## chun61205
> [2023q1 第 11 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz11)
### `barrier_cross` 是怎麼執行的？
看到 `barrier_cross`
```c
// test
/* before starting the test, we insert a number of elements in the data
* structure.
* we do this at each thread to avoid the situation where the entire data
* structure resides in the same memory node.
*/
for (int i = 0; i < (int)d->n_add; ++i) {
the_value =
(val_t) my_random(&seeds[0], &seeds[1], &seeds[2]) & rand_max;
/* we make sure the insert was effective (as opposed to just updating an
* existing entry).
*/
// if(push(the_list,the_value))
if (list_insert(the_list, the_value) == 0)
i--;
}
/* Wait on barrier */
barrier_cross(d->barrier);
```
```c
void barrier_cross(barrier_t *b)
{
pthread_mutex_lock(&b->mutex);
b->crossing++; /* One more thread through */
if (b->crossing < b->count) { /* If not all here, wait */
pthread_cond_wait(&b->complete, &b->mutex);
} else {
pthread_cond_broadcast(&b->complete);
b->crossing = 0; /* Reset for next time */
}
pthread_mutex_unlock(&b->mutex);
}
```
看到 `test` 的說明，在實際測試時，會交錯進行插入和刪除，因此需要在測試之前進行測試前插入，以確保在刪除時 list 內部有節點可以刪除。
只要 thread 執行完測試前的插入，就會執行 `barrier_cross` ，並執行 `b->crossing++` 代表多一個 thread ，直到 `b->crossing < b->count` 時，就會值行 `p_thread_cond_broadcase` 將其他 thread 叫起來，代表所有的 thread 都已經做完測試前插入。
1. 這段程式碼的 condition variable 的使用很像 counting semaphore ，差別在於這裡有使用到 broadcase 發送信號給其他 thread 。
2. 另外這個 barrier_cross 在 linux 有相對應的 API 實作，因此可以用 API 來改寫。
這裡我有個問題，就是為什麼在測試前插入時，會需要使用 barrier 來等待所有 thread 的測試前插入都執行完成？
仔細觀察程式碼可以發現，
```c
barrier_init(&barrier, n_threads + 1);
void barrier_init(barrier_t *b, int n)
{
pthread_cond_init(&b->complete, NULL);
pthread_mutex_init(&b->mutex, NULL);
b->count = n;
b->crossing = 0;
}
void barrier_cross(barrier_t *b)
{
pthread_mutex_lock(&b->mutex);
b->crossing++; /* One more thread through */
if (b->crossing < b->count) { /* If not all here, wait */
pthread_cond_wait(&b->complete, &b->mutex);
} else {
pthread_cond_broadcast(&b->complete);
b->crossing = 0; /* Reset for next time */
}
pthread_mutex_unlock(&b->mutex);
}
```
`barrier_init` 會以 `nthreads + 1` 作為參數，並設定 `b->count = n` ，換句話說在 `barrier_cross` 的時候會等待 `pthread_create` 執行的數量再加上 $1$ 個 thread 才會執行 `pthread_cond_broadcast` 。
繼續往下看到 `main` 可以發現
```c
/* Start threads */
barrier_cross(&barrier);
gettimeofday(&start, NULL);
if (duration > 0) {
/* sleep for the duration of the experiment */
nanosleep(&timeout, NULL);
} else {
sigemptyset(&block_set);
sigsuspend(&block_set);
}
/* signal the threads to stop */
*running = 0;
gettimeofday(&end, NULL);
```
在所有 thread 都創建完後，才會再執行 `barrier_cross` 這時進入 `barrier_cross` 數量才會足夠，並把所有的 thread 叫起來開始測試，`main` 也會在這個時候開始計時。因此，使用 barrier 等待所有 thread 的測試前插入都執行完的原因是，為了能夠讓所有 thread 在同一個時間「起跑」。
然而，如此一來又會產生另外一個問題，因為這些 thread 事實上並不會同時執行，而是由 CPU scheduler 決定當前的資源要分給哪個 thread 執行。
### Insert 和 Delete 的執行順序
```c
if (op < read_thresh) { /* do a find operation */
top(the_list);
if (list_insert(the_list, the_value)) {
d->n_insert++;
last = 1;
}
if (list_delete(the_list, the_value)) {
d->n_remove++;
last = -1;
}
d->n_ops++;
```
在插入一定的資料到鏈結串列後，會測試 insert 和 delete 以及「某個其他的動作」 (這裡是 `top(the_list)`) 的運作效能。
實際運作方式如下：
1. 先進行一定數量的 `top(the_list)`
2. `list_insert`
3. `list_delete`
4. 反覆進行步驟 3 和步驟 4
然而，這麼做會有一個問題，因為 insert 和 delete 是交錯進行，會造成能夠測試到的範圍固定的問題。
接下來，我希望能夠設計出一種方法，利用隨機數產生接下來執行的 operation 。
大略想法如下，
1. 隨機數生成出的 operation 和目前鏈結串列中的資料數有關，資料越多，則生成出 delete 的機率越高。
2. 因為當鏈結串列的資料數量為 $0$ 時，不能執行 delete ，因此如果發生這樣的情況生成出 delete 的機率應該要為零。
設計這樣的方法有一個前題，也就是鏈結串列的容量固定。如果能夠事先估算鏈結串列的容量，則代表在接近容量滿的情況下，會再需要插入資料的可能性較低。
#### 參考線性同餘方法 LCG
> [線性同餘方法- 维基百科，自由的百科全书](https://zh.wikipedia.org/zh-tw/%E7%B7%9A%E6%80%A7%E5%90%8C%E9%A4%98%E6%96%B9%E6%B3%95)
$$
N_{j+1}=(A\times N_j B)\ mod\ M
$$
其中
1. $N_{j+1}$ 和 $N_j$ 分別是下個要產生出的隨機數和當前的隨機數。
2. $A$, $B$, $M$ 為常數
1. $B$, $M$ 互質
2. $M$ 的所有質因數能夠整除 $A-1$
3. 若 $M$ 是 $4$ 的倍數，則 $A-1$ 也是
4. $A$, $B$, $N_0$ 都小於 $M$
5. $A$, $B$ 屬於正整數
事實上， glibc 的 `rand` 正是使用此方法來實作，其中，
1. $A=1103515245$
2. $B=12345$
3. $M=2^{31}$
#### 設計 operation 生成函式
### barrier 的改寫
## fennecJ
### `uintptr_t` 是從什麼型態的衍生型態
### 為何需要使用 (`uintptr_t`) 轉型
在 `try_flag` 這個函式中，第 31 行的操作如下：
```c
const uintptr_t new_val = (uintptr_t) n | F_FLAG;
```
為何需要在 n 前面加上 `(uintptr_t)`，如果不加的話會有什麼問題？
> 會有 warning ?
好，我們把它拿掉直接編譯看看
```bash
...
error: invalid operands to binary | (have ‘struct nblist_node *’ and ‘int’)
```
這是因為 C 語言中的 bitwise 運算只能給整數型態使用，而 n 不是整數型態，所以會出錯。
### list_search 的用途是找兩個連續的相鄰節點，這件事為何重要
> 我想是為了確保它 insert 時不會讓資料出錯...?
你有看過 [並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree) 這篇文章了嗎？
> 還沒。
沒關係，那我們現在來看：
現在有一個鏈結串列，我要把 10 移走，把 20 插進來，如果先發生 remove 才發生 insert 結果就會出錯：
> 所以找兩個相鄰節點目的就是找出可能發生這種錯誤的地方？
沒錯，在程式中我們會用 F_FLAG 和 F_MARK 來標出即將被移除的節點和已經被移除的節點。這裡有一件值得注意的事情，看到 `list_delete` 這個函式，你有在裡面看到任何釋放記憶體的程式碼嗎？
> 沒有。
對，這個函式真正做的事情只有更新該節點的 flag ，而真正移除節點的操作則是在
## mimalloc
[include/mimalloc/internal.h](https://github.com/microsoft/mimalloc/blob/master/include/mimalloc/internal.h)
> Overflow detecting multiply
mmap(2)
> If addr is NULL, then the kernel chooses the (page-aligned) address at which to create the mapping; this is the most portable method of creating a new mapping.
## Korin777
```c
struct page_header {
size_t pages;
size_t page_size;
char page_data[]; // the rest of the page(s) of memory
};
```
```c
struct page_header {
size_t pages;
size_t page_size;
char *page_data; // the rest of the page(s) of memory
};
```
> 為何將 `struct page_header` 的 `page_data` 改為 `char *page_data` 會引發錯誤 => a.out: test.c:138: test_alloc_small: Assertion `result == TEST_SUCCESS' failed.`
> [name= fennecJ]
是不是和 [Flexible array members](https://www.ibm.com/docs/en/i/7.2?topic=declarations-flexible-array-members) 有關
在 `simple_malloc` 我們要回傳記憶體地址給使用者，若將 `page_data[]` 改為 `*page_data`，此時 `result->page_data` 會是記憶體地址中的值
* 當 `page_data` 為 `page_data[]` 此時 `result->page_data` 相當於 `&result->page_data[0]`
* 當 `page_data` 為 `*page_data` 此時 `result->page_data` 相當於 `result->page_data[0]`
因此把 `page_data[]` 改為 `*page_data` 就必須將所有 `result->page_data` 改為 `&result->page_data` 才會是我們要的記憶體地址，就能避免上述錯誤，這時會發現在 `free` 產生錯誤
用 `sizeof` 去看上面兩個結構體所佔的空間，可以發現 `page_data[]` 空間並沒有被算進去，所以 `void_to_page_header` 可以直接減去結構體大小來獲取 `page_header` ， 也因此當我們將 `page_data[]` 改為 `*page_data` ， 就會額外去扣掉 `*page_data` 所佔的空間，可以在 `simple_free_internal` 補回多扣掉的空間來解決這個問題
## YSRossi
> [alloc.c](https://gist.github.com/jserv/6ba3bacbbde6ccbf1f0a2b26f00b92a3) 目前的 `alloc` 實作能否在多執行緒的環境運作？
不行，因為沒有保護
> 哪些部份需要被保護？
第 15 行之前都是區域變數，不需要保護。[mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 為 `MT-Safe`，因此也不需要保護。應該保護的地方為第 23~24 行，也就是更新 page header 資訊的地方。
```c=
static struct page_header *alloc_internal(size_t size)
{
if (!size)
return NULL;
/* size in bytes of a page of memory */
size_t page_size = get_page_size();
/* size in bytes that needs to be allocated */
size_t size_with_header = size + sizeof(AAAA);
/* number of pages to allocate */
/* TODO: fix case where size_with_header == page_size */
size_t pages = size_with_header / page_size + BBBB;
size_t mmap_size = pages * page_size;
void *ptr = mmap(0, mmap_size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (ptr == MAP_FAILED)
return NULL;
struct page_header *page = ptr;
/* copy values to page header */
page->pages = pages;
page->page_size = page_size;
return page;
}
```
:::info
我仔細思考這一題，我覺得這題不必特別去保護資料就可以在多執行緒運作。
`realloc` 和 `free` 以功能來說，在傳入指標相同的狀況下一定不可能在二個以上執行緒運作。因為一旦一個執行緒為先進行 `free` ，另一個執行緒在傳入相同指標下執行 `free` 就變成 double-free ， `realloc` 重新配置空間可能會改變指標，故一個執行緒成功，另一個執行緒就會對無效的指標進行 `realloc` 。故考慮多執行緒的狀況下，應只需要考慮 `realloc` 和 `free` 在不同指標的情況下同時執行的狀況。
老師在檢討時提到的 `alloc_internal` 函式來說，在多執行緒同時執行時，`mmap` 同時被執行，但回傳的指標應會不同。故下面的幾行指派 `struct page_header` 裡的 `pages` 和 `page_size` 部份應不會造成問題，不需要保護。
不過老師有提到，若加入 free list 來充份利用空間，而不是每此配置只能以 page 為單位來配置空間，維護 free list 就需要特別保護。
> [name= yanjiew1]
:::
> 如果為了使用較小的空間而配置一個 page，這樣很浪費資源，我們可以配置一個 page 重複使用這個空間，那你會用什麼較不複雜的資料結構來管理？
雖然使用單向鏈結串列較省空間，但通常會使用雙向 linked list，相較於單向鏈結串列有較快的搜尋速度。
我們需要搜尋 free list 尋找符合請求的空間，所以搜尋複雜度為一個考量點。選擇使用 red-black tree 來管理 free list ，雖然搜尋速度不是最快的，重點是 worst case 的時間複雜度為 O(log n)。
## [concurrent hashtable](https://hackmd.io/@sysprog/linux2023-quiz12)
- [ ] concurrent hashtable
* deep copy
* 運用 callback 處理數值傳遞和資源釋放
* 呼叫 `sched_yield`
#### `ht_get_list` 的作用
本次程式碼使用 [seperate chaining](https://en.wikipedia.org/wiki/Hash_table#Separate_chaining) 的機制 （示意圖如下）以處理 hash table 中發生 collision 的問題， 其中 `ht_get_list` 的作用如其名稱，將回傳作為 bucket 所使用的 linked list。
#### deep copy 的存在必要是在並行的環境中，避免 dangling pointer
Copy 主要可以分為 shallow copy 和與其相對的 deep copy，其中 shallow copy 並不完全 "複製" 出一個物件，而是複製出一個物件的參照 (如： 指標)。 例如 [python](https://github.com/python/cpython/blob/3.11/Lib/copy.py) 中的 `copy` 作法是創造一個物件並將原物件內含的物件裝入，示意圖如下。
> - A shallow copy constructs a new compound object and then (to the
extent possible) inserts *the same objects* into it that the
original contains.
而 deep copy 相對於 shallow copy，除了複製物件本身之外也會一併複製內含的物件，新物件和就物件可以看成相同屬性的量個獨立個體，示意圖如下。 由於內容物也需要配置記憶體，所消耗資源也比 shallow copy 多上許多。
> - A deep copy constructs a new compound object and then, recursively,
inserts *copies* into it of the objects found in the original.
在 cocurrent 的需求下，物件何時會被哪個執行序進行修改是無法得知的，使用 deep copy 可以避免其他執行序若持有該物件的參照進而在執行過程中產生 dangling pointer。
iterator 在走訪個別元素時，可能會有其他執行緒變更
Sign in with Wallet
Connect another wallet