# F02: fibdrv

:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2019 年系統軟體課程](https://www.facebook.com/groups/system.software2019/)
:mega: 返回「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表
:::

==[作業說明直播錄影](https://youtu.be/go41AXrBR1Y)==

## 預期目標

* 撰寫可適用於使用者和核心層級的程式
* 自動測試機制
* 透過工具進行效能分析

## 費氏數列

* [費氏數列](https://hackmd.io/s/BJPZlyDSV)
* [Fast modular Fibonacci](http://fedelebron.com/fast-modular-fibonacci)
* 影片「什麼是費氏數列」: [Part I](https://youtu.be/JWGCrICTars), [Part II](https://youtu.be/TA0Dpx0LOeY), [Part III](https://youtu.be/WyDn6wiwW74), [Part IV](https://youtu.be/iCSNHH45EeI)
* [Fibonacci and Golden Ratio Formulae](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html)

## 撰寫 Linux 核心模組

* [Introduction to Linux kernel driver programming](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf)
* [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
* [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)

## 測試給定的 `fibdrv` 模組

* 檢查 Linux 核心版本

    $ uname -r

預期是大於等於 `4.15` 的版本，例如 `4.15.0-45-generic`。若在你的開發環境中，核心版本低於 `4.15` 的話，需要更新 Linux 核心，請自行參照相關文件
* 安裝 `linux-headers` 套件 (注意寫法裡頭有 `s`)，以 [Ubuntu Linux 18.04 LTS](https://packages.ubuntu.com/bionic/linux-headers-generic) 為例:

    $ sudo apt install linux-headers-`uname -r`

* 確認 `linux-headers` 套件已正確安裝於開發環境

    $ dpkg -L linux-headers-4.15.0-45-generic | grep "/lib/modules"

預期得到以下輸出:

    /lib/modules/4.15.0-45-generic/build

* 檢驗目前的使用者身份

    $ whoami

預期為「不是 root 的使用者名稱，例如 `jserv` (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。由於測試過程需要用到 sudo，請一併查驗:

    $ sudo whoami

預期輸出是 `root`
:notes: 在下列操作中，請==避免用 root 帳號輸入命令==，而該善用 `sudo`
* 取得原始程式碼

    $ git clone https://github.com/sysprog21/fibdrv
    $ cd fibdrv

* 編譯並測試

    $ make check

預期會看到綠色的 ` Passed [-]` 字樣
* 觀察產生的 `fibdrv.ko` 核心模組

    $ modinfo fibdrv.ko

預期可得以下輸出:

    description:    Fibonacci engine driver
    author:         National Cheng Kung University, Taiwan
    license:        Dual MIT/GPL
    name:           fibdrv
    vermagic:       4.15.0-45-generic SMP mod_unload 

## 自我檢查清單

* 檔案 `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，到底會發生什麼問題
* 許多現代處理器提供了 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令，你知道如何透過演算法的調整，去加速 [費氏數列](https://hackmd.io/s/BJPZlyDSV) 運算嗎？請列出關鍵程式碼並解說

## 作業要求

* 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 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) 一類的指令，過程中都要充分量化

## 繳交方式

編輯 [Homework2 作業區共筆](https://hackmd.io/s/rygjaEK8V)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆

## 截止日期
Mar 19, 2019 (含) 中午之前
越早在 GitHub 上有動態、越早接受 code review，評分越高