2023q1 Homework3 (fibdrv)

contributed by < willwillhi1 >

實驗環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  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
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
Stepping:                        12
CPU MHz:                         2100.000
CPU max MHz:                     4200.0000
CPU min MHz:                     400.0000
BogoMIPS:                        4199.88
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

開發紀錄

執行 make check 遇到的問題

$ make check
cc -o client client.c
make -C /lib/modules/5.15.0-52-generic/build M=fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.15.0-52-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.15.0-52-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 mokutil --disable-validation
  

• 重新開機，選擇 Change Secure Boot State
• 之後就可以正常執行
  ​​​​$ make check
  ​​​​make -C /lib/modules/5.15.0-52-generic/build M=/home/will/fibdrv modules
  ​​​​make[1]: Entering directory '/usr/src/linux-headers-5.15.0-52-generic'
  ​​​​make[1]: Leaving directory '/usr/src/linux-headers-5.15.0-52-generic'
  ​​​​make unload
  ​​​​make[1]: Entering directory '/home/will/fibdrv'
  ​​​​sudo rmmod fibdrv || true >/dev/null
  ​​​​[sudo] password for will: 
  ​​​​rmmod: ERROR: Module fibdrv is not currently loaded
  ​​​​make[1]: Leaving directory '/home/will/fibdrv'
  ​​​​make load
  ​​​​make[1]: Entering directory '/home/will/fibdrv'
  ​​​​sudo insmod fibdrv.ko
  ​​​​make[1]: Leaving directory '/home/will/fibdrv'
  ​​​​sudo ./client > out
  ​​​​make unload
  ​​​​make[1]: Entering directory '/home/will/fibdrv'
  ​​​​sudo rmmod fibdrv || true >/dev/null
  ​​​​make[1]: Leaving directory '/home/will/fibdrv'
  ​​​​ Passed [-]
  ​​​​f(93) fail
  ​​​​input: 7540113804746346429
  ​​​​expected: 12200160415121876738
  

實驗環境的設定

• 撰寫 perfomance.sh，讓 cpu 只注重效率，將頻率固定在其支持的最高運行頻率上。
  ​​​​for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
  ​​​​do
  ​​​​    echo performance > ${i}
  ​​​​done
  

• 抑制 address space layout randomization (ASLR)，ASLR 全名為 Address Space Layout Randomization (地址空間佈局隨機化)，它可以將 process 的某些內存空間地址進行隨機化來增加入侵者預測目的地址的難度，從而降低被入侵的風險。
  ​​​​$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
  

• 限定 CPU 給特定的程式使用，修改 /etc/default/grub 內的 GRUB_CMDLINE_LINUX_DEFAULT 為 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7" ，修改完成後需 sudo update-grub 來更新設定，重開機後即生效
• 可用 cat /sys/devices/system/cpu/isolated
• 或用 taskset -cp 1，來確認是否生效
  ​​​​$ taskset -cp 1
  ​​​​pid 1's current affinity list: 0-6
  

• 之後用 taskset -c 7 command 執行測試程式

開發過程

前期準備

cat /sys/class/fibonacci/fibonacci/dev

輸出結果代表註冊的 fibdrv 的 Major and Minor Numbers

$ cat /sys/class/fibonacci/fibonacci/dev
509:0

509 代表動態申請的主設備號
也可以用 ls -l /dev | grep fib 找到

crw-------   1 root root    509,     0  3月  2 15:57 fibonacci

• 編譯 linux kernel moudle
  • 修改完 fibdrv.c 後，用 make all 來編譯
  • 之後先用 make unload 移除之前的模組
  • 再用 make load 載入新編譯後的模組

fast-doubling 加速 Fibonacci 運算

以下為原始版本的演算法:

static long long easy_fib(int k)
{
    long long f[k + 2];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[k];
}

用作業提示的 fast-doubling 實作 fibonacci，參考作業說明和 Calculating Fibonacci Numbers by Fast Doubling 的解說。
公式列在下方:

$$\begin{array}{rl}& F(2k)=2F(k)\times F(k+1)-F(k{)}^2\\ & F(2k+1)=F(k{)}^2+F(k+1{)}^2\end{array}$$

