# 2023q1 Homework3 (fibdrv)
contributed by < `ItisCaleb` >

## 開發環境

$ uname -r
6.2.1-arch1-1

$ gcc --version 
gcc (GCC) 12.2.1 20230201

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i5-12400
    CPU family:          6
    Model:               151
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    CPU(s) scaling MHz:  16%
    CPU max MHz:         5600.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4993.00

## 開發紀錄

原本使用 `read` 來傳遞結果，但因為 `ssize_t` 最多只有 64 位元，所以改用 `copy_to_user` 把計算的結果傳遞到 user 提供的 buffer

支援大數運算後則是把 `int` 陣列傳遞到 buffer，然後回傳陣列的長度

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;

> [commit 6168e5a](https://github.com/ItisCaleb/fibdrv/commit/6168e5ad90391758ad90691666de8a550c36d6f7)

加了 `bn.h` 後需要修改 Makefile
`fibdrv-objs` 是 module 所需要的 object，由於 target 不能跟其他 obj 重複命名，所以把 `fibdrv.c` 重新命名成 `fibdrvko.c`

@@ -2,6 +2,8 @@
obj-m := $(TARGET_MODULE).o
+fibdrv-objs := bn_kernal.o bn.o fibdrvko.o

----

### 大數運算
新增 `digit_t` 使得大數運算使用的類別可以根據使用的是 32 位元或是 64 位元的架構來切換
[commit a440b72 `Decouple the type used during computation`](https://github.com/ItisCaleb/fibdrv/commit/a440b72677f5c0d0027ac7f41d333d25a2c1ed2c)

把 `bn_alloc` 及 `bn_free` 等跟記憶體配置相關的函式分離到 `bn_client.c` 及`bn_kernal.c`，使得可以在 client 使用大數運算，不需要再透過 Kernal Module 去測試，避免在實作或是改進原本函式時導致 Segment fault，造成需要重新開機
[commit b0426ea `Separate some utility function`](https://github.com/ItisCaleb/fibdrv/commit/b0426ea3af275165d07f263c6d68b56d3a6053a8)

### 費氏數列
引入大數運算後，原本先用迭代法來作為大數運算的測試
最新版的是用 Fast Doubling 的手法去實作
乘二以及平方的操作改用 `bn_lshfit` 及 `bn_sqr`

static bn *fib_sequence(uint64_t n)
{
    bn *a = bn_alloc(1);
    if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
        a->number[0] = n;
        return a;
    }
    int len = 64 - __builtin_clzl(n);
    bn *b = bn_alloc(1);
    b->number[0] = 1;
    bn *t1 = bn_alloc(1);

    while (len > 0) {
        // t1 = a * (2 * b - a)
        bn_lshift(b, 1, t1);
        bn_sub(t1, a, t1);
        bn_mult(a, t1, t1);

        // t2 = b^2 + a^2
        // b = t2
        bn_sqr(b, b);
        bn_sqr(a, a);
        bn_add(a, b, b);
        // a = t1
        bn_swap(a, t1);
        if (n >> (--len) & 1) {
            bn_add(a, b, t1);
            bn_swap(a, b);
            bn_swap(b, t1);
        }
    }
    bn_free(b);
    bn_free(t1);
    return a;
}

> [commit aac8fb7 `Improve big number`](https://github.com/ItisCaleb/fibdrv/commit/aac8fb7e4876a07a9df36420693b82f536741447#diff-5fdd043fc53edd4ddf5414cfadd0348064f484953487781197861c6f64592491)

### 時間測量

Makefile 增加選項 `test`
並且使用`sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"`及`sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"`
來分別關閉 ASLR 跟 turbo mode 避免影響效能分析
同時使用 taskset 來指定 cpu 給程式使用

`plot.py` 則會對資料的極端值並且畫成圖表

test: 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"
	$(MAKE) unload
	$(MAKE) load
	sudo taskset 0x2 ./client
	$(MAKE) unload
	sudo sh -c "echo 1 > /proc/sys/kernel/randomize_va_space"
	sudo sh -c "echo 0 > /sys/devices/system/cpu/intel_pstate/no_turbo"
	python3 plot.py

> taskset 0x2

如果使用 `isolcpus=0` 及 `taskset 0x1` 是沒辦法跑出如此平滑的曲線的，並且指定其他的 CPU 也同樣都會有很大的波動
只有當設置 `isolcpus=0` 且指定為 CPU1 的時候才會有上圖的結果
不知道是什麼原因造成的
:::warning
閱讀 [SMP IRQ affinity](https://www.kernel.org/doc/html/next/core-api/irq/irq-affinity.html) 並留意到每個處理器核的中斷事件。
:notes: jserv
:::

> taskset 0x1

在使用 Fast Doubling 手法後，可以很明顯看到效率遠優於使用迭代法

在改用 u64 後，效率相比原本使用 u32 明顯提昇
而在實作 `bn_lshift` 後，執行效率也有些許提昇