# Linux 核心專題: 改進 ttt 作為核心模組
> 執行人: brian049
> [專題解說錄影](https://youtu.be/3Fkwso92eX4)
## review by `marvin0102`
強化對奕的互動，sysfs 與 ioctl 行為的差異為何，除了使用到 major number ，是否會有其他影響？
## Reviewed by `otteryc`
在 commit [18090cc](https://github.com/brian049/simrupt/commit/18090ccffc77a5a4bb7dba8345b686f2c1b1e297) 的 simrupt.c 第 173 行中，常數 70 是什麼意思？另外，`simrupt_work_func_first` 以及 `simrupt_work_func_second` 函式的內容相同，能不能用巨集撰寫，提高可讀性？
```diff
mutex_lock(&producer_lock);
-produce_data(val);
+produce_data(70);
mutex_unlock(&producer_lock);
```
### Reviewed by `Terry7Wei7`
繼續更新未完成的TODO事項
## 任務簡介
重作第六次作業的 simrupt，整合 ttt 程式碼和彙整其他學員的成果，建構 Linux 核心模組
## TODO: 回答第六次作業的自我檢查清單
> 回答第六次作業的自我檢查清單的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
- [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
...
```
可以在 [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 達到並行的排序;
## TODO: 整合第三次作業提及的人工智慧程式碼到 simrupt
> 整合第三次作業提及的人工智慧程式碼，主體應在 Linux 核心內運作，讓二個不同的井字遊戲人工智慧演算法執行在「不同的 CPU」(善用 CMWQ) 並模擬二者的對弈，並允許使用者層級的程式藉由開啟 /dev/simrupt (可適度更名) 來設定二個人工智慧程式的對弈並存取彼此的棋步。
> 務必在 Linux 核心模組中使用定點數。
其一演算法必是 MCTS，另一者可參照第三次作業或 jserv/ttt 專案近期整合的 ELO rating system。
$\to$ 適度彙整其他學員的成果並予以驗證。
### 設計兩位玩家
> [commit 18090cc](https://github.com/brian049/simrupt/commit/18090ccffc77a5a4bb7dba8345b686f2c1b1e297)
透過更改 simrupt.c，新增一個 work function 並進行 declare。
```shell
$ sudo insmod simrupt.ko
$ sudo cat /dev/simrupt
FSFS...
```
### 畫棋盤
> [commit 5332bdc](https://github.com/brian049/simrupt/commit/5332bdcbb0dcbbd85a66790fb0ef7479a4c4e911)
對於 `void draw_board()` 函式的更改，[vax-r](https://hackmd.io/@vax-r/linux2024-homework6#%E7%95%AB%E6%A3%8B%E7%9B%A4), [marvin0102](https://hackmd.io/@marvin0102/2024q1-Homework6#%E7%B9%AA%E8%A3%BD%E6%A3%8B%E7%9B%A4) 發現如果透過原始 simrupt 程式碼運作方式會需要一次次地將資料傳遞至 kfifo buffer。其中， vax-r 在 `draw_board()` 當中使用 `WRITE_ONCE` 巨集寫入 `pos` 變數來避免 race condition，解決<s>多核心</s> CPU 之間資料一致性的問題。
:::danger
注意用語：
* (OS) kernel 是「核心」
* (processor) core 是「核」
工程人員說話務必精準且有效。
:::
```c
static int draw_board(int pos)
{
WRITE_ONCE(pos, pos % N_GRIDS);
WRITE_ONCE(pos, 2 + (pos >> 2) * 16 + ((pos & 3) << 1));
...
WRITE_ONCE(draw_buffer[pos], 'O');
return 0;
}
```
:::danger
上述實作的成本仍過高，棋盤的狀態可事先編碼為特定的數值 (善用數學分析)，然後 Linux 核心模組只要傳遞一個數值給應用程式，後者就能在解讀後，用合適的手段 (包含藉由 SDL2 來繪製棋盤) 展現，這樣效率高又有彈性。
:::
### 加入 MCTS
#### 在 Linux 核心模組中使用定點數
在 mcts.h 當中有計算到 sqrt(2)，在這之中定點數的運算改寫方式參考 [sqrt 的計算](https://hackmd.io/@sysprog/B13GqdgQ0#sqrt-%E7%9A%84%E8%A8%88%E7%AE%97)。
## TODO: 強化對奕的互動
> 查閱 CMWQ 的文件，指定前述不同的人工智慧演算法固定在不同的 CPU (如 CPU #0 和 CPU #1)，應該要能從使用者層級指定對弈的起始、暫停、恢復，和瀏覽狀態，Linux 核心模組和使用者層級的程式藉由 /dev/simrupt (可適度更名) 裝置檔案互動，注意需要擴充 VFS 註冊的檔案操作。
> 模擬對弈過程，前述二個人工智慧演算法程式碼在執行時間，應適度停頓 (數百個 millisecond)。
> 使用者層級的程式應能清楚繪製出 Linux 核心模組的對弈過程，在終端機展現 (你也可改用 SDL 一類的圖形函式庫繪製)
### 使用者層級指定對弈的起始、暫停、恢復
HenryChaing 以及 vax-r 有針對此項目實作，前者使用 ioctl write 的機制並且加上鍵盤處理機制，並讓終端機的 stdin 轉為 raw mode，再搭配上一個 `process_lock`。此機制會判斷鍵盤輸入是否是 0x10 也就是`ctrl + p`，來判斷是否需要暫停。所以當核心模組接收到暫停訊號時，work 會因為獲取不到 `process_lock` 而無法繼續執行，從而得到暫停機制。
```c
work A { work B {
while(!checkwin()){ while(!checkwin()){
mutex_lock(lock_A); mutex_lock(lock_B);
mutex_lock(pro_lock); mutex_lock(pro_lock);
/*negamax decision*/ /*MCTS decision*/
mutex_unlock(pro_lock); mutex_unlock(pro_lock);
mutex_unlock(lock_B); mutex_unlock(lock_A);
} }
} }
simrupt_write event : mutex_lock(pro_lock);
```
後者針對暫停機制採用 sysfs 機制，<s>筆者</s> 有提起不使用 ioctl 機制是因為需要事先得知裝置的 major number，但是筆者想讓系統動態配置裝置的 major number。想透過寫入代表核心模組當中變數的檔案和核心模組進行溝通，並透過 `select()` 來同時監聽標準輸入裝置 `STDIN_FILENO` 以及裝置檔案是否有輸入。
## TODO: 評估不同的 PRNG
> 考慮到 PRNG 的效率，改用 xorshift128+ 或其他執行成本更低的演算法，並評估對於 MCTS 的影響。
## TODO: 針對 Linux 核心模組提出改進方案
> 量化程式表現、輔以數學分析
Sign in with Wallet
Connect another wallet