owned this note
owned this note
Published
Linked with GitHub
# 2025q1 Homework3 (kxo)
contribute by < `ginsengAttack` >
:::danger
注意書寫規範！
:::
成果：
```
|O| |
-------
|X|O|
-------
| |X|
-------
| | |X
-------
X win!!!
O| | |
-------
| |X|
-------
|O|X|
-------
| | |
-------
```
:::danger
文字訊息不要用圖片展現
:::
## 減少核心與使用者通訊成本
> commit [e86bee3](https://github.com/sysprog21/kxo/commit/e86bee38dd9a2d448bd4823847bb4ee2e76446f3)
原本的程式碼每次傳送一整個棋盤，我改為傳送單一步數，棋盤繪製由使用者進行，每次傳送僅需要4 bytes ，當某方勝利，由核心向使用者通知勝利訊息，使用者接著印出。
但是程式碼存在 bug，核心傳送的勝利訊息會多一個，目前是採用重新讀一次 buf 解決，導致多傳訊息的地方應該在於核心的處理。
:::danger
提供數學分析
:::
## 輸出規則
測試的時候，我想要印出每一步驟，但是發現問題，printf 是 line-buffered，只有在換行的時候會輸出，其他時候如果輸出長度不足，就會先儲存在緩衝區當中。所以我們的輸出訊息要加入 '\n'。
後來遇到另一個問題，我在輸出勝利訊息的時候，勝利前最後一步不會輸出，把刷新頁面的部份拿掉，一個一個追蹤輸出結果，發現是螢幕刷新速度太快。
為什會刷新太快？其實問題應該改成，為什正常情況下輸出不會太快？後來想通應該也是 printf buffer 的問題，正常情況下印出棋盤後，會接著執行：
```c
printf("\033[H\033[J"); /* ASCII escape code to clear the screen */
```
但是他不會直接刷新螢幕，而是等到下一輪才會和新的棋盤一起輸出，而如果我接著直接輸出誰勝利，就會把最後的棋盤覆蓋掉。
所以之前的問題是 printf 太慢輸出，這邊的問題反而變成太快輸出。
## 整合三種工作到一個 work item
:::danger
明確標示你所參照的學員的 GitHub 帳號名稱
:::
參考<s>同學</s> `timsong1`的想法，我把 ai1 ai2跟傳訊息，整合到一起，打算用 coroutine 實現三者在同一 work item 的並行，所以我先把三者從三個不同的 work item 改成寫在一起變成 `entire_game_func`這個 function，然後發現問題：
```
O| | |
-------
O| | |X
-------
| | |X
-------
| | |
-------
O win!!!
```
排查後發現是我在第一個 commit 提過的 bug，也就是核心勝利訊息會多傳送一個，當時我的解決方法是：
```c
read(device_fd, step, 4);
```
多讀一個勝利訊息卻不處理就好，但是現在核心突然不會傳送重複訊息了？
所以這行變得沒必要了，莫名奇妙少一個 bug ，可能要再研究一下為什。
初步懷疑是之前 timer 觸發的太頻繁，導致一次勝利被兩次偵測到？
:::danger
善用 Ftrace 分析
:::
## 嘗試加入 coroutine 機制
就我對 coroutine 的理解，這種技術應該比較適合應用在 I/O bound 的程式，因為我們可以在進行 I/O 的時候主動儲存自己的狀態，並讓出執行權限。
KXO 程式碼是 CPU bound，所以不太好善用這個機制，不如直接循序執行？就算用 coroutine 也沒有中斷的感覺，因為兩個 ai 下棋，本來就是輪流的，不存在下到一半轉給另一個人下的情境。
我能想到必要用 coroutine 的部份是處理鍵盤事件，或者是我加入 coroutine 的方式有錯誤？
:::danger
使用 Graphviz 重新製圖
:::
大致框架：
```c
#include <setjmp.h>
struct task {
jmp_buf env;
char *task_name;
};
/*for schedule to save status*/
jmp_buf schedule_buf;
struct task *tasklist[3];
/*initial tasklist and add task1 task2 into it*/
static void initial_tasklist(void)
{
/*initial array*/
}
static void switch_task(int current)
{
current %= 3;
longjmp(tasklist[current]->env,1);
}
static void schedule(void)
{
int i = 3;
initial_tasklist();
int current = setjmp(schedule_buf);
/*execute every coroutine
*
* */
switch_task(current);
}
static void task1(void)
{
if(setjmp(tasklist[0]->env) == 0)
longjmp(schedule_buf,1);
/*to do*/
longjmp(schedule_buf,1);
}
static void task2(void)
{
if(setjmp(tasklist[1]->env) == 0)
longjmp(schedule_buf,1);
/*to do*/
longjmp(schedule_buf,1);
}
static void keyboard(void)
{
if(setjmp(tasklist[2]->env) == 0)
longjmp(schedule_buf,1);
/*to do*/
longjmp(schedule_buf,1);
}
```
## coroutine 運行鍵盤事件和對局：
> commit [bda40b6](https://github.com/sysprog21/kxo/commit/bda40b6d62217ba4a8fe73ac58782f39589d65a4)
還沒加入第二個對局。
## 用 select 監聽事件
用 `readset` 紀錄需要監聽的檔案，把對應核心訊息跟鍵盤事件的檔案加入：
```c
FD_ZERO(&readset);//清空
FD_SET(STDIN_FILENO, &readset);//加入
FD_SET(device_fd, &readset);
```
然後就可以用 `select` 同時監聽：
```c
int result = select(max_fd + 1, &readset, NULL, NULL, NULL);
```
接著判斷監聽到的事件來自哪裡：
```c
if (read_attr && FD_ISSET(device_fd, &readset)) {
FD_CLR(device_fd, &readset);//清除
...
}
```
以此同時處理鍵盤跟核心訊息。
## 複數棋局並行：
一開始我是打算將多個 KXO 放入核心，由單個 user 進行處理，但是難度太高，而且沒必要。
考慮到我前面提到的，把對局封裝成單個 workitem ，那我們就可以透過放入複數 workitem 來讓核心實現對局的並行。
接著我們讓每組對局，都能分別和使用者層級的不同 coroutine 進行通訊即可。
首先是封裝的部份：
```c
/*use coroutine to package ai_1、ai_2 and drawboard in one work item
*and tasklet can just put one item into work queue
*/
static void entire_game_func(struct work_struct *w)
{
READ_ONCE(finish);
READ_ONCE(turn);
smp_rmb();
if (finish && turn == 'O') {
WRITE_ONCE(finish, 0);
smp_wmb();
ai_one_work_func(w);
} else if (finish && turn == 'X') {
WRITE_ONCE(finish, 0);
smp_wmb();
ai_two_work_func(w);
}
drawboard_work_func(w);
}
```
### 核心與使用者的通訊
註冊操作：
```c
static const struct file_operations kxo_fops = {
.read = kxo_read,
.llseek = no_llseek,
.open = kxo_open,
.release = kxo_release,
.owner = THIS_MODULE,
};
```
這邊的操作是以結構的形式存在，所以核心中可以有多組這樣子的結構，我一開始沒看清楚這裡，以為核心只能定義一組操作。
然後綁定到界面： `dev/kxo` 中
```c
/* Register the device with sysfs */
struct device *kxo_dev =
device_create(kxo_class, NULL,MKDEV(major, 0), NULL, DEV_NAME);
```
所以使用者端才能透過執行：
```c
device_fd = open(XO_DEVICE_FILE,O_RDONLY);
read(device_fd, step, 4);
```
根據 `dev/kxo` 打開對應的操作，以此執行到 `kxo_read`
所以接下來我要自定義一組新的操作符號，用來傳送對局2的參數。
在設定的時候，我發現了一個參數：
```c
/* We use an additional "faster" circular buffer to quickly store data from
* interrupt context, before adding them to the kfifo.
*/
static struct circ_buf fast_buf;
```
這個東西照字面意思應該是 kfifo 在中斷的緩衝，但是我看不到相關的寫入程式碼，就只有分配跟釋放，所以我把這部份刪掉，然後發現程式碼沒影響，所以我先假裝它不存在。
### 然後我的系統爆掉了
紀錄一下，第一次真的把系統搞到連正常關機都不行，試著一步一步來，先加入另一個界面。
:::danger
幻滅是成長的開始
:::
慢慢排查錯誤，發現好像是我創建的另一個界面沒有關掉。然後用終端機觀察證實：
```c
~/kxo$ cat /proc/devices | grep kxo
510 kxo
```
真的是資源沒釋放乾淨，但我也不知道怎處理，只能用重開機解決一切。
再開就真的沒問題了，至少多了一個 `rx_fifo2` 可以傳資料。
但是我執行
```c
read(device_fd2, &test, 1);
```
一直報錯，核心訊息
```c
char tmp = 't';
kfifo_in(&rx_fifo2, &tmp, sizeof(tmp));
pr_info("kxo:!!!!!!!!!!!!!!%c\n",tmp);
wake_up_interruptible(&rx_wait2);
```
輸出：
```
kxo:!!!!!!!!!!!!!! 1
```
然後發現好像是沒有分配空間給`rx_fifo2`：
```c
if (kfifo_alloc(&rx_fifo2, PAGE_SIZE, GFP_KERNEL) < 0)
return -ENOMEM;
```
還真的是這種白痴問題，成功輸出：
```c
| | |
-------
| | |
-------
| | |
-------
|O| |
-------
This is :game2
```
> commit [bda40b6](https://github.com/sysprog21/kxo/commit/bda40b6d62217ba4a8fe73ac58782f39589d65a4)
但是程式碼變得超遲緩。
是我傳第二個界面資料的地方設置錯誤，再改。
## 第二個對局
我增加了另一個 work item :
```c
/*test if game2 worj or not*/
static void test_game2_func(struct work_struct *w)
{
char tmp[5] = "game2";
kfifo_in(&rx_fifo2, tmp, sizeof(tmp));
pr_info("kxo:!!!!!!!!!!!!!!%s\n", tmp);
wake_up_interruptible(&rx_wait2);
}
```
的確是可以傳輸資料了，但是我的 coroutine 好像有問題。
## 最終兩個對局在 user 端輸出：
> commit [1b31144](https://github.com/sysprog21/kxo/commit/1b311448d91fec614df51f06a659ad12868fed9d)
```c
|O| |
-------
|X|O|
-------
| |X|
-------
| | |X
-------
O| | |
-------
| |X|
-------
|O|X|
-------
| | |
-------
```
本來是想說每次對局輸出結果都會一樣，所以我要改換 AI 下棋順序來讓結果不同，結果不知道為什輸出的棋步會不同，直接達成不同棋局並行。
而且勝利條件也是各自印各自的。
說真的，我覺得我超強。
但好像還存在一些問題，而且程式碼可讀性有點差，寫得時候有點沒耐心了，細節處理的不是很好，要再改進。
:::danger
改進書寫和修正格式。
:::
## timer 設置問題
發現我的勝利判斷有錯誤：
```c
O|O|O|
-------
| | |
-------
|X|X|
-------
| | |
-------
X win!!!
```
測試後發現可能是勝利條件的判斷太慢了，導致都已經換 X 執行了，它才發現有人勝利，所以顯示 X 勝利？
呼應到之前的問題，也遇過一次 timer 出錯的情況。
所以在二個 work item 並行的時候，它會出現一些問題，可能是因為我把 `delay` 設置成 10 倍？
不是上述問題，應該是條件判斷式有誤：
```c
if (win == ' ' && win2 == ' ') {
...
} else if (win2 == ' ') {
...
} else {
...
}
```
這是先偵測是否沒人贏，再偵測是否對局一贏，但是如果兩把對局同時贏，那它就會跳過對 對局1的檢測。
但好像也不是這個問題，最後用比較爛的方法解決，再想為啥會這樣。
> commit [d68e5b9](https://github.com/sysprog21/kxo/commit/d68e5b975543b98e8afd4de568cec78f7ec68b31)
我想到 bug 大概是什問題了，是因為我的棋局2邏輯和棋局1不同。
## 棋局輸出問題
我發現因為我的寫法問題，第二個棋局的輸出會比第一個還要快，這也是保證畫面看起來能夠並行輸出的原因。
在每次螢幕刷新輸出第一個棋局的時候，核心的第二個棋局總是會傳輸資料，導致第二個棋局永遠會輸出，當我將第二個棋局的邏輯更改後，它就不總是輸出了，會導致螢幕斷斷續續。
這個部份很好解決，讓使用者端在沒有收到新的輸入的時候重複上一輪的輸出就好。
但是最大的問題是，在我設置 `turn2` 來實現兩種棋局的相同羅即時，系統總是會壞掉，目前還在找問題。
而且使用者端讀取的速度完全受限於核心端寫入的速度。
:::danger
查字典：理解「蠻」的意思
:::
花了<s>蠻多</s> 時間找問題，發現用 mutex 保護 ai 就可以保證系統不崩潰，但是上述的問題還是存在。
> 中國南方種族的舊稱。《禮記．王制》：「南方曰蠻，雕題交趾，有不火食者矣。」唐．王勃〈滕王閣序〉：「襟三江而帶五湖，控蠻荊而引甌越。」 by [教育部國語辭典](https://dict.revised.moe.edu.tw/dictView.jsp?ID=1235&la=0&powerMode=0)
結果反而用錯誤的邏輯寫出了結果還行的程式碼，改正邏輯後效果反而變差了，先不提交，再想辦法。
## 核心端重複傳輸
上述的問題本來想透過使用者端的處理來解決，但是有點困難，所以想到一個最簡單直接的方法，讓核心段的對局2重複傳輸勝利訊息就好了。
這顯然不是一個特別好的方法，因為會增加傳輸的成本，但我暫時想不到更好的方法，所以再透過進一步縮減傳輸成本來彌補這個問題。
## 改善 coroutine 邏輯
在讀作業六資料的時候，有新的想法，原本我是在每個 coroutine 的部份判斷有沒有新的資料，進而印出。
排程器具每次僅安排下一個 coroutine 去執行，我認為可以改善一下邏輯，用 select 監聽多個棋局的資料傳輸，有資料才進入該 coroutine 執行，這樣比較有協同式多工<s>的感覺</s>。
:::danger
使用精準的話語。
:::
更正，更符合協同式多工的概念。
Google Drive
Gist
Clipboard
Sign in with Wallet
