# 2024q1 Homework6 (integration)
contributed by < `aa860630` >
## 實驗環境
```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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 6220.80
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 5 MiB (4 instances)
L3: 8 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
$ uname -r
6.5.0-26-generic
```
## 自我檢查清單
- [ ] 研讀前述 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 核心的掛載，涉及哪些系統呼叫和子系統？
[insmod](https://man7.org/linux/man-pages/man8/insmod.8.html) 的主要功能是將特定的模組檔案載入到核心中。這個程序直接處理模組插入，因此並不會自動處理模組間的依賴關係。如果模組有未解決的依賴，insmod 可能會失敗。
#### 藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
```
$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7ffd6b299d08 /* 26 vars */) = 0
brk(NULL) = 0x5cafc9612000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffec5eccf40) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x78d3c2a8a000
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=71415, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 71415, PROT_READ, MAP_PRIVATE, 3, 0) = 0x78d3c2a78000
close(3) = 0
```
利用 strace 追蹤執行`insmod fibdrv.ko`的過程可以發現如 `close()`、`mmap()`、`read()`、`openat()`等函式 ：
* [openat()](https://linux.die.net/man/2/openat) :`openat()`系統調用的操作方式與`open()`完全相同,如果```pathname```中給出的路徑名是相對的，則它將相對於由檔案描述符`dirfd`指示的目錄進行編譯
```int openat(int dirfd, const char *pathname, int flags, mode_t mode);```
* [close()](https://linux.die.net/man/2/close) : `close()`關閉檔案描述符，使其不再指向任何文件並且可能被重新使用。
* [read()](https://linux.die.net/man/3/read):`read()`函數將嘗試從與打開的檔案描述符 fildes 相關的文件中讀取`nbyte`字節，並將其放入由`buf`指向的緩衝區。
```ssize_t read(int fildes, void *buf, size_t nbyte);```
* [mmap](https://linux.die.net/man/2/mmap) : `mmap()`會在呼叫進程的虛擬地址空間中創建一個新的映射。這個映射的起始地址由`addr`指定，而`length`參數指定了映射的長度。
```void *mmap(void *addr, size_t lengthint " prot ", int " flags , int fd, off_t offset);int munmap(void *addr, size_t length);```
- [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);
* Producer (生產者)：產生新資料，並將其插入到 fast_buf 中，以便快速存儲，或插入到 kfifo 中，以便後續傳輸或消費
* Consumer (消費者)：從 fast_buf 中讀取資料，然後進一步處理這些資料，可能是將其傳輸到 kfifo，或者進行其他操作
不管是生產者在產生新資料抑或是消費者在讀取資料，我們都不希望這個期間被干擾。舉例來說，當消費者在讀取資料時，我們希望操作是原子性的，不受其他操作的影響。這樣做的目的是避免數據競爭或緩衝區內資料的不一致。
在這個程式碼片段中，```consumer_lock```用於保護從```fast_buf```中讀取資料的操作。在```mutex_lock(&consumer_lock)```和```mutex_unlock(&consumer_lock)```之間，確保只有一個執行緒可以訪問```fast_buf```，避免同時讀取或修改帶來的競爭條件，```mutex_lock(&producer_lock)```與```mutex_unlock(&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);
}
```
- [ ] 探討 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) 的分析和效能評比方式
- [ ] 研讀 [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)
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;
Sign in with Wallet
Connect another wallet