# 2020q1 Homework4 (kcalc)
contributed by < `kylekylehaha` >
> [作業內容](https://hackmd.io/@sysprog/linux2020-kcalc#截止日期)
>
###### tags: `linux2020`
## 測試環境
```shell
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.3.0-42-generic (buildd@lcy01-amd64-019)
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1))
```
## 作業要求
* [x] 找出至少 2 個 Linux 核心中使用定點數的案例，搭配程式碼解說
* [x] MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
* [x] 在 MathEx 中，nop 一類使用者自訂的函數如何實作呢？
* [x] 是否發現 MathEx 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？
* [x] 將 fibdrv 作業的成果透過 livepatch，整合進 kcalc。
* [ ] 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作
## Linux 核心中使用定點數的案例
### Linux kernel load average
計算 load average 時，採用**指數平滑法**以及**定點數**。這邊我們主要討論**定點數**的運用。
這邊簡單介紹定點數:
* 定點數的加法和減法可直接進行
* 定點數的乘法需要將乘法運算後的結果除以 $b^n$ (b: 進制 ; n: 小數的位數)
* 定點數的除法需要將除法運算後的結果乘以 $b^n$ (b: 進制 ; n: 小數的位數)
e.g.
浮點數 0.5 換成 3 位精準度的定點數: $0.5 \times 10^3 = 500$
* 當兩浮點數 0.5 + 0.5 = 1.0 時，轉成定點數 500 + 500 = 1000 ，轉成浮點數仍為 1。同理，減法也是。
* 當兩浮點數 0.5 * 0.5 = 0.25，轉成定點數 500 * 500 = 250000，轉成浮點數為 250000/1000 = 250，和原本答案 0.25 不同。修正方法為定點數: (500 * 500) / 1000 = 250，轉成浮點數為0.25
* 除法和乘法一樣需要做修正，然而是將運算結果乘以1000。浮點數0.5/0.02 = 25，定點數500/20 = 25，轉成浮點數為0.025，和正確答案25有所不同，故須乘以1000來修正。
在探討code之前，需要先了解 linux load average 如何計算。
$$
load_t = load_{t-1} * \alpha + n * (1 - \alpha)
$$
其中，$\alpha$ 對應於 1min, 5min, 15min 分别是0.920044415, 0.983471454, 0.994459848。
由於該公式不能直接在 linux kernel 用浮點數計算，因此採用定點數來運算。這裡我們用 1min 來解釋，將小數位數定為 2 進制的的 11 位。
* $\alpha$: 0.920044415 轉成定點數 $0.920044415 * 2^{11}$ = 1884
* 將 n 和常數 1 也轉成定點數 $n * 2^{11}$, $1 * 2^{11}$
* 將 $n * (1 - \alpha)$ 轉成 $((n * 2^{11}) * (1 * 2^{11} - 1884)) / 2^{11}$
最後可以將原本公式改寫成
$$
load_t * 2^{11} = (load_{t-1} * 1884 + (n * 2^{11}) * ((1 * 2^{11}) - 1884)) / 2^{11}
$$
---
終於，來進入我們的程式碼。
在[include/linux/sched.h](https://elixir.bootlin.com/linux/v4.0/source/include/linux/sched.h#L154) 中，先來看一些marco
```cpp
#define FSHIFT 11 /* nr of bits of precision */
#define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */
#define LOAD_FREQ (5*HZ+1) /* 5 sec intervals */
#define EXP_1 1884 /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5 2014 /* 1/exp(5sec/5min) */
#define EXP_15 2037 /* 1/exp(5sec/15min) */
```
* FSHIFT: 定點運算中11位表示小數的精度。
* FIXED_1: 定點數的1
* LOAD_FREQ: linux 每 5 秒計算一次。
* EXP_1: 1min 的 $\alpha$
* EXP_5: 5min 的 $\alpha$
* EXP_15: 15min 的 $\alpha$
接著，在[kernel/sched/proc.c](https://elixir.bootlin.com/linux/v4.0/source/kernel/sched/proc.c)，我們來看`calc_global_load`，當中呼叫`calc_load`即為上述公式的運算。
```cpp
void calc_global_load(unsigned long ticks)
{
long active, delta;
if (time_before(jiffies, calc_load_update + 10))
return;
/*
* Fold the 'old' idle-delta to include all NO_HZ cpus.
*/
delta = calc_load_fold_idle();
if (delta)
atomic_long_add(delta, &calc_load_tasks);
active = atomic_long_read(&calc_load_tasks);
active = active > 0 ? active * FIXED_1 : 0;
avenrun[0] = calc_load(avenrun[0], EXP_1, active);
avenrun[1] = calc_load(avenrun[1], EXP_5, active);
avenrun[2] = calc_load(avenrun[2], EXP_15, active);
calc_load_update += LOAD_FREQ;
/*
* In case we idled for multiple LOAD_FREQ intervals, catch up in bulk.
*/
calc_global_nohz();
}
```
```cpp
/*
* a1 = a0 * e + a * (1 - e)
*/
static unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
load *= exp;
load += active * (FIXED_1 - exp);
load += 1UL << (FSHIFT - 1);
return load >> FSHIFT;
}
```
當 load average 計算出來後，我們必須正確的將結果顯示出來。
在[fs/proc/loadavg.c](https://elixir.bootlin.com/linux/v4.0/source/fs/proc/loadavg.c) 可以找到一下程式碼。
```cpp
#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
static int loadavg_proc_show(struct seq_file *m, void *v)
{
unsigned long avnrun[3];
get_avenrun(avnrun, FIXED_1/200, 0);
seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
nr_running(), nr_threads,
task_active_pid_ns(current)->last_pid);
return 0;
}
```
`LOAD_INT`: 即為將小數去掉，顯示整數部份。
`LOAD_FRAC`: 因 FIXED_1 = $100000000000_2$，FIXED_1 - 1 = $011111111111_2$。透過 AND 的方式即可取出小數部份。
接著將其乘以 100 後，再取 `LOAD_INT`，即為小數前面的兩位數。
### time(7)
[time(7)](http://man7.org/linux/man-pages/man7/time.7.html)
## MathEx 如何解析給定字串，從而分離出變數和對應數學表示法呢？
從 `test-simple.c`中，可以看到在 `main`中主要呼叫兩個函式: `expr_create` & `expr_eval`。
* `expr_create`: 將字串轉成 `expr` type。
* `expr_eval`: 則是計算結果，並回傳 float 型態。
```cpp
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;
}
float result = expr_eval(e);
printf("result: %f\n", result);
expr_destroy(e, &vars);
return 0;
}
```
`expr_create`:
* 在503行，呼叫`expr_next_token`，去找出token。
```cpp=502
for (;;) {
int n = expr_next_token(s, len, &flags);
...
```
* 找出token後，依照不同的類型進入不同的 if else block
`expr_calc`:
* 採用遞迴的方式
* 若為單元運算子，則取出一個即可。e.g. `case OP_UNARY_MINUS`
* 若為二元運算子，則須取出兩個做運算。e.g. `case OP_DIVIDE`
```cpp
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_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]);
...
default:
return NAN;
}
}
```
## 在 MathEx 中，nop 一類使用者自訂的函數如何實作呢？
在 `experssion.h`中，可以找到 `struct expr_func`。
* `name`: 函式名稱
* `f`: function pointer
```cpp
/*
* Functions
*/
typedef float (*exprfn_t)(struct expr_func *f, vec_expr_t args, void *context);
struct expr_func {
const char *name;
exprfn_t f;
exprfn_cleanup_t cleanup;
size_t ctxsz;
};
```
在 `test-simple.h`中，我們定義 `add`，並將自己定義的函式加入 `user_funcs[]`。之後，`user_func` 也會一同被丟入 `expr_create`，去判斷字串中是否含有自定義的函式。
```cpp
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 },
};
```
在 `expression.c` 中可以找到 `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;
}
```
## 是否發現 MathEx 對於負數的除法結果不正確、乘法和加法的 overflow 沒有做處理，且缺乏對減法的 underflow 處理機制呢？你預計如何克服？
**除法負數處理**
在做除法之前，我們先判斷被除數或除數是否為負數，用` sign` 來紀錄該運算結果為正或負。因此我們將 `n1` 及 `n2` 都變為正數後再去做除法運算後，其結果與正確結果差一個原本的 `sign` 。故在最後 `n3` 乘上 `sign` 做修正。
```cpp
static int divid(int a, int b)
{
...
int sign = 1;
...
/* check if there is negative number */
if (n1 < 0) {
sign = -sign;
n1 = -n1;
}
if (n2 < 0) {
sign = -sign;
n2 = -n2;
}
...
int n3 = (n1 / n2) * sign;
int frac3 = frac1 - frac2;
return FP2INT(n3, frac3);
}
```
**加法的 overflow 處理**
當計算完 `n1 + n2` 時，須檢查是否產生 overflow。如果產生 overflow，則一律回傳 -1，並用 `printk` 印出發生overflow。
```cpp
static int plus(int a, int b)
{
...
/* check whether it is overflow */
int n3 = n1 + n2;
if ((n3 > 0) && (n1 < 0) && (n2 < 0)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
if ((n3 < 0) && (n1 > 0) && (n2 > 0)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
return FP2INT(n3, frac1);
}
```
**乘法的 overflow 處理**
乘法的部份，分成 `frac` 與 `num` 兩個部份:
`frac` 判斷方式和加法一樣: 當兩個正數相加變成負數時，即為發生overflow ; 當兩個負數相加變成正數時，即為發生 overflow。
`num` 判斷方式我們採**乘完的結果除乘數，應為被乘數**，來判斷是否發生 overflow。
如果發生 overflow，則印出警告訊息，並回傳 -1。
```cpp
static int mult(int a, int b)
{
int frac1 = GET_FRAC(a);
int frac2 = GET_FRAC(b);
int n1 = GET_NUM(a);
int n2 = GET_NUM(b);
int n3 = n1 * n2;
/* check whether num is overflow */
if ((n2 != 0) && (n1 != n3 / n2)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
/* check whether frac is overflow */
int frac3 = frac1 + frac2;
if ((frac3 > 0) && (frac1 < 0) && (frac2 < 0)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
if ((frac3 < 0) && (frac1 > 0) && (frac2 > 0)) {
printk("Error: overflow\n");
return FP2INT(-1 , 0)
}
return FP2INT(n3, frac3);
}
```
**減法 underflow 的處理**
判斷減法 underflow，分成兩種 case:
* 當被減數 `n1` 大於結果 `n3`，`n2` 小於零。
* 當被減數 `n1` 小於結果 `n3`，`n2` 大於零。
```cpp
static int minus(int a, int b)
{
...
/* check whether it is underflow */
int n3 = n1 - n2;
if ((n1 > n3) && (n2 < 0)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
if ((n1 < n3) && (n2 > 0)) {
printk("Error: overflow\n");
return FP2INT(-1, 0);
}
return FP2INT(n3, frac1);
}
```
## 將 fibdrv 作業的成果透過 livepatch，整合進 kcalc。
根據上面所談到的，若要加入自訂的函數，只須在 `user_funcs[]` 加入即可。這邊我們加入 `user_func_fib` 和 `user_func_fib_cleanup`。
我們在 `user_func_fib` 中先呼叫 `expr_eval(&vec_nth(&args, 0))`，來取得變數 `n`，也就是欲計算的第 `n` 項 fibonacci number。之後，在傳入計算 fibonacci 的函式 `fib_clz`。(此函式目前錯誤的，之後要利用 livepatch 進行修補。)
```cpp
noinline void user_func_fib_cleanup(struct expr_func *f, void *c)
{
/* suppress compilation warning */
(void) f;
(void) c;
}
noinline int fib_clz(int n)
{
printk("Use fib_clz to calculate fib %d\n", n);
return 0;
}
noinline int user_func_fib(struct expr_func *f, vec_expr_t args, void *c)
{
/* test */
int n = expr_eval(&vec_nth(&args, 0));
return fib_clz(n);
}
static struct expr_func user_funcs[] = {
{"nop", user_func_nop, user_func_nop_cleanup, 0},
{"fib", user_func_fib, user_func_fib_cleanup, 0},
{NULL, NULL, NULL, 0}
};
```
接著來到 `livepatch-calc.c` 中，在 `funcs` 內加入欲修改的函式。
* `.old_name` 為欲修改的函式名稱。
* `.new_func` 為用來修補的函式名稱。
因此，我們在這邊利用 `livepatch_fib` 來修補原本的 `fib_clz`。
```cpp
static struct klp_func funcs[] = {
{
.old_name = "user_func_nop",
.new_func = livepatch_nop,
},
{
.old_name = "user_func_nop_cleanup",
.new_func = livepatch_nop_cleanup,
},
{
.old_name = "fib_clz",
.new_func = livepatch_fib,
},
{
.old_name = "user_func_fib_cleanup",
.new_func = livepatch_fib_cleanup,
},
{},
};
```
這邊我們利用 [fibdrv](https://hackmd.io/K_HYJqW9QqeoC463kw871w#%E5%8A%A0%E5%85%A5-clzctz-%E6%8C%87%E4%BB%A4) 中的 `clz` 指令，以及 fast doubling 來做 fibonacci 的計算。
`n` 為 `expr_eval` 的回傳值，其中 MathEx 的格式由左至右分別為:
* int(28 bits)
* sign(1 bit)
* frac(3 bits)
故真實所代表的 number，其公式為:
$$
number = (int)_{10} * 10^{(frac)_{10}}
$$
也就是 `script/eval.sh` 中 `fromfixed` 的內容。
```cpp
int livepatch_fib(int n)
{
printk("livepatch_fib is now patched\n");
int num = n >> 4;
int frac = n & 15;
if (frac >= 8) {
printk("Warning: Invalid number!");
return -1;
}
for (int i = 0; i < frac; i++)
num *= 10;
if (num < 0)
return -1;
int clz = __builtin_clz(num);
int digit = 32 - clz;
num <<= clz;
int fn = 0, fn1 = 1;
for (int i = 0; i < digit; i++) {
int f2n, f2n1;
f2n1 = fn1 * fn1 + fn * fn;
f2n = fn * 2 * fn1 - fn * fn;
fn = f2n;
fn1 = f2n1;
if (num & 0x80000000) {
fn = f2n1;
fn1 = f2n + f2n1;
}
num <<= 1;
}
printk("expecedt answer is %d\n", fn);
return fn << 4;
}
```
來測試一下，在 `scripts/test.sh` 中加入 fib(11)。
```shell
# pre-defined function
test_op 'fib(11)'
# Livepatch
sudo insmod $LIVEPATCH_CALC_MOD
sleep 1
echo "livepatch was applied"
test_op 'fib(11)'
```
```shell
$ ./scripts/test.sh
...
Testing fib(11) ...
0
livepatch was applied
Testing fib(11) ...
89
[18690.427898] livepatch_calc: livepatch_fib is now patched
[18690.427904] expected answer is 89
[18690.427906] calc: Result: 1424
[18690.427913] calc: Device successfully closed
[18690.430197] calc: size: 5 result: 1424
[18690.430240] calc: Device successfully closed
Disabling livepatch...
Complete
```
## 觀察原始程式碼的 expression.[ch] 裡頭 vec 相關的程式碼，將 quiz4 使用到的技巧予以應用，提出對空間效率更好的實作
Sign in with Wallet
Connect another wallet