修改過後的程式碼:
以 n = 0b101 為例，
當迴圈走到最左邊的 1 時(也就是目前總共是 0b1)，會先計算 F(2K) 和 F(2K+1)，之後在用這兩個結果算出 a = F(2K+1) 和 b = F(2K+2) = F(2K) + F(2K+1)。
接著往右移一位遇到 0，相當於把先前的結果乘二即可(0b1 -> 0b10)，也就是 6、7 行。
最後遇到 1，就是將上一步的結果乘二 (0b10 -> 0b100)，再加 1 (9 ~ 11 行) 得到 0b101。

static long long double_fib(int n)
{
    long long a = 0; 
    long long b = 1;
    for (int i = 31; i >= 0; --i) {
        long long c = a * (2 * b - a);
        long long d = a * a + b * b;

        if ((n >> i) & 1) { 
            a = d;          
            b = c + d;      
        } else {            
            a = c;          
            b = d;          
        }
    }
    return a;
}

其中

for (int i = 31; i >= 0; --i)

可以用 __builtin_clz 加速

int i = 31 - __builtin_clz(n);

這麼做可以不需要每次迴圈都從 31 開始，透過 clz 可以直接從最高位 1 開始做，接下來用 gunplot 來製圖

if-else 的部份

if ((n >> i) & 1) { 
    a = d;          
    b = c + d;      
} else {            
    a = c;          
    b = d;          
}

可以用以下程式代替

mask = -!!(n & (1UL << i));

a = (c & ~mask) + (d & mask);
b = (c & mask) + d;

• n & (1UL << i) 表示只保留 n 的第 i 個 bit，其餘 bits 都是零，而 -!! 這個操作可以讓 mask:
  1. mask = -1，如果 n 的第 i 個 bit 為 1
  2. mask = 0，如果 n 的第 i 個 bit 為 0

最後的程式會是:

static long long fib_sequence(int n)
{
    long long a = 0; 
    long long b = 1;
    long long mask;
    for (int i = 31 - __builtin_clz(n); i >= 0 ; --i) {
        long long c = a * (2 * b - a);
        long long d = a * a + b * b;

        mask = -!!(n & (1UL << i));
        a = (c & ~mask) + (d & mask);
        b = (c & mask) + d;
    }
    return a;
}

接下來測試不同實作的時間分佈
write 實作 naive 版本
read 實作 fast doubling 版本

static inline long elapse(struct timespec start, struct timespec end)
{
    return ((long) 1.0e+9 * end.tv_sec + end.tv_nsec) -
           ((long) 1.0e+9 * start.tv_sec + start.tv_nsec);
}

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);

    clock_gettime(CLOCK_REALTIME, &t1);
    write(fd, write_buf, strlen(write_buf));
    clock_gettime(CLOCK_REALTIME, &t2);
    printf("%d ", i);
    printf("%ld ", elapse(t1, t2));

    clock_gettime(CLOCK_REALTIME, &t1);
    read(fd, buf, 1);
    clock_gettime(CLOCK_REALTIME, &t2);
    printf("%ld\n", elapse(t1, t2));
}

然後用 gunplot 製圖

圖例應為 naive vs. fast doubling

jserv

kernel, user space & system call time

使用作業說明提及的 ktime 在核心模組中測量執行時間，實作在 write 函式裡，並回傳 kernel space 執行時間。

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    ktime_t k1, k2;
    k1 = ktime_get();
    long long result = double_fib(*offset);
    k2 = ktime_sub(ktime_get(), k1);
    return ktime_to_ns(k2);
}

user space 在呼叫 write 前後用 clock_gettime 計算 user space 的時間，最後可以把 kernel time, user time 相減得到 system call 的時間。

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);

    clock_gettime(CLOCK_REALTIME, &t1);
    kernel_time = write(fd, buf, 1);
    clock_gettime(CLOCK_REALTIME, &t2);
    printf("%d ", i);
    /* user space execute time */
    printf("%ld ", elapse(t1, t2));
    /* kernel space execute time */
    printf("%ld ", kernel_time);
    /* system call overhead between kernel and user space */
    printf("%ld\n", elapse(t1, t2)-kernel_time);
}

大數運算

先看懂 作業說明的大數運算部份

struct bn

使用以下結構體來進行大數運算

