2025q1 Honework3 (kxo)

contributed by < JeepWay >

理解 Makefile 內容

參考文章：(Linux kernel模組的開發) 編譯 Linux kernel module

參照指定的教材 (你也可因此做出貢獻)，而非這類過時資訊。

$\to$ Linux 核心模組運作原理

Makefile 裡面的兩個子目標

1. kmod
   • 編譯一個 Linux kernel module kxo.ko。
2. xo-user
   • 與 kxo.ko 互動的 user space 程式。

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。否則會出現以下：
  ​​​​make[3]: *** 沒有規則可製作目標「/media/jeepway/Acer/Linux_kernel_design/kxo/kxo1.o」，由「/media/jeepway/Acer/Linux_kernel_design/kxo/」 需求。 停止。
  

• obj-m：表示要編譯成核心模組的檔案名稱集合，這邊是 kxo.o。

$(MAKE) -C $(KDIR) M=$(PWD) modules

• $(KDIR)：指定 Linux 核心的建構目錄，例如 /usr/src/linux-headers-6.8.0-56-generic。
• -C $(KDIR)：告訴 make 切換到核心的建構目錄。
• M=$(PWD) ：指定要編譯的模組原始碼的目錄 (即專案目錄)
• modules：是核心編譯系統的目標，表示編譯模組，觸發模組編譯流程。

$ 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?
• 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。

插入模組問題

$ 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。

$ mokutil --sb-state
SecureBoot enabled

解決方法

方法一：進入 BIOS/UEFI 設定，關閉 Secure Boot

方法二：為模組 kxo 建立簽名

• 參考文章：How to sign a kernel module Ubuntu 18.04
• 參考文章：Linux系统解决“Key was rejected by service”

根據作業的說明，為了方便還是採用方法一。

修復 Ctrl-Q 無法離開對弈

commit c86c1ce

再 fork 完 kxo 並編譯後，執行 sudo ./xo-user 後發現 Ctrl-Q 無法確實離開對弈，只能按下 Ctrl-C 強制 xo-user 結束。

使用 cat -v 檢查輸入 Ctrl-Q 後是否有正確產生控制字元，可以發現有

$ cat -v
^P^C

輸入 Ctrl-P，Ctrl-Q，Ctrl-C 後，只有出現 ^P^C，可能是終端機配置中，Ctrl-Q 被綁定為特殊控制字符，導致 Ctrl-Q 不被程式接收。

使用 $ stty -a 檢查終端機設置，看 Ctrl-Q 是被用於什麼地方。

$ 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 文件說明

在 bits/termios-ciflags.h 中有寫到 ixon 的定義

#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。

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 內核模組。

 | | | 
-------
 | | | 
-------
 | | |O
-------
 | | | 
-------
�Stopping the kernel space tic-tac-toe game...

執行以下命令發現 kxo 內核模組還存活著，kxo_state 的 end 也為 1。

$ 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 核心模組重新執行，需要先卸載模組後，再重新載入。

$ sudo rmmod kxo
$ sudo insmod kxo.ko

讀取 kxo_state 檔案沒有出現換行

commit 2829628

當使用 cat 命令獲取 /sys/class/kxo/kxo/kxo_state 的內容時會有以下結果：

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，就可以正確輸出換行符號了。

...
-     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);
...

修正後就可以看到終端機有出現換行了：

user@Ubuntu:~$ cat /sys/class/kxo/kxo/kxo_state
1 1 0
user@Ubuntu:~$

減少呼叫 drawboard 的次數

commit 33f52d9

在 game_tasklet_func 函式裡，每次都會把 drawboard_work 放入 workqueue 當中執行，不管下棋狀態是否為 finish。而這樣做會導致在終端機畫面中一直看到相同的棋盤狀態，因為只有當 AI 演算法完成計算，決定出當前動作後，棋盤狀態才有出現變化。

然後 AI 演算法的計算時間相當的久，導致 drawboard_work_func 一直在產生相同的棋盤狀態，這不僅浪費 cpu 資源，也導致很難在終端機中觀察出棋盤狀態的變化，因為前後的棋盤狀態可能是相同的。

為了減少 drawboard 的次數，需要移動把 drawboard 的
work item 放到 workqueue 的這項動作，移動到 AI 演算法完成後才執行，這樣就可以確保每次 drawboard_work_func 畫出的棋盤狀態都是有差異的，並且減少 drawboard 的次數。

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 的次數。

[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 流程圖

移動 MCTS 到 userspace

以肉眼觀察 dmesg --follow 的輸出，有明顯發現 ai_one (MCTS) 的運算時間明顯長於 ai_two (Negamax)。