---
tags: linux2023
---

# 2023q1Homework2 (fibdrv)
contributed by < `JoshuaLee0321` >

## 開發環境
:::spoiler
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 2600X Six-Core Processor
CPU family: 23
Model: 8
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU max MHz: 3600.0000
CPU min MHz: 2200.0000
BogoMIPS: 7199.10
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht
:::

## 自我檢查清單

- [x] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉

## 開發紀錄

### 使用 Fast Doubling 改寫
* 剛開始打開 `fibdrv` 的時候會發現，最開始的 `fibonacci number` 是一個 $O(N)$ 的演算法

* 首先先嘗試使用 pseudo code 中的方法改寫

static long long fast_doubling(long long n)
{
    long long a = 0, b = 1;

    for (unsigned int i = 1U << 31; i; i >>= 1) {
        long long t1 = a * (2 * b - a);    // 2k
        long long t2 = a * a + b * b;      // 2k + 1
        if (n & i) {
            a = t2;
            b = t1 + t2;
        } else {
            a = t1;
            b = t2;
        }
    }
    return a;
}

*

* 在實作這個方法的時候我發現，實際上感覺時間沒有到非常的快，尤其在 `n` 很小的時候與原先的 `fibonacci number` 的速度差很多，第一個想到的原因就是：`fast_doubling` 的這個寫法會導致不管如何都跑 `32` 次迴圈，由於我只需要找到第一個為1的位元即可，所以我可以把以上程式碼中 `int len = 64` 更改成 `int i = 32 - __builtin_clz(k)`，這樣即可確保在 `n` 很小的時候不會跑太多次迴圈即可把答案回傳給 `user space`

static long long fast_doubling_clz(long long n)
{
    long long a = 0, b = 1;

    for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
        long long t1 = a * (2 * b - a);  // 2k
        long long t2 = a * a + b * b;    // 2k+1
        if (n & i) {
            a = t2;
            b = t1 + t2;
        } else {
            a = t1;
            b = t2;
        }
    }
    return a;
}

* 以下為對於這個程式碼的實驗數據
* 

* 從以下圖可以觀察到，如同剛剛提到，實作出 `fast_doubling` 並沒有提升非常多的效能。原因就如同剛剛所說的每一次呼叫 `fib` 都需要花上 `32` 次迴圈，此舉將會大大降低整體的效能。如果使用 `__builtin_clz` 即可大大提升 `fibdrv` 的效能

### 突破 fib(93) 的限制
* 為了要突破 `fib(93)` 勢必需要使用 `char` 來突破限制，參考了 [jj971818](https://github.com/jj97181818/fibdrv) 的實作方法，以下提供 `bigN` 的實作解說

typedef struct _BigN {
    unsigned int *val;
    unsigned int size;
    int sign;
} BigN;

// 主要的重點放在這 function， 他會回傳一個 bigN

static BigN *BigN_add(const BigN *a, const BigN *b)
{
    unsigned int size = ((a->size > b->size) ? a->size : b->size) + 1;
    BigN *sum = BigN_new(size);

    unsigned int carry = 0;
    unsigned long s = 0;
    for (int i = 0; i < sum->size; i++) {
        unsigned int tmp1 = (a->size) > i ? a->val[i] : 0;
        unsigned int tmp2 = (b->size) > i ? b->val[i] : 0;
        // 找出第一位數
        
        s = (unsigned long) tmp1 + tmp2 + carry;

        sum->val[i] = s & UINT_MAX;
        carry = 0;
        if (s > UINT_MAX) {
            carry = 1;
        }
    }
    if (sum->val[sum->size - 1] == 0) {
        sum->size -= 1;
    }

    return sum;
}

* 有了 `bigN` 的加法之後就可以套用在原本的 `fibdrv` 上了

static BigN *fib_sequence_BigN(long long k)
{
    BigN *a = BigN_new(1);  // f(0) = 0
    BigN *b = BigN_new(1);  // f(1) = 1
    b->val[0] = 1;
    BigN *sum;

    if (k == 0)
        return a;

    for (int i = 2; i <= k; i++) {
        sum = BigN_add(a, b);  // f[i] = f[i - 1] + f[i - 2]
        BigN_free(a);
        a = b;
        b = sum;
    }
    BigN_free(a);

    return b;
}

* 如此一來就可以突破 fib(93) 的限制

### 遇到的問題

* 有很長一段時間我無法理解到底如何把自定義的值回傳給自動測試的檔案，後來發現只需要在 `fib_write` 裡面寫 `copy_to_user` 即可