Try   HackMD

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,且兔子不死亡

an+1=an+bn
bn+1=an

一般遞迴

an+1=an1+an,n1
a0=0,a1=1

矩陣運算 Q-matrix

[an+1bn+1]=[1110][anbn]

又可改寫成

[an+1an]=[1110][anan1]

[an+1ananan1]=[1110]n

Fast Doubling

F(0)=a0=0
F(1)=a1=1

[F(2n+1)F(2n)]=[1110]2n[F(1)F(0)]=[1110]n[1110]n[F(1)F(0)]=[F(n+1)F(n)F(n)F(n1)][F(n+1)F(n)F(n)F(n1)][10]=[F(n+1)2+F(n)2F(n)F(n+1)+F(n1)F(n)]

其中

F(n1)=F(n+1)F(n)

最後得到

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

Fast Doubling

F(2k)=F(k)[2F(k+1)F(k)]
F(2k+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(logn)
內,這可以大幅減少重複的計算

參考: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(logn)
    次遞迴
  • 總共時間複雜度為
    O(1)O(logn)=O(logn)

解釋 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 的解釋

  1. High resolution timers and dynamic ticks design notes
  2. 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) 不大於

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

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

  1. 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.
  2. 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.
  3. 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.hktime_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 中順序呼叫 readwrite,即可取得所花費的 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 給效能測試使用

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

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

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

觀察 Linux 核心模組中的 mutex

fibdrv 中的 mutex 使用在 openrelease 的部份,也就是一次只允許一個 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-1thread-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:

    • digits[0]=2
    • digits[1]=1
    • bignum =
      12641+22640
  • CASE 2:

    • digits[0]=3
    • digits[1]=2
    • digits[2]=1
    • bignum =
      12642+22641+32640

大數運算之 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 [-]

確認在

fib(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 *

109 來換算成與 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 時程式執行的效率越來越差

有產生階梯圖的狀況,每次階梯的產生剛好發生在

fib(n) 的數值超過一個 uint64_t 可表示的大小時,與 paul90317 同學遇到相似的結果,但原因可能有待釐清

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

  1. 儘量降低由核心傳遞到應用程式的資料量
  2. 確保應用程式不需要過多的計算量才可重現 Fibonacci 數列
  3. 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,在上述大數運算的程式碼基礎之上,改進乘法運算,確保在大多數的案例均可加速,需要有對應的驗證機制。