# 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 時，主迴圈仍然能讀取到最後的棋盤狀態更新。即可修正這些問題。
Sign in with Wallet
Connect another wallet