• number 是儲存整個數值的陣列，以 unsigned int 為單位也就是 32 bits，由低位元依序存到高位元。
• size 代表該陣列的長度。
• sign 代表該數為正或負。

typedef struct _bn {
    u8 *number;
    unsigned int size;
    int sign;
} bn;

bn_clz

計算 src 的陣列的 leading zero。

/* count leading zeros of src*/
static int bn_clz(const bn *src)
{
    int cnt = 0;
    for (int i = src->size - 1; i >= 0; i--) {
        if (src->number[i]) {
            // prevent undefined behavior when src = 0
            cnt += __builtin_clz(src->number[i]);
            return cnt;
        } else {
            cnt += 32;
        }
    }
    return cnt;
}

bn_to_string

for 迴圈要是主要處理轉成二進位轉成十進位字串的地方，每 32 bits 處理一次。

• 由 src->number 的最高位(msb)逐一放入字串的最高位(msb)並處理。
• 用 carry 來代表是否進位，初始化為 !!(d & src.number[i])，代表該 bit 是否為 0 或 1。
• for (int j = len - 2; j >= 0; j--)，每次累加一個 bit 時都要跑整個字串的長度的迴圈。
• 累加的方式為 s[j] += s[j] - '0' + carry，原本的數值乘以二再加上 carry，最後還要處理進位問題。

/* 
 * 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_add

bn_add 是先用判斷正負號後再依照案例使用 bn_do_add 和 bn_do_sub 進行無號整數的計算。

/* c = a + b 
 * Note: work for c == a or c == b
 */
void bn_add(const bn *a, const bn *b, bn *c)
{
    if (a->sign == b->sign) { // both positive or negative
        bn_do_add(a, b, c);
        c->sign = a->sign;
    } else { // different sign
        if (a->sign)  // let a > 0, b < 0
            SWAP(a, b);
        int cmp = bn_cmp(a, b);
        if (cmp > 0) {
            /* |a| > |b| and b < 0, hence c = a - |b| */
            bn_do_sub(a, b, c);
            c->sign = 0;
        } else if (cmp < 0) {
            /* |a| < |b| and b < 0, hence c = -(|b| - |a|) */
            bn_do_sub(b, a, c);
            c->sign = 1;
        } else {
            /* |a| == |b| */
            bn_resize(c, 1);
            c->number[0] = 0;
            c->sign = 0;
        }
    }
}

bn_do_add

進行無號整數加法 (c = |a| + |b|)

• DIV_ROUNDUP(x, len) 的定義為 (((x) + (len) -1) / (len))，簡單來說就是除法無條件進位。
• !d 應該不用加，因為 d 不可能是 0。
• for 迴圈部份則是執行簡單的加法。

/* |c| = |a| + |b| */
static void bn_do_add(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b)) + 1
    int d = MAX(bn_msb(a), bn_msb(b)) + 1;
    d = DIV_ROUNDUP(d, 32) + !d;
    bn_resize(c, d); // round up, min size = 1

    unsigned long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry += (unsigned long long int) tmp1 + tmp2;
        c->number[i] = carry;
        carry >>= 32;
    }

    if (!c->number[c->size - 1] && c->size > 1)
        bn_resize(c, c->size - 1);
}

bn_do_sub

• |a| > |b| 條件一定要成立。
• 由於 carry 計算時可能會需要與 1LL << 32 相加，超過 unsigned int 大小，所以 carry 型別要宣告為 long long int。
• (long long int) tmp1 - tmp2 - carry 結果若小於 0 就需要借位。
• 最後 bn_resize(c, c->size - d)，把多餘的零去掉。

static void bn_do_sub(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b))
    int d = MAX(a->size, b->size);
    bn_resize(c, d);

    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry = (long long int) tmp1 - tmp2 - carry;
        if (carry < 0) {
            c->number[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->number[i] = carry;
            carry = 0;
        }
    }
    
    d = bn_clz(c) / 32;
    if (d == c->size)
        --d;
    bn_resize(c, c->size - d);
}

bn_mult

邏輯就像一般的乘法一樣，慢慢累加上去
另外處理 c 有可能是 a 或 b 的情況，會先用 tmp 來存 c 原本的位址避免 a 或 b 的值被改變，等最後做完乘法再 swap 回來。

