---
tags: linux kernel
---

# 2023q1 Homework3 (fibdrv)
contributed by < [hankTaro](https://github.com/hankTaro/fibdrv) >

## 自我檢查清單

- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉

### 欲完成功能
- [ ] 利用 list 實作 bignumber

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
    CPU family:          6
    Model:               126
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            5
    CPU max MHz:         3600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            2380.80
    
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   192 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    2 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7

## 開發階段一 支援大數運算

### bn 結構
使用 `bn` 結構體，將單一數值以 `int` 陣列儲存，並用 `size` 紀錄共需要幾個 `int` 空間作儲存，而 capacity 作為 [memory pool](https://en.wikipedia.org/wiki/Memory_pool) 的空間上限，以進行動態記憶體管理(稍後會解釋)

/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
    unsigned int *number;
    unsigned int size;
    unsigned int capacity;
    int sign;
} bn;

e.g. $2^{35}$ 需要兩個 `int` 空間做儲存

digraph graphname {
    
    list_1[label="<f0>00000000000000000000000000001000|<f1>00000000000000000000000000000000",shape=record, fixedsize=false,width=6]
    
    node[label="number[0]",shape=none]; i1
    node[label="number[1]",shape=none]; i2
    
    list_1:f0->i2[style=invis]
    list_1:f1->i1[style=invis]

    }

### bn 的空間分配

由於是利用多個 32 bit 儲存資料，在定義與分配記憶體空間就十分關鍵，在執行初始化與算數運算時，都需要額外執行分配空間的工作，特別是在算數運算時，需要先將輸出的空間預備好，避免 overflow ， 為了避免過於頻繁的呼叫 `krealloc` 造成時間的浪費，這裡預先引入 [memory pool](https://en.wikipedia.org/wiki/Memory_pool)，當所需 `size` 小於 `capacity` 時，便不會重新分配空間，而是單純的將 `size` 改為所需空間

bn *bn_alloc(size_t size)
{
    bn *new = (bn *) kmalloc(sizeof(bn), GFP_KERNEL);
    new->size = size;
    new->capacity = size > INIT_ALLOC_SIZE ? (size + (ALLOC_CHUNK_SIZE - 1)) &
                                                 ~(ALLOC_CHUNK_SIZE - 1)
                                           : INIT_ALLOC_SIZE;  // ceil to 4*n
    new->number =
        (unsigned int *) kmalloc(sizeof(int) * new->capacity, GFP_KERNEL);
    for (int i = 0; i < size; i++)
        new->number[i] = 0;
    new->sign = 0;
    return new;
}


static int bn_resize(bn *src, size_t size)
{
    ...
        
    if (size > src->capacity) { /* need to allocate larger capacity */
        src->capacity = (size + (ALLOC_CHUNK_SIZE - 1)) &
                        ~(ALLOC_CHUNK_SIZE - 1);  // ceil to 4*n
        src->number =
            krealloc(src->number, sizeof(int) * src->capacity, GFP_KERNEL);
    }
    if (!src->number) {  // realloc fail
        return -1;
    }
    if (size > src->size) { /* memset(src, 0, size) */
        for (int i = src->size; i < size; i++)
            src->number[i] = 0;
    }
    src->size = size;
    return 0;
}

當 `capacity = 4` `size = 2` 時，已知輸出所需空間為 3 ，故進行 `bn_resize(src, 3)` ，但 3 未超過 memory pool 上限，故單純將 `src->size = 3`

digraph graphname {
    
    list_1[label="<f0>未使用|<f1>未使用|<f2>已使用|<f3>已使用",shape=record, fixedsize=false,width=6]
    list_2[label="<f0>未使用|<f1>已使用|<f2>已使用|<f3>已使用",shape=record, fixedsize=false,width=6]
    
    node[label="number[0]",shape=none]; i1
    node[label="number[1]",shape=none]; i2
    node[label="number[2]",shape=none]; i3
    node[label="number[3]",shape=none]; i4
    
    
    
    list_1->list_2[label="bn_resize(src, 3)"]
    
    list_2:f0->i4[style=invis]
    list_2:f1->i3[style=invis]
    list_2:f2->i2[style=invis]
    list_2:f3->i1[style=invis]

    }

:::info
為了方便說明，往後將 `number[0]` `number[1]` 這種已使用的區域，取名為 ==block==
:::

### 算數運算

算數運算有以下幾個重點
* 預先判斷輸出最多可能需要幾個 block，預先將輸出空間分配至其大小
* 結束前確認輸出 block 的數量，並更改其 size
* 進位的處理
* 減少變數量
* 正負號的判別
* 支援 `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;
        }
    }
}

void bn_sub(const bn *a, const bn *b, bn *c)
{
    /* xor the sign bit of b and let bn_add handle it */
    bn tmp = *b;
    tmp.sign ^= 1;  // a - b = a + (-b)
    bn_add(a, &tmp, c);
}

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);
}

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);
}

值得注意的地方是 40 行，利用 `clz` 快速取得左側 0 的數量，快速取得其 size，而非使用迴圈

至於乘法運算先使用最簡單的 block 兩兩相乘後相加至對應的位置，在第二階段加速運算部分在將其改進

有一個點要注意，因為乘法中的單一 block 需要反覆與其他 block 相乘，所以其相乘結果無法存入輸入位置，需要將回傳結果的輸入備份，再以備份進行相乘，避免輸入的值遭到更改而無法正確的相乘

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);
    }
}

static void bn_mult_add(bn *c, int offset, unsigned long long int x)
{
    unsigned long long int carry = 0;
    for (int i = offset; i < c->size; i++) {
        carry += c->number[i] + (x & 0xFFFFFFFF);
        c->number[i] = carry;
        carry >>= 32;
        x >>= 32;
        if (!x && !carry)  // done
            return;
    }
}

### 運行測試

由於本模組要掛載至核心中，所以在 `fibdrv.c` 中有自定義系統呼叫

const struct file_operations fib_fops = {
    .owner = THIS_MODULE,
    .read = fib_read,
    .write = fib_write,
    .open = fib_open,
    .release = fib_release,
    .llseek = fib_device_lseek,
};

在 `fib_sequence` 中先使用最簡單的方法求費式數列，將回傳值存入 `dest` 中，再將數值轉換成字串後，使用 `fib_read` 中的 `__copy_to_user` 將字串傳回到 user space

void fib_sequence(bn *dest, long long k)
{
    // bn *fib = kmalloc((k + 2) * sizeof(bn), GFP_KERNEL);
    bn_resize(dest, 1);
    if (k < 2) {
        dest->number[0] = k;
        return;
    }

    bn *a = bn_alloc(1);
    bn *b = bn_alloc(1);
    dest->number[0] = 1;

    for (size_t i = 1; i < k; i++) {
        bn_swap(b, dest);
        bn_add(a, b, dest);
        bn_swap(a, b);
    }
    bn_free(a);
    bn_free(b);
}


static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    bn *result = bn_alloc(1);
    fib_sequence(result, *offset);
    char *p = bn_to_string(*result);
    size_t len = strlen(p) + 1;
    __copy_to_user(buf, p, len);
    bn_free(result);
    kfree(p);

    return 0;
}

另外要注意 `fibdrv.c` 中 `MAX_LENGTH` 定義，需要修改其上限才可以求出 F(92) 以上的值，希望不要有其他人也因為這個問題被困擾好幾天

#define MAX_LENGTH 1000

確認計算至 `1000` 為止的值都是正確的

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

<!-- :::info
欲了解問題
* 不理解 size_t 的使用時機以及其作用
* 不理解 user 與 kernal 之間是如何利用 driver 進行資料傳遞和使用特定功能
* 在 user 是只能使用 `read()` `write()` 等特定函式去與 kernel 端作互動嗎(存取資料 寫入讀出等等)嗎?
* > 此為系統呼叫，fibdrv 設計為一個 [character device](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html)，可理解是個能夠循序存取檔案，透過定義相關的函數，可利用存取檔案的系統呼叫以存取 (即 open, read, write, mmap 等等)。因此，使用者層級 (user-level 或 userspace) 的程式可透過 read 系統呼叫來得到輸出。

* 當把 .ko 檔掛載進核心中，並且定義了 read write 等函式，此模組就是屬於 kernel 端了嗎? 另外由於定義了 read 那往後不想使用此模組功能的 read 是一定要將其卸載嗎?

::: -->

## 開發階段二 加速運算

### 實驗環境架設

* 抑制 [address space layout randomization (ASLR)](https://en.wikipedia.org/wiki/Address_space_layout_randomization)

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

* 限定部分 CPU 只運行此程式，利用 [taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 指定行程所使用的 CPU 核，並且使用 isolcpus 這個 Linux 核心起始參數，讓特定的 CPU 核在開機時就被保留下來，這樣便可讓特定 CPU 不受其他因素干擾，限定在特定程式上
> 設定的方式有兩種，一個是在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 isolcpus=cpu_id 參數，或是直接加在 GRUB 的設定檔中，這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核中執行，只有那些被 taskset 特別指定的行程可使用
>
>* 用第一種方式:
>如果想讓第 0 個與第 1 個 CPU 核都被保留下來，則在開機時加入:
>```
>isolcpus=0,1
>```
>* 第二種方式:
>修改 `/etc/default/grub 內的 GRUB_CMDLINE_LINUX_DEFAULT` 為 `GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"` ，
>修改完成後需 `sudo update-grub` 來更新設定，重開機後即生效
* 設定 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"

* 關閉 [SMT](https://en.wikipedia.org/wiki/Simultaneous_multithreading) (Intel 稱它為 [Hyper-Threading](https://en.wikipedia.org/wiki/Hyper-threading))

    $ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"

參考 [do_measurement.sh](https://github.com/KYG-yaya573142/fibdrv/blob/master/do_measurement.sh) 將以上設定包進一個 shell script 中

#!/bin/bash
#This script tweak the system setting to minimize the unstable factors while
#analyzing the performance of fibdrv.
#
#2023/3/20  ver 1.0
CPUID=7
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`

sudo bash -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"

#measure the performance of fibdrv
make client_plot
make client_statistic
make unload
make load
rm -f plot_input_statistic
sudo taskset -c 7 ./client_statistic
sudo taskset -c 7 ./client_plot > plot_input
gnuplot scripts/plot-statistic.gp
gnuplot scripts/plot.gp
make unload

# restore the original system settings
sudo bash -c "echo $ORIG_ASLR >  /proc/sys/kernel/randomize_va_space"
sudo bash -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo bash -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"

### 引入 ktime API
在 `fib_read` 與 `fib_write` 做修改，並將 `fib_read` 中的呼叫導向 `fib_time_proxy` ，一個用於測量不同作法所需時間的函式

### 輸出圖表
使用[此 Python script](https://github.com/colinyoyo26/fibdrv/commit/4ce43c4e7ee0b80c4ce9e6dcd995bbfdf239206c)，計算某個 fibonacci number 的時間，並去除 95% 區間之外的值

並更改 MakeFile 中新增 plot 以方便輸出圖表

plot: all
	$(MAKE) unload
	$(MAKE) load
	@python3 scripts/driver.py
	$(MAKE) unload

### 計算 CPU time 以及 Real time

由於從核心模式複製資料到使用者層級是有時間成本的，每個位元組會花費 22ns，因此 CPU time 的計算需避免計算到 `copy_to_user` 的時間，而 Real time 需要計算從使用者呼叫到使用者收到資料的時間，包括 Wall clock time 和其他 process 使用的 time slice 和該 process 耗費在阻塞上的時間。

### 去除 cache miss 造成的震盪
> 觀察計算 fibonacci 的時間會發現會有震盪的奇況 每過一段時間執行時間就會往上跳一小段 是因為 cache miss，若要排除這種 cache 對執行時間所造成的影響可以藉由降低 realloc 次數，因為 realloc 可能導致需要將原本的資料搬到更大的記憶體空間而新的空間並不是在原本的附近，造成原本 cache 裡的資料需要被更新。

可以先進入計算 fib 函式，算完後，因為 cache 裡的資料已被更新，再利用 ktime 開始計算時間，再算一次取 ktime

#### 圖片

### 引入 fast doubling

利用 shift 而非乘法

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;
}