# 2020q2 Homework2 (fibdrv)
contributed by < `matches4453` >

> GitHub: [YanjenChen/fibdrv](https://github.com/YanjenChen/fibdrv)

[作業說明](https://hackmd.io/@sysprog/linux2020-fibdrv)

## Enviroment setting

### 排除特定 CPU
透過設定 Linux 參數，要求 Linux 排程器排除 (isolate) 特定 CPU 預設不予排程:
1. 開機進入 GRUB
2. 選擇 Linux instance
3. 按 `e` 編輯 Linux 啟動設定
4. 在 `linux /boot/...` 這行後面加上 `isolcpus=1`
5. 按 `ctrl + x` 用編輯後的設定執行 Linux

Linux 啟動後，若想確認是否設定成功，可以透過 `cat` 查看:

$ cat /sys/devices/system/cpu/isolated 
1

輸出 1 表示 CPU1 成功被保留給 `taskset` 使用。

### 設定 scaling_governor 為 performance
作業說明中的 shell script 執行會發生錯誤

$ sudo sh performance.sh
performance.sh: 3: performance.sh: cannot create /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor: Directory nonexistent

更改 shell script 可以解決路徑問題:

for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
    echo performance > ${i}
done

## Optmization ideas

### CLZ(Count leading zeros) 硬體加速
使用 CLZ 代替迴圈計算 MSB 的位置。在 [Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 演算法中作者使用迴圈計算 MSB 的位置，隨著 n 增大此處的計算時間會以 $O(log{n})$ 增加:

uint64_t fib(unsigned int n)
{
    unsigned int h = 0;
    for (unsigned int i = n ; i ; ++h, i >>= 1);
    ...
}

上述第 4 行可以用 `h = total_digits - CLZ(n);` 取代。

## Development log

### Fibdrv 執行時間分析
Kernel to user 所需時間量測結果為常數。透過 [ktime](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 和 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 分別量測 kernel space 和 user space 執行 $F(n)$ 所需的時間，將兩者相減可得到 kernel to user 的溝通時間。


### 改進 Fibdrv 執行時間
透過 [fast doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法可以減少計算 Fibonacci 數列的時間。考慮 fast doubling 計算需要在每次呼叫做 **count leading zeros(clz)**，使用 gcc 提供的[硬體 clz](https://gcc.gnu.org/onlinedocs/gcc-4.8.0/gcc/Other-Builtins.html) 做進一步的加速。

但下面實驗結果顯示不使用 gcc 提供的硬體 clz 反而比較快。:confused:

:::info
**TODO: 找出硬體減速的原因**
:::


### Kernel module 編譯設定
編譯 kernel module 時的 dependency 由特定的變數指定，將程式碼整理到數個 source file 時需要特別注意 makefile 的設定。參考 [kernel make file 解讀](https://blog.xuite.net/tzeng015/twblog/113272248-kernel+makefile%E8%A7%A3%E8%AE%80?fbclid=IwAR3bqmy1TBWqcBWThtvU9xpcMa9EetpdsUjROhlL6sK3IdHokZgIjYX80lA):

- `obj-m := xxx.o` 表示最終要產生名為 `xxx` 的 kernel module(.ko 檔)
- `xxx-objs := SOME DEPEDENT FILES` 表示產生 `xxx` 所需要的物件

下方的 makefile 表示要編譯名為 `fibdrvmodule.ko` 的 kernel module，由兩部分的 source file (即原始碼中的 `bign.[ch]` 和 `fibdrv.c`) 組成。

TARGET_MODULE := fibdrvmodule

obj-m := $(TARGET_MODULE).o
$(TARGET_MODULE)-objs := bign.o fibdrv.o

注意若直接指定 `obj-m := fibdrv.o` 會編譯出垃圾，因為 `fibdrv.o` 會同時成為**目標輸出和要連結的物件**導致連結發生非預期的行為。

### 大數運算
:::info
**WIP**
:::