# F03: fibdrv
contributed by < `afcidk` >
* [F03: fibdrv](https://hackmd.io/s/SJ2DKLZ8E)
## 自我檢查清單
### 1. 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
`MODULE_LICENSE` 一類的巨集被定義在 [linux/module.h](https://github.com/torvalds/linux/blob/64c0133eb88a3b0c11c42580a520fe78b71b3932/include/linux/module.h) 底下。繼續追下去，會發現所有巨集最後都會被展開成 `__MODULE_INFO`([linux/moduleparam.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/moduleparam.h#L21))。
節錄 moduleparam.h 裏面關於 `__MODULE_INFO` 的程式碼
```clike=
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
1. `__UNIQUE_ID` 會根據參數產生一個不重複的名字（參考[linux/compiler.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler.h#L161)），其中使用到的技術是利用巨集中的 `##` 來將兩個引數合併成一個新的字串。
2. 透過 `__attribute__` 關鍵字告訴編譯器，這段訊息
1. 要被放在 `.modinfo` 段
2. 應該不會被程式使用到，所以不要產生警告訊息
3. 最小的對齊格式需要是 1 bit
3. 在 [linux/stringfy.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/stringify.h) 裡頭，我們可以看到 `__stringify` 的目的是為了把引數轉換成字串形式。以 `MODULE_LICENSE(Dual MIT/GPL)` 為例，被展開後的 `__stringify(tag) "=" info` 會是 `"license = Dual MIT/GPL"` 字串。
總結這部份，`MODULE_XXX` 系列的巨集在最後都會被轉變成
```clike
static const char 獨一無二的變數[] = "操作 = 參數"
```
再放到 `.modinfo` 區段中。
:::info
舉兩個 `fibdrv.c` 的例子
* `MODULE_VERSION("0.1")` 會變成 `static const char xxx[] = "version = 0.1"`
* `MODULE_DESCRIPTION("Fibonacci engine driver")` 會變成 `static const char yyy[] = "description = Fibonacci engine driver"`
:::
在編譯完 kernel module 後，我們可以確認那些資訊是不是真的被放到 `.modinfo` 區段中了。
```clike
$ readelf -x .modinfo fibdrv.ko
```
得到結果
```bash
Hex dump of section '.modinfo':
0x00000000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0x00000010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0x00000020 6920656e 67696e65 20647269 76657200 i engine driver.
0x00000030 61757468 6f723d4e 6174696f 6e616c20 author=National
0x00000040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0x00000050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0x00000060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
0x00000070 504c0000 00000000 73726376 65727369 PL......srcversi
0x00000080 6f6e3d35 39423145 39304633 32394543 on=59B1E90F329EC
0x00000090 39353539 39443835 45320000 00000000 95599D85E2......
0x000000a0 64657065 6e64733d 00726574 706f6c69 depends=.retpoli
0x000000b0 6e653d59 006e616d 653d6669 62647276 ne=Y.name=fibdrv
0x000000c0 00766572 6d616769 633d342e 31352e30 .vermagic=4.15.0
0x000000d0 2d34322d 67656e65 72696320 534d5020 -42-generic SMP
0x000000e0 6d6f645f 756e6c6f 61642000 mod_unload .
```
### 2. 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
在 [linux/module.h](https://elixir.bootlin.com/linux/latest/source/include/linux/module.h#L128) 裡頭，我們可以發現到
```clike=128
/* Each module must use one module_init(). */
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __copy(initfn) __attribute__((alias(#initfn)));
```
:::warning
需要注意到查的內容是不是有被 `ifdef` 之類的指示詞擋住，可能會有重複的名稱，但是作用不同！
:::
展開後，我原本預期應該要達到下面的程式碼
```clike
static inline initcall_t __maybe_unused __inittest(void) {return init_fib_dev; }
int init_module(void) __copy(init_fib_dev) __attribute__((alias("init_fib_dev")));
```
但是查看了預處理過後的程式碼，卻發現展開後長這樣
```clike
static initcall_t __initcall_init_fib_dev6 \
__used __attribute__((__section__(".initcall" "6" ".init"))) = init_fib_dev;;;
```
:::info
可以透過 `gcc -E fibdrv.c -I$TREE/include -I$TREE/arch/x86/include -I$TREE/include/uapi` 看到經過預處理後的程式碼，`$TREE` 指的是 kernel tree 的位置，在這邊是 `/usr/src/linux-headers-$(uname -r)`
註：這樣做會有問題，參考後續的筆記
參考 [Stack Overflow - Kernel module source file after preprocessing](https://stackoverflow.com/questions/21177935/kernel-module-source-file-after-preprocessing)
:::
事實上，在 linux/module.h 裏面，有兩個地方定義了 `module_init`，分別是
有定義 `MODULE` 的
```clike
#ifndef MODULE
#define module_init(x) __initcall(x);
```
還有沒定義 `MODULE` 的
```clike
#else /* MODULE */
...
/* Each module must use one module_init(). */
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __copy(initfn) __attribute__((alias(#initfn)));
```
不了解的地方是，我們得到預處理過後的結果是選用沒定義 `MODULE` 的 `module_init(x)` ，也就是之後會繼續展開 `__initcall(x)`。
`__initcall(x)` 巨集被定義在 [linux/init.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/init.h)
```clike
#define __initcall(fn) device_initcall(fn)`
```
`device_initcall` 展開成 `__define_initcall(fn, 6)`，最後會變成我們預處理看到的結果。
:::info
我在想是因為我們用 gcc -E 指令的時候，並不是要把他編譯成 kernel module，所以展開的時候才會朝向 `ifndef MODULE` 繼續往下做。
如果是這樣的話，現在應該要找個方法在把編譯成 kernel moudle 時把預處理後的檔案留著對照看看。
:::
:::success
後來我多加了 `EXTRA_CFLAGS` 到指令中，
`$(MAKE) -C $(KDIR) M=$(PWD) modules EXTRA_CFLAGS=-save-temps`
這樣我們生成的中間檔案就不會被移除，可以在 `KDIR` (`/lib/modules/$(shell uname -r)/build`) 裏面找到我們想要的 `fibdrv.i`
:::
最後展開的巨集
```clike
static inline __attribute__((unused))
__attribute__((no_instrument_function))
initcall_t __attribute__((unused))
__inittest(void) { return init_fib_dev; }
int init_module(void) __attribute__((alias("init_fib_dev")));;
```
再來我們解讀一下這邊做了什麼事，
首先是第一段 `static inline ....`，這邊用了一個小技巧讓我們可以在編譯時期就知道傳入的 function pointer 是不是合法的。我們回傳的 `return init_fib_dev`，他的資料型態必須要和 `initcall_t` 相同，否則編譯器會報錯。
> 這種作法和 [BUG_ON](https://kernelnewbies.org/FAQ/BUG) 和 C++ 的 [static assertion](https://en.cppreference.com/w/cpp/language/static_assert) 有點像。
再來是 [init_module](http://man7.org/linux/man-pages/man2/init_module.2.html)，我們知道這個**系統呼叫**讓我們把一個 ELF image 載入到 kernel space，而在最後一行 `int init_module(void) __attribute__((alias("init_fib_dev")))` 的目的是為了替 `init_module` 取一個別名。我寫了一個[範例程式](https://gist.github.com/afcidk/fe227edd29bb6a3674e9d778fc171840)演示這麼做的結果，如果不太懂 `alias` 的用途可以跑跑看。
在這裡之所以要這樣做，是因為在前面的地方有寫到
```clike
/* These are either module local, or the kernel's dummy ones. */
extern int init_module(void);
```
這行告訴我們說，有 `init_module` 可以使用，但是不在這個地方實作。那實作在什麼地方呢？就是我們寫的 `init_fib_dev`，因為我們把 `init_module` 取了一個別名叫作 `init_fib_dev`。
總結一下，`module_init` 巨集幫我們做了兩件事
1. 檢查傳入的函式，回傳值是否正確
2. 把 `init_module` 和傳入的函式關聯起來，因為 `insmod` 指令實作裏面會呼叫 `init_module`。如此一來呼叫 `init_module` 就等同於呼叫我們自己寫的函式。
### 5. 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
[ktime](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 讓 device driver 可以得到時間的資訊。
既然 ktime 可以讓我們在 kernel space 得到時間，很直覺的可以想到要應用在測試程式的速度上。在這個部份我找了 MTD（Memory Technology Device）測試讀寫速度的使用案例 [mtd/tests/speedtest.c](https://github.com/torvalds/linux/blob/master/drivers/mtd/tests/speedtest.c)
MTD 是在 linux 系統中，用來和快閃記憶體溝通的一種 device file。
需要注意到的是，不能把隨身碟、記憶卡等同樣使用快閃記憶體儲存的裝置和 MTD 搞混。他們使用的雖然同樣是 flash，但是是透過 FTL (Flash Translation Layer)系統溝通的，稱作 block device。
| block device | MTD |
| -------- | -------- |
| 由 sector 組成 | 由 eraseblocks 組成 |
| 一個 sector 單位小（512/1024 bytes) | 一個 eraseblock 單位大（通常是128 KiB）|
|read/write|read/write/erase|
|硬體會隱藏 bad sector|bad eraseblock 不會被隱藏，需要在軟體方面手動處理|
|Sectors are devoid of wear-out property *註| Eraseblocks 大概在 $10^3$~$10^5$ 次 erase 後就會壞掉了|
> *註：我不太懂那邊寫的到底是什麼意思，不會壞掉？QQ
節錄程式碼中計算速度的部份
```clike=297
pr_info("testing eraseblock read speed\n");
start_timing();
for (i = 0; i < ebcnt; ++i) {
if (bbt[i]) // bbt 代表的是 bad eraseblock，
// 因為 bad eraseblock 不會被隱藏起來，
// 所以需要跳過他
continue;
err = read_eraseblock(i);
if (err)
goto out;
err = mtdtest_relax();
if (err)
goto out;
}
stop_timing();
speed = calc_speed();
pr_info("eraseblock read speed is %ld KiB/s\n", speed);
```
看起來蠻直觀的，除了 `mtdtest_relax`
```clike
static inline int mtdtest_relax(void)
{
cond_resched();
if (signal_pending(current)) {
pr_info("aborting test due to pending signal!\n");
return -EINTR;
}
return 0;
}
```
`mtdtest_relax` 的作用是把 cpu 讓出來給其他 process 用，不過我不太確定為什麼這邊需要做這件事，也許是怕沒有把 kernel preemption 打開，防止 kernel 一直佔用著 CPU。
> Reference: [linux-mtd](http://www.linux-mtd.infradead.org/faq/general.html)
### 6. clock_gettime 和 High Resolution Timers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
根據 [High Resolution Timers Wiki 頁面](https://elinux.org/High_Resolution_Timers)，我們可以知道 HRT 是一個用來實作 [POSIX 1003.1b](http://www.open-std.org/jtc1/sc22/open/n4217.pdf) Section 14 (Clocks and Timers) API 的專案。
> POSIX 1003.1b 是 1993 年被制定出來的
在 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 可以看到上面寫說遵守的是 POSIX.1-2001 標準，是在 2001 年被制定出來的。
另外在說明頁面內，可以注意到 `clock_gettime` 一類的函式需要使用到 POSIX 1993 以後的特徵，而那正是 POSIX 1003.1b。
```
clock_getres(), clock_gettime(), clock_settime():
_POSIX_C_SOURCE >= 199309L
```
### 7. fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
Linux 的 device 分成 character device (cdev) 還有 block device (bdev)。Char device 的傳輸單位是一個字元，而 block device 的單位則是一個 block。常見的 character device 例如 Serial port，block device 像是硬碟。
另外在 device driver 上，根據不同的實作我們可以分成 physical device driver 還有 virtual device driver。可以說 physical device driver 負責向下和硬體溝通，而 virtual device driver 負責和 kernel VFS 層溝通。
透過 kernel 提供的 API，我們可以讓 virtual device（kernel space） 和 userspace 溝通。
我們需要定義一些 file operations，再註冊寫好的 driver。如此一來就可以在 userspace 使用到我們定義好的 system call。
在 `fibdrv.c` 中，有 file operations 的定義，可以看到這個部份我們告訴系統，當需要 read syscall 的時候，就執行 `fib_read`，當需要 open syscall 的時候，就執行 `fib_open`。
```clike
const struct file_operations fib_fops = {
.owner = THIS_MODULE,
.read = fib_read,
.write = fib_write,
.open = fib_open,
.release = fib_release,
.llseek = fib_device_lseek,
};
```
userspace 的方面，我們可以直接對註冊好的 device driver 操作。舉例來說，如果我們寫了 `open('....', '....')`，對應到 kernel space 的動作就會是 `fib_open` 這個函式。
提到和 device 溝通，我最直覺想到的是 [tty](https://en.wikipedia.org/wiki/Tty_\(unix\))。在 [tty_io.c](https://github.com/torvalds/linux/blob/master/drivers/tty/tty_io.c) 裡頭，我們可以看到他也定義了各種 file operations。
```clike
static const struct file_operations tty_fops = {
.llseek = no_llseek,
.read = tty_read,
.write = tty_write,
.poll = tty_poll,
.unlocked_ioctl = tty_ioctl,
.compat_ioctl = tty_compat_ioctl,
.open = tty_open,
.release = tty_release,
.fasync = tty_fasync,
.show_fdinfo = tty_show_fdinfo,
};
```
### 8. 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
觀察程式碼可以發現，互斥鎖只有在 `open` syscall 中使用到，這是因為我們不希望同時有兩個不同的地方使用這個 device。當我們的 device 需要根據輸入 (write) 得到對應的輸出 (read) 時，這個機制就會顯得非常重要。
我修改了 fibdrv.c，他會註冊一個 character device，並且提供 read/write 操作。在 write 的時候，我們可以把一個字串丟到 kernel space 存起來，並且在 read 的時候讀回來。
在 user space 的程式中，我們應該要確保寫和讀會得到相同的結果。但是在 multitasking 的例子中，我們卻可能得到錯誤的結果。
這是其中一種輸出
```
2: Writing bbb to kernel
5: Writing eee to kernel
6: Writing fff to kernel
1: Writing aaa to kernel
3: Writing CCC to kernel
4: Writing ddd to kernel
7: Writing ggg to kernel
2: Received ggg from kernel (Should receive bbb)
3: Received ggg from kernel (Should receive CCC)
1: Received ggg from kernel (Should receive aaa)
4: Received ggg from kernel (Should receive ddd)
6: Received ggg from kernel (Should receive fff)
7: Received ggg from kernel (Should receive ggg)
10: Writing jjj to kernel
5: Received ggg from kernel (Should receive eee)
10: Received jjj from kernel (Should receive jjj)
9: Writing hhh to kernel
8: Writing iii to kernel
9: Received iii from kernel (Should receive hhh)
8: Received iii from kernel (Should receive iii)
```
可以發現在第 2 個 receive 中我們就得到錯誤的結果了。
使用的程式碼可以參考[這個 gist](https://gist.github.com/afcidk/18508eaa63da55a5b9799fa6edf936e2)
## 效能分析
* 使用 fast doubling 演算法和原本的版本 (dynamic programming) 比較時間差異，時間單位為 ns
Fast doubling 使用兩組公式來加速運算速度
$F(2n) = F(n)[2F(n+1) – F(n)] \\
F(2n + 1) = F(n)^2 + F(n+1)^2$
這樣的時間複雜度會是 $O(logn)$，可以發現算到 `fib(92)` 的時候計算時間就有落差了。
* kernel space 到 user space 的時間開銷
###### tags:`afcidk`
Sign in with Wallet
Connect another wallet