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

加了 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

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

費氏數列

引入大數運算後，原本先用迭代法來作為大數運算的測試
最新版的是用 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

時間測量

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