# 2020q1 Homework4 (kcalc)
contributed by < `eecheng87` >
###### tags: `linux2020`
# 自我檢查清單
## 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
### Linux Kernel Load Average 計算分析
事實上，作業說明提供的連結已經把相關的程式碼都分類好了，所以可以很直接的看到 Linux 核心如何使用定點數。以下統整連結的內容和補充沒提到的細節。
首先，Load Average 顧名思義就是要查看近期的負載平均，近期可分成三種時間間隔。而計算的公式如下：
$load_t = n \times \alpha + (1- \alpha) \times load_{t-1}$
這個公式其實很常見，在作業系統決定下一個 cpu burst 時就會套這個 [Exponential average](https://www.geeksforgeeks.org/shortest-job-first-cpu-scheduling-with-predicted-burst-time/) 公式。這個公式的好處是簡單且省記憶體的把過去的**歷史資料**都記住，而且會 aging。而很明顯的，這個公式的計算絕對牽涉的浮點數運算，而 kernel 是不能做浮點運算的，所以定點運算就派上用場了。
### Fixed Point Arithmetis for RT-Linux
[這是](http://netwinder.osuosl.org/pub/netwinder/docs/nw/rt_fixed/doc/html/rt_fix.html) linux 中另外一個定點運算的例子，和前者不一樣的是，這個專案實做了自己的 API，此外定義的定點數格式也和前者不同。詳細內容和 MathEx 實做的定點數將於文末討論。
## MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
先從 `test-simple.c` 下手，觀察如何運算出結果。
```cpp=19
int main()
{
const char *s = "x1 = 40, add(2, x1)";
struct expr_var_list vars = { 0 };
struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
if (!e) {
printf("Syntax error");
return 1;
}
float result = expr_eval(e);
```
我們可以觀察到，要透過 expression 得到結果須經過
* 將用 string 表示的 expression 轉成正規的格式 ( 透過 `expr_var_list` )
* 由上個步驟得到的 list 運算出結果
接著打開 `expression.c` 觀察 `expr_create` 的實做方式：
```cpp=502
for (;;) {
int n = expr_next_token(s, len, &flags);
```
首先把目前**剩下的**表示式傳入 `expr_next_token`，則 `n` 會得到下一個合理的 token 結尾的位置，透過 `n` 來取得 `char* token` 且記得維護新的**剩下的**表示式。( 關於 `expr_next_token` 是如何實做的，稍後會詳細說明 )
接著從 572 行開始就是判斷剛剛得到的 token 應該屬於那一個種類，並把不同類的 token 中的資料拿出來維護，以下說明面對不同類型 token 會做的事：
* 573 行的 else block 是處理遇到左括號 '(' 的區塊，左括號的添加又分成兩種情況
* 允須加：顧名思義，可有可無，交給使用者決定。
* 必須加：當 call function 後，預期緊接著的是左括號，e.g. `add(...`。
* 588 行的 else block 是處理遇到右括號 ')' 的區塊，簡單說明這個區塊該考慮什麼事：
* `while (vec_len(&os) > minlen ..`
* `if (str.n == 1 && *str.s == '{')` 當已經呼叫函數和讀完參數後，現在讀到 ')' 則進入。
* 686 行的 else block 是處理常數的區塊，並將數字包裝後 append 到 `es` 尾巴。
* 689 行的 else block 是處理 operand 的區塊，而定義的 operand 在 `expr_type` 中，只要不是 `OP_UNKNOWN` 一律進這個 block。但比較特別的地方是，逗號 comma 也有被定義在 `expr_type` 中。這個符號特別的地方在他有可能出現在用來區隔函數內的參數，若是這種情況，可以在 `for(;;;)` 的第一個 `if` 內看到，並且更新資料結構 `as`。
* 719 行的 else block 是處理**變數名稱**或**函數名稱**，在這個 block 只會紀錄 id 和 id 的長度。接著在下一個 iterate 的 543 行我們才會透過 `expr_var` 將這個新的變數包裝起來，並且 append 到 `es` 的尾端。若 id 是函數名稱，如：`add`。則會進 `if (n == 1 && *tok == '(') ..` ，內部會有 `expr_func(funcs, id, idn)` 檢查是否有這個 function name ( 有什麼 function name 是由 user 決定，透過傳入的參數 `funcs` )，有的話把 function name 放到 `os`，反之則報錯。
## 在 MathEx 中，nop 一類使用者自訂的函數如何實作呢？
當需要額外新增自定義函數時可以透過添加項目到 `struct expr_func user_funcs[]` 中，其中第一個成員要填這個函數的代稱，再來需要填實作的 function name。
舉例來說，若我想新增 fib，而 fib 的實作是 `int fibonacci(...)`，那應該這麼填 :
```cpp
static struct expr_func user_funcs[] = {
{"fib", user_fib, NULL, 0},
};
```
這個陣列在進入 `expr_create` 時會傳入，用來檢查表示式中是否有包含自定義的函數。在 905 行可以發現
```cpp=905
struct expr_func *f = expr_func(funcs, str.s, str.n);
```
將 `user_funcs` 傳入 `expr_func` 做檢查，檢查 `user_funcs` 中是否含有表示式中呼叫的函數。若有的話回傳那個 function 的資料。 `expr_func` 的實作如下:
```cpp
struct expr_func *expr_func(struct expr_func *funcs, const char *s, size_t len)
{
for (struct expr_func *f = funcs; f->name; f++) {
if (strlen(f->name) == len && strncmp(f->name, s, len) == 0)
return f;
}
return NULL;
}
```
可以清楚看到，是在做名字匹配的檢測。若找不到當然回傳 NULL。
## 是否發現 MathEx 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？
參考 RT-Linux 實做乘法時，也有考慮到 overflow 和 underflow 的狀況。
```cpp
if(iwl > RT_FIXWL) {
if(rt_fix_sign(x) ^ rt_fix_sign(y)) {
x = rt_fix_min;
} else {
x = rt_fix_max;
}
rt_fix_errmergeset(&x, y);
rt_fix_erraddset(&x, RT_FIX_OV);
return x;
}
```
`iwl` 是類似乘數和被乘數相加的值，用這個值判斷是否超過 `RT_FIXWL`，即 31 bit。如果超過，就是溢位。再來透過 XOR 來檢查兩者的 sign bit ，藉此判斷是 overflow 或是 underflow。
## 整合 fibdrv 到 calc
目前專案 kcalc 的狀況是已經引入 MathEx 的 API，而 MathEx 提供使用者方便引入自定義函數，簡單範例可以考[這裡](https://github.com/jserv/MathEX/blob/master/test-simple.c)。而我們可以參照範例，把 fib 加入函式庫。
```cpp
static struct expr_func user_funcs[] = {
{"nop", user_func_nop, user_func_nop_cleanup, 0},
{"fib", user_fib, user_fib_cleanup, 0},
{NULL, NULL, NULL, 0},
};
noinline int user_fib(struct expr_func *f, vec_expr_t args, void *c){
printk("I am in user_fib\n");
return 100;
}
```
首先註冊函數基本資料，然後簡單寫個 fib 運算，這裡只是測試能夠正常擴充，所以尚未實做運算。預期能得到結果：
```shell
$ echo -ne "fib(5)" > /dev/calc
$ dmesg
[26595.020599] calc: Received 6 -> fib(5)
[26595.020618] I am in user_fib
[26595.020622] calc: Result: 100
[26595.020636] calc: Device successfully closed
```
以上，順利完成擴充。接著我們來學習如何運用 livepatch 覆蓋原本的 fib() 運算。打開 livepatch-cal.c ，簡單觀察之後發現，覆蓋原本模組函數的機制很簡單，只需要在 `klp_func funcs[]` 註冊新的運算，然後而外實做運算 ( 想要覆蓋的新演算法 )。了解需要改的地方之後，接著來驗證一下。
```cpp
{
.old_name = "user_fib",
.new_func = livepatch_fib,
},
```
接著記得把 livepatch 模組掛載上去，得到以下輸出：
```shell
[ 3207.492266] livepatch: 'livepatch_calc': patching complete
[ 3216.199506] calc: Received 5 -> fib()
[ 3216.199528] livepatch_calc: function fib is now patched
[ 3216.199540] calc: Result: 0
[ 3216.199555] calc: Device successfully closed
```
可以清楚看到 livepatch 內的函數成功取代原本的演算法。
## 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作
首先回顧 quiz4，在 folly 實做的 vector 有提到幾個改善效能的議題：
* 減少 malloc, realloc 的次數
* 如何選擇 realloc 的大小
### 減少 malloc, realloc 的次數
第一點，malloc 和 realloc 其實很花時間，像是 realloc 如果新要的記憶體無法以目前的記憶體做連續的延伸，那就得再找其他一塊連續的記憶體，接著更討厭的是還要把先前的那一堆東西複製到新的記憶體。所以可想而知，記憶體的配置策略不但會影響**空間的**效能，也會影響**速度的**效能。但是這兩種效能我認為無法並進，只能在當中取得平衡。所以我在本專案的策略並不一定是最好，只是在兩者間取得平衡。
首先，我希望達到的目標是，減少 alloc 的次數。事實上，這個目標不夠嚴謹，若要達到最少次數，那我第一次直接要一大塊就好了，這樣 push 時永遠不會超過 capacity。所以，我們要做的應該是**合理且有限度的**減少 alloc 的次數。接著我們就來觀察哪些地方可以減少配置的次數。
仔細觀察 `expression.h` 中的 `vec_init()`
```cpp
#define vec_init() \
{ NULL, 0, 0 }
```
當 vec_expr_t 類別的變數被創立的時候呼叫，預設 capacity 是 0。但是仔細想想，這樣的安排是不好的，因為在所有的運算中，宣告的 vec_expr_t 類別變數，如：`es`。有很大的機率會新增 vector 的成員，所以將會遇到無法避免的 alloc。不過再仔細觀察處理 create_expression 時 vector 大小的變化可以發現，有某幾 struct expr 型態的變數都會經歷由容量 0 擴增 ( realloc ) 成 1，再擴增成 2。 既然如此，不如把 vector 的初始大小改成 2，以減少呼叫 realloc 的次數。此外，每次 create_expression 會創造的 vector 數量其實不多，所以每個都預設初始大小為 2 並不會造成太大的負擔。
接著著手修改 expression，找出 vector_init 定義的巨集：
```cpp
#define vec_init() \
{ malloc(2 * 40), 0, 2}
```
這個巨集當初始化 `es`, `os` 等等會被呼叫。這裡為了方便，沒有把分配的大小做彈性化處理，直接給 40 ( 一個 vec_expr_t 的大小 )。
再來將原本 `struct expr binary = expr_init()` 改成：
```cpp
struct expr binary = { \
(enum expr_type)0, \
{ \
.op = vec_init() \
} \
};
```
目前已經把所有初始化的大小都改成我的版本了，使用 `MathEx` 內提供的 test-bench.c 來測試效能。測試的項目大概是以下格式，目的是為了看看兩種不同方案的 allocate policy 速度差異如何：
```shell
test_benchmark("5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
test_benchmark("5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5");
..
```
分別用原版本 ( original allocator ) 的和我修改的版本 ( my allocator ) 在 gnuplot 展示速度差異，以下是 expression 長度對速度作圖：
可以發現若對初始化大小做修改的話，速度整體上來說能比原版本的略快。
### 如何選擇 realloc 的大小
第二點，在 folly 文件有提到，而我也有在 [quiz4](https://hackmd.io/W16BH33uRCyHup-Ob3sBPQ#%E8%A8%98%E6%86%B6%E9%AB%94%E9%85%8D%E7%BD%AE%E7%AD%96%E7%95%A5) 解釋為什麼要把擴大記憶體的 factor 設為 1.5。其實選擇 1.5 也有一個好處是，容易用 bitwise operation 實現。
接著來修改程式碼：將原本的
```cpp
int n = (*cap == 0) ? 1 : ((*cap << 1));
```
改成
```cpp
int n = (*cap == 0) ? 1 : ((*cap << 1) - (*cap >> 1));
```
再來設計一個簡單的實驗來看看效能如何，原本 MathEx 底下有提供 `test_benchmark` 來評估速度，邏輯是重複執行一百萬次，然後平均。雖然沒有拿掉 outliar ，但是為了方便還使勉強可以接受。現在要製造的情境是會一直 realloc，所以可以透過
```cpp
test_benchmark("a=1");
test_benchmark("a=1,a=1")
...
```
當然，為了方便，所以要寫一個 `char* repeat(char* orig, size_t times)` 來達到目的。這樣就能透過以下呼叫，來達到不同長度的執行。
```cpp
for(int i = 0; i < 3000; i++){
char *tmp = repeat("a=1,",i);
tmp[strlen(tmp) - 1] = '\0';
test_benchmark(tmp);
free(tmp);
}
```
可以看到，兩種 factor 的大小似乎對效能沒什麼提昇。選定 1.5 的原因是能夠重複利用之前已經 alloc 的區塊，而不用再複製一份一樣的到新的記憶體，進而增加速度。但是，我從上個作業就開始在懷疑改變 factor 真的能增加效能? 現代的 allocator 在 realloc 時真的會每次都要一塊全新的，然後再複製之前的到新記憶體，最後刪掉之前要的記憶體? 如果現代的 allocator 沒這麼笨的話，或許改變 factor 對效能起不了什麼太大的作用。
## 指出原本 fixed-point 實作的限制，觀察 Linux 核心所用的 fixed-point 運算程式碼，提出針對 kcalc 的改進方案
在 MathEx 中定點數的格式是：
```shell
28 | 1 | 3
----------------
int sign frac
```
而這裡的 frac 是指數的次方數，若是 -5，則最後的結果將是 $Integer \times 10^{frac}$。
而在 RT-Linux 中定點數的格式是：
```shell
1 | 14 | 17
-------------------
sign int frac
```
這邊轉換的方式我寫了一個函數，我認為會比較容易理解這種定點數是怎麼表示的
```cpp
void rt_fromfix(int tar){
double result;
result = (double)tar;
result = result / (1 << (31 - 14));
printf("%lf ",result);
}
```
### 兩種表示法之比較 ( MathEx v.s RT-Linux )
簡單列出幾個能比較的項目，分別是：
* 精準度
* 表示範圍
* 相關運算的速度
#### 精準度
在討論之前，先補上 MathEx 表示法如何轉換成浮點數的函數：
```cpp
void fromfix(int tar){
int num = tar >> 4;
int frac = tar & 15;
int neg = (frac & 8) >> 3;
if(neg > 0)
frac = -1 * ((~frac & 15) + 1);
printf("%lf\n",(double)num * pow(10, (double)frac));
}
```
在小範圍的精準度而言，可以觀察到 RT-Linux 限制在 0.000008 ( 約 $2^{-17}$ )。反觀，MathEx 的精準度可以高達 0.0000001 ($10^{-7}$)，下面用分佈圖展示兩種表示法能表達的密度：
可以很直覺的看出，MathEx 精準度比較好 ( 事實上，**精準度兩者各有好和壞的時候** )。但是，當表示的數字很大的時候，MathEx 的即大缺陷將會顯現。若 frac > 0，精準度將降為 $10^0$ 以上。反觀，RT-Linux 的表示法下，不論何種情況，精準度都是 $2^{-17}$，因為都會除以 `(1 << (31 - 14))`。
#### 表示範圍
RT-Linux 能表示的最大值落在 16384 左右 ( $\frac{2^{31}}{2^{14}}$ )，相較 MathEx 的 $2^{28} \times 10^8$ 就顯得很小。不過當 MathEx 來到這麼大的值下，精準度也不會好到哪裡，都是 $10^3$ 起跳。
#### 相關運算的速度
這裡來分別測試 MathEx 和 RT-Linux 在定點數轉浮點數，定點數乘法的速度。
##### 定點數轉浮點數
兩種表示法轉換的程式碼在前面已經提及，分別是 `fromfix` 和 `rt_fromfix`，簡單設計一個實驗來看看速度表現：
```cpp
for(int i = 100; i < 1000000; i++){
clock_gettime(CLOCK_REALTIME, &t1);
rt_fromfix(i);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%d ", i);
printf("%ld ", elapse(t1, t2));
clock_gettime(CLOCK_REALTIME, &t1);
fromfix(i);
clock_gettime(CLOCK_REALTIME, &t2);
printf("%ld \n", elapse(t1, t2));
}
```
若放大來看會發現 MathEx 轉換的速度會比較快。
##### 定點數乘法的速度
MathEx 的乘法沿用 expression.c 內提供的函數。
而 RT-Linux 的乘法是用組合語言寫的，擷取片段解釋：
```cpp
rt_fix rt_fix_mul(rt_fix x, rt_fix y,int i)
{
unsigned short iwl = x._iwl + y._iwl;
..
if(y._iwl < iwl) {
y._value >>= x._iwl;
}
if(x._iwl < iwl) {
x._value >>= y._iwl;
}
x._iwl = iwl;
__asm__("imull %%ebx\n\t"
"shrdl %%cl, %%edx, %%eax\n\t"
: "=a" (x._value)
: "a" (x._value), "b" (y._value), "c" (RT_FIXWL - x._iwl)
: "edx");
rt_fix_min_iwl(&x);
return x;
}
```
省略的部份是檢查 overflow 或 underflow 的判斷。成員變數 `_iwl` 是整數的 bit 數，我們選 14。而 `_value` 表示定點數。`rt_fix_mul` 首先會把兩個數字對齊 ( 但我們傳入的都是 14，所以沒差 )，接著組合語言 `imull` 負責做乘法 ( $a \times b$ )，`shrdl` 負責 shift ( 因為定點數相乘最後需要右移修正，在 Linux Kernel Load Average 計算分析有說明相同的概念 )。
再來又是簡單寫個實驗來評估兩種乘法的速度：
```cpp
for(int i = 0; i < 1000; i++){
rt_fix a, b, c;
a._value = 61526515;
a._iwl = 14;
b._iwl = 14;
b._value = 54545454;
c._iwl = 14;
c = rt_fix_mul(a,b,i);
}
```
結果有點令人小失望，用組合語言寫的乘法竟然沒有比較快。
Sign in with Wallet
Connect another wallet