# 2021q1 Homework3 (fibdrv)
contributed by < `gyes00205` >
###### tags: `linux2021`
> [作業要求](https://hackmd.io/@sysprog/linux2021-fibdrv)

## 安裝工具

$ sudo apt install linux-headers-`uname -r`
$ sudo apt-get update`
$ sudo apt install util-linux strace gnuplot-nox

## 遇到問題
* 執行 `$ make check`

    $ make check
    cc -o client client.c
    make -C /lib/modules/5.4.0-67-generic/build M=fibdrv modules
    make[1]: Entering directory '/usr/src/linux-headers-5.4.0-67-generic'
      CC [M]  fibdrv/fibdrv.o
    fibdrv/fibdrv.c: In function ‘fib_sequence’:
    fibdrv/fibdrv.c:30:5: warning: ISO C90 forbids variable length array ‘f’ [-Wvla]
       30 |     long long f[k + 2];
          |     ^~~~
      Building modules, stage 2.
      MODPOST 1 modules
      CC [M]  fibdrv/fibdrv.mod.o
      LD [M]  fibdrv/fibdrv.ko
    make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-67-generic'
    make unload
    make[1]: Entering directory 'fibdrv'
    sudo rmmod fibdrv || true >/dev/null
    rmmod: ERROR: Module fibdrv is not currently loaded
    make[1]: Leaving directory 'fibdrv'
    make load
    make[1]: Entering directory 'fibdrv'
    sudo insmod fibdrv.ko
    insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted
    make[1]: *** [Makefile:23: load] Error 1
    make[1]: Leaving directory 'fibdrv'
    make: *** [Makefile:37: check] Error 2

原來是忘記關閉 Secure Boot
* 關閉方式：

    $ sudo apt install mokutil
    $ sudo mokutil --disable-validation

接著重新啟動，按 `Esc` 鍵選擇 `Change Secure Boot State`
* 重新 `$ make check`

    $ make check
    make -C /lib/modules/5.4.0-70-generic/build M=fibdrv modules
    make[1]: Entering directory '/usr/src/linux-headers-5.4.0-70-generic'
      Building modules, stage 2.
      MODPOST 1 modules
    make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-70-generic'
    make unload
    make[1]: Entering directory 'fibdrv'
    sudo rmmod fibdrv || true >/dev/null
    [sudo] password for gyes00205: 
    rmmod: ERROR: Module fibdrv is not currently loaded
    make[1]: Leaving directory 'fibdrv'
    make load
    make[1]: Entering directory 'fibdrv'
    sudo insmod fibdrv.ko
    make[1]: Leaving directory 'fibdrv'
    sudo ./client > out
    make unload
    make[1]: Entering directory 'fibdrv'
    sudo rmmod fibdrv || true >/dev/null
    make[1]: Leaving directory 'fibdrv'
     Passed [-]
    f(93) fail
    input: 7540113804746346429
    expected: 12200160415121876738

### Fast doubling
利用 `__builtin_clzll(k)` 找出 leading zero number 。
將 `long long` 改為 `__uint128_t` ， `long long` 可以表達 64 bit 的有號數，因此可表達的最大正整數為 $2^{63} - 1$ $=$ $9,223,372,036,854,775,807$ ， `__uint128_t` 可表達最大正整數為 $2^{128} - 1$ 。

static __uint128_t fib_fast_doubling(long long k)
{
    __uint128_t a = 0, b = 1, t1, t2;
    for (long long i = 1 << (63 - __builtin_clzll(k)); i > 0; i >>= 1) {
        t1 = a * (2 * b - a);
        t2 = b * b + a * a;
        a = t1;
        b = t2;
        if (i & k) {
            t1 = a + b;
            a = b;
            b = t1;
        }
    }
    return a;
}

### 印出 128 bit 數字: 參考同學[hankluo6](https://hackmd.io/@hankluo6/fibdrv#%E5%A4%A7%E6%95%B8%E9%81%8B%E7%AE%97)的方法。
`ssize_t` 只能表達 64 bit 的整數，所以用 `copy_to_user` (需要 `#include <linux/uaccess.h>`) 取代 `ssize_t` 將 128 bit 傳到 `buf` 。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    __uint128_t ret = fib_fast_doubling(*offset);
    copy_to_user(buf, &ret, sizeof(ret));
    return 1;
    // return (ssize_t) fib_sequence(*offset);
}

另外在 `client.c` 實做 `print_u128_u()`

static int print_u128_u(__uint128_t u128)
{
    int rc;
    if (u128 > UINT64_MAX) {
        __uint128_t leading = u128 / P10_UINT64;
        uint64_t trailing = u128 % P10_UINT64;
        rc = print_u128_u(leading);
        rc += printf("%." TO_STRING(E10_UINT64) PRIu64, trailing);
    } else {
        uint64_t u64 = u128;
        rc = printf("%" PRIu64, u64);
    }
    return rc;
}

之後將 scripts/expected.txt 改為正確答案，執行 `make check`，成功 `Passed[-]` 。

$ make check
make -C /lib/modules/5.4.0-71-generic/build M=fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.4.0-71-generic'
  Building modules, stage 2.
  MODPOST 1 modules
make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-71-generic'
make unload
make[1]: Entering directory 'fibdrv'
sudo rmmod fibdrv || true >/dev/null
[sudo] password for gyes00205: 
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory 'fibdrv'
make load
make[1]: Entering directory 'fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory 'fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory 'fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory 'fibdrv'
 Passed [-]