# 2024q1 Homework6 (integration)
contributed by < `yeh-sudo` >
## 開發環境
```shell
$ uname -a
Linux andyyeh-ubuntu 6.5.0-21-generic #21~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb 9 13:32:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800HS with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5788.79
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 4 MiB (8 instances)
L3: 8 MiB (2 instances)
```
---
## 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉
### 建構核心模組
進行編譯：
```shell
make -C /lib/modules/`uname -r`/build M=$PWD module
```
依照 [The Linux Kernel document](https://docs.kernel.org/kbuild/modules.html) ，命令的形式如下：
```shell
make -C $KDIR M=$PWD [target]
```
- [ ] `-C $KDIR`
`$KDIR` 這個路徑為核心程式碼的位置，執行 `make` 命令時，會切換到指定的目錄，完成後再切換回來。
- [ ] `M=$PWD`
提醒 kbuild 此時正在編譯外部模組，而 `M` 則代表外部模組檔案所在的路徑。
- [ ] `[target]`
* `modules`: 在 `$PWD` 建構模組，此參數為預設值，所以不用特別打出來，使用此參數不會對核心做出更動。
* `modules_install`: 編譯完之後會直接安裝模組。
* `clean`: 移除編譯所生成的檔案。
* `help`: 列出可以使用的參數。
編譯後的訊息顯示我的編譯器版本與核心開發套件所使用的不一致。
```shell
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
```
使用 `ls /usr/bin/ -l` 看到， 我的 `gcc-12` 是連結 `x86_64-linux-gnu-gcc-12` 的，所以兩個 gcc 版本是一樣的，所以我就忽略了這個警告。
```shell
➜ andyyeh@andyyeh-ubuntu ~ ls /usr/bin/ -l | grep gcc
lrwxrwxrwx 1 root root 23 May 13 2023 gcc-12 -> x86_64-linux-gnu-gcc-12
```
### 掛載核心模組
掛載編譯出來的模組：
```shell
sudo insmod hello.ko
```
接著查看是否掛載成功：
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/mod_test sudo dmesg | grep Hello
[ 2141.536990] Hello, world
```
### 卸載核心模組
進行卸載：
```shell
sudo rmmod hello
```
查看是否卸載成功：
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/mod_test sudo dmesg | grep Goodbye
[ 2292.659951] Goodbye, cruel world
```
### `insmod`
透過 strace 來追蹤使用 `insmod` 載入模組時，使用了哪些系統呼叫。
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/fibdrv git:(master) ✗ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7fff0e130a18 /* 26 vars */) = 0
...
getcwd("/home/andyyeh/linux2024/fibdrv", 4096) = 31
newfstatat(AT_FDCWD, "/home/andyyeh/linux2024/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274792, ...}, 0) = 0
openat(AT_FDCWD, "/home/andyyeh/linux2024/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=274792, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274792, PROT_READ, MAP_PRIVATE, 3, 0) = 0x743e55fa4000
finit_module(3, "", 0) = 0
munmap(0x743e55fa4000, 274792) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
其中的 `finit_module` 作用為將編譯出來的 ELF 格式的 obejct file 載入核心中， 首先，這個系統呼叫會先呼叫 `idempotent_init_module` ，而這個函式又會呼叫 `init_module_from_file` ，接著才會呼叫到 `load_module` ，其中， Linux 核心使用 `struct module` 這個結構來儲存模組的相關資訊。
- [ ] `/include/linux/module.h`
```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];
```
- [ ] `/kernel/module/main.c`
在 `load_module` 中，就會使用 `add_unformed_module` 這個函式，將模組加入到核心中保存模組的鏈結串列，加入時用到的就是 `struct module` 中定義的 `struct list_head list` 。
```c
/*
* Allocate and load the module: note that size of section 0 is always
* zero, and we rely on this for optional sections.
*/
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
...
/* Reserve our place in the list. */
err = add_unformed_module(mod);
if (err)
goto free_module;
...
}
```
將模組載入鏈結串列時，使用到了 RCU 同步機制，允許多個 reader 在單一 writer 更新資料的同時，得以在不需要 lock 的前提，正確讀取資料。
```c
static int add_unformed_module(struct module *mod)
{
...
mod_update_bounds(mod);
list_add_rcu(&mod->list, &modules);
mod_tree_insert(mod);
...
}
```
在 `load_module` 函式中呼叫了 `complete_formation` ，其中，必須要檢查有沒有重複的符號 (symbol) ，因此呼叫了 `verify_exported_symbols` ，在這個函式中使用了 `find_symbol` 去尋找有沒有重複的符號。
- [ ] `kernel/module/main.c`
函式中也使用了 RCU 的機制，使用 `list_for_each_entry_rcu` 遍歷整個 `modules` 的鏈結串列。
```c
/*
* Find an exported symbol and return it, along with, (optional) crc and
* (optional) module which owns it. Needs preempt disabled or module_mutex.
*/
bool find_symbol(struct find_symbol_arg *fsa)
{
...
list_for_each_entry_rcu(mod, &modules, list,
lockdep_is_held(&module_mutex)) {
struct symsearch arr[] = {
{ mod->syms, mod->syms + mod->num_syms, mod->crcs,
NOT_GPL_ONLY },
{ mod->gpl_syms, mod->gpl_syms + mod->num_gpl_syms,
mod->gpl_crcs,
GPL_ONLY },
};
if (mod->state == MODULE_STATE_UNFORMED)
continue;
for (i = 0; i < ARRAY_SIZE(arr); i++)
if (find_exported_symbol_in_section(&arr[i], mod, fsa))
return true;
}
...
}
```
所以當 Linux 核心要使用或是尋找模組的資訊時，只要遍歷儲存模組的鏈結串列就可以得到想要的資訊。
#### 追蹤程式執行流程
使用〈[建構 User-Mode Linux 的實驗環境](https://hackmd.io/@sysprog/user-mode-linux-env#%E6%90%AD%E9%85%8D-GDB-%E9%80%B2%E8%A1%8C%E6%A0%B8%E5%BF%83%E8%BF%BD%E8%B9%A4%E5%92%8C%E5%88%86%E6%9E%90)〉中的方法，使用 GDB 對 `insmod` 進行追蹤。在 `idempotent_init_module` 這個函式新增斷點，到最後確實有執行到 `load_module` 。
```shell
/ # insmod hello.ko
Thread 1 "vmlinux" hit Breakpoint 1, 0x000000006007c6f1 in idempotent_init_module (flags=<optimized out>, uargs=<optimized out>, f=<optimized out>) at kernel/module/main.c:3164
3164 return -EBADF;
...
1036 WRITE_ONCE(n->pprev, &h->first);
(gdb) s
idempotent_init_module (flags=0, uargs=<optimized out>, f=0x60a77600) at kernel/module/main.c:3173
3173 return idempotent_complete(&idem,
(gdb) s
init_module_from_file (f=f@entry=0x60a77600, uargs=uargs@entry=0x40097ca0 <error: Cannot access memory at address 0x40097ca0>, flags=flags@entry=0) at kernel/module/main.c:3132
3132 {
(gdb) s
3133 struct load_info info = { };
(gdb) n
3134 void *buf = NULL;
(gdb) n
3137 len = kernel_read_file(f, 0, &buf, INT_MAX, NULL, READING_MODULE);
(gdb) n
3138 if (len < 0) {
(gdb) n
3143 if (flags & MODULE_INIT_COMPRESSED_FILE) {
(gdb) n
3152 info.hdr = buf;
(gdb) n
3153 info.len = len;
(gdb) s
3156 return load_module(&info, uargs, flags);
(gdb) s
load_module (info=info@entry=0x648a7d90, uargs=uargs@entry=0x40097ca0 <error: Cannot access memory at address 0x40097ca0>, flags=flags@entry=0) at kernel/module/main.c:2838
2838 {
```
接著查看 `modules` 鏈結串列中的值，確認 `hello` 模組是否有被載入到核心中。
```shell
/ # lsmod
Module Size Used by Tainted: G
hello 12288 0
/ #
Thread 1 "vmlinux" received signal SIGUSR1, User defined signal 1.
0x00007ffff7c427dc in __GI___sigsuspend (set=set@entry=0x604fbda0) at ../sysdeps/unix/sysv/linux/sigsuspend.c:26
26 in ../sysdeps/unix/sysv/linux/sigsuspend.c
(gdb) p $container_of(modules->next, "struct module", "list")->name
$2 = "hello", '\000' <repeats 50 times>
```
### MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響
在 `find_symbol` 這個函式中，會透過 `find_exported_symbol_in_section` 來檢查模組是否符合 GPL 的授權條款，若不符合，模組就不會被載入到核心中。在 `load_module` 中，就會直接跳到 `ddebug_cleanup` 這個地方，透過 `ftrace_release_mod` 將加入鏈結串列的模組移除。
```c
ddebug_cleanup:
ftrace_release_mod(mod);
synchronize_rcu();
kfree(mod->args);
```
當我把 `fibdrv` 的 `MODULE_LICENSE` 修改成 Proprietary ，就會顯示錯誤，因為不符合 GPL 的條款，所以沒辦法使用 GPL 授權的 `class_create` 等函式，非 GPL 與 GPL 的模組無法進行互動。
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/fibdrv git:(master) ✗ make all
...
ERROR: modpost: GPL-incompatible module fibdrv.ko uses GPL-only symbol 'class_create'
ERROR: modpost: GPL-incompatible module fibdrv.ko uses GPL-only symbol 'device_create'
ERROR: modpost: GPL-incompatible module fibdrv.ko uses GPL-only symbol 'class_destroy'
ERROR: modpost: GPL-incompatible module fibdrv.ko uses GPL-only symbol 'device_destroy'
...
```
#### 為何有這種規範？
> [Linux GPL and binary module exception clause?](https://lkml.org/lkml/2003/12/3/177)
在 2003 年 12 月 3 日， Kendall Bennett 問了一個問題， Linux GPL and binary module exception clause? 其中寫到，雖然 Linux 核心是使用 GPL 授權條款，但是核心模組可以是其他種授權條款，不需要使用 GPL 的授權條款。
> I have heard many people reference the fact that the although the Linux
Kernel is under the GNU GPL license, that the code is licensed with an
exception clause that says binary loadable modules do not have to be
under the GPL.
結果 Linus Torvalds 就出來回應了，他說，沒有這種例外的模組存在，只要是 Linux 核心的衍生作品 (derived work) ，就必須要使用 GPL 的授權條款，所以，核心模組也不例外，一定要是 GPL 授權條款。
> Basically:
> - anything that was written with Linux in mind (whether it then _also_
works on other operating systems or not) is clearly partially a derived
work.
> - anything that has knowledge of and plays with fundamental internal
Linux behaviour is clearly a derived work. If you need to muck around
with core code, you're derived, no question about it.
另外，在這篇 [Making life (even) harder for proprietary modules](https://lwn.net/Articles/939842/) 文章中也說明了為何只使用 GPL-only 的程式碼，是為了避免侵權，因為 Linux 核心沒辦法有效的判斷一個模組是否為 Linux Torvalds 口中的 derived work ，所以採用了這種機制來確保不會有法律上的疑慮。而且 GPL 這個協議中有規範，若使用者使用了這個程式碼，則他也必須進行開源，若不開源，則不能使用，所以，模組中也有可能使用了 GPL 授權條款的程式碼，所以模組也必須要進行開源，否則違反 GPL 協議，網路上也查的到因為違反 GPL 協議而受到法律制裁的案例。
> Distributing a proprietary module might be a copyright violation, though, if the module itself is a derived work of the kernel code. But "derived work" is a fuzzy concept, and the kernel itself cannot really make that judgment. There is a longstanding mechanism in the kernel designed to keep infringing modules out, though: GPL-only exports.
:::info
Linux 社群對於 GPL 條款的紛爭歷史真的好長，其中還有提到 Nvidia 等著名公司，還有許多 [patch](https://lwn.net/ml/linux-kernel/20230731083806.453036-2-hch@lst.de/) 針對 GPL 相關的程式碼進行修改，不知道這部份的討論能不能當作期末專題？
:::
### Linux 核心的掛載，涉及哪些系統呼叫和子系統
在 [`syscall`](https://man7.org/linux/man-pages/man2/syscalls.2.html) 的 manual page 中可以找到 `insmod` 所呼叫的系統呼叫。
#### [`execve`](https://man7.org/linux/man-pages/man2/execve.2.html)
`execve` 會執行參數 `pathname` 指定的程式，必須要是一個執行檔或是 interpreter scripts ，呼叫 `execve` 的行程當中正在執行的程式會被替換成新的程式，且具有新的堆疊和堆積，以及新的資料區段。
#### [`brk`](https://man7.org/linux/man-pages/man2/brk.2.html)
當傳入的值是合理的，且系統有足夠的記憶體空間，行程沒有超出他的最大資料大小時， `brk` 會將資料區段結束的位置設置為其傳入的參數 `addr` 。
#### [`arch_prctl`](https://man7.org/linux/man-pages/man2/arch_prctl.2.html)
這個系統呼叫可以設定特定架構下的行程或是執行緒的狀態。
:::warning
還有很多...
:::
---
## 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》
### [simrupt](https://github.com/sysprog21/simrupt) 程式碼中的 mutex lock
#### `read_lock`
在 `simrupt_read` 這個函式中，使用 `mutex_lock_interruptible` 對 `read_lock` 進行加鎖，若沒有拿到鎖，則回傳 `-EINTR` ，若有拿到鎖，就回傳 0 ，防止多個 reader 同時進入 critical section 去對 `kfifo` 進行操作。拿到鎖之後，會使用 `kfifo_to_user` 將 `kfifo` 中的資料複製到 user space
在核心模組的進入點 `simrupt_init` ，就有使用 `simrupt_fops` 將 `simrupt_read` 註冊為讀取這個 character device 會執行的函式，在讀取時，就會持續使用 `kfifo_to_user` 將 `kfifo` 中的資料持續複製到 user space ，使用 `cat` 命令讀取，就可以得到 `kfifo_to_user` 放入 `buf` 中的資料以顯示在終端機上。
```c
static ssize_t simrupt_read(struct file *file,
char __user *buf,
size_t count,
loff_t *ppos)
{
unsigned int read;
int ret;
pr_debug("simrupt: %s(%p, %zd, %lld)\n", __func__, buf, count, *ppos);
if (unlikely(!access_ok(buf, count)))
return -EFAULT;
if (mutex_lock_interruptible(&read_lock))
return -ERESTARTSYS;
```
#### `producer_lock`, `consumer_lock`
`consumer_lock` 確保在多個 writer 的情況下，不會有多個 writer 同時要進行 `fast_buf_get` 將 `fast_buf` 中的資料取出，`producer_lock` 防止在多個 writer 的情況下，同時進行 `produce_data` 將資料存放入 `kfifo` 。
使用 `DECLARE_WORK` 巨集將 `work` 指向 `simrupt_work_func` 函式，接著在 `simrupt_tasklet_func` 中將 `work` 放入 `simrupt_workqueue` ， Linux 核心會使用 Complete Fair Scheduler 去執行 `simrupt_workqueue` 中的任務。
```c
/* Workqueue handler: executed by a kernel thread */
static void simrupt_work_func(struct work_struct *w)
{
...
while (1) {
/* Consume data from the circular buffer */
mutex_lock(&consumer_lock);
val = fast_buf_get();
mutex_unlock(&consumer_lock);
if (val < 0)
break;
/* Store data to the kfifo buffer */
mutex_lock(&producer_lock);
produce_data(val);
mutex_unlock(&producer_lock);
}
wake_up_interruptible(&rx_wait);
}
```
### 追蹤程式執行
---
## [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html)
### worker-pools 如何指定 Bound 來分配及限制特定 worker 執行於指定的 CPU
建立 work queue 時使用的是 `alloc_workqueue` ，其中的第二個參數需要傳入 [flags](https://www.kernel.org/doc/html/latest/core-api/workqueue.html#flags) ，在 CMWQ 的文件中有很詳細的介紹，在 simrupt 專案中，建立 work queue 使用的是 `WQ_UNBOUND` 這個 flag ，代表被加入到該 queue 中的 work 是由不指定 CPU 的特殊 worker-pools 所服務的。這種情況下核心不會對該 work queue 提供並行管理， worker-pools 會嘗試盡快開始執行 work queue 中的 work 但使用 `WQ_UNBOUND` 這個 flag 犧牲了 cache locality ，但在一些 CPU 密集型的任務上會很有用。
> Work items queued to an unbound wq are served by the special worker-pools which host workers which are not bound to any specific CPU. This makes the wq behave as a simple execution context provider without concurrency management. The unbound worker-pools try to start execution of work items as soon as possible.
使用 `WQ_UNBOUND` 這個參數時，執行 `sudo cat /dev/simrupt` 的結果，可以發現， `simrupt_work_func` 在很多不同的 CPU 上執行。
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/simrupt git:(main) sudo dmesg | grep simrupt_work_func
...
[ 9908.032725] simrupt: [CPU#0] simrupt_work_func
[ 9908.136392] simrupt: [CPU#0] simrupt_work_func
[ 9908.244375] simrupt: [CPU#0] simrupt_work_func
[ 9908.348636] simrupt: [CPU#0] simrupt_work_func
[ 9908.452656] simrupt: [CPU#6] simrupt_work_func
[ 9908.556653] simrupt: [CPU#7] simrupt_work_func
[ 9908.660766] simrupt: [CPU#7] simrupt_work_func
[ 9908.764465] simrupt: [CPU#7] simrupt_work_func
[ 9908.868648] simrupt: [CPU#7] simrupt_work_func
[ 9908.972670] simrupt: [CPU#7] simrupt_work_func
[ 9909.076656] simrupt: [CPU#7] simrupt_work_func
[ 9909.180402] simrupt: [CPU#7] simrupt_work_func
[ 9909.284641] simrupt: [CPU#7] simrupt_work_func
[ 9909.388660] simrupt: [CPU#6] simrupt_work_func
[ 9909.492652] simrupt: [CPU#6] simrupt_work_func
[ 9909.596658] simrupt: [CPU#6] simrupt_work_func
[ 9909.700626] simrupt: [CPU#6] simrupt_work_func
[ 9909.804624] simrupt: [CPU#6] simrupt_work_func
[ 9909.908666] simrupt: [CPU#6] simrupt_work_func
[ 9910.012654] simrupt: [CPU#6] simrupt_work_func
[ 9910.116699] simrupt: [CPU#6] simrupt_work_func
[ 9910.220374] simrupt: [CPU#10] simrupt_work_func
[ 9910.324594] simrupt: [CPU#7] simrupt_work_func
[ 9910.428693] simrupt: [CPU#10] simrupt_work_func
[ 9910.532638] simrupt: [CPU#10] simrupt_work_func
[ 9910.636661] simrupt: [CPU#7] simrupt_work_func
[ 9910.740395] simrupt: [CPU#6] simrupt_work_func
[ 9910.844651] simrupt: [CPU#6] simrupt_work_func
[ 9910.948462] simrupt: [CPU#6] simrupt_work_func
```
而將 `WQ_UNBOUND` 這個 flag 去除之後，執行 `simrupt_work_func` 都會在同一個 CPU 上。
```shell
➜ andyyeh@andyyeh-ubuntu ~/linux2024/simrupt git:(main) sudo dmesg | grep simrupt_work_func
[10071.428340] simrupt: [CPU#2] simrupt_work_func
[10071.532446] simrupt: [CPU#2] simrupt_work_func
[10071.636625] simrupt: [CPU#2] simrupt_work_func
[10071.740649] simrupt: [CPU#2] simrupt_work_func
[10071.844666] simrupt: [CPU#2] simrupt_work_func
[10071.948397] simrupt: [CPU#2] simrupt_work_func
[10072.052628] simrupt: [CPU#2] simrupt_work_func
[10072.156372] simrupt: [CPU#2] simrupt_work_func
[10072.261169] simrupt: [CPU#2] simrupt_work_func
[10072.364337] simrupt: [CPU#2] simrupt_work_func
[10072.468346] simrupt: [CPU#2] simrupt_work_func
[10072.572443] simrupt: [CPU#2] simrupt_work_func
[10072.676665] simrupt: [CPU#2] simrupt_work_func
[10072.780345] simrupt: [CPU#2] simrupt_work_func
```
如果在呼叫 `alloc_workqueue` 時，傳入 `WQ_UNBOUND` 參數，在配置 work queue 時會呼叫到 `alloc_unbound_pwq` 配置 `pool_workqueue` ，在進行 `queue_work` 時，會使用 `wq_select_unbound_cpu` 選擇 CPU ，並在這個選定的 CPU 上執行，若沒有傳入 `WQ_UNBOUND` ，則會為每一個 CPU 都配置 `pool_workqueue` ，在進行 `queue_work` 時，則會在呼叫這個函式的 CPU 上運行。
### CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動
在初始化 work queue 時，進行的 `workqueue_init` 會建立 `worker_pool` 底下的 `worker` ，其中就包含 kernel thread ，執行 `queue_work` 將要執行的任務放入 work queue 中，最後會呼叫 `insert_work` 將任務插入其所屬的 `pool_workqueue` ，之後排程器就會對 `worker` 中的任務進行排程。
---
## `xoroshiro128+`
### 解釋 `xoroshiro128+` 的原理
### 比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度
Sign in with Wallet
Connect another wallet