# 2025q1 Homework 3 (kxo)

contributed by <`alanhc`>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
{%hackmd TDGjUnHqRlSwffjXulBnrw %}

{%hackmd q17g9ZZBTCO8aM-spFz-sg %}

## 整理核心觀念

1. User/Kernel 空間分離與通訊成本
減少 syscall 頻率、減少 context switch 數量。
善用 bitops 傳遞精簡資料格式，了解共享資源與對映的記憶體結構（如 mmap）。
2. 並行程式設計中的 Coroutine 實作
**不依賴 pthread！** 實作協程（可能是 stackless 或基於狀態機）。
練習如何透過 coroutine 在同一 thread 中模擬併發邏輯（AI1、AI2、鍵盤處理）。
3. AI 對弈模組化與負載分析
不同演算法帶來的 CPU load 差異，需自行統計（使用類似 load average 的定點數演算法）。
測量方式需能體現 AI 策略之間的效率與效能差異。
4. 畫面處理與低階鍵盤事件
不可使用 ncurses，需學習如何直接操作終端（ex: termios + 非同步 IO）。
實作 raw mode、讀取 Ctrl-P/Ctrl-Q，並在畫面顯示時間與棋盤更新狀態。
5. 程式設計工程與重用
學會如何 fork 現有專案並基於現有 struct 和 logic 進行擴充與模組化。
面對實作限制（不允許 thread、ncurses）仍能構建可維護與運作的系統。

## 需要實作的元件與建議拆分

1. ttt 主程式（User Space）
使用 mmap() 或簡化的 ioctl() 傳遞 AI 對弈命令。
使用 coroutine 實作：
AI1_coroutine()
AI2_coroutine()
keyboard_coroutine()
畫面更新程式（raw mode + 自繪棋盤）
2. kxo 核心模組
僅保留 minimal API，用於共享棋盤狀態、AI 統計資料。
改為只處理 bit-level 棋盤狀態，並允許 ttt mmap 該區域。
3. Coroutine 架構參考（教材方式）
使用 setjmp/longjmp 或狀態機實作 coroutine 切換
參考 MIT xv6 或「並行程式設計：排程器原理」書中 coroutine 範例（你可能用 co_yield()、co_resume() 的概念）
4. 螢幕畫面處理
使用 termios 設定 raw mode。
用 select() 或非同步輸入處理 Ctrl-P/Q
每場對弈持續更新時間（time(NULL) + strftime()）

## 負載分析與量化

<s>

## 總結
</s>
https://deepwiki.com/sysprog21/kxo

:::danger
不要輕易將自己的專業建構在無法保證自身專業的大語言模型上面。
:::
> 收到
## 測量
https://hackmd.io/@JeffBla/linux2025-homework3
- 在 10 秒內觀察程式 ./xo-user 的系統呼叫（syscalls）行為，並統計其使用情況，將結果輸出到 trace.log
sudo timeout 10 strace -c -o trace.log ./xo-user
- strace: 追蹤程式執行過程中的系統呼叫和訊號
- `-c` 統計模式（summary），會顯示各種系統呼叫的次數、耗時百分比等，而不是每一筆詳細呼叫

alanhc@alanhc-NUC7i7DNHE:~/workspace/kxo$ cat trace.log 
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 35.81    0.000583          11        49           write
 35.57    0.000579          11        52           read
 20.39    0.000332           6        50           pselect6
  1.60    0.000026           3         8           mmap
  1.29    0.000021           7         3           mprotect
  1.23    0.000020           5         4           openat
  0.80    0.000013          13         1           munmap
  0.80    0.000013           3         4           ioctl
  0.49    0.000008           2         3           close
  0.37    0.000006           1         4           fstat
  0.37    0.000006           2         3           brk
  0.31    0.000005           2         2           fcntl
  0.25    0.000004           4         1           prlimit64
  0.18    0.000003           3         1           set_tid_address
  0.18    0.000003           3         1           getrandom
  0.12    0.000002           2         1           arch_prctl
  0.12    0.000002           2         1           set_robust_list
  0.12    0.000002           2         1           rseq
  0.00    0.000000           0         2           pread64
  0.00    0.000000           0         1         1 access
  0.00    0.000000           0         1           execve
