# 2024q1 Homework6 (integration)
contributed by < `nosba0957` >

## 檢查清單
- [ ] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

在 `/linux/kernel/module/main.c` 中的 `load_module` 函式中可以找到 [simplfy_symbols](https://github.com/torvalds/linux/blob/master/kernel/module/main.c#L1367) 函式的呼叫，在 `simplify_symbols` 內看到 `case SHN_UNDEF:` 內呼叫 `resolve_symbol_wait` 再呼叫到 `resolve_symbol`。最後找到 [find_symbol](https://github.com/torvalds/linux/blob/master/kernel/module/main.c#L302) 函式，其中使用到 `list_for_each_entry_rcu`。再深入查看可以在 [find_exported_symbol_in_section](https://github.com/torvalds/linux/blob/master/kernel/module/main.c#L276) 找到 `bsearch`，在 [include/linux/bsearch.h](https://github.com/torvalds/linux/blob/master/include/linux/bsearch.h#L8) 可以看到 bsearch 的實作，也就是透過 binary search 找到 symbol。`MODULE_LICENSE` 的影響是若此核心模組宣告非為 `GPL`，則其無法使用透過 `EXPORT_SYMBOL_GPL` 的 symbol。從 strace 中看到的系統呼叫有，`mmap`，`mprotect`，`fstat`，`fcntl`等。

- [ ] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);

在 simrupt.c 中有三個 mutex lock，`read_lock, consumer_lock, producer_lock`。在 `simrupt_work_func` 中呼叫 `fast_buf_get` 的時候使用到 `consumer_lock`，保護 `fast_buf_get` 中 `ring->buf[tail]` 和 `ring->tail` 的讀取。而 `produce_lock` 則是為了保護 `produce_data` 中，將值存入 `rx_fifo` 的操作。而 `read_lock` 是在 `simrupt_read` 中，也就是當這個核心模組被讀取時，用來保護 `kfifo_to_user` 這個函式執行。

## 排序的改進
### Bottom-up heapsort / `lib/sort.c`
在 Bottem-up heapsort 第一步驟要先建立 heap，`bottom-up-reheap` 總共執行 $\lfloor \frac{n}{2} \rfloor$ 次，而 `bottom-up-reheap` 由三個函式組成。

bottom-up-reheap(m, i)
    j = leaf-search(m, i);
    j = bottom-up-search(i, j);
    interchange(i, j);

#### `leaf-search`
首先是 `leaf-search`。由於 heap 插入時會先將節點新增在 array 的最後方，所以 heap 必為 complete binary tree，除了最後一層沒有填滿以外，其他層都是填滿的。並且最後一層要先從左側插入。所以分析比較次數時先分析 perfect binary tree。此 binary tree 共有 $k$ 層(從第 $0$ 層 ~ 第 $k-1$ 層)。第 $0$ 層找到 special leaf 所需要的比較次數為 $k-1$ 次。第 $1$ 層需要 $k-2$ 次。而第 $0$ 層有 1 個節點，第 $1$ 層有 $2^1=2$ 個節點。而前面提到 `bottom-up-reheap` 會執行 $\lfloor \frac{n}{2} \rfloor$ 次，所以 `leaf-search` 會從 第 $\lfloor \frac{n}{2} \rfloor$ 個節點執行到第 $1$ 個節點。所以要總和所有比較次數
$$
\begin{aligned}
\sum_{i=0}^{k-2}2^i \times (k-1-i) &= 2^0 \times (k-1) + 2^1 \times (k-2)+\ ...\ +2^{k-2} \times 1 \\
&=(2^k - 1) -k \\
&=n - \lceil log_{2}(n+1) \rceil
\end{aligned}
$$
接下來計算沒有填滿節點的最後一層。若該層只有 1 個節點，則對其親代節點的比較次數沒有影響。如左下圖，即使 special path 選擇到 2，也只有走到 4 這一個結果。若是有 2 個節點，如右下圖，則會讓 `9` 和 `10` 的親代節點多 1 次比較次數。
設第 $k$ 層有 $i$ 個節點，計算此 $i$ 個節點在 worst-case 會新增多少比較次數。此 $i$ 個節點的親代共 $\lceil \frac{i-1}{2} \rceil$ 個節點會受影響，再上一層(第 $k-2$ 層)有 $\lceil \frac{i-1}{2^2} \rceil$ 節點也會多 1 次比較次數。所以將受影響的節點次數相加
$$
\sum_{j=1}^{k} \lceil \frac{i-1}{2^j} \rceil \leq i-2+k
$$
所以 worst-case 情況，比較次數為 perfect binary tree 的比較次數加上最後一層新增的 $i$ 個節點在 worst-case 情況的次數。
$$
(2^k - 1 - k) + (i - 2 + k) = n - 2
$$
接下來是新增此 $i$ 個節點時，情況是 best-case 的比較次數。best-case 的情況是在根節點到最後一個節點的路徑上，路徑中的節點進行 `leaf-search` 時直接指向右節點，會少一次比較次數。這條路徑上共有 $\lceil log_{2}n\rceil -1$ 個節點。所以 best-case 的比較次數為
$$
n-\lceil log_{2}(n+1) \rceil - \lceil log_{2}n \rceil + 1
$$
最後論文總結 best-case 和 worst-case 的比較次數相近。所以以 $n+\Theta(logn)$ 表示。

