# 2025q1 Homework3 (kxo)
contributed by < `vicLin8712` >
## 問題紀錄
### Kxo `xo-user.c` 檔案分析
此檔案示範如何在 userspace 端與 kernel space 進行通訊，此檔案為 user space 端的程式碼。
```C
#define XO_STATUS_FILE "/sys/module/kxo/initstate"
static bool status_check(void)
{
FILE *fp = fopen(XO_STATUS_FILE, "r");
if (!fp) {
printf("kxo status : not loaded\n");
return false;
}
char read_buf[20];
fgets(read_buf, 20, fp);
read_buf[strcspn(read_buf, "\n")] = 0;
if (strcmp("live", read_buf)) {
printf("kxo status : %s\n", read_buf);
fclose(fp);
return false;
}
fclose(fp);
return true;
}
```
`status_check` 用於檢測對應模組是否掛載。
`FILE` 結構體屬於 `<stdio.h>` ，此宣告意即將 `fp` 指向 `XO_STATUS_FILE`，並且僅可讀。
注意到其指向 `/sys/module/kxo/initstate`，為何不是 `dev` 等檔案系統?
`/sys` 檔案系統主要用於暴露檔案資訊給存取者，而 `/dev` 用於存取硬體資訊，故而放置在 `/sys` 內部。另一個問題是裝置狀態儲存位置需要額外在核心模組寫入嗎?
查看`main.c:492 ret = device_create_file(kxo_dev, &dev_attr_kxo_state);` 發現其利用`linux devices` 所提供的 `device_create_file`，建立一個於 `sys` 的檔案用於儲存 `kxo_dev` 的狀態，當然前面需要先建立 `kxo_dev` 的物件(後續會討論到)。
`fget` 用於讀取 `fp` 的20個字元，注意到 C11 標準內提到 `fget` 僅會讀取到換行符號(或檔案結束)為止，並於最後保留 `\0`，也就是僅會讀取最多19個 bytes。問題是究竟 `fget` 所獲得的 bytes 會有何種形式?回顧到 `fp` 的創建，需回去查看核心模組的原始碼，後續再追蹤，在此先認為他會回傳某些用於判斷模組正常與否的資料。
`strcspn` 用於取出兩者字串一樣的位置，在此例也就是 `read_buf` 出現 `\n` 的位置，將其設置為 0 避免掉換行。
```c
static struct termios orig_termios;
static void raw_mode_disable(void)
{
tcsetattr(STDIN_FILENO, TCSAFLUSH, &orig_termios);
}
static void raw_mode_enable(void)
{
tcgetattr(STDIN_FILENO, &orig_termios);
atexit(raw_mode_disable);
struct termios raw = orig_termios;
raw.c_iflag &= ~IXON;
raw.c_lflag &= ~(ECHO | ICANON);
tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
}
```
`termios` 查詢此結構體的使用，可參考 [termios(3) — Linux manual page](https://www.man7.org/linux/man-pages/man3/termios.3.html) ，此標頭檔提供用於控制終端機，terminal，所需的基本操作。
終端機在此專案中用以呈現下棋步驟，其中步驟由核心模組的演算法所決定。先查看 `raw_mode_enable` ，`tcgetattr` 取得 `STDIN_FILENO` 所對應的檔案描述符 (STDIN_FILENO 實際上 = 0)，並將其賦予後者 `orig_termios`。
#### 主要目的
使用者端建立輸出列印機制，在終端機顯現出來自 kernel module 所提供的資訊，以及接收來自鍵盤輸入的相關命令。第一個問題是該如何建立一個機制，使得持續列印出 kernel 所提供的資訊，同時亦監聽鍵盤輸入，若有輸入特定命令則及時響應。
```c
FD_ZERO(&readset);
FD_SET(STDIN_FILENO, &readset);
FD_SET(device_fd, &readset);
```
上方函式利用 `fcntl` 函式庫功能將 kernel 輸入與鍵盤輸入添加至讀取集合 `readset` 中。
```c
int result = select(max_fd + 1, &readset, NULL, NULL, NULL);
if (result < 0) {
printf("Error with select system call\n");
exit(1);
}
```
`result` 設為執行 `select` 的結果，可查詢 s[elect(2) — Linux manual page](https://man7.org/linux/man-pages/man2/select.2.html)，此函式目的在於等待 `readset` 內 `fd` 有 I/O 事件發生，則回傳給 `result`，下方為避免錯誤發生所添加的判斷式。
```C
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, DRAWBUFFER_SIZE);
display_buf[DRAWBUFFER_SIZE - 1] = '\0';
printf("%s", display_buf);
}
```
上方函式判斷究竟是哪個 `fd` 發生 I/O 事件，使用 `FD_ISSET` 巨集，以第一個條件判斷式來說，即為 `STDIN_FILENO` 發生 I/O，因此進行 `listen_keyboard_handler()` 函式用以處理輸入的字串判斷後續相對應動作。 `else if` 則用以判斷 kernel I/O 所做的相對應處理。
結束後需要回復原先終端機設定，並關閉 kernel 的 `fd`，如下。
```c
raw_mode_disable();
fcntl(STDIN_FILENO, F_SETFL, flags);
close(device_fd);
```
### Kxo `main.c` 檔案分析
此為 kernel module 檔案，因此先由 `init` 部分觀察，再延伸至後續所引用到的程式碼。
`dev_t` 為 Linux Kernel 用於管理裝置識別碼的一個結構。
```c
dev_t dev_id;
```
接下來要在 kernel space 嘗試分配記憶體，如下方操作
```c
if (kfifo_alloc(&rx_fifo, PAGE_SIZE, GFP_KERNEL) < 0)
return -ENOMEM;
/* Register major/minor numbers */
ret = alloc_chrdev_region(&dev_id, 0, NR_KMLDRV, DEV_NAME);
if (ret)
goto error_alloc;
major = MAJOR(dev_id);
```
`kfifo_alloc()` 將記憶體分配至 `rx_fifo` 指標所指向的地址，同時賦予 `PAGE_SIZE` 大小的記憶體，可用 `getconf PAGE_SIZE` 查詢當前 kernel 的 page size。`GFP_KERNEL` ，get free page 為 kfifo 的 flag，可於 [kfifo](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 查詢。同時文中也提及宣告 `kfifo` 指標的方式，即為利用 API `DECLARE_KFIFO_PTR`。
`alloc_chrdev_region` 為 [Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.alloc_chrdev_region)，其功能原文為 register a range of char device numbers ，即可向核心註冊所需要的裝置編號範圍。
註冊編號後，接下來要將裝置綁定相對應的操作，如下程式碼
```c
cdev_init(&kxo_cdev, &kxo_fops);
ret = cdev_add(&kxo_cdev, dev_id, NR_KMLDRV);
```
`cdev_init` 可在 [Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.alloc_chrdev_region) 查詢，其將 `cdev` 結構初始化，並與 `kxo_fops` 操作進行綁定。
接下來將先前向核心註冊的裝置編號與 `kxo_cdev` 進行綁定。
註冊完裝置編號與綁定相關驅動操作後，接下來就可以向檔案系統創建檔案供 user space 操作，參考如下程式碼
```c
struct device *kxo_dev =
device_create(kxo_class, NULL, MKDEV(major, 0), NULL, DEV_NAME);
ret = device_create_file(kxo_dev, &dev_attr_kxo_state);
```
裝置的結構與相關操作可以在 [Device drivers infrastructure](https://www.kernel.org/doc/html/latest/driver-api/infrastructure.html) 查閱，第一個結構 `kxo_dev` 利用 `device_create` 建立此類別的裝置，後續使用 `device_create_file` 建立個別裝置檔。
下一步建立 buffer 以供裝置檔案使用，利用 `fast_buf.buf = vmalloc(PAGE_SIZE)`
:::info
`vmalloc` 所建立的記憶體空間有何特性?
:::
下行程式碼將棋盤填入空白，也就是初始化之意思。
```c
memset(table, ' ', N_GRIDS);
```
下一步對此棋盤屬性進行宣告，如下
```c
attr_obj.display = '1';
attr_obj.resume = '1';
attr_obj.end = '0';
rwlock_init(&attr_obj.lock);
```
`attr_obj` 定義有四個屬性，接下來著重探討 `rwlock` 。
#### timer_handler
此程式碼模擬固定時間產生 hard_irq 訊號給 CPU，並進行 soft_irq 做後續處理。而 `timer_handler` 則用於控制時間計時用以當作發出 hard_irq 訊號的依據。
整體的運作流程:
1. 關閉 cpu irq
2. 開始計時
3. 檢查勝利條件
4. 結束計時
5. 開啟 cpu irq
延伸 3. 檢查勝利條件，也就是可以分為有結果與尚未有結果，這邊觀察尚未有結果的程式碼。
在並行處理時，需先鎖住當前棋盤狀態，僅供狀態讀取
```c
read_lock(&attr_obj.lock);
```
接下來進行 kernel 端的棋盤規劃，當棋盤對奕尚未結束，則進行 `ai_game()`
##### ai_game
`ai_game()` 為人工智慧演算法執行的函式，其需在 `irq_disable` 的條件之下利用 `tasklet_schedule` 將 `game_tasklet` 進行排程。接下來探討 `game_tasklet` 函式。
由 `static DECLARE_TASKLET_OLD(game_tasklet, game_tasklet_func);` 巨集宣告 `game_tasklet`，探討 `game_tasklet_func`，分析程式碼如下
```c
READ_ONCE(finish);
READ_ONCE(turn);
smp_rmb();
if (finish && turn == 'O') {
WRITE_ONCE(finish, 0);
smp_wmb();
queue_work(kxo_workqueue, &ai_one_work);
} else if (finish && turn == 'X') {
WRITE_ONCE(finish, 0);
smp_wmb();
queue_work(kxo_workqueue, &ai_two_work);
}
queue_work(kxo_workqueue, &drawboard_work);
```
`READ_ONCE` 與 `smp_rmb` 規定了操作順序，`READ_ONCE` 避免了編譯器優化作出的打亂排序，`smp_rmb` 確保了所有 read 操作須在此函式前完成。
後續針對不同的 `turn` ，呼叫對應的 `ai_worker` 排入 `work_queue` 中等待演算，並於最後將 `drawboard_work` 排入排程。
接下來查看 `ai_worker` 程式碼
```c
mutex_lock(&producer_lock);
int move;
WRITE_ONCE(move, mcts(table, 'O'));
smp_mb();
if (move != -1)
WRITE_ONCE(table[move], 'O');
WRITE_ONCE(turn, 'X');
WRITE_ONCE(finish, 1);
smp_wmb();
mutex_unlock(&producer_lock);
```
上方程式碼先將 `producer` 鎖住，避免多下棋者要存取修改當前的棋盤資訊，再將 `mcts` 演算法計算出下一個 `move`，最後再修改棋盤 flag 並解鎖。
## 減少通訊成本
### 棋盤移植至 user space
原先機制會在 kernel space，透過函式 `draw_board` 繪製，並儲存在 `draw_buffer` 字元陣列中。也因此在繪製新棋盤時需要利用 mutex lock 鎖住，而後再藉由 `kfifo_in` 函式將 `draw_buff` 資料存入 circular buffer 之中，後續再由 user space 處理 circular buffer 資訊。
首先先將繪製棋盤的函式 `draw_board` 移至到 user space 中，在 `xo-user.c` 檔中，原先需讀取全部資訊，包含棋盤，落子，而更改後，僅需讀取落子順序，再搭配原先在 kernel space 移至 user space 的棋盤繪製函數，即可繪製出下棋過程
>[commit 12b41f0](https://github.com/vicLin8712/kxo/commit/12b41f0792d095cb68216ca37eba13d65b0f4a40)
## 並行處理
Sign in with Wallet
Connect another wallet