# 2024q1 Homework6 (integration)
contributed by < `ranvd` >
## Linux 核心如何找到核心模組
> 以下內容為 Linux 核心版本 5.15，其他版本的檔案位置與內容可以有些出入
在過去的教材中有提到 LKM 在 Linux kernel 中是透過鍊結串列維護。在 [include/linux/module.h](https://github.com/torvalds/linux/blob/v5.15/include/linux/module.h) 中可以看到 module 結構體，其中可以看到有一項熟悉的結構體 `struct list_head`，根據註解可以猜測 Linux 核心中的 modules 是透過鍊結串列的方式儲存，同時也使用 enum 型態紀錄目前 module 的狀態。
```c
struct module {
...
/* Member of list of modules */
struct list_head list;
...
```
為了驗證 Linux Module 的載入方式如上述提到的鍊結串列，首先透過 strace 追蹤 insmod 命令在載入 LKM 時使用了哪些系統呼叫。從下面 `strace insmod` 的輸出結果可以看到，在第 1 行時將 hello.ko 打開，此時打開的 fd = 3，接著在第 6 行可以看到呼叫了 `finit_module` 這個系統呼叫。
```=
openat(AT_FDCWD, "/home/ranvd/Code/linux2024/lkm-test/hello/hello.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6) = 6
lseek(3, 0, SEEK_SET) = 0
fstat(3, {st_mode=S_IFREG|0664, st_size=218008, ...}) = 0
mmap(NULL, 218008, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fcece859000
finit_module(3, "", 0) = -1 EEXIST (File exists)
write(2, "insmod: ERROR: could not insert "..., 61insmod: ERROR: could not insert module hello.ko: File exists
) = 61
munmap(0x7fcece859000, 218008) = 0
close(3) = 0
exit_group(1) = ?
+++ exited with 1 +++
```
在 [kernel/module.c](https://github.com/torvalds/linux/blob/v5.15/kernel/module.c) 中可以看到以下的程式碼。`finit_module` 首先是透過 `kernel_read_file_from_fd` 將整個 Linux 核心模組讀取到 kernel space 後呼叫了 `load_module` 將 Linux 核心模組載入。
```c
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
...
err = kernel_read_file_from_fd(fd, 0, &hdr, INT_MAX, NULL,
READING_MODULE);
if (err < 0)
return err;
info.hdr = hdr;
info.len = err;
return load_module(&info, uargs, flags);
}
```
接著透過 `load_module` 的程式碼可以看到 `load_module` 透過 `layout_and_allocate` 配置了一個 module 的記憶體空間，接著再透過 `add_unformed_module` 將該核心模組加入鍊結串列中。最後透過 `do_init_module` 將載入的核心模組初始化。
```c
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
struct module *mod;
...
/* Figure out module layout, and allocate all the memory. */
mod = layout_and_allocate(info, flags);
...
/* Reserve our place in the list. */
err = add_unformed_module(mod);
...
return do_init_module(mod);
...
}
```
最後，為了驗證上述的結果，透過第第七周的教材 [建構 User-Mode Linux 的實驗環境](https://hackmd.io/@sysprog/user-mode-linux-env)，使用 GDB 對 UML 的行為進行觀測。首先是設立中斷點在 `finit_module` 系統呼叫，不過從上面系統呼叫的宣告方式，可以知道 `finit_module` 這並不是真正系統呼叫函式的名稱，在對著程式碼『舉燭』過後，並結合過去教材提供的連結 [How does the Linux kernel handle a system call](https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-2.html) 得知這些系統呼叫的名稱是透過腳本與 .tbl 在編譯時自動生成的。因此根據 [syscall_64.tbl](https://github.com/torvalds/linux/blob/v5.15/arch/x86/entry/syscalls/syscall_64.tbl) 可以輕易得知正確的系統呼叫名稱為 `sys_finit_module`。
接著就進行 debug，從 GDB 的訊息中可以看到每個模組之間確實適用開頭提到的鍊結串列維護。
```shell
(gdb) p $container_of(modules.next, "struct module", "list")->name
$11 = "hello", '\000' <repeats 50 times>
(gdb) p $container_of(modules.next->next, "struct module", "list")->name
$12 = "isofs", '\000' <repeats 50 times>
```
## LKM 指定的授權條款對核心的影響
## 解釋 simrupt 內 mutex lock 使用方式
## 探討 Timsort, pdqsort, heapsort 比較次數
### Timsort
### pdqsort
### heapsort
Heapsort 的方式如下，先透過 bottom-up 的方式建立 heap，接著再透過不斷將根節點與未排序的最後一個節點交換，並維持 heap 的特性。直到所有的節點都排序好即可。複雜度為 $O(n\log n)$。
:::info
**HEAPSORT(input: a, len: n)**:
for (i = $\lfloor$n/2$\rfloor$ to 1):
  **reheap(n, i)**
for (m = n to 2):
  **interchange** a[1] and a[m]
  in m != 2 then **reheap(m-1, 1)**
:::
在 Linux 核心早期的 lib/sort.c ([1da177e](https://github.com/torvalds/linux/blob/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2/lib/sort.c)) 以下稱這種方式為 Standard heapsort。heapify 的方式為由上而下尋找最小的節點，因此每層都會需要 2 次比較。從 [22a241c](https://github.com/torvalds/linux/commit/22a241ccb2c19962a0fb02c98154aa93d3fc1862) 開始，就採用與現在較為相近的 heapsort 方式 Bottom-up heapsort，由於程式碼將 Heapify 與 Sorting 兩個部分寫在同一個 for 迴圈中，導致我花了一些時間才看懂他的實作如何對照 [BOTTOM-UP-HEAPSORT](https://www.sciencedirect.com/science/article/pii/030439759390364Y)。以下稱作 Bottom-up heapsort。Bottom-up heapsort 與傳統 heapsort 最主要的差別在於減少 reheap 時的比較次數。
Bottom-up heapsort 將原本 reheap 的部份改成 bottom-up-reheap
:::info
**bottom-up-reheap(m, i):**
j = **leaf-search(m, i)**
j = **bottom-up-search(i, j)**
**interchange(i, j)**
:::
首先會由上至下比較左右兩個子節點的大小，選擇較小的方向走。如下演算法，由於只需要比較左右子節點，因此只需要做一次比較，所以 leaf-search 最多只會需要做 d 次比較，d 是樹的深度。
:::info
**leaf-search(m, i):**
j = i
while 2j < m:
  if (a[2j] < a[2j+1]):
    j = 2j
  else:
    j = 2j + 1
if (2j == m):
  j = m
**return j**
:::
上述找到的 j 稱作 special leaf，過程中經過的路徑稱作 special path。接著我們要順著這個路徑由下至上尋找 reheap 中的 i 應該要放的正確位置。由於 heap 是 complete binary tree，因此尋找父節點可以透過簡單的 $\lfloor$n/2$\rfloor$ 得到正確的位置。如下演算法。
:::info
**bottom-up-search(i, j):**
while (j AND a[i] < a[j]):
  j = $\lfloor$j/2$\rfloor$
**return j**
:::
最後，找到正確的位置後，就可以將資料從 j 開始不斷向上做交換直到根節點。
:::info
**interchange(i, j):**
l = $\lfloor$log(j/i)$\rfloor$, x=a[j], a[j]=a[i]
while (j > i):
  interchange a[$\lfloor$j/2$\rfloor$] and x
  j = $\lfloor$j/2$\rfloor$
:::
### Average Case 分析
**建立 Heap 時 leaf-search 的比較次數**
首先，先考慮建立 heap 時的 leaf-search 比較次數，假設 heap 是 full binary tree。則我們會有 $n=2^{k}-1$ 個節點。從 full binary tree 的特性我們可以知道深度 k 的節點會有 $2^{k}$ 個節點。而越靠進葉節點的 inner nodes 需要的比較次是越少，因此可以列出需要比較的次數 $l$ 介於 $1\le l\le k-1$。
從上面可以得知在 full binary tree 中需要的總比較次為 $$\sum_{1\le l\le k-1}l2^{k-l-1}=1\cdot2^{k-2}+2\cdot2^{k-3}+\cdots+(k-1)\cdot2^0$$$$=2^{k-2}({1\over2^0}+{2\over2^1}+{3\over2^2}+\cdots+{k-1\over2^{k-2}})$$$$=2^{k-1}({1\over2^1}+{2\over2^2}+{3\over2^3}+\cdots+{k-1\over2^{k-1}})$$
接著令 $S=({1\over2^1}+{2\over2^2}+{3\over2^3}+\cdots+{k-1\over2^{k-1}})$ 可知 $2S=({1}+{2\over2^1}+{3\over2^2}+\cdots+{k-1\over2^{k-2}})$，接著可知 $$S=2S-S=1+{1\over2^1}+{1\over2^2}+\cdots+{1\over2^{k-2}}-{k-1\over2^{k-1}}$$ 接著透過等比數列和公式可知 $S=2-2^{k-2}-{k-1\over2^{k-1}}$，將 $S$ 代回公式可知 $$\sum_{1\le l\le k-1}l2^{k-l-1}=2^{k-1}(2-{1\over2^{k-2}}-{k-1\over2^{k-1}})=2^k-1-k=n-\lceil\log(n+1)\rceil$$
接著考慮非 full binary tree 的情況。令 $i=n-(2^k-1)$，其中 $n$ 代表節點的總數，$2^k-1$ 代表上一層的 full binary tree。因此 $i$ 代表多出來的節點個數。由於每多 $i$ 個節點就會增加 $\sum_{1\le r\le k}\lceil(i-1)/2^r\rceil$ 個內部節點。而每個內部節點都須增加 1 個比較次數，因此最多只有可能增加 $i-2+k$ 次比較。
以下提供簡單的思考方式說明為什麼 $\sum_{1\le r\le k}\lceil(i-1)/2^r\rceil\le i-2+k$。由於在多出來的 $i$ 之上的二元樹狀結構中，最多會有 $i-1$ 個內部節點會被更新，接著離開樹狀結構後，需要一路更新內部節點到根節點，最多會有 $k-1$ 個節點。因此最差的情況為 $i-2+k$。從前述資訊可知道在非 full binary tree 的情況下的總比較次數為 $2^k-1-k+i-2+k$ $=n-2$
**建立 Heap 時 leaf-search 的比較次數**
接著，考慮建立 heap 時的 bottom-up-search 比較次數。令 $l_{HS}$ 為傳統 Heapsort 須使用的比較次數的一半、$l_{BUS}$ 為 Bottom-up-search 所需的比較次數。
當 j <
Sign in with Wallet
Connect another wallet