# 2024q1 Homework6 (integration)
## 開發環境
$ 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 5
CPU max MHz: 4800.0000
CPU min MHz: 800.0000
BogoMIPS: 5799.77
## 自我檢查清單
- [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 核心的掛載，涉及哪些些系統呼叫和子系統？
### 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉筆記
`MODULE_LICENSE` 在 [/include/linux/module.h](https://elixir.bootlin.com/linux/latest/source/include/linux/module.h#L186) 定義如下
```c
#define MODULE_LICENSE(_license) MODULE_FILE MODULE_INFO(license, _license)
```
共有 `GPL`, `GPL v2`, `GPL and additional rights`, `Dual BSD/GPL`, `Dual MIT/GPL`, `Dual MPL/GPL` 用來標示模組為自由軟體模組，非自由則是 `Proprietary`。
這些標記的理由如下
>1. So modinfo can show license info for users wanting to vet their setup is free
>2. So the community can ignore bug reports including proprietary modules
>3. So vendors can do likewise based on their own policies
看註解時看到 `EXPORT_SYMBOL_GPL` 這個巨集，它的用途是導出給定的 symbol 給其他模組使用。但是該模組必須遵循 GPL 規範，也就是說如果模組是 `Proprietary` 則無法使用 `EXPORT_SYMBOL_GPL` 導出的 symbol
>The sole purpose is to make the 'Proprietary' flagging work and to refuse to bind symbols which are exported with EXPORT_SYMBOL_GPL when a non free module is loaded.
#### 模組掛載練習
檢查 Linux 核心版本
$ uname -r
6.5.0-28-generic
確認 linux-headers 套件已正確安裝於開發環境
$ dpkg -L linux-headers-`uname -r` | grep "/lib/modules/.*/build"
/lib/modules/6.5.0-28-generic/build
掛載核心模組
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
$ sudo insmod hello.ko
$ sudo rmmod hello
$ sudo dmesg
....
[174167.005752] Hello, world
[174246.857853] Goodbye, cruel world
考慮到以下程式碼
```c
static int hello_init(void) {
printk(KERN_INFO "Hello, world\n");
return 0;
}
static void hello_exit(void)
{
printk(KERN_INFO "Goodbye, cruel world\n");
}
module_init(hello_init);
module_exit(hello_exit);
```
在 `module_init` 巨集中會展開 `__initcall(x)` 巨集
```c
#define __initcall(fn) device_initcall(fn)
```
`device_initcall(fn)` 對應到 `__define_initcall(fn, 6)`
> `device_initcall(fn)` 定義在 [linux/init.h](https://github.com/torvalds/linux/blob/5eb4573ea63d0c83bf58fb7c243fc2c2b6966c02/include/linux/init.h#L311)
```c
#define device_initcall(fn) __define_initcall(fn, 6)
```
持續展開後會執行到以下巨集
```c
#define ____define_initcall(fn, __unused, __name, __sec) \
static initcall_t __name __used \
__attribute__((__section__(__sec))) = fn;
```
意思是 symbol : `__name` (根據定義的函數名稱決定)會註冊到 `__sec` 這個 ELF section (`__define_initcall(fn, 6)` 傳入參數為 6，對應到 : `.initcall6.init`)
並將此 symbol 指到 `fn` 這個函式
> 上述展開過程有些程式碼還沒看懂，我是以[此篇討論]([參考](https://stackoverflow.com/questions/18605653/module-init-vs-core-initcall-vs-early-initcall))幫助理解
***`initcall_t` 定義為一個 function pointer**
```c
typedef int (*initcall_t)(void);
```
透過 `insmod` 載入此核心模組時，`module_init` 會做兩件事情
1. 傳入的 function pointer，也就是 `hello_init` 是不是合法的
2. `insmod` 指令實作內部會呼叫 `init_module`，`module_init` 會將 `init_module` 與 `hello_init` 關聯起來，因此呼叫 `init_module` 就相當於執行自行定義的函式
```c
#define module_init(initfn)
...
int init_module(void) __copy(initfn) __attribute__((alias(#initfn)))
```
> initfn 為傳入的 funciton，在這邊也就是 `hello_init`。
> 透過 gcc 的 __attribute__((alias( ..))) 來將 `hello_init` 設成 `init_module` 的別名
#### 藉由 strace 追蹤 Linux 核心的掛載
```c=
$ sudo strace insmod hello.ko
execve("/usr/sbin/insmod", ["insmod", "hello.ko"], 0x7fff7b3dba78 /* 26 vars */) = 0
brk(NULL) = 0x5a65cffc8000
arch_prctl(0x3001 /* ARCH_??? */, 0x7fff7c5e9120) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7b82f94c7000
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=61287, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 61287, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b82f94b8000
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) = 0x7b82f93e9000
mmap(0x7b82f93f3000, 729088, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xa000) = 0x7b82f93f3000
mmap(0x7b82f94a5000, 69632, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xbc000) = 0x7b82f94a5000
mmap(0x7b82f94b6000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0xcc000) = 0x7b82f94b6000
close(3) = 0
...
close(3) = 0
getcwd("/home/xiang/Desktop/hello", 4096) = 26
newfstatat(AT_FDCWD, "/home/xiang/Desktop/hello/hello.ko", {st_mode=S_IFREG|0664, st_size=112368, ...}, 0) = 0
openat(AT_FDCWD, "/home/xiang/Desktop/hello/hello.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=112368, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 112368, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b82f93a0000
finit_module(3, "", 0) = 0
munmap(0x7b82f93a0000, 112368) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
自上述第 28 行可以發現呼叫到 `finit_module`，其實做內部會呼叫 `idempotent_init_module` 當中的 `init_module_from_file` 再呼叫 `load_module` 以此分配記憶體並載入模組。
`load_module` 會呼叫 `simplify_symbols` -> `resolve_symbol_wait` -> `resolve_symbol_wait` 最後呼叫到 `find_symbol`，其中用到 `list_for_each_entry_rcｕ` 並透過 `find_exported_symbol_in_section` 進行symbol 查找。
>`load_module` 定義在 [module/main.c](https://elixir.bootlin.com/linux/v6.5/source/kernel/module/main.c#L2820)
:::info
上述目前僅於流程概念上的理解，實作原理尚待研究。
:::
- [ ] 研讀 [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 排程器互動？
### [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) 筆記
> CMWQ
Linux 提供 workqueue API 用來實現非同步執行 context。每個需要被非同步執行的函式，會抽象為一個 work item，並加入 workqueue 中，接著核心便會挑選合適的 "worker" thread 來處理 work item，完畢後便從 workqueue 中剔除。
在 CMWQ 之前的 workqueue 實作上，worker thread 數量和被建立的 workqueue 數量成正相關，也就是每建立新的 workqueue，系統上的 worker thread 總量便會增加。
實作上有兩種建立 worker thread 方式
* multi threaded (MT) workqueue : 每個 CPU 上會有各自的 worker thread。可分別處理不同的 work item
* single threaded (ST) workqueue: 只有單一的 worker thread 來處理 work item
MT 的缺陷為 CPU 和 workqueue 數量變多時，worker thread 數量也會增多，可能會因 worker thread 行程數量太多，將 32k 的 PID 空間佔滿 (32k PID 為可以分配行程 ID 的數量)，導致其他行程無法運行。又因替每個 CPU 提供一個 context，會消耗大量資源，但 concurrency 效果卻不佳。原因是 workqueue 中的 work 會對應到特定的 worker pool 去處理，那當此 worker pool 所有 worker 被 block 住時，該 workqueue 的其他 work 便無法轉交其他 worker pool，導致剩餘 work 無法及時被處理。
ST 的缺陷則為只有一個 worker thread，因此所有的 work 都需逐一排隊執行，造成並行效果不佳。
**CMWQ 為了解決上述問題而生，並專注於以下目標**
* 維持原始 workqueue API 的相容性
* 捨棄 workqueue 獨立對應一組 worker-pools 的作法。反之是讓 workqueue 共享 per-CPU worker pools，並依照情況提供對應的並行程度，也進而減少資源浪費
* worker pool 和並行程度由系統內部處理，API使用者可以不用考慮細節
**設計方式**
會創造一個 `work_struct` 結構，裡面有 `func` 成員，用來指向要被執行的函式。當系統想非同步執行某個函式，就會透過 `work_struct` 建立對應的 `work item` 並放入 workqueue 中等待執行。worker thread 會負責從佇列中取出 work item 並執行其中的 `func`。
CMWQ 會對每個 CPU 含有兩個 worker pools，一種是處理普通的 work，另一則是處理優先等級高的。此外還有一些額外 worker-pools，它們不會被綁訂到特定 CPU，且 pools 的數量是動態的。
對於 CPU 上的 worker-pool，可以排程器做並行的管理，且每個 worker 被喚醒或是睡眠時，worker-pools 會收到通知，以此追蹤可運行的 woker 數量。CPU 上只要有多個正運行的 worker threads，worker-pools 就不會處理新的 work，當所有 worker threads 都進入睡眠狀態時，worker-pools 就會立刻排程 work 給新的 worker thread，藉此 CPU 就不會在還有 work 要處理時進入 idle。
除了會占用記憶體空間外，idle 的 worker thread 不會消耗其他資源，因此 CWMQ 會保留一個 idle 的 worker thread 一段時間。這樣若有 work，則直接拿閒置的 worker thread 處理，就不需額外創造。
:::info
教材有提到 BH (softirq) context, 目前還沒看懂。
:::
- [ ] 閱讀《[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) 在排序過程中的平均比較次數，並提供對應的數學證明;
- [ ] 解釋 `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+` 是否有速度的優勢？其弱點又是什麼？
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
Sign in with Wallet
Connect another wallet