# 2019q1 Homework2 (fibdrv)
contributed by < `bauuuu1021` >

## 環境及初始測試
* linux version

    $ uname -r
    4.15.0-45-generic

* 安裝 linux-headers 套件

    $ sudo apt install linux-headers-`uname -r`

* 確認 linux-headers 套件已正確安裝

    bauuuu1021@x555:~$ dpkg -L linux-headers-4.15.0-45-generic | grep "/lib/modules"
    /lib/modules
    /lib/modules/4.15.0-45-generic
    /lib/modules/4.15.0-45-generic/build

* 使用者身份測試

    $ whoami
	bauuuu1021
	$ sudo whoami
	root

## 自我檢查清單
### fibdrv.c 中巨集作用
>檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ [color=#7F8580]
* 編譯完成後執行 `$ modinfo fibdrv.ko` 得到以下輸出

    filename:       /home/bauuuu1021/fibdrv/fibdrv.ko
    version:        0.1
    description:    Fibonacci engine driver
    author:         National Cheng Kung University, Taiwan
    license:        Dual MIT/GPL
    ...

將 `fibdrv.c` 中

    MODULE_VERSION("0.1");

改為

    MODULE_VERSION("1.0");

執行結果變成

    filename:       /home/bauuuu1021/fibdrv/fibdrv.ko
    version:        1.0
    description:    Fibonacci engine driver
    author:         National Cheng Kung University, Taiwan
    license:        Dual MIT/GPL

>根據結果，這些 macro 很有可能是用來印出 module 相關資訊。但只有猜測不符合科學精神，以下為驗證過程[name=bauuuu1021][color=#0ABAB5]

* 在 [linux/module.h](https://github.com/torvalds/linux/blob/master/include/linux/module.h) 中，可以發現題目要求探討的 macro 都是展開為另一個 macro `MODULE_INFO`，例如：

    #define MODULE_LICENSE(_license) MODULE_INFO(license, _license)

而 `MODULE_INFO` 又會再<s>呼叫</s>展開為另一個 macro `__MODULE_INFO`
:::warning
preprocessor 的術語不是「呼叫」，而是「展開」(expand)，注意用語，兩者行為截然不同
:notes: jserv
:::

    /* Generic info of form tag = "info" */
    #define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)

* `__MODULE_INFO` 是被定義在另一個 header file [linux/moduleparam.h](https://github.com/torvalds/linux/blob/master/include/linux/moduleparam.h)

    #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

* [\_\_attribute\_\_](https://gcc.gnu.org/onlinedocs/gcc-4.0.0/gcc/Variable-Attributes.html#Variable-Attributes)
>The keyword \_\_attribute\__ allows you to specify special attributes of variables or structure fields.This keyword is followed by an attribute specification inside **double parentheses**.
* section(".modinfo")
>Sometimes, however, you need additional sections, or you need certain particular variables to appear in special sections, for example to map to special hardware. The section attribute specifies that a variable (or function) lives in a particular section.

* unused
表示這個變數可能宣告但不被用到，加上 `unused` 可避免 gcc 產生 warning
* aligned(size)
可將變數配置在 `size` 大小的記憶體空間內，方便一些特定指令的操作，如：
* 在 68040 上，指令 `move16` 要求 16-byte aligned operands
* 此時若宣告 `int x __attribute__ ((aligned (16))) = 0;` 即可滿足 16-byte aligned

* [_\_stringify](https://blog.csdn.net/luckywang1103/article/details/73863043)
* 定義在 [linux/stringify.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/stringify.h) 中

        #define __stringify_1(x...)	#x
        #define __stringify(x...)	__stringify_1(x)

* 根據同樣 header file 中的註解，這樣的兩層結構是為了 `allows the parameter to be a macro itself`，亦即允許 `__stringify` 傳入之參數為 macro
* [# 及 ## 的用途](https://blog.csdn.net/Richard_LiuJH/article/details/45669207)

| 符號 | 作用 | 舉例 |
| -------- | -------- | -------- |
| # | 表可以轉為 string | 例如 #id 為 "id"，id=6 時(使用 `#define`)<br>#id 等於 "6"
| ## | 表可以連接 | __initcall_##fn##id 等於 __initcall_fnid <br>fn = test_init，id = 6 時(使用 `#define`)<br>__initcall_##fn##id 等於 __initcall_test_init6 |

實驗 1 :

            #include <stdio.h>

            #define _str(x) #x
            #define str(x) _str(x)
            #define x 5

            int main () {
                    printf("%d\n", x);                  // output : 5
                    printf("%s %s\n", str(x), _str(x)); // output : 5 x
            }

實驗 2 :

            #include <stdio.h>

            struct node {
                    int x;
                    char y;
            };

            #define def(a,b) struct node a##_##b;

            int main () {
                    def(create,node);
                    create_node.x = 5;
                    printf("%d\n", create_node.x);    // output : 5
            }

### insmod 對應操作
>insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀 [color=#7F8580]
* [strace](https://linuxtools-rst.readthedocs.io/zh_CN/latest/tool/strace.html) 可以追蹤一個系統呼叫之參數、return value、execution time 等。
* 使用 strace 追蹤 insmod 之行為，結果如下

    $ sudo strace insmod fibdrv.ko
    execve("/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7fffc8dd46f8 /* 17 vars */) = 0
    brk(NULL)                               = 0x562bf3deb000
    access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
    access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
    openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
    fstat(3, {st_mode=S_IFREG|0644, st_size=178409, ...}) = 0
    mmap(NULL, 178409, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6b78caa000
    close(3)                                = 0
    access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
    openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
    read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\260\34\2\0\0\0\0\0"..., 832) = 832
    fstat(3, {st_mode=S_IFREG|0755, st_size=2030544, ...}) = 0
    mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f6b78ca8000
    mmap(NULL, 4131552, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f6b786be000
    mprotect(0x7f6b788a5000, 2097152, PROT_NONE) = 0
    mmap(0x7f6b78aa5000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e7000) = 0x7f6b78aa5000
    mmap(0x7f6b78aab000, 15072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f6b78aab000
    close(3)                                = 0
    arch_prctl(ARCH_SET_FS, 0x7f6b78ca9540) = 0
    mprotect(0x7f6b78aa5000, 16384, PROT_READ) = 0
    mprotect(0x562bf36d3000, 8192, PROT_READ) = 0
    mprotect(0x7f6b78cd6000, 4096, PROT_READ) = 0
    munmap(0x7f6b78caa000, 178409)          = 0
    brk(NULL)                               = 0x562bf3deb000
    brk(0x562bf3e0c000)                     = 0x562bf3e0c000
    uname({sysname="Linux", nodename="x555", ...}) = 0
    openat(AT_FDCWD, "/lib/modules/4.15.0-45-generic/modules.softdep", O_RDONLY|O_CLOEXEC) = 3
    fcntl(3, F_GETFL)                       = 0x8000 (flags O_RDONLY|O_LARGEFILE)
    fstat(3, {st_mode=S_IFREG|0644, st_size=540, ...}) = 0
    read(3, "# Soft dependencies extracted fr"..., 4096) = 540
    read(3, "", 4096)                       = 0
    close(3)                                = 0
    openat(AT_FDCWD, "/proc/cmdline", O_RDONLY|O_CLOEXEC) = 3
    read(3, "BOOT_IMAGE=/boot/vmlinuz-4.15.0-"..., 4095) = 119
    read(3, "", 3976)                       = 0
    close(3)                                = 0
    getcwd("/home/bauuuu1021/fibdrv", 4096) = 24
    stat("/home/bauuuu1021/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=8288, ...}) = 0
    openat(AT_FDCWD, "/home/bauuuu1021/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
    fstat(3, {st_mode=S_IFREG|0664, st_size=8288, ...}) = 0
    mmap(NULL, 8288, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6b78cd3000
    finit_module(3, "", 0)                  = 0
    munmap(0x7f6b78cd3000, 8288)            = 0
    close(3)                                = 0
    exit_group(0)                           = ?
    +++ exited with 0 +++

* 倒數第五行的 `finit_module` 根據 [man finit_module(2)](https://linux.die.net/man/2/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() 之描述如下
>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
>

>TODO 找出相對應程式碼 [color=red]

>當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？ Linux 核心做了什麼事呢？ [color=#7F8580]
>
* 根據 [kernel documentation](https://www.kernel.org/doc/htmldocs/kernel-hacking/routines-init-again.html)
>**The module_init() macro defines which function is to be called at module insertion time** (if the file is compiled as a module), or at boot time: if the file is not compiled as a module the module_init() macro becomes equivalent to __ initcall(), which through linker magic ensures that the function is called on boot.
>
亦即被 module_init() 當作參數之 function 會在 module 被載入 kernel 時執行

>補充：
>module 有兩種運作方式：
>
> 1. 編譯成可動態鏈結的 module，透過 `insmod` 指令來動態載入及初始化。
> 2. 編譯成靜態與 kernel 鏈結，系統啟動過程中進行初始化。
>
>題目要求為 `insmod` 之行為，因此此處僅對 dynamic linking 做探討
>[name=bauuuu1021][color=#0ABAB5]
### 解讀針對特定應用場景使用 Linux 核心的案例
>這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)
>[color=#7F8580]
>

>* [meaning of entropy](https://en.wikipedia.org/wiki/Entropy_(computing))
>In computing, **entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data.** This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators.
>
* 加密隨機性
* 加密隨機性一直是 kernel random number community 中廣泛討論的議題，依賴 timing of user input 或 disk interrupt 的加密常遇到以下問題：這些 event 不一定會發生(或在需要呼叫時發生)
* Stephan Müller 提出一個可預期一定發生的方案：CPU execution time jitter
* 對 hardware-level 沒有特別存取能力的 attacker 無法預測 jitter，使 jitter 成為一個良好的加密來源
* random bit generator
* 透過 `jent_measure_jitter()` 來實現，回傳一個 1-bit 結果
* function 內容為將一段 buffer 內的數值都加一，完成後比較當下的及前一個 timestamp，得到差值 `delta`
* 將 `delta` fold down to a single bit，即為結果
* 值得注意的是 folding operation 固然有較快的操作方式，但根據相關程式碼中的註解：不應該在此執行編譯最佳化(`optimization for the jitter random number generator (RNG) must be turned off`)，以避免得到不佳的亂數(`avoid the possibility of getting bad random numbers`)
* 與 kernel 關係
* kernel's deterministic random bit generator (DRBG) is currently initialized by making a call to `get_random_bytes()`.
In certain circumstances that pool **will not have been seeded from enough events to provide the entropy required.**
>註 **currently:**
>以上敘述發表於 April 29, 2015[name=bauuuu1021][color=#0ABAB5]
>
* Müller 的 patch 中建立了一個只能被 kernel 存取的 kernel_pool。藉此避免了 **user-space program 透過不斷讀取 `/dev/random` 來消耗系統產生的 entropy** 這種 DoS 攻擊
## 改善效率
>在 GitHub 上 fork fibdrv，目標是改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
> * 在 Linux 核心模組中，可用 ktime 系列的 API
> * 在 userspace 可用 clock_gettime 相關 API
> * 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
> * 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
> * 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
>
>[color=#7F8580]

:::warning
發現問題：
* 1~92 之 fib number 皆正確，但 93~100 之 fib number 皆為 <br>fib(92) = 7540113804746346429，顯然有問題
* 現在用來儲存 fib number 的 data type 為 `long long int`，而 `LLONG_MAX` = 9223372036854775807($2^{63}-1$) 恰比 fib(92) 略大，故 fib(93) 就超出 `long long int` 可表示的範圍。<br>然而就算將 data type 改為 `unsigned long long`，`ULLONG_MAX` = 18446744073709551615 ($2^{64}-1$) 也會很快不敷使用 (未到達 fib(100) )，因此必須用其他方式解決。
[name=bauuuu1021]
:::
* 參考過去大三上 OS 課程的[作業](https://github.com/bauuuu1021/mailbox)，也是需要修改 kernel module 及探討 kernel <-> user 間的溝通。
* 那時是將要從 kernel 傳回 user space 的資料放在 `char *buf` 中

        strcpy(buf,temp);

>不佳，建議使用 `strncpy` [color=#0ABAB5][name=(寫完一年多後的)bauuuu1021]
>

在 user space 再從 `buf` 中取出結果

        int ret_val = read(sysfs_fd,buf,sizeof(buf));
        // buf .....

* 將作法移植過來卻發現會導致程式中止

        make[1]: Leaving directory '/home/bauuuu1021/fibdrv'
        sudo ./client > out
        Killed
        Makefile:36: recipe for target 'check' failed
        make: *** [check] Error 137

* 用 gdb 逐條檢查發現，在

      sz = read(fd, buf, 8);

發生

      Program terminated with signal SIGKILL, Killed.

代表它所對應到 kernel function `fib_read()` 出了問題
* `fib_read()` 中有一行

    	strncpy(buf, (char*)&runtime, strlen((char*)&runtime));

拿掉這行 `$ make check` 即正確執行
* 在 fibdrv.c 中無法 include <string.h>，故猜測 string.h 中所定義的函式無法在此檔案中執行
* 驗證：

            char a[6];
            memset(a, 0, sizeof(a));
            strncpy(a, "aaaaa", 5);
            printk(KER_INFO "%s", a);

可正常執行且印出正確字串，猜測錯誤。
* 跟強者我同學討論後，被建議使用 [copy to user](http://huenlil.pixnet.net/blog/post/23507650-%5B%E8%BD%89%5Duser-space-kernel-space-%E7%9A%84io%E8%A7%80%E5%BF%B5%E5%8F%8A%E5%AF%A6%E4%BD%9C)，主要原因為在 kernel space 對傳入的 pointer 指向的記憶體空間進行操作，可能造成非預期的結果。詳可見 [johnnylord](https://hackmd.io/s/rkLAuRs8V) 同學的共筆。
* 需 `#include <linux/uaccess.h>`
* [ktime_t](https://github.com/spotify/linux/blob/master/include/linux/ktime.h) 在不同架構(32&64 bits)的電腦上的行為可能不同，在我的實驗環境上 (64 bits) 是被當作 `long long int`，因此測量時間傳回 user space 後要使用 `atoll` 將 buf 內容轉回數值
* 執行結果
* kernel space 及 user space 所需的時間比較圖
* kernel space 在整個過程中所佔的時間，以百分比表示

* 因此從發 request 到收到結果的過程中，真正花在計算上的時間 (costing time on kernel space) 只有大約 20%

## 參考資料
* [GitHub link](https://github.com/bauuuu1021/fibdrv)
* [作業要求](https://hackmd.io/s/SJ2DKLZ8E)
* [2019q1 HW2 作業區](https://hackmd.io/s/rygjaEK8V)
* [HTML color codes](https://htmlcolorcodes.com/)
* [linux 模組化機制](https://blog.csdn.net/yueqian_scut/article/details/46694229)
* [The first 300 Fibonacci numbers](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html)
* [limit of each data type](http://www.cplusplus.com/reference/climits/)
* [Gnuplot](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg)
###### tags: `bauuuu1021`, `sysprog`,`2019spring`