# 2024q1 Homework6 (integration)
contributed by < [`hungyuhang`](https://github.com/hungyuhang) >
## 自我檢查清單
- [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 閱讀〈[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 核心的掛載，涉及哪些系統呼叫和子系統？
- [ ] 閱讀《[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);
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
- [ ] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
(https://blog.cruciferslab.net/?p=599)
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
## 自我檢查清單 - 筆記
### 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉筆記
#### 製作 hello world 核心模組
檢查 Linux 核心版本：
```
$ uname -r
6.5.0-28-generic
```
在用 make 命令編譯 hello 核心模組時，雖然可以成功編譯，但終端機出現下列敘述：
```
warning: the compiler differs from the one used to build the kernel
The kernel was built by: x86_64-linux-gnu-gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
You are using: gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
```
將 make 產生的 hello.ko 核心模組用 `insmod` 掛載後，可以透過 `dmesg` 命令看到 hello.ko 發出的核心訊息：
```
[ 3849.955965] Hello, world
```
使用 `rmmod` 卸載 hello 核心模組，並且用 `dmesg` 命令查看核心訊息：
```
[ 3849.955965] Hello, world
[ 4260.552598] Goodbye, cruel world
```
#### 解釋 `insmod`
`insmod` 會呼叫 [`finit_module`](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3177) 這個 system call ，而 `finit_module` 會透過下列程式呼叫去執行 fibdrv.c 中被 `module_init` 宏所設定的函式：
- 呼叫 `idempotent_init_module` ([kernel/module/main.c#L3159](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3159))
- 在上方函式裡，呼叫 `init_module_from_file` ([kernel/module/main.c#L3131](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3131))
- 在上方函式裡，呼叫 `load_module` ([kernel/module/main.c#L2836](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L2836))
- 在上方函式裡，呼叫 `do_init_module` ([kernel/module/main.c#L2509](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L2509))
- 在上方函式裡，呼叫 `do_one_initcall` ([init/main.c#L1234](https://elixir.bootlin.com/linux/latest/source/init/main.c#L1234))
- 最後，這個函式會叫 `module_init` 宏當中設定的函式（在這個例子中就是 `init_fib_dev` ）
同時，`insmod` 也需要將 user space 中 kernel module 的資料複製到 kernel space 中，這個操作是在 [`init_module_from_file`](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3131) 這個函式所做的：
```c
static int init_module_from_file(struct file *f, const char __user * uargs, int flags)
{
struct load_info info = { };
void *buf = NULL;
int len;
len = kernel_read_file(f, 0, &buf, INT_MAX, NULL, READING_MODULE);
if (len < 0) {
mod_stat_inc(&failed_kreads);
return len;
}
// ...
return load_module(&info, uargs, flags);
}
```
#### Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)
Linux 核心會維護一份鏈節串列 ，串列內的每一個節點都是一個核心模組的資訊（包含 symbol ）。這份鏈節串列可以使用 /proc/modules 這份文件來取得。
當使用 terminal 的時候，我們可以使用 [lsmod](https://man7.org/linux/man-pages/man8/lsmod.8.html) 這個工具程式來列出 /proc/modules 裡面所有紀錄的核心模組。
但如果我們想要在程式碼裡面去取用上述鏈節串列的內容，就需要仰賴 `THIS_MODULE` 物件。每個核心模組在程式碼中都會有一個相對應的 `THIS_MODULE` 物件，這個物件的資料型態為 `struct module` ，其定義可以在 [include/linux/module.h](https://elixir.bootlin.com/linux/latest/source/include/linux/module.h#L402) 中被找到：
```c
struct module {
enum module_state state;
/* Member of list of modules */
struct list_head list;
/* Unique handle for this module */
char name[MODULE_NAME_LEN];
// ...
#ifdef CONFIG_DYNAMIC_DEBUG_CORE
struct _ddebug_info dyndbg_info;
#endif
} ____cacheline_aligned __randomize_layout;
```
要拿到該鏈節串列，只要使用 `&THIS_MODULE->list` 就可以取得該鏈節串列的 list head ，接下來就可以使用 List API 來對這個鏈節串列進行操作了。
參考： [Linux Rootkits Part 5: Hiding Kernel Modules from Userspace](https://xcellerator.github.io/posts/linux_rootkits_05/)
#### `MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)
如果將沒有 GPL License 的核心模組加載到 Linux 核心的話， Linux 核心會將自己標記為「受污染的」 (tainted) （[參考](https://docs.kernel.org/admin-guide/tainted-kernels.html)）。以下是比較細節的流程：
當使用 `insmod` 來掛載核心模組時， `insmod` 會執行下列呼叫：
- 呼叫 `finit_module` system call ([kernel/module/main.c#L3177](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3177))
- 在上方函式裡，呼叫 `idempotent_init_module` ([kernel/module/main.c#L3159](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3159))
- 在上方函式裡，呼叫 `init_module_from_file` ([kernel/module/main.c#L3131](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L3131))
- 在上方函式裡，呼叫 `load_module` ([kernel/module/main.c#L2836](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L2836))
- 在上方函式裡，呼叫 `module_augment_kernel_taints` ([kernel/module/main.c#L2035](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L2035))
- 在上方函式裡，呼叫 `module_license_taint_check` ([kernel/module/main.c#L1582](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c#L1582))
當呼叫 `module_license_taint_check` 的時候， Linux 就會檢查核心模組的 License 並且做出相對應的動作。以下為 `module_license_taint_check` 的程式碼：
```c
static void module_license_taint_check(struct module *mod, const char *license)
{
if (!license)
license = "unspecified";
if (!license_is_gpl_compatible(license)) {
if (!test_taint(TAINT_PROPRIETARY_MODULE))
pr_warn("%s: module license '%s' taints kernel.\n",
mod->name, license);
add_taint_module(mod, TAINT_PROPRIETARY_MODULE,
LOCKDEP_NOW_UNRELIABLE);
}
}
```
程式碼會先透過 `license_is_gpl_compatible` 函式來檢查欲載入的核心模組是否為 GPL compatible ([Reference](https://docs.kernel.org/process/license-rules.html#id1)) ，如果不是 GPL compatible 的話， Linux 就會用 `add_taint_module` 函式將該模組標記為「受污染的」。
#### 藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
- 大量使用 openat 跟 close 系統呼叫來開啟或是關閉檔案。
- 使用 read 跟 newfstat 來讀取檔案內容或是資訊。
- 使用 mmap 來建立虛擬的記憶體。
以下是利用 strace 追蹤執行 `insmod fibdrv.ko` 的完整結果：
```shell
$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7ffee1a7da18 /* 27 vars */) = 0
brk(NULL) = 0x5c026a554000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffc0d1f94c0) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x76452f960000
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=88687, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 88687, PROT_READ, MAP_PRIVATE, 3, 0) = 0x76452f94a000
close(3) = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libzstd.so.1", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\0\0\0\0\0\0\0\0"..., 832) = 832
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=841808, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 843832, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x76452f87b000
mmap(0x76452f885000, 729088, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xa000) = 0x76452f885000
mmap(0x76452f937000, 69632, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xbc000) = 0x76452f937000
mmap(0x76452f948000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xcc000) = 0x76452f948000
close(3) = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/liblzma.so.5", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\0\0\0\0\0\0\0\0"..., 832) = 832
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=170456, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 172296, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x76452f850000
mmap(0x76452f853000, 110592, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x3000) = 0x76452f853000
mmap(0x76452f86e000, 45056, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e000) = 0x76452f86e000
mmap(0x76452f879000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x76452f879000
close(3) = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libcrypto.so.3", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\0\0\0\0\0\0\0\0"..., 832) = 832
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=4455728, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 4469952, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x76452f400000
mmap(0x76452f4b2000, 2486272, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xb2000) = 0x76452f4b2000
mmap(0x76452f711000, 860160, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x311000) = 0x76452f711000
mmap(0x76452f7e3000, 385024, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x3e2000) = 0x76452f7e3000
mmap(0x76452f841000, 9408, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x76452f841000
close(3) = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P\237\2\0\0\0\0\0"..., 832) = 832
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
pread64(3, "\4\0\0\0 \0\0\0\5\0\0\0GNU\0\2\0\0\300\4\0\0\0\3\0\0\0\0\0\0\0"..., 48, 848) = 48
pread64(3, "\4\0\0\0\24\0\0\0\3\0\0\0GNU\0\226 \25\252\235\23<l\274\3731\3540\5\226\327"..., 68, 896) = 68
newfstatat(3, "", {st_mode=S_IFREG|0755, st_size=2220400, ...}, AT_EMPTY_PATH) = 0
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
mmap(NULL, 2264656, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x76452f000000
mprotect(0x76452f028000, 2023424, PROT_NONE) = 0
mmap(0x76452f028000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x76452f028000
mmap(0x76452f1bd000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x76452f1bd000
mmap(0x76452f216000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x215000) = 0x76452f216000
mmap(0x76452f21c000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x76452f21c000
close(3) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x76452f84e000
arch_prctl(ARCH_SET_FS, 0x76452f84ec40) = 0
set_tid_address(0x76452f84ef10) = 9765
set_robust_list(0x76452f84ef20, 24) = 0
rseq(0x76452f84f5e0, 0x20, 0, 0x53053053) = 0
mprotect(0x76452f216000, 16384, PROT_READ) = 0
mprotect(0x76452f7e3000, 372736, PROT_READ) = 0
mprotect(0x76452f879000, 4096, PROT_READ) = 0
mprotect(0x76452f948000, 4096, PROT_READ) = 0
mprotect(0x5c0268f48000, 8192, PROT_READ) = 0
mprotect(0x76452f99a000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0x76452f94a000, 88687) = 0
getrandom("\xbb\xcd\xcf\xef\xb3\x85\x16\x61", 8, GRND_NONBLOCK) = 8
brk(NULL) = 0x5c026a554000
brk(0x5c026a575000) = 0x5c026a575000
uname({sysname="Linux", nodename="hungyuhang-ZenBook-UX434FQ-UX434FQ", ...}) = 0
openat(AT_FDCWD, "/lib/modules/6.5.0-28-generic/modules.softdep", O_RDONLY|O_CLOEXEC) = 3
fcntl(3, F_GETFL) = 0x8000 (flags O_RDONLY|O_LARGEFILE)
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=1991, ...}, AT_EMPTY_PATH) = 0
read(3, "# Soft dependencies extracted fr"..., 4096) = 1991
read(3, "", 4096) = 0
close(3) = 0
openat(AT_FDCWD, "/proc/cmdline", O_RDONLY|O_CLOEXEC) = 3
read(3, "BOOT_IMAGE=/boot/vmlinuz-6.5.0-2"..., 4095) = 105
read(3, "", 3990) = 0
close(3) = 0
getcwd("/home/hungyuhang/linux2024/hw6/fibdrv", 4096) = 38
newfstatat(AT_FDCWD, "/home/hungyuhang/linux2024/hw6/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274824, ...}, 0) = 0
openat(AT_FDCWD, "/home/hungyuhang/linux2024/hw6/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6) = 6
lseek(3, 0, SEEK_SET) = 0
newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=274824, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274824, PROT_READ, MAP_PRIVATE, 3, 0) = 0x76452f3bc000
finit_module(3, "", 0) = 0
munmap(0x76452f3bc000, 274824) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
Sign in with Wallet
Connect another wallet