HackMD
2024q1 Homework6 (integration)
contributed by < marvin0102 >
留意空白字元，注意細節。
開發環境
自我檢查清單
-
研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
-
檢查目前的 linux 版本：
- 安裝 linux-headers 套件
- 確認 linux-headers 套件已正確安裝於開發環境
掛載核心模組測試流程
- 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？
以 fibdrv.c 為例：
從 include/linux/module.h 可以得到聚集 MODULE_LICENSE 的定義，展開可得：
從註解可以得知， 目前提供的自由軟體模組的 license 有 GPL、BSD、MIT、MPL，而 Proprietary 代表非自由軟體，其中 GPL 根據法規與技術的更新，分為 GPL 、 GPL v2 、 GPL and additional rights ， MODULE_LICENSE 的作用主要為： 1. 在 modinfo 中顯示，讓使用者知道此模組為自由軟體模組 2. 讓開發者社群可以忽略 Proprietary 相關的錯誤訊息 3. 廠商可以根據自己的政策做同樣的事情
為何 Linux 核心模組的掛載跟授權條款有關？
通過 strace 查看執行 insmod fibdrv.ko 時，的過程有哪些系統呼叫被執行:
從訊息中可以得知， insmod 大量的使用了 openat 、 read 、 newfstatat 、 mmap 、 close 等系統呼叫。
其中，系統呼叫 finit_module 被定義於 kernel/module.c 中，通過呼叫 kernel_read_file_from_fd 將 ELF 檔 fibdrv.ko 打開並且呼叫 load_module 。
load_module 同樣被定義於 kernel/module.c 中，從程式碼可以發現，核心先做 layout_and_allocate 為載入的 module 進行記憶體配置。而後在呼叫 do_init_module 對 module 做初始化。最後在函式 do_one_initcall 中，呼叫 init_function 為核心模組進行真正的初始化的工作。
在核心初始化的過程中， load_module 呼叫了函式 simplify_symbols:
simplify_symbols 被定義於 kernel/module.c 中:
從註解可以得知， simplify_symbols 從模組的 ELF 中取出需要尋找的 external symbols ， 隨後在函式 resolve_symbol_wait 中呼叫 resolve_symbol 。 resolve_symbol 通過呼叫 find_symbol 尋找哪些符號屬於該模組，而後使用 add_module_usage 將符號加入模組。
其中， find_symbol 搜尋使用到 list_for_each_entry_rcu 走訪 mod 雙向鏈結串列。
使用精準的術語
- 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;
在 simrupt 中，函式 simrupt_read 的作用為將 buffer 中的資料輸送到 userspace ， 若 rx_fifo 為空，則呼叫 wait_event_interruptible 將程式加入 wait queue 中。
其中使用到了 mutex_lock_interruptible ， mutex_lock_interruptible 被定義在 kernel/locking/mutex.c 中：
從註解中可以得知， mutex_lock_interruptible 可以在接收到中斷信號後，直接返回 -EINTR ，避免浪費 CPU 資源 ，若成功獲得 lock 則返回 0。
並非如此，詳閱 LKMPG 和 Linux 文件。
在 LKMPG 中提到：
We could have used
wait_eventinstead, but that would have resulted in extremely angry users whose Ctrl+c’s are ignored.
wait_event_interruptible 與 wait_event 的差別在於， wait_event 會忽略 ctl+c signal ，因此需要返回 -EINTR 讓使用者可以中止行程。
因此我們可以知道，返回 -EINTR 的作用是行程在進入 critical section 前，允許使用者中止行程或是接收 interrupt signal。
mutex_lock 與 mutex_lock_interruptible 主要的差別在未能獲得 lock 時所呼叫的函式 __mutex_lock_common 中的參數 state 被設定為 uninterrputible 或是 interruptible ，即是否能被中斷。
另外 wait_event_interruptible 會將 process 加入 wait queue rx_wait 中，並且使 process 進入 sleep 狀態，只有滿足條件 kfifo_len(&rx_fifo) 不為 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 排程器互動？
-
解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？
從 LKMPG 理解 simrupt 原理
simrupt
從 simrupt_init 的初始化可以知道， simrupt 為 character device ，作用為不斷循環生成大小為 0x20 ~ 0x7f 的可視字元，並且輸出至 user space 。
字元生成的流程如下:
在函式 timer_handler 中，呼叫函式 process_data -> update_simrupt_data ，函式 update_simrupt_data 循環輸出範圍 0x20 ~ 0x7f 中的數值，每次呼叫遞增 1 ，隨後在函式 fast_buf_put 將數值存入 Circular buffer fast_buf 中，fast_buf 做為資料輸入 kfifo rx_fifo 的中間緩衝區，最後通過函式 fast_buf_get 將數值提出後，在函式 produce_data 將資料存入 rx_fifo 。
字元輸出的流程如下:
在讀取 character device 時，會呼叫 simrupt_fops.read ，也就是函式 simrupt_read ，在函式 simrupt_read 中，先是會使用 mutex lock 確認沒有其他 process 進入 critical section ，隨後通過 kfifo_to_user 將 rx_fifo 中的字元輸出至 userspace ，當 rx_fifo 為空時，則呼叫 wait_event_interruptible 使 precoss 進入 sleep 狀態。
class
在註冊 character device 時，使用到 device_create 函式，在 LKMPG 中提到:
6.3 Registering A Device:
we can have our driver make the device file using the device_create function after a successful registration and device_destroy during the call to cleanup_module .
device_create 被定義在 drivers/base/core.c，作用是建立一個 device 並且註冊於 sysfs 中。其中 class 的作用為何呢?
從註解中可以知道，引數 class 為 device 所需註冊之類的指標，此 class 經由 class_create 函式建立。struct class *class_create 在 include/linux/device/class.h 中被定義，同樣被定義在此檔案的還有資料結構 class 。
從資料結構 class 的註解中可以知道，class 為低層級實作細節之高層級抽象，做用為讓使用者可以根據 device 的功能進行使用，而非根據 device 的連接或運作方式。
vmalloc
simrupt 中記憶體配置使用的是 vmalloc 而非 LKMPG 中提到的 kmalloc 。
kmalloc 被定義在 include/linux/slab.h ，而 vmalloc 則是定義於 mm/vmalloc.c 中:
比較之後可以發現， kmalloc 負責在 kernal 中配置大小小於 page size 的記憶體，而 vmalloc 則可以透過虛擬記憶體的方式，配置數量滿足 size 大小的 pages，並且映射到連續的核心虛擬空間。
interrupt
在 simrupt 中，使用到 workqueue 、 tesklet 等 interrupt handler。
在 linux-insides 中有介紹到:
Interrupts may have different important characteristics and there are two among them:
- Handler of an interrupt must execute quickly;
- Sometime an interrupt handler must do a large amount of work.
中斷有可能會有兩中不同的特性，有時些中斷需要盡快處理，如:硬體中斷，然而有些中斷需要做的事非常多，因此可能會占用較長的 CPU 時間，需要同時滿足這兩個特性非常困難。
在 LKMPG 中有提到:
15.1 Interrupt Handlers:
Linux kernel solves the problem by splitting interrupt handling into two parts. The first part executes right away and masks the interrupt line. Hardware interrupts must be handled quickly, and that is why we need the second part to handle the heavy work deferred from an interrupt handler.
解決辦法為將中斷分為兩種，需要即時處理的中斷具有較高的權重，被歸類為 top half ，而工作比較繁重，需要佔有較多 CPU 時間的中斷，被歸類為 button half ，此類中斷會被推遲處理，可以稱為 deferred interrupts。
There are three types of deferred interrupts in the Linux kernel:
- softirqs;
- tasklets;
- workqueues;
softirq
目前 linux bottom half handlers 的實作都是基於 ksoftirqd ，每一個行程都一個 ksoftirqd/n 其中 n 為行程編號，可以經由命令 systemd-cgls -k | grep ksoft 查看。
linux-insides 中有提到:
Interrupts and Interrupt Handling. Part 9.:
Softirqs are determined statically at compile-time of the Linux kernel and the open_softirq function takes care of softirq initialization.
open_softirq 在 kernel/softirq.c 可以找到其定義:
目前 linux 定義了 10 種類型的 softirq，softirq_vec 則包含其中一種 :
我們可以透過命令 cat /proc/softirqs 查看:
tasklets
linux-insides 中寫到:
tasklets are softirqs that can be allocated and initialized at runtime and unlike softirqs, tasklets that have the same type cannot be run on multiple processors at a time.
我們知道， softirq 只能在 compile-time 時被決定，而 tasklet 則可以在 runtime 時配置及初始化。
從 kernel/softirq.c 中的函式 softirq_init 可以知道， tasklet 可以藉由兩種 softirqs 建立:
- TASKLET_SOFTIRQ
- HI_SOFTIRQ
kernel/softirq.c 中，資料結構 tasklet_head 負責描述 tasklet 串列:
串列中的tasklet，經由資料結構 task_struct 表達:
可以看到，此資料結構內容包含:
- 指向下個 tasklet 的指標
- tasklet 的狀態
- tasklet 是否為 active
- tasklet 的 callback function
- callback function 所需之參數
可以同過聚集 DECLARE_TASKLET(name, func, data) 、 DECLARE_TASKLET_DISABLED(name, func, data) 或是函式 tasklet_init 進行初始化。
而我們可以通過下列這三個函式標示該 tasklet 準備執行:
三者的實作方法相似，差別在於優先權的高低而已。
Workqueues
同樣以 linux-insides 理解 workqueue :
Workqueue functions run in the context of a kernel process, but tasklet functions run in the software interrupt context. This means that workqueue functions must not be atomic as tasklet functions.
workqueue 與 tasklet 主要的差別在於，workqueue 函式不能為 atomic 。
workqueue 中的 work 使用 work_struct 表現，定義於 include/linux/workqueue_types.h :
其中 func 為被排程於 workqueue 中的函式， data 為 func 所需要的參數。
linux 核心使用 kworker 執行續用於排程 workqueue，作用相當於 ksoftirqd 之於 softirqs， 我們可以透過命令 systemd-cgls -k | grep kworker 查看:
linux 核心使用巨集 DECLARE_WORK 建立 work :
接著使用函式 queue_work 將 work 加入 workqueue 中:
timer
simrupt 使用 timer_list 模擬 IRQ，根據 Linux Device Drivers, 3rd Edition 的敘述:
A kernel timer is a data structure that instructs the kernel to execute a user-defined function with a user-defined argument at a user-defined time.
在 include/linux/timer_types.h 中可以找到資料結構 timer_list 的定義:
其中，expire 為設定的時間，function 為超過時間時所執行的 call back function 。
巨集 timer_setup 用於初始化 timer_list ， timer_list 在使用前必須先使用巨集 DEFINE_TIMER() 或是 timer_setup() 初始化。
函式 mod_timer 用於更新 timer_list 的觸發時間，作用相當於
del_timer(timer); timer->expires = expires; add_timer(timer)
函式 del_timer_sync 用於刪除 timer_list ，與 del_timer 的差別在於，當 del_timer_sync 返回時，保證 timer_list 不會在任何 CPU 上執行。
jiffies
在 wikipedia 可以看見敘述:
Jiffy is an informal term for any unspecified short period of time
同樣 linux 核心也有相似的定義，在 linux-insides 中提到:
There is global variable with the jiffies which holds the number of ticks that have occurred since the system booted.
在形成初始化的時候，全域變數 jiffies 會被設為 0 ，並且在 timer interrupt 觸發時遞增。
作業主題二
繪製棋盤
在一開始繪製棋盤的時候，是使用 cir_buff 將棋盤一個字元一個字元送至 rx_fifo 中。但考慮到棋盤所需的資料很少，因此改為直接將棋盤輸入至 rx_fifo 中，再交由 rx_fifo 將棋盤送至 userspace。
使用函式 update_simrupt_data() 模擬下棋，將棋盤 table[N_GRIDS] 中的格子陸續下滿。
AI 對弈
做為測試，先只將 MCTS 移入，並且作為兩個 ai 的下棋演算法。在測試時，嘗試使用函式 get_random_bytes() 作亂數生成，但此函式不能再 wait 狀態，因此會導致程式出現錯誤。
因此維持 PRNG 作為亂數產生器。
首先，先測試 MCTS 在 linux module 中是否能正常對弈，因此將兩個 ai 寫在同一個 while 迴圈中，透過 turn = turn == 'O'? 'X' : 'O'; 交換對弈。
從結果可以看出，ai 可以正常對弈，但由於對弈演算法的執行速度較慢，無法在一個 interrupt 之內跑完，因此會出現棋盤的顯示比下棋速度快的情況。
接這是將 ai 的對弈從 while 迴圈轉換成函式加入 workqueue 中進行對弈，一開始單純將 while 迴圈中的任務摘分出來，寫成函式。
為了避免出現 race condition ，因此加入 mutex lock ，但因為 workqueue 中的 work 為並行，容易出現 dead lock ，因此先改為 WRITE_ONCE 做測試。
在成功使兩個 ai 對弈後，發現 cpu 的使用比起將兩個 ai 寫在同一個 while 迴圈的版本還要多上不少，從 dmesg 發現，因為使用 timer_handler 將 ai 對弈的程式不斷加入 workqueue 中，但演算法的運算過於緩慢，無法一個interrupt 內完成，導致 workqueue 中的 work 不斷堆積。
解決方法為，將 Player_I_task 、 Player_II_task 中加入 while 迴圈，使兩程式不斷相互執行對弈，而 timer_handler 的功能從將程式加入 workqueue 中改為檢查對弈是否結束。
使用者介面
使用 ioctl 作為 kernel module 的交互工具，在 LKMPG 中的範例程式要求在使用 ioctl 時，需要固定 character device 的 major number ，原因是當我們在使用 ioctl 時，會需要定義 ioctl numbers 來區分讀取、寫入等不同的命令，但 __IOW 、 __IOR 等等定義 ioctl numbers 的巨集需要三個引數，其中引數 type 的作用是用於區分不同 device 的 ioctl 命令，因此不能與其他 device 重疊，這也是為甚麼使用 major number 作為引數 type 的原因。
__IOW 、 __IOR 等等定義 ioctl numbers 的巨集 include/uapi/asm-generic/ioctl.h:
從引數 type 的作用可以只到，我們只需要設定一個不與其他 device 重疊的數值就可以了，這樣不但可以使 device 可以動態配置 major number ，也不會造成不同 device 的 ioctl 命令重疊的問題。
使用者層級的程式主要做的事情為，接收兩種命令 '^Q' 、 '^P' ，其中命令 '^Q' 的作用是終止遊戲，而命令 '^p' 的作用是暫停棋局的輸出，但對弈仍會繼續。
使用 RawMode 來改變程式在接收 stdin 的輸入時的設定:
其中 raw.c_iflag &= ~(IXON) 、 raw.c_lflag &= ~(ECHO | ICANON) 的作用為禁用特殊字元 '^Q' '^P' 的功能以及不再印出輸入的字元， raw.c_cc[VMIN] = 0 raw.c_cc[VTIME] = 1 的作用是使程式不再等待來自 stdin 的輸入進而使程式無法繼續運行。
使用者層級的程式透過 while 迴圈中的 iotcl 命令接收來自 device 訊息，也就是對弈的過程，並將其印出，在接收到命令 '^Q' 後，跳出迴圈並且關閉 device 。
命令 '^p' 的作用是暫停棋局的輸出，但如果使 device 停止輸出， iotcl 會因為需要等待來自 device 對弈過程而使程式無法順利執行。因此，在使用者層級的程式接收到命令 '^p' 時，將其傳入 device 中，而 device 在接收到此命令後，將停止把新的棋局寫入紀錄棋盤的 board_buff 中，使得 device 輸出的仍會是舊的棋盤。
成果影片
