# 2020q1 Homework2 (fibdrv)
contributed by < `unknowntpo` >
[TOC]
# 大綱
* [2020 年春季 Linux 核心設計課程作業 —— fibdrv](/@sysprog/linux2020-fibdrv)
* [fibdrv 作業說明筆記](/XNH6vfe1QUiNQnes_VGIEQ)
* [Note: fibdrv code_review](/Q9-sLm0-TvepYw5-5UwRXA)
* fibdrv
* 費氏數列
* What is q-matrix?
* What is the purpose of fast doubling?
* [Binary Exponentiation](https://cp-algorithms.com/algebra/binary-exp.html)
* 硬體加速 F(n) 的手法
* fast - doubling + clz / ctz 指令
* 應用
* 亂數產生
* fibdrv Linux 核心模組撰寫
* 大數運算
* 使用 struct 來包裝大數字
* 分為 upper, lower,
* 型態為 `unsigned long long`
* 注意 lower 是否需進位
* Linux VFS 介面
* 使LKM 在 userspace 計算出的 fib bumber 透過 vfs 讓 userspace 的 `client.c` 存取結果
* file_operation
* ref:
* [你所不知道的 C 語言：物件導向程式設計篇](/@sysprog/c-oop?type=view)
* [Linux 核心設計: 檔案系統概念及實作手法](/@sysprog/linux-file-system?type=view)
* 核心模式的時間測量
* linux kernel 內的兩種計時功能
* timer
* old implementation: jiffies
* [Linux 核心設計: 中斷處理和現代架構考量](/@sysprog/linux-interrupt)
* new: ktime_t
*
* timeout
- [ ] What's the diff?
* client.c 介紹
* why we need copy_to_user?
* 效能分析提示
* cpu affinity
- [ ] how to check?
* `taskset`
- [ ] how to improve affinity?
* 以特定的 CPU 執行程式
* 限定 CPU 給特定的程式使用
* 排除干擾效能分析的因素
* :panda_face: Linux 核心模組掛載機制
- [ ] 檔案 fibdrv.c 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？
* 利用 `##`合併字串
* ref:
* C99/C11 6.4.5 String Literals
* [你所不知道的 C 語言：前置處理器應用篇](/@sysprog/c-preprocessor?type=view)
* Variable attribute `__attribute__ `的作用是什麼？
* insmod 背後的機制
- [ ] 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢?
- [ ] 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
## 自我檢查清單
- [ ] 研讀上述 ==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，到底會發生什麼問題
## :penguin: 作業要求
* 回答上述==自我檢查清單==的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
:::warning
:warning: 如果你在 2020 年 3 月 2 日前，已從 GitHub [sysprog21/fibdrv](https://github.com/sysprog21/fibdrv) 進行 fork，請依據 ==[Alternatives to forking into the same account](https://github.community/t5/Support-Protips/Alternatives-to-forking-into-the-same-account/ba-p/7428)== 一文，對舊的 repository 做對應處置，然後重新 fork
:::
* 在 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 核心有對應的包裝函式)，過程中都要充分量化
# 重現 `Idotrg 同學` 實驗結果
## 遇到問題
```shell
$ sudo ./bpf_scripts.sh
Data will preserved in performance.csv... Press Ctrl+C to stop.
sh: 1: objdump: not found
Failed to compile: stoull
```
### build bpftrace
```shell
/usr/bin/mandb: can't write to /var/cache/man/28345: No space left on device
```
### No space left on device 問題
原來是因為 `lvm` - Logical Volume Management 的關係
> follow the steps on the article below, I just fix the problem
>[time=Mon, Aug 17, 2020 2:24 PM]
[Ubuntu Server 18.04 LVM out of space with improper default partitioning
](https://askubuntu.com/questions/1106795/ubuntu-server-18-04-lvm-out-of-space-with-improper-default-partitioning)
```shell
# We need to resize the logical volume to use all the existing and free space of the volume group
$ lvm
lvm> lvextend -l +100%FREE /dev/ubuntu-vg/ubuntu-lv
lvm> exit
# And then, we need to resize the file system to use the new available space in the logical volume
$ resize2fs /dev/ubuntu-vg/ubuntu-lv
resize2fs 1.44.1 (24-Mar-2018)
Filesystem at /dev/ubuntu-vg/ubuntu-lv is mounted on /; on-line resizing required
old_desc_blocks = 1, new_desc_blocks = 58
The filesystem on /dev/ubuntu-vg/ubuntu-lv is now 120784896 (4k) blocks long.
# Finally, you can check that you now have available space:
$ df -h
Filesystem Size Used Avail Use% Mounted on
udev 3.9G 0 3.9G 0% /dev
tmpfs 786M 1.2M 785M 1% /run
/dev/mapper/ubuntu--vg-ubuntu--lv 454G 3.8G 432G 1% /
```
# Next
read
[Learn eBPF Tracing: Tutorial and Examples](http://www.brendangregg.com/blog/2019-01-01/learn-ebpf-tracing.html#Intermediate) 學習 how to use eBPF tracing
## Learn gnuplot -> 來產生 fibdrv 的製圖
* [gnuplot 語法解說和示範](/@sysprog/Skwp-alOg)
* [2016q3 Homework1 (phonebook)](/@ktvexe/HkUNXnz6?type=view)
* phonebook 作業內涵
* gnuplot 說明
* cache-miss 議題
* perf 分析
## solve SecureBoot problem
Use mokutil to disable secure boot
```shell
$ sudo mokutil --disable-validation
password length: 8~16
input password:
input password again:
```
Check the current state of secure boot
```shell
$ mokutil --sb-state
SecureBoot disabled
Platform is in Setup Mode
```
>still can not load kernel module
觀察 dmesg 後發現
關掉 secure boot 前，還可以正常 load module
關掉後反而無法
證據:
```shell
ls -l /dev/fibonacci 找不到東西
```
execute `make check` 時，出現
```shell
make -C /lib/modules/4.15.0-112-generic/build M=/home/unknowntpo/repo/unknowntpo/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-112-generic'
Building modules, stage 2.
MODPOST 1 modules
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-112-generic'
make unload
make[1]: Entering directory '/home/unknowntpo/repo/unknowntpo/fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
```
>在 vm 上觀察
```shell
$ sudo insmod fibdrv.ko
insmod: ERROR: could not insert module fibdrv.ko: Invalid module format
```
## OscarShiang's [repo](https://github.com/OscarShiang/fibdrv/commit/87e3ec827e3d29e12d681a02f157f2630223db1c) imitate (unsolved)
(已回報[錯誤](https://github.com/OscarShiang/fibdrv/commit/6c604859eb2e998fa33201e686e8111c9f25ecf5))
at commit 6c604859eb : Add fast doubling method to test the speed
:::danger
can't load module
```shell
$ make check
make -C /lib/modules/4.15.0-112-generic/build M=/home/unknowntpo/repo/OscarShiang/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-4.15.0-112-generic'
Building modules, stage 2.
MODPOST 1 modules
make[1]: Leaving directory '/usr/src/linux-headers-4.15.0-112-generic'
make unload
make[1]: Entering directory '/home/unknowntpo/repo/OscarShiang/fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
...
```
我的開發環境
```shell
$ uname -a
Linux unknowntpo 4.15.0-112-generic #113-Ubuntu SMP Thu Jul 9 23:41:39 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ cat /proc/version
Linux version 4.15.0-112-generic (buildd@lcy01-amd64-027) (gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)) #113-Ubuntu SMP Thu Jul 9 23:41:39 UTC 2020
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.4 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
```
:::
Sign in with Wallet
Connect another wallet