# 2025q1 Homework3 (kxo)
contributed by < `Charlie-Tsai1123` >
:::danger
注意細節
:::
## 問題修正
### 出現亂碼
在執行 ```sudo ./xo-user``` 若按下 ctrl + P 會暫停繪製棋盤的畫面但會出現以下錯誤
<!-- <s>
</s>
:::danger
注意看作業規範：文字訊息不要用圖片展現
::: -->
```bash
O| | |
-------
|X|X|
-------
| | |O
-------
O| | |
-------
���Stopping the kernel space tic-tac-toe game...
```
我先找到 ctrl + P 的程式碼位子，在 xo-user.c 中
```c
int attr_fd = open(XO_DEVICE_ATTR_FILE, O_RDWR);
```
XO_DEVICE_ATTR_FILE 是用來更改遊戲的狀態
```c
case 16: /* Ctrl-P */
read(attr_fd, buf, 6);
buf[0] = (buf[0] - '0') ? '0' : '1';
read_attr ^= 1;
write(attr_fd, buf, 6);
if (!read_attr)
printf("Stopping to display the chess board...\n");
break;
```
從這段程式可以得知，buf[0] 是用來控制程式是否顯示棋盤 read 部份負責看現在的狀態 write 部份則更改現在狀態，從這部份我對修改這個錯誤沒有頭緒，所以轉向觀察輸出棋盤的程式 main.c
發現輸出棋盤的地方好像沒有加上 '\0' 這樣 printf 處理時不知道哪裡終結可能會出現亂碼，所以做了以下修改
```main.c```
```diff
while (i < DRAWBUFFER_SIZE) {...}
+ draw_buffer[i - 1] = '\0';
```
```xo-user.c```
```c
- printf("%s", display_buf);
+ printf("%s\n", display_buf);
```
### 改善 ctrl + Q
>commit [0e1d9b4](https://github.com/sysprog21/kxo/commit/0e1d9b45ab65b2564159dc783e48a5ee21f381f4)
## 畫面呈現在使用者層級
>commit [5377a9c](https://github.com/sysprog21/kxo/commit/5377a9c6b9c368ca054956e6b39a89ad4e225df4)
### 修改 ```draw_buffer```
參考 rota1001
從原本的 ```DRAWBUFFER_SIZE``` 可以得知 ```draw_buffer``` 紀錄了整個畫面的資訊，也因此從 kernel mode 傳到 user mode 會用很多資源 (66 bytes 以 4x4 為例)，那要如何減少？每格狀態只會有三種 ('O', 'X', ' ') 但三不是 2 的冪，所以要用 2 個 bit 表示 (4種狀態)，所以傳遞資訊只需要 ```BOARD_SIZE``` $\times$ ```BOARD_SIZE``` $\times$ 2 bits (32 bits = 1 bytes 以 4x4 為例) 因此我將 ```draw_buffer``` 的型別改用 ```unsigned int```
```diff
- static char draw_buffer[DRAWBUFFER_SIZE];
+ static unsigned int draw_buffer;
```
:::danger
提供更多數學分析
:::
然後從 ```main.c``` ```draw_board``` 可以發現 ```draw_buffer``` 的更新是根據 ```table``` ，它紀錄了每個位子的符號
```c
draw_buffer[i++] = j & 1 ? '|' : table[k++];
```
所以可以思考該如何把 ```O```, ```X```, ``` ``` 用三個狀態表示，我先列出他們三個的 Asquii Code:
| ```O``` | ```X``` | ``` ``` |
| -------- | -------- | -------- |
| 1==00==1111 | 1==01==1000 | 0==10==0000 |
可以發現黃色標起來的地方剛好可以用 2 bits 代表不同狀態，只需要把那一格的 ```char``` 向右移動 4 格再 and 0b11 = 3 ，因此依序把值填入 ```draw_buffer``` 中
```c
while (i < N_GRIDS) {
draw_buffer |= ((table[k++] >> 4) & 3) << (i << 1);
i++;
}
```
>[!Note]明明第三跟第四個 bit 就可以表示三個狀態了為什麼要用第五跟第六
>| ```O``` | ```X``` | ``` ``` |
>| -------- | -------- | -------- |
>| 100==11==11 | 101==10==00 | 010==00==00 |
>
>因為等等在 user mode 的 draw_board 不想用到 if else
### 移動 ```draw_board``` 到 user mode
```c
const char mapping[3] = {'O', 'X', ' '};
```
仔細觀察剛剛用來代表 ```O```, ```X```, ``` ``` 的值，剛剛好分別對應 0, 1, 2 ，所以可以創見一個大小為 3 的陣列分別就把 0, 1, 2 對應到 ```O```, ```X```, ``` ```
```c
static int draw_board(unsigned int display_buf)
{
const char mapping[3] = {'O', 'X', ' '};
for (int i = 0; i < BOARD_SIZE; i++) {
putchar(mapping[display_buf & 3]);
display_buf >>= 2;
for (int j = 0; j < BOARD_SIZE - 1; j++) {
putchar('|');
putchar(mapping[display_buf & 3]);
display_buf >>= 2;
}
putchar('\n');
for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) {
putchar('-');
}
putchar('\n');
}
return 0;
}
```
>[to do] 測試是否真的效率較好
## 引入 coroutine
首先我看了 <[並行程式設計：排程器原理](https://hackmd.io/@sysprog/concurrency-sched)> 中的 coro.c 程式碼，裡面使用了 setjmp 跟 longjmp 處理 coroutine
嘗試在 main.c 使用 setjmp.h 出現以下錯誤
```bash
/home/charlie-tsai/linux2025/hw/kxo/main.c:15:10: fatal error: setjmp.h: No such file or directory
15 | #include <setjmp.h>
| ^~~~~~~~~~
compilation terminated.
```
根據 《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(lkmpg) 5.2
>One point to keep in mind is the difference between library functions and system calls. Library functions are higher level, run completely in user space and provide a more convenient interface for the programmer to the functions that do the real work — system calls. System calls run in kernel mode on the user’s behalf and are provided by the kernel itself.
因為 setjmp/longjmp 是 glibc 提供的函式，設計給 user space 使用，依賴 user space 的 stack ，因為 kernel 沒有使用 glibc 所以無法使用
想法：
將不同演算法下棋也可以運作在 user space 並用 coroutine 在 AI1, AI2, draw_board 間輪流執行
### 讓 user space 可以使用 kernel space 函式 (mcts, negamax)
>Commit [166d6e4](https://github.com/sysprog21/kxo/commit/166d6e40758cea1ba13fbb1644b1ded0cd366745)
首先要讓 user space 可以使用 mcts 跟 negamax 這兩個函式，先去翻了 lkmpg 並學習了 ioctl 的用法以及第六章提及的 [character device driver](https://sysprog21.github.io/lkmpg/#character-device-drivers)
>[!Note] Device
>device 分成兩種 character devices 跟 block devices
>| character devices | block devices |
>| -------- | -------- |
>| input or output many or as few bytest they like | input output through fix-sized buffer |
>||buffer for request 可以選擇順序(就像選擇更近的 sector 存取資料)
<!-- #### 嘗試自己寫 kernel module 並讓 user space 使用 -->
==修改 file_operations==
file_operations 定義了各種 device 的函式
```diff
static const struct file_operations kxo_fops = {
.read = kxo_read,
.llseek = no_llseek,
.open = kxo_open,
.release = kxo_release,
.owner = THIS_MODULE,
+ .unlocked_ioctl = kxo_ioctl,
};
```
==define magic number==
magic number 可以辨別不同的 ioctl 指令來源，這裡想要讓 ```mcts``` ```negamax_predict``` 讓使用者使用，所以需要用到兩組 magic number
```c
#define MY_IOCTL_MAGIC_MCTS 'O'
#define MY_IOCTL_MCTS _IOWR(MY_IOCTL_MAGIC_MCTS, 1, unsigned int)
#define MY_IOCTL_MAGIC_NEGAMAX 'X'
#define MY_IOCTL_NEGAMAX _IOWR(MY_IOCTL_MAGIC_NEGAMAX, 1, unsigned int)
```
==完成 kxo_ioctl==
進行四個步驟：
1. kernel space 讀取 user space 傳過來的資料 --> ```copy_from_user```
2. 將收到的 unsigned int 轉成 char* --> ```int_to_table```
3. run ```mcts``` 或 ```negamax_predict```
4. 將 kernel space 產生的最佳位子傳回到 user space --> ```copy_to_user```
```c
switch (cmd) {
case MY_IOCTL_MCTS:
if (copy_from_user(&value, (unsigned int __user *) arg,
sizeof(unsigned int)))
return -EFAULT;
int_to_table(value, user_table);
value = mcts(user_table, 'O');
if (copy_to_user((unsigned int __user *) arg, &value,
sizeof(unsigned int)))
return -EFAULT;
return 0;
case MY_IOCTL_NEGAMAX:
if (copy_from_user(&value, (unsigned int __user *) arg,
sizeof(unsigned int)))
return -EFAULT;
int_to_table(value, user_table);
value = negamax_predict(user_table, 'X').move;
if (copy_to_user((unsigned int __user *) arg, &value,
sizeof(unsigned int)))
return -EFAULT;
return 0;
default:
return -EINVAL;
```
==修改 user space 程式==
用 ```ioctl``` 傳入棋盤並回傳最佳下棋位子，接著再更新
空棋盤會是 ```0b10101010101010101010101010101010``` 每一格都是 10 因為代表 ``` ``` (可以看上面 mapping 的方法)
* mcts 只要清空那一格就好 (```00``` 代表 ```O```) :
user_draw_buffer &= ~(0b11 << (move << 1));
* negamax 還要 or 01 (```01``` 代表 ```X```) :
user_draw_buffer &= ~(0b11 << (move << 1));
user_draw_buffer |= (0b01 << (move << 1));
```c
void task_mtcs(int fd)
{
finish++;
unsigned int move = user_draw_buffer;
ioctl(fd, MY_IOCTL_MCTS, &move);
if (move != -1) {
user_draw_buffer &= ~(0b11 << (move << 1));
}
}
void task_negamax(int fd)
{
finish++;
unsigned int move = user_draw_buffer;
ioctl(fd, MY_IOCTL_NEGAMAX, &move);
if (move != -1) {
user_draw_buffer &= ~(0b11 << (move << 1));
user_draw_buffer |= (0b01 << (move << 1));
}
}
```
結果
上面是 kernel space 執行的，下面是 user space 執行的
```bash
|O|O|
-------
| | |
-------
|X| |
-------
| | |
-------
=======
=======
| | |
-------
|X| |
-------
| | |O
-------
| | |
-------
```
>[to do] 目前犯了個錯誤因為 user space 沒辦法使用 check_win （因為在 kernel ）所以我是讓 mcts 跟 negamax 總共呼叫 16 次再開始新的一局，之後想要寫在 user space 判斷棋盤勝利
### 使用 coroutine
上面實做完後，目前是讓兩個 ai 更新完 table 後再執行 draw_board
```diff
if (FD_ISSET(STDIN_FILENO, &readset)) {
FD_CLR(STDIN_FILENO, &readset);
listen_keyboard_handler();
} else if (read_attr && FD_ISSET(device_fd, &readset)) {
FD_CLR(device_fd, &readset);
printf("\033[H\033[J"); /* ASCII escape code to clear the screen */
read(device_fd, &display_buf, sizeof(display_buf));
+ task_mtcs(device_fd);
+ task_negamax(device_fd);
draw_board(display_buf, user_draw_buffer);
}
```
那現在想要將這兩個函式跟 draw_board 還有 keyboard handler 改成使用 coroutine
## 讀懂程式
### mcts.c
MCTS 演算法分成三步（參考[Monte Carlo Tree Search 解說](https://www.youtube.com/watch?v=J3I3WaJei_E)）
1. sellect
2. rollout && expand
- rollout (還沒有更新過 n~i~ = 0)
- expand (有更新過了 --> 往下試探新增新的節點)
3. backpropagate (往上更新結果 n~i~++ , w~i~++ if win)
>n~i~ 是右邊的數字代表模擬了幾次， w~i~ 是贏得次數
:::danger
數學分析呢？
:::
### ```xo-user.c```
```xo-user.c``` 用來控制並顯示來自 Linux kernel space 的圈圈叉叉（XO）遊戲，透過 /dev/kxo 與 /sys/class/kxo/kxo/kxo_state 與核心模組互動。
(/dev/kxo 內有棋盤的資訊、/sys/class/kxo/kxo/kxo_state 內有遊玩狀態的資訊)
#### ```static bool status_check(void)```
### ```main.c```
## 閱讀 lkmpg
Sign in with Wallet
Connect another wallet