---
tags: linux2023
---
# 2023q1 Homework3 (fibdrv)
contributed by < `brianlin314` >
## 開發環境
```shell
$ 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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12400
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
CPU max MHz: 5600.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
```
## 前期準備
詳閱 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 了解 Linux 核心模組掛載機制
Ubuntu 預設開啟 EFI_SECURE_BOOT_SIG_ENFORCE，使得核心模需要簽章才可掛載進入 Linux 核心，所以需將 UEFI Secure Boot 的功能關閉。
需輸入 8-16 個字元的密碼，並且重新 reboot 後，需按照系統提示的數字，輸入你密碼對應的字元。
```shell
$ sudo apt install mokutil
$ sudo mokutil --disable-validation
```
Linux 核心版本需大於等於 `5.4.0`
```shell
$ uname -r
5.19.0-35-generic
```
安裝 `linux-headers` 套件，並確認是否安裝
```shell
$ sudo apt install linux-headers-`uname -r`
$ dpkg -L linux-headers-5.19.0-35-generic | grep "/lib/modules"
```
得到輸出
```
/lib/modules
/lib/modules/5.19.0-35-generic
/lib/modules/5.19.0-35-generic/build
```
檢驗目前的使用者身份，第一個命令的預期輸出為 `非root的使用者名稱`，第二個命令的預期輸出則為 `root`
```shell
$ whoami
$ sudo whoami
```
安裝必要套件
```shell
$ sudo apt install util-linux strace gnuplot-nox
```
在 Linux 核心掛載 `fibdrv.ko` 核心模組
```shell
$ sudo insmod fibdrv.ko
```
---
## Linux 效能分析
參考 [KYG-yaya573142](https://hackmd.io/@KYWeng/rkGdultSU#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0) 所紀錄的排除干擾效能分析的因素
在多核心作業系統中，使用處理器的親和性(processor affinity) 讓行程在特定的CPU核中持續執行的好處。將行程綁定在特定的CPU核上可以減少cache miss的狀況，也可以增進執行效率。
#### 查看行程的 CPU affinity
在 Linux 系統中可以使用 taskset 命令來設定或取得行程的處理器親和性。
```shell
$ taskset -p 1
pid 1's current affinity mask: fff
```
可以看見輸出為 `fff`，轉成二進位格式之後為 `111111111111`，表示行程可以在第 0 到第 11 個 CPU 核中執行，若位元值為 `1` 則代表該行程可在這個位元對應的 CPU 核中執行，若位元值為 `0` 則代表該行程不允許在這個位元對應的 CPU 核中執行。
也可以使用以下命令，直接輸出 CPU 核的列表：
```shell
$ taskset -cp 1
pid 1's current affinity list: 0-11
```
#### 限定 CPU 給特定的程行程使用
修改 `/etc/default/grub` 內的 `GRUB_CMDLINE_LINUX_DEFAULT`，加入 isolcpus=7 來指定編號 7 的核心不被排程器賦予任務。
修改完成後需 sudo update-grub 來更新設定，重開機後即生效，輸入以下命令可查看是否設定成功：
```shell
$ taskset -cp 1
pid 1's current affinity list: 0-6,8-11
```
```shell
$ cat /sys/devices/system/cpu/isolated
7
```
#### 固定在特定的 CPU 中執行
```
$ sudo taskset -c 7 ./client
```
#### 排除干擾效能分析的因素
<s>
簡單請 ChatGPT 解釋 ASLR ，見以下：
地址空間隨機化（Address Space Layout Randomization，簡稱ASLR）是一種記憶體保護機制，用於抵禦緩衝區溢出攻擊。 ASLR 會在每次運行程式時，隨機地配置程式使用的記憶體地址，使得攻擊者無法預測所要攻擊的程式的記憶體地址，從而增加了攻擊者利用程式漏洞的難度[[1]](https://zhuanlan.zhihu.com/p/58419878)。 ASLR 可以在Linux、Windows 和 macOS 等操作系統中使用[[1]](https://zhuanlan.zhihu.com/p/58419878)。在 ASLR 機制中，程式在運行時的地址空間會被隨機化，而程式的代碼段和數據段的隨機化則由PIE（Position Independent Executable）機制負責，但是只有在開啟ASLR之後，PIE才會生效[[3]](https://zhuanlan.zhihu.com/p/77370302)。
</s>
:::warning
參照 LWN 的 [Kernel address space layout randomization](https://lwn.net/Articles/569635/)，儘量閱讀第一手材料
:notes: jserv
:::
#### 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
#### 設定 scaling_governor 為 performance
準備以下 shell script 來設定 CPU 以最高頻率執行所有 process
```shell
$ vim performance.sh
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
done
$ sudo sh performance.sh
```
#### 關閉 turbo mode
關閉 Intel 處理器的 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
---
## 費式數列
參考 [你所不知道的 C 語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion#Fibonacci-sequence) 的 Fibonacci sequence
### Iterative
以下是原始 `fibdrv.c` 裡實作的計算費式數列程式碼，相比於 Recursive 版本，運用 array 來儲存已計算過的子問題，能避免子問題的重複計算，時間複雜度與空間複雜度皆為 $O(n)$，尚有很大的進步空間。
```c
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];
}
```
### Fast Doubling
參考 [Matrix Difference Equation for Fibonacci Sequence](https://chunminchang.github.io/blog/post/matrix-difference-equation-for-fibonacci-sequence) 與 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling)
公式如下:
$F_{2k} = F_k(2F_{k+1}-F_k)$
$F_{2k+1} = {F_{k+1}}^2+{F_k}^2$
可以明顯看出兩式皆可由 $F_{k}$ 與 $F_{k+1}$ 推導而出
#### Fast Doubling (recursive 版本)
```c
static long long fast_doubling_recursive(int k)
{
if (k <= 2) {
return k ? 1 : 0;
}
int n = k / 2;
long long a = fast_doubling_recursive(n);
long long b = fast_doubling_recursive(n + 1);
if (k & 1) {
return a * a + b * b;
}
return a * (2 * b - a);
}
```
#### Fast Doubling (iterative 版本)
實作參照以下虛擬碼進行實作:
```c
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;
```
舉 $F(12)$ 為例:
$12$ = $1100_2$
| i | start | 4 | 3 | 2 | 1 | result |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| n | - | **1**100 | 1**1**00 | 11**0**0 | 110**0** | - |
| F(k) | F(0) | F(0*2+1) | F(1*2+1) | F(3*2) | F(6*2) | F(12) |
| a |0|1|2|8|144 | 144|
| b |1|1|3|13|233| - |
時間複雜度為: $O(log N)$
- 當遇到 `0` : 求出 $F_{2k}$ 和 $F_{2k+1}$
- 當遇到 `1` : 先求 $F_{2k}$ 和 $F_{2k+1}$，再求出 $F_{2k+2}$
```c
static long long fast_doubling_iterative(long long k)
{
if (k < 2) {
return k;
}
long long a = 0, b = 1;
for (unsigned int i = 1U << 15; i; i >>= 1) {
long long t1 = a * (2 * b - a);
long long t2 = b * b + a * a;
if (k & i) {
a = t2;
b = t1 + t2;
} else {
a = t1;
b = t2;
}
}
return a;
}
```
#### Fast Doubling (iterative with __builtin_clz())
Fast Doubling 會根據 bit 的值來進行相對應的操作，因此可以先利用 `clz` 去除數字 MSB 起算的開頭 0 位元。
```c
static long long fast_doubling_iterative_clz(long long k)
{
if (k < 2) {
return k;
}
long long a = 0, b = 1;
for (unsigned int i = 1U << (15 - __builtin_clz(k)); i; i >>= 1) {
long long t1 = a * (2 * b - a);
long long t2 = b * b + a * a;
if (k & i) {
a = t2;
b = t1 + t2;
} else {
a = t1;
b = t2;
}
}
return a;
}
```
### 時間測量
#### kernel space
參照作業說明，挪用 `fib_write` 來回傳 kernel space 的執行時間，同時借用 size 參數當作切換的參數，以便於量測不同演算法的執行時間。
```c
/* write operation is skipped */
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
ktime_t kt;
switch (size) {
case 1:
kt = ktime_get();
fib_sequence(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
case 2:
kt = ktime_get();
fast_doubling_recursive(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
case 3:
kt = ktime_get();
fast_doubling_iterative(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
case 4:
kt = ktime_get();
fast_doubling_iterative_clz(*offset);
kt = ktime_sub(ktime_get(), kt);
break;
default:
return 1;
}
return (ssize_t) ktime_to_ns(kt);
}
```
詳閱 [gnuplot 語法解說和示範](https://hackmd.io/@sysprog/Skwp-alOg) 來進行繪圖。
額外寫一個 `compare.c` 與 `fib_compare.gp` 來量測時間。
- write(fd, buf, 1) 回傳 iterative 的執行時間
- write(fd, buf, 2) 回傳 fast_doubling_recursive 的執行時間
- write(fd, buf, 3) 回傳 fast_doubling_iterative 的執行時間
- write(fd, buf, 4) 回傳 fast_doubling_iterative_clz 的執行時間
```c
int main()
{
char write_buf[] = "testing writing";
int offset = 100; /* TODO: try test something bigger than the limit */
int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
for (int i = 0; i <= offset; i++) {
long long t1, t2, t3, t4;
lseek(fd, i, SEEK_SET);
/*iterative*/
t1 = write(fd, write_buf, 1);
/*fast_doubling_recursive*/
t2 = write(fd, write_buf, 2);
/*fast_doubling_iterative*/
t3 = write(fd, write_buf, 3);
/*fast_doubling_iterative_clz*/
t4 = write(fd, write_buf, 4);
printf("%lld %lld %lld %lld\n", t1, t2, t3, t4);
}
close(fd);
return 0;
}
```
```
set title "Fibonacci Compare"
set xlabel "F(n)"
set ylabel "time (ns)"
set terminal png enhanced font "Verdana,12"
set output "Fib_Compare.png"
set xtics 0 ,10 ,100
set key left
set grid
plot [:][:]'test' using 1 with linespoints linewidth 2 title "iterative", \
"" using 2 with linespoints linewidth 2 title "fast doubling recursive", \
"" using 3 with linespoints linewidth 2 title "fast doubling w/o clz", \
"" using 4 with linespoints linewidth 2 title "fast doubling w/ clz", \
```
並執行以下命令
```shell
$ make load
$ sudo taskset -c 7 ./compare > output.txt
$ gnuplot scripts/fib_compare.gp
```
---
### 大數運算
詳讀 [初步支援大數運算](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d#%E5%88%9D%E6%AD%A5%E6%94%AF%E6%8F%B4%E5%A4%A7%E6%95%B8%E9%81%8B%E7%AE%97)
#### `bn` 結構
引入長度可變動的數值表示法，動態配置不同大小的記憶體來呈現更大範圍的整數，將此資料結構定義在 `bn.h` 中。
```c
/* number[size - 1] = msb, number[0] = lsb */
typedef struct _bn {
unsigned int *number;
unsigned int size;
int sign;
} bn;
```
- `number` - 指向儲存的數值，之後會以 array 的形式來取用
- `size` - 配置的記憶體大小，單位為 sizeof(unsigned int)
- `sign` - 0 為正數、1 為負數
#### `bn_to_string`
大數沒辦法直接以數值的形式列出，這裡改用字串來呈現，轉換的部分利用 ASCII 的特性並根據 fast doubling 的邏輯來「組合」出 10 進位字串。
以下詳細探討該程式碼，並理解其運作:
```c=
/*
* output bn to decimal string
* Note: the returned string should be freed with kfree()
*/
char *bn_to_string(bn src)
{
// log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
size_t len = (8 * sizeof(int) * src.size) / 3 + 2 + src.sign;
char *s = kmalloc(len, GFP_KERNEL);
char *p = s;
memset(s, '0', len - 1);
s[len - 1] = '\0';
for (int i = src.size - 1; i >= 0; i--) {
for (unsigned int d = 1U << 31; d; d >>= 1) {
/* binary -> decimal string */
int carry = !!(d & src.number[i]);
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 (src.sign)
*(--p) = '-';
memmove(s, p, strlen(p) + 1);
return s;
}
```
第 8 行: `len` 用於儲存將 `bn` 轉換為十進制字串所需的最大字串長度(Bytes)。
第 9 行: `kmalloc` 是一個動態記憶體配置函式，用於在 Linux 核心中配置記憶體空間。
:::warning
注意用語!
:notes: jserv
:::
Sign in with Wallet
Connect another wallet