# 2019q1 Homework2 (fibdrv)
contributed by < `Laurora` >
### Reviewed by `rebvivi`
- 在標題 `fibdrv 計算 Fibonacci 數列` 的第一張圖，可以在 `client.c` 中嘗試用不同的輸入數值：
* 原本老師給的檔案是用 `for (i = 0; i <= offset; i++)`當作 input，輸入數值是漸進遞增的 ，所以畫出來的圖是 best case 的情況
* 可以嘗試把 `fib_sequence(n)` 的輸入數值 n 改成固定區間的 random input
## 自我檢查清單
- [ ] 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
`MODULE_LICENSE`: 讓 kernel 知道 device driver 的授權方式
* 如果一個 module 没有授權，那麼很多需要授權的函式會因此不能使用
* 如果 module 授權錯誤，會導致 module 在 run 或是 load 錯誤
`MODULE_AUTHOR`: module 的作者
`MODULE_DESCRIPTION`: module 的功用跟簡介
`MODULE_VERSION`: module 的版本
`insmod`: 用於將給定的 module 載入到 kernel 中
* Linux 有許多功能是通過 module 的方式，在需要時才載入 kernel，可以讓 kernel較為精簡，進而提高效率
* module 載入的時候會呼叫 `init_fib_dev`
當使用 `insmod fibdrv.ko` 時，會自動的呼叫到 `init_fib_dev` 這個 function
```clike
module_init(init_fib_dev);
```
---
- [ ] 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
我們在`fibdrv.c`載入函式庫 `<linux/init.h>`
```clike
#include <linux/init.h>
```
在 `<linux/init.h>` 中定義如下:
```clike
#ifndef MODULE
#define module_init(x) __initcall(x);
#else
#define module_init(initfn) \
int init_module(void) __attribute__((alias(#initfn)));
#endif
```
* `__attribute__`: 讓我們定義函數的行為，以便告訴 gcc 在編譯時期對此函式做一些特殊的處理或檢查動作
* `alias` : 定義 `init_module` 爲函數 initfn 的別名
```clike
module_init(init_fib_dev);
```
* `module_init(init_fib_dev)` 的作用就是定義一個變量名 `init_module`，其地址和 `init_fib_dev` 一樣
* 在寫 module 的時候有兩個特殊的函數，分別是 `init_module` 和 `cleanup_module` ，這兩個函數分別在 `insmod` 的時候和 `rmmod` 的時候調用，並且 `insmod` 和 `rmmod` 只識別這兩個特殊的函數
* 當我們給的 `initfn (init_fib_dev)` 定義一個別名 `init_module`，這樣 `insmod` 就能夠執行我們的 `initfn (init_fib_dev)`
---
- [ ] 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
當我們在終端機輸入 `$ modinfo fibdrv.ko` ，可以得到以下資訊
```
version: 0.1
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: CCEDBC56685E857565A460A
depends:
retpoline: Y
name: fibdrv
vermagic: 4.18.0-15-generic SMP mod_unload
```
而當我們輸入 ` $ readelf -a fibdrv.ko` 會列出，可以在 `Section Headers:` 中找到 `.modinfo` ，利用 `$ sudo objdump --section=.modinfo -s fibdrv.ko` 可以查看 `.modinfo` 的內容，發現與上方結果一致。
```
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 6f6e3d43 43454442 43353636 38354538 on=CCEDBC56685E8
0090 35373536 35413436 30410000 00000000 57565A460A......
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 2d31352d 67656e65 72696320 534d5020 -15-generic SMP
00e0 6d6f645f 756e6c6f 61642000 mod_unload .
```
同樣利用 `objdump` 查詢 `.gnu.linkonce.this_module` 即列出此模組的名字 `fibdrv`
* `modinfo` 指令用來顯示核心模組的資訊（ section `.modinfo` ），此 section 的資料不會載入到 kernel address space 。
* 而 `.gnu.linkonce.this_module` section 含有一個 module 的結構，其中包含模組名及其他欄位，但在這次的作業中只看的到模組名。插入模組 (`insmod`) 時，`module_init()` 會從這個 section 將該 module 結構讀入動態記憶體。
> The `.modinfo` section is used by the `modinfo` command to show information about the kernel module. The data stored in the section is not loaded in the kernel address space.
> The `.gnu.linkonce.this_module` special section includes a module structure which contains, among other fields, the module's name. When inserting a module, the `init_module()` system call reads the module structure from this special section into an area of dynamic memory.
>--- source from [Special sections in Linux binaries](https://lwn.net/Articles/531148/)
* linux 模組化後， `.ko` 檔可透過 insmod 載入 linux 核心，由於 `.ko` 檔環境須與系統環境一致，因此在開發之前的準備工作需要確認 `linux-headers` 是否正確安裝於開發環境。
* makefile 中 ```$(MAKE) -C $(KDIR) M=$(PWD) modules``` 即是將 `linux-headers` include 進來。
---
- [ ] 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。
---
- [ ] 查閱 `ktime` 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
---
- [ ] `clock_gettime` 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
* `clock_gettime`: 用來取得程式的 CPU time，是 POSIX 的 High Resolution Timer 之一，精確度可以達到 nanosecond，其所回傳的時間是用 `timespec` 這個 struct 所儲存
第一個 parameter `clock_id` 可以設定成 `clockid_t` 型態
`CLOCK_REALTIME`: `clockid_t` 型態的一種，是系統實際的時間
```clike
int clock_gettime
(clockid_t clock_id, struct timespec *tp);
```
* 函式會將計時器的值儲存成 `timespec` 的型態，會將時間分為 second 及 nanosecond
```clike
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
---
- [ ] `fibdrv` 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
* Linux Virtual File System
---
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
* mutex 的存在是為了讓 kernel 保持同步，防止多核心處理器同時訪問及修改某段 code ，或者對 driver 做 critical section 的 protection。
* `DEFINE_MUTEX`: 靜態初始化 mutex ，一般宣告在 global
* `mutex_init`: 初始化已經 allocate 的 mutex ，It is used for per-object mutexes, when mutex is just a field in a heap-allocated object.
* `mutex_trylock`: 不暫停目前執行的程式，嘗試鎖定 mutex ，成功返回非零，否則返回 0 。若沒有 sleeping ，此功能無法安全地在硬體或軟體中斷環境中使用。
* `mutex_unlock`: 將 mutex 解鎖。
* `mutex_destroy`: 可以 destory mutex pointer 所指向的與 mutex lock 相關的任何狀態。用來儲存 mutex lock 的空間不會釋放。
* userspace 沒有 mutex 的情況下測試多執行緒 ( [測試程式](https://github.com/Laurora/test_pthread) )
預期結果
```
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.
This is the main process.
This is the main process.
```
但是在沒有 mutex 的情況可能會變成
```
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is the main process.
This is the main process.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.
```
或是其他可能。顯示出 main process 和 thread 之間會競爭先後順序，若 process 和 thread 之間有共用變數或是資料傳遞，沒有 mutex 會導致計算結果與預期結果不同。
- [ ] 許多現代處理器提供了 `clz / ctz` 一類的指令，你知道如何透過演算法的調整，去加速費氏數列運算嗎？請列出關鍵程式碼並解說
## fibdrv 計算 Fibonacci 數列
* 原來使用一維陣列儲存 fib
* 更改算法，預期結果為 $O(logN)$
```clike
static long long fib_sequence(long long n)
{
long long i,h,j,k,t;
i=h=1;
j=k=0;
while(n>0) {
if(n%2==1){
t=j*h;
j=i*h + j*k +t;
i=i*k + t;
}
t=h*h;
h=2*k*h + t;
k=k*k + t;
n=(long long) n/2;
}
return j;
}
```
但此圖仍看不出 $O(logN)$ 的趨勢，可能是迭代次數不夠多的關係。
Sign in with Wallet
Connect another wallet