---
title: 2022q1 Homework3 (fibdrv)
description: Linux 核心設計作業 fibonacci character device
---
###### tags: `Linux 核心設計 2022`
# 2022q1 Homework3 (fibdrv)
contributed by < [DokiDokiPB](https://github.com/a1091150/fibdrv) >
### 實驗環境
```
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): 20
On-line CPU(s) list: 0-19
Thread(s) per core: 1
Core(s) per socket: 14
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 154
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
Stepping: 3
CPU MHz: 612.719
CPU max MHz: 6000.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
Virtualization: VT-x
L1d cache: 336 KiB
L1i cache: 224 KiB
L2 cache: 8.8 MiB
NUMA node0 CPU(s): 0-19
```
附註： intel 第 12 代 CPU 可以關閉 E Core
## fibonacci 實作
<!--
### 基本的實作
```c
long long fibseq_basic(long long offset)
{
if (!offset) {
return 0;
}
long long y = 1, z = 1;
for (int i = 2; i < offset; i++) {
long long tmp = y;
y = z;
z = y + tmp;
}
return z;
};
```
-->
### fast doubling method
在 [Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 網誌中，提及 fast doubling 手法
1. $Fib(2k) = Fib(k)[2Fib(k+1) - Fib(k)]$
2. $Fib(2k + 1) = Fib(k+1)^2 + Fib(k)^2$
例如 $Fib(10)$ 的計算過程，以 top-down 方法去觀察
$Fib(10) \rightarrow Fib(5) \rightarrow Fib(2) \rightarrow Fib(1) \rightarrow Fib(0)$
使用第一第二計算方法是取決當下 $Fib(n)$ 的 n 是否為偶數
- $Fib(10) \rightarrow Fib(5)$，使用規則一
- $Fib(5) \rightarrow Fib(2)$，使用規則二
- $Fib(2) \rightarrow Fib(1)$，使用規則一
- $Fib(1) \rightarrow Fib(0)$，使用規則二
使用 bottom-up 手法去觀察其對應關係
> 乘 2 即左移一項 k << 1，因此可以理解為從 F(0) 開始，經過以下 4 個步驟可以得到 F(10)，這也是為何 fast doubling 實作上會根據 bit 來決定計算的步驟
(0000 << 1) + 1 = 0001
(0001 << 1) + 0 = 0010
(0010 << 1) + 1 = 0101
(0101 << 1) + 0 = 1010
>
> 引用自 [KYG-yaya573142 作者](https://hackmd.io/BZjwYw1FQ1O0NPY5kIS7VQ?view#fast-doubling)
| i | start | 4 | 3 | 2 | 1 | result |
|---|-------|----------|----------|----------|---------|--------|
| n | - | ==1==010 | 1==0==10 | 10==1==0 | 101==0== | - |
|F(m) | F(0) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2) | F(10) |
| a | 0 | 1 | 1 | 5 | 55 | 55 |
| b | 1 | 1 | 2 | 8 | 89 | - |
> 圖表引用自 [2022 年 Linux 核心設計/實作課程作業 —— fibdrv - HackMD](https://hackmd.io/@sysprog/linux2022-fibdrv#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97)
引用 Calculating Fibonacci Numbers by Fast Doubling 文章底部的實作
```c
long long fibseq_basic_fast_doubling_branch(unsigned int offset)
{
unsigned long long h = 0;
for (int i = offset; i; i >>= 1, h++)
;
unsigned long long a = 0, b = 1; // fib(0), fib(1)
for (unsigned long long mask = 1 << (h - 1); mask; mask >>= 1) {
unsigned long long c = a * (2 * b - a);
unsigned long long d = a * a + b * b;
if (mask & offset) {
a = d;
b = c + d;
} else {
a = c;
b = d;
}
}
return a;
}
```
使用 ```__builtin_clz``` 的改進實作
```c
long long fibseq_basic_fast_doubling_branch(unsigned int offset)
{
unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
mask >>= __builtin_clz(offset);
unsigned long long a = 0, b = 1; // fib(0), fib(1)
for (; mask; mask >>= 1) {
unsigned long long c = a * (2 * b - a);
unsigned long long d = a * a + b * b;
if (mask & offset) {
a = d;
b = c + d;
} else {
a = c;
b = d;
}
}
return a;
}
```
其中 ```unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);``` 為將最高位元設為 ```1```
使用 bitwise 的技巧，再改寫成以下程式碼
```c
long long fibseq_basic_fast_doubling_branchless(unsigned int offset)
{
unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
mask >>= __builtin_clz(offset);
unsigned long long a = 0, b = 1; // fib(0), fib(1)
for (; mask; mask >>= 1) {
unsigned long long c = a * (2 * b - a);
unsigned long long d = a * a + b * b;
int aset = !(mask & offset);
int bset = !!(mask & offset);
a = d ^ ((c ^ d) & -aset);
b = d + (c & -bset);
}
return a;
}
```
### 在 user space 中測試程式碼
考量上述的 fast doubling 手法，分為是否使用 bitwise 技巧的實作。在 user space 測試是否有差異。
新增 ```fibseq.h, fibseq.c```，用於實作上述使用 branch 與 branchless 的程式碼、新增 ```uclient.c``` ，實作如下：
```c
#include <stdio.h>
#include <time.h>
#include "fibseq.h"
#define NANOSECOND(x) ((x).tv_sec * 1e9 + (x).tv_nsec)
int main()
{
for (int i = 0; i < 1000; i++) {
struct timespec t1, t2, t3;
clock_gettime(CLOCK_MONOTONIC, &t1);
long long ret1 = fibseq_basic_fast_doubling_branch(i);
clock_gettime(CLOCK_MONOTONIC, &t2);
long long ret2 = fibseq_basic_fast_doubling_branchless(i);
clock_gettime(CLOCK_MONOTONIC, &t3);
long long ut = (long long) (NANOSECOND(t2) - NANOSECOND(t1));
long long ut2 = (long long) (NANOSECOND(t3) - NANOSECOND(t2));
printf("%d %lld %lld %d\n", i, ut, ut2, ret1 == ret2);
}
return 0;
}
```
在 MakeFile 中新增 ```make uclient``` 指令
```
uclient: uclient.c fibseq.c
$(CC) -o $@ $^
```
新增 gnuplot 檔案 ```scripts/uclient_plot.gp```
> 參考自 [KYG-yaya573142/fibdrv/plot.gp](https://github.com/KYG-yaya573142/fibdrv/blob/master/scripts/plot.gp)
```
reset
set xlabel 'F(n)'
set ylabel 'time(ns)'
set title 'Fibonacci runtime in userspace'
set term png
set output "uclient_picture.png"
set grid
plot [0:92][0:] \
"uclient_time" using 1:2 with linespoints linewidth 2 pointtype 7 pointsize 0.5 title "fast doubling", \
"" using 1:3 with linespoints linewidth 2 pointtype 7 pointsize 0.5 title "bitwise hack",
```
將以上流程寫成寫入 MakeFile 中，新增 ```make ucheck```：
```
ucheck: uclient
./uclient > ./uclient_time
gnuplot scripts/uclieng_plot.gp
```
最終產生以下圖片，可見在 userspace 中使用 bitwise 技巧比原本的實作多耗時
<!--
參考該範例，去思考此圖的消息
https://hackmd.io/BZjwYw1FQ1O0NPY5kIS7VQ?view#%E5%BF%83%E5%BE%97---%E6%B3%A8%E6%84%8F%E5%AF%A6%E9%A9%97%E8%A8%AD%E7%BD%AE
-->
透過 ```gcc -S fibseq.c``` 輸出 x86_64 的組合語言程式碼，可參考[線上網站 Godbolt Complier Explorer](https://godbolt.org/)
[fibseq_basic_fast_doubling_branchless](https://godbolt.org/z/Kz9j4fb78)
```
# int aset = !(mask & offset);
movl -52(%rbp), %eax
andq -8(%rbp), %rax
testq %rax, %rax
sete %al
movzbl %al, %eax
movl %eax, -44(%rbp)
# int bset = !!(mask & offset);
movl -52(%rbp), %eax
andq -8(%rbp), %rax
testq %rax, %rax
setne %al
movzbl %al, %eax
movl %eax, -48(%rbp)
# a = d ^ ((c ^ d) & -aset);
movq -32(%rbp), %rax
xorq -40(%rbp), %rax
movq %rax, %rdx
movl -44(%rbp), %eax
negl %eax
cltq
andq %rdx, %rax
xorq -40(%rbp), %rax
movq %rax, -16(%rbp)
# b = d + (c & -bset);
movl -48(%rbp), %eax
negl %eax
cltq
andq -32(%rbp), %rax
movq %rax, %rdx
movq -40(%rbp), %rax
addq %rdx, %rax
movq %rax, -24(%rbp)
```
[fibseq_basic_fast_doubling_branch](https://godbolt.org/z/jnqxnGGf4)
```
# if (mask & offset){
# a = d;
# b = c + d;
# }
movl -52(%rbp), %eax
andq -8(%rbp), %rax
testq %rax, %rax
je .L3
movq -40(%rbp), %rax
movq %rax, -16(%rbp)
movq -32(%rbp), %rdx
movq -40(%rbp), %rax
addq %rdx, %rax
movq %rax, -24(%rbp)
jmp .L4
# else {
# a = c;
# b = d;
# }
movq -32(%rbp), %rax
movq %rax, -16(%rbp)
movq -40(%rbp), %rax
movq %rax, -24(%rbp)
```
> 目前初步推論使用 bitwise 技巧產生較多的組合語言程式碼跟更多的計算，導致效能比單純使用 branch 指令來得費時。
> [color=#ff0000]
## 在 user space 實作大數
> 以下程式碼實作在分支 [decnum](https://github.com/a1091150/fibdrv/tree/decnum)，為第二個版本。
> 第一版本 [744e95c3a987a3b5822cd887234d9a667c5d9591](https://github.com/a1091150/fibdrv/tree/744e95c3a987a3b5822cd887234d9a667c5d9591)
> 第二版本 [decnum head](https://github.com/a1091150/fibdrv/tree/decnum) 將 ```malloc``` 從 ```decnum_t``` 函式移除，改進記憶體使用方式
> 為了測試程式碼，先實作於 user space。
### 新增的程式碼
#### 新增 ```decnum.c decnum.h```
新增兩個檔案，用於實作大數 ```struct decnum``` 結構體
#### 新增 ```dclient.c```
```c
#define PRINTDECNUM(a) \
printf("%" PRIu32, (a).digits[((a).size - 1)]); \
for (size_t i = 1; i < (a).size; i++) { \
printf(",%09" PRIu32 "", (a).digits[((a).size - i - 1)]); \
} \
printf("\n");
int main()
{
decnum_t fib = DECNUM_INIT(0, 0);
for (size_t i = 0; i < 100; i++) {
decnum_fast_doubling(i, &fib);
printf("%lu ", i);
PRINTDECNUM(fib);
decnum_free(&fib);
}
return 0;
}
```
隨著大數 ```decnum``` 相關的加法、減法、乘法實作，在每次 git commit 中，皆有 ```dclient.c``` 為對應的程式碼測試。
#### 修改 ```Makefile``` 內容
```diff
+ dclient: dclient.c decnum.c fibseq.c
+ $(CC) -o $@ $^
```
新增 ```dclient``` 用於測試 ```decnum``` 程式碼內容
#### 修改 ```fibseq.h fibseq.c```
在 ```fibseq.h fibseq.c``` 中新增 ```void decnum_fast_doubling``` 函式
### ```decnum.c decnum.h``` 程式碼內容
#### struct decnum 大數結構體
```c
struct decnum {
uint32_t size;
uint32_t cap;
int32_t *digits;
};
typedef struct decnum decnum_t;
#define DECMAXVALUE 1000000000 // 10^9
#define DECNUM_INIT(a, b) \
{ \
.size = (a), .cap = (b), .digits = NULL \
}
```
在原本的作業敘述中，$F_{93}$ 之後的數字會因為 overflow 導致輸出錯誤，採用 ```struct decnum``` 結構體表示一個數字。
- ```size```:紀錄大數的最高位有效位數(非零位數)
- ```cap```: 實際使用 ```malloc``` 的記憶體量
- ```digits```: 表示一個數字。使用 ```int32_t``` 紀錄數字，使用 $10^9$ 進位模式，因此每個位數最大能儲存 $999,999,999$，最小為 $0$
例如以下程式碼，若以 ```decnum``` 要表示 $1,999,999,999$，```digits[0]``` 表示最低位數字，而 ```digits[1]``` 表示第二位數字
```c
decnum_t b1 = DECNUM_INIT(2, 2);
decnum_new(&b1);
b1.digits[0] = DECMAXVALUE - 1;
b1.digits[1] = 1;
```
參考 Fast Doubling 方法
$Fib(2k) = Fib(k)[2Fib(k+1) - Fib(k)]$
$Fib(2k + 1) = Fib(k+1)^2 + Fib(k)^2$
要實作的函式功能為：加法、減法、乘法、平方
以下的實作，程式碼主要分為兩個部份
- 執行函式要求的運算
- 計算後的結果的位數，調整 ```size``` 與 ```cap```
#### decnum_add function 兩個大數加法
```c=
void decnum_add(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
if (!result || !b1 || !b2) {
return;
}
if (b1->size > result->cap || b2->size > result->cap) {
return;
}
decnum_t a1 = DECNUM_INIT(b1->size, b1->cap);
a1.digits = b1->digits;
decnum_t a2 = DECNUM_INIT(b2->size, b2->cap);
a2.digits = b2->digits;
if (b2->size > b1->size) {
decnum_swap(&a1, &a2);
}
if (b1 != result && b2 != result) {
decnum_clean(result);
}
int32_t carry = 0;
for (size_t i = 0; i < a2.size; i++) {
int32_t digit = a1.digits[i] + a2.digits[i] + carry;
carry = digit >= DECMAXVALUE;
result->digits[i] = digit % DECMAXVALUE;
}
if (carry) {
result->size = a2.size;
for (size_t i = a2.size; (i < a1.size) && carry; i++) {
int32_t digit = a1.digits[i] + 1;
result->size += 1;
carry = digit >= DECMAXVALUE;
result->digits[i] = digit % DECMAXVALUE;
}
if ((result->size < result->cap) && carry) {
result->digits[result->size] = 1;
result->size += 1;
}
} else {
result->size = a1.size;
memcpy(result->digits + a2.size, a1.digits + a2.size,
sizeof(int32_t) * (a1.size - a2.size));
}
}
```
因為加法的特性，可以將運算完成的數字直接指派給原本的變數，例如 ```decnum_add(a,b,a)``` 將結果重新指派回 ```a``` ，就不需要新的空間指派。
處理兩數加法運算，將重疊的位數相加。再透過變數 ```carry``` 處理剩餘的位數
#### decnum_sub 兩個大數減法
```c=
void decnum_sub(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
if (!result || !b1 || !b2) {
return;
}
if (b1->size > result->cap || !b1->size || !b2->size) {
return;
}
decnum_t a1 = DECNUM_INIT(b1->size, b1->cap);
a1.digits = b1->digits;
decnum_t a2 = DECNUM_INIT(b2->size, b2->cap);
a2.digits = b2->digits;
if (b1 != result && b2 != result) {
decnum_clean(result);
}
int32_t carry = 0;
for (size_t i = 0; i < a2.size; i++) {
int32_t digit = a1.digits[i] - a2.digits[i] - carry;
carry = digit < 0;
result->digits[i] = digit + (DECMAXVALUE & -carry);
}
for (size_t i = a2.size; i < a1.size; i++) {
int32_t digit = a1.digits[i] - carry;
carry = digit < 0;
result->digits[i] = digit + (DECMAXVALUE & -carry);
}
result->size = a1.size;
size_t i = a1.size - 1;
while (i && !result->digits[i]) {
result->size--;
i--;
}
}
```
在 fast doubling 的計算過程中，$Fib(2k) = Fib(k)[2Fib(k+1) - Fib(k)]$ 用到減法運算，並且 $2Fib(k+1) \geqq Fib(k)$，因此實作中只有考慮 ```decnum_t b1``` 大於 ```decnum_t b2``` 下的減法運算
同樣因為減法的特性，可以將運算完成的數字直接指派給原本的變數，例如 ```decnum_add(a,b,a)``` 將結果重新指派回 ```a``` ，就不需要新的空間指派。
#### decnum_mult function 大數乘法
```c=
void decnum_mult(decnum_t *b1, decnum_t *b2, decnum_t *result)
{
if (!result || !b1 || !b2) {
return;
}
if ((b1->size + b2->size) > result->cap) {
return;
}
decnum_clean(result);
result->size = b1->size + b2->size;
const int32_t size = b1->size + b2->size;
for (size_t i = 0; i < b1->size; i++) {
for (size_t j = 0; j < b2->size; j++) {
int64_t carry =
((int64_t) b1->digits[i]) * ((int64_t) b2->digits[j]);
size_t k = i + j;
do {
uint64_t vv = carry + result->digits[k];
result->digits[k] = vv % DECMAXVALUE;
carry = vv / DECMAXVALUE;
k++;
} while ((k < size) && carry);
}
}
size_t i = result->size - 1;
while (i && !result->digits[i]) {
result->size--;
i--;
}
}
```
在第 21 ~ 26 行中，因為乘法的特性，會向更高位數傳遞 ```carry```，因此不能重新指派數值給原有的變數。
#### decnum_multi_by_two function 兩倍乘法
```c=
void decnum_multi_by_two(decnum_t *b1)
{
if (!b1) {
return;
}
for (size_t i = 0; i < b1->size; i++) {
b1->digits[i] <<= 1;
}
int32_t carry = 0;
for (size_t i = 0; i < b1->size; i++) {
int32_t digit = b1->digits[i] + carry;
b1->digits[i] = digit % DECMAXVALUE;
carry = digit / DECMAXVALUE;
}
if (carry && (b1->size < b1->cap)) {
b1->digits[b1->size] = carry;
b1->size++;
}
}
```
提供大數一個乘以 2 的實作
### 使用大數搭配 Fast Doubling
#### decnum_fast_doubling 函式
```c=
void decnum_fast_doubling(unsigned int offset, decnum_t *result)
{
if (!result) {
return;
}
const float factor = 42.25;
unsigned int sp = (((float) offset) / factor) + 2;
decnum_t a = DECNUM_INIT(1, sp);
decnum_new(&a);
if (!a.digits) {
goto fa;
}
decnum_t b = DECNUM_INIT(1, sp);
decnum_new(&b);
if (!b.digits) {
goto fb;
}
decnum_t tmp = DECNUM_INIT(1, sp);
decnum_new(&tmp);
if (!tmp.digits) {
goto ft;
}
decnum_t tmp2 = DECNUM_INIT(1, sp);
decnum_new(&tmp2);
if (!tmp2.digits) {
goto ft2;
}
decnum_clean(&a);
decnum_clean(&b);
decnum_clean(&tmp);
decnum_clean(&tmp2);
a.size = 1;
a.digits[0] = 0;
b.size = 1;
b.digits[0] = 1;
unsigned long long mask = ULLONG_MAX ^ (ULLONG_MAX >> 1);
mask >>= __builtin_clz(offset);
for (; mask; mask >>= 1) {
if (mask & offset) {
// A = (a + b)^2 - 2ab = a^2 + b^2
decnum_add(&a, &b, &tmp);
decnum_mult(&tmp, &tmp, &tmp2);
decnum_mult(&a, &b, &tmp);
decnum_multi_by_two(&tmp);
decnum_sub(&tmp2, &tmp, &tmp);
// B = (a + b)^2 - a^2
decnum_mult(&a, &a, &b);
decnum_sub(&tmp2, &b, &b);
decnum_assign(&a, &tmp);
} else {
// B = a^2 + b^2
decnum_mult(&a, &a, &tmp);
decnum_mult(&b, &b, &tmp2);
decnum_add(&tmp, &tmp2, &tmp2);
// A = a * (2 * b - a)
decnum_multi_by_two(&b);
decnum_sub(&b, &a, &b);
decnum_mult(&b, &a, &tmp);
decnum_assign(&b, &tmp2);
decnum_assign(&a, &tmp);
}
}
decnum_free(&tmp);
decnum_free(&tmp2);
decnum_free(&b);
decnum_swap(result, &a);
return;
ft2:
decnum_free(&tmp);
ft:
decnum_free(&b);
fb:
decnum_free(&a);
fa:
return;
}
```
**神秘的數字 42.25**
透過觀察 $fib(x)$在 ```decnum_t``` 實作，將輸出的 ```decnum_t size``` 除以 $x$ 會得出一組穩定的數字 ，例如 $x$ 取以下範圍
- $0 \backsim 44$：需要 1 個 ```int32_t```
- $45 \backsim 87$：需要 2 個 ```int32_t```
- $950 \backsim 992$：需要 23 個 ```int32_t```， 950 / 23 = 41.304、992 / 23 = 43.130
- $34842 \backsim 34884$：需要 810 個 ```int32_t```， 34842 / 810 = 43.066、1035 / 24 = 43.148
選出一個 magic number：$42.25$，將 $\lfloor x/42.3 \rfloor + 2$ 作為每次使用 ```malloc``` 的大小
第 52 ~ 77 行中，只能使用 ```a```, ```b```, ```tmp```, ```tmp2``` 四個變數去取得計算結果，並且盡量不使用乘法實作。
### 確認輸出
使用 ```make dclient``` 確認輸出
```
0 0
1 1
2 1
3 2
4 3
5 5
6 8
...
91 4,660046610,375530309
92 7,540113804,746346429
93 12,200160415,121876738
94 19,740274219,868223167
95 31,940434634,990099905
96 51,680708854,858323072
97 83,621143489,848422977
98 135,301852344,706746049
99 218,922995834,555169026
```
交叉比對後，列出到 $Fib(99)$ 皆為正確的數字。
## 將大數程式碼移植成 kernel space 版本
> 以下程式碼實作於 [```kdecnum```](https://github.com/a1091150/fibdrv/tree/kdecnum) 分支
### 移植的程式碼
#### 新增 ```kdecnum.h kdecnum.c``` 檔案
- 原本用於 user space 中的 ```decnum_t``` 加上前綴 ```k```，改名成 ```kdecnum_t```
- 將相關的函式名稱也加入前綴，例如 ```void decnum_new(decnum_t *ptr)``` 改成 ```void kdecnum_new(kdecnum_t *ptr)```
- ```malloc``` 改為 ```kmalloc```, ```free``` 改為 ```kfree```, ```realloc``` 改為 ```krealloc```
#### 修改 ```Makefile``` 檔案
```diff
- TARGET_MODULE := fibdrv
+ TARGET_MODULE := fibdrv_new
obj-m := $(TARGET_MODULE).o
- $(TARGET_MODULE)-objs := fibdrv.o
+ $(TARGET_MODULE)-objs := fibdrv.o kdecnum.o
...
+ eclient: eclient.c
+ $(CC) -o $@ $^
```
- 修改 TARGET_MODULE 名稱，避免使用 ```make``` 指令時發生錯誤
- 使用 ```eclient.c``` 測試 fibonacci driver
#### 修改 ```fibdrv.c```
- 原本實作於 ```fibseq.c``` 的 ```decnum_fib_fast_doubling``` 函式移植到 ```fibdrv.c``` 中
- 修改原本 ```fibdrv.c``` 中 ```ssize_t fib_read```，將 ```b1.digits``` 大數數值指派給 ```buf```
- ```#define MAX_LENGTH 92``` 改為 ```#define MAX_LENGTH 150```
```c
#define MAX_LENGTH 150
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
kdecnum_t b1 = KDECNUM_INIT(0, 0);
int res = decnum_fib_fast_doubling(*offset, &b1);
size_t ss = min(size, b1.size * sizeof(int32_t));
access_ok(buf, ss);
res = copy_to_user(buf, b1.digits, ss);
kdecnum_free(&b1);
return res;
}
```
> 參考 [K04: fibdrv](https://hackmd.io/@sysprog/linux2022-fibdrv#%E9%97%9C%E6%96%BC-clientc)
> 核心驅動裝置不能直接寫入該硬體，需透過 ```copy_to_user``` 方能將數值內容複製，使得 client 端接收。
剛開始撰寫程式碼時，我使用以下程式碼，導致 Ubuntu 系統螢幕顯示卡頓，即使是只有一行也是卡頓。意外的是系統沒有崩潰。
```c
buf[0] = b1.digits[0] & 0xFF;
```
#### 修改 ```eclient.c```
```c
#define BUFSIZE 8
int main()
{
long long sz;
int32_t buf[BUFSIZE];
memset(buf, 0, sizeof(int32_t) * BUFSIZE);
int fd = open(FIB_DEV, O_RDWR);
if (fd < 0) {
perror("Failed to open character device");
exit(1);
}
lseek(fd, 99, SEEK_SET);
sz = read(fd, buf, BUFSIZE * sizeof(int32_t));
decnum_t fib = DECNUM_INIT(BUFSIZE, BUFSIZE);
fib.digits = buf;
PRINTDECNUM(fib);
close(fd);
return 0;
}
```
在實作上幾乎與原本的 ```client.c``` 相同
## 時間成本計算
<!--
> 參考的實作為 [sysprog21/bignum](https://github.com/sysprog21/bignum)
-->
> 以下實作於 [```timemeasure```](https://github.com/a1091150/fibdrv/tree/timemeasure) 分支
### 修改的程式碼
> 以下實作的版本為 [```timemeasure 60268ca7215f84a3f0a973d05f7fda03bab3f2f5```](https://github.com/a1091150/fibdrv/tree/60268ca7215f84a3f0a973d05f7fda03bab3f2f5)
將 ```fibdrv.c``` 的程式碼的回傳改為計算 ``` decnum_fib_fast_doubling``` 需要的時間，單位為 nano second
```diff
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
kdecnum_t b1 = KDECNUM_INIT(0, 0);
+ ktime_t kk = ktime_get();
int res = decnum_fib_fast_doubling(*offset, &b1);
+ kk = ktime_sub(ktime_get(), kk);
+ ssize_t dd = ktime_to_ns(kk);
size_t ss = min(size, b1.size * sizeof(int32_t));
access_ok(buf, ss);
res = copy_to_user(buf, b1.digits, ss);
kdecnum_free(&b1);
- return res;
+ return dd;
}
```
在尚未移除影響效能的因素下，多次使用指令 ```make eclient``` 計算 $Fib(99)$，可得到以下輸出
```
28713
28342
34695
30788
30795
```
### 移除影響效能分析的因素
<!--
> 參考 [2022 年 Linux 核心設計/實作課程作業 fibdrv Linux 效能分析的提示 - HackMD](https://hackmd.io/@sysprog/linux2022-fibdrv#-Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA)
-->
#### 使用 taskset 指定 CPU 核心上執行程式(指定 19)
> cpu19 為 Intel effective core，用途為省電，使用 Performance core 在執行時間上較短
> 以下實作為 [```timemeasure 719aa1ef02dc949dbd4c65979a2698ae726acdc9```](https://github.com/a1091150/fibdrv/tree/719aa1ef02dc949dbd4c65979a2698ae726acdc9)
在 ```Makefile``` 中新增測試流程
```diff=
eall: all eclient
$(MAKE) unload
$(MAKE) load
- sudo ./eclient > ./eclient_time
+ sudo taskset -c 1 ./eclient > ./eclient_time
gnuplot scripts/eclient_plot.gp
```
在多次執行 ```make eall``` 後，無論是否使用第四行或是第五行程式碼所繪製的圖片，皆有週期性的跳動
或是遠高於平均、低於平均的數值
#### 設定 intel turbo mode、 抑制 ASLR、區隔指定的 CPU
> 參考 [2022 年 Linux 核心設計/實作課程作業 fibdrv Linux 效能分析的提示，保留特定的 CPU](https://hackmd.io/@sysprog/linux2022-fibdrv#%E9%99%90%E5%AE%9A-CPU-%E7%B5%A6%E7%89%B9%E5%AE%9A%E7%9A%84%E7%A8%8B%E5%BC%8F%E4%BD%BF%E7%94%A8)
> 參考 [grub2 - How do I add a kernel boot parameter? - Ask Ubuntu](https://askubuntu.com/questions/19486/how-do-i-add-a-kernel-boot-parameter)
> 參考 [What is the difference between GRUB_CMDLINE_LINUX and GRUB_CMDLINE_LINUX_DEFAULT in /etc/default/grub](https://askubuntu.com/questions/575651/what-is-the-difference-between-grub-cmdline-linux-and-grub-cmdline-linux-default)
在 ```/etc/default/grub``` 檔案中加入 ```GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=19"```，並且 ```sudo update-grub```
並修改 ```Makefile```
```
performance:
# cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
sudo sh scripts/performance.sh
powersave:
# cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
sudo sh scripts/powersave.sh
noturbo:
sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
noaslr:
sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
irqaffinity:
sudo sh scripts/changeIRQAffinity.sh
eall: all eclient noturbo noaslr performance irqaffinity
$(MAKE) unload
$(MAKE) load
sudo taskset -c 19 ./eclient > ./eclient_time
gnuplot scripts/eclient_plot.gp
```
使用 ```make eall``` 後，產生以下圖片
好像什麼沒變化
## 檢查實驗因素
在這次作業中，我使用 [@KYWeng 的筆記](https://hackmd.io/@KYWeng/rkGdultSU) 作為對照組去檢驗我的實作。忽略第 0 ~ 5 次的 $Fib(99)$ 計算，並顯示於以下圖片，此實驗獲得平穩的結果，表示確實移除影響效能分析的因素。
### ftrace and trace-cmd
使用 [```trace-cmd```](https://man7.org/linux/man-pages/man1/trace-cmd.1.html) 追蹤我的實作：使用 ```sudo trace-cmd record --max-graph-depth 1 -e all taskset -c 19 ./eclient > ./eclient_time```，並將結果輸出為下圖。執行時間驚人的增加 7 倍。
使用 ```trace-cmd report``` 輸出的報告如下
```
eclient-9916 [019] 1781.863070: kmalloc: (kdecnum_new+0x23) call_site=kdecnum_new ptr=0xffff8fe002e101a0 bytes_req=4 bytes_alloc=8 gfp_flags=GFP_KERNEL
eclient-9916 [019] 1781.863070: kfree: (kdecnum_free+0x17) call_site=kdecnum_free ptr=0xffff8fe002e10118
eclient-9916 [019] 1781.863070: kfree: (kdecnum_free+0x17) call_site=kdecnum_free ptr=0xffff8fe002e10b10
...
```
然而同樣的使用 ftrace 追蹤 @KYWeng 的實作，卻是沒有變化(下圖)
在觀察 ```trace-cmd report``` 輸出的報告後，我注意到我的實作在每次加法、減法、乘法、都會使用 ```kmalloc``` 並且很快就 ```kfree```，因 ftrace 追蹤行為導致在執行時間大幅增加。
對比於 @KYWeng 的實作輸出的報告，出現 ```kmalloc```, ```kfree``` 的頻率不多，參照其程式碼的實作中，使用 ```krealloc``` 而不是多次使用 ```kmalloc```
## 減少大數運算的時間成本
### 第一次改進
這一次的修改包含
- 修改大數系統的加法、減法、乘法函式，可參考 [master b3960dd6260b28872978d53720d1c66c4139b01f](https://github.com/a1091150/fibdrv/tree/b3960dd6260b28872978d53720d1c66c4139b01f)
- 修改記憶體使用方式，使用 magic number 42.25 配置指定大小的記憶體。在 Linux driver 版本中，不能使用浮點數，因此採用 42 作為計算數值。
改進之後產生的輸出圖片如下：
成為穩定執行時間成本的線段 38000 ns 下降至 11500 ns
### 第二次改進(使用 perf)
參考 [@KYWeng perf](https://hackmd.io/@KYWeng/rkGdultSU#perf) 說明
```
sudo perf record -g --call-graph dwarf ./eclient
sudo perf report --stdio -g graph,0.5,caller
```
取得以下結果(省略部份輸出)，可以得出實作中乘法與 ```memset_erms``` 指令絕大多數執行時間
```
59.11% 0.00% eclient eclient [.] main
|
---main
__GI___read (inlined)
entry_SYSCALL_64_after_hwframe
do_syscall_64
__x64_sys_read
ksys_read
vfs_read
fib_read
|
|--29.81%--kdecnum_mult
|
--29.30%--memset_erms
```
使用 ```sudo perf stat -r 10 -e cycles,instructions,cache-misses,cache-references,branch-instructions,branch-misses ./eclient``` 取得以下輸出， ```cpu_core/cache-misses/``` 佔去 59.19%
```
Performance counter stats for './eclient' (10 runs):
205,8354 cpu_core/cycles/ ( +- 1.36% )
<not counted> cpu_atom/cycles/ (0.00%)
426,1798 cpu_core/instructions/ ( +- 0.11% )
<not counted> cpu_atom/instructions/ (0.00%)
2274 cpu_core/cache-misses/ ( +- 52.19% )
<not counted> cpu_atom/cache-misses/ (0.00%)
1,9000 cpu_core/cache-references/ ( +- 7.76% )
<not counted> cpu_atom/cache-references/ (0.00%)
81,7867 cpu_core/branch-instructions/ ( +- 0.12% )
<not counted> cpu_atom/branch-instructions/ (0.00%)
6047 cpu_core/branch-misses/ ( +- 7.44% )
<not counted> cpu_atom/branch-misses/ (0.00%)
0.0011872 +- 0.0000302 seconds time elapsed ( +- 2.54% )
Some events weren't counted. Try disabling the NMI watchdog:
echo 0 > /proc/sys/kernel/nmi_watchdog
perf stat ...
echo 1 > /proc/sys/kernel/nmi_watchdog
```
Sign in with Wallet
Connect another wallet