---
tags: linux2023
---
# 2023q1 Homework3 (fibdrv)
contributed by < `Ahsen-lab` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
Stepping: 5
CPU MHz: 2904.002
BogoMIPS: 5808.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 48 MiB
NUMA node0 CPU(s): 0-3
```
## 自我檢查清單
- [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 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 `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)〉
## 作業要求
> [題目](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a)
> [作業要求](https://hackmd.io/@sysprog/linux2023-fibdrv/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux2023-fibdrv-g#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
## 修正 variable-length array (VLA) 警告
若在 Linux module 中使用 variable-length array (VLA) 的機制，編譯過程中會產生警告。因此，為了解決此問題，改用固定大小的陣列來實作求解 Fibonacci 數列的迭代演算法。經修改後，程式碼可以正常編譯和執行。
在新的實作中，迭代演算法從第二項開始進行計算，而不再是從第一項開始。
```diff
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];
+ if (k < 1)
+ return 0;
- f[0] = 0;
- f[1] = 1;
+ long long f[2] = {1, 1};
- for (int i = 2; i <= k; i++) {
- f[i] = f[i - 1] + f[i - 2];
+ for (int i = 2; i < k; i++) {
+ f[1] += f[0];
+ f[0] = f[1] - f[0];
}
- return f[k];
+ return f[1];
}
```
## 支援大數運算
> 參考 [KYG-yaya573142 / fibdrv](https://github.com/KYG-yaya573142/fibdrv)
引入大數運算的實作，用來計算 $fib(92)$ 以後的數值。
### `bn` 結構體
:::spoiler 完整程式碼
```c
/*
* bignum data structure
* number[0] contains least significant bits
* number[size - 1] contains most significant bits
* sign = 1 for negative number
*/
typedef struct _bn {
unsigned int *number;
unsigned int size;
int sign;
} bn;
```
:::
- `number` - 指向儲存的數值，之後會以 array 的形式來取用
- `size` - 配置的記憶體大小，單位為 `sizeof(unsigned int)`
- `sign` - 0 為正數、1 為負數
### `bn_to_string`
> [kmalloc(9)](https://manpages.debian.org/jessie/linux-manual-3.16/kmalloc.9.en.html)
:::spoiler 完整程式碼
```c
/*
* output bn to decimal string
* Note: the returned string should be freed with the kfree()
*/
char *bn_to_string(const 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';
/* src.number[0] contains least significant bits */
for (int i = src->size - 1; i >= 0; i--) {
/* walk through every bit of bn */
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;
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;
}
```
:::
### `bn_fib_fdoubling`
使用 Fast Doubling 的技巧，在大數運算中計算 Fibonacci 數。
:::spoiler 完整程式碼
```c
/*
* calc n-th Fibonacci number and save into dest
* using fast doubling algorithm
*/
void bn_fib_fdoubling(bn *dest, unsigned int n)
{
bn_resize(dest, 1);
if (n < 2) { // Fib(0) = 0, Fib(1) = 1
dest->number[0] = n;
return;
}
bn *f1 = dest; /* F(k) */
bn *f2 = bn_alloc(1); /* F(k+1) */
f1->number[0] = 0;
f2->number[0] = 1;
bn *k1 = bn_alloc(1);
bn *k2 = bn_alloc(1);
/* walk through the digit of n */
for (unsigned int i = 1U << 31; i; i >>= 1) {
/* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
bn_cpy(k1, f2);
bn_lshift(k1, 1);
bn_sub(k1, f1, k1);
bn_mult(k1, f1, k1);
/* F(2k+1) = F(k)^2 + F(k+1)^2 */
bn_mult(f1, f1, f1);
bn_mult(f2, f2, f2);
bn_cpy(k2, f1);
bn_add(k2, f2, k2);
if (n & i) {
bn_cpy(f1, k2);
bn_cpy(f2, k1);
bn_add(f2, k2, f2);
} else {
bn_cpy(f1, k1);
bn_cpy(f2, k2);
}
}
// return f[0]
bn_free(f2);
bn_free(k1);
bn_free(k2);
}
```
:::
- `dest` - 用來儲存 $fib(n)$
- `n` - 找出第 $n$ 個 Fibonacci 數
```c
bn_resize(dest, 1);
if (n < 2) { // Fib(0) = 0, Fib(1) = 1
dest->number[0] = n;
return;
}
bn *f1 = dest; /* F(k) */
bn *f2 = bn_alloc(1); /* F(k+1) */
f1->number[0] = 0;
f2->number[0] = 1;
bn *k1 = bn_alloc(1);
bn *k2 = bn_alloc(1);
```
首先確保 `dest` 的 size 為 1，若 `n < 2` 則 $fib(n) = n$ 。
初始化 `f1` 和 `f2` 為 `0` 和 `1` ，分別對應 $fib(0)$ 和 $fib(1)$ ，再給定兩個變數 `k1` 和 `k2` 分別用來儲存 $fib(k)$ 和 $fib(k + 1)$ 。
$$
\begin{split}
fib(2k) &= fib(k)[2fib(k+1) - fib(k)] \\
fib(2k+1) &= fib(k+1)^2+fib(k)^2
\end{split}
$$
根據上述公式並配合 [Bottom-up Fast Doubling](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d#Bottom-up-Fast-Doubling) 的做法，假設要找第 $n$ 個 Fibonacci 數，只需要從左到右依序檢查每個位元，步驟如下：
1. 計算 `k1 = fib(2k)` 、 `k2 = fib(2k+1)`
2. 檢查當前位元 `i` ，若不存在的話跳到第 3 步，否則（假設目前為 $n = k$）：
- `i = 0` : $n = 2k$
- `f1 = fib(2k) = k1`
- `f2 = fib(2k+1) = k2`
- `i = 1` : $n = 2k + 1$
- `f1 = fib(2k+1) = k2`
- `f2 = fib(2k+2) = k1 + k2`
- 回到第 2 步
3. 此時 $n$ 為目標數，回傳 `f1` 也就是 $fib(n)$
對應的程式碼：
```c
/* walk through the digit of n */
for (unsigned int i = 1U << 31; i; i >>= 1) {
/* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
bn_cpy(k1, f2);
bn_lshift(k1, 1);
bn_sub(k1, f1, k1);
bn_mult(k1, f1, k1);
/* F(2k+1) = F(k)^2 + F(k+1)^2 */
bn_mult(f1, f1, f1);
bn_mult(f2, f2, f2);
bn_cpy(k2, f1);
bn_add(k2, f2, k2);
if (n & i) {
bn_cpy(f1, k2);
bn_cpy(f2, k1);
bn_add(f2, k2, f2);
} else {
bn_cpy(f1, k1);
bn_cpy(f2, k2);
}
}
```
## 量化執行時間
為了分析並改善 Fibonacci 數的計算效率，需要測量並量化執行時間，我們會使用 `fib_read()` 來計算 Fibonacci 數列，使用者可在 user space 透過指定不同的 offest 作為 Fibonacci 數列的 $n$ 然後透過 `read` 來輸出 $fib(n)$。
在計算的過程中，傳入 `fib_read()` 的 `size` 參數並沒有被使用到，因此我將 `size` 當作選擇演算法的參數：
- case 0 :
- 原始迭帶版本的計算方式，因有缺陷，最多只能計算到 $fib(92)$
- case 1 :
- 結合了 Fast Doubling 的大數運算函式 `bn_fib_fdoubling()`
在 `case 1` 中，首先用 `bn_alloc` 創建了一個新的大數 `fib` （用於計算 Fibonacci 數列），然後調用 `bn_fib_fdoubling` 函式來計算第 `*offset` 項的 Fibonacci 數。計算完成後，使用 `bn_to_string` 將結果轉換為字串，並用 `copy_to_user` 將其複製到 user space 的 `buf` 中，最後回傳剩餘的未複製成功的字節數。如果一切正常，該函式回傳 0。
```c
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
bn *fib;
switch (size) {
case 0: /* fib_sequence */
if (*offset > 92)
*offset = 92;
return (ssize_t) fib_sequence(*offset);
case 1: /* bn_fib_fdoubling */
fib = bn_alloc(1);
kt = ktime_get();
bn_fib_fdoubling(fib, *offset);
kt = ktime_sub(ktime_get(), kt);
char *p = bn_to_string(fib);
size_t len = strlen(p) + 1;
k2u = ktime_get();
size_t left = copy_to_user(buf, p, len);
k2u = ktime_sub(ktime_get(), k2u);
bn_free(fib);
kfree(p);
return (ssize_t) left;
}
return 0;
}
```
### Fibonacci 數列計算的時間
在 Linux 核心模組中，使用 ktime 系列的 API 來測量 Fibonacci 數列計算的時間，參考 [核心模式的時間測量](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c#%E6%A0%B8%E5%BF%83%E6%A8%A1%E5%BC%8F%E7%9A%84%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F) 的做法
```c
kt = ktime_get();
bn_fib_fdoubling(fib, *offset);
kt = ktime_sub(ktime_get(), kt);
```
`kt` 為在核心模式下執行 `bn_fib_fdoubling(fib, *offset)` 的時間，首先，在計算之前先用 `ktime_get()` 取得當前時間，在計算完成後，再次呼叫 `ktime_get()` ，用計算後的時間減去計算前的時間，即可得到在核心模式中 Fibonacci 數列計算的時間。
### 從 kernel 傳遞到 user space 的時間
Fibonacci 數列計算的結果會儲存在 `buf` 裡面，需要透過 `copy_to_user` 函式來傳回 user space ， `k2u` 會儲存資料從 kernel 傳遞到 user space 的時間。
```c!
k2u = ktime_get();
size_t left = copy_to_user(buf, p, len);
k2u = ktime_sub(ktime_get(), k2u);
```
這段程式碼的目的是將 Fibonacci 數列計算的結果傳回給 user space，並測量從 kernel 傳遞到 user space 所需的時間。
`copy_to_user` 函式用於將計算結果從 kernel 的記憶體區域 `p` 複製到 user space 的緩衝區 `buf` 中。在這之前，使用 `ktime_get()` 函式獲取當前時間，在傳遞結束之後，再次呼叫 `ktime_get()` 函式，獲取傳遞後時間點，並使用 `ktime_sub()` 函式計算兩者之差，即為從 kernel 傳遞到 user space 所需的時間，儲存在 `k2u` 變數中。
### `read()` 在 user space 的執行時間
`fibdrv` 是一個 character device ，使用者可透過定義相關的函式並使用存取檔案的系統呼叫 (如 `read()`) 來與裝置互動，也就是說使用者空間 ( userspace ) 的程式可透過 `read()` 系統呼叫來得到 `fibdrv` 裝置的輸出。
```c
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
long long sz = read(fd, buf, 1);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
```
在 user space 中，我使用 [`clock_gettime(3)`](https://linux.die.net/man/3/clock_gettime) 函式來計算 `read()` 系統呼叫的執行時間。
```c
#include <time.h>
int clock_gettime(clockid_t clk_id, struct timespec *tp);
```
`clk_id` 參數可用來指定不同的計時器
- `CLOCK_PROCESS_CPUTIME_ID` ： 當前進程在 CPU 上執行的時間。
這個計時器不會包括行程被阻塞的時間，因此可以更好地測量行程的實際執行時間。
具體而言，首先獲取當前時間點，稱為 `start` ，接著執行 `read()` 系統呼叫，獲取讀取的字元數 sz，最後再次使用 `clock_gettime()` 函式獲取當前時間點，稱為 end 時間點。使用 end 減去 start 可得到 read() 系統呼叫在使用者空間中的執行時間。
Sign in with Wallet
Connect another wallet