# 2023q1 Homework3 (fibdrv)
contributed by <`kart81604`>
## 開發環境

$ gcc -version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5599.85

## 修改 `fibdrv.c`
執行 `make file` 會出現

...
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738

表示與預期的不同，輸出應為下面的值，先照著[作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d#F92-%E4%BB%A5%E5%BE%8C%E7%9A%84%E6%95%B8%E5%80%BC%E9%8C%AF%E8%AA%A4%E7%9A%84%E5%8E%9F%E5%9B%A0)將 `MAX_LENGTH` 從 92 更改至 93 ， `fib_sequence` 的回傳值從 `long long` 更改至 `uint64_t` ，再執行 `make check` 預期 f(93) 應跑出正確的數字。
out 檔如下

Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence -6246583658587674878.

仍然 overflow ，再將 `client.c` 作修改。

- long long sz;
+ u_int64_t sz;
...
- printf("... %lld ...");
+ printf("... %llu ...");

f(93) 就能輸出正確值

Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.

引入 [big number](https://github.com/sysprog21/bignum/blob/master/bignum.c#L114) 並研讀此方法，使其能顯示出超過 64 位元的二進位數字。

/* 
 * output bn to decimal string
 * Note: the returned string should be freed with kfree()
 */
char *bn_to_string(bn src)
{
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * src.size) / 3 + 2 + src.sign;
    char *s = kmalloc(len, GFP_KERNEL);
    char *p = s;

    memset(s, '0', len - 1);
    s[len - 1] = '\0';

    for (int i = src.size - 1; i >= 0; i--) {
        for (unsigned int d = 1U << 31; d; d >>= 1) {
            /* binary -> decimal string */
            int carry = !!(d & src.number[i]);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry; // double it
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') { 
        p++;
    }
    if (src.sign)
        *(--p) = '-';
    memmove(s, p, strlen(p) + 1);
    return s;
}

主要實現顯示大數的函式 `bn_to_string` ，因沒有資料型態能夠顯示出超過一定位元的數字，因此將儲存至 char 型別的陣列之中。
其運作方式如下，考慮二進位表示 10101001 ，則十進位表示為 169 ，可以發現，要將1、6、9 這三個數字儲存至 cahr 陣列 `s` ， `s[0]` 儲存 `1` ， `s[1]` 儲存 `6` ， `s[2]` 儲存 `9`，我們希望是得到以上的結果，陣列中，靠前(位子接近 0)的位子，儲存十進位中較高的位元。
觀察函式 16 行的 for 迴圈，因為前幾 bits 皆為 0 ，不會有任何行為，我們從開始碰到 1 開始討論，以下是過程。

 v             v              v              v             v              v
 10101001     10101001      10101001      10101001     10101001      10101001

s[0][1][2]    s[0][1][2]   s[0][1][2]   s[0][1][2]   s[0][1][2]   s[0][1][2]
  0  0  1       0  0  2      0  0  5      0  1  0      0  2  1      0  4  2

        v            v
  10101001    10101001

s[0][1][2]   s[0][1][2]
  0  8  4      1  6  9

可以發現，第一次碰到的 1 ，會通過第 20 行來進行乘以 2 的行為，如果需要進位，則透過第 21 ~ 23 行來處理，這行為會做剩餘還未處理的二進位的個數次數，因此第一個 1 會乘以 2 七次，也就會得到 128 ，為我們需要的數字，透過這方法，後面的數字就同理，就能使用 char 型別陣列來表示十進位數字。

透過 `bn` 結構，已能印出 f(1000) 。

### 分析執行時間

+ static ktime_t kt;
  /* calculate the fibonacci number at given offset */
  static ssize_t fib_read(struct file *file,
                         char *buf,
                         size_t size,
                         loff_t *offset)
  {
     bn *fib = bn_alloc(1);
+    kt = ktime_get();
     bn_fib_fdoubling(fib, *offset);
+    kt = ktime_sub(ktime_get(), kt);
     char *s = bn_to_string(*fib);
     copy_to_user(buf, s, strlen(s) + 1);
     bn_free(fib);
-    return strlen(s) + 1;
+    return ktime_to_ns(kt);
 }

在執行 `bn_fib_fdoubling` 前後加入 `kt` 的計算，可以得到執行運算的時間，在透過 `client` 呼叫， `bn_fib_fdoubling` 的執行時間入下圖所示。
有許多峰值，~~但最令人疑惑的是運算時間沒有隨著 n 值成長。(也許我該好好的審視一下大數運算)~~
關於時間沒有隨著 n 值成長，是因為 `bn_fib_fdoubling` 不管 n 是多少，裡面的 for 迴圈都會執行 32 次，因此所有 n 值的情況下，執行時間都差不多。
(猜測)而出現峰值的時候應該是執行了 `bn_resize` 。
將 `bn_to_string` 時間也考慮進去後，得到下圖。
可以得知運算耗時的地方在於將 2 進位轉換成字串的運算上。
透過作業提供的 [script](https://github.com/colinyoyo26/fibdrv/commit/4ce43c4e7ee0b80c4ce9e6dcd995bbfdf239206c) 來求出 kernel 與 user 端的效能表現。