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

## 自我檢查清單

- [ ] 研讀上述 ==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: 作業要求

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

* 在 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 核心有對應的包裝函式)，過程中都要充分量化

## Fast Doubling 實作

static long long fast_fib(long long k)
{
    long long a, b;
    unsigned long long u = 1;
    a = 0;
    b = 1;
    for (int i = sizeof(k) * 8; i >= 1; i--) {
        long long t1 = a * (2 * b - a);
        long long t2 = b * b + a * a;
        a = t1;
        b = t2;
        if ((k & (u << (i - 1))) > 0) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

基本上是根據作業內容所提供的演算法所撰寫的，在實作抓取第 n 位元的時候，一開始用另外寫的 ```lpow``` 來進行運算，後來發現程式的執行速度會比原本不做 fast doubling 來的慢
![fast doubling pow]!(https://i.imgur.com/mJrFX3n.png)

後來想到在 2 的次方可以用 shift 來加速，運算速度有明顯上升。

從圖發現在 N 較小時，還看不出 fast doubling 的速度優勢，且會浪費許多時間在從最高位到找到第一位 1 的位元中間，作業提示中有提到可以使用 ```clz``` 來進行加速

### clz (count leading zero)
clz 函式的部份使用 gcc 內建的 __builtin_clz

static long long fast_fib_clz(long long k)
{
    long long a, b;
    if (k == 0)
        return 0;
    a = 0;
    b = 1;
    int zeros = (int)__builtin_clz(k);
    int start = sizeof(k) * 8 - zeros;
    unsigned long long u = 1;
    for (int i = start; i >= 1; i--) {
        long long t1 = a * (2 * b - a);
        long long t2 = b * b + a * a;
        a = t1;
        b = t2;
        if ((k & (u << (i - 1))) > 0) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

加入 `clz` 可以在 N 值較小可以直接從首位為 1 的位元開始計算，而非從頭開始，藉此節省前段為 0 的空間，當 N 越小，第一個為 1 的位元便越靠前，能夠節省的次數便越多，反之當 N 越大時，能夠節省的時間便越有限。
在加入 `clz` 之後可以看出在 $N \leq 100$ (實際為 92) 時速度有所提昇。

在一開始設計位元檢查的時候因為還沒想到用 shift 的方式來作2的次方計算，因此實作了 lpow 來計算次方，而在加入 shift 之後，卻沒將2次方運算換成一般的乘法而造成多餘的時間開銷。
將改 lpow 改為乘法運算之後的結果如下

## Makefile 自動生圖
由於在測試效能的過程中每次都需要修改 `fibdrv.c` 中的 function 重新編譯後再進行測試，需要測試的 function 又有 3 個實在太麻煩，因此在 `Makefile` 中加入了 test 的 option ，並在 ```client.c``` 裡面利用 ```argv```傳遞參數，讓他可以一次 ```make``` 就作三種 function 的測試，並幫我畫好圖。

TARGET_MODULES := fibdrv fibdrv_fast fibdrv_fast_clz
obj-m := fibdrv.o fibdrv_fast.o fibdrv_fast_clz.o

test: all
	for MODULE in $(TARGET_MODULES);do \
		sudo rmmod $$MODULE || true >/dev/null; \
		sudo insmod $$MODULE.ko; \
		sudo ./client $$MODULE > out; \
		sudo rmmod $$MODULE || true >/dev/null; \
		echo $$MODULE; \
	done
	gnuplot fib_plot.gp