2025q1 Homework3 (kxo)

# 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) ## 並行處理

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.