Linux 核心專題: 重作 kxo

# Linux 核心專題: 重作 kxo > 執行人: mincch > [解說影片](https://youtu.be/JZnuofbJINE?si=SmNTC1LKuuLJw6qU) ### Reviewed by `Mike1117` - 很多程式碼區塊未註記程式語言，導致可讀性下降。 - >接這去記錄每一步移動 record_move 當有新的棋盤狀態傳輸過來時，我們需要檢查舊狀態和新狀態的差異，可以判斷出在哪個格子進行了移動，並將其記錄下來。 - 「接著」 - 選擇在 user space 比對新舊棋盤推斷下棋的位置，而不是由 kernel space 傳送的理由是什麼？ ### Reviewed by `alexc-313` > 但是修改後的 code 雖然減少了每次傳輸的成本，但卻增加了大量的呼叫次數這可能是因為修改後的程式碼多字呼叫 `smp_wmb()` ，是否能夠在保存並行性的前提下減少呼叫次數? 處理完一行再呼叫 `smp_wmb()` 是否可行? 另外，建議使用 c 註記程式語言，而非 clike 。 ## 任務描述以[第三份作業](https://hackmd.io/@sysprog/linux2025-kxo)為基礎、搭配課堂討論和觀摩學員的成果，重新投入 kxo 開發。過程中可參照其他學員的成果 (但要實驗和指出其缺失)，務必清楚標示。 ## TODO: 重作 kxo ## TODO: 觀摩其他學員的成果 > 紀錄你的啟發、你進行的驗證，以及後續改進 ## 開發環境 ```shell $ uname -rs Linux 6.11.0-28-generic $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 $ 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): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz CPU family: 6 Model: 69 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 80% CPU max MHz: 2600.0000 CPU min MHz: 800.0000 BogoMIPS: 4589.34 Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 64 KiB (2 instances) L1i: 64 KiB (2 instances) L2: 512 KiB (2 instances) L3: 3 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-3 ``` ## 處理 ctrl+Q 無法使用自 GitHub kxo 進行 fork 專案後，閱讀 README 後發現 Ctrl + Q: Terminate all tic-tac-toe games running in kernel space，但是當我實際在操作時卻沒有反應，接著我去檢查了 `xo-user.c` 看到了以下這段 code ```clike 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); tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw); } ``` `c_lflag` : 主要是在影響字元的處理方式，處理使用者互動體驗，例如:打字的時候，螢幕上是否立刻顯示出來。 `ECHO` ：控制輸入字符是否顯示出來。當設為 true 時，輸入的字元會立即顯示。當清除時 `raw.c_lflag &= ~ECHO` ，輸入的字元不會顯示，這常用於密碼輸入或遊戲等需要隱藏輸入的場景。 `ICANON`：當設為 true 時，不會直接送出，直到接收到換行符 `\n` 或 EOF ，再將整個傳遞給程式。所以這代表在按下 Enter 鍵之前，可以編輯或修改輸入的內容。 `c_iflag` : 處理鍵盤輸入的原始資料，例如:終端機是不是要處理 Ctrl+S 和 Ctrl+Q 這種特殊輸入 `IXON` ：用來攔截 Ctrl+S / Ctrl+Q `ICANON`：將 CR(0x0D) 轉成 LF(0x0A)，若設為 false 可保留 `\r` ```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 | ICRNL); tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw); } ``` 這邊將 `IXON` 與 `ICRNL` 設為 false，可以使我們鍵盤的輸入 Ctrl+Q 不會再被攔截導致沒有反應，這樣只要按下 Ctrl+Q 就可以正常終止遊戲。 ## 使畫面呈現的部分在使用者層級在將畫面呈現在使用者層級實作前我先研讀了 kxo 的原始設計中，遊戲盤面的繪製是透過模組中的 draw_board 完成的。這個函式使用draw_buffer，把 ASCII 畫面字元放到 kfifo；使用者程式只負責把字串整段讀出來再 printf()。這做法雖然直觀，但每次畫面更新都要在核心與 user space 之間處理會有額外更多的開銷。在最後印出 `DRAWBUFFER_SIZE`，可以發現為 `DRAWBUFFER_SIZE = 66` ，而修改之後只需要傳送 board 自己的大小 size 運用 bpftrace 測量: ``` write_bytes : 1058 B read_bytes : 5984 B write_calls : 15 read_calls : 18 ioctl_calls : 4 @ioctl_calls: 4 @rd_bytes: 5984 @rd_calls: 18 @wr_bytes: 1058 @wr_calls: 15 ``` 1058B / 15 = 70 byte per call ``` write_bytes : 3506722 B read_bytes : 714248 B write_calls : 350764 read_calls : 175286 ioctl_calls : 4 @ioctl_calls: 4 @rd_bytes: 714248 @rd_calls: 175286 @wr_bytes: 3506722 @wr_calls: 350764 ``` 3506722B / 350764 = 9.9 byte per call 用同樣30秒的時間讓他 timeout ，但是修改後的 code 雖然減少了每次傳輸的成本，但卻增加了大量的呼叫次數 ```c static int draw_board(char *table) { int i = 0, k = 0; draw_buffer[i++] = '\n'; smp_wmb(); draw_buffer[i++] = '\n'; smp_wmb(); while (i < DRAWBUFFER_SIZE) { for (int j = 0; j < (BOARD_SIZE << 1) - 1 && k < N_GRIDS; j++) { draw_buffer[i++] = j & 1 ? '|' : table[k++]; smp_wmb(); } draw_buffer[i++] = '\n'; smp_wmb(); for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) { draw_buffer[i++] = '-'; smp_wmb(); } draw_buffer[i++] = '\n'; smp_wmb(); } return 0; } ``` 這段函式負責根據遊戲介面 (char *table) 的狀態，把它變成一個 draw_buffer。將井字遊戲盤面的文字表示形式 ( 'X', 'O', ' ', '|', '-') 放到一個記憶體緩衝區中。 `draw_buffer` : 用於暫存要輸出的盤面字串 ( static char draw_buffer[DRAWBUFFER_SIZE] )。 `table` : 傳入的參數，代表了當前遊戲的介面狀態，通常是一個包含 'X', 'O', ' ' 等字元的陣列。根據 table 的內容，將井字遊戲盤面的視覺化表示（包含格子內容、分隔符號 | 和 -、以及換行符號 \n）寫入 draw_buffer 中。 `smp_wmb()` : 在多核心處理器系統中，處理器可能會為了效能而重新排序記憶體寫入操作。`smp_wmb()` 確保在此之前的所有寫入操作（即對 draw_buffer 的寫入）都已完成並對其他處理器可見，這對於並行操作和資料一致性非常重要。 ```c static void produce_board(void) { unsigned int len = kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer)); if (unlikely(len < sizeof(draw_buffer))) pr_warn_ratelimited("%s: %zu bytes dropped\n", __func__, sizeof(draw_buffer) - len); pr_debug("kxo: %s: in %u/%u bytes\n", __func__, len, kfifo_len(&rx_fifo)); } ``` 這段函式負責將 draw_board 準備好的 draw_buffer 中的資料，透過 KFIFO (Kernel FIFO) 機制寫入 rx_fifo。 `kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer))` : 將資料寫入 KFIFO 。 `draw_buffer` : 包含要寫入資料的源緩衝區 (也就是 draw_board 準備好的盤面字串)。 `if (unlikely(len < sizeof(draw_buffer)))` 這是一個錯誤檢查。如果實際寫入的資料量少於預期，表示 KFIFO 可能滿了，會導致部分資料被丟棄。將 produce_board 以及 draw_board 移除，並在 `xo-user.c` 加入 ```c static void draw_board(uint32_t bits) { printf("\x1b[H"); for (int r = 0; r < 4; ++r) { printf("|"); for (int c = 0; c < 4; ++c) { int idx = r * 4 + c; uint32_t v = (bits >> (idx * 2)) & 3; char ch = (v == 1) ? 'X' : (v == 2) ? 'O' : ' '; printf(" %c |", ch); } printf("\n-----------------\n"); } fflush(stdout); } ``` 這段函式負責從 KFIFO 讀取到的壓縮盤面資料 (bits) ，然後將他輸出在終端機上繪製出遊戲盤面。用 00 , 01 , 10 分別來代表 ' ','O', 'X' `uint32_t v = (bits >> (idx * 2)) & 3` : 將 bits 右移 idx * 2 位，這樣就把當前格子 idx 的 2 位元狀態移到了 bits 的最低兩位。接著再 & 3：可以找出最低兩位元的值。這就是當前格子的狀態 (0, 1, 或 2)。 ## 對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新為了在使用者層獲取和顯示時間，我使用了時間處理函式庫，並調整 select 系統呼叫，使其能夠在沒有新的遊戲盤面資料或使用者輸入時，也能周期性地執行，以便更新時間顯示。引入 <time.h> 標頭檔在 xo-user.c 中，新增對 <time.h> 的引用。這個函式庫提供了獲取和格式化時間的相關函式，例如 time() 和 localtime()。遇到的困難 1. 時間與棋盤共享 stdout 造成的衝突：終端機的所有輸出都導向同一個標準輸出 (stdout)。當時間列和遊戲棋盤都需要向終端機寫入資料時，同時多個 printf() 操作都可能改變終端機滑鼠的當前位置。會造成棋盤被時間覆蓋掉，並且畫面會有閃爍的感覺 2. 游標位置干擾問題：在前面的處理中，我的 draw_board() 函式內部可能直接使用了 `\x1b[H` （將游標移動到左上角）來清除畫面或是重新顯示畫面。這導致了一些問題。時鐘已經寫好的字會立即被棋盤重畫的內容覆蓋掉，導致時間無法穩定顯示。為了解決這些問題我將時間顯示與棋盤繪製分離，我創建了一個專門顯示時間的函式 `draw_time()` 來去單獨處理顯示時間的功能 ```c static void draw_time(void) { time_t now = time(NULL); const struct tm *tm = localtime(&now); printf("\x1b[H"); printf("Time: %02d:%02d:%02d\x1b[K", tm->tm_hour, tm->tm_min, tm->tm_sec); fflush(stdout); } ``` `time_t now = time(NULL);` 和 `const struct tm *tm = localtime(&now);`：利用 time() 獲取時間戳，再用 localtime() 轉換為 tm 結構，來提取時、分、秒。 `fflush(stdout);` 獨立的 fflush 調用確保了 `draw_time()` 輸出的時間能夠立即顯示在螢幕上，不會因為 stdout 的緩衝機制而延遲，這對於時間的即時性較重要。為了解決游標會在畫面左上角一直閃爍的問題，我直接在 `main` 的開頭和結尾加上 `printf("\x1b[?25l");` 和 `printf("\x1b[?25h");` 分別代表了隱藏游標和顯示游標，在開始進入棋局前將游標隱藏起來，結束時再把他顯示，這樣就可以解決一直在畫面閃爍的問題。 ## 當離開對弈時，顯示多場對弈的過程在 `xo-user.c` 中，新增 moves 陣列用於儲存每次移動的文字表示，n_moves 記錄移動次數，game_lines 儲存多個遊戲的歷史記錄，n_games 記錄遊戲局數。接著去記錄每一步移動 `record_move` 當有新的棋盤狀態傳輸過來時，我們需要檢查舊狀態和新狀態的差異，可以判斷出在哪個格子進行了移動，並將其記錄下來。比較 oldb 和 newb。找出哪個格子從 0 (空) 變成了 1 (X) 或 2 (O)。 ```c static void record_move(uint32_t oldb, uint32_t newb) { if (n_moves >= 128) return; for (int i = 0; i < 16; ++i) { uint32_t o = (oldb >> (i * 2)) & 3; uint32_t n = (newb >> (i * 2)) & 3; if (o == 0 && n != 0) { moves[n_moves][0] = 'A' + (i % 4); moves[n_moves][1] = '1' + (i / 4); moves[n_moves][2] = '\0'; ++n_moves; break; } } } ``` 接下來是當遊戲結束（分出勝負或平局）時，需要將當前遊戲的移動過程儲存到歷史記錄中，並為下一局遊戲重置相關計數器。實作 `game_over_flush` ：這個函式在遊戲結束時被呼叫，負責將當前局的移動歷史 (moves) 拼接成一個字串，儲存到 game_lines 中，並重置 n_moves。 ```c static void game_over_flush(void)Add commentMore actions { if (!n_moves) return; int len = 0; len += snprintf(game_lines[n_games] + len, sizeof(game_lines[0]) - len, "Moves:"); for (int i = 0; i < n_moves; ++i) len += snprintf(game_lines[n_games] + len, sizeof(game_lines[0]) - len, " %s%s", moves[i], (i + 1 == n_moves) ? "" : " -> "); n_games++; n_moves = 0; } ``` 最後將 game_history 在 main 要結束前輸出，即可得到各對局的對弈過程。在實作過程中遇到了問題: 開始棋局後沒有經過暫停直接 Ctrl+Q :就會缺少 Moves 輸出但如果有 Ctrl+P → 恢復 → Ctrl+Q : Moves 就可以正常列印在原本設計中，Ctrl+Q 在 `listen_keyboard_handler` 中會直接設定 `end_attr = true;` 並呼叫 `game_over_flush()`。當 Ctrl+Q 被按下時， device_fd 還沒有讀取到最後的棋盤更新（或者 main 迴圈中的 read_attr 處理還沒觸發），導致 record_move 沒有記錄最後一步， game_over_flush 在 moves 陣列被正確輸入前就被呼叫。導致來不及讀取最後被遺漏。 listen_keyboard_handler() 內對 Ctrl‑Q 的處理： ```c read_attr = false; end_attr = true; game_over_flush(); ``` 就會導致:提早關閉讀取 (read_attr = false) 主迴圈的 select() 之後就不再監聽 /dev/kxo，這一步永遠不會進到 record_move() → moves[]。 ```diff static void listen_keyboard_handler(void) case 17: read(attr_fd, buf, 6); buf[4] = '1'; - read_attr = false; end_attr = true; - game_over_flush(); write(attr_fd, buf, 6); break; ``` 將 `game_over_flush()` 移動到 `main` 函式結束前再呼叫，並且保持 `read_attr = true`：確保在 Ctrl+Q 時，主迴圈仍然能讀取到最後的棋盤狀態更新。即可修正這些問題。

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.