---
tags: NCKU Linux Kernel Internals
---
# fibdrv
[H03: fibdrv](https://hackmd.io/@sysprog/linux2020-fibdrv)
完整的程式內容請參考: [Github](https://github.com/RinHizakura/fibdrv/tree/rin)
## 費氏數列: Fast Doubling
[Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 是計算費氏數列的手法，其遞迴式如下: (細節請參閱連結 or 原作業 Hackmd)
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
對應的程式設計為:
```c=
int digit(unsigned long long n){
int bits;
for (bits = 32; bits > 0; --bits) {
if (n & 0x80000000) break;
n <<= 1;
}
return bits;
}
int fast_fib(unsigned int n){
int a = 0, b = 1;
for (int i = digit(n); i > 0; i--){
int t1 = a * (2 * b - a);
int t2 = b * b + a * a;
a = t1;
b = t2;
if ( (n >> (i -1)) % 2 == 1){
t1 = a + b; // m++
a = b;
b = t1;
}
}
return a;
}
```
其中 `digit()` 用來計算 `n` 的二進位表示式共有多少位元(從最左邊的 1 數到最後一位的位元數)，其實就是 **counting leading zero** 的變形。
:::warning
:warning: [counting leading zero](https://hackmd.io/9tGfpJtLTwyyOzDvlyJS2w?view#Count-Leading-Zero) 中有討論到許多更快的 clz 作法
:::
:::warning
:warning: 需注意這個函式只能處理在 int 範圍中的 `fib(n)`
:::
## 事前準備
取得程式碼並執行
```
$ git clone https://github.com/sysprog21/fibdrv
$ cd fibdrv
$ make check
```
可能會遇到錯誤訊息：
```
insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted
```
```
$ dmeseg
Lockdown: insmod: unsigned module loading is restricted; see man kernel_lockdown.7
```
這是因為 `EFI_SECURE_BOOT_SIG_ENFORCE` kernel config 被使用。當 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) 將 secure boot 關閉，之後就可以成功執行。
## 效能分析的前置準備
### 限定執行的核心
以使用 core 5 號為例，修改 /etc/default/grub
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=5"
```
```
$ sudo update-grub
$ sudo reboot
```
再透過 taskset 把程式限定在特定核心中執行
```
$ taskset 0x20 ./a.out
```
可以寫一個無限迴圈測試，透過 `top ` (執行後按 `1`) 察看，成功的話，不執行時 core 5 應該不會被使用，執行時則反之。
### 抑制 address space layout randomization (ASLR)
```
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
:::warning
將 address space layout 隨機化是為了安全考量，需注意原本的值是 2，測試後最好還是設定回來。
:::
### scaling_governor
指定 CPU 5 全速執行
```
$ sudo sh -c "echo performance > /sys/devices/system/cpu/cpu5/cpufreq/scaling_governor"
```
:::warning
為了 CPU 的穩定，測試後最好還是設定回原本的 powersave。
:::
### turbo mode
針對 Intel 處理器，關閉 turbo mode
```
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
:::warning
測試後設定回原本的 0。
:::
## 費式數列的正確性
執行程式可以注意到，因為 fib(93) 已經超過 long long 可以表達的範圍，我們需要設計大數的運算。
定義大數的資料結構如下，可根據 [fibdrv 核心模組內部](https://hackmd.io/@sysprog/linux2020-fibdrv#fibdrv-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%E5%85%A7%E9%83%A8) 的說明來實作大數運算，細節請直接參考上面的 Github 連結。
```c=
struct BigN{
unsigned long long lower, upper;
char num[128];
};
```
也要記得要修改 macro
```c=
#define MAX_LENGTH 100 //或者更大
```
:::warning
:warning:需注意我們只是把 64 bits 擴展到 128 bits 表示! 經計算其實也只能表示到 `fib(185)`。如果要再擴展就要使用更多的 `unsigned long long` 來紀錄。
:::
此外，由於原本的 `fib(n)` 結果是有點投機的透過 read 的回傳值取得，然而現在我們改成使用資料結構紀錄 `fib(n)` ，因此需要修改得到輸出的方法。
使用函式 `printBigN()` 先將 kernel 內部的大數資料結構做更新，再透過 `copy_to_user()` 將資料從 kernel 搬運到 userspace。需注意 [copy_to_user()](https://www.kernel.org/doc/htmldocs/kernel-api/API---copy-to-user.html) 的 return 值是**無法被 copy 的 byte 數量**!
:::info
:bell: 因為 lower 和 upper 是紀錄二進位，特別設計了 `printBigN(struct BigN *x)` 將十六進位轉成十進位。注意`num[128]` 結構只是為了 debug 時方便觀察，需呼叫 `printBigN(struct BigN *x)` 才會根據 lower/upper 更新。
轉換的方法並未充足考慮執行效率，有待改善。
:::
修改後，可以得到正確的結果。
:::warning
:warning: 此外，原本的 `struct BigN *f` 是用 [variable length array](https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html) 分配空間的，由於 VLA 是把空間分配在 stack 上，根據編譯器的實作也會有差異，當 k 太大時可能會有問題！ 建議改用 [kmalloc](https://www.kernel.org/doc/html/latest/core-api/mm-api.html#the-slab-cache) 動態配置空間會比較安全。
:::
## Fast doubling 的效益
修改計算費式數列的演算法成 Fast doubling。
為了做到 Fast doubling，除了大數加法之外，我們還需要實作大數的減法和乘法(可以參考 [Catch and compute overflow during multiplication of two large integers
](https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers)的討論，或者參考我寫的 [BigN.h](https://github.com/RinHizakura/fibdrv/blob/rin/BigN.h))
此外，由於我們的費式數列是在 kernel 中計算的，如果要評估兩個演算法的時間差異的話，最好根據[核心模式的時間測量](https://hackmd.io/@sysprog/linux2020-fibdrv#%E6%A0%B8%E5%BF%83%E6%A8%A1%E5%BC%8F%E7%9A%84%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F)所說在 kernel 中透過 [The high-resolution timer API](https://lwn.net/Articles/167897/) 來計算時間。下圖為兩個演算法 fib(n) 隨 n 成長的時間差異，可以看到 fast doubling 手法確實對計算所需時間帶來極高的效益。
需注意如果是從 userspace 的角度評測 `read()` function call 的時間，`read()` 的整個呼叫不只有我們想估計的 `fib()` 本身(例如還有很費時的 `copy_to_user()`)，如果時間瓶頸不是費式數列的計算的話，我們可能會錯誤的估計時間，需要特別小心。
:::danger
:question: 代解問題：
naive 方法在某些點會有高峰，成鋸齒狀而非線性上升，原因為何？是否是因為 kmalloc 背後的 buddy allocator? cache 的影響？
:::
## clz / ctz 的效益
原本計算 fib(n) 中 n 的二元表示式是透過自己寫的 `digit()`，我們可以換成 GCC 的 Built-in Function: `__builtin_clzll(x)` 來得到更快的計算。
需注意根據[文件](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)的說明:
> Built-in Function: int __builtin_clz (unsigned int x)
> Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
x 為 0 時是會發生 undefined behavior 的！ 需注意要另外進行調整。比較的結果如下：
可以看到使用 `__builtin_clz` 對執行時間產生的效益。
## 優化運算成本
* TODO
- [ ] 思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
## kernel 與 user 的執行時間差異
如圖為使用 fast doubling + clz builtin + bigNum 的執行時間，可以見到程式運行在 kernel 的時間，以及傳遞到 userspace 的時間開銷。
可以見到，在 fib(n) 中的 n 很小時，傳遞到 userspace 的時間成本反而會大過計算 fib 的時間。
### 使用統計方法降低誤差
為避免實驗誤差產生的極值，可以善用統計方法來進行效能分析。
重複相同的實驗 100 次後，對於 fib(n) 中的每個 n 會有 100 筆計算而得的執行時間，得到 95% 區間的值後，取平均作為 fib(n) 的執行時間。
:::warning
偶然發現有論文提到使用 standard deviation around the mean(即這裡使用的方法) 的問題，並建議使用 absolute deviation around the median(MAD)。
這裡暫時偷懶不探討，不過實際使用時或許是需要考量的因素。[附上連結](https://core.ac.uk/download/pdf/206095228.pdf)
:::
從圖可以見到，利用此種分析方式可以減少圖表的鋸齒狀，得到更可信的結果
## kernel module 的 reference count
透過 lsmod 指令，可以看到存在於 kernel 中的 module，以及包括：
* 模組名稱(Module)；
* 模組的大小(size)；
* 此模組是否被其他模組所使用 (Used by)。
的資訊
其中 Used by 的資訊從何而來呢？可以在 [linux/include/linux/module.h](https://elixir.bootlin.com/linux/v5.8/source/include/linux/module.h#L360) 底下看到 `refcnt` 變數，不難猜想其中的關聯。
```c=
struct module {
...
#ifdef CONFIG_MODULE_UNLOAD
/* What modules depend on me? */
struct list_head source_list;
/* What modules do I depend on? */
struct list_head target_list;
/* Destruction function. */
void (*exit)(void);
atomic_t refcnt;
#endif
...}
```
### atomic_t
refcnt 透過 atomic operation 來達到 kernel synchronization ，避免在多核心的硬體下對同一變數的同時操作導致非預期的行為，在 [include/linux/types.h](https://elixir.bootlin.com/linux/v5.8/source/include/linux/types.h#L168)
```c=
typedef struct {
int counter;
} atomic_t;
```
首先可以看到其型態的 atomic_t，乍看之下只是一個整數型態的 counter 而已。
:::warning
在新版的 linux kernel 中，counter 已經沒有 volitile 的修飾詞。經過 volitile 修飾的變數並非 atomic，只是用來避免編譯器的優化導致非預期的行為(可參照維基百科的範例)。根據 [wiki](https://en.wikipedia.org/wiki/Volatile_(computer_programming)) 上的敘述:
> Operations on volatile variables are not atomic, nor do they establish a proper happens-before relationship for threading. This is specified in the relevant standards (C, C++, POSIX, WIN32), and volatile variables are not threadsafe in the vast majority of current implementations. Thus, the usage of volatile keyword as a portable synchronization mechanism is discouraged by many C/C++ groups.
此外，在[這裡](https://stackoverflow.com/questions/34747475/atomic-t-in-linux)有提到把 atomic_t 定義成一個只有單一成員的 struct 而非 `typedef int atomic_t` 可以避免錯誤的 casting
:::
再針對不同的硬體，去設計一系列的 atomic operation API，例如 [arch/arm/include/asm/atomic.h](https://elixir.bootlin.com/linux/latest/source/include/linux/atomic.h)。
### lsmod 實作原理
我們可以透過 strace 來觀察 lsmod 使用的 system call
```
openat(AT_FDCWD, "/sys/module/pinctrl_intel/refcnt", O_RDONLY|O_CLOEXEC) = 3
read(3, "1\n", 31) = 2
read(3, "", 29) = 0
close(3)
```
可以從輸出觀察到這樣的 pattern，明顯的可以得知實作就是去讀取 `/sys/module` 底下的檔案撈出的 refcnt。
也就是說，
```
$ cat /sys/module/fibdrv/refcnt
0
```
可以毫不意外的讓我們得到跟 lsmod 中 Used by 相同的數值
### refcnt 在 kernel 中的實作
執行
```
$ strace insmod fibdrv.ko
```
可以看到載入模組相關的 system call [finit_module](https://linux.die.net/man/2/finit_module)。事實上，載入模組有兩種 system call: `init_module()` 和 `finit_module()`。
根據 document 所說:
> **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. This system call requires privilege.
> The **finit_module()** system call is like init_module(), but reads the module to be loaded from the file descriptor fd. It is useful when the authenticity of a kernel module can be determined from its location in the file system; in cases where that is possible, the overhead of using cryptographically signed modules to determine the authenticity of a module can be avoided. The param_values argument is as for init_module().
`init_module()` 是比較舊的方法。一個載入 module 的程式可以大致分成3個部份:
1. 打開 ELF image file
2. 讀檔或者透過 mmap() 把檔案載入到記憶體中
3. 呼叫 init_module()
這個 system call 的缺點是，由於得到 image file 的 file descriptor 的方式與模組載入的 interface 是分開的，operating system 很難基於 filesystem 去驗證 module 的可信度。
此問題的解決方案是：刪除上述的第二個步驟。而改成讓程式打開 file，並將返回的 file descriptor 傳遞給 kernel 的方式來操作 module。如此一來，kernel 就可以透過對 file descriptor 的操作讀取 module image。此方式可以確保 kernel module 僅從系統的 read-only，經過 root file system 驗證的位置載入，減少不必要的 module signatures 產生的 overhead。這就是 `finit_module()`
順帶一提，glibc 並沒有對於這兩個 system call 設計專屬的 wrapper，因此需要利用如 `#define finit_module(fd, param_values, flags) syscall(__NR_finit_module, fd, param_values, flags)` 這樣的介面去呼叫。
```c=
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
...
return load_module(&info, uargs, flags);
}
```
在 [/kernel/module.c](https://elixir.bootlin.com/linux/v5.8/source/kernel/module.c#L3776) 可以看到對應的 system call，可以看到主要是透過 load_module 來載入 kernel
#### `load_module`
```c=
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
...
/* Now module is in final location, initialize linked lists, etc. */
err = module_unload_init(mod);
...
/* Link in to sysfs. */
err = mod_sysfs_setup(mod, info, mod->kp, mod->num_kp);
...
```
其中與 refcnt 有關聯的部份分別是 `module_unload_init` 與 `mod_sysfs_setup`
#### `module_unload_init`
```c=
static int module_unload_init(struct module *mod)
{
/*
* Initialize reference counter to MODULE_REF_BASE.
* refcnt == 0 means module is going.
*/
atomic_set(&mod->refcnt, MODULE_REF_BASE);
INIT_LIST_HEAD(&mod->source_list);
INIT_LIST_HEAD(&mod->target_list);
/* Hold reference count during initialization. */
atomic_inc(&mod->refcnt);
return 0;
}
```
在 module_unload_init 的地方，初始化 refcnt(MODULE_REF_BASE = 1，refcnt)、 source_list(依賴自己的 module list)和 target_list(自己依賴的 module)
#### `mod_sysfs_setup`
```c=
static int mod_sysfs_setup(struct module *mod,
const struct load_info *info,
struct kernel_param *kparam,
unsigned int num_params)
{
...
err = mod_sysfs_init(mod);
if (err)
goto out;
mod->holders_dir = kobject_create_and_add("holders", &mod->mkobj.kobj);
if (!mod->holders_dir) {
err = -ENOMEM;
goto out_unreg;
}
err = module_param_sysfs_setup(mod, kparam, num_params);
if (err)
goto out_unreg_holders;
err = module_add_modinfo_attrs(mod);
if (err)
goto out_unreg_param;
...
}
```
在 mod_sysfs_setup:
* `mod_sysfs_init` 中呼叫 `kobject_init_and_add` 在 sysfs 底下建立 **/sys/module/{module name}**
* `kobject_create_and_add` 在 **/sys/module/{module name}** 下建 holders 目錄
* `module_param_sysfs_setup` 在 **/sys/module/{module name}** 下建 parameters 目錄(在 fibdrv.c 裡沒有註冊 parameters，所以實際上不會產生)
```c=
static int module_add_modinfo_attrs(struct module *mod)
{
...
for (i = 0; (attr = modinfo_attrs[i]); i++) {
if (!attr->test || attr->test(mod)) {
memcpy(temp_attr, attr, sizeof(*temp_attr));
sysfs_attr_init(&temp_attr->attr);
error = sysfs_create_file(&mod->mkobj.kobj,
&temp_attr->attr);
if (error)
goto error_out;
++temp_attr;
}
}
...
}
```
* `module_add_modinfo_attrs` 會透過 `sysfs_create_file` ，從 `modinfo_attrs` 添加相關的 attribute，建立 module 的 attribute 檔。[這裡](https://elixir.bootlin.com/linux/v5.8/source/kernel/module.c#L1265) 可以看到 `modinfo_attrs` 的結構包含 `modinfo_refcnt`，而其定義為:
```c=
static struct module_attribute modinfo_refcnt =
__ATTR(refcnt, 0444, show_refcnt, NULL);
```
```c=
#define __ATTR(_name, _mode, _show, _store) { \
.attr = {.name = __stringify(_name), \
.mode = VERIFY_OCTAL_PERMISSIONS(_mode) }, \
.show = _show, \
.store = _store, \
}
```
```c=
static ssize_t show_refcnt(struct module_attribute *mattr,
struct module_kobject *mk, char *buffer)
{
return sprintf(buffer, "%i\n", module_refcount(mk->mod));
}
```
```c=
/**
* module_refcount - return the refcount or -1 if unloading
*
* @mod: the module we're checking
*
* Returns:
* -1 if the module is in the process of unloading
* otherwise the number of references in the kernel to the module
*/
int module_refcount(struct module *mod)
{
return atomic_read(&mod->refcnt) - MODULE_REF_BASE;
}
```
可以看到 refcnt 通過 macro `__ATTR` 被建立，其中的 `show` 介面會印出 `mod->refcnt - MODULE_REF_BASE`
:::info
還記得初始化的時候是初始成 MODULE_REF_BASE = 1 嗎，然後因為包含自己再去加 1 嗎？因為 0 是用來表示 module 將要被 unload，所以實際的 reference count 是 `mod->refcnt - 1`)
:::
### reference
[Loading modules from file descriptors](https://lwn.net/Articles/519010/)
[How to load Linux kernel modules from C code?](https://stackoverflow.com/questions/5947286/how-to-load-linux-kernel-modules-from-c-code)
## mutex 的用途
## debug 技巧
一種簡單的作法是使用 [`printk`](https://en.wikipedia.org/wiki/Printk)，再透過 [dmesg](https://man7.org/linux/man-pages/man1/dmesg.1.html) 察看內容，但其執行時間易受各種因素而不穩定，額外的 printk 可能導致程式的運作行為和不加 printk 有差異。
### sysfs 介面
Sign in with Wallet
Connect another wallet