# 2024q1 Homework6 (integration)
contributed by < [`Wufangni`](https://github.com/Wufangni) >
## 開發環境
``` shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12500H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU max MHz: 4500.0000
CPU min MHz: 400.0000
BogoMIPS: 6220.80
```
## 自我檢查清單
- [x] 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
> Linux 核心 4.4 版以後 Ubuntu Linux 預設使用 `EFI_SECURE_BOOT_SIG_ENFORCE`，若核心模組沒有簽章則無法掛載至核心，因此需要預先關閉 UEFI Secure Boot 的功能
- 使用 `mokutil --sb-state` 查看 Secure Boot 是否停用成功。
``` shell
$ sudo mokutil --sb-state
SecureBoot enabled
SecureBoot validation is disabled in shim
```
- 檢查核心版本是否大於 5.15.0。
``` shell
$ uname -r
6.5.0-28-generic
```
:::danger
你現在執行的 Linux 核心版本是什麼？
:::
- 安裝 linux-headers 套件及確認是否正確裝於開發環境。
``` shell
$ dpkg -L linux-headers-5.15.0-102-generic | grep "/lib/modules"
/lib/modules/5.15.0-102-generic/build
```
- [X] 閱讀 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module#fibdrv-%E5%8F%AF%E8%BC%B8%E5%87%BA-Fibonacci-%E6%95%B8%E5%88%97%E7%9A%84-Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
**練習 hello.c 測試**
- 新增 hello 目錄，建立兩個檔案 `hello.c` 及 `Makefile`，編譯核心模組產生 `hello.ko` 。
``` shell
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
```
- 嘗試對核心掛載及卸載兩指令
``` shell
$ sudo insmod hello.ko
$ sudo rmmod hello
```
- 使用 `dmesg` 顯示核心訊息
``` shell
[88338.431769] Hello, world
[88361.955635] Goodbye, cruel world
```
**fibdrv: 可輸出 Fibonacci 數列的 Linux 核心模組**
- 取得 `fibdrv` 程式碼進行 `make check` 編譯測試，觀察核心模組 `fibdrv.ko` 。
``` shell
$ modinfo fibdrv.ko
filename: /home/fangni/fibdrv/fibdrv.ko
version: 0.1
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: 6DA710BB9C77E697D6DBEEA
depends:
retpoline: Y
name: fibdrv
vermagic: 6.5.0-28-generic SMP preempt mod_unload modversions
```
檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 會在編譯 `.ko` 檔後提供對應的資訊，在 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module#fibdrv-%E5%8F%AF%E8%BC%B8%E5%87%BA-Fibonacci-%E6%95%B8%E5%88%97%E7%9A%84-Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84) 中以 `MODULE_AUTHOR` 為例。
在 `fibdrv.c` 可看到對巨集的定義:
``` c
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
```
回朔至 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/module.h#L205) 找到 `MODULE_AUTHOR` 使用 `MODULE_INFO` 結構
``` c
#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)
```
再從 [include/linux/moduleparam.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/moduleparam.h) 觀察， `__MODULE_INFO` 使用到 `__UNIQUE_ID` 。
``` c
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
從 [include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/compiler-gcc.h#L208) 看到定義過程使用了 `__PASTE`。
``` c
#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
```
再對 `__UNIQUE_ID` 繼續做展開:
``` c
static const char __PASTE(__PASTE(__UNIQUE_ID_, author), __COUNTER__)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(author) "=" "National Cheng Kung University, Taiwan"
```
`__UNIQUE_ID` 使用傳入的兩參數產生一個不重複的名字，`__attribute__` 告訴編譯器文字存放的位置及其餘格式設定，`__stringify` 會將引數轉換成字串，因此 `MODULE_` 系列的巨集最後會轉變成唯一獨立的變數。
**藉由 strace 追蹤 Linux 核心的掛載**
``` shell
$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7fff78d52d88 /* 26 vars */) = 0
brk(NULL) = 0x55ad5cf7b000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffd4d65fde0) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7b99da089000
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=58227, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 58227, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b99da07a000
close(3) = 0
...
close(3) = 0
getcwd("/home/fangni/fibdrv", 4096) = 20
newfstatat(AT_FDCWD, "/home/fangni/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274752, ...}, 0) = 0
openat(AT_FDCWD, "/home/fangni/fibdrv/fibdrv.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=274752, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274752, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7b99d9f3a000
finit_module(3, "", 0) = 0
munmap(0x7b99d9f3a000, 274752) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
追蹤過程中可看到 `finit_module` 被系統執行，此函數用於動態加載 linux 核心模組，擴展系統功能性及添加新的驅動程序。
- [x] 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢?
從 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/module.h#L129) 觀察 `module_init` 的定義方式:
``` c
/* Each module must use one module_init(). */
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __attribute__((alias(#initfn)));
```
- `static inline initcall_t __maybe_unused __inittest(void)` 標記函數為未使用並傳回名為 `initfn` 的初始化函數指針。
- 查閱 GCC 手冊 `__attribute__((alias("target")))` 用於給予函數或變量設置別名，讓其指向另一個函數，在這裡 `init_module` 被給予另一個別名 `initfn` ，使得加載模組時不會直接使用到 `init_module` ，而是調用 `module_init` 函數。
- 從註解中提到每個模組在加載過程中必須使用到 `module_init()` 進行初始化函數。
系統在執行 `finit_module` 後會執行 `load_module` ，從 [kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3785) 觀察 `load_module` 定義:
``` c
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
struct module *mod;
//...
/* Figure out module layout, and allocate all the memory. */
mod = layout_and_allocate(info, flags);
if (IS_ERR(mod)) {
err = PTR_ERR(mod);
goto free_copy;
}
// ...
return do_init_module(mod);
// ...
}
```
使用 `layout_and_allocate` 對模組進行記憶體配置，接著以 `do_init_module` 對模組進行初始化。
``` c
static noinline int do_init_module(struct module *mod)
{
// ...
/* Start the module */
if (mod->init != NULL)
ret = do_one_initcall(mod->init);
// ...
}
```
再從 [init/main.c](https://elixir.bootlin.com/linux/v4.18/source/init/main.c#L874) 中追述 `do_one_initcall` 的定義，可看到`ret = fn()` 實際上針對函數 `fn` 進行初始化工作。
``` c
int __init_or_module do_one_initcall(initcall_t fn)
{
// ...
do_trace_initcall_start(fn);
ret = fn();
do_trace_initcall_finish(fn, ret);
// ...
}
```
- [x] 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
Executable and Linking Format(ELF) 可以表示成一種二進制文件格式，用於儲存 Executable File、Shared Library 和 Object File，可分成 ELF header、Section(s)、Section Header(s)三部份。
``` shell
$ readelf -a fibdrv.ko
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: REL (Relocatable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x0
Start of program headers: 0 (bytes into file)
Start of section headers: 271424 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 0 (bytes)
Number of program headers: 0
Size of section headers: 64 (bytes)
Number of section headers: 52
Section header string table index: 51
```
從 `ELF header` 中可觀察到 `fibdrv.ko` 沒有 program headers 等訊息，因此 `fibdrv.ko` 不是能在 shell 呼叫的可執行檔，需要透過可執行檔 `insmod` 來將其植入核心，所需使用到 system call 將核心模組的資料複製到 kernel space。
- [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);
`simrupt_work_func` 使用到 `kfifo buffer` 與 `circular buffer` 兩種儲存 data 的方式作為例子，先從 `kfifo` 觀察，為一種 First-In-First-Out (FIFO) 的結構體，在此定義一個 `rx_fifo` 的 kfifo 資料結構儲存傳遞到 userspace 的 data。
``` c
/* Data are stored into a kfifo buffer before passing them to the userspace */
static struct kfifo rx_fifo;
```
`kfifo` 生產資料使用到 `kfifo_in` 函數，此函數會先確認 buffer 剩餘空間大小是否裝的下生產的資料總長度，若不夠大則以剩餘空間長度為主複製資料到 buffer 中，足夠大則全部複製過去，最後更新 buffer 中插入資料的 index 並回傳插入資料的長度。
``` c
/* Insert a value into the kfifo buffer */
static void produce_data(unsigned char val)
{
/* Implement a kind of circular FIFO here (skip oldest element if kfifo
* buffer is full).
*/
unsigned int len = kfifo_in(&rx_fifo, &val, sizeof(val));
if (unlikely(len < sizeof(val)) && printk_ratelimit())
pr_warn("%s: %zu bytes dropped\n", __func__, sizeof(val) - len);
pr_debug("simrupt: %s: in %u/%u bytes\n", __func__, len,
kfifo_len(&rx_fifo));
}
```
`Circular Buffer` 為一種固定大小的環狀記憶體緩衝區，`head index` 用於指向可插入資料的剩餘空間索引，`tail index` 則指向消費者即將取出資料的索引位置。
在 [include/linux/circ_buf.h](https://elixir.bootlin.com/linux/latest/source/include/linux/circ_buf.h) 可看到結構體的定義:
``` c
struct circ_buf {
char *buf;
int head;
int tail;
};
/* Return count in buffer. */
#define CIRC_CNT(head,tail,size) (((head) - (tail)) & ((size)-1))
/* Return space available, 0..size-1. We always leave one free char
* as a completely full buffer has head == tail, which is the same as
* empty.
*/
#define CIRC_SPACE(head,tail,size) CIRC_CNT((tail),((head)+1),(size))
```
`CIRC_CNT` 被消費者所使用到，用於計算 buffer 內含有的物體數量; `CIRC_SPACE` 則被生產者所使用，用於計算剩餘空間數量。
``` c
static int fast_buf_get(void)
{
struct circ_buf *ring = &fast_buf;
/* prevent the compiler from merging or refetching accesses for tail */
unsigned long head = READ_ONCE(ring->head), tail = ring->tail;
int ret;
if (unlikely(!CIRC_CNT(head, tail, PAGE_SIZE)))
return -ENOENT;
/* read index before reading contents at that index */
smp_rmb();
/* extract item from the buffer */
ret = ring->buf[tail];
/* finish reading descriptor before incrementing tail */
smp_mb();
/* increment the tail pointer */
ring->tail = (tail + 1) & (PAGE_SIZE - 1);
return ret;
}
```
`fast_buf_get` 函數代表消費者，分別取得 buffer 的 `head` 及 `tail` 後先使用 `smp_rmb()` 作為記憶體緩衝區保護取出資料的過程，`ret = ring->buf[tail]` 取出該筆資料後執行 `smp_mb()` ，並對 `tail` 做更新，最後回傳取出的資料內容。
接著從 [linux/include/linux/workqueue.h](https://elixir.bootlin.com/linux/latest/source/include/linux/workqueue.h) 看到兩個 `mutex lock` 的定義:
``` c
/* Mutex to serialize kfifo writers within the workqueue handler */
static DEFINE_MUTEX(producer_lock);
/* Mutex to serialize fast_buf consumers: we can use a mutex because consumers
* run in workqueue handler (kernel thread context).
*/
static DEFINE_MUTEX(consumer_lock);
```
`producer_lock` 作為生產者執行程式時的保護鎖，以 `mutex_lock` 及 `mutex_unlock` 方式防止其餘 thread 干擾包在其中的程式，而 `consumer_lock` 作為消費者的保護鎖，功能與 `producer_lock` 相似。
``` 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);
}
```
在 `simrupt_work_func` 函式中以 `val = fast_buf_get()` 執行消費者從 `circular buffer` 中取出資料，而 `produce_data(val)` 則是將剛才取出的資料放至 `kfifo buffer` 中，兩個過程分別都由 `mutex_lock` 及 `mutex_unlock` 保護，確保只有一個 thread 可對 `buffer` 進行存取。
在 `simrupt` 中單純使用 lock 作為共同資料存取的保護手段，但在多執行緒環境下此方法容易有阻塞問題，也就是說當其中一個 thread 再對共同記憶體進行存取過程時因為 lock 的性質，導致其餘欲使用到此空間的 thread 執行停滯，而若此時原進行存取的執行緒被系統做搶先或直接被 kill 則會造成所有 thread 都被迫暫停工作的情形，因此為了提昇多執行緒的效能達成並行成效，可使用 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree) 方法做改進。
lock-free 為一種實現並行操作的方法，避免使用 lock 減少執行緒間的競爭關系，它使得執行緒間不須等待其他人釋放 lock 就可以自由操作，主要依賴於 `Compare and Swap (CAS)` 實現對共用資源的並行存取操作。
``` c
int CAS(int *a, int old_val, int new_val) {
if (*a == old_val) {
*a = new_val;
return old_val;
}
return *a;
}
```
`CAS` 有三種須代入的參數，分別為用來比較的指標變數 `*a`、指標原先的舊數值 `old_val` 以及要做替換的新數值 `new_val`。
``` c
int old, new;
do {
old = *p;
new = NEW_VALUE;
} while(CAS(*p, old, new) != new);
```
使用 `CAS` 包覆的迴圈作為 Critical Section，其空間為共用記憶體做存取，若執行到該空間的內容則 `CAS` 會去檢查 `p` 的值是否與原先 `old` 的值相同，一樣代表此空間沒有被其他執行緒使用過可以將 `p` 的值替換為 `new`，而若不相同則重新跑一次迴圈。
- [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 排程器互動？
`workqueue` 作為 linux 核心對非同步的執行手段，其中 `work item` 代表欲執行的一種工作項目，創建時會先將其加入到等待佇列( workqueue )中，等待 linux 核心找到適合的 `work thread` 執行，以往 `workqueue` 的作法分成兩種方式:
1. **single threaded (ST) workqueue**
只依靠單一個 `work thread` 來處理系統上所有的 `work item`，因此若前面正執行的 `work item` 非常龐大，其餘所有的 work 都須等待該`work thread` 執行結束，雖然有可節省資源的優勢在(只需要少數的 `work thread` )，但會造成系統執行效率低落的問題。
2. **multi threaded (MT) workqueue**
每個 CPU 上會有一個 `work thread`，對於每個 `workqueue` 會有自己的一個 `thread pool` 且數目固定，對於分配到該 CPU 的 `work item` 有嚴格的綁定關係，不能隨意移到別的 `work thread` 上執行，需要多個 `work thread` 配合故十分消耗資源，雖然可緩解執行效率低落的現象，但在並行的效果有限，且不可避免的還是會有死結情況產生。
因此 CMWQ（Concurrent Multi-Queue Workqueue）方法被提出用於解決 ST 及 MT 效能和耗能上的問題，它打破一般對於 `workqueue` 與特定的 `thread pool` 之間的關聯性，建立若干個 `worker pool` (其等於 `thread pool` 的概念) 可共享給所有的 `workqueue` ，且可以根據 CPU 的負載情況動態調整 `worker pool` 大小釋放 `work thread` ，更好的實現並行，其主要實現的目標有:
- **維持與原始 `workqueue` 的兼容性**
在與原本 `workqueue` 相容的情況下原始程式碼可以更容易的移植到 CMWQ，不需要進行過大的改動。
- **共享 per-CPU worker pools**
CMWQ使得每個 `workqueue` 都可共用 per-CPU worker pools，也就是說不同的 `workqueue` 可共同使用一個 `work pool`, 減少資源浪費。
- **黑盒子式調整**
`worker pool` 和並行等級共同封裝在系統內部，使用者只須使用系統提供的 API 進行提交和管理。
在 CMWQ 設計理念中分為兩種 `work pool` 類型，屬於Bound 類型的 `work pool` 會被限制與特定的 CPU 綁定，且每個 CPU 會有兩個 `work pool`，一個提供給普通的 work，一個則給予高等級的 work，藉由 `workqueue` 上的 `flag` 決定由哪一個來執行;屬於 Unbound 類型的 `work pool` 未與 CPU 做綁定，可動態釋放 `work thread` 減少資源消耗。
透過 `workqueue API` 生成的 `work item` 會根據 `workqueue` 參數和本身的屬性決定該交由哪個種類的 `work pool` 處理，而只要 CPU 上存在一個或個正在執行的 `worker thread`， `work pool` 就會停止執行新的 work 直到最後一個 `worker thread` 執行結束，確保不會有尚有 `work item` 但 `worker thread` 卻閒置的問題，且不會過度產生 `worker thread`。
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
- [ ] 解釋 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+ 是否有速度的優勢？其弱點又是什麼？
Sign in with Wallet
Connect another wallet