void bn_mult(const bn *a, const bn *b, bn *c)
{
    // max digits = sizeof(a) + sizeof(b))
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d; // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c; // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
        for (int i = 0; i < c->size; i++)
            c->number[i] = 0;
        bn_resize(c, d);
    }
    
    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_swap(tmp, c); // restore c
        bn_free(c);
    }
}

bn_lshift

原本的版本程式碼如下，會限制 shift 在 31 以下，然後根據 shift 是否大於 leading zero 來判斷重新 resize dest 的大小。

/* left bit shift on bn (maximun shift 31) */
void bn_lshift(const bn *src, size_t shift, bn *dest)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z) {
        bn_resize(dest, src->size + 1);
    } else {
        bn_resize(dest, src->size);
    }
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        dest->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    dest->number[0] = src->number[0] << shift;
}

後來我在進行 10110001000110010010010011100001(剛好 32 bits) 向左 shift 1 時會出錯輸出 01100010001100100100100111000010，很明顯是最高位的 1 被吃掉了，後來我發現如果 dest 被 resize 成大小為 src->size + 1，需要額外處理 dest 陣列的最後一個 unsigned int (第三行)。

if (shift > z) {
    bn_resize(dest, src->size + 1);
    dest->number[src->size] = src->number[src->size - 1] >> (32 - shift);
} else {
    bn_resize(dest, src->size);
}

這麼一來 fast doubling 需要用到的函式幾乎都有了，接下來就是拿作業說明提供的 bn_fib_fdoubling 函式來跑即可。

bn_fib_fdoubling 改進

原始版本的 bn_fib_fdoubling 為以下：

void bn_fib_fdoubling(bn *dest, unsigned int n)
{
    bn_resize(dest, 1);
    if (n < 2) {  // Fib(0) = 0, Fib(1) = 1
        dest->number[0] = n;
        return;
    }

    bn *f1 = dest;        /* F(k) */
    bn *f2 = bn_alloc(1); /* F(k+1) */
    f1->number[0] = 0;
    f2->number[0] = 1;
    bn *k1 = bn_alloc(1);
    bn *k2 = bn_alloc(1);

    for (unsigned int i = 1U << 31; i; i >>= 1) {
        /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
        bn_cpy(k1, f2);
        bn_lshift(k1, 1, k1);
        bn_sub(k1, f1, k1);
        bn_mult(k1, f1, k1);
        /* F(2k+1) = F(k)^2 + F(k+1)^2 */
        bn_mult(f1, f1, f1);
        bn_mult(f2, f2, f2);
        bn_cpy(k2, f1);
        bn_add(k2, f2, k2);
        if (n & i) {
            bn_cpy(f1, k2);
            bn_cpy(f2, k1);
            bn_add(f2, k2, f2);
        } else {
            bn_cpy(f1, k1);
            bn_cpy(f2, k2);
        }
    }
    bn_free(f2);
    bn_free(k1);
    bn_free(k2);
}

後來利用 __builtin_clz 硬體指令可以直接從最高位的 1 開始計算，減少迴圈數。
接著為了避免執行 bn_mult 的 (c == a || c == b) 會用 tmp 來儲存 c 的情況所以用以下邏輯來避免這個情況。

/* f1 = F(k)   */
/* f2 = F(k+1) */
for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
    /* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */ 
    bn_lshift(f2, 1, k1); // k1 = 2 * F(k+1)
    bn_mult(k1, f1, k2);  // k2 = 2 * F(k+1) * F(k)
    bn_mult(f1, f1, k1);  // k1 = F(k) * F(k) 
    bn_sub(k2, k1, f1);   // f1 = F(2k) = 2 * F(k+1) * F(k) - F(k) * F(k)
    /* F(2k+1) = F(k)^2 + F(k+1)^2 */
    bn_mult(f2, f2, k2);  // k2 = F(k+1) * F(k+1)
    bn_add(k1, k2, f2);   // f2 = F(2k+1) = F(k)^2 + F(k+1)^2

    if (n & i) {
        bn_swap(f1, f2);       // f1 = F(2k+1)
        bn_add(f1, f2, f2);    // f2 = F(2k+2)
    }
}

