Try   HackMD

Linux 核心專題: 改進 ttt 作為核心模組

執行人: brian049
專題解說錄影

review by marvin0102

強化對奕的互動，sysfs 與 ioctl 行為的差異為何，除了使用到 major number ，是否會有其他影響？

Reviewed by otteryc

在 commit 18090cc 的 simrupt.c 第 173 行中，常數 70 是什麼意思？另外，simrupt_work_func_first 以及 simrupt_work_func_second 函式的內容相同，能不能用巨集撰寫，提高可讀性？

mutex_lock(&producer_lock);
-produce_data(val);
+produce_data(70);
mutex_unlock(&producer_lock);

Reviewed by Terry7Wei7

繼續更新未完成的TODO事項

任務簡介

重作第六次作業的 simrupt，整合 ttt 程式碼和彙整其他學員的成果，建構 Linux 核心模組

TODO: 回答第六次作業的自我檢查清單

回答第六次作業的自我檢查清單的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

  • 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
    →     從中也該理解為何不希望在虛擬機器中進行實驗;
$ uname -a
Linux ubuntu22-System-Product-Name 6.5.0-41-generic #41~22.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jun  3 11:32:55 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
  • 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？

    〈Linux 核心模組運作原理〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。

free software 不是「免費軟體」！
務必詳閱 https://hackmd.io/@sysprog/revolution-os-note
「自由」和「免費」的意義截然不同，只是剛好英語可用同一個字表達。

在 linux 6.8.12 版本當中，MODULE_LICENSE() 在 /linux/module.h 當中有進行定義，從巨集上述的註解可得知 LICENSE 可以分成免費軟體 自由軟體模組以及非自由，自由軟體模組 LICENSE 為下列幾種: "GPL", "GPL v2", "GPL and additional rights", "Dual BSD/GPL", "Dual MIT/GPL", "Dual MPL/GPL"，非自由的是 "Proprietary"，自由以及非自由的區別在於，如果使用的是 "Proprietary"，則會避免非自由模組使用 EXPORT_SYMBOL_GPL 導出的 symbol。

在註解最下方有給出這麼規定的理由是:

  1. So modinfo can show license info for users wanting to vet their setup is free.
  2. So the community can ignore bug reports including proprietary modules.

Linux 核心模組運作原理 文中有 hello.ko 的範例，在 insmod 的時候使用 strace 追蹤並觀察 insmod 。最需要注意的是 finit_module:

$ sudo strace insmod hello.ko
...
getcwd("/home/ubuntu22/Desktop/linux_ws/test", 4096) = 37
newfstatat(AT_FDCWD, "/home/ubuntu22/Desktop/linux_ws/test/hello.ko", {st_mode=S_IFREG|0664, st_size=112416, ...}, 0) = 0
openat(AT_FDCWD, "/home/ubuntu22/Desktop/linux_ws/test/hello.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6)               = 6
lseek(3, 0, SEEK_SET)                   = 0
newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=112416, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 112416, PROT_READ, MAP_PRIVATE, 3, 0) = 0x765804b3d000
finit_module(3, "", 0)                  = 0
munmap(0x765804b3d000, 112416)          = 0
close(3)                                = 0
...

可以在 kernel/module/main.c 當中找到關於 finit_module() 的宣告，其中 finit_module 會呼叫 idempotent_init_module，idempotent_init_module 會透過 load_module 來為模組配置記憶體並載入模組。

在 simrupt.c 當中主要有兩種使用 mutex lock 的方式: mutex_lock, mutex_lock_interruptible。前者被使用於 simrupt_work_func 函式當中，而後者被使用於 simrupt_read 函式當中。

mutex_lock_interruptible() 與 mutex_lock() 有著些微的差異，針對前者函式的詳細解釋可以在 kernel/locking/mutex.c 中找到。當使用 mutex_lock_interruptible() 函式時，如果該行程是處於睡眠狀態，它會回傳 EINTR，並且不會獲取 lock。但若成功取得 lock，則與 mutex_lock() 一樣回傳 0。

  • 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;

  • 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？

    搭配閱讀《Demystifying the Linux CPU Scheduler》

Linux 核心當中，會透過 workqueue API 處理非同步 process，其中 work item 代表要執行的函式並透過 workqueue 利用執行緒來處理，在這當中 thread 被稱呼為 worker。

Workqueue 當中分成 multi-thread wq 以及 single-thread wq，MTWQ 的 worker 是每一個 CPU 都有一個 worker，至於 STMQ 則是整個系統只有一個 worker。由於 MTWQ 需要維持與 CPU 數量相同的 workers，此舉會導致系統在啟動時會佔據大量資源。且因為 MT 當中每個 CPU 只能提供一個 execution context，而 ST 當中只有一個 execition context，此狀況導致 work items 的大量競爭。