#### `buttom-up-search`

分析 heapsort 和 bottom-up search 的比較次數。heapsort 每次 comparison 時，要先比較其底下的 2 個子節點，選出小的子節點(min-heap)後再將自己和那個子節點比，所以需要 2 次比較次數。$b(1)...b(d)$ 用來描述 special path 路徑上的節點，總長度為 $d$ 且不包含 root。設 $x$ 為 root，此處的 $j$ 是我們要找到 $b(j) < x < b(j+1)$。

| |$j=0$| $0<j<d$ | $j=d$ |
|:--------------:|:---:|:-------:|:-----:|
|heapsort |$2$ | $2(j+1)$| $2d$ |
|buttom-up search|$d$ | $d-j+1$ | $1$ |

用 $l_{HS}$ 表示 heapsort 比較次數的一半，$l_{BUS}$ 表示 buttom-up search 的比較次數。因為 buttom-up reheap 會執行 $\lfloor \frac{n}{2} \rfloor$ 次， buttom-up search 也會執行 $\lfloor \frac{n}{2} \rfloor$ 次。所以目標是算出 buttom-up search 的比較次數。$L_{HS}, L_{BUS}, D$ 這三個隨機變數，代表 $l_{HS}, l_{BUS}, d$ 的總和。所以現在目標是要計算 $E(L_{BUS})$。

| | $l_{HS} + l_{BUS}$ |
| -------- |:--------:|
| $0<j<d$ | $d+2$ |
| $j=0\ or\ j=2$|$d+1$|

為了計算 $E(L_{BUS})$，論文提供 heapsort 在 heap creation phase 的平均比較次數為 $(\alpha_1+2\alpha_2-2)n+\Theta(log\ n)$，平均 interchange 次數為 $(\alpha_1+\alpha_2-2)n+\Theta(log\ n)$。並且論文中推算出 $E(D), E(L_{HS})$。但我想不出 $E(D)$ 是如何計算的。
$$
\begin{aligned}
E(D) &= n+\Theta(log\ n)\\
E(L_{HS}) &= (\alpha_1/2 + \alpha_2-1)n+\Theta(log\ n)
\end{aligned}
$$

接下來假設 $T$ 是呼叫 bottom-up search 時情況為 $j=0\ or\ j=d$ 的呼叫次數。而 $\lfloor \frac{n}{2} \rfloor -T$ 則為情況是 $0<j<d$ 的呼叫次數。

$$
\begin{aligned}
E(L_{BUS}) &= E(T) \times (E(d)+1-E(l_{HS})) + (\lfloor \frac{n}{2} \rfloor - E(T)) \times (E(d)+2-E(l_{HS}))\\
&=(3-\frac{\alpha_1}{2}-\alpha_2)n+E(T)+\Theta(log\ n)
\end{aligned}
$$
接下來計算其中 $E(T)$，$T$ 的情況為 $j=0\ or\ j=d$，所以分成兩部分討論。首先 $j=0$ 表示要執行到根節點。若某 subtree 有 r 個節點，則根節點的機率為 $\frac{1}{r}$。允許 $\Theta(log\ n)$ 的誤差，從 perfect binary tree 的倒數第 2 層(第 $k-2$ 層)來看，約有 $\frac{n}{2^2}$ 個子樹，每個子樹有 3 個節點。再往上一層(第 $k-3$ 層)，約有 $\frac{n}{2^3}$ 個子樹，每個子樹有 7 個節點。所以可以推算當有 $\frac{n}{2^h}$ 個子樹，每個子樹會有 $2^h-1$ 個節點。所以根節點的機率為 $\frac{1}{2^h-1}$。計算 $E(T)$ 中 $j=0$ 的部分，$\beta n+\Theta(log\ n)$，其中
$$
\beta=\sum_{h=2}^{\infty} \frac{1}{2^h(2^h-1)}=0.1066952...
$$

