# F04: kcalc
:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2019 年系統軟體課程](https://www.facebook.com/groups/system.software2019/)
:mega: 返回「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表
:::
==[作業說明直播錄影](https://youtu.be/jyflHdZMB2s)==
## 預期目標
* 重新學習數值系統：浮點運算和定點數
* 留意 Linux 核心程式撰寫的限制
* 撰寫可適用於使用者和核心層級的程式
* 自動測試機制
* 透過工具進行效能分析
## Linux 核心的浮點數運算
Robert Love 在 [Linux Kernel Development](https://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672329468/) 一書論及浮點運算:
> No (Easy) Use of Floating Point
> When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel.
* 解說: [Use of floating point in the Linux kernel](https://stackoverflow.com/questions/13886338/use-of-floating-point-in-the-linux-kernel)
Rusty Russell 在 [Unreliable Guide To Hacking The Linux Kernel](http://landley.net/kdocs/htmldocs/kernel-hacking.html) 則說:
> The FPU context is not saved; even in user context the FPU state probably won't correspond with the current process: you would mess with some user process' FPU state. If you really want to do this, you would have to explicitly save/restore the full FPU state (and avoid context switches). It is generally a bad idea; use fixed point arithmetic first.
## 數學式計算器
[Reverse Polish Notation](https://en.wikipedia.org/wiki/Reverse_Polish_notation)
- Reverse Polish notation (RPN) 中 operator 會放在所有 operand 後面
- 平常所使用的是 infix notation ，用括號 `( )` 表示順序
範例:
- Infix notation
* 運算子標為藍色，數值標為黑色
* human friendly
- Reverse Polish notation (RPN)
* computer friendly
- infix notation 轉 postfix notation
- [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)
- RPN evaluated from left to right
- 遇到數值 push 進 stack
- 遇到運算子取出 stack 前兩個運算，再把結果 push 進 stack
- 最後 stack 中剩下的那個數 (在 s[0]) 為答案
```
a : s[0] = a
1 : s[1] = 1
2 : s[2] = 2
+ : s[1] = s[1] + s[2]
b : s[2] = b
* : s[1] = s[1] * s[2]
+ : s[0] = s[0] + s[1]
3 : s[1] = 3
- : s[0] = s[0] - s[1]
```
MathEX 是成功大學師生開發的數學表示式求值工具，接受一組數學表達式，輸出這段數學表達式所對應的答案。
取得 `MathEX` 原始程式碼並測試:
```shell
$ git clone https://github.com/sysprog21/kcalc
$ cd kcalc/mathex
$ make check
```
預期可見以下測試輸出:
```
OK: six=6, seven=7, six*seven == 42.000000
OK: 小熊=6, 維尼=7, 小熊*維尼 == 42.000000
OK: τ=1.618, 3*τ == 4.854000
OK: $(τ, 1.618), 3*τ() == 4.854000
...
Execute build/test-bench...
BENCH 5: 9.383917 ns/op (106M op/sec)
BENCH 5+5+5+5+5+5+5+5+5+5: 137.161016 ns/op (7M op/sec)
BENCH 5*5*5*5*5*5*5*5*5*5: 127.733946 ns/op (7M op/sec)
BENCH 5,5,5,5,5,5,5,5,5,5: 102.152109 ns/op (9M op/sec)
BENCH ((5+5)+(5+5))+((5+5)+(5+5))+(5+5): 126.007080 ns/op (7M op/sec)
...
```
`MathEX` 基本的使用方式：
```clike
#include "expression.h"
/* Custom function that returns the sum of its two arguments */
static float add(struct expr_func *f, vec_expr_t args, void *c) {
float a = expr_eval(&vec_nth(&args, 0));
float b = expr_eval(&vec_nth(&args, 1));
return a + b;
}
static struct expr_func user_funcs[] = {
{"add", add, 0}, {NULL, NULL, 0},
};
int main() {
const char *s = "x = 40, add(2, x)";
struct expr_var_list vars = {0};
struct expr *e = expr_create(s, strlen(s), &vars, user_funcs);
if (!e) { printf("Syntax error"); return 1; }
printf("result: %f\n", expr_eval(e));
expr_destroy(e, &vars);
return 0;
}
```
上面的程式碼為範例，利用 `expr_create()` 將字串 `x = 40, add(2, x)` 輸入，再使用 `expr_eval()` 來產生輸出結果
### MathEx APIs
這個工具提供了 4 個 API：
- `struct expr *expr_create(const char *s, size_t len, struct expr_var_list *vars, struct expr_func *funcs)`：將輸入的字串數學表達式編譯成 `struct expr` 型態，並且回傳
- `float expr_eval(struct expr *e)`：計算 `struct expr` 的結果並回傳
- `void expr_destroy(struct expr *e, struct expr_var_list *vars)`：清除記憶體，`vars` 可以為 NULL (不清除 `vars` 的記憶體)
- `struct expr_var *expr_var(struct expr_var_list *vars, const char *s, size_t len)`：在給定的變數清單 `vars` 中回傳對應名稱 `s` 的變數，如果清單中不存在該變數則會產生一個並回傳
### 應用情境
這類的數學表達式分析工具可以被應用於工程計算機類的軟體，如：[insect](https://github.com/sharkdp/insect) 是個支援物理單位的工程計算機，其中程式碼 [insect/src/Insect/Parser.purs](https://github.com/sharkdp/insect/blob/master/src/Insect/Parser.purs) 就是計算機的數學表達式的解析器
## 解析 `MathEx` 程式碼
透過 `expression.h` 的 macro 以及 struct 可以找到用來表示 expression 的 struct：
```clike
#define vec(T) \
struct { \
T *buf; \
int len; \
int cap; \
}
typedef vec(struct expr) vec_expr_t;
struct expr {
int type;
union {
struct { float value; } num;
struct { float *value; } var;
struct { vec_expr_t args; } op;
struct {
struct expr_func *f;
vec_expr_t args;
void *context;
} func;
} param;
};
```
從上面的定義可以看到 `struct expr` 中，`param.op.args` 裡面其實包著 `struct expr` 的 pointer，在後續的程式中可以發現這個 pointer 會指向 1 或 2 個 `struct expr`，因此得知 `struct expr` 是一個 tree 的結構
接著可以透過 `expression.c` 中的 `expr_eval()` 中得知如何計算 expression 結果：
```clike
float expr_eval(struct expr *e)
{
float n;
switch (e->type) {
case OP_UNARY_MINUS:
return -(expr_eval(&e->param.op.args.buf[0]));
case OP_UNARY_LOGICAL_NOT:
return !(expr_eval(&e->param.op.args.buf[0]));
case OP_UNARY_BITWISE_NOT:
return ~(to_int(expr_eval(&e->param.op.args.buf[0])));
case OP_POWER:
return powf(expr_eval(&e->param.op.args.buf[0]),
expr_eval(&e->param.op.args.buf[1]));
case OP_MULTIPLY:
return expr_eval(&e->param.op.args.buf[0])
* expr_eval(&e->param.op.args.buf[1]);
case OP_DIVIDE:
return expr_eval(&e->param.op.args.buf[0])
/ expr_eval(&e->param.op.args.buf[1]);
case OP_REMAINDER:
return fmodf(expr_eval(&e->param.op.args.buf[0]),
expr_eval(&e->param.op.args.buf[1]));
}
...
}
```
從上面可以知道，它透過遞迴呼叫，計算目前節點的左子節點跟右子節點的結果，最後根據自己的 operator 將左子節點跟右子節點的結果作運算
### 效能分析
利用 `test-bench.c` 來查看結果：
```shell
BENCH 5: 5.650043 ns/op (176M op/sec)
BENCH 5+5+5+5+5+5+5+5+5+5: 39.499998 ns/op (25M op/sec)
BENCH 5*5*5*5*5*5*5*5*5*5: 38.609982 ns/op (25M op/sec)
BENCH 5,5,5,5,5,5,5,5,5,5: 42.056084 ns/op (23M op/sec)
BENCH ((5+5)+(5+5))+((5+5)+(5+5))+(5+5): 34.670115 ns/op (28M op/sec)
BENCH x=5: 3.753185 ns/op (266M op/sec)
BENCH x=5,x+x+x+x+x+x+x+x+x+x: 44.126987 ns/op (22M op/sec)
BENCH x=5,((x+x)+(x+x))+((x+x)+(x+x))+(x+x): 43.509007 ns/op (22M op/sec)
BENCH a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8,i=9,j=10: 59.928894 ns/op (16M op/sec)
BENCH a=1,a=2,a=3,a=4,a=5,a=6,a=7,a=8,a=9,a=10: 58.668852 ns/op (17M op/sec)
```
## 重新學習浮點運算和定點操作
* [浮點數運算和定點數操作](https://hackmd.io/s/H1SVhbETQ)
* [Fixed-point arithmetic](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)
* [fixed point arithmetic for RT-Linux](http://netwinder.osuosl.org/pub/netwinder/docs/nw/rt_fixed/doc/html/rt_fix.html)
* [include/rt_fix.h](http://netwinder.osuosl.org/pub/netwinder/docs/nw/rt_fixed/include/rt_fix.h)
* [src/rt_fix.c](http://netwinder.osuosl.org/pub/netwinder/docs/nw/rt_fixed/src/rt_fix.c)
* Linux 核心的 CFS 排程器就用到 fixed-point
* [linux/include/linux/sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h)
```clike
/*
* Integer metrics need fixed point arithmetic, e.g., sched/fair
* has a few: load, load_avg, util_avg, freq, and capacity.
*
* We define a basic fixed point arithmetic range, and then formalize
* all these metrics based on that basic range.
*/
```
* [linux/kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c)
```clike
/*
* The exact cpuload calculated at every tick would be:
*
* load' = (1 - 1/2^i) * load + (1/2^i) * cur_load
*
* If a CPU misses updates for n ticks (as it was idle) and update gets
* called on the n+1-th tick when CPU may be busy, then we have:
*
* load_n = (1 - 1/2^i)^n * load_0
* load_n+1 = (1 - 1/2^i) * load_n + (1/2^i) * cur_load
*
* decay_load_missed() below does efficient calculation of
*
* load' = (1 - 1/2^i)^n * load
*
* Because x^(n+m) := x^n * x^m we can decompose any x^n in power-of-2 factors.
* This allows us to precompute the above in said factors, thereby allowing the
* reduction of an arbitrary n in O(log_2 n) steps. (See also
* fixed_power_int())
*
* The calculation is approximated on a 128 point scale.
*/
```
* [Floating Point Numbers and printk()](http://www.kernelthread.com/publications/faq/335.html)
## 自我檢查清單
* 解釋浮點運算在 Linux 核心中為何需要特別對待，以及 context switch 的過程中，涉及到 FPU/SIMD context，該注意什麼？
* 提示: 參照 [Lazy FP state restore](https://en.wikipedia.org/wiki/Lazy_FP_state_restore) 和上方參考資料
* 應該撰寫對應包含浮點運算的 Linux 核心模組，實際編譯和測試
* 在給定的 `calc.c` 檔案中，和 [fibdrv](https://hackmd.io/s/SJ2DKLZ8E) 一樣有 character device，但註冊用的 kernel API 不同 (`register_chrdev` vs. `alloc_chrdev_region`)，能否解釋其差異和適用場合呢？
* 在 `scripts/test.sh` 檔案中，有一道命令為 `sudo chmod 0666`，這個作用為何？對於我們測試有何幫助？能否對 [fibdrv](https://hackmd.io/s/SJ2DKLZ8E) 建立的 `/dev/fibonacci` device file 也套用類似修改呢？另外，請解釋 device file 在核心及使用者層級的功能
* 在 `calc.c` 檔案中，用到 `copy_to_user` 這個 kernel API，其作用為何？本例使用該 API 做了什麼事？若是資料量增長，是否會有效能的嚴重衝擊呢？
* 找出至少 3 個 Linux 核心中使用定點數的案例，搭配程式碼解說
* 提示: 參照 [Linux Kernel Load Average 計算分析
](http://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/), [What Every Computer Scientist Should Know About Floating-Point Arithmetic](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html), [Load average explained](https://wiki.nix-pro.com/view/Load_average_explained)
* 是否知曉 MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
* 如何對 `MathEx` 進行效能分析？能否找出相似的 math expression 來分析比較呢？
* 提示: 參照 [muparserSSE - A Math Expression Compiler](http://beltoforion.de/article.php?a=muparsersse)
* 在 `MathEx` 原始程式碼的 `expression.[ch]` 裡頭 `vec` 相關的程式碼，主要做什麼事？有沒有發現類似 [list](https://hackmd.io/s/S12jCWKHN) 使用到的技巧呢？
* 提示: 參照 `mathex/test-unit.c` 的測試項目
* 解釋 `MathEx` 一類的 math expression 在真實世界有哪些應用？甚至，是否在 Linux 核心就存在類似的程式碼？
* 提示: 參照 [A thorough introduction to eBPF](https://lwn.net/Articles/740157/)
* 如果要將使用者層級的 C 語言程式，搬到 Linux 核心作為核心模組 (LKM)，該注意哪些議題呢？請舉例說明
* 提示: 注意 `__KERNEL__` 巨集的定義, [kmalloc](https://www.kernel.org/doc/htmldocs/kernel-api/API-kmalloc.html) 的使用, [vmalloc](https://www.kernel.org/doc/htmldocs/kernel-api/API-vmalloc.html) 的使用 (以及後兩者的差異)
* [fixed point arithmetic for RT-Linux](http://netwinder.osuosl.org/pub/netwinder/docs/nw/rt_fixed/doc/html/rt_fix.html) 的運作原理為何？給定的程式碼已經存在超過 20 年，很多細節已有出入，可否嘗試移植到 Linux `v4.15+` 呢？
## 作業要求
* 回答上述「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼，以第一手材料 (包含自己設計的實驗) 為佳
* 在 GitHub 上 fork [kcalc](https://github.com/sysprog21/kcalc)，主要目標是將 `MathEx` 整合到 `calc.c` 中 (作為 LKM 的形式)，過程中需要一併完成以下:
* 將 `MathEx` 的浮點數運算換為 fixed point，應該先在使用者層級驗證，然後再搬到 Linux 核心中。可斟酌移除 `MathEx` 裡頭的功能，但需要充分解釋;
* 量化 `MathEx` 在核心的執行時間，搭配 [fibdrv](https://hackmd.io/s/SJ2DKLZ8E) 撰寫的工具程式使用;
* 設計 micro-benchmarking 實驗，用以驗證 `MathEx` 移植到 Linux 核心後的表現;
* 嘗試解讀上述時間分佈，特別是隨著 Fibonacci 數列增長後，對於 Linux 核心的影響;
* 改善 `MathEx` 的執行效率;
* 請善用 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 一類地效能分析工具;
## 繳交方式
編輯 [Homework2 作業區共筆](https://hackmd.io/s/rygjaEK8V)，將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於新建立的共筆
## 截止日期
Mar 19, 2019 (含) 中午之前
越早在 GitHub 上有動態、越早接受 code review，評分越高
Sign in with Wallet
Connect another wallet