# 2021q1 Homework3 (fibdrv)
contributed by < `idoleat` >

## 自我檢查清單

- [ ] 研讀 [Linux 效能分析的提示](https://hackmd.io/@sysprog/linux2021-fibdrv#-Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA) 描述，在自己的實體電腦運作 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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `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，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。

## Linux 效能分析
為何不希望使用虛擬機
* 虛擬機無法對 CPU 進行最佳排程，虛擬機對原本的系統而言是一個 process，此 process 也需要被原系統排程，所以在虛擬機內的排程會被再次排程，變得不是當下排程演算法的最佳排程（:question:==那我就指定虛擬機完全霸佔某幾個 CPU 行不行？==）

:question:==為什麼 KVM 或 Docker 就可以？==
KVM 和 Docker 作業系統共用的部份是？

## clz / ctz 一類的指令對 Fibonacci 數運算的幫助
### 論文要點
* 計算模型：因為 oprand 變大，計算時間也會變久，所以用 uniform cost function 計算模型來測量時間不太對，這邊改用 bitwise model
* 計算方法一：repeated addition
* 計算方法二：遞迴
* 計算方法三

論文中的關鍵手法:
code explanation:

## 修正並改善 fibdrv
原先的程式碼存在以下問題
* 使用 long long 儲存數值，到 f(93) 的時候就會 overflow 了
* 在重新計算其他項次並沒有善用已計算過的項次，每次都是從第一項開始重算
* 使用的計算方法並非最快，有更好的算法

實做上還有幾個需要注意的點
* 使用浮點數會有誤差

/* MAX_LENGTH is set to 92 because
 * ssize_t can't fit the number > 92
 */
#define MAX_LENGTH 92

why define MAX_LENGTH can effect the actual length of [ssize_t](https://man7.org/linux/man-pages/man7/system_data_types.7.html)? (No. It cannot.)
And why 92? 我用 sizeof 讀出來他的大小是 8

## 大數
原本想偷懶使用 `__int128_t` 快速修正 F(93) overflow 的問題，結果發現 [GCC 使用手冊](https://gcc.gnu.org/onlinedocs/gcc-10.3.0/gcc/_005f_005fint128.html) 說
> **6.8 128-bits integers**
>As an extension the integer scalar type `__int128` is supported for targets having an integer mode wide enough to hold 128-bit. Simply write `__int128` for a signed 128-bit integer, or unsigned `__int128` for an unsigned 128-bit integer. There is no support in GCC to express an integer constant of type `__int128` for targets having `long long` integer with less then 128 bit width.

所以要把 `__int128_t` 的數字 print 出來，必須要分成兩個 `long long` 來 print，同樣的也查到別人[有一樣的疑惑](https://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc)。似乎直接使用 `__int128_t` 也沒有多偷懶，而且一樣有上限，那不如好好處理大數運算比較實際。