# Linux 核心專題: 重作 lab0
> 執行人: leonnig
> [解說錄影](https://youtu.be/MS8MC07cKz0)
### Reviewed by `jserv`
[leonnig/lab0-c](https://github.com/leonnig/lab0-c) 尚未依據作業規範，rebase 到最新的 [lab0-c](https://github.com/sysprog21/lab0-c)。務必改正。
> [name=leonnig]
收到!
### Reviewed by `thwuedwin`
你的 select 實驗中，會先檢查 server 的輸入，再逐一檢查所有連線的輸入。你的做法每次都需要檢查整個陣列，若只有一個連線，但他在陣列的最後一格，就會浪費很多時間。若用鏈結串列儲存會比較好嗎？還是有其他的考量？
若我沒有理解錯的話，`select` 的回傳值是目前可以讀寫的檔案描述子的數量，你將其儲存在 `ret_val`。你每處理一個輸入就會將其遞減，當其歸零時代表已經處理完畢。我不清楚 select 的運作機制，有沒有可能在執行迴圈時有新的輸入，因此導致你實際要處理的輸入量比這個值更大，就會導致某些輸入沒被處理到？
程式碼的部分125 行的 `continue` 是在 for 迴圈內，所以應該沒有辦法達到你要的效果，應該要改成 `break` 吧？而且你還有使用 `ret_val` 來儲存 socket 的輸入。雖然只是沒有達到「處理完輸入就提早結束」的功能，並不會有太大的影響，但整個流程看起來很奇怪。
> [name=leonnig]
> 目前的寫法會導致在檢查 fd 是否 ready 時，每次都得掃一次 all_connections 陣列，的確效率不高，因為當初想說只是要簡單觀察一下，我會再改用 link_list 試看看。
> 然後關於 `ret_val`，`select()` 回傳的 ret_val 的確是「當下」 ready 的 fd 數量。而這個數字不會在迴圈中更新，即使有新的輸入在處理過程中到來，也不會反映在這次的 `ret_val` 裡。
不過這並不會造成資料漏掉，因為新的輸入會在下一次(下一輪迴圈中) `select()` 再次觸發。
再來是 `continue` 的部分，這裡 continue 只會跳過當下的 for 迴圈剩餘部分，然後進入下一個 i，所以其實還是會繼續跑下去，沒有達成我原本的「處理完所有 ready fd 就跳出」的目標。
改成 break 可以讓我提早結束這次 for，效率會更好一點。當然即使不改也不會造成錯誤，但流程上會更清晰，謝謝你提出的問題，我會再改進。
### Reviewed by `liangchingyun`
數學符號需統一，如 $C_b,_{bu}(N)$ 及 $C_{\text{b,bu}}(N)$。
> [name=leonnig]
> 收到，以更正，謝謝提醒。
### Reviewed by `I-Ying-Tsai`
你在 web.c 的 select 實驗中，維護一個陣列來追蹤所有連線，每次都需要掃描整個陣列來檢查 ready fd，這在連線數變多時可能會影響效能。想請問能否使用 linked list 或其他資料結構如紅黑樹來儲存連線資訊？
> [name=leonnig]
> 在我目前的實驗中，我用固定大小的陣列維護所有連線，但在連線數變多時，每次都要線性掃描整個陣列，對效能來說確實是不利的，使用 linked list 可以減少掃描無用連線的成本，不過它還是線性查找，所以可以試試看你提到的紅黑樹，這部分我會再研讀完紅黑樹的原理再來實驗看看。
### Reviewed by `alexc-313`
> [而在發現 list sort 在 branche-instructions 的次數也比較少](https://hackmd.io/WJX0QWZfR4OVCoA94qCqmg?both=&stext=15511%3A45%3A0%3A1751523495%3AbLZiIq)
這邊應該是 branch-instructions 。
> [name=leonnig]
感謝提醒，已更正。
### Reviewed by `MuChengChen`
在計算 Bottom-Up Mergesort 的比較次數時有提到是運用 $$C_{\text{b,bu}}(N) = \sum_{0 < j \leq k} 2^{j - 1}\left\lfloor \frac{N}{2^j} \right\rfloor + \sum_{0 < j \leq k} b_j (b_{j-1} \cdots b_0)_2 = \sum_{n < N} v(n)$$ 進行計算，想請問其中 $v(n)$ 的計算式以及細節?
## 任務描述
重作 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 並強化以下:
1. 記憶體分析
2. dudect 論文和給定的 lab0-c 的程式碼有哪些出入？如何改進 lab0-c?
3. 探討 lib/list_sort.c 相關實作時，除了觀察程式碼，，也該理解為何 Linux 核心開發者採用這段程式碼，也就是推敲開發是如何思考及進行取捨。我們可參見 github commit history，lib/list_sort.c 最近一次演算法上的改動在 2019 年 5 月 15 日的 commit b5c56e0c, lib/list_sort: optimize number of calls to comparison function 引入，閱讀程式碼引用的三篇論文
4. 強化實驗
5. web.c 裡頭運用 select 系統呼叫的方式，搭配並行程式設計的教材
務必詳實更新在本頁面。
## 閱讀 lib/list_sort.c 程式碼引用的三篇論文，並強化實驗
### Bottom-Up Mergesort--a Detailed Analysis
merge sort 可以簡單分為 Top-down 及 Bottom-up 兩種，一般常見的 divide and conquer 的屬於 Top-down，而這篇論文則是仔細分析了 Bottom-up 的複雜度等等。
$C(N)$ 表示排序 $N$ 個元素的比較次數，文中認為這個可能是對運行時間影響最大的因素。
Bottom-up 跟 Top-dwon 的不同就在於 divide 的策略，跟 Top-down 的一半一半的 splitting 策略相反，bottom-up 是以二的冪來決定，而因為是二的冪的關係，所以使得演算法在設計上可以考慮以非遞迴的方式去實作。
Bottom-up 的 psuedo code:
```
begin
length := 1;
while length < N do
begin
p := 0;
q := length;
while q + length <= N do
begin
Merge(a[p + 1 .. p + length], a[q + 1 .. q + length]);
p := q + length;
q := p + length;
end;
if q < N then
Merge(a[p + 1 .. p + length], a[q + 1 .. N]);
length := 2 * length;
end;
end;
```
假設有資料： [8, 3, 5, 1, 7, 6, 2, 4]
第一輪 length = 2：每兩個數合併成排好的：
[3,8] [1,5] [6,7] [2,4]
第二輪 length = 4：每四個合併：
[1,3,5,8] [2,4,6,7]
第三輪 length = 8：全部合併：
[1,2,3,4,5,6,7,8]
整體是從最底層一對一開始兩兩合併，直到整體完成排序。
可以看出來，在最一開始的 bottom level 有 $\left\lfloor \frac{N}{2} \right\rfloor$ 次的(1,1)類型的合併過程，而在下一個 level 有 $\left\lfloor \frac{N}{4} \right\rfloor$ 次的(2,2)類型的合併，所以推到一般化來看: level $j(j>0)$ 有 $\left\lfloor \frac{N}{2^{j+1}} \right\rfloor$ 次 $(2^j, 2^j)$ 的 complete merge，而若 $N$ $mod$ $2^{j+1} >2^j$ 的話，代表還會多一次額外的 $(2^j, N mod 2^j)$ 的不完整合併
也可以用二進位表示成 $b_j \cdot (b_{j-1}...b_1b_0)_2 > 0$，當 $b$ 為 1 就代表有一個非 $2^k$ 的子串列。
論文中也提到總共有 $N - 1$ 次合併，這邊以 $N = 15$ 舉例
- 完整合併次數: $\left\lfloor \frac{15}{2} \right\rfloor$ + $\left\lfloor \frac{15}{2^2} \right\rfloor$ + $\left\lfloor \frac{15}{2^3} \right\rfloor$ = $7 + 3 + 1 =11$
- 不完整合併次數: 15 = $(1111)_2$ -> $b_3 + b_2 + b_1 + b_0 - 1 = 3$
$11 + 3 = 15 - 1$
1. $j = 0$，$15 mod 2 = 1$， $1 > 1$ 不成立，未發生不完整合併。
2. $j = 1$，$15 mod 4 = 3$， $3 > 2$ 成立，發生不完整合併 $(2,1)$。
3. $j = 2$，$15 mod 8 = 7$， $7 > 4$ 成立，發生不完整合併 $(4,3)$。
4. $j = 4$，$15 mod 16 = 15$， $15 > 8$ 成立，發生不完整合併 $(8,7)$。
確實總共 3 次不完整合併。
比較次數可以用以下式子表示:
$min\{m,n\} \leq C_n,_m \leq n + m - 1$
再看以下公式:
$\displaystyle P\{c_{n,m} = j\} = \frac{\binom{j-1}{n-1} + \binom{j-1}{m-1}}{\binom{n+m}{n}}$
此為合併兩個已排序序列（長度為 𝑛 和 𝑚）時，剛好需要做 𝑗 次比較 的機率。
$\displaystyle P\{c_{n,m} = j\}$ 代表比較次數剛好等於 𝑗 的機率。
${\binom{j-1}{n-1} + \binom{j-1}{m-1}}$ 分別是從 𝑗−1 次操作中選出哪幾次是從左側（長度 𝑛）或右側（長度 𝑚）陣列中取出元素的方式數。
最佳情況 $C_b,_{bu}(N)$，代表每次合併的過程都為最佳情況(比較次數最少)，因此根據上面比較次數的式子，只須對合併過程中較小的字串長度求和。
而最佳情況下的比較次數可以表示為以下:
$C_{{b,bu}}(N) = \sum_{0 < j \leq k} 2^{j - 1}\left\lfloor \frac{N}{2^j} \right\rfloor + \sum_{0 < j \leq k} b_j (b_{j-1} \cdots b_0)_2 = \sum_{n < N} v(n)$
---
#### 第一項: $\sum_{0 < j \leq k} 2^{j - 1}\left\lfloor \frac{N}{2^j} \right\rfloor$
此像是根據 MergeSort 的 bottom-up合併過來的，在每一層 level $j$ 的合併中，有 $\left\lfloor\frac{N}{2^j} \right\rfloor$ 對要合併的子串列，每一對合併中較小的那一半會有 $2^{j-1}$ 長度，因為是合併兩個長度 $2^{j-1}$ 的串列，所以此項為第 $j$ level所有合併操作的成本總和(只計算較小的那一半)。
---
#### 第二項: $\sum_{0 < j \leq k} b_j (b_{j-1} \cdots b_0)_2$
這項是計算在 Bottom-Up MergeSort 中，當 N 不是 2 的冪時，某些「額外的不完整合併」所產生的比較次數。
當某一位 $b_j = 1$ 時: 需要額外進行一次不完整合併。
---
$\sum_{n < N} v(n)$
等價於上面兩項的總和，代表合併過程中「每一個索引 n < N」所經歷的合併次數，所以每一個 n 所經歷的合併的次數剛好等於 $v(n)$。
#### Top-Down Versus Bottom-Up Mergesort.
在 best case 中，bottom-up 比較次數和 Top-down 相同，worst case 和 average case 皆是 top-down mergesort 比較次數更少，特別在 worst case 時 ，Top-down 恆優於或等於 Bottom-up，僅在 $N = 2^k$ 時相等。
------
### Queue-mergesort
論文中提出了一種 mergesort 的變體，作者將其稱為 Queue mergesort，概念是建構一個 queue 並且當中的元素都是排序好的鍵結串列，一開始每個節點都是一個串列。
Algo:
```
queue-mergesort(
while (Qsize! = 1) do
Q.put(Merge(Q.get, Q.get))
}
```
每一輪會將 queue 頭部的前兩的串列取出來，並將兩個串列進行排序以及合併，完成後變成一條串列，再將其插入到 queue 的尾部，所以每一輪都會少一個元素(串列)，並且直到整個 queue 只剩下一個串列。
示意圖:
接著取出前兩項 C 和 F，並且合併後插入到尾部
重複以上動作直到剩下一條串列
  
此時排序完成
接著要證明 queue mergesort 是 optimal mergesort，此處的 optimal 的意思是指，對於任意元素數量 $n$，queue mergesort 在 worst case 下所需的比較次數，不超過任何其他類型的 merge sort，則代表它是 optimal mergesort 。
關於 mergesort 的 worst case 我有另外整理在 [Mergesort 的 worst case](https://hackmd.io/o2H9UQgDTmKgFcmFvq_XUw?view)。
mergesort 在進行合併的過程都可以用二元樹狀結構來表示，而樹葉(外部節點)就代表一開始要被排序的 item，而內部節點則代表合併過後的串列，而此處先定義權重 `w(i)` 為樹中的每個節點 `i`，裡面所包含的 item 的數量，所以樹葉的權重就都或是 1，而`root` 包含了全部的 item，權重為 $n$。
在合併兩條長度 $i$ 和 $j$ 的串列時，worst case 下的比較次數為 $i + j -1$，對內部節點 $v$ 來說，worst case 的比較次數即為 $w(v) - 1$，所以我們在計算比較次數時，就看二元樹中的內部節點，因此整棵樹在 worst case 下的比較次數即是
$$ \sum_{v \in T} [w(v) - 1] = [\sum_{v \in T} w(v)] - (n - 1) $$
$T$ 為對 $n$ 個 item 進行 mergesort 的二元樹
證明 **Queue-mergesort is an optimal mergesort** : 要證明此結論，只需要證明對所有具有 $n$ 個節點的 merge tree $T'$，都滿足 $w(T) \leq w(T')$。
這裡要用到一些性質
1. $T$ 的權重等同於它的外部節點路徑長，$w(T) = E(T)$。
在此性質下，令 $h(l)$ 為節點 $l$ 到 root 的距離。樹 $T'$ 的外部總和長度為 $E(T) = \sum_l h(l)$。因此任意 merge tree $T'$ ，根據性質得出 $w(T') = E(T')$，因此要證明定理，只需要證明對所有具有 $n$ 個節點的 $T'$能夠滿足 $E(T) \leq E(T')$。
2. **Huffman enoding**: 這個演算法可以建構出 **weighted external path length 最小** 的二元樹，一開始會創造一個包含 $n$ 個節點的集合，權重分別為 $w_1, w_2, w_3,...,w_n，每次將集合中最小的兩個節點拿出來合併，合併後的節點權重為取出的兩節點權重合併，再重新將此合併的節點加入集合。
根據 Huffman encoding 的描述，可以發現一些與 queue mergesort 的相似性，兩者在迭代的過程中都是移除集合中的兩個節點，並且合併後新節點的權重等於其子節點權重之和，再將新節點加入，直到集合中剩一個節點，其實 queue mergesort 就幾乎等價於權重都為 `w_1 = w_2 = ... = w_n = 1` 的 huffman coding 所構建的二元樹，只需要在證明: 在 queue mergesort 的每一步中，queue head 的前兩個串列始終是 queue 中長度最小的兩個串列，則和 huffman encoding 的特性完全一致。
這邊使用數學歸納法，當演算法開始時 queue 中包含 $n$ 個長度為 1 的串列，長度按照非遞減順序排序，在第一次合併後，queue head 的前兩個串列合併為長度為2的新串列，並且加入到 queue 的尾部，此時 queue 中串列長度 $1 \leq 1 \leq ... \leq 2$ 仍保持非遞減順序。
假設演算法執行了 $s$ 步 ($s \geq 1$)，queue 中的串列均按照長度非遞減排序。
要證明 $s+1$ 步後 queue 仍保持串列長度非遞減排序，只需要證明在 $s+1$ 步完成後插入到 queue 尾部的子串列 $L_{s+1}$ 的大小至少要和 $s$ 步完成後插入 queue 尾部的 $L_s$ 一樣大。
而子串列 $L_s$ 是 $s−1$ 步完成後，queue 中前兩個子串列的合併結果，而又根據假設 $s$ 步 ($s \geq 1$)的queue 中的串列均按照長度非遞減排序，所以 $L_{s+1}$ 長度必定不會小於 $L_s$ 。
### list_sort
搭配 [git commit message](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09#diff-885cee1e475f747c4f9d9eb78bfb1cca5fa5067759e320ee0ceb0bc178cb08f0) 來了解關於 list_sort 改動的理由。
首先 Mergesort 的比較次數可以寫成
$$\begin{gather*}
nlog_2 n - Kn + O(1)
\end{gather*}$$
其中前面的主要項 $nlog_2 {n}$，已經接近理論的極限 ($log_2 {n!}$)，所以在不同的 Mergesort 變體中，真正的差異是在第二項的係數 $K$，目前 mergesort 能夠達到最好的結果為 $K = 1.2645$，條件為當輸入 $n$ 為 2 的次方時。
>The differences between mergesort variants appear when n is *not* a power of 2; K is a function of the fractional part of log2(n). Top-down mergesort does best of all, achieving a minimum K=1.2408, and an average (over all sizes) K=1.248. However, that requires knowing the number of entries to be sorted ahead of time, and making a full pass over the input to count it conflicts with a second performance goal, which is cache blocking.
不同的合併排序變體之間的差異會出現在 n 不是 2 的次方的時候，其中 **Top-down** 的表現最好，但因為他的需要事先知道整個排序的元素數量，而在鏈結串列的實作中，就必須要從頭開始走訪一次以取得整個串列的 size，而在讀取 list 的過程中，若是 L1 cache 放不下，則需要重新走訪，會造成元素 cache miss，從而影響效能。
> While textbooks explain bottom-up mergesort as a succession of merging passes, practical implementations do merging in depth-first order: as soon as two lists of the same size are available, they are merged. This allows as many merge passes as possible to fit into L1; only the final few merges force cache misses.
>This cache-friendly depth-first merge order depends on us merging the
beginning of the input as much as possible before we've even seen the
end of the input (and thus know its size).
**bottom-up** 的實作上是採用深度優先，當有兩個相同大小的串列時則立刻和併，這樣可以減少 L1 cache miss 的機率，但這樣的方式也有可能導致當資料量略大於 2 的次方時，會產生大量的比較次數，例如當 $n = 1028$ 時，最後一次合併會是 $[1024, 4]$，很浪費效能。
> There are "worst-case optimal" variants of bottom-up mergesort which avoid this bad performance, but the algorithms given in the literature, such as queue-mergesort and boustrodephonic mergesort, depend on the breadth-first multi-pass structure that we are trying to avoid.
而文獻中有針對這類 case 去做最佳化的一些 bottom-up mergesort 變體，但這些演算法大多是採用廣度優先的合併，這會造成 cache miss 的機率上升，因此作者對此進行了以下的改善方式。
> This implementation is as eager as possible while ensuring that all merge passes are at worst 1:2 unbalanced. This achieves the same average K=1.207 as queue-mergesort, which is 0.2*n better then bottom-up, and only 0.04*n behind top-down mergesort.
Specifically, defers merging two lists of size 2^k until it is known that there are 2^k additional inputs following. This ensures that the final uneven merges triggered by reaching the end of the input will be at worst 2:1. This will avoid cache misses as long as 3*2^k elements fit into the cache.
一般的fully-eager bottom-up mergesort只要出現兩個大小為 $2^k$ 小的list就會進行排序並合併，而這裡的實作方式仍然是盡可能的先行合併，以確保深度優先，盡量減少 cache miss，同時保確保所有合併最差情況的大小比例是 2:1，但是會延遲合併兩個 $2^k$ 大小的串列，直到有額外的 $2^k$ 大小的串列，在進行合併。
這樣的作法成功讓 $K$ 達到 1.207，比原本的 bottpm-up mergesort 好了 $0.2 * n$ 次的比較。
而它是如何做到的，可以藉由程式碼註解來進一步了解
:::info
Thus, it will avoid cache thrashing as long as $3*2^{k}$ elements can fit into the cache.
ot quite as good as a fully-eager bottom-up mergesort, but it does use $0.2*n$ fewer comparisons, so is faster in the common case that everything fits into L1.
:::
只要 $3*2^k$ 的串列可以被放到 cache 中，就可以避免 cachr thrashing。
:::info
The merging is controlled by "count", the number of elements in the pending lists.
This is beautiully simple code, but rather subtle.
Each time we increment "count", we set one bit (bit k) and clear bits k-1 .. 0. Each time this happens (except the very first time for each bit, when count increments to $2^k$), we merge two lists of size $2^k$ into one list of size.
:::
合併過程利用 **count** 來記錄 pending 內的節點數量，每次當 count+1 時，若第 k 個 bit 為 1 且 k-1 ~ 0 的 bit 為 0，代表此時將 2 個 $2^k$ 合併，留下一個 $2^k$。
例如: count = (011) -> count++ = (100)，也就是 pending 內的節點數量為 2 的次方時，就會去合併兩個 size 為 $2^k$ 的串列為一個 size 為 $2^{k+1}$ 的串列。
:::info
This merge happens exactly when the count reaches an odd multiple of $2^k$, which is when we have $2^k$ elements pending in smaller lists, so it's safe to merge away two lists of size $2^k$.
After this happens twice, we have created two lists of size $2^{k+1}$, which will be merged into a list of size $2^{k+2}$ before we create a third list of size $2^{k+1}$, so there are never more than two pending.
:::
當 count 達到 $2^k$ 的奇數倍的時候會合併，而在發生兩次合併後會產生兩個 $2^{k+1}$ 的串列，並且會合併為一個 $2^{k+2}$ 的串列，**但這個合併會發生在第三個 $2^{k+1}$ 之前**，所以永遠不會超過兩個 pending。
___
list_sort 實作
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
首先將尾部的的 `next` 指向 `NULL`，使其不為環狀。
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
`bits` 的變化會決定合併，當 `count+1` 後為 $2^k$ 的話，則不合併，因為代表這時的 `count` 就是 $2^k -1$，那用位元表示的話就會是 …0111111，這樣就會在 `for` 迴圈的判斷中讓 bits 一直往右 shift，直到變為 0，而無法進行合併，而 `*tail` 其實就是 `pending`，所以 `for` 迴圈內就是在將節點加入到 pending 中。
而在 `if (likely(bits))` 的程式判斷內，當 `bits` 為 0 時就不會進行合併，也就是當前面 `for` 迴圈的 count 是 $2^k - 1$ 時，例如 $7 = (0111), 15 = (1111)$，以 7 的情況為例，代表在 pending list 中有 size 分別為 1, 2, 4 的串列各一，所以沒辦法進行合併。
### 實驗
首先撰寫好測試的腳本:
```
# Test the performance of q_sort
option fail 0
option malloc 0
new
ih RAND 800000
qsort
free
# Test the performance of listsort from Linux kernel
option fail 0
option malloc 0
new
ih RAND 800000
listsort
free
```
每次給予隨機的 80 萬筆資料下去做排序。
我們可以使用 `perf stat` 來去查看統計資料，選項 `-e` 可以指定要測量的事件種類，並且使用 `repeat` 讓他重複10次腳本。
```shell
$ perf stat --repeat=10 -e cycles,instructions,branch-instructions,branch-misses,context-switches,page-faults ./qtest -f traces/trace-q_sort_per_eval.cmd
```
##### 自己實作的 Merge sort
```
Performance counter stats for './qtest -f traces/trace-q_sort_per_eval.cmd' (10 runs):
5,873,534,758 cycles ( +- 1.79% )
7,006,674,521 instructions # 1.19 insn per cycle ( +- 0.46% )
959,393,683 branch-instructions ( +- 0.81% )
20,945,600 branch-misses # 2.18% of all branches ( +- 0.10% )
964 context-switches ( +- 1.32% )
113,976 page-faults ( +- 0.10% )
4.1678 +- 0.0202 seconds time elapsed ( +- 0.49% )
```
##### Linux kernel 中的 list_sort
```
Performance counter stats for './qtest -f traces/trace-listsort_per_eval.cmd' (10 runs):
5,388,986,349 cycles ( +- 3.11% )
6,792,569,210 instructions # 1.26 insn per cycle ( +- 0.76% )
928,518,120 branch-instructions ( +- 1.36% )
20,905,545 branch-misses # 2.25% of all branches ( +- 0.15% )
932 context-switches ( +- 0.52% )
114,042 page-faults ( +- 0.06% )
4.0867 +- 0.0293 seconds time elapsed ( +- 0.72% )
```
差異比較明顯的幾個項目有以下
|事件種類|自己實作的 sort| list_sort
| ---- | ------ | ------ |
**cycles** | 5,873,534,758 | 5,388,986,349
**instructions** | 7,006,674,521 | 6,792,569,210
**branch-instructions** | 959,393,683 | 928,518,120
**IPC** | 1.19 | 1.26 |
list_sort 在 cycles 和 instructions 上 都較前者明顯來的低，instructions per second 也有較好的表現。
而在發現 list sort 在 branch-instructions 的次數也比較少，因為 list_sort 是使用 iteration 的方式，相較於自己實作的 mergesort 來說，它在函式重複呼叫的次數上就不會那麼多，對應到的 branch 次數也會比較低，而我實作的 Top-down mergesort 是使用遞迴的方式，當中就會有大量的 function call branches。
---
#### Cache Miss
使用 `cachegrind` 工具來幫助分析 cache miss，產生報告。
```shell
$ valgrind --tool=cachegrind --cache-sim=yes ./qtest -f trace/trace-q_sort_per_eval.cmd
```
可以使用 `cg_annotate` 來查看結果
```c
$ cg_annotate cachegrind.out.xxxx
```
參考 [cachegrind 工具使用](https://www.mropengate.com/2016/10/valgrind-kcachegrindintel-vtuneperf.html)
- I1mr: I1 cache read misses
- D1mr: D1 cache read misses
- D1mw: D1 cache write misses
##### 自己實作的 merge sort
| I1mr | ILmr | D1mr | DLmr | D1mw | DLmw |
| ------------ | ------------ | ---------- | ---------- |---- |---|
| 125 | 124 | 8,716,833 | 3,709,026 |1,669,546 |640,127|
---
##### Linux kernel 中的 list_sort
| I1mr | ILmr | D1mr | DLmr | D1mw | DLmw |
| ------------ | ------------ | ---------- | ---------- |---- |---|
| 129 | 128 | 7,194,256| 3,698,007 |786,990 |615,145|
可以看到在 level1-Data cache read / write 的 miss 次數上，list_sort 比 q_sort 明顯還要來的低，這很可能跟前面提到的 merge sort 合併的模式有關，因為我自己實作的 mergesort 是使用 Top-down 的方式，而使用的是廣度搜尋，在合併的時候會需要，更多的記憶體空間來儲存子串列，進而帶來比較高的 cache miss，而 list sort 除了實作 bottom up 的算法之外，也規定了最差的情況能夠其維持著合併：不合併為 2：1 的比例，以確保 $3*2^k$ 都能放入 cache 內，這樣 cache 中的資料就更容易被存取到，進而減少 cache-misses
---
## web.c 裡頭運用 select 系統呼叫的方式
### File Descreptor
參考資料: [Linux 的 file descriptor 筆記](https://kkc.github.io/2020/08/22/file-descriptor/)
### `select()`
> select() allows a program to monitor multiple file descriptors,waiting until one or more of the file descriptors become "ready for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation.
`select()` 可以讓程式去監控多個[檔案描述子](https://zh.wikipedia.org/zh-tw/%E6%96%87%E4%BB%B6%E6%8F%8F%E8%BF%B0%E7%AC%A6)，並會等待直到這些檔案描述子中有一個或多個是處於 **ready** 狀態，而這個 **ready** 指的是可以對這些檔案描述子進行一些 I/O 操作，像是 `read()` 或是 `write()` 。
其中，`select()` 也有一些限制，他只能監控編號小於 FD_SETSIZE（預設通常是 1024的檔案描述子，而在手冊中也有提到
> An unreasonably low limit for many modern applications—and this limitation will not change.
對於現代的應用程式，這個數量非常不夠用，所以可能在比較大型或追求高效能的網頁伺服器也不適合使用。
### 參數
`select()` 的主要參數是三個「檔案描述子集合」（file descriptor sets），這些集合的型態是 `fd_set`，`fd_set` 是一個結構體，可以視為是一組檔案描述子的集合，根據 POSIX 標準，`fd_set` 結構裡最多能放多少個檔案描述子，是由一個常數 `FD_SETSIZE` 決定的。
這三個集合分別對應三種事件類型，如果對某一類事件不需要監控，可以把對應的集合參數設為 `NULL`。
- readfds : 監控哪些 fd 是否可以讀取，當把一個 fd 加進 readfds，`select()` 就會去監控它，看看它什麼時候可以讀，`select()` 回傳後，readfds 這個集合裡只會剩下這次已經 ready（可以讀) 的 fd，其他會被清除。
- writefds : 監控哪些 fd 是否可以寫入，當把一個 fd 加進 writefds，`select()` 就會去監控它，看看它什麼時候可以寫入，`select()` 回傳後，writefds 這個集合裡只會剩下這次已經 ready（可以寫入) 的 fd，其他會被清除。
- exceptions: 監控哪些 fd 是否發生異常，`select()` 回傳後，exceptfds 這個集合裡只會剩下這次發生異常的 fd。
- nfds: 把三個集合（readfds、writefds、exceptfds）裡編號最大的 fd 找出來，然後加 1，這個值就是 nfds。
- timeout: 用來指定 `select()` 最多要等待多久。
> The call will block until either:
• a file descriptor becomes ready;
• the call is interrupted by a signal handler; or
• the timeout expires.
`select()` 會在什麼情況下結束等待？
- 有檔案描述子變成 ready（可以 I/O）時
- 呼叫被 signal handler 中斷時
- 等待時間（timeout）到了
特別注意的是，**如果把 timeout 設成 NULL**，`select()` 會無限期阻塞，直到有 `fd` ready 或被訊號中斷。
回傳值會分成 `select()` 執行成功或失敗的狀況
成功: 回傳三個 `fd_set` 中，有多少 `fd` 是處於 ready 的，也就是總共有幾個檔案描述符在這次呼叫後被標記為 ready。
失敗: 回傳 -1，並且會設定 `errno` 來說明錯誤訊息。
`fd_set` 則能夠透過一些巨集來操作。
#### `FD_ZERO()`
用來清空一個 `fd_set` 內的 file descriptors。
> It should be employed as the first step in initializing a file descriptor set.
在使用 `fd_set` 之前，第一步通常就是呼叫 `FD_ZERO()` 來初始化這個集合，確保集合是空的，避免殘留之前的資料。
#### `FD_SET()`
把某個指定的 file descriptor 加入到 `fd_set`。
#### `FD_CLR()`
把某個指定的 file descriptor 從 `fd_set` 中移除。
#### `FD_ISSET()`
用來檢查某個 `fd` 是不是在指定的 `fd_set` 裡。
在 [I/O Multiplexing](https://hackmd.io/@sysprog/linux-file-system#IO-Multiplexing) 中有說到，`select()` 可以同時監視多個 file descrepitor，不用因為一個 `read()` 而阻塞， 因此 select 常被用於實作 I/O Multiplexing 的函式。
使用範例：
```c
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
int main(void)
{
int retval;
fd_set rfds;
struct timeval tv;
/* Watch stdin (fd 0) to see when it has input. */
FD_ZERO(&rfds);
FD_SET(0, &rfds);
/* Wait up to five seconds. */
tv.tv_sec = 5;
tv.tv_usec = 0;
retval = select(1, &rfds, NULL, NULL, &tv);
/* Don't rely on the value of tv now! */
if (retval == -1)
perror("select()");
else if (retval)
printf("Data is available now.\n");
/* FD_ISSET(0, &rfds) will be true. */
else
printf("No data within five seconds.\n");
exit(EXIT_SUCCESS);
}
```
先用 `FD_ZERO()` 將 `rfds` 做初始化，將裡面的 `fd_set` 清空，再用 `FD_SET()` 將 `stdin` 加入到 fd_set，`select(1, &rfds, NULL, NULL, &tv)` 會關心是否有可讀的資料，程式執行後便會開始監控輸入。
因為目前對 socket programming 一竅不通，在看 `web.c` 的時候一頭霧水，決定先去補基本知識。
參考資料: [TCP Socket Programming 學習筆記](https://zake7749.github.io/2015/03/17/SocketProgramming/)、[socket(2)](https://man7.org/linux/man-pages/man2/socket.2.html)
### socket
Socket 是一種通用的通訊機制，可以讓兩個或多個程式在同一台電腦或不同電腦之間進行資料交換，而在 UNIX 中，socket 是一種 **file descreptor**，透過 read/write 操作就能收發資料。
```c
int socket(int domain, int type, int protocol
```
- **domain**: 定義這個 socket 要用來進行哪一類型的通訊
- AF_UNIX, AF_LOCAL: 用於本機間 process 的溝通。
- AF_INET: IPv4 協定
- AF_INET: IPv6 協定
- **type**: socket 的型態，決定通訊的特性。
- **protocol**: 設定通訊協定的號碼，通常在寫的時候會填入 0，kernel 會根據上面的兩個參數自動選擇合適的協定。 [protocol man page](https://man7.org/linux/man-pages/man5/protocols.5.html#top_of_page)
當 socket 成功建立後，會回傳該 socket 的 file descreptor，若建立失敗則回傳 -1。
### bind
讓前面創建的 socket 實際綁定到本機的某個 port 上面，這樣子 client 端在送資料到某個 port 的時候，我們寫的 server 程式才可以在那個 port 上面運行，處理資料，如果綁定成功則回傳 0，否則回傳 -1。
```c
int bind(int sockfd, struct sockaddr *addr, unsigned int addrlen)
```
### select() 小實驗
:::danger
HackMD 不是讓你張貼程式碼的地方，GitHub/gist 才是。當你張貼程式碼，就該要有對應的解說。
:::
接下來利用 `select()` 來建立一個可以監聽多個 socket 的 server。
```c
#include <stdio.h>
#include <netinet/in.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#define DATA_BUFFER 5000
#define MAX_CONNECTIONS 10
int create_tcp_server_socket() {
struct sockaddr_in saddr;
int fd, ret_val;
/* Step1: create a TCP socket */
fd = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
if (fd == -1) {
fprintf(stderr, "socket failed [%s]\n", strerror(errno));
return -1;
}
printf("Created a socket with fd: %d\n", fd);
/* Initialize the socket address structure */
saddr.sin_family = AF_INET;
saddr.sin_port = htons(7000);
saddr.sin_addr.s_addr = INADDR_ANY;
/* Step2: bind the socket to port 7000 on the local host */
ret_val = bind(fd, (struct sockaddr *)&saddr, sizeof(struct sockaddr_in));
if (ret_val != 0) {
fprintf(stderr, "bind failed [%s]\n", strerror(errno));
close(fd);
return -1;
}
/* Step3: listen for incoming connections */
ret_val = listen(fd, 5);
if (ret_val != 0) {
fprintf(stderr, "listen failed [%s]\n", strerror(errno));
close(fd);
return -1;
}
return fd;
}
int main () {
fd_set read_fd_set;
struct sockaddr_in new_addr;
int server_fd, new_fd, ret_val, i;
socklen_t addrlen;
char buf[DATA_BUFFER];
int all_connections[MAX_CONNECTIONS];
/* Get the socket server fd */
server_fd = create_tcp_server_socket();
if (server_fd == -1) {
fprintf(stderr, "Failed to create a server\n");
return -1;
}
/* Initialize all_connections and set the first entry to server fd */
for (i=0;i < MAX_CONNECTIONS;i++) {
all_connections[i] = -1;
}
all_connections[0] = server_fd;
while (1) {
FD_ZERO(&read_fd_set);
/* Set the fd_set before passing it to the select call */
for (i=0;i < MAX_CONNECTIONS;i++) {
if (all_connections[i] >= 0) {
FD_SET(all_connections[i], &read_fd_set);
}
}
/* Invoke select() and then wait! */
printf("\nUsing select() to listen for incoming events\n");
ret_val = select(FD_SETSIZE, &read_fd_set, NULL, NULL, NULL);
/* select() woke up. Identify the fd that has events */
if (ret_val >= 0 ) {
printf("Select returned with %d\n", ret_val);
/* Check if the fd with event is the server fd */
if (FD_ISSET(server_fd, &read_fd_set)) {
/* accept the new connection */
printf("Returned fd is %d (server's fd)\n", server_fd);
new_fd = accept(server_fd, (struct sockaddr*)&new_addr, &addrlen);
if (new_fd >= 0) {
printf("Accepted a new connection with fd: %d\n", new_fd);
for (i=0;i < MAX_CONNECTIONS;i++) {
if (all_connections[i] < 0) {
all_connections[i] = new_fd;
break;
}
}
} else {
fprintf(stderr, "accept failed [%s]\n", strerror(errno));
}
ret_val--;
if (!ret_val) continue;
}
/* Check if the fd with event is a non-server fd */
for (i=1;i < MAX_CONNECTIONS;i++) {
if ((all_connections[i] > 0) &&
(FD_ISSET(all_connections[i], &read_fd_set))) {
/* read incoming data */
printf("Returned fd is %d [index, i: %d]\n", all_connections[i], i);
ret_val = recv(all_connections[i], buf, DATA_BUFFER, 0);
if (ret_val == 0) {
printf("Closing connection for fd:%d\n", all_connections[i]);
close(all_connections[i]);
all_connections[i] = -1; /* Connection is now closed */
}
if (ret_val > 0) {
printf("Received data (len %d bytes, fd: %d): %s\n",
ret_val, all_connections[i], buf);
}
if (ret_val == -1) {
printf("recv() failed for fd: %d [%s]\n",
all_connections[i], strerror(errno));
break;
}
}
ret_val--;
if (!ret_val) continue;
} /* for-loop */
} /* (ret_val >= 0) */
} /* while(1) */
/* Last step: Close all the sockets */
for (i=0;i < MAX_CONNECTIONS;i++) {
if (all_connections[i] > 0) {
close(all_connections[i]);
}
}
return 0;
}
```
首先對 `read_fd_set` 這個 `fd_set` 結構初始化，把裡面所有的 fd 給清空，迴圈會把目前所有有效的連線 fd 都加入到 `read_fd_set` 裡。
```c
while (1) {
FD_ZERO(&read_fd_set);
/* Set the fd_set before passing it to the select call */
for (i=0; i < MAX_CONNECTIONS; i++) {
if (all_connections[i] >= 0) {
FD_SET(all_connections[i], &read_fd_set);
}
}
// ...
}
```
呼叫 `select()` 去同時監聽多個事件( `fd_set` 裡設定的 fd)。
```c
ret_val = select(FD_SETSIZE, &read_fd_set, NULL, NULL, NULL);
```
用 `FD_ISSET(server_fd, &read_fd_set)` 判斷 `server_fd` 是否在 `read_fd_set` 中，如果有，就呼叫 `accept()` 接受新連線，並把新的 `client fd` 加進 all_connections 陣列。處理完後，`ret_val--`，如果已經沒有事件就繼續下一輪迴圈。
```c
/* Check if the fd with event is the server fd */
if (FD_ISSET(server_fd, &read_fd_set)) {
/* accept the new connection */
printf("Returned fd is %d (server's fd)\n", server_fd);
new_fd = accept(server_fd, (struct sockaddr*)&new_addr, &addrlen);
if (new_fd >= 0) {
printf("Accepted a new connection with fd: %d\n", new_fd);
for (i=0;i < MAX_CONNECTIONS;i++) {
if (all_connections[i] < 0) {
all_connections[i] = new_fd;
break;
}
}
}
```
接下來回圈內會開始處理所有 client 端的 socket，`all_connections[i] > 0` 代表這個位置有一個有效的 client fd， `FD_ISSET(all_connections[i], &read_fd_set)` 代表這個 fd 在這一輪 select() 中有可讀事件，再用 `recv()` 從client fd 讀取資料，存到 buffer 裡，如果讀出來大於 0 ，代表成功街收到資料，若等於 0，則代表這個 client fd 的連線被對方關閉，若等於 -1，代表讀取資料時發生錯誤。
```c
for (i=1;i < MAX_CONNECTIONS;i++) { //檢查所有已連線的 client fd。
if ((all_connections[i] > 0) &&
(FD_ISSET(all_connections[i], &read_fd_set))) {
/* read incoming data */
printf("Returned fd is %d [index, i: %d]\n", all_connections[i], i);
ret_val = recv(all_connections[i], buf, DATA_BUFFER, 0);
if (ret_val == 0) {
printf("Closing connection for fd:%d\n", all_connections[i]);
close(all_connections[i]);
all_connections[i] = -1; /* Connection is now closed */
}
if (ret_val > 0) {
printf("Received data (len %d bytes, fd: %d): %s\n",
ret_val, all_connections[i], buf);
}
if (ret_val == -1) {
printf("recv() failed for fd: %d [%s]\n",
all_connections[i], strerror(errno));
break;
}
}
ret_val--;
if (!ret_val) continue;
```
### web.c 中的 select()
而在 `web.c` 當中，`select()` 出現在 `web_eventmux()` 函式中，用來實作多工 I/O 監聽，因為如果只使用 `read()` 會導致阻塞，進而消耗資源，而 `select()` 可以以更有效率的方式來等待並監聽事件。
函式中會呼叫 `select()` 去監聽並持續 block，直到發生新的連接，或者是使用者輸入了新的資料，
```c
int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
```
可以發現 `timeout` 設為 `NULL`，表示會一直等待下去直到發生事件。
如果有使用者在終端機輸入，`STDIN_FILENO` 會變為 ready，如果有 client TCP 請求進來，`server_fd` 也會變成 ready。
再來函式會處理哪個 fd 有事件發生
```c
if (server_fd > 0 && FD_ISSET(server_fd, &listenset))
```
表示有新的 TDP client 進行連線，若 `server_fd` 處於 ready，就會使用 `accept()` 來建立一個與特定用戶端通訊的 socket (`web_conffd`)
```c
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
int web_connfd = accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen);
```
然後 `web_recv()` 會讀取 HTTP request，發送回應，最後將 client 的資料寫到 buffer 內。
```c
char *p = web_recv(web_connfd, &clientaddr);
char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
web_send(web_connfd, buffer);
strncpy(buf, p, strlen(p) + 1);
```
如果是鍵盤輸入觸發 STDIN，則在此函示不會特別做處理，而是會由 linenoise 的 `read()` 來處理。
---
Sign in with Wallet
Connect another wallet