---
tags: linux2022
---

# 2022q1 Homework3 (fibdrv)

contributed by < `SmallHanley` >

> [作業說明](https://hackmd.io/@sysprog/linux2022-fibdrv)
> [GitHub](https://github.com/SmallHanley/fibdrv)

## 開發環境

$ cat /proc/version
Linux version 5.13.0-37-generic (buildd@lcy02-amd64-111)
(gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0, GNU ld (GNU Binutils for Ubuntu) 2.34)
#42~20.04.1-Ubuntu SMP Tue Mar 15 15:44:28 UTC 2022

$ 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-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualisation:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

## fibdrv

file_operations [include/linux/fs.h](https://elixir.bootlin.com/linux/latest/source/include/linux/fs.h#L2069)

==TODO==

## Linux 效能分析的提示

首先，根據不同的算法，畫出折線圖，橫軸是費氏數列第 n 項，縱軸是計算該項所花費的時間：


:::spoiler gnuplot script

set title "Time cost"
set xlabel "n th sequence of Fibonacci number"
set ylabel "time cost (ns)"
set terminal png font " Times_New_Roman,12 "
set output "time.png"
set xrange [0:100]
set xtics 0, 20, 100
set key left

plot \
"time" using 1:2 with linespoints linewidth 2 title "original", \
"time" using 1:3 with linespoints linewidth 2 title "fast-exp", \
"time" using 1:4 with linespoints linewidth 2 title "fast-doubling", \

:::

### 執行多次運算取平均

為了減少誤差，我嘗試將執行 10 次的結果取平均，再重新繪製，執行方式：

$ make plot


### 以特定的 CPU 執行程式

一個在 userspace 的程式，我們可以使用 [taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 命令，將指定的行程透過 PID 和 cpumask 固定在指定的 CPU 上執行，又或是將給定的新的程式或命令固定在指定的 CPU 上執行，用法如下：

taskset [options] [mask | cpu-list] [pid|cmd [args...]]

至於 kernel module，在閱讀 [Kernel_modules](https://linux-kernel-labs.github.io/refs/heads/master/labs/kernel_modules.html) tutorial 後，發現 kernel module 可以使用 `current` 變數 (需要 include `linux/sched.h`)，該變數代表的是一個指標指向該行程的 `struct task_struct`，這意味著 kernel module 是一個獨立且可以被排程的一個單位 (task)，並用有自己的 PID，我們可以使用 `taskset` 根據 PID 固定在指定的 CPU 上執行。

不過我們又面臨一個問題，我們需要程式執行以後才會知道行程的 PID，因此我嘗試使用 [linux/sched](https://github.com/torvalds/linux/blob/master/include/linux/sched.h#L2173) 的 `sched_setaffinity()`，不過遇到以下問題，目前還沒解決：

ERROR: modpost: "sched_setaffinity" [.../fibdrv/fibdrv.ko] undefined!

後來改成在 `client.c` 使用系統呼叫 [sched_setaffinity(2)](https://man7.org/linux/man-pages/man2/sched_setaffinity.2.html)，先將 `fibdv` 的 PID 透過 `write` 傳至 `client.c`，再呼叫 `sched_setaffinity()` 將行程固定在 CPU 0。

### 限定 CPU 給特定的程式使用

[taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 可指定行程所使用的 CPU 核心，但不代表其他的行程不會使用這些被指定的 CPU 核心，如果你不想讓其他的行程干擾你要執行的程式，讓指定的核心只能被自己設定的行程使用，可以使用 `isolcpus` 這個 Linux 核心起始參數，這個參數可以讓特定的 CPU 核心在開機時就被保留下來。

我在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 `isolcpus=cpu_id` 參數：

1. 開機時進入 GRUB。
2. 按 `e` 編輯開機參數。
3. 往下到 `linux` 開頭這行，加上 `isolcpus=0`。
4. 按 `Ctrl-x` 或是 `F10` 以修改過後的設定開機。

觀察 CPU 0 是否在開機後被保留下來：

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

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

使用 `htop` 觀察 CPU 0，不過 CPU 0 的使用率並不是一直維持在 0，推測有其他程式也有使用到 sched_setaffinity()，或是中斷處理 (?)，不過可以大幅減低干擾：


### 排除干擾效能分析的因素

* 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/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

之後再用 `$ sudo sh performance.sh` 執行
* 針對 Intel 處理器，關閉 turbo mode

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


### 用統計手法去除極端值

## 引入 bignum

### 資料結構

* 目前只有使用 `unsigned long` 陣列，後續可以加入 `size` 來做優化。
* 後續更新添加 `size` 來做優化，更該於 [commit 61cad9e](https://github.com/SmallHanley/fibdrv/commit/61cad9ea8f953696209fee3d3ce4605515a58299) 。一是降低運算成本，二是方便於乘法引入 `ctz` 加速手段。
* `size` 為表示此一數字所需的陣列大小 (即表示此數需要多少個 `unsigned long` 的空間)， `size` 為 `0` 代表數字為 `0`。

typedef struct {
    unsigned long val[BN_LENGTH];
    unsigned size;
} bn_t;

### bn_init()

* 將陣列初始化為 `0`。
* `size` 設成 `0`。

static inline void bn_init(bn_t *a)
{
    memset(a->val, 0, sizeof(a->val));
    a->size = 0;
}

### bn_set_with_pos()

* 傳入三個參數，分別為 `bn_t` 變數的位址、`num` 和`pos`。
* 將 `pos` 作為陣列的 index，賦值成 `num`。
* 如果此數原本 `size` 為 `1`，我們又想要將陣列第 `0` 位置設成 `0`，則將 `size` 歸零。

static inline void bn_set_with_pos(bn_t *a, uint64_t num, unsigned pos)
{
    a->val[pos] = num;
    if (unlikely(!pos && !num && a->size == 1)) {
        a->size = 0;
    } else if (pos + 1 > a->size) {
        a->size = pos + 1;                                                                                                         
    }
}

### bn_swap()

* 將給定的兩物件交換。

static inline void bn_swap(bn_t *a, bn_t *b)
{
    bn_t tmp = *a;
    *a = *b;
    *b = tmp;
}

### bn_srl()

* 將大數作邏輯右移。
* 考慮到後續大數乘法可能會使用 `ctzl` 優化，目前實作是使用位移運算子 (`<<`、`>>`)，只能處理小於等於 63 的右移，當 n 超過 64 (包含) 是未定義行為。

static void bn_srl(bn_t *a, bn_t *res, unsigned n)
{
    if (!a->size) {
        bn_init(res);
        return;
    }
    if (!n) {
        *res = *a;
        return;
    }
    for (int i = 0; i < a->size - 1; i++) {
        res->val[i] = a->val[i] >> n | a->val[i + 1] << (64 - n);
    }
    res->val[a->size - 1] = a->val[a->size - 1] >> n;
    res->size = (res->val[a->size - 1]) ? a->size : a->size - 1;
}

### bn_sll()

* 將大數作邏輯左移。
* 同理，目前只能處理小於等於 63 的左移。
* 要注意的是，此處有關 `size` 的實作還是有瑕疵，如果左移超過儲存資料的上限，得到的 `size` 很可能是錯的。

static void bn_sll(bn_t *a, bn_t *res, unsigned n)
{
    if (!a->size) {
        bn_init(res);
        return;
    }
    if (!n) {
        *res = *a;
        return;
    }
    unsigned sz = (a->size > BN_LENGTH - 1) ? BN_LENGTH - 1 : a->size;
    for (int i = sz; i > 0; i--) {
        res->val[i] = a->val[i] << n | a->val[i - 1] >> (64 - n);
    }                                                                                                                              
    res->val[0] = a->val[0] << n;
    res->size = (res->val[sz]) ? sz + 1 : sz;
}

### bn_add()

* 將 `a` 和 `b` 相加的結果存至 `res`。
* 這裡使用 GNU [Built-in Functions to Perform Arithmetic with Overflow Checking](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html) 的 `__builtin_uaddl_overflow()` 來檢查是否產生溢位，從最低位加到最高位，並將 carry 加至高一位。
* 嘗試改寫，使得大數加法成功在編譯器優化開啟時生成出 [x86 指令集](https://en.wikipedia.org/wiki/X86_instruction_listings) 的 `ADC` 或是 `ADCX`，不過沒有成功。

static void bn_add(bn_t *a, bn_t *b, bn_t *res)
{
    unsigned c = 0;
    unsigned sz = (a->size > b->size) ? a->size : b->size;
    for (int i = 0; i < sz; i++) {
        unsigned c1 =
            __builtin_uaddl_overflow(a->val[i], b->val[i], &res->val[i]);
        unsigned c2 = __builtin_uaddl_overflow(res->val[i], c, &res->val[i]);
        c = c1 | c2;
    }
    if (sz < BN_LENGTH) {
        res->val[sz] = c;
        res->size = (res->val[sz]) ? sz + 1 : sz;
    } else {
        res->size = BN_LENGTH;
    }
}

### bn_sub()

* 將 a 和 b 相減的結果存至 res。

static void bn_sub(bn_t *a, bn_t *b, bn_t *res)
{
    unsigned c = 0;
    for (int i = 0; i < a->size; i++) {
        unsigned c1 =
            __builtin_usubl_overflow(a->val[i], b->val[i], &res->val[i]);
        unsigned c2 = __builtin_usubl_overflow(res->val[i], c, &res->val[i]);
        c = c1 | c2;
    }
    for (int i = a->size - 1; i >= 0; i--) {
        if (res->val[i]) {
            res->size = i + 1;
            return;
        }
    }
    res->size = 0;
}

### bn_mul()

* 將 a 和 b 相乘的結果存至 res。
* 目前採用 O(n) 的乘法，使用位移運算子和大數加法實作，後續可以增加 `ctzl` 或是不同演算法優化。

static void bn_mul(bn_t a, bn_t b, bn_t *res)
{
    bn_init(res);
    unsigned sz = b.size;
    for (int i = 0; i < 64 * sz; i++) {
        if (b.val[0] & 1) {
            bn_add(res, &a, res);
        }
        bn_sll(&a, &a, 1);
        bn_srl(&b, &b, 1);
    }
}

乘法除了加上 `size` 來優化，後續也增加 `ctzl` 的優化。原本的實作方式是模擬計算機組織教科書有關乘法器的實作方式，每次都只位移一個 bit。當除數的 bits 為 set 的數量很少的時候，這種作法的位移運算成本會高很多，於是我使用 `ctzl` 加速，可以一次位移多個 bits，實作如下：

static void bn_mul(bn_t a, bn_t b, bn_t *res)
{
    bn_init(res);
    while (b.size) {
        if (b.val[0]) {
            unsigned z = __builtin_ctzl(b.val[0]);
            bn_sll(&a, &a, z);
            bn_srl(&b, &b, z);
            bn_add(res, &a, res);
            b.val[0] &= ~(1ul);
        } else {
            bn_sll(&a, &a, 63);
            bn_srl(&b, &b, 63);
        }
    }
}

對應的實驗和效能分析可以參考下面圖表。

### bn2string()

static char *bn2string(bn_t *a)
{
    char str[64 * BN_LENGTH / 3 + 2];

    memset(str, '0', sizeof(str) - 1);
    str[sizeof(str) - 1] = '\0';

    unsigned sz = a.size;
    for (int i = 0; i < 64 * sz; i++) {
        unsigned carry = a.val[sz - 1] >> 63;
        for (int j = sizeof(str) - 2; j >= 0; j--) {
            str[j] += str[j] - '0' + carry;
            carry = (str[j] > '9');
            if (carry)
                str[j] -= 10;
        }
        bn_sll(&a, &a, 1);
    }

    // search for numbers
    int i = 0;
    while (i < sizeof(str) - 2 && str[i] == '0')
        i++;

    // passing string back
    char *p = kmalloc(sizeof(str) - i, GFP_KERNEL);
    memcpy(p, str + i, sizeof(str) - i); 

    return p;
}

### 效能分析

引入 bignum 後，根據 Linux 效能分析的提示，繪製出不同實作方式對於不同輸入參數所花的時間比較：


將輸入參數擴增至 1000，發現 fast-doubling 和 exponentiating by squaring 與原本 $O(n)$ 時間複雜度相比，花費時間高很多，可見目前採用的乘法實作方式還有很大改進空間：


後續改進加入 `size` 和 `ctzl` 優化，前者優化各種運算的次數 (包含加法、減法、位移運算)，後者大幅減少位移運算次數，實驗結果如下：


發現 exponentiating by squaring 的乘法運算量還是過大，fast-doubling 和 sequence 較為接近，不過在前 1000 項還是 sequence 的方式花費時間最少 (後續實驗發現輸入參數數量級要到 $10^5$，fast-doubling 才會追過 sequence)。

下圖以 fast-doubling 的實作方式，分析加上 `size` (不含 `ctzl`) 前後花費時間的比較：


在大數乘法的實作中加入 `ctzl` 優化，可以大幅減少位移運算的次數，下圖是實驗有無 `ctzl` 的比較，發現採用 `ctzl` 的程式碼執行時間大幅縮短：


進一步觀察整體程式 (fast-doubling 從 0 執行到 1000) 呼叫大數運算的次數，確實大幅減少 `bn_sll()` 、`bn_srl()` 的呼叫次數：

| no-ctz | add | sub | sll | srl |
| ------ | ------ | ---- | ------- | ------- |
| times | 541118 | 8987 | 2316635 | 2307648 |

| with-ctz | add | sub | sll | srl |
| -------- | ------ | ---- | ------ | ------ |
| times | 541118 | 8987 | 562141 | 553154 |

## Reference

[矩陣快速冪](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/HJiorDSpE?type=view)
[Fast-doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling)
[The high-resolution timer API](https://lwn.net/Articles/167897/)
[Message logging with printk](https://www.kernel.org/doc/html/latest/core-api/printk-basics.html)
[oscarshiang 共筆](https://hackmd.io/@oscarshiang/linux_fibdrv)
[Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
[Kernel modules](https://linux-kernel-labs.github.io/refs/heads/master/labs/kernel_modules.html)
[rt:labs Real-time properties of Linux](https://rt-labs.com/docs/p-net/linuxtiming.html)
[Built-in Functions to Perform Arithmetic with Overflow Checking](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)