2024q1 Homework6 (integration)

contributed by < ranvd >

Linux 核心如何找到核心模組

以下內容為 Linux 核心版本 5.15，其他版本的檔案位置與內容可以有些出入

在過去的教材中有提到 LKM 在 Linux kernel 中是透過鍊結串列維護。在 include/linux/module.h 中可以看到 module 結構體，其中可以看到有一項熟悉的結構體 struct list_head，根據註解可以猜測 Linux 核心中的 modules 是透過鍊結串列的方式儲存，同時也使用 enum 型態紀錄目前 module 的狀態。

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 中可以看到以下的程式碼。finit_module 首先是透過 kernel_read_file_from_fd 將整個 Linux 核心模組讀取到 kernel space 後呼叫了 load_module 將 Linux 核心模組載入。

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 將載入的核心模組初始化。

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 的實驗環境，使用 GDB 對 UML 的行為進行觀測。首先是設立中斷點在 finit_module 系統呼叫，不過從上面系統呼叫的宣告方式，可以知道 finit_module 這並不是真正系統呼叫函式的名稱，在對著程式碼『舉燭』過後，並結合過去教材提供的連結 How does the Linux kernel handle a system call 得知這些系統呼叫的名稱是透過腳本與 .tbl 在編譯時自動生成的。因此根據 syscall_64.tbl 可以輕易得知正確的系統呼叫名稱為 sys_finit_module。

接著就進行 debug，從 GDB 的訊息中可以看到每個模組之間確實適用開頭提到的鍊結串列維護。

(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)$。

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) 以下稱這種方式為 Standard heapsort。heapify 的方式為由上而下尋找最小的節點，因此每層都會需要 2 次比較。從 22a241c 開始，就採用與現在較為相近的 heapsort 方式 Bottom-up heapsort，由於程式碼將 Heapify 與 Sorting 兩個部分寫在同一個 for 迴圈中，導致我花了一些時間才看懂他的實作如何對照 BOTTOM-UP-HEAPSORT。以下稱作 Bottom-up heapsort。Bottom-up heapsort 與傳統 heapsort 最主要的差別在於減少 reheap 時的比較次數。

Bottom-up heapsort 將原本 reheap 的部份改成 bottom-up-reheap

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

首先會由上至下比較左右兩個子節點的大小，選擇較小的方向走。如下演算法，由於只需要比較左右子節點，因此只需要做一次比較，所以 leaf-search 最多只會需要做 d 次比較，d 是樹的深度。

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$ 得到正確的位置。如下演算法。

bottom-up-search(i, j):
while (j AND a[i] < a[j]):
  j =

$\lfloor$j/2

$\rfloor$

return j

最後，找到正確的位置後，就可以將資料從 j 開始不斷向上做交換直到根節點。

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}l{2}^{k-l-1}=1\cdot 2^{k-2}+2\cdot 2^{k-3}+\cdots +(k-1)\cdot 2^0$$

$$=2^{k-2}(\frac{1}{2^0}+\frac{2}{2^1}+\frac{3}{2^2}+\cdots +\frac{k-1}{2^{k-2}})$$

$$=2^{k-1}(\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{k-1}{2^{k-1}})$$

接著令

$S=(\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{k-1}{2^{k-1}})$ 可知

$2S=(1+\frac{2}{2^1}+\frac{3}{2^2}+\cdots +\frac{k-1}{2^{k-2}})$，接著可知

$$S=2S-S=1+\frac{1}{2^1}+\frac{1}{2^2}+\cdots +\frac{1}{2^{k-2}}-\frac{k-1}{2^{k-1}}$$ 接著透過等比數列和公式可知

$S=2-2^{k-2}-\frac{k-1}{2^{k-1}}$，將

$S$ 代回公式可知

$$\sum _{1\le l\le k-1}l{2}^{k-l-1}=2^{k-1}(2-\frac{1}{2^{k-2}}-\frac{k-1}{2^{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 <