Try   HackMD

2025q1 Homework 3 (kxo)

contributed by <alanhc>

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

加油！

  • 由於寫到後面幾週心態有點崩，這些東西怎麼之前都不知道，有幾句話想做精神喊話：
  • 你不必非常出色，只要在很長的時間內，保持比其他人聰明一點點就夠了 - 查理蒙格
  • 誠實的面對自己 - Jserv
  • 青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。
  • 學習方法 - 小林說 學習 YT
    • 找到複雜東西的結構 > 結構化的理解
    • 流程的思維模式

linux kernel 學習筆記

Kernel

  • 看核心版本
uname -r
6.11.0-21-generic

sudo apt install linux-headers-`uname -r`
  • 確認套件安裝
dpkg -L linux-headers-`uname -r` | grep "/lib/modules/.*/build"

make -C /lib/modules/`uname -r`/build M=`pwd` modules

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

  • 下載到kernel
    sudo insmod hello.ko
  • 看核心訊息緩衝區（kernel ring buffer）
dmseg
[781851.187559] Hello, world
  • 設定
    sudo nano /etc/default/grub
    GRUB_CMDLINE_LINUX_DEFAULT="quiet splash intel_pstate=disable"
for cpu in /sys/devices/system/cpu/cpu[0-9]*; do
    echo performance | sudo tee $cpu/cpufreq/scaling_governor
    max=$(cat $cpu/cpufreq/cpuinfo_max_freq)
    sudo tee $cpu/cpufreq/scaling_min_freq <<< $max > /dev/null
    sudo tee $cpu/cpufreq/scaling_max_freq <<< $max > /dev/null
done

cat /proc/cpuinfo | grep 'MHz'
sudo sh -c 'echo 1 > /proc/sys/kernel/perf_event_paranoid'

整理核心觀念

  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()）

負載分析與量化

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

總結

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →


https://deepwiki.com/sysprog21/kxo

不要輕易將自己的專業建構在無法保證自身專業的大語言模型上面。

收到

測量

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）

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Notes

架構

Kernelspace
Userspace
ioctl / read / write / mmap
xo-user
kxo kernel module
  • 遊戲邏輯
    • 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

注意用語！

  • 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#棋盤壓縮並將畫面顯示在使用者階層

User/Kernel 空間分離與通訊成本

  • 對應教材
  • 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）。
      • image
  • 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 也可能同時寫入棋盤
  • 程式
    image

TODO: 使用思路 > 編碼

並行程式設計中的 Coroutine 實作

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

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

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

改進書寫！

收到

縮減使用者和核心層級的通訊成本

https://hackmd.io/@Guanchun0803/linux2025-homework3#縮減使用者和核心層級的通訊成本
https://hackmd.io/@BigMickey/linux2025-homework3#改善使用者和核心層級的通訊的效能

顯示多場對弈

https://hackmd.io/@Guanchun0803/linux2025-homework3#顯示多場對弈的過程
https://github.com/leowu0411/kxo/commit/b74af57a55fde04049aee8b6e02c2879de7a741f

時間量測模式

https://hackmd.io/@leo361288/linux2025-homework3#加入時間測量模式

## 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
Last changed by 
 
alanhc
https://www.linkedin.com/in/alanhc316/
0
166

Read more

2025q1 Homework5 (assessment)

contributed by &lt;alanhc&gt;

Jun 5, 2025
serial over lan

什麼是 SoL？ Serial over LAN 是一種技術，允許使用者透過網路（通常是 Ethernet）來遠端存取主機的序列埠（Serial Port），也就是說SoL是將傳統串列埠資料轉封包，經網路傳送，再還原為串列資料的過程。 爲什麼需要 SoL？ 傳統串列埠（如 RS-232）需直接接線，非常不方便遠端操作。 BMC（Baseboard Management Controller）透過 SoL：在作業系統開機前也能觀察主機輸出（BIOS/UEFI/Post）。 可搭配 IPMI 或 Redfish 管理介面啟用/停止 SoL。 達到「無人值守的伺服器管理」。 Components

Jun 5, 2025
til

index

Jun 5, 2025
Hardware

一種低速的雙線通信協議，用於連接主機（如 BMC）和多個外設（如 EEPROM、溫度感測器等）。有主從架構，主機發起通信，從機回應。在 BMC 的應用：用來監控硬體設備的狀態，例如存取 EEPROM 儲存韌體資訊、讀取溫度感測器數據，或控制 GPIO 擴展器

Jun 4, 2025
Read more from alanhc
Published on HackMD