# 2020q2 Homework2 (fibdrv)
contributed by < `ndsl7109256` >

## 作業要求
- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [x] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [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 核心如何追蹤呢？
- [x] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

## Fibonacci 數運算的效能分析

首先我們先簡單比較一下根據定義運算 $O(n)$

static unsigned long long normal_fib(long k){
    long long f[k + 2];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    return f[k];
}

與 `fast doubling` 所需的時間。

unsigned long long fast_fib(int n)
{
    unsigned long long a = 0, b = 1, t1, t2;
    for (int i = 31; i >= 0; i--) {
        t1 = a * (b * 2 - a);
        t2 = b * b + a * a;
        a = t1;
        b = t2;
        if ((n & (1 << i)) > 0) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

由於
$$
\begin{align}
&F(2n) = 2F(n)\times F(n+1) - F(n)^2 \\
&F(2n+1) = F(n)^2 + F(n+1)^2
\end{align}
$$
所以運算只需要 $O(logN)$ 。

但是這裡我們這裡每次必須看每完 32 個位元，所以在 n 比較小的時候反而沒有比較快，所以我們這裡引進 clz 幫助我們看所需要的位元就好。

由上圖可以看出有了 clz 的幫忙後速度明顯提升了。

這裡我們原先用的是 gcc 所提供的 `__builtin_clz` 而從 [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 我們知道 clz 還有許多實作的方法這裡我另外用了 **Binary Search Technique**

int clz(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
    return n;
}

所得到的效果似乎沒有差太多。

## 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

觀察程式碼發現 mutex lock 只有在 `fib_open` 中使用到，這是因為我們不希望同時有兩個不同的 user 使用這個 device。當我們的 device 需要根據輸入 (write) 得到對應的輸出 (read) 時，這個機制就會顯得非常重要。

在 user space 的程式中，我們應該要確保寫和讀會得到相同的結果。但是在 multitasking 的例子中，我們卻可能得到錯誤的結果。

藉由這段 [gist](https://gist.github.com/ndsl7109256/79d0d81517ace379fa8bd483d2600bfc) ， module 會把 client 傳來的 string 原封不動傳回去，但就因為沒有防止其他 thread 進入結果而有所錯誤。

1:Writing 111 to kernel, Received 333 from kernel
3:Writing 333 to kernel, Received 333 from kernel
2:Writing 444 to kernel, Received 777 from kernel
4:Writing 222 to kernel, Received AAA from kernel
5:Writing 999 to kernel, Received AAA from kernel
6:Writing 888 to kernel, Received AAA from kernel
7:Writing 777 to kernel, Received AAA from kernel
9:Writing 555 to kernel, Received 666 from kernel
10:Writing 666 to kernel, Received 666 from kernel
8:Writing AAA to kernel, Received AAA from kernel

## 列出 Fib(100) 以後的數值
我所用的資料結構是有兩個 long long 所組成的 `Bignum`。

struct BigN {
    unsigned long long lower, upper;
} BigN;

原本利用作業說明給的提示做了 `add` `big` `mul` 運算。

void addBigN(struct BigN *output, struct BigN x, struct BigN y)
{
    output->upper = x.upper + y.upper;
    unsigned long long diff = ULLONG_MAX - x.lower;
    if (y.lower > ~x.lower){
        output->upper++;
    }
    output->lower = x.lower + y.lower;
}

void subBigN(struct BigN *output, struct BigN x, struct BigN y)
{
    if (x.lower < y.lower) {
        output->lower = x.lower + ~y.lower + 1;
        output->upper = x.upper - y.upper - 1;
    } else {
        output->lower = x.lower - y.lower;
        output->upper = x.upper - y.upper;
    }
}

static inline void mulBigN(struct BigN *output, struct BigN x, struct BigN y)
{
    output->lower = 0;
    output->upper = 0;

    size_t width = 8 * sizeof(unsigned long long);

    for (size_t i = 0; i < width; i++) {
        if ((y.lower >> i) & 0x1) {
            BigN tmp;

            output->upper += x.upper << i;

            tmp.lower = (x.lower << i);
            tmp.upper = (i == 0) ? 0 : (x.lower >> (width - i));
            addBigN(output, *output, tmp);
        }
    }

    for (size_t i = 0; i < width; i++) {
        if ((y.upper >> i) & 0x1) {
            output->upper += (x.lower << i);
        }
    }
}

但用這種方法做出來的結果乘法效果沒有很好的樣子，而且在將結果轉換時 `BigN.upper` 必須乘上 $2^{64}$ 再加上 `BigN.lower` ，還必須做額外的處理。

後來我用十進位的思維另外做了加法，得到的結果可以直接將 `BigN.upper` 和 `BigN.lower` 串接就可

static inline void addBigN_DECIMAL(struct BigN *output, struct BigN x, struct BigN y)
{
    output->upper = x.upper + y.upper;
    unsigned long long diff =  DECIMAL_MAX - x.lower;//DECIMAL_MAX = 100000000000000000
    if(y.lower > diff){
        output->upper++;
        output->lower = x.lower+y.lower-DECIMAL_MAX;
    }else
        output->lower = x.lower + y.lower;
}