2024q1 Homework6 (integration)

# 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 達到並行的排序;

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.