------ ----------- ----------- --------- --------- ----------------
100.00    0.001628           8       193         1 total

- strace
- use case
- 🔍 效能瓶頸分析：找出哪個 syscall 耗時最多
- 🧨 偵錯死鎖或系統卡頓問題
- 📊 觀察 coroutine / 多執行緒行為（你提過 xo-user 是 coroutine-based 的 AI）
- ⏱️ 短時間壓力測試（限制時間，避免不小心跑太久）
- perf 使用時機
- 找出
- 🚨 效能瓶頸函式（hotspots）
- 🔁 無效 CPU 使用（例如高 cycles / 低 instructions）
- 🧠 記憶體密集行為，如高 cache misses
- 💥 推估 coroutine 切換是否導致快取效能下降

- 用 perf 工具在 10 秒內記錄 ./xo-user 的硬體事件（如 CPU cycles、指令數、快取未命中、記憶體寫入），可用於低階效能分析。

- perf record
- `sudo timeout 10 perf record -e \
cycles,instructions,cache-misses,mem-stores ./xo-user
`
- perf record: 使用 perf 工具來收集效能樣本
- -e cycles,instructions,cache-misses,mem-stores
stores 指定要收集的硬體事件：
- cycles：CPU 執行週期數
- instructions：已執行的指令數
- cache-misses：快取未命中次數（memory latency 高的關鍵）
- mem-stores：記憶體寫入操作數（store instructions）


- 看即時統計
perf stat ./xo-user
- 有可能需要 `sudo sh -c 'echo 1 > /proc/sys/kernel/perf_event_paranoid'`

- perf 另外可以參考 https://hackmd.io/@Henry0922/linux2025-homework3

## Notes

- https://github.com/alanhc/kxo
- [requirements](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-f)

