# 2023q1 Homework3 (fibdrv)

:::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.

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6399.96

:::

### 使用 string 實作 fibnacci 解決溢位問題

:::spoiler

void add_str(char *num1, char *num2, char *out)
{
    size_t len1 = strlen(num1), len2 = strlen(num2);
    int i, sum, carry = 0;
    reverse(num1);
    reverse(num2);
    if (len1 >= len2) {
        for (i = 0; i < len2; i++) {
            sum = (num1[i] - '0') + (num2[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }
        for (i = len2; i < len1; i++) {
            sum = (num1[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }
    } 
    else {
        for (i = 0; i < len1; i++) {
            sum = (num1[i] - '0') + (num2[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }

        for (i = len1; i < len2; i++) {
            sum = (num2[i] - '0') + carry;
            out[i] = '0' + sum % 10;
            carry = sum / 10;
        }
    }

    if (carry)
        out[i++] = '0' + carry;

    out[i] = '\0';
    reverse(num1);
    reverse(num2);
    reverse(out);
}

:::

struct BigN{
    char string[128];
};

static long long fib_sequence(long long k, char *buf)
{
    struct BigN *f = kmalloc(sizeof(struct BigN) * (k + 1), GFP_KERNEL);

    if (!f) {
        return -ENOMEM;
    }

    strncpy(f[0].string, "0", 1);
    strncpy(f[1].string, "1", 1);

    for (int i = 2; i <= k; i++)
        add_str(f[i - 1].string , f[i - 2].string, f[i].string);

    int len = strlen(f[k].string) + 1;
    printk("k: %lld\n", k);
    if(__copy_to_user(buf, f[k].string, len))
        return -EFAULT;

    return len;
}

使用字串來實作大數運算，發現 `fib[93]` 開始還是會錯，在 `fib_squence` 中加入 `printk("k: %lld\n", k);` ，並搭配 `journalctl` 發現 93 到 100 的 `k` 值都是 92。

發現 fibdrv.c 裡面有設定 `MAX_LENGTH` ， 改完後就可以通過 make check

### clz / ctz 一類的指令對 Fibonacci 數運算的幫助

將原本的 fib 運算改成 fast doubling ， 搭配 `__builtin_clzll` 去除 leading zero

static long long fib_sequence(long long k)
{
    int num_bits = sizeof(k) * 8 - __builtin_clzll(k);
    long long t1, t2;
    long long a = 0, b = 1;  // m = 0
    for (int i = num_bits; i > 0; i--) {
        t1 = a * (2 * b - a);
        t2 = b * b + a * a;
        a = t1;
        b = t2;  // m *= 2
        if ((k >> (i - 1)) & 1) {
            t1 = a + b;  // m++
            a = b;
            b = t1;
        }
    }
    return a;
}

### [用 string 實作 fast doubling](https://github.com/sysprog21/fibdrv/commit/a08f677ad802aaaf1430b3c802a6188ad4c81d3f)
`void mul_str(char *num1, char *num2, char *result)`
`mul_str(t2, tmp, tmp);`
原本在 `fib_sequence` 中呼叫 `mul_str` 時沒注意到 `num2` 跟 `result` 是帶入相同的指標，在更改 `result` 時就會改到 `num2`

### 測量執行時間

加入測試時間程式後執行 make check 會卡住，待查

---

- [ ] 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 G NU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。 → 搭配閱讀〈並行和多執行緒程式設計〉