Try   HackMD

linux2025-homework3

contributed by <PigeonSir>

注意書寫規範!

KXO

ai 演算法 : mcts.c, negamax.c
kxo module : main.c
user-mode 觀看棋局 : xo-user.c
遊戲規則 & 勝利判定 : game.c

zoberst.c

一開始編譯 kxo 時發生錯誤,其原因為 zobrist.c 中的 u128 未定義,暫時透過新增定義解決

#define u128 __uint128_t

但詢問 chatgpt 發現該操作存在風險,因為並非所有架構都支援 __uint128_t,查看該函式的程式碼

static inline u64 wyhash64_stateless(u64 *seed)
{
    *seed += 0x60bee2bee120fc15;
    u128 tmp;
    tmp = (u128) *seed * 0xa3b195354a39b70d;
    u64 m1 = (tmp >> 64) ^ tmp;
    tmp = (u128) m1 * 0x1b03738712fad5c9;
    u64 m2 = (tmp >> 64) ^ tmp;
    return m2;
}

說好的進度呢?

加入 coroutine

要可以同時觀看多場對局,代表要有很多個 AI1 和 AI2,並要透過鍵盤觸發 signal 來切換對局、暫停和停止,參考 coro 的程式碼發現 setjump/longjump 僅能在 user space 使用,所以我的計畫是在 kernel mode 中運用現有的架構延伸多棋局的功能,並且在 user space 運用 corutine 支援多使用者同時觀看不同的棋局。

kxo 分析

  1. 模組載入階段 kxo_init()
    • 建立 device 並掛載於 /dev 和 /sysfs
    • 呼叫 timer_setup(&timer, timer_handler, 0) → 沒有啟動 timer(尚未進入排程)
    • 初始化 game & AI 狀態
  2. 使用者互動啟動 kxo_open()
    • mod_timer(&timer, jiffies + delay) 啟動第一個 tick 並等待 delay 後觸發 timer_handler()
  3. 定時中斷模擬:timer_handler()
    • 判斷勝負 (check_win)
      • 若無勝負:
        → ai_game()
        → mod_timer()(設定下一次觸發)
      • 若有勝負:
        → draw_board() 處理畫面顯示
        → producer_board 儲存棋盤資料
  4. AI 工作排入 tasklet:ai_game()
    • tasklet_schedule(&game_tasklet) 轉交排程器來決定誰是下一個落子
  5. tasklet 排程器:game_tasklet_func()
    • 讀 turn & finish 狀態
      • 若 turn == 'X' → queue_work(&ai_one_work)
      • 若 turn == 'O' → queue_work(&ai_two_work)
    • queue_work(&draw_work)

加入多場棋局(運算)

流程

先以確保每個棋盤可以獨立運算為目標,不排程畫圖的相關任務,中間有經過一些修改,以下為修改過的流程

  1. 模組載入階段
    初始化多個棋局的結構體 (tasklet, table 等)並存放到陣列當中,每個棋盤有自己的 minor number 並命名為 kxo1 ~ kxoX
  2. 第一個被 open 的棋盤 -> mod_timer
  3. timer_handler 要檢查全部有被開啟的棋盤(全部的棋局使用同一個 timer),並透過 ai_game() 排程還沒分出勝負的,把已經分出勝負的就刷新但不畫出來
  4. ai_game() -> tasklet_schedule() 全部尚未完成的棋局
  5. game_tasklet_func -> 透過 queue_work 排程讓 O 和 X 各下一子(ai_one/two_work_func)
  6. ai -> 兩邊各下一子
  7. 等到下一次 timer 喚醒

新增結構體

為了存放多場棋局的資料並且傳送特定棋局的參數至愈排程的函式,新增結構體 kxo_task

/* Declare game infomation for coroutine */
struct kxo_task {
    char turn;
    int finish;
    int id;
    char table[N_GRIDS];
    struct tasklet_struct tasklet;
    struct work_struct ai_one;
    struct work_struct ai_two;
    struct work_struct draw;
    ...
};

傳遞參數

tasklet 和 workqueue 都無法直接傳遞額外參數。它們只能接受固定型別的 callback 函式:

tasklet_func(unsigned long data)
work_func_t(struct work_struct *w)

實作時,需要在 kxo_task 中定義 tasklet_struct 和 work_struct 的結構體,並且在模組初始化階段定義執行的函式

// tasklet_struct 初始化
tasklet_init(&cur->tasklet, game_tasklet_func, (unsigned long)cur);
// work_struct 初始化
INIT_WORK(&cur->ai_one, ai_one_work_func);
INIT_WORK(&cur->ai_two, ai_two_work_func);

在函式被執行後用 cotainer_of() 或是透過指標取得 kxo_task 棋盤資訊

// tasklet
static void game_tasklet_func(unsigned long __data) {
    struct kxo_task *cur = (struct kxo_task *) __data;
    ...
}
// workqueue
static void ai_two_work_func(struct work_struct *w) {
    struct kxo_task *cur = container_of(w, struct kxo_task, ai_two);
    ...
}

狀況排除

mutex lock 問題

