---
tags: linux kernel class
---
# 2023q1 Homework3 (fibdrv)
contributed by < `willwillhi1` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.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): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
Stepping: 12
CPU MHz: 2100.000
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4199.88
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 開發紀錄
### 執行 `make check` 遇到的問題
```
$ make check
cc -o client client.c
make -C /lib/modules/5.15.0-52-generic/build M=fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.15.0-52-generic'
CC [M] fibdrv/fibdrv.o
fibdrv/fibdrv.c: In function ‘fib_sequence’:
fibdrv/fibdrv.c:30:5: warning: ISO C90 forbids variable length array ‘f’ [-Wvla]
30 | long long f[k + 2];
| ^~~~
Building modules, stage 2.
MODPOST 1 modules
CC [M] fibdrv/fibdrv.mod.o
LD [M] fibdrv/fibdrv.ko
make[1]: Leaving directory '/usr/src/linux-headers-5.15.0-52-generic'
make unload
make[1]: Entering directory 'fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory 'fibdrv'
make load
make[1]: Entering directory 'fibdrv'
sudo insmod fibdrv.ko
insmod: ERROR: could not insert module fibdrv.ko: Operation not permitted
make[1]: *** [Makefile:23: load] Error 1
make[1]: Leaving directory 'fibdrv'
make: *** [Makefile:37: check] Error 2
```
* 關閉 Secure Boot:
```shell
$ sudo mokutil --disable-validation
```
* 重新開機，選擇 ```Change Secure Boot State```
* 之後就可以正常執行
```
$ make check
make -C /lib/modules/5.15.0-52-generic/build M=/home/will/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.15.0-52-generic'
make[1]: Leaving directory '/usr/src/linux-headers-5.15.0-52-generic'
make unload
make[1]: Entering directory '/home/will/fibdrv'
sudo rmmod fibdrv || true >/dev/null
[sudo] password for will:
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory '/home/will/fibdrv'
make load
make[1]: Entering directory '/home/will/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/will/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/will/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/will/fibdrv'
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
### 實驗環境的設定
* 撰寫 `perfomance.sh`，讓 cpu 只注重效率，將頻率固定在其支持的最高運行頻率上。
```shell
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > ${i}
done
```
* 抑制 `address space layout randomization (ASLR)`，`ASLR` 全名為 `Address Space Layout Randomization` (地址空間佈局隨機化)，它可以將 process 的某些內存空間地址進行隨機化來增加入侵者預測目的地址的難度，從而降低被入侵的風險。
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
* 限定 CPU 給特定的程式使用，修改 ```/etc/default/grub``` 內的 ```GRUB_CMDLINE_LINUX_DEFAULT``` 為 ```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=7"
```，修改完成後需 ```sudo update-grub``` 來更新設定，重開機後即生效
* 可用 ```cat /sys/devices/system/cpu/isolated```
* 或用 ```taskset -cp 1```，來確認是否生效
```shell
$ taskset -cp 1
pid 1's current affinity list: 0-6
```
* 之後用 `taskset -c 7 command` 執行測試程式
## 開發過程
### 前期準備
```shell
cat /sys/class/fibonacci/fibonacci/dev
```
輸出結果代表註冊的 `fibdrv` 的 [Major and Minor Numbers](http://www.makelinux.net/ldd3/chp-3-sect-2.shtml)
```shell
$ cat /sys/class/fibonacci/fibonacci/dev
509:0
```
`509` 代表動態申請的主設備號
也可以用 `ls -l /dev | grep fib` 找到
```
crw------- 1 root root 509, 0 3月 2 15:57 fibonacci
```
* 編譯 `linux kernel moudle`
* 修改完 `fibdrv.c` 後，用 `make all` 來編譯
* 之後先用 `make unload` 移除之前的模組
* 再用 `make load` 載入新編譯後的模組
### fast-doubling 加速 Fibonacci 運算
以下為原始版本的演算法:
```c
static long long easy_fib(int k)
{
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` 實作 `fibonacci`，參考作業說明和 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 的解說。
公式列在下方:
$$
\begin{align}
&F(2k) = 2F(k)\times F(k+1) - F(k)^2 \\
&F(2k+1) = F(k)^2 + F(k+1)^2
\end{align}
$$
修改過後的程式碼:
以 `n = 0b101` 為例，
當迴圈走到最左邊的 1 時(也就是目前總共是 `0b1`)，會先計算 `F(2K)` 和 `F(2K+1)`，之後在用這兩個結果算出 `a = F(2K+1)` 和 `b = F(2K+2) = F(2K) + F(2K+1)`。
接著往右移一位遇到 0，相當於把先前的結果乘二即可(`0b1` -> `0b10`)，也就是 6、7 行。
最後遇到 1，就是將上一步的結果乘二 (`0b10` -> `0b100`)，再加 1 (9 ~ 11 行) 得到 `0b101`。
```c=
static long long double_fib(int n)
{
long long a = 0;
long long b = 1;
for (int i = 31; i >= 0; --i) {
long long c = a * (2 * b - a);
long long d = a * a + b * b;
if ((n >> i) & 1) {
a = d;
b = c + d;
} else {
a = c;
b = d;
}
}
return a;
}
```
其中
```c
for (int i = 31; i >= 0; --i)
```
可以用 `__builtin_clz` 加速
```c
int i = 31 - __builtin_clz(n);
```
這麼做可以不需要每次迴圈都從 `31` 開始，透過 `clz` 可以直接從最高位 `1` 開始做，接下來用 `gunplot` 來製圖
`if-else` 的部份
```c
if ((n >> i) & 1) {
a = d;
b = c + d;
} else {
a = c;
b = d;
}
```
可以用以下程式代替
```c
mask = -!!(n & (1UL << i));
a = (c & ~mask) + (d & mask);
b = (c & mask) + d;
```
* `n & (1UL << i)` 表示只保留 `n` 的第 `i` 個 bit，其餘 `bits` 都是零，而 `-!!` 這個操作可以讓 `mask`:
1. `mask = -1`，如果 n 的第 `i` 個 `bit` 為 `1`
2. `mask = 0`，如果 n 的第 `i` 個 `bit` 為 `0`
最後的程式會是:
```c
static long long fib_sequence(int n)
{
long long a = 0;
long long b = 1;
long long mask;
for (int i = 31 - __builtin_clz(n); i >= 0 ; --i) {
long long c = a * (2 * b - a);
long long d = a * a + b * b;
mask = -!!(n & (1UL << i));
a = (c & ~mask) + (d & mask);
b = (c & mask) + d;
}
return a;
}
```
接下來測試不同實作的時間分佈
`write` 實作 `naive` 版本
`read` 實作 `fast doubling` 版本
```c
static inline long elapse(struct timespec start, struct timespec end)
{
return ((long) 1.0e+9 * end.tv_sec + end.tv_nsec) -
((long) 1.0e+9 * start.tv_sec + start.tv_nsec);
}
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
clock_gettime(CLOCK_REALTIME, &t1);
write(fd, write_buf, strlen(write_buf));
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d ", i);
printf("%ld ", elapse(t1, t2));
clock_gettime(CLOCK_REALTIME, &t1);
read(fd, buf, 1);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%ld\n", elapse(t1, t2));
}
```
然後用 `gunplot` 製圖
> 圖例應為 naive vs. fast doubling
> :notes: jserv
### kernel, user space & system call time
使用作業說明提及的 `ktime` 在核心模組中測量執行時間，實作在 `write` 函式裡，並回傳 `kernel space` 執行時間。
```c
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
ktime_t k1, k2;
k1 = ktime_get();
long long result = double_fib(*offset);
k2 = ktime_sub(ktime_get(), k1);
return ktime_to_ns(k2);
}
```
`user space` 在呼叫 `write` 前後用 `clock_gettime` 計算 `user space` 的時間，最後可以把 `kernel time`, `user time` 相減得到 `system call` 的時間。
```c
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
clock_gettime(CLOCK_REALTIME, &t1);
kernel_time = write(fd, buf, 1);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d ", i);
/* user space execute time */
printf("%ld ", elapse(t1, t2));
/* kernel space execute time */
printf("%ld ", kernel_time);
/* system call overhead between kernel and user space */
printf("%ld\n", elapse(t1, t2)-kernel_time);
}
```
### 大數運算
先看懂 [作業說明的大數運算部份](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)
#### struct bn
使用以下結構體來進行大數運算
* `number` 是儲存整個數值的陣列，以 `unsigned int` 為單位也就是 `32 bits`，由低位元依序存到高位元。
* `size` 代表該陣列的長度。
* `sign` 代表該數為正或負。
```c=
typedef struct _bn {
u8 *number;
unsigned int size;
int sign;
} bn;
```
#### bn_clz
計算 `src` 的陣列的 `leading zero`。
```c
/* count leading zeros of src*/
static int bn_clz(const bn *src)
{
int cnt = 0;
for (int i = src->size - 1; i >= 0; i--) {
if (src->number[i]) {
// prevent undefined behavior when src = 0
cnt += __builtin_clz(src->number[i]);
return cnt;
} else {
cnt += 32;
}
}
return cnt;
}
```
#### bn_to_string
`for` 迴圈要是主要處理轉成二進位轉成十進位字串的地方，每 `32 bits` 處理一次。
* 由 `src->number` 的最高位(msb)逐一放入字串的最高位(msb)並處理。
* 用 `carry` 來代表是否進位，初始化為 `!!(d & src.number[i])`，代表該 `bit` 是否為 `0` 或 `1`。
* `for (int j = len - 2; j >= 0; j--)`，每次累加一個 `bit` 時都要跑整個字串的長度的迴圈。
* 累加的方式為 `s[j] += s[j] - '0' + carry`，原本的數值乘以二再加上 `carry`，最後還要處理進位問題。
```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;
}
```
#### bn_add
`bn_add` 是先用判斷正負號後再依照案例使用 `bn_do_add` 和 `bn_do_sub` 進行無號整數的計算。
```c
/* c = a + b
* Note: work for 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;
}
}
}
```
#### bn_do_add
進行無號整數加法 (c = |a| + |b|)
* `DIV_ROUNDUP(x, len)` 的定義為 `(((x) + (len) -1) / (len))`，簡單來說就是除法無條件進位。
* `!d` 應該不用加，因為 `d` 不可能是 `0`。
* `for` 迴圈部份則是執行簡單的加法。
```c=
/* |c| = |a| + |b| */
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);
}
```
#### bn_do_sub
* `|a| > |b|` 條件一定要成立。
* 由於 `carry` 計算時可能會需要與 `1LL << 32` 相加，超過 `unsigned int` 大小，所以 `carry` 型別要宣告為 `long long int`。
* `(long long int) tmp1 - tmp2 - carry` 結果若小於 `0` 就需要借位。
* 最後 `bn_resize(c, c->size - d)`，把多餘的零去掉。
```c
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);
}
```
#### bn_mult
邏輯就像一般的乘法一樣，慢慢累加上去
另外處理 `c` 有可能是 `a` 或 `b` 的情況，會先用 `tmp` 來存 `c` 原本的位址避免 `a` 或 `b` 的值被改變，等最後做完乘法再 `swap` 回來。
```c
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);
}
}
```
#### bn_lshift
原本的版本程式碼如下，會限制 `shift` 在 `31` 以下，然後根據 `shift` 是否大於 `leading zero` 來判斷重新 `resize dest` 的大小。
```c
/* left bit shift on bn (maximun shift 31) */
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;
}
```
後來我在進行 `10110001000110010010010011100001`(剛好 32 bits) 向左 `shift 1` 時會出錯輸出 `01100010001100100100100111000010`，很明顯是最高位的 `1` 被吃掉了，後來我發現如果 `dest` 被 `resize` 成大小為 `src->size + 1`，需要額外處理 `dest` 陣列的最後一個 `unsigned int` (第三行)。
```c=
if (shift > z) {
bn_resize(dest, src->size + 1);
dest->number[src->size] = src->number[src->size - 1] >> (32 - shift);
} else {
bn_resize(dest, src->size);
}
```
這麼一來 `fast doubling` 需要用到的函式幾乎都有了，接下來就是拿作業說明提供的 `bn_fib_fdoubling` 函式來跑即可。
#### bn_fib_fdoubling 改進
原始版本的 `bn_fib_fdoubling` 為以下：
```c
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);
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, k1);
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);
}
}
bn_free(f2);
bn_free(k1);
bn_free(k2);
}
```
後來利用 `__builtin_clz` 硬體指令可以直接從最高位的 `1` 開始計算，減少迴圈數。
接著為了避免執行 `bn_mult` 的 `(c == a || c == b)` 會用 `tmp` 來儲存 `c` 的情況所以用以下邏輯來避免這個情況。
```c
/* f1 = F(k) */
/* f2 = F(k+1) */
for (unsigned int i = 1U << (31 - __builtin_clz(n)); i; i >>= 1) {
/* F(2k) = F(k) * [ 2 * F(k+1) – F(k) ] */
bn_lshift(f2, 1, k1); // k1 = 2 * F(k+1)
bn_mult(k1, f1, k2); // k2 = 2 * F(k+1) * F(k)
bn_mult(f1, f1, k1); // k1 = F(k) * F(k)
bn_sub(k2, k1, f1); // f1 = F(2k) = 2 * F(k+1) * F(k) - F(k) * F(k)
/* F(2k+1) = F(k)^2 + F(k+1)^2 */
bn_mult(f2, f2, k2); // k2 = F(k+1) * F(k+1)
bn_add(k1, k2, f2); // f2 = F(2k+1) = F(k)^2 + F(k+1)^2
if (n & i) {
bn_swap(f1, f2); // f1 = F(2k+1)
bn_add(f1, f2, f2); // f2 = F(2k+2)
}
}
```
`fib v0` 代表修改前，`fib v1` 代表修改後，由此可見 `bn_alloc()` 的成本是很高的。
#### 減少 `realloc` 次數
為了避免每次呼叫 `bn_resize` 時都會執行 `realloc` 造成對記憶體頻繁的修剪。
在 `bn` 結構體多加入了一個變數 `capacity`，用來事先配置額外的記憶體，所以在每次呼叫 `resize` 時都會先判斷是否還有空間可以使用 `(capacity > resize size)`，若是則可以直接回傳，避免再次執行 `realloc`。
```c=
static int bn_resize_v1(bn *src, size_t size)
{
...
if (src->capacity < size) {
src->capacity = (size+(CHUNK_SIZE-1)) & ~(CHUNK_SIZE-1);
src->number = realloc(src->number, sizeof(unsigned int) * src->capacity);
}
...
}
```
用 `perf` 比較前後結果，計算 `fib(1) ~ fib(10000)`，可以發現 `cache-references` 確實有明顯的下降。
```c=
BRFORE
Performance counter stats for './experiment/exp4' (5 runs):
48,912 cache-misses # 4.071 % of all cache refs ( +- 21.01% )
1,665,299 cache-references ( +- 18.85% )
19,037,748,191 instructions # 2.05 insn per cycle ( +- 0.00% )
9,267,320,914 cycles ( +- 0.07% )
7.06808 +- 0.0124 seconds time elapsed ( +- 0.17% )
---------------------------
AFTER
Performance counter stats for './experiment/exp4' (5 runs):
49,883 cache-misses # 4.824 % of all cache refs ( +- 30.55% )
365,370 cache-references ( +- 98.70% )
19,034,628,079 instructions # 2.05 insn per cycle ( +- 0.00% )
9,255,791,613 cycles ( +- 0.15% )
5.81458 +- 0.00717 seconds time elapsed ( +- 0.12% )
```
#### 用 `verify.py` 驗證
`verify.py` 會產生 `fib(0) ~ fib(想要測量到的範圍)` 並存放在 `expect` 裡，隨後讀取 `out` 並存在 `result`，經過處理後將答案存在 `dice`，
```c
#!/usr/bin/env python3
expect = [0, 1]
result = []
result_split = []
dics = []
for i in range(2, 1001):
expect.append(expect[i - 1] + expect[i - 2])
with open('out', 'r') as f:
tmp = f.readline()
while (tmp):
result.append(tmp)
tmp = f.readline()
f.close()
for r in result:
if (r.find('Reading') != -1):
result_split.append(r.split(' '))
k = int(result_split[-1][5].split(',')[0])
f0 = int(result_split[-1][9].split('.')[0])
dics.append((k, f0))
for i in dics:
fib = i[1]
if (expect[i[0]] != fib):
print('f(%s) fail' % str(i[0]))
print('input: %s' %(fib))
print('expected: %s' %(expect[i[0]]))
exit(1)
```
最後去跟 `expect` 做比較，如果有錯就會輸出類似以下的訊息:
```
f(93) fail
input: -6246583658587674878
expected: 12200160415121876738
```
目前測試到 `1000` 為止答案都是正確的。
```
Reading from /dev/fibonacci at offset 1000, returned the sequence 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
```
觀察 `make check` 時會執行的命令，
發現 `expected.txt` 不會變更到，所以
```shell
@diff -u out scripts/expected.txt && $(call pass)
```
就用 `verify.py` 來驗證，改為以下:
```shell
@scripts/verify.py && $(call pass)
```
且 `verify.py` 裡的 `exit()` 改為 `exit(1)`，代表執行期間有錯誤發生 (與預期答案不符)。
### 測量 user space 和 kernel space 的傳遞時間
原本的大數運算方式是直接在 `kernel space` 執行 `bn_to_string` 將 `bn->number` 轉成字串後通過 `copy_to_user` 將答案傳回 `user space`。
但是實作的大數結構是用一個 `unsigned int` 陣列來表示
* 以 `0xffffffff` 為例，其所需要的空間是 `4 Byte`。
* 轉為十進位是 `4294967295`，因為這邊是用字元表示所以所需空間是 `10 byte`，大於二進位表示時所需的空間。
所以我將傳送的方式改成傳送 `bn->number` 到 `user space` 而不是空間佔用較大的字串，
直接將計算結果透過 `copy_to_user` 傳送。
```c
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
bn *fib = bn_alloc(1);
bn_fib_fdoubling(fib, *offset);
size = fib->size;
copy_to_user(buf, fib->number, sizeof(unsigned int)*size);
bn_free(fib);
return size;
}
```
接著由 `client` 接收，並用修改過後的 `bn_to_str` 將其轉成字串。
```c
char buf[1000];
int offset = 1000; /* 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++) {
lseek(fd, i, SEEK_SET);
unsigned int size = read(fd, buf, 1000);
char *p = bn_to_str(buf, size, 0);
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%s.\n",
i, p);
}
```
最後對 `copy_to_user` 的執行時間做比較，可以發現傳送所花費的時間確實有差，而且數字越大越明顯。
但是這麼做會造成將 `bn` 轉成十進位需要在 `user space` 做相對於在 `kernel space` 還要花時間，~~原因推測是因為 `bn_to_string` 會呼叫到 `malloc` 需要切換到 `Supervisor mode`，導致時間花費會比較高。~~
`malloc` 是 `library function`，底下實際的實作是透過 `sbrk` 或 `mmap`。
:::warning
`malloc` 不是系統呼叫！請善用 perf 一類的工具分析執行成本。
:notes: jserv
:::
後來發現編譯時用 `-O3`，之前沒用的時候導致修改後的 `client` 的 `instructions` 數過多導致執行時間變長。
接著用 `perf` 做比較可以發現兩個方法所花費的時間基本上差不多，但是 `pass_number_array` 相對減少了 `copy_to_user` 的時間，也就是傳送 `bn->number` 到 `user space`，然後在 `user space` 執行 `bn_to_string`。
* pass_number_array
```c=
Performance counter stats for './client' (10 runs):
156.76 msec task-clock # 0.997 CPUs utilized ( +- 0.08% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
83 page-faults # 529.003 /sec ( +- 0.36% )
250,231,871 cycles # 1.595 GHz ( +- 0.08% )
774,286,066 instructions # 3.09 insn per cycle ( +- 0.00% )
61,917,107 branches # 394.631 M/sec ( +- 0.01% )
400,112 branch-misses # 0.65% of all branches ( +- 0.15% )
0.157247 +- 0.000113 seconds time elapsed ( +- 0.07% )
```
* pass_string
```c=
Performance counter stats for './client' (10 runs):
155.82 msec task-clock # 0.946 CPUs utilized ( +- 1.48% )
0 context-switches # 0.000 /sec
0 cpu-migrations # 0.000 /sec
49 page-faults # 299.439 /sec ( +- 0.68% )
248,725,566 cycles # 1.520 GHz ( +- 1.43% )
832,882,929 instructions # 3.22 insn per cycle ( +- 0.04% )
62,446,804 branches # 381.613 M/sec ( +- 0.11% )
400,226 branch-misses # 0.64% of all branches ( +- 0.68% )
0.16468 +- 0.00242 seconds time elapsed ( +- 1.47% )
```
原本以為會有明顯差距，但實際上沒有，
從以上結果可以看到 `malloc` 再執行時沒有呼叫 `system call` 因為沒有做 `context switch`，
所以我後來去查了一些可能的因素，發現 `kmalloc` 和 `malloc` 它們實作上的不同，
`kmalloc` 配置的記憶體是 `physically contiguous` 的，通常用於配置 `128 KB` 以下的空間。
而 `malloc` 拿到的記憶體是 `virtual memory`(也就是物理上不連續的記憶體)，所以當程式去修改這片記憶體時，就有可能會發生 `page fault`。
由以上兩點來看，剛好可以呼應前面的 `perf` 分析的 `page fault` 的結果。
進一步優化 `copy_to_user` 所需要複製的資料大小，目前的算法是陣列多大就複製多大，可優化的地方是最後一個元素的 `leading zero` 是不需要的，所以就只傳送最少所需要的位元組即可。
```c=
int count = 32 - __builtin_clz(fib->number[fib->size-1]);
count = (count >> 3) + !!(count & 0x7);
copy_to_user(buf, fib->number, sizeof(unsigned int) * (len-1) + count);
```
### 使用 `sysfs` 界面
為了取得比用 `printk` 更準確的時間，所以透過 `sysfs` 的界面來存取 `fibdrv` 的執行時間。
[`sysfs` 描述](https://man7.org/linux/man-pages/man5/sysfs.5.html)：
> The sysfs filesystem is a pseudo-filesystem which provides an interface to kernel data structures.(More precisely, the files and directories in sysfs provide a view of the kobject structures defined internally within the kernel.)The files under sysfs provide information about devices, kernel modules, filesystems,and other kernel components.
簡單來說 `sysfs` 可以提供一個界面 (`kobject structures`) 讓 `user space` 可以存取 `kernel` 內的資料結構。
* kobject
* 定義於 [linux/kobject.h](https://elixir.bootlin.com/linux/v2.6.34/source/include/linux/kobject.h#L59)，主要功能有：
* `reference count`
* 管理物件的鏈結串列(集合)，`linux` 風格的 `linked list`，嵌入在別的資料結構中使用
* 將該物件的屬性導出到 `user space`(透過 `sysfs`)
* `kobject` 在 `sysfs` 會以目錄的形式呈現。
* 該物件具有的屬性(`attribute`)會以檔案的方式表示。
* attribute
* 每個 `kobject` 都會有一到多個屬性，每個屬性都代表核心內的某資訊
* 使用者可以通過 `attribute` 中的 `show` 和 `store` callback 函式來取得核心資訊
* 對 `attribute` 進行讀取操作(ex: cat)時會執行 `show`
* 對 `attribute` 進行寫入操作(ex: echo)時會執行 `store`
以下依照[kobject-example.c](https://elixir.bootlin.com/linux/latest/source/samples/kobject/kobject-example.c)的實作
#### 設定 `attribute`
* `__ATTR` 定義在 [`linux/sysfs.h`](https://github.com/torvalds/linux/blob/master/include/linux/sysfs.h) 中：
```c=
#define __ATTR(_name, _mode, _show, _store) { \
.attr = {.name = __stringify(_name), \
.mode = VERIFY_OCTAL_PERMISSIONS(_mode) }, \
.show = _show, \
.store = _store, \
}
```
* 定義 `show`, `store`
* `store`: 利用寫入的方式傳入要算第幾個費氏數列，並將執行時間紀錄在 `kt`。
* `show`: 將 `fibdrv` 內的 `kt` 轉為奈秒後輸出。
```c=
static ssize_t show(struct kobject *kobj,
struct kobj_attribute *attr,
char *buf)
{
kt_ns = ktime_to_ns(kt);
return snprintf(buf, 16, "%lld\n", kt_ns);
}
static ssize_t store(struct kobject *kobj,
struct kobj_attribute *attr,
const char *buf,
size_t count)
{
int ret, n_th;
if (ret = kstrtoint(buf, 10, &n_th)) {
return ret;
}
bn *fib = bn_alloc(1);
kt = ktime_get();
bn_fib_fdoubling(fib, n_th);
kt = ktime_sub(ktime_get(), kt);
bn_free(fib);
return count;
}
```
* 設定 `attribute`
```c=
struct kobject *fib_ktime_kobj;
static ktime_t kt;
static long long kt_ns;
// 設定一個 attribute 叫做 kt_ns，並設定權限為 rw-rw-r--
static struct kobj_attribute ktime_attr = __ATTR(kt_ns, 0664, show, store);
// 定義 kobject 的 attributes，可以有一到多個
static struct attribute *ktime_attrs[] = {
&ktime_attr.attr,
NULL,
};
// 把 attribute 封裝成 attribute_group，之後建立 sysfs 界面時使用
static struct attribute_group ktime_attr_group = {
.attrs = ktime_attrs,
};
```
#### 建立目錄
* 利用 `kobject_create_and_add` 在 `/sys/kernel/` 下建立 `fib_ktime` 目錄。
* 然後用 `sysfs_create_group` 把剛剛建立的屬性放到這個目錄下。
```c
fib_ktime_kobj = kobject_create_and_add("fib_ktime", kernel_kobj);
if (!fib_ktime_kobj)
return -ENOMEM;
int retval = sysfs_create_group(fib_ktime_kobj, &ktime_attr_group);
if (retval)
goto failed_sysfs_create;
```
最後用 `kobject_put` 減少 `reference count`。
```c=
static void __exit exit_fib_dev(void)
{
mutex_destroy(&fib_mutex);
device_destroy(fib_class, fib_dev);
class_destroy(fib_class);
cdev_del(fib_cdev);
unregister_chrdev_region(fib_dev, 1);
kobject_put(fib_ktime_kobj);
}
```
#### 簡單測試
* 測試 `fib(1000)` 的執行時間
```c=
will@will:/sys/kernel/fib_ktime$ sudo sh -c "echo 1000 > kt_ns"
will@will:/sys/kernel/fib_ktime$ sudo cat kt_ns
8838
```
Sign in with Wallet
Connect another wallet