kxo

contributed by <liangchingyun>

注意書寫規範！

參考資料

• N04: kxo(A)
  • 井字遊戲
  • Linux 核心的浮點數運算
  • 強化學習（Reinforcement Learning）
  • 以定點數實作 MCTS
• N04: kxo(B)
  • ksort: 處理並行排序的 Linux 核心模組
  • ksort 核心模組內部
  • 核心模式的時間測量
  • Linux 效能分析
• N04: kxo(C)
  • Linux 核心的並行處理
  • Linux 核心的 kfifo
• N04: kxo(D)
  • 對奕的核心模組
  • kxo 程式碼分析
• N04: kxo(E)
  • Shannon Entropy 與亂度
  • 亂數產生器
  • xoroshiro 亂數產生器
  • 回顧作業一的洗牌過程
  • xoro 核心模組
• N04: kxo(F)
  作業要求：
  • 縮減使用者和核心層級的通訊成本，並允許並行的對奕
  • 引入若干 coroutine
  • 在「電腦 vs. 電腦」的對弈模式，比照前述 load average 的計算方式，規範針對下棋 AI 的 load 機制
  • 運用定點數來統計不同 AI 實作機制對系統負載的使用率，整合到畫面輸出，開發過程中應有對應的數學分析和羅列實作考量因素。
  • 對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新。
  • 原本 kxo 棋盤繪製在核心模式，你應該修改程式碼，使畫面呈現的部分全部在使用者層級，且善用 bitops，降低核心和使用者層級之間的通訊成本，應給予相關量化
  • 自 jserv/ttt 移植 reinforcement learning (RL) 到 kxo 核心模組，使其得以動態切換。
• LKMPG WriteUp

對奕的核心模組

注意用語！

執行指令

編譯

make

載入 kxo module

sudo insmod kxo.ko

執行

sudo ./xo-user

卸載模組

sudo rmmod kxo

查看核心訊息

sudo dmesg

使用者層級互動

使用了 raw_mode_enable() ，則不用另外再執行 $ stty start '^-' stop '^-'，即可直接接收 Ctrl-P，Ctrl-Q 等控制字元

使用 Ctrl + Q 使對弈終止時產生亂碼

Commit 22a2477

�_�Stopping the kernel space tic-tac-toe game...

給 display_buf 中的字串正確結尾（'\0'）便可解決

    read(device_fd, display_buf, DRAWBUFFER_SIZE);
+   display_buf[DRAWBUFFER_SIZE - 1] = '\0';
    printf("%s", display_buf);
}

使對弈終止後自動重置 xo-user

Commit db786e8

原程式在執行完 Ctrl-Q 後，直接跑 sudo ./xo-user 的結果會卡在第一個棋盤，需要重新載入 kxo module 才會正常。

查看核心訊息後發現使用 Ctrl-Q 會使 attr_obj.end 被設成 '1'（ASCII 49）。解決辦法是在 kxo_release() 程式中將 attr_obj.end 重設為 '0'（ASCII 48），就不用一直重新載入 kxo module。

static int kxo_release(struct inode *inode, struct file *filp)
{
    pr_debug("kxo: %s\n", __func__);
    if (atomic_dec_and_test(&open_cnt)) {
        del_timer_sync(&timer);
        flush_workqueue(kxo_workqueue);
        fast_buf_clear();
    }
    pr_info("release, current cnt: %d\n", atomic_read(&open_cnt));
+   attr_obj.end = 48;
    return 0;
}

使畫面呈現在使用者層級

Commit 43dc5ba

原本 draw_board() 函式在核心層級中進行，每次棋盤狀態改變，核心就要透過 copy_to_user() 把整個畫面樣板傳給使用者空間。

參考 a2985ba，將核心層級（main.c）中的draw_board 改寫成只把 16 格棋盤資料存入 draw_buffer，只需傳送字元，無需畫出畫面。

- static char draw_buffer[DRAWBUFFER_SIZE];
+ static char draw_buffer[N_GRIDS];

另外，使用者層級（xo-user.c）中新增 draw_board() 函數，將核心傳來的 16 格資料轉換為棋盤畫面（含換行與橫線）。

效能分析
在 kxo_release 最後加入下面這一行：

pr_info("kxo: DRAWBUFFER_SIZE = %d, N_GRIDS = %d\n", DRAWBUFFER_SIZE, N_GRIDS);

可得到：

[421143.829037] kxo: DRAWBUFFER_SIZE = 66, N_GRIDS = 16

原本讀取 DRAWBUFFER_SIZE（66 個字元）→ 現在只讀 N_GRIDS（16 個字元）。也就是減少了了 66 - 16 = 50 bytes 的傳輸成本。

提供更多數學分析

亂碼問題
先前所提到使用 Ctrl + Q 使對弈終止時產生亂碼，是因為 ASCII 畫面含有空格、|、-、換行等特殊字元，在傳輸中斷或解碼錯誤所造成。因此將畫棋盤的動作改在使用者層級進行也能解決此問題。

顯示當下的時間

Commit 00a2c58

使用 time(NULL) 來取得現在的時間，再用 localtime_r() 轉換成當地時間的結構，同時保證 thread-safe。

thread-safe：當多個執行緒（threads）同時使用同一段程式碼時，不會發生資料衝突或錯誤。

輸出結果如下：

Time: 2025-04-16 20:42:40