2022q1 Homework3 (fibdrv)

contributed by < hsuedw >

• 作業繳交
• 作業需求
• Due Date: Mar 21, 2022

---

預備知識

• Linux 核心模組運作原理

工作環境

• 作業系統
  • Ubuntu 20.04.4 LTS (Focal Fossa)
  • Linux kernel: 5.13.0-30-generic
  details

  ​​​​$ uname -a
  ​​​​Linux edward-ubuntu 5.13.0-30-generic #33~20.04.1-Ubuntu SMP Mon Feb 7 14:25:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
  

• 硬體資源
  • CPU: Intel® Core™ i5-7400 CPU @ 3.00GHz, 4 cores
    CPU details

    ​​​​​​$ 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):                          4
    ​​​​​​On-line CPU(s) list:             0-3
    ​​​​​​Thread(s) per core:              1
    ​​​​​​Core(s) per socket:              4
    ​​​​​​Socket(s):                       1
    ​​​​​​NUMA node(s):                    1
    ​​​​​​Vendor ID:                       GenuineIntel
    ​​​​​​CPU family:                      6
    ​​​​​​Model:                           158
    ​​​​​​Model name:                      Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz
    ​​​​​​Stepping:                        9
    ​​​​​​CPU MHz:                         3000.000
    ​​​​​​CPU max MHz:                     3500.0000
    ​​​​​​CPU min MHz:                     800.0000
    ​​​​​​BogoMIPS:                        6000.00
    ​​​​​​Virtualization:                  VT-x
    ​​​​​​L1d cache:                       128 KiB
    ​​​​​​L1i cache:                       128 KiB
    ​​​​​​L2 cache:                        1 MiB
    ​​​​​​L3 cache:                        6 MiB
    ​​​​​​NUMA node0 CPU(s):               0-3
    

  • RAM: 8 GB
• 編譯器
  ​​ $ gcc --version
  ​​ gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
  

---

Fix VLA not allowed in kernel issue

編譯 fibdrv 時，發現下列警告訊息。雖然 fibdrv 仍可安裝並計算 Fibonacci number。不過，既然 Linux kernel 不允許使用 variable length array (VLA)，那就把先把這個警告訊息處理掉。
目前採用的解法是用動態規劃 (Dynamic Programming) 裡的狀態壓縮技巧處理。原本的 fib_sequence() 裡有個 f 陣列，用來計算 f[k]。這樣做的時間與空間複雜度都是 O(k)。不過，仔細想想，以 buttom-up DP 實作的演算法只需要 f[k - 1] 與 f[k - 2] 就可以計算出 f[k]。所以不需要一個長度為 k 的陣列。所以改用下列實作，既可避開禁止使用 VLA 的警告訊息，又可降低空間複雜度到 O(1)。

Fix VLA not allowed in kernel issue (commit: dd77cd1)

static long long fib_sequence(long long k)
{
    if (k < 2)
        return k;

    long long fk = -1, fk_2 = 0, fk_1 = 1;
    for (int i = 2; i <= k; i++) {
        fk = fk_2 + fk_1;
        fk_2 = fk_1;
        fk_1 = fk;
    }

    return fk;
}

使用 sysfs 介面

fibdrv 遇到的第一個要解決的問題就是因為 C 語言內建的 long long 資料型態所能表示的最大值為 2⁶³ - 1 = ‭9,223,372,036,854,775,807‬。導致在計算 F₉₃ 出現溢位 (overflow)。

F₉₃ = 15080227609492692858

就算是改用 unsigned long long 最大值也只能是 2⁶⁴ - 1 = ‭18,446,744,073,709,551,615‬。勉強可以用來計算 F₉₃。但是作業的要求是至少要計算到 F₁₀₀，甚至是更後面的 Fibonacci number。所以必須要使用自訂資料型態實作 big number。不過，若是以目前 fibdrv 所採用的 VFS，實作 open、close、read、write 等 system call 的方式將 fibdrv 計算出來的 Fibonacci number (用自訂資料型態實作 big number 表示) 困擾。在用 VFS 的實作前提下，可能的解決方案有兩種。

1. 使用 ioctl 這個 system call。這樣可以一次把自訂 big number 型態的 object 讀到 user space 中。不過，這樣做的話， fibdrv 必須向 client 揭露 big number 資料型態定義與其他相關實作細節。
2. 按照目前 client 所提示的實作方式，用 lseek 與 read 兩個 system call 搭配操作。先用 lseek 設定準備要讀取的資料的位置，再用 read 把指定的資料讀出來。一次讀一個 long long 的資料，直到把自訂 big number 資料結構中記錄 Fibonacci number 的所有 long long 讀完為止。

這兩種做法對 client 而言，都不是很友善。因為 client 必須重組資料才能得到完整的 Fibonacci number。而且必須揭露許多 fibdrv 的實作細節給 client。會加深 fibdrv 與 client 間 coupling 的程度。

Coupling (computer programming)

比較好的做法應該是 client 能夠直接讀到計算完成的 Fibonacci number。並且不要揭露任何關於 fibdrv 內部的實作細節給 client。所以我打算使用 sysfs 介面。

目前打算在 sysfs 下產生三個檔案。藉以向 client 揭露 fibdrv 的計算結果。

1. /sys/kernel/fibonacci/input: client 在此檔案中寫入想要計算的 Fibonacci number 的項數。例如，寫入 10 表示想要計算 F₁₀。
2. /sys/kernel/fibonacci/output: fibdrv 計算的 Fibonacci number。例如，F₁₀ = 55。
3. /sys/kernel/fibonacci/time: fibdrv 計算 Fibonacci number 所花費的時間。

測試目前實作的 sysfs interface (commit: 6d04220)

$ make clean all
make -C /lib/modules/5.13.0-30-generic/build M=/home/edward/workspace/linux_2022/homework3/fibdrv clean
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic'
  CLEAN   /home/edward/workspace/linux_2022/homework3/fibdrv/Module.symvers
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic'
rm -f client out
cc -o client client.c
make -C /lib/modules/5.13.0-30-generic/build M=/home/edward/workspace/linux_2022/homework3/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic'
  CC [M]  /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.o
  MODPOST /home/edward/workspace/linux_2022/homework3/fibdrv/Module.symvers
  CC [M]  /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.mod.o
  LD [M]  /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko
  BTF [M] /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko
Skipping BTF generation for /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko due to unavailability of vmlinux
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic'
$
$ sudo insmod fibdrv.ko
$
$ lsmod | grep fibdrv
fibdrv                 16384  0
$
$ sudo su
[sudo] password for edward:
#
# whoami
root
#
# cat /sys/kernel/fibonacci/input
0
#
# cat /sys/kernel/fibonacci/output
0
#
# echo 10 > /sys/kernel/fibonacci/input
#
# cat /sys/kernel/fibonacci/input
10
#
# cat /sys/kernel/fibonacci/output
55
#
# echo 92 > /sys/kernel/fibonacci/input
# cat /sys/kernel/fibonacci/input
92
#
# cat /sys/kernel/fibonacci/output
7540113804746346429

• 參考資料:
  Brief sysfs Tutorial
  Documentation/filesystems/sysfs.rst
  Sample kobject implementation (注意: 切換到對應的 Linux 核心版本)

---

實作 big number

• 本階段目標

  • 實作 big number 資料結構。
  • 實作 big number 加法運算。使 fibdrv 可用原本的迭代演算計算 Fibonacci number (F₉₂ 以上)。
  • 實作 big number 轉字串。在字串中以十六進位表示 Fibonacci number。
  • 為 Fast Doubling 計算 Fibonacci number 做準備。
    • 實作 big number bitwise left shift
    • 實作 big number 減法運算。
    • 實作 big number 乘法運算。

• big number 資料結構

  ​​/*
  ​​ * bignum data structure
  ​​ * number[0] contains least significant bits
  ​​ * number[size - 1] contains most significant bits
  ​​ * sign = 1 for negative number
  ​​ */
  ​​typedef struct _bignum {
  ​​    NUM_TYPE *num;
  ​​    size_t sz;
  ​​    int sign;
  ​​} bignum;
  

  • 目前只有用到 num 與 sz 兩個欄位。
  • num 是指向一個 kmalloc() 動態宣告的記憶體空間。其大小為 BIGNUM_SZ * sizeof(NUM_TYPE)。目前 BIGNUM_SZ 設定為 500。NUM_TYPE 定義為 uint32_t。以目前這樣的實作可以算到 F₂₃₀₀₀。

• big number 加法運算

  ​​// s = a + b
  ​​void bignum_add(bignum *s, const bignum *a, const bignum *b)
  ​​{
  ​​    memset(s->num, 0, s->sz * sizeof(NUM_TYPE));
  
  ​​    int carry = 0;
  ​​    for (int i = 0; i < s->sz; ++i) {
  ​​        TMP_TYPE tmp = (TMP_TYPE) a->num[i] + b->num[i] + carry;
  ​​        carry = tmp > MAX_VAL;
  ​​        s->num[i] = tmp & MAX_VAL;
  ​​    }
  
  ​​    return;
  ​​}
  

  • TMP_TYPE 被定義為 uint64_t。NUM_TYPE 被定義為 uint32_t。而 a->num[i] 的型態為 NUM_TYPE 也就是 uint32_t。
  • 所以，在第 8 行執行加法運算時，被加數 (a->num[i]) 與加數 (b->num[i]) 均被轉型為 uint64_t。然後在第 9 行判斷變數 tmp 是否大於 uint32_t 所能表示的最大值決定是否有發生進位。

• big number 轉字串。在字串中以十六進位表示 Fibonacci number

  ​​ssize_t bignum_to_string(bignum *bn, char *buf)
  ​​{
  ​​    ssize_t s_len = BIGNUM_SZ * sizeof(NUM_TYPE) * 2 + 1;
  ​​    ssize_t j = 0, blk_sz = sizeof(NUM_TYPE) * 2 + 1;
  ​​    char *s = (char *) kmalloc(s_len, GFP_KERNEL);
  
  ​​    for (int i = bn->sz - 1; i >= 0; --i)
  ​​        j += snprintf(s + j, blk_sz, "%08X", bn->num[i]);
  ​​    j = snprintf(buf, s_len + 1, "%s\n", s);
  ​​    kfree(s);
  
  ​​    return j;
  ​​}
  

  • 目前這個將 big number 轉為字串的實作是以十六進位顯示。因為 big number 是以二進位的想法在實作運算。這樣可以省去轉換為十進位的運算成本。
  • 這個 big number 轉為字串的實作沒有去掉 leading zeros。應該稍後會回來實作這部分。

• big number bitwise left shift

  ​​// bn = bn << shift
  ​​void bignum_lshift(bignum *bn, size_t shift)
  ​​{
  ​​    shift %= 32;  // only handle shift within 32 bits atm
  ​​    if (!shift)
  ​​        return;
  
  ​​    for (int i = bn->sz - 1; i > 0; i--)
  ​​        bn->num[i] = bn->num[i] << shift | bn->num[i - 1] >> (32 - shift);
  ​​    bn->num[0] <<= shift;
  ​​}
  

  • big number 的 bitwise left shift 運算是為了 fast doubling 演算法做準備。因為在計算 F(2k) 時，需要對 F(k+1) 乘 2。
  • 對數字左移一個 bit，相當於對此數字執行乘 2 運算。

• big number 減法運算

  ​​// d = a - b
  ​​void bignum_sub(bignum *d, const bignum *a, const bignum *b)
  ​​{
  ​​    memset(d->num, 0, d->sz * sizeof(NUM_TYPE));
  
  ​​    bignum *tmp = bignum_create(BIGNUM_SZ);
  ​​    bignum_cpy(tmp, b);
  
  ​​    // Calculate the two's complement for b.
  ​​    tmp->num[0] = ~tmp->num[0];
  ​​    int carry = ((TMP_TYPE) tmp->num[0] + 1) > MAX_VAL;
  ​​    tmp->num[0] += 1;
  ​​    for (int i = 1; i < tmp->sz; ++i) {
  ​​        tmp->num[i] = ~tmp->num[i];
  ​​        carry = ((TMP_TYPE) tmp->num[i] + carry) > MAX_VAL;
  ​​        tmp->num[i] += carry;
  ​​    }
  
  ​​    // d = a - b = a + b(two's complement)
  ​​    bignum_add(d, a, tmp);
  ​​}
  

  • big number 的減法運算基本上就是先對減數取其二補數 (two's complement)。然後再利用 big number 加法運算將被減數與被減數二補數相加。

• big number 乘法運算

  ​​static void bn_mult_add(bignum *p, int offset, TMP_TYPE x)
  ​​{
  ​​    TMP_TYPE carry = 0;
  ​​    for (int i = offset; i < p->sz; ++i) {
  ​​        carry += p->num[i] + (x & MAX_VAL);
  ​​        p->num[i] = carry;
  ​​        carry >>= 32;
  ​​        x >>= 32;
  ​​        if (!x && !carry)
  ​​            return;
  ​​    }
  ​​}
  
  ​​// p = a * b
  ​​void bignum_mult(bignum *p, const bignum *a, const bignum *b)
  ​​{
  ​​    memset(p->num, 0, p->sz * sizeof(NUM_TYPE));
  ​​    for (int i = 0; i < a->sz; ++i)
  ​​        for (int j = 0; j < b->sz; ++j) {
  ​​            TMP_TYPE carry = (TMP_TYPE) a->num[i] * b->num[j];
  ​​            bn_mult_add(p, i + j, carry);
  ​​        }
  ​​}
  

• Debug tools:

  • fibonacci number generator
  • Decimal to Hexadecimal converter
  • Online Big Number Calculator
  • Hexadecimal to Decimal converter

• 參考實作:

  • KYG-yaya573142
  • sysprog21
  • bignum.c
  • kokke

---

實作時間量測

在 fibdrv.c 中使用 ktime 量測每次計算 Fibonacci number 所花費的時間。單位是 nano second。我把實作 fast doubling (fib_fast_doubling()) 與 iteration (fib_sequence()) 的函式原型設計得一樣，然後利用函式指標 (function pointer) 依據不同的需求將不同的演算法送入 fib_time_cost() 中。

static void fib_time_cost(void (*fib_algo)(NUM_TYPE), NUM_TYPE k)
{
    kt = ktime_get();
    fib_algo(k);
    kt = ktime_sub(ktime_get(), kt);
}

在 client.c 中使用 clock_gettime() 量測讀取 Fibonacci number 所需花費的時間。單位是 nano second。

               :
        struct timespec t1, t2;
        size_t rd_len, out_len = 0;
        // Read a Fibonacci number from linux kernel.
        // The output of the Fibonacci driver is a hexdecimal number.
        char fib_output[FIB_OUTPUT_LEN];
        int fd_out = open(FIB_OUTPUT, O_RDONLY);
        clock_gettime(CLOCK_MONOTONIC, &t1);
        while (rd_len = read(fd_out, fib_output + out_len,
                             FIB_OUTPUT_LEN - out_len)) {
            out_len += rd_len;
        }
        clock_gettime(CLOCK_MONOTONIC, &t2);
        fib_output[FIB_OUTPUT_LEN - 1] = '\0';
        close(fd_out);

                  :
  
        // Record the time for reading a Fibonacci number.
        uint64_t rd_time = (uint64_t)((t2.tv_sec * 1e9 + t2.tv_nsec) -
                                      (t1.tv_sec * 1e9 + t1.tv_nsec));
        snprintf(tmp_buf, TMP_BUF_LEN, "%d %lu\n", k, rd_time);
        int fd_rd_time = open(rd_time_file, O_CREAT | O_APPEND | O_WRONLY,
                              S_IRUSR | S_IRGRP | S_IROTH);
        write(fd_rd_time, tmp_buf, strlen(tmp_buf));
        close(fd_rd_time);

---

簡化實驗流程

這個階段的目標是要透過下列方法簡化實驗流程。

• 在 sysfs 中新增 /sys/kernel/fibonacci/algo。利用它來動態調整計算 Fibonacci number 的演算法。
  • 在 fibdrv.c 中，實作 iteration 與 fast doubling 的函式原型如下所示:
    ​​​​​​static void fib_fast_doubling(NUM_TYPE k);
    ​​​​​​static void fib_sequence(NUM_TYPE k);
    

  • 定義函式指標 fib_algo 動態指向上述兩個函式中的一個。fib_algo 預設指向 fib_fast_doubling。
    ​​​​​​static void (*fib_algo)(NUM_TYPE);
    

  • 對 /sys/kernel/fibonacci/algo 分別寫入 "iteration" 與 "fast-doubling" 就可以控制計算 Fibonacci number 的演算法。
    ​​​​​​static ssize_t fib_algo_store(struct kobject *kobj,
    ​​​​​​                              struct kobj_attribute *attr,
    ​​​​​​                              const char *buf,
    ​​​​​​                              size_t count)
    ​​​​​​{
    ​​​​​​    if (strncmp(buf, "iteration", 9) == 0) {
    ​​​​​​        /* Set the algorithm to be iteration. */
    ​​​​​​        pr_info("%s: Set the algorithm to be iteration.\n", KBUILD_MODNAME);
    ​​​​​​        fib_algo = fib_sequence;
    ​​​​​​    } else if (strncmp(buf, "fast-doubling", 13) == 0) {
    ​​​​​​        /* Set the algorithm to be fast-doubling. */
    ​​​​​​        pr_info("%s: Set the algorithm to be fast-doubling.\n", KBUILD_MODNAME);
    ​​​​​​        fib_algo = fib_fast_doubling;
    ​​​​​​    } else {
    ​​​​​​        pr_info("%s: %s is not support.\n", KBUILD_MODNAME, buf);
    ​​​​​​        pr_info("%s: Set the algorithm to be fast-doubling.\n", KBUILD_MODNAME);
    ​​​​​​        fib_algo = fib_fast_doubling;
    ​​​​​​    }
    ​​​​​​    return strlen(buf);
    ​​​​​​}
    
    

---

為效能分析設定實驗環境

將行程固定在特定的 CPU 中執行

執行 taskset 並使用 -cp 參數再加上 process ID 查看指定行程的處理器親和性(CPU affinity)。已執行結果看來，我可以使用 CPU 0~3。

$ taskset -cp 1
pid 1's current affinity list: 0-3

接下來使用 boot loader 所提供的自訂開機參數功能，手動加入 isolcpus=cpu_id 參數。讓特定的 CPU 核心在開機時就被保留下來，不讓其他的行程干擾我要執行的程式。我先保留 CPU 0。首先切換目錄到 /etc/default，然後備份 grub。

$ cd /etc/default
$ sudo cp grub grub-org

然後修改 /etc/default/grub 中的 GRUB_CMDLINE_LINUX_DEFAULT 參數。在此參數後加上 isolcpus=0 也就是保留 CPU 0 給特定程式使用。

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0"

執行下列指令更新 boot loader 的開機參數。

$ sudo update-grub

Sourcing file `/etc/default/grub'
Sourcing file `/etc/default/grub.d/init-select.cfg'
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-5.13.0-35-generic
Found initrd image: /boot/initrd.img-5.13.0-35-generic
Found linux image: /boot/vmlinuz-5.13.0-30-generic
Found initrd image: /boot/initrd.img-5.13.0-30-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
done

先檢查 /sys/devices/system/cpu/isolated 的內容，應該要是空的。

$ cat /sys/devices/system/cpu/isolated

然後，重新開機。

$ sudo reboot

待重新開機完成後，在檢查 /sys/devices/system/cpu/isolated 的內容。應該要是 0。也就是我剛剛在 /etc/default/grub 中用 isolcpus=0 保留下來的 CPU。

$ cat /sys/devices/system/cpu/isolated
0

接著就可以用 taskset 指定 CPU 來執行程式。在這個作業中，執行 client 並透過 sysfs 介面操作 fibdrv 計算 Fibonacci numbers。

# taskset -c 0 ./client $PWD fd_fib.time fd_rd.time

將這個動作整合到 Makefile 中。以簡化後續的實作流程。以下是在 Makefile 中新增的兩個 rule。

it_time: client
        # This rule must be run as root
        echo "iteration" > /sys/kernel/fibonacci/algo
        # Bind the executable to CPU 0.
        taskset -c 0 ./client $(PWD) it_fib.time it_rd.time

fd_time: client
        # This rule must be run as root
        echo "fast-doubling" > /sys/kernel/fibonacci/algo
        # Bind the executable to CPU 0.
        taskset -c 0 ./client $(PWD) fd_fib.time fd_rd.time

排除干擾效能分析的因素

• 暫時抑制 address space layout randomization (ASLR)

  ​​$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
  

• 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 performance.sh:

  ​​for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
  ​​do
  ​​    echo performance > ${i}
  ​​done
  

  然後再用下列執行 performance.sh。

  ​​$ sudo sh performance.sh
  

• 針對 Intel 處理器，關閉 turbo mode

  ​​$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
  

• 將上述這些排除干擾效能分析的因素的動作全部整合進 Makefile 以簡化後續實驗流程。

  ​​set_env:
  ​​        # This rule must be run as root
  ​​        # Suppress address space layout randomization (ASLR)
  ​​        sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
  ​​        sudo sh performance.sh
  ​​        # For Intel CPU, disable turbo mode
  ​​        sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
  

• 參考資料: 排除干擾效能分析的因素

---

效能分析(內建資料型別)

初步觀察

以下列這個 commit 的程式碼搭配本文一開始所描述的環境做實驗。

commit: ab44371
branch: perf.built-in-type

fast doubling

static long long fib_fast_doubling_org(long long n)
{
    if (n <= 1) {
        // base case:
        //   F(0) = 0
        //   F(1) = 1

        // Performanc measure strat.
        kt = ktime_get();

        int ret = n;

        // Performanc measure stop.
        kt = ktime_sub(ktime_get(), kt);

        return ret;
    }

    // Performanc measure strat.
    kt = ktime_get();

    long long a = 0, b = 1;
    unsigned int mask_len = sizeof(unsigned int) * 8 - 1;

    for (unsigned int k = 1U << mask_len; k; k >>= 1) {
        long long k1 = a * (2 * b - a);  // F(2k) = F(k)[2F(k+1) - F(k)]
        long long k2 = a * a + b * b;    // F(2k+1) = F(k)^2 + F(k+1)^2
        if (n & k) {
            a = k2;       // F(2k+1)
            b = k1 + k2;  // F(2k+2)
        } else {
            a = k1;  // F(2k)
            b = k2;  // F(2k+1)
        }
    }

    // Performanc measure stop.
    kt = ktime_sub(ktime_get(), kt);

    return a;
}

執行下列指令畫出 iteration 與 fast doubling 的效能比較。

$ make clean plot_clean all
$ make unload load
$ sudo su
$ make plot

結果會畫在 fibdrv_perf.png 中。

Iteration 演算法的時間複雜度為 O(n)，fast doubling 演算法的時間複雜度為 O(logn)。由上圖的實驗結果可看出這個趨勢。

設法改善 fast doubling 的效能

由作業說明 (H03: fibdrv, 費氏數列) 中的虛擬碼與示範案例，以及Calculating Fibonacci Numbers by Fast Doubling 的說明可窺見，以 fast doubling 計算 Fibonacci number 可對所欲求取的項數的二進位表示法決定計算步驟。所以可以利用 gcc 提供的 __builtin_clz() 減少尋找 MSB (most significant bit) 的時間。

commit: ab44371
branch: perf.built-in-type

fast doubling with clz

static long long fib_fast_doubling_clz(long long n)
{
    if (n <= 1) {
        // base case:
        //   F(0) = 0
        //   F(1) = 1

        // Performanc measure strat.
        kt = ktime_get();

        int ret = n;

        // Performanc measure stop.
        kt = ktime_sub(ktime_get(), kt);

        return ret;
    }

    // Performanc measure strat.
    kt = ktime_get();

    long long a = 0, b = 1;
    unsigned int mask_len = sizeof(unsigned int) * 8 - 1 - __builtin_clz(n);

    for (unsigned int k = 1U << mask_len; k; k >>= 1) {
        long long k1 = a * (2 * b - a);  // F(2k) = F(k)[2F(k+1) - F(k)]
        long long k2 = a * a + b * b;    // F(2k+1) = F(k)^2 + F(k+1)^2
        if (n & k) {
            a = k2;       // F(2k+1)
            b = k1 + k2;  // F(2k+2)
        } else {
            a = k1;  // F(2k)
            b = k2;  // F(2k+1)
        }
    }

    // Performanc measure stop.
    kt = ktime_sub(ktime_get(), kt);

    return a;
}

效能分析 (自行實作的 big number)

初步觀察

以下列這個 commit 的程式碼搭配本文一開始所描述的環境做實驗。

commit: 2b8c55a
branch: master

fast doubling (big number)

static void fib_fast_doubling_org(NUM_TYPE k)
{
    if (k <= 1) {
        answer = bignum_create(BIGNUM_SZ);

        // Performanc measure strat.
        kt = ktime_get();

        answer->num[0] = k;

        // Performanc measure stop.
        kt = ktime_sub(ktime_get(), kt);

        return;
    }

    bignum *a = bignum_create(BIGNUM_SZ);
    answer = a;
    bignum *b = bignum_create(BIGNUM_SZ);
    bignum *c = bignum_create(BIGNUM_SZ);
    bignum *d = bignum_create(BIGNUM_SZ);
    bignum *tmp1 = bignum_create(BIGNUM_SZ);
    bignum *tmp2 = bignum_create(BIGNUM_SZ);

    // Performanc measure strat.
    kt = ktime_get();

    unsigned int mask_len = sizeof(unsigned int) * 8 - 1;

    a->num[0] = 0;  // base case, F(0) = 0
    b->num[0] = 1;  // base case, F(1) = 1

    for (unsigned int i = 1U << mask_len; i; i >>= 1) {
        bignum_cpy(tmp1, b);
        bignum_lshift(tmp1, 1);     // tmp1 = 2 * F(k+1)
        bignum_sub(tmp2, tmp1, a);  // tmp2 = 2 * F(k+1) - F(k)
        bignum_mult(c, a, tmp2);    // F(2k) = F(k) * [2 * F(k+1) - F(k)]

        bignum_mult(tmp1, a, a);    // tmp1 = a * a
        bignum_mult(tmp2, b, b);    // tmp2 = b * b
        bignum_add(d, tmp1, tmp2);  // F(2k+1) = F(k) * F(k) + F(k+1) * F(k+1)

        if (k & i) {
            bignum_cpy(a, d);
            bignum_add(b, c, d);
        } else {
            bignum_cpy(a, c);
            bignum_cpy(b, d);
        }
    }

    // Performanc measure stop.
    kt = ktime_sub(ktime_get(), kt);

    bignum_destroy(b);
    bignum_destroy(c);
    bignum_destroy(d);
    bignum_destroy(tmp1);
    bignum_destroy(tmp2);
}

執行下列指令畫出 iteration 與 fast doubling 的效能比較。

$ make clean plot_clean all
$ make unload load
$ sudo su
$ make plot

結果會畫在 fibdrv_perf.png 中。

以 clz 改善以 big number 實作的 fast doubling 效能

commit: 2b8c55a
branch: master

fast doubling (big number) with clz

static void fib_fast_doubling_clz(NUM_TYPE k)
{
    if (k <= 1) {
        answer = bignum_create(BIGNUM_SZ);

        // Performanc measure strat.
        kt = ktime_get();

        answer->num[0] = k;

        // Performanc measure stop.
        kt = ktime_sub(ktime_get(), kt);

        return;
    }

    bignum *a = bignum_create(BIGNUM_SZ);
    answer = a;
    bignum *b = bignum_create(BIGNUM_SZ);
    bignum *c = bignum_create(BIGNUM_SZ);
    bignum *d = bignum_create(BIGNUM_SZ);
    bignum *tmp1 = bignum_create(BIGNUM_SZ);
    bignum *tmp2 = bignum_create(BIGNUM_SZ);

    // Performanc measure strat.
    kt = ktime_get();

    unsigned int mask_len = sizeof(unsigned int) * 8 - 1 - __builtin_clz(k);

    a->num[0] = 0;  // base case, F(0) = 0
    b->num[0] = 1;  // base case, F(1) = 1

    for (unsigned int i = 1U << mask_len; i; i >>= 1) {
        bignum_cpy(tmp1, b);
        bignum_lshift(tmp1, 1);     // tmp1 = 2 * F(k+1)
        bignum_sub(tmp2, tmp1, a);  // tmp2 = 2 * F(k+1) - F(k)
        bignum_mult(c, a, tmp2);    // F(2k) = F(k) * [2 * F(k+1) - F(k)]

        bignum_mult(tmp1, a, a);    // tmp1 = a * a
        bignum_mult(tmp2, b, b);    // tmp2 = b * b
        bignum_add(d, tmp1, tmp2);  // F(2k+1) = F(k) * F(k) + F(k+1) * F(k+1)

        if (k & i) {
            bignum_cpy(a, d);
            bignum_add(b, c, d);
        } else {
            bignum_cpy(a, c);
            bignum_cpy(b, d);
        }
    }

    // Performanc measure stop.
    kt = ktime_sub(ktime_get(), kt);

    bignum_destroy(b);
    bignum_destroy(c);
    bignum_destroy(d);
    bignum_destroy(tmp1);
    bignum_destroy(tmp2);
}

由實驗數據看來，原本的 iteration 演算法隨著項數的增長，所花費的時間以線性關係成長。而 fast doubling 演算法的曲線則是呈現類似對數 (logarithm) 的關係。雖然兩個演算法的時間複雜度與理論吻合，可是fast doubling 所花費的時間卻比 iteration 來的高。以這個趨勢來看，當項數足夠大的時候，iteration 所花費的時間會超越 fast doubling。
不過，已經算到 F₂₃₀₀₀ 了 fast doubling 所花費的時間仍然比 iteration 高。看來我實作的 big numger 還有很大的改善空間。

---

自我檢查清單

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
• lsmod 的輸出結果有一欄名為 Used by，這是 “each module’s use count and a list of referring modules”，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？

搭配閱讀 The Linux driver implementer’s API guide » Driver Basics

• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。