在 /core-api/workqueue.rst 文中指出 CMWQ 的優勢在於:

  • 保持與原始工作隊列 wq API 的相容性。

  • 每個 CPU 的 worker pool 統一，並且所有 wq 共享，提供相同並行程度，避免資源浪費。

  • 自動規範 worker pool 和並行程度，使用戶不需要關注這些細節。

  • 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？

    → 搭配閱讀: 不亂的「亂數」

  • 解釋 ksort 如何運用 CMWQ 達到並行的排序;

TODO: 整合第三次作業提及的人工智慧程式碼到 simrupt

整合第三次作業提及的人工智慧程式碼，主體應在 Linux 核心內運作，讓二個不同的井字遊戲人工智慧演算法執行在「不同的 CPU」(善用 CMWQ) 並模擬二者的對弈，並允許使用者層級的程式藉由開啟 /dev/simrupt (可適度更名) 來設定二個人工智慧程式的對弈並存取彼此的棋步。
務必在 Linux 核心模組中使用定點數。
其一演算法必是 MCTS，另一者可參照第三次作業或 jserv/ttt 專案近期整合的 ELO rating system。

→ 適度彙整其他學員的成果並予以驗證。

設計兩位玩家

commit 18090cc

透過更改 simrupt.c，新增一個 work function 並進行 declare。

$ sudo insmod simrupt.ko
$ sudo cat /dev/simrupt
FSFS...

畫棋盤

commit 5332bdc

對於 void draw_board() 函式的更改，vax-r, marvin0102 發現如果透過原始 simrupt 程式碼運作方式會需要一次次地將資料傳遞至 kfifo buffer。其中， vax-r 在 draw_board() 當中使用 WRITE_ONCE 巨集寫入 pos 變數來避免 race condition，解決多核心 CPU 之間資料一致性的問題。

注意用語：

  • (OS) kernel 是「核心」
  • (processor) core 是「核」

工程人員說話務必精準且有效。

static int draw_board(int pos)
{
    WRITE_ONCE(pos, pos % N_GRIDS);
    WRITE_ONCE(pos, 2 + (pos >> 2) * 16 + ((pos & 3) << 1));
    
    ...
        
    WRITE_ONCE(draw_buffer[pos], 'O');
    
    return 0;
}

上述實作的成本仍過高，棋盤的狀態可事先編碼為特定的數值 (善用數學分析)，然後 Linux 核心模組只要傳遞一個數值給應用程式，後者就能在解讀後，用合適的手段 (包含藉由 SDL2 來繪製棋盤) 展現，這樣效率高又有彈性。

加入 MCTS

在 Linux 核心模組中使用定點數

在 mcts.h 當中有計算到 sqrt(2)，在這之中定點數的運算改寫方式參考 sqrt 的計算。

TODO: 強化對奕的互動

查閱 CMWQ 的文件，指定前述不同的人工智慧演算法固定在不同的 CPU (如 CPU #0 和 CPU #1)，應該要能從使用者層級指定對弈的起始、暫停、恢復，和瀏覽狀態，Linux 核心模組和使用者層級的程式藉由 /dev/simrupt (可適度更名) 裝置檔案互動，注意需要擴充 VFS 註冊的檔案操作。
模擬對弈過程，前述二個人工智慧演算法程式碼在執行時間，應適度停頓 (數百個 millisecond)。
使用者層級的程式應能清楚繪製出 Linux 核心模組的對弈過程，在終端機展現 (你也可改用 SDL 一類的圖形函式庫繪製)

使用者層級指定對弈的起始、暫停、恢復

HenryChaing 以及 vax-r 有針對此項目實作，前者使用 ioctl write 的機制並且加上鍵盤處理機制，並讓終端機的 stdin 轉為 raw mode，再搭配上一個 process_lock。此機制會判斷鍵盤輸入是否是 0x10 也就是ctrl + p，來判斷是否需要暫停。所以當核心模組接收到暫停訊號時，work 會因為獲取不到 process_lock 而無法繼續執行，從而得到暫停機制。

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);

後者針對暫停機制採用 sysfs 機制，筆者 有提起不使用 ioctl 機制是因為需要事先得知裝置的 major number，但是筆者想讓系統動態配置裝置的 major number。想透過寫入代表核心模組當中變數的檔案和核心模組進行溝通，並透過 select() 來同時監聽標準輸入裝置 STDIN_FILENO 以及裝置檔案是否有輸入。

TODO: 評估不同的 PRNG

考慮到 PRNG 的效率，改用 xorshift128+ 或其他執行成本更低的演算法，並評估對於 MCTS 的影響。

TODO: 針對 Linux 核心模組提出改進方案

量化程式表現、輔以數學分析

Last changed by 
 
sysprog
System Software Programming
0
402
Published on HackMD