# linux2025-homework3
contributed by <PigeonSir>
:::danger
注意書寫規範！
:::
# KXO
ai 演算法 : mcts.c, negamax.c
kxo module : main.c
user-mode 觀看棋局 : xo-user.c
遊戲規則 ＆ 勝利判定 : game.c
## zoberst.c
一開始編譯 kxo 時發生錯誤，其原因為 zobrist.c 中的 u128 未定義，暫時透過新增定義解決
```c
#define u128 __uint128_t
```
但詢問 chatgpt 發現該操作存在風險，因為並非所有架構都支援 `__uint128_t`，查看該函式的程式碼
```c
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;
}
```
:::danger
說好的進度呢？
:::
# 加入 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
```c
/* 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 函式：
```c
tasklet_func(unsigned long data)
work_func_t(struct work_struct *w)
```
實作時，需要在 kxo_task 中定義 tasklet_struct 和 work_struct 的結構體，並且在模組初始化階段定義執行的函式
```c
// 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` 棋盤資訊
```c
// 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
```diff
/* Declare game infomation for coroutine */
struct kxo_task {
...
+ struct mutex lock;
};
```
改完之後就不再有該問題了，但是發現電腦會變很卡，而且每一場棋局都只有 ai O 在下棋
> commmit [70162cf
](https://github.com/sysprog21/kxo/commit/70162cf53f277cf7ca52f75ae319921cead6d2c6)
#### 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() 的程式碼
```c
#define get_cpu() ({ preempt_disable(); __smp_processor_id(); })
```
[Keeping Kernel Code Preempt-Safe](https://www.kernel.org/doc/Documentation/preempt-locking.txt)
#### 排程策略修改
> commit [f71ff80](https://github.com/sysprog21/kxo/commit/f71ff80bf12465e64c3c6673ee7a5160f03d8e63)
目前的作法在任一個棋盤（cdev）被 open 就會全部的棋局都開始運算，接下來改成只有被開啟的棋局需要被排程。
先在 `kxo_task` 中新增 `bool playing` 來識別該棋局有無被開啟
```diff
/* Declare game infomation for coroutine */
struct kxo_task {
...
+ bool playing;
};
```
在 `kxo_open` 中透過 `inode` 來得知現在被開啟的棋盤編號
```c
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](https://github.com/sysprog21/kxo/commit/2eab22cb150bcf4c093d32b1f435f46bd81d1610)
在結構體內新增傳送棋盤資訊用的參數
```diff
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. 有新的進度才更新畫面
## 在使用者層級畫圖
### 只傳送落子位置
> commit [b75b3d6](https://github.com/sysprog21/kxo/commit/b75b3d680af7a01bd549ec3616df96f2f65390a4)
原本的作法是紀錄並傳送整個棋盤，改為只傳送當前的落子位置，由使用者執行紀錄棋盤與畫圖，但是勝負判定還是要在核心模組內進行，所以核心模組還是需要透過 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 |
win: 為 1 時代表有人贏了
turn: 'X' -> 1 'O' -> 0
修改 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
```diff
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!!!
```
#### 觀察溝通成本的變化
比較在兩種溝通方式各下 100 局
先嘗試統計原始的程式碼 kxo_read 的資料
=== kxo_read timing report ===
Total Calls : 1822
Avg time (us) : 108118.164
Max time (us) : 247843.300
Top 10 Longest Calls:
247843.3
247446.3
247150.1
247116.1
247014.6
246969.2
246808.0
246707.7
246618.1
246578.5
測試新版的程式碼
=== kxo_read timing report ===
Total Calls : 82
Avg time (us) : 479325.243
Max time (us) : 996201.100
Top 10 Longest Calls:
996201.1
994974.3
989618.1
982364.0
898238.9
889721.9
889645.3
885614.0
878803.3
855962.8
### 畫一場棋局
> commit [0e3b576](https://github.com/sysprog21/kxo/commit/0e3b576d3cb375f8d3fbafb3303cbfdb2458aa30)
先嘗試在 xo.user.c 接收、解碼並儲存棋盤資訊，前面已經成功將正確的 step 放到 kfifo 中，但後續發現在使用者空間解碼並顯示出來時還是會重複讀取跟讀到亂數，經過觀察 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!!!
```
先實現在 user space 畫出一個棋盤，使用原本在核心模組的作法，透過 char table[][] 儲存每個棋盤的資料，在 main 中接到一個新的 step 後會先把兩個 byte 轉為一個 unsigned short 並呼叫
draw_board()
```
raw data : 4 -> win=0 turn=O game=0 move=4
O| | |
-------
O| |X|O
-------
|X|X|
-------
|O| |
-------
raw data : 4008 -> win=0 turn=X game=0 move=8
O| | |
-------
O| |X|O
-------
X|X|X|
-------
|O| |
-------
raw data : c000 -> win=1 turn=X game=0 move=0
game 0 : X win !!!
```
### 畫多場棋局
> commit [6d22236](https://github.com/sysprog21/kxo/commit/6d2223622cb2d46bd25667ce1a148db0526b91b1)
在 xo-user.c 中根據棋盤的數量開啟多個 fd 並存到陣列 fds 中，按照先前的設計核心此時就會開始排程棋局的運算
```c
int fds[MAX_GAME];
int main(int argc, char *argv[])
...
int max_fd = -1;
for (int i = 0; i < MAX_GAME; i++)
{
memset(table[i], ' ', N_GRIDS);
char fileName[32];
sprintf(fileName, XO_DEVICE_FILE, i);
fds[i] = open(fileName, O_RDONLY);
max_fd = fds[i] > STDIN_FILENO ? fds[i] : STDIN_FILENO;
}
...
```
> 這個方式有改良的空間，之前在設計核心模組的時候特別多用一個參數來判定一個棋盤有沒有被開啟，但是 user space 這樣寫的話又變成一次性開起全部了，接下來應該要讓使用者自行決定要不要開啟新的棋局，例如按按鍵切換棋局時如果是之前沒開過的再把它 open 。
在主迴圈中用 select() 同時監看所有棋局的 /dev/kxoX，有資料才 read，然後更新對應的棋盤，為了觀察正確性先把全部的棋盤都畫出來
```c
while (!end_attr) {
FD_ZERO(&readset);
FD_SET(STDIN_FILENO, &readset);
for (int i = 0; i < MAX_GAME; i++)
FD_SET(fds[i], &readset);
int result = select(max_fd + 1, &readset, NULL, NULL, NULL);
```
在 result 大於 0 時代表有鍵盤事件觸發或是有新的落子，此時就要檢查全部的棋盤
```c
for (int i = 0; i < MAX_GAME; i++) {
if (FD_ISSET(fds[i], &readset)) {
// read data and draw board
```
每一次 read 到值之後都會用 draw_board 畫出棋盤，實測可以順利畫出多個棋局
```
raw data : 7 -> win=0 turn=O game=0 move=7
O| | |O
-------
|X| |O
-------
|X|X|O
-------
O| | |
-------
raw data : 101 -> win=0 turn=O game=1 move=1
|O| |
-------
|X|X|
-------
| |X|
-------
O|X|O|
-------
```
### 鍵盤事件切換棋局
> commit ()[]
原先的設計是 read 到新的資料後就會 解碼 -> 更新棋盤 -> 畫出來，現在透過鍵盤事件來決定要畫出來的棋盤 id，使用 > 和 < 來切換（對應 62 跟 60）
Sign in with Wallet
Connect another wallet