按照上述策略修改程式碼後會觸發以下錯誤

[ 4488.745102] kxo: [CPU#1] start doing ai_one_work_func
[ 4488.745349] BUG: scheduling while atomic: kworker/u33:0/6432/0x00000002
...
[ 4489.388419] kxo: [CPU#0] ai_one_work_func completed in 1293411 usec
[ 4489.388421] BUG: workqueue leaked atomic, lock or RCU: kworker/u33:1[6061]
                    preempt=0x7fffffff lock=0->0 RCU=0->0 workfn=ai_one_work_func [kxo]

觸發的時間點是在 ai_one_work_func 呼叫 get_cpu 並且使用 mutex 後,推測是因為調用了多場棋局但全部共用一個 mutex lock 導致的,所以試著先改成每個棋盤一個 mutex

/* Declare game infomation for coroutine */
struct kxo_task {
...
+  struct mutex lock;
};

改完之後就不再有該問題了,但是發現電腦會變很卡,而且每一場棋局都只有 ai O 在下棋

commmit 70162cf

ai O 連下問題

[  244.107387] kxo: [CPU#7] doing AI game
[  244.119731] kxo: [game 6] AI O played at 0
[  244.140031] kxo: [game 0] AI O played at 11
[  244.145553] kxo: [game 0] AI O played at -1
[  244.148246] kxo: [game 6] AI O played at -1

結果沒什麼大不了,只是我在 game_tasklet_func 中決定排程時條件判斷的變數忘了改。

mutex lock 問題 again

原本以為我已經排除了,結果只是因為我把每個棋盤的 mutex lock 分開後只在每個棋盤排程 ai O 所以沒有觸發等待,把 ai X 加入後該問題又跟著回來了,即便我只使用一個棋盤還是會發生,而且當我把兩個 ai 任務的 mutex_lock 都註解掉時,這個錯誤又不發生了,之後可以考慮不要使用 mutex,但目前先研究一下觸發錯誤的原因
觀察 get_cpu() 的程式碼

#define get_cpu()		({ preempt_disable(); __smp_processor_id(); })

Keeping Kernel Code Preempt-Safe

排程策略修改

commit f71ff80

目前的作法在任一個棋盤(cdev)被 open 就會全部的棋局都開始運算,接下來改成只有被開啟的棋局需要被排程。
先在 kxo_task 中新增 bool playing 來識別該棋局有無被開啟

/* Declare game infomation for coroutine */
struct kxo_task {
...
+  bool playing;
};

kxo_open 中透過 inode 來得知現在被開啟的棋盤編號

int minor = MINOR(inode->i_rdev);
game_list[minor].playing = true;

最後在 timer_handler 中只排程有被開啟的棋局

加入多場棋局 (畫圖)

前面只執行了多棋局的運算,接下來在核心層級把在畫圖加回來,並且要可以支援多棋局觀看

kxo 畫圖流程

維護棋盤

  1. game_tasklet_func 每下一子就排程
    • 在 tasklet 裡面在排程完兩個 AI 後會排程 draw_board_work_function
  2. draw_board_work_function 搬運資料
    • draw_board() 把棋盤資料從 table 搬到 draw_buffer,並加入棋盤格和換行
    • produce_board()draw_buffer 的資料寫進 kfifo
    • 這個流程在 timer_handler 中若是棋局結束也會執行一遍

呼叫 read 後

  1. 使用 kfifo_to_user() 傳遞 rx_fifo 內的資料給使用者層級
  2. 在迴圈內等待,由 draw_board_work() 或 AI 透過 rx_wait 來通知 kxo_read() 傳送資料給使用者

修改程式碼

Commit 2eab22c

在結構體內新增傳送棋盤資訊用的參數

struct kxo_task {
    ...
+    char draw_buffer[DRAWBUFFER_SIZE];
+    DECLARE_KFIFO_PTR(rx_fifo, unsigned char);
+    wait_queue_head_t rx_wait;
+    struct mutex read_lock;
};

剩下就是根據執行時的 id 維護對應的棋盤資訊來達成顯示多個棋局的功能

實測透過 cat /dev/kxoN 可以正確的顯示棋盤資訊,但明明沒新的落子卻一直畫新的圖,推估是因為 ai 的計算時間較長,同一個 tasklet 會排程一個 ai 和一個畫圖的 work_struct 進 workqueue,但兩者執行時間落差過大,導致一次 ai 下一個子的同時畫圖的任務已經執行超過一次了,雖然使用 xo-user 觀看棋局時會避免重複繪製棋盤,但這樣的溝通方式還是有改善空間,接下來透過簡化傳送的資料以及把畫圖移至使用者層級來改善。

  1. 核心只負責傳送落子位置
  2. user 透過 read 讀取,紀錄對奕過程
  3. 有新的進度才更新畫面

在使用者層級畫圖

只傳送落子位置

原本的作法是紀錄並傳送整個棋盤,改為只傳送當前的落子位置,由使用者執行紀錄棋盤與畫圖,但是勝負判定還是要在核心模組內進行,所以核心模組還是需要透過 table 紀錄棋盤資訊

先把 produce_board 和 draw_board 移到 xo-user.c,並在 ai 運算完後直接把結果放到 kfifo 裡面,在一個 unsigned short 裡面紀錄換誰、棋盤編號和落子位置

win turn game ID move
1 bit 1 bit 6 bit 1 byte

修改 main.c 和 xo-user.c 並觀察輸出,發現會重複傳送資料以及出現錯誤的 game id

get: win=0 turn=0 game=0 move=13
get: win=0 turn=0 game=0 move=13
get: win=0 turn=1 game=0 move=6
get: win=0 turn=0 game=0 move=6
get: win=0 turn=0 game=0 move=0
get: win=0 turn=0 game=0 move=0
get: win=0 turn=1 game=0 move=10
get: win=0 turn=0 game=0 move=10

實際印出 ai 計算完放到 kfifo 中的值發現跟預先規劃的配置不同

[ 4042.173518] kxo: [game 0] AI O played at 8
[ 4042.173524] write    1 to kfifo
[ 4042.521057] kxo: [game 0] AI X played at 7
[ 4042.521067] write 4001 to kfifo
[ 4043.405204] kxo: [game 0] AI O played at 4
[ 4043.405210] write    1 to kfifo
[ 4043.515363] kxo: [game 0] AI X played at 11
[ 4043.515379] write 4001 to kfifo
[ 4044.161128] kxo: [game 0] AI O played at 0
[ 4044.161138] write    0 to kfifo

發現原因是我在把 ai 算出來的 move 轉成設定的資料格式並寫到 step 時沒有使用 WRITE_ONCE

    if (move != -1) {
        WRITE_ONCE(cur->table[move], cur->turn);
--      step = produce_step(0, cur->turn, cur->id, move);
++      WRITE_ONCE(step, produce_step(0, cur->turn, cur->id, move));
        kfifo_in(&cur->rx_fifo, &step, sizeof(step));
        pr_info("write %4x to kfifo", step);
    }

修正之後就確定寫進 kfifo 的數值是正常的

// ai work function
[ 9243.892347] kxo: [game 0] AI O played at 13
[ 9243.892353] write    d to kfifo
[ 9244.229855] kxo: [game 0] AI X played at 6
[ 9244.229865] write 4006 to kfifo
[ 9245.205444] kxo: [game 0] AI O played at 0
[ 9245.205450] write    0 to kfifo
[ 9245.227057] kxo: [game 0] AI X played at 10
[ 9245.227069] write 400a to kfifo
[ 9245.974008] kxo: [game 0] AI O played at 7
[ 9245.974013] write    7 to kfifo
[ 9246.232978] kxo: [game 0] AI X played at 9
[ 9246.232987] write 4009 to kfifo
[ 9246.951869] kxo: [game 0] AI O played at 4
[ 9246.951874] write    4 to kfifo
[ 9247.240457] kxo: [game 0] AI X played at 8
[ 9247.240472] write 4008 to kfifo
// timer_handler 判定勝負並傳送勝利資訊
[ 9247.743584] write 8000 to kfifo
[ 9247.743599] kxo: game 0 -> X win!!!

但是在 xo.user.c 還是會重複讀取跟讀到亂數,經過觀察 dmesg 發現錯誤總是發生在讀取大於 0xFF 的數之後,推測原因是 kfifo_to_user 可以一次複製超過一個 byte 的資料到 user-space 但是他的 pointer 只會移動一個 byte ,所以改成把 unsigned short 拆成兩個 byte 分開傳送,就可以收到正確的資料
user space

raw data : d -> win=0 turn=O game=0 move=13
raw data : 4006 -> win=0 turn=X game=0 move=6
raw data : 0 -> win=0 turn=O game=0 move=0
raw data : 400a -> win=0 turn=X game=0 move=10
raw data : 7 -> win=0 turn=O game=0 move=7
raw data : 4009 -> win=0 turn=X game=0 move=9
raw data : 4 -> win=0 turn=O game=0 move=4
raw data : 4008 -> win=0 turn=X game=0 move=8
raw data : 8000 -> win=1 turn=O game=0 move=0

kernel space

[40778.751992] kxo: [game 0] AI O played at 13
[40778.751996] write    d to kfifo
[40779.092108] kxo: [game 0] AI X played at 6
[40779.092114] write 4006 to kfifo
[40780.063947] kxo: [game 0] AI O played at 0
[40780.063952] write    0 to kfifo
[40780.088828] kxo: [game 0] AI X played at 10
[40780.088835] write 400a to kfifo
[40780.833132] kxo: [game 0] AI O played at 7
[40780.833135] write    7 to kfifo
[40781.095380] kxo: [game 0] AI X played at 9
[40781.095388] write 4009 to kfifo
[40781.814470] kxo: [game 0] AI O played at 4
[40781.814473] write    4 to kfifo
[40782.102551] kxo: [game 0] AI X played at 8
[40782.102558] write 4008 to kfifo

[40782.605627] kxo: [CPU#0] enter timer_handler
[40782.605667] write 8000 to kfifo
[40782.605672] kxo: game 0 -> X win!!!