# 2024q1 Homework6 (integration)

contributed by [`< HenryChaing >`](https://github.com/HenryChaing/simrupt)

## 自我檢查清單

## 作業主題二: 整合井字遊戲對弈

### Linux 核心模組

本次作業內容希望我們撰寫一個會執行井字遊戲的核心模組，並且使用者空間的行程可以接收到核心模組傳來的資訊並圖形化顯示過程及結果。因此我們會先來了解何謂 Linux 核心模組，並且說明如何實現它。

所謂核心模組就是指一段可以動態載入以及卸除的程式碼區塊，因此我們可以在不重新開機以及重新編譯核心的情形下加入我們需要的程式碼片段，而核心模組最常見的應用是作為硬體的驅動程式，這不僅增強核心整合週邊裝置的能力，還省去了改變原本核心程式碼的麻煩。

---
### 裝置驅動程式

這邊會簡略地介紹裝置驅動程式的程式樣貌，以方便理解接下來的 simrupt 專案的程式行為。首先最基礎的 Linux 核心模組會有載入以及卸除時對應的方法，分別為 `<linux/module.h>` 提供的 `module_init` 以及 `module_init` 方法，這兩個方法都各只有一個函式指標參數，在載入以及卸除時分別呼叫該函式，例如範例程式 [`hello-2.c`](https://github.com/sysprog21/lkmpg/blob/master/examples/hello-2.c) 。

接著是裝置驅動程式一定會使用到由 `<linux/fs.h>` 提供的 `file_operations` 結構變數，該結構變數的成員大多是函式指標變數，會用來儲存檔案（裝置）對應的開啟、關閉、讀寫等對應到的函式，因此每當這個檔案（裝置）被不論是核心或是使用者空間行程進行檔案操作時，核心模組就會呼叫對應的函式，用來處理實際或虛擬硬體裝置的操作，參考的範例程式如下，這是個可以讀取虛擬字元硬體裝置產生之字元陣列的核心模組 [`chardev.c`](https://github.com/sysprog21/lkmpg/blob/master/examples/chardev.c)。

---

### simrupt

這個是需要我們改寫成井字遊戲對弈的核心模組專案，不過原始專案是由核心 timer 觸發排程，並且在讀取裝置時會由 work 向進行讀取的行程傳遞介於 `0x20 ~ 0x7e` 之間字元，融合多項核心機制的核心模組。

#### simrupt 流程圖 及 核心機制說明

digraph simrupt {
    node [shape = box]
    rankdir = TD
    timer_handler [label="timer_handler"]
    process_data [label = "process_data"]
    update_simrupt_data [label="update_simrupt_data"]
    fast_circular_buffer [label="fast_circular_buffer", shape=ellipse]
    simrupt_tasklet_func [label = "simrupt_tasklet_func"]
    simrupt_work_func [label = "simrupt_work_func"]
    kfifo [label = "kfifo", shape=ellipse]
    
    timer_handler -> process_data
    process_data -> update_simrupt_data 
    update_simrupt_data -> fast_circular_buffer [label = "  fast_buf_put"]
    process_data -> simrupt_tasklet_func [label = " tasklet_schedule"]
    simrupt_tasklet_func -> simrupt_work_func [label = " queue_work"]
    fast_circular_buffer -> simrupt_work_func [label = "fast_buf_get"]
    simrupt_work_func -> kfifo [label = "  produce_data"]
    {rank=same update_simrupt_data simrupt_tasklet_func}
}

首先是 simrupt 會透過核心的 **timer** 定期發出中斷訊號，而中斷處理常式（ISR） 會運用 **tasklet** 進行中斷處理，並且產生可顯示字元放入 **fast_buf** 當中。

**tasklet** 的方法則是設計成 **workqueue** 的排程， 而 **work** 的工作就是把 **fast_buf** 最早放入的內容取出，並且將其放入 **kfifo** 當中，其中由於 **work** 之間會並行處理，並且可能產生平行處理的狀況，因此需要加上生產者以及消費者的 lock 避免同時對兩項資料結構同時存取。

最後 **kfifo** 則是會將資料回傳給讀取檔案的行程，但是若有多個行程同時讀取，只會有其中一個行程接收到資料。

---

### tic-tac-toe

這是要被改寫為與核心模組搭配的使用者空間程式專案，它是個 4X4 的井字遊戲，並且提供多項人工智慧的演算法讓使用者可以與其對弈，它會將對弈過程在終端機圖形化顯示出來，並且印出雙方玩家的棋路。

## 主題二專案實作

### work 設計
> [commit ef7cd37](https://github.com/HenryChaing/simrupt/commit/ef7cd37a7e0b4a1fb9aba4c71e3b67e8e5c48eb4)

原先 simrupt 專案只有一個 work 會進行排程，但是考量到本次主題為二位玩家的井字遊戲，因此在這次的設計中我安排了兩個 work 進到 workqueue 進行排程，分別是執行 `negamax` , `MCTS` 人工智慧演算法的 work 。每次中斷發生時會交替將這兩個 work 加入佇列當中。在專案的初期階段我讓兩個 work 交錯印出 `C` , `D` 來驗證排程的可能性，並且執行確實符合預期。

$ insmod simrupt.ko
$ cat /dev/simrupt
CDCDCD ...

### 加入 MCTS 人工智慧演算法
> [commit 14f15e1](https://github.com/HenryChaing/simrupt/commit/14f15e15c0efde2557057b6f44b87102e4a6605c)

MCTS 的程式碼反應到了 Linux 核心模組較為重要的問題，就是對浮點數的處理不易。在缺少了 C 標準函式庫的幫助下浮點數運算變成了一項危險的操作。因此我將原先為浮點數的部份轉由定點數代為運算。

MCTS 會在每一回合訓練計算各個節點的分數，最後挑出分數最高者並回饋到整個樹狀模型。而分數的計算就會牽扯到浮點數，但是我發現到了最後是比較各個節點的分數並找出最大者，因此我決定將原先與分數計算有關的過程通通放大 $2^{16}$ 倍，再由無號整數紀錄結果，在每個節點均等比例放大後再進行比較。

### 融入 negamax 演算法
> [commit d1ea508](https://github.com/HenryChaing/simrupt/commit/d1ea5084feb39dfa1949cc8ddba76d4eccce632d)

在撰寫核心模組程式碼會遇到第一個難題，就是不能使用標準 C 函式庫，而是只能使用簡易的 Linux 核心標頭檔函式庫。因此在改寫原本使用者空間的程式碼時遇到不少阻礙，甚至遇到系統通知需要立即重開機的問題，透過虛擬環境的架設後有了有效的解決。

#### virtme-ng

          _      _                                    
   __   _(_)_ __| |_ _ __ ___   ___       _ __   __ _ 
   \ \ / / |  __| __|  _   _ \ / _ \_____|  _ \ / _  |
    \ V /| | |  | |_| | | | | |  __/_____| | | | (_| |
     \_/ |_|_|   \__|_| |_| |_|\___|     |_| |_|\__  |
                                                |___/ 

這是一個以 QEMU 為基礎的 Linux 核心虛擬環境，可以運用類似 kvm 的形式在使用者端建立虛擬環境，可以在上面測試欲載入的核心模組，並且可以透過 telenet 從宿主端連線到虛擬環境紀錄發生的錯誤，再搭配 crash 套件進行除錯，這樣可以避免因為錯誤的核心模組而造成的實際硬體損壞。

### ioctl 設計
> [commit 8353e42](https://github.com/HenryChaing/simrupt/commit/8353e422c73907471ef2cb4d0680bff638862af5)

ioctl (Input Output ConTroL) 是 Linux 核心提供給行程用來與核心或核心模組溝通的機制，當核心模組或是裝置驅動程式需要被井字遊戲讀寫，則 ioctl 將是非常合適的核心機制。

在我對裝置驅動程式 ioctl 設計中，當井字遊戲向核心模組讀取 negamax 人工智慧演算法的判斷結果時， ioctl 會呼叫 `simrupt_read` 函式，而 `simrupt_read` 會將 kfifo 儲存的判斷結果取出，並且將其放入參數所指定的記憶體空間，最後在由 ioctl 透過 `put_user` 函式將結果回傳給呼叫 ioctl 方法的行程。

### 並行程式間的同步
> [commit 5eb181a](https://github.com/HenryChaing/simrupt/commit/5eb181a368857215d8a66a3dd5406f50e14de3ae)

有別於 simrupt 一個 work 印出一個字元就結束任務，我讓一個 work 擔當井字遊戲的玩家（而非只下一步棋就結束任務）。因此理想情況即是兩個 work 交替決定落棋點並完成一場對局，但是實際情形是一個 work 可能連下兩步棋而導致結果不如預期。

因此我採用 mutex lock 來解決這次的同步問題，原理如下： 核心模組當中共有 A 、 B 兩項 work ，我們預期讓 A 先下棋，並透過 lock_A 、 lock_B 兩個 mutex lock 來做同步信號，在對方的工作結束時才會解鎖自己行程的 lock ，這樣就不會有搶先對方工作先執行的問題，以下為同步實作虛擬碼:

work A {                       work B {

while(!checkwin()){            while(!checkwin()){
    
    mutex_lock(lock_A);             mutex_lock(lock_B);
    
    /*negamax decision*/            /*MCTS decision*/
    
    mutex_unlock(lock_B);           mutex_unlock(lock_A);
}                              }

}                              }

initial step : mutex_lock(lock_B);

### 暫停以及恢復機制
> [commit 61c55bf](https://github.com/HenryChaing/simrupt/commit/61c55bf9e340bc706c0a8342f3349ff44e2a479c)
>
我加入了 ioctl write 機制在核心模組以及井字遊戲當中，並且加入了 [作業三](https://hackmd.io/Ywll9SJPTFuYtIc-qGp36g?view#%E4%BA%95%E5%AD%97%E9%81%8A%E6%88%B2) 的鍵盤處理機制，包含啟動 RAW mode 再偵測 `ctrl+P` 也就是 `0x10` 的字元輸入，當鍵盤輸入為 `0x10` 則 ioctl 會以 `IOCTL_SET_MSG` 模式發送資料到核心模組，當核心模組接收到資料，就會使用 `process_lock` 這個 mutex lock ，讓兩個 work 的進展中止，要一直等到核心模組再次收到資料才會恢復執行。

井字遊戲在偵測到 `ctrl+P` 後，會紀錄第一次中止時的 `turn` 變數，並在再次偵測到 `ctrl+P` 後給 `turn` 變數恢復成紀錄的數值，以防止與核心模組的紀錄出現落差。核心模組的互斥鎖設計如下，可以停止兩項 work 的進展。

work A {                       work B {

while(!checkwin()){            while(!checkwin()){
    
    mutex_lock(lock_A);             mutex_lock(lock_B);
    mutex_lock(pro_lock);           mutex_lock(pro_lock);
    
    /*negamax decision*/            /*MCTS decision*/
    
    mutex_unlock(pro_lock);         mutex_unlock(pro_lock);
    mutex_unlock(lock_B);           mutex_unlock(lock_A);
}                              }

}                              }

simrupt_write event : mutex_lock(pro_lock);

### 結果展示

我在主機端為 ubuntu 的電腦上進行展示，首先會對編譯完成的核心模組進行載入，並更改權限為使用者可讀，最後執行井字遊戲，每次過程會同步顯示現在的棋譜以及接收到的訊息，在核心日誌訊息中也會同步紀錄過程，可以透過 ```$ dmesg --follow``` 觀察。

核心日誌紀錄示意：

[   38.173307] simrupt: [negamax] 10, O
...
[   44.375313] simrupt: [negamax] 2, X
...
[   46.417942] simrupt: [negamax] 9, O
...
[   52.542799] O won!

結果展示影片：

{%youtube mxS9M9mDrng %}

## 參考資料

- [ ] [The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/#talking-to-device-files)
- [ ] [Linux 核心的並行處理](https://hackmd.io/@sysprog/linux2024-integration/%2F%40sysprog%2Flinux2024-integration-c)
- [ ] [測試 Linux 核心的虛擬化環境](https://hackmd.io/@sysprog/linux-virtme)