# 2023q1 Homework3 (fibdrv)
contributed by < [`chiwawachiwawa`](https://github.com/Chiwawachiwawa) >
## 作業環境
```
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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss
ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art
arch_perfmon pebs bts rep_good nopl xtopology nonstop_
tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cp
l vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1
sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsav
e avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault
epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow
vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust
bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap cl
flushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm
ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp
md_clear flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
Vulnerabilities:
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Mitigation; PTE Inversion; VMX conditional cache flushe
s, SMT vulnerable
Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Meltdown: Mitigation; PTI
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Retbleed: Mitigation; IBRS
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer
sanitization
Spectre v2: Mitigation; IBRS, IBPB conditional, RSB filling, PBRSB-
eIBRS Not affected
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
## 遇到的問題
我在執行
```
make check
```
會遇到一個錯誤
這邊需要進行一個步驟，如果我們是利用 windows 筆電進行重灌 ubuntu ，會因為我們在 bios 預設 secure boot ，會導致錯誤，這邊關閉就好。
## 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作，從中也該理解為何不希望在虛擬機器中進行實驗
### perf
我是依據這篇文章來使用的( [from ncku csie](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) )
這個工具可以來獲取我們機器上的一些數據，並且依照我們給定的權限，來盡可能地算出最直準確的值，
其中會有一些重要的數據需要讀取，例如:
### 為何我們需要在實體機器上面實行實驗，並且測量:
因為我們再進行效能測量時，會需要最直觀的 baer metal 數據，但是如果今天我們使用"虛擬的"機器來進行測量，我們需要對一些維持這個環境所需的程式，這樣會導致我們的硬體，例如 cpu 無法發揮他百分之百的性能，這樣我們透過 PERF 所獲得的數據，必定是不標準的。
我在嘗試使用 ktime 時遇到幾個問題，我操考了其他同學再測量時效時都指定了特定的 CPU 因此我也在實體機器上面嘗試設定成功了，但是我在虛擬機( virtual box )上面無法成功配置。
## 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
## F(92)以後的數值錯誤的原因
我在進行 `make check` 之後遇到跟題目所述一樣的情況，進行到 f(92) 會 fail，
因此要進行改善
```
n96111150@n96111150:~/fibdrv$ make check
make -C /lib/modules/5.19.0-32-generic/build M=/home/n96111150/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.19.0-32-generic'
warning: the compiler differs from the one used to build the kernel
The kernel was built by: x86_64-linux-gnu-gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
You are using: gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
make[1]: Leaving directory '/usr/src/linux-headers-5.19.0-32-generic'
make unload
make[1]: Entering directory '/home/n96111150/fibdrv'
sudo rmmod fibdrv || true >/dev/null
[sudo] password for n96111150:
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory '/home/n96111150/fibdrv'
make load
make[1]: Entering directory '/home/n96111150/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/n96111150/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/n96111150/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/n96111150/fibdrv'
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
#### 修改後的版本
閱讀相關的文章之後，
我的思路是先做出一個版本（不需要使用 big_num ）:
1.先讓這段程式可以使用 fast_doubling 來動
其中我們要盡量使用 clz 指令來進行加速，
```c
static long long fib_sequence(int k)
{
if (k < 2)
return k;
long long first_element = 0;
long long second_element = 1;
long long cover_bits;
for(int i = 31 - __builtin_clz(k); i>=0; --i){
long long temp_1 = first_element * (2 * second_element - first_element);
long long temp_2 = first_element * first_element + second_element * second_element;
long long process_bits = 1UL<<i;
cover_bits = -!!(k&(process_bits));
first_element = (temp_1 & ~cover_bits) + (temp_2 & cover_bits);
second_element = (temp_1 & cover_bits) + temp_2;
}
return first_element;
}
```
程式碼說明：
#### 下一步，使程式可以進行到 f(92)以後
更改完畢之後，我要來處理進一步的優化，
我們來閱讀作業下面關於大數運算的部份，以及可以使 f(92)以後不出現 fail
首先我們要先來找出問題所在。
可以看到我們使用long long 來進行數值的 return，
這樣會導致在 fib(92) 之後產生 overflow，
為了解決這個問題，我要來閱讀另外一個專案 big_num ，並且詳細的內容要來研讀。
### 研讀 big_num 相關檔案
### 依照範例開始改良 bn 的基本操作
### 結構
```c
typedef struct _bn {
unsigned int *digits;
unsigned int size;
int sign;
} bn;
```
### bn_clz
```c
static int bn_clz(const bn *insert)
{
int count = 0;
for (int i = insert->size - 1; i >= 0; i--) {
if (insert->digits[i]) {
count += __builtin_clz(insert->digits[i]);
return count;
} else {
count += 32;
}
}
return count;
}
```
### bn_alloc
```c
bn *bn_alloc(size_t size)
{
bn *new = (bn *) kmalloc(sizeof(bn), GFP_KERNEL);
new->digits = kmalloc(sizeof(int) * size, GFP_KERNEL);
memset(new->digits, 0, sizeof(int) * size);
new->size = size;
new->sign = 0;
return new;
}
```
### bn_free
```c
int bn_free(bn *insert)
{
if (insert == NULL)
return -1;
kfree(insert->digits);
kfree(insert);
return 0;
}
```
### bn_resize
```c
static int bn_resize(bn *insert, size_t size)
{
if (!insert)//if insert is not a ptr
return -1;
if (size == insert->size)
return 0;
if (size == 0)
return bn_free(insert);
insert->digits = krealloc(insert->digits, sizeof(int) * size, GFP_KERNEL);
if (!insert->digits) { // realloc fails
return -1;
}
if (size > insert->size)
memset(insert->digits + insert->size, 0, sizeof(int) * (size - insert->size));
insert->size = size;
return 0;
}
```
### bn_copy
```c
int bn_copy(bn *dest, bn *insert)
{
if (bn_resize(dest, insert->size) < 0)
return -1;
dest->sign = insert->sign;
memcpy(dest->digits, insert->digits, insert->size * sizeof(int));
return 0;
}
```
### bn_bn_to_str
```c
char *bn_to_string(bn insert)
{
// log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
size_t len = (8 * sizeof(int) * insert.size) / 3 + 2 + insert.sign;
char *s = kmalloc(len, GFP_KERNEL);
char *p = s;
memset(s, '0', len - 1);
s[len - 1] = '\0';
for (int i = insert.size - 1; i >= 0; i--) {
for (unsigned int d = 1U << 31; d; d >>= 1) {
/* binary -> decimal string */
int carry = !!(d & insert.digits[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 (insert.sign)
*(--p) = '-';
memmove(s, p, strlen(p) + 1);
return s;
}
```
### bn_cmp
```c
int bn_cmp(const bn *a, const bn *b)
{
if (a->size > b->size) {
return 1;
} else if (a->size < b->size) {
return -1;
} else {
for (int i = a->size - 1; i >= 0; i--) {
if (a->digits[i] > b->digits[i])
return 1;
if (a->digits[i] < b->digits[i])
return -1;
}
return 0;
}
}
```
然後依據範例給的原始程式碼來思考如何優化。
#### 遇到問題
`fatal error: stdio.h: No such file or directory`
我更新了所有能更新的東西，卻還是無法使用，我目前往降級的方向去思考
最優解:直接重灌(老師的話要聽...不要亂用 root)
後來是我犯蠢了，我不該在 kernel 運用 stdio 的，因為 linux/ 底下壓根沒有它...
#### 思路
並且我留下了以下幾個操作
經歷了一陣學習之後，
我做出了以下幾個範例:
這邊我參考了[費波那契數](https://zh.wikipedia.org/zh-tw/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)，這邊我還需要詳加閱讀。
#### 結構
### 各式演算法實現(講解近日補上)
將寫好的 bn.h include 進入我們的程式。
我參考的是這幾篇:
[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number)
Vorobev 等式
重點為:
$f(2n) = 2 \times f(n+1) \times f(n) - (f(n))^2$
$f(2n+1)=(f(n+1))^2 + (f(n))^2$
Vorobev 等式怎麼證？
我們在 n 上作歸納。當 n := 1 和 2 的 case 很容易成立。假設 n:= n+1 的 case 也成立（以下我們把fib簡寫為f）：
```
f (n+1+k) = f n * f k + f (n+1) * f(k+1)
```
我們來證明 n:=n+2
```
f (n+2+k)
= { f 之定義 }
f (n+k) + f (n+k+1)
= { (Vor) & (Vor') }
f (n-1) * f k + f n * f (k+1) +
f n * f k + f (n+1) * f(k+1)
= { f (n+1) = f n + f (n-1) }
f (n+1) * f k + f n * f (k+1) + f (n+1) * f (k+1)
= { f (n+2) = f (n+1) + f n }
f (n+1) * f k + f (n+2) * f (k+1) .
```
並且延伸閱讀提及的文章
[費氏數怎麼算？](https://scm.iis.sinica.edu.tw/ncs/2019/06/how-to-compute-fibonacci/)
普通公式:
```
fib n = (((1+√5)/2)^n - ((1-√5)/2)^n) /√5
```
[論文](https://ir.library.oregonstate.edu/downloads/t435gg51w)
[關於費式數列的那些事](https://yodalee.blogspot.com/2019/02/fibonacci.html)
#### 將 bn 帶入 sequence 之中
```c
void fib_og_bn(bn *target, unsigned int n){
bn_resize(target, 1);
if (n < 2){
target->digits[0] = n;
return;
}
bn *fst_ele = bn_alloc(1);
bn *sec_ele = bn_alloc(1);
target->digits[0] = 1;
for (unsigned int i = 1; i < n; i++){
bn_swap(sec_ele, target);
bn_add(fst_ele, sec_ele, target);
bn_swap(fst_ele, sec_ele);
}
bn_free(fst_ele);
bn_free(sec_ele);
}
```
#### 將 fdouble 與 bn 結合再一起
```c
void fib_fdbbn(bn *target, unsigned int n){
bn_resize(target, 1);
if (n < 2){
target->digits[0] = n;
return;
}
bn *f_k = target;
bn *f_k_next = bn_alloc(1);
f_k->digits[0] = 0;
f_k_next->digits[0] = 1;
bn *k = bn_alloc(1);
bn *k_next = bn_alloc(1);
for (unsigned int i = 1U << 31; i; i >>= 1){
bn_copy(k, k_next);
bn_lshift(k, 1, k);
bn_sub(k, f_k, k);
bn_mult(k, f_k, k);
bn_mult(f_k, f_k, f_k);
bn_mult(f_k_next, f_k_next, f_k_next);
/* f(k)*f(k) + f(k+1)*f(k+1) */
bn_copy(k_next,f_k);
bn_add(k_next, f_k_next, k_next);
if(n & i){
bn_copy(f_k, k_next);
bn_copy(f_k_next, k);
bn_add(f_k_next, k_next, f_k_next);
}
else{
bn_copy(f_k, k);
bn_copy(f_k_next, k_next);
}
}
bn_free(f_k_next);
bn_free(k);
bn_free(k_next);
}
```
#### 將 fdouble 與 clz 結合
```c
static long long fib_sequence_dbc(int k)
{
if (k < 2)
return k;
long long first_element = 0;
long long second_element = 1;
long long cover_bits;
for(int i = 31 - __builtin_clz(k); i>=0; --i){
long long temp_1 = first_element * (2 * second_element - first_element);
long long temp_2 = first_element * first_element + second_element * second_element;
long long process_bits = 1UL<<i;
cover_bits = -!!(k&(process_bits));
first_element = (temp_1 & ~cover_bits) + (temp_2 & cover_bits);
second_element = (temp_1 & cover_bits) + temp_2;
}
return first_element;
}
```
### 效能測試，演算法改寫
參考了作業說明上的程式碼，
由於因為作品中沒有用到 read 還有 write ， 因此我們可以用來測量消耗的時間。
改寫 fib_read
```c
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
bn *fib = bn_alloc(1);
ktime_t k1 = ktime_get();
fib_og_bn(fib, *offset);
ktime_t k2 = ktime_sub(ktime_get(), k1);
char *p = bn_to_string(*fib);
size_t len = strlen(p) + 1;
copy_to_user(buf, p, len);
bn_free(fib);
return ktime_to_ns(k2);
}
```
改寫 fib_write
```c
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
bn *fib = bn_alloc(1);
ktime_t k1 = ktime_get();
fib_fdbbn(fib, *offset);
ktime_t k2 = ktime_sub(ktime_get(), k1);
char *p = bn_to_string(*fib);
size_t len = strlen(p) + 1;
copy_to_user(buf, p, len);
bn_free(fib);
kfree(p);
return ktime_to_ns(k2);
}
```
### fib_sequence_og vs fib_sequence_fd
我們可以看到使用了 fast doubleing 在 n > 20 之後有顯著的速度提升，而使用了非遞迴但也非 fast doubleing
### fib_fd_nclz(遞迴) vs fib_fb_clz
這個實驗是利用未使用大數運算，並且使用了遞迴(也就是常人最直觀的算法)可以看到，使用了 fastdoubling 並且使用了 clz 硬體指令之後，效能差了100倍(而且這樣還是在 n = 93的情況下，如果數字加大，差距會變得更加顯著)
### fib_fdbbn vs fib_og_bn
我發現在一些奇怪的現象（為何會有一些況使得我們的 ns 突然暴漲？）
### fib_fd vs fib_fdbbn
## 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
### user space vs kernel space
### 探討時間暴漲的問題
我們可以看到，在 fast-doubleing-bignumber 時間雖然成長平穩但是使用的時間有時會暴漲，想理解這個問題我需要確認一下 client.c 這個檔案。
我發現問題似乎是出在 copy_to_user 這個東西上面。
#### copy to user
Sign in with Wallet
Connect another wallet