# F03: fibdrv

contributed by < `st9540808` >

* [F03: fibdrv](https://hackmd.io/s/SJ2DKLZ8E)

### 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說
fast doubling 是藉由從 $[F_n, F_{n+1}]$ 來計算 $[F_{2n},F_{2n+1}]$ 或 $[F_{2n+1},F_{2n+2}]$ 根據 $n$ 是偶數或奇數，計算公式如下

$F_{2n+1} = {F_{n+1}}^2 + {F_n}^2$
$F_{2n} \ \ \ \ = F_n \cdot (2 \cdot F_{n+1} - F_n)$

在實作時必須從 MSB 開始，檢查每個位元是 1 或 0，如果是 1 就去計算 $[F_{2n+1},F_{2n+2}]$，反之則是 $[F_{2n},F_{2n+1}]$。這個公式會被計算 $\left \lfloor{log_2n}\right \rfloor +1$ 次，所以時間複雜度是 $O(logn)$

在一開始找 MSB 時可用 `__builtin_clzll()` gcc 支援的 builtin functions，`63 - __builtin_clzll(k)` MSB 的位置，用 `k >> (n - i)` 就可以得到 MSB 位元。

long long fib_sequence(long long k)
{
    long long f[2] = {0, 1};
    int n = 63 - __builtin_clzll(k);
    for (int i = 0; i <= n; i++) {
        // a = F2n+1;  b = F2n
        long long a = f[1] * f[1] + f[0] * f[0];
        long long b = f[0] * (2 * f[1] - f[0]);
        if ((k >> (n - i)) & 1) {
            // n is odd
            f[0] = a;
            f[1] = a + b;
        } else {
            // n is even
            f[0] = b;
            f[1] = a;
        }
    }
    return f[0];
}

### 效能分析
時間量測方法參照 [ChihAnLin0607](https://hackmd.io/s/BkpaZKRUE) 同學的共筆，在 kernel space 使用 ktime_get() 紀錄時間並回傳給 user space。

比較在 kernel space 與在 user space 中花的時間，每一個點均測量五萬次並繪出 95% 信賴區間

繪出在 kernel space 所花的時間佔總時間的百分比，變化沒有很明顯，沒辦法看出 $O(logn)$ 的趨勢

:::warning
如何解釋 userspace 時間分佈較廣的結果呢？
:notes: jserv
:::

## CHECK LIST
- [ ] 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
- [ ] 在 GitHub 上 fork [fibdrv](https://github.com/sysprog21/fibdrv)，目標是改善 `fibdrv` 計算 Fibinacci 數列的執行效率，過程中需要量化執行時間，可在 Linux 核心模組和使用層級去測量
- [ ] 在 Linux 核心模組中，可用 ktime 系列的 API
- [ ] 在 userspace 可用 [clock_gettime](https://linux.die.net/man/2/clock_gettime) 相關 API
- [ ] 分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)
- [ ] 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響
- [ ] 原本的程式碼只能列出到 Fibonacci(100)，請修改程式碼，列出後方更多數值 (注意: 檢查正確性和數值系統的使用)
- [ ] 逐步最佳化 Fibonacci 的執行時間，引入 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 提到的策略，並善用 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，過程中都要充分量化

==自我檢查清單==
- [ ] 檔案 `fibdrv.c` 裡頭的 `MODULE_LICENSE`, `MODULE_AUTHOR`, `MODULE_DESCRIPTION`, `MODULE_VERSION` 等巨集做了什麼事，可以讓核心知曉呢？
- [ ]`insmod` 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
- [ ] 當我們透過 `insmod` 去載入一個核心模組時，為何 `module_init` 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
- [ ] 試著執行 `$ readelf -a fibdrv.ko`, 觀察裡頭的資訊和原始程式碼及 `modinfo` 的關聯，搭配上述提問，解釋像 `fibdrv.ko` 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
- [ ] 這個 `fibdrv` 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 [Random numbers from CPU execution time jitter](https://lwn.net/Articles/642166/)
- [ ] 查閱 [ktime 相關的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html)，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
- [ ] [clock_gettime](https://linux.die.net/man/2/clock_gettime) 和 [High Resolution TImers (HRT)](https://elinux.org/High_Resolution_Timers) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
- [ ] `fibdrv` 如何透過 [Linux Virtual File System](https://www.win.tue.nl/~aeb/linux/lk/lk-8.html) 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 `client.c` 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
- [x] 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說