# 2024q1 Homework6 (integration)
contributed by < [`kkkkk1109`](https://github.com/kkkkk1109) >
## 安裝 Ubuntu-22.04
下載 [Ubuntu 22.04.4 LTS (Jammy Jellyfish)](https://releases.ubuntu.com/jammy/)
安裝完後在開機時卡住，[網站](https://blog.csdn.net/dair6/article/details/121151562) 說明可能是獨顯啟動時造成黑屏，因此前往 `recovery mode`，修改 `/etc/default/grub`
```diff
GRUB_DEFAULT=0
GRUB_TIMEOUT_STYLE=hidden
GRUB_TIMEOUT=10
GRUB_DISTRIBUTOR=`lsb_release -i -s 2> /dev/null || echo Debian`
--GRUB_CMDLINE_LINUX_DEFAULT="quiet splash "
++GRUB_CMDLINE_LINUX_DEFAULT="quiet splash nomodeset"
GRUB_CMDLINE_LINUX=""
```
即可完成安裝。
:::spoiler 開發環境
```shell
kkkk1109@kkkkk1109-GF65-Thin-10UE:~$ 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.
kkkkk1109@kkkkk1109-GF65-Thin-10UE:~$ 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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
CPU max MHz: 5000.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 12 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Retbleed: Mitigation; Enhanced IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer
sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS, IBPB conditional
, RSB filling, PBRSB-eIBRS SW sequence
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
:::
## 研讀 Linux 效能分析
## 閱讀[〈Linux 核心模組運作原理〉](https://hackmd.io/@sysprog/linux-kernel-module)
### 安裝模組範例
建立 `hello` 目錄並在其中建立 `Makefile` 及 `hello.c`
- [ ] hello.c
```cpp
#include <linux/init.h>
#include <linux/module.h>
MODULE_LICENSE("Dual BSD/GPL");
static int hello_init(void) {
printk(KERN_INFO "Hello, world\n");
return 0;
}
static void hello_exit(void)
{
printk(KERN_INFO "Goodbye, cruel world\n");
}
module_init(hello_init);
module_exit(hello_exit);
```
- [ ] makefile
```
obj-m := hello.o
clean:
rm -rf *.o *.ko *.mod.* *.symvers *.order *.mod.cmd *.mod
```
編譯核心模組的命令
```
make -C /lib/modules/`uname -r`/build M=`pwd` modules
```
參閱 [LKMPG](https://sysprog21.github.io/lkmpg/) 有對於 `printk` 的說明：
> 在 print macros 中，首先要學的是 `printk`，內部的參數通常為 `KERN_INFO` 或 `KERN_DEBUG` ， 可以用 `pr_info` 或 `pr_DEBUG` 來進行替換。
使用 `dmesg` 命令時，權限不足，無法查看 kernal 內部，使用 `sudo dmesg` 或 `sudo sysctl kernel.dmesg_restrict=0` 來關閉權限即可查看。
```shell
[ 41.465609] Hello, world
```
[dmesg](https://man7.org/linux/man-pages/man1/dmesg.1.html) 可用來查看 kernal 中的 [ring buffer](https://hackmd.io/@sysprog/concurrency-ringbuffer) 。 Ring buffer 是個固定容量、頭尾相連的緩衝區的資料結構，具有 FIFO 的特性，因此也可以視為一佇列，適合進行資料的快取。
```
[ 2049.701188] Hello, world
[ 2062.337822] Goodbye, cruel world
```
前面的單位為秒，紀錄著不同 message 的時間，可以配合不同命令來更改輸出的方式。
產生的模組為 `.ko `檔 (ko 即 kernel object 之意，對比使用者層級的 shared object），可以使用 `insmod` 來掛載模組。
```shell
$ sudo insmod fibdrv.ko
```
可以使用 `strace` 追蹤執行 `insmod fibdrv.ko` 的過程有哪些系統呼叫被執行
```shell
$ sudo strace insmod fibdrv.ko
```
於系統呼叫中，可以看到 `finit_module` 的存在，在先前的 v4.18 的 [`kernel/module.c`](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3785) 中，會 return 到 `load_module`
```cpp
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
...
return load_module(&info, uargs, flags);
}
```
`load_module` 為 Linux 核心為模組配置記憶體和載入模組相關資料的地方。
在 Linux kernel v6.8.5 [`kernel/module/main.c`](https://elixir.bootlin.com/linux/latest/source/kernel/module/main.c) 中， `finit_module` 系統呼叫的實作方式已變更，呼叫 `idempotent_init_module` 後在該函式當中還會呼叫 `init_module_from_file `，在 `init_module_from_file` 才真正呼叫到 `load_module`。
```cpp
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
int err;
struct fd f;
err = may_init_module();
if (err)
return err;
pr_debug("finit_module: fd=%d, uargs=%p, flags=%i\n", fd, uargs, flags);
if (flags & ~(MODULE_INIT_IGNORE_MODVERSIONS
|MODULE_INIT_IGNORE_VERMAGIC
|MODULE_INIT_COMPRESSED_FILE))
return -EINVAL;
f = fdget(fd);
err = idempotent_init_module(f.file, uargs, flags);
fdput(f);
return err;
}
```
`may_init_module` 檢查是否發生錯誤情況，`capable(CAP_SYS_MODULE)` 查看是否有權限去修改 kernal 中的 module，而 `modules_disabled` 則是查看目前是否禁止使用者掛載核心模組。
```cpp
static int may_init_module(void)
{
if (!capable(CAP_SYS_MODULE) || modules_disabled)
return -EPERM;
return 0;
}
```
## 閱讀《The Linux Kernel Module Programming Guide》
### 錯字？
**4.1**
> Kernel modules must have at least two functions: a "start" (initialization) function called init_module() which is called when the module is insmod **ed** into the kernel, and an "end" (cleanup) function called cleanup_module() which is called just before it is removed from the
### Ch4. Hello World
**4.1**
Kernal modules 至少要有開始和結束的函數，分別為 `init_module()` 和 `cleanup_module()`，不過在 kernel 2.3.13 版本後，可以自己對上述函式命名。
kernal module 需要 include `<linux/module.h>`，而如果要使用 `pr_alert()` 層級時，也就是，才需要 include `<linux/printk.h>`。
需要注意的事項
1. 使用 tab 而不使用 space
2. 在 print macros 中，首先要學的是 `printk`，內部的參數通常為 `KERN_INFO` 或 `KERN_DEBUG` ， 可以用 `pr_info` 或 `pr_DEBUG` 來進行替換
3. 使用 `kbuild` 來編譯，減少複雜的環境設置。
4.
**4.2**
可利用 `module_init` 和 `module_exit` 自己命名上述的 start 和 clean_up function 。
**4.3**
使用 `__init` 巨集的話，執行結束後便會釋放記憶體，但只對 built-in driver 有用， 對 loadable driver 沒有用。
**4.4**
需要加入 module license
**4.5**
若要輸入參數的話，使用 `module_param()` ，並設置成全域變數。 `module_param()` 需要三個參數，分別是 變數名稱、變數型態和sysfs 中對應檔案的權限
```
int myint = 3;
module_param(myint, int, 0);
```
若要傳入陣列，則需要使用 `module_param_array`，而其中第三參數則為計算陣列中第幾個元素的 `counter`，若不需要，也可以使用 `NULL`。
```
int myintarray[2];
module_param_array(myintarray, int, NULL, 0); /* not interested in count */
short myshortarray[4];
int count;
module_param_array(myshortarray, short, &count, 0); /* put count into "count" variable */
```
可以將各種 `set_param` 的第三個參數設成 `0000`，便可以在 `insmod` 時引入參數
```cpp
module_param(myshort, short, S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP);
MODULE_PARM_DESC(myshort, "A short integer");
module_param(myint, int, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
MODULE_PARM_DESC(myint, "An integer");
module_param(mylong, long, S_IRUSR);
MODULE_PARM_DESC(mylong, "A long integer");
module_param(mystring, charp, 0000);
MODULE_PARM_DESC(mystring, "A character string");
```
```shell
$ sudo insmod hello-5.ko mystring="bebop" myintarray=-1
$ sudo dmesg -t | tail -7
myshort is a short integer: 1
myint is an integer: 420
mylong is a long integer: 9999
mystring is a string: bebop
myintarray[0] = -1
myintarray[1] = 420
got 1 arguments for myintarray.
```
### Ch5. Preliminaries
**5.2**
使用 `strace` 可以查看運行程式時做了哪些系統呼叫
**5.3**
Kernal 的存在是為了維護各個程式使用資源時可以按照層級的方式來進行，避免造成相互競爭。
在 Unix 分層兩個層級： `ring-0 (supervisor mode)` 和 `lowest ring(user mode)`
我們在 user mode 使用 libary function ， 而 libary function 再呼叫各個 system calls 如我們在 `strace` 中所看到的，在完成任務後回到使用者模式。
**5.4**
避免變數衝突，可以使用 `static` 或加入一些 prefix 來宣告變數，或者是可以於 kernal 中註冊。
**5.5**
當建立一個 process ， Kernal 會為它創造一個記憶體空間來執行程式碼，而 process 一般無法存取另一個 process 的記憶體空間。
Kernal 也有自己的記憶體空間，由於 module 會被動態地掛載或卸載，因此兩者會是共享同個 code space ，也因此當 module 報錯時， Kernal 也會一起報錯。
### Ch6. Character Device drivers
**6.1**
File operation 定義了各種對於 device 的操作。
**6.3**
透過在 `/dev` 底下的 device files 可以去存取 device，只要是從 `dev` 中生成的 device file 便可以放置在任何目錄中。
使用 `register_chrdev` 對 Kernal 註冊 device ，為了避免和其他設備的 major number 重複，可以傳遞 0 給 Kernal 獲得尚未使用的編號，也可以使用 cdev 界面來幫助存取 device。
**6.5**
在多個 thread 的環境中，若同時存取同個地址，可能會造成 race condition ，可以使用 atmoic 指令來進行。
### Ch7. The /proc File System
/proc file system 原先是用來讓 Kernal 和 Kernal module 來傳送資料給 process ，而現在是 Kernal 報告其目錄下的訊息。
我們也可以使用 /proc 像 module device 的方式，使用 `init_function` 和 `cleanup_function` 來進行讀取。
**7.1**
`proc_ops` 在較舊的版本中，使用了 `file_operation` 來定義 /proc ，導致定義了不必要的成員。現今的 `proc_ops` 簡化了許多操作，並優化了 /proc 的空間及操作。
**7.2**
示範如何進行寫入 /proc file
**7.3**
使用 `inode` 來管理 /proc file， file operation 是對於檔案內部的操作，而 inode 是如何處理這些 file 。
在 /proc 中，每當註冊新的 file 時，便會使用 `inode_operation` 來訪問和指向文件。可以使用 `module_permission` 來查看 process 是否有權限對 /proc 進行操作。
**7.4**
可以使用 `seq_file` 的 API 來幫助我們編寫 /proc 文件(還不太懂)
### Ch8. sysfs: Interacting with your module
sysfs 可以讓我們在 userspace 來查看或設定 module 的狀態或參數
```shell
ls -l /sys
```
可以使用 `attribute` 來讓 sysfs 來對定義的 file 進行操作。
### Ch9. Talking To Device Files
Devices file 可以對應到一個物理上的 device，因此 Kernal 也需要一個機制來和其互動，如 `device_write` ，可以使用 `ioctl` 來完成。
### Ch10. System Calls
目前都是以 Kernal 定義好的機制來註冊 /proc file 和 device ，但如果要做特殊的事的話，就必須要謹慎小心處理。
通常 process 無法訪問 Kernal ，作為一種保護。但 system call 可以作為例外，當 process 對特定的暫存器設定值，而可以跳轉到 kernal 中事先定義好的位置。
在 `sys_call_table` 中，定義了各種 system call 要跳轉到不同的 Kernal function ，我們也可以更改成自己想要進行的行為，但在 module 結束後要記得回覆原狀。
### Ch11. Blocking Process and threads
當 Kernal 在處理其他 process ，而有新的 process 要運行時，可以先將此 process 睡眠，當有空時再喚醒此 process。
(尚未看完)
### Ch12. Avoiding Collisions and Deadlocks
**12.1**
mutex的用法。
**12.2**
spinlock 會 100% 佔用 CPU 的資源，因此應該使用在教短的 critical section ，並且要注意擁有 lock 的 process 必須在 sleep 前釋放 lock ，避免造成系統崩潰。
:::info
不太懂 `example_spinlock_dynamic` 和 `example_spinlock_static` 差了一個 `spin_lock_init(&sl_dynamic);` 有什麼樣的差異
:::
`static`
**12.3**
R/W lock ，不能出現同時讀取又寫入的情況。若發生可能會被中斷的情況，則使用 `read_unlock_irqrestore(&myrwlock, flags)`，不會被中斷的話使用較簡單的 `read_lock(&myrwlock)` 即可。
**12.4**
使用 atomic ，這樣就能避免出現錯誤。
## kfifo
## 探討 各種排序的比較
## 研讀 CMWQ (Concurrency Managed Workqueue) 文件
## 解釋 xoroshiro128+ 的原理
## 解釋 ksort 如何運用 CMWQ 達到並行的排序
Sign in with Wallet
Connect another wallet