# 2019q1 Homework2 (fibdrv)
contributed by < `grant7163` >
###### tags: `sysprog2019_q1`
## 作業要求
依據 [F03: fibdrv](https://hackmd.io/HIn9ZuKFS62quuQjSO0eEw?view)
* 回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
* 在 Linux 核心模組中，可用 ktime 系列的 API
* 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API
* 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
* 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
* 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
* 逐步最佳化 Fibonacci 的執行時間，引入 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 提到的策略，並善用 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，過程中都要充分量化
## 實驗環境
```shell
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
製程： 9
CPU MHz： 900.044
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5616.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s)： 0-7
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
$ cat /proc/version`
Linux version 5.4.0-67-generic (buildd@lcy01-amd64-025) (gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)) #75-Ubuntu SMP Fri Feb 19 18:03:38 UTC 2021
$ cat /etc/lsb-release`
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=20.04
DISTRIB_CODENAME=focal
DISTRIB_DESCRIPTION="Ubuntu 20.04.2 LTS"
```
## 自我檢查
- [ ] 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
以 MODULE_AUTHOR 為例，在範例程式中我們指定 module 的作者。
```c
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
```
在 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/module.h) 中找到這幾個巨集都對應到一個 MODULE_INFO() 巨集。
若將巨集展開應得 `MODULE_INFO(author, "National Cheng Kung University, Taiwan")`
```clike
#define MODULE_AUTHOR(_author) MODULE_INFO(author, _author)
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
```
繼續將如下敘述展開得 `__MODULE_INFO(author, author, "National Cheng Kung University, Taiwan")`
```c
/* Generic info of form tag = "info" */
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
```
依據 [linux/moduleparam.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/moduleparam.h#L21) 中的定義
`__MODULE_INFO()` 用來宣告一個唯一的變數名稱，值等於 __stringify(tag) "=" info。
* `__used` ： `__attribute__((__used__))` ([/include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler-gcc.h#L139))
* `__attribute__` : 關鍵字將一些訊息告訴編譯器
* section(".modinfo") ： 將訊息放在 .modinfo 區段裡
* unused : 變數可能不會被使用，不要發出警告訊息
* aligned(1) : 最小要求1 byte 的對齊
```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 */
#define __MODULE_INFO(tag, name, info) \
struct __UNIQUE_ID(name) {}
#endif
```
繼續將上述巨集展開
```c
static const char __UNIQUE_ID(author)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(author) "=" "National Cheng Kung University, Taiwan"
```
依據 [include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/compiler-gcc.h#L208) 中的定義
__UNIQUE_ID() 用來產生一個唯一的變數名稱。
* `__COUNTER__` : 每當遇到使用到 `__COUNTER__` 就會將其值加一。
```c
# define __UNIQUE_ID(prefix) #define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
```
依據 [/include/linux/compiler_types.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler_types.h#L53) 中的定義
__PASTE() 用來連接二個符號。
* 當 macro 代入參數是要被字串化或符號連接時，參數將不會被展開，此時需要一個間接的 macro 先將參數展開。
> 3.10.6 [Argument Prescan](https://gcc.gnu.org/onlinedocs/cpp/Argument-Prescan.html)
> Macro arguments are completely macro-expanded before they are substituted into a macro body, unless they are stringized or pasted with other tokens.
```clike
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)
```
依據 [include/linux/stringify.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/stringify.h#L10) 中的定義
__stringify() 用來字串化。
* 同 __PASTE() 需作二次 macro
```clike
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
實驗確認一下用來轉為字串化的巨集。
```clike=
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)
#define STR abc
#define abc_QQ 123
#define STR_QQ 456
int main(int argc, char *argv[])
{
printf("__stringify: %s \n", __stringify(STR));
printf("__stringify_1: %s \n", __stringify_1(STR));
printf("__PASTE: %d \n", __PASTE(STR,_QQ));
printf("___PASTE: %d \n", ___PASTE(STR,_QQ));
printf("line: %d \n", __LINE__);
return 0;
}
```
印出結果符合預期。
```shell
__stringify: abc
__stringify_1: STR
__PASTE: 123
___PASTE: 456
line: 18
```
做最後的展開能夠得到以下的結果
```clike
static const char __UNIQUE_ID_author0[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= "author=National Cheng Kung University, Taiwan"
```
`section` 會特別將此 variable 放到指定的 ELF section 中，這邊為 `.modinfo`，從如下顯示的資訊可以看到 author 的資訊確實被寫入到 `.modinfo` section 中。
```
$ objdump -s fibdrv.ko
...
Contents of section .modinfo:
0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0020 6920656e 67696e65 20647269 76657200 i engine driver.
0030 61757468 6f723d4e 6174696f 6e616c20 author=National
0040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
0070 504c0000 00000000 73726376 65727369 PL......srcversi
0080 6f6e3d34 42373436 37453631 43414238 on=4B7467E61CAB8
0090 32354539 35364446 38330000 00000000 25E956DF83......
00a0 64657065 6e64733d 00726574 706f6c69 depends=.retpoli
00b0 6e653d59 006e616d 653d6669 62647276 ne=Y.name=fibdrv
00c0 00766572 6d616769 633d342e 31382e30 .vermagic=4.18.0
00d0 2d31362d 67656e65 72696320 534d5020 -16-generic SMP
00e0 6d6f645f 756e6c6f 61642000 mod_unload .
...
```
### insmod 執行動作
使用 strace 追蹤 insmod 執行過程中做了哪些事。
從輸出訊息可以看到一個關鍵字 finit_module。
```shell
$ sudo strace insmod fibdrv.ko
...
openat(AT_FDCWD, "/home/grant7163/github/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=8288, ...}) = 0
mmap(NULL, 8288, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6375753000
finit_module(3, "", 0) = 0
munmap(0x7f825840f000, 8288) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
`$ 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. The param_values argument is as for init_module().
>
> init_module() loads an ELF image into kernel space, performs any necessary symbol relo‐cations, initializes module parameters to values provided by the caller, and then runs the module's init function.
依據 [busybox/modutils/insmod.c](https://elixir.bootlin.com/busybox/latest/source/modutils/insmod.c#L48) 中的程式碼
將指定檔案代入並使用 parse_cmdline_module_options() 解析 insmod command 後面的參數。
```clike=
int insmod_main(int argc UNUSED_PARAM, char **argv)
{
char *filename;
int rc;
IF_FEATURE_2_4_MODULES(
getopt32(argv, INSMOD_OPTS INSMOD_ARGS);
argv += optind - 1;
);
filename = *++argv;
if(!filename)
bb_show_usage();
rc = bb_init_module(filename, parse_cmdline_module_options(argv, /*quote_spaces:*/ 0));
if(rc)
bb_error_msg("can't insert '%s': %s", filename, moderror(rc));
return rc;
}
```
依據 [busybox/modutils/modutils.c](https://elixir.bootlin.com/busybox/latest/source/modutils/modutils.c#L194) 中的程式碼
使用 open 打開指定的檔案並回傳一個 fd，最後將 fd 代入到 finit_module 並呼叫 system call，發現跟使用 strace 輸出訊息中會呼叫到 finit_module() 一致。
至此 user space 的程式就執行完成了，接著透過 system call 進入到 kernel space。
```c=
#define finit_module(fd, uargs, flags) syscall(__NR_finit_module, fd, uargs, flags)
int FAST_FUNC bb_init_module(const char *filename, const char *options)
{
...
#ifdef __NR_finit_module
{
int fd = open(filename, O_RDONLY | O_CLOEXEC);
if(fd >= 0) {
rc = finit_module(fd, options, 0) != 0;
close(fd);
if (rc == 0)
return rc;
}
}
#endif
...
}
```
依據 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3846) 中的程式碼
先檢查是否是有效 module，最後會呼叫到 load_module()。
```clike=
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
struct load_info info = { };
loff_t size;
void *hdr;
int err;
err = may_init_module();
if (err)
return err;
pr_debug("finit_module: fd=%d, uargs=%p, flags=%i\n", fd, uargs, flags);
if (flags & ~(MODULE_INIT_IGNORE_MODVERSIONS
|MODULE_INIT_IGNORE_VERMAGIC))
return -EINVAL;
err = kernel_read_file_from_fd(fd, &hdr, &size, INT_MAX,
READING_MODULE);
if (err)
return err;
info.hdr = hdr;
info.len = size;
return load_module(&info, uargs, flags);
}
```
依據 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3642) 中的程式碼
對 module 進行記憶體配置，檢查與載入 module 並最後會呼叫 do_init_module()
```c=
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
struct module *mod;
...
return do_init_module(mod);
...
}
```
依據 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L3426) 中的程式碼
```c=
static noinline int do_init_module(struct module *mod)
{
...
/* Start the module */
if (mod->init != NULL)
ret = do_one_initcall(mod->init);
...
}
```
依據 [/init/main.c](https://elixir.bootlin.com/linux/v4.15/source/init/main.c#L820) 中的程式碼
最後終於在這裡執行到我們的函式了(init_fib_dev)
```c=
int __init_or_module do_one_initcall(initcall_t fn)
{
...
if (initcall_debug)
ret = do_one_initcall_debug(fn);
else
ret = fn();
...
}
```
- [ ] 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
在原始碼中可以看到`module_init`,`module_exit` 函式
```c=
static int __init init_fib_dev(void)
{
// ...
}
static void __exit exit_fib_dev(void)
{
// ...
}
module_init(init_fib_dev);
module_exit(exit_fib_dev);
```
依據 [include/linux/module.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/module.h#L85)
發現 `module_init` 分別依據有無定義 `MODULE` 來區分實作的方式
```C=
#ifndef MODULE
#define module_init(x) __initcall(x);
#else /* MODULE */
...
/* Each module must use one module_init(). */
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __copy(initfn) __attribute__((alias(#initfn)));
...
#endif
```
依據 [include/linux/init.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/init.h#L199)
#### 無定義`MODULE`的實作方式
`__initcall` 會展開為 `__define_initcall`，宣告一個 `initcall_t`(function pointer) 的變數並指向我們寫的`init_fib_dev`函式
```shell=
typedef int (*initcall_t)(void);
#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;
```
使用 gcc 的 `-E` 參數觀察讓編譯器只做完前置處理後就停止，從如下前置處理的程式碼發現 `module_init` 展開使用的是沒定義 `MODULE` 的方式 ==(沒符合預期，因為變數存儲的位置會在`.initcall`(kernel init 才會使用到)，推測 gcc -E 命令並不是把他編譯成 kernel module)==
:::warning
請閱讀 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)，留意 compiler driver 的作用
:notes: jserv
:::
```c
$gcc -E fibdrv.c -I/path/
static initcall_t __initcall_init_fib_dev6 __attribute__((__used__)) __attribute__((__section__(".initcall6" ".init"))) = init_fib_dev;;;
static exitcall_t __exitcall_exit_fib_dev __attribute__((__used__)) __attribute__((__section__(".exitcall.exit"))) = exit_fib_dev;;
```
#### 有定義`MODULE`的實作方式
檢查資料型態是否正確並宣告一個 `init_module` 的變數
* `__inittest()` 是為了檢查函數的資料型態是否符合 `initcall_t` ，如果不是的話在編譯階段就會發出警告訊息
* `__attribute__(alias())` 將 `init_module()` 設為 `initfn` 的別名
```clike
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __attribute__((alias(#initfn)));
```
依據 [include/linux/compiler-gcc.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/compiler-gcc.h#L128) 中的定義
```clike
#define __maybe_unused __attribute__((unused))
```
以 module_init(init_fib_dev) 為例，最後會被展開成如下 :
```clike
#define module_init(init_fib_dev) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return init_fib_dev; } \
int init_module(void) __attribute__((alias("init_fib_dev")));
```
在 fibdrv.c 中 init_fib_dev() 宣告為 __init 屬性。
依據 [/include/linux/init.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/init.h#L43) 中的定義
__init 用來指定放到 .init.text 區段裡。
```clike
#define __init __section(.init.text) __cold __latent_entropy
```
為了觀察整個編譯過程，不要讓編譯時期產生的中間檔被刪除，在 Makefile 中的 gcc 選項加入 `-save-temps`
```c
static inline __attribute__((__gnu_inline__)) __attribute__((__unused__)) __attribute__((patchable_function_entry(0, 0))) initcall_t __attribute__((__unused__)) __inittest(void) { return init_fib_dev; } int init_module(void) __attribute__((__copy__(init_fib_dev))) __attribute__((alias("init_fib_dev")));;
static inline __attribute__((__gnu_inline__)) __attribute__((__unused__)) __attribute__((patchable_function_entry(0, 0))) exitcall_t __attribute__((__unused__)) __exittest(void) { return exit_fib_dev; } void cleanup_module(void) __attribute__((__copy__(exit_fib_dev))) __attribute__((alias("exit_fib_dev")));;
```
依據 [linux kernel makefile](https://www.kernel.org/doc/html/latest/kbuild/modules.html) 說明
若要建立一個外部 kernel module，能用如下語法來實現
* obj-m : 編譯器會從 `<module_name>.c` 生成 `<module_name>.o`，最後透過連結器生成 `<module_name>.ko`
```
obj-m := <module_name>.o
$ make -C /lib/modules/`uname -r`/build M=$PWD
```
當執行編譯之後會產生一個 fibdrv.mod.c 檔
* 宣告一個 global 變數(__this_module)並設定 struct 中的資料
* .init = init_fib_dev
* .exit = cleanup_module
* 將變數放在 .gnu.linkonce.this_module 區段裡
```clike=
__visible struct module __this_module
__attribute__((section(".gnu.linkonce.this_module"))) = {
.name = KBUILD_MODNAME,
.init = init_module,
#ifdef CONFIG_MODULE_UNLOAD
.exit = cleanup_module,
#endif
.arch = MODULE_ARCH_INIT,
};
```
根據上述程式碼的解析，推論 __this_module 應該會是在呼叫 load_module() 時被載入，回頭仔細看 load_module() 中哪邊有執行到。
依據 [/kernel/module.c](https://elixir.bootlin.com/linux/v4.15/source/kernel/module.c#L2950) 中的程式碼
發現在 layout_and_allocate() 中的 setup_load_info() 會取得 .gnu.linkonce.this_module 的位址。
```shell
static struct module *setup_load_info(struct load_info *info, int flags)
{
...
info->index.mod = find_sec(info, ".gnu.linkonce.this_module");
if (!info->index.mod) {
pr_warn("%s: No module found in object\n",
info->name ?: "(missing .modinfo name field)");
return ERR_PTR(-ENOEXEC);
}
/* This is temporary: point mod into copy of data. */
mod = (void *)info->sechdrs[info->index.mod].sh_addr;
...
}
```
- [ ] 試著執行 `$ readelf -a fibdrv.ko`，觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
Executable and Linking Format 簡稱為 ELF，作為目前最常用的標準檔案格式 (object file, executable file, share object... etc)。
ELF 可大致分為 3 個部分：
依據 `$ man modinfo 8` 說明
> modinfo extracts information from the Linux Kernel modules given on the command line. If the module name is not a filename, then the /lib/modules/version directory is searched, as is also done by modprobe(8) when loading kernel modules.
使用 modinfo 命令觀察模組資訊
```
$ modinfo fibdrv.ko
filename: /home/grant/workspace/jserv_training/2020_q3/fibdrv/fibdrv.ko
version: 0.1
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: 611A7CBA45EA14A2FCC57E1
depends:
name: fibdrv
vermagic: 5.8.0-1006-raspi SMP preempt mod_unload aarch64
```
如上敘 `MODULE_INFO()` 系列的巨集會將模組資訊存在 `.modinfo` 區段，透過使用 readelf 指令觀察 fibdrv.ko，在 section 的部分確實有 `.modinfo` 的區段
```shell
$ readelf -a fibdrv.ko
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: REL (Relocatable file)
Machine: AArch64
Version: 0x1
Entry point address: 0x0
Start of program headers: 0 (bytes into file)
Start of section headers: 7968 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 0 (bytes)
Number of program headers: 0
Size of section headers: 64 (bytes)
Number of section headers: 31
Section header string table index: 30
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .text PROGBITS 0000000000000000 00000040
000000000000020c 0000000000000000 AX 0 0 16
...
[10] .modinfo PROGBITS 0000000000000000 00000600
00000000000000e4 0000000000000000 A 0 0 1
[11] .eh_frame PROGBITS 0000000000000000 000006e8
0000000000000114 0000000000000000 A 0 0 8
[12] .rela.eh_frame RELA 0000000000000000 00001c50
00000000000000a8 0000000000000018 I 28 11 8
[13] .note.gnu.pr[...] NOTE 0000000000000000 00000800
0000000000000020 0000000000000000 A 0 0 8
[14] .note.gnu.bu[...] NOTE 0000000000000000 00000820
0000000000000024 0000000000000000 A 0 0 4
[15] .note.Linux NOTE 0000000000000000 00000844
0000000000000018 0000000000000000 A 0 0 4
[16] .data PROGBITS 0000000000000000 00000860
0000000000000020 0000000000000000 WA 0 0 8
[17] .rela.data RELA 0000000000000000 00001cf8
0000000000000030 0000000000000018 I 28 16 8
[18] __patchable_[...] PROGBITS 0000000000000000 00000880
0000000000000030 0000000000000000 WA 0 0 8
[19] .rela__patch[...] RELA 0000000000000000 00001d28
0000000000000090 0000000000000018 I 28 18 8
[20] .gnu.linkonc[...] PROGBITS 0000000000000000 000008c0
00000000000003c0 0000000000000000 WA 0 0 64
[21] .rela.gnu.li[...] RELA 0000000000000000 00001db8
0000000000000030 0000000000000018 I 28 20 8
[22] .plt PROGBITS 00000000000003c0 00000c80
0000000000000001 0000000000000000 WAX 0 0 1
[23] .init.plt NOBITS 00000000000003c1 00000c81
0000000000000001 0000000000000000 WA 0 0 1
[24] .text.ftrace[...] PROGBITS 00000000000003c2 00000c81
0000000000000001 0000000000000000 WAX 0 0 1
[25] .bss NOBITS 0000000000000000 00000c88
0000000000000018 0000000000000000 WA 0 0 8
...
```
使用 objdump 命令在更詳細觀察 `.modinfo` 區段裡面存放的內容，
```
$objdump -s fibdrv.ko
...
Contents of section .modinfo:
0000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0020 6920656e 67696e65 20647269 76657200 i engine driver.
0030 61757468 6f723d4e 6174696f 6e616c20 author=National
0040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
0070 504c0073 72637665 7273696f 6e3d3631 PL.srcversion=61
0080 31413743 42413435 45413134 41324643 1A7CBA45EA14A2FC
0090 43353745 31006465 70656e64 733d006e C57E1.depends=.n
00a0 616d653d 66696264 72760076 65726d61 ame=fibdrv.verma
00b0 6769633d 352e382e 302d3130 30362d72 gic=5.8.0-1006-r
00c0 61737069 20534d50 20707265 656d7074 aspi SMP preempt
00d0 206d6f64 5f756e6c 6f616420 61617263 mod_unload aarc
00e0 68363400 h64.
...
```
可以看當執行 strace insmod fibdrv.ko 後，在第 3 行開啟 fibdrv.ko 這個檔案並得到其 file descriptor 為 3。並且在第 6 行傳入 finit_module 中。
```clike=
$ sudo strace insmod fibdrv.ko
...
openat(AT_FDCWD, "/home/grant7163/github/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=8288, ...}) = 0
mmap(NULL, 8288, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6375753000
finit_module(3, "", 0) = 0
munmap(0x7f825840f000, 8288) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
- [ ] 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)
- [ ] 查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
- [ ] [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
- [ ] `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
VFS 提供一種統一的檔案系統介面，方便使用者操作不同的裝置或檔案時也可以使用一致的方式存取。
Linux 的裝置驅動程式大致分為 Character Device Driver 、 Block Device Driver 、 Network Device Driver。
在使用裝置前需要對其定義一些 file operation，並將其註冊到 kernel 中。
依據 [/include/linux/fs.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/fs.h#L572) 的定義
```shell
struct inode {
// ...
dev_t i_rdev;
// ...
union {
struct pipe_inode_info *i_pipe;
struct block_device *i_bdev;
struct cdev *i_cdev;
char *i_link;
unsigned i_dir_seq;
};
// ...
} __randomize_layout;
```
[include/linux/cdev.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/cdev.h#L14)
```shell
struct cdev {
struct kobject kobj;
struct module *owner;
const struct file_operations *ops;
struct list_head list;
dev_t dev;
unsigned int count;
} __randomize_layout;
```
[/include/linux/fs.h](https://elixir.bootlin.com/linux/v4.15/source/include/linux/fs.h#L1692)
```shell
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;
```
以本次作業為例，宣告一個 file_operations 的資料型態並設定一些對應到 VFS 操作的函式(fib_read, fib_write...)。
當在 user space 中呼叫到 read 的 system call 時，藉由 VFS 將其對應到 fib_read。
```clike
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,
};
```
```clike=
static int __init init_fib_dev(void)
{
...
fib_cdev = cdev_alloc();
if (fib_cdev == NULL) {
printk(KERN_ALERT "Failed to alloc cdev");
rc = -1;
goto failed_cdev;
}
cdev_init(fib_cdev, &fib_fops);
rc = cdev_add(fib_cdev, fib_dev, 1);
...
}
```
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
mutex 是一種用於多執行緒中，防止多個執行緒同時對同一共享資源（全域變數）進行讀寫的保護機制。
利用本次 fibdrv.c 來實驗有無使用 mutex 的差異。
將原本 fib_write 函式改為每呼叫一次就對 global 變數(testdata)做加一的動作並 printf 出來
```clike
long long testdata = 0;
static ssize_t fib_write(struct file *file, const char *buf, size_t size, loff_t *offset)
{
return testdata++;
}
```
有 mutex 的版本
若有2個執行緒執行 fibdrv，做到一半會跳出程式(其中一個 thread 會 open fail 跳出程式)，所以這邊先列單一執行緒的情況。
從 log 可以看出，在單一執行緒時確實會執行100次加一的動作。
```shell
Writing to /dev/fibonacci, thread 1 returned the sequence 0
Writing to /dev/fibonacci, thread 1 returned the sequence 1
Writing to /dev/fibonacci, thread 1 returned the sequence 2
Writing to /dev/fibonacci, thread 1 returned the sequence 3
Writing to /dev/fibonacci, thread 1 returned the sequence 4
Writing to /dev/fibonacci, thread 1 returned the sequence 5
Writing to /dev/fibonacci, thread 1 returned the sequence 6
Writing to /dev/fibonacci, thread 1 returned the sequence 7
Writing to /dev/fibonacci, thread 1 returned the sequence 8
Writing to /dev/fibonacci, thread 1 returned the sequence 9
Writing to /dev/fibonacci, thread 1 returned the sequence 10
Writing to /dev/fibonacci, thread 1 returned the sequence 11
Writing to /dev/fibonacci, thread 1 returned the sequence 12
Writing to /dev/fibonacci, thread 1 returned the sequence 13
Writing to /dev/fibonacci, thread 1 returned the sequence 14
Writing to /dev/fibonacci, thread 1 returned the sequence 15
...
...
...
Writing to /dev/fibonacci, thread 1 returned the sequence 93
Writing to /dev/fibonacci, thread 1 returned the sequence 94
Writing to /dev/fibonacci, thread 1 returned the sequence 95
Writing to /dev/fibonacci, thread 1 returned the sequence 96
Writing to /dev/fibonacci, thread 1 returned the sequence 97
Writing to /dev/fibonacci, thread 1 returned the sequence 98
Writing to /dev/fibonacci, thread 1 returned the sequence 99
Writing to /dev/fibonacci, thread 1 returned the sequence 100
```
無 mutex 的版本
先把 fibdrv.c 中的 mutex_trylock() and mutex_unlock() 註解掉。
在測試程式中建立一個 thread ，使用同一個 fibdrv 並都呼叫 fib_write() 100次。
```clike=
void *thread_function(void *arg)
{
int fd2;
long long sz;
char write_buf[] = "testing writing";
int offset = 100;
fd2 = open(FIB_DEV, O_RDWR);
if (fd2 < 0) {
perror("Failed to open character device");
exit(1);
}
for (int i = 0; i <= offset; i++) {
sz = write(fd2, &write_buf, strlen(write_buf));
printf("Writing to " FIB_DEV ", thread 2 returned the sequence %lld\n", sz);
}
}
int main(int argc, char *argv[])
{
int fd;
long long sz;
pthread_t mythread;
char write_buf[] = "testing writing";
int offset = 100;
if ( pthread_create( &mythread, NULL, thread_function, NULL) )
{
printf("error creating thread.");
return 1;
}
fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
for (int i = 0; i <= offset; i++) {
sz = write(fd, &write_buf, strlen(write_buf));
printf("Writing to " FIB_DEV ", thread 1 returned the sequence %lld\n", sz);
}
if ( pthread_join ( mythread, NULL ) )
{
printf("error joining thread.");
return 1;
}
return 0;
}
```
從 log 可以看出，當 thread 1 在對 testdata 做加一時，期間 testdata 也會被 thread 2 做加一的動作，導致最後的執行結果不符合預期。
```shell
Writing to /dev/fibonacci, thread 1 returned the sequence 0
Writing to /dev/fibonacci, thread 1 returned the sequence 1
Writing to /dev/fibonacci, thread 1 returned the sequence 2
Writing to /dev/fibonacci, thread 1 returned the sequence 3
Writing to /dev/fibonacci, thread 1 returned the sequence 4
Writing to /dev/fibonacci, thread 1 returned the sequence 5
Writing to /dev/fibonacci, thread 1 returned the sequence 6
Writing to /dev/fibonacci, thread 2 returned the sequence 7
Writing to /dev/fibonacci, thread 2 returned the sequence 9
Writing to /dev/fibonacci, thread 2 returned the sequence 10
Writing to /dev/fibonacci, thread 2 returned the sequence 11
Writing to /dev/fibonacci, thread 1 returned the sequence 8
Writing to /dev/fibonacci, thread 1 returned the sequence 13
Writing to /dev/fibonacci, thread 1 returned the sequence 14
Writing to /dev/fibonacci, thread 1 returned the sequence 15
...
...
...
Writing to /dev/fibonacci, thread 1 returned the sequence 195
Writing to /dev/fibonacci, thread 1 returned the sequence 196
Writing to /dev/fibonacci, thread 1 returned the sequence 197
Writing to /dev/fibonacci, thread 1 returned the sequence 198
Writing to /dev/fibonacci, thread 1 returned the sequence 199
Writing to /dev/fibonacci, thread 1 returned the sequence 200
Writing to /dev/fibonacci, thread 1 returned the sequence 201
```
- [ ] 許多現代處理器提供了 [clz / ctz]( https://en.wikipedia.org/wiki/Find_first_set ) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說
## 前置測試
從老師的 [github]( https://github.com/sysprog21/fibdrv ) 上 fork 完 fibdrv 之後，先來測試看看。
到目標資料夾下，輸入如下指令。
可以印出 Fibonacci 計算的結果，不過在 offset 大於92之後，輸出的數值都沒有變化了
```shell
$ make check
$ make load
$ sudo ./client
...
Reading from /dev/fibonacci at offset 91, returned the sequence 4660046610375530309.
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 94, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 95, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 96, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 97, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 98, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 99, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 100, returned the sequence 7540113804746346429.
...
```
## 開發紀錄
使用 [clock_gettime](https://man7.org/linux/man-pages/man2/clock_getres.2.html) 與 [ktime](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 分析原始版本的效能
* 在執行 `fib_read` 時使用 `ktime_get` 來計算 fibonacci 運算的耗時。
* 使用 `fib_write` 回傳 fibonacci 運算耗時的資訊
```clike=
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
clock_gettime(CLOCK_MONOTONIC, &start);
sz = read(fd, buf, 1);
ssize_t kt = write(fd, NULL, 0);
clock_gettime(CLOCK_MONOTONIC, &end);
long long elapsed = (long long)(end.tv_sec * 1e9 + end.tv_nsec)
- (start.tv_sec * 1e9 + start.tv_nsec);
printf("%d %lld %ld %lld %lld\n", i, sz, kt, elapsed,
elapsed - kt);
}
```
分別將 user space 與 kernel space 的執行狀況分開來觀察，發現2者在執行過程都會有抖動的現象產生，尤其在 kernel space 最為明顯
### 排除干擾效能分析的因素
先聚焦在 kernelspace 執行的狀況，參考作業說明，使用 `taskset` 命令將程式設定於指定 CPU 核心上執行。
```
$ sudo taskset -c 7 ./client
```
發現並無明顯改善抖動的現象。
嘗試限定 CPU 給特定的程式使用，需在 `/etc/default/grub` 檔案中的 GRUB_CMDLINE_LINUX_DEFAULT 這行新增 `isolcpu=7`，修改完成後需執行 `sudo update-grub` 來更新設定。
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"
```
接著重開機後可透過以下命令確認是否設定成功。
```
$ cat /sys/devices/system/cpu/isolated
7
```
使用 htop 實際觀察所設定的 cpu 核心使用狀況，從下圖中觀察到確實在 cpu 核心8 使用率為0。
跟先前相比發現實驗結果有比較穩定，但還是有少量的抖動存在。
SMP IRQ affinity
將特定的 IRQ# 設定到目標 CPU 核心上，使用如下命令設定 IRQ affinity(需在 root 權限)。
操作說明參考 [linux kernel document](https://www.kernel.org/doc/html/latest/core-api/irq/irq-affinity.html)
```
/proc/irq# echo 7f > default_smp_affinity
```
先透過如下命令觀察 CPU 中斷次數，發現在 CPU 核心7 的中斷源已經很少。
```
$ cat /proc/interrupts
CPU0 CPU1 CPU2 CPU3 CPU4 CPU5 CPU6 CPU7
0: 7 0 0 0 0 0 0 0 IR-IO-APIC 2-edge timer
1: 0 0 0 424 0 0 0 0 IR-IO-APIC 1-edge i8042
8: 0 0 0 0 1 0 0 0 IR-IO-APIC 8-edge rtc0
9: 0 13009 0 0 0 0 0 0 IR-IO-APIC 9-fasteoi acpi
12: 0 0 77 0 0 0 0 0 IR-IO-APIC 12-edge i8042
16: 0 0 0 0 0 0 0 0 IR-IO-APIC 16-fasteoi idma64.0, i801_smbus, i2c_designware.0
17: 0 2329 0 0 0 0 0 0 IR-IO-APIC 17-fasteoi idma64.1, i2c_designware.1
51: 0 0 23 0 0 0 0 0 IR-IO-APIC 51-fasteoi DLL07BE:01
120: 0 0 0 0 0 0 0 0 DMAR-MSI 0-edge dmar0
121: 0 0 0 0 0 0 0 0 DMAR-MSI 1-edge dmar1
123: 0 0 372 3805 0 111 5 0 IR-PCI-MSI 458752-edge aerdrv
124: 0 0 0 0 0 0 0 0 IR-PCI-MSI 460800-edge aerdrv
125: 0 0 2 31 0 0 4 0 IR-PCI-MSI 475136-edge aerdrv
127: 0 0 0 1 1 0 0 0 IR-PCI-MSI 487424-edge aerdrv
128: 0 248 0 394300 0 0 3 0 IR-PCI-MSI 327680-edge xhci_hcd
129: 0 0 0 0 0 20 0 0 IR-PCI-MSI 1572864-edge rtsx_pci
130: 0 0 0 0 0 0 0 0 IR-PCI-MSI 376832-edge ahci[0000:00:17.0]
131: 0 0 0 21 0 0 0 0 IR-PCI-MSI 2097152-edge nvme0q0
132: 26762 0 0 0 0 0 0 0 IR-PCI-MSI 2097153-edge nvme0q1
133: 0 22473 0 0 0 0 0 0 IR-PCI-MSI 2097154-edge nvme0q2
134: 0 0 15449 0 0 0 0 0 IR-PCI-MSI 2097155-edge nvme0q3
135: 0 0 0 31023 0 0 0 0 IR-PCI-MSI 2097156-edge nvme0q4
136: 0 0 0 0 55583 0 0 0 IR-PCI-MSI 2097157-edge nvme0q5
137: 0 0 0 0 0 58363 0 0 IR-PCI-MSI 2097158-edge nvme0q6
138: 0 0 0 0 0 0 35557 0 IR-PCI-MSI 2097159-edge nvme0q7
139: 0 0 0 0 0 0 0 0 IR-PCI-MSI 2097160-edge nvme0q8
140: 0 0 0 0 66 0 0 0 IR-PCI-MSI 360448-edge mei_me
141: 0 6 1 2686 0 4407 358 0 IR-PCI-MSI 32768-edge i915
142: 0 0 0 0 872752 2056 697 0 IR-PCI-MSI 1048576-edge ath10k_pci
143: 0 0 701168 1326 0 0 1943 217 IR-PCI-MSI 524288-edge nvidia
144: 2929 0 0 0 0 0 0 0 IR-PCI-MSI 514048-edge snd_hda_intel:card0
NMI: 158 167 168 109 138 131 133 3 Non-maskable interrupts
LOC: 7011952 6495800 6233315 7039497 7480337 6435815 6430481 43233 Local timer interrupts
SPU: 0 0 0 0 0 0 0 0 Spurious interrupts
PMI: 158 167 168 109 138 131 133 3 Performance monitoring interrupts
IWI: 0 4 2 2 0 0 1 0 IRQ work interrupts
RTR: 0 0 0 0 0 0 0 0 APIC ICR read retries
RES: 4003667 1088375 229983 144618 83451 75995 54095 33 Rescheduling interrupts
CAL: 238325 211469 211385 185093 205656 205184 197364 37791 Function call interrupts
TLB: 335433 343308 338173 358243 342771 345289 339533 0 TLB shootdowns
TRM: 0 0 0 0 0 0 0 0 Thermal event interrupts
THR: 0 0 0 0 0 0 0 0 Threshold APIC interrupts
DFR: 0 0 0 0 0 0 0 0 Deferred Error APIC interrupts
MCE: 0 0 0 0 0 0 0 0 Machine check exceptions
MCP: 257 258 258 258 258 258 258 258 Machine check polls
ERR: 2
MIS: 0
PIN: 0 0 0 0 0 0 0 0 Posted-interrupt notification event
NPI: 0 0 0 0 0 0 0 0 Nested posted-interrupt event
PIW: 0 0 0 0 0 0 0 0 Posted-interrupt wakeup event
```
### Page fault
在如上敘的實驗結果中，userspace 剛開始的部份會特別耗時，參考 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#2020q1-Homework2-fibdrv) 同學中的筆記可能是 page fault 造成的關係。
依據此篇文章 [Threaded RT-application with memory locking and stack handling example](https://rt.wiki.kernel.org/index.php/Threaded_RT-application_with_memory_locking_and_stack_handling_example) 的作法，使用 `getrusage()` 觀察 page fault 是否發生與在程式剛開始時使用 `mlockall()` 將所需的 page 鎖在記憶體當中，已防止 page faults 的發生。
先觀察在未加入 `mlockall()` 函式時 page faults 發生的狀況。
```clike=
int main()
{
...
Detect_pagefault();// printf page fault status
...
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
...
printf("%d %lld %ld %lld %lld\n", i, sz, kt, elapsed, elapsed - kt);
Detect_pagefault();// printf page fault status
}
}
```
從印出來的訊息觀察到在計算第1次 fibonacci 時確實有發生 page fault。
```
min pagefault
0 0 34 1435 1401
min pagefault
1 1 20 1096 1076
2 1 43 1059 1016
3 2 29 1032 1003
4 3 63 1058 995
...
```
上述程式第4行的地方加入 `mlockall()` 函式後是乎沒有改善狀況，在計算第1次 fibonacci 時還是會發生 page fault。
```
min pagefault
0 0 32 1405 1373
min pagefault
1 1 29 1070 1041
2 1 50 1033 983
3 2 28 998 970
4 3 63 1030 967
...
```
### Fast doubling
是一種透過 Q-Matrix 的方法推演而來，概念是使用矩陣乘法將兩個 n 次方矩陣相乘而得，最後推得如下2個公式，分別表示奇偶數。
* $f(2n) = f(n)[2f(n+1) - f(n)]$
* $f(2n+1) = f(n+1)^2 + f(n)^2$
參考 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 此篇文章中的作法
藉由 $F(k)$ 與 $F(k + 1)$ 來計算出 $F(2k)$ 與 $F(2k + 1)$
* 若所求目標 n 為偶數則將 $k = n / 2$ 帶入 $F(k)$ 與 $F(k + 1)$
* 若所求目標 n 為奇數則將 $k = n - 1 / 2$ 帶入 $F(k)$ 與 $F(k + 1)$
以計算 $F(10)$ 為例:
$n = 10，k = 10 / 2 = 5$
$n = 5，k = (5 - 1) / 2 = 2$
$n = 2，k = 2 / 2 = 1$
$n = 1，k = (1 - 1) / 2 = 0$
$n = 0$
由上可以觀察出 $n / 2$ 到0的次數便可知道須計算的次數，又 C 語言的整數除法是使用無條件捨去的方式
```clike=
static long long fib_fd(unsigned int n)
{
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
long long a = 0; // F(0) = 0
long long b = 1; // F(1) = 1
for (unsigned int mask = 1 << (h - 1); mask; mask >>= 1) {
uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) - F(k) ]
uint64_t d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) {
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else {
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
```
從下圖中發現當 n 小於10的情況，原始版本運算時間是比較小的，而當 n 越大時，Fast doubling 版本的運算時間才有明顯的優勢。
又根據上述 Fast doubling 實作的觀察，由 $n / 2$ 的動作在 C 語言中相當於 right shift 1，因此可使用 clz 來計算出 bit 為1的最高位置。
由印出來的 log 觀察 Fibonacci(92) 的16進制為 0x1,11F3,8AD0,840B,F6BF，發現已經超過 64 bits 所能表達的數值了。
### Fibonacci 大數運算
接著將原始版本改成能夠大數運算，使用 struct 將數字分成4個無號 int 來表達大數。
```clike
#define BN_ARRAY_SIZE 4
typedef struct bn
{
uint32_t bn_array[BN_ARRAY_SIZE];
} bn_t;
```
先配置一整塊記憶體空間並初始化為0。
為了顯示個位數是從 LSB 開始，在放入 bn_array 矩陣時先從尾巴開始放。
使用 MAX_VAL 與當下2個數相加的結果比較，若大於 MAX_VAL 則進位。
參考 [kokke github](https://github.com/kokke/tiny-bignum-c?fbclid=IwAR3SGOy8fH2qKPIdrPbtukcugBqYDinXRG5krUryqEhnpspPz-KJLVX5eNc) 的實作
```clike=
#define MAX_VAL (uint64_t) 0xFFFFFFFF
static bn_t *fib_sequence(long long k)
{
uint64_t temp = 0;
int carry = 0;
bn_t *f = kmalloc(sizeof(bn_t) * (k + 2), GFP_KERNEL);
if(f == NULL)
return NULL;
memset(f, 0, sizeof(bn_t) * (k + 2));
f[1].bn_array[BN_ARRAY_SIZE - 1] = 1;
for(int i = 2; i <= k; i++)
{
for(int j = BN_ARRAY_SIZE - 1; j >= 0; j--)
{
temp = (uint64_t) f[i - 1].bn_array[j] + f[i - 2].bn_array[j] + carry;
carry = (temp > MAX_VAL);
f[i].bn_array[j] = (uint32_t) (temp & MAX_VAL);
}
}
return &f[k];
}
```
從 printk 印出來的結果正確，不過需要在修改一下顯示的方式。
```shell
...
[111876.140532] 0000
[111876.140532] 0002
[111876.140532] CD36C2E3
[111876.140533] 2A371480
[111876.140537] 0000
[111876.140538] 0004
[111876.140538] 8879FAF5
[111876.140539] D0623241
[111876.140543] 0000
[111876.140544] 0007
[111876.140544] 55B0BDD8
[111876.140545] FA9946C1
[111876.140549] 0000
[111876.140550] 000B
[111876.140550] DE2AB8CE
[111876.140551] CAFB7902
[111876.140556] 0000
[111876.140556] 0013
[111876.140557] 33DB76A7
[111876.140557] C594BFC3
```
將時間單位 scale 放大，可以發現整體 bign-kernel 耗費時間是略大於 orig-kernel，並當 n 越大 bign-kernel 與 orig-kernel 的耗費時間差也會跟著變大。
將 Fast doubling 演算法與大數運算版本合併
Fast doubling 要使用到乘法，所以先來實作大數乘法。
Sign in with Wallet
Connect another wallet