- task
+ 畫面呈現在使用者層級
+ 用 bitops
+ 允許並行
+ 移植 [ttt](https://github.com/jserv/ttt) 的 RL

- 編譯：make
- 下載：sudo insmod kxo.ko
- 移除：sudo rmmod kxo
- 看log: sudo dmesg
- xo-user：
- 執行
1. install to kernel
2. load companion tool: sudo ./xo-user
- usage
- Ctrl + P：pause/resume board display
- Ctrl + Q：Terminate games running in kernel space
- 參考
- https://hackmd.io/@otischung/linux2025-homework3
- https://hackmd.io/@yy214123/linux2025-homework3#%E8%A8%BB%E8%A7%A3%E4%BF%AE%E6%AD%A3
- https://hackmd.io/@weiso131/linux2025-homework3
- https://hackmd.io/@Wqq3PJvaSQeXVOkcZIX1Eg/rJOCciPTyx
- https://hackmd.io/@leo361288/linux2025-homework3
- https://hackmd.io/@salmonii/linux2025-homework3

- 執行流程
- `make`
- `sudo insmod kxo.ko`
- `sudo ./xo-user`

### 架構

graph TD
    subgraph Userspace
        A[xo-user]
    end

    subgraph Kernelspace
        B[kxo kernel module]
    end

    A -- ioctl / read / write / mmap --> B

- 遊戲邏輯
- game.c 和 game.h 定義了遊戲的核心邏輯，包括檢查勝利條件 (check_win) 和計算分數 (calculate_win_value)。
- AI
- MCTS (mcts.c)：基於隨機模擬的搜索演算法。
Negamax (negamax.c)：基於深度優先搜索的極小化演算法，使用 Zobrist 哈希加速。
- 隨機數生成
- xoroshiro.c 提供高效的隨機數生成器，用於 MCTS 模擬。
- 數據結構
- 使用 kfifo 和 hlist 管理遊戲數據和哈希表。
- 用戶互動
- xo-user.c 提供用戶空間工具，通過 kxo 與核心模組交互，支持遊戲狀態顯示與控制。
關鍵文件
- 核心模組：
main.c：模組入口，負責初始化與清理。
game.c：遊戲邏輯。
mcts.c / negamax.c：AI 算法。
xoroshiro.c：隨機數生成。
zobrist.c：hash table 管理。
- 用戶工具：
xo-user.c：用戶空間交互工具。
- 構建與配置：
Makefile：構建腳本。
.clang-format：代碼風格配置。

### Files
- xo-user: userspace 的 interface
- 主要功能
- 檢查核心模組狀態：status_check
- 鍵盤讀取：listen_keyboard_handler
- main：
- display_buf：用於存儲從設備文件讀取的棋盤數據。
- readset：用於 select() 的文件描述符集合。
- device_fd：打開 /dev/kxo 設備文件，獲取文件描述符。
- max_fd：計算 select() 所需的最大文件描述符。
- read_attr 和 end_attr：控制顯示狀態和程式退出。
- 恢復終端的原始模式：raw_mode_disable
- Standard File Descriptor 恢復為原始狀態：fcntl
- 關閉：close
- 關閉了與 /dev/kxo 的 Standard File Descriptor

:::danger
注意用語！
:::

- main
- 文件相關
- kxo_read：從內核的 kfifo 緩衝區中讀取資料，並傳遞給用戶空間。
- kxo_open：當用戶空間打開設備檔案時執行，啟動定時器。
- kxo_release：當用戶空間關閉設備檔案時執行，停止定時器並清理資源。
- 核心遊戲邏輯
- draw_board：將遊戲棋盤的狀態繪製到 draw_buffer 中。
- ai_one_work_func：執行 AI 玩家 1 的行為，使用 mcts 演算法計算下一步。
- 中斷與工作隊列
- game_tasklet_func：處理遊戲的主要邏輯，根據當前回合調度 AI 或繪製棋盤。
- drawboard_work_func：將棋盤狀態存入 kfifo，供用戶空間讀取。
- 初始化與清理函式
- kxo_init：初始化模組，分配資源，註冊字元設備。
- kxo_exit：卸載模組，釋放所有資源。
- 其他
- produce_board：將棋盤資料存入 kfifo 緩衝區。
- fast_buf_clear：清空快速環形緩衝區。

### 畫面呈現在使用者層級
https://hackmd.io/@Guanchun0803/linux2025-homework3#%E6%A3%8B%E7%9B%A4%E5%A3%93%E7%B8%AE%E4%B8%A6%E5%B0%87%E7%95%AB%E9%9D%A2%E9%A1%AF%E7%A4%BA%E5%9C%A8%E4%BD%BF%E7%94%A8%E8%80%85%E9%9A%8E%E5%B1%A4

### User/Kernel 空間分離與通訊成本
- 對應教材
- [Linux 核心設計: 記憶體管理](https://hackmd.io/@sysprog/linux-memory)
- https://chatgpt.com/share/67fe511b-9bf0-8002-beba-8b864741f51b
- 什麼是syscall, context switch?
- system call: 程式與作業系統之間的橋樑。當使用者空間（user space）的應用程式需要使用核心空間（kernel space）提供的資源（像是檔案、網路、記憶體、裝置等），就會透過 syscall。
- context switch: 當作業系統要從一個執行緒（thread）或行程（process）切換到另一個時，就需要進行 context switch（上下文切換）。
- 什麼是共享資源與對映的記憶體結構（如 mmap）。
- why? 共享資源需要妥善同步，否則會發生 race condition、資料毀損等問題。
- 常見tool:
- Mutex（互斥鎖）
- Semaphore（信號量）
- Spinlock（自旋鎖）
- mmap
- 記憶體共享： 兩個行程可以對映同一份記憶體，進行快速通訊（IPC）。
- use case
- 效能優化： 不用反覆 read()/write()，而是直接透過指標存取。
- 記憶體共享： 兩個行程可以對映同一份記憶體，進行快速通訊（IPC）。
- 
- kxo_read
- 加鎖保護共享資源
- 從內部 rx_fifo 取資料
- 把 rx_fifo 資料拷貝給使用者空間的 buf
- read: 成功讀取的 bytes

        do {
            ret = kfifo_to_user(&rx_fifo, buf, count, &read);
            if (unlikely(ret < 0))
                break;
            if (read)
                break;

- 是否有blocking?
- 有：sleep
- rx_fifo沒有資料就sleep：`ret = wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo));`
- 無：傳送資料到使用者空間
- 釋放鎖並回傳實際讀取的 bytes 數
- kfifo_to_user
- Linux kernel 提供的 API，用來從 kfifo（kernel FIFO 緩衝區） 拷貝資料到使用者空間。
- `int kfifo_to_user(struct kfifo *fifo, void __user *to, unsigned int len, unsigned int *copied);`
- wait_event_interruptible
- 是一個 marco ， 會讓當前 process 進入 sleep，直到條件成立（或被 signal 打斷）。
- `wait_event_interruptible(queue, condition);`
- 如何透過mmap降低 read 、 write 成本
- 研究：`strace -tt -e trace=read,write,pselect6 ./your_program`

| **syscall** | **可能源自 user space 呼叫** | **你模組中可能觸發的時機** |
| ----------- | ---------------------- | -------------------- |
| read | read() from /dev/kxo | 使用者讀棋盤、狀態、事件 |
| write | write() to /dev/kxo | 使用者寫入指令、下棋命令 |
| pselect6 | select() or poll() | 等待有資料可讀，避免 busy loop |

| **優化項目** | **對應 syscall** | **解決方法簡述** |
| ---------------- | ------------------------ | --------------------------------------------- |
| 減少 read() 頻率 | read() | 改用 blocking 模式 + 喚醒機制（已有）或改用 mmap() |
| 減少 write() 頻率 | write() | 將指令打包成 bitflags，一次寫入代表多種行為 |
| 減少 pselect6() 次數 | select() / poll() | 改用 signal、eventfd、timerfd、epoll 等更高效通知機制 |
| 降低資料搬移開銷 | read() 與 kfifo_to_user() | 改用 mmap() 將 draw_buffer 映射給使用者 |
| 精簡狀態同步格式 | N/A（自定義格式） | 使用 bitops 傳遞壓縮的狀態格式（例如 1 個 uint32_t 傳 32 個旗標） |

| **組件** | **舊做法（可能）** | **新做法（效能優化）** |
| ------ | ------------------------ | ------------------------------------ |
| 畫面資料 | 每次 read() 複製進使用者空間 | mmap() 映射 draw_buffer（只傳 flags 通知刷新） |
| 狀態事件 | 一個事件一次 read | 使用 bitops 回傳狀態集合 |
| 用戶通知 | select() / pselect6() 輪詢 | 用 eventfd 或 epoll 等通知 |
| 輸入指令 | 每個指令一個 write() | 批次寫入指令結構體，減少 syscall 次數 |

| **問題點** | **優化建議** |
| ------------------------------ | ------------------------------------------ |
| select() 效能漸低 | 改用 epoll() → 適合大規模、多 fd、多事件場合 |
| read_attr/end_attr 是布林值但用字串寫入 | 改用 bitops 傳遞 kernel flags → "00001" → 0x01 |
| /sys/class/kxo/kxo_state 是檔案操作 | 改成 ioctl() 傳遞控制旗標或事件 |
| 螢幕每次清空整個畫面 | 若用 mmap() 可僅更新差異，降低畫面閃爍 |

- 優化實作
1. ✅ 將 /sys/class/kxo/kxo/kxo_state 控制邏輯改為 ioctl(fd, CMD_TOGGLE)
• 讓控制和畫面資料都透過 /dev/kxo 傳遞
• 減少開檔、read/write /sys 帶來的 syscall 開銷
2. ✅ 用 bitops 讓 kernel kxo_state 成為一個 unsigned long flag，減少字串處理成本
3. ✅ 用 eventfd 結合 epoll 取代 select()，達到低延遲高效率通知
4. ✅ 用 mmap() 對映 draw_buffer 給 user space（只傳 flag 通知畫面是否需要更新）

- 如何透過編碼降低成本
- 重點 function ： produce_board
- main.c
- drawboard_work_func > produce_board
- timer_handler > produce_board
- 流程
- user writes to control node (/sys/kxo/display)
- trigger schedule_work()

            drawboard_work_func()
              ├─ draw_board()        <- 畫棋盤到 buffer
              ├─ produce_board()     <- 寫進 kfifo
              └─ wake_up()           <- 喚醒等待讀取的 user

- 思路
- kxo 使用的 board (code裡面變數table) 是 char array，是否可以直接使用編碼的方式降低棋盤有關的成本?
- 遊戲規則
- OX 遊戲只有 X, O，用 1, 0 替代
- 一回合只會改變棋盤上的一個格子
- e.g. 原先 $4*4$ 棋盤 table array，使用 0, 1 做編碼，應該使用 32 bit (4 bytes)，來存棋盤。因為每個格子會有 O、X、及空。每次更新不用更新整個棋盤，傳遞部分只溝通每一回合是動第幾個 格子 ，奇數回合是 0 （Ｏ） ，偶數回合是 1 (Ｘ)。
- 為何要 mutex_lock？
- draw_buffer[] 是共享的，全域變數，可能同時被多個 context 存取

| **操作角色** | **時機** | **行為** |
| --------------------- | --------------------------- | ------------------------------ |
| drawboard_work_func() | 背景 kernel thread（workqueue） | 呼叫 draw_board() 寫入 draw_buffer |
| kxo_read() | user 調用 read() 時 | 從 draw_buffer 拷貝到 rx_fifo |
| 其他生產者 | 可能有其他 thread、timer、event | 也可能同時寫入棋盤 |
- 程式

:::info
TODO: 使用思路 > 編碼
:::

## 並行程式設計中的 Coroutine 實作

## Coroutine-based 使用者層級排程器設計

https://hackmd.io/@DX3906/B105-Dxa1e#xo-userc-a8b4186

好用工具
compiler exlporer
https://godbolt.org/

:::danger
改進書寫！
:::
> 收到

## 縮減使用者和核心層級的通訊成本
https://hackmd.io/@Guanchun0803/linux2025-homework3#%E7%B8%AE%E6%B8%9B%E4%BD%BF%E7%94%A8%E8%80%85%E5%92%8C%E6%A0%B8%E5%BF%83%E5%B1%A4%E7%B4%9A%E7%9A%84%E9%80%9A%E8%A8%8A%E6%88%90%E6%9C%AC
https://hackmd.io/@BigMickey/linux2025-homework3#%E6%94%B9%E5%96%84%E4%BD%BF%E7%94%A8%E8%80%85%E5%92%8C%E6%A0%B8%E5%BF%83%E5%B1%A4%E7%B4%9A%E7%9A%84%E9%80%9A%E8%A8%8A%E7%9A%84%E6%95%88%E8%83%BD

## 顯示多場對弈
https://hackmd.io/@Guanchun0803/linux2025-homework3#%E9%A1%AF%E7%A4%BA%E5%A4%9A%E5%A0%B4%E5%B0%8D%E5%BC%88%E7%9A%84%E9%81%8E%E7%A8%8B
https://github.com/leowu0411/kxo/commit/b74af57a55fde04049aee8b6e02c2879de7a741f
## 時間量測模式
https://hackmd.io/@leo361288/linux2025-homework3#%E5%8A%A0%E5%85%A5%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F%E6%A8%A1%E5%BC%8F

<s>
## Links
- https://hackmd.io/@sysprog/linux-kernel-module
- https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf
</s>