# 2020q2 Homework2 (fibdrv)
contribute by < `simpson0114` >
###### tags: `linux2020`

## 測試環境

$ 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

$ cat /proc/version
Linux version 5.3.0-40-generic (buildd@lcy01-amd64-024) 
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)) 
#32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020

## 作業要求

### 自我檢查清單
- [ ] 研讀上述 ==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 數計算的正確性
- [ ] 修正 Fibonacci 數計算的正確性 (現有實作存在缺陷，請指出)，隨後改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量

## 自我檢查清單
- [ ]使用實體電腦能夠控制CPU的使用情形，並且排除干擾效能分析的因素。
- [ ]關鍵手法如下，如果遇到 bit 為1的位元就將 $F(n)*2+1$，若遇到 bit 為0的位元則將 $F(n)*2$，又因 $F(0)=0$，因此第一個 bit 為1的位元左邊的位元都沒有用處，所以用 clz 先計算出有多少 leading 0s，將其省略掉可以使 Fibonacci 數運算更快速。

Fast_Fib(n)
    a = 0; b = 1;       // m = 0
    for i = (number of binary digit in n) to 1
        t1 = a*(2*b - a);
        t2 = b^2 + a^2;
        a = t1; b = t2; // m *= 2
        if (current binary digit == 1)
            t1 = a + b; // m++
            a = b; b = t1;
    return a;

- [ ]Fibonacci 數定義為
$$
F(0) = 0, F(1) = 1 \\
F(n) = F(n-1) + F(n-2),\ where \ n > 1
$$
以$F(6)$為例可得以下呼叫結果：

strict digraph G
{
	1[label="F(6)"]
    2[label="F(4)"]
    3[label="F(5)"]
    4[label="F(2)"]
    5[label="F(3)"]
    6[label="F(3)"]
    7[label="F(4)"]
    8[label="F(0)", style=filled]
    9[label="F(1)", style=filled]
    10[label="F(1)", style=filled]
    11[label="F(2)"]
    12[label="F(1)", style=filled]
    13[label="F(2)"]
    14[label="F(2)"]
    15[label="F(3)"]
    16[label="F(0)", style=filled]
    17[label="F(1)", style=filled]
    18[label="F(0)", style=filled]
    19[label="F(1)", style=filled]
    20[label="F(0)", style=filled]
    21[label="F(1)", style=filled]
    22[label="F(1)", style=filled]
    23[label="F(2)", style=filled]
    24[label="F(0)", style=filled]
    25[label="F(1)", style=filled]
    1 -> {2, 3}
    2 -> {4, 5}
    3 -> {6, 7}
    4 -> {8, 9}
    5 -> {10, 11}
    6 -> {12, 13}
    7 -> {14, 15}
    11 -> {16, 17}
    13 -> {18, 19}
    14 -> {20, 21}
    15 -> {22, 23}
    23 -> {24, 25}
}

而依照[Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 手法可得以下等式
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
依照此手法一樣以$F(6)$為例可得以下呼叫結果：

strict digraph G
{
	1[label="F(6)"]
    2[label="F(3)"]
    3[label="F(4)"]
    4[label="F(1)", style=filled]
    5[label="F(2)", style=filled]
    6[label="F(2)", style=filled]
    7[label="F(3)"]
    8[label="F(1)", style=filled]
    9[label="F(2)", style=filled]
    
    1 -> {2, 3}
    2 -> {4, 5}
    3 -> {6, 7}
    7 -> {8, 9}
}

可看出遞迴次數少了許多
## 修正 Fibonacci 數計算的正確性