# 2024q1 Homework1 (lab0)
contributed by < `idoleat` >
## 作業表單中的問題
**問題 2 ：考慮以下程式碼: char s\[64\]; 試問 `s == &s` 是否成立？搭配〈你所不知道的 C 語言：指標篇〉的描述，佐以 C 語言規格來解釋**
```c
#include <stdio.h>
int main(){
char s[64] = "test";
if (s == &s) {
printf("equal!");
} else {
printf("not equal!");
}
return 0;
}
```
若是編譯上面的程式碼，不論是宣告在 global 還是函式中皆會得到警告
```
warning: comparison of distinct pointer types lacks a cast
if(s == &s){
^~
```
首先思考 s 什麼時候會被當成指標？
C11 6.3.2.1 Lvalues, arrays, and function designators 中第三點
> Except when it is the operand of the sizeof operator, the _Alignof operator, or the unary & operator, or is a string literal used to initialize an array, an expression that has type "array of type" is converted to an expression with type "pointer to type" that points to the initial element of the array object and is not an lvalue. If the array object has register storage class, the behavior is undefined.
由此可知左邊的 s 是指向 char array 的第一個元素的指標，右邊的 s 是 array of char，由 unary operator `&` 取址後與左邊的 s 所指之地址相同，`s == &s` 為 `true`
起初在查閱規格書之前猜想如果兩邊的 s 都作為 expression 因此都是指標，則 `s == &s` 是在判斷指標指的地址與指標本身的地址是否一樣，查閱完規格書之後思考那如果是這樣的規格會發生什麼事？若是作為 expression 都解讀為指標，那得到一個指標時就需要再額外判斷此指標究竟是指向一個 object 還是 array of object
由 `s == &s` 延伸思考，編譯器實作上是否可以在宣告 array of type 時額外配置一個指標指向該 array? 如此可以滿足 s 作為 expression 時都是指標，此時的 `s == &s` 則是 `false`
若是以 GDB 觀察：
```c
(gdb) whatis s
type = char [64]
(gdb) whatis &s
type = char (*)[64]
(gdb) explore s
's' is an array of 'char'.
...
...
(gdb) explore &s
'&s' is a pointer to a value of type 'char [64]'
...
...
```
GDB 的解釋方法似乎有太過聰明？或是說 GDB 並沒有把 s 當作 expression? 需要去閱讀 GDB 文件確認一下
## 排序
一個序列是一張全連接圖退化而成的子圖，一張 $|V| = n$ 的全連接圖可以退化成 $n!$ 種不同的序列，排序是從一個子圖演變成另一種子圖，過程中各節點會斷開邊或建立邊。假設邊上有權重，權重為相鄰節點之間的數值差，一個已排序的序列其權重合的絕對值為所有子圖的最小值，並且剛好為首尾節點的數值差。
思考：將子圖視為一種狀態，要如何找出走到已排序狀態的路徑？
目前已知性質：
* 狀態到狀態的路徑不唯一
* 已排序狀態未知
* 排序演算法為找出並執行狀態轉移的方法
* 若已知從 A 狀態 B 狀態所需建立與斷開的邊，直達比起先到中間狀態再到 B 可以少掉一些 overhead
想法一：先接回全連接圖，再逐步斷開邊，直至一個序列。如何挑邊？會不會陷入 local minimum? 需要 heuristic?
## 佇列操作
### q_new()
在建立空佇列時會配置結構體 `queue_context_t` ，並根據需要初始化每個欄位，其中的 list head 即為佇列的 head，但不包括 ID。我不確定 ID 的使用方式，所以稍後會更新它。
### q_insert_head(), q_insert_tail()
如果傳入的 head 是 `NULL` 會回傳 `false` 作為失敗的操作。成功配置且插入的節點會使用 `strdup` 配置新的字串並從傳入的字串複製內容。若字串配置失敗也會回傳 `false` 作為失敗的操作並一併釋放已配置的記憶體。Cppcheck 這時會偵測到函式宣告中的字串沒有被修改到所以需要被標示為 `const`，不過修改 `queue.h` 會造成 commit 時 check sum 失敗並得到不得修改 `queue.h` 的警告，所以我使用 `// cppcheck-suppress constParameterPointer` 暫時抑制了此項檢查。
在佇列的建立與節點插入時若遇到配置失敗皆會導致操作失敗，不過不包含作業系統 over commit 的情況 (TODO: 該怎麼處理 over commit 的狀況？) [vacantron](https://hackmd.io/@vacantron/linux2024-homework1)提示了 Linux kernel 內即有[文件](https://docs.kernel.org/mm/overcommit-accounting.html)描述之，不過他被歸類在 legacy documentation，屬筆記、mailing list 回覆等類型所以無法百分之百仰賴其解釋。但是同時我也發現我對 memory paging 及 mapping 理解不足，需要去閱讀 CS:APP Ch9
> TODO: 設計會發生 over commit 的環境
*持續思考間接指標及更多層間接指標所創造的幻象 (illusion)，如何利用此特性更簡潔統一的操作？*
### q_remove
如果傳入的 head 是 `NULL` 或佇列為空會回傳 `false` 作為失敗的操作。注意 `list_empty` 不檢查 `head` 是否為 `NULL`。節點在此只是斷開連結並回傳指向此節點的指標及複製節點內字串給呼叫者做後續動作。注意 `man strncpy` 中 CAVEATS 段落提到 "The name of these function is confusing" ，該處舉例並說明補上 0 及裁剪超出指定長度字串的行為。對於 bufsize 不大於節點內字串 buffer size 的情況都須補上空字元作為結尾。另外，`list_del` 實質上是 remove
### q_free
走訪每個節點釋放該節點及該節點內成員所指向的記憶體。在迭代器所指的元素直接釋放或是使用 q_remove 逐一釋放都會造成迭代器遺失下一個節點的地址，因此需要保留可以存取下一個節點的途徑，`for_each_safe` 以及 `for_each_entry_safe` 使用額外的指標先行紀錄下一個節點的位址。最後 `queue_context_t` 也要釋放。若 `head` 是 NULL 則視為無效操作。此處的額外宣告的迭代器及 safe 指標若是還會為他處所用記得先設為 NULL 以免 double free
### q_dedup
直覺上是使用 hash table，但是需要考慮到 hash table 會需要使用記憶體，若為了節省記憶體開銷 table size 開很小碰撞機率很高，會逐漸退化為鏈結串列，開太大又使用太多記憶體，這在 Linux kernel 內是不樂見的。不過這邊 dedup 的前提是鏈結串列是已經排序過的，有相同字串內容的結點會相鄰排列。在逐一走訪每個結點時檢查下一個節點是否也一樣內容的字串，若有則移除並釋放當下結點，並標記下一結點為也需要移除與釋放，以此讓有相同字串內容的結點最後一個在檢查到與下一個結點有不同內容的字串時還是會自我移除與釋放。本來想用記憶體位置對齊的特性，將標記放在記憶體位置最低位元，但仍一直觸發 segmentation fault ，在找出原因之前先以 bool flag 標記
### q_sort
實作方式為 bottom-up merge sort，將子鏈結串列成對合併，其長度為 2 的冪，從零次方開始。每次合併完所有成對的鏈結串列時，子鏈結串列長度都會加倍，直到沒有 `list head` 可以合併為止。
當鏈結串列長度不是 2 的冪時，有兩種情況
1. 結束合併長度相等的子鏈結串列後剩餘的長度比單一子鏈結串列長度還長，導致合併不等長的子鏈結串列
2. 結束合併長度相等的子鏈結串列後剩餘的長度比單一子鏈結串列長度還短，導致無法進行合併，會留到下一輪合併，此時也是為已排序好狀態
合併的方法為將右子鏈結串列取出作為一個儲存於 stack 上的新鏈結串列，並依據 `strcmp` 的結果將節點逐一加回左子鏈結串列。注意要維持 stable sort 的特性，比較結果相同的情況下原本在右子鏈結串列的節點要維持放在右邊。取右子鏈結串列的原因為剩餘的節點都在右側，如此可以取較少數量，而非左側完整長度的子鏈結串列。當然要取左子鏈結串列也是可行的
使用此將右子鏈結串列取出作為一個新鏈結串列來合併的原因是要善用 list API 來達到更好的 semantic 也比較好維護，雖然建立新鏈結串列又再插入有很多多餘的指標內容修改，但是能避免為了省去那些指標內容修改而帶來的更多的特殊情況。例如以下失敗的嘗試，由於長度太長這邊用 spoiler 折疊，這還不包括一些還沒處理的特殊狀況，即便善用間接指標，也還是相當冗長不易讀。在分析上，合併兩個子鏈結串列的行為即為建立（長度 -1） 個邊，不是跨串列就是同串列，雖然看似簡單但是在指標內容修改上很容易寫到不易確認行為。使用 list API 至少是透過已知安全的操作來建構，其整個操作也會是安全的
:::spoiler bad `q_sort`
```c
void q_sort(struct list_head *head, bool descend)
{
int size = q_size(head), l = 1, r = 1;
struct list_head *L = head->next, *R = head->next;
// i is the length of sub-list to merge
// j is j-th time of merge in current iteration
for (int i = 1; i < size; i <<= 1) {
for (int k = 0; k < i; k++) {
R = R->next;
}
for (int j = 0; i * j * 2 - size < i; j++) {
while (l < i || r < i) {
if ((descend * 2 - 1) *
strcmp(list_entry(L, element_t, list)->value,
list_entry(R, element_t, list)->value) >
0) {
R->prev = L;
L = L->next;
L->prev->next = R;
L->prev = R;
R = R->next;
L->prev = L;
// R->prev = NULL
r += 1;
if(r == i)
l = i;
} else {
L = L->next;
l += 1;
if(l == i){
L->next = R;
R->prev = L;
r = i;
}
}
if (R->next == head)
r = i;
}
R = R->next;
L = L->next;
l = 1;
r = 1;
}
L = head->next;
R = head->next;
}
}
```
:::
<br>值得提到的是，目前測試通過的實作中 `bool descend`，是以 `descend * 2 - 1` 轉換為不是 1 就是 -1 的整數，與 `strcmp` 回傳值相乘，這樣遞增遞減都使用同一段程式碼不用多寫
接下來要研究 Linux 核心鏈結串列的實作機制，及其高效的排序實作，並再多加實作 [作業二](https://hackmd.io/@idoleat/linux2024-homework2) 中的排序方法還有我在重新認識 quick sort 時提出來的新嘗試 `vbsort` ，並在修正 qtest 及其測試方法後進行效能比較
## 排序實作研究與測試
* 移植 `lib/list_sort.c`：除了複製貼上函式以外，`u8` 在 `lib/type.h` 中沒有定義 `__BIT_TYPES_DEFINED__` 的情況為 `u_int8_t`，其餘為 `uint8_t`。前者為相容不同 C 函式庫而定（待考證），後者為 C 標準函式庫中的型別，在此選用 `uint8_c`。`likely` 與 `unlikely` 的巨集也需要一併移植，另外我注意到如果 [`include/linux/compiler.h`](https://github.com/torvalds/linux/blob/4f55aa85a8746e5e255c46c98c031e143605e2a0/include/linux/compiler.h) 有開啟 `CONFIG_TRACE_BRANCH_PROFILING` 的話，會搭配 `__branch_check__` 巨集來 profile 分之預測。其中 profiling 標的除了預設的 none 之外分為 annotated 及 all branches，`likely` 及 `unlikely` 即屬前者。可在 [`kernel/trace/Kconfig`](https://github.com/torvalds/linux/blob/4f55aa85a8746e5e255c46c98c031e143605e2a0/kernel/trace/Kconfig#L564) 見到使用說明及注意事項，以及更多的 profiling 選項。。[Kernel Build System](https://docs.kernel.org/kbuild/index.html) 文件紀錄了如何設置^(?)^ kernel，之前沒耐心只會用 allconfig 或是發行版的預設 config。`compiler.h` 也提供了以 `__notrace` 為後綴的巨集來躲避 tracing，在 6.8.1 中只在 `include/linux/jump_label.h` 見其使用
* 躲避 tracing 的理由是為了減少 tracepoint 的 overhead，即便 tracing 是被關閉的情況下。tracepoint 會使用分支 (or jumps) 條件性的檢查全域變數，而這會佔用快取，在 tracepoint 越來越多的情況下會造成負擔。在極度注重效能的情況下可以使用。詳見 [Static keys 說明文件](https://docs.kernel.org/staging/static-keys.html)。[XFS online FSCK design](https://docs.kernel.org/filesystems/xfs/xfs-online-fsck-design.html) 中有提到 static keys 的使用，由於對檔案系統認知不足無法理解其用法，但是竟然見到 [eventual consistency](https://docs.kernel.org/filesystems/xfs/xfs-online-fsck-design.html?highlight=static+keys#eventual-consistency-vs-online-fsck) 的身影！（雖然他造成了一些問題）
* > If the merge is highly unbalanced (e.g. the input is already sorted), this loop may run many iterations. Continue callbacks to the client even though no element comparison is needed, so the client's cmp() routine can invoke cond_resched() periodically.
if non-preemptive....
* 以下簡記對於 commit 中提及的三篇論文的想法，詳細紀錄於 [Sorting](/b49-W8u0Q_a8rNcMgxHEdA)
* Queue Mergesort (1993)
* 本篇以 merge tree 解釋了任一種 merge sort 過程
* 以形式而言相當簡單易懂，作者沒有說明是自己想出來的還是受 Huffman code 啟發
* 依據我的觀察，合併長度不等的串列會影響樹的平衡，兩串列長度差越大樹就會歪斜 (skew) 的越嚴重，造成在 worst case 下的比較次數變多。Insertion sort 是最歪斜的例子，因此在 worst case 下時間複雜度變成了 $O(n^2)$。Insertion sort 的 merge 過程以本篇 Queue 的方法可以解釋為：
`Q.put(merge(Q.get_head(), Q.get_tail()))`
* 從以上觀點，我寫的 bottom-up merge sort 就是左傾的樹
* 這邊 worst case 指的是沒有一個 list 提早完成可以讓另一個 list 直接接到最後的情況，因此比較次數是兩個 list 長度相加再減一。顯然作者假設讀者有先備知識而未多做說明，但是我覺得稍微提及一下會比較好避免大家對 wortst case 的認知有落差（自身經驗：會議或期刊的審稿委員也比較好抓到論點基礎，畢竟他們都看很快，若有誤也可以讓委員直接點出來）
* 對於非 worst case，既然是合併兩個已排序的串列，是否可以以二分搜尋找插入點而非逐一比較？
* 本篇定義 optimal merge sort 為 worst case 下比較次數比其他 merge sort 都少。Huffman code 已經被發現權重合不一定為最佳，那我可以 dis-proof Queue Mergesort 的 optimality (紀錄於 [Sorting](/b49-W8u0Q_a8rNcMgxHEdA)，嘗試使用 lean proof assitance 重新建構並驗證)，並參照下一篇
* top down 和 queue 都是 optimal，但兩者是不同的演算法，顯然不能只關心 worst case
* The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules (1998)
* 為什麼要找 2 的冪？因為可形成平衡的完整二元樹。那為什麼要找最接近 n/2 的 2 的冪？因為要平衡左右子樹
* 扣掉 2 的冪的子樹的另一半，要繼續找最接近 n/2 的 2 的冪。這個貪婪法要證明最後結果一定 optimal，就必須證明每次「找最接近 n/2 的 2 的冪」這個動作為產出的左右兩子樹為 optimal (平衡)
* average case:
* Bottom-Up Mergesort - a Detailed Analysis (1995)
* 課堂問答紀錄中的分析
* DFS (vs 我的 BFS stackless 寫法)
* cache
* count
### 測試方法
測試指標為
* 執行時間：注意影響時間測量的因素
* Cycle count：關於為何不使用 instruction count 是因為現代處理器一個指令所花費的 cycle 數量不固定，無法依據一個指令會花多少 Cycle 計算總 Cycle 數量 ^(?待考證)^
* cache miss rate：作為可否針對快取再做改善的指示
* Memory usage：運用 Valgrind 中的 Massif
* 比較次數
測試資料
* 不同排序亂度：實作可控制亂度的 shuffle Algorithm
* 不同資料分佈：乍看之下不影響？需要研讀 entropy 並測試
* 不同大小：檢視該實做是否如同 big O 所定義的在「足夠大的 $n$」之後執行時間以該演算法的時間複雜度成長，並且找出 $n$ 是多少。觀察在 $n$ 不足夠大的場景適合哪種排序方法，並思考如何針對場景切換實做如同 glibc，如找出在快排序完的情況下應該就要再排一下就好而不是整個重排 (be adaptive)
* 若是很常需要排序近乎完成排序的資料，又不要求插入與刪除一定要常數時間，則可以考慮使用紅黑樹。換言之，鍊結串列的排序適用於排序沒那麼頻繁的情況
修正 `dudect.c`
## 間接堆疊
假設現有一長度為 $n$ 的雙向環狀鏈結串列，定義一階間接指標為序列 $S_1 = (a_0, a_1, ..., a_{n-1})$，序列內成員 $a_i$ 型別皆為 `struct list_head *`，二階間接指標為序列 $S_2 = (a_0, a_1, ..., a_{n-1})$，序列內成員 $a_i$ 型別皆為 `struct list_head **`，$k$ 階間接指標為序列 $S_k$ 以此類推，$S_0$ 為原雙向環狀鏈結串列。$S_k$ 經由 $F$ 動作映射^(?)^(map) 為 $S_{k+1}$ ($k>0$)，$S_{k+1}$ 經由 $P^{'}$ 動作投影 (project) 回 $S_k$，可視為套用 $F$ 動作之變更，二次投影可記為 $P^{''}$ 或 $P^2$，以此類推，至多投影回 $S_0$。
### 以 q_swap 為例
對 $(0, 1, 2, 3, 4, 5, 6, 7,...)$ 成員 XOR 1 會得到 $(1, 0, 3, 2, 5, 4, 7, 6,...)$，$F$ 可定義為
$$
(a_i)_{i = 1}^{n} = \&S_{k-1}(i\space xor\space1)
$$
其中 $S_k(i)$ 表示 $k$ 階間接指標為序列中第 $i$ 成員，$\&$ 則表示取址 (address of)，假使目前為 $S_0$ 映射到 $S_1$ 可實作為
```c
struct list_head **q_swap(struct list_head *head)
{
int size = q_size(head), i = 0;
struct list_head **S = malloc(sizeof(struct list_head *) * size);
struct list_head *buf[2], *node;
list_for_each (node, head){
if ((i & 1U) == 0){
buf[0] = node;
buf[1] = node->next;
}
S[i] = buf[(i ^ 1U) & 1U]; // $S_{k-1}(i xor 1)$
i += 1;
}
return S;
}
```
不過我們無法直接更改函式簽名，所以將真正的 `q_swap()` 作為此實作方法（將名稱改為 `__q_swap`）的 driver code
對於一般投影回非 $S_0$ 的前一階的作法為逐一 dereference 指標覆蓋原有的前一階指標，例如
```c
bool __project(struct list_head ****S3, struct list_head ***S2)
{
int S3_size = sizeof(S3)/sizeof(S3[0]);
if (S3_size > sizeof(S2)/sizeof(S2[0])){
/* reallocaate S2 to fit S3 size
* return false if fail
*/
}
while (S3_size--){
// potential race condition
S2[S3_size - 1] = *(S3[S3_size - 1]);
}
return true;
}
```
延續假設為 $S_1$ 與 $S_0$ 之間的操作，$P^{'}$ 投影的方法，此處重新連結串列是投影回 $S_0$ 才需要做的操作
```c
/* @S1: first order inderect pointer sequence
* @head: head of the queue
* Return true if success, false if head is null
*/
bool q_project(struct list_head **S1, struct list_head *head)
{
if(!head)
return false;
int size = q_size(head);
head->next = S1[0];
head->prev = S1[size - 1];
S1[0]->next = S1[1];
S1[0]->prev = head;
S1[size - 1]->next = head;
S1[size - 1]->prev = S1[size - 2];
for(int i = 1; i < size - 1; i++){
S1[i]->next = S1[i+1];
S1[i]->prev = S1[i-1];
}
return true;
}
```
注意 `__q_swap` 配置的 `S1` 需要被釋放，再上個程式碼片段中的 `S3` 也是，至於是在投影的時候就釋放還是在 driver code 明確 (explicit) 釋放需要多使用間接堆疊才能知道 best practice 是什麼。由於 `qtest.c` 中`do_swap` 將 `noalloc_mode` 設為 `true` 所以此實作無法使用
可以更改為只使用 stack 上的空間，不過缺點就是需要將要執行的操作連續做完，stack frame 一個一個往上疊，然後在結束 stack frame 時再一個一個投影回來（或一次投影回 $S_0$）
### 泛化 (generalize)
推廣此實作至 $k$ 與 $k+1$，需要藉由 macro 來生成投影函式定義及宣告中對應的指標層級
```c
#define _0_PTR *
#define _1_PTR **
#define _2_PTR ****
#define _3_PTR ********
#define _4_PTR ****************
#define _5_PTR ********************************
#define _6_PTR ****************************************************************
#define _7_INDERECT ********************************************************************************************************************************
#define __PROJECT(src, dst, k0, k1, k2, k3, k4, k5, k6, k7) \
struct list_head ??##??
#define PROJECT(src, dst, k) __PROJECT(src, dst, k & 1U, (k >> 1) & 1U, (k >> 2) & 1U, (k >> 3) & 1U, (k >> 4) & 1U, (k >> 5) & 1U, (k >> 6) & 1U, (k >> 7) & 1U)
```
以上是失敗的 C macro 嘗試。此處意圖是解析指定的 k ，依據各 bit 的狀況取對應的 `*` 數量組成長度為 k 的連續 `*`
嘗試使用 [GNU M4 macro processor](https://www.gnu.org/software/m4/manual/m4.html) 撰寫
### 改寫插入及刪除
向左對齊？向右對齊？
### 部份映射
more cache friendly
### 漸近式^(?)^投影(Incremental projection)
### 以 q_sort 為例
$F$ 可定義為
> 思考中
### 間接堆疊的優缺點
#### 優點
- [ ] Enable concurrent list
* reader-reader: 對於任意沒有在修改的 $S_k$ ，reader 並不修改要讀取的內容所以不互相影響
* writer-writer: race condition 發生於兩個 writer 同時想要對同一個共享資源做出修改，映射將修改分離至不同的記憶體區塊從而避免了兩個 writer 間有共享資源。此時產生的 concurrent write 若有衝突就必須定出順序，參見下方
* writer-reader: writer 在修改其他間接指標序列時不影響 reader 讀取。reader 預期拿到 list head 就可以走訪 list 讀取資料，關鍵在於 writer 要什麼時候將修改投影回 $S_0$？
方案一、reader 允許讀取 stale data，投影時機交由投影排程器
方案二、額外維護間接指標序列狀態，讀取時觸發投影
承襲方案一之排程策略：
* 時機：能投影就投影、
* 排程標的為間接堆疊末端的操作者
* 投影兩個基於同個 $S_k$ 的分支時 (concurrent write) ，對於不衝突者不要求順序投影完即合併完修改 (commutative)，有衝突者依據已定立好之優先度決定投影順序。允許分支而不強制寫入需要透過同步機制保護來維持順序的原因為並不是所有寫入都衝突（例如從頭插入與從尾端插入）。對於有衝突者可以更進一步在接指標序列設置映射 handler，不衝突的事件則允許分支，會衝突的事件（例如 swap 及 sort），則不允許分支回傳失敗操作，這樣就不用訂立優先度
設計的精神上是盡可能讓所有不衝突事件同時發生，以提高平行度，僅協調衝突事件。使用間接堆疊可簡化操作，不須混雜同步上的邏輯，映射歸映射，協調歸協調
- [ ] 統一的操作方式（品味）
所有操作皆透過單一映射函式修改
#### 缺點
* 記憶體開銷
* not cache friendly, 不管是哪一階的指標都沒辦法一直待在 cache 裡面被重複利用
* 頻繁記憶體配置
* 改使用預先配置好的空間？memory pool?
* 投影是瓶頸：投影時若有讀寫可能會得到一半舊一半新的資料，因而無法保證與先前已完成之讀寫事件的順序，所以投影時不允許讀寫操作，可以以 Big List Lock 描述之，惟讀取若是與更上層的投影錯開可同時進行。不過如果可以再更細部的掌握正在投影及讀寫位置，就有辦法擺脫 Big List Lock
* 綜合以上描述之所有機制，協調上的設計仰賴許多 fine-grained control 而繁雜
## 自動化測試
### Valgrind
about debuginfod
### qtest 錯誤修正及改進
* Wrong interpretation on commends with leading spaces
### 不同的 PRNG 的實作
有意圖的從已排好的序列打亂是不是就可以控制亂數的分佈和 entropy? 每一步打亂都可以算出 entropy 加多少
Two Choices
### select
## 論文閱讀
## 教材疑問
* [macro 與 function call 的執行時間差異](https://hackmd.io/@sysprog/c-preprocessor#%E6%87%89%E7%94%A8-Linked-List-%E7%9A%84%E5%90%84%E5%BC%8F%E8%AE%8A%E7%A8%AE)：macro 與 inline function 的差異？
設計實驗比較
* typedef is for semantic? and type checking?
> Units of measure is sort of related in that we usually prefer the unit tags have no runtime cost (e.g. boxing), but different in that achieving that cost savings needs significant compile-time machinery
> e.g. multiplying 2^kg * 1.5^m is valid and produces 3^kg.m but 2^kg + 1.5^m is an error
> The exponents need to live in type space, but the coefficients can be in term space
> [name=David Chrisnall]
* [[RFC PATCH 0/2] add list iterate & delete macros](https://lore.kernel.org/all/20231020102901.3354273-1-mszeredi@redhat.com/T/#m1dc37efe24c96ed40844653aa7d99a9cc321d7a8) (2023-10-20 10:28 Miklos Szeredi)
* 此 RFC patch 針對常見的「移除元素、對該元素做一些事、重複動作直到鏈結串列是空的」操作提出一個新的巨集，相比 `while` 的寫法省略兩行，閱讀上也直觀的就是一個逐一走訪的 statement
* 第一個 patch 為兩個新的巨集的實作，此處做的動作是 `remove` 但是用途說明的註解標題寫 `remove` 描述寫 `delete`，後者為誤用
* 我的想法是已經有 `list_for_each_entry_safe` 可以用了，裡面再接著 `list_del` 也是足夠 semantic，不過既然都要 `remove` 直到串列為空那就不用 `list_del` 維持 `prev` 的正確？
* 第二個 patch 將現有的 `while` 寫法都換成新提出的巨集，數量相當驚人，大家不知道有 `list_for_each_entry_safe` 可以用嗎？
* 不確定 Linus 直接回覆 patch 常不常見，他在這邊提出兩個疑慮
* 他希望新的鏈結串列走訪不需要再先行宣告一個 iterator 傳入而是利用現代 C 的方式在迴圈中直接宣告變數（雖然他理解到有人這麼做是為了可以中間跳出去而仍保有走訪的紀錄）
* 對於無論如何都要移除所有東西這件事，比較好的作法是建立一個新的 private list head 然後用 `list_splice_init` 把東西搬過去，而避免會需要在整個 while loop 中都拿著 lock（這邊我的理解是既然都要整個清空了就不要還拿著 lock 卡住別人，把東西搬到旁邊去做）。對於中途可能會跳出去做其他事情可以用 `list_for_each_entry_safe` 並在迴圈的**最後**做 `list_del`, Hmm? （這個我不懂為什麼要強調放最後）
* A pointer to a pointer to a pointer to a type (*type* \*\*\*ptr) would be used in
* 不論是從 C 語言還是組合語言觀察，都不見直接操作快取的動作，只有操作記憶體位置的操作，為什麼不能查看當下 cache 內的狀態？如此可以以查看的結果為依據決定要不要續使用快取內的資料，不須臆測 (Cache flush 是如何達成？一個指令？)。個人猜測就算可以查看 cache 的狀態，看完到執行下一個指令的當下可能狀態又不一樣，例如隔壁 CPU 會發 IPI 來 invalid cache，那查 cache 就完全沒有意義因為不可用，除非要阻止別人更動 cache 但是那又會造成嚴重 stall
* 3/14 的課程提到 `likely` 與 `unlikely` 的使用，我有個疑問是那如果開發者誤用而導致該在前面的 code block 被放在後面怎麼辦？ 我們需要有測試來指出這些分支預測與 L1i cache 命中的情形。而 PGO 提供另一種改善方式，依據實際執行的結果來調整分支，參見 [每位程式開發者都該有的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/) [Ch 6.2.2](https://sysprog21.github.io/cpumemory-zhtw/what-programmers-can-do/cache-access/optimizing-level-1-instruction-cache-access.html) 與 [Ch 7.4](https://sysprog21.github.io/cpumemory-zhtw/memory-performance-tools/improving-branch-prediction.html) 的說明。不過需要注意使用 PGO 執行的代表工作若無法反應程式碼的常見使用情形則無法發揮最佳化，不如手動指定 `likely` 與 `unlikely` 並多測試
:::warning
參見 LWN [Likely unlikely()s](https://lwn.net/Articles/420019/)，提到 Steven Rostedt 在 2010 年對 Linux 核心的統計數據，呈現若干誤用 `unlikely` 的狀況：
> "correct a total of 1909540379 times and incorrect 1270533123 times, with a 39% being incorrect"
由於現代處理器應用場景多元，當初 Linux 核心開發者針對特定的工作負載而指定的 `unlikely` 可能不適用新的情境，另外，現在處理器的分支預測能力也相當強，就算不用特別提示編譯器最佳化，往往性能也相當好，因此 `unlikely` 僅該在開發者相當確定時使用。
延伸閱讀: [How branches influence the performance of your code and what can you do about it?](https://johnysswlab.com/how-branches-influence-the-performance-of-your-code-and-what-can-you-do-about-it/)
:::
* 在與朋友 Eric2011 討論到 magic number 時我用 `git blame` 查閱了定義 `LIST_POISON` 的 `include/linux/poison.h`（我們想知道這些奇怪的數字到底是怎麼決定的，有些很有梗有些很隨便），發現了 `RED_INACTIVE` 及 `RED_ACTIVE` 是針對 slab 定義的。slab 已經於 6.5.0 正式[淘汰並移除大量程式碼](https://www.phoronix.com/news/Linux-6.8-Dropping-SLAB)，目前 6.8.1 中也沒有見到其使用，而 slub 中使用的是以 `SLUB_` 為前綴的毒藥。看來這兩個是可以移除的巨集？
* [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
* [Unix fork 誕生](https://hackmd.io/@sysprog/unix-fork-exec#Unix-fork-%E7%9A%84%E8%AA%95%E7%94%9F) 中引用到：
> a newly recreated shell had to close all its open files both to get rid of any open files left by the command just executed and to rescind previous IO redirection
* （續上）command 不會 close files and rescind IO redirection 嗎？
* [Unix 經典的 fork-exec-exit-wait 組合](https://hackmd.io/@sysprog/unix-fork-exec#Unix-%E7%B6%93%E5%85%B8%E7%9A%84-fork-exec-exit-wait-%E7%B5%84%E5%90%88)：是的，不會。當 fork 引入 Unix 後，exit 的語意才發生巨大的改變
* [Unix fork 誕生](https://hackmd.io/@sysprog/unix-fork-exec#Unix-fork-%E7%9A%84%E8%AA%95%E7%94%9F) 中用 graphviz 視覺化 `pstree` 的結果的圖中，直線是 fork ，那橫線是指什麼？
* 使用以下程式碼搭配 linenoise 可實做一個簡陋的 shell (`execve` 甚至可以在讀取到文字檔的時候切換到 interpreter mode!)
```c
char *args[] = {NULL};
char *envp[] = {NULL};
char path[100] = "/usr/bin/";
pid_t pid = fork();
if (pid == -1) {
printf("failed to fork\n");
} else if (pid > 0) {
int status;
waitpid(pid, &status, 0);
} else {
execve(strcat(path, line), args, envp);
fprintf(stderr, "Failed to execute '%s', %s\n", line, strerror(errno));
_exit(EXIT_FAILURE);
}
```
```
shell>> ls
LICENSE Makefile README.markdown ccnshell ccnshell.c example.c history.txt linenoise.c linenoise.h linenoise_example shell_script.sh
shell>> pwd
/home/idoleat/Documents/linenoise
shell>> ../../home/idoleat/Documents/shell_script.sh
echo yoooo
```
這段程式碼在 `execve()` 前皆於 parent 與 child process 中執行，所以在有成功 `fork()` 的情況下 parent 會進入第一個 else if 進行等待，child 會進入 else 載入對應的檔案。`execve` 會[載入](https://lwn.net/Articles/631631/) elf 覆蓋現有的記憶體空間，如果不 fork 的話會直接覆蓋掉 process 當下的執行狀態不會再跳回來 shell，一如 Ken Unix 中的覆蓋<br>
可以再嘗試如果改用 `clone()` 建立行程會需要做出什麼調整，`execve` 也可以改用 glibc 包裝好的 `exec`，或是使用 [`posix_spawnp()`](https://www.man7.org/linux/man-pages/man3/posix_spawn.3.html) 一次做完 `fork`, `exec` 與 housekeeping steps (?)<br>
linenoise 有同步以及非同步兩種模式，`select` 的使用
* 思考為什麼 `lib/list_sort.c` 不實作為 concurrent merge sort
* TODO: 不要只是思考，實做出來就知道具體細節，便得以推斷原因
* Counter-Strike 2 的工作坊工具（製作客製化造型與自製地圖的工具），苦於沒有 Linux 版本而需要使用 proton 執行，但是必須加上玩家提供的額外調整 `sysctl -w vm.max_map_count=262144` 才不會 crash，而 [Arch Linux 也將調大預設 `vm.max_map_count` 以增進這類應用場景的體驗](https://www.phoronix.com/news/Arch-Linux-vm.max_map_count)
* **如此調整會造成什麼影響？** 想到這我無法做出完整解釋，顯然對記憶體管理認知不足，需要再去加強。SUSE 倒是有針對此問題[做出回答](https://www.suse.com/support/kb/doc/?id=000016692)
* > since there will be more elements in the VM red-black tree, all operations on the VMA will take longer. The slow-down of most operations is logarithmic, e.g. further mmap's, munmap's et al. as well as handling page faults (both major and minor). Some operations will slow down linearly, e.g. copying the VMAs when a new process is forked.
* 對於不知道 Virtual memory areas (VMAs) 是使用紅黑樹來紀錄追蹤頁面變更深感慚愧，查閱 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)及 [kernel 文件](https://www.kernel.org/doc/html/latest/core-api/rbtree.html)得知除了排程器及記憶體管理，還有很多地方使用到紅黑樹而我仍對紅黑樹不了解，需要趕上課程進度因為這些都是必要的基礎
* 可以驗證 SUSE 的說法是否正確，以及是否還有其他影響？
### string and stack
根據 [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E9%87%8D%E6%96%B0%E6%8E%A2%E8%A8%8E%E3%80%8C%E5%AD%97%E4%B8%B2%E3%80%8D)
* 已知 string literal 會儲存於 .rodata (gcc)
* 已知 `char s[] = "hello";` gcc 會把 string literal 複製到 stack
* 那 `char s[64] = "hello";` gcc 會放多長的字串在 .rodata? 64 byte? 6 byte?
對於以上三點進行實驗：
以下 `func()` 皆在於 `main()` 中呼叫
```c
int main()
{
func();
}
```
ELF 格式皆為 `elf64-x86-64`
**1. `char *p = "hello"`**
```c
void func()
{
char *p = "hello";
printf("%s", p);
}
```
```
$ gcc -c str.c
$ objdump -D str.o
Disassembly of section .text:
0000000000000000 <func>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 10 sub $0x10,%rsp
8: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # f <func+0xf>
f: 48 89 45 f8 mov %rax,-0x8(%rbp)
13: 48 8b 45 f8 mov -0x8(%rbp),%rax
17: 48 89 c6 mov %rax,%rsi
1a: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # 21 <func+0x21>
21: 48 89 c7 mov %rax,%rdi
24: b8 00 00 00 00 mov $0x0,%eax
29: e8 00 00 00 00 call 2e <func+0x2e>
2e: 90 nop
2f: c9 leave
30: c3 ret
0000000000000031 <main>:
31: 55 push %rbp
32: 48 89 e5 mov %rsp,%rbp
35: b8 00 00 00 00 mov $0x0,%eax
3a: e8 00 00 00 00 call 3f <main+0xe>
3f: b8 00 00 00 00 mov $0x0,%eax
44: 5d pop %rbp
45: c3 ret
Disassembly of section .rodata:
0000000000000000 <.rodata>:
0: 68 65 6c 6c 6f push $0x6f6c6c65
5: 00 .byte 0
6: 25 .byte 0x25
7: 73 00 jae 9 <func+0x9>
...
```
`.rodata` 中 `0: 68 65 6c 6c 6f`，對照 ASCII Code 查詢即可得知從 0 的位置開始放了五個字元 `h` `e` `l` `l` `o`，但是後面反組譯為 `push $0x6f6c6c65` 相當令人困惑！
**2. `char s[] = "hello";`**
```c
void func()
{
char s[] = "hello";
printf("%s", s);
}
```
```
$ gcc -c str.c
$ objdump -D str.o
Disassembly of section .text:
0000000000000000 <func>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 10 sub $0x10,%rsp
8: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
f: 00 00
11: 48 89 45 f8 mov %rax,-0x8(%rbp)
15: 31 c0 xor %eax,%eax
17: c7 45 f2 68 65 6c 6c movl $0x6c6c6568,-0xe(%rbp)
1e: 66 c7 45 f6 6f 00 movw $0x6f,-0xa(%rbp)
24: 48 8d 45 f2 lea -0xe(%rbp),%rax
28: 48 89 c6 mov %rax,%rsi
2b: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # 32 <func+0x32>
32: 48 89 c7 mov %rax,%rdi
35: b8 00 00 00 00 mov $0x0,%eax
3a: e8 00 00 00 00 call 3f <func+0x3f>
3f: 90 nop
40: 48 8b 45 f8 mov -0x8(%rbp),%rax
44: 64 48 2b 04 25 28 00 sub %fs:0x28,%rax
4b: 00 00
4d: 74 05 je 54 <func+0x54>
4f: e8 00 00 00 00 call 54 <func+0x54>
54: c9 leave
55: c3 ret
0000000000000056 <main>:
56: 55 push %rbp
57: 48 89 e5 mov %rsp,%rbp
5a: b8 00 00 00 00 mov $0x0,%eax
5f: e8 00 00 00 00 call 64 <main+0xe>
64: b8 00 00 00 00 mov $0x0,%eax
69: 5d pop %rbp
6a: c3 ret
Disassembly of section .rodata:
0000000000000000 <.rodata>:
0: 25 .byte 0x25
1: 73 00 jae 3 <func+0x3>
...
```
`.text` 中 `17: c7 45 f2 68 65 6c 6c movl $0x6c6c6568,-0xe(%rbp)` 以及 `1e: 66 c7 45 f6 6f 00 movw $0x6f,-0xa(%rbp)`，`movl` xx待查閱 x86 指令格式xx，`movw` xx待查閱 x86 指令格式xx，`$0x6c6c6568` （倒過來放?），`h` `e` `l` `l` 4 byte 先放，再放 `o`，因為 CPU 一次寫入 4 byte。這兩道指令將 string literal 複製進堆疊
而 `.rodata` 中並沒有 string literal ，自然也沒有從 `.rodata` 複製到 stack 上，與教材中所述不符。但是參照規格書 6.4.5 "hello" 符合 string literal 的語法，應置於 static storage 中。~~由此可以推斷，gcc 對他做了最佳化，並不把他視為 string literal 處理？然而關閉最佳化後 `objdump -D` 結果仍相同~~ 關閉最佳化後仍然是置於 `.text`。
此處應該要思考 static storage 是指什麼？
* [ELF 規格書](https://refspecs.linuxfoundation.org/elf/elf.pdf) 只有在 introduction 隱晦的提示
> Executable and shared object files statically represent programs.
* GCC 13.2 manual - [18.18 Dividing the Output into Sections (Texts, Data, …)](https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gccint/Sections.html) ，此文件紀錄 GCC 內部用以指定資料擺放位置的巨集
> **TEXT_SECTION_ASM_OP**
> A C expression whose value is a string, including spacing, containing the assembler operation that should precede instructions and ==read-only== data. Normally `"\t.text"` is right.
> **READONLY_DATA_SECTION_ASM_OP**
> A C expression whose value is a string, including spacing, containing the assembler operation to identify the following data as ==read-only== initialized data.
<br>比較有趣的是 [gcc 3.4 的文件](https://gcc.gnu.org/onlinedocs/gcc-3.4.0/gccint/Sections.html) 有一個 `READONLY_DATA_SECTION` 巨集會在 target 沒有唯獨區塊也不把資料放在 text 的情況下把資料放進 `.data`
* CS:APP Ch 7.8, 7.9 中說明 `.init`, `.text`, `.rodata` 為唯讀
以此推斷，`.text` 及 `.rodata` 皆為 static storage。所以是我誤會 [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer#%E9%87%8D%E6%96%B0%E6%8E%A2%E8%A8%8E%E3%80%8C%E5%AD%97%E4%B8%B2%E3%80%8D) 「重新探討字串」段落中 read-only data section 的意思，不可以直接解讀為 `.rodata` section
另外，GCC 也支援透過 [`__attribute__`](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html) 自訂資料存放的 section，但僅限於 global variables，而且一樣要[注意](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37506) `char *` 與 `char[]` 的區別
> Normally, the compiler places the objects it generates in sections like data and bss. Sometimes, however, you need additional sections, or you need certain particular variables to appear in special sections, for example to map to special hardware. The section attribute specifies that a variable (or function) lives in a particular section.
**3. `char s[64] = "hello";`**
> **(C99) 6.4.5p5**
> In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals(66). The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.
先不論第二個實驗的結果，照規格書所述空間會剛好足夠容納 multibyte character sequence，以此推斷只會有 6 byte 在 `.rodata`
```c
void func()
{
char s[64] = "hello";
printf("%s", s);
}
```
```
$ gcc -c str.c
$ objdump -D str.o
Disassembly of section .text:
0000000000000000 <func>:
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 48 83 ec 50 sub $0x50,%rsp
8: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
f: 00 00
11: 48 89 45 f8 mov %rax,-0x8(%rbp)
15: 31 c0 xor %eax,%eax
17: 48 b8 68 65 6c 6c 6f movabs $0x6f6c6c6568,%rax
1e: 00 00 00
21: ba 00 00 00 00 mov $0x0,%edx
26: 48 89 45 b0 mov %rax,-0x50(%rbp)
2a: 48 89 55 b8 mov %rdx,-0x48(%rbp)
2e: 48 c7 45 c0 00 00 00 movq $0x0,-0x40(%rbp)
35: 00
36: 48 c7 45 c8 00 00 00 movq $0x0,-0x38(%rbp)
3d: 00
3e: 48 c7 45 d0 00 00 00 movq $0x0,-0x30(%rbp)
45: 00
46: 48 c7 45 d8 00 00 00 movq $0x0,-0x28(%rbp)
4d: 00
4e: 48 c7 45 e0 00 00 00 movq $0x0,-0x20(%rbp)
55: 00
56: 48 c7 45 e8 00 00 00 movq $0x0,-0x18(%rbp)
5d: 00
5e: 48 8d 45 b0 lea -0x50(%rbp),%rax
62: 48 89 c6 mov %rax,%rsi
65: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # 6c <func+0x6c>
6c: 48 89 c7 mov %rax,%rdi
6f: b8 00 00 00 00 mov $0x0,%eax
74: e8 00 00 00 00 call 79 <func+0x79>
79: 90 nop
7a: 48 8b 45 f8 mov -0x8(%rbp),%rax
7e: 64 48 2b 04 25 28 00 sub %fs:0x28,%rax
85: 00 00
87: 74 05 je 8e <func+0x8e>
89: e8 00 00 00 00 call 8e <func+0x8e>
8e: c9 leave
8f: c3 ret
0000000000000090 <main>:
90: 55 push %rbp
91: 48 89 e5 mov %rsp,%rbp
94: b8 00 00 00 00 mov $0x0,%eax
99: e8 00 00 00 00 call 9e <main+0xe>
9e: b8 00 00 00 00 mov $0x0,%eax
a3: 5d pop %rbp
a4: c3 ret
Disassembly of section .rodata:
0000000000000000 <.rodata>:
0: 25 .byte 0x25
1: 73 00 jae 3 <func+0x3>
...
```
上方輸出結果與第二個實驗一樣，沒有 string literal 儲存於 `.rodata` 中。接續第二個實驗的結論，我的問題可以回答為：「string literal 一樣位於 static storage 中，在 `.text`，並在執行時期將字傳內容複製到 64 byte 連續記憶體的低位，並將剩餘空間補上 0」(但是這邊用 `movabs $0x6f6c6c6568,%rax`，第二個實驗中卻是用 `movl` `movw`)
Sign in with Wallet
Connect another wallet