---
# System prepended metadata

title: 2025q1 Homework3 (kxo)

---

# 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 重新製圖
:::

![image](https://hackmd.io/_uploads/S1dQs2Blel.png)


大致框架：
```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
使用精準的話語。
:::
更正，更符合協同式多工的概念。
