# 2020q1 Homework2 (fibdrv)
contributed by < `ZhuMon` >
###### tags: `linux2020`, `fibonacci`, `linux-kernel`
## 大綱
[TOC]
## 開發環境
:::spoiler
> 依照[此篇](https://hackmd.io/@junwei/Syy7Sc4WU) 來建立虛擬機
> 建議使用 Ubuntu Server 18.04 ，之前使用 Ubuntu Server 19.10 時，無法使用 Host 端的 CPU （選項 -cpu host），改採用 18.04 便可成功執行
* `cat /etc/lsb-release`
```
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.3 LTS"
```
* `lscpu`
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: 06/3d
Stepping: 4
CPU MHz: 1800.105
BogoMIPS: 3600.21
L1d cache: 32K
L1i cache: 32K
L2 cache: 4096K
L3 cache: 16384K
NUMA node0 CPU(s): 0
Flags: （略）
```
* `uname -a`
```
Linux yx 4.15.0-91-generic #92-Ubuntu SMP Fri Feb 28 11:09:48 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
```
* `gcc --version`
```
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.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，到底會發生什麼問題
- [ ] 修正 Fibonacci 數計算的正確性，改善 fibdrv 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
## 測試模組
* 取得程式碼
```script
$ git clone https://github.com/sysprog21/fibdrv
$ cd fibdrv
```
* 編譯並測試
```script
$ make check
```
確實得到預期結果
<pre>
<span style="color:green; font-weight: bold"> Passed [-]</span>
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
</pre>
* 載入模組並觀察該模組狀況
``` script
$ sudo insmod fibdrv.ko
$ modinfo fibdrv.ko
```
得到以下輸出
```
filename: /home/yx/linux2020/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: 4.15.0-91-generic SMP mod_unload
```
與預期相同
* 觀察模組掛載後的行為
```shell
$ ls -l /dev/fibonacci
crw------- 1 root root 243, 0 Mar 25 02:37 /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev
243:0
```
其中有一個數字 `243` 查閱資料後，發現他是指檔案的大小
> 在 man page 中，`-l` 選項只有簡短的一句話
> > `-l use a long listing format`
>
> 參照 [What-information-is-listed](https://www.gnu.org/software/coreutils/manual/html_node/What-information-is-listed.html#What-information-is-listed)，可以得知
> > In addition to the name of each file, print the file type, file mode bits, number of hard links, owner name, group name, size, and timestamp, normally the modification timestamp. If the owner or group name cannot be determined, print the owner or group ID instead, right-justified as a cue that it is a number rather than a textual name. Print question marks for other information that cannot be determined.
> > 也就是說 `243` 是指該檔案的大小，而且這裡的 `243` 應該跟後面的 `0` 一起看，也就是說檔案的大小是 `243, 000 byte`
``` shell
$ cat /sys/module/fibdrv/version
0.1
$ lsmod | grep fibdrv
fibdrv 16384 0
```
## 計算時間
綁定 cpu 後
```shell
$ taskset 0x1 sudo ./client
```
好像沒什麼變化，等之後大數完成再看一次
## 導入大數運算
綁定 cpu 後
1000 次
因為不是線性，改採 eBPF
10000次
## eBPF
### 安裝
* 安裝 [BCC](https://github.com/iovisor/bcc/blob/master/INSTALL.md#install-and-compile-bcc)
dependency
```shell
$ sudo apt-get -y install bison build-essential cmake flex git libedit-dev \
libllvm6.0 llvm-6.0-dev libclang-6.0-dev python zlib1g-dev libelf-dev
```
install BCC
```shell
$ git clone https://github.com/iovisor/bcc.git
$ mkdir bcc/build; cd bcc/build
$ cmake ..
$ make
$ sudo make install
$ cmake -DPYTHON_CMD=python3 .. # build python3 binding
$ pushd src/python/
$ make
$ sudo make install
$ popd
```
* 安裝 [bpftrace](https://github.com/iovisor/bpftrace/blob/master/INSTALL.md#ubuntu)
```shell
$ sudo snap install --devmode bpftrace
$ sudo snap connect bpftrace:system-trace
```
### 測試時間
Sign in with Wallet
Connect another wallet