# 2024q1 Homework6 (integration)
contributed by < `vestata` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 24
On-line CPU(s) list: 0-23
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i7-13700
CPU family: 6
Model: 183
Thread(s) per core: 2
Core(s) per socket: 16
Socket(s): 1
Stepping: 1
CPU max MHz: 5200.0000
CPU min MHz: 800.0000
BogoMIPS: 4224.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 640 KiB (16 instances)
L1i: 768 KiB (16 instances)
L2: 24 MiB (10 instances)
L3: 30 MiB (1 instance)
```
## 自我檢查清單
- [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？
> 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。
- [x] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);
> 參照 [2021 年的筆記](https://hackmd.io/@linD026/simrupt-vwifi)。歡迎貢獻 LKMPG!
> $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
> 對照 [fluxsort](https://github.com/scandum/fluxsort) 和 [crumsort](https://github.com/scandum/crumsort) 的分析和效能評比方式
- [x] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
> 搭配閱讀《Demystifying the Linux CPU Scheduler》
- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)
- [x] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
## 開發紀錄
### 處理並行排序的 Linux 核心模組
#### 前期準備
由於我使用 Ubuntu 22.04 去要新增設定已掛載進 linux 核心，進入 BIOS 發現 Secure Boot 的功能已關閉。
安裝 `linux-headers` 套件
>自從 Linux 核心 4.4 版以來，Ubuntu Linux 預設開啟 EFI_SECURE_BOOT_SIG_ENFORCE，這使得核心模組需要適度的簽章才可掛載進入 Linux 核心，為了後續測試的便利，我們需要將 UEFI Secure Boot 的功能關閉
我的核心版本為 `6.5.0-28-generic`
```shell
$ sudo apt install linux-headers-`uname -r`
```
下載版本為
```shell
/lib/modules
/lib/modules/6.5.0-28-generic
/lib/modules/6.5.0-28-generic/build
```
將 ksort 專案放到本地，編譯並測試 `make check`，但是**沒有**如預期看到 2 次綠色的 `Passed [-]` 字樣
遇到問題：
```shell
warning: the compiler differs from the one used to build the kernel
The kernel was built by: x86_64-linux-gnu-gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
You are using: gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
```
推測要更新 gcc，但是我更新 gcc 後使用 `gcc --verison` 查看到版本為 12.3.0 與 kernel 相同，但是依舊出現相同警告。
```shell
warning: the compiler differs from the one used to build the kernel
```
尚未出現如說明所說的
>預期會看到 2 次綠色的 Passed [-] 字樣
:::danger
執行 `make check`
:::
但是目前先繼續進行。
`modinfo sort.ko` 核心模組與與其輸出相同。我們可以使用 `sort.ko` 核心模組使用 `insmod` 掛進 linux 核心之中。掛載完成會出現 `/dev/sort`
`cat /sys/class/sort/sort/dev` 在 dev 中出現 `511:0` 的數字
:::success
TODO 對照 [sort_mod.c](https://github.com/sysprog21/ksort/blob/master/sort_mod.c)，找尋彼此的關聯。
:::
#### ksort 核心模組內部
### 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉
#### 解釋 `insmod`
##### hello world
透過 insmod 將模組載入核心後，在需要的時候載入核心，可以使 kernel 較為今減，提高效率以及保有較大的彈性。依照教材的說明要加入核心模組需要使用 `insmod` 才會在 `/dev/` 之中新增裝置檔案 `/dev/fibonacci` 所以接下來思考 `/dev` 是作什麼功用？
>The /dev directory contains the special device files for all the devices. The device files are created during installation, and later with the /dev/MAKEDEV script. The /dev/MAKEDEV.local is a script written by the system administrator that creates local-only device files or links (i.e. those that are not part of the standard MAKEDEV, such as device files for some non-standard device driver).
`/dev/` 是 device 的縮寫，此目錄包含所有 linux 系統中使用的的外部設備（非驅動程式）。Linux 核心通過設備驅動來管理這些設備，並將它們表示為文件，使得用戶空間的程式可以通過標準的文件操作來訪問和控制。
##### Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)
##### `MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響
這個巨集用於聲明模組的授權條款，比如是否為 GPL 授權。如果模組聲明為非 GPL，它將無法使用核心中那些標記為 "GPL only" 的符號。這是為了保護 GPL 軟體的自由原則，防止可能的授權衝突。而 GPL 是什麼？以下為 [wiki](https://en.wikipedia.org/wiki/GNU_General_Public_License) 的解釋。
>The GNU General Public License (GNU GPL or simply GPL) is a series of widely used free software licenses, or copyleft, that guarantee end users the four freedoms to run, study, share, and modify the software.
##### 藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些些系統呼叫和子系統？
使用命令 `sudo strace insmod fibdrv.ko`
- 文件和模組處理：使用 `openat` 打開特定模組檔案和其他相關系統檔案，比如動態鏈接庫（`libzstd.so.1`, `libc.so.6` 等）和模組配置文件（如 `modules.softdep`）。
- 記憶體管理：透過 `mmap` 將文件內容映射到記憶體中，以便執行。同時，使用 `mprotect` 設定記憶體保護，確保運行安全。
- 核心互動：執行 `finit_module`，嘗試初始化並加載模組。如果模組已存在，會返回錯誤。
查閱 [finit_module() Linux man page](https://linux.die.net/man/2/finit_module)
`finit_module()` 是一個系統呼叫，用於從文件描述符讀取並加載核心模組。這個函數與 `init_module()` 類似，但它允許從文件系統中的位置直接讀取模組，而 `init_module()` 以下解釋：
>init_module() loads an ELF image into kernel space, performs any necessary symbol relocations, initializes module parameters to values provided by the caller, and then runs the module's init function. This system call requires privilege.
這邊提到的 ELF 是什麼？往下的講義有提到：
>`Executable and Linking Format` 簡稱為 `ELF`，可以表示一個 executable binary file 或是 object file。
`MODULE_XXX` 等巨集會將 module 的額外資訊放入 `fibdrv.ko `中 `.modinfo` 中，modinfo 這個程式應該就是到 `fibdrv.ko` 中的 `.modinfo` 區段讀取資料並做顯示。
`fibdrv.ko` 不是能在 shell 呼叫並執行的執行檔，它只是 ELF 格式的 object file。
以下這段幫我釐清很多觀念
>因此我們需要透過 `insmod` 這個程式（可執行檔）來將 `fibdrv.ko` 植入核心中。`kernel module` 是執行在 kernel space 中，但是 `insmod fibdrv.ko` 是一個在 user space 的程序，因此在 insmod 中應該需要呼叫相關管理記憶體的 system call，將在 user space 中 kernel module 的資料複製到 kernel space 中。
#### 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree)
搭配 [並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-lockfree)
觀察 [simrupt](https://github.com/sysprog21/simrupt):
- `DECLARE_KFIFO_PTR(rx_fifo, unsigned char)`：宣告一個指向 kfifo 的指針，`kfifo` 是一个先進先出（FIFO）的環形緩衝區，它在内核中用來暫存數據，直到數據被用戶空間讀取。
- `produce_data(unsigned char val)`:將 `val` 存入 kfifo buffer 之中。
- `static DEFINE_MUTEX(producer_lock)`;
- `static DEFINE_MUTEX(consumer_lock)`;
- `fast_buf` 是一個額外的、更快速的環形緩衝區（circular buffer），主要用於從 interrupt context 快速存儲數據，然後再將數據傳遞到 kfifo 緩衝區。
- `fast_buf_get` :從 `fast_buf` 緩衝區中讀取數據
- `fast_buf_put` :將數據寫入 `fast_buf` 緩衝區
- `fast_buf_clear` 清空 `fast_buf` 資料
- `simrupt_work_func`
```c
cpu = get_cpu();
pr_info("simrupt: [CPU#%d] %s\n", cpu, __func__);
put_cpu();
```
調用 `get_cpu()` 時，它不僅返回當前 CPU 的編號，還會增加當前線程的前置禁用計數（preemption disable count）。這個計數器的增加會阻止作業系統調度器將該線程從當前 CPU 調度到其他 CPU。任何調用 `get_cpu()` 的地方都應該隨後調用 `put_cpu()`。`put_cpu()` 函數將減少前置禁用計數，允許調度器再次遷移線程。這是確保資源在使用後能夠正常釋放的做法。
```c
while (1) {
/* Consume data from the circular buffer */
mutex_lock(&consumer_lock);
val = fast_buf_get();
mutex_unlock(&consumer_lock);
if (val < 0)
break;
/* Store data to the kfifo buffer */
mutex_lock(&producer_lock);
produce_data(val);
mutex_unlock(&producer_lock);
}
```
在這邊不斷從 fast_buff 搬數據到 kfifo 之中。其中在存取 fast_buff 時會使用 `mutex_lock(&consumer_lock)` 已防止其他線程同時讀取同一資源。隨後 `mutex_unlock(&consumer_lock)` 使其他線程可以進入 fast_buff
:::success
這邊此 mutex(&consumer_lock) 或許可以省略，待釐清
:::
後面在將數據寫入 kfifo buffer 使用一樣操作。
```c
wake_up_interruptible(&rx_wait);
```
在處理完所有 fast_buff 數據後，喚醒所有在 rx_wait 上阻塞的線程，使得任何等待數據的用戶空間進程可以被喚醒並處理新的數據。
- `simrupt_read(struct file *file, char __user *buf, size_t count, loff_t *ppos)`:從 kernel space 的 kfifo 將數據讀取到 user space，使用與上述 `simrupt_work_func` 相同的 mutex 手法，但是這邊使用的是 mutex_lock_interruptible()，與 mutex_lock() 有何區別？以下為 [kernel.org](https://www.kernel.org/doc/html/v4.19/translations/it_IT/kernel-hacking/locking.html#c.mutex_lock_interruptible) 解說：
`int mutex_lock_interruptible(struct mutex * lock)`
>Lock the mutex like mutex_lock(). If a signal is delivered while the process is sleeping, this function will return without acquiring the mutex.
由於 `mutex_lock()` 不能被信號打斷，因此存在失去響應的風險。進而演伸出 ` mutex_lock_interruptible()` 當 mutex 為睡眠狀態還可以接受 interrupt。
參閱[並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-lockfree)
>根據定義，所有 wait-free 都屬於 lock-free
故就算不使用 mutex lock (e.g. busy waiting)，不代表就是 lock-free，例如 `while (x == 0) { x = 1 - x; }` 這樣的程式碼 (當 x 為共享變數)
1. Atomic Operation: Read-Modify-Write
2. Compare-And-Swap Loops
3. Sequential Consistancy
4. Memory Ordering
:::success
尚不知道如何改為 lock-free
:::
### 探討 sort
查閱 fluxsort, crumsort 之中它所使用的 `bench.c`
### 研讀 CMWQ 文件，對照 simrupt 專案
>When such an asynchronous execution context is needed, a work item describing which function to execute is put on a queue. An independent thread serves as the asynchronous execution context. The queue is called workqueue and the thread is called worker.
這邊介紹了 workqueue 與 worker，Workqueue是一個用來存放工作項目，Worker是獨立的線程，為存放在 workqueue 中的工作項目。
為什麼需要 CMWQ? 在傳統的多線程 (MT) wq 實現中，每個 CPU 都有一個工作線程，而單線程 (ST) wq 則在整個系統中只有一個工作線程。隨著 CPU 核心數的增加，這導致了大量的工作線程創建，進一步導致 PID 空間的濫用和資源浪費。
>An MT wq could provide only one execution context per CPU while an ST wq one for the whole system. Work items had to compete for those very limited execution contexts leading to various problems including proneness to deadlocks around the single execution context.
MTwq 實現方式為每一在線程在每一個 CPU 執行，而 ST wq 在一個時間只會執行一個線程，此行為容易造成 deadlocks。
CMWQ 為一個 wq 重新實作方式並目標達成以下：
1. 維持原本 wq API
2. 每一個 CPU 維持自己的 workers pool，這些 pools 在 wq 中共享
3. 自動調節 worker pool 還有平性度
每一個 CPU 會有兩種 worker-pools，一個用於普通工作項目，另一個用於高優先級工作項目。
>When a work item is queued to a workqueue, the target worker-pool is determined according to the queue parameters and workqueue attributes and appended on the shared worklist of the worker-pool. For example, unless specifically overridden, a work item of a bound workqueue will be queued on the worklist of either normal or highpri worker-pool that is associated to the CPU the issuer is running on.
那 work 會怎麼排進哪一個 worker-pools 呢？ 除非有特殊覆蓋 （cpu_mask）到指定 CPU，work 會被分配到與作為發出者的 CPU。這樣 work 可以直接去使用 CPU 快取以減少存取成本並減少線程遷移的開銷。
使用命令 `sudo dmesg` 可以看到如以下，指定在 CPU#4 上，且如同說明文件，work handler 會自己在一個 CPU（此範例為 #17），單一 CPU 有自己的 work pool 並在自己 CPU 上運行。
```shell
[ 1062.739759] simrupt: [CPU#17] simrupt_work_func
[ 1062.843606] simrupt: [CPU#4] enter timer_handler
[ 1062.843621] simrupt: [CPU#4] produce data
[ 1062.843625] simrupt: [CPU#4] scheduling tasklet
[ 1062.843629] simrupt: [CPU#4] timer_handler in_irq: 8 usec
[ 1062.843647] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 3 usec
[ 1062.843731] simrupt: [CPU#17] simrupt_work_func
[ 1062.947580] simrupt: [CPU#4] enter timer_handler
[ 1062.947595] simrupt: [CPU#4] produce data
[ 1062.947599] simrupt: [CPU#4] scheduling tasklet
[ 1062.947602] simrupt: [CPU#4] timer_handler in_irq: 7 usec
[ 1062.947622] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 3 usec
[ 1062.947709] simrupt: [CPU#17] simrupt_work_func
```
#### 翻閱 [include/linux/workqueue.h](https://github.com/torvalds/linux/blob/c942a0cd3603e34dd2d7237e064d9318cb7f9654/include/linux/workqueue.h)
在 `include/linux/workqueue.h` 裡面有很詳細的說明，尤其是 `struct workqueue_attrs` 這個結構體的定義。其中特別需要注意的是，`cpumask_var_t cpumask`
> Work items in this workqueue are affine to these CPUs and not allowed to execute on other CPUs. A pool serving a workqueue must have the same cpumask.
使用此遮罩可以限定在與工作提交的相同 CPU 上面執行，盡量避免 CPU 之間 migrate，盡可能使用 CPU 快取的局部性。
翻閱 [linux/kernel/workqueue.c](https://github.com/torvalds/linux/blob/c942a0cd3603e34dd2d7237e064d9318cb7f9654/kernel/workqueue.c)裡面可以找到對 workqueue_init 有三個步驟，我嘗試在這邊尋找 cpumask 的操作。
第一步： `workqueue_init_early()`：此階段主要負責初始最基本的資料結構和系統工作，這一階段的初始化發生在記憶體分配、cpumask 和 idr 初始化之後。這個階段還沒有 kthreads 創建和調度，所以實際的工作項目執行將會推遲到下一階段。
#### 閱讀 《Demystifying the Linux CPU Scheduler》
在 page 157 寫到：
會使用 `sched_setaffinity()` and `sched_getaffinity()` 這兩個函式來設定或是獲取 affinity mask。工作必須維持在由 `cpu_mask` 與 `task_struct` 結構中。新的線程會繼承其父線程之 affinity mask。可以直接使用 `taskset` 這個命令將進程指定或是更改於特定 CPU。
我們因用書中所提到的例子：
```shell
$ echo "0" > $MOUNT_POINT/mygroup/group1/cpuset.cpus
$ taskset -pc $PID
pid 2259's current affinity list: 0
```
我們使用 `taskset` 將此 process 指定在 CPU 0。
使用 `systemd-cgtop` 和 `top` 命令來檢查特定腳本對系統資源分配的影響。
`systemd-cgtop` 命令提供了一個動態視圖，顯示系統中控制組（cgroup）的資源使用情況。控制組是 Linux 中用於資源分配、優先級設定和計量的一種機制，它允許系統管理員對系統資源進行細粒度的控制。`top` 命令顯示了系統中各個處理器的即時資源使用情況。從 `systemd-cgtop` 的輸出可以看到，mygroup/group1 的任務正在大量使用 CPU 資源，而 top 的輸出則確認了這些任務僅在 CPU 0 上運行，與之前設置的 CPU 親和性相符。
### 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序
在 `ksort/sort_impl.c` 中發現它引入核心模組 `linux/workqueue.h`，我們往下觀察 `qsort_algo` 其中實作的實現會用元素數量來使用不同作法，在元素量小於 7 會使用 insertion sort:
```c
if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
pl -= es)
q_swap(pl, pl - es);
return;
}
```
當元素量大於 7 會使用 quick sort:
```c
pm = (char *) a + (n / 2) * es;
if (n > 7) {
pl = (char *) a;
pn = (char *) a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
pm = med3(pm - d, pm, pm + d, cmp, thunk);
pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
}
pm = med3(pl, pm, pn, cmp, thunk);
}
q_swap(a, pm);
pa = pb = (char *) a + es;
pc = pd = (char *) a + (n - 1) * es;
for (;;) {
while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
if (r == 0) {
swap_cnt = 1;
q_swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
if (r == 0) {
swap_cnt = 1;
q_swap(pc, pd);
pd -= es;
}
pc -= es;
}
if (pb > pc)
break;
q_swap(pb, pc);
swap_cnt = 1;
pb += es;
pc -= es;
}
```
在快速排序算法中，選擇一個好的 pivot 是提高排序效率的關鍵。如果樞軸選擇得當，可以盡可能均勻地將數據分成兩部分，這樣可以減少算法的遞迴深度，並最大化每次遞迴所能達到的數據分割效率。使用 `med3()` Median-of-three 方法更能取到接近中間的 pivot。所以最終會獲得 pivot `pm`。再切出左右子集：
```c
nl = (pb - pa) / es;
nr = (pd - pc) / es;
```
使用 `nl`、`nr` 紀錄左右子數組的數量。如果兩個子數組的大小都超過 100，則選擇異步處理方式。
```c
if (nl > 100 && nr > 100) {
struct qsort *q = kmalloc(sizeof(struct qsort), GFP_KERNEL);
init_qsort(q, a, nl, c);
queue_work(workqueue, &q->w);
} else if (nl > 0) {
qs->a = a;
qs->n = nl;
/* The struct qsort is used for recursive call, so don't free it in
* this iteration.
*/
do_free = false;
qsort_algo(w);
}
```
動態分配一個 struct qsort 結構來處理其中一個子數組。再使用 `init_qsort()` 初始化新分配的 struct qsort 結構，準備對左子數組進行排序。
目前按照文件說明會發現當調用 queue_work 這個函式通常會嘗試將工作繫結到提交工作的 CPU 上。
:::success
實際 cpumask 行為的追蹤應該補上
:::
我在 `qsort_algo()` 的 `work_queue` 引用 `simrupt` 專案的程式，用來見測它是否真的在同一個 cpu 上執行：
```c
/* Pretend to simulate access to per-CPU data, disabling preemption
* during the pr_info().
*/
int cpu = get_cpu();
pr_info("sort: [CPU#%d] %s\n", cpu, __func__);
put_cpu();
```
使用 `sudo dmesg` 得到以下結果：
```shell
[ 6488.143982] sort: [CPU#2] qsort_algo
[ 6488.143986] sort: [CPU#2] qsort_algo
[ 6488.143997] sort: [CPU#2] qsort_algo
[ 6488.144011] sort: [CPU#2] qsort_algo
```
可以看到有如文件所說，調用 `work_queue()` 使他在同一個 cpu 上執行，詳細程式細節尚未追蹤。
### 作業主題一: 並行的混合排序
到了實際要寫並行排序的時候，發現我對怎麼撰寫 driver 掌握度很差，故決定先研讀 [Writing a simple device driver](https://www.apriorit.com/dev-blog/195-simple-driver-for-linux-os) 提高掌握度。
```c
#include <linux/init.h>
#include <linux/module.h>
static int my_init(void)
{
return 0;
}
static void my_exit(void)
{
return;
}
module_init(my_init);
module_exit(my_exit);
```
`my_init` 函數是驅動程式的初始化入口點，在系統啟動時被調用當模被插入到核心中時。`my_exit` 函數是驅動程式的退出點。它在從 Linux 核心卸載模塊時被調用。
`Device file` 通常存儲在 `/dev` 文件夾中。它們促進了 user space 和 kernel space 之間的互動。要讓核心接收任何東西，可以撰寫 divice file 來傳遞資訊給負責得模組。
而 device file 會有兩種：
1. Character files: 無 buffe，透過 read/write 字元在 user space 與 kernel space 溝通
2. Block files：有 buffer，已整個 block 為單位 read/wite
Linux 系統有兩種識別 device file 的方法：
1. Major device numbers：標示設備編號（若是設備編號已經被使用，會回傳 error）
2. Minor device numbers：指定特定設備
要註冊 character device，我們需要使用 `register_chrdev` 函數：
```c
int register_chrdev (unsigned int major,
const char * name,
const struct file_operations * fops);
```
然而我觀察查到在 simrupt 專案中它使用 `device_create()` 去註冊核心模組。在模組卸載的時候也要有相段應的 `unregister_device()`，以釋放掉資源。
我們可以使用 `printk()` 函式，它可以輸出字串於系統 log，可以在核心任何位置調用此函式。
接下來的 read function 會從 device 中讀取字元。
`ssize_t (*read) (struct file *filep, char *buffer, size_t len, loff_t *offset);`
它提供了一個機制，允許 user space 程序通過像操作普通文件那樣使用 read() 系統調用來從設備讀取數據。這實現了 user space 和 kernel space 之間的數據交換。
當內核需要將數據發送到 user space 應用程序時，`copy_to_user()` 被用來安全地執行這一操作。這涉及到從內核分配的記憶體區域（如驅動程序的內部緩衝區）將數據複製到由用戶應用程序提供的緩衝區。由於 kernel space 和 user space 在記憶體管理上是隔離的，直接訪問 user space 記憶體可能導致安全問題或系統崩潰，因此需要使用這種安全的複製方法。
在撰寫 Makefile 要注意的是 module build system 位在 `/lib/modules/`uname -r`/build` 所以像是 `sumrupt` 中的 Makefile 就如以下撰寫：
```makefile
KDIR := /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)
all: $(GIT_HOOKS) user test_xoro
$(MAKE) -C $(KDIR) M=$(PWD) modules
```
以上為撰寫 kernel module 的補充
---
#### 量化執行時間
##### 在 Linux 核心模組測量
> [commit 3ffaca0](https://github.com/vestata/ksort/commit/3ffaca0f495355830581ad1d6c2863fb8312e414)
Linux 核心模組中，使用 ktime 系列的 API
調用 `#include <linux/ktime.h>` 使用 `ktime_get_ns()` 然後再使用 printk 輸出到核心訊息之中。
```shell
[91110.738868] Sorting took 58277 nanoseconds.
```
##### 在 user space 測量
調用 clock_gettime 相關 API 即可完成，注意要對 user.c 中的 `read()` 做測量，他是對 kernel module 的對皆口。
接下為為了要比對不同排序的時間，我需要輸出一個 .csv 檔案用來儲存資料以便使用 gnuplot 來輸出比較圖。我使用的作法是使用 `printk` 所紀錄的核心時間，使用 dmesg， grep 與 awk 去抓取。一開始在撰寫 Makefile 遇到問題，當直接在 Makefile 中寫 `$(NF-1) `時，Makefile 會試圖解釋這裡的 `$(NF-1)` 為一個 Makefile 變量，而不是 awk 的腳本部分。
改為：
```makefile
sudo dmesg | grep "Sorting took" | awk '{print $$(NF-1)}' >> out.csv
```
#### 引入其他排序方法
> [commit 9194cd7](https://github.com/vestata/ksort/commit/9194cd7b4f76fb9807855c483fdc11d882321166)
由於一開始的 kosrt 專案只有並行 quicksort 定義在 `sort_main()` 之中，要完成其他排序的比較會需要的是將其他排序手法掛載進去，所以我先著手的是 `lib/sort.c`，畢竟已有很完整的程式。由於 `sort.c` 這個名子在專案中很容易有衝突，故我先將其改名為 `l_sort.c` 。因為此專案的測資資料型態為 `size_t` 長度為 64 位元，翻閱其 `l_sort.c` 找到其對應 swap 函式的巨集：
```c
#define SWAP_WORDS_64 (swap_r_func_t) 0
```
，所以在呼叫的時候我選擇使用以下：
```c
l_sort(sort_buffer, size / es, es, num_compare, 0);
```
接下來要處理的設定可以在 user space 選擇要使用 ksort 或是 l_sort。所以我在 `user.c` 之中使用 `ioctl` 做完參數，使它可以將 user space 所定義的參數傳入 kernel space。
```c
ioctl(fd, sort_method);
```
而在模組的程式需要改動的是先定義ioctl 請求的處理函數為以下
```c
static long sort_ioctl(struct file *file, unsigned int cmd, unsigned long arg)
{
current_sort_method = cmd;
return 0;
}
```
在 Linux 內核模組的 file_operations 結構中，.unlocked_ioctl 成員用於指定一個函數，該函數將處理從 user space 發來的 ioctl 請求。sort_ioctl 是這個 ioctl 請求的處理函數。當用戶空間的應用程序執行 ioctl 命令時，這個函數被呼叫來執行特定的內核級操作，如讀取或修改設備的配置。
```c
static const struct file_operations fops = {
.read = sort_read,
.write = sort_write,
.open = sort_open,
.release = sort_release,
.owner = THIS_MODULE,
.unlocked_ioctl = sort_ioctl,
};
```
所以接下來定義 sort 的主程式：
```c
if (current_sort_method == 0) {
start = ktime_get_ns();
sort_main(sort_buffer, size / es, es, num_compare);
end = ktime_get_ns();
duration = end - start;
printk(KERN_INFO "ksort took %llu nanoseconds.\n", duration);
} else if (current_sort_method == 1) {
start = ktime_get_ns();
l_sort(sort_buffer, size / es, es, num_compare, 0);
end = ktime_get_ns();
duration = end - start;
printk(KERN_INFO "l_sort took %llu nanoseconds.\n", duration);
}
```
針對每一個排序做時間的計算，對接上面提到的時間測量手法。
#### 繪圖
> [commit f74179a](https://github.com/vestata/ksort/commit/f74179a2b9b6187a71c6d408e743fd2a8a133936)
為了要方便比較排序手法所以撰寫了 bash 腳本已方便執行，以 500 為一步長測量 1000 ~ 20000 筆資料的排序速度，對腳本比較不熟悉所以花了較多時間撰寫，還遇到
```gp
echo "$n, $duration" >> "$output_file"
```
忘了加空格，所以輸出 .csv 檔案對於 .gp 檔案花了多時間尋找錯誤。藉此警惕。
在腳本中撰寫以下已獲取排序執行時間 （ns）。
```gp
sudo dmesg | grep "took" | awk '{print $5}'
```
接下來撰寫一個 gnuplot 檔案 `test.gp` 使它接到數據 .csv 檔案，我將其步驟寫入 Makefile 之中 所以之後只要下命令 `make [ksort|l_sort]` 便可以生出相對應數據。
生出以下圖形：
可以觀察到數值很不平均，需要對其做除去極端數值的動作。
使用 [hankluo6/ksort/outlier.py](https://github.com/hankluo6/ksort/blob/master/outlier.py) 中的方法去除極端值
這邊遇到一個問題是當我要測量數量較多的數據，比如說 1000 ~ 20000 ，步數為 5，他運行到一半就會卡住，如下圖：
使用 `ctrl + c` 也無法退出，只能重新開機。(尚未安裝使用 UML)
我推測是因為從 user space 複製到 kernel space 的緩衝區有上限？目前只有 l_sort 正常執行 （1000 ~ 20000, step=5）
這邊發現是原本 ksort workqueue 的 work 沒有正常釋放？
使用 `sudo dmesg` 輸出以下錯誤：
```shell
[ 156.659689] general protection fault, probably for non-canonical address 0x761b1616a86d165c: 0000 [#1] PREEMPT SMP NOPTI
[ 156.659703] CPU: 4 PID: 757 Comm: kworker/4:2 Tainted: G OE 6.5.0-28-generic #29~22.04.1-Ubuntu
[ 156.659710] Hardware name: Gigabyte Technology Co., Ltd. Z790 D DDR4/Z790 D DDR4, BIOS F2 10/03/2022
[ 156.659713] Workqueue: sortq qsort_algo [sort]
[ 156.659732] RIP: 0010:qsort_algo+0x2c/0xbf0 [sort]
[ 156.659746] Code: 44 00 00 55 48 89 f8 48 89 e5 41 57 41 56 41 55 41 54 53 48 83 ec 78 48 8b 5f 20 48 89 bd 60 ff ff ff 4c 8b 68 28 48 8b 40 30 <48> 8b 7b 10 4c 8b 43 08 48 89 9d 68 ff ff ff 8b 1b 48 89 45 88 48
[ 156.659751] RSP: 0018:ffffb2774169faf0 EFLAGS: 00010286
[ 156.659756] RAX: 0000000000000003 RBX: 761b1616a86d164c RCX: ffff92cbd8352e84
[ 156.659759] RDX: 0000000000000000 RSI: 000000000000000c RDI: ffff92cbd9284340
[ 156.659762] RBP: ffffb2774169fb90 R08: 0000000000000004 R09: 0000000000000014
[ 156.659765] R10: 0000000000000000 R11: ffff92cbd8352e74 R12: ffff92cbd8352e7c
[ 156.659768] R13: ffff92cbd8352e70 R14: fffffffffffffffc R15: 0000000000000005
[ 156.659771] FS: 0000000000000000(0000) GS:ffff92cf6f700000(0000) knlGS:0000000000000000
[ 156.659775] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 156.659778] CR2: 00007ffd47151080 CR3: 0000000247f4e000 CR4: 0000000000750ee0
[ 156.659782] PKRU: 55555554
[ 156.659784] Call Trace:
```
:::success
不知道這怎麼辦，再問問 jserv
:::
> [commit 14daeca](https://github.com/vestata/ksort/commit/9194cd7b4f76fb9807855c483fdc11d882321166)
timsort 的部份因為這次的測試項目是在陣列之中，基於以下兩個原因我選擇使用 [patperry/timsort](https://github.com/patperry/timsort) 所撰寫的版本。第一，由於測驗題中的 timsort 算是一個半成品，很多功能我尚未補齊，所以直接使用已撰寫好的版本; 第二，這次測試項目是陣列的型態，而測驗題的 timsort 是針對 LIST API 所撰寫。
要將此專案引入需要將引用的標頭檔更換為適用於 kernel module 得標頭檔。將計體配置換成 kmalloc/kfree，將 assert 與 errno 等使用於 user space 的函式刪除。將其融入原本的專案。
得出以下的結果：
最後還是發現，排序表現還是非常混亂，還是需要處理上述資料量一大程式就會卡住的問題，目前資料量還是太少，需要更大的資料量才能處理去除偏差值或是使用線性回歸繪圖。
Sign in with Wallet
Connect another wallet