接下來計算 $E(T)$ 中 $j=d$ 的部分。在原版 heapsort 的 reheap 中，比較次數為 $c$，interchange 次數為 $i$，special object 的子代節點數量為 $s$。可以用算式 $c=2i+s$ 表示。interchange 的係數為 2 是因為 reheap 要先比較該節點的兩個子節點的數值大小，再比較該節點和其子節點中數值小的節點，才會進行 interchange。而 s 是因為 $j=d$ 的情況下，reheap 會一直往下直到葉節點，所以比較次數和 special path 的最後一組子代節點有關。接下來透過隨機變數 $C,I,S$ 代表 $c,i,s$ 的總和。而 $E(C), E(I)$ 在前面論文有直接提供。

$$
\begin{aligned}
E(S) &= E(C)-2E(I)\\
&= [(\alpha_1+2\alpha_2-2)n+\Theta(log\ n)]-2[(\alpha_1+\alpha_2-2)n+\Theta(log\ n)]\\
&= (-\alpha_1+2)n+\Theta(log\ n)
\end{aligned}
$$

要計算 $E(T)$ 中 $j=d$，也就是要計算 special object 在葉節點的期望值。所以透過 $E(S)$ 來計算 $s=0$ 的期望值，也就是 special object 沒有子代節點的情況。$s$ 有三種可能性，$s\in \{0,1,2\}$。其中 $s=1$ 的情況如下圖，$s=1$ 的情況表示 special object 為 5 號節點，且 reheap 的節點在 $1 \to 2 \to 5 \to 10$ 的路徑上才會發生，共 $log\ n$ 次。當 $n$ 夠大時可以忽略。
所以計算 $s \in \{0,2\}$，而 $E(S) = \lfloor \frac{n}{2} \rfloor \times E(s)$。$p_{s=0}, p_{s=2}$ 為 $s=0$ 和 $s=2$ 的機率。
$$
\begin{aligned}
E(s)&=0 \times p_{s=0}+2 \times p_{s=2}\\
&= 2 \times p_{s=2}\\
\lfloor \frac{n}{2} \rfloor \times E(s) &= p_{s=2} \times \lfloor \frac{n}{2} \rfloor \times 2\\
E(S) &= p_{s=2} \times \lfloor \frac{n}{2} \rfloor \times 2\\
p_{s=2} &= \frac{E(S)}{\lfloor \frac{n}{2} \rfloor} \times \frac{1}{2}\\
&= 2-\alpha_1 + \Theta(n^{-1}log\ n)
\end{aligned}
$$
而 $p_{s=0}$ 則為 $1-p_{s=2}$，所以 $p_{s=0} = \alpha_1 - 1+\Theta (n^{-1}log\ n)$。接下來可以計算 $E(T)$ 中 $j=d$ 的部分，也就是
$$
\lfloor \frac{n}{2} \rfloor p_{s=0} = (\frac{\alpha_1}{2}-\frac{1}{2})n+\Theta(log\ n)
$$
總和 $j=0,j=d$，計算出 $E(T)=(\frac{\alpha_1}{2}-\frac{1}{2}+\beta)n+\Theta(log\ n)$，再帶回計算 $E(L_{BUS})$
$$
\begin{aligned}
E(L_{BUS}) &= (3-\frac{\alpha_1}{2}-\alpha_2)n+E(T)+\Theta(log\ n)\\
&= (\frac{7}{2}-\alpha_1-\alpha_2+\beta)n+\Theta(log\ n)
\end{aligned}
$$
所以可以總結出在 heap creation phase 的 buttom-up reheap 的比較次數為
$$
\begin{aligned}
n+\Theta(log\ n) + E(L_{BUS})&=n + \Theta(log\ n) + (\frac{7}{2}-\alpha_1-\alpha_2 +\beta)n + \Theta(log\ n)\\
&=(\frac{9}{2}-\alpha_1-\alpha_2 +\beta)n + \Theta(log\ n)\\
&\approx 1.649271n
\end{aligned}
$$

#### Selection phase