# 2025q1 Honework3 (kxo)
contributed by < [`JeepWay`](https://github.com/JeepWay) >
<!-- {%hackmd NrmQUGbRQWemgwPfhzXj6g %} -->
## 理解 Makefile 內容
<s>參考文章：[(Linux kernel模組的開發) 編譯 Linux kernel module](https://ithelp.ithome.com.tw/articles/10158003)</s>
:::danger
參照指定的教材 (你也可因此做出貢獻)，而非這類過時資訊。
$\to$ [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)
:::
Makefile 裡面的兩個子目標
1. `kmod`
* 編譯一個 Linux kernel module `kxo.ko`。
2. `xo-user`
* 與 `kxo.ko` 互動的 user space 程式。
```makefile
TARGET = kxo
kxo-objs = main.o game.o xoroshiro.o mcts.o negamax.o zobrist.o
obj-m := $(TARGET).o
```
* `TARGET`：模組的名稱，這裡是 `kxo`。
* `kxo-objs`：列出了組成 `kxo` 模組的所有目標檔案（.o）。一定要取名為 `kxo-objs`，不能是其他名子，例如 `kxo1-objs`。否則會出現以下：
```shell
make[3]: *** 沒有規則可製作目標「/media/jeepway/Acer/Linux_kernel_design/kxo/kxo1.o」，由「/media/jeepway/Acer/Linux_kernel_design/kxo/」 需求。 停止。
```
* `obj-m`：表示要編譯成核心模組的檔案名稱集合，這邊是 `kxo.o`。
```makefile
$(MAKE) -C $(KDIR) M=$(PWD) modules
```
* `$(KDIR)`：指定 Linux 核心的建構目錄，例如 `/usr/src/linux-headers-6.8.0-56-generic`。
* `-C $(KDIR)`：告訴 make 切換到核心的建構目錄。
* `M=$(PWD)` ：指定要編譯的模組原始碼的目錄 (即專案目錄)
* `modules`：是核心編譯系統的目標，表示編譯模組，觸發模組編譯流程。
```shell=
$ make
make -C /lib/modules/6.8.0-56-generic/build M=/media/jeepway/Acer/Linux_kernel_design/kxo modules
make[1]: Entering directory '/usr/src/linux-headers-6.8.0-56-generic'
warning: the compiler differs from the one used to build the kernel
The kernel was built by: x86_64-linux-gnu-gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
You are using: gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/main.o
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/game.o
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/xoroshiro.o
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/mcts.o
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/negamax.o
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/zobrist.o
LD [M] /media/jeepway/Acer/Linux_kernel_design/kxo/kxo.o
MODPOST /media/jeepway/Acer/Linux_kernel_design/kxo/Module.symvers
CC [M] /media/jeepway/Acer/Linux_kernel_design/kxo/kxo.mod.o
LD [M] /media/jeepway/Acer/Linux_kernel_design/kxo/kxo.ko
BTF [M] /media/jeepway/Acer/Linux_kernel_design/kxo/kxo.ko
Skipping BTF generation for /media/jeepway/Acer/Linux_kernel_design/kxo/kxo.ko due to unavailability of vmlinux
make[1]: Leaving directory '/usr/src/linux-headers-6.8.0-56-generic'
cc -std=gnu99 -Wno-declaration-after-statement -o xo-user xo-user.c
```
* 4-6 行：當前使用的編譯器（gcc-13）與編譯核心時的編譯器（x86_64-linux-gnu-gcc-13）名稱不同，但版本相同。可以暫時忽略這警告。
* 7-13 行：
* `[M]`：kbuild 系統中的標記，表示這些檔案是為核心模組編譯的，而不是核心本身的內建部分。這些 `.o` 檔案最終會成為一個獨立的 `.ko` 檔案，而不是直接連結到核心 image 中。
* 如果沒有 `[M]`，表示該檔案是核心內建部分的編譯（例如編譯 `vmlinux` 時）。
* `CC [M]` 編譯指定的 `.c` 原始碼檔案成 `.o` 目標檔案。
* `LD [M]` 將 `main.o`、`game.o`、`xoroshiro.o` 等目標檔案（由 `kxo-objs` 定義的檔案）連結成 `kxo.o`，並最終生成 `kxo.ko`，成為一個可以在 Linux 核心啟動後支援動態插入 `sudo insmod kxo.ko` 和卸載的核心模組。模組的設計允許機器在不重新編譯或重啟核心的情況下新增功能，這是 Linux 模組化架構的強大之處。
* 參考文章：[What are the codes such as CC, LD and CC[M] output when compiling the Linux kernel?](https://stackoverflow.com/questions/11697800/what-are-the-codes-such-as-cc-ld-and-ccm-output-when-compiling-the-linux-kern)
* 14 行：`MODPOST` 處理模組的符號表，生成 `Module.symvers`，記錄模組中導出的符號（例如函式），以便其他模組使用。
* 15 行：編譯模組的元數據檔案`kxo.mod.c`，包含模組資訊（如名稱、版本、參數等），生成 `kxo.mod.o`。
* 16 行：將 `kxo.o` 和 `kxo.mod.o` 連結成最終的核心模組檔案 `kxo.ko`，即要載入核心的檔案。
* 17 行：`BTF`（BPF Type Format）是核心用於調試和追蹤的格式。由於缺少 `vmlinux`（未壓縮的核心映像檔案），`BTF` 生成被跳過。這不影響模組功能，只是缺少額外的調試資訊。
* 20 行：編譯 user space 程式 `xo-user`。
## 插入模組問題
```bash
$ sudo insmod kxo.ko
[sudo] password for jeepway:
insmod: ERROR: could not insert module kxo.ko: Key was rejected by service
```
* 核心可以配置為強制要求所有模組都必須經過數位簽署（digitally signed），以防止載入未經授權或未驗證的模組。這是一種安全措施，特別在啟用了**安全啟動 (Secure Boot)** 的系統上常見。
透過 `mokutil` 命令檢查是否開啟 Secure Boot，由以下得知確實有開啟 Secure Boot。
```shell
$ mokutil --sb-state
SecureBoot enabled
```
### 解決方法
#### 方法一：進入 BIOS/UEFI 設定，關閉 Secure Boot
#### 方法二：為模組 kxo 建立簽名
* 參考文章：[How to sign a kernel module Ubuntu 18.04](https://superuser.com/questions/1438279/how-to-sign-a-kernel-module-ubuntu-18-04)
* 參考文章：[Linux系统解决“Key was rejected by service”](https://blog.csdn.net/WCH_TechGroup/article/details/134943308)
根據作業的說明，為了方便還是採用方法一。
## 修復 Ctrl-Q 無法離開對弈
> commit [c86c1ce](https://github.com/JeepWay/kxo/commit/c86c1cecde2ff74e00d3507fb4125526053731ed)
再 fork 完 kxo 並編譯後，執行 `sudo ./xo-user` 後發現 Ctrl-Q 無法確實離開對弈，只能按下 Ctrl-C 強制 `xo-user` 結束。
使用 `cat -v` 檢查輸入 Ctrl-Q 後是否有正確產生控制字元，可以發現有
```shell
$ cat -v
^P^C
```
輸入 Ctrl-P，Ctrl-Q，Ctrl-C 後，只有出現 `^P^C`，可能是終端機配置中，Ctrl-Q 被綁定為特殊控制字符，導致 Ctrl-Q 不被程式接收。
使用 `$ stty -a` 檢查終端機設置，看 Ctrl-Q 是被用於什麼地方。
```shell
$ stty -a
speed 38400 baud; rows 24; columns 123; line = 0;
intr = ^C; quit = ^\; erase = ^?; kill = ^U; eof = ^D; eol = <undef>; eol2 = <undef>; swtch = <undef>; start = ^Q;
stop = ^S; susp = ^Z; rprnt = ^R; werase = ^W; lnext = ^V; discard = ^O; min = 1; time = 0;
-parenb -parodd -cmspar cs8 -hupcl -cstopb cread -clocal -crtscts
-ignbrk -brkint -ignpar -parmrk -inpck -istrip -inlcr -igncr icrnl ixon -ixoff -iuclc -ixany -imaxbel iutf8
opost -olcuc -ocrnl onlcr -onocr -onlret -ofill -ofdel nl0 cr0 tab0 bs0 vt0 ff0
isig icanon iexten echo echoe echok -echonl -noflsh -xcase -tostop -echoprt echoctl echoke -flusho -extproc
```
`ixon` 表示啟用了 START/STOP 輸出控制。 一旦已啟用 START/STOP 輸出控制，可以按 Ctrl-S 來暫停輸出至終端機，並按 Ctrl-Q 來恢復輸出至終端機。所以終端機會攔截並處理 Ctrl-Q 和 Ctrl-S 作為流控制字符，而不是將它們傳遞給應用程式。
* [stty 指令 IBM 文件說明](https://www.ibm.com/docs/zh-tw/aix/7.3?topic=s-stty-command)
在 `bits/termios-ciflags.h` 中有寫到 `ixon` 的定義
```cpp
#define IXON 0002000 /* Enable start/stop output control. */
```
在執行 `xo-user` 的終端機中按下：
* Ctrl-S (stop)：暫停終端機畫面的刷新。
* Ctrl-Q (start)：恢復終端機畫面的刷新。如果本來就沒暫停，那對終端機畫面沒有任何影響
* Ctrl-Z (susp)：退出 `xo-user`，但 `xo-user` 還是在背景執行。
使用 `$ stty -ixon` 可以禁用軟體流控制，再用 `$ stty ixon` 恢復軟體流控制。但為了不手動改變終端機預設條件，我們需要去改變 `xo-user.c` 中的 `raw_mode_enable` 函式，來停用 `ixon`。
```diff
static void raw_mode_enable(void)
{
tcgetattr(STDIN_FILENO, &orig_termios);
atexit(raw_mode_disable);
struct termios raw = orig_termios;
raw.c_lflag &= ~(ECHO | ICANON);
+ raw.c_iflag &= ~(IXON); /* Disable start/stop output control. */
tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
}
```
重新編譯 `xo-user.c` 在執行後，Ctrl-S 也不會停止終端機畫面的刷新，使用 Ctrl-Q 後會中止 `kxo` 內核模組。
```shell
| | |
-------
| | |
-------
| | |O
-------
| | |
-------
�Stopping the kernel space tic-tac-toe game...
```
執行以下命令發現 `kxo` 內核模組還存活著，`kxo_state` 的 end 也為 1。
```shell
$ cat /sys/module/kxo/initstate
live
$ cat /sys/class/kxo/kxo/kxo_state
1 1 1
```
但是透過 `$ sudo dmesg --follow` 會發現沒有執行任何有關 kxo 的函式，即便有執行 `$ sudo cat /dev/kxo`，因為核心模組已經中止了。如果要讓 kxo 核心模組重新執行，需要先卸載模組後，再重新載入。
```shell
$ sudo rmmod kxo
$ sudo insmod kxo.ko
```
## 讀取 `kxo_state` 檔案沒有出現換行
> commit [2829628](https://github.com/JeepWay/kxo/commit/2829628cf3cd4b1f3d18070dd45494c34e36362c)
當使用 `cat` 命令獲取 `/sys/class/kxo/kxo/kxo_state` 的內容時會有以下結果：
```shell
user@Ubuntu:~$ cat /sys/class/kxo/kxo/kxo_state
1 1 0user@Ubuntu:~$
```
可以發現並沒有正確換行，但是在 `kxo_state_show` 函式中，`snprintf` 使用了格式字串 `"%c %c %c\n"`，確實有用到換行符號 `\n`，然而，實際輸出卻沒有換行。
原因是 `snprintf` 中的第二個參數 `size` (原始設為 6)，限制了寫入緩衝區的字元數，而這個限制包含了結束符號 `\0`，導致換行符號 `\n` 被截斷，所以實際輸出電成 `"%c %c %c\0"`，而不是預期的 `"%c %c %c\n\0"`。而修正發法只需要把 6 改成 7，就可以正確輸出換行符號了。
```diff
...
- int ret = snprintf(buf, 6, "%c %c %c\n", attr_obj.display, attr_obj.resume,
+ int ret = snprintf(buf, 7, "%c %c %c\n", attr_obj.display, attr_obj.resume,
attr_obj.end);
...
```
修正後就可以看到終端機有出現換行了：
```shell
user@Ubuntu:~$ cat /sys/class/kxo/kxo/kxo_state
1 1 0
user@Ubuntu:~$
```
## 減少呼叫 drawboard 的次數
> commit [33f52d9](https://github.com/JeepWay/kxo/commit/33f52d971e926b021bc2862fb8c5599f0facdc97)
在 `game_tasklet_func` 函式裡，每次都會把 `drawboard_work` 放入 workqueue 當中執行，不管下棋狀態是否為 `finish`。而這樣做會導致在終端機畫面中一直看到相同的棋盤狀態，因為只有當 AI 演算法完成計算，決定出當前動作後，棋盤狀態才有出現變化。
然後 AI 演算法的計算時間相當的久，導致 `drawboard_work_func` 一直在產生相同的棋盤狀態，這不僅浪費 cpu 資源，也導致很難在終端機中觀察出棋盤狀態的變化，因為前後的棋盤狀態可能是相同的。
為了減少 drawboard 的次數，需要移動把 drawboard 的
work item 放到 workqueue 的這項動作，移動到 AI 演算法完成後才執行，這樣就可以確保每次 `drawboard_work_func` 畫出的棋盤狀態都是有差異的，並且減少 drawboard 的次數。
```diff
static void ai_one_work_func(struct work_struct *w)
{
...
put_cpu();
+ queue_work(kxo_workqueue, &drawboard_work);
}
static void ai_two_work_func(struct work_struct *w)
{
...
put_cpu();
+ queue_work(kxo_workqueue, &drawboard_work);
}
static void game_tasklet_func(unsigned long __data)
{
...
- queue_work(kxo_workqueue, &drawboard_work);
tv_end = ktime_get();
...
}
```
使用 `sudo dmesg --follow` 觀察 kernel，會看到以下結果。只有當 `ai_work_func completed`，才會出現 `drawboard_work_func` 這項 work item (每 7 行為一組)。
如果 AI 還沒完成，就不會出現 `drawboard_work_func` (每 5 行為一組)。這也驗證了這項修改確實可以減少呼叫 drawboard 的次數。
```shell
[23621.360625] kxo: [CPU#8] enter timer_handler
[23621.360630] kxo: [CPU#8] doing AI game
[23621.360631] kxo: [CPU#8] scheduling tasklet
[23621.360632] kxo: [CPU#8] timer_handler in_irq: 2 usec
[23621.360637] kxo: [CPU#8] game_tasklet_func in_softirq: 0 usec
[23621.464614] kxo: [CPU#8] enter timer_handler
[23621.464623] kxo: [CPU#8] doing AI game
[23621.464624] kxo: [CPU#8] scheduling tasklet
[23621.464625] kxo: [CPU#8] timer_handler in_irq: 2 usec
[23621.464630] kxo: [CPU#8] game_tasklet_func in_softirq: 0 usec
[23621.568613] kxo: [CPU#8] enter timer_handler
[23621.568618] kxo: [CPU#8] doing AI game
[23621.568619] kxo: [CPU#8] scheduling tasklet
[23621.568620] kxo: [CPU#8] timer_handler in_irq: 2 usec
[23621.568627] kxo: [CPU#8] game_tasklet_func in_softirq: 0 usec
[23621.598688] kxo: [CPU#9] ai_one_work_func completed in 943267 usec
[23621.598764] kxo: [CPU#0] drawboard_work_func
```
## kxo 流程圖
```graphviz
digraph kxo_flow {
node [shape = box]
rankdir = TD
timer_handler [label="timer_handler"]
ai_game [label="ai_game"]
game_tasklet_func [label="game_tasklet_func"]
drawboard_work_func [label="drawboard_work_func"]
ai_one_work_func [label="ai_one_work_func"]
ai_two_work_func [label="ai_two_work_func"]
draw_buffer [label="draw_buffer", shape=ellipse]
produce_board [label="produce_board"]
rx_fifo [label="rx_fifo", shape=ellipse]
timer_handler -> ai_game
ai_game -> game_tasklet_func [label="tasklet_schedule"]
game_tasklet_func -> drawboard_work_func [label="queue_work "]
game_tasklet_func -> ai_one_work_func [label="turn=O\nqueue_work"]
game_tasklet_func -> ai_two_work_func [label="turn=X\nqueue_work"]
drawboard_work_func -> draw_buffer [label=" draw_board"]
draw_buffer -> produce_board
produce_board -> rx_fifo [label=" kfifo_in"]
{rank=same drawboard_work_func ai_one_work_func ai_two_work_func}
}
```
## 移動 MCTS 到 userspace
以肉眼觀察 `dmesg --follow` 的輸出，有明顯發現 ai_one (MCTS) 的運算時間明顯長於 ai_two (Negamax)。
Sign in with Wallet
Connect another wallet