fib v0 代表修改前，fib v1 代表修改後，由此可見 bn_alloc() 的成本是很高的。

減少 realloc 次數

為了避免每次呼叫 bn_resize 時都會執行 realloc 造成對記憶體頻繁的修剪。
在 bn 結構體多加入了一個變數 capacity，用來事先配置額外的記憶體，所以在每次呼叫 resize 時都會先判斷是否還有空間可以使用 (capacity > resize size)，若是則可以直接回傳，避免再次執行 realloc。

static int bn_resize_v1(bn *src, size_t size)
{
    ...
    if (src->capacity < size) {
        src->capacity = (size+(CHUNK_SIZE-1)) & ~(CHUNK_SIZE-1);
        src->number = realloc(src->number, sizeof(unsigned int) * src->capacity);
    }
    ...
}

用 perf 比較前後結果，計算 fib(1) ~ fib(10000)，可以發現 cache-references 確實有明顯的下降。

BRFORE
 Performance counter stats for './experiment/exp4' (5 runs):

            48,912      cache-misses              #    4.071 % of all cache refs      ( +- 21.01% )
         1,665,299      cache-references                                              ( +- 18.85% )
    19,037,748,191      instructions              #    2.05  insn per cycle           ( +-  0.00% )
     9,267,320,914      cycles                                                        ( +-  0.07% )

            7.06808 +- 0.0124 seconds time elapsed  ( +-  0.17% )


---------------------------
AFTER
 Performance counter stats for './experiment/exp4' (5 runs):

            49,883      cache-misses              #    4.824 % of all cache refs      ( +- 30.55% )
           365,370      cache-references                                              ( +- 98.70% )
    19,034,628,079      instructions              #    2.05  insn per cycle           ( +-  0.00% )
     9,255,791,613      cycles                                                        ( +-  0.15% )

           5.81458 +- 0.00717 seconds time elapsed  ( +-  0.12% )

用 verify.py 驗證

verify.py 會產生 fib(0) ~ fib(想要測量到的範圍) 並存放在 expect 裡，隨後讀取 out 並存在 result，經過處理後將答案存在 dice，

#!/usr/bin/env python3

expect = [0, 1]
result = []
result_split = []
dics = []

for i in range(2, 1001):
    expect.append(expect[i - 1] + expect[i - 2])
with open('out', 'r') as f:
    tmp = f.readline()
    while (tmp):
        result.append(tmp)
        tmp = f.readline()
    f.close()
for r in result:
    if (r.find('Reading') != -1):
        result_split.append(r.split(' '))
        k = int(result_split[-1][5].split(',')[0])
        f0 = int(result_split[-1][9].split('.')[0])
        dics.append((k, f0))
for i in dics:
    fib = i[1] 
    if (expect[i[0]] != fib):
        print('f(%s) fail' % str(i[0]))
        print('input: %s' %(fib))
        print('expected: %s' %(expect[i[0]]))
        exit(1)

最後去跟 expect 做比較，如果有錯就會輸出類似以下的訊息:

f(93) fail
input: -6246583658587674878
expected: 12200160415121876738

目前測試到 1000 為止答案都是正確的。

Reading from /dev/fibonacci at offset 1000, returned the sequence 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.

觀察 make check 時會執行的命令，
發現 expected.txt 不會變更到，所以

@diff -u out scripts/expected.txt && $(call pass)

就用 verify.py 來驗證，改為以下:

@scripts/verify.py && $(call pass)

且 verify.py 裡的 exit() 改為 exit(1)，代表執行期間有錯誤發生 (與預期答案不符)。

測量 user space 和 kernel space 的傳遞時間

原本的大數運算方式是直接在 kernel space 執行 bn_to_string 將 bn->number 轉成字串後通過 copy_to_user 將答案傳回 user space。
但是實作的大數結構是用一個 unsigned int 陣列來表示

• 以 0xffffffff 為例，其所需要的空間是 4 Byte。
• 轉為十進位是 4294967295，因為這邊是用字元表示所以所需空間是 10 byte，大於二進位表示時所需的空間。

所以我將傳送的方式改成傳送 bn->number 到 user space 而不是空間佔用較大的字串，
直接將計算結果透過 copy_to_user 傳送。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *fib = bn_alloc(1);
    bn_fib_fdoubling(fib, *offset);
    size = fib->size;
    copy_to_user(buf, fib->number, sizeof(unsigned int)*size);
    bn_free(fib);
    return size;
}

接著由 client 接收，並用修改過後的 bn_to_str 將其轉成字串。

char buf[1000];
int offset = 1000; /* TODO: try test something bigger than the limit */

int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
    perror("Failed to open character device");
    exit(1);
}

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    unsigned int size = read(fd, buf, 1000);
    char *p = bn_to_str(buf, size, 0);
    printf("Reading from " FIB_DEV
           " at offset %d, returned the sequence "
           "%s.\n",
           i, p);
}

最後對 copy_to_user 的執行時間做比較，可以發現傳送所花費的時間確實有差，而且數字越大越明顯。

但是這麼做會造成將 bn 轉成十進位需要在 user space 做相對於在 kernel space 還要花時間，原因推測是因為 bn_to_string 會呼叫到 malloc 需要切換到 Supervisor mode，導致時間花費會比較高。
malloc 是 library function，底下實際的實作是透過 sbrk 或 mmap。

malloc 不是系統呼叫！請善用 perf 一類的工具分析執行成本。

jserv

後來發現編譯時用 -O3，之前沒用的時候導致修改後的 client 的 instructions 數過多導致執行時間變長。
接著用 perf 做比較可以發現兩個方法所花費的時間基本上差不多，但是 pass_number_array 相對減少了 copy_to_user 的時間，也就是傳送 bn->number 到 user space，然後在 user space 執行 bn_to_string。

• pass_number_array

 Performance counter stats for './client' (10 runs):

            156.76 msec task-clock                #    0.997 CPUs utilized            ( +-  0.08% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                83      page-faults               #  529.003 /sec                     ( +-  0.36% )
       250,231,871      cycles                    #    1.595 GHz                      ( +-  0.08% )
       774,286,066      instructions              #    3.09  insn per cycle           ( +-  0.00% )
        61,917,107      branches                  #  394.631 M/sec                    ( +-  0.01% )
           400,112      branch-misses             #    0.65% of all branches          ( +-  0.15% )

          0.157247 +- 0.000113 seconds time elapsed  ( +-  0.07% )

• pass_string

 Performance counter stats for './client' (10 runs):

            155.82 msec task-clock                #    0.946 CPUs utilized            ( +-  1.48% )
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                49      page-faults               #  299.439 /sec                     ( +-  0.68% )
       248,725,566      cycles                    #    1.520 GHz                      ( +-  1.43% )
       832,882,929      instructions              #    3.22  insn per cycle           ( +-  0.04% )
        62,446,804      branches                  #  381.613 M/sec                    ( +-  0.11% )
           400,226      branch-misses             #    0.64% of all branches          ( +-  0.68% )

           0.16468 +- 0.00242 seconds time elapsed  ( +-  1.47% )

原本以為會有明顯差距，但實際上沒有，
從以上結果可以看到 malloc 再執行時沒有呼叫 system call 因為沒有做 context switch，
所以我後來去查了一些可能的因素，發現 kmalloc 和 malloc 它們實作上的不同，
kmalloc 配置的記憶體是 physically contiguous 的，通常用於配置 128 KB 以下的空間。
而 malloc 拿到的記憶體是 virtual memory(也就是物理上不連續的記憶體)，所以當程式去修改這片記憶體時，就有可能會發生 page fault。
由以上兩點來看，剛好可以呼應前面的 perf 分析的 page fault 的結果。

進一步優化 copy_to_user 所需要複製的資料大小，目前的算法是陣列多大就複製多大，可優化的地方是最後一個元素的 leading zero 是不需要的，所以就只傳送最少所需要的位元組即可。

int count = 32 - __builtin_clz(fib->number[fib->size-1]);
count = (count >> 3) + !!(count & 0x7);
copy_to_user(buf, fib->number, sizeof(unsigned int) * (len-1) + count);

使用 sysfs 界面

為了取得比用 printk 更準確的時間，所以透過 sysfs 的界面來存取 fibdrv 的執行時間。
sysfs 描述：

The sysfs filesystem is a pseudo-filesystem which provides an interface to kernel data structures.(More precisely, the files and directories in sysfs provide a view of the kobject structures defined internally within the kernel.)The files under sysfs provide information about devices, kernel modules, filesystems,and other kernel components.

簡單來說 sysfs 可以提供一個界面 (kobject structures) 讓 user space 可以存取 kernel 內的資料結構。

• kobject
  • 定義於 linux/kobject.h，主要功能有：
    • reference count
    • 管理物件的鏈結串列(集合)，linux 風格的 linked list，嵌入在別的資料結構中使用
    • 將該物件的屬性導出到 user space(透過 sysfs)
  • kobject 在 sysfs 會以目錄的形式呈現。
  • 該物件具有的屬性(attribute)會以檔案的方式表示。
• attribute
  • 每個 kobject 都會有一到多個屬性，每個屬性都代表核心內的某資訊
  • 使用者可以通過 attribute 中的 show 和 store callback 函式來取得核心資訊
  • 對 attribute 進行讀取操作(ex: cat)時會執行 show
  • 對 attribute 進行寫入操作(ex: echo)時會執行 store

以下依照kobject-example.c的實作

設定 attribute

• __ATTR 定義在 linux/sysfs.h 中：

#define __ATTR(_name, _mode, _show, _store) {				\
	.attr = {.name = __stringify(_name),				\
		 .mode = VERIFY_OCTAL_PERMISSIONS(_mode) },		\
	.show	= _show,						\
	.store	= _store,						\
}

• 定義 show, store
  • store: 利用寫入的方式傳入要算第幾個費氏數列，並將執行時間紀錄在 kt。
  • show: 將 fibdrv 內的 kt 轉為奈秒後輸出。

static ssize_t show(struct kobject *kobj, 
                    struct kobj_attribute *attr,
                    char *buf)
{
    kt_ns = ktime_to_ns(kt);
    return snprintf(buf, 16, "%lld\n", kt_ns);
}

static ssize_t store(struct kobject *kobj, 
                    struct kobj_attribute *attr,
                    const char *buf,
                    size_t count)
{
    int ret, n_th;
    if (ret = kstrtoint(buf, 10, &n_th)) {
        return ret;
    }
    bn *fib = bn_alloc(1);
    kt = ktime_get();
    bn_fib_fdoubling(fib, n_th);
    kt = ktime_sub(ktime_get(), kt);
    bn_free(fib);
    return count;
}

• 設定 attribute

struct kobject *fib_ktime_kobj;
static ktime_t kt;
static long long kt_ns;

// 設定一個 attribute 叫做 kt_ns，並設定權限為 rw-rw-r--
static struct kobj_attribute ktime_attr = __ATTR(kt_ns, 0664, show, store); 

// 定義 kobject 的 attributes，可以有一到多個
static struct attribute *ktime_attrs[] = {
    &ktime_attr.attr,
    NULL,
};

// 把 attribute 封裝成 attribute_group，之後建立 sysfs 界面時使用
static struct attribute_group ktime_attr_group = {
    .attrs = ktime_attrs,
};

建立目錄

• 利用 kobject_create_and_add 在 /sys/kernel/ 下建立 fib_ktime 目錄。
• 然後用 sysfs_create_group 把剛剛建立的屬性放到這個目錄下。

fib_ktime_kobj = kobject_create_and_add("fib_ktime", kernel_kobj);
if (!fib_ktime_kobj)
    return -ENOMEM;

int retval = sysfs_create_group(fib_ktime_kobj, &ktime_attr_group);
if (retval)
    goto failed_sysfs_create;

最後用 kobject_put 減少 reference count。

static void __exit exit_fib_dev(void)
{
    mutex_destroy(&fib_mutex);
    device_destroy(fib_class, fib_dev);
    class_destroy(fib_class);
    cdev_del(fib_cdev);
    unregister_chrdev_region(fib_dev, 1);
    kobject_put(fib_ktime_kobj);
}

簡單測試

• 測試 fib(1000) 的執行時間

will@will:/sys/kernel/fib_ktime$ sudo sh -c "echo 1000 > kt_ns"
will@will:/sys/kernel/fib_ktime$ sudo cat kt_ns 
8838