2019q1 Homework2 (fibdrv)

# 2019q1 Homework2 (fibdrv) contributed by < `guojiun` > ### Review by Zames-Chang * 在 `int fib(int n)` 的函式中，因為第一個 `if` 函式會執行到 `2^K <= n && 2^K+1 > n` 所以你的時間複雜度仍然是 $O(n)$，要計算的總數為$N = (n-2^k) + logk$，其中 `if` 這段程式碼執行了 $logk$ 次 `else` 執行了 $(n-2^k)$ 次。不過因為$(2^k-logk) < 0$ 所以仍然有起到加速的作用。 * 使用 `int` 比原本使用的` long long ` 可以處理的數值範圍更小，建議使用 `unsiged long long `，不過我想也是方便起見你才這樣寫的。 * 然後要 reject input 的 int < 0 的情況。 ```cpp while (i < n) { /* 這一個 if 會執行到 2^K <= n 然後 2^K+1 > n */ if ((i << 1) <= n) { t4 = t1 * t1 + t0 * t0; t3 = t0 * (2 * t1 - t0); t0 = t3; t1 = t4; i = i << 1; /* 這一個 else 會執行從2^K -> n */ } else { t0 = t3; t3 = t4; t4 = t0 + t4; i++; } } ``` ## 實驗環境 ```shell $ uname -r 4.15.0-45-generic ``` ## 自我檢查清單 - [ ] **檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？** 在 [/include/linux/module.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/module.h#L198) 中，定義了相關的 macro，以 `MODULE_LICENSE` 來說，其定義如下： ```clike #define MODULE_LICENSE(_license) MODULE_INFO(license, _license) #define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info) ``` 而 `__MODULE_INFO()` 則於 [/include/linux/moduleparam.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/moduleparam.h#L21) 之中： ```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 ``` `__stringify` [/include/linux/stringify.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/stringify.h#L10) : ```clike #define __stringify_1(x...) #x #define __stringify(x...) __stringify_1(x) ``` `__used` [/include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler-gcc.h#L139) : ```clike #if GCC_VERSION < 30300 # define __used __attribute__((__unused__)) #else # define __used __attribute__((__used__)) #endif ``` 最終，展開後，如下所示： ```clike static const char __UNIQUE_ID_license23[] \ __attribute__((__used__)) \ __attribute__((section(".modinfo"), unused, aligned(1))) \ = "license = Dual MIT/GPL" ``` 由此可知，上述 `MODULE_XXXX` 等 macro，將其對應的變量，如 `MODULE_LICENSE` 對應至__UNIQUE_ID_license23 (可由 .ko 之 symbol table 得知) 放至 `.modinfo` section 中。 - [ ] **insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀** * **當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢?** `insmod` 指令位於 /sbin 底下，實際上指向 /bin/kmod，而 `kmod` 是管理 linux 模組的命令集合 [kmod](https://packages.ubuntu.com/zh-tw/trusty/kmod)。我們不從 `insmod` 內部的實作入手，而是透過像 `strace` 這樣的工具來追蹤 `insmod` 命令在執行的過程中所呼叫的 system call 資訊: ``` sudo strace -o strace.txt insmod fibdrv.ko ... finit_module(3, "", 0) = 0 ... ``` 查看 man page [finit_module](https://linux.die.net/man/2/finit_module) finit_module : * The finit_module() system call is like init_module(), but reads the module to be loaded from the file descriptor fd. 那 init_module 是做什麼的呢？ * loads an ELF image into kernel space * performs anynecessary symbol relocations * initializes module parameters to values * runs the module's init function `finit_module` 對應的 linux 實作 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3846)：(摘要) ```clike SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags) { ... err = kernel_read_file_from_fd(fd, &hdr, &size, INT_MAX, READING_MODULE); ... return load_module(&info, uargs, flags); } ``` 接著呼叫 load_module [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3642) (摘要) ```clike static int load_module(struct load_info *info, const char __user *uargs, int flags) { ... /* Figure out module layout, and allocate all the memory. */ mod = layout_and_allocate(info, flags); /* Now module is in final location, initialize linked lists, etc. */ err = module_unload_init(mod); init_param_lock(mod); /* Now we've got everything in the final locations, we can * find optional sections. */ err = find_module_sections(mod, info); err = check_module_license_and_versions(mod); /* Set up MODINFO_ATTR fields */ setup_modinfo(mod, info); /* Now copy in args */ mod->args = strndup_user(uargs, ~0UL >> 1); /* Done! */ trace_module_load(mod); return do_init_module(mod); } ``` 這時才呼叫 do_init_module() [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3426) (摘要) ``` static noinline int do_init_module(struct module *mod) { struct mod_initfree *freeinit; freeinit = kmalloc(sizeof(*freeinit), GFP_KERNEL); freeinit->module_init = mod->init_layout.base; /* Start the module */ if (mod->init != NULL) ret = do_one_initcall(mod->init); ... return 0; ... } ``` 觀察到有個很特別的 function call `do_one_initcall(mod->init)` 可能是由此呼叫 module_init 所設定的函式。 - [ ] **試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心** ```shell $readelf -a fibdrv.ko ... Section Headers: [Nr] Name Type Address Offset ... [ 4] .init.text .... Symbol table '.symtab' contains 59 entries: ... 22: 0000000000000000 339 FUNC LOCAL DEFAULT 4 init_fib_dev ``` `module_init` 與 `module_exit` 兩者都是 macro ，且被定義在 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/module.h#L85) ```clike #define module_init(x) __initcall(x); #define module_exit(x) __exitcall(x); ``` ```clike #define module_init(initfn) \ static inline initcall_t __maybe_unused __inittest(void) \ { return initfn; } \ int init_module(void) __attribute__((alias(#initfn))); ``` 因此，fibdrv.c 中 `module_init(init_fib_dev);` ，其展開後，如下： ```clike= static inline initcall_t __maybe_unused __inittest(void) { return init_fib_dev;} int init_module(void) __attribute__((alias("init_fib_dev"))); ``` 以 module_init(x) 為例，其 __initcall 另被定義在 [/include/linux/init.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/init.h#L199) ```clike #define __initcall(fn) device_initcall(fn) #define device_initcall(fn) __define_initcall(fn, 6) #define __define_initcall(fn, id) \ static initcall_t __initcall_##fn##id __used \ __attribute__((__section__(".initcall" #id ".init"))) = fn; ``` 其中，initcall_t 被定義於同個檔案 [/include/linux/init.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/init.h#L109) ```clike typedef int (*initcall_t)(void); ``` __used 則被定義於 [/include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler-gcc.h#L138) ```clike #if GCC_VERSION < 30300 # define __used __attribute__((__unused__)) #else # define __used __attribute__((__used__)) #endif ``` 因此，`module_init(x)` 最終展開後，等同於 `__define_initcall(fn, 6)` 而其又等同於： ```clike static int __initcall_fn_6(void) \ __attribute__((__used__)) \ __attribute__((__section__(".initcall" "6" ".init"))) = fn; ``` 根據 [linux-insides](https://0xax.gitbooks.io/linux-insides/Concepts/linux-cpu-3.html) ，其中提及，在 [/include/asm-generic/vmlinux.lds.h](https://elixir.bootlin.com/linux/v4.15/source/include/asm-generic/vmlinux.lds.h#L749) linker script 中，`initcalls` sections 會透過 `data` sections 間接取得 ```clike #define INIT_CALLS \ VMLINUX_SYMBOL(__initcall_start) = .; \ KEEP(*(.initcallearly.init)) \ INIT_CALLS_LEVEL(0) \ INIT_CALLS_LEVEL(1) \ INIT_CALLS_LEVEL(2) \ INIT_CALLS_LEVEL(3) \ INIT_CALLS_LEVEL(4) \ INIT_CALLS_LEVEL(5) \ INIT_CALLS_LEVEL(rootfs) \ INIT_CALLS_LEVEL(6) \ INIT_CALLS_LEVEL(7) \ VMLINUX_SYMBOL(__initcall_end) = .; ... #define INIT_DATA_SECTION(initsetup_align) \ .init.data : AT(ADDR(.init.data) - LOAD_OFFSET) { \ ... INIT_CALLS \ ... } ``` **小記** * 原以為 ELF 檔中會存在 `initcall` section，然而根據 symbal table 得知，module_init() 所註冊的 function，其實是放在 `.init.text` section 中。尚不太清楚上述 `".initcall" "6" ".init"` 最終是如何對應至 ELF 檔的 section。 > 注意到 module.h 中第 76 行的 `#ifndef MODULE`，這用來區別需要編譯出靜態還是動態連結的ELF，而 kernel module 需要動態加載，所以這邊需要看[第 128 行](https://elixir.bootlin.com/linux/v4.15/source/include/linux/module.h#L128)的 macro 定義 > 然後可以去看看 `fibdrv.mod.c` > [name=HexRabbit][color=purple] * 到目前為止，已約略了解 fibdrv.c 與其 ELF 檔 section 之間的對應關係，也初步了解，insmod 將 ELF 檔載入 kernel 的流程。不過細節的把握，仍迷惑不已。將繼續釐清... [Linux Loadable Kernel Module HOWTO](https://www.tldp.org/HOWTO/html_single/Module-HOWTO/#AEN627) * 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。 * 參考資料：[Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/) * 名詞解釋： * CPU execution time jitter: jitter is the deviation from true periodicity of a presumably periodic signal [wiki](https://en.wikipedia.org/wiki/Jitter) * 摘要： > The kernel's deterministic random bit generator (DRBG) is currently initialized by making a call to get_random_bytes(), which uses the non-blocking random number pool. > > Instead of reusing the existing blocking pool (i.e. the one that feeds `/dev/random`), though, his patch creates a new kernel_pool that is only accessible to the kernel itself. That eliminates a kind of denial-of-service attack where a user-space program can continuously read `/dev/random` to consume all of the entropy being generated by the system. * 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說) * clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說 * fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例 * why considering writing kernel-mode code? [來源](https://stackoverflow.com/questions/149032/when-should-i-write-a-linux-kernel-module) * Does it need access to extremely low-level resources, such as interrupts? * Is your code defining a new interface/driver for hardware that cannot be built on top of currently exported functionality? * Does your code require access to data structures or primitives that are not exported out of kernel space? * Are you writing something that will be primarily used by other kernel subsystems, such as a scheduler or VM system? ## 實作： * 未修改 : ![Imgur](https://i.imgur.com/kO0EW3B.png) ```clike= static long long fib_sequence(long long k) { /* FIXME: use clz/ctz and fast algorithms to speed up */ long long f[k + 2]; f[0] = 0; f[1] = 1; for (int i = 2; i <= k; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[k]; } ``` * Fast-doubling : [參考資料](https://hackmd.io/s/rJ8BOjGGl#Fast-doubling) ![Imgur](https://i.imgur.com/hXWF9Va.png) ```clike= int fib(int n) { if (n == 0) return 0; int t0 = 1; // F(n) int t1 = 1; // F(n + 1) int t3 = 1; // F(2n) int t4; // F(2n+1) int i = 1; while (i < n) { if ((i << 1) <= n) { t4 = t1 * t1 + t0 * t0; t3 = t0 * (2 * t1 - t0); t0 = t3; t1 = t4; i = i << 1; } else { t0 = t3; t3 = t4; t4 = t0 + t4; i++; } } return t3; } ``` * 實作在 user space 上，尚未在 kernel space 上運行： ```clike= void fib_luc(long *fib_result, long *luc_result, int n) { long tmp; if (n == 0) { *fib_result = 0; *luc_result = 2; return; } fib_luc(fib_result, luc_result, n/2); if (n & 1) { tmp = (*fib_result) * (*luc_result); *luc_result = 5 * (*fib_result) * ((*luc_result) + (*fib_result)) / 2; ((n & 2) == 0) ? (*luc_result += 1) : (*luc_result -= 1); *fib_result = *luc_result - 2 * tmp; } else { tmp = (*fib_result) * (*fib_result); *fib_result = (*fib_result) * (*luc_result); *luc_result = 5 * tmp; ((n & 2) == 0) ? (*luc_result += 2) : (*luc_result -= 2); } } void fib(long *result, int n) { long luc, tmp; fib_luc(result, &luc, n/2); if (n % 2 != 0) { *result = 5 * (*result) * (luc + *result) / 2 - 2 * luc * (*result); if ((n & 2) == 0) { *result = *result + 1; } else { *result = *result - 1; } } else { *result = (*result) * (luc); } } ``` * 說明： * 因目前版本為遞迴形式，須改為 iteration 後，再移植到 kernel module 中 * [參考資料(一)](https://bosker.wordpress.com/2011/07/27/computing-fibonacci-numbers-using-binet%E2%80%99s-formula/) * [參考資料(二)](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html#section2.3)