# 2019q1 Homework2 (fibdrv)
contributed by < `joey-ycpeng` >
## [測試給定的 fibdrv 模組](https://hackmd.io/s/HkSY7SYw4)
## 自我檢查清單
#### 1. 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
Answer:
* 觀察定義 `include/linux/module.h`:
```
/* Generic info of form tag = "info" */
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
...
#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)
#define MODULE_DESCRIPTION(_description) MODULE_INFO(description,_description)
#define MODULE_VERSION(_version) MODULE_INFO(version, _version)
```
* `include/linux/moduleparam.h`:
`__MODULE_INFO` 展開變成以 `name` 形成的 unique ID 的 `char` array，並以 `info` 裡的字串做初始化，放入 `.modinfo` section
```
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
```
* Dump section `.modinfo` 可以看到 `auth=...` 、`license=...`，因為 `MODULE_AUTHOR` 和 `MODULE_LICENSE` 都把定義的字串加入 module 的 `.modinfo` section
```
$ readelf -p .modinfo fibdrv.ko
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.18.0-15-generic SMP mod_unload
```
* 觀察 `insmod` 的動作，先打開 module 的 dynamic debug
```
$ echo -n "file module.c +p" > /sys/kernel/debug/dynamic_debug/control
```
* 載入 module 並觀察 kernel message，發現 `insmod` 會呼叫 system call `finit_module`
```
$ insmod fibdrv.ko
$ dmesg
[36174.464243] finit_module: fd=3, uargs=0000000072596e31, flags=0
[36174.464291] Core section allocation order:
[36174.464293] .text
[36174.464295] .text.unlikely
[36174.464297] .exit.text
[36174.464299] .note.gnu.build-id
[36174.464301] __mcount_loc
[36174.464303] .rodata.str1.1
[36174.464305] .rodata.str1.8
[36174.464306] .rodata
[36174.464309] .data
[36174.464311] .gnu.linkonce.this_module
[36174.464313] .bss
[36174.464315] Init section allocation order:
[36174.464317] .init.text
[36174.464321] .symtab
[36174.464325] .strtab
[36174.464381] final section addresses:
[36174.464384] 0xffffffffc0e4a000 .note.gnu.build-id
[36174.464387] 0xffffffffc0e49000 .text
[36174.464389] 0xffffffffc0e49151 .text.unlikely
[36174.464391] 0xffffffffc0e98000 .init.text
[36174.464393] 0xffffffffc0e49167 .exit.text
[36174.464395] 0xffffffffc0e4a024 __mcount_loc
[36174.464397] 0xffffffffc0e4a054 .rodata.str1.1
[36174.464399] 0xffffffffc0e4a0c8 .rodata.str1.8
[36174.464401] 0xffffffffc0e4a120 .rodata
[36174.464403] 0xffffffffc0e4b000 .data
[36174.464406] 0xffffffffc0e4b040 .gnu.linkonce.this_module
[36174.464408] 0xffffffffc0e4b380 .bss
[36174.464410] 0xffffffffc0e99000 .symtab
[36174.464412] 0xffffffffc0e995b8 .strtab
[36174.464457] Absolute symbol: 0x00000000
[36174.464459] Absolute symbol: 0x00000000
```
* 以`MODULE_LICENSE` 為例， 核心在 `check_modinfo()` 會讀取 `.modinfo` 裡`license=` 開頭的字串:
```c
static int check_modinfo(struct module *mod, struct load_info *info, int flags)
{
...
/* Set up license info based on the info section */
set_license(mod, get_modinfo(info, "license"));
return 0;
}
```
---
#### 2. 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
Answer:
* 觀察 `module_init()` 在 `include/linux/module.h` 的定義:
```c
/* 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)));
```
* 定義了一個回傳 `initcall_t` 型別 (`typedef int (*initcall_t)(void);`) 的 function `__inittest(void)`，目的是檢查 `initfn` 是否符合 `initcall_t` 型別
* 接著宣告了一個 `init_module(void)` 做為 `initfn` 的別名（alias)
* 觀察核心原始碼 `kernel/module.c` ，發現核心會找尋 `.gnu.linkonce.this_module` ，將其位置存在 `info->mod`，並在之後以 `struct module *` 的結構去讀取其中的內容
```c
static int setup_load_info(struct load_info *info, int flags)
{
...
info->index.mod = find_sec(info, ".gnu.linkonce.this_module");
if (!info->index.mod) {
pr_warn("%s: No module found in object\n",
info->name ?: "(missing .modinfo name field)");
return -ENOEXEC;
}
/* This is temporary: point mod into copy of data. */
info->mod = (void *)info->hdr + info->sechdrs[info->index.mod].sh_offset;
...
```
* 最後會在 `do_init_module` 裡執行 `mod->init`
```c
static noinline int do_init_module(struct module *mod)
{
...
do_mod_ctors(mod);
/* Start the module */
if (mod->init != NULL)
ret = do_one_initcall(mod->init);
if (ret < 0) {
goto fail_free_freeinit;
}
if (ret > 0) {
pr_warn("%s: '%s'->init suspiciously returned %d, it should "
"follow 0/-E convention\n"
"%s: loading module anyway...\n",
__func__, mod->name, ret, __func__);
dump_stack();
}
...
```
* 回頭去找 `.gnu.linkonce.this_module` section 出現的檔案，發現在 `fibdrv.mod.c`
```
$ grep -Inr .gnu.linkonce.this_module ./
./fibdrv.mod.c:9:__attribute__((section(".gnu.linkonce.this_module"))) = {
```
* 打開 `fibdrv.mod.c`，看到 `.init = init_module`，所以核心得以找到 macro `module_init` 所設定的 function 來執行
```c
#include <linux/module.h>
#include <linux/vermagic.h>
#include <linux/compiler.h>
MODULE_INFO(vermagic, VERMAGIC_STRING);
MODULE_INFO(name, KBUILD_MODNAME);
__visible struct module __this_module
__attribute__((section(".gnu.linkonce.this_module"))) = {
.name = KBUILD_MODNAME,
.init = init_module,
#ifdef CONFIG_MODULE_UNLOAD
.exit = cleanup_module,
#endif
.arch = MODULE_ARCH_INIT,
};
#ifdef RETPOLINE
MODULE_INFO(retpoline, "Y");
#endif
static const char __module_depends[]
__used
__attribute__((section(".modinfo"))) =
"depends=";
MODULE_INFO(srcversion, "24DC5FB7E7608AF16B0CC1F");
```
---
#### 3. 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
Answer:
* 關於「植入」核心，首先觀察 system call `sys_init_module` 和 `sys_finit_module` 都會先把整個 module cpoy 到核心的記憶體空間 (`copy_module_from_user` or `kernel_read_file_from_fd`)，接著初始化 `struct load_info` 並呼叫 `load_module`
```c
err = kernel_read_file_from_fd(fd, &hdr, &size, INT_MAX,
READING_MODULE);
if (err)
return err;
info.hdr = hdr;
info.len = size;
return load_module(&info, uargs, flags);
```
* `load_info` structure:
```c
struct load_info {
const char *name;
/* pointer to module in temporary copy, freed at end of load_module() */
struct module *mod;
Elf_Ehdr *hdr;
unsigned long len;
Elf_Shdr *sechdrs;
char *secstrings, *strtab;
unsigned long symoffs, stroffs;
struct _ddebug *debug;
unsigned int num_debug;
bool sig_ok;
#ifdef CONFIG_KALLSYMS
unsigned long mod_kallsyms_init_off;
#endif
struct {
unsigned int sym, str, mod, vers, info, pcpu;
} index;
};
```
* `load_module` 裡幾個重要的 function call
1. `elf_header_check(info)` 檢查 ELF header
2. `setup_load_info(info, flags)` 將 `info` 裡的 pointer 指向正確位置
1. `*name`: `.modinfo` 裡的 name
2. `*mod`: `.gnu.linkonce.this_module` 裡的 `struct module`
3. `*hdr`: module 的檔頭
4. `len`: module 檔案長度
5. `*sechdrs`: section headers 的位置
6. `*secstrings`: section header string table
3. `rewrite_section_headers(info, flags)` 將 section offset 寫入 `info->sechdrs[].sh_addr`
4. `mod = layout_and_allocate(info, flags);` Figure out module layout, and allocate all the memory
1. `layout_sections(info->mod, info);`
1. `mod->core_layout.size`
2. `mod->init_layout.size`
2. `layout_symtab(info->mod, info);`
3. ==`move_module(info->mod, info);`==
1. Allocate core section 並存入 `mod->core_layout.base`
2. Allocate init section 並存入 `mod->init_layout.base`
3. Copy core and init sections to the final allocated memory address
4. 觀察 kernel message 可以看到最後分配的位址
```
[33747.463297] final section addresses:
[33747.463300] 0xffffffffc0e9f000 .note.gnu.build-id
[33747.463303] 0xffffffffc0e9e000 .text
[33747.463305] 0xffffffffc0e9e151 .text.unlikely
[33747.463307] 0xffffffffc0ea3000 .init.text
[33747.463309] 0xffffffffc0e9e167 .exit.text
[33747.463311] 0xffffffffc0e9f024 __mcount_loc
[33747.463313] 0xffffffffc0e9f054 .rodata.str1.1
[33747.463315] 0xffffffffc0e9f0c8 .rodata.str1.8
[33747.463317] 0xffffffffc0e9f120 .rodata
[33747.463320] 0xffffffffc0ea0000 .data
[33747.463322] 0xffffffffc0ea0040 .gnu.linkonce.this_module
[33747.463324] 0xffffffffc0ea0380 .bss
[33747.463326] 0xffffffffc0ea4000 .symtab
[33747.463328] 0xffffffffc0ea45b8 .strtab
```
5. 至此 module 已經初步植入核心
---
* 這個 `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 核心模組範例
* 注意到 `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