# 2019q1 Homework2 (fibdrv)
contributed by < `tfliao` >
## Environment
```shell
$ uname -a
Linux debian-nk 4.19.0-2-amd64 #1 SMP Debian 4.19.16-1 (2019-01-17) x86_64 GNU/Linux
$ lsb_release -a
No LSB modules are available.
Distributor ID: Debian
Description: Debian GNU/Linux buster/sid
Release: testing
Codename: buster
```
## 自我檢查清單
- [x] MODULE_XXX 巨集做了什麼事
[`MODULE_LICENSE(_license)`](https://elixir.bootlin.com/linux/v4.19.16/source/include/linux/module.h#L200) -> `MODULE_INFO(tag, info)` -> [`__MODULE_INFO(tag, name, info)`](https://elixir.bootlin.com/linux/v4.19.16/source/include/linux/moduleparam.h#L21)
以`MODULE_LICENSE("Dual MIT/GPL")`作為例子，MACRO最後會變成`__MODULE_INFO("license", "license", "Dual MIT/GPL")`，並且展開為下列程式碼
```
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
概念上就是
1. 宣告一個 static 的常數字串 (`static const char[]`)
2. 字串內容是 "license=Dual MIT/GPL" (`__stringify(tag) "=" info`)
3. 放在.modinfo 這個 section (`__attribute__((section(".modinfo")))`)
4. 變數名稱不重要所以請 compiler 隨便長一個 (`__UNIQUE_ID(name)`)
5. 為了避免 compiler 浪費空間去做 padding ，所以請他對齊一個位元(`__attribute__((aligned(1)))`)
6. 最後是跟 linker 說不要把這個變數當成沒用的東西 (`__attribute__((unused))` 和 [`__used`](https://elixir.bootlin.com/linux/v4.19.16/source/tools/include/linux/compiler.h#L54)
可使用`readelf` dump `.modinfo` 內的值
```
$ readelf fibdrv.ko -p .modinfo
String dump of section '.modinfo':
[ 0] version=0.1
[ c] description=Fibonacci engine driver
[ 30] author=National Cheng Kung University, Taiwan
[ 5e] license=Dual MIT/GPL
[ 78] srcversion=24DC5FB7E7608AF16B0CC1F
[ a0] depends=
[ a9] retpoline=Y
[ b5] name=fibdrv
[ c1] vermagic=4.19.0-2-amd64 SMP mod_unload modversions
```
- [ ] insmod
遇到問題先找source code，在 `man insmod` 的輸出左下角，可以知道 `insmod` 放在 `kmod`這個 package 內，從 [這裡](http://snapshot.debian.org/package/kmod/25-2/) 可以找到原始碼，在 `tools/insmod.c` 裡面，可以看到 `insmod` 主要就做幾件事
```
135 ctx = kmod_new(NULL, &null_config);
136 if (!ctx) {
137 ERR("kmod_new() failed!\n");
138 free(opts);
139 return EXIT_FAILURE;
140 }
141
142 err = kmod_module_new_from_path(ctx, filename, &mod);
143 if (err < 0) {
144 ERR("could not load module %s: %s\n", filename,
145 strerror(-err));
146 goto end;
147 }
148
149 err = kmod_module_insert_module(mod, flags, opts);
150 if (err < 0) {
151 ERR("could not insert module %s: %s\n", filename,
152 mod_strerror(-err));
153 }
```
* `kmod_new`
* 建立 `struct kmod_ctx`，做為後續操做 `kmod` 系列函數用的物件
* `kmod_module_new_from_path`
* 把路徑轉換為module name，檢查是否已經存在於kernel中，若都沒問題則用 `kmod_module_new` 建立 `struct kmod_module`，並記錄 name 和 path
* `kmod_module_insert_module`
* 利用前面產生 `struct kmod_module` 內的路徑，把 elf 檔案讀進 memory 中 (同樣存放在 `kmod_module` 結構內)
* 這邊有個有趣的點，kernel module在編譯的時候，會把參照的kernel版本以vermagic的形式存起來 (e.g. 前面 dump 出來的 `vermagic=4.19.0-2-amd64 SMP mod_unload modversions`)，在 insert 時檢查是否與現在的 kernel 相符，避免插錯 module 把系統搞壞；如果有下 `KMOD_INSERT_FORCE_VERMAGIC` 這個 flag，在 insert 之前會把 `vermagic` 移除來繞過 kernel 的檢查
* 最後從 elf 檔案中取得檔案大小，透過 `init_module(module_image, size, param)` 請 kernel 把 module_image 載入到 kernel 中
- [ ] init_module
> 終於回到kernel space了 感動
`init_module` 是一個 system call，其實作定義在[kernel/module.c](https://elixir.bootlin.com/linux/v4.19.26/source/kernel/module.c#L3842)，在確認當下的執行的 kernel 有支援 module 能力後，把 module_image 用 `copy_module_from_user` 複製到 kernel space，最後透過 `load_module` 載入 module_image
[`load_module`](https://elixir.bootlin.com/linux/v4.19.26/source/kernel/module.c#L3644) 開始會先跑一堆檢查，然後把 module imge 載入到 kernel 內，最後在 call do_init_module 執行 module 設定的進入點
* `elf_header_check`
* 檢查elf的格式
* `setup_load_info`
* 讀取 .modinfo section 內的值，把 mod 指到 data 內對應的位置 ... etc
* `blacklisted`
* 檢查這個 module 是不是在黑名單內，有的話就不要 load
* `module_sig_check`
* 檢查 module 的 signature
* `rewrite_section_headers`
* 把 elf 的 section header 指到 kernel space 的 address
* 如果 kernel 不想支援 module unload，把 .exit 幹掉 XDDD
* `check_modstruct_version`
* 檢查 modversion
* `layout_and_allocate`
* 調整 section/ symbol table 的 layout，並且把 module 移動到新的記憶體位置 (而非 info 的一部份)
* `add_unformed_module`
* 檢查是不是有同名的 module，若沒有則把這個 module 串到 list 中
* `add_taint_module`
* 若 module 的 signature 不正確，會把 kernel 標記成 (taint)，基本上 tainted kernel 出現的 bug 會被社群無視，就是個誰知道你的 kernel 被幹過什麼事情的概念 XD
* `module_unload_init`
* 設定 refcount 以及追蹤 `struct module_use` 的 linked-list
* `find_module_sections`
* 把各個 section 的位置存到 `struct module` 結構的變數內
* `check_module_license_and_versions`
* 檢查 module 使用的 license，必要時標上taint
* `setup_modinfo`
* 把用 MODULE_XXX 寫入的資訊存到 `struct module` 結構的變數內
* `simplify_symbols`
* 試圖解出 symbol table 內的 undefine，若有 undefine 則會 load 失敗
* 若從其他 module 中找到 symbol，會產生 `struct module_use` 紀錄 module 之間的dependency
* `apply_relocations`
* 根據 section type，調整存放在記憶體內的位置
* `post_relocation`
* 調整完位置後，把 module 內的 symbol 加入 kallsym
* `flush_module_icache`
* flush module 使用的 instruction cache
* `strndup_user`
* 把 module arguments 複製到 kernel space
* `complete_formation`
* 檢查重複的 symbol，狀態標成 COMING
* `mod_sysfs_setup`
* 產生 module 對應的 sysfs 目錄
* `do_init_module`
* 到這裡就會呼叫 `struct module` 內的 init 函數
但是奇怪的地方是，在 kernel 裡面沒有人去設定 `struct module` 中的 `init` 函數，把 [`module_init`](https://elixir.bootlin.com/linux/v4.19.26/source/include/linux/module.h#L130) 解開也只是增加一個叫 `init_module` 的 alias 指向我們的 `init_dib_dev`，最後在編譯過程產生的 `fibdrv.mod.c` 找到答案
> 這部分是參考 cjwind 大大的[共筆](https://hackmd.io/s/SkW25-2UV)，才知道要去找fibdrv.mod.c
```
11 __visible struct module __this_module
12 __attribute__((section(".gnu.linkonce.this_module"))) = {
13 .name = KBUILD_MODNAME,
14 .init = init_module,
15 #ifdef CONFIG_MODULE_UNLOAD
16 .exit = cleanup_module,
17 #endif
18 .arch = MODULE_ARCH_INIT,
19 };
```
這裡宣告一個 `struct module` 的變數，並且把 `init_module` 存到 `init` 的欄位內，配上 `module_init` 設定的 alias ，我們就建立好一個 `struct module` ，內含的 `init` 直接指向 `init_fib_drv`
再回頭看 [`setup_load_info`](https://elixir.bootlin.com/linux/v4.19.26/source/kernel/module.c#L2947)，有一段尋找 `.gnu.linkonce.this_module` 的 section，並且 assign 到 `info->mod` 的邏輯，在這裡就已經把 `init` 設定到我們的 `init_fib_drv` 上了
- [ ] module (?)
- [ ] ktime
- [ ] clock_gettime
- [ ] VFS
- [ ] mutex
測試前先猜測， `mutex` 僅有開檔的時候被 lock，關檔(或是module unload)的時候被 unlock ，這確保了同時僅會有一個 userspace 的程序在操作 `/dev/fibonacci`，並且這個 module 也只有這一個介面，等於一次僅會有一個程序在使用這個 module。
==猜測==
若是把 `mutex` 移除，以這個 module 來說應該不會炸裂 XD
在多執行緒的情況下，假設每個執行緒不共用開啟的檔案，則各自開啟的檔案應有獨立的 fd ，各自的，不該出現問題；但若是公用開啟的檔案則在 seek 和 read 之間，pos可能被改變，造成 read 到的值不是期待的結果，這個問題就算沒有移除 mutex 也會發生。
若是多個程序同時開啟檔案，狀況應該與單一程序多執行緒的結果相同
==結果==
修改程式碼於 [remove_mutex](https://github.com/tfliao/fibdrv/tree/remove_mutex)
同時執行10個client，根據 `dmesg` 的訊息，可以看到 `/dev/fibonacci` 被同時開啟多次，並且十個 client 的 log 完全相符
* 此處可修改 client 測試是否為獨立的 `struct file` (但是懶得弄XD)
```
$ for i in `seq 1 10`; do sudo ./client > /tmp/log.$i & done
[305276.901764] fibonacci opened by 19263
[305276.902706] fibonacci closed by 19263
[305276.910405] fibonacci opened by 19267
[305276.912089] fibonacci closed by 19267
[305276.915322] fibonacci opened by 19270
[305276.916426] fibonacci closed by 19270
[305276.917330] fibonacci opened by 19268
[305276.918249] fibonacci closed by 19268
[305276.920695] fibonacci opened by 19273
[305276.921104] fibonacci opened by 19272
[305276.921658] fibonacci closed by 19273
[305276.922018] fibonacci closed by 19272
[305276.932219] fibonacci opened by 19275
[305276.933983] fibonacci opened by 19274
[305276.935930] fibonacci opened by 19277
[305276.936539] fibonacci opened by 19276
[305276.936893] fibonacci closed by 19277
[305276.937461] fibonacci closed by 19276
[305276.938267] fibonacci closed by 19275
[305276.938791] fibonacci closed by 19274
$ for i in `seq 2 10`; do diff /tmp/log.1 /tmp/log.$i ; done
```
==結論==
這個 module 擋在開檔根本沒什麼用XD
但也是因為這是教學用途的 module，功能較為單純，若這個 module 會把計算數列的時間存在 module 內，或是透過 write 決定要計算的fib，這時就比較需要 lock 來避免中途被改內容。
- [ ] ffs
## fibdrv 修改
### 使用 ktime 執行時間
[`ktime`](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 系列 API 在最基礎的使用上相當直覺，在需要測量程式碼前後用 `ktime_get` 取得當下的時間，相減就可以知道這過程中經過多少時間
```
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
ssize_t r;
#ifdef ENABLE_STAT
ktime_t begin = ktime_get();
#endif /* ENABLE_STAT */
r = fib_sequence(*offset);
#ifdef ENABLE_STAT
struct timespec64 ts = ktime_to_timespec64(ktime_get() - begin);
printk(KERN_INFO "fib_sequence(%lld) takes %lld.%09ld seconds\n",
(long long) *offset, (long long) ts.tv_sec, (long) ts.tv_nsec);
#endif /* ENABLE_STAT */
return r;
}
```
用 `printk` 把算出來的結果直接丟到 console 輸出
```
$ sudo ./client
[93220.012408] fib_sequence(0) takes 0.000000053 seconds
[93220.012419] fib_sequence(1) takes 0.000000044 seconds
[93220.012427] fib_sequence(2) takes 0.000000060 seconds
[93220.012436] fib_sequence(3) takes 0.000000056 seconds
[93220.012445] fib_sequence(4) takes 0.000000058 seconds
[93220.012454] fib_sequence(5) takes 0.000000073 seconds
[93220.012462] fib_sequence(6) takes 0.000000064 seconds
[93220.012474] fib_sequence(7) takes 0.000000071 seconds
[93220.012484] fib_sequence(8) takes 0.000000068 seconds
[93220.012492] fib_sequence(9) takes 0.000000072 seconds
[93220.012501] fib_sequence(10) takes 0.000000071 seconds
[93220.012510] fib_sequence(11) takes 0.000000074 seconds
...
```
### 使用 sysfs
用 `printk` 固然方便，但執行時間容易因為各種因素而不穩定，通常我們會執行多次來觀察各種統計數值，此時用 `printk` 作為介面就不會是個好選擇。
此時我們可以使用 kernel 的 sysfs 介面，透過 sysfs 介面，我們可以宣告 `show` 和 `store` 介面來提供讀寫操作。要產生一個 sysfs entry 還挺多東西要寫的，好在 kernel 有提供 [`sample`](https://elixir.bootlin.com/linux/v4.19.26/source/samples/kobject/kobject-example.c) ，幫我們省掉去 stack overflow 找哪段 code 可以抄的時間。
我建立了兩個介面， `result` 用來讀取目前的統計資訊 (為了之後用其他成切資料方便，輸出格式為: `n : ns / cnt`)， `reset` 則是清空當下的統計，修改的程式碼在 [commit](https://github.com/tfliao/fibdrv/commit/bdd47fa3a76280fe1cecbca807d00515012dcf19) 。
```
$ ll /sys/kernel/fibonacci/*
-rw-r--r-- 1 root root 4096 Mar 17 01:05 /sys/kernel/fibonacci/reset
-r--r--r-- 1 root root 4096 Mar 17 01:05 /sys/kernel/fibonacci/result
$ sudo ./client > /dev/null
$ cat /sys/kernel/fibonacci/result
0: 88 / 2
1: 74 / 2
2: 95 / 2
3: 100 / 2
4: 99 / 2
5: 109 / 2
6: 123 / 2
7: 118 / 2
8: 124 / 2
9: 129 / 2
10: 131 / 2
...
92: 3428 / 18
```
## CHECK LIST
- [ ] 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
- [ ] 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
- [ ] 在 Linux 核心模組中，可用 ktime 系列的 API
- [ ] 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API
- [ ] 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
- [ ] 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
- [ ] 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
- [ ] 逐步最佳化 Fibonacci 的執行時間，引入 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 提到的策略，並善用 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，過程中都要充分量化
==自我檢查清單==
- [x] 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？
- [x]`insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
- [x] 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
- [x] 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
- [ ] 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)
- [ ] 查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
- [ ] [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
- [ ] `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
- [x] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
- [ ] 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說
Sign in with Wallet
Connect another wallet