# 2024q1 Homework6 (integration)

contributed by < `lintin528` >

## 自我檢查清單

- [ ] 研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
### 實驗環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 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
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             12
On-line CPU(s) list:                0-11
Thread(s) per core:                 2
Core(s) per socket:                 6
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              151
Model name:                         12th Gen Intel(R) Core(TM) i5-12400
Stepping:                           2
CPU MHz:                            2500.000
CPU max MHz:                        4400.0000
CPU min MHz:                        800.0000
BogoMIPS:                           4992.00
Virtualization:                     VT-x
L1d cache:                          288 KiB
L1i cache:                          192 KiB
L2 cache:                           7.5 MiB
L3 cache:                           18 MiB
NUMA node0 CPU(s):                  0-11

$ uname -r
5.15.0-101-generic

$ dpkg -L linux-headers-5.15.0-101-generic | grep "/lib/modules"
/lib/modules
/lib/modules/5.15.0-101-generic
/lib/modules/5.15.0-101-generic/build

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

看完這個教材後，剛開始有個粗淺的觀念：核心模組的掛載是為了在不重新編譯 kernel 的情況下加入新的功能。以下寫出各個節點所遇到的問題。

在第一步了解核心模組是如何被編譯的，在當前目錄新增了 `hello.c` 與 `Makefile` ，並且透過指令

完成編譯並產出 `.ko` 檔案，這邊可以看出是透過在 `/lib/modules/`uname -r`/build` 目錄下的 `Makefile` 裡描述編譯操作，但就產出一個疑問，為何我需要建立在當前目錄的 `Makefile` ?

目前想出的解釋只有需要指定目標模組 `obj-m` ，以及可以寫一些自定義的規則，所以才需要在當前目錄建立 `Makefile`。

之後以 `fibdrv` 為例去探討如何在 linux 核心中掛載模組，在看這部分內容時，其實一開始有點茫然，但看完之後可以大約總結為將每一個 `MODULE_XXX` 巨集分別透過 `__UNIQUE_ID` 產生一個獨特的名稱，並且從以下這一段

#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
.
.
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[]

可以看出來，產出的名稱其實就是 tag 所對應到的標籤，如 `author, license` 等等，並且在之後的 `__stringify(tag) "=" info` ，將其內容轉換為 `"操作 = 參數"` 的這個形式後，透過 
`__used __attribute__((section(".modinfo"), unused, aligned(1)))` ，在最後所產出的 ELF 格式 object file 中，將先前所生成的字串寫入對應的 `.modinfo` section。然後去觀察使用 `objdump` 產出的內容資訊

0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc

在 `.modinfo section` 裡面的其中一小段，第一段 `0010` 為此段訊息的十六進制 `offset` ，代表該段數據的偏移量，後面的 `76657273` 其實是對應到該段文字的 ASCII 碼 ， `76` 對應到 `v` ， `65` 對應到 `e` ，以此類推，至此就是編譯過程中是如何透過 `MODULE_XXX` 系列的巨集將 module 的資訊寫入此 object 檔案的過程。

下一部分在分析使用 `insmod` 時，是如何透過系統呼叫將編譯出的 kernel object (.ko) 檔案掛載進 linux 核心中，在最後的總結中可以看出 `insmod` 實際執行的系統呼叫中主要是透過

openat(AT_FDCWD, "/tmp/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
finit_module(3, "", 0) = 0

去配置記憶體空間以及加入初始化模組函數的起始位置，而細部觀察 `finit_module` 系統呼叫的實作，在最後呼叫 `load_module` ，且實際的記憶體配置就在裡面的 `layout_and_allocate` ，最後執行 `do_init_module` ，在其實作中的 `ret = fn();` 做實際的模組初始化，另外在讀取 `.ko` 檔案後事透過 `do_init_module` 函式實作中的 `ret = do_one_initcall(mod->init);`  去讀取透過 `module_init` 將使用者自己寫的 init funciton ，在此情況透過 `finit_module` 所執行的模組初始化就會更改為使用者自定義的 `init_fib_dev` 。

- [ ] 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;
- [ ] 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
- [ ] 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？
- [ ] 解釋 ksort 如何運用 CMWQ 達到並行的排序;