# 2023q1 Homework3 (quiz3)

contributed by < `ShallowFeather` >

## 開發環境

$ uname -r
5.15.0-67-generic
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
架構：                           x86_64
CPU 作業模式：                   32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
每核心執行緒數：                 2
每通訊端核心數：                 4
Socket(s):                       1
NUMA 節點：                      1
供應商識別號：                   GenuineIntel
CPU 家族：                       6
型號：                           158
Model name:                      Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz
製程：                           10
CPU MHz：                        2400.000
CPU max MHz:                     4100.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4800.00
虛擬：                           VT-x
L1d 快取：                       128 KiB
L1i 快取：                       128 KiB
L2 快取：                        1 MiB
L3 快取：                        8 MiB

## 開發紀錄
### 費氏數列

static long long fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    if (k < 2)
        return k;
    __uint128_t a = 0, b = 1, t1, t2;

    int len = 64 - __builtin_clzl(k);
    while (len > 0) {
        t1 = a * (2 * b - a);
        t2 = b * b + a * a;
        a = t1; b = t2;
        if (k >> (--len) & 1) {
            t1 = a + b;
            a = b; b = t1;
        }
    }
    return a;
}

#### 支援大數運算
踩坑 撰寫完 `bn.h` 以及 `bn.c` 後將 Makefile 當中改成

obj-m := $(TARGET_MODULE).o
$(TARGET_MODULE)-objs := bn.o fibdrv.o

但因為 module 名稱與輸出檔案相同 因此會報錯

ERROR: modpost: missing MODULE_LICENSE() in /home/sf/fibdrv/fibdrv.o

新增 `bn.c` 和 `bn.h` 用於支援大數運算，參考 bignum 以及 L04
將 `fibdrv.c` 當中的數值限制刪除，並將讀取形制從數值轉換成字串

//fibdrv.c
static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *res = fib_sequence(*offset);
    if (copy_to_user(buf, res->number, res->size * sizeof(int)))
        return -EFAULT;
    int sz = res->size;
    bn_free(res);
    return (ssize_t) sz;
}

// client.c
for (int i = offset; i >= 0; i--) {
    lseek(fd, i, SEEK_SET);
    sz = read(fd, buf, 1);
    char *str = bn_to_string(buf, sz);
    printf("Reading from " FIB_DEV
           " at offset %d, returned the sequence "
           "%s.\n",
        i, str);
    free(str);
}

## 效能分析
在 `Makefile` 中新增一個 `plot` 指令用於分析效能，並製作線性圖方便觀察，且降低其他影響運算速度的因素。

plot: all
	sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
	sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
	sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
	$(MAKE) unload
	$(MAKE) load
	@python3 plot.py
	$(MAKE) unload

而測量結果如圖