# 2020q1 Homework2 (fibdrv)
contributed by < `oucs638` >

## 作業說明

- [fibdriv](https://hackmd.io/@sysprog/linux2020-fibdrv)

- - -

## 開發環境

$ uname -a
Linux oucs638-ROG-Strix-G731GU-G731GU 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              12
On-line CPU(s) list: 0-11
Thread(s) per core:  2
Core(s) per socket:  6
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping:            13
CPU MHz:             800.015
CPU max MHz:         4500.0000
CPU min MHz:         800.0000
BogoMIPS:            5199.98
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            12288K
NUMA node0 CPU(s):   0-11
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 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 ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad 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 md_clear flush_l1d arch_capabilities

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

- - -

## 作業要求

### 自我檢查清單
- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

### 目標
- 回答上述==自我檢查清單==的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

- 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
- 原本的程式碼只能列出到 Fibonacci(100) 而且==部分輸出是錯誤的數值==，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
- 務必研讀上述 ==Linux 效能分析的提示== 的描述，降低效能分析過程中的干擾;
- 在 Linux 核心模組中，可用 ktime 系列的 API;
- 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API;
- 分別[用 gnuplot 製圖](https://hackmd.io/@sysprog/Skwp-alOg)，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
- 嘗試解讀上述實驗的時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響。可修改 VFS 函式，允許透過寫入 `/dev/fibonacci` 裝置檔案來變更不同的 Fibonacci 求值的實作程式碼。
- 用 printk 固然方便，但其執行時間易受各種因素而不穩定，除了透過統計來觀察，也可改用核心的 sysfs 介面，後者可讓我們自行宣告 show 和 store 介面來提供讀寫操作，可參見 [Sample kobject implementation](https://elixir.bootlin.com/linux/latest/source/samples/kobject/kobject-example.c) (注意: 切換到對應的 Linux 核心版本)。
- 逐步最佳化 Fibonacci 的執行時間，引入[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number) 提到的策略，並善用 [clz / ffs](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令 (Linux 核心有對應的包裝函式)，過程中都要充分量化

- - -

## 參考資料

- [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)

- - -

## 實作紀錄

- 檢查 Linux 核心版本

$ uname -r
5.3.0-40-generic

- 安裝 linux-headers 於開發環境，並確認

$ sudo apt install linux-headers-`uname -r`
$ dpkg -L linux-headers-5.3.0-40-generic | grep "/lib/modules"
/lib/modules
/lib/modules/5.3.0-40-generic
/lib/modules/5.3.0-40-generic/build

- 檢查使用者身份

$ whoami
oucs638
$ sudo whoami
root

- 安裝工具

$ sudo apt install util-linux strace gnuplot-nox

- 編譯並測試

$ make check
Git hooks are installed successfully.

cc -o client client.c
make -C /lib/modules/5.3.0-40-generic/build M=/home/oucs638/GitHub/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.3.0-40-generic'
  CC [M]  /home/oucs638/GitHub/fibdrv/fibdrv.o
/home/oucs638/GitHub/fibdrv/fibdrv.c: In function ‘fib_sequence’:
/home/oucs638/GitHub/fibdrv/fibdrv.c:30:5: warning: ISO C90 forbids variable length array ‘f’ [-Wvla]
     long long f[k + 2];
     ^~~~
  Building modules, stage 2.
  MODPOST 1 modules
  CC      /home/oucs638/GitHub/fibdrv/fibdrv.mod.o
  LD [M]  /home/oucs638/GitHub/fibdrv/fibdrv.ko
make[1]: Leaving directory '/usr/src/linux-headers-5.3.0-40-generic'
make unload
make[1]: Entering directory '/home/oucs638/GitHub/fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory '/home/oucs638/GitHub/fibdrv'
make load
make[1]: Entering directory '/home/oucs638/GitHub/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/oucs638/GitHub/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/oucs638/GitHub/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/oucs638/GitHub/fibdrv'
 Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

- 觀察產生的 fibdrv.ko 核心模組

$ modinfo fibdrv.ko
filename:       /home/oucs638/GitHub/fibdrv/fibdrv.ko
version:        0.1
description:    Fibonacci engine driver
author:         National Cheng Kung University, Taiwan
license:        Dual MIT/GPL
srcversion:     24DC5FB7E7608AF16B0CC1F
depends:        
retpoline:      Y
name:           fibdrv
vermagic:       5.3.0-40-generic SMP mod_unload