# 2023q1 Homework3 (fibdrv)
contributed by < `paulpeng-popo` >
> Github: [paulpeng-popo](https://github.com/paulpeng-popo/fibdrv)

## 開發環境

$ 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
Byte Order:              Little Endian
Address sizes:           39 bits physical, 48 bits virtual
CPU(s):                  12
On-line CPU(s) list:     0-11
Thread(s) per core:      2
Core(s) per socket:      6
Socket(s):               1
NUMA node(s):            1
Vendor ID:               GenuineIntel
CPU family:              6
Model:                   158
Model name:              Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping:                10
CPU max MHz:             4600.0000
CPU min MHz:             800.0000
BogoMIPS:                6399.96
Virtualization:          VT-x
L1d:                     192 KiB (6 instances)
L1i:                     192 KiB (6 instances)
L2:                      1.5 MiB (6 instances)
L3:                      12 MiB (1 instance)
NUMA node0 CPU(s):       0-11

## 開發紀錄

### 頭腦暖身操
:::spoiler
#### 費氏數列推導

假設成年兔子為 `a`，幼年兔子為 `b`，且兔子不死亡

$a_{n+1} = a_n + b_n$
$b_{n+1} = a_n$

==一般遞迴==

$a_{n+1} = a_{n-1} + a_n, n \ge 1$
$a_0 = 0, a_1 = 1$

==矩陣運算 Q-matrix==

$\begin{bmatrix}
a_{n+1} \\ b_{n+1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_n \\ b_n
\end{bmatrix}$

又可改寫成

$\begin{bmatrix}
a_{n+1} \\ a_n
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
a_n \\ a_{n-1}
\end{bmatrix}$

$\begin{bmatrix}
a_{n+1} & a_n \\ a_n & a_{n-1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n$

==Fast Doubling==

$F(0) = a_0 = 0$
$F(1) = a_1 = 1$

$$
\begin{split}
\begin{bmatrix}
F(2n+1) \\ F(2n)
\end{bmatrix} &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n}
\begin{bmatrix}
F(1) \\ F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\begin{bmatrix}
F(1) \\ F(0)
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
F(n+1) & F(n) \\
F(n) & F(n-1)
\end{bmatrix}
\begin{bmatrix}
1 \\ 0
\end{bmatrix}\\ \\ &=
\begin{bmatrix}
F(n+1)^2 + F(n)^2\\
F(n)F(n+1) + F(n-1)F(n)
\end{bmatrix}
\end{split}
$$

其中 $F(n-1) = 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(\log{n})$ 內，這可以大幅減少重複的計算

參考：[Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/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(log n)$ 次遞迴
- 總共時間複雜度為 $O(1) * O(log n) = O(log n)$

解釋 fast doubling ==為什麼用 2k 跟 2k + 1==

例如：**長度為 n 個 bit 的數字 $\alpha$** 與 **長度為 n+1 個 bit 的數字 $\beta$** 具有以下關係：
- if $\beta$ 要為偶數，則 $\beta = 2\alpha$，也就是 $\beta$ = $\alpha$ << 1
- if $\beta$ 要為奇數，則 $\beta = 2\alpha + 1$，也就是 $\beta$ = $\alpha$ << 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](https://www.phoronix.com/news/Linux-Kills-The-VLA) 有提到 Linux kernel 不再允許 VLA 的使用
>
> C99 具有 VLA (Variable-Length Array) 的特性，允許執行時期再決定陣列佔用的空間大小，但可能會造成 stack overflow 等安全疑慮
根據教材 [你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function#stack-based-buffer-overflow)，攻擊者可以利用 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.](https://lkml.org/lkml/2018/3/7/621)』

/* 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];
}

#### 時間測量功能

> 參考 [時間測量與效能分析](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c) 的說明與 [qwe661234](https://hackmd.io/@qwe661234/linux2022q1-homework3#%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90) 的解釋
> 1. [High resolution timers and dynamic ticks design notes](https://docs.kernel.org/timers/highres.html)
> 2. [hrtimers - subsystem for high-resolution kernel timers](https://docs.kernel.org/timers/hrtimers.html)

在 Linux kernel 中具有兩種計時方式

==jiffies== 是 Linux kernel 較早期存在的計時方法，使用作業系統**從開機以來的計時器中斷發生的次數**作為計時的依據，此全域變數稱作 `ticks` 數。計時器中斷為週期性的中斷事件，以固定的時間間隔觸發，利用間隔固定的特性便能達到測量時間的目的。

通常情況下，jiffies 的精度為毫秒級別，具體的精度取決於 tick rate 的大小。例如 1000Hz 表示每秒觸發 1000 次的 timer interrupt，因此 jiffies 的增加速度為每毫秒一次。

jiffies 轉換為**秒**的公式為

(unsigned long long)(jiffies - INITIAL_JIFFIES) / HZ;

由以上程式碼可知, 假如系統原先設定的 `tick rate (HZ)` 不大於 $10^9$，其時間精度是無法達到 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，單位為奈秒 (ns)

透過調用 [Linux kernel API](https://elixir.bootlin.com/linux/v4.4/source/kernel/time/timekeeping.c#L665) `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` 中順序調用 `read` 和 `write`，即可取得所花費的 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](https://hackmd.io/@yanjiew/linux2023q1-fibdrv#%E5%A4%9A%E6%BC%94%E7%AE%97%E6%B3%95%E9%81%B8%E6%93%87) 的做法，利用 `read` 傳入 `size` 作為使用不同演算法的條件

/* 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

#!/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 進行費氏數計算

#### 去除極端值
參考 [時間測量與效能分析](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c)

計算 50 次費氏數的平均，並將離散值做處理，用以得到較平滑的效能比較圖
程式碼 [4b6a40c](https://github.com/paulpeng-popo/fibdrv/commit/4b6a40cd4785434a5250e6ef80409fb5e2ea2561#diff-310bc6068100c1b144bacada83ff9be0125cea94160c62aea2ca0b15c3e566fa)