# 2024q1 Homework6 (integration)
contributed by < `chloe0919` >
## 自我檢查清單
- [x] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作

* 第一個 Linux 核心模組的撰寫：

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

* 掛載核心模組

$ sudo insmod hello.ko

* 顯示核心訊息

$ sudo dmesg

* 卸載核心模組

$ sudo rmmod hello

- [x] 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

**fibdrv: 可輸出 Fibonacci 數列的 Linux 核心模組**

將 `fibdrv.ko` 核心模組掛載後觀察其行為，執行以下命令：

$ ls -l /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev

會輸出 `511:0`，並且對照 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c#L125) 觀察輸出的意思，可以看到以下程式中會利用 `register_chrdev` 讓 kernel 自動分配一個未被註冊的註冊號，並且用 `if` 進行錯誤處理

rc = major = register_chrdev(major, DEV_FIBONACCI_NAME, &fib_fops);
if (rc < 0) {
    printk(KERN_ALERT "Failed to add cdev\n");
    rc = -2;
    goto failed_cdev;
}
fib_dev = MKDEV(major, minor);

在 [kdev_t.h](https://github.com/torvalds/linux/blob/master/include/linux/kdev_t.h) 可以看到 `MKDEV` 巨集的定義，可以發現 `MKDEV` 就是將 `ma` 和 `mi` 進行一些 bitwise 的操作，對應上述程式最後一行也就是將 `major` 和 `minor` 合併成完整的設備號碼

#define MKDEV(ma,mi)	(((ma) << MINORBITS) | (mi))

最後可以使用以下命令查詢目前已被申請的設備號碼列表：

$ cat /proc/devices

**Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)**

首先在 [linux/bsearch.h](https://elixir.bootlin.com/linux/v6.8.7/source/include/linux/bsearch.h#L30) 可以看到這裡定義了一個 `bsearch` 的函式，其任務主要就是利用[二分搜尋演算法](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95)查找到目標的 `key`。

void *__inline_bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
{
	const char *pivot;
	int result;

	while (num > 0) {
		pivot = base + (num >> 1) * size;
		result = cmp(key, pivot);

		if (result == 0)
			return (void *)pivot;

		if (result > 0) {
			base = pivot + size;
			num--;
		}
		num >>= 1;
	}

	return NULL;
}

再來看到 `find_exported_symbol_in_section` ，首先要先利用 `!fsa->gplok` 判斷 `fsa` 和需要查找的 `syms` 是否有取得 [GPL授權條款](https://zh.wikipedia.org/zh-tw/GNU%E9%80%9A%E7%94%A8%E5%85%AC%E5%85%B1%E8%AE%B8%E5%8F%AF%E8%AF%81)，再來會利用上述提到的 `bsearch` 查找符號。

static bool find_exported_symbol_in_section(const struct symsearch *syms,
					    struct module *owner,
					    struct find_symbol_arg *fsa)
{
	struct kernel_symbol *sym;

	if (!fsa->gplok && syms->license == GPL_ONLY)
		return false;

	sym = bsearch(fsa->name, syms->start, syms->stop - syms->start,
			sizeof(struct kernel_symbol), cmp_name);
	if (!sym)
		return false;

	fsa->owner = owner;
	fsa->crc = symversion(syms->crcs, sym - syms->start);
	fsa->sym = sym;
	fsa->license = syms->license;

	return true;
}

最後在 [kernel/module/main.c](https://elixir.bootlin.com/linux/v6.8.7/source/kernel/module/main.c) 中定義 Linux 核心如何找到符號的過程，其中如果沒在內建的模組找到則會利用 `list_for_each_entry_rcu` 逐步走訪每個已載入的核心模組並且使用 `symsearch` 定義相關資訊，這邊會分成兩個類型的符號表是因為會需要根據當前模組的許可證是否為符合 GPL 授權條款，如果是則需要查找 GPL 的符號表，另外還要使用 `mod->state == MODULE_STATE_UNFORMED` 判斷模組的狀態是否能在被設定中，若成立則代表此模組的符號表不可使用。

bool find_symbol(struct find_symbol_arg *fsa)
{
	...

	for (i = 0; i < ARRAY_SIZE(arr); i++)
		if (find_exported_symbol_in_section(&arr[i], NULL, fsa))
			return true;

	list_for_each_entry_rcu(mod, &modules, list,
				lockdep_is_held(&module_mutex)) {
		struct symsearch arr[] = {
			{ mod->syms, mod->syms + mod->num_syms, mod->crcs,
			  NOT_GPL_ONLY },
			{ mod->gpl_syms, mod->gpl_syms + mod->num_gpl_syms,
			  mod->gpl_crcs,
			  GPL_ONLY },
		};

		if (mod->state == MODULE_STATE_UNFORMED)
			continue;

		for (i = 0; i < ARRAY_SIZE(arr); i++)
			if (find_exported_symbol_in_section(&arr[i], mod, fsa))
				return true;
	}

	pr_debug("Failed to find symbol %s\n", fsa->name);
	return false;
}

**MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)**
此巨集是定義模組的授權條款，若此模組是被授權的，則代表該模組可以使用為 GPL 的符號表，這是為了保護 GPL 軟體的自由，根據 [GNU General Public License](https://en.wikipedia.org/wiki/GNU_General_Public_License) 的內容，藉由此授權可以保護對核心做出貢獻的程式設計師。
> David A. Wheeler argues that the copyleft provided by the GPL was crucial to the success of Linux-based systems, giving the programmers who contributed to the kernel the assurance that their work would benefit the whole world and remain free, rather than being exploited by software companies that would not have to give anything back to the community.

**藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？**
* 操作系統呼叫
`uname`：獲取系統的資訊，包括系統名稱、記憶體版本等等
`finit_module`：允許從文件系統中的位置直接讀取模組，和 `init_module()` 類似，但是它是從 file descriptor 中讀取要加載的模組內容

`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](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format) 指的是一種文件格式，表示一個 executable binary file 或是 object file
* 記憶體管理系統呼叫
`mmap` ：用於在虛擬地址空間中創建一個新的映射給 process 使用，將一個文件映射進對應的記憶體空間
`munmap`：用於取消記憶體映射
`mprotect` ：用來修改記憶體的保護狀態
1. PROT_NONE：代表禁止訪問該記憶體區域
1. PROT_READ：代表允許該記憶體區域
1. PROT_WRITE：代表允許寫入該記憶體區域
1. PROT_EXEC：代表允許執行該記憶體區域
* 文件系統操作
`access`：檢查文件的訪問權限
1. R_OK：檢查文件讀取權限
1. W_OK：檢查文件寫入權限
1. X_OK：檢查文件執行權限
1. F_OK：檢查文件是否存在

`openat`：打開文件
`newfstatat` ：獲取文件的狀態
`read` ：讀取文件內容
`pread64`：從文件的指定 offset 位置開始讀取或寫入資料
`brk`:調整 data segment 結尾的大小，data segment 通常是屬於存放已經有明確初始化的 global 和 static 變數
`fcntl`：操作 file descriptor 屬性
`lseek`：改變文件 offset
* thread 控制系統相關
`set_tid_address`：設置指向 thread ID 的指針
`set_robust_list`：為 process 設置一個 robust 列表，用來儲存 thread 的資訊
`prlimit64`：設置資源限制

- [ ] 閱讀《[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)

- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明
- [ ] 研讀 [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 排程器互動？
- [ ] 解釋 `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+` 是否有速度的優勢？其弱點又是什麼？
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序