# 2022q1 Homework3 (fibdrv)
contributed by < `vacantron` >
## 自我檢查清單
- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [x] 複習 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 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
----
### Fast doubling:
Fibonacci 數列經過整理後：
$$ F_{2n} = F_n (2 F_{n+1} - F_n) $$
$$ F_{2n+1} = F_{n+1} ^ 2 + F_n ^ 2 $$
可以由索引值較小的數求出特定的索引值的數。在計算的過程中可能會產生不需要的值，如：由 $F_5, F_6$ 計算 $F_11$ 時
#### top-down
將索引值 k 除以 2 並無條件捨去，算出可以要由哪項 n 得到該索引的值，如 $F_12$ 可以由 $F_6$ 與 $F_7$ 組成。若將兩個數表示成 [$F_k$, $F_{k+1}$]，若 k 是偶數，則可以再向下分解為 [$F_n$, $F_{n+1}$] (k = 2n)；若 k 是奇數，需要多一個步驟將 [$F_n$, $F_{n+1}$] 得出的 [$F_2n$, $F_{2n+1}$] 相加才能得到 $F_{2n+2}$ 這一項。
#### bottom-up
可以利用 stack 先算出需要的 n，由大到小推入堆疊中後迭代地取出，並根據 n 的奇偶性分別代入最前面的公式得出結果。
若將索引值以二進位表示，由左向右讀取的話就與 top-down 方式相似。若尋訪到的位元為 1，與上述 k 為奇數的處理方法相同，如下所示：
```c
// reference: https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling
uint64_t fib(unsigned int n)
{
// loop log2(n) times
unsigned int h = 0;
for (unsigned int i = n ; i ; ++h, i >>= 1);
uint64_t a = 0; // F(0) = 0
uint64_t b = 1; // F(1) = 1
for (unsigned int mask = 1 << (h - 1) ; mask ; mask >>= 1) {
uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
uint64_t d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) {
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else {
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
```
使用 `__builtin_clz()` 取代用位移計算 log2(n)
```c
uint64_t fib_clz(unsigned int n)
{
uint64_t a = 0; // F(0) = 0
uint64_t b = 1; // F(1) = 1
for (unsigned int mask = 1 << (sizeof(n) * 8 - __builtin_clz(n)); mask ; mask >>= 1) {
uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
uint64_t d = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2
if (mask & n) {
a = d; // F(n_j) = F(2k + 1)
b = c + d; // F(n_j + 1) = F(2k + 2) = F(2k) + F(2k + 1)
} else {
a = c; // F(n_j) = F(2k)
b = d; // F(n_j + 1) = F(2k + 1)
}
}
return a;
}
```
使用陣列儲存，以陣列索引為 Fibonacci 數列的索引
```c
uint64_t fib_array(unsigned int n)
{
uint64_t arr[n];
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i < n + 1; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
```
原始迭代版本
```c
uint64_t fib_literal(unsigned int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
uint64_t a = 0; // F(0) = 0
uint64_t b = 1; // F(1) = 1
for(int i = 2; i < n + 1; i++) {
uint64_t t = a;
a = b;
b += t;
}
return b;
}
```
效能對比：
------
### 核心模組
使用自定義的結構體來儲存溢位的整數，並在讀取檔案時使用 `copy_to_user` 將結構體的內容回傳至 userspace 。在 client 也要對自定義的結構體處理才能如期輸出。
```c
struct u128_t {
uint64_t upper;
uint64_t lower;
};
unsigned __int128 res = fib_sequence(*offset);
struct u128_t u128;
u128.upper = (uint64_t) res / pow2_64s;
u128.lower = (uint64_t) res % pow2_64s;
if (copy_to_user(buf, &u128, size))
return -EFAULT;
void print_u128(int i, struct u128_t u128)
{
if (u128.upper != 0) {
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%llu%llu.\n",
i, u128.upper, u128.lower);
} else {
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%llu.\n",
i, u128.lower);
}
}
```
這裡實作時發現轉送回去的數值有部份有錯誤，在 gdb 中發現在溢位時 ($F_{94}$ 開始) upper 反而變成 0，高位元的資料不見導致後來相加的數值有誤。
[]()
一開始是直接使用 `__uint128_t` 型別的指標透過 `copy_to_user` 轉送給 userspace，但是在資料型別的轉換上似乎沒有處理好，導致在對指標取值的時候一直拿不到正確的數值；但測試後發現在 kernel space 確實有算出正確的值，但在轉送的過程中遺失了，在 userspace 只能拿到一個指向一個連續記憶體空間的指標，後來由自定義資料結構解決問題。
gcc 的 [文件](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) 中也有提到 `__int128_t` 的資料型態無法直接指派或轉型給小於 128 位元的整數。
中途在使用陣列儲存已計算的數值時不小心發生越界存取 (索引值超過陣列本身) 的問題，會直接導致 kernel panic 並卡死，並不像平時只會在執行時回報 segment fault，需要特別留意。
:::spoiler outdated
### 修正 Fib(93)
使用 gcc 實作的 `__uint128_t` 避免 64 位元整數的溢位，以及使用 `copy_to_user` kernel API 將計算完的 Fibonacci 數傳至 user space
### 輸出 (printf)
新增 `print_u128` 函式來印出計算後的 Fibonacci 數，將 128 位元的無號數對半拆成高、低位元部份處理
----
:::warning
目前問題：
Fib(12) 開始會出現亂碼 (之前都正常) ，應該是 `copy_to_user` 使用方式錯誤所導致
:::
Sign in with Wallet
Connect another wallet