Linux 核心專題: 重做 fibdrv

執行人: paulpeng-popo
專題解說錄影
 GitHub

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

提問清單

任務簡述

依據 fibdrv 作業規範，繼續投入 Linux 核心模組和相關程式的開發。

公式推導

假設成年兔子為 a，幼年兔子為 b，且兔子不死亡

a_{n + 1} = a_{n} + b_{n}

b_{n + 1} = a_{n}

一般遞迴

a_{n + 1} = a_{n - 1} + a_{n}, n \geq 1

a_{0} = 0, a_{1} = 1

矩陣運算 Q-matrix

[\begin{matrix} a_{n + 1} \\ b_{n + 1} \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} a_{n} \\ b_{n} \end{matrix}]

又可改寫成

[\begin{matrix} a_{n + 1} \\ a_{n} \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} a_{n} \\ a_{n - 1} \end{matrix}]

[\begin{matrix} a_{n + 1} & a_{n} \\ a_{n} & a_{n - 1} \end{matrix}] = {[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n}

Fast Doubling

F (0) = a_{0} = 0

F (1) = a_{1} = 1

\begin{aligned} [\begin{array}{c} F (2 n + 1) \\ F (2 n) \end{array}] & = {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{2 n} [\begin{array}{c} F (1) \\ F (0) \end{array}] \\ = {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{n} {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{n} [\begin{array}{c} F (1) \\ F (0) \end{array}] \\ = [\begin{array}{c} F (n + 1) & F (n) \\ F (n) & F (n - 1) \end{array}] [\begin{array}{c} F (n + 1) & F (n) \\ F (n) & F (n - 1) \end{array}] [\begin{array}{c} 1 \\ 0 \end{array}] \\ = [\begin{array}{c} F (n + 1)^{2} + F (n)^{2} \\ F (n) F (n + 1) + F (n - 1) F (n) \end{array}] \end{aligned}

其中

F (n - 1) = F (n + 1) - F (n)

最後得到

F (2 k) = F (k) [2 F (k + 1) - F (k)]

F (2 k + 1) = F (k + 1)^{2} + F (k)^{2}

Fast Doubling

F (2 k) = F (k) [2 F (k + 1) - F (k)]

F (2 k + 1) = F (k + 1)^{2} + F (k)^{2}

作業說明中的虛擬碼

Fast_Fib(n)
    a = 0; b = 1;       // m = 0
    for i = (number of binary digit in n) to 1
        t1 = a*(2*b - a);
        t2 = b^2 + a^2;
        a = t1; b = t2; // m *= 2
        if (current binary digit == 1)
            t1 = a + b; // m++
            a = b; b = t1;
    return a;

原理

這裡 Fast Doubling 利用比

$n$ 兩倍小的
$n^{'}$ 來算出

F (n)

，遞迴的深度則被限制在

O (\log n)

內，這可以大幅減少重複的計算

參考：Calculating Fibonacci Numbers by Fast Doubling

/* FILE: fibdrv.c */

static long long fib_fastd(long long n)
{
    if (n < 2)
        return n;

    long long a = 0;
    long long b = 1;
    for (int j = 63 - 1; j >= 0; j--) {
        long long c = a * ((b << 1) - a);
        long long d = a * a + b * b;
        a = c;
        b = d;

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

    return a;
}

n 小於 2，直接回傳，不會經過迴圈
從 n 的 MSB 開始，依序計算該數的費氏數，直到 n 的 LSB 或剩下之 bit 皆為 0，則提前跳出迴圈

先用 h 記錄實際的數字共有幾個 bit (不含 leading 0s)，接著從 MSB 開始計算首項費氏數，再藉由迴圈依次增加 n >> j 的 bit 數，以計算後續的費氏數

複雜度分析

每次迭代使用 3 個乘法跟 2 個加法，時間複雜度為
$O (1)$
根據輸入的 n 大小決定迭代次數，即最多做
$O (l o g n)$ 次遞迴
總共時間複雜度為
$O (1) * O (l o g n) = O (l o g n)$

解釋 fast doubling 為什麼用 2k 跟 2k + 1

例如：長度為 n 個 bit 的數字

$α$ 與長度為 n+1 個 bit 的數字
$β$ 具有以下關係：

if
$β$ 要為偶數，則
$β = 2 α$ ，也就是
$β$ =
$α$ << 1
if
$β$ 要為奇數，則
$β = 2 α + 1$ ，也就是
$β$ =
$α$ << 1 + 1

剛好就是 binary number 的進位規則

使用 __builtin_clzll function 做硬體上的計算加速
clz (Count Leading Zero) 可以計算數字 n 前面有幾個 0，加速取得 h 的速度

- for (int j = 63 - 1; j >= 0; j--) {
+ long long mask = 1LL << (63 - __builtin_clzll(n));
+ for (; mask; mask >>= 1) {

- if ((n >> j) & 1LL) {
+ if (mask & n) {

實作大數運算前的效能比較

VLA 改進

Linux kernel 不支援 VLA，因此使用 Dynamic Programming 與空間重複利用的技巧，避免動態陣列的使用，同時將 space complexity 從

O (n)

降到

O (1)

Linux 核心限制使用 VLA 的因素
在 The Linux Kernel is now VLA-Free 有提到 Linux kernel 不再允許 VLA 的使用

C99 具有 VLA (Variable-Length Array) 的特性，允許執行時期再決定陣列佔用的空間大小，但可能會造成 stack overflow 等安全疑慮
根據教材你所不知道的 C 語言：函式呼叫篇，攻擊者可以利用 stack-based-buffer-overflow 來執行惡意程式碼，從而對系統造成威脅

此外，Linus Torvalds 也說過：USING VLA'S IS ACTIVELY STUPID! It generates much more code, and much slower code (and more fragile code), than just using a fixed key size would have done.』

/* FILE: fibdrv.c */

static long long fib_sequence(long long k)
{
    long long f[2] = {0, 1};

    if (k < 2)
        return f[k];

    for (int i = 2; i <= k; i++) {
        f[i & 1] = f[0] + f[1];
    }

    return f[k & 1];
}

時間測量功能

參考時間測量與效能分析的說明與 qwe661234 的解釋

High resolution timers and dynamic ticks design notes

hrtimers - subsystem for high-resolution kernel timers

在 Linux 核心中具有兩種計時方式

jiffies 是 Linux kernel 較早期存在的計時方法，使用作業系統從開機以來的計時器中斷發生的次數作為計時的依據，此全域變數稱作 ticks 數。計時器中斷為週期性的中斷事件，以固定的時間間隔觸發，利用間隔固定的特性便能達到測量時間的目的。

通常情況下，jiffies 的精度為毫秒級別，具體的精度取決於 tick rate 的大小。例如 1000Hz 表示每秒觸發 1000 次的 timer interrupt，因此 jiffies 的增加速度為每毫秒一次。

jiffies 轉換為秒的公式為

(unsigned long long)(jiffies - INITIAL_JIFFIES) / HZ;

由以上程式碼可知，假如系統原先設定的 tick rate (HZ) 不大於

10^{9}

，其時間精度是無法達到 ns 等級的。

hrtimer 是在 2.6.16 開始有的新的計時機制，裡面使用了 ktime_t 這個資料結構來進行計時。書中提到，原本基於 jiffies 的計時機制 timer wheel 在許多層面上有許多缺失，並幾乎無法再優化/整合了，包括：

The forced handling of low-resolution and high-resolution timers in the same way leads to a lot of compromises, macro magic and #ifdef mess.

The unpredictable [O(N)] overhead of cascading leads to delays which necessitate a more complex handling of high resolution timers, which in turn decreases robustness.

The timer wheel data structure is too rigid for high-res timers.

因此實作 hrtimer 的設計考量包括

simplicity
data structure not bound to jiffies or any other granularity. All the kernel logic works at 64-bit nanoseconds resolution - no compromises
simplification of existing, timing related kernel code

ktime_t 結構體定義如下

union ktime {
	s64	tv64;
};

typedef union ktime ktime_t;

其結構體內有一型態為 64 位元的有號整數 tv64
跟據 Linux 原始碼 include/linux/ktime.h， ktime_t 的單位為奈秒 (ns)

透過呼叫 Linux kernel API ktime_get()，可以取得相對於系統啟動時間的偏移量，因此藉由計算出兩次 ktime_get() 的時間差異，便可知其之間的程式碼執行時間花費

/* FILE: fibdrv.c */

static ktime_t kt;

static long long fib_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = fib_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) fib_time_proxy(*offset);
}

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt);
}

在 read 的時候，計算 fib，並同時將所花時間儲存在 kt 中
接著 write 的時候，將 kt 的值轉換成 nanoseconds 再回傳給 client

client 中順序呼叫 read 和 write，即可取得所花費的 kernel time

/* FILE: client.c */

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    sz = read(fd, buf, 1);
    kt = write(fd, write_buf, 1);
}

執行 sudo ./client 後，成功輸出計算費氏數時間，輸出如下

Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Time: 331 (ns).
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Time: 197 (ns).
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Time: 183 (ns).
Reading from /dev/fibonacci at offset 3, returned the sequence 2.
Time: 113 (ns).
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
Time: 123 (ns).
Reading from /dev/fibonacci at offset 5, returned the sequence 5.
Time: 120 (ns).
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Time: 81 (ns).
Reading from /dev/fibonacci at offset 7, returned the sequence 13.
Time: 78 (ns).
Reading from /dev/fibonacci at offset 8, returned the sequence 21.
...

選擇演算法

參考 yanjiew1 的做法，利用 fib_read 傳入 size 作為使用不同演算法的條件

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)

/* FILE: fibdrv.c */

switch (size) {
case 1:
    result = fib_sequence(k);
    break;
case 2:
    result = fib_fastd(k);
    break;
case 3:
    result = fib_fastd_clz(k);
    break;
default:
    return -EINVAL;
}

使用 gnuplot 製圖，確認 fast doubling 確實加速費氏數的計算，同時發現 __builtin_clzll 大幅降低時間開銷

NOTE: 此處時間為 kernel mode 中計算的時間，還未加入 user space 的時間開銷比較

排除效能干擾因素

使用 taskset 預留 cpu 給效能測試使用

$ sudo vim /etc/default/grub
修改此行 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=5"
$ sudo update-grub
$ sudo init 6

將作業說明提到的方法寫成一個 script，包括：

關閉 ASLR（address space layout randomization
將 cpufrq 從 powersave 變成 performance
關閉 turbo mode
取消 cpu smp affinity

#!/bin/sh

CPUID=5
MASK=$((1 << $CPUID))
MASK=$((0xfff & ~$MASK))
MASK=`printf "%x" $MASK`
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`
ORIG_IRQ=`cat /proc/irq/$CPUID/smp_affinity`

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 performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"

for file in /proc/irq/*/smp_affinity; do
    var=0x$(cat "$file")
    var=$((var & 0xfdf))
    var=`printf "%x" $var`
    sudo sh -c "echo $var > $file" 2> /dev/null
done
sudo sh -c "echo $MASK > /proc/irq/$CPUID/smp_affinity"

# Load the module and run the client
make unload
make load
python3 scripts/statisic_plot.py -cpu=$CPUID
gnuplot -e "filename='scripts/data.txt'" scripts/draw.gp
make unload

# Restore original settings
sudo sh -c "echo $ORIG_ASLR > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo $ORIG_IRQ > /proc/irq/$CPUID/smp_affinity"

最後使用 taskset -c 5 ./client 指定 client 使用 cpu 5 進行費氏數計算

去除極端值

參考時間測量與效能分析

計算 50 次費氏數的平均，並將離散值做處理，用以得到較平滑的效能比較圖
去除的 outlier 以超過兩個標準差為條件，移除離 50 次平均值太遠的數據

commit 4b6a40c

以常態分佈曲線來看，當我們排除兩個標準以外的數據後，代表此統計手法是在 95% 之信賴區間內取樣平均

def outlier_filter(datas, threshold = 2):
    datas = np.array(datas)
    z = np.abs((datas - datas.mean()) / datas.std())
    return datas[z < threshold]


def data_processing(data_set, n):
    catgories = data_set[0].shape[0]
    samples = data_set[0].shape[1]
    final = np.zeros((catgories, samples))

    for c in range(catgories):        
        for s in range(1, samples):
            final[c][0] = data_set[0][c][0]
            final[c][s] =                                                    \
                outlier_filter([data_set[i][c][s] for i in range(n)]).mean()
            
    return final

TODO: 紀錄閱讀作業說明中所有的疑惑

閱讀 fibdrv 作業規範，包含「作業說明錄影」和「Code Review 錄影」，本著「誠實面對自己」的心態，在本頁紀錄所有的疑惑，並與授課教師預約討論。

過程中，彙整 Homework3 學員的成果，挑選至少三份開發紀錄，提出值得借鏡之處，並重現相關實驗。

Todo: 嘗試使用 mlock 改善 page fault 的情況
2020 - KYG-yaya573142
Todo: 嘗試使用 sysfs
willwillhi1

TODO: 回覆「自我檢查清單」

回答「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳

研讀上述 Linux 效能分析的提示描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
$\to$ 從中也該理解為何不希望在虛擬機器中進行實驗
- 虛擬機技術通常使用虛擬化層來模擬硬體資源，這個虛擬化層介於實際硬體和作業系統之間，可能會引入效能上的延遲或不準確的測量結果。
- 虛擬環境中可能有多個虛擬機共享同一個實際硬體資源，意味著資源分配可能會導致效能變異性。
- 虛擬機中的時間處理不同於實際硬體。虛擬機軟體必須模擬時間的流逝，並為虛擬機中的作業系統和應用程式提供時間服務。
研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
複習 C 語言數值系統和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本
學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
$\to$ 搭配閱讀〈並行和多執行緒程式設計〉

觀察 Linux 核心模組中的 mutex

fibdrv 中的 mutex 使用在 open 和 release 的部份，也就是一次只允許一個 thread 能夠存取 character device

static int fib_open(struct inode *inode, struct file *file)
{
    if (!mutex_trylock(&fib_mutex)) {
        printk(KERN_ALERT "fibdrv is in use");
        return -EBUSY;
    }
    return 0;
}

static int fib_release(struct inode *inode, struct file *file)
{
    mutex_unlock(&fib_mutex);
    return 0;
}

現在嘗試將 mutex lock 移除

static int fib_open(struct inode *inode, struct file *file)
{
    /*
    if (!mutex_trylock(&fib_mutex)) {
        printk(KERN_ALERT "fibdrv is in use");
        return -EBUSY;
    }
    */
    return 0;
}

static int fib_release(struct inode *inode, struct file *file)
{
    //mutex_unlock(&fib_mutex);
    return 0;
}

撰寫簡單的 POSIX thread 程式來測試
例如：thread-1 和 thread-2 都同時打開 fibdrc device，讀取 fib(0) ~ fib(49)，並且為了使用延遲讓兩個 thread 交替執行，營造 race condition 的情況

static int fd;

void *job(void* arg){
    char buf[100];
    int id = *((int *) arg);
    for (int i = 0; i <= 50; i++) {
        lseek(fd, i, SEEK_SET);
        sleep(id);
        read(fd, buf, 0);
        printf("thread %d read fib(%d): %s\n", id, i, buf);
    }
}

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

    pthread_t test[2];
    int pid1 = 1;
    pthread_create(&test[0], NULL, job, (void *), &pid1);
    int pid2 = 2;
    pthread_create(&test[1], NULL, job, (void *), &pid2);
    for(int i = 0; i < 2; i++)
        pthread_join(test[i], NULL);

    close(fd);
    return 0;
}

這邊可以看到前幾項發生錯誤了，thread-2 讀取 fib(2) 的值為 2，說明在 thread-2 設定好的 offest 並將要透過 read() 進入 kernel space 讀取之前，file offset 被 thread-1 更動過了，造成錯誤結果

thread 1 read fib(0): 0
thread 2 read fib(0): 1
thread 1 read fib(1): 1
thread 1 read fib(2): 1
thread 2 read fib(1): 2    <-------
thread 1 read fib(3): 1
thread 1 read fib(4): 3
thread 2 read fib(2): 5
thread 1 read fib(5): 2
thread 1 read fib(6): 8

因此我們需要在 device 被 open() 時將 mutex 上鎖，而 release() 時將 mutex 解鎖，保持同時只有一個 thread 能夠控制 device driver

TODO: 以 sysprog21/bignum 為範本，實作有效的大數運算

理解其中的技巧並導入到 fibdrv 中，並留意以下:

在 Linux 核心模組中，可用 ktime 系列的 API;
在 userspace 可用 clock_gettime 相關 API;
善用統計模型，除去極端數值，過程中應詳述你的手法
分別用 gnuplot 製圖，分析 Fibonacci 數列在核心計算和傳遞到 userspace 的時間開銷，單位需要用 us 或 ns (自行斟酌)

嘗試引入 sysprog21/bignum 程式碼，使 fib 核心模組可以計算 93 以後的數值

commit 4105efe
Todo: 分析細部的程式實作方法，並思考能否加速
參考 bakudr18

typedef struct {
    uint64_t *digits;  /* Digits of number. */
    uint32_t size;     /* Length of number. */
    uint32_t alloc;    /* Size of allocation. */
    unsigned sign : 1; /* Sign bit. */
}

CASE 1:
- $d i g i t s [0] = 2$
- $d i g i t s [1] = 1$
- bignum =
  $1 * 2^{64^{1}} + 2 * 2^{64^{0}}$
CASE 2:
- $d i g i t s [0] = 3$
- $d i g i t s [1] = 2$
- $d i g i t s [2] = 1$
- bignum =
  $1 * 2^{64^{2}} + 2 * 2^{64^{1}} + 3 * 2^{64^{0}}$

大數運算之 fast doubling

    bn *a1 = fib; /* Use output param fib as a1 */

    bn_t a0, tmp, a;
    bn_init_u32(a0, 0); /*  a0 = 0 */
    bn_set_u32(a1, 1);  /*  a1 = 1 */
    bn_init(tmp);       /* tmp = 0 */
    bn_init(a);

    /* Start at second-highest bit set. */
    for (uint64_t k = ((uint64_t) 1) << (62 - __builtin_clzll(n)); k; k >>= 1) {
        /* Both ways use two squares, two adds, one multipy and one shift. */
        bn_lshift(a0, 1, a); /* a03 = a0 * 2 */
        bn_add(a, a1, a);    /*   ... + a1 */
        bn_sqr(a1, tmp);     /* tmp = a1^2 */
        bn_sqr(a0, a0);      /* a0 = a0 * a0 */
        bn_add(a0, tmp, a0); /*  ... + a1 * a1 */
        bn_mul(a1, a, a1);   /*  a1 = a1 * a */
        if (k & n) {
            bn_swap(a1, a0);    /*  a1 <-> a0 */
            bn_add(a0, a1, a1); /*  a1 += a0 */
        }
    }
    /* Now a1 (alias of output parameter fib) = F[n] */

修改 verify.py 使 python 腳本可透過參數更動測試的項數大小

# FILE: verify.py

parser = argparse.ArgumentParser()
parser.add_argument('-k', '--max_k', type=int, default=500)
args = parser.parse_args()
verify_fib(args.max_k)

修改 client.c

int offset = MAX_FIB_K;

在編譯 client 時添加 -D flag 用作條件編譯

client: client.c
    $(CC) -o $@ $^ -DMAX_FIB_K=$(FIB_K)

執行

$ make check FIB_K=5000

得到輸出

make load
make[1]: Entering directory '/home/pengpaul/linux2023/fibdrv'
sudo insmod fibdrv_new.ko
make[1]: Leaving directory '/home/pengpaul/linux2023/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/pengpaul/linux2023/fibdrv'
sudo rmmod fibdrv_new || true >/dev/null
make[1]: Leaving directory '/home/pengpaul/linux2023/fibdrv'
 Passed [-]

確認在

f i b (5000)

以前其演算法的正確性

實作大數運算後的效能比較

使用者模式時間同步

因為要測量運算完成後，把資料從核心搬到使用者模式，及使用者模式收到資料的時間。故在使用者模式取得到時間要能跟核心模式進行對應。

在使用者模式可以用 clock_gettime 函式來取得時間，其中又有不同的 clock id 。跟據 Linux 核心 ktime API 文件，在 Linux 核心內，以 ktime_get 函式所取得的時間可以對應到 CLOCK_MONOTONIC 的時間。

探討 clock_gettime 造成 page fault 的原因

struct timespec {
   time_t   tv_sec;        /* seconds */
   long     tv_nsec;       /* nanoseconds */
};

從 clock_gettime 取得的時間結構定義如上，我們可以簡單的將 tv_sec *

10^{9}

來換算成與 ktime 對應的 nanoseconds

struct timespec start, end;

clock_gettime(CLOCK_MONOTONIC, &start);
long long sz = read(fd, buf, sizeof(buf));
clock_gettime(CLOCK_MONOTONIC, &end);
long long ut = (long long) (end.tv_sec - start.tv_sec) * \
                1e9 + (end.tv_nsec - start.tv_nsec);

通過 user time - kernel time 可以得出 copy_to_user system call 的花費時間

依據 Hierarchical performance measurement and modeling of the Linux file system 研究指出，從核心模式複製資料到使用者層級的時間成本是，每個位元組達 22ns。也就是當數字越大，需傳遞的字串越長，時間花費就越多

如圖所示，隨著 n 增加，system call 開銷明顯可見地大幅增加

當把 n 設到 500 時程式執行的效率越來越差

有產生階梯圖的狀況，每次階梯的產生剛好發生在
$f i b (n)$ 的數值超過一個 uint64_t 可表示的大小時，與 paul90317 同學遇到相似的結果，但原因可能有待釐清

在作業三說明中，老師有給出三種提升效能的方法

儘量降低由核心傳遞到應用程式的資料量
確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
Integer Encoding Algorithm 技巧

針對第一種降低資料傳遞量的做法，可以將 bn 結構體先回傳到 user space，再去做 bn_to_str 的操作

char *bn_to_str(const unsigned long long *digits, size_t size)
{
    size_t str_size = (size_t) (size * DIGIT_BITS) / 3 + 1;

    if (size == 0) {
        char *str = malloc(2);
        str[0] = '0';
        str[1] = '\0';
        return str;
    } else {
        char *s = malloc(str_size);
        char *p = s;

        memset(s, '0', str_size - 1);
        s[str_size - 1] = '\0';

        /* n.digits[0] contains least significant bits */
        for (int i = size - 1; i >= 0; i--) {
            /* walk through every bit of bn */
            for (unsigned long long d = 1ULL << 63; d; d >>= 1) {
                /* binary -> decimal string */
                int carry = !!(d & digits[i]);
                for (int j = str_size - 2; j >= 0; j--) {
                    s[j] += s[j] - '0' + carry;
                    carry = (s[j] > '9');
                    if (carry)
                        s[j] -= 10;
                }
            }
        }
        // skip leading zero
        while (p[0] == '0' && p[1] != '\0') {
            p++;
        }
        memmove(s, p, strlen(p) + 1);
        return s;
    }
}

Todo: 減少 bn_to_str() 迴圈和分支的使用情況

實驗證明，copy_to_user 複製 bn 結構體比複製字串還來的節省時間
system call overhead 維持在 1000 ns 左右，比複製字串的 2000 ns 好上許多

TODO: 實作更快速的乘法運算

參照 Schönhage–Strassen algorithm，在上述大數運算的程式碼基礎之上，改進乘法運算，確保在大多數的案例均可加速，需要有對應的驗證機制。