# 2022q1 Homework3 (fibdrv)
contributed by < `Korin777` >
## Linux 效能分析
### 限定 CPU 給特定的程式使用
1. 在 `/etc/default/grub` 中新增 `isolcpus` 參數
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=1"
```
2. 更新 `/boot/grub/grub.cfg`
```shell
$ sudo update-grub
```
3. 重新開機
4. 檢查是否生效
* 查看 `/proc/cmdline` 裡是否有 `isolcpu` 參數
> korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ cat /proc/cmdline
BOOT_IMAGE=/boot/vmlinuz-5.13.0-30-generic root=UUID=0316da8c-1a94-4511-a7fc-a5133651768b ro quiet splash isolcpus=1 vt.handoff=7
* 最後用 `taskset` 查看 process 的 cpu affinity ， 可以發現它已經不能在第一個 cpu 執行了
> korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~$ taskset -p 1
pid 1's current affinity mask: fd
### 排除干擾效能分析的因素
* 抑制 [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
* `cpufreq` 是一個動態調整 cpu 頻率的模組，系統啟動時生成一個資料夾 `/sys/devices/system/cpu/cpu0/cpufreq/`，裡面有幾個檔案，`scalin_governor` 代表 cpu 頻率調整模式，用它來控制 CPU 頻率 ， 設為 `performance` 表示將 CPU 頻率固定工作在其支援的最高執行頻率上，而不動態調節
```shell
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
sudo echo performance > ${i}
done
```
* 針對 Intel 處理器，關閉 turbo mode
* Intel CPU 有個 [Turbo Boost](https://zh.wikipedia.org/wiki/%E8%8B%B1%E7%89%B9%E5%B0%94%E7%9D%BF%E9%A2%91%E5%8A%A0%E9%80%9F) 功能，當應用程式需要較高的運算效能時，可以以高於額定頻率執行 ， 我們要避免上述情況
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
* 經過以上處理後 ， 比較計算費式數列對時間的作圖 ， 可以發現執行時間比較沒有突然衝很高的情況 ， 可以看作每次測量執行時間都比較沒有被外在因素影響
* Before: 沒有排除效能分析干擾 ， 沒有限定 CPU 只給程式用
* After: 排除效能分析干擾 ， 限定 CPU 只給程式用
## 費氏數列
* 費氏數列 $F(n$) 可透過 $F(n/2)$ 及 $F(n/2+1)$ 求得 ， 而在 $n$ 為奇數及偶數的算法分別如下
* $F(2k)=F(k)[2F(k+1)-F(k)]$
* $F(2k+1)=F(k+1)^2+F(k)^2$
* 當我們有$(a,b) = (F(n/2),F(n/2)+1)$ ，根據上面兩個式子即可算出 $(c,d)=(2 * a * b - a * a,a * a + b * b)$ ， 考慮 $n$ 以下情況
* $n$ 為奇數 => $(c,d)=(F(n-1),F(n))$
* $n$ 為偶數=> $(c,d)=(F(n),F(n+1))$
* 可以發現當 $n$ 為奇數 ， 我們會得到 $F(n-1)$ 及 $F(n)$ ， 因此若要在算出 $F(2n)$ ， 我們得再算出 $F(n+1)$ ， 而 $n$ 為奇數則變為如下
* $n$ 為奇數 => $(d,c+d)=(F(n),F(n+1))$
* 透過上面式子 ， 假設要計算 $F(11)$ ， 我們只要透過 $F(5)、F(6) => F(2)、F(3) => F(1)、F(2)$
* 對照 $F(11)$ ， 11~10~ = 1011~2~
| i | start | 4 | 3 |2|1| result
| -------- | -------- | -------- | -------- |-------- |-------- |-------- |
| n | - | ==1==011 | 1==0==11 | 10==1==1 | 101==1== | - |
| F(n)| F(0) | F(0*2+1)| F(1*2) |F(2*2+1)|F(5*2+1) |F(11)
| F(n) = a | F(0)=0 |1 |1|5|89|89
| F(n+1) = b | F(1)=1 |1|2|8|144
|F(2n),F(2n+1)|-|奇數(d,c+d)|偶數(c,d)|奇數(d,c+d)|奇數(d,c+d)
* 透過以上公式 ， 可以寫出以下程式來計算費伯納西數 `n`
* 可以透過 `63 - __builtin_clzll(n)` 來代替迴圈求出 `n` 要除以 2 多少次才等於 0
```c
unsigned long long fib(unsigned long long n) {
int start = 63 - __builtin_clzll(n);
unsigned long long int bit = 1ULL << (start), a = 0, b = 1,c,d;
while(bit) {
c = 2*a*b - a*a, d = a*a + b*b;
if(n & bit) {
a = d, b = c + d;
}
else {
a = c, b = d;
}
bit >>= 1;
}
return a;
}
```
## 減少乘法運算的成本
* 計算費式數列的過程中 ， 可以發現要求出 `c,d` 需要大量的乘法運算
```c
c = 2*a*b - a*a, d = a*a + b*b;
```
* 運用位移的方式將乘法運算改為加法 ， 可以實作出一個只需要加減及為移的 `fib` 函式
```c
c = (mul(a,b) << 1ULL) - sqare(a), d = sqare(a) + sqare(b);
```
```c
unsigned long long mul(unsigned long long a, unsigned long long b) {
unsigned long long ans = 0ULL;
for(int i = 0 ; i < 64; ++i) {
if(b & (1ULL << i))
ans += a << i;
}
return ans;
}
unsigned long long sqare(unsigned long long x) {
unsigned long long ans = 0ULL;
for(int i = 0 ; i < 64; ++i) {
if(x & (1ULL << i))
ans += x << i;
}
return ans;
}
```
## 大數運算
### 正確計算 $F(93)$ 以及其後的值
在計算 $F(93)$ 時 ， 因為結果超過 64 位元所能表示的數 ， 得定義新的資料結構來儲存 ， 並改寫 `fib_sequence`
```c
struct BigN{
unsigned long long lower, higher;
};
static struct BigN fib_sequence(long long k)
{
struct BigN f[k + 2];
f[0].lower = f[0].higher = f[1].higher = 0;
f[1].lower = 1;
for (int i = 2; i <= k; i++) {
f[i].lower = f[i - 1].lower + f[i - 2].lower;
f[i].higher = f[i - 1].higher + f[i - 2].higher + (f[i].lower < f[i - 1].lower || f[i].lower < f[i - 2].lower);
}
return f[k];
}
```
* 參考 [KYG-yaya573142 的報告](https://hackmd.io/@KYWeng/rkGdultSU#%E5%A4%A7%E6%95%B8%E9%81%8B%E7%AE%97) ， 透過字串的方式 ， 將大數以 10 進位的方式印出來
* 將大數以 2 進位的觀點轉成 10 進位 ， 假設有一 10 進位數 `num` 初始為 0 ， 將大數從高位元到低位元 ， 每次將 `num` 乘以 2 且若遇到 1 就將 `num` 加 1 ， 最後即可將此數轉為 10 進位
* 對照 40~10~ = 101000~2~
| i | start = 6 | 5 | 4 | 3 | 2 |1|result
| -------- | -------- | --------| -------- | -------- | -------- |-------- |-------- |
| n(2進位)|==1==01000 | 1==0==1000 | 10==1==000 | 101==0==00 | 1010==0==0 |10100==0== | - |
| n(10進位)| 0 | 1 | 2 | 5| 10 | 20 | 40
| 下一個數 | 0*2+1| 1*2|2*2+1|5*2|10*2 |20*2|-
* 前兩層 for 迴圈即是將大數從 2 進位轉成 10 進位
* 最後一層 for 迴圈用來找出 10 進位數的開頭
* `kmalloc` 定義於 `linux/slab.h` ， 用來配置核心的記憶體空間
```c
char* displayBigN(struct BigN b) {
char *num = kmalloc(41,GFP_KERNEL);
memset(num,'0',40);
num[40] = '\0';
int carry;
for(unsigned long long i = 1ULL << 63; i; i >>= 1) {
carry = (b.higher & i) > 0;
for(int j = 39; j >= 0; j--) {
num[j] += ((num[j] - '0') + carry);
if(num[j] > '9') {
num[j] -= 10;
carry = 1;
}
else
carry = 0;
}
}
for(unsigned long long i = 1ULL << 63; i; i >>= 1) {
carry = (b.lower & i) > 0;
for(int j = 39; j >= 0; j--) {
num[j] += ((num[j] - '0') + carry);
if(num[j] > '9') {
num[j] -= 10;
carry = 1;
}
else
carry = 0;
}
}
int i = 0;
for(;i < 39 && num[i] == '0';++i);
return &num[i];
}
```
如果我們要用這個資料結構 ， 運用 fast doubling 的手法計算費伯那西數 ， 我們得另外實做用於此資列結構的 `+`,`-`,`*`,`<< 1`
1. `+`
* 先將 `lower` 相加 ， 在將 `higher` 相加並加上 `lower` 的進位
```c
struct BigN* add(struct BigN a, struct BigN b) {
struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL);
c->lower = a.lower + b.lower;
c->higher = a.higher + b.higher + (c->lower < a.lower || c->lower < b.lower);
return c;
}
```
2. `-`
* 將減數取 2 補數再與被減數相加
```c
struct BigN* sub(struct BigN a, struct BigN b) {
struct BigN *c;
b.lower = ~b.lower+1;
b.higher = ~b.higher + (b.lower == 0);
c = add(a,b);
return c;
}
```
3. `*`
* 先將 `lower` 轉型成 `unsigned __int128` 並相乘 ， 避免 overflow ， 結果的較低 64 位元即是新的 `lower` ， 較高 64 位元進位到 `higher`
* 分別將一數的 `higher` 乘以另一數的 `lower` 並相加 ， 在將上之前的進位 ， 即為新的 `higher`
* `higher` 乘以 `higher` 因無法儲存於此資料結構 ， 暫時不處理
```c
struct BigN* mul(struct BigN a, struct BigN b) {
struct BigN *c = kmalloc(sizeof(struct BigN),GFP_KERNEL);
unsigned __int128 tmp = (unsigned __int128)a.lower * (unsigned __int128)b.lower;
c->lower = (unsigned long long)tmp;
c->higher = a.lower * b.higher + a.higher * b.lower + (unsigned long long)(tmp >> 64);
return c;
}
```
4. `<< 1`
* 先將 `higher` 左移並加上 `lower` 的最高位元 ， 在將 `lower` 左移
```c
void lshfit(struct BigN *a) {
a->higher = (a->higher << 1) + (a->lower >> 63 & 1ULL);
a->lower = a->lower << 1;
}
```
* 修改實作 fast doubling 的 `fib`
```c
struct BigN fib(unsigned long long n) {
int start = 63 - __builtin_clzll(n);
unsigned long long int bit = 1ULL << (start);
struct BigN a, b;
struct BigN *v1, *v2, *v3,*c,*d;
a.lower = a.higher = b.higher = 0;
b.lower = 1;
while(bit) {
v1 = mul(a,b);
lshfit(v1);
v2 = mul(a,a);
v3 = mul(b,b);
c = sub(*v1,*v2);
d = add(*v2,*v3);
kfree(v1);
kfree(v2);
kfree(v3);
if(n & bit) {
a = *d, b = *add(*c,*d);
}
else {
a = *c, b = *d;
}
bit >>= 1;
}
return a;
}
```
* 透過這個資料結構 ， 我們可以表示 $0$ ~ $2^{128}-1$ ， 就可以正確計算到 $F(186) = 332825110087067562321196029789634457848$
### 改寫 BigN 來計算更大的費伯納西數
為了計算出更大的費伯納西數 ， 將 `BigN` 的 `higher` 及 `lower` 更改為 `*digits` ， 可以根據我們想儲存的數字大小 ， 動態配置記憶體 ， `size` 則用來表示數字真正用到的 記憶體大小(幾個 unsigned long long)
```c
struct BigN{
unsigned long long *digits;
unsigned long long size;
};
```
* 改寫 `fib_sequence`
* 這裡將 `f[k + 2]` 改為 `f1`,`f2` 及 `tmp` ， `f1`,`f2` 用來保留前兩個費伯那西數 ， `tmp` 則用來更換新的 `f1`,`f2`
```c
static struct BigN* fib_sequence(unsigned long long k)
{
struct BigN *f1, *f2, *tmp;
f1 = malloc(sizeof(struct BigN));
f2 = malloc(sizeof(struct BigN));
f1->digits = malloc(sizeof(unsigned long long));
f2->digits = malloc(sizeof(unsigned long long));
f1->digits[0] = 0;
f1->size = f2->size = f2->digits[0] = 1;
unsigned long long overflow;
for (int i = 2; i <= k; i++) {
int carry = 0;
for(int j = 0; j < f1->size; j++) {
overflow = f1->digits[j];
f1->digits[j] += f2->digits[j] + carry;
carry = f1->digits[j] < overflow;
}
unsigned long long f = 0;
int inc = 1;
if(f1->size != f2->size) {
overflow = f = f2->digits[f2->size-1];
f += carry;
carry = f < overflow;
++inc;
}
if(carry) {
f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+inc));
f1->size += inc;
f1->digits[f1->size-1] = 1;
if(f)
f1->digits[f1->size-2] = f;
}
if(!carry && f) {
f1->digits = realloc(f1->digits,sizeof(unsigned long long) *(f1->size+1));
f1->size += 1;
f1->digits[f1->size-1] = f;
}
tmp = f2;
f2 = f1;
f1 = tmp;
}
if(k==0) {
tmp = f2;
f2 = f1;
f1 = tmp;
}
free(f1->digits);
free(f1);
return f2;
}
```
* 改寫 `displayBigN`
```c
char *displayBigN(struct BigN *b)
{
char *num = kmalloc(sizeof(char) * (b->size * 20) + 1, GFP_KERNEL);
unsigned long long len = sizeof(char) * (b->size * 20) + 1;
memset(num, '0', len);
num[len - 1] = '\0';
int carry;
// convert number from base-2 to base-10
for (int k = b->size - 1; k >= 0; --k) {
for (unsigned long long i = 1ULL << 63; i; i >>= 1) {
carry = (b->digits[k] & i) > 0;
for (int j = len - 2; j >= 0; j--) { // update num
num[j] += ((num[j] - '0') + carry);
if (num[j] > '9') {
num[j] -= 10;
carry = 1;
} else
carry = 0;
}
}
}
// skip leading 0
int i = 0;
for (; i < len - 2 && num[i] == '0'; ++i)
;
char *retnum = kmalloc(sizeof(char) * (len - i), GFP_KERNEL);
memcpy(retnum, &num[i], sizeof(char) * (len - i));
kfree(num);
return retnum;
}
```
1. `+`
```c
struct BigN* add(struct BigN *f1, struct BigN *f2) {
struct BigN *c = malloc(sizeof(struct BigN)), *large, *small;
int carry = 0, j;
if(f1->size > f2->size)
large = f1, small = f2;
else
large = f2, small = f1;
c->digits = malloc(sizeof(unsigned long long)*(large->size+1));
for(j = 0; j < small->size; j++) {
c->digits[j] = small->digits[j] + large->digits[j] + carry;
carry = c->digits[j] < small->digits[j];
}
for(; j < large->size; j++) {
c->digits[j] = large->digits[j] + carry;
carry = c->digits[j] < large->digits[j];
}
c->digits[j] = carry;
c->size = large->size + carry;
return c;
}
```
* 透過 `add` 函式改寫 `fib_sequence`
```c
static struct BigN* fib_sequence(unsigned long long k)
{
struct BigN *f1, *f2, *tmp;
f1 = malloc(sizeof(struct BigN)), f2 = malloc(sizeof(struct BigN));
f1->digits = malloc(sizeof(unsigned long long)), f2->digits = malloc(sizeof(unsigned long long));
f1->digits[0] = 0, f1->size = f2->size = f2->digits[0] = 1;
for(int i = 2; i <= k; i++) {
tmp = add(f1,f2);
free(f1->digits), free(f1);
f1 = f2, f2 = tmp;
}
if(k == 0)
tmp = f2, f2 = f1, f1 = tmp;
free(f1->digits), free(f1);
return f2;
}
```
2. `-`
* 保證 a,b 皆為正數
```c
struct BigN* sub(struct BigN *a, struct BigN *b) {
struct BigN *c, *tmp = malloc(sizeof(struct BigN)), *large, *small;
if(a->size > b->size)
large = a, small = b;
else
large = b, small = a;
tmp->size = large->size, tmp->digits = malloc(sizeof(unsigned long long) * large->size);
// change b to its 2's complement
tmp->digits[0] = ~b->digits[0] + 1;
int i = 1;
for(; i < b->size; ++i)
tmp->digits[i] = ~b->digits[i] + (tmp->digits[i-1] == 0);
for(; i < large->size; ++i)
tmp->digits[i] = ~0ULL;
c = add(a,tmp);
i = large->size - 1;
c->size = 1;
for(; i > 0; --i) {
if(c->digits[i]) {
c->size = i+1;
break;
}
}
free(tmp->digits);
free(tmp);
return c;
}
```
3. `*`
```c
struct BigN* mul(struct BigN *a, struct BigN *b) {
struct BigN *c = malloc(sizeof(struct BigN));
int size = a->size + b->size;
c->digits = malloc(sizeof(unsigned long long)*size);
memset(c->digits,0,sizeof(unsigned long long)*size);
int *carry = malloc(sizeof(int)*size);
memset(carry,0,sizeof(int)*size);
unsigned long long overflow;
for(int i = 0; i < a->size; ++i) {
for(int j = 0; j < b->size; ++j) {
unsigned __int128 tmp = (unsigned __int128)a->digits[i] * (unsigned __int128)b->digits[j];
int index = i+j;
overflow = c->digits[index];
c->digits[index] += (unsigned long long)tmp;
carry[index] += c->digits[index] < overflow;
overflow = c->digits[index+1];
c->digits[index+1] += (unsigned long long)(tmp >> 64);
carry[index+1] += c->digits[index+1] < overflow;
}
}
for(int i = 0; i < size-1; i++) {
overflow = c->digits[i+1];
c->digits[i+1] += carry[i];
carry[i+1] += c->digits[i+1] < overflow;
}
if(c->digits[size-1])
c->size = size;
else
c->size = size -1;
free(carry);
return c;
}
```
4. `<<1`
```c
void lshfit(struct BigN *a) {
int i = a->size - 1;
if(a->digits[i] >> 63 & 1ULL) {
a->size += 1;
a->digits = realloc(a->digits,sizeof(unsigned long long) * (a->size));
a->digits[a->size-1] = 1;
}
for(; i > 0; --i)
a->digits[i] = (a->digits[i] << 1) + (a->digits[i-1] >> 63 & 1ULL);
a->digits[0] <<= 1;
}
```
* 改寫實作 fast doubling 的 `fib`
```c
struct BigN* fib(unsigned long long n) {
struct BigN *a = malloc(sizeof(struct BigN)), *b = malloc(sizeof(struct BigN)), *v1, *v2, *v3, *c, *d;
a->digits = malloc(sizeof(unsigned long long)) , b->digits = malloc(sizeof(unsigned long long));
a->digits[0] = 0;
a->size = b->size = b->digits[0] = 1;
if(n == 0) {
free(b->digits), free(b);
return a;
}
int start = 63 - __builtin_clzll(n);
unsigned long long int bit = 1ULL << start;
while(bit) {
v1 = mul(a,b);
lshfit(v1);
v2 = mul(a,a);
v3 = mul(b,b);
c = sub(v1,v2);
d = add(v2,v3);
free(v1->digits), free(v1), free(v2->digits), free(v2), free(v3->digits), free(v3),
free(a->digits), free(a), free(b->digits), free(b);
if(n & bit)
a = d, b = add(c,d);
else
a = c, b = d;
bit >>= 1;
}
free(b->digits), free(b);
return a;
}
```
* 根據 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) ， `__builtin_clzll` 傳 0 進去為 undefined behavior 所以得特別判斷 `n` 是否為 0
透過這個改寫過的 `BigN` ， `fib_sequence` 及 `fib` 至少能正確計算到 $F(31200)$
### fast doubling 及 sequence 執行時間
* 在 kernel space 測量時間
* 透過 gnuplot 觀察到 sequence 手法執行時間隨著 n 的增大線性成長 ， 而 fast doubling 手法為非線性緩慢上升
### 與 [bignum](https://github.com/0xff07/bignum/tree/fibdrv) 實做比較
* 在 user space 進行 fast doubling 的時間測量
* 在用 gnuplot 繪圖時 ， 發現還是有許多突然衝高的點 ， 後來透過每個 $F(n)$ 都測量 100 次 ， 並取其中最小值後畫出來的圖比較沒有上述情況了
* `bignum` 的實做比我的實做還要快 3 ～ 4 倍
## 回傳核心計算的值給使用者
在費伯那西數大於 `ssize_t` 的情況下 ， 使用者就無法透過 `read` 的回傳值取得它 ， 因此在進行大數運算時，我們得透過 `copy_to_user` 的方式 ， 將大數傳給使用者
* `unsigned long copy_to_user(void *to, const void *from, unsigned long n)`
* `to`:目標地址（使用者空間）
* `from`:源地址（核心空間）
* `n`:將要拷貝資料的位元組數
```c
static ssize_t fib_read(struct file *file,char *buf,size_t size,loff_t *offset)
{
int ret = 0;
struct BigN *n = fib(*offset);
char *num = displayBigN(n);
ret = copy_to_user(buf,num,strlen(num)+1);
kfree(n), kfree(num);
return (ssize_t) ret;
}
```
## 檢查費氏數列正確性
透過 `make check` 我們能檢查我們所求的費氏數列是否正確 ， 並將發生錯誤的地方給印出來
1. 將 MakeFile `@diff -u out scripts/expected.txt && $(call pass)` 註解 ， `expected.txt` 裡的 $fib(93)$ ~ $fib(100)$ 是錯誤的並非我們想要的值
2. 跟據想計算到費伯那西數修改 `fibdrc.c` 的 `MAX_LENG` 、 `client.c` 的 `offset` 及 `verify.py` 的 `range(2, 101)`
```
korin@korin-VivoBook-15-ASUS-Laptop-X542UF:~/Desktop/linux2022/fibdrv$ make check
make -C /lib/modules/5.13.0-30-generic/build M=/home/korin/Desktop/linux2022/fibdrv modules
make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic'
make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic'
make unload
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo rmmod fibdrv || true >/dev/null
rmmod: ERROR: Module fibdrv is not currently loaded
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
make load
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo insmod fibdrv.ko
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
sudo ./client > out
make unload
make[1]: Entering directory '/home/korin/Desktop/linux2022/fibdrv'
sudo rmmod fibdrv || true >/dev/null
make[1]: Leaving directory '/home/korin/Desktop/linux2022/fibdrv'
# @diff -u out scripts/expected.txt && env printf "\e[32;01m Passed [-]\e[0m\n"
f(187) fail
input: 198239973509362327032045173661212819077
expected: 538522340430300790495419781092981030533
```
#### 參考資料
[CPU 優化建議使用 cpupower 設定 CPU Performance 模式](https://www.gushiciku.cn/pl/2iRh/zh-tw)
[isolcpu參數 隔離cpu使其不被自動調度（linux 修改boot參數）](https://www.twblogs.net/a/5d3f74ccbd9eee5174229c27)
Sign in with Wallet
Connect another wallet