2023 年 Linux 核心設計/實作課程作業 —— fibdrv

--- title: 2023 年 Linux 核心設計/實作課程作業 —— fibdrv image: https://i.imgur.com/KXUuZLV.png description: 引導學員開發 Linux 核心模組，預期知悉核心模組如何掛載進入 Linux 核心、Virtual File System (VFS) 概況、character device driver 撰寫，和準備對應的測試及效能分析工具 tags: linux2023 --- # L04: fibdrv > 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2023 年系統軟體課程](https://www.facebook.com/groups/system.software2023/) :mega: 返回「[Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表 ## :package: 撰寫 Linux 核心模組請自行參閱以下教材: * 《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》 * [Introduction to Linux kernel driver programming](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf) * [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/) * [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/) ## :dart: `fibdrv`: 可輸出 Fibonacci 數列的 Linux 核心模組 ### 前期準備 :::info 1. 開發環境預期和 ==[lab0](https://hackmd.io/@sysprog/linux2021-lab0)== 相似，如果你剛好重新安裝 Ubuntu Linux，請依據指示將必要的開發套件裝好; 2. ==自本次作業==，我們就有分析應用程式和 Linux 核心效能的需求，==不該在虛擬機器環境== 裡頭測試 (但 [container](https://linuxcontainers.org/) 或 [Linux KVM](https://www.linux-kvm.org/page/Main_Page) 可接受)，否則會有效能偏差的問題 $\to$ 及早在實體機器上安裝好 GNU/Linux; ::: * 自從 Linux 核心 4.4 版以來，Ubuntu Linux 預設開啟 `EFI_SECURE_BOOT_SIG_ENFORCE`，這使得核心模組需要適度的簽章才可掛載進入 Linux 核心，為了後續測試的便利，我們需要將 UEFI Secure Boot 的功能**關閉**，請見 [Why do I get “Required key not available” when install 3rd party kernel modules or after a kernel upgrade?](https://askubuntu.com/questions/762254/why-do-i-get-required-key-not-available-when-install-3rd-party-kernel-modules) * 檢查 Linux 核心版本 ```shell $ uname -r ``` 預期是大於等於 `5.4.0` 的版本，例如 `5.4.0-66-generic`。若在你的開發環境中，核心版本低於 `5.4` 的話，需要更新 Linux 核心，請自行參照相關文件 * 安裝 `linux-headers` 套件 (注意寫法裡頭有 `s`)，以 [Ubuntu Linux 20.04 LTS](https://packages.ubuntu.com/focal/linux-headers-generic) 為例: ```shell $ sudo apt install linux-headers-`uname -r` ``` * 確認 `linux-headers` 套件已正確安裝於開發環境 ```shell $ dpkg -L linux-headers-5.4.0-66-generic | grep "/lib/modules" ``` 預期得到以下輸出: ``` /lib/modules/5.4.0-66-generic/build ``` * 檢驗目前的使用者身份 ```shell $ whoami ``` 預期為「不是 root 的使用者名稱」，例如 `jserv` (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。由於測試過程需要用到 sudo，請一併查驗: ```shell $ sudo whoami ``` 預期輸出是 `root` :notes: 在下列操作中，請==避免用 root 帳號輸入命令==，而該善用 `sudo` :::danger 之後的實驗中，我們會重建 root file system，若濫用 root 權限，很可能就把 GNU/Linux 開發環境不小心破壞 (當然，你還是可重新安裝)，現在開始養成好習慣 ::: * 安裝後續會用得到的工具 ```shell $ sudo apt install util-linux strace gnuplot-nox ``` * 取得原始程式碼 ```shell $ git clone https://github.com/sysprog21/fibdrv $ cd fibdrv ``` * 編譯並測試 ```shell $ make check ``` 預期會看到綠色的 ` Passed [-]` 字樣，隨後是 ``` f(93) fail input: 7540113804746346429 expected: 12200160415121876738 ``` 這符合預期，因為給定的 `fibdrv` 存在==缺陷==。 :::info 就因世界不完美，才有我們工程師存在的空間。 ::: * 觀察產生的 `fibdrv.ko` 核心模組 ```shell $ modinfo fibdrv.ko ``` 預期可得以下輸出: ``` description: Fibonacci engine driver author: National Cheng Kung University, Taiwan license: Dual MIT/GPL name: fibdrv vermagic: 5.4.0-45-generic SMP mod_unload ``` * 觀察 `fibdrv.ko` 核心模組在 Linux 核心掛載後的行為（要先透過 `insmod` 將模組載入核心後才會有下面的裝置檔案 `/dev/fibonacci`）模組載入核心： ```shell $ sudo insmod fibdrv.ko ``` ```shell $ ls -l /dev/fibonacci $ cat /sys/class/fibonacci/fibonacci/dev ``` 新建立的裝置檔案 `/dev/fibonacci`，注意到 `236` 這個數字，在你的電腦也許會有出入。試著對照 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c)，找尋彼此的關聯。 ```shell $ cat /sys/module/fibdrv/version ``` 預期輸出是 `0.1`，這和 [fibdrv.c](https://github.com/sysprog21/fibdrv/blob/master/fibdrv.c) 透過 `MODULE_VERSION` 所指定的版本號碼相同。 ```shell $ lsmod | grep fibdrv $ cat /sys/module/fibdrv/refcnt ``` 這兩道命令的輸出都是 `0`，意味著目前的 [reference counting](https://en.wikipedia.org/wiki/Reference_counting)。 ## 計算 F~93~ (包含) 之後的 Fibonacci 數 (功能受限) 因 F~93~ 之後的運算會發生 overflow，導致無法正確地計算結果。可以使用底下方法計算 big number: * 使用 [GCC `__int128`](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) 型態，或者自行定義的結構: ```cpp struct BigN { unsigned long long lower, upper; }; ``` * 使用數字字串做運算，並運用 [Small/Short String Optimization](http://wdv4758h.github.io/notes/cpp/string-optimization.html)。[實作程式碼](https://github.com/AdrianHuang/fibdrv/tree/big_number)。底下為數字字串加法實作，細節如下: * 確保 `a` 字串長度大於 `b` 字串 * 將 `a` 與 `b` 字串反轉 * 逐字對數字字元做加法運算 * 將得出字串反轉，即得出最終結果 ```cpp static void string_number_add(xs *a, xs *b, xs *out) { char *data_a, *data_b; size_t size_a, size_b; int i, carry = 0; int sum; /* * Make sure the string length of 'a' is always greater than * the one of 'b'. */ if (xs_size(a) < xs_size(b)) __swap((void *) &a, (void *) &b, sizeof(void *)); data_a = xs_data(a); data_b = xs_data(b); size_a = xs_size(a); size_b = xs_size(b); reverse_str(data_a, size_a); reverse_str(data_b, size_b); char buf[size_a + 2]; for (i = 0; i < size_b; i++) { sum = (data_a[i] - '0') + (data_b[i] - '0') + carry; buf[i] = '0' + sum % 10; carry = sum / 10; } for (i = size_b; i < size_a; i++) { sum = (data_a[i] - '0') + carry; buf[i] = '0' + sum % 10; carry = sum / 10; } if (carry) buf[i++] = '0' + carry; buf[i] = 0; reverse_str(buf, i); /* Restore the original string */ reverse_str(data_a, size_a); reverse_str(data_b, size_b); if (out) *out = *xs_tmp(buf); } ``` 如此一來，計算到 F~500~ [(The first 500 Fibonacci numbers )](https://home.hiwaay.net/~jalison/Fib500.html) 也是正確的，結果如下: ```shell $ sudo ./client ... Reading from /dev/fibonacci at offset 499, returned the sequence 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501. Reading from /dev/fibonacci at offset 500, returned the sequence 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125. ... ``` ## 減少 copy to user 傳送的資料量 ### 計算 leading zeros 以 $fib(100) = 354224848179261915075=$ $100110011001111011011011101101010011111000101100101001011111111000011_2$ 為例，先對 $fib(100)$ 取2為底的對數 $\log_2(354224848179261915075) = 68.26322731561805$ 無條件進位後是69，要表達到 $2^{69}-1$ 總共需要 69 個 bit，每個 int 是 32 bit，共需要 3 個 int。 leading zeros 數量為 96-69 = 27個可以用 bitwise 操作最高位的整數來計算 leading zeros。 ```c int clz (int x){ if (x == 0) return 32; int n = 0; if ((x & 0xFFFF0000) == 0) {n += 16; x <<= 16;} if ((x & 0xFF000000) == 0) {n += 8; x <<= 8;} if ((x & 0xF0000000) == 0) {n += 4; x <<= 4;} if ((x & 0xC0000000) == 0) {n += 2; x <<= 2;} if ((x & 0x80000000) == 0) n += 1; return n; } ``` 這個程式碼以二分搜尋法找出 leading zeros，做法如下: * 檢查最高 16 bit 是否全為零，全為零的話將 `x` 的首16個零移除(`x` 左移16 bit) * 檢查以 `fib(100)` 為例，最高位整數儲存的是 `0x00000013` * 0x00000013 & 0xFFFF0000 == 0 ， n = 16 ， x = 0x00130000 * 0x00130000 & 0xFF000000 == 0 ， n = 24 ， x = 0x13000000 * 0x13000000 & 0xF0000000 != 0 * 0x13000000 & 0xC0000000 == 0 ， n = 26 ， x = 0x4C000000 * 0x4C000000 & 0x80000000 == 0 ， n = 27 與之前的計算一致。 ### 計算以 2 為底數的對數以 32 減去 `clz(x)` 可獲得 x 所使用到的 bit 數量。令 $n = 32 - clz(x)$ 使用這些 bit 可表達的範圍為 $2^{n-1}$ ~ $2^n -1$，可得 $n = 32 - clz(x) = \lceil log_2x \rceil$ 且 $n - 1 = 31 - clz(x) = \lfloor log_2x \rfloor$。 `fibdrv` 計算完後，會藉由 `copy_to_user()` 將結果傳回使用者空間。計算leading zeros，並將 `int32` 細分為 4 個位元組，呼叫`copy_to_user()` 時不傳送全為 0 的位元組。 ```c static int my_copy_to_user(const bn *bignum, char __user *buf) { int i = MAX_LENGTH_BN - 1; for (; bignum->num[i] == 0; i--) ; int lzbyte = __builtin_clz(bignum->num[i]) >> 3; size_t size = sizeof(int32_t) * (i + 1) - lzbyte; copy_to_user(buf, bignum->num, size); return size; } ``` 使用 `gcc` 內建函式 `__builtin_clz` 來計算 leading zero bit 數量，其中 ` >> 3` 除以 8 並捨棄餘數換算成 leading zero byte。針對 little-endian 架構，非零的位元組會被存在較低的記憶體位址。以 `fib(100)` 為例，需要 3 個整數，最高位整數是 `0x00000013`，倘若我們只要前 2 個整數以及第 3 個整數的 `0x13` 由 `copy_to_user()` 傳送。 ![](https://hackmd.io/_uploads/By_Il53Cj.png) 將 `copy_to_user()` 的 size 指定為 2 個整數再加 1 個位元組，就不用傳送 leading zero byte。 ![](https://hackmd.io/_uploads/H1yPg9n0i.png) 將複製的 byte 數量作為 `read` 的回傳值傳回 user。 ```c sz = my_copy_to_user(a, buf); ... return sz; ``` 在 `client.c` 中將 `bn` 初始化後以 `memcpy` 複製資料即可。 ```c sz = read(fd, buf, 1); bn a; bn_init(&a); memcpy(a.num, buf, sz); int j = MAX_LENGTH_BN; for (; a.num[j] == 0; j--) ; a.length = j + 1; ... ``` ### 預先計算儲存 $F(n)$ 所需的空間倘若一開始就知道該配置多少空間給 Fibonacci 運算，就能避免空間浪費，或在計算過程中重複呼叫 `krealloc`。首先，我們可用 [Binet 公式](https://en.wikipedia.org/wiki/Fibonacci_number)計算任意 Fibonacci 數列中第 $n$ 個數 $$Fn= \frac{(\phi^n)-(1-\phi)^n}{\sqrt5}$$ $$\phi = \frac{1+\sqrt5}{2} (golden \ ratio)$$ 上式的近似值: $$Fn= \frac{\phi^n}{\sqrt5} \ (since\ (1-\phi)^n\ is\ very\ small\ for\ large\ n)$$ 知道近似值後，我們可使以 10 為底的對數計算其位數。具體如下： $$ Digits = \log_{10}(\frac{\phi^n}{\sqrt5}) \\ Digits = n\log_{10}\phi - (\frac{\log_{10}5}{2}) \\ $$ 當 $n$ 為足夠大的正整數時， $$ F(n)\approx0.4472135955\times1.61803398875^n $$ 將近似值取 2 為底的對數，可得到需要使用的位元數 $$ log_2(0.4472135955\times1.61803398875^n)\approx-1.160964 + n\times0.694242 $$ 再除以 32 可得到需要使用的 `uint32` 數量 $$ (-1.160964 + n\times0.694242)\div32 = -0.036280125 + n\times0.0216950625 $$ Linux 核心無法使用 (正確說法是，不能直接使用) 浮點數運算，因此將算式乘以 $10^{10}$，亦即: $$\lfloor\frac{-362801250 + n\times216950625}{10^{10}}\rfloor+1 $$ 此算式的結果就是該事先配置的 `uint32` 數量。參考的 C 程式: ```c #define BUFFSIZE (8 * sizeof(int) * LENGTH / 3 + 2) #define LOGPHI (0.20898764025) #define LOGSQRT5 (0.34948500216) int main() { int offset = 100; /* TODO: try test something bigger than the limit */ int fd = open(FIB_DEV, O_RDWR); if (fd < 0) { perror("Failed to open character device"); exit(1); } float digits; int size; for (int i = 0; i <= offset; i++) { // calculate how many digits are needed for fib(i) // digits needed for fib(n) = n*LOG(Phi) - (LOG √5) digits = i * LOGPHI - LOGSQRT5; float buf_size = floor(digits / 9); size = (int) buf_size; char *buf = malloc(sizeof(char) * (BUFFSIZE * size)); lseek(fd, i, SEEK_SET); long long time1 = read(fd, buf, 0); long long time2 = read(fd, buf, 1); printf("%d %lld %s\n", i, time1, buf); free(buf); } ``` ## `fibdrv` 核心模組內部觀察使用者層級 (user-level) 的程式如何與 fibdrv 互動: ```cpp fd = open(FIB_DEV, O_RDWR); if (fd < 0) { perror("Failed to open character device"); exit(1); } for (i = 0; i <= offset; i++) { sz = write(fd, write_buf, strlen(write_buf)); printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz); } for (i = 0; i <= offset; i++) { lseek(fd, i, SEEK_SET); sz = read(fd, buf, 1); printf("Reading from " FIB_DEV " at offset %d, returned the sequence " "%lld.\n", i, sz); } ``` `fibdrv` 設計為一個 [character device](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html)，可理解是個能夠循序存取檔案，透過定義相關的函數，可利用存取檔案的系統呼叫以存取 (即 open, read, write, mmap 等等)。因此，使用者層級 (user-level 或 userspace) 的程式可透過 `read` 系統呼叫來得到輸出。接著來看如何實作: ```cpp /* calculate the fibonacci number at given offset */ static ssize_t fib_read(struct file *file, char *buf, size_t size, loff_t *offset) { return (ssize_t) fib_sequence(*offset); } 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, }; ``` 不難發現是透過 `fib_fops` 中的自行定義的 read 來實作讀取操作，而 `fib_read` 最終會回傳 `fib_sequence(*offset)`，因此就是透過讓使用者指定不同的 offest 作為 Fibonacci 數列的 $x$ 然後透過 read 的回傳值輸出 $fib(x)$ 給使用者。在 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模式中，`long long` 僅寬 64 位元，因此若要表示更大的數，需要用兩個以上的變數表示一個數，在這種情況下作加法運算時，若使用 "+" operator ，會發生 overflow，可考慮實作一個更多位元的全加器。 $fib(92)$ 的計算結果用 16 進位表示是 `0x1 11F3 8AD0 840B F6BF`，超過 64 位元整數所夠表示的最大數值，因此考量到要正確輸出 $fib(100)$ 或數列更後面的數值，就必須使用到特製的結構來處理回傳值。以下是參考實作 ```cpp struct BigN { unsigned long long lower, upper; }; ``` 使用 struct BigN 來將一個數字分成兩部份: * 高位的 64 bits 保存 upper 中; * 低位的 64 bit 則是保存在 lower 中; 進行大數加法時，則需要注意 lower 是否需要進位到 upper: ```cpp static inline void addBigN(struct BigN *output, struct BigN x, struct BigN y) { output->upper = x.upper + y.upper; if (y.lower > ~x.lower) output->upper++; output->lower = x.lower + y.lower; } ``` 因為 `x.lower + ~x.lower = ~0`，移項後 `~x.lower = ~0 - x.lower`，亦即 `~x.lower` 表示 `x.lower` 跟最大值(`~0`) 的距離。所以若 `y.lower` 比 `x.lower` 距離最大值的距離還大，就表示相加後會 overflow，需要進位，這時執行 `output->upper++`。 ### [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，本核心模組可將計算出來的 Fibonacci 數讓 `client.c` 程式得以存取。 VFS 提供一統各式檔案系統的共用介面，方便使用者操作不同的裝置或檔案時，可用一致的方式存取。Linux 的裝置驅動程式大致分為: * Character Device Driver; * Block Device Driver; * Network Device Driver; ![](https://i.imgur.com/lvjQxCt.png) 在使用裝置前需要對其定義一些 file operation，並將其註冊到 kernel 中。依據 [/include/linux/fs.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/fs.h#L1692) 中的定義 ```cpp struct file_operations { struct module *owner; loff_t (*llseek) (struct file *, loff_t, int); ssize_t (*read) (struct file *, char __user *, size_t, loff_t *); ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *); ... int (*open) (struct inode *, struct file *); ... int (*release) (struct inode *, struct file *); int (*fsync) (struct file *, loff_t, loff_t, int datasync); int (*fasync) (int, struct file *, int); int (*lock) (struct file *, int, struct file_lock *); ... } __randomize_layout; ``` 此手法可參見 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop)。以本例來說，宣告一個 file_operations 的資料型態並設定一些對應到 VFS 操作的函式 (fib_read, fib_write 等等)。當在使用者模式程式中呼叫到 read 系統呼叫時，藉由 VFS 將其對應到 fib_read。 ```cpp 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, }; ``` 對照 [Linux 核心設計: 檔案系統概念及實作手法](https://hackmd.io/@sysprog/linux-file-system)。 ## :calling: Linux 核心的浮點數運算 Robert Love 在 [Linux Kernel Development](https://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672329468/) 一書論及浮點運算: > No (Easy) Use of Floating Point > When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel. * 解說: [Use of floating point in the Linux kernel](https://stackoverflow.com/questions/13886338/use-of-floating-point-in-the-linux-kernel) Rusty Russell 在 [Unreliable Guide To Hacking The Linux Kernel](https://docs.kernel.org/kernel-hacking/hacking.html) 則說: > The FPU context is not saved; even in user context the FPU state probably won't correspond with the current process: you would mess with some user process' FPU state. If you really want to do this, you would have to explicitly save/restore the full FPU state (and avoid context switches). It is generally a bad idea; use fixed point arithmetic first. #### Lazy FP state restore [CVE-2018-3665](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-3665) 存在於 Intel Core 系列微處理器中，因為 speculative execution（推測執行）技術中的一些缺陷加上特定作業系統中對 FPU（Floating point unit）進行 context switch 所產生的漏洞，允許一個本地端的程式洩漏其他程序的 FPU 暫存器內容。 [Lazy FP state leak](https://en.wikipedia.org/wiki/Lazy_FP_state_restore) 的原理是透過 FPU 的 lazy state switching 機制達成。因為 FPU 和 SIMD 暫存器不一定會在每個任務持續被使用到，因此作業系統排程器可將不需要使用到 FPU 的任務，標註為不可使用 FPU，而不更改裡面的內容。然而，在現今的[亂序執行](https://en.wikipedia.org/wiki/Out-of-order_execution) CPU 中，lazy state switching 裡會設定的 "FPU not available" 可能沒辦法馬上被偵測到，導致我們在 process B，但仍然可以存取到 process A 的 FPU 暫存器內容。基於上述原因，儘管我們在 Linux 核心模式中仍可使用浮點運算，但這不僅會拖慢執行速度，還需要手動儲存/取回相關的 FPU 暫存器，因此核心文件不建議在核心中使用到浮點運算。 ### 浮點運算時間差異比較 [afcidk](https://github.com/afcidk) 透過開發簡單的 Linux 核心模組，來測試在單純的浮點數運算及整數運算花費的時間差異。 > 相關的程式碼可見 [floating.c](https://gist.github.com/afcidk/7178ef368d98ee4b49c7a1acc3704303) ![](https://hackmd.io/_uploads/r1ikMonCj.png) 可見到核心模式中的浮點數運算，時間成本較整數運算高。