# 2024q1 Homework6 (Integration)
contributed by < [`brian049`](https://github.com/brian049) >
> [GitHub](https://github.com/brian049/ksort)
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping: 10
CPU MHz: 1368.609
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 自我檢查清單
- [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
```shell
$ uname -a
Linux ubuntu22-System-Product-Name 6.5.0-41-generic #41~22.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jun 3 11:32:55 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
```
- [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)〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。
:::danger
free software 不是「免費軟體」！
務必詳閱 https://hackmd.io/@sysprog/revolution-os-note
「自由」和「免費」的意義截然不同，只是剛好英語可用同一個字表達。
:::
在 linux 6.8.12 版本當中，`MODULE_LICENSE()` 在 [/linux/module.h](https://elixir.bootlin.com/linux/v6.8.12/source/include/linux/module.h#L230) 當中有進行定義，從巨集上述的註解可得知 LICENSE 可以分成<s>免費軟體</s> 自由軟體模組以及非自由，自由軟體模組 LICENSE 為下列幾種: "GPL", "GPL v2", "GPL and additional rights", "Dual BSD/GPL", "Dual MIT/GPL", "Dual MPL/GPL"，非自由的是 "Proprietary"，自由以及非自由的區別在於，如果使用的是 "Proprietary"，則會避免非自由模組使用 `EXPORT_SYMBOL_GPL` 導出的 symbol。
在註解最下方有給出這麼規定的理由是:
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.
[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 文中有 hello.ko 的範例，在 `insmod` 的時候使用 `strace` 追蹤並觀察 `insmod` 。最需要注意的是 `finit_module`:
```shell
$ sudo strace insmod hello.ko
...
getcwd("/home/ubuntu22/Desktop/linux_ws/test", 4096) = 37
newfstatat(AT_FDCWD, "/home/ubuntu22/Desktop/linux_ws/test/hello.ko", {st_mode=S_IFREG|0664, st_size=112416, ...}, 0) = 0
openat(AT_FDCWD, "/home/ubuntu22/Desktop/linux_ws/test/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=112416, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 112416, PROT_READ, MAP_PRIVATE, 3, 0) = 0x765804b3d000
finit_module(3, "", 0) = 0
munmap(0x765804b3d000, 112416) = 0
close(3) = 0
...
```
可以在 [/linux/kernel/module/main.c](https://elixir.bootlin.com/linux/v6.8.12/source/kernel/module/main.c#L3131) 當中找到關於 `finit_module()` 的宣告，其中 `finit_module` 會呼叫 `idempotent_init_module`，`idempotent_init_module` 會透過 `load_module` 來為模組配置記憶體並載入模組。
- [x] 閱讀《[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);
> 參照 [2021 年的筆記](https://hackmd.io/@linD026/simrupt-vwifi)。歡迎貢獻 LKMPG!
> $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
在 simrupt.c 當中主要有兩種使用 mutex lock 的方式: `mutex_lock`, `mutex_lock_interruptible`。前者被使用於 `simrupt_work_func` 函式當中，而後者被使用於 `simrupt_read` 函式當中。
`mutex_lock_interruptible()` 與 `mutex_lock()` 有著些微的差異，針對前者函式的詳細解釋可以在 [kernel/locking/mutex.c](https://elixir.bootlin.com/linux/latest/source/kernel/locking/mutex.c#L982) 中找到。當使用 `mutex_lock_interruptible()` 函式時，如果該行程是處於睡眠狀態，它會回傳 `EINTR`，並且不會獲取 lock。但若成功取得 lock，則與 `mutex_lock()` 一樣回傳 0。
- [ ] 探討 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 排程器互動？
> 搭配閱讀《Demystifying the Linux CPU Scheduler》
Linux 核心當中，會透過 workqueue API 處理非同步 process，其中 work item 代表要執行的函式並透過 workqueue 利用執行緒來處理，在這當中 thread 被稱呼為 worker。
Workqueue 當中分成 multi-thread wq 以及 single-thread wq，MTWQ 的 worker 是每一個 CPU 都有一個 worker，至於 STMQ 則是整個系統只有一個 worker。由於 MTWQ 需要維持與 CPU 數量相同的 workers，此舉會導致系統在啟動時會佔據大量資源。且因為 MT 當中每個 CPU 只能提供一個 execution context，而 ST 當中只有一個 execition context，此狀況導致 work items 的大量競爭。
在 [/core-api/workqueue.rst](https://www.kernel.org/doc/Documentation/core-api/workqueue.rst) 文中指出 CMWQ 的優勢在於:
- 保持與原始工作隊列 wq API 的相容性。
- 每個 CPU 的 worker pool 統一，並且所有 wq 共享，提供相同並行程度，避免資源浪費。
- 自動規範 worker pool 和並行程度，使用戶不需要關注這些細節。
- [ ] 解釋 `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+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
Sign in with Wallet
Connect another wallet