---
tags: linux2022
---

# 2022q1 Homework3 (fibdrv)
contributed by < [`jj97181818`](https://github.com/jj97181818) >
## 自我檢查清單

- [x] 研讀上述 ==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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 研讀 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU)，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？
- [ ] `lsmod` 的輸出結果有一欄名為 `Used by`，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 ([reference counting](https://en.wikipedia.org/wiki/Reference_counting)) 在 Linux 核心如何追蹤呢？
> 搭配閱讀 [The Linux driver implementer’s API guide » Driver Basics](https://www.kernel.org/doc/html/latest/driver-api/basics.html)
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。
- [ ] timer interrupt, IPI

## 效能分析
### 限定 CPU 給特定的程式使用
1. 在 `/etc/default/GRUB` 中的一行 `GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"` 加入 `isolcpus=3`，指定編號 3 的 CPU 核心就不會被 Linux 的排程器安排行程，只有用 `taskset` 設定的 process 可以使用該 CPU 核心：

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=3"

2. 執行 `sudo update-grub` 後關機，然後透過 `cat /sys/devices/system/cpu/isolated` 可以確認是否有設定成功。這裡有成功回傳 3。

### 指定 CPU 核心來執行一個新的程式
1. 指定保留的 CPU 核心來跑 `./client`

sudo taskset 0x8 ./client

### 排除干擾效能分析的因素
1. 抑制 address space layout randomization (ASLR)
不讓 ASLR 利用隨機方式配置資料位址。

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

+ 0 = 關閉
+ 1 = 半隨機
+ 2 = 全隨機

2. 用以下 shell script，檔名為 performance.sh:

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

再用 `sudo sh performance.sh` 執行，固定 CPU 頻率。

3. 針對 Intel 處理器，關閉 turbo mode

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

CPU 就不會自動超頻。原本是 0，改為 1。

## kernel space 傳遞到 user space
### copy_to_user
原本的 `fib_read` 從 kernel space 傳遞到 user space 時，會碰到只能回傳 `ssize_t` 大小的值，在 LP64 資料模式中僅 64 位元，會使得 Fibonacci 數只能算到 $F(92)$ = 7540113804746346429，$F(93)$ 之後的皆無法正確傳送。

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

因此改用 `copy_to_user` 將 Fibonacci 數從 kernel space 傳遞到 user space。

unsigned long copy_to_user (void __user * to, const void * from, unsigned long n);

將 `from` 的資料複製到 `to`。
+ to: Destination address, in user space.
+ from: Source address, in kernel space.
+ n: Number of bytes to copy.

因為 `fib_read` 從 user space 取得的參數 `buf` 的型別是 `char*`，所以要將 Fibonacci 數 `fib` 從 `long long` 轉成 `char*`。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    char fib[64];
    long long n = fast_doubling(*offset);
    int i = 0;

    if (n == 0) {
        fib[i] = '0';
        i++;
    }

    while (n) {
        fib[i] = (n % 10) + '0';
        n /= 10;
        i++;
    }

    fib[i] = '\0';

    int start = 0, end = i - 1;
    while (start < end) {
        int temp = fib[start];
        fib[start] = fib[end];
        fib[end] = temp;
        start++;
        end--;
    }

    copy_to_user(buf, fib, 64);

    return (ssize_t) fib_sequence(*offset);
}

後來實作大數運算，是將 `BigN*` 型別的 Fibonacci 數轉成 `char*`，然後同樣使用 copy_to_user。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    char fib[64];
    
    BigN *n = fib_sequence_BigN(*offset);
    BigN_to_string(fib, n);

    copy_to_user(buf, fib, 64);
    return (ssize_t) fib_sequence(*offset);
}

## 計算 Fibonacci 數的方法
### 一、iterative
最基本計算 Fibonacci 數的方式：
$$
a_{n+1} = a_n + b_n \\ b_{n+1} = a_n
$$

原本提供的 `fib_sequence` 程式有 VLA 的問題：

static long long fib_sequence(long long k)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    long long f[k + 2];

    f[0] = 0;
    f[1] = 1;

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

    return f[k];
}

其實這裡不需要處理 VLA 的問題，因為可以用更簡單的方式來儲存計算過程：透過 3 個型別為 `long long` 的變數，取代原本的 variable-length array。

static long long fib_sequence(long long k)
{
    if (k == 0) return 0;
    long long a, b;
    a = 0;
    b = 1;

    for (int i = 2; i <= k; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

不傾向使用 VLA 是因為如果變數是很大的值，可能會導致 buffer overflow，放在 stack 中，會因為太大蓋到其他的資料。

### 二、fast doubling
當需要計算 2k（偶數）或 2k + 1（奇數）的 Fibonacci 數時，只要使用到 k 和 k + 1 的 Fibonacci 數，這表示不需要將 2k 之前所有數字的 Finbonacci 數都算一遍，可以減少計算量。
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$

先將要求的 Fibonacci 數 `n` 換成二進位來看，從 MSB 開始判斷是 0 還是 1
+ 遇到 0，求 F(2k) 和 F(2k + 1)
+ 遇到 1，求 F(2k + 1) 和 F(2k + 2)

一直看到 `n` 的 LSB 為止。

參考 [K04: fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97) fast doubling 的虛擬瑪，程式碼如下：

因為加法的結果都會存在資料型態為 long long 的變數中，所以只能算到第 92 個 Fibonacci 數，所以這裡的 `n` 最大到 92，92~10~ = 1011100~2~，因此最多只需要將 mask `i` 先向左位移六位即可。

static long long fast_doubling(long long n)
{
    long long a = 0, b = 1;

    for (unsigned int i = 1U << 6; i; i >>= 1) {
        long long t1 = a * (2 * b - a);  // 2k
        long long t2 = a * a + b * b;    // 2k+1
        if (n & i) {
            a = t2; // 2k + 1
            b = t1 + t2; // 2k + 2
        } else {
            a = t1; // 2k
            b = t2; // 2k + 1
        }
    }
    return a;
}

由實驗可看出，左移 6 位 fast doubling 的速度，的確比左移 31 位的 fast doubling 來得快，因為需要跑的迴圈數比較少。

### 三、fast doubling with clz
使用 `__builtin_clz` 計算 leading zero 的個數，加速 fast doubling，減少不必要的迴圈執行。

static long long fast_doubling_clz(long long n)
{
    long long a = 0, b = 1;

    for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
        long long t1 = a * (2 * b - a);  // 2k
        long long t2 = a * a + b * b;    // 2k+1
        if (n & i) {
            a = t2;
            b = t1 + t2;
        } else {
            a = t1;
            b = t2;
        }
    }
    return a;
}

`fast doubling` 左移 6 位和 `fast doubling with clz` 看起來不會差太多。

## 時間量測
### kernel space
因為 `fib_write` 在這個 kernel module 裡面沒有做什麼事，所以拿來測量 Fibonacci 數演算法的時間，參考 [KYWeng](https://hackmd.io/@KYWeng/rkGdultSU#%E9%87%8F%E6%B8%AC%E6%99%82%E9%96%93%E7%9A%84%E6%96%B9%E5%BC%8F) 的做法，利用傳進來的 `size` 參數，選擇要測量的演算法。
+ 0: fib_sequence
+ 1: fast_doubling
+ 2: fast_doubling_clz

static ktime_t kt;
/* write operation is skipped */
static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    long long res = 0;
    if (size == 0) {
        kt = ktime_get();
        res = fib_sequence(*offset);
        kt = ktime_sub(ktime_get(), kt);
    } else if (size == 1) {
        kt = ktime_get();
        res = fast_doubling(*offset);
        kt = ktime_sub(ktime_get(), kt);
    } else if (size == 2) {
        kt = ktime_get();
        res = fast_doubling_clz(*offset);
        kt = ktime_sub(ktime_get(), kt);
    }
    return ktime_to_ns(kt);
}


三個演算法測量出來的時間，看起來 `iterative` 最花時間，再來是 `fast doubling with clz`，最後是 `fast doubling`。但是有用到 `clz` 的 `fast doubling` 比沒有 `clz` 的執行更慢還滿奇怪的。

同樣是參考 [KYWeng](https://hackmd.io/@KYWeng/rkGdultSU#%E9%87%8F%E6%B8%AC%E6%99%82%E9%96%93%E7%9A%84%E6%96%B9%E5%BC%8F) 用 `escape` 函式來避免編譯器做最佳化時，直接不執行沒用到其結果的程式。
+ `__attribute__((always_inline))` 會確保 escape 這個 inline function 永遠會展開
+ `__asm__ volatile ("" : : "g"(p) : "memory");` 這行 assembly 的 volatile 會提醒編譯器該變數可能隨時改變，阻止編譯器做優化。

__attribute__((always_inline))
static inline void escape(void *p) {
  __asm__ volatile ("" : : "g"(p) : "memory");
}

用 escape 函式來保護 `res` 不被編譯器優化影響，並確實計算 `fast_doubling` 和 `fast_doubling_clz`。

static ktime_t kt;
/* write operation is skipped */
static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    long long res = 0;
    if (size == 0) {
        kt = ktime_get();
        res = fib_sequence(*offset);
        kt = ktime_sub(ktime_get(), kt);
    } else if (size == 1) {
        kt = ktime_get();
        res = fast_doubling(*offset);
        kt = ktime_sub(ktime_get(), kt);
    } else if (size == 2) {
        kt = ktime_get();
        res = fast_doubling_clz(*offset);
        kt = ktime_sub(ktime_get(), kt);
    }
+   escape(&res);
    return ktime_to_ns(kt);
}


實驗結果看起來比較合理了，`fast doubling with clz` 執行的速度比 `fast doubling` 都來得快，然後 `iterative` 隨著 Fibonacci 數愈來愈大，執行時間愈來愈長，慢慢地超過 fastdoubling 做法所花的時間。

## 大數運算
因為 `long long` 可以儲存的數字只夠存到 F(92)，從 F(93) 以後的數字都會 overflow，所以要自定義一個大數的資料結構，並定義大數的相關運算。

### 結構

typedef struct _BigN {
    unsigned int *val;
    unsigned int size;
    int sign;
} BigN;

### to_string

static void BigN_to_string(char* s, BigN *num) {
    // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
    size_t len = (8 * sizeof(int) * num->size) / 3 + 2 + num->sign;
    char *p = s;

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

    for (int i = num->size - 1; i >= 0; i--) {
        for (unsigned int d = 1U << 31; d; d >>= 1) {
            /* binary -> decimal string */
            int carry = ((d & num->val[i]) > 0);
            for (int j = len - 2; j >= 0; j--) {
                s[j] += s[j] - '0' + carry; // double it
                carry = (s[j] > '9');
                if (carry)
                    s[j] -= 10;
            }
        }
    }
    // skip leading zero
    while (p[0] == '0' && p[1] != '\0') { 
        p++;
    }
    if (num->sign)
        *(--p) = '-';
    memmove(s, p, strlen(p) + 1);
}

### add

static BigN* BigN_add(const BigN *a, const BigN *b)
{
    unsigned int size = ((a->size > b->size) ? a->size : b->size) + 1;
    BigN *sum = BigN_new(size);

    unsigned int carry = 0;
    unsigned long s = 0;
    for (int i = 0; i < sum->size; i++) {
        unsigned int tmp1 = (a->size) > i ? a->val[i] : 0;
        unsigned int tmp2 = (b->size) > i ? b->val[i] : 0;
        s = (unsigned long)tmp1 + tmp2 + carry;
        
        sum->val[i] = s & UINT_MAX;
        carry = 0;
        if (s > UINT_MAX) {
            carry = 1;
        }
    }
    if (sum->val[sum->size - 1] == 0) {
        sum->size -= 1;
    }

    return sum;
}

### new

static BigN* BigN_new(unsigned int size) {
    BigN *new = kmalloc(sizeof(BigN), GFP_KERNEL);
    new->size = size;
    new->sign = 0;
    new->val = kmalloc(sizeof(unsigned int) * size, GFP_KERNEL);
    memset(new->val, 0, sizeof(unsigned int) * size);

    return new;
}

### free

static void BigN_free(BigN *num) {
    kfree(num->val);
    kfree(num);
}

### 用大數實作的 iterative

static BigN* fib_sequence_BigN(long long k)
{

    BigN *a = BigN_new(1); // f(0) = 0
    BigN *b = BigN_new(1); // f(1) = 1
    b->val[0] = 1;
    BigN *sum;

    if (k == 0) return a;

    for (int i = 2; i <= k; i++) {
        sum = BigN_add(a, b); // f[i] = f[i - 1] + f[i - 2]
        BigN_free(a);
        a = b;
        b = sum;
    }
    BigN_free(a);

    return b;
}

能算出 f(93) 以後的值了

Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.