# 2019q1 Homework2 (fibdrv)
contributed by < `cjwind` >
## 環境
* Debian 9.8
* Linux 4.19.0-0.bpo.2-amd64
* gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1)
## 自我檢查清單
### 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？
以下檔案路徑為 `/usr/src/linux-headers-4.19.0-0.bpo.2-common/` 的相對路徑。
:::warning
列舉程式碼時，請附上 [bootlin](https://elixir.bootlin.com/linux/latest/source) 對應的超連結，注意要選取對應的核心版本號碼
:notes: jserv
:::
這幾個 macro 定義在 [`include/linux/module.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L200)：
```clike
#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)
#define MODULE_DESCRIPTION(_description) MODULE_INFO(description, _description)
#if defined(MODULE) || !defined(CONFIG_SYSFS)
#define MODULE_VERSION(_version) MODULE_INFO(version, _version)
#else
#define MODULE_VERSION(_version) \
static struct module_version_attribute ___modver_attr = { \
.mattr = { \
.attr = { \
.name = "version", \
.mode = S_IRUGO, \
}, \
.show = __modver_version_show, \
}, \
.module_name = KBUILD_MODNAME, \
.version = _version, \
}; \
static const struct module_version_attribute \
__used __attribute__ ((__section__ ("__modver"))) \
* __moduleparam_const __modver_attr = &___modver_attr
#endif
```
`MODULE_INFO` 定義於[相同檔案](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L161)：
```clike
/* Generic info of form tag = "info" */
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
```
author、license、description 跟 version 資訊以 `<tag, info>` 的 key-value 形式記錄。
`__MODULE_INFO` 定義於 [`include/linux/moduleparam.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/moduleparam.h#L20)：
```clike
#ifdef MODULE
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
#else /* !MODULE */
/* This struct is here for syntactic coherency, it is not used */
#define __MODULE_INFO(tag, name, info) \
struct __UNIQUE_ID(name) {}
#endif
```
`__used __attribute__((section(".modinfo"), unused, aligned(1)))` 看起來跟 section `.modinfo` 有關，用 `readelf` 觀察 `fibdrv.o`：
```
$ readelf -x .modinfo fibdrv.o
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 504c00 PL.
```
可以看到這些資訊存在 `.modinfo` section。
`__attribute__` 在 GCC 裡用來對 function、variable 等指定 attribute，syntax 為 `__attribute__ ((attribute-list))`。其中 `attribute-list` 中多個 attribute 以逗號 `,` 分隔，一個 attribute 的格式可以是 `name(parameter)`，更多 syntax 可參考 [Attribute Syntax](https://gcc.gnu.org/onlinedocs/gcc/Attribute-Syntax.html)。
variable attribute 寫起來會像這樣：`int x __attribute__ ((aligned (16))) = 0;`
回到 `__MODULE_INFO` 定義中的 attribute。`section(".modinfo")` 表示把這個 variable 放在 `.modinfo` section 裡，符合 `readelf` 看到的。`unused` 表示這個 variable 可能不會被使用，GCC 不會對它產生 warning。`aligned(1)` 設定這個 variable 的最小 alignment 為 1 byte。Ref [Common Variable Attributes](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html#Common-Variable-Attributes)
`__used` 定義於 [`include/linux/compiler_types.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/compiler_types.h#L208)：
```clike
#define __used __attribute__((__used__))
```
對 static variable 設定 `__attribute__((__used__))` 時，會要求 compiler 一定要產生 symbol，即使 variable 沒有被 reference 到。舉個例子：
```clike
static int x = 123;
int main() {
return 0;
}
```
這段程式用 `gcc -O1 -c test.c` compile 後，用 `nm` 看 symbol：
```
$ nm test.o
0000000000000000 T main
```
幫 `x` 加上 `used` attribute：
`static int x __attribute__((__used__)) = 123;`
以相同參數 compile 後的 symbol：
```
$ nm test.o
0000000000000000 T main
0000000000000000 d x
```
`__UNIQUE_ID(name)` 就字面來看是以 `name` 產生一個 unique id 作為這個 `static const char []` 的變數名稱。
這個變數的值是 `__stringify(tag) "=" info`，`__stringify` 定義在 [`include/linux/stringify.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/stringify.h)：
```clike
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
一般 `#define` macro 不會把 parameter 展開成字串，只會把 parameter 放到對應位置，例如以下：
```clike
#define ECHO(str) printf("%s\n", str)
int main() {
char s[] = "hello";
ECHO(s);
return 0;
}
```
經過 preprocess 後會變成：
```clike
int main() {
char s[] = "hello";
printf("%s\n", s);
return 0;
}
```
如果在 parameter 前加 `#`，preprocessor 會把 actual argument 變成「字串」，稱為 [Stringizing](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html)，例子：
```clike
#define ECHO(str) printf("%s\n", #str)
int main() {
char s[] = "hello";
ECHO(s);
return 0;
}
```
經過 preprocess（只是例子，code 本身不太 make sense）：
```clike
int main() {
char s[] = "hello";
printf("%s\n", "s");
return 0;
}
```
為什麼 `__stringify` 要 define 兩次呢？
在 [Argument Prescan](https://gcc.gnu.org/onlinedocs/cpp/Argument-Prescan.html) 提到 macro 的參數如果也是 macro，一般在被替換進 macro body 前就會被展開，但如果是 stringized 則不會被展開。例如：
```clike
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
#define FOO bar
__stringify_1(FOO) // become "FOO"
__stringify(FOO) // become "bar"
```
`__stringify_1(FOO)` 因為是 stringized 的 macro 參數，所以 FOO 不會被展開，macro 替換後最後變成 `"FOO"`。
`__stringify(FOO)` 會先把 `FOO` 展開並且替換變成 `__stringify_1(bar)`，然後會再有一次 scan 將 macro 再展開成 `"bar"`。
`__stringify` define 兩次是為了讓參數可以使用 macro。
`...` 是跟 function 一樣的不定參數，可參考 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)。
總結，這四個 macro 會變成四個 `static const char []` 變數，放在 section `.modinfo`，值為 `"name=value"`，`name` 為 `author`、`license`、`description` 或 `version`，`value` 為 macro 參數。
### `insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？
用 [`apt-src`](https://wiki.debian.org/apt-src) download 了 `kmod` 的程式碼，`insmod` 用到 system call `init_module` 跟 `finit_module`。
用 `strace` 看 `insmod` 執行過程中使用到哪些 system call：
```
$ sudo strace insmod fibdrv.ko
...(ignore)
finit_module(3, "", 0) = 0
munmap(0x7f14027d3000, 334816) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
`init_module` 與 `finit_module` 是 load kernel module 的 system call。
```
int init_module(void *module_image, unsigned long len, const char *param_values);
int finit_module(int fd, const char *param_values, int flags)
```
> init_module() loads an ELF image into kernel space, performs any necessary symbol relocations, initializes module parameters to values provided by the caller, and then runs the module's init function.
> ~ from [init_module(2)](http://man7.org/linux/man-pages/man2/init_module.2.html)
`finit_module` 跟 `init_module` 的差異在 `finit_module` 從 file descriptor load module，`init_module` 直接從參數的 buffer load module binary image。
module 的參數會在 module 內以 `module_param()` 定義。`insmod` 後面可以接要傳給 module 的參數，參數透過 `param_values` 傳給 module。
### kerenl 如何 load module
**當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？**
**試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心**
`module_init` 定義於 [`include/linux/module.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L87)：
```clike
#define module_init(x) __initcall(x);
```
`__initcall` 定義於 [`include/linux/init.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/init.h#L233)
```clike
#define __initcall(fn) device_initcall(fn)
```
`device_initcall` 定義在[同個檔案](https://elixir.bootlin.com/linux/v4.19/source/include/linux/init.h#L228)：
```clike
#define device_initcall(fn) __define_initcall(fn, 6)
```
最後到 `__define_initcall` 的[定義](https://elixir.bootlin.com/linux/v4.19/source/include/linux/init.h#L194)：
```clike
#ifdef CONFIG_HAVE_ARCH_PREL32_RELOCATIONS
#define ___define_initcall(fn, id, __sec) \
__ADDRESSABLE(fn) \
asm(".section \"" #__sec ".init\", \"a\" \n" \
"__initcall_" #fn #id ": \n" \
".long " #fn " - . \n" \
".previous \n");
#else
#define ___define_initcall(fn, id, __sec) \
static initcall_t __initcall_##fn##id __used \
__attribute__((__section__(#__sec ".init"))) = fn;
#endif
```
`initcall_t` 是個 function pointer 的 type，定義於 [`include/linux/init.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/init.h#L116)：
```clike
typedef int (*initcall_t)(void);
```
也就是給 `module_init` 的 function type。
`module_init(init_fib_dev)` 展開後是一個名字為 `__initcall_init_fib_dev6` 的 function pointer，並且被放在 `.initcall6.init` section。
可是用 `readelf -S fibdrv.ko` 卻沒看到 `.initcall6.init` section？
回到 [`include/linux/module.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L78) 看仔細點：
```clike
#ifndef MODULE
/**
* module_init() - driver initialization entry point
* @x: function to be run at kernel boot time or module insertion
*
* module_init() will either be called during do_initcalls() (if
* builtin) or at module insertion time (if a module). There can only
* be one per module.
*/
#define module_init(x) __initcall(x);
/**
* module_exit() - driver exit entry point
* @x: function to be run when driver is removed
*
* module_exit() will wrap the driver clean-up code
* with cleanup_module() when used with rmmod when
* the driver is a module. If the driver is statically
* compiled into the kernel, module_exit() has no effect.
* There can only be one per module.
*/
#define module_exit(x) __exitcall(x);
#else /* MODULE */
/*
* In most cases loadable modules do not need custom
* initcall levels. There are still some valid cases where
* a driver may be needed early if built in, and does not
* matter when built as a loadable module. Like bus
* snooping debug drivers.
*/
#define early_initcall(fn) module_init(fn)
#define core_initcall(fn) module_init(fn)
#define core_initcall_sync(fn) module_init(fn)
#define postcore_initcall(fn) module_init(fn)
#define postcore_initcall_sync(fn) module_init(fn)
#define arch_initcall(fn) module_init(fn)
#define subsys_initcall(fn) module_init(fn)
#define subsys_initcall_sync(fn) module_init(fn)
#define fs_initcall(fn) module_init(fn)
#define fs_initcall_sync(fn) module_init(fn)
#define rootfs_initcall(fn) module_init(fn)
#define device_initcall(fn) module_init(fn)
#define device_initcall_sync(fn) module_init(fn)
#define late_initcall(fn) module_init(fn)
#define late_initcall_sync(fn) module_init(fn)
#define console_initcall(fn) module_init(fn)
#define security_initcall(fn) module_init(fn)
/* 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) __attribute__((alias(#initfn)));
/* This is only required if you want to be unloadable. */
#define module_exit(exitfn) \
static inline exitcall_t __maybe_unused __exittest(void) \
{ return exitfn; } \
void cleanup_module(void) __attribute__((alias(#exitfn)));
#endif
```
前面提到的定義，是在 `#ifndef MODULE`，即**非 module** 的情況。
剛好有在編 5.0 kernel，來看一下編成非 module 的 `fs/block_dev.o` 的 section：
```
$ readelf -S block_dev.o | grep init
[ 3] .init.text PROGBITS 0000000000000000 00002f54
[ 4] .rela.init.text RELA 0000000000000000 00044270
[29] .initcall6.init PROGBITS 0000000000000000 00003048
[30] .rela.initcall6.i RELA 0000000000000000 000445b8
```
從 `Makefile` 可以確認它不是編成 module：
```
$ grep -n 'block_dev.o' Makefile
18:obj-y += buffer.o block_dev.o direct-io.o mpage.o
```
`.initcall` section 跟 kernel 啟動時的初始化有關，相關參考資料：
* [module_init() vs. core_initcall() vs. early_initcall()](https://stackoverflow.com/questions/18605653/module-init-vs-core-initcall-vs-early-initcall)
* [Init Call Mechanism in the Linux Kernel. When the module in loaded in the kernel then module init function gets called. How this call happen internally?](https://www.quora.com/Init-Call-Mechanism-in-the-Linux-Kernel-When-the-module-in-loaded-in-the-kernel-then-module-init-function-gets-called-How-this-call-happen-internally)
回到 load module 的 [`module_init` 定義](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L130)：
```clike
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __attribute__((alias(#initfn)));
```
定義了一個 `__inittest` 的 function，return value 的 type 是 `initcall_t`（前面提到的 function pointer），這個 function 就是 return `module_init()` 所指定的 function pointer。
同時，宣告了 `init_module()` function 並設定 [attribute `alias`](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes)。alias attribute 是可以宣告一個 symbol 為另一個 symbol 的 alias，這邊就是將 `init_module` 設為 `initfn` 的 alias，即 `init_module` 是 `init_fib_dev` 的 alias。
`init_fib_dev()` 宣告為 `static int __init init_fib_dev(void)`，其中 `__init` 是指定放到 `.init.text` section 的 attribute 設定，用 `readelf` 可以看到 `init_fib_dev` 跟 `init_module` 放的 section 及 symbol value：
```
$ readelf -sS fibdrv.ko | grep init
[ 4] .init.text PROGBITS 0000000000000000 000001dc
[ 5] .rela.init.text RELA 0000000000000000 0002c4e8
34: 0000000000000000 334 FUNC LOCAL DEFAULT 4 init_fib_dev
60: 0000000000000000 334 FUNC GLOBAL DEFAULT 4 init_module
65: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND __mutex_init
70: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND cdev_init
```
接下來改從 system call `init_module` 出發，在 [`include/linux/syscalls.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/syscalls.h#L567) 宣告：
```clike
/* kernel/module.c */
asmlinkage long sys_init_module(void __user *umod, unsigned long len,
const char __user *uargs);
```
到 [`kernel/module.c`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3840) 找到 function：
```clike
SYSCALL_DEFINE3(init_module, void __user *, umod,
unsigned long, len, const char __user *, uargs)
{
int err;
struct load_info info = { };
err = may_init_module();
if (err)
return err;
pr_debug("init_module: umod=%p, len=%lu, uargs=%p\n",
umod, len, uargs);
err = copy_module_from_user(umod, len, &info);
if (err)
return err;
return load_module(&info, uargs, 0);
}
```
先做點檢查接著 `copy_module_from_user()`，應該是把 user space 的 module binary image copy 到 kernel space。最後進入 [`load_module()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3642)。
[`load_module()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3642) 會檢查 ELF header，call [`setup_load_info()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L2945) setup `struct load_info` 的資料，接著會做許多檢查、allocate memory 等等，最後 call [`do_init_module()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3421)。
`struct load_info` 定義在 [`kernel/module-internal.h`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module-internal.h#L15)：
```clike
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;
};
```
其中 `Elf_Ehdr` 跟 `Elf_Shdr` 是 macro，會定義成不同 architecture 下的 ELF header struct 及 ELF section header struct。
[`setup_load_info()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L2945) 會找 `.modinfo` section，接著透過 `struct load_info` 內 ELF 相關 struct 從 section 中取得 module information。猜測指令 `modinfo` 也是以類似方式讀取 module binary file 取得資訊印出。
`struct load_info` 中有個 `struct module *mod`，`struct module` 定義於 [`include/linux/module.h`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L330)，裡面有個 [member `init`](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L392)：
```clike
/* Startup function. */
int (*init)(void);
```
這個 function pointer 會在 [`do_init_module()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3442) 被傳進 [`do_one_initcall()`](https://elixir.bootlin.com/linux/v4.19/source/init/main.c#L875) 然後呼叫。`do_one_initcall()` 應該就是 kernel 內 call 到 module 內使用 macro `module_init()` 設定的 initialize function 的地方，但這個 function pointer `init` 如何指向 module 內的 function？
回到 [`setup_load_info()` 這段](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L2977)：
```clike
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;
```
先找到 `.gnu.linkonce.this_module` section 的 index，再由 `info->mod` 指向算出的 section 位置。`fibdrv.ko` 的 `.gnu.linkonce.this_module` section 的內容：
```
$ readelf -x .gnu.linkonce.this_module fibdrv.ko
Hex dump of section '.gnu.linkonce.this_module':
NOTE: This section has relocations against it, but these have NOT been applied to this dump.
0x00000000 00000000 00000000 00000000 00000000 ................
0x00000010 00000000 00000000 66696264 72760000 ........fibdrv..
0x00000020 00000000 00000000 00000000 00000000 ................
0x00000030 00000000 00000000 00000000 00000000 ................
0x00000040 00000000 00000000 00000000 00000000 ................
0x00000050 00000000 00000000 00000000 00000000 ................
...(ignore)
0x00000320 00000000 00000000 00000000 00000000 ................
0x00000330 00000000 00000000 00000000 00000000 ................
```
看起來有個 `fibdrv` 名字，然後都是 0。
`fibdrv.c` 裡沒有相關 code 把東西放到這個 section，最後在 compile 過程中自動產生的 `fibdrv.mod.c` 找到這段：
```clike
__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,
};
```
這裡定義了 `struct module __this_module` 而且用 [Designated Initializer](https://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html) 初始化了幾個欄位，其中的 `init` 就在這裡初始化為 `init_module`，而 `init_module` 是 `init_fib_dev` 的 alias。
不過，怎麼 `.gnu.linkonce.this_module` section 裡除了 module name 之外都是 0？那行 NOTE 給了點提示：relocation。用 `readelf -r fibdrv.ko` 找到這個 section 的 relocation 資訊：
```
Relocation section '.rela.gnu.linkonce.this_module' at offset 0x2cc98 contains 2 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000000150 003c00000001 R_X86_64_64 0000000000000000 init_module + 0
000000000320 003a00000001 R_X86_64_64 0000000000000000 cleanup_module + 0
```
relocation table 表示要在 offset 為 `0x150` 的地方以 `R_X86_64_64` 的方式填入 `init_module` 的 address。`load_module()` 中間 call [`apply_relocations()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3730) 進行 relocation。`apply_relocations()` 會再 call 各 architecture 的 relocation 實作。
看 `struct module` 發現有個 [`struct list_head` member](https://elixir.bootlin.com/linux/v4.19/source/include/linux/module.h#L334)，表示 kernel 用 list 來 maintain module。在 `load_module()` 中 call [`add_unformed_module()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3686)，它再 call [`list_add_rcu()`](https://elixir.bootlin.com/linux/v4.19/source/kernel/module.c#L3569) 將 `struct module` 加到 [RCU-protected list](https://elixir.bootlin.com/linux/v4.19/source/include/linux/rculist.h#L8)。
RCU (Read-copy update) 是一種 synchronization 機制，允許一個 updater 跟多個 reader 同時（concurrently）操作。參考資料：
* [What is RCU, Fundamentally?](https://lwn.net/Articles/262464/)
* [RCU concepts](https://www.kernel.org/doc/Documentation/RCU/rcu.txt)
### `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace 程式得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
`fibdrv.c` 利用 `struct file_operations` 指定以 file 相關 operation 操作時的 callback：
```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,
};
```
`cdev_init()` initialize `struct cdev` 並且記錄指定的 `struct file_operations` 到 `struct cdev`。`cdev_add()` 會把 char device 加到系統裡。
### 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
multiple thread / process 的情境下需要用 mutex 保護會共用的 resource。
在 `client.c` write 後、read 前加 `fork()` 讓後面 read 有兩隻 process 在跑，會看到第二個 offset 0 的 return 值壞掉，但後面又會正常：
```
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Reading from /dev/fibonacci at offset 3, returned the sequence 2.
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
Reading from /dev/fibonacci at offset 5, returned the sequence 5.
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Reading from /dev/fibonacci at offset 7, returned the sequence 13.
Reading from /dev/fibonacci at offset 8, returned the sequence 21.
Reading from /dev/fibonacci at offset 9, returned the sequence 34.
Reading from /dev/fibonacci at offset 10, returned the sequence 55.
Reading from /dev/fibonacci at offset 11, returned the sequence 89.
Reading from /dev/fibonacci at offset 12, returned the sequence 144.
Reading from /dev/fibonacci at offset 13, returned the sequence 233.
Reading from /dev/fibonacci at offset 14, returned the sequence 377.
Reading from /dev/fibonacci at offset 15, returned the sequence 610.
Reading from /dev/fibonacci at offset 16, returned the sequence 987.
Reading from /dev/fibonacci at offset 17, returned the sequence 1597.
Reading from /dev/fibonacci at offset 18, returned the sequence 2584.
Reading from /dev/fibonacci at offset 0, returned the sequence 144.
Reading from /dev/fibonacci at offset 19, returned the sequence 4181.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 20, returned the sequence 6765.
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Reading from /dev/fibonacci at offset 21, returned the sequence 10946.
Reading from /dev/fibonacci at offset 3, returned the sequence 2.
Reading from /dev/fibonacci at offset 22, returned the sequence 17711.
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
```
每次跑的結果會不同。猜測是 `fork()` 在 parent 跟 child 的 file 相關 structure 還沒分開前有短暫的時間共用，導致看起來像 child 的 offset 有 parent 的值的執行結果（需確認）。後面結果會對是因為 parent process 跟 child process 的 file 相關 structure 會分開、不會互相干擾。以 `fibdrv` 是用 file offset 作為 input 來說，file structure 分開後就沒有影響。
TODO multi-thread
## 修改 fibdrv
### 使用 `ktime_get()` 測量計算時間
將 `fib_read()` 實作修改為：
```clike
ktime_t start = ktime_get();
long long int fib = fib_sequence(*offset);
ktime_t end = ktime_get();
printk("n = %lld, spend = %lld ns\n", *offset, end - start);
return (ssize_t) fib;
```
---
## 作業要求
### 自我檢查清單
* [x] 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ `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 核心模組範例
* [ ] 注意到 `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) 運算嗎？請列出關鍵程式碼並解說
### 作業要求
* 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 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) 一類的指令，過程中都要充分量化
###### tags: `Linux 核心設計 2019`
Sign in with Wallet
Connect another wallet