2019q1 Homework2 (fibdrv)

contributed by < flawless0714 >

執行環境

OS: Lubuntu 18.04.1 LTS (Bionic Beaver)
Kernel Version: 4.15.0-46-generic

Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping:            9
CPU MHz:             700.030
CPU max MHz:         3500.0000
CPU min MHz:         400.0000
BogoMIPS:            5808.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            4096K
NUMA node0 CPU(s):   0-3
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d

自我檢查清單

• 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀

  • 由於 MODULE_LICENSE 等巨集在第二層後都使用相同巨集，因此以下僅介紹 MODULE_LICENSE。下方程式碼為此巨集所用到的所有巨集，我們由深至淺一一介紹每個巨集。
    • __PASTE(a,b)
      此巨集功用為連接兩字串(## 為連接子(concatenator))，會有兩層的原因是第一層的輸入有可能是巨集字串，假如沒有兩層巨集包裝的話巨集名稱會被當作字串。
    • __UNIQUE_ID(prefix)
      此巨集功用為輸出變數名稱。 其中輸入變數會與 __UNIQUE_ID_ 做連接，之後在與 __COUNTER__ 做連接，最後輸出 __UNIQUE_ID_license__COUNTER。此巨集在 v3.8-rc1 之前為 __module_cat，此外，這個 commit 沒有註明替換原因，找了兩個 kernel 的版控系統都沒看到，不知道是不是只在 mailing list 裡討論。
    • __stringify(x…)
      此巨集功能為將輸入轉為字串後輸出。有兩層包裝的原因同上。
    • MODULE_INFO(tag, info)
      此巨集功能為宣告並定義模組資訊(license, author…)。其中__attribute__ 後的 section("") 為提示編譯器要將此資訊存放在名為 .modinfo 的 section，unused 為告知編譯器不需跳警告 (編譯器會對沒有使用的變數提出警告)，aligned(1) 為告知編譯器此變數在 allocation 時是以每單位(字元)一個 byte 來存放。
    • MODULE_LICENSE(_license)
      此巨集才是我們平常會用到的，參數為 license 名稱的字串，傳遞給下一層的 MODULE_INFO 時會由第一個參數告知此為模組的 license 資訊，並由第二個參數告知 license 名稱。
  ​​​​#define   ___PASTE(a,b) a##b
  ​​​​#define   __PASTE(a,b) ___PASTE(a,b)
  ​​​​
  ​​​​#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
  ​​​​
  ​​​​#define   \_\_stringify\_1(x...) #x
  ​​​​#define   __stringify(x...)   \_\_stringify\_1(x)
  ​​​​
  ​​​​#define   __MODULE_INFO(tag, name, info) \
  ​​​​static   const   char   __UNIQUE_ID(name)[] \
  ​​​​__used __attribute__((section(".modinfo"), unused, aligned(1))) \   
  ​​​​=   __stringify(tag) "=" info
  ​​​​#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
  ​​​​
  ​​​​#define   MODULE_LICENSE(_license) MODULE_INFO(license, _license)
  

  • insmod
    呼叫此程式載入模組後會有以下步驟:
    1. insmod 首先使用模組中的 init_module() 巨集去提示 kernel 有模組要求載入，並將控制權移交給 kernel。
    2. Kernel space 接下來會呼叫 sys_init_module，之後首先檢查使用者是否有權限載入模組。
    3. 通過檢查後，呼叫 load_module()，此函數會配置一段暫時性記憶體空間，並使用 copy_from_user 將模組的 elf 複製到這段記憶體。
    4. 接下來會驗證這個 elf 是否合法。
    5. 通過驗證後，load_module 會開始解譯 elf 檔，並且根據剛才配置的記憶體空間來產生 offset，這個 offset 名為 convenience variable。
    6. 使用者呼叫 insmod 時給的參數也複製進 kernel space 的記憶體。
    7. 此時模組的狀態更新為 MODULE_STATE_COMING。
    8. 開始配置模組在 kernel memory 中的永久記憶體位置(使用 SHF_ALLOC 配置)。
    9. 完成符號解析 (symbol resolution)。
    10. 到此 load_module 的任務已經完成，回傳值為此模組記憶體位置的 reference。
    11. 回傳的 reference 會被插入到 doubly linked list，這個 list 存有所有系統已載入的模組的 reference。
    12. 模組狀態更新為 MODULE_STATE_LIVE。
  • module_init()
    以本次作業的模組為例，此巨集所帶入之參數為 init_fib_dev，此參數為模組初始化函數之記憶體位置。module_init() 展開後的程式碼如下:
    ​​​​​​​​#define module_init(initfn)					\
    ​​​​​​​​static inline initcall_t __maybe_unused __inittest(void)		\
    ​​​​​​​​{ return initfn; }					\
    ​​​​​​​​int init_module(void) __attribute__((alias(#initfn)));
    

    程式碼第 2 行的 initcall_t 為 function type，此處為 pointer of int。__maybe_unused 這個巨集即為前面提過的 gcc attribute，unused。此函數功用為回傳函數的記憶體位置(initfn)。接下來宣告的函數(init_module())為巨集帶入的參數(initfn)的函數別名(當呼叫 init_module() 時其實是呼叫 initfn)。
    接下來是系統呼叫，sys_init_module()。其實這邊接不太起來，沒有看到哪邊執行這個系統呼叫的。以下為此系統呼叫的程式碼:
    ​​​​​​​​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);
    ​​​​​​​​}
    

    開頭看到的巨集 SYSCALL_DEFINE3 在這段程式碼可以把它替換成 asmlinkage long sys_init_module(void __user *umod, unsigned long len, const char __user *uargs);，中間會包那麼多層巨集主要是因為 CVE-2009-2009，這漏洞簡單來說就是系統呼叫時假如有32位元參數要放到64位元暫存器來做傳遞的話，programmer 要手動做 sign extension (ABI 規定的)，假如沒做的話，當 MSB 為1時就有可能拿到非法地址。
    此系統呼叫首先驗證使用者權限與核心是否允許載入模組(may_init_module())，通過驗證後模組(elf)將被複製到 kernel memory (copy_module_from_user())，接下來 kernel 將驗證此 elf、完成 symbol resolution…(load_module())，load_module() 的最後一步 (回傳前)，會呼叫 do_init_module() 做模組啟動的相關作業，至此模組已完成載入並啟動。另外 insmod 用的是 finit_module() 系統呼叫，與 init_module() 做的事情雷同，只是 finit_module() 是用 file descriptor 來載入模組，而 init_module() 用的是帶入參數中的 buffer 來載入。

• 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？

• 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心

• 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter

• 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)

• clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說

• fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例

• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

  • 當有多個 process/thread 在對 fibdrv 做要求時，若沒有 mutex，則 fibdrv 會因為同時處理多個要求而產生錯誤的輸出，mutex 的存在就是要讓 fibdrv 在單位時間內只處理一個要求。

• 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？請列出關鍵程式碼並解說

效能分析

原始程式

• 下圖為 fabonacci 單次計算時間(僅此數據包含上數下數，其餘僅包含上數)、kernel space 計算時間以及 user space 與 kernel space 傳輸時間(user->kernel, kernel->user)。此分析為取100次運算後的平均值，其中可以發現上數平均花費時間較下數少，發現原因是 client.c 中上數執行於下數後，應該是跟快取有關。
  

大數運算版本 (未優化)

• 此版本使用 tiny-bignum-c 作為大數運算的 API，此 API 基本上無最大輸入限制，只要提供適量記憶體(128 bytes 可表示約150位數的輸出)即可使用(根據使用的演算法而定，像是會用到 VLA 宣告 struct bn 的演算法就須注意。過多(kernel process stack 只有 16KB (x86_64))會導致 process 發生 stack overflow)。只是未優化的 fabonacci 效能實在勘憂。

• 下圖為大數運算與原始版本之效能分析圖，其中可以發現兩個版本進行 copy_to_user()(分別為8 bytes 與128 bytes)的花費時間是幾乎相同的，而 fabonacci 計算效能的部份我們可以看到兩者差距之大，同樣都是使用 DP，大數運算版本的時間複雜度是 O(n)，原始版本的時間複雜度則為 O(logn)。
  

• 已知問題

  • 目前輸入大於80(含)後的輸出的是錯誤的(誤差值呈指數成長)。執行於 user space (大數專用測試程式)與 kernel space (module) 都有一樣問題。
  • 當在 kernel space 中計算時，只要輸入在120左右或 bn_kernel_space.h 中的 bn.array 大小大於128 bytes 時(目前僅測試256 bytes)會造成 kernel panic。

    找到問題了，是我的資料結構大到讓 kernel space 的 process 發生 stack overflow (kernel space 的 stack 只有 8KB。在 2.6.37 前，有些 kernel 只有 4KB 的 stack，這樣有好也有壞，但壞大於好，所以最後全部改用 8KB 的 stack，詳見 Kernel Small Stacks)。話說 kdump 剛開始開的時候都捕捉不到 kernel panic，推測是我在設定的時候自己手動去調到 kernel image 的載入 cmd，而污染到其他檔案(因為有試過改回去，但問題依舊)，後來想說都 panic 了，原本開著的東西都被關了，就順便升級一下(4.15.0-46-generic -> 4.15.0-45-generic)，結果問題就解決了…，以下是 kernel 被 kexec 替換前最後一口氣(其中 fibonacci 的訊息是 debug 時插入的)：

    ​​​​​​​​[  234.940933] fibdrv: loading out-of-tree module taints kernel.
    ​​​​​​​​[  234.941043] fibdrv: module verification failed: signature and/or required key missing - tainting kernel
    ​​​​​​​​[  240.368167] <3>The input of fibnacci is 120
    ​​​​​​​​[  240.368170] <3>The line of fibnacci is 112
    ​​​​​​​​[  240.368172] <3>The line of fibnacci is 113
    ​​​​​​​​[  240.368182] BUG: stack guard page was hit at 00000000ef42e155 (stack is 00000000b89c63b9..000000004a314c94)
    ​​​​​​​​[  240.368197] kernel stack overflow (double-fault): 0000 [#1] SMP PTI
    ​​​​​​​​[  240.368203] Modules linked in: fibdrv(OE) ...(已省略) 
    

    以下是 module 中出問題的程式碼，"<3>" 是多加的，原本以為要這樣設 log level 才能在 dmesg 中有發言權，但用錯方法了。其中大家可以發現到 panic 是發生在第117行之後，所以可以推測在配置 local variable 時讓 stack overflow 了。但奇怪的地方是假如 stack 只有 8KB，那我在 fibonacci input 輸入110時也應該會 panic 阿(一個 struct bn 大小為 128bytes，假設參數 k 為110，則共有 110 + 2 + 1 個 struct bn，總計使用記憶體為 113 * 128bytes = 14464bytes，這明顯已經超過 8KB 了，思考原因中…)。

    ​​​​​​​​static void fib_sequence(long long k, char *buf, size_t size)
    ​​​​​​​​{
    ​​​​​​​​    /* FIXME: use clz/ctz and fast algorithms to speed up */
    ​​​​​​​​    printk("<3>""The input of fibnacci is %lld\n", k);
    ​​​​​​​​    ktime_t start, end;
    ​​​​​​​​        printk("<3>""The line of fibnacci is 112\n");
    
    ​​​​​​​​    struct fabo_res res;
    ​​​​​​​​    printk("<3>""The line of fibnacci is 113\n");
    
    ​​​​​​​​    struct bn tmp, f[k + 2];
    ​​​​​​​​    printk("<3>""The line of fibnacci is 114\n");
    
    ​​​​​​​​    bignum_from_int(&f[0], 0);
    ​​​​​​​​    bignum_from_int(&f[1], 1);
    ​​​​​​​​    printk("<3>""The line of fibnacci is 118\n");
    
    ​​​​​​​​    start = ktime_get_ns();
    ​​​​​​​​    for (int i = 2; i <= k; i++) {
    ​​​​​​​​        printk("<3>""The line of fibnacci is 122, iterate number %d\n", i);
    
    ​​​​​​​​        bignum_add(&f[i - 1], &f[i - 2], &tmp);
    ​​​​​​​​        bignum_assign(&f[i], &tmp);
    ​​​​​​​​    }
    ​​​​​​​​    end = ktime_get_ns();
    ​​​​​​​​    printk("<3>""The line of fibnacci is 126\n");
    
    ​​​​​​​​    res.ker_time_ns = end - start;
    
    ​​​​​​​​    bignum_assign(&res.result, &f[k]);
    ​​​​​​​​    printk("<3>""The line of fibnacci is 133\n");
    
    ​​​​​​​​    copy_to_user(buf, &res, size);
    ​​​​​​​​    printk("<3>""The line of fibnacci is 136\n");
    
    ​​​​​​​​}
    

    Wed, Mar 20, 2019 9:15 PM 目前有找到 gcc 的靜態分析功能，-Wframe-larger-than=8192。這個 option 可以監測靜態的 stack 大小，目前設定8192再配上宣告112個 struct bn，gcc 確實有吐出警告。這樣就可以猜測目前 kernel space 的 stack size 大於 8KB，或許我應該試試在執行時期吐出 stack size 到 dmseg。

    Thu, Mar 21, 2019 11:23 PM 找到問題了…，x86_64 的 kernel process stack 是兩個 page (16KB)，所以當我使用了 14464bytes 時，其實還有剩下 1.5KB 左右，而 fibonacci 輸入為120時，使用的記憶體大小至少是 15744bytes，這數字已經 stack frame 的邊界，而且 stack frame 中不只有 stack 而已，還有 thread_struct 等等元件，所以會爆掉不太意外…，目前想到的解法就是換演算法了。

    還以為是區域變數 fib 沒有初始化而造成算到後面出現誤差，結果白高興了，問題依舊，而且假如是這原因的話那誤差應該不會很規律的發生在 80 左右，還有 0~70 這區間應該也會出問題才對..
    Sun, Mar 31, 2019 5:32 PM

大數運算版本 (已優化)

• 目前使用同個大數資料結構，演算法則是使用 Fast doubling，但效能還是不如預期，在 user space 的測試程式輸入為92時計算花費時間約為 6ms，並且在輸入大於80(含)時一樣會有計算錯誤的相同問題，目前推測有極高可能是使用的資料結構造成的問題，解決辦法不是自己幹個資料結構就是找出 tiny-bignum-c 出問題的點。

問題

• 套用 tiny-bignum-c 的 fibonacci 演算法
  不管使用的演算法是 DP 還是 fast doubling，只要輸入超過80左右後輸出會與正確輸出產生指數成長的差距，試過把 tiny-bignum-c 使用的資料結構加大與研究其 API 都還沒發現問題點…

  。

• read() 系統呼叫
  模組中有用到這個系統呼叫，這個系統呼叫的第三個參數 size_t count 代表欲讀取的大小(單位為 byte)。但是 client 呼叫 read() 時回傳的結果往往大於呼叫時傳入的大小(1 byte)，這已經不符合 read() 在 manpage 裡面的說明。

  打問題的時候想到解答…，對模組的 fd 的 read() 已經被包裝成 fib_read()，也就是它不用照規定走，只要 caller 跟 calle 互相有協調好就好。

  這邊說錯了，只有內部實做(將 read() syscall 實做成 fabonacci 數列運算)才能自己定義，回傳型態需要照原本 syscall 的走。譬如說 read() 回傳型態為 ssize_t，那就不能使用 ssize_t 以為的資料型態。原本想直接回傳一個自定義 struct，裡面包含計算時間跟計算結果，看來除非是自己做 syscall，不然就只能乖乖直接從 kernel space 丟出相關數據或對回傳值動手腳了。

筆記

• Kernel Module

  • 不按照順序執行
    Kernel module 不像一般 user space 的程式 (C語言)，大部分都是從 main() 開始執行。kernel module 在初始化的時候會註冊他將 handle 的 request (request 類型定義於 module code 中)，之後只會在收到特定的 request 時才有事做，類似 event-driven 的方式。
  • 不會自動做善後工作
    執行於 user space 的程式在結束時作業系統會去偵測是否有 memory leak，如果有的話會協助釋放該段記憶體。但是 kernel module 在 unload 的時候作業系統並不會做偵測的動作，而若真有 memory leak 的情況發生，那這段記憶體只有在重開機後才能被回收。
  • 無法使用 printf()
    由於 kernel code 無法存取 user space 的 library，所以無法使用。但我們可以使用 printk() 來輸出 user space 可以看到的資訊。
  • 可以被中斷
    Kernel module 可能在同時被多個程式/行程使用，我們需要確保當 module 正在處理多個程式/行程的 request 時被中斷後，其可以對每個程式/行程保有一致性與正確的行為。
  • 有較高的執行權
    Kernel module 較 user space 的程式有較多的 CPU cycles，但同時我們也需注意我們寫的 module 是否對系統整體效能造成影響。
  • 不支援浮點數計算
    在 user space 中，浮點數的計算是 kernel 協助的 (使用 trap 將運算模式從整數轉態到浮點數)。但在 kernel space 使用 trap 是困難的 (division by zero 沒有適當 handler，可能會 kernel panic)。然而，有些 kernel 有提供 fixed point 的浮點數運算。

• 巨集 __stringify(x...)
  此巨集用途為將輸入替換為字串輸出。此巨集有個夥伴名為 _stringify_1(x...)，這種巨集叫做 two levels macro，他可以接受輸入參數同樣也是 macro，如此就可以直接將字串 macro 當做輸入參數，而不使 macro 名稱直接轉為字串。

• GCC aligned()
  指定空間配置時的最小單位。e.g. 使用 int x __attribute__ ((aligned (16))) = 0; 宣告一 int 變數，那麼這個變數大小為 16 bytes。增加 boundary 可以改善 copy 時的效能(編譯器會使用其他複製 instruction)。值得注意的是此 attribute 只能增加不能減少，e.g. int 定義為 4 bytes，那你就不能 align 小於 4 bytes。若真有需要，請使用另個 attribute，packed。

• pointer of array, array of pointers 宣告方式

  ​​​​int* arr[8]; // An array of int pointers.
  ​​​​int (*arr)[8]; // A pointer to an array of integers
  

• module_exit()
  Kernel 的內建模組會直接忽略此呼叫，因為編進核心的模組規定是不會被卸載的。

• copy_to_user() 時間開銷 (TODO)
  根據此研究，從 kernel space 複製資料到 user space 的花費時間為 22ns/byte，所以在做效能分析時假如有包含到此函數的時間開銷，須注意資料大小成長後造成的量測誤差。另外根據不同架構、kernel 版本等等環境因素，可能會有不一樣的花費時間，因此此時間開銷待測試。

參考資料

• C語言巨集、單井號(#)和雙井號(##)
• stringify & stringify_1 解說
• Specifying Attributes of Variables
• What does insmod internally do? (also rmmod)
• System Call
• difference of fopen() and open()
• linux kernel stack size
• Kernel Small Stacks
• Expanding the kernel stack
• Linux-Kernel-Development-Robert-Love 3e. (Single Page Kernel Stacks